[機械学習]決定ツリー
5935 ワード
けっていじゅ
決定ツリー学習はトップダウンの再帰法を採用し,その基本思想は情報エントロピーをメトリックとしてエントロピー値の低下が最も速いツリーを構築し,葉ノードにおいてエントロピー値が0である.
非常に解釈性に優れ、分類速度が速いという利点があり、監督学習がある.
決定木思想について最初に言及したのはQuinlanが1986年に提出したID 3アルゴリズムと1993年に提出したC 4である.5アルゴリズム,およびBriemanらが1984年に提案したCARTアルゴリズム
さぎょうげんり
一般的に、1つの決定ツリーには、1つのルートノード、複数の内部ノード、および複数のリーフノードが含まれます.
こうぞう
構造は、完全な意思決定ツリーを生成することです.簡単に言えば,構造の過程はどの属性をノードとして選択する過程である.
リーフノードは決定結果に対応し、他の各ノードは属性テストに対応し、各ノードに含まれるサンプルセットは属性テストの結果に基づいてサブノードに分割される.
ルートノードはサンプルの集合体を含む、ルートノードから各リーフノードへの経路が判定試験シーケンスに対応する.意思決定ツリー学習の目的は、一般化能力が強い、すなわち、例示的な能力が強い意思決定ツリーを処理することであり、その基本プロセスは簡単で直感的な分割戦略に従うことである.
決定ツリーの生成は再帰的なプロセスであることは明らかである.決定ツリーの基本アルゴリズムでは、再帰的な戻りをもたらす3つのケースがあります.現在のノードに含まれるサンプルはすべて同じカテゴリに属し、 を区分する必要はない.現在のプロパティセットが空であるか、またはすべてのサンプルがすべてのプロパティで同じ値をとるか、 を区別できません.現在のノードに含まれるサンプルの集合は空であり、 を区切ることはできない.
分割の選択
決定ツリー学習の鍵は、最適な区分プロパティをどのように選択するかです.
分割プロセスが進むにつれて、決定ツリーの分岐ノードに含まれるサンプルができるだけ同じカテゴリに属することを望んでいます.すなわち、ノードの「純度」が高くなります.
じょうほうエントロピー
情報エントロピーは情報論においてランダム変数の不確定度のメトリックを表す
エントロピーが大きいほどデータの不確実性が高くなり純度が低くなる
エントロピーが小さいほどデータの不確実性が低くなり純度が高くなる
現在のサンプルセット$D$の$k$クラスのサンプルが占める割合を$p_と仮定する{k}(k=1,2,ldots,|mathcal{Y}|)$では$D$の情報嫡は
$$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k}\log _{2} p_{k}$$
じょうほうりとく
離散属性$a$に$V$個の可能な値$left{a^{1},a^{2},ldots,a^{V}right},$が$a$を使用してサンプルセット$D$を分割すると、$V$個の分岐ノードが生成され、$v$個目の分岐ノードには$D$のすべての属性$a$に$a^{v}$が含まれるサンプルが$D^{v}$として記録される.式(4.1)に基づいて$D^{v}$の情報嫡を算出することができ,また,異なる分岐ノードに含まれるサンプル数の違いを考慮して,分岐ノードに重み$left|D^{v}right|/|D|,$すなわち,サンプル数が多いほど分岐ノードの影響が大きくなり,そこで、サンプルセット$D$を属性$a$で分割して得られる「情報利得」$operatorname{Gain}(D,a)=operatorname{Ent}(D)-sum_{v=1}^{V}\frac{\left|D^{v}\right|}{|D|}\operatorname{Ent}\left(D^{v}\right)$$
一般に、情報利得が大きいほど、属性$a$を用いて分割する「純度アップ」が大きいことを意味する.したがって,情報利得を用いて決定ツリーの区分属性選択を行うことができ,有名なID 3決定ツリー学習アルゴリズムは情報利得を基準として区分属性を選択する
ID 3アルゴリズムの利点は方法が簡単で,欠点はノイズに敏感である.トレーニングデータに少量のエラーがあると、意思決定ツリーの分類エラーが発生する可能性があります.
じょうほうりとくりつ
$$\text {GainRatio}(D, a)=\frac{\operatorname{Gain}(D, a)}{Ent(D)} $$
C4.5 IID 3に基づいて、情報利得の代わりに情報利得率を用いることにより、ノイズに敏感な問題を解決するとともに、構造木の剪定や連続数値の処理、数値の欠落などを行うことができるが、C 4.5データセットを複数回スキャンする必要があり、アルゴリズム効率が比較的低い
キニーしすう
キニー指数は古典的な決定木CARTが問題を分類する際に最適な特徴を選択する指標である.
$K$クラスがあると仮定し、サンプルポイントが$k$クラスに属する確率は$p_k$、確率分布のキニー指数は
$$ G(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} $$
情報利得,利得率,キニー指数に加えて,決定ツリー分割選択のための多くの他の準則も設計されている.
しかし,これらの準則は決定ツリーのサイズに大きな影響を及ぼすが,汎化性能に及ぼす影響は限られていることが実験的に示された.
枝を切る
決定ツリーの欠点には、未知のテストデータに対して必ずしも良い分類、汎化能力があるとは限らない.すなわち、フィット現象が発生する可能性がある.この場合、剪定枝やランダム森林を採用することができる.
剪定は決定木学習アルゴリズムが「オーバーフィット」に対処する主な手段である.
意思決定ツリー学習では、できるだけ正確に訓練サンプルを分類するために、結点区分過程が繰り返され、意思決定ツリーの分岐が多すぎる場合がある.この場合、訓練サンプルがよく勉強されているため、訓練セット自体のいくつかの特徴をすべてのデータが持つ一般的な性質としてフィッティングしすぎる可能性がある.
ID 3決定ツリーコード
参照Machine Learning in Actionby Peter Harrington
リファレンス
機械学習の-一般的な決定木アルゴリズム(ID 3、C 4.5、CART)
けっていじゅ
意思決定ツリー(Decision Tree):わかりやすい紹介
機械学習-周志華
Machine Learning in Action by Peter Harrington
決定ツリー学習はトップダウンの再帰法を採用し,その基本思想は情報エントロピーをメトリックとしてエントロピー値の低下が最も速いツリーを構築し,葉ノードにおいてエントロピー値が0である.
非常に解釈性に優れ、分類速度が速いという利点があり、監督学習がある.
決定木思想について最初に言及したのはQuinlanが1986年に提出したID 3アルゴリズムと1993年に提出したC 4である.5アルゴリズム,およびBriemanらが1984年に提案したCARTアルゴリズム
さぎょうげんり
一般的に、1つの決定ツリーには、1つのルートノード、複数の内部ノード、および複数のリーフノードが含まれます.
こうぞう
構造は、完全な意思決定ツリーを生成することです.簡単に言えば,構造の過程はどの属性をノードとして選択する過程である.
リーフノードは決定結果に対応し、他の各ノードは属性テストに対応し、各ノードに含まれるサンプルセットは属性テストの結果に基づいてサブノードに分割される.
ルートノードはサンプルの集合体を含む、ルートノードから各リーフノードへの経路が判定試験シーケンスに対応する.意思決定ツリー学習の目的は、一般化能力が強い、すなわち、例示的な能力が強い意思決定ツリーを処理することであり、その基本プロセスは簡単で直感的な分割戦略に従うことである.
決定ツリーの生成は再帰的なプロセスであることは明らかである.決定ツリーの基本アルゴリズムでは、再帰的な戻りをもたらす3つのケースがあります.
分割の選択
決定ツリー学習の鍵は、最適な区分プロパティをどのように選択するかです.
分割プロセスが進むにつれて、決定ツリーの分岐ノードに含まれるサンプルができるだけ同じカテゴリに属することを望んでいます.すなわち、ノードの「純度」が高くなります.
じょうほうエントロピー
情報エントロピーは情報論においてランダム変数の不確定度のメトリックを表す
エントロピーが大きいほどデータの不確実性が高くなり純度が低くなる
エントロピーが小さいほどデータの不確実性が低くなり純度が高くなる
現在のサンプルセット$D$の$k$クラスのサンプルが占める割合を$p_と仮定する{k}(k=1,2,ldots,|mathcal{Y}|)$では$D$の情報嫡は
$$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k}\log _{2} p_{k}$$
じょうほうりとく
離散属性$a$に$V$個の可能な値$left{a^{1},a^{2},ldots,a^{V}right},$が$a$を使用してサンプルセット$D$を分割すると、$V$個の分岐ノードが生成され、$v$個目の分岐ノードには$D$のすべての属性$a$に$a^{v}$が含まれるサンプルが$D^{v}$として記録される.式(4.1)に基づいて$D^{v}$の情報嫡を算出することができ,また,異なる分岐ノードに含まれるサンプル数の違いを考慮して,分岐ノードに重み$left|D^{v}right|/|D|,$すなわち,サンプル数が多いほど分岐ノードの影響が大きくなり,そこで、サンプルセット$D$を属性$a$で分割して得られる「情報利得」$operatorname{Gain}(D,a)=operatorname{Ent}(D)-sum_{v=1}^{V}\frac{\left|D^{v}\right|}{|D|}\operatorname{Ent}\left(D^{v}\right)$$
一般に、情報利得が大きいほど、属性$a$を用いて分割する「純度アップ」が大きいことを意味する.したがって,情報利得を用いて決定ツリーの区分属性選択を行うことができ,有名なID 3決定ツリー学習アルゴリズムは情報利得を基準として区分属性を選択する
ID 3アルゴリズムの利点は方法が簡単で,欠点はノイズに敏感である.トレーニングデータに少量のエラーがあると、意思決定ツリーの分類エラーが発生する可能性があります.
じょうほうりとくりつ
$$\text {GainRatio}(D, a)=\frac{\operatorname{Gain}(D, a)}{Ent(D)} $$
C4.5 IID 3に基づいて、情報利得の代わりに情報利得率を用いることにより、ノイズに敏感な問題を解決するとともに、構造木の剪定や連続数値の処理、数値の欠落などを行うことができるが、C 4.5データセットを複数回スキャンする必要があり、アルゴリズム効率が比較的低い
キニーしすう
キニー指数は古典的な決定木CARTが問題を分類する際に最適な特徴を選択する指標である.
$K$クラスがあると仮定し、サンプルポイントが$k$クラスに属する確率は$p_k$、確率分布のキニー指数は
$$ G(p)=\sum_{k=1}^{K} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{K} p_{k}^{2} $$
情報利得,利得率,キニー指数に加えて,決定ツリー分割選択のための多くの他の準則も設計されている.
しかし,これらの準則は決定ツリーのサイズに大きな影響を及ぼすが,汎化性能に及ぼす影響は限られていることが実験的に示された.
枝を切る
決定ツリーの欠点には、未知のテストデータに対して必ずしも良い分類、汎化能力があるとは限らない.すなわち、フィット現象が発生する可能性がある.この場合、剪定枝やランダム森林を採用することができる.
剪定は決定木学習アルゴリズムが「オーバーフィット」に対処する主な手段である.
意思決定ツリー学習では、できるだけ正確に訓練サンプルを分類するために、結点区分過程が繰り返され、意思決定ツリーの分岐が多すぎる場合がある.この場合、訓練サンプルがよく勉強されているため、訓練セット自体のいくつかの特徴をすべてのデータが持つ一般的な性質としてフィッティングしすぎる可能性がある.
ID 3決定ツリーコード
参照Machine Learning in Actionby Peter Harrington
# coding = utf-8
from math import log
import numpy as np
from collections import Counter
class DecisionTree:
"""ID3 DecisionTree
"""
def __init__(self):
self.decisionTree = None
self._X = None
self._y = None
#
def calcShannonEnt(self,y):
lablesCounter = Counter(y)
shannonEnt = 0.0
for num in lablesCounter.values():
p = num / len(y)
shannonEnt += -p * log(p,2)
return shannonEnt
def fit(self, X, y):
self._X = X
self._y = y
self.decisionTree = self.createTree(self._X,self._y)
return self
def splitDataset(self,X,y,d,value):
features = X[X[:,d]==value]
labels = y[X[:,d]==value]
return np.concatenate((features[:,:d],features[:,d+1:]),axis=1), labels
def chooseBestFeatureToSplit(self,X,y):
numFeatures = X.shape[1]
baseEntropy = self.calcShannonEnt(y)
bestInfoGain, bestFeature = 0.0, -1
for i in range(numFeatures):
#
uniqueVals = np.unique(X[:,i])
newEntropy =0.0
#
for value in uniqueVals:
_x, _y = self.splitDataset(X,y,i,value)
prob = len(_x)/len(X)
newEntropy += prob * self.calcShannonEnt(_y)
infoGain = baseEntropy - newEntropy
if infoGain>bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
def majorityCnt(self,y):
lablesCounter = Counter(y)
return lablesCounter.most_common(1)[0]
def createTree(self,X,y):
#
if y[y == y[0]].size == y.size :
return y[0]
#
if X.shape[1] == 0:
return self.majorityCnt(y)
bestFeat = self.chooseBestFeatureToSplit(X,y)
decisionTree = {bestFeat: {}}
for value in np.unique(X[:,bestFeat]):
decisionTree[bestFeat][value] = self.createTree(*self.splitDataset(X,y,bestFeat, value))
return decisionTree
if __name__ == '__main__':
dataSet = np.array([[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']])
labels = ['no surfacing', 'flippers']
dt = DecisionTree()
X = dataSet[:, :2]
X = X.astype(np.int)
y = dataSet[:,-1]
dt.fit(X,y)
print(dt.decisionTree)リファレンス
機械学習の-一般的な決定木アルゴリズム(ID 3、C 4.5、CART)
けっていじゅ
意思決定ツリー(Decision Tree):わかりやすい紹介
機械学習-周志華
Machine Learning in Action by Peter Harrington