デシジョン ツリー アルゴリズムの構造

翻訳者| Zhao Qingyu

査読者| Sun Shujuan

序文

機械学習では、分類には 2 つの段階があります。それぞれ学習段階と予測段階です。学習フェーズでは、指定されたトレーニング データに基づいてモデルが構築され、予測フェーズでは、そのモデルはデータに基づいて応答を予測するために使用されます。デシジョン ツリーは、理解して説明するのが最も簡単な分類アルゴリズムの 1 つです。

機械学習では、分類には学習段階と予測段階の 2 つの段階があります。学習フェーズでは、指定されたトレーニング データに基づいてモデルが構築され、予測フェーズでは、そのモデルはデータに基づいて応答を予測するために使用されます。デシジョン ツリーは、理解して説明するのが最も簡単な分類アルゴリズムの 1 つです。

デシジョン ツリー アルゴリズム

デシジョン ツリー アルゴリズムは、教師あり学習アルゴリズムの 1 つです。他の教師あり学習アルゴリズムとは異なり、デシジョン ツリー アルゴリズムは回帰問題と分類問題の両方を解決するために使用できます。

デシジョン ツリーを使用する目的は、以前のデータ (トレーニング データ) から推測される単純な決定ルールを学習することによって、ターゲット変数のクラスまたは値を予測するトレーニング モデルを作成することです。

デシジョン ツリーでは、ツリーのルートから開始してレコードのクラス ラベルを予測します。ルート属性の値を記録された属性と比較し、その比較に基づいて、この値に対応する分岐をたどって次のノードにジャンプします。

デシジョン ツリーの種類

ターゲット変数の種類に基づいて、ツリーを 2 つのタイプに分けることができます:

1. カテゴリ変数デシジョン ツリー: はい デシジョンカテゴリカルターゲット変数のツリーは、カテゴリカル変数決定木と呼ばれます。

2. 連続変数決定木: 決定木の対象変数が連続であるため、連続変数決定木と呼ばれます。

例: 顧客が保険会社に更新料を支払うかどうかを予測するという問題があるとします。ここでは顧客の収入が重要な変数ですが、保険会社はすべての顧客の収入の詳細を把握しているわけではありません。これが重要な変数であることがわかったので、職業、製品、その他のさまざまな変数に基づいて顧客の収益を予測するデシジョン ツリーを構築できます。この場合、ターゲット変数は連続であると予測します。

デシジョン ツリーに関する重要な用語

1. ルート ノード (ルート ノード): メンバーまたはサンプル全体を表し、さらに 2 つ以上の同じタイプのコレクションに分割されます。

2. 分割): ノードを 2 つ以上の子ノードに分割するプロセス。

3. 意思決定ノード: 子ノードがさらに多くの子ノードに分割される場合、その子ノードは意思決定ノードと呼ばれます。

4. リーフ/ターミナル ノード: 分割できないノードは、リーフ ノードまたはターミナル ノードと呼ばれます。

5. プルーニング: デシジョン ノードの子ノードを削除するプロセスは、プルーニングと呼ばれます。建設は、分離の逆のプロセスとみなすこともできます。

6. ブランチ/サブツリー: ツリー全体のサブパートはブランチまたはサブツリーと呼ばれます。

7. 親ノードと子ノード: 子ノードに分割できるノードは親ノードと呼ばれ、子ノードは親ノードの子ノードです。

デシジョン ツリーは、ルートからリーフ/終端ノードまでの降順でサンプルを分類し、サンプルの分類方法を提供します。ツリー内の各ノードは特定の属性のテスト ケースとして機能し、ノードからの各下降方向はテスト ケースに対する考えられる答えに対応します。このプロセスは本質的に再帰的であり、新しいノードをルートとする各サブツリーに対して同じように扱われます。

デシジョン ツリーを作成するときに行う仮定

デシジョン ツリーを使用するときに行ういくつかの仮定を次に示します:

#●まず、トレーニング セット全体をルートとして取得します。

##●特徴量は分類できればベストです。これらの値が連続値である場合、モデルを構築する前に離散化できます。

#●レコードは属性値に基づいて再帰的に分散されます。

#いくつかの統計的手法を使用して、対応する属性がツリーのルート ノードまたはツリーの内部ノードに順番に配置されます。

