决策树顾名思义,就相当于我们平常所画的那种逻辑树形图,帮助我们一步步判断。举个例子:
我们已经知道6位女生对经济和长相和最终结果(约会还是回家)的态度,那么现在来了一个男生他的条件是经济rich,长相ugly。
我们可以看到数据集(1,2行)两位女生的态度都不相同,一位拜金女表示愿意约会,另一位外貌协会表示不约。那么这种情况怎么办呢?我们可以看第三行,有一位女生在经济rich的情况下选择了约会,那么也就是说虽然前两位女生引起了冲突,但第三位女生虽然没有完全对rich和ugly的态度表态,但她对rich,cool的男生表示了愿意约会,也就是说她对rich的男生表示愿意约会的可能性也是比较大的,相当于给了rich,ugly这个男生信心。但第五位女士又对ugly表示要回家,那到底这个男生能不能约到女生呢?
如何用数学度量这种情况呢?对于一个普适的情况而言,女生是先考虑经济,还是长相呢?决策树帮我们处理了这一类问题
决策树划分算法有非常多,这里我们拿ID3算法举例。
ID3算法主要从信息增益来考量:
信息增益公式如下,S代表没划分,A表示特征,等式右边第一个项表示没划分前的信息熵,第二个代表根据属性A划分后的信息熵
对于特征的信息熵的计算公式如下,我们假定特征A有k个属性,比如我们上述例子,经济有poor和rich两个属性,那么k=2
|Si|/|S|表示某个属性占多少,例如rich有3个,一共6个,那么Si=3,S=6。Entropy(Si)则是计算在这个属性的样本中信息熵的大小。
信息熵计算公式如下,pi表示某个label占比,继续拿上述例子举例,我们假定现在已经在rich的条件下了,那么p1表示home个数/date个数 p1 = 1/3,p2 = 2/3
我们拿上述例子来实际计算下第一个划分点:
最终经济的信息增益熵高于长相,因此我们第一划分点为经济。
如此循环判断直到划分完所有属性或者不必再继续划分
下面是我写的一个python的id3具体实现
实现的算法如下
'''
基于id3算法的决策树模型
def 创建决策树
if 所有样本都是一个类别:
创建叶节点
elif 没有属性可以划分:
选择样本标签多的作为节点值(如果label数量一样,随便选择)
else:
计算信息增益,选择分裂特征
根据分裂特征将样本分离
将已选特征从特征集中删除
for 每个样本集
递归生成决策树
'''
项目地址:https://github.com/ccyzml/my_ml_models/blob/master/decision_tree.py
最终的运行结果如下
画成决策树就是这个样子