JP2002183171A

JP2002183171A - 文書データ・クラスタリングシステム

Info

Publication number: JP2002183171A
Application number: JP2000377606A
Authority: JP
Inventors: Kai Itou; 快伊藤; Takao Fukushige; 貴雄福重; Takamasa Koyama; 隆正小山
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 2000-12-12
Filing date: 2000-12-12
Publication date: 2002-06-28

Abstract

(57)【要約】【課題】文書データをクラスタリング対象に応じたク
ラスタ数に分類できる文書クラスタリングシステムを提
供する。【解決手段】特徴ベクトル作成手段103が作成した各
文書の特徴ベクトルの組を特異値分解し、特異値分解の
結果106から文書間の類似度を計算するための文書類似
ベクトル108を作成する。クラスタ作成手段110は、対象
文書に対して文書類似ベクトルを用いて、文書とクラス
タ重心との距離を算出し、さらに同一の対象文書に対し
て一回目の分類に利用した文書類似ベクトルの次元数を
増加させて二回目の分類を行い、双方の結果を比較し変
化の少ないクラスタを安定クラスタとする。データ選択
手段109は、安定クラスタの文書を対象から除いてクラ
スタ作成手段の次の分類の対象文書を選定し、この試行
を繰り返す。段階的に分類を繰り返すことにより、クラ
スタ数を事前に決定していなくても、対象に応じたクラ
スタ数を決定できる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文書検索システム
や文書ファイリングシステムなどに利用される文書クラ
スタリングシステムに関し、特に、段階的にクラスタリ
ングを実施する手法を用いて文書を的確に分類すること
を可能にしたものである。

【０００２】

【従来の技術】従来、文書の分類方法では、文書の特徴
を表すものとして、文書の持つキーワードを抽出し、キ
ーワードの内容に基づいて文書を自動分類する方法が知
られている。キーワードは、形態素解析などの文書解析
方法を用いて文書から自動的に抽出され、あるいは、予
め人手によって付与される。例えば、特開平７−１１４
５７２号公報には、文書解析方法により文書から単語を
自動抽出し、各単語にベクトルを対応させた単語の特徴
ベクトルを文書ごとに求め、この特徴ベクトルの類似度
から文書を分類する方法が開示されている。

【０００３】

【発明が解決しようとする課題】しかし、類似度から文
書を分類する場合には、沢山の分類候補が発生するた
め、どの分類候補を選択、採用すべきかの判定基準が不
明確になり、分類が困難になると云う問題点がある。

【０００４】また、分類された結果が何を意味している
のかが分かりにくいという問題点がある。

【０００５】また、人間が日常行っているクラスタリン
グは、例えば、新聞記事を、まず政治関係記事、経済関
係記事、国際関係記事、スポーツ・芸能記事などに大別
し、さらに、経済関係記事を、経済政策記事、株式市場
関係記事、企業動向記事などに細分化する、と云うよう
に、分類の結果が階層的な構造を持つことが多い。これ
は、階層的なクラスタリングの方が、非階層的なクラス
タリングよりも人間にとって自然であり、理解しやすい
ことを意味している。そのため、機械的にクラスタリン
グを行う場合でも、なるべく階層的な構造を持つ分類結
果が得られるようにすることが望ましい。

【０００６】本発明は、こうした課題に応えるものであ
り、文書データをクラスタリング対象に応じたクラスタ
数に的確に分類することができ、また、分類された結果
に対して、その内容を表す表示を対応付けることがで
き、さらに、文書データを階層構造に分類することがで
きる文書クラスタリングシステムを提供することを目的
としている。

【０００７】

【課題を解決するための手段】そこで、本発明では、機
械可読な文書データを格納した文書データベースと、機
械可読な単語を格納した辞書とを備え、前記文書データ
ベースに格納された文書をクラスタリングする文書デー
タ・クラスタリングシステムにおいて、文書中の前記辞
書に格納された単語の出現頻度をもとに文書データベー
スに格納された文書の特徴ベクトルを作成する特徴ベク
トル作成手段と、特徴ベクトル作成手段により作成され
た特徴ベクトルの組を特異値分解する特異値分解手段
と、特異値分解の結果から文書間の類似度を計算するた
めの文書類似ベクトルを作成する文書類似ベクトル作成
手段と、文書類似ベクトル作成手段により作成された文
書類似ベクトルの組により文書データベース中の全てま
たは一部の文書を対象にクラスタを作成するクラスタ作
成手段と、作成されたクラスタの情報を格納するクラス
タ情報テーブルと、クラスタ情報テーブルを参照してク
ラスタ作成手段でのクラスタリングの対象となる文書を
文書データベースから選択するクラスタリングデータ選
択手段とを設け、クラスタ作成手段は、クラスタリング
対象の文書に対して、文書類似ベクトルを用いて、文書
とクラスタ重心との距離を算出し、さらに同一のクラス
タリング対象の文書に対して、一回目のクラスタリング
に利用した文書類似ベクトルの次元数を適度な範囲で増
加させて二回目のクラスタリングを行い、二回のクラス
タリング結果を比較して、変化の少ないクラスタを安定
したクラスタとして判別し、クラスタリングデータ選択
手段は、安定したクラスタに割り当てられた文書をクラ
スタリング対象から取り除いて、クラスタ作成手段が次
に行うクラスタリングの対象を選定し、クラスタ作成手
段とクラスタリングデータ選択手段との間で、この試行
を繰り返すように構成している。

【０００８】また、クラスタ作成手段は、クラスタリン
グ対象の文書に対して、文書類似ベクトルを用いて、文
書とクラスタ重心との距離を算出し、さらに同一のクラ
スタリング対象の文書に対して、一回目のクラスタリン
グに利用した文書類似ベクトルの次元数を適度な範囲で
増加させて二回目のクラスタリングを行い、二回のクラ
スタリング結果を比較して、変化の大きいクラスタを不
安定なクラスタとして判別し、クラスタリングデータ選
択手段は、不安定なクラスタに割り当てられた文書をク
ラスタリング対象から取り除いて、クラスタ作成手段が
次に行うクラスタリングの対象を選定し、クラスタ作成
手段とクラスタリングデータ選択手段との間で、この試
行を繰り返すように構成している。

【０００９】また、文書データベースと、辞書と、特異
値分解結果と、クラスタ情報テーブルとを参照して、ク
ラスタごとのラベルを抽出するラベル抽出手段を設け、
ラベル抽出手段は、クラスタの重心での前記単語の擬似
的な出現頻度を表現した特徴ベクトルを算出し、当該ク
ラスタに割り当てられた文書中から、前記特徴ベクトル
に含まれる出現頻度の大きな単語の周辺に出現する文字
列をラベルとして抽出するように構成している。

【００１０】また、クラスタ作成手段により作成された
クラスタの間の階層関係を設定するクラスタ階層関係決
定手段を設け、クラスタ階層関係決定手段は、任意のク
ラスタＣが安定したクラスタであると判定されたときの
次元数を当該クラスタの安定次元ｄ（Ｃ）として定義す
るとき、クラスタＣの安定次元ｄ（Ｃ）より安定次元が
低いクラスタＣ’に属する全ての文書とクラスタＣの重
心ｇ（Ｃ）とのｄ（Ｃ）次元における距離が一定の距離
Ｒ（Ｃ）以内にある場合に、クラスタＣをクラスタＣ’
の上位クラスタに階層化するように構成している。