デシジョン ツリーは、積の和の式形式に従います。 Sum of Products (SOP) は選言正規形としても知られています。クラスの場合、ツリーのルートから同じクラスのリーフ ノードまでの各分岐は値の結合であり、クラスで終わる異なる分岐は論理和を構成します。

デシジョン ツリーの実装プロセスにおける主な課題は、ルート ノードと各レベル ノードの属性を決定することであり、この問題は属性選択問題です。現在、各レベルでノードの属性を選択するためのさまざまな属性選択方法があります。

デシジョン ツリーはどのように機能しますか?

意思決定の分離特性はツリーの精度に重大な影響を与えます。分類ツリーと回帰ツリーの意思決定基準は異なります。

デシジョン ツリーは、さまざまなアルゴリズムを使用して、ノードを 2 つ以上の子ノードに分割することを決定します。子ノードを作成すると、子ノードの均一性が高まります。言い換えれば、ノードの純度はターゲット変数と比較して増加します。デシジョン ツリーは、使用可能なすべての変数でノードを分離し、分割する多くの同型子ノードを生成できるノードを選択します。

アルゴリズムはターゲット変数のタイプに基づいて選択されます。次に、デシジョン ツリーで使用されるいくつかのアルゴリズムを見てみましょう:

ID3→(D3 の拡張)

C4.5→(ID3 の後継)

CART→ (分類と回帰木)

CHAID→(カイ二乗自動交互作用検出は分類木計算時に多段階分離を実行)

MARS→(多重適応回帰スプライン)

ID3 アルゴリズムは、トップダウンの貪欲な検索手法を使用して、バックトラックすることなく、可能な分岐空間を通じてデシジョン ツリーを構築します。貪欲なアルゴリズムは、その名前が示すように、常にある時点で最善と思われるものを選択します。

ID3 アルゴリズム ステップ:

1. 元のセット S をルート ノードとして使用します。

2. アルゴリズムの各反復中に、セット S 内の未使用の属性を反復処理し、属性のエントロピー (H) と情報ゲイン (IG) を計算します。

3. 次に、最小のエントロピーまたは最大の情報利得を持つ属性を選択します。

4. 次に、選択した属性を使用してセット S を分離し、データのサブセットを生成します。

5. アルゴリズムは、各反復で以前に選択されたことのない属性のみを考慮して、各サブセットを反復し続けます。

属性選択方法

データ セットに N 個の属性が含まれている場合、どの属性をルート ノードに配置するか、内部ノードとしてツリーのさまざまなレベルに配置するかを決定するのは複雑な手順です。この問題は、任意のノードをルート ノードとしてランダムに選択することによっては解決できません。無作為なアプローチを採用すると、さらに悪い結果が生じる可能性があります。

この属性選択の問題を解決するために、研究者はいくつかのソリューションを設計しました。彼らは、次の基準を使用することを提案しました:

• エントロピー
• 情報利得
• ジニ指数
• 利得率
• 分散削減
• カイ 2 乗

# これらの基準を使用して各属性の値を計算し、値を並べ替えて属性をツリーに順番に配置します。つまり、値が高い属性です。値はルートの場所に配置されます。

情報獲得を基準として使用する場合、属性はカテゴリ的であると仮定しますが、ジニ指数の場合は属性が連続的であると仮定します。

1. エントロピー

エントロピーは、処理される情報のランダム性の尺度です。エントロピー値が高くなるほど、情報から結論を引き出すことが難しくなります。コインを投げることは、ランダムな情報を提供する行動の一例です。

上の図からわかるように、確率が 0 または 1 の場合、エントロピー H(X) はゼロです。確率が 0.5 の場合、データ内の完全なランダム性が予測されるため、エントロピーは最大になります。

ID3 に従うルールは次のとおりです。エントロピー 0 のブランチはリーフ ノードであり、エントロピー 0 より大きいブランチはさらに分離する必要があります。

単一属性の数学的エントロピーは次のように表されます。

#ここで、S は現在の状態を表し、Pi は状態 i におけるイベント i の確率を表します。状態 S ノードの S または i クラスの割合。

複数の属性の数学的エントロピーは次のように表されます。

ここで、T は現在の状態を表し、X は選択された属性を表します

2. 情報ゲイン

情報ゲイン (IG) は、ターゲット クラスに基づいて特定の属性に対する個別のトレーニングの有効性を測定するために使用される統計属性です。デシジョン ツリーの構築は、最高の情報利得と最低のエントロピーを返す属性を見つけるプロセスです。

