深度学习之八:机器学习之 KNN 原理与代码实现
KNN 原理与代码实现
本文系作者原创,转载请注明出
处:https://www.cnblogs.com/further-further-further/p/9670187.html
1. KNN 原理
KNN(k-Nearest Neighbour):K-近邻算法,主要思想可以归结为一个成语:物以类聚
1.1 工作原理
给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的 k (k <= 20)个实例,
这 k 个实例的多数属于某个类,
就把该输入实例分为这个类。
https://www.cnblogs.com/ybjourney/p/4702562.html 给出的例子很形象,这里借用一下。
如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果 K=3,由于红色三角形所占
比例为 2/3,绿色圆将被赋予红色三角形那个类,
如果 K=5,由于蓝色四方形比例为 3/5,因此绿色圆被赋予蓝色四方形类。
由此也说明了 KNN 算法的结果很大程度取决于 K 的选择。
1.2 欧氏距离公式
计算两个向量点 xA 和 xB 之间的距离
1.3 分类决策规则(如多数表决)
决定 类别 , 为指示函数,即当 时 为 1,否则 为 0。
1.4 算法流程
对未知类别属性的数据集中的每个点依次执行以下操作:
1. 计算已知类别数据集中的点与当前点之间的距离;
2. 按照距离递增次序排序;
3. 选取与当前点距离最小的 k 个点;
4. 确定前 k 个点所在类别的出现频率;
5. 返回前 k 个点出现频率最高的类别作为当前点的预测分类;
2. 代码实现
python3.6
每个方法的作用,以及每行代码的作用,同样我都做了详细的注解。
希望大家最好自己能实现一下,特别是在运算时 list,array,matrix 之间的关系以及运用场景,
只有在你自己实现时,才能理清这三者的作用以及关系。
2.1 输入数据
datingTestSet2.txt :约会网站数据(三种类型:不喜欢的人,魅力一般的人,极具魅力的人)
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
72993 10.141740 1.032955 1
35948 6.830792 1.213192 3
42666 13.276369 0.543880 3
67497 8.631577 0.749278 1
35483 12.273169 1.508053 3
50242 3.723498 0.831917 1
63275 8.385879 1.669485 1
5569 4.875435 0.728658 2
51052 4.680098 0.625224 1
77372 15.299570 0.331351 1
43673 1.889461 0.191283 1
61364 7.516754 1.269164 1
69673 14.239195 0.261333 1
15669 0.000000 1.250185 2
28488 10.528555 1.304844 3
6487 3.540265 0.822483 2
37708 2.991551 0.833920 1
22620 5.297865 0.638306 2
28782 6.593803 0.187108 3
19739 2.816760 1.686209 2
36788 12.458258 0.649617 3
5741 0.000000 1.656418 2
28567 9.968648 0.731232 3
6808 1.364838 0.640103 2
41611 0.230453 1.151996 1
36661 11.865402 0.882810 3
43605 0.120460 1.352013 1
15360 8.545204 1.340429 3
63796 5.856649 0.160006 1
10743 9.665618 0.778626 2
70808 9.778763 1.084103 1
72011 4.932976 0.632026 1
5914 2.216246 0.587095 2
14851 14.305636 0.632317 3
33553 12.591889 0.686581 3
44952 3.424649 1.004504 1
17934 0.000000 0.147573 2
27738 8.533823 0.205324 3
29290 9.829528 0.238620 3
42330 11.492186 0.263499 3
36429 3.570968 0.832254 1
39623 1.771228 0.207612 1
32404 3.513921 0.991854 1
27268 4.398172 0.975024 1
5477 4.276823 1.174874 2
14254 5.946014 1.614244 2
68613 13.798970 0.724375 1
41539 10.393591 1.663724 3
7917 3.007577 0.297302 2
21331 1.031938 0.486174 2
8338 4.751212 0.064693 2
5176 3.692269 1.655113 2
18983 10.448091 0.267652 3
68837 10.585786 0.329557 1
13438 1.604501 0.069064 2
48849 3.679497 0.961466 1
12285 3.795146 0.696694 2
7826 2.531885 1.659173 2
5565 9.733340 0.977746 2
10346 6.093067 1.413798 2
1823 7.712960 1.054927 2
9744 11.470364 0.760461 3
16857 2.886529 0.934416 2
39336 10.054373 1.138351 3
65230 9.972470 0.881876 1
2463 2.335785 1.366145 2
27353 11.375155 1.528626 3
16191 0.000000 0.605619 2
12258 4.126787 0.357501 2
42377 6.319522 1.058602 1
25607 8.680527 0.086955 3
77450 14.856391 1.129823 1
58732 2.454285 0.222380 1
46426 7.292202 0.548607 3
32688 8.745137 0.857348 3
64890 8.579001 0.683048 1
8554 2.507302 0.869177 2
28861 11.415476 1.505466 3
42050 4.838540 1.680892 1
32193 10.339507 0.583646 3
64895 6.573742 1.151433 1
2355 6.539397 0.462065 2
0 2.209159 0.723567 2
70406 11.196378 0.836326 1
57399 4.229595 0.128253 1
41732 9.505944 0.005273 3
11429 8.652725 1.348934 3
75270 17.101108 0.490712 1
5459 7.871839 0.717662 2
73520 8.262131 1.361646 1
40279 9.015635 1.658555 3
21540 9.215351 0.806762 3
17694 6.375007 0.033678 2
22329 2.262014 1.022169 1
46570 5.677110 0.709469 1
42403 11.293017 0.207976 3
33654 6.590043 1.353117 1
9171 4.711960 0.194167 2
28122 8.768099 1.108041 3
34095 11.502519 0.545097 3
1774 4.682812 0.578112 2
40131 12.446578 0.300754 3
13994 12.908384 1.657722 3
77064 12.601108 0.974527 1
11210 3.929456 0.025466 2
6122 9.751503 1.182050 3
15341 3.043767 0.888168 2
44373 4.391522 0.807100 1
28454 11.695276 0.679015 3
63771 7.879742 0.154263 1
9217 5.613163 0.933632 2
69076 9.140172 0.851300 1
24489 4.258644 0.206892 1
16871 6.799831 1.221171 2
39776 8.752758 0.484418 3
5901 1.123033 1.180352 2
40987 10.833248 1.585426 3
7479 3.051618 0.026781 2
38768 5.308409 0.030683 3
4933 1.841792 0.028099 2
32311 2.261978 1.605603 1
26501 11.573696 1.061347 3
37433 8.038764 1.083910 3
23503 10.734007 0.103715 3
68607 9.661909 0.350772 1
27742 9.005850 0.548737 3
11303 0.000000 0.539131 2
0 5.757140 1.062373 2
32729 9.164656 1.624565 3
24619 1.318340 1.436243 1
42414 14.075597 0.695934 3
20210 10.107550 1.308398 3
33225 7.960293 1.219760 3
54483 6.317292 0.018209 1
18475 12.664194 0.595653 3
33926 2.906644 0.581657 1
43865 2.388241 0.913938 1
26547 6.024471 0.486215 3
44404 7.226764 1.255329 3
16674 4.183997 1.275290 2
8123 11.850211 1.096981 3