【００１１】そのため、本発明の文書データ・クラスタ
リングシステムでは、文書類似ベクトルの次元数を徐々
に増加させて、段階的にクラスタリングを繰り返すこと
により、クラスタ数を事前に決定していなくても、クラ
スタリング対象に応じたクラスタ数を決定することがで
きる。

【００１２】また、ラベル抽出手段が、クラスタの内容
を表す文字列を、そのクラスタに属する文書から抽出す
ることができる。

【００１３】また、クラスタ階層関係決定手段が、段階
的なクラスタリングで生成されたクラスタ間の階層化を
設定し、人間の直感に一致するクラスタ間の階層関係を
生成することができる。

【００１４】

【発明の実施の形態】（第１の実施形態）第１の実施形
態の文書データ・クラスタリングシステムは、図１に示
すように、文書データを格納する文書データベース101
と、単語を格納した機械可読な辞書102と、クラスタリ
ング対象の文書における単語出現頻度から特徴ベクトル
を作成する特徴ベクトル作成手段103と、特徴ベクトル
データを特異値分解する特異値分解手段105と、特徴ベ
クトルの次元を縮小した文書類似ベクトルを作成する文
書類似ベクトル作成手段107と、クラスタリング対象の
文書を選択するクラスタリング対象データ選択手段109
と、文書類似ベクトルを基にしてクラスタリング対象文
書のクラスタを作成するクラスタ作成手段110と、クラ
スタ作成手段110により作成されたクラスタの情報を格
納するクラスタ情報テーブル111と、クラスタリング結
果を表示する結果表示手段112とを備えている。

【００１５】なお、図１において、104は、特徴ベクト
ル作成手段103によって作成されて格納された特徴ベク
トル組、106は、特異値分解手段105によって作成されて
格納された特異値分解結果、また、108は、文書類似ベ
クトル作成手段107によって作成されて格納された文書
類似ベクトル組を表している。

【００１６】次に、以上の構成を有する文書データ・ク
ラスタリングシステムの動作を図２から図１０を用いて
説明する。

【００１７】まず、文書データから文書類似ベクトルを
作成するまでの処理手順について説明する。図３は、こ
の処理手順を表すフローチャートである。

【００１８】ステップ302：特徴ベクトル作成手段103
は、辞書102を参照しながら、文書データベース101中の
文書について、その単語出現頻度の統計的情報により特
徴ベクトル104を作成する。

【００１９】特徴ベクトル作成手段103は、辞書102を参
照し、この辞書102に記載された単語の文書における出
現頻度を求め、各単語の出現頻度を当該文書に対する特
徴ベクトルの要素の値とする。特徴ベクトルの次元数は
辞書中の全単語数に一致し、特徴ベクトル数は文書数に
一致する。当該文書に出現しない単語の頻度は０とな
る。

【００２０】図４は、文書内の単語の出現頻度を基にし
た特徴ベクトルの例である。文書識別子０００１の文書
１には、辞書102に収録された単語１が１３回、単語２
が０回、単語３が４回出現していることを表している。

【００２１】なお、特徴ベクトルの要素は、出現頻度だ
けでなく、図５に示すように、出現頻度を文書長で除算
して正規化した値や、図６に示すように、出現頻度を文
書内での単語の出現頻度の総和で除算して正規化した値
や、また、情報検索の分野で広く用いられている、文書
内出現頻度と全文書中での出現頻度とを考慮したｔｆ・
ｉｄｆ値などを用いることができる。特徴ベクトルの要
素は、出現頻度を基に算出される統計的情報であればど
のような値でも構わない。

【００２２】ステップ303：特異値分解手段105は、ステ
ップ302で得られた特徴ベクトル組について、特異値分
解を行う。

【００２３】特徴ベクトル組を行列Ｘで表現すると、行
数は特徴ベクトル数、列数は特徴ベクトルの次元数、す
なわち辞書103中の単語数となる。行列Ｘを階数ｒ、行
数ｍ、列数ｎとすれば、特異値分解により、３つの行列
Ｄ、Ｓ、Ｔに分解できる（Ｔ’はＴの転置行列を表
す）。Ｘ＝ＤＳＴ’ （式１）ここで、Ｓは、行列Ｘの特異値を対角要素とするｒ×ｒ
の対角行列であり、Ｄはｍ×ｒ、Ｔはｎ×ｒの列直交行
列（ＴＴ’＝ＤＤ’＝Ｉ、Ｉは単位行列）となる。こう
して、特徴ベクトルを特異値分解し、特異値分解結果10
6を得る。

【００２４】特異値分解を行った場合は、行列Ｓから対
角要素の大きい順にｓ個の要素を取り出して低階数近似
を行うことができ、このとき、低階数近似で得た特徴ベ
クトルの次元数は元の特徴ベクトル組の次元数よりも少
なくなる。

【００２５】ステップ305：文書類似ベクトル作成手段1
07は、特異値分解結果106を用いて、文書間の類似度を
算出するための文書類似ベクトル組を作成する。

【００２６】前記特徴ベクトル組104の行列表現Ｘを用
いると、文書間の類似度はＸＸ’という行列で表現でき
る。したがって、文書間の類似度行列は、（式１）で与
えられる特異値分解結果から、ＸＸ’＝ＤＳＴ’ＴＳＤ’＝ＤＳＳＤ’＝（ＤＳ）（ＤＳ）’（式２）と変形できる。行列ＤＳはｍ×ｒの行列であり、行数は
文書数ｍに一致し、列数は行列Ｘの階数ｒに一致する。
この行列ＤＳの行ベクトルを文書類似ベクトルとする。

【００２７】なお、特異値分解で得られる行列Ｓの対角
要素は、主成分分析における主成分に相当するので、次
元数が多いほど、より多くの情報をもつ。

【００２８】次に、このシステムでのクラスタリング処
理の処理手順について説明する。図２は、この処理手順
を表すフローチャートである。

【００２９】ステップ202：クラスタリング対象データ
選択手段109は、文書データベース101の全文書（全要
素）をクラスタリング対象として、クラスタ情報テーブ
ル111に加える。

【００３０】図７はクラスタ情報テーブル111の記述例
を示す。このテーブルのレコード数は文書データベース
101内の文書数であり、少なくとも文書を特定する文書
識別子と、その文書が割り当てられたクラスタの識別子
のフィールドと、その文書がクラスタリング対象である
ことを示すフラグとを有する。図７では、ステップ202
の結果、文書データベース101内の全文書がクラスタ識
別子０のクラスタに割り当てられていること、及び全て
の文書がクラスタリング対象であることを示している。
ここで、クラスタ識別子０は、クラスタリングが一度も
行われていないので、仮想的なクラスタを示している。
なお、クラスタリング対象フラグとして、１はクラスタ
リング対象、０はクラスタリング対象外であることを示
す。

【００３１】ステップ203：クラスタ作成手段110は、パ
ラメタとして、一回のクラスタリングで作成するクラス
タ数ｋと、クラスタ数の増分Δｋと、クラスタ割り当て
時に利用する文書類似ベクトルの次元数ｄ及び次元数の
増分Δｄとを設定する。

【００３２】クラスタ数ｋは、１以上、文書データベー
スの文書数以下であればよい。クラスタ数の増分Δｋ
は、０または、その絶対値が１から文書データベースの
文書数以下であればよい。次元数ｄ及び次元数の増分Δ
ｄは、ステップ303で算出された行列Ｓの階数ｒ以下で
あればよい。

