郁啟麟

(中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,徐州 221116)

K-means算法初始聚類中心選擇的優(yōu)化①

郁啟麟

(中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,徐州 221116)

迄今為止,在數(shù)據(jù)挖掘領(lǐng)域,人們已經(jīng)實(shí)現(xiàn)了多種聚類算法,其中使用最廣泛的當(dāng)屬K-means聚類算法.然而,在數(shù)據(jù)挖掘中,K-means算法面臨的一個(gè)主要問(wèn)題就是初始中心點(diǎn)選擇問(wèn)題.本文提出了一種結(jié)合關(guān)系矩陣和度中心性(Degree Centrality)的分析方法,從而確定K-means算法初始的k個(gè)中心點(diǎn).與傳統(tǒng)方法相比,本文算法可得到更加優(yōu)質(zhì)的聚類結(jié)果.實(shí)驗(yàn)結(jié)果表明該算法的有效性和可行性.

數(shù)據(jù)挖掘;度中心性;K-means算法;聚類

1 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展,人們已經(jīng)進(jìn)入到了大數(shù)據(jù)時(shí)代,并且已經(jīng)真正體會(huì)到無(wú)邊際的海量數(shù)據(jù).數(shù)據(jù)挖掘技術(shù)的實(shí)現(xiàn),使人們可以利用這些海量數(shù)據(jù),發(fā)掘出可供人們決策的知識(shí).現(xiàn)有的數(shù)據(jù)挖掘方法有多種,主要包括關(guān)聯(lián)規(guī)則分析、聚類分析、離群點(diǎn)分析、分類等.其中聚類是一種無(wú)監(jiān)督學(xué)習(xí)的分類技術(shù),聚類的目的是使同一類中的數(shù)據(jù)的相似度盡可能高,而且不同類的相異度也盡可能高.從而得到數(shù)據(jù)中潛在的分類信息.

主要的聚類算法有:基于劃分方法、基于層次方法、基于密度方法、基于網(wǎng)格方法和基于模型方法. K-means算法是一種基于劃分的聚類分析方法,該算法的運(yùn)行效率較高,因此廣泛應(yīng)用于各個(gè)領(lǐng)域的聚類分析中,目前的許多算法都是圍繞著它進(jìn)行創(chuàng)新和拓展.但是,在傳統(tǒng)的K-means聚類分析中存在很多缺陷:(1)在K-means算法中,k是需要事先給定的.(2)在K-means算法中,初始中心的選擇對(duì)聚類結(jié)果影響比較大,若初始聚類中心選擇的不合適,那么就無(wú)法得到預(yù)期的聚類結(jié)果,這也是K-means算法的一個(gè)缺點(diǎn). (3)一些噪聲點(diǎn)和孤立點(diǎn)會(huì)對(duì)最終的聚類結(jié)果產(chǎn)生較大的影響.

目前,針對(duì)以上K-means算法的缺點(diǎn),很多學(xué)者提出了對(duì)K-means算法的優(yōu)化方法,如文獻(xiàn)[1]采用密度敏感的相似性度量計(jì)算對(duì)象密度的方法產(chǎn)生初始類中心,從而優(yōu)化聚類結(jié)果的穩(wěn)定性;文獻(xiàn)[2]提出一種基于人工魚(yú)群的優(yōu)化算法AFS-KM,利用信息增益對(duì)屬性進(jìn)行加權(quán),從而計(jì)算實(shí)體之間的距離.文獻(xiàn)[3]通過(guò)找出相距最遠(yuǎn)的數(shù)據(jù)對(duì)象作為初始聚類中心,然后對(duì)該聚類進(jìn)行分裂,反復(fù)迭代直到找出指定個(gè)數(shù)的初始聚類中心;文獻(xiàn)[4]結(jié)合Ap算法和最大最小距離算法確定K-means算法的最佳聚類個(gè)數(shù).文獻(xiàn)[5]利用大數(shù)據(jù)技術(shù),結(jié)合Hadoop平臺(tái)的map和reduce框架優(yōu)化K-means算法;文獻(xiàn)[6]提出了一種新的NDK-means方法,它通過(guò)標(biāo)準(zhǔn)差確定有效密度半徑,然后挑取高密度區(qū)域中的具有代表性的樣本點(diǎn),用這些樣本點(diǎn)作為初始聚類中心;文獻(xiàn)[7]基于結(jié)果敏感性和局部最優(yōu)而提出了一種K-meansCAN算法,利用不同聚類結(jié)果的子簇的交集建立帶權(quán)連通圖,根據(jù)圖中各節(jié)點(diǎn)的連通性合并子簇;文獻(xiàn)[8]將K-means算法和蟻群算法相結(jié)合,提高了聚類質(zhì)量;文獻(xiàn)[9]采用密度方法和對(duì)象間的距離確定初始聚類中心,選擇相距最遠(yuǎn)的k個(gè)處于高密度區(qū)域的點(diǎn)作為初始聚類中心.文獻(xiàn)[10]利用核系數(shù)解決非凸問(wèn)題,確定合適的聚類個(gè)數(shù).文獻(xiàn)[11]利用最大最小距離算法,根據(jù)已經(jīng)選取到的中心點(diǎn),選取與之距離乘機(jī)最大的的高密度點(diǎn)作為當(dāng)前初始中心點(diǎn).

