相関ルール - Top Page | 中川研究室

データマイニング &
パターンマイニング
目次
相関ルール
Apriori algorithm
頻出アイテム集合を探す
subset関数
Apriori-Gen関数
相関ルールを探す
FP-growth algorithm
さまざまな手法
列パタンのマイニング:PrefixSpan
相関ルールとは
「目玉商品Aと日用品Bを購入した顧客は、同時に高級品C
も高い確率で購入する」
•A,B,Cのセット商品を発売する
•顧客の便利性を考えて、商品の配置を近づける
{目玉商品A、日用品B}⇒{高級品C}と表現できる
{X}⇒{Y}
定義
{X}⇒{Y}
X, Y
I={i1,i2,…,im}
T
相関ルール
X:前提部, Y:結論部
アイテム集合, ik, k=1,.,mはアイテム、例えば個
別の商品
トランザクション(例えば買い物かごの中身)＝
アイテムの集合
support(X)
支持度: support
アイテム集合X含むTの全Tに対する割合
conf(X⇒Y)
確信度: confidence
Xを含むTのうち、Yを含むTの全Tに対する割
合 =support(XUY)/support(X)
価値のある相関ルールを求める
 m種類のアイテムで
m k
k 2  k (2  2)個のルールが存在する
 
m
 Mこのアイテムの中からｋこを選ぶ方法=  
k
 
m
 ｋこのアイテムの各々が前提に来るか、結論に来る
かのわけ方＝ 2k
 全部のアイテムが前提に集まる場合と、結論に集ま
る場合は、ルールにならないので排除
  2k -2
価値のある相関ルールを求める
 m種類のアイテムで
m k
k 2  k (2  2)個のルールが存在する
 
m
 アイテムが10種類の場合でもルールは約57,000も
ある
 価値のある相関ルールはわずかだけ
 価値のある相関ルールとは
 確信度 conf が高い
 支持度 support が高い
アプリオリアルゴリズム
(Agrawal 1994, VLDB94)
• 最小確信度、最小サポート(min support)を
与えて確信度、サポートがそれ以上の相関
ルールを発見する
support(XUY)>α
support(XUY)/support(X)=conf(X⇒Y) >β
を満たす相関ルールX⇒Yを取り出すのが目的
効率よく探し出すために
 アイテム集合のサポートは単調減であることを使う。
 頻出アイテム集合とは、最小サポート以上のサポートを持つアイテム集合
I  Jならば support(I )  support(J )
｛A,B｝が頻出アイテム集合でない
↓
｛A,B,C｝も頻出アイテム集合ではない
 この背反を取ると
｛A,B,C｝が頻出アイテム集合⇒｛A,B｝も頻出アイテム集合
 support(XUY)とsupport(X)が必要。
 support(XUY)は最小サポート以上であるので、XUYの部分集合であるXのサポー
トも最小サポート以上（ XとY はともに条件なので、XUYは、 X、Y 単独よりも厳し
い条件）
 最小サポート以上の頻出アイテム集合のサポートを求めておけばすべての相関
ルールの確信度を求めることができる
アルゴリズム
1. support(XUY)>αを満たす頻出アイテム集合をすべ
て探し出し、サポートを求める
2. support(XUY)/support(X)>β
を満たす相関ルールを探し出す
(1)が求まれば、それを使うと(2)は簡単
どうやって(1)を効率よくもとめるか
Apriori algorithm
k アイテム集合
ｋ個のアイテムを持つアイテム集合
Lk
頻出ｋアイテム集合（これらは最小サポート以上を持
つ）以下の２つのフィールドからなる: (1)アイテム集合、
(2) support count
Ck
頻出アイテム集合の可能性のある k アイテム集合:
以下の２つのフィールドからなる (1) アイテム集合 (2)
support count
C’k
TIDs(Transaction ID) のtransactionから生成された
kアイテム集合の候補の集合
頻出アイテム集合を探し出す
｛A,B｝が頻出アイテム集合でない⇒
｛A,B,C｝も頻出アイテム集合ではない
• 要素数の少ないサポートから求めていき、最小サ
ポートより少ない集合を含めるものは計算しない
1. データベースをスキャンしCk中の各サポートを計算する
2. Ck中の最小サポートを満足する部分をLkとする
3. LkからCk+1を生成する
Apriori algorithm
L1={頻出アイテム集合}
for ( k=2; Lk-1≠Ø; k++) do
{ Ck= apriori_gen(Lk-1) ; // New candidates
for (all transactions t in D )do
{ Ct = subset(Ck , t) // Candidates contained in t;
for (all candidates c in Ct) do
{c.count++}
};
Lk ={c in Ck | c.count≥ minsup}
}
Answer ∪k Lk
}
Apriori-Gen関数
 結合フェーズ
