吳學(xué)輝

(運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山西 運(yùn)城 044000)

基于粗糙集的決策樹(shù)在產(chǎn)品缺陷檢測(cè)中的應(yīng)用

吳學(xué)輝

(運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山西 運(yùn)城 044000)

將數(shù)據(jù)挖掘中的決策樹(shù)與粗糙集理論進(jìn)行了有機(jī)結(jié)合,提出了一種基于粗糙集技術(shù)的決策樹(shù)構(gòu)造算法,并將該算法應(yīng)用于膠合板缺陷檢測(cè)．通過(guò)粗糙集屬性約簡(jiǎn),找出造成膠合板缺陷的關(guān)鍵因素;再基于約簡(jiǎn)后的決策表,使用該決策樹(shù)算法構(gòu)建決策樹(shù),從而提取分類規(guī)則,指導(dǎo)決策過(guò)程．通過(guò)實(shí)驗(yàn)驗(yàn)證了,該算法可以有效對(duì)膠合板的缺陷進(jìn)行檢測(cè)．

粗糙集;決策樹(shù);屬性約簡(jiǎn)

0 引言

當(dāng)前,數(shù)據(jù)挖掘技術(shù)在許多領(lǐng)域得到廣泛應(yīng)用,如教育、零售業(yè)、醫(yī)療、保險(xiǎn)、股票等．它可以從各行業(yè)積累的大量數(shù)據(jù)中發(fā)現(xiàn)隱藏的知識(shí)．?dāng)?shù)據(jù)挖掘中的決策樹(shù)技術(shù)可以對(duì)數(shù)據(jù)進(jìn)行分類,提取有用規(guī)則．粗糙集作為處理不完備信息的有效工具,已經(jīng)廣泛應(yīng)用于知識(shí)發(fā)現(xiàn)、問(wèn)題求解等領(lǐng)域[1，2]．粗糙集屬性約簡(jiǎn)通過(guò)刪除不相關(guān)或不重要的屬性,簡(jiǎn)化原有系統(tǒng)．通過(guò)它可以對(duì)決策樹(shù)分類屬性進(jìn)行約簡(jiǎn),從而使構(gòu)造的決策樹(shù)模型簡(jiǎn)單,預(yù)測(cè)分類精度更高．

在膠合板生產(chǎn)過(guò)程中,膠合板在生產(chǎn)線上以2～3 m/s的速度運(yùn)行,人工檢測(cè)的時(shí)間非常短,大約只有1～2 s,更主要的是這種單調(diào)重復(fù)的工作容易引起工人的誤分類,相關(guān)實(shí)驗(yàn)表明人工檢測(cè)缺陷的準(zhǔn)確率只有68%．為了減輕工人的檢測(cè)負(fù)擔(dān),提高檢測(cè)缺陷的準(zhǔn)確率,采用自動(dòng)檢測(cè)系統(tǒng)是非常必要的．自動(dòng)檢測(cè)系統(tǒng)得到大量數(shù)據(jù),如何對(duì)這些大量數(shù)據(jù)進(jìn)行分類是檢測(cè)面臨的最大問(wèn)題．本文將基于粗糙集的決策樹(shù)算法應(yīng)用于膠合板缺陷檢測(cè)分類．利用粗糙集屬性約簡(jiǎn)確定最簡(jiǎn)決策表,最后通過(guò)決策樹(shù)方法提取規(guī)則,指導(dǎo)決策過(guò)程．

1 基本概念

1.1粗糙集理論

粗糙集理論是由波蘭教授Pawlak Z提出的一種數(shù)據(jù)挖掘新方法．它是當(dāng)前處理不完全和不精確信息的一種有效工具,已經(jīng)廣泛應(yīng)用于知識(shí)發(fā)現(xiàn)、模式識(shí)別、專家系統(tǒng)以及不確定推理等領(lǐng)域[3，4]．本文研究中所涉及的粗糙集相關(guān)理論如下:

定義 1一個(gè)信息系統(tǒng)S可表示為:S=〈U,R,V,f〉．其中:

1)U為對(duì)象的集合．

2)R=C∪D,C為條件屬性集合,D為決策屬性集合．

4)f:U×R→V是一個(gè)信息函數(shù)．

