《机器学习实战》 第二章【k-近邻算法】

作为本书的第一个算法，k-近邻算法简单易懂，在分类任务中起到很重要的作用

---

算法描述

算法简述

简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。即如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

• Step1.计算已知类别数据集中的点与当前点之间的距离
  这里采用欧式距离进行计算，例如向量点xA和xB之间的距离：
  
  例如（0，3，5）和（1，2，7）的距离为：
  
• Step2.按照距离递增次序排序
• Step3.选取与当前点距离最小的k个点
• Step4.确定前k个点所在类别的出现的频率
• Step5.返回前k个点中出现频率最高的类别作为当前点的预测分类

优缺点

• 优点：精度高、对异常值不敏感、无数据输入假定
• 缺点：计算复杂度高、空间复杂度高
• 适用数据范围：数值型和标称型

一般流程

• 收集数据：任何方法
• 准备数据：距离计算所需要的数值，最好是结构化的数据格式
• 分析数据：任何方法
• 训练算法：不适用于k-近邻算法
• 测试算法：计算错误率
• 使用算法：首先需要输入样本数据和结构化输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理

实例0.一个简单的例子

from numpy import *

#classify0
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0] #得到数据集长度
    diffMat = tile(inX, (dataSetSize,1)) - dataSet #把inX在行上重复dataSize次，在列上重复1次，方便进行差运算
    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 #类似map结构存储
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    #print(sortedClassCount)
    #[('B', 2), ('A', 1)]
    return sortedClassCount[0][0]
    
#创建数据集
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

group,labels=createDataSet()
print(classify0([0,0],group,labels,3))

结果

实例1.约会网站配对

#将文本记录转换为Numpy的解析程序
from numpy import *
import operator
from os import listdir
import matplotlib.pyplot as plt
def file2matrix(filename):
    fr = open(filename)
    arrayOLines=fr.readlines()
    numberOfLines = len(arrayOLines)         #得到文本行数
    returnMat = zeros((numberOfLines,3))        #返回矩阵，行数x3
    #print(numberOfLines)
    #1000
    classLabelVector = []                       #labels
    index = 0
    for line in arrayOLines:
        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))
    normDataSet = normDataSet/tile(ranges, (m,1))    #减去最小值后除以max-min的值
    return normDataSet, ranges, minVals
   
def datingClassTest():
    hoRatio = 0.10      #选用10%的数据用于测试
    datingDataMat,datingLabels = file2matrix('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))
    print errorCount
#datingMat,datinglabels=file2matrix('datingTestSet2.txt')
# fig=plt.figure()
# ax=fig.add_subplot(111)
# ax.scatter(datingMat[:,1],datingMat[:,2],15.0*array(datinglabels),15.0*array(datinglabels))#带有样本标签的约会数据散点图
# plt.show()
datingClassTest()

结果：10%的数据，错了5个，错误率5%

实例2.手写数字识别

from numpy import *

def img2vector(filename):
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #去掉“.txt”
        classNumStr = int(fileStr.split('_')[0])#分开_
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('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('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))
    
handwritingClassTest()

结果：