基于Spark平臺的聚類算法的研究和實現

沈陽理工大學信息科學與工程學院 胡 可 姜學軍

基于Spark平臺的聚類算法的研究和實現

沈陽理工大學信息科學與工程學院 胡 可 姜學軍

傳統的聚類算法[1]是從要聚類的樣本中任意挑選指定個樣本作為中心點開始聚類，中心點選取不同，聚類算法每次執行的結果可能不一樣，這樣會導致不穩定的結果。為了使聚類結果更加穩定，在聚類算法開始之前怎樣得到準確的中心點個數以及正確地挑選合適的初始中心點[2]的研究具有非常重要的價值。Mean shift算法[3]是一種非參數密度估計算法。Mean shift算法可以通過不停的循環調用，可以很快地收斂于概率密度函數最大的地方。算法的過程就是不斷尋找概率密度局部最大值的過程。通過Mean shift算法可以很快的找到中心點。

聚類算法；mean shift

1 Mean shift算法概述

假設一個d維空間Rd，其d維空間中有n個數據點xi，i = 1，2，…，n ……隨便取其中一點x，那么此時它的多元核密度估計表達式由核函數[4]k(x)和d*d維正對稱帶寬矩陣構成，該函數可以表示為：

其中KH(x)：

其中，核函數 k(x)決定了采樣點與核中心點之間的相似程度。Mean Shift算法變形如公式如下所示。

其中，h為半徑，ck,d，nhd為單位密度。

Mean Shift向量表示為：

令mh,G(x)=0，可以求得向量最終坐標：

Mean Shift算法流程可以簡述為：

1)在d維空間中以x為圓心，以h為半徑，做一個高維球，落在球內的所有點為xi。

2)計算 mh,G(x)，手動設向量的值為δ，如果mh,G(x)＜δ，程序結束。

否則mh,G(x)＞δ，則利用公式1) 重復以上步驟直到迭代結束。

2 對聚類算法的改進

2.1 k-中心點聚類算法及缺點

當利用k-中心點算法[5-7]對數據集進行聚類時，首先，人工設定需要聚類數目k，然后隨機在樣本點內選擇k個點作為初始中心點，剩下的n－k個樣本點計算樣本與k個中心點的距離，將樣本點劃分到距離最近的中心點所代表的簇。接著在每個簇中計算改簇中所有樣本點的均值，選用距離均值最近的樣本點作為新的簇中心，重復上述步驟直到該簇的中心點不再發生明顯的變化(簇的絕對誤差和收斂)為止。簇的絕對誤差和反應聚類的質量，值越小，表示類簇越緊湊，聚類效果越好。假設聚類好的k個簇為X1，X2，…，Xk，每個簇的中心點r1，r2……rk，則每個簇的誤差和E的公式為：

k-中心點聚類算法對于數據簇內密集、簇間稀疏的情況，其聚類效果較好(誤差平方和最小)，但存在因初始點的選取問題而導致不穩定的聚類結果的缺陷[8]。聚類算法的正確率與選擇的中心點有很大關系，致使算法相對不穩定，初始點選取的隨機性不僅會導致初始點不同時運行效率不一樣，更可能使聚類結果不一致，影響算法在實際中的效果。

2.2 Mean Shift算法對k-中心點算法的改進

針對上述k-中心點算法的缺陷，已有很多學者對算法提出了改進[9-10]，但是現有的改進方法實現起來較為復雜，不便于直接在實際問題中應用。直觀上，如果一個點附近的鄰居點越多，則該點越有可能是簇的中心點。Mean shift 算法[3]是一種非參數密度估計算法。Mean shift算法可以通過不停的循環調用，可以很快地收斂于概率密度函數最大的地方。算法的過程就是不斷尋找概率密度局部最大值的過程。通過Mean shift算法可以很快的找到中心點。

使用Mean Shift算法改進k-中心點算法：

輸入數據：數據集X（總共包含n個樣本）和簇數目k

輸出數據：聚好類的k個簇

過程：

步驟1：計算任意兩樣本點間距離d(xi，xj) ；

步驟2：取樣本點間距離的均值的k分之一作為樣本點的鄰域半徑ε；

步驟3：確定初始中心點集合C：

