基于K-mean聚類算法的海量數(shù)據(jù)分析方法*

金巨波

（黑龍江財(cái)經(jīng)學(xué)院 黑龍江哈爾濱 150001）

互聯(lián)網(wǎng)技術(shù)、傳感器技術(shù)的發(fā)展應(yīng)用為社會進(jìn)步積攢了海量數(shù)據(jù)信息，計(jì)算機(jī)是處理海量數(shù)據(jù)的中轉(zhuǎn)站.爆炸式的數(shù)據(jù)產(chǎn)生速度雖然方便了人們對各領(lǐng)域事物的加深了解與感知，豐富了信息來源，但同時(shí)也為計(jì)算機(jī)處理數(shù)據(jù)的性能帶來負(fù)擔(dān)，導(dǎo)致數(shù)據(jù)處理效率與質(zhì)量雙重下降［1］.Kmean聚類算法是處理大數(shù)據(jù)聚類分析的經(jīng)典方式，但由于聚類結(jié)果直接影響知識挖掘的優(yōu)劣，現(xiàn)代信息領(lǐng)域?qū)?shù)據(jù)聚類質(zhì)量要求甚高，傳統(tǒng)的K-mean聚類算法普遍存在計(jì)算量大數(shù)據(jù)處理效率低、收斂效果不理想等弊端［2］.為此，在Hadoop大規(guī)模數(shù)據(jù)分布式并行處理框架下運(yùn)行Kmean聚類算法，并采用遺傳算法將聚類問題轉(zhuǎn)化為求極值問題，以提高K-mean聚類算法在海量數(shù)據(jù)分析中的準(zhǔn)確度與效率.

1 基于K-mean聚類算法海量數(shù)據(jù)分析

1.1 傳統(tǒng)K-mean聚類算法的基本原理

K-means算法以距離為依據(jù)完成數(shù)據(jù)聚類，因?yàn)橐子趯?shí)現(xiàn)、可拓展性能優(yōu)被廣泛使用.算法運(yùn)行的思路如下：設(shè)定原始數(shù)據(jù)集并任意選定k個原始聚類中心，依次求取剩余全部樣本與原始中心的歐氏距離［3］；將樣本分配到對應(yīng)的聚類中心所述的類別之中，分配的依據(jù)是最小距離原則，即將距離較近的劃分到相同類之中；緊接著求取各個類別樣本的距離均值，此類別新的聚類中心由此得到，當(dāng)誤差平方和函數(shù)處于合理范圍內(nèi)時(shí)確定得到最終的聚類中心，輸出此時(shí)的聚類結(jié)果.傳統(tǒng)K-means算法的缺點(diǎn)是需要人工定義K的大小，增加了計(jì)算時(shí)間開銷.

采用式（1）所示的誤差平方和函數(shù)約束聚類誤差：

式（2）中，聚類類別數(shù)量為K，第i類樣本數(shù)量以及樣本均值分別表示為g、ei.

1.2 傳統(tǒng)K-means算法改進(jìn)策略

文章采用兩種策略改進(jìn)傳統(tǒng)K-means算法運(yùn)行性能，一方面在Hadoop大規(guī)模數(shù)據(jù)分布式并行處理框架下運(yùn)用MapReduce模型實(shí)現(xiàn)算法的并行化，優(yōu)化算法的運(yùn)行效率，節(jié)省時(shí)間開銷［4］；另一方面，基于遺傳算法完成K-means算法聚類運(yùn)算，將聚類轉(zhuǎn)化為求極值問題，提高算法自適應(yīng)計(jì)算的能力，聚類結(jié)果更加精準(zhǔn).一般情況下，K-means聚類算法處理大數(shù)據(jù)分類問題難以預(yù)先判斷聚類數(shù)量k的大?。?］，所以文章闡述的遺傳算法優(yōu)化K-means聚類需要在計(jì)算過程中確定k值.基于遺傳算法優(yōu)化K-means聚類算法的計(jì)算過程如下.

Step 1：遺傳操作編碼.因?yàn)榫垲愃惴ǖ木垲悢?shù)量k是在變化過程中確定，所以將k的編碼添加到原染色體編碼中，以更新染色體設(shè)計(jì)方式，W＝kw1w2…wk為更新后的染色體編碼形式.其中，染色體表達(dá)形式的長度由聚類數(shù)量k來決定，編碼方式較為靈活.

