改进的k最邻近算法在海量数据挖掘中的应用

黄文秀， 唐超尘， 神显豪， 周术诚

(1. 福州工商学院工学院， 福建福州350715； 2. 西安电子科技大学通信工程学院， 陕西西安710071；3. 桂林理工大学广西嵌入式技术与智能系统重点实验室， 广西桂林541004；4. 福建农林大学计算机与信息学院, 福建福州350002)

文本分类作为数据挖掘技术的重要环节之一，其分类性能对数据挖掘的效果具有重要影响。特别是对于海量数据挖掘人工整理及分类数据已经不能满足要求，将海量数据进行有效分类，是数据资源被利用的关键，也是数据挖掘需要克服的难题。在数据挖掘研究中，数据文本并非完全独立存在[1]，利用数据文本间的强联系性和弱相关性，可以对数据文本进行有效的分类处理，提高了文本管理的有效性。对分类后的数据进行有效处理，能够更加充分地挖掘出数据内在的价值。

在数据分类过程中， 常用的算法有支持向量机(SVM)、 贝叶斯法及决策树法等。 文献[2]中研究了改进的SVM针对样本不均衡情况下的优化分类方法， 文献[3]中对改进的贝叶斯方法对文本分类的优化进行了研究。 基于上述3种机器学习挖掘算法的数据分类存在准确度较低的问题， 而k最近邻(k-nearest neighbor， KNN)算法表现出较强的分类能力， 在数据分类过程中应用非常广泛[4-5]。 例如， 文献[6]中提出了一种改进的KNN短文本分类算法， 相比SVM等算法， 该算法的效率提高近50%， 分类的准确性也有一定的提升； 但是， 面对海量数据， 特别是面对处理样本分布不均衡的大规模数据挖掘任务时， KNN算法的运行效率成为其短板， 并且分类准确度下降[7-8]， 因此如何提高KNN算法的分类效率及分类准确度成为KNN算法研究的关键。 本文中采取样本均衡思想， 根据KNN训练样本分布情况， 对样本的领域密集区域进行优化处理， 旨在进一步提高数据样本的分类效率和分类准确度。

1 KNN算法

首先假设需要进行分类的2个样本向量为di、dj(i、j分别为不同的样本类别)，两者之间的相似程度计算方法[4]为

(1)

根据式(1)计算的相似度的降序结果进行筛选，选择前k个样本作为邻域。对这k个样本进行权重设置，设置方法[5]为

(2)

式中：w为样本的对应权重；Cm为第m类样本的集合； δ函数为

根据式(2)的计算结果，生成分类决策结果[6]，

(3)

式中Cf为最终分类结果。

2 基于样本均衡的KNN算法

2.1 样本均衡原理

假设在KNN算法中存在2个数据样本A和B。对于仅求两者交集的情况，若2个样本的属性不同，则可能出现A∩B=∅。考虑到样本属性之间的联系，若A样本的第M个属性和B样本的第N个属性存在关联，那么，从数据挖掘的角度来说A∩B=∅并不成立。在实际操作中，KNN算法在解决这种因样本属性存在某种或强或弱的关联(样本分布不均衡)而引起的分类问题时，会导致KNN算法的性能劣化[7]，运行时间增加，因此必须采用有效方法来优化KNN算法。

2.2 样本均衡处理

设样本集合S中2个样本A、B之间的距离为d(A,B), 那么样本集合S中的任意样本A∈S，邻域ε的圆形区域范围[8]为

Nε={B|d(A,B)≤ε,B∈D} ，

式中D为不同于S的另一个集合。 设样本A在邻域ε中的最小样本个数为Smin， 那么根据Nε与Smin的关系， 可以确定该邻域内的样本分布情况[9]， 即当Nε>Smin时，该邻域为密集区域； 当Nε

图1所示为文本分布示意图。 样本分为“+”和“*” 2类。 从“+”类角度来看， 红色圈表示“+”类的类内区域， 蓝色圈表示“+”类的分界区域。

图1 文本分布示意图

文本邻域的密集区域分布如图2(a)所示。由图可以看出，文本B、C均处于密集区域，设文本B的Smin为5，若文本C处于文本B的ε邻域内，那么将该文本优化掉，同时将Nε缩放，直到Nε=Smin，则文本B的邻域变为均匀分布区域。经过处理后的文本B的区域如图2(b)所示。

(a)密集区域分布

对于边界处的文本处理稍显复杂，从图2(a)可以看出，文本A的邻域内有多个类别，设类别总数为ctot。设边界区域内的样本个数为sbor，且有sbor≥Smin。当sbor≤ctot时，边界区域对每种类别只保留1个样本[10-11]；当sbor>ctot时，根据每个类别的样本数量按比例保留各类别样本。

