吉成恒，雷詠梅（上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院，上海200444）

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

吉成恒，雷詠梅
（上海大學(xué)計算機(jī)工程與科學(xué)學(xué)院，上海200444）

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

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

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

1　抽樣聚類相關(guān)定義和性質(zhì)

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

為便于描述，對于給定的n維空間數(shù)據(jù)集S=｛xi|xi∈R2，i=1，2，···，N｝和參數(shù)K，先作如下定義.

定義1xi，xj的距離dij.距離是用于量化樣本間相似度的量，距離越大，表示兩個點(diǎn)越不相似.距離的種類很多， 本研究采用歐式距離：

定義2K鄰近樣本.對S中任意xi，KNNxi表示S中離xi最近的前K個樣本.

定義3K鄰近一致性.對任意xi∈S，若xi屬于類Cp，那么對任意xj∈KNNxi，xj屬于類Cp.

定義4xi的局部密度ρi.局部密度用于描述樣本周圍空間中樣本的密集程度，密度的計算方式有很多，本研究采用K鄰近方式：

1.1抽樣聚類的效率

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

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

（2）對S′進(jìn)行聚類；

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

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

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

1.2K鄰近思想

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

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

2.1算法設(shè)計思想

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

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

2.2密度降序空間均勻抽樣及準(zhǔn)確性分析

本研究將密度降序遍歷和K鄰近思想相結(jié)合，得到K鄰近均勻抽樣算法，即通過密度降序遍歷數(shù)據(jù)集的同時，對于每一個遍歷到的樣本，將所有K鄰近樣本中密度比該樣本小的樣本從數(shù)據(jù)集中刪除，最后通過保留未被刪除樣本的方式得到抽樣數(shù)據(jù)集.所提出算法的主要流程如圖1所示.

圖1　空間均勻抽樣流程Fig.1　Flowchart of spatial even sampling

為直觀起見，圖2給出了密度降序空間均勻抽樣算法在一維（K=1）情況下的一個簡單模型.在圖2中，設(shè)類Cp由一組分布在（0，3）中的樣本組成，且沿坐標(biāo)正向Cp中的樣本密度遞減，當(dāng)K=1時，按圖1流程進(jìn)行抽樣.可以合理推測，該類中的樣本在聚類過程中依然會被判別為一類.

圖2　一維（K=1）情況下的空間均勻抽樣模型Fig.2　Model of spatial even sampling in one dimensional space with K=1

對于密度降序抽樣方法，可從以下3個方面分析其準(zhǔn)確性.

（1）按照密度降序遍歷整個數(shù)據(jù)集，對于數(shù)據(jù)集所在空間的每一個局部空間都進(jìn)行了處理，不存在遺漏.

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

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

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

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

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

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

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

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

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

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

對于給定的空間數(shù)據(jù)集S=｛xi|xi∈Rn，i=1，2，···，N｝，通過空間均勻抽樣算法進(jìn)行預(yù)處理，將輸出抽樣子集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ù)據(jù)集中被刪除的.空間均勻抽樣算法總體分為4步，具體如下.

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

Step 1預(yù)處理

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

Step 2數(shù)據(jù)分片

（2）按順序?qū)等量劃分為p個子樣本集Li，i=1，2，···，p.

（3）對Li進(jìn)行邊界保留，將Li的dim維邊界外寬度為θ范圍內(nèi)的樣本從L復(fù)制到Li中，并標(biāo)記為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ù)據(jù)集S′，依次遍歷Li，i=1，2，···，p，將Li中所有樣本添加到S′.

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

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

4　實驗及結(jié)果分析

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

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

4.1效率及準(zhǔn)確性對比實驗

采用多組大小和分布不同的人工測試數(shù)據(jù)集，在保持聚類過程參數(shù)不變以及結(jié)果準(zhǔn)確性觀測可靠的前提下，測得通過抽樣聚類和直接聚類的執(zhí)行時間對比如表1所示.可以發(fā)現(xiàn)，對于同等規(guī)模數(shù)據(jù)，采用CFSDP算法進(jìn)行抽樣聚類的加速效果非常明顯，因此性質(zhì)1成立.

表1　聚類時間比較Table 1　Clustering time comparison

圖3和4分別為K=10，N=15 760和K=8，N=12 800情況下，抽樣聚類和直接聚類結(jié)果的準(zhǔn)確性比較.

圖3　抽樣聚類和直接聚類結(jié)果準(zhǔn)確性比較（K=10，N=15 760）Fig.3　Comparison of clustering accuracy between sampling-clustering and direct clustering （K=10，N=15 760）

圖4　抽樣聚類和直接聚類結(jié)果準(zhǔn)確性比較（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ù)對抽樣效率影響的測試

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

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

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

5　結(jié)束語

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

［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］.軟件學(xué)報，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ìn)的基于密度的抽樣聚類算法［J］.中國圖象圖形學(xué)報，2007（11）：2031-2036.

［8］周兵，沈鈞毅，彭勤科.基于隨機(jī)抽樣和聚類特征的聚類算法［J］.西安交通大學(xué)學(xué)報，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

上海市教委重點(diǎn)學(xué)科資助項目（12ZZ09）；上海市科委資助項目（13DZ118800）

雷詠梅（1965—），女，教授，博士生導(dǎo)師，博士，研究方向為高性能計算、大數(shù)據(jù)處理等. E-mail:lei@shu.edu.cn