一種基于信息熵和密度的K-means算法的改進

谷玉榮

摘要：影響K-means聚類算法的因素主要有聚類個數(shù)、初始聚類中心、異常點、相似性度量和聚類評價準則五個方面。本文通過利用信息熵確定屬性的權重，從而對歐氏距離進行加權處理，將孤立點從數(shù)據(jù)集中取出，從而更好得選出聚類中心，然后利用加權歐氏距離公式對數(shù)據(jù)集進行相應的聚類。實驗結果表明，基于信息熵和密度的K-means聚類算法聚類結果更精確。

關鍵詞：信息熵;加權歐氏距離;基于信息熵和密度的K-means聚類算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2018）12-0107-03

0 引言

K-means聚類算法是在1967年由J.B.Mac Queen提出的一種基于歐氏距離和誤差平方和函數(shù)SSE（Sum of the Squared Error）的劃分聚類算法。它的主要目的是通過選取聚類中心和聚類個數(shù)，利用歐氏距離公式將剩余數(shù)據(jù)劃分到距離最近的聚類中心的簇中。這個聚類劃分的過程需要反復迭代，直到新選出的聚類中心與上一次的差距不大為止。其算法的具體過程如圖1所示。

K-means聚類算法盡管具備計算復雜度簡單、可擴展性好、收斂速度快和效率高四大優(yōu)點，但也有缺點。它的缺點主要包括：（1）由于聚類數(shù)目是人為決定的且聚類中心是隨機選擇，因此不同的聚類中心和聚類數(shù)目會導致不同聚類結果（2）數(shù)據(jù)集中會出現(xiàn)所謂的“噪聲”和孤立點數(shù)據(jù)，而這些數(shù)據(jù)在聚類的過程中會對聚類中心產(chǎn)生影響，從而形成局部最優(yōu)解。（3）當數(shù)據(jù)集中的數(shù)據(jù)屬性維度較大時，不僅會產(chǎn)生冗余信息從而使得算法運行的時間較長，而且利用的歐氏距離公式對待每一個屬性的重要性是一致的，導致聚類中心選擇有問題，聚類精度不精確。

針對K-means聚類算法現(xiàn)存的缺點，大多數(shù)研究者采用密度優(yōu)化的方法對聚類中心進行適當選取。文獻[1]中采用了密度指針函數(shù)選取了初始化聚類中心;文獻[2]中采用最優(yōu)劃分方法對數(shù)據(jù)集進行劃分，從而了解數(shù)據(jù)點的分布情況，依據(jù)數(shù)據(jù)點的分布情況進行初始聚類中心的選取;文獻[3]中利用距離、平均距離、密度參數(shù)、平均密度四個參數(shù)對每個數(shù)據(jù)的密度值進行相應的排序，并從中將密度值大的數(shù)據(jù)點選為聚類中心;文獻[4]中通過研究數(shù)據(jù)集的分布特征，在數(shù)據(jù)高密度分布的區(qū)域，取出距離最遠的一些點為聚類中心;文獻[5]中通過了解數(shù)據(jù)的分布情況，從高密度的數(shù)據(jù)分布中選取第一個初始化聚類中心，剩下聚類中心利用最大最小距離原則進行選取;文獻[6]中通過利用局部密度和高密距離參數(shù)，劃分出孤立點，并對其余的數(shù)據(jù)點進行排序，選出合適的聚類中心，避免陷入局部最優(yōu)解;文獻[7]中利用平均密度計算公式、數(shù)據(jù)點的密度參數(shù)公式和孤立點排除公式將數(shù)據(jù)集中的孤立點劃分出來，通過不斷迭代的過程在大于平均密度的密度參數(shù)集中選擇合適的聚類中心，并對剩余數(shù)據(jù)進行劃分后再對孤立點進行聚類，很好地避免孤立點對聚類中心選擇的影響，且提高了聚類精度和反應時間。

