Class Confidence Proportion不平衡数据集的决策树算法
Class Confidence Proportion算法是一种基于C4.5算法改进而来、处理不平衡数据集的决策树划分算法。由悉尼大学的LiuWei博士在2010年发表在SIAM,《A Robust Decision Tree Algorithm for Imbalanced Data Sets》。
其基本思想是通过提出一种改进的置信度Class Confidence代替原有的置信度,将数据集中的各属性值的数量转换成各属性值所占比例,从而消除了数据不平衡对属性划分带来的影响。
算法简介
对决策树也不了解的同学可以点击这里从零开始的机器学习生活—决策树
C4.5算法
CCP算法是一种基于C4.5的改进算法,C4.5算法使用增益率选择最优划分属性,增益率的定义如下:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVMk5mYmh2RaZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jNzMjM1kTNzETOxETM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
其中IV(a)属性a的固有值,属性a的可能取值数量越大,IV(a)越大,IV(a)的表达式如下:
通过计算所有属性的增益率,一种增益率最大的属性进行划分。
CCP算法
然而使用增益率划分属性,对不平衡数据的处理并不好,一些高置信度的规则对划分来说可能并不重要,一些重要的规则却没有高置信度。所以在处理不平衡数据集时需要引入新的处理方式。
下面表格是使用ID3、C4.5等传统的基于关联规则分类的数据处理情况
- FN:False Negative,被判定为负样本,但事实上是正样本。
- FP:False Positive,被判定为正样本,但事实上是负样本。
- TN:True Negative,被判定为负样本,事实上也是负样本。
- TP:True Positive,被判定为正样本,事实上也是证样本。
传统的决策树分类划分球置信度如下:
改进之后使用Class Confidence Proportion代替置信度,将原本的a,b,c,d用tpr/tpr+fnr、fnr/tpr+fnr、fpr/fpr+tnr、tnr/fpr+tnr代替,将数值转换成占positive/negative预测的比例。这样,无论是positive数量更大,还是negative数量更大,都不影响属性划分的结果。
代入数据,用下面的公式计算出Gain(D,a)。
剩下的工作和C4.5计算方式相同了,使用求出来的Gain(D,a),并求出IV(a)即可计算出增益率Gain_ratio(D,a)。
值得注意的是,C4.5算法不是直接选择增益率最大的属性进行划分,而是先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiQ3chVEa0V3bT9CX5RXa2Fmcn9CXwczLcVmds92czlGZvwVP9EUTDZ0aRJkSwk0LcxGbpZ2LcBDM08CXlpXazRnbvZ2LcRlMMVDT2EWNvwFdu9mZvwVMk5mYmh2RaZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39jNzMjM1kTNzETOxETM3EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
以上,对C4.5进行改进的CCP算法就介绍完了。
(如果有人看的话,我后续把代码给补上)