一種特征加權(quán)的順序IB算法

，

(鄭州大學(xué) 信息工程學(xué)院，鄭州 450052)

IB方法(Information Bottleneck)是Tishby等人在1999年提出的一種基于信息論的數(shù)據(jù)分析方法[1]，該方法通過最小化源數(shù)據(jù)與聚類之間的互信息來實(shí)現(xiàn)對(duì)數(shù)據(jù)的壓縮，最大化聚類結(jié)果與相關(guān)信息的互信息來達(dá)到對(duì)相關(guān)信息保存的目的[2]，從而有效地發(fā)現(xiàn)數(shù)據(jù)中隱含的模式。這種算法在文本聚類[3-4]、圖像聚類[5]、星系光譜分析[6]、基因表達(dá)式分析[7]等領(lǐng)域都得到了有效的應(yīng)用。

順序IB算法(sIB)是Slonim于2002年提出的[3]，該算法主要是對(duì)待分析數(shù)據(jù)對(duì)象按其與另一數(shù)據(jù)對(duì)象的相關(guān)性進(jìn)行“硬”劃分，使劃分在一起的對(duì)象體現(xiàn)出源數(shù)據(jù)對(duì)象所蘊(yùn)含的某個(gè)特征模式。sIB是較好的IB算法，但是它假定樣本中各維特征對(duì)分類的貢獻(xiàn)是均勻的，事實(shí)上，由于數(shù)據(jù)集中，特征矢量的各維特征來自不同的傳感器，存在量綱、精度及可靠性的差異。為了考慮特征矢量中各維特征對(duì)聚類結(jié)果的不同貢獻(xiàn)，本文提出了一種基于特征加權(quán)的順序IB算法，該算法利用特征加權(quán)技術(shù)ReliefF對(duì)特征進(jìn)行加權(quán)，即給特征集中每一個(gè)特征賦予一定的權(quán)重，并迭代更新權(quán)值，然后根據(jù)權(quán)值大小變化特征集。特征加權(quán)后再對(duì)其進(jìn)行聚類分析，不僅使聚類效果優(yōu)于傳統(tǒng)聚類算法，同時(shí)可以分析各維特征對(duì)聚類的貢獻(xiàn)程度。

1 IB和sIB算法

1.1 IB算法

IB算法是在率失真定理基礎(chǔ)上擴(kuò)展的一種新的數(shù)據(jù)分析方法。對(duì)于率失真定理，失真度量的選擇是一大難題。因?yàn)閷?duì)于數(shù)據(jù)資源分布p(x)，不同的率失真函數(shù)會(huì)產(chǎn)生不同的結(jié)果。

在IB理論中，引入一個(gè)與源變量相關(guān)的目標(biāo)變量X～p(x)，達(dá)到壓縮X與維持相關(guān)信息平衡的目的，這個(gè)相關(guān)隨機(jī)變量稱為Y。通過尋找X的壓縮變量T(最大化維持了X與相關(guān)變量Y的互信息)來確定x,y的聯(lián)合分布。其中，T形成了從X到Y(jié)信息壓縮的“瓶頸”。該理論可表示為：

(1)

其中，d(x,t)是失真度量函數(shù)；I(T;X)表示T與X的互信息。IB理論通過失真度量函數(shù)來度量信息壓縮過程產(chǎn)生的失真，使該失真小于預(yù)先制定的值D[8]。

IB理論中，壓縮變量T只與源變量X有關(guān)，與相關(guān)變量Y無關(guān)，因此有概率分布為

p(x,y,t)=p(x,y)p(t|x,y)

(2)

在率失真中，引入拉格朗日乘數(shù)來實(shí)現(xiàn)聚類的最優(yōu)劃分。則IB的目標(biāo)函數(shù)表示為

L[p(t|x)]=I(T;X)-βI(T;Y)

(3)

乘數(shù)β用來控制壓縮和失真的平衡。p(t|x)為隨機(jī)映射函數(shù)。IB理論克服了率失真的缺點(diǎn)，不用考慮如何選取失真度量的問題。

1.2 sIB算法

相對(duì)于其他IB算法，sIB算法可以保證能夠及時(shí)得到一個(gè)固定的解，而且有較為理想的時(shí)間復(fù)雜度和空間復(fù)雜度。是一個(gè)將已知自凝聚算法映射到類似“順序KMeans算法”的算法。

sIB算法先將x隨機(jī)地劃分為M個(gè)簇(M保持不變)，再在每一步中將每個(gè)x從簇t(x)中提取出來，再將x合并到tnew中去，從而得到新的tnew劃分[9]。

tnew=arg mint∈Tcost({x},t)

(4)

cost({x},t)=(p(x)+p(t))×JSπ1,π2(p(y|x),p(y|t)),其中π1和π2滿足

通過不同的初始值T，可以得到不同的結(jié)果，以此來降低局部最優(yōu)解潛在的不穩(wěn)定性。因此sIB算法適于實(shí)際應(yīng)用，而且可以得到局部穩(wěn)定解。

2 特征加權(quán)的順序IB算法(wsIB算法)

