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

相関ルールを求める
目次
• 相関ルール
• Apriori algorithm
– 頻出アイテム集合を探す
• subset関数
• Apriori-Gen関数
– 相関ルールを探す
• FP-growth algorithm
• さまざまな手法
相関ルールとは
「目玉商品Aと日用品Bを購入した顧客は、同時に高級品C
も高い確率で購入する」
•A,B,Cのセット商品を発売する
•顧客の便利性を考えて、商品の配置を近づける
{目玉商品A、日用品B}⇒{高級品C}と表現できる
{X}⇒{Y}
定義
{X}⇒{Y}
相関ルール
X
前提部
Y
結論部
I={i1,i2,…,im} アイテム(例えば商品)の集合
T
トランザクション(例えば買い物かごの中身)
確信度
conf(X⇒Y)
Xを含むTのうち、Yを含むTの割合
支持度
support(X⇒Y)
XUYを含むTの全てのTに対する割合
価値のある相関ルールを求める
 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も
ある
 価値のある相関ルールはわずかだけ
 価値のある相関ルールとは
 確信度が高い
 支持率が高い
アプリオリアルゴリズム
(Agrawal 1994, VLDB94)
• 最小確信度、最小サポートを与えて確信度、
サポートがそれ以上の相関ルールを発見す
る
support(XUY)>α
support(XUY)/support(X)>β
を満たす相関ルール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
のサポートも最小サポート以上
• 最小サポート以上の頻出アイテム集合のサポートを求めておけばすべて
の相関ルールの確信度を求めることができる
アルゴリズム
1. support(XUY)>αを満たす頻出アイテム集合をすべ
て探し出し、サポートを求める
2. support(XUY)/support(X)>β
を満たす相関ルールを探し出す
(1)が求まれば、それを使うと(2)は簡単
どうやって(1)を効率よくもとめるか
頻出アイテム集合を探し出す
｛A,B｝が頻出アイテム集合でない⇒
｛A,B,C｝も頻出アイテム集合ではない
• 要素数の少ないサポートから求めていき、最小サ
ポートより少ない集合を含めるものは計算しない
1. データベースをスキャンしCk中の各サポートを計算する
2. Ck中の最小サポートを満足する部分をLkとする
3. LkからCk+1を生成する
Apriori algorithm
k itemset
An itemset having k items
Lk
Set of large k itemsets (those with minimum
support). Each member of this set has two fields:
(1)itemset and (2) support count
Ck
Set of candidate k itemsets (potentially large
itemsets). Each member of this set has two fields:
(1) itemset and (2) support count
C’k
Set of candidate k itemsets when the TIDs of the
generating transactions are kept associated with
the candidates.
Apriori algorithm
L1={large item set}
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
}
Transaction dataの例
データベース D
TID
item
００００１
A,C,D
００００２
B,C,E
００００３
A,B,C,E
００００４
B,E
頻出アイテム集合の候補
subset関数
頻出アイテム集合
Apriori-Gen関数
Apriori-Gen関数
• 結合フェーズ
– Lk中から最後の要素だけが異なる二つのアイテ
ム集合を結合して要素数k+1の候補アイテム集
合を作る
• 枝狩りフェーズ
– 結合フェーズで作った候補アイテム集合に対し、
要素数kの部分集合がLkに含まれていないような
候補を除去する
頻出アイテム集合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
insert into Ck
select p.item1,….,p.itemk-1, q.itemk
from Lk-1 p, Lk-1 q
where p.item1=q.item1,…,p.itemk-1=q.itemk-1,
p.itemk ≠ q.itemk
//prune
for (all itemsets c in Ck )do
for(all k-1 subsets s of c )do
{if s not in Lk-1
then delete c from Ck}
}
}
subset関数
• トランザクションtに含まれる候補アイテム集合を見
つけ出す
• 例
• t={A,B,C,E}
• 候補アイテム集合C2 から{A,B}1、{A,C}2、 {A,E}1、
{B,C}2、 {B,E}3、 {C,E}2 （数字は出現回数）
• SUBSET(C2,t)={{A,C}、 {B,C}、 {B,E}、{C,E}}
t={A,B,C,E}
B
{C,E}
A
{B,C,E}
C
root
E
C
B
{E}
E
C
E
{C,E}
C
E
候補アイテム集合{A,B}、{A,C}、{A,E}、{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))も最小確信度以上である
相関ルールの導出
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}も最小確信度未満である
頻出アイテム集合{A,B,C,D}について考える？？
{ A, B, C}  {D}
{ A, B, D}  {C}
{ A, C , D}  {B}
{B, C , D}  { A}
{C , D}  { A, B}
{B, D}  { A, C}
{ A, B}  {B, C}
{D}  { A, B, C}
{ A, B}
{ A, C}
{B , C}
{ A, B, C}
なし
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β, β) }
}
FP-growthの性能
その他
• 分類階層つき相関ルール
• 並列アルゴリズム
• 視覚化手法

Download Report