【机器学习二】分类算法之K近邻算法

kNN原理：

对于一个给定的训练集，我们知道训练样本中的每组数据特征及其分类标签。然后输入没有标签的新数据，将新数据的每个特征与训练集中的每个特征进行比较，选取特征最相似（最近邻：k=1）的分类标签，一般来说，我们只选取前 k 个最相似的分类标签，这也是 k-近邻算法中 k 的由来，通常 k 不超过 20。最后，选择 k 个数据中出现次数最多的分类标签作为新数据的分类结果。

K-近邻算法的一般流程

收集数据：可以使用任何方法

准备数据：距离计算所需要的数值，最好是结构化的数据格式

分析数据：可以使用任何方法

训练算法：此步骤不适用于K-近邻算法

测试算法：计算错误率

使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

K近邻算法伪代码：

对未知类别属性的数据集中的每个点依次执行以下操作：

（1）计算已知类别数据集中的点与当前点之间的距离；

（2）按照距离递增次序排序；

（3）选取与当前点距离最小的k和点；

（4）确定前k个点所在类别的出现频率；

（5）返回当前k个点出现频率最高类别作为当前点的预测分类。

python3 代码：

原理示例：

import numpy as np
import operator

group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']

def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #距离计算，新的数据与样本的距离进行减法
    diffMat = np.tile(inX, (dataSetSize,1)) - dataSet
    #对数组的每一项进行平方
    sqDiffMat=diffMat**2
    #数组每个特征值进行求和
    sqDistances=sqDiffMat.sum(axis=1)
    #每个值开方
    distances=sqDistances**0.5
    #索引值排序
    sortedDistIndicies = distances.argsort()
    #选取距离最小的前k个值进行索引，从k个中选取分类最多的一个作为新数据的分类
    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)
    #返回前k个点中频率最高的类别
    return sortedClassCount[0][0]
    
print(classify0([0,0],group,labels,3))

out:B

应用实例-鸢尾花分类

本例中我们用到了鸢尾花（ Iris）数据集，这是机器学习和统计学中一个经典的数据集。它包含在 scikit-learn 的 datasets 模块中。

认识数据集

#导入数据集
from sklearn.datasets import load_iris
iris_dataset = load_iris()
#查看数据集的键
print("Keys of iris_dataset: \n{}".format(iris_dataset.keys()))
#数据集有5个键，鸢尾花数据，标签值，标签名，简要说明，特征名称（单位）
out:dict_keys(['data', 'target', 'target_names', 'DESCR', 'feature_names'])

训练数据与测试数据

我们要用新数据来评估模型的性能。新数据是指模型之前没有见过的数据，而我们有这些新数据的标签。通常的做法是将收集好的带标签数据（此例中是 150 朵花的测量数据）分成两部分。一部分数据用于构建机器学习模型，叫作训练数据（ training data）或训练集（ training set）。其余的数据用来评估模型性能，叫作测试数据（ test data）、测试集（ testset）或留出集（ hold-out set）。

scikit-learn 中的 train_test_split 函数可以打乱数据集并进行拆分。这个函数将 75% 的行数据及对应标签作为训练集，剩下 25% 的数据及其标签作为测试集。训练集与测试集的分配比例可以是随意的，但使用 25% 的数据作为测试集是很好的经验法则。scikit-learn 中的数据通常用大写的 X 表示，而标签用小写的 y 表示。这是受到了数学标准公式 f(x)=y 的启发，其中 x 是函数的输入， y 是输出。我们用大写的 X 是因为数据是一个二维数组（矩阵），用小写的 y 是因为目标是一个一维数组（向量），这也是数学中的约定。

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(
iris_dataset['data'], iris_dataset['target'], random_state=0)

在对数据进行拆分之前， train_test_split 函数利用伪随机数生成器将数据集打乱。如果我们只是将最后 25% 的数据作为测试集，那么所有数据点的标签都是 2，因为数据点是按标签排序的（参见之前 iris['target'] 的输出）。测试集中只有三个类别之一，这无法告诉我们模型的泛化能力如何，所以我们将数据打乱，确保测试集中包含所有类别的数据。

为了确保多次运行同一函数能够得到相同的输出，我们利用 random_state 参数指定了随机数生成器的种子。这样函数输出就是固定不变的，所以这行代码的输出始终相同。本书用到随机过程时，都会用这种方法指定 random_state。

train_test_split 函数的输出为 X_train、 X_test、 y_train 和 y_test，它们都是 NumPy数组。 X_train 包含 75% 的行数据， X_test 包含剩下的 25%。

K近邻算法构建模型

k 近邻算法中 k 的含义是，我们可以考虑训练集中与新数据点最近的任意 k 个邻居（比如说，距离最近的 3 个或 5 个邻居），而不是只考虑最近的那一个。然后，我们可以用这些邻居中数量最多的类别做出预测。现在我们只考虑一个邻居的情况。

