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

摘要：

由于基于排序熵的有序决策树在扩展属性选取时，需计算每个条件属性的每个割点处的排序互信息，并通过对比这些排序互信息的大小来确定最大值(最大值对应的属性为扩展属性)，计算复杂度较高。针对此问题，文中将割点分为平衡割点和非平衡割点两部分，建立一个数学模型，从理论上证明排序互信息最大值不会在平衡割点处达到，而只能在非平衡割点处达到。这说明在计算排序互信息时只需遍历非平衡割点，而无需再计算平衡割点处的值，从而使决策树构建的计算效率得到较大程度提高。数值实验验证此结果。

关键词：有序分类、有序决策树、非平衡割点

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金61170040;河北省自然科学基金F2013201110,F2013201220

在线出版日期：2014-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：134-140