使用环形过滤器的K 值自适应KNN算法

1 引言

近年来，随着国家大力推进大数据产业的发展，各行各业都在加快构建符合自身状况的大数据生态系统。由此产生的数据规模及维度将呈现指数增长。与此同时，诸如智能手机、平板电脑等移动设备的普及也使得数据的产生变得越来越多元化。当前Baidu、Bing、Google等搜索引擎索引了超过数百亿张图片，Youtube、爱奇艺、斗鱼等视频平台存储有数十亿个视频都是印证大数据时代最好的例子[1]。据国际数据公司（IDC）发布的研究报告称，近几年全球数据年增长率基本保持在50%左右。据粗略估计，2020年全球产生的数据将达到40 ZB[2]。面对工业和生活中出现的海量数据，人们越来越关注如何从中挖掘出有价值的信息。因此，数据挖掘逐渐成为各类研究者争相选择的热门课题。

根据挖掘任务的不同，本文大致将数据挖掘分为分类或预测模型发现、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等。其中数据分类是数据挖掘领域中最为关键的核心问题之一，已经囊括了决策树、朴素贝叶斯（Naive Bayes）、支持向量机（Support Vector Machine，SVM）、K 最近邻（K- Nearest Neighbor，KNN）及逻辑回归（Logistic Regression）等一系列成熟的分类算法[3]。其中K 最近邻算法由于其简单、易于实现等特性现已被广泛应用于文本分类、模式识别、计算机视觉、科技金融及生物医疗等领域[4]。

虽然KNN 分类算法具有对噪声点不敏感，不需要建立学习模型及算法实现简单等一系列优点[5]，但是该算法仍然存在以下问题。

（1）在处理数据规模庞大或是维度较高的数据集时，KNN算法会存在耗时较高的问题。因为KNN是一种懒惰的学习算法[6]，该算法需要扫描全部训练样本点并计算每个训练样本点与待分类样本点的相似度距离（如欧氏距离、曼哈顿距离等）。最终由待分类样本点的前K 个最近邻点来决定其类别。因此，K 近邻算法对计算机的存储和计算性能都有较高的要求。随着数据规模的增大，对于判断待分类样本点类别的系统开销也会相应增大。

（2）K 值选择的问题。数据集的大小决定了算法的耗时，而K 值的大小在一定程度上决定了算法的准确率。当选择的K 值越小时，虽然降低样本点的排序开销但是分类结果易受样本稀疏性及噪声点等异常值的影响，从而造成分类准确率的降低[7]；当选择的K 值越大时，待分类样本点可以包含更多的最近邻点，这样不仅提高了算法的排序开销而且对分类准确率也有较大的影响，尤其是在不平衡的数据集上分类尤为明显[8]。如K 值大小直接选择训练点的数量时，算法虽然可以省略最近邻点的排序开销和相似度的计算开销，但是并不能提高分类结果的准确率且不具备算法的一般性[9]。

在现有工作中，研究者们在削减数据集时，往往会损失部分最近邻点，从而造成分类的准确率相比较于传统的KNN 算法有所降低；当考虑动态K 值选择时，算法的内存消耗将存在较大程度的增长[10]。

因此，对于任意数据集时，研究如何高效地找到K个最近邻点，且保持较高的分类准确率将是一个十分有意义的课题。

2 AAKNN算法的原理及实现

AKNN（K-value Adaptive KNN Algorithm based on Annular Filter，基于环形过滤器的K 值自适应KNN算法）、KNN、ELM-KNN[11]、EKRV[12]等算法存在K 值固定的问题。当选择固定K 值进行分类时，算法容易对一些测试点的类别判断有误。如图1所示，加号表示正样本，负号表示负样本，三角形表示当前待测点。当前K 值为7，左边圆中待测点的类别根据最多类别判断为正样本，同理右边圆中的待测点的类别也是正样本。但是，右边圆中待测点的类别明显与负样本更相关。因此，诸如AKNN算法在这种情况下可能存在类别误判的情况。

图1 AKNN算法在K = 7 时的分类结果