Lk中から最後の要素だけが異なる二つのアイテ
ム集合を結合して要素数k+1の候補アイテム集
合を作る
 枝狩りフェーズ
結合フェーズで作った候補アイテム集合に対し、
要素数kの部分集合がLkに含まれていないような
候補を除去する
Transaction dataの例
データベース D
TID
item
００００１
A,C,D
００００２
B,C,E
００００３
A,B,C,E
００００４
B,E
頻出アイテム集合を計算する例
min support =2
頻出アイテム集合の候補
Ｃ1
アイテ
ム集合
｛Ａ｝
｛Ｂ｝
｛Ｃ｝
｛Ｄ｝
｛Ｅ｝
subset関数
&
minsupport
>=2のものを
選択
頻出アイテム集合
L1
アイテ
ム集合
{A}
｛B}
｛C}
｛E}
頻出アイテム集合の候補
C2
カウン
ト
２
３
３
３
アイテム集合
AprioriGen関数
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
頻出アイテム集合を計算する例
つづき
頻出アイテム集合の候補
C2
頻出アイテム集合
{A,E}
{B,C}
{B,E}
{C,E}
AprioriGen関数
L2
アイテム集合 subset関数
アイテム
&
{A,B}
集合
minsupport
{A,C}
>=2のものを
選択
{A,C}
頻出アイテム集合の候補
C3
アイテム集合
カウン
ト
２
｛B,C} 2
｛B,E} ３
｛C,E} 2
｛B,C,E}
ここだけが
異なる
subset
関数
L3
アイテム集合
カウント
｛B,C,E}
２
頻出アイテム集合
頻出アイテム集合C3
{A,B,C}
{A,B,D}
{A,C,D}
頻出アイテム集合の候補L4
{A,B,C,D}
{A,C,D,E}
{A,C,E}
{B,C,D}
要素数3の部分集合
{A,D,E}
が含まれていないので、
{A,C,D,E}は排除
Apriori_Gen（Ｌｋ）
｛Ck＋１＝φ;
foreach p,q in Lk such that ( p.item1=q.item1,…,
p.itemk-1=q.itemk-1, p.itemk ≠ q.itemk)
{c=p U q.itemk;
Ck+1=Ck+1U{c}
}
//prune
for (all itemsets c in Ck+1 )do
for(all k subsets s of c )do
{if s not in Lk
then delete c from Ck+1}
}
return Ck+1
}
subset関数
 トランザクションtに含まれる候補アイテム集合を見
