K-近邻算法

机器学习的一般步骤：

image.png

概述

• 主要思想：采用测量不同特征值之间的距离方法进行分类
  • 优点：精度高、对异常值不敏感、无数据输入假定
  • 缺点：计算复杂度搞，空间复杂度高
  • 适用范围：数值型和标称型
    • 标称型：一般在有限的数据中取，而且只存在‘是’和‘否’两种不同的结果（一般用于分类）
    • 数值型：可以在无限的数据中取，而且数值比较具体化，例如4.02,6.23这种值（一般用于回归分析）
• KNN算法工作原理：存在一个带有标签的训练样本集，输入没有比起前的新数据，将新数据的每个特征值与样本集中数据 对应的特征进行比较，然后算法提取样本集中最相似数据的分类标签。选择K个最相似数据中出现次数最多的分类，作为新数据的分类
• 导入数据

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

• 实现KNN算法

算法思想：
1.计算Dataset中的数据距离（使用欧式距离）
2.按照距离升序排列
3.选取距离最小的K个点
4.确定和返回K点钟频率最高的类别
# inX用于分类的输入向量
# dataset输入训练样本集
# labels标签向量
# k是要选取的点数
# 注意在python2下使用的是iteritems()，在Python3下使用的是items()
def classify0(inX, dataSet, labels, k):
    # 计算距离
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    # 排序：按从小到大
    sortedDistIndicies = distances.argsort()
    classCount={}
    for i in range(k):
        voyteIlabel = labels[sortedDistIndicies[i]]
        classCount[voyteIlabel] = classCount.get(voyteIlabel,0) + 1
    #找出得票最高的类别
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),reverse=True)
    return  sortedClassCount[0][0]

参考书籍：机器学习实战 Perer Harrington