【００３３】ステップ204：クラスタ作成手段110は、ク
ラスタ情報テーブル111を参照して、クラスタリング対
象文書数を調べる。クラスタリングが一度も行われてい
ない状態では、全ての文書がクラスタリング対象となる
ので、クラスタリング対象文書数は文書データベース中
の文書数に一致し、ステップ205へ進む。

【００３４】ステップ205：ステップ305で得られた文書
類似ベクトル組108を用いて、Ｋ平均法と呼ばれる非階
層クラスタリングを行う。

【００３５】Ｋ平均法では、以下のようなアルゴリズム
でクラスタリングを行う。まず、初期値としてｋ個のク
ラスタ重心点を与える。クラスタリング対象の文書（＝
要素）ごとにｋ個のクラスタ重心との距離を計算し、最
も近いクラスタ重心のクラスタにその要素を割り当て
る。全ての要素について割り当てが終わったら、ｋ個の
クラスタごとにその要素から重心を求め、これを新たな
重心点とし、再び各要素のクラスタへの割り当てを行
う。各要素はクラスタの割り当てごとに、別のクラスタ
に割り当てられる可能性があるが、全ての要素につい
て、直前のクラスタと新しく割り当てられるクラスタと
の一致しない数が一定数以下になった場合に割り当ては
終了する。

【００３６】ステップ205では、クラスタ情報テーブル1
11中のクラスタリング対象となっている文書について、
Ｋ平均法によりクラスタリングを行う。ここで、クラス
タ重心と各要素の文書類似ベクトルとの間の距離計算、
及び、重心算出時に、ｒ次元の文書類似ベクトルの第１
次元から第ｄ次元までの要素を用いる。また、このとき
各クラスタ初期重心点と、クラスタに含まれる文書の文
書識別子のリストとを記録しておく。ステップ205の結
果、ｋ個のクラスタが生成される。

【００３７】ステップ206：利用次元数ｄをｒに満たな
い範囲で適度に増加させる。次元数ｄの増分をΔｄとす
れば、ｄ＋Δｄがｄとなる。例えば、ｄが１００、増分
を５０とすれば、新しい利用次元数は１５０になる。ステップ207：ステップ205と同様にＫ平均法によりｋ個
のクラスタを作成する。ここでのクラスタリングでは、
利用する次元数がステップ205の場合よりも大きくなっ
ているので、より多くの情報を用いて、クラスタリング
が行われる。このとき、初期重心は、ステップ205で用
いたものと同じ点を利用する。同じ初期重心を利用する
ことで、ステップ205で得られたクラスタとステップ207
で得られたクラスタとの対応づけが可能になる。このと
きクラスタに含まれる文書の文書識別子のリストを記録
しておく。

【００３８】ステップ208：ステップ205のクラスタリン
グ結果と、クラスタリングに利用する情報を増加させて
クラスタリングしたステップ207の結果とを比較するこ
とにより、それ以上のクラスタリングが不要であるクラ
スタを判別する。情報量を増やしてもクラスタに割り当
てられた文書が変動しないクラスタは、それ以上の情報
を与えてもクラスタリング結果は変わらないと判断でき
る。

【００３９】判別の手順は、まず、ステップ205及びス
テップ207で得られたクラスタごとに、それぞれ割り当
てられている文書の有無を比較し、一致度を調べる。

【００４０】図８は、あるクラスタについて、２回のク
ラスタリングの結果、割り当てられた文書を比較したも
のである。２行目はステップ205、すなわち、次元数ｄ
を用いて作成したクラスタに含まれる文書を、３行目は
ステップ207、すなわち次元数ｄ＋Δｄを用いて作成し
たクラスタに含まれる文書を、それぞれ示している。図
中で０は、その文書がクラスタに含まれていないこと
を、１はクラスタに含まれていることを示す。一致度
は、２回のクラスタリング結果に共通して含まれている
文書数と総文書数との比で与えるなどとすればよい。

【００４１】図８では、１回目のクラスタリングで合計
１００個の文書が、２回目のクラスタリングで合計１１
０個の文書がそれぞれ割り当てられ、共通に含まれてい
る文書数が９５である場合を示している。このとき一致
度は９５／（１００＋１１０）＝０．４５となる。各ク
ラスタについて、適当なしきい値を与え、その一致度が
高いものは安定したクラスタとし、それ以外のクラスタ
は不安定なクラスタとする。

【００４２】また、一致度で不安定なクラスタを判断す
るだけでなく、クラスタに割り当てられた文書数と全文
書数との比などを用いて、不安定なクラスタを判断して
もよい。

【００４３】ステップ208：次に、安定したクラスタに
含まれる文書については、それ以上のクラスタリングは
不要であるので、クラスタ情報テーブル111のクラスタ
リング対象フラグを不要に設定する。不安定なクラスタ
に含まれる文書については、クラスタリング対象フラグ
を変化させないでおき、再クラスタリングの対象とす
る。クラスタ情報テーブル111には、安定したクラスタ
に含まれる文書のクラスタ番号のフィールドに２回目に
割り当てられたクラスタ番号を記録しておく。

【００４４】図９は、更新されたクラスタ情報テーブル
111の例を示している。文書識別子０００１、０００３
は安定したクラスタ１００１に、また、文書識別子００
０４、ｍは安定したクラスタ１００２に割り当てられて
いる。文書識別子０００２，０００５は再クラスタリン
グ対象であるので、クラスタリング対象フラグが０にな
っている。

【００４５】ステップ209：ステップ208の後、作成クラ
スタ数ｋをステップ203で与えたΔｋだけ増加させる。
Δｋが０の場合はクラスタ数は変化しない。

【００４６】続いてステップ204へ移り、再びクラスタ
情報テーブル111を参照してクラスタリング対象文書数
を調べる。

【００４７】ステップ208で、全てのクラスタが安定し
たクラスタであると判断された場合は、クラスタリング
対象の文書は存在しないのでステップ210へ移り、クラ
スタリング処理が終了する。クラスタリング対象文書が
存在した場合は再びステップ205から208までを繰り返
す。ただし、クラスタ割り当て時に利用する文書類似ベ
クトルの次元数はｄ＋Δｄである。

【００４８】図１０は、以上説明したステップ201から
ステップ210までに作成されるクラスタの変化を表す概
念図である。左側には、クラスタ数ｋとステップ207の
クラスタリング時に利用した文書類似ベクトルの次元数
を示す。ｋは７としてある。Δｋは０である。最初のク
ラスタリングでは、３つの安定したクラスタ（図中の四
角）と、４つの不安定なクラスタ（斜線入りの四角）と
が作成されたことを示している。次の段階では、４つの
不安定なクラスタに割り当てられた文書をクラスタリン
グ対象として、クラスタリングを行った結果を表してい
る。

【００４９】このように、クラスタリングを繰り返すこ
とによって、４段階目は不安定なクラスタが無くなり、
クラスタ作成処理が終了したことを示している。

【００５０】以上の説明のように、この実施形態の文書
データ・クラスタリングシステムでは、文書データの特
異値分解を行い、文書間の距離計算に用いる情報を徐々
に増加させ、段階的にクラスタリングを繰り返し行うこ
とにより、クラスタ数を事前に決定していなくても、ク
ラスタリング対象に応じたクラスタ数を決定することが
でき、また、類似している文書だけを集約したクラスタ
が生成できる、という効果がある。