基于环形过滤器的K 值自适应KNN算法（K-value Adaptive KNN Algorithm based on Annular Filter，AAKNN）的框架图如图2所示。该算法在上一章AKNN算法的基础上增加动态K 值选择的步骤，使得算法不仅可以缩小训练集的大小，而且能够打破AKNN算法在准确率上的瓶颈。因此相比较于KNN、LC-KNN和RCKNN算法，AAKNN 算法能够进一步提高分类的准确率，并且该算法相比较于Zhang 等人提出的CM-KNN算法[13]和kTree算法[14]能够消耗更少的内存。该算法的主要步骤为：数据处理、更新训练点与簇心点之间的距离、构建环形过滤器、构建稀疏向量及进行KNN 分类。首先在数据处理过程中使用K-Means++算法初始化m个簇心点（m 的值可以任意设置）；其次更新训练点与簇心点之间的距离，并且对聚类后的训练集以测试点为中心设置不同半径的环形过滤器；然后通过过滤出的新训练集构建当前测试点的稀疏向量；最后对稀疏向量进行KNN分类得到当前测试点的类别。下面将具体介绍算法中的步骤。

图2 AAKNN算法的流程图

2.1 环形过滤器

该步骤与前一章AKNN 算法所提出的环形过滤器一致，区别在于当前过滤器的簇心不是由聚类得出，而是直接使用K-Means++算法[15]初始化得到m 个簇心点。然后以测试点j 为中心，先用其与最近簇心c1 的距离（即dis(c1,j)）为半径画圆，从而过滤出圆内的训练点i（即满足2 ⋅dis(c1,j) ≥dis(c1,i)）。若圆内包含的训练点小于个时，则再以第二短的半径画圆（即j 点与第二近的簇心c2 之间的距离，dis(c2,i)）。若新的圆内包含训练点的数量大于等于个时，则以所包含的训练点作为当前测试点j 的新训练集，不需要再进行更长半径的过滤。若新的圆内包含的训练点仍然小于 个时，则再以第三短的半径画圆（即dis(c3,i)）。以此类推，直到过滤器包含训练点的数量大于等于 。

该步骤的目的是以三角不等式的加法运算来替代两点之间的精确计算，并且去除掉部分远离于测试点j的训练点。这与CM-KNN算法相比能够有效地缩小构建稀疏向量时的训练点数量，从而有利于降低矩阵运算中的内存消耗。

2.2 L2,1范数的定义

假设给定一个矩阵M ∈Rn × m ，其中Mi 表示为矩阵M 的第i 行，Mj 表示为矩阵M 的第j 列。本文定义出矩阵的Frobenius范数：

其中L2 范数定义为：

矩阵M 的L2,1 范数定义为：

本章使用L2,1 范数的一个最重要的特性，即通过稀疏化数据点间的关系向量来选取与当前测试点相似度较高的训练点。如以下矩阵中，若某一行全为零，则该训练点对所有测试点不起作用（即噪声点），否则算法可以从中选取对于不同测试点相似度较高的训练点。

2.3 LPP算法

LPP（Locality Preserving Projections）算法又称局部保持投影[16]，是一种新的降维算法。该算法是拉普拉斯特征映射的线性近似，其本质是通过寻找线性变换矩阵W ，以实现高维数据的降维。

假设数据集，其中xi 代表d 维空间中的某一数据点。上述变换矩阵W 可以通过最小化如下的目标函数来得到：

其中，S 表示权值矩阵，其每个元素可以由基于热核的估计定义（σ 是一个调优参数）所得到。本文为了算法简单，使用σ =1。

通过式（5）可以发现算法既能获得新的数据集在较低维度的投影，又能保持原始数据集的局部结构不变。然后式（5）通过变换操作如下：

其中D表示为对角矩阵，对角线上的第i个元素为：Di,i =，即S 的第i 列的总和。上述可知L = D - S 是一个拉普拉斯矩阵。

2.4 稀疏向量

2.4.1 构建稀疏向量

假设X ∈Rn × d 表示训练集，其中n 表示过滤器过滤出的训练点个数，d 表示训练点的维度。 Y ∈Rd × 1表示当前测试点。本章算法的核心是构建当前测试点与训练集之间的稀疏向量，即让XTW 与Y 的差值最小，其中Wi 表示当前测试点与第i 个训练点之间的相关系数。通过最小二乘法得出目标函数[17]：

其中W ∈Rn × 1 表示当前测试点的稀疏向量，即训练集与当前测试点的相关系数。上述可以看出式（7）是光滑且收敛的，并且W 的最优稀疏向量W*=(XXT)-1XY 。然而，在实际情况中XXT 可能存在不可逆的情况，所以传统目标函数通常需要加上一个正则项（如L2 正则）：

