今回で2章が終わります！！
前回分はこちら↓↓
http://qiita.com/ru_pe129/items/7f4485e5347aea080c5f
2.4 Cluster Analysis
CFで問題となるのは各アイテムやユーザー間の距離を求める際に必要となる処理の量である。たとえばkNNで最適なk個の近傍点を見つけるためには多くの点との距離を計算・比較する必要がある。以前紹介した次元削減によって計算量を減らす方法もあるが、根本的な解決にはならない。そこで、クラスタリングが役に立つのである。しかし、クラスタリングを行うことによってRSの精度が向上するわけではなく、精度と効率の両立は難しい。したがってクラスタリングをRSで用いる場合には注意が必要であり、精度と効率の妥協点を見つけなければならない。
クラスタリングは教師なし学習の一つである。似た特徴を持つ（距離の小さい）アイテム同士を同じグループにラベルづけを行う。同じグループ内のアイテム同士の距離は最小化し、グループ間の距離は最大となるようにラベリングを行うアルゴリズムである。クラスタリングには階層型クラスタリングと非階層型クラスタリングがある。非階層型クラスタリングでは各アイテムはただ一つのグループに属し、グループ同士の重なりは存在しない。階層型クラスタリングではクラスタリングした結果をさらにクラスタリングすることで階層構造を持つ。
多くのクラスタリングアルゴリズムではクラスタリングを最適化問題として帰着することができる。可能なクラスタリングパターンをすべて試し、もっともよいクラスタリングを採用することが理想である。しかし、これはNP困難の問題である。どのクラスタリングアルゴリズムを用いるのか、クラスタリングに用いる特徴量の選択、類似度や距離をどの指標を用いて表現するかなど様々な要素があり、最善のクラスタリングを選択することは非常に難しい。
2.4.1 k-Means
k-Means は非階層型クラスタリングのアルゴリズムの一つである。N個のアイテムをk個のクラスタにクラスタリングすることを考える。各グループの中心座標をセントロイドと呼ぶ。クラスタリング後に各クラスタにラベルづけされた点とセントロイドの距離の和が最小になるようにクラスタリングするのがk-Meansのアルゴリズムである。その各距離は以下の式によって定義される。
E=\sum_{j=1}^{k}\sum_{n\inS_{j}}d(x_{n},\lambda_{j})
x_nは各アイテムのベクトル、λ_jはクラスタjのセントロイドを表すベクトルであり、S_jはクラスタjにラベルづけされたアイテムの集合、dは距離を表す。上式で示したEが最小になるように各アイテムのラベルづけを変更させていく。
まずk個のセントロイドをランダムに選択する。各アイテムをそれぞれ一番近いセントロイドと同じクラスタにラベル付けを行う。ラベルづけされたアイテムに応じてセントロイドを更新し、更新したセントロイドとの距離を比較することで、再び各アイテムを適切なクラスタにラベルづけを行う。すべてのアイテムがグループを移動しなくなった時点で計算を終了する。実際には効率を考慮してしきい値のようなものを設け、移動するアイテムの数が一定数を下回った時点でクラスタリングを終了する。
k-Meansには以下のような問題点がある。
1.適切なk（クラスタ数）を選択するにはクラスタリング対象の背景知識を必要とする
2.クラスタリング結果が初期のセントロイドの選択によって変化する
3. 各クラスタのアイテム数や密度、分布の仕方によっては適切にクラスタリングできない場合がある。また、外れ値を含む場合も適切にクラスタリングすることができない。からっぽのクラスタを生成してしまう場合がある。
k-Meansの利用例としてRSの前処理として用いる方法や、欠損値補間の手段として用いる方法もある。協調フィルタリングにkNNを用いる場合の前処理としてk-Meansで処理対象をクラスタリングして近傍探索を制限することでkNNで近傍k個の点を見つける手間を減らすことができる。ある研究結果では精度が5%下がったものの処理効率は大きく向上したことが報告されている。
2.4.2 Alternatives to k-Means
k-Means以外のクラスタリング手法が紹介されている。
・ Density-based clustering
クラスタリング対象の密度に注目した手法
ex) DBSCAN
・ Message-passing Clustering
（なんだかよくわかりませんでした…グラフ構造を用いてクラスタリングしている？）
Affinity Propagation
DNA配列や画像での顔認識に利用され、優れた結果を残している。
※あまり理解できなかったので以下の資料を読みました。わかりやすかったです。
http://stanag4172.m13.coreserver.jp/document/AffinityPropagation.rev2.pdf
次に、階層型クラスタリングを紹介する。階層型クラスタリングは入れ子の形でクラスタリングした木構造のクラスタリング結果を返すものであるが、階層型クラスタリングには主に二つのタイプがある。
- 各アイテムを別々のクラスタとして扱い、マージしていくことで木構造を実現させる
- 各アイテムを同一のクラスタであるとして扱い、分割していくことで木構造を実現させる。
k-Means以外のクラスタリング手法を紹介したが、実際にRSに応用されていない。k-Meansのシンプルさと精度の良さが他の手法を上回っているからである。しかし、Message-passing Clusteringについてはすでに他の分野で良い結果を残しており、グラフ構造を用いたアルゴリズムもRSに応用できるため、近い将来にはこのタイプのクラスタリング手法を用いられるだろう。
2.5 Association Rule Mining
Association Rule Mining （日本語でいうと相関ルールマイニングというやつですね）は他のアイテムに関する出来事からあるアイテムの出来事を予測するようなルールを発見する手法である。ここで注意しなければならないのは二つのアイテムの出来事を因果関係ではなく共起に関する問題として扱うのである。したがって、2.3.3で紹介したrule-based clusteringとは異なる手法である。
ここで、itemsetを1つ以上のアイテムの集合として定義しk-itemsetをk個のアイテムからなるアイテム集合として定義する。itemsetの出現回数をsupport count(支持度)と呼び、その割合をsupportと呼ぶ。当然のことではあるが、support countは全集合の出現回数よりもちろん小さい。たとえば、(Milk, Beer, Diaper)= 0.12であれば、三つの単語Milk, Beer, Diaperという単語を含む文書が全体のうち0.12の割合で存在するという意味になる（合ってるのかな…）。A frequent itemsetはある定められたしきい値minsupthreshholdよりも大きいsupportを持つアイテムセットのことを指す。Association RuleはアイテムXとYが与えられた場合に次のように表現される。
X \Rightarrow Y
ex) (Milk, Beer) \Rightarrow (Diaper)
Xを含むアイテムのなかでYも含むアイテムの出現回数をconfidence(信頼度)と呼ぶ。confidenceについてもしきい値minconfthreshholdを定める。
Association Rule Miningの目的は、supportとconfidenceのそれぞれのしきい値を両方とも超えるルールをすべて見つけ出すことにある。総当たり法（the brute-force approach）では考えられるルールの組み合わせをすべてリストアップし、しきい値を満たすかどうかすべてチェックしていく。しかし、この方法では計算コストが非常に高い。そこで、2ステップに分けることを考える。
- minsupthreshholdの値を超えるsupportを持つアイテムセットをすべてリストアップする
- 1のステップを通過したルールのみconfidenceを計算する。
計算量を最適化する手法は複数存在するが、広い意味ではルールの候補を減らす問題へと帰着することができる。もっとも一般的な手法としてApriori principleが挙げられる。頻繁に出現する集合のサブセットも頻繁に出現するだろうという考え方を用いたものである。Association Rule Miningの場合、supportの定義から、集合の部分集合のsupportが元の集合のsupportを超えることはないためApriori Principleを適用することができる。
Association Rule Miningの効果はある程度知られているが、RSの主流とはなっていない。なぜなら、この手法はトランザクションを明確に把握する必要があり、柔軟性に欠けるからである（各アイテムのセットや共起回数などをすべて把握しなければならないから？）。しかし、かと言ってRSに全く使えないかと言えばそうではなく、他の手法と併用することで優れた推薦結果を得られることが複数の研究により報告されている。
2.6 Conclusions
本章ではRSに応用できるデータマイニング手法について述べてきた。（応用部分については僕が勝手に端折った部分も多いです…）主なテーマとしては、データマイニングで用いる類似度や距離の定義、サンプリング、次元削減、分類器、クラスタリング手法などを扱った。
いくつかの分類器を紹介してきたが、RSにおいて適切な分類器を選択することは非常に難しい。内容ベースか、モデルベースか、分類対象は何かなど考慮すべき要素は非常に多い。複数の分類器を組み合わせて使うこともできる。つまり、簡単に結論付けられる問題ではないのである。したがって推薦タスクによって分類器を使い分けるが最も適切であると言えるだろう。適切な分類器と一言で言っても、精度だけではなく計算効率を考える必要もある。
クラスタリングについては、RSの精度を向上させるために用いられているが、アイテムのスパース性を考慮してSVDのような次元圧縮が一般的に行われている。様々な種類の分類器がRSに用いられている一方で、クラスタリング手法についてはk-Meansの精度と効率の良さから他の大体手法が応用されていない。したがって、階層型クラスタリングやMessage-passing algorithmなどの他の手法について将来の研究に期待が寄せられている。
Association Rule Miningはトランザクションを正確に把握できる場合おいて直感的な枠組みをアイテムの推薦に与えることができた。アルゴリズムとして良い結果を残している一方で現在は採用されている例が少ない。
RSの設計において適切なデータマイニング手法を選択することは難しい。RSは多くの制約条件が伴う複雑なタスクである。しかし、本章で得た知識を用いて読者がより良い選択ができることを期待している。
お疲れ様でした！！ついにChapter2が終わりました。今回の更新はめちゃめちゃ時間がかかりました…
分からなくてサボった部分も少しありますが（おい）、詳しすぎず浅すぎずきれいにまとめられていて分類器やクラスタリングに関して知識が深まった気がします。しかし、まだまだ理解が浅いですね…
割と飛ばしているのでこの記事を読んだだけでは分からないと思いますが、アルゴリズムの解説だけではなく、各アルゴリズムの研究での応用例が割と多く載っています。自分で推薦システムを作りたい！！ってなったときの参考書として非常に使えそうです。
Chapter3は内容ベースのRSに関する最新情報とトレンドに関する内容が書かれています。
引き続きよろしくお願いします。