[人工智能] 机器学习——K-近邻算法实例实战

????????我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的
人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：

????????尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会那些魅力一般的人，而周末更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。此外海伦还收集了一些约会网站未曾记录的数据信息，她认为这些数据更有助于匹配对象的归类。

1.2 流程步骤

(1) 收集数据：提供文本文件。
(2) 准备数据：使用Python解析文本文件。
(3) 分析数据：使用Matplotlib画二维扩散图。
(4) 训练算法：此步驟不适用于k近邻算法。
(5) 测试算法：使用海伦提供的部分数据作为测试样本。

? ? ?测试样本和非测试样本的区别：测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误。
(6) 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型。

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

????????约会数据收集存放在文本文件datingTestSet2.txt中，每个样本数据占据一行，总共有1000行。样本主要包含以下3中特征：

????????在将上述特征数据输入到分类器之前，必须将待处理数据的格式改变为分类器可以接受的格式。在kNN.py中创建名为fileMatrix的函数，以此来处理输入格式问题。该函数的输入为文件名字符串，输出为训练样本矩阵和类标签向量。

def fileMatrix(filename):
    file = open(filename)
    arrayOLines = file.readlines()
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines, 3))
    classLabelVector = []
    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

①readlines()：用于读取文件中的一行，包含最后的换行符“\n”。方法读取整个文件所有行，保存在一个列表(list)变量中，每行作为一个元素，但读取大文件会比较占内存。

②readline()：用于读取文件中的所有行，它和调用不指定 size 参数的 read() 函数类似，该方法每次读出一行内容，所以，读取时占用内存小，比较适合大文件，该方法返回一个字符串对象。

③read()：从文件当前位置起读取size个字节，若无参数size，则表示读取至文件结束为止，它范围为字符串对象

④zeros()：返回给定形状和类型的新数组，用0填充；zeros((2,3))，返回两行三列值为0的数组。

⑤strip()：方法用于移除字符串头尾指定的字符（默认为空格或换行符）或字符序列。该方法只能删除开头或是结尾的字符，不能删除中间部分的字符。

⑥split()?：通过指定分隔符对字符串进行切片，返回分割后的字符串列表。

⑦数组切片：逗号“,”分隔各个维度，“:”表示各个维度内的切片，只有:表示取这个维度的全部值。

1.4?分析数据：用Matplotlib创建散点图

????????Matplotlib 是 Python 的绘图库，类似 MATLAB 的绘图工具。它可与 NumPy 一起使用，提供了一种有效的 MatLab 开源替代方案，它也可以和图形工具包一起使用。

def showdatas(datingDatMat, datingLabels, numScatter, xylabel):
    fig = plt.figure()
    font = {'family': 'MicroSoft YaHei'}
    matplotlib.rc("font", **font)
    ax = fig.add_subplot(111)
    ax.scatter(datingDatMat[:, numScatter[0]], datingDatMat[:, numScatter[1]], 15.0 * array(datingLabels), 15.0 * array(datingLabels))
    ax.set_xlabel(xylabel[1])
    ax.set_ylabel(xylabel[2])
    plt.title(xylabel[0])
    plt.show()

datingDatMat, datingLabels = fileMatrix('datingTestSet2.txt')
numScatter = array([[0, 1], [0, 2], [1, 2]])
xylabel = array([['每年获得飞行常客里程数与玩视频游戏所消耗占比', '每年获得的飞行常客里程数', '玩视频游戏所消耗时间占'],
                 ['每年获得飞行常客里程数与每周消费的冰激淋公升数', '每年获得的飞行常客里程数', '每周消费的冰激淋公升数'],
                 ['玩视频游戏所消耗时间占比与每周消费的冰激淋公升数', '玩视频游戏所消耗时间占比','每周消费的冰激淋公升数']])
showdatas(datingDatMat, datingLabels, numScatter[0], xylabel[0])
showdatas(datingDatMat, datingLabels, numScatter[1], xylabel[1])
showdatas(datingDatMat, datingLabels, numScatter[2], xylabel[2])

操作过程中遇到的问题是，散点图的标题及横纵坐标中文显示不出来，应该是散点图默认字体不支持显示中文，所以解决办法是自己设置字体MicroSoft YaHei微软雅黑。