其中，是L2 正则项，λ 表示调优参数。通常也称式（8）为岭回归，求解可以得到最优W 为W*=(XXT +λI)-1XY 。但是该函数得出的W 向量不一定稀疏，即存在选取n 作为K 值情况，这不能根本性地解决K 值选择的问题。本章算法使用L2,1 范数来替代L2 范数，同时引入LPP 算法对训练集在保持局部结构的条件下进行降维操作：

其中L ∈Rd × d 。如何从式（9）中更高效地计算出最优W 在下一节中将被详细论述W* 中的元素Wi 表示第i个训练点与当前测试点的相关系数。正数（即Wi ＞0）表示第i 个训练点与当前测试点正相关，反之负相关。当Wi = 0 时，则代表第i 个训练点与当前训练点之间无相关性。因此可以认为该训练点可以不作为该测试点的最近邻点。更准确地说，仅使用具有非零系数的训练点来对测试点的类别进行预测，而无需使用所有训练点来判断当前测试点的类别。所以本文通过式（9）计算出最优稀疏向量W* ，从而根据当前测试点的数据分布来动态选择前K 个最近邻点。

为了更好理解系数向量，假设W* ∈R5 × 1 ：

从上述表示的稀疏向量可以看出，现有5个训练点和当前测试点，而向量中非零系数是第2，3 和5 个训练点，由此可以得出当前测试点的最近邻点数是3且通过第2，3和5个训练点来预测当前测试点的类别。同理可得其余测试点的稀疏向量及其所属类别。因此根据测试点周围数据的实际分布状况可以选择不同的K 值进行KNN分类，从而进一步提高算法的准确率。

2.4.2 构建过程的优化

由于式（9）的函数图像是凸且非光滑的，所以本节使用迭代重加权的最小二乘法框架对式（9）进行优化[18]。首先对当前稀疏向量W 求导，并将其赋值为零：

其中，D代表对角矩阵，第k 个对角线上的值是。通过代数变换，可以将式（10）进一步化简得出：

其中D 的取值依赖于稀疏向量W 。根据文献[19]，本文使用迭代求解式（11）的稀疏向量（即算法1中），并且证明如下。

根据算法1，可以得出：

从而可以推出：

算法1 构建稀疏向量

Input：新训练集X ，当前测试点Y

Output：当前测试点的W(t)

initialize（W(1) ，λ1，λ2）t←1

While not converge do：

compute(D(t))

W =(XXT + λ1D + λ2XLXT)-1XY

t ←t + 1

End While

returnW(t)

根据文献[17]，对于任意向量W 和W0 ，可以推出所以在算法1 的每次迭代中稀疏向量W 中的元素都会存在一定程度减小。因此稀疏向量W 会收敛到式（11）的全局最优解。

2.5 算法形式化描述

上述已经详细描述了算法的每个步骤。如算法2所示，首先对训练集X 和测试集T 进行数据正规化，并且使用K-Means++算法初始化m 个簇心点。然后精确计算每个训练点与所有簇心点之间的欧氏距离。同时算法使用环形过滤器对训练集过滤出当前待测点的新训练集，利用新训练集与当前测试点的相关性构建出两者之间的稀疏向量。最后使用KNN算法对稀疏向量进行分类操作，具体操作是通过稀疏向量中不为零的训练点来判断当前待测点的类别。因为稀疏向量能够依据当前测试点的具体情况得到不同的K 值，所以降低了测试点类别的误判率。依次通过构建每个测试点的稀疏向量，则算法可以得到整个测试集的类别。通过实验结果也验证出该算法在准确率上能够打破AKNN 和KNN算法的瓶颈。

算法2 基于环形过滤器的K 值自适应KNN 算法

Input：训练集X ，测试集T ，m 个簇心

Output：测试集的标签集T_label

训练集X 和测试集T 正规化

K-Means++算法初始化m 个簇心点

更新每个训练点的上下界

For j ←testing_start：testing_end do：

For num_k ←1：K do：

For i ←training_start：training_end do：

If 2·dis(num_k,j) ≥dis(num_k,i) THEN

X(i)={i:2·dis(num_k,j) ≥dis(num_k,i)}

End If

End For

If |X(i)| ≥K THEN

Break

End If

End For

使用算法1和新的训练集构建当前测试点的稀疏向量

对稀疏向量进行KNN 分类，得出当前测试点的类别T_label(j)

End For

return T_label

2.6 时间复杂度分析

