機械学習とデータマイニング

機械学習は,AIシステムが経験を通して自らのふるまいや知識を改良できるようにするための手法である.データマイニングはデータの中から法則性を推定する技術である.データの中から法則性やパターンを見つけるアルゴリズムを構成するという目標は両者に共通している.機械学習はそのユーザがAIシステムであり,データマイニングはユーザが人間であるという点が異なっている.
ここでは,機械学習とデータマイニングの入門的な手法として,決定木学習,頻出集合発見,簡単なニューラルネットワーク学習をとり上げる.
スライド → こちら
1. 決定木学習
決定木(decision tree)とは,与えられたデータの属性値を点検してカテゴリに分類するための手続きを木構造として表現している.非終端ノードは属性の点検を表し,終端ノードは結論づけられるカテゴリを示す.

たとえば,次の決定木

は,次の表の左の3列の情報を用いて右端の列の内容を決定する.

例えば,4番目のデータについては,taste属性値がmildであるので,size属性の検査が行われ,その他隊がLなので,goodという決定がされる.
サンプルデータに対して同じ決定を行う決定木は複数個有り得る.通常,オッカムのかみそり(ないしは最小記述長)の原理により,その中で最も小さなものが,最も的確にデータ分類の基準を表現していると考えられる.ID3のような決定木学習アルゴリズムでは与えられたサンプルデータに対するもっとも小さな決定木を算出する.
プログラミング演習
ID3:ソースコード例実行例
2. 頻出集合発見
トランザクション名とそのトランザクションに関わったアイテムの集合からなるトランザクションの集合として規定されたトランザクションデータベースから,頻出するアイテム集合を発見せよという問題である.

例えば,次のように与えられる6個のトランザクションデータからなるデータベースDにおいて,パラメータとして与えられるθ=5とすると,アイテム8はトランザクションt1,t2,t3,t4,t5,t6に含まれているので,少なくとも大きさ1の頻出集合に含まれることがわかる.さらに調べてみると,{17,8,23}はトランザクションt1,t2,t4,t5,t6に含まれているので,大きさ3の頻出集合であることがわかる.

頻出集合を求めること自体は難しくないが,どうすれば効率的に求めることができるかは自明ではない.基本的なアイデアとして,頻出集合の族の単調性,すなわち,「トランザクションtが頻出集合Xを含むならば,tはXの任意の部分集合を含む」という性質に着目すると,Xの部分集合の出現集合はXの出現集合を含み,頻出度はXより同じか大きくなることが導かれる.

アプリオリ法のアルゴリズムでは,空集合から出発し,幅優先的にアイテムを一つずつ追加していく,すなわち,

という方式で頻出集合をすべて見つける.
プログラミング演習
a priori:ソースコード例実行例
3.簡単なニューラルネットワーク学習
ニューラルネットワーク は,ユニットと呼ばれる多数の処理エレメントが結合された計算メカニズムであり,分類などのタスクに使用される.

例えば,次のフィードフォーワード型ネットワークは,排他的選言を計算する.

中間層をもつフィードフォーワード型ニューラルネットワークの学習アルゴリズムとして知られている誤差逆伝播(back propagation)は,教師データとして示された分類ができるように繰り返し計算によってリンクの重みとバイアスを計算する.
誤差逆伝播の基本的な考え方は,入力パターンpに対して発見された出力層の誤差に責任をもつリンク重みとバイアスを寄与の度合いに応じて修正する.

フィードフォーワード型ネットワークの性質を使うと,

に示された通り,出力層から逐次重み修正を行っていけることがわかる.

バックプロパゲーションはこれを実装したものである.計算を安定にし,トレーニングデータへの過度の適応を防ぐために,小刻みに修正を行う.
計算例は次のようになる.



プログラミング演習
バックプロパゲーション:バックプロソースコード例実行例