一種基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法

趙興旺　　　梁吉業(yè)

(山西大學(xué)計算機與信息技術(shù)學(xué)院　太原　030006)(計算智能與中文信息處理教育部重點實驗室(山西大學(xué))　太原　030006)(zhaoxw84@163.com)

一種基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法

趙興旺梁吉業(yè)

(山西大學(xué)計算機與信息技術(shù)學(xué)院太原030006)(計算智能與中文信息處理教育部重點實驗室(山西大學(xué))太原030006)(zhaoxw84@163.com)

摘要同時兼具數(shù)值型和分類型屬性的混合數(shù)據(jù)在實際應(yīng)用中普通存在，混合數(shù)據(jù)的聚類分析越來越受到廣泛的關(guān)注.為解決高維混合數(shù)據(jù)聚類中屬性加權(quán)問題，提出了一種基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法，以提升模式發(fā)現(xiàn)的效果.工作主要包括：首先為了更加準確客觀地度量對象與類之間的差異性，設(shè)計了針對混合數(shù)據(jù)的擴展歐氏距離；然后，在信息熵框架下利用類內(nèi)信息熵和類間信息熵給出了聚類結(jié)果中類內(nèi)抱團性及一個類與其余類分離度的統(tǒng)一度量機制，并基于此給出了一種屬性重要性度量方法，進而設(shè)計了一種基于信息熵的屬性加權(quán)混合數(shù)據(jù)聚類算法.在10個UCI數(shù)據(jù)集上的實驗結(jié)果表明，提出的算法在4種聚類評價指標下優(yōu)于傳統(tǒng)的屬性未加權(quán)聚類算法和已有的屬性加權(quán)聚類算法，并通過統(tǒng)計顯著性檢驗表明本文提出算法的聚類結(jié)果與已有算法聚類結(jié)果具有顯著差異性.

關(guān)鍵詞聚類分析；混合數(shù)據(jù)；屬性加權(quán)；信息熵；相異性度量

聚類分析的主要目的在于發(fā)現(xiàn)數(shù)據(jù)中隱含的類結(jié)構(gòu)，將物理或抽象對象劃分為不同的類，使得同一類內(nèi)對象之間相似度較大，而不同類的對象之間相似度較小.作為一種主要的探索性數(shù)據(jù)分析工具，聚類分析目前已經(jīng)在機器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別、生物信息學(xué)、統(tǒng)計學(xué)和社會計算等領(lǐng)域都得到了廣泛的研究和應(yīng)用[1].

半個多世紀以來，研究者針對不同的應(yīng)用領(lǐng)域已經(jīng)提出了諸多聚類算法，主要分為層次聚類算法和劃分式聚類算法[2-4].其中，劃分式聚類算法由于簡單、高效、易實現(xiàn)等優(yōu)點得到了廣泛的應(yīng)用.在傳統(tǒng)的劃分式聚類過程中，都假定各個屬性對聚類的貢獻程度相同，即在相似性或相異性度量的計算中所有屬性的權(quán)重相同.而在大部分實際應(yīng)用中，用戶期望得到的聚類結(jié)果，對參與聚類的各個屬性的重要程度往往并不相同.特別是在高維數(shù)據(jù)聚類過程中，樣本空間中各屬性對聚類效果貢獻大小不同成為了一個不可回避的問題[5].因此，識別不同屬性在聚類過程中的差異程度，從而提高聚類結(jié)果的質(zhì)量，研究聚類過程中屬性自動加權(quán)技術(shù)具有非常重要的意義.

近年來，為了計算不同屬性對聚類貢獻程度的差異性，許多學(xué)者針對聚類算法中屬性加權(quán)問題已經(jīng)開展了一些研究，提出了一系列屬性自動加權(quán)聚類算法，這些研究大多針對數(shù)值型數(shù)據(jù)[6-8].然而現(xiàn)實生活中遇到的數(shù)據(jù)既可能是數(shù)值型數(shù)據(jù)，也可能是分類型數(shù)據(jù)，或同時由數(shù)值型和分類型屬性共同描述的混合數(shù)據(jù).與數(shù)值型數(shù)據(jù)相比，分類型數(shù)據(jù)的某一屬性的取值是有限集合中的某一個值，而且取值之間沒有序關(guān)系，這些特點使得分類型數(shù)據(jù)之間相似性度量的定義更為困難，從而使得數(shù)值型數(shù)據(jù)屬性加權(quán)聚類算法無法直接應(yīng)用于分類型數(shù)據(jù)[9-11].在分類型數(shù)據(jù)屬性加權(quán)聚類算法方面，文獻[10]提出了一種分類型數(shù)據(jù)屬性加權(quán)聚類算法，在計算屬性權(quán)重的過程中同時考慮了類中心出現(xiàn)的頻率和類內(nèi)對象到類中心平均距離.文獻[11]提出了一個基于非模的分類型數(shù)據(jù)屬性自動加權(quán)聚類方法，依據(jù)屬性取值的總體分布情況對屬性賦予不同權(quán)重.文獻[12]設(shè)計了一種基于類內(nèi)信息熵的分類型數(shù)據(jù)軟子空間聚類算法，在每一個類中根據(jù)屬性重要度對不同屬性賦予不同的權(quán)重.

