(57)【要約】【課題】文書に対するクラスタリングの並列処理を効率的に行うことができる文書分割装置、文書分割プログラムおよび文書分割方法を提供する。【解決手段】生成部４１は、文書データ３０の複数の文書それぞれの特徴を示す特徴情報として索引データ３１を生成する。文書間類似度算出部４２は、生成された索引データ３１に基づき、複数の文書間の類似度を算出し、算出した文書間の類似度を文書間類似度データ３２として格納する。集合間類似度算出部４４は、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出し、算出した集合間の類似度を集合間類似度データ３４として格納する。分類部４５は、集合間の類似度の高い文書同士をグループに分類する。分割部４６は、クラスタデータ３５に記憶されたグループ単位で、複数の文書を分割する。【選択図】図１
2013196212.tif 000002
【特許請求の範囲】
【請求項１】
クラスタリング対象とする複数の文書それぞれの特徴を示す特徴情報を生成する生成部と、
前記生成部により生成された特徴情報に基づき、前記複数の文書間の類似度を算出する文書間類似度算出部と、
各文書の前記文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出する集合間類似度算出部と、
前記集合間の類似度の高い文書同士をグループに分類する分類部と、
前記分類部により分類されたグループ単位で前記複数の文書を分割する分割部と、
を有することを特徴とする文書分割装置。
【請求項２】
前記集合間類似度算出部は、各文書を、それぞれ当該文書との類似度が上位の所定位以内の文書を要素とし、類似度を要素の値としたベクトルと見なして、ベクトル間の類似度から文書の集合間の類似度を算出する
ことを特徴とする請求項１に記載の文書分割装置。
【請求項３】
前記分割部により前記複数の文書を分割した分散データおよび当該分散データに含まれる文書にかかる前記文書間の類似度を、それぞれクラスタリングを実行する処理部へ出力する出力部をさらに有することを特徴とする請求項１または２に記載の文書分割装置。
【請求項４】
前記分割部は、文書数が同等となるように前記複数の文書を分散データに分割する
ことを特徴とする請求項１〜３の何れか１つに記載の文書分割装置。
【請求項５】
コンピュータに、
クラスタリング対象とする複数の文書それぞれの特徴を示す特徴情報を生成し、
生成された特徴情報に基づき、前記複数の文書間の類似度を算出し、
各文書の前記文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出し、
前記集合間の類似度の高い文書同士をグループに分類し、
前記分類部により分類されたグループ単位で前記複数の文書を分割する
各処理を実行させることを特徴とする文書分割プログラム。
【請求項６】
コンピュータが、
クラスタリング対象とする複数の文書それぞれの特徴を示す特徴情報を生成し、
生成された特徴情報に基づき、前記複数の文書間の類似度を算出し、
各文書の前記文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出し、
前記集合間の類似度の高い文書同士をグループに分類し、
前記分類部により分類されたグループ単位で前記複数の文書を分割する
各処理を実行することを特徴とする文書分割方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書分割装置、文書分割プログラムおよび文書分割方法に関する。
【背景技術】
【０００２】
従来から複数の文書同士の類似度を計算し、類似度が高い文書をクラスタリングする技術が知られている。このクラスタリングは、例えば、ヘルプデスクなどで受けた問い合わせに対してＦＡＱ（Frequently  Asked  Question）を作成する際に、頻度の高い問い合わせを特定する際に用いられる。
【０００３】
クラスタリングでは、例えば、複数の文書同士を総当りで比較して類似する文書を求める。このようにクラスタリングでは、複数の文書同士を総当りで比較して各文書間の類似度を求めるため、クラスタリングの対象とする文書数の増加に伴い処理で使用する記憶容量が増加し、処理時間も増加する。
【０００４】
従来よりデータ処理を行う際の処理時間や処理負荷の軽減を図る方法として、複数のコンピュータやプロセッサによる並列処理が知られている。そこで、例えば、データの複製を複数用意して、複数のコンピュータやプロセッサでクラスタリングを並列処理させる方法が考えられる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−２６３４４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、クラスタリングを並列処理させる場合、対象とする文書数の増加に伴い多くの記憶容量が必要となる中で、データの複製を作成することになるため、より記憶容量を消費する。
【０００７】
開示の技術は、上記に鑑みてなされたものであって、文書に対するクラスタリングの並列処理を効率的に行うことができる文書分割装置、文書分割プログラムおよび文書分割方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願の開示する文書分割装置は、生成部と、文書間類似度算出部と、集合間類似度算出部と、分類部と、分割部と、を有する。生成部は、クラスタリング対象とする複数の文書それぞれの特徴を示す特徴情報を生成する。文書間類似度算出部は、生成部により生成された特徴情報に基づき、前記複数の文書間の類似度を算出する。集合間類似度算出部は、各文書の前記文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出する。分類部は、集合間の類似度の高い文書同士をグループに分類する。分割部は、分類部により分類されたグループ単位で前記複数の文書を分割する。
【発明の効果】
【０００９】
本願の開示する文書分割装置によれば、文書に対するクラスタリングの並列処理を効率的に行うことができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、文書分割装置の全体構成を示す図である。
【図２】図２は、文書間類似度データの構成例を示す図である。
【図３】図３は、集合間類似度データの構成例を示す図である。
【図４】図４は、文書の集合間の類似度を説明するための説明図である。
【図５】図５は、文書を分類する処理の流れの一例を示す図である。
【図６】図６は、文書を分割する処理の流れの一例を示す図である。
【図７】図７は、クラスタリングを説明するための説明図である。
【図８】図８は、文書データに対する処理の流れを模式的に示した図である。
【図９】図９は、文書データに含まれるクラスタリング対象の文書の文書名および文書に含まれる単語の一例を示す図である。
【図１０】図１０は、索引データの一例を示す図である。
【図１１】図１１は、文書間類似度データの一例を示す図である。
【図１２】図１２は、除外文書データの一例を示す図である。
【図１３】図１３は、集合間類似度データの一例を示す図である。
【図１４】図１４は、クラスタデータの一例を示す図である。
【図１５】図１５は、分散データの一例を示す図である。
【図１６】図１６は、分割処理の手順を示すフローチャートである。
【図１７】図１７は、索引生成処理の手順を示すフローチャートである。
【図１８】図１８は、文書間類似度算出処理の手順を示すフローチャートである。
【図１９】図１９は、除外文書特定処理の手順を示すフローチャートである。
【図２０】図２０は、集合間類似度算出処理を示すフローチャートである。
【図２１】図２１は、分類処理を示すフローチャートである。
【図２２】図２２は、分割処理を示すフローチャートである。
【図２３】図２３は、クラスタリング処理の手順を示すフローチャートである。
【図２４】図２４は、分割プログラムを実行するコンピュータの一例について説明するための図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示する文書分割装置、文書分割プログラムおよび文書分割方法の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。そして、各実施例は、処理内容を矛盾させない範囲で適宜組み合わせることが可能である。
【実施例１】
【００１２】
［文書分割装置１０の構成］
実施例１に係る文書分割装置について説明する。図１は、文書分割装置の全体構成を示す図である。文書分割装置１０は、複数の文書を類似度が高い文書同士の組に分割する装置であり、例えば、コンピュータである。
【００１３】
文書分割装置１０は、外部Ｉ／Ｆ（インタフェース）部２０と、記憶部２１と、制御部２２とを有する。
【００１４】
外部Ｉ／Ｆ部２０は、外部と各種の情報を入出力するインタフェースである。外部Ｉ／Ｆ部２０は、例えば、ネットワークなどのデータ伝送路を介して外部装置から各種の情報を入出力するインタフェースであってもよい。また、外部Ｉ／Ｆ部２０は、例えば、フラッシュメモリなどの記憶媒体との間で各種情報を入出力するインタフェースであってもよい。外部Ｉ／Ｆ部２０は、外部装置と通信を行うことにより、あるいは、記憶媒体を介して各種情報を取得する。例えば、外部Ｉ／Ｆ部２０には、クラスタリング対象である複数の文書が入力される。また、外部Ｉ／Ｆ部２０は、分割された分散データ３６をクラスタリングを行うコンピュータやプロセッサに出力する。また、外部Ｉ／Ｆ部２０は、クラスタリングを行うコンピュータやプロセッサとの間でクラスタリングの結果を入出力する。
【００１５】
記憶部２１は、フラッシュメモリなどの半導体メモリ素子、ハードディスク、光ディスクなどの記憶装置である。なお、記憶部２１は、上記の種類の記憶装置に限定されるものではなく、ＲＡＭ（Random  Access  Memory)、ＲＯＭ（Read  Only  Memory)であってもよい。
【００１６】
記憶部２１は、制御部２２で実行されるＯＳ（Operating  System）や後述する文書の分割に用いる各種プログラムを記憶する。さらに、記憶部２１は、制御部２２で実行されるプログラムで使用する各種データを記憶する。かかるデータの一例として、記憶部２１は、文書データ３０と、索引データ３１と、文書間類似度データ３２と、除外文書データ３３と、集合間類似度データ３４と、クラスタデータ３５と、分散データ３６とを記憶する。
【００１７】
文書データ３０は、クラスタリングの対象となる複数の文書が記憶されたデータである。一例として、文書データ３０は、外部Ｉ／Ｆ部２０に入力されたクラスタリング対象である複数の文書の文書データが後述の登録部４０によって格納される。他の一例として、文書データ３０は、後述の生成部４１および分割部４６によって参照される。
【００１８】
索引データ３１は、文書データ３０に記憶された複数の文書に含まれる単語がどの文書に含まれるかを示す索引が記憶されたデータである。一例として、索引データ３１は、後述の生成部４１によって生成されて格納される。他の一例として、索引データ３１は、後述の文書間類似度算出部４２によって参照される。
【００１９】
文書間類似度データ３２は、文書データ３０に記憶された各文書について、自文書を含む各文書との間の類似度が記憶されたデータである。一例として、文書間類似度データ３２は、後述の文書間類似度算出部４２によって算出されて格納される。他の一例として、文書間類似度データ３２は、後述の除外文書特定部４３、集合間類似度算出部４４および出力部４７によって参照される。
【００２０】
図２は、文書間類似度データの構成例を示す図である。文書データ３０に含まれる各文書には、それぞれの文書を識別する文書名が定めされる。文書名は、文書にそれぞれ予め定められ、文書データ３０に記憶されている場合、その文書名を用いてもよい。また、文書名は、文書分割装置１０において、文書データ３０に含まれる各文書に対して定めてもよい。図２の例は、文書名が「Ａ」〜「Ｚ」の各文書について、類似度が所定の第１閾値以上である相手の文書名と、類似度を、[文書名，類似度]の形式で類似度が大きい順位に並べ記憶されている。類似度は、値が大きいほど類似していることを示す。本実施例では、類似度は、０．０〜１．０までの範囲に正規化している。図２の例は、文書Ａは、文書Ａとの類似度が１．０であり、文書Ｂとの類似度が０．８であり、文書Ｃとの類似度が０．８であり、文書Ｅとの類似度が０．７であることを示す。また、文書Ｂは、文書Ｂとの類似度が１．０であり、文書Ａとの類似度が０．８であり、文書Ｄとの類似度が０．８であり、文書Ｇとの類似度が０．５であることを示す。また、文書Ｃは、文書Ｃとの類似度が１．０であり、文書Ｅとの類似度が０．９であり、文書Ａとの類似度が０．８であり、文書Ｄとの類似度が０．７であることを示す。また、文書Ｄは、文書Ｄとの類似度が１．０であり、文書Ｂとの類似度が０．８であり、文書Ｃとの類似度が０．７であることを示す。また、文書Ｉは、文書Ｉとの類似度が１．０であることを示す。また、文書Ｊは、文書Ｊとの類似度が１．０であり、文書Ｘとの類似度が０．９であり、文書Ｋとの類似度が０．５であることを示す。また、文書Ｘは、文書Ｘとの類似度が１．０であり、文書Ｊとの類似度が０．９であり、文書Ｙとの類似度が０．８であることを示す。また、文書Ｙは、文書Ｙとの類似度が１．０であり、文書Ｚとの類似度が０．８であり、文書Ｘとの類似度が０．８であることを示す。また、文書Ｚは、文書Ｚとの類似度が１．０であり、文書Ｘとの類似度が０．９であり、文書Ｙとの類似度が０．８であることを示す。
【００２１】
除外文書データ３３は、第１閾値以上類似する文書が自文書以外にない文書を除外文書として記憶したデータである。一例として、除外文書データ３３は、後述の除外文書特定部４３によって除外文書が特定されて格納される。他の一例として、除外文書データ３３は、後述の分割部４６によって参照される。
【００２２】
集合間類似度データ３４は、文書データ３０に記憶された各文書について、それぞれの文書の類似する文書集合間の類似度が記憶されたデータである。一例として、集合間類似度データ３４は、後述の集合間類似度算出部４４によって算出されて格納される。他の一例として、集合間類似度データ３４は、後述の分類部４５によって参照される。
【００２３】
図３は、集合間類似度データの構成例を示す図である。図２の例は、文書名が「Ａ」〜「Ｚ」の各文書について、類似する文書集合間の類似度が記憶されている。集合間の類似度は、値が大きいほどその集合に含まれる文書が類似する文書が類似していることを示す。本実施例では、集合間の類似度は、０．０〜１．０までの範囲に正規化している。図３の例は、文書名が「Ａ」〜「Ｚ」の各文書について、相手の文書名と、集合間の類似度を、[文書名，類似度]の形式で類似度が大きい順位に並べ記憶されている。図３の例は、文書Ａは、文書Ｂとの集合間の類似度が０．５であることを示す。また、文書Ｂは、文書Ａとの集合間の類似度が０．５であり、文書Ｃとの集合間の類似度が０．３であることを示す。また、文書Ｃは、文書Ｄとの集合間の類似度が０．３であることを示す。また、文書Ｄは、文書Ｂとの集合間の類似度が０．４であり、文書Ｃとの類似度が０．３であることを示す。また、文書Ｊは、文書Ｋとの集合間の類似度が０．４であることを示す。また、文書Ｘは、文書Ｙとの集合間の類似度が０．５であることを示す。また、文書Ｙは、文書Ｚとの集合間の類似度が０．６であり、文書Ｘとの類似度が０．５であることを示す。また、文書Ｚは、文書Ｙとの集合間の類似度が０．６であることを示す。
【００２４】
クラスタデータ３５は、文書データ３０に示される複数の文書をグループに分類し、各グループの文書をクラスタとして記憶したデータである。一例として、クラスタデータ３５は、後述の分類部４５によって生成されて格納される。他の一例として、クラスタデータ３５は、後述の分割部４６によって参照される。
【００２５】
分散データ３６は、文書データ３０に示される複数の文書をクラスタデータ３５により示されるグループ単位で分けた文書を記憶したデータである。一例として、分散データ３６は、後述の分割部４６によって生成されて格納される。他の一例として、分散データ３６は、後述の出力部４７およびクラスタリング部４８によって参照される。
【００２６】
図１に戻り、制御部２２は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。制御部２２には、各種の集積回路や電子回路を採用できる。例えば、集積回路としては、ＡＳＩＣ（Application  Specific  Integrated  Circuit）が挙げられる。また、電子回路としては、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などが挙げられる。制御部２２は、図１に示すように、登録部４０と、生成部４１と、文書間類似度算出部４２と、除外文書特定部４３と、集合間類似度算出部４４と、分類部４５と、分割部４６と、出力部４７と、クラスタリング部４８とを有する。
【００２７】
このうち、登録部４０は、文書データを記憶部２１へ登録する処理部である。一態様としては、登録部４０は、データ伝送路あるいは記憶媒体から外部Ｉ／Ｆ部２０にクラスタリング対象である複数の文書を示す文書データが入力された場合に、文書データを記憶部２１へ登録する。これにより、記憶部２１には、文書データ３０が格納される。
【００２８】
生成部４１は、文書データ３０に記憶されたクラスタリング対象とする複数の文書それぞれの特徴を示す特徴情報を生成する処理部である。一態様としては、生成部４１は、文書の特徴を示す特徴情報として、文書データ３０に示される各文書に含まれる各単語がどの文書に含まれるかを示す索引データ３１を生成する。例えば、生成部４１は、文書データ３０に示される各文書からそれぞれ単語を抽出し、各単語を文書名と対応させて記憶する。そして、生成部４１は、各文書から抽出した単語および文書名を単語の文字コード順に並べる。文字コード順に並べた結果、単語毎に、単語および文書名が順に並ぶ。生成部４１は、文字コード順に並べた単語および文書名を順に参照して、それぞれ各単語がどの文書に含まれるかを示す索引データ３１を生成する。生成部４１は、生成した索引データ３１を記憶部２１に格納する。
【００２９】
文書間類似度算出部４２は、文書データ３０に記憶されたクラスタリング対象とする複数の文書間の類似度を算出する処理部である。一態様としては、文書間類似度算出部４２は、生成部４１により生成された索引データ３１に基づき、文書データ３０に記憶された複数の文書間の類似度を算出する。例えば、文書間類似度算出部４２は、索引データ３１に基づき、文書データ３０に示される各文書に含まれる単語を特定する。そして、文書間類似度算出部４２は、それぞれの文書を単語のベクトルと見なしてベクトル間の角度(cosineθ)を文書間の類似度を算出している。
【００３０】
例えば、文書Ａが単語ａ、単語ｂ、単語ｃ、単語ｄを含み、文書Ｂが単語ｂ、単語ｃ、単語ｄ、単語ｅを含むものとする。この場合、文書間類似度算出部４２は、文書Ａと文書Ｂが含む単語を要素とし、それぞれ単語を含む場合、単語を対応する要素の値を１とし、それぞれ単語を含まない場合、単語を対応する要素の値を０としたベクトルを求める。例えば、ベクトルの要素が（単語ａ、単語ｂ、単語ｃ、単語ｄ、単語ｅ）に対応するものとした場合、文書ＡのベクトルＡは、（１、１、１、１、０）と求まる。また、文書ＢのベクトルＢは、（０、１、１、１、１）と求まる。文書間類似度算出部４２は、ベクトルＡ、ベクトルＢについて、以下の（１）式に示す角度(cosineθ)を求める演算を行って文書Ａと文書Ｂの類似度を求める。
類似度＝Ａ・Ｂ／（｜Ａ｜×｜Ｂ｜）            （１）
【００３１】
ここで、Ａ・Ｂは、１×０＋１×１＋１×１＋１×１＋０×１＝３と算出される。また、｜Ａ｜は、（１×１＋１×１＋１×１＋１×１＋０×０）１／２＝２と算出される。同様に、｜Ｂ｜は、（０×０＋１×１＋１×１＋１×１＋１×１）１／２＝２と算出される。よって、文書Ａと文書Ｂの類似度は、３／（２×２）＝０．７５と算出される。
【００３２】
文書間類似度算出部４２は、文書データ３０に示される各文書毎に、文書データ３０に示される自文書を含む各文書をそれぞれ相手文書として類似度を求める。そして、文書間類似度算出部４２は、求めた類似度が所定の第１閾値以上である相手文書の文書名および類似度を文書間類似度データ３２として記憶部２１に格納する。例えば、第１閾値を０．４とし、文書間類似度算出部４２は、類似度が０．４以上である相手文書の文書名および類似度を文書間類似度データ３２として記憶部２１に格納するものとする。なお、第１閾値については、この例示に限るものではなく、文書分割装置１０を利用する者が任意の値に設定してよい。これにより、記憶部２１には、図２に示すように文書間類似度データ３２が記憶される。なお、類似度の算出方法は、文書間が類似している度合いを算出できるものであれば、文書を単語のベクトルと見做し上記の角度(cosineθ)を求める方法に限らず何れの方式を用いてもよい。例えば、自文書及び相手文書に互いに同じ単語が含まれる割合を類似度として算出してもよい。
【００３３】
除外文書特定部４３は、何れの文書とも類似していない文書を特定する処理部である。一態様としては、除外文書特定部４３は、文書間類似度データ３２に基づき、自文書以外に類似度が上記第１閾値以上の文書がない文書を特定する。例えば、除外文書特定部４３は、文書間類似度データ３２において自文書以外に類似する文書が登録されていない文書を特定する。図２の例では、文書Ｉが自文書Ｉ以外に類似度が０．４以上の文書がない。このため、除外文書特定部４３は、文書Ｉを除外文書と特定する。除外文書特定部４３は、特定した文書を除外文書データ３３として記憶部２１に格納する。
【００３４】
集合間類似度算出部４４は、文書データ３０に記憶された各文書について、それぞれの類似する文書の集合間の類似度を算出する処理部である。一態様としては、集合間類似度算出部４４は、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出する。例えば、集合間類似度算出部４４は、除外文書特定部４３により除外された文書を除き、各文書の文書間の類似度が上位４位以内の文書の集合間の類似度を算出する。なお、集合間類似度算出部４４は、文書に類似度が上記第１閾値以上である相手文書が所定位分無い場合、類似度が上記第１閾値以上の全文書の集合間で類似度を算出する。すなわち、類似度が上記第１閾値以上の文書が３つしか無い場合は、３つの文書を集合として類似度を算出する。例えば、上位の所定位以内の文書として上位４位以内の文書の集合間の類似度を算出するものとする。なお、類似度を算出する範囲とする順位については、この例示に限るものではなく、文書分割装置１０を利用する者が任意の値に設定してよい。
【００３５】
集合間類似度算出部４４は、文書間類似度データ３２に基づき、文書データ３０に示される各文書を、それぞれ類似する文書を要素とし、類似する文書との類似度を要素の値としたベクトルと見なして、ベクトル間の類似度から文書の集合間の類似度を算出する。例えば、文書Ａは、上位４位の文書および類似度が[Ａ、１．０]、[Ｂ、０．８]、[Ｃ、０．８]、[Ｅ、０．７]であり、文書Ｂは、上位４位以内の文書および類似度が[Ｂ、１．０]、[Ａ、０．８]、[Ｄ、０．８]、[Ｇ、０．５]であるものとする。この場合、集合間類似度算出部４４は、文書Ａおよび文書Ｂに類似する文書を要素とし、類似度を要素の値としたベクトルを求める。例えば、ベクトルの要素が（文書Ａ、文書Ｂ、文書Ｃ、文書Ｄ、文書Ｅ、文書Ｇ）に対応するものとした場合、文書ＡのベクトルＡは（１．０、０．８、０．８、０．０、０．７、０．０）と求まる。また、文書ＢのベクトルＢは（０．８、１．０、０．０、０．８、０．０、０．５）と求まる。集合間類似度算出部４４は、ベクトルＡ、ベクトルＢについて、以下の（２）式に示す角度cosineθを求めこれを文書Ａと文書Ｂの類似度としている。
類似度＝Ａ・Ｂ／（｜Ａ｜×｜Ｂ｜）            （２）
【００３６】
ここで、Ａ・Ｂは、１．０×０．８＋０．８×１．０＋０．８×０．０＋０．０×０．８＋０．７×０．０＋０．０×０．５＝１．６と算出される。また、｜Ａ｜は、（１．０×１．０＋０．８×０．８＋０．８×０．８＋０．７×０．７）１／２＝（２．７７）１／２と算出される。同様に、｜Ｂ｜は、（０．８×０．８＋１．０×１．０＋０．８×０．８＋０．５×０．５）１／２＝（２．５３）１／２と算出される。よって、文書Ａと文書Ｂの類似度は、１．６／（（２．７７）１／２×（２．５３）１／２）≒０．６と算出される。
【００３７】
また、例えば、文書Ａおよび文書Ｂが、相手文書が３つしかなく、文書Ａは、相手文書および類似度が[Ａ、１．０]、[Ｂ、０．５]、[Ｃ、０．３]であり、文書Ｂは、相手文書および類似度が[Ｂ、１．０]、[Ａ、０．８]、[Ｃ、０．４]であるものとする。この場合も、集合間類似度算出部４４は、文書Ａおよび文書Ｂに類似する文書を要素とし、類似度を要素の値としたベクトルを求める。例えば、ベクトルの要素が（文書Ａ、文書Ｂ、文書Ｃ）に対応するものとした場合、文書ＡのベクトルＡは（１．０、０．５、０．３）と求まる。また、文書ＢのベクトルＢは（０．８、１．０、０．４）と求まる。集合間類似度算出部４４は、ベクトルＡ、ベクトルＢについて、上述の（２）式に示す演算を行って文書Ａと文書Ｂの類似度を求める。
【００３８】
ここで、Ａ・Ｂは、１．０×０．８＋０．５×１．０＋０．３×０．４＝１．４２と算出される。また、｜Ａ｜は、（１．０×１．０＋０．５×０．５＋０．３×０．３）１／２＝（１．３９）１／２と算出される。同様に、｜Ｂ｜は、（０．８×０．８＋１．０×１．０＋０．４×０．４）１／２＝（１．８）１／２と算出される。よって、文書Ａと文書Ｂの類似度は、１．４２／（（１．３９）１／２×（１．８）１／２）≒０．９２と算出される。
【００３９】
ここで、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度について説明する。図４は、文書の集合間の類似度を説明するための説明図である。図４の例では、各文書の文書間の類似度の一例が示されている。また、図４の例では、文書Ａ〜Ｇ、Ｎ〜Ｑを文書間の類似度が高いほど文書間の距離を短く配置して文書間の類似度を模式的に示している。また、図４の例では、文書間の類似度が高い文書Ａ〜Ｇを「●」で示し、文書間の類似度が低い文書Ｎ〜Ｑを「○」で示している。図４の例では、例えば、クラスタリングを行った場合、互いに文書間の類似度が高い範囲５０内の文書Ａ〜Ｇがクラスタにまとまることが期待される。この文書Ａ〜Ｇは、互いに類似しているため、類似する文書の集合間の類似度を算出した場合、類似度が高く算出される。よって、類似する文書の集合間の類似度が高い文書を同じグループにまとめることにより、類似する文書が別の分散データ３６に分割されることを抑制できる。また、それぞれの文書間について、類似する文書の集合で類似度を算出することにより、類似する文書が同じグループに分類しやすくなる。
【００４０】
集合間類似度算出部４４は、各文書毎に、相手文書の文書名および集合間の類似度を集合間類似度データ３４として記憶部２１に格納する。これにより、記憶部２１には、図３に示すように集合間類似度データ３４が記憶される。なお、図３に示す集合間類似度データ３４は、一例であり、図２に示す文書間類似度データ３２から求めたものではない。
【００４１】
分類部４５は、文書データ３０に記憶された各文書を集合間の類似度の高い文書同士をグループに分類する処理部である。一態様としては、分類部４５は、集合間類似度データ３４に基づき、各文書を集合間の類似度が所定の第２閾値以上である文書同士をグループに分類する。図５は、文書を分類する処理の流れの一例を示す図である。例えば、分類部４５は、集合間類似度データ３４に記憶された各文書を、文書の集合間の類似度の大きい順に並べ、類似度の大きい順に各文書を順次、処理対象と特定する。分類部４５は、処理対象とされた文書が、既に処理対象とされた文書と集合間の類似度が第２閾値以上である場合、既に処理対象とされた文書と同じグループに分類する。また、分類部４５は、既に処理対象とされた文書と集合間の類似度が第２閾値未満である場合、新たなグループとして分類する。例えば、第２閾値を０．４とし、分類部４５は、集合間の類似度が０．４以上である場合、既に処理対象とされた文書と同じグループに分類し、集合間の類似度が０．４未満である場合、新たなグループとして分類するものとする。これにより、文書データ３０に記憶された各文書は、グループに分類される。これにより、図５の例では、文書Ｙ、Ｚ、Ｘが同じグループに分類され、文書Ａ、Ｂ、Ｃ、Ｄが同じグループに分類され、文書Ｊ、Ｋが同じグループに分類される。分類部４５は、分類した各グループの文書をクラスタデータ３５として記憶部２１に格納する。なお、第２閾値については、この例示に限るものではなく、文書分割装置１０を利用する者が任意の値に設定してよい。
【００４２】
分割部４６は、文書データ３０に記憶された各文書を分散処理させる分散データに分割する処理部である。一態様としては、分割部４６は、クラスタデータ３５に記憶されたグループ単位で、複数の文書を分割する。また、分割部４６は、除外文書データ３３に記憶された除外文書を分散データに分割する。図６は、文書を分割する処理の流れの一例を示す図である。例えば、分割部４６は、分類部４５により分類されたグループを文書数の多い順に並べ、文書数の多い順に各グループを順次、処理対象と特定する。そして、分割部４６は、複数の分散データ３６に分割する場合、各分散データ３６のうち、文書数が最も少ない分散データ３６にグループ単位で文書を分割する。これにより、図６の例では、文書Ａ、Ｂ、Ｃ、Ｄのグループと文書Ｊ、Ｋのグループが分散データ３６Ａに分割され、文書Ｙ、Ｚ、Ｘが分散データ３６Ｂに分割される。また、分割部４６は、除外文書データ３３に記憶された除外文書も文書数が最も少ない分散データに分割する。なお、分割部４６は、文書数が最も少ない分散データ３６が複数ある場合、文書数が最も少ない何れかの分散データに文書を分割する。これにより、分散データには、文書数が同等となるように複数の文書が分割される。分割部４６は、分割した各分散データ３６を記憶部２１に格納する。
【００４３】
出力部４７は、記憶部２１に記憶された分散データ３６を、それぞれクラスタリングを実行する処理部へ出力する処理部である。一態様としては、出力部４７は、クラスタリングを実行する複数のコンピュータやプロセッサに対してクラスタリング対象のデータとして分散データ３６を出力する。また、出力部４７は、分散データ３６と共に、文書間類似度データ３２に記憶された当該分散データ３６に含まれる文書にかかる文書間の類似度をクラスタリングを実行する複数のコンピュータやプロセッサに対して出力する。本実施例では、何れか１つの分散データ３６を処理対象として文書分割装置１０においてクラスタリングを実行する。出力部４７は、クラスタリングの処理対象とされた分散データ３６以外の分散データ３６を他のコンピュータやプロセッサに対して出力する。出力された分散データ３６は、他のコンピュータやプロセッサにおいてクラスタリングが実行される。また、出力部４７は、分散データ３６と共に、文書間類似度データ３２に記憶された当該分散データ３６に含まれる文書にかかる文書間の類似度を他のコンピュータやプロセッサに対して出力する。他のコンピュータやプロセッサでは、分散データ３６に含まれる文書にかかる文書間の類似度を使用してクラスタリングを行うことにより、類似度の算出処理を軽減できる。
【００４４】
クラスタリング部４８は、クラスタリングの処理対象とされた分散データ３６のクラスタリングを実行する処理部である。一態様としては、クラスタリング部４８は、処理対象とされた分散データ３６に含まれる文書間の類似度を算出し、類似する文書をまとめるクラスタリング処理を実行する。この際、クラスタリング部４８は、文書間の類似度を算出する際、文書間類似度データ３２に処理対象の分散データ３６に含まれる文書にかかる文書間の類似度が記憶されている場合、記憶された類似度を使用する。すなわち、クラスタリング部４８は、文書間の類似度が文書間類似度データ３２に記憶されている場合、類似度の算出を行わず、記憶された類似度を文書間の類似度として使用する。このように、文書間類似度データ３２に類似度が記憶されている文書間については、記憶された類似度を使用することにより、類似度の算出処理が省略され、処理負荷を軽減することができる。
【００４５】
図７は、クラスタリングを説明するための説明図である。図７の例では、上段に文書Ａ〜Ｆをクラスタリングした一例が示されている。また、図７の例では、下段に文書Ａ〜Ｆを類似する文書の集合間の類似度が高い文書Ａ〜Ｃと文書Ｄ〜Ｆとに分割し、文書Ａ〜Ｃと文書Ｄ〜Ｆをそれぞれ別なプロセッサ１、２によりクラスタリングした一例が示されている。クラスタリングでは、例えば、複数の文書同士を総当りで比較して類似する文書を求める。このため、図７の上段に示すように、文書Ａ〜Ｆをクラスタリングする場合は、文書Ａ〜Ｆの間の類似度を算出し、類似度を記憶するため、クラスタリングの対象とする文書数の増加に伴い処理で使用する記憶容量が増加し、処理時間も増加する。例えば、文書数ｎが多くなるとｎ×ｎで類似度の計算量および記憶容量も増加する。一例として、文書数ｎを１００万個とし、各類似度を記憶する記憶領域のサイズを４バイトとした場合、類似度を記憶する記憶領域は、（１０７×２−１）２×４バイト≒１４．５ＴＢとなる。よって、文書数ｎが多い場合、１つのプロセッサでは文書のクラスタリングを行うことに限界がある。
【００４６】
一方、図７の下段に示すように、文書Ａ〜Ｃと文書Ｄ〜Ｆをそれぞれ別なプロセッサによりクラスタリングした場合は、分割したことによりクラスタリング対象の文書数が減るため、記憶容量を抑制でき、処理時間も抑制できる。また、文書Ａ〜Ｃと文書Ｄ〜Ｆは、それぞれ類似する文書の集合間の類似度が低く、文書間の類似度も低い。このため、文書Ａ〜Ｃと文書Ｄ〜Ｆをクラスタリングする処理部は、互いに算出した類似度を交換することなく、類似した文書のクラスタリングを行うことができる。
【００４７】
クラスタリング部４８は、クラスタリングを実行した他のコンピュータやプロセッサと通信を行ってそれぞれのクラスタリング処理の結果をマージし、文書データ３０に対するクラスタリングの結果としてまとめる。
【００４８】
図８は、文書データに対する処理の流れを模式的に示した図である。生成部４１は、文書データ３０の複数の文書それぞれの特徴を示す特徴情報として索引データ３１を生成する。文書間類似度算出部４２は、生成された索引データ３１に基づき、複数の文書間の類似度を算出し、算出した文書間の類似度を文書間類似度データ３２として格納する。除外文書特定部４３は、文書間類似度データ３２において自文書以外に類似する文書が登録されていない文書を特定し、特定した文書を除外文書データ３３として格納する。集合間類似度算出部４４は、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出し、算出した集合間の類似度を集合間類似度データ３４として格納する。分類部４５は、集合間の類似度の高い文書同士をグループに分類する。分割部４６は、クラスタデータ３５に記憶されたグループ単位で、複数の文書を分散データ３６に分割する。また、分割部４６は、除外文書データ３３に記憶された除外文書を分散データ３６に分割する。このように分散データ３６に分割することにより、類似する文書が別な分散データ３６に分かれることが抑制されるため、それぞれの分散データ３６に対するクラスタリングの並列処理を効率的に行うことができる。また、分割したことによりクラスタリング対象の文書数が減るため、記憶容量、処理時間も抑制されたため、文書に対する効率的なクラスタリングの並列処理を行うことができる。
【００４９】
［具体例］
次に、実施例１に係る文書分割装置１０により文書を分割する具体例を説明する。図９は、文書データに含まれるクラスタリング対象の文書の文書名および文書に含まれる単語の一例を示す図である。図９の例では、クラスタリング対象の文書として文書名「ｄｏｃ０１」〜「ｄｏｃ１１」の１１個の文書が示されており、それぞれの文書名の横に文書に含まれる単語がアルファベットの記号として示されている。図９の例では、文書名ｄｏｃ０１の文書は、単語Ａ〜Ｊを含むことを示す。
【００５０】
生成部４１は、クラスタリング対象の各文書に含まれる各単語がどの文書に含まれるかを示す索引データ３１を生成する。図１０は、索引データの一例を示す図である。図１０の例では、クラスタリング対象の文書に含まれる単語が一覧で示されており、それぞれの単語の横に単語を含む文書の文書名が示されている。図１０の例では、単語Ａは、文書名ｄｏｃ０１、ｄｏｃ０２、ｄｏｃ０３、ｄｏｃ０４、ｄｏｃ０５の各文書に含まれていることを示す。
【００５１】
文書間類似度算出部４２は、索引データ３１に基づき、文書データ３０に記憶された複数の文書間の類似度を算出し、算出した類似度が第１閾値以上である相手文書の文書名および類似度を文書間類似度データ３２として記憶部２１に格納する。なお、第１閾値は０．２としている。図１１は、文書間類似度データの一例を示す図である。図１１の例では、クラスタリング対象の文書の文書名が示されており、それぞれの文書名の横に、類似度が第１閾値以上である相手の文書名と、類似度が、文書名：類似度の形式で類似度が大きい順位に並べ示されている。図１１の例では、文書名ｄｏｃ０１の文書は、文書名ｄｏｃ０１の文書との類似度が１．０であり、文書名ｄｏｃ０２の文書との類似度が０．８であり、文書名ｄｏｃ０３の文書との類似度が０．７であることを示す。また、図１１の例では、文書名ｄｏｃ０１の文書は、文書名ｄｏｃ０４の文書との類似度が０．４であり、文書名ｄｏｃ０５の文書との類似度が０．３であることを示す。
【００５２】
除外文書特定部４３は、文書間類似度データ３２において自文書以外に類似する文書が登録されていない文書を特定し、特定した文書を除外文書データ３３として記憶部２１に格納する。図１２は、除外文書データの一例を示す図である。図１２の例では、図１１に示した文書間類似度データ３２から自文書以外に類似する文書が登録されていない文書名ｄｏｃ１１の文書が除外文書として記憶されている。
【００５３】
集合間類似度算出部４４は、文書間類似度データ３２に基づき、各文書の文書間の類似度が上位４位以内の文書の集合間の類似度を算出し、各文書毎に、相手文書の文書名および集合間の類似度を集合間類似度データ３４として記憶部２１に格納する。図１３は、集合間類似度データの一例を示す図である。図１３の例では、クラスタリング対象の文書の文書名が示されており、それぞれの文書名の横に、相手の文書名と、類似する文書の集合間の類似度が、文書名：類似度の形式で類似度が大きい順位に並べ示されている。図１３の例では、文書名ｄｏｃ０１の文書は、文書名ｄｏｃ０１の文書との類似度が１．００であり、文書名ｄｏｃ０２の文書との類似度が０．９８であり、文書名ｄｏｃ０３の文書との類似度が０．９６であることを示す。また、図１３の例では、文書名ｄｏｃ０１の文書は、文書名ｄｏｃ０４の文書との類似度が０．７６であり、文書名ｄｏｃ０５の文書との類似度が０．４４であることを示す。
【００５４】
分類部４５は、集合間類似度データ３４に基づき、各文書を集合間の類似度が第２閾値以上である文書同士をグループに分類し、分類した各グループの文書をクラスタデータ３５として記憶部２１に格納する。なお、第２閾値は０．７としている。図１４は、クラスタデータの一例を示す図である。図１４の例では、グループ１として文書名ｄｏｃ０８〜ｄｏｃ１０の文書がクラスタとされ、グループ２として文書名ｄｏｃ０６、ｄｏｃ０７の文書がクラスタとされ、グループ３として文書名ｄｏｃ０１〜ｄｏｃ０５の文書がクラスタとされていることを示す。
【００５５】
分割部４６は、分類部４５により分類されたグループを文書数の多い順に並べ、文書数の多い順に各グループを順次、文書数が最も少ない分散データ３６にグループ単位で文書を分割する。また、分割部４６は、除外文書データ３３に記憶された除外文書も文書数が最も少ない分散データ３６に分割する。図１５は、分散データの一例を示す図である。図１５は、文書を２つの分散データ３６Ａ、３６Ｂに分割した例を示している。図１５の例では、グループ３の文書名ｄｏｃ０１〜ｄｏｃ０５の文書と、グループ２の文書名ｄｏｃ０６、ｄｏｃ０７の文書が分散データ３６Ａとして分割されていることを示す。また、図１５の例では、グループ１の文書名ｄｏｃ０８〜ｄｏｃ１０の文書と、文書名ｄｏｃ１１の除外文書が分散データ３６Ｂとして分割されていることを示す。
【００５６】
このように文書データ３０を分散データ３６Ａ、３６Ｂに分割することにより文書に対する効率的なクラスタリングの並列処理を実行させることができる。
【００５７】
［処理の流れ］
次に、本実施例に係る文書分割装置１０によりクラスタリング対象の複数の文書を分割する分割処理の流れを説明する。図１６は、分割処理の手順を示すフローチャートである。この分割処理は、記憶部２１に文書データ３０が格納された後に分割開始を指示する所定操作が行われたタイミングで実行される。
【００５８】
図１６に示すように、生成部４１は、文書の特徴を示す特徴情報として、文書データ３０に示される各文書に含まれる各単語がどの文書に含まれるかを示す索引データ３１を生成する索引生成処理を実行する（ステップＳ１０）。文書間類似度算出部４２は、生成された索引データ３１に基づき、文書データ３０に記憶された複数の文書間の類似度を算出する文書間類似度算出処理を実行する（ステップＳ１１）。除外文書特定部４３は、何れの文書とも類似していない除外文書の特定する除外文書特定処理を実行する（ステップＳ１２）。文書間類似度算出部４２は、文書間類似度算出処理により算出された比較元文書、相手文書、類似度の組を、比較元文書毎に、[文書名，類似度]の形式で類似度が大きい順位に並べ文書間類似度データ３２として記憶部２１に格納する（ステップＳ１３）。集合間類似度算出部４４は、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出する集合間類似度算出処理を実行する（ステップＳ１４）。分類部４５は、文書データ３０に記憶された各文書を集合間の類似度の高い文書同士をグループに分類する分類処理を実行する（ステップＳ１５）。分割部４６は、各文書を分散処理させる分散データに分割する分割処理を実行し（ステップＳ１６）、処理を終了する。
【００５９】
次に、本実施例に係る索引生成処理の流れについて説明する。図１７は、索引生成処理の手順を示すフローチャートである。この索引生成処理は、図１６に示す分割処理のステップＳ１０から呼び出されて実行される。
【００６０】
図１７に示すように、生成部４１は、単語および文書名を記憶するための記憶領域を初期化する（ステップＳ２０）。生成部４１は、文書データ３０に示される複数の文書の最初の文書に処理対象であることを示すポインタＡをセットする（ステップＳ２１）。生成部４１は、ポインタＡが示す文書から単語を全て取り出す（ステップＳ２２）。生成部４１は、取り出した単語から重複する単語を１つのみ残して消去し、それぞれの単語を一意にする（ステップＳ２３）。生成部４１は、取り出した各単語にポインタＡが示す文書の文書名を対応させて登録する（ステップＳ２４）。生成部４１は、ポインタＡを次の文書に進める（ステップＳ２５）。生成部４１は、ポインタＡが示す文書があるか否か判定する（ステップＳ２６）。ポインタＡが示す文書がある場合（ステップＳ２６肯定）、上述のステップＳ２２へ戻り、処理を実行する。
【００６１】
一方、ポインタＡが示す文書がない場合（ステップＳ２６否定）、生成部４１は、各文書から取り出した単語および文書名を単語の文字コード順にソートする（ステップＳ２７）。生成部４１は、文字コード順に並んだ単語および文書名を順に変換して、それぞれ各単語がどの文書に含まれるかを示す索引データ３１を生成し（ステップＳ２８）、呼び出した元に戻る。
【００６２】
次に、本実施例に係る文書間類似度算出処理の流れについて説明する。図１８は、文書間類似度算出処理の手順を示すフローチャートである。この文書間類似度算出処理は、図１６に示す分割処理のステップＳ１１から呼び出されて実行される。
【００６３】
図１８に示すように、文書間類似度算出部４２は、類似度の第１閾値をセットする（ステップＳ３０）。文書間類似度算出部４２は、文書データ３０に示される複数の文書の最初の文書に処理対象であることを示すポインタＡをセットする（ステップＳ３１）。文書間類似度算出部４２は、ポインタＡが示す文書から単語を全て取り出す（ステップＳ３２）。文書間類似度算出部４２は、索引データ３１に基づき、文書データ３０に記憶された自文書を含む複数の文書間の類似度を算出する（ステップＳ３３）。文書間類似度算出部４２は、算出された類似度が所定の第１閾値以上である相手文書の文書名および類似度を文書間類似度データ３２として記憶部２１に格納する（ステップＳ３４）。文書間類似度算出部４２は、ポインタＡを次の文書に進める（ステップＳ３５）。文書間類似度算出部４２は、ポインタＡが示す文書があるか否か判定する（ステップＳ３６）。ポインタＡが示す文書がある場合（ステップＳ３６肯定）、上述のステップＳ３２へ戻り、処理を実行する。一方、ポインタＡが示す文書がない場合（ステップＳ３６否定）、呼び出した元に戻る。
【００６４】
次に、本実施例に係る除外文書特定処理の流れについて説明する。図１９は、除外文書特定処理の手順を示すフローチャートである。この除外文書特定処理は、図１６に示す分割処理のステップＳ１２から呼び出されて実行される。
【００６５】
図１９に示すように、除外文書特定部４３は、文書データ３０に示される複数の文書の最初の文書に処理対象であることを示すポインタＡをセットする（ステップＳ４０）。除外文書特定部４３は、除外文書データ３３を初期化する（ステップＳ４１）。除外文書特定部４３は、ポインタＡが示す文書が自文書以外に類似度が第１閾値以上の文書がない文書であるか否かを判定する（ステップＳ４２）。自文書以外に類似度が第１閾値以上の文書がない場合（ステップＳ４２肯定）、除外文書特定部４３は、ポインタＡが示す文書を除外文書データ３３に登録する（ステップＳ４３）。一方、自文書以外に類似度が第１閾値以上の文書がある場合（ステップＳ４２否定）、後述するステップＳ４４へ移行する。
【００６６】
除外文書特定部４３は、ポインタＡを次の文書に進める（ステップＳ４４）。除外文書特定部４３は、ポインタＡが示す文書があるか否か判定する（ステップＳ４５）。ポインタＡが示す文書がある場合（ステップＳ４５肯定）、上述のステップＳ４２へ戻り、処理を実行する。一方、ポインタＡが示す文書がない場合（ステップＳ４５否定）、呼び出した元に戻る。
【００６７】
次に、本実施例に係る集合間類似度算出処理の流れについて説明する。図２０は、集合間類似度算出処理を示すフローチャートである。この集合間類似度算出処理は、図１６に示す分割処理のステップＳ１４から呼び出されて実行される。
【００６８】
図２０に示すように、集合間類似度算出部４４は、文書データ３０に示される複数の文書の最初の文書に処理対象であることを示すポインタＡをセットする（ステップＳ５０）。集合間類似度算出部４４は、ポインタＢをポインタＡの次の文書にセットする（ステップＳ５１）。集合間類似度算出部４４は、ポインタＡが示す文書とポインタＢが示す文書それぞれの類似度が上位４位以内の文書の集合間の類似度を算出する（ステップＳ５２）。集合間類似度算出部４４は、算出した類似度をポインタＡが示す文書とポインタＢが示す文書の類似する文書の集合間の類似度として記憶する（ステップＳ５３）。
【００６９】
集合間類似度算出部４４は、ポインタＢを次の文書に進める（ステップＳ５４）。集合間類似度算出部４４は、ポインタＢが示す文書があるか否か判定する（ステップＳ５５）。ポインタＢが示す文書がある場合（ステップＳ５５肯定）、上述のステップＳ５２へ戻り、処理を実行する。一方、ポインタＢが示す文書がない場合（ステップＳ５５否定）、集合間類似度算出部４４は、ポインタＡを次の文書に進める（ステップＳ５６）。集合間類似度算出部４４は、ポインタＡが示す文書があるか否か判定する（ステップＳ５７）。ポインタＡが示す文書がある場合（ステップＳ５７肯定）、上述のステップＳ５１へ戻り、処理を実行する。一方、ポインタＡが示す文書がない場合（ステップＳ５７否定）、呼び出した元に戻る。
【００７０】
次に、本実施例に係る分類処理の流れについて説明する。図２１は、分類処理を示すフローチャートである。この分類処理は、図１６に示す分割処理のステップＳ１５から呼び出されて実行される。
【００７１】
図２１に示すように、分類部４５は、集合間類似度データ３４に記憶された各文書を、文書の集合間の類似度の大きい順に並べる（ステップＳ６０）。分類部４５は、文書の集合間の類似度の大きい順に、集合間類似度データ３４に記憶された最初の文書に処理対象であることを示すポインタＡをセットする（ステップＳ６１）。分類部４５は、ポインタＡが示す文書をグループに分類する（ステップＳ６２）。分類部４５は、ポインタＡを次の文書に進める（ステップＳ６３）。分類部４５は、ポインタＡが示す文書があるか否か判定する（ステップＳ６４）。ポインタＡが示す文書がある場合（ステップＳ６４肯定）、後述するステップＳ６５へ移行する。一方、ポインタＡが示す文書がない場合（ステップＳ６４否定）、後述するステップＳ７０へ移行する。
【００７２】
分類部４５は、ポインタＡが示す文書と集合間の類似度が第２閾値以上である文書が既にグループに分けられた文書に存在するか否か判定する（ステップＳ６５）。集合間の類似度が第２閾値以上である文書が存在する場合（ステップＳ６５肯定）、分類部４５は、類似度が第２閾値以上である文書が存在するグループにポインタＡが示す文書を追加し（ステップＳ６６）、ステップＳ６３へ移行する。一方、集合間の類似度が第２閾値以上である文書が存在しない場合（ステップＳ６５否定）、分類部４５は、ポインタＡが示す文書に集合間の類似度が第２閾値以上のものがあるか否か判定する（ステップＳ６７）。集合間の類似度が第２閾値以上のものがある場合（ステップＳ６７肯定）、分類部４５は、ポインタＡが示す文書を新たなグループに分類し（ステップＳ６８）、ステップＳ６３へ移行する。一方、集合間の類似度が第２閾値以上のものがない場合（ステップＳ６７否定）、分類部４５は、ポインタＡが示す文書をその他として記憶し（ステップＳ６９）、ステップＳ６３へ移行する。
【００７３】
一方、分類部４５は、その他として記憶した最初の文書に処理対象であることを示すポインタＢをセットする（ステップＳ７０）。分類部４５は、ポインタＢが示す文書において文書間の類似度が最も大きい文書を含むグループにポインタＢが示す文書を追加する（ステップＳ７１）。分類部４５は、ポインタＢを次の文書に進める（ステップＳ７２）。分類部４５は、ポインタＢが示す文書があるか否か判定する（ステップＳ７３）。ポインタＢが示す文書がある場合（ステップＳ７３肯定）、上述のステップＳ７１へ戻り、処理を実行する。一方、ポインタＢが示す文書がない場合（ステップＳ７３否定）、呼び出した元に戻る。
【００７４】
次に、本実施例に係る分割処理の流れについて説明する。図２２は、分割処理を示すフローチャートである。この分割処理は、図１６に示す分割処理のステップＳ１６から呼び出されて実行される。
【００７５】
図２２に示すように、分割部４６は、文書をｎ個に分割する場合、分割文書を格納するｎ個の領域を準備する（ステップＳ８０）。分割部４６は、分類処理により分類されたグループを文書数の多い順に並べる（ステップＳ８１）。分割部４６は、文書数の多い順に、最初のグループに処理対象であることを示すポインタＡをセットする（ステップＳ８２）。分割部４６は、ｎ個の領域に格納された文書数を比較し、最も文書数が少ない領域にポインタＡが示すグループの文書を格納する（ステップＳ８３）。分割部４６は、ポインタＡを次のグループに進める（ステップＳ８４）。分割部４６は、ポインタＡが示すグループがあるか否か判定する（ステップＳ８５）。ポインタＡが示すグループがある場合（ステップＳ８５肯定）、ステップＳ８３へ戻り、処理を実行する。
【００７６】
一方、ポインタＡが示すグループがない場合（ステップＳ８５否定）、分割部４６は、除外文書データ３３に記憶された除外文書に処理対象であることを示すポインタＢをセットする（ステップＳ８６）。分割部４６は、ｎ個の領域に格納された文書数を比較し、最も文書数が少ない領域にポインタＢが示す文書を格納する（ステップＳ８７）。分割部４６は、ポインタＢを次の除外文書に進める（ステップＳ８８）。分割部４６は、ポインタＢが示す文書があるか否か判定する（ステップＳ８９）。ポインタＢが示す文書がある場合（ステップＳ８９肯定）、ステップＳ８７へ戻り、処理を実行する。一方、ポインタＢが示す文書がない場合（ステップＳ８９否定）、分割部４６は、ｎ個の領域に格納された文書をそれぞれ分散データ３６として記憶部２１へ格納し（ステップＳ９０）、呼び出した元に戻る。
【００７７】
出力部４７は、このように上述した分割処理により分割された分散データ３６をクラスタリング対象のデータとしてクラスタリングを実行する複数のコンピュータやプロセッサに対して出力する。
【００７８】
次に、本実施例に係る文書分割装置１０によりクラスタリング処理の流れを説明する。図２３は、クラスタリング処理の手順を示すフローチャートである。このクラスタリング処理は、上述した分割処理の後に続けて実行されてもよい。また、クラスタリングを指示する所定操作が行われたタイミングで実行されてもよい。
【００７９】
図２３に示すように、クラスタリング部４８は、処理対象とされた分散データ３６に含まれる文書間の類似度を算出する（ステップＳ１００）。クラスタリング部４８は、算出した文書間の類似度に基づき、類似する文書をまとめるクラスタリングを行う（ステップＳ１０１）。クラスタリング部４８は、クラスタリングを実行した他のプロセッサとクラスタリングの結果をマージし（ステップＳ１０２）、処理を終了する。
【００８０】
［実施例１の効果］
本実施例に係る文書分割装置１０は、文書データ３０の複数の文書それぞれの特徴を示す特徴情報として索引データ３１を生成する。本実施例に係る文書分割装置１０は、生成された索引データ３１に基づき、複数の文書間の類似度を算出する。本実施例に係る文書分割装置１０は、各文書の文書間の類似度が上位の所定位以内の文書の集合間の類似度を算出する。そして、本実施例に係る文書分割装置１０は、集合間の類似度の高い文書同士をグループに分類する。本実施例に係る文書分割装置１０は、分類されたグループ単位で複数の文書を分散処理させる分散データ３６に分割する。これにより、本実施例に係る文書分割装置１０によれば、文書に対するクラスタリングの並列処理を効率的に行うことができる。
【００８１】
また、本実施例に係る文書分割装置１０は、各文書を、それぞれ当該文書との類似度が上位の所定位以内の文書を要素とし、類似度を要素の値としたベクトルと見なして、ベクトル間の類似度から文書の集合間の類似度を算出する。これにより、本実施例に係る文書分割装置１０によれば、類似する文書の集合間の類似度が高い文書を同じグループにまとめることができ、類似する文書が別の分散データ３６に分割されることを抑制できる。
【００８２】
また、本実施例に係る文書分割装置１０は、分割された分散データ３６および当該分散データ３６に含まれる文書にかかる文書間の類似度をそれぞれクラスタリングを実行する処理部へ出力する。これにより、本実施例に係る文書分割装置１０によれば、文書間の類似度の算出処理を軽減させることができる。
【００８３】
また、本実施例に係る文書分割装置１０は、文書数が同等となるように複数の文書を分散データ３６に分割する。これにより、本実施例に係る文書分割装置１０によれば、各分散データ３６のクラスタリングを複数のコンピュータやプロセッサにより並列処理させた場合でも、特定のコンピュータやプロセッサの負荷が偏ることを抑制できる。
【実施例２】
【００８４】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【００８５】
例えば、上記の実施例では、文書数が同等となるように複数の文書を分散データ３６に分割する場合について説明したが、開示の装置はこれに限定されない。例えば、文書数の多い順に各グループの文書を分散データ３６に順番に格納してもよい。また、除外文書データ３３に記憶された除外文書を特定の分散データ３６に格納してもよい。
【００８６】
また、上記の実施例では、クラスタリング部４８によりいずれかの分散データ３６のクラスタリングを実行する場合について説明したが、開示の装置はこれに限定されない。例えば、分散データ３６を全て外部のコンピュータやプロセッサでクラスタリングを実行させるものとしてもよい。
【００８７】
また、上記の実施例では、各文書からそれぞれ単語を抽出して各文書間の類似度を算出する場合について説明したが、開示の装置はこれに限定されない。例えば、文書が画像を含む場合、画像間の類似度も加えて文書間の類似度を算出してもよい。
【００８８】
また、上記の実施例では、類似する文書が自文書以外にない文書を除外文書として除外文書データ３３に記憶した場合について説明したが、開示の装置はこれに限定されない。例えば、類似する文書が自文書以外にない文書をそれぞれ単独でグループとしてもよい。これにより、グループ単位で文書を分散データ３６に分割することにより、除外文書も分散データ３６に分割することができる。
【００８９】
また、上記の実施例では、文書数が同等となるように文書データ３０に含まれる複数の文書を分散データ３６に分割する場合について説明したが、開示の装置はこれに限定されない。例えば、クラスタリングを実行するコンピュータやプロセッサなどの各処理部の処理能力を示す情報を取得し、各処理部の処理能力に応じた比率で文書データ３０に含まれる複数の文書を分散データ３６に分割してもよい。処理能力を示す情報としては、例えば、ＣＰＵのクロック数やメモリ量、処理性能を測定するソフトウェアにより測定された性能を示す数値、管理者等が処理能力に応じて定めた数値などが挙げられる。これにより、クラスタリングを実行する各処理部に、処理能力に応じた文書数の分散データ３６が割り当てられるため、特定の処理部の負荷が過剰に高くなることを抑制できる。
【００９０】
［分散および統合］
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、文書分割装置１０の登録部４０、生成部４１、文書間類似度算出部４２、除外文書特定部４３、集合間類似度算出部４４、分類部４５、分割部４６、出力部４７、クラスタリング部４８の各処理部が適宜統合されてもよい。また、各処理部の処理が適宜複数の処理部の処理に分離されてもよい。また、各処理部を別の装置がそれぞれ有し、ネットワーク接続されて協働することで、上記の文書分割装置１０の機能を実現するようにしてもよい。
【００９１】
［分割プログラム］
また、上記の実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図２４を用いて、上記の実施例と同様の機能を有する分割プログラムを実行するコンピュータの一例について説明する。
【００９２】
図２４は、分割プログラムを実行するコンピュータの一例について説明するための図である。図２４に示すように、コンピュータ２００は、操作部２１０と、ディスプレイ２２０と、通信部２３０とを有する。さらに、このコンピュータ２００は、ＣＰＵ２５０と、ＲＯＭ２６０と、ＨＤＤ２７０と、ＲＡＭ２８０と有する。これら２１０〜２８０の各部はバス２４０を介して接続される。
【００９３】
ＨＤＤ２７０には、登録部４０、生成部４１、文書間類似度算出部４２、除外文書特定部４３、集合間類似度算出部４４、分類部４５、分割部４６、出力部４７、クラスタリング部４８と同様の機能を発揮する分割プログラム２７０ａが予め記憶される。この分割プログラム２７０ａについては、実施例１で示した各構成要素と同様、適宜統合又は分離しても良い。すなわち、ＨＤＤ２７０に格納される各データは、常に全てのデータがＨＤＤ２７０に格納される必要はなく、処理に必要なデータのみがＨＤＤ２７０に格納されれば良い。
【００９４】
そして、ＣＰＵ２５０が、分割プログラム２７０ａをＨＤＤ２７０から読み出してＲＡＭ２８０に展開する。これによって、図２４に示すように、分割プログラム２７０ａは、分割プロセス２８０ａとして機能する。この分割プロセス２８０ａは、ＨＤＤ２７０から読み出した各種データを適宜ＲＡＭ２８０上の自身に割り当てられた領域に展開し、この展開した各種データに基づいて各種処理を実行する。分割プロセス２８０ａは、登録部４０、生成部４１、文書間類似度算出部４２、除外文書特定部４３、集合間類似度算出部４４、分類部４５、分割部４６、出力部４７、クラスタリング部４８にて実行される処理、例えば図１６〜図２３に示す処理を含む。すなわち、分割プロセス２８０ａは、登録部４０、生成部４１、文書間類似度算出部４２、除外文書特定部４３、集合間類似度算出部４４、分類部４５、分割部４６、出力部４７、クラスタリング部４８と同様の動作を実行する。なお、ＣＰＵ２５０上で仮想的に実現される各処理部は、常に全ての処理部がＣＰＵ２５０上で動作する必要はなく、処理に必要な処理部のみが仮想的に実現されれば良い。
【００９５】
なお、上記の分割プログラム２７０ａについては、必ずしも最初からＨＤＤ２７０やＲＯＭ２６０に記憶させておく必要はない。例えば、コンピュータ２００に挿入されるフレキシブルディスク、いわゆるＦＤ、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させる。そして、コンピュータ２００がこれらの可搬用の物理媒体から各プログラムを取得して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ２００に接続される他のコンピュータまたはサーバ装置などに各プログラムを記憶させておき、コンピュータ２００がこれらから各プログラムを取得して実行するようにしてもよい。
【符号の説明】
【００９６】
１０    文書分割装置
２１    記憶部
２２    制御部
３０    文書データ
３１    索引データ
３２    文書間類似度データ
３３    除外文書データ
３４    集合間類似度データ
３５    クラスタデータ
３６    分散データ
４１    生成部
４２    文書間類似度算出部
４３    除外文書特定部
４４    集合間類似度算出部
４５    分類部
４６    分割部
４７    出力部
４８    クラスタリング部
【図１】
2013196212.tif 000003
【図２】
2013196212.tif 000004
【図３】
2013196212.tif 000005
【図４】
2013196212.tif 000006
【図５】
2013196212.tif 000007
【図６】
2013196212.tif 000008
【図７】
2013196212.tif 000009
【図８】
2013196212.tif 000010
【図９】
2013196212.tif 000011
【図１０】
2013196212.tif 000012
【図１１】
2013196212.tif 000013
【図１２】
2013196212.tif 000014
【図１３】
2013196212.tif 000015
【図１４】
2013196212.tif 000016
【図１５】
2013196212.tif 000017
【図１６】
2013196212.tif 000018
【図１７】
2013196212.tif 000019
【図１８】
2013196212.tif 000020
【図１９】
2013196212.tif 000021
【図２０】
2013196212.tif 000022
【図２１】
2013196212.tif 000023
【図２２】
2013196212.tif 000024
【図２３】
2013196212.tif 000025
【図２４】
2013196212.tif 000026