吉成恒，雷詠梅（上海大學計算機工程與科學學院，上海200444）

大規(guī)模數(shù)據集聚類的K鄰近均勻抽樣數(shù)據預處理算法

吉成恒，雷詠梅
（上海大學計算機工程與科學學院，上海200444）

為解決基于密度的聚類算法處理大規(guī)模數(shù)據集效率低和存儲開銷大的問題，提出一種分片的基于K鄰近關系的空間均勻抽樣算法作為聚類應用的數(shù)據預處理過程，將數(shù)據集分片，按密度降序方式去除數(shù)據集中部分樣本的K鄰居，將剩余樣本作為抽樣樣本，在保證精度的同時，可以降低數(shù)據規(guī)模，提升計算效率.實驗結果表明，在數(shù)據規(guī)模較大且保證聚類結果準確性的前提下，通過降低聚類數(shù)據規(guī)模，可以有效提升聚類效率.

密度降序；K鄰近；空間均勻抽樣；聚類

在聚類問題［1-2］中，基于密度的聚類算法［3-4］如DBSCAN［5］，CFSDP［6］等，由于能夠發(fā)現(xiàn)任意形狀類簇而成為一類十分有效的算法.在基于密度的聚類算法中，距離計算的時間和空間復雜度都為o（n2），當處理數(shù)據量巨大、價值密度低的大規(guī)模數(shù)據集聚類需求時，這類算法都會面臨存儲受限和效率低的問題.針對該類問題，可以從原數(shù)據中選取合適的子集進行聚類，從子集中找到每個類，然后將剩余樣本歸類，從而降低數(shù)據規(guī)模，緩解存儲壓力，以提高聚類效率.本研究提出一種數(shù)據抽樣算法，所構造的子集可以保證對原數(shù)據集聚類結果的準確性.通過采用密度降序的方式對原數(shù)據集進行抽樣的預處理，并將K鄰近思想與抽樣過程相結合，一方面保證了抽樣子集能夠有效代表原數(shù)據集，另一方面保證了對未被抽樣數(shù)據集可以進行準確歸類.本研究還提出一種分片處理的策略，在保證聚類結果準確性的前提下，既加快抽樣速度，同時具有可擴展性，易于大規(guī)模并行實現(xiàn).針對大規(guī)模數(shù)據聚類問題，本研究通過構建一種抽樣處理再合并結果的流程，提高了算法效率，為處理大數(shù)據的基于密度的聚類問題提供了一類有效的算法模型.

1　抽樣聚類相關定義和性質

關于抽樣聚類算法，文獻［7］提出一種改進的基于密度的聚類算法，但是其抽樣過程與DBSCAN算法綁定，不具有可移植性.文獻［8］提出一種基于隨機抽樣的聚類算法，其抽樣過程采用一種隨機算法.文獻［9］介紹了一種基于樣本的分層自適應k-均值（sample-based hierarchical adaptive k-means，SHAKM）大型視頻檢索的聚類算法，為了能夠高效處理大型數(shù)據庫，SHAKM采用多級隨機抽樣策略.為了使數(shù)據抽樣可以作為大數(shù)據聚類分析乃至其他應用的數(shù)據預處理的一種普遍適用方法，本研究將給出一種與具體聚類算法相互獨立的非隨機抽樣算法，可以應用于其他聚類算法的數(shù)據預處理過程.

為便于描述，對于給定的n維空間數(shù)據集S=｛xi|xi∈R2，i=1，2，···，N｝和參數(shù)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抽樣聚類的效率

對于給定數(shù)據集S，對S進行抽樣聚類分如下3個步驟：

（1）對S進行抽樣獲得抽樣子集S′=｛xi|xi∈Rn，i=1，2，···，N′｝；

（2）對S′進行聚類；

（3）對非抽樣子集S-S′中所有樣本進行歸類.

評價抽樣聚類的性能主要從兩個方面出發(fā)：效率和準確性.要保證抽樣聚類能夠提高聚類的效率，則抽樣聚類算法應滿足如下性質.

性質1對于相同聚類算法，令t1，t2，t3分別表示抽樣聚類的3個步驟的執(zhí)行時間，令t表示直接聚類的執(zhí)行時間，在聚類算法相同的條件下，t1+t2+t3＜t成立.

