ID3算法
- 算法流程描述
-
- 算法流程
- python實作代碼
-
- 各方法的解釋
- 代碼
- 資料集介紹
- 訓練資料和測試資料劃分
- 結果分析
-
- 分類準确率及決策樹
- 優點和缺點
- 改進的算法：
-
- C4.5算法
- CART算法
算法流程描述
ID3算法是一種貪心算法，用來構造決策樹。它以資訊熵的下降速度為選取測試屬性的标準，即在每個節點選取還尚未被用來劃分的具有最高資訊增益的屬性作為劃分标準，然後繼續這個過程，直到生成的決策樹能完美分類訓練樣例。
算法流程
- 輸入需要分類的資料集和類别标簽和靶标簽。
- 檢驗資料集是否隻有一列，或者是否最後一列(靶标簽資料預設放到最後一列)隻有一個水準(唯一值)。是則傳回唯一值水準或者占比最大的那個水準。
-
調用資訊增益公式，計算所有節點的資訊增益，得到最大資訊增益所對應的類别标簽。
資訊熵公式：
資訊增益公式：
機器學習之ID3算法（小白入門級别）算法流程描述資料集介紹訓練資料和測試資料劃分結果分析優點和缺點改進的算法： 
機器學習之ID3算法（小白入門級别）算法流程描述資料集介紹訓練資料和測試資料劃分結果分析優點和缺點改進的算法： - 建立決策樹字典用以儲存該次葉節點資料資訊。
- 進入循環：按照該類别标簽的不同水準，依次計算子資料集；對子資料集重複(1),(2),(3),(4),(5)步。
- 傳回決策樹字典。
該算法使用python語言實作，最終生成的決策樹實際上是一個大的遞歸函數，其結果是一個多層次的字典。
python實作代碼
各方法的解釋
LoadDataSet函數用來載入資料。
ID3Tree類中，_best_split用來周遊标簽并計算最大資訊增益對應的标簽；_entropy就是計算熵；_split_dataSet用于切割資料集；_top_amount_level是遞歸終止條件觸發時的傳回值。即隻有一個特征列的一個level的子集時，如果對應的purchase還有買和不買(level)，就傳回最大占比的level；mktree主程式，遞歸生成決策樹，并将其儲存在tree字典中；predict主程式，用于預測分類；_unit_test，單元測試程式，用于測試上面一些函數。
代碼
import numpy as np
import pandas as pd
import json
from divideData import divide_data
# 用于載入資料
class LoadDataSet(object):
def load_dataSet(self):
data = pd.read_csv("./train_ID3data.txt", sep="\t", header=None) # 傳回DataFrame類型：二維标記資料結構
data.rename(columns={0: "age", 1: "income", 2: "student", 3: "reputation", 4: "purchase"}, inplace=True) # 修改列名
return data
class ID3Tree(LoadDataSet):
"""主要的資料結構是pandas對象"""
__count = 0
def __init__(self):
super().__init__()
"""認定最後一列是标簽列"""
self.dataSet = self.load_dataSet()
self.gain = {}
def _entropy(self, dataSet):
"""計算給定資料集的熵"""
labels = list(dataSet.columns) # 擷取列名，即屬性标簽
level_count = dataSet[labels[-1]].value_counts().to_dict() # 統計分類屬性标簽的各類水準
entropy = 0.0
for key, value in level_count.items(): # 對每一種分類都計算
prob = float(value) / dataSet.shape[0] # 使用某類數量除dataSet.shape[0]（行數），即某分類個數/總數
entropy += -prob * np.log2(prob) # 計算資訊熵
return entropy # 傳回資訊熵
def _split_dataSet(self, dataSet, column, level):
"""根據給定的column和其level來擷取子資料集"""
subdata = dataSet[dataSet[column] == level] # 選出某列值為level的行資料，建構資料子集
del subdata[column] # 删除這個劃分字段列
return subdata.reset_index(drop=True) # 重建索引
def _best_split(self, dataSet):
"""計算每個分類标簽的資訊增益"""
best_info_gain = 0.0 # 求最大資訊增益
best_label = None # 求最大資訊增益對應的标簽(字段)
labels = list(dataSet.columns)[: -1] # 不包括最後一個靶标簽
init_entropy = self._entropy(dataSet) # 先求靶标簽的香農熵
for _, label in enumerate(labels): # enumerate() 函數用于将一個可周遊的資料對象(如清單、元組或字元串)組合為一個索引序列，同時列出資料和資料下标，一般用在 for 循環當中
# 根據該label(也即column字段)的唯一值(levels)來切割成不同子資料集，并求它們的香農熵
levels = dataSet[label].unique().tolist() # 擷取該分類标簽的不同level
label_entropy = 0.0 # 用于累加各水準的資訊熵；分類标簽的資訊熵等于該分類标簽的各水準資訊熵與其機率積的和。
for level in levels: # 循環計算不同水準的資訊熵
level_data = dataSet[dataSet[label] == level] # 擷取該水準的資料集
prob = level_data.shape[0] / dataSet.shape[0] # 計算該水準的資料集在總資料集的占比
# 計算香農熵，并更新到label_entropy中
label_entropy += prob * self._entropy(level_data) # _entropy用于計算香農熵
# 計算資訊增益
info_gain = init_entropy - label_entropy # 代碼至此，已經能夠循環計算每個分類标簽的資訊增益
# 用best_info_gain來取info_gain的最大值，并擷取對應的分類标簽
if info_gain > best_info_gain:
best_info_gain = info_gain
best_label = label
# 這裡儲存一下每一次計算的資訊增益，便于檢視和檢查錯誤
# Python 字典 setdefault() 函數和 get()方法類似, 如果鍵不存在于字典中，将會添加鍵并将值設為預設值。
self.gain.setdefault(self.__count, {}) # 建立本次函數調用時的字段，設其value為字典
self.gain[self.__count][label] = info_gain # 把本次函數調用時計算的各個标簽資料存到字典裡
self.__count += 1
return best_label
def _top_amount_level(self, target_list):
"""傳回數量最多的水準"""
class_count = target_list.value_counts().to_dict() # 計算靶标簽的不同水準的樣本量，并轉化為字典
# 字典的items方法可以将鍵值對轉成[(), (), ...]，可以使用清單方法
sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True) # 将字典中各水準按數量降序排列
return sorted_class_count[0][0] # 傳回最大數量的水準
def mktree(self, dataSet):
"""建立決策樹"""
target_list = dataSet.iloc[:, -1] # target_list 靶标簽的那一列資料
# 程式終止條件一: 靶标簽(資料集的最後一列因變量)在該資料集上隻有一個水準，傳回該水準
if target_list.unique().shape[0] <= 1:
return target_list[0] # ！！！
# 程式終止條件二: 資料集隻剩下靶标簽這一列資料；傳回數量最多的水準
if dataSet.shape[1] == 1:
return self._top_amount_level(target_list)
# 不滿足終止條件時，做如下遞歸處理
# 1.選擇最佳分類标簽
best_label = self._best_split(dataSet)
# 2.遞歸計算最佳分類标簽的不同水準的子資料集的資訊增益
# 各個子資料集的最佳分類标簽的不同水準...
# ...
# 直至遞歸結束
best_label_levels = dataSet[best_label].unique().tolist() # 傳回best_label列中的所有水準值
tree = {best_label: {}} # 生成字典，用于儲存樹狀分類資訊；這裡不能用self.tree = {}存儲
for level in best_label_levels:
level_subdata = self._split_dataSet(dataSet, best_label, level) # 擷取該水準的子資料集
tree[best_label][level] = self.mktree(level_subdata) # 傳回結果
return tree
def predict(self, tree, labels, test_sample):
"""
對單個樣本進行分類
tree: 訓練的字典
labels: 除去最後一列的其它字段
test_sample: 需要分類的一行記錄資料
"""
firstStr = list(tree.keys())[0] # tree字典裡找到第一個用于分類鍵值對
secondDict = tree[firstStr] # 第一個分類之後的字典存起來
featIndex = labels.index(firstStr) # 找到第一個分類的索引
for key in secondDict.keys():
if test_sample[featIndex] == key: # 找到test_sample在目前分類下的值
if secondDict[key].__class__.__name__ == "dict": # 後面仍為字典類型，即仍需分類
classLabel = self.predict(secondDict[key], labels, test_sample) # 繼續分類
else: # 否則就直接傳回該處的yes/no
classLabel = secondDict[key]
return classLabel
def _unit_test(self):
divide_data()
self.tree = self.mktree(self.dataSet) # 到此行，用于測試主程式mktree
labels = ["age", "income", "student", "reputation"]
test_data = pd.read_csv("./test_ID3data.txt", sep="\t", header=None)
target_list = (test_data.iloc[:, -1]).values.tolist() # 擷取靶标簽
test_list = (test_data.iloc[:, [0, 1, 2, 3]]).values.tolist() # 擷取其他四列資料
sum = 0
right = 0
for test_sample in test_list:
outcome = self.predict(self.tree, labels, test_sample) # 預測分類
if outcome == target_list[sum]:
right = right+1
sum = sum + 1
accuracy_rate = right/sum
print("模型準确率：", accuracy_rate)
model = ID3Tree()
model._unit_test()
print(json.dumps(model.gain, indent=" ")) # 可以檢視每次遞歸時的資訊熵
print(json.dumps(model.tree, indent=" ")) # 檢視樹
資料集介紹
代碼中使用的資料是一張包含使用者資訊和購買決策的表，來源于網絡。對于第0條和第7條資料，唯一的差別是income不同，于是可以認為，此時income不具有參考價值，而應考察student值或reputation的資訊，這也是為什麼生成的樹中不包含income這一節點。這張表已經對1024個樣本進行了分組統計，具體資料如下：
| — | count | age | income | student | reputation | purchase |
|---|---|---|---|---|---|---|
| 64 | 青年 | 高 | 否 | 良 | 不買 | |
| 1 | 64 | 青年 | 高 | 否 | 優 | 不買 |
| 2 | 128 | 中年 | 高 | 否 | 良 | 買 |
| 3 | 60 | 老年 | 中 | 否 | 良 | 買 |
| 4 | 64 | 老年 | 低 | 是 | 良 | 買 |
| 5 | 64 | 老年 | 低 | 是 | 優 | 不買 |
| 6 | 64 | 中年 | 低 | 是 | 優 | 買 |
| 7 | 128 | 青年 | 中 | 否 | 良 | 不買 |
| 8 | 64 | 青年 | 低 | 是 | 良 | 買 |
| 9 | 132 | 老年 | 中 | 是 | 良 | 買 |
| 10 | 64 | 青年 | 中 | 是 | 優 | 買 |
| 11 | 32 | 中年 | 中 | 否 | 優 | 買 |
| 12 | 32 | 中年 | 高 | 是 | 良 | 買 |
| 13 | 64 | 老年 | 中 | 否 | 優 | 不買 |
訓練資料和測試資料劃分
使用sklearn.model_selection.train_test_split來随機劃分訓練集和測試集，在本次實驗中，将購買決策資訊表的資料按7:3的比例劃分為訓練集和測試集。使用訓練集進行模型的訓練，測試集用于測試模型的準确性。
divideData.py檔案具體代碼如下：
import numpy as np
from sklearn.model_selection import train_test_split
import random
def divide_data():
my_matrix = np.loadtxt(open("ID3data.txt"),dtype=str,delimiter="\t")
X, y = my_matrix[:,:-1],my_matrix[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=int(random.random()*100))
train= np.column_stack((X_train,y_train))
np.savetxt('train_ID3data.txt', train, fmt='%s', delimiter='\t')
test = np.column_stack((X_test, y_test))
np.savetxt('test_ID3data.txt', test, fmt='%s', delimiter='\t')
print("訓練集與資料集劃分完成，比例為7:3！")
結果分析
分類準确率及決策樹
經過多次測試，在不同訓練集和測試集下建構多個決策樹，并計算出準确率（在第十次測試時修改測試集的一個屬性的标簽），結果如下：
| 測試序号 | 準确率 |
|---|---|
| 1 | 1.0 |
| 2 | 1.0 |
| 3 | 1.0 |
| 4 | 1.0 |
| 5 | 1.0 |
| 6 | 1.0 |
| 7 | 1.0 |
| 8 | 1.0 |
| 9 | 1.0 |
| 10 | 0.9968 |
分類結果準确率
第6次測試遞歸的資訊熵
生成的決策樹
由結果分析可知，ID3算法充分發揮了資訊增益的優點，使建構的決策樹最小，僅有三層，同時準确率非常高，這也與資料的完整和無噪聲密切相關。但是也存在着缺陷，比如該模型處理大量缺失值的資料時會報錯。
優點和缺點
優點：算法簡單，核心是根據“最大資訊熵增益”原則選擇劃分目前資料集的最好特征。
缺點：隻能處理離散型屬性，并且傾向于選擇取值較多的屬性。因為資訊增益反映的給定一個條件以後不确定性減少的程度，必然是分得越細的資料集确定性更高，也就是條件熵越小，資訊增益越大。
改進的算法：
C4.5算法
C4.5算法流程與ID3相類似，隻不過将資訊增益改為資訊增益比，以解決偏向取值較多的屬性的問題，另外它可以處理連續型屬性。
資訊增益率：
其中IV(a)的計算方式如下：
CART算法
相比ID3和C4.5，CART應用要多一些，既可以用于分類也可以用于回歸。CART分類時，使用基尼指數（Gini）來選擇最好的資料分割特征，Gini描述的是純度，與資訊熵的含義相似。Gini指數越小表示集合中被選中的樣本被分錯的機率越小，也就是說集合的純度越高，反之，集合越不純。
對于給定的樣本集合D，其基尼指數為：
如果樣本集合D根據特征A是否取某一可能值a被分為兩部分，則在特征A的條件下，集合D的基尼指數定義為：