【００５１】（第２の実施形態）第２の実施形態では、
クラスタリングした結果に対して、その内容を表す文字
列をラベリングするシステムについて説明する。

【００５２】このシステムは、図１１に示すように、第
１の実施形態と同様に、文書データを格納する文書デー
タベース1101と、単語を格納した機械可読な辞書1102
と、特徴ベクトルを作成する特徴ベクトル作成手段1103
と、特徴ベクトル組を特異値分解する特異値分解手段11
05と、特異値分解結果を基に文書間の類似度を算出する
ための文書類似ベクトルを算出する文書類似ベクトル作
成手段1107と、結果表示手段1112とを備え、さらに、ク
ラスタを代表するラベルを抽出するラベル抽出手段1110
を備えている。

【００５３】図１１において、1104は特徴ベクトル作成
手段1103によって作成された特徴ベクトル組を、1106は
特異値分解手段1105により得られた特異値分解結果を、
1108は文書類似ベクトル作成手段1107により作成された
文書類似ベクトル組を示している。また、1109は、何ら
かの方法で、文書データベース中の文書を複数のクラス
タのいずれかに割り当て、第１の実施形態と同様の情報
を格納してあるクラスタ情報テーブルを表している。

【００５４】ラベル抽出手段1110は、文書データベース
1101と辞書1102と特異値分解結果1106と文書類似ベクト
ル組1108とクラスタ情報テーブル1109とを参照しなが
ら、クラスタを代表するラベルを抽出する。1111はラベ
ル抽出手段1108により抽出されたラベルを示している。
結果表示手段1112は、クラスタ情報テーブル1109と抽出
ラベル1111とを表示する。

【００５５】以上の構成の文書データ・クラスタリング
システムの動作を図１２から図１４を用いて説明する。

【００５６】図１２は、このシステムの処理手順を表す
フローチャートである。ステップ1202：特徴ベクトル作
成手段1103は、文書データベース1101と辞書1102とを用
いて特徴ベクトル組1104を作成する。この手順は第１の
実施形態（図３）のステップ302と同様である。

【００５７】ステップ1203：次に特異値分解手段1105
は、特徴ベクトル組をもとに、特異値分解を行い特異値
分解結果1106を得る。この手順は第１の実施形態（図
３）のステップ303と同様である。

【００５８】特異値分解の結果、第１の実施形態の（式
１）と同様にして、特徴ベクトル組の行列表現Ｘ（ｍ×
ｎ）は、３つの行列Ｄ（ｍ×ｒ）、Ｓ（ｒ×ｒ）、Ｔ
（ｎ×ｒ）に分解される。ここで、ｍは文書データベー
ス中の文書数、ｎは辞書中の単語数、ｒは行列Ｘの階数
である。

【００５９】ステップ1204：文書類似ベクトル作成手段
1107は、特異値分解結果から文書類似ベクトル1108を作
成する。この手順は第１の実施形態（図３）のステップ
304と同様である。

【００６０】ステップ1205：次に、ラベル抽出手段1110
は、クラスタからのラベル抽出処理に移る。ステップ12
05では、全てのクラスタからラベルを抽出し終えたかど
うかを判断する。全てのクラスタについてラベル抽出を
終えていた場合は、処理は終了する（ステップ1210）。
ラベル抽出手段1106は、ラベル抽出を終えていないクラ
スタについて、クラスタからのラベル抽出処理を行う
（ステップ1206からステップ1209）。

【００６１】ステップ1206：まず、クラスタの重心ベク
トルｇを求める。クラスタの重心ベクトルｇの各要素
は、クラスタに割り当てられた文書に対応する文書類似
ベクトル1108の各要素ごとの平均値とする。クラスタ重
心ベクトルの次元数は文書類似ベクトルの次元数に一致
し、ｒとなる。

【００６２】ステップ1207：次に、クラスタの重心ベク
トルｇ（１×ｒ）と、特異値分解結果1106とを利用し、
（式３）に示す計算方法で代表語ベクトルｈを取得す
る。ｈ＝ｇＳＴ’ （式３）（式３）の右辺は、（式１）における行列Ｄを重心ベク
トルｇに置き換えたものであるので、ｈはクラスタの重
心ベクトルｇに対応する特徴ベクトルを表すことにな
る。したがって、代表語ベクトルｈの各要素は辞書1102
中の単語に対応し、要素の値はクラスタ重心に対する出
現頻度に対応する。

【００６３】図１３は、代表語ベクトルの例を示す。図
中で代表語ベクトルを点線で囲み、各要素に対応する単
語を左側に記述してある。

【００６４】次に、代表語ベクトルの各要素に対応する
単語を辞書1102を参照して取得し、これらを代表語組と
する。各代表語にはそのスコアとして、代表語ベクトル
の対応する要素の値を記録しておく。代表語数は辞書11
02中の単語数に一致するが、スコアの小さなものを代表
語から取り除いてもよい。

【００６５】ステップ1208：続いて、代表語を用いて、
クラスタに割り当てられた文書に出現する代表語の周辺
にある文字列をラベル候補として抽出する。ここでは、
任意の２つの代表語に挟まれた文字列をラベル候補とす
る。

【００６６】なお、代表語の周辺の文字列をラベルとし
て抽出する方法は、例えば代表語の品詞を考慮し、固有
名詞である代表語で始まりサ変動詞である代表語で終わ
る文字列をラベル候補とする、などの方法も考えられ
る。また、ラベル抽出元の文書はクラスタに割り当てら
れた全ての文書でもよいし、幾つかの選択した文書でも
よい。文書の選択方法としては、クラスタの重心ベクト
ルと文書類似ベクトルとの距離を算出し、その距離が近
いものから数文書を選択するなどという方法が考えられ
る。

【００６７】ステップ1209：各ラベル候補について、ス
コアを計算し、スコアの大きなラベル候補をクラスタを
代表するラベルとして抽出する。スコア計算方法は幾つ
か考えられるが、一例として（式４）に示すような計算
方法がある。（ｐ×ｗ１＋（１−ｐ）ｗ２）／Ｌ（式４）ここで、ｐはラベル候補の先頭に位置する代表語のスコ
ア重みを表し、その値は０以上１以下である。ｗ１、ｗ
２はラベル候補の先頭に位置する代表語のスコア、末尾
に位置する代表語のスコアをそれぞれ表す。Ｌはラベル
候補の長さである。

【００６８】図１４は、文書中から、ラベル候補を抽出
し、そのスコアを算出した例を示している。上段の例で
は、「生活」及び「水準」で挟まれた文字列として「生
活水準」が抽出され、そのスコアが、（式４）において
Ｐ＝０．５として算出されている。下段の例では、「専
門」及び「連携」で挟まれた文字列として「専門性を生
かした連携」が抽出され、そのスコアが算出されてい
る。

【００６９】以上の説明のように、この実施形態の文書
データ・クラスタリングシステムでは、クラスタリング
された結果に対して、その内容を代表させた文字列をラ
ベルとして抽出することができ、クラスタを区別し、そ
の内容を推測させるための情報を提供できるという効果
がある。

【００７０】（第３の実施形態）第３の実施形態では、
不安定なクラスタを対象から除いて、再クラスタリング
を繰り返し、類似している文書だけを集約したクラスタ
を生成するシステムについて説明する。

【００７１】第１の実施形態では、再クラスタリングを
実施する場合に、安定しているクラスタを対象から除い
て再クラスタリングを実施しているが、第３の実施形態
のシステムでは、情報量を増やしてクラスタリングした
ときの不一致度が高い不安定なクラスタを対象から除い
て再クラスタリングを行う。

