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

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

關鍵詞：粗糙集； 離散化； 信息熵； 斷點

中圖分類號：TP301．6文獻標志碼：A

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

0引言

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

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

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

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

在決策表DT=〈U，R，V，f〉中，對論域U的連續屬性離散化的結果就是要在每個連續屬性a的值域Va中尋找一個恰當的劃分Pa，且在劃分Pa下的決策表與原決策表具有相同的決策能力。Pa將屬性值域劃分為若干互不相交的子區間，對每個子區間以符號賦值，即得到一組Va上的離散化取值。因為任何劃分Pa都是由一組值域Va內的斷點序列(v1＜v2＜…＜vk)確定的，所以離散化就是要在每個連續值域Va的斷點序列集合中選出一個恰當的斷點序列，進而形成滿足需要的劃分。一個決策表的最優劃分通常不是惟一的。相關文獻已經證明，在一個給定的決策表中尋找最優劃分是NP難題[1]。因此，人們設計了各種算法以求得近似解，即尋找次優劃分。

3計算初始斷點集合算法

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

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

根據上面的定義，任意兩個有序屬性值序列S1和S2的位置關系如圖1所示。

依據圖1所示得到計算初始斷點集合的算法如下：

算法1計算初始斷點集合算法

a)初始斷點集合P為空集。

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

（a）根據決策屬性值將條件屬性a的值劃分成若干集合，并由各集合構造出相應的有序屬性值序列。

（b）查看有序屬性值序列對Si和Sj(i＜j)：

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

● 構造有序屬性值序列S=Si∪Sj，分別確定max(B(Si)，B(Sj))和min(T(Si)，T(Sj))在S中的序號m和n；

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

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

（c)若仍有未查看的屬性值序列對，則轉（b)；

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

4約簡初始斷點集合算法

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

5實驗結果和分析

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

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

6結束語

本文討論了基于粗糙集理論的屬性離散化方法，并在此基礎上提出了基于信息熵的離散化算法，本文算法不僅保證了決策表的分辨關系，而且還不改變決策表的相容度。實驗結果表明本文算法適于處理大規模數據。

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

參考文獻：

［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－hua， 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]王國胤．Rough集理論與知識獲取[M]．西安:西安交通大學出版社，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]侯利娟，王國胤，聶能，等. 粗糙集理論中的離散化問題[J]．計算機科學，2000，27(12):89－94．

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

[10]李興生． 一種基于云模型的決策表連續屬性離散化方法[J]．模式識別與人工智能，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－hong，ZHANG Shu－cui，FAN 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－hua，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.

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