Parabola JournalプログラミングMachine Learning

Subgroup DiscoveryとPython Orangeで遊んでいた

 
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(日本語訳不明)というのはデータマイニングの諸手法の一つで,簡単に言えば,与えられたデータの中で特徴的な部分集合を発見してあげる手法の総称です.(教師あり学習+教師なし学習)/2みたいなポジションです.なんでかというと,目的変数(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

参考リンク



Scala

Scala用の機械学習関係ライブラリ関係を調べてみる

 
Scala Advent Calendar 2013の一環として記事を書いてます.内容としてはScala Advent Calendar 2011の記事(Scalaは機械学習に使えるかな?)の続きみたいなものかな・・・.

まずScalaからJava系のライブラリ各種を呼び出す場合ですが,Scala Days 2013のトーク : Scalable and Flexible Machine Learning With Scala (http://parleys.com/p/51c2e0f3e4b0ed877035684f)や,関係のスライド Scalable and Flexible Machine Learning With Scala @ LinkedInあたりをまず見てみます.
 
要するにMapReduceの処理にどうやって持っていくかという話になるのですが(暴論),紹介されているScalding(Github: https://github.com/twitter/scalding)などのように,ScalaでDSLの実装をして,裏ではJavaライブラリやScalaで書かれた部分に頑張ってもらう,と.ScalaでDSLという話はScalaスケーラブルプログラミングにも出てくる程度には普通の話だと思うので,まぁ普通に嬉しいですね,ということになります.
 
自前で実装するという話をもう少し見ていくと,メソッドを演算子のような形で使うことで(この表現は怪しい?)普通に自作クラス間での計算式を賭けるようになるので,機械学習で使うような計算(線形代数: ベクトル,行列, 確率統計: 分布からのサンプルその他)を実装していくという方向になります.2年前に調べたときはScalalaという線形代数(Linear Algebra, LA)のライブラリ開発がされていましたが,今はbreezeというプロジェクトになりました.

Github: https://github.com/scalanlp/breeze

ScalaNLPというNLP(自然言語処理; 人間が読み書きや話しに使う言語で書かれた文書や,文書の集まり(コーパス)をコンピュータで処理すること. ibisforestさんより)のための開発の一環でしょうか.

Breeze is a library for numerical processing, machine learning, and natural language processing. Its primary focus is on being generic, clean, and powerful without sacrificing (much) efficiency.

 
Scalalaの時代はそこまでドキュメントが整理されていなかったですが,最近ではMatlabやPythonでのNumpy/Scipyと比較してどうこう・・・Breeze Linear Algebra · scalanlp/breeze Wiki · GitHubというページが整備されていて,普通の行列計算やベクトル計算をそのまま書き写すことが一応出来るでしょうか.

なぜ一応と言っているかというと,Pythonでいうndarrayの機能が全てないようなんですね.全て無いこと自体は欠点ではないですが,平たく言うと多次元配列をそんなに上手く扱えないようので,そのあたりが本当にMatlabやNumpy/Scipyからの書き写しが出来るのか疑問に思っています.というかできなかったんだよ.

val c = DenseMatrix.zeros[Double](n,m) 
c(::, 2) 

このようにそれっぽく要素アクセス出来るので,たぶんちゃんと調べたらもう少し使い方分かるような気がするのですが.上の対応表ページで紹介されているSpecial “reduction” functions.とか面白いのですけどね.肝心の性能ですが

Breeze uses netlib-java for its core linear algebra routines. This includes all the cubic time operations, matrix-matrix and matrix-vector multiplication. Special efforts are taken to ensure that arrays are not copied.

ということらしいです.僕は詳しいことは分からないので,そのうち実験したいです.DenseMatrixと他のMatrixの違いとか.

breeze自体は上に書いた通り,自然言語処理関係の一部分で開発されているようなので,線形代数計算以外にもパッケージがあります.機械学習関係(breeze-learn)や可視化関係(breeze-viz)があります.一番ドキュメントが整理されているのは線形代数関係(UserGuide: https://github.com/scalanlp/breeze/wiki/UserGuide)だと思いますが.ホームページ上ではEpicというパーサ(文を区切ります)を作ってるっぽいですが,正体は謎です.

ただ,ScalaDocで吐き出されているAPIページを見てみると,breeze.classify(分類器), breeze.corpora(コーポラ), breeze.data(データ関係,おそらくファイルとか読み込んだりする用), breeze.inference, breeze.stat, breeze.optimize(推論,確率統計関係,最適化関係)とかいろいろあるんですよね.まぁ開発中なんでしょ,きっと.

ちょっと試したい場合,build.sbtにライブラリ依存を書いて使って見て下さい.

scalaVersion := "2.10.2"

libraryDependencies ++= Seq(
  "org.scalanlp" % "breeze_2.10" % "0.5.2",
  "org.scalanlp" % "breeze-viz_2.10" % "0.5.2"
)

resolvers ++= Seq(
  "Sonatype Snapshots" at "https://oss.sonatype.org/content/repositories/snapshots/",
  "Sonatype Releases" at "https://oss.sonatype.org/content/repositories/releases/"
)



さて,もう少し別の方向にDSLが発展した(と言っていいのか,ちょっと自信がないですが)ものにOptiMLという開発中のものがあります(Stanford PPL).これは全体的にもっと大きなフレームワークの一部だと思いますが,機械学習用のDSLを目指しているように見えます.

OptiML is a domain-specific language for machine learning written in Scala. This project primarily explores how scalable data and task parallelism can be implicitly extracted out of high level abstractions such as vectors, matrices, factor graphs, decision trees, and neural networks.


現在はアルファ版(OptiML — Welcome)で遊ぶことができます.結構容量あります.Scalaで書かれているものを.degファイルで書かれたものにコンパイルして実行します.大きなフレームワークってどういう話かというと,OpenCLやCUDA使ったり,C++と絡ませたり,そういうことです.全然Scalaで完結してないじゃん・・・.

それはともかく,サンプルとしてGDA(って何?), ロジスティック回帰,ナイーブベイズ,RBM,kNNのscalaファイルが入ってます.余計な部分を省いてちょっと見てみます.

val x = readMatrix(args(0))
val y = readVector(args(1)).t

val theta = DenseVector.zeros(x.numCols)
// gradient descent with logistic function
val alpha = 1.0
val w = untilconverged(theta, maxIter = 30) { cur =>
  val gradient = sum((0::x.numRows) { i =>
    x(i)*(y(i) - sigmoid(cur *:* x(i)))
  })
  val z = cur + gradient*alpha
  z
}

ってまぁ上のbreezeみたいな計算,中で書いてます.普通だった.んでoptimlの中身に上のbreezeのコアで使われているっぽいですがnetlib-java使ってるようです.あらあら.もう少しの中身はExampleページをどうぞ(Example: OptiML — Examples).実際中身でどんなことしてるか,よくわかりませんでした.


と,ここまで順番にbreezeとOptiMLを見て見ましたけど(書いてないですが,breeze.linalg使って一応ナイーブベイズまで書いたんだよ…),正直なところ例えばMatlabからScalaに,PythonからScalaにと,移行してくるほどかというと,全然そうでもないですね.また来年に期待しましょう.もう少し真面目に,ドキュメント/API読んでみようかなぁ.