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

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