決定木-C 4.5

C4.5アルゴリズムはQuinlanによって1993年に提案され、コア部分はID 3アルゴリズムと似ており、ID 3アルゴリズムに基づいて改造されただけである--特徴選択過程で情報利得比を選択基準としている.
【具体的な方法】:

ルートノード(root node)から出発し、ノードに対してすべての可能な特徴の情報利得比を計算し、情報利得比が最大の特徴をノードの特徴として選択し、この特徴の異なる値からサブノードを確立する.

はさらにサブノードに対して以上の方法を再帰的に呼び出し、決定ツリーを構築する.すべてのフィーチャーの情報利得が小さいか、フィーチャーが選択できないまで.

は最後に決定ツリーを得た.

【アルゴリズム】:C 4.5アルゴリズムを生成します.

入力:トレーニングデータセットD、フィーチャーセットA、しきい値e.

出力:決定ツリーT.

プロセス:

Dのすべてのインスタンスが同じクラスC k Cに属している場合k Ck、Tを単一ノードツリーとし、C k C_k Ckはこのノードのクラスとして、Tを返す.

A=∅A=emptyset A=∅の場合、Tを単一ノードツリーとし、Dのインスタンス数が最も大きいクラスC k C_k Ckはこのノードのクラスとして、Tを返す.

それ以外の場合、情報ゲイン比式に従ってAにおける各特徴対Dの情報ゲイン比を算出し、情報ゲイン比が最大となる特徴A g A_を選択するg Ag​;

A g A_g Agの情報利得比が閾値eより小さい場合、Tを単一ノードツリーとし、D中のインスタンス数が最大のクラスC k C_k Ckはこのノードのクラスとして、Tを返す.

そうでなければ、A g A_g Agの各可能値a i a_i ai,依A g=a i A_g = a_i Ag=ai Dをいくつかの非空子セットD i D_に分割するi Di,D i D_i Diの中で実例数が最も大きいクラスをタグとして、サブノードを構築し、ノードとそのサブノードからツリーTを構成し、Tを返す.

対のノードi、D i D_i Diはトレーニングセットであり、A−A g A−{A_g}A−Agを特徴セットとし、(1)~(5)ステップを再帰的に呼び出し、サブツリーT i T_を得るi Ti,T i T_を返すi Ti​.

情報エントロピー、情報ゲイン、および情報ゲイン比については、ブログモデル選択-決定ツリーを参照してください.
【情報エントロピー計算式】E n t(D)＝Σi＝i k−∣Y i∣Y∣l o g 2∣Y i∣Y∣Ent(D)＝sum＿{i=i}^{k}-\frac{|Y_i|}{|Y|}log_2frac{|Y_i|}{|Y|}Ent(D)=i=iΣk−∣Y∣Yi∣log 2∣Y∣Yi∣のうち、|Y|は現在のデータセットDのラベル数、kはデータセットDのラベル種類数を表す.例えば、現在5つのサンプルがあり、各サンプルの分類は1、0、1、2、0であり、|Y|=5、k=3である.∣ Y i ∣ |Y_i|∣Yi∣は、指定されたラベル種別のラベル数、例えばY 0 Y_を示す0 Y 0がラベル種別0に対応すると、∣Y 0∣=2|Y_0|=2∣Y 0∣=2,同理可得∣Y 1∣=2,∣Y 2∣=1|Y_1| = 2, |Y_2|= 1 ∣Y1​∣=2,∣Y2​∣=1.
【情報利得計算式】:G a i n(D,a)=Σi=1∣a∣D i∣D∣E n t(D i)Gain(D,a)=sum_{i=1}^{|a|}frac{|D_i|}{|D|}Ent(D_i)Gain(D,a)=1ΣaD i D_i Diは、指定された特徴値に基づいて分割されたデータセット、∣D i∣|D_を表すi|∣Di∣は、そのデータセットのサンプル数を示す.
【情報利得比計算式】:I V(a)=Σi=1∣a∣−∣D i∣D∣l o g 2∣D i∣D∣G a i n r a t i o(D,a)=G a i n(D,a)I V(a)IV(a)=sum_{i=1}^{|a|}-\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}\\Gain_{ratio}(D, a) =\frac{Gain(D, a)}{IV(a)} IV(a)=i=1∑∣a∣​−∣D∣∣Di​∣​log2​∣D∣∣Di​∣​Gainratio​(D,a)=IV(a)Gain(D,a)​
コード実装
C4.5アルゴリズムはID 3アルゴリズムと同じで、離散型データ及び分類タスクの処理にしか使用できないので、sklearnを選択する.Datasetsのirisアヤメデータセット.

