(57)【要約】【課題】状態列パターンの中から上記意外性の高いパターンを抽出し、出力できるようにすること。【解決手段】状態列パターンを作成し、状態列パターン・データベース７に登録する。データベース内度数ｐ（ｓ）の計算部２は、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する状態列パターンｓの出現頻度の比を求める。想定度数計算部３は、所定の確率分布の下で、状態列パターンｓについて、要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率である想定度数ｑ（ｓ）を計算する。意外性尺度の計算部４は、データベース内度数ｐ（ｓ）と想定度数ｑ（ｓ）と、部分パターン集合Ｔ〔ｓ〕内での要素ｔ∈Ｔ〔ｓ〕の相対出現頻度に基づき意外性の尺度Ｉ（ｓ）を求める。この結果は評価部５で評価され、出力処理部６で処理され出力装置９から出力される。【選択図】          図１
2004178515.tif 000002
【特許請求の範囲】
【請求項１】
分析対象となる状態列パターンを保持する状態列パターン・データベースと、
上記状態列パターン・データベースにおける、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比であるデータベース内度数ｐ（ｓ）の計算部と、
上記状態列パターンｓに関して、所定の確率分布の下で、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率である想定度数ｑ（ｓ）を計算する想定度数の計算部と、
部分パターン集合Ｔ〔ｓ〕内での上記要素ｔ∈Ｔ〔ｓ〕の相対出現頻度を求め、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の関数Ｊを、上記相対出現頻度に基づき求める意外性の尺度の計算部と、
上記意外性の尺度の計算部で計算した意外性の尺度に基づき、状態列パターン・データベースに蓄積された状態列パターンの意外性の高さを評価する評価部と、
上記評価部における評価結果を出力する出力処理部を備えた
ことを特徴とする意外性に基づく状態列パターンの評価装置。
【請求項２】
状態列パターン生成部を備え、
上記状態列パターン生成部により、入力装置から入力された状態列データから状態列の部分列を生成し、
状態列パターンとして状態列パターン・データベースに登録する
ことを特徴とする請求項１の意外性に基づく状態列パターンの評価装置。
【請求項３】
上記状態列パターンの評価部は、状態列パターン・データベース内の状態列パターン群を意外性の尺度の値に基づいて順位付けし、意外性の尺度に関する所定の順位条件を満たす状態列パターン群を選択する
ことを特徴とする請求項１または請求項２の意外性に基づく状態列パターンの評価装置。
【請求項４】
状態列パターンの類似度の計算部を備え、
上記類似度の計算部は、状態列パターン・データベース内の状態列パターン群について、意外性の尺度の値、および状態列パターンの類似度が所定の範囲内にあるパターン群どうしをグループ化する
ことを特徴とする請求項１または請求項２の意外性に基づく状態列パターンの評価装置。
【請求項５】
状態列パターン・データベースに保持された状態列パターンについて、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比であるデータベース内度数ｐ（ｓ）の計算する処理と、
上記状態列パターンｓに関して、所定の確率分布の下で、上記状態列パターンｓについて、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率（出現するし易さ）である想定度数ｑ（ｓ）を計算する想定度数を計算する処理と、
部分パターン集合Ｔ〔ｓ〕内での上記要素ｔ∈Ｔ〔ｓ〕の相対出現頻度を求め、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の関数Ｊを、上記相対出現頻度に基づき平均化した意外性の尺度を計算する処理と、
上記意外性の尺度の計算部で計算した意外性の尺度に基づき、状態列パターン・データベースに蓄積された状態列パターンの意外性の高さを評価する処理を、コンピュータに実行させる
ことを特徴とする状態列パターンの評価プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、顧客の購買履歴、Ｗｅｂアクセス・ログ、株価や気温の時系列データといった状態列データの分析を行い評価するための評価装置に関し、特に、分析対象となる状態列パターンの意外性の高さを評価する意外性に基づく状態列パターンの評価装置に関する。
【０００２】
【従来の技術】
顧客の購買履歴データベース等の状態列データベースから特徴的なパターン（  状態列の部分列）  を発見する方法として、従来から、所定値（最小サポート値）以上の頻度で出現するパターンを選ぶという種々の「頻出パターン抽出法」が提唱されている（例えば非特許文献１，２，３等参照）。
また、その外、数値属性から例外ルールを発見する手法として、例えば非特許文献４に記載されるものが提唱されている。
【０００３】
【非特許文献１】
Ｒａｋｅｓｈ  Ａｇｒａｗａｌ，Ｔｏｍａｓｚ  Ｉｍｉｅｌｉｎｓｋｉ，ａｎｄ  Ａｒｕｎ  Ｓｗａｍｉ：”Ｍｉｎｉｎｇ  ａｓｓｏｃｉａｔｉｏｎ  ｒｕｌｅｓ  ｂｅｔｗｅｅｎ  ｓｅｔｓ  ｏｆ  ｉｔｅｍｓ  ｉｎ  ｌａｒｇｅ  ｄａｔａｂａｓｅｓ”．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＭＯＤ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｎａｇｅｍｅｎｔ  ｏｆ  Ｄａｔａ，  ｐｐ．２０７−２１６，１９９３．
【非特許文献２】
Ｒａｋｅｓｈ  Ａｇｒａｗａｌ  ａｎｄ  Ｒａｍａｋｒｉｓｈｎａｎ  Ｓｒｉｋａｎｔ：”Ｆａｓｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｍｉｎｉｎｇ  ａｓｓｏｃｉａｔｉｏｎ  ｒｕｌｅｓ”．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ，  ｐｐ．４８７−４９９，１９９４．
【非特許文献３】
Ｒａｋｅｓｈ  Ａｇｒａｗａｌ  ａｎｄ  Ｒａｍａｋｒｉｓｈｎａｎ  Ｓｒｉｋａｎｔ：”Ｍｉｎｉｎｇ  ｓｅｑｕｅｎｔｉａｌ  ｐａｔｔｅｒｎｓ  ”．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ，１９９５．
【非特許文献４】
湯上伸弘，  岡本青史著：”数値属性からの例外ルールの発見”，人工知能学会誌ｖｏｌ．１５，ｎｏ．６，  ｐｐ１０８１−１０８８，  ２０００．
【０００４】
【発明が解決しようとする課題】
上記頻出パターン抽出法の問題点として、最小サポート値を小さめに設定した場合、人間が把握しきれないほどの膨大な数（例えば数千、数万以上）のパターンが抽出されたり、また逆に、人手で把握できる程度のパターン数になるまでサポート値を上げた場合、出現頻度について意外性の高いパターンの中で最小サポート値に満たないものが見落とされる可能性が高まる。
また、従来法では、パターンの長さの違いによる出現し易さ／しにくさが考慮されにくい。例えば、長さ３のパターンの出現頻度２５％と、長さ６のパターンの出現頻度１０％との比較が考慮されにくい。
また、上記の「頻出パターン抽出法」では、個々の状態の出現頻度情報等から前もって頻出であることが予想されるパターンと、予想外に頻度が高いパターンとは区別されない。
【０００５】
そこで、単に頻出のパターンを抽出するのではなく、パターンに関する所定の特性（出現頻度等）  について意外性の高いパターンを抽出することが望まれる。
ここで、出現頻度について意外性の高いパターンとは、パターンの個々の要素や部分パターンとしては出現頻度が低いにもかかわらず、そのパターンで出現する場合の頻度が高いパターン、あるいは逆に、パターンの個々の要素や部分パターンとしては出現頻度が高いにもかかわらず、そのパターンで出現する場合の頻度が低いパターンのことである。
意外性の高いパターンの発見は、購買履歴等の顧客行動履歴の中から、単なる頻出パターン分析では見つからないような顧客の潜在的な要求や不満を発見することに役立つ。
本発明は上記事情に鑑みなされたものであって、本発明の目的は、状態列パターンの中から上記意外性の高いパターンを抽出し出力できるようにするとともに、パターン長によるパターンの出現しやすさ／しにくさを考慮してパターンの意外性の尺度を定義することにより、様々な長さの状態列パターンを一括して取り扱うことができるようにすることである。
【０００６】
【課題を解決するための手段】
本発明の状態列パターンの評価装置は、図１に示すように、分析対象となる状態列パターンを保持する状態列パターン・データベース７と、状態列パターン・データベース７に格納されている状態列パターンデータのデータベース内度数ｐ（ｓ）を計算する計算部２と、上記状態列パターンに関して、想定度数ｑ（ｓ）を計算する想定度数の計算部３と、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）に基づき意外性の尺度Ｉ（ｓ）を計算する計算部４と、意外性の尺度の計算部４で計算した意外性の尺度Ｉ（ｓ）に基づき、状態列パターン・データベースに蓄積された状態列パターンの意外性の高さを評価する評価部５と、評価部５における評価結果を出力する出力処理部６を備えており、システム全体は処理制御部１で制御される。
【０００７】
上記状態列パターンの意外性を評価する際に用いる出現頻度等の、状態列パターンに関する特性、その特性に対するデータベース内度数、その特性に関する想定度数、あるいは意外性の尺度は、定義可能な範囲で、ユーザーの便宜に基づく任意の形式で定義することができる。
上記状態列パターンに関する特性、この特性に対するデータベース内度数、その特性に関する想定度数、意外性の尺度は、例えば、以下のように定義される。
（ｉ）  状態列パターンに関するの特性：
ターゲット状態ｓｘ  に続く状態列パターンの出現し易さ。例えば、ターゲット状態ｓｘ  を”Ａ”とすると、Ａに続く、ある状態列パターンＢ，Ｃ，Ｄの出現のし易さ。
（ｉｉ）上記特性に対するデータベース内度数：
上記ターゲット状態ｓｘ  に続く状態列パターンのデータベース内での出現頻度。
（ｉｉｉ）  上記特性に関する想定度数：
上記ターゲット状態ｓｘ  に続く状態列パターンの長さが、所定のパラメータの所定の確率分布（例えば平均長１０のポアソン分布）に従うものとすると、その状態列パターン上に各状態｛ｓｉ  ｝が頻度ｆ（ｓｉ  ）でランダムに（あるいはユーザが定めた所定の確率分布で）出現するとした場合の確率分布。なお、上記想定度数は、上記のように所定の条件のもとに計算されるので、条件付きの確率分布となる。
（ｉｖ）意外性の尺度：
上記特性に関するデータベース内度数とその特性に関する想定度数との相対エントロピー。
本発明では、このような定義の下で、各状態列パターンの意外性の尺度を計算し、その評価結果として、状態列パターンを意外性の尺度の順に並べ替えるなどして出力する。
【０００８】
例えば、上記状態列パターンは、顧客の購買履歴であり、顧客があるものＡを買って、次にＢ，Ｃを買うと、Ａ：Ｂ：Ｃのデータが購買履歴として保存される。このように顧客毎にデータを収集する。
そして、状態列パターンを作成し、状態列パターン・データベース７に格納する。すなわち、顧客毎の状態列パターンから各顧客のパターン、頻度、パターンを構成する要素の相対出現頻度を得て、これらを状態列パターン・データベース７に格納する。
そして、データベース内度数ｐ（ｓ）の計算部２で、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比を求め、また、想定度数の計算部３で、所定の確率分布の下で、上記状態列パターンｓについて、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率である想定度数ｑ（ｓ）を計算する。さらに、部分パターン集合Ｔ〔ｓ〕内での上記要素ｔ∈Ｔ〔ｓ〕の相対出現頻度を求める。
そして、意外性の尺度の計算部４で、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の関数Ｊ（例えばｐ（ｓ）と、想定度数ｑ（ｓ）の比をパラメータとした関数）を、上記相対出現頻度に基づき求めて、意外性の尺度Ｉ（ｓ）を求める。
すなわち、状態列パターン・データベース７内に保持されたあるパターンのデータベース内度数ｐ（ｓ）と、所定の確率分布に基づき求めたあるパターンの想定度数ｑ（ｓ）との相対関係（例えばＰ（ｓ）とｑ（ｓ）との比等）から意外性の尺度Ｉ（ｓ）を求める。
上記において、状態列パターン生成部を設けて、入力装置から入力された状態列データから状態列の部分列を生成し、状態列パターン・データベース７に登録するようにしてもよい。
上記のようにして求めた意外性の尺度に基づき、評価部５では、状態列パターン・データベースに蓄積された状態列パターンを並べ替える等して、意外性の高さを評価する。
また、意外性の尺度に基づき、評価部５で、以下のような評価を行い、出力処理部６から出力するようにしてもよい。
（１）状態列パターン・データベース内の状態列パターン群の中から、意外性の尺度の値が所定の条件を満たす状態列パターン群を選択する。
（２）状態列パターン・データベース内の状態列パターン群を意外性の尺度の値に基づいて順位付けし、意外性の尺度に関する所定の順位条件を満たす状態列パターン群を選択する。
さらに、状態列パターンの類似度を計算する計算部を設け、意外性の尺度の値、および状態列パターンの類似度が所定の範囲内にあるパターン群同士をグループ化してもよい。
【０００９】
【発明の実施の形態】
図１は本発明の第１の実施例のシステムの構成を示す図である。
図１において、１は制御処理部でありシステム全体を制御する。２はデータベース内度数の計算部であり、状態列パターン・データベース７に格納された状態列パターンデータについて、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比であるデータベース内度数を計算する。３は想定度数の計算部であり、所定の確率分布の下で、上記状態列パターンｓについて、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率である想定度数を計算する。
４は意外性の尺度計算部であり、上記データベース内度数と、想定度数に基づき意外性の尺度を計算する。
５は状態列パターンの評価部であり、上記意外性の尺度計算部４の計算結果に基づき、状態列パターンを評価する。評価結果は、評価結果の出力処理部６で処理されたのち、出力装置９を介して出力される。また、入力装置８が設けられ、ここから、状態列パターンデータを入力したり、システムの操作を行う。
【００１０】
状態列パターン・データベース７には、図２に示すように、状態列パターンとその出現頻度（図２（ａ））、および、状態とその相対出現頻度（図２（ｂ））が登録されている。図２の状態列パターンは、１３種類のＡ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ，Ｉ，Ｊ，Ｋ，Ｌ，Ｍを要素としており、パターンＡ，Ｂ，Ｃがこの順番に出現したことを示している。例えば、図２（ａ）における「Ａ：Ｂ，９」は、Ａという状態の次にＢという状態が９回発生したことを示している。
前記したようにこのデータが顧客の購買履歴である場合には、上記「Ａ：Ｂ，９」は、例えばＡを購入した後、Ｂを購入した顧客が９人いたことを示し、同様に、「Ａ：Ｂ：Ｃ，６」はＡを購入した後にＢを購入し、さらにＣを購入した顧客が６人いたことを示している。
また、例えば、図２（ｂ）における「Ａ，０．２１」は、状態列パターン・データベース７のデータ中に状態Ａが現れる相対出現頻度が０．２１であることを示している。なお、この相対出現頻度を以下では、ｆ（ｓｉ  ）と表記し、この場合の状態Ａの相対出現頻度はｆ（Ａ）＝０．２１である。この相対出現頻度は、後述する想定頻度等を計算する際に使用される。
上記状態列パターン・データベース７の状態列パターン・データは、後述するように入力装置等から購買履歴等の状態列データを読み込み、これを処理して状態列パターンを生成するとともに出現頻度、相対頻度を求めることにより作成される。
【００１１】
本実施例では、前記状態パターンｓの特性、データベース内度数ｐｔ  （ｓ）、想定度数ｑｔ  （ｓ）、意外性の尺度Ｉ（ｓ）を以下のように定義する。
（ｉ）  状態パターンｓの特性：
状態パターンｓから長さ１だけ短い部分パターンで構成される集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕が出現したときのｓの出現のし易さ。
（ｉｉ）データベース内度数ｐｔ  （ｓ）：
状態列パターン・データベース７内の集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度と、状態パターンｓの出現頻度の比。
（ｉｉｉ）  想定度数ｑｔ  （ｓ）：
長さ１０の状態列上に、各状態が状態列パターン・データベース７内での相対出現頻度〔前記ｆ（ｓｉ）〕でランダムに出現するとして、ある状態列上に前記要素ｔを構成する状態群が、要素ｔと同じ順番に出現したときに、その状態列の残りの部分に、状態列パターンｓから要素ｔを取り除いた差分ｓ｜ｔ（ここでは差分を｜で表記する）を構成する状態群が、状態列パターンｓと同じ順番になるように出現する確率。
（ｉｖ）意外性の尺度Ｉ（ｓ）：
以下の（１）式に示すように、データベース内度数ｐｔ  （ｓ）および想定度数ｑｔ  （ｓ）の比の対数を、Ｔ〔ｓ〕内での要素ｔの相対出現頻度ｆ（ｔ）に基づいて平均を取ったもの。
【００１２】
【数１】
2004178515.tif 000003
【００１３】
図３は本実施例の評価装置の処理フローである。以下、図３を参照しながら本実施例の処理について説明する。
（１）  状態列パターン・データベース７から状態列パターンのデータを読み込む（図３のステップＳ１）
状態列パターン・データベース７には、図２に示したように、状態列パターンとその出現頻度（ａ）、状態の相対出現頻度ｆ（ｓｉ  ）が登録されている。意外性の尺度を計算するためこのデータを読み込む。
【００１４】
（２）  データベース内度数計算部３で、データベース内度数を計算する（ステップＳ２）。
例えば、状態列パターンｓ＝Ａ：Ｂ：Ｃ：Ｄについて考えると、このパターンに対する長さが１だけ短い部分パターン集合Ｔ〔ｓ〕は、Ａ：Ｂ：Ｃ，Ａ：Ｂ：Ｄ，Ａ：Ｃ：Ｄ，Ｂ：Ｃ：Ｄの４種類で構成される。
このパターンｓ＝Ａ：Ｂ：Ｃ：Ｄについて、上記部分パターンに対する出現頻度（データベース内度数ｐｔ  （Ａ：Ｂ：Ｃ：Ｄ））を求めると、図２（ａ）のデータから以下のように求まる。
・部分パターンＡ：Ｂ：Ｃに対するＡ：Ｂ：Ｃ：Ｄの出現頻度の比：ｐＤ  （Ａ：Ｂ：Ｃ：Ｄ）＝３／６
・部分パターンＡ：Ｂ：Ｄに対するＡ：Ｂ：Ｃ：Ｄの出現頻度の比：ｐｃ  （Ａ：Ｂ：Ｃ：Ｄ）＝３／６
・部分パターンＡ：Ｃ：Ｄに対するＡ：Ｂ：Ｃ：Ｄの出現頻度の比：ｐＢ  （Ａ：Ｂ：Ｃ：Ｄ）＝３／５
・部分パターンＢ：Ｃ：Ｄに対するＡ：Ｂ：Ｃ：Ｄの出現頻度の比：ｐＡ  （Ａ：Ｂ：Ｃ：Ｄ）＝３／５
【００１５】
（ｉｉｉ）  想定度数の計算部３で想定度数を計算する（ステップＳ３）。
次に、想定度数を計算するために、長さ１０の状態列ｓ＝ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ｘ７，ｘ８，ｘ９，ｘ１０を想定する。この状態列上に、例えば部分パターンｔ＝Ａ：Ｂ：Ｃが出現している（例えば、ｘ１，Ａ，ｘ３，ｘ４，ｘ５，Ｂ，ｘ７，Ｃ，ｘ９，ｘ１０）とき、パターンｓ＝Ａ：Ｂ：Ｃ：Ｄも出現するには、状態列上のｔ＝Ａ：Ｂ：Ｃの後ろに（つまり、”Ｃ”の後ろに）  ｓの残りの部分”Ｄ”が出現しなくてはならない。
長さ１０の状態列のうちの３箇所が、ｘ１，Ａ，ｘ３，ｘ４，ｘ５，Ｂ，ｘ７，Ｃ，ｘ９，ｘ１０のように、所定の状態群で埋まっているとき、状態列上で３つの状態群で分割される４箇所の部分列（つまり、”Ａ”の前、”Ａ”と”Ｂ”の間、”Ｂ”と”Ｃ”の間、”Ｃ”の後ろ）  の平均長は以下の（２）式で計算される。
【００１６】
【数２】
2004178515.tif 000004
【００１７】
このとき、”Ｃ”の後ろの部分列（平均長７／４）に、状態”Ｄ”が出現する確率（条件付き確率）は、状態列上に１３種類の状態がランダムに出現するとして、以下の（３）式で計算される。
【００１８】
【数３】
2004178515.tif 000005
【００１９】
ここで、上記０．０９は、前記図２のデータ（ｂ）における”Ｄ”の相対出現頻度である。なお、上記のように相対出現頻度を用いる代わりに、ユーザが適宜定めた確率分布に基づくものであってもよく、また、状態が「ランダム」に出現するとする代わりに、ユーザが適宜定めた所定の確率分布に基づいて出現するとしてもよい。
同様に、長さ１０の状態列上に、以下の部分パターンが出現したときにＡ：Ｂ：Ｃ：Ｄも出現する確率ｑｔ  （ｓ）（想定度数）を計算する。
・部分パターンＡ：Ｂ：Ｄが出現したときにＡ：Ｂ：Ｃ：Ｄも出現する確率＝ｑｃ  （Ａ：Ｂ：Ｃ：Ｄ）
・部分パターンＡ：Ｃ：Ｄが出現したときにＡ：Ｂ：Ｃ：Ｄも出現する確率＝ｑＢ  （Ａ：Ｂ：Ｃ：Ｄ）
・部分パターンＢ：Ｃ：Ｄが出現したときにＡ：Ｂ：Ｃ：Ｄも出現する確率＝ｑＡ  （Ａ：Ｂ：Ｃ：Ｄ）
また、以下の（４）式に示すＴ〔ｓ〕内での部分パターンＡ：Ｂ：Ｃの相対出現頻度ｆ（Ａ：Ｂ：Ｃ）を計算し、同様に、部分パターンＡ：Ｂ：Ｄ，Ａ：Ｃ：Ｄ、Ｂ：Ｃ：Ｄの相対出現頻度ｆ（Ａ：Ｂ：Ｄ），ｆ（Ａ：Ｃ：Ｄ），ｆ（Ｂ：Ｃ：Ｄ）も計算する。
【００２０】
【数４】
2004178515.tif 000006
【００２１】
（ｉｖ）意外性の尺度を意外性の尺度計算部４で計算する（ステップＳ４）。
上記のように求めたデータベース内度数ｐｔ  （ｓ）、想定度数ｑｔ  （ｓ）、相対出現頻度ｆ（ｔ）に基づき、前記（１）式により意外性の尺度Ｉ（ｓ）を計算する。
すなわち、各ｔについて、ｐｔ  （ｓ），ｑｔ  （ｓ）の比の対数を求め、相対出現頻度ｆ（ｔ）を乗じてその総和を求めることにより意外性の尺度Ｉ（ｓ）を求めることができる。
さらに、状態列のデータベース７内の他の状態列パターン（例えば長さが３以上）についても同様の手順で意外性の尺度を計算する。
なお、意外性の尺度Ｉ（ｓ）を求める計算式としては（１）式以外に例えば、以下の（５）（６）式を用いるなど、その他の式により求めることもできる。
【００２２】
【数５】
2004178515.tif 000007
【００２３】
（ｉｖ）意外性の尺度に基づき状態列パターンを評価する（ステップＳ５）。
状態列パターン評価部５は、上記のように求めた意外性の尺度Ｉ（ｓ）の順番に状態列パターンを並べる。
（ｖ）  評価結果を出力する（ステップＳ６）。
上記評価部５による評価結果は出力部６から出力される。
図４に、前記図２に示した状態列パターンについて意外性の尺度を求め、順番に並べた場合の出力例を示す。
この評価結果から、例えば以下のことが分かる。
・パターンＡ：Ｃ：Ｅ：Ｆは、その部分パターンＡ：Ｃ：Ｅ、Ａ：Ｃ：Ｆ、Ａ：Ｅ：Ｆ、Ｃ：Ｅ：Ｆの出現頻度、および、個々の状態Ａ、Ｃ、Ｅ、Ｆの出現頻度と比較すると、出現頻度が意外に多い。
・パターンＨ：Ａ：Ｃは、その部分パターンＨ：Ａ、Ｈ：Ｃ、Ａ：Ｃの出現頻度、および、個々の状態Ｈ、Ａ、Ｃの出現頻度と比較すると、出現頻度が意外に少ない。
【００２４】
次に本発明の第２の実施例について説明する。
図２に示した状態列パターン・データベース７の例は、サイズ（状態列パターンの数）  が小さいので、データベース７に属する状態列パターン全部について意外性の評価結果を図４に示したように出力しても、容易に読み取ることができる。しかし、データベース内の状態列パターンの数が膨大な場合、その意外性の評価結果をすべて出力すると、読み取ることが困難である。
そこで、本実施例では、意外性の尺度Ｉ（ｓ）の値について所定の条件を設定し、その条件を満たす状態列パターンのみを出力することとする。
例えば、前記図４における評価結果について、以下の条件を満たす状態列パターンを出力すると、図５に示すようになる。
Ｉ（ｓ）≧０．５あるいはＩ（ｓ）≦−０．５
これにより、状態列パターンの数が膨大な場合であっても、評価結果を容易に読み取ることができる。
【００２５】
次に本発明の第３の実施例について説明する。
上記第２の実施例のように、状態列パターンを出力する条件を意外性の尺度の値に対して設定する代わりに、意外性の尺度に関する順位に対して設定することも可能である。
例えば、意外性の尺度に関する順位の上位４件および下位４件を出力することとすれば、前記図４の場合には、図６に示すような評価結果が得られる。
【００２６】
次に本発明の第４の実施例について説明する。
状態列パターン・データベース７内に、互いにパターンの形状が似ているもの（例えば、Ａ：Ｃ：Ｆ、Ａ：Ｃ：Ｅ、Ａ：Ｃ：Ｅ：Ｆ等）が多数存在することがある。このような場合には、類似している状態列パターン同士をグループ化して出力すれば、意外性の読み取り結果をさらに読み取り易くすることができる。
そこで、本実施例では、図７に示すように、前記図１の構成に加えて状態列パターンの類似度計算部１１を設けている。
そして、図８のフローチャートに示すように、前記図３のフローチャートのステップＳ４とステップＳ５の間に、状態列パターンの類似度を計算するステップＳ４’を追加し、ここで、状態列パターンの類似度を計算し、ステップＳ５で類似度の計算結果に基づき状態列パターンを評価する。
【００２７】
類似度計算部１１では、意外性の尺度を計算した後に、意外性の尺度、およびパターンの形状について類似度を計算し、状態列パターンの評価部５では、意外性の尺度、およびパターンの形状が互いに類似している状態列パターン同士をグループ化して評価結果を求める。この結果は評価結果の出力処理部６で処理され、出力装置９から出力される。
図９に上記出力結果の例を示す。
同図に示すように、意外性の尺度計算部４で求めたパターン、意外性の尺度（同図（ａ））をグループ化することにより、例えば同図（ｂ）に示す結果が得られる。さらに、場合によっては、同図（ｃ）に示すように、各グループにつき状態列パターンを例えば１つ選んで、グループ単位で出力するようにしてもよい。
【００２８】
次に本発明の第５の実施例について説明する。
上記第１〜第４の実施例では、状態列パターン・データベース７から状態列パターンのデータを読み込んでいるが、代わりに、顧客の購買履歴等の状態列データを入力装置から読み込み、その状態列から所定の条件で状態列パターンを生成し、それを状態列パターン・データベース７に登録し、それらについて意外性の尺度を計算することも可能である。
図１０に本実施例のシステムの構成を示し、図１１に本実施例の処理フローを示す。
本実施例においては、図１の構成に加えて、状態列パターン生成部１０が設けられており、状態列パターン生成部１０では、入力装置９から入力された状態列データから、状態列パターンデータを生成し、状態列パターン・データベース７に登録する。
【００２９】
上記処理を行うため、本実施例では、図１１に示すように、前記図３に示した処理フローに、ステップＳ０１、ステップＳ０２が追加されており、ステップＳ０１で入力装置から状態列データを読み込み、ステップＳ０２で状態列パターンを生成して、データベースに登録する。その際、前記したように、状態列パターンの出現頻度（図２の（ａ））、および、状態の相対出現頻度を計算して登録する。
例えば、顧客の購買履歴等から、図１２の（ａ）に示す状態列データが得られ、状態列パターン生成部１０は、２つ以上の状態列に出現している長さ２以上の（状態間の跳びを許す）  部分列を生成し、その部分列が出現している状態列の数（これをここでは状態列パターン出現頻度とする）を求めて、図１２の（ｂ）に示すパターン、頻度を出力する。また、前記したように、状態の相対出現頻度を計算する。
上記のようにして生成された状態列パターン・データは、状態列パターン・データベース７に登録され、この状態列パターンデータに基づき、前記したように意外性の尺度が計算される。
【００３０】
（付記１）  分析対象となる状態列パターンを保持する状態列パターン・データベースと、
上記状態列パターン・データベースにおける、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比であるデータベース内度数ｐ（ｓ）の計算部と、
上記状態列パターンｓに関して、所定の確率分布の下で、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率である想定度数ｑ（ｓ）を計算する想定度数の計算部と、
部分パターン集合Ｔ〔ｓ〕内での上記要素ｔ∈Ｔ〔ｓ〕の相対出現頻度を求め、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の関数Ｊを、上記相対出現頻度に基づき求める意外性の尺度の計算部と、
上記意外性の尺度の計算部で計算した意外性の尺度に基づき、状態列パターン・データベースに蓄積された状態列パターンの意外性の高さを評価する評価部と、
上記評価部における評価結果を出力する出力処理部を備えた
ことを特徴とする意外性に基づく状態列パターンの評価装置。
（付記２）  状態列パターン生成部を備え、
上記状態列パターン生成部により、入力装置から入力された状態列データから状態列の部分列を生成し、
状態列パターンとして状態列パターン・データベースに登録する
ことを特徴とする付記１の意外性に基づく状態列パターンの評価装置。
（付記３）  意外性の尺度の計算部で用いる関数Ｊは、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の比をパラメータとした関数である
ことを特徴とする付記１または付記２の意外性に基づく状態列パターンの評価装置。
（付記４）  上記想定度数の計算部は、上記想定度数ｑ（ｓ）を、状態列の各構成要素が、状態列パターン・データベース内での出現頻度に比例する頻度でランダムに出現するとして、ある状態列パターン上に、上記要素ｔ∈Ｔ〔ｓ〕を構成する状態群が上記要素ｔと同じ順番に出現したときに、その状態列の残りの部分に、状態列パターンｓから上記要素ｔを取り除いた差分を構成する状態群が、状態列パターンｓと同じ順番になるように出現する確率として求める
ことを特徴とする付記１，２または付記３の意外性に基づく状態列パターンの評価装置。
（付記５）  上記状態列パターンの評価部は、状態列パターン・データベース内の状態列パターン群の中から、意外性の尺度の値が所定の条件を満たす状態列パターン群を選択する
ことを特徴とする付記１，２または付記３の意外性に基づく状態列パターンの評価装置。
（付記６）  上記状態列パターンの評価部は、状態列パターン・データベース内の状態列パターン群を意外性の尺度の値に基づいて順位付けし、意外性の尺度に関する所定の順位条件を満たす状態列パターン群を選択する
ことを特徴とする付記１，２または付記３の意外性に基づく状態列パターンの評価装置。
（付記７）  状態列パターンの類似度の計算部を備え、
上記類似度の計算部は、状態列パターン・データベース内の状態列パターン群について、意外性の尺度の値、および状態列パターンの類似度が所定の範囲内にあるパターン群どうしをグループ化する
ことを特徴とする付記１，２または付記３の意外性に基づく状態列パターンの評価装置。
（付記８）  状態列パターン・データベースに保持された状態列パターンについて、状態列パターンｓの部分パターン集合Ｔ〔ｓ〕の要素ｔ∈Ｔ〔ｓ〕の出現頻度に対する上記状態列パターンｓの出現頻度の比であるデータベース内度数ｐ（ｓ）の計算する処理と、
上記状態列パターンｓに関して、所定の確率分布の下で、上記状態列パターンｓについて、上記要素ｔ∈Ｔ〔ｓ〕が出現したときにｓが出現する条件付確率（出現するし易さ）である想定度数ｑ（ｓ）を計算する想定度数を計算する処理と、
部分パターン集合Ｔ〔ｓ〕内での上記要素ｔ∈Ｔ〔ｓ〕の相対出現頻度を求め、上記データベース内度数ｐ（ｓ）と、想定度数ｑ（ｓ）の関数Ｊを、上記相対出現頻度に基づき平均化した意外性の尺度を計算する処理と、
上記意外性の尺度の計算部で計算した意外性の尺度に基づき、状態列パターン・データベースに蓄積された状態列パターンの意外性の高さを評価する処理を、コンピュータに実行させる
ことを特徴とする状態列パターンの評価プログラム。
【００３１】
【発明の効果】
以上説明したように、本発明においては、以下の効果を得ることができる。
（１）種々の長さの状態列パターンが混在するデータベースの中から、出現頻度等の所定の特性について、意外性のある状態列パターンを選択して出力することができる。
このため、購買履歴等の顧客行動履歴や、ｗｅｂアクセス・ログ、株価や気温の変動データ等の中から単なる頻出パターン分析では見つからないパターンを発見することができ、これらの分析に資することができる。
（２）入力装置から入力された状態列データから状態列の部分列を生成し、状態列パターンとして状態列パターン・データベースに登録し、これに基づき意外性の尺度を求めることにより、収集したデータから直ちに状態列パターンの分析を行い、評価結果を出力することができる。
（３）意外性の尺度の値が所定の条件を満たす状態列パターン群を選択して出力したり、意外性の尺度の値に基づいて状態列パターンを順位付けし、意外性の尺度に関する所定の順位条件を満たす状態列パターン群を選択して出力したり、さらに、意外性の尺度の値、および状態列パターンの類似度が所定の範囲内にあるパターン群どうしをグループ化して出力することにより、状態列パターンの数が膨大な場合であっても、評価結果を容易に読み取ることが可能となる。
【図面の簡単な説明】
【図１】本発明の第１の実施例の構成を示す図である。
【図２】状態列パターン・データベースに登録されているデータ例を示す図である。
【図３】本発明の第１の実施例の処理フローを示す図である。
【図４】本発明の第１の実施例の評価結果の例を示す図である。
【図５】本発明の第２の実施例の評価結果の例を示す図である。
【図６】本発明の第３の実施例の評価結果の例を示す図である。
【図７】本発明の第４の実施例の構成を示す図である。
【図８】本発明の第４の実施例の処理フローを示す図である。
【図９】本発明の第４の実施例の評価結果の例を示す図である。
【図１０】本発明の第５の実施例の構成を示す図である。
【図１１】本発明の第５の実施例の処理フローを示す図である。
【図１２】第５の実施例において状態列データから生成される状態列パターンの例を示す図である。
【符号の説明】
１    処理制御部
２    データベース内度数の計算部
３    想定度数の計算部
４    意外性の尺度の計算部
５    状態列パターンの評価部
６    評価結果の出力処理部
７    状態列パターン・データベース
８    入力装置
９    出力装置
１０  状態列パターン生成部
１１  状態列パターンの類似度の計算部
【図１】
2004178515.tif 000008
【図２】
2004178515.tif 000009
【図３】
2004178515.tif 000010
【図４】
2004178515.tif 000011
【図５】
2004178515.tif 000012
【図６】
2004178515.tif 000013
【図７】
2004178515.tif 000014
【図８】
2004178515.tif 000015
【図９】
2004178515.tif 000016
【図１０】
2004178515.tif 000017
【図１１】
2004178515.tif 000018
【図１２】
2004178515.tif 000019