タグ: data mining

Parabola Journal、プログラミング、Machine Learning

Subgroup DiscoveryとPython Orangeで遊んでいた

投稿日: 投稿者: taki

　
Machine Learning Advent Calendar 2013の一環で書いてます．動かしてみるつもりだったんですが，諸般の事情で動かなかったものもあったりして・・・．機械学習関係で比較的メジャーなタスクは分類と回帰だと思うのですが，RのEcdatパッケージに含まれているHousing data(data(Housing)で使う)を線形回帰してみます．

入力
output

出力(回帰直線を重ねたもの)
output_line

わーい嬉しい．まぁ細かいところを見てみたらこのデータに線形回帰を突っ込むのがそもそもどうなのか，という問題はありますが，別に2次の項を入れた曲線で近似したところでどうこうなる問題でもないでしょう．そこで，結局横軸(x: lotsize)と縦軸(y: price)がダメなんでしょ？という話を考えたい．いえ，別に積極的に考えたくはないのですが．あと問題にもよりますが．

なんとなく線形回帰ダメっぽいという話からすると，このグラフ(軸のとり方)がそもそもあかんのや，という話を考えるしかないでしょう．別にどこかの特徴空間に写像してもらって，うまく回帰するならそれはそれでもちろんいいですけどね，そのあたりはよく分かりません．Housingデータはもともと，price, lotsize, bedrooms, bathrms, stories(謎), driveway, … と他にも属性ありますので，そのあたりもコミコミで計算したらもっといい感じの回帰式にはなると思います(何がいい回帰式なのか，はとりあえず考えない)．

  1. とりあえずデータがあります(離散値，整数値，カテゴリ値，二値，etc.で構成される)
  2. なんか処理したい(←今ココ
という状況を思い浮かべていただきたいと思います．こういう状況になるとさすがにパッケージにぶち込んで＼(^o^)／というわけにはいかないので，データの整形・特徴抽出・正規化などなどをやる必要があるかもしれません．結局データ事態が言うほどキレイでない，というのが問題なんですね．データの生成がそもそもi.i.d.でないとか，いろんなデータの種類が混じっているとか，要因はいろいろでしょうが，なかなか難しい．

全部ごちゃまぜのデータを扱うのももちろんそれはそれで良いのですが，出来ればなんかキレイなデータにしてから処理した方が，扱いやすくなります．例えば先にクラスタリング(何でもいいので，レコード間の距離か類似度を決めて，例えば階層クラスタリングにぶち込んでグループ分け，みたいなことする)などの手法をかけたデータの前処理を職人芸でやって，さらに機械学習の諸手法で大域モデルを学習すれば，そのグループの中での精度は高くなるでしょう，仮にただの線形回帰だとしても．

ここでようやく表題なのですが，Subgroup Discovery(日本語訳不明)というのはデータマイニングの諸手法の一つで，簡単に言えば，与えられたデータの中で特徴的な部分集合を発見してあげる手法の総称です．（教師あり学習＋教師なし学習）／２みたいなポジションです．なんでかというと，目的変数(target; 決定木とかでも決めているあれ，いわゆる目標変数)を決めた上で，マイニングとルール生成と評価を繰り返していくからでしょうね．もちろんこういう手法だけでなく，RやPythonの可視化(Numpy/Scipy->Matplotlib), Wekaほげほげを利用して可視化しながらデータをよーく眺めるというのが，まず最初にやる作業となるとは思いますが，前処理にデータマイニング処理使ってもいいじゃないか．そこで今回はPythonのOrangeという環境でそれをやろうとしました，という話です．データマイナーを名乗るための道のりは長く険しいですね．

パッケージとしてはよく分かりませんが，Python Orange用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/)，Rapid Miner用(http://kt.ijs.si/petra_kralj/SubgroupDiscovery/rm.html)，R用(詳細未確認)(http://www.subgroup.cc/)をとりあえず見つけました．

特徴的な部分集合とはどういうことか

線形回帰の例を続けます．全体の回帰式Y_{\mathrm{Price},i} = A + B X_{\mathrm{lotsize}, i} + \varepsilon_iが得られているとします．次にやることは，ある部分集合D (つまり，subgroup）を検索します．この部分集合Dにおいて回帰式を学習すると，例えば別の回帰式Y_{D,\mathrm{Price},i} = A_D + B_D X_{\mathrm{lotsize}, i} + \varepsilon_iが得られるとします．もし，2つの例えば回帰直線の傾きが統計的に有意に異なるなら(つまり帰無仮説H_0\: B_D = B)をチェックする．もし有意に異なるなら，今見ている部分集合Dを，何らかの特徴によって全体と異なる部分だ，と見なす(´・ω・`)

部分集合の作り方: 簡単なイメージ

例えば離散値属性がある場合(性別: 男/女，年齢層:10代/20代/30代/…)，これをそのまま条件としたサブグループというのを作ることができる．
  • サブグループ1: 男性
  • サブグループ2: 10代男性
  • サブグループ3: 10代男性既婚
  • …
ある条件が有意に異なるサブグループを発見した場合，さらに条件を加えて条件1∧条件2，条件1∧条件2∧条件3，…と頑張って条件を難しくしていく．この探索空間はデータベースの次元(属性数，か)が上がると当然のように手に負えなくなるので，近似的な探索(例えばグループを表現するルールの精度やカバー率を定義して，その値が大きいものから決められた個数だけ発展的に検索するなど．要するにビーム探索)をすることも．というか，基本的に全列挙は諦めていると思う．

上のHousingデータの属性pref_area(Yes/No二値)を例えば対象とすると，Yes(好ましい)とNo(好ましくない)という+/-がデータ中の各レコードに付いていると考えることができる．次にやるのは上で考えた空間の探索で，簡単な規則から難しい規則を生成して，空間を走査していく．

ある条件(ルール)が得られた時，ルールで表現されるレコードのうち，pref_areaが，例えばYesが75%以上であれば，そのルールを特徴的な部分を表現していると見なす．アイテム集合発見における出現割合(# of occurrences / The entire size of DB)みたいなもの．もちろんそういう評価の仕方だけでなく，いろんな評価があってもいいのだけど，空間内のルールと評価関数においてdownward-closure propertyが成立していた方が，探索は簡単になる．

必要なもの

真面目に考えると，Subgroup Discoveryを適用するには次のことを決める必要がある．
  • 何を対象として集合を分けるのか
    • 決定木作るときの対象属性と同じ．Subgroup Discoveryは基本的に1つの対象変数のみを扱う．2つ以上を同時に扱うような拡張は，一部でExceptional Model Miningと呼ばれる．
  • そのようにしてサブグループを表現するのか
    • 命題論理式，述語論理式，数値区間，その他いろいろを使う．定式化的には探索空間を効率的に検索するための精密化演算子が上手く定義出来，下で述べる基準について単調性が保証される方が望ましい．
  • サブグループ選択のための基準
    • ルールを評価するために使う．カバー率や頻度，エントロピーなど．
  • 探索をどのように効率化するか
    • いくら枝刈りを頑張っても全列挙はだいたいしんどいので近似探索手法も同時に使う．

Orangeで動かしてみる

Subgroup Discovery用のWidgetをインストールしたOrangeにデータをぶち込む
Orange_1

見たい場合はData Tableに通す
Orange_2

インストールしたSubgroup Discovery Widget群を使って
Orange_3

Subgroup Discoveryを動かすと
Orange_4

楽しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌ここでは相関規則系のSubgroup Discovery手法を利用しているので，出てきているサブグループの記述もそういう形です．（条件→嬉しい✌(‘ω’✌ )三✌(‘ω’)✌三( ✌’ω’)✌）とりあえず家賃400(単位はポンド・・・か？)あたりでいいらしいです．
Orange_5

データマイナーへの道のりは長く険しいですねぇ(二度目)．機械学習手法を用いるとき，自分のデータがどういうデータなのかに注意をはらって，楽しい学習ライフを送りましょうということで，ひとつ．

参考文献
  • F. Herrera et al. An overview on subgroup discovery: foundations and applications

参考リンク



1