近邻算法分类

原文:Classification Using Nearest Neighbors

1.距离度量指标

将待查询数据和训练数据集的距离作为分类依据是一种简单有效的分类方法。可以使用多种指标来确定距离。

常用的距离度量有：

• 欧式距离
• 归一化欧式距离
• 马（马哈拉诺比斯）氏距离
• 城市街区距离
• 闵可夫斯基距离
• 切比雪夫距离
• 余弦距离
• 相关距离
• 汉明距离
• 杰卡德距离
• 斯皮尔曼距离

对于给定的 x 矩阵 ，将其看作是 行的行向量， 。同理对于给定的 x 矩阵 ，将其看作是 行的行向量，向量 和 之间的不同距离度量定义如下：

欧式距离(Euclidean distance)

欧几里得距离是 闵可夫斯基距离的一个特例，其中 p = 2。

归一化欧氏距离(Standardized Euclidean distance)

其中 是对角矩阵，其第个对角元素是，其中 是每个维度的缩放因子向量。

马（马哈拉诺比斯）氏距离(Mahalanobis distance)

其中是协方差矩阵。

城市街区距离(City block distance)

城市街区距离是 Minkowski 距离的一个特例，其中 p = 1。

闵可夫斯基距离(Minkowski distance)

对于 p = 1 的特殊情况，Minkowski 距离表示城市街区距离；

对于 p = 2 的特殊情况，Minkowski 距离表示欧几里得距离；

对于 p = ∞ 的特殊情况，Minkowski 距离表示切比雪夫距离；

切比雪夫距离(Chebychev distance)

切比雪夫距离是 Minkowski 距离的一个特例，其中 p = ∞。

余弦距离(Cosine distance)

相关距离(Correlation distance)

汉明距离(Hamming distance)

汉明距离表示的是两个向量 和 相同位置上元素不相同和向量长度的比值。比如 则

杰卡德距离(Jaccard distance)

斯皮尔曼距离(Spearman distance)

MATLAB中用pdist2函数计算不同距离度量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

X = [1,3];
Y = [2,4];
D1 = pdist2(X,Y,'cityblock')

D3 = pdist2(X,Y,'euclidean')

D4 = pdist2(X,Y,'minkowski',2)

D5 = pdist2(X,Y,'hamming')

D6 = pdist2(X,Y,'chebychev')

D7 = pdist2(X,Y,'cosine')

2.k近邻搜索和半径搜索

给定一组包含 n 个点的和一个距离函数，k-近邻 (kNN) 搜索可以找到 中与查询点或点集 最接近的 k 个点。kNN 算法和基于 kNN 的算法被广泛用作不同学习算法的基准。 kNN 算法相对简单且可解释性使得将其他分类技术的结果与 kNN 结果进行比较容易。

kNN 算法可以用在其他机器学习算法中，例如：

• kNN分类
• 局部加权回归
• 缺失数据插补和插值
• 密度估计

kNN可以与许多基于距离的学习的算法一起使用，例如 K-means 聚类。 相反，对于正实数 r，范围搜索 rangsearch查找 X 中与 Y 中每个点的距离为 r 的所有点。这种固定半径搜索与 kNN 搜索密切相关，因为它支持相同的距离度量和搜索类别 ，并使用相同的搜索算法。

2.1 KNN-穷举搜索

在matlab中，可以使用多种底层搜索算法实现kNN算法的搜索过程，当满足以下条件时默认使用穷举搜索方式：

• 的列数超过 10；
• 是稀疏的；
• 距离度量使用：苏氏距离、马氏距离、余弦距离、相关距离、斯皮尔曼距离、汉明距离、杰卡德距离、自定义距离函数 ；

如果搜索对象是ExhaustiveSearcher 模型对象，knnsearch 也会使用穷举搜索方法。 穷举搜索方法是找到每个查询点到中每个点的距离，按升序排列，返回距离最小的k个点。 例如，此图显示了 k = 3 个最近邻。

2.2 KNN-Kd树搜索

当输入数据满足以下所有条件时，knnsearch 默认会创建一个 Kd树来查找：

• 的列数不超过 10；
• 是非稀疏的；
• 欧式距离（默认）、城市街区距离、闵可夫斯基距离、切比雪夫距离