#情報の増加はエントロピーの減少です。指定された属性値に基づいて、データセットの分離前のエントロピー差と分離後の平均エントロピー差を計算します。 ID3 決定木アルゴリズムは情報獲得法を使用します。

IG は数学的に次のように表されます:

より単純なアプローチを使用すると、次の結論を導き出すことができます:

ここで、before は分割前のデータ セット、K は分割によって生成されたサブセットの数、(j, after) は分割後のサブセット j です。

3. ジニ指数

ジニ指数は、データセット内の分離を評価するために使用されるコスト関数と考えることができます。これは、各クラスの確率の二乗の合計を 1 から引くことによって計算されます。これは、より大きなパーティションの場合に有利であり、実装が容易ですが、情報の取得は、

異なる値を持つより小さなパーティションの場合に有利です。

Gini インデックスは、カテゴリカルなターゲット変数「成功」または「失敗」から切り離すことができません。バイナリ分離のみを実行します。ジニ係数が高いほど不平等の程度が大きくなり、不均一性が強くなります。

ジニ指数分離を計算する手順は次のとおりです。

• 次のコマンドを使用して、子ノードのジニ係数を計算します。上記の成功 (p) と失敗 (q) の式は (p² q²) です。
• 分離の各ノードの加重ジニ スコアを使用して、分離のジニ係数インデックスを計算します。

CART (分類および回帰ツリー) は、ジニ指数法を使用して分離点を作成します。

4. 獲得率

情報獲得では、多数の値を持つ属性がルート ノードとして選択される傾向があります。これは、多数の異なる値を持つプロパティが優先されることを意味します。

C4.5 は ID3 の改良された方法で、ゲイン比を使用します。これは情報ゲインを修正してバイアスを低減するもので、通常はこれが最適な方法です。ゲイン レートは、分割を行う前に分岐の数を考慮することで、情報ゲインの問題を解決します。個別の固有情報を考慮に入れることで、情報の獲得を補正します。

ユーザーと、性別、年齢層、階級などの変数に基づいた映画ジャンルの好みを含むデータセットがあるとします。情報獲得の助けを借りて、「性別」で分離します (情報獲得が最も高いと仮定します)。今度は、変数「年齢層」と「評価」も同様に重要になる可能性があります。獲得率の助けを借りて、次のようなプロパティを選択できます。次の層で分離されます。

#ここで、before は分離前のデータセット、K は分離によって生成されたサブセットの数、(j, after) は分離後のサブセットです。 j.

5. 分散削減

分散削減は、連続ターゲット変数 (回帰問題) に使用されるアルゴリズムです。このアルゴリズムでは、標準分散公式を使用して最適な分離を選択します。母集団を分離する基準として分散が小さい分離を選択します。

は平均、X は実際の値、n は数値です。価値観の。

分散を計算する手順:

• 各ノードの分散を計算します。
• 各分離の分散を計算し、それを各ノードの分散の加重平均として使用します。

6. カイ二乗

CHAID は、カイ 2 乗自動相互作用検出器の略称です。これは、古いツリー分類方法の 1 つです。子ノードとその親ノードの間の統計的に有意な差を見つけます。ターゲット変数の観測頻度と期待頻度の差の二乗和によって測定します。

これは、カテゴリカル ターゲット変数「成功」または「失敗」で機能します。 2 つ以上の分離を実行できます。カイ二乗値が大きいほど、子ノードと親ノードの差が統計的に有意になります。 CHAID というツリーが生成されます。

数学では、カイ 2 乗は次のように表されます。

カイ 2 乗を計算する手順

• 成功と失敗の偏差を計算して、単一ノードのカイ 2 乗を計算します。
• 別々の値を使用します。各ノードの成功と失敗 すべてのカイ 2 乗の合計により、分離されたカイ 2 乗が計算されます。 ##デシジョン ツリーがあります。特に列がいっぱいのツリーでよくある問題です。場合によっては、ツリーがトレーニング データ セットを記憶しているように見えることがあります。デシジョン ツリーに制約がない場合、最悪の場合、観測ごとに 1 つのリーフが生成されるため、トレーニング データ セットに対して 100% の精度が得られます。したがって、これはトレーニング セットの一部ではないサンプルを予測する際の精度に影響します。

ここでは、過学習を解消する 2 つの方法、つまり枝刈りデシジョン ツリーとランダム フォレストを紹介します。

