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

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

（1.吉林師范大學(xué)計(jì)算機(jī)學(xué)院，吉林 四平 136000；

2.長春師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130032；

3.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長春 130117）

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

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

（1.吉林師范大學(xué)計(jì)算機(jī)學(xué)院，吉林 四平 136000；

2.長春師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130032；

3.東北師范大學(xué)計(jì)算機(jī)科學(xué)與信息技術(shù)學(xué)院，吉林 長春 130117）

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

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

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

1 離散化相關(guān)概念

1.1 離散化描述

具有條件屬性和決策屬性的知識(shí)表達(dá)系統(tǒng)S＝（U，A，｛Va｝，f）稱為決策表.對(duì)于?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］上的任意一個(gè)斷點(diǎn)集合｛（a，ca1），（a，ca2），…，（a，cak）｝定義Va上的一個(gè)分類Pa：

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

1.2 屬性重要度

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

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

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

2.1 算法的主要思想

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

2.2 算法描述

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

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

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

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

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

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

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

（4）計(jì)算S′中各屬性的重要度，并按照屬性重要度由高到低排序各條件屬性，令各條件屬性排序?yàn)镃1，C2，…，Cn.

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

（6）i＝i＋1.

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

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

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

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

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

2.3 區(qū)間劃分

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

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

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

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

若條件屬性值相同時(shí)，決策屬性值唯一，則取該條件屬性值的各行其余連續(xù)屬性不再需要離散化，否則，將Snew中條件屬性值相同的各行劃分為一組.因此在Snew中同一組的各行條件屬性取值相同，而決策屬性值并不完全相同，即存在不一致數(shù)據(jù).令第x小組內(nèi)決策屬性種類為Numdx，則其對(duì)S中i的劃分區(qū)間至少為Numdx個(gè)，若劃分區(qū)間存在交集，增加一個(gè)劃分區(qū)間.兩個(gè)劃分區(qū)間a，b的相交情況只有如下兩種情況：此時(shí)原有區(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歸并.因?yàn)楦餍〗M間不存在不一致數(shù)據(jù)，因此，各小組劃分區(qū)間與O進(jìn)行歸并時(shí)，在不導(dǎo)致數(shù)據(jù)產(chǎn)生不一致的前提下盡量不增加O的區(qū)間劃分.每一個(gè)小組執(zhí)行與O歸并前，將O各區(qū)間的更新標(biāo)志清空.第x小組的區(qū)間劃分，與O歸并的方法為：由小到大依次取x的劃分區(qū)間x1，x2，…，與O歸并，xi（?xi，1，xi，2））區(qū)間與Oj及Oj－1區(qū)間之間的關(guān)系有如圖2所示的4種情形.

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

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

（c）如果Oj－1為未更新，則將Oj－1的右端點(diǎn)移至xi，2；否則，將Oj的左端點(diǎn)移至xi，1，并將Oj標(biāo)志為已更新.

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

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

2.3.3 去除沖突規(guī)則

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

3 算例

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

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

表1 不同算法離散化結(jié)果對(duì)比

表2 不同算法的離散化斷點(diǎn)結(jié)果

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

為了驗(yàn)證算法的可行性和有效性，采用UCI機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)數(shù)據(jù)集中的數(shù)據(jù)作為測試數(shù)據(jù)［12］.數(shù)據(jù)集的特征如表3所示.

表3 實(shí)驗(yàn)數(shù)據(jù)集

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

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

表4 識(shí)別精度比較%

4 結(jié)論

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

［1］ 李永敏，朱善君，陳湘暉，等.基于粗糙集理論的數(shù)據(jù)挖掘模型［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，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］.暨南大學(xué)學(xué)報(bào)：自然科學(xué)版，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］.微電子學(xué)與計(jì)算機(jī)，2009，26（1）：177-179.

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

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

［8］ 劉德玲，馬志強(qiáng).基于多群體遺傳算法的非線性最小二乘估計(jì)［J］.東北師大學(xué)報(bào)：自然科學(xué)版，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］.儀器儀表學(xué)報(bào)，2007，28（9）：1700-1705.

［11］ 王國胤.Rough集理論與知識(shí)獲取［M］.西安：西安交通大學(xué)出版社，2001：24-105.

［12］ 蔣盛益，李霞，鄭琪.一種近似等頻離散化方法［J］.暨南大學(xué)學(xué)報(bào)：自然科學(xué)版，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

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

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

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

陶 理）