特征加權(quán)是從原始特征集中，按照某一評(píng)價(jià)標(biāo)準(zhǔn),對(duì)具有不同區(qū)分特性的特征子集進(jìn)行加權(quán)的方法，是提高聚類質(zhì)量的有效方法[10]?；镜腞elief算法是Kira等在1992 年提出的，它可以檢測(cè)那些與目標(biāo)屬性不相關(guān)的特征[11]，當(dāng)時(shí)僅局限于解決兩類問題。1994年Kononenko擴(kuò)展了Relief算法得出一種新的算法，即ReliefF算法，其可以解決多類問題、回歸問題以及數(shù)據(jù)缺失問題[12]。該算法的基本思想是根據(jù)每個(gè)屬性對(duì)聚類結(jié)果影響程度的不同給每一特征項(xiàng)賦予不同的權(quán)重，并迭代更新權(quán)值，然后根據(jù)權(quán)值大小對(duì)特征子集做相應(yīng)的加權(quán)變換，使得好的特征聚集同類樣本，離散異類樣本。

數(shù)據(jù)集X中，xi=[xi1,xi2,…,xiN]T表示第i個(gè)樣本的N個(gè)特征值。對(duì)于任意一個(gè)樣本xi，首先找出R個(gè)與xi同類的最鄰近的樣本hi,i=1,2，…，R。設(shè)diff-hit是N×1的矩陣，表示最鄰近樣本hi與xi在特征上的差異。

(5)

然后在與xi不同類的子集中找到R個(gè)最鄰近的樣本mli，i=1,2,…，R,l≠class(xi)。設(shè)diff-miss是N×1的矩陣，表示mli與xi在特征上的差異，則

(6)

式中：p(l)為第l類數(shù)據(jù)出現(xiàn)的概率;p(class(xi))是xi在類中出現(xiàn)的概率。

sIB算法以循環(huán)的方式遍歷所有的數(shù)據(jù)點(diǎn)，對(duì)每個(gè)點(diǎn)檢查是否要把它從當(dāng)前簇中取出并放到另一個(gè)簇中，這個(gè)循環(huán)過程迭代至局部最優(yōu)。將ReliefF算法融入到sIB算法中，在順序聚類算法的基礎(chǔ)上對(duì)特征值進(jìn)行加權(quán)。令λ=[λ1,λ2,…，λi]T表示每個(gè)特征的權(quán)值。將目標(biāo)函數(shù)改寫為

tnew←arg mint∈T∑icost({λix},t)

(7)

λ更新式為

λ=λ-(diff-hit)/R+(diff-miss)/R

(8)

當(dāng)目標(biāo)函數(shù)循環(huán)至最小值，就得到了最優(yōu)的聚類結(jié)果。改進(jìn)后的wsIB算法描述如下：

wsIB算法執(zhí)行過程：

輸入:數(shù)據(jù)集X,X具有聯(lián)合分布p(x,y)；

平衡參數(shù)β;簇?cái)?shù)k.

輸出:

X到k簇的隨機(jī)劃分T.

初始化：

T←將X隨機(jī)劃分為k個(gè)簇.

主循環(huán)：

Done=False;

While not Done

Done←TRUE；

λ=λ-(diff-hit)/R+(diff-miss)/R

For everyx∈X

將x從其歸屬的t中取出，形成單元素集合{x}

tnew←arg mint∈T∑icost({λix},t)

iftnew≠t

done←FALSE

將x合并到tnew中；

End For

End While

對(duì)目標(biāo)函數(shù)tnew的加權(quán),改變了多維數(shù)據(jù)集中數(shù)據(jù)項(xiàng)之間在歐式空間中的距離，聚類中循環(huán)更新簇的分配將權(quán)值計(jì)算在內(nèi)，進(jìn)而影響了算法迭代過程中不同特征值對(duì)聚類結(jié)果的影響。

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)為在經(jīng)典數(shù)據(jù)集UCI中隨機(jī)選取的8組數(shù)據(jù)集，包括：Cancer(醫(yī)學(xué)乳腫瘤記錄)、Car(汽車評(píng)估資料庫)、Diabetes(比馬族人糖尿病數(shù)據(jù)記錄)、Hepatitis(醫(yī)學(xué)肝炎記錄數(shù)據(jù))、Iris(鳶尾花數(shù)據(jù)記錄)、Kr_vs_kp(國(guó)際象棋殘局?jǐn)?shù)據(jù))、Votes(1984美國(guó)國(guó)會(huì)選舉記錄)、Credit_a(信用記錄數(shù)據(jù))。用傳統(tǒng)sIB算法和加權(quán)改進(jìn)后的wsIB算法分別對(duì)其聚類，得出的聚類結(jié)果用精度、召回率和準(zhǔn)確率進(jìn)行評(píng)估。實(shí)驗(yàn)數(shù)據(jù)描述如表1所示。

表1 UCI數(shù)據(jù)集

3.2 實(shí)驗(yàn)結(jié)果