混合數(shù)據(jù)由于同時具有數(shù)值型屬性和分類型屬性，在對象之間相似性或相異性度量的定義和不同類型屬性加權(quán)機制方面更為困難.其中，1998年，文獻[13]通過把K-Modes算法和K-Means算法進行簡單集成提出了針對混合數(shù)據(jù)的K-Prototypes算法.在該算法中，對象與類中心之間的相異性度量同時考慮了數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)，并通過參數(shù)來控制數(shù)值型部分和分類型部分貢獻的大小.其中，在相異性度量方面，數(shù)值型屬性之間的相異性度量采用歐氏距離，分類型屬性之間的相異性通過簡單0-1匹配來度量；在類中心表示方面，數(shù)值型數(shù)據(jù)部分采用均值(means)表示，而分類型數(shù)據(jù)分別采用眾數(shù)(modes)表示.K-Prototypes算法由于簡單易實現(xiàn)，已經(jīng)在混合數(shù)據(jù)聚類中得到了廣泛的應(yīng)用.但是，歐氏距離和簡單0-1匹配相異性度量的取值范圍不同，而且不同類型數(shù)據(jù)之間的相異性度量僅僅通過一個參數(shù)進行調(diào)節(jié)，因此在聚類過程中不能客觀地體現(xiàn)對象與類之間相異性在數(shù)值屬性和分類屬性各個屬性的重要度.針對以上問題，一些學(xué)者已經(jīng)進行了一些探索[14-16].如文獻[14]針對分類數(shù)據(jù)部分，通過考慮同一屬性下不同屬性值的出現(xiàn)頻率給出了一種新的相異性度量方法，并利用倒數(shù)比例計算法給出了一種新的類中心更新方式，通過與K-Means算法集成進而提出了一個可以處理混合數(shù)據(jù)的聚類算法.文獻[15]給出了一個針對分類型和數(shù)值型屬性統(tǒng)一的相似性度量方法，消除了不同類型數(shù)據(jù)之間度量量綱的差異性，同時也免去了不同度量之間參數(shù)的設(shè)置.該方法針對分類型數(shù)據(jù)，利用信息熵對不同分類屬性的重要性進行了刻畫.但是，在分類型屬性加權(quán)過程中直接計算各個屬性在所有數(shù)據(jù)上的信息熵，并沒有考慮不同類之間的差異性；另外在計算相似性度量過程中把數(shù)值型數(shù)據(jù)的所有屬性當(dāng)作整體計算得到一個相似度度量的數(shù)值，然后與分類型屬性部分進行加權(quán)，這種計算方法顯然削弱了數(shù)值型數(shù)據(jù)部分的權(quán)重.

通過以上分析可知，已有的屬性加權(quán)聚類算法主要存在3個局限性：

1) 大多數(shù)加權(quán)聚類方法僅僅針對數(shù)值型或分類型單一類型數(shù)據(jù)進行屬性加權(quán)，這些方法在實際應(yīng)用中存在一定的局限性；

2) 已有屬性加權(quán)方法或者依賴于整體數(shù)據(jù)集屬性值的總體分布情況(屬性重要性與數(shù)據(jù)分布的離散程度成反比，數(shù)據(jù)集中某個屬性的取值越集中，該屬性的重要性就越高)，或者根據(jù)對象到類中心的距離定義的分散度來衡量(在某個類中某屬性下的分散度越低，則該屬性在該類的重要性越高)，而并沒有考慮不同類之間屬性值分布的差異性，這必然導(dǎo)致屬性權(quán)重計算上的偏差，從而影響聚類質(zhì)量；

3) 針對現(xiàn)實生活中廣泛存在的混合型數(shù)據(jù)，已有方法在對象與類中心之間相似性或相異性度量方面，通常采用不同的度量機制，存在量綱不同的問題，不能客觀地反映混合數(shù)據(jù)之間的差異性.

