(57)【特許請求の範囲】
【請求項１】
記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置のデータ分類方法であって、
前記データ処理装置は、
前記記憶装置に記憶された文書データを読み出し、文書データ毎に該文書データに含まれるキーワードを抽出し、キーワード毎に該キーワードを含む文書データの文書識別情報を対応付けたリストを作成するリスト作成ステップと、
前記リストに対し、文書識別情報毎に射影を実行して、同一のキーワードを有する他の文書識別情報を残し、残った文書識別情報の組み合わせの発生回数を判定する判定ステップと、
前記判定ステップの判定結果に基づいて、各文書データ間の類似度を算出する算出ステップと、
を含んだことを特徴とするデータ分類方法。
【請求項２】
前記判定ステップは、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを特徴とする請求項１に記載のデータ分類方法。 
【請求項３】
前記類似度の値が最大となる各文書データの組合せを求めることにより、文書データを分類する分類ステップを更に含み、当該分類ステップは、利用者に指定される分類数と文書データの分類数とが等しくなるように、前記文書データを分類することを特徴とする請求項１または２に記載のデータ分類方法。 
【請求項４】
記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置であって、
前記記憶装置に記憶された文書データを読み出し、文書データ毎に該文書データに含まれるキーワードを抽出し、キーワード毎に該キーワードを含む文書データの文書識別情報を対応付けたリストを作成するリスト作成手段と、
前記リストに対し、文書識別情報毎に射影を実行して、同一のキーワードを有する他の文書識別情報を残し、残った文書識別情報の組み合わせの発生回数を判定する判定手段と、
前記判定手段の判定結果に基づいて、各文書データ間の類似度を算出する算出手段と、
を備えたことを特徴とするデータ処理装置。 
【請求項５】
前記判定手段は、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを特徴とする請求項４に記載のデータ処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置およびそのデータ分類方法に関するものである。
【背景技術】
【０００２】
従来、サーバ装置およびクライアント装置から構成される文書検索システムでは、例えば、サーバ装置がクライアント装置から検索キーワードを取得した場合に、データベースに記憶された複数の文書データの中から検索キーワードに対応する文書データを検索し、検索結果をクライアント装置に提供している。
【０００３】
また、近年では、データベースに記憶される文書データの数が飛躍的に増加しており、検索キーワードに基づいて検索される文書データの数が膨大な数となってしまうため、利用者が検索結果となる文書データを参照しやすいように、ベクタースペースモデル（例えば、非特許文献１参照）等の技術を利用して、各文書データの類似度を計算し、類似する文書データ毎に文書データを分類している。
【０００４】
例えば、非特許文献１に記載されているベクタースペースモデルでは、文書データ毎に複数のキーワードの存在有無をベクトルとして変換し、変換した全てのベクトルの組合せにおいて類似度を計算している。
【０００５】
【非特許文献１】G.Sallon,A,Wong  and  C.S.Yang  Cornell  University"A  Vector  Space  Model  for  Automatic  Indexing",Communications  of  the  ACM  November1975  Volume18  Number11
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来の技術のように、ベクタースペースモデルを利用して、文書データの類似度を算出すると、全ての文書データの組み合わせの間で計算が行われるため、文書データ数の二乗の計算量が発生し、類似度計算にかかる処理時間が長くなってしまうという問題があった。
【０００７】
すなわち、文書データの類似度を効率よく算出することで、類似度計算にかかる処理時間を短縮することが極めて重要な課題となっている。
【０００８】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、文書データの類似度を効率よく算出して、類似度計算にかかる処理時間を短縮することが出来るデータ分類方法およびデータ処理装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するため、このデータ分類方法は、記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置のデータ分類方法であって、前記データ処理装置は、前記記憶装置に記憶された文書データを読み出し、各文書データ中のキーワードと当該キーワードを含む文書データとを対応付けたリストを作成するリスト作成ステップと、前記リストに対してシーケンシャルパターン抽出を実行し、出現した文書データの組み合わせの発生回数を判定する判定ステップと、前記判定ステップの判定結果に基づいて、各文書データ間の類似度を算出する算出ステップと、を含んだことを要件とする。
【００１０】
また、このデータ分類方法は、上記のデータ分類方法において、前記判定ステップは、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを要件とする。
【００１１】
また、このデータ分類方法は、上記のデータ分類方法において、前記類似度の値が最大となる各文書データの組合せを求めることにより、文書データを分類する分類ステップを更に含み、当該分類ステップは、利用者に指定される分類数と文書データの分類数とが等しくなるように、前記文書データを分類すること要件とする。
【００１２】
また、このデータ処理装置は、記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置であって、前記記憶装置に記憶された文書データを読み出し、各文書データ中のキーワードと当該キーワードを含む文書データとを対応付けたリストを作成するリスト作成手段と、前記リストに対してシーケンシャルパターン抽出を実行し、出現した文書データの組み合わせの発生回数を判定する判定手段と、前記判定手段の判定結果に基づいて、各文書データ間の類似度を算出する算出手段と、を備えたことを要件とする。
【００１３】
また、このデータ処理装置は、上記データ処理装置において、前記判定手段は、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを要件とする。
【発明の効果】
【００１４】
このデータ分類方法によれば、各文書データ中のキーワードと当該キーワードに対応する文書データとを対応付けたリストを作成し、リストに対してシーケンシャルパターン抽出を実行する。そして、シーケンシャルパターン抽出を実行した結果出現する文書データの組み合わせの発生回数を判定し、判定結果に基づいて、各文書データ間の類似度を計算するので、文書データの類似度を効率よく算出でき、類似度計算にかかる処理時間を短縮することが出来る。
【００１５】
また、このデータ分類方法によれば、シーケンシャルパターン抽出において、長さ２のパターンの発生回数のみを判定することにより、各文書データ間の類似度を計算するので、装置にかかる処理負荷を大幅に軽減させることが出来る。
【００１６】
また、このデータ分類方法によれば、利用者に指定される分類数と文書データの分類数とが等しくなるように、文書データを分類するので、ユーザの好みに合った情報提供を行うことが可能となる。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この発明に係るデータ分類方法およびデータ処理装置の好適な実施の形態を詳細に説明する。
【実施例】
【００１８】
まず、本実施例にかかるデータ処理装置の概要および特徴について説明する。本実施例にかかるデータ処理装置は、各文書データ中のキーワードと当該キーワードを含む文書データとを対応付けた転置インデックスリストを作成し、転置インデックスリストに対してシーケンシャルパターン抽出を実行する。
【００１９】
そして、データ処理装置は、シーケンシャルパターン抽出を実行した結果出現する文書データの組み合わせの発生回数を判定（特に、本実施例では、シーケンシャルパターン抽出において、長さ２のパターンの発生回数のみを判定）し、判定結果に基づいて、各文書データ間の類似度を計算する。
【００２０】
このように、本実施例にかかるデータ処理装置は、転置インデックスリストに対して、シーケンシャルパターン抽出を実行することで、各文書データ間の類似度を算出するので、文書データの類似度を効率よく算出でき、類似度計算にかかる処理時間を短縮することが出来る。
【００２１】
次に、本実施例にかかる検索システムの構成について説明する。図１は、検索システムの構成を示す図である。同図に示すように、この検索システムは、端末装置５０およびデータ処理装置１００から構成され、端末装置５０およびデータ処理装置１００は、ネットワーク１０を介して接続されている。
【００２２】
このうち、端末装置５０は、入力装置等を介して、利用者から検索キーワードを受け付けた場合に、検索キーワードをデータ処理装置１００に送信する装置である。そして、端末装置５０は、検索結果をデータ処理装置１００から取得した場合に、取得した検索結果をディスプレイに表示させる。
【００２３】
データ処理装置１００は、端末装置５０から検索キーワードを取得した場合に、検索キーワードに対応する文書データを記憶装置から検索し、上記のシーケンシャルパターン抽出を実行することで、文書データを分類し、分類した文書データを検索結果として端末装置５０に出力する装置である。
【００２４】
ここで、図１に示したデータ処理装置１００の構成について詳細に説明する。図２は、本実施例にかかるデータ処理装置１００の構成を示す機能ブロック図である。図２に示すように、このデータ処理装置１００は、入力部１１０と、出力部１２０と、通信制御ＩＦ部１３０と、入出力制御ＩＦ部１４０と、記憶部１５０と、制御部１６０とを備えて構成される。
【００２５】
このうち、入力部１１０は、各種の情報を入力する入力手段であり、キーボードやマウス、マイクなどによって構成される。また、出力部１２０は、各種の情報を出力する出力手段であり、モニタ（若しくはディスプレイ、タッチパネル）やスピーカなどによって構成される。
【００２６】
通信制御ＩＦ部１３０は、主に端末装置５０（図１参照）との間における通信を制御する手段である。また、入出力制御ＩＦ部１４０は、入力部１１０、出力部１２０、通信制御ＩＦ部１３０、記憶部１５０、制御部１６０によるデータの入出力を制御する手段である。
【００２７】
記憶部１５０は、制御部１６０による各種情報処理に必要なデータおよびプログラムを記憶する記憶手段であり、特に本発明に密接に関連するものとしては、図２に示すように、文書管理データ１５０ａと、単語インデックス１５０ｂと、単語ＩＤ管理テーブル１５０ｃと、転置インデックス１５０ｄと、類似度テーブル１５０ｅと、クラスタテーブル１５０ｆとを備える。
【００２８】
文書管理データ１５０ａは、各種の文書データを記憶するデータである。図３は、文書管理データ１５０ａのデータ構造の一例を示す図である。同図に示すように、この文書管理データ１５０ａは、各文書データを識別する文書ＩＤと、文書データとを対応付けて記憶している。
【００２９】
単語インデックス１５０ｂは、文書ＩＤと、文書ＩＤによって識別される文書データに含まれる各単語ＩＤ（単語ＩＤ列）とを対応付けて記憶するデータである。図４は、単語インデックス１５０ｂのデータ構造の一例を示す図である。
【００３０】
同図に示すように、この単語インデックス１５０ｂは、文書ＩＤと単語ＩＤ列とを対応付けて記憶している。例えば、図４の１段目には、文書ＩＤ「Ａ」によって識別される文書データに、単語ＩＤ「１，２，３」によって識別される単語が含まれている旨の情報が登録されている。
【００３１】
単語ＩＤ管理テーブル１５０ｃは、単語ＩＤと、この単語ＩＤに対応する単語とを対応付けて記憶するテーブルである。図５は、単語ＩＤ管理テーブル１５０ｃのデータ構造の一例を示す図である。
【００３２】
転置インデックス１５０ｄは、単語ＩＤと、この単語ＩＤの単語を含む文書データの文書ＩＤとを対応付けて記憶するデータである。図６は、転置インデックス１５０ｄのデータ構造の一例を示す図である。例えば、図６の１段目には、単語ＩＤ「１」によって識別される単語を有している文書データは、文書ＩＤ「Ａ」によって識別される文書データである旨が登録されている。
【００３３】
類似度テーブル１５０ｅは、各文書データ間の類似度を記憶するテーブルである。図７は、類似度テーブル１５０ｅのデータ構造の一例を示す図である。図７に示す「Ａ」〜「Ｅ」は、文書ＩＤであり、各数値は、類似度である。図７を参照すると、例えば、文書ＩＤ「Ａ」の文書データと、文書ＩＤ「Ｂ」の文書データとの類似度が「２」である旨の情報が登録されている。
【００３４】
クラスタテーブル１５０ｆは、各文書データの類似度に基づいて文書データを分類する場合に利用するデータである。図８は、クラスタテーブル１５０ｆのデータ構造の一例を示す図である。図８に示す「Ａ」〜「Ｅ」は、文書ＩＤであり、各数値は、類似度である。なお、クラスタテーブル１５０ｆを基にして、文書データを分類する処理は後述する。
【００３５】
制御部１６０は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する制御手段であり、特に本発明に密接に関連するものとしては、文書データ検索部１６０ａと、転置インデックス作成部１６０ｂと、類似度テーブル作成部１６０ｃと、クラスタリング処理部１６０ｄとを備える。
【００３６】
このうち、文書データ検索部１６０ａは、端末装置５０から検索キーワードを受け付けた場合に、受け付けた検索キーワードを含む文書データを文書管理データ１５０ａから検索する手段である。文書データ検索部１６０ａは、検索した文書データの文書ＩＤを転置インデックス作成部１６０ｂに出力する。
【００３７】
転置インデックス作成部１６０ｂは、文書データ検索部１６０ａから文書ＩＤを取得し、取得した文書ＩＤに対応する転置インデックス１５０ｄを作成する手段である。具体的に、この転置インデックス作成部１６０ｂは、単語インデックス１５０ｂ、単語ＩＤ管理テーブル１５０ｃを作成する単語インデックス作成処理と、転置インデックス１５０ｄを作成する転置インデックス作成処理を実行する。以下において、転置インデックス作成部１６０ｂが実行する単語インデックス作成処理、転置インデックス作成処理を順に説明する。
【００３８】
まず、転置インデックス作成部１６０ｂが実行する単語インデックス作成処理について説明する。転置インデックス作成部１６０ｂは、文書データ検索部１６０ａから文書ＩＤを取得した場合に、文書ＩＤに対応する文書データを文書管理データ１５０ａから取得し、取得した各文書データ（以下、文書データ群）に対して形態素解析を実行する。
【００３９】
そして、転置インデックス作成部１６０ｂは、文書データ群に対して形態素解析を実行した結果得られる単語に単語ＩＤを割り振り、単語ＩＤとこの単語ＩＤに対応する単語とを対応付けて単語ＩＤ管理テーブル１５０ｃに登録する。
【００４０】
転置インデックス作成部１６０ｂは、単語ＩＤ管理テーブル１５０ｃと、文書データ群とを比較することにより、単語ＩＤ管理テーブル１５０ｃの単語が含まれる文書データを判定し、単語インデックス１５０ｂ（図４参照）を作成する。
【００４１】
続いて、転置インデックス作成部１６０ｂが実行する転置インデックス作成処理について説明する。転置インデックス作成部１６０ｂは、単語インデックス１５０ｂを取得し、単語ＩＤ毎に、単語ＩＤを有する文書データの文書ＩＤを判定することにより、転置インデックス１５０ｄ（図６参照）を作成する。
【００４２】
類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄに対してシーケンシャルパターン抽出を実行し、シーケンシャルパターン抽出を実行した結果出現する文書データ（文書ＩＤ）の組合せの発生回数を判定（特に、本実施例では、シーケンシャルパターン抽出において、長さ２のパターンの発生回数のみを判定）し、判定結果に基づいて、類似度テーブル１５０ｅを作成する手段である。
【００４３】
以下において、類似度テーブル作成部１６０ｃの処理を具体的に説明する。まず、類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄからアイテム数１の多頻度系列となる文書ＩＤ（換言すれば、転置インデックス１５０ｄに含まれる各文書ＩＤ）を抽出する。例えば、図６に示した転置インデックス１５０ｄからアイテム数１の多頻度系列となる文書ＩＤ（以下、系列文書ＩＤと表記する）を抽出すると、系列文書ＩＤとして、文書ＩＤ「Ａ」、「Ｂ」、「Ｃ」が抽出される。
【００４４】
続いて、類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄに対して、系列文書ＩＤによって射影し、射影データを作成する。
【００４５】
ここで、射影の定義について説明する。ある系列ｓ＝＜ａ１、ａ２、・・・、ａｍ＞、アイテムａに対し、ａ１≠ａ、ａ２≠ａ、・・・、ａｊ−１≠ａ、ａｊ＝ａとなるような整数ｊ（１≦ｊ≦ｍ）が存在する場合、系列＜ａ１、ａ２、・・・、ａｊ＞をｓのａに対するprefix(prefix(s,a))と定義し、系列＜ａｊ＋１、・・・、ａｍ＞をｓのａに対するpostfix(postfix(s,a))と定義する。もし、ｊが存在しない場合には、prefix、postfixは未定義となる。
【００４６】
そして、ある系列データベースＳ（上記系列のデータを複数含んだデータベース）に対し、アイテムａによって射影し、射影データＳ｜ａを作成するとは、Ｓ中のそれぞれの系列ｓに対し、postfix(s,a)を作成し、それらを改めて系列データベースとする操作と定義される。
【００４７】
具体的に、類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄ（系列データベースＳに対応）に含まれる各文書ＩＤ列（系列ｓに対応）に対して、アイテム（系列文書ＩＤ「Ａ」、「Ｂ」、「Ｃ」）によって射影する。そして、例えば、類似度テーブル作成部１６０ｃは、系列文書ＩＤ「Ａ」、「Ｂ」、「Ｃ」の順で射影を実行する。
【００４８】
（系列文書ＩＤ「Ａ」による射影）
類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄ（図６参照）に対して、系列文書ＩＤ「Ａ」による射影を実行すると、系列文書ＩＤ「Ａ」を含む各文書ＩＤ列の内、系列文書ＩＤ「Ａ」を除いた文書ＩＤ列（系列文書ＩＤ「Ａ」のpostfix(s,a)に対応）および当該文書ＩＤ列に対応する単語ＩＤを抽出し、射影データを作成する。
【００４９】
図９は、系列文書ＩＤ「Ａ」の射影によって作成される射影データの一例を示す図である。図９の射影データを参照すると、系列文書ＩＤ「Ａ」と文書ＩＤ「Ｂ」との組み合わせの発生回数が「２」であり、系列文書ＩＤ「Ａ」と文書ＩＤ「Ｃ」との組み合わせの発生回数が「３」であるため、類似度テーブル作成部１６０ｃは、文書ＩＤ「Ａ」の文書データと文章ＩＤ「Ｂ」の文書データとの類似度を「２」、文書ＩＤ「Ａ」の文書データと文章ＩＤ「Ｃ」の文書データとの類似度を「３」と判定する。
【００５０】
その後、類似度テーブル作成部１６０ｃは、射影データ（図９参照）に対応させて、転置インデックス１５０ｄ（図６参照）を更新する。具体的には、転置インデックス１５０ｄの単語ＩＤ「２」の文書ＩＤ列を「Ｂ，Ｃ」、単語ＩＤ「７」の文書ＩＤ列を「Ｂ，Ｃ」、単語ＩＤ「１０」の文書ＩＤ列を「Ｃ」に更新する。図１０は、更新された転置インデックス１５０ｄのデータ構造の一例を示す図（１）である。
【００５１】
（系列文書ＩＤ「Ｂ」による射影）
類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄ（図１０参照）に対して、系列文書ＩＤ「Ｂ」による射影を実行すると、系列文書「Ｂ」を含む各文書ＩＤ列の内、系列文書ＩＤ「Ｂ」を除いた文書ＩＤ列（系列文書ＩＤ「Ｂ」のpostfix(s,a)に対応）および当該文書ＩＤ列に対応する単語ＩＤを抽出し、射影データを作成する。
【００５２】
図１１は、系列文書ＩＤ「Ｂ」の射影によって作成される射影データの一例を示す図である。図１１の射影データを参照すると、系列文書ＩＤ「Ｂ」と文書ＩＤ「Ｃ」との組み合わせの発生回数が「４」であるため、類似度テーブル作成部１６０ｃは、文書ＩＤ「Ｂ」の文書データと文章ＩＤ「Ｃ」の文書データとの類似度を「４」と判定する。
【００５３】
その後、類似度テーブル作成部１６０ｃは、射影データ（図１１）に対応させて、転置インデックス１５０ｄ（図１０参照）を更新する。具体的には、転置インデックス１５０ｄの単語ＩＤ「２」、「５」、「７」、「９」の文書ＩＤ列を「Ｃ」に更新する。図１２は、更新された転置インデックス１５０ｄのデータ構造の一例を示す図（２）である。
【００５４】
（系列文書ＩＤ「Ｃ」による射影）
類似度テーブル作成部１６０ｃは、転置インデックス１５０ｄ（図１２参照）に対して、系列文書ＩＤ「Ｃ」による射影を実行すると、系列文書「Ｃ」を含む各文書ＩＤ列の内、系列文書ＩＤ「Ｃ」を除いた文書ＩＤ列（系列文書ＩＤ「Ｃ」のpostfix(s,a)に対応）および当該文書ＩＤ列に対応する単語ＩＤが存在しないため、類似度テーブル作成部１６０ｃは、射影処理を終了する。
【００５５】
次に、類似度テーブル作成部１６０ｃは、系列文書ＩＤ「Ａ」、「Ｂ」、「Ｃ」による射影を実行した結果得られる各文書データ間の類似度に基づいて、類似度テーブル１５０ｅを作成する。なお、ここでは一例として、系列文書ＩＤ「Ａ」、「Ｂ」、「Ｃ」から類似度を算出する場合について説明したが、例えば、上記の系列文書ＩＤの他に、系列文書ＩＤ「Ｄ」、「Ｅ」等が含まれる場合であっても、上述したシーケンシャルパターン抽出を実行することにより、類似度を算出する。
【００５６】
クラスタリング処理部１６０ｄは、類似度テーブル１５０ｅに基づいて、文書データ群を分類する手段である。なお、クラスタリング処理部１６０ｄは、分類するグループの数（以下、クラスタ数）が、利用者によって指定されたクラスタ数（以下、指定クラスタ数）と等しくなるように、文書データ群を分類する。利用者は、入力部１１０を利用して指定クラスタ数を指定しても良いし、端末装置５０の利用者が、指定クラスタ数を入力し、端末装置５０がデータ処理装置１００に、指定クラスタ数の情報を送信しても良い。
【００５７】
以下において、クラスタリング処理部１６０ｄの処理を具体的に説明する。図１３は、クラスタリング処理部１６０ｄの処理を説明するための図である。なお、ここでは一例として、指定クラスタ数が「３」である場合について説明する。
【００５８】
まず、クラスタリング処理部１６０ｄは、クラスタテーブル１５０ｆを初期化した後、類似度テーブル１５０ｅ（図７参照）のデータをクラスタテーブル１５０ｆにコピーすることにより、図８（あるいは、図１３の上段左端）に示すクラスタテーブル１５０ｆを生成する。
【００５９】
そして、クラスタリング処理部１６０ｄは、クラスタテーブル１５０ｆから最大の類似度を持つ文書ＩＤのペアを検出し、検出したペアの文書ＩＤに対応する行と列のデータをクラスタテーブル１５０ｆから削除する。
【００６０】
図１３に示す例では、最大の類似度を持つ文書ＩＤのペアは、類似度「８」を持つ文書ＩＤ「Ａ」、「Ｄ」のペアとなるので、クラスタリング処理部１６０ｄは、文書ＩＤ「Ａ」、「Ｄ」に対応する行と列のデータをクラスタテーブル１５０ｆから削除する（図１３のステップＳ１０参照）。
【００６１】
クラスタリング処理部１６０ｄは、最大の類似度を持つペア（削除したペア）からなるクラスタを作成し、クラスタテーブル１５０ｆに追加する。図１３に示す例では、文書ＩＤ「Ａ」、「Ｄ」からなるクラスタ「Ａ，Ｄ」を作成し、作成したクラスタ「Ａ，Ｄ」をクラスタテーブル１５０ｆに追加する（図１３のステップＳ２０参照）。
【００６２】
クラスタリング処理部１６０ｄは、クラスタテーブル１５０ｆに追加したクラスタに含まれる文書ＩＤと、他の文書ＩＤとの間の類似度のうち、最大となる類似度を、クラスタに対応する行に登録する。そして、クラスタリング処理部１６０ｄは、クラスタの行に登録した類似度に対応させて、クラスタの列に類似度を登録する。
【００６３】
図１３を例に説明する。クラスタ「Ａ，Ｄ」と文書ＩＤ「Ｂ」との間における類似度は、文書ＩＤ「Ａ」と文書ＩＤ「Ｂ」との間における類似度「２」および文書ＩＤ「Ｄ」と文書ＩＤ「Ｂ」との間における類似度「０」のうち、最大となる類似度が登録されるため、類似度「２」が該箇所に登録される。
【００６４】
クラスタ「Ａ，Ｄ」と文書ＩＤ「Ｃ」との間における類似度は、文書ＩＤ「Ａ」と文書ＩＤ「Ｃ」との間における類似度「５」および文書ＩＤ「Ｄ」と文書ＩＤ「Ｃ」との間における類似度「３」のうち、最大となる類似度が登録されるため、類似度「５」が該箇所に登録される。
【００６５】
クラスタ「Ａ，Ｄ」と文書ＩＤ「Ｅ」との間における類似度は、文書ＩＤ「Ａ」と文書ＩＤ「Ｅ」との間における類似度「１」および文書ＩＤ「Ｄ」と文書ＩＤ「Ｅ」との間における類似度「２」のうち、最大となる類似度が登録されるため、類似度「２」が該箇所に登録される。そして、クラスタリング処理部１６０ｄは、クラスタの行に登録した類似度に対応させて、クラスタの列に類似度を登録する（図１３のステップＳ３０参照）。
【００６６】
クラスタリング処理部１６０ｄは、クラスタテーブル１５０ｆのクラスタ数と、指定クラスタ数とが等しくなるまで、上記処理を繰り返す。図１３のステップＳ３０の終了時点において、クラスタ数は「４」であり、指定クラスタ数は、「３」であるため、クラスタリング処理部１６０ｄは、もう一度、上記処理を繰り返す。
【００６７】
すなわち、図１３の上段右端に示すクラスタテーブル１５０ｆにおいて、最大の類似度を持つ文書ＩＤのペアは、類似度「６」を持つ文書ＩＤ「Ｃ」、「Ｅ」のペアとなるので、クラスタリング処理部１６０ｄは、文書ＩＤ「Ｃ」、「Ｅ」に対応する行と列のデータをクラスタテーブル１５０ｆから削除する（図１３のステップＳ４０参照）。
【００６８】
そして、クラスタリング処理部１６０ｄは、文書ＩＤ「Ｃ」、「Ｅ」からなるクラスタ「Ｃ，Ｅ」を作成し、作成したクラスタ「Ｃ，Ｅ」をクラスタテーブル１５０ｆに追加する（図１３のステップＳ５０参照）。
【００６９】
クラスタリング処理部１６０ｄは、文書ＩＤ「Ｃ」と文書ＩＤ「Ｂ」との間における類似度が「３」、文書ＩＤ「Ｅ」と文書ＩＤ「Ｂ」との間における類似度が「４」となるので、最大となる類似度「４」をクラスタ「Ｃ，Ｅ」と文書ＩＤ「Ｂ」との間における類似度として登録する。
【００７０】
また、クラスタリング処理部１６０ｄは、文書ＩＤ「Ｃ」と文書ＩＤ「Ａ，Ｄ」との間における類似度が「５」、文書ＩＤ「Ｅ」と文書ＩＤ「Ａ，Ｄ」との間における類似度が「２」となるので、最大となる類似度「５」をクラスタ「Ｃ，Ｅ」と文書ＩＤ「Ａ，Ｄ」との間における類似度として登録する（図１３のステップＳ６０参照）。
【００７１】
図１３のステップＳ６０の処理が終了した時点で、クラスタテーブル１５０ｆのクラスタ数が「３」となり、指定クラスタ数「３」と等しくなるので、クラスタリング処理部１６０ｄは、クラスタテーブル１５０ｆに基づいて、文書データ群を分類する。図１３に示す例では、文書データ群は、文書ＩＤ「Ｂ」の文書データと、文書ＩＤ「Ａ」、「Ｄ」の文書データと、文書ＩＤ「Ｃ」、「Ｅ」の文書データに分類されることになる。
【００７２】
クラスタリング処理部１６０ｄは、端末装置５０から送信された検索キーワードの回答として、分類した文書データを端末装置５０に出力する。
【００７３】
次に、本実施例にかかるデータ処理装置１００の処理手順について説明する。図１４は、本実施例にかかるデータ処理装置１００の処理手順を示すフローチャートである。同図に示すように、データ処理装置１００は、端末装置５０から検索キーワードを取得し（ステップＳ１０１）、検索キーワードに対応する文書データを検索する（ステップＳ１０２）。
【００７４】
そして、データ処理装置１００は、転置インデックス作成処理を実行し（ステップＳ１０３）、類似度テーブル作成処理を実行し（ステップＳ１０４）、クラスタリング処理を実行し（ステップＳ１０５）、クラスタリング結果（分類した文書データ）を端末装置５０に出力する（ステップＳ１０６）。
【００７５】
次に、図１４のステップＳ１０３に示した転置インデックス作成処理について説明する。図１５は、転置インデックス作成処理を示すフローチャートである。同図に示すように、データ処理装置１００は、転置インデックス作成部１６０ｂが各文書データに対して形態素解析を実行する（ステップＳ２０１）。
【００７６】
そして、転置インデックス作成部１６０ｂは、単語インデックス１５０ｂを作成し（ステップＳ２０２）、単語ＩＤをキーにして、転置インデックス１５０ｄを作成する（ステップＳ２０３）。
【００７７】
次に、図１４のステップＳ１０４に示した類似度テーブル作成処理について説明する。図１６は、類似度テーブル作成処理を示すフローチャートである。同図に示すように、データ処理装置１００は、類似度テーブル作成部１６０ｃが類似度テーブル１５０ｅを初期化し（ステップＳ３０１）、転置インデックス１５０ｄからアイテム数１の多頻度系列となる系列文書ＩＤを抽出する（ステップＳ３０２）。
【００７８】
そして、類似度テーブル作成部１６０ｃが、系列文書ＩＤと転置インデックス１５０ｄとを基にして、射影データを作成し（ステップＳ３０３）、ペアの出現頻度（組合せの発生回数）を計算し（ステップＳ３０４）、転置インデックス１５０ｄを更新する（ステップＳ３０５）。
【００７９】
類似度テーブル作成部１６０ｃは、全ての系列文書ＩＤを選択したか否かを判定し（ステップＳ３０６）、全てを選択していない場合には（ステップＳ３０７，Ｎｏ）、未選択の系列文書ＩＤを選択し（ステップＳ３０８）、ステップＳ３０３に移行する。
【００８０】
一方、全ての系列文書ＩＤを選択した場合には（ステップＳ３０７，Ｙｅｓ）、類似度テーブル１５０ｅに各文書ペアの類似度を登録する（ステップＳ３０９）。
【００８１】
次に、図１４のステップＳ１０５に示したクラスタリング処理について説明する。図１７は、クラスタリング処理を示すフローチャートである。同図に示すように、クラスタリング処理部１６０ｄは、類似度テーブル１５０ｅをクラスタテーブル１５０ｆにコピーし（ステップＳ４０１）、クラスタテーブル１５０ｆのクラスタ数が指定クラスタ数と等しいか否かを判定する（ステップＳ４０２）。
【００８２】
そして、クラスタ数と指定クラスタ数とが等しい場合には（ステップＳ４０３，Ｙｅｓ）、クラスタリング処理を終了する。一方、クラスタ数と指定クラスタ数とが異なる場合（ステップＳ４０３，Ｎｏ）、クラスタテーブル１５０ｆ中で最大の値を判定する（ステップＳ４０４）。
【００８３】
クラスタリング処理部１６０ｄは、最大の値を持つペアの行と列を削除し（ステップＳ４０５）、最大の値を持つペアからなるクラスタを生成し、クラスタテーブル１５０ｆに追加する（ステップＳ４０６）。
【００８４】
続いて、クラスタリング処理部１６０ｄは、追加したクラスタの行の各要素から、未選択の要素を選択し（ステップＳ４０７）、類似度テーブル１５０ｅを参照し、追加したクラスタ間の類似度で最大の値を要素に登録する（ステップＳ４０８）。
【００８５】
そして、クラスタリング処理部１６０ｄは、全ての要素を選択したか否かを判定し（ステップＳ４０９）、全ての要素を選択していない場合には（ステップＳ４１０，Ｎｏ）、ステップＳ４０７に移行し、全ての要素を選択した場合には（ステップＳ４１０，Ｙｅｓ）、クラスタテーブル１５０ｆに追加した行の各要素の値を、対応する列の各要素に登録し（ステップＳ４１１）、ステップＳ４０２に移行する。
【００８６】
上述してきたように、本実施例にかかるデータ処理装置１００は、各文書データ中の単語ＩＤと当該単語ＩＤに対応する単語を含む文書データとを対応付けた転置インデックス１５０ｄを作成し、転置インデックス１５０ｄに対してシーケンシャルパターン抽出を実行する。そして、シーケンシャルパターン抽出を実行した結果出現する文書データの組み合わせの発生回数を判定（特に、本実施例では、シーケンシャルパターン抽出において、長さ２のパターンの発生回数のみを判定）し、判定結果に基づいて、各文書データ間の類似度を計算するので、文書データの類似度を効率よく算出でき、従来の技術と比較して、類似度計算にかかる処理時間を短縮することが出来る。
【００８７】
例えば、従来技術のように、ベクタースペースモデルによる類似度の計算は、文書同士を比較することにより、文書間の類似度を算出しているので、文書数をｎとした場合の比較回数を表す式Ｆ（ｎ）は、
F(n)=(n×(n-1))/2
のような「二次関数の式」で表すことができる。そして、例えば、文書数が４の場合には、類似度の計算を６回行う必要がある（例えば、文書をａ，ｂ，ｃ，ｄとすれば、ａ−ｂ、ａ−ｃ、ａ−ｄ、ｂ−ｃ、ｂ−ｄ、ｃ−ｄの計６回計算を行う必要がある）。
【００８８】
そして、ベクタースペースモデルの計算量を見積もるため、比較回数を表す式をＯ記法によって表すと、
O(n)=n^2
と表すことが出来る。
【００８９】
一方、本実施例にかかるデータ処理装置１００では、各文書と、転置インデックス１５０ｄとを比較することによって、各文書間の類似度を算出しているので、文書数が増えることによって増加する計算量は、「１次関数」に従って増加する（例えば、文書数が１つ増えると、転置インデックス１５０ｄと比較する回数が一回増える）と考えられ、比較回数を表す式をＯ記法によって表すと
O(n)=n
と表すことができる。
【００９０】
従って、文書数ｎが２倍になったときに、従来の技術では、処理時間が約ｎ＾２倍になるのに対し、本実施例にかかるデータ処理装置１００では、処理時間を約ｎ倍に抑えることが出来るので、従来の技術と比較して、類似度計算にかかる処理時間を短縮することが出来る。
【００９１】
ところで、本実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部あるいは一部を公知の方法で自動的に行うこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００９２】
また、図２に示したデータ処理装置１００の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行われる各処理機能は、その全部または任意の一部がＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００９３】
図１８は、実施例にかかるデータ処理装置１００を構成するコンピュータ４０のハードウェア構成を示す図である。図１８に示すように、このコンピュータ（物品検索装置）４０は、入力装置４１、モニタ４２、ＲＡＭ（Random  Access  Memory）４３、ＲＯＭ（Read  Only  Memory）４４、記憶媒体からデータを読み取る媒体読取装置４５、他の装置（例えば、端末装置５０）との間でデータの送受信を行う通信装置４６、ＣＰＵ（Central  Processing  Unit）４７、ＨＤＤ（Hard  Disk  Drive）４８をバス４９で接続して構成される。
【００９４】
そして、ＨＤＤ４８には、上記したデータ処理装置１００の機能と同様の機能を発揮するクラスタリング処理プログラム４８ｂが記憶されている。ＣＰＵ４７が、クラスタリング処理プログラム４８ｂを読み出して実行することにより、クラスタリング処理プロセス４７ａが起動される。ここで、クラスタリング処理プロセス４７ａは、図２に示した文書データ検索部１６０ａ、転置インデックス作成部１６０ｂ、類似度テーブル作成部１６０ｃ、クラスタリング処理部１６０ｄに対応する。
【００９５】
また、ＨＤＤ４８は、文書管理データ１５０ａ、単語インデックス１５０ｂ、単語ＩＤ管理テーブル１５０ｃ、転置インデックス１５０ｄ、類似度テーブル１５０ｅ、クラスタテーブル１５０ｆに対応する各種データ４８ａを記憶する。ＣＰＵ４７は、ＨＤＤ４８に格納された各種データ４８ａを読み出して、ＲＡＭ４３に格納し、ＲＡＭ４３に格納された各種データ４３ａを用いて、各文書データを分類する。
【００９６】
ところで、図１８に示したクラスタリング処理プログラム４８ｂは、必ずしも最初からＨＤＤ４８に記憶させておく必要はない。たとえば、コンピュータに挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータの内外に備えられるハードディスクドライブ（ＨＤＤ）などの「固定用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータに接続される「他のコンピュータ（またはサーバ）」などにクラスタリング処理プログラム４８ｂを記憶しておき、コンピュータがこれらからクラスタリング処理プログラム４８ｂを読み出して実行するようにしてもよい。
【００９７】
上記の実施例を含む実施形態に関し、以下の付記を開示する。
【００９８】
（付記１）記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置のデータ分類方法であって、
前記データ処理装置は、
前記記憶装置に記憶された文書データを読み出し、各文書データ中のキーワードと当該キーワードを含む文書データとを対応付けたリストを作成するリスト作成ステップと、
前記リストに対してシーケンシャルパターン抽出を実行し、出現した文書データの組み合わせの発生回数を判定する判定ステップと、
前記判定ステップの判定結果に基づいて、各文書データ間の類似度を算出する算出ステップと、
を含んだことを特徴とするデータ分類方法。
【００９９】
（付記２）前記判定ステップは、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを特徴とする付記１に記載のデータ分類方法。
【０１００】
（付記３）前記類似度の値が最大となる各文書データの組合せを求めることにより、文書データを分類する分類ステップを更に含み、当該分類ステップは、利用者に指定される分類数と文書データの分類数とが等しくなるように、前記文書データを分類することを特徴とする付記１または２に記載のデータ分類方法。
【０１０１】
（付記４）記憶装置に記憶された各文書データの類似度によって、文書データを分類するデータ処理装置であって、
前記記憶装置に記憶された文書データを読み出し、各文書データ中のキーワードと当該キーワードを含む文書データとを対応付けたリストを作成するリスト作成手段と、
前記リストに対してシーケンシャルパターン抽出を実行し、出現した文書データの組み合わせの発生回数を判定する判定手段と、
前記判定手段の判定結果に基づいて、各文書データ間の類似度を算出する算出手段と、
を備えたことを特徴とするデータ処理装置。
【０１０２】
（付記５）前記判定手段は、シーケンシャルパターン抽出で、長さ２のパターンの発生回数のみを判定することを特徴とする付記４に記載のデータ処理装置。
【０１０３】
（付記６）前記類似度の値が最大となる各文書データの組合せを求めることにより、文書データを分類する分類手段を更に備え、当該分類手段は、利用者に指定される分類数と文書データの分類数とが等しくなるように、前記文書データを分類することを特徴とする付記４または５に記載のデータ処理装置。
【産業上の利用可能性】
【０１０４】
以上のように、本発明にかかるデータ分類方法およびデータ処理装置は、文書データを検索する検索システムなどに有用であり、特に、処理時間をかけることなく、各文書データを分類する必要がある場合に適している。
【図面の簡単な説明】
【０１０５】
【図１】検索システムの構成を示す図である。
【図２】本実施例にかかるデータ処理装置の構成を示す機能ブロック図である。
【図３】文書管理データのデータ構造の一例を示す図である。
【図４】単語インデックスのデータ構造の一例を示す図である。
【図５】単語ＩＤ管理テーブルのデータ構造の一例を示す図である。
【図６】転置インデックスのデータ構造の一例を示す図である。
【図７】類似度テーブルのデータ構造の一例を示す図である。
【図８】クラスタテーブルのデータ構造の一例を示す図である。
【図９】系列文書ＩＤ「Ａ」の射影によって作成される射影データの一例を示す図である。
【図１０】更新された転置インデックスのデータ構造の一例を示す図（１）である。
【図１１】系列文書ＩＤ「Ｂ」の射影によって作成される射影データの一例を示す図である。
【図１２】更新された転置インデックスのデータ構造の一例を示す図（２）である。
【図１３】クラスタリング処理部の処理を説明するための図である。
【図１４】本実施例にかかるデータ処理装置の処理手順を示すフローチャートである。
【図１５】転置インデックス作成処理を示すフローチャートである。
【図１６】類似度テーブル作成処理を示すフローチャートである。
【図１７】クラスタリング処理を示すフローチャートである。
【図１８】実施例にかかるデータ処理装置を構成するコンピュータのハードウェア構成を示す図である。
【符号の説明】
【０１０６】
１０    ネットワーク
４０    コンピュータ
４１    入力装置
４２    モニタ
４３    ＲＡＭ
４３ａ，４８ａ  各種データ
４４    ＲＯＭ
４５    媒体読取装置
４６    通信装置
４７    ＣＰＵ
４７ａ  クラスタリング処理プロセス
４８    ＨＤＤ
４８ｂ  クラスタリング処理プログラム
４９    バス
５０    端末装置
１００    データ処理装置
１１０    入力部
１２０    出力部
１３０    通信制御ＩＦ部
１４０    入出力制御ＩＦ部
１５０    記憶部
１５０ａ  文書管理データ
１５０ｂ  単語インデックス
１５０ｃ  単語ＩＤ管理テーブル
１５０ｄ  転置インデックス
１５０ｅ  類似度テーブル
１５０ｆ  クラスタテーブル
１６０    制御部
１６０ａ  文書データ検索部
１６０ｂ  転置インデックス作成部
１６０ｃ  類似度テーブル作成部
１６０ｄ  クラスタリング処理部
【図１】
0005194818.tif 000002
【図２】
0005194818.tif 000003
【図３】
0005194818.tif 000004
【図４】
0005194818.tif 000005
【図５】
0005194818.tif 000006
【図６】
0005194818.tif 000007
【図７】
0005194818.tif 000008
【図８】
0005194818.tif 000009
【図９】
0005194818.tif 000010
【図１０】
0005194818.tif 000011
【図１１】
0005194818.tif 000012
【図１２】
0005194818.tif 000013
【図１３】
0005194818.tif 000014
【図１４】
0005194818.tif 000015
【図１５】
0005194818.tif 000016
【図１６】
0005194818.tif 000017
【図１７】
0005194818.tif 000018
【図１８】
0005194818.tif 000019