K近邻算法-python代码实现

K-Nearest Neighbor

　　商业哲学家 Jim Rohn 说过一句话，“你，就是你最常接触的五个人的平均。”那么，在分析一个人时，我们不妨观察和他最亲密的几个人。同理的，在判定一个未知事物时，可以观察离它最近的几个样本，这就是 kNN（k最近邻）的方法[1]。

　　下面引自维基百科上的一幅图，这也是我们在学习KNN时最常见的一幅图。

　　在上图中显示，一共存在两种标签不同的数据，我们需要根据这些数据来判别一个新的数据（绿色点）属于哪一类，例如选择K=1，那么结果就是距离该点最近的点的分类，而k-近邻算法（K-Nearest Neighbor）要做的就是通过K值的选择、距离的度量、分类策略规则的定义来给出一个最好的预测结果。

K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最有的 K 值。
该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。
距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大（归一化处理）。

　　KNN的算法很简单，但实现起来还是需要有一定的python基础。之前老师说过，我们可以将整个算法用自己的方式画出流程图，根据流程图一步一步的来实现这个算法。参考《机器学习实战》这本入门级别书，学习KNN算法的python实现。

Other

K-近邻算法（适合于多分类问题）

k的选取：先选取一个较小的值，再根据交叉验证法来选取最优K值。参数k的取值一般通常不大于20
距离衡量：欧氏距离曼哈顿距离等
KNN缺陷：样本不平衡问题（怎么解决）
类别的判定：
投票决定：少数服从多数，近邻中哪个类别的点最多就分为该类。
加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）
优点：不需要参数估计，不需要事先训练
缺点：kNN不用事先训练，而是在输入待分类样本时才开始运行，这一特点导致kNN计算量特别大，而且训练样本必须存储在本地，内存开销也特别大。
KD树

加载基础的简单数据

from numpy import *
import operator as op
# 原始训练集
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

k-近邻算法的实现

def classify0(intX, dataSet, labels, k):
    # intX是测试的用例，dataset训练集，labels是训练集对应的标签，k是用于选择最近邻的数目
    dataSetSize = dataSet.shape[0]
    # 用欧式距离公式进行距离计算
    diffMat = tile(intX, (dataSetSize,1)) - dataSet   # numpy.tile进行数组的重复生成
    sqdiffMat = diffMat**2
    sqDistances = sqdiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()  # 返回的是数组值从小到大的索引值
    classCount = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=op.itemgetter(1), reverse=True)
    # python3中函数为：items(),python2中函数为：iteritems()
    return sortedClassCount[0][0]

　　新建一个test.py文件，进行测试,结果为B：

kNN.classify0([0, 0], group, labels, 3)

KNN的小例子——约会数据的判别

准备数据：从本文中解析数据

　　文本中前几条数据内容如下，分别代表这个人每年获得的飞行常客里程数，玩游戏所消耗时间百分比，每周消费的冰激凌公升数，和各自的标签，标签范围为1-3，标签数值越大，表示能让Helen接受约会的可能性越大。


40920	8.326976	0.953952	3
14488	7.153469	1.673904	2
26052	1.441871	0.805124	1

#  读取文件到矩阵
def file2matrix(filename):
    fr = open(filename)
    arrayOfLines = fr.readlines()
    numberOfLines = len(arrayOfLines)  # 得到文件行数
    returnMat = zeros((numberOfLines, 3))  # 定义一个全为0的矩阵
    classLabelVector = []
    index = 0
    for line in arrayOfLines:
        line = line.strip() # 截取掉所有回车符
        listFromLine = line.split('\t')  # 制表符
        returnMat[index, :] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector

准备数据：归一化数据

　　从文本数据可以看出，各个特征间的数据差值很大，所以需要归一化处理。

# 归一化数值
def autoNorm(dataSet):
    minvals = dataSet.min(0)
    maxvals = dataSet.max(0)
    ranges = maxvals - minvals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minvals, (m, 1))
	# tile()函数将变量内容复制成输入矩阵同样大小的矩阵
    normDataSet = normDataSet/tile(ranges, (m, 1))
    return normDataSet, ranges, minvals

分类器的测试代码

# 测试算法
def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix("D:\Learn and work\Code\Books\ML_code\Ch02\datingTestSet2.txt")
    normMat, ranges, minvals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m * hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
        if(classifierResult != datingLabels[i]):
            errorCount += 1.0
        print("the total error rate is: %f" % (errorCount/float(numTestVecs)))

约会网站预测函数

# 约会网站预测函数
def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input("percentage of time spent playing video games?"))
    ffMiles = float(input("frequent fliter miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix("D:\Learn and work\Code\Books\ML_code\Ch02\datingTestSet2.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr - minVals)/ranges, normMat, datingLabels, 3)
    print("You will probably like this person:", resultList[classifierResult - 1])

KNN的小例子—手写数字识别

准备数据：图像转化为测试向量

　　首先，观察一下图像的存储方式，如图：

　　每一个txt文件中，数字以如下方式进行展示。整个图像由32×32的矩阵构成。

　　我们接下来需要做的是将这个矩阵格式化成一个1×1024的向量。

def img2vector(filename): #将32×32的矩阵转换为1024的向量
    returnVector = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVector[0, 32*i+j] = int(lineStr[j])
    return returnVector

手写数字识别系统

def handwrittingClassTest():
    hwLabels = []
    trainingFileList = listdir("D:\\Learn and work\\Code\\Books\\ML_code\Ch02\digits\\trainingDigits")
    m = len(trainingFileList)  # 获取目录内容，给出长度
    trainingMat = zeros((m, 1024))
    for i in range(m):
		# 从文件名中解析分类数字
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i, :] = img2vector("D:\\Learn and work\\Code\\Books\\ML_code\Ch02\digits\\trainingDigits\\%s"
                                       % fileNameStr)
    testFileList = listdir("D:\\Learn and work\\Code\\Books\\ML_code\Ch02\digits\\testDigits")
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector("D:\\Learn and work\\Code\\Books\\ML_code\Ch02\digits\\testDigits\\%s"
                                     % fileNameStr)
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if(classifierResult != classNumStr):
            errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount / float(mTest)))

　　执行该函数，得到结果：

the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9
the classifier came back with: 9, the real answer is: 9

the total number of errors is: 10

the total error rate is: 0.010571

K近邻算法