(57)【要約】【課題】高次元の文書ベクトルを適切に圧縮、離散化し、ベイジアンネットワークによる分類学習および文書分類を可能にする。【解決手段】文書の特長をあらわす高次元ベクトルを、主成分分析などの行列演算により低次元近似し、ＭＤＬ基準などのモデル選択基準にもとづく離散化と素性選択を行い、ベイジアンネットワークの入力とする。【特許請求の範囲】
【請求項１】
各文書に対して、決められたカテゴリに属すかどうかがラベル付けされている学習用文書集合を用いて、教師あり学習を行ったベイジアンネットワークを用いて、新規に与えられる各文書が各カテゴリに属す確率を計算する文書分類方法において、前記ベイジアンネットワークへの入力として、各文書の持つ特徴を表す高次元ベクトルを、学習データに基づく行列演算による次元圧縮により低次元近似して得られる実数ベクトルに対して、モデル選択基準を用いた学習に基づく区間分割を行って得られる離散値からなる素性ベクトルを用いることを特徴とする文書分類方法。
【請求項２】
請求項１記載の文書分類方法において、とくに、前記行列演算による次元圧縮の手法として、対応分析を用いることを特徴とする文書分類方法。
【請求項３】
請求項１の文書分類方法において、とくに、前記区間分割のための学習において、モデル選択規準に基づいて使用するモデル選択基準として、ＭＤＬ（最小記述長）規準を用いることを特徴とする文書分類方法。
【請求項４】
学習用文書を格納する学習用文書格納部と、
単語の文字列を格納した単語辞書と、
前記学習用文書格納部に格納された学習用文書に出現する単語の頻度を数えて単語文書行列を作成する単語文書行列作成部と、
作成された単語文書行列に対して対応分析を行い、学習用文書特徴ベクトルと単語の特徴を表す単語特徴ベクトルを生成する対応分析実行部と、
対応分析により得られた単語特徴ベクトルを格納する単語特徴ベクトル格納部と、
対応分析により得られた学習用文書ベクトルを格納する学習用文書ベクトル格納部と、
学習用の各文書がどのカテゴリに属すかに関する情報を格納する学習用カテゴリ情報格納部と、
前記学習用文書ベクトルの集合と前記学習用カテゴリ情報離散化パラメータを計算する離散化パラメータ計算部と、
前記離散化パラメータ計算結果を格納する離散化パラメータ格納部と、
前記学習用文書特徴ベクトル格納部に格納されている学習用文書特徴ベクトルから、ベイジアンネットワークの学習に用いる学習用素性ベクトルを作成する学習用素性ベクトル作成部と、
前記学習用素性ベクトル作成部および学習用カテゴリ情報格納部からの情報を利用して、各カテゴリごとにベイジアンネットワークを学習するベイジアンネットワーク学習部と、
前記ベイジアンネットワーク学習部における学習によって得られたベイジアンネットワークを格納するベイジアンネットワーク格納部とを備えた文書分類用の学習装置。
【請求項５】
単語文書行列作成部は、学習用文書格納部に格納された学習用文書に出現する単語の頻度を数え文書ベクトルを作り、それらを行方向に連結して単語文書行列を作成することを特徴とする請求項４記載の文書分類用の学習装置。
【請求項６】
離散化パラメータ計算部は、前記学習用文書特徴ベクトル格納部に格納されている学習用文書の文書ベクトルの集合と前記学習用カテゴリ情報格納部に格納されている学習用カテゴリ情報から、ベイジアンネットワークの学習に用いる学習要素性ベクトルをつくるために、学習用ＭＤＬ・規準に基づいて、前記文書特徴ベクトルの各軸から各軸の値を離散化するための区切り情報を計算し、区切り情報が得られた軸を各カテゴリの素性ベクトルにおいて使用する軸（有効軸）として選ぶことを特徴とする請求項５記載の文書分類用の学習装置。
【請求項７】
ベイジアンネットワーク学習部は、前記学習用素性ベクトル作成部により作成された学習用素性ベクトルと、前記学習用カテゴリ情報格納部に格納されている学習用カテゴリ情報とを利用して、各カテゴリごとに、文書の当該カテゴリへの所属確率を計算するベイジアンネットワークを学習することを特徴とする請求項６記載の文書分類用の学習装置。
【請求項８】
請求項４記載の文書分類用の学習装置と、
分類対象となる文書を入力する分類対象文書入力部と、
前記学習装置の単語辞書を用いて、分類対象の文書に対して文書ベクトルを作成する分類対象文書ベクトル作成部と、
前記分類対象文書ベクトル作成部および前記学習装置の単語特徴ベクトル格納部に接続された分類対象文書特徴ベクトル作成部と、
前記学習装置の離散化パラメータ格納部に接続された分類対象素性ベクトル作成部と、
前記分類対象文書素性ベクトル作成部と前記学習装置のベイジアンネットワーク格納部に接続された所属確率計算部と、
前記所属確率計算部による計算結果を出力する、分類結果出力部を備えた文書分類装置。
【請求項９】
分類対象文書特徴ベクトル作成部は、前記分類対象文書ベクトル作成部により作成された分類対象文書ベクトルと、前記単語特徴ベクトル格納部に格納されている単語特徴ベクトルの集合を用いて、分類対象文書における各単語の出現度数に基づいて分類対象文書特徴ベクトルを計算することを特徴とする請求項８記載の文書分類装置。
【請求項１０】
分類対象素性ベクトル作成部は、各カテゴリに対して、前記離散化パラメータ格納部に格納されている離散化パラメータに基づいて、前記分類対象文書特徴ベクトルから当該カテゴリへの分類判定において用いる素性値を抽出して離散化することを特徴とする請求項９記載の文書分類装置。
【請求項１１】
所属確率計算部は、前記分類対象素性ベクトル作成部によって作成された、各カテゴリごとに離散化された分類対象文書素性ベクトルと、前記ベイジアンネットワーク格納部に格納されたベイジアンネットワークを用いて、当該文書が各カテゴリに属する確率を計算することを特徴とする請求項１０記載の文書分類装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、与えられた文書が、一つ以上のあらかじめ決められた特定のカテゴリに属すかどうかを判定する文書分類方法及び装置に関する。特に、本発明は、文書分類の種々の手法の中の、ベイジアンネットワークを使った確率的文書分類手法に対する改良を行なうものである。
【０００２】
【従来の技術】
文書分類は、与えられた文書が、与えられた特定のカテゴリに属すかどうか判定するもので、さまざまな手法が提案されているが、その中の一つに、ベイジアンネットワークを使った確率的文書分類手法がある。
【０００３】
文書分類に関しては、この他にも、文書が特定のキーワードを含むかどうかに基づく文書分類方法や、文書内に生起する単語の頻度を元に、文書をあらわす多次元のベクトル表現を生成し、多次元ベクトル空間に文書を配置し、ベクトル間の距離や内積などの比較により判定する文書分類方法などがあるが、これらの文書分類方法の詳細に関しては、たとえば非特許文献１に記載がある。
【０００４】
ベイジアンネットワークを使った文書分類において、特定の文書が特定のカテゴリに属すかどうかを判定する際は、分類対象となる文書から、当該カテゴリへの分類において用いる素性値をあらかじめ定められた基準に従って抽出し、それらのベクトル（以下、素性ベクトルと呼ぶ）が得られたときの、当該文書の当該カテゴリへの所属確率をベイズの定理を用いて計算する。ここで用いられる素性値の抽出方法や、所属確率の計算に用いるパラメータは、通常、それぞれの文書がどのカテゴリに属すかの情報が付与された学習用文書集合から機械学習によって計算されて、装置の内部に保持されている。ベイジアンネットワークによる文書分類に関しては、たとえば非特許文献２に記載がある。
【０００５】
しかし、ベイジアンネットワークによる分類における一般的な課題として、分類に用いる素性の数が多くなると、ベイジアンネットワークの学習が計算量的に困難になる。また、素性の組み合わせの数に比べてデータの数が少なくなることから生じる「過適応」により、結果の分類精度が悪くなる、という、機械学習一般に当てはまる弊害も出てくる。
【０００６】
特に、文書分類においては、各文書に出てくる単語の生起頻度を素性として用いる場合が多いが、一般的に大量の文書に出てくる単語の種類は数十万規模であり、それらを別々の素性とした場合には、上記の素性数が多くなることによる問題が発生する。したがって、通常、文書から抽出した素性の集合から、実際に分類に用いる素性の集合を選択する、素性選択が行われる。
【０００７】
素性選択の手法としては、単語の頻度を用いる方法、単語の頻度とカテゴリへの所属・非所属の間の相互情報量を用いる方法、などが提案されている。素性選択の主な手法に関しては、たとえば非特許文献３に記載がある。
【０００８】
また、ベクトル空間法によるテキスト検索における次元圧縮の手法の一つであるＬＳＡ法については、たとえば非特許文献４に記載がある。
【０００９】
また、多変量解析の一手法である対応分析に関しては、たとえば非特許文献５に記載がある。
【００１０】
また、ＭＤＬ基準を用いた連続値の離散化手法については、たとえば非特許文献６に記載がある。
【００１１】
【非特許文献１】永田昌明（２００３）：“確率モデルによる自然言語処理”、甘利俊一他編「言語と心理の統計    ことばと行動の確率モデルによる分析」、岩波書店、  ５９−１２８．
【非特許文献２】Ｋｏｌｌｅｒ，  Ｄ．  ａｎｄ  Ｓａｈａｍｉ，  Ｍ．  （１９９７），  ”Ｈｉｅｒａｒｃｈｉｃａｌｌｙ  ｃｌａｓｓｉｆｙｉｎｇ  ｄｏｃｕｍｅｎｔｓ  ｕｓｉｎｇ  ｖｅｒｙ  ｆｅｗ  ｗｏｒｄｓ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＣＭＬ−９７，  １４ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ，  １７０−−１７８．
【非特許文献３】Ｙａｎｇ，  Ｙ．  ａｎｄ  Ｐｅｄｅｒｓｅｎ，  Ｊ．Ｏ．，（１９９７），  ”Ａ  ｃｏｍｐａｒａｔｉｖｅ  ｓｔｕｄｙ  ｏｎ  ｆｅａｔｕｒｅ  ｓｅｌｅｃｔｉｏｎ  ｉｎ  ｔｅｘｔ  ｃａｔｅｇｏｒｉｚａｔｉｏｎ”，  Ｐｏｒｃ．ｏｆ  ｔｈｅ  Ｆｏｕｒｔｅｅｎｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｃｈｉｎ  Ｌｅａｒｎｉｎｇ  （ＩＣＭＬ−９７），  ４１２−４２０．
【非特許文献４】Ｄｅｅｒｗｅｓｔｅｒ，  Ｓ．Ｃ．  ｅｔ  ａｌ．，  （１９９０）  ”Ｉｎｄｅｘｉｎｇ  ｂｙ  ｌａｔｅｎｔ  ｓｅｍａｎｔｉｃ  ａｎａｌｙｓｉｓ”，  Ｊｏｕｎａｌ  ｏｆ  ｔｈｅ  Ａｍｅｒｉｃａｎ  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｃｉｅｎｃｅ，  ４１（６），  ３９１−４０７
【非特許文献５】大津起夫（２００３）：“社会調査データからの推論：実践的入・・門”、甘利俊一他編「言語と心理の統計    ことばと行動の確率モデルによる分・・析」、岩波書店、  １２９−１７７．
【非特許文献６】Ｆａｙｙａｄ，  Ｕ．Ｍ，  ａｎｄ  Ｉｒａｎｉ，  Ｋ．Ｂ，  （１９９３）  ”Ｍｕｌｔｉ−ｉｎｔｅｒｖａｌ  ｄｓｃｒｅｔｉｚａｔｉｏｎ  ｏｆ  ｃｏｎｔｉｎｕｏｕｓ−ｖａｌｕｅｄ  ａｔｔｒｉｂｕｔｅｓ  ｆｏｒ  ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｌｅａｒｎｉｎｇ”，・  Ｉｎ  ＩＪＣＡＩ  ’９３  １０２２−１０２７．
【００１２】
【発明が解決しようとする課題】
ベイジアンネットを使った文書分類における従来の素性選択手法は、いずれも、単語の頻度や相互情報量が一定のしきい値以上のものを素性として残し、しきい値に満たないものを捨てるという方法であるため、まず、しきい値に満たない単語に関する情報がすべて失われてしまうという欠点があった。
【００１３】
また、特に、一般的な語よりも出現頻度の少ない語、長い文書よりも簡潔な文書の方が、カテゴリの特徴を表しやすく、重みを重くした方が直感にあうが、どのような規準で重みをつければよいかに関しては、経験的な手法に頼らざるを得なかった。
【００１４】
また、素性選択に利用されるしきい値についても、自動的に決定する方法がなく、利用者が、そのつど試行錯誤によりしきい値を決めなくてはならないという問題もあった。
【００１５】
本発明は、上記従来の不具合に鑑みてなされたもので、その第１の目的は、一定の基準に満たない単語に関する情報が考慮されつつ文書分類を実行することができる文書分類方法及び装置を提供することである。
【００１６】
本発明の第２の目的は、学習データをベイジアンネットワークの学習に適した形にし、その学習データを基に文書分類が行なえる文書分類方法及び装置を提供することである。
【００１７】
【課題を解決するための手段】
上記目的を達成するため、本発明は、文書分類方法として、各文書に対して、決められたカテゴリに属すかどうかがラベル付けされている学習用文書集合を用いて、教師あり学習を行ったベイジアンネットワークを用いて、新規に与えられる各文書が各カテゴリに属す確率を計算する文書分類方法において、前記ベイジアンネットワークへの入力として、各文書の持つ特徴を表す高次元ベクトルを、学習データに基づく行列演算による次元圧縮により低次元近似して得られる実数ベクトルに対して、モデル選択基準を用いた学習に基づく区間分割を行って得られる離散値からなる素性ベクトルを用いるようにしたものである。
【００１８】
本発明の文書分類方法は、行列演算による次元圧縮法を用いて、各文書に対する文書ベクトルを、より次元数の低いベクトルにより近似し、ベイジアンネットワークを用いた文書分類の入力として用いる。行列演算による次元圧縮の主な手法としては、特異値分解や主成分分析、対応分析などが知られている。特に、文書分類においては、特異値分解を用いたＬＳＡ法と呼ばれる次元圧縮方が多く用いられている。ただし、上記行列演算による次元圧縮の結果得られるベクトルの成分は、一般に実数となるが、一般にベイジアンネットワークにおいては、用いられる素性の値は離散値でなくてはならない。したがって、上記本発明の文書分類方法においては、新しい素性ベクトルの各要素に対して、離散化を行う、素性ベクトル離散化処理を行うステップを設ける。行列演算による次元圧縮は、特定の行または列に関する情報が完全に捨て去られることはないので、一定の基準に満たない単語に関する情報がすべて落とされるという問題が解決される。
【００１９】
さらに、本発明の別の態様に係る文書分類方法は、上記次元圧縮法として、多変量解析の一手法である対応分析の手法を用いる。対応分析は、２つの離散値変数の間の関係を分析する手法の一つで、心理学や社会学などで広く利用されている手法であるが、ＬＳＡ法や主成分分析などの行列計算による他の次元圧縮方に比べて、一般的に、頻度の少ない素性値をとるデータの方が、頻度の大きい素性値をとるデータより結果に与える影響が大きくなるという性質を持つ。非特許文献５参照。これは、文書分類の場合に当てはめると、頻度の少ない語や文書長の短い文書を重視する、ということに相当する。これは、普遍的な語の影響は小さくし、簡潔な文書の影響を高くすることであるので、直感的にも妥当である。実際、従来のベクトル空間法では、文書を表すベクトルを作る際に、各単語の生の生起頻度でなく、ｉｄｆという文書集合中の当該単語のあらわれる文書数の割合の逆数のｌｏｇを取ったものをかける、というｔｆ．ｉｄｆという重み付けが行われているが、これも普遍的な語の影響を小さくすることを目的としたものである。ただし、本発明において用いている対応分析においては、簡潔な文書の影響を高くする効果も得られる。
【００２０】
さらに、本発明の別の態様に係る文書分類方法は、上記素性ベクトル離散化部における、モデル選択規準としてＭＤＬ規準に基づいて学習された区間分割による離散化を行い、区切り点が得られた素性（軸）のみを分類に用いるようにした。ＭＤＬ規準は、系と学習データを記述するのに必要となる最小記述長が最小になるモデルを選択する、というもので、系の複雑さによる予測性能の向上と、学習に使ったデータの量とのバランスをとるもので、機械学習において過適応を防ぐ手法として使われている。ＭＤＬ規準を用いたデータの離散化に関しては、非特許文献６があるが、本発明は、Ｆａｙｙａｄ  ＆  Ｉｒａｎｉの手法を、次元圧縮により求めた文書特徴ベクトルの再離散化に用いるものであり、これにより、文書を表すベクトルを、ベイジアンネットワークの入力としてふさわしい離散値を取るベクトルに変換可能になるとともに、分類において有効な素性とそうでない素性を区別する作用も持つので、各カテゴリへの分類にとって効果のない素性の使用を排除でき、素性の数を絞り込むことができるので、分類装置を過適応に陥りにくくすることが可能になるとともに、ベイジアンネットワークの学習における計算量的側面からも好ましい性質を持つ。また、ＭＤＬ規準においては、有効な素性と有効でない素性は、自動的に計算される基準に従って区別されるので、利用者が閾値を試行錯誤により設定する負担もなくなる。
【００２１】
本発明はまた、文書分類用の学習装置を、学習用文書を格納する学習用文書格納部と、単語の文字列を格納した単語辞書と、前記学習用文書格納部に格納された学習用文書に出現する単語の頻度を数えて単語文書行列を作成する単語文書行列作成部と、作成された単語文書行列に対して対応分析を行い、学習用文書特徴ベクトルと単語の特徴を表す単語特徴ベクトルを生成する対応分析実行部と、対応分析により得られた単語特徴ベクトルを格納する単語特徴ベクトル格納部と、対応分析により得られた学習用文書ベクトルを格納する学習用文書ベクトル格納部と、学習用の各文書がどのカテゴリに属すかに関する情報を格納する学習用カテゴリ情報格納部と、前記学習用文書ベクトルの集合と前記学習用カテゴリ情報離散化パラメータを計算する離散化パラメータ計算部と、前記離散化パラメータ計算結果を格納する離散化パラメータ格納部と、前記学習用文書特徴ベクトル格納部に格納されている学習用文書特徴ベクトルから、ベイジアンネットワークの学習に用いる学習用素性ベクトルを作成する学習用素性ベクトル作成部と、前記学習用素性ベクトル作成部および学習用カテゴリ情報格納部からの情報を利用して、各カテゴリごとにベイジアンネットワークを学習するベイジアンネットワーク学習部と、前記ベイジアンネットワーク学習部における学習によって得られたベイジアンネットワークを格納するベイジアンネットワーク格納部とから構成したものである。そして、この文書分類用の学習装置に、分類対象となる文書を入力する分類対象文書入力部と、前記学習装置の単語辞書を用いて、分類対象の文書に対して文書ベクトルを作成する分類対象文書ベクトル作成部と、前記分類対象文書ベクトル作成部および前記学習装置の単語特徴ベクトル格納部に接続された分類対象文書特徴ベクトル作成部と、前記学習装置の離散化パラメータ格納部に接続された分類対象素性ベクトル作成部と、前記分類対象文書素性ベクトル作成部と前記学習装置のベイジアンネットワーク格納部に接続された所属確率計算部と、前記所属確率計算部による計算結果を出力する、分類結果出力部とを備えることにより文書分類装置が構成される。
【００２２】
【発明の実施の形態】
以下に、本発明の実施の形態を図面を用いながら説明する。図１は、本発明の一実施の形態に係る文書分類装置の構成を示すブロック図である。この実施の形態に係る文書分類装置は、学習用文書を格納する学習用文書格納部（１０１）と、単語の文字列を格納した単語辞書（１０２）と、学習用文書格納部（１０１）と単語辞書（１０２）とに接続された単語文書行列作成部（１０３）と、単語文書行列作成部（１０３）で作成された単語文書行列に対して、対応分析を行って学習用文書特徴ベクトルと単語の特徴を表す単語特徴ベクトルを生成する対応分析実行部（１０４）と、対応分析により得られた単語特徴ベクトルを格納する単語特徴ベクトル格納部（１０５）と、対応分析により得られた学習用文書特徴ベクトルを格納する学習用文書特徴ベクトル格納部（１０６）と、学習用の各文書がどのカテゴリに属するかに関する情報（学習用カテゴリ情報）を格納する学習用カテゴリ情報格納部（１０７）と、上記学習用文書特徴ベクトルの集合と上記学習用カテゴリ情報から離散化パラメータを計算する離散化パラメータ計算部（１０８）と、上記離散化パラメータの計算結果を格納する離散化パラメータ格納部（１０９）と、上記学習用文書特徴ベクトル格納部（１０６）に格納されている学習用文書特徴ベクトルから、ベイジアンネットワークの学習に用いる学習用素性ベクトルを作成する学習用素性ベクトル作成部（１１０）と、上記学習用素性ベクトル作成部（１１０）と上記学習用カテゴリ情報格納部（１０７）に接続されたベイジアンネットワーク学習部（１１１）と、上記ベイジアンネットワーク学習部（１１１）によって学習されたベイジアンネットワークを格納するベイジアンネットワーク格納部（１１２）とを備えている。
【００２３】
そして、上記学習用文書格納部（１０１）、単語辞書（１０２）、単語文書行列作成部（１０３）、対応分析実行部（１０４）、単語特徴ベクトル格納部（１０５）、学習用文書特徴ベクトル格納部（１０６）、学習用カテゴリ情報格納部（１０７）、離散化パラメータ計算部（１０８）、離散化パラメータ格納部（１０９）、学習用素性ベクトル作成部（１１０）、ベイジアンネットワーク学習部（１１１）、およびベイジアンネットワーク格納部（１１２）により文書分類用の学習装置を構成している。
【００２４】
本実施の形態に係る文書分類装置はまた、分類対象となる文書を入力する分類対象文書入力部（１１３）と、上記単語辞書（１０２）を用いて、分類対象の文書に対して文書ベクトルを作成する分類対象文書ベクトル作成部（１１４）と、上記分類対象文書ベクトル作成部（１１４）および単語特徴ベクトル格納部（１０５）に接続された分類対象文書特徴ベクトル作成部（１１５）と、上記離散化パラメータ格納部（１０９）に接続された分類対象素性ベクトル作成部（１１６）と、上記分類対象素性ベクトル作成部（１１６）と上記ベイジアンネットワーク格納部（１１２）とに接続された所属確率計算部（１１７）と、上記所属確率計算部による計算結果を出力する、分類結果出力部（１１８）とを備えている。
【００２５】
単語文書行列作成部（１０３）は、学習用文書格納部（１０１）・に格納された学習用文書に出現する単語の頻度を数え文書ベクトルを作り、それらを行方向に連結して単語文書行列を作成する。離散化パラメータ計算部（１０８）は、上記学習用文書特徴ベクトル格納部（１０６）に格納されている学習用文書の文書ベクトルの集合と上記学習用カテゴリ情報格納部（１０７）に格納されている学習用カテゴリ情報から、ベイジアンネットワークの学習に用いる学習要素性ベクトルをつくるために、学習用ＭＤＬ・規準に基づいて、上記文書特徴ベクトルの各軸から、各軸の値を離散化するための区切り情報を計算し、区切り情報が得られた軸を各カテゴリの素性ベクトルにおいて使用する軸（有効軸）として選ぶ。ベイジアンネットワーク学習部（１１１）は、上記学習用素性ベクトル作成部（１１０）により作成された学習用素性ベクトルと、上記学習用カテゴリ情報格納部（１０７）に格納されている学習用カテゴリ情報とを利用して、各カテゴリごとに、文書の当該カテゴリへの所属確率を計算するベイジアンネットワークを学習する。
【００２６】
分類対象文書特徴ベクトル作成部（１１５）は、上記分類対象文書ベクトル作成部（１１４）により作成された分類対象文書ベクトルと、上記単語特徴ベクトル格納部（１０５）に格納されている単語特徴ベクトルの集合を用いて、分類対象文書における各単語の出現度数に基づいて分類対象文書特徴ベクトルを計算する。分類対象素性ベクトル作成部（１１６）は、各カテゴリに対して、上記離散化パラメータ格納部（１０９）に格納されている離散化パラメータに基づいて、上記分類対象文書特徴ベクトルから当該カテゴリへの分類判定において用いる素性値を抽出して離散化する。所属確率計算部（１１７）は、上記分類対象素性ベクトル作成部（１１６）によって作成された、各カテゴリごとに離散化された分類対象文書素性ベクトルと、上記ベイジアンネットワーク格納部（１１２）に格納されたベイジアンネットワークを用いて、当該文書が各カテゴリに属する確率を計算する。
【００２７】
以下、本実施の形態の文書分類装置の動作について、図２から図１２を用いて説明する。本実施の形態における文書分類装置の動作は、学習フェーズと分類フェーズに分けられる。
【００２８】
まず、学習フェーズの動作について、図２から図１１を用いて説明する。
学習フェーズにおいては、
【００２９】
ステップ１：（図２    ２０１）単語文書行列作成部１０３が、学習用文書格納部１０１に格納されている各学習用文書ｄｄ（ｄ＝１，  …，  Ｍ；Ｍは学習用文書の総数）に対して、上記単語辞書１０２に含まれる各語ｗｗが現れる回数ｆｄ，ｗを調べ、文書ベクトル
【数１】
2004326465.tif 000002
を作る（図３）。ここで、Ｎは、上記辞書に含まれる単語の総数である。そして、
【数２】
2004326465.tif 000003
を第ｄ行とするようなＭ＊Ｎ次元の行列Ｆを作成する。このＦを単語文書行列と呼ぶ。
【００３０】
ステップ２：（図２    ２０２）単語文書行列Ｆに対して対応分析を行い、各単語に対するＫ次元の単語特徴ベクトルと、各文書に対するＫ次元の文書特徴ベクトルを求める。ここで、Ｋは、Ｎにくらべて非常に小さい数で、あらかじめ決めておいてもよいし、累積寄与率に関する閾値を設定してそれを元に実行時に決定されるようにしてもよい。本実施の形態では、あらかじめ２００に設定しておく。
【００３１】
具体的には、
（ｉ）    （図４    ４０１）Ｆの第ｄ行の成分の和をｇｄ（図３）とし、ｇｄをｄ番目の対角要素とする対角行列Ｇを作る。
（ｉｉ）    （図４  ４０２）Ｆの第ｗ列の成分の和をｈｗ（図３）とし、ｈｗをｗ番目の対角要素とする対角行列Ｈを作る。
（ｉｉｉ）    （図４  ４０３）行列Ｇ−１／２ＦＨ−１／２に対して、特異値分解を行い、Ｇ−１／２ＦＨ−１／２＝ＵＤＶＴとする。ここで、Ｕは、Ｍ＊Ｋ次元の正規直交行列である。ＤはＲ次元の対角行列であり、その対角要素は降順に並んでいるとする。また、Ｖは、Ｎ＊Ｋ次元の正規直交行列であり、ＶＴは、Ｖの転置行列を表す。
（ｉｖ）    （図４  ４０４）Ｗｗに対して、
【数３】
2004326465.tif 000004
を単語特徴ベクトルとし、単語特徴ベクトル格納部１０５に格納する。
（ｖ）    （図４  ４０５）文書ｄｄに対して、
【数４】
2004326465.tif 000005
を文書特徴ベクトルとし、学習用文書特徴ベクトル格納部１０６に格納する。
【００３２】
ステップ３：（図２  ２０３）ステップ２で求めた各学習用文書の文書特徴ベクトルと、前記学習用カテゴリ情報格納部１０７に格納された、当該文書がどのカテゴリに属すかに関する情報を元に、離散化パラメータ計算部１０８が、離散化パラメータを計算し、離散化パラメータ格納部１０９に格納する。
具体的には、各カテゴリＣｃに対して、以下のようにしてＣｃに対する離散化パラメータを格納する表ＴＡＢｃ（図７）を学習する。
（ｉ）    （図５    ５０１）ＴＡＢｃを空にする。
（ｉｉ）    （図５    ５０２）未処理の軸の集合＝軸の集合全体とする。ここで、軸とは、文書特徴ベクトルのＫ個の次元の一つ一つを指すとする。
（ｉｉｉ）    （図５    ５０３）未処理の軸がなければ、ＴＡＢｃの学習終了。
（ｉｖ）  （図５    ５０４）未処理の軸ｋを選ぶ。
（ｖ）    （図５    ５０５）全学習用文書の第ｋ成分の集合
【数５】
2004326465.tif 000006
における最小値ａ、最大値ｂ  を求め、ＭＤＬ規準にしたがって、区間［ａ，ｂ］の分割点の集合を得る。このステップについては、後で詳述する。
（ｖｉ）    （図５  ５０６）分割点が得られた場合は、軸番号ｋと、得られた各分割点の値をＴＡＢｃに追加する。得られなかった場合は、軸ｋは、当該カテゴリＣｃは有効でないとして、ＴＡＢｃには追加しない。
（ｖｉｉ）    （図５    ５０７）軸ｋを処理済として、未処理の軸の集合から除く。
（ｖｉｉｉ）    （ｉｉｉ）に戻る。
【００３３】
以下に、上の（ｉｖ）における、ＭＤＬ規準に基づいた分割点の集合の求め方を図６を用いながら説明する。以下では、一般的に、ｍ個の学習用文書に対する文書特徴ベクトルのｋ番目の成分からなる集合
【数６】
2004326465.tif 000007
（うち、異なる値の集合を下記（数７）とする）
【数７】
2004326465.tif 000008
を含む区間
【数８】
2004326465.tif 000009
の分割点の求め方ＤＩＶ（Ｓ，Ｃｃ）として、説明する。
手続きＤＩＶ（Ｓ，  Ｃｃ）
（ａ）    （図６    ６０１）学習用文書特徴ベクトルの第ｋ成分で、区間Ｓに入るものがなければ、Ｓは分割不能として、空集合φを返す。
（ｂ）    （図６    ６０２）分割前の系の最小記述長
【数９】
2004326465.tif 000010
により求める。
ただし、Ｈ（ｃ）（Ｓ）は、ＳのカテゴリＣｃに関するクラスエントロピで、
【数１０】
2004326465.tif 000011
である（対数の底は２。以下同様）。
また、ｐｓ（ｃ）は、文書特徴ベクトルのｋ番目の成分が区間Ｓに入るような文書が、カテゴリＣｃに属す確率の推定値で、ここでは、
【数１１】
2004326465.tif 000012
とする。ただし、
【数１２】
2004326465.tif 000013
は、Ｘ’の要素のうち、カテゴリＣｃに属すものの数とする。
（ｃ）  （図６  ６０３）Ｘ’’の各点
【数１３】
2004326465.tif 000014
に分割したときの系のカテゴリＣｃに関するクラスエントロピ
【数１４】
2004326465.tif 000015
を求める。ただし、
【数１５】
2004326465.tif 000016
は、以下により計算する：
【数１６】
2004326465.tif 000017
ここで、
【数１７】
2004326465.tif 000018
である。
（ｄ）    （図６    ６０４）
【数１８】
2004326465.tif 000019
を与えるｔを分割点の候補とする。
（ｅ）    （ｄ）で求めたｔで、Ｓを
【数１９】
2004326465.tif 000020
に分割したときの、分割後の系の最小記述長ＭＤＬｔを以下により計算する。
【数２０】
2004326465.tif 000021
ただし、
【数２１】
2004326465.tif 000022
は、文書特徴ベクトルの第ｋ成分が区間
【数２２】
2004326465.tif 000023
に属すような学習用文書の集合の中で、カテゴリＣｃに属すものと属さないものがあれば２、どちらかしかなければ１とする。
【数２３】
2004326465.tif 000024
についても同様に、文書特徴ベクトルの第ｋ成分が区間
【数２４】
2004326465.tif 000025
に属すような学習用文書の集合の中で、カテゴリＣｃに属すものと属さないものがあれば２、どちらかしかなければ１とする。
（ｆ）    （図６    ６０６）
【数２５】
2004326465.tif 000026
なら、Ｓは分割不可能として、空集合φを返す。
（ｇ）    （図６    ６０７）
【数２６】
2004326465.tif 000027
を分割点とする。
（ｈ）    （図６    ６０８）手続き
【数２７】
2004326465.tif 000028
の分割点の集合を求め、Ｔ’とする。同様に、手続き
【数２８】
2004326465.tif 000029
の分割点の集合を求め、Ｔ’’とする。
（ｉ）    （図６    ６０９）
【数２９】
2004326465.tif 000030
を、Ｓの分割点の集合として返す。
（手続きＤＩＶ（Ｓ，  Ｃｃ）の終わり）
【００３４】
ステップ４：（図２    ２０４）離散化パラメータ格納部１０９に格納された離散化パラメータ表ＴＡＢｃに従って、学習用素性ベクトル作成部１１０が、各学習用文書特徴ベクトル
【数３０】
2004326465.tif 000031
から、各カテゴリＣｃへの分類学習用文書素性ベクトル
【数３１】
2004326465.tif 000032
を作成する。ただし、
【数３２】
2004326465.tif 000033
は、ステップ３で、カテゴリＣｃに対して有効とされた軸の数である。
具体的には、次のようにする。
（ｉ）    （図８    ８０１）ＴＡＢｃを参照し、カテゴリＣｃに対して有効な軸番号（文書特徴ベクトルのＫ個の基底の中での番号）列
【数３３】
2004326465.tif 000034
を求める。
（ｉｉ）    （図８    ８０２）列
【数３４】
2004326465.tif 000035
に対して、当該文書特徴ベクトルの第αｊ成分
【数３５】
2004326465.tif 000036
を得る。
（ｉｉｉ）    （図８    ８０３）Ｂｃを参照し、
【数３６】
2004326465.tif 000037
番目の軸に対する分割点の列
【数３７】
2004326465.tif 000038
を得る。
（ｉｖ）    （図８  ８０４）
【数３８】
2004326465.tif 000039
とする。
【００３５】
ステップ５：（図２  ２０５）ベイジアンネットワーク学習部１１１が、各カテゴリＣｃについて、各学習用文書ｄが属すかどうかを示す値
【数３９】
2004326465.tif 000040
と、ｄの素性ベクトルの組の集合
【数４０】
2004326465.tif 000041
から、カテゴリＣｃへの分類確率計算用のベイジアンネットワークＢＮ（ｃ）を学習により生成し、ベイジアンネットワーク格納部１１２に格納する。ベイジアンネットワークの学習には、各種のアルゴリズムが存在するが、本実施の形態では、ベイジアンネットワークの型を、カテゴリＣｃに対応する節点を根とし、各素性に対応する節点を葉とするような、Ｎａｉｖｅ  Ｂａｙｅｓ型（図９）に限定し、以下のように学習を行う。
（ｉ）    （図１０  １００１）節点の集合Ｎ（ｃ）および辺の集合Ｅ（ｃ）を空にする。
（ｉｉ）    （図１０  １００２）カテゴリＣｃに対応する節点
【数４１】
2004326465.tif 000042
に加える。
（ｉｉｉ）    （図１０  １００３）各有効軸番号
【数４２】
2004326465.tif 000043
に対して、対応する節点
【数４３】
2004326465.tif 000044
に加える。
（ｉｖ）    （図１０  １００４）
【数４４】
2004326465.tif 000045
に向かう有向辺を
【数４５】
2004326465.tif 000046
に加える。
（ｖ）    （図１０  １００５）各
【数４６】
2004326465.tif 000047
における条件付確率表
【数４７】
2004326465.tif 000048
に付与する。
一般に、ベイジアンネットワークにおいて、各節点に付与される条件付確率表は、当該節点のすべての親節点に対応する変数のすべての値の組に対して、当該節点に対応する変数が、当該変数がとりうる値をどのような確率でとるかを示す条件付確率である。本実施の形態の場合は、節点
【数４８】
2004326465.tif 000049
の要素は、任意の文書がカテゴリＣに属す場合と属さない場合のそれぞれにおいて、当該文書のカテゴリＣｃに関するｊ番目の有効素性
【数４９】
2004326465.tif 000050
となる（図１１）。ただし、ｚは、文書がカテゴリＣｃに属すときに１、属さないときに０とする。
ここでは、
【数５０】
2004326465.tif 000051
により計算する。ここで、Ｄｔｒａｉｎは、学習用文書集合である。θｔは、
【数５１】
2004326465.tif 000052
により計算した数であり、θは、設計者によって設定される数であり、本実施の形態では１とする。
（ｖｉ）    （図１０  １００６）文書がカテゴリＣｃに属す確率を
【数５２】
2004326465.tif 000053
に対して、付与する。
以上が、学習フェーズに関する説明である。
【００３６】
次に、分類フェーズの動作に関する説明を図１２を用いながら行う。
分類フェーズにおいては、
ステップ１：（図１２  １２０１）分類対象文書入力部１１３により入力された分類対象の各文書ｄｄに対して、分類対象文書ベクトル作成部１１４が、分類対象文書特徴ベクトル学習フェーズのステップ１におけると同様にして、文書ベクトル
【数５３】
2004326465.tif 000054
を作成する。
【００３７】
ステップ２：（図１２  １２０２）分類ベクトル
【数５４】
2004326465.tif 000055
と学習フェーズのステップ２で求め、単語特徴ベクトル格納部１０５に格納されている各語ｗｗに対する単語特徴ベクトル
【数５５】
2004326465.tif 000056
を用いて、分類対象文書特徴ベクトル作成部１１５が、文書特徴ベクトル
【数５６】
2004326465.tif 000057
により求める。
【００３８】
ステップ３：（図１２  １２０３）学習フェーズのステップ４と同様にして、各カテゴリＣｃに対して、離散化パラメータ格納部１０９に格納されている離散化パラメータ表ＴＡＢｃにしたがって、分類対象素性ベクトル作成部１１６が、文書特徴ベクトル
【数５７】
2004326465.tif 000058
を作成する。
【００３９】
ステップ４：（図１２  １２０４）各分類対象文書ｄｄについて、学習フェーズのステップ５で作成し、ベイジアンネットワーク格納部１１２に格納されている各カテゴリＣｃへの分類用のベイジアンネットワークＢＮｃを用いて、所属確率計算部１１７が、素性ベクトル
【数５８】
2004326465.tif 000059
から、文書ｄｄがカテゴリＣｃに属すかどうかに関する確率
【数５９】
2004326465.tif 000060
を求める。これは、一般的には、ベイジアンネットワークにおける周辺確率分布の計算法により計算すればよい。本実施の形態では、特に、ＢＮｃはｎａｉｖｅ  Ｂａｙｅｓ型の構造を持つので、
【数６０】
2004326465.tif 000061
が成り立ち、これから
【数６１】
2004326465.tif 000062
が成り立つが、
【数６２】
2004326465.tif 000063
に付与されている条件付確率表から求めることができるので、これを用いれば、簡単に計算することができる。
【００４０】
ステップ５：（図１２  １２０５）分類結果出力部１１８が、各文書ｄｄの、各カテゴリＣｃへの所属確率を出力する。
以上が、分類実行時の動作である。
【００４１】
【発明の効果】
以上のように、本発明によれば、行列演算による次元圧縮法を用いて、各文書に対する文書ベクトルを、より次元数の低いベクトルにより近似させ、ベイジアンネットワークを用いた文書分類の入力として用いるので、一定の基準に満たない単語に関する情報がすべて落とされるという問題は解決される。また、学習に基づく区間分割を行って得られる離散値からなる素性ベクトルを生成することにより、学習データをベイジアンネットワークの学習に適した形にすることができる。
【００４２】
また、本発明の別の態様によれば、上記次元圧縮法として、対応分析を用いることにより、頻度の少ない語や文書長の短い文書を重視した効果を自動的に得ることができる。
【００４３】
また、本発明のさらに別の態様によれば、上記素性ベクトル離散化部における、モデル選択規準としてＭＤＬ・規準に基づいて学習された区間分割による離散化行うことにより、各カテゴリへの分類にとって効果のない素性の使用を排除でき、素性の数を絞り込むことができるので、分類装置を過適応に陥りにくくすることが可能になるとともに、ベイジアンネットワークの学習における計算量的側面からも好ましい性質を持つ。また、ＭＤＬ規準においては、有効な素性と有効でない素性は、自動的に計算される基準に従って区別されるので、利用者が閾値を試行錯誤により設定する負担もなくなる。
【００４４】
なお、本実施の形態においては、主成分分析により得られた文書特徴ベクトルをそのまま用いていたが、文書特徴ベクトルの長さが１になるように正規化したものを用いても良い。
【００４５】
また、本実施の形態においては、モデル選択の規準として、ＭＤＬ基準を用いたが、その他のモデル選択規準として、拡張確率的コンプレキシティなどの規準を用いても良い。
【図面の簡単な説明】
【図１】本発明の一実施の形態に係る文書分類装置の構成を示すブロック図
【図２】前記実施の形態における学習フェーズの処理動作を説明するフローチャート
【図３】前記実施の形態における単語文書行列の例を説明する図
【図４】前記実施の形態における対応分析の処理動作を説明するフローチャート
【図５】前記実施の形態における離散化パラメータ学習の処理動作を説明するフローチャート
【図６】前記実施の形態におけるＭＤＬ・規準による区間の分割の処理動作を説明するフローチャート流れを示す図
【図７】前記実施の形態における離散化パラメータのの例を説明する図
【図８】前記実施の形態における素性ベクトル作成の処理動作を説明するフローチャート
【図９】前記実施の形態における分類用ベイジアンネットワークの説明図
【図１０】前記実施の形態におけるベイジアンネットワーク学習の処理動作を説明するフローチャート
【図１１】前記実施の形態における条件付確率表の説明図
【図１２】前記実施の形態における分類フェーズの動作の処理動作を説明するフローチャート
【符号の説明】
１０１  学習用文書格納部
１０２  単語辞書
１０３  単語文書行列作成部
１０４  対応分析実行部
１０５  単語特徴ベクトル格納部
１０６  学習用文書特徴ベクトル格納部
１０７  学習用カテゴリ情報格納部
１０８  離散化パラメータ計算部
１０９  離散化パラメータ格納部
１１０  学習用素性ベクトル作成部
１１１  ベイジアンネットワーク学習部
１１２  ベイジアンネットワーク格納部
１１３  分類対象文書入力部
１１４  分類対象文書ベクトル作成部
１１５  分類対象文書特徴ベクトル作成部
１１６  分類対象素性ベクトル作成部
１１７  所属確率計算部
１１８  分類結果出力部
【図１】
2004326465.tif 000064
【図２】
2004326465.tif 000065
【図３】
2004326465.tif 000066
【図４】
2004326465.tif 000067
【図５】
2004326465.tif 000068
【図６】
2004326465.tif 000069
【図７】
2004326465.tif 000070
【図８】
2004326465.tif 000071
【図９】
2004326465.tif 000072
【図１０】
2004326465.tif 000073
【図１１】
2004326465.tif 000074
【図１２】
2004326465.tif 000075