JP2005004393A - Pattern evaluation apparatus, pattern evaluation processing method, pattern evaluation processing program, and program recording medium thereof - Google Patents

Abstract

The present invention relates to a pattern evaluation apparatus based on significance using sub-pattern and super-pattern frequencies, and selects only patterns necessary and sufficient for expressing the relationship between elements in a pattern group composed of element sets. For the purpose.
A pattern frequency calculation unit calculates a frequency in a state sequence database for various patterns and stores it in a pattern frequency information database, and a sub-pattern / super pattern generation unit generates a sub-pattern from a pattern to be evaluated. A pattern group and a super pattern group are generated, the pattern estimation frequency calculation unit 14 calculates the estimation frequency of S based on the sub-pattern and super pattern frequencies, and the pattern significance calculation unit 15 calculates the S from each estimation frequency. The actual frequency deviation degree is calculated, a predetermined statistical value relating to each calculated deviation degree is calculated as the significance level of S, and the pattern evaluation unit 16 evaluates the pattern based on the calculated significance level.
[Selection] Figure 1

Description

となる。
【００４２】
（４）各スーパーパターンに対するパターンの推定頻度の計算
第１の実施例では， スーパーパターンＳ^＋ に対するパターンＳの推定頻度＾ｆ（Ｓ｜Ｓ^＋ ）を， スーパーパターンＳ^＋ の頻度ｆ（Ｓ^＋ ）と追加した要素（Ｓ^＋ ＼Ｓ）の頻度ｆ（Ｓ^＋ ＼Ｓ）と商品購買履歴データベース内の全状態列数Ｎを用いて，
＾ｆ（Ｓ｜Ｓ^＋ ）＝ｆ（Ｓ^＋ ）・Ｎ／ｆ（Ｓ^＋ ＼Ｓ）
で定義するものとする。
【００４３】
したがって， スーパーパターン｛Ａ，Ｂ，Ｃ，Ｄ ｝， ｛Ａ，Ｂ，Ｃ，Ｅ ｝に対するパターン｛Ａ，Ｂ，Ｃ ｝の推定頻度はそれぞれ，

となる。
【００４４】
（５）各推定頻度からのパターンの実際の頻度の乖離度の計算
第１の実施例では， 各推定頻度＾ｆ（Ｓ｜・）からのパターンの実際の頻度ｆ（Ｓ）の乖離度ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））を，
ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜・））＝ ａｒｃｔａｎ （ｆ（Ｓ）／＾ｆ（Ｓ｜・））
で定義するものとする。
【００４５】
ここでａｒｃｔａｎ（ｒ）は， 実数ｒの逆正接（アークタンジェント）を表わす。ａｒｃｔａｎ（ｒ）は，ｒの単調増加関数であり， ｒ≧０のとき，０≦ａｒｃｔａｎ（ｒ）≦π／２である。
【００４６】
ａｒｃｔａｎ（ｆ（Ｓ）／＾ｆ（Ｓ｜・））は， 図５に示すように，底辺が＾ｆ（Ｓ｜・），高さがｆ（Ｓ）の直角三角形の傾斜角度に相当する。パターンの推定頻度＾ｆ（Ｓ｜・）に比べて実際の頻度ｆ（Ｓ）が大きいほど， 傾斜角度ａｒｃｔａｎ（ｆ（Ｓ）／＾ｆ（Ｓ｜・））が大きくなる。
【００４７】
サブパターン｛Ｂ，Ｃ ｝， ｛Ａ，Ｃ ｝， ｛Ａ，Ｂ ｝， およびスーパーパターン｛Ａ，Ｂ，Ｃ，Ｄ ｝， ｛Ａ，Ｂ，Ｃ，Ｅ ｝に対するパターン｛Ａ，Ｂ，Ｃ ｝の推定頻度からの実際の頻度ｆ（｛Ａ，Ｂ，Ｃ ｝） の乖離度はそれぞれ，

となる。
【００４８】
（６）パターンの有意義度の計算
第１の実施例では， パターンＳの有意義度Ｉ（Ｓ）を，サブパターン群における乖離度の最小値とスーパーパターン群における乖離度の最小値との和，つまり，
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））；Ｓ⁻ はＳの所与のサブパターン｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ^＋ ））；Ｓ^＋ はＳの所与のスーパーパターン｝
で定義するものとする。
【００４９】
このとき， パターン｛Ａ，Ｂ，Ｃ ｝の有意義度は，
Ｉ（｛Ａ，Ｂ，Ｃ ｝）＝１．１０７ ＋０．７８５ ＝１．８９２
となる。
【００５０】
なお， パターン頻度情報データベース２１内にスーパーパターンが存在しないパターンＳについては， 例えば， ＾ｆ（Ｓ｜Ｓ^＋ ）≡０，およびａｒｃｔａｎ（ｘ／０）＝π／２（＝１．５７０ ），ｘ＞０を仮定して，
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））；Ｓ⁻ はＳの所与のサブパターン｝＋π／２
と定義するものとする。
【００５１】
（７）パターンの評価
第１の実施例では， パターン頻度情報データベース２１における， 所定の範囲の要素数で構成されたパターンについて有意義度を計算し， パターン群を有意義度が高い順にソートして， 有意義度の上位から所定の数（あるいは， 所定の割合）のパターンを出力するものとする。
【００５２】
図４におけるパターン頻度情報データベース２１の中で， 要素数２から４までのパターン群について有意義度を計算し， 有意義度の高い順にパターン群をソートした上位６パターンを図６に示す。
【００５３】
従来方式のように， サブパターンだけで比較する場合，つまり，ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））｝の値でパターンを評価する場合，｛Ｂ，Ｃ ｝， ｛Ａ，Ｃ ｝， ｛Ａ，Ｂ ｝には， ｛Ａ，Ｂ，Ｃ ｝と等しい評価値が与えられる。これは， ｛Ｄ，Ｅ ｝や｛Ａ，Ｂ，Ｃ，Ｄ ｝よりも評価値が高い。
【００５４】
しかし， 図３に示すもとの商品購買履歴データベースを見れば分かるように， 商品Ａ ， Ｂ ， Ｃ はつねに併買されているので， 本来， パターン｛Ａ，Ｂ，Ｃ ｝を｛Ｂ，Ｃ ｝， ｛Ａ，Ｃ ｝， ｛Ａ，Ｂ ｝よりも高く評価すべきであって， この従来方式のように， ｛Ａ，Ｂ，Ｃ ｝， ｛Ｂ，Ｃ ｝， ｛Ａ，Ｃ ｝， ｛Ａ，Ｂ ｝に等しい評価値を与えるのは適切ではない。しかも， 従来方式では， 別種のパターン｛Ｄ，Ｅ ｝， ｛Ａ，Ｂ，Ｃ，Ｄ ｝の評価が相対的に低くなっていて， 比較的少ないパターンでデータベースの多様な特徴を表現することにも適していない。
【００５５】
それに対して， 第１の実施例に係るパターン評価方式は， サブパターンとの比較とスーパーパターンとの比較を組み合わせた有意義度Ｉ（Ｓ），
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ^＋ ））｝
によって， 冗長なパターン｛Ｂ，Ｃ ｝， ｛Ａ，Ｃ ｝， ｛Ａ，Ｂ ｝の評価値を低く抑えることができる。
【００５６】
〔第２の実施例〕
次に，本発明の第２の実施例について説明する。一般に， 状態列データベース２０内のパターンは膨大な数になるので， すべてのパターンの頻度を数え上げて， パターン頻度情報データベース２１に登録することは現実的ではない。そのため通常は，Ａｐｒｉｏｒｉ 法などのように， 頻度が所定の最小サポート値以上のパターンのみを数え上げてパターン頻度情報データベース２１に登録する。
【００５７】
状態列データベース２０として図３に示す商品購買履歴データベースを例にとり，この商品購買履歴データベースについて最小サポート値「２」で商品購買パターンを数え上げた場合のパターン頻度情報データベース２１を，図７に示す。図７において，中線が引かれたパターンは，頻度が最小サポート値未満の，パターン頻度情報データベース２１に登録されないパターンを表わす。
【００５８】
この場合， 要素数２から４のパターン群を有意義度の評価対象とすると， 頻度が最小サポート値以上の（中線の引かれていない）１２パターンが評価対象となる。このとき， ｛Ａ，Ｂ，Ｃ，Ｄ ｝のように， 状態列データベース（商品購買履歴データベース）２０には最小サポート値未満でスーパーパターンが存在するにもかかわらず， パターン頻度情報データベース２１ではスーパーパターンがいっさい存在しないというパターンが生じることがある。
【００５９】
上述した第１の実施例では， そのようなパターンＳに対して一律に＾ｆ（Ｓ｜Ｓ^＋ ）≡０を仮定し，
ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ^＋ ））；Ｓ^＋ はＳの所与のスーパーパターン｝＝ａｒｃｔａｎ（ｘ／０）＝π／２
と定義していた。
【００６０】
第２の実施例では， パターン頻度情報データベース２１内にスーパーパターンが存在しない場合でも， 状態列データベース（商品購買履歴データベース）２０内に最小サポート値未満でスーパーパターンが存在する可能性を考慮して， 下記のように， スーパーパターンについての推定頻度からのパターンの実際の頻度の乖離度を計算する方法を導入する。
・Ｎを状態列データベース（商品購買履歴データベース）２０内の全状態列数とする。
・Ｍを要素の全種類（ 要素集合） とする。例えば， Ｍ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ ｝。
・ｆ^＊ をパターン頻度情報データベース２１内にスーパーパターンが存在しない場合の所与の仮想的なスーパーパターンの頻度とする。例えば， 最小サポート値が２のとき，ｆ^＊ ＝（最小サポート値）／２＝１。
【００６１】
パターン頻度情報データベース２１内にスーパーパターンが存在しない場合のスーパーパターンについてのパターンＳの推定頻度を， 仮想的なスーパーパターンの頻度ｆ^＊ と， パターン頻度情報データベース２１内で最大頻度の要素の頻度を用いて下記のように定義する。
【００６２】
【数１】

