孫英慧，孫英娟，蒲東兵，姜 艷

（1.吉林師范大學計算機學院，吉林 四平 136000；

2.長春師范學院計算機科學與技術學院，吉林 長春 130032；

3.東北師范大學計算機科學與信息技術學院，吉林 長春 130117）

一種基于連續(xù)屬性離散化的知識分類方法

孫英慧1，孫英娟2，蒲東兵3，姜 艷2

（1.吉林師范大學計算機學院，吉林 四平 136000；

2.長春師范學院計算機科學與技術學院，吉林 長春 130032；

3.東北師范大學計算機科學與信息技術學院，吉林 長春 130117）

提出一種基于連續(xù)屬性離散化的知識分類方法.將條件屬性按照重要度由高到低排序，并依照此排序?qū)Q策表中各條件屬性依次離散化.在對決策表中條件屬性的離散化過程中充分考慮已離散化的條件屬性及決策屬性，離散后的決策表不需要進一步約簡.使用了模擬數(shù)據(jù)和UCI機器學習數(shù)據(jù)集中的數(shù)據(jù)進行算法測試，而且與其他離散化算法進行了對比，結果充分證明了新方法的有效性.

粗糙集；離散化；屬性重要度；區(qū)間劃分；斷點

粗糙集是一種主要用于分析具有不確定性數(shù)據(jù)的數(shù)學理論，被廣泛應用于模式識別、機器學習、數(shù)據(jù)挖掘、知識獲取、知識發(fā)現(xiàn)等研究［1－2］.粗糙集只能對離散化的數(shù)據(jù)進行處理，因此連續(xù)屬性的離散化非常關鍵.目前關于數(shù)據(jù)的離散化方法有很多，如等距或等頻法［3］、基于統(tǒng)計的方法［4－5］、基于屬性重要度的方法［6］、基于計算智能的方法［7－10］等.其中等距或等頻法應用起來很方便，但是可能導致離散點過多，丟失信息.基于屬性重要度的方法和基于計算智能的方法是應用比較廣泛的方法.本文提出的連續(xù)屬性離散化方法，在充分考慮屬性重要度的同時，也考慮決策分類，離散后的決策表不需要約簡.與其他算法相比，具有極高的識別率、最低的誤識率和拒識率，產(chǎn)生盡可能少的斷點，生成最少、最優(yōu)的規(guī)則集.

1 離散化相關概念

1.1 離散化描述

具有條件屬性和決策屬性的知識表達系統(tǒng)S＝（U，A，｛Va｝，f）稱為決策表.對于?x∈U，有序列C（c1（x），…，cn（x）），D（d1（x），…，dm（x）），其中U為非空有限集，稱為域；A為非空有限集，稱為屬性集合；Va為屬性a∈A的值域；f：U→Va為一單射，使論域U中任一元素取屬性a在Va中的某一唯一值；A＝C∪D，C∩D＝?；｛c1（x），…，cn（x）｝稱為條件屬性集，｛d1（x），…，dm（x）｝稱為決策屬性集，決策規(guī)則可以表示為c1（x），…，cn（x）→d1（x），…，dm（x）.在值域Va＝［la，ra］上的任意一個斷點集合｛（a，ca1），（a，ca2），…，（a，cak）｝定義Va上的一個分類Pa：

若某一條件屬性的值域被劃分為n個區(qū)間，每一個斷點即是一個區(qū)間端點，斷點數(shù)應為n－1.離散化實質(zhì)上即是利用選取的斷點來對條件屬性的值域進行劃分，每一劃分區(qū)間對應一個離散值，一般為一個整數(shù).這樣原有屬性中同屬于一個劃分區(qū)間的各屬性值合并為一個，用同一離散值代替.因而，離散化過程即是選取斷點的過程.

1.2 屬性重要度

在決策表中，條件屬性與決策屬性之間的關聯(lián)程度反映了條件屬性的重要性.因此，條件屬性a取得某個屬性值Va時，決策屬性的可能值數(shù)目就反映了條件屬性相對于對決策屬性的重要性.如果條件屬性a取得某個屬性值Va時，決策屬性的可能值數(shù)目唯一，則說明該條件屬性值能夠唯一確定該決策屬性，因此在規(guī)則生成時，當條件屬性取該值時不需要考慮其他條件屬性.

從定義可以看出，在一個決策系統(tǒng)中，Ma的值越大，說明a屬性的決策能力越強.

