全海金，何映思

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

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

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

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

1.1 模糊K-means算法介紹

K-means算法是一種基于距離的聚類方法[6-9]，它基本上按距離將每個數據分配給它自己的聚類中心。在聚類過程中，先選定K個點，并將這些點設定為集群中心，然后計算所有對象與這些點的歐式距離，將距離較近的歸為同一類。然后重復前面的聚類，在重復聚類過程中不停更新中心點的值，一直重復到預先設定的重復迭代次數或者超過了預先設定的規(guī)則函數邊界值。這時即認為取得了最佳的聚類結果。在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算法是一種貪婪算法，使用了非凸成本函數優(yōu)化，使用該算法僅僅能夠獲得局部最優(yōu)解[12]。此外，在該算法中，聚類中心的設置非常關鍵，同樣的數據集，聚類的點集也一樣，如果群集中心發(fā)生變化，則生成的群集可能會有很大差異[13]。

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

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

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

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

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

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

(3)

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

(4)

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

(5)

步驟3 選取密度靠前的K個點作為初始中心點，其中經過上述的計算已經得到密度集合P={P(x1),P(x2),…,P(xn)}。選取其中密度最大的點作為第1個中心點，記作O1。之后不是簡單地選取密度第二大的點，而是結合FF最遠最優(yōu)策略，即選擇離第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。

現(xiàn)在使用文本中的方法聚類提取的數據，并計算與聚類對應的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值時，人為因素的參與將導致聚類分析結果的不穩(wěn)定。因此，針對聚類算法的特點，本文采用大數據算法估計K值的聚類中心點，使聚類結果的質量和穩(wěn)定性在一定程度上得到了提高。通過對聚類結果仿真的分析，可以從大數據的復雜事件中找到所需的模式關系。仿真結果表明：所提優(yōu)化算法是可行的，具有一定的實際意義。