数据挖掘-K-近邻算法

怼烎@ 2021-09-21 13:24 375阅读 0赞

## **微信搜索：“二十同学” 公众号，欢迎关注一条不一样的成长之路** ##

### 1. K-近邻算法 ###

k-近邻算法（k Nearest Neighbor），是最基本的分类算法，其基本思想是采用测量不同特征值之间的距离方法进行分类。

### 2. 算法原理 ###

存在一个样本数据集合（训练集），并且样本集中每个数据都存在标签（即每一数据与所属分类的关系已知）。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较（计算距离），然后提取样本集中特征最相似数据（最近邻）的分类标签。一般会取前k个最相似的数据，然后取k个最相似数据中出现次数最多的标签（分类）最后新数据的分类。  
因此，这是一个很“懒惰”的算法，所谓的训练数据并没有形成一个“模型”，而是一个新的数据需要分类了，去和所有训练数据逐一比较，最终给出分类。这个特征导致在数据量较大时，性能很差劲。

### 3. 算法过程 ###

对未知类别属性的数据集中的每个点依次执行以下操作：  
1）计算已知类别数据集中的点与当前点之间的距离（欧式距离、曼哈顿距离或者余弦夹角等各种距离算法，具体情况具体分析用哪种）；  
2）按照距离递增次序排序；  
3）选取与当前点距离最小的k个点；  
4）确定前k个点所在类别的出现频率；  
5）返回前k个点出现频率最高的类别作为当前点的预测分类。

欧氏距离计算：

1.  二维平面上两点*A*(x1,y1)与*B*(x2,y2)间的欧氏距离：  
    　　
    
    ![e851ff42a143d189ef85206925a388e0.webp][]
2.  三维空间两点*A*(x1,y1,z1)与*B*(x2,y2,z2)间的欧氏距离：  
    　　
    
    ![d7c68cc7ea883e661a3f6275a2916b8a.webp][]
3.  n维空间两点的欧式距离以此类推

### 4. 计算案例 ###

我还是瞎编一个案例，下表有11个同学的小学成绩和12年后读的大学的情况，现在已知“卫”同学的小学成绩了，可以根据kNN来预测未来读啥大学。

![a7833951f0b3d032f923ae85401c4c4d.webp][]

逐一计算各位同学与卫同学的距离，然后我们选定3位（即这里的k=3）最为接近的同学，推测卫同学最终的大学

![2ff5dba207aa998cd89a6508947514eb.webp][]

3位同学中2个清华，1个北邮，所以卫同学很有可能在12年后上清华。

### 5. 算法要点 ###

1） K的选择，一般不超过训练集数量的平方根  
2）距离更近的近邻也许更应该决定最终的分类，所以可以对于K个近邻根据距离的大小设置权重，结果会更有说服力  
3）如果采用欧氏距离计算，不同变量间的值域差距较大时，需要进行标准化，否则值域较大的变量将成为最终分类的唯一决定因素

非常感谢：**点赞**、**收藏**和**评论**

**微信搜索：“二十同学” 公众号，或者直接扫一扫，关注一条不一样的成长之路**

![20201202173850460.jpg][]

[e851ff42a143d189ef85206925a388e0.webp]: /images/20210920/2abd5a5a52ba4edf810580bb78fe460b.png
[d7c68cc7ea883e661a3f6275a2916b8a.webp]: /images/20210920/d670e4c2709747519e1ee33ebcda6ed4.png
[a7833951f0b3d032f923ae85401c4c4d.webp]: /images/20210920/20b6944025f7481e96843e3e5a819f86.png
[2ff5dba207aa998cd89a6508947514eb.webp]: /images/20210920/e657a43986f447a09f3f85375cca4683.png
[20201202173850460.jpg]: /images/20210920/1c6e2eb7f2d54ceead4112764815d642.png