(57)【要約】【課題】閾値を変更した場合、または期間を変更した場合、適切なクラスタを短期間で提供することができる文書分類装置、文書分類方法、プログラムおよび記録媒体を提供することを目的とする。【解決手段】蓄積されている文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と自文書との距離を、文書間類似度に基づいて算出し、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを蓄積し、蓄積されている最短距離が、閾値よりも短い文書を、１つのクラスタに統合し、統合したクラスタを蓄積し、蓄積されているクラスタを構成する文書のうちで、指定期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成し、上記生成された期間指定クラスタを蓄積する。【選択図】図１
2008234482.tif 000002
【特許請求の範囲】
【請求項１】
文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、文書の本文とを蓄積する文書蓄積部と；
クラスタを生成するための距離の閾値と、開始時刻と、終了時刻とを出力する入力部と；
文書蓄積部に蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離を、文書間類似度に基づいて算出する文書間距離算出部と；
上記自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを蓄積する最短距離文書蓄積部と；
上記最短距離文書蓄積部に蓄積されている最短距離が、上記入力部から受け取った閾値よりも短い文書を、１つのクラスタに統合する統合処理部と；
上記統合処理部が統合したクラスタを蓄積する全クラスタ蓄積部と；
全クラスタ蓄積部に蓄積されているクラスタを構成する文書のうちで、上記入力部から受け取った上記開始時刻から上記終了時刻までの期間である指定期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成する期間指定クラスタ生成部と；
上記期間指定クラスタ生成部が生成した上記期間指定クラスタを蓄積する期間指定クラスタ蓄積部と；
を有することを特徴とする文書分類装置。
【請求項２】
請求項１において、
上記全クラスタ蓄積部から、未処理のクラスタＩＤに対応する文書の集合を取得し、上記指定期間に含まれている文書について、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書である親ノードの時刻情報が上記開始時刻よりも前である文書が複数存在すれば、上記閾値に基づいて、クラスタを分割するかどうかを決定する分割判定処理を実行することを特徴とする文書分類装置。
【請求項３】
請求項２において、
上記閾値と、上記指定期間と、親ノードが開始時刻よりも前である文書が複数あるクラスタのクラスタＩＤと対応付けられている文書と、文書の時刻情報とを入力し、親ノードの時刻情報が上記開始時刻よりも前である文書の集合において、親ノードとの距離が最も短い文書である仮ルートを選択し、
上記仮ルートをルートとするサブツリーの文書の集合において、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積部に蓄積し、
上記仮ルート以外で、親ノードが開始時刻よりも前である文書の集合を選択し、文書集合中に、未処理の文書があれば、未処理の文書を１つ選択し、上記仮ルートとの距離を新たに算出し、この算出した距離が、上記閾値以下であれば、処理中の文書をルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積部に蓄積し、
上記算出した距離が上記閾値よりも大きければ、新しいクラスタＩＤを作成し、処理中の文書ＩＤをルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書に、上記全クラスタ蓄積部に蓄積されていないクラスタＩＤである新しいクラスタＩＤを対応付け、上記期間指定クラスタ蓄積部に蓄積することを特徴とする文書分類装置。
【請求項４】
文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、文書の本文とを、記憶装置に蓄積する文書蓄積段階と；
クラスタを生成するための距離の閾値と、開始時刻と、終了時刻とを入力する入力段階と；
上記文書蓄積段階で蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離を、文書間類似度に基づいて算出し、記憶装置に記憶する文書間距離算出段階と；
上記自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを、記憶装置に蓄積する最短距離文書蓄積段階と；
上記最短距離文書蓄積段階に蓄積されている最短距離が、上記入力段階で受け取った閾値よりも短い文書を、１つのクラスタに統合し、記憶装置に記憶する統合処理段階と；
上記統合処理段階で統合したクラスタを、記憶装置に蓄積する全クラスタ蓄積段階と；
全クラスタ蓄積段階で蓄積されているクラスタを構成する文書のうちで、上記入力段階で受け取った上記開始時刻から上記終了時刻までの期間である指定期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成し、記憶装置に記憶する期間指定クラスタ生成段階と；
上記期間指定クラスタ生成段階で生成された上記期間指定クラスタを、記憶装置に蓄積する期間指定クラスタ蓄積段階と；
を有することを特徴とする文書分類方法。
【請求項５】
請求項４において、
上記全クラスタ蓄積段階で、未処理のクラスタＩＤに対応する文書の集合を取得し、上記指定期間に含まれている文書について、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書である親ノードの時刻情報が上記開始時刻よりも前である文書が複数存在すれば、上記閾値に基づいて、クラスタを分割するかどうかを決定する分割判定処理を実行することを特徴とする文書分類方法。
【請求項６】
請求項５において、
上記閾値と、上記指定期間と、親ノードが開始時刻よりも前である文書が複数あるクラスタのクラスタＩＤと対応付けられている文書と、文書の時刻情報とを入力し、親ノードの時刻情報が上記開始時刻よりも前である文書の集合において、親ノードとの距離が最も短い文書である仮ルートを選択し、
上記仮ルートをルートとするサブツリーの文書の集合において、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積段階で蓄積し、
上記仮ルート以外で、親ノードが開始時刻よりも前である文書の集合を選択し、文書集合中に、未処理の文書があれば、未処理の文書を１つ選択し、上記仮ルートとの距離を新たに算出し、この算出した距離が、上記閾値以下であれば、処理中の文書をルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積段階で蓄積し、
上記算出した距離が上記閾値よりも大きければ、新しいクラスタＩＤを作成し、処理中の文書ＩＤをルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書に、上記全クラスタ蓄積段階で蓄積されていないクラスタＩＤである新しいクラスタＩＤを対応付け、上記期間指定クラスタ蓄積段階で蓄積することを特徴とする文書分類方法。
【請求項７】
請求項１〜請求項３のいずれか１項記載の方法をコンピュータに実行させるプログラム。
【請求項８】
請求項７記載のプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に公開されている文書情報から、人々が記載している話題をテーマ毎にまとめ、クラスタ単位で閲覧可能にする文書分類装置に係り、特に、利用者が所望する期間に合致する文書を対象に、所望の粒度でテーマ毎にまとめたクラスタを提示する文書分類装置に関する。
【背景技術】
【０００２】
近年、インターネット等のコンピュータネットワークの発達に伴い、大量の電子化された情報が発信され続けている。そのために、ある話題に関する情報を取得したいと思った場合、複数の情報源から、公開されているＷｅｂページを１つ１つ閲覧する大変な労力を必要とする。
【０００３】
従来、自然言語処理や情報検索技術分野において、電子化されている文書を、文書内で出現する単語のベクトルで表し、単語のベクトルが類似している文書を、ひとまとめのクラスタにする技術が知られている。
【０００４】
このような従来技術では、単語出現頻度を用いて、文書をベクトル表現し（以下、「文書ベクトル」と呼ぶ）、文書間の類似度は、この文書ベクトル間のコサイン類似度を適用している。すなわち、文書ｄｎを文書ベクトル
【０００５】
【数１】
2008234482.tif 000003
によって表す。なお、ｖは、単語集合Ｗ＝｛ｗ１，ｗ２，…，ｗＶ｝中の単語の総数を示し、ｘｎｉは文書ｄｎにおける単語ｗｉの重みを示す。このときに、文書ｄｊとｄｋとの類似度を、各文書ベクトルがなす角
【０００６】
【数２】
2008234482.tif 000004
で示す。また、単語ｗｉの重みは、単語の文書内での出現頻度、ｔｆ（term frequency）をそのまま利用する場合があり、また、ｔｆに、ｉｄｆ（単語出現数を全文書数で割った値の対数）を乗算したｔｆ・ｉｄｆ（term frequency/inverse document）を利用する場合がある。
【０００７】
そして、類似度に基づいて、クラスタリング処理を行う。クラスタリング手法は、様々存在するが、類似している文書を１つのクラスタとして順次まとめ、閾値を利用して類似していないと判断したときに処理をやめる手法が知られている（たとえば、特許文献１参照）。この手法では、１つの文書を１クラスタとして処理を予め開始し、最も類似しているクラスタ同士を蓄積したテーブルを作成することによって、クラスタリングの処理時間を短縮する。
【０００８】
そこで、たとえば１ヶ月分の文書情報を１週間ずつに区切り、それぞれの期間における話題を見たいと思った場合、文書集合を１週間ずつに分割し、それぞれを入力文書としてクラスタリング処理を実行する。この結果、生成されたクラスタは、期間毎に独立であり、異なる期間におけるクラスタの対応付けが困難である。すなわち、あるクラスタが、時系列で変化した経緯を提示することができないという問題がある。
【０００９】
一方、１ヶ月分の文書情報を全て利用して、クラスタを生成し、この生成されたクラスタのうちで、指定された期間の文書のみを提示する方法も考えられる。この方法では、異なる期間においてクラスタ同士を対応付けることは可能であるが、クラスタ間の類似度を求める際に、本来、利用すべきではない期間外の文書についても、類似度を求めているので、正確さに欠けるという問題がある。
【特許文献１】特許第３６７５６８２号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
つまり、上記従来例では、開始時刻から終了時刻までの期間と、文書間の距離に関する閾値とが与えられた場合、蓄積されている文書の中から、クラスタを短時間で生成することができないという問題がある。
【００１１】
本発明は、蓄積されている文書の全てについて予め木構造を生成し、与えられた文書間の距離に関する閾値によって全期間のクラスタを生成し、開始時刻から終了時刻までの期間が指定された場合、期間に含まれている時刻情報を持つ文書のみを検出し、この検出された文書によって構成される期間指定クラスタを生成する。
【００１２】
また、本発明は、閾値を変更した場合、または期間を変更した場合、適切なクラスタを短期間で提供することができる文書分類装置、文書分類方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、文書の本文とを蓄積する文書蓄積部と、クラスタを生成するための距離の閾値と、開始時刻と、終了時刻とを出力する入力部と、文書蓄積部に蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離を、文書間類似度に基づいて算出する文書間距離算出部と、上記自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを蓄積する最短距離文書蓄積部と、上記最短距離文書蓄積部に蓄積されている最短距離が、上記入力部から受け取った閾値よりも短い文書を、１つのクラスタに統合する統合処理部と、上記統合処理部が統合したクラスタを蓄積する全クラスタ蓄積部と、全クラスタ蓄積部に蓄積されているクラスタを構成する文書のうちで、上記入力部から受け取った上記開始時刻から上記終了時刻までの期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成する期間指定クラスタ生成部と、上記期間指定クラスタ生成部が生成した上記期間指定クラスタを蓄積する期間指定クラスタ蓄積部とを有することを特徴とする文書分類装置である。
【発明の効果】
【００１４】
本発明によれば、蓄積されている文書の全てについて予め木構造を生成し、与えられた文書間の距離に関する閾値によって全期間のクラスタを生成し、開始時刻から終了時刻までの期間が指定された場合、期間に含まれている時刻情報を持つ文書のみを検出し、この検出された文書によって構成される期間指定クラスタを生成するので、上記閾値を変更した場合、または期間を変更した場合に、適切なクラスタを短期間で提供することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１５】
発明を実施するための最良の形態は、以下の実施例である。
【実施例１】
【００１６】
本発明の実施例1は、文書間の類似度に基づいて文書間の距離を求め、文書間の距離が近い文書ほど類似しているとする。すなわち、文書ｄｊとｄｋとの距離を、各文書類似度を用い、１−Ｃｏｓθｊ，ｋで示す。
【００１７】
インターネット上では次々と新しい文書が発信され、更新された時刻情報等を、文書に付与し、蓄積する。実施例１では、このような場合について考える。
【００１８】
図１は、本発明の実施例１の原理を示すフローチャートである。
【００１９】
実施例１では、処理対象である文書間の距離を全て算出するのではなく、自文書の時刻よりも古い時刻が付与されている文書のみを対象として距離を算出する。次いで、全ての文書を時刻順に並べ、自文書と最も距離の近い文書との間を結ぶことによって木構造を形成し、この場合、最も古い文書をルートとして木構造を生成する（Ｓ１）。
【００２０】
図２は、実施例１の原理を説明する図である。
【００２１】
図２において、●印が１つの文書を示し、左から右に向かうほど、時刻の新しい文書が順に並んでいる。自文書よりも古い時刻を持ち、自文書に最も距離の短い文書と自文書とを線で結ぶと、図２（１）に示すように、木構造が生成される。
【００２２】
次に、上記木構造において、文書間の距離が、与えられた閾値以下である文書同士を、同じクラスタにまとめる統合処理を行う（Ｓ２）。
【００２３】
図２（２）に示す例では、距離の閾値に基づいて、クラスタ１とクラスタ２とが生成される。また、全ての文書に、上記統合処理を実施したクラスタについて、指定されている期間（以下、「指定期間」という）に含まれている文書だけを提示する（Ｓ３）。
【００２４】
図２（３）に示す例において、時刻Ｔ１〜Ｔ２の期間が指定されていると、●の文書だけを提示し、○の文書は、期間外になるので提示しない。
【００２５】
このときに、あるクラスタにおける文書が、上記指定期間よりも古ければ、親ノードが期間外である文書が複数存在する場合がある。なお、上記「親ノード」は、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書である。上記の場合、親ノードが期間外である複数の文書間の距離が、閾値以下であれば、同じクラスタとし、閾値よりも大きければ、別のクラスタとして提示する（クラスタを分割する）。
【００２６】
図２（３）に示すように、クラスタ１は、親ノードが期間外になる文書（点線でつながれた文書）が２つ存在し、これらの文書間の距離を算出し、この算出された距離に応じて、クラスタを分離するかどうかを決定する。
【００２７】
図３は、本発明の実施例１における文書分類装置ＤＣ１を示す図である。
【００２８】
文書分類装置ＤＣ１は、文書蓄積部１０と、入力部２０と、クラスタ表示部３０とに接続されている。
【００２９】
文書蓄積部１０は、文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、本文とが記憶装置に蓄積されている。
【００３０】
入力部２０は、クラスタを生成するための閾値と、開始時刻と、終了時刻とを出力する。
【００３１】
クラスタ表示部３０は、文書分類装置ＤＣ１が出力したクラスタ情報（文書の時刻情報、タイトル、本文）を表示する。つまり、クラスタ表示部３０は、図１０（２）に示すように、クラスタの概要を表示する際に、時刻情報、本文から抜粋したテキストを表示する。この場合、タイトルを表示することもある。
【００３２】
文書分類装置ＤＣ１は、文書間距離算出部１１と、最短距離文書蓄積部１２と、統合処理部１３と、全クラスタ蓄積部１４と、期間指定クラスタ生成部１５と、期間指定クラスタ蓄積部１６とを有する。
【００３３】
文書間距離算出部１１は、文書蓄積部１０に蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書との距離を、文書間類似度に基づいて算出する。
【００３４】
上記自文書の時刻情報よりも古い時刻情報を持つ文書と、上記着目文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを記憶装置に蓄積する。文書間距離算出にかかる計算時間は、文書数の二乗オーダである。
【００３５】
図４は、最短距離文書蓄積部１２に蓄積されているデータの例を示す図である。
【００３６】
最短距離文書蓄積部１２は、図４（１）に示すように、各文書の文書ＩＤ４１と、時刻情報４２と、文書間距離算出部１１が算出した最短距離を持つ文書の文書ＩＤ４３と、その最短最短距離４４とが対応付けられ、記憶装置に蓄積する。
【００３７】
図４（２）は、最短距離文書蓄積部１２が蓄積している情報を表す木構造４０を示す図である。
【００３８】
統合処理部１３は、入力部２０から受け取った閾値と最短距離文書蓄積部１２に蓄積されている最短距離４４とを比較する。まず、最新文書からなるクラスタを１つ生成し、最短距離４４と上記閾値と比較し、上記最短距離が上記閾値以下であれば、最短文書を自文書と同一のクラスタに追加する。上記最短距離が上記閾値よりも大きければ、最短文書からなる新しいクラスタを生成する。次に、最短文書４３に記載されている文書を文書４１から探索し、該当する文書の最短距離４４と上記閾値とを比較する。一旦ルート（最も古い文書：図４に示す例では文書ｄ１）に到達した場合、閾値との比較が実施されていない文書集合において、該文書集合の中で最新の文書を選択し、最短距離４４と上記閾値との比較を開始する。
【００３９】
全ての文書について、上記閾値と比較し、生成したクラスタを、全クラスタ蓄積部１４に蓄積する。
【００４０】
全クラスタ蓄積部１４は、統合処理部１３が全ての文書のそれぞれについて生成したクラスタを蓄積する。
【００４１】
実施例１では、最短距離と閾値とを比較する上記処理を、全ての文書について、１度だけ実行すれば足りるので、処理が高速である。
【００４２】
次に、図４に示すデータが、最短距離文書蓄積部１２に蓄積され、上記閾値として０．５が入力された場合の動作について説明する。
【００４３】
まず、クラスタＣ１の要素とし最新の文書ｄ１０を考え、最新の文書ｄ１０に最短距離０．６が対応付けられ、この対応付けられている最短距離０．６と閾値０．５とを比較する。文書ｄ１０の最短距離０．６は、閾値０．５よりも大きいので、新しいクラスタＣ２を作成し、このクラスタＣ２の要素として、図４（１）に示す最短文書ＩＤのｄ９を蓄積する。
【００４４】
続いて、上記最短文書ＩＤのｄ９について、上記と同様に、最短文書ＩＤであるｄ２との最短距離０．５と閾値０．５とを比較し、文書ＩＤｄ９と文書ＩＤｄ２との最短距離０．５が閾値０．５以下であるので、文書ＩＤｄ９が属するクラスタＣ２に、文書ＩＤｄ２を追加する。
【００４５】
図５は、実施例１における全クラスタ蓄積部１４に蓄積されているデータの例を示す図である。
【００４６】
上記のようにして、全ての文書について処理した結果が、図５に示す例である。全クラスタ蓄積部１４は、図５（１）に示すように、クラスタを一意に示すクラスタＩＤ５１と、各クラスタに属する文書集合５２とを対応付けて蓄積している。図５（２）は、図５（１）に示す例を木構造で表示した例であり、各文書は、自文書と最も距離の短い最短文書と実線でつながれている。
【００４７】
期間指定クラスタ生成部１５は、全クラスタ蓄積部１４に蓄積されているクラスタを構成する文書のうちで、上記入力部２０から受け取った上記開始時刻から上記終了時刻までの期間（指定期間）に含まれている時刻情報をもつ文書を、検出し、この検出された文書のみによって構成されているクラスタである期間指定クラスタを生成する。
【００４８】
期間指定クラスタ蓄積部１６は、期間指定クラスタ生成部１５が生成した上記期間指定クラスタを蓄積する。
【００４９】
図６は、実施例１における期間指定クラスタ生成部１５の動作を示すフローチャートである。
【００５０】
まず、全クラスタ蓄積部１４から、全てのクラスタＩＤを取得し、クラスタ毎の処理を順次、行う。未処理のクラスタがあれば（Ｓ１１）、全クラスタ蓄積部１４から、未処理のクラスタＩＤに対応する文書ＩＤの集合を取得する（Ｓ１２）。
【００５１】
次に、上記指定期間内に含まれている文書があるかどうか、最短距離文書蓄積部１２に蓄積されている各文書の時刻情報４２を参照して調べる（Ｓ１３）。上記指定期間内に文書が存在しないクラスタは、以後の処理を実行せずに、Ｓ１１に戻り、次のクラスタの処理を実施する。
【００５２】
未処理のクラスタＩＤに対応する文書ＩＤの集合のうちで、上記指定期間内に含まれている文書があれば（Ｓ１３）、上記指定期間に基づいて、クラスタが分割されるかどうかを調べる（Ｓ１４）。クラスタが分割されなければ（Ｓ１４）、クラスタ内の文書が全て期間内に含まれ、処理しているクラスタＩＤと対応付けられている文書ＩＤとを、そのまま、期間指定クラスタ蓄積部１６に蓄積する（Ｓ１５）。
【００５３】
上記指定期間に基づいて、クラスタが分割される場合（Ｓ１４）、続いて、クラスタ内の各文書において、親ノードが、入力部２０が出力した開始時刻よりも前の時刻情報を持つ文書を選択し、上記選択された文書が複数存在するかどうかを調べる。つまり、図８に示すクラスタＣ２における文書ｄ６、ｄ８、ｄ９のように、複数の文書が存在するかどうかを調べる（Ｓ１６）。
【００５４】
なお、上記「親ノード」は、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書である。つまり、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書を、自文書に対して「親ノード」という。
【００５５】
親ノードの時刻情報が上記開始時刻よりも前の時刻情報を持つ文書が１つしかなければ（Ｓ１６）、クラスタＩＤと対応付けられている文書ＩＤ集合の中で、上記指定期間内に含まれている文書だけを選び、この選ばれた文書を、クラスタＩＤと対応付け、期間指定クラスタ蓄積部１６に蓄積する（Ｓ１７）。
【００５６】
上記親ノードが指定期間外になる文書が複数あれば、分割判定処理（Ｓ１８）を実行し、閾値と比較し、クラスタを分割するかどうかを決定する。
【００５７】
図７は、実施例１における期間指定クラスタ生成部１５の分割判定処理（Ｓ１８）の動作を示すフローチャートである。
【００５８】
分割判定処理（Ｓ１８）には、上記指定されている閾値と、上記指定期間と、開始時刻よりも前の時刻情報を持つ親ノードの子ノードである文書を複数含むクラスタのＩＤと対応付けられている文書と、文書の時刻情報とが入力される。まず、入力されたクラスタＩＤをそのまま引き継ぐ文書ＩＤを決定する。
【００５９】
ここでは、クラスタの中で、上記開始時刻よりも前の時刻情報を持つ文書に最も類似している文書を選択する。そこで、最短距離文書蓄積部１２に蓄積されている文書ＩＤ毎の最短距離４４に基づいて、文書ＩＤ（仮ルート）を選択する（Ｓ２０）。
【００６０】
次に、仮ルートをルートとするサブツリーの文書の集合において、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２１）。そして、仮ルート以外の文書であって、親ノードの時刻情報が開始時刻よりも前である文書の集合を選択し（Ｓ２２）、この文書集合について、以下の処理を実行する。なお、上記「仮ルート」は、自文書が所定の期間内にあり、自文書の親ノードが上記期間外にある文書である。
【００６１】
まず、文書集合中に、未処理の文書があれば（Ｓ２３のＹＥＳ）、未処理の文書を１つ選択し、上記仮ルートとの距離を新たに算出する（Ｓ２４）。距離を算出する場合、文書間距離算出部１１が、文書間の距離を既に算出し、この算出された距離が蓄積され、これを参照するので、文書間距離をその都度算出する場合よりも、処理が高速である。
【００６２】
算出した距離が、指定された閾値以下であれば（Ｓ２５のＹＥＳ）、処理中の文書ＩＤをルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書を、クラスタＩＤと対応付けて、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２６）。
【００６３】
算出した距離が閾値よりも大きければ（Ｓ２５のＮＯ）、新しいクラスタＩＤを作成し（Ｓ２７）、処理中の文書ＩＤをルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書に、新しく作成したクラスタＩＤを対応付け、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２８）。
【００６４】
ここで、上記「新し作成したクラスタＩＤ」は、全クラスタ蓄積部１４に蓄積されているクラスタＩＤ以外のクラスタである。また、新しく作成したクラスタＩＤが、元々、属していたクラスタと対応させるために、処理中のクラスタＩＤを、新しく生成したクラスタＩＤと対応付けて蓄積する（Ｓ２９）。
【００６５】
１つの文書に対する処理が終了すると、Ｓ２３に戻り、未処理の文書が無くなるまで、処理を実行する（Ｓ２３のＮＯ）。
【００６６】
次に、実際のデータを例にして、期間指定クラスタ生成部１５の処理について説明する。
【００６７】
図８は、期間指定クラスタ生成部１５における処理を説明する図である。
【００６８】
図８において、文書間を接続している実線が、木構造であり、この木構造を全クラスタ蓄積部１４が蓄積している。また、図８において、点線は、Ｓ２４で距離を算出する対象である２文書を結ぶ点線である。
【００６９】
図８に示す例では、統合処理部１３の説明で記載したように、閾値を０．５とし、この閾値０．５に基づいて、クラスタＣ１、クラスタＣ２、クラスタＣ３が生成され、存在している。
【００７０】
上記指定期間として、開始時刻＝Ｔ１、終了時刻＝Ｔ２が与えられている場合、まず、全クラスタ蓄積部１４から、３つのクラスタＩＤ：クラスタＣ１、クラスタＣ２、クラスタＣ３を取得する（Ｓ１０）。続いて，各クラスタＩＤに対して、以下の処理を実行する。
【００７１】
未処理のクラスタＩＤとして（Ｓ１１のＹＥＳ）、まず、クラスタＣ１を選択し、クラスタＣ１に対応する文書の集合として、文書ｄ１０を取得する（Ｓ１２）。クラスタＣ１は、文書ＩＤ：ｄ１０のみで構成され、文書ｄ１０は、指定期間に含まれている文書である（Ｓ１３のＹＥＳ）。また、上記指定期間内に、全ての文書ＩＤが含まれているので（Ｓ１４のＮＯ）、文書ｄ１０を、クラスタＣ１と対応付けて、期間指定クラスタ蓄積部１６に蓄積する。
【００７２】
次に、クラスタＣ２を選択し（Ｓ１１のＹＥＳ）、クラスタＣ２に対応する文書の集合｛ｄ１，ｄ２，ｄ５，ｄ６，ｄ７，ｄ８，ｄ９｝を取得する（Ｓ１２）。クラスタＣ２には、上記指定期間に含まれている文書の集合｛ｄ６，ｄ７，ｄ８，ｄ９｝が存在し（Ｓ１３のＹＥＳ）、期間によって、集合｛ｄ１，ｄ２，ｄ５｝と集合｛ｄ６，ｄ７，ｄ８，ｄ９｝とに分割される（Ｓ１４のＹＥＳ）。
【００７３】
そこで、上記指定期間に含まれている文書集合｛ｄ６、ｄ７、ｄ８、ｄ９｝のうちで、親ノードの時刻情報が上記開始時刻Ｔ１よりも前である文書が、複数存在するかどうかを調べると（Ｓ１６）、文書ｄ６の親ノードｄ５、文書ｄ８の親ノードｄ５、文書ｄ９の親ノードｄ２が、図８に示すように、開始時刻Ｔ１よりも前である。３文書ｄ６、ｄ８、ｄ９の親ノードが、指定期間外であるので（Ｓ１６のＹＥＳ）、分割判定処理（Ｓ１８）を実行する。
【００７４】
分割判定処理では、まず、親ノードの時刻情報が、指定されている開始時刻よりも前である文書（子ノード）の集合｛ｄ６，ｄ８，ｄ９｝から、親ノードとの距離が最短である文書（仮ルート）として、文書ｄ６を選択する（Ｓ２０）。これを仮ルートという。つまり、「仮ルート」は、親ノードの時刻情報が、指定されている開始時刻よりも前である文書（子ノード）の集合から、親ノードとの距離が最短である文書である。
【００７５】
次に、仮ルートｄ６をルートとするサブツリーに含まれている文書の集合｛ｄ６、ｄ７｝のうちで、指定期間内に含まれている文書ｄ６とｄ７とを、クラスタＣ２と対応付けて、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２１）。
【００７６】
次に、仮ルートｄ６以外で、親ノードの時刻情報が上記開始時刻Ｔ１よりも前である文書の集合ｄ８，ｄ９を選択し（Ｓ２２）、この集合に属する文書ＩＤ毎に、次の処理を実行する。
【００７７】
まず、文書集合｛ｄ８，ｄ９｝の中に未処理の文書がある場合（Ｓ２３のＹＥＳ）、未処理の文書を選択し、仮ルートｄ６との距離を算出する（Ｓ２４）。まず、文書ｄ８を選択し、仮ルート（ｄ６）との距離を算出する。算出した距離が、たとえば０．２５であれば、指定された閾値０．５以下であるので（Ｓ２５のＹＥＳ）、文書ｄ８をルートとするサブツリーに含まれている文書の集合｛ｄ８｝のうちで、期間内に含まれている文書を選択するが、この例では、文書ｄ８に子ノードが無いので、文書ｄ８のみをクラスタＣ２と対応付け、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２６）。上記「子ノード」は、自文書の時刻情報よりも新しい時刻情報を持ち、しかも自文書から最短距離にある文書である。
【００７８】
次に、未処理の文書：ｄ９の処理を実行する（Ｓ２３のＹＥＳ）。仮ルートｄ６との距離を算出し（Ｓ２４）、算出した距離が、たとえば０．６であれば、指定された閾値０．５よりも大きいので（Ｓ２５のＮＯ）、新しいクラスタＩＤ：クラスタＣ４を作成する（Ｓ２７）。
【００７９】
そして、文書ｄ９をルートとするサブツリーに含まれている文書の集合｛ｄ９，ｄ１０｝のうちで、指定期間に含まれている文書は｛ｄ９｝のみであり、文書ｄ９を、クラスタＣ４と対応付けて、期間指定クラスタ蓄積部１６に蓄積する（Ｓ２８）。蓄積に際して、クラスタＣ４が分割される前には、クラスタＣ２であったことを蓄積するようにしてもよい（Ｓ２９）。文書の集合｛ｄ８，ｄ９｝の処理が終了したので（Ｓ２３のＮＯ）、分割判定処理を終了し、図６のＳ１１に戻る。
【００８０】
Ｓ１１では、クラスタＩＤ：クラスタＣ１、クラスタＣ２について処理が終了した状態であり、未処理のクラスタＣ３を選択する。このクラスタＣ３に対応する文書の集合｛ｄ３，ｄ４｝を取得し、上記指定されている期間に含まれている文書があるかどうかを調べるが、全て開始時刻よりも前の文書であるので（Ｓ１３のＮＯ）、Ｓ１１の処理に戻る。
【００８１】
全てのクラスタＩＤ：クラスタＣ１、クラスタＣ２、クラスタＣ３について、処理が終了したので、期間指定クラスタ生成部１５の処理を終了する。
【００８２】
図９は、処理が終了した時点における期間指定クラスタ蓄積部１６に蓄積されているデータの例を示す図である。
【００８３】
クラスタＩＤ６１に対応して、指定期間に含まれている文書のみの集合である文書の集合６２が、期間指定クラスタ蓄積部１６に蓄積されている。また、分割判定処理において、新しいクラスタＩＤ：クラスタＣ４を作成した際に、分割前クラスタＩＤであるクラスタＣ２を対応付けて蓄積している。
【００８４】
図１０は、期間指定クラスタ蓄積部１６と、文書蓄積部１０とに蓄積されている情報を用いて、クラスタ表示部３０が表示する画面例を示す図である。
【００８５】
図１０（１）に、２つの期間におけるクラスタリング結果が表示されている。期間Ｔ０〜Ｔ１におけるクラスタリング結果は、領域７１に表示され、クラスタＣ２、クラスタＣ３が存在している。期間Ｔ１〜Ｔ２におけるクラスタリング結果は、領域７２に表示され、クラスタＣ１、クラスタＣ２、クラスタＣ４が存在している。各クラスタは、円で表示され、その円の中に、そのクラスタに属する文書のＩＤが表示されている。
【００８６】
この画面において、利用者がクラスタを選択した場合におけるクラスタに属する文書の概要８０を、図１０（２）に示す。
【００８７】
図１０（２）には、期間Ｔ０〜Ｔ１におけるクラスタＣ２が選択された場合の概要が表示されている。各クラスタは、期間内の文書のみを利用したクラスタリング結果である。
【００８８】
互いに異なる期間において、統一されたクラスタＩＤ（同一のクラスタＩＤ）が付与されているので、クラスタＣ２は、２つの期間で同じ数の文書が存在し、話題が継続していることが分かる。また、クラスタＣ２からは、話題が少し変化したクラスタＣ４が派生したことが見て取れる。さらに、クラスタＣ３は、期間Ｔ０〜Ｔ１の間に瞬間的に生じた話題であり、クラスタＣ１は、期間Ｔ１〜Ｔ２の間に新たに発生した話題であることが分かる。
【００８９】
利用者が、閾値や期間を指定する前の段階で、文書間距離算出部１１の処理を実行し、最短距離文書蓄積部１２を作成し、その後に、利用者が、閾値と期間とを指定すると、統合処理部１３による処理と、期間指定クラスタ生成部１５による処理とを実行することによって、指定された期間内の文書のみを用いたクラスタを短時間で、しかも精度よく提供することができる。
【００９０】
また、利用者が期間を変更した場合、期間指定クラスタ生成部１５の処理を実行するだけで、該当期間のクラスタを生成することができる。
【００９１】
上記実施例は、各文書が、作成時刻や更新時刻等の時刻情報とともに保存され、ユーザが指定した任意の期間（指定期間）に属する文書のみについて分類する実施例である。
【００９２】
すなわち、上記実施例は、次の処理によって、クラスタ作成と、期間指定によるクラスタ変更処理を行う。
【００９３】
（１）自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短の文書を、自文書に対する「親ノード」と定義し、その距離が、指定された閾値以下である自文書の集合を、１つのクラスタとする。
【００９４】
（２）全文書を用いて、上記（１）のクラスタ作成処理を１度だけ実行し、各文書とクラスタとの対応関係を、保存手段に保存する。
【００９５】
（３）期間が指定されると、指定期間内の文書のみを、上記（２）で保存した対応関係に基づいて、クラスタ毎に分類する。指定期間外の文書については、処理しない。
【００９６】
（４）同一クラスタに属する指定期間内の文書のうちで、その親ノードの時刻情報が期間外である文書が複数ある場合、これら複数の文書について、最も古い時刻情報を持つ文書と他の文書との２文書間の距離を新たに計算し、閾値以下であれば、その２文書と各子孫ノードとは、全て同一クラスタに属すると判定し、それ以外の場合は、２文書と各子孫ノードとは、異なるクラスタに属すると判定する。
【００９７】
上記実施例によれば、蓄積されている文書の全てについて、木構造を生成し、文書間の距離に関する閾値が与えられた場合、全文書を１回探索するだけで、クラスタを生成することができる。
【００９８】
また、上記実施例によれば、任意の期間が与えられた場合でも、全文書について生成したクラスタ情報を用いて、同一クラスタ内で親ノードの時刻情報が期間外である文書間の距離を計算するだけで、期間内の文書だけを用いた精度のよいクラスタを生成することができる。
【００９９】
さらに、全文書でクラスタを生成するので、連続する異なる期間において、クラスタの対応付けが可能であり、異なる期間でクラスタが大きくなったのか、小さくなったのか、または分割したのかを提示することができる。
【０１００】
なお、上記実施例において、処理対象は文書の本文であるが、タイトルを含めた「タイトル＋本文」を処理対象としてもよい。
【０１０１】
つまり、上記実施例は、文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、文書の本文とを蓄積する文書蓄積部と、クラスタを生成するための距離の閾値と開始時刻と終了時刻とを出力する入力部と、文書蓄積部に蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離を、文書間類似度に基づいて算出する文書間距離算出部と、上記自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを蓄積する最短距離文書蓄積部と、上記最短距離文書蓄積部に蓄積されている最短距離が、上記入力部から受け取った閾値よりも短い文書を、１つのクラスタに統合する統合処理部と、上記統合処理部が統合したクラスタを蓄積する全クラスタ蓄積部と、全クラスタ蓄積部に蓄積されているクラスタを構成する文書のうちで、上記入力部から受け取った上記開始時刻から上記終了時刻までの期間である指定期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成する期間指定クラスタ生成部と、上記期間指定クラスタ生成部が生成した上記期間指定クラスタを蓄積する期間指定クラスタ蓄積部とを有する文書分類装置の例である。
【０１０２】
この場合、上記全クラスタ蓄積部から、未処理のクラスタＩＤに対応する文書の集合を取得し、上記指定期間に含まれている文書について、自文書よりも古い時間情報を持つ文書のうちで、自文書との距離が最短である文書である親ノードの時刻情報が上記開始時刻よりも前である文書が複数存在すれば、上記閾値に基づいて、クラスタを分割するかどうかを決定する分割判定処理を実行する。
【０１０３】
また、上記の場合、上記閾値と、上記指定期間と、親ノードが開始時刻よりも前である文書が複数あるクラスタのクラスタＩＤと対応付けられている文書と、文書の時刻情報とを入力し、親ノードの時刻情報が上記開始時刻よりも前である文書の集合において、親ノードとの距離が最も短い文書である仮ルートを選択し、上記仮ルートをルートとするサブツリーの文書の集合において、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積部に蓄積し、上記仮ルート以外で、親ノードが開始時刻よりも前である文書の集合を選択し、文書集合中に、未処理の文書があれば、未処理の文書を１つ選択し、上記仮ルートとの距離を新たに算出し、この算出した距離が、上記閾値以下であれば、処理中の文書をルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書を、クラスタＩＤと対応付け、上記期間指定クラスタ蓄積部に蓄積し、上記算出した距離が上記閾値よりも大きければ、新しいクラスタＩＤを作成し、処理中の文書ＩＤをルートとするサブツリーの文書の集合の中で、上記指定期間に含まれている文書に、上記全クラスタ蓄積部に蓄積されていないクラスタＩＤである新しいクラスタＩＤを対応付け、上記期間指定クラスタ蓄積部に蓄積する。
【０１０４】
また、上記実施例を方法の発明として把握することができる。つまり、上記実施例は、文書を一意に示す文書ＩＤに対応付けて、時刻情報と、タイトルと、文書の本文とを、記憶装置に蓄積する文書蓄積段階と、クラスタを生成するための距離の閾値と開始時刻と終了時刻とを入力する入力段階と、上記文書蓄積段階で蓄積されている上記文書の本文を用い、自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離を、文書間類似度に基づいて算出し、記憶装置に記憶する文書間距離算出段階と、上記自文書の時刻情報よりも古い時刻情報を持つ文書と上記自文書との距離のうちで、最短距離である文書の文書ＩＤと、上記最短距離とを、記憶装置に蓄積する最短距離文書蓄積段階と、上記最短距離文書蓄積段階に蓄積されている最短距離が、上記入力段階で受け取った閾値よりも短い文書を、１つのクラスタに統合し、記憶装置に記憶する統合処理段階と、上記統合処理段階で統合したクラスタを、記憶装置に蓄積する全クラスタ蓄積段階と、全クラスタ蓄積段階で蓄積されているクラスタを構成する文書のうちで、上記入力段階で受け取った上記開始時刻から上記終了時刻までの期間である指定期間に含まれている時刻情報をもつ文書のみを検出し、この検出された文書によって期間指定クラスタを生成し、記憶装置に記憶する期間指定クラスタ生成段階と、上記期間指定クラスタ生成段階で生成された上記期間指定クラスタを、記憶装置に蓄積する期間指定クラスタ蓄積段階とを有する文書分類方法の例である。
【０１０５】
また、上記実施例をプログラムの発明として把握することができる。つまり、上記実施例は、請求項１〜請求項３のいずれか１項記載の方法をコンピュータに実行させるプログラムの例である。
【０１０６】
さらに、上記プログラムを記録媒体に記録するようにしてもよい。つまり、上記実施例は、請求項７記載のプログラムを記録したコンピュータ読取可能な記録媒体の例である。この場合、上記記録媒体として、ＣＤ、ＤＶＤ、ＨＤ、半導体メモリ等が考えられる。
【図面の簡単な説明】
【０１０７】
【図１】本発明の実施例１の原理を示すフローチャートである。
【図２】実施例１の原理を説明する図である。
【図３】実施例１である文書分類装置ＤＣ１を示す図である。
【図４】最短距離文書蓄積部１２に蓄積されているデータの例を示す図である。
【図５】実施例１における全クラスタ蓄積部１４に蓄積されているデータの例を示す図である。
【図６】実施例１における期間指定クラスタ生成部１５の動作を示すフローチャートである。
【図７】実施例１における期間指定クラスタ生成部１５の分割判定処理（Ｓ１８）の動作を示すフローチャートである。
【図８】期間指定クラスタ生成部１５における処理を説明する図である。
【図９】処理が終了した時点における期間指定クラスタ蓄積部１６に蓄積されているデータの例を示す図である。
【図１０】期間指定クラスタ蓄積部１６に蓄積されている情報を用いて、クラスタ表示部３０が表示する画面例を示す図である。
【符号の説明】
【０１０８】
ＤＣ１…文書分類装置、
１０…文書蓄積部、
１１…文書蓄積部、
１２…最短距離文書蓄積部、
１３…統合処理部、
１４…全クラスタ蓄積部、
１５…期間指定クラスタ生成部、
１６…期間指定クラスタ蓄積部、
２０…入力部、
３０…クラスタ表示部、
４０…木構造。
【図１】
2008234482.tif 000005
【図２】
2008234482.tif 000006
【図３】
2008234482.tif 000007
【図４】
2008234482.tif 000008
【図５】
2008234482.tif 000009
【図６】
2008234482.tif 000010
【図７】
2008234482.tif 000011
【図８】
2008234482.tif 000012
【図９】
2008234482.tif 000013
【図１０】
2008234482.tif 000014