步驟3.1：從X中隨機選擇一點G，以G為起點，以將此點ε鄰域內所有點為終點做一個矢量，求這些矢量和得到mean shift向量，以mean shift向量終點為起點，重復上述動作最終得到密度最大點c1，作為第一個初始聚類中心加入集合C；

步驟3.2：從X中找出距離c1最遠的樣本按照步驟3.1得到一個初始聚類中心c2，將c2加入集合C；

步驟3.3：從X中找與c1，…，ck－1距離和最遠的樣本按照步驟3.1得到一個初始聚類中心ck，將ck加入集合C；

步驟4：最后將剩下的n－k個樣本點計算樣本與集合C中的距離，將樣本點劃分到距離最近的中心點ci所代表的簇；

步驟5：輸出k個簇。

3 實驗結果與分析

下面將對K-中心點算法與改進后的聚類算法的聚類效果在不同的應用景進行比較分析。

3.1 分區數與聚類效果分析

每個分區所聚類的個數c如果是指定的聚類數目k的3倍以上效果會更好，這樣可以使得所有的子分區不會聚成一個簇。實驗結果表明：如果聚類個數c小于聚類數目k時，聚類結果可能與理想的情況不匹配。

上圖說明，在k為6時，c為2、6、12，即小于k的2～3倍，則聚類結果不理想。而在c為18時，聚類結果理想。

3.2 對于K-中心點算法和改進K-中心點算法的比較

從圖中看出在收縮因子α的值為0.2或者0.4時，K-中心點算法的聚類結果與期望情況不符，而使用Mean Shift算法改進的聚類算法的聚類效果相對比較符合情況。因此Mean Shift算法改進的聚類算法在數據處理上比K-中心點算法效果更好。

4 結論

原始的k-中心點算法使用在所有樣本點里隨機選擇k個點作為中心點，這樣的方法并沒有考慮樣本點的實際分布，導致聚類算法的正確率與選擇的中心點有很大關系，致使算法相對不穩定，并且結果容易出現局部最優解。而采用Mean Shift算法改進的聚類算法獲得初始中心點，使用這種方法得到的初始聚類中心收斂于概率密度局部最大值，與真實的聚類中心分布較為一致，算法穩定且快速收斂，同時也降低了測試的錯誤率。實驗結果證明了我們設計目標。

雖然Mean Shift算法改進的聚類算法穩定性和準確率有所提升，并且由大量數據證明在聚類算法的應用中效果良好，但對于該方法的有效性評估尚處于定性階段，未來將開展針對此類數據聚類效果的整體、定量評估方法，從而對不同聚類算法進行評價。

[1]周愛武,于亞飛.K-means聚類算法的研究[J].計算機技術與發展,2011(02):2.

[2]汪中,劉貴全,陳恩紅.一種優化初始中心點的K-means算法[J].模式識別與人工智能,2009,22(2).

[3]Comaniciu D,Ramesh V,Meer P.Real-time tracking of nonrigid objects using Mean shift[C]//Proc IEEE Coference on Computer Vision and Pattern Recognition,2000:142-149.

[4]CHENG Yi-zong.Mean shift,mode seeking,and clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligen ce,1995,17(8):790-799.

[5]ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[J].Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining.Portland:AAAI,1996:226-231.

[6]Song Y,Liang J G.Study of fuzzy clustering algorithm using in C RM[J].Logistics Management,2005,28(1):26-28(Ch).

[7]Bradley PS,Fayyad UM.Refining initial points for k-means clustering［DB/ OL].[2014-06-02].http://pub-lic.zirmed.com/wp-content /uploads /2014 /12 /Refining-In-itial-Points-for-k-Means-Clustering.pdf.

[8]Chen J H,Zhang Q,Feng WX,etal.Lightning location system and lightning detection network of China power grid[J].High Voltage Engineering,2008,34(3):425-431(Ch).

[9]Yun Won Chung;Min Young Chung;Dan Keun Sung. Modeling and Analysis of Mobile Terminal Power on/off-State Management Considering User Behavior[J].Vehicular Technology,IEEE Transactio ns.2008,6(57):3708-3722.

[10]Wei-Jen Hsu;Dutta,D.;Helmy,A.Structural Analysis of User Association Patterns in University Campus Wireless LANs[J].Mobile Computing,IEEE Transactions.2012,11(11):1734-1748.