4.1 读文件，解析特征向量和类别标签
• 4.2 特征标准化
• 4.3 画散点图，观察特征
• 4.4 利用k-NN算法进行分类
• 4.5 验证算法

一. k-NN简介

k-NN，即k-nearest neighbors algorithm ，是一种非常简单且应用广泛的机器学习算法，属于监督学习大家庭中的一员，多用于分类问题，也可以用于回归问题，本文主要讲述分类问题。虽然k-NN简单，但应用很广泛，且常被用作更复杂分类器的测试基准，对k-NN应用的研究有很多，例如：

1. 遗传学 — Gene function prediction
2. 农业 — Tree density estimation
3. 航空— Air traffic flow prediction
4. 安全 — Detection of distress in mood

二. k-NN原理

分类问题中，训练集（training set）中的每个样本已知类别，而测试集（test set）中的样本未知类别，分类问题的目标是对测试集中每个样本标记类别标签（label）。k-NN(k-nearest neighbors algorithm)，即对每一个测试集样本\\(x\\)，在训练集中选取\\(k\\)个最近的“邻居”，由这些“邻居”的大多数来决定\\(x\\)所属的类别标签，如下图所示：

绿圆应该标记成红三角还是蓝方块？well, it depends !
计算绿圆和所有红三角、蓝方块的距离；
当\\(K=3\\)时（实心圆圈），选取绿圆的\\(3\\)个最近“邻居”，即\\(2\\)个红三角和\\(1\\)个蓝方块，红三角占多数，那么绿圆标记成红三角；
当\\(K=5\\)时（虚线圆圈），选取绿圆的\\(5\\)个最近“邻居”，即\\(2\\)个红三角和\\(3\\)个蓝方块，蓝方块占多数，那么绿圆标记成蓝方块；

下面给出k-NN的定义：

k-NN is a non parametric, instance based, lazy supervised algorithm

三. 关于 k-NN的进一步讨论

上文讲述了k-NN的核心思想，但仍然有很多疑问等待我们继续挖掘，(ง •̀_•́)ง

3.1. \\(K\\)的大小怎么选择?

首先我们来看下\\(K\\)的取值有什么影响，我们刚才已经看到\\(K\\)越大，参与标记决策的最近“邻居”越多，意味着正确标记的可能性越大，但是k越大越好么？
来看一个训练集，其中共有2个类别，红点-Class 1和蓝点-Class 2，每个类别100个点，画出散点图如下，我们可以大致看出左上部分主要是红点，右下部分主要是蓝点：

如果我们为两个类别划分边界：

\\(K\\) = 1 时，边界准确地划分了训练集； 而当
\\(K\\) = 5 时，训练误差变大了。

过度的追求训练集的准确性并没有什么用，因为过高的训练集的准确性会导致较低的测试集准确性，很容易导致过拟合（overfitting）。机器学习中过拟合（overfitting）指当算法在训练集上表现非常好，而对测试集上新的数据表现很差。简单来说，算法推广性较差。

随着\\(K\\)增大，边界越来越平滑。

最后，蓝色和红色区域大致分开了，同时，蓝色和红色两类中都有落到对方区域的点，这使训练误集准确性降低，不过不是坏事，因为算法的推广性更好了，对新数据标记的准确性增加，如图所示：

为了选取\\(K\\)的值，我们将一部分数据作为测试集，尝试不同的\\(K\\)值，观察验证误差。

测试误差/验证误差 = (预测错误数/验证集总数T) * 100%

验证误差最小时\\(K\\)的取值就是我们要找的\\(K\\)值，\\(K\\)值与训练集误差，K值与测试集误差之间的关系如下图所示，可以看出，当\\(K\\) = 8时，测试集误差最小。

3.2. 怎么计算最近“邻居”

给定\\(K\\)值，怎么找出最近的\\(K\\)个“邻居”呢？计算\\(x-y\\)平面上两点\\(p (x_1, y_1)\\) 和 \\(q (x_2, y_2)\\)有很多种方法，这里主要简单介绍三种。
欧式距离（Euclidean distance），即两点之间的直线距离，也是最常用的一种计算距离的方法：
\\[distance = \\sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2}\\]

切比雪夫距离:
\\[distance = max(|x_1 – x_2| , |y_1 – y_2|)\\]

曼哈顿距离，也称为\\(L1\\)距离:
\\[distance = |x_1 – x_2| + |y_1 – y_2|\\]

3.3 既然是监督学习，怎么训练？

k-NN没有显示的训练这一步骤，我们需要知道的所有内容就是最近“邻居”的标签-本身已知。也就是k-NN的训练过程就是准备好训练集中样本的特征向量和样本的标签。不过需要注意的是，我们上面距离都是\\(x-y\\)平面上点\\((x, y)\\)，两个特征值组成的特征向量，实际上一个样本可能有多个特征组成一个特征向量，别急，后面有例子(＾-＾)

3.4. 定义中的lazy, non-parametric怎么理解?

