Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections(1992)

#クラスタリング

February 19, 2023

Scatter/Gatherは、ユーザーにクエリを入力するかわりに、システムが提示する文書のクラスタをユーザーに選ばせる情報検索の手法である。ユーザーが目的の情報にだどりつける適当なクエリをいつも作れるとはかぎらない。ユーザーが詳しくない分野の情報を調べるときは、クエリにつかえる用語を知らないかもしれない。また、ある分野の情報を広く浅く収集したいときは、クエリの単語によって検索対象を狭く限定したくないかもしれない。

Scatter/Gatherは、文書のクラスタを生成し、ユーザーに関心のあるクラスタを選んでもらい、選ばれたクラスタの文書だけから再度クラスタを生成する手順を繰りかえす情報検索の手法である。ユーザーが反復的にクラスタを選択するインタラクティブな手法であるため、ユーザーを待たせないように、高速にクラスタを生成しなければならない。そこで、クラスタリングを高速化するために、BuckshotとFractionationの2つのクラスタリング手法を提案する。 Buckshotは、Fractionationよりも速度を重視し、ランダムサンプルした文書のみをクラスタリングする。他方で、FractionationはBuckshotよりも精度を重視する。また、ユーザーがクラスタを選びやすくするために、クラスタを要約する手法としてCluster Digestを提案する。 Cluster Digiestは、クラスタをよく表す単語をクラスタ内の文書から抽出し、ユーザーに提示する。

文書を$\alpha$, その集合を$C$, $V$を$C$内にある単語の集合とおく。また、$c(\alpha)$を$\alpha$に出現する単語とその頻度をペアが要素で要素数が$|V|$の集合とする。

文書の類似度にコサイン類似度を採用し、文書$\alpha, \beta$の類似度$s(\alpha, \beta)$を $$ s(\alpha, \beta)=\frac{\langle g(c(\alpha)), g(c(\beta))\rangle}{||g(c(\alpha))||||g(c(\beta))||} $$ と定義する。 $||\cdot||$はノルム、$\langle\cdot\rangle$は内積である。 $g$は単調な減衰関数であり、実験では成分単位の平方根の乗積にすると良い結果がえられた。

また、文書集合$\Gamma$と文書$\alpha$の類似度$s(\Gamma, \alpha)$を定義するために、文書の$\alpha$について$\textit{profile}(\alpha)=\frac{g(c(\alpha))}{||g(c(\alpha))||}$とおく。 $$ \begin{align} \hat{p}(\Gamma)&=\sum_{\alpha\in\Gamma}p(\alpha)\\ p(\Gamma)&=\frac{\hat{\Gamma}}{||\hat{p}(\Gamma)||}\\ s(\Gamma, \alpha) &=\langle p(\Gamma), p(\alpha) \rangle \end{align} $$

クラスタの中心から遠い文書をクラスタから除けば、クラスタの意味がわかりやすくなることがある。クラスタ$\Gamma$の中心から最も近い、つまり$s(\alpha, \Gamma)$の大きい上位$m$個の文書集合$r_m(\Gamma)$をとする。クラスタ$\Gamma$を説明するためのCluster Digestは、$p(\Gamma)$のうち重みの大きい上位$w$個の単語と$r_m(\Gamma)$である。

BuckshotとFractionationは、最初のクラスタの中心を決めることで、ほかのクラスタリング手法を高速化するアルゴリズムであり、別のクラスタリング手法と組み合わせて使われる。 Buckshotは、クラスタ数を$k$, 文書数を$n$とすると、$\sqrt{kn}$個ランダムサンプルした文書のみにクラスタリングを適用し、求めたクラスタの中心を初期値にする。 Fractionationは、はじめに、$m>k$として文書集合$C$を$n/m$個のバケットに分割する。つぎに、別のクラスタリングを各バケットに適用し、文書数に対する$\rho$の割合だけクラスタを生成する。以降は、生成されたクラスタを1つの文書とみなし、クラスタ数が$k$になるまで、手続きを繰り返す。中心の初期値が決まれば、たとえば、文書を最近傍の中心に割りあてることで、クラスタをつくれる。

論文のリンク

雑記

解きたい問題はクエリを作れない状況での検索の質を向上することで、やや込み入った状況設定だったが、提案された手段はクラスタリングの高速化という分かりやすいものだった。手法の評価がなく、インタラクティブな手法であるため評価が難しいため、Scatter/Gatherがどの程度有効か分からない。単に、クラスタリングを高速化することを目的とした論文にして、既存手法と処理時間を比較したほうが完結した研究になった気がする。