基于Spark平臺(tái)的聚類(lèi)算法的研究和實(shí)現(xiàn)

沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院 胡 可 姜學(xué)軍

基于Spark平臺(tái)的聚類(lèi)算法的研究和實(shí)現(xiàn)

沈陽(yáng)理工大學(xué)信息科學(xué)與工程學(xué)院 胡 可 姜學(xué)軍

傳統(tǒng)的聚類(lèi)算法[1]是從要聚類(lèi)的樣本中任意挑選指定個(gè)樣本作為中心點(diǎn)開(kāi)始聚類(lèi)，中心點(diǎn)選取不同，聚類(lèi)算法每次執(zhí)行的結(jié)果可能不一樣，這樣會(huì)導(dǎo)致不穩(wěn)定的結(jié)果。為了使聚類(lèi)結(jié)果更加穩(wěn)定，在聚類(lèi)算法開(kāi)始之前怎樣得到準(zhǔn)確的中心點(diǎn)個(gè)數(shù)以及正確地挑選合適的初始中心點(diǎn)[2]的研究具有非常重要的價(jià)值。Mean shift算法[3]是一種非參數(shù)密度估計(jì)算法。Mean shift算法可以通過(guò)不停的循環(huán)調(diào)用，可以很快地收斂于概率密度函數(shù)最大的地方。算法的過(guò)程就是不斷尋找概率密度局部最大值的過(guò)程。通過(guò)Mean shift算法可以很快的找到中心點(diǎn)。

聚類(lèi)算法；mean shift

1 Mean shift算法概述

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

其中KH(x)：

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

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

Mean Shift向量表示為：

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

Mean Shift算法流程可以簡(jiǎn)述為：

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

2)計(jì)算 mh,G(x)，手動(dòng)設(shè)向量的值為δ，如果mh,G(x)＜δ，程序結(jié)束。

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

2 對(duì)聚類(lèi)算法的改進(jìn)

2.1 k-中心點(diǎn)聚類(lèi)算法及缺點(diǎn)

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

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

2.2 Mean Shift算法對(duì)k-中心點(diǎn)算法的改進(jìn)

針對(duì)上述k-中心點(diǎn)算法的缺陷，已有很多學(xué)者對(duì)算法提出了改進(jìn)[9-10]，但是現(xiàn)有的改進(jìn)方法實(shí)現(xiàn)起來(lái)較為復(fù)雜，不便于直接在實(shí)際問(wèn)題中應(yīng)用。直觀上，如果一個(gè)點(diǎn)附近的鄰居點(diǎn)越多，則該點(diǎn)越有可能是簇的中心點(diǎn)。Mean shift 算法[3]是一種非參數(shù)密度估計(jì)算法。Mean shift算法可以通過(guò)不停的循環(huán)調(diào)用，可以很快地收斂于概率密度函數(shù)最大的地方。算法的過(guò)程就是不斷尋找概率密度局部最大值的過(guò)程。通過(guò)Mean shift算法可以很快的找到中心點(diǎn)。

使用Mean Shift算法改進(jìn)k-中心點(diǎn)算法：

輸入數(shù)據(jù)：數(shù)據(jù)集X（總共包含n個(gè)樣本）和簇?cái)?shù)目k

輸出數(shù)據(jù)：聚好類(lèi)的k個(gè)簇

過(guò)程：

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

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

步驟3：確定初始中心點(diǎn)集合C：

步驟3.1：從X中隨機(jī)選擇一點(diǎn)G，以G為起點(diǎn)，以將此點(diǎn)ε鄰域內(nèi)所有點(diǎn)為終點(diǎn)做一個(gè)矢量，求這些矢量和得到mean shift向量，以mean shift向量終點(diǎn)為起點(diǎn)，重復(fù)上述動(dòng)作最終得到密度最大點(diǎn)c1，作為第一個(gè)初始聚類(lèi)中心加入集合C；

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

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

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

步驟5：輸出k個(gè)簇。

3 實(shí)驗(yàn)結(jié)果與分析

下面將對(duì)K-中心點(diǎn)算法與改進(jìn)后的聚類(lèi)算法的聚類(lèi)效果在不同的應(yīng)用景進(jìn)行比較分析。

3.1 分區(qū)數(shù)與聚類(lèi)效果分析

每個(gè)分區(qū)所聚類(lèi)的個(gè)數(shù)c如果是指定的聚類(lèi)數(shù)目k的3倍以上效果會(huì)更好，這樣可以使得所有的子分區(qū)不會(huì)聚成一個(gè)簇。實(shí)驗(yàn)結(jié)果表明：如果聚類(lèi)個(gè)數(shù)c小于聚類(lèi)數(shù)目k時(shí)，聚類(lèi)結(jié)果可能與理想的情況不匹配。

上圖說(shuō)明，在k為6時(shí)，c為2、6、12，即小于k的2～3倍，則聚類(lèi)結(jié)果不理想。而在c為18時(shí)，聚類(lèi)結(jié)果理想。

3.2 對(duì)于K-中心點(diǎn)算法和改進(jìn)K-中心點(diǎn)算法的比較

從圖中看出在收縮因子α的值為0.2或者0.4時(shí)，K-中心點(diǎn)算法的聚類(lèi)結(jié)果與期望情況不符，而使用Mean Shift算法改進(jìn)的聚類(lèi)算法的聚類(lèi)效果相對(duì)比較符合情況。因此Mean Shift算法改進(jìn)的聚類(lèi)算法在數(shù)據(jù)處理上比K-中心點(diǎn)算法效果更好。

4 結(jié)論

原始的k-中心點(diǎn)算法使用在所有樣本點(diǎn)里隨機(jī)選擇k個(gè)點(diǎn)作為中心點(diǎn)，這樣的方法并沒(méi)有考慮樣本點(diǎn)的實(shí)際分布，導(dǎo)致聚類(lèi)算法的正確率與選擇的中心點(diǎn)有很大關(guān)系，致使算法相對(duì)不穩(wěn)定，并且結(jié)果容易出現(xiàn)局部最優(yōu)解。而采用Mean Shift算法改進(jìn)的聚類(lèi)算法獲得初始中心點(diǎn)，使用這種方法得到的初始聚類(lèi)中心收斂于概率密度局部最大值，與真實(shí)的聚類(lèi)中心分布較為一致，算法穩(wěn)定且快速收斂，同時(shí)也降低了測(cè)試的錯(cuò)誤率。實(shí)驗(yàn)結(jié)果證明了我們?cè)O(shè)計(jì)目標(biāo)。

雖然Mean Shift算法改進(jìn)的聚類(lèi)算法穩(wěn)定性和準(zhǔn)確率有所提升，并且由大量數(shù)據(jù)證明在聚類(lèi)算法的應(yīng)用中效果良好，但對(duì)于該方法的有效性評(píng)估尚處于定性階段，未來(lái)將開(kāi)展針對(duì)此類(lèi)數(shù)據(jù)聚類(lèi)效果的整體、定量評(píng)估方法，從而對(duì)不同聚類(lèi)算法進(jìn)行評(píng)價(jià)。

[1]周愛(ài)武,于亞飛.K-means聚類(lèi)算法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011(02):2.

[2]汪中,劉貴全,陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法[J].模式識(shí)別與人工智能,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.