基于大數據的改進模糊K-means算法

全海金，何映思

(西南大學 數學與統計學院，計算機與信息科學學院， 重慶 400715)

隨著互聯網技術蓬勃發展，各種傳感器大量應用于互聯網各行各業，產生龐大數據[1]。如百度、FaceBook、騰訊、谷歌、阿里巴巴等互聯網巨頭，每天需要處理數百PB的數據。亞馬遜、淘寶以及拼多多等大型在線電子商務平臺，每小時會接受數億訪問請求。信息技術的飛速發展，數據的爆炸增長，使整個人類社會進入了“大數據”時代。這些大數據的出現為人類提供了豐富的信息來源用以感知、識別和控制物理世界[2]，在帶來便利的同時也帶來了新的挑戰，那就要求服務器具有更高的處理能力和效率。

大數據所有數據將存儲在服務器，由服務器進行合理整理分類，統一管理。并將相關計算和數據處理過程分發到類似終端設備進行處理，以提高數據處理的效率[3]。因此，在大數據時代，更需要數據的高處理效率和準確性。傳統的聚類方法主要包括K-means算法[4]和FCM方法[5]，但在處理大數據時這2種聚類方法的聚類效率很低，并不能滿足大數據處理的要求。為了解決這個問題，本文利用現有的分布式平臺Hadoop的MapReduce計算框架將模糊K-means聚類算法移植到大數據聚類方法中。優化的模糊K-Means算法具有良好的效率和穩定性。

1 模糊K-means算法的改進算法

1.1 模糊K-means算法介紹

K-means算法是一種基于距離的聚類方法[6-9]，它基本上按距離將每個數據分配給它自己的聚類中心。在聚類過程中，先選定K個點，并將這些點設定為集群中心，然后計算所有對象與這些點的歐式距離，將距離較近的歸為同一類。然后重復前面的聚類，在重復聚類過程中不停更新中心點的值，一直重復到預先設定的重復迭代次數或者超過了預先設定的規則函數邊界值。這時即認為取得了最佳的聚類結果。在K均值聚類過程中，需要人為地設置K值。

在經典的K-Means算法中，每個點都被強制分配給一個簇，Bezdek提出了模糊C-均值[10]。這樣一個點不僅僅屬于一個簇，可以屬于多個簇，使用該方法能夠使聚類過程更好地收斂。

模糊K-means 算法的數學描述如下[11]：

設對象集合P={x1,x2,…,xn}，數據樣本為xi={xi1,xi2,…,xin}，則樣本xi與樣本xj的歐式距離計算公式為

d(xi,xj)=[(xi1-xj1)2+(xi2-xj2)2+…+(xin-xjn)2]

(1)

最小化非負代價函數是K-means 算法的一種收斂條件，數學描述為

(2)

1.2 模糊K-means 算法的局限性

K-means算法是一種貪婪算法，使用了非凸成本函數優化，使用該算法僅僅能夠獲得局部最優解[12]。此外，在該算法中，聚類中心的設置非常關鍵，同樣的數據集，聚類的點集也一樣，如果群集中心發生變化，則生成的群集可能會有很大差異[13]。

為了解決局部最小問題，需要優化初始中心點的選擇，并根據相應數據集的分布特征選擇更合理的初始分類中心。以達到更快更準的目標，在保證精準度的前提下，盡可能提高其運算效率[14]。

最佳K值很難選擇，而K-means算法需要高初始聚類點。如果初始聚類中心點選擇合理，能夠很好地提高聚類準確性和效率。所以，K-means 算法中存在2個關鍵問題[15]：①K值的選取；② 進行聚類的中心點的選擇。

1.3 模糊K-means改進算法流程

根據實際經驗，用戶消費流法一般具有較好的聚合特性，例如，高流量用戶的特征是相似的。如具有消耗月流量大，月資費較高，用戶年齡大部分為30、40歲左右等特點。因此，本文考慮選擇基于密度的優化方法來確定數據的初始中心。其理論依據為：數據樣本之間的歐氏距離越近，它們的相似度越高，即在固定的數據區域中，數據密度越大，其中數據點的聚合程度越高，則首先將具有大密度區域的點集中并選擇初始中心點。顯然，可以獲得更好的局部最優解[16]。

改進的模糊K-means算法具體步驟如下：

步驟1 根據計算得到集合里任意2個點之間的歐氏距離d(xi,xj)。為了求得一個點的周圍區域的密度，首先需要一個中間變量，也就是所有點之間的平均距離，這里記為AD(average distance)：

(3)

步驟2 計算數據樣本周圍區域的密度，xi周圍區域密度大小記為D(xi)，其意義是若兩點之間比平均距離小，則認為它是較相似的。這里采用密度強化的系數u來間接描述這種相似性。那么密度公式為：

(4)

其中，密度強化系數u定義為：

(5)

步驟3 選取密度靠前的K個點作為初始中心點，其中經過上述的計算已經得到密度集合P={P(x1),P(x2),…,P(xn)}。選取其中密度最大的點作為第1個中心點，記作O1。之后不是簡單地選取密度第二大的點，而是結合FF最遠最優策略，即選擇離第1個中心點較遠且密度最大的點作為第2個中心點。其公式可描述為：

max(mind(yi-o1),min(d(yi-o2)),…,

min(d(yi-on-1)))

(6)

尋求滿足上述公式的樣本點yi，直到找到K個初始中心為止。

2 仿真實驗

采用Matlab對文中的聚類算法進行仿真。Matlab可用于模擬本文中的聚類算法。首先，從UCI機器學習庫[10]中提取了17 000個文檔，并使用向量空間模型將文檔集轉換為向量集。獲得的數據向量的維數為120，數據可以分為4大類，即R.*、C.*、S.*和T.*，每個子類別包含幾個子類別，可分為14個子類別。

R.*類可以分為R.autos、R.motorcycles、R.sport.baseball和R.soprt.hockey。

C.*類可以分為C.graphics、C.os.ms、C.sys.mac.hardware和C.widows.x。

S.*類可以分為S.electronics、S.med、S.space和S.crypt。

T.*類可以分為T.politics和T.religion。

現在使用文本中的方法聚類提取的數據，并計算與聚類對應的avgIE值。并與經典模糊K-means算法對比，對比結果見圖1。

圖1 改進的模糊K-means算法與經典模糊K-means算法的比較

從圖1中可以看出：在模擬過程中，對應于該方法的聚類結果的avgIE值遠高于經典的K均值算法。當模擬時間為400 ms時，avgIE值收斂到0.9，而經典模糊K均值算法收斂于1 300 ms。avgIE值最終收斂到0.81，其收斂效應不理想。

3 結束語

在模糊K均值算法中，當選擇K值時，人為因素的參與將導致聚類分析結果的不穩定。因此，針對聚類算法的特點，本文采用大數據算法估計K值的聚類中心點，使聚類結果的質量和穩定性在一定程度上得到了提高。通過對聚類結果仿真的分析，可以從大數據的復雜事件中找到所需的模式關系。仿真結果表明：所提優化算法是可行的，具有一定的實際意義。