つけ出す
例
 t={A,B,C,E}
 SUBSET(C2,t)＝{{A,B}1、{A,C}2、 {A,E}1、
{B,C}2、 {B,E}3、 {C,E}2} （数字は出現回数）
がsubset関数で生成されるが、そのうち
min support=2以上のものだけを選ぶと
{{A,C}、 {B,C}、 {B,E}、{C,E}}
相関ルールの導出（枝刈り１）
a~  aについて support(a~)  support(a)
support(l )
~
~
conf(a  (l  a )) 
support(a~)
support(l )
conf(a  (l  a)) 
support(a)
conf(a~  (l  a~))  conf(a  (l  a))
a~  { A, B}
a  { A, B, C}
l  { A, B, C , D}
conf({A, B}  {C , D})
conf({A, B, C}  {D})
conf(a~  (l  a~))が最小確信度以上ならば
conf(a  (l  a))も最小確信度以上である
相関ルールの導出：枝刈り2
conf(a~  (l  a~))が最小確信度以上ならば
conf(a  (l  a))も最小確信度以上である
対偶をとる
c  l  a~、 c~  l  aとする
c~  c
conf((l  c~)  c~)が最小確信度未満ならば
conf((l  c)  c)も最小確信度未満である
c  {C , D}
c~  {D}
l  { A, B, C , D}
conf({A, B, C}  {D})
conf({A, B}  {C , D})
• {A,B,C}⇒{D}と{A,B,D}⇒{C}のどちらか一方でも
最小確信度未満ならば
• {A,B}⇒{C,D}も最小確信度未満である
FP-growth algorithm
• Apriori algorithm の効率を大きく改善するア
ルゴリズム(J.Han, 1999 SIGMOD)
I = {a1; a2; : : :; am} be a set of items
a transaction database DB = {T1; T2; : :Tn}
 where Ti (i =1,..,n) is a transaction which
contains a set of items in I.
The support1 (or occurrence frequency) of a
pattern A, which is a set of items is the number
of transactions containing A in DB.
A is a frequent pattern if A's support is no less
than a predefined minimum support threshold,
ξ.
FP-treeの定義
• 要素
– one root “null”
– a set of item prefix subtrees as the children of the root
– a frequent-item header table
• Node in the item prefix subtree consists of
– (1)item-name, (2)count, (3)node-link
• frequent-item header table con-sists of
– (1) item-name and (2) head of node-link
例
Item name
Count
Item link
a:3 ----->
FP-tree construction algorithm
Step1:DBをscanし、ξ以上の頻度を持つfrequent item
Fを集め、頻度の降順にソート。
Step2:DBの格要素(transaction)において、それに含ま
れるitemを頻度の降順にソートし、
Step3:
for( each transaction: L) do
{ root のnullノードからスタートして、以下のように
rootにぶら下がる木を作る。ただし、T=rootする;
L=[p|P], pは先頭の要素、Pは残りのリスト;
insert_tree([p|P],T) }
insert_tree([p|P],T)
{
If T has a child N such that N.item-name= p.item-name,
then increment N's count by 1;
else
{ create a new node N, and let its count be 1;
its parent link be linked to T；
its node-link be linked to the nodes with the same
item-name via the node-link structure.
｝
If P is nonempty,
then call insert tree(P;N) recursively
}
FP-Treeの木の高さは、ひとつのtransaction
に含まれるitemの個数の最大値
Rootからleafまでの枝（path)において、item
は頻度の降順に並んでいる。
FP-Treeからのルール導出
• Property 3.1 (Node-link property) For any
frequent item ai, all the possible frequent
patterns that contain ai can be obtained by
following ai's node-links,starting from ai's
head in the FP-tree header.
パタンマイニング関数:mine
Header table の中で、一番頻度の低い（つ
まり、一番下の） itemから順にパターンを探
す。
(ｐ：３）の上に来るパタンはpの条件付パタン
ベースと呼ばれ、以下の通り。
 {<f:4; c:3; a:3;m:2>| p}, {<c:1; b:1>| p}
ｐの上に共通に来るパタンはｃのみなので、
抽出されたパタンは (cp:3)だけ。
つづき
ｍの上には、<f:4; c:3; a:3>,
<f:4; c:3; a:3; b:1> が来るが、共通するパタ
ンは< f:3; c:3; a:3>だけ。
そこで、mine(< f:3; c:3; a:3>|m)を実行する
と(am:3),(cm:3),(fm:3)が得られる。
次に、mine(< f:3; c:3>|am)を実行すると、
(cam:3),(fam:3)が得られる。
さらに(<f:3>|cam)を実行すると、(fcam:3)が
得られる。以下他のパタンについても同様。
Conditional FP-tree は、条件のitem（例えば1番上の例だとｐ）のcountに合わせ
る。
パタン・マイニング・アルゴリズム
• Input: FP-tree constructed based on Algorithm 1,using DB and a
minimum support threshold ξ.
• Output: The complete set of frequent patterns.
• Method: Call FP-growth (FP-tree ; null).
Procedure FP-growth (Tree、α )
｛
if Tree contains a single path P
then for each combination (denoted as β ) of the nodes in the
path P do
｛generate pattern β∪α
[ with support =minimum support of nodes in β]｝
else for each ai in the header of Tree do
｛generate pattern β= ai ∪α
[ with support = ai :support};
construct 's conditional pattern base;
β‘s conditional FP-tree ：Treeβ;
if Tree β≠Ø
then call FP-growth (Treeβ, β) }
}
その他
•
•
•
•
•
分類階層つき相関ルール
数値属性を１個持つ相関ルール
数値属性を２個持つ相関ルール
並列アルゴリズム
視覚化手法
Sequential pattern mining
列パタンのマイニング
抽出対象のデータは要素の列の集合
要素はitemの集合
min_support以上の出現頻度を持つ部分列
をすべて探し出すこと
対象のデータ
 I={i1,i2,….,in}, ijはitem
 Sequenceは順序付きのitem集合の列
 Sequence:S=<s1,s2,…,sl>,要素： Si  I for1  i  l
 Si=(x1,x2,…,xm) xiはIの要素（＝item)。 1個しかitemを含まな
