学习自《机器学习实战》

任务

学习k-近邻分类算法
使用matplotlib创建扩散图
归一化数值

思想

采用测量不同特征值之间的距离的方法进行分类

优缺点

优点：精度高，对异常值不敏感，无数据输入假定
缺点：计算复杂度高，空间复杂度高

使用数据范围

数值型
标称型

工作原理（有监督学习算法）

存在带分类标签的训练集数据
输入没有标签的测试集数据，只选择训练集前k个（通常k为不大于20的整数）与测试集最相似的数据
选择这k个最相似数据中出现次数最多的分类标签，作为测试集数据的分类标签

实施kNN分类算法的步骤

计算已知类别数据集中的点与当前点之间的距离
按照距离递增（小到大）次序排序
选取与当前点距离最小的前k个点
确定前k个点所在类别的出现频率
返回前k个点出现频率最高的类别作为当前点的预测分类

实操

from numpy import *
import operator

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

def classify0(inX, dataSet, labels, k):
    """
    inX 用于分类的输入向量（元素数目与dataSet列数相同） 测试集数据
    dataSet 输入的训练集数据
    标签向量 labels
    k最近邻的数目
    """
    #距离计算（欧式距离）  
    ###将测试集inX按行广播成与训练集dataSetSize相同的行数，求差
    dataSetSize = dataSet.shape[0] 
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1) #求上述距离平方的和。axis=1,按列方向求元素和
    distances = sqDistances**0.5
    #排序
    sortedDistIndicies = distances.argsort()
    #选择距离最小的前k个点
    classCount={}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #计算每个标签出现的次数
    
    #将字典classCount分解为元组，利用operator.itemgetter方法对元组的第2个元素进行从大到小排序
    sortedClassCount = sorted(classCount.items(),
                             key=operator.itemgetter(1), reverse=True)
    
    return sortedClassCount[0][0]

运行：

PS D:\Data\File\ML> ipython
Python 3.6.5 |Anaconda, Inc.| (default, Mar 29 2018, 13:32:41) [MSC v.1900 64 bit (AMD64)]
Type 'copyright', 'credits' or 'license' for more information
IPython 7.8.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import kNN

In [2]: group, labels = kNN.createDataSet()

In [3]: group
Out[3]:
array([[1. , 1.1],
       [1. , 1. ],
       [0. , 0. ],
       [0. , 0.1]])

In [4]: labels
Out[4]: ['A', 'A', 'B', 'B']

In [5]: kNN.classify0([0,0], group, labels, 3)
Out[5]: 'B'

案例一：使用kNN改进约会网站的配对效果

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

1.2 分析数据：使用Matplotlib创建散点图

In [1]: import importlib

In [2]: importlib.reload(kNN)
Out[2]: <module 'kNN' from 'D:\\Data\\File\\ML\\kNN.py'>

In [2]: datingDataMat,datingLabels = kNN.file2matrix('datingTestSet2.txt')

In [3]:  datingDataMat
Out[3]:
array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01],
       [1.4488000e+04, 7.1534690e+00, 1.6739040e+00],
       [2.6052000e+04, 1.4418710e+00, 8.0512400e-01],
       ...,
       [2.6575000e+04, 1.0650102e+01, 8.6662700e-01],
       [4.8111000e+04, 9.1345280e+00, 7.2804500e-01],
       [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]])
In [5]: datingLabels[0:20]
Out[5]: [3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1, 1, 1, 1, 2, 3]

In [8]: import matplotlib

In [9]: import matplotlib.pyplot as plt

In [12]: fig  = plt.figure()

In [13]: ax = fig.add_subplot(111)

In [24]: ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 
                          15.0*array(datingLabels), 15.0*array(datingLabels))
Out[24]: <matplotlib.collections.PathCollection at 0x26983f8ec50>

1.3 数据归一化

#数据归一化
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)) #特征值相除（Numpy的“/”代表的是值相除，并非矩阵除法）
    return normDataSet, ranges, minVals

重新加载kNN.py模块，检查函数autoNorm执行结果：

In [36]: import importlib