import numpy as np
from sklearn.datasets import load_iris


dataset = load_iris()
x = dataset.data
y = dataset.target
features = dataset.feature_names

決定ツリーのノード構造コード:

class Node:
    
    def __init__(self, value, type='decision'):
        self.value = value    
        self.type = type
        self.children = {}

calc_shannon_ent()
calc_shannon_ent情報利得計算関数で、2つのパラメータdataとlabelsを受け入れる.

data:データセット

labels:ラベルセット

まず,データセットの個数と特徴数,および分類の個数を取得する.

data_count = float(data.shape[0])
features = data.shape[1]
labels_count = np.array([labels[labels == label].size for label in set(labels)])

注意:labels_count/data_countの結果は,元のデータセットの各分類の確率である.
次に、元のデータセットの情報エントロピーを算出し、区分を格納した各特徴情報ゲイン比情報のリストgain_を作成するlist.

base_ent = -np.sum((labels_count / data_count) * np.log2(labels_count / data_count))
gain_list = []

そして、各特徴区分されたデータセットの情報エントロピー及びその特徴対応IVを計算する.

for feature in range(0, features):
    #          
    feature_data = data[:, feature]
    #       ，      key，        value
    feature_info = {feature: feature_data[feature_data == feature].size for feature in set(feature_data)}
    feature_shannonEnt, IV = 0, 0
    
    #                     
    for feature_value in feature_info:
        #         
        feature_count = float(feature_info[feature_value])
        label_data = labels[feature_data == feature_value]
        labels_feature = np.array([label_data[label_data == label].size for label in set(label_data)])
        #          
        p_label = labels_feature / feature_count
        feature_shannonEnt += (feature_count / data_count) * np.sum(-p_label * np.log2(p_label))
        #    IV
        IV += (feature_count / data_count) * np.log2(feature_count / data_count)
    #                  gain_list    
    gain_list.append((base_ent - feature_shannonEnt) / IV)

最後に、情報利得比が最も大きいフィーチャーの下付きスケールを返します.

gain_list = np.array(gain_list)
return np.argmax(gain_list)

【完全コード】:

def calc_shannon_ent(data, labels):
    data_count = float(data.shape[0])
    features = data.shape[1]
    #          
    labels_count = np.array([labels[labels == label].size for label in set(labels)])
    #          
    base_ent = -np.sum((labels_count / data_count) * np.log2(labels_count / data_count))
    #             
    gain_list = []
    
    #                  
    for feature in range(0, features):
        #          
        feature_data = data[:, feature]
        #       ，      key，        value
        feature_info = {feature: feature_data[feature_data == feature].size for feature in set(feature_data)}
        feature_shannonEnt, IV = 0, 0
        #                     
        for feature_value in feature_info:
            #         
            feature_count = float(feature_info[feature_value])
            label_data = labels[feature_data == feature_value]
            labels_feature = np.array([label_data[label_data == label].size for label in set(label_data)])
            #          
            p_label = labels_feature / feature_count
            feature_shannonEnt += (feature_count / data_count) * np.sum(-p_label * np.log2(p_label))
            #    IV
            IV += (feature_count / data_count) * np.log2(feature_count / data_count)
        #                  gain_list    
        gain_list.append((base_ent - feature_shannonEnt) / IV)
    gain_list = np.array(gain_list)
    return np.argmax(gain_list)

