- m回の買い物イベント(トランザクション)があったとする
- n種類の商品:
があったとする
- Tは買い物イベントの集合とする。買い物イベントのデータベースとも言う
はT、すべての買い物イベントによって購入されたアイテムの「のべ総数」であり、買い物イベントデータベースの大きさと言う- 商品集合
の部分集合を考える
- の部分集合Kがあったとき、買い物イベントの中には、このKを含むこともあれば含まないこともある
- 買い物イベントのうち、Kを含むものを、Kに関する出現と言い、
と書く
- Kに関する出現()は買い物イベントの部分集合である。その部分集合の要素数(Kを含む買い物イベントの発生した回数)を
と書き、この値が大きいとき、「この出現は頻繁に起きている」と言う意味で、Kは頻出集合と言う
- Kが頻出集合であるとき、その程度を定めるとよい。
であるときに、Kを頻出集合であると言うことにするとしたときに、
を頻出集合のサポートと呼ぶ
- Kが頻出集合であるとき、Kの部分集合も頻出集合である。逆にKにどんな要素を付け加えてもそれが頻出集合ではないようなKというものもある。そのようなKを極大頻出集合と言う
- 部分集合ごとに出現が定義されるので、二つの部分集合K,K'のそれぞれに出現
がある。これらが等しいこともある。
のとき、この出現は買い物イベントに関する部分集合であるが、たくさんのアイテムからなるK'もあれば少しのアイテムからなるK'もあるがを共有するすべてのK'を含むようなKを飽和集合と呼ぶ。サポートの大きさごとに定めることができる。極大の場合と違って、飽和の場合には、飽和集合のすべての部分集合が頻出しているわけではない→こちらの例を参照
- 例
- m=4,n=5とする
- (1,1,1,1,1),(1,1,1,0,1),(1,1,0,1,0),(0,0,1,1,1)という４つの買い物あるとする
- 全購入アイテムのべ数
の出現
であり、
となる- サポート
としたとき、頻出集合は
となる
- このときの極大頻出集合は
の３つである
- すべてのKについてそのを列挙すると
となる。これらのそれぞれに対して飽和集合がある。
がそれぞれ対応する
- nysol ZDDを使ってやってみる
irb(main):039:0* t1 = ZDD::itemset("a b c d e")
=> a b c d e
irb(main):040:0> t2 = ZDD::itemset("a b c e")
=> a b c e
irb(main):041:0> t3 = ZDD::itemset("a b d")
=> a b d
irb(main):042:0> t4 = ZDD::itemset("c d e")
=> c d e
irb(main):043:0>
irb(main):044:0* T = t1 + t2 + t3 + t4
(irb):44: warning: already initialized constant T
(irb):30: warning: previous definition of T was here
=> a b c d e + a b c e + a b d + c d e
irb(main):045:0> T.freqpatA(3)
=> a b + a + b + c e + c + d + e + 1
irb(main):046:0> T.freqpatM(3)
=> a b + c e + d
irb(main):047:0> T.freqpatC(3)
=> a b + c e + d + 1
irb(main):048:0> T.freqpatC(2)
=> a b c e + a b d + a b + c d e + c e + d + 1
irb(main):049:0> T.freqpatC(1)
=> a b c d e + a b c e + a b d + a b + c d e + c e + d + 1
