(57)【要約】【課題】冗長性を削除すると共に、可変長ワイルドカードの幅を限定したパターンを抽出できるパターン抽出プログラム及びパターン抽出方法を提供することを目的とする。【解決手段】コンピュータに、シーケンス集合表からパターンに含まれる構成単位の列をパターン毎に抽出するステップと、パターン集合表から選択した同じ構成単位の並びを持つパターンの一方が他方の真部分集合であるかを判断するステップと、真部分集合と判断されたパターンをシーケンス集合表から削除するステップと、処理対象のパターン及び処理対象の親パターンに対応する第１及び第２射影データベースとに基づき、最右端の構成単位の右隣位置の差から同一シーケンスＩＤごとの差分を計算するステップと、差分集合表が保持している同一シーケンスＩＤごとの差分に基づき、ワイルドカードの幅が最小となるパターンを抽出するステップとを実行させることで上記課題を解決する。【選択図】  図４
2011086252.tif 000002
【特許請求の範囲】
【請求項１】
可変長ワイルドカードを用いた頻出パターンを抽出するコンピュータに、
可変長ワイルドカードと構成単位とにより表現されたパターンにマッチするシーケンスの識別子の集合を保持するシーケンス集合表から、前記パターンに含まれる構成単位の列を前記パターン毎に抽出し、同じ構成単位の並びを持つ前記パターンの集合をパターン集合表に保持させるステップと、
前記パターン集合表が保持している同じ構成単位の並びを持つパターンを二つずつ選択して、二つのパターンに対応するシーケンスの識別子の集合から前記二つのパターンの一方が他方の真部分集合であるかを判断するステップと、
前記二つのパターンの一方が他方の真部分集合であると判断されたとき、真部分集合と判断された前記二つのパターンの一方を前記シーケンス集合表から削除するステップと、
処理対象のパターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第１射影データベースと前記処理対象のパターンより可変長ワイルドカードと構成単位が少ない親パターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第２射影データベースとに基づき、第１及び第２射影データベースの同一シーケンスの識別子に対応する最右端の構成単位の右隣位置の差から同一シーケンスの識別子ごとの差分を計算し差分集合表に保持させるステップと、
前記差分集合表が保持している同一シーケンスの識別子ごとの差分に基づき、前記可変長ワイルドカードの幅が最小となるパターンを抽出する抽出ステップと、
を実行させるためのパターン抽出プログラム。
【請求項２】
前記抽出ステップは、
前記差分集合表から差分の値が１個であるシーケンスの識別子を求め、そのシーケンスの識別子に対応する差分の値から最小値及び最大値を算出するステップと、
前記差分集合表から差分の値が複数であるシーケンスの識別子を求め、そのシーケンスの識別子に対応する差分の値が全て前記最大値より大きいとき、前記差分の値が複数であるシーケンスの識別子に対応する差分の値のうち小さい方の値で前記最大値を更新するステップと、
前記差分集合表から差分の値が複数であるシーケンスの識別子を求め、そのシーケンスの識別子に対応する差分の値が全て前記最小値より小さいとき、前記差分の値が複数であるシーケンスの識別子に対応する差分の値のうち大きい方の値で前記最小値を更新するステップと、
前記差分集合表から差分の値が複数であるシーケンスの識別子を求め、そのシーケンスの識別子に対応する差分の値が全て前記最小値より小さく、且つ、前記最大値より大きいとき、前記差分の値が複数であるシーケンスの識別子に対応する差分の値と前記最小値との差の最小値を求め、前記差分の値が複数であるシーケンスの識別子に対応する差分の値と前記最大値との差の最小値を求め、前記差分の値と前記最小値との差の最小値より前記差分の値と前記最大値との差の最小値の方が小さければ、前記差分の値と前記最大値との差の最小値に対応する前記差分の値で前記最大値を更新し、前記差分の値と前記最小値との差の最小値より前記差分の値と前記最大値との差の最小値の方が小さくなければ、前記差分の値と前記最小値との差の最小値に対応する前記差分の値で前記最小値を更新するステップと
を有する請求項１記載のパターン抽出プログラム。
【請求項３】
前記パターンの一番右の可変長ワイルドカードから順番に、前記可変長ワイルドカードの幅が最小となるパターンを抽出することを特徴とする請求項１又は２記載のパターン抽出プログラム。
【請求項４】
前記処理対象の親パターンは、右に可変長ワイルドカードと構成単位とを追加して処理対象のパターンを生成するのに用いたパターンであることを特徴とする請求項１乃至３何れか一項記載のパターン抽出プログラム。
【請求項５】
可変長ワイルドカードを用いた頻出パターンを抽出するコンピュータによって実行されるパターン抽出方法であって、
前記コンピュータが、
可変長ワイルドカードと構成単位とにより表現されたパターンにマッチするシーケンスの識別子の集合を保持するシーケンス集合表から、前記パターンに含まれる構成単位の列を前記パターン毎に抽出し、同じ構成単位の並びを持つ前記パターンの集合をパターン集合表に保持させるステップと、
前記パターン集合表が保持している同じ構成単位の並びを持つパターンを二つずつ選択して、二つのパターンに対応するシーケンスの識別子の集合から前記二つのパターンの一方が他方の真部分集合であるかを判断するステップと、
前記二つのパターンの一方が他方の真部分集合であると判断されたとき、真部分集合と判断された前記二つのパターンの一方を前記シーケンス集合表から削除するステップと、
処理対象のパターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第１射影データベースと前記処理対象のパターンより可変長ワイルドカードと構成単位が少ない親パターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第２射影データベースとに基づき、第１及び第２射影データベースの同一シーケンスの識別子に対応する最右端の構成単位の右隣位置の差から同一シーケンスの識別子ごとの差分を計算し差分集合表に保持させるステップと、
前記差分集合表が保持している同一シーケンスの識別子ごとの差分に基づき、前記可変長ワイルドカードの幅が最小となるパターンを抽出する抽出ステップと、
を実行することを特徴とするパターン抽出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン抽出プログラム及びパターン抽出方法に係り、特に可変長ワイルドカードを用いた頻出パターンを抽出するパターン抽出プログラム及びパターン抽出方法に関する。
【背景技術】
【０００２】
業務プロセスの流れを可視化する技術を用いると、ユーザは業務プロセスの案件１個ごとに業務プロセスで実行される複数のイベント間の順序を抽出し、業務プロセスの案件１個が開始してから終了するまでに発生したイベントの連なり（シーケンス）を把握することができる（例えば非特許文献１参照）。
【０００３】
通常、業務プロセスは様々な要因によって例外や処理の変更が発生する。このような理由の為、シーケンスは、大まかな流れが同じであるものの、一部が異なるものが多種類発生する。このように多種類発生したシーケンスの集合から代表的なシーケンスの特徴を抽出することは困難である。
【０００４】
一方、例えばタンパク質の解析にはシーケンスマイニング技術が用いられている。タンパク質は複数種類のアミノ酸の並び方で出現する特徴が変わるが、特徴づけるアミノ酸の間にいくつかの関係のないアミノ酸が含まれている場合もある。そのような関係のないアミノ酸を無視して特徴に関与するアミノ酸の並びのみを表現する方法としては、特徴に関与しないアミノ酸部分をワイルドカードで表現するモチーフ"Motif"による表現が用いられている。なお、モチーフとは複数のシーケンスに共通して存在する特別な配列パターンである。以下では、長いモチーフのほうが、そのモチーフで代表されるシーケンス部分集合の特徴をより表していると仮定する。
【０００５】
複数のシーケンスからモチーフを発見する技法としては"PrefixSpan法"が知られている。また、PrefixSpanの拡張の一つとしては、新Modified PrefixSpan法が発表されている（例えば非特許文献２参照）。
【０００６】
新Modified PrefixSpan法は、特徴に関与しないシーケンス部分を表現するワイルドカードに可変長ワイルドカードを用いる。以下の説明では、シーケンスの構成単位をアルファベットで表す。シーケンスの構成単位は、業務プロセスの場合がイベント、タンパク質の場合がアミノ酸に相当する。
【０００７】
例えばシーケンスの構成単位を表すアルファベットがＡ、Ｂ、Ｃであるときは、配列パターン（以下、単にパターンという）<AC>、<AxC>、<AxxC>を表記<A-x(0,2)-C>でまとめて表現する。ただし、x(0,2)は、０個以上２個以下の任意の長さのアルファベット列を表す。単独のxは、任意のアルファベット１文字に対応する。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】"フィールド・イノベーションを実現する業務とシステムの可視化技術"、富士通ジャーナル、Vol.33、2007 No.298 p.20-23http://jp.fujitsu.com/about/journal/publication_number/index02.shtml#y07
【非特許文献２】搭野など(広島市立大)、"Modified PrefixSpan法を用いた頻出正規パターンの抽出をめざして"、DEWS2004
【発明の概要】
【発明が解決しようとする課題】
【０００９】
新Modified PrefixSpan法では、生成済みのパターンpatkに新たなワイルドカードと頻出アルファベットを追加して、より長いパターンpatk+1を生成する。patk+1を生成することにより、新Modified PrefixSpan法では、同じ最右端文字αを持つ以下のパターンが複数生成される場合がある（例えば非特許文献２参照）。ただし、cntは、あるシーケンスの集合に対してマッチしたシーケンスの個数を表す。
【００１０】
<patk-x(i,i+ε1)-α>:cntε1, <patk-x(i,i+ε2)-α>:cntε2, ... 
【００１１】
図１は複数のシーケンスを表した説明図である。図１に表したシーケンスは、構成単位を表すアルファベットがa,f,k,l,m,p,r,s,t,v,w,yである例を表している。それぞれのシーケンスには一意のシーケンスＩＤが付与されている。
【００１２】
ここでは、図１に示すシーケンスにおいて、新Modified PrefixSpan法の処理途中で生成されたパターンに、以下の複数のパターン（Ａ）が含まれていたとして説明する。
【００１３】
<k-x(0,2)-a> (0 1 5 6 7)、<k-x(0,0)-a> (0 1 5 6 7)、<k-x(0,3)-a> (0 1 4 5 6 7 8 10)、<k-x(1,4)-a> (4 5 8 9 10)、<k-x(2,4)-a> (4 5 8 9 10)・・・（Ａ）
【００１４】
ただし、パターンの後の括弧内の数値は、そのパターンにマッチしているシーケンスのシーケンスＩＤを表す。
【００１５】
<patk-x(i,i+ε1)-α>にマッチするシーケンス集合Sk+1ε1と<patk-x(i,i+ε2)-α>にマッチするSk+1ε2はε1≦ε2ならばSk+1ε1⊆Sk+1ε2の関係にある。新Modified PrefixSpan法では、<patk-x(i,i+ε2)-α>を代表として選択して、冗長性のない(k+1)-頻出パターンを抽出する。そのため、新Modified PrefixSpan法を上記のパターン（Ａ）に適用すると冗長性のないパターンとして、以下の複数のパターン（Ｂ）が選択される。
【００１６】
<k-x(0,3)-a> (0 1 4 5 6 7 8 10)、<k-x(1,4)-a> (4 5 8 9 10)、<k-x(2,4)-a> (4 5 8 9 10)・・・（Ｂ）
【００１７】
しかし、パターン（Ｂ）は同じシーケンス集合が得られる<k-x(1,4)-a>と<k-x(2,4)-a>が存在し、依然として冗長である。これは、新Modified PrefixSpan法で可変長ワイルドカードの最小値（x(i,j)におけるi）が異なるパターンの冗長性を考慮しない為で、依然として冗長性が存在するという問題があった。
【００１８】
そこで、より冗長性を減少させる為の方法としては、例えば新Modified PrefixSpan法を拡張して最右端のワイルドカードx(im,jm)から、x(i,j)、ただしi=min(im),j=max(jm)を求めることが考えられる。上記パターン（Ｂ）に適用すると、以下のパターン（Ｃ）が生成できる。
【００１９】
<k-x(0,4)-a> (0 1 4 5 6 7 8 9 10)・・・（Ｃ）
【００２０】
この場合、パターンは１個のみとなるが、可変長ワイルドカードの範囲を広く取りすぎた為にパターン（Ａ），（Ｂ）の結果に見られるパターンの性質が得られないという問題があった。
【００２１】
また、新Modified PrefixSpan法は、以下のような別の問題もあった。パターンpatkからpatk+1を生成すると、元のpatkよりもマッチするシーケンスが減る可能性があるために、patk部分のワイルドカードは、より狭い範囲に限定できる可能性がある。
【００２２】
例えば図１に示すシーケンスから新Modified PrefixSpan法で以下のような長さ４のパターン（Ｄ）が得られる。しかし、パターン（Ｄ）と同じシーケンス集合を得られる最小のワイルドカードの範囲（幅）を持つパターンとして以下のようなパターン（Ｅ）が存在するが新Modified PrefixSpan法では検出されない。
【００２３】
<f-x(0,3)-s-x(0,2)-k-x(0,3)-a> (1 4 5 7 10)・・・（Ｄ）
<f-x(0,2)-s-x(0,1)-k-x(0,3)-a> (1 4 5 7 10)・・・（Ｅ）
【００２４】
ワイルドカードの幅が限定されているパターン（Ｅ）はパターン（Ｄ）よりもパターンが持つ性質を正確に表していると考えられる。このように、新Modified PrefixSpan法はワイルドカードの幅を限定したパターンが得られないという問題があった。
【００２５】
本発明の一実施形態は、上記の点に鑑みなされたもので、冗長性を削除すると共に、可変長ワイルドカードの幅を限定したパターンを抽出できるパターン抽出プログラム及びパターン抽出方法を提供することを目的とする。
【課題を解決するための手段】
【００２６】
上記課題を解決するため、本発明の一実施形態は、  可変長ワイルドカードを用いた頻出パターンを抽出するコンピュータに、可変長ワイルドカードと構成単位とにより表現されたパターンにマッチするシーケンスの識別子の集合を保持するシーケンス集合表から、前記パターンに含まれる構成単位の列を前記パターン毎に抽出し、同じ構成単位の並びを持つ前記パターンの集合をパターン集合表に保持させるステップと、前記パターン集合表が保持している同じ構成単位の並びを持つパターンを二つずつ選択して、二つのパターンに対応するシーケンスの識別子の集合から前記二つのパターンの一方が他方の真部分集合であるかを判断するステップと、前記二つのパターンの一方が他方の真部分集合であると判断されたとき、真部分集合と判断された前記二つのパターンの一方を前記シーケンス集合表から削除するステップと、処理対象のパターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第１射影データベースと前記処理対象のパターンより可変長ワイルドカードと構成単位が少ない親パターンに対応するシーケンスの識別子ごとに最右端の構成単位の右隣位置を保持する第２射影データベースとに基づき、第１及び第２射影データベースの同一シーケンスの識別子に対応する最右端の構成単位の右隣位置の差から同一シーケンスの識別子ごとの差分を計算し差分集合表に保持させるステップと、前記差分集合表が保持している同一シーケンスの識別子ごとの差分に基づき、前記可変長ワイルドカードの幅が最小となるパターンを抽出する抽出ステップと、を実行させるためのパターン抽出プログラムである。
【００２７】
なお、本発明の一実施形態の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも本発明の態様として有効である。
【発明の効果】
【００２８】
上述の如く、本発明の一実施形態によれば、冗長性を削除すると共に、可変長ワイルドカードの幅を限定したパターンを抽出できる。
【図面の簡単な説明】
【００２９】
【図１】複数のシーケンスを表した説明図である。
【図２】本実施例のパターン抽出装置を含むシステムの一例の構成図である。
【図３】パターン抽出装置の一例のハードウェア構成図である。
【図４】パターン抽出装置の一例のブロック図である。
【図５】冗長パターン削除処理の一例のイメージ図である。
【図６】冗長パターン削除処理の手順を示す一例のフローチャートである。
【図７】ワイルドカード決定処理の一例のイメージ図である。
【図８】ワイルドカード決定処理の手順を示す一例のフローチャートである。
【図９】ステップＳ２０４の処理の手順を示す一例のフローチャートである。
【図１０】冗長パターン削除処理とワイルドカード決定処理とを交互に連続して実行しながらパターン長がより長いパターンを取得していく一例の全体処理フローである。
【図１１】冗長パターン削除処理の手順を示す他の例のフローチャートである。
【図１２】ステップＳ２０４の処理の一例のイメージ図である。
【図１３】新Modified PrefixSpan法で抽出したパターン一覧を示す説明図である。
【図１４】本実施例により抽出したパターン一覧を示す説明図である。
【発明を実施するための形態】
【００３０】
次に、本発明を実施するための形態を、以下の実施例に基づき図面を参照しつつ説明していく。なお、本実施例は、業務プロセスやタンパク質，ＤＮＡの解析の他、顧客の購買履歴，Ｗｅｂアクセス履歴，科学的な実験データ，病気の治療履歴，自然災害の履歴などの分析に利用できる。
【００３１】
図２は本実施例のパターン抽出装置を含むシステムの一例の構成図である。パターン抽出装置１は図２（Ａ）に示すようにスタンドアローンの形態でも良いし、図２（Ｂ）に示すようにインターネットやＬＡＮなどのネットワーク３経由でユーザ端末２にデータ通信可能に接続された形態でもよい。
【００３２】
パターン抽出装置１は、例えば図３に示すように構成される。図３はパターン抽出装置の一例のハードウェア構成図である。パターン抽出装置１は、それぞれバスＢで相互に接続されている入力装置１１，出力装置１２，ドライブ装置１３，補助記憶装置１４，主記憶装置１５，演算処理装置１６及びインターフェース装置１７を有する。
【００３３】
入力装置１１はキーボードやマウス等である。入力装置１１は、各種信号を入力するために用いられる。出力装置１２はディスプレイ装置等である。出力装置１２は、各種ウインドウやデータ等を表示するために用いられる。インターフェース装置１７は、モデム又はＬＡＮカード等である。インターフェース装置１７は、ネットワーク３に接続する為に用いられる。
【００３４】
本実施例のパターン抽出プログラムは、パターン抽出装置１を制御する各種プログラムの少なくとも一部である。パターン抽出プログラムは例えば記録媒体１８の配布やネットワーク３からのダウンロードなどによって提供される。パターン抽出プログラムを記録した記録媒体１８としては、ＣＤ−ＲＯＭ、フレキシブルディスク、光磁気ディスク等の様に情報を光学的，電気的或いは磁気的に記録する記録媒体、ＲＯＭ、フラッシュメモリ等の様に情報を電気的に記録する半導体メモリ等、様々なタイプの記録媒体を用いることができる。
【００３５】
また、パターン抽出プログラムを記録した記録媒体１８がドライブ装置１３にセットされると、パターン抽出プログラムは記録媒体１８からドライブ装置１３を介して補助記憶装置１４にインストールされる。なお、ネットワーク３からダウンロードされたパターン抽出プログラムは、インターフェース装置１７を介して補助記憶装置１４にインストールされる。
【００３６】
補助記憶装置１４はインストールされたパターン抽出プログラムを格納すると共に、必要なファイル，データ等を格納する。主記憶装置１５は、パターン抽出プログラムの起動時に補助記憶装置１４からパターン抽出プログラムを読み出して格納する。そして、演算処理装置１６は主記憶装置１５に格納されたパターン抽出プログラムに従って、後述するような各種処理を実現している。
【００３７】
図４はパターン抽出装置の一例のブロック図である。パターン抽出装置１は、パターン生成部２１，シーケンス集合表生成部２２，パターン集合表生成部２３，冗長パターン削除部２４，ワイルドカード決定部２５，シーケンス表保存部３１，シーケンス集合表保存部３２，パターン集合表保存部３３，削除対象パターン表保存部３４，代表パターン表保存部３５，ＰＤＢ（射影データベース）保存部３６，差分集合表保存部３７を有する。図４の各ブロックについての詳細は後述する。
【００３８】
以下、パターン抽出装置１の冗長パターン削除処理及びワイルドカード決定処理について順次説明する。
【００３９】
（冗長パターン削除処理）
パターン抽出装置１の冗長パターン削除処理は、パターンにマッチするシーケンス集合が重複しているかを計算することにより、一のパターンを他のパターンで代表させられるかを決定するものである。
【００４０】
図５は冗長パターン削除処理の一例のイメージ図である。図５に含まれるシーケンス集合表１００はシーケンス集合表保存部３２が保存している。シーケンス集合表１００はパターン長ｋごとのパターンの集合（パターン集合）と、パターンにマッチするシーケンスＩＤとを保持する。
【００４１】
図５に含まれるアルファベット抽出機能１０１はパターン集合表生成部２３が有する機能である。アルファベット抽出機能１０１はシーケンス集合表１００に含まれるパターン長ｋのパターンから、そのパターンに含まれるアルファベットの列を抽出する。図５に含まれるパターン集合表１０２はパターン集合表保存部３３が保存している。パターン集合表１０２は、アルファベットの並びと、そのアルファベットの並びに該当するパターンの集合（パターン集合）とを保持する。パターン集合表１０２は同じアルファベットの並びを持つパターン集合を保持している。
【００４２】
図５に含まれる真部分集合かの判断機能１０３は冗長パターン削除部２４が有する機能である。冗長パターン削除部２４は、２個のシーケンス集合を与えられたときに真部分集合になっているかを判断する。ここでは、アルファベットの並び「f,s,k」を持つパターン集合<f-x(0,3)-s-x(0,2)-k>、<f-x(0,3)-s-x(0,0)-k> (4 5 7 9 10)を処理対象とする場合について説明する。
【００４３】
図５に含まれる削除対象パターン表１０４は削除対象パターン表保存部３４が保存している。削除対象パターン表保存部３４はシーケンス集合表１００から削除すべきパターンを記録する。図５に含まれる代表パターン表１０５は代表パターン表保存部３５が保存している。代表パターン表１０５は、あるアルファベットの並びを代表するパターン集合を保持する。
【００４４】
また、図５に含まれるパターン削除機能１０６は冗長パターン削除部２４が有する機能である。冗長パターン削除部２４は削除対象パターン表１０４が記録しているパターンをシーケンス集合表１００から削除する。つまり、パターン削除機能１０６は、同じアルファベットの並びを持つパターンにおいて、あるワイルドカードを採用したパターンのシーケンス集合が他のパターンのシーケンス集合の真部分集合である場合にそのパターンをシーケンス集合表１００から削除する。
【００４５】
ただし、２つのパターンのシーケンス集合が同一の場合、パターン抽出装置１の冗長パターン削除処理では、どちらのパターンも削除せずにそのまま用いる。この場合は、ワイルドカードの範囲が重複している場合と重複していない場合とがあり得るが、どちらの場合も削除しない。
【００４６】
なお、ワイルドカードの範囲が重複している場合、本実施例のパターン抽出装置１では後述のワイルドカード決定処理によりワイルドカードの範囲を限定することで、重複したパターンを取り除くことができる。また、ワイルドカードの範囲が重複していない場合は２つのパターンの性質が異なっていることになるので、削除せずにそのまま用いるのが妥当である。さらに、２つのパターンのシーケンス集合が真部分集合でない場合（部分集合であるが真部分集合でない場合と集合に重なりがない場合と）は、それぞれのパターンが異なる性質を表していると判断し、そのまま用いる。
【００４７】
図６は冗長パターン削除処理の手順を示す一例のフローチャートである。ステップＳ１００に進み、パターン生成部２１はシーケンス表保存部３１から図１に表したシーケンスを読み出し、既知の方法でパターンを生成する。ステップＳ１０１に進み、シーケンス集合表生成部２２はパターンをパターン長ｋごとに分類し、シーケンス集合表１００に保存する。
【００４８】
ステップＳ１０２に進み、シーケンス集合表生成部２２はパターンにマッチするシーケンスを計算し、パターンにマッチするシーケンスのシーケンスＩＤをシーケンス集合表１００に保存する。
【００４９】
ステップＳ１０３に進み、パターン集合表生成部２３のアルファベット抽出機能１０１はシーケンス集合表１００のパターン集合に含まれる各パターンからアルファベットの並びを抽出する。ステップＳ１０４に進み、パターン集合表生成部２３はアルファベットの並びが同じであるパターンのパターン集合を求め、そのパターン集合をパターン集合表１０２に格納する。
【００５０】
そして、冗長パターン削除部２４はステップＳ１０５に進み、パターン集合表１０２の同じアルファベットの並びを持つパターン集合ごとに以下の処理を行う。ステップＳ１０６に進み、冗長パターン削除部２４は代表パターン表１０５を初期化する。ステップＳ１０７に進み、冗長パターン削除部２４は削除対象パターン表１０４を初期化する。
【００５１】
ステップＳ１０８に進み、冗長パターン削除部２４の真部分集合かの判断機能１０３は同じアルファベットの並びを持つパターン集合からパターンを１個ずつ順に選択して処理対象パターンとする。
【００５２】
ステップＳ１０９に進み、真部分集合かの判断機能１０３は処理対象パターンに対応するシーケンス集合が、代表パターン表１０５に存在する代表パターンのシーケンス集合の真部分集合になっているかを判定する。代表パターンのシーケンス集合の真部分集合になっていれば、真部分集合かの判断機能１０３はステップＳ１１３に進み、処理対象パターンを削除対象パターン表１０４に追加したあと、ステップＳ１０８に戻る。
【００５３】
代表パターンのシーケンス集合の真部分集合になっていなければ、真部分集合かの判断機能１０３はステップＳ１１０に進み、代表パターン表１０５に存在する代表パターンのシーケンス集合が、処理対象パターンに対応するシーケンス集合の真部分集合になっているかを判定する。
【００５４】
処理対象パターンに対応するシーケンス集合の真部分集合になっていれば、真部分集合かの判断機能１０３はステップＳ１１４に進み、処理対象パターンに対応するシーケンス集合の真部分集合になっている代表パターンを代表パターン表１０５から削除し、削除対象パターン表１０４に追加する。真部分集合かの判断機能１０３は処理対象パターンを代表パターン表１０５に追加したあと、ステップＳ１０８に戻る。
【００５５】
処理対象パターンに対応するシーケンス集合の真部分集合になっていなければ、真部分集合かの判断機能１０３はステップＳ１１１に進み、処理対象パターンのシーケンス集合が代表パターンのシーケンス集合と等しいかを判定する。
【００５６】
代表パターンのシーケンス集合と等しくなければ、真部分集合かの判断機能１０３はステップＳ１１２に進み、処理対象パターンを代表パターン表１０５に追加したあと、ステップＳ１０８に戻る。代表パターンのシーケンス集合と等しければ、真部分集合かの判断機能１０３はステップＳ１０８に戻る。
【００５７】
同じアルファベットの並びを持つパターン集合からパターンを１個ずつ順に選択して全てのパターンを処理対象パターンとして処理すると、次のパターン集合について同様な処理を行う。パターン集合表１０２の全てのパターン集合についてステップＳ１０６〜Ｓ１１２の処理を終了すると、冗長パターン削除部２４のパターン削除機能１０６はステップＳ１１５に進み、削除対象パターン表１０４に含まれているパターンをシーケンス集合表１００から削除する。
【００５８】
（ワイルドカード決定処理）
パターン抽出装置１のワイルドカード決定処理は、PrefixSpan法で用いるＰＤＢを用いてワイルドカードを決定するものである。PrefixSpan法では、計算においてパターンごとにＰＤＢを計算している。ＰＤＢは、あるパターンpatkに対して、
pdbk={(i,j)|シーケンスiにおけるpatkの最右端アルファベットの右隣位置j}
である。つまりＰＤＢは、あるパターンにマッチするシーケンスＩＤと、パターンの一番右のアルファベットがマッチするシーケンスでの位置＋１を記録している。
【００５９】
図７はワイルドカード決定処理の一例のイメージ図である。図７に含まれるＰＤＢ２００，２０１はＰＤＢ保存部３６が保存している。ＰＤＢ２００は処理対象のパターンpatkが持つＰＤＢを格納した表である。ＰＤＢ２０１はpatkの親（右にワイルドカードとアルファベットを追加してpatkを生成するのに用いたパターン）patk-1が持つＰＤＢを格納した表である。
【００６０】
図７に含まれる差分計算機能２０２は、ワイルドカード決定部２５が有している機能である。差分計算機能２０２は、ＰＤＢ２００及びＰＤＢ２０１の同一のシーケンスＩＤの最右端アルファベットの右隣位置の差からワイルドカードの長さを計算する。図７に含まれる差分集合表２０３は差分集合表保存部３７が保存している。差分集合表２０３は差分計算機能２０２が計算したワイルドカードの長さを差分としてシーケンスＩＤごとに格納する。
【００６１】
図７に含まれる最小値、最大値計算機能２０４はワイルドカード決定部２５が有する機能である。最小値、最大値計算機能２０４は差分集合表２０３からシーケンスＩＤごとに差分の最小値、最大値を計算する。
【００６２】
1≦m≦kとするとき、patkの元になったパターンpatmと、パターンpatmの一つ前のパターンpatm-1とに対応するそれぞれのＰＤＢには、それぞれの最右端アルファベットの右隣位置が記録されているので、その差分から実際のギャップ（アルファベットをいくつ飛ばしたか）の長さを計算できる。計算された実際のギャップの長さは差分集合表２０３に格納される。最小値、最大値計算機能２０４は、差分集合表２０３からシーケンスＩＤごとにギャップの長さの最小値と最大値を求め、patkの対応するワイルドカードを置換する。最小値、最大値計算機能２０４は、パターンに対して一番右のワイルドカードから順に上記計算を行い、すべてのワイルドカードの幅が最小となるパターンを得る。
【００６３】
図８はワイルドカード決定処理の手順を示す一例のフローチャートである。ステップＳ２００に進み、patkのＰＤＢ２００に含まれるシーケンスＩＤの集合を生成し、indexesとする。ステップＳ２０１に進み、ワイルドカード決定部２５はm=k〜1の順に、以下の処理を行う。
【００６４】
ステップＳ２０２に進み、ワイルドカード決定部２５はpatkを生成する元となったpatm(m≦k)のＰＤＢであるpdbmの各要素(im,jm)のうち、そのシーケンスＩＤがindexesに含まれるものを対象に次の処理を行う。
【００６５】
ステップＳ２０３に進み、差分計算機能２０２はpatm-1のＰＤＢであるpdbm-1に含まれる要素(im-1,jm-1)のうちim=im-1なら、rel=jm-jm-1-1、0≦rel≦(max_wc+εmax)を満たすrelを計算する。ただしmax_wcは最大ワイルドカード数、εmaxは新Modified PrefixSpan法における最大誤差数である。
【００６６】
ステップＳ２０４に進み、最小値、最大値計算機能２０４は上記relの最小値および最大値を計算する。ただし、シーケンスに対応するrelの値は１個のみを選択する。一つのシーケンスＩＤに対し複数のrelが求まる場合は、その中から最小値ないし最大値の変化が最も少ない値を選択する。なお、ステップＳ２０４の詳細は後述する。
【００６７】
ステップＳ２０５に進み、最小値、最大値計算機能２０４はpatkのm-1番目の可変長ワイルドカードを、上記relの最小値および最大値で置換する。m=k〜1の全てについてステップＳ２０２〜Ｓ２０５の処理を終了すると、ワイルドカード決定部２５はワイルドカード決定処理を終了する。
【００６８】
図９はステップＳ２０４の処理の手順を示す一例のフローチャートである。ステップＳ３００に進み、最小値、最大値計算機能２０４はpdbmの各要素(im,jm)のうち、１回のみ現れるimに対応するrelの集合を求める。ステップＳ３０１に進み、最小値、最大値計算機能２０４はステップＳ３００で求めたrelの集合から、relの最小値minと最大値maxを算出する。ステップＳ３０２に進み、最小値、最大値計算機能２０４はpdbmの各要素のうち、2回以上現れるimを求め、imに対応するrelの集合を作る。ステップＳ３０３に進み、最小値、最大値計算機能２０４はrelの集合ごとにステップＳ３０４〜Ｓ３０７の処理を行い、以下の条件を満たすかを調べる。
【００６９】
ステップＳ３０４に進み、最小値、最大値計算機能２０４はrelの集合に含まれる値が全て最大値maxより大きいかを判定する。relの集合に含まれる値が全て最大値maxより大きい場合は該当のrelの最小値で最大値maxの値を更新する。relの集合に含まれる値のうち少なくとも一つが最大値maxより大きくない場合は該当のrelの値を更新することなくステップＳ３０６に進む。
【００７０】
ステップＳ３０６に進み、最小値、最大値計算機能２０４はrelの集合に含まれる値が全て最小値minより小さいかを判定する。relの集合に含まれる値が全て最小値minより小さい場合は該当のrelの最大値で最小値minの値を更新する。また、relの集合に含まれる値のうち少なくとも一つが最小値minより大きい場合は該当のrelの値を更新しない。
【００７１】
relの集合ごとにステップＳ３０４〜Ｓ３０７の処理を行ったあと、最小値、最大値計算機能２０４はステップＳ３０８に進み、relの集合ごとにステップＳ３０９〜Ｓ３１４の処理を行い、以下の条件を満たすかを調べる。
【００７２】
ステップＳ３０９に進み、最小値、最大値計算機能２０４はrelの集合に含まれる値に最小値min≦ｒ≦最大値maxなる値が含まれているかを判定する。relの集合に含まれる値に最小値min≦ｒ≦最大値maxなる値が含まれていなければ、最小値、最大値計算機能２０４はステップＳ３１０に進み、relの各要素と最小値minとの差分を計算して差分が最小のrelの値を求め、relの値をrminとする。
【００７３】
ステップＳ３１１に進み、最小値、最大値計算機能２０４はrelの各要素と最大値maxとの差分を計算して差分が最小のrelの値を求め、relの値をrmaxとする。ステップＳ３１２に進み、最小値、最大値計算機能２０４は（最小値min−rmin）よりも（rmax−最大値max）が小さいかを判定する。
【００７４】
（最小値min−rmin）よりも（rmax−最大値max）が小さければ、最小値、最大値計算機能２０４はステップＳ３１３に進み、最大値maxをrmaxで更新する。また、（最小値min−rmin）よりも（rmax−最大値max）が小さくなければ、最小値、最大値計算機能２０４はステップＳ３１４に進み、最小値minをrminで更新する。
【００７５】
なお、最小値、最大値計算機能２０４はrelの集合に含まれる値に最小値min≦ｒ≦最大値maxなる値が含まれていれば、最大値max又は最小値minの更新を行わない。relの集合ごとに行うステップＳ３０９〜Ｓ３１４は、relの集合に最小値minから最大値maxの範囲に該当する値が含まれていない場合に行われる。
【００７６】
relの集合ごとに行うステップＳ３０９〜Ｓ３１４は、relのうち最小値minないし最大値maxに一番近い値を選択し、選択したrelが最小値minに近い値の場合、そのrelの値で最小値minの値を更新し、選択したrelが最大値maxに近い値の場合、そのrelの値で最大値maxの値を更新するものである。
【００７７】
（全体処理フロー）
本実施例のパターン抽出装置１は、図６の冗長パターン削除処理を実行した後、図８のワイルドカード決定処理を行う。また、別の実施例として、パターン抽出装置１は冗長パターン削除処理とワイルドカード決定処理とを交互に連続して実行しながら、パターン長がより長いパターンを取得していくようにしてもよい。
【００７８】
図１０は冗長パターン削除処理とワイルドカード決定処理とを交互に連続して実行しながらパターン長がより長いパターンを取得していく一例の全体処理フローである。
【００７９】
ステップＳ１に進み、パターン生成部２１はパターン長ｋに１を代入する。ステップＳ２に進み、パターン生成部２１はシーケンス表保存部３１から図１に表したシーケンスを読み出し、既知の方法でパターン長ｋのパターンを生成する。
【００８０】
ステップＳ３に進み、シーケンス集合表生成部２２はパターン長ｋのパターンが存在するか（ステップＳ２で生成されたか）を判定する。パターン長ｋのパターンが存在しなければ、シーケンス集合表生成部２２は全体処理フローを終了する。
【００８１】
パターン長ｋのパターンが存在すれば、パターン抽出装置１はステップＳ４に進み、パターン長ｋのパターンに対し、図１１に示す冗長パターン削除処理を実行する。図１１は冗長パターン削除処理の手順を示す他の例のフローチャートである。なお、図１１のフローチャートは、図６のフローチャートと一部を除いて同様であるため、適宜説明を省略する。
【００８２】
ステップＳ４０１に進み、シーケンス集合表生成部２２はパターン長ｋのパターンをシーケンス集合表１００に保存する。ステップＳ４０２以降の処理は図６のステップＳ１０２以降の処理をパターン長ｋのパターンに限定したものであり、説明を省略する。
【００８３】
図１０のステップＳ５に進み、ワイルドカード決定部２５はパターン長ｋのパターンに対し、図８に示したワイルドカード決定処理を実行する。そして、パターン生成部２１はステップＳ６に進み、パターン長ｋに１を加算（ｋ←ｋ＋１）したあと、ステップＳ２に戻り処理を続ける。
【００８４】
図１０の全体処理フローはパターン長ｋを１から順に増やしながら、パターン長ｋに対応するパターンが存在しなくなるまで繰り返される。図１０の全体処理フローは、あるパターン長ｋのパターンに対して、図６に示した冗長パターン削除処理をパターン長ｋに限定した図１１の冗長パターン削除処理を実行した後、図８に示したワイルドカード決定処理を実行するものである。
【実施例１】
【００８５】
図５に示すシーケンス集合表１００はパターン長ｋ＝３のパターンとして、
<f-x(0,3)-s-x(0,2)-k> (1,4,5,7,9,10)
<f-x(0,3)-s-x(0,0)-k> (4,5,7,9,10)
<f-x(0,3)-s-x(0,1)-k> (1,4,5,7,9,10)
<f-x(0,3)-s-x(1,4)-a> (1,4,5,7,10)
の４つのパターンと、パターンにマッチするシーケンスＩＤとを保持している。上記４つのパターンにはパターン内のアルファベットの並びがf,s,kのパターンとf,s,aのパターンとが含まれる。４つのパターンのうち、アルファベットの並びがf,s,kのパターンである<f-x(0,3)-s-x(0,2)-k>、<f-x(0,3)-s-x(0,0)-k>、<f-x(0,3)-s-x(0,1)-k>のシーケンス集合は(4,5,7,9,10)又は (1,4,5,7,9,10)である。
【００８６】
シーケンス集合(4,5,7,9,10)と(1,4,5,7,9,10)との関係は{4,5,7,9,10}⊂{1,4,5,7,9,10}である。つまり、シーケンス集合{4,5,7,9,10}はシーケンス集合{1,4,5,7,9,10}の真部分集合である。シーケンス集合{4,5,7,9,10}に対応するパターン<f-x(0,3)-s-x(0,0)-k>は削除対象パターン表１０４に記録され、最終的にシーケンス集合表１００から削除される。このようにパターン<f-x(0,3)-s-x(0,0)-k>は他のパターン(<f-x(0,3)-s-x(0,2)-k>ないし<f-x(0,3)-s-x(0,1)-k>)により代表されることが分かるため、冗長をなくするために削除される。
【００８７】
また、図７に示すＰＤＢ２００はパターン長ｋ＝３のパターン<f-x(0,2)-s-x(0,2)-k>が存在し、図１のシーケンス表を対象とするとき、各シーケンスＩＤに対応する、最右端アルファベットの右隣位置を記録したものである。なお、シーケンスＩＤ＝５のように複数のマッチの仕方が存在する場合は、同一のシーケンスＩＤの行が複数発生する。図７に示すＰＤＢ２０１はパターン<f-x(0,2)-s-x(0,2)-k>の元になっているパターン長＝２のパターン<f-x(0,2)-s>が存在し、図１のシーケンス表を対象とするとき、各シーケンスＩＤに対応する、最右端アルファベットの右隣位置を記録したものである。
【００８８】
ＰＤＢ２００及び２０１の同一のシーケンスＩＤにおいて、ＰＤＢ２０１の最右端アルファベットの右隣位置からＰＤＢ２００の最右端アルファベットの右隣位置を引き、さらに１を引いた値はギャップ、つまり、ＰＤＢ２００の最右端アルファベットの右隣位置からアルファベット"k"にマッチする位置までずれるのに要した量になる。このギャップはワイルドカードの長さとなり、差分集合表２０３に差分としてシーケンスＩＤごとに格納される。例えば図７に示す差分集合表２０３のシーケンスＩＤ＝５の場合は差分として二通りの値０，２が格納される。
【００８９】
図７に示す差分集合表２０３の場合は、先に、シーケンスＩＤごとに格納される差分の集合のうち、１個の値を含む差分の集合を用いて、差分の最小値と最大値を計算すると最小値=０、最大値=１となる。さらに、図７に示す差分集合表２０３の場合は、シーケンスＩＤ＝５に対応する差分の集合が２個の値０，２を含んでいる。
【００９０】
さらに、シーケンスＩＤ＝５の結果を考慮するときは、差分の値０，２のどちらを選択しても同じ結果が得られる。しかし、差分の値２を選択するとワイルドカードの幅が広がるのに対し、差分の差０を選択するとワイルドカードの幅が同じであるので、シーケンスＩＤ＝５に対応する差分は０が採用される。
【００９１】
したがって、パターン<f-x(0,2)-s-x(0,2)-k>の一番右のワイルドカードはx(0,1)で十分であることが分かり、<f-x(0,2)-s-x(0,1)-k>に置き換えられる。
【００９２】
ワイルドカード決定処理の別の例として、図７に示した差分集合表２０３の代わりに図１２の差分集合表３００のときの処理を説明する。まず、差分集合表３００に１回のみ現れる（差分の集合の要素が１個のみの）シーケンスＩＤは表３０１に示すように３，４である。シーケンスＩＤが３，４の差分の集合における最小値minと最大値maxは１と２である。つまり、図１２に示す差分集合表３００は、シーケンスＩＤが３と４の場合をすべて満たすワイルドカードがx(1,2)である。
【００９３】
次に差分集合表３００に２回以上現れる（差分の集合の要素が２個以上の）シーケンスＩＤは表３０２に示すように０、１、２である。表３０２のうち、差分の集合がすべて最大値max＝２より大きいシーケンスＩＤは、表３０３に示すように、２である。このときワイルドカードx(1,2)の範囲をなるべく広くせず、かつ、シーケンスＩＤが２の場合を満たすには、差分の集合のうち最小値(3)をもって最大値maxを更新する。つまりワイルドカードx(1,3)はシーケンスＩＤが２、３、４の場合を満たす。なお、差分の集合がすべて最小値minより小さいシーケンスＩＤは存在しない。
【００９４】
次に差分集合表３００に２回以上現れ、最小値min≦r≦最大値maxなるrを含まないシーケンスＩＤは表３０４に示すように０である。シーケンスＩＤ１は、差分の集合に２と３を含んでいるのでワイルドカードx(1,3)に該当する。シーケンスＩＤ２は、差分の集合に３を含んでいるのでワイルドカードx(1,3)に該当する。このように、シーケンスＩＤ１、２はワイルドカードをこれ以上広くする必要がない。
【００９５】
しかし、シーケンスＩＤ０は表３０４に示すように、ワイルドカードx(1,3)に該当しない差分の集合０、５を持つので、どちらかを含むようにワイルドカードx(1,3)を広げる必要がある。このとき最小値minを小さくして０にするとワイルドカードは表３０５に示すように１広くなる。一方、最大値maxを大きくして５にするとワイルドカードは表３０６に示すように２広くなる。
【００９６】
そのため、ワイルドカードは、シーケンスＩＤ０から４の全てを満たし、且つ、より狭くなるように、最小値min=０、最大値max=３に更新される。以上により、差分集合表３００では、ワイルドカードをx(0,3)に置き換えればいいことが分かる。
【００９７】
（まとめ）
本実施例によれば、結果として得られるパターンの数を抑制することができ、無駄なパターンを削減することができる。例えば図１のデータにおいて（両者とも長さ２〜４のパターンに対して）、新Modified PrefixSpan法では図１３に示すように３５パターン抽出する。本実施例では図１４に示すように２４パターン抽出する。このように、本実施例は新Modified PrefixSpan法と比較して、無駄なパターンを削減できる。また、本実施例では可変長ワイルドカードの幅が最小のパターンを得られる。上記の効果により、本実施例は発見したパターンを用いて行う、後段の処理での計算量削減が期待できる。なお、図１３及び図１４の最大支持数、最大ワイルドカード数及び最大誤差数は、上記した非特許文献２において説明されている。
【００９８】
本実施例は、モチーフを発見する技法である可変長ワイルドカードを用いた"PrefixSpan法"で複数生成されるパターン間の重複を除去したあと、ＰＤＢを用いて最小幅のワイルドカードを持つパターンを抽出するものである。
【００９９】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１００】
１    パターン抽出装置
２    ユーザ端末
３    ネットワーク
１１    入力装置
１２    出力装置
１３    ドライブ装置
１４    補助記憶装置
１５    主記憶装置
１６    演算処理装置
１７    インターフェース装置
１８    記録媒体
２１    パターン生成部
２２    シーケンス集合表生成部
２３    パターン集合表生成部
２４    冗長パターン削除部
２５    ワイルドカード決定部
３１    シーケンス表保存部
３２    シーケンス集合表保存部
３３    パターン集合表保存部
３４    削除対象パターン表保存部
３５    代表パターン表保存部
３６    ＰＤＢ（射影データベース）保存部
３７    差分集合表保存部
１００    シーケンス集合表
１０１    アルファベット抽出機能
１０２    パターン集合表
１０３    真部分集合かの判断機能
１０４    削除対象パターン表
１０５    代表パターン表
１０６    パターン削除機能
２００，２０１    ＰＤＢ（射影データベース）
２０２    差分計算機能
２０３    差分集合表
２０４    最小値、最大値計算機能
３０１〜３０６    表
Ｂ    バス
【図１】
2011086252.tif 000003
【図２】
2011086252.tif 000004
【図３】
2011086252.tif 000005
【図４】
2011086252.tif 000006
【図５】
2011086252.tif 000007
【図６】
2011086252.tif 000008
【図７】
2011086252.tif 000009
【図８】
2011086252.tif 000010
【図９】
2011086252.tif 000011
【図１０】
2011086252.tif 000012
【図１１】
2011086252.tif 000013
【図１２】
2011086252.tif 000014
【図１３】
2011086252.tif 000015
【図１４】
2011086252.tif 000016