郭晨晨，朱紅康

(山西師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西 臨汾 041000)

?

基于K-均值和K-中心點算法的大數(shù)據(jù)集分析

郭晨晨，朱紅康

(山西師范大學(xué) 數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院，山西 臨汾 041000)

大數(shù)據(jù)已然成為當(dāng)今世界最熱門的話題之一，對于海量數(shù)據(jù)處理方法的研究一直是重要的科研領(lǐng)域，將原有的數(shù)據(jù)統(tǒng)計分析方法加入到大數(shù)據(jù)分析中也是必然的研究方向.文章選取了 K-Means 及其K-Mediods算法對KEEL的transaction10k數(shù)據(jù)集進(jìn)行評估.該數(shù)據(jù)包含較大的數(shù)據(jù)容量，因此對于模擬大數(shù)據(jù)環(huán)境有很好的作用.可以想象到，現(xiàn)實世界龐大的數(shù)據(jù)真實客觀地反映到圖像中必然會為分析數(shù)據(jù)帶來極大的便利.輸入到這些算法中是隨機(jī)分布的數(shù)據(jù)點，并根據(jù)其相似度產(chǎn)生的聚類已經(jīng)生成.比較結(jié)果表明，K-Medoids在種子對象的選取和聚類間重疊的合理控制方面要比K-均值更有優(yōu)勢.

大數(shù)據(jù);聚類;數(shù)據(jù)處理;K-Means;K-Medoids

0 引言

海量數(shù)據(jù)指數(shù)型的增長提前宣告了大數(shù)據(jù)時代的到來,而作為大數(shù)據(jù)核心的數(shù)據(jù)挖掘成為信息時代研究的核心領(lǐng)域．?dāng)?shù)據(jù)挖掘是指從大量的數(shù)據(jù)中通過算法搜索隱藏于其中信息的過程,這些信息是清晰的、易理解的、有用的、合理的．而數(shù)據(jù)挖掘的主要工作任務(wù)是將現(xiàn)有數(shù)據(jù)或者經(jīng)簡單分析的“粗加工”數(shù)據(jù)“加工”成包含知識的有用信息的過程[1]．

數(shù)據(jù)挖掘服務(wù)端接收來自客戶端的原始數(shù)據(jù)、元數(shù)據(jù)和可能的特定領(lǐng)域知識．海量數(shù)據(jù)通過數(shù)據(jù)挖掘的篩選、提取、改造后通常不再巨大,這也為詳細(xì)研究數(shù)據(jù)提供可能性．經(jīng)過“粗加工”的數(shù)據(jù)通常還需要用相應(yīng)的聚類算法進(jìn)一步“細(xì)加工”,聚類是數(shù)據(jù)挖掘中常見的最常見的技術(shù),它是一種對抽象或現(xiàn)實事物的認(rèn)知、分類和歸納過程．在數(shù)據(jù)處理方面,其探索能力、構(gòu)建預(yù)測模型以及克服數(shù)據(jù)中的“噪聲”方面具有巨大的潛力．?dāng)?shù)據(jù)集通過聚類形成不同的簇進(jìn)而形成圖像,這樣有利于對數(shù)據(jù)集直觀性的分析和規(guī)律、知識的表露．常見聚類方法主要是基于距離的、層次的、網(wǎng)格的或者密度的,每種方法都有其優(yōu)勢和局限性．而本文主要介紹基于距離的K-Means及其改進(jìn)算法K-Medoids．

1 算法

1.1 K-Means

