Skip to content

Commit 361f197

Browse files
change knn
1 parent 16b5393 commit 361f197

3 files changed

Lines changed: 50 additions & 30 deletions

File tree

knn/KNN.ipynb

Lines changed: 27 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -57,7 +57,7 @@
5757
},
5858
{
5959
"cell_type": "code",
60-
"execution_count": null,
60+
"execution_count": 5,
6161
"metadata": {},
6262
"outputs": [],
6363
"source": [
@@ -66,7 +66,7 @@
6666
},
6767
{
6868
"cell_type": "code",
69-
"execution_count": null,
69+
"execution_count": 6,
7070
"metadata": {},
7171
"outputs": [
7272
{
@@ -86,7 +86,9 @@
8686
"model = knn, dataNum = 10000, takeTime = 0.47404\n",
8787
"model = kdtree, dataNum = 10000, takeTime = 0.16433\n",
8888
"model = knn, dataNum = 50000, takeTime = 2.0887\n",
89-
"model = kdtree, dataNum = 50000, takeTime = 0.93545\n"
89+
"model = kdtree, dataNum = 50000, takeTime = 0.93545\n",
90+
"model = knn, dataNum = 400000, takeTime = 16.82156\n",
91+
"model = kdtree, dataNum = 400000, takeTime = 11.85994\n"
9092
]
9193
}
9294
],
@@ -102,9 +104,29 @@
102104
},
103105
{
104106
"cell_type": "code",
105-
"execution_count": null,
107+
"execution_count": 7,
106108
"metadata": {},
107-
"outputs": [],
109+
"outputs": [
110+
{
111+
"name": "stdout",
112+
"output_type": "stream",
113+
"text": [
114+
"<knn.knn_kdtree.Node object at 0x1091d00b8>\n",
115+
"<knn.knn_kdtree.Node object at 0x1091d0240>\n",
116+
"<knn.knn_kdtree.Node object at 0x1091d0080>\n"
117+
]
118+
},
119+
{
120+
"data": {
121+
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvNQv5yAAAIABJREFUeJzt3XmUXFW5/vHvW9Vd1VMSMiFkItGEMTJoMyuESYJCAhIkQbgy5ncZxAtcEJlEcEAQvVwFIYKCCkRARpn0AoIgEYIMAgkaAmSCJCQhQ3fX/P7+qCb2UJ2uJFV1qqqfz1q90lX79Dlvzup++vQ+++xt7o6IiFSXUNAFiIhI4SncRUSqkMJdRKQKKdxFRKqQwl1EpAop3EVEqpDCXUSkCincRUSqkMJdRKQK1QR14CFDhvjo0aODOryISEV66aWXPnT3ob1tF1i4jx49mtmzZwd1eBGRimRm7+WznbplRESqkMJdRKQKKdxFRKqQwl1EpAoFdkNVSmfpe8t58IbHmffyfIZ9aismnXEoYz69TdBliUgRKdyr3AuPvswVx1xLOpUmlUjxylNv8KdfP80pV32Vo77+xYIcY9G/3mfmVffx9z+9RqS+loknHcjksyZS31RfkP2LyMazoFZiam5udg2FLK62lhhf2epUYi3xbm2R+ggzXv0Rw8duvVnHeGv225x/4OXE2xJk0pn1+/7ENkP52d9+QEM/BbxIIZnZS+7e3Nt26nOvYs8/8CJmlrMtk0rz2C1PbvYxfnTS9bSti60PdoBEW4Kl7y7j3v/5w2bvX0Q2jcK9Arhn8Mxq3JMb9XWrlq4mlUjlbEsl0yxbtGKz6lr63nKWzF+asy0RS/LYL5/arP2LyKZTn3sZc8/gLb+AlpvBW4EQXn8E1u8iLNTU69eP2XkbaiI1JHMEfF1DlB32HLdZ9cVaYoTDPV8fxFq7dweJSGnoyr2M+Zpvw7obwFcDSSAObQ/iK6fmdRW/6wE7MWjrgYRyBHC4NswhJ+y3WfUNG7tVzn0DWMjYZcJOm7V/Edl0Cvcy5ekl0HY/0NalJQHpRRB/otd9hEIhrnni24zaYQR1jVHqm+qo71fP4GED+dFTl9M4oHGzaqyN1HL8pVOoa4h2a4vURTj+0imbtX8R2XTqlilX8efo8Xevt+Jtj2J1E3vdzdARg5nx6o9468V5LJy7hMHDB7HrATsRChXm9/rR5xxOOp3hju/+HgzSqQyDthrA+b86izHjRxXkGCKy8RTuZSsMZtDTSFUL570nM2P7Pcax/R6b18fe076PPX8yR539RRa8uYhoQ4QR2w7rcZSOiJSGwr1cRfeDNblHukADVndEScvpTSRay9jdxgRdhgSsZXULT975HIv/9T4jtxvGhKn70ti/Ieiy+iSFe5my8BC88WRouY3O/e5RqN0hG/4iZeSVp17n0klXgWdHStU1Rrnp/F/z3Ye+xc777Rh0eX2ObqiWMWs6B/pfDuFRQAhsIDSeig26DduIbhmRYmtZ3cKlk39IrCW+fghsrCVO29oYlxzxA9rWdR0YIMWmK/cyZmZYw1HQcFTQpYhs0FMz/wqZ3DeIPOM8fdfzTDz5wBJX1bcp3CvIgrmLWbbgQ4aP24qtx3wi6HJE1ls87/0eH1qLtcR5v4cnmaV4FO4VYOl7y/nO0dewYM7i7BOn8SQ77LUtl951LgOG9A+6PBFGbjuMusZozknq6prqGDZ2qwCq6tvU517mEvEk3/jcJbz96nvE2xK0rG4lEUvyxnNzOf+g7xDUrJ4iHU2Yui8Wyj38NRwOsd8xe5e4IlG4l7lnfz+L1tWtnWZdhOzEXx+8s4zXnn4zoMpE/q2hXz3ff/gi6vvVU9dUB2Sv2BsHNPD9Ry6ivrEu4Ar7HnXLlLnXnnmTtnWxnG2JWII5s/6pOVykLIz/3A78bvFNPH33LN6fv5ThY7div2P2zjk9hRSfwr2IVry/ivuue5jnH5pNpC7CoScdwMSTD9yob/YBQ/oTrgmTTqW7tdVEamka2PvskCKlUt9Uz8STDgi6DEHhXjQL5i7mG/tcTLwtTjKefdJ04VuLeXjGn/jfv34v7yXoDj5hP+75yR9yhrtnMnz+6D0LWreIVAf1uRfJtafeQMvq1vXBDhBvTbBk3gfcfe1Dee9n5HbDOfaCyUQ7XO1byIg2RDjjupM0WkZEctIaqkXw0fLVHDfyP3MukgEwZPgg7lx400bt89U/v8E9P36IJfOXMmb8SI45bxLb7T62EOWKSAXJdw3VvLplzGwicB0QBm5296u6tI8CbgO2aN/mQnd/ZKOrrhKta9oI14Z7DPeebpBuyC4TdtKNUxHJW6/dMpadxOR64DBgR2CamXWdBegS4C533w2YCtxQ6EIryZajhhCu6Xnul81d3k5EpDf59LnvAcxz9/nungBmApO7bOPAx52/A4AlhSux8tTU1nDcxUfnHBUTbYhwwuVfCaAqEelL8umWGQ4s7PB6EdB1iMblwB/N7OtAI3BwQaqrYMecdwTx1ji/u/oBamrDZDIZInURzrv5dHbca9ugyxORKpdPuOd6prjrXdhpwK3ufq2Z7Q38xszGu3unxyrNbDowHWDUqOpegs3MOOGyY5hy3hH8c/bbROoibNv8ScJhTdUrIsWXT7gvAkZ2eD2C7t0upwATAdz9eTOrA4YAyzpu5O4zgBmQHS2ziTVXlPrGOnbZXzdCRaS08ulzfxEYZ2ZjzCxC9obpg122WQAcBGBmOwB1wPJCFioiIvnrNdzdPQWcBTwOzCE7KuYNM7vCzCa1b3YecJqZvQrcCZzomq5QRCQweY1zbx+z/kiX9y7r8PmbwL6FLU1ERDaVph8QEalCCncRkSqkcBcRqUIKdxGRKqRwFxGpQgp3EZEqpHAXEalCCncRkSqkcBcRqUIKdxGRKqRwFxGpQgp3EZEqpHAXEalCec0KKSKyqdydZ+6ZxV1X388H7y5nqzFbMvWbR/K5L++JWa6F3qQQFO4iUlQ3/fdtPDzj/4i1xAFYs2ItV5/4M+b87V9Mv/qEgKurXuqWEZGiWfjWYh668U/rg/1jsZY4D/zsUZa8/UFAlVU/hbuIFM3Tdz9POpnO2ZZJZ3jmnlklrqjvULiLSNHEW+OkU7nDPZVME2uJlbiivkPhLiJFs+sB46lvqsvZVtdUxy4TdipxRX2Hwr0Pi7fFefnJf/Dyk/8g3hbv/QtENtJuB32a4eO2pjbSeexGbbSGkdsNY9cDxgdUWfXTaJk+6v6fPcotF91BKJQdipbJOKd8bxpHfv2LAVcm1SQUCvGjJ7/NtafdyKyHXqI2UkMykWKfyc2cM+M/NRSyiBTufdCff/ccN194O/HWzlfrN3/rDrbYcgATjt03oMqkGjUOaOSyu85j7ap1fLh4JUOGD6LfwKagy6p66pbpg3516cxuwQ7Zm1+/umRmj1/n7iyYu5h5r7xDMpEsZolShfoNbGLM+FEK9hLRlXsfk0qmeP/tpT22vz9/Kalkiprazt8aLz/5D6499eesXr6GUCiEhYz/uPwYjjr7S/rTWqQMKdz7mHBNmJpIDcl47ivvmkiYcE2403vzXn6HSyddRbw10en9X148k5raGiadMbFo9YrIplG3TB9jZhwwdV/CteFubeHaMBOO3bfblfhtl99Foi3Rbft4a5zbvv27Hscxi0hwFO590GlXH8/grQcSqY+sfy9SH2Hw1gOZfk33uT5e/8sc3HPvKxFLsvS95cUqVQLg6cV48l+4d/+FLpVD3TJ90BZDBzDjtWt59OYnePLOZwE4cNrnOOzUg2js39Bt+0h9BD5qybmvdCpDXWO0qPVKaXjyDXz1NyH1Hlg2GrzxdKzxNN1XqUAK9z6qsX8DU849ginnHtHrtoeeOIF7fvwQyXiqW9vonUYwaKuBxShRSshTC/CVXwVvbX+jfTTVuutxUljTGcEVJ5tE3TLSq2MvmMzQkUOI1NWufy9cE6K+Xx3n3nx6gJVJoXjLzZCzG6YNWmbgrjlgKo3CXXrVOKCRG2b/kK9ecjTDPrUVQ4YP4gsnHsBNL/+IsbuOCbo8KYT4s0D3v8yyQpB8q5TVSAGoW0by0ti/geMuOprjLjo66FKkGGxD903SYPUlK0UKQ1fuIgL1U4DcszdiA6FmXEnLkc2ncBcRrPE4qBkFdLyCDwF12IAfarRMBVK4iwhm9digu6DpDAiPhNBgiH4BG3w3Ft0z6PJkE+TV525mE4HrgDBws7tflWObrwCXAw686u7HFbBOESkyCzVgTadDk0ZAVYNew93MwsD1wCHAIuBFM3vQ3d/ssM044FvAvu6+ysy2LFbBIiLSu3y6ZfYA5rn7fM8+jzwTmNxlm9OA6919FYC7LytsmSIisjHyCffhwMIOrxe1v9fRtsC2Zvacmc1q78YREZGA5NPnnus2eddppGqAccAEYATwFzMb7+4fddqR2XRgOsCoUaM2uliRvqxtXRvLF61k4CcGaMEL6VU+4b4IGNnh9QhgSY5tZrl7EnjHzN4iG/YvdtzI3WcAMwCam5t7mGdQRDpKxBLccM6v+NNtzxCuDZFKpGk+dBfOu/l0BgzpH3R5Uqby6ZZ5ERhnZmPMLAJMBR7sss39wAEAZjaEbDfN/EIWKuXL0x/gqXdx17zuxfCdKdfyp18/QyKWoG1tjGQ8yQuPvsw39r2EVLKnKQOkr+s13N09BZwFPA7MAe5y9zfM7Aozm9S+2ePACjN7E3gKON/dVxSraCkPnnyNzIeH48sPwVcciS/bh0xLz2uwVgv3JJmW35BZ/gUyS/cks/IkPDG7KMd65x/v8epTr3dbLCWdTLPy/VU8d98LRTmuVL68xrm7+yPAI13eu6zD5w6c2/4hfYCn3sZX/keHKWIBWmHtD8jghBqnBVle0bin8VWnQuJloH2mxMRz+MqX8P5XEmroOpBs87zy1BtkMrl7MNvWxZj1yN/Z/yv7FPSYUh30hKpsEl93A+ScBrYN1v2Y7B98VSj+f5B8lfXBvl4M1n674FPjRupqCYVz/5iaGfVaKEV6oHCXTRN/Dsj00JiE9HulrKZkvPX3//5rpZsQxJ8v6PH2mbw7nsl9nqMNEQ4+fr+CHk+qh8JdNo1Fem7zNFgPMwxWuh6DHbJ9U/GCHm7gJ7bg+MuOIdrQ+Qq9rjHK3pOa2WGvbQt6PKkems9dNk39UdByC5Bj9Z7wcCzc9Tm3KhE9AJKv0b1bBvAk1O5W8ENOu/AoxowfxR3f+z0L/7mEwVsPZMq5R/CFEydotkbpkcJdNok1nozHHoL0Mv4d8CEgig34foCVFZc1HIO3/KJ9SbqO3SV1UH84Fv5EUY671+GfZa/DP1uUfUt1UreMbBILDcAG3weNJ0NoS7AtIHooNvgeLPKZoMsrGgv1xwbfDbWfASJgjUA9NByH9b8i6PJE1tOVu2wyCw3A+p0L/frWCFirGYkNvgNPL4fMR1AzAtMydFJmFO5ScO4ZSM1t74PeHtvg+pyVy8JDITw06DJEclK4S0F57El8zcXgbWR7/Rxv+jqhxpODLk2kT1G4S8F44iX8o/+i20iStdeRob5qn1oVKUe6oSoF4+v+h5xDBGmDdddlu2tEpCQU7lI4ydd6bvNWyGiBLpFSUbhLAW1oxEgarKFklWyMTCZD69o20mlNWSzVQ+EuhVN/FFCbo8GgdlcsVF4LS6TTaX773d9z9NCT+fLgkzhyi6/x83NuJd5W2CkERIKgcJeCsabTIbw10HHoYy1YEzbgu0GV1aOrv/YzZl51L+tWtZBOpYm1xPnDTX/km4dcSaaHybpEKoXCXQom+/Tm/dB0NoTHQngbaDgBG/IwVjMm6PI6eW/OIp6992/EWzvPjZOIJXn7tfd4+Yl/BFSZSGFoKKQUlIWasKbToOm0oEvZoNmPvUJ2jZnuYutiPHvfC3z2kF1KXJVI4ejKXfokCxmQe0ZFMwiHNduiVDaFu/RJex3+WXqaLTfaWMfnp+xd2oJECkzhLn3SsE9txcEn7NdtEYxIfYQd996WnffbMaDKRApD4S591jd+Pp1TfnAcQ4YPAoP+g/tx7DeP5LsPXahFMKTiWU83lYqtubnZZ8+eHcixRbpydwV6hfL4c3jLLZBeAOHRWOOpWHSvoMsqGjN7yd2be9tOo2VEQMFeoTLrrod1M4C27BvpBXjiRbzpTEJN0wOtLWjqlhGRiuSphbDuRtYH+3ptsO6nePr9IMoqGwp3EalIHnuYzuvYdmqF2COlLKfsKNxFpDJl1gDJHhoTeGZtKaspOxUb7ulUmg8Xr6B1bdc/yUSkL7BIc88zjVpDVS/Uno+Ku6Hq7tx1zQPM/OH9JGNJMukMnzlkZ/7rxukMGT446PJEpFSi+0NoS0gvAlIdGmogtDVEPhdUZWWh4q7cb77wt/zmintYt6qFeFuCZCLFi4+9wpl7fIuW1S1BlyciJWIWxgbdAbWfAaJg/bL/RpqxwbdjVnHxVlAVdeW+ZuVa7v/poyRinfvZMukMLatbeOyXT3L0OUcEVJ2IlJqFh2CDf4unF0N6CYRHYOGtgy6rLFTUr7bXn51LTST376N4a4Jnfv+3ElckIuXAwsOxyO4K9g4qKtxrajf8h0ZttKL+EBERKZqKCvddJuxIJpN7uoS6xiiHnnhAiSsSESlPFRXu0fooZ/zkRKINkU7vR+pqGbn9cCYcu09AlYmIlJeK68c47JSDGDJiML++/C7eee09GgY0cPj/O4SvnD+Z2kiuxZlFRPqeigt3gN0P3ZXdD9016DJERMpWXt0yZjbRzN4ys3lmduEGtptiZm5mvU5HKSIixdNruJtZGLgeOAzYEZhmZt2WqTGzfsDZgMYjiogELJ8r9z2Aee4+390TwExgco7trgSuBmIFrE9ERDZBPuE+HFjY4fWi9vfWM7PdgJHu/ocN7cjMppvZbDObvXz58o0uVkRE8pNPuOdaomb9YHPLTuDwE+C83nbk7jPcvdndm4cOHZp/lSIislHyCfdFwMgOr0cASzq87geMB/5sZu8CewEP6qaqiEhw8gn3F4FxZjbGzCLAVODBjxvdfbW7D3H30e4+GpgFTHJ3rX4tIhKQXsPd3VPAWcDjwBzgLnd/w8yuMLNJxS5QREQ2Xl4PMbn7I8AjXd67rIdtJ2x+WSIisjkqam4ZERHJj8JdRKQKKdxFRKqQwl1EpAop3EVEqpDCXUSkCincRaqMp98n89F/k/ng02Q+2IHMiml44qWgy5ISU7iLVBFPL8U/PBJifwDiQBqSL+ErT8LjzwVdnpSQwl2kB+4JMi13kvnwKDLLDyWz5ko8vaT3LwyQr7sRfC2Q6dISw9dchnvuBeal+lTkMntSHdwTkHgRPAGR3bDQFkGXtJ57HF8xDVLzWL9EQetCvO1eGHQ7VtttvZryEH8MSOVuSy+DzBIID8/dLlVF4S6ByLQ+AGsvZ/2M0p7EG76K9buA7CzSwfKW2zsHOwAp8BS++gJsyAaXLgiOd71i78jA0yUrRYIV/E+R9DkenwVrLgVvwY6aix01F4hD6514y42bts9MC578J55eUZgi22bS46JiqQV4amHutqDVHQiEc7eFBkB4ZO42qToKdyk5X/e/5A7ONmi5Bfdk/vvyBJnV38GX7Y2vPBZfvj+ZlSfg6Q82s8iWntssDL5u8/ZfJNZ4Blg93dfYqYN+l2CWa+0dqUYKdym91Bzsy4uyH8+3ZT/aX0MKNiKY/aMLoO33QKw9kBOQmI2vmIJnWje9xtrP0vOPRwZqxmz6vovIakZig++GyN5kr+DDEB6DbXEdofpDgy5PSkh97lJ61q/nNk9BaAPtnTZdAPEnyA756ygNmXV42wNY47RNK7HpDDz+NNDWpaUeGk7GrG6T9lsKVvMpbNCtuMfBk1ioKeiSJAAKdym9hqn4vauAOHx5EQB+7wggBJHm/EfNJGe3d5HkamyF+FOwqeFeuz0MvAFffUH7XwQh8CQ0nIA1fX2T9llqZlGwaNBlSEAU7lJy1ngyHnuifTTKx+rAGrD+39uIPdWRe/32dqHGTawwy6L7wtC/QOpN8Dao2UFXwVIxFO5ScmZ1MPhOiD2CP3QPeAzqDsEajt24se7R/Xoe2mcNWP3RBag1BLXjN3s/IqWmcJdAmEWg/kis/shN30eoCe93Eaz9Pp1H39RDZC+I7LPZdVYiT87NPqmafAmsCRqOy/7itEjQpUkJKdylooUap+I1o/GWGyD5FoQGQ8PXsIYpZfEwVKl5/Dl81elAguwUBEth7TV47GEY9GsFfB+icJeKZ9G9sOheQZcROPcMvvp8uj9DEIPkHGh7EBqmBFGaBKDvXdqIVKvkP7I3fnNqw9t+V9JyJFgKd5Fq4a1scPRQZgNP3UrVUbiLVIvanbJj8XM3QvTzJS1HgqVwF6kSFuoPDdOA+hyNEazxxFKXJAFSuItUEev3TWg4HqjPDoOkDsJjsUG3Y+Gtgy5PSkijZUSqiFkY638+3nQmpOeD9cdqRgVdlgRA4S5ShSzUACE9WduXqVtGRKQKKdxFRKqQumWkbHns//CWmyC1EMLDsKbpED1UqwmJ5EHhLmUps/Yn0HIr0Na+QtNr+H1vQ/3fsf4XBVydSPlTt4yUHU8thJZf0m0VJG+D1pl46u1A6hKpJLpyl/ITfxzItF+xgz3fHvJfXgQY/vjDWL+zAytPpBLoyl3Kj7cBqZ4aNzA5loh8LK9wN7OJZvaWmc0zswtztJ9rZm+a2Wtm9oSZbVP4UqUU3NN4ZhXuiY37wtbWwhUR2ROsHr93RPZj7/rsx70j8Pu2xaJ7F+5YIlWq13A3szBwPXAYsCMwzcx27LLZy0Czu+8M3ANcXehCpbjc02TWXY8v2wNf9nl86WfJrP4Wnlnb+xd/8AFsuSUsXVqYYmp3h/BYoOvCErUQHgGRzxXmOCJVLJ8r9z2Aee4+37OXczOByR03cPen3P3jS7dZwIjClinF5msuhXUzwNdiX56PffltaHsIXzkN73GmwXb33w8tLdl/C8DMsEG3QvQgIILftz1+7ychOiE7R0ofXGFJZGPlc0N1OLCww+tFwJ4b2P4U4NHNKUpKy1OLoO0hIN6lJQHpRRB/EuoO7f6F48fD3Lngnn19xhlw5pmw/fbw+uubVZOFmrCB1+GZjyD9AYQ/gYUGbtY+RfqSfMI91xMjnnNDs+OBZmD/HtqnA9MBRo3SZEZlI/EcEOphdAr4I49hucL9jjvgiCNg+XJoa4NoNNs9c+edBSvNQltAaIuC7U+kr8jn79tFwMgOr0cAS7puZGYHAxcDk9y96yUgAO4+w92b3b156NChm1KvFEV4gwv49HgNsPPOcNllkEpBfX3238sug09/uhhFishGyCfcXwTGmdkYyy6dPhV4sOMGZrYbcBPZYF9W+DI7S6fTZDKZYh+m74juD57ueXRK/eE9f+1vfws1NXDeedl/f/Ob0tUtIj3qNdzdPQWcBTwOzAHucvc3zOwKM5vUvtk1QBNwt5m9YmYP9rC7zfL6c3M5e5+LOCwyjcOi07joi9/nvTmLinGoPsXCQ6HxZLqv4FMHNeMhsoHl2U4/PdvvfuWV2X9PP72YpYpInsw9Z/d50TU3N/vs2bPz3v7Vp9/g4i99n3jrv8dfm0FdUz03vHgVI7YdVowy+wx3x9vuh5YbsjdRbQA0Ho81Tif7B5uIlAMze8ndm3vbrmLGlF1/9i87BTtkB2nEWmL86tKZAVVVPcyMUMNRhIb+idBWcwh9YhahprMU7CIVqiLCfc3KtSx8q9s9XAA847zw8N9LXJGISHmriHDvTTAdSyIi5asiwr3/oH6M3C53n7qFjD2/9JkSVyQiUt4qItwBzvzfk4k2dO7/NYO6xjpOunJqQFWJFIe7k4glCGrAg1S+ign3Xfbfiasev5Qd9hqXvfkXDtF86G78dNb3NVJGqoa7c+91D3PssNM4oul4JvU/gZ+fcyux1pzPBYr0qGKGQnaUTqWxkBEKVczvJpG8/PSsm/njrX/uFOa10Vo+ufMorvvr9wiHwwFWJ+Wg6oZCdhSuCSvYpeosW7CcR295sttVejKeZMGcxfxNo8JkIyghRcrE7MdfJRTOPclP27oYz9z9fIkrkkqmcBepEGYbnN1NpBOFu0iZ2P2w3cikc98Dq2uqY/+v7FPiiqSSKdxFysTQEYP50vSDqWuIdnq/tq6W0TuNZPfDdg2oMqlECneRMnLG/5zEqT/8KoOHDcQMGvrXc+RZh/GjJ7+tkTKyUSpyKKRIX5BOpQnXKNCls6oeCinSFyjYZXMo3EVEqlA+C2SLFFwmk+Efz8xh+aIVbLPjCMZ95pNBlyRSVRTuUnLzXnmHSw6/ita1reDZ+VSGj92a7z1yEYO3Hhh0eSJVQd0yUlItq1s4/8DvsGLJStrWxmhbFyPWEufdNxZwwcHf0SyIIgWicJeS+uOvnyaVSHV7P53KsHzhCl575s0AqhKpPgp3Kak5z/+zx+lrU8kUb7/ybmkLEqlS6nOXkhoyYhDhmjDpVLpbW02khi22HBBAVRIU9wwknsXjfwNrxOq/iNWMDrqsqqArdympw045iHBtD+O3HfaZvHtpC5LAeOYjfMUk/KOzofUX0PIz/MMjyKy5WvdeCkDhLiU1crvhnHTlVKL1EULh7LdfTaSGaEOUi2ee021eFalevvpCSL0D3tr+TgqIQ+vtEH8iyNKqgrplpOSmnHsEux44ngeuf4wP5i9j7GfGMPnMiWw1esugS5MS8cxKiD8LJHO0tuEtv8DqDi51WVVF4S6BGLvrGM77xelBlyFBSb8PFgFP9NC+qLT1VCF1y4hI6YW37jnYAcIjS1dLlVK4i0jJWWgQRPcDanM01mON00teU7VRuItIIGzAVVAzDqyh/Z1aIAoNJ2J1BwZZWlVQn7uIBMJC/WHwfZB4Hk+8gFkj1E3EatQlUwgKdxEJjJlBdB8sqvVhC62iwt0zqyD2CJ5ejtVuB9GDMIsEXZaISNmpmHDPtD0Gqy9ofxXDrRGsHgbdjtWMCbQ2EZF8rP5wDe/PX8rgYYMYOmJwUY9VEeHuqYXtwR7r8GYLeCu+8mQY+mT2zzsRkTLUtq6NH592I3994EU6OWFIAAAFoUlEQVRqo7Uk40m222MsF93+DYYML07IV8RoGW+9g+yjyd1awFdB4oVSlyQikrdLJ/2Q5x54kUQsScvqVhKxJG/+9S3O3udiErENjPffDHmFu5lNNLO3zGyemV2Yoz1qZr9rb/+bmY0uaJWpf5E73AF3SC8o6OFERArlX3+fz9wX5pGMdZ5qIZ3KsG5VC8/cM6sox+013M0sDFwPHAbsCEwzsx27bHYKsMrdxwI/AX5Y0CprxpLzYQcAC0F4REEPJyJSKK8/O5dMOpOzrW1djNmPv1KU4+Zz5b4HMM/d57t7ApgJTO6yzWTgtvbP7wEOsgJ2glvDtB5KNbB+ENmzUIcSESmo+qY6wjW5ozYUMpoGNhbluPmE+3BgYYfXi9rfy7mNu6eA1UDB7hJYzTbQ/3tAtP2D7FNttgU26JeYVcStAxHpg/aZvHuPV+61dREOOWH/ohw3n1TMdQXedSb9fLbBzKab2Wwzm718+fJ86lsv1DAJG/oUNJ0LDSdj/b+DbfkMVjN2o/YjIlJK/Qf3Y/o1JxBt6PxMTl1jlIO++jm22704GZbPUMhFQMfngUcAS3rYZpGZ1QADgJVdd+TuM4AZAM3NzRu91IqFh2BNJ23sl4mIBGrymYcxevwoZl51H+++sYghwwcx5dwj2G/KXkU7Zj7h/iIwzszGAIuBqcBxXbZ5EPga8DwwBXjStU6WiMh6u+y/E7vsv1PJjtdruLt7yszOAh4HwsAv3f0NM7sCmO3uDwK3AL8xs3lkr9inFrNoERHZsLyeUHX3R4BHurx3WYfPY8AxhS1NREQ2lYaZiIhUIYW7iEgVUriLiFQhC2pQi5ktB97biC8ZAnxYpHIqlc5Jdzon3emcdFbp52Mbdx/a20aBhfvGMrPZ7t4cdB3lROekO52T7nROOusr50PdMiIiVUjhLiJShSop3GcEXUAZ0jnpTuekO52TzvrE+aiYPncREclfJV25i4hInsou3ANf0q8M5XFOzjWzN83sNTN7wsy2CaLOUurtnHTYboqZuZlV9eiIfM6HmX2l/fvkDTO7o9Q1lloePzejzOwpM3u5/Wfni0HUWTTuXjYfZCcmexv4JBABXgV27LLNGcCN7Z9PBX4XdN1lcE4OABraPz9d52T9dv2AZ4BZQHPQdQf8PTIOeBkY2P56y6DrLoNzMgM4vf3zHYF3g667kB/lduUe+JJ+ZajXc+LuT7l7a/vLWWTn3K9m+XyfAFwJXA3ESllcAPI5H6cB17v7KgB3X1biGkstn3PiQP/2zwfQfZ2KilZu4R74kn5lKJ9z0tEpwKNFrSh4vZ4TM9sNGOnufyhlYQHJ53tkW2BbM3vOzGaZ2cSSVReMfM7J5cDxZraI7Ky3Xy9NaaWR15S/JVSwJf2qSN7/XzM7HmgGirMoY/nY4Dmx7KK6PwFOLFVBAcvne6SGbNfMBLJ/2f3FzMa7+0dFri0o+ZyTacCt7n6tme1Ndk2K8e6ee8HTClNuV+4bs6QfG1rSr4rkc04ws4OBi4FJ7h4vUW1B6e2c9APGA382s3eBvYAHq/imar4/Nw+4e9Ld3wHeIhv21Sqfc3IKcBeAuz8P1JGdd6YqlFu4r1/Sz8wiZG+YPthlm4+X9IO+saRfr+ekvQviJrLBXu19qdDLOXH31e4+xN1Hu/tosvchJrn77GDKLbp8fm7uJ3vjHTMbQrabZn5JqyytfM7JAuAgADPbgWy4Ly9plUVUVuHe3of+8ZJ+c4C7vH1JPzOb1L7ZLcDg9iX9zgV6HAZXDfI8J9cATcDdZvaKmXX9Jq4qeZ6TPiPP8/E4sMLM3gSeAs539xXBVFx8eZ6T84DTzOxV4E7gxGq6UNQTqiIiVaisrtxFRKQwFO4iIlVI4S4iUoUU7iIiVUjhLiJShRTuIiJVSOEuIlKFFO4iIlXo/wN7Vchil0gbWwAAAABJRU5ErkJggg==\n",
122+
"text/plain": [
123+
"<matplotlib.figure.Figure at 0x1091d0fd0>"
124+
]
125+
},
126+
"metadata": {},
127+
"output_type": "display_data"
128+
}
129+
],
108130
"source": [
109131
"point = (0.3, 0.2)\n",
110132
"model = KNNKdTree()\n",

knn/knn_kdtree.py

Lines changed: 16 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -45,30 +45,43 @@ def preOrder(self, node):
4545
self.preOrder(node.lchild)
4646
self.preOrder(node.rchild)
4747

48-
# 搜索kdtree的前n个近的点
48+
# 搜索kdtree的前count个近的点
4949
def search(self, x, count = 1):
5050
nearest = []
5151
for i in range(count):
5252
nearest.append([-1, None])
53-
self.nearest = np.array(nearest) # 初始化n个点
53+
# 初始化n个点,nearest是按照距离递减的方式
54+
self.nearest = np.array(nearest)
5455

5556
def recurve(node):
5657
if node is not None:
58+
# 计算当前点的维度axis
5759
axis = node.depth % self.n
60+
# 计算测试点和当前点在axis维度上的差
5861
daxis = x[axis] - node.data[axis]
62+
# 如果小于进左子树,大于进右子树
5963
if daxis < 0:
6064
recurve(node.lchild)
6165
else:
6266
recurve(node.rchild)
63-
67+
# 计算预测点x到当前点的距离dist
6468
dist = np.sqrt(np.sum(np.square(x - node.data)))
6569
for i, d in enumerate(self.nearest):
70+
# 如果有比现在最近的n个点更近的点,更新最近的点
6671
if d[0] < 0 or dist < d[0]:
72+
# 插入第i个位置的点
6773
self.nearest = np.insert(self.nearest, i, [dist, node], axis=0)
74+
# 删除最后一个多出来的点
6875
self.nearest = self.nearest[:-1]
6976
break
7077

78+
# 统计距离为-1的个数n
7179
n = list(self.nearest[:, 0]).count(-1)
80+
'''
81+
self.nearest[-n-1, 0]是当前nearest中已经有的最近点中,距离最大的点。
82+
self.nearest[-n-1, 0] > abs(daxis)代表以x为圆心,self.nearest[-n-1, 0]为半径的圆与axis
83+
相交,说明在左右子树里面有比self.nearest[-n-1, 0]更近的点
84+
'''
7285
if self.nearest[-n-1, 0] > abs(daxis):
7386
if daxis < 0:
7487
recurve(node.rchild)

perceptron/perceptron_base.py

Lines changed: 7 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -9,22 +9,17 @@ class PerceptronBase(object):
99
原始形态感知机
1010
"""
1111
def __init__(self, eta=0.1, n_iter=50):
12-
self.eta = eta # 学习率
13-
self.n_iter = n_iter # 迭代次数
12+
# 学习率
13+
self.eta = eta
14+
# 迭代次数
15+
self.n_iter = n_iter
1416

1517
def fit(self, X, y):
16-
"""
17-
拟合函数,使用训练集来拟合模型
18-
:param X:training sets
19-
:param y:training labels
20-
:return:self
21-
"""
22-
# X's each col represent a feature
23-
# initialization wb(weight plus bias)
18+
# 初始化参数w,b
2419
self.w = np.zeros(X.shape[1])
2520
self.b = 0
26-
# the main process of fitting
27-
self.errors_ = [] # store the errors for each iteration
21+
# 记录所有error
22+
self.errors_ = []
2823
for _ in range(self.n_iter):
2924
errors = 0
3025
for xi, yi in zip(X, y):
@@ -39,19 +34,9 @@ def fit(self, X, y):
3934
return self
4035

4136
def sign(self, xi):
42-
"""
43-
计算净输入
44-
:param xi:
45-
:return:净输入
46-
"""
4737
return np.dot(xi, self.w) + self.b
4838

4939
def predict(self, xi):
50-
"""
51-
计算预测值
52-
:param xi:
53-
:return:-1 or 1
54-
"""
5540
return np.where(self.sign(xi) <= 0.0, -1, 1)
5641

5742

0 commit comments

Comments
 (0)