Rough Set-Based Decision Tree Construction Algorithm翻译

1、基于决策树构造的粗糙集算法Sang-wook han 和 Tae-Ywern Kim汉阳大学工业工程学院，Sungdong-gu, 韩国首尔133-791softhanhanyang.ac.kr, jykhanyang.ac.kr摘要：我们运用粗糙集理论获取决策树的构造知识。决策树广泛适用于机械学习。各种各样决策方法的树被开发出来。我们的算法是一种新型树结构。它相比了对象的核心属性并基于这些特点建立了决策树。实验表明新算法比其他算法可以更有意义和更明确提取规则。关键字：粗糙集，决策树，核1引言分类是数据挖掘的重要组成部分，在这一过程中决策树是被广泛应用的工具,因为他们是容易诠释的、准确、快速。

2、粗糙集理论是一种数学技术用于分析不确切的,不确定的,或模糊的信息等方面的数据挖掘，比如人工智能和模式识别。各种各样的方法提出了构建决策树，包括基于核心属性的粗糙集理论,可以用来排除不必要的特征,从而对象创建一个数据,约简,粗糙近似的对象的简化版本。Weietal提出基于上下近似决策树的粗糙集，而baietal 是基于核心属性和熵的决策树的代表。粗糙集理论有很多优势,但它的主要好处是它不需要初步数据知识或另外的数据信息。虽然核属性在粗糙集理论中最重要的概念,人们没有做出尝试建立决策树，这种决策树使用数据集的每一件物体比较。提出了一种新的决策树分类算法,这种算法使用核心属性在数据分类提供最重大的贡

3、献。在第二部分,我们将讨论粗糙集理论的有关概念。第三部分给出了新方法的基本入门,并给出了一种简单的例子。第四部分计算实验来描述的方法。最后一部分进行总结以及未来的研究方向。2粗糙集理论在粗糙集理论，知识的表示方法是通过做的信息系统，信息系统定义如下：S=(U,Q,V,f) 其中，U是非空有限对象集合；Q是记录的属性集合，V是属性值集合，V=Vq ，对于qQ且Vq 是属性q的值，并且U*Q V整体判决函数称为信息函数，例如：f（x，q）Vq，qQ，xU。一个决策表格式一个信息系统：Q=（）。C是条件属性，D是决策属性。在这个信息系统中，子集A包含于Q称为不可分辨关系，用IND（A）表示 IND(

4、A)是一个等价关系，IND(A)把U划分为若干等价类。这些等价类是A中那些有不可分辨关系的对象的集合，这些划分集表示为U/IND(A). 约简是指保持不可分辨关系的最小的属性集。相对约简属性集P,P包含于Q，P称为是Q的约简，表示为RED Q（P），如果P在Q的集合中式最小的，Q中所有不可约去的集合称为Q的核，并用CORE（Q）表示，当aP,aCORE（Q），如果将属性a从P中删除，原始系统的决策性能将不会改变。否则,原系统的决定性能将会改变。约简和核使核心属性在决策问题中起很重要的作用,而且我们可以用它来创建简单规则的信息系统。Skowron提出了区分矩阵，这是一种解决代表性知识的方法。令S

5、=(U,Q,V,f)是一种信息系统。U=X1,X2Xn10;使用区分矩阵S,表示为M（S），定义n×n的矩阵为: for 因此，是识别对象和的所有属性集。在区分矩阵中，因为，对角元素为空集。因此，在区分矩阵中上三角部分可以忽略。3 算法3.1基本算法在信息系统中, 当我们比较对象Xi和对象Xi+1，条件属性值和决策属性值有四种可能的组合。表1给出了四种情况,通过对比两个对象的条件属性和决策属性值。C表示条件属性集合,C=c1,c2,cn,和D是一个决策属性, D=d1、d2,dk。 如果我们假设有一个条件属性“收入”和一个决策属性的“买一部计算机”。这个条件属性“收入”有两个属性值、

6、低和高,这个决策属性的“买一部计算机”有两个属性值,买还是不买。表1 两对象的对比条件情况条件属性值决策属性值（种类）条件属性Ci的判断对象xi和xi+11相同相同积极2相同不同消极3不同相同消极4不同不同积极1) 情况1，如果信息系统只有一个规则，表1的情况1，我们可以立即直接推导情况1的规则，这种价值可能是积极的。表2直接归纳了这种类型。表2 情况1：两个对象的对比顾客ID收入（条件属性）买电脑（决策属性）规则条件属性收入的判断1低不买收入=低之后不买电脑积极2低不买2)情况2：从表1中情况2推导，表3给出了含糊的结果，这个结果可能是消极的。表3 情况2：两个对象的对比顾客ID收入（条件属

