基于粗糙集理論和信息熵的屬性離散化方法

摘要：在分析當(dāng)前研究中常用的屬性離散化方法的基礎(chǔ)上，提出了一種計(jì)算初始斷點(diǎn)集合的算法；定義了斷點(diǎn)的信息熵，并以此作為對(duì)斷點(diǎn)重要性的度量，提出了一種基于粗糙集理論和信息熵的屬性離散化算法。通過與其他離散化算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了本算法的有效性，而且在樣本數(shù)和條件屬性數(shù)目不斷增大時(shí)仍有很高的效率。

關(guān)鍵詞：粗糙集； 離散化； 信息熵； 斷點(diǎn)

中圖分類號(hào)：TP301．6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1701－03

0引言

Pawlak提出的粗糙集是一種新的處理不精確、不完全與不相容知識(shí)的數(shù)學(xué)理論，目前已在模式識(shí)別、機(jī)器學(xué)習(xí)、知識(shí)發(fā)現(xiàn)和決策支持等方面獲得了廣泛的應(yīng)用。人們對(duì)基于粗糙集模型的離散化方法已經(jīng)取得了一些有價(jià)值的研究成果。Nguyen等人提出了粗糙集與布爾邏輯方法[1]，該方法具有完備性，即理論上可以找出所有可能組合的離散化斷點(diǎn)集，但是其算法復(fù)雜度是指數(shù)級(jí)的，無法在實(shí)際問題中應(yīng)用；有些文獻(xiàn)提出了在此基礎(chǔ)上的幾種改進(jìn)貪心算法[2~5]，這些算法都是基于斷點(diǎn)對(duì)實(shí)例的可分性，屬于局部尋優(yōu)搜索算法；有的文獻(xiàn)則采用遺傳算法搜索最佳離散化斷點(diǎn)集合[6，7]，它們屬于整體搜索算法；有的文獻(xiàn)提出了一種基于屬性重要性的離散化方法[8]；有的文獻(xiàn)給出了一種將多項(xiàng)式超曲面與支撐向量機(jī)方法相結(jié)合的離散化方法[9]；有的文獻(xiàn)提出了一種基于云模型的離散化方法[10]；有的文獻(xiàn)將模糊性引進(jìn)到離散化中[11]；有的文獻(xiàn)則討論了離散化中的信息粒度[12]；有的文獻(xiàn)提出了基于屬性聚類的離散化方法[13]。

本文提出了一種計(jì)算初始斷點(diǎn)集合的算法，該算法不但能夠保證決策表的分辨關(guān)系，而且求得的初始斷點(diǎn)集合的基數(shù)小于按參考算法求得的結(jié)果[1]。并從決策表信息熵的角度提出了一種新的連續(xù)屬性離散化算法，在保證決策表的相容度不變的同時(shí)還考慮了由連續(xù)條件屬性和離散條件屬性構(gòu)成的混合決策表。實(shí)驗(yàn)結(jié)果表明，該算法的綜合性能優(yōu)于參考算法[1，8]。

1粗糙集的基本概念[ 5]

2決策表屬性離散化問題描述

在決策表DT=〈U，R，V，f〉中，對(duì)論域U的連續(xù)屬性離散化的結(jié)果就是要在每個(gè)連續(xù)屬性a的值域Va中尋找一個(gè)恰當(dāng)?shù)膭澐諴a，且在劃分Pa下的決策表與原決策表具有相同的決策能力。Pa將屬性值域劃分為若干互不相交的子區(qū)間，對(duì)每個(gè)子區(qū)間以符號(hào)賦值，即得到一組Va上的離散化取值。因?yàn)槿魏蝿澐諴a都是由一組值域Va內(nèi)的斷點(diǎn)序列(v1＜v2＜…＜vk)確定的，所以離散化就是要在每個(gè)連續(xù)值域Va的斷點(diǎn)序列集合中選出一個(gè)恰當(dāng)?shù)臄帱c(diǎn)序列，進(jìn)而形成滿足需要的劃分。一個(gè)決策表的最優(yōu)劃分通常不是惟一的。相關(guān)文獻(xiàn)已經(jīng)證明，在一個(gè)給定的決策表中尋找最優(yōu)劃分是NP難題[1]。因此，人們?cè)O(shè)計(jì)了各種算法以求得近似解，即尋找次優(yōu)劃分。

3計(jì)算初始斷點(diǎn)集合算法

在保證決策表分辨關(guān)系的前提下，如何使初始斷點(diǎn)集合具有盡可能小的基數(shù)，對(duì)后繼工作具有非常重要的意義，它不但可以減小約簡(jiǎn)初始斷點(diǎn)集合的計(jì)算量，而且可以減小計(jì)算過程的時(shí)間和空間開銷。