針對以上問題，本文基于信息熵理論提出了一個混合數(shù)據(jù)屬性加權(quán)聚類算法.1)為了更加準確客觀地度量對象與類之間的差異性，設(shè)計了一種針對混合數(shù)據(jù)的擴展歐氏距離；2)在信息熵框架下利用類內(nèi)信息熵和類間信息熵給出了聚類結(jié)果中類內(nèi)抱團性及一個類與其余類分離度的統(tǒng)一度量機制，并基于此給出了一種屬性加權(quán)方法;3)在UCI數(shù)據(jù)集上實驗結(jié)果表明，本文提出的屬性加權(quán)聚類算法在4種評價指標下優(yōu)于傳統(tǒng)的未加權(quán)聚類算法和已有加權(quán)聚類算法.

1相關(guān)工作

本節(jié)主要對混合型數(shù)據(jù)聚類相關(guān)背景知識和K-Prototypes聚類算法進行介紹.

(1)

K-Prototypes算法最小化以下目標函數(shù)：

其中，wli∈{0,1},1≤l≤k,1≤i≤n；

wli=1時表示第i個對象屬于第l個類，wli=0時表示第i個對象不屬于第l個類.

為了使目標函數(shù)F在給定的約束條件下達到極小值，采用如下算法進行計算.

算法1.K-Prototypes聚類算法.

Step1. 從數(shù)據(jù)集X中隨機選取k個對象作為初始類中心；

Step2. 根據(jù)式(1)計算對象與類中心之間的距離,并根據(jù)最近原則將每個對象分配到離它最近的類中；

Step3. 更新聚類中心，其中數(shù)值屬性部分通過計算同一類中對象的平均值得到，分類型屬性部分通過計算類中各屬性值出現(xiàn)的頻率高低來確定；

Step4. 重復(fù)Step2,Step3,直到目標函數(shù)F不再發(fā)生變化為止.

K-Prototypes算法由于簡單、高效、易實現(xiàn)，已經(jīng)得到了廣泛的應(yīng)用.但是，在相異性度量的定義中存在數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)部分量綱不同、參數(shù)γ難以確定、不能客觀地反映對象與類中心的差異性的缺陷；而且在定義對象與類中心的差異性度量的過程中未考慮各個屬性的重要性.本文在K-Prototypes算法的框架下，提出了一個針對混合數(shù)據(jù)迭代式的屬性加權(quán)聚類算法.

2基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法

在信息論中，信息熵是一種用于度量系統(tǒng)不確定性的度量方法.在一個系統(tǒng)中，某個屬性取值的不確定性程度越大，表明系統(tǒng)越混亂，在該屬性下系統(tǒng)的信息熵越大，它提供的信息量越小，該屬性的重要性也就越?。环粗?，某個屬性取值的不確定性程序越小，表明系統(tǒng)越有序，在該屬性下信息熵越小，它提供的信息量越大，該屬性的重要性也就越大.作為一種有效的度量機制，信息熵已經(jīng)在聚類分析、孤立點檢測、不確定性度量等領(lǐng)域得到了廣泛的應(yīng)用.本文根據(jù)各個屬性下取值的不確定程度，利用類內(nèi)和類間信息熵來度量各個屬性在聚類過程中的重要程度.由于描述對象的屬性類型不同，信息熵的計算方法也不同，本節(jié)將分別進行描述.

在給出數(shù)值型和分類型數(shù)據(jù)基于信息熵度量的屬性加權(quán)機制之前，首先定義一種新的混合數(shù)據(jù)相異性度量方法.

2.1混合數(shù)據(jù)相異性度量方法

由于K-Prototypes算法中分類型數(shù)據(jù)部分的聚類中心僅僅將某類中當(dāng)前屬性值域中出現(xiàn)頻率最高的取值(即modes)作為類中心，忽略了該屬性的其余取值情況，而且往往會出現(xiàn)類中心不唯一的情況.本節(jié)首先給出分類型數(shù)據(jù)一種新的模糊類中心表示方式，并基于此將傳統(tǒng)的歐氏距離擴展到混合數(shù)據(jù)，使得能夠在統(tǒng)一的框架下更加客觀地度量混合數(shù)據(jù)中對象與類之間的相異性.

定義1. 設(shè)Cl表示數(shù)據(jù)集X在聚類過程中得到的一個類，則分類型屬性部分模糊類中心表示為

(2)