由此可以看出，雖然大部分的利用密度進行聚類優(yōu)化的方式對數(shù)據(jù)整體的分布情況反映良好，且在對數(shù)據(jù)進行聚類時可不受“噪聲”和孤立點數(shù)據(jù)的影響，導致選取的聚類中心更為合適，但在利用距離公式進行數(shù)據(jù)劃分時，認為每一個屬性的重要程度都是一樣的，造成聚類結果不精確，而且算法過程較為復雜，算法運行的時間較長。

1 相關基本理論

對于具有m個屬性值的n個數(shù)據(jù)值的數(shù)據(jù)集S={x1，x2，....xn}來說：

（1）任意兩個數(shù)據(jù)點之間的距離：

（1）

其中，指n個數(shù)值中第i個數(shù)據(jù)的第p個屬性值。

（2）所有數(shù)據(jù)點之間的平均距離：

（2）

其中，是從n個數(shù)據(jù)中任取兩個數(shù)據(jù)點的個數(shù)之和。

（3）任意一個點的密度參數(shù)：

（3）

即以數(shù)據(jù)集S中任一點為圓心，平均距離Mean Dist（S） 為半徑，圓內數(shù)據(jù)的個數(shù)即為的密度參數(shù)。其中，當時，;當時，。

（4）所有數(shù)據(jù)點密度的平均值：

（4）

（5）孤立點的確定：

（5）

（6）信息熵：

（6）

其中，為出現(xiàn)的概率。

2 基于信息熵和密度的K-means聚類算法的改進

在利用算法解決實際問題的過程中，會遇到數(shù)據(jù)的屬性值種類多且重要性不一致的問題，而基于密度的K-means聚類算法并不能很好處理這種缺點，因此，需將“信息熵”的概念引入到基于密度改進的K-means聚類算法中，從而客觀的確定屬性的權重，對歐式距離公式進行相應的加權處理，用來確定合適的聚類中心且對數(shù)據(jù)集進行聚類。

2.1 運用信息熵確定屬性權重[8]

（1）利用公式（7）計算j維屬性對應的第i個數(shù)據(jù)點出現(xiàn)的概率。

（7）

（2）利用公式（6）計算j維屬性的信息熵。

（3）利用公式（8）計算j維屬性的差異性系數(shù)。

（8）

其中，越小，越大，屬性越重要。

（4）利用公式（9）計算出j維屬性的權重。

（9）

從而得到加權的歐式距離公式為：

（10）

2.2 基于密度的K-means聚類算法的改進

本文通過利用信息熵對歐氏距離公式進行相應的加權處理，對文獻[7]中的基于密度的K-means聚類算法進行相應的改進，從而選取合適聚類中心并進行相應聚類。具體的實現(xiàn)過程如下：

（1）從包含有m個屬性值的n個數(shù)據(jù)集合s中，利用公式（10）、（2）、（3）、（4）計算出所有數(shù)據(jù)點之間的距離、平均距離、密度及平均密度。

（2）利用公式（5）將數(shù)據(jù)集s劃分成孤立點Q集合和剩余點P集合。

（3）將P集合按照公式（3）、（4），將大于平均密度的密度參數(shù)放入到集合U中。

（4）在集合U中找出最大的密度參數(shù)值和其個數(shù)N。

（5）if N=1，在集合P中找出密度參數(shù)值所對應的數(shù)據(jù)點即為聚類中心。利用公式（10）、（2）將與聚類中心的距離小于平均距離的數(shù)據(jù)點的密度參數(shù)從集合U中刪除。

（6）else在集合P中找出密度參數(shù)值為的所有數(shù)據(jù)點，利用公式（11）計算出最小的，此時最小的所對應的數(shù)據(jù)點即為聚類中心。再利用公式（10）、（2）將與聚類中心的距離小于平均距離的數(shù)據(jù)點的密度參數(shù)從集合W中刪除。

（11）

其中，。

（7）重復步驟（4）—（6），直到選出K個聚類中心。

