(57)【要約】【課題】  Ｋ平均法では、データが高次元の場合、低品質な局所最適解に陥りやすく、高精度のクラスタリング結果が得にくい点がある。一方、球面Ｋ平均法では、文書を表すベクトルｘnは、高次元となることが多く、特に、語彙数Ｖが大きい場合、低品質な局所最適解に陥りやすいという問題点がある。【解決手段】  有限個の重要単語を文書群データベース１１の文書群から選び出す重要単語群選択手段１３と、各重要単語が出現する文書群の単語出現頻度ベクトルを構成する単語出現頻度ベクトル構成手段１４と、文書群の前記単語出現頻度ベクトルの平均値を取ることにより、有限個の代表ベクトルの候補を構成する代表候補ベクトル構成手段１５と、前記代表候補ベクトルと前記単語出現頻度ベクトルとの間の類似度の総和を最大にする代表ベクトルを構成する代表ベクトル構成手段１６と、前記代表ベクトルを用いて文書のクラスタリングを行うクラスタリング手段１７とを有する【選択図】    図１
2005346223.tif 000002
【特許請求の範囲】
【請求項１】
文書群記憶手段に蓄積された類似の文書群を、複数のクラスタに分割する文書クラスタリング方法において、
コンピュータが、有限個の重要単語を文書群から選び出し、前記各重要単語が出現する文書群の単語出現頻度ベクトルの平均値を取ることにより、有限個の代表候補ベクトルを構成し、該代表候補ベクトルと前記単語出現頻度ベクトルとの間の類似度の総和を最大にする代表ベクトルを選択し、該代表ベクトルを用いて文書のクラスタリングを行う
ことを特徴とする文書クラスタリング方法。
【請求項２】
文書群記憶手段に蓄積された類似の文書群を、複数のクラスタに分割する文書クラスタリング装置において、
有限個の重要単語を文書群から選び出す重要単語群選択手段と、
前記各重要単語が出現する文書群の単語出現頻度ベクトルを構成する単語出現頻度ベクトル構成手段と、
前記文書群の前記単語出現頻度ベクトルの平均値を取ることにより、有限個の代表ベクトルの候補を構成する代表候補ベクトル構成手段と、
前記代表候補ベクトルと前記単語出現頻度ベクトルとの間の類似度の総和を最大にする代表ベクトルを構成する代表ベクトル構成手段と、
前記代表ベクトルを用いて文書のクラスタリングを行うクラスタリング手段とを有する
ことを特徴とする文書クラスタリング装置。
【請求項３】
文書群記憶手段に蓄積された類似の文書群を、複数のクラスタに分割する文書クラスタリングプログラムにおいて、
コンピュータに、
有限個の重要単語を文書群から選び出すステップと、
前記各重要単語が出現する文書群の単語出現頻度ベクトルを構成するステップと、
前記文書群の前記単語出現頻度ベクトルの平均値を取ることにより、有限個の代表候補ベクトルを構成するステップと、
前記代表候補ベクトルと前記単語出現頻度ベクトルとの間の類似度の総和を最大にする代表ベクトルを選択するステップと、
前記代表ベクトルを用いて、文書のクラスタリングを行うステップとを実行させる
ことを特徴とする文書クラスタリングプログラム。
【請求項４】
請求項３に記載の文書クラスタリングプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的に蓄積された文書群を、類似した文書が同じクラスタになるように分割する、文書クラスタリング方法、文書クラスタリング装置、文書クラスタリングプログラムならびにそのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
文書クラスタリング技術の著名なものとしては、たとえば、非特許文献１に記載されているような、球面Ｋ平均法がある。球面Ｋ平均法は、クラスタリング手法として極めて著名で、たとえば、非特許文献２に記載されているようなＫ平均法を、文書クラスタリングに適用したものである。
【０００３】
以下、球面Ｋ平均法について、簡単に説明する。
【０００４】
文書クラスタリングは、Ｎ個の文書
【０００５】
【数１】
2005346223.tif 000003
【０００６】
を、Ｋ個のクラスタに分割する問題である。文書ｄnがｋ番目のクラスタに属するときは、ｙn,k＝1、そうでないときは、ｙn,k＝０とする。
【０００７】
【数２】
2005346223.tif 000004
【０００８】
（ベクトルをアンダーラインで表している。以下、同じ。）
【０００９】
また、多くの文書クラスタリング手法では、文書を、単語出現頻度ベクトルにより表す。すなわち、単語出現頻度ベクトルｘn＝（ｘn,1，…，ｘn,V）により、文書ｄnを表す。ここで、Ｖは、語彙Ｗ＝｛ｗ1，…，ｗV｝の中の単語の総数を、ｘn,iは、文書ｄnにおける、単語ｗiの出現頻度をそれぞれ表す。（日本語において、単語出現頻度ベクトルｘnを構成するには、形態素解析などにより、単語への分かち書きを行う必要がある。）このとき、ｘnに対して、後に詳述するｔｆ−ｉｄｆ（term frequency-inversed document frequency）変換を施すこともある。また、球面Ｋ平均法では、ｘnをＬ2ノルムにより正規化する。以後、簡単のために、このような変換が施された単語出現頻度ベクトルもｘnで表し、また、単語出現頻度ベクトルと呼ぶ。
【００１０】
各クラスタに対して、代表ベクトル
【００１１】
【数３】
2005346223.tif 000005
【００１２】
を考え、
【００１３】
【数４】
2005346223.tif 000006
【００１４】
とする。そして、単語出現頻度ベクトルと代表ベクトル間の類似度ｓ（・，・）を与える。たとえば、球面Ｋ平均法では、コサイン類似度を用いる。すなわち、
【００１５】
【数５】
2005346223.tif 000007
【００１６】
とする。
【００１７】
（球面）Ｋ平均法では、次の目的関数Ｊ（Ｙ，Θ）を考え、この目的関数を最大にするようなクラスタリング結果
【００１８】
【数６】
2005346223.tif 000008
【００１９】
と、代表ベクトル
【００２０】
【数７】
2005346223.tif 000009
【００２１】
を求める。
【００２２】
【数８】
2005346223.tif 000010
【００２３】
この目的関数の値は、ｘnと、ｘnが属するクラスタの代表ベクトルとの間の類似度Σk
ｙn,kｓ（ｘn，θk）の、ｎに関しての和に等しい。
【００２４】
Ｋ平均法では、ＹとΘを、収束するまで、逐次、更新することにより、目的関数Ｊを局所的に最大にする解
【００２５】
【数９】
2005346223.tif 000011
【００２６】
を求める。そして、得られた
【００２７】
【数１０】
2005346223.tif 000012
【００２８】
をもって、クラスタリング結果とする。
【００２９】
ここで、前記ｔｆ−ｉｄｆ変換について説明しておく。
【００３０】
ｔｆは、文書中における語の出現頻度を表し、たとえば、ｔｆ（ｎ，ｉ）は文書ｄnにおける語ｗiの出現頻度を表す。また、ｄｆは、語が出現した文書数を表し、たとえば、ｄｆ（ｉ）は、語ｗiが出現した文書数を表す。ｉｄｆは、ｄｆを基に定義される量で、いくつかの定義があるが、最もよく用いられる定義の一つとして、
【００３１】
【数１１】
2005346223.tif 000013
【００３２】
があげられる（ただし、ここでＮは文書の総数を表す）。ｔｆ−ｉｄｆはｔｆとｉｄｆを掛け合わせたもので、
【００３３】
【数１２】
2005346223.tif 000014
【００３４】
と定義される。ｔｆｉｄｆの目的は、文書中での語の重み付けであって、文書中での語の出現頻度が高く、出現した文書数が少ない語の重みが大きくなる。
【非特許文献１】Spherical k-means, Dhillon, I.S. & Modha, D.S.(2001).“Concept Decompositions for large sparse text data using clustering”Machine Learning, 42, 143-175
【非特許文献２】K-means, Hastie, T., Tibshirani, T., Friedman, J. & Friedman, J. H.(2001).“The Elements of statistical Learning”.Springer Verlag
【発明の開示】
【発明が解決しようとする課題】
【００３５】
Ｋ平均法では、逐次更新により、目的関数を最大にする解を探索する。そのため、Ｋ平均法で得られる解は、その解の近傍における最適解、すなわち、局所最適解である。Ｋ平均法の問題点として、データが高次元の場合、低品質な局所最適解に陥りやすく、高精度のクラスタリング結果が得にくい点がある。一方、球面Ｋ平均法では、文書を表すベクトルｘnは、高次元となることが多い。そのため、特に、語彙数Ｖが大きい場合、球面Ｋ平均法は、低品質な局所最適解に陥りやすいという問題点がある。
【課題を解決するための手段】
【００３６】
高次元データに対するＫ平均法の解が、低品質な局所最適解となる原因の一つに、探索する解の空間が広いため、多数の局所最適解が存在する点がある。そこで、本発明では、探索空間のより狭い離散最適化問題を考え、この最適化問題を解くことにより、Ｋ平均法が持つ低品質な局所最適解の問題を克服する。
【００３７】
本発明では、Ｋ平均法と同様の目的関数（※）の最大化を考える。ただし、代表ベクトルθkに対して制約を設け、解の探索空間を限定する。具体的には、代表ベクトルθkが取り得る値を、Ｍ（＞Ｋ（Ｋ個のクラスタに分割する））個の代表候補ベクトルに限定する。そして、これらの代表候補ベクトルの中から、目的関数（※）を最大にする代表ベクトルの組み合わせを探索する。この探索問題は、離散最適化問題となり、Ｋ平均法よりも、解の探索空間が限定される。したがって、解の探索空間を適切に限定すれば、Ｋ平均法よりも、高品質な解が得られると期待できる。
【００３８】
このとき、精度の高いクラスタリングを実現するには、適切な代表候補ベクトルを構成する必要がある。そこで、本発明では、文書がもつ特性を利用し、次の手順により、代表候補ベクトルを効率よく構成する。
【００３９】
まず、重要単語群を適当な方法で定める。そして、この単語群の各単語について、その単語が出現した文書群を求める。これらの文書群の単語出現頻度ベクトルの平均値を代表候補ベクトルとする。この手続きを、重要単語群に属する全ての単語に対して行うことにより、複数の代表候補ベクトルを構成する。
【００４０】
このようにして得られた代表候補ベクトルは、代表ベクトルの候補として有効であると考えられる。なぜなら、特定の単語、たとえば「コンピュータ」が出現した文書は、「コンピュータ」に関連した単語（「メモリ」や「ＣＰＵ」）が出現しやすい。そのため、「コンピュータ」が出現した文書の単語出現頻度ベクトルの平均ベクトルは、「コンピュータ」に関するクラスタの代表ベクトルとして適切であると考えられるからである。ただし、どのベクトルが代表ベクトルとして適切であるかは自明ではないので、Ｍ個の代表候補ベクトルより、Ｋ個の代表ベクトルを選択する。
【発明の効果】
【００４１】
データが高次元の場合であっても、文書を表すベクトルｘnが高次元で語彙数Ｖが大きい場合であっても、低品質な局所最適解に陥ることなく、精度のよいクラスタリング結果を得ることができる。
【発明を実施するための最良の形態】
【００４２】
図１および図２は、本発明の一実施形態を示すもので、図１は本発明の文書クラスタリング装置のブロック構成図である。
【００４３】
本文書クラスタリング装置は、文書入力手段１０と、文書群データベース１１と、中央処理装置内の文書出力手段１２、重要単語群選択手段１３、単語出現頻度ベクトル構成手段１４、代表候補ベクトル構成手段１５、代表ベクトル構成手段１６、クラスタリング手段１７、および結果出力手段１８とから構成されている。
【００４４】
前記文書入力手段１０には、キーボードやマウスなどが考えられる。
【００４５】
前記文書群データベース１１は、文書入力手段１０によって入力された文書群を蓄積する。
【００４６】
前記文書出力手段１２は、文書群データベース１１から文書群を出力するように命令があると、文書群データベース１１から文書群を出力する。
【００４７】
前記重要単語群選択手段１３は、まず、文書群において、Ｍ個の重要単語群ＷC＝｛ｗC1，…，ｗCM｝を、なんらかの手法、たとえば、ｔｆ−ｉｄｆの値が上位の語により定める。ｔｆ−ｉｄｆは、文書中の語の重みを表す量であるが、この量を文書全体について合わせたものもｔｆ−ｉｄｆと呼ばれる。このとき、単語ｗiのｔｆ−ｉｄｆ ｓｃｏｒｅ ｓ（ｉ）は、
【００４８】
【数１３】
2005346223.tif 000015
【００４９】
となり、ここでは、ｓ（ｉ）の値の高い上位Ｍ個の語を用いて、クラスタリングの代表ベクトルの候補である重要単語群ＷC＝｛ｗC1，…，ｗCM｝を構成する。
【００５０】
前記単語出現頻度ベクトル構成手段１４は、文書ｄnを表す単語出現頻度ベクトルｘn＝（ｘn,1，…，ｘn,V）を構成する。ここで、Ｖは、語彙Ｗ＝｛ｗ1，…，ｗV｝の中の単語の総数を、ｘn,iは、文書ｄnにおける、単語ｗiの出現頻度をそれぞれ表す。
【００５１】
前記代表候補ベクトル構成手段１５は、各重要単語ｗCcに対して、この語が出現した文書群Ｄcを求め、Ｄcに属する文書の単語出現頻度ベクトルの平均値をφcとする。すなわち、
【００５２】
【数１４】
2005346223.tif 000016
【００５３】
とする。得られたＭ個のφcを、代表ベクトルθkの代表候補ベクトルとする。
【００５４】
前記代表ベクトル構成手段１６および前記クラスタリング手段１７は、式（※）の目的関数Ｊ（Ｙ，Θ）を最大にする、
【００５５】
【数１５】
2005346223.tif 000017
【００５６】
を求める。すなわち、次の最適化問題を解く。
【００５７】
【数１６】
2005346223.tif 000018
【００５８】
この最適化問題は離散最適化問題となる。Ｋ平均法の最適化問題では、Θは任意のＶ次元ベクトルであったが、本文書クラスタリング装置では、Θは有限個のＭ個の代表候補ベクトルの中から選択される。したがって、解の探索空間が限定されるため、低品質な局所最適解に陥りにくくなる。
【００５９】
式（※※）の離散化問題を解くには、greedy searchアルゴリズムなどが適用できる。たとえば、Θに関するgreedy searchでは、次の手順により、最適なΘを探索する。
【００６０】
最初に、初期値Θ(0)を定める。そして、各代表ベクトル
【００６１】
【数１７】
2005346223.tif 000019
【００６２】
について、クラスタの代表ベクトルを目的関数の値を大きくするように更新する。たとえば、θkを次の式にしたがって更新する：
【００６３】
【数１８】
2005346223.tif 000020
【００６４】
ただし、ｍａｘYＪ（Ｙ，Θ(t)）の計算の際には、θk以外の代表ベクトル
【００６５】
【数１９】
2005346223.tif 000021
【００６６】
の値は固定する。次に、Θの更新を収束するまで繰り返し、得られた解
【００６７】
【数２０】
2005346223.tif 000022
【００６８】
を用いて、
【００６９】
【数２１】
2005346223.tif 000023
【００７０】
を得、
【００７１】
【数２２】
2005346223.tif 000024
【００７２】
をクラスタリング結果として、前記結果出力手段１８が出力する。そして、たとえば、クラスタリングされた状態で再度、データベースに蓄積する。
【００７３】
図２は、コンピュータに、本発明の文書クラスタリングプログラムを実行させたときの、コンピュータの動作を示したフローチャートである。
【００７４】
まず、クラスタリングの対象となる文書群が、文書入力手段１０により入力されると、文書群データベース１１に文書群が一時、保存される（Ｓ１）。
【００７５】
次に、文書出力手段１２が、文書群データベース１１から文書を出力し、重要単語群選択手段１３が、文書群において、Ｍ個の重要単語群ＷC＝｛ｗC1，…，ｗCM｝を、たとえば、ｔｆ−ｉｄｆの値が上位の語により定める（Ｓ２）。
【００７６】
次に、単語出現頻度ベクトル構成手段１４が、文書ｄnを表す単語出現頻度ベクトルｘn＝（ｘn,1，…，ｘn,V）を構成する（Ｓ３）。ここで、Ｖは、語彙Ｗ＝｛ｗ1，…，ｗV｝の中の単語の総数を、ｘn,iは、文書ｄnにおける、単語ｗiの出現頻度をそれぞれ表す。
【００７７】
続いて、代表候補ベクトル構成手段１５が、各重要単語ｗCcに対して、この語が出現した文書群Ｄcを求め、Ｄcに属する文書の単語出現頻度ベクトルの平均値をφcとする。すなわち、
【００７８】
【数２３】
2005346223.tif 000025
【００７９】
とする。得られたＭ個のφcを、代表ベクトルθkの代表候補ベクトルとする（Ｓ４）。
【００８０】
そして、代表ベクトル構成手段１６は、得られた代表候補ベクトルの中から（※）式を最大にする組み合わせを探索する。すなわち、
【００８１】
【数２４】
2005346223.tif 000026
【００８２】
を解く（Ｓ５）。
【００８３】
続いて、クラスタリング手段１７は、得られた代表ベクトルを用いて、
【００８４】
【数２５】
2005346223.tif 000027
【００８５】
より、
【００８６】
【数２６】
2005346223.tif 000028
【００８７】
をクラスタリング結果とする（Ｓ６）。
【００８８】
最後に、クラスタリング結果を、結果出力手段１８が出力し（Ｓ７）、クラスタリングされた状態でデータベースに蓄積などを行う。
【００８９】
なお、式（※※）の解き方は前記に限ったものではない。
【００９０】
なお、この文書クラスタリングプログラムは、読み取り可能な記録媒体に記録させることにより実現可能であり、また、持ち運びなどをすることができる。
【実施例】
【００９１】
図３は、本発明を実際に施行し、その結果を実データを用いてグラフで表し、その有効性を示したものである。
【００９２】
評価用データとして、文書クラスタリングの評価に広く用いられている２０newsgroupsデータを用いた。２０newsgroupsデータは、２０のカテゴリに分類された文書である。この分類されたカテゴリと、クラスタリング結果との一致度により、クラスタリング性能を評価する。
【００９３】
本発明の有効性を評価するため、１０００個の文書をクラスタリングした際のクラスタリング精度（micro averaged precision）を、本発明と従来法である球面Ｋ平均法とで比較する。なお、Ｍ＝５００とし、類似度としては、コサイン類似度を用いた。
【００９４】
データの次元の影響を調べるため、用いる語彙の数Ｖの値を変化させた場合のクラスタリング精度の変化を調べた。このとき、用いる単語は相互情報量基準によって選択した。
【００９５】
図３より、本発明が、Ｋ平均法を上回るクラスタリング精度を達成し、その差は、データが高次元な場合、特に大きいことが分かる。
【図面の簡単な説明】
【００９６】
【図１】本発明の一実施形態に係る文書クラスタリング装置のブロック構成図である。
【図２】コンピュータに、本発明の文書クラスタリングプログラムを実行させたときの、コンピュータの動作を示したフローチャートである。
【図３】本発明の実施例と従来例の結果をグラフで比較した図である。
【符号の説明】
【００９７】
１１    文書群データベース
１２    文書出力手段
１３    重要単語群選択手段
１４    単語出現頻度ベクトル構成手段
１５    代表候補ベクトル構成手段
１６    代表ベクトル構成手段
１７    クラスタリング手段
【図１】
2005346223.tif 000029
【図２】
2005346223.tif 000030
【図３】
2005346223.tif 000031