2 基于決策屬性的連續(xù)屬性離散化算法

2.1 算法的主要思想

決策表中的每條記錄就是一條決策規(guī)則，訓練樣本數(shù)據(jù)并沒有廣泛的決策意義.通過屬性離散化能將各樣本之間的共同點找到，得出有意義的決策規(guī)則［10］.在本文算法中，首先運用C-mean方法將原決策系統(tǒng)中的各連續(xù)屬性離散化，然后計算決策表中各條件屬性的重要度，并將其按重要度由高到低排序.重要度最高的屬性保留C-mean方法的離散化結果，其他屬性根據(jù)重要度排序，依次離散化.離散化過程中充分考慮已離散化的各屬性及決策屬性，所有的連續(xù)屬性離散化后得到新的決策系統(tǒng).最后去除新的決策系統(tǒng)中的矛盾規(guī)則，以保證系統(tǒng)的識別準確率.

2.2 算法描述

在一個決策系統(tǒng)中，決策規(guī)則通常與重要度高的條件屬性相關性更高，即重要度高的屬性決策能力更強.算法描述如下：

算法：一種基于連續(xù)屬性離散化的知識分類方法.輸入：訓練樣本集D.

輸出：決策規(guī)則表Snew.

令：S＝（U，A，｛Va｝，f），條件屬性數(shù)目為n，決策屬性集為｛d｝，S′和Snew與S具有相同結構，初始值為空.

（1）將樣本集D預處理后，輸入決策系統(tǒng)S.

（2）S′＝S，i＝1.

（3）將S′的各條件屬性用FCM聚類方法離散化，令聚類中心數(shù)為k（決策分類數(shù)）.

（4）計算S′中各屬性的重要度，并按照屬性重要度由高到低排序各條件屬性，令各條件屬性排序為C1，C2，…，Cn.

（5）將S′的C1屬性列賦值給Snew.

（6）i＝i＋1.

（7）判斷Snew中條件屬性取值相同的各行，決策屬性值是否相同.分別執(zhí)行（a）或（b）.

（a）若條件屬性值相同時，決策屬性值唯一，則取該條件屬性值的各行其余連續(xù)屬性不再需要離散化，如果Snew中所有的條件屬性都無需離散化或者i＞n，則轉(zhuǎn)至（9）；

（b）否則，將Snew中條件屬性值相同的各行劃分為一組.組內(nèi)計算取得每一個決策值時，S中對應的i劃分區(qū)間，求各劃分區(qū)間的并（若劃分區(qū)間有交集，則增加斷點）.將各組的劃分區(qū)間進行歸并，最后生成i條件屬性的劃分區(qū)間，離散化i屬性，將離散化結果添加到Snew.

（8）i≤n轉(zhuǎn)至（6）.

（9）生成規(guī)則集，即將Snew中沖突行重新離散化，最后去除Snew中重復行.

2.3 區(qū)間劃分

離散化即是對屬性區(qū)間的劃分，如果區(qū)間劃分過細，就會導致分類規(guī)則過細，決策規(guī)則增加；相反，如果區(qū)間劃分過粗就會導致分類不清，出現(xiàn)矛盾規(guī)則.本文提出兩個概念：已劃分區(qū)間和空閑區(qū)間.

定義2 在數(shù)軸上，已經(jīng)有屬性取值劃分的區(qū)間稱之為已劃分區(qū)間.

定義3 在數(shù)軸上，沒有屬性取值的區(qū)間稱之為空閑區(qū)間.

2.3.1 組內(nèi)劃分區(qū)間

若條件屬性值相同時，決策屬性值唯一，則取該條件屬性值的各行其余連續(xù)屬性不再需要離散化，否則，將Snew中條件屬性值相同的各行劃分為一組.因此在Snew中同一組的各行條件屬性取值相同，而決策屬性值并不完全相同，即存在不一致數(shù)據(jù).令第x小組內(nèi)決策屬性種類為Numdx，則其對S中i的劃分區(qū)間至少為Numdx個，若劃分區(qū)間存在交集，增加一個劃分區(qū)間.兩個劃分區(qū)間a，b的相交情況只有如下兩種情況：此時原有區(qū)間劃分轉(zhuǎn)變?yōu)閍′，b′，c′.如圖1所示.

圖1 組內(nèi)區(qū)間劃分

2.3.2 各組劃分區(qū)間歸并