7、性）买电脑（决策属性）规则条件属性收入的判断1低买收入=低之后电脑买还是不买消极2低不买3）情况3：在同一个等价类的两个事例可以归纳出两种规则。可能的结果是消极的,因为在分类相同时，情况3比情况1的规则更多。决策树的构造的重要的一个步骤就是选择能够产生“最小树”的节点属性。一个最小树有相对较少的树枝：决策规则。表4 情况3：两个对象对比顾客ID收入（条件属性）买电脑（决策属性）规则条件属性收入的判断1高买1）收入=高之后不买电脑2）收入=低之后电脑不买消极2低不买4） 情况4.第四种情况是积极的，很好地区分了属于不同分类的两个实例。表5顾客ID收入（条件属性）买电脑（决策属性）规则条件属性收入

8、的判断1高买1）收入=高之后买电脑2）收入=低之后电脑不买积极2低不买情况3和4可以代表属于相同类别或不同类别对象的典型例子。我们将应用价值函数表示情况3和4计算分类价值。我们的方法使用核心属性,包括区别矩阵的功能,贡献函数代替熵函数。Skowron和Rauszer认为区别矩阵是一个n×n矩阵关于cij定义为(cij)=aQ:a(xi)a(xj) 如果d(xi)d(xj)对i，j=1,2n，a是条件属性和d是决策属性10.在这个例子中，条件属性a是积极的。我们建议算法用Skowron 和Rauszer的想法,而且考虑对象的关系在同一类型,并确定这是(cij)=aA:a(xi)a(xj

9、) 如果d(xi)=d(xj);条件属性为消极情况10。熵cij是判别对象xi和xj的所有属性集的。基于上述讨论,我们分类贡献函数的定义如下:积极情况：（）I(Cijak)是（Cijak）的指数函数。如果条件属性ak是cij的元素，则I（cijak）否则它为0.CCp表示消极情况分类价值。分类价值函数,分类贡献是条件属性ak的积极和消极情况之和。cijak空集。CCT表示整个分类贡献。从公式5中，我们可以选择最大CCT（ak）的属性。该属性的最大贡献对分类。在区别矩阵有三个例子关于粗糙集：其一，没有核心的属性，第二个只有一个核心属性，第三个案例不止一个核心属性。该算法生成的决策树如下：1）生成

