【1】KNN（K-nearest neighbors algorithm）

基本原理

KNN算法又叫最近邻居法，是一种非常简单易于掌握的分类算法。

其基本原理是，存在一个已知标签的数据集合，也就是训练样本集。

这个样本集中的每一个数据所属的分类都是已知的。

当一个没有标签的新数据需要确定自己属于哪个分类的时候，

只需要把新数据的每个特征和训练集中的每个数据的特征进行比较，

找出其中和新数据最相似（最近邻）的k个数据，

算法取这k个数据中出现次数最多的标签作为新数据的类别。

通常k不大于20。

代码实现

假如现在又四个已知点， [ 1.0 , 1.1 ], [ 1.0 , 1.0 ], [ 0 , 0 ], [ 0 , 0.1 ]，类别标签分别是A、A、B、B

如果给定一个新的点[0, 0]，那么怎么判断它属于A还是B呢？

按照ＫＮＮ算法原理，需要执行以下操作：

计算训练集中各点与当前点之间的距离(本文采用最经典的欧式距离)

计算训练集中各点与当前点之间的距离(本文采用最经典的欧式距离)
按照距离递增次序对各点排序
选取与当前点距离最小的k个点
确定前k个点所在类别的出现频率
返回前k个点出现频率最高的类别，即为分类结果。

以下代码实现了ＫＮＮ算法的分类过程

    
    
    
# 创建训练数据集
     
     
     def creatDataSet():
     
     
      group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
     
     
      labels = ['A', 'A', 'B', 'B']
     
     
      return group, labels
     
     
      
     
     
     # ========================================
     
     
     # inX:输入待分类向量
     
     
     # dataSet：输入的训练样本集
     
     
     # labels:标签向量
     
     
     # k:用于选择最近邻居的数目
     
     
     # 分类器得出类别标签然后返回
     
     
     # =========================================
     
     
     def classify0 (inX, dataSet, labels, k):
     
     
      # shape返回表示行列数的元组，shape[0]获得行数
     
     
      dataSetSize = dataSet.shape[0]
     
     
      # 以inX为元素重复(dataSetSize, 1)次构成新的数组
     
     
      diffMat = tile(inX, (dataSetSize, 1))-dataSet
     
     
      sqDiffMat = diffMat**2
     
     
      # 矩阵行元素相加(如果axis = 0的话表示列相加)
     
     
      sqDistance = sqDiffMat.sum(axis = 1)
     
     
      distances = sqDistance**0.5
     
     
      # argsort()得到排序后原来位置的下标
     
     
      sortedDisIndicies = distances.argsort()
     
     
      classCount = {}
     
     
      for i in range(k):
     
     
      voteIlabel = labels[sortedDisIndicies[i]]
     
     
      classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
     
     
      
     
     
      sortedClassCount = sorted(classCount.iteritems(),
     
     
      # 构造函数key，获取对象的第1个域的值
     
     
      key = operator.itemgetter(1),
     
     
      # 升序排列
     
     
      reverse = True) 
     
     
      # 返回分类器得出类别标签
     
     
      return sortedClassCount[0][0]

如果把上面问题中的待测试点［０，　０］和训练集生成函数的返回值ｇｒｏｕｐ和ｌａｂｅｌｓ作为参数输入分类器，选择ｋ＝３

即：

     
     
     
 classify0 ([0, 0], group, labels, 3):

会得到其标签为Ｂ

这就完成了一个基于ＫＮＮ分类算法的简单分类器。

当然，在现实中的应用场景的复杂程度比这个例子大多了

秒客网

【1】KNN（K-nearest neighbors algorithm）

相关文章