一种不确定多变量决策树生成算法.pdfVIP

一种不确定多变量决策树生成算法1 1 2 1 邵良杉 ，邱云飞 ，孙韶光 1 辽宁工程技术大学系统工程研究所，辽宁阜新（123000 ） 2 辽宁工程技术大学软件学院，辽宁葫芦岛（125100 ） E-mail ：lntushao@163.com 摘 要：针对常规多变量决策树算法不能有效处理噪声数据影响的问题，将 Pawlak.Z 粗糙 集(rough set ，RS)模型中相对核的概念推广到变精度粗糙集(variable precision rough set ，VPRS) 模型中，并利用其进行决策树初始变量选择；将两个等价关系相对泛化的概念推广为两个等 价关系多数包含情况下的相对泛化，并利用其进行决策树初始属性检验；最后，给出一种能 够有效消除噪声数据干扰的多变量决策树构造算法。 关键词：决策树；噪声数据；变精度粗糙集；相对核 中图分类号：TP 181 文献标识码：A 决策树作为分类和预测的重要工具，为确定某一事例类别的序贯决策方法提供了清晰的 陈述。决策树主要有单变量决策树和多变量决策树两种。由于单变量决策树在每个节点上只 检验一个属性（如ID3[1] ，AQ11[2] ，ASSISTANT[3]和GREEDY3GROVE[4]等），从而造 成了对很多复杂概念的表达困难或无法表达[5]，为了解决这个问题人们提出了许多多变量 决策树构造算法（如Brodley C E[6]等人采用初始属性的线性组合来构造多变量决策树，苗 夺谦、王珏[5]利用粗糙集的相对核的概念构造多变量决策树），即在树的结点上可以同时检 验多个属性。然而，这些算法都是在理想的环境下进行推导的，没有考虑现实中噪声数据对 分类的影响。 Ziarko[7]等人提出的变精度粗糙集(variable precision rough set，VPRS)模型是对 Pawlak.Z 的粗糙集(rough set，RS)模型的一种推广。VPRS 通过设置阈值参数(0.5 β ≤1) ，放松了 RS 理论对近似边界的严格定义，即允许一定程度的错误分类率的存在。随着β 变大，VPRS 模型的近似边界区域变窄，即变精度粗糙集意义下的不确定区域变小。当β 1 时，VPRS 模型就变成了 RS 模型，因此 RS 模型是 VPRS 模型的一个特例。相对 RS 模型来说 VPRS 模型对数据的不确定性有一定的容忍度。 构造不确定多变量决策树的关键问题是如何消除噪声数据对分类的影响，本文基于变精 度粗糙集模型提出了一种不确定多变量决策树构造算法。本文第 1 节将 Pawlak 粗糙集模型 中相对核的概念引入变精度粗糙集模型中，给出了变精度粗糙集模型下相对核的定义，解决 了有噪声数据干扰下的初始属性选择问题；从容忍数据中存在一定不确定性现象的角度出 发，将[5]中两个等价关系相对泛化的概念，推广为两个等价关系多数包含情况下的相对泛 化，进而进行多变量初始属性检验；第 2 节给出了不确定信息下的多变量决策树生成算法； 第 3 节给出了本文的结论。 1. 属性的选择及相对泛化 1.1 变精度粗糙集模型的相对核及属性的选择 变精度粗糙集模型是对Pawlak粗糙集模型的扩充。设X 和 Y 表示有限论域U 的非空子 集，令0.5 β ≤1 ，定义多数包含关系(majority inclusion relation)[7]： 1 本课题得到教育部博士点基金（20041047006 ）和国家自然科学基金）的资助。 -1- β Y ⊇X ⇔D (Y | X ) ≥β 其中， | X IY | / | X |, | X |0 ⎧