English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
一、決定木の原理
決定木はサンプルの属性をノードとして、属性の値を枝としての木構造です。
決定木の根ノードはすべてのサンプルの中で情報量が最大の属性です。中間ノードはそのノードが根であるサブツリーに含まれるサンプルのサブセットの中で情報量が最大の属性です。決定木の葉ノードはサンプルのカテゴリ値です。決定木は知識表現の形式であり、すべてのサンプルデータの高度な要約です。決定木はすべてのサンプルのカテゴリを正確に識別し、新規サンプルのカテゴリも効果的に識別できます。
決定木アルゴリズムID3の基本思想は：
まず最も判別力のある属性を見つけ、サンプルを複数のサブセットに分け、各サブセットも最も判別力のある属性を選んで分類し、すべてのサブセットが同じタイプのデータのみを含むまで繰り返します。最終的には決定木が得られます。
J.R.Quinlanの仕事は、情報論における情報増益を導入し、それを情報増益（information gain）と呼び、属性の判別能力の測定として、決定木の再帰的な構築アルゴリズムを設計しました。
例を挙げることで理解しやすくなります：
気候分類問題において、属性は：
天気(A1値を取るのは：晴れ、曇り、雨
気温(A2値を取るのは：冷、適中、暑い
湿度(A3) 取值为：高 ，正常
風 (A4) 取值为：有风， 无风
各サンプルは異なるカテゴリに属しており、この例ではPとNの2つのカテゴリがあります。PクラスとNクラスのサンプルはそれぞれ正例と反例と呼ばれます。既知の正例と反例を組み合わせてトレーニングセットを得ます。
から、3アルゴリズムはトレーニングセットの各サンプルを正しく分類する決定木を導き出します。以下の図を参照してください。
決定木の葉はカテゴリ名であり、PまたはNです。他のノードはサンプルの属性で構成されており、各属性の異なる値に対応する枝があります。
サンプルを分類する場合、木の根からテストを開始し、属性の値に基づいて枝を分岐して下層のノードに入ります。そのプロセスは葉ノードまで続けられ、サンプルはその葉ノードに記載されたカテゴリに分類されます。
図を使用して具体的な例を判別します。
ある朝の気候の説明は：
天気：曇り
気温：冷
湿度：正常
風：無風
それはどの気候に属しているのでしょうか？63;-------------から図を見て、そのサンプルがPクラスであると判別できます。
ID3すなわち、トレーニングセットのテーブルから図のような決定木を構築することです。実際には、トレーニングセットを正しく分類する決定木は複数あります。QuinlanのID3アルゴリズムはノード数の少ない決定木を導き出すことができます。
ID3アルゴリズム：
1。現在のサンプルセットに対して、各属性の情報增益を計算します；
2。情報增益が最大の属性Akを選択します；
3。同じ属性値を持つサンプルを同じサブセットにまとめます；
4。既に正例と反例を含む子集に対して、再帰的に決定木構築アルゴリズムを呼び出します；
5。子集が正例や反例のみを含む場合、枝にPまたはNを付けて、呼び出し元に戻ります。
一般に、木の構造に関連する場合は、再帰をよく使用します。
気候分類問題に対する具体的な計算には、
1、情報エントロピーの計算: その中で、Sはサンプルの集合であり、P(ui)はカテゴリiが現れる確率です：
|S|はサンプルセットSの総数を表し、|ui|はカテゴリuiのサンプル数を表します。以下に、9個正例と5個反例があります：
P（u1）=9/14
P（u2）=5/14
H（S）=（9/14）log（14/9）+（5/14）log（14/5）=0。94ビット
2、情報增益の計算:
で、Aは属性であり、Value(A)は属性Aの値の集合であり、vはAの特定の属性値であり、SvはSの中でAの値がvを持つサンプルの集合であり、| Sv |はSvの中に含まれるサンプルの数です。
で属性A1として、情報增益の計算公式に基づいて、属性A1の情報增益が
S=[9+,5-] //元のサンプルセットには14個サンプル、9個正例、5個反例、
S晴=[2+,3-]//属性A1晴の値を持つサンプルが5個、2正、3反
S多云=[4+,0-] //属性A1、04個、4正、0反
S雨=[3+,2-] //属性A1晴の値を持つサンプルが5個、3正、2反
ですので、
3、結果が
属性A1の情報增益が最大であるため、根ノードとして選ばれました。
4、決定木の根と葉の
ID3アルゴリズムは、情報增益が最大の属性「天気」を選択して木の根として、14の例に対して天気の3の値に対して枝を分岐します3 枝に対応します3 サブセットは、以下の通りです:
中のS2の例がすべてPクラスに属しているため、対応する枝はPとマークされます。残りの2つのサブセットには正例と負例が含まれており、再帰的に木構築アルゴリズムを呼び出します。
5、再帰的に木を構築します
それぞれS1とS3子集に再帰的にIDを呼び出します3アルゴリズムでは、各属性に対して各子集中の情報増益を求めます。
（1）Sに対して1湿度属性の情報増益が最大であり、それが枝の根节点として選ばれます。さらに枝を分岐し、湿度が高い例はすべてNクラスとされ、その枝はNとマークされます。湿度が通常の例はすべてPクラスとされ、その枝はPとマークされます。
（2）Sに対して3風属性の情報増益が最大であり、そのためそれが枝の根节点として選ばれます。さらに枝を分岐し、風が強い場合、すべての例がNクラスとされ、その枝はNとマークされます。風が無い場合、すべての例がPクラスとされ、その枝はPとマークされます。
二、PYTHONで決定木アルゴリズムを実装する
本コードはmachine learning in action 第三章の例で、正確であることが確認されています。
1与指定データセットのshannonエントロピーを計算する関数：
def calcShannonEnt(dataSet):
#calculate the shannon value
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #create the dictionary for all of the data
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2) #get the log value
return shannonEnt
2データを作成する関数
def createDataSet():
dataSet = [[1,1']
[1,1, 'yes'],
[1,0,'no'],
[0,1']
[0,1']
labels = ['no surfacing','flippers']
return dataSet, labels
3.劃分數據集，按照給定的特徵劃分數據集
def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: #抽象該特徵 reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
4.選擇最好的數據集劃分方式
def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0])-1 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 for i in range(numFeatures): featList = [example[i] for example in dataSet] uniqueVals = set(featList) newEntropy = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i , value) prob = len(subDataSet)/float(len(dataSet)) newEntropy +=prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
5.遞迴創建樹
用於找出出現次數最多的分類名稱的函數
def majorityCnt(classList):
classCount = {}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
樹の作成を行う関数のコード
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
# タイプが同じなら、分類を停止します
if classList.count(classList[0]) == len(classList):
return classList[0]
# 全ての特徴量をトラバースし、最も頻繁な特徴量を選択します
if (len(dataSet[0]) == 1):
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
# 全ての属性を取得するリストを取得します
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return myTree
次に、Pythonのインデントに以下のコマンドを入力します：
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
結果は：
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
6.実際の決定木を用いた分類の関数
def classify(inputTree, featLabels, testVec):
firstStr = inputTree.keys()[0]
secondDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testVec[featIndex] == key:
if type(secondDict[key]).__name__ == 'dict':
classLabel = classify(secondDict[key], featLabels, testVec)
else: classLabel = secondDict[key]
return classLabel
Pythonのコマンドプロンプトで、以下を入力：
trees.classify(myTree,labels,[1,0])
結果を得ます：
'no'
おめでとう。ああだね。あなたはそれを達成した。!!!
これで本記事の全ての内容が終わりました。皆様の学習に役立つことを願っています。また、呐喊ガイドを多くのサポートをお願いします。
声明：本記事の内容はインターネットから収集され、著作権者に帰属します。インターネットユーザーが自発的に貢献し、自己でアップロードした内容です。本サイトは所有権を有しなく、人工的な編集を施しておらず、関連する法的責任も負いません。著作権に疑われる内容がある場合は、以下のメールアドレスまでご連絡ください：notice#oldtoolbag.com（メールを送信する際は、#を@に変更してください）で通報し、関連する証拠を提供してください。一旦確認が取れましたら、本サイトは即座に侵害を疑われるコンテンツを削除します。