基于變精度粗糙集理論的決策樹生成方法的研究

摘 要：文章在基于變精度粗糙集模型的基礎(chǔ)上，研究了具有置信度規(guī)則的一種新的決策樹構(gòu)造方法。新算法對(duì)基于粗糙集的決策樹生成方法進(jìn)行改進(jìn)，新算法以變精度加權(quán)平均粗糙度作為屬性選擇標(biāo)準(zhǔn)構(gòu)造決策樹，綜合分析訓(xùn)練數(shù)據(jù)的噪聲數(shù)據(jù)，引入在構(gòu)造決策樹的過程中存在的不一致性。在決策樹生長(zhǎng)過程中引入置信度，以控制決策樹的生長(zhǎng)，得到具有確切置信度的決策規(guī)則。

關(guān)鍵詞：決策樹；粗糙集理論；置信度；變精度粗糙集理論

中圖分類號(hào)：TP311.13

1 Pawlak理論決策樹生成方法的缺陷

Pawlak粗糙集理論可以用不完全信息或知識(shí)去處理一些不分明現(xiàn)象，具有良好的數(shù)學(xué)基礎(chǔ)和性質(zhì)。但在構(gòu)造決策樹過程中，單一使用該理論不能有效描述不精確的實(shí)際問題。Ziarko基于多數(shù)包含關(guān)系提出了可變精度粗糙集理論，可以處理某種程度上的包含關(guān)系，讓模型具有一定的抗噪聲能力。

2 變精度粗糙集理論的概念及特點(diǎn)

2.1 變精度粗糙集理論的概念

粗糙集理論規(guī)定，下近似是根據(jù)某等價(jià)關(guān)系判斷肯定包含于某子集X的等價(jià)類組成的并集；上近似是可能包含于X的等價(jià)類的并集，要求集合與集合之間要么“嚴(yán)格包含”，要么“嚴(yán)格不包含”。Ziarko基于多數(shù)包含關(guān)系提出了可變精度粗糙集理論，它是一種經(jīng)典粗糙集理論的擴(kuò)展，它能解決屬性間無(wú)函數(shù)或不確定關(guān)系的數(shù)據(jù)分類問題。

2.2 特點(diǎn)

變精度粗糙集理論作為經(jīng)典粗糙集模型的一種擴(kuò)展，具有經(jīng)典粗糙集模型不具備的特點(diǎn)：

（1）具有較強(qiáng)的數(shù)據(jù)的處理能力；

（2）模型的容噪性在原始分類過程中容噪和約簡(jiǎn)過程中，分類正確率β值分別是靜態(tài)和動(dòng)態(tài)的；

（3）變精度粗糙集模型除了考慮樣例數(shù)據(jù)中正確的分類規(guī)則，還考慮了某種程度錯(cuò)誤分類率的分類規(guī)則，使其有更高的規(guī)則泛化程度。

3 一種新的決策樹構(gòu)造算法

3.1 一種新的構(gòu)造決策樹的改進(jìn)算法

在原有理論的加權(quán)平均粗糙度概念的基礎(chǔ)上，提出變精度加權(quán)平均粗糙度的概念，并作為屬性選擇的標(biāo)準(zhǔn)。

定義：變精度加權(quán)平均粗糙度

（1）

其中β為錯(cuò)誤分類率，i、j表示第i、j個(gè)條件屬性，m是決策屬性等價(jià)類的個(gè)數(shù)。γRβ（i）的取值范圍是[0，1]，γRβ（i）越小包含的確定性因素就越大。

3.2 生成具有確切置信度的葉節(jié)點(diǎn)

置信度描述了規(guī)則成立的可能性。變精度粗糙集允許在分類時(shí)存在置信度為β的誤差，但在人們只知道其置信度大于1-β，不知道其確切的置信度，不利于用戶更好的使用這些規(guī)則。生成具有確切置信度的葉節(jié)點(diǎn)的方法：

設(shè)，U/R={X1，…Xi…，Xp}，U/D={Z1，…Zj…，Zq}。對(duì)于Xi，如果存在Zj使得Pr（Zj/Xi）≥1-β，則認(rèn)為Xi是Zj所在的同一個(gè)類，并且葉節(jié)點(diǎn)不再劃分。并把這條規(guī)則的置信度設(shè)置為Pr（Zj/Xi）。這里，，是集合Xi相對(duì)于集合Z的正確分類率。

3.3 算法描述

輸入：訓(xùn)練實(shí)例集U，條件屬性集C，決策屬性集D，設(shè)定錯(cuò)誤分類率β（0≤β<0.5）。

輸出：具有確切置信度規(guī)則的決策樹。

（1）初始化根節(jié)點(diǎn)，設(shè)定錯(cuò)誤分類率β；