非参数（Non-parametric）
Non-parametric意味着算法不依赖样本数据的分布，模型只适应样本数据本身。这对于现实世界中不适合任何一个分布的数据集非常有用。除了k-NN，两个非常流行的非参数机器学习算法是：

• 决策树(Decision Trees )，例如像CART和C4.5
• 支持向量机（Support Vector Machines）

懒惰（lazy）

An eager learner has a model fitting or training step. A lazy learner does not have a training phase.

逻辑回归算法通过训练学习得到假设(hypothesis)的参数，进而在预测阶段使用这个假设。而K-NN则不同，它没有这一训练学习过程，而是像记住了所有训练集样本数据一样，在预测阶段全部拿来计算，看来lazy这个词还是挺恰当的(＾-＾)。

3.5. k-NN怎么用于回归?

k-NN 用来解决回归问题需要预测连续值，可以使用最近\\(K\\)个“邻居”的加权平均值，权重与和“邻居”之间的距离成反比。和解决分类问题不同，不再是看“邻居”的大多数来决定分类标签了。

3.6. 最后, 为什么选择k-NN?

k-NN是监督学习算法的一种，虽然没有训练学习的过程，但是选择最近“邻居”的过程成本较高，如果没有其他优化手段，需要计算和所有训练集样本之间的距离，然后再排序，选出\\(K\\)个最近的。随着特征向量维度增加或者是训练集样本的增加，计算成本将会是指数级的增长。不过k-NN也有优点：

• 可以快速实现 : 这也是为什么k-NN广泛作为其他算法的测试基准；
• 训练学习时间少；
• 预测准确性高: 很多研究论文中指出，k-NN在很多应用中预测的准确性都很高。

四. k-NN应用-提高约会对象匹配(python)

（参考数据集与源代码见 machine learning in action Source Code Ch02）
场景：Hellen最近在用一个在线约会app，app经常给她推荐一些她可能感兴趣的人，Hellen可以和这些人去约会，可是渐渐的Hellen发现，和她约会的这些人大致分为三种：

• 不喜欢(People she didn\’t like)
• 魅力一般(People she liked in small doses)
• 极具魅力(People she liked in large doses)

Hellen收集了一些app上没有的特征数据，希望我们帮忙将app推荐的人自动分类：

• 每年获取的飞行常客里程数
• 玩视频游戏的耗时百分比
• 每周吃掉的冰激凌（单位：升）

数据集文本格式如下：

40920   8.326976    0.953952    largeDoses14488   7.153469    1.673904    smallDoses26052   1.441871    0.805124    didntLike75136   13.147394   0.428964    didntLike35948   6.830792    1.213192    largeDoses42666   13.276369   0.543880    largeDoses67497   8.631577    0.749278    didntLike

4.1 读文件，解析特征向量和类别标签

\"\"\"读取数据集文件，输出特征矩阵和类别标签\"\"\"def file2matrix(filename):# get number of lines in filefr = open(filename)numberOfLines = len(fr.readlines())# create NumPy matrix to returnfr = open(filename)datingDataMat = zeros((numberOfLines, 3))datingLabelDescs = []index = 0for line in fr.readlines():line = line.strip()listFromLine = line.split(\'\\t\')# 3 featuresdatingDataMat[index, 0:3] = listFromLine[0:3]# label descriptiondatingLabelDescs.append(listFromLine[-1])index += 1# 类别数据转数值数据  [didntLike, smallDoses, largeDoses] -> [0, 1, 2]datingLabelDataFrame = pd.DataFrame(datingLabelDescs)datingLabelDict = {label: idx for idx, label in enumerate(unique(datingLabelDataFrame))}datingLabels = datingLabelDataFrame[0].map(datingLabelDict)return datingDataMat, datingLabels

[/code]

很多机器学习算法不能处理类别数据，例如电影类型中有科幻、爱情、恐怖、乡村等，本节例子中不喜欢(didntLike)，魅力一般（smallDoses）和极具魅力（largeDoses），因此数据预处理阶段会涉及类别数据转换成数值数据的问题。关于
有序类别特征：电影评星
无序的类别特征，如电影类型，科幻->0、爱情->1、恐怖->2、乡村->3，但这样直接编码可能存在问题，因为计算机会认为3>2>2>0，如果算法中存在数值大小有关的计算影响了结果，就需要用到独热(one-hot)技术去解决，关于这块就不细说了，感兴趣可以自己去了解。

4.2 特征标准化(normalizing numeric values)

3.2小节介绍了计算最近“邻居”的三种方法，这里我们使用常用的欧式距离（Euclidean distance），这里有3个特征，设特征向量为\\((x, y, z)\\)，则距离计算方法如下：
\\[distance = \\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}\\]
取两个样本的特征向量进行计算
\\[ \\sqrt{(40920 - 14488)^2 + (8.326976 - 7.153469)^2 + (0.953952 - 1.673904)^2}\\]
我们会发现每年的累计飞行里程数这个特征数值比较大，对距离的计算起到了决定性作用，这对其他两个特征不公平，因为在Hellen眼里，这些特征都是平等的，因此我们需要对数值进行标准化，即将处在不同数值范围的特征数据标准化到一个数值范围，比如[0,1]或者[-1,1]，我们选用[0,1]，标准化的计算方式如下：
\\[newValue = (oldValue - min)/(max - min)\\]
代码如下所示：

