LOFTER-网易轻博

K最近邻算法

KNN模型属于有监督的学习算法，该模型将模型的构建与未知数据的预测同时进行。既可以对离散型因变量实现分类，也可以对连续型因变量实现预测。

KNN模型的中文名字叫做K最近邻算法，顾名思义就是指在未知类别的样本点附近，搜寻最近的k个已知类别的样本点，根据特定的投票规则来确定未知类别样本点所属的类别。其中，“最近”指的是在所选取特定的某种距离或相似性的度量办法下，与样本点之间距离或相似性需要达到最小。对于离散型因变量而言，通常以在k个最近的已知样本点中，频率最高的的类别作为位置样本点的预测类别；对于连续型因变量而言，通常以k个最近的样本点的均值作为未知样本的预测值。

最佳K值的确定

从KNN的基本思想来看，如果KNN模型中k值的选取过于偏小，则会导致模型的过拟合；而如果k值的选取过于偏大，则将会导致模型的欠拟合。因此，需要使用交叉验证法来确定最佳的k值。

这里可以使用sklearn.metrics.cross_val_score(estimator, X, y=None, scoring=None, cv=None)来实现k值的交叉验证。这里对其参数作简要说明：estimator为所要拟合的模型对象、X为样本自变量数据、y为样本因变量数据、scoring为模型的评价指标，cv为交叉验证法的分割组数。其中对于分类问题来说一本采用’accuracy’作为scoring参数，对于预测问题一般使用’neg_mean_squared_erro’作为scoring参数，这里以KNN分类问题为例：

Accuracy = []

K = np.arange(1,50)

For k in K:

         Cv_score = sklearn.metrics.cross_val_score(estimator = sklearn.neighbors.KNeighborsClassifier(n_neighbors = k, weights = ‘distance’), X = X_train, y = Y_train, cv = 10, scoring = ‘accuracy’)

         Accuracy.append(Cv_score.mean())

由上可以得到在不同k值的条件下，所构建的KNN模型的accuracy平均得分，根据accuracy的意义，可以选用平均得分最大值所对应的k值。（注意：K值需为整数型，如为浮点型会出现错误，可使用np.ceil()、np.floor()或直接使用.astype(‘int’)方法将k值的可能取值数组转换成整数型）

相似度的度量方法

根据KNN算法的思想，其中的一个重要步骤就是确定各已知样本点与未知样本点的距离，这里简单介绍几种常用的距离或相似度的度量方法。

1.欧氏距离

欧氏距离是由平面空间中两点之间直线距离的推广，在n维空间中，点A和点B的欧式距离公式为：

2.曼哈顿距离

曼哈顿距离又称为“曼哈顿街区距离”，度量的为两点在轴上的相对距离的总和。在n维空间中，点A和点B的曼哈顿距离的公式为：

3.余弦相似度

该相似度实质上可以理解为两点构成向量夹角的余弦值，夹角越小，则余弦值越接近于1，说明两点之间越相似。在n为空间中，余弦相似度的公式为：

4.杰卡德相似系数

杰卡德相似系数和余弦相似度常用于推荐算法。这里举个例子说明杰卡德相似系数的计算方法：A用户购买了10件不同商品，B用户购买了15件不同商品，其中AB两个共有8件商品相同，二者一共购买了17种不同的商品，则相似系数则可以表示为：

5. 闵氏距离

闵氏距离，全称为闵可夫斯基距离，为sklearn中KNN分类算法的默认距离计算方法。在n维空间中，p为常数，点A和点B的闵氏距离为：

从上式不难看出，当p=1时，即为曼哈顿距离；当p=2时，即为欧氏距离；这里补充一下，当p→∞时，为切比雪夫距离。

近邻样本的搜寻方法

根据KNN算法的思想，在确定距离度量方法和最佳k值之后，接下来便可展开对未知样本点的近邻样本的搜寻。

1.暴力搜寻法

顾名思义，该搜寻法简单粗暴。其思想是对于每一个未知样本点，将其与每一个已知样本点的距离计算出来，并选取其中距离最小的k个作为近邻样本。该方法适用于小样本的数据集，如果数据集样本数量较大，会使得KNN算法效率低下，因此介绍另外两种搜寻方法。

2.KD树搜寻法

KD树是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索。k-d树是每个节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。选择超平面的方法如下：每个节点都与k维中垂直于超平面的那一维有关。因此，如果选择按照x轴划分，所有x值小于指定值的节点都会出现在左子树，所有x值大于指定值的节点都会出现在右子树。这样，超平面可以用该x值来确定，其法线为x轴的单位向量。其具体构建方法可以参考：kd-tree百度百科。

3.球树搜寻法

球树的英文称为ball-tree，其产生是为了解决KD树在高维空间中效率低下的问题，因此引入了ball-tree。KD树在搜索路径优化时使用的是两点之间的距离来判断，而球树使用的是两边之和与第三边大小来判断。其具体构建思想可以参考：20.推荐召回算法之k近邻算法：局部敏感哈希、kdtree、balltree算法分析与比较

Python实现

对于KNN模型的Python实现，一般使用sklearn的neighbors模块中的KNeighborsClassifier()类和KNeighborsRegressor()类来实现，详细使用说明参考官方说明文档。