大规模数据集聚类的K邻近均匀抽样数据预处理算法

吉成恒，雷咏梅（上海大学计算机工程与科学学院，上海200444）

大规模数据集聚类的K邻近均匀抽样数据预处理算法

吉成恒，雷咏梅
（上海大学计算机工程与科学学院，上海200444）

为解决基于密度的聚类算法处理大规模数据集效率低和存储开销大的问题，提出一种分片的基于K邻近关系的空间均匀抽样算法作为聚类应用的数据预处理过程，将数据集分片，按密度降序方式去除数据集中部分样本的K邻居，将剩余样本作为抽样样本，在保证精度的同时，可以降低数据规模，提升计算效率.实验结果表明，在数据规模较大且保证聚类结果准确性的前提下，通过降低聚类数据规模，可以有效提升聚类效率.

密度降序；K邻近；空间均匀抽样；聚类

在聚类问题［1-2］中，基于密度的聚类算法［3-4］如DBSCAN［5］，CFSDP［6］等，由于能够发现任意形状类簇而成为一类十分有效的算法.在基于密度的聚类算法中，距离计算的时间和空间复杂度都为o（n2），当处理数据量巨大、价值密度低的大规模数据集聚类需求时，这类算法都会面临存储受限和效率低的问题.针对该类问题，可以从原数据中选取合适的子集进行聚类，从子集中找到每个类，然后将剩余样本归类，从而降低数据规模，缓解存储压力，以提高聚类效率.本研究提出一种数据抽样算法，所构造的子集可以保证对原数据集聚类结果的准确性.通过采用密度降序的方式对原数据集进行抽样的预处理，并将K邻近思想与抽样过程相结合，一方面保证了抽样子集能够有效代表原数据集，另一方面保证了对未被抽样数据集可以进行准确归类.本研究还提出一种分片处理的策略，在保证聚类结果准确性的前提下，既加快抽样速度，同时具有可扩展性，易于大规模并行实现.针对大规模数据聚类问题，本研究通过构建一种抽样处理再合并结果的流程，提高了算法效率，为处理大数据的基于密度的聚类问题提供了一类有效的算法模型.

1　抽样聚类相关定义和性质

关于抽样聚类算法，文献［7］提出一种改进的基于密度的聚类算法，但是其抽样过程与DBSCAN算法绑定，不具有可移植性.文献［8］提出一种基于随机抽样的聚类算法，其抽样过程采用一种随机算法.文献［9］介绍了一种基于样本的分层自适应k-均值（sample-based hierarchical adaptive k-means，SHAKM）大型视频检索的聚类算法，为了能够高效处理大型数据库，SHAKM采用多级随机抽样策略.为了使数据抽样可以作为大数据聚类分析乃至其他应用的数据预处理的一种普遍适用方法，本研究将给出一种与具体聚类算法相互独立的非随机抽样算法，可以应用于其他聚类算法的数据预处理过程.

为便于描述，对于给定的n维空间数据集S=｛xi|xi∈R2，i=1，2，···，N｝和参数K，先作如下定义.

定义1xi，xj的距离dij.距离是用于量化样本间相似度的量，距离越大，表示两个点越不相似.距离的种类很多， 本研究采用欧式距离：

定义2K邻近样本.对S中任意xi，KNNxi表示S中离xi最近的前K个样本.

定义3K邻近一致性.对任意xi∈S，若xi属于类Cp，那么对任意xj∈KNNxi，xj属于类Cp.

定义4xi的局部密度ρi.局部密度用于描述样本周围空间中样本的密集程度，密度的计算方式有很多，本研究采用K邻近方式：

1.1抽样聚类的效率

对于给定数据集S，对S进行抽样聚类分如下3个步骤：

（1）对S进行抽样获得抽样子集S′=｛xi|xi∈Rn，i=1，2，···，N′｝；

（2）对S′进行聚类；

（3）对非抽样子集S-S′中所有样本进行归类.

评价抽样聚类的性能主要从两个方面出发：效率和准确性.要保证抽样聚类能够提高聚类的效率，则抽样聚类算法应满足如下性质.