由定義1可知，數(shù)據(jù)集中的單一對象也可以表示為模糊類中心的形式，是模糊類中心表示的一種特殊形式.即針對某一屬性下，當(dāng)前對象的屬性值對應(yīng)的頻率為1，其余值域?qū)?yīng)的頻率為0.

基于以上給出的分類型數(shù)據(jù)新的類中心表示方式，下面給出擴展的歐氏距離度量.

(3)

(4)

2.2基于信息熵的數(shù)值型屬性加權(quán)機制

針對數(shù)值型數(shù)據(jù)，匈牙利數(shù)學(xué)家Renyi[17]于1961年提出了一個可以度量連續(xù)型隨機變量的信息熵，稱作Renyi熵.設(shè)連續(xù)型隨機變量x的概率密度函數(shù)為f(x)，則該隨機變量的Renyi熵定義為

(5)

當(dāng)α=2，HR(x)=-ln∫f2(x)dx，記為二階Renyi熵.

二階Renyi熵由于計算方便、具有很好的性質(zhì)，在實際應(yīng)用中得到了廣泛的應(yīng)用.Parzen窗口估計法作為一種非參數(shù)估計方法，通常用于利用已知樣本對總體樣本的概率密度進行估計[18].因此二階Renyi熵中的密度函數(shù)可以用Parzen窗口估計法來進行估計.設(shè)X={x1,x2,…,xN}，xi∈d，是一個由獨立同分布的N個數(shù)據(jù)對象組成的數(shù)據(jù)集合，則對于任意隨機變量x∈X利用Parzen窗口估計法估計出的概率密度為

(6)

其中，Wσ2表示Parzen窗函數(shù)，σ2表示窗寬.通常選取高斯核函數(shù)作為Parzen窗函數(shù)，即

(7)

通過分析可知，基于Parzen窗口估計法得到的Renyi熵可能出現(xiàn)負值的情況.為了保證熵值為正及計算的方便，本文在W2σ2(xi,t,xj,t)之前乘以一個相對小的正數(shù)，即:

基于以上給出的Renyi熵，數(shù)值型數(shù)據(jù)在某一屬性下類內(nèi)熵、類間熵分別定義如下[20].

(8)

其中，Nk′=|Crk′|表示類Crk′中對象的個數(shù).

上述定義給出的類內(nèi)熵反映了聚類劃分結(jié)果中某一類在不同的屬性下數(shù)據(jù)分布的不確定程度.即在一個類中如果某個屬性下的類內(nèi)熵越小，則該屬性在該類中的不確定性越小，聚類過程中該屬性的權(quán)重就越大.

(9)

其中，Nk′=|Crk′|和Ns=|Crs|分別表示類Crk′和Crs中對象的個數(shù).

基于定義4和定義5，下面給出數(shù)值型數(shù)據(jù)屬性加權(quán)的定義.

(10)

由定義6可知，屬性權(quán)重與類內(nèi)熵成反比，與類間熵成正比，而且類內(nèi)熵、類間熵都已經(jīng)歸一化到[0,1]之間，因此，各個屬性權(quán)重的范圍為[0,1].由定義5可知，如果聚類個數(shù)為2時，類與類之間的平均類間熵則相等，此時屬性權(quán)重只與類內(nèi)熵有關(guān).

2.3基于信息熵的分類型屬性加權(quán)機制

針對分類型數(shù)據(jù)，文獻[21]中提出了一個既可以用來度量隨機性，又可以度量模糊性的互補信息熵.目前，該信息熵已經(jīng)在不確定性度量、特征選擇、聚類分析、孤立點檢測等領(lǐng)域得到了廣泛的應(yīng)用[12,22-26].

基于互補熵，分類型數(shù)據(jù)的類內(nèi)熵、類間熵分別定義如下[25]:

(11)

(12)

式(12)表明分類型數(shù)據(jù)類內(nèi)熵與類內(nèi)平均距離是等價的.因此，可以從距離的角度來定義分類型數(shù)據(jù)一個類與其余類之間的平均類間熵.

(13)

與數(shù)值型數(shù)據(jù)的信息熵類似，定義7和定義8給出的分類型數(shù)據(jù)的類內(nèi)熵、類間熵分別表示在一個聚類劃分結(jié)果中一個類在不同的屬性下類內(nèi)數(shù)據(jù)分布的不確定程度和與其余類的分離程度.

基于定義7和定義8，下面給出分類型數(shù)據(jù)屬性加權(quán)的定義.

(14)

2.4基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法

基于式(4)(10)(14)，任一對象xi∈X和類Cl(類中心表示為zl)的加權(quán)相異度度量定義為

