序文 最近、欲張りになりすぎないように、機械学習の基本的なアルゴリズムを体系的に勉強しようと思っています。印象を深めるために、よく使われる基本的な機械学習アルゴリズムをすべて実装してみることにしました。この記事は、決定木のアルゴリズム実装に関するブログ シリーズの最初の記事です。この記事では、決定木に関係するアルゴリズムの概要を説明し、関連する独自の実装コードを添付します。対応するモデルのトレーニングに使用されるすべてのアルゴリズム コードとデータは、GitHub (https://github.com/PytLab/MLBox) に配置されます。 この記事では、MLiA コンタクト レンズ処方データセットを段階的に調べて決定木を構築し、Graphviz を使用して決定木を視覚化します。 文章 決定木学習 決定木学習は、データの属性に基づいてツリー構造を使用して確立された決定モデルです。このモデルは、分類および回帰の問題を解決するために使用できます。一般的なアルゴリズムには、CART (分類と回帰ツリー)、ID3、C4.5 などがあります。私たちは、データセットに基づいて決定木を構築することがよくあります。その重要なタスクの 1 つは、データに含まれる知識情報から一連のルールを抽出することです。これらのルール、つまりツリー構造を作成するプロセスが、機械学習のプロセスです。 決定木の構造 コンピュータを購入するかどうかを予測するための次の簡単な決定木を例に挙げます。ツリー内の内部ノードは特定の属性を表し、ノードから伸びるブランチはこの属性のすべての可能な値を表し、リーフノードは最終的な判断結果、つまりタイプを表します。 Graphviz、matplotlib アノテーションなどの視覚化ツールの助けを借りて、私たちが作成した決定木モデルを視覚化し、人々が直接理解することができます。これは、ベイジアンニューラルネットワークなどのアルゴリズムにはない機能です。 決定木アルゴリズム 決定木アルゴリズムは、主に決定木の作成中に木を分割(データセットを分割)する際に最適な特徴を選択するアルゴリズムを指します。その主な目的は、分離されたデータセットをできるだけ規則的、つまりできるだけ純粋にできる特徴を選択することです。最大の原則は、無秩序なデータをより秩序立てることです。 よく使われる 3 つの方法を以下に示します。 情報獲得 これには、情報理論のいくつかの概念が含まれます。イベントの情報量、情報エントロピー、情報ゲインなどです。イベント情報の一般的な説明については、Zhihuの回答を参照してください。 - イベントに関する情報量 i: このイベントが発生する確率の負の対数
- 情報エントロピーとは、ある出来事から平均的に得られる情報量、つまり情報量の期待値です。
任意のシーケンスの情報エントロピーを取得できます。つまり、シーケンスを分類した後に各タイプの確率をカウントし、上記の式を使用して計算します。Python を使用した実装は次のとおりです。 - get_shanno_entropy(self,値) を定義します。
-
- '' ' 指定されたリスト内の値のShannoエントロピーを計算します
-
- '' '
-
- uniq_vals = set (値)
-
- val_nums = {キー:値.count (キー)の 鍵 uniq_vals内}
-
- probs = [v/len(値) 、k、v、 val_nums.items()の場合]
-
- エントロピー = sum ([-prob*log2(prob) for prob in probs])
-
- エントロピーを返す
情報獲得 データセットを分割すると、データの情報エントロピーが変化します。情報エントロピー計算式を使用して、分割されたサブデータセットのそれぞれの情報エントロピーを計算し、その平均値(期待値)を分割データセットの情報エントロピーとして計算することができます。分割されていないデータの情報エントロピーと比較した新しい情報エントロピーの減少が情報ゲインです。私は最初これを誤解していたため、私が書いたコードでは正しい決定木を作成できませんでした。 データセット D を k 個の部分 D1、D2、…、Dk に分割すると、分割後の情報エントロピーは次のようになります。 情報ゲインは、2 つの情報エントロピーの差です。 ここでは主に属性選択に情報ゲインを使用します。具体的な実装コードは次のとおりです。 - def choose_best_split_feature(自分自身、データセット、クラス):
-
- '' ' 情報利得に基づいてデータを分割するための最適な特徴を決定する
-
-
-
- :param dataset: 分割するデータセット
-
- :param classes: データセットの種類
-
-
-
- :戻り値: データの分割で最大の利益が得られる属性インデックス
-
- '' '
-
- base_entropy = self.get_shanno_entropy(クラス)
-
-
-
- feat_num = len(データセット[0])
-
- エントロピーゲイン = []
-
- iが範囲内(feat_num)の場合:
-
- splited_dict = self.split_dataset(データセット、クラス、i)
-
- 新しいエントロピー =合計([
-
- len(サブクラス)/len(クラス)*self.get_shanno_entropy(サブクラス)
-
- splited_dict.items()内の_、(_、sub_classes)の場合
-
- ])
-
- entropy_gains.append(基本エントロピー - 新しいエントロピー)
-
-
-
- entropy_gains.index ( max ( entropy_gains))を返します。
ゲイン比 ゲイン比は情報ゲイン法の拡張であり、情報ゲインによって引き起こされる弱い一般化の欠陥を克服するために設計されています。情報ゲイン選択によれば、より多くのブランチを持つ属性を常に選択する傾向があり、これにより各サブセットの情報エントロピーが最小化されるからです。たとえば、各データに固有の ID 値機能が追加されると、この ID 値による分類によって最大の情報ゲインが得られ、各サブセットの情報エントロピーは 0 になります。ただし、このような分類は意味がなく、一般化能力がなく、オーバーフィッティングに似ています。 したがって、分割情報、つまりゲイン比を導入することで、データ分割を測定するためのより適切な基準を見つけることができます。 情報を分割する式は次のように表されます。 もちろん、SplitInfo が 0 に近づくこともあり、その場合、ゲイン比が非常に大きくなり、信頼性がなくなるため、分母にスムージング関数を追加する必要がある場合があります。詳細については、参考セクションに記載されている記事を参照してください。 ジニ不純度 ジニ不純度の定義: ここで、m はデータ セット D 内のカテゴリの数を表し、pi は特定のタイプが出現する確率を表します。種類が 1 つの場合、ジニ不純度の値は 0 となり、このとき不純度が最も低くなることがわかります。 k 個のサブデータセットに分割されたデータセットのジニ不純度は、次のように計算できます。 これにより、不純度の変化に応じて最適なツリー分割属性を選択することができます。 ツリー分割 最適な分割属性を選択するアルゴリズムを使用して、選択した属性に基づいてツリーをさらに分割する必要があります。いわゆるツリー分割とは、選択された属性に従ってデータセットを分割し、分割されたデータセット全体で属性選択メソッドを再度呼び出して、サブデータセットの中央の属性を選択することです。これを実装する最良の方法は再帰です。 決定木を表現するためにどのようなデータ構造を使用するかについては、Python では辞書を使用して入れ子になった決定木を便利に表現できます。ツリーのルート ノードは属性であり、属性に対応する値は新しい辞書です。キーは属性の可能な値であり、値は新しいサブツリーです。 Python を使用してデータ セットに基づいて決定木を作成する方法は次のとおりです。 - def create_tree(self, データセット, クラス, feat_names):
-
- '' ' 現在のデータセットに基づいて決定木を再帰的に作成します
-
-
-
- :param データセット: データセット
-
- :param feat_names: データセット内のデータに対応する特徴名
-
- :param クラス: データセット内の対応するデータの種類
-
-
-
- :param tree: 決定木を辞書形式で返します
-
- '' '
-
- # データセットにタイプが 1 つしかない場合はツリー分割を停止します
-
- len( set (classes)) == 1の場合:
-
- 戻りクラス[0]
-
-
-
- # すべての特徴が走査された場合、最も高い割合を持つタイプを返します
-
- len(feat_names) == 0の場合:
-
- get_majority(クラス)を返す
-
-
-
- # 分割して新しいサブツリーを作成する
-
- ツリー = {}
-
- best_feat_idx = self.choose_best_split_feature(データセット、クラス)
-
- 特徴 = 特技名[ベスト特技ID]
-
- ツリー[機能] = {}
-
-
-
- # 再帰的にサブツリーを作成するためのサブデータセットを作成する
-
- sub_feat_names = feat_names[:]
-
- サブフィーチャ名.pop(ベストフィーチャidx)
-
-
-
- splited_dict = self.split_dataset(データセット、クラス、best_feat_idx)
-
- splited_dict.items()内のfeat_val、(sub_dataset、sub_classes)の場合:
-
- tree[feature][feat_val] = self.create_tree(sub_dataset,
-
- サブクラス、
-
- サブフィーチャ名)
-
- self.tree = ツリー
-
- self.feat_names = feat_names
-
-
-
- リターンツリー
ツリー分割には 2 つの終了条件があります。 ツリーが分割されると、データセット内のデータベクトルの長さが常に短くなることがわかります。 0 に短縮されると、データセットのすべての属性が使い果たされ、分割できなくなることを意味します。 このとき、最終的なサブデータセットの大部分を最終的な分類結果として選択し、リーフノードに配置します。 - もう 1 つは、新しく分割されたデータセットには 1 つのタイプしかないことです。
ノードによって指し示されるデータ セットがすべて同じタイプである場合、属性がまだ走査されていない場合でも、それらをさらに分割する必要はありません。 意思決定ツリーを構築する 私は、MLiA ブックに含まれるコンタクト レンズ データを使用して、決定木を生成しました。データには、患者の目の状態と医師が推奨するコンタクト レンズの種類が含まれていました。 まず、データをインポートし、決定木を生成するためのトレーニングデータと同じタイプのデータ特徴を分離します。 - ツリーからDecisionTreeClassifierをインポートする
-
-
-
- lense_labels = [ '年齢' 、 '処方箋' 、 '乱視' 、 '涙液量' ]
-
- バツ = []
-
- Y = []
-
-
-
- と ' lenses.txt' 、 'r' )をf:として開きます。
-
- fの行の場合:
-
- comps = line.strip().split( '\t' )
-
- X.append(comps[: -1])
-
- Y.append(comps[-1])
決定木を生成します。 - clf = 決定木分類器()
-
- clf.create_tree(X, Y, レンズラベル)
生成された決定木を表示します。 - [2]: clf.tree内
-
- アウト[2]:
-
- { '涙量' : { '正常' : { '乱視' : { 'なし' : { '年齢' : { '前' : 'ソフト' ,
-
- '老眼' : { '処方箋' : { 'ハイパー' : 'ソフト' , '近視' : 'レンズなし' }},
-
- 「若い」 : 「柔らかい」 }},
-
- 'はい' : { '処方箋' : { 'ハイパー' : { '年齢' : { 'プレ' : 'レンズなし' ,
-
- 「老眼」 : 「レンズなし」 、
-
- 「若い」 : 「ハード」 }},
-
- 「近視」 : 「難しい」 }}}},
-
- 「縮小」 : 「レンズなし」 }}
決定木の視覚化 ネストされた辞書を通して決定木を直接理解することは困難です。ツリー構造を視覚化するには、視覚化ツールを使用する必要があります。ここでは、Graphviz を使用してツリー構造を視覚化します。この目的のために、辞書で表されるツリーから Graphviz Dot ファイルの内容を生成する関数が実装されています。基本的な考え方は、ツリー全体のすべてのノードとノードを接続するエッジを再帰的に取得し、これらのノードとエッジから Dot 形式の文字列を生成してファイルに書き込み、グラフを描画することです。 ツリーのノードとエッジを再帰的に取得し、uuid を使用して各ノードに id 属性を追加し、同じ属性を持つノードを区別します。 - def get_nodes_edges(self, tree=None, root_node=None):
-
- '' ' ツリー内のすべてのノードとエッジを返します
-
- '' '
-
- ノード = namedtuple( 'ノード' , [ 'id' , 'ラベル' ])
-
- エッジ = namedtuple( 'エッジ' , [ '開始' , '終了' , 'ラベル' ])
-
-
-
- ツリーがNoneの場合:
-
- ツリー = 自己.ツリー
-
-
-
- タイプ(ツリー)が 辞書ではない:
-
- 戻る[]、 []
-
-
-
- ノード、エッジ = []、[]
-
-
-
- root_nodeがNone の場合:
-
- ラベル = リスト(tree.keys())[0]
-
- root_node = Node._make([uuid.uuid4(), ラベル])
-
- ノードを追加します(ルートノード)
-
-
-
- tree[root_node.label].items()内のedge_label、sub_treeの場合:
-
- node_label = list(sub_tree.keys())[0] 型(sub_tree)がdictの場合、そうでない場合はsub_tree
-
- サブノード = Node._make([uuid.uuid4(), node_label])
-
- ノードを追加します(サブノード)
-
-
-
- エッジ = Edge._make([ルートノード、サブノード、エッジラベル])
-
- エッジ.append(エッジ)
-
-
-
- サブノード、サブエッジ = self.get_nodes_edges(サブツリー、ルートノード = サブノード)
-
- ノードを拡張します(サブノード)
-
- エッジを拡張する(サブエッジ)
-
-
-
- ノード、エッジを返す
ドットファイルコンテンツを生成する - def dotify(self, tree=None):
-
- ' ' ツリーのGraphviz Dotファイルの内容を取得します
-
- '' '
-
- ツリーがNoneの場合:
-
- ツリー = 自己.ツリー
-
-
-
- コンテンツ = '有向グラフ決定木 {\n'
-
- ノード、エッジ = self.get_nodes_edges(tree)
-
-
-
- ノード内のノードの場合:
-
- コンテンツ += ' "{}" [label="{}"];\n' .format(node.id, node.label)
-
-
-
- エッジ内のエッジの場合:
-
- 開始、ラベル、終了= edge.start、edge.label、 edge.end
-
- コンテンツ += ' "{}" -> "{}" [label="{}"];\n' .format(start.id, end .id, label)
-
- コンテンツ += '}'
-
-
-
- コンテンツを返す
コンタクトレンズデータによって生成されたDotファイルの内容は次のとおりです。 - 有向グラフ決定木 {
-
- "959b4c0c-1821-446d-94a1-c619c2decfcd" [ラベル= "通話" ];
-
- "18665160-b058-437f-9b2e-05df2eb55661" [ラベル= "宛名" ];
-
- "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [ラベル= "あなたの" ];
-
- "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [ラベル= "areyouunique" ];
-
- "ca091fc7-8a4e-4970-9ec3-485a4628ad29" [ラベル= "02073162414" ];
-
- "aac20872-1aac-499d-b2b5-caf0ef56eff3" [ラベル= "ハム" ];
-
- "18aa8685-a6e8-4d76-bad5-ccea922bb14d" [ラベル= "スパム" ];
-
- "3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [ラベル= "スパム" ];
-
- "44d1f972-cd97-4636-b6e6-a389bf560656" [ラベル= "スパム" ];
-
- "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [ラベル= "i" ];
-
- "a6f22325-8841-4a81-bc04-4e7485117aa1" [ラベル= "スパム" ];
-
- "c181fe42-fd3c-48db-968a-502f8dd462a4" [ラベル= "ldn" ];
-
- "51b9477a-0326-4774-8622-24d1d869a283" [ラベル= "ハム" ];
-
- "16f6aecd-c675-4291-867c-6c64d27eb3fc" [ラベル= "スパム" ];
-
- "adb05303-813a-4fe0-bf98-c319eb70be48" [ラベル= "スパム" ];
-
- "959b4c0c-1821-446d-94a1-c619c2decfcd" -> "18665160-b058-437f-9b2e-05df2eb55661" [ラベル= "0" ];
-
- "18665160-b058-437f-9b2e-05df2eb55661" -> "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" [ラベル= "0" ];
-
- "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" [ラベル= "0" ];
-
- "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "ca091fc7-8a4e-4970-9ec3-485a4628ad29" [ラベル= "0" ];
-
- "ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "aac20872-1aac-499d-b2b5-caf0ef56eff3" [ラベル= "0" ];
-
- "ca091fc7-8a4e-4970-9ec3-485a4628ad29" -> "18aa8685-a6e8-4d76-bad5-ccea922bb14d" [ラベル= "1" ];
-
- "bcbcc17c-9e2a-4bd4-a039-6e51fde5f8fd" -> "3f7f30b1-4dbb-4459-9f25-358ad3c6d50b" [ラベル= "1" ];
-
- "2eb9860d-d241-45ca-85e6-cbd80fe2ebf7" -> "44d1f972-cd97-4636-b6e6-a389bf560656" [ラベル= "1" ];
-
- "18665160-b058-437f-9b2e-05df2eb55661" -> "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" [ラベル= "1" ];
-
- "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "a6f22325-8841-4a81-bc04-4e7485117aa1" [ラベル= "0" ];
-
- "7f3c8562-69b5-47a9-8ee4-898bd4b6b506" -> "c181fe42-fd3c-48db-968a-502f8dd462a4" [ラベル= "1" ];
-
- "c181fe42-fd3c-48db-968a-502f8dd462a4" -> "51b9477a-0326-4774-8622-24d1d869a283" [ラベル= "0" ];
-
- "c181fe42-fd3c-48db-968a-502f8dd462a4" -> "16f6aecd-c675-4291-867c-6c64d27eb3fc" [ラベル= "1" ];
-
- "959b4c0c-1821-446d-94a1-c619c2decfcd" -> "adb05303-813a-4fe0-bf98-c319eb70be48" [ラベル= "1" ];
-
- }
このようにしてGraphvizを使って決定木を描くことができる。 - と open ( 'lenses.dot' , 'w' )をf:として開きます。
-
- ドット = clf.tree.dotify()
-
- f.write(ドット)
-
-
- ドット -Tgif レンズ.ドット -o レンズ.gif
効果は以下のとおりです。 生成された決定木を分類に使用する 未知のデータを予測するには、主にツリー内のノードに基づいてリーフノードを再帰的に見つける必要があります。ここでは再帰によって最適化できます。コードは次のようになります。 - def classify(self, data_vect, feat_names=None, tree=None):
-
- '' ' 構築された決定木に従ってデータを分類する
-
- '' '
-
- ツリーがNoneの場合:
-
- ツリー = 自己.ツリー
-
-
-
- feat_namesがNone の場合:
-
- feat_names = 自己.feat_names
-
-
-
- # 再帰的な基本ケース。
-
- タイプ(ツリー)が 辞書ではない:
-
- リターンツリー
-
-
-
- 機能 = リスト(tree.keys())[0]
-
- 値 = data_vect[ feat_names.index (フィーチャ)]
-
- sub_tree = ツリー[機能][値]
-
-
-
- self.classify(feat_names, data_vect, sub_tree)を返します。
決定木の保存 決定木は辞書で表現されるため、組み込みの pickle または json モジュールを介してハードディスクに保存できます。また、ハードディスクからツリー構造を読み取ることもできるため、データセットが大きい場合に決定木の構築時間を節約できます。 - def dump_tree(self, ファイル名, ツリー=なし):
-
- '' '店舗決定ツリー
-
- '' '
-
- ツリーがNoneの場合:
-
- ツリー = 自己.ツリー
-
-
-
- と (ファイル名、 'w' )をf:として開きます。
-
- pickle.dump(ツリー、f)
-
-
-
- def load_tree(self, ファイル名):
-
- '' ' ツリー構造をロードする
-
- '' '
-
- と open (filename, 'r' )をf:として開きます。
-
- ツリー = pickle.load (f)
-
- self.tree = ツリー
-
- リターンツリー
要約する この記事では、ID3 アルゴリズムを使用して最適なパーティション属性を決定し、構築された決定木を Graphviz で視覚化することで、決定木を段階的に実装します。この記事に関連するコードリンク: https://github.com/PytLab/MLBox/tree/master/decision_tree 参照: - 機械学習の実践
- データマイニングシリーズ(6)決定木分類アルゴリズム
|