(57)【要約】【課題】  競合学習におけるゼロ頻度問題を回避しつつ、評価基準に関して優れた解を得る。【解決手段】  本発明は、各文書の単語を確率変数とする確率分布を算出し、確率分布記憶手段に格納し、確率分布記憶手段のクラスタに属する文書の確率分布からクラスタの確率分布モデルを算出し、確率分布モデル記憶手段に格納し、逐次更新型のクラスタリングアルゴリズムである競合学習により、確率分布モデル記憶手段の確率分布モデルの逐次更新を行い、確率分布モデル記憶手段のクラスタの確率分布モデルにより文書が属するクラスタを決定する。このとき、確率分布モデル記憶手段のクラスタの確率分布モデルによる文書の確率分布のエントロピーを算出し、その結果最も小さな値を与える確率分布モデルに対応したクラスタを当該文書のクラスタと決定する。【選択図】  図１
2011221666.tif 000002
【特許請求の範囲】
【請求項１】
単語を構成要素とする文書データの集合を空でないいくつかのクラスタに分割する文書データクラスタリング装置であって、
各文書の単語を確率変数とする確率分布を算出し、確率分布記憶手段に格納する確率分布算出手段と、
前記確率分布記憶手段のクラスタに属する文書の確率分布からクラスタの確率分布モデルを算出し、確率分布モデル記憶手段に格納する確率分布モデル算出手段と、
逐次更新型のクラスタリングアルゴリズムである競合学習により、前記確率分布モデル記憶手段の前記確率分布モデルの逐次更新を行う確率分布モデル更新手段と、
前記確率分布モデル記憶手段のクラスタの確率分布モデルにより文書が属するクラスタを決定するクラスタ決定手段と、を有し、
前記クラスタ決定手段は、
前記確率分布モデル記憶手段の前記クラスタの確率分布モデルによる文書の確率分布のエントロピーを算出し、その結果最も小さな値を与える確率分布モデルに対応したクラスタを当該文書のクラスタと決定する手段を含む
ことを特徴とする文書データクラスタリング装置。
【請求項２】
前記確率分布モデル更新手段は、
前記入力文書の確率分布と各確率分布モデルを予め決定されている学習率γを用いて（γ：１−γ）で足し合わせた更新された確率分布モデルを算出する手段を含み、
前記クラスタ決定手段は、
学習過程においてランダムに選ばれた入力文書に対応して、該入力文書の確率分布に最も合致する確率分布モデルを持つクラスタを勝者として選出するときに、前記更新された確率分布モデルに基づく入力文書の確率分布のクロスエントロピーが最も小さくなる更新された確率分布を持つクラスタを勝者と決定し、前記確率分布モデル記憶手段の勝者以外のクラスタの確率分布モデルを更新前に戻す手段を含む
請求項１記載の文書データクラスタリング装置。
【請求項３】
単語を構成要素とする文書データの集合を空でないいくつかのクラスタに分割する文書データクラスタリング方法であって、
確率分布記憶手段と確率分布モデル記憶手段とを有する装置が、
各文書の単語を確率変数とする確率分布を算出し、前記確率分布記憶手段に格納する確率分布算出ステップと、
前記確率分布記憶手段のクラスタに属する文書の確率分布からクラスタの確率分布モデルを算出し、前記確率分布モデル記憶手段に格納する確率分布モデル算出ステップと、
逐次更新型のクラスタリングアルゴリズムである競合学習により、前記確率分布モデル記憶手段の前記確率分布モデルの逐次更新を行う確率分布モデル更新ステップと、
前記確率分布モデル記憶手段のクラスタの確率分布モデルにより文書が属するクラスタを決定するクラスタ決定ステップと、を行い、
前記クラスタ決定ステップにおいて、
前記確率分布モデル記憶手段の前記クラスタの確率分布モデルによる文書の確率分布のエントロピーを算出し、その結果最も小さな値を与える確率分布モデルに対応したクラスタを当該文書のクラスタと決定する
ことを特徴とする文書データクラスタリング方法。
【請求項４】
前記確率分布モデル更新ステップにおいて、
前記入力文書の確率分布と各確率分布モデルを予め決定されている学習率γを用いて（γ：１−γ）で足し合わせた更新された確率分布モデルを算出し、
前記クラスタ決定ステップにおいて、
学習過程においてランダムに選ばれた入力文書に対応して、該入力文書の確率分布に最も合致する確率分布モデルを持つクラスタを勝者として選出するときに、前記更新された確率分布モデルに基づく入力文書の確率分布のクロスエントロピーが最も小さくなる更新された確率分布を持つクラスタを勝者と決定し、前記確率分布モデル記憶手段の勝者以外のクラスタの確率分布モデルを更新前に戻す
請求項３記載の文書データクラスタリング方法。
【請求項５】
請求項１または２に記載の文書データクラスタリング装置を構成する各手段としてコンピュータを機能させるための文書データクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書データクラスタリング装置及び方法及びプログラムに係り、特に、文書データを特徴が似たデータを一括りのクラスタとしてまとめる文書データクラスタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
文書特徴を、単語を確率変数とする確率分布で表し、確率分布モデルの差をカルバック・ライブラー・ダイバージェンス（確率論と情報理論情報における２つの確率分布（真の確率分布Ｐと任意の確率分布Ｑ）の差の尺度）で測るときに、類似した確率分布を持つ文書を一括りのクラスタとしてまとめるクラスタリング手法がある（例えば、非特許文献１参照）。
【０００３】
カルバック・ライブラー・ダイバージェンスを小さくする基準は、クラスタのエントロピーをクラスタに属する文書数で加重平均した値を最小化する基準（以下では、「エントロピー最小基準」と記す）と言い換えることができる。
【０００４】
また、一般のベクトル集合を競合学習を用いて２乗誤差最小基準によりクラスタリングする手法がある（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】高村大也、松本裕治、"文書分類のための共クラスタリング"、情報処理学会論文誌、Vol.44, No.2, pp. 443-450, 2003.
【非特許文献２】Toshio Uchiyama, M. A. Arbib, "Color Image Segmentation Using Competitive Learning", IEEE Trans.  PAMI, Vol. 16, No. 12, pp. 1197-1206, 1994.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の従来技術の非特許文献１では、確率分布が似ている文書をボトムアップ的にマージする凝集型の階層クラスタリングアルゴリズム（以下、「凝集法」と記す）が示されている。凝集法はクラスタの階層構造が得られるという特長がある反面、個々のクラスタ同士の近さに着目するため、文書集合全体から見た評価基準の最適化に適しているとは言いにくい。
【０００７】
一方、競合学習は逐次更新型のクラスタリングアルゴリズムで、非特許文献２には劣悪な局所最適解へ陥らないような工夫が提案され、評価基準の最適化に比較的適していると考えられる。ところが、競合学習において、上記のエントロピー最小基準を採用すると、必然的に入力文書の確率分布に対して最も合致する確率分布モデルを持つクラスタを選ぶ（勝者を決定する）過程で、クロスエントロピーの計算を要する。このときクラスタが学習したことがない単語が入力文書に含まれていると、対応する確率値がゼロとなり、いわゆるゼロ頻度問題（例えば、「北研二，"確率的言語モデル"，東京大学出版会，1999.」（以下、「文献１」と記す）が起こり、上記のクロスエントロピーの計算に失敗することになる。このゼロ頻度問題を回避するため単語の出現回数を補正するディスカウンティング法（文献１参照）が提案されているが、競合学習においては逐次的に確率分布モデルを更新するため、適切に補正することが困難である。例えば、全ての確率値に予め小さな値を設定することが考えられるが、学習全体を通して適切な値は存在しないため、優れた評価基準を持つ結果を得ることは難しい。
【０００８】
本発明は、上記の点に鑑みなされたもので、競合学習におけるゼロ頻度問題を回避しつつ、評価基準に関して優れた解を得ることが可能な文書データクラスタリング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理構成図である。
【００１０】
本発明（請求項１）は、単語を構成要素とする文書データの集合を空でないいくつかのクラスタに分割する文書データクラスタリング装置であって、
各文書の単語を確率変数とする確率分布を算出し、確率分布記憶手段１８に格納する確率分布算出手段１１０と、
確率分布記憶手段１８のクラスタに属する文書の確率分布からクラスタの確率分布モデルを算出し、確率分布モデル記憶手段１９に格納する確率分布モデル算出手段１２０と、
逐次更新型のクラスタリングアルゴリズムである競合学習により、確率分布モデル記憶手段１９の確率分布モデルの逐次更新を行う確率分布モデル更新手段１３０と、
確率分布モデル記憶手段１９のクラスタの確率分布モデルにより文書が属するクラスタを決定するクラスタ決定手段１４０と、を有し、
クラスタ決定手段１４０は、
確率分布モデル記憶手段１９のクラスタの確率分布モデルによる文書の確率分布のエントロピーを算出し、その結果最も小さな値を与える確率分布モデルに対応したクラスタを当該文書のクラスタと決定する手段を含む。
【００１１】
また、本発明（請求項２）は、請求項１の確率分布モデル更新手段１３０において、
入力文書の確率分布と各確率分布モデルを予め決定されている学習率γを用いて（γ：１−γ）で足し合わせた更新された確率分布モデルを算出する手段を含み、
クラスタ決定手段１４０において、
学習過程においてランダムに選ばれた入力文書に対応して、該入力文書の確率分布に最も合致する確率分布モデルを持つクラスタを勝者として選出するときに、更新された確率分布モデルに基づく入力文書の確率分布のクロスエントロピーが最も小さくなる更新された確率分布を持つクラスタを勝者と決定し、確率分布モデル記憶手段１９の勝者以外のクラスタの確率分布モデルを更新前に戻す手段を含む。
【００１２】
図２は、本発明の原理を説明するための図である。
【００１３】
本発明（請求項３）は、単語を構成要素とする文書データの集合を空でないいくつかのクラスタに分割する文書データクラスタリング方法であって、
確率分布記憶手段と確率分布モデル記憶手段とを有する装置が、
各文書の単語を確率変数とする確率分布を算出し、確率分布記憶手段に格納する確率分布算出ステップ（ステップ１）と、
確率分布記憶手段のクラスタに属する文書の確率分布からクラスタの確率分布モデルを算出し、前記確率分布モデル記憶手段に格納する確率分布モデル算出ステップ（ステップ２）と、
逐次更新型のクラスタリングアルゴリズムである競合学習により、確率分布モデル記憶手段の前記確率分布モデルの逐次更新を行う確率分布モデル更新ステップ（ステップ３）と、
確率分布モデル記憶手段のクラスタの確率分布モデルにより文書が属するクラスタを決定するクラスタ決定ステップ（ステップ４）と、を行い、
クラスタ決定ステップ（ステップ４）において、
確率分布モデル記憶手段のクラスタの確率分布モデルによる文書の確率分布のエントロピーを算出し、その結果最も小さな値を与える確率分布モデルに対応したクラスタを当該文書のクラスタと決定する。
【００１４】
また、本発明（請求項４）は、確率分布モデル更新ステップ（ステップ３）において、
入力文書の確率分布と各確率分布モデルを予め決定されている学習率γを用いて（γ：１−γ）で足し合わせた更新された確率分布モデルを算出し、
クラスタ決定ステップ（ステップ４）において、
学習過程においてランダムに選ばれた入力文書に対応して、該入力文書の確率分布に最も合致する確率分布モデルを持つクラスタを勝者として選出するときに、更新された確率分布モデルに基づく入力文書の確率分布のクロスエントロピーが最も小さくなる更新された確率分布を持つクラスタを勝者と決定し、確率分布モデル記憶手段の勝者以外のクラスタの確率分布モデルを更新前に戻す。
【００１５】
本発明（請求項５）は、請求項１または２に記載の文書データクラスタリング装置を構成する各手段としてコンピュータを機能させるための文書データクラスタリングプログラムである。
【発明の効果】
【００１６】
上記のように、本発明によれば、エントロピー最小基準における競合学習を用いたクラスタリングが実現でき、従来法と比べて評価基準を最適化する意味で優れた結果を得ることができる。クラスタリングはデータマイニングの基本技術であり、確率分布がより近いデータ同士を一括りにするエントロピー最小基準によるクラスタリング手法を用いる文書処理アプリケーションにおいて、性能向上が期待できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の原理構成図である。
【図２】本発明の原理を説明するための図である。
【図３】本発明の一実施の形態における文書データのクラスタリング装置のハードウェア構成図である。
【図４】本発明の一実施の形態における文書データクラスタリング装置の機能構成図である。
【図５】本発明の一実施の形態におけるクラスタリング処理のフローチャートである。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図３は、本発明の一実施の形態における文書データクラスタリング装置のハードウェア構成を示す。同図に示す文書データクラスタリング装置は、ＣＰＵ１１、メモリ１２、ディスプレイ１３、キーボード１４、処理プログラム１５、処理対象記憶部１６、ＯＳ（オペレーティングシステム）１７、文書の確率分布記憶部１８、クラスタの確率分布モデル記憶部１９、勝ち回数記憶部２０、文書のクラスタの記憶部２１から構成される。
【００２０】
上記の処理対象記憶部１６、文書の確率分布記憶部１８、クラスタの確率分布モデル記憶部１９、勝ち回数記憶部２０、文書のクラスタ記憶部２１はハードディスク等の記憶媒体である。
【００２１】
以下に示す文書データのクラスタリングは、上記の処理プログラム１５によりＣＰＵ１１で実行されるが、以下にＣＰＵ１１における処理機能を示す。
【００２２】
図４は、本発明の一実施の形態における文書データクラスタリング装置の機能構成を示す。
【００２３】
同図に示す文書データクラスタリング装置の要部は、確率分布算出部１１０、確率分布モデル算出部１２０、確率分布モデル更新部１３０、クラスタ決定部１４０、クラスタ生成部１５０を有する。
【００２４】
確率分布算出部１１０は、クラスタリング対象の文書が格納された処理対象記憶部１６から入力された文書の単語を確率変数とする確率分布Ｐを算出し、文書の確率分布記憶部１８に格納する。
【００２５】
確率分布モデル算出部１２０は、キーボード１４から入力された分割するクラスタ数、最大繰り返し数、学習率、しきい回数を取得し、ランダムに選んだ文書の確率分布を文書の確率分布記憶部１８から選択して、選択された文書の確率分布と学習率を用いて確率分布モデルＱを求める。
【００２６】
確率分布モデル更新部１３０は、確率分布モデル記憶部１９に対して、逐次更新型のクラスタリングアルゴリズムである競合学習による確率分布モデルを逐次更新する。
【００２７】
クラスタ決定部１４０は、クラスタの確率分布モデル記憶部１９に格納されているクラスタの確率分布モデルによる選択した文書の確率分布のクロスエントロピーを算出し、最も小さな値を与える確率分布モデルに対応したクラスタを勝者として、勝ち回数記憶部２０の当該クラスタの勝ち回数に１を加え、勝者以外のクラスタについては、クラスタの確率分布モデル記憶部１９の確率分布モデルを更新前の状態に戻す。
【００２８】
クラスタ生成部１５０は、クラスタ決定部１４０により勝者クラスタが決定された後、所定の条件により新たなクラスタを生成する。
【００２９】
次に、上記の構成における一連の動作を説明する。
【００３０】
図５は、本発明の一実施の形態におけるクラスタリング処理のフローチャートである。
【００３１】
ステップ１０１）  初期設定として、確率分布算出部１１０は、クラスタリング対象である文書集合を処理対象記憶部１６から順次読み出し、文書に含まれる単語を確率変数とする確率分布Ｐ
Ｐ＝｛ｐ1，…，ｐm，…，ｐM｝
を計算して文書の確率分布記憶部１８に記憶する。ここで、Ｍは確率変数の個数、すなわち、様々な文書に出現する全単語の種類であり、出現する全単語数をＡ，ｍ番目の出現数をＡmとすると、確率値ｐmは
ｐm=Ａm／Ａ                                （１）
により算出でき、確率値ｐmの和は、
【００３２】
【数１】
2011221666.tif 000003
になる。
【００３３】
次に、確率分布モデル算出部１２０は、キーボード１４から分割するクラスタ数ｎ（ｎ≧１）、最大繰り返す回数Ｌ、学習率γ、しきい回数θを取得する。そして、全文書Ｄi（ｉ＝１，…，Ｎ）からランダムに選んだ文書が持つ確率分布Ｐを文書の確率分布記憶部１８から読み出し、１番目のクラスタの確率分布モデルＱ１としてクラスタの確率分布モデル記憶部１９に記憶する。
【００３４】
また、クラスタ決定部１４０はクラスタ数ｕを１に設定し、勝ち回数記憶部２０のクラスタ１の勝ち回数を０に初期化し、繰り返し回数ｒを０に設定する。
【００３５】
ステップ１０２）  確率分布モデル算出部１２０は、全文書からランダムに１つの文書を選択し、その文書に対応する確率分布Ｐを確率分布記憶部１８から取得する。
【００３６】
ステップ１０３）  確率モデル算出部１２０は、ステップ１０２で選択した文書の確率分布Ｐとキーボード１４から入力された学習率γを用いて、
【００３７】
【数２】
2011221666.tif 000004
を求め、確率分布モデル更新部１３０は、クラスタの確率分布モデル記憶部１９の各クラスタＣk（ｋ＝１，…，ｕ）の確率分布モデルＱk（ｋ＝１，…，ｕ）を、上記の式（２）で求められた値により更新する。
【００３８】
ステップ１０４）  クラスタ決定部１４０は、各クラスタＣkの確率分布モデルＱkによる選択した文書の確率分布Ｐのクロスエントロピー
【００３９】
【数３】
2011221666.tif 000005
を算出し、最も小さな値を与える確率分布モデルに対応したクラスタＣを勝者とする。勝者の添え字をｃで表し、勝者の確率分布モデルをＱcとする。もし、同じ値に複数のクラスタが存在した場合は、添え字が小さい方を勝ちとしてもよい。勝ち回数記憶部２０の勝者のクラスタの勝ち回数ｖcに１を加える。そして、クラスタの確率分布モデル記憶部１９の勝者以外のクラスタの確率分布モデルをステップ１０３で更新する前の状態に戻す。
【００４０】
ステップ１０５）  クラスタ決定部１４０は、もし、クラスタ数ｕが分割するクラスタ数ｎに等しいか、勝ち回数記憶部２０の勝者のクラスタの勝ち回数ｖcがしきい回数θ未満であれば、ステップ１０７に移行し、そうでなければステップ１０６へ移行する。
【００４１】
ステップ１０６）  クラスタ数ｕを１増やし、クラスタ生成部１５０でｕ番目のクラスタを生成しクラスタの確率分布モデル記憶部１９に設定し、クラスタ決定部１４０は、クラスタの確率分布モデル記憶部１９のｕ番目のクラスタの確率分布モデルＱuを勝者のクラスタの確率分布モデルＱcで初期化する。また、クラスタ決定部１４０は、勝ち回数記憶部２０の勝者と新たに生成したｕ番目のクラスタの勝ち回数ｖc、ｖuを０に初期化する。
【００４２】
ステップ１０７）  繰り返し回数ｒに１を足し（ｒ＝ｒ＋１）、もしｒが最大繰り返し回数Ｌに等しければステップ１０８に移行し、そうでなければステップ１０２に移行する。
【００４３】
ステップ１０８）  各文書Ｄi（ｉ＝１，…，Ｎ）を順次選択し、以下の手順で属するクラスタを決定する。
【００４４】
まず、確率分布モデル算出部１２０は、文書の確率分布記憶部１８から選択した文書Ｄiの確率分布Ｐiと学習率γを用いて、
【００４５】
【数４】
2011221666.tif 000006
を求め、確率分布モデル更新部１３０は、クラスタの確率分布モデル記憶部１９の全クラスタの確率分布モデルＱkを、上記の式（４）で求めた値により更新し、次に、クラスタ決定部１４０は、各クラスタＣkの確率分布モデルＱkによる文書の確率分布Ｐiのクロスエントロピー
【００４６】
【数５】
2011221666.tif 000007
を算出し、最も小さな値を与える確率分布モデルに対応したクラスタＣkを当該文書のクラスタとし、その情報を文書のクラスタ記憶部２１に記憶し、クラスタの確率分布モデル記憶部１９の確率分布モデルＱkを更新前に戻す。
【００４７】
上記のようにクラスタのモデル（クラスタの確率分布モデル）を文書の特徴である確率分布の所定の割合（学習率γ）で更新することにより、競合学習によるゼロ頻度問題を解決することができる。
【００４８】
なお、上記の図４に示す文書データクラスタリング装置の各構成要素を処理プログラム１５とし、ＣＰＵ１１で実行させる、または、ネットワークを介して流通させることが可能である。
【００４９】
また、構築されたプログラムをハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５１】
１１  ＣＰＵ
１２  メモリ
１３  ディスプレイ
１４  キーボード
１５  処理プログラム
１６  処理対象記憶部
１７  ＯＳ（オペレーティングシステム）
１８  文書の確率分布記憶部、確率分布記憶手段
１９  クラスタの確率分布モデル記憶部、確率分布モデル記憶手段
２０  勝ち回数記憶部
２１  文書のクラスタ記憶部
１１０  確率分布算出部、確率分布算出手段
１２０  確率分布モデル算出部、確率分布算出手段
１３０  確率分布モデル更新部、確率分布モデル更新手段
１４０  クラスタ決定部、クラスタ決定手段
１５０  クラスタ生成部
【図１】
2011221666.tif 000008
【図２】
2011221666.tif 000009
【図３】
2011221666.tif 000010
【図４】
2011221666.tif 000011
【図５】
2011221666.tif 000012