Step 2：還原聚類種群設(shè)置.聚類種群產(chǎn)生是隨機(jī)的，任意從中挑出k個個體，原始的聚類中心便使用這些個體來表示；隨后利用實(shí)數(shù)編碼法完成這組個體的編碼工作，得到一條染色體.

Step 3：確定聚類的適應(yīng)度函數(shù).K個聚類中心在染色體中產(chǎn)生后，聚類算法使用的輸入向量即為各個樣本向量，采用如下形式表示X＝，其中，輸入向量維數(shù)為m；基于公式計(jì)算歐氏距離并將樣本劃分到聚類中心為wi的類別中.類間距、類內(nèi)距是目標(biāo)函數(shù)需要考慮的重要變量，以此約束K-means算法呈現(xiàn)最優(yōu)的聚類結(jié)果，所以考慮這兩個變量設(shè)計(jì)目標(biāo)函數(shù)如下.

Step 4：遺傳操作.確定完遺傳算法迭代的基本參數(shù)與函數(shù)后即可開始選擇算子、交叉算子、變異算子等遺傳操作.

Step 5：算法終止條件判斷.當(dāng)遺傳算法達(dá)到迭代次數(shù)上限，或者誤差達(dá)到終止條件時(shí)，即可輸出聚類結(jié)果；反之，循環(huán)操作Step 3，直到獲得聚類輸出結(jié)果.

1.3 基于MapReduce模型的改進(jìn)K-means聚類算

改進(jìn)的K-means聚類算法在MapReduce模型下進(jìn)行優(yōu)化迭代的過程如下：

（1）輸入待聚類分析的計(jì)算機(jī)網(wǎng)絡(luò)數(shù)據(jù)集，輸出k個聚類中心，完成數(shù)據(jù)聚類.

（2）基于遺傳算法確定reducer函數(shù)的輸出結(jié)果并傳輸?shù)絤apper函數(shù)中，求取各個樣本數(shù)據(jù)與遺傳操作最近的簇中心距離［6］，此時(shí)得到數(shù)據(jù)樣本以及樣本歸屬的簇.

（3）mapper函數(shù)將輸出結(jié)果傳輸?shù)絚ombine函數(shù)中，同時(shí)完成相同簇對象合并工作，采用的方法是：求取不同簇樣本數(shù)據(jù)的維數(shù)之和，并總結(jié)樣本數(shù)據(jù)對象的數(shù)量.

（4）combine函數(shù)將運(yùn)算結(jié)果輸入reducer函數(shù)，經(jīng)過遺傳算法優(yōu)化求得準(zhǔn)確的聚類中心數(shù)量K，此時(shí)總結(jié)全部數(shù)據(jù)樣本的維數(shù)和、樣本對象總數(shù)情況，將遺傳操作獲得的中心值作為有效的K-means聚類算法中心［7］，并查看算法收斂情況.

（5）基于遺傳算法優(yōu)化后的K-means聚類算法獲得簇中心，實(shí)現(xiàn)數(shù)據(jù)聚類分析，步驟如下：①將輸入樣本數(shù)據(jù)集輸入到mapper函數(shù)中；②利用最后確定的最優(yōu)中心支求取樣本數(shù)據(jù)與k個簇之間的距離，獲得數(shù)據(jù)對象歸屬的簇；③mapper函數(shù)將計(jì)算完成的結(jié)果輸入到reducer函數(shù)中，完成數(shù)據(jù)收集工作，進(jìn)而得到最優(yōu)的網(wǎng)絡(luò)數(shù)據(jù)聚類結(jié)果.

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集設(shè)置