1. デシジョン ツリーの剪定

分離プロセスでは、停止基準に達するまで完全に成長したツリーが生成されます。ただし、成熟したツリーはデータを過剰適合させる可能性があり、その結果、目に見えないデータの精度が低下します。

枝刈りでは、ツリーの枝を枝刈りします。つまり、全体の精度が損なわれないように、葉ノードから開始して決定ノードを削除します。これは、実際のトレーニング セットをトレーニング データ セット D と検証データ セット V の 2 つのセットに分割し、分離されたトレーニング データ セット D を使用してデシジョン ツリーを準備し、その後、検証データ セット V を最適化するためにツリーの枝刈りを継続することによって行われます。正確さ。

上の画像では、ツリーの左側の「Age」属性が枝刈りされています。これは、ツリーの右側の方が重要であるためです。過学習。

2. ランダム フォレスト

ランダム フォレストはアンサンブル学習 (アンサンブル学習) の一例であり、複数の機械学習アルゴリズムを組み合わせて、より優れた予測パフォーマンスを実現します。ツリーを構築するときにトレーニング データ セットがランダムにサンプリングされ、ノードを分離するときに特徴のランダムなサブセットが考慮されるため、このメソッドをランダムと呼びます。

バギングと呼ばれる手法を使用して、複数のトレーニング セットが置換によって生成されるツリーのコレクションを作成します。

バギング テクノロジは、ランダム サンプリングを使用してデータ セットを N 個のサンプルに分割します。次に、単一の学習アルゴリズムを使用して、すべてのサンプルに対してモデルを構築します。次に、予測は並列投票または平均を通じて結合されます。

線形モデルとツリーベース モデルのどちらが優れていますか?

問題は、解決しようとしている問題の種類によって異なります。

1. 従属変数と独立変数の間の関係が線形モデルで適切にモデル化できる場合、線形回帰はツリーベースのモデルよりも優れています。

2. 従属変数と独立変数の間に高度に非線形で複雑な関係がある場合、ツリー モデルは従来の回帰手法よりも優れています。

3. 理解しやすいモデルを構築する必要がある場合は、線形モデルよりもデシジョン ツリー モデルの方が常に優れています。デシジョン ツリー モデルは線形回帰よりも理解しやすいです!

Scikit-learn を使用してデシジョン ツリー分類器を構築する

使用したデータは https://drive.google.com/ からのものです。 id=1x1KglkvJxNn8C8kzeV96YePFnCUzXhBS によってダウンロードされたスーパーマーケット関連データについては、まず次のコードを使用してすべての基本ライブラリをロードします:

import numpy as np
import matplotlib.pyplot as plt 
import pandas as pd

その後、次のメソッドを使用してロードします。データセット。ユーザーID、性別、年齢、推定給与、購買状況の5つの属性が含まれます。

data = pd.read_csv('/Users/ML/DecisionTree/Social.csv')
data.head()

図 1 データセット

年齢と予測のみを組み合わせます。性別やユーザー ID などの他の特性は無関係で、個人の購買力に影響を与えないため、給与が独立変数 X として使用され、y が従属変数となります。

feature_cols = ['Age','EstimatedSalary' ]X = data.iloc[:,[2,3]].values
y = data.iloc[:,4].values

次のステップは、データ セットをトレーニング セットとテスト セットに分離することです。

from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test =train_test_split(X,y,test_size = 0.25, random_state= 0)

次に特徴スケーリングを実行します

#feature scaling
from sklearn.preprocessing import StandardScaler
sc_X = StandardScaler()
X_train = sc_X.fit_transform(X_train)
X_test = sc_X.transform(X_test)

モデルをデシジョン ツリーに適合させます。分類子。

from sklearn.tree import DecisionTreeClassifier
classifier = DecisionTreeClassifier()
classifier = classifier.fit(X_train,y_train)

予測を立てて精度を確認します。

#prediction
y_pred = classifier.predict(X_test)#Accuracy
from sklearn import metricsprint('Accuracy Score:', metrics.accuracy_score(y_test,y_pred))

デシジョン ツリー分類器の精度は 91% です。

混同マトリックス

from sklearn.metrics import confusion_matrix
cm = confusion_matrix(y_test, y_pred)Output:
array([[64,4],
 [ 2, 30]])

これは、エラーとして分類された観測値が 6 つあることを意味します。

#まず、モデルの予測を視覚化しましょう