令數(shù)軸O存放i的最后區(qū)間劃分，初始值為空閑區(qū)間.首先用第一小組的區(qū)間劃分劃分O.然后依次將第二小組的區(qū)間劃分與O歸并，……直到所有小組的區(qū)間劃分與O歸并.因為各小組間不存在不一致數(shù)據(jù)，因此，各小組劃分區(qū)間與O進行歸并時，在不導致數(shù)據(jù)產(chǎn)生不一致的前提下盡量不增加O的區(qū)間劃分.每一個小組執(zhí)行與O歸并前，將O各區(qū)間的更新標志清空.第x小組的區(qū)間劃分，與O歸并的方法為：由小到大依次取x的劃分區(qū)間x1，x2，…，與O歸并，xi（?xi，1，xi，2））區(qū)間與Oj及Oj－1區(qū)間之間的關系有如圖2所示的4種情形.

（a）如果Oj－1為未更新，將Oj－1設置為已更新；否則，將xi，1作為Oj－1的新斷點，將Oj－1劃分為左、右兩個區(qū)間，并將右區(qū)間設置為已更新.

（b）將Oj－1的右端點移至xi，2，如果Oj－1為已更新，則將xi，1作為一個新斷點，將Oj－1劃分為左、右兩個區(qū)間.

（c）如果Oj－1為未更新，則將Oj－1的右端點移至xi，2；否則，將Oj的左端點移至xi，1，并將Oj標志為已更新.

（d）將Oj的左端點移至xi，1，若xi右端點落在O的劃分區(qū)間，則將該劃分區(qū)間設置為更新.

圖2 屬性區(qū)間劃分

2.3.3 去除沖突規(guī)則

找到Snew中有沖突的兩行記錄，按照屬性重要度，依次比較原決策系統(tǒng)中對應的屬性值，找到兩行記錄首次出現(xiàn)不同的屬性值.獲得該屬性的新斷點D（取兩條記錄對應屬性值的均值）.令Snew中該屬性的斷點序列為D1＜…＜Di－1＜Di＜…，Di－1＜D＜Di，如果原決策表S中沒有記錄屬性取值在［Di－1，D）區(qū)間，并且更新斷點后不會產(chǎn)生新沖突行，則將Snew中Di－1斷點變更為D；否則如果決策表S中沒有記錄屬性取值在［D，Di）區(qū)間，并且更新斷點后不會產(chǎn)生新沖突行，則將Snew中Di斷點變更為D.如果前面所述條件都不能滿足，則將D作為該屬性的一個新斷點.按照該方法，將所有沖突行的相應屬性重新離散化.運用更新后的斷點集去重新離散S，得到Snew.

3 算例

3.1 模擬數(shù)據(jù)

本文選取來自文獻［11］的決策表，并將本文算法與貪心算法、屬性重要性離散化算法和遺傳算法進行比較［10－11］，離散化結果如表1所示，斷點結果如表2所示.從表1和表2可以看到，本文所提出的連續(xù)屬性離散化方法只有3個斷點，與遺傳算法和屬性重要性離散化算法的斷點數(shù)相同，優(yōu)于貪心算法，獲得了最少的斷點集.屬性重要度排序為a，b；重要度分別為0.75和0.5.

表1 不同算法離散化結果對比

表2 不同算法的離散化斷點結果

3.2 UCI數(shù)據(jù)

為了驗證算法的可行性和有效性，采用UCI機器學習標準數(shù)據(jù)集中的數(shù)據(jù)作為測試數(shù)據(jù)［12］.數(shù)據(jù)集的特征如表3所示.

表3 實驗數(shù)據(jù)集

按訓練集與測試集分別占60%及40%，獨立運行100次，求得分類精度的平均值.與文獻［12］中表5的各算法進行比較，結果如表4所示.其中：AEFD為文獻［12］提出的一種近似等頻離散化方法；A2為基于混合概率模型的無監(jiān)督離散化算法；MDL為有監(jiān)督離散化方法Fayyad＆Irani的MDL方法.

實驗結果表明，本文提出的基于連續(xù)屬性離散化的知識分類方法，在4個數(shù)據(jù)集上的識別精度都高于其他三種算法，而對Breast數(shù)據(jù)集的分類識別率更是達到99%以上，實驗效果非常好.

表4 識別精度比較%

4 結論