In [37]: importlib.reload(kNN)
Out[37]: <module 'kNN' from 'D:\\Data\\File\\ML\\kNN.py'>

In [38]: normMat, ranges, minVals = kNN.autoNorm(datingDataMat)

In [39]: normMat
Out[39]:
array([[0.44832535, 0.39805139, 0.56233353],
       [0.15873259, 0.34195467, 0.98724416],
       [0.28542943, 0.06892523, 0.47449629],
       ...,
       [0.29115949, 0.50910294, 0.51079493],
       [0.52711097, 0.43665451, 0.4290048 ],
       [0.47940793, 0.3768091 , 0.78571804]])

In [40]: ranges
Out[40]: array([9.1273000e+04, 2.0919349e+01, 1.6943610e+00])

In [41]: minVals
Out[41]: array([0.      , 0.      , 0.001156])

1.4 测试算法：作为完整程序验证分类器

提供已有数据的90%作为训练集去训练分类器
其余10%数据去测试分类器，检查分类器的正确率（随机选择的）

编写计算错误率的函数：

def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('./datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]  #获取行数(样本数)
    numTestVecs = int(m*hoRatio) #计算测试集样本数
    
    errorCount = 0.0
    for i in range(numTestVecs): #去除前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
    
    print("The total error rate is: %f" % (errorCount/float(numTestVecs)))

运行：

In [52]: kNN.datingClassTest()
The classifier came back with: 3, the real answer is: 3
The classifier came back with: 2, the real answer is: 2
The classifier came back with: 1, the real answer is: 1
The classifier came back with: 3, the real answer is: 1
The total error rate is: 0.050000

错误率为5%

我们可以函数datingClassTest内的变量hoRatio和变量k的值，检查错误率的变化

依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。

1.5 使用算法：构建完整可用系统

程序给出用户对对方喜欢程度的预测值

def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input("percentage of time spent playing vedio games?"))
    ffMiles = float(input("frequent filer miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('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])

运行

In [57]: kNN.classifyPerson()
percentage of time spent playing vedio games?10
frequent filer miles earned per year?10000
liters of ice cream consumed per year?0.5
You will probably like this person:  in small doses

案例二：手写识别系统

在二进制存储的图片数据上使用kNN

识别手写字体0-9
需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小

宽高：32像素x32像素的黑白图像

2.1 收集数据

2.2 准备数据：将图像格式转换为分类器使用的向量格式

将一个32x32的二进制图像矩阵转换为1x1024的向量

##准备数据
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

运行：

In [59]: testVector = kNN.img2vector('./trainingDigits/0_13.txt')

In [60]: testVector[0, 32:63]
Out[60]:
array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 1.,
       1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.])

2.3 测试算法：使用k-邻近算法识别手写数字

需要加上

from os import listdir

2.4 测试算法

由于文件中的值已经在0和1之间，无需对其进行autoNorm()的归一化

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] #文件名
        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 error is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

运行：

In [52]: importlib.reload(kNN)
Out[52]: <module 'kNN' from 'D:\\Data\\File\\ML\\kNN.py'>

In [53]: kNN.datingClassTest()
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 error is: 10

the total error rate is: 0.010571

错误率为1.06%

改变变量k的值、修改函数handwritingClassTest随机选取训练样本、改变训练样本的数目，都会对kNN的错误率产生影响。

总结

k-邻近算法是分类数据最简单最有效的算法，是基于实例的学习，使用算法需要提供接近实际数据的训练样本数据

缺点

kNN必须保存全部数据集，如果训练数据集很大，必须使用大量的存储空间，又由于需要对每个数据集中的每个数据都计算距离值，实际使用时可能非常费时，执行效率并不高。

例如此处需要对每个测试向量做2000次距离计算，每个距离计算包括1024个维度的浮点运算，总共需要执行900次，需要为测试向量准备2MB的存储空间

kNN无法给出任何数据的基础结构信息，因此我们无法知晓平均实际样本和典型实例样本具有什么特征。

讨论

决策树是kNN的优化版，可以节省大量的计算开销
可以使用概率测量方法处理分类问题

【机器学习】有监督学习kNN（k-近邻法）