如何(更好地)离散化决策树中的连续数据?

数据挖掘 决策树
2021-10-14 11:26:31

标准决策树算法,如 ID3 和 C4.5,有一种蛮力方法来选择连续特征中的切点。每个值都作为可能的切点进行测试。(通过测试我的意思是,例如信息增益是在每个可能的值上计算的。)

由于有许多连续特征和大量数据(因此每个特征有很多值),这种方法似乎非常低效!

我假设找到一种更好的方法来做到这一点是机器学习中的一个热门话题。事实上,我的谷歌学术搜索揭示了一些替代方法。比如用k-means进行离散化。然后似乎有很多论文解决特定领域的特定问题。

但是,是否有最近的评论论文、博客文章或书籍对常见的离散化方法进行了概述?我一个都没找到...

或者,也许你们中的一个人是该主题的专家并且愿意写一个小概述。那将非常有帮助!

1个回答

不,您可能不想在认真的实现中尝试所有可能的切入点。这就是我们在 ID3 的简单介绍中描述它的方式,因为它更容易理解,但通常不是它实际实现的方式,因为它很慢。特别是,如果有n 数据点,那么你需要测试 n-1候选阈值;使用朴素算法计算每个候选阈值的信息增益需要(n) 每个候选人的时间,总共 (n2) 时间。

在实践中,有一些优化可以显着加快速度:

  1. 不要尝试所有可能的阈值。相反,选择 1000 个候选阈值的随机样本(从一组n-1 候选阈值),计算每个阈值的信息增益,并选择最佳的。

  2. 使用动态规划有效地计算所有的信息增益 n-1 拆分,总共 (n)时间,通过重用计算。该算法很容易推导出来。