Amazon Elastic MapReduceで、Apache Mahout 0.8のk-meansクラスタリングを実行する。

先のログでは、MahoutをLocal環境（Mac OSX Mountain Lion）で実行した。

今回は、Amazon Elastic MapReduce（EMR）＋Hadoop MapReduceで、k-meansクラスタリングを動かしてみたい。
Mahoutのバージョンは、0.8で行った。

EMRの構成は、m1.smallが２台の最小構成（マスタインスタンスと、コアインスタンス）とした。
Amazon EC2（Elastic Compute Cloud）を選ばなかったのは、Hadoopでサンプルを動かしたかったことと、EC2だとJavaやHadoopなどの設定に手間がかかるからである。

コマンドラインツール（Elastic MapReduce Ruby）をつかって、ターミナルから、以下のようにジョブフローを起動する。

elastic-mapreduce --create --alive --name Mahout-Cluster --instance-group master --instance-type m1.small --instance-count 1 --bid-price 0.02  --instance-group core --instance-type m1.small --instance-count 1 --bid-price 0.02

上の例では、スポットインスタンス(Spot Instance）を$0.02/hでリクエストしている。スポットインスタンスは、いわゆる変動価格で、利用状況によって変化する。EC2のマネージメントコンソールのInstances=>Spot Requestsとすると、画面上にPrice Historyというボタンがでてくる。これを見ることで、インスタンスタイプ、リージョンごとの価格変動をみることができる。
U.S.Standardのm1.smallは通常（オンデマンドプライス）$0.06/hだが、場合によっては安く利用することができる。今回の場合、$0.02で2台購入できれば、EC2を1台$0.06で買うより安い（EC2を１台$0.02で買った方が安いので、理由にならないか。。。）。

スポット料金はかなり変動して、「購入した価格がスポット料金を下回ると、自動的にインスタンスが停止されてしまう（プロセスが動いているとか、全く関係なく、突然Terminateされてしまう）」ので、通常利用するなら、リザーブドインスタンス（予約することでディスカウントプライスが使える）か、オンデマンドインスタンスを使いましょう。

Mahoutは開発環境からsftpでマスターノードに送り、SSHでマスタノードに（ユーザーhadoopで）ログインして、zipを解凍する。

ここで、改めて、Amazon EMRでのユーザーhadoopの環境変数を見ると、

TERM=xterm-256color
SHELL=/bin/bash
HADOOP_HOME=/home/hadoop
SSH_CLIENT=[your IP Address] xxxxx xx
SSH_TTY=/dev/pts/0
USER=hadoop
LD_LIBRARY_PATH=/usr/local/cuda/lib64:/usr/local/cuda/lib:
MAIL=/var/mail/hadoop
PATH=/usr/local/cuda/bin:/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games:/home/hadoop/bin
PWD=/home/hadoop
JAVA_HOME=/usr/lib/jvm/java-6-sun
LANG=ja_JP.UTF-8
SHLVL=1
HOME=/home/hadoop
LOGNAME=hadoop
HADOOP_HOME_WARN_SUPPRESS=true
SSH_CONNECTION=[your IP Address] xxxxx [EC2 Local IP Address]
_=/usr/bin/env

となっているので、Mahout用に不足を追加する。

export HADOOP_CONF_DIR=/home/hadoop/conf
export MAHOUT_HOME=/home/hadoop/mahout-distribution-0.8
export CLASS_PATH=$HADOOP_CONF_DIR:$MAHOUT_HOME/conf
export PATH=$MAHOUT_HOME/bin:$PATH

これで、ようやく$MAHOUT_HOME/examples/binに移動し、MapReduceでサンプルを動かす。

$MAHOUT_HOME/examples/binには、「Hadoop MapReduceを使うサンプル」と、「使わないサンプル」が混在していて紛らわしい。

たとえば、classify-20newsgroup.shなどは、Hadoop MapReduceを使わずにローカルで実行するようになっている。簡単な見分け方は、shellスクリプトの中で、HDFSを使っているかどうかチェックするのが簡単で、HDFSを使っていれば、Hadoop MapReduce環境で（も）動く前提でサンプルが書かれている（と考えていいと思う）。
逆に、HDFSを使うようにShellを書き直してもいいと思うが、classify-20newsgroup.shではつまらないところでMapReduceが落ちてしまう。（データをSparceVectorに変換するところで、IlligalArgument Exceptionを吐く）

以下では、cluster-syntheticcontrol.shで、k-means法のサンプルを動かしてみる。
Mahoutのドキュメント（少し古い感がある）にも説明のあるサンプルで、「（シューハートの管理図に代表される）時系列かつサイクリックな（同じ計測を繰り返し行った）データを、クラスタリングする。

シューハートの管理図は、製造した製品機械の特性値の中心値のずれ（Xバー管理図）やバラツキ（R管理図）を計るために古くから使われている図表で、工場ではおなじみの図表である（「QC７つ道具」にも入っている）。

管理図の作り方と活用 (新版QC入門講座)

作者: 中村達男,鉄健司
出版社/メーカー: 日本規格協会
発売日: 1999/12
メディア: 単行本
購入: 1人クリック: 2回
この商品を含むブログ (2件) を見る

サンプルジョブでは、1999年にカリフォルニア大学で作成されたデータを利用しており、以下が概略である。

1つの特性値に対して60回（たとえば、60個の製品）の計測を行う。
6パターンのトレンドが１つのデータに100個ずつ収まっている。

上の6つのパターンは、（オリジナルのサイトにあるように）

デクリージング・トレンド(A)：特性値が徐々に加工している場合
サイクリック(B)：特性値の変化に特定の周期がある場合
ノーマル(C)：特性値、ばらつきともに安定した状態：一般には、データが想定されている正規分布に従っている場合
アップワード・シフト(D)：特性値が突然、上方にシフトした場合
インクリージング・トレンド(E)：特性値が徐々に上昇している場合
ダウンワード・シフト(E)：特性値が突然、下方にシフトした場合

の６つである。

　...　Synthetic Control Chart Time Seriesより抜粋

ここで、クラスタリング対象が、上の図の「線」であることに注意する。
各線は、60個のポイント（点）を繋いでおり、60次元の空間内のプロットと見なす。

これらが、「うまくクラスタリングされるか（６つの系列に分類されるか）」を試すのが、cluster-sytheticcontrol.shの目的である。

製造現場における工程管理のツールとしても興味深い使い方だと思う（メーカー勤務が長い人間としての意見）。
このサンプルにある６つのパターンは、行程における特性値のシフト（Xバー管理図でチェックする異常）に関わるもので、緩慢な特性値の変化は、機械振動によって留め具が移動するなどで発生するし、急な変動は、機械のメンテナンス・ミス、誤操作などで発生する。いずれも、不良（製造不良）の発生に結びつく。

さて、それでは、実際に動かしてみると、9つのMapReduceジョブ（以下）のあとに、終了する。

実行は、$MAHOUT_HOME/examples/binに移動し

./cluster-syntheticcontrol.sh

とする。すると、

Please select a number to choose the corresponding clustering algorithm
1. canopy clustering
2. kmeans clustering
3. fuzzykmeans clustering
4. dirichlet clustering
5. meanshift clustering

のように（代表的な）クラスタリング・メソッドを聞いてくる。ここで2を選択すると、デフォルトの設定で、k-means法でのクラスタリングが開始される。

最終的には、以下のような出力結果がでて終了する。

VL-291{n=60 c=[30.019, 29.965, 30.427, 32.054, 31.535, 33.238, 32.189, 32.998, 33.412, 33.825, 34.260, 34.567, 35.249, 35.224, 35.506, 35.968, 36.780, 37.337, 37.695, 37.685, 37.811, 38.975, 39.097, 39.354, 39.893, 40.137, 41.381, 40.389, 40.911, 42.327, 41.944, 43.074, 42.380, 42.983, 44.110, 44.312, 44.794, 44.541, 45.072, 45.229, 46.211, 46.931, 47.283, 47.386, 47.683, 48.441, 49.139, 48.533, 48.447, 49.815, 50.037, 50.413, 51.312, 51.630, 51.522, 52.397, 52.944, 52.648, 53.306, 53.320] r=[3.586, 3.435, 3.033, 3.425, 3.786, 3.180, 3.245, 3.400, 3.642, 3.572, 3.191, 3.248, 3.475, 3.803, 3.697, 3.355, 3.570, 3.188, 3.698, 3.720, 3.156, 3.564, 3.755, 3.847, 3.579, 4.028, 3.424, 4.064, 3.691, 3.136, 3.494, 3.903, 3.774, 3.788, 3.864, 3.713, 3.923, 4.390, 4.075, 4.032, 3.952, 4.248, 3.342, 4.006, 3.995, 4.323, 4.041, 4.294, 4.464, 4.280, 4.173, 3.740, 4.287, 4.759, 4.138, 3.992, 4.110, 4.231, 4.374, 4.328]}
	Weight : [props - optional]:  Point:
	1.0: [33.786, 29.428, 27.377, 37.342, 26.013, 36.203, 31.024, 37.785, 35.754, 36.953, 32.401, 37.258, 37.536, 40.414, 33.863, 33.254, 43.233, 40.022, 34.117, 38.453, 42.565, 37.477, 37.266, 43.044, 39.428, 43.563, 45.807, 49.265, 40.014, 43.101, 40.967, 47.690, 47.250, 49.214, 43.991, 51.439, 49.912, 53.279, 45.193, 45.813, 48.885, 55.934, 50.823, 53.761, 48.767, 57.682, 58.600, 54.354, 57.292, 50.088, 55.553, 50.929, 56.859, 54.562, 53.578, 62.184, 62.853, 57.198, 63.828, 56.127]
.....

VTLxxxというのがクラスタ名であり、その後に、そのクラスタに分類された系列数、クラスタの重心（centroid as a vector）、クラスタの半径（radius as a vector）、行を変えて、そのクラスタに分類された系列がダンプされる。

結果は、HDFS上に残るので、以下のコマンドで結果を確認することもできる。クラスタの重心だけなら、以下で見ることができる。

mahout clusterdump -i /user/hadoop/output/clusters-7-final

各系列が、どのクラスタに分類されたかは、以下で見ることができる。

mahout seqdumper -i /user/hadoop/output/clusteredPoints

６つのクラスタの重心の位置をプロットしてみる。
A-Fはクラスターにつけたラベルで、度数はそれぞれ以下。

A	60
B	172
C	194
D	112
E	28
F	34

さて、上を見ると、うまくクラスタリングできてない。混同行列を作るまでもなく、以下の現象が起こっている。

ノーマルとサイクリックが分離されていない。F（度数:34）が明らかな周期を示しているのと同時に、B（度数:172）も周期性を示しており、BとFに混同されていると考えられる。
デクリージング・トレンドとダウンワード・シフトが分離されていない。これらは、下降トレンドを描くはずであり、C（度数194）に混同していると考えられる。
アップワード・シフトと、インクリージング・トレンドが分離されていない。（A:度数60、D:112、E:28に混同している）

さて、ここで冷静になって考えてみると、このサンプルで扱った「特性値の系列」を「60次元のプロットとしたときに、クラスター分析でうまく分離できるのか？」という問題が、頭をもたげてくる。

サイクリックな場合については、「サイクルが同一の場合」にはプロットが近くに集まる、シフトの発生は、「同一のタイミング（計測点）でシフトが発生する場合」にプロットが近くに集まる。これ以外の場合には、プロットのバラツキが大きくなってしまい、他のクラスタに吸収されてしまう確率が高くなってしまう。
サイクリックとシフトがうまく分離できないのは、このためと考えられる。
これに対して、トレンドについては、ベクトルの方向が揃うため、クラスタリング可能と思える。また、逆にシフトも、トレンドに吸収される可能性が高い。

k-means法（に限らず、他の機械学習系の手法や統計学的手法は殆どそうなのだが）には、それを規定する多くのパラメータ（仮定）が存在する。
一番大きい影響を及ぼすのは、距離の概念（距離空間の概念）であって、LDAのような手法の場合には、分布の仮定が結果に影響を及ぼす。k-means法では、あまり問題にならないが、数値解析的な収束性と精度の問題もあるし、初期値の置き方の問題もある。
「何回も分析しましょう」というのは、こういう諸々の諸条件を変えて「実験してみなさいよ」という意味なのだが、このサンプルではどうなっているのだろうか？

サンプルを実行すると、以下のようなメッセージが現れる。

13/08/15 00:32:13 INFO kmeans.RandomSeedGenerator: Wrote 6 Klusters to output/random-seeds/part-randomSeed
13/08/15 00:32:13 INFO kmeans.Job: Running KMeans with k = 6
13/08/15 00:32:13 INFO kmeans.KMeansDriver: Input: output/data Clusters In: output/random-seeds/part-randomSeed Out: output Distance: org.apache.mahout.common.distance.EuclideanDistanceMeasure
13/08/15 00:32:13 INFO kmeans.KMeansDriver: convergence: 0.5 max Iterations: 10

k=6で、重心の収束は0.5、距離はユークリッド距離（L2ノルム）、初期値としてはランダムシードを使いますよ、となっている。

これは、org.apache.mahout.clustering.syntheticcontrol.kmeans.Jobのソースを見ると、以下の記述になっているため。k-means法は、org.apache.mahout.clustering.kmeans.KMeansDriver
で実行されるが、ここへのエントリがmainに記載されている。

  public static void main(String[] args) throws Exception {
    if (args.length > 0) {
      log.info("Running with only user-supplied arguments");
      ToolRunner.run(new Configuration(), new Job(), args);
    } else {
      log.info("Running with default arguments");
      Path output = new Path("output");
      Configuration conf = new Configuration();
      HadoopUtil.delete(conf, output);
      run(conf, new Path("testdata"), output, new EuclideanDistanceMeasure(), 6, 0.5, 10);
    }
  }

このサンプルでは、測定値の系列がデータであったので、ユークリッド距離を使ったが、Mahout in Actionなど読むと、頻度などがデータになっている場合には、他の距離（cosine距離など）を使う方がよい、と書いてあるし、Kを決めるために、Canopyクラスタリングというのもありがちな方法のようだ。
たしかに、この例でも、シフトとサイクルについて、上述のように割り切れば、ベクトル空間の方向に注目するのも「あり」だろう。この場合には、cosine距離で「望んだ結果が得られる」可能性が高い。

Mahoutイン・アクション

作者: Sean Owen,Robin Anil,Ted Dunning,Ellen Friedman,伊東直子,真鍋加奈子,堀内孝彦,都元ダイスケ
出版社/メーカー: オライリージャパン
発売日: 2012/10/26
メディア: 大型本
購入: 3人クリック: 26回
この商品を含むブログ (11件) を見る

Canopyクラスタリングを挟むことで、結果がよくなる可能性はあるが、「シフトといった現象をバラツキとして距離空間上に表現する」のであれば、Canopyのパラメータを決める際の恣意性が高くなりすぎるかもしれない。

ともあれ、いろいろ考える事があって、面白い。