优先出版 计 算 机 应 用 研 究 第33 卷----------------------------基金项目：国家自然科学基金资助项目（61170131，61263035）；国家“863”计划项目（2012AA011005）；国家“973”计划项目（2013CB329404）；广西自然科学基金资助项目（2012GXNSFGA060004）；广西八桂创新团队、广西百人计划和广西高校科学技术研究重点项目（2013ZD04）；广西自然科学基金项目（2014jjAA70175）作者简介：苏毅娟（1976-），女，广西桂林人，副教授，主要研究方向为机器学习和数据挖掘；邓振云+（1991-），男（通信作者），江西南昌人，硕士，主要研究方向为机器学习和数据挖掘；程德波（1990-），男，江西丰城人，硕士，主要研究方向为数据挖掘和机器学习；宗鸣（1990-），男，江苏泰州人，硕士，主要研究方向为机器学习和数据挖掘．大数据下的快速KNN 分类算法 *苏毅娟1，邓振云2，程德波2，宗 鸣2(1．广西师范学院 计算机与信息工程学院，南宁 230023；2．广西师范大学 广西多源信息挖掘与安全重点实验室，广西 桂林，541004)摘 要：针对K 最近邻算法测试复杂度至少为线性，导致其在大数据样本情况下的效率很低的问题，提出了一种应用于大数据下的快速KNN 分类算法。该算法创新的在K 最近邻算法中引入训练过程，即通过线性复杂度聚类方法对大数据样本进行分块，然后在测试过程中找出与待测样本距离最近的块，并将其作为新的训练样本进行K 最近邻分类。这样的过程大幅度的减少了K 最近邻算法的测试开销，使其能在大数据集中得以应用。实验表明，本文算法在与经典KNN分类准确率保持近似的情况下，分类的速度明显快于经典KNN 算法。关键词：K 最近邻；测试复杂度；大数据；分块；聚类中心中图分类号：TP181Fast KNN classification algorithm under large dataSu Yijuan1, Deng Zhenyun2, Cheng Debo2, Zong Ming2(1. College of Computer & information Technology, Guangxi Teachers Education University, Nanning 530023, China; 2.Guangxi Key Lab of Multi-source Information Mining & Security, Guangxi Normal University, Guilin Guangxi 541004, China)Abstract: Aim at the problems of the K-Nearest Neighbor algorithm testing complex is linear at least. and lead to the accuracyis low when the samples large. This paper proposed a fast KNN classification algorithm faster than the traditional KNN does.The proposed algorithm innovation introduce the training process during the KNN method. i.e. the algorithm blocks the big databy linear complexity clustering. Then. the algorithm select the nearest cluster as new training samples and establish aclassification model. This process reduces the KNN algorithm testing overhead. which makes the proposed algorithm can beapplied to big data. Experiments result showed that the accuracy of the proposed KNN classification is similarity than thetraditional KNN. but the classification speed has been significantly improved.Key Words: K-nearest neighbor;testing complex;big data;cluster;cluster centers0 引言随着互联网的迅猛发展，大数据不断的产生，分类作为当前数据挖掘中最实用的技术之一，已得到广泛的应用。目前常用的分类方法有决策树、人工神经网络、SVM、Bayes、KNN等。KNN 算法因其简单和有效在分类算法中得到广泛的应用，其基本思想是：在训练样本中找到待测样本的k 个最近邻样本,然后根据这k 个最近邻样本的类进行投票，以此来决定测试样本的类别。但是KNN 在寻找最近邻样本的过程中,需要逐个计算测试样本与每个训练样本的距离(或相似度)，当训练样本为大数据时，将会产生很高的计算开销，如果大数据集是保存在内存(或硬盘)中，这种逐个扫描的方式将几乎不可行。目前提出了许多对于KNN 的改进算法，比如文献[1][2]提出一种从所有已知样本中选取测试样本的k 个最近邻，然后建立分类器进行分类的方法，提高了分类的性能。文献[3]提出了一种基于密度的训练样本裁剪方法，使样本分布密度趋于平均，降低了KNN 的计算量。文献[4]提出了一种基于利用中心文档代替原始样本建立分类模型的方法，减少了KNN 算法需要进行相似计算的样本数，从而达到提高分类速度的目的。文献[5]提出了减少大量计算的排类算法和归类算法，在不影响原有准确率的情况下，构建了一种基于KNN 的快速分类算法，提高了分类的速度。这些算法主要是通过快速搜索算法、降维[6-8]或通过一定的优化策略直接减少需要进行相关性计算的样本数，从而提高分类的效率。但当面临大数据和高维样本时，这些分类方法的效率将会大幅度降低[9-11]。针对KNN 算法无训练过程的特点[12-13]，本文创新的对其引网络出版时间：2015-09-29 08:24:28网络出版地址：http://www.cnki.net/kcms/detail/51.1196.TP.20150929.0824.020.html优先出版 计 算 机 应 用 研 究 第33 卷入一个训练过程，即首先采用线性复杂度聚类方法对大数据进行分块。而在测试过程，对于每一个测试样本，首先找出与待测样本距离最近的聚类中心所在的簇作为新的训练样本集，然后对新训练集建立分类模型进行分类，由于聚类后簇内样本的相似度高，所以该算法能达到既减少计算量，又能保持较高分类准确率的目的。1 基于聚类的KNN 改进算法本文算法包括两个过程，即训练过程和测试过程。训练过程主要选取适用的聚类算法对大数据样本进行分类，测试过程主要是对测试样本在它最近的簇运行KNN 算法。1.1 训练过程聚类是数据分析中最基本的一种技术，它在数据挖掘、机器学习、模式识别方面都受到广泛应用。所谓聚类就是将数据对象分组成多个类和簇的过程。其中，聚类所生成的簇包含以下两个性质：簇内样本相似性高和簇之间差异性大。目前的聚类方法有很多，例如基于划分的k-means 算法，基于层次的BIRCH 算法[14]和基于密度的DBSCAN 算法[15]等。但是面临高维大样本数据时，常见的聚类算法将在时间复杂度方面受到极大挑战。因此，对高维大样本数据进行聚类需要满足一些条件：复杂度低，最好是线性的，如文献[16][17]。为此，本文采用了[18]提出的聚类算法，该算法提出一种基于界标的谱聚类(Landmark-based Spectral clustering) LSC 算法，该算法主要是选取p ( n p << )个具有代表性的点作为界标点，并将这p 个界标点进行线性组合以替代原始数据。注意，常见的谱聚类算法[19]通常用所有样本表达每个数据。因此，这种方法大大降低了相似矩阵的复杂度，即从二次降到了一次，从而也顺带把特征根求解的复杂度降低到了线性[20]。LSC 算法通过“压缩”原始数据找出一组基向量去代表每个数据点，即找出p 个具有代表的界标点。常见的选取界标点的方法有随机选取法和k-means 聚类。随机选取法即随机选取界标点，而k-means 聚类算法通过简单重复算法几次(通常低于10 次)，把得到的聚类中心作为界标点。本文重复k-means 聚类算法10 次，把得到的聚类中心作为界标点。我们把每个界标点当做一个向量组成界标矩阵U ，LSC 算法用得到的p 个界标点去表示所有的原始数据点m nx xn ´ = [ 1, , ]ÎR L X ，即找出X 在界标矩阵上的投影Z：< >Î= Îå < >ij Uh i jh i jji j UK x uK x uzi，'( , ')( , )(1)其中j u 是矩阵U 的第j 个列向量， U<i> 是由xi的r 个最近邻界标组成的U 的子矩阵。易知，矩阵Z 的运行时间为O( pmn)。接着对其进行谱聚类分析，首先构造如下图矩阵W：Ù ÙW= Z ZT(2)其中Z Z -1/ 2Ù= D ， D 是Z 中行向量的和，则矩阵W即为一个单位矩阵I 。当得到单位图矩阵W 后，通过奇异值分解计算ÙZ 的特征向量，如下：T Z = ASBÙ(3)易知，左奇异向量p pa ak R ´ = [ 1, , ]ΠA L 为矩阵٠٠TZZ 前k个特征向量，右奇异向量n pb bk R ´ = [ 1, , ]ΠB L 为矩阵Ù ÙZ ZT的特征向量。由于矩阵Ù Ù= Z Z WT为p p ´ 维，可知向量A 的计算时间为( ) 3 p O ，而特征向量B 的计算时间则可通过如下公式得出：Ù- S = Z A B T 1 T(4)特征向量B 的总时间为( ) 2 3 n p p O + [21]。由于n p << ，所以当我们选取特征向量B 进行k-means 聚类时，算法的运行的总时间则由( ) 3nO 降为) ( 3 p O ，算法的效率得到明显的提高。这种低复杂度的算法非常适合在大数据方面的应用。最后，给出LSC 算法的具体步骤，如下所示：算法1：LSC 算法输 入：n 个数据点mx1, x2,Kxn ÎR 以及聚类个数k输 出：k 个子簇(1) 通过k-means 选取p 个界标点(2) 根据公式(1)投影原始数据X 到界标矩阵，得到原始矩阵的表示p´n ZÎR(3) 根据矩阵Z ，计算TZZ 的前k 个特征向量A(4) 根据公式(4)计算特征向量B(5) 运用k-means 对特征向量B 进行最终的聚类，并 输出k个子簇1.2 测试过程本文在采用LSC 算法得到k 个子簇并求出k 个聚类中心后，找出距离待测样本最近的聚类中心所在的子簇，将其作为新的训练样本，由于通过LSC 聚类得到的子簇中的样本都是彼此相似的，因此在选定的子簇中进行KNN 分类可以充分保证分类的准确率。最后，给出基于LSC 聚类的KNN 改进算法的具体步骤，如下所示：算法2：LC-KNN 算法输 入：数据集输 出：待测样本类标签的预测值(1) 使用LSC 聚类方法对训练样本进行聚类，得到m 个聚类中心C1,C2,C3,....,Cm(2) 计算待测样本y 与所有聚类中心的距离D( y,Ci ) ，将与之距离最近的聚类中心所在的簇作为新的训练样本，即NewXi = min{D( y,Ci )} i =1,2,L,m优先出版 计 算 机 应 用 研 究 第33 卷(3) 在新训练样本i NewX 中对待测样本进行KNN 分类，得到待测样本y 的k 个最近邻，并通过投票确定其类标签的预测值i class通过上述算法2 可知，当聚类的个数较多，即m 较大时，新的训练样本i NewX 的样本数将远小于原始样本数，可以很容易达到大幅度减少KNN 的计算量[22-23]，提高分类的速度的目的。但是随着m 的增大，聚类的开销也会同时增加，且新训练样本i NewX 中的样本数将会逐渐减小，这很有可能会导致分类准确率的下降。所以为了避免这种情况，聚类的个数m 需要设置在一个比较合理的数值。极端情况下，假定令m 为样本个数时，则为1NN 算法，该算法分类的效率较高，但当训练样本分布比较集中时，则很有可能导致分类准确率降低；而令m=1 时，则为经典的KNN算法。因此，常见k 最近邻算法是本文算法的一种特例。通过以上分析可知，聚类的簇的个数m 越大，KNN 分类需要扫描的样本数也就越少，运行速度越快。但是考虑到样本集为大数据，如果m 较小，簇中样本数依然很大，不能在内存(数据空间)中运行。因此，假设程序运行占用的总内存为M ，计算机系统内存为0M ，样本集中最小类样本的个数为0n 。那么m 的取值范围可表示如下：00m nMM< <在步骤3 确定新训练样本i NewX ，对测试样本选取k 个最近邻过程中，k 值是非常重要的参数之一。文献[24]建议n = k (n>100)，n 是测试样本的个数，但这种取法通常不能得到满意的结果，并且该想法也没有理论保证。由于本文提出的基于LSC 的聚类方法得到子簇i NewX 中样本之间都是相关的，考虑到在大数据中需要减少KNN 的计算量，因此k 值的选取不宜过大，应在保持较高分类准确率的情况下，k 值的选取应尽可能小。通过实验发现，当k=1,2 时，分类的结果较优。1.3 图例说明KNN 分类算法虽然简单、有效且准确率高，但是缺点也很明显：其时间复杂度几乎与样本数成正比。这是因为KNN 算法是一种懒惰的基于实例的学习方法，每次在寻找待测样本的k个最近邻时，都需要计算其与所有训练样本的距离，当训练样本较大时，分类的时间也成正比增加，考虑到目前KNN 分类都是在数据空间中进行，在样本为大数据情况下要扫描数据集(或者从磁盘/内存中读取)一遍几乎不可能。为了解决这个问题，本文将样本集分成多个较小的块(保证每个块都能够在内存中运行)，并将具有代表性的块作为新的训练样本，进行KNN 分类。如图1，对样本集进行聚类得到3 个聚类中心，分别计算测试样本与3 个聚类中心的距离，可知测试样本1 距离簇1 的聚类中心最近，因此本算法将簇1 作为样本1 的新的训练样本；而对于测试样本2，其最近邻样本中虽然包含簇2、簇3 的样本，但是距离最近的聚类中心为簇3，所以我们将簇3 作为新的测试集。考虑到仅将簇3 作为新的训练样本，可能会影响分类准确率。但通过LSC聚类得到的簇内样本之间具有较高的相似性，簇簇之间样本差异性大，所以，将簇3 作为新的训练样本集进行KNN 分类时，依旧能够保持较高的分类准确率。图 1 改进算法中测试样本选择训练样本集的过程2 实验设计为了验证算法的有效性，本文通过MATLAB 编程实现本文算法，并在win7 系统下的MATLAB 7.1 软件上进行实验。本文以分类准确率和时间作为评价指标，对随机分块KNN 算法、基于LSC 聚类的KNN 改进算法以及经典KNN 算法进行对比。实验所用数据来源于LIBSVM 和UCI 数据集，数据集的基本信息如下表1 所示：表1 数据集基本信息No 数据集 样本数 属性数 类数1 usps 9298 256 102 mnist 70000 780 103 gisette 7000 5000 24 letter 20000 16 265 pendigits 10992 16 106 satimage 6435 36 62.1 分簇数m 的确定改进算法中m 是非常重要的参数之一。为了确定参数m，我们对随机分块KNN算法和本文改进算法在6 个数据集上分别重复10 次，实验结果不但报告每次实验的结果而且报告10 次结果的均值和方差。实验结果如表2-表7 所示：表2 两种算法在usps 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.9027±1.6498e-005 0.9355±7.1306e-006time 3.5589±0.0107 3.7605±0.024215 correct 0.8964±5.1803-005 0.9338± 4.1625e-006time 2.4857±0.0032 2.7260± 0.007720correct 0.8770±7.4889e-005 0.9300± 4.9238e-006time 1.8586± 0.0008 2.5157±0.0192825 correct 0.8793± 4.9917e-005 0.9284±1.0637e-005time 1.8586± 0.0008 1.9971± 0.004230 correct 0.8607± 4.6629e-005 0.9275±1.1596e-005time 1.6441± 0.0002 1.9249± 0.0023优先出版 计 算 机 应 用 研 究 第33 卷表3 两种算法在mnist 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.7221± 4.8878e-005 0.8389±3.1656e-005time 0.508 2.9369± 0.0927 3.5504±15 correct 0.6840± 2.3333e-004 0.8364± 2.3136e-005time 2.8905± 0.0456 3.1222±0.0139720correct 0.6657± 2.4739e-004 0.8353±3.3233e-005time 0.0011 2.0564± 0.0065 2.1490±25 correct 0.6478± 2.2689e-004 0.8338±8.7844e-005time 0.0020 1.8240± 0.0094 2.1148±30 correct 0.6396±6.9156e-005 0.8313±3.8678e-005time 1.5457± 0.0002 1.7274± 0.0011表4 两种算法在gisette 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.9311±5.0989e-005 0.9526±1.4711e-005time 0.9677 23.3933± 3.2405 28.5940±15 correct 0.9252±1.0573e-004 0.9494±1.3378e-005time 0.2434 18.0106± 1.0894 23.1904±20correct 0.9166± 2.8267e-005 0.9411±5.4699e-004time 0.0966 12.7685± 0.8880 16.2759±25 correct 0.9150±7.0000e-005 0.9321±6.4810e-004time 9.9201± 0.3696 13.8645±1.509330 correct 0.9079±1.0366e-004 0.9192±5.3796e-004time 8.4064±0.0784 11.3922±0.0658表5 两种算法在letter 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.7892±3.8822e-005 0.9495±1.0760e-006time 3.2391± 0.0015 3.2994±0.001015 correct 0.7932±3.7106e-005 0.9469±5.5751e-006time 3.3808±0.0435 3.4334±0.058520correct 0.6815±1.3812e-004 0.9451±1.9756e-006time 3.0938±5.8392e-004 3.1285±3.1243e-00425 correct 0.7279±5.6480e-005 0.9423±5.2818e-006time 3.3950±0.0018 3.4813±0.005430 correct 0.6214±9.8480e-005 0.9403±3.9204e-006time 3.0889±0.0013 3.1168±3.8514e-004表6 两种算法在pendigits 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.9452±3.5382e-005 0.9721± 4.7991e-006time 2.3380± 0.0041 2.4056± 0.010115 correct 0.9316±1.0341e-004 0.9711±6.0196e-006time 2.5451± 0.0011 2.5709±0.0089820correct 0.9163±1.5515e-004 0.9700± 2.5390e-006time 2.2233±6.4795e-005 2.2554± 2.1569e-00425 correct 0.9216±1.5677e-004 0.9687±3.5642e-006time 2.5270± 0.0056 2.5468± 0.008330 correct 0.9088±1.8409e-004 0.9683±1.5809e-006time 2.1805±7.4785e-005 2.2022±8.9611e-005表7 两种算法在satimage 数据集上的对比分块数m 评价指标 随机分块KNN 基于聚类的KNN10correct 0.8603±8.9122e-005 0.8883 ±8.1139e -006time 1.2868±6.5495e-005 1.3027±1.1429e-00415 correct 0.7917±3.1680e-005 0.9468±3.7244e-006time 0.0332 3.8583± 0.0152 3.9337±20correct 005 - 8.8847e 0.8418± 6.80280.8884±time 1.2292±3.2277e-005 1.2463± 4.3126e-00525 correct 0.7283±1.1039e-004 0.9421±8.8449e-006time 0.0061 3.5062± 0.0052 3.6287±30 correct 0.8312±3.5146e-004 0.8878± 4.9556e-006time 1.2225±1.8176e-005 1.2396±1.7711e-005通过表2~表7 可知，随着分块数m 的增加，两种算法的分类的速度逐渐变快，但相应的分类准确率却逐渐下降。考虑到两种算法都属于近似算法，如果分类的准确率明显低于经典KNN 算法，那么在大数据分类中将会出现很大的误分率，这显然是不可取。此外，从表2~表7 可知，在分类时间相近的情况下，基于LSC 聚类的KNN 算法的分类准确率明显高于随机分块的KNN 算法，且从表8 中可以发现，其分类准确率更加接近经典KNN 算法。依据上文分析可知，聚类分簇的个数m 的大小同样应该是在保证所有子簇都能在内存中运行的情况下，尽可能小。这样既减小了聚类的时间，又提高了分类的速度，并且能保证具有较高的分类准确率。根据表2~7 的实验结果显示，在m=10 的情况下，分类的结果更优。2.2 k 值的确定在算法2 确定新的训练样本i NewX 后，需利用KNN 算法对测试样本在i NewX 中建立分类模型，其中对于k 值的选取是非常重要的步骤之一。考虑到经LSC 聚类后簇内的样本已具有很高的相似性，所以k 值的选择无需太大。为了确定k 的取值，我们分别对表1 中数据集进行了如下实验，为了保证实验的准确性，实验结果中每个点都是10 次结果的均值。图2 6 个数据集分别在不同k 值时的分类准确率优先出版 计 算 机 应 用 研 究 第33 卷从图2 中曲线可知，随着k 值增加，分类准确率总体呈下降趋势，这是因为簇内样本已经具有了很高的相似性，如果k值的选取过大，且待分类样本又属于训练集中包含数较少的类，那么在选择k 个最近邻时，实际上并不相似的数据就会被包含进来，从而造成噪声而导致分类效果的降低，同时也增加了KNN 算法的计算量。因此，在分类准确率保持较高的情况下，k 值的选取应尽可能小。根据图2 表示，本文算法在satimage数据集上k=3 时可以取到0.8986，高于k=1 时的准确率，但是在k=1 时，本文算法的实验结果就已经优于KNN。因此，本文统一选取k=1。2.3 三种算法的性能比较本次实验在分块(簇)数m=10，k=1 的情况下，以准确率和时间为评价指标，对3 种算法进行的对比实验，实验结果如下表2 所示：表8 三种算法的性能比较No. 随机分块KNN 基于聚类的KNN 经典KNNcorrect time correct time correct time1 0.9027 3.5589 0.9355 3.7605 0.9482 32.87642 0.7221 2.9369 0.8389 3.5504 0.8635 24.15753 0.9311 23.3933 0.9526 28.594 0.9660 217.33274 0.7892 3.2391 0.9495 3.2994 0.9518 19.82465 0.9452 2.3380 0.9721 2.4056 0.9780 7.29826 0.8603 1.2868 0.8883 1.3027 0.9065 3.5525由于改进算法为近似算法，因此通过表8 可以看出，该算法分类准确率低于经典KNN 算法1%~2.4%，但是样本数据足够大时，分类的速度接近于经典KNN 算法的7~9 倍(接近分块数)。而随机分块算法虽然分类速度略高于本文算法，但分类准确率较低。因此，通过上述实验可知，使用基于LSC 聚类的KNN 改进算法，能在保持分类准确率较高的情况下，大幅度提高分类的速度，使其能够在大数据中得到应用。3 结束语本文针对经典KNN 算法难以在大数据样本中应用的问题，提出了一种基于LSC 聚类的KNN 改进算法。该算法针对KNN没有训练过程的特点，创新的引入了一个训练过程，即通过聚类技术找出了远小于原始样本集的新的训练样本集，极大的减少了KNN算法的计算量，使其能够在大数据空间(内存)中运行，并且该算法能够保持较高的分类准确率。但是本文算法仍有一些地方需要改进，如新的训练集用于KNN 分类时，其分类准确率的高低依赖于聚类的效果，如果聚类的效果较好，那么改进算法的分类准确率将完全有可能超过经典算法。参考文献:[1] Zhang Shichao. KNN-CF Approach: incorporating certainty factor tokNN classification[J]. IEEE Intelligent Informatics Bulletin, 2010, 11(1):24-33.[2] Zhang Shichao, Zhang Chengqi, Yan Xiaowei. Post-mining: maintenanceof association rules by weighting[J]. Information Systems, 2003, 28(7):691-707.[3] 李荣陆, 胡运发. 基于密度的KNN 文本分类器训练样本裁剪方法[J].计算机研究与发展, 2004, 41(4): 539-545.[4] 张孝飞, 黄河燕. 一种采用聚类技术改进的KNN文本分类方法[J]. 模式识别与人工智能, 2009, 22(6): 936-940.[5] 李杨, 曾海泉, 刘庆华, 胡运发. 基于KNN 的快速Web 文档分类[J].小型微型计算机系统, 2004, 25(4): 725-728.[6] Zhu Xiaofeng, Huang Zi, Yang Yang, et al. Self-taught dimensionalityreduction on the high-dimensional small-sized data[J]. PatternRecognition, 2013, 46(1): 215-229.[7] Zhu Xiaofeng, Huang Zi, Cui Jiangtao, et al. Video-to-shot tagpropagation by graph sparse group Lasso[J]. IEEE Trans on Multimedia,2013, 15(3): 633-646.[8] Zhu Xiaofeng, Huang Zi, Cheng Hong, et al. Sparse hashing for fastmultimedia search[J]. ACM Trans on Information Systems, 2013, 31(2):9.[9] Zhu Xiaofeng, Huang Zi, Shen Hengtao, et al. Dimensionality reductionby mixed kernel canonical correlation analysis[J]. Pattern Recognition,2012, 45(8): 3003-3016.[10] Zhu Xiaofeng, Zhang Shichao, Jin Zhi, et al. Missing value estimation formixed-attribute data sets[J]. IEEE Trans on Knowledge DataEngineering, 2011, 23(1): 110-121.[11] Zhao Yanchang, Zhang Shichao. Generalized dimension-reductionframework for recent-biased time series analysis[J]. IEEE Trans onKnowledge and Data Engineering, 2006, 18(2): 231-244.[12] Qin Yongsong, Zhang Shichao, Zhu Xiaofeng, et al. Semi-parametricoptimization for missing data imputation[J]. Applied Intelligence, 2007,27(1): 79-88.[13] Wu Xindong, Zhang Shicao. Synthesizing high-frequency rules fromdifferent data sources[J]. IEEE Trans on Knowledge and DateEngineering, 2003, 15(2): 353-367.[14] Zhang Tian, Ramakrishnan R, Livny M. BIRCH: an efficient dataclustering method for very large databases[C]//SIGMOD Conference.1996: 103-114.[15] Ester M, Kriegel H-P, Sander J, et al. A density-based algorithm fordiscovering clusters in large spatial databases with noise[C]// KDD. 1996:274-287.[16] Ng A Y, Jordan M I, Weiss Y. On spectral clustering: analysis and analgorithm[M]//Advance in Neural Information Processing Systems 14. [S.l. ]: MIT Press, 2002.[17] Filippone M, Camastra F, Masulli F, et al. A survey of kernel and spectralmethods for clustering[J]. Pattern Recognition, 2007, 41(1): 176-190.[18] Chen Xinlei, Cai Deng. Large scale spectral clustering withlandmark-based representation[C]// Proc of the 25th AAAI Conference onArtificial Intelligence. [S. l. ]: AAAI, 2011: 313-318.优先出版 计 算 机 应 用 研 究 第33 卷[19] Zhu Xiaofeng, Zhang Lei, Huang Zi. A sparse embedding and leastvariance encoding approach to hashing[J]. IEEE Trans on ImageProcessing, 2014, 23(9): 3737-3750.[20] Zhu Xiaofeng, Suk Heung-II, Shen Dinggang. A novel matrix-similaritybased loss function for joint regression and classification in ADdiagnosis[J]. NeuroImage, 2014, 100: 91-105.[21] Liu Wei, He Junfeng, Chang Shihfu. Large graph construction for scalablesemi-supervised learning[C]// Proc of the 27th International Conferenceon Machine Learning. 2010.[22] Wu Xindong, Zhang Chengqi, Zhang Shichao. Efficient mining of bothpositive and negative association rules[J]. ACM Trans on InformationSystems, 2004, 22(3): 381-405.[23] Zhang Shichao, Qin Zhenxing, Ling C X, et al. "Missing Is Useful':missing values in cost-sensitive decision trees[J]. IEEE Trans onKnowledge and Data Engineering, 2005, 17(12): 1689-1693.[24] Lall U, Sharma A. A nearest neighbor bootstrap for resampling hydrologictime series[J]. Water Resource Research, 1996, 32: 679-693.