(15)

由式(15)可知，在信息熵機制下結(jié)合類內(nèi)信息熵和類間信息熵給出了針對數(shù)值型和分類型數(shù)據(jù)統(tǒng)一的加權(quán)方法，而且不同類型屬性下的相異性度量的范圍都在[0,1]之間，避免了量綱不同的問題，能夠更加客觀地反映混合數(shù)據(jù)中對象與類之間的差異性.

設(shè)X={x1,x2,…,xN}是一個混合型數(shù)據(jù)集，將上述給出的加權(quán)相異性度量應(yīng)用到K-Prototypes算法框架中，算法的目標函數(shù)定義為

其中：

1≤l≤k,1≤i≤n；

以上優(yōu)化問題是一個非常復(fù)雜的非線性規(guī)劃問題，和K-Prototypes類型算法類似，采用逐步迭代優(yōu)化的策略，即首先固定聚類中心Z，最小化目標函數(shù)F′得到隸屬矩陣W；然后固定隸屬矩陣W，最小化目標函數(shù)F′得到新的聚類中心Z；如此迭代，直到目標函數(shù)F′收斂為止.算法描述如下.

算法2. 基于信息熵的混合數(shù)據(jù)加權(quán)聚類算法.

輸入: 數(shù)據(jù)集X={x1,x2,…,xN}、類個數(shù)k；

輸出: 聚類結(jié)果.

Step1. 從數(shù)據(jù)集X中隨機選取k個不同的對象作為初始聚類中心；

Step3. 根據(jù)式(15)計算對象與類中心之間的相異度，按照最近鄰原則將數(shù)據(jù)對象劃分到離它最近的聚類中心所代表的類中；

Step4. 更新聚類中心，其中數(shù)值屬性部分通過計算同一類中對象取值的平均值得到，分類型屬性部分根據(jù)定義1計算模糊類中心；

Step5. 根據(jù)定義6和定義9分別計算各個類在數(shù)值型和分類型數(shù)據(jù)部分各個屬性的權(quán)重；

Step6. 重復(fù)Step3～Step5,直到目標函數(shù)F′不再發(fā)生變化為止.

3實驗結(jié)果與分析

為了測試本文提出算法的有效性，我們從UCI真實數(shù)據(jù)集中分別選取了數(shù)值型、分類型和混合型3種不同類型的數(shù)據(jù)集進行了測試，并將本文提出的算法與K-Prototypes算法[13]、K-Centers算法[14]和基于屬性加權(quán)的OCIL算法[15]、改進的K-Prototypes算法[16]進行了比較.10組數(shù)據(jù)集信息描述如表1所示，其中包括3個數(shù)值型數(shù)據(jù)、3個分類型數(shù)據(jù)和4個混合型數(shù)據(jù).

Table 1　The Summary of Data Sets’ Characteristics

為了對聚類結(jié)果的有效性進行評價，本文采用3個外部有效性評價指標和1個內(nèi)部有效性評價指標對聚類結(jié)果評價.外部有效性評價指標包括聚類精度(clustering accuracy, CA)[14]、標準互信息(normalized mutual information, NMI)[27]和調(diào)整的蘭特指數(shù)(adjusted rand index, ARI)[25]；內(nèi)部有效性指標包括混合數(shù)據(jù)分類效用函數(shù)(category utility function for mixed data, CUM)[25].

實驗中，由于本文提出的新算法和被比較算法的聚類結(jié)果均受初始類中心選擇的影響，不同的初始類中心可能有不同的聚類結(jié)果.因此，以下實驗結(jié)果均為算法隨機運行50次評價指標的平均值和方差.K-Prototypes算法[13]、K-Centers算法[15]中的權(quán)重參數(shù)γ根據(jù)作者建議分別設(shè)置為γ=1.5和γ=0.5.改進的K-Prototypes算法[16]中參數(shù)λ根據(jù)作者建議設(shè)置為λ=8.另外，為了避免數(shù)值型不同屬性間量綱的影響，在聚類之前對數(shù)值型數(shù)據(jù)進行了標準化處理.

3.1數(shù)值型數(shù)據(jù)聚類結(jié)果分析

在不同評價指標下，本文提出的新算法和其他4種聚類算法在數(shù)值型數(shù)據(jù)上聚類結(jié)果如表2～5所示.由于K-Prototypes算法、K-Centers算法和基于屬性加權(quán)的OCIL算法在針對純數(shù)值型數(shù)據(jù)聚類時，都退化為經(jīng)典K-Means算法，因此本實驗中針對數(shù)值型數(shù)據(jù)只將本文提出算法與K-Means算法、改進的K-Prototypes算法進行了比較.

