(57)【特許請求の範囲】
【請求項１】
単一または複数の文書からなる文書集合を特徴量で表現するための文書集合特徴化方法であって、
ツリー作成手段が、全文書で文書間の距離に基づき最小スパン木を構成するステップと、
セグメント分割手段が、前記最小スパン木をいくつかのセグメントに分割するステップと、
ベクトルデータ生成手段が、前記文書集合を構成する文書の、前記セグメント中における分布を要素とするベクトルデータを生成し、前記文書集合の特徴量とするステップを含むことを特徴とする文書集合特徴化方法。
【請求項２】
前記セグメントの分割は、ＭＤＬ（最小記述長）基準に基づく分割を行うことを特徴とする請求項１に記載の文書集合特徴化方法。
【請求項３】
前記ベクトルデータは、正規化された分布を要素とすることを特徴とする請求項１または２に記載の文書集合特徴化方法。
【請求項４】
単一または複数の文書からなる文書集合を特徴量で表現するための文書集合特徴化装置であって、
全文書に出現する単語を抽出する出現単語抽出手段と、
この抽出した単語に基づき文書同士の距離を計算する文書間距離計算手段と、
この計算された文書間距離に基づき全文書で最小スパン木を作成するツリー作成手段と、
この作成された最小スパン木をいくつかのセグメントに分割するセグメント分割手段と、
前記文書集合を構成する文書の、前記セグメント中における分布を要素とするベクトルデータを生成し、このベクトルデータで前記文書集合の特徴量を表現するベクトルデータ生成手段とを有することを特徴とする文書集合特徴化装置。
【請求項５】
前記セグメント分割手段は、ＭＤＬ基準に基づく分割を行うＭＤＬ基準分割手段を有することを特徴とする請求項４に記載の文書集合特徴化装置。
【請求項６】
前記ベクトルデータ生成手段は、正規化された分布を要素としてベクトルデータを生成する手段を有することを特徴とする請求項４または５に記載の文書集合特徴化装置。
【請求項７】
検索対象文書群を構成する検索対象文書の特徴量を用いて、指定された参照文書集合に類似する文書集合を前記検索対象文書群から検索する文書集合検索方法であって、
ツリー作成手段が、前記検索対象文書群と参照文書集合で文書間の距離に基づき最小スパン木を構成するステップと、
セグメント分割手段が、前記最小スパン木をいくつかのセグメントに分割するステップと、
ベクトルデータ生成手段が、単一または複数の参照文書からなる参照文書集合を構成する参照文書の、前記セグメント中における分布を要素とする参照ベクトルデータを生成し、前記参照文書集合の特徴量とし、単一または複数の検索対象文書からなる検索対象文書集合を構成する検索対象文書の、前記セグメント中における分布を要素とする検索対象ベクトルデータを前記検索対象文書集合の特徴量とするステップと、
検索手段が、参照文書集合の特徴量および検索対象文書集合の特徴量に基づき参照文書集合に類似する文書集合を前記検索対象文書群から検索するステップを含むことを特徴とする文書集合検索方法。
【請求項８】
請求項７に記載の文書集合検索方法で検索された文書集合を新たに参照文書集合として検索を繰り返すことを特徴とする請求項７に記載の文書集合検索方法。
【請求項９】
前記セグメントの分割は、ＭＤＬ基準に基づく分割を行うことを特徴とする請求項７または８に記載の文書集合検索方法。
【請求項１０】
前記ベクトルデータは、正規化された分布を要素とすることを特徴とする請求項７乃至９のいずれかに記載の文書集合検索方法。
【請求項１１】
検索対象文書群を構成する検索対象文書の特徴量を用いて、指定された参照文書集合に類似する文書集合を前記検索対象文書群から検索する文書集合検索装置であって、
前記参照文書集合と検索対象文書群に出現する単語を抽出する出現単語抽出手段と、この抽出した単語に基づき文書同士の距離を計算する文書間距離計算手段と、
この計算された文書間距離に基づき前記検索対象文書群と参照文書集合で最小スパン木を作成するツリー作成手段と、
前記最小スパン木をいくつかのセグメントに分割するセグメント分割手段と、
単一または複数の参照文書からなる参照文書集合を構成する参照文書の、前記セグメント中における分布を要素とする参照ベクトルデータを生成する参照ベクトルデータ生成手段と、
単一または複数の検索対象文書からなる検索対象文書集合を構成する検索対象文書の、前記セグメント中の分布を要素とする検索対象ベクトルデータを生成する検索対象ベクトルデータ生成手段と、
前記参照ベクトルデータ生成手段で得られた参照ベクトルデータを参照文書集合の特徴量とし、検索対象ベクトルデータ生成手段で得られた検索対象ベクトルデータを検索対象文書集合の特徴量として、参照文書集合に類似する文書集合を前記検索対象文書群から検索する検索手段と、
この検索結果を提示する提示手段とを有することを特徴とする文書集合検索装置。
【請求項１２】
請求項１１に記載の文書集合検索装置で検索された文書集合を新たに参照文書集合として検索を繰り返すことを特徴とする請求項１１に記載の文書集合検索装置。
【請求項１３】
前記セグメント分割手段は、ＭＤＬ基準に基づく分割を行うＭＤＬ基準分割手段を有することを特徴とする請求項１１または１２に記載の文書集合検索装置。
【請求項１４】
前記ベクトルデータ生成手段は、正規化された分布を要素としてベクトルデータを生成する手段を有することを特徴とする請求項１１乃至１３のいずれかに記載の文書集合検索装置。
【請求項１５】
前記提示手段は、前記参照文書集合と前記検索対象文書集合の類似度を反映するように前記参照文書集合と前記検索対象文書集合を検索結果提示マップ上に表示する表示手段を有することを特徴とする請求項１１乃至１４のいずれかに記載の文書集合検索装置。
【請求項１６】
前記表示手段は、前記参照ベクトルデータおよび検索対象ベクトルデータを主成分分析して２次元上に表現する主成分分析手段を有することを特徴とする請求項１１乃至１５のいずれかに記載の文書集合検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、単一または複数の文書からなる文書集合を特徴量で表現して特徴化する文書集合特徴化方法、および該方法の特徴量による文書集合間の類似度に基づいて文書集合の検索を行う文書集合検索方法およびそれらの装置に関する。
【０００２】
【従来の技術】
従来、複数の文書からなる文書集合を特徴化する場合、文書集合に含まれる全ての文書をまとめて１つの文書と見なし、この１つの文書に対して単一文書の場合と同様に特徴化することが考えられる。このように文書集合を１つの文書と見なして、文書中の単語に基づいて特徴を抽出する場合、次のようなことが考えられる。
【０００３】
４つの単語Ｗ１，Ｗ２，Ｗ３，Ｗ４が存在し、単語Ｗ１とＷ２を含む文書Ｄ１、単語Ｗ３とＷ４を含む文書Ｄ２、単語Ｗ１とＷ３を含む文書Ｄ３、単語Ｗ２とＷ４を含む文書Ｄ４が存在するとする。また、文書Ｄ１とＤ２から構成される文書集合Ｓ１および文書Ｄ３とＤ４から構成される文書集合Ｓ２が存在するとした場合に、文書集合Ｓ１とＳ２の類似度に関しては、上述したように文書集合中の文書をまとめて、１つの文書と見なす従来の方法において、文書集合Ｓ１およびＳ２が両方とも同じ単語Ｗ１，Ｗ２，Ｗ３，Ｗ４を含んでいるため、文書Ｄ１，Ｄ２，Ｄ３，Ｄ４の内容に関係なく、類似した文書集合であると判定される。
【０００４】
【発明が解決しようとする課題】
上述したように、従来の方法では、文書集合Ｓ１，Ｓ２が両方とも同じ単語Ｗ１，Ｗ２，Ｗ３，Ｗ４を含んでいると、文書Ｄ１，Ｄ２，Ｄ３，Ｄ４の内容に関係なく、類似した文書集合であると判定されてしまうが、実際には単語Ｗ１，Ｗ２，Ｗ３，Ｗ４が同じであっても、文書Ｄ１とＤ２で記述されている内容が文書Ｄ３とＤ４で記述されている内容と異なることがあり、このような場合には文書集合Ｓ１とＳ２は内容的に類似していないと判定されるべきものであるにも関わらず、上述した従来の方法では類似していると誤判定されてしまうという問題がある。
【０００５】
本発明は、上記に鑑みてなされたもので、その目的とするところは、文書集合を構成する文書の特徴を要素とするベクトルデータを文書集合の特徴量とすることにより文書集合の類似性判定および類似した文書集合の検索を適確に行い得る文書集合特徴化方法および該方法を用いた文書集合検索方法およびそれらの装置を提供することにある。
【０００６】
【課題を解決するための手段】
上記目的を達成するため、請求項１記載の本発明は、単一または複数の文書からなる文書集合を特徴量で表現するための文書集合特徴化方法であって、ツリー作成手段が、全文書で文書間の距離に基づき最小スパン木を構成するステップと、セグメント分割手段が、前記最小スパン木をいくつかのセグメントに分割するステップと、ベクトルデータ生成手段が、前記文書集合を構成する文書の、前記セグメント中における分布を要素とするベクトルデータを生成し、前記文書集合の特徴量とするステップを含むことを要旨とする。
【０００７】
請求項１記載の本発明にあっては、全文書で文書間の距離に基づき構成した最小スパン木をいくつかのセグメントに分割し、この各セグメントにおける文書の分布を要素とするベクトルデータを文書集合の特徴量とするため、この特徴量を使用することにより、文書集合の類似性を適確に判定できる。
【００１２】
請求項２に記載の本発明は、請求項１に記載の発明において、前記セグメントの分割が、ＭＤＬ（最小記述長）基準に基づく分割を行うことを要旨とする。
【００１３】
請求項２に記載の本発明にあっては、ツリーはＭＤＬ（最小記述長）基準に基づいていくつかのセグメントに分割される。
【００１４】
また、請求項３に記載の本発明は、請求項１または２に記載の発明において、前記ベクトルデータが、正規化された分布を要素とすることを要旨とする。
【００１５】
請求項３に記載の本発明にあっては、ベクトルデータは正規化された分布を要素とする。
【００１６】
更に、請求項４に記載の本発明は、単一または複数の文書からなる文書集合を特徴量で表現するための文書集合特徴化装置であって、全文書に出現する単語を抽出する出現単語抽出手段と、この抽出した単語に基づき、文書同士の距離を計算する文書間距離計算手段と、この計算された文書間距離に基づき全文書で最小スパン木を作成するツリー作成手段と、この作成された最小スパン木をいくつかのセグメントに分割するセグメント分割手段と、前記文書集合を構成する文書の、前記セグメント中における分布を要素とするベクトルデータを生成し、このベクトルデータで前記文書集合の特徴量を表現するベクトルデータ生成手段とを有することを要旨とする。
【００１７】
請求項４に記載の本発明にあっては、全文書に出現する単語を抽出し、この抽出した単語に基づき計算された文書同士の距離に基づき、全文書で最小スパン木を作成し、この最小スパン木をいくつかのセグメントに分割し、各セグメントにおける文書の分布を要素とするベクトルデータを生成し、このベクトルデータで文書集合の特徴量を表現するため、この特徴量を使用することにより、文書集合の類似性を適確に判定できる。
【００２０】
また、請求項５に記載の本発明は、請求項４に記載の発明において、前記セグメント分割手段が、ＭＤＬ基準に基づく分割を行うＭＤＬ基準分割手段を有することを要旨とする。
【００２１】
請求項５に記載の本発明にあっては、セグメント分割ではＭＤＬ基準に基づく分割を行う。
【００２２】
更に、請求項６に記載の本発明は、請求項４または５に記載の発明において、前記ベクトルデータ生成手段が、正規化された分布を要素としてベクトルデータを生成する手段を有することを要旨とする。
【００２３】
請求項６に記載の本発明にあっては、正規化された分布を要素としてベクトルデータを生成する。
【００２８】
更に、請求項７に記載の本発明は、検索対象文書群を構成する検索対象文書の特徴量を用いて、指定された参照文書集合に類似する文書集合を前記検索対象文書群から検索する文書集合検索方法であって、ツリー作成手段が、前記検索対象文書群と参照文書集合で文書間の距離に基づき最小スパン木を構成するステップと、セグメント分割手段が、前記最小スパン木をいくつかのセグメントに分割するステップと、ベクトルデータ生成手段が、単一または複数の参照文書からなる参照文書集合を構成する参照文書の、前記セグメント中における分布を要素とする参照ベクトルデータを生成し、前記参照文書集合の特徴量とし、単一または複数の検索対象文書からなる検索対象文書集合を構成する検索対象文書の、前記セグメント中における分布を要素とする検索対象ベクトルデータを前記検索対象文書集合の特徴量とするステップと、検索手段が、参照文書集合の特徴量および検索対象文書集合の特徴量に基づき参照文書集合に類似する文書集合を前記検索対象文書群から検索するステップを含むことを要旨とする。
【００２９】
請求項７に記載の本発明にあっては、検索対象文書群で文書間の距離に基づき最小スパン木を構成し、この最小スパン木をいくつかのセグメントに分割し、この分割した各セグメント中における参照文書の分布を要素とする参照ベクトルデータを参照文書集合の特徴量とし、検索対象文書の分布を要素とする検索対象ベクトルデータを検索対象文書集合の特徴量とし、この各特徴量に基づき参照文書集合に類似する文書集合を前記検索対象文書群から検索するため、参照文書集合に類似する文書集合を適確に検索することができる。
【００３０】
請求項８に記載の本発明は、請求項７に記載の発明において、請求項７に記載の文書集合検索方法で検索された文書集合を新たに参照文書集合として検索を繰り返すことを要旨とする。
【００３１】
請求項８に記載の本発明にあっては、参照文書集合は文書集合検索方法で検索された文書集合である。
【００３４】
更に、請求項９に記載の本発明は、請求項７または８に記載の発明において、前記セグメントの分割が、ＭＤＬ基準に基づく分割を行うことを要旨とする。
【００３５】
請求項９に記載の本発明にあっては、ＭＤＬ基準に基づいてセグメントの分割を行う。
【００３６】
請求項１０に記載の本発明は、請求項７乃至９のいずれかに記載の発明において、前記ベクトルデータが、正規化された分布を要素とすることを要旨とする。
【００３７】
請求項１０に記載の本発明にあっては、ベクトルデータは正規化された分布を要素とする。
【００３８】
また、請求項１１に記載の本発明は、検索対象文書群を構成する検索対象文書の特徴量を用いて、指定された参照文書集合に類似する文書集合を前記検索対象文書群から検索する文書集合検索装置であって、前記参照文書集合と検索対象文書群に出現する単語を抽出する出現単語抽出手段と、この抽出した単語に基づき文書同士の距離を計算する文書間距離計算手段と、この計算された文書間距離に基づき前記検索対象文書群と参照文書集合で最小スパン木を作成するツリー作成手段と、前記最小スパン木をいくつかのセグメントに分割するセグメント分割手段と、単一または複数の参照文書からなる参照文書集合を構成する参照文書の、前記セグメント中における分布を要素とする参照ベクトルデータを生成する参照ベクトルデータ生成手段と、単一または複数の検索対象文書からなる検索対象文書集合を構成する検索対象文書の、前記セグメント中の分布を要素とする検索対象ベクトルデータを生成する検索対象ベクトルデータ生成手段と、前記参照ベクトルデータ生成手段で得られた参照ベクトルデータを参照文書集合の特徴量とし、検索対象ベクトルデータ生成手段で得られた検索対象ベクトルデータを検索対象文書集合の特徴量として、参照文書集合に類似する文書集合を前記検索対象文書群から検索する検索手段と、この検索結果を提示する提示手段とを有することを要旨とする。
【００３９】
請求項１１に記載の本発明にあっては、参照文書集合と検索対象文書群に出現する単語を抽出し、この抽出した単語に基づき計算した文書間距離に基づき検索対象文書群と参照文書集合で最小スパン木を作成し、こので最小スパン木をいくつかのセグメントに分割し、この分割した各セグメント中における参照文書の分布を要素とする参照ベクトルデータを生成し、また検索対象文書の分布を要素とする検索対象ベクトルデータを生成し、参照ベクトルデータを参照文書集合の特徴量とし、検索対象ベクトルデータを検索対象文書集合の特徴量とし、参照文書集合に類似する文書集合を検索対象文書群から検索し、この検索結果を提示するため、参照文書集合に類似する文書集合を適確に検索することができる。
【００４０】
更に、請求項１２に記載の本発明は、請求項１１に記載の発明において、請求項１１に記載の文書集合検索方法で検索された文書集合を新たに参照文書集合として検索を繰り返すことを要旨とする。
【００４１】
請求項１２に記載の本発明にあっては、参照文書集合は文書集合検索装置で検索された文書集合である。
【００４４】
また、請求項１３に記載の本発明は、請求項１１または１２に記載の発明において、前記セグメント分割手段が、ＭＤＬ基準に基づく分割を行うＭＤＬ基準分割手段を有することを要旨とする。
【００４５】
請求項１３に記載の本発明にあっては、ＭＤＬ基準に基づいてセグメントを分割する。
【００４６】
更に、請求項１４に記載の本発明は、請求項１１乃至１３のいずれかに記載の発明において、前記ベクトルデータ生成手段が、正規化された分布を要素としてベクトルデータを生成する手段を有することを要旨とする。
【００４７】
請求項１４に記載の本発明にあっては、正規化された分布を要素としてベクトルデータを生成する。
【００４８】
請求項１５に記載の本発明は、請求項１１乃至１４のいずれかに記載の発明において、前記提示手段が、前記参照文書集合と前記検索対象文書集合の類似度を反映するように前記参照文書集合と前記検索対象文書集合を検索結果提示マップ上に表示する表示手段を有することを要旨とする。
【００４９】
請求項１５に記載の本発明にあっては、参照文書集合と検索対象文書集合の類似度を反映するように参照文書集合と検索対象文書集合を検索結果提示マップ上に表示する。
【００５０】
また、請求項１６に記載の本発明は、請求項１１乃至１５のいずれかに記載の発明において、前記表示手段が、前記参照ベクトルデータおよび検索対象ベクトルデータを主成分分析して２次元上に表現する主成分分析手段を有することを要旨とする。
【００５１】
請求項１６に記載の本発明にあっては、表示手段は参照ベクトルデータおよび検索対象ベクトルデータを主成分分析して２次元上に表現する。
【００５２】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。図１は、本発明の一実施形態に係る文書集合特徴化方法を説明するための図である。本実施形態の文書集合特徴化方法は、文書集合を構成する文書の特徴を要素とするベクトルデータを文書集合の特徴量として決定するものであるが、図１に示す実施形態では、３つの文書集合ｓ１，ｓ２，ｓ３を一例として使用して説明を行っている。そして、文書集合ｓ１は、文書ｄ１１，ｄ１２，ｄ１３、文書集合ｓ２は、文書ｄ２１，ｄ２２，ｄ２３、文書集合ｓ３は、文書ｄ３１，ｄ３２，ｄ３３から構成されている。
【００５３】
このような３つの文書集合ｓ１，ｓ２，ｓ３を構成する全文書ｄ１１，ｄ１２，ｄ１３，ｄ２１，ｄ２２，ｄ２３，ｄ３１，ｄ３２，ｄ３３で図１に示すようなツリーｔを構成する。このツリーｔの構成にあたっては、まず文書集合ｓ１，ｓ２，ｓ３からなる全文書ｄ１１，ｄ１２，ｄ１３，ｄ２１，ｄ２２，ｄ２３，ｄ３１，ｄ３２，ｄ３３に出現する単語を抽出し、この抽出した単語に基づき各文書間の距離（類似度）を計算する。そして、この計算した各文書間の距離に基づいてツリーｔを作成する。
【００５４】
このツリーｔは、全文書の類似度を尺度とした最小スパン木を構成するツリーとするものである。すなわち、各文書間の類似度に基づいて対象とする個々の文書をノードとする最小スパン木を図１に示すツリーｔのように構成するものである。
【００５５】
最小スパン木は、単一要素の集合Ａi(0)＝ａiから始め、続く各ステップ（ｓ ）毎に、ｋ個の最も類似度の高い部分集合Ａj1(s-1)，Ａj2(s-1)，…，Ａjk(s-1)を融合して、より大きい部分集合Ａjsを作ることによって構成されるものであ る。部分集合Ａi，Ａjの類似度は、Ｓｉｍ（ａk，ａl）：ａk∋Ａi ａl∋Ａjの 最小値を用いる。このように構成される最小スパン木は、クラスタリングのアルゴリズムが単純であるため、大量の文書を扱う場合に時間的に優位になると考えられる。
【００５６】
次に、このように構成された最小スパン木のツリーｔをいくつかのセグメントに分割する。この分割では、ＭＤＬ（Minimum Description Length：最小記述長）基準に基づく分割を行い、図１に示すようにツリーｔを複数（本実施形態では２つ）のセグメントｇ１およびｇ２に分割する。図１では、セグメントｇ１には文書集合ｓ１を構成する文書ｄ１３、文書集合ｓ２を構成する文書ｄ２２，ｄ２３、および文書集合ｓ３を構成する文書ｄ３３からなる４つの文書が存在し、セグメントｇ２には文書集合ｓ１を構成する文書ｄ１１，ｄ１２、文書集合ｓ２を構成する文書ｄ２１、および文書集合ｓ３を構成する文書ｄ３１，ｄ３２からなる５つの文書が存在する。
【００５７】
なお、上述したように分割した各セグメントを１つの次元と考え、それぞれの次元での値に基づき特徴を表現するものであるが、この場合に分割数が少ないと、特徴を十分に表現することができず、反対に分割数が多すぎると、分割されたセグメント当たりの文書数が少なくなって、データに対する信頼性が低下するので、本実施形態のようにＭＤＬ基準を用いることが有効である。
【００５８】
この分割では、最小スパン木をＭＤＬ基準に基づき、
Ｌ＝Ｌ１＋Ｌ２
で表される記述長Ｌを最小とするような条件でいくつかのセグメントに分割する。なお、Ｌ１は分割モデルの記述長であり、Ｌ２は分割モデルの与えられたデータを記述するのに必要な記述長である。
【００５９】
本実施形態では、Ｌ１は最小スパン木を分割したセグメントを記述するものであり、構成した最小スパン木からどの枝を取り除くかによって表現できる。従って、ドキュメントの数をｎ、セグメント分割の数をｒ本としたときにセグメント分割の場合はn-1Ｃr-1通りあり、それを表現するための符号長は、
Ｌ１＝ｌｏｇ2 （n-1Ｃr-1）
で表現することができる。また、Ｌ２は、各セグメントにおける文書集合中の文書の対数尤度の和であり、セグメントｓｅｇiにおける文書集合中の文書の対数 尤度を、
【数１】
0003812799.tif 000002
と表すと、
【数２】
0003812799.tif 000003
で表現できる。ここで、ｎ（Ｓj，ｓｅｇi）は、セグメントｓｅｇi中の文書集 合Ｓjに属する文書の数である。一般に、分割数が増えると、Ｌ１は増加し、Ｌ ２は減少する。
【００６０】
次に、それぞれの文書集合ｓ１，ｓ２，ｓ３について、分割した各セグメントｇ１，ｇ２の中にいくつの文書が含まれるかという分布、すなわち各文書集合ｓ１，ｓ２，ｓ３を構成する各文書の、各セグメントｇ１，ｇ２中における数を各文書集合ｓ１，ｓ２，ｓ３の特徴として決定する。
【００６１】
このベクトルデータである特徴量の決定では、各文書の分布において、文書集合ｓ１の各文書ｄ１１，ｄ１２，ｄ１３のうち、１つの文書ｄ１３がセグメントｇ１に存在し、２つの文書ｄ１１，ｄ１２がセグメントｇ２に存在するので、文書集合ｓ１の特徴量はｓ１（１，２）となる。同様に、文書集合ｓ２の各文書ｄ２１，ｄ２２，ｄ２３のうち、２つの文書ｄ２２，ｄ２３がセグメントｇ１に存在し、１つの文書ｄ２１がセグメントｇ２に存在するので、文書集合ｓ２の特徴量はｓ２（２，１）となる。また、文書集合ｓ３の各文書ｄ３１，ｄ３２，ｄ３３のうち、１つの文書ｄ３３がセグメントｇ１に存在し、２つの文書ｄ３１，ｄ３２がセグメントｇ２に存在するので、文書集合ｓ３の特徴量はｓ３（１，２）となる。
【００６２】
なお、各セグメントｇ１，ｇ２の中における各文書の数である各文書集合の特徴量は、正規化された分布として取り扱われるが、この正規化処理は、分割された各セグメントによって表現される空間上で、文書集合Ｓjの特徴量を次に示す ベクトル形式の式に代入することにより行われる。
【００６３】
｛n(Ｓj，seg1)-mseg1}/σseg1,{n(Ｓj,seg2)-mseg2}/σseg2
ここで、ｍｓｅｇiは、セグメントｉ中の文書集合Ｓjの要素数の平均、σｓｅｇiは、セグメントｉ中の文書集合Ｓjの要素数の標準偏差である。
【００６４】
そして、上式から各文書集合ｓ１，ｓ２，ｓ３の特徴量を正規化すると、次のようになる。
【００６５】
ｓ１（１，２）→（-1/21/2 ，1/21/2)
ｓ２（２，１）→（2/21/2 ,-2/21/2 )
ｓ３（１，２）→（-1/21/2 ,1/21/2 )
以後の実施例の説明における文書集合ｓ１，ｓ２，ｓ３の特徴量ｓ１（１，２），ｓ２（２，１），ｓ３（１，２）の値は、正規化したものである。
【００６６】
このように各文書集合ｓ１，ｓ２，ｓ３の特徴量が決定されると、これらの文書集合ｓ１，ｓ２，ｓ３から参照文書集合に類似する文書集合を検索するには、参照文書集合の特徴量を同様に決定し、この参照文書集合の特徴量と各文書集合ｓ１，ｓ２，ｓ３の特徴量とを比較することにより、参照文書集合に類似した文書集合を検索することができるものである。
【００６７】
図２は、本発明の他の実施形態に係る文書集合検索方法を説明するための図であり、本実施形態の文書集合検索方法は上述した図１の実施形態の文書集合特徴化方法を利用して、文書集合の検索を行うものである。
【００６８】
図２に示す実施形態は、図１の実施形態において説明したように特徴量ｓ１（１，２），ｓ２（２，１），ｓ３（１，２）が決定された各文書集合ｓ１，ｓ２，ｓ３を検索対象文書集合とし、この検索対象文書集合ｓ１，ｓ２，ｓ３から参照文書集合ｒに類似する文書集合をそれぞれの特徴量に基づいて検索するものである。本実施形態では、参照文書集合ｒは、文書集合ｓ１と同じものである。
【００６９】
すなわち、参照文書集合ｒの特徴量は、図１に示した文書集合特徴化方法により（１，２）として決定されているとすると、参照文書集合ｒの特徴量ｒ（１，２）と検索対象文書集合ｓ１，ｓ２，ｓ３のそれぞれの特徴量ｓ１（１，２），ｓ２（２，１），ｓ３（１，２）を比較する。この比較の結果、参照文書集合ｒの特徴量ｒ（１，２）は、自分自身を除いた検索対象文書集合ｓ３の特徴量ｓ３（１，２）に一致し、参照文書集合ｒは文書集合ｓ３に類似していることがわかり、この文書集合ｓ３が検索結果として出力されることになる。なお、検索装置として考えた場合には、単一の文書の類似度を求める手段やそのために単語を抽出する手段が必要となることは勿論のことである。
【００７０】
次に、図３を参照して、図２に示した文書集合検索方法を実施する文書集合検索装置について説明する。
【００７１】
図３に示す文書集合検索装置は、文書集合を構成する全文書に出現する単語を抽出する出現単語抽出手段１、この出現単語抽出手段１で抽出した単語に基づき各文書間の距離（類似度）を計算する文書間距離計算手段３、この文書間距離計算手段３で計算した各文書間の距離に基づきツリーを作成するツリー作成手段５、このツリー作成手段５で作成されたツリーをいくつかのセグメントに分割するセグメント分割手段７、このセグメント分割手段７で分割した各セグメントの中にいくつの文書が含まれるかという分布を要素とするベクトルデータを各文書集合の特徴量として生成するベクトルデータ生成手段９、このベクトルデータ生成手段９で生成した文書集合の特徴量に基づき参照文書集合に類似する文書集合を検索する検索手段１１、およびこの検索手段１１による検索結果である参照文書集合に類似した文書集合を提示する提示手段１３から構成されている。
【００７２】
なお、上述したように、ツリー作成手段５で作成されるツリーは、全文書の類似度を尺度とした最小スパン木であり、またセグメント分割手段７は、ツリー作成手段５で作成されたツリーである最小スパン木をＭＤＬ基準に基づいていくつかのセグメントに分割するものである。
【００７３】
このように構成される文書集合検索装置では、複数の文書集合を構成する全文書に出現する単語を出現単語抽出手段１で抽出し、この抽出した全文書の単語に基づいて各文書間の距離を文書間距離計算手段３で計算する。それから、この計算した各文書間の距離に基づきツリーである最小スパン木をツリー作成手段５で作成する。そして、セグメント分割手段７は、ツリー作成手段５で作成されたツリーをＭＤＬ基準に基づきいくつかのセグメントに分割する。
【００７４】
次に、ベクトルデータ生成手段９は、セグメント分割手段７で分割した各セグメントの中にいくつの文書が含まれるかという分布を要素とするベクトルデータを各文書集合の特徴量として生成する。検索手段１１は、ベクトルデータ生成手段９で生成した文書集合の特徴量に基づき参照文書集合に類似する文書集合を複数の文書集合の中から検索する。なお、この場合、参照文書集合の特徴量も同様な手法で生成し、この生成した参照文書集合の特徴量と先に生成した文書集合の特徴量に基づき参照文書集合に類似する文書集合を複数の文書集合の中から検索することになる。この検索手段１１の検索結果は、提示手段１３により利用者に例えば視覚的に提示されることになる。
【００７５】
ベクトルデータ生成手段９で生成されたベクトルデータである各文書集合の特徴量は、各セグメントに含まれるかという文書の分布であり、図１、図２で示したように、例えばｓ１（１，２），ｓ２（２，１），ｓ３（１，２）のように生成されるが、この特徴量であるベクトルデータから各ベクトル間の距離、すなわち類似度の逆数を算出することができるものである。
【００７６】
また、この特徴量を表すベクトルの次数は２次元よりも大きいものである場合には、そのまま平面上に表すことができないため、主成分分析を用いて、２次元のデータに変換し、２次元のデータとして座標にとらえ、平面上の位置として提示手段１３により提示されるようになっている。
【００７７】
図４は、上述したように生成した各文書集合の特徴量に基づき各文書集合である各サイト、本例では複数の学校（school）の類似関係を視覚的に表現したサイトマップを示す図である。このサイトマップは、上述したような主成分分析によって得られた２次元のデータに基づいて作成されている。
【００７８】
図４において、座標軸の値は各学校の特徴量、すなわち主成分分析によって得られた２次元のデータの値を示している。主成分分析で得られた２次元のデータ（座標）は、元のデータの距離関係を保存するように求められる。従って、サイトマップの位置関係から類似度の高いもの、すなわちサイトマップ上で近いものと類似度の高くないもの、すなわち近くないものとを視覚的に識別することができる。
【００７９】
また、本発明は、基準となる文書集合に対して、他の文書集合、例えばＷｅｂのサイトを視覚的に、例えば内容の近いものを近くに内容の遠いものを遠くに表示するような文書集合間のナビゲーション装置にも適用可能である。
【００８０】
【発明の効果】
以上説明したように、本発明によれば、全文書で文書間の距離に基づき構成した最小スパン木をセグメントに分割し、各セグメントにおける文書の分布を要素とするベクトルデータを文書集合の特徴量とするので、この特徴量を使用することにより、文書集合の類似性を適確に判定でき、更に特徴量から得られる類似度を用いて、文書集合の検索も適確に行うことができる。
【００８２】
更に、本発明によれば、全文書に出現する単語に基づき計算された各文書間の距離に基づき全文書で最小スパン木を作成し、この最小スパン木をセグメントに分割し、各セグメントにおける文書の分布を要素とするベクトルデータを生成し、このベクトルデータで文書集合の特徴量を表現するので、この特徴量を使用することにより、文書集合の類似性を適確に判定でき、更に特徴量から得られる類似度を用いて、文書集合の検索も適確に行うことができる。
【００８４】
また、本発明によれば、検索対象文書群と参照文書集合で文書間の距離に基づき最小スパン木を作成し、この最小スパン木をセグメントに分割し、各セグメント中における参照文書の分布を要素とする参照ベクトルデータを参照文書集合の特徴量とし、検索対象文書の分布を要素とする検索対象ベクトルデータを検索対象文書集合の特徴量とし、各特徴量に基づき参照文書集合に類似する文書集合を検索対象文書群から検索するので、参照文書集合に類似する文書集合を適確に検索することができる。
【００８５】
更に、本発明によれば、参照文書集合と検索対象文書群に出現する単語に基づき計算した文書間距離に基づき検索対象文書群と参照文書集合で最小スパン木を作成し、この最小スパン木をセグメントに分割し、各セグメント中における参照文書の分布を要素とする参照ベクトルデータを生成するとともに検索対象文書の分布を要素とする検索対象ベクトルデータを生成し、参照ベクトルデータを参照文書集合の特徴量とし、検索対象ベクトルデータを検索対象文書集合の特徴量とし、参照文書集合に類似する文書集合を検索対象文書群から検索するので、参照文書集合に類似する文書集合を適確に検索することができる。
【００８６】
本発明によれば、参照ベクトルデータおよび検索対象ベクトルデータを主成分分析して２次元上に表現するので、特徴量を平面上の位置として表現でき、視覚的に理解しやすくなる。
【００８７】
また、本発明によれば、最小スパン木を使用するので、クラスタリングのアルゴリズムが単純であり、大量の文書を扱う場合に時間的に優位である。
【００８８】
更に、本発明によれば、ツリーはＭＤＬ（最小記述長）基準に基づいていくつかのセグメントに分割されるので、最適な分割数を決定でき、信頼性を向上することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る文書集合特徴化方法を説明するための図である。
【図２】本発明の他の実施形態に係る文書集合検索方法を説明するための図である。
【図３】図２に示した文書集合検索方法を実施する文書集合検索装置の構成を示すブロック図である。
【図４】各文書集合の特徴量に基づき各文書集合の各サイトの類似関係を表したサイトマップを示す図である。
【符号の説明】
１  出現単語抽出手段
３  文書間距離計算手段
５  ツリー作成手段
７  セグメント分割手段
９  ベクトルデータ生成手段
１１  検索手段
１３  提示手段
【図１】
0003812799.tif 000004
【図２】
0003812799.tif 000005
【図３】
0003812799.tif 000006
【図４】
0003812799.tif 000007