数据挖掘学习札记：KNN算法（一）

向右看齐 2022-08-22 11:26 167阅读 0赞

参考：

1. [KNN算法介绍][KNN]，[Python][]程序和一个简单算例

2. [k-nearest neighbor algorithm][]

基本想法：

在距离空间里，如果一个样本的最接近的k个邻居里，绝大多数属于某个类别，则该样本也属于这个类别。俗话叫，“随大流”。

算法描述：

**\[plain\]**  [view plain][]   [copy][view plain]

1.  1. 依公式计算 Item 与 D1、D2 … …、Dj 之相似度。得到Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)。  
2.  2. 将Sim(Item, D1)、Sim(Item, D2)… …、Sim(Item, Dj)排序，若是超过相似度阈值t则放入邻居案例集合NN。  
3.  3. 自邻居案例集合NN中取出前k名，依多数决，得到Item可能类别。

参数K的选取：

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。比如下图，

[![220px-KnnClassification.svg.png][]][220px-KnnClassification.svg.png 1]

待测样本（绿色圆圈）既可能分到红色三角形类，也可能分到蓝色正方形类。如果k取3，从图可见，待测样本的3个邻居在实线的内圆里，按多数投票结果，它属于红色三角形类，票数1:2.但是如果k取5，那么待测样本的最邻近的5个样本在虚线的圆里，按表决法，它又属于蓝色正方形类，票数2（红色三角形）:3（蓝色正方形）。

其它问题：

计算两者间距离，用哪种距离会更好呢？计算量太大怎么办？假设样本中，类型分布非常不均，该怎么办呢？

例子（电影分类）：

<table style="font-size:14px; line-height:26px; margin:0px; padding:0px; color:rgb(73,73,73); font-family:simsun; width:500px; background-color:rgb(215,215,215)"> 
 <tbody> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 电影名称</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 打斗次数</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 接吻次数</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 电影类型</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      California Man&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 3</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 104</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Romance</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      He’s Not Really into Dudes&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 2</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 100</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Romance</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      Beautiful Woman&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 1</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 81</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Romance</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      Kevin Longblade&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 101</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 10</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Action</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      Robo Slayer 3000&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 99</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 5</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Action</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 
    <div>
      Amped II&nbsp;  
    </div> 
    <div>
      &nbsp;  
    </div> </td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 98</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 2</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Action</td> 
  </tr> 
  <tr> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 未知</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 18</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> 90</td> 
   <td style="margin:0px; padding:0px; font-family:Verdana,宋体,sans-serif; line-height:18px"> Unknown</td> 
  </tr> 
 </tbody> 
</table>

这个数据用打斗次数和接吻次数来界定电影类型，接吻多的是Romance类型的，而打斗多的是动作电影。现在有一部名字未知的电影，打斗次数为18次，接吻次数为90次的电影（这里名字未知是为了防止能从名字中猜出电影类型），它到底属于哪种类型的电影呢？

下面调用Python的sklearn模块求解：(转自[KNN算法介绍][KNN])

**\[python\]**  [view plain][]   [copy][view plain]

1.  **import** numpy as np  
2.  **from** sklearn **import** neighbors  
3.  knn = neighbors.KNeighborsClassifier() \#取得knn分类器  
4.  data = np.array(\[\[3,104\],\[2,100\],\[1,81\],\[101,10\],\[99,5\],\[98,2\]\]) \# <span style="font-family:Arial, Helvetica, sans-serif;">data对应着打斗次数和接吻次数</span>  
5.  labels = np.array(\[1,1,1,2,2,2\]) \#<span style="font-family:Arial, Helvetica, sans-serif;">labels则是对应Romance和Action</span>  
6.  knn.fit(data,labels) \#导入数据进行训练'''  
7.  knn.predict(\[18,90\])

说明：

首先，用labels数组中的1和2代表Romance和Aciton，因为sklearn不接受字符数组作为标志，只能用1,2这样的int型数据来表示，后面处理可以将1和2映射到Romance和Action上来。fit则是用data和labels进行训练，data对应的是打斗次数和接吻次数构成的向量，称之为特征向量。labels则是这个数据所代表的电影所属的类型。调用predict 进行预测，将未知电影的特征向量代入，则能分析出该未知电影所属的类型。此处计算结果为1,也就是该未知电影属于Romance，和直觉相符。

[KNN]: http://blog.sina.com.cn/s/blog_7fc305440101d0vr.html
[Python]: http://lib.csdn.net/base/11
[k-nearest neighbor algorithm]: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
[view plain]: http://blog.csdn.net/zhaoyl03/article/details/8666906#
[220px-KnnClassification.svg.png]: /images/20220722/58ff3c68f06d41caa8b730a5acb87aa7.png
[220px-KnnClassification.svg.png 1]: http://en.wikipedia.org/wiki/File:KnnClassification.svg