基于粗糙集理論的兩類離散化方法研究

張文波

（重慶郵電大學計算機科學與技術(shù)研究所，重慶 400065）

0 引言

信息系統(tǒng)連續(xù)型屬性值的離散化對決策規(guī)則或決策樹的學習具有非常重要的意義，它能夠提高系統(tǒng)對樣本的聚類能力，增強系統(tǒng)抗數(shù)據(jù)噪音的能力，減少機器學習算法的時間和空間開銷，提高其學習精度。由于最優(yōu)離散化問題是NP（non-deterministic polynomial）困難的，因此在實際應(yīng)用中通常采用啟發(fā)式算法來計算次最優(yōu)結(jié)果。粗糙集是一種有效的數(shù)據(jù)離散化工具，基于這一模型已發(fā)展了很多典型的啟發(fā)式離散化方法，但研究結(jié)果表明，沒有一種絕對好或絕對差的通用的離散化方法［1］，因此，需要研究不同離散化算法的特性，以便為不同的數(shù)據(jù)集選擇合適的算法。

大部分現(xiàn)有的基于粗糙集理論的啟發(fā)式離散化方法都是建立在一種輔助矩陣基礎(chǔ)之上［2］。由此我們可以將離散化方法大致分為2類:一類是基于輔助矩陣的算法;另一類算法在離散化過程中則沒有建立和利用輔助矩陣。基于信息熵的離散化算法就是后一類算法的典型代表。本文通過系統(tǒng)實驗研究，分析比較了基于輔助矩陣和基于信息熵的典型算法的性能。結(jié)果表明:基于輔助矩陣的方法性能比較穩(wěn)定，通用性相對較強，但復(fù)雜度較高，較適合于處理小容量數(shù)據(jù)集;信息熵類算法的識別率雖低于輔助矩陣類算法，但是在正確識別率方面有一定優(yōu)勢且計算時間短，適合于處理較大容量數(shù)據(jù)集。

1 兩類啟發(fā)式離散化算法思想

粗糙集研究和處理的對象通常是決策系統(tǒng)，記為S=（U，V，f，C∪j5i0abt0b），其中:U 是有限樣本集合，稱為論域;C是描述樣本的條件屬性集合，d是決策屬性，C∩j5i0abt0b= ?;Va=［la，ra］是屬性 a∈C∪j5i0abt0b的值域，V=∪Va;f:U→C∪j5i0abt0b是從樣本空間向?qū)傩钥臻g的映射函數(shù)。

樣本x∈U在屬性a∈（C∪j5i0abt0b）上的取值通常記為a（x），即f（x，a）=a（x）。若S中存在取值連續(xù)的屬性，則需對S進行離散化。

一般說來，基于粗糙集理論的啟發(fā)式離散化算法都是以相鄰屬性值的平均值為候選斷點［3］，然后根據(jù)某種啟發(fā)式標準，從候選斷點集合中選擇一個能保證原系統(tǒng)的樣本分辨關(guān)系、且足夠小的子集來對系統(tǒng)進行離散化。不同啟發(fā)式算法最核心的區(qū)別就在于它們采用不同的啟發(fā)式方式來度量候選斷點的重要性。

1.1 基于輔助矩陣的離散化算法

這類算法根據(jù)決策系統(tǒng)及其候選斷點集合來構(gòu)造一個輔助矩陣，并通過考察矩陣的特征來計算候選斷點的重要性。

定義1 給定S=（U，V，f，C∪j5i0abt0b）及其候選斷點集合R*，S*=（U*，R*）是其輔助矩陣，其中:是屬性a的第r個候選斷點

S*表達了與S相同的樣本分辨關(guān)系。顯然，它能直觀地、比較全面地反映候選斷點的特征:從列方向看，各列上值為1的元素數(shù)目能夠直接描述該候選斷點對樣本的分辨能力;從行方向看，各行上值為1的元素個數(shù)反映了能夠分辨相應(yīng)樣本對的候選斷點的多寡，因而能間接地反映候選斷點的重要程度。基于輔助矩陣的各種典型算法就是從不同的角度，按不同的方式來利用S*的行、列方向的特征，計算候選斷點的相對重要性，并以之作為選擇斷點的啟發(fā)式依據(jù)。

1.2 基于信息熵的離散化算法