AAKNN算法的时间复杂度为O(a ⋅x3t)，而CM-KNN算法的时间复杂度为O(a ⋅n3) ，其中a 表示求逆的次数，n 表示训练集的数量，t 表示测试集的数量，x 表示当前训练集的数量（范围属于）。该两种算法为了动态选取K 值提高了一定程度的时间复杂度，从而造成比KNN和AKNN算法耗时更高。在进行求逆运算时，AAKNN 比CM-KNN 算法可以减少n - x 个数据点。所以在内存消耗上，AAKNN比CM-KNN算法占用更少的内存。

3 实验验证及分析

上述已经详细描述了基于环形过滤器的K 值自适应算法的实现。在这一章中本文将通过大量实验来验证所提出的算法具有更优秀的性能。实验代码均使用MATLAB实现，设备使用Windows 7旗舰版操作系统，CPU型号为i5-3210M，内存为4 GB。对照实验选用常用的KNN 算法，LC-KNN，RC-KNN，Zhang 等人提出的CM-KNN，以及上一章提出的AKNN算法。其中LC-KNN和RC-KNN算法由于选用不同的地标点p 会有不同的结果，因此本文选择精度较高时的准确率作为对照。

本次实验同样选取UCI（http：//archive.ics.uci.edu/ml/index.php）数据库上6 组公开数据集：Seeds（http：//archive.ics.uci.edu/ml/datasets/seeds），Fertility（http：//archive.ics.uci.edu/ml/datasets/Fertility），Blood（http：//archive.ics.uci.edu/ml/datasets/Blood+Transfusion+Service+Center），Balance（http：//archive.ics.uci.edu/ml/support/balance+scale），Australian（http：//archive.ics.uci.edu/ml/datasets/Statlog +（Australian + Credit + Approval）），Haberman（http：//archive.ics.uci.edu/ml/datasets/Haberman%27s+Survival）。其中Seeds数据集是识别三种不同小麦的类别，维度为6；Fertility 数据集是100 个人提供的精液样本，用来判断人的身体状况是否正常；Blood数据集来源于中国台湾新竹市输血服务中心的数据，用来判断是否是男人的血液；Balance数据集分别包含训练点437个和测试点188个；Australian数据集中数据集分别包含训练点484个和测试点207个；Haberman数据集是对进行过乳腺癌手术后患者寿命的研究。

3.1 不同λ1 和λ2 对算法性能的影响

λ1 和λ2 两个参数分别代表L2,1 范数和局部保持投影在AAKNN 算法中的权重。其中通过调整λ1 的大小可以很好地控制稀疏向量W 的稀疏程度，当λ1 值越大时，稀疏向量中存在为0 的个数相应增加，使得算法去除非噪声点的数量增加，反之为0 的个数相应减少，使得算法包含太多的噪声点。两者情况对算法结果都有较大的影响。因此当选择合适的λ1 时，算法不仅能够让每个测试点达到去除噪声点的目的，而且可以选出对于当前测试点相似度高的测试点。 λ2 值的调优处理能够让训练集在降维过程中保持原始的局部结构不变，即当前测试点从高维降到低维中的仍然存在相同的最近邻点。

图3 表示不同λ1 和λ2 参数在6 组不同数据集上的RMSE结果。横坐标表示λ1 分别取{0.01，0.1，1，3，5，7，10}7 个不同值，其中使用-2 与-1 分别表示0.01 和0.1。λ2 与λ1 的取值一致，在图中使用不同形状的线段表示。纵坐标表示不同λ1 和λ2 的均方根误差。从图中可以看出，Seeds 数据集能够在（0.01，0.01），（0.01，0.1），（0.01，1），（0.01，5），（0.1，1），（1，0.01），（1，0.1），（1，7），（3，3），（5，0.01），（5，0.1），（5，1），（5，5），（5，10），（7，0.01），（7，1），（7，1），（7，3），（7，5），（7，10），（10，0.1），（10，3）和（10，7）位置下RMSE 取到最小值。 即在λ1 ∈[0.01, 10] 及λ2 = 10 范围内可以得到RMSE相对较小的值，从而反映出算法在这段参数范围内具有较高的稳定性。Fertility数据集的RMSE结果在整个参数范围内都比较平稳。因为在训练集中不同类别数据点的数量相差较大，从而造成对30 个测试点在大部分情况下都判断为正样本，使得RMSE在整个取值范围内都比较平稳。Blood 数据集除了在（1，5）位置时RMSE 的值取到最小，而且在λ1 ∈[1,7]，λ2 ={0.01,7,10} 范围内也能够得到相对较小的RMSE。Balance数据集在λ1 ∈[0.01,3]范围内λ2 ={0.01,0.1,1,3,7} 能够得到RMSE相对较小的值。Australian 数据集在λ1 ∈[3,10] ，λ2 ={0.01,0.1,1,5,7} 时RMSE 的值较小。其中当λ2 ={0.1,3,7} 时，RMSE 存在下降的趋势。最后，Haberman 数据集与Seeds数据集类似，λ1 在整个取值范围内都能取到相对较低的RMSE。其中在λ1 ∈[1,5] ，λ2 ∈[0.01,0.1] 范围内RMSE能够取到较小的值。

