K近邻算法

KNN K近邻算法
（1）算法思路
计算待测样本与实际每一个样本之间的欧式距离（一般都是转换为向量，二位图像也是转化为一维向量）
选取距离最小的k个样本
统计K个样本的所属类别，出现频率最高的类别即为待测样本的类别

算法正确率影响参数， 测试集和样本数据的比重，以及K的选取

def classify0(inX,dataSet,labels,k):
    dataSetSize= dataSet.shape[0]  # type: object # shape[0]获取行 shape[1] 获取列
    diffMat=tile(inX,(dataSetSize,1))-dataSet #tile类似于matlab中的repmat，
    #1 计算欧式距离
    sqDiffMat=diffMat**2
    sqDistance=sqDiffMat.sum(axis=1)
    distance=sqDistance**0.5
    sortedDistance=distance.argsort()#增序排序
    classCount={}
    for i in range(k):
        #获取类别
        voteIlabel=labels[sortedDistance[i]]
        # 字典的get方法，查找classCount中是否包含voteIlabel，是则返回该值，不是则返回defValue，这里是0
        # 其实这也就是计算K临近点中出现的类别的频率，以次数体现
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
        # 对字典中的类别出现次数进行排序，classCount中存储的事 key-value，其中key就是label，value就是出现的次数
        # 所以key=operator.itemgetter(1)选中的事value，也就是对次数进行排序
    sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    # sortedClassCount[0][0]也就是排序后的次数最大的那个label
    return sortedClassCount[0][0]

（2）算法应用实例
数值型、标称型。
海伦约会数据预测
可以用来对手写的数字进行分类，但是对于图像运算量太大
（3）算法优缺点
缺点：基于实例的学习，必须保存全部数据集，占用存储空间大
非常耗时：因为必须对数据集中的每一个数据，计算距离。
无法给出任何数据的基础结构信息，无法知晓平均实例样本和典型实例样本具有的什么特征
优点：精度高，对异常值不敏感