這類算法通過計算信息熵值來判斷斷點的重要性，不同的算法對信息熵概念的定義不同。典型的定義斷點信息熵的方式有兩類。

一類［4-6］是給定屬性a∈C上斷點q，q將U劃分為2個子集（Pj是S中決策值為j的樣本的概率分布，r（d）為S的決策種類總數(shù)）分別計算E（S1）和E（S2），于是q的熵為

另一類［7-11］方法計算斷點信息熵的思路與第一類相似，但不是考慮整個樣本空間，而是僅考慮斷點兩側(cè)屬性值區(qū)間內(nèi)的樣本分布。這類方法的計算結(jié)果通常用于刪除最次要的候選斷點，合并其兩側(cè)的屬性值區(qū)間。

2 兩類離散化算法性能的實驗研究

為了分析比較兩類離散化方法的性能，我們進行了一系列仿真實驗研究，從UCI機器學習數(shù)據(jù)庫①http://www.fmt.vein.hu/softcomp/ucidata/dataset/中選取典型的連續(xù)型數(shù)據(jù)集，測試比較典型離散化算法的性能。實驗環(huán)境為:Intel（R）Pentium（R）Dual E2180@2.00 GHz 2.00 GHz，960 MB 的內(nèi)存。實驗所用數(shù)據(jù)集特征如表1和表2所示。

表1 測試數(shù)據(jù)集的特征Tab.1 Character of Database for test

表1中，No為數(shù)據(jù)集所對應(yīng)的序號，Name為數(shù)據(jù)集的名字，NI為數(shù)據(jù)集的實例數(shù)，NC為數(shù)據(jù)集的決策屬性數(shù)。

基于輔助矩陣類算法中我們選擇改進的貪心算法 1［12］、列先行后法［13］、行先列后法［13］、改進貪心算法 1 進一步完善算法［14］、二進制矩陣變換［15］5 種方法（分別對應(yīng)M1-M5）;基于信息熵類算法中選擇斷點信息熵［16］、啟發(fā)式信息熵［5］、區(qū)間類信息熵［7］、區(qū)間距離信息熵［10］、EADC［9］5 種方法（分別對應(yīng)E1-E5）。每組數(shù)據(jù)集采用5折交叉法進行實驗，訓練樣本經(jīng)不同的離散化算法處理之后，再進行屬性約簡和值約簡，得到分類規(guī)則，最后分別用得到的分類規(guī)則對測試樣本進行測試。其中，屬性約簡和值約簡均采用現(xiàn)成的算法，我們嘗試過多種算法組合，均得到了完全相似的結(jié)果。表2—6給出了實驗結(jié)果，其對應(yīng)的屬性約簡算法是信息熵屬性約簡，值約簡算法是歸納值約簡［17］。

表2 5種基于輔助矩陣的離散化算法結(jié)果的簡潔性與運行時間比較Tab.2 Concision comparisons of discretized Results by different algorithms of the first kind

表3 5種基于輔助矩陣的離散化算法的識別結(jié)果比較Tab.3 Learning accuracy comparison of different algorithms in the first kind

表4 5種基于信息熵的離散化算法結(jié)果的簡潔性與運行時間比較Tab.4 Concision comparisons of discretized Results by different algorithms of the second kind

表5 5種基于信息熵的離散化算法的識別結(jié)果比較Tab.5 Learning accuracy comparison of different algorithms in the second kind

表6 兩類離散化算法斷點選取個數(shù)、屬性約簡剩余列數(shù)、運行時間、識別精度的比較Tab.6 Comparisons of discretized Results by different algorithms of the two classes

2.1 基于輔助矩陣離散化算法結(jié)果分析

由表2和表3可以看出，對于同一個數(shù)據(jù)集:

1）5 種基于輔助矩陣的離散化方法在斷點選取、屬性約簡剩余個數(shù)、識別率方面都大致相同;

2）在運行時間方面，前4種算法的運行時間大致相同，而第5種算法的運行時間顯著延長。

對一個給定的數(shù)據(jù)集，這類方法都是依據(jù)同一個輔助矩陣來選擇斷點，只是衡量列和行特征的先后順序和統(tǒng)計方法不同，相互之間不存在本質(zhì)性的差異，所以算法的性能大致相當，其中，第5種算法在計算結(jié)果斷點子集之前，需要先對輔助矩陣進行變換，因而增加了時間開銷，使算法運行時間顯著延長。