Table 2Comparison of CA Values (means±std) of Different Algorithms on Numerical Data

表2　數(shù)值型數(shù)據(jù)聚類結(jié)果比較：CA值(均值±方差)

Table 3Comparison of NMI Values (means±std) of

Different Algorithms on Numerical Data

表3　數(shù)值型數(shù)據(jù)聚類結(jié)果比較：NMI值(均值±方差)

Table 4Comparison of ARI Values (means±std) of

Different Algorithms on Numerical Data

表4　數(shù)值型數(shù)據(jù)聚類結(jié)果比較：ARI值(均值±方差)

Table 5Comparison of CUM Values (means±std) of

Different Algorithms on Numerical Data

表5　數(shù)值型數(shù)據(jù)聚類結(jié)果比較：CUM值(均值±方差)

由表2～5可知，從CA，NMI，CUM指標看，本文提出的算法在Segment數(shù)據(jù)集上獲得的聚類結(jié)果劣于其他算法，在CUM指標下本文算法在Waveform+Noise數(shù)據(jù)集上獲得的聚類結(jié)果劣于改進的K-Prototypes算法.除此之外，在不同指標下本文提出的聚類算法在其他數(shù)據(jù)集上的聚類結(jié)果均優(yōu)于其他算法.

3.2分類型數(shù)據(jù)聚類結(jié)果分析

在不同評價指標下，本文提出的新算法和其他4種聚類算法在分類型數(shù)據(jù)上聚類結(jié)果如表6～9所示:

Table 6　Comparison of CA Values (means±std) of Different Algorithms on Categorical Data

Table 7　Comparison of NMI Values (means±std) of Different Algorithms on Categorical Data

Table 8　Comparison of ARI Values (means±std) of Different Algorithms on Categorical Data

Table 9　Comparison of CUM Values (means±std) of Different Algorithms on Categorical Data

由表6～9可知，本文提出的算法除了在Chess數(shù)據(jù)集上聚類結(jié)果的CA值劣于改進的K-Prototypes算法之外，其余聚類結(jié)果均均優(yōu)于其他算法.

3.3混合型數(shù)據(jù)聚類結(jié)果分析

在不同評價指標下，本文提出的新算法和其他4種聚類算法在混合數(shù)據(jù)上聚類結(jié)果如表10～13所示.

由表10～13可知，從CA和ARI評價指標看，K-Centers算法在Flag和German Credit數(shù)據(jù)集上取得了最優(yōu)的聚類結(jié)果.除此之外，本文提出的算法在其余數(shù)據(jù)集上均取得了最優(yōu)的聚類結(jié)果.

Table 10　Comparison of CA Values (means±std) of Different Algorithms on Mixed Data

Table 11　Comparison of NMI Values (means±std) of Different Algorithms on Mixed Data

Table 12　Comparison of ARI Values (means±std) of Different Algorithms on Mixed Data

Table 13　Comparison of CUM Values of (means±std) Algorithms on Mixed Data

3.4聚類結(jié)果統(tǒng)計顯著性分析

針對本文提出算法的聚類結(jié)果與其他算法聚類結(jié)果差異是否顯著的問題，本節(jié)利用無參數(shù)的Wilcoxon秩和檢驗方法進行了統(tǒng)計顯著性檢驗.在不同評價指標下，將本文提出算法實驗結(jié)果的均值分別與其余算法實驗結(jié)果的均值進行了統(tǒng)計顯著性檢驗.其中，原假設(shè)為在當(dāng)前指標下本文算法與已有算法的聚類結(jié)果沒有顯著性差異，備擇假設(shè)為不同聚類算法結(jié)果具有顯著性差異.

置信區(qū)間為95%的Wilcoxon秩和檢驗結(jié)果h(p)如表14所示.其中數(shù)據(jù)分別表示假設(shè)檢驗結(jié)果h和p值.h=1表示在置信區(qū)間為95%時拒絕原假設(shè)接受備擇假設(shè)，即表示本文提出算法的聚類結(jié)果與已有算法聚類結(jié)果具有顯著差異性；h=0表示本文提出算法的聚類結(jié)果與已有算法聚類結(jié)果無顯著差異性.由表14可知，本文提出算法在10個數(shù)據(jù)集獲得的聚類結(jié)果在87.5%的情況下與其余聚類算法獲得的聚類結(jié)果具有顯著差異性.

