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算法使用增益率選擇最優劃分屬性，增益率的定義如下：

其中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算法不是直接選擇增益率最大的屬性進行劃分，而是先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。

以上，對C4.5進行改進的CCP算法就介紹完了。

（如果有人看的話，我後續把代碼給補上）