说这个前,需要重申一下,机器学习的主要目的在于预测。对于给定的训练集,总有一个结局变量(outcome,好与坏,高与低,长与短),决策树通常用于结局为二分类变量的案例预测。同时,我们有许多用来预测结局变量的特征变量(比如你想通过外观来预测一个人有没有到了中年,特征变量可能是……胖瘦、皱纹、发量……算了,越写越伤心)。
决策树呢,就是根据某一个特征变量,将结局变量分类。我们需要考虑两个因素,一个是纯度(purity)一个是熵(entropy)。纯度就是在一个特征类别中,一类事物的比例是不是很高,如果胖子里都是中年,那中年在胖子这个特征里的纯度就很高。熵呢,我们在大学化学课学过,它是物质混乱程度的度量,我们这里的熵跟化学课上的熵有一点点不一样,这里是信息熵,表示信息的混乱程度,也用大写的S表示。
决策树大概长这样:
上面这张图片来自百度百科,如果你在犹豫要不要出去打网球,你可能看一下外面,感受一下温度,适度和风的强度,然后做出你的判断,上面的这幅图可能代表了你的决策流程,但是你通常不会画出这种图来,如果你的行为方式被机器掌握,电脑会帮你画出一幅这样的图来,它叫决策树。决策树是如何找出特征变量,帮助决策的呢?下面是一种最常用的算法,叫C5.0,它根据信息的增益率来采纳特征变量:
以下是有点烧脑的部分……
根据熵的定义:
其中c:是类的水平数;Pi:是落入第i类中某案例的比例。
如果只有2各类:那么S∈ [0, 1];如果有n类:那么S∈ [0, log2n]
这东西咋算?
假设我们有一伙人,青年占40%,中年占60%,则该数据的分割熵计算方法如下:
再回到要不要去打网球的问题:
注:此数据来源于http://m.blog.csdn.net/sinat_26917383/article/details/47617801
这组数据中的outcome中有9个yes和5个no,首先算一下这组数据的总信息熵:
然后,我们要计算根据Outlook这组特征分割案例后得到的熵值:
一个分割得到的总熵是根据案例落入分区中的比例Wi加权的N个分区的熵值总和,表述成公式:
所以,观察上表:Outlook中有三个属性:Sunny、Overcast、Rain。
Sunny有2个Yes,3个No;Overcast里有4个Yes,个No;Rain里有3个Yes,2个No。
所以根据Outlook得到的总熵值:
得结果:
用总信息熵减去分割熵,叫做这个分割属性的信息增益,那么Outlook的信息增益可计算:
用以上同样的方法,可求得:
比较四者,发现Outlook的信息增益是最大的,也就是说,按照Outlook这个属性作为分类,可以尽可能的把去和不去打网球的情况分开,如此Outlook变成了新的节点。
再往下,outlook成为了新的根节点,根据sunny、overcast、rain进行了分割,又有了新一级的信息熵,sunny下方再从Temperature、Hunmidity和Wind中,依据上法寻找新的特征变量进行再次分割,知道分割后的信息增益为,或不再有新的特征变量可供分割。
如此,就是决策树的构建方法了。
文字从来不会治愈谁,它只是一种温柔的陪伴——七七电影解药
领取专属 10元无门槛券
私享最新 技术干货