性质1对于相同聚类算法，令t1，t2，t3分别表示抽样聚类的3个步骤的执行时间，令t表示直接聚类的执行时间，在聚类算法相同的条件下，t1+t2+t3＜t成立.

1.2K邻近思想

K邻近思想来源于K邻近算法［10］，可以描述为如下合理假设：对于一个样本，其周围前K个与其最邻近的样本与该样本同属一类.一般而言，随着数据规模的增大，使该假设合理的K的取值范围也越大.本研究所阐述的数据抽样方法以该假设为前提，对于非抽样子集依据K邻近一致性进行归类.

2　密度降序空间均匀抽样算法

2.1算法设计思想

对空间数据集进行聚类时，如果原数据集所在空间的某个局部空间中的样本分布越多，则该局部空间中的样本密度越高，在聚类时被选作聚类中心的可能性越大.因此，要通过抽样聚类，必须从原数据所在空间的各个局部进行均匀采样，从而对于抽样子集和原数据集，二者分布的空间一致，并且对于相同的局部子空间，样本的疏密程度一致.只有这样，抽样子集才能够有效代表原数据集，保证对抽样子集聚类结果的正确性.

根据局部密度ρ的定义，对于一个类，由其中心向边缘发散，类中样本的密度呈下降趋势. DBSCAN算法就采用了从密度较高的核心对象出发，向非核心样本探测，从而发现类的做法.因此，如果通过密度下降的顺序遍历整个数据集，从空间上来看，就相当于从各个类的中心出发，依照广度优先的顺序，遍历了整个数据集所在的空间.只要在这一遍历的过程中对各个局部进行同比例采样，使抽样过程尽可能均匀，那么就可以保证获得的抽样子集能有效代表原数据集的分布.

2.2密度降序空间均匀抽样及准确性分析

本研究将密度降序遍历和K邻近思想相结合，得到K邻近均匀抽样算法，即通过密度降序遍历数据集的同时，对于每一个遍历到的样本，将所有K邻近样本中密度比该样本小的样本从数据集中删除，最后通过保留未被删除样本的方式得到抽样数据集.所提出算法的主要流程如图1所示.

图1　空间均匀抽样流程Fig.1　Flowchart of spatial even sampling

为直观起见，图2给出了密度降序空间均匀抽样算法在一维（K=1）情况下的一个简单模型.在图2中，设类Cp由一组分布在（0，3）中的样本组成，且沿坐标正向Cp中的样本密度递减，当K=1时，按图1流程进行抽样.可以合理推测，该类中的样本在聚类过程中依然会被判别为一类.

图2　一维（K=1）情况下的空间均匀抽样模型Fig.2　Model of spatial even sampling in one dimensional space with K=1

对于密度降序抽样方法，可从以下3个方面分析其准确性.

（1）按照密度降序遍历整个数据集，对于数据集所在空间的每一个局部空间都进行了处理，不存在遗漏.

（2）对每个被遍历的样本，其周围被删除的样本数都遵循同一上限K.因此可以认为对于每个局部空间的采样都使用了同样的比例上限.

（3）对每个被遍历的样本，其K邻近样本中只删除密度比该样本小的样本，因此对于某个局部空间中的样本互为K邻近样本的情况，不会将整个局部空间的样本都删除.因此可以认为对于每个局部空间的采样都使用了同样的比例下限.

通过以上分析可以合理推断，通过该抽样方法获得的抽样子集能够有效代表原数据集分布，满足了抽样聚类对抽样子集选取的前提条件.

2.3数据集分片策略

在上述抽样过程中，对于数据集S，由于要计算每个样本的密度，仍然需要先计算距离矩阵，时间和空间开销为N2.为了处理大规模数据集，本研究提出一种对数据集进行分片处理再合并的策略.

采用分片策略的抽样算法先将原数据集按照空间的任意一维的大小进行排序，然后将排序好的数据集按照给定的分片数P进行等量划分，从而使每个分片只包含数据集所在空间某一子空间中的所有样本.对于该子空间边界部分的样本，其密度计算还依赖于该子空间相邻空间中的部分样本.因此，在分片策略中引入边界宽度参数θ，对于每个分片，根据给定的θ保留边界.θ可以是固定的距离宽度，还可以是指定的数据量大小.