2.2 基于信息熵的離散化算法結(jié)果分析

由表4和表5可以看出:即使是對于同一個數(shù)據(jù)集，5種基于信息熵的離散化方法在斷點選取、屬性約簡剩余個數(shù)、運行時間、識別率方面差別都很大。該類方法雖然都是基于一個信息熵的概念，但是衡量標準有很大不同，一類是以計算斷點的信息熵為準，一類是以計算區(qū)間的信息熵為準（選擇閾值），而且計算公式和閾值的選擇各異。該類方法與數(shù)據(jù)的分布有很大關(guān)系，比如對于方法E3（或E4），適合一個數(shù)據(jù)集的閾值在處理另一個數(shù)據(jù)集時效果往往不好（E4對于數(shù)據(jù)集8的處理結(jié)果）。

2.3 兩類離散化算法的比較分析

對基于輔助矩陣類算法中的5種方法結(jié)果求平均值，對基于信息熵類的離散化方法結(jié)果做相同處理，然后針對所有的數(shù)據(jù)集求取平均值（見表6最后一列）。由表6可看出:從平均值結(jié)果來看，在絕大多數(shù)情況下，信息熵類算法所選取的斷點要多于輔助矩陣類算法;信息熵類算法能夠約簡相對較多點的屬性，其計算時間要遠短于輔助矩陣類算法;依據(jù)本實驗結(jié)果，兩類算法相比，輔助矩陣類算法具有更高的樣本識別能力，兩類算法在正確識別率方面結(jié)果大致相同。

為了對結(jié)論加以驗證，在原有離散化結(jié)果的基礎(chǔ)上又采用了MIBARK屬性約簡和一般值約簡進行實驗，統(tǒng)計實驗結(jié)果，方法同上（見表7最后一列）。從表7可以看出，實驗結(jié)果對上述結(jié)論得到了很好地支持。

表7 兩類離散化算法屬性約簡剩余列數(shù)、運行時間、識別精度的比較Tab.7 Comparisons of discretized Results by different algorithms of the two classes

3 結(jié)束語

本文中我們對基于輔助矩陣和基于信息熵的兩類離散化方法進行了說明，分析它們的特征且對兩類算法中幾種比較典型的方法分別進行實驗，對實驗結(jié)果求平均值進行比較。結(jié)果表明:輔助矩陣類方法能得到較少的斷點、識別率高，但因其空間復(fù)雜度和時間復(fù)雜度都較大，適合于處理小容量數(shù)據(jù)集;信息熵類算法的識別率雖低于輔助矩陣類算法，但是在正確識別率方面有一定優(yōu)勢且計算時間短，在樣本分布均勻和閾值選擇合適的情況下該類方法適合于處理較大容量數(shù)據(jù)集。所以如何提高信息熵類算法的識別率成為今后有待研究的課題。

［1］PIOTR Blajdo，JERZY W Grzymala-Busse，ZDZISLAW SHippe，et al.A comparison of six approaches to discretiz-ation—A rough set perspective［C］//WANG guoyin，LI Tianrui，JERZY W Grzymala-Busse，et al.RSKT'08 Proceedings of the 3rd international conference on Rough sets and knowledge technology，Beijing:Springer-Verlag，2008:31-38.

［2］ FOMINA Marina，KULIKOV Alexey，VAGIN Vadim.The development of the generalization algorithm based on the rough set theory［J］.Information Theories ＆ Applications，2006，13（3）:255-262.

［3］DAI Jian-hua，LI Yuan-xiang.Study on discretization based on rough set theory［C］//Proceedings of the First International Conference on Machine Learning and Cyberntics，Beijing:［s.n.］，2002，1371-1373.

［4］白銀柱，裴志利，王建.基于粗集理論和信息熵的屬性離散化方法［J］.計算機應(yīng)用研究，2008，25（6）:1701-1703.

BAIYin-zhu，PEIZhi-li，WANG Jian.Discreti-zation algorithm ofattributes based on the rough set theory and information entropy［J］.Computer application and research，2008，25（6）:1701-1703.

［5］李春貴，王萌，原慶能.基于啟發(fā)式信息熵的粗集數(shù)值屬性離散化算法［J］.廣西科學院學報，2007，23（4）:235-237.

