K-means算法初始聚類中心選擇的優化①

郁啟麟

(中國礦業大學 計算機科學與技術學院,徐州 221116)

K-means算法初始聚類中心選擇的優化①

郁啟麟

(中國礦業大學 計算機科學與技術學院,徐州 221116)

迄今為止,在數據挖掘領域,人們已經實現了多種聚類算法,其中使用最廣泛的當屬K-means聚類算法.然而,在數據挖掘中,K-means算法面臨的一個主要問題就是初始中心點選擇問題.本文提出了一種結合關系矩陣和度中心性(Degree Centrality)的分析方法,從而確定K-means算法初始的k個中心點.與傳統方法相比,本文算法可得到更加優質的聚類結果.實驗結果表明該算法的有效性和可行性.

數據挖掘;度中心性;K-means算法;聚類

1 引言

隨著互聯網的不斷發展,人們已經進入到了大數據時代,并且已經真正體會到無邊際的海量數據.數據挖掘技術的實現,使人們可以利用這些海量數據,發掘出可供人們決策的知識.現有的數據挖掘方法有多種,主要包括關聯規則分析、聚類分析、離群點分析、分類等.其中聚類是一種無監督學習的分類技術,聚類的目的是使同一類中的數據的相似度盡可能高,而且不同類的相異度也盡可能高.從而得到數據中潛在的分類信息.

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

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

本文在研究K-means算法及其一些改進算法的基礎上,提出一種新的選取初始聚類中心的方法,該方法與關系對稱矩陣和度社會網絡分析中的度中心性相結合確定初始聚類中心,將所得到的聚類中心應用于聚類算法當中,在穩定聚類結果的同時,使得聚類結果有了較大提高.

2 K-means算法簡介

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

2.1 K-means算法的主要步驟

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

2.2 K-means算法描述

3 度中心性簡介

度中心性(Degree Centrality)是在社會網絡分析中分析節點在整個網絡中重要程度的一個很重要和直接的方法.與一個節點相連接的其他節點個數越多,就表示這個節點的度中心性越高,那么這個節點在網絡中的重要性就越高.

在擁有N個節點的無向圖G中,節點i的度中心性表示該節點與其它N-1個節點的聯系程度.即用于計算節點i與其它N-1個節點的直接連接數量,i≠j表示節點自身與自身的連接可以忽略不計.度中心性的計算可以簡單地將節點i在矩陣中對應的行或列所在的單元格值加總.

度在有向網絡圖中分為入度和出度,例如微博中的關注關系.因為本文將相互距離小于閾值的兩個節點看作是相互連接的,所以關系對稱矩陣轉化為無向圖,不區分出度和入度.

4 初始中心點的確定

針對初始中心點對聚類結果的影響,本文提出了一種基于在關系矩陣中測量度中心性的方式優化初始中心點的選擇.首先,將對象集N內的節點計算兩兩之間的距離,因為不同的距離計算方法不會對本算法造成大的影響,所以為了降低計算量,本文采用曼哈頓距離.設立一個閾值L,根據反復測試,L取任意兩個節點之間平均距離的一半.兩個節點之間的距離如果小于這個閾值,建立節點之間的關系對稱矩陣時,我們將值設置為1,即認為這兩個節點在網絡中是相互連接的;如果距離大于閾值,則設為0,即認為這兩個節點在網絡中是無連接的.遍歷所有對象的行向量,將度中心性最高的節點設為初始中心點,并將與之相連的節點從矩陣中刪除.繼續迭代遍歷剩下的節點,直到找到k個中心點.

設目標對象集N={X1,X2,X3,…Xn},包含n個對象,每個對象有m個屬性,設每個對象Xi={xi1,xi2,…xim},從數據集N中選出k個中心點.

算法描述如下:

(1)預處理數據集N.