對(duì)于數(shù)據(jù)集Cancer，本文得到的加權(quán)矩陣為：λ= [2.633 3，1.322 2，1.477 8，2.055 6，1.066 7，2.666 7，1.855 6，2.522 2，0.071 1]。從這個(gè)矩陣來看，第六維特征的貢獻(xiàn)最大，第九維特征的貢獻(xiàn)最小。由此可見，對(duì)于Cancer數(shù)據(jù)集來說，加權(quán)之后特征值從均勻貢獻(xiàn)變?yōu)榈谝痪S特征值最高的不均勻貢獻(xiàn)。

表2 sIB算法和wsIB聚類結(jié)果對(duì)比

實(shí)驗(yàn)結(jié)果對(duì)比如表2所示，對(duì)于Car數(shù)據(jù)集，加權(quán)后的聚類結(jié)果準(zhǔn)確率提高了6.77%、精度提高了2.39%、召回率提高了5.55%。

3.3 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)所選取的數(shù)據(jù)從150到319 6個(gè)不等，數(shù)據(jù)的特征個(gè)數(shù)從4到36個(gè)不等。對(duì)實(shí)驗(yàn)結(jié)果分析可得出：

(1)較傳統(tǒng)sIB算法，wsIB算法中數(shù)據(jù)集的3種評(píng)價(jià)指標(biāo)(準(zhǔn)確率、精度、召回率)均得到不同程度的提高。

(2)wsIB算法對(duì)于特征個(gè)數(shù)少、特征個(gè)數(shù)多以及數(shù)據(jù)樣本個(gè)數(shù)少、數(shù)據(jù)樣本個(gè)數(shù)多的數(shù)據(jù)集均有效。

(3)wsIB算法不僅改善了聚類的性能，還有助于分析各維特征對(duì)聚類的貢獻(xiàn)度。

wsIB算法對(duì)各個(gè)聚類成員的先進(jìn)性進(jìn)行了劃分，利用權(quán)重改變了數(shù)據(jù)項(xiàng)之間的相對(duì)距離，降低了劣質(zhì)聚類成員的影響，提升了優(yōu)質(zhì)聚類成員的影響，使聚類質(zhì)量大大提高。因此，該算法在精確度方面優(yōu)于傳統(tǒng)IB聚類算法。

4 結(jié) 語

本文提出的wsIB方法可以很容易地?cái)U(kuò)展到其他聚類算法中。因此，將特征加權(quán)應(yīng)用到其他協(xié)同學(xué)習(xí)方法上是未來的一個(gè)研究方向。另外，可以對(duì)本文提出的方法進(jìn)行進(jìn)一步的理論分析，并將它應(yīng)用到其他領(lǐng)域之中。

參考文獻(xiàn)：

[1] Tishby N, Pereira F, Bialek W.The Information Bottleneck Method[C]//Proceeding of the 37th Allerton Conference on Communication.USA:Control and Computing，1999: 368-377.

[2] 朱真峰, 葉陽東.基于變異的迭代 sIB 算法[J].計(jì)算機(jī)研究與發(fā)展, 2008, 44(11): 1832-1838.

[3] Slonim N, Friedman N, Tishby N.Unsupervised Document Classification Using Sequential Information Maximization[C]//Proceeding of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Finland:ACM, 2002: 129-136.

[4] Slonim N, Tishby N.Document Clustering Using Word Clusters via the Information Bottleneck Method[C]// Proceeding of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Greece:ACM, 2000: 208-215.

[5] Goldberger J, Gordon S, Greenspan H.Unsupervised Image-set Clustering Using an Information Theoretic Framework[J].IEEE Transactions on Image Processing, 2006, 15(2): 449-458.

[6] Slonim N, Somerville R, Tishby N, et al.Objective Classification of Galaxy Spectra Using the Information Bottleneck Method[J].Monthly Notices of the Royal Astronomical Society, 2001, 323(2): 270-284.

[7] Tishby N, Slonim N.Data Clustering by Markovian Relaxation and the Information Bottleneck Method[C]// Proceeding of the 13th Annual Conference on Neural Information Processing Systems.Colorado, USA：NIPS，2000: 640-646.

[8] 葉陽東, 劉東, 賈利民.一種自動(dòng)確定參數(shù)的 sIB 算法[J].計(jì)算機(jī)學(xué)報(bào), 2007, 30(6): 969-978.

[9] Ye Y D, Ren Y, Li G.Using Local Density Information

to Improve IB Algorithms[J].Pattern Recognition Ietters, 2011, 32(2): 310-320.

[10] Ji B, Ye Y D, Xiao Y.Mutual Information Evaluation: a Way to Predict the Performance of Feature Weighting on Clustering[J].Intelligent Data Analysis, 2013, 17(6): 1001-1021.

[11] Kira K, Rendell L A.A Practical Approach to Feature Selection[C]//Proceeding of the 9th International Workshop on Machine Learning.Britain: Morgan Kaufmann Publishers Inc., 1992: 249-256.

[12] Lim S C, Jang S J, Lee S P.Music Genre/Mood Classification Using a Feature-based Modulation Spectrum[C]//International Conference on Mobile IT Convergence(ICMIC)．Washington: Procceeding of IEEE Computer Society, 2011:133-136.