2.3 基于样本均衡的KNN算法流程

通过样本均衡处理后的改进的KNN算法流程如图3所示。

改进的KNN算法流程有4个初始值需要设定，分别是Smin、ctot、k值和准确度阈值。这4个参数的设置与KNN算法的分类准确度和分类效率有密切的联系，其中ctot和准确度阈值可以根据实际情况需要设定，一般ctot可根据训练样本指定的类别数直接设定[12]，而准确度阈值作为算法迭代运行终止的判别条件，在设置时需要根据实际分类的准确率要求而定。Smin和k值需要在改进的KNN算法模型优化过程中不断调整来达到理想的分类性能。

3 实例仿真

为了验证改进的KNN算法在海量数据挖掘的性能，以某图书馆平台的馆藏数据进行实例仿真。选取运动、艺术、历史、计算机和地理5个类别的样本，5类样本的数据样本集[13-14]如表1所示。

图3 改进的k最邻近(KNN)算法流程

表1 5个类别样本集的属性参数

3.1 分类准确度

首先，设KNN算法的k值为10，Smin值为5。根据表1，分别对5种不同样本的ctot进行设定，分别为21、 23、 15、 22、 3，然后分别采用传统KNN算法和改进的KNN算法对5类不同的数据样本进行性能仿真，验证算法的分类准确度，分类准确度指标为查准率和查全率[15]。仿真结果统计如表2所示。

从表2中可以看出，相比于传统KNN算法，本文中提出的改进KNN算法在分类性能方面表现更优。为了进一步验证本文中提出的算法在数据挖掘中的效果，在相同数据集情况下，分别采用常见分类算法(SVM、贝叶斯法和决策树法)进行对比仿真，比较不同分类算法的精准率与召回率的调和平均数F1的最大值、最小值和平均值，结果如表3所示。

表2 传统k最邻近(KNN)算法与改进KNN算法的分类准确率

表3 不同分类算法的精准率与召回率的调和平均数F1

与其他3种常见分类算法相比，改进的KNN算法对于5种不同样本集的F1值更大，表明该算法的分类性能更优。特别是在样本“计算机”的分类中，F1均值达到0.918 2，比其他算法的均值提升较大。在5种不同类别的数据样本中，改进的KNN算法的分类性能(按照F1值的平均值从大到小)排序为计算机、 历史、 地理、 运动、 艺术。

3.2 样本均衡性能

为了验证经过样本均衡处理后的KNN算法的性能，对“运动”样本集进行训练，k值设为20，Smin设置为区间[1, 10]，验证邻域密集区域的样本裁剪优化情况，并对样本均衡处理后的KNN算法的性能和未经过样本均衡处理的KNN算法性能进行对比，结果如表4所示。

表4 “运动”样本集裁剪优化结果

通过不断改变样本“运动”的邻域样本个数最小值Smin，邻域样本密集区域不断改变。当Smin逐渐增大，密集区域的Nε扩大，所需要裁剪优化的样本数量减少；当Smin较小时，Nε区域很小，因此需要进行大量样本的裁剪优化，优化比例达到了45.96%。在实际操作中，Smin过小，样本数量裁剪过多，会影响分类性能，一般优化比例在20%左右较合理。

在实际的改进KNN算法建模过程中，可以通过k值和Smin值组合调节，根据实际需要，设置合适的参数来完成KNN算法的数据分类，以便能够提高改进KNN算法的分类准确度。

3.3 运行时间

KNN算法k值设为10，Smin设为8，对5种不同的样本集进行分类，对3种常见分类算法与改进的KNN算法的运行时间进行仿真，要求F1值不小于70%，否则算法继续，直到F1值大于或等于70%。不同分类算法的运行时间如表5所示。

表5 不同分类算法的运行时间 s

在实验数据集相同的条件下，设置F1值大于或等于70%为阈值，当达到该条件时，改进的KNN算法优势明显，所用的时间比其他3种算法所用的时间更少。

不断提高F1值的阈值门槛，继续实验，所有算法的运算时间均在增加。当阈值门槛提高至80%时，在对样本“艺术”进行分类时，发现SVM算法并未收敛，这可能是由SVM对样本“艺术”分类准确度较低导致的。综合而言，改进的KNN算法在分类准确度和分类时间方面更有优势。

4 结语

将KNN算法的训练样本经过样本均衡策略处理后，能够较大幅度地提高样本分类准确度和分类效率。与传统KNN算法及常见分类算法相比，改进的KNN算法表现出更稳定的F1指标性能和运行时间性能，但是，对于高维稀疏数据，该算法的运行效率下降较明显。后续将对如何将KNN算法与降维方法和特征选择方法进行结合开展进一步研究。