![ジニ不純度を算出するプログラム
def giniimpurity(rows):
total=len(rows)
counts=uniquecounts(rows)
imp=0
for k1 in counts:
p1=?oat(counts[k1])/total
for k2 in counts:
if k1==k2: continue
p2=?oat(counts[k2])/total
imp+=p1*p2
return imp
rows
?→ジニ不純度計算対象のデータ集合
uniquecounts(rows)
?→集合に属す要素の目的変数に関する
??度数分布を算出
None : 7
Basic : 6
Premium : 3](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-26-320.jpg)
![エントロピーを算出するプログラム
def entropy(rows):
from math import log
log2=lambda x:log(x)/log(2)
results=uniquecounts(rows)
ent=0.0
for r in results.keys():
p=?oat(results[r])/len(rows)
ent=ent-p*log2(p)
return ent
rows
?→エントロピー計算対象のデータ集合
uniquecounts(rows)
?→集合に属す要素の目的変数に関する
??度数分布を算出
None : 7
Basic : 6
Premium : 3](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-31-320.jpg)
![情報ゲイン
?集合の分類操作によるエントロピーの減少量
? 分類後のエントロピーは、真集合のエントロピーと偽集合のエント
ロピーの加重平均としている
? 分類操作によってどれだけ集合がきれいに分割されたかを示す
? （エントロピーではなくジニ不純度を使っても良い）
gain = [分類前のentropy] - [分類後のentropy]
[分類後のentropy] = tr entropy(真集合) + (1 - tr) entropy(偽集合)
（tr = [分類後の真集合要素数] / [分類前の集合要素数]）](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-32-320.jpg)
![決定木の構築プログラム
def buildtree(rows,scoref=entropy):
if len(rows)==0: return decisionnode()
current_score=scoref(rows)
best_gain=0.0
best_criteria=None
best_sets=None
column_count=len(rows[0])-1
for col in range(0,column_count):
column_values={}
for row in rows:
column_values[row[col]]=1
###（続く）
分類前のエントロピー
（ or ジニ不純度）
各説明変数に対するループ](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-40-320.jpg)
![決定木の構築プログラム
###（続き）
for value in column_values.keys():
(set1,set2)=divideset(rows,col,value)
# Information gain
p=?oat(len(set1))/len(rows)
gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
if gain>best_gain and len(set1)>0 and len(set2)>0:
best_gain=gain
best_criteria=(col,value)
best_sets=(set1,set2)
if best_gain>0:
trueBranch=buildtree(best_sets[0])
falseBranch=buildtree(best_sets[1])
return decisionnode(col=best_criteria[0],value=best_criteria[1],
tb=trueBranch,fb=falseBranch)
else:
return decisionnode(results=uniquecounts(rows))
情報ゲイン
現ループの説明変数
が取り得る各値に対す
るループ
分類した真集合と偽集合に対
して再帰的に木を構築
部分木のルートノー
ド返却
帰結を返却](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-41-320.jpg)
![構築した決定木による予測プログラム
def classify(observation,tree):
if tree.results!=None:
return tree.results
else:
v=observation[tree.col]
branch=None
if isinstance(v,int) or isinstance(v,?oat):
if v>=tree.value: branch=tree.tb
else: branch=tree.fb
else:
if v==tree.value: branch=tree.tb
else: branch=tree.fb
return classify(observation,branch)
葉に り着いたら、
帰結を返却する
再帰的に木を る](https://image.slidesharecdn.com/tokyoci20130212publish-130212100905-phpapp02/85/-42-320.jpg)
集合知プログラミング勉強会 ７章（前半）
- 1. 集合知プログラミング勉強会 ７章 決定木によるモデリング (前半) 2013.02.12 #TokyoCI 担当 : @_kobacky
- 5. こんなデータが取れました ユーザーの行動と購入サービス （学習データ） リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Premium Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic ???その他9件のユーザーのデータ
- 6. そこに新規無料ユーザー来たる！ リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Premium Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic ???その他9件のユーザーのデータ リファラー 住所 FAQ読？ 見たページ数 購入サービス （直接） USA Yes 5 ？？？ ユーザーの行動と購入サービス （学習データ） 購入サービスのわからない新規無料ユーザーの行動（評価データ）
- 7. そこに新規無料ユーザー来たる！ リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Premium Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic ???その9件のユーザーのデータ リファラー 住所 FAQ読？ 見たページ数 購入サービス （直接） USA Yes 5 ？？？ ユーザーの行動と購入サービス （学習データ） 購入サービスのわからない新規無料ユーザーの行動（評価データ） サービスを購入するのか？ 生データからは判断困難。
- 8. そこで决定木です
- 9. 学習データから決定木を構築 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 3 no yes ※注 本章のプログラム?サンプルデータで生成される決定木は ???正確には「None : 3, Basic : 1」の部分がさらに分類されます。
- 10. 決定木とは ? 予測モデルの一つ ? 目的変数が同じデータがなるべく同グループに属するよ うデータを分類する分岐条件を表す木構造。分岐条件は 説明変数によって表される。 ? 目的変数：予測したい変数（「購入サービス」） ? 説明変数：目的変数の要因となる変数（「リファラ」「住所」など） ? 決定木の構成要素 ? 枝（ノード）：分岐条件のこと ? 葉（帰結）：条件分岐を った結果の帰結 ref = google ? Basic : 4
- 11. 評価データの購入サービスを予測 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 1 no yes ref = (direct) address = USA FAQ = Yes page = 5 評価データ
- 12. 評価データの購入サービスを予測 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 1 no yes ref = (direct) address = USA FAQ = Yes page = 5 評価データ
- 13. 評価データの購入サービスを予測 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 1 no yes ref = (direct) address = USA FAQ = Yes page = 5 評価データ
- 14. 評価データの購入サービスを予測 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 1 no yes ref = (direct) address = USA FAQ = Yes page = 5 評価データ
- 15. 評価データの購入サービスを予測 ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 1 no yes ref = (direct) address = USA FAQ = Yes page = 5 評価データ Basicサービス購入者4人の帰結に到達。 評価データのユーザーはBasicサービスを 購入すると予測できる。
- 17. もう一度決定木を眺めてみると?? ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 3 no yes
- 18. もう一度決定木を眺めてみると?? ref = google ? ref = slashdot ? page >= 21 ? FAQ = Yes ? FAQ = Yes ? None : 3 Basic : 1 Basic : 4 None : 3 None : 1 Basic : 1 Premium : 3 no yes なぜ「リファラーが googleか否か」で分 類するのか？？
- 20. そもそも有効な分類条件とは？ リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Basic Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic
- 21. そもそも有効な分類条件とは？ リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Basic Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic address = USA ? page >= 23 ? None : 2 Basic : 3None : 1 Basic : 2 None : 1 Basic : 1 no yes no yesどっち？
- 22. そもそも有効な分類条件とは？ リファラー 住所 FAQ読？ 見たページ数 購入サービス Slashdot USA Yes 18 None Google France Yes 23 Basic Slashdot UK No 21 None Digg USA Yes 24 Basic Kiwitobes France Yes 23 Basic page >= 23 ? None : 2 Basic : 3 no yes こっち！ address = USA ? None : 1 Basic : 2 None : 1 Basic : 1 no yes 購入サービスがよりきれいに 分類される条件の方が良い
- 24. ジニ不純度とは ?集合中のアイテムの一つに、ランダムに帰結を 当てはめる場合の期待誤差率 ? 値が高いほど集合の要素はバラついている ?giniimpurity = Σ (P( a ) P( a )) ? a ∈ A = {None, Basic, Premium} ? P( a ) ：集合A内の要素aが選ばれる確率 ? P( a ) ：要素aに対して誤った帰結が当てはめられる確率 a ∈ A
- 25. ジニ不純度の計算例 None : 7 Basic : 6 Premium : 3 0 2 4 6 None Basic Premium giniimpurity = (7/16 9/16) + (6/16 10/16) + (3/16 13/16) = 0.6328 None : 3 Basic : 1 0 2 4 6 None Basic giniimpurity = (3/4 1/4) + (1/4 3/4) = 0.375 ① ②
- 26. ジニ不純度を算出するプログラム def giniimpurity(rows): total=len(rows) counts=uniquecounts(rows) imp=0 for k1 in counts: p1=?oat(counts[k1])/total for k2 in counts: if k1==k2: continue p2=?oat(counts[k2])/total imp+=p1*p2 return imp rows ?→ジニ不純度計算対象のデータ集合 uniquecounts(rows) ?→集合に属す要素の目的変数に関する ??度数分布を算出 None : 7 Basic : 6 Premium : 3
- 27. エントロピー ?集合中の無秩序の量 ?(p161 より引用) ? 値が大きいほど集合は無秩序。 ?entropy = -1 Σ(P( a ) logP( a )) ? a ∈ A = { None, Basic, Premium } ? logの底は2 a ∈ A
- 28. エントロピーの計算例 None : 7 Basic : 6 Premium : 3 0 2 4 6 None Basic Premium entropy = -1 ((7/16 log(7/16)) + (6/16 log(6/16)) + (3/16 log(3/16))) = 1.5052 None : 3 Basic : 1 0 2 4 6 None Basic entropy = -1 ((3/4 log(3/4)) + (1/4 log(1/4))) = 0.8112 ① ②
- 29. エントロピーの比較① （集合の要素数固定で比較してみた） None : 5 Basic : 1 0 2 4 6 None Basic entropy = -1 ((5/6 log(5/6)) + (1/6 log(1/6))) = 0.6500 None : 3 Basic : 3 0 2 4 6 None Basic entropy = -1 ((3/6 log(3/6)) + (3/6 log(3/6))) = 1.0000 ① ②
- 30. エントロピーの比較② （各クラスの要素数固定で比較してみた） None : 2 Basic : 2 0 2 4 6 None Basic entropy = -1 ((2/4 log(2/4)) + (2/4 log(2/4))) = 1.0000 None : 2 Basic : 2 Premium : 2 0 2 4 6 None Basic Premium entropy = -1 ((2/6 log(2/6)) + (2/6 log(2/6)) + (2/6 log(2/6))) = 1.5850 ① ②
- 31. エントロピーを算出するプログラム def entropy(rows): from math import log log2=lambda x:log(x)/log(2) results=uniquecounts(rows) ent=0.0 for r in results.keys(): p=?oat(results[r])/len(rows) ent=ent-p*log2(p) return ent rows ?→エントロピー計算対象のデータ集合 uniquecounts(rows) ?→集合に属す要素の目的変数に関する ??度数分布を算出 None : 7 Basic : 6 Premium : 3
- 32. 情報ゲイン ?集合の分類操作によるエントロピーの減少量 ? 分類後のエントロピーは、真集合のエントロピーと偽集合のエント ロピーの加重平均としている ? 分類操作によってどれだけ集合がきれいに分割されたかを示す ? （エントロピーではなくジニ不純度を使っても良い） gain = [分類前のentropy] - [分類後のentropy] [分類後のentropy] = tr entropy(真集合) + (1 - tr) entropy(偽集合) （tr = [分類後の真集合要素数] / [分類前の集合要素数]）
- 33. 情報ゲインの計算例 (分岐条件を決めて、集合を分類) None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes
- 34. 情報ゲインの計算例 (各集合のエントロピーを計算) None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes 1.5052 1.37100.9940
- 35. 情報ゲインの計算例 (分類後集合のエントロピーを加重平均で計算) None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes 1.5052 1.37100.9940 0.9940 11/16 + 1.3710 5 / 16 = 1.1118
- 36. 情報ゲインの計算例 (分類後の集合エントロピーを加重平均で計算) None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes 1.5052 1.37100.9940 0.9940 11/16 + 1.3710 5 / 16 = 1.1118 Gain = 1.5052 - 1.1118 = 0.3934
- 37. 分類条件の決定 ? 全ての分類条件で情報ゲイン計算して、情報ゲイン が最大になる条件を選んでいるだけ。 ? リファラーがGoogle？ ? FAQ読んだ？ ? 見たページ数 >= 18 ? ? 見たページ数 >= 21 ? ? ???etc (全部です) ? 本章のデータでは「 リファラーがGoogle？」で分 類すると情報ゲインが最大になる。
- 38. あとは再帰的に分類して決定木を構築 None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes さらに分類処理 さらに分類処理
- 39. あとは再帰的に分類して決定木を構築 None : 7 Basic : 6 Premium : 3 None : 6 Basic : 5 Premium : 0 None : 1 Basic : 1 Premium : 3 ref = google ? no yes さらに分類処理 さらに分類処理 集合に対する（最良の）分類 による情報ゲインが正( > 0) である限り分類を繰り返す。
- 40. 決定木の構築プログラム def buildtree(rows,scoref=entropy): if len(rows)==0: return decisionnode() current_score=scoref(rows) best_gain=0.0 best_criteria=None best_sets=None column_count=len(rows[0])-1 for col in range(0,column_count): column_values={} for row in rows: column_values[row[col]]=1 ###（続く） 分類前のエントロピー （ or ジニ不純度） 各説明変数に対するループ
- 41. 決定木の構築プログラム ###（続き） for value in column_values.keys(): (set1,set2)=divideset(rows,col,value) # Information gain p=?oat(len(set1))/len(rows) gain=current_score-p*scoref(set1)-(1-p)*scoref(set2) if gain>best_gain and len(set1)>0 and len(set2)>0: best_gain=gain best_criteria=(col,value) best_sets=(set1,set2) if best_gain>0: trueBranch=buildtree(best_sets[0]) falseBranch=buildtree(best_sets[1]) return decisionnode(col=best_criteria[0],value=best_criteria[1], tb=trueBranch,fb=falseBranch) else: return decisionnode(results=uniquecounts(rows)) 情報ゲイン 現ループの説明変数 が取り得る各値に対す るループ 分類した真集合と偽集合に対 して再帰的に木を構築 部分木のルートノー ド返却 帰結を返却
- 42. 構築した決定木による予測プログラム def classify(observation,tree): if tree.results!=None: return tree.results else: v=observation[tree.col] branch=None if isinstance(v,int) or isinstance(v,?oat): if v>=tree.value: branch=tree.tb else: branch=tree.fb else: if v==tree.value: branch=tree.tb else: branch=tree.fb return classify(observation,branch) 葉に り着いたら、 帰結を返却する 再帰的に木を る