K-Means是是典型的基于原型的目標(biāo)函數(shù)聚類方法的代表,它是數(shù)據(jù)點到原型的某種距離作為優(yōu)化的目標(biāo)函數(shù),利用函數(shù)求極值的方法得到迭代運算的調(diào)整規(guī)則．K-means算法以歐式距離作為相似度測度,它是求對應(yīng)某一初始聚類中心向量的最優(yōu)分類,使得評價指標(biāo)最?。惴ú捎谜`差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)．

K-Means首先需要事先選取若干個中心點,這一過程主要依靠用戶對數(shù)據(jù)的預(yù)先估計．最初中心點的選取直接影響聚類的效果和最終的聚類數(shù)量．當(dāng)然,為了降低這部分的人為誤差,可以使用很多方法來實現(xiàn),諸如:

1)層次聚類法:利用層次聚類的迭代算法尋找初始中心數(shù)目[2]．

2)穩(wěn)定性法:通過對一個數(shù)據(jù)集的多次采樣,利用聚類算法分別進(jìn)行聚類,比較它們間的相似性最終確定中心數(shù)目[3]．

3)系統(tǒng)演化法:系統(tǒng)演化方法能提供關(guān)于所有聚類之間的相對邊界距離或可分程度,它適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)[4]．

4)canopy法:參考文獻(xiàn)[5]．

5)貝葉斯信息準(zhǔn)則法:參考文獻(xiàn)[6]．

K-Means算法如下:

輸入:結(jié)果簇的個數(shù)K,包含n個對象的數(shù)據(jù)集D；

輸出:K個簇的集合.

第一步:輸入數(shù)據(jù)集和K的值;

第二步:若K=1,則退出;

第三步:從D中選擇k個對象作為最初的簇中心;

第四步:將其余對象分配到最近的種子對象所代表的簇中;

第五步:計算每個簇中所有對象的平均值獲得每個類的類中心,替代最初的簇中心;

第六步:重復(fù)上面兩步,直到每個簇的聚類中心不再改變．

算法成功的標(biāo)準(zhǔn)在于衡量迭代次數(shù)或者說是聚類中心變化的次數(shù)．

1.2 K-Medoids

K-Mediods是基于K-means的改進(jìn)算法．在K-means算法中,由于中心點的選取是基于當(dāng)前簇中所有對象的平均值,因而容易受到異常值或者離群值的影響．為了克服這樣的問題,從而提出了新的中心點選取方法,即從當(dāng)前簇中選取這樣的一個點——它到當(dāng)前簇中所有點的距離是最小的,作為新的中心點．

K-Mediods算法如下:

輸入:結(jié)果簇的個數(shù)K,包含n個對象的數(shù)據(jù)集D.

輸出:K個簇的集合.

第一步:從數(shù)據(jù)集D中隨機(jī)選擇k個對象作為初始的種子對象;

第二步:將其余對象分配到最近的種子對象所代表的k個簇中;

第三步:隨機(jī)選擇一個非種子對象;

第四步:計算用非種子對象代替種子對象的總代價C;

第五步:如果C<0,則用非種子對象替換種子對象,從而產(chǎn)生新的對象集合;

第六步:除非種子對象不再發(fā)生變化,否則重復(fù)四步過程．

2 實驗

本文分別將K-Means和K-Mediods算法應(yīng)用于transaction10k數(shù)據(jù)集[7]上,程序是基于MATLAB編譯實現(xiàn)的．由于該算法相對簡單,因此時間消耗并不多,只是毫秒級別．當(dāng)然在不同性能的計算機(jī)中運行的時間有一些差別．隨機(jī)交易10 000次,商品及數(shù)據(jù)生成見表1.

表1 transaction10k數(shù)據(jù)集基本信息

K-Means的聚類效果如圖1所示,幾個聚類間存在著明顯的重疊,這是由于K-Means本身的缺陷導(dǎo)致的．

K-Mediods的聚類效果如圖2所示,聚類間的重疊部分相比K-Means明顯減少,這表明基于中心點或者中心對象劃分方法具有一定的優(yōu)勢．

圖1 K-Means聚類示意圖

圖2 K-Mediods聚類示意圖

圖3和圖4分別表示了K-Means和K-Mediods各個聚類中心的位置．可以發(fā)現(xiàn),在不同的種子對象迭代算法影響下,聚類中心的位置也存在很大的不同．

圖3 K-Means聚類中心分布圖

圖4 K-Mediods聚類中心分布圖

圖5、圖6展示了K-Means和K-Mediods對于異常值得處理,容易發(fā)現(xiàn),K-Mediods在這一方面顯示了強(qiáng)大的能力,這也是K-Mediods抗噪聲能力最明顯的體現(xiàn)．

圖5 K-Means異常點處理圖

圖6 K-Mediods異常點處理圖

3 結(jié)論

本文介紹了我們常見的兩種聚類算法,通過KEEL(Knowledge Extraction based on Evolutionary Learning)提供的模擬軟件,對數(shù)據(jù)量相對較大的數(shù)據(jù)集進(jìn)行了聚類分析．顯示出在數(shù)據(jù)集較大的情況下,K-Means和K-Mediods聚類效果間的差異．由于后者更加合理地處理異常值,因此聚類結(jié)果收到的噪聲數(shù)據(jù)的干擾明顯小于K-Means．對于大數(shù)據(jù)處理中很多龐大數(shù)據(jù)問題,K-Mediods顯然更具有開發(fā)和應(yīng)用潛力．

[1] VELMURUGAN T,SANTHANAM T.A survey of partition based clustering algorithms in data mining:an experimental approach.Information Technology Journal,2011,10 (3):478-484

[2] PANG Ningtan.MICHELINE Steinbach,VIPIN kumar.數(shù)據(jù)挖掘?qū)д?北京：人民郵電出版，2011:320-327

[3] HAN Jiawei.MICHELINE kamber, PEI Jian.數(shù)據(jù)挖掘概念與技術(shù).北京：機(jī)械工業(yè)出版社,2012：295-304

[4] 王開軍,李 健,張軍英,等.聚類分析中類數(shù)估計方法的實驗比較[J].計算機(jī)工程,2008,34(9):198-199

[5] 毛典輝.基于MapRecude的Canopy-kmeans改進(jìn)算法[J].計算機(jī)工程與應(yīng)用,2012,48(27):22-26

[6] 儲岳中.一類基于貝葉斯信息準(zhǔn)則的k均值聚類算法[J].安徽工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2010(4):409-412

Analysis of Large Data Sets Based on K-Means and K-Mediods Algorithm

GUO Chenchen,ZHU Hongkang

(School of mathematics and computer science,Shanxi Normal University,Linfen Shanxi 041000, China)

Big data has already become one of the hottest topics in today’s world, Research on massive data processing methods is always an important research area.The original data statistics analysis method to join the big data analysis is also an inevitable research direction.In this paper the two most popular clustering algorithms K-Means and K-Medoids are evaluated on dataset transaction10k of KEEL.You can imagine, The reality of the huge data in the world objectively reflected in the image is bound to bring great convenience for the analysis of data.The input to these algorithms are randomly distributed data points and based on their similarity clusters has been generated.The comparison results show that time taken in cluster head selection and space complexity of overlapping of cluster is much better in K-Medoids than K-Means.

Big data； Clustering； Data processing； K-Medoids； K-Means

2016-04-20

郭晨晨(1992-),男,山西長治人,山西師范大學(xué)數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院在讀碩士研究生，主要從事計算機(jī)應(yīng)用研究．

1672-2027(2016)02-0056-04

TP18

A