基于排序熵的有序决策树高效算法研究

摘要

基于排序熵的有序决策树归纳在选择扩展属性时,需要计算每个条件属性的每个割点的排序互信息,并通过比较这些排序互信息的大小来选择扩展属性,计算复杂度高,特别是在处理海量数据时,计算时间复杂度高会成为该算法的应用瓶颈。
　　针对以上问题,本文研究了如何提高有序决策树的计算效率,主要工作包括以下两个方面:
　　1.在选取扩展属性时,将割点分为平衡割点和非平衡割点两部分,建立了一个数学模型,从理论上证明了排序互信息最大值不会在平衡割点处达到,而只能在非平衡割点处达到。这个结果意味着算法在计算排序互信息时只需遍历非平衡割点,而无需计算平衡割点处的值,这样可提高有序决策树归纳的计算效率。
　　2.针对海量数据的有序分类问题,论文探讨了几种基于排序熵的有序决策树并行策略,并给出了基于MapReduce的有序决策树算法并行化方法,可使选择扩展属性的时间降低、算法的效率提高。
　　分别在人工数据集和实际数据集上进行了实验,实验结果表明本文提出的方法可提高有序决策树归纳的计算效率。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 背景知识及研究意义

1.2 有序分类的研究现状

1.3 有序决策树的发展与研究现状

1.4 本文的主要工作及内容安排

第2章 基础知识

2.1 有序分类问题的描述

2.2 单调分类

2.3 信息熵

第3章 有序决策树算法简介

3.1 有序决策树的适用对象及过程

3.2 基于排序熵的有序决策树简介

3.3 基于排序熵的有序决策树性质

3.4 本章小结

第4章 改进的基于排序熵的有序决策树算法

4.1 非平衡割点引入分析

4.2 命题的证明

4.3 引入非平衡割点的有序决策算法的归纳

第5章 有序决策树算法并行化研究

5.1 有序决策树算法的并行策略

5.2 有序决策树并行的具体实现

5.3 实验对比

5.4 本章小结

第6章 结论与展望

6.1 结论

6.2 展望

参考文献

致谢

攻读学位期间取得的科研成果