分类算法——K-邻近

   K-邻近分类方法通过计算待分类目标和训练样例之间的距离，选取与待分类目标距离最近的K个训练样例，根据K个选取样例中占多数的类别来确定待分类样例。距离类型有很多，大致有欧式距离，曼哈顿距离，切比雪夫距离，闽科夫斯基距离，标准化欧式距离，马氏距离，夹角余弦，汉明距离，相关系数，信息熵等。 

  KNN算法的具体步骤：

1、计算待分类目标与每个训练样例之间的距离dist；

2、对dist进行排序，选择前K个训练样例作为K-最邻近样例；

3、统计K个训练样例中每个类别出现的频次；

4、选择出现频次最大的类别作为待分类目标的类别。

  依据上述流程，给出实现代码：

from numpy import * import operator def knn(x,transet,labels,k,type = 0):     '''     k-近邻算法     :param x:待分类特征     :param transet: 已知特征     :param labels: 特征标签     :param k:     :param type:         距离类型：0：欧式，1：曼哈顿，2：切比雪夫，3：闽科夫斯基，4：标准化欧式，5：马氏，6：夹角余弦                   7：汉明距离，8：杰卡德，9：相关系数，11:信息熵     :return:     '''     distances = zeros_like(labels)     if type == 0:         tranSize = shape(transet)         diffMat = tile(x,(tranSize[0],1)) - transet         distances = ((diffMat**2).sum(axis=1))**0.5     #TODO：根据不同的类型计算距离     sortedIndex = distances.argsort()     classCount = {}     for i in labels[sortedIndex[:k]]:         classCount[i] = classCount.get(i,0) + 1     sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)     return sortedClassCount;

  KNN算法的优点：理论简单，实现简单。

  KNN算法的缺点：1）对K值的选取依赖大，不同的K值选取可能产生不同的结果。可以通过实验选取分类误差最小的K值。2）由于需要计算特征的距离，所以需要特征进行量化和标准化。