第３回 森林・林業形成研究会 2009/7/24(Fri.)18:00- Today's Title 「非線形森林科学と森林データマイニング」 京都府立大学大学院 生命環境科学研究科 森林科学科 流域情報学研究室 美濃羽 靖 Today's Contents 1. 非線形な現象を取り扱いたいので．．． 2. データマイニングとは WEKAを使ってみる 3. 実際に適用してみよう 1) とりあえず，なんかデータを放り込んで，なんか結果を出力さ せたい。ついでにコンピュータが学習してくれるとありがたい。 ->ニューラルネットワーク 2) 出力結果が誰にでもわかる形，人間がわかる形で出力させたい ->言語情報による出力->機械学習，決定木（樹木モデル） 3) あんまり良い結果がでないし，データ数も少ないけど，なんと か良く（推定精度）ならないかな。->集団学習アルゴリズム， 交差検証法 非線形森林科学 線形と非線形の違いは？ 自然界の現象の多くは 複雑なシステムを形成している→「非線形」 まさにそう？ 非線形現象を線形理論に帰 着することなく取り扱うこと のできる手法 森林科 学 適用してみよう （工学的アプローチ） ：ニューラルネットワーク， 遺伝的アル ゴリズムetc （人工知能アプローチ） :ファジィ，エキスパートシステムetc データマイニング（Data Mining) 膨大なデータの山から宝物（情報，知識）を掘り出す（採鉱，mining）技法 や方法論の体系。1990年代中頃から。テキストマイニング，Webマイニング などが派生（金，2007）。KDD:knowledge-discovery in databases （データベースからの知識発見）とも呼ばれる。 概念としては，従来のデータ解析や統計学と同様であろうが，近年では，コン ピュータ資源の発達により，大量のデータの蓄積・処理が可能になったことから 「膨大なデータの集合（データベース含む）から有用な情報を抽出する技術 （Hand et al, 2001）」あるいは「今まであまり知られていなかったが，役立つであ ろうと考えられる情報をデータから抽出する方法（Frawley et al, 1992）」といった 意味で使われることが多い。 例）（金，2007） スーパーやコンビニの顧客履歴データベースから，商品を購買する際 の商品の組み合わせに関するパターンを抽出し，得られた知見に基づい て商品の陳列を見直す。 病院におけるカルテのデータベースから病気診断の知識を見つけ出す。 WEKA 1. 2. フリーのデータマイニングツール オープンソース開発 1. 2. 3. 3. 4. Waikato(ワイカト）大学（ニュージーランド）が中心となって開発 1. Witten,Frankらの機械学習の専門家が中心 Webから入手可能（無償） 1. http://www.cs.waikato.ac.nz/ml/weka/ 誰もがソースコードにアクセスでき，改変・再配布可能 最新版はVersion 3.6.1 Java言語により実装（＝マルチプラットホーム） 1. Windows/MacOS X/UnixのJAR(ZIP)の各形式のパッケージにより配布 API，CLI，GUIの各インターフェイスを備える 数多くのデータマイニング手法が利用可能 各種の可視化機能が提供される 商用データマイニングツールに迫る機能や品質 研究段階のアルゴリズムも実行可能 ユーザの試行錯誤により，新たなデータマイニングプロセスが実行可能 ソースコードが公開されているため，アルゴリズムの教育目的に利用可能 アルゴリズムとアルゴリズム内のパラメータが整理されている etc… （阿部ら,2004）第19回 AIシンポジウム資料より What WEKA? WEKA is bird. Copyright: Martin Kramer ([email protected]) （Frank,2006) University of Waikato WEKAのインターフェイス 起動：①．アプリケーションをクリック ②．コマンドラインから 例）>java –Xmx256m –jar weka.jar 【Simple CLI】 各クラスを個々に実行 【Explorer】 対話的に利用するため のUI 【Experimenter】 アルゴリズム，データの 比較ができる 【Knowledge Flow】 可視化して実行できる UI Explorer Data Input 画面 データの 読み込み 属性の 表示 図示 Explorer Classify 画面 選択された アルゴリズム 交差検証法 結果の表示 Knowledge Flow Wekaでできること 入力方法 欠点・Javaなので，重い。 ・でかいデータはメモリーエラー ARFFファイル，CSV (Comma Separated Values)形式ファイル，C4.5形式ファイル RDB (Relational Database） 出力方法 テキスト・オブジェクトファイルによる実行結果 可視化（グラフ，２次元プロット）による実行結果 フィルタ 分類学習・数値予測アルゴリズム メタスキーム（分類学習・数値予測アルゴリズムを内包し，分類・予測精度を向上する） AdaBoost,Bagging,Stacking etc… クラスタリング・相関ルール学習アルゴリズム ベイズ則に基づくアルゴリズム（確率モデル，ナイーブベイズetc） 関数型アルゴリズム（線形回帰，ニューラルネットワークetc） インスタンスに基づく分類器（K-Nearest Neighbours，K*アルゴリズムetc) 決定木・モデル木学習アルゴリズム（C4.5，M5，PARTetc) その他 EMアルゴリズム，距離尺度に基づく非階層的クラスタリングetc 相関ルール アプリオリアルゴリズム，Tertius etc… 11 （阿部ら,2004）第19回 AIシンポジウム資料より データマイニングの流れ データの獲得 ・・・データベース，調査 データ ・・・（質的，量的）データ，（名義，順序，間隔，比）尺度 の加工 モデル選択 ・・・各種予測，分類モデル 実 行 ・・・WEKA,R，独自プログラム 結 果 ・・・推定精度，判別率，正答率，汎化 モデル選択 パターン分析における識別問題 B A うまく分離（分類）するた めには識別線をどこに引 いたらよいでしょうか？ ペンを渡されたら….. じゃあ，なぜ，こう引かないのか 大半の人はこんな 風に線を引くだろう クラスAの周りの領域がクラスBのデータの周り の領域より大きすぎるから →「クラスBの汎化能力が低くなる」 最も適した識別境界を見つける ◆ パラメトリックな方法 母集団の特性を規定する母数についてある仮説を設定する。パターン 分析的には，統計的な学習データの分布を考えて識別境界を引く方法 母集団 分布型は既知（あるいは仮定） ◆ サンプル 未知データに対する予測 の信頼性をある程度，保 証できる。ただし，母集団 が既知なのは稀。 ノンパラメトリックな方法 集団の分布型（母数）について一切の仮定を設定しない。パターン分 析的に言えば，与えられた学習データをすべて正しく識別できるよう にする方法 サンプルが母集団。未知デ ータに対する予測は信頼さ れない（汎化性の問題） 母集団 分布型は問わない サンプル ３つの主な学習の枠組み ◆ （銅谷,2006) 目標出力 教師あり学習 入力に対する正しい出力が教師信号として与えられ， 教師信号 実際に出した出力との誤差信号がゼロになるように学 習が行われる（パーセプトロン）。 識別機 入力 出力 ◆ 強化学習 いつどこでどういう出力を出せば良いかという具体的な教師信号は与 えられない。その代わり，実際に出してみた出力に対して，それがどれ くらい良かったかを示す「報酬信号」が与えられ，これをなるべく大きく 報酬信号 するように探索的に学習が行われる。 動物や人間の試行錯誤的な行動学習の 過程のモデル ◆ 教師なし学習 入力 識別機 出力 どういう出力を出すべきかは全く教えられない。それでなぜ学習でき るかというと，入力信号の統計的な分布に着目し，データをクラス分 けしたり，成分に分解したりという形で学習が行われる（クラスタリン グ，自己組織化マップ，主成分分析，独立成分解析） 高次元のデータの圧縮，解析の前処理 入力 識別機 出力 林業技術の中には，林業技術者が持つ高度な「経験則」や 「勘」を要するものがある。 例) 目測による樹高測定，樹形級区分， 間伐木・伐採木の選定， 森林経営計画における意思決定 etc.... 様々な種類 のデータ 入力 1. 線形 or 非線形 2. 量的 or 質的 3. 比尺度, 間隔尺度, 順序尺度，名義尺度 ・経験 則 ・勘.... Black-Box 出力 Results i.e.) 「間伐する」？ :定量的な評価は難し 「間伐しない」？ い :すべての人が理解で きるわけではない 人間が持つ高度な識別機能を模倣しよう 内部構造は不明だが， 人間の脳機能を模倣 している 理論はさ ておき とりあえず 放り込め Black-Box 出力結果は？ ニューロ，ファジィ... ごちゃまぜなんですが... 定性的/ 定量的 線形/ 非線形 それらしい結果 が出てくるので 質的/量的 入力データ 出力データ 間伐木の選定 欠点 樹冠量 ・経験則 ・勘 樹高 DBH 森林調査 選木 間伐 間伐木の選定に用いられる情報（データ）には 質的（qualitative），量的（quantitative）データが混在 脳の学習機構を応用した間伐木選定モデル 研究(1) 関数型を仮定することなく，モデルを組み立てられる方法として， ニューラルネットワークを適用する。 研究(2) 新たなモデルとして，機械学習システムC4.5（樹木モデル，決定木）を 適用し，ニューラルネットワークモデルとの比較・検討を行う。 研究(3) 集団学習アルゴリズムとm重交差検証法を適用し，これまで構築した モデル（ニューラルネットワークモデル，樹木モデル）のモデル精度と汎 化性を検証する。また，WEKAに内在する様々な分類アルゴリズムを 適用し，比較・検討する。 調査対象地と資料 東京大学大学院農学生命科学研 究科附属 科学の森教育研究セン ター 千葉演習林 ２つの試験地（スギ人工林）に おける間伐木選定調査のデー タを利用 試験地 名 面積 林齢 立木本 数 平均樹 高 平均直 径 郷田倉 27C4 1.10 99 503 31.8 46.8 一杯水 46C1 0.54 99 281 24.8 35.1 （千葉演習林パンフレット，2002） ニューラルネットワークモデル(Artificial Neural Network) Brain Neuron 人間の脳は約10 11 個以上の神経細胞（ニューロン：Neuron）と約10 15個のシナプス (Synapse)結合から成る巨大なネットワークで構成されている。ニューロンはシナプス 結合を通じて他のニューロンからの信号を受け取り，その総和があるしきい値を越え ると発火し，その発火した信号は軸索(Axon)を通じて他のニューロンに伝達される。こ のプロセスを単純化してニューロンを簡単なモデルで表すと，ニューロンはシナプス結 合の強さを示す重み係数（シナプス荷重）としきい値およびニューロンの入出力特性 関数だけで記述することができる。 脳の情報処理システムを数学的に表現する 重み 入力 z1 x1 出力 出力 y1 zj xn ym zh 入力 重み h O n n H T T H O y(t) 1 wixi(t) 1w x(t) z j g w jk x k w jo , y j g w ij x k w io k1 i1 j1 1 1 if u > 0 g(u) u 1u 1 e 0 otherwise ２種類のニューラルネットワーモデル ニューラルネットワークはニューロン間の結合の方法によって分類することによ り，下図に示すように「相互結合（リカレント）型」と「階層型」の２種類に大別する ことが出来る。階層型ニューラルネットワークは，基本的にはユニット間の情報 （信号）の流れは一方通行である。代表的なものとしては，Rosenblattが1957 年に提案したパーセプトロンやD.E.Rumelhartらにより1986年に提案されたバ ックプロパゲーション等があげられる。一方，相互結合型ニューラルネットワーク は，情報の流れは双方向的でフィードバックが存在するのが特徴である。代表 的なものとしては，J.J.Hopfieldが1982年に提案したホップフィールド・ネット ワークやG.E.Hintonらによって1984年に提案されたボルツマン・マシン等があ げられる。 教師なし モデル 相互結合型ニューラルネットワーク 教師あり モデル 階層型ニューラルネットワーク ニューラルネットワークは非常に単純であるため，コンピュータ・プログラムで容易に シミュレすることができる。さらに，これらをたくさん用意し接続すると神経回路網全 体のモデルが出来上がる。このような神経回路網のシミュレーションモデルをニュー ラルネット（artificial neural network），ニューラルネットを使った計算をニューロコン ピューティング（neuro-computing）と呼んでいる（星ら,1990）。応用範囲としては学 習・認識・直感・類推を得意とする。用途としては，パターン処理・運動処理・曖昧処 理・連想記憶などがある。特徴としては，並列分散処理・自己組織化機能・学習の一 般化能力・情報の分散表現性などがあげられる（星ら,1990） 。 排他的論理和の問題 期待される応用分野例（中野ら,1989） 階層型ニューラルネットワークのアルゴリズム L 1 2 H j f Vij Ii A j , f (x) = , f (x) = f (x) (1 f (x)) 2x i1 0 1 +exp(- ) 0 入力データ 入力層 I1 I2 IL Vji M Ok f W kj H j Bk j1 誤差二乗和Ｅが最小になるように各ニューロンの結合 係数およびしきい値を修正することで学習が進む。 中間層の結合係数およびしきい値の修正量をΔＶｊｉ，Δ Ａｊとおくと，修正前の結合係数およびしきい値をoldＶｊｉ， oldＡｊ，修正後の結合係数およびしきい値をnewＶｊｉ， newＡｊとして， V oldVij V ji, new ij new A1 H1 A2 W kj oldW kj W kj , H2 結 合 係 数 AM HM Wkj A j old A j A j と表される。ただし，α，βはそれぞれ結合係数およびし 出力層 B1 きい値の学習係数である。αおよびβは大きい値をとる O1 と修正量も大きくなり学習も進むが，誤差最小の点に収 N 1 束しない可能性がある。出力層についても中間層の場 E T O 2 k k 2 k1 合と同様に， new new Bk old Bk Bk と表される。これらの修正量を最急降下法によって求め ていく。 中間層 誤差二乗和 T1 B2 BN O2 出力データ ON T2 TN 教師データ Backpropagation Method （誤差逆伝搬法） ニューラルネットワークのイメージ 通常のモデル(回帰分析etc) 入力 出力 X1 X2 Y1 Xn 多入力他出力 質的・量的データ混在 非線形構造もOK ニューラルネットワーク 入力層 X1 X2 Xn 中間層 H1 H2 Hn 出力層 Y1 Y2 Yn 最小二乗推定(Ordinary Least Square Estimate) Y ei Yi Yˆi Yi 重回帰分析のパラ メータを解析的に求 める際に利用 ↓ 解は一意的に決定す る。 Yi Yˆ a bX Xi 0 X ei Yi Yˆi Yi a bX i (i =1,2,...,n) Residuals n Select a, b to make e i1 Select a, b to minimize n 2 i Yi a bX i 0 2 i1 Σei2 ( e 2 ) ( e 2 ) 0 a b 評価関数を最適とするようなパラメータを求める →最急降下法（Steepest Descent Method) t番目の入力x（t）に対する出力y（t）の二乗誤差は E(t) 解析的にパラメータを求められない時に利用 ↓ 解は更新回数や初期値によって異なる 1 1m 2 y(t) yˆ (t) (y i (t) yˆ i (t))2 2 2 i=1 E(w) で与えられる。最小二乗誤差学習では， 1 T E E(t) T t1 を最小にするような結合荷重を探す。しかし， これらは陽に解けないので，ある適当な初期値 （初期パラメータ）からはじめて，その値を繰り返 し更新する（修正する）ことにより，最適なパラメ ータの値を求める方法を行う。 wi (t 1) = wi (t) - E(w(t)) E(t) w i E(w(t))における Wi方向の傾き E(t) wi E(w)を最小化する場合 E(t) wi E(w)を最大化する場合 wi (t 1) = wi (t) + E(t) wi 傾きが負→Wiを正の方向 E(w)は小さくなる 最小化の場合 w(t) w(t+1) E(w)を時刻tにおけるE(w(t))を通るwi-E(w)平面に平行な面で切った図 入力層 量的情報 直径，樹高 順序尺度 樹冠量{少，小，普通，大}，幹形質{悪い，普通，良 い} 名義尺度 腐り・キズ・曲がり・二又・樹冠小・小径木・枝下低・樹 冠偏り・先折れ・・・{ある，なし} 質的情報 入力層 因子 層数 直径(3) 樹高(3) 樹冠量(4) 幹形質(3) 欠点(10) ○ ー ー ー ー ３ 各因子のみ ー ○ ー ー ー ３ 〃 ー ー ○ ー ー ４ 〃 ー ー ー ○ ー ３ 〃 ー ー ー ー ○ １０ 〃 ○ ○ ー ー ー ６ 量的のみ ー ー ○ ○ ー ７ 質的のみ ○ ○ ー ー ○ １６ 量的+欠点 ー ー ○ ○ ○ １７ 質的+欠点 ○ ○ ○ ○ ○ ２３ 全因子 中間層，出力層 中間層：層数を１から２N+１（N:入力層数） 出力層 ３５１本 １５２本 出力が２段階 「間伐しない」or「間伐する」 出力が４段階 「間伐しない」ｏｒ「間伐する（３段階の間伐）」 間伐率（％） 間伐タイプ 本数 本数 材積 間伐前 間伐後 間伐前 間伐後 環境保全型 200 40 39.8 25 25.5 長伐期施業 型 93 60 58.3 40 42.8 複層林施業 型 58 70 69.8 55 55.0 データの正規化 N o DB H 樹高 樹冠量 幹形 質 １ 53.1 26.5 4 2 2 37.0 21.6 2 1 ３ 38.0 27.6 3 2 4 44.4 23.9 3 1 5 46.8 23.1 3 1 欠点 腐り キズ 二 又 曲り 冠 小 枝 下 小径 隣 接 偏 り 先 折 選木 結果 ◎ あり × あり あり あり △ あり ○ あり × データを０または１に正規化する 樹高 DBH No 小 中 大 小 中 樹冠量 大 少 小 普 幹形質 大 悪 普 良 欠点 腐 傷 曲 二 冠 小 選木結果 枝 隣 偏 先 ◎ X △ ○ １ 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 2 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 ３ 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 4 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 5 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 シミュレーションの条件 各試験地ごとで学習モデルを構築する。 ニューラルネットワークによる推定精度の検証 中間層数，出力層数，学習回数 学習済みパラメータを用いて，お互いを推定する。 要因別解析 Program: NEURO92 (築城ら、１９９３) (ワークステーション版階層型ニューラルネット構築プログラム) 中間層数：３から2n+1（n:入力層数） 学習回数：２,０００回 各種パラメータの設定 シミュレーティッド・アニーリン グ（シミュレーションによる焼き 鈍し） ニューラルネットワークによる推定結果 99.2 正答率(%) 100 77.9 99.2 94.3 正答率(%) 100 85.9 50 94.3 50 2 0 4 3 中間層数 2n+1 郷田倉27C4 (n：入力層数=23 データ数：503) 2 0 4 3 中間層数 2n+1 一杯水46C1 (n：入力層数=23 データ数：281) 学習済みネットワーク・パラメータの再帰的利用 96. 95. 4 8 96. 4 86. 86. 正答率(%) 83. 1 5 84. 100 6 7 100 50 50 0 中間層数 郷田倉27C4 ->一杯水46C1 正答率(%) 3 0 11 中間層数 2n+1 一杯水46C1->郷田倉27C4 要因別解析結果 推定精度（％） + 30% + 41% 70% + + 54% 中間層数=２ｎ+１ 出力層数=4 直径 + 77% 65% 全因子 =85.9 64% 樹高 樹冠量 + 幹形質 欠点 研究（２） 機械学習を用いた間伐木の推定 機械学習とは，人間が日常的にやっているが，どうやってやってい るかは自分でもよくわからないことを機械化する手段として発展。 適切な事前知識（バイアス） があり，十分な量の学習用 データがあれば，人間に近い 性能も得られる。 Bais-Variance の ジ レ ン マ ： バイアスが足りないと，学習に 大量のテータ・時間が必要。 バイアスが不適切だったり，多 過ぎると，いくら学習しても，性 能があがらない。 ニューラルネットワークも機械 学習の１つではあるが... 出力がパラメータ（数値）なので， 人間に取って理解できない。 言語で結果を出力してくれると 理解しやすいのだが 決定木（樹木モデル）をベースにした機械学習システムを 用いるとうまくいきそうだ。 機械学習システムC4.5 C4.5は，J.R.QUINLANによって先に彼が開発した機械学習システムID3の改良 版である。ID3は，獲得情報量(information gain)を用いて属性の選択を行いなが ら決定木を生成する方法である。その基本原理は獲得情報量の期待値の最大化で あり，決定木内の「不確かさ」「あいまいさ」「乱雑さ」などを最小限に押さえる。C4.5 では，さらにエキスパートシステムに帰納学習を付加した形のアルゴリズムを採用し 改良が施されている。また，実数値データに加え，名称データを取り扱うことができ ること，欠落した特徴を持つパターンを識別できること，さらには，作成された決定木 を精度を落とさないように単純化し，より少ないルールでモデルを構築することがで きる「枝刈り」と呼ばれる機能が付随していること，などの様々な特徴を有している。 決定木を作るためには，帰納学習を用いてトレーニングデータを超平面上の点とし て表現し状態空間を分類する必要がある。C4.5では，オブジェクト（ある性質や属性 を持ったデータ，あるいはデータの集合）や事例を，クラス（事例が割り当てられるべ きカテゴリーのこと。予め定義されている必要がある）に分割するため，「利得比基 準（gain ratio criterion）」と呼ばれる基準を活用する。 ◆決定木(樹木モデル)の導出 ◆プロダクション・ルールの導出 ◆利得比基準の計算 樹木モデル（Tree-based model） 樹木モデルとは非線形回帰分析，判別 分析の一つの方法で，回帰の問題では 回帰木（regression tree），分類の問題 では決定木（classification treeあるいは decision tree）と呼ばれる。 樹木モデルは，説明変数の値を分岐 させ，それらを組み合わせて，判別・予 測のモデルを構築する。分析の結果は If-Thenのような簡潔なルールを生成さ せ，ま太，そのルールを樹木構造で図 示することができるため，理解しやすい。 阪神ファン？ No Yes たこ焼き器を持っ ている？ 納豆嫌い？ No Yes 関西人 マクド？ No not関西人 No Yes not関西人 関西人 Yes 関西人 関西人判別モデル 回帰直線 例えば 変数の分割条件 回帰モデルによる判別例 決定木モデルによる判別例 決定木の導出 決定木（decision trees）とは，構造のはっきりした意志決定問題を図的に表したもので （森村ら，1999），ノード（node）とリンク（link，他に枝：branchあるいはアーク：arc）からなる グラフとして表現される。ノードでは１つの属性値を調べるテストが行われ，ノード同士はリ ンクで繋がっている。ある事例に対するパターン識別では，木の最初の根ノード（root node）から最終的なクラスを表す葉ノード（leaf node）にたどり着くまで，テストを繰り返しな がら分類が実行される。分類はパターンが持つある特定の性質に関する質問に答える形 で進行する。そして，質問の答えに基づき適切なリンクをたどりながら次のノードに移り，最 終的に質問が無くなる葉ノードにたどり着くまで繰り返される（QUINLAN，1993；DUDA et. al， 2001）。決定木は，決定がいかにしてなされるか，あるいはなされたかについて，明確に記 録された議論可能なモデルをユーザーに提供し，ニューラルネットワークのような他の識別 木と比べ解釈可能性が明瞭であるといった利点を持っている（DUDA et. al，2001）。 根ノード 阪神ファン？ リンク No Yes たこ焼き機を持っ ている？ 納豆嫌い？ ノード No Yes 関西人 マクド？ No 葉ノード not関西人 Yes 関西人 No not関西人 Yes 関西人 プロダクション・ルールの導出 C4.5は，プログラム「c4.5rules」を用いて，単純なプロダクション・ルール：Ｌ -> Ｒを導出 する。ルールとは，条件部（IF部）と結論部（THEN部）から構成される推論知識の単位で あり，プロダクション・ルールはモジュール型の知識表現において使用され，特にヒューリ スティック探索（heuristic search）において，基本的な推論メカニズムを構成するルール となる（森村ら，1999）。Ｌは属性に基づいたテストの積集合である条件部を表し，Ｒはクラ スである結論部を表す（QUINLAN，1993）。プログラム「c4.5rules」は，プログラム「c4.5」に よって作られた決定木を調べ，以下の例に示したようなプロダクション・ルールの集合を決 定木から導出する。 Rule 6: 露出度 = very small 有効貯留容量= large -> class large [61.0 %] L R ルール番号（ここでは6）は，元の木の葉の順序から決められており，ルールを識別するた めに用いられる。例では，条件部には２つのテストがあり，これらの両方を満足する事例は クラスlargeとして分類される。また，［ ］内の数字（例では61.0％）は，未知事例に対して， このルールが適用され，かつ条件部が満足された場合の分類の正しさを表している。なお， C4.5では，クラスの１つがデフォルトクラスとして選択され，どのルールの条件部も満たさ なかった事例はデフォルトクラスに属していると見なされる （QUINLAN，1993）。 利得比基準（gain ratio criterion） C4.5は，訓練事例集合から分類規則を発見する際に利得比基準と呼ばれる情報量を用い ている。今，事例集合Ｓに対し，Ｓの中でクラスＣｊに属する事例数をfreq(Ｃｊ,Ｓ)，集合Ｓに含 まれる事例数を|Ｓ|とすると，クラスの所属関係に関する平均情報量Ｈ(Ｓ)は， freqC ,S freqC j ,S j H S log 2 S S J 1 k となる。ここで，テストＸ（ある属性をもとに分類することをテストと呼ぶことにする）のｎ通り の結果に合わせて，事例集合Ｔが分割された後について同様に情報量を計算すると， Ti H X T H Ti i1 T n となる。こららの差，gain(Ｘ)＝Ｈ(Ｓ)−Ｈx(Ｓ)は，テストＸでＳを分割することによって獲 得された情報量を表す。これらを最大とするようにテストを選ぶ規準を「利得規準」と呼ぶ。さ らに分割情報量 T Ti i splitHX log 2 i1 T T n を考えると、利得比基準は以下の式で表される。 gain ratio(Ｘ)＝gain(Ｘ)／splitＨ(Ｓ) つまり，利得比規準は，分割によって得られる情報量のうち，クラス分類に役立つ部分の 割合を表すこととなる。 シャノンの情報理論(SHANNON’S Information Theory) 情報工学 エントロピー （entropy） 情報エントロピー Information entropy 物理学 熱力学第２法則 エントロピー増大の法則：閉じた系内で はエネルギーの配分が均一化し，エント ロピーが増大する方向に向かう 使用不可能部分 1984 年 ， ア メ リ カ の 数 学 者 C.E.SHANNONは「情報は１つのメッ セージを選ぶときの選択の自由度の 尺度である」として定義することによ り，情報を定量的に評価できることを 示し，情報の量が確率の対数的測度 で表されることを提示した。 ある事象系のエントロピーをその事象系の 生起確率分布から定義し，情報を受け取る 前後でのエントロピーの差を用いて，その 情報がもたらす情報量を導出する。 熱力学第１法則 エネルギー：仕事をする可能性を表す尺度 一般には「秩序・無 秩序の度合いを測 る尺度」として認識 例)サイコロを振ってどの目が出たかを観察する 情報として （１の目が出るという）事象が生起した。 この系は「１の目」から「６の目」までの６つの事象が等確率で生起する事象系であ る。 情報量とは... 「情報がもたらす系の状態の不確定さの減少分」 エントロピー：高い 最初に観測を行う 前，つまり系がどの 目を出したかが全く わからない状態 観測 観測し，「１の目が出 た」という情報によっ て系の状態が確定 エントロピー：低い ハートレーの情報量 - R.V.L. Hartley (1982) 今，伝送できる記号の集合を考え，それがｎ個の記号からなる場合を考える。この集合からN個の記号を選ん で作った系列はｎのN乗通りある。よって，このような系列の中から１つを受信したときに得られる情報量は，情 報量をHとすると， H log 10 n N Nlog 10 n 〔単位：Hartley〕 情報量の単位 I p log p において，対数の底を２にとれば，単位はビット，10にとればデジット，自然対数の底ｅ (=2.71828…)にとればナットとなる。１ビットの情報量とは二者択一の，１デジットとは10者択一の，１ナットはｅ 者択一の事象が生じたことを報せる情報のもつ情報量である。 １デジット＝3.22ビット， １ナット＝1.443ビット 情報を定量的に評価する P0 P1 P2 ← 情報の加法性 I0：サイコロの１の目が出たことを直接報せる情報量 I1：奇数の目が出たことを報せる情報量 I2：奇数の目が出たことを知った上で，それが１の目であることを報せる情報量 情報量は事象の生起確率のみの関数，よって生起確率p0＝1/6，p1＝1/2 ，p2＝1/3 を用いて Ip0 p1 p2 Ip1 Ip2 I 1 6 I 1 2I 1 3 を満たす初等関数は対数関数である。従って，確率pの事象が生起したことを報せる情報の量（情報量，あるい は自己情報量）は I p log p （負号は情報量を正の値にするため） 自己情報量，情報量の評価方法 サイコロを振って１の目が出たときの自己情報量は Ix i log2 px i ６者択一の事象が生じたわけだから，４者択一の場合の２ビットより多く，８者択一の場合の３ビットより少ない 値となる。一方，系が様々な確率で時々刻々と異なる状態にあることが判っている時、多数回の観測を行った 場合に得られるであろう１情報あたりの情報量は X = xi = {x1, x2, … , xn} (I = 1〜n) ：n個の事象からなる集合 p(xi) = {p1, p2, … , pn} (i = 1〜n) ：集合の中の各事象の生起確率ただし，Σ pi = 1 とすると，そのときの自己情報量I(xi)は I 1 6 log 2 p1 6 2.585 (bit) となる。この値は事象xiの確率p(xi)によるので時々刻々において異なる。よって，時々刻々と伝えられる事象の 自己情報量は変化を繰り返して定まらないが，その重み付け平均値， IX p1 log2 px1 p1 log2 px1 n px i log2 px i i1 として与えることができる。 pn log2 px n ；平均情報量 (自己情報量の期待値) 訓練事例の分割例 事例の分割 天候 温度 (°F) 湿度 (%) 強 風？ クラ ス 晴れ 75 70 真 開催 晴れ ４つの属性 80 90 晴れ 85 晴れ 天候＝晴れ： 湿度≦75： 天候 温度 (°F) 湿度(%) 強風？ クラス 晴れ 75 70 真 開催 晴れ 69 70 偽 開催 真 中止 85 偽 中止 72 95 偽 中止 湿度＞75： 晴れ 69 70 偽 開催 天候 湿度(%) 強風？ クラス 曇り 72 90 真 開催 温度 (°F) 晴れ 80 90 真 中止 曇り 83 78 偽 開催 85 偽 中止 曇り 64 65 真 開催 95 偽 中止 曇り 81 75 偽 開催 雨 71 80 真 中止 雨 65 70 真 中止 雨 75 80 偽 開催 雨 68 80 偽 開催 雨 70 96 偽 開催 ２つのクラス 85 晴れ 晴れ 72 対応する決定木 天候＝晴れ： 湿度≦75：開催 湿度＞75：中止 開催：９事例， 中止：５事例 利得基準の計算例 info(T) 天候 温度 (°F) 湿度 (%) 強 風？ クラ ス 晴れ 75 70 真 開催 晴れ 80 90 真 中止 天候を用いて３つの部分集合に分割すると 晴れ 85 85 偽 中止 infoX(T) 晴れ 72 95 偽 中止 晴れ 69 70 偽 開催 曇り 72 90 真 開催 曇り 83 78 偽 開催 曇り 64 65 真 開催 曇り 81 75 偽 開催 雨 71 80 真 中止 雨 65 70 真 中止 雨 75 80 偽 開催 雨 68 80 偽 開催 雨 70 96 偽 開催 =−9/14×log2(9/14)−5/14×log2(5/14) =0.940(bit) =5/14×(−2/5×log2(2/5)−3/5×log2(3/5 )) +4/14×(−4/4×log0.940-0.694=0.246 2(4/4)−0/4×log2(0/4 )) 強風を用いて分割すると こちらを選択 info +5/14×(−3/5×log X(T) 2(3/5)−2/5×log2(2/5 )) =6/14×(−3/6×log =0.694(bit) 2(6/3)−3/6×log2(3/6 )) 0.940-0.892=0.048 +8/14×(−6/8×log2(6/8)−2/8×log2(2/8 シミュレーションの条件 各種パラーメータをかえて，シミュレーションを行う。 枝刈り（pruning）：すべての訓練集合が含まれるよう分類を続ける と，どんどん複雑な木が生成されるが，必ずしも正答率が高くなる わけではない。そこで，できるだけ推定精度が落ちないよう，木を 剪定する。 グループ化：訓練集合を多くの部分集合に分割すると，それぞれ の部分集合は小さくなり，中にはほとんど予測能力がない木が生 成される。例えば，１００のサンプル例があるとき，１００のルールを 作れば，完全に分類できるが，それはあまり意味がない。そこでで きるだけ，推定精度が落ちないよう，ルールをまとめる作業をする。 Program: 機械学習システムC4.5(Quinlan,1993) モデル数: 決定木導出時：80パターン， ルール構築時：80x8=640パターン 機械学習システムC4.5による推定 緑：最低，青：デフォルト，赤：最高 枝刈り前 出力層数 サイズ 枝刈り前 誤差 数 ％ サイズ 推定精 度 誤差 数 ％ ４ 22 127 25.2 15 134 26.6 64.3 ４ 111 85 16.9 57 95 18.9 73.0 ４ 111 85 16.9 78 88 17.5 78.8 ２ 12 30 6.0 12 30 6.0 88.0 ２ 29 10 2.0 23 12 2.3 94.3 ２ 29 10 2.0 28 10 2.0 97.0 プロダクション・ルールの一例 Rule 1: 欠点-隣接木 = はい -> 「 間伐する」 [99.3%] Rule 6: defects-fork = yes -> class thinned [92.6%] Rule 3: defects-curve = yes -> class thinned [98.3%] Rule 4: defects-low crown height = yes -> class thinned [92.2%] Rule 8: dbh in {small} height in {lower, higher} stem quality in {bad, normal} -> class thinned [97.6%] Rule 13: defects-cut = no defects-curve = no stem quality in {good} defects-small crown = no defects-adjacent trees = no -> class unthinned [95.9%] Rule 2: stem quality in {bad} -> class thinned [97.4%] Rule 5: defects-cut = yes -> class thinned [97.1%] Rule 7: defects-small crown = yes -> class thinned [96.3%] Rule 10: dbh in {middle} defects-cut = no defects-curve = no defects-fork = no defects-low crown height = no defects-adjacesnt trees = no -> class unthinned [93.0%] Default class: unthinned ニューラルネットワークとの比較（郷田倉27C4) 100 97.0 85.9 78.8 100.0 99.2 99.2 88.0 77.9 63.3 50 50.0 推定精度(%) 推定精度(%) Best 0 Worst C4.5 Neural Network 出力層数：４ Best 0.0 Worst C4.5 Neural Network 出力層数：２ 研究（３） 集団学習アルゴリズムを用いた地位指数推定モデ ル の精度および汎化性の検証 モデルの精度や汎化性を，少ないサンプルから，できるだけ保証したい 汎化（generalization）とは， 学習データを用いて学習 した結果を未知データに 適用すること。未知デー タに対する性能は学習 データに対する性能より も一般的には低くなるが， それがあまり低下しない ときに汎化能力が高いと いう（麻生ら，2003）。 モデル選択，サンプリングサイズ •より簡単な識別器を選択する （χ2検定，AIC） •偏り-分散ジレンマ •データ数 集団学習アルゴリズ ム （ensemble learning） m重交差検証法 （m-fold cross validation） m重交差検証法（m-fold cross validation） （大滝ら，1998；Duda et.al., 2001；金，2005) ①．1番目のサブデータ セットを予測誤差の推 定用，残りのサブデー タセットを訓練用としモ デルの構築。 ②．2番目のサブ データセットを予測誤 差の推定用，残りの サブデータセットを訓 練用として，同様にモ デルの構築。 ③．m回繰り返した後， 各回に算出した誤差 の推定値Ri(d)(i=1,..., m) を 平 均 し た 値 を 未 知データに対するモデ ルの推定精度とする。 集団学習アルゴリズム（ensemble learning algorithms） 「３人よれば文殊の知恵？」戦法 AdaBoost,Boostingというアイデア 多少できの悪い学習器でも，たくさん組み合わせて使えば間違いを０に 近づけることができるのでは。 例）クイズ対決 ©村田昇（早稲田） 「１０のジャンルでクイズ対戦」 優等生３人組 • ８ジャンル得意，２ジャンル苦手 • スポーツ・芸能が苦手 V.S. 普通の３人組 • ６ジャンル得意，４ジャンル苦手 • 苦手ジャンルバラバラ 優等生３人組 ：正解 ：間違い Aさん Bさん Cさん 多数決 ©村田昇（早稲田） 普通の３人組 ：正解 ：間違い Uさん Vさん Wさん 多数決 ©村田昇（早稲田） どのようにすればよいのか 麻生（2006） •どうやって，得意分野のばらついた人をバランスよく育てるか？ •どうやって，それぞれの人の答えを統合すれば良いか？ AdaBoost (Freund and Shapire，1997） •得意分野のばらついた人を育てる方法 -最初の人が間違えた問題を，次の人は集中的に訓練する。 すなわち，学習例に重みをつけて，重みつきの誤り率を減ら すように学習する。 •それぞれの人の答えの統合方法 -それぞれの人の信頼度つきで多数決を取る。 集団学習（ensemble learning，アンサンブル学習）とは，個々ではそれほど精度 が高くない学習済みの識別器を複数個用意し，それらを集約して１つの結果を 出力する方法である（金，2005）。通常，分類問題では多数決，回帰問題では平 均を用いて，精度と汎化能力を両立するモデルを構築する。代表的なアルゴリ ズムとして，バギング（bagging），ブースティング（boosting），ランダム森（random forests）などがある。 麻生（2006） AdaBoostの学習アルゴリズム N個の例題からなる訓練集合(x1, xN),...,(y1, yN)が与えられているとする（i=1,...,N ）。 ただし，xi∈X，yi∈Y = {–1, +1}。 t回目の学習における例題iの重みをDt(i)とする。 D1 1 N 1) 重みの初期値を生成する。 1) t=1,...,Tに対し，分布Dtに基づいた誤り率を最小化する識別器，ht：X→Yを学習する。 N t PrD ht (xi ) yi Dt (i) 1) t i* htの誤り率を用いて，信頼度αtを計算する。 1) 分布Dtを更新する。 Dt1(i) N ただし，Ztは D i 1 t 1 1 t ln 2 t Dt (i)expt yi ht (xi ) Zt N である。 t1(i) 1とするための規格化因子で， Z t D t (i)exp t yi ht (xi ) i 1 1) 信頼度で重み付けた多数決Hd(x)を用いて最終的な判別を行う。 T H d (x) signt ht (xi ) t 1 シミュレーション条件 1) 分類器のみ（６個の分類モデル） ・分類型モデル：J48（C4.5のWEKA版）,NBTree（ナイーブ・ベイズ分類器）, RandomForests（集団学習アルゴリズムの一種）， RandomTree,REPTree ・関数型モデル：MultilayerPercptron（ニューラルネットワーク） 2) 集団学習アルゴリズムを併用（２つのアルゴリズム） AdaBoost(boostingの代表的手法)，Bagging(bootstrap法の代表的手法) 3) m-重交差検証法を併用 推定結果-交差検証なし 集団学習 なし AdaBoost Bagging 赤字：改善，緑字：改悪 J48 NBTree Random Forest Random Tree REPTree なし 99.3 96.5 100.0 100.0 環境 93.0 86.6 100.0 長伐期 61.6 61.7 複層 72.1 なし 間伐 MultilayerPercptron 10-1,000 29-10,000 93.4 99.3 99.7 100.0 82.4 95.2 99.1 98.6 100.0 53.7 66.1 90.5 60.5 98.6 100.0 52.4 76.9 90.2 100.0 99.4 100.0 100.0 95.5 99.7 99.7 環境 100.0 93.5 100.0 100.0 88.4 96.2 99.1 長伐期 100.0 71.8 100.0 100.0 59.6 76.9 91.6 複層 100.0 76.9 100.0 100.0 57.2 83.8 91.4 なし 98.9 99.3 100.0 100.0 96.6 99.5 99.9 環境 95.0 94.2 99.7 100.0 90.3 95.8 99.2 長伐期 73.4 67.0 97.6 98.8 55.8 73.1 91.5 複層 80.3 72.6 99.0 99.3 57.8 81.9 91.0 推定結果-交差検証=10回 集団学習 なし AdaBoost Bagging 赤字：改善，緑字：改悪 J48 NBTree Random Forest Random Tree REPTree なし 94.5 95.1 94.4 91.4 環境 81.7 80.4 81.8 長伐期 38.4 40.0 複層 47.8 なし 間伐 MultilayerPercptron 10-1,000 29-10,000 92.3 97.6 96.1 73.6 80.1 79.6 77.9 42.6 39.9 37.0 36.3 40.0 38.8 39.0 36.7 41.6 46.4 39.7 96.4 96.0 94.7 91.4 93.8 97.2 96.2 環境 79.2 80.9 80.5 73.6 80.8 79.5 78.1 長伐期 46.1 43.2 44.6 39.9 39.5 35.8 39.6 複層 44.5 39.1 40.9 36.7 39.5 43.6 39.1 なし 97.4 97.0 94.9 95.5 94.5 97.9 97.4 環境 83.0 84.1 83.6 83.8 81.5 82.0 81.8 長伐期 41.7 38.0 43.9 40.3 38.9 36.8 38.4 複層 44.3 40.0 42.9 39.1 42.9 47.6 39.7
© Copyright 2024 ExpyDoc
