决策树原理
决策树的一个重要任务是获取数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,在这些机器根据数据集创建规则时,就是机器学习的过程。专家系统中经常使用决策树,而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。
在构造决策树时,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征,划分出最好的结果,我们必须评估每个特征。完成测试之后,原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,则当前无需阅读的垃圾邮件已经正确地划分数据分类,无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型,则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同,直到所有具有相同类型的数据均在一个数据子集内。
在划分数据集之前之后信息发生的变化称为信息增益,知道如何计算信息增益,我们就可以计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。分类算法除了需要测量信息熵,还需要划分数据集,度量划分数据集的熵,以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的划分方式。
遍历当前特征中的所有唯一属性值,对每个特征划分一次数据集 ,然后计算数据集的新熵值,并对所有唯一特征值得到的熵求和。信息增益是熵的减少或者是数据无序度的减少,比较所有特征中的信息增益,返回最好特征划分的索引值。
信息增益 = 信息熵-条件熵
最大熵原理:系统中事件发生的概率满足一切已知约束条件,不对任何未知信息做假设,也就是对于未知的,当作等概率处理。
由吉布斯不等式推导
条件熵 <= 信息熵
反证法:
已知条件熵H(Y)
假设以X作为分类变量,将Y分为2组, X1组中的信息熵H(x1) > H(Y);
因此X1组的复杂度高于Y,此时必定存在
香农辅助定理(吉布斯不等式)
通俗理解条件熵
通俗理解决策树算法中的信息增益
决策树(一)熵、条件熵、信息增益
图解最大熵原理
信息熵越大,信息量到底是越大还是越小?
熵的性质
吉布斯不等式