粗决策树动态规则提取算法研究及应用

摘要：针对静态算法对大数据和增量数据处理不足的问题，构造了基于粗决策树的动态规则提取算法，并将其应用于旋转机械故障诊断中。将粗集与决策树结合，用增量方式实现样本抽取；经过动态约简、决策树构造、规则提取与选择、匹配4个步骤的循环迭代过程，实现了数据的动态规则提取，使得提取的规则具有更高的可信度；同时，将算法应用于旋转机械故障诊断这一动态问题中，验证了算法的有效性；最后，将所提算法分别与静态算法和增量式动态算法进行了效率对比分析，实验结果表明，所提算法能够以最精简的规则获得更多数据隐含信息。

关键词：粗集；决策树；静态算法；动态约简；动态规则

中图分类号： TP301.6；O29

文献标志码：A

0引言

粗集理论[1]主要用来处理模糊和不确定性知识，对数据进行约简、去除冗余，在保持分类能力不变的前提下，通过知识约简导出问题的决策和分类规则。近年来，吴顺祥等[2]利用粗集进行规则提取，提出了一种基于粗集理论的规则提取方法；谭俊璐等[3]利用决策树（decision tree）提取规则实现分类计算；丁春荣等[4]将粗集与决策树结合构造规则提取算法。石凯[5]将粗集理论中的属性约简与决策树算法相结合，提出了改进算法；胡煜等[6]从ID3算法的缺点出发，根据粗集理论完成了对ID3算法的改进，为建立决策树分析模型奠定了基础。

以上这些算法均是在静态数据研究背景下提出的，可以从海量数据中提取相对精确的知识，但这种规则提取方法只能针对静态数据，对于现实生活中的大量动态数据，以往的基于静态数据的规则提取算法很难得到正确的规则。而目前我们处于大数据时代，网络数据、股票数据、机械故障诊断收集数据等均具有明显的动态特征，直接应用静态数据下的算法，势必会使提取的规则产生很大的误差，因此，研究适合动态数据的规则提取算法显得尤为重要。

目前，关于动态规则提取算法的研究也有相关报道：如余峰林等[7]提出的基于差别矩阵的动态约简及规则提取和尹阿东等[8]提出的动态决策树算法研究等，但这些算法存在着求解速度慢、约简程度不够等缺陷。王杨等[9]提出的基于粗集和决策树的增量式规则约简算法比传统算法和粗集决策树增量知识获取算法（Rough setRule tree Incremental knowledge acquisition Algorithm， RRIA）在效率方面有所提高，但仍存在着提取的规则集不够精简等缺陷。因此，本文提出将粗集与决策树相结合，设计动态规则提取算法，同时兼顾约简精确程度和约简时间两方面，从而更有效地实现决策规则的提取。

本文算法的基本思想：抽取样本进行属性约简；按约简结果建立决策树；通过规则的准确度和覆盖度进行规则提取；用未抽取样本进行规则匹配，确定规则的有效性，并判断属性约简是否稳定（若得到稳定约简，即匹配成功；若没有匹配成功，则增大抽取样本，直到达到要求为止）。

1基本理论

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，CU{d}）为一决策表，S′=（U′，C∪{d}） 为决策表的子决策表，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决策树技术

决策树是一个树结构（可以是二叉树或非二叉树）。其每个非叶子节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶子节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

决策树是实现数据挖掘的一种重要的分类技术。该技术分两步：一是决策树的构造；二是决策树的剪枝。决策树的构造是生成决策树的过程；决策树的剪枝是指用测试数据对生成的决策树进行验证，减去影响预测精度的分支，从而简化决策树。

2算法设计

粗决策树动态规则提取是利用数据的动态约简构造决策树，从而得到规则。首先对数据进行预处理，当数据为连续型数据，对数据进行离散化处理；然后随机抽取样本，进行约简构造决策树；最后根据可信度和覆盖度提取规则，用未抽取样本进行规则匹配，以判断约简是否稳定，若匹配不成功，说明约简不稳定，则增大抽取样本并循环上述过程，反之停止。粗决策树的动态规则提取，利用动态约简既能匹配已知数据，又能匹配未知数据的优势，解决了在线数据规则提取的难题，更有利于数据挖掘。具体步骤如下：

步骤1从总体样本中抽取部分样本，构造区分矩阵，计算区分函数，进行属性约简。

步骤2建立决策树。以属性约简计算出的核属性作为根节点，然后计算除核属性之外的属性约简的属性依赖度，将属性依赖度大的作为节点的分支，当依赖度相同时，将序号小的作为节点的分支。建立的决策树的个数与属性约简的个数相同。

步骤3规则提取与选择。计算可信度和覆盖度，从上到下、从左到右遍历决策树，当可信度和覆盖度达到设定的阈值时，提取规则。当有不一致的信息时，提取可信度高、覆盖度大的作为规则。

步骤4规则匹配。将提取的规则，与样本中未抽取的样本进行匹配，测试得出的规则是否有效，同时判断属性约简的稳定性。当匹配不成功，转步骤5；否则转步骤6。

步骤5增大随机抽取的样本。增大样本后再重复进行步骤1～4的操作，直到提取样本规则匹配已知样本中未抽取的样本为止。其稳定的属性就是匹配成功的属性与增量样本属性通过交运算得到的，满足动态约简的规则提取方法。

步骤6获得最终规则。停止抽取样本，将最后得到的规则进行整合，得到最终的规则。

3算法应用

以旋转机械故障诊断数字化后的决策表（表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进行规则提取，分别设定可信度和覆盖度的阈值，选择可信度和覆盖度大于阈值的进行规则提取。当有不一致的信息时，提取可信度高、覆盖度大的作为规则。可以设定可信度的阈值为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增加抽取样本的数量。可以增加样本X2，根据数据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算法效率分析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时，即增加新对象C11C20C31C40C51D1，C10C20C31C41C51D1，用本文算法和文献[9]算法得出的约简分别如表5和表6所示（x表示此处可取0或1）。经约简结果对比，本文算法提取的规则要比文献[9]中提取的规则集更精简，提高了规则集匹配效率，凸显了本文算法的优越性。

综上所述，通过与其他算法的比较，粗决策树动态规则提取算法能够以最精简的规则挖掘出数据本身潜在的信息，从而提高决策效率。

5结语

本文提出了基于粗决策树的动态规则提取算法，并将其应用于旋转机械故障诊断。该算法利用粗集动态约简与决策树规则提取的优势，采用增量式的样本抽取，用得到的动态约简进行匹配，以便提取更为有效的规则，弥补了静态约简无法描述决策表局部变化规律的缺陷。最后，用旋转机械故障诊断问题为应用背景，验证了算法的有效性，并分别与静态算法和基于粗集和决策树的增量式规则约简算法进行了对比分析。本文算法能够以最精简的规则获得更多数据隐含信息，为实时、动态数据的处理提供了一种解决思路，具有一定的理论价值和推广价值。

参考文献：

[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.）