基于Spark平臺的聚類算法的研究和實現(xiàn)

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

基于Spark平臺的聚類算法的研究和實現(xiàn)

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

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

聚類算法；mean shift

1 Mean shift算法概述

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

其中KH(x)：

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

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

Mean Shift向量表示為：

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

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

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

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

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

2 對聚類算法的改進

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

當利用k-中心點算法[5-7]對數(shù)據(jù)集進行聚類時，首先，人工設定需要聚類數(shù)目k，然后隨機在樣本點內(nèi)選擇k個點作為初始中心點，剩下的n－k個樣本點計算樣本與k個中心點的距離，將樣本點劃分到距離最近的中心點所代表的簇。