计算机 数学 外文翻译 外文文献 英文文献 模糊决策森林.doc

模糊决策森林Cezary Z. JanikowDepartment of Math and Computer ScienceUniversity of Missouri St. L摘要：过去，我们已经提出了模糊决策树，现在作为一种扩展就称本文中的方法为模糊决策森林。森林背后的想法不仅是要代表多个树，而且还要代表在每棵树的各级进行的测试选择。这样产生的树其实是一个三维树。森林允许在决策树的一些或所有的结点进行测试的多种选择。然而，有多个测试选择的主要优点是在测试数据的特征是不可靠或丢失的情况下，有选择测试决策。在本文中，我们概述了模糊决策森林背后的想法，并且用特征值缺失的数据进行了大量的实验，证明了这种方法的增强能力。一 引言当今时代，面对海量的的数据，开发能够处理和挖掘数据的计算机程序显得尤为重要。对于分类任务，决策树被证明是最成功的方法之一1 6 7。用决策树的形式以及推理步骤的来获取知识，一直以准确性，效率和可理解性为人称道。决策树方法原本是为符号域和一个简单的决策过程提出的6，它有着许多方法论的进步性，如能产生二叉树处理连续数据1，新的推理过程，例如，计算决策的概率7，最后纳入模糊集和不确定性推理推论法说明噪音和不确定的状况2 8。决策树是由两个要素组成：一个自上而下的划分递归过程，生成决策树，然后从得到的树推出规则。该过程开始于训练集，根据可用的变量和域通过特征的组合来表达，并划分为若干类。划分过程一次选择一个测试，通常是一个特征，然后根据测试特征将数据分成几个子集。选定的测试是为了最大限度地提高一些目标，如将不同类的样例分离7。一旦样例被完美的分类或者达到一些其他目标，递归过程就停止 7。随后的推理规则使用树来分配新的测试数据，到达一些相同的类。模糊集与逻辑被提出用来处理语言和数据有关的不确定性9。同不确定性推理相结合，模糊表达提供了更大的稳定性和鲁棒性。这种表示已纳入决策树，在树中仍然保持了其标准的优势，并且更强大和更稳定2 8。一个模糊决策树（FID）就是这样一个扩展2。 FID可以处理由符号值和连续变量混合描述的数据。 FID原本要求所有域预划分成模糊集。之后又被扩展到允许预划分和未划分的变量共存3 4。然而，FID具有和所有决策树一样的传统缺点。决策树过程试图尽量减少训练数据分类的测试次数。这大大提高了综合性，但同时也减少了在数据中学习到的特征数量。认识到这个潜在的问题以后，研究人员提出了扩展，如：得到多个不同的决策树，随后表决或应用另一个决策过程再对新的数据集进行分类。模糊决策森林包含了与模糊决策树相似的思想。最后获取的知识是更高维的而且是更不好理解的。但是模糊决策森林的简单切片却减少了对简单树的描述。此外，最后得到的模糊决策树提高了分类的精度，尤其是处理特征值丢失的测试数据的时候。在本文中，我们综述了模糊决策树背后的思想，然后给出了实验结果，说明它的增强能力。二 模糊决策森林建立一个决策树的过程是：每一个树结点选择一个测试，这可以最大化的使不同类的数据分离。这种单一的测试产生最小的知识决策树的过程就是一个判别学习过程的一个例子，其目的是尽量减少类描述，从而减少了测试的变量和测试特征的集合。当两个测试在一个结点提供相似的质量，其中一个需要遗弃，取舍哪一个有时候是很随机的。遗弃的那个测试减少了树中表达的知识。 在一个结点上执行的不同测试可能会导致不同的决策。保留这多个测试，用冲突的解决过程组合，增加了分类的潜力。这在两种情况下尤其重要：1与成功测试相关的特征在给定的测试数据可能是有噪音或不准确的。保留选择测试提高了预测精度。2在一个给定的测试数据中，和成功测试相关的特征可能信息存在丢失。处理这个问题传统的方法是测试这个特征的所有情况然后解决由此产生的冲突7。再者，保留其他相关的测试，可以使得推理更全面和更正式。模糊决策森林通过允许在所有结点上执行选择测试来扩展模糊决策树。FDF除了以下的方面，建树过程和FID是一样的：在一个特定的结点，可以选择不止一个测试。每一个测试结果，将生成不同的子树。实际选择的测试的数量，是基于一些启发式和参数。通过选择将相似类分离是重要的；但是，潜在的选择试验次数在更深的层次将减少。如果在根结点有不止一个测试，结果得到的树其实是一个森林。此外，选择测试也可以在更深的层次探索，产生了一个三维树5。通过在每一个结点选择一个测试可能会产生森林的一个部分。森林的一部分确实是一个决策树。从相同的数据中，在每个结点进行最好的选择测试生成的森林和决策树建立的树是一样的。当然，你需要一个推理过程来探索在森林保留的额外信息。FID提供了许多推理过程2。每一个推理过程需要用到路径约束匹配测试数据的所有叶子，并以一些方式结合那些叶子的类别。当数据和模糊决策森林不止一棵树匹配的时候，就会导致仅仅是更多的叶子参与最终投票。树的每个部分投出属于自己的一票。然后，每一个部分提出推理和类别。这一推论是：a)每个类的投票和（一个简单的投票），b)加权和，在部分中（片相匹配的测试数据更具有加权更高的表决），c）加权和，用产生结果的每个测试的长度来加权（匹配测试数据的部分不但更好而且有更多的训练数据有较高的投票）模糊决策森林如图1所示，在这里我们假设三个变量A，B和C，域作为说明。森林在两个结点只使用了两个选择测试，看上去是个二维的。图示中的森林可以用三种方法分解，如图2所示。假设第一个部分对应占主导地位的模糊决策树，就是如果不选择替代测试方法会建成的那棵树。现在假设，我们有具有以下特点的测试数据：A=a2, B=b1, C=c1.。第一部分将数据分到的叶子上类别，第二部分将数据分到的叶子上类别，第三部分将数据分到叶子上的类别。当解决了这三者之间的潜在的冲突时，我们可以给来自主导树的中更高的权重。另外，如果有更多训练数据，我们给它更高的权。这证明了来自森林的潜在推论。三 实验我们已经进行了两组实验，一组是在从机器学习保管人那里得到的真实数据-glass的数据，另一组是人为修改过的数据-修改过的glass数据。3.1 玻璃数据Glass数据集是机器学习中使用的标准数据之一。它包含214个样本，7个不同的glass类。每个数据样本由9个连续值属性描述，并且属性值是无缺失的。首先，我们训练一个模糊决策树，模糊决策森林在10字交叉验证中建立起来，当面临着同样的终止条件，计算训练集中的错误（避免与实验一过分专业化），结果列于表1。正像我们所看到的，模糊决策森林训练是为了让训练数据达到更高的精度。如果模糊决策树通过overspecializing它的树实现了较高的训练精度，这本身可能是不相关的。为了验证这一点，我们用测试数据测试生成的模糊决策树和模糊决策森林，同样是用10字交叉验证，在真实数据上开始进行。结果如表1，它表明模糊决策森林具有更高的精度。然后，我们重复同样的试验，但每次从测试集中删除不同百分比的特征。这些结果如图3所示。正如所看到的，模糊决策森林和单独的模糊决策树相比在缺失特征数据上显示出了更高的鲁棒性3.2 修改过的glass数据我们还修改了glass数据，如下：对于每三个随机属性，我们增加了两个属性并随机生成对应的属性值，但通过这种方式，新属性到原始属性的关系是0.75和0.5。这是为了模拟一个或多个属性是相关的，能产生相似的测试的情况。然后，我们重复以前的10字交叉验证实验：训练模糊决策树和模糊决策森林，之后在缺失特征值的数据上测试。结果如图4所示，它说明用模糊决策树方法可以在属性相关上取得优势以建立多余的部分来提高预测精度（给定运行参数，切片数量从6到11）。4 结论我们提出了模糊决策森林的概念，它通过在树的一些结点进行多种测试来重新训练，从而扩展决策树。最终得到的树确实是一个三维的森林。森林可以被切割，产生单个决策树。但是，很多切片可以用在对测试数据进行分类的推理过程中。当测试数据中的一些特征是含噪音的，不确定的，或者只是缺失的时候，这个过程特别有用。实验结果确实证明，产生的森林在我们经常遇到但又不好的条件下，更有推理能力。该软件可从/janikow/FID得到。10. 参考文献1 Breiman, L., Friedman, J.H., Olshen, R.A., Stone,C.J., Classification and Regression Trees, Wadsworthand Brooks, 1984.2 C.Z. Janikow, “Fuzzy Decision Trees: Issues and Methods”, IEEE Transactions on Man, Systems, andCybernetics, Vol. 28, Issue 1, pp. 1-14, 1998.3 M. Fajfer, C.Z. Janikow, “Bottom-up Partitioning in Fuzzy Decision Trees”, Proceedings of the 19thInternational Conference of the North American Fuzzy Information Society, Atlanta 2000, pp. 326-330.4 C.Z. Janikow, M. Fajfer. “Fuzzy Partitioning with FID3.1”, Proceedings of the 18th International Conference of the North American Fuzzy Information Society, NY 1999, pp. 467-471.5 C.Z. Janikow, M. Fajfer, “Fuzzy Decision Forest”,Proceedings of the19th International Conference of theNorth American Fuzzy Information Society, Atlanta 2000,pp. 218-221.6 J.R. Quinlan, “Induction on Decision Trees”, Machine Learning, Vol. 1, 1986, pp. 81-106.7 Quinlan, J.R., C4.5: Program for Machine Learning, Morgan Kaufmann, San Mateo, CA, 1993.8 M. Umano, H. Okamoto, I. Hatono, H. Tamura, F.Kawachi, S. Umedzu, J. Kinoschit