私は大学の試験のためにID3 アルゴリズムを研究していますが、ルートに少ない属性を持つ新しいサブツリーを作成するために最適な属性を選択する方法を理解するのにいくつか問題があります(葉の作成に到達するまで)
そこで、先生の講義ノートにある実用的な例を紹介します。誰かが私の疑問を解決するための実用的な助けを提供してくれることを願っています.
これは、私が構築する最終的な意思決定ツリーです。
この決定木は、レストランにいるときに待つ必要があるかどうかを単純に示しています。ですから、たとえば、多くの常連客がいて( patons 属性 = many )、彼らがお腹を空かせていて( hungry 属性 = yes )、料理の種類がフランス料理( type 属性 = French )の場合、私は待つということになります)。代わりに、パトロンがいない場合(パトロン属性 = no )、待つ必要はないとすぐに結論付けることができます。
わかりましたので、決定木を使用するのは非常に簡単です。
これは、決定木の前の例のドメインを表す表です(さらにいくつかの属性がありますが、これはそれほど重要ではないと思います)。
したがって、間違ったことを言ったら訂正してください。この表は、一般的なケースを示す12 の例を示しており、ID3 アルゴリズムが決定木を構築するために使用されます。
これは ID3 アルゴリズムの疑似コードです。
ID3 (Examples, Target_Attribute, Attributes)
Create a root node for the tree
If all examples are positive, Return the single-node tree Root, with label = +.
If all examples are negative, Return the single-node tree Root, with label = -.
If number of predicting attributes is empty, then Return the single node tree Root,
with label = most common value of the target attribute in the examples.
Otherwise Begin
A ← The Attribute that best classifies examples.
Decision Tree attribute for Root = A.
For each possible value, v_i, of A,
Add a new tree branch below Root, corresponding to the test A = v_i.
Let Examples(v_i) be the subset of examples that have the value v_i for A
If Examples(v_i) is empty
Then below this new branch add a leaf node with label = most common target value in the examples
Else below this new branch add the subtree ID3 (Examples(v_i), Target_Attribute, Attributes – {A})
End
Return Root
したがって、このアルゴリズムはルート ノードの作成から始まります。このノードには、前の表で提供されたすべての例を、イベントを分類するクラスに従って分けて配置します。
したがって、この場合、前の 12 の例を次の 2 つのクラスにのみ分けます:肯定的な例(状況に関連する:私はレストランで待つ) と否定的な例(状況に関連する: 私はレストランで待たない)レストラン）
したがって、前の表を見ると、決定木のルート ノードには次のような状況があります。
+: X1、X3、X4、X6、X8、X12 (正の例)
-: X2、X5、X7、X9、10、X11 (負の例)
これらの例に関連する属性は、前の表にあるものです: Fri、Hun、Pat、Price、Rain、Res、Type、Est
すべてを使用せずに目標 (結論) に到達するため、これらの属性が決定木ですべて使用されているわけではありません。
ここで、例を正のケースと負のケースに分けて、最初に最適な属性を選択する必要があります(これは、以前のすべての属性の中でより関連性が高い)。
実際には、次の最初のステップを実行する必要があります。
彼は、この最初の分岐ステップの最良の属性として常連客属性を選択しました。
この属性は、次の値を持つことができます:なし(レストランに常連客がいない)、一部(常連客がほとんどいない)、満員(レストランは常連客でいっぱい)、したがって、3 つのサブツリーに分岐する必要があります (そして、これらのツリーの関連するルート ノード ラベル 関連するケース)
私の問題は次のとおりです。最適なノードを選択するにはどうすればよいですか?
Entropy値を使用する必要があることはわかっています。
これは、すべての属性の情報取得を計算するために使用されます。
そして、すべての属性に対してそれを行った後、情報獲得の価値が高い属性を最良の属性として選択する必要があります
しかし、前の例でこのことを行うにはいくつかの問題が見つかりました。パトロン属性を最初に最適な属性として選択した具体的なケースにこれらの式を適用する方法を教えてくれる人がいますか?
Tnxそんなに
アンドレア