C4.5算法是由RossQuinlan開發的用於產生決策樹的算法。該算法是對RossQuinlan之前開發的ID3算法的一個擴展。C4.5算法產生的決策樹可以被用作分類目的,因此該算法也可以用於統計分類。
C4.5算法與ID3算法一樣使用了信息熵的概念,並和ID3一樣通過學習數據來建立決策樹。[1]
一個元組(數據集)本身有很多屬性,怎么知道首先要對哪個屬性進行判斷,接下來要對哪個屬性進行判斷?引入一個概念就是屬性選擇度量。
屬性選擇度量又稱分裂規則,因為它們決定給定節點上的元組如何分裂。屬性選擇度量提供了每個屬性描述給定訓練元組的秩評定,具有最好度量得分的屬性被選作給定元組的分裂屬性。目前比較流行的屬性選擇度量有--信息增益、增益率和Gini指標。
(1)信息增益信息增益實際上是ID3算法中用來進行屬性選擇度量的。它選擇具有最高信息增益的屬性來作為節點N的分裂屬性。該屬性使結果劃分中的元組分類所需信息量最小。對D中的元組分類所需的期望信息為下式:
![1](/img/9/dc1/cmbw5CM0EzXzgTO5UzN4kTOyczN4QTM5IjNxUTOzMTNwAzMxAzL5kzL4czLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)
![2](/img/5/eed/cmbw5CM0EzXyIjM5QDMzADMzczN4QTM5IjNxUTOzMTNwAzMxAzLwAzL3gzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![3](/img/d/937/cmbw5CM0EzXyAjN2kTN3ADMzczN4QTM5IjNxUTOzMTNwAzMxAzLwAzL2IzLt92YucmbvRWdo5Cd0FmLyE2LvoDc0RHa.jpg)
![4](/img/6/b0c/cmbw5CM0EzXwADO5ITNxIDMzczN4QTM5IjNxUTOzMTNwAzMxAzLyAzL3YzLt92YucmbvRWdo5Cd0FmLxE2LvoDc0RHa.jpg)
![5](/img/a/e8a/cmbw5CM0EzX0YzN2AjM0IDMzczN4QTM5IjNxUTOzMTNwAzMxAzLyAzL0gzLt92YucmbvRWdo5Cd0FmL0E2LvoDc0RHa.jpg)
(3)Gini指標Gini指標在CART中使用。Gini指標度量數據劃分或訓練元組集D的不純度,定義為:
![6](/img/c/57d/cmbw5CM0EzXyQTN2UDN3IDMzczN4QTM5IjNxUTOzMTNwAzMxAzLyAzLzAzLt92YucmbvRWdo5Cd0FmLwE2LvoDc0RHa.jpg)