基于样本对的极小决策树构建

摘要

随着人类社会生活、学习和日常生产的进步与Internet技术的快速发展，产生了海量的、有潜在利用价值的数据信息。如何使用相关工具和技术有效、准确和经济地从海量数据信息中发现有价值的知识，提取潜在的有效规则，更好地为生产、生活服务，已经成为数据挖掘中一个热点的研究领域。数据挖掘技术中的分类算法在商业领域中应用的最为广泛，而决策树学习算法又是数据挖掘技术的核心算法之一。ID3算法是一种构建决策树的经典算法，但ID3算法存在内在偏置和生成的决策树需要进行剪枝等问题。
　　本文主要介绍了构建决策树的新算法。针对一致决策表和不一致决策表分别作了如下研究。
　　(1)对于一致决策表，首先定义了极小特征集合，因为极小特征集合中的特征都是必要的，所以由极小特征集合中的特征构建的极小决策树中不包含冗余特征，且规则是一致的;其次给出了一种计算极小特征集合的方法和构建极小决策树的算法，并通过实例验证算法的可行性和有效性。
　　(2)对于不一致决策表，基于β分布构造出β分布一致集合，并定义了一个条件特征的相对辨识关系。由于每个极小特征都对应着某个条件特征的等价类，所以可以使用等价类寻找全部的极小特征，进而由全部的极小特征构成一个极小特征集合。最后，结合辨识关系和等价类，本文给出了一种寻找全部极小特征的方法和构建极小决策树的算法，并通过例子进行了验证。本文构建的极小决策树与传统的ID3算法相比，既没有ID3算法中的内在偏置，也没有由ID3算法生成的决策树需要剪枝这一过程等。

目录

声明

摘要

第1章 绪论

1．1 课题产生的背景

1．2 课题的应用

1．3 国内外研究现状及进展

1．4 论文的组织结构

第2章 决策树及其算法介绍

2．1 ID3算法

2．2 等价关系和决策规则

2．3 依赖函数与β分布

2．4 本章小结

第3章 基于一致决策表构建极小决策树

3．1 极小特征集合及其计算方法

3．2 极小决策树算法

3．3 数值实验

3．4 本章小结

第4章 基于不一致决策表构建极小决策树

4．1 β依赖函数特征选择和β极小条件特征子集

4．2 极小决策树算法

4．3 应用举例

4．4 本章小结

第5章 总结与展望

5．1 全文总结

5．2 研究展望

参考文献

在学校期间发表的学术论文

致谢

作者简介