い(x)はxと略記

 Sequence：Sの長さ： Sが含むitem数
 length(<(a)(b)>)=length(<ab>)=2, length(<(a b)>)=2
 β(=b1,..,bm) is super-sequence of α(=a1,…,an) (逆にαはβ
のsubsequence)とは次の条件を満たす1≤j1≤j2≤…. ≤
jn≤mなるサフィックス列が存在すること。
a1  bj1かつa2  bj2 ,.....,an  bjm
 Sequence database: <sid,s>の集合。sidはseqience:sの名前
Sequence databaseの例：Ｓ
Sequence id
Sequence
１０
<a(abc)(ac)d(cf)>
２０
<(ad)c(bc)(ae)>
３０
<(ef)(ab)(df)cb>
４０
<eg(af)abc>
Prefix, projection and postfix
 α=<e1,e2,..en>, β=<e1’,e2’,..,em’>, m≤n
 次の条件を満たすとき、βはαのprefix
 (1)ei’=ei for (i≤m-1)
'
 (2) em
 em
 (3)em-e’mの要素はe’mの要素より辞書順で後のもの
 βをαのsubsequenceとするとき、αのsubsequence α’がα
のprojectionであるとは以下のように定義される
 α’はprefix βを持つ
 α’のsuper-sequenceであり、prefixβを持ち、かつαの
subsequenceであるものは存在しない。（α’は上記の条件を持た
す最大の列
Prefix, projection and postfix
 α’=<e1,e2,..,eｋ>はβ=< e1,e2,..,em-1,e’m>に対するαの
projection.ただし(m≤ｋ)
 このとき列γ=<e’’m,em+1,…,eｋ>はβに対するαのpostfix
ただし、e’m＋ e’’m＝em。
'
e
m  em
 つまり α＝βγ
 例：α=< (a) (b) (a b c) (f) >
β=< (a) (b) (a b )> γ=<(c) (f) >
 例：<a>,<aa>,<a(ab)>,<a(abc)>は<a(abc)(ac)d(cf)>のprefixだが、
<ab>や<a(bc)>はprefixではない？？
prefix <ab> =<(a)(b)> のpostfixは <(_c) )(ac)d(cf)>。2項目の(abc)は
集合だから、いきなり<ab>をprefixにしてもよい。
PrefixSpanの動作
sequence data base：Ｓの例を用いて
ただし、min_support=2
 Step 1: length=1の列パタンを全て求める
 <a>:a, <b>:4, <c>:4, <d>:3, <e>:3, <f>:3
 Step 2:列パタンの分割（辞書順に含むアイテムを
拡大していくように）
 a以外は持たないもの、
 a b以外は持たないもの、
 a b c以外は持たないもの、
 ……
