并行K_means算法的優(yōu)化研究分析

【摘要】眾所周知我們已經(jīng)生活在信息時(shí)代。隨著大量數(shù)據(jù)不斷的涌入到數(shù)據(jù)庫(kù)，使得我們數(shù)據(jù)庫(kù)中的信息不斷的增長(zhǎng)，以至于我們很難從龐大的數(shù)據(jù)庫(kù)中發(fā)現(xiàn)知識(shí)，發(fā)現(xiàn)對(duì)我們來說還有潛在意義的知識(shí)。本文主要對(duì)傳統(tǒng)的聚類分析中的經(jīng)典算法K_means進(jìn)行改進(jìn)，增強(qiáng)其對(duì)龐大數(shù)據(jù)聚類的伸縮性以及時(shí)效性。本次算法的改進(jìn)對(duì)收斂速度和準(zhǔn)確率以及算法的伸縮性都有了很大的提升。

【關(guān)鍵詞】數(shù)據(jù)挖掘；聚類 K_means 并行K均值；初始值優(yōu)化

隨著數(shù)據(jù)庫(kù)和數(shù)據(jù)管理產(chǎn)業(yè)的不斷發(fā)展，如今大型的的數(shù)據(jù)庫(kù)系統(tǒng)已經(jīng)普及發(fā)展，從常見的關(guān)系數(shù)據(jù)庫(kù)到企業(yè)級(jí)的數(shù)據(jù)倉(cāng)庫(kù)已經(jīng)包含了大量的數(shù)據(jù)，而數(shù)據(jù)庫(kù)系統(tǒng)只提供事務(wù)處理，數(shù)據(jù)倉(cāng)庫(kù)提供決策級(jí)的數(shù)據(jù)分析。面對(duì)眾多的層積在數(shù)據(jù)庫(kù)中的知識(shí)，對(duì)其發(fā)現(xiàn)和分析變得越來越重要也越來越困難，在這種背景下數(shù)據(jù)挖掘便應(yīng)運(yùn)而生，從大量的數(shù)據(jù)中發(fā)現(xiàn)知識(shí)也變得至關(guān)重要。所以我們對(duì)數(shù)據(jù)挖掘的研究顯得尤為重要。然而在數(shù)據(jù)挖掘中聚類分析是最基本也是最重要的，現(xiàn)在國(guó)內(nèi)外對(duì)聚類方法中的K_means算法的研究也是如火如荼。面對(duì)不通的應(yīng)用領(lǐng)域K_means算法的改進(jìn)也是多種多樣，但對(duì)大型數(shù)據(jù)K_means算法的局限性也展示了出來，于是并列K_means算法也得到了很好的發(fā)展和研究。本文章主要針對(duì)大型數(shù)據(jù)做聚類分析，采用基于Mapreduce并列K_means算法，并對(duì)K_means算法的初始值選擇加以優(yōu)化，主要從效率和準(zhǔn)確度出發(fā)進(jìn)行研究。

一、傳統(tǒng)的K_means算法思想

K_means算法是一種最著名和最普及的聚類方法之一，其目的是將數(shù)據(jù)對(duì)象的數(shù)據(jù)集M劃分成K個(gè)相互排斥的簇，使簇與簇之間有高度的相異性，而簇內(nèi)部具有高度的相似性。在劃分的時(shí)候一般采取歐式距離為參考。

一般步驟：根據(jù)經(jīng)驗(yàn)確定要聚類的數(shù)目K，然后隨機(jī)的選取K個(gè)對(duì)象作為K個(gè)簇的中心點(diǎn)，再按照歐式距離對(duì)其余對(duì)象進(jìn)行距離計(jì)算，將其余對(duì)象分配到離中心最近的簇中。然后分配完畢后，重新計(jì)算各個(gè)簇中的平局?jǐn)?shù)，并將這個(gè)平均數(shù)作為新的中心點(diǎn)。重復(fù)這個(gè)過程直到簇沒有變化為止。

K-均值算法的過程如下：算法：K_means。每個(gè)簇都用簇中心表示，簇中心用簇內(nèi)的對(duì)象的均值來表示。輸入：K：簇的個(gè)數(shù) M：包含n個(gè)對(duì)象的數(shù)據(jù)集

輸出：k個(gè)簇的集合，方法：

（一）從M中任意選擇K個(gè)對(duì)象作為初始簇的中心；

（二）Repeat

（三）根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象分配到最相似的簇

（四）更新簇的中心

（五）Until不在發(fā)生變化

二、改進(jìn)的K_means并行處理算法

改進(jìn)的K_means算法，通過預(yù)先對(duì)大數(shù)據(jù)進(jìn)行抽樣，然后對(duì)樣本進(jìn)行分析采用最長(zhǎng)距離法選定簇中心。然后用基于MapReduce的并列K_means算法進(jìn)行聚類。本文數(shù)據(jù)來源由隨機(jī)生成函數(shù)隨機(jī)產(chǎn)生40000條1-100的隨機(jī)數(shù)，然后人為插入10條4位數(shù)到數(shù)據(jù)中。通過抽樣函數(shù)在數(shù)據(jù)中抽樣100個(gè)數(shù)為抽樣樣本。

（一）K_均值初始簇中心的選定