【００７２】このシステムは、図１５に示すように、ク
ラスタリング対象データ選択手段109として、文書デー
タベース101またはクラスタリング結果から、不安定な
クラスタを除き、残ったクラスタをクラスタリング対象
として、その文書データの識別子を選択する主要親クラ
スタリング対象データ選択手段1091を備えている。その
他の構成は、第１の実施形態（図１）と変わりが無い。

【００７３】このシステムの動作を図１６のフローチャ
ートに示している。図１６において、ステップ202から
ステップ207までの手順は、第１の実施形態（図２）の
手順と同様である。

【００７４】ステップ208：ステップ205のクラスタリン
グ結果と、クラスタリングに利用する情報を増加させて
クラスタリングしたステップ207の結果とを比較するこ
とにより、クラスタの対象から外すクラスタを判別す
る。情報量を増やしてもクラスタに割り当てられた文書
が大きく変動するクラスタは、情報をさらに与えること
によりクラスタリング結果は更に大きく変動すると判断
する。

【００７５】判別の手順は、まず、ステップ205及びス
テップ207で得られたクラスタごとに、それぞれ割り当
てられている文書の有無を比較し、一致度を調べる。図
１７はあるクラスタについて、２回のクラスタリングの
結果、割り当てられた文書を比較したものである。２行
目はステップ205、すなわち、次元数ｄを用いて作成し
たクラスタに含まれる文書を、３行目はステップ207、
すなわち次元数ｄ＋Δｄを用いて作成したクラスタに含
まれる文書を、それぞれ示している。図中で０はその文
書がクラスタに含まれていないことを、１はクラスタに
含まれていることを示す。一致度は２回のクラスタリン
グ結果に共通して含まれている文書数と総文書数との比
で与えるなどすればよい。図１７では、１回目のクラス
タリングで合計１００個の文書が、２回目のクラスタリ
ングで合計１１０個の文書がそれぞれ割り当てられ、相
互に共通しない文書数が４０である場合を示している。
このとき、不一致度は４０／（１００＋１１０）＝０．
１８となる。

【００７６】各クラスタについて、適当なしきい値を与
え、その不一致が高いものは不安定なクラスタとして除
外し、それ以外を安定したクラスタとする。なお、不一
致度で不安定なクラスタを判断するだけでなく、クラス
タに割り当てられた文書数と全文書数との比などを用い
て不安定なクラスタを判断してもよい。

【００７７】次に、不安定なクラスタに含まれる文書に
ついては、クラスタ情報テーブル111のクラスタリング
対象フラグを不要に設定する。安定なクラスタに含まれ
る文書については、クラスタリング対象フラグを変化さ
せないでおき、再クラスタリング対象とする。クラスタ
情報テーブル111の、安定したクラスタに含まれる文書
のクラスタ番号のフィールドには２回目に割り当てられ
たクラスタ番号を記録しておく。

【００７８】図１８は、更新されたクラスタ情報テーブ
ル111の例を示している。文書識別子０００１、０００
３は安定したクラスタ１００１に、文書識別子０００
４、ｍは安定したクラスタ１００２に割り当てられ、再
クラスタリング対象であるので、クラスタリング対象フ
ラグが１になっている。文書識別子０００２、０００５
は再クラスタリング対象から除外されるので、クラスタ
リング対象フラグが０になっている。

【００７９】ステップ208以降については、図１と同様
の処理が行われる。こうすることで、安定したクラスタ
を更にクラスタリングすることができる。

【００８０】図１９は、クラスタの変化を表す概念図で
ある。左側には、クラスタ数ｋとステップ207のクラス
タリング時に利用した文書類似ベクトルの次元数を示
す。ｋは７としてある。Δｋは０である。最初のクラス
タリングでは、３つの安定したクラスタ（図中の四角）
と、４つの不安定なクラスタ（斜線入りの四角）とが作
成されたことを示している。次の段階では、３つの安定
なクラスタに割り当てられた文書をクラスタリング対象
として、クラスタリングを行った結果を表している。

【００８１】このように、クラスタリングを繰り返すこ
とによって、類似している文書だけを集約したクラスタ
を生成することができる。

【００８２】以上の説明のように、この実施形態の文書
データ・クラスタリングシステムでは、文書データの特
異値分解を行い、文書間の距離計算に用いる情報を徐々
に増加させ、段階的にクラスタリングを繰り返し行うこ
とにより、クラスタ数を事前に決定していなくても、ク
ラスタリング対象に応じたクラスタ数が決定でき、ま
た、類似している文書だけを集約したクラスタを生成す
ることができる、という効果がある。

【００８３】（第４の実施形態）第４の実施形態では、
文書データを階層的に分類する文書データ・クラスタリ
ングシステムについて説明する。

【００８４】このシステムでの階層化の基本的な考え方
は以下の通りである。第１の実施形態では、クラスタを
作成する過程において、使用する次元数を増やしなが
ら、安定したクラスタを随時除いて行き、残った要素
を、より大きな次元を持つ空間でクラスタリングする、
という段階的なクラスタリングを実現している。

【００８５】このような段階的なクラスタリングでは、
より密集したクラスタが早期に安定し、より広がりをも
ったクラスタが後になって生成され易い、という傾向が
認められる。そのため、より密集したクラスタ、すなわ
ち、より特定のテーマに関連した文書からなるクラスタ
が、早期に生成され、より疎なクラスタ、すなわち、よ
り一般的なテーマの下で纏められる文書からなるクラス
タが、後から生成され易い。

【００８６】この場合、より一般的なテーマに関連した
文書クラスタを、より特定のテーマに関する文書クラス
タの上位クラスタとすることは、人間の行うクラスタ間
の階層化の直感にも一致する。

【００８７】したがって、クラスタリングの過程におい
て、段階的に求められたクラスタ間に自然な階層関係を
導入するには、より後になって安定した（安定次元の高
い）クラスタを、より先に安定して（安定次元の低い）
クラスタよりも階層において上位に位置させることが望
ましい。

【００８８】ただし、上位クラスタは、下位クラスタの
テーマをカバーするというのが自然な直感であるから、
下位クラスタは、上位クラスタの重心から一定の範囲内
に収まっていることが望まれる。

【００８９】これらの要件を満たすべく、各クラスタの
重心と当該クラスタが安定したと判定されたときの次元
とを参照し、先に安定したクラスタＣ’が、後で次元ｄ
（Ｃ）で安定したクラスタＣの重心から一定距離以内に
位置する場合、すなわち、次元ｄ（Ｃ）において、クラ
スタＣの重心からクラスタＣ’までの距離が、クラスタ
Ｃの大きさを示す一定距離の範囲内に収まる場合には、
ＣをＣ’の上位クラスタと位置付けることにより、段階
的に生成されたクラスタ間の階層関係を設定している。

【００９０】ここで、各クラスタの重心や、クラスタの
大きさを表す距離は、文書特徴ベクトル間の計算により
機械的に求めることができる計算可能な量である。

【００９１】以上の考え方に従って、この実施形態の文
書データ・クラスタリングシステムは、クラスタリング
を実行する。