本文在研究K-means算法及其一些改進(jìn)算法的基礎(chǔ)上,提出一種新的選取初始聚類中心的方法,該方法與關(guān)系對(duì)稱矩陣和度社會(huì)網(wǎng)絡(luò)分析中的度中心性相結(jié)合確定初始聚類中心,將所得到的聚類中心應(yīng)用于聚類算法當(dāng)中,在穩(wěn)定聚類結(jié)果的同時(shí),使得聚類結(jié)果有了較大提高.

2 K-means算法簡(jiǎn)介

K-means算法根據(jù)聚類的個(gè)數(shù)k,將已有的數(shù)據(jù)集劃分成k個(gè)簇.算法采用迭代更新的方法,在第一輪中,根據(jù)隨機(jī)選定的k個(gè)初始中心點(diǎn)將對(duì)象集劃分成k個(gè)初始簇,之后根據(jù)每個(gè)簇的中心迭代重新劃分每個(gè)對(duì)象所屬的類,而每個(gè)簇的平均值將被作為下一輪迭代的中心點(diǎn).直到中心點(diǎn)不再發(fā)生改變,即產(chǎn)生了最后的聚類結(jié)果.

2.1 K-means算法的主要步驟

假設(shè)將數(shù)據(jù)集D包含n個(gè)數(shù)據(jù)對(duì)象.該算法將D中的對(duì)象分配到k個(gè)簇W1,W2…WK中,每個(gè)簇的中心設(shè)為c1,c2…ck,其中,其中是簇中數(shù)據(jù)點(diǎn)的個(gè)數(shù).對(duì)象與該簇的代表之間的歐式距離用dist(x,ci)表示,聚類效果的好壞用目標(biāo)函數(shù)目標(biāo)函數(shù)E就是每個(gè)數(shù)據(jù)點(diǎn)與其所在簇的簇中心的距離總和,隨著聚類次數(shù)不斷增加,E值也會(huì)動(dòng)態(tài)的改變,理想狀況下,E值會(huì)逐漸收縮變小,簇內(nèi)對(duì)象的相互距離會(huì)變小,簇間的相互距離會(huì)逐漸變大.因此,算法通過(guò)不斷尋求更加小而穩(wěn)定的E值來(lái)尋求好的聚類方案,當(dāng)E逐漸收縮到極小值時(shí),會(huì)產(chǎn)生更好的聚類結(jié)果.

2.2 K-means算法描述

3 度中心性簡(jiǎn)介

度中心性(Degree Centrality)是在社會(huì)網(wǎng)絡(luò)分析中分析節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中重要程度的一個(gè)很重要和直接的方法.與一個(gè)節(jié)點(diǎn)相連接的其他節(jié)點(diǎn)個(gè)數(shù)越多,就表示這個(gè)節(jié)點(diǎn)的度中心性越高,那么這個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性就越高.

在擁有N個(gè)節(jié)點(diǎn)的無(wú)向圖G中,節(jié)點(diǎn)i的度中心性表示該節(jié)點(diǎn)與其它N-1個(gè)節(jié)點(diǎn)的聯(lián)系程度.即用于計(jì)算節(jié)點(diǎn)i與其它N-1個(gè)節(jié)點(diǎn)的直接連接數(shù)量,i≠j表示節(jié)點(diǎn)自身與自身的連接可以忽略不計(jì).度中心性的計(jì)算可以簡(jiǎn)單地將節(jié)點(diǎn)i在矩陣中對(duì)應(yīng)的行或列所在的單元格值加總.