1.2K鄰近思想

K鄰近思想來源于K鄰近算法［10］，可以描述為如下合理假設：對于一個樣本，其周圍前K個與其最鄰近的樣本與該樣本同屬一類.一般而言，隨著數(shù)據規(guī)模的增大，使該假設合理的K的取值范圍也越大.本研究所闡述的數(shù)據抽樣方法以該假設為前提，對于非抽樣子集依據K鄰近一致性進行歸類.

2　密度降序空間均勻抽樣算法

2.1算法設計思想

對空間數(shù)據集進行聚類時，如果原數(shù)據集所在空間的某個局部空間中的樣本分布越多，則該局部空間中的樣本密度越高，在聚類時被選作聚類中心的可能性越大.因此，要通過抽樣聚類，必須從原數(shù)據所在空間的各個局部進行均勻采樣，從而對于抽樣子集和原數(shù)據集，二者分布的空間一致，并且對于相同的局部子空間，樣本的疏密程度一致.只有這樣，抽樣子集才能夠有效代表原數(shù)據集，保證對抽樣子集聚類結果的正確性.

根據局部密度ρ的定義，對于一個類，由其中心向邊緣發(fā)散，類中樣本的密度呈下降趨勢. DBSCAN算法就采用了從密度較高的核心對象出發(fā)，向非核心樣本探測，從而發(fā)現(xiàn)類的做法.因此，如果通過密度下降的順序遍歷整個數(shù)據集，從空間上來看，就相當于從各個類的中心出發(fā)，依照廣度優(yōu)先的順序，遍歷了整個數(shù)據集所在的空間.只要在這一遍歷的過程中對各個局部進行同比例采樣，使抽樣過程盡可能均勻，那么就可以保證獲得的抽樣子集能有效代表原數(shù)據集的分布.

2.2密度降序空間均勻抽樣及準確性分析

本研究將密度降序遍歷和K鄰近思想相結合，得到K鄰近均勻抽樣算法，即通過密度降序遍歷數(shù)據集的同時，對于每一個遍歷到的樣本，將所有K鄰近樣本中密度比該樣本小的樣本從數(shù)據集中刪除，最后通過保留未被刪除樣本的方式得到抽樣數(shù)據集.所提出算法的主要流程如圖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）按照密度降序遍歷整個數(shù)據集，對于數(shù)據集所在空間的每一個局部空間都進行了處理，不存在遺漏.

（2）對每個被遍歷的樣本，其周圍被刪除的樣本數(shù)都遵循同一上限K.因此可以認為對于每個局部空間的采樣都使用了同樣的比例上限.

（3）對每個被遍歷的樣本，其K鄰近樣本中只刪除密度比該樣本小的樣本，因此對于某個局部空間中的樣本互為K鄰近樣本的情況，不會將整個局部空間的樣本都刪除.因此可以認為對于每個局部空間的采樣都使用了同樣的比例下限.

通過以上分析可以合理推斷，通過該抽樣方法獲得的抽樣子集能夠有效代表原數(shù)據集分布，滿足了抽樣聚類對抽樣子集選取的前提條件.

2.3數(shù)據集分片策略

在上述抽樣過程中，對于數(shù)據集S，由于要計算每個樣本的密度，仍然需要先計算距離矩陣，時間和空間開銷為N2.為了處理大規(guī)模數(shù)據集，本研究提出一種對數(shù)據集進行分片處理再合并的策略.

采用分片策略的抽樣算法先將原數(shù)據集按照空間的任意一維的大小進行排序，然后將排序好的數(shù)據集按照給定的分片數(shù)P進行等量劃分，從而使每個分片只包含數(shù)據集所在空間某一子空間中的所有樣本.對于該子空間邊界部分的樣本，其密度計算還依賴于該子空間相鄰空間中的部分樣本.因此，在分片策略中引入邊界寬度參數(shù)θ，對于每個分片，根據給定的θ保留邊界.θ可以是固定的距離寬度，還可以是指定的數(shù)據量大小.

分片策略合理性的依據在于：①根據樣本局部密度的定義，對于每個樣本的局部密度，只需根據其周圍局部范圍內的樣本共同計算即可得到；②在對每個局部空間的抽樣過程中，只需要根據該局部空間內樣本的密度和距離關系就可以進行，除了固定參數(shù)K之外，沒有任何全局因素能夠影響該過程.

