Amazon Elastic MapReduceで、Apache Mahout 0.8のクラスタリングを総ざらいする（まとめ）
先のログでは、Apache Mahout 0.8のサンプルにあるcluster-syntheticcontrol.shを用いて、「k-means法」によるクラスタリングについて詳しくみた。
同shellでは、他にもいくつかのクラスタリング手法（アルゴリズム）を試すことができる。今回のログでは、残りのクラスタリング手法について、簡単な解説をまじえて実行結果を掲載する。
手法として取り上げるのは、以下のアルゴリズムである。
- Canopyクラスタリング（Canopy Clustering）
- 潜在ディリクレ配置（Latent Dirichret Allocation:LDA）
- ファジーk-means法（Fuzzy k-Means Clustering）
- Mean Shift法（Mean Shift Clustering）
（昔からある）階層型のクラスタリング手法ではなく、非階層な手法であるところが、今時の機械学習ツールたる由縁であろうか。（個人的には、「デンドログラム」という怪しげな響きが好きなのだが。。。）
各実行結果について、「深追い」はしないが、アルゴリズムやパラメータが、「クラスタリングの結果を大きく変える」ことは注目に値する。
たとえば、以下に示す「潜在ディリクレ配備」では、サンプルである「管理図データ」をうまくクラスタリングすることは難しいように思える。また、「Mean Shift法」も解釈が難しい結果を返す。
両方法ともに、背景となる理論に確率分布などを織り込んだ手法である。k-means法が広く使われる理由には、そのシンプルさが挙げられると思う。
今回も、「Mahout in アクション」を参考にして、できるだけそれに沿った解説にした（ただし、Mean Shift法については、記載がない）。
- 作者: Sean Owen,Robin Anil,Ted Dunning,Ellen Friedman,伊東直子,真鍋加奈子,堀内孝彦,都元ダイスケ
- 出版社/メーカー: オライリージャパン
- 発売日: 2012/10/26
- メディア: 大型本
- 購入: 3人 クリック: 26回
- この商品を含むブログ (11件) を見る
実行方法については、先のログを参照ください。
Canopyクラスタリング（Canopy Clustering）
Canopyクラスタリングという「楽しげな名前がついたアルゴリズム」では、定義した距離に対して２つのしきい値を設定する必要がある。
１つの点（ここでいう「点」とは、測定値の計測グラフを形成する60個の値を、60次元の線形空間にプロットしたもの）にから出発し、半径がしきい値（t2）内の点を、同一クラスタに入るものとし、しきい値(t1>t2）内の点は同一クラスタに入るが、他のクラスタを形成してもよいもの、と扱う。
「Mahout in アクション」のpp165-の記述を参考にすると、この割当処理は、Mahoutでは１回のMapperで行われるとのこと。
ソースコード（examples下のorg.apache.mahout.clustering.syntheticcontrol.canopy.Job.java）を見ると、このサンプルでは、
- 距離はユークリッド距離
- t1=80
- t2=55
と設定されていることがわかる。
Canopyクラスタリングの実行本体は、coreに含まれるorg.apache.mahout.clustering.canopy.CanopyDriver.javaであり、以下の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"); HadoopUtil.delete(new Configuration(), output); run(new Path("testdata"), output, new EuclideanDistanceMeasure(), 80, 55); } }
先に述べたように、Canopyクラスタリングでは、iterateせず1回のMapReduceで終了する。
以下にクラスタごとの中心点を、特性値の系列として示す。
Canopyクラスタリングではt1とt2の決め方に恣意性が紛れ込むが、クラスター数が「正しく６つ」とされてるところが面白い。
潜在ディリクレ配置（Latent Dirichret Allocation:LDA）
名前がイカツイが、簡単に言えば「60次元のプロットについて、いくつか（=クラスター数）の確率分布を当てはめて、もっともらしい分布にプロットを帰属させる」という方法。
この「もっともらしい」という部分は、統計学で「尤度」といって、ある確率分布に従うとしたときの確率、の意味となる。
尤度は、確率分布を規定するパラメータの関数になる（例えば、正規分布を仮定したら、平均と標準偏差はパラメータとなる）ので、（パラメータの関数とみたときには）尤度関数と言われる。
そのパラメータをどう決めるか？という問題が残ってしまうので、パラメータに対しても確率分布を当てはめる。このための確率分布としてディリクレ分布を用いる、という意味になる。なんで、ディリクレ分布なのか？という話があって、こういう記事もあるが、基本的には、非常に自由度の高い確率分布(Wikipediaにあるようにベータ分布の多変量版なので、αの置き方によって密度関数が様々な格好をとることができる）だからと考えておけばいいと思う。
サンプルプログラムのソースコードは、org.apache.mahout.clustering.syntheticcontrol.dirichlet.Job.javaである。
クラスタリングを行うクラスは、core下のorg.apache.mahout.clustering.dirichlet.DirichletDriver
であり、以下のmainメソッドが１つのエントリーポイントになっている。
以下をみると、乱数をもとにした多次元正規分布を仮定して、モデル（クラスタ）=10、最大反復数=5、ディリクレ分布のパラメータを１とおいている。
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"); HadoopUtil.delete(new Configuration(), output); DistributionDescription description = new DistributionDescription(GaussianClusterDistribution.class.getName(), RandomAccessSparseVector.class.getName(), null, 60); run(new Path("testdata"), output, description, 10, 5, 1.0, true, 0); } }
実行すると、上で指定した通りに5回のiterationで終了する。
以下にクラスタごとの中心点を、特性値の系列として示す。指定した通りに10個のクラスタを分離しようとしているが、実際には、殆どそれができない状況となったのは興味深い。
ファジーk-means法（Fuzzy k-Means Clustering）
ファジーk-meansクラスタリングは、１つのプロットが複数のクラスタに属することを許すクラスタリング手法である（ソフトクラスタリング）。
サンプルである「管理図データ（特性値の時系列データ）」については、「この特性値の系列は、このクラスタとこのクラスタに属する」という結果に意味がなさそうだが、ニュースや店舗などをクラスタリングする際には、「どちらにも属する」ということがあり得るし、そのように情報をまとめて見せたい場合も多いと思われる。
このような場合には、ソフトクラスタリングを使うのがよい。
ソフトクラスタリングでは、一般に、各プロットが「クラスタへの帰属度」を持っていて、k-means法に追加される「あるパラメータ」でファジーネスが決定される（式は「Mahout in アクション」に掲載されている）。
同書によれば、パラメータ（m）は1 < m であって、m=2が推奨されている。これは、m=1に近づくにつれ、ファジーネスが弱まり（ハードクラスタに近くなり）、m=2の時に各クラスタへの帰属度の和が１になる、という性質があるためである。
サンプルプログラムのソースコードは、examples下のorg.apache.mahout.clustering.syntheticcontrol.fuzzykmeans.Job.java
なので、このmainメソッドを見ると以下のようになっている。
Fuzzy K-Meansを実行する実態は、core下のorg.apache.mahout.clustering.fuzzykmeans.FuzzyKMeansDriver
となっている。
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(), 80, 55, 10, 2.0f, 0.5); } }
上でクラスタの数を指定していないことに注目して、サンプルプログラムを見ると、クラスタ数の決定にCanopyクラスタリングが用いられていることがわかる。80、55というパラメータは、先に述べたCanopyクラスタリングのパラメータt1、t2である。
public static void run(Configuration conf, Path input, Path output, DistanceMeasure measure, double t1, double t2, int maxIterations, float fuzziness, double convergenceDelta) throws Exception { Path directoryContainingConvertedInput = new Path(output, DIRECTORY_CONTAINING_CONVERTED_INPUT); log.info("Preparing Input"); InputDriver.runJob(input, directoryContainingConvertedInput, "org.apache.mahout.math.RandomAccessSparseVector"); log.info("Running Canopy to get initial clusters"); Path canopyOutput = new Path(output, "canopies"); CanopyDriver .run(new Configuration(), directoryContainingConvertedInput, canopyOutput, measure, t1, t2, false, 0.0, false); log.info("Running FuzzyKMeans"); FuzzyKMeansDriver.run(directoryContainingConvertedInput, new Path(canopyOutput, "clusters-0-final"), output, measure, convergenceDelta, maxIterations, fuzziness, true, true, 0.0, false); // run ClusterDumper ClusterDumper clusterDumper = new ClusterDumper(new Path(output, "clusters-*-final"), new Path(output, "clusteredPoints")); clusterDumper.printClusters(null); }
実行すると、Canopyクラスタリングでクラスタ数が6と決定され、6回のiterationで終了する。
以下にクラスタごとの中心点を、特性値の系列として示す。先のログで、「k-means法で、このデータが分離できるのか？」と考察した際に、インクリーズ、デクリーズについてはベクトルの方向性が合うので、分離できるだろうと書いた。ファジーk-means法による結果で、その予想を裏付けるような結果が得られたのは面白いと思う。
Mean Shift法（Mean Shift Clustering）
Mean Shift法については、「Mahout in アクション」に説明がない。
理化学研究所のサイトに説明を見つけたので、リンクを貼っておく。
数式はともかく、この手法で確率・統計でいう「カーネル密度推定」という確率分布の推定方法を使う。カーネル密度推定については、Wikipediaにも説明がある。「カーネル」とは（一般に）「積分値が１の関数」のことで、標準正規分布の密度関数（Gaussian Kernel)や、[-b,b]で定義されたy=1/2bの関数（Rectangular Kernel、Uniform Kernel）、上を向いた三角形（Triangular Kernel）などが使われる（こちらのサイトにも、代表的な種類が上げられている）。
確率密度関数の推定を行う有力な方法の１つである。
先に述べた潜在ディリクレ配置（LDA）を思い出してもらうと、60次元の空間に散らばったプロットに対して、「特定の確率分布（サンプルでは正規分布）」を当てはめていた。これに対して、Mean Shift法では「確率分布を推定すること」で、「特定の確率分布を選択する」というリスクを減らすことができる。ここで「リスク」という言葉を使ったが、多変量データの分布では「プロットを視覚化できない」ため、プロットの散らばりを眺めて分布を当てはめるという行為そのものがリスクとなる可能性が高い。
Mean Shift法では、各プロットを密度関数が極大になる方向へ移動させ（最適化手法としては、最急降下法を使う）る。そうすると、収束した点の集まった部分ができるので、これらが特定のしきい値を半径とする円（多次元の）に入れば、同じクラスタに属するとする。
以下は、理研のサイトからの引用であり、概念的にはこの手続きによりクラスタリングを行う。
d次元空間Rdにばらまかれたn個の点，X1, X2, ..., Xnが入力された下で．
密に分布する点群をクラスタとして分割する．1. 各点xi にMean Shift Proceduerを適用し，収束位置Xic を計算する
2. 任意の2個の点 Xi Xk について，その収束位置が閾値以下なら，( ||Xic - Xkc|| < thresh )この二点を同じクラスタに入れる．これにより，同じ密度の極大点(node)に属する点群が同じクラスタになるよう，分割できる．
… 理研のHPより引用。
それでは、サンプルのジョブを見てみる。ソースコードはexamples下にあるorg.apache.mahout.clustering.syntheticcontrol.meanshift.Job.javaで、クラスタリングの実行本体はcore下にあるorg.apache.mahout.clustering.meanshift.MeanShiftCanopyDriver.javaとなっており、Canopyクラスタリングをロジックに含む実装になっている。
実行時パラメータとして、ユークリッド距離、Triangularカーネルの指定、Canopyクラスタリングのt1=47.6,t2=1、収束のしきい値=0.5、最大繰り返し数=10が指定されている。
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(), new TriangularKernelProfile(), 47.6, 1, 0.5, 10); } }
実行すると、3回のiterationで終了する。
以下にクラスタごとの中心点を、特性値の系列として示す。Canopyクラスタリングを行っているのに、クラスタ数が７つに増えたのは、t2の設定が小さくなった影響と思われる。