\"\"\"数值特征标准化\"\"\"def autoNorm(dataSet):# numpy中的array的min# arrayTest = array([[1,6,3],[4,2,5]])# arrayTest.min(0) -> array([1, 2, 3]) # 每一列的最小值# arrayTest.min(1) -> array([1, 2])  # 每一行的最小值minVal = dataSet.min(0)maxVal = dataSet.max(0)ranges = maxVal - minVal# shape：This is a tuple of integers indicating the size of the array in each dimension.# b = np.array([[1,2,3],[3,4,5]])# print(b.shape)# 输出(2,3)dataSetShape = shape(dataSet)normMat = zeros(dataSetShape)m = dataSet.shape[0]normMat = dataSet - tile(minVal, (m, 1))normMat = normMat/tile(ranges, (m, 1))return normMat, ranges, minVal

[/code]

4.3 画散点图，观察特征

在处理好特征数据之后，通常先画出散点图观察一下，可以检验下前面两步没有问题，比如输出个空，也可以看出是否有明显的规律，还可以观察是否有明显离谱的点，我们的特征向量是三维的，有三个类别标签，我们挑两个特征来看下：

\"\"\"画出散点图，观察特征数据\"\"\"def plotDataSet3d(datingDataMat, classLabels):dating_x1 = []dating_y1 = []dating_x2 = []dating_y2 = []dating_x3 = []dating_y3 = []fig = plt.figure()ax = fig.add_subplot(111)i = 0for labels in datingLabels:if labels == 0:dating_x1.append(datingDataMat[i, 0])dating_y1.append(datingDataMat[i, 1])i = i + 1if labels == 1:dating_x2.append(datingDataMat[i, 0])dating_y2.append(datingDataMat[i, 1])i = i + 1if labels == 2:dating_x3.append(datingDataMat[i, 0])dating_y3.append(datingDataMat[i, 1])i = i + 1ax.scatter(dating_x1, dating_y1, s=5, label=\'不喜欢\')ax.scatter(dating_x2, dating_y2, s=10, label=\'魅力一般\')ax.scatter(dating_x3, dating_y3, s=15, label=\'极具魅力\')plt.legend(loc=\'best\')plt.xlabel(\'每年获取的飞行常客里程数（经标准化）\')plt.ylabel(\'玩视频游戏所耗时间百分比（经标准化）\')plt.show()

[/code]

4.4 利用k-NN算法进行分类

终于来到了k-NN算法的核心部分～

\"\"\"对输入样本inX使用k-NN算法进行分类\"\"\"def kNNClassify(inX, dataSet, labels, start, k):dataSetSize = dataSet.shape[0]# Distance calculationdiffMat = tile(inX, (dataSetSize, 1)) - dataSetsqDiffMat = diffMat**2sqDistance = sqDiffMat.sum(axis=1)              # axis=0，按列相加； axis=1，按行相加；distance = sqDistance**0.5# Voting with lowest k distancessortedDistIndices = distance.argsort()          # argsort函数返回数组值从小到大索引值classCount = {}for i in range(k):labelIndex = sortedDistIndices[i]voteIlabel = labels[labelIndex + start]classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1# Sort dictionarysortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]

[/code]

4.5 验证算法

\"\"\"对测试集进行预测，k-NN算法性能\"\"\"def datingClassTest():hoRatio = 0.10filename = \"Ch02/datingTestSet.txt\"datingDataMat, datingLabels = file2matrix(filename)normMat, ranges, minVal = autoNorm(datingDataMat)# plotDataSet(normMat, datingLabels)m = normMat.shape[0]numTestVecs = int(m*hoRatio)errorCount = 0.0for i in range(numTestVecs):classifierResult = kNNClassify(normMat[i, :], normMat[numTestVecs:m, ], datingLabels[numTestVecs:m], numTestVecs,  3)print(\"the classifier came back with: %d, the real answer is: %d\" % (classifierResult, datingLabels[i]))if (classifierResult != datingLabels[i]): errorCount += 1.0print(\"the total error rate is: %f\" % (errorCount / float(numTestVecs)))print(errorCount)

[/code]

运行程序得到最终结果如下：

the total error rate is: 0.0500005.0

[/code]

Reference

KNN — The Lazy Algorithm Simplified

Machine Learning in Action

Performance Comparison between Naïve Bayes,Decision Tree and k-Nearest Neighbor in Searching Alternative Design in an Energy Simulation Tool

Introduction to k-Nearest Neighbors: Simplified (with implementation in Python)

K-nearest_neighbors_algorithm by wikipedia

euclidean-vs-chebyshev-vs-manhattan-distance

Python数据分析——类别数据的转换

Why One-Hot Encode Data in Machine Learning?

Matplotlib 如何画散点图的图例

How kNN algorithm works

[Understanding the Bias-Variance Tradeoff](

转载于:https://www.cnblogs.com/withwhom/p/11623391.html