基于粒的二進制數表示的一種熵的計算方法

[摘要]很多決策樹算法中，進行分裂選擇測試屬性的時候，都要用到對屬性熵的計算和比較，提出一種方法，該方法首先將屬性的等價類和粒聯系起來，繼而利用粒的二進制數表示來計算相應屬性的熵，也就是說將等價類轉化為粒的二進制數表示，這樣只需要將粒的二進制數駐留內存就可以計算熵了，現在在包含數以百萬計樣本的非常大的訓練集是很普通的，利用這種方法就可以減少在計算熵時訓練樣本在主存和高速緩存換進換出的次數，達到提高效率的目的。

[關鍵詞]信息粒 熵

中圖分類號：TP3文獻標識碼：A文章編號：1671－7597（2009）0320040－01

一、引言

由Z.Pawlak與他的合作者于70年代提出的粗糙集理論從一種全新的視覺審視知識，認為知識與分類相關，知識是有粒度的。所謂信息粒（Information Granule）是指人類在解決處理和存貯信息的有限能力上的一種反映，也就是人類在解決和處理大量復雜信息問題時，需要將大量復雜信息按其各自的特征和性能將其劃分成若干較簡單的塊，而每個如此劃分出來的塊被看成一個粒。這種處理信息的過程就被稱作信息粒化。信息的顆粒化相當于把原始的復雜的問題分解為多個易管理的子問題，即把大顆粒分解為小顆粒，顆粒化問題隨處可見，它是許多學科的共同研究課題。粒計算是由T.Y.Lin提出的，現在已經成為數據挖掘等領域的一個重要工具。

二、有關粗糙集和粒計算的概念

一個論域U在一個等價關系R下可以得到U關于R的一個劃分，劃分后的所有U的子集的集合就是U關于R的一個商集U/R，商集U/R中的每個元素就是一個粒。知識的這種顆粒狀結構通過等價關系的等價類表示。

既然等價類可以表示知識的顆粒狀結構，那么將等價類看成是粒就是很容易理解的事情因為施行粒計算比施行等價類計算速度要快的多，靈活的多[2]。

例如表一是對AllElectronics顧客是否會買計算機所做的調查的一個決策表。按條件屬性age分類，則可得商集U/IND(age)={[“<=30”]，[“31…40”]，[“>40”]}。按決策屬性buys_computer分類，則可得商集U/IND(buys_computer)={[no],[yes]}。為了將等價類和粒建立聯系，我們將商集中的元素作為粒，顯然它是一種等價類。為了方便地表示一個粒，我們引入一個二進制數表示。表示規則為：對每個粒中的元素都可以給出它在全域U上的位置即下標表示法，然后以下標編碼對應于二進制位數的位數來確定二進制位數的0、1取值，即Oi∈U且出現于某個等價類時，相應的表示該等價類的二進制數的第i位上置1，否則置0。具體的表示見表二。

設K＝（U，M）為一知識庫，R∈M為一知識，在R對U形成均勻劃分的情況下，R的熵值較大，而此時知識的粒度GD（R）較小；由表三可以看出它們各自的變化趨勢。

接下來討論如何利用粒的二進制數表示法來求取對應屬性的熵。我們還用上面的那個例子，由表二已知U/IND(age)={[“<=30”],[“31…40”]，[“>40”]},

[“<=30”]=11000001101000，[“31,…,40”]=00100010000110，[“>40”]=00011100010001，其中sij是子集sj中類Ci的樣本數，pij＝是Sj中的樣本屬于類Ci的概率。

因為[“<=30”]AND [no]＝11000001000000中1的個數為3，所以s11＝3，

[“<=30”]AND[yes]＝00000000101000中1的個數為2，所以s12＝2

按照公式，對于age＝”<=30”, I(s11,s12)=－3/5log2(3/5)－2/5log2(2/5)=0.971

同理對于age=”31…40”，易知I（s11,s12）=0,

age=”>40”時，I（s11,s12）=0.971

進而知道E（age）＝5/14 I（s11,s12）+4/14 I（s11,s12）+5/14 I（s11,s12）=0.694

至此，我們利用粒的二進制數表示法成功地求出了對應屬性的熵。熵這個指標，在生成判定樹的算法中，進行分裂選擇測試屬性時，一般作為判定指標。我們利用上面提到的思想來選擇最佳的分裂方案，不過這里計算的不是進行分割時熵的減少量，而是分割后所產生的熵選擇具有最小熵值的屬性，顯然，這個和計算熵的減少量是異曲同工的。

三、總結

本文討論了粒和等價類的聯系，并采用粒的二進制數表示法將它們統一了起來，因此將有關信息論的計算轉化為二進制數之間的計算，提高了速度，節省了內存。

參考文獻：

[1]張鈸、張鈴，問題求解理論及原理[M].北京：清華大學出版社，1990.

[2]劉斕、劉清，基于粒的二進制運算的關聯規則提取方法[J].南昌大學學報，2003:27(1).

[3]Y.Y.Yao. On modeling data mining with granular computing[J].Proceedings of COMPSAC 2001,pp,638-643,2001.

[4]苗奪謙，范世棟. 知識的粒度計算及其應用[J].系統工程理論與實踐，2002,1(1):48-56.

[5]王國胤，Rough集理論與知識獲取[M].西安交通大學出版社，2001.

[6]J.W.Han,M.Kamber:Data Mining:Concepts and Techniques[M].Morgan Kaufmann Publishers,2001.

作者簡介：

李潔穎，女，河南新鄉人，助教，研究方向為人工智能和網絡技術。