Table 14Resultsh(p) of Wilcoxon Signed-ranks Test for the

Proposed Algorithm versus Other Algorithms

表14　本文算法與其余算法Wilcoxon秩和檢驗結(jié)果h(p)

4結(jié)束語

本文首先基于分類型數(shù)據(jù)類中心的模糊表示形式，給出了一種針對混合數(shù)據(jù)擴展的歐氏距離，能夠更加客觀準確地度量對象與類之間的差異性.其次，分別基于Renyi熵和互補熵定義了數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)的類內(nèi)熵、類間熵，給出了屬性加權(quán)機制，進而設(shè)計了一個基于信息熵的混合數(shù)據(jù)屬性加權(quán)聚類算法.新提出的算法克服了主流聚類算法僅依據(jù)數(shù)據(jù)集總體分布或類內(nèi)分散度進行屬性加權(quán)的缺陷.在多個真實數(shù)據(jù)集上進行了實驗驗證，與其他混合數(shù)據(jù)聚類算法相比,本文提出的算法可以獲得較高的聚類質(zhì)量，而且與其他聚類結(jié)果具有顯著差異性.

參考文獻

[1]Han Jiawei, Kamber M, Pei Jian. Data Mining: Concepts and Techniques[M]. 3rd ed. San Francisco: Morgan Kaufmann, 2011

[2]Jain A K. Data clustering: 50 years beyondK-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666

[3]Xu Rui, Wunsch D. Survey of clustering algorithm[J]. IEEE Trans on Neural Networks, 2005, 16(3): 645-678

[4]Sun Jigui, Liu Jie, Zhao Lianyu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1): 48-61 (in Chinese)(孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報, 2008, 19(1): 48-61)

[5]Kriegel H P, Kr?ger P, Zimek A. Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering[J]. ACM Trans on Knowledge Discovery from Data, 2009, 3(1): 1-58

[6]Chan E Y, Ching W K, Ng M K, et al. An optimization algorithm for clustering using weighted dissimilarity measures[J]. Pattern Recognition, 2004, 37(5): 943-952