1.5?准备数据：数据归一化

?若计算样本1和样本4之间的距离，按照K-近邻算法的工作原理使用如下面的公式：

????????容易发现，上面方程中数字差值最大的属性对计算结果的影响最大，也就是说，每年获得的飞行常客里程数对于计算结果的影响将远远大于其他两个特征：玩视频游戏所耗时间百分比和每周消费的冰淇淋公斤数的影响。而差生这种现象的唯一原因，仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的，因此作为三个等权重的特征之前，飞行常客里程数并不应该如此严重地影响到计算结果。

????????在处理这种不同取值范围的特征值时，我们通常采用的方法是将数据归一化，如将取值范围处理为0到1或者-1到1之间。这样的再次使用公式计算起来的话，就不会存在个别数值的差非常大的情况。我们可以使用下面的公式将任意取值范围的特征值转化为0到1区间内的值：

????????其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂程度，但为了得到准确结果，我们必须这样做。编写一个autoNorm函数，该函数会自动的将数字特征值转化为0到1的区间。

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)) #特征值相除
    return normDataSet, ranges, minVals

datingDatMat, datingLabels = fileMatrix('datingTestSet2.txt')
normData, ranges, minVals = autoNorm(datingDatMat)
print('normData')
print(normData)
print('ranges')
print(ranges)
print('minVals')
print(minVals)

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

????????机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。10%数据应该是随机选择的。

def datingClassTest():
    hoRatio = 0.1    #10%的测试数据
    datingDatMat, datingLabels = fileMatrix('datingTestSet2.txt')  #从文件读数据
    normMat, ranges, minVals = autoNorm(datingDatMat)              #数据的归一化
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)                                   #测试数据数量
    errorCount = 0.0                                               #错误数量统计
    for i in range(numTestVecs):
        classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
        print("分类器返回的结果是：%d，真实结果是：%d"%(classifierResult, datingLabels[i]))
        if(classifierResult != datingLabels[i]):
            errorCount += 1.0
    print('分类器处理约会数据集的错误率是：%f'%(errorCount/float(numTestVecs)))

我们可以从中看到，在1000条数据中将前100条数据分别使用分类器去进行分类，然后与数据的真实类别进行比较，分类器处理约会数据的错误率为：0.05，即错误率是5%，正确率就是95%，已经能够满足要求了。

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

? ? ? ? 以上的步骤，我们已经在数据上对分类器进行了测试，现在终于可用使用这个分类器为海伦来对人们分类了。通过构建完整可用系统，给出完整的程序，海伦会在约会网站上找到某个人并输入他的信息，程序会给出她对对方喜欢程度的预测值。

def classifyPerson():
    resultList = ['不喜欢的人', '魅力一般的人', '极具魅力的人']
    precentTats = float(input('玩视频游戏所耗时间百分比：'))           #用户输入三个特征
    ffMiles = float(input('每年获得的飞行常客里程数：')) 
    iceCream = float(input('每周消费的冰淇淋公升数：'))
    datingDatMat, datingLabels = fileMatrix('datingTestSet2.txt')    #文件数据读入
    normMat, ranges, minVals = autoNorm(datingDatMat)               
    inArr = array([precentTats, ffMiles, iceCream])                  #生成测试集                
    norminArr = (inArr-minVals)/ranges                               #数据归一化
    classifierResult = classify(norminArr, normMat, datingLabels, 5) #分类器分类
    print('这个人可能是你%'%(resultList[classifierResult-1]))

1.8 实例一：实验总结

? ? ? ? 在使用K-近邻算法改进约会网站的配对效果的实例中，我体会到了KNN算法的思想，同时也感觉到了python语言的简便性和强大性，比如对于KNN算法的核心部分代码，计算距离远近，数组dataSet训练样本集可以兼容计算任意维度距离，因为前一次博客简单实现KNN算法，只用了简单的分类电影类型例子，只有两个特征值，即用二维数组计算就好，而约会网站的配对有三个特征值，距离值是三个维度的，还担心之前写的KNN算法不能用，但是经过仔细研究思考后发现，因为python语言的强大性，array()函数，可以创建二维数组，即利用数学矩阵知识，就可以解决问题。