【００６３】
このとき， パターンＳの実際の頻度との乖離度は，
【００６４】
【数２】

【００６５】
パターン頻度情報データベース２１内にスーパーパターンが存在しない場合の， パターンの有意義度を下記のように定義する。
【００６６】
Ｉ（Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））｝＋ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜^＋ ）
ここで， 最小サポート値「２」の場合の図７に示すパターン頻度情報データベース２１における評価対象の１２パターンの中でスーパーパターンの存在しない｛Ｄ，Ｅ ｝と｛Ａ，Ｂ，Ｃ，Ｄ ｝について， ＾ｆ（Ｓ｜^＋ ）およびＩ（Ｓ）の計算例を示す。全状態列数はＮ＝６，要素集合はＭ＝｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ ｝である。また， 仮想的なスーパーパターンの頻度をｆ^＊ ＝（最小サポート値）／２＝１とする。
（１）パターン｛Ｄ，Ｅ ｝：
【００６７】
【数３】

【００６８】
第１の実施例より，
ｍｉｎ｛ｄ（ｆ（｛Ｄ，Ｅ ｝），＾ｆ（｛Ｄ，Ｅ ｝｜｛Ｄ，Ｅ ｝⁻ ））｝＝０．８４４
ゆえに，Ｉ（｛Ｄ，Ｅ ｝）＝０．８４４ ＋０．９８２ ＝１．８２６
（２）パターン｛Ａ，Ｂ，Ｃ，Ｄ ｝：
【００６９】
【数４】