(4)遍歷所有節點,找出度中心性最高的節點,然后在矩陣中刪除該節點,由于類中心點相互之間的距離應該盡可能遠,且相互連接的節點是抱團存在的,所以刪除與之相連接的p個節點,所以n階矩陣轉變為n-p+1階矩陣.

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

5 實驗仿真分析

圖1為本文算法的流程圖.為了方便計算,并能表示出原始算法與改進算法的區別,所以本文使用java語言隨機生成7維的仿真數據對象,因為現實數據中每一維的差距有限,所以將每一維的屬性用0-200的整數型數字表示.并用java語言生成對象對稱關系矩陣.分別用原始方法選擇的初始中心點和本方法選擇的初始中心點比較聚類過程消耗的時間和聚類最終的效果.

圖1 實驗流程圖

圖2 為選取的前10個節點根據相互之間的距離和閾值L轉化而成的0和1的關系對稱矩陣,由于是無向圖,本文這里將節點本身看作是有連接的,這樣對最終的初始中心點選取結果并不會產生影響.

圖2 選取10個節點的關系矩陣

圖3 表示100個節點利用如圖2所示的關系對稱生成的社會網絡關系圖.我們可以很明顯的看出相互之間距離小且連接的節點是抱團存在的;又因為選取的初始中心點距離應該盡可能的遠,所以我們在選取每個初始中心點后,因為與之相鄰的節點將不會作為我們選取下一個聚類中心的候選節點,所以我們在矩陣網絡中刪除與之相鄰的節點.

圖3 包含100個節點的網絡連接圖

本文為了更準確的表示比較結果,所以將每種算法反復運行30次,用最終的四舍五入后的平均值去表示實驗性能和結果.以下實驗結果均為反復測試的平均值.

表1表示在沒有離群點的對象集中測試的實驗結果,本文使用兩種方法的運行時間和E值來作為衡量指標.這里的E值表示所有節點與最終所在的簇中心距離之和,E值的大小體現了最終子簇成員之間的緊密程度.

表1 不包含離群點的實驗結果

表2表示在含有離群點的對象集中分別使用兩種方法的運行時間和E值對比,為了說明改進算法的有效性,我們將添加的離群點設為原算法的其中一個初始中心點.

表2 包含離群點的實驗結果

除了與傳統方法比較之外,本文還與最新的文獻中的改進方法進行比較,本文選取了文獻[1],文獻[3]和文獻[6]中的優化初始中心選取方法進行實驗比較,實驗中使用了包含離群點的500個實驗對象,并且使用經過反復實驗得到的理想K值,用運行時間、迭代次數和E值來表示實驗結果,比較結果如表3所示.

表3 與近期改進算法的比較結果

通過表1和表2我們可以看出,在平滑的數據集中進行聚類處理,改進的算法與傳統算法在時間性能上的聚類結果上沒有優勢,但是在含有離群點數據集中,改進的算法的聚類結果明顯優于傳統算法.

通過表3可以看出,本文中提出的算法與近期文獻提出的方法相比較而言,本文提出的改進算法在時間性能上有一定的劣勢,但是在類內距和迭代次數這兩個指標上優于近期文獻中提出的算法,可以產生更加穩定和優質的聚類結果.

通過以上實驗結果可以得出結論,由于本文中提出的算法在聚類之前要生成對稱矩陣,并且要迭代計算每個節點的度中心性,所以造成了大量的時間消耗,但是通過這種方式可以找到更加優質的初始聚類中心,從而能夠生成更加精確和穩定的聚類結果,所以本文提出的算法更適合體量小的聚類對象集,在實際應用中是可行的.

6 結語

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

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

2于海濤,賈美娟,王慧強,等.基于人工魚群的優化K-means聚類算法.計算機科學,2012,39(12):60–64.

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

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

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

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

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

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

9賴玉霞,劉建平.K-means算法的初始聚類中心的優化.計算機工程與應用,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;收到修改稿時間:2016-09-23

10.15888/j.cnki.csa.005733