如果搜索对象是 KDTreeSearcher 模型对象，knnsearch 也会使用 Kd-树。

Kd-树根据坐标（而不是类别）将数据划分为每个节点最多 BucketSize（默认为 50）个点的节点。 下图中不同的颜色块对应的是不同的节点。

查找给定查询点的 k 最近邻时，knnsearch 执行以下操作：

1. 确定查询点所属的节点。 在以下示例中，查询点 (32,90) 属于节点 4。
2. 查找该节点内最近的 k 个点及其到查询点的距离。 在以下示例中，红色圆圈中的点与查询点等距，并且是节点 4 内离查询点最近的点。
3. 选择从查询点到第 k 个最近点在任何方向上具有相同距离内的任何区域的所有其他节点。 在此示例中，只有节点 3 与以查询点为中心的实心黑色圆圈重叠，其半径等于到节点 4 内最近点的距离。
4. 在该范围内的节点中搜索更接近查询点的任何点。 在以下示例中，红色方块中的点比节点 4 中的点更靠近查询点。

对少于 10 个维度（列）的大型数据集使用 Kd-树可能比使用穷举搜索方法更有效，因为knnsearch 只需要计算距离的子集。 为了最大限度地提高 Kd树的效率，请使用KDTreeSearcher模型。

2.3 搜索模型对象

通常来说，模型对象是一种存储信息的便捷方式。相关模型具有与指定搜索方法相关的值和类型的相同属性。 除了在模型中存储信息之外，还可以对模型执行某些操作。可以使用 rangesearch 在搜索模型上高效地执行 k 近邻搜索。 或者，可以使用搜索模型和范围搜索搜索指定半径内的所有邻居。 此外，还有一个通用的knnsearch 和 rangesearch 函数可以在不创建或使用模型的情况下进行搜索。

可以从以下方向考虑使用哪种类型的模型和搜索方法最适合给定的数据：

• 数据列数；
• 数据是否稀疏；
• 距离度量方式；

3.对数据进行分类—Kd树

使用Kd树方式对查询数据进行分类包括以下步骤：

1. 构建 Kd 树；
2. 使用Kd树进行 k 近邻搜索；
3. 确定待查询数据所属的类；

示例根据 Fisher iris 数据的最后两列对新点进行分类。

Step- 1 导入数据并对最后两列绘图

1
2
3
4

load fisheriris
x = meas(:,3:4);
gscatter(x(:,1),x(:,2),species)
legend('Location','best')

Step-2 绘制待查询数据

1
2
3

newpoint = [5 1.45];
line(newpoint(1),newpoint(2),'marker','x','color','k',...
   'markersize',10,'linewidth',2)

Step-3 构建Kd树近邻搜索模型

1

Mdl = KDTreeSearcher(x)

Mdl 是一个KDTreeSearcher模型。 默认情况下，它用于搜索邻居的距离度量是欧氏距离。

Step-4 找出到待查询点最近的10个点

1
2
3
4
5
6

[n,d] = knnsearch(Mdl,newpoint,'k',10);
line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o',...
    'linestyle','none','markersize',10)
xlim([4.5 5.5]);
ylim([1 2]);
axis square

Step-5 找出到待查询点最近的10个点的特征

1
2
3
4

tabulate(species(n))
       Value    Count   Percent
   virginica        2     20.00%
  versicolor        8     80.00%

可以依据不同的分类依据将此新点归类到不同的类别。

Step-6 在一组近邻点周围画一个圆圈来直观地识别近邻点

根据新点的位置定义圆的中心和直径 。

1
2
3
4
5
6

ctr = newpoint - d(end);
diameter = 2*d(end);
% Draw a circle around the 10 nearest neighbors.
h = rectangle('position',[ctr,diameter,diameter],...
   'curvature',[1 1]);
h.LineStyle = ':';

step-7 多个数据点分类

1
2
3
4
5
6
7
8
9

figure 
newpoint2 = [5 1.45;6 2;2.75 .75];
gscatter(x(:,1),x(:,2),species)
legend('location','best')
[n2,d2] = knnsearch(Mdl,newpoint2,'k',10);
line(x(n2,1),x(n2,2),'color',[.5 .5 .5],'marker','o',...
   'linestyle','none','markersize',10)