scikit-learn 中所有的机器学习模型都在各自的类中实现，这些类被称为 Estimator类。 k 近邻分类算法是在 neighbors 模块的 KNeighborsClassifier 类中实现的。我们需要将这个类实例化为一个对象，然后才能使用这个模型。这时我们需要设置模型的参数。

KNeighborsClassifier 最重要的参数就是邻居的数目，这里我们设为 1：

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=1)

knn 对象对算法进行了封装，既包括用训练数据构建模型的算法，也包括对新数据点进行预测的算法。它还包括算法从训练数据中提取的信息。对于KNeighborsClassifier 来说，里面只保存了训练集。想要基于训练集来构建模型，需要调用 knn 对象的 fit 方法，输入参数为 X_train 和 y_train，二者都是 NumPy 数组，前者包含训练数据，后者包含相应的训练标签：

knn.fit(X_train, y_train)

利用模型预测

现在我们可以用这个模型对新数据进行预测了，我们可能并不知道这些新数据的正确标签。想象一下，我们在野外发现了一朵鸢尾花，花萼长 5cm 宽 2.9cm，花瓣长1cm 宽0.2cm。这朵鸢尾花属于哪个品种？我们可以将这些数据放在一个 NumPy 数组中，再次计算形状，数组形状为样本数（ 1）乘以特征数（ 4）：

X_new = np.array([[5, 2.9, 1, 0.2]])

我们调用 knn 对象的 predict 方法来进行预测：

prediction = knn.predict(X_new)
print("Prediction: {}".format(prediction))
print("Predicted target name: {}".format(
      iris_dataset['target_names'][prediction]))

out:
Prediction: [0]
Predicted target name: ['setosa']

根据我们模型的预测，这朵新的鸢尾花属于类别 0，也就是说它属于 setosa 品种。但我们怎么知道能否相信这个模型呢？我们并不知道这个样本的实际品种，这也是我们构建模型的重点啊！

评估模型

这里需要用到之前创建的测试集。这些数据没有用于构建模型，但我们知道测试集中每朵鸢尾花的实际品种。

因此，我们可以对测试数据中的每朵鸢尾花进行预测，并将预测结果与标签（已知的品种）进行对比。我们可以通过计算精度（ accuracy）来衡量模型的优劣，精度就是品种预测正确的花所占的比例：

# 1.用测试集结果与实际结果的平均值
y_pred = knn.predict(X_test)
print("Test set score: {:.2f}".format(np.mean(y_pred == y_test)))
# 2.使用 knn 对象的 score 方法来计算测试集的精度
print("Test set score: {:.2f}".format(knn.score(X_test, y_test)))

out：Test set score: 0.97

代码整合

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

iris_dataset = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
iris_dataset['data'], iris_dataset['target'], random_state=0)
knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
print("Test set score: {:.2f}".format(knn.score(X_test, y_test)))

X_new = np.array([[5, 2.9, 1, 0.2]])
prediction = knn.predict(X_new)
print("Prediction: {}".format(prediction))
print("Predicted target name: {}".format(
       iris_dataset['target_names'][prediction]))

小结

利用鸢尾花的物理测量数据来预测其品种。我们在构建模型时用到了由专家标注过
的测量数据集，专家已经给出了花的正确品种，因此这是一个监督学习问题。一共有三个品种： setosa、 versicolor 或 virginica，因此这是一个三分类问题。在分类问题中，可能的品种被称为类别（ class），每朵花的品种被称为它的标签（ label）。

鸢尾花（ Iris）数据集包含两个 NumPy 数组：一个包含数据，在 scikit-learn 中被称为 X；一个包含正确的输出或预期输出，被称为 y。数组 X 是特征的二维数组，每个数据点对应一行，每个特征对应一列。数组 y 是一维数组，里面包含一个类别标签，对每个样本都是一个 0 到 2 之间的整数。

我们将数据集分成训练集（ training set）和测试集（ test set），前者用于构建模型，后者用于评估模型对前所未见的新数据的泛化能力。

我们选择了 k 近邻分类算法，根据新数据点在训练集中距离最近的邻居来进行预测。该算法在 KNeighborsClassifier 类中实现，里面既包含构建模型的算法，也包含利用模型进行预测的算法。我们将类实例化，并设定参数。然后调用 fit 方法来构建模型，传入训练数据（ X_train）和训练输出（ y_trian）作为参数。我们用 score 方法来评估模型，该方法计算的是模型精度。我们将 score 方法用于测试集数据和测试集标签，得出模型的精度约为 97%，也就是说，该模型在测试集上 97% 的预测都是正确的。

这让我们有信心将模型应用于新数据（在我们的例子中是新花的测量数据），并相信模型在约 97% 的情况下都是正确的。