度在有向網(wǎng)絡(luò)圖中分為入度和出度,例如微博中的關(guān)注關(guān)系.因?yàn)楸疚膶⑾嗷ゾ嚯x小于閾值的兩個(gè)節(jié)點(diǎn)看作是相互連接的,所以關(guān)系對(duì)稱矩陣轉(zhuǎn)化為無(wú)向圖,不區(qū)分出度和入度.

4 初始中心點(diǎn)的確定

針對(duì)初始中心點(diǎn)對(duì)聚類結(jié)果的影響,本文提出了一種基于在關(guān)系矩陣中測(cè)量度中心性的方式優(yōu)化初始中心點(diǎn)的選擇.首先,將對(duì)象集N內(nèi)的節(jié)點(diǎn)計(jì)算兩兩之間的距離,因?yàn)椴煌木嚯x計(jì)算方法不會(huì)對(duì)本算法造成大的影響,所以為了降低計(jì)算量,本文采用曼哈頓距離.設(shè)立一個(gè)閾值L,根據(jù)反復(fù)測(cè)試,L取任意兩個(gè)節(jié)點(diǎn)之間平均距離的一半.兩個(gè)節(jié)點(diǎn)之間的距離如果小于這個(gè)閾值,建立節(jié)點(diǎn)之間的關(guān)系對(duì)稱矩陣時(shí),我們將值設(shè)置為1,即認(rèn)為這兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中是相互連接的;如果距離大于閾值,則設(shè)為0,即認(rèn)為這兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中是無(wú)連接的.遍歷所有對(duì)象的行向量,將度中心性最高的節(jié)點(diǎn)設(shè)為初始中心點(diǎn),并將與之相連的節(jié)點(diǎn)從矩陣中刪除.繼續(xù)迭代遍歷剩下的節(jié)點(diǎn),直到找到k個(gè)中心點(diǎn).

設(shè)目標(biāo)對(duì)象集N={X1,X2,X3,…Xn},包含n個(gè)對(duì)象,每個(gè)對(duì)象有m個(gè)屬性,設(shè)每個(gè)對(duì)象Xi={xi1,xi2,…xim},從數(shù)據(jù)集N中選出k個(gè)中心點(diǎn).

算法描述如下:

(1)預(yù)處理數(shù)據(jù)集N.

(4)遍歷所有節(jié)點(diǎn),找出度中心性最高的節(jié)點(diǎn),然后在矩陣中刪除該節(jié)點(diǎn),由于類中心點(diǎn)相互之間的距離應(yīng)該盡可能遠(yuǎn),且相互連接的節(jié)點(diǎn)是抱團(tuán)存在的,所以刪除與之相連接的p個(gè)節(jié)點(diǎn),所以n階矩陣轉(zhuǎn)變?yōu)閚-p+1階矩陣.

(5)在形成的新矩陣中繼續(xù)找出度中心性最高的節(jié)點(diǎn),設(shè)為第2個(gè)中心點(diǎn),并在方陣中刪除與之相連接的節(jié)點(diǎn).利用迭代算法繼續(xù)循環(huán)遍歷直到找出第k個(gè)中心點(diǎn).

5 實(shí)驗(yàn)仿真分析

圖1為本文算法的流程圖.為了方便計(jì)算,并能表示出原始算法與改進(jìn)算法的區(qū)別,所以本文使用java語(yǔ)言隨機(jī)生成7維的仿真數(shù)據(jù)對(duì)象,因?yàn)楝F(xiàn)實(shí)數(shù)據(jù)中每一維的差距有限,所以將每一維的屬性用0-200的整數(shù)型數(shù)字表示.并用java語(yǔ)言生成對(duì)象對(duì)稱關(guān)系矩陣.分別用原始方法選擇的初始中心點(diǎn)和本方法選擇的初始中心點(diǎn)比較聚類過(guò)程消耗的時(shí)間和聚類最終的效果.

圖1 實(shí)驗(yàn)流程圖

圖2 為選取的前10個(gè)節(jié)點(diǎn)根據(jù)相互之間的距離和閾值L轉(zhuǎn)化而成的0和1的關(guān)系對(duì)稱矩陣,由于是無(wú)向圖,本文這里將節(jié)點(diǎn)本身看作是有連接的,這樣對(duì)最終的初始中心點(diǎn)選取結(jié)果并不會(huì)產(chǎn)生影響.