采用分片的抽樣算法，對于距離矩陣的存儲和計算開銷均由之前的N2降至

其中P為分片數(shù)，N為原數(shù)據集大小，θ為邊界樣本數(shù).由于分片之間沒有互通信過程，分片數(shù)也沒有限制，因此解決了抽樣算法的可擴展問題，且易于多處理器并行實現(xiàn).

3　數(shù)據分片的空間均勻抽樣算法步驟

對于給定的空間數(shù)據集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鄰近樣本從原數(shù)據集中被刪除的.空間均勻抽樣算法總體分為4步，具體如下.

設定抽樣參數(shù)：數(shù)據劃分份數(shù)為p，抽樣系數(shù)為K，數(shù)據邊界寬度為θ.

Step 1預處理

（1）將原數(shù)據集S中所有數(shù)據按照任意S所在空間任意一維dim的大小進行排序，得到排序后的樣本集L.

Step 2數(shù)據分片

（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）新建抽樣數(shù)據集S′，依次遍歷Li，i=1，2，···，p，將Li中所有樣本添加到S′.

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

通過上述步驟，使得非抽樣映射表M準確記錄了每個未被抽樣的樣本與抽樣集中樣本的K鄰近對應關系.要對數(shù)據集S進行聚類，只需對規(guī)模較小的S′進行聚類，然后利用映射表M將S-S′進行歸類.下節(jié)將采用該方法結合具體聚類算法對空間數(shù)據集進行抽樣聚類實驗，驗證性質1以及聚類的準確性.

4　實驗及結果分析

為了比較采用K鄰近均勻抽樣算法對數(shù)據作預處理以進行抽樣聚類與直接對原數(shù)據集聚類這兩種方法在效率和準確性兩個方面的差別，本研究選用CFSDP（clustering by fast search and find of density peaks）算法作為實驗測試中的聚類算法.CFSDP算法由Rodriguez等［6］提出，是一種新型的基于密度的聚類算法，具有快速無迭代、抗噪音能力強等優(yōu)點.

實驗環(huán)境所采用的電腦基本配置情況如下：Intel（R）Core（TM）i5-2400處理器，8 GB DDR3內存，Windows8.1x64操作系統(tǒng).

4.1效率及準確性對比實驗

采用多組大小和分布不同的人工測試數(shù)據集，在保持聚類過程參數(shù)不變以及結果準確性觀測可靠的前提下，測得通過抽樣聚類和直接聚類的執(zhí)行時間對比如表1所示.可以發(fā)現(xiàn)，對于同等規(guī)模數(shù)據，采用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不同參數(shù)對抽樣效率影響的測試

同樣在保證聚類結果準確性的前提下，對不同數(shù)據集，測試聚類時間分別與抽樣系數(shù)K和分片數(shù)P之間的關系，實驗結果如圖5所示.

圖5　執(zhí)行時間t與K和P的關系Fig.5　Relation schemas of K-t and P-t

對于固定數(shù)據規(guī)模，由圖5（a）可知，K在一定范圍內增大會使聚類時間縮短，加速程度隨K值增大而減弱；由圖5（b）可知，聚類時間先隨P增大而縮短，達到最優(yōu)值后，P繼續(xù)增大會導致聚類時間延長.

5　結束語

本研究設計了一種基于K鄰近思想的均勻抽樣算法，由于采取了密度降序的抽樣方式且抽樣過程遵循K鄰近一致性，因此保證了抽樣結果具有良好的代表性；同時，利用分片處理策略，大幅提高了抽樣效率，并具有良好的擴展性和健壯性.經實驗驗證，將所提出抽樣算法作為數(shù)據預處理方法應用于聚類算法中，使聚類效率得到大幅提升，同時有效保證了聚類結果的準確性.作為一種獨立于具體應用的抽樣算法，本算法可以應用于很多大數(shù)據應用的數(shù)據預處理過程，具有較大的現(xiàn)實意義和應用價值.

［1］JAIN A K，MURTY M N，F(xiàn)LYNN 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—），女，教授，博士生導師，博士，研究方向為高性能計算、大數(shù)據處理等. E-mail:lei@shu.edu.cn