1.数据结构文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
主要的数据结构有:1.Attribute List 2.Class List文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
对于数据集,每一个属性都有一个对应的Attribute List.如上图所示,每个Attribute List有两列,分别是对应的属性值和该条记录在Class List里的索引。根据不同的索引值,可以得到记录的类标。对于连续型的属性,Attribute List应当是有序的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
对于Class List,存储的是每条记录对应的类标以及记录所在的当前叶节点。Class List 需常驻内存当中。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
2.算法过程文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
gini index:如果一个数据集D有n个不同的类,那么:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
在属性A下,把数据集分为D1和D2,那么:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
基尼增益定义:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
算法思想:扫描全部的Attribute List.对于每一个不同的Attribute List,从上到下扫描,并计算以当前记录split所得出的基尼增益。从而求出最大基尼增益的属性和分裂点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
在对Attribute List 从上到下扫描时,需要用到另一种数据结构——类直方图。类直方图的行表分裂点的左边和右边,列代表不同的类。如上图所示,当算法扫描到Salary List的第一条记录时,首先根据index找到当前记录所属的叶子节点。可知,salary = 15时这条记录属于N2节点。当前N2节点有两条记录,类直方图初始化时默认这两条记录属于未分裂。所以,在N2节点中共有两条记录,分别是索引值1和索引值2的记录。在Class List中可知,这两条记录分别属于G类和B类。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
算法在扫描到salary = 15这条记录时,实际上是在N2这个节点做了一次试探性的分裂,N2中salary<=15的记录归为左边,其余的归为右边。类直方图可变为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
从而可以根据这次分裂算得基尼增益:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
依次向下扫描,分别得到每一次试探性分裂的基尼增益,选择基尼增益最大的分裂。比如,在N2节点中,选择salary = 15这条记录分裂所得的基尼增益最大,那么在该节点的分裂点就是(a1+a2)/2,也就是40.文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
算法在决定每一个当前叶子节点的分裂点之后,需要根据分裂点,更新Class List中每条记录所属的叶子节点。然后再次循环分裂。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/12962.html