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

[關(guān)鍵詞]信息粒 熵

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

一、引言

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

二、有關(guān)粗糙集和粒計算的概念

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

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

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

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

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

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

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

[“<=30”]AND[yes]＝00000000101000中1的個數(shù)為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

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

三、總結(jié)

本文討論了粒和等價類的聯(lián)系，并采用粒的二進制數(shù)表示法將它們統(tǒng)一了起來，因此將有關(guān)信息論的計算轉(zhuǎn)化為二進制數(shù)之間的計算，提高了速度，節(jié)省了內(nèi)存。

參考文獻：

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

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

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

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

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

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

作者簡介：

李潔穎，女，河南新鄉(xiāng)人，助教，研究方向為人工智能和網(wǎng)絡(luò)技術(shù)。