Decision Tree -- 决策树

假如给定数据如下:

根据头发长度和体重对性别进行分类
hair weight>70 gender
long no F
long yes M
short yes M
short no M

有了以上的数据,我们就可以对其他的数据进行分类了。比如对{"long", "yes"},我们可以将其分类为"M"。但是有一个问题,怎么将这个数据与已有的数据进行比对呢?当然我们可以每项挨个进行遍历,直到找到与目标完全相等的,但是这个过程一点都不直观,效率也不怎么好,我们也不知道数据中每项的重要性。对于例子中的数据,我们可以写出对应的简单的决策树如下:

/attachment/id3_1_26d5361e1c6515b3d660173a2cdbd999.png

构建好决策树后,对数据分类的过程,先判断"weight>70"项的值,"yes", 好了,转到相应节点,已经到叶子节点了,所以分类为"M",判断一次就得出结论了,效率提高了不少,而且通过树结构可以清楚的看出各项的重要程度,这些就是决策树拥有的一些优点。

ID3 Algorithm -- ID3算法

ID3算法属于监督式学习的。给定数据集,可以用ID3算法构建决策树,最后用构建好的决策树对数据进行分类。

ID3算法的基础是香农熵(Shannon Entropy), 代表数据的混乱程度,其计算公式如下:

\begin{equation*} E = -\sum_{i=1}^{N} log_2 (X_i) \end{equation*}

其中\(i和X_i\) 分别为目标属性的个数和概率。熵最小为0,数据中某项如果只能有一个选择,那其熵值为0。

Info Gain信息增益是用原数据集的熵减去目标数据项所得。信息增益大的数据项位于决策树的上层,从直观上理解可以更快地对数据进行分类。

comments powered by Disqus