[7]Huang J Z, Ng M K, Rong Hongqiang, et al. Automated variable weighting ink-means type clustering[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(5): 657-668

[8]Jing Liping, Ng M K, Huang J Z. An entropy weightingk-means algorithm for subspace clustering of high-dimensional sparse data[J]. IEEE Trans on Knowledge and Data Engineering, 2007, 19(8): 1026-1041

[9]Liang Jiye, Bai Liang, Cao Fuyuan.K-modes clustering algorithm based on a new distance measure[J]. Journal of Computer Research and Development, 2010, 47(10): 1749-1755 (in Chinese)(梁吉業(yè), 白亮, 曹付元. 基于新的距離度量的K-modes聚類算法[J]. 計算機研究與發(fā)展, 2010, 47(10): 1749-1755)

[10]Bai Liang, Liang Jiye, Dang Chuangyin, et al. A novel attribute weighting algorithm for clustering high-dimensional categorical data[J]. Pattern Recognition, 2011, 44(12): 2843-2861

[11]Chen Lifei, Guo Gongde. Non-mode clustering of categorical data with attributes weighting[J]. Journal of Software, 2013, 24(11): 2628-2641 (in Chinese)(陳黎飛, 郭躬德. 屬性加權(quán)的類屬型數(shù)據(jù)非模聚類[J]. 軟件學(xué)報, 2013, 24(11): 2628-2641)

[12]Cao Fuyuan, Liang Jiye, Li Deyu, et al. A weightingk-modes algorithm for subspace clustering of categorical data[J]. Neurocomputing, 2013, 108: 23-30

[13]Huang Zhexue. Extensions to thek-means algorithm for clustering large data sets with categorical values[J]. Data Mining and Knowledge Discovery, 1998, 2 (3): 283-304

[14]Zhao Weidong, Dai Weihui, Tang Chunbin.K-centers algorithm for clustering mixed type data[C]Proc of the 11th Pacific-Asia Conf on Knowledge Discovery and Data Mining. Berlin: Springer, 2007: 1140-1147

[15]Cheung Y, Jia Hong. Categorical-and-numerical-attribute data clustering based on a unified similarity metric without knowing cluster number[J]. Pattern Recognition, 2013, 46(8): 2228-2238

[16]Ji Jinchao, Bai Tian, Zhou Chunguang, et al. An improvedk-prototypes clustering algorithm for mixed numeric and categorical data[J]. Neurocomputing, 2013, 120: 590-596

[17]Renyi A. On measures of entropy and information[C]Proc of the 4th Berkley Symp on Mathematics of Statistics and Probability. Berkeley: University of California Press, 1961: 547-561

[18]Parzen E. On the estimation of a probability density function and the mode[J]. Annals of Mathematical Statistics, 1962, 33(3): 1065-1076

[19]Jenssen R, Eltoft T, Erdogmus D, et al. Some equivalences between kernel methods and information theoretic methods[J]. Journal of VLSI Signal Processing Systems, 2006, 45(12): 49-65

[20]Gokcay E, Principe J C. Information theoretic clustering[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2002, 24(2): 158-171

[21]Liang Jiye, Chin K S, Dang Chuangyin, et al. A new method for measuring uncertainty and fuzziness in rough set theory[J]. International Journal of General Systems, 2002, 31(4): 331-342

[22]Xu Weihua, Zhang Xiaoyan, Zhang Wenxiu. Knowledge granulation, knowledge entropy and knowledge uncertainty measure in ordered information systems[J]. Applied Soft Computing, 2009, 9(4): 1244-1251

[23]Wang Junhong, Liang Jiye, Qian Yuhua. Uncertainty measure of rough sets based on a knowledge granulation of incomplete information systems[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2008, 16(2): 233-244

[24]Qian Yuhua, Liang Jiye, Pedrycz W, et al. Positive approximation: An accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence, 2010, 174(910): 597-618

[25]Liang Jiye, Zhao Xingwang, Li Deyu, et al. Determining the number of clusters using information entropy for mixed data[J]. Pattern Recognition, 2012, 45(6): 2251-2265

[26]Zhao Xingwang, Liang Jiye, Cao Fuyuan. A simple and effective outlier detection algorithm for categorical data[J]. International Journal of Machine Learning and Cybernetics, 2014, 5(3): 469-477

[27]Ienco D, Pensa R G, Meo R. From context to distance: Learning dissimilarity for categorical data clustering[J]. ACM Trans on Knowledge Discovery from Data, 2012, 6(1): 1-25

Zhao Xingwang, born in 1984. PhD candidate. Member of China Computer Federation. His main research interests include data mining and machine learning.

Liang Jiye, born in 1962. Professor and PhD supervisor. Distinguished member of China Computer Federation. His main research interests include granular computing, data mining and machine learning.

2014年《計算機研究與發(fā)展》高被引論文TOP10

數(shù)據(jù)來源：中國知網(wǎng), CSCD；統(tǒng)計日期：2016-02-16

An Attribute Weighted Clustering Algorithm for Mixed Data Based on Information Entropy

Zhao Xingwang and Liang Jiye

(SchoolofComputerandInformationTechnology,ShanxiUniversity,Taiyuan030006)(KeyLaboratoryofComputationalIntelligenceandChineseInformationProcessing(ShanxiUniversity),MinistryofEducation,Taiyuan030006)

AbstractIn real applications, mixed data sets with both numerical attributes and categorical attributes at the same time are more common. Recently, clustering analysis for mixed data has attracted more and more attention. In order to solve the problem of attribute weighting for high-dimensional mixed data, this paper proposes an attribute weighted clustering algorithm for mixed data based on information entropy. The main work includes: an extended Euclidean distance is defined for mixed data, which can be used to measure the difference between the objects and clusters more accurately and objectively. And a generalized mechanism is presented to uniformly assess the compactness and separation of clusters based on within-cluster entropy and between-cluster entropy. Then a measure of the importance of attributes is given based on this mechanism. Furthermore, an attribute weighted clustering algorithm for mixed data based on information entropy is developed. The effectiveness of the proposed algorithm is demonstrated in comparison with the widely used state-of-the-art clustering algorithms for ten real life datasets from UCI. Finally, statistical test is conducted to show the superiority of the results produced by the proposed algorithm.

Key wordsclustering analysis; mixed data; attribute weighting; information entropy; dissimilarity measure

收稿日期：2015-02-12；修回日期：2015-06-09

基金項目：國家自然科學(xué)基金項目(61432011,U1435212,61402272)；國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2013CB329404)；山西省自然科學(xué)基金項目(2013021018-1)

通信作者：梁吉業(yè)(ljy@sxu.edu.cn)

中圖法分類號TP391

This work was supported by the National Natural Science Foundation of China (61432011,U1435212,61402272), the National Basic Research Program of China (973 Program) (2013CB329404), and the Natural Science Foundation of Shanxi Province of China (2013021018-1).