- 相關推薦
粗決策樹動態規則提取算法研究及應用
摘要：針對靜態算法對大數據和增量數據處理不足的問題，構造了基于粗決策樹的動態規則提取算法，并將其應用于旋轉機械故障診斷中。將粗集與決策樹結合，用增量方式實現樣本抽取;經過動態約簡、決策樹構造、規則提取與選擇、匹配4個步驟的循環迭代過程，實現了數據的動態規則提取，使得提取的規則具有更高的可信度;同時，將算法應用于旋轉機械故障診斷這一動態問題中，驗證了算法的有效性;最后，將所提算法分別與靜態算法和增量式動態算法進行了效率對比分析，實驗結果表明，所提算法能夠以最精簡的規則獲得更多數據隱含信息。
關鍵詞：粗集;靜態算法;動態約簡;動態規則;決策樹
引言
粗集理論[1]主要用來處理模糊和不確定性知識，對數據進行約簡、去除冗余，在保持分類能力不變的前提下，通過知識約簡導出問題的決策和分類規則。近年來，吳順祥等[2]利用粗集進行規則提取，提出了一種基于粗集理論的規則提取方法;譚俊璐等[3]利用決策樹(decision tree)提取規則實現分類計算;丁春榮等[4]將粗集與決策樹結合構造規則提取算法。石凱[5]將粗集理論中的屬性約簡與決策樹算法相結合，提出了改進算法;胡煜等[6]從ID3算法的缺點出發，根據粗集理論完成了對ID3算法的改進，為建立決策樹分析模型奠定了基礎。
以上這些算法均是在靜態數據研究背景下提出的，可以從海量數據中提取相對精確的知識，但這種規則提取方法只能針對靜態數據，對于現實生活中的大量動態數據，以往的基于靜態數據的規則提取算法很難得到正確的規則。而目前我們處于大數據時代，網絡數據、股票數據、機械故障診斷收集數據等均具有明顯的動態特征，直接應用靜態數據下的算法，勢必會使提取的規則產生很大的誤差，因此，研究適合動態數據的規則提取算法顯得尤為重要。
目前，關于動態規則提取算法的研究也有相關報道：如余峰林等[7]提出的基于差別矩陣的動態約簡及規則提取和尹阿東等[8]提出的動態決策樹算法研究等，但這些算法存在著求解速度慢、約簡程度不夠等缺陷。王楊等[9]提出的基于粗集和決策樹的增量式規則約簡算法比傳統算法和粗集決策樹增量知識獲取算法(Rough setRule tree Incremental knowledge acquisition Algorithm， RRIA)在效率方面有所提高，但仍存在著提取的規則集不夠精簡等缺陷。因此，本文提出將粗集與決策樹相結合，設計動態規則提取算法，同時兼顧約簡精確程度和約簡時間兩方面，從而更有效地實現決策規則的提取。
本文算法的基本思想：抽取樣本進行屬性約簡;按約簡結果建立決策樹;通過規則的準確度和覆蓋度進行規則提取;用未抽取樣本進行規則匹配，確定規則的有效性，并判斷屬性約簡是否穩定(若得到穩定約簡，即匹配成功;若沒有匹配成功，則增大抽取樣本，直到達到要求為止)。
一、基本理論
1.1不可區分關系
信息系統S=(U，A，V， f)，其中U為論域;A=C∪D，C為條件屬性，D為決策屬性;V是屬性的值域; f是信息函數，a∈A，x∈U， f(x，a)∈V。當RC，IND(R)={(x，y)∈(U，U)|a∈B， f(x，a)=f(y，a)}，表示是屬性R不可區分的。
U/IND(R)為U的等價類[10]。
1.2屬性約簡和屬性依賴度
R為一族等價類，當a∈R，若IND(R)=IND(R-{a})，則稱a為R中不必要的;否則a為必要的。如果a∈A 都是R中必要的，稱R獨立;否則稱R為依賴的。
若QP，如果Q是獨立的，且IND(Q)=IND(P)，稱Q為P的一個約簡。CORE(P)=∩RED(P)，其中CORE(P)為P的核，RED(P)為P的約簡。
屬性依賴度：K=max{|XiYj|/|Yj|}，K表示決策分類對條件屬性集的依賴度。
1.3動態約簡
S=(U，CU5vajrimf)為一決策表，S′=(U′，C∪5vajrimf) 為決策表的子決策表，U′U。F是決策表S的子決策表集合，簡稱F族。將F族中所有子決策表約簡的交集稱為決策表S的F動態約簡[11]，即為DR(S，F)。表達式為：
DR(S，F)=RED(S，d)∩∩S′∈FRED(S′，d
此方法限制太大，所以選擇更為普遍的(F，ε)的約簡：
DR(S，F)={C∈RED(S，d)：
|S′∈F：C∈RED(S′，d)||F|≥1-ε}
其中ε∈[0，1]，記為DRε(S，F)。
1.4區分矩陣與區分函數
決策表S=(U，C∪D，V， f)的區分矩陣是一個n×n矩陣，矩陣中的任一元素用以下公式計算：
α(x，y)={a∈C|f(x，a)≠f(y，a)}
區分函數可定義為Δ=∏(x，y)∈U×U∑α(x，y)，函數Δ的極小析取范式中的所有合取式是C的所有D約簡[12]。
1.5決策規則及可信度與覆蓋度
決策表S=(U，C∪D，V， f)，令Xi表示U/C的等價類，Yj表示U/D的等價類，則決策規則定義為：Xi →Yj。其中Xi，Yj分別為前件和后件，當前件相同時，后件也相同，則稱決策是一致的;否則為不一致[11]。
對于不一致性，用可信度進行度量，可信度定義為：
μ(Xi，Yj)=|Xi∩Yj||Xi|
規則對數據的代表性不夠，從而表現出一定的隨機性。在極端情況下，每個規則僅僅代表數據表中的一個數據對象，這種規則顯然很難使用于新的數據對象上。
對于隨機性，用覆蓋度來表示，覆蓋度定義為：
φ(Xi，Yj)=|Xi∩Yj||Yj|
1.6決策樹技術
決策樹是一個樹結構(可以是二叉樹或非二叉樹)。其每個非葉子節點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉子節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
決策樹是實現數據挖掘的一種重要的分類技術。該技術分兩步：一是決策樹的構造;二是決策樹的剪枝。決策樹的構造是生成決策樹的過程;決策樹的剪枝是指用測試數據對生成的決策樹進行驗證，減去影響預測精度的分支，從而簡化決策樹。
二、算法設計
粗決策樹動態規則提取是利用數據的動態約簡構造決策樹，從而得到規則。首先對數據進行預處理，當數據為連續型數據，對數據進行離散化處理;然后隨機抽取樣本，進行約簡構造決策樹;最后根據可信度和覆蓋度提取規則，用未抽取樣本進行規則匹配，以判斷約簡是否穩定，若匹配不成功，說明約簡不穩定，則增大抽取樣本并循環上述過程，反之停止。粗決策樹的動態規則提取，利用動態約簡既能匹配已知數據，又能匹配未知數據的優勢，解決了在線數據規則提取的難題，更有利于數據挖掘。具體步驟如下：
步驟1從總體樣本中抽取部分樣本，構造區分矩陣，計算區分函數，進行屬性約簡。
步驟2建立決策樹。以屬性約簡計算出的核屬性作為根節點，然后計算除核屬性之外的屬性約簡的屬性依賴度，將屬性依賴度大的作為節點的分支，當依賴度相同時，將序號小的作為節點的分支。建立的決策樹的個數與屬性約簡的個數相同。
步驟3規則提取與選擇。計算可信度和覆蓋度，從上到下、從左到右遍歷決策樹，當可信度和覆蓋度達到設定的閾值時，提取規則。當有不一致的信息時，提取可信度高、覆蓋度大的作為規則。
步驟4規則匹配。將提取的規則，與樣本中未抽取的樣本進行匹配，測試得出的規則是否有效，同時判斷屬性約簡的穩定性。當匹配不成功，轉步驟5;否則轉步驟6。
步驟5增大隨機抽取的樣本。增大樣本后再重復進行步驟1～4的操作，直到提取樣本規則匹配已知樣本中未抽取的樣本為止。其穩定的屬性就是匹配成功的屬性與增量樣本屬性通過交運算得到的，滿足動態約簡的規則提取方法。
步驟6獲得最終規則。停止抽取樣本，將最后得到的規則進行整合，得到最終的規則。
三、算法應用
以旋轉機械故障診斷數字化后的決策表(表1)為案例[14]驗證算法。
表1中，U={X1，X2，…，X6}為對象的故障征兆有限集;k為樣本個數;C={C1，C2，…，C5}為故障條件屬性集合，C1表示振動烈度，C2為振動一倍頻幅值，C3為振動二倍頻幅值，C4為振動高頻幅值，C5為振動的相位變化;D為決策屬性，0表示無故障，1表示有故障;C1、C2、C3、C4的值為0表示無，1表示有;C5的值為0表示相位穩定，1表示相位不符合穩定要求。具體計算過程如下：
步驟1抽取50%以上樣本，本例中抽取X3、X4、X5、X6。抽取之后的決策表如表1后4行所示，計算得到區分矩陣：
000C2C3C1C2C40C1C3C4C5C500
將其按長度依次排序，得出區分函數：
Δ=C5∧(C2∨C3)∧(C1∨C2∨C4)∧(C1∨C3∨C4∨C5
將析取的合取表達式轉化為合取的析取表達式，得出結果：Δ=(C2∧C5)∨(C1∧C3∧C5)∨(C3∧C4∧C5)。
所以得到3個約簡{C2，C5}、 {C1，C3，C5}、 {C3，C4，C5}，并且CORE(Δ)=C5。
步驟2建立決策樹。屬性依賴度K(C1)=0，K(C2)=0.644，K(C3)=0.658，K(C4)=0。
根據屬性依賴度可以計算出決策樹的構造過程。以C1、C3、C5為例給出構造過程：由于C5是核屬性，因此將C5作為根節點;比較屬性依賴度K(C3)>K(C1)，所以選擇屬性依賴度大的C3為根節點的分支;最后將C1作為C3的分支節點。這樣可以得到約簡{C1，C3，C5}的決策樹，如圖1(c)所示。圖1(a)為約簡{C2，C5}建立的決策樹;圖1(b)為約簡{C3，C4，C5}建立的決策樹，具體計算過程不再重復。利用屬性依賴度構造的決策樹，簡單易懂，又能很好地進行分類。
步驟3計算可信度和覆蓋度。
規則的不確定主要包括不一致性和隨機性。規則的不一致性可以通過可信度來檢驗;規則的隨機性可以通過覆蓋度來檢驗，最后提取出有效的規則。
以C3、C5為例計算，U/IND(R)={{X3}，{X4，X5}，{X6}}， U/D={{X3，X4}，{X5，X6}}。
設：X1={X3}，X2={X4，X5}，X3={X6}，Y1={X3，X4}，Y2={X5，X6}，計算可信度和覆蓋度：
μ(X1，Y1)=|X1∩Y1||X1|=2525=1
φ(X1，Y1)=|X1∩Y1||Y1|=2525+13=0.66
計算結果如表2所示。
根據表2進行規則提取，分別設定可信度和覆蓋度的閾值，選擇可信度和覆蓋度大于閾值的進行規則提取。當有不一致的信息時，提取可信度高、覆蓋度大的作為規則�？梢栽O定可信度的閾值為0.5，覆蓋度的閾值為0.3。此例中C5=0，出現不一致的信息，取可信度和覆蓋度大的，即if C5=0，then D=1; if C3=0，C5=0，then D=0。利用可信度和覆蓋度對決策樹進行剪枝得到規則，取滿足設定閾值的規則，即去掉表2中第2條和第8條規則。步驟4規則匹配。將得到的規則匹配樣本X1，規則匹配后由表2第3條規則得出的決策屬性D=0，而實際上D=1。即得出的規則無效，規則匹配失敗，可以判斷屬性約簡不穩定，轉步驟5。步驟5增加抽取樣本的數量�？梢栽黾訕颖綳2，根據數據X2，X3，X4，X5，X6得出屬性約簡的結果為：{C1，C2，C5}，{C1，C3，C5}，{C3，C4，C5}，{C2，C3，C5}，{C2，C4，C5}。按照步驟2的方法構造得到5棵決策樹，提取可信度達到閾值的規則，當出現不一致信息時，提取可信度和覆蓋度大的作為規則。增大樣本的規則集見表3。用樣本X1進行匹配，規則1和規則4可以匹配，規則15不能匹配，所以根據匹配與否進行規則刪除，即提取有效規則。由于存在有效規則，所以將其屬性約簡與匹配成功的屬性進行交運算，得到穩定的屬性約簡。步驟6得到最終規則。算法結束，獲得最終23條規則(如表3所示，27條規則中刪除序號為12～15的四條規則)，這些規則代表與其匹配成功，得到穩定屬性約簡提取出的有效規則。用本文的動態規則提取算法，得到穩定的約簡為{C1，C2，C5}，{C1，C3，C5}，{C3，C4，C5}，{C2，C3，C5}，而本例通過靜態算法得到的約簡為{C1，C3，C5}，{C2，C3，C5}，{C3，C4，C5}，由此可見，動態約簡包含了更多的隱含信息，對于增量的旋轉機械故障問題能夠更好地進行診斷。
四、算法效率分析
4.1與靜態算法對比分析
通過與靜態算法基于粗集和決策樹的規則提取方法[14]進行比較，當振動二倍頻幅值、相位不穩定，對應的數字形式化為C3=1，C5=1，進行規則匹配，通過表3第4條規則可以得到D=1，推出旋轉機械有轉子不對中故障，相應的可信度為1，覆蓋度為0.46，相應的覆蓋度高于文獻[14]中覆蓋度，如表4所示，說明動態算法比靜態算法診斷精度更高。
當旋轉機械中沒有振動烈度，相位也不穩定，數字化為C1=0，C5=1，通過表3的第16條和第19條規則可以得到D=1，推出旋轉機械有轉子不對中故障。而在文獻[14]中不能找到相應的規則去匹配，而是通過減少條件來匹配，結果往往帶來誤差。靜態算法在面對海量決策表和動態變化決策表的約簡時，所得的約簡不夠穩定，無法描述決策表局部變化的規律，會出現較大決策誤差。由此可見，本文設計的粗決策樹動態規則提取算法能夠更好地挖掘出數據本身潛在的信息，從而獲得更精確的決策規則。
4.2與增量式約簡算法對比分析
將本文算法與文獻[9]的基于粗集和決策樹的增量式規則約簡算法進行對比分析如下：
1)文獻[9]中規則樹構造算法第2步中，構造的決策樹是通過條件屬性的取值個數從小到大排列條件屬性構造的決策樹，傾向于選擇取值較多的屬性作為分支決策，但在有些情況下這類屬性可能不會提供太多有價值的信息，從而導致決策出現偏差;而本文算法根據屬性依賴度的大小作為決策樹的分支屬性來構造決策樹，決策分類對條件屬性集的依賴度程度越大說明屬性對于決策越重要，這樣構造的決策樹更有利于正確決策。
2)文獻[9]中基于粗集和決策樹的增量式規則約簡算法，當新對象與規則集不一致時，增加屬性值來辨別規則，沒有考慮規則數據的隨機性，從而出現噪聲;而本文算法針對規則的不一致性和隨機性分別通過可信度和覆蓋度來進行決策，當可信度和覆蓋度達到設定閾值時對規則進行提取，既能對不一致規則進行正確決策，又能夠有效過濾數據的隨機性產生的噪聲，得到最精簡的規則集，提高規則集匹配效率。
3)針對本案例，將文獻[9]中的算法與本文算法規則約簡結果作對比。當增加樣本X1，X2時，即增加新對象C11C20C31C40C51→D1，C10C20C31C41C51→D1，用本文算法和文獻[9]算法得出的約簡分別如表5和表6所示(x表示此處可取0或1)。經約簡結果對比，本文算法提取的規則要比文獻[9]中提取的規則集更精簡，提高了規則集匹配效率，凸顯了本文算法的優越性。
綜上所述，通過與其他算法的比較，粗決策樹動態規則提取算法能夠以最精簡的規則挖掘出數據本身潛在的信息，從而提高決策效率。
五、結語
本文提出了基于粗決策樹的動態規則提取算法，并將其應用于旋轉機械故障診斷。該算法利用粗集動態約簡與決策樹規則提取的優勢，采用增量式的樣本抽取，用得到的動態約簡進行匹配，以便提取更為有效的規則，彌補了靜態約簡無法描述決策表局部變化規律的缺陷。最后，用旋轉機械故障診斷問題為應用背景，驗證了算法的有效性，并分別與靜態算法和基于粗集和決策樹的增量式規則約簡算法進行了對比分析。本文算法能夠以最精簡的規則獲得更多數據隱含信息，為實時、動態數據的處理提供了一種解決思路，具有一定的理論價值和推廣價值。
參考文獻：
[1] ZHANG W， WU W， LIANG J， et al. Rough set theory and method [M]. Beijing： Science Press， 2001：1-39.(張文修，吳偉志，梁吉業，等.粗集理論與方法[M].北京：科學出版社，2001：1-39.)
[2] WU S， LIU S， GU J. A rule extraction method based on rough sets theory [J]. Journal of Xiamen University：Natural Science， 2004，43(5)：605-608.(吳順祥，劉思峰，辜建德.基于粗集理論的一種規則提取方法[J].廈門大學學報：自然科學版，2004，43(5)： 605-608.)
[3] TAN J， WU J. Study of classification algorithm based on the decision tree rules [J]. Computer Engineering and Design， 2010， 31 (5) ： 1017-1019.(譚俊璐，吳建華.基于決策樹規則的分類算法研究[J].計算機工程與設計，2010，31(5)：1017-1019.)
[4] DING C， LI L. A decision tree rule extraction algorithm based on rough set [J]. Computer Technology and Development， 2007， 17(11)：111-113.(丁春榮，李龍.一個基于粗集的決策樹規則提取算法[J].計算機技術與發展，2007，17(11)：111-113.)
[5] SHI K. Attribute reduction based on rough set theory and decision tree classification algorithm research [D]. Dalian： Dalian Maritime University， 2014.(石凱.基于粗集理論的屬性約簡與決策樹分類算法研究[D]. 大連： 大連海事大學，2014.)
[6] HU Y， ZHENG J. Improved ID3 algorithm based on rough set theory and application [J]. Journal of Guiyang College， 2015， 10 (1)： 16-20.(胡煜，鄭娟.基于粗集理論的ID3算法的改進與應用[J].貴陽學院學報，2015，10(1)：16-20.) [7] YU F， WANG R， ZHU X， et al. Dynamic reduction and rule extraction based on discernibility matrix algorithm[J]. Automation and Instrumentation， 2007，22(6)：1-4.(余峰林，王儒敬，朱學昊，等.基于差別矩陣的動態約簡及規則提取算法[J].自動化與儀表，2007，22(6)：1-4.)
[8] YIN A， XIE L， LONG Y， et al. Dynamic decision tree algorithm study[J]. Computer Engineering and Applications， 2004，40(33)：103-105.(尹阿東，謝林銓，龍譽，等.動態決策樹算法研究[J]. 計算機工程與應用，2004，40(33)：103-105.)
[9] WANG Y， YAN D， ZHANG F. Based on rough set and decision tree rules of incremental reduction algorithm [J]. Computer Engineering and Application， 2007，43(1)： 170-172.(王楊，閆得勤，張鳳梅.基于粗集和決策樹的增量式規則約簡算法[J].計算機工程與應用，2007，43(1)：170-172.)
[10] ZHOU H. Dynamic reduction based on rough set theory research [D]. Changsha： Central South University， 2004.(周化.基于粗集理論的動態約簡研究[D].長沙：中南大學，2004.)
[11] SHU W， SHEN H. Incremental feature selection based on rough set in dynamic incomplete data [J]. Pattern Recognition， 2014， 47(12)：3890-3906.
[12] SON C， KIM Y， KIM H， et al. Decisionmaking model for early diagnosis of congestive heart failure using rough set and decision tree approaches [J]. Journal of Biomedical Informatics， 2012， 45(5)：999-1008.
[13] LIAO Q， HAO Z， CHEN Z. Data mining and mathematical modeling [M]. Beijing： National Defense Industry Press， 2010：126-138.(廖芹，郝志峰，陳志宏.數據挖掘與數學建模[M].北京： 國防工業出版社，2010：126-138.)
[14] XIA Y. Extracting rules based on rough set and decision tree method research [D]. Nanchang： Nanchang University， 2008.(夏葉娟.基于粗集和決策樹的規則提取方法研究[D]. 南昌： 南昌大學，2008.)
【粗決策樹動態規則提取算法研究及應用】相關文章：
試析決策樹算法在教育統計學中的應用論文12-02
基于構造超平面的兩階段決策樹算法的研究03-28
大學課程表問題中的算法研究與應用03-01
計數查找算法的研究11-22
外包的動態治理研究03-24
路面裂縫影像幾何特征提取算法03-07
關于LZW算法的改進研究03-25