【００７０】
第１の実施例より，
ｍｉｎ｛ｄ（ｆ（｛Ａ，Ｂ，Ｃ，Ｄ ｝），＾ｆ（｛Ａ，Ｂ，Ｃ，Ｄ ｝｜｛Ａ，Ｂ，Ｃ，Ｄ ｝⁻ ））｝＝０．７８５
ゆえに， Ｉ（｛Ａ，Ｂ，Ｃ，Ｄ ｝）＝０．７８５ ＋０．９２７ ＝１．７１２
図７における評価対象の１２パターンについて， 第２の実施例の方法に従って有意義度を計算し， 有意義度の高い順にパターン群をソートした上位６パターンを図８に示す。
【００７１】
図８中のｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ^＋ ））｝欄は， スーパーパターン群におけるパターンの推定頻度からの実際の乖離度の最小値を第１の実施例の方法に従って計算した値（つまり， スーパーパターンが存在しないパターンについてはπ／２＝１．５７０ ）を， ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜^＋ ））欄は第２の実施例の方法に従って計算した値を表わす。
【００７２】
また， Ｉ_１ （Ｓ）欄は有意義度を仮想的なスーパーパターンの頻度を利用しない第１の実施例の方法に従って計算した値を， Ｉ_２ （Ｓ）欄は仮想的なスーパーパターンの頻度を利用する第２の実施例の方法に従って計算した値を表わす。
【００７３】
Ｉ_１ （Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））｝＋ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ^＋ ））｝
Ｉ_２ （Ｓ）＝ｍｉｎ｛ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜Ｓ⁻ ））｝＋ｄ（ｆ（Ｓ），＾ｆ（Ｓ｜^＋ ））
パターン頻度情報データベース２１内にスーパーパターンが存在しないことを重要視したい場合には， 第１の実施例の方法に基づく有意義度Ｉ_１ （Ｓ）が適している。逆に， スーパーパターンが存在しないことを特に重要視する必要がない場合には， 第２の実施例の方法に基づく有意義度Ｉ_２ （Ｓ）が適している。
【００７４】
〔第３の実施例〕
次に，本発明の第３の実施例について説明する。上記第１の実施例，第２の実施例では， 評価対象のパターンは状態列を構成する要素の組（例えば， 購入した商品の組み合わせ， アクセスしたことのあるＷｅｂのＵＲＬの組み合わせなど）であるが， 状態列上の要素の並び順（例えば， 商品の購入順序，ＵＲＬのアクセス順序など）のパターンを評価したい場合がある。
【００７５】
そこで， 第３の実施例として， 状態列上の要素の並び順を考慮したパターンの有意義度の計算方法を示す。図９は， ユーザＴ_１，Ｔ_２，．．．，Ｔ_１０によるＷｅｂのＵＲＬのアクセス順序を表わす状態列データベース２０の例である。１つのＵＲＬは英数３文字で表記されている。例えば， ユーザＴ_１ は， ＸＭＫ， ＸＱＫ， ＸＱＫ， ＸＱＫ， ＸＭＫ， ．．．の順にＵＲＬにアクセスしている。
【００７６】
第３の実施例では， １つの状態列上で要素を跳び跳びにつなげてパターンを生成する。ただし， パターンの最大長はＬ，パターンは，図１０に示すように，１つの状態列上の長さＷ（ウインドウ・サイズ） の部分列に含まれるように生成することとする。
【００７７】
このようにして生成されるパターンを含む， 状態列データベース２０内での状態列の数をパターンの頻度とする。なお，図１０では，最大パターン長＝５，ウインドウ・サイズ＝１２の場合のパターンの生成例を示している。
【００７８】
図９に示す状態列データベース２０について， 最大パターン長＝５，ウインドウ・サイズ＝２５で生成されるパターン頻度情報データベース２１を，図１１に示す。
【００７９】
パターンの並び順を考慮した場合のパターンの推定頻度 ^ｅｆ（Ｓ｜・）を， 上記第１の実施例または第２の実施例で示した方式において要素の組にのみ注目して計算される推定頻度＾ｆ（Ｓ｜・）から， パターンの並び順の場合の数で割って， 下記のように定義するものとする。
【００８０】
^ｅｆ（Ｓ｜Ｓ⁻ ）＝（ｎ（Ｓ⁻ ）！・ｎ（Ｓ＼Ｓ⁻ ）！／ｎ（Ｓ）！）・＾ｆ（Ｓ｜Ｓ⁻ ）
^ｅｆ（Ｓ｜Ｓ^＋ ）＝（ｎ（Ｓ^＋ ）！／ｎ（Ｓ）！・ｎ（Ｓ^＋ ＼Ｓ）！）・＾ｆ（Ｓ｜Ｓ^＋ ）
ここで， ｎ（Ｓ）はパターンＳの要素数を表わす。
【００８１】
特に， サブパターンを生成する際にパターンから取り除く要素数が１で， スーパーパターンを生成する際にパターンに追加する要素数が１の場合には，
ｎ（Ｓ⁻ ）！・ｎ（Ｓ＼Ｓ⁻ ）！／ｎ（Ｓ）！＝（ｎ（Ｓ）−１）！／ｎ（Ｓ）！＝１／ｎ（Ｓ）
ｎ（Ｓ^＋ ）！／ｎ（Ｓ）！・ｎ（Ｓ^＋ ＼Ｓ）！＝ｎ（Ｓ^＋ ）！／ｎ（Ｓ）！＝ｎ（Ｓ^＋ ）
となるので， パターンの並び順を考慮した場合のパターンの推定頻度は次式で表わされることになる。
【００８２】
^ｅｆ（Ｓ｜Ｓ⁻ ）＝（１／ｎ（Ｓ））・＾ｆ（Ｓ｜Ｓ⁻ ）
^ｅｆ（Ｓ｜Ｓ^＋ ）＝ｎ（Ｓ^＋ ）・＾ｆ（Ｓ｜Ｓ^＋ ）
例えば， 長さ３のパターンＳ＝｛ＹＥＫ，ＸＮＫ，Ｘ３Ｋ ｝について， サブパターンＳ⁻ ＝｛ＹＥＫ，ＸＮＫ ｝からもとのパターンＳを作るために追加すべき要素Ｘ３Ｋ は， サブパターンＳ⁻ に対して，
・ＹＥＫ の前に追加される，
・ＹＥＫ とＸＮＫ の間に追加される，
・ＸＮＫ の後ろに追加される，
という３通りの場合が考えられる。
【００８３】
その中でパターンＳに等しくなるのは最後の１つである。したがって， 要素の並び順を考慮する場合の推定頻度は， 要素の組み合わせだけを考慮する場合の推定頻度＾ｆ（Ｓ｜Ｓ⁻ ）から， 要素が追加される場合の数（つまりパターンＳの長さｎ（Ｓ））だけ割った値とすることが妥当である。
【００８４】
同様に， パターンＳからスーパーパターンＳ^＋ ＝｛ＹｎＫ，ＹＥＫ，ＸＮＫ，Ｘ３Ｋ ｝を作るために追加すべき要素ＹｎＫ は， パターンＳに対して，
・ＹＥＫ の前に追加される，
・ＹＥＫ とＸＮＫ の間に追加される，
・ＸＮＫ とＸ３Ｋ の間に追加される，
・Ｘ３Ｋ の後ろに追加される，
という４通りの場合が考えられる。
【００８５】
その中でスーパーパターンＳ^＋ に等しくなるのは最初の１つである。したがって， 要素の並び順を考慮する場合の推定頻度は， 要素の組み合わせだけを考慮する場合の推定頻度＾ｆ（Ｓ｜Ｓ^＋ ）に，パターンＳに要素が追加される場合の数（つまりスーパーパターンＳ^＋ の長さｎ（Ｓ^＋ ））を掛けた値とすることが妥当である。
【００８６】
以上から把握できるように，本発明の実施形態の特徴を述べると，以下のようである。
【００８７】
（付記１） サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価装置であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算手段と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成手段と，
前記パターン頻度計算手段により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算手段により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算手段と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算手段と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価手段とを備える
ことを特徴とするパターン評価装置。
【００８８】
（付記２） 付記１記載のパターン評価装置において，
前記パターン推定頻度計算手段は，
前記サブパターンの頻度と前記評価対象のパターンから取り除かれた要素の頻度の積を全状態列数で割った値を前記サブパターンについての前記評価対象のパターンの推定頻度として算出し，
前記スーパーパターンの頻度と全状態列数の積を前記評価対象のパターンに追加した要素の頻度で割った値を前記スーパーパターンについての前記評価対象のパターンの推定頻度として算出する
ことを特徴とするパターン評価装置。
【００８９】
（付記３） 付記１または付記２に記載のパターン評価装置において，
前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，前記評価対象のパターンの実際の頻度と前記サブパターンについての前記評価対象のパターンの推定頻度との比の逆正接であり，
前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，前記評価対象のパターンの実際の頻度と前記スーパーパターンについての前記評価対象のパターンの推定頻度との比の逆正接である
ことを特徴とするパターン評価装置。
【００９０】
（付記４） 付記１から付記３までのいずれかに記載のパターン評価装置において，
前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する統計値は，前記サブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度の最小値と， 前記スーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度の最小値との和である
ことを特徴とするパターン評価装置。
【００９１】
（付記５） 付記１から付記４までのいずれかに記載のパターン評価装置において，
前記パターン頻度計算手段により算出されたスーパーパターンの頻度が所与の閾値よりも低い場合には， そのスーパーパターンについての推定頻度からの前記評価対象のパターンの実際の頻度の乖離度は，所与の値または所与の値の関数値とする
ことを特徴とするパターン評価装置。
【００９２】
（付記６） 付記１から付記５までのいずれかに記載のパターン評価装置において，
前記パターン推定頻度計算手段は，パターンを構成する要素の並び順を考慮する場合には，前記算出したサブパターンについての前記評価対象のパターンの推定頻度または前記算出したスーパーパターンについての前記評価対象のパターンの推定頻度をそれぞれパターンの並び順の場合の数で割った値をサブパターンについての前記評価対象のパターンの推定頻度またはスーパーパターンについての前記評価対象のパターンの推定頻度として算出する
ことを特徴とするパターン評価装置。
【００９３】
（付記７） サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価をコンピュータによって行うパターン評価処理方法であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算ステップと，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成ステップと，
前記パターン頻度計算ステップにより算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算ステップにより算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算ステップと，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算ステップと，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価ステップとを有する
ことを特徴とするパターン評価処理方法。
【００９４】
（付記８） サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのパターン評価処理プログラムであって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのパターン評価処理プログラム。
【００９５】
（付記９） サブパターンおよびスーパーパターンの頻度を用いた有意義度に基づくパターンの評価処理を，コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって，
要素の組で構成される複数のパターンについて頻度を算出するパターン頻度計算処理と，
評価対象のパターンから一部の要素を取り除いたサブパターンと，前記評価対象のパターンに要素を追加したスーパーパターンとを生成するサブパターン／スーパーパターン生成処理と，
前記パターン頻度計算処理により算出された前記サブパターンの頻度に基づいて前記サブパターンについての前記評価対象のパターンの推定頻度を算出し，前記パターン頻度計算処理により算出された前記スーパーパターンの頻度に基づいて前記スーパーパターンについての前記評価対象のパターンの推定頻度を算出するパターン推定頻度計算処理と，
前記算出されたサブパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度と前記算出されたスーパーパターンについての前記評価対象のパターンの推定頻度からの前記評価対象のパターンの実際の頻度の乖離度に関する任意の統計値を前記評価対象のパターンの有意義度として算出するパターン有意義度計算処理と，
前記算出された有意義度に基づいて前記評価対象のパターンを評価するパターン評価処理とを，
コンピュータに実行させるためのプログラムを記録したことを特徴とするパターン評価処理プログラム記録媒体。
【００９６】
【発明の効果】
本発明のパターン評価装置によって， 要素の組で構成されるパターン群について， データベース内の頻度に関して相関の低いパターン， および互いに強い相関を持つ要素の集合の一部だけを取り出した冗長なパターンを除去することができる。したがって，本発明によれば，要素の組で構成されるパターン群について，互いに相関を持つ要素を全て含み，それらと相関のない要素を含まない，要素間の関係を表わすのに必要十分なパターンのみを選択することが可能となる。
【図面の簡単な説明】
【図１】本発明のパターン評価装置の構成例を示す図である。
【図２】本発明のパターン評価処理フローの一例を示す図である。
【図３】商品購買履歴データベースを示す図である。
【図４】パターン頻度情報データベースを示す図である。
【図５】各推定頻度からのパターンの実際の頻度の乖離度の計算を示す図である。
【図６】有意義度上位のパターン群を示す図である。
【図７】パターン頻度情報データベースを示す図である。
【図８】最小サポート値が２の場合の有意義度上位のパターン群を示す図である。
【図９】要素の並び順を考慮した状態列データベースの一例を示す図である。
【図１０】状態列上で要素を跳び跳びにつなげて生成されるパターンの一例を示す図である。
【図１１】要素の並び順を考慮したパターン頻度情報データベースを示す図である。
【符号の説明】
１ パターン評価装置
１１ 処理制御部
１２ パターン頻度計算部
１３ サブパターン／スーパーパターン生成部
１４ パターン推定頻度計算部
１５ パターン有意義度計算部
１６ パターン評価部
１７ 評価結果出力処理部
１８ 入力装置
１９ 出力装置
２０ 状態列データベース
２１ パターン頻度情報データベース[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a pattern evaluation apparatus, a pattern evaluation processing method, a pattern evaluation processing program, and a program recording medium for evaluating a plurality of patterns composed of a set of elements. It relates to methods related to the analysis of status column data such as logs, stock prices and time series data of temperature.
[0002]
[Prior art]
Finding a set of elements that appear in a lot of data from POS data and Web access logs, that is, patterns, is an important issue in many fields such as database marketing and customer information management (CRM). In order to solve this, a method such as Priori has been proposed (see, for example, Non-Patent Document 1).
[0003]
However, with these methods, a very large number of patterns are discovered, and it is extremely difficult to select patterns with high utility value from them. Therefore, it is possible to evaluate the goodness of the found patterns, remove statistically meaningless patterns and redundant patterns based on them, and select a relatively small number of patterns representing various features in the database. Necessary.
[0004]
Patterns that appear much more frequently than estimated from the frequency of the individual elements that make up the pattern (for example, the purchase frequency of individual products) in the database are based on the point of view that they are particularly valuable. Conventionally, a method for evaluating the usefulness of a pattern by comparing the estimated frequency from the sub-pattern that is a part and the actual frequency of the pattern has been used (for example, Non-Patent Documents 2, 3, 4, 5, 6). reference).
[0005]
Also, for example, in a related patent application (Application No .: Japanese Patent Application No. 2002-347241, “Evaluation device for state sequence pattern based on unexpectedness”), a pattern is assumed by using the frequency of partial patterns for a pattern to be analyzed. The frequency is calculated, and the usefulness of the pattern is defined by a function of the assumed frequency and the actual frequency in the database.
[0006]
[Non-Patent Document 1]
Rakesh Agrawal and Ramakrishnan Srikant: 'Fast algorithms for mining association rules'. In Proceedings of the International Conference on Very Large Data Bases, pp. 487-499, 1994.
[Non-Patent Document 2]
Guozhu Dong and Jinyan Li: 'Interesting of Discovered Association Rules in Terms of Neighborhood-Based Unexpectedness'. Proc. of the Second Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 1998.
[Non-Patent Document 3]
Robert J. et al. Hilderman and Howard J. et al. Hamilton: 'Knowledge discovery and interestingness measures: a survey'. Department of Computer Science, University of Regina, CS 99-04, 1999.
[Non-Patent Document 4]
Farhad Hussain, Huan Liu and Hongjun Lu: 'Relativistic measure for mining interesting rules'. Proc. of PKDD-2000 Workshop on Knowledge Management Theory and Applications, 2000.
[Non-Patent Document 5]
Szymon Jaroszewicz and Dan A.M. Simonici: 'A General Measurement of Rule Interferenceness'. Proc. of the Fifth European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD), 2001.
[Non-Patent Document 6]
Pang-Ning Tan, Vipin Kumar and Jaideep Srivastava: 'Selecting the Right Interstitial for Measurement Patterns'. Proc. of the Eight ACM SIGKDD Int'l Conference on Knowledge Discovery and Data Mining (KDD), 2002.
[0007]
[Problems to be solved by the invention]
However, the above-mentioned conventional method of comparing with sub-patterns may give a high evaluation value to redundant pattern groups, which is a factor in reducing the efficiency of pattern discovery. For example, when products A, B, and C are always bought together, only the pattern {A, B, C} should be evaluated as useful, but in the prior art, the patterns {A, B}, {A, C }, {B, C} also have high evaluation values, and there is a problem that they are evaluated as useful.
[0008]
The present invention solves the above-mentioned problems of the prior art and expresses a relationship between elements that includes all elements that are correlated with each other and does not include elements that are not correlated with each other in the pattern group composed of element sets. It is an object of the present invention to provide a pattern evaluation method capable of selecting only necessary and sufficient patterns.
[0009]
[Means for Solving the Problems]
In order to solve this problem, in the present invention, the estimated frequency of the pattern S to be evaluated is added to the frequency of the sub-pattern obtained by removing some elements from the pattern S, and the elements are added to the pattern S. It is calculated from the frequency of the super pattern, and the goodness of the pattern, that is, the significance level, is evaluated according to how much the actual frequency of the pattern S is larger than the estimated value.
[0010]
If the pattern to be evaluated is a combination of sub-patterns that are not correlated with each other, the estimated frequency calculated from those sub-patterns is almost equal to the actual frequency, so the evaluation value for that pattern is small . On the other hand, the actual frequency is smaller than the estimated frequency calculated from the super pattern with the remaining elements added to the pattern that extracts only a part of the set of elements that are strongly correlated with each other. Becomes smaller. As a result, it is possible to select only the patterns that are necessary and sufficient to represent the relationship between elements, including all elements that are correlated with each other and not including elements that are not correlated with them.
[0011]
That is, the present invention uses a sub-pattern frequency obtained by removing some elements from a pattern, a super-pattern frequency obtained by adding elements to the pattern, and an element frequency for a plurality of patterns composed of element sets. The pattern estimation frequency is calculated for each sub-pattern group formed by removing various elements from the pattern, and for the super-pattern group formed by adding various elements to the pattern. The actual frequency divergence is calculated, and the pattern is evaluated using any statistical value related to the actual frequency divergence from the estimated frequency in the sub-pattern group and super-pattern group as the significance of the pattern. To do.
[0012]
In the above method, the pattern estimation frequency for the sub-pattern is the product of the frequency of the sub-pattern and the frequency of the removed element divided by the total number of state columns, and the pattern estimation frequency for the super-pattern is The product is a value obtained by dividing the product of the super pattern frequency and the total number of state columns by the frequency of the added element.
[0013]
In the above method, the arc tangent of the ratio between the actual frequency of the pattern and the estimated frequency can be used as the degree of deviation of the actual frequency of the pattern from each estimated frequency.
[0014]
In the above method, as a statistical value regarding the deviation of the actual frequency of the pattern from the estimated frequency in the sub-pattern group and the super-pattern group, the minimum value of the deviation of the actual frequency of the pattern from the estimated frequency in the sub-pattern group, The sum of the deviation of the actual frequency of the pattern from the estimated frequency in the super pattern group can be used.
[0015]
In the above method, when the frequency of the super pattern is lower than a given threshold, the deviation of the actual frequency of the pattern from the estimated frequency for the super pattern is the given value, or the given value. Function value.
[0016]
In addition, in the above method, when the arrangement order of the elements constituting the pattern is also taken into consideration, the estimated frequency calculated by dividing the estimated frequency calculated by the above method by the number of pattern arrangement orders can be used as the estimated frequency. .
[0017]
By using the present invention, a pattern group composed of a set of elements includes all the elements that are correlated with each other, and does not include elements that are not correlated with them. Can be selected.
[0018]
Pattern evaluation processing based on significance using the sub-pattern and super-pattern frequencies can be realized by a computer and a software program, and the program is recorded on a computer-readable recording medium and provided. Can also be provided through a network.
[0019]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings. FIG. 1 is a diagram showing a configuration example of a pattern evaluation apparatus according to the present invention. In FIG. 1, reference numeral 1 denotes a pattern evaluation apparatus including a computer such as a CPU and a memory, and a software program for pattern evaluation. 11 is a processing control unit that controls the entire pattern evaluation apparatus 1, 12 is a pattern frequency calculation unit that calculates the frequency of patterns in the state sequence database, and 13 is a sub-pattern / super-pattern generation that generates a sub-pattern group and a super-pattern group. And 14 are a pattern estimation frequency calculation unit that calculates the estimation frequency of the pattern to be evaluated, and 15 is a pattern significance calculation unit that calculates the significance of the pattern to be evaluated.
[0020]
16 is a pattern evaluation unit that evaluates a pattern based on significance calculated for each pattern, 17 is an evaluation result output processing unit that outputs a pattern evaluation result, 18 is an input device, 19 is an output device, and 20 is an analysis target. The state column database 21 stores the state column data, and 21 is a pattern frequency information database in which the calculated frequency of the pattern in the state column database 20 is stored.
[0021]
FIG. 2 is a diagram showing an example of the pattern evaluation processing flow of the present invention. First, state column data is read from the state column database 20 in which state column data to be analyzed such as POS data and Web access logs is stored (step S1). Next, the frequency in the state string database 20 is calculated by the pattern frequency calculation unit 12 for various patterns composed of elements of the state string (step S2). The frequency information is stored in the pattern frequency information database 21.
[0022]
Next, the sub pattern / super pattern generation unit 13 generates a sub pattern group obtained by removing some elements from the pattern S to be evaluated, and a super pattern group in which elements are added to the pattern S (step S3). The pattern estimation frequency calculation unit 14 calculates the estimation frequency of the pattern S from the frequency of each sub-pattern and super pattern (step S4).
[0023]
The pattern significance level calculation unit 15 calculates the divergence degree of the actual frequency of the pattern S from each estimated frequency, and determines a predetermined divergence degree of the actual frequency of the pattern S from the estimated frequency in the sub-pattern group and the super pattern group. The statistical value is calculated as the significance level of the pattern S (step S5).
[0024]
Based on the significance calculated for each pattern, the pattern evaluation unit 16 evaluates the pattern (step S6), and the evaluation result output processing unit 17 outputs the result (step S7).
[0025]
In the embodiment of the present invention, the frequency of elements or patterns in the state string database 20 is appropriately defined according to the situation. For example, it is defined as the number of state strings including the element or pattern in the state string database 20, or when the element or pattern can appear multiple times on the state string, it is defined as the appearance frequency of the element or pattern itself. It is possible.
[0026]
Appropriate methods shall be applied to generate sub-patterns and super-patterns from the pattern to be evaluated, depending on the situation. For example, you can create a sub-pattern by removing one element from the pattern, and generate a super pattern by adding one element to the pattern, or create a sub-pattern by removing up to two elements from the pattern, A method of generating a super pattern by adding up to two elements to a pattern is possible.
[0027]
When all types of elements (element set) are {A, B, C, D, E, F} and the pattern to be evaluated is {A, B, C, D}, the former method generates Sub-pattern group is obtained by removing elements A, B, C, D from {A, B, C, D}
{B, C, D}, {A, C, D}, {A, B, D}, {A, B, C}
The generated super pattern group is obtained by adding elements E and F to {A, B, C, D}.
{A, B, C, D, E}, {A, B, C, D, F}
It is.
[0028]
In the latter method of removing or adding up to two, the sub-pattern group generated from the pattern {A, B, C, D} is
{B, C, D}, {A, C, D}, {A, B, D}, {A, B, C}, {C, D}, {B, D}, {B, C}, {A, D}, {A, C}, {A, B}
And the generated super pattern group is
{A, B, C, D, E}, {A, B, C, D, F}, {A, B, C, D, E, F}
It is.
[0029]
The estimated frequency of the pattern to be evaluated from the frequency of each sub-pattern and super-pattern shall be defined by an appropriate function. For example, the sub-pattern S of the pattern S to be evaluated ⁻ Frequency of pattern S (^ f (S | S ⁻ ) Represents the sub-pattern S ⁻ Frequency f (S ⁻ ) And removed elements (S \ S ⁻ Frequency f (S \ S) ⁻ ) And the total number of state columns N in the state column database 20,
^ F (S | S ⁻ ) = F (S ⁻ ) ・ F (S \ S ⁻ ) / N
Super pattern S ⁺ Frequency of pattern S (^ f (S | S ⁺ ) Represents the super pattern S ⁺ Frequency f (S ⁺ ) And added elements (S ⁺ Frequency f (S ⁺ \ S) and the total number N of state columns in the state column database 20,
^ F (S | S ⁺ ) = F (S ⁺ ) ・ N / f (S ⁺ \ S)
It is possible to define in
[0030]
Alternatively, if the frequency of an element is lower than a given threshold (eg, 1% of the total number of state columns), the calculation of the estimated frequency of the pattern will give the given element frequency (eg, all states) A method using a value of 0.8% of the number of columns) is also possible.
[0031]
The actual frequency divergence d (f (S), ^ f (S | •)) from each estimated frequency increases as the value of f (S) increases from ^ f (S | •). It shall be defined by an appropriate function that takes a value. For example, taking the ratio of the actual frequency f (S) of the pattern to the estimated frequency ^ f (S |
d (f (S), ^ f (S |.)) = f (S) / ^ f (S |.)
Or define the difference between the two,
d (f (S), ^ f (S |.)) = (f (S)-^ f (S |.)) / ^ f (S |.)
It is possible to define in
[0032]
The significance level of the pattern S is also defined by an appropriate statistical value regarding the degree of deviation of the actual frequency of the pattern S from the estimated frequency in the sub pattern group and the super pattern group. For example, it is defined by the average value of the divergence degree d (f (S), ^ f (S |)) in the sub pattern group and the super pattern group, or d (f (S), ^ f (S |))) Defined by the minimum value of d, defined by the maximum value of d (f (S), ^ f (S |)), or d (f (S), ^ f (S | And the sum of the minimum value of d and the minimum value of d (f (S), ^ f (S |.)) In the super pattern group.
[0033]
Based on the significance calculated for each pattern, the method for evaluating the pattern and outputting the evaluation result shall apply the appropriate method according to the situation. For example, it is possible to sort patterns in descending order of significance and output the top 100 patterns, output the top 1% pattern, or output patterns that exceed a predetermined threshold of significance. .
[0034]
【Example】
[First embodiment]
Hereinafter, the operation of the pattern evaluation apparatus according to the first embodiment of the present invention will be described by taking the commodity purchase history database shown in FIG.
[0035]
The product purchase history database shown in FIG. 3 includes product purchase histories for six customers. A,. . . , E are product names and each customer T ₁ ,. . . , T ₆ Represents a set of products purchased by a set of product names. For example, customer T ₁ Purchases goods A, B, C, D, E and customer T ₂ Has purchased goods D and E.
[0036]
Based on this product purchase history database, three customers have purchased product A, three customers have purchased products A and B, three customers have purchased products A, B and C, and products A and B and Two customers have purchased C and D. . . Thus, by counting the number of customers who have purchased each combination of products, the pattern frequency information database 21 shown in FIG. 4 is generated for the product purchase pattern that is a subset of the set of purchased products.
[0037]
Next, the pattern significance level calculation procedure will be described using the pattern {A, B, C} as an example.
[0038]
(1) Sub-pattern generation
A sub-pattern group is generated by removing one element from the pattern to be evaluated. For example, the elements A 1, B 2, and C are removed from the pattern {A, B, C}, respectively, and sub-patterns {B, C}, {A, C}, {A, B} are generated. In the first embodiment, a sub-pattern is generated by removing one element from a pattern, but a sub-pattern may be generated by removing two or more elements.
[0039]
(2) Super pattern generation
A super pattern group is generated by adding one element to the pattern to be evaluated. For example, elements D 1 and E are respectively added to the pattern {A, B, C}, and super patterns {A, B, C, D}, {A, B, C, E} are generated. In the first embodiment, a super pattern is generated by adding one element to a pattern, but a super pattern may be generated by adding two or more elements.
[0040]
(3) Calculation of pattern estimation frequency for each sub-pattern
In the first embodiment, the sub-pattern S ⁻ The estimated frequency ^ f (S | S ⁻ ), Sub-pattern S ⁻ Frequency f (S ⁻ ) And removed element S \ S ⁻ Frequency f (S \ S ⁻ ) And the total number of state columns N in the product purchase history database,
^ F (S | S ⁻ ) = F (S ⁻ ) ・ F (S \ S ⁻ ) / N
It shall be defined in
[0041]
Therefore, the estimated frequencies of the patterns {A, B, C} for the sub-patterns {B, C}, {A, C}, {A, B} are

It becomes.
[0042]
(4) Calculation of pattern estimation frequency for each super pattern
In the first embodiment, the super pattern S ⁺ The estimated frequency ^ f (S | S ⁺ ), Super Pattern S ⁺ Frequency f (S ⁺ ) And added elements (S ⁺ \ S) frequency f (S ⁺ \ S) and the total number of state columns N in the product purchase history database,
^ F (S | S ⁺ ) = F (S ⁺ ) ・ N / f (S ⁺ \ S)
It shall be defined in
[0043]
Therefore, the estimated frequencies of the patterns {A, B, C} with respect to the super patterns {A, B, C, D}, {A, B, C, E} are respectively

It becomes.
[0044]
(5) Calculation of the deviation of the actual frequency of the pattern from each estimated frequency
In the first embodiment, the deviation d (f (S), ^ f (S |)) of the actual frequency f (S) of the pattern from each estimated frequency ^ f (S |
d (f (S), ^ f (S |.)) = arctan (f (S) / ^ f (S |.))
It shall be defined in
[0045]
Here, arctan (r) represents the arc tangent of the real number r. arctan (r) is a monotonically increasing function of r, and when r ≧ 0, 0 ≦ arctan (r) ≦ π / 2.
[0046]
arctan (f (S) / ^ f (S |.)) corresponds to the inclination angle of a right triangle whose base is ^ f (S |.) and height is f (S), as shown in FIG. . The inclination angle arctan (f (S) / ^ f (S |.)) Becomes larger as the actual frequency f (S) is larger than the estimated frequency ^ f (S |.) Of the pattern.
[0047]
Patterns {A, B, C for subpatterns {B, C}, {A, C}, {A, B}, and super patterns {A, B, C, D}, {A, B, C, E} } Of the actual frequency f ({A, B, C}) from the estimated frequency of

It becomes.
[0048]
(6) Calculation of pattern significance
In the first embodiment, the significance level I (S) of the pattern S is the sum of the minimum value of the divergence degree in the sub-pattern group and the minimum value of the divergence degree in the super pattern group, that is,
I (S) = min {d (f (S), ^ f (S | S ⁻ )); S ⁻ Is a given subpattern of S} + min {d (f (S), ^ f (S | S ⁺ )); S ⁺ Is a given super pattern of S}
It shall be defined in
[0049]
At this time, the significance of the pattern {A, B, C} is
I ({A, B, C}) = 1.107 +0.785 = 1.892
It becomes.
[0050]
For the pattern S for which no super pattern exists in the pattern frequency information database 21, for example, ^ f (S | S ⁺ ) ≡0, and arctan (x / 0) = π / 2 (= 1.570), x> 0,
I (S) = min {d (f (S), ^ f (S | S ⁻ )); S ⁻ Is a given subpattern of S} + π / 2
It shall be defined as
[0051]
(7) Pattern evaluation
In the first embodiment, the significance level is calculated for patterns configured with the number of elements in a predetermined range in the pattern frequency information database 21, the pattern groups are sorted in descending order of significance level, The number of patterns (or a predetermined ratio) shall be output.
[0052]
In the pattern frequency information database 21 in FIG. 4, the significance levels are calculated for pattern groups with 2 to 4 elements, and the top six patterns are shown in FIG. 6 in which the pattern groups are sorted in descending order of significance.
[0053]
When comparing only sub-patterns as in the conventional method, that is, min {d (f (S), ^ f (S | S ⁻ ))} When evaluating a pattern, {B, C}, {A, C}, {A, B} are given an evaluation value equal to {A, B, C}. This has a higher evaluation value than {D, E} or {A, B, C, D}.
[0054]
However, as can be seen from the original merchandise purchase history database shown in FIG. 3, since the merchandise A, B, and C are always bought together, the pattern {A, B, C} is essentially replaced with {B, C}. , {A, C}, {A, B}, and {A, B, C}, {B, C}, {A, C}, { It is not appropriate to give an evaluation value equal to A, B}. Moreover, in the conventional method, the evaluation of different types of patterns {D, E}, {A, B, C, D} is relatively low, and various features of the database can be expressed with relatively few patterns. Is also not suitable.
[0055]
On the other hand, the pattern evaluation method according to the first embodiment has a significance level I (S) that combines the comparison with the sub-pattern and the comparison with the super-pattern,
I (S) = min {d (f (S), ^ f (S | S ⁻ ))} + Min {d (f (S), ^ f (S | S ⁺ ))}
Thus, the evaluation value of the redundant pattern {B, C}, {A, C}, {A, B} can be kept low.
[0056]
[Second Embodiment]
Next, a second embodiment of the present invention will be described. In general, since the number of patterns in the state sequence database 20 is enormous, it is not realistic to count the frequencies of all patterns and register them in the pattern frequency information database 21. Therefore, normally, only the patterns whose frequency is equal to or higher than a predetermined minimum support value are counted and registered in the pattern frequency information database 21 as in the priori method.
[0057]
FIG. 7 shows a pattern frequency information database 21 when the product purchase history database shown in FIG. 3 is taken as an example of the state column database 20 and the product purchase patterns are counted with the minimum support value “2” for this product purchase history database. In FIG. 7, a pattern with a middle line represents a pattern whose frequency is less than the minimum support value and is not registered in the pattern frequency information database 21.
[0058]
In this case, if a pattern group with 2 to 4 elements is to be evaluated for significance, 12 patterns with a frequency equal to or greater than the minimum support value (no underline) are evaluated. At this time, as shown in {A, B, C, D}, although the superstring exists in the state sequence database (product purchase history database) 20 with less than the minimum support value, the pattern frequency information database 21 has a super pattern. There may be a pattern where no pattern exists.
[0059]
In the above-described first embodiment, ^ f (S | S ⁺ ) ≡≡0,
min {d (f (S), ^ f (S | S ⁺ )); S ⁺ Is a given super pattern of S} = arctan (x / 0) = π / 2
It was defined as
[0060]
In the second embodiment, even if there is no super pattern in the pattern frequency information database 21, considering the possibility that a super pattern exists in the status column database (product purchase history database) 20 below the minimum support value. The following introduces a method for calculating the deviation of the actual frequency of the pattern from the estimated frequency for the super pattern.
N is the number of all state columns in the state column database (product purchase history database) 20.
-Let M be all kinds of elements (element set). For example, M = {A, B, C, D, E}.
・ F ^* Is the frequency of a given virtual super pattern when no super pattern exists in the pattern frequency information database 21. For example, when the minimum support value is 2, f ^* = (Minimum support value) / 2 = 1.
[0061]
The estimated frequency of the pattern S for the super pattern when there is no super pattern in the pattern frequency information database 21 is expressed as the virtual super pattern frequency f. ^* And the frequency of the maximum frequency element in the pattern frequency information database 21 is defined as follows.
[0062]
[Expression 1]

[0063]
At this time, the degree of deviation from the actual frequency of the pattern S is
[0064]
[Expression 2]

[0065]
The significance level of the pattern when the super pattern does not exist in the pattern frequency information database 21 is defined as follows.
[0066]
I (S) = min {d (f (S), ^ f (S | S ⁻ ))} + D (f (S), ^ f (S | ⁺ )
Here, {D, E} and {A, B, C, D} having no super pattern among 12 patterns to be evaluated in the pattern frequency information database 21 shown in FIG. 7 in the case of the minimum support value “2”. , ^ F (S | ⁺ ) And I (S) are shown below. The total number of state columns is N = 6, and the element set is M = {A, B, C, D, E}. The frequency of the virtual super pattern is f ^* = (Minimum support value) / 2 = 1.
(1) Pattern {D, E}:
[0067]
[Equation 3]

[0068]
From the first example,
min {d (f ({D, E})), ^ f ({D, E} | {D, E} ⁻ ))} = 0.844
Therefore, I ({D, E}) = 0.844 + 0.982 = 1.826
(2) Pattern {A, B, C, D}:
[0069]
[Expression 4]

[0070]
From the first example,
min {d (f ({A, B, C, D}), ^ f ({A, B, C, D} | {A, B, C, D}) ⁻ ))} = 0.785
Therefore, I ({A, B, C, D}) = 0.785 + 0.927 = 1.712
FIG. 8 shows the top six patterns obtained by calculating the significance for the 12 patterns to be evaluated in FIG. 7 according to the method of the second embodiment and sorting the pattern group in descending order of significance.
[0071]
In FIG. 8, min {d (f (S), ^ f (S | S ⁺ ))} Column is a value obtained by calculating the minimum value of the actual divergence from the pattern estimation frequency in the super pattern group according to the method of the first embodiment (that is, π / 2 = 1.570), d (f (S), ^ f (S | ⁺ )) Column represents values calculated according to the method of the second embodiment.
[0072]
I ₁ In the (S) column, the significance calculated according to the method of the first embodiment that does not use the frequency of the virtual super pattern is I ₂ The column (S) represents a value calculated according to the method of the second embodiment using the frequency of the virtual super pattern.
[0073]
I ₁ (S) = min {d (f (S), ^ f (S | S ⁻ ))} + Min {d (f (S), ^ f (S | S ⁺ ))}
I ₂ (S) = min {d (f (S), ^ f (S | S ⁻ ))} + D (f (S), ^ f (S | ⁺ ))
When it is important to emphasize that there is no super pattern in the pattern frequency information database 21, the significance level I based on the method of the first embodiment is used. ₁ (S) is suitable. On the other hand, when it is not particularly important that the super pattern does not exist, the significance level I based on the method of the second embodiment is determined. ₂ (S) is suitable.
[0074]
[Third embodiment]
Next, a third embodiment of the present invention will be described. In the first and second embodiments described above, the pattern to be evaluated is a set of elements constituting the status string (for example, a combination of purchased products, a combination of URLs that have been accessed, etc.) However, there are cases where it is desired to evaluate the pattern of the order of elements on the status column (for example, purchase order of products, access order of URLs, etc.).
[0075]
Therefore, as a third example, a method for calculating the significance level of a pattern considering the order of elements on the state sequence is shown. FIG. 9 shows user T ₁ , T ₂ ,. . . , T ₁₀ It is an example of the state column database 20 showing the access order of Web URL by. One URL is represented by three alphanumeric characters. For example, user T ₁ Are XMK, XQK, XQK, XQK, XMK,. . . URLs are accessed in this order.
[0076]
In the third embodiment, a pattern is generated by jumping elements on one state sequence. However, the maximum length of the pattern is L, and the pattern is generated so as to be included in a partial sequence of length W (window size) on one state sequence as shown in FIG.
[0077]
The number of state strings in the state string database 20 including the patterns generated in this way is defined as the pattern frequency. FIG. 10 shows a pattern generation example when the maximum pattern length = 5 and the window size = 12.
[0078]
FIG. 11 shows a pattern frequency information database 21 generated with the maximum pattern length = 5 and the window size = 25 for the state sequence database 20 shown in FIG.
[0079]
Estimated frequency of patterns when considering the order of patterns ^e f (S | •) is obtained from the estimated frequency ^ f (S | •) calculated by paying attention only to the set of elements in the method shown in the first or second embodiment. Divided by the number of cases in order, it shall be defined as follows:
[0080]
^e f (S | S ⁻ ) = (N (S ⁻ )!・ N (S \ S ⁻ )! / N (S)! ) ・ ^ F (S | S ⁻ )
^e f (S | S ⁺ ) = (N (S ⁺ )! / N (S)!・ N (S ⁺ \ S)! ) ・ ^ F (S | S ⁺ )
Here, n (S) represents the number of elements of the pattern S.
[0081]
In particular, if the number of elements to be removed from the pattern when generating a subpattern is 1 and the number of elements to be added to the pattern when generating a superpattern is 1,
n (S ⁻ )!・ N (S \ S ⁻ )! / N (S)! = (N (S) -1)! / N (S)! = 1 / n (S)
n (S ⁺ )! / N (S)!・ N (S ⁺ \ S)! = N (S ⁺ )! / N (S)! = N (S ⁺ )
Therefore, the pattern estimation frequency when considering the pattern order is expressed by the following equation.
[0082]
^e f (S | S ⁻ ) = (1 / n (S)) · ^ f (S | S ⁻ )
^e f (S | S ⁺ ) = N (S ⁺ ) ・ ^ F (S | S ⁺ )
For example, for a pattern 3 of length S = {YEK, XNK, X3K}, sub-pattern S ⁻ = The element X3K to be added to create the original pattern S from {YEK, XNK} ⁻ Against
・ Added before YEK,
Added between YEK and XNK,
・ Added after XNK,
There are three possible cases.
[0083]
Among them, the last one is equal to the pattern S. Therefore, the estimated frequency when considering the order of elements is the estimated frequency ^ f (S | S ⁻ ) Is divided by the number of elements to be added (that is, the length n (S) of the pattern S).
[0084]
Similarly, from pattern S to super pattern S ⁺ = YnK, YEK, XNK, X3K} The element YnK to be added to create the pattern S
・ Added before YEK,
Added between YEK and XNK,
・ Added between XNK and X3K,
・ Added after X3K,
There are four possible cases.
[0085]
Super pattern S in it ⁺ Is the first one to be equal to Therefore, the estimated frequency when considering the order of elements is the estimated frequency ^ f (S | S ⁺ ) Is the number of elements added to the pattern S (ie, the super pattern S ⁺ Length n (S ⁺ It is reasonable to multiply the value by)).
[0086]
As can be understood from the above, the features of the embodiment of the present invention are described as follows.
[0087]
(Supplementary note 1) A pattern evaluation device based on significance using sub-pattern and super-pattern frequencies,
A pattern frequency calculation means for calculating the frequency for a plurality of patterns composed of element sets;
A sub-pattern / super-pattern generating means for generating a sub-pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation means, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation means Pattern estimation frequency calculating means for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation means for calculating an arbitrary statistical value related to the actual frequency divergence of the pattern to be evaluated as the significance of the pattern to be evaluated;
Pattern evaluation means for evaluating the pattern to be evaluated based on the calculated significance level.
A pattern evaluation apparatus characterized by that.
[0088]
(Appendix 2) In the pattern evaluation apparatus described in Appendix 1,
The pattern estimation frequency calculation means includes:
A value obtained by dividing the product of the frequency of the sub-pattern and the frequency of the element removed from the pattern to be evaluated by the total number of state columns is calculated as the estimated frequency of the pattern to be evaluated for the sub-pattern,
A value obtained by dividing the product of the frequency of the super pattern and the total number of state columns by the frequency of the element added to the pattern to be evaluated is calculated as the estimated frequency of the pattern to be evaluated for the super pattern.
A pattern evaluation apparatus characterized by that.
[0089]
(Supplementary note 3) In the pattern evaluation apparatus according to Supplementary note 1 or Supplementary note 2,
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the sub-pattern is the actual frequency of the pattern to be evaluated and the pattern of the evaluation target for the sub-pattern. Is the arc tangent of the ratio to the estimated frequency,
The degree of deviation of the actual frequency of the evaluation target pattern from the estimated frequency of the evaluation target pattern for the super pattern is the actual frequency of the evaluation target pattern and the evaluation target pattern for the super pattern. The arc tangent of the ratio to the estimated frequency
A pattern evaluation apparatus characterized by that.
[0090]
(Supplementary note 4) In the pattern evaluation apparatus according to any one of Supplementary note 1 to Supplementary note 3,
The actual frequency of the evaluation target pattern from the estimation frequency of the evaluation target pattern for the super pattern and the degree of deviation of the actual frequency of the evaluation target pattern from the estimation frequency of the evaluation target pattern for the subpattern The statistical value related to the frequency divergence degree is the minimum value of the actual frequency divergence degree of the evaluation target pattern from the estimation frequency of the evaluation target pattern for the sub-pattern, and the evaluation target for the super pattern. This is the sum of the deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern and the minimum value
A pattern evaluation apparatus characterized by that.
[0091]
(Supplementary note 5) In the pattern evaluation apparatus according to any one of Supplementary note 1 to Supplementary note 4,
When the frequency of the super pattern calculated by the pattern frequency calculation means is lower than a given threshold value, the degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency for the super pattern is given by The value of or a function value of the given value
A pattern evaluation apparatus characterized by that.
[0092]
(Appendix 6) In the pattern evaluation apparatus according to any one of Appendix 1 to Appendix 5,
The pattern estimation frequency calculation means, when considering the arrangement order of elements constituting the pattern, the estimated frequency of the evaluation target pattern for the calculated sub-pattern or the evaluation target of the calculated super pattern A value obtained by dividing the estimated frequency of the pattern by the number in the case of the arrangement order of the patterns is calculated as the estimated frequency of the pattern to be evaluated for the sub-pattern or the estimated frequency of the pattern to be evaluated for the super pattern.
A pattern evaluation apparatus characterized by that.
[0093]
(Supplementary note 7) A pattern evaluation processing method in which a computer evaluates a pattern based on significance using the frequency of sub-patterns and super patterns,
A pattern frequency calculation step for calculating a frequency for a plurality of patterns composed of element sets;
A sub-pattern / super-pattern generation step for generating a sub-pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculating step, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculating step A pattern estimation frequency calculating step for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern A pattern significance calculation step for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation step for evaluating the pattern to be evaluated based on the calculated significance level.
A pattern evaluation processing method characterized by the above.
[0094]
(Supplementary Note 8) A pattern evaluation processing program for causing a computer to execute pattern evaluation processing based on significance using sub-pattern and super-pattern frequencies,
Pattern frequency calculation processing for calculating the frequency for a plurality of patterns composed of element sets;
A sub pattern / super pattern generation process for generating a sub pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation process, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation process Pattern estimation frequency calculation processing for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation processing for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation process for evaluating the pattern to be evaluated based on the calculated significance level,
A pattern evaluation processing program to be executed by a computer.
[0095]
(Supplementary Note 9) A computer-readable recording medium recording a program for causing a computer to execute pattern evaluation processing based on significance using sub-pattern and super-pattern frequencies,
Pattern frequency calculation processing for calculating the frequency for a plurality of patterns composed of element sets;
A sub pattern / super pattern generation process for generating a sub pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation process, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation process Pattern estimation frequency calculation processing for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation processing for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation process for evaluating the pattern to be evaluated based on the calculated significance level,
A pattern evaluation processing program recording medium having recorded thereon a program to be executed by a computer.
[0096]
【The invention's effect】
The pattern evaluation device of the present invention removes patterns that are composed of element groups from patterns that have a low correlation with respect to the frequency in the database and redundant patterns that extract only a part of a set of elements that have a strong correlation with each other. can do. Therefore, according to the present invention, a pattern group composed of a set of elements includes all the elements that are correlated with each other, and does not include elements that are not correlated with them. It becomes possible to select only.
[Brief description of the drawings]
FIG. 1 is a diagram showing a configuration example of a pattern evaluation apparatus according to the present invention.
FIG. 2 is a diagram showing an example of a pattern evaluation process flow of the present invention.
FIG. 3 is a diagram showing a product purchase history database.
FIG. 4 is a diagram showing a pattern frequency information database.
FIG. 5 is a diagram illustrating calculation of a deviation degree of an actual frequency of a pattern from each estimated frequency.
FIG. 6 is a diagram showing a pattern group with higher significance.
FIG. 7 is a diagram showing a pattern frequency information database.
FIG. 8 is a diagram showing a pattern group of higher significance when the minimum support value is 2. FIG.
FIG. 9 is a diagram illustrating an example of a state string database in consideration of the arrangement order of elements.
FIG. 10 is a diagram illustrating an example of a pattern generated by jumping an element on a state sequence.
FIG. 11 is a diagram showing a pattern frequency information database in consideration of the arrangement order of elements.
[Explanation of symbols]
1 Pattern evaluation device
11 Processing control unit
12 Pattern frequency calculator
13 Sub pattern / super pattern generator
14 Pattern estimation frequency calculator
15 Pattern significance calculation section
16 Pattern evaluation section
17 Evaluation result output processing section
18 Input device
19 Output device
20 State column database
21 pattern frequency information database

Claims (5)

A pattern evaluation device based on significance using sub-pattern and super-pattern frequencies,
A pattern frequency calculation means for calculating the frequency for a plurality of patterns composed of element sets;
A sub-pattern / super-pattern generating means for generating a sub-pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation means, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation means Pattern estimation frequency calculating means for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation means for calculating an arbitrary statistical value related to the actual frequency divergence of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation unit comprising: a pattern evaluation unit that evaluates the pattern to be evaluated based on the calculated significance level. The pattern evaluation apparatus according to claim 1,
The pattern estimation frequency calculation means includes:
A value obtained by dividing the product of the frequency of the sub-pattern and the frequency of the element removed from the pattern to be evaluated by the total number of state columns is calculated as the estimated frequency of the pattern to be evaluated for the sub-pattern,
A value obtained by dividing the product of the frequency of the super pattern and the total number of state columns by the frequency of the element added to the pattern to be evaluated is calculated as the estimated frequency of the pattern to be evaluated for the super pattern. Pattern evaluation device. A pattern evaluation processing method that uses a computer to evaluate patterns based on significance using sub-pattern and super-pattern frequencies,
A pattern frequency calculation step for calculating a frequency for a plurality of patterns composed of element sets;
A sub-pattern / super-pattern generation step for generating a sub-pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculating step, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculating step A pattern estimation frequency calculating step for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern A pattern significance calculation step for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
And a pattern evaluation step for evaluating the pattern to be evaluated based on the calculated significance level. A pattern evaluation processing program for causing a computer to execute pattern evaluation processing based on significance using sub-pattern and super-pattern frequencies,
Pattern frequency calculation processing for calculating the frequency for a plurality of patterns composed of element sets;
A sub pattern / super pattern generation process for generating a sub pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation process, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation process Pattern estimation frequency calculation processing for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation processing for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation process for evaluating the pattern to be evaluated based on the calculated significance level,
A pattern evaluation processing program to be executed by a computer. A computer-readable recording medium storing a program for causing a computer to execute pattern evaluation processing based on significance using sub-pattern and super-pattern frequencies,
Pattern frequency calculation processing for calculating the frequency for a plurality of patterns composed of element sets;
A sub pattern / super pattern generation process for generating a sub pattern obtained by removing some elements from the pattern to be evaluated, and a super pattern in which elements are added to the pattern to be evaluated;
Based on the frequency of the sub-pattern calculated by the pattern frequency calculation process, the estimated frequency of the pattern to be evaluated for the sub-pattern is calculated, and based on the frequency of the super pattern calculated by the pattern frequency calculation process Pattern estimation frequency calculation processing for calculating an estimation frequency of the pattern to be evaluated for the super pattern;
The degree of deviation of the actual frequency of the pattern to be evaluated from the estimated frequency of the pattern to be evaluated for the calculated sub-pattern and the estimated frequency of the pattern to be evaluated for the calculated super pattern Pattern significance calculation processing for calculating an arbitrary statistical value related to the actual frequency deviation of the pattern to be evaluated as the significance of the pattern to be evaluated;
A pattern evaluation process for evaluating the pattern to be evaluated based on the calculated significance level,
A pattern evaluation processing program recording medium having recorded thereon a program to be executed by a computer.

Images