郭晨晨，朱紅康

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

?

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

郭晨晨，朱紅康

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

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

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

0 引言

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

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

1 算法

1.1 K-Means

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

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

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

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

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

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

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

K-Means算法如下:

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

輸出:K個(gè)簇的集合.

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

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

第三步:從D中選擇k個(gè)對(duì)象作為最初的簇中心;

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

第五步:計(jì)算每個(gè)簇中所有對(duì)象的平均值獲得每個(gè)類(lèi)的類(lèi)中心,替代最初的簇中心;

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

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

1.2 K-Medoids

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

K-Mediods算法如下:

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

輸出:K個(gè)簇的集合.

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

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

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

第四步:計(jì)算用非種子對(duì)象代替種子對(duì)象的總代價(jià)C;

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

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

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

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

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

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

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

圖1 K-Means聚類(lèi)示意圖

圖2 K-Mediods聚類(lèi)示意圖

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

圖3 K-Means聚類(lèi)中心分布圖

圖4 K-Mediods聚類(lèi)中心分布圖

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

圖5 K-Means異常點(diǎn)處理圖

圖6 K-Mediods異常點(diǎn)處理圖

3 結(jié)論

本文介紹了我們常見(jiàn)的兩種聚類(lèi)算法,通過(guò)KEEL(Knowledge Extraction based on Evolutionary Learning)提供的模擬軟件,對(duì)數(shù)據(jù)量相對(duì)較大的數(shù)據(jù)集進(jìn)行了聚類(lèi)分析．顯示出在數(shù)據(jù)集較大的情況下,K-Means和K-Mediods聚類(lèi)效果間的差異．由于后者更加合理地處理異常值,因此聚類(lèi)結(jié)果收到的噪聲數(shù)據(jù)的干擾明顯小于K-Means．對(duì)于大數(shù)據(jù)處理中很多龐大數(shù)據(jù)問(wèn)題,K-Mediods顯然更具有開(kāi)發(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] 王開(kāi)軍,李 健,張軍英,等.聚類(lèi)分析中類(lèi)數(shù)估計(jì)方法的實(shí)驗(yàn)比較[J].計(jì)算機(jī)工程,2008,34(9):198-199

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

[6] 儲(chǔ)岳中.一類(lèi)基于貝葉斯信息準(zhǔn)則的k均值聚類(lèi)算法[J].安徽工業(yè)大學(xué)學(xué)報(bào)(自然科學(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-),男,山西長(zhǎng)治人,山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院在讀碩士研究生，主要從事計(jì)算機(jī)應(yīng)用研究．

1672-2027(2016)02-0056-04

TP18

A