基于大數(shù)據(jù)的改進(jìn)模糊K-means算法

全海金，何映思

(西南大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，計(jì)算機(jī)與信息科學(xué)學(xué)院， 重慶 400715)

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

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

1 模糊K-means算法的改進(jìn)算法

1.1 模糊K-means算法介紹

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

在經(jīng)典的K-Means算法中，每個(gè)點(diǎn)都被強(qiáng)制分配給一個(gè)簇，Bezdek提出了模糊C-均值[10]。這樣一個(gè)點(diǎn)不僅僅屬于一個(gè)簇，可以屬于多個(gè)簇，使用該方法能夠使聚類(lèi)過(guò)程更好地收斂。

模糊K-means 算法的數(shù)學(xué)描述如下[11]：

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

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

(1)

最小化非負(fù)代價(jià)函數(shù)是K-means 算法的一種收斂條件，數(shù)學(xué)描述為

(2)

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

K-means算法是一種貪婪算法，使用了非凸成本函數(shù)優(yōu)化，使用該算法僅僅能夠獲得局部最優(yōu)解[12]。此外，在該算法中，聚類(lèi)中心的設(shè)置非常關(guān)鍵，同樣的數(shù)據(jù)集，聚類(lèi)的點(diǎn)集也一樣，如果群集中心發(fā)生變化，則生成的群集可能會(huì)有很大差異[13]。

為了解決局部最小問(wèn)題，需要優(yōu)化初始中心點(diǎn)的選擇，并根據(jù)相應(yīng)數(shù)據(jù)集的分布特征選擇更合理的初始分類(lèi)中心。以達(dá)到更快更準(zhǔn)的目標(biāo)，在保證精準(zhǔn)度的前提下，盡可能提高其運(yùn)算效率[14]。

最佳K值很難選擇，而K-means算法需要高初始聚類(lèi)點(diǎn)。如果初始聚類(lèi)中心點(diǎn)選擇合理，能夠很好地提高聚類(lèi)準(zhǔn)確性和效率。所以，K-means 算法中存在2個(gè)關(guān)鍵問(wèn)題[15]：①K值的選?。虎?進(jìn)行聚類(lèi)的中心點(diǎn)的選擇。

1.3 模糊K-means改進(jìn)算法流程

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

改進(jìn)的模糊K-means算法具體步驟如下：

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

(3)

步驟2 計(jì)算數(shù)據(jù)樣本周?chē)鷧^(qū)域的密度，xi周?chē)鷧^(qū)域密度大小記為D(xi)，其意義是若兩點(diǎn)之間比平均距離小，則認(rèn)為它是較相似的。這里采用密度強(qiáng)化的系數(shù)u來(lái)間接描述這種相似性。那么密度公式為：

(4)

其中，密度強(qiáng)化系數(shù)u定義為：

(5)

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

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

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

(6)

尋求滿(mǎn)足上述公式的樣本點(diǎn)yi，直到找到K個(gè)初始中心為止。

2 仿真實(shí)驗(yàn)

采用Matlab對(duì)文中的聚類(lèi)算法進(jìn)行仿真。Matlab可用于模擬本文中的聚類(lèi)算法。首先，從UCI機(jī)器學(xué)習(xí)庫(kù)[10]中提取了17 000個(gè)文檔，并使用向量空間模型將文檔集轉(zhuǎn)換為向量集。獲得的數(shù)據(jù)向量的維數(shù)為120，數(shù)據(jù)可以分為4大類(lèi)，即R.*、C.*、S.*和T.*，每個(gè)子類(lèi)別包含幾個(gè)子類(lèi)別，可分為14個(gè)子類(lèi)別。

R.*類(lèi)可以分為R.autos、R.motorcycles、R.sport.baseball和R.soprt.hockey。

C.*類(lèi)可以分為C.graphics、C.os.ms、C.sys.mac.hardware和C.widows.x。

S.*類(lèi)可以分為S.electronics、S.med、S.space和S.crypt。

T.*類(lèi)可以分為T(mén).politics和T.religion。

現(xiàn)在使用文本中的方法聚類(lèi)提取的數(shù)據(jù)，并計(jì)算與聚類(lèi)對(duì)應(yīng)的avgIE值。并與經(jīng)典模糊K-means算法對(duì)比，對(duì)比結(jié)果見(jiàn)圖1。

圖1 改進(jìn)的模糊K-means算法與經(jīng)典模糊K-means算法的比較

從圖1中可以看出：在模擬過(guò)程中，對(duì)應(yīng)于該方法的聚類(lèi)結(jié)果的avgIE值遠(yuǎn)高于經(jīng)典的K均值算法。當(dāng)模擬時(shí)間為400 ms時(shí)，avgIE值收斂到0.9，而經(jīng)典模糊K均值算法收斂于1 300 ms。avgIE值最終收斂到0.81，其收斂效應(yīng)不理想。

3 結(jié)束語(yǔ)

在模糊K均值算法中，當(dāng)選擇K值時(shí)，人為因素的參與將導(dǎo)致聚類(lèi)分析結(jié)果的不穩(wěn)定。因此，針對(duì)聚類(lèi)算法的特點(diǎn)，本文采用大數(shù)據(jù)算法估計(jì)K值的聚類(lèi)中心點(diǎn)，使聚類(lèi)結(jié)果的質(zhì)量和穩(wěn)定性在一定程度上得到了提高。通過(guò)對(duì)聚類(lèi)結(jié)果仿真的分析，可以從大數(shù)據(jù)的復(fù)雜事件中找到所需的模式關(guān)系。仿真結(jié)果表明：所提優(yōu)化算法是可行的，具有一定的實(shí)際意義。