split_dataset()
split_Dataset()メソッドは、4つのパラメータを受け入れるフィーチャー値とフィーチャー値に基づいてデータセットを分割します.

data:データセット

labels:ラベルリスト

feature:フィーチャー

value:フィーチャー値

split_Dataset()は、分割されたデータセットとラベルセットを含むメタグループを返します.
【完全コード】:

def split_dataset(data, labels, feature, value):
    """
    :param data:        ndarray
    :param labels:       ndarray
    :param feature:    
    :param value:      
    :return: 
    """
    feature_data = data[:, feature]
    select_rows = feature_data == value
    return (np.delete(data[select_rows], feature, axis=1), labels[select_rows])

voting_label()
voting_Label()投票関数は,葉結点の分類結果を決定するために用いられる.このメソッドは、1つのパラメータlabels、ラベルセットのみを受け入れます.
【完全コード】:

def voting_label(labels):
    return sorted([(label, len(labels[label == label])) for label in set(labels)])[-1][1]

create_tree()
create_tree()は、3つのパラメータを受け入れる決定ツリー関数を再帰的に作成します.

data:データ

labels:ラベルセット

features:フィーチャーセット

まず,特徴セットが存在するか否かを判断し,存在しなければ現在のノードをリーフノードとする.

if len(features) == 0:
    return Node(voting_label(labels))

そして,ラベルセットを判断し,1つのラベルのみであれば現在のノードをリーフノードとする.

if len(set(labels)) == 1:
    return Node(labels[0])

次に、calc_を呼び出すshannon_ent()メソッドは,最適特徴の下付き文字を取得し,下付き文字に基づいて最適特徴を得る.

best_feature_index = calc_shannon_ent(data, labels)
best_feature = features[best_feature_index]

ステップ4では、ノードを作成し、分割されたフィーチャーをフィーチャーセットから削除します.

node = Node(best_feature)
features = np.delete(features, best_feature_index)

第5のステップでは、最適な特徴に基づいてデータセットを分割します.

best_feature_data = data[:, best_feature_index]
best_feature_info = {feature: best_feature_data[best_feature_data == feature].size for feature in set(best_feature_data)}

注意:best_feature_infoは、各特徴値に対応するデータセットを含む辞書です.
ステップ6では、各特徴値に対応するデータセットに基づいてcreate_を再帰的に呼び出すtree()メソッドを使用して、サブノードを作成します.

for feature_value in best_feature_info:
    split_data, split_labels = split_dataset(data, labels, best_feature_index, feature_value)
    node.children[feature_value] = create_tree(split_data, split_labels, features)

最後に、ルートノードを返します.

return node

【完全コード】:

def create_tree(data, labels, features):
    #   ：       ，     ，          
    if len(features) == 0:
        return Node(voting_label(labels))
    #   ：   ，       ，          
    if len(set(labels)) == 1:
        return Node(labels[0])
    #          
    best_feature_index = calc_shannon_ent(data, labels)
    best_feature = features[best_feature_index]    
    #     
    node = Node(best_feature)
    #               
    features = np.delete(features, best_feature_index)
    #            
    best_feature_data = data[:, best_feature_index]
    best_feature_info = {feature: best_feature_data[best_feature_data == feature].size for feature in set(best_feature_data)}
    for feature_value in best_feature_info:
        split_data, split_labels = split_dataset(data, labels, best_feature_index, feature_value)
        node.children[feature_value] = create_tree(split_data, split_labels, features)
    return node

【create_tree()関数の呼び出し】

root = create_tree(x, y, list(range(x.shape[1])))
print(root.value) #    1

ID 3アルゴリズムの出力結果を比較すると,ルートノードの特徴が変化することが分かった.すなわち,異なる特徴選択基準に基づいて,決定ツリー内部ノードの特徴もそれに応じて変化する.
完全なコードおよび呼び出しプロセスは、転送ゲートから取得できます.
リファレンス

《統計学習方法》李航

『機械学習』周志華