本文提出一種基于連續(xù)屬性離散化的知識分類方法.通過屬性重要度確定屬性離散化次序，離散化過程中始終以決策分類為核心，充分考慮已經(jīng)離散化的條件屬性.從表1可以看出，本文提出算法的斷點數(shù)明顯低于文獻［11］提出的貪心算法，與文獻［10］提出的遺傳算法和屬性重要性離散化算法的斷點數(shù)相同.從表4可以看出，算法在UCI的4個數(shù)據(jù)集（Breast，Diabetes，Glass，Iris）上運行所得的分類精度遠高于文獻［12］中表5的各分類算法.綜合以上實驗結果，可以看出：使用本文算法，條件屬性離散后產(chǎn)生的斷點數(shù)少，能夠更好地抓住樣本共性，從而分類精度更高.

［1］ 李永敏，朱善君，陳湘暉，等.基于粗糙集理論的數(shù)據(jù)挖掘模型［J］.清華大學學報：自然科學版，1999，39（1）：110-113.

［2］ PAWLAK Z.Rough sets［J］.International Journal of Information and Computer Science，1982，11（5）：341-356.

［3］ 蔣盛益，李霞，鄭琪.一種近似等頻離散化方法［J］.暨南大學學報：自然科學版，2009，30（1）：31-34.

［4］ MEHMET ACI，CIGDEM INAN，MUTLU AVCI.A hybrid classification method of k nearest neighbor，Bayesian methods and genetic algorithm ［J］.Expert Systems with Applications，2010，37：5061-5067.

［5］ 劉豐年，黃景濤.基于分布率的連續(xù)屬性二次離散化算法［J］.微電子學與計算機，2009，26（1）：177-179.

［6］ 白根柱，裴志利，王建，等.基于粗糙集理論和信息熵的屬性離散化方法［J］.計算機應用研究，2008，25（6）：1701-1703.

［7］ 王飛，劉大有，薛萬欣.基于遺傳算法的Bayesian網(wǎng)中連續(xù)變量離散化的研究［J］.計算機學報，2002，25（8）：794-800.

［8］ 劉德玲，馬志強.基于多群體遺傳算法的非線性最小二乘估計［J］.東北師大學報：自然科學版，2011，43（1）：40-47.

［9］ YOON-SEOK CHOI，BYUNG-RO MOON，SANG YONG SEO.Genetic fuzzy discretization with adaptiv ntervals for classification problems［C］／／GECCO.Proceedings of the genetic and Evolutionary Computatin Conference，Wahington，DC，2005：2037-2043.

［10］ 陳果.基于遺傳算法的決策表連續(xù)屬性離散化方法［J］.儀器儀表學報，2007，28（9）：1700-1705.

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

［12］ 蔣盛益，李霞，鄭琪.一種近似等頻離散化方法［J］.暨南大學學報：自然科學版，2009，30（1）：31-34.

One method of classification based on discretization of continuous attributes

SUN Ying-hui1，SUN Ying－juan2，Pu Dong-bing3，JIANG Yan2

（1.College of Computer，Jilin Normal University，Siping 136000，China；
2.College of Computer Science and Technology，Changchun Normal University，Changchun 130032，China；
3.College of Computer Science and Information Technology，Northeast Normal University，Changchun 130117，China）

This paper gives a new method of classification based on discretization of continuous attributes.Firstly condition attributes are sorted in descending order by their significance，and then each condition attribute in the decision table is discretized in sequence by the order.Both discretized condition attributes and decision attributes are paid more attention during the course of discretization.And the discretized decision table needs not to be reduced further.Finally，the simulation data and the UCI machine learning data are used to verify the new method，and the new method is compared with other discretization algorithms.The results fully show the correctness and effectiveness of the proposed method of classification based on discretization of continuous attributes.

rough set；discretization；significance of attributes；region division；breakpoint

TP 18

520·20

A

1000-1832（2012）01-0045-05

2011-05-11

國家自然科學基金資助項目（60673099，60873146）；吉林省科技發(fā)展計劃項目（201105056）；吉林省教育廳科技計劃基

金資助項目（2007172，2010383）；長春師范學院校內(nèi)青年基金資助項目（010，012）.

孫英慧（1975—），女，碩士，講師，主要從事數(shù)據(jù)挖掘、人工智能研究；通訊作者：蒲東兵（1970—），男，博士，副教授，主要從事嵌入式、模式識別、人工智能研究.

陶 理）