[x]R?X}

定義 4(屬性核)P和Q是論域U上的兩個(gè)等價(jià)關(guān)系簇,如果Q?P獨(dú)立,并且IND(P)=IND(Q),則稱Q是P的約簡(jiǎn),在每個(gè)約簡(jiǎn)中都不可缺的關(guān)系集合稱為核,記為COREQ(P)．其中COREQ(P)=∩REDQ(P),P的所有Q約簡(jiǎn)關(guān)系簇為REDQ(P)．

1.2決策樹(shù)算法

決策樹(shù)作為一種分類方法,已經(jīng)在許多領(lǐng)域得到廣泛應(yīng)用．它是一種基于知識(shí)表示的樹(shù),用于表示分類規(guī)則．葉節(jié)點(diǎn)代表類標(biāo)號(hào),而其他節(jié)點(diǎn)代表與被分類對(duì)象相關(guān)聯(lián)的屬性．從決策樹(shù)的根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就是一條決策規(guī)則[5]．

ID3算法是決策樹(shù)的經(jīng)典算法,它以信息熵和信息增益度為標(biāo)準(zhǔn),對(duì)數(shù)據(jù)進(jìn)行歸納分類．信息量和熵定義如下:

信息量:information=-log2pi

熵:Entropy=-∑pilog2pi

1)數(shù)據(jù)集S劃分前的熵:

其中,pi=ni/n．因?yàn)樾畔⒁远M(jìn)制編碼,所以對(duì)數(shù)的底為2．

2)數(shù)據(jù)集S劃分后的熵:

3)數(shù)據(jù)集S劃分前后的熵差:Gain(S,A)=E(S)-E(S,A),Gain(S,A)為信息增益,用系統(tǒng)墑的減少值描述．表示系統(tǒng)由于分類獲得的信息量,Gain(S,A)是指熵的期望壓縮,其值越大,表明屬性A對(duì)分類提供的信息量越大．ID3算法的核心思想就是選擇信息增益最大的屬性作為結(jié)點(diǎn),再在每個(gè)分支中采用遞歸方法構(gòu)建決策樹(shù)．

1.3基于粗糙集的決策樹(shù)算法

決策樹(shù)進(jìn)行分類時(shí),生成的分類模型簡(jiǎn)單,精度也較高,但當(dāng)決策屬性過(guò)多時(shí),生成的分類模型復(fù)雜,而粗糙集在消除決策表冗余屬性方面有其特殊優(yōu)勢(shì)[6]．

本文將二者結(jié)合起來(lái),首先通過(guò)屬性約簡(jiǎn)去掉冗余屬性,得到屬性核,接著利用ID3算法對(duì)約簡(jiǎn)后的決策表進(jìn)行決策樹(shù)的構(gòu)建,產(chǎn)生相應(yīng)的分類規(guī)則．

基于粗糙集的決策樹(shù)算法描述如圖1所示．

該算法的基本步驟如下:

1)收集相應(yīng)的訓(xùn)練數(shù)據(jù)集,刪除重復(fù)記錄．

2)對(duì)訓(xùn)練集進(jìn)行離散化處理．

3)將離散化的數(shù)據(jù)用粗糙集屬性約簡(jiǎn)算法求出屬性核．

4)依據(jù)約簡(jiǎn)后的核屬性,篩選新的數(shù)據(jù)集.

5)對(duì)此數(shù)據(jù)集進(jìn)行決策樹(shù)的構(gòu)建,建立決策樹(shù)模型．

6)用該決策樹(shù)模型對(duì)測(cè)試數(shù)據(jù)集進(jìn)行預(yù)測(cè)分類．

2 實(shí)驗(yàn)結(jié)果與分析

2.1決策表離散化

