[机器学习实战]k近邻算法

从一个最基本的算法示例来入门机器学习

第一个分类算法 --- k-近邻算法（简单地说，k近邻算法采用测量不同特征值之间的距离方法进行分类。）

---

前言：

• 工具, 我用的 Pycharm ，Python V3.X和V2.x 随意切换，建议初学者还是下个编辑工具方便些. Pycharm环境配置
• 本篇基于 Python 2.X 环境,Mac OS 系统
• 模块导入 numpy,operator,matplotlib，不知道从哪导入?
• 这里用的比较的多的NumPy数组，建议先简单了解下，NumPy使用手册
• 建议第一遍先过一下算法大概的思想，之后再细看代码
• 源码在这里

---

需求分析,使用k-近邻算法改进约会网站的配对效果

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

• 不喜欢的人
• 魅力一般的人
• 极具魅力的人

这次的分类软件可以更好地帮助她将匹配对象划分到确切的分类中

---

k-近邻算法流程

1. 收集数据:提供文本文件
2. 准备数据: 使用 Python 解析文本文件
3. 分析数据:使用 Matplotlib 画二维扩散图
4. 训练算法:此步驟不适用于卜近邻算法
5. 使用海伦提供的部分数据作为测试样本,测试样本和非测试样本的区别在于:测试样本是已经完成分类的数据，如果预测分类与实际类别不同，则标记为一个错误
6. 使用算法:产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否
   为自己喜欢的类型

准备数据:从文本文件中解析数据

本次数据来源海伦的约会数据，放在文本文件 datingTestSet2.txt 中，每 个样本数据占据一行，总共有1000行。样本主要包含以下3种特征：

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰淇淋公升数

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

def file2matrix(filename):
    love_dictionary = {'非常喜欢': 3, '一般喜欢': 2, '讨厌': 1}
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)  # get the number of lines in the file
    returnMat = zeros((numberOfLines, 3))  # prepare matrix to return
    classLabelVector = []  # prepare labels return
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        if (listFromLine[-1].isdigit()):
            classLabelVector.append(int(listFromLine[-1]))
        else:
            classLabelVector.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector

首先我们需要知道文本文件包含多 少行。打开文件，得到文件的行数。然后创建以零填充的矩阵NumPy(实际上，NumPy是一 个二维数组，这里暂时不用考虑其用途)。为了简化处理，我们将该矩阵的另一维度设置为固定 值3 , 你可以按照自己的实际需求增加相应的代码以适应变化的输人值。循环处理文件中的每行 数据 , 首先使用函数line.strip()截取掉所有的回车字符，然后使用tab字符\t将上一步得 到的整行数据分割成一个元素列表。接着，我们选取前3个元素，将它们存储到特征矩阵中。Python 语言可以使用索引值-1表示列表中的最后一列元素，利用这种负索引，我们可以很方便地将列表 的最后一列存储到向量classLabelVector中。需要注意的是，我们必须明确地通知解释器，告 诉它列表中存储的元素值为整型，否则Python语言会将这些元素当作字符串处理。以前我们必须自己处理这些变量值类型问题.

测试一下，读出来的数据是这样

屏幕快照 2017-10-09 下午3.46.43.png

散点图，观察数据的样本分布

只是为了能比较直观的看到样本之间的模式，不在算法内

一般来说，图形化的方式能更直观地展示数据。接下来下面用 Matplotlib 来图形化展示数据内容，看一下数据之间的模式,测试代码。

def matplotTest():
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
    plt.show()

图二.png

这是玩视频游戏所耗时间百分比(X)与每周消费的冰激凌公升数的散点图(Y),可以看到三个样本的分布情况，不过区分度不是很清晰

接下来取矩阵列的0和1列

datingDataMat[:,0],datingDataMat[:,1]

图三.png

这是每年飞行常客里程数(X)与玩视频游戏所占百分比的约会数据散点图(Y)

清晰地标识了三个不同的样本分类区域，具有不同爱好的人其类别区域也不同。

准备数据:归一化数值