【００９２】このシステムは、図２０に示すように、第
１の実施形態（図１）と同様、文書データベース1901、
辞書1902、特徴ベクトル作成手段1903、特徴ベクトル組
1904、特異値分解手段1905、特異値分解結果1906、文書
類似ベクトル作成手段1907、文書類似ベクトル組1908、
クラスタリング対象データ選択手段1909、クラスタ作成
手段1910、クラスタ情報テーブル1911、及び、結果表示
手段1915を備えるとともに、さらに、クラスタ情報テー
ブル1911に格納されたクラスタの情報と文書類似ベクト
ル組1908とからクラスタ間の階層関係を計算するクラス
タ階層関係決定手段1912と、各クラスタのサイズ情報を
格納するクラスタサイズ情報テーブル1913と、クラスタ
間の階層関係を登録するクラスタ階層関係テーブル1914
とを備えている。

【００９３】ここで、クラスタ作成手段1910は、第１の
実施形態における作用に加えて、安定したクラスタを検
出したときに、その時点での使用次元を当該クラスタの
安定次元としてクラスタサイズ情報テーブル1912に格納
し、また、同時に当該クラスタの重心を同クラスタサイ
ズ情報テーブル1913に格納する。また、結果表示手段19
15は、クラスタリング結果及びクラスタ間階層関係を表
示する。このクラスタ作成手段1910を除く1901から1911
までの内部構成と作用は、第１の実施形態と同一であ
る。

【００９４】図２１は、前記クラスタサイズ情報テーブ
ル1913の例である。このテーブルには、各クラスタごと
に、クラスタ番号、安定次元、重心ベクトル、及び、基
準半径が格納されている。クラスタＣの安定次元とは、
クラスタリングの過程において、クラスタＣが安定して
いるとしてクラスタリング対象から外されるときの次元
数である。以後、この安定次元をｄ（Ｃ）と表す。

【００９５】クラスタＣの基準半径とは、クラスタＣに
属す文書のうち、クラスタＣのクラスタ重心（ｇ（Ｃ）
と表記）から、ｄ（Ｃ）次元での距離において最も遠い
文書とｇ（Ｃ）とのｄ（Ｃ）次元での距離をＲ１（Ｃ）
とし、また、安定次元がｄ（Ｃ）以上のＣ以外のクラス
タに属す文書のうち、ｄ（Ｃ）次元での距離において、
最もｇ（Ｃ）に近くなる文書とｇ（Ｃ）とのｄ（Ｃ）次
元での距離をＲ２（Ｃ）とするとき、Ｒ１（Ｃ）及びＲ
２（Ｃ）の中の小さい方とする。以後、クラスタＣの基
準半径をＲ（Ｃ）と表す。

【００９６】ただし、ここで、ｄ（Ｃ）次元における文
書あるいはクラスタ重心間の距離は、文書類似ベクトル
間のｄ（Ｃ）次元における距離であるとし、文書類似ベ
クトルｘ１＝（ｘ11，ｘ12，‥，ｘ1d(C)，‥，ｘ1r）
と、ｘ２＝（ｘ21，ｘ22，‥，ｘ2d(C)，‥，ｘ2r）と
のｄ（Ｃ）次元における距離ｄｉｓｔ（ｘ１，ｘ２）
は、ｄｉｓｔ（ｘ１，ｘ２）＝{(ｘ11−ｘ21)²＋(ｘ12−ｘ22)²＋‥ ＋(ｘ1d(C)−ｘ2d(C))²}^0.5 （式５）により定義する。

【００９７】図２２は、クラスタ階層関係テーブル1914
の例を示した図である。生成された全クラスタ数をＣma
xとすると、同テーブルは、Ｃmax×Ｃmax次元の行列で
あり、第（ｉ，ｊ）要素には、クラスタ番号ｉのクラス
タが、クラスタ番号ｊのクラスタの上位クラスタである
場合には、１が、それ以外の場合には、０が格納され
る。図２２は、クラスタ２００１が、クラスタ１００１
の上位クラスタであると登録されている状態を示してい
る。初期状態では、すべての要素は０である。

【００９８】以上の構成の文書データ・クラスタリング
システムの動作を図２３から図２５を用いて説明する。
図２３は、クラスタリング処理及びクラスタ間の階層関
係計算手順を表すフローチャートである。

【００９９】ステップ2202：特徴ベクトル作成手段1903
は、文書データベース1901に含まれる文書について特徴
ベクトル1904を作成する。ステップ2203：特異値分解手段1905は、特徴ベクトル組
をもとに、特異値分解を行い特異値分解結果1906を得
る。ステップ2204：文書類似ベクトル作成手段1907は、特異
値分解結果から文書類似ベクトル組1908を作成する。ここまでの手順は、第１の実施形態（図３）のステップ
302〜ステップ305と同じである。

【０１００】ステップ2205：クラスタリング対象データ
選択手段1909、クラスタ作成手段1910は、文書類似ベク
トル組1908及び文書データベース1901を参照しながら、
文書データベース中のすべての文書に対してクラスタリ
ングを行う。この手順は、第１の実施形態（図２）のス
テップ201からステップ210と同様である。ただし、クラ
スタ作成手段1910は、安定したクラスタを認定するたび
に（第１の実施形態のステップ208の時点に相当）、そ
の時点での使用次元数及び当該クラスタの重心ベクトル
をクラスタサイズ情報テーブル1913に登録する。

【０１０１】ステップ2206：次に、クラスタ階層関係決
定手段1912は、クラスタ情報テーブル1911とクラスタサ
イズ情報テーブル1913との内容を参照し、上述の定義に
従って、各クラスタの基準半径を計算し、クラスタサイ
ズ情報テーブル1912に登録する。ステップ2207：クラスタ階層関係決定手段1913は、クラ
スタ情報テーブル1911とクラスタサイズ情報テーブル19
13との内容を参照し、各クラスタ間の階層関係を計算
し、結果をクラスタ階層関係テーブル1914に登録する。

【０１０２】図２４は、このクラスタ間の階層関係を計
算する手順を表すフローチャートである。ステップ2302：まず、クラスタ階層関係テーブル1914の
要素をすべて０（何も階層関係がない状態）に初期化す
る。ステップ2303：次に、クラスタサイズ情報テーブル1913
を参照し、次元ｄの値を、登録されている安定次元の最
小値とする。ステップ2304：次に、クラスタサイズ情報テーブル1913
を参照し、安定次元がｄのクラスタの集合を比較対象集
合として求める。以後、比較対象集合のことをＳ０と表
すことにする。

【０１０３】ステップ2305：次に、次元を、クラスタリ
ングのときに用いたΔｄの値だけ増やし、ステップ2306：クラスタサイズ情報テーブル1913を参照
し、増やした結果の次元が、安定次元の最大値を超えて
いるか調べる。超えていれば、クラスタ間の階層関係の
計算を終了する（ステップ2314）。超えていなければ、ステップ2307：クラスタサイズ情報テーブル1913を参照
し、現在の次元を安定次元とするクラスタの集合を、処
理対象集合として求める。以後、処理対象集合のことを
Ｓ１と表すことにする。

【０１０４】ステップ2308：次に、処理対象集合Ｓ１に
属する各クラスタを全て未処理とした後、ステップ2309：Ｓ１の中に未処理のクラスタが無くなる
まで、ステップ2310：Ｓ１からクラスタを一つ取り出して処理
対象とし、ステップ2311：Ｓ０の各クラスタと、その処理対象のク
ラスタとの包含関係を調べる。この手順については後に
図２５を用いて詳述する。

【０１０５】ステップ2312：処理が済んだ処理対象のク
ラスタを処理済みとし、ステップ2309からの手順を繰り
返す。

