论文部分内容阅读
分类是数据挖掘领域中一种非常重要的研究方法。分类的主要任务是为一个实例或对象归类,通过建立一个分类模型(或分类器),既可以用此模型研究已有的数据,也可以用它来预测未来的数据。目前可用于分类的方法很多,如决策树、粗糙集、贝叶斯网络、模糊集、遗传算法、人工神经网络等。其中,决策树方法以其结构简单、计算量较小且分类精度较高、易于提取显式规则等优点而成为广大数据挖掘领域专家学者的研究热点,并且提出了大量的方法来构建决策树,如基于粗糙集的决策树方法、基于模糊集的决策树方法、基于遗传算法的决策树方法等。本文主要研究基于粗糙集的决策树构建方法。粗糙集理论是PawlakZ教授于1982年提出来的,它是一种处理不精确、不确定和不完备信息的数学工具。本文的研究重点是如何将粗糙集和决策树这两种分类技术有机地结合起来,取长补短,发挥各自的优势,为分类的实际应用寻找一种有效的方法和途径。
本文在总结和借鉴前人经验的基础上,从理论和应用两个方面进行了研究。在理论方面,本文不仅研究了基于粗糙集的单变量决策树算法,同时也对基于粗糙集的多变量决策树算法以及粗糙集的属性约简算法进行了研究,从而使基于粗糙集的决策树方法更加完善。在应用方面,将改进的决策树方法应用到边坡稳定性分析中,从大量的历史边坡数据中提取出边坡状态规则以预测边坡是否稳定,从而为边坡的防护和治理提供决策支持。本文的主要研究内容概括如下:
(1)详细概述了决策树和粗糙集技术的原理、方法、种类、研究热点以及国内外研究现状,为本文后续研究提供了可靠的理论支撑。
(2)由于现有单变量决策树的分裂属性选择标准存在以下两个问题:一方面,基于信息论的属性选择标准(信息增益或信息增益率)大多未考虑条件属性和决策属性之间的关联性,从而造成生成的决策树分枝较多,规模较大,并且在有噪声的情况下分类精度迅速下降;另一方面,基于粗糙集的决策树分裂属性选择标准虽然考虑了条件属性和决策属性之间的相关性,但未能从信息论角度考虑某些重要条件属性自身对分类的影响。针对以上两方面不足,本文基于变精度粗糙集提出了一种决策树分裂属性选择标准,并在此基础上形成一种决策树构建算法(VPRSUDT)。该算法综合考虑了变精度粗糙集的属性依赖度和信息论中的信息增益率。属性依赖度反映条件属性与决策属性之间的依赖关系,可以选出与决策属性关系最紧密的条件属性;信息增益率则反映条件属性自身在信息论角度下的优劣。本文还考虑了当两个或两个以上属性的启发函数值相同时,如何选择分裂属性进行下一步分裂。UCI24个数据集仿真实验以及与C4.5算法和现有四种常见的变精度粗糙集分裂属性选择标准对比实验验证了改进的算法的可行性与优越性。
(3)针对现有启发式约简算法的空间复杂度和时间复杂度都较高且易陷入局部最优等问题,本文提出了一种基于改进粒子群优化的属性约简算法(RSIPSOAR)。与遗传算法相比,粒子群优化不需要交叉与变异等复杂的运算,只需使用简单的数学运算。因此,它易于实现,收敛速度和迭代速度相对较快。但基本粒子群优化算法(BPSO)也容易陷入局部最优,不能在全局范围内搜索最优属性约简集。因此,本文首先提出一种改进粒子群优化算法(IPSO),对初始搜索粒子生成机制、速度更新函数以及适应度函数进行了改进,并在此基础上提出一种属性约简算法(RSIPSOAR)。该算法中,为了加快收敛速度,引入条件属性在决策属性上的支持度以及相对属性重要度来获得相对核,并将此相对核作为初始粒子在属性空间搜索最优约简的起点。通过在UCI20个数据集上仿真实验并与四种经典的属性约简算法进行比较表明,RSIPSOAR算法在绝大多数数据集上能获得全局最优约简,且具有较快的收敛速度和较高的分类精度。
(4)针对单变量决策树算法存在的树的规模庞大、规则复杂不易理解以及现有多变量决策树算法的多变量构造难以准确的描述分类,算法时间复杂度也较高等问题,本文提出了一种基于粗糙集正域度与相对核的多变量决策树构造算法(RSODT)。该算法首先引入正域度,然后结合相对核中的核属性将满足正域度要求的属性共同作为构造多变量检验的属性,并利用相对泛化将这些属性合取,进行多变量检验。UCI36个数据集仿真实验结果表明,RSODT的分类精度和决策树规模与ID3算法以及四种经典的多变量决策树分类算法相比有较大的改善。
(5)由于基于粗糙集的决策树分类算法能够从海量的数据中挖掘出有用的分类规则,所以将改进的分类方法(VPRSUDT和RSODT)应用到边坡稳定性分析中具有可行性和实际应用性。一方面,这可以有效利用大量宝贵的历史边坡数据提取出边坡状态的规则,为现阶段或以后的边坡稳定性分析工作提供决策支持;另一方面还可以发现影响边坡状态最重要的因素,针对这些因素结合边坡的实际情况可对边坡采取有效的防范和治理措施。
(6)最后对本文研究工作进行了系统总结,并展望了有待进一步研究的方向。
综上所述,本文在分析和研究粗糙集技术和决策树技术以及已有的基于粗糙集的决策树方法的基础上,重点研究了基于变精度属性依赖度和信息增益率的单变量决策树分裂属性选择标准以及由此形成的决策树分类算法、基于改进粒子群优化的属性约简算法、基于粗糙集正域度和相对核的多变量决策树分类算法、改进的决策树分类算法在边坡稳定性分析中的应用。在研究中通过数据集仿真实验的方法证明了各算法的有效性和工程实际应用的可行性。