（8）利用加權的歐式距離公式（10）計算出數(shù)據(jù)集P中的數(shù)據(jù)點與k個聚類中心的距離，根據(jù)“類內距離最小化”的原則將其聚類到不同的簇中。

（9）用公式（12）重新計算這k個聚類簇的聚類中心，并對數(shù)據(jù)集P進行重新劃分，直到滿足誤差平方和公式（13）收斂為止。

（12）

其中，代表的是聚類中心，代表的是聚類的簇，代表的是聚類簇中的數(shù)據(jù)點的個數(shù)，。

（13）

其中，代表的是所有對象的均方差和。

（10）利用加權的歐式距離公式（10）計算出數(shù)據(jù)集Q中的數(shù)據(jù)點與k個聚類中心的距離，根據(jù)“類內距離最小化”的原則將其聚類到不同的簇中。因此，這種基于信息熵和密度的改進K-means聚類算法的流程圖如下圖2所示。

3 實驗結果及分析

本文通過選取UCI上的Iris數(shù)據(jù)集為例子，利用基于信息熵和密度的改進的K-means聚類算法進行聚類分析并和文獻[7]中基于密度的K-means聚類算法進行相應的比較，聚成3種結果，對應的聚類結果如圖3和圖4所示。

通過兩者算法的比較，可以得出基于密度的K-means聚類算法的聚類中心為第96，131，89數(shù)據(jù)，分別對應的密度參數(shù)值為119，79，119;基于信息熵和密度的改進的K-means聚類算法的聚類中心為第80，133，99數(shù)據(jù)，分別對應的密度參數(shù)值為97，93，81。兩種算法的4種屬性值所對應的聚類中心如下表1所示。通過圖3和圖4的對比，可以得出，利用加權的歐式距離公式進行聚類劃分，使得權重大的屬性值在聚類的過程中作用放大，權重小的屬性值在聚類的過程中作用縮小，使得聚類的分界線明顯，取得得聚類中心更合適，進一步提高了聚類的精度，更符合實際過程中的應用。

參考文獻

[1]牛琨，張舒博，陳俊亮.融合網(wǎng)格密度的聚類中心初始化方案[J].北京郵電大學學報，2007（2）：6-10.

[2]崔斌，盧陽.基于不確定數(shù)據(jù)的查詢處理綜述[J].計算機應用，2008（11）：2729-2731+2744.

[3]韓凌波，王強，蔣正峰，等.一種改進的k-means 初始聚類中心選取算法[J].計算機工程與應用，2010（17）：150-152.

[4]孫士保，秦克云.改進的k-平均聚類算法研究[J].計算機工程，2007（13）：200-201+209.

[5]左進，陳澤茂.基于改進K 均值聚類的異常檢測算法[J].計算機科學，2016（8）：258-261.

[6]劉闖，陳桂芬.基于密度最大值的K-means初始聚類中心點算法改進[J].數(shù)字技術與應用，2017（11）：118-119.

[7]邢長征，谷浩.基于平均密度優(yōu)化初始聚類中心的K-means算法[J].計算機工程與應用，2014（20）：135-138.

[8]楊玉梅.基于信息熵改進的K-means動態(tài)聚類算法[J].重慶郵電大學學報（自然科學版），2016（2）：254-259.

An Improvement of K-means Algorithm Based on Information Entropy and Density

GU Yu-rong

（North Automatic Control Technology Institute， Taiyuan Shanxi 030006）

Abstract：The factors affecting the K-means clustering algorithm mainly include five aspects： cluster number， initial cluster center， outlier， similarity measure and cluster evaluation criteria. This paper uses the information entropy to determine the weight of the attribute， thus the Euclidean distance is weighted， and the isolated points are taken out from the data set， so that the cluster center is better selected. Then， the data set is clustered by the weighted Euclidean distance formula. The experimental results show that the K-means clustering algorithm based on information entropy and density is more accurate.

Key words：information entropy; weighted Euclidean distance; K-means clustering algorithm based on information entropy and density