改進的k-means算法在三支決策中的應用研究*

藺艷艷 陸介平 王郁鑫 傅廷妍

（江蘇科技大學計算機學院 鎮江 212001）

1 引言

隨著互聯網在生產生活中應用的越來越廣泛，隨之產生的是大量的數據。這些數據往往潛藏著用戶的行為動向或某個行業的發展規律。如何從這些海量數據中挖掘到有價值的信息是我們今天的研究熱點。聚類是數據挖掘中的一個非常重要的分支，它是根據信息相似度原則在預先不知道預劃分類的情況下進行信息聚類的一種方法。k-means算法［1］是一種典型的基于劃分的聚類算法，自1967年MacQueen提出后，由于其具有算法簡單易懂且收斂速度快的優點，得到較普遍的應用［2］。比如，利用k-means聚類方法來對客戶進行準確的分類，其結果可以作為企業優化營銷資源的重要依據等等。

但是，傳統的k-means算法是二支聚類，它不適用具有不確定因素的環境，并且k-means算法需要預先隨機選取初始聚類中心和設定聚類數目［3］，這些因素將導致聚類結果不穩定，影響其精確性。有許多學者對k-means算法進行研究和改進，Feng等改進k-means算法［4］是根據數據點的距離構造最小生成樹，并加以剪枝來構造樣本分布情況，從而動態選取初始聚類中心。Yu等提出了一種結合關系矩陣和度中心性（Degree Centrality）的分析方法，從而確定k-means算法初始的k個中心點［5］。為了能自動選擇k-means算法的初始k值，Debatty等提出了 G-means算法［6］，Yuan 等加入密度參數并通過計算平均密度來降噪［7］，Kettani等提出AK-means算法［8］等。但是，這些方法對局部最優、聚類結果不穩定和總迭代次數多等問題進行優化，并且在處理不確定性信息時，考慮到當前獲取到的信息不夠充分的特點，如果強制將其中的元素劃分到一個類中，往往容易帶來較高的錯誤率或決策風險。基于此，Hoppner等提出用模糊集表示聚類結果的模糊聚類理論方法［9］，Lingras提出了粗糙聚類方法，將聚類結果由粗糙集的正域，邊界域和負域來表示［10-13］，Yao等用區間集來表示聚類結果中的一個類［14］等，這些方法計算復雜，對指標權重矢量的確定主觀性較強。三支決策聚類理論的提出，有效地改善了傳統聚類方法處理具有不確定性因素的問題，并且可與傳統聚類算法結合，計算相對簡單。

三支決策聚類是一種重疊聚類，早先由Yao、Yu［15～17］等提出，它采用核心域、邊界域和瑣碎域來表示每個類別，其中邊界域中的元素是介于核心域和瑣碎域之間的元素，集中對邊界域中的元素判斷處理，可以較好地處理具有不確定性對象的聚類問題。在三支決策理論中，傳統的k-means二支聚類算法是一種特殊的三支聚類，即邊界域中的元素為空。有學者Li［18］利用傳統k-means聚類算法產生的結果和每個類中元素的鄰域所在的集合進行收縮與擴張，來研究將二支聚類轉化為三支聚類的方法，達到提高聚類結果的數據結構的目的。但是，這些方法均是直接使用傳統k-means算法，聚類結果的準確性和確定性受k-means算法缺點影響。

針對傳統k-means算法不適用具有不確定因素的環境和現有的基于k-means的三支聚類分析中并未避免傳統k-means聚類隨機選擇初始簇中心而導致聚類結果不穩定的問題，本文提出一種改進的k-means聚類方法，避免了傳統k-means算法由于初始簇中心選擇的隨機性而導致聚類結果不穩定的現象；其次，為了避免傳統k-means算法在處理不確定性信息時，強制將其中的元素劃分到一個類中帶來的錯誤率或決策風險，將改進的k-means算法與Wang提出的將二支聚類結果轉換成三支聚類方法結合起來，研究本文所提出的方法在三支決策中的應用，以提高聚類結果的結構和精度，實驗結果證明這種方法是有效的。

2 相關知識

2.1 k-means算法

k-means算法［19］原理簡單易懂，時間復雜度低，僅為O( )kNT ，并且具有計算簡單、高效等特點，廣泛應用在生產生活的各個領域。k-means算法基于樣本間相似度原則，采用兩樣本間的歐氏距離遠近作為衡量標準進行數據集劃分。k-means的算法理論是：在數據集D中，先隨機選取k個樣本作為初始中心，再計算剩下的所有樣本到這一組初始中心的歐氏距離，根據距離最近原則將各個樣本歸入到相應的聚類中心所在的類，然后計算每個類的新均值，重新修正聚類中心。不斷迭代更新，直到誤差平方和函數穩定在最小值。