本文抽取某企業(yè)膠合板缺陷檢測(cè)數(shù)據(jù)作為樣本數(shù)據(jù),并利用譜系聚類法[7，8]對(duì)每條記錄進(jìn)行離散化,離散化的結(jié)果如表1所示．論域U={1,2,3，…,10},條件屬性C={灰度均值,灰度中值,灰度最頻值,灰度標(biāo)準(zhǔn)差,偏度,峰度,黑像素?cái)?shù),亮像素?cái)?shù),最低灰度值,最高灰度值,直方圖黑區(qū)尾部長(zhǎng)度,直方圖白區(qū)尾部長(zhǎng)度,均值為域值的邊緣像素?cái)?shù),以μ-σ為閾值后像素?cái)?shù),特征14的邊緣像素?cái)?shù),以μ+σ為閾值后像素?cái)?shù),特征16的邊緣像素?cái)?shù)},在表中用1-17來(lái)表示．決策屬性D={檢測(cè)類型}．其值為1,2,3,4,其中,1表示樹(shù)皮缺陷,2表示無(wú)缺陷,3表示有彩色條紋,4表示有皺狀紋理．

2.2屬性約簡(jiǎn)

屬性約簡(jiǎn)常用算法有盲目法和啟發(fā)式約簡(jiǎn)算法[9，10]．前者在時(shí)間和空間上開(kāi)銷較大,因此本文采用后者對(duì)表1進(jìn)行約簡(jiǎn),最后得到的決策表如表2所示．

從約簡(jiǎn)后的結(jié)果可以看出,屬性2,3,4,8,12,14是冗余屬性,對(duì)于決策屬性是不必要的,而屬性1,5,6,7,9,10,11,13,15,17是核屬性．對(duì)決策屬性是必要的．

2.3構(gòu)建決策樹(shù)

針對(duì)表3,用ID3算法構(gòu)建決策樹(shù),過(guò)程如下:計(jì)算各個(gè)條件屬性的信息增益,Gain(11)=0.724,Gain(17)=0.701,Gain(9)=0.608,Gain(10)=0.537,Gain(15)=0.451,Gain(7)=0.449,Gain(1)=0.429,Gain(6)=0.194．條件屬性11的信息增益最大,因此將條件屬性11將作為決策樹(shù)的根節(jié)點(diǎn),當(dāng)分類屬性11為2時(shí),論域子集{2,8},由于該子集中的決策屬性為同一類,所以停止選擇屬性．當(dāng)分類屬性11為1時(shí),論域子集{1,3,4,5,6,7,9,10},由于它的決策屬性不為一類,繼續(xù)選擇屬性分類,依據(jù)ID3算法再次選擇信息增益最大的屬性17,作為決策樹(shù)的根節(jié)點(diǎn),遞歸地構(gòu)建決策樹(shù),以此類推,最終構(gòu)造的決策樹(shù)如圖2所示．

從構(gòu)造的決策樹(shù)可以看出,如果只用ID3算法則由于條件屬性有17個(gè),構(gòu)造出的決策樹(shù)很復(fù)雜,而用粗糙集屬性約簡(jiǎn)后,只有10個(gè)必要屬性,用約簡(jiǎn)后的決策表,構(gòu)造的決策樹(shù)簡(jiǎn)單,計(jì)算復(fù)雜度明顯降低．

2.4規(guī)則提取

從圖2構(gòu)造的決策樹(shù),得到以下分類規(guī)則:

1)IF直方圖黑區(qū)尾部長(zhǎng)度=“2”THEN檢測(cè)類型=“彩色條紋”．

2)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“1”AND最低灰度值=“2”THEN檢測(cè)類型=“樹(shù)皮缺陷”．

3)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“1”AND最低灰度值=“1”AND最高灰度值=“1”THEN檢測(cè)類型=“樹(shù)皮缺陷”．

4)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“1”AND最低灰度值=“1”AND最高灰度值=“3”AND特征14的邊緣像素?cái)?shù)=“1”AND黑像素?cái)?shù)=“1”THEN檢測(cè)類型=“有皺狀紋理”．

5)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“1”AND最低灰度值=“1”AND最高灰度值=“3”AND特征14的邊緣像素?cái)?shù)=“1”AND黑像素?cái)?shù)=“3”THEN檢測(cè)類型=“樹(shù)皮缺陷”．

6)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“2”AND最低灰度值=“1”THEN檢測(cè)類型=“樹(shù)皮缺陷”．

7)IF直方圖黑區(qū)尾部長(zhǎng)度=“1”AND特征16的邊緣像素?cái)?shù)=“2”AND最低灰度值=“2”THEN檢測(cè)類型=“無(wú)缺陷”．