实例二：手写识别系统

2.1 实例分析

????????使用K-近邻分类器的手写识别系统。简单起见，这里构造的系统只能识别数字0到9。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素x32像素的黑白图像。当前使用文本格式存储图像，即使不能有效的利用空间，但是为了方便理解，还是将图像转换成文本格式。

2.2 流程步骤

（2）处理数据：编写imgVector()函数，将图像格式转换成分类器使用的向量格式。

（3）分析数据：在Python命令提示符中检查数据，确保它符合要求。

（5）测试算法：编写函数使用提供的部分数据集作为测试样本，对学习算法进行测试。

2.3 准备数据：将图像转换为测试向量

????????目录trainingDigits中包含了大约2000个例子，每个数字大约有200个样本；测试文件testDigits中包含了大约900个测试数据。两组数据没有重叠。使用trainingDigits中的数据训练分类器，使用testDigits的数据测试分类器效果。为了使用kNN算法分类器必须将一个32x32的二进制矩阵转换为1x1024的向量，以便我们使用分类器处理数字图像信息。

#定义imgVector()函数，将32*32的二进制矩阵转换成1*1024的矩阵并返回
def imgVector(filename):
    returnVect = zeros((1, 1024))
    file = open(filename)
    for i in range(32):
        lineStr = file.readline()
        for j in range(32):
            returnVect[0, 32*i+j] = int(lineStr[j])
    return returnVect

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

????????现在这一步，需要构造handWriteClassTest( )函数进行分类器测试。为了处理大量的文本文件我们需要from os import listdir用于列出指定目录的文件名，读取多个数字文本文件。

#K-近邻算法
def classify(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):
        voteILabel = labels[sortedDistIndicies[i]]
        classCount[voteILabel] = classCount.get(voteILabel, 0) + 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

# 手写识别系统测试代码
def handWriteClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')   #获取trainingDigits文件子目录的列表
    m = len(trainingFileList)                      #获得训练样本集总数
    trainingMat = zeros((m, 1024))                 #初始化训练样本集
    for i in range(m):                             #循环将trainingDigits目录下的训练样本集的文本文件放入矩阵traningMat中，真实值放入hwLabels中
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]        #将获得的字符串按分隔符'.'分隔并取第一个字符串即去掉拓展名的文件名
        classNumStr = int(fileStr.split('_')[0])   #获取训练样本集的真实值，非numpy数据需要指定数据类型int
        hwLabels.append(classNumStr)               #将得到的单个真实值按加入到真实值列表hwLabels中
        trainingMat[i, :] = imgVector('trainingDigits/%s' % fileNameStr) #把32行*32列的二进制文本文件转换成1行*1024列矩阵并按行存储到训练数据总矩阵中
    testFileList = listdir('testDigits')           #获取testDigits文件子目录的列表
    errorCount = 0.0                               #预测错误计数器
    mTest = len(testFileList)                      #测试样本集总量
    for i in range(mTest):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = imgVector('trainingDigits/%s' % fileNameStr)
        classifierResult = classify(vectorUnderTest, trainingMat, hwLabels, 3) #用K-近邻算法对测试样本集分类
        print("分类器得到得预测值为：%d ,真实值为：%d " % (classifierResult, classNumStr))
        if(classifierResult != classNumStr):        #判断预测是否正确，如果错误预测，则errorCount加1
            errorCount += 1.0
    print("测试总数：%d，预测错误总数：%d，错误率为：%f" % (mTest, errorCount, errorCount/float(mTest)))

2.5 实例二：实验总结

? ? ? ? ?上面的实例二实验中，可以知道当K = 3时，使用K-近邻算法识别手写数据集的错误率大约为百分之一。但是从运行效果看，实际使用这个算法的时候，算法的执行效率并不高。我们需要进行2000次距离计算，每个距离计算包括了1024个维度的浮点数，总计执行900次，此外，我们还要为测试向量准备很大的存储空间。

? ? ? ? 我觉得中手写数字识别的系统可以做的更好一点，比如做出一个程序界面，给窗口在画板上手写数字，然后程序能够识别出手写数字，后期继续吧自己的想法实现！