見出し画像

🎭決定木におけるエントロピーは「不純度」または「不確実性」の度合いを表します。



Id3アルゴリズムはその純度をあげるわけですか?


はい、ID3アルゴリズムは各分割で情報利得を最大化することにより、純度(エントロピーの低減)を高めることを目指します。これにより、データをより良く分類できるように決定木を構築していきます。



利得の最大化の式が上記の式ですか?

はい、上記の式は利得(Gain)の最大化を表しています。この式により、分割によるエントロピーの減少量、つまり情報利得が計算され、ID3アルゴリズムはこの情報利得が最大となる属性によってデータを分割していきます。

擬似的なコードではif文の値の比較で決定木は作れると思いますが、この比較部分に利得関数におきかえればid3になりますか?


はい、そのとおりです。擬似コードにおけるif文での値の比較を行う部分に、情報利得を計算して最大化するロジックを組み込むことで、ID3アルゴリズムが実装されます。各ノードで分割を決める際に、全ての属性について情報利得を計算し、最も情報利得が大きくなる属性を選択してその属性によってデータを分割します。これをデータが完全に分類されるか、あるいは他の停止条件を満たすまで再帰的に繰り返します

以下はID3アルゴリズムのPython擬似コードの例です。このコードは実際には実行不可能ですが、ID3アルゴリズムの基本的な流れを説明するためのものです。

def calculate_entropy(data):
    # データセットのエントロピーを計算する関数
    pass

def calculate_information_gain(data, attribute, entropy):
    # 属性による情報利得を計算する関数
    pass

def id3(data, original_data, features, target_attribute_name, parent_node_class=None):
    """
    ID3アルゴリズムの実装。
    data: 現在のデータセット(分割される)
    original_data: もとのデータセット
    features: 属性のリスト
    target_attribute_name: 目標となる属性名
    parent_node_class: 親ノードのクラス
    """
    # 停止条件のチェック
    if len(data) == 0:
        return parent_node_class
    elif len(data[target_attribute_name].unique()) == 1:
        return data[target_attribute_name].iloc[0]
    elif len(features) == 0:
        return original_data[target_attribute_name].mode()[0]
    else:
        # 親ノードのクラス値をセット
        parent_node_class = original_data[target_attribute_name].mode()[0]

        # エントロピーを計算
        entropy = calculate_entropy(data)

        # すべての属性に対して情報利得を計算
        information_gains = {}
        for feature in features:
            information_gains[feature] = calculate_information_gain(data, feature, entropy)

        # 最大の情報利得を持つ属性を選択
        best_feature = max(information_gains, key=information_gains.get)

        # ツリー構造を生成
        tree = {best_feature: {}}

        # 最良の属性で分割
        for value in data[best_feature].unique():
            sub_data = data.where(data[best_feature] == value).dropna()
            subtree = id3(sub_data, original_data, [feat for feat in features if feat != best_feature], 
                          target_attribute_name, parent_node_class)
            tree[best_feature][value] = subtree

        return tree

Cartアルゴリズムもc4.5も、基本はid3と同じ考え方ですか?

はい、CART(Classification and Regression Trees)アルゴリズムとC4.5は、基本的にID3アルゴリズムの考え方を拡張したものです。

  • CART は、二分木を構築し、分類問題だけでなく回帰問題にも使用できます。CARTはGini不純度という別の尺度を使用して分割を決定し、また枝刈りを通じて過学習を防ぐ手法を取り入れています。

  • C4.5 はID3の直接の後継で、多くの改良が加えられています。例えば、連続値属性の扱い、欠損値の扱い、枝刈りの導入、情報利得ではなく正規化情報利得(ゲインレシオ)を使用する点などがあります。

両方とも、決定木を構築する際の基本的なステップはID3と同じで、最適な分割を見つけるために特定の基準を使用して、各ノードでデータセットを分割していきます。しかし、その分割を決定するための基準や、木の構築後の処理において、それぞれ独自の改良が加えられています。

どちらも、利得や純度という考えにおいて分類をこなすという事ですね?

はい、正確にはその通りです。CARTもC4.5も、ID3と同様にデータを分類する際には利得や純度の概念を利用していますが、それぞれ異なる基準や方法を使用して最良の分割を見つけ出します。CARTはGini不純度を、C4.5は情報利得率(ゲインレシオ)を使って、それぞれのアルゴリズムが最も情報価値の高い属性によってデータセットを分割するように設計されています。


お願い致します