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

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

中圖分類號(hào)：TP3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1671－7597（2009）0320040－01

一、引言

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

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

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

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

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

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

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

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

因?yàn)閇“<=30”]AND [no]＝11000001000000中1的個(gè)數(shù)為3，所以s11＝3，

[“<=30”]AND[yes]＝00000000101000中1的個(gè)數(shù)為2，所以s12＝2

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

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

age=”>40”時(shí)，I（s11,s12）=0.971

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

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

三、總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

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

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

作者簡(jiǎn)介：

李潔穎，女，河南新鄉(xiāng)人，助教，研究方向?yàn)槿斯ぶ悄芎途W(wǎng)絡(luò)技術(shù)。