K-近邻算法实战——改进约会网站的配对效果

我的朋友海伦直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不限人选，但她并不是喜欢每一个人。经过番总结，她发现曾交往过三种类型的人:

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

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

示例:在约会网站上使用k-近邻算法

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

注：本文将不会对K-近邻算法的具体实现进行详解，如有需要请点击按钮查看：

K-近邻算法详解

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

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingTestSet2.csv中，每个样本数据占据一行， 总共有1000行。海伦的样本主要包含以下3种特征：

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

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

将下面的代码增加到kNN.py中。

def file2matrix(filename="datingTestSet2.csv"):
    dating = pd.read_csv(filename)
    returnMat = dating.iloc[:, :3].values
    classLableVector = dating.iloc[:, -1].values
    return returnMat, classLableVector

从上面的代码可以看到，Python处理文本文件非常容易。首先我们需要知道文本文件包含多少行。打开文件，得到文件的行数。然后创建以零填充的矩阵NumPy(实际上，NumPy是一个二维数组，这里暂时不用考虑其用途)。为了简化处理，我们将该矩阵的另-维度设置为固定值3，你可以按照自己的实际需求增加相应的代码以适应变化的输入值。我们选取前3个元素，将它们存储到特征矩阵中。Python语言可以使用索引值-1表示列表中的最后一列元素，利用这种负索引，我们可以很方便地将列表的最后一列存储到向量classLabelvector中。 需要注意的是，我们必须明确地通知解释器，告诉它列表中存储的元素值为整型，否则Python语言会将这些元素当作字符串处理。以前我们必须自己处理这些变量值类型问题，现在这些细节问题完全可以交给NumPy函数库来处理。

在PyCharm下输人下面代码:

datingDataMat, datingLabels = kNN.file2matrix('datingTestSet2.csv')
print(returnMat)
print(classLableVector)

使用函数file2matrix读取文件数据，必须确保文件datingTestSet.txt存储在我们的工作目录中。此外在执行这个函数之前，我们重新加载了kNN.py模块，以确保更新的内容可以生效，否则Python将继续使用上次加载的kNN模块。

成功导人datingTestSet.txt文件中的数据之后，可以简单检查一下数据内容。Python的输出结果大致如下:

准备数据:归一化数值

下表给出了提取的四组数据，如果想要计算样本3和样本4之间的距离，

可以使用下面的方法:

√(0-67) ^2+(20000-32000)^2 +(1.1-0.1)^2

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

约会网站原始数据改进之后的样本数据

	玩视频游戏所耗时间百分比	每年获得的飞行常客里程数	每周消费的冰淇淋公升数	样本分类
1	0.8	400	0.5	1
2	12	13400	0.9	3
3	0	20000	1.1	2
4	67	32000	0.1	2

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

newValue = (oldvalue-min) / (max - min)

其中min和max分别是数据集中的最小特征值和最大特征值。虽然改变数值取值范围增加了分类器的复杂度，但为了得到准确结果，我们必须这样做。我们需要在文件kNN.py中增加一个新函数autoNorm()，该函数可以自动将数字特征值转化为0到]的区间。

def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = (dataSet-minVals)/ranges
    return normDataSet, ranges, minVals

在函数autoNorm()中，我们将每列的最小值放在变量minVals中，将最大值放在变量maxVals中，其中dataSet . min(0)中的参数0使得函数可以从列中选取最小值，而不是选取当前行的最小值。然后，函数计算可能的取值范围，并创建新的返回矩阵。正如前面给出的公式，为了归一化特征值，我们必须使用当前值减去最小值，然后除以取值范围。

在PyCharm下输人下面代码:

returnMat, classLableVector=file2matrix()
normDataSet, ranges, minVals=autoNorm(returnMat)
print(normDataSet)
print(ranges)
print(minVals)

Python的输出结果大致如下:

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

上面我们已经将数据按照需求做了处理，本节我们将测试分类器的效果，如果分类器的正确率满足要求，海伦就可以使用这个软件来处理约会网站提供的约会名单了。机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的85%作为训练样本来训练分类器，而使用其余的15%数据去测试分类器，检测分类器的正确率。本书后续章节还会介绍一些高级方法完成同样的任务，这里我们还是采用最原始的做法。需要注意的是，15%的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定目的来排序，所以我们可以随意选择15%数据而不影响其随机性。

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

为了测试分类器效果，在kNN.py文件中创建函数datingClassTest,该函数是自包含的，你可以在任何时候在thn运行环境中使用该函数测试分类器效果。在kNN.Py文件中输人下面的程序代码。

def datingClassTest(HoRatio=0.15, filename="datingTestSet2.csv", k=5):
    datingDataMat, datingLabels = file2matrix(filename)
    normMat, range, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*HoRatio)
    errorCount = 0.0
    for i in ny.arange(numTestVecs):
        classifierResult = classify0(normMat[i, :],
            normMat[numTestVecs:m, :],datingLabels[numTestVecs:m], k)
        print("分类器为：%d，真实值为：%d" 
            % (classifierResult, datingLabels[i]))
        if classifierResult != datingLabels[i]:
            errorCount += 1.0
    print("总的错误率为：%f" % (errorCount/float(numTestVecs)))

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

在PyCharm下输人下面代码:

datingClassTest()

Python的输出结果大致如下:

分类器处理约会数据集的错误率是5.3%，这是一个相当不错的结果。我们可以改变函数datingClassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值的变化而增加。依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。

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

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

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

def classifyPerson():
    resultList = ['不感兴趣', '有点喜欢', '非常喜欢']
    percentTats = float(input("您花在玩电子游戏上的时间百分比?"))
    ffMiles = float(input("您每年飞行的里程数为多少？"))
    iceCream = float(input("您每年消耗多冰淇淋的公升数为多少？"))
    datingDataMat, datingLabels = file2matrix()
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = ny.array([ffMiles, percentTats, iceCream])
    classifierResult = classify0((inArr-minVals) / ranges,
        normMat, datingLabels, 5)
    print("您是否可能会喜欢这个人：", resultList[classifierResult - 1])

在PyCharm下输人下面代码:

classifyPerson()

Python的输出结果大致如下:

写在最后

到目前为止，我们已经能够达到改进约会网站的配对效果了，而且误差率也是可以接受的。整个程序到现在为止已经算大功告成了。我们已经看到如何在数据上构建分类器，这也是K-近邻算法的核心。