【０１０６】Ｓ１のすべてのクラスタについて、Ｓ０の
クラスタとの階層関係の計算が終わったら、ステップ2313：処理対象集合Ｓ１の全クラスタを比較対
象集合Ｓ０に加えて、ステップ2305に戻る。

【０１０７】以上により、各クラスタについて、当該ク
ラスタの安定次元より低い安定次元を持つクラスタ、す
なわち、当該クラスタよりも早い段階で安定したと判定
されたクラスタとの間の階層関係が計算される。

【０１０８】図２５は、下位クラスタの求め方の手順を
表すフローチャートである。この図２５を用いて、ステ
ップ2311における処理対象のクラスタと比較対象集合Ｓ
０の各クラスタとの間の階層関係の計算について説明す
る。ここで、処理対象のクラスタをＣとする。

【０１０９】ステップ2402：比較対象集合のクラスタを
すべて未比較とする。ステップ2403：次に、クラスタサイズ情報テーブル1912
を参照し、処理対象のクラスタＣのクラスタ重心ｇ
（Ｃ）の重心ベクトルとクラスタＣの基準半径Ｒ（Ｃ）
とを得る。

【０１１０】ステップ2404：次に、比較対象集合の中
に、未比較のクラスタがあるか調べる。なければ、階層
関係の計算を終了する(ステップ2409)。未比較のクラス
タがあれば、ステップ2405：そのうちの一つを比較対象とする。比較
対象としたクラスタをＣ’とする。

【０１１１】ステップ2406：次に、比較対象のクラスタ
Ｃ’に属するすべての文書が、処理対象のクラスタＣの
重心ｇ（Ｃ）を中心とする基準半径Ｒ（Ｃ）の範囲に入
っているか調べる。ただし、距離に関しては、（式５）
の定義に従って計算する。

【０１１２】ステップ2407：その結果、すべてが入って
いれば、処理対象のクラスタＣを、比較対象のクラスタ
Ｃ’の上位クラスタとし、ステップ2408：比較対象のクラスタＣ’を比較済みにす
る。また、ステップ2406の検査で、比較対象のクラスタ
Ｃ’に属する文書で、処理対象のクラスタＣの重心ｇ
（Ｃ）から、基準半径Ｒ（Ｃ）内の範囲に入っていない
ものがあった場合は、ステップ2406から直接ステップ24
08に移る。ステップ2408の後はステップ2404に戻り、次
の比較対象があるか調べる。

【０１１３】以上が、処理対象のクラスタと比較対象集
合Ｓ０の各クラスタとの間の階層関係を調べる方法であ
る。

【０１１４】以上の説明のように、第４の実施の形態の
文書データ・クラスタリングシステムでは、文書データ
の特異値分解を行い、文書間の距離計算に用いる情報を
徐々に増加させ、段階的にクラスタリングを行った結果
のクラスタ間に、計算可能な量を用いて、自然な形の階
層関係を導入できる、という効果がある。

【０１１５】なお、上記実施形態では、クラスタＣがク
ラスタＣ’の上位クラスタであると認定された後も、ク
ラスタＣ’の要素をクラスタＣに直接含めることは行わ
なかったが、下位クラスタの要素を上位クラスタに含ま
せるようにしてもよい。

【０１１６】また、下位クラスタの要素を考慮して、上
位クラスタの重心を計算し直すようにしてもよい。

【０１１７】また、上記実施形態では、クラスタ間の階
層関係を調べる際に基準半径という距離を定義して用い
たが、上記定義の基準半径の代わりに、例えば、処理対
象のクラスタの重心から同クラスタに属する各文書まで
の距離の最大値や、最小値、あるは、平均値、９５％の
要素が入るような半径など、ｄ（Ｃ）次元において定義
される各種の距離を用いるようにしてもよい。

【０１１８】

【発明の効果】以上の説明から明らかなように、本発明
の文書データ・クラスタリングシステムでは、文書デー
タの特異値分解を行い、文書間の距離計算に用いる情報
を徐々に増加させ、段階的にクラスタリングを繰り返す
ことにより、クラスタ数を事前に決定していなくても、
クラスタリング対象に応じたクラスタ数が決定でき、ま
た、類似している文書だけを集約したクラスタを生成す
ることができる、という効果がある。

【０１１９】また、ラベル抽出手段を設けたシステムで
は、クラスタリングされた結果に対して、その内容を表
す文字列をラベリングすることができ、クラスタリング
結果を分かり易く示すことができる。

【０１２０】また、段階的なクラスタリングで生成した
クラスタの間を階層化することにより、人間の直感に一
致するクラスタ間の階層関係を生成することができると
いう効果がある。

【図面の簡単な説明】

【図１】第１の実施形態における文書データ・クラスタ
リングシステムの全体構成を表すブロック図、

【図２】第１の実施形態における文書データ・クラスタ
リングシステムのクラスタリング処理手順を表すフロー
チャート、

【図３】第１の実施形態における文書データ・クラスタ
リングシステムの文書データベースから文書類似ベクト
ルを作成するまでの処理手順を表すフローチャート、

【図４】第１の実施形態における文書データ・クラスタ
リングシステムの文書内の単語の出現頻度を基にした特
徴ベクトルの例、

【図５】第１の実施形態における文書データ・クラスタ
リングシステムの出現頻度を文書長で除算し正規化した
値を基にした特徴ベクトルの例、

【図６】第１の実施形態における文書データ・クラスタ
リングシステムの出現頻度を文書内での単語の出現頻度
の総和で除算し正規化した値を基にした特徴ベクトルの
例、

【図７】第１の実施形態における文書データ・クラスタ
リングシステムのクラスタ情報テーブルの記述例、

【図８】第１の実施形態における文書データ・クラスタ
リングシステムのあるクラスタについて、２回のクラス
タリングの結果割り当てられた文書を比較した例、

【図９】第１の実施形態における文書データ・クラスタ
リングシステムの更新されたクラスタ情報テーブルの
例、

【図１０】第１の実施形態における文書データ・クラス
タリングシステムのクラスタの変化を表す概念図、

【図１１】第２の実施形態における文書データ・クラス
タリングシステムの全体構成を表すブロック図、

【図１２】第２の実施形態における文書データ・クラス
タリングシステムの処理手順を表すフローチャート、

【図１３】第２の実施形態における文書データ・クラス
タリングシステムの代表語ベクトルの例、

【図１４】第２の実施形態における文書データ・クラス
タリングシステムの文書中から、ラベル候補を抽出し、
そのスコアを算出した例、

【図１５】第３の実施形態における文書データ・クラス
タリングシステムの全体構成を表すブロック図、

【図１６】第３の実施形態における文書データ・クラス
タリングシステムのクラスタリング処理手順を表すフロ
ーチャート、

【図１７】第３の実施形態における文書データ・クラス
タリングシステムのクラスタについて、２回のクラスタ
リングの結果割り当てられた文書を比較した例、

【図１８】第３の実施形態における文書データ・クラス
タリングシステムの更新されたクラスタ情報テーブルの
例、

【図１９】第３の実施形態における文書データ・クラス
タリングシステムのクラスタの変化を表す概念図、

【図２０】第４の実施形態における文書データ・クラス
タリングシステムの構成を示すブロック図、

【図２１】第４の実施形態におけるクラスタサイズ情報
テーブルの例を示す図、

【図２２】第４の実施形態におけるクラスタ階層関係テ
ーブルの例を示す図、