為測試文章改進(jìn)K-means聚類算法在處理海量計(jì)算機(jī)網(wǎng)絡(luò)中的有效性和優(yōu)勢，搭建分布式并行運(yùn)算環(huán)境，在局域網(wǎng)內(nèi)設(shè)置5臺計(jì)算機(jī)構(gòu)成Hadoop集群，將一臺計(jì)算機(jī)定義為Master節(jié)點(diǎn)，另外計(jì)算機(jī)定義為Slave節(jié)點(diǎn)；計(jì)算機(jī)均為2GB內(nèi)存，3.20GHz.在權(quán)威網(wǎng)絡(luò)數(shù)據(jù)庫中選取2.0×104條數(shù)據(jù)作為聚類實(shí)驗(yàn)使用的樣本數(shù)據(jù)集，采用模糊K-means聚類算法、傳統(tǒng)K-means聚類算法作為對比測試方法，這兩種算法運(yùn)行環(huán)境均為分布式運(yùn)行框架，以驗(yàn)證文章方法解決海量數(shù)據(jù)聚類的性能.

2.2 時(shí)間開銷分析

實(shí)驗(yàn)首先在單機(jī)環(huán)境下運(yùn)行文章方法，記錄該方法聚類不同數(shù)據(jù)量的時(shí)間開銷；隨后采用文章方法、模糊K-means聚類算法、傳統(tǒng)Kmeans聚類算法在Hadoop集群MapReduce模型上展開分布式并行聚類，記錄相應(yīng)的時(shí)間開銷情況，匯總四種情況下聚類花費(fèi)的時(shí)間，如圖1所示.

圖1中，文章方法在單機(jī)環(huán)境中運(yùn)行的時(shí)間低于分布式環(huán)境下運(yùn)行時(shí)間，這是因?yàn)榉植际江h(huán)境下改進(jìn)聚類算法需要遍歷所有數(shù)據(jù)集，花費(fèi)一定的時(shí)間.圖像總體趨勢顯示，隨著數(shù)據(jù)規(guī)模的增加，分布式環(huán)境下并行運(yùn)算算法數(shù)據(jù)聚類的時(shí)間有所降低，呈現(xiàn)傳統(tǒng)K-means聚類算法＞模糊K-means聚類算法＞文章方法的趨勢，其中文章采用方法花費(fèi)的時(shí)間最少、效率最高，這是因?yàn)樵摲椒ú捎眠z傳算法將聚類問題轉(zhuǎn)化為求極值問題，無需人工設(shè)置聚類中心k，提高了聚類算法的自適應(yīng)程度，處理海量數(shù)據(jù)的時(shí)間自然減少.

2.3 準(zhǔn)確度分析

2.2 小節(jié)各方法聚類測試的均方誤差情況，如表1所示.

表1 各方法的均方誤差統(tǒng)計(jì)／107

表1顯示，單機(jī)運(yùn)行環(huán)境下的文章聚類方法不僅效率低，而且聚類準(zhǔn)確度不理想，數(shù)據(jù)量為2.0×104時(shí)對應(yīng)的均方誤差高達(dá)4.125×107；而相同數(shù)據(jù)量環(huán)境下，文章方法在Hadoop集群MapReduce模型上運(yùn)行的聚類均方誤差僅約為1.713×107，精確度最高.這是因?yàn)槲恼路椒☉?yīng)用遺傳算法解決聚類中心確定問題，考慮K-means聚類算法類間距、類內(nèi)距兩個變量確定遺傳操作的適應(yīng)度函數(shù)，保障聚類結(jié)果達(dá)到最優(yōu)，因而提高了算法的準(zhǔn)確度.

3 結(jié)論

Hadoop分布式并行處理框架提供了海量網(wǎng)絡(luò)數(shù)據(jù)聚類分析的新出路，將數(shù)據(jù)聚類任務(wù)分布到集群計(jì)算機(jī)多個節(jié)點(diǎn)上，改變以往單個計(jì)算機(jī)處理數(shù)據(jù)的局面，大量節(jié)約數(shù)據(jù)聚類分析的時(shí)間開銷，數(shù)據(jù)分析效率得到提升.文章改進(jìn)的Kmeans聚類算法應(yīng)用該方法可提升網(wǎng)絡(luò)數(shù)據(jù)聚類的效率，同時(shí)基于遺傳算法將聚類問題視為求極值問題，聚類中心選取的隨機(jī)性降低，保障了海量數(shù)據(jù)聚類結(jié)果的精準(zhǔn)度，為劃分海量網(wǎng)絡(luò)數(shù)據(jù)類別提供了有效的解決方案.