基于信息熵的度量類間橋方法

摘要:類間橋在化學試劑合成#65380;市場營銷#65380;生物嫁接等多個領域都有著廣泛的應用?？紤]了類間橋形成的深層次原因，給出了尋找以及結合信息熵的兩種度量類間橋的方法。

關鍵詞:聚類分析; 關系數據庫; 類間橋; 信息熵

中圖分類號:TP311文獻標志碼:A

文章編號:1001－3695(2008)02－0359－03

分類和聚類是數據挖掘研究領域中兩個十分重要的分支。分類首先需要建立一個模型，用來描述預定的數據類集或概念集，然后使用模型進行分類。基本的分類技術以判定樹歸納和貝葉斯分類為代表，主要用于預測。聚類的目標是將數據對象分組成多個類或簇，使同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。聚類分析的主要算法包括基于距離#65380;基于密度和基于層次等。然而無論是分類還是聚類，它們的目標都是將具有不同特性的對象盡可能地區分清楚，使之歸入到不同的類中，對于類間的相互作用關系卻研究得很少。如果需要將整個數據集看成一個整體來研究內部的關系，或者需要探討兩個不同類中對象間的相互制約或是相互促進，以及這種關系帶給兩個類的影響時，類間的相互作用關系就顯得尤為重要。舉個例子來說，化學研究中的催化劑就是連接兩個類的很好例子，比如廣泛用于調制香料和洗滌劑的檸檬醛，就是經牦牛兒醇和分子氧在催化劑Al2O3的作用下生成的。如果沒有催化劑，反應的效果會很差且時間很長。可見催化劑很好地起到了類間的橋梁作用，利用它把兩個類連接起來，形成互動，產生新的知識。因此，筆者形象地把本文要研究的這種類間關系稱之為類間橋。除此以外，植物學中的嫁接和市場營銷中的交叉銷售都是利用類間橋的典型例子。

可以看出，研究類間橋是很有意義和實用價值的。然而在尋找類間橋之前，還需要先解決的一個問題就是類間橋的度量。因為即使找到了類間橋，如果不能正確地判斷它的重要程度，那么對于它的研究和應用就會受到影響。正如關聯規則的支持度—置信度框架和聚類分析的閾值一樣，類間橋也需要一個度量和評判的標準。

1相關工作

文獻[1~3]介紹了尋找類間橋的一些研究。文獻[1]是在聚類算法[4]的基礎上改進的，適用于大型關系數據庫的挖掘。下面介紹另外一種算法——基于權重的算法。這種算法實質上是一個后處理過程，適用于交易數據庫的挖掘。它考慮了每種對象的權重和apriori的一些特性。整個算法分為三個步驟:發現跨類的頻繁項集;在發現的頻繁項集的基礎上用χ2檢測[5，6]確定頻繁相集，并且用項集排列樹[5]進行剪枝;計算項集的標準重要性。

2基于信息熵的度量

上面介紹的兩種方法成功地找到了所期望的類間橋。橋兩端的對象與其他類間對象相比有著特殊的#65380;更為緊密的聯系。這里再從另外一個角度來考慮有意義的類間橋，即某座橋之所以重要，不僅僅因為橋兩端對象間的緊密聯系，還在于通過這座橋，引起的兩個概念類之間相互聯系的多少。那么可以說，對一座類間橋而言，橋兩端的對象聯系越緊密，概念類之間的相互聯系就越多，這座橋就越重要。

就度量這個問題來說，用到的評價標準因數據庫類型的不同而有所區別。對關系數據庫而言，衡量橋兩端的對象聯系是否緊密就用相似度，即兩對象中具有相同屬性值的屬性個數和總屬性個數的比值;衡量概念類間的相互聯系多少可以利用信息熵。因為類間相互聯系的多少也可以看成是從一個類中可以獲得的有關另一個類的信息量的多少。這正好符合信息熵的定義和性質[7]，即信息熵越大，信息量就越多。對交易數據庫而言，第一個衡量標準用置信度計算，第二個可以根據具體情況作相應改變。由于交易數據庫可以轉換為關系數據庫，兩者并沒有本質的不同。這里先考慮關系數據庫的情況，介紹兩種相似度與信息熵結合的度量方法(假定所有的橋，包括有趣的和無趣的都已經找到)。

從結果來看，兩種方法得到的橋是完全不一樣的，這是因為它們是從不同的角度來對橋進行度量的。這里不評論它們誰更有效，因為它們是不可相互替代的。

4結束語

本文描述了類間橋的一般形式和研究它的現實意義，列舉了前期做的一些相關工作;分析了橋的深層次的特征，并利用這一點結合信息熵給出了兩種度量橋重要性的方法。最后用實驗證明了度量方法的有效性。

參考文獻:

[1]張師超，陳峰，尤曉芳.挖掘概念類間的相互作用關系[J].計算機科學，2005，32(10):128－131.

[2]QIN Ze， CHEN Feng. Discovering class－bridge rules within concep－tual Classes[J]. Asian Journal of Information Technology， 2006，5(2):169－171.

[3]ZHANG Shi－chao， CHEN Feng， WU Xin－dong， et al. Identifying bridging rules between conceptual clusters[C]//Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press， 2006:815－820.

[4]KARYPIS G， HAN E H， KUMAR V. CHAMELEON: a hierarchical clustering algorithm using dynamic modeling[C]//Proc of IEEE Computer. 1999:68－75.

[5]BAY S D， PAZZANI M J. Detecting group differences: mining contrast sets[J]. Data Ming and Knowledge Discovery， 2001，5(3):213－246.

[6]BAY S D，PAZZANI M J. Discovering and describing category differe－nces: what makes a discovered difference insightful?[C]//Proc of the 2nd Annual Meeting of the Cognitive Science Society. 2000.

[7]EPPSTEIN D， PATERSON M S， YAO F F. On nearest－neighbor graphs[J]. Discrete Comput Geom， 1997，17:263－282.

[8]XIA Chen－yi， HSU W， LEE M L， et al. BORDER: an efficient method of boundary points[J]. IEEE Trans on Knowledge and Data Engineering， 2006，18(3):289－303.

[9]BRIN S， MOTWANI R， SILVERSTEIN C. Beyond market baskets: generalizing association rules to correlations[C]//Proc of ACM SIGMOD International Conference on Management of Data. London: Springer， 1997:265－276.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”