(57)【要約】【課題】クラスタリングのための閾値が変わり、または、文書集合に新たな文書データが追加され、クラスタ分類の結果が変更された場合でも、利用者の意図を、クラスタ分類処理に適切に反映させることができるようにする。【解決手段】文書記録部に記録されている所定の文書に最も近い文書である最接近文書の識別子である最接近文書識別子と、上記所定の文書と、上記最接近文書との距離とを記録して、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を記録し、上記文書間の距離を参照し、予め定められている閾値等に応じて、上記記録されている文書を、複数のクラスタに分割し、クラスタ内の各文書の文書識別子と、上記クラスタ内の文書間距離の最大値と、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に付与される同一のＩＤである組合せＩＤとを記録する。【選択図】図１
2008287493.tif 000002
【特許請求の範囲】
【請求項１】
文書記録部に記録されている所定の文書に最も近い文書である最接近文書の識別子である最接近文書識別子と、上記所定の文書と、上記最接近文書との距離との３つを１組として記録することによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を記録する文書グラフ構造記録手段と；
上記文書グラフ構造記録手段に記録されている文書間の距離を参照し、予め定められている閾値、または、利用者が指定する閾値に応じて、上記文書グラフ構造記録手段に記録されている文書を、複数のクラスタに分割するクラスタリング手段と；
クラスタ内の各文書の文書識別子と、上記クラスタ内の文書間距離の最大値と、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に付与される同一のＩＤである組合せＩＤとを記録するクラスタ組合せ情報記録手段と；
上記クラスタリング手段が生成したクラスタである初期クラスタを記録する初期クラスタ記録手段と；
を有することを特徴とする文書群組合せ装置。
【請求項２】
請求項１において、
上記文書記録部に新たに入力された文書である新規文書と過去に入力済の文書との距離を算出し、上記最近接文書との距離とを、上記文書グラフ構造記録手段に記録させることによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を更新する文書グラフ構造更新手段を有することを特徴とする文書群組合せ装置。
【請求項３】
請求項１において、
上記新規文書の最近接文書が上記クラスタ組合せ情報記録手段に既に記録され、かつ上記新規文書と上記最近接文書との距離が、上記最近接文書と共に記録されている距離以下である場合に、上記新規文書を新規に記録するクラスタ組合せ情報更新手段を有することを特徴とする文書群組合せ装置。
【請求項４】
請求項１において、
クラスタを組合せた結果を、画面上に表示するクラスタ組合せ表示手段を有することを特徴とする文書群組合せ装置。
【請求項５】
請求項１において、
利用者が組合せることを望むクラスタを指定する操作部と、利用者が指定する各クラスタを構成する文書間のリンクについて、上記文書グラフ構造記録手段を参照して距離を獲得し、文書間距離の最大値を算出し、クラスタ内の各文書と、上記最大値と、上記組合せＩＤとを上記クラスタ組合せ情報記録手段に記録させべきかどうかを判断する判断部と、上記クラスタ組合せ情報記録手段に記録させべきであると判断すると、クラスタ内の各文書と、上記最大値と、上記組合せＩＤとを上記クラスタ組合せ情報記録手段に送信し、記録させる制御部とを具備する制御手段を有することを特徴とする文書群組合せ装置。
【請求項６】
文書記録部に新たに入力された文書である新規文書の文書識別子とベクトルとを取得する段階と；
文書グラフ構造記録部に文書が既に蓄積されているか否かを判定する段階と；
新規文書が２番目以降に入力した文書であり、上記文書グラフ構造記録部に文書が既に記録されていれば、上記文書グラフ構造記録部に既に記録されている文書の文書ＩＤを全て取得し、各文書のベクトルを、文書記録部から取得し、各ベクトルを新規文書のベクトルと比較し、文書間の距離を算出し、記憶装置に記憶する段階と；
上記算出した距離に基づいて、新規文書からの距離が最も小さい文書が、最近接文書であると判定し、上記新規文書の文書識別子と、上記最近接文書の識別子である最接近文書識別子と、上記２文書間の距離とを、上記文書グラフ構造記録部とクラスタ組合せ情報更新部とに送出する段階と；
上記文書グラフ構造記録部に文書が蓄積されていないと判断されると、上記新規文書の文書識別子のみを上記文書グラフ構造記録部に記録する段階と；
を有することを特徴とする文書分類方法。
【請求項７】
クラスタ内文書数が２以上であると判断されると、取得した各文書の文書ＩＤに基づいて、文書グラフ構造記録部を参照し、クラスタを構成する各文書間の距離の最大値を取得し、記憶装置に記憶する段階と；
上記クラスタ内の文書の文書識別子が上記クラスタ組合せ情報記録部に記録済であり、上記文書識別子に対応して記録されている距離が、上記最大値よりも小さければ、上記クラスタ内の文書の文書識別子と、上記取得した距離の最大値とを対応付けし、上記クラスタ組合せ情報記録部に記録する段階と；
ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に、同一のＩＤである組合せＩＤ付与し、クラスタ組合せ情報記録部に、各文書と上記最大値と上記組合せＩＤとが存在すれば、記録しようとする距離と、既に記録されている距離とを比較し、記録しようとする距離が、既に記録されている距離よりも大きければ、上記記録しようとする距離を上書きする段階と；
を有することを特徴とする文書分類方法。
【請求項８】
文書グラフ構造更新部から、文書記録部に新たに入力された文書である新規文書の文書識別子と、文書記録部に記録されている所定の文書に最も近い文書である最近接文書の識別子である最近接文書識別子と、上記所定の文書と上記最近接文書との２文書間の距離とを受け取ると、上記最近接文書識別子が、クラスタ組合せ情報記録部に存在するか否かを問い合わせる段階と；
上記最近接文書識別子が、クラスタ組合せ情報記録部に存在すれば、上記文書グラフ構造更新部から受け取った上記２文書間の距離と、クラスタ組合せ情報記録部において上記最近接文書と共に記録されている距離とを比較し、記憶装置に記憶する段階と；
文書グラフ構造更新部から受け取った上記２文書間の距離が、クラスタ組合せ情報記録部において最近接文書と共に記録されている距離以下であれば、新規文書をクラスタ組合せ情報記録部に記録する段階と；
を有することを特徴とする文書分類方法。
【請求項９】
請求項６〜請求項８のうちの少なくとも１つの請求項に記載の方法をコンピュータに実行させるプログラム。
【請求項１０】
請求項６〜請求項８のうちの少なくとも１つの請求項に記載の方法をコンピュータに実行させるプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量の文書データからなる文書集合において、文章データ同士の距離を類似度等に基づいて計算し、閾値処理によって類似文書群（クラスタ）を生成し、文書集合を分類する方法に関する。
【０００２】
また、本発明は、分類されたクラスタについて、利用者が何らかの意図に基づいて、異なるクラスタ同士を組合せし、１つのクラスタにまとめる指示入力をすることができる方法に関する。
【背景技術】
【０００３】
多数の文書閲覧を効率的に行う場合、クラスタリングによって、類似文書を集約し、これによって、文書を整理する。コンテンツのベクトルに応じて、複数のコンテンツをクラスタ分類する場合、従来は、選択しなかったコンテンツを活用して、次のクラスタリング結果を、利用者の意図に近づける技術が知られている（たとえば、特許文献１参照）。
【０００４】
上記従来例では、各コンテンツに、説明のためのキーワードや文書を予め付与し、この付与されているキーワードや文書中に含まれている単語の出現回数を集計し、コンテンツのベクトルを生成する。利用者が選択しなかったコンテンツのベクトルを加算したベクトルを算出し、他のコンテンツのベクトルの各要素を、上記加算したベクトルの各要素の値の大きさに基づいて減少させる。これによって、利用者が選択しなかったコンテンツと関連の深い要素の影響を抑制した新たなベクトルを生成する。このようにして生成した新たなベクトルを用い、クラスタリング処理を行い、利用者の意図に沿った分類を行う。
【０００５】
上記従来例は、主に、映像等のコンテンツに対して付随する文字情報（キーワードや文書）に基づいて、分類するが、映像のみならず、文書そのものを対象にすることもできる。
【特許文献１】特開２００３−２４８６８８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
利用者が選択しなかったコンテンツに基づく上記従来例とは逆のアプローチとして、利用者が選択したコンテンツのベクトルに基づいて、全てのコンテンツのベクトルの各要素を強調すれば、利用者が選択したコンテンツに類するコンテンツを、次回以降の分類時に、より精度よく集めることが可能である。
【０００７】
しかし、クラスタリングでは、利用者の意図を反映しにくいという問題がある。つまり、上記従来例は、あくまでも、利用者の選択結果に基づいて、他のコンテンツのベクトルを間接的に加工し、コンテンツ間の距離を、強制的に縮めたり遠ざけたりするのみであるので、必ずしも、利用者の意図を反映した通りのクラスタリング結果が得られる保証はない。
【０００８】
また、利用者が選択したコンテンツが、互いに類似する場合、加算したベクトルに利用者の意図が表れ易く、次回の分類結果を、利用者の意図に近づけることも可能である。しかし、利用者が選択するコンテンツは、必ずしも意味的に近いものであるとは限らない。このために、計算上は全く類似しないコンテンツを、組合せる相手として利用者が選択した場合、利用者の意図が平均化され、曖昧になり、精度の高い分類を行うことができないという問題がある。
【０００９】
すなわち、特許文献１記載の発明は、非選択結果をフィードバックさせて利用者の意図を反映させる発明であるが、逆に、選択結果をフィードバックさせるようにすれば、今回の課題を解決できそうである。しかし、この考え方は、利用者の選択結果を直接反映させるのではなく、前段階であるベクトル算出時に反映させるので、利用者の意図を忠実に反映させることが難しいという問題がある。
【００１０】
本発明は、クラスタリングのための閾値が変わり、または、文書集合に新たな文書データが追加され、クラスタ分類の結果が変更された場合でも、利用者の意図を、クラスタ分類処理に適切に反映させることができる文書群組合せ装置、文書分類方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、文書記録部に記録されている所定の文書に最も近い文書である最接近文書の識別子である最接近文書識別子と、上記所定の文書と、上記最接近文書との距離との３つを１組として記録することによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を記録する文書グラフ構造記録手段と、上記文書グラフ構造記録手段に記録されている文書間の距離を参照し、予め定められている閾値、または、利用者が指定する閾値に応じて、上記文書グラフ構造記録手段に記録されている文書を、複数のクラスタに分割するクラスタリング手段と、クラスタ内の各文書の文書識別子と、上記クラスタ内の文書間距離の最大値と、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に付与される同一のＩＤである組合せＩＤとを記録するクラスタ組合せ情報記録手段と、上記クラスタリング手段が生成したクラスタである初期クラスタを記録する初期クラスタ記録手段とを有する文書群組合せ装置である。
【発明の効果】
【００１２】
本発明によれば、利用者が明示的に選択した複数のクラスタに属する文書は、以後、異なる閾値でクラスタリング処理を再実行した場合でも、または新規に文書を入力して全体の文書集合が変化した場合でも、同じ組合せＩＤをもつ文書をまとめて表示するので、利用者の意図に合致した文書分類結果を提供することができるという効果を奏する。
【００１３】
本発明によれば、類似度の低い複数のクラスタを利用者が指定した場合に、以後入力した新規文書を、組合せの対象として追加すべきか否かを、利用者が指定した各クラスタについて、クラスタ組合せ情報更新手段が独立して判定するので、概念的に上記複数クラスタの中間的な位置にある曖昧な文書を、組合せの対象として判定することがなく、当初の利用者の意図とは離れたところへ、組合せ対象の文書が拡散することを阻止することができる。つまり、「組合せさせたい」という利用者の明確な意思を尊重した文書分類結果を提供することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１４】
発明を実施するための最良の形態は、次の実施例である。
【実施例１】
【００１５】
実施例１は、全ての異なる文書間に距離付きのリンクが張られた文書グラフ構造ではなく、新規文書に対して、過去に入力した文書のうちで最も距離が近い文書（最近接文書）との間にのみ、距離付きのリンクを持った文書グラフ構造を生成する実施例である。
【００１６】
図１は、本発明の実施例１である文書群組合せ装置１００を示すブロック図である。
【００１７】
文書群組合せ装置１００は、文書記録部１と、文書グラフ構造記録部２と、文書グラフ構造更新部３と、クラスタリング部４と、クラスタ組合せ情報記録部５と、クラスタ組合せ情報更新部６と、初期クラスタ記録部７と、クラスタ組合せ表示部８と、制御部９とを有する。
【００１８】
文書記録部１は、入力した文書を蓄積する記録部であり、文書をベクトルで表現し、異なる文書間の距離を、文書間の類似性に基づいて、数値化して蓄積する。また、各文書を識別可能な一意の文書ＩＤを文書に付与する。文書データを空間モデルで表現する場合、文書から単語、形態素、または固定長の文字列等の文字列を多数取得し、各文字列の文書中での出現回数、各文字列を含む文書の数等の統計情報から、各文字列の重みを数値化することによって、文書をベクトルとして表現する。
【００１９】
文書グラフ構造記録部２は、文書記録部に記録されている所定の文書に最も近い文書である最接近文書のＩＤである最接近文書ＩＤと、上記所定の文書と、上記最接近文書との距離との３つを１組として記録することによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を記録する。
【００２０】
文書グラフ構造更新部３は、過去に入力済みの文書のそれぞれと新規文書との距離を算出し、最近接文書との距離とを、文書グラフ構造記録部２に記録させることによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を更新する。
【００２１】
クラスタリング部４は、文書グラフ構造記録部２に記録されている文書間の距離を参照し、予め定められている閾値、または、利用者が指定する閾値に応じて、文書グラフ構造記録部２に記録されている文書を、複数のクラスタに分割する。
【００２２】
クラスタ組合せ情報記録部５は、クラスタ内の各文書と、上記クラスタ内の文書間距離の最大値と、組合せＩＤとを記録する記録装置である。なお、上記「組合せＩＤ」は、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に付与される同一のＩＤである。
【００２３】
クラスタ組合せ情報更新部６は、新規文書の最近接文書が既にクラスタ組合せ情報記録部５に記録され、かつ上記新規文書と上記最近接文書との距離が、上記最近接文書と共に記録されている距離以下である場合に、上記新規文書をクラスタ組合せ情報記録部５に新規に記録する。また、新たに記録する新規文書と共に記録する距離、および組合せＩＤには、上記最近接文書と共に記録されている各値を複写する。
【００２４】
初期クラスタ記録部７は、クラスタリング部４が生成したクラスタである初期クラスタを記録する。
【００２５】
クラスタ組合せ表示部８は、初期クラスタ記録部７を参照し、どの文書が含まれているクラスタ同士を組合せるべきか、または、どのクラスタも組合せる必要がないかを、クラスタ組合せ情報記録部５を参照して、クラスタ組合せ表示部８が決定し、必要に応じてクラスタを組合せた結果を、画面上に表示する。
【００２６】
さらに、表示結果を閲覧した利用者が複数のクラスタを指定した場合に、各クラスタを構成する組合せ前のクラスタ（組合せによって生成されたクラスタではない場合は、指定したクラスタ自体）のクラスタＩＤが、制御部９に送出される。
【００２７】
制御部９は、利用者が組合せることを望むクラスタを指定する操作手段を有する。また、制御部９は、利用者が指定する各クラスタを構成する文書間のリンクについて、文書グラフ構造記録部２を参照して距離を獲得し、文書間距離の最大値を算出し、クラスタ内の各文書と、上記最大値と、組合せＩＤとをクラスタ組合せ情報記録部５に記録させべきかどうかを判断する判断手段を具備する。そして、制御部９は、クラスタ組合せ情報記録部５に記録させるべきであると判断すると、クラスタ内の各文書と、上記最大値と、組合せＩＤとをクラスタ組合せ情報記録部５に送信し、記録させる制御手段を有する。
【００２８】
上記組合せＩＤは、利用者が一度に指定した複数クラスタに対して共通に与える識別子である。このときに、記録する対象となった文書ＩＤが、クラスタ組合せ情報記録部５に既に記録されている場合は、既に記録されている距離と、記録しようとする上記最大値とを比較し、既に記録されている距離が上記最大値以下である場合にのみ、上記文書ＩＤに対応する距離を上記最大値で置き換えて、クラスタ組合せ情報記録部５のデータを修正する。
【００２９】
単語に基づくベクトル空間モデルの場合、文書を「総理大臣＝０．２」「政党＝０．４」「午前＝０．１」等のような、単語と数値との組合せを列挙したベクトルで表現する。
【００３０】
文書から、文字列を取得する方法、重みを算出する方法としては、既存の方法を用いればよく、またベクトル空間モデルとは異なる方法で、類似性に基づく文書間の距離を決定するようにしてもよい。
【００３１】
次に、文書グラフ構造更新部３が、文書グラフ構造記録部２に記録した情報を更新する動作について説明する。
【００３２】
図２は、文書グラフ構造更新部３が、文書グラフ構造記録部２に記録されている情報を更新する動作を示すフローチャートである。
【００３３】
つまり、Ｓ１で、文書記録部１に新規に入力した１文書（新規文書）の文書ＩＤとベクトルとを取得する。Ｓ２で、文書グラフ構造記録部２に１以上の文書が既に蓄積されているか否かを判定する。新規文書が２番目以降に入力した文書であり、文書グラフ構造記録部２に１以上の文書が既に記録されていれば、Ｓ３の処理に進む。上記新規文書が最初の文書であれば、文書グラフ構造記録部２に記録されている文書は存在しないので（Ｓ２のＮＯ）、Ｓ５の処理に進む。
【００３４】
Ｓ３で、文書グラフ構造記録部２に既に記録されている文書の文書ＩＤを全て取得し、各文書のベクトルを、文書記録部１から取得し、各ベクトルを新規文書のベクトルと比較し、文書間の距離を算出する。
【００３５】
Ｓ４では、Ｓ３で算出した距離に基づいて、新規文書からの距離が最も小さい文書が、最近接文書であると判定し、上記新規文書の文書ＩＤと、上記最近接文書ＩＤと、上記２文書間の距離とを、文書グラフ構造記録部２とクラスタ組合せ情報更新部６とに送出し、処理を終える。
【００３６】
一方、Ｓ５では、Ｓ２で文書グラフ構造記録部２に文書が蓄積されていないと判断されると、新規文書の文書ＩＤのみを文書グラフ構造記録部２に記録し、処理を終わる。
【００３７】
図３は、文書グラフ構造記録部２に記録されているデータの例を示す図である。
【００３８】
文書記録部１に、文書ｄ１、ｄ２、ｄ３、ｄ４、ｄ５、ｄ６、…の順に文書を入力したとすると、文書ｄ１は、最初の文書であるので、最近接文書の欄に、記載がない。文書ｄ２を入力した時点では、文書ｄ１のみの文書が存在するので、必然的に、最近接文書が、文書ｄ１である。以後、上記と同様に、新規文書のＩＤと、その最近接文書ＩＤと、上記最近接文書との距離とが、文書記録部１に蓄積される。クラスタ組合せ情報記録部５に何も記録されていなければ、更新する必要がないので、最近接文書の文書ＩＤと最近接文書との距離とを追加しない。クラスタ組合せ情報更新部６が行う処理については、以下で詳細に説明する。
【００３９】
図４は、文書グラフ構造記録部２に記録されているデータを、図式化した文書グラフ構造を示す図である。
【００４０】
○印は、文書を示し、○印の内部の記号は、それぞれ文書ＩＤを示す。文書ｄ２からｄ１に向かう矢印は、文書ｄ２の最近接文書が文書ｄ１であることを示し、上記矢印の横に添えられている数値は、文書ｄ１とｄ２との距離を示す。
【００４１】
クラスタリング部４に対して、たとえば閾値０．４が与えられると、図４において、距離が０．４以下である文書同士が接続される。
【００４２】
図５は、閾値を０．４として生成したクラスタの例を示す図である。
【００４３】
この結果、距離が０．１である文書ｄ４とｄ３とが接続され、距離が０．３である文書ｄ６とｄ２とが接続され、図５に示すように、文書ｄ１のみからなるクラスタＣ１と、文書ｄ２とｄ６とからなるクラスタＣ２と、文書ｄ３とｄ４とからなるクラスタＣ３と、文書ｄ５のみからなるクラスタＣ４との、合計４クラスタが生成される。
【００４４】
図６は、初期クラスタ記録部７に記録されているデータの一覧の例を示す図である。
【００４５】
クラスタリング部４は、生成したクラスタを識別するために、上記のようにクラスタＩＤであるＣ１〜Ｃ４を、一意に付与し、各クラスタのクラスタＩＤと各クラスタに含まれている文書の文書ＩＤとの一覧（図６に示す一覧）を、初期クラスタ記録部７に記録させる。
【００４６】
クラスタ組合せ情報記録部５に何も記録されていない初期状態である場合、クラスタ組合せ表示部８は、初期クラスタ記録部７から取得したクラスタリングの結果をそのまま表示する。
【００４７】
図７は、クラスタ組合せ表示部８による画面の表示例を示す図である。
【００４８】
図７に示す画面上には、クラスタＩＤと、各クラスタに属する文書の文書ＩＤと、クラスタに属する文書の概要とが表示されている。クラスタに属する文書の概要を表示する場合、各文書の本文の一部を、文書記録部１か図示しない記録部等から取得し、文書ＩＤと並べて表示する。その他、文書のタイトル、作成時刻、作者等、付随する情報を取得可能であれば、別途、これらを取得し、表示するようにしてもよい。
【００４９】
図７に示す画面を閲覧した利用者が、２以上のクラスタを指定すると、クラスタ組合せ表示部８は、各クラスタを組合せる前のクラスタである初期クラスタのクラスタＩＤ一覧を、制御部９に送出する。利用者が指定したクラスタが、組合せによって生成されたクラスタではなければ、初期クラスタそのもののクラスタＩＤを、制御部９に送出する。
【００５０】
図８は、制御部９が行う処理を示すフローチャートである。
【００５１】
図７を閲覧した利用者が、クラスタＣ１に含まれている文書とクラスタＣ３に含まれている文書とが、ともに「○○会議」を扱う文書であったとすると、「○○会議」についてクラスタＣ１とＣ３とが共通するので、利用者がクラスタＣ１とＣ３とを組合せたいと考え、制御部９を介して、クラスタＣ１とＣ３とを利用者が指定したとする。
【００５２】
Ｓ１１で、一意な組合せＩＤを発行する。上記「組合せＩＤ」は、利用者が複数のクラスタを指定する度に付与される一意のＩＤであり、クラスタＣ１とＣ３とを指定すると、たとえば「組合せ１」の組合せＩＤを、クラスタＣ１に含まれている全ての文書とクラスタＣ３に含まれている全ての文書とに付与する。引き続いて、たとえばクラスタＣ５とＣ６とＣ７とを指定したとすると、「組合せ１」とは異なるＩＤ、たとえば「組合せ２」の組合せＩＤを、クラスタＣ５に含まれている全ての文書とクラスタＣ６に含まれている全ての文書とクラスタＣ７に含まれている全ての文書とに付与する。
【００５３】
制御部９は、Ｓ１２で、クラスタＣ１とＣ３とのうちの一方のクラスタであるクラスタＣ１に含まれている文書ＩＤ一覧「ｄ１」を、初期クラスタ記録部７から取得する。
【００５４】
Ｓ１３で、クラスタ内文書数が２以上であると判断されると、Ｓ１４で、既に取得した各文書の文書ＩＤに基づいて、文書グラフ構造記録部２を参照し、クラスタを構成する各文書間の距離の最大値を取得する。
【００５５】
ただし、１文書のみからなるクラスタを指定した場合、クラスタを構成する文書間の距離を定義できないので、Ｓ１５で、クラスタリング部４に与えられている閾値（本例では、０．４）が、文書間距離の最大値であるとみなす。したがって、文書ｄ１における距離の最大値は、０．４であるとみなされる。一方、クラスタＣ３の場合、図３によれば、クラスタＣ３を構成する文書が文書ｄ３とｄ４との２文書であり、また、文書ｄ３とｄ４との距離が０．１であるので、距離の最大値は０．１である。３文書以上が存在するクラスタの場合、上記と同様に、文書グラフ構造記録部２を参照し、クラスタを構成する文書間の距離の最大値を取得する。
【００５６】
文書ＩＤが記録済であり（Ｓ１６）、記録済文書ＩＤに対応する距離が、最大値よりも小さければ（Ｓ１７）、Ｓ１８では、Ｓ１２で取得した各文書ＩＤと、Ｓ１３で取得した距離の最大値とを対応付ける。さらに、利用者がクラスタを指定する度に、新たな組合せＩＤを付与し、クラスタ組合せ情報記録部５に、クラスタ内の各文書と上記クラスタ内の文書間距離の最大値と組合せＩＤとが存在していれば、記録しようとする距離と、既に記録されている距離とを比較し、記録しようとする距離が、既に記録されている距離よりも大きい場合には、Ｓ１９で、上書きする。しかし、記録しようとする距離が、既に記録されている距離以下である場合、距離を置き換えず、Ｓ１９で、組合せＩＤのみを更新する。つまり、一旦クラスタ組合せ情報記録部５に記録した文書の距離を、より小さな値の距離で置き換えることはない。
【００５７】
Ｓ２０では、利用者が指定したクラスタを構成する元のクラスタ（初期クラスタ）のそれぞれについて、上記Ｓ１１〜Ｓ１９の処理を終えたかどうかを判定し、全クラスタについての処理が終わるまで繰り返す。
【００５８】
図９は、クラスタ組合せ情報記録部５に記録されているデータ例を示す図である。
【００５９】
利用者が指定したクラスタＣ１、Ｃ３に含まれている文書ｄ１、ｄ３、ｄ４のそれぞれに、「組合せ１」という組合せＩＤが付与され、クラスタＣ１に含まれている文書ｄ１には、距離０．４が記録され、Ｃ３に含まれる文書ｄ３、ｄ４には、距離０．１が記録される。
【００６０】
クラスタ組合せ表示部８が行う処理について、クラスタ組合せ情報記録部５内に何も記録されない初期状態における動作のみを説明した。
【００６１】
次に、図９に示すような情報が記録された状態において行う処理について説明する。
【００６２】
クラスタ組合せ表示部８は、初期クラスタ記録部７に記録されているクラスタのうちで、クラスタ組合せ情報記録部５内において同じ組合せＩＤを持つ文書を含むクラスタを全て組合せる。たとえば、「組合せ１」という組合せＩＤを持つ文書ｄ１、ｄ３、ｄ４を含むクラスタを、常に組合せる。つまり、クラスタリング部４が生成したクラスタリング結果によらずに、組合せる。画面上には、クラスタ組合せ表示部８が組合せたクラスタを表示するので、利用者が指定した複数のクラスタに含まれている全ての文書が、全て１クラスタとして表示される。
【００６３】
次に、クラスタ組合せ情報記録部５にデータが存在する場合、表示結果を閲覧した利用者が、複数のクラスタを指定した際に、制御部９が行う処理の流れを、再度、図８を用いて説明する。ここでは、前例とは異なる閾値０．５が指定された場合について説明する。
【００６４】
図１０は、閾値を０．５として生成したクラスタの例を示す図である。
【００６５】
閾値が０．５である場合、図１０に示すように、文書ｄ１、ｄ３、ｄ４からなるクラスタＣ１１と、文書ｄ２、ｄ６からなるクラスタＣ１２と、文書ｄ５のみからなるクラスタＣ１３との合計３クラスタが生成される。クラスタ組合せ情報記録部５に記録されている文書ｄ１、ｄ３、ｄ４は、既に、１個のクラスタに属しているので、組合せ処理を行っても結果は変わらない。
【００６６】
この状況で、Ｃ１１とＣ１２とを組合せるように、ユーザが指定したとする。上記例と同様に、組合せによって生成されたクラスタを指定した場合、組合せ前のクラスタである初期クラスタのそれぞれについて、Ｓ１１〜Ｓ１９の処理を実行する。
【００６７】
まず、第１のクラスタＣ１１について、Ｓ１１〜Ｓ１９の処理を実行する。Ｓ１２で、クラスタＣ１１に属する文書ＩＤの一覧ｄ１、ｄ３、ｄ４を取得し、Ｓ１３で、これらの文書間の距離の最大値である０．５を取得する。Ｓ１８で、文書ｄ１、ｄ３、ｄ４のそれぞれを、既に取得した距離０．５と、新たに付与する組合せＩＤ「組合せ２」とを、クラスタ組合せ情報記録部５に記録する。
【００６８】
このときに、文書ｄ１、ｄ３、ｄ４は、いずれもクラスタ組合せ情報記録部５に存在しているので、距離を比較し、距離を更新するか否かを判定する。文書ｄ１、ｄ３、ｄ４の各文書に対して、クラスタ組合せ情報記録部５は、それぞれ０．４、０．１、０．１という距離が記録されているが、既に取得した距離０．５は、既に記録されているいずれの距離よりも大きいので、全ての距離が上書きの対象になる。つまり、クラスタ組合せ情報記録部５において、文書ｄ１、ｄ３、ｄ４のそれぞれに付与されている組合せＩＤが、いずれも「組合せ２」に更新され、距離が０．５に更新される。
【００６９】
距離が大きい場合にのみ、上書きするのは、利用者の意図を正確に反映させるためである。つまり、クラスタ内の距離の最大値は、上記クラスタを形成するために必要な距離の最小値であり、クラスタ内の距離の最大値よりも小さな閾値が与えられると、上記クラスタが形成されない。あるクラスタを指定した後に、上記クラスタを内包するクラスタ、つまり、より大きな距離の最大値を持つクラスタを１度でも指定すると、より概念の広いクラスタに対して、他との組合せを、利用者が許容したことを意味する。したがって、距離が大きい場合にのみ、距離を更新する。
【００７０】
続いて、２番目のクラスタＣ１２では、属する文書である文書ｄ２とｄ６との距離の最大値は０．３であり、この距離の最大値０．３が、組合せＩＤ「組合せ２」と共に記録される。
【００７１】
図１１は、クラスタＣ１１とＣ１２とを組合せる指示を、利用者が入力した場合、クラスタ組合せ情報記録部５に記録されているデータの変化後の例を示す図である。
【００７２】
以上によって、クラスタ組合せ情報記録部５に記録されているデータは、図１１に示すように変化する。
【００７３】
上記のように、クラスタ組合せ情報記録部５は、利用者が複数のクラスタを指定する度に、距離を判定した上で、更新処理が行われる。
【００７４】
最後に、クラスタ組合せ情報更新部６が行う処理について説明する。
【００７５】
図１２は、実施例１において、新規文書が入力される度に、クラスタ組合せ情報更新部６が行う処理を示すフローチャートである。
【００７６】
文書グラフ構造更新部３から、新規文書の文書ＩＤと、最近接文書のＩＤと、上記２文書間の距離とを受け取ると、Ｓ３１で、上記最近接文書のＩＤが、クラスタ組合せ情報記録部５に存在するか否かを問い合わせる。
【００７７】
上記記最近接文書のＩＤが、クラスタ組合せ情報記録部５に存在しなければ、処理を終え、次の新規文書の入力を待つ。上記最近接文書のＩＤが、クラスタ組合せ情報記録部５に存在すれば、Ｓ３２で、文書グラフ構造更新部３から受け取った上記２文書間の距離と、クラスタ組合せ情報記録部５において最近接文書と共に記録されている距離とを比較する。文書グラフ構造更新部３から受け取った上記２文書間の距離が、クラスタ組合せ情報記録部５において最近接文書と共に記録されている距離以下であれば、Ｓ３３に進む。文書グラフ構造更新部３から受け取った上記２文書間の距離が、クラスタ組合せ情報記録部５に、最近接文書と共に記録されている距離よりも大きければ、処理を終え、次の新規文書の入力を待つ。
【００７８】
Ｓ３３で、新規文書をクラスタ組合せ情報記録部５に記録する。記録する内容は、文書ＩＤと、距離とであるが、組合せＩＤと距離とは、最近接文書と共に記録されている組合せＩＤ、距離と同じ値を複写する。
【００７９】
次に、実施例１において、クラスタ組合せ情報記録部５に記録されているものがある場合、クラスタ組合せ情報更新部６の処理の具体例について説明する。
【００８０】
クラスタ組合せ情報記録部５に、図９に示すデータが記録されているとし、新規文書の文書ＩＤがｄ１０であり、文書ｄ１０の最近接文書の文書ＩＤがｄ１であり、文書ｄ１０とｄ１との距離が０．３であるとする。この場合、クラスタ組合せ情報記録部５には、最近接文書ｄ１が存在し、文書ｄ１０とｄ１との距離０．３が、文書ｄ１と共に記録されている距離０．４以下であるので、新規文書をクラスタ組合せ情報記録部５に追加する（Ｓ３３）。この結果、クラスタ組合せ情報記録部５には、文書ＩＤがｄ１０であり、組合せＩＤが「組合せ１」、距離が０．４である行が追加される。
【００８１】
クラスタ組合せ情報記録部５に最近接文書ｄ１が存在しないか、または存在しても、文書ｄ１０とｄ１との距離が、文書ｄ１と共に記録されている距離０．４よりも大きければ、クラスタ組合せ情報記録部５へは追加しない。
【００８２】
クラスタ組合せ情報更新部６が行う上記処理は、文書を入力するタイミングによらず、クラスタ組合せ情報記録部５に記録した内容を維持するための処理である。通常、利用者がクラスタを指定した時点で、上記クラスタに含まれている文書しか、クラスタ組合せ情報記録部５には記録し得ないが、上記処理によれば、クラスタ指定後に入力した文書であっても、仮にクラスタ指定以前に入力していれば、上記クラスタに含まれている性質の文書（つまり、上記クラスタ内の文書との類似度が高く、同一クラスタに含まれるべき文書）であれば、クラスタ組合せ情報記録部５に記録される。
【００８３】
上記実施例によれば、クラスタ分類結果が変更された場合でも、利用者が指示したクラスタ間の組合せに関する情報を継承させるので、クラスタ分類結果に、利用者の意図を適切に反映させることができる。
【００８４】
上記実施例において、文書ＩＤの代わりに、文書のタイトル、文書自体を使用するようにしてもよい。ここで、文書ＩＤ、文書のタイトル、文書自体を包含した概念が文書識別子である。また、上記最接近文書ＩＤの代わりに、最接近文書のタイトル、最接近文書自体を使用するようにしてもよい。ここで、最接近文書ＩＤ、最接近文書のタイトル、最接近文書自体を包含した概念が最接近文書識別子である。
【００８５】
つまり、上記実施例は、文書記録部に記録されている所定の文書に最も近い文書である最接近文書の識別子である最接近文書識別子と、上記所定の文書と、上記最接近文書との距離との３つを１組として記録することによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を記録する文書グラフ構造記録手段と、上記文書グラフ構造記録手段に記録されている文書間の距離を参照し、予め定められている閾値、または、利用者が指定する閾値に応じて、上記文書グラフ構造記録手段に記録されている文書を、複数のクラスタに分割するクラスタリング手段と、クラスタ内の各文書の文書識別子と、上記クラスタ内の文書間距離の最大値と、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に付与される同一のＩＤである組合せＩＤとを記録するクラスタ組合せ情報記録手段と、上記クラスタリング手段が生成したクラスタである初期クラスタを記録する初期クラスタ記録手段とを有する文書群組合せ装置の例である。
【００８６】
この場合、上記文書記録部に新たに入力された文書である新規文書と過去に入力済の文書との距離を算出し、上記最近接文書との距離とを、上記文書グラフ構造記録手段に記録させることによって、複数の文書が、距離付きのリンクで接続されている文書グラフ構造を更新する文書グラフ構造更新手段を有する。
【００８７】
また、上記新規文書の最近接文書が上記クラスタ組合せ情報記録手段に既に記録され、かつ上記新規文書と上記最近接文書との距離が、上記最近接文書と共に記録されている距離以下である場合に、上記新規文書を新規に記録するクラスタ組合せ情報更新手段を有する。
【００８８】
さらに、クラスタを組合せた結果を、画面上に表示するクラスタ組合せ表示手段を有する。
【００８９】
しかも、利用者が組合せることを望むクラスタを指定する操作部と、利用者が指定する各クラスタを構成する文書間のリンクについて、上記文書グラフ構造記録手段を参照して距離を獲得し、文書間距離の最大値を算出し、クラスタ内の各文書と、上記最大値と、上記組合せＩＤとを上記クラスタ組合せ情報記録手段に記録させべきかどうかを判断する判断部と、上記クラスタ組合せ情報記録手段に記録させべきであると判断すると、クラスタ内の各文書と、上記最大値と、上記組合せＩＤとを上記クラスタ組合せ情報記録手段に送信し、記録させる制御部とを具備する制御手段を有する。
【００９０】
また、上記実施例を方法の発明として把握することができる。つまり、上記実施例は、文書記録部に新たに入力された文書である新規文書の文書識別子とベクトルとを取得する段階と、文書グラフ構造記録部に文書が既に蓄積されているか否かを判定する段階と、新規文書が２番目以降に入力した文書であり、上記文書グラフ構造記録部に文書が既に記録されていれば、上記文書グラフ構造記録部に既に記録されている文書の文書ＩＤを全て取得し、各文書のベクトルを、文書記録部から取得し、各ベクトルを新規文書のベクトルと比較し、文書間の距離を算出し、記憶装置に記憶する段階と、上記算出した距離に基づいて、新規文書からの距離が最も小さい文書が、最近接文書であると判定し、上記新規文書の文書識別子と、上記最近接文書の識別子である最接近文書識別子と、上記２文書間の距離とを、上記文書グラフ構造記録部とクラスタ組合せ情報更新部とに送出する段階と、上記文書グラフ構造記録部に文書が蓄積されていないと判断されると、上記新規文書の文書識別子のみを上記文書グラフ構造記録部に記録する段階とを有する文書分類方法の例である。
【００９１】
さらに、上記実施例は、クラスタ内文書数が２以上であると判断されると、取得した各文書の文書ＩＤに基づいて、文書グラフ構造記録部を参照し、クラスタを構成する各文書間の距離の最大値を取得し、記憶装置に記憶する段階と、上記クラスタ内の文書の文書識別子が上記クラスタ組合せ情報記録部に記録済であり、上記文書識別子に対応して記録されている距離が、上記最大値よりも小さければ、上記クラスタ内の文書の文書識別子と、上記取得した距離の最大値とを対応付けし、上記クラスタ組合せ情報記録部に記録する段階と、ユーザが複数のクラスタを組合せる指示を出すと、上記組合せる対象のクラスタに含まれている文書に、同一のＩＤである組合せＩＤ付与し、クラスタ組合せ情報記録部に、各文書と上記最大値と上記組合せＩＤとが存在すれば、記録しようとする距離と、既に記録されている距離とを比較し、記録しようとする距離が、既に記録されている距離よりも大きければ、上記記録しようとする距離を上書きする段階とを有する文書分類方法の例である。
【００９２】
しかも、上記実施例は、文書グラフ構造更新部から、文書記録部に新たに入力された文書である新規文書の文書識別子と、文書記録部に記録されている所定の文書に最も近い文書である最近接文書の識別子である最近接文書識別子と、上記所定の文書と上記最近接文書との２文書間の距離とを受け取ると、上記最近接文書識別子が、クラスタ組合せ情報記録部に存在するか否かを問い合わせる段階と、上記最近接文書識別子が、クラスタ組合せ情報記録部に存在すれば、上記文書グラフ構造更新部から受け取った上記２文書間の距離と、クラスタ組合せ情報記録部において上記最近接文書と共に記録されている距離とを比較し、記憶装置に記憶する段階と、文書グラフ構造更新部から受け取った上記２文書間の距離が、クラスタ組合せ情報記録部において最近接文書と共に記録されている距離以下であれば、新規文書をクラスタ組合せ情報記録部に記録する段階とを有する文書分類方法の例である。
【００９３】
また、上記実施例をプログラムの発明として把握することができる。つまり、上記実施例は、請求項６〜請求項８のうちの少なくとも１つの請求項に記載の方法をコンピュータに実行させるプログラムの例である。
【００９４】
さらに、上記実施例を記録媒体として把握することができる。つまり、上記実施例は、請求項６〜請求項８のうちの少なくとも１つの請求項に記載の方法をコンピュータに実行させるプログラムを記録したコンピュータ読取可能な記録媒体の例である。この記録媒体は、ＣＤ、ＤＶＤ、ＨＤ、光ディスク、光磁気ディスク、半導体メモリ等の記録媒体である。
【図面の簡単な説明】
【００９５】
【図１】本発明の実施例１である文書群組合せ装置１００を示すブロック図である。
【図２】文書グラフ構造更新部３が、文書グラフ構造記録部２に記録されている情報を更新する動作を示すフローチャートである。
【図３】文書グラフ構造記録部２に記録されているデータの例を示す図である。
【図４】文書グラフ構造記録部２に記録されているデータを、図式化した文書グラフ構造を示す図である。
【図５】閾値を０．４として生成したクラスタの例を示す図である。
【図６】初期クラスタ記録部７に記録されているデータの一覧の例を示す図である。
【図７】クラスタ組合せ表示部８による画面の表示例を示す図である。
【図８】制御部９が行う処理を示すフローチャートである。
【図９】クラスタ組合せ情報記録部５に記録されているデータ例を示す図である。
【図１０】閾値を０．５として生成したクラスタの例を示す図である。
【図１１】クラスタＣ１１とＣ１２とを組合せる指示を、利用者が入力した場合、クラスタ組合せ情報記録部５に記録されているデータの変化後の例を示す図である。
【図１２】実施例１において、新規文書が入力される度に、クラスタ組合せ情報更新部６が行う処理を示すフローチャートである。
【符号の説明】
【００９６】
１００…文書群組合せ装置、
１…文書記録部、
２…文書グラフ構造記録部、
３…文書グラフ構造更新部、
４…クラスタリング部、
５…クラスタ組合せ情報記録部、
６…クラスタ組合せ情報更新部、
７…初期クラスタ記録部、
８…クラスタ組合せ表示部、
９…制御部。
【図１】
2008287493.tif 000003
【図２】
2008287493.tif 000004
【図３】
2008287493.tif 000005
【図４】
2008287493.tif 000006
【図５】
2008287493.tif 000007
【図６】
2008287493.tif 000008
【図７】
2008287493.tif 000009
【図８】
2008287493.tif 000010
【図９】
2008287493.tif 000011
【図１０】
2008287493.tif 000012
【図１１】
2008287493.tif 000013
【図１２】
2008287493.tif 000014