(57)【要約】【課題】サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価装置に関し，要素の組で構成されるパターン群について，要素間の関係を表わすのに必要十分なパターンのみを選択することを目的とする。【解決手段】パターン頻度計算部１２が種々のパターンについて状態列データベース２０内の頻度を計算してパターン頻度情報データベース２１に格納し，サブパターン／  スーパーパターン生成部１３が評価対象のパターンＳからサブパターン群とスーパーパターン群を生成し，パターン推定頻度計算部１４がサブパターン，  スーパーパターンの頻度に基づくＳの推定頻度を計算し，パターン有意義度計算部１５が算出された各推定頻度からのＳの実際の頻度の乖離度を計算し，  算出された各乖離度に関する所定の統計値をＳの有意義度として算出し，算出された有意義度に基づいてパターン評価部１６がパターンを評価する。【選択図】        図１
2005004393.tif 000002
【特許請求の範囲】
【請求項１】
サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価装置であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算手段と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成手段と，
前記パターン頻度計算手段により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算手段により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算手段と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算手段と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価手段とを備える
ことを特徴とするパターン評価装置。
【請求項２】
請求項１記載のパターン評価装置において，
前記パターン推定頻度計算手段は，
前記サブパターンの頻度と前記評価対象のパターンから取り除かれた要素の頻度の積を全状態列数で割った値を前記サブパターンについての前記評価対象のパターンの推定頻度として算出し，
前記スーパーパターンの頻度と全状態列数の積を前記評価対象のパターンに追加した要素の頻度で割った値を前記スーパーパターンについての前記評価対象のパターンの推定頻度として算出する
ことを特徴とするパターン評価装置。
【請求項３】
サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価をコンピュータによって行うパターン評価処理方法であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算ステップと，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成ステップと，
前記パターン頻度計算ステップにより算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算ステップにより算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算ステップと，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算ステップと，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価ステップとを有する
ことを特徴とするパターン評価処理方法。
【請求項４】
サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのパターン評価処理プログラムであって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのパターン評価処理プログラム。
【請求項５】
サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのプログラムを記録したことを特徴とするパターン評価処理プログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，  要素の組で構成される複数のパターンの評価を行うパターン評価装置，パターン評価処理方法，パターン評価処理プログラムおよびそのプログラム記録媒体に関し，特に，例えば，顧客の購買履歴，Ｗｅｂアクセス・ログ，  株価や気温の時系列データといった状態列データの分析に関わる方式に関する。
【０００２】
【従来の技術】
ＰＯＳデータやＷｅｂアクセス・ログ等から，  多くのデータに共通して現れる要素の組，  すなわちパターンを見つけ出すことは，  データベース・マーケティングや顧客情報管理（ＣＲＭ）等多くの分野で重要な課題であり，  これを解決するためにＡｐｒｉｏｒｉ  等の手法が提案されている（例えば，非特許文献１参照）。
【０００３】
しかし，これらの手法では，  非常に多くのパターンが発見され，  その中から利用価値の高いパターンを選び出すことはきわめて困難である。そのため，  発見されたパターンの良さを評価し，  それをもとに統計的に意味のないパターンや冗長なパターンを除去し，  データベース内の多様な特徴を表わす比較的少数のパターンを選択することが必要となる。
【０００４】
データベース内で，  パターンを構成する個々の要素の頻度（例えば，  個々の商品の購買頻度）から推定されるよりも非常に多く出現するパターンは，特に利用価値が高いという観点にもとづき，  パターンの一部であるサブパターンからの推定頻度と，  パターンの実際の頻度との比較によってパターンの有用性を評価する方式が従来より用いられてきた（例えば，非特許文献２，３，４，５，６参照）。
【０００５】
また，例えば，  関連する特許出願（出願番号：  特願２００２−３４７２４１，「意外性に基づく状態列パターンの評価装置」）では，  分析対象となるパターンについて，  部分パターンの頻度を用いてパターンの想定頻度を計算し，  その想定頻度とデータベース内の実際の頻度との関数でパターンの有用性を定義している。
【０００６】
【非特許文献１】
Ｒａｋｅｓｈ  Ａｇｒａｗａｌ  ａｎｄ  Ｒａｍａｋｒｉｓｈｎａｎ  Ｓｒｉｋａｎｔ：‘Ｆａｓｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｍｉｎｉｎｇ  ａｓｓｏｃｉａｔｉｏｎ  ｒｕｌｅｓ’．  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ，  ｐｐ．４８７−４９９，１９９４．
【非特許文献２】
Ｇｕｏｚｈｕ  Ｄｏｎｇ  ａｎｄ  Ｊｉｎｙａｎ  Ｌｉ：‘Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ  ｏｆ  Ｄｉｓｃｏｖｅｒｅｄ  Ａｓｓｏｃｉａｔｉｏｎ  Ｒｕｌｅｓ  ｉｎ  Ｔｅｒｍｓ  ｏｆ  Ｎｅｉｇｈｂｏｒｈｏｏｄ−Ｂａｓｅｄ  Ｕｎｅｘｐｅｃｔｅｄｎｅｓｓ  ’．  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  Ｓｅｃｏｎｄ  Ｐａｃｉｆｉｃ−Ａｓｉａ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ  （ＰＡＫＤＤ），１９９８．
【非特許文献３】
Ｒｏｂｅｒｔ  Ｊ．  Ｈｉｌｄｅｒｍａｎ  ａｎｄ  Ｈｏｗａｒｄ  Ｊ．  Ｈａｍｉｌｔｏｎ：  ‘Ｋｎｏｗｌｅｄｇｅ  ｄｉｓｃｏｖｅｒｙ  ａｎｄ  ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ  ｍｅａｓｕｒｅｓ：  ａ  ｓｕｒｖｅｙ’．  Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｒｅｇｉｎａ，  ＣＳ  ９９−０４，１９９９．
【非特許文献４】
Ｆａｒｈａｄ  Ｈｕｓｓａｉｎ，  Ｈｕａｎ  Ｌｉｕ  ａｎｄ  Ｈｏｎｇｊｕｎ  Ｌｕ：‘Ｒｅｌａｔｉｖｅ  ｍｅａｓｕｒｅ  ｆｏｒ  ｍｉｎｉｎｇ  ｉｎｔｅｒｅｓｔｉｎｇ  ｒｕｌｅｓ  ’．  Ｐｒｏｃ．  ｏｆ  ＰＫＤＤ−２０００  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  Ｍａｎａｇｅｍｅｎｔ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，２０００．
【非特許文献５】
Ｓｚｙｍｏｎ  Ｊａｒｏｓｚｅｗｉｃｚ  ａｎｄ  Ｄａｎ  Ａ．  Ｓｉｍｏｖｉｃｉ：  ‘Ａ  Ｇｅｎｅｒａｌ  Ｍｅａｓｕｒｅ  ｏｆ  Ｒｕｌｅ  Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ  ’．  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  Ｆｉｆｔｈ  Ｅｕｒｏｐｅａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ａｎｄ  Ｐｒａｃｔｉｃｅ  ｏｆ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ｉｎ  Ｄａｔａｂａｓｅｓ  （ＰＫＤＤ），２００１．
【非特許文献６】
Ｐａｎｇ−Ｎｉｎｇ  Ｔａｎ，  Ｖｉｐｉｎ  Ｋｕｍａｒ  ａｎｄ  Ｊａｉｄｅｅｐ  Ｓｒｉｖａｓｔａｖａ：‘Ｓｅｌｅｃｔｉｎｇ  ｔｈｅ  Ｒｉｇｈｔ  Ｉｎｔｅｒｅｓｔｉｎｇｎｅｓｓ  Ｍｅａｓｕｒｅ  ｆｏｒ  Ａｓｓｏｃｉａｔｉｏｎ  Ｐａｔｔｅｒｎｓ’．  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  Ｅｉｇｈｔｈ  ＡＣＭ  ＳＩＧＫＤＤ  Ｉｎｔ’ｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ  （ＫＤＤ），２００２．
【０００７】
【発明が解決しようとする課題】
しかし，  上記従来技術の，サブパターンと比較する方式では，  冗長なパターン群に高い評価値が与えられる場合があり，  パターン発見の効率を下げる要因となる。例えば，  商品Ａ，Ｂ，Ｃが常に併買されている場合，  パターン｛Ａ，Ｂ，Ｃ  ｝のみを有用と評価すべきであるが，  従来技術では，  パターン｛Ａ，Ｂ  ｝，｛Ａ，Ｃ  ｝，｛Ｂ，Ｃ  ｝の評価値も高くなり，  有用であると評価されてしまうという問題がある。
【０００８】
本発明は，上記従来技術の問題点を解決し，要素の組で構成されるパターン群について，互いに相関を持つ要素を全て含み，それらと相関のない要素を含まない，要素間の関係を表わすのに必要十分なパターンのみを選択することが可能なパターンの評価方式を提供することを目的とする。
【０００９】
【課題を解決するための手段】
この問題点を解決するために，  本発明では，  評価対象のパターンＳの頻度の推定値を，  パターンＳから一部の要素を取り除いたサブパターンの頻度と，  反対にパターンＳに要素を追加したスーパーパターンの頻度から計算し，  パターンＳの実際の頻度がそれらの推定値よりどれだけ大きいかによってパターンの良さ，  つまり有意義度を評価する。
【００１０】
評価対象のパターンが互いに相関のないサブパターンの組み合わせである場合には，  それらのサブパターンから計算される頻度の推定値と実際の頻度とがほぼ等しくなるので，  そのパターンの評価値は小さくなる。逆に，  互いに強い相関を持つ要素の集合の一部だけを取り出したパターンについても，  残りの要素を追加したスーパーパターンから計算される頻度の推定値よりも実際の頻度が小さくなるので，  評価値は小さくなる。その結果，  互いに相関を持つ要素を全て含み，  それらと相関のない要素を含まない，  要素間の関係を表わすのに必要十分なパターンのみを選択することが可能となる。
【００１１】
すなわち，本発明は，要素の組で構成される複数のパターンについて，  パターンから一部の要素を取り除いたサブパターンの頻度と，  パターンに要素を追加したスーパーパターンの頻度と，  要素の頻度を用いて，  パターンから種々の要素を取り除いて形成されるサブパターン群，  およびパターンに種々の要素を追加して形成されるスーパーパターン群についてそれぞれパターンの推定頻度を計算し，  各推定頻度からのパターンの実際の頻度の乖離度を計算し，  サブパターン群およびスーパーパターン群における推定頻度からのパターンの実際の頻度の乖離度に関する任意の統計値をパターンの有意義度として，  パターンを評価することを特徴とする。
【００１２】
また，上記方式において，  サブパターンについてのパターンの推定頻度は，サブパターンの頻度と取り除かれた要素の頻度の積を全状態列数で割った値とし，  スーパーパターンについてのパターンの推定頻度は，スーパーパターンの頻度と全状態列数の積を追加した要素の頻度で割った値とすることを特徴とする。
【００１３】
上記方式において，  各推定頻度からのパターンの実際の頻度の乖離度として，  パターンの実際の頻度と推定頻度との比の逆正接を用いることができる。
【００１４】
上記方式において，  サブパターン群およびスーパーパターン群における推定頻度からのパターンの実際の頻度の乖離度に関する統計値として，  サブパターン群における推定頻度からのパターンの実際の頻度の乖離度の最小値と，  スーパーパターン群における推定頻度からのパターンの実際の頻度の乖離度の最小値との和を用いることができる。
【００１５】
また，上記方式において，  スーパーパターンの頻度が所与の閾値よりも低い場合には，  そのスーパーパターンについての推定頻度からのパターンの実際の頻度の乖離度は所与の値，  あるいは所与の値の関数値とすることができる。
【００１６】
また，上記方式において，  パターンを構成する要素の並び順も考慮する場合には，  上記方式で計算される推定頻度をパターンの並び順の場合の数で割ったものを推定頻度とすることができる。
【００１７】
本発明を用いることにより，要素の組で構成されるパターン群について，互いに相関を持つ要素を全て含み，それらと相関のない要素を含まない，要素間の関係を表わすのに必要十分なパターンのみを選択することが可能となる。
【００１８】
以上のサブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターン評価の処理は，コンピュータとソフトウェアプログラムとによって実現することができ，そのプログラムをコンピュータ読み取り可能な記録媒体に記録して提供することも，ネットワークを通して提供することも可能である。
【００１９】
【発明の実施の形態】
以下に，図を用いて，本発明の実施の形態を説明する。図１は本発明のパターン評価装置の構成例を示す図である。図１において，１はＣＰＵおよびメモリ等のコンピュータとパターン評価のためのソフトウェアプログラムとから構成されるパターン評価装置である。１１はパターン評価装置１全体を制御する処理制御部，１２は状態列データベース内のパターンの頻度を計算するパターン頻度計算部，１３はサブパターン群とスーパーパターン群を生成するサブパターン／スーパーパターン生成部，１４は評価対象のパターンの推定頻度を計算するパターン推定頻度計算部，１５は評価対象のパターンの有意義度を計算するパターン有意義度計算部である。
【００２０】
１６は各パターンについて計算された有意義度に基づいてパターンを評価するパターン評価部，１７はパターンの評価結果を出力する評価結果出力処理部，１８は入力装置，１９は出力装置，２０は分析対象の状態列データが格納された状態列データベース，２１は算出された状態列データベース２０内のパターンの頻度が格納されるパターン頻度情報データベースである。
【００２１】
図２は，本発明のパターン評価処理フローの一例を示す図である。まず，ＰＯＳデータやＷｅｂアクセス・ログ等の分析対象の状態列データが格納された状態列データベース２０から状態列データを読み込む（ステップＳ１）。次に，パターン頻度計算部１２によって，  状態列の要素で構成される種々のパターンについて，  状態列データベース２０内の頻度を計算する（ステップＳ２）。その頻度情報をパターン頻度情報データベース２１に格納する。
【００２２】
次に，サブパターン／スーパーパターン生成部１３によって，  評価対象のパターンＳから一部の要素を取り除いたサブパターン群と，  パターンＳに要素を追加したスーパーパターン群を生成する（ステップＳ３）。パターン推定頻度計算部１４によって，  各サブパターン，  スーパーパターンの頻度からそれぞれ，  パターンＳの推定頻度を計算する（ステップＳ４）。
【００２３】
パターン有意義度計算部１５によって，  各推定頻度からのパターンＳの実際の頻度の乖離度を計算し，  サブパターン群およびスーパーパターン群における推定頻度からのパターンＳの実際の頻度の乖離度に関する所定の統計値を，  パターンＳの有意義度として計算する（ステップＳ５）。
【００２４】
そして，各パターンについて計算された有意義度に基づいて，  パターン評価部１６によって，  パターンを評価し（ステップＳ６），  評価結果出力処理部１７によってその結果を出力する（ステップＳ７）。
【００２５】
本発明の実施の形態においては，状態列データベース２０内の要素あるいはパターンの頻度は，  状況に応じて適宜定義するものとする。例えば，  状態列データベース２０内でその要素あるいはパターンを含む状態列の数として定義したり，  状態列上で要素あるいはパターンが複数回出現しうる場合には，  要素あるいはパターン自体の出現頻度として定義することなどが可能である。
【００２６】
評価対象のパターンからサブパターン群やスーパーパターン群を生成する方法は，  状況に応じて適当な方法を適用するものとする。例えば，  パターンから要素を１つ取り除いてサブパターンを生成し，  パターンに要素を１つ追加してスーパーパターンを生成する方法，  あるいは，  パターンから要素を最大２つまで取り除いてサブパターンを生成し，  パターンに要素を最大２つまで追加してスーパーパターンを生成する方法などが可能である。
【００２７】
要素の全種類（要素集合）が｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ  ｝で，  評価対象のパターンが｛Ａ，Ｂ，Ｃ，Ｄ  ｝であるとき，  前者の方法では，  生成されるサブパターン群は，  ｛Ａ，Ｂ，Ｃ，Ｄ  ｝から要素Ａ  ，  Ｂ  ，  Ｃ  ，  Ｄ  を取り除いた
｛Ｂ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｃ  ｝
であり，  生成されるスーパーパターン群は，  ｛Ａ，Ｂ，Ｃ，Ｄ  ｝に要素Ｅ  ，  Ｆ  を追加した
｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｄ，Ｆ  ｝
である。
【００２８】
また，後者の最大２つまで取り除いたり追加したりする方法では，  パターン｛Ａ，Ｂ，Ｃ，Ｄ  ｝から生成されるサブパターン群は，
｛Ｂ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｃ  ｝，  ｛Ｃ，Ｄ  ｝，  ｛Ｂ，Ｄ  ｝，  ｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｄ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝
であり，  生成されるスーパーパターン群は，
｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｄ，Ｆ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ  ｝
である。
【００２９】
各サブパターン，  スーパーパターンの頻度からの評価対象のパターンの推定頻度は，  適当な関数で定義するものとする。例えば，  評価対象のパターンＳのサブパターンＳ−  に対するパターンＳの推定頻度（  ＾ｆ  （Ｓ｜Ｓ−  ）  で表わす）  を，  サブパターンＳ−  の頻度ｆ（  Ｓ−  ）  と取り除かれた要素（  Ｓ＼Ｓ−  で表わす）  の頻度ｆ（  Ｓ＼Ｓ−  ）  と状態列データベース２０内の全状態列数Ｎを用いて，
＾ｆ（Ｓ｜Ｓ−  ）＝ｆ（Ｓ−  ）・ｆ（Ｓ＼Ｓ−  ）／Ｎ
で定義し，  スーパーパターンＳ＋  に対するパターンＳの推定頻度（  ＾ｆ  （Ｓ｜Ｓ＋  ）  で表わす）  を，  スーパーパターンＳ＋  の頻度ｆ（Ｓ＋  ）と追加した要素（Ｓ＋  ＼Ｓで表わす）の頻度ｆ（Ｓ＋  ＼Ｓ）と状態列データベース２０内の全状態列数Ｎを用いて，
＾ｆ  （Ｓ｜Ｓ＋  ）＝ｆ（Ｓ＋  ）・Ｎ／ｆ（Ｓ＋  ＼Ｓ）
で定義するなどの方法が可能である。
【００３０】
あるいは，  要素の頻度が所与の閾値（  例えば，  全状態列数の１％）よりも低い場合には，  パターンの推定頻度の計算では，その要素の頻度として所与の値（例えば，  全状態列数の０．８％の値）を用いるなどの方法も可能である。
【００３１】
各推定頻度からのパターンの実際の頻度の乖離度ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））は，  ｆ（Ｓ）の値が＾ｆ（Ｓ｜・）から離れれば離れるほど大きい値を取るような適当な関数で定義するものとする。例えば，  パターンの実際の頻度ｆ（Ｓ）と推定頻度＾ｆ（Ｓ｜・）との比を取って，
ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））＝ｆ（Ｓ）／＾ｆ（Ｓ｜・）
で定義したり，  あるいは，  両者の差を取って，
ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））＝（ｆ（Ｓ）−＾ｆ（Ｓ｜・））／＾ｆ（Ｓ｜・）
で定義するなどの方法が可能である。
【００３２】
パターンＳの有意義度も，  サブパターン群およびスーパーパターン群における推定頻度からのパターンＳの実際の頻度の乖離度に関する適当な統計値で定義するものとする。例えば，  サブパターン群およびスーパーパターン群における乖離度ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））の平均値で定義したり，  ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））の最小値で定義したり，  ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））の最大値で定義したり，  サブパターン群におけるｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））の最小値とスーパーパターン群におけるｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））の最小値との和で定義するなどの方法が可能である。
【００３３】
各パターンについて計算された有意義度に基づいて，  パターンを評価し，  評価結果を出力する方法は，  状況に応じて適当な方法を適用するものとする。例えば，  パターンを有意義度の高い順にソートし，  上位１００パターンを出力したり，  上位１％のパターンを出力したり，  有意義度の所定の閾値を上回ったパターンを出力するなどの方法が可能である。
【００３４】
【実施例】
〔第１の実施例〕
以下に，本発明の第１の実施例に係るパターン評価装置の動作を，状態列データベース２０として図３に示す商品購買履歴データベースを例にとって説明する。
【００３５】
図３に示す商品購買履歴データベースには，  顧客６人分の商品購買履歴が含まれている。  Ａ  ，  ．．．，  Ｅ  は商品名であり，  各顧客Ｔ１，  ．．．，  Ｔ６  が購入した商品の組を商品名の集合で表わす。例えば，  顧客Ｔ１  は商品Ａ  ，  Ｂ  ，  Ｃ  ，  Ｄ  ，  Ｅ  を購入し，  顧客Ｔ２  は商品Ｄ  ，  Ｅ  を購入している。
【００３６】
この商品購買履歴データベースに基づいて，  商品Ａ  を購入した顧客は３人，  商品Ａ  とＢ  を購入した顧客は３人，  商品Ａ  とＢ  とＣ  を購入した顧客は３人，商品Ａ  とＢ  とＣ  とＤ  を購入した顧客は２人，．．．  のように各商品の組み合わせを購入した顧客数を数え上げることにより，  購入された商品の組の部分集合である商品購買パターンについて，  図４に示すパターン頻度情報データベース２１が生成される。
【００３７】
次に，  パターン｛Ａ，Ｂ，Ｃ  ｝を例にして，  パターンの有意義度の計算手順を説明する。
【００３８】
（１）サブパターンの生成
評価対象のパターンから要素を１つ取り除いてサブパターン群を生成する。例えば，  パターン｛Ａ，Ｂ，Ｃ  ｝から要素Ａ  ，  Ｂ  ，  Ｃ  をそれぞれ取り除き，  サブパターン｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝を生成する。なお，  第１の実施例では，  パターンから要素を１つ取り除いてサブパターンを生成するが，  要素を２つ以上取り除いて，  サブパターンを生成してもよい。
【００３９】
（２）スーパーパターンの生成
評価対象のパターンに要素を１つ追加してスーパーパターン群を生成する。例えば，  パターン｛Ａ，Ｂ，Ｃ  ｝に要素Ｄ  ，  Ｅ  をそれぞれ追加し，  スーパーパターン｛Ａ，Ｂ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｅ  ｝を生成する。なお，  第１の実施例では，  パターンに要素を１つ追加してスーパーパターンを生成するが，  要素を２つ以上追加して，  スーパーパターンを生成してもよい。
【００４０】
（３）各サブパターンに対するパターンの推定頻度の計算
第１の実施例では，  サブパターンＳ−  に対するパターンＳの推定頻度＾ｆ（Ｓ｜Ｓ−  ）を，  サブパターンＳ−  の頻度ｆ（Ｓ−  ）と取り除かれた要素Ｓ＼Ｓ−  の頻度ｆ（Ｓ＼Ｓ−  ）と商品購買履歴データベース内の全状態列数Ｎを用いて，
＾ｆ（Ｓ｜Ｓ−  ）＝ｆ（Ｓ−  ）・ｆ（Ｓ＼Ｓ−  ）／Ｎ
で定義するものとする。
【００４１】
したがって，  サブパターン｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝に対するパターン｛Ａ，Ｂ，Ｃ  ｝の推定頻度はそれぞれ，
2005004393.tif 000003
となる。
【００４２】
（４）各スーパーパターンに対するパターンの推定頻度の計算
第１の実施例では，  スーパーパターンＳ＋  に対するパターンＳの推定頻度＾ｆ（Ｓ｜Ｓ＋  ）を，  スーパーパターンＳ＋  の頻度ｆ（Ｓ＋  ）と追加した要素（Ｓ＋  ＼Ｓ）の頻度ｆ（Ｓ＋  ＼Ｓ）と商品購買履歴データベース内の全状態列数Ｎを用いて，
＾ｆ（Ｓ｜Ｓ＋  ）＝ｆ（Ｓ＋  ）・Ｎ／ｆ（Ｓ＋  ＼Ｓ）
で定義するものとする。
【００４３】
したがって，  スーパーパターン｛Ａ，Ｂ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｅ  ｝に対するパターン｛Ａ，Ｂ，Ｃ  ｝の推定頻度はそれぞれ，
2005004393.tif 000004
となる。
【００４４】
（５）各推定頻度からのパターンの実際の頻度の乖離度の計算
第１の実施例では，  各推定頻度＾ｆ（Ｓ｜・）からのパターンの実際の頻度ｆ（Ｓ）の乖離度ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））を，
ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））＝  ａｒｃｔａｎ  （ｆ（Ｓ）／＾ｆ（Ｓ｜・））
で定義するものとする。
【００４５】
ここでａｒｃｔａｎ（ｒ）は，  実数ｒの逆正接（アークタンジェント）を表わす。ａｒｃｔａｎ（ｒ）は，ｒの単調増加関数であり，  ｒ≧０のとき，０≦ａｒｃｔａｎ（ｒ）≦π／２である。
【００４６】
ａｒｃｔａｎ（ｆ（Ｓ）／＾ｆ（Ｓ｜・））は，  図５に示すように，底辺が＾ｆ（Ｓ｜・），高さがｆ（Ｓ）の直角三角形の傾斜角度に相当する。パターンの推定頻度＾ｆ（Ｓ｜・）に比べて実際の頻度ｆ（Ｓ）が大きいほど，  傾斜角度ａｒｃｔａｎ（ｆ（Ｓ）／＾ｆ（Ｓ｜・））が大きくなる。
【００４７】
サブパターン｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝，  およびスーパーパターン｛Ａ，Ｂ，Ｃ，Ｄ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｅ  ｝に対するパターン｛Ａ，Ｂ，Ｃ  ｝の推定頻度からの実際の頻度ｆ（｛Ａ，Ｂ，Ｃ  ｝）  の乖離度はそれぞれ，
2005004393.tif 000005
となる。
【００４８】
（６）パターンの有意義度の計算
第１の実施例では，  パターンＳの有意義度Ｉ（Ｓ）を，サブパターン群における乖離度の最小値とスーパーパターン群における乖離度の最小値との和，つまり，
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））；Ｓ−  はＳの所与のサブパターン｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ＋  ））；Ｓ＋  はＳの所与のスーパーパターン｝
で定義するものとする。
【００４９】
このとき，  パターン｛Ａ，Ｂ，Ｃ  ｝の有意義度は，
Ｉ（｛Ａ，Ｂ，Ｃ  ｝）＝１．１０７  ＋０．７８５  ＝１．８９２
となる。
【００５０】
なお，  パターン頻度情報データベース２１内にスーパーパターンが存在しないパターンＳについては，  例えば，  ＾ｆ（Ｓ｜Ｓ＋  ）≡０，およびａｒｃｔａｎ（ｘ／０）＝π／２（＝１．５７０  ），ｘ＞０を仮定して，
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））；Ｓ−  はＳの所与のサブパターン｝＋π／２
と定義するものとする。
【００５１】
（７）パターンの評価
第１の実施例では，  パターン頻度情報データベース２１における，  所定の範囲の要素数で構成されたパターンについて有意義度を計算し，  パターン群を有意義度が高い順にソートして，  有意義度の上位から所定の数（あるいは，  所定の割合）のパターンを出力するものとする。
【００５２】
図４におけるパターン頻度情報データベース２１の中で，  要素数２から４までのパターン群について有意義度を計算し，  有意義度の高い順にパターン群をソートした上位６パターンを図６に示す。
【００５３】
従来方式のように，  サブパターンだけで比較する場合，つまり，ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））｝の値でパターンを評価する場合，｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝には，  ｛Ａ，Ｂ，Ｃ  ｝と等しい評価値が与えられる。これは，  ｛Ｄ，Ｅ  ｝や｛Ａ，Ｂ，Ｃ，Ｄ  ｝よりも評価値が高い。
【００５４】
しかし，  図３に示すもとの商品購買履歴データベースを見れば分かるように，  商品Ａ  ，  Ｂ  ，  Ｃ  はつねに併買されているので，  本来，  パターン｛Ａ，Ｂ，Ｃ  ｝を｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝よりも高く評価すべきであって，  この従来方式のように，  ｛Ａ，Ｂ，Ｃ  ｝，  ｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝に等しい評価値を与えるのは適切ではない。しかも，  従来方式では，  別種のパターン｛Ｄ，Ｅ  ｝，  ｛Ａ，Ｂ，Ｃ，Ｄ  ｝の評価が相対的に低くなっていて，  比較的少ないパターンでデータベースの多様な特徴を表現することにも適していない。
【００５５】
それに対して，  第１の実施例に係るパターン評価方式は，  サブパターンとの比較とスーパーパターンとの比較を組み合わせた有意義度Ｉ（Ｓ），
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ＋  ））｝
によって，  冗長なパターン｛Ｂ，Ｃ  ｝，  ｛Ａ，Ｃ  ｝，  ｛Ａ，Ｂ  ｝の評価値を低く抑えることができる。
【００５６】
〔第２の実施例〕
次に，本発明の第２の実施例について説明する。一般に，  状態列データベース２０内のパターンは膨大な数になるので，  すべてのパターンの頻度を数え上げて，  パターン頻度情報データベース２１に登録することは現実的ではない。そのため通常は，Ａｐｒｉｏｒｉ  法などのように，  頻度が所定の最小サポート値以上のパターンのみを数え上げてパターン頻度情報データベース２１に登録する。
【００５７】
状態列データベース２０として図３に示す商品購買履歴データベースを例にとり，この商品購買履歴データベースについて最小サポート値「２」で商品購買パターンを数え上げた場合のパターン頻度情報データベース２１を，図７に示す。図７において，中線が引かれたパターンは，頻度が最小サポート値未満の，パターン頻度情報データベース２１に登録されないパターンを表わす。
【００５８】
この場合，  要素数２から４のパターン群を有意義度の評価対象とすると，  頻度が最小サポート値以上の（中線の引かれていない）１２パターンが評価対象となる。このとき，  ｛Ａ，Ｂ，Ｃ，Ｄ  ｝のように，  状態列データベース（商品購買履歴データベース）２０には最小サポート値未満でスーパーパターンが存在するにもかかわらず，  パターン頻度情報データベース２１ではスーパーパターンがいっさい存在しないというパターンが生じることがある。
【００５９】
上述した第１の実施例では，  そのようなパターンＳに対して一律に＾ｆ（Ｓ｜Ｓ＋  ）≡０を仮定し，
ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ＋  ））；Ｓ＋  はＳの所与のスーパーパターン｝＝ａｒｃｔａｎ（ｘ／０）＝π／２
と定義していた。
【００６０】
第２の実施例では，  パターン頻度情報データベース２１内にスーパーパターンが存在しない場合でも，  状態列データベース（商品購買履歴データベース）２０内に最小サポート値未満でスーパーパターンが存在する可能性を考慮して，  下記のように，  スーパーパターンについての推定頻度からのパターンの実際の頻度の乖離度を計算する方法を導入する。
・Ｎを状態列データベース（商品購買履歴データベース）２０内の全状態列数とする。
・Ｍを要素の全種類（  要素集合）  とする。例えば，  Ｍ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ  ｝。
・ｆ＊  をパターン頻度情報データベース２１内にスーパーパターンが存在しない場合の所与の仮想的なスーパーパターンの頻度とする。例えば，  最小サポート値が２のとき，ｆ＊  ＝（最小サポート値）／２＝１。
【００６１】
パターン頻度情報データベース２１内にスーパーパターンが存在しない場合のスーパーパターンについてのパターンＳの推定頻度を，  仮想的なスーパーパターンの頻度ｆ＊  と，  パターン頻度情報データベース２１内で最大頻度の要素の頻度を用いて下記のように定義する。
【００６２】
【数１】
2005004393.tif 000006
【００６３】
このとき，  パターンＳの実際の頻度との乖離度は，
【００６４】
【数２】
2005004393.tif 000007
【００６５】
パターン頻度情報データベース２１内にスーパーパターンが存在しない場合の，  パターンの有意義度を下記のように定義する。
【００６６】
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））｝＋ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜＋  ）
ここで，  最小サポート値「２」の場合の図７に示すパターン頻度情報データベース２１における評価対象の１２パターンの中でスーパーパターンの存在しない｛Ｄ，Ｅ  ｝と｛Ａ，Ｂ，Ｃ，Ｄ  ｝について，  ＾ｆ（Ｓ｜＋  ）およびＩ（Ｓ）の計算例を示す。全状態列数はＮ＝６，要素集合はＭ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ  ｝である。また，  仮想的なスーパーパターンの頻度をｆ＊  ＝（最小サポート値）／２＝１とする。
（１）パターン｛Ｄ，Ｅ  ｝：
【００６７】
【数３】
2005004393.tif 000008
【００６８】
第１の実施例より，
ｍｉｎ｛ｄ（ｆ（｛Ｄ，Ｅ  ｝），＾ｆ（｛Ｄ，Ｅ  ｝｜｛Ｄ，Ｅ  ｝−  ））｝＝０．８４４
ゆえに，Ｉ（｛Ｄ，Ｅ  ｝）＝０．８４４  ＋０．９８２  ＝１．８２６
（２）パターン｛Ａ，Ｂ，Ｃ，Ｄ  ｝：
【００６９】
【数４】
2005004393.tif 000009
【００７０】
第１の実施例より，
ｍｉｎ｛ｄ（ｆ（｛Ａ，Ｂ，Ｃ，Ｄ  ｝），＾ｆ（｛Ａ，Ｂ，Ｃ，Ｄ  ｝｜｛Ａ，Ｂ，Ｃ，Ｄ  ｝−  ））｝＝０．７８５
ゆえに，  Ｉ（｛Ａ，Ｂ，Ｃ，Ｄ  ｝）＝０．７８５  ＋０．９２７  ＝１．７１２
図７における評価対象の１２パターンについて，  第２の実施例の方法に従って有意義度を計算し，  有意義度の高い順にパターン群をソートした上位６パターンを図８に示す。
【００７１】
図８中のｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ＋  ））｝欄は，  スーパーパターン群におけるパターンの推定頻度からの実際の乖離度の最小値を第１の実施例の方法に従って計算した値（つまり，  スーパーパターンが存在しないパターンについてはπ／２＝１．５７０  ）を，  ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜＋  ））欄は第２の実施例の方法に従って計算した値を表わす。
【００７２】
また，  Ｉ１  （Ｓ）欄は有意義度を仮想的なスーパーパターンの頻度を利用しない第１の実施例の方法に従って計算した値を，  Ｉ２  （Ｓ）欄は仮想的なスーパーパターンの頻度を利用する第２の実施例の方法に従って計算した値を表わす。
【００７３】
Ｉ１  （Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ＋  ））｝
Ｉ２  （Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ−  ））｝＋ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜＋  ））
パターン頻度情報データベース２１内にスーパーパターンが存在しないことを重要視したい場合には，  第１の実施例の方法に基づく有意義度Ｉ１  （Ｓ）が適している。逆に，  スーパーパターンが存在しないことを特に重要視する必要がない場合には，  第２の実施例の方法に基づく有意義度Ｉ２  （Ｓ）が適している。
【００７４】
〔第３の実施例〕
次に，本発明の第３の実施例について説明する。上記第１の実施例，第２の実施例では，  評価対象のパターンは状態列を構成する要素の組（例えば，  購入した商品の組み合わせ，  アクセスしたことのあるＷｅｂのＵＲＬの組み合わせなど）であるが，  状態列上の要素の並び順（例えば，  商品の購入順序，ＵＲＬのアクセス順序など）のパターンを評価したい場合がある。
【００７５】
そこで，  第３の実施例として，  状態列上の要素の並び順を考慮したパターンの有意義度の計算方法を示す。図９は，  ユーザＴ１，Ｔ２，．．．，Ｔ１０によるＷｅｂのＵＲＬのアクセス順序を表わす状態列データベース２０の例である。１つのＵＲＬは英数３文字で表記されている。例えば，  ユーザＴ１  は，  ＸＭＫ，  ＸＱＫ，  ＸＱＫ，  ＸＱＫ，  ＸＭＫ，  ．．．の順にＵＲＬにアクセスしている。
【００７６】
第３の実施例では，  １つの状態列上で要素を跳び跳びにつなげてパターンを生成する。ただし，  パターンの最大長はＬ，パターンは，図１０に示すように，１つの状態列上の長さＷ（ウインドウ・サイズ）  の部分列に含まれるように生成することとする。
【００７７】
このようにして生成されるパターンを含む，  状態列データベース２０内での状態列の数をパターンの頻度とする。なお，図１０では，最大パターン長＝５，ウインドウ・サイズ＝１２の場合のパターンの生成例を示している。
【００７８】
図９に示す状態列データベース２０について，  最大パターン長＝５，ウインドウ・サイズ＝２５で生成されるパターン頻度情報データベース２１を，図１１に示す。
【００７９】
パターンの並び順を考慮した場合のパターンの推定頻度  ｅｆ（Ｓ｜・）を，  上記第１の実施例または第２の実施例で示した方式において要素の組にのみ注目して計算される推定頻度＾ｆ（Ｓ｜・）から，  パターンの並び順の場合の数で割って，  下記のように定義するものとする。
【００８０】
ｅｆ（Ｓ｜Ｓ−  ）＝（ｎ（Ｓ−  ）！・ｎ（Ｓ＼Ｓ−  ）！／ｎ（Ｓ）！）・＾ｆ（Ｓ｜Ｓ−  ）
ｅｆ（Ｓ｜Ｓ＋  ）＝（ｎ（Ｓ＋  ）！／ｎ（Ｓ）！・ｎ（Ｓ＋  ＼Ｓ）！）・＾ｆ（Ｓ｜Ｓ＋  ）
ここで，  ｎ（Ｓ）はパターンＳの要素数を表わす。
【００８１】
特に，  サブパターンを生成する際にパターンから取り除く要素数が１で，  スーパーパターンを生成する際にパターンに追加する要素数が１の場合には，
ｎ（Ｓ−  ）！・ｎ（Ｓ＼Ｓ−  ）！／ｎ（Ｓ）！＝（ｎ（Ｓ）−１）！／ｎ（Ｓ）！＝１／ｎ（Ｓ）
ｎ（Ｓ＋  ）！／ｎ（Ｓ）！・ｎ（Ｓ＋  ＼Ｓ）！＝ｎ（Ｓ＋  ）！／ｎ（Ｓ）！＝ｎ（Ｓ＋  ）
となるので，  パターンの並び順を考慮した場合のパターンの推定頻度は次式で表わされることになる。
【００８２】
ｅｆ（Ｓ｜Ｓ−  ）＝（１／ｎ（Ｓ））・＾ｆ（Ｓ｜Ｓ−  ）
ｅｆ（Ｓ｜Ｓ＋  ）＝ｎ（Ｓ＋  ）・＾ｆ（Ｓ｜Ｓ＋  ）
例えば，  長さ３のパターンＳ＝｛ＹＥＫ，ＸＮＫ，Ｘ３Ｋ  ｝について，  サブパターンＳ−  ＝｛ＹＥＫ，ＸＮＫ  ｝からもとのパターンＳを作るために追加すべき要素Ｘ３Ｋ  は，  サブパターンＳ−  に対して，
・ＹＥＫ  の前に追加される，
・ＹＥＫ  とＸＮＫ  の間に追加される，
・ＸＮＫ  の後ろに追加される，
という３通りの場合が考えられる。
【００８３】
その中でパターンＳに等しくなるのは最後の１つである。したがって，  要素の並び順を考慮する場合の推定頻度は，  要素の組み合わせだけを考慮する場合の推定頻度＾ｆ（Ｓ｜Ｓ−  ）から，  要素が追加される場合の数（つまりパターンＳの長さｎ（Ｓ））だけ割った値とすることが妥当である。
【００８４】
同様に，  パターンＳからスーパーパターンＳ＋  ＝｛ＹｎＫ，ＹＥＫ，ＸＮＫ，Ｘ３Ｋ  ｝を作るために追加すべき要素ＹｎＫ  は，  パターンＳに対して，
・ＹＥＫ  の前に追加される，
・ＹＥＫ  とＸＮＫ  の間に追加される，
・ＸＮＫ  とＸ３Ｋ  の間に追加される，
・Ｘ３Ｋ  の後ろに追加される，
という４通りの場合が考えられる。
【００８５】
その中でスーパーパターンＳ＋  に等しくなるのは最初の１つである。したがって，  要素の並び順を考慮する場合の推定頻度は，  要素の組み合わせだけを考慮する場合の推定頻度＾ｆ（Ｓ｜Ｓ＋  ）に，パターンＳに要素が追加される場合の数（つまりスーパーパターンＳ＋  の長さｎ（Ｓ＋  ））を掛けた値とすることが妥当である。
【００８６】
以上から把握できるように，本発明の実施形態の特徴を述べると，以下のようである。
【００８７】
（付記１）  サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価装置であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算手段と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成手段と，
前記パターン頻度計算手段により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算手段により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算手段と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算手段と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価手段とを備える
ことを特徴とするパターン評価装置。
【００８８】
（付記２）  付記１記載のパターン評価装置において，
前記パターン推定頻度計算手段は，
前記サブパターンの頻度と前記評価対象のパターンから取り除かれた要素の頻度の積を全状態列数で割った値を前記サブパターンについての前記評価対象のパターンの推定頻度として算出し，
前記スーパーパターンの頻度と全状態列数の積を前記評価対象のパターンに追加した要素の頻度で割った値を前記スーパーパターンについての前記評価対象のパターンの推定頻度として算出する
ことを特徴とするパターン評価装置。
【００８９】
（付記３）  付記１または付記２に記載のパターン評価装置において，
前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，前記評価対象のパターンの実際の頻度と前記サブパターンについての前記評価対象のパターンの推定頻度との比の逆正接であり，
前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，前記評価対象のパターンの実際の頻度と前記スーパーパターンについての前記評価対象のパターンの推定頻度との比の逆正接である
ことを特徴とするパターン評価装置。
【００９０】
（付記４）  付記１から付記３までのいずれかに記載のパターン評価装置において，
前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する統計値は，前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度の最小値と，  前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度の最小値との和である
ことを特徴とするパターン評価装置。
【００９１】
（付記５）  付記１から付記４までのいずれかに記載のパターン評価装置において，
前記パターン頻度計算手段により算出されたスーパーパターンの頻度が所与の閾値よりも低い場合には，  そのスーパーパターンについての推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，所与の値または所与の値の関数値とする
ことを特徴とするパターン評価装置。
【００９２】
（付記６）  付記１から付記５までのいずれかに記載のパターン評価装置において，
前記パターン推定頻度計算手段は，パターンを構成する要素の並び順を考慮する場合には，前記算出したサブパターンについての前記評価対象のパターンの推定頻度または前記算出したスーパーパターンについての前記評価対象のパターンの推定頻度をそれぞれパターンの並び順の場合の数で割った値をサブパターンについての前記評価対象のパターンの推定頻度またはスーパーパターンについての前記評価対象のパターンの推定頻度として算出する
ことを特徴とするパターン評価装置。
【００９３】
（付記７）  サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価をコンピュータによって行うパターン評価処理方法であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算ステップと，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成ステップと，
前記パターン頻度計算ステップにより算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算ステップにより算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算ステップと，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算ステップと，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価ステップとを有する
ことを特徴とするパターン評価処理方法。
【００９４】
（付記８）  サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのパターン評価処理プログラムであって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのパターン評価処理プログラム。
【００９５】
（付記９）  サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのプログラムを記録したことを特徴とするパターン評価処理プログラム記録媒体。
【００９６】
【発明の効果】
本発明のパターン評価装置によって，  要素の組で構成されるパターン群について，  データベース内の頻度に関して相関の低いパターン，  および互いに強い相関を持つ要素の集合の一部だけを取り出した冗長なパターンを除去することができる。したがって，本発明によれば，要素の組で構成されるパターン群について，互いに相関を持つ要素を全て含み，それらと相関のない要素を含まない，要素間の関係を表わすのに必要十分なパターンのみを選択することが可能となる。
【図面の簡単な説明】
【図１】本発明のパターン評価装置の構成例を示す図である。
【図２】本発明のパターン評価処理フローの一例を示す図である。
【図３】商品購買履歴データベースを示す図である。
【図４】パターン頻度情報データベースを示す図である。
【図５】各推定頻度からのパターンの実際の頻度の乖離度の計算を示す図である。
【図６】有意義度上位のパターン群を示す図である。
【図７】パターン頻度情報データベースを示す図である。
【図８】最小サポート値が２の場合の有意義度上位のパターン群を示す図である。
【図９】要素の並び順を考慮した状態列データベースの一例を示す図である。
【図１０】状態列上で要素を跳び跳びにつなげて生成されるパターンの一例を示す図である。
【図１１】要素の並び順を考慮したパターン頻度情報データベースを示す図である。
【符号の説明】
１  パターン評価装置
１１  処理制御部
１２  パターン頻度計算部
１３  サブパターン／スーパーパターン生成部
１４  パターン推定頻度計算部
１５  パターン有意義度計算部
１６  パターン評価部
１７  評価結果出力処理部
１８  入力装置
１９  出力装置
２０  状態列データベース
２１  パターン頻度情報データベース
【図１】
2005004393.tif 000010
【図２】
2005004393.tif 000011
【図３】
2005004393.tif 000012
【図４】
2005004393.tif 000013
【図５】
2005004393.tif 000014
【図６】
2005004393.tif 000015
【図７】
2005004393.tif 000016
【図８】
2005004393.tif 000017
【図９】
2005004393.tif 000018
【図１０】
2005004393.tif 000019
【図１１】
2005004393.tif 000020