首页 > 代码库 > 分类算法——K-邻近

分类算法——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)由于需要计算特征的距离,所以需要特征进行量化和标准化。


本文出自 “走一停二回头看三” 博客,请务必保留此出处http://janwool.blog.51cto.com/5694960/1895064

分类算法——K-邻近