分片策略合理性的依据在于：①根据样本局部密度的定义，对于每个样本的局部密度，只需根据其周围局部范围内的样本共同计算即可得到；②在对每个局部空间的抽样过程中，只需要根据该局部空间内样本的密度和距离关系就可以进行，除了固定参数K之外，没有任何全局因素能够影响该过程.

采用分片的抽样算法，对于距离矩阵的存储和计算开销均由之前的N2降至

其中P为分片数，N为原数据集大小，θ为边界样本数.由于分片之间没有互通信过程，分片数也没有限制，因此解决了抽样算法的可扩展问题，且易于多处理器并行实现.

3　数据分片的空间均匀抽样算法步骤

对于给定的空间数据集S=｛xi|xi∈Rn，i=1，2，···，N｝，通过空间均匀抽样算法进行预处理，将输出抽样子集S′=｛xi|xi∈Rn，i=1，2，···，N′｝，以及非抽样映射表M=｛xp：xq|xp∈（S-S′）and xq∈S′，p=1，2，···，N-N′｝，其中xp：xq表示xp是作为xq的K邻近样本从原数据集中被删除的.空间均匀抽样算法总体分为4步，具体如下.

设定抽样参数：数据划分份数为p，抽样系数为K，数据边界宽度为θ.

Step 1预处理

（1）将原数据集S中所有数据按照任意S所在空间任意一维dim的大小进行排序，得到排序后的样本集L.

Step 2数据分片

（2）按顺序将L等量划分为p个子样本集Li，i=1，2，···，p.

（3）对Li进行边界保留，将Li的dim维边界外宽度为θ范围内的样本从L复制到Li中，并标记为Li的边界样本.

Step 3分片抽样

（4）对每个子样本集Li，新建局部非抽样映射表Mi.

（5）采用式（1）计算Li中所有样本两两之间的距离，得到距离矩阵DMi.

（6）遍历Li，由DMi计算Li中所有样本的K邻近样本.

（7）遍历Li，由式（2）计算Li中所有样本的局部密度，得到.

①若是，将xqj从Li中删除.

②若否，则遍历KNNqj，将其中所有密度小于xqj的非边界样本xp从Li中删除，并将映射xp：xqj添加到Mi.

Step 4抽样合并

（10）新建抽样数据集S′，依次遍历Li，i=1，2，···，p，将Li中所有样本添加到S′.

（11）新建非抽样映射表M，依次遍历Mi，i=1，2，···，p，将Mi中所有映射添加到M.

通过上述步骤，使得非抽样映射表M准确记录了每个未被抽样的样本与抽样集中样本的K邻近对应关系.要对数据集S进行聚类，只需对规模较小的S′进行聚类，然后利用映射表M将S-S′进行归类.下节将采用该方法结合具体聚类算法对空间数据集进行抽样聚类实验，验证性质1以及聚类的准确性.

4　实验及结果分析

为了比较采用K邻近均匀抽样算法对数据作预处理以进行抽样聚类与直接对原数据集聚类这两种方法在效率和准确性两个方面的差别，本研究选用CFSDP（clustering by fast search and find of density peaks）算法作为实验测试中的聚类算法.CFSDP算法由Rodriguez等［6］提出，是一种新型的基于密度的聚类算法，具有快速无迭代、抗噪音能力强等优点.

实验环境所采用的电脑基本配置情况如下：Intel（R）Core（TM）i5-2400处理器，8 GB DDR3内存，Windows8.1x64操作系统.

4.1效率及准确性对比实验

采用多组大小和分布不同的人工测试数据集，在保持聚类过程参数不变以及结果准确性观测可靠的前提下，测得通过抽样聚类和直接聚类的执行时间对比如表1所示.可以发现，对于同等规模数据，采用CFSDP算法进行抽样聚类的加速效果非常明显，因此性质1成立.

表1　聚类时间比较Table 1　Clustering time comparison

图3和4分别为K=10，N=15 760和K=8，N=12 800情况下，抽样聚类和直接聚类结果的准确性比较.

图3　抽样聚类和直接聚类结果准确性比较（K=10，N=15 760）Fig.3　Comparison of clustering accuracy between sampling-clustering and direct clustering （K=10，N=15 760）