傳統(tǒng)的初始中心都是隨機(jī)抽取，我們對(duì)隨機(jī)抽取進(jìn)行一些優(yōu)化。對(duì)于初始簇中心選擇采取基于距離與密度而確定?；舅枷霝樵跇颖局羞x取相距距離最遠(yuǎn)且樣本的密度最大的k個(gè)點(diǎn)作為初始簇中心。

下面定義樣本點(diǎn)x所處區(qū)域的密度 ：

P (x )= {x∈D|Dis(x，d)≤r}其中 D 為樣本點(diǎn)集，r為球體半徑，Dis (x ，d)為距離測(cè)量。樣本點(diǎn)x所處區(qū)域的密度計(jì)算規(guī)則為以x為中心，r 為半徑的球體所包含的樣本個(gè)數(shù)。半徑r的確定規(guī)則如下 ：<1> 求解每?jī)蓚€(gè)數(shù)據(jù)對(duì)象的距離，然后求出所有距離的平均值λ。然后求出每個(gè)樣本點(diǎn)所在區(qū)域的密度，然后把密度大的區(qū)域中的點(diǎn)組成新的集合D1，在集合中取 P 值最大的樣本點(diǎn)作為第一個(gè)初始中心K1，然后取離K1最遠(yuǎn)的高密度樣本點(diǎn)作為第二個(gè)初始簇中心K2 ，然后取滿足 max(min(d(Xi，K1)，d(Xi，K2))) i=1，2，…，n 的樣本點(diǎn)Xi作為第三個(gè)初始中心K3，依次類推，取滿足 max(min(d(Xi，K1)，d(Xi，K2)，…d(Xi，KK-1))) i=1，2，…，n 的 樣 本 點(diǎn)Xi作為第K個(gè)初始簇中心，最后確定了聚類的 k 個(gè)初始中心。多次實(shí)驗(yàn)改進(jìn)算法取距離最遠(yuǎn)的k 個(gè)密度大的樣本點(diǎn)作為聚類的初始簇中心，這些簇中心點(diǎn)基本上是穩(wěn)定的，從而而消除了初始中心選擇的隨機(jī)性，提高了聚類結(jié)果的精確度。

（二）基于MapReduce的并行K_means算法實(shí)現(xiàn)

K_means算法中的主要計(jì)算工作是將每個(gè)樣本分配到距離其最近的聚簇，并且分配不同對(duì)象之間的操作是相互獨(dú)立的，因此可以將這一步在Ｈａｄｏｏｐ分布式框架中并行操作．首先，將這Ｋ個(gè)聚簇存儲(chǔ)在ＨＤＦＳ上作為全局變量，并在每次迭代執(zhí)行完成后進(jìn)行更新．簇中包含該簇的簇符、簇中含有的對(duì)象的個(gè)數(shù)及簇的中心，初始聚簇的中心心就是我們先前確定Ｋ個(gè)簇中心本．算 法 的 執(zhí) 行 迭 代 的 過 程 中 包 含Ｍａｐ和Ｒｅｄｕｃｅ2個(gè)部分． 在Map函數(shù)部分計(jì)算各節(jié)點(diǎn)數(shù)據(jù)與初始簇中心的距離，然后將對(duì)象標(biāo)記為離他最近的簇標(biāo)記。在reduce部分，對(duì)輸出結(jié)果進(jìn)行歸并，將數(shù)據(jù)點(diǎn)編號(hào)和所屬的類別的對(duì)應(yīng)關(guān)系輸出。然后匯總各個(gè)map的新的簇中心點(diǎn)重新計(jì)算中心點(diǎn)。然后依次迭代。

三、總結(jié)

經(jīng)過改進(jìn)后的K_均值算法，在簇初始中心點(diǎn)選擇上沒有采用隨機(jī)的選擇還是采用了基于最大密度與最大距離的思想，減小了隨機(jī)性帶來的影響同時(shí)也減小了離群點(diǎn)對(duì)算法的影響，因?yàn)殡x群點(diǎn)是屬于小密度數(shù)據(jù)，所以在基于這種改進(jìn)的情況下，是不會(huì)選到離群點(diǎn)的。然后與原來的串行K_means算法比較，本文采用了基于MapReduce的并列算法思想，在運(yùn)算的時(shí)效上有了很大的改進(jìn)。最后經(jīng)過在實(shí)驗(yàn)室的數(shù)據(jù)測(cè)試，本次算法的改進(jìn)大大的提高了K_means算法的準(zhǔn)確性，并且收斂速度也有了很大提升，在map節(jié)點(diǎn)越多的情況下效率越快，解決了在對(duì)大數(shù)據(jù)處理時(shí)間長(zhǎng)的問題。

參考文獻(xiàn):

[1]Han J，Kamber M，Pei J.數(shù)據(jù)挖掘概念與技術(shù)[M].機(jī)械工業(yè)出版社，2012.7.

[2]Dunham，M.H.著，郭崇慧，田鳳占，勒曉明等譯.數(shù)據(jù)挖掘教程[M].北京:清華大學(xué)出版社，2005.

[3]張?jiān)茲?，龔?數(shù)據(jù)挖掘原理與技術(shù)[M].北京:電子工業(yè)出版社，2004:123.