计算俩点间的距离公式

图四.png

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

在处理这种不同取值范围的特征值时，我们通常采用的方法是将数值归一化，如将取值范围 处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值:

newValue = {oldValue-min)/(max-min)

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

为了归一化特征值，我们必须使用当前值减去最小值，然后除以取值范围. 需要注意的是，特征 值矩阵有1000 * 3个值，而minVals和range的值都为1 * 3。为了解决这个冋题，我们使用NumPY函数将变量内容复制成输入矩阵同样大小的矩阵，注意这是具体特征值相除 ，而 对于某些数值处理软件包，/可能意味着矩阵除法，但在NumPy库中，矩阵除法需要使用函数 linalg .solve (matA,matB) 。

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))  # element wise divide
    return normDataSet, ranges, minVals
    
#将每列的最小值放在变量minVals中，将最大值放在变量 maxVals中,其中dataSet.min(0)中的参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值。然后，函数计算可能的取值范围，并创建新的返回矩阵    

这里可以打印出归一之后的结果,测试代码

def solveTest():
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    print autoNorm(datingDataMat)

输出

图五.png

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

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

使用错误率来检测分类器的性能。对于分类器来说，错误率就是分类 器给出错误结果的次数除以测试数据的总数，完美分类器的错误率为0，而错误率为1.0的分类器 不会给出任何正确的分类结果。代码里我们定义一个计数器变量，每次分类器错误地分类数据， 计数器就加1, 程序执行完成之后计数器的结果除以数据点总数即是错误率

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): #表示提取前k个值
        voteIlabel = labels[sortedDistIndicies[i]] #排在第i位置的类别
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1 #对 classCount[voteIlabel] 的值进行加一，如果不存在则初始化为1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) #出现频次列表classCount 进行倒序排序
    return sortedClassCount[0][0]
#分类器

classify0分类算法流程,对未知类别属性的数据集中的每个点依次执行以下操作:
(1)计算已知类别数据集中的点与当前点之间的距离;
(2)按照距离递增次序排序;
(3)选取与当前点距离最小k几个点;
(4)确定前k个点所在类别的出现频率;
(5)返回前k个点出现频率最高的类别作为当前点的预测分类。

def datingClassTest():
    hoRatio = 0.50  # hold out 10%
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')  # load data setfrom file
    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

从文件中读取数据并将其转换为归一化特征值。接着计算测试向量的数量，此步决定了 normMat向量中哪些数据用于测试，哪些数据用于分类器的训练样本;然后将这两部分数据输人到原始kNN分类器函数classifyO。最后，函数计算错误率并输出结果

调用测试函数 datingClassTest(),输出

图六.png

可以看到，约会数据集的错误率5%，还算是一个可以接受的结果,可以改变函数 datingClassTest内变量 hoRatio 和变量 k 的值，检测错误率是否随着变量值的变化而增加。依 赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同

这个例子表明我们可以正确地预测分类，错误率是5%。海伦完全可以输人未知对象的 属性信息’由分类软件来帮助她判定某一对象的可交往程度:讨厌、一般喜欢、非常喜欢。

使用算法:构建完整可用系统

现在可以做出一个小程序,通过该程序海伦会在约会网站上找到某个人并输入他的信息。 程序会给出她对对方喜欢程度的预测值

def classifyPerson():
    resultList = ['讨厌', '一般喜欢', '非常喜欢']
    percentTats = float(raw_input( \
        "percentage of time spent playing video games?"))
    ffMiles = float(raw_input("frequent flier miles earned per year?"))
    iceCream = float(raw_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: %s" % resultList[classifierResult - 1]

测试下，运行函数,依次输入

玩视频游戏的百分比?  12
每年的飞行公里数  30354
每周消费的冰淇淋公升数  2

然后可以得到 你对他的喜欢程度 非常喜欢 的结论

---

到此为止，算是初步摸到了机器学习的门槛,后续会有包括决策树，朴素贝叶斯等进阶算法的学习总结篇,共同进步.

WechatIMG1.jpeg