图4　抽样聚类和直接聚类结果准确性比较（K=8，N=12 800）Fig.4　Comparison of clustering accuracy between sampling-clustering and direct clustering （K=8，N=12 800）

4.2不同参数对抽样效率影响的测试

同样在保证聚类结果准确性的前提下，对不同数据集，测试聚类时间分别与抽样系数K和分片数P之间的关系，实验结果如图5所示.

图5　执行时间t与K和P的关系Fig.5　Relation schemas of K-t and P-t

对于固定数据规模，由图5（a）可知，K在一定范围内增大会使聚类时间缩短，加速程度随K值增大而减弱；由图5（b）可知，聚类时间先随P增大而缩短，达到最优值后，P继续增大会导致聚类时间延长.

5　结束语

本研究设计了一种基于K邻近思想的均匀抽样算法，由于采取了密度降序的抽样方式且抽样过程遵循K邻近一致性，因此保证了抽样结果具有良好的代表性；同时，利用分片处理策略，大幅提高了抽样效率，并具有良好的扩展性和健壮性.经实验验证，将所提出抽样算法作为数据预处理方法应用于聚类算法中，使聚类效率得到大幅提升，同时有效保证了聚类结果的准确性.作为一种独立于具体应用的抽样算法，本算法可以应用于很多大数据应用的数据预处理过程，具有较大的现实意义和应用价值.

［1］JAIN A K，MURTY M N，FLYNN P J.Data clustering：a review［J］.ACM Computing Surveys，1999，31（2）：264-323.

［2］孙吉贵，刘杰，赵连宇.聚类算法研究［J］.软件学报，2008，19（1）：48-61.

［3］KRIEGEL H P，KR¨OGER P，SER J，et al.Density-based clustering［J］.Wiley Interdisciplinary Reviews：Data Mining and Knowledge Discovery，2011，1（3）：231-240.

［4］SAKAI T，TAMURA K，KITAKAMI H.A new density-based spatial clustering algorithm for extracting attractive local regions in georeferenced documents［J］.Lecture Notes in Engineering and Computer Science，2014，2209（1）：360-365.

［5］ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise［C］//Proceedings 2nd International Conference on Knowledge Discovery and Data Mining.1996：226-231.

［6］RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks［J］.Science，2014，344（6191）：1492-1496.

［7］胡彩平，秦小麟.一种改进的基于密度的抽样聚类算法［J］.中国图象图形学报，2007（11）：2031-2036.

［8］周兵，沈钧毅，彭勤科.基于随机抽样和聚类特征的聚类算法［J］.西安交通大学学报，2003（12）：1234-1237.

［9］LIAO K，LIU G，XIAO L，et al.A sample-based hierarchical adaptive K-means clustering method for large-scale video retrieval［J］.Knowledge-Based Systems，2013，49：123-133.

［10］HASTIE T，TIBSHIRANI R.Discriminant adaptive nearest neighbor classification［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18（6）：607-616.

KNN-based even sampling preprocessing algorithm for big dataset

JI Chengheng，LEI Yongmei
（School of Computer Engineering and Science，Shanghai University，Shanghai 200444，China）

To solve the problem of low efficiency and high storage overheads in densitybased clustering algorithms，an algorithm of even data sampling based on K nearest neighbors（KNN）is proposed as a data preprocessing method of clustering applications.The sampling algorithm slices dataset and gets samples evenly.After slicing a dataset，for part of the samples，the algorithm removes each sample's K nearest neighbors in a descending order according to the density.The remaining samples are then used as the sample dataset. Experimental results show that，with the increase of data size and the guaranteed accuracy，the sampling algorithm can effectively improve efficiency of clustering by reducing the amount of data needed in clustering.

density descending order；K nearest neighbors（KNN）；spatial even sampling；clustering

TP 391

A

1007-2861（2016）01-0028-08

10.3969/j.issn.1007-2861.2015.04.020

2015-11-20

上海市教委重点学科资助项目（12ZZ09）；上海市科委资助项目（13DZ118800）

雷咏梅（1965—），女，教授，博士生导师，博士，研究方向为高性能计算、大数据处理等. E-mail:lei@shu.edu.cn