(57)【要約】    【課題】  制度の高いクラスタ解析を行う。    【解決手段】  クラスタ集合入力部１０は、指定文書クラスタ集合を処理対象として入力する。クラスタ単位重み計算部１１は、クラスタごとにそのクラスタ内での単語の出現頻度に基づいて単語重みを計算する。統合単語重み計算部１２は、クラスタ単位単語重み計算部１１によりクラスタごとに求めた単語重みをクラスタ全体にわたって平均し統合単語重みを計算する。クラスタ解析部１３は、統合単語重み計算部１２により計算した統合単語重みを参照してクラスタ解析を行う。クラスタ解析部１３は、クラスタ解析終了条件を吟味し、条件が満たされないときには、文書クラスタ集合をクラスタ単位単語重み計算部１１以降に戻し、同じ処理を繰り返させる。クラスタ解析終了条件が満たされたときには、文書クラスタ集合をクラスタ集合出力部１４に供給し、クラスタ集合出力部１４が文書クラスタ集合を出力する。【選択図】  図２
2005063159.tif 000002
【特許請求の範囲】
【請求項１】
文書クラスタの集合を入力する文書クラスタ集合入力手段と、
文書クラスタごとに単語の重みを計算するクラスタ単位単語重み計算手段と、
文書クラスタごとの単語の重みに基づいて上記文書クラスタの集合をなす全文書における単語の重みを計算する全文書単語重み計算手段と、
上記全文書における単語の重みを参照して上記全文書を再度クラスタに分ける二次クラスタ解析手段とを有することを特徴とする文書クラスタ処理装置。
【請求項２】
全文書を受け取って最初のクラスタ解析を行って文書クラスタの集合を出力する一次クラスタ解析手段をさらに有する請求項１記載の文書クラスタ処理装置。
【請求項３】
上記二次クラスタ解析手段から出力される文書クラスタ集合を上記文書クラスタ集合に入力して上記クラスタ単位単語重み計算手段、上記全文書単語重み計算手段および上記二次クラスタ解析手段の処理を行い上記二次クラスタ解析手段のクラスタ解析処理を繰り返す請求項１または２記載の文書クラスタ処理装置。
【請求項４】
１の文書クラスタから他の文書クラスタに所属が変更する文書の個数が所定数に到達したときに上記二次クラスタ解析手段によるクラスタ解析処理の繰り返しを中止し上記二次クラスタ解析手段から出力されるクラスタ集合を最終的なクラスタ集合として出力する請求項３記載の文書クラスタ処理装置。
【請求項５】
上記二次クラスタ解析手段によるクラスタ解析処理の繰り返し回数が所定数に到達したときに上記二次クラスタ解析手段によるクラスタ解析処理の繰り返しを中止し上記二次クラスタ解析手段から出力されるクラスタ集合を最終的なクラスタ集合として出力する請求項３記載の文書クラスタ処理装置。
【請求項６】
上記クラスタ単位単語重み計算手段は、単語と文書クラスタとの間の相互情報量に基づいて単語の重みを算出する請求項１、２、３または４記載の文書クラスタ処理装置。
【請求項７】
上記全文書単語重み計算手段は、上記クラスタ単位単語重み計算手段により算出された文書クラスタごとの単語の重みを文書クラスタ全体にわたって平均して上記全文書における単語の重みを算出する請求項１〜６のいずれかに記載の文書クラスタ処理装置。
【請求項８】
文書クラスタ集合入力部が文書クラスタの集合を入力するステップと、
クラスタ単位単語重み計算部が文書クラスタごとに単語の重みを計算するステップと、
全文書単語重み計算部が文書クラスタごとの単語の重みに基づいて上記文書クラスタの集合をなす全文書における単語の重みを計算するステップと、
二次クラスタ解析部が上記全文書における単語の重みを参照して上記全文書を再度クラスタに分けるステップとを有することを特徴とする文書クラスタ処理方法。
【請求項９】
文書クラスタの集合を入力する文書クラスタ集合入力ステップと、
文書クラスタごとに単語の重みを計算するクラスタ単位単語重み計算ステップと、
文書クラスタごとの単語の重みに基づいて上記文書クラスタの集合をなす全文書における単語の重みを計算する全文書単語重み計算ステップと、
上記全文書における単語の重みを参照して上記全文書を再度クラスタに分ける二次クラスタ解析ステップとをコンピュータに実行させるために用いられることを特徴とする文書クラスタ処理用コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、文書クラスタ処理技術に関し、とくに、高精度にクラスタ解析を行えるようにするものである。
【背景技術】
【０００２】
文書集合から文書クラスタを求めるために、入力文書集合中での単語出現頻度を利用したＴＦ・ＩＤＦ（Ｔｅｒｍ  Ｆｒｅｑｕｅｎｃｙ／Ｉｎｖｅｒｓｅ  Ｄｏｃｕｍｅｎｔ  Ｆｒｅｑｕｅｎｃｙ）手法は広く一般に用いられているが、これはクラスタごとの単語の重要性までは考慮していない。そのため、あるクラスタにあまり関連がない文書でも、たまたまＴＦ・ＩＤＦ値が高い単語がクラスタと文書の双方に存在する場合、その文書がクラスタに組み込まれてしまうことがある。
【０００３】
個々の文書を人手でクラスタ分けし直すのはユーザの負荷が高いため、簡便にクラスタ解析の精度を向上させる方法が強く求められている。
【０００４】
なお、特許文献１には、特徴ベクトルを特異値分解し、クラスタリングの際に用いる類似ベクトルの次元を徐々に増やしていくことで最適なクラスタ数を自動的に決定する手法が開示されているが、上述の問題は未解決のままである。
【特許文献１】特開２００２−１８３１７１
【発明の開示】
【発明が解決しようとする課題】
【０００５】
この発明は、以上の事情を考慮してなされたものであり、あるクラスタにあまり関連がない文書でも、たまたまＴＦ・ＩＤＦ値が高い単語がクラスタと文書の双方に存在する場合、その文書がクラスタに組み込まれてしまうという問題を解決した文書クラスタ処理手法を提供することを目的としている。
【課題を解決するための手段】
【０００６】
この発明によれば、上述の目的を達成するために、特許請求の範囲に記載のとおりの構成を採用している。ここでは、発明を詳細に説明するのに先だって、特許請求の範囲の記載について補充的に説明を行っておく。
【０００７】
この発明の一側面によれば、上述の目的を達成するために、文書クラスタ処理装置に：文書クラスタの集合を入力する文書クラスタ集合入力手段と；文書クラスタごとに単語の重みを計算するクラスタ単位単語重み計算手段と；文書クラスタごとの単語の重みに基づいて上記文書クラスタの集合をなす全文書における単語の重みを計算する全文書単語重み計算手段と；上記全文書における単語の重みを参照して上記全文書を再度クラスタに分ける二次クラスタ解析手段とを設けるようにしている。
【０００８】
この構成においては、クラスタ集合入力手段により文書クラスタ集合を入力し、単語重みとする。クラスタ単位単語重み計算手段によりクラスタごとに単語の重み（単語重み、単語の重み付けともいう）を計算する。全文書単語重み計算手段は、クラスタごとの単語重みから全文書における単語重みを計算する。二次クラスタ解析手段は、入力されたすべての文書集合を、全文書における単語重みを参照して各クラスタに分ける。
【０００９】
全文書単語重み計算手段は、クラスタごとに単語の重みから、たとえば値を平均するなどして入力全体における単語重みを求める。単語の重みは、クラスタ内の単語頻度を利用する。以上の処理は繰り返して行うことができる。繰り返し回数は、例えば、予め定められた回数でもよいし、あるいは、クラスタの間で変更される文書の個数が所定値になったときに繰り返しを終了するようにしてもよい。
【００１０】
また、文書集合を入力として、ユーザから指定された条件でクラスタを抽出する一次クラスタ抽出手段を設けてもよい。
【００１１】
具体的な例では、クラスタごとの単語重みは、相互情報量の考え方を単語とクラスタについて応用して求める。一般に、ｘとｙの相互情報量Ｉ（ｘ，ｙ）の式は次である。
【００１２】
Ｉ（ｘ，ｙ）＝ｌｏｇ２［Ｐ（ｘ，ｙ）／｛Ｐ（ｘ）Ｐ（ｙ）｝］
ただし、Ｐ（ｘ）は全体におけるｘの頻度比、Ｐ（ｘ，ｙ）はある範囲でｘとｙが同時に出現する頻度比であり、ｘの頻度をｆ（ｘ）、ｘとｙがある範囲に同時に出現する頻度をｆ（ｘ，ｙ）、全体の母数をＮとすると、
【００１３】
Ｐ（ｘ）＝ｆ（ｘ）／Ｎ
Ｐ（ｘ，ｙ）＝ｆ（ｘ，ｙ）／Ｎ
となる。
【００１４】
いま、ｘとしてある単語、ｙとしてあるクラスタを想定して、文書ごとに頻度を考えると、
【００１５】
Ｐ（ｘ）＝ｆ（ｘ）／Ｎ
Ｐ（ｙ）＝ｎ／Ｎ
Ｐ（ｘ，ｙ）＝ｆ（ｘ，ｙ）／Ｎ
となる。ただし、ｆ（ｘ）はｘが出現する文書数、ｆ（ｘ，ｙ）はｙのうちｘが出現する文書数、Ｎは全文書数、ｎはあるクラスタの文書数である。このとき、相互情報量は、
【００１６】
Ｉ（ｘ，ｙ）＝ｌｏｇ２［Ｎ・ｆ（ｘ，ｙ）／｛ｎ・ｆ（ｘ）｝］
である。
【００１７】
上記の式に、単語出現頻度を考慮し、さらにクラスタ内単語頻度を傾斜させ、ｌｏｇおよび全単語数は各単語重みで共通の値のため省略すると、単語重みＷを次の式で定義できる。
【００１８】
Ｗ（ｘ，ｙ）＝（１＋ｎｔｆ）ｆ（ｘ，ｙ）２／｛ｎ・ｆ（ｘ）｝
ただし、ｎｔｆは単語ｘのクラスタｙ内での出現頻度を、ｙの全出現単語数で正規化した値である。
【００１９】
なお、この発明は装置またはシステムとして実現できるのみでなく、方法としても実現可能である。また、そのような発明の一部をソフトウェアとして構成することができることはもちろんである。またそのようなソフトウェアをコンピュータに実行させるために用いるソフトウェア製品もこの発明の技術的な範囲に含まれることも当然である。
【００２０】
この発明の上述の側面および他の側面は特許請求の範囲に記載され以下実施例を用いて詳述される。
【発明の効果】
【００２１】
この発明によれば、クラスタごとの単語重みを考慮して精度の高いクラスタ解析が期待できる。
【発明を実施するための最良の形態】
【００２２】
以下、この発明の実施例について説明する。
【００２３】
図１は、この発明をパーソナルコンピュータやワークステーション等の計算機で実現した実施例を示しており、この図において、計算機１００にコンピュータプログラム（記録媒体）１０１をインストールしてユーザインタフェース２００および文書クラスタ処理システム３００を構成する。ユーザインタフェース２００は、ユーザからの指示を受取り、文書クラスタ集合の指定やクラスタ条件（クラスタの数等）を文書クラスタ処理システム３００に供給する。文書クラスタ処理システム３００は、指定された文書クラスタ集合を受け取って単語重みを計算し、この単語重みを参照して再度クラスタ解析を行う。文書クラスタ処理システム３００で行われるクラスタ解析の手法は、処理対象の文書クラスタ集合を生成するために用いたものと同じでもよいし、異なるものでもよい。
【００２４】
図２は、図１の文書クラスタ処理システム３００の構成を模式的に示すものであり、この図において、文書クラスタ処理システム３００は、クラスタ集合入力部１０、クラスタ単位単語重み計算部１１、統合単語重み計算部１２、クラスタ解析部１３、クラスタ集合出力部１４等を含んで構成されている。
【００２５】
クラスタ集合入力部１０は、図１のユーザインタフェース２００により指定された文書クラスタ集合を処理対象として入力する。
【００２６】
クラスタ単位重み計算部１１は、クラスタごとに単語重みを計算する。クラスタごとにそのクラスタ内での単語の出現頻度に基づいて単語重みを計算する。具体的な例では、クラスタごとの単語重みは、相互情報量の考え方を単語とクラスタについて応用して求める。一般に、ｘとｙの相互情報量Ｉ（ｘ，ｙ）の式は次である。
【００２７】
Ｉ（ｘ，ｙ）＝ｌｏｇ２［Ｐ（ｘ，ｙ）／｛Ｐ（ｘ）Ｐ（ｙ）｝］
ただし、Ｐ（ｘ）は全体におけるｘの頻度比、Ｐ（ｘ，ｙ）はある範囲でｘとｙが同時に出現する頻度比であり、ｘの頻度をｆ（ｘ）、ｘとｙがある範囲に同時に出現する頻度をｆ（ｘ，ｙ）、全体の母数をＮとすると、
【００２８】
Ｐ（ｘ）＝ｆ（ｘ）／Ｎ
Ｐ（ｘ，ｙ）＝ｆ（ｘ，ｙ）／Ｎ
となる。
【００２９】
いま、ｘとしてある単語、ｙとしてあるクラスタを想定して、文書ごとに頻度を考えると、
【００３０】
Ｐ（ｘ）＝ｆ（ｘ）／Ｎ
Ｐ（ｙ）＝ｎ／Ｎ
Ｐ（ｘ，ｙ）＝ｆ（ｘ，ｙ）／Ｎ
となる。ただし、ｆ（ｘ）はｘが出現する文書数、ｆ（ｘ，ｙ）はｙのうちｘが出現する文書数、Ｎは全文書数、ｎはあるクラスタの文書数である。このとき、相互情報量は、
【００３１】
Ｉ（ｘ，ｙ）＝ｌｏｇ２［Ｎ・ｆ（ｘ，ｙ）／｛ｎ・ｆ（ｘ）｝］
である。
【００３２】
上記の式に、単語出現頻度を考慮し、さらにクラスタ内単語頻度を傾斜させ、ｌｏｇおよび全単語数は各単語重みで共通の値のため省略すると、単語重みＷを次の式で定義できる。
【００３３】
Ｗ（ｘ，ｙ）＝（１＋ｎｔｆ）ｆ（ｘ，ｙ）２／｛ｎ・ｆ（ｘ）｝
ただし、ｎｔｆは単語ｘのクラスタｙ内での出現頻度を、ｙの全出現単語数で正規化した値である。
【００３４】
統合単語重み計算部１２は、クラスタ単位単語重み計算部１１によりクラスタごとに求めた単語重みをクラスタ全体にわたって平均し統合単語重みを計算する。
【００３５】
クラスタ解析部１３は、統合単語重み計算部１２により計算した統合単語重みを参照してクラスタ解析を行う。例えば、単語ベクトル空間における各文書のベクトルをなる各単語ごとの要素を対応する統合単語重みで重み付け、この重み付けした文書のベクトルを用いて文書間の関連度を計算し、この関連度に基づいて文書を、ユーザにより指定されて数のクラスタに分類する。クラスタ解析の手法はこれに限らず任意の手法を採用できる。
【００３６】
クラスタ解析部１３は、クラスタ解析終了条件を吟味し、条件が満たされないときには、文書クラスタ集合をクラスタ単位単語重み計算部１１以降に戻し、同じ処理を繰り返させる。クラスタ解析終了条件が満たされたときには、文書クラスタ集合をクラスタ集合出力部１４に供給し、クラスタ集合出力部１４が文書クラスタ集合を出力する。
【００３７】
クラスタ解析終了条件は例えば図４の例に示すように予め定められた繰り返し回数であったり、あるいは、クラスタ解析の結果により他のクラスタに再配置される文書の数が書定数を下回ることである。エントロピやその他種々の統計情報を用いてもよい。
【００３８】
図３はこの実施例の動作概略を説明するものである。ユーザがユーザインタフェース２００（図１）を用いて対象文書や分類条件を入力し（Ｓ１０、Ｓ１１）、文書クラスタ処理システム３００（図１）が文書クラスタ集合を受取り、受け取った文書クラスタ集合を再解析する（Ｓ１２、Ｓ１３）。
【００３９】
図４は、文書クラスタ処理システム３００の動作の詳細を示しており、この図において、まず、文書クラスタ集合を受け取るとこれに基づいてクラスタごとの単語重みを計算する（Ｓ２０）。この後全文書にわたる単語重み（統合単語重み）を例えば平均処理により計算する（Ｓ２１）。統合単語重みを参照して例えば文書間の関連度を計算しこれに基づいてクラスタ解析を行う（Ｓ２２）。目的回数だけ繰り返しが行われたならば文書クラスタ集合を出力し（Ｓ２３、Ｓ２４）、そうでないのであればステップＳ２０に戻り処理を繰り返す（Ｓ２３）。
【００４０】
この実施例では、大まかの文書クラスタを入力として受取り、クラスタごとの単語重みを考慮して制度の高いクラスタ解析を後処理として行うことができ、人手でクラスタを分け直す手間が省ける。
【００４１】
図５は上述実施例の変形例を示している。この変形例では、初期クラスタ解析部１５を設け、文書クラスタ集合を受け取るのでなく、文書集合を受取り、これを初期クラスタ解析部１５でクラスタ解析し文書クラスタ集合を生成するようにしている。初期クラスタ解析部１５は、種々のクラスタ解析手法を採用できる。図５において図２と対応する箇所に対応する符号を付して詳細な説明を省略する。
【００４２】
なお、この発明は上述の実施例に限定されるものではなくその趣旨を逸脱しない範囲で種々変更が可能である。例えば、上述の実施例では単一の計算機上で文書クラスタ処理システムを構築したが、複数の計算機をネットワークで接続し分散処理により文書クラスタ処理システムを実現するようにしてもよい。また少なくとも一部をハードウェアにより構成できることはもちろんである。
【図面の簡単な説明】
【００４３】
【図１】この発明の実施例の実現環境を説明する図である。
【図２】上述実施例の構成例を説明するブロック図である。
【図３】上述実施例の動作の概要を説明するフローチャートである。
【図４】上述実施例の要部の動作を説明するフローチャートである。
【図５】上述実施例の変形例を説明するブロック図である。
【符号の説明】
【００４４】
１０      クラスタ集合入力部
１１      クラスタ単位単語重み計算部
１２      統合単語重み計算部
１３      クラスタ解析部
１４      クラスタ集合出力部
１５      初期クラスタ解析部
１００      計算機
２００      ユーザインタフェース
３００      文書クラスタ処理システム
【図１】
2005063159.tif 000003
【図２】
2005063159.tif 000004
【図３】
2005063159.tif 000005
【図４】
2005063159.tif 000006
【図５】
2005063159.tif 000007