名古屋検索勉強会での発表資料です。
https://search-nagoya.connpass.com/event/146107/

概要

• クラスタリングアルゴリズム：文書集合をクラスターという部分集合にグループ分けするアルゴリズム

クラス分類とクラスタリングの違い

• クラスタリング：教師なし学習で文書をグループ化
• クラス分類：教師あり学習で文書をグループ化

クラスタリングの分類

クラスタ間の関係

• フラットクラスタリング：クラスタ間に構造を持たない
• 階層的クラスタリング：クラスタ間に階層あり

クラスタへの割り当て

• ハードクラスタリング：各文書が1つのクラスタに割り当てられる（ハードな割り当て）
• ソフトクラスタリング：各文書が全クラスへの分布として割り当てられる（ソフトな割り当て）

16.1 情報検索でのクラスタリング

クラスター仮説

同じクラスターの文書は、情報要求への関連性について同じように振る舞う。
本質的には、14章の連続性仮説（近接性仮説はたぶん間違い）である。

情報検索におけるクラスタリングのアプリケーション

検索結果クラスタリング

• 文書がまとまっていた方が簡単に調べられる
• 検索用語が異なる意味で使われている場合に有用
  • 例："jaguar"の意味は車、動物、OSなどがある。
• 再現率を向上させる

スキャッターギャザー

• ユーザが選択したクラスタの集合をクラスタリングする？
• きれいに組織化されていない
• 以下のとき有用
  • ユーザがどの検索用語を使うべきか確信を持てないとき
  • 検索よりブラウジングを好むとき
• 

言語モデル化

• Google Newsなど ※よく分からなかった

クラスタに基づいた検索

• クエリにもっとも近いクラスターを見つけ、そのクラスタの文書だけを考慮する
• クエリに対するすべての文書の類似性を計算するのは遅い。
• 文書の個数よりもクラスタの個数の方がはるかに小さい

16.2 問題設定（ハードクラスタリング）

• $K$ : クラスターの個数
• $D$ : 文書集合
• 目的関数：クラスタリングの品質を評価する関数
  • 文書間や重心の平均距離を最小化する
  • 文書間や重心の類似性を最大化する（上と同じ）
• $\gamma$: 目的関数を最小化する割り当て
  • どのクラスタも空でない
  • 全射

16.2.1 濃度―クラスの個数

• クラスタリングで困難な問題：クラスの個数を決めること
• クラスタの個数：濃度（cardinarity）とも呼ぶ。以下 $K$ と表記する。

16.3 クラスタリングの評価

• 品質の内部基準
  • 「クラスタ内の類似性を高く、クラスタ間の類似性を低くする」という目標の定式化
  • 必ずしもアプリケーションにおける効果が高いとは限らない
• 品質の外部基準
  • クラスタリングがゴールドスタンダードにどの程度適合するか
  • ゴールドスタンダード：評価ベンチマーククラスの集合。人間の判断による基準

4つの品質の外部基準

• 純度(purity)
• 正規化相互情報量
• Randインデックス
• F値

純度

• 定義？（合っているか不明）
  • 正解のクラスのデータをどの程度含むかという指標P
  • その指標Pを、各クラスタのデータ数による重み付き平均をとったもの
  • http://nlp.dse.ibaraki.ac.jp/~shinnou/zemi2008/Rclustering/r-tanaka-0415.pdf 参考
• 単純かつ透過は評価尺度

純度の例（図16.4）

純度の特徴

• 悪いクラスタリング: 純度0
• 完全なクラスタリング：純度1
• クラスタの個数が多いと、純度が高くなりやすい
• 文書の数とクラスタの数が同じなら、純度は1になる。
• クラスタリングの品質とクラスタの個数のトレードオフに、純度を使うことができない
  • ⇒ 純度で評価するには、クラスタの個数を固定する必要あり？

正規化された相互情報量（NMI）

• MI: 相互情報量
  • K=Nのとき最大になる。純度と同じ問題。

※分かりませんでした

Randインデックス

クラスタリングされた文書対（N(N-1)/2個）に関して、TP,TN,FP,FNを考える。

• TP(true-positive)：類似した2文書を同じクラスタに割り当てる
• TN(true-negative)：異なる2文書を異なるクラスタに割り当てる
• FP(true-positive)：異なる2文書を同じクラスタに割り当てる
• FN(false-negative)：類似した2文書を異なるクラスに割り当てる

※「クラスタリングについての、情報理論的解釈に代わるもの」が分からなかった

RI(Rand index)の定義

• 単純な精度を表す式になる

Rand Indexの TP+FPを計算する

正(Positive)の総数を算出。
同じクラスターにある文書対の総数は、

TP+FP={}_6C_2+{}_6C_2+{}_5C_2=
\begin{pmatrix}
6 \\
2 \\
\end{pmatrix}
+
\begin{pmatrix}
6 \\
2 \\
\end{pmatrix}
+\begin{pmatrix}
5 \\
2 \\
\end{pmatrix}

=40