line(newpoint2(:,1),newpoint2(:,2),'marker','x','color','k',...
   'markersize',10,'linewidth',2,'linestyle','none')

完整代码：Position/knn_kd_tree.mlx at develop · Joiner12/Position (github.com)

4.使用自定义距离度量查找最近的邻居

示例说明如何找到与 X 中的三个最近卡方距离(chi-square distance)数据的索引。卡方距离常用于相关性分析(correspondence analysis)，特别是在生态应用中。

维向量 和 之间的卡方距离定义为：

其中是于维度相关的权重系数；

Step-1 随机生成两个正态分布矩阵，矩阵的行数可以变化，但列数必须相等。因为矩阵 表示训练数据集， 表示待分类数据集合；

1
2
3
4
5
6
7
8
9
10

rng(1) % For reproducibility
X = randn(50,2);
Y = randn(4,2);

h = zeros(3,1);
figure
h(1) = plot(X(:,1),X(:,2),'bx');
hold on
h(2) = plot(Y(:,1),Y(:,2),'rs','MarkerSize',10);
title('Heterogeneous Data')

Step2-定义距离函数

1
2
3
4

% distance function
w = [0.4; 0.6];
chiSqrDist = @(x,Z)sqrt((bsxfun(@minus,x,Z).^2)*w);

Step3-找出Y中每个到 X 中三个最近观测值的索引

1
2

k = 3;
[Idx,D] = knnsearch(X,Y,'Distance',chiSqrDist,'k',k);

Step4- 确定图中最近的观测值

1
2
3
4
5
6

for j = 1:k
    h(3) = plot(X(Idx(:,j),1),X(Idx(:,j),2),'ko','MarkerSize',10);
end 
legend(h,{'\texttt{X}','\texttt{Y}','Nearest Neighbor'},'Interpreter','latex')
title('Heterogeneous Data and Nearest Neighbors')
hold off

完整代码：Position/using_custom_distance_metric.mlx at develop · Joiner12/Position (github.com)

5.有监督学习的 K-近邻分类

5.1 说明

使用ClassificationKNN 分类模型实现k-近邻分类具体可以分为以下几步：

1. 构造 KNN 分类器Construct KNN Classifier
2. 检查 KNN 分类器Examine Quality of KNN Classifier
3. 使用 KNN 分类器进行预测分类 Predict Classification Using KNN Classifier
4. 修改 KNN 分类器 Modify KNN Classifier

5.2 示例

例子展示了如何为 Fisher iris 数据构建一个 k 最近邻分类器。

Step1- 导入数据

1
2
3

load fisheriris
X = meas;    % Use all data for fitting
Y = species; % Response data

Step2- 使用knn构造分类器

1

Mdl = fitcknn(X,Y)

Step3- 修改邻域大小

默认的 k 近邻分类器仅使用一个临近值。将 Mdl 的邻域大小更改为 4

1

Mdl.NumNeighbors = 4;

Step4- 重新替换和交叉验证检查 k 最近邻分类器

1
2
3
4

loss = resubLoss(Mdl)
rng(10); % For reproducibility
CVMdl = crossval(Mdl,'KFold',5);
kloss = kfoldLoss(CVMdl)

Step5- 使用kNN构造预测分类

1
2
3
4
5

flwr = mean(X); % an average flower
flwrClass = predict(Mdl,flwr)
% 预测结果
% flwrClass = 1x1 cell array
%    {'versicolor'}

完整代码：Position/knn_supervised_learn.mlx at develop · Joiner12/Position (github.com)

6.kNN开发流程总结

机器学习算法通用流程

收集数据：任何方法
准备数据：距离计算所需要的数值，最好是结构化的数据格式
分析数据：任何方法
训练算法：此步骤不适用于 k-近邻算法，k-近邻算法是在搜索过程中训练算法；
测试算法：计算错误率
使用算法：输入样本数据和结构化的输出结果，然后运行 k-近邻算法判断输入数据分类属于哪个分类，最后对计算出的分类执行后续处理。

2022-01-11 15:10