定義4有序?qū)傩灾敌蛄小Q策表DT=〈U，R，V，f〉，R=C∪g0gggggg，連續(xù)屬性a∈C。設(shè)Ia=[VBa，VTa]是a上的取值區(qū)間，若VBa＜V1a＜V2a＜…＜VTa，則序列S={VBa，V1a，V2a，…，VTa}稱為有序?qū)傩灾敌蛄?。VBa稱為S的下確界，記為B(S)，VTa稱為S的上確界，記為T(S)。

根據(jù)上面的定義，任意兩個(gè)有序?qū)傩灾敌蛄蠸1和S2的位置關(guān)系如圖1所示。

依據(jù)圖1所示得到計(jì)算初始斷點(diǎn)集合的算法如下：

算法1計(jì)算初始斷點(diǎn)集合算法

a)初始斷點(diǎn)集合P為空集。

b)查看決策表中的條件屬性a：

（a）根據(jù)決策屬性值將條件屬性a的值劃分成若干集合，并由各集合構(gòu)造出相應(yīng)的有序?qū)傩灾敌蛄?。?/p>

（b）查看有序?qū)傩灾敌蛄袑?duì)Si和Sj(i＜j)：

● 若min(T(Si)，T(Sj))≤max(B(Si)，B(Sj))將max(B(Si)，B(Sj))加入P，轉(zhuǎn)（c)；

● 構(gòu)造有序?qū)傩灾敌蛄蠸=Si∪Sj，分別確定max(B(Si)，B(Sj))和min(T(Si)，T(Sj))在S中的序號(hào)m和n；

● 將S中的元素S[m]和S[n]加入P；

● 對(duì)于S中S[m]和S[n]間的元素（設(shè)為S[k]），若S[k-1]與S[k]僅同時(shí)在Sj中，則忽略S[k]；否則將S[k]加入P。

（c)若仍有未查看的屬性值序列對(duì)，則轉(zhuǎn)（b)；

（d）若仍有未查看的條件屬性，則轉(zhuǎn)（b）；否則算法結(jié)束，輸出集合P。

4約簡(jiǎn)初始斷點(diǎn)集合算法

離散化本質(zhì)上就是利用選取的斷點(diǎn)來對(duì)條件屬性構(gòu)成的空間進(jìn)行劃分的問題，即把這個(gè)n（n為條件屬性的個(gè)數(shù)）維空間劃分成有限個(gè)區(qū)域。顯然，采用不同的劃分方法，離散化后得到的新的決策表的相容性有可能與原決策表的相容性不同。隨著屬性個(gè)數(shù)和樣本量的增加，初始斷點(diǎn)的數(shù)目將會(huì)不斷增大，因此，初始斷點(diǎn)集合約簡(jiǎn)算法的效率對(duì)后續(xù)的規(guī)則獲取是很重要的。

5實(shí)驗(yàn)結(jié)果和分析

為驗(yàn)證本文提出的離散化算法的有效性，本文選擇貪心算法（用A1表示）和屬性重要性算法（用A2表示）與本文提出的算法（用A3表示）進(jìn)行了詳細(xì)對(duì)比實(shí)驗(yàn)。首先采用以上三種離散化方法對(duì)樣本數(shù)據(jù)進(jìn)行離散化處理，然后進(jìn)行屬性約簡(jiǎn)和屬性值約簡(jiǎn)從而得到推理規(guī)則，最后采用獲得的規(guī)則對(duì)測(cè)試數(shù)據(jù)進(jìn)行識(shí)別測(cè)試。全部算法采用C++語言實(shí)現(xiàn)，測(cè)試計(jì)算機(jī)的基本配置為：CPU為奔騰4處理器（主頻1.7 GHz），內(nèi)存為256 MB。實(shí)驗(yàn)數(shù)據(jù)選取了來自網(wǎng)站http://www.fmt.vein.hu/softcomp/ucidata/dataset/的UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的一些實(shí)際數(shù)據(jù)集，針對(duì)四組不同的實(shí)驗(yàn)數(shù)據(jù)分別進(jìn)行5折交叉驗(yàn)證。四個(gè)實(shí)驗(yàn)數(shù)據(jù)的詳細(xì)信息如表1所示，斷點(diǎn)計(jì)算結(jié)果如圖2所示，識(shí)別測(cè)試結(jié)果如圖3所示。其中Ⅰ指正確識(shí)別率，Ⅱ指錯(cuò)誤識(shí)別率，Ⅲ指拒絕識(shí)別率。