10、区别矩阵，然后三种情况是：2）案（一）：如果没有核心属性，衡量约简中的每个属性分类贡献CCT(aK）和选择一CCT(aK）最大值 的个节点的条件属性。 案例（二）：如果只有一个核心属性，选择为核心节点的属性。 案例（三）：如果有多于一个核心属性，测量分类贡献CCT(aK）的每个核心属性。 3）选择扩展属性作为每个级节点。 4）重复上述过程递归，直到在一个节点的对象都属于同一类。3.2 扩展算法我们所建议的算法对比两个对象，计算他们的对分类的贡献，并选择更可区分的属性作为一个节点。除了我们的算法，我们假设如果有焦点类，它会产生更多的有意义的和有效

11、的结果。焦点分析的重点是在目标市场营销，特殊的客户需求分析，欺诈检测重要，在不寻常情况的模型5。在第3.1节，我们的算法考虑内在和超分类的值，并选择最大CCT(aK）的条件属性aK作为一个节点，在扩展算法中，我们只比较焦点分类组与超类的类值值组，找出最大CCT(aK）。那没有消极的例子，它可以选择一个更极大贡献的特殊属性，分类决策属性值 另一个类。例如，我们可以假设保险数据表是在表6中所示的方式排列。如果我们在安排保险='N'，我们在比较和计算编号N的分类函数（客户ID 6，7和9）编号Y（客户ID 1，2，3，4，5，8和10）。表6 区分矩阵ID年龄率（a）保险费

12、用率(b)会费(c)健康检查(d)安排保险(D)145MNY255OYY344MNY455MNY535MNY654MYN724MYN845MNY955MYN1045MNY继3.1节的程序，我们为表6做区分矩阵如表7所示。表7 区分矩阵为表6123456789101a,b,da,b,da,d2b,ca,b,cc3a,b,da,da,b,d4b,da,b,dd5a,b,da,b,da,d678a,b,da,b,da,d910a,b,da,b,da,d核可以被定义为区分矩阵的所有单元素熵的集。表7 呈现出两个核心属性的c，d。我们可以计算C和D的分类 贡献如下：我们考虑在3.1节的负面情况

13、，但无论如何，当我们使用扩展算法时我们不考虑负面情况。当CCp（d）是较CCp（c）更大，然后属性d基于对分类贡献函数为标准为基础而选为根节点 。这将产生如图1所示的子树。图1 生成的子树我们可以申请相同的子集进程d = 直到在一个节点的对象都属于同一类。示例的结果如下，由这个例子中，判决结果树，如图2所示。健康检查=N ，则安排保险=Y；健康检查=N ，会费=O则安排保险=Y；健康检查=N ，会费=M则安排保险=N。图2： 使用扩展算法的决策树结构4 实验结果我们实施了来自美国加州大学欧文分校（UCL）机器学习数据库建议方法和扩展方法在小样本数据集。在先前的决定树的研究中，yang

14、et，MinZ和JAIN，和 Tu和chung对比了他们提出的算法ID3 13，6，11。要测试我们所提出算法和扩展算法的有效性和的准确性，我们必须比较那些使用ID3算法获得结果与算法C4.5的结果 。在WEKA3.4中的应用了ID3和C4.5算法，这是一个基于数据挖掘机器学习算法集合，这种算法是由Frank等4开发的。（http:/www.cs.waikato.ac.nz/ml/weka/）。建议的算法在C中实现，要求英特尔奔腾处理器2.80千兆赫，2.81 GHz的CPU时钟速度，在样本数据集和数值数据中我们忽视了丢失的数据，并用10倍交叉验证。我们增加了样本“heart-h”和

15、“credit-g”来探讨模式中的变化。表8显示了每个算法的精度和表9列出他们的规则。在图3显示规则的数量。该建议的方法和扩展方法构造更简单决策树方法比那些ID3方法所创建的。 C4.5算法性能更好，但如何才能解释结果只用一个规则的情况下，如在心脏-h时，甲状腺和生病。我们的算法似乎更有说服力。表8 使用UCI数据四种不同决策树方法规则数量规则数量数据库ID3C4.5建议算法扩展算法隐形眼镜8455心高（100）1011213动物园9766淋巴64141917心高（285）44265信贷 (500)309412522信贷(1000)708544235甲状腺10011214生病8911

16、013表9 UCI数据的四种决策树方法的精确度数据集元组条件属性分类精确度ID3C4.5建议算法扩展算法隐形眼镜24337183100100心高（100）1005296979393动物园101157929296100淋巴14815475799390心高（285）2855275808197信贷 (500)500112637196100信贷(1000)1000112627198100甲状腺377121492929294生病377320293939395我们使用的数据集的10倍交叉验证测试方法的准确性。图4给出了测试结果。在大多数情况下，我们的方法比C4.5算法准确，心脏- H的例外。建议和扩展算法

17、是有意义的事情，由此产生的结果树考虑这些属性，这些属性能提供最大分的类贡献。图3 规则数量的比较5 结论构建一个最佳分类决策树是一个完整不确定多项式（NP完成）的问题，因此它不能实现一个有效的算法。相反，必须采用启发式算法11。建议的算法是一种逻辑推理树的新概念。此外，当扩大算法有一个重点分类，扩大算法的性能更好的时候。  在UCI数据实验证明新概念的性能比ID3决策树方法和C4.5方法更好。不过，建议和扩展算法是独一无二的，因为它们使用粗糙集理论和分类属性以最大贡献的概念为基础的对象。此外，建议的方法没有数据预处理可诱导分类规则。字符和象征型数据可以被应用。尽管有上述优点，当决策表

18、时有许多不同的属性或属性值计算约简集所需的时间可能会很长，以及计算的最小约简问题是NP -难问题。Bazan等。建议减少约简计算的一个更有效的方法2。在我们的算法中包括归纳需要进一步研究。参考文献1. Bai, J., Fan, B., Xue, J.: Knowledge representation and acquisition approach based on decision tree. In: Proceedings of the, International Conference on Natural2. Language Processing and Knowledge En

19、gineering (October 2629, 2003), pp. 33538 (2003)3. Bazan, J., Skowron, A., Synak, P.: Dynamic reduct as a toll for extracting laws from decision tables. In: Ra, Z.W., Zemankova, M. (eds.) ISMIS 1994. LNCS, vol. 869, pp. 346355. Springer, Heidelberg (1994)4. Duda, R., Hart, P., Stork, D.: Pattern Cla

20、ssification, 2nd edn. Wiley, New York (2001)5. Frank, E., Hall, M., Trigg, L., WEKA, (2003), ttp:/www.cs.waikato.ac.nz/ml/weka6. Han, J., Kamber, M.: Data Mining, 2nd edn. pp. 285289 (2006)7. Minz, S., Jain, R.: Rough set based decision tree model for classification. In: Kambayashi,Y., Mohania, M.K.

21、, Wöß, W. (eds.) Data Warehousing and Knowledge Discovery. LNCS,vol. 2737, pp. 172181. Springer, Heidelberg (2003)8. Pawlak, Z.: Rough sets. International Journal of Computer and Information Science 11(1982)9. Quinlan, J.R.: Induction of decision trees. Machine Learning I, 81106 (1986)10. Quinlan, J.R.: Improved use of continuous attributes in C4.5. Artificial Intelligence 4, 7790 (1996)11. Skowron, A., Rauszer, C.M.: The discernibility matrices and functions in information systems, Institute of Computer