圖2 選取10個(gè)節(jié)點(diǎn)的關(guān)系矩陣

圖3 表示100個(gè)節(jié)點(diǎn)利用如圖2所示的關(guān)系對(duì)稱生成的社會(huì)網(wǎng)絡(luò)關(guān)系圖.我們可以很明顯的看出相互之間距離小且連接的節(jié)點(diǎn)是抱團(tuán)存在的;又因?yàn)檫x取的初始中心點(diǎn)距離應(yīng)該盡可能的遠(yuǎn),所以我們?cè)谶x取每個(gè)初始中心點(diǎn)后,因?yàn)榕c之相鄰的節(jié)點(diǎn)將不會(huì)作為我們選取下一個(gè)聚類中心的候選節(jié)點(diǎn),所以我們?cè)诰仃嚲W(wǎng)絡(luò)中刪除與之相鄰的節(jié)點(diǎn).

圖3 包含100個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)連接圖

本文為了更準(zhǔn)確的表示比較結(jié)果,所以將每種算法反復(fù)運(yùn)行30次,用最終的四舍五入后的平均值去表示實(shí)驗(yàn)性能和結(jié)果.以下實(shí)驗(yàn)結(jié)果均為反復(fù)測(cè)試的平均值.

表1表示在沒(méi)有離群點(diǎn)的對(duì)象集中測(cè)試的實(shí)驗(yàn)結(jié)果,本文使用兩種方法的運(yùn)行時(shí)間和E值來(lái)作為衡量指標(biāo).這里的E值表示所有節(jié)點(diǎn)與最終所在的簇中心距離之和,E值的大小體現(xiàn)了最終子簇成員之間的緊密程度.

表1 不包含離群點(diǎn)的實(shí)驗(yàn)結(jié)果

表2表示在含有離群點(diǎn)的對(duì)象集中分別使用兩種方法的運(yùn)行時(shí)間和E值對(duì)比,為了說(shuō)明改進(jìn)算法的有效性,我們將添加的離群點(diǎn)設(shè)為原算法的其中一個(gè)初始中心點(diǎn).

表2 包含離群點(diǎn)的實(shí)驗(yàn)結(jié)果

除了與傳統(tǒng)方法比較之外,本文還與最新的文獻(xiàn)中的改進(jìn)方法進(jìn)行比較,本文選取了文獻(xiàn)[1],文獻(xiàn)[3]和文獻(xiàn)[6]中的優(yōu)化初始中心選取方法進(jìn)行實(shí)驗(yàn)比較,實(shí)驗(yàn)中使用了包含離群點(diǎn)的500個(gè)實(shí)驗(yàn)對(duì)象,并且使用經(jīng)過(guò)反復(fù)實(shí)驗(yàn)得到的理想K值,用運(yùn)行時(shí)間、迭代次數(shù)和E值來(lái)表示實(shí)驗(yàn)結(jié)果,比較結(jié)果如表3所示.

表3 與近期改進(jìn)算法的比較結(jié)果

通過(guò)表1和表2我們可以看出,在平滑的數(shù)據(jù)集中進(jìn)行聚類處理,改進(jìn)的算法與傳統(tǒng)算法在時(shí)間性能上的聚類結(jié)果上沒(méi)有優(yōu)勢(shì),但是在含有離群點(diǎn)數(shù)據(jù)集中,改進(jìn)的算法的聚類結(jié)果明顯優(yōu)于傳統(tǒng)算法.

通過(guò)表3可以看出,本文中提出的算法與近期文獻(xiàn)提出的方法相比較而言,本文提出的改進(jìn)算法在時(shí)間性能上有一定的劣勢(shì),但是在類內(nèi)距和迭代次數(shù)這兩個(gè)指標(biāo)上優(yōu)于近期文獻(xiàn)中提出的算法,可以產(chǎn)生更加穩(wěn)定和優(yōu)質(zhì)的聚類結(jié)果.

通過(guò)以上實(shí)驗(yàn)結(jié)果可以得出結(jié)論,由于本文中提出的算法在聚類之前要生成對(duì)稱矩陣,并且要迭代計(jì)算每個(gè)節(jié)點(diǎn)的度中心性,所以造成了大量的時(shí)間消耗,但是通過(guò)這種方式可以找到更加優(yōu)質(zhì)的初始聚類中心,從而能夠生成更加精確和穩(wěn)定的聚類結(jié)果,所以本文提出的算法更適合體量小的聚類對(duì)象集,在實(shí)際應(yīng)用中是可行的.