Ｓｔｅｐ３：列パタンの部分集合を数え上げる
これは、step 2の各結果に対して、projection
を数え上げ、その結果の列パタンに同様の数
え上げを再帰的に繰り返す。
Step 3のＳにおける動作例
<a>に対するprojectionのデータベースは
<a(abc)(ac)d(cf)>  <( abc)(ac)d(cf)> (1)
<(ad)c(bc)(ae)>  <(_d)c(bc)(ae)> (2)
<(ef)(ab)(df)cb>  <(_b)(df)cb> (3)
<eg(af)cbc>  <(_f)cbc> (4)
prefix<a>を含むlength=2の列パタン
(min_support=2)は上記の結果のprojection
たちを調べると
 <aa>:2 (1),(2), <ab>:4 (1)(2)(3)(4)
 <(ab)>:2 (1)(3), <ac>:4 (1)(2)(3)(4)
 <ad>:2 (1)(3), <af>:2 (1)(3)
つづき
 Prefix <aa>を持つpostfix subsequence(<aa>-projected
database) は(1)から得られる< (_bc)(ac)d(cf)>だけ。よって、
min_support以上の頻出パタンはここからは生成されない。
よって、このパタンは修了

<ab>-projected databaseからは
<(_c) (ac)d(cf)> (1) , <(_c)a> (1)(2), <c> (1)-(4)
 この結果を再帰的に調べると <(_c)>:2, <(_c)a>:2, <a>:2, <c>:3
(全部書くと<a(bc)>, <a(bc)a>, <aba>, <abc>)
 <(ab)>-projected databaseからは <(_c) (ac)d(cf)>,
<(df)cb>
 この結果を再帰的に調べると <(ab)c>, <(ab)d>, <(ab)f>, <(ab)dc>
 以下同様に全ての列パタンを再帰的に調べ、min_support
以上の列パタンを数え上げる。
例：ＳからPrefixSpanで得た列パタン
Prefix
Projected postfix
列パタン
<a>
<(abc)(ac)d(cf)>,
<(_d)c(bc)(ae)>,
<(_b)(df)cb>,<(_f)cbc>
<a>,<aa>,<ab>,<a(bc)>,<a(bc)a>,<aba>,<
abc>,<(ab)>,<(ab)c>,<(ab)d>,<(ab)f>,<(a
b)dc>,<ac>,<aca>,<acb>,<acc>,<ad>,<ad
c>,<af>
<b>
<(_c)(ac)d(cf)>, <(_c)(ae)>,
<(df)cb>, <c>,
<b>, <ba>, <bc>, <(bc)>, <(bc)a>, <bd>,
<bdc>, <bf>
<c>
<(ac)d(cf)>, <(bc)(ae)>, <b>,
<bc>
<c>, <ca>, <cb>, <cc>,
<d>
<(cf)>, <c(bc)(ae)>,<(_f)cb>
<d>, <db>, <dc>, <dcb>
<e>
<(_f)(ab)(df)cb>, <(af)cbc>
<e>, <ea>, <eab>, <eac>, <eacb>, <eb>,
<ebc>, <ec>, <ecb>, <ef>,
<efb>,<efc>,<efcb>
<f>
<(ab)(df)cb>, <cbc>
<f>, <fb>, <fbc>, <fc>, <fcb>
PrefixSpanの効率化
 Apriori propertyの利用
 例：<ac>は列パタン(すなわちmin_support以上）だが、
<ad>は列パタンでない（min_support未満）の場合は、両
者を含む<acd>およびそのsuper-sequenceは列パタン
にならないことは明白なので、調べる必要はない。
 Pointer利用によるメモリの効率的使用
 例えば、<a(abc)(ac)d(cf)>の処理では、その部分列が何
回も処理される。
例えば、<a>のprojection:①<(abc)(ac)d(cf)>と、<ab>の
projection：②<(_c) )(ac)d(cf)>。これらが別々にメインメ
モリに格納されることを防ぐために、projection database
には、ｓ①＝２(offset), s②=4(offset)を記憶しておけば、
<a(abc)(ac)d(cf)>は１箇所で記憶しておくだけで良い。

Download Report