※丸括弧は組み合わせを表す

Rand IndexのTPを計算する

TPは、類似した2文書を同じクラスタに割り当てた個数なので、クラスタ内のクラスごとに文書対の数をもとめる。

Rand Indexを計算する

前述の方法で、TP,FP,TN,FNを求めると、Rand Indexは以下の値になる。

F値

• RIではFPとFNに同じ重み
  • 類似文書の分離は、異なる文書を同じクラスに入れるよりも悪いときもある
• F値を使って、FPよりFNのペナルティを大きくする
  • $\beta > 1$

16.4 K平均法

• 目標：クラスタの中心から平均二乗ユークリッド距離を最小化する
• クラスタの中心：クラスターωにある文書の重心μ

• ロッキオ分類の重心と同じ式
  • ロッキオ分類ととの違いはラベル付き訓練集合がないことが異なる？

※ ロッキオ分類とは？

重心の評価

• 残差平方和（RSS）
• K平均法の目的：RSSの最小化

K平均法のステップ

1. ランダムに選んだ文書のシードを最初の重心にする

※ω∪xは何を表す？

K平均法のステップを可視化したサイト
http://tech.nitoyon.com/ja/blog/2013/11/07/k-means/
http://shabal.in/visuals/kmeans/4.html

K平均法の停止条件

• 固定回数Iの反復が終了
• クラスタへの割り当てが変わらない
• 重心が変わらない（上と同じ）
• RSSが閾値を切ったら
• RRSの減少が閾値を切ったら

K平均法の収束

• RSSは単調減少する。以下、その説明

1. 反復時に各ベクトルが最も小さい重心に割り当てられる？
2. 新しい再計算ステップにおいて、新しい重心がRSSが最小となるベクトルvになる？

※単調現象する理由が分からなかった

極小値

• 極小値に到達する可能性がある
• タイ(tie)で解消？
• いくつかの重心が等距離にある場合、インデックスが最も小さいクラスタに文書を割り当てる？

※タイ（tie）とは何か？
※「インデックスが最も小さいクラスタに文書を割り当てる」とは？

シード選択（初期値）に有効なヒューリスティック

3種類ある。

• シード集合から外れ値を除く
  • 外れ値が多いと、どのクラスタにも適合しない可能性がある
• 複数の始点を試して、最小のコストのクラスタリングを選ぶ
• 他の手法（階層的クラスタリングのようなもの）からシードを選ぶ

シード選択の重要性

最初のシードによって、クラスタリング結果が大きく異なる

計算コスト

* M: 次元数
* K：クラス多数
* N：文書数
* I：反復回数

• ベクトル距離の計算: O(M)
• 再割当ステップ：O(KNM)
• 重心の再計算：O(NM)
• 全体の計算量：O(IKNM)

ベクトルの疎密による計算速度

• 2文書間の距離を計算：疎なベクトルの計算
  • ⇒ 計算が速い

• 重心の計算：密なベクトルの計算

  • ⇒ 計算が遅い

• Kメドイド法で解決

  • 重心でなく、重心にもっとも近いベクトル「メドイド」を計算する
  • メドイドは疎な文書ベクトル

※なぜメドイドは疎な文書ベクトルなのか？

16.4.1 K平均法のクラスター濃度

クラスタの個数（クラスタ濃度）をどのように選ぶか？

$RSS_{min} (K)$という、Kに関する単調減少関数を定義する。

• 0つ目：目的関数に従って最適なKを選ぶ
  • クラスタの個数Kが、文書の個数Nと一致する場合は、$RSS_{min} (K)$は最小値0になる。
  • ⇒ 最適なクラスタリングではないので、この方法は却下
• 1つ目：ヒューリスティックス
  • $RSS_{min} (K)$の傾きが緩やかになるときのKから、選択する
  • ⇒ Elbow Method（肘） https://en.wikipedia.org/wiki/Elbow_method_(clustering)
• 2つ目：ペナルティーを課す
  • モデル計算量？
  • 赤池情報基準？

※モデル計算量、赤池情報基準が分からない
https://ja.wikipedia.org/wiki/赤池情報量規準

16.5 モデルに基づいたクラスタリング

データがモデルにより生成されると仮定して、データから元のモデルを回復（推定?）する。
回復したモデルが、クラスタとクラスタへの文書の割り当てを定義する

EMアルゴリズム(expectation-maximization algorithm)(期待値最大化アルゴリズム)
* Eステップ：
* Mステップ

※「ノイズが正規分布で、共分散が球状ならば、この方法で球形のクラスタができる」が分からない。「共分散が球状」？

共分散が球状とは？

その他

参考サイト

• クラスタリング入門
• クラスタリング

scikit-learnのKMeansクラス

初期化や打ち切り条件の参考になるかもしれない。
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html

初期化にはk-means++法が選択できる。

正誤表

• P312
  • (誤) クラスタリング仮説は、本質的には14章の近接性仮説である
  • (正) クラスタリング仮説は、本質的には14章の連続性仮説である