其中：k為聚類類別數，ri為第i類中的樣本的個數，ni為第i類中樣本的平均值。

2.2 三支決策聚類的相關概念

其中式（3）表明，可通過和來表示一個類，式（4）要求正域非空，即每個類中至少有一個對象，而式（5）保證每個對象至少被分到一個類中。與二支聚類結果不同，三支聚類的結果可由下式來表示：

2.3 基于傳統k-means算法的三支聚類

二支決策的聚類結果是對象一定屬于兩個類中的一個，而三支決策的聚類結果是：對象確定屬于某類、可能屬于某類或確定不屬于某類。可以說二支決策是三支決策類結果中的一種，即不存在邊界區域。

圖1 數據集圖

如果刪除x1和x2，則很容易地將圖1聚成兩個結構特征非常好的類，而無論將x1或x2放到哪一個類中均會降低這個類的緊致性。基于三支決策聚類的核心思想，將x1和x2放到兩個類的邊界域當中去。定義一個θ域（距離該點最近的θ個點組成的集合），使θ域內的點在二支聚類的結果下不完全包含于某個類中，例如x1和x2這類點。這樣先采用k-means聚類的結果，再結合θ域（邊界域）的進行決策聚類的方法，便是基于傳統k-means算法的三支聚類。

3 改進的k-means算法在三支決策中的應用研究

3.1 改進的k-means算法

傳統的k-means算法的缺點是隨機地選取任意k個樣本作為初始聚類中心，這種隨機性會影響最終聚類結果的穩定性。本文提出的k-means算法的改進能夠克服上述問題。首先，先對數據集進行凝聚層次聚類，并采用輪廓系數對不同層次劃分進行評估，獲得較為合理中心數K。再對數據集進行n次樣本抽取（n次抽取的樣本總數要大于等于原始樣本數），并以層次聚類所得K值做為輸入對其進行k-means聚類，從而得出一組中心。然后計算這n組中心的誤差平方和準則函數值，選擇值最小所對應的聚類中心作為初始聚類中心。最后將其作為k-means三支聚類算法的初始中心和k值的輸入，避免了k-means算法隨機選擇初始中心和k值而導致最終三支聚類結果不穩定的問題。其中，多次抽取樣本可以保持隨機性不被破壞。層次聚類算法可以在其聚類結果上采用輪廓系數對數據集的不同層次劃分進行評估，在初始中心確定前先初步優化簇數K，最終的初始中心是由收斂函數來選取。為防止因適應誤差平方和準則函數而陷于局部最優或導致簇過度劃分，可以采取設定初始聚類中心數大于指定的K值，并且設定準則函數收斂標準，使達到收斂后的初始聚類中心數在合并距離近的簇之后數量減少到指定的K值。

層次聚類中需要用的公式具體如下：

3.2 改進的k-means算法在三支決策中的應用研究

本文將層次聚類和科學抽樣法引入到k-means算法中，是為了獲取最優初始簇類的數目，避免k-means算法隨機選擇k值和初始聚類中心而導致分類結果誤差較大、聚類結果不穩定等問題。然后將改進后的k-means算法聚類的結果做為三支聚類的初始輸入，實現最優類別劃分的問題。

前文提到的θ域這里給出詳細定義：

因為θ的選取也會對最終聚類結果產生影響，所以選擇合適的θ很重要，這里選取的θ是數據集中樣本數目的開平方，即N。

算法1：改進的k-means算法在三支決策中的應用

Step1：通過式（6）、式（7）將U中所有樣本都合并成一類，利用輪廓系數對聚類結果進行評估，得到較為合理的K值；

Step2：對U進行多次抽樣，通過式（1）對每次抽取的樣本進行k-means聚類，得到一組中心；

4 幾種聚類性能度量的指標

4.1 平均輪廓系數

輪廓系數（silhouette coefficient）［20］是聚類效果好壞的一種評價方式，它結合內聚度和分離度兩種因素，在相同原始數據的基礎上，評價不同算法或算法的不同運行方式對聚類結果所產生的影響。

計算某一個點的輪廓系數公式：

其中：表示i點向量到與它同簇的其他點的平均距離；表示i點向量到與它異簇的點的平均距離最小值。由上式可知，輪廓系數的值為[- 1，1]，如果輪廓系數S(i)值越大，則表明i點所在的簇就越緊密。

對于整個數據集來說，其輪廓系數的計算公式如下：

其中：n表示數據集中的樣本總數；SC值越大，則聚類效果越好，反之越差。

4.2 Davies-Bouldin-Index評價準則

Davies-Bouldin-Index（DBI）［21］，聚 類 結 果 的DBI越小，聚類效果越好。公式如下：

