情報検索概論 第7回
第7回は文書のクラスタリング
第8回はマルチメディア情報検索
第9回・第10回は深層学習を用いた情報検索
サイズが大きく、抽象的なデータの処理や検索
2ステップ
1. データを比較するための尺度を計算する
類似性の定義
データをベクトル空間に写像する
問題依存性が非常に大きい
文書、画像など、対象が変わると写像の方法も大きく変わる
2. 尺度を元にデータを求める形にする
分類、近傍検索、ランキングなど
結果となるグループをクラスタと呼ぶ
類似性
2つのテキストがどれくらい似ているかを表現する抽象概念
似ているものほど値が大きくなる
同一だと0、似ているほど値が小さくなる
距離の公理を満たす
なんだそれ momeemt.icon
非類似度で、かつ距離の公理を満たす場合が少ないらしい
距離の公理
非負性
$ \text{dist}(x, y) > 0
対称性
$ \text{dist}(x, y) = \text{dist}(y, x)
$ \text{dist}(x, z) \le \text{dist}(x, y) + \text{dist}(y, z)
この制限が厳しすぎて使えないことが多い
AとCは似ていて、BとCが似ていて、AとCが似ていないとき、三角不等式を常に適用、というか直感に合う形で適用できるわけではない
出現単語を単語の珍しさで補正する
$ \text{TF-IDF}(t, d) = \text{TF}(t, d) \cdot \text{IDF}(t)
文書に含まれる単語数だけでなく、文書の総数を単語を含む文書数で割った値の対数をかけてあげて補正する
紹介済み
対称性があるから
作成コストも格納コストも$ O(n^2)
クラスタリング手法
全体を徐々に分割して小クラスタを結合していく
クラスタリング結果が階層的になる
ざっくり分けたクラスタも、細かく分割したクラスタも得られる
デンドログラムの作成
分割型
徐々に分割しながら作成
凝集型
近いものを結合しながら作成
こちらの方が簡単
最下層（各テキストのみを持つ最小のクラスタを作る）を作ってから凝集していく
$ K個のクラスタを作成する
クラスタ間の類似性の計算
この計算方法が性能や結果傾向を決定付ける
2クラスタ間で最も高い類似度を採用する
$ \text{sim}(C_i, C_j) = \max_{t_i \in C_i, t_j \in C_j} \text{sim}(d_i, d_j)
テキスト数が多いクラスタが有利になる
大きなクラスタが発生しやすくなってしまう
大きいクラスタほど不利にするために、2クラスタ間で最も低い類似度を採用する
$ \text{sim}(C_i, C_j) = \min_{t_i\in C_i, t_j \in C_j} \text{sim}(d_i, d_j)
問題点
類似度が低いクラスタを繋ぐのが現実的ではない
チェイニングする結果よりはマシだが、孤立したテキストが0になってしまう
全てのテキストペアの平均値を採用する
$ \text{sim}(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{d_i\in C_i} \sum_{d_j \in C_j} \text{sim}(d_i, d_j)
経験則的にちょうど良い値を示すことがわかっている
クラスタ内の類似度の平均値
新たな文書を投入するとき、自己類似度が最も下がらないようなクラスタに追加する
問題点
計算量
類似度計算と比較の回数が多くて、$ O(n^3)
事前に類似度を計算しておくと空間計算量は増えるが、$ O(n^2 \log n)に落とせる
対象とするデータのサイズが大きいので空間計算量にも気を使う必要があるのか momeemt.icon
代表ベクトル
クラスタを簡潔に表す1つの文書ベクトルのこと
ベクトル空間に写像して距離を使う場合は、代表ベクトルが使える 文書ベクトルの平均値
文書間類似度
クラスタ間類似度
自己類似度アプローチの亜種
クラスタの評価指標を、クラスタ内文章から代表ベクトル間の距離の二乗和を引いたものとする
非階層型クラスタリング
一般的に階層型クラスタリングよりも効率が良い
結果が良いというわけではない
手法
など
単一パス法
適当な文書を1つ選んで$ C_1クラスタを生成する
閾値を超えたらクラスタに追加、そうでなければクラスタを生成
全ての文書を1度しか確認しないので計算量が$ O(n^2)で済むので効率的
→ 大規模文書集合のクラスタリングに向いている
文書を見る順番によって結果が変わる
閾値$ tのパラメータ依存性が強く、選択が難しい
k-means法
まずk個のクラスタ代表をランダムに決定する
全てのクラスタ代表が収束するまで、以下の操作をする
1. 各文書を最も近い代表のクラスタに挿入する
2. 全クラスタ代表を再計算する
めっちゃ時間かかりそうな気がするけどそうでもないのかな momeemt.icon
k-meansはかなり良く使われていると思っていた
効率と質のバランスが良いので、手法に悩んだらとりあえず使ってみる
計算量は$ O(lkn)
$ lは収束までの繰り返し回数
線形ではないが（$ nが増えると$ lも増えることが多いので）、二乗オーダーよりは高速な場合が多い（経験的）
初期値に依存するのと、局所解に陥る可能性がある
グラフ論的クラスタリング
グラフとして見做せる
全てのノード間に辺を持つ部分グラフ
クリークの中で極大のものを極大クリークと呼ぶ
極大クリークをクラスタと見なす
類似度$ t以上の場合には辺を持つことにする
情報が落ちて困りそう？ momeemt.icon
まあでも非階層型の手法でも実質的にその2値しか意味を持ってないなら良いのかな
グラフの全$ n個の頂点を、$ n-1個の辺で繋いだ木
全域木の中で、辺の重みの合計が最大になる木を最大全域木と呼ぶ 手法
辺の数$ mに対して、$ O(m\log n)
→ 階層型クラスタリング（単連結法）と同じ結果が得られる
じゃあダメでは？momeemt.icon