從斷點(diǎn)計(jì)算結(jié)果中可以看出：如圖2（a）所示，A2的剩余屬性數(shù)目最少，A1和A3的剩余屬性數(shù)目相當(dāng)；如（b)所示，A3的斷點(diǎn)數(shù)目最少，A1和A2的斷點(diǎn)數(shù)目相當(dāng)如（c）所示，隨著樣本數(shù)和條件屬性數(shù)目的不斷增大，計(jì)算時(shí)間A2和A3增加不多，而A1急劇增加，因此A1更適合小樣本數(shù)據(jù)集。出現(xiàn)這種情況的主要原因是，A1會(huì)把所有可能的斷點(diǎn)都計(jì)算出來，因此計(jì)算時(shí)間會(huì)隨著樣本數(shù)和條件屬性數(shù)目的增大而急劇增加；而A2和A3是在可能的斷點(diǎn)集合中尋找符合要求的最小斷點(diǎn)集合，所以它們的計(jì)算時(shí)間隨著樣本數(shù)和原始屬性數(shù)目的增大只是小幅度地增加。從識(shí)別測(cè)試結(jié)果（圖3）中可以看出，正確識(shí)別率A1和A3相當(dāng)，略好于A2，錯(cuò)誤識(shí)別率A2略高一些，而且其拒絕識(shí)別率也略高于A1和A3。實(shí)驗(yàn)結(jié)果說明本文提出的離散化算法不僅是有效的，而且在樣本數(shù)和條件屬性數(shù)目不斷增大時(shí)仍有很高的效率。

6結(jié)束語

本文討論了基于粗糙集理論的屬性離散化方法，并在此基礎(chǔ)上提出了基于信息熵的離散化算法，本文算法不僅保證了決策表的分辨關(guān)系，而且還不改變決策表的相容度。實(shí)驗(yàn)結(jié)果表明本文算法適于處理大規(guī)模數(shù)據(jù)。

今后的研究工作包括改進(jìn)此算法，使其能夠處理不完備數(shù)據(jù)，最終使改進(jìn)的算法具有普遍適應(yīng)性；把遺傳算法與粗糙集理論相結(jié)合，進(jìn)一步提高解決大規(guī)模數(shù)據(jù)問題的效率。

參考文獻(xiàn)：

［1］NGUYEN H S，SKOWRON A. Quantization of real values attributes，rough set and Boolean reasoning approaches[C]//Proc ofthe 2nd Joint Annual Conference on Information Science， Wrightsville Beach:[s.n.]，1995:34－37．

[2]NGUYEN S H，NGUYEN H S．Some efficient algorithms for rough set methods[C]//Proc ofConference on Information Processing and Management of Uncertainty in Knowledge－based Systems. 1996:1451－1456．

[3]SUSMAGA R．Analyzing discretizations of continuous attributes given a monotonic discrimination function[J]．Intelligent Data Analysis，1997，1(4):157－179．

[4]DAI Jian－h(huán)ua， LI Yuan－xiang．Study on discretization based on rough set theory[C]//Proc of the 1st International Conference on Machine Learning and Cybernetics. 2002:1371－1373．

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

[6]CHEN Cai－yun，LI Zhi－guo，QIAO Sheng－yong，et al.Study on discre－tization in rough set based on genetic algorithm[C]//Proc of the 2nd International Conference on Machine Learning and Cybernetics. 2003:1430－1434．

[7]HUANG Jin－jie， LI Shi－yong．A GA－based approach to rough data model[C]//Proc of the 5th World Congress on Intelligent Control and Automation. 2004:1880－1884．

[8]侯利娟，王國(guó)胤，聶能，等. 粗糙集理論中的離散化問題[J]．計(jì)算機(jī)科學(xué)，2000，27(12):89－94．

[9]何亞群， 胡壽松． 粗糙集中連續(xù)屬性離散化的一種新方法[J]．南京航空航天大學(xué)學(xué)報(bào)，2003，35(3):213－215．

[10]李興生． 一種基于云模型的決策表連續(xù)屬性離散化方法[J]．模式識(shí)別與人工智能，2003，16(3):33－38．

[11]ROY A，PAL S K．Fuzzy discretization of feature space for a rough set classier[J]．Pattern Recognition Letters，2003，24(6):895－902．

[12]WANG Li－h(huán)ong，ZHANG Shu－cui，F(xiàn)AN Hui，et al. The information granulation in discretization[C]//Proc of the 2nd International Conference on Machine Learning and Cybernetics. 2003:2620－2623．

[13]LI Meng－xin，WU Cheng－dong，HAN Zhong－h(huán)ua，et al. A hierarchical clustering method for attribute discretization in rough set theory[C]//Proc of the 3rd International Conference on Machine Learning and Cybernetics. 2004:3650－3654.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文