4.3 準確率

準確率（accuracy）是常見的一種評價聚類性能的外部指標。準確率越高，聚類效果越好。計算公式為

其中N是所有已被確定類別的對象的總數，k是聚類數，θi是第i個類中正確劃分的數據對象的個數。

5 實驗結果與分析

本節選用5組標準UCI［22］數據集對本文提出的算法進行測試實驗來驗證方法的性能。表1列出了實驗中所使用的5組測試數據集的基本信息。對于每個數據集，重復進行了200次實驗，用200次的平均值作為算法性能差異比較的依據。

表1 實驗所使用的數據集

本文設置兩個實驗來說明提出的改進的k-means算法以及基于改進k-means算法的三支決策的聚類效果和準確率。將改進的k-means算法記為k-means PA。

第一個實驗是二支聚類的測試，通過對比一些已有的算法，即首先用fuzzy c-means、k-medoid、傳統k-means和k-means PA分別在表1中的數據集上進行聚類來驗證本文提出的k-means PA算法的聚類結果DBI和準確率，以及聚類結果的穩定性。

第二個實驗是在第一個實驗的基礎上，結合本文介紹的三支決策方法進一步優化聚類結果。最后通過實驗數據分別比較二支聚類和三支聚類兩組實驗結果的DBI和ACC。

5.1 實驗一

圖2是fuzzy c-means、k-medoid、傳統k-means和k-means PA四種算法表1中的數據集上進行二支聚類后結果的DBI對比圖。由圖可知，本文提出的算法k-means PA在UCI的5個數據集上，其DBI均低于fuzzy c-means、k-medoid和傳統k-means的DBI，在Sonar數據集上尤其明顯。在Wine數據集上，本文算法與傳統k-means基本相同，低于fuzzy c-means和k-medoid。

圖3是fuzzy c-means、k-medoid、傳統k-means和k-means PA四種算法表1中的數據集上進行二支聚類后結果的準確率對比圖。由圖可知，本文提出的算法k-means PA在Iris數據集上的準確率沒有 fuzzy c-means、k-medoid的 ACC 高，但比傳統k-means的準確率要高；在Hill、Sonar和Wine數據集上，k-means PA的準確率要高于其他三種算法；在Wdbc數據集上，k-means PA的準確率和其他三種算法的準確率不分伯仲。

圖2 算法DBI實驗結果

圖3 算法準確率實驗結果

綜合圖2和圖3來，本文提出的改進算法在UCI的5個數據集上獲得了較好的DBI和準確率，因此，本文的算法能適應于不同數據集的聚類挖掘。

5.2 實驗二

實驗二是在實驗一的基礎上進行的三支聚類，圖 4和圖 5是基于 fuzzy c-means、k-medoid、傳統k-means和改進k-means算法結合三支聚類理論的聚類結果的DBI和ACC對比圖。

圖4 三支聚類結果DBI對比圖

圖5 三支聚類結果ACC對比圖

圖6 基于k-means PA的二支聚類和三支聚類結果的DBI和ACC對比圖

由圖可知，三支聚類結果的DBI和ACC對比結論同實驗一。但從圖6中可以明顯看出基于本文提出的k-means PA算法的三支聚類結果的DBI比k-means PA二支聚類結果的DBI低，基于本文提出的k-means PA算法的三支聚類結果的ACC比k-means PA二支聚類結果的ACC高，這表明結合三支聚類方法的聚類效果更好，準確率更高。綜上所述，本文提出的改進的k-means算法在三支聚類算法中應用是有效的。

5.3 穩定性

由于傳統k-means算法在聚類時結果存在不穩定現象，因此，對提出改進行算法的聚類結果進行了穩定性實驗。選取其中一個數據集并進行30次運行實驗，其結果如圖7所示。從圖7可以看出，傳統的k-means算法穩定性較差，結果會隨著運行次數不同而呈現不同的聚類結果，而本文提出的聚類算法的聚類結果呈現出較好的穩定性。

圖7 算法穩定性比較

6 結語

本文針對傳統k-means聚類算法初始中心的選取做了改進，并結合Yu等學者研究的基于鄰域的三支聚類理論，提出一種改進的k-means算法并結合三支聚類的算法，解決了初始中心和k值的選取問題和處理不確定性信息時最優類別劃分的問題。實驗結果證明，本文所提出的算法可以有效地避免傳統k-means因隨機選取初始簇而導致了聚類不穩定的現象，并且算法在準確率上有所提高，DBI表明聚類的效果更好。但計算的時間有所增加，如何快速有效地獲取一個最優參數k來使聚類效果和精度能達到一個最佳理想的結果，還有研究近鄰參數θ的值將會是下一步的研究工作內容。