（2）如果C為空或者U中所有樣本都已經(jīng)被分類到相應(yīng)的帶標(biāo)記的葉節(jié)點(diǎn)或者不存在沒有標(biāo)記的節(jié)點(diǎn)，算法停止并轉(zhuǎn)入（6）。否則，選擇一個(gè)沒有標(biāo)記的節(jié)點(diǎn)，計(jì)算U′/D={Z1′，…Zj′…，Zq′}；

（3）如果U′中所有樣本在錯(cuò)誤分類率β滿足Pr（Zj/U′）≥1-β，則把節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)，并設(shè)置這條分類規(guī)則的置信度為Pr（Zj/U′），并轉(zhuǎn)入（2），否則繼續(xù)；

（4）對(duì)于所選節(jié)點(diǎn)中的可用的條件屬性，計(jì)算其對(duì)應(yīng)的變精度加權(quán)平均粗糙度，選擇最小的屬性作為決策樹劃分屬性；

（5）依據(jù)劃分屬性對(duì)所選節(jié)點(diǎn)劃分，建立決策分支，并得到各分支相應(yīng)的U′；轉(zhuǎn)入（2）；

（6）輸出決策樹，返回。

3.4 算法復(fù)雜度分析

生成的決策樹最壞情況下的深度為|C|，每層最多的實(shí)例數(shù)是|U|，因此每一層的最壞時(shí)間復(fù)雜度是O（|C||U|2），故算法的最壞時(shí)間復(fù)雜度為O（|C|2|U|2）。

3.5 程序?qū)崿F(xiàn)

（1）首先導(dǎo)入訓(xùn)練樣本集，用于生成分類模型。提示成功導(dǎo)入數(shù)據(jù)和數(shù)據(jù)的條數(shù)，數(shù)據(jù)表顯示出各屬性（條件屬性和決策屬性）及其取值；

（2）創(chuàng)造決策樹之前先設(shè)置錯(cuò)誤分類率β。系統(tǒng)采用基于變精度加權(quán)平均粗糙度的方法構(gòu)造決策樹，因此需要設(shè)置錯(cuò)誤分類率β，β的取值范圍是[0，0.5]；

（3）參數(shù)設(shè)置完畢，即可進(jìn)行構(gòu)造決策樹操作，決策樹顯示了決策樹的具體內(nèi)容、訓(xùn)練數(shù)據(jù)量以及決策樹大小的信息，并且葉節(jié)點(diǎn)具有確切的置信度；

（4）將決策樹轉(zhuǎn)換為決策規(guī)則。此過程是將決策樹轉(zhuǎn)化為比較直觀的規(guī)則形式，讓用戶能更好地理解分類結(jié)果。分類規(guī)則是用if-then的形式表示，從根到樹葉的每條路徑創(chuàng)建一個(gè)規(guī)則：沿著給定路徑上的每個(gè)屬性-值對(duì)形成規(guī)則“if”部分的一個(gè)合取項(xiàng)；葉節(jié)點(diǎn)形成規(guī)則的“then”部分；

（5）對(duì)生成的規(guī)則進(jìn)行測(cè)試。通過導(dǎo)入測(cè)試數(shù)據(jù)集對(duì)決策規(guī)則的準(zhǔn)確度進(jìn)行測(cè)試。整個(gè)算法就是通過上述過程來(lái)體現(xiàn)的?？梢钥闯?，通過優(yōu)化算法得到的決策樹更簡(jiǎn)單（既樹的深度小，節(jié)點(diǎn)少）；分類準(zhǔn)確度也較好，具有良好的預(yù)測(cè)能力。

4 結(jié)束語(yǔ)

本文首先介紹了Pawlak粗糙集理論的決策樹生成方法的缺陷，并給出了變精度粗糙集理論的基本概念和特點(diǎn)，提出一種基于變精度粗糙集理論的決策樹構(gòu)造算法，并以實(shí)現(xiàn)。

參考文獻(xiàn)：

[1]熊范綸，杭小樹.基于粗糙集理論的實(shí)例學(xué)習(xí)研究[J].浙江大學(xué)學(xué)報(bào)，2002（03）：346-354.

[2]曾黃麟.粗集理論及其應(yīng)用-關(guān)于數(shù)據(jù)推理的新方法[M].重慶：重慶大學(xué)出版社，1994：1-198.

[3]張文修，吳偉志，梁吉業(yè).粗糙集理論與方法[M].北京：科學(xué)出版社，2001：1-224.

[4]鄂旭，高學(xué)東，喻斌.基于掃描向量的屬性約簡(jiǎn)方法[J].北京科技大學(xué)學(xué)報(bào)，2006（04）：604-608.

作者簡(jiǎn)介：李想（1982.07-），男，遼寧錦州人，碩士研究生，講師，研究方向：數(shù)據(jù)挖掘、圖像處理、系統(tǒng)可靠性研究、計(jì)算機(jī)網(wǎng)絡(luò)。

作者單位：遼寧石化職業(yè)技術(shù)學(xué)院，遼寧錦州 121001