【図２３】第４の実施形態における文書データ・クラス
タリングシステムの動作手順を示すフローチャート、

【図２４】第４の実施形態におけるクラスタ間の階層関
係計算手順を示すフローチャート、

【図２５】第４の実施形態における下位クラスタ計算手
順を示すフローチャートである。

【符号の説明】

101、1101、1901 文書データベース 102、1102、1902 辞書 103、1103、1903 特徴ベクトル作成手段 104、1104、1904 特徴ベクトル組 105、1105、1905 特異値分解手段 106、1106、1906 特異値分解結果 107、1107、1907 文書類似ベクトル作成手段 108、1108、1908 文書類似ベクトル組 109、1909 クラスタリング対象データ選択手段 110、1910 クラスタ作成手段 111、1109、1911 クラスタ情報テーブル 112、1112、1915 結果表示手段 1091 主要親クラスタリング対象データ選択手段 1110 ラベル抽出手段 1111 抽出ラベル 1912 クラスタ階層関係決定手段 1913 クラスタサイズ情報テーブル 1914 クラスタ階層関係テーブル

───────────────────────────────────────────────────── フロントページの続き (72)発明者小山隆正大阪府門真市大字門真1006番地松下電器産業株式会社内Ｆターム(参考） 5B075 ND03 NK06 NR12 PQ02 PR04 PR06 QM08 UU06

Claims

【特許請求の範囲】

【請求項１】機械可読な文書データを格納した文書デ
ータベースと、機械可読な単語を格納した辞書とを備
え、前記文書データベースに格納された文書をクラスタ
リングする文書データ・クラスタリングシステムにおい
て、文書中の前記辞書に格納された単語の出現頻度をもとに
前記文書データベースに格納された文書の特徴ベクトル
を作成する特徴ベクトル作成手段と、前記特徴ベクトル
作成手段により作成された特徴ベクトルの組を特異値分
解する特異値分解手段と、前記特異値分解の結果から文
書間の類似度を計算するための文書類似ベクトルを作成
する文書類似ベクトル作成手段と、前記文書類似ベクト
ル作成手段により作成された文書類似ベクトルの組によ
り前記文書データベース中の全てまたは一部の文書を対
象にクラスタを作成するクラスタ作成手段と、作成され
たクラスタの情報を格納するクラスタ情報テーブルと、
前記クラスタ情報テーブルを参照して前記クラスタ作成
手段でのクラスタリングの対象となる文書を前記文書デ
ータベースから選択するクラスタリングデータ選択手段
とを具備し、前記クラスタ作成手段は、クラスタリング対象の文書に
対して、前記文書類似ベクトルを用いて、文書とクラス
タ重心との距離を算出し、さらに同一のクラスタリング
対象の文書に対して、一回目のクラスタリングに利用し
た文書類似ベクトルの次元数を適度な範囲で増加させて
二回目のクラスタリングを行い、二回のクラスタリング
結果を比較して、変化の少ないクラスタを安定したクラ
スタとして判別し、前記クラスタリングデータ選択手段
は、前記安定したクラスタに割り当てられた文書をクラ
スタリング対象から取り除いて、前記クラスタ作成手段
が次に行うクラスタリングの対象を選定し、前記クラス
タ作成手段と前記クラスタリングデータ選択手段との間
で、この試行を繰り返すことを特徴とする文書データ・
クラスタリングシステム。
【請求項２】機械可読な文書データを格納した文書デ
ータベースと、機械可読な単語を格納した辞書とを備
え、前記文書データベースに格納された文書をクラスタ
リングする文書データ・クラスタリングシステムにおい
て、文書中の前記辞書に格納された単語の出現頻度をもとに
前記文書データベースに格納された文書の特徴ベクトル
を作成する特徴ベクトル作成手段と、前記特徴ベクトル
作成手段により作成された特徴ベクトルの組を特異値分
解する特異値分解手段と、前記特異値分解の結果から文
書間の類似度を計算するための文書類似ベクトルを作成
する文書類似ベクトル作成手段と、前記文書類似ベクト
ル作成手段により作成された文書類似ベクトルの組によ
り前記文書データベース中の全てまたは一部の文書を対
象にクラスタを作成するクラスタ作成手段と、作成され
たクラスタの情報を格納するクラスタ情報テーブルと、
前記クラスタ情報テーブルを参照して前記クラスタ作成
手段でのクラスタリングの対象となる文書を前記文書デ
ータベースから選択するクラスタリングデータ選択手段
とを具備し、前記クラスタ作成手段は、クラスタリング対象の文書に
対して、前記文書類似ベクトルを用いて、文書とクラス
タ重心との距離を算出し、さらに同一のクラスタリング
対象の文書に対して、一回目のクラスタリングに利用し
た文書類似ベクトルの次元数を適度な範囲で増加させて
二回目のクラスタリングを行い、二回のクラスタリング
結果を比較して、変化の大きいクラスタを不安定なクラ
スタとして判別し、前記クラスタリングデータ選択手段
は、前記不安定なクラスタに割り当てられた文書をクラ
スタリング対象から取り除いて、前記クラスタ作成手段
が次に行うクラスタリングの対象を選定し、前記クラス
タ作成手段と前記クラスタリングデータ選択手段との間
で、この試行を繰り返すことを特徴とする文書データ・
クラスタリングシステム。
【請求項３】前記文書データベースと、前記辞書と、
前記特異値分解結果と、前記クラスタ情報テーブルとを
参照して、クラスタごとのラベルを抽出するラベル抽出
手段を具備し、前記ラベル抽出手段は、クラスタの重心
での前記単語の擬似的な出現頻度を表現した特徴ベクト
ルを算出し、当該クラスタに割り当てられた文書中か
ら、前記特徴ベクトルに含まれる出現頻度の大きな単語
の周辺に出現する文字列をラベルとして抽出することを
特徴とする請求項１または２に記載の文書データ・クラ
スタリングシステム。
【請求項４】前記クラスタ作成手段により作成された
クラスタの間の階層関係を設定するクラスタ階層関係決
定手段を具備し、前記クラスタ階層関係決定手段は、任
意のクラスタＣが安定したクラスタであると判定された
ときの次元数を当該クラスタの安定次元ｄ（Ｃ）として
定義するとき、クラスタＣの安定次元ｄ（Ｃ）より安定
次元が低いクラスタＣ’に属する全ての文書と前記クラ
スタＣの重心ｇ（Ｃ）とのｄ（Ｃ）次元における距離が
一定の距離Ｒ（Ｃ）以内にある場合に、前記クラスタＣ
を前記クラスタＣ’の上位クラスタに階層化することを
特徴とする請求項１に記載の文書データ・クラスタリン
グシステム。
【請求項５】前記クラスタ階層関係決定手段は、クラ
スタＣに属する各文書と前記クラスタＣの重心ｇ（Ｃ）
とのｄ（Ｃ）次元における距離の中で最大の距離をＲ１
（Ｃ）とし、安定次元がｄ（Ｃ）以上のＣ以外のクラス
タに属する各文書と前記クラスタＣの重心ｇ（Ｃ）との
ｄ（Ｃ）次元における距離の中で最小の距離をＲ２
（Ｃ）とするとき、Ｒ１（Ｃ）及びＲ２（Ｃ）の内の小
さい方を、前記Ｒ（Ｃ）とすることを特徴とする請求項
４に記載の文書データ・クラスタリングシステム。