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

8749474

　　摘要：针对静态算法对大数据和增量数据处理不足的问题，构造了基于粗决策树的动态规则提取算法，并将其应用于旋转机械故障诊断中。将粗集与决策树结合，用增量方式实现样本抽取;经过动态约简、决策树构造、规则提取与选择、匹配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=CD，C为条件属性，D为决策属性;V是属性的值域; f是信息函数，aA，xU， f(x，a)V。当RC，IND(R)={(x，y)(U，U)|aB， f(x，a)=f(y，a)}，表示是属性R不可区分的。
　　U/IND(R)为U的等价类[10]。
　　1.2属性约简和属性依赖度
　　R为一族等价类，当aR，若IND(R)=IND(R-{a})，则称a为R中不必要的;否则a为必要的。如果aA 都是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}) 为决策表的子决策表，UU。F是决策表S的子决策表集合，简称F族。将F族中所有子决策表约简的交集称为决策表S的F动态约简[11]，即为DR(S，F)。表达式为：
　　DR(S，F)=RED(S，d)SFRED(S，d
　　此方法限制太大，所以选择更为普遍的(F，)的约简：
　　DR(S，F)={CRED(S，d)：
　　|SF：CRED(S，d)||F|1-}
　　其中[0，1]，记为DR(S，F)。
　　1.4区分矩阵与区分函数
　　决策表S=(U，CD，V， f)的区分矩阵是一个nn矩阵，矩阵中的任一元素用以下公式计算：
　　(x，y)={aC|f(x，a)f(y，a)}
　　区分函数可定义为=(x，y)UU(x，y)，函数的极小析取范式中的所有合取式是C的所有D约简[12]。
　　1.5决策规则及可信度与覆盖度
　　决策表S=(U，CD，V， f)，令Xi表示U/C的等价类，Yj表示U/D的等价类，则决策规则定义为：Xi Yj。其中Xi，Yj分别为前件和后件，当前件相同时，后件也相同，则称决策是一致的;否则为不一致[11]。
　　对于不一致性，用可信度进行度量，可信度定义为：
　　(Xi，Yj)=|XiYj||Xi|
　　规则对数据的代表性不够，从而表现出一定的随机性。在极端情况下，每个规则仅仅代表数据表中的一个数据对象，这种规则显然很难使用于新的数据对象上。
　　对于随机性，用覆盖度来表示，覆盖度定义为：
　　(Xi，Yj)=|XiYj||Yj|
　　1.6决策树技术
　　决策树是一个树结构(可以是二叉树或非二叉树)。其每个非叶子节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶子节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
　　决策树是实现数据挖掘的一种重要的分类技术。该技术分两步：一是决策树的构造;二是决策树的剪枝。决策树的构造是生成决策树的过程;决策树的剪枝是指用测试数据对生成的决策树进行验证，减去影响预测精度的分支，从而简化决策树。