2.5模型準(zhǔn)確性評(píng)估

數(shù)據(jù)挖掘最后一個(gè)步驟就是對(duì)模型準(zhǔn)確性評(píng)估．模型準(zhǔn)確性評(píng)估就是利用已生成的決策規(guī)則來(lái)預(yù)測(cè)未知數(shù)據(jù),判斷未知數(shù)據(jù)屬于哪一分類,再通過(guò)預(yù)測(cè)結(jié)果與實(shí)際情況吻合的比率來(lái)判斷該模型是否有效．在WEKA軟件中,將膠合板缺陷檢測(cè)數(shù)據(jù)中的前10%作為訓(xùn)練集,剩余90%作為測(cè)試集．實(shí)驗(yàn)證明,用基于粗糙集的決策樹(shù)算法進(jìn)行分類后,預(yù)測(cè)準(zhǔn)確率達(dá)88.3%,比人工檢測(cè)缺陷的準(zhǔn)確率提高將近20個(gè)百分點(diǎn)．

3 總結(jié)

本文提出了將粗糙集和決策樹(shù)結(jié)合,利用粗糙集對(duì)決策表中的條件屬性進(jìn)行約簡(jiǎn),去除多余屬性后,再用ID3算法構(gòu)造決策樹(shù),提取規(guī)則,并將其用于膠合板缺陷檢測(cè),并最終為企業(yè)提供決策支持．實(shí)驗(yàn)表明該方法快速有效,生成的規(guī)則簡(jiǎn)單準(zhǔn)確,計(jì)算復(fù)雜度明顯降低．

[1] QUINLAN J R.Induction of decision trees[J].Machine Learning,1986(1):81-106

[2] 王熙照,楊晨曉.分支合并對(duì)決策樹(shù)歸納學(xué)習(xí)的影響[J].計(jì)算機(jī)學(xué)報(bào),2007,30(8):1251-1258

[3] ZIARKO W.Variable precision rough set model[J].Journal of Computer and System Sciences,1993,46(1):39-59

[4] 高 雋.智能信息處理方法導(dǎo)論[M].北京:機(jī)械工業(yè)出版社,2004:254-255

[5] 翟俊海,王熙照,張滄生.基于粗糙集技術(shù)的決策樹(shù)歸納[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(11):45-47

[6] 周玉敏.基于Rough集的數(shù)據(jù)挖掘在教學(xué)評(píng)價(jià)中的應(yīng)用[J].重慶郵電大學(xué)學(xué)報(bào),2008,11(3):155-156

[7] 韓中華,馬 斌.基于譜系聚類的粗糙集數(shù)據(jù)挖掘預(yù)處理方法[J].計(jì)算機(jī)工程與應(yīng)用,2008,32(8):23-25

[8] 何 明.一種改進(jìn)的粗糙集屬性約簡(jiǎn)啟發(fā)式遺傳算法[J].西安石油大學(xué)學(xué)報(bào),2004,19(3):80-86

[9] 黃宇穎.基于粗糙集的決策樹(shù)算法在體檢系統(tǒng)中的研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(25):78-80

[10] 吳尚智.粗糙集和信息熵的屬性約簡(jiǎn)算法及其應(yīng)用[J].計(jì)算機(jī)工程,2011,37(7):56-61

The Application of Decision Tree Technology Based
on Rough Sets in Detection of the Plywood Defect

WU Xuehui

(Department of Computer Science and Technology, Yuncheng University, Yuncheng 044000, China)

Through the combination of the Decision Tree and Rough Set Theory in Data Mining, a decision tree construction algorithm based on Rough Set technology is proposed. And the algorithm is applied to the detection of the plywood defect. Rough set attribute reduction is used to find out the key factors caused the plywood defect. Then on the foundation of the reduction decision table, the decision tree is constructed by use of this algorithm, so as to extract the classification rules and to guide the decision-making process. In the end, the experiments prove that the algorithm can detect the plywood defect effectively.

rough set;decision tree;attribute reduction

2015-07-29

吳學(xué)輝(1978-),男,山西運(yùn)城人，碩士,太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院講師，主要從事數(shù)據(jù)挖掘，粗糙集研究.

1672-2027(2015)03-0037-05

TP18

A