パターン抽出装置、パターン抽出方法及びプログラム
【課題】ラベルが付与されたテキストの数が少量であったとしても、自動分類処理に寄与するパターンを必要な数だけ自動生成する。
【解決手段】ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものを分類モデルとする。分類モデルは、ラベルなしテキストに適用され、当該ラベルなしテキストが所定の集合に属する確率を表す確率データが生成される。そして、少なくとも、生成された確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標が生成される。
【解決手段】ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものを分類モデルとする。分類モデルは、ラベルなしテキストに適用され、当該ラベルなしテキストが所定の集合に属する確率を表す確率データが生成される。そして、少なくとも、生成された確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標が生成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記号系列からなるデータの自動分類処理に寄与する系列のパターンを抽出するための技術に関する。
【背景技術】
【０００２】
記号系列からなるデータ（例えば、文字記号によって記述された文書データや、遺伝子記号によって記述された遺伝子配列など）群を自動分類する技術が存在する。例えば、スパムメールとその他の電子メールが混在する電子メール群を、スパムメールの集合とその他電子メールの集合とに分類する技術などである。このような技術では、或る特徴を持つ系列（記号系列）のパターンに基づいて、データの自動分類処理が行われる。例えば、所定の集合（例えば、スパムメールの集合）に属するデータが含む頻度が高い系列のパターンが用意され、分類対象のデータが当該系列のパターンを含むか否かに応じ、当該分類対象のデータが自動分類される。よって、このような自動分類技術では、その前提として、自動分類処理に寄与する系列のパターン（例えば、スパムメールの集合に属するデータが含む頻度が高い系列のパターン）を生成する必要がある。
【０００３】
一方、記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する技術が存在する（例えば、非特許文献１参照）。
【０００４】
図１は、記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する従来技術を説明するための図である。
【０００５】
以下では、１個以上の記号からなる要素（最小単位）をアイテムと呼び、１個以上のアイテムからなる系列をテキストと呼び、テキストが含む１個以上のアイテムからなる系列をパターンと呼び、テキストの集合をデータベースと呼ぶ。なお、記号の例は、文字、数字、マークなどであり、アイテムの例は、文字、数字、マーク、単語、単語列、塩基、塩基対などである。図１の例では、例えば、「a」〜「d」がアイテムであり、「a b c c」などの系列が1つのテキストであり、テキストが含む「a」「a b」「a c」などの系列がパターンである。また、図１の例では、５つのテキストからなるデータベースを扱う。
【０００６】
ここで、データベース中から、出現頻度がζ=2よりも大きいパターンを抽出することを考える。なお、１つのテキスト中に同じパターンが複数回出現したとしても、そのテキストに対するそのパターンのカウント回数は1回とする。
【０００７】
まず、与えられたデータベース（「入力データベース(IDB)」と呼ぶ）に対し、アイテム(長さ1のパターン)の出現頻度が算出される。図１の例の場合、アイテム「a」「b」「c」「d」の出現頻度は、それぞれ5, 4, 4, 2となる。すなわち、入力データベースにおいて、出現頻度がζ=2より大きいアイテムは「a」「b」「c」の３つである。これらの３つのアイテム「a」「b」「c」は出力リスト（OUT）の要素として記憶に格納され（OUT={a, b, c}）、その後、それぞれのパターン「a」「b」「c」から始まるパターンの出現頻度が算出される。「d」から始まるパターンの出現頻度がζ=2よりも大きくなることはないので、「d」から始まるパターンは以降の処理対象とされない。なお、この例では、プロジェクションによって生成されたデータベースを用い、入力データベースにおける、パターン「a」「b」「c」から始まるパターンの出現頻度が算出される。プロジェクションとは、データベース中の各エントリ（初期はテキスト）に対し、それぞれの先頭から或るアイテム（「着目アイテム」と呼ぶ）が最初に見つかった位置までを削除し、残りの系列をデータベースのエントリとして新たなデータベースを作成することを示す。なお、プロジェクションにおいて、着目アイテムを含まないエントリはデータベースから除外される。ここで説明するアイテムの出現頻度を算出する処理では、出現頻度がζ=2より大きいアイテム「a」「b」「c」が、それぞれ着目アイテムとされる。
【０００８】
まず、入力データベースに対し、「a」を着目アイテムとしてプロジェクション（prj(a)）を行うと、「b c c」、「c」、「c」、「b d」というエントリのデータベース(DB(a))が作成される。次にこのデータベース(DB(a))に対し、アイテム(長さ1のパターン)の出現頻度を求める。ここで、頻度がζ=2より大きいアイテムがあれば、そのアイテムの前にこれまでのプロジェクションの着目アイテムを付加した系列であるパターンが出力リスト（OUT）の要素として記憶に格納される。図１のプロジェクション（prj(a)）の例の場合、出現頻度がζ=2より大きいアイテムは「b」「c」の２つである。よって、各アイテム「b」「c」の前に、それぞれ、これまでのプロジェクションの着目アイテム「a」を付加した系列であるパターン「a b」「a c」が出力リスト（OUT）の要素として記憶に格納される（OUT={a, b, c, a b, a c}）。さらに、データベース（DB(a)）に対し、再度、プロジェクションが実行される。図１の例では、データベース(DB(a))に対し、頻度がζ=2より大きいアイテム「b」を着目アイテムとしたプロジェクション（prj(b)）が行われ、データベース(DB(a b))が生成される。データベース(DB(a b))には、頻度がζ=2より大きいアイテムが存在しないため、出力リスト（OUT）に新たな要素が加えられない。次に、データベース(DB(a))に戻り、頻度がζ=2より大きいアイテム「c」を着目アイテムとしたプロジェクション（prj(c)）が行われ、データベース(DB(a c))が生成される。データベース(DB(a c))には、頻度がζ=2より大きいアイテムが存在しないため、出力リスト（OUT）に新たな要素が加えられない。次に、入力データベース(IDB)に戻り、「b」を着目アイテムとしたプロジェクション（prj(b)）が行われ、データベース(DB(b))が生成され、「b a」「b c」が出力リスト（OUT）の要素として記憶に格納される（OUT={a, b, c, a b, a c, b a, b c}）。その後、同様な基準に従い、深さ優先順で、データベース(DB(b))に対するアイテム「a」「c」を着目アイテムとしたプロジェクション、入力データベース(IDB)に対するアイテム「c」を着目アイテムとしたプロジェクションが実行され、処理が終了する。このようにプロジェクションを再帰的に行うことにより、出現頻度が或る値ζより大きいパターンを効率的に求めることができる。図１の例では、出現頻度がζ=2よりも大きいパターンとして「a, b, c, a b, a c, b a, b c」が得られる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】J. Pei, J. Han, B.Mortazavi-Asl, H.Pinto, Q.Chen, U.Dayal, and M.-C. Hsu 2001. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth In Proc. of the 17th ICDE, pages 215-224.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、非特許文献１にあるような従来技術では、データベースから出現頻度の高いパターンを自動抽出することはできても、自動分類処理に寄与するパターンを自動生成することはできない。例えば、データベースに属する各テキストにテキストが属する集合を表すデータであるラベル（例えば、スパムメールであるか否かを表すラベルなど）が付与されていたとしても、非特許文献１にあるような従来技術では、ラベルを考慮したパターン抽出を行うことはできない。
【００１１】
また、ラベルが対応付けられた（ラベルが付与された）テキストをラベルが示す集合ごとに分類し（例えば、スパムメールであるか否かに分類し）、分類された集合ごとに非特許文献１にあるような従来技術を適用すれば、集合ごとに別個に、出現頻度が高いパターンを抽出することができる。このようにして抽出されるパターンは、自動分類処理に寄与するパターンである。しかしながら、通常、テキストにラベルを対応付ける処理は人手によって行われ、そのコストは高い。よって、ラベルが対応付けられたテキストを大量に用意することは難しい。さらに、少量のテキストからパターン抽出が行われた場合には抽出されるパターンの数が非常に少なくなり、抽出されたパターンを用いた自動分類処理の性能が低下してしまう。
【００１２】
本発明はこのような点に鑑みてなされたものであり、ラベルが付与されたテキストの数が少量であったとしても、自動分類処理に寄与するパターンを必要な数だけ自動生成することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、１個以上の記号からなる要素をアイテムとし、１個以上のアイテムからなる系列をテキストとし、テキストが含む１個以上のアイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられたテキストをラベルありテキストとし、ラベルに対応付けられていないテキストをラベルなしテキストとし、ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものを分類モデルとする。分類モデルは、ラベルなしテキストに適用され、当該ラベルなしテキストが所定の集合に属する確率を表す確率データが生成される。そして、少なくとも、生成された確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標が生成される。
【発明の効果】
【００１４】
本発明で生成される指標を用いることで、テキストの自動分類処理に寄与する度合いの高いパターンを自動生成できる。また、当該指標はラベルなしテキストに分類モデルを適用した結果を用いて生成できる。よって、本発明では、ラベルが付与されたテキストの数が少量であったとしても、自動分類処理に寄与するパターンを必要な数だけ自動生成することができる。
【図面の簡単な説明】
【００１５】
【図１】記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する従来技術を説明するための図。
【図２】実施形態のパターン抽出装置の機能構成を説明するためのブロック図。
【図３】パターン抽出装置の処理を説明するための図。
【図４】パターン抽出装置の処理を説明するための図。
【図５】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図６】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図７】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図８】ステップＳ１４の処理の具体例を説明するための擬似コード。
【図９】ステップＳ１４の実施例を説明するための図。
【図１０】ステップＳ１４の実施例を説明するための図。
【図１１】ステップＳ１４の実施例を説明するための図。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
＜機能構成＞
図２は、実施形態のパターン抽出装置１の機能構成を説明するためのブロック図である。
【００１８】
図２に例示するように、本形態のパターン抽出装置１は、訓練部１１と、分類部１２と、データベース合成部１３と、抽出部１４と、制御部１５と、記憶部１６ａ〜１６ｅとを有する。抽出部１４は、指標生成部１４ａと、限界値生成部１４ｂと、探索部１４ｃとを有する。なお、本形態のパターン抽出装置１は、例えば、CPU(central processing unit)、RAM(random-access memory)、ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに、所定のプログラムが読込まれて構成される特別な装置である。すなわち、訓練部１１、分類部１２、データベース合成部１３、抽出部１４及び制御部１５は、例えば、所定のプログラムを実行するCPUである。また、記憶部１６ａ〜１６ｅは、例えば、ハードディスク装置などの補助記憶装置、RAM、レジスタ、若しくは、キャッシュメモリ、又は、これらの少なくとも一部が結合された記憶領域である。また、訓練部１１、分類部１２、データベース合成部１３、抽出部１４及び制御部１５の少なくとも一部の機能が集積回路によって構成されてもよいし、記憶部１６ａ〜１６ｅの少なくとも一部の記憶領域が集積回路内に存在してもよい。なお、パターン抽出装置１は、制御部１５の制御のもと、各処理を実行する。また、以下では一部で説明を省略するが、各演算において生成されたデータは各記憶部に格納され、必要に応じてそこから読み出されて各演算に用いられる。
【００１９】
＜処理＞
図３、４は、パターン抽出装置１の処理を説明するための図である。以下、これらの図を用いてパターン抽出装置１の処理を説明する。
【００２０】
［事前処理］
事前処理として、ラベルありテキストを含むラベルありデータとラベルなしテキストを含むラベルなしデータとが、それぞれ、１個以上、記憶部１６ａ（図２）に格納される。ラベルありテキスト及びラベルなしテキストの例は、文字記号によって記述された文書データや、遺伝子記号によって記述された遺伝子配列や、プログラムコードによって記述されたプログラム列などである。また、ラベルありテキストは、事前に人間によって、それぞれのテキストが属する集合を表すデータであるラベルが対応付けられたテキストである。なお、集合の数は２以上であればいくつでもよいが、以下では２個の集合が設定され、一方の集合を「P+（正例：+）」とし、他方の集合を「P-（負例：-）」とする。図４の例では、識別子(ID)とテキスト（ラベルありテキスト）とラベルの内容(P+,P-)(ラベルが集合P+を表すなら(P+,P-)=(1,0)、ラベルが集合P-を表すなら(P+,P-)=(0,1)）との組が、ラベルありデータとされる。また、識別子(ID)とテキスト（ラベルなしテキスト）とラベルの内容(P+,P-)が不明であることを示す情報（(P+,P-)=(unk,unk)）との組が、ラベルなしデータとされる。
【００２１】
また、予め定められた減衰パラメータλと、出力リストの要素の上限値を表すパラメータKとが、記憶部１６ｅに格納される。なお、減衰パラメータλは、例えば、0≦λ≦1の範囲、好ましくは、0＜λ＜1の範囲から事前に選択された値である。また、パラメータKは、例えば、事前に選択された正整数である。
【００２２】
［パターン抽出処理］
まず、訓練部１１が、記憶部１６ａから、ラベルありデータが含むラベルありテキストを抽出し、当該ラベルありテキストを訓練データとして用い、適用された任意のテキストが所定の集合（クラス）に属する確率を表す確率データを出力するように構成された統計モデルである分類モデルを生成する。生成された分類モデルは記憶部１６ｂに格納される（ステップＳ１１）。なお、分類モデルは、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものであればどのようなものでもよい。例えば、ナイーブ・ベイズ法や最大エントロピー法などの周知の統計方法におけるモデルを分類モデルとすればよい。以下に、ナイーブ・ベイズ法を用いる場合の分類モデルを例示する。
【００２３】
［ステップＳ１１の具体例（ナイーブ・ベイズ法の例）］
ナイーブ・ベイズ法では、テキストxが所定の集合（クラス）cに属する確率Pr(c|x)が以下の式で定義される。
【００２４】
【数１】
ここで、wiはテキストxのi番目のアイテムを表し、N(wi,x)は、テキストxにおけるアイテムwiの出現頻度を表す。Pr(c)は、テキストxが集合cに属することの生起確率を表し、以下の式で定義される。
【００２５】
【数２】
また、Pr(wi|c)は以下の式で定義される。
【００２６】
【数３】
ナイーブ・ベイズ法における分類モデルは、訓練データであるラベルありテキストを用いて算出（学習）された式(2)(3)の値となる。以下にナイーブ・ベイズ法において学習される分類モデルを例示する。
【００２７】
この例では、以下の１０個のラベルありテキストを訓練データとして用い、適用された任意のテキストxが集合P+に属する確率を表す確率データを出力するように構成された分類モデルを生成する。
【００２８】
【表１】
この場合、訓練データであるラベルありテキストがラベルP+で表される集合c=P+に属する生起確率Pr(P+)、及び、訓練データであるラベルありテキストがラベルP-で表される集合c=P-に属する生起確率Pr(P-)は以下のようになる。
【００２９】
Pr(P+)=7/10 …(4)
Pr(P-)=3/10 …(5)
また、各単語wi=a〜iについてのPr(wi|P+)は以下のようになる。
【００３０】
【数４】
また、各単語wi=a〜iについてのPr(wi|P-)は以下のようになる。
【００３１】
【数５】
この例では、式(1)から定まるPr(P+|x)と式(4)〜(23)とが分類モデルとなる（［ステップＳ１１の具体例（ナイーブ・ベイズ法の例）］の説明終わり）。なお、ステップＳ１１の処理は、必ずしもパターン抽出処理が行われるたびに実行される必要はなく、過去に生成された分類モデルを使用できるのであれば、ステップＳ１１の処理が省略されてもよい。
【００３２】
次に、分類部１２に、上述のラベルなしテキストと分類モデルとが入力される。分類部１２は、分類モデルをラベルなしテキストに適用し、当該ラベルなしテキストが所定の集合に属する確率を表す確率データを生成する（ステップＳ１２）。この処理の具体的な方法は分類モデルに応じて異なる。例えば、前述したナイーブ・ベイズ法おける分類モデルが用いられる場合には、以下のような確率データが生成される。
【００３３】
［ステップＳ１２の具体例（ナイーブ・ベイズ法の例）］
前述したナイーブ・ベイズ法おける分類モデルが用いられる場合、式(1)に従って、入力されたラベルなしテキストxが所定の集合cに属する確率Pr(c|x)が算出される。例えば、式(1)から定まるPr(P+|x)と式(4)〜(23)とからなる分類モデルに、ラベルなしテキストx=a a c c d d fが適用される場合、当該ラベルなしテキストx=a a c c d d fが、ラベルP+で表される所定の集合に属する確率Pr(P+|x)は、
【００３４】
【数６】
となる（［ステップＳ１２の具体例（ナイーブ・ベイズ法の例）］の説明終わり）。
【００３５】
以上のように生成された確率Pr(P+|x)は、対応するラベルなしテキストに対応付けられ、確率データ付きデータとして記憶部１６ｃに格納される。例えば、図４の例では、識別子(ID)とテキスト（ラベルなしテキスト）と確率Pr(P+|x)と確率Pr(P-|x)=1-Pr(P+|x)とが互いに対応付けられた確率データ付きデータが、記憶部１６ｃに格納される。
【００３６】
次に、データベース合成部１３（図２）に、記憶部１６ａに格納されたラベルありデータと、記憶部１６ｃに格納された確率データ付きデータと、記憶部１６ｅに格納された減衰パラメータλとが入力される。データベース合成部１３は、ラベルありデータと確率データ付きデータとを合成したデータベースを生成する（ステップＳ１３）。この際、確率データ付きデータの含む確率Pr(P+|x)，Pr(P-|x)が分類モデルを用いて自動的に生成されたものであることを考慮し、確率データ付きデータが含む確率Pr(P+|x)，Pr(P-|x)に減衰パラメータλが乗じられる。図４の例では、減衰パラメータλ=0.5とし、データベースが生成されている。生成されたデータベースは記憶部１６ｄに格納される。
【００３７】
次に、抽出部１４が、記憶部１６ｄに格納されたデータベースと、記憶部１６ｅに格納されたパラメータK及び減衰パラメータλとを入力とし、テキストのラベル分類に寄与する度合い（テキストの自動分類処理に寄与する度合い）の高い、K個のパターンを抽出し、それらを要素とする出力リストを出力する（ステップＳ１４）。以下に、ステップＳ１４の処理の詳細を説明する。
【００３８】
［指標］
従来の手法では、パターンの出現頻度に基づき、或るデータベースに含まれるパターンを抽出するか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが、決定されていた。これに対し、本形態では、パターンの出現頻度ではなく、パターンがラベル分類に寄与する度合い（すなわち、パターンと、当該パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さ）を表す指標に基づき、或るデータベースに含まれるパターンを抽出するか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００３９】
この指標は、抽出部１４の指標生成部１４ａが、少なくとも、分類部１２で生成された確率データから定まる値を用いて生成する。以下に、指標生成部１４ａが生成する指標の一例を示す。
【００４０】
この例では、以下のような分割表を考える。
【００４１】
【表２】
ここで、記憶部１６ｄに格納されたデータベースは、|DL|個（|DL|≧0）のラベルありテキストと、分類部１２で確率データがそれぞれ生成された|DU|個（|DU|＞0）のラベルなしテキストとを含むものとする。この例では|DL|≧1とする。なお、|DL|はデータベースが含むラベルありテキストの総数を表し、|DU|はデータベースが含むラベルなしテキストの総数を表す。また、DLはラベルありテキストの集合を表し、DUはラベルなしテキストの集合を表す。
【００４２】
Nはデータベースが含むラベルありテキストの総数|DL|から定まる値と、データベースが含むラベルなしテキストの総数|DU|から定まる値との和である。この例では、以下のように、データベースが含むラベルありテキストの総数|DL|と、データベースが含むラベルなしテキストの総数DUから定まる値と減衰パラメータλとの積との和をNとする。
【００４３】
N=|DL|+λ・|DU| …(25)
Mは、データベースが含むラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値と、分類部１２で生成されたラベルありテキストが集合P+に属する確率を表す確率データから定まる値の総数との和である。この例では、以下のように、データベースが含むラベルありテキストのうち所定の集合P+に属することを表すラベルに対応付けられたものの総数と、ラベルありテキストが集合P+に属する確率と減衰パラメータλとの積の総数との和をMとする。
【００４４】
【数７】
なお、diはテキストを表し、I(di)はラベルありテキストdi∈DLが集合P+に属するときに1となり、それ以外のときに0となる関数を表す。また、Pr(P+|dj)(dj∈DU)は、ラベルなしテキストdj∈DUが集合P+に属する確率を表す。
【００４５】
y(α)は、データベースが含むラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうちパターンαを含むものの総数から定まる値と、パターンαを含むラベルなしテキストが所定の集合に属する確率を表す確率データから定まる値の総数との和を表す。この例では、以下のように、データベースが含むラベルありテキストであって集合P+に属することを表すラベルに対応付けられたラベルありテキストのうちパターンαを含むものの総数と、パターンαを含むラベルなしテキストが集合P+に属する確率と減衰パラメータλとの積の総数との和をy(α)とする。
【００４６】
【数８】
なお、F(di,α)は、テキストdiがパターンαを含むときに1となり、それ以外のときに0となる関数である。
【００４７】
x(α)は、パターンαを含むラベルありテキストの総数から定まる値と、パターンαを含むラベルなしテキストの総数から定まる値との和を表す。この例では、以下のように、パターンαを含むラベルありテキストの総数と、パターンαを含むラベルなしテキストの総数と減衰パラメータλとの積との和をx(α)とする。
【００４８】
【数９】
このとき、パターンαと、当該パターンαを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標として、以下のΧ2(α)を用いる。
【００４９】
【数１０】
この例の場合、指標生成部１４ａは、記憶部１６ｄに格納されたデータベースと、記憶部１６ｅに格納された減衰パラメータλとを入力とし、式(29)にしたがって指標Χ2(α)を生成する。パターンαに対する指標Χ2(α)は記憶部１６ｅに格納される。
【００５０】
抽出部１４は、上記の指標に基づき、ラベル分類に寄与する度合いの高い順に選択したK個のパターンを、出力リストLの要素として出力する。本形態の例では、各パターンに対して上記の指標を順次生成していき、K個以上のパターンにそれぞれ対応する指標が生成された場合に、ラベル分類に寄与する度合いが高い順に数えてK番目の指標を閾値τKとする。そして、その後生成される各指標が当該閾値τKに基づく出力条件を満たすか否かに応じ、その指標に対応するパターンを出力リストLの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。例えば、式(29)の指標Χ2(α)を用いる場合には、K個以上のパターンにそれぞれ対応する指標が生成された場合に、それらのうちでK番目に大きい指標を閾値τKとする。そして、その後生成される各指標が閾値τKを超えるという出力条件を満たすか否かに応じ、その指標に対応するパターンを出力リストLの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００５１】
［指標の限界値］
ただし、或るパターンαに対応する指標が出力条件を満たさない場合であっても、当該パターンαに１個以上のアイテムが付加された新たなパターンに対応する指標が出力条件を満たす場合がある。すなわち、指標が出力条件を満たさない場合であっても、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行った場合、出力条件を満たすパターンが検出される場合がある。
【００５２】
そのため、本形態では、抽出部１４の限界値生成部１４ｂが、或るパターンαに１個以上のアイテムが付加された任意の系列である任意パターンと、当該任意パターンを含む任意のテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標の限界値を生成する。当該限界値は、パターンαに１個以上のアイテムが付加された任意パターンに対応する指標の最良値（最もラベル分類に寄与する度合いが高い値）を表すものである。例えば、式(29)の指標Χ2(α)が用いられる場合には、パターンαに対して以下の限界値Χ2max(α)が生成される。なお、Χ2(α, y=x)はy=xである場合のΧ2(α)を表し、Χ2(α,y=0)はy=0である場合のΧ2(α)を表し、max(ν, μ)は、ν≧μの場合にνとなり、ν＜μの場合にμとなる関数を表す。
【００５３】
Χ2max(α)=max(Χ2(α, y=x), Χ2(α,y=0)) …(30)
そして、限界値が所定の探索条件を満たすか否かに応じて、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００５４】
［探索処理］
抽出部１４の探索部１４ｃは、判定対象のパターンに対して生成された上記の指標と限界値とを用い、判定対象のパターンを出力リストの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かを決定する。
【００５５】
(I)すなわち、第１パターンαに対して生成された指標が所定の第１出力条件（例えば、Χ2(α)＞τK）を満たす場合、探索部１４ｃが、第１パターンαを出力リストの要素として出力するとともに、指標生成部１４ａが、当該第１パターンαに１個以上のアイテムが付加された系列である第２パターンと、当該第２パターンを含む第２テキストを当該第２テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第２指標を生成する。そして、その後の再帰的な処理により、当該第２指標が所定の第２出力条件を満たしたのであれば、当該第２パターンが出力リストの要素として出力される。
【００５６】
(II)また、限界値生成部１４ｂが、第１パターンαに対応する指標が第１出力条件を満たさないが限界値が所定の探索条件を満たすときには（例えば、Χ2(α)≦τKかつΧ2max(α)＞τK）、探索部１４ｃが、当該第１パターンαを出力リストの要素として出力することなく、指標生成部１４ａが、当該第１パターンαに１個以上のアイテムが付加された系列である第３パターンと、当該第３パターンを含む第３テキストを当該第３テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第３指標を生成する。そして、その後の再帰的な処理により、当該第３指標が所定の第３出力条件を満たしたのであれば、当該第３パターンが出力リストの要素として出力される。
【００５７】
(III)また、第１パターンαに対応する指標が第１出力条件を満たさず、限界値も所定の探索条件を満たさないときには（例えば、Χ2(α)≦τKかつΧ2max(α)≦τK）、当該第１パターンαが出力リストの要素とされず、かつ、上記の第３指標も生成されない。
【００５８】
これらの抽出部１４の処理を、式(29)の指標Χ2(α)と式(30)の限界値Χ2max(α)とを用いる場合に限定して言い換えると以下のようになる。
【００５９】
(I)Χ2(α)＞τKなら、パターンαを出力リストの要素として出力するとともに、プロジェクションを行って、パターンαに１個以上のアイテムが付加された系列を新たなパターンαとし、再帰的な処理を行う。
【００６０】
(II)Χ2(α)≦τKかつΧ2max(α)＞τKなら、パターンαを出力リストの要素とすることなくプロジェクションを行って、パターンαに１個以上のアイテムが付加された系列を新たなパターンαとし、再帰的な処理を行う。
【００６１】
(III)Χ2(α)≦τKかつΧ2max(α)≦τKなら、パターンαを出力リストの要素とせず、プロジェクションも行わず、パターンαに１個以上のアイテムが付加された系列に対する処理を行わない。
【００６２】
［ステップＳ１４の処理の具体例］
図５から図７は、ステップＳ１４の処理の具体例を説明するためのフローチャートである。図８は、ステップＳ１４の処理の具体例を説明するための擬似コードである。以下、これらの図を用いて、ステップＳ１４の処理の具体例を説明する。
【００６３】
まず、抽出部１４の探索部１４ｃが、パターンαを空に設定し（α=[ ]）、Rを記憶部１６ｄに格納されたデータベースとし、閾値τK=nan（未定であることを表す値）とする（ステップＳ１４０１）。これらの値は記憶部１６ｅに格納される。
【００６４】
次に、探索部１４ｃが、Rが空集合（R={ }）であるか否かを判定する（ステップＳ１４０２）。ここで、R={ }であれば処理が終了する。一方、R={ }でなければ、探索部１４ｃが、RRを空集合（RR←{ }）に設定し（ステップＳ１４０３）、αが空であるか（α=[ ]）否かを判定する（ステップＳ１４０４）。
【００６５】
ここでαが空であると判定された場合、探索部１４ｃは、RRをRに設定し（RR←R）（ステップＳ１４０５）、Rが含むアイテムの集合をβ（β←itemset(R)）として設定し（ステップＳ１４０６）、後述のステップＳ１４１５の処理が実行される。
【００６６】
一方、αが空でないと判定された場合、Rが含むアイテムからなる系列のエントリtrans(trans∈R)を選択する（ステップＳ１４０８）。なお、プロジェクションが１度も実行されておらず、Rが記憶部１６ｄに格納されたデータベースである場合、記憶部１６ｄに格納されたデータベースが含むテキストがエントリtransに相当する。また、過去にプロジェクションが実行されている場合、テキストからそれまでのプロジェクションによって削除されたアイテムを除いた残りの系列がエントリtransに相当する。次に、探索部１４ｃは、選択したエントリtransに対し、その先頭からアイテムαが最初に見つかった位置までを削除し、残りの系列をsubseqとして設定する処理（subseq ← postseq(last(α), trans)）を実行する（ステップＳ１４０９）。次に、探索部１４ｃは、subseqが空でないか（subseq≠[ ]）否かを判定する（ステップＳ１４１０）。ここで、subseqが空でないならば、探索部１４ｃは、RRにsubseqをエントリとして追加したものを新たなRR（RR←append(RR, subseq)）として設定し（ステップＳ１４１１）、ステップＳ１４１２の処理を実行する。一方、subseqが空であるならば、探索部１４ｃは、ステップＳ１４１１の処理を実行することなく、ステップＳ１４１２の処理を実行する。ステップＳ１４１２の処理では、探索部１４ｃが、すべてのエントリtrans∈Rについて処理が終了したか否かを判定する（ステップＳ１４１２）。ここで、すべてのエントリtrans∈Rについて処理が終了していないと判定されたのであれば、処理がステップＳ１４０８に戻される。一方、すべてのエントリtrans∈Rについて処理が終了したと判定されたのであれば、探索部１４ｃは、RRが含むアイテムの集合をβ（β←itemset(RR)）として設定し（ステップＳ１４１３）、ステップＳ１４１５の処理が実行される。なお、ステップＳ１４０８からＳ１４１３までの処理がプロジェクションに相当する。
【００６７】
ステップＳ１４１５の処理では、探索部１４ｃがβに属するアイテム（item∈β）を選択する（ステップＳ１４１５）。次に、探索部１４ｃが、αの最後にステップＳ１４１５で選択されたアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）として生成する（ステップＳ１４１６）。次に、探索部１４ｃが出力リストLに属するパターンの要素数|L|が、記憶部１６ｅに格納されたパラメータK未満であるか（|L|<K）否かを判定する（ステップＳ１４１７）。ここで、|L|<Kであると判定された場合、指標生成部１４ａが、パターンαに対する指標Χ2(α)を式(29)にしたがって生成し、探索部１４ｃが、パターンαと指標Χ2(α)との組[α, Χ2(α)]を出力リストLの要素として加え、出力リストLを更新する。更新された出力リストL（L←append(L, [α, Χ2(α)])）は記憶部１６ｅに格納される（ステップＳ１４１８）。次に、探索部１４ｃが、出力リストLに属するパターンの要素数|L|が、記憶部１６ｅに格納されたパラメータKと同値であるか（|L|=K）否かを判定する（ステップＳ１４１９）。|L|=Kでないと判定された場合、後述するステップＳ１４２２の処理が実行される。一方、|L|=Kであると判定された場合、探索部１４ｃが、出力リストLの要素[α, Χ2(α)]を指標Χ2(α)が大きい順に並び替えたものを新たな出力リストL（L=sort(L)）とし、記憶部１６ｅに格納する（ステップＳ１４２０）。次に、探索部１４ｃが、出力リストLのK番目の要素の指標（最も小さな値の指標）を閾値τK（τK=Χ2(L[K])）とし、閾値τKを更新して記憶部１６ｅに格納し（ステップＳ１４２１）、次のステップＳ１４２２の処理が実行される。
【００６８】
ステップＳ１４２２の処理では、抽出部１４が、現在の（α，RR, K）に対し、ステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４２２）。その後、後述するステップＳ１４３１の処理が実行される。
【００６９】
一方、ステップＳ１４１８で、|L|<Kでないと判定された場合、指標生成部１４ａが、パターンαに対する指標Χ2(α)を式(29)にしたがって生成して記憶部１６ｅに格納し、探索部１４ｃが、記憶部１６ｅに格納された閾値τKを用い、Χ2(α)＞τKを満たすか否かを判定する（ステップＳ１４２３）。なお、閾値が未定である場合（τK=nan）には、Χ2(α)＞τKを満たさないものとする。ここで、Χ2(α)＞τKを満たすと判定された場合には、探索部１４ｃが、記憶部１６ｅに格納された出力リストLの最後の要素（最も指標Χ2(α)の値が小さな要素）を削除し、残りの要素からなる新たな出力リストL（L=lastdel(L)）を生成し、記憶部１６ｅに格納する（ステップＳ１４２４）。次に、探索部１４ｃが、パターンαと指標Χ2(α)との組[α, Χ2(α)]を出力リストLの要素として加え、出力リストLを更新する。更新された出力リストL（L←append(L, [α, Χ2(α)])）を記憶部１６ｅに格納される（ステップＳ１４２５）。次に、探索部１４ｃが、この出力リストLの要素[α, Χ2(α)]を指標Χ2(α)が大きい順に並び替えたものを新たな出力リストL（L=sort(L)）とし、記憶部１６ｅに格納する（ステップＳ１４２６）。次に、探索部１４ｃが、出力リストLのK番目の要素の指標（最も小さな値の指標）を閾値τK（τK=Χ2(L[K])）とし、閾値τKを更新して記憶部１６ｅに格納する（ステップＳ１４２７）。次に、抽出部１４が、現在の（α，RR, K）に対し、ステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４２８）。その後、後述するステップＳ１４３１の処理が実行される。
【００７０】
一方、ステップＳ１４２３の判定で、Χ2(α)＞τKを満たさないと判定された場合には、限界値生成部１４ｂが、パターンαに対する限界値Χ2max(α)を式(30)に従って生成して記憶部１６ｅに格納し、探索部１４ｃが、記憶部１６ｅに格納された閾値τKを用い、Χ2max(α)＞τKを満たすか否かを判定する（ステップＳ１４２９）。ここで、Χ2max(α)＞τKを満たすと判定された場合、抽出部１４が、現在の（α，RR, K）に対してステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４３０）。その後、以下のステップＳ１４３１の処理が実行される。一方、Χ2max(α)＞τKを満たさないと判定された場合、ステップＳ１４３０の処理が実行されることなく、ステップＳ１４３１の処理が実行される。
【００７１】
ステップＳ１４３１の処理では、探索部１４ｃが、すべてのアイテムitem∈βについて処理が終了したか否かを判定する（ステップＳ１４３１）。ここで、すべてのアイテムitem∈βについて処理が終了していれば、ステップＳ１４の処理が終了となる。一方、すべてのアイテムitem∈βについて処理が終了していなければ、処理がステップＳ１４１５に戻される。
【００７２】
［ステップＳ１４の実施例］
図９から図１１は、ステップＳ１４の実施例を説明するための図である。以下に、これらの図を用いながら、ステップＳ１４の実施例を説明する。なお、この実施例では、記憶部１６ｄに格納される初期のデータベースとして図３のデータベース（減衰パラメータλ=0.5が乗じられたもの）を用いる。また、K=4, λ=0.5とする。また、M=1.8, N=3.5であり、これらは初期のデータベースにおける定数である。また、図１０及び図１１に示す木構造の各ノードのアイテムa,b,c,dの右上添字は、その木のルートのアイテムからノードのアイテムまでの系列からなるパターンαの指標Χ2(α)であり、右下添字はそのパターンαの限界値Χ2max(α)を表す。また、図１０及び図１１に示すxは、パターンαの最後にβの要素であるアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）とし、当該新たなパターンαについて、式(28)にしたがって生成されたx(α)を表す。また、図１０及び図１１に示すyは、パターンαの最後にβの要素であるアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）とし、当該新たなパターンαについて、式(27)にしたがって生成されたy(α)を表す。
【００７３】
1. まず、α=[ ], RR←R, β={a,b,c,d}とされる（ステップＳ１４０１〜Ｓ１４０６／図１０（Ａ））。
【００７４】
2. 次に、α=aとされる（ステップＳ１４１５，Ｓ１４１６）。|L|<K(k=4)であるから、aと指標Χ2(a)=0との組[a, 0]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ａ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理（call WTPS（α，RR, K）／ステップＳ１４０２〜Ｓ１４３１）の中でβ={b,c,d}とされる（図１０（Ｂ））。
【００７５】
3. 2の再帰的処理の中で、α=a bとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a bと指標Χ2(a b)=0.5との組[a b, 0.5]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ｂ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理の中でβ={c,d}とされる（図１０（Ｂ））。
【００７６】
4. 3の再帰的処理の中で、β={c, d}のうちcがitemとして選択され、α=a b cとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a b cと指標Χ2(a b c)=1.3との組[a b c, 1.3]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ｃ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理の中でβ={c}とされる（図１０（Ｂ））。
【００７７】
5. 4の再帰的処理の中で、α=a b c cとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a b c cと指標Χ2(a b c c)=1.3との組[a b c c, 1.3]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８）。
【００７８】
6. 4の再帰的処理の中で、|L|=K(k=4)となったため、出力リストLの要素を指標Χ2(α)に基づいて並び替え、閾値τK=0が得られる（ステップＳ１４１９〜Ｓ１４２１／図９（Ｄ））。
【００７９】
7. これ以上のプロジェクションが不可能なので（4の再帰的処理のステップＳ１４３１でyesとなるので）4の再帰的処理が終了し、3の再帰的処理に戻る。ここでは、α=a b, β={c, d}であるが、β={c, d}のうちcについては処理済みである。
【００８０】
8. 3の再帰的処理の中で、β={c, d}のうちdがitemとして選択され、α=a b dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a b dに対する指標Χ2(a b d)=0.2が閾値τK=0を超えるため（ステップＳ１４２３）、出力リストLから[a, 0]が削除され、a b dと指標Χ2(a b d)=0.2との組[a b d, 0.2]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=0.2に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｅ））。
【００８１】
9. これ以上のプロジェクションが不可能なので（3の再帰的処理のステップＳ１４３１でyesとなるので）、3の再帰的処理が終了し、2の再帰的処理に戻る。ここでは、α=a, β={b, c, d}であるが、β={b, c, d}のうちbについては処理済みである（図１０（Ｂ））。
【００８２】
10. 2の再帰的処理の中で、β={b, c, d}のうちcがitemとして選択され、α=a cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a cに対する指標Χ2(a c)=2.1が閾値τK=0.2を超えるため（ステップＳ１４２３）、出力リストLから[a b d, 0.2]が削除され、a cと指標Χ2(a c)=2.1との組[a c, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=0.5に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｆ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={c}とされる（図１０（Ｂ））。
【００８３】
11. 10の再帰的処理の中で、β={c}のうちcがitemとして選択され、α=a c cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a c cに対する指標Χ2(a c c)=1.3が閾値τK=0.5を超えるため（ステップＳ１４２３）、出力リストLから[a b, 0.5]が削除され、a c cと指標Χ2(a c c)=1.3との組[a c, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｇ））。
【００８４】
12. これ以上のプロジェクションが不可能なので（10の再帰的処理のステップＳ１４３１でyesとなるので）、10の再帰的処理が終了し、2の再帰的処理に戻る。ここでは、α=a, β={b, c, d}であるが、β={b, c, d}のうちb, cについては処理済みである（図１０（Ｂ））。
【００８５】
13. 2の再帰的処理の中で、β={b, c, d}のうちdがitemとして選択され、α=a dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a dに対する指標Χ2(a d)=0.2も限界値Χ2max(a d)=0.5も閾値τK=1.3を越えず（ステップＳ１４２３，Ｓ１４２９）、β={b, c, d}のすべての要素が処理済であるため（ステップＳ１４３１）、2の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、α=[ ], β={a,b,c,d}であるが、β={a,b,c,d}のうちaについては処理済みである。
【００８６】
14. 最初のループ処理の中で、β={a,b,c,d}のうちbがitemとして選択され、α=bとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=bに対する指標Χ2(b)=0は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b)=2.7が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c,d}とされる（図１０（Ｃ））。
【００８７】
15. 14の再帰的処理の中で、β={a,c,d}のうちaがitemとして選択され、α=b aとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b a対する指標Χ2(b a)=0.5は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b a)=1.6が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={c}とされる（図１０（Ｃ））。
【００８８】
16. 15の再帰的処理の中で、β={c}のうちcがitemとして選択され、α=b a cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b a cに対する指標Χ2(b a c)=0.3も限界値Χ2max(b a c)=0.5も閾値τK=1.3を越えず（ステップＳ１４２３，Ｓ１４２９）、β={c}のすべての要素が処理済であるため（ステップＳ１４３１）、15の再帰的処理が終了し、14の再帰的処理に戻る。14の再帰的処理ではβ={a,c,d}であるが、β={a,c,d}のうちaについては処理済みである。
【００８９】
17. 14の再帰的処理の中で、β={a,c,d}のうちcがitemとして選択され、α=b cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c対する指標Χ2(b c)=0.2は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b c)=2.3が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c}とされる（図１０（Ｃ））。
【００９０】
18. 17の再帰的処理の中で、β={a,c}のうちaがitemとして選択され、α=b c aとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c aに対する指標Χ2(b c a)=1.5が閾値τK=1.3を超えるため（ステップＳ１４２３）、出力リストLから[a c c, 1.3]が削除され、b c aと指標Χ2(b c a)=1.5との組[b c a, 1.5]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｈ））。
【００９１】
19. これ以上のプロジェクションが不可能なので、17の再帰的処理の中で、β={a,c}のうちcがitemとして選択され、α=b c cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c cに対する指標Χ2(b c c)=1.3が閾値τK=1.3も限界値Χ2max(b c c)=1.3も閾値τK=1.3を超えず（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、17の再帰的処理が終了し、14の再帰的処理に戻る。14の再帰的処理ではβ={a,c,d}であるが、β={a,c,d}のうちa,cについては処理済みである。
【００９２】
20. 14の再帰的処理の中で、β={a,c,d}のうちdがitemとして選択され、α=b dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b d対する指標Χ2(b d)=0.2も限界値Χ2max(b d)=0.5も閾値τK=1.3を超えず、（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、14の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,bについては処理済みである。
【００９３】
21. 最初のループ処理の中で、β={a,b,c,d}のうちcがitemとして選択され、α=cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=cに対する指標Χ2(ｃ)=0.2は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b)=3.1が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c}とされる（図１１（Ａ））。
【００９４】
22. 21の再帰的処理の中で、β={a,c}のうちaがitemとして選択され、α=c aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=c aに対する指標Χ2(c a)=1.5が閾値τK=1.3を超えるため（ステップＳ１４２３）、出力リストLから[a b c c, 1.3]が削除され、c aと指標Χ2(c a)=1.5との組[c a, 1.5]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｉ））。
【００９５】
23. これ以上のプロジェクションが不可能なので、21の再帰的処理の中で、β={a,c}のうちcがitemとして選択され、α=c cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=c cに対する指標Χ2(c c)=1.3が閾値τK=1.3も限界値Χ2max(c c)=1.3も閾値τK=1.3を超えず（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、21の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,b,cについては処理済みである。
【００９６】
24. 最初のループ処理の中で、β={a,b,c,d}のうちdがitemとして選択され、α=dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=dに対する指標Χ2(d)=2.1は閾値τK=1.3を越えるため（ステップＳ１４２３）、出力リストLから[a b c, 1.3]が削除され、dと指標Χ2(d)=2.1との組[d, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.5とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｊ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={a,b,c,d}とされる（図１１（Ｂ））。
【００９７】
25. 24の再帰的処理の中で、β={a,b,c,d}のうちaがitemとして選択され、α=d aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d aに対する指標Χ2(d a)=2.1が閾値τK=1.5を超えるため（ステップＳ１４２３）、出力リストLから[c a, 1.5]が削除され、d aと指標Χ2(d a)=2.1との組[d a, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.5とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｋ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={b,d}とされる（図１１（Ｂ））。
【００９８】
26. 25の再帰的処理の中で、β={b,d}のうちbがitemとして選択され、α=d a bとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d a bに対する指標Χ2(d a b)=0.2も限界値Χ2max(d a b)=0.5も閾値τK=1.5を越えない（ステップＳ１４２３，Ｓ１４２９）。
【００９９】
27. 次に、25の再帰的処理の中で、β={b,d}のうちdがitemとして選択され、α=d a dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d a dに対する指標Χ2(d a d)=0.2も限界値Χ2max(d a d)=0.5も閾値τK=1.5を越えず（ステップＳ１４２３，Ｓ１４２９）、β={b,d}のすべての要素が処理済であるため（ステップＳ１４３１）、25の再帰的処理が終了し、24の再帰的処理に戻る。24の再帰的処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちaについては処理済みである。
【０１００】
28. 24の再帰的処理の中で、β={a,b,c,d}のうちbがitemとして選択され、α=d bとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d bに対する指標Χ2(d b)=2.1が閾値τK=1.5を超えるため（ステップＳ１４２３）、出力リストLから[b c a, 1.5]が削除され、d bと指標Χ2(d b)=2.1との組[d b, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=2.1とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｌ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={a,c,d}とされる（図１１（Ｂ））。
【０１０１】
29. 28の再帰的処理の中で、β={a,c,d}のうちaがitemとして選択され、α=d b aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b aに対する指標Χ2(d b a)=1.5も限界値Χ2max(d b a)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０２】
30. 28の再帰的処理の中で、β={a,c,d}のうちcがitemとして選択され、α=d b cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b cに対する指標Χ2(d b c)=1.5も限界値Χ2max(d b a)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０３】
31. 28の再帰的処理の中で、β={a,c,d}のうちdがitemとして選択され、α=d b dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b dに対する指標Χ2(d b d)=0.5も限界値Χ2max(d b d)=0.2も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。28の再帰的処理のステップＳ１４３１の判定でyesとされるため、28の再帰的処理が終了し、24の再帰的処理に戻る。24の再帰的処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,bについては処理済みである。
【０１０４】
32. 24の再帰的処理の中で、β={a,b,c,d}のうちcがitemとして選択され、α=d cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d cに対する指標Χ2(d c)=1.5も限界値Χ2max(d c)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０５】
33. 24の再帰的処理の中で、β={a,b,c,d}のうちdがitemとして選択され、α=d dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d dに対する指標Χ2(d d)=0.2も限界値Χ2max(d d)=0.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。24の再帰的処理のステップＳ１４３１の判定でyesとされるため24の再帰的処理が終了し、最初のループ処理に戻る。
【０１０６】
34. 最初のループ処理のステップＳ１４３１の判定でyesとされるためステップＳ１４の処理が終了し、記憶部１６ｅに格納された出力リストLが出力される。
【０１０７】
〔変形例など〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の実施形態では、ステップＳ１３でラベルありデータと確率データ付きデータとを合成したデータベースを生成する際、確率データ付きデータが含む確率Pr(P+|x)，Pr(P-|x)に減衰パラメータλが乗じられた。しかし、減衰パラメータλが乗じられない構成であってもよい。また逆に、ラベルありデータのラベル値（1 or 2）に)に増幅パラメータρ（ρ≧1、好ましくはρ＞1）が乗じられてもよい。また、減衰パラメータλと増幅パラメータρの両方が乗じられてもよい。
【０１０８】
また、式(25)-(28)の代わりに以下の式(31)-(34)が用いられてもよい。
【０１０９】
N=ρ・|DL|+|DU| …(31)
【０１１０】
【数１１】
或いは、式(25)-(28)の代わりに以下の式(35)-(38)が用いられてもよい。
【０１１１】
N=ρ・|DL|+λ・|DU| …(35)
【０１１２】
【数１２】
すなわち、データベースが含むラベルありテキストの総数|DL|から定まる値が、当該総数|DL|と所定の増幅パラメータとの積であり、データベースが含むラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値が、当該ラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数と増幅パラメータとの積であり、データベースが含むラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち第１パターンαを含むものの総数から定まる値が、当該ラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち第１パターンαを含むものの総数と増幅パラメータとの積であり、第１パターンαを含むラベルありテキストの総数から定まる値が、当該第１パターンαを含むラベルありテキストの総数と増幅パラメータとの積であってもよい。
【０１１３】
また、上述の実施形態では、Χ2(α)そのものを指標として用いた。しかし、その他のΧ2(α)の広義単調関数値（単調非減少関数値）に相当する値を指標としてもよい。なお、Χ2(α)の広義単調関数値に相当する値は、Χ2(α)そのものをも含む概念である。例えば、Χ2(α)の広義単調増加関数値に相当する値を指標とするのであれば、指標の値が大きいパターンαほどラベル分類に寄与する度合いが大きいといえる。また、例えば、Χ2(α)の広義単調減少関数値に相当する値を指標とするのであれば、指標の値が小さいパターンαほどラベル分類に寄与する度合いが大きいといえる。その他、パターンαと、パターンαを含むテキストを当該テキストが属する集合に分類した際の分類結果との関連性の高さを表す凸関数値を指標としてもよい。
【０１１４】
同様に、上述の実施形態では、Χ2max(α)そのものを指標として用いた。しかし、その他のΧ2max(α)の広義単調関数値に相当する値を指標としてもよい。なお、Χ2max(α)の広義単調関数値に相当する値は、Χ2max(α)そのものをも含む概念である。
【０１１５】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１２１】
１ パターン抽出装置
１１ 訓練部
１２ 分類部
１３ データベース合成部
１４ 抽出部
１５ 制御部
１６ａ〜１６ｅ 記憶部
【技術分野】
【０００１】
本発明は、記号系列からなるデータの自動分類処理に寄与する系列のパターンを抽出するための技術に関する。
【背景技術】
【０００２】
記号系列からなるデータ（例えば、文字記号によって記述された文書データや、遺伝子記号によって記述された遺伝子配列など）群を自動分類する技術が存在する。例えば、スパムメールとその他の電子メールが混在する電子メール群を、スパムメールの集合とその他電子メールの集合とに分類する技術などである。このような技術では、或る特徴を持つ系列（記号系列）のパターンに基づいて、データの自動分類処理が行われる。例えば、所定の集合（例えば、スパムメールの集合）に属するデータが含む頻度が高い系列のパターンが用意され、分類対象のデータが当該系列のパターンを含むか否かに応じ、当該分類対象のデータが自動分類される。よって、このような自動分類技術では、その前提として、自動分類処理に寄与する系列のパターン（例えば、スパムメールの集合に属するデータが含む頻度が高い系列のパターン）を生成する必要がある。
【０００３】
一方、記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する技術が存在する（例えば、非特許文献１参照）。
【０００４】
図１は、記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する従来技術を説明するための図である。
【０００５】
以下では、１個以上の記号からなる要素（最小単位）をアイテムと呼び、１個以上のアイテムからなる系列をテキストと呼び、テキストが含む１個以上のアイテムからなる系列をパターンと呼び、テキストの集合をデータベースと呼ぶ。なお、記号の例は、文字、数字、マークなどであり、アイテムの例は、文字、数字、マーク、単語、単語列、塩基、塩基対などである。図１の例では、例えば、「a」〜「d」がアイテムであり、「a b c c」などの系列が1つのテキストであり、テキストが含む「a」「a b」「a c」などの系列がパターンである。また、図１の例では、５つのテキストからなるデータベースを扱う。
【０００６】
ここで、データベース中から、出現頻度がζ=2よりも大きいパターンを抽出することを考える。なお、１つのテキスト中に同じパターンが複数回出現したとしても、そのテキストに対するそのパターンのカウント回数は1回とする。
【０００７】
まず、与えられたデータベース（「入力データベース(IDB)」と呼ぶ）に対し、アイテム(長さ1のパターン)の出現頻度が算出される。図１の例の場合、アイテム「a」「b」「c」「d」の出現頻度は、それぞれ5, 4, 4, 2となる。すなわち、入力データベースにおいて、出現頻度がζ=2より大きいアイテムは「a」「b」「c」の３つである。これらの３つのアイテム「a」「b」「c」は出力リスト（OUT）の要素として記憶に格納され（OUT={a, b, c}）、その後、それぞれのパターン「a」「b」「c」から始まるパターンの出現頻度が算出される。「d」から始まるパターンの出現頻度がζ=2よりも大きくなることはないので、「d」から始まるパターンは以降の処理対象とされない。なお、この例では、プロジェクションによって生成されたデータベースを用い、入力データベースにおける、パターン「a」「b」「c」から始まるパターンの出現頻度が算出される。プロジェクションとは、データベース中の各エントリ（初期はテキスト）に対し、それぞれの先頭から或るアイテム（「着目アイテム」と呼ぶ）が最初に見つかった位置までを削除し、残りの系列をデータベースのエントリとして新たなデータベースを作成することを示す。なお、プロジェクションにおいて、着目アイテムを含まないエントリはデータベースから除外される。ここで説明するアイテムの出現頻度を算出する処理では、出現頻度がζ=2より大きいアイテム「a」「b」「c」が、それぞれ着目アイテムとされる。
【０００８】
まず、入力データベースに対し、「a」を着目アイテムとしてプロジェクション（prj(a)）を行うと、「b c c」、「c」、「c」、「b d」というエントリのデータベース(DB(a))が作成される。次にこのデータベース(DB(a))に対し、アイテム(長さ1のパターン)の出現頻度を求める。ここで、頻度がζ=2より大きいアイテムがあれば、そのアイテムの前にこれまでのプロジェクションの着目アイテムを付加した系列であるパターンが出力リスト（OUT）の要素として記憶に格納される。図１のプロジェクション（prj(a)）の例の場合、出現頻度がζ=2より大きいアイテムは「b」「c」の２つである。よって、各アイテム「b」「c」の前に、それぞれ、これまでのプロジェクションの着目アイテム「a」を付加した系列であるパターン「a b」「a c」が出力リスト（OUT）の要素として記憶に格納される（OUT={a, b, c, a b, a c}）。さらに、データベース（DB(a)）に対し、再度、プロジェクションが実行される。図１の例では、データベース(DB(a))に対し、頻度がζ=2より大きいアイテム「b」を着目アイテムとしたプロジェクション（prj(b)）が行われ、データベース(DB(a b))が生成される。データベース(DB(a b))には、頻度がζ=2より大きいアイテムが存在しないため、出力リスト（OUT）に新たな要素が加えられない。次に、データベース(DB(a))に戻り、頻度がζ=2より大きいアイテム「c」を着目アイテムとしたプロジェクション（prj(c)）が行われ、データベース(DB(a c))が生成される。データベース(DB(a c))には、頻度がζ=2より大きいアイテムが存在しないため、出力リスト（OUT）に新たな要素が加えられない。次に、入力データベース(IDB)に戻り、「b」を着目アイテムとしたプロジェクション（prj(b)）が行われ、データベース(DB(b))が生成され、「b a」「b c」が出力リスト（OUT）の要素として記憶に格納される（OUT={a, b, c, a b, a c, b a, b c}）。その後、同様な基準に従い、深さ優先順で、データベース(DB(b))に対するアイテム「a」「c」を着目アイテムとしたプロジェクション、入力データベース(IDB)に対するアイテム「c」を着目アイテムとしたプロジェクションが実行され、処理が終了する。このようにプロジェクションを再帰的に行うことにより、出現頻度が或る値ζより大きいパターンを効率的に求めることができる。図１の例では、出現頻度がζ=2よりも大きいパターンとして「a, b, c, a b, a c, b a, b c」が得られる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】J. Pei, J. Han, B.Mortazavi-Asl, H.Pinto, Q.Chen, U.Dayal, and M.-C. Hsu 2001. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth In Proc. of the 17th ICDE, pages 215-224.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、非特許文献１にあるような従来技術では、データベースから出現頻度の高いパターンを自動抽出することはできても、自動分類処理に寄与するパターンを自動生成することはできない。例えば、データベースに属する各テキストにテキストが属する集合を表すデータであるラベル（例えば、スパムメールであるか否かを表すラベルなど）が付与されていたとしても、非特許文献１にあるような従来技術では、ラベルを考慮したパターン抽出を行うことはできない。
【００１１】
また、ラベルが対応付けられた（ラベルが付与された）テキストをラベルが示す集合ごとに分類し（例えば、スパムメールであるか否かに分類し）、分類された集合ごとに非特許文献１にあるような従来技術を適用すれば、集合ごとに別個に、出現頻度が高いパターンを抽出することができる。このようにして抽出されるパターンは、自動分類処理に寄与するパターンである。しかしながら、通常、テキストにラベルを対応付ける処理は人手によって行われ、そのコストは高い。よって、ラベルが対応付けられたテキストを大量に用意することは難しい。さらに、少量のテキストからパターン抽出が行われた場合には抽出されるパターンの数が非常に少なくなり、抽出されたパターンを用いた自動分類処理の性能が低下してしまう。
【００１２】
本発明はこのような点に鑑みてなされたものであり、ラベルが付与されたテキストの数が少量であったとしても、自動分類処理に寄与するパターンを必要な数だけ自動生成することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、１個以上の記号からなる要素をアイテムとし、１個以上のアイテムからなる系列をテキストとし、テキストが含む１個以上のアイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられたテキストをラベルありテキストとし、ラベルに対応付けられていないテキストをラベルなしテキストとし、ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものを分類モデルとする。分類モデルは、ラベルなしテキストに適用され、当該ラベルなしテキストが所定の集合に属する確率を表す確率データが生成される。そして、少なくとも、生成された確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標が生成される。
【発明の効果】
【００１４】
本発明で生成される指標を用いることで、テキストの自動分類処理に寄与する度合いの高いパターンを自動生成できる。また、当該指標はラベルなしテキストに分類モデルを適用した結果を用いて生成できる。よって、本発明では、ラベルが付与されたテキストの数が少量であったとしても、自動分類処理に寄与するパターンを必要な数だけ自動生成することができる。
【図面の簡単な説明】
【００１５】
【図１】記号系列からなるデータ群から頻度の高い系列のパターンを自動抽出する従来技術を説明するための図。
【図２】実施形態のパターン抽出装置の機能構成を説明するためのブロック図。
【図３】パターン抽出装置の処理を説明するための図。
【図４】パターン抽出装置の処理を説明するための図。
【図５】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図６】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図７】ステップＳ１４の処理の具体例を説明するためのフローチャート。
【図８】ステップＳ１４の処理の具体例を説明するための擬似コード。
【図９】ステップＳ１４の実施例を説明するための図。
【図１０】ステップＳ１４の実施例を説明するための図。
【図１１】ステップＳ１４の実施例を説明するための図。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
＜機能構成＞
図２は、実施形態のパターン抽出装置１の機能構成を説明するためのブロック図である。
【００１８】
図２に例示するように、本形態のパターン抽出装置１は、訓練部１１と、分類部１２と、データベース合成部１３と、抽出部１４と、制御部１５と、記憶部１６ａ〜１６ｅとを有する。抽出部１４は、指標生成部１４ａと、限界値生成部１４ｂと、探索部１４ｃとを有する。なお、本形態のパターン抽出装置１は、例えば、CPU(central processing unit)、RAM(random-access memory)、ROM(read-only memory)などを有する公知のコンピュータ又は専用コンピュータに、所定のプログラムが読込まれて構成される特別な装置である。すなわち、訓練部１１、分類部１２、データベース合成部１３、抽出部１４及び制御部１５は、例えば、所定のプログラムを実行するCPUである。また、記憶部１６ａ〜１６ｅは、例えば、ハードディスク装置などの補助記憶装置、RAM、レジスタ、若しくは、キャッシュメモリ、又は、これらの少なくとも一部が結合された記憶領域である。また、訓練部１１、分類部１２、データベース合成部１３、抽出部１４及び制御部１５の少なくとも一部の機能が集積回路によって構成されてもよいし、記憶部１６ａ〜１６ｅの少なくとも一部の記憶領域が集積回路内に存在してもよい。なお、パターン抽出装置１は、制御部１５の制御のもと、各処理を実行する。また、以下では一部で説明を省略するが、各演算において生成されたデータは各記憶部に格納され、必要に応じてそこから読み出されて各演算に用いられる。
【００１９】
＜処理＞
図３、４は、パターン抽出装置１の処理を説明するための図である。以下、これらの図を用いてパターン抽出装置１の処理を説明する。
【００２０】
［事前処理］
事前処理として、ラベルありテキストを含むラベルありデータとラベルなしテキストを含むラベルなしデータとが、それぞれ、１個以上、記憶部１６ａ（図２）に格納される。ラベルありテキスト及びラベルなしテキストの例は、文字記号によって記述された文書データや、遺伝子記号によって記述された遺伝子配列や、プログラムコードによって記述されたプログラム列などである。また、ラベルありテキストは、事前に人間によって、それぞれのテキストが属する集合を表すデータであるラベルが対応付けられたテキストである。なお、集合の数は２以上であればいくつでもよいが、以下では２個の集合が設定され、一方の集合を「P+（正例：+）」とし、他方の集合を「P-（負例：-）」とする。図４の例では、識別子(ID)とテキスト（ラベルありテキスト）とラベルの内容(P+,P-)(ラベルが集合P+を表すなら(P+,P-)=(1,0)、ラベルが集合P-を表すなら(P+,P-)=(0,1)）との組が、ラベルありデータとされる。また、識別子(ID)とテキスト（ラベルなしテキスト）とラベルの内容(P+,P-)が不明であることを示す情報（(P+,P-)=(unk,unk)）との組が、ラベルなしデータとされる。
【００２１】
また、予め定められた減衰パラメータλと、出力リストの要素の上限値を表すパラメータKとが、記憶部１６ｅに格納される。なお、減衰パラメータλは、例えば、0≦λ≦1の範囲、好ましくは、0＜λ＜1の範囲から事前に選択された値である。また、パラメータKは、例えば、事前に選択された正整数である。
【００２２】
［パターン抽出処理］
まず、訓練部１１が、記憶部１６ａから、ラベルありデータが含むラベルありテキストを抽出し、当該ラベルありテキストを訓練データとして用い、適用された任意のテキストが所定の集合（クラス）に属する確率を表す確率データを出力するように構成された統計モデルである分類モデルを生成する。生成された分類モデルは記憶部１６ｂに格納される（ステップＳ１１）。なお、分類モデルは、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成されたものであればどのようなものでもよい。例えば、ナイーブ・ベイズ法や最大エントロピー法などの周知の統計方法におけるモデルを分類モデルとすればよい。以下に、ナイーブ・ベイズ法を用いる場合の分類モデルを例示する。
【００２３】
［ステップＳ１１の具体例（ナイーブ・ベイズ法の例）］
ナイーブ・ベイズ法では、テキストxが所定の集合（クラス）cに属する確率Pr(c|x)が以下の式で定義される。
【００２４】
【数１】
ここで、wiはテキストxのi番目のアイテムを表し、N(wi,x)は、テキストxにおけるアイテムwiの出現頻度を表す。Pr(c)は、テキストxが集合cに属することの生起確率を表し、以下の式で定義される。
【００２５】
【数２】
また、Pr(wi|c)は以下の式で定義される。
【００２６】
【数３】
ナイーブ・ベイズ法における分類モデルは、訓練データであるラベルありテキストを用いて算出（学習）された式(2)(3)の値となる。以下にナイーブ・ベイズ法において学習される分類モデルを例示する。
【００２７】
この例では、以下の１０個のラベルありテキストを訓練データとして用い、適用された任意のテキストxが集合P+に属する確率を表す確率データを出力するように構成された分類モデルを生成する。
【００２８】
【表１】
この場合、訓練データであるラベルありテキストがラベルP+で表される集合c=P+に属する生起確率Pr(P+)、及び、訓練データであるラベルありテキストがラベルP-で表される集合c=P-に属する生起確率Pr(P-)は以下のようになる。
【００２９】
Pr(P+)=7/10 …(4)
Pr(P-)=3/10 …(5)
また、各単語wi=a〜iについてのPr(wi|P+)は以下のようになる。
【００３０】
【数４】
また、各単語wi=a〜iについてのPr(wi|P-)は以下のようになる。
【００３１】
【数５】
この例では、式(1)から定まるPr(P+|x)と式(4)〜(23)とが分類モデルとなる（［ステップＳ１１の具体例（ナイーブ・ベイズ法の例）］の説明終わり）。なお、ステップＳ１１の処理は、必ずしもパターン抽出処理が行われるたびに実行される必要はなく、過去に生成された分類モデルを使用できるのであれば、ステップＳ１１の処理が省略されてもよい。
【００３２】
次に、分類部１２に、上述のラベルなしテキストと分類モデルとが入力される。分類部１２は、分類モデルをラベルなしテキストに適用し、当該ラベルなしテキストが所定の集合に属する確率を表す確率データを生成する（ステップＳ１２）。この処理の具体的な方法は分類モデルに応じて異なる。例えば、前述したナイーブ・ベイズ法おける分類モデルが用いられる場合には、以下のような確率データが生成される。
【００３３】
［ステップＳ１２の具体例（ナイーブ・ベイズ法の例）］
前述したナイーブ・ベイズ法おける分類モデルが用いられる場合、式(1)に従って、入力されたラベルなしテキストxが所定の集合cに属する確率Pr(c|x)が算出される。例えば、式(1)から定まるPr(P+|x)と式(4)〜(23)とからなる分類モデルに、ラベルなしテキストx=a a c c d d fが適用される場合、当該ラベルなしテキストx=a a c c d d fが、ラベルP+で表される所定の集合に属する確率Pr(P+|x)は、
【００３４】
【数６】
となる（［ステップＳ１２の具体例（ナイーブ・ベイズ法の例）］の説明終わり）。
【００３５】
以上のように生成された確率Pr(P+|x)は、対応するラベルなしテキストに対応付けられ、確率データ付きデータとして記憶部１６ｃに格納される。例えば、図４の例では、識別子(ID)とテキスト（ラベルなしテキスト）と確率Pr(P+|x)と確率Pr(P-|x)=1-Pr(P+|x)とが互いに対応付けられた確率データ付きデータが、記憶部１６ｃに格納される。
【００３６】
次に、データベース合成部１３（図２）に、記憶部１６ａに格納されたラベルありデータと、記憶部１６ｃに格納された確率データ付きデータと、記憶部１６ｅに格納された減衰パラメータλとが入力される。データベース合成部１３は、ラベルありデータと確率データ付きデータとを合成したデータベースを生成する（ステップＳ１３）。この際、確率データ付きデータの含む確率Pr(P+|x)，Pr(P-|x)が分類モデルを用いて自動的に生成されたものであることを考慮し、確率データ付きデータが含む確率Pr(P+|x)，Pr(P-|x)に減衰パラメータλが乗じられる。図４の例では、減衰パラメータλ=0.5とし、データベースが生成されている。生成されたデータベースは記憶部１６ｄに格納される。
【００３７】
次に、抽出部１４が、記憶部１６ｄに格納されたデータベースと、記憶部１６ｅに格納されたパラメータK及び減衰パラメータλとを入力とし、テキストのラベル分類に寄与する度合い（テキストの自動分類処理に寄与する度合い）の高い、K個のパターンを抽出し、それらを要素とする出力リストを出力する（ステップＳ１４）。以下に、ステップＳ１４の処理の詳細を説明する。
【００３８】
［指標］
従来の手法では、パターンの出現頻度に基づき、或るデータベースに含まれるパターンを抽出するか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが、決定されていた。これに対し、本形態では、パターンの出現頻度ではなく、パターンがラベル分類に寄与する度合い（すなわち、パターンと、当該パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さ）を表す指標に基づき、或るデータベースに含まれるパターンを抽出するか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００３９】
この指標は、抽出部１４の指標生成部１４ａが、少なくとも、分類部１２で生成された確率データから定まる値を用いて生成する。以下に、指標生成部１４ａが生成する指標の一例を示す。
【００４０】
この例では、以下のような分割表を考える。
【００４１】
【表２】
ここで、記憶部１６ｄに格納されたデータベースは、|DL|個（|DL|≧0）のラベルありテキストと、分類部１２で確率データがそれぞれ生成された|DU|個（|DU|＞0）のラベルなしテキストとを含むものとする。この例では|DL|≧1とする。なお、|DL|はデータベースが含むラベルありテキストの総数を表し、|DU|はデータベースが含むラベルなしテキストの総数を表す。また、DLはラベルありテキストの集合を表し、DUはラベルなしテキストの集合を表す。
【００４２】
Nはデータベースが含むラベルありテキストの総数|DL|から定まる値と、データベースが含むラベルなしテキストの総数|DU|から定まる値との和である。この例では、以下のように、データベースが含むラベルありテキストの総数|DL|と、データベースが含むラベルなしテキストの総数DUから定まる値と減衰パラメータλとの積との和をNとする。
【００４３】
N=|DL|+λ・|DU| …(25)
Mは、データベースが含むラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値と、分類部１２で生成されたラベルありテキストが集合P+に属する確率を表す確率データから定まる値の総数との和である。この例では、以下のように、データベースが含むラベルありテキストのうち所定の集合P+に属することを表すラベルに対応付けられたものの総数と、ラベルありテキストが集合P+に属する確率と減衰パラメータλとの積の総数との和をMとする。
【００４４】
【数７】
なお、diはテキストを表し、I(di)はラベルありテキストdi∈DLが集合P+に属するときに1となり、それ以外のときに0となる関数を表す。また、Pr(P+|dj)(dj∈DU)は、ラベルなしテキストdj∈DUが集合P+に属する確率を表す。
【００４５】
y(α)は、データベースが含むラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうちパターンαを含むものの総数から定まる値と、パターンαを含むラベルなしテキストが所定の集合に属する確率を表す確率データから定まる値の総数との和を表す。この例では、以下のように、データベースが含むラベルありテキストであって集合P+に属することを表すラベルに対応付けられたラベルありテキストのうちパターンαを含むものの総数と、パターンαを含むラベルなしテキストが集合P+に属する確率と減衰パラメータλとの積の総数との和をy(α)とする。
【００４６】
【数８】
なお、F(di,α)は、テキストdiがパターンαを含むときに1となり、それ以外のときに0となる関数である。
【００４７】
x(α)は、パターンαを含むラベルありテキストの総数から定まる値と、パターンαを含むラベルなしテキストの総数から定まる値との和を表す。この例では、以下のように、パターンαを含むラベルありテキストの総数と、パターンαを含むラベルなしテキストの総数と減衰パラメータλとの積との和をx(α)とする。
【００４８】
【数９】
このとき、パターンαと、当該パターンαを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標として、以下のΧ2(α)を用いる。
【００４９】
【数１０】
この例の場合、指標生成部１４ａは、記憶部１６ｄに格納されたデータベースと、記憶部１６ｅに格納された減衰パラメータλとを入力とし、式(29)にしたがって指標Χ2(α)を生成する。パターンαに対する指標Χ2(α)は記憶部１６ｅに格納される。
【００５０】
抽出部１４は、上記の指標に基づき、ラベル分類に寄与する度合いの高い順に選択したK個のパターンを、出力リストLの要素として出力する。本形態の例では、各パターンに対して上記の指標を順次生成していき、K個以上のパターンにそれぞれ対応する指標が生成された場合に、ラベル分類に寄与する度合いが高い順に数えてK番目の指標を閾値τKとする。そして、その後生成される各指標が当該閾値τKに基づく出力条件を満たすか否かに応じ、その指標に対応するパターンを出力リストLの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。例えば、式(29)の指標Χ2(α)を用いる場合には、K個以上のパターンにそれぞれ対応する指標が生成された場合に、それらのうちでK番目に大きい指標を閾値τKとする。そして、その後生成される各指標が閾値τKを超えるという出力条件を満たすか否かに応じ、その指標に対応するパターンを出力リストLの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００５１】
［指標の限界値］
ただし、或るパターンαに対応する指標が出力条件を満たさない場合であっても、当該パターンαに１個以上のアイテムが付加された新たなパターンに対応する指標が出力条件を満たす場合がある。すなわち、指標が出力条件を満たさない場合であっても、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行った場合、出力条件を満たすパターンが検出される場合がある。
【００５２】
そのため、本形態では、抽出部１４の限界値生成部１４ｂが、或るパターンαに１個以上のアイテムが付加された任意の系列である任意パターンと、当該任意パターンを含む任意のテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標の限界値を生成する。当該限界値は、パターンαに１個以上のアイテムが付加された任意パターンに対応する指標の最良値（最もラベル分類に寄与する度合いが高い値）を表すものである。例えば、式(29)の指標Χ2(α)が用いられる場合には、パターンαに対して以下の限界値Χ2max(α)が生成される。なお、Χ2(α, y=x)はy=xである場合のΧ2(α)を表し、Χ2(α,y=0)はy=0である場合のΧ2(α)を表し、max(ν, μ)は、ν≧μの場合にνとなり、ν＜μの場合にμとなる関数を表す。
【００５３】
Χ2max(α)=max(Χ2(α, y=x), Χ2(α,y=0)) …(30)
そして、限界値が所定の探索条件を満たすか否かに応じて、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かが決定される。
【００５４】
［探索処理］
抽出部１４の探索部１４ｃは、判定対象のパターンに対して生成された上記の指標と限界値とを用い、判定対象のパターンを出力リストの要素とするか否か、及び、プロジェクションを行って新たなデータベースを生成して再帰的な処理を行うか否かを決定する。
【００５５】
(I)すなわち、第１パターンαに対して生成された指標が所定の第１出力条件（例えば、Χ2(α)＞τK）を満たす場合、探索部１４ｃが、第１パターンαを出力リストの要素として出力するとともに、指標生成部１４ａが、当該第１パターンαに１個以上のアイテムが付加された系列である第２パターンと、当該第２パターンを含む第２テキストを当該第２テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第２指標を生成する。そして、その後の再帰的な処理により、当該第２指標が所定の第２出力条件を満たしたのであれば、当該第２パターンが出力リストの要素として出力される。
【００５６】
(II)また、限界値生成部１４ｂが、第１パターンαに対応する指標が第１出力条件を満たさないが限界値が所定の探索条件を満たすときには（例えば、Χ2(α)≦τKかつΧ2max(α)＞τK）、探索部１４ｃが、当該第１パターンαを出力リストの要素として出力することなく、指標生成部１４ａが、当該第１パターンαに１個以上のアイテムが付加された系列である第３パターンと、当該第３パターンを含む第３テキストを当該第３テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第３指標を生成する。そして、その後の再帰的な処理により、当該第３指標が所定の第３出力条件を満たしたのであれば、当該第３パターンが出力リストの要素として出力される。
【００５７】
(III)また、第１パターンαに対応する指標が第１出力条件を満たさず、限界値も所定の探索条件を満たさないときには（例えば、Χ2(α)≦τKかつΧ2max(α)≦τK）、当該第１パターンαが出力リストの要素とされず、かつ、上記の第３指標も生成されない。
【００５８】
これらの抽出部１４の処理を、式(29)の指標Χ2(α)と式(30)の限界値Χ2max(α)とを用いる場合に限定して言い換えると以下のようになる。
【００５９】
(I)Χ2(α)＞τKなら、パターンαを出力リストの要素として出力するとともに、プロジェクションを行って、パターンαに１個以上のアイテムが付加された系列を新たなパターンαとし、再帰的な処理を行う。
【００６０】
(II)Χ2(α)≦τKかつΧ2max(α)＞τKなら、パターンαを出力リストの要素とすることなくプロジェクションを行って、パターンαに１個以上のアイテムが付加された系列を新たなパターンαとし、再帰的な処理を行う。
【００６１】
(III)Χ2(α)≦τKかつΧ2max(α)≦τKなら、パターンαを出力リストの要素とせず、プロジェクションも行わず、パターンαに１個以上のアイテムが付加された系列に対する処理を行わない。
【００６２】
［ステップＳ１４の処理の具体例］
図５から図７は、ステップＳ１４の処理の具体例を説明するためのフローチャートである。図８は、ステップＳ１４の処理の具体例を説明するための擬似コードである。以下、これらの図を用いて、ステップＳ１４の処理の具体例を説明する。
【００６３】
まず、抽出部１４の探索部１４ｃが、パターンαを空に設定し（α=[ ]）、Rを記憶部１６ｄに格納されたデータベースとし、閾値τK=nan（未定であることを表す値）とする（ステップＳ１４０１）。これらの値は記憶部１６ｅに格納される。
【００６４】
次に、探索部１４ｃが、Rが空集合（R={ }）であるか否かを判定する（ステップＳ１４０２）。ここで、R={ }であれば処理が終了する。一方、R={ }でなければ、探索部１４ｃが、RRを空集合（RR←{ }）に設定し（ステップＳ１４０３）、αが空であるか（α=[ ]）否かを判定する（ステップＳ１４０４）。
【００６５】
ここでαが空であると判定された場合、探索部１４ｃは、RRをRに設定し（RR←R）（ステップＳ１４０５）、Rが含むアイテムの集合をβ（β←itemset(R)）として設定し（ステップＳ１４０６）、後述のステップＳ１４１５の処理が実行される。
【００６６】
一方、αが空でないと判定された場合、Rが含むアイテムからなる系列のエントリtrans(trans∈R)を選択する（ステップＳ１４０８）。なお、プロジェクションが１度も実行されておらず、Rが記憶部１６ｄに格納されたデータベースである場合、記憶部１６ｄに格納されたデータベースが含むテキストがエントリtransに相当する。また、過去にプロジェクションが実行されている場合、テキストからそれまでのプロジェクションによって削除されたアイテムを除いた残りの系列がエントリtransに相当する。次に、探索部１４ｃは、選択したエントリtransに対し、その先頭からアイテムαが最初に見つかった位置までを削除し、残りの系列をsubseqとして設定する処理（subseq ← postseq(last(α), trans)）を実行する（ステップＳ１４０９）。次に、探索部１４ｃは、subseqが空でないか（subseq≠[ ]）否かを判定する（ステップＳ１４１０）。ここで、subseqが空でないならば、探索部１４ｃは、RRにsubseqをエントリとして追加したものを新たなRR（RR←append(RR, subseq)）として設定し（ステップＳ１４１１）、ステップＳ１４１２の処理を実行する。一方、subseqが空であるならば、探索部１４ｃは、ステップＳ１４１１の処理を実行することなく、ステップＳ１４１２の処理を実行する。ステップＳ１４１２の処理では、探索部１４ｃが、すべてのエントリtrans∈Rについて処理が終了したか否かを判定する（ステップＳ１４１２）。ここで、すべてのエントリtrans∈Rについて処理が終了していないと判定されたのであれば、処理がステップＳ１４０８に戻される。一方、すべてのエントリtrans∈Rについて処理が終了したと判定されたのであれば、探索部１４ｃは、RRが含むアイテムの集合をβ（β←itemset(RR)）として設定し（ステップＳ１４１３）、ステップＳ１４１５の処理が実行される。なお、ステップＳ１４０８からＳ１４１３までの処理がプロジェクションに相当する。
【００６７】
ステップＳ１４１５の処理では、探索部１４ｃがβに属するアイテム（item∈β）を選択する（ステップＳ１４１５）。次に、探索部１４ｃが、αの最後にステップＳ１４１５で選択されたアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）として生成する（ステップＳ１４１６）。次に、探索部１４ｃが出力リストLに属するパターンの要素数|L|が、記憶部１６ｅに格納されたパラメータK未満であるか（|L|<K）否かを判定する（ステップＳ１４１７）。ここで、|L|<Kであると判定された場合、指標生成部１４ａが、パターンαに対する指標Χ2(α)を式(29)にしたがって生成し、探索部１４ｃが、パターンαと指標Χ2(α)との組[α, Χ2(α)]を出力リストLの要素として加え、出力リストLを更新する。更新された出力リストL（L←append(L, [α, Χ2(α)])）は記憶部１６ｅに格納される（ステップＳ１４１８）。次に、探索部１４ｃが、出力リストLに属するパターンの要素数|L|が、記憶部１６ｅに格納されたパラメータKと同値であるか（|L|=K）否かを判定する（ステップＳ１４１９）。|L|=Kでないと判定された場合、後述するステップＳ１４２２の処理が実行される。一方、|L|=Kであると判定された場合、探索部１４ｃが、出力リストLの要素[α, Χ2(α)]を指標Χ2(α)が大きい順に並び替えたものを新たな出力リストL（L=sort(L)）とし、記憶部１６ｅに格納する（ステップＳ１４２０）。次に、探索部１４ｃが、出力リストLのK番目の要素の指標（最も小さな値の指標）を閾値τK（τK=Χ2(L[K])）とし、閾値τKを更新して記憶部１６ｅに格納し（ステップＳ１４２１）、次のステップＳ１４２２の処理が実行される。
【００６８】
ステップＳ１４２２の処理では、抽出部１４が、現在の（α，RR, K）に対し、ステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４２２）。その後、後述するステップＳ１４３１の処理が実行される。
【００６９】
一方、ステップＳ１４１８で、|L|<Kでないと判定された場合、指標生成部１４ａが、パターンαに対する指標Χ2(α)を式(29)にしたがって生成して記憶部１６ｅに格納し、探索部１４ｃが、記憶部１６ｅに格納された閾値τKを用い、Χ2(α)＞τKを満たすか否かを判定する（ステップＳ１４２３）。なお、閾値が未定である場合（τK=nan）には、Χ2(α)＞τKを満たさないものとする。ここで、Χ2(α)＞τKを満たすと判定された場合には、探索部１４ｃが、記憶部１６ｅに格納された出力リストLの最後の要素（最も指標Χ2(α)の値が小さな要素）を削除し、残りの要素からなる新たな出力リストL（L=lastdel(L)）を生成し、記憶部１６ｅに格納する（ステップＳ１４２４）。次に、探索部１４ｃが、パターンαと指標Χ2(α)との組[α, Χ2(α)]を出力リストLの要素として加え、出力リストLを更新する。更新された出力リストL（L←append(L, [α, Χ2(α)])）を記憶部１６ｅに格納される（ステップＳ１４２５）。次に、探索部１４ｃが、この出力リストLの要素[α, Χ2(α)]を指標Χ2(α)が大きい順に並び替えたものを新たな出力リストL（L=sort(L)）とし、記憶部１６ｅに格納する（ステップＳ１４２６）。次に、探索部１４ｃが、出力リストLのK番目の要素の指標（最も小さな値の指標）を閾値τK（τK=Χ2(L[K])）とし、閾値τKを更新して記憶部１６ｅに格納する（ステップＳ１４２７）。次に、抽出部１４が、現在の（α，RR, K）に対し、ステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４２８）。その後、後述するステップＳ１４３１の処理が実行される。
【００７０】
一方、ステップＳ１４２３の判定で、Χ2(α)＞τKを満たさないと判定された場合には、限界値生成部１４ｂが、パターンαに対する限界値Χ2max(α)を式(30)に従って生成して記憶部１６ｅに格納し、探索部１４ｃが、記憶部１６ｅに格納された閾値τKを用い、Χ2max(α)＞τKを満たすか否かを判定する（ステップＳ１４２９）。ここで、Χ2max(α)＞τKを満たすと判定された場合、抽出部１４が、現在の（α，RR, K）に対してステップＳ１４０２からＳ１４３１までの処理（call WTPS（α，RR, K））を再帰的に実行する（ステップＳ１４３０）。その後、以下のステップＳ１４３１の処理が実行される。一方、Χ2max(α)＞τKを満たさないと判定された場合、ステップＳ１４３０の処理が実行されることなく、ステップＳ１４３１の処理が実行される。
【００７１】
ステップＳ１４３１の処理では、探索部１４ｃが、すべてのアイテムitem∈βについて処理が終了したか否かを判定する（ステップＳ１４３１）。ここで、すべてのアイテムitem∈βについて処理が終了していれば、ステップＳ１４の処理が終了となる。一方、すべてのアイテムitem∈βについて処理が終了していなければ、処理がステップＳ１４１５に戻される。
【００７２】
［ステップＳ１４の実施例］
図９から図１１は、ステップＳ１４の実施例を説明するための図である。以下に、これらの図を用いながら、ステップＳ１４の実施例を説明する。なお、この実施例では、記憶部１６ｄに格納される初期のデータベースとして図３のデータベース（減衰パラメータλ=0.5が乗じられたもの）を用いる。また、K=4, λ=0.5とする。また、M=1.8, N=3.5であり、これらは初期のデータベースにおける定数である。また、図１０及び図１１に示す木構造の各ノードのアイテムa,b,c,dの右上添字は、その木のルートのアイテムからノードのアイテムまでの系列からなるパターンαの指標Χ2(α)であり、右下添字はそのパターンαの限界値Χ2max(α)を表す。また、図１０及び図１１に示すxは、パターンαの最後にβの要素であるアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）とし、当該新たなパターンαについて、式(28)にしたがって生成されたx(α)を表す。また、図１０及び図１１に示すyは、パターンαの最後にβの要素であるアイテムitemを付加した系列を新たなパターンα（α←append(α,[item])）とし、当該新たなパターンαについて、式(27)にしたがって生成されたy(α)を表す。
【００７３】
1. まず、α=[ ], RR←R, β={a,b,c,d}とされる（ステップＳ１４０１〜Ｓ１４０６／図１０（Ａ））。
【００７４】
2. 次に、α=aとされる（ステップＳ１４１５，Ｓ１４１６）。|L|<K(k=4)であるから、aと指標Χ2(a)=0との組[a, 0]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ａ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理（call WTPS（α，RR, K）／ステップＳ１４０２〜Ｓ１４３１）の中でβ={b,c,d}とされる（図１０（Ｂ））。
【００７５】
3. 2の再帰的処理の中で、α=a bとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a bと指標Χ2(a b)=0.5との組[a b, 0.5]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ｂ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理の中でβ={c,d}とされる（図１０（Ｂ））。
【００７６】
4. 3の再帰的処理の中で、β={c, d}のうちcがitemとして選択され、α=a b cとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a b cと指標Χ2(a b c)=1.3との組[a b c, 1.3]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８／図９（Ｃ））。なお、この時点では閾値τK=nanである。さらに、プロジェクションが行われ（ステップＳ１４２２）、その再帰的処理の中でβ={c}とされる（図１０（Ｂ））。
【００７７】
5. 4の再帰的処理の中で、α=a b c cとされる（ステップＳ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)であるから、a b c cと指標Χ2(a b c c)=1.3との組[a b c c, 1.3]が出力リストLの要素に追加される（ステップＳ１４１７，Ｓ１４１８）。
【００７８】
6. 4の再帰的処理の中で、|L|=K(k=4)となったため、出力リストLの要素を指標Χ2(α)に基づいて並び替え、閾値τK=0が得られる（ステップＳ１４１９〜Ｓ１４２１／図９（Ｄ））。
【００７９】
7. これ以上のプロジェクションが不可能なので（4の再帰的処理のステップＳ１４３１でyesとなるので）4の再帰的処理が終了し、3の再帰的処理に戻る。ここでは、α=a b, β={c, d}であるが、β={c, d}のうちcについては処理済みである。
【００８０】
8. 3の再帰的処理の中で、β={c, d}のうちdがitemとして選択され、α=a b dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a b dに対する指標Χ2(a b d)=0.2が閾値τK=0を超えるため（ステップＳ１４２３）、出力リストLから[a, 0]が削除され、a b dと指標Χ2(a b d)=0.2との組[a b d, 0.2]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=0.2に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｅ））。
【００８１】
9. これ以上のプロジェクションが不可能なので（3の再帰的処理のステップＳ１４３１でyesとなるので）、3の再帰的処理が終了し、2の再帰的処理に戻る。ここでは、α=a, β={b, c, d}であるが、β={b, c, d}のうちbについては処理済みである（図１０（Ｂ））。
【００８２】
10. 2の再帰的処理の中で、β={b, c, d}のうちcがitemとして選択され、α=a cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a cに対する指標Χ2(a c)=2.1が閾値τK=0.2を超えるため（ステップＳ１４２３）、出力リストLから[a b d, 0.2]が削除され、a cと指標Χ2(a c)=2.1との組[a c, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=0.5に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｆ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={c}とされる（図１０（Ｂ））。
【００８３】
11. 10の再帰的処理の中で、β={c}のうちcがitemとして選択され、α=a c cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a c cに対する指標Χ2(a c c)=1.3が閾値τK=0.5を超えるため（ステップＳ１４２３）、出力リストLから[a b, 0.5]が削除され、a c cと指標Χ2(a c c)=1.3との組[a c, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3に更新される（ステップＳ１４２４〜Ｓ１４２７／図９（Ｇ））。
【００８４】
12. これ以上のプロジェクションが不可能なので（10の再帰的処理のステップＳ１４３１でyesとなるので）、10の再帰的処理が終了し、2の再帰的処理に戻る。ここでは、α=a, β={b, c, d}であるが、β={b, c, d}のうちb, cについては処理済みである（図１０（Ｂ））。
【００８５】
13. 2の再帰的処理の中で、β={b, c, d}のうちdがitemとして選択され、α=a dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=a dに対する指標Χ2(a d)=0.2も限界値Χ2max(a d)=0.5も閾値τK=1.3を越えず（ステップＳ１４２３，Ｓ１４２９）、β={b, c, d}のすべての要素が処理済であるため（ステップＳ１４３１）、2の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、α=[ ], β={a,b,c,d}であるが、β={a,b,c,d}のうちaについては処理済みである。
【００８６】
14. 最初のループ処理の中で、β={a,b,c,d}のうちbがitemとして選択され、α=bとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=bに対する指標Χ2(b)=0は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b)=2.7が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c,d}とされる（図１０（Ｃ））。
【００８７】
15. 14の再帰的処理の中で、β={a,c,d}のうちaがitemとして選択され、α=b aとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b a対する指標Χ2(b a)=0.5は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b a)=1.6が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={c}とされる（図１０（Ｃ））。
【００８８】
16. 15の再帰的処理の中で、β={c}のうちcがitemとして選択され、α=b a cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b a cに対する指標Χ2(b a c)=0.3も限界値Χ2max(b a c)=0.5も閾値τK=1.3を越えず（ステップＳ１４２３，Ｓ１４２９）、β={c}のすべての要素が処理済であるため（ステップＳ１４３１）、15の再帰的処理が終了し、14の再帰的処理に戻る。14の再帰的処理ではβ={a,c,d}であるが、β={a,c,d}のうちaについては処理済みである。
【００８９】
17. 14の再帰的処理の中で、β={a,c,d}のうちcがitemとして選択され、α=b cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c対する指標Χ2(b c)=0.2は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b c)=2.3が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c}とされる（図１０（Ｃ））。
【００９０】
18. 17の再帰的処理の中で、β={a,c}のうちaがitemとして選択され、α=b c aとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c aに対する指標Χ2(b c a)=1.5が閾値τK=1.3を超えるため（ステップＳ１４２３）、出力リストLから[a c c, 1.3]が削除され、b c aと指標Χ2(b c a)=1.5との組[b c a, 1.5]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｈ））。
【００９１】
19. これ以上のプロジェクションが不可能なので、17の再帰的処理の中で、β={a,c}のうちcがitemとして選択され、α=b c cとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b c cに対する指標Χ2(b c c)=1.3が閾値τK=1.3も限界値Χ2max(b c c)=1.3も閾値τK=1.3を超えず（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、17の再帰的処理が終了し、14の再帰的処理に戻る。14の再帰的処理ではβ={a,c,d}であるが、β={a,c,d}のうちa,cについては処理済みである。
【００９２】
20. 14の再帰的処理の中で、β={a,c,d}のうちdがitemとして選択され、α=b dとされる（ステップ１４１５，Ｓ１４１６／図１０（Ｃ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=b d対する指標Χ2(b d)=0.2も限界値Χ2max(b d)=0.5も閾値τK=1.3を超えず、（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、14の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,bについては処理済みである。
【００９３】
21. 最初のループ処理の中で、β={a,b,c,d}のうちcがitemとして選択され、α=cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=cに対する指標Χ2(ｃ)=0.2は閾値τK=1.3を越えないが（ステップＳ１４２３）、限界値Χ2max(b)=3.1が閾値τK=1.3を超えるため（ステップＳ１４２９）、プロジェクションが行われ（ステップＳ１４３０）、その再帰的処理の中でβ={a,c}とされる（図１１（Ａ））。
【００９４】
22. 21の再帰的処理の中で、β={a,c}のうちaがitemとして選択され、α=c aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=c aに対する指標Χ2(c a)=1.5が閾値τK=1.3を超えるため（ステップＳ１４２３）、出力リストLから[a b c c, 1.3]が削除され、c aと指標Χ2(c a)=1.5との組[c a, 1.5]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.3とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｉ））。
【００９５】
23. これ以上のプロジェクションが不可能なので、21の再帰的処理の中で、β={a,c}のうちcがitemとして選択され、α=c cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ａ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=c cに対する指標Χ2(c c)=1.3が閾値τK=1.3も限界値Χ2max(c c)=1.3も閾値τK=1.3を超えず（ステップＳ１４２３，Ｓ１４２９）、ステップＳ１４３１の判定でyesとされるため、21の再帰的処理が終了し、最初のループ処理に戻る。最初のループ処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,b,cについては処理済みである。
【００９６】
24. 最初のループ処理の中で、β={a,b,c,d}のうちdがitemとして選択され、α=dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=dに対する指標Χ2(d)=2.1は閾値τK=1.3を越えるため（ステップＳ１４２３）、出力リストLから[a b c, 1.3]が削除され、dと指標Χ2(d)=2.1との組[d, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.5とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｊ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={a,b,c,d}とされる（図１１（Ｂ））。
【００９７】
25. 24の再帰的処理の中で、β={a,b,c,d}のうちaがitemとして選択され、α=d aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d aに対する指標Χ2(d a)=2.1が閾値τK=1.5を超えるため（ステップＳ１４２３）、出力リストLから[c a, 1.5]が削除され、d aと指標Χ2(d a)=2.1との組[d a, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=1.5とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｋ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={b,d}とされる（図１１（Ｂ））。
【００９８】
26. 25の再帰的処理の中で、β={b,d}のうちbがitemとして選択され、α=d a bとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d a bに対する指標Χ2(d a b)=0.2も限界値Χ2max(d a b)=0.5も閾値τK=1.5を越えない（ステップＳ１４２３，Ｓ１４２９）。
【００９９】
27. 次に、25の再帰的処理の中で、β={b,d}のうちdがitemとして選択され、α=d a dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d a dに対する指標Χ2(d a d)=0.2も限界値Χ2max(d a d)=0.5も閾値τK=1.5を越えず（ステップＳ１４２３，Ｓ１４２９）、β={b,d}のすべての要素が処理済であるため（ステップＳ１４３１）、25の再帰的処理が終了し、24の再帰的処理に戻る。24の再帰的処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちaについては処理済みである。
【０１００】
28. 24の再帰的処理の中で、β={a,b,c,d}のうちbがitemとして選択され、α=d bとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d bに対する指標Χ2(d b)=2.1が閾値τK=1.5を超えるため（ステップＳ１４２３）、出力リストLから[b c a, 1.5]が削除され、d bと指標Χ2(d b)=2.1との組[d b, 2.1]が出力リストLの要素に追加され、出力リストLの要素が並び替えられて、閾値がτK=2.1とされる（ステップＳ１４２４〜Ｓ１４２７／図９（Ｌ））。さらに、プロジェクションが行われ（ステップＳ１４２８）、その再帰的処理の中でβ={a,c,d}とされる（図１１（Ｂ））。
【０１０１】
29. 28の再帰的処理の中で、β={a,c,d}のうちaがitemとして選択され、α=d b aとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b aに対する指標Χ2(d b a)=1.5も限界値Χ2max(d b a)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０２】
30. 28の再帰的処理の中で、β={a,c,d}のうちcがitemとして選択され、α=d b cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b cに対する指標Χ2(d b c)=1.5も限界値Χ2max(d b a)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０３】
31. 28の再帰的処理の中で、β={a,c,d}のうちdがitemとして選択され、α=d b dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d b dに対する指標Χ2(d b d)=0.5も限界値Χ2max(d b d)=0.2も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。28の再帰的処理のステップＳ１４３１の判定でyesとされるため、28の再帰的処理が終了し、24の再帰的処理に戻る。24の再帰的処理では、β={a,b,c,d}であるが、β={a,b,c,d}のうちa,bについては処理済みである。
【０１０４】
32. 24の再帰的処理の中で、β={a,b,c,d}のうちcがitemとして選択され、α=d cとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d cに対する指標Χ2(d c)=1.5も限界値Χ2max(d c)=1.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。
【０１０５】
33. 24の再帰的処理の中で、β={a,b,c,d}のうちdがitemとして選択され、α=d dとされる（ステップ１４１５，Ｓ１４１６／図１１（Ｂ））。|L|<K(k=4)でなく（ステップＳ１４１７）、α=d dに対する指標Χ2(d d)=0.2も限界値Χ2max(d d)=0.5も閾値τK=2.1を越えない（ステップＳ１４２３，Ｓ１４２９）。24の再帰的処理のステップＳ１４３１の判定でyesとされるため24の再帰的処理が終了し、最初のループ処理に戻る。
【０１０６】
34. 最初のループ処理のステップＳ１４３１の判定でyesとされるためステップＳ１４の処理が終了し、記憶部１６ｅに格納された出力リストLが出力される。
【０１０７】
〔変形例など〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上記の実施形態では、ステップＳ１３でラベルありデータと確率データ付きデータとを合成したデータベースを生成する際、確率データ付きデータが含む確率Pr(P+|x)，Pr(P-|x)に減衰パラメータλが乗じられた。しかし、減衰パラメータλが乗じられない構成であってもよい。また逆に、ラベルありデータのラベル値（1 or 2）に)に増幅パラメータρ（ρ≧1、好ましくはρ＞1）が乗じられてもよい。また、減衰パラメータλと増幅パラメータρの両方が乗じられてもよい。
【０１０８】
また、式(25)-(28)の代わりに以下の式(31)-(34)が用いられてもよい。
【０１０９】
N=ρ・|DL|+|DU| …(31)
【０１１０】
【数１１】
或いは、式(25)-(28)の代わりに以下の式(35)-(38)が用いられてもよい。
【０１１１】
N=ρ・|DL|+λ・|DU| …(35)
【０１１２】
【数１２】
すなわち、データベースが含むラベルありテキストの総数|DL|から定まる値が、当該総数|DL|と所定の増幅パラメータとの積であり、データベースが含むラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値が、当該ラベルありテキストのうち所定の集合に属することを表すラベルに対応付けられたものの総数と増幅パラメータとの積であり、データベースが含むラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち第１パターンαを含むものの総数から定まる値が、当該ラベルありテキストであって所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち第１パターンαを含むものの総数と増幅パラメータとの積であり、第１パターンαを含むラベルありテキストの総数から定まる値が、当該第１パターンαを含むラベルありテキストの総数と増幅パラメータとの積であってもよい。
【０１１３】
また、上述の実施形態では、Χ2(α)そのものを指標として用いた。しかし、その他のΧ2(α)の広義単調関数値（単調非減少関数値）に相当する値を指標としてもよい。なお、Χ2(α)の広義単調関数値に相当する値は、Χ2(α)そのものをも含む概念である。例えば、Χ2(α)の広義単調増加関数値に相当する値を指標とするのであれば、指標の値が大きいパターンαほどラベル分類に寄与する度合いが大きいといえる。また、例えば、Χ2(α)の広義単調減少関数値に相当する値を指標とするのであれば、指標の値が小さいパターンαほどラベル分類に寄与する度合いが大きいといえる。その他、パターンαと、パターンαを含むテキストを当該テキストが属する集合に分類した際の分類結果との関連性の高さを表す凸関数値を指標としてもよい。
【０１１４】
同様に、上述の実施形態では、Χ2max(α)そのものを指標として用いた。しかし、その他のΧ2max(α)の広義単調関数値に相当する値を指標としてもよい。なお、Χ2max(α)の広義単調関数値に相当する値は、Χ2max(α)そのものをも含む概念である。
【０１１５】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１１８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１２１】
１ パターン抽出装置
１１ 訓練部
１２ 分類部
１３ データベース合成部
１４ 抽出部
１５ 制御部
１６ａ〜１６ｅ 記憶部
【特許請求の範囲】
【請求項１】
１個以上の記号からなる要素をアイテムとし、１個以上の前記アイテムからなる系列をテキストとし、前記テキストが含む１個以上の前記アイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられた前記テキストをラベルありテキストとし、前記ラベルに対応付けられていない前記テキストをラベルなしテキストとした場合における、前記ラベルなしテキストを格納する記憶部と、
前記ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成された分類モデルを、前記ラベルなしテキストに適用し、当該ラベルなしテキストが前記所定の集合に属する確率を表す確率データを生成する分類部と、
前記分類部で生成された前記確率データから定まる値を用い、任意の前記パターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標を生成する抽出部と、
を有するパターン抽出装置。
【請求項２】
請求項１のパターン抽出装置であって、
前記抽出部は、
前記指標が所定の第１出力条件を満たすときに、前記第１パターンを出力リストの要素として出力するとともに、当該第１パターンに１個以上のアイテムが付加された系列である第２パターンと、当該第２パターンを含む第２テキストを当該第２テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第２指標を生成し、当該第２指標が所定の第２出力条件を満たすときに、当該第２パターンを出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項３】
請求項２のパターン抽出装置であって、
前記抽出部は、
前記第１パターンに１個以上のアイテムが付加された任意の系列である任意パターンと、当該任意パターンを含む任意のテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標の限界値を生成し、前記指標が前記第１出力条件を満たさないが前記限界値が所定の探索条件を満たすときに、当該第１パターンを出力リストの要素として出力することなく、当該第１パターンに１個以上のアイテムが付加された系列である第３パターンと、当該第３パターンを含む第３テキストを当該第３テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第３指標を生成し、当該第３指標が所定の第３出力条件を満たすときに、当該第３パターンを出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項４】
請求項１から３の何れかのパターン抽出装置であって、
前記確率データから定まる値は、当該確率データと所定の減衰パラメータとの積である、
ことを特徴とするパターン抽出装置。
【請求項５】
請求項１から４の何れかのパターン抽出装置であって、
前記指標は、
|DL|個（|DL|≧0）の前記ラベルありテキストと、前記確率データがそれぞれ生成された|DU|個（|DU|＞0）の前記ラベルなしテキストと、を含むデータベースに対して生成され、
前記第１パターンをαとし、
前記データベースが含む前記ラベルありテキストの総数|DL|から定まる値と、前記データベースが含む前記ラベルなしテキストの総数|DU|から定まる値と、の和をNとし、
前記データベースが含むラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値と、前記分類部で生成された前記確率データから定まる値の総数と、の和をMとし、
前記データベースが含むラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数から定まる値と、前記第１パターンαを含むラベルなしテキストが前記所定の集合に属する確率を表す確率データから定まる値の総数と、の和をy(α)とし、
前記第１パターンαを含むラベルありテキストの総数から定まる値と、前記第１パターンαを含むラベルなしテキストの総数から定まる値と、の和をx(α)とした場合における、
【数１３】
の広義単調関数値に相当する値である、
ことを特徴とするパターン抽出装置。
【請求項６】
請求項５のパターン抽出装置であって、
前記抽出部は、さらに、
y=xである場合の前記Χ2(α)をΧ2(α, y=x)とし、y=0である場合の前記Χ2(α)をΧ2(α,y=0)とし、ν≧μの場合のmax(ν, μ)をνとし、ν＜μの場合のmax(ν, μ)をμとした場合における、
Χ2max(α)=max(Χ2(α, y=x), Χ2(α,y=0))
の広義単調関数値に相当する指標の限界値を生成する、
ことを特徴とするパターン抽出装置。
【請求項７】
請求項５から６の何れかのパターン抽出装置であって、
前記データベースが含む前記ラベルなしテキストの総数|DU|から定まる値が、当該ラベルなしテキストの総数|DU|と所定の減衰パラメータとの積であり、前記確率データから定まる値が、当該確率データが表す確率と前記減衰パラメータとの積であり、前記第１パターンαを含むラベルなしテキストの総数から定まる値が、当該第１パターンαを含むラベルなしテキストの総数と前記減衰パラメータとの積である、
及び／又は、
前記データベースが含む前記ラベルありテキストの総数|DL|から定まる値が、当該総数|DL|と所定の増幅パラメータとの積であり、前記データベースが含むラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値が、当該ラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数と前記増幅パラメータとの積であり、前記データベースが含むラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数から定まる値が、当該ラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数と前記増幅パラメータとの積であり、前記第１パターンαを含むラベルありテキストの総数から定まる値が、当該第１パターンαを含むラベルありテキストの総数と前記増幅パラメータとの積である、
ことを特徴とするパターン抽出装置。
【請求項８】
請求項１から７の何れかのパターン抽出装置であって、
前記抽出部は、対応する前記指標の大きさの大きい順に選択された所定個以下のパターンを、出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項９】
分類部が、１個以上の記号からなる要素をアイテムとし、１個以上の前記アイテムからなる系列をテキストとし、前記テキストが含む１個以上の前記アイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられた前記テキストをラベルありテキストとし、前記ラベルに対応付けられていない前記テキストをラベルなしテキストとした場合における、前記ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成された分類モデルを、記憶部に格納された前記ラベルなしテキストに適用し、当該ラベルなしテキストが前記所定の集合に属する確率を表す確率データを生成するステップと、
抽出部が、前記分類部で生成された前記確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標を生成するステップと、
を有するパターン抽出方法。
【請求項１０】
請求項１から８の何れかのパターン抽出装置としてコンピュータを機能させるためのプログラム。
【請求項１】
１個以上の記号からなる要素をアイテムとし、１個以上の前記アイテムからなる系列をテキストとし、前記テキストが含む１個以上の前記アイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられた前記テキストをラベルありテキストとし、前記ラベルに対応付けられていない前記テキストをラベルなしテキストとした場合における、前記ラベルなしテキストを格納する記憶部と、
前記ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成された分類モデルを、前記ラベルなしテキストに適用し、当該ラベルなしテキストが前記所定の集合に属する確率を表す確率データを生成する分類部と、
前記分類部で生成された前記確率データから定まる値を用い、任意の前記パターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標を生成する抽出部と、
を有するパターン抽出装置。
【請求項２】
請求項１のパターン抽出装置であって、
前記抽出部は、
前記指標が所定の第１出力条件を満たすときに、前記第１パターンを出力リストの要素として出力するとともに、当該第１パターンに１個以上のアイテムが付加された系列である第２パターンと、当該第２パターンを含む第２テキストを当該第２テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第２指標を生成し、当該第２指標が所定の第２出力条件を満たすときに、当該第２パターンを出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項３】
請求項２のパターン抽出装置であって、
前記抽出部は、
前記第１パターンに１個以上のアイテムが付加された任意の系列である任意パターンと、当該任意パターンを含む任意のテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標の限界値を生成し、前記指標が前記第１出力条件を満たさないが前記限界値が所定の探索条件を満たすときに、当該第１パターンを出力リストの要素として出力することなく、当該第１パターンに１個以上のアイテムが付加された系列である第３パターンと、当該第３パターンを含む第３テキストを当該第３テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す第３指標を生成し、当該第３指標が所定の第３出力条件を満たすときに、当該第３パターンを出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項４】
請求項１から３の何れかのパターン抽出装置であって、
前記確率データから定まる値は、当該確率データと所定の減衰パラメータとの積である、
ことを特徴とするパターン抽出装置。
【請求項５】
請求項１から４の何れかのパターン抽出装置であって、
前記指標は、
|DL|個（|DL|≧0）の前記ラベルありテキストと、前記確率データがそれぞれ生成された|DU|個（|DU|＞0）の前記ラベルなしテキストと、を含むデータベースに対して生成され、
前記第１パターンをαとし、
前記データベースが含む前記ラベルありテキストの総数|DL|から定まる値と、前記データベースが含む前記ラベルなしテキストの総数|DU|から定まる値と、の和をNとし、
前記データベースが含むラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値と、前記分類部で生成された前記確率データから定まる値の総数と、の和をMとし、
前記データベースが含むラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数から定まる値と、前記第１パターンαを含むラベルなしテキストが前記所定の集合に属する確率を表す確率データから定まる値の総数と、の和をy(α)とし、
前記第１パターンαを含むラベルありテキストの総数から定まる値と、前記第１パターンαを含むラベルなしテキストの総数から定まる値と、の和をx(α)とした場合における、
【数１３】
の広義単調関数値に相当する値である、
ことを特徴とするパターン抽出装置。
【請求項６】
請求項５のパターン抽出装置であって、
前記抽出部は、さらに、
y=xである場合の前記Χ2(α)をΧ2(α, y=x)とし、y=0である場合の前記Χ2(α)をΧ2(α,y=0)とし、ν≧μの場合のmax(ν, μ)をνとし、ν＜μの場合のmax(ν, μ)をμとした場合における、
Χ2max(α)=max(Χ2(α, y=x), Χ2(α,y=0))
の広義単調関数値に相当する指標の限界値を生成する、
ことを特徴とするパターン抽出装置。
【請求項７】
請求項５から６の何れかのパターン抽出装置であって、
前記データベースが含む前記ラベルなしテキストの総数|DU|から定まる値が、当該ラベルなしテキストの総数|DU|と所定の減衰パラメータとの積であり、前記確率データから定まる値が、当該確率データが表す確率と前記減衰パラメータとの積であり、前記第１パターンαを含むラベルなしテキストの総数から定まる値が、当該第１パターンαを含むラベルなしテキストの総数と前記減衰パラメータとの積である、
及び／又は、
前記データベースが含む前記ラベルありテキストの総数|DL|から定まる値が、当該総数|DL|と所定の増幅パラメータとの積であり、前記データベースが含むラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数から定まる値が、当該ラベルありテキストのうち前記所定の集合に属することを表すラベルに対応付けられたものの総数と前記増幅パラメータとの積であり、前記データベースが含むラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数から定まる値が、当該ラベルありテキストであって前記所定の集合に属することを表すラベルに対応付けられたラベルありテキストのうち前記第１パターンαを含むものの総数と前記増幅パラメータとの積であり、前記第１パターンαを含むラベルありテキストの総数から定まる値が、当該第１パターンαを含むラベルありテキストの総数と前記増幅パラメータとの積である、
ことを特徴とするパターン抽出装置。
【請求項８】
請求項１から７の何れかのパターン抽出装置であって、
前記抽出部は、対応する前記指標の大きさの大きい順に選択された所定個以下のパターンを、出力リストの要素として出力するように構成される、
ことを特徴とするパターン抽出装置。
【請求項９】
分類部が、１個以上の記号からなる要素をアイテムとし、１個以上の前記アイテムからなる系列をテキストとし、前記テキストが含む１個以上の前記アイテムからなる系列をパターンとし、テキストが属する集合を表すデータであるラベルに対応付けられた前記テキストをラベルありテキストとし、前記ラベルに対応付けられていない前記テキストをラベルなしテキストとした場合における、前記ラベルありテキストが訓練データとして用いられて生成された統計モデルであって、なおかつ、適用された任意のテキストが所定の集合に属する確率を表す確率データを出力するように構成された分類モデルを、記憶部に格納された前記ラベルなしテキストに適用し、当該ラベルなしテキストが前記所定の集合に属する確率を表す確率データを生成するステップと、
抽出部が、前記分類部で生成された前記確率データから定まる値を用い、任意のパターンである第１パターンと、当該第１パターンを含むテキストを当該テキストが属する集合に分類した際の分類結果と、の関連性の高さを表す指標を生成するステップと、
を有するパターン抽出方法。
【請求項１０】
請求項１から８の何れかのパターン抽出装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−１５４４６９（Ｐ２０１１−１５４４６９Ａ）
【公開日】平成２３年８月１１日（２０１１．８．１１）
【国際特許分類】
【出願番号】特願２０１０−１４６０３（Ｐ２０１０−１４６０３）
【出願日】平成２２年１月２６日（２０１０．１．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年８月１１日（２０１１．８．１１）
【国際特許分類】
【出願日】平成２２年１月２６日（２０１０．１．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]