图3 不同参数下的RMSE统计图

从上述6 组数据集的结果分析，可以看出λ1 和λ2分别在λ1 ∈[1,7] ，λ2 ∈[0.01,5] 范围内让算法取到较稳定的分类结果。因此在本文实验中λ1 和λ2 在该范围内随机取值。

3.2 比较几种优化算法之间的区别

如图4所示，横坐标表示6组不同的数据集，纵坐标表示不同算法在不同数据集上的准确率。从图中可以看出，LC-KNN与RC-KNN算法的准确率最低。因为该两种算法会漏选实际的最近邻点，从而导致准确率最低。而KNN 和AKNN 算法的结果一致，并且两种算法都能够找到实际的最近邻点，从而提高了算法的准确率。AAKNN 算法与CM-KNN 算法的准确率最高，两者都是根据测试点的实际情况来构建不同的稀疏向量，从而为每个测试点选择不同的K 值。不同之处在于CM-KNN 和kTree 算法在寻找K 值时，是通过整个训练集来构建稀疏矩阵，而AAKNN算法对每个测试点分别过滤出内围训练点来构建自己的稀疏向量，从而进行每个测试点的K 值选择。虽然会增加一定的时间开销，但在内存紧张的情况下，AAKNN算法更加适用。

图4 不同算法在6组数据集上的准确率

如图5 所示，横坐标表示不同数据集中的测试点，纵坐标表示每个测试点实际使用的训练点的数量，红色基准线代表CM-KNN算法对于每个测试点所需使用的训练点的数量。从图中可以看出，AAKNN算法通过环形过滤器依次能够平均减少86.2%，55.14%，92.14%，90.73%，90.97%，及89.54%的训练点，从而算法能够更加快速地构建每个测试点的稀疏向量。如当前实验电脑使用的是4 GB内存，每个数字以4个字节存储，每个数据点的维度是10，则大约能够存储107 374 182 个数据点。当算法进行大量数据点的求逆运算时，则当前电脑必然不能满足当前需要。因此，升级电脑配置或者使用AAKNN算法替代CM-KNN算法都是可行的方案。

如图6 所示，横坐标表示负正类率（False Positive Rate，FPR），其代表分类算法在预测的正类中实际负样本占所有负样本的比例。纵坐标表示真正类率（True Positive Rate，TPR），其代表分类算法在预测的正类中实际正样本占所有正样本的比例。图中4 条不同的曲线分别代表不同算法在不同的数据集中的ROC 曲线。由于KNN 和AKNN 算法在判别结果上是一致的，所以本文仅使用KNN 算法的ROC 曲线来代表该两种算法。从图中可以看出，LC-KNN 与RC-KNN 算法的ROC 曲线所包含的面积最小，从而反映出该两种算法的准确性最低。因为该两种算法会漏选实际的最近邻点，从而导致准确率最低。其次是KNN算法的ROC曲线所包含的面积较大。最后是AAKNN 算法的ROC 曲线在不同数据集中所包含的面积都是最大，从而反映出该算法的准确性最高。因为越凸并且越靠近左上角的ROC 曲线代表分类器的准确性越高，并且其假正样本和假负样本的总数最少。因此，所提出的AAKNN 算法在分类准确性上要高于KNN，AKNN，LC-KNN 和RC-KNN算法。

4 总结

图5 AAKNN算法在6组数据集上的训练点数

图6 不同算法的ROC曲线

本章提出一种基于环形过滤器的K 值自适应KNN算法。该算法以AKNN算法为基础，通过环形过滤器过滤出每个测试点的内围训练集。然后通过新训练集来构建每个待测点的稀疏向量，从而得出每个测试点的动态K 值。实验结果表明AAKNN算法比AKNN算法在准确率上平均提高2%。但是在不平衡数据集中，仍然存在较高的误判率。如在Fertility 数据集中，由于负样本的数量较少，AAKNN算法可能会将类别全都判断为正样本。因此，不平衡数据集中的算法改进是下一步工作的重点。