LIChun-gui，WANG Meng，YUAN Qing-neng.Disc-retization algorithm of attributes based on the rough set theory and heuristic information entropy［J］.Guangxi academy of sciences ，2007，23（4）:235-237.

［6］沈永紅，王發(fā)興.基于信息熵的粗集屬性離散化方法及應(yīng)用［J］.計算機工程與應(yīng)用，2008，44（5）:221-224.

SHEN Yong-hong，WANG Fa-xing.Discretization algorithm of attributes based on the rough set theory and information entropy［J］.Computer engineering and application，2008，44（5）:221-224.

［7］闕夏，胡學鋼，張玉紅.基于區(qū)間類信息熵的連續(xù)屬性離散化［J］.計算機技術(shù)與應(yīng)用進展，2006，236-239.

QUE Xia，HU Xue-gang，ZHANG Yu-hong.Discret-ization algorithm of Continuous attributes based on the rough set theory and interval class information entropy［J］.Computer techn-ology and application progress，2006，236-239.

［8］張葛祥，金煒東，胡來招.粗集理論中連續(xù)屬性的廣義離散化［J］.控制與決策，2005，20（4）:372-376.

ZHANG Ge-xiang，JINWei-dong，HU Lai-zhao.The generalized discretization algorithm of Continuous attributes based on the rough set theory［J］.Control and decision，2005，20（4）:372-376.

［9］賀躍，鄭建軍，朱蕾.一種基于熵的連續(xù)屬性離散化算法［J］.計算機應(yīng)用，2005，25（3）:637-639.

HE Yue，ZHENG Jian-jun，ZHU Lei.Discretizat-ion algorithm of Continuous attributees based on entropy.Computer application，2005，25（3）:637-639.

［10］徐如燕，魯漢榕，郭齊勝.基于信息論的連續(xù)屬性離散化［J］.空軍雷達學院學報，2001，15（2）:20-23.

XU Ru-yan，LUHan-rong，GUOQi-sheng.Discreti-zation algorithm of Continuous attributes based on information theory［J］.The air force radars of journals，2001，15（2）:20-23.

［11］王國胤，劉靜，胡峰.基于斷點辨別力的粗糙集離散化算法［J］.重慶郵電大學學報:自然科學版，2009，21（3）:388-392.

WANG Guo-yin，LIU Jing，HU Feng.Discretiza-tion algorithm of Continuous attributes based on Breakpoint discrimination and rough set theory［J］.Cqupt journal，2009，21（3）:388-392.

［12］侯利娟，王國胤，聶能，等.粗集理論中的離散化問題［J］.計算機科學，2000，27（12）:89-94.

HOU Li-juan，WANG Guo-yin，NIE Neng，et al.Discretization question based on rough set theor-y［J］.Computer science，2000，27（12）:89-94.

［13］趙軍，王國胤，吳中福，等.基于粗集理論的數(shù)據(jù)離散化新算法［J］.重慶大學學報，2002，25（3）:18-21.

ZHAO Jun，WANG Guo-yin，WU Zhong-fu，et al.New method of data discretization based on rough set theory［J］.Chongqing university journal，2002，25（3）:18-21.

［14］高赟，侯媛彬.改進貪心算法的完善與應(yīng)用［J］.儀器儀表學報，2004，25（4）:727-729.

GAO Bin，HOU Yuan-bin.Perfection and application of improved greedy algorithm［J］.Instrumentation journal，2004，25（4）:727-729.

［15］侯利娟，顏宏文.基于二進制可辨識矩陣變換的離散化算法［J］.計算機工程與設(shè)計，2008，29（9）:2330-2332.

HOU Li-juan，YAN Hong-wen.Discretization algorithm based on Binary discernibility matrix transformation［J］.The computer engineering and design，2008，29（9）:2330-2332.

［16］謝宏，程浩忠，牛東曉.基于信息熵的粗集連續(xù)屬性離散化算法［J］.計算機學報，2005，28（9）:1570-1574.

XIE Hong，CHENG Hao-zhong，NIU Dong-xiao.Discretization algorithm of Continuous attributes based on the rough set theory and information entropy［J］.Computer Journal，2005，28（9）:1570-1574.

［17］王國胤.Rough集理論與知識獲?。跰］.西安:西安交通大學出版社，2001.

WANG Guo-yin.Rough set theory and Knowledge acquisition［M］.Xi'an Jiaotong University Press，2001.