6 結(jié)語(yǔ)

傳統(tǒng)的K-means算法在進(jìn)行聚類時(shí)隨機(jī)的選取對(duì)象集合中的k個(gè)點(diǎn)作為初始聚類中心,這導(dǎo)致了該算法失去了穩(wěn)定性,容易產(chǎn)生不理想的結(jié)果.本文提出了一種利用關(guān)系矩陣和度數(shù)中心度的方法去優(yōu)化K-means算法中的初始中心節(jié)點(diǎn)選擇問(wèn)題,得到了更加優(yōu)化的初始中心點(diǎn).本文通過(guò)用java代碼生成的測(cè)試對(duì)象集和運(yùn)行代碼,通過(guò)與傳統(tǒng)方法以及最新的改進(jìn)算法進(jìn)行比較,證明了本算法的高穩(wěn)定性.雖然生成矩陣的過(guò)程造成了大量的時(shí)間消耗,在處理海量數(shù)據(jù)的性能上有一定的局限性;但是從一方面講,本算法又減少了聚類過(guò)程中的迭代次數(shù),得到更加穩(wěn)定和高質(zhì)量的聚類結(jié)果,所以這些代價(jià)是在實(shí)際應(yīng)用中是可以付出的.今后也會(huì)進(jìn)一步完善本文提出的算法.

1汪中,劉貴全,陳恩紅.一種優(yōu)化初始中心點(diǎn)的K-means算法.模式識(shí)別與人工智能,2009,22(2):299–304.

2于海濤,賈美娟,王慧強(qiáng),等.基于人工魚(yú)群的優(yōu)化K-means聚類算法.計(jì)算機(jī)科學(xué),2012,39(12):60–64.

3陳光平,王文鵬,黃俊.一種改進(jìn)初始聚類中心選擇的K-means算法.小型微型計(jì)算機(jī)系統(tǒng),2012,33(6):1320–1323.

4周世兵,徐振源,唐旭清.新的K-均值算法最佳聚類數(shù)確定方法.計(jì)算機(jī)工程與應(yīng)用,2010,46(16):27–31.

5趙慶.基于hadoop平臺(tái)下的k均值高效算法的研究[碩士學(xué)位論文].西安:西安電子科技大學(xué),2014.

6何云斌,劉雪嬌,王知強(qiáng),等.基于全局中心的高密度不唯一的K-means算法研究.計(jì)算機(jī)工程與應(yīng)用,2016,52(1):48–54.

7雷小鋒,謝昆青,林帆,等.一種基于K-Means局部最優(yōu)性的高效聚類算法.軟件學(xué)報(bào),2008,19(7):1683–1692.

8莫錦萍,陳琴,馬琳,等.一種新的K-Means蟻群聚類算法.廣西科學(xué)院學(xué)報(bào),2008,24(4):284–286.

9賴玉霞,劉建平.K-means算法的初始聚類中心的優(yōu)化.計(jì)算機(jī)工程與應(yīng)用,2008,44(10):147–149.

10 Yu S,Tranchevent LC,Moor BD,et al.Optimized data fusion for Kernel k-means clustering.IEEE Trans.on Pattern Analysis&Machine Intelligence,2012,34(5): 1031–1039.

11 Li MJ,Ng MK,Cheung YM,et al.Agglomerative fuzzy k-means clustering algorithm with selection of number of clusters.IEEE Trans.on Knowledge&Data Engineering, 2008,20(11):1519–1534.

Optimization of Initial Clustering Centers Selection Method for K-MeansAlgorithm

YU Qi-Lin

(School of Computer Science and Technology,China University of Mining and Technology,Xuzhou 221116,China)

So far,in the field of data mining,people have achieved a variety of algorithms of clustering.And the most widely used is K-means clustering algorithm.But the main problem of K-means is the initial center selection problem. In this paper,a method is proposed to determine the initial K centers of the K-means algorithm through the relationship matrix and the Degree Centrality.Compared with the traditional algorithm,the proposed algorithm can get the better clustering result.Experimental results have proved the validity and feasibility of this algorithm.

data mining;degree centrality;K-means algorithm;clustering

2016-08-01;收到修改稿時(shí)間:2016-09-23

10.15888/j.cnki.csa.005733