from matplotlib.colors import ListedColormap
X_set, y_set = X_test, y_test
X1, X2 = np.meshgrid(np.arange(start = X_set[:,0].min()-1, stop= X_set[:,0].max()+1, step = 0.01),np.arange(start = X_set[:,1].min()-1, stop= X_set[:,1].max()+1, step = 0.01))
plt.contourf(X1,X2, classifier.predict(np.array([X1.ravel(), X2.ravel()]).T).reshape(X1.shape), alpha=0.75, cmap = ListedColormap(("red","green")))plt.xlim(X1.min(), X1.max())
plt.ylim(X2.min(), X2.max())for i,j in enumerate(np.unique(y_set)):
plt.scatter(X_set[y_set==j,0],X_set[y_set==j,1], c = ListedColormap(("red","green"))(i),label = j)
plt.title("Decision Tree(Test set)")
plt.xlabel("Age")
plt.ylabel("Estimated Salary")
plt.legend()
plt.show()

##次に、このツリーを想像してください

次に、Scikit を使用できます-learn の import_graphviz 関数を使用して、Jupyter ノートブックにツリーを表示します。ツリーを描画するには、次のコマンドを使用して Graphviz と pydotplus をインストールする必要があります:

conda install python-graphviz
pip install pydotplus

export_graphviz 関数はデシジョン ツリー分類子をポイント ファイルに変換し、pydotplus はポイント ファイルを変換しますpng または in Jupyter 上で表示されるフォームは次のように実装されます:

from sklearn.tree import export_graphviz
from sklearn.externals.six import StringIO
from IPython.display import Image
import pydotplusdot_data = StringIO()
export_graphviz(classifier, out_file=dot_data,
filled=True, rounded=True,
special_characters=True,feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(graph.create_png())

在决策树形图中，每个内部节点都有一个分离数据的决策规则。Gini代表基尼系数，它代表了节点的纯度。当一个节点的所有记录都属于同一个类时，您可以说它是纯节点，这种节点称为叶节点。

在这里，生成的树是未修剪的。这棵未经修剪的树不容易理解。在下一节中，我会通过修剪的方式来优化树。

随后优化决策树分类器

criteria: 该选项默认配置是Gini，我们可以通过该项选择合适的属性选择方法，该参数允许我们使用different-different属性选择方式。支持的标准包含基尼指数的“基尼”和信息增益的“熵”。

splitter: 该选项默认配置是" best "，我们可以通过该参数选择合适的分离策略。支持的策略包含“best”(最佳分离)和“random”(最佳随机分离)。

max_depth：默认配置是None，我们可以通过该参数设置树的最大深度。若设置为None，则节点将展开，直到所有叶子包含的样本小于min_samples_split。最大深度值越高，过拟合越严重，反之，过拟合将不严重。

在Scikit-learn中，只有通过预剪枝来优化决策树分类器。树的最大深度可以用作预剪枝的控制变量。

# Create Decision Tree classifer object
classifier = DecisionTreeClassifier(criterion="entropy", max_depth=3)# Train Decision Tree Classifer
classifier = classifier.fit(X_train,y_train)#Predict the response for test dataset
y_pred = classifier.predict(X_test)# Model Accuracy, how often is the classifier correct?
print("Accuracy:",metrics.accuracy_score(y_test, y_pred))

至此分类率提高到94%，相对之前的模型来说，其准确率更高。现在让我们再次可视化优化后的修剪后的决策树。

dot_data = StringIO()
export_graphviz(classifier, out_file=dot_data,
filled=True, rounded=True,
special_characters=True, feature_names = feature_cols,class_names=['0','1'])
graph = pydotplus.graph_from_dot_data(dot_data.getvalue())
Image(graph.create_png())

上图是经过修剪后的模型，相对之前的决策树模型图来说，其更简单、更容易解释和理解。

总结

在本文中，我们讨论了很多关于决策树的细节，它的工作方式，属性选择措施，如信息增益，增益比和基尼指数，决策树模型的建立，可视化，并使用Python Scikit-learn包评估和优化决策树性能，这就是这篇文章的全部内容，希望你们能喜欢它。

译者介绍

赵青窕，51CTO社区编辑，从事多年驱动开发。

原文标题：​​Decision Tree Algorithm, Explained​​，作者：Nagesh Singh Chauhan

以上がデシジョン ツリー アルゴリズムの構造の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。