(57)【要約】【課題】Multinomial Bayesによる教師付きデータ分類法において、出来るだけ少ない分類パラメータで良好な分類精度を実現する。【解決手段】特徴生成部１１は、入出力装置２を通して入力された学習テキストから特徴を生成する。特徴選択部１２では、特徴生成部１１で生成した特徴群を入力として、分類に有効と思われる特徴を特徴群から選択することで、分類パラメータ候補群を生成する。機械学習部１３内の分類パラメータ選択部１３１は、分類パラメータ候補群に対して、Multinomial Bayesによる機械学習アルゴリズムに基づいて重みを付与しつつ、付与した重みから分類パラメータとして有効かどうか判断し、有効なもののみを分類パラメータとして出力する。【選択図】図１
2010282502.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより、カテゴリラベル付き学習データから、分類パラメータを生成する方法であって、
カテゴリラベル付き学習データから特徴を抽出するステップと、
その抽出された特徴を所定の条件に基づいて選択してカテゴリ毎の分類パラメータ候補を取得するステップと、
その分類パラメータ候補に対して、Multinomial Bayesの重みの計算式を基に重みを算出するステップと、
その算出した重みが所定の閾値を超える分類パラメータ候補及びその重みの組を分類パラメータとするステップと
を有することを特徴とする分類パラメータ生成方法。
【請求項２】
請求項１に記載された分類パラメータ生成方法において、
前記所定の閾値は、カテゴリＣi毎の学習データから計算された２つの閾値Thresh(i)+,Thresh(i)-であり、前記分類パラメータとするステップは、前記重みがThresh(i)+より大きいか、またはThresh(i)-より小さい分類パラメータ候補を分類パラメータとすることを特徴とする分類パラメータ生成方法。
【請求項３】
請求項２に記載された分類パラメータ生成方法において、
前記Thresh(i)+，Thresh(i)- を下記の式により計算することを特徴とする分類パラメータ生成方法。
Thresh(i)+ = log((((N-N(i))+V)/(N(i)+V))*(N(i)/M(i)+1))
Thresh(i)- = log((((N-N(i))+V)/(N(i)+V))/((N-N(i))/(M-M(i))+1))
ただし、
N：各学習データ内の重複もカウントした全学習データに含まれる特徴数
N(i)：各学習データ内の重複もカウントしたカテゴリＣiに属する特徴数
V：全学習データに含まれる特徴の種類数
M：各学習データ内の重複を無視し、各学習データ間の重複をカウントした全学習データに含まれる重複もカウントした特徴数
M(i)：各学習データ内の重複を無視し、各学習データ間の重複をカウントしたカテゴリＣiに属する特徴数
【請求項４】
カテゴリラベル付き学習データから特徴を抽出する手段と、
その抽出された特徴を所定の条件に基づいて選択してカテゴリ毎の分類パラメータ候補を取得する手段と、
その分類パラメータ候補に対して、Multinomial Bayesの重みの計算式を基に重みを算出する手段と、
その算出した重みが所定の閾値を超える分類パラメータ候補及びその重みの組を分類パラメータとする手段と
を有することを特徴とする分類パラメータ生成装置。
【請求項５】
コンピュータに、請求項１〜３のいずれかに記載された分類パラメータ生成方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分類パラメータ生成装置、生成方法及び生成プログラムに関し、さらに詳しくは、Multinomial Bayesによる教師付きデータ分類法において、出来るだけ少ない分類パラメータで良好な分類精度を実現できるようにした分類パラメータ生成装置、生成方法及び生成プログラムに関する。
【背景技術】
【０００２】
インターネットの急速な普及に伴って、Webページには電子化された書類などのテキストデータが急速に増加したために、目的とするテキストデータを探し出す場合には、大量のテキストデータの中から探し出す必要がある。
【０００３】
大量のテキストデータの中から目的とするテキストデータを探し出すための技術として、テキストデータを予め幾つかのカテゴリに分類しておくことにより、検索対象に関連する特定のカテゴリに属するテキストデータのみを検索する方法がある。例えば、特許文献１には、入力テキストについて形態素解析を行ってテキストを単語に分割し、各単語に品詞を割り当て、入力テキストの内容をよく表す名詞を特徴語として取り出し、取り出した特徴語の出現頻度をカウントし、特徴語とその出現頻度を用いてテキストベクトルを生成し、生成したテキストベクトルと分類パラメータの内積を算出し、算出した内積が閾値に達しているか否かによりカテゴリに属するか否かを判定するテキスト」分類方法が開示されている。
【０００４】
ここで、入力テキストのカテゴリを正確に判定するためには、分類パラメータが適切であることが必要である。従来、分類パラメータを作成する方法として、Multinomial Bayesによる教師付きデータ分類法がある。
【０００５】
図４は、教師付きデータ分類法のアルゴリズムのフローチャートである。図示のように、特徴抽出フェーズ（ステップＳ１）で、入力されたカテゴリラベル付き学習用データの特徴抽出を行い、特徴選択フェーズ（ステップＳ２）で、先に抽出された特徴を絞り込んで分類パラメータ候補とする。次いで、機械学習フェーズ（ステップＳ３）で、Multinomial Bayesによる機械学習アルゴリズムを用いて各分類パラメータ候補に対して重みを付与し、分類パラメータ候補とその重みの組を分類パラメータとする。
【０００６】
Multinomial Bayesでは、分類パラメータが多い程分類精度が高くなると言われている。しかし、分類パラメータが多いと分類時間が長くなるため、出来るだけ少ない分類パラメータで良好な分類精度を実現することが望ましい。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、このような問題を解決するためになされたものであり、その目的は、Multinomial Bayesによる教師付きデータ分類法により分類パラメータを生成するときに、出来るだけ少ない分類パラメータで良好な分類精度を実現できるようにすることである。
【課題を解決するための手段】
【０００８】
本発明の分類パラメータ生成方法は、コンピュータにより、カテゴリラベル付き学習データから、分類パラメータを生成する方法であって、カテゴリラベル付き学習データから特徴を抽出するステップと、その抽出された特徴を所定の条件に基づいて選択してカテゴリ毎の分類パラメータ候補を取得するステップと、その分類パラメータ候補に対して、Multinomial Bayesの重みの計算式を基に重みを算出するステップと、その算出した重みが所定の閾値を超える分類パラメータ候補及びその重みの組を分類パラメータとするステップとを有することを特徴とする分類パラメータ生成方法である。
本発明の分類パラメータ生成装置は、カテゴリラベル付き学習データから特徴を抽出する手段と、その抽出された特徴を所定の条件に基づいて選択してカテゴリ毎の分類パラメータ候補を取得する手段と、その分類パラメータ候補に対して、Multinomial Bayesの重みの計算式を基に重みを算出する手段と、その算出した重みが所定の閾値を超える分類パラメータ候補及びその重みの組を分類パラメータとする手段とを有することを特徴とする分類パラメータ生成装置である。
本発明の分類パラメータ生成プログラムは、コンピュータに、本発明の分類パラメータ生成方法の各ステップを実行させるためのプログラムである。
【０００９】
［作用］
本発明によれば、カテゴリ毎の分類パラメータ候補の内、Multinomial Bayesの重みの計算式を基に算出した重みが所定の閾値を超える分類パラメータ候補とその重みの組を分類パラメータとする。換言すれば、重みが所定の閾値以下の分類パラメータ候補及びその重みの組を分類に寄与しない無効な分類パラメータであると判断して除去する。
【発明の効果】
【００１０】
本発明によれば、Multinomial Bayesによる教師付きデータ分類法により分類パラメータを生成するときに、出来るだけ少ない分類パラメータで良好な分類精度を実現することが出来る。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態の分類パラメータ生成装置のブロック図である。
【図２】本発明の実施形態の分類パラメータ生成装置における分類パラメータ選択処理のフローチャートの一部である。
【図３】本発明の実施形態の分類パラメータ生成装置における分類パラメータ選択処理の残りの部分である。
【図４】教師付きデータ分類法のアルゴリズムのフローチャートである。
【発明を実施するための形態】
【００１２】
以下、本発明を実施するための形態について、図面を参照して説明する。
〈分類パラメータ生成装置のブロック図〉
図１は、本発明の実施形態の分類パラメータ生成装置のブロック図である。この分類パラメータ生成装置１は入出力装置２に接続されており、入出力装置２を介して外部から入力される学習テキストから分類パラメータを生成し、入出力装置２を介して外部へ出力する。
【００１３】
分類パラメータ生成装置１は、特徴生成部１１、特徴選択部１２、及び分類パラメータ選択部１３１を内蔵する機械学習部１３を備えており、各部は、コンピュータのＲＯＭに格納された分類パラメータ生成プログラムをＣＰＵが実行することにより実現される機能ブロックであり、入出力装置２は、そのコンピュータの入出力装置である。
【００１４】
特徴生成部１１は、入出力装置２を通して入力された学習テキストから特徴を生成する。生成する特徴は、例えば、形態素解析を使用したＢＯＷ(Bag of Words)、ある規則に基づいて生成する可変長n-gram、suffix arrayを使用したlcp文字列群である。また、特徴生成部１１では、生成した特徴の統計値を計測する。計測する統計値は、ＴＦ(文書内出現頻度)、ＤＦ（文書頻度）あるいは特徴の長さなどである。
【００１５】
特徴選択部１２では、特徴生成部１１で生成した特徴群を入力として、分類に有効と思われる特徴を特徴群から選択することで、分類パラメータ候補群を生成する。例えば各特徴に対して、特徴生成部１１で計測した値(ＴＦ,ＤＦ)を基に重みを付与し、重みをキーとして整列させ、上位から条件に合う特徴を選択する。重み計算法にはいくつかあり、例えば、情報利得、相関係数等を重みとして用いる。
【００１６】
機械学習部１３では、分類パラメータ選択部１３１により分類パラメータ候補群を分類パラメータに変換する。分類パラメータ選択部１３１では、分類パラメータ候補群に対して、Multinomial Bayesによる機械学習アルゴリズムに基づいて重みを算出し、算出した重みから、分類パラメータ候補が分類パラメータとして有効かどうか判断する。そして、有効であると判断した分類パラメータ候補及びその重みの組を分類パラメータとして出力する。
【００１７】
〈分類パラメータ選択部の処理〉
以上説明した分類パラメータ選択部１３１の処理の詳細について、図２及び図３のフローチャートを参照しながら説明する。
まず入力されたカテゴリ毎（カテゴリ数nは２以上の整数）の分類パラメータ候補群に対し、i=1に設定し（ステップＳ３１）、２つの閾値Thresh(i)+,Thresh(i)-を計算する（ステップＳ３１）。
【００１８】
Thresh(i)+は、次のように導出する。
“『Improving Multi-class Text Classification with Naive Bayes』Jason D.M.Rennie，AI Technical Report 2001-004，September 2001，ＭＩＴ-artificial intelligence laboratory”（以下、非特許文献１）によると、Multinomial BayesにおけるカテゴリＣiの分類パラメータ候補Cand(i,j)の重みθijの計算式は下記の式［１］である。
log(((N(i,j)+1)/(N(i)+V)))/(((~N(i,j))+1)/((ΣiN(i)-N(i))+V))  …式［１］
【００１９】
ただし、
N(i)：各学習データ内の重複もカウントしたカテゴリＣiに属する特徴数
N(i,j)：各学習データ内の重複もカウントしたカテゴリＣiにおける分類パラメータ候補Cand(i,j)の出現数（count (Cand(i,j))）
V: 全学習データに含まれる特徴の種類数
M：各学習データ内の重複を無視し、各学習データ間の重複をカウントした全学習データに含まれる重複もカウントした特徴数
M(i)：各学習データ内の重複を無視し、各学習データ間の重複をカウントしたカテゴリＣiに属する特徴数
~N(i,j)：Σicount (cand(i,j))-N(i,j)
である。
【００２０】
式［１］のlog内を変形すると、下記の式［２］となる。
(((ΣiN(i)-N(i))+V))/(N(i)+V))×((N(i,j)+1)/(~N(i,j)+1))  …式［２］
【００２１】
式［２］の中で分類パラメータ候補Candjと関係する項である下記の式［３］に注目する。
((N(i,j)+1)/(~N(i,j)+1))  …式［３］
【００２２】
式［３］において分類パラメータ候補CandjがカテゴリＣiだけに存在すると仮定すると、「~N(i,j)=0」になるから、式［３］は下記の式［４］となる。
N(i,j)+1  …式［４］
【００２３】
N(i,j)は、count (Cand(i,j))であり、この値をカテゴリＣiにおける特徴１個あたりの平均出現頻度とすると、式［４］は下記の式［５］となる。
N(i)/M(i)+1  …式［５］
【００２４】
従って、カテゴリＣiだけに存在する特徴で、その数が平均出現頻度に等しいCand(i,j)の重みは、次の式［６］になる。
log((((N-N(i))+V)/(N(i)+V))*(N(i)/M(i)+1))  …式［６］
【００２５】
Thresh(i)-は、次のように導出する。
式［３］において、分類パラメータ候補CandjがカテゴリＣi以外だけに存在すると仮定すると、「(N(i,j)=0」になるから、式［３］は下記の式［４’］となる。
1/(~N(i,j)+1)  …式［４’］
【００２６】
~N(i,j)をカテゴリＣi以外の特徴の平均出現頻度とすると、N-N(i)はカテゴリＣi以外の特徴の出現頻度であり、M-M(i)はカテゴリＣi以外の特徴数であるから、~N(i,j)は下記の式［５’］となる。
(N-N(i))/(M-M(i))…式［５’］
【００２７】
これを式［１］に適用すると、カテゴリＣi以外だけに存在する特徴で、その数が平均出現頻度に等しいCand(i,j)の重みは、下記の式［６’］になる。
Thresh(i)- = log((((N-N(i))+V)/(N(i)+V))/((N-N(i))/(M-M(i))+1))  …式［６’］
【００２８】
次にカテゴリＣiの分類パラメータ候補Cand(i,j)（j=1〜M(i)）を抽出し（ステップＳ３３）、j=1とした後（ステップＳ３４）、式［１］を用いてCand(i,j)の重みθijを算出する（ステップＳ３５）。
【００２９】
次いで、重みがθijがThresh(i)+より大きいかどうか、またはThresh(i)-より小さい（絶対値は大きい）かどうか判断する（ステップＳ３６）。
【００３０】
判断の結果、θijがThresh(i)+より大きいか、またはThresh(i)-より小さい場合（Ｓ３６：Yes）は、分類パラメータ候補Cand(i,j)を分類パラメータとし（ステップＳ３７）、jをインクリメントする（ステップＳ３８）。一方、θijがThresh(i)+以下、又はThresh(i)-の場合（Ｓ３６：No）は、そのままjをインクリメントする（ステップＳ３８）。
【００３１】
jがM(i)と等しくなる（ステップＳ３９：No）まで、Ｓ３５〜Ｓ３８を繰り返し、jがM(i)と等しくなったら、カテゴリＣiの分類パラメータ（Cand(i’,j’)θi’,j’）を出力（ステップＳ４０）した後にiをインクリメントする（ステップＳ４１）。iがnに等しくなる（ステップＳ42：No）まで、Ｓ３２〜Ｓ４１を繰り返す。
【００３２】
〈分類パラメータ生成の具体例〉
ロイター（Reuters）の記事でコットン（cotton）のカテゴリ（以下、カテゴリＣＡ）に属するテキストと、カテゴリＣＡに属さない（カテゴリＣＡ以外のあるカテゴリＣＢに属する）テキストについて、Thresh(i)+、およびThresh(i)-を計算するとともに、分類パラメータセ生成の様子を説明する。なお、ここではカテゴリＣＢはwpi（wholesale price index：卸売物価指数）である。
【００３３】
ＣＡの分類パラメータ候補と各観測値は下記のとおりである。
uary,N(A,uary)=5,~N(A,uary)=78
pct,N(A,pct)=21,~N(A,pct)=96
ry,N(A,ry)=15,~N(A,ry)=84
ot,N(A,ot)=91,~N(A,ot)=0
ar,N(A,ar)=117,~N(A,ar)=171
ct,N(A,ct)=51,~N(A,ct)=109
ro,N(A,ro)=85,~N(A,ro)=0
ton,N(A,ton)=82,~N(A,ton)=0
ice,N(A,ice)=14,~N(A,ice)=63
January,N(A, January)=2,~N(A, January)=42
tt,N(A,tt)=77,~N(A,tt)=0
N(A)=12442
N(B)=6667
V=1374
M(A)=4859
【００３４】
また、ＣＢの分類パラメータ候補と各観測値は下記のとおりである。
uary, N(B,uary)=78,~N(B,uary)=5
pct, N(B,pct)=96,  ~N(B,pct)=21
N(B)=6667
N(A)=12442
M(B)=2407
V=1374
【００３５】
以上の観測値から、Thresh+,Thresh-と、分類パラメータ候補の重みを計算すると、
Thresh(A)+= 0.728658
Thresh(A)-= -1.868306
uary,-3.237930
pct,-2.081069
ry,-2.275491
ot,4.629907
*ar,-0.957724
*ct,-1.333922
ro,4.562085
ton,4.526366
ice,-2.056470
January,-3.412792
tt,4.463846
Thresh(B)+= 1.868306
Thresh(B)-= -0.728658
uary,3.237930
pct,2.081069
となる。
【００３６】
ここで、*がついている分類パラメータ候補の重みはThresh(A)-より大きい（絶対値が小さい）ので、分類パラメータに採用されない。なお、ここでは分類パラメータの重みの計算式は式［１］ではなく、Jeffreys-Perks law smoothing を施した下記の式［１’］を使用した。
log(((N(i,j)+1/2)/(N(i)+V/2)))/(((~N(i,j))+1/2)/((ΣiN(i)-N(i))+V/2))  …式［１’］
【００３７】
〈分類精度の実測例〉
図４に示す従来の方法と、本実施形態とにより、９４年度の毎日新聞のある記事を各種カテゴリ（演劇,スポーツ,農業,・・・）に分類したところ、従来方法では分類パラメータ数3988、Ｆ値0.725であったのに対し、本実施形態では分類パラメータ数3472、Ｆ値0.735となり、本実施形態の方が少ない分類パラメータ数で高い分類精度を達成した。
【００３８】
本実施形態の分類パラメータ生成装置１は下記（１）〜（３）の特徴を有する。
（１）分類パラメータ候補群に対して、Multinomial Bayesによる機械学習アルゴリズムに基づいて重みを計算しつつ、計算した重みから分類パラメータとして有効かどうか判断し、無効と判断される分類パラメータ候補を除去するので、出来るだけ少ない分類パラメータで良好な分類精度を実現することが出来る。
（２）Multinomial Bayesでは、重みの計算式（式［１］）が予め分かっているので、SVM、Log Linear Modelなどの機械学習アルゴリズムよりも学習速度が速い。
（３）ベイズの仮定（特徴が互いに独立して各カテゴリのテキストに出現する）が成立する限り、他の機械学習アルゴリズムより分類精度が高くなる。
【符号の説明】
【００３９】
１・・・分類パラメータ生成装置、１１・・・特徴生成部、１２・・・特徴選択部、１３・・・機械学習部、１３１・・・分類パラメータ選択部。
【先行技術文献】
【特許文献】
【００４０】
【特許文献１】特開２００８−７１２８３号公報（段落０００６）
【図１】
2010282502.tif 000003
【図２】
2010282502.tif 000004
【図３】
2010282502.tif 000005
【図４】
2010282502.tif 000006