(57)【特許請求の範囲】
【請求項１】
入力文書を1つ以上のクラスに分類する文書分類装置であって、
入力された訓練文書集合をクラス毎に分割し、各クラスの文書を連結したクラス別連結文書を作成する文書連結手段と、
前記クラス別連結文書からクラス毎に接尾辞配列を構築する接尾辞配列構築手段と、
前記接尾辞配列を記憶する接尾辞配列記憶手段と、
前記入力文書に含まれる部分文字列が、前記クラス別連結文書に出現する頻度であるクラス別出現頻度と、該クラス別連結文書において該部分文字列の次に出現する異なり文字数であるクラス別異なり次文字数と、を前記接尾辞配列記憶手段に格納されている前記接尾辞配列から検索結果として取得する部分文字列検索手段と、
前記部分文字列検索手段の前記検索結果から前記入力文書のクラス別文書スコアを計算する文書スコア計算手段と、
前記クラス別文書スコアを基に、前記入力文書のクラスを決定する文書クラス決定手段と、
を有することを特徴とする文書分類装置。
【請求項２】
前記部分文字列検索手段の検索結果を記憶する検索結果キャッシュ手段を更に有し、
前記部分文字列検索手段は、
前記入力文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれていない場合は、該部分文字列の前記クラス別出現頻度と前記クラス別異なり次文字数を前記接尾辞配列から検索結果として取得すると同時に該検索結果を該検索結果キャッシュ手段に記憶し、
前記入力文書に含まれる部分文字列の検索結果が該検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する手段を含む、
請求項１記載の文書分類装置。
【請求項３】
前記文書スコア出力手段は、
前記部分文字列検索手段の検索結果を基に、前記入力文書に含まれる全ての文字毎に、該文字の生起確率に依存する直前の文字数モデル次数を決定して該文字の生起確率を推定し、前記生起確率を全ての文字に関して掛け合わせて、クラス別文書スコアを計算する手段を含む
請求項１または２記載の文書分類装置。
【請求項４】
入力文書を1つ以上のクラスに分類する文書分類方法であって、
文書連結手段が、入力された訓練文書集合をクラス毎に分割し、各クラスの文書を連結したクラス別連結文書を作成する文書連結ステップと、
接尾辞配列構築手段が、前記クラス別連結文書からクラス毎に接尾辞配列を構築し、接尾辞配列記憶手段に格納する接尾辞配列構築ステップと、
部分文字列検索手段が、前記入力文書に含まれる部分文字列が、前記クラス別連結文書に出現する頻度であるクラス別出現頻度と、該クラス別連結文書において該部分文字列の次に出現する異なり文字数であるクラス別異なり次文字数と、を前記接尾辞配列記憶手段に格納されている前記接尾辞配列から検索結果として取得する部分文字列検索ステップと、
文書スコア計算手段が、前記部分文字列検索ステップの前記検索結果から前記入力文書のクラス別文書スコアを計算する文書スコア計算ステップと、
文書クラス決定手段が、前記クラス別文書スコアを基に、前記入力文書のクラスを決定する文書クラス決定ステップと、
を有することを特徴とする文書分類方法。
【請求項５】
前記部分文字列検索ステップにおいて、
当該部分文字列検索ステップの検索結果を記憶するための検索結果キャッシュ手段に、前記入力文書に含まれる部分文字列の検索結果が含まれていない場合は、該部分文字列の前記クラス別出現頻度と前記クラス別異なり次文字数を前記接尾辞配列から検索結果として取得すると同時に該検索結果を該検索結果キャッシュ手段に記憶し、
前記入力文書に含まれる部分文字列の検索結果が該検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する、
請求項４記載の文書分類方法。
【請求項６】
前記文書スコア出力ステップにおいて、
前記部分文字列検索ステップの検索結果を基に、前記入力文書に含まれる全ての文字毎に、該文字の生起確率に依存する直前の文字数モデル次数を決定して該文字の生起確率を推定し、前記生起確率を全ての文字に関して掛け合わせて、クラス別文書スコアを計算する
請求項４または５記載の文書分類方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載の文書分類装置の各手段として機能させるための文書分類プログラム。
【請求項８】
請求項７記載の文書分類プログラムを格納したことを特徴とするコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書分類装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体に係り、特に、入力文書に含まれる可変長の部分文字列の出現頻度を、少ない記憶容量と短い計算時間で分類時に効率的に求め、文書を単語の集合に分割することなく高精度な文書分類を実現するための文書分類装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
文書分類のための学習アルゴリズムを適用する際には、文書を単語の集合（Bag-of-words）で表現し、それぞれの単語の出現は独立と仮定する手法が現在の主流である。
【０００３】
しかし、日本語などの単語が空白文字で区切られていない言語においては、形態素解析の精度が文書分類に直結する。
【０００４】
また、文書長が短い場合においては、単語の出現を独立と仮定することによって生じる情報欠落が無視できなく（2単語以上に跨る情報を捉えて分類に利用することができない）、分類精度の低下に繋がっている。
【０００５】
ここで、文書を、連続するn文字（文字nグラム）の集合とみなし、nの値を大きく設定すれば形態素解析の必要も無く、2単語以上に跨る情報を捉えることも可能である。しかし、文字nグラムの種類数は、文字種類数をΣとしたとき、最大でΣのn乗個存在するため、記憶容量の面で実現が難しい。
【０００６】
訓練集合における特徴的な部分文字列を用いて分類する手法が提案されている（例えば、非特許文献1参照）。しかし、どの部分文字列が分類に有効かを学習するための時間が必要となってしまう。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】岡野原、辻井、"全ての部分文字列を考慮した文書分類"NL187 自然言語研究会）
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記のように、現在は、入力文書を可変長な部分文字列の集合として扱う文書分類技術において、少ない記憶容量・短い学習時間・高精度な文書分類を同時に全て実現する技術は存在しない。
【０００９】
本発明は、上記従来技術の問題点に鑑みて、訓練文書集合の学習を連結した文書の文字列から接尾辞配列を構築することのみとし、分類時に接尾辞配列から必要な情報を取得することで、形態素解析や部分文字列長の制限が無く、少ない記憶容量・短い学習時間・高精度な文書分類を同時に全て実現する文書分類装置及び方法及びプログラム及びコンピュータ読取可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記の課題を解決するため、本発明（請求項１）は、入力文書を1つ以上のクラスに分類する文書分類装置であって、
入力された訓練文書集合をクラス毎に分割し、各クラスの文書を連結したクラス別連結文書を作成する文書連結手段と、
前記クラス別連結文書からクラス毎に接尾辞配列を構築する接尾辞配列構築手段と、
前記接尾辞配列を記憶する接尾辞配列記憶手段と、
前記入力文書に含まれる部分文字列が、前記クラス別連結文書に出現する頻度であるクラス別出現頻度と、該クラス別連結文書において該部分文字列の次に出現する異なり文字数であるクラス別異なり次文字数と、を前記接尾辞配列記憶手段に格納されている前記接尾辞配列から検索結果として取得する部分文字列検索手段と、
前記部分文字列検索手段の前記検索結果から前記入力文書のクラス別文書スコアを計算する文書スコア計算手段と、
前記クラス別文書スコアを基に、前記入力文書のクラスを決定する文書クラス決定手段と、を有する。
【００１１】
また、本発明（請求項２）は、前記部分文字列検索手段の検索結果を記憶する検索結果キャッシュ手段を更に有し、
前記部分文字列検索手段は、
前記入力文書に含まれる部分文字列の検索結果が前記検索結果キャッシュ手段に含まれていない場合は、該部分文字列の前記クラス別出現頻度と前記クラス別異なり次文字数を前記接尾辞配列から検索結果として取得すると同時に該検索結果を該検索結果キャッシュ手段に記憶し、
前記入力文書に含まれる部分文字列の検索結果が該検索結果キャッシュ手段に含まれている場合は、該検索結果キャッシュ手段から該検索結果を取得する手段を含む。
【００１２】
また、本発明（請求項３）は、前記文書スコア出力手段において、
前記部分文字列検索手段の検索結果を基に、前記入力文書に含まれる全ての文字毎に、該文字の生起確率に依存する直前の文字数モデル次数を決定して該文字の生起確率を推定し、前記生起確率を全ての文字に関して掛け合わせて、クラス別文書スコアを計算する手段を含む。
【発明の効果】
【００１３】
上記のように構成された請求項１記載の文書分類装置によれば、入力文書に含まれる部分文字列が、どのクラスと強い関連を示すかについて、接尾辞配列からクラス毎の出現頻度や異なり次文字数を分類時に取得して計算し、高い分類精度を実現することができる。学習は訓練文書集合を連結した文書から接尾辞配列を構築するのみであるため、形態素解析やn-gram分割の必要が無く、どんな言語で記述された文書に対しても共通の処理を用いて、少ない記憶容量・短い学習時間で文書分類器を実現できる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態における文書分類装置の構成図である。
【図２】本発明の一実施の形態における文書分類装置の学習動作のフローチャートである。
【図３】本発明の一実施の形態における文字列"abracadabra"から接尾辞配列を構築した例である。
【図４】本発明の一実施の形態における文書分類装置の分類動作のフローチャートである。
【図５】本発明の一実施の形態における入力文書に含まれる部分文字列の例である。
【図６】本発明の一実施の形態における分類の例である。
【発明を実施するための形態】
【００１５】
以下図面と共に、本発明の実施の形態を説明する。
【００１６】
図１は、本発明の一実施の形態における文書分類装置の構成を示す。
【００１７】
同図に示す文書分類装置は、文書連結部１と接尾辞配列構築部２と接尾辞配列記憶部３と部分文字列検索部４と文書スコア計算部５と文書クラス決定部６と検索結果キャッシュ部７から構成され、訓練文書集合と入力文書を受け取り、入力文書を1つ以上のクラスに分類する。
【００１８】
まず、文書連結部１、接尾辞配列構築部２、接尾辞配列記憶部３による学習動作について説明する。
【００１９】
図２は、本発明の一実施の形態における文書分類装置の学習動作フローチャートである。
【００２０】
ステップ１０１）文書連結部１は、入力された訓練文書集合から、クラスc毎に連結したクラス別連結文書Dcを作成する。ここで、文書の連結順序は、ランダム順、文書の作成時間順など如何なる順序でも良い。
【００２１】
ステップ１０２）接尾辞配列構築部２は、前記文書連結部１から出力されたクラス別連結文書Dc毎に接尾辞配列を構築する。図３に構築された接尾辞配列の例を示す。図３において、列SAは、各接尾辞（suffix）が、基の文書中のどの位置に出現するかを表す。また、列lcpは、接尾辞配列における次行の接尾辞との共通接頭辞長を表す。ここで、接尾辞配列の構築には、文献１（G. Nong, S. Zhang, and W.H. Chan, "Two efficient algorithms for linear suffix array constraction", 2008.）で示される手法などの公知のアルゴリズムが利用可能で、文書長の長さに比例する時間で高速に構築することが可能である。また、接尾辞配列よりもさらに必要な記憶容量を減らすことのできるCompressed Suffix Array（文献２：R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching], SIAM Journal on Computing, 35(2), 2005, 378-407.）やFM-index（文献３：Paolo Ferragina and Giovanni Manzini. Indexing compressed text. Journal of the ACM (JACM), 52, 4 (Jul. 2005), 552-581）などを用いても良い。
【００２２】
ステップ１０３）接尾辞配列記憶部３は、前記接尾辞配列構築部２が構築したクラス別接尾辞配列を記憶する。
【００２３】
以上で学習動作は完了であり、本発明における学習動作は接尾辞配列の構築のみであるため、非常に短い時間で文書分類の準備を整えることができる。
【００２４】
次に、文書分類装置の分類動作について説明する。当該処理は、接尾辞配列記憶部３、部分文字列検索部４、文書スコア計算部５、文書クラス決定部６、検索結果キャッシュ部７を用いる。
【００２５】
図４は、本発明の一実施の形態における文書分類装置の分類動作フローチャートである。
【００２６】
ステップ２０１）部分文字列検索部４は、入力文書に含まれる全ての部分文字列を検索する。
【００２７】
当該処理を図5に示す、入力文書が"bracara"の場合を用いて本ステップの説明を行う。該部分文字列検索部４は、入力文書の長さがm（この例では7）のとき、m回のループ（ループ1〜ループm）を処理する。
【００２８】
まずループ1では、文字列"ｂ"のクラス別出現頻度を、前記検索結果キャッシュ部７または前記接尾辞配列記憶部３から検索して取得する。次は文字列"br"、その次は"bra"、という様に1文字ずつ検索文字列を追加していく。このとき、該部分文字列の接尾辞配列中の出現範囲を覚えておき、次の部分文字列の検索範囲として設定することで、効率的な検索が行える。なお、クラス別出現頻度が0になったところで、該クラスにおいては、該ループにおける以降の部分文字列のクラス別出現頻度は全て0となるので次ループに移る。
【００２９】
ループ2も同様に、文字列"r"，"ra"，"rac"，…の順に検索結果を取得し、以降、最後のループmまで同様の処理を行う。
【００３０】
当該ステップにより、部分文字列検索部４は、各クラス毎に、前記クラス別連結文書において出現頻度が0となる部分文字列を除いた全ての部分文字列に関して、クラス別出現頻度と、クラス別異なり次文字数を取得する。入力文書に含まれる部分文字列数の総数はm(m+1)/2個であるが、出現頻度が0回の部分文字列については検索処理を打ち切るため、効率的かつ高速に該出現頻度と該異なり次文字数を取得できる。また、検索結果キャッシュ部７に接尾辞配列からの検索結果を記憶しておくことで、さらなる高速化が可能となる。この検索結果キャッシュ部７に検索結果を格納する条件は、全て記憶、部分文字列の長さがN1以上、部分文字列の出現頻度がN2以上、これらの条件の組み合わせ、などとする。
【００３１】
ステップ２０２）文書スコア計算部５は、以下の式に従って入力文書dのクラスcに対するスコアscore(d|c)を計算する。
【００３２】
【数１】
0005575074.tif 000002
ここで、siは、入力文書dにおけるi番目の文字、
【００３３】
【数２】
0005575074.tif 000003
は、j番目からi番目までの文字を表す。そして、siが依存する直前の文字数
【００３４】
【数３】
0005575074.tif 000004
は、
【００３５】
【数４】
0005575074.tif 000005
として各文字毎に決定する。ここで、ステップ２０1にて導出済みの
【００３６】
【数５】
0005575074.tif 000006
はクラスcにおける
【００３７】
【数６】
0005575074.tif 000007
の出現頻度である。Fcutoffは、ハイパーパラメータである（例えば、3などを設定する）。また、
【００３８】
【数７】
0005575074.tif 000008
を全ての文字で同じ値としても良い（例えば、5などを設定する）。
【００３９】
文字siのクラスcにおける生起確率
【００４０】
【数８】
0005575074.tif 000009
は、以下の通り計算する。
【００４１】
【数９】
0005575074.tif 000010
ここで、重みwは以下の通り計算できる。
【００４２】
【数１０】
0005575074.tif 000011
ただし、p0はクラス別連結文書に出現する全ての異なり文字数の逆数、e0=0とする。
【００４３】
そして、
【００４４】
【数１１】
0005575074.tif 000012
と
【００４５】
【数１２】
0005575074.tif 000013
は、以下の通り計算する。
【００４６】
【数１３】
0005575074.tif 000014
ここで、
【００４７】
【数１４】
0005575074.tif 000015
は、ステップ２０1にて導出済みのクラスcの連結文書中における
【００４８】
【数１５】
0005575074.tif 000016
の後に続く異なり文字数である。
【００４９】
また、
【００５０】
【数１６】
0005575074.tif 000017
は、文献４（北研二,"確率的言語モデル", 東京大学出版会, 1999）にて公知のバックオフスムージングなどにより決定しても良い。
【００５１】
最後に、クラスcの時前確率p(c)は、各クラスの訓練文書数の比率から決定する。また、全てのクラスで等しいと設定しても良い。
【００５２】
以上の様に入力文書の各クラスに対するスコアを計算することで、入力文書を単語に分割する必要無く、入力文書中の2単語以上に跨る情報や、1単語未満の文字レベル情報、文字の出現順序に関する情報を全て利用することができるので、高い精度での分類が可能となる。
【００５３】
ステップ２０３）文書クラス決定部６は、前記文書スコア計算部５が導出した入力文書のクラス別スコアscore(d|c)のうち、最大のスコアとなるcを出力する。
【００５４】
また、各クラスのスコアの総和に対する比率が、閾値θ以上のクラスを全て出力する、などとして決定しても良い。
【００５５】
図６に、訓練文書集合として地震に関する文書とスポーツに関する文書を与え、入力文書として「原子力発電について考える」を与えた際の分類例を示す。この場合、『クラス:地震』においては、「原子力発電」という文字列は多く出現するため、特にp("電"|"原子力発")の値が1に近づく。しかし、『クラス:スポーツ』においては、「原子力発電」という文字列が出現する頻度は低いため、これらの文字列に対する生起確率は低くなる。この部分の差によって、入力文書がクラス:地震に属すると分類することができる。このように、本発明では、クラス毎に特徴的な文字列の出現順序を捉えることができるので、高い精度で分類することが可能となる。また、学習は接尾辞配列の構築のみで良いので、少ない記憶容量・短い学習時間で文書分類器を実現できる。また、扱う文書がどんな言語で書かれていても、本発明は適用できる。
【００５６】
本発明は、どのような文書に対しても適用可能であるが、特に、Twitter(登録商標)などのリアルタイム性の高く、文書長が短いものの分類に対して有効である。
【００５７】
また、本発明は、図１に示す構成要素の動作をプログラムとして構築し、マイクロブログ文書分類装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５８】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５９】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００６０】
１  文書連結部
２  接尾辞配列構築部
３  接尾辞配列記憶部
４  部分文字列検索部
５  文書スコア計算部
６  文書クラス決定部
７  検索結果キャッシュ部
【図１】
0005575074.tif 000018
【図２】
0005575074.tif 000019
【図３】
0005575074.tif 000020
【図４】
0005575074.tif 000021
【図５】
0005575074.tif 000022
【図６】
0005575074.tif 000023