新規
編集
添付
一覧
最終更新
差分
バックアップ
凍結
複製
名前変更
ヘルプ連想ルールとは，同時に共起しやすいアイテムの組をみつけることで，「アイテムＡを買えば，アイテムＢも買いやすい」といったルールを見つけるアルゴリズムである．英語で，Association Rule と呼ばれる事から，連想ルール以外にも，アソシエーションルール，相関ルール，また，買い物籠の中の商品の共起性「を分析することから， バスケット分析とも呼ばれる．
このマイニング手法は，アメリカのスーパーマーケットでのＰＯＳデータの分析において，「紙おむつを買うと，ビールも買われやすい」（休日のマイカーでのお父さんのお役目）という連想ルールが発見された話で有名．
概念 
トランザクションデータ
分析の元データは，トランザクションデータと呼ばれ，トランザクションＩＤとアイテムの２つの項目をもつ．
トランザクションＩＤが，１つのバスケットだったり，１つの伝票だったり，一人の顧客を意味している．アイテムは，そのトランザクションに属する商品ＩＤで，原則トランザクション内では１つのアイテムは重複しないものとする．
トランザクションID アイテム 顧客Ａ ビール 顧客Ａ 紙おむつ 顧客Ａ 週刊誌 顧客Ｂ ビール : ：
アイテムセット
アイテムセット(item set)，またはタプル(tuple)とは，0個以上のアイテムの集合で，n個の商品からなるものをn-itemset，n-tupleと呼ぶ．
1-itemsetは，{ビール},{紙おむつ}など，2-itemsetは，{ビール,紙おむつ},{ビール,週刊誌}などである．
アイテムが全部で3種類(A,B,C)であれば，すべてのアイテムセットは，2**3=8種類，すなわち，
{},{A},{B},{C},{A,B},{A,C},{B,C},{A,B,C}
であり，アイテムが全部でn種類であれば，2**n種類のアイテムセットが存在する．連想ルールでは，各アイテムセットを含むトランザクションの数を数えることが必要である．しかし，アイテムが数千以上もあるなら，すべてのアイテムセットの組み合わせ自体膨大な数になってしまい，それを含むトランザクション数を力任せに数え上げることは現実的な時間内ではまったく実行できない．
連想ルールは，ある種の工夫をすることで，それを高速に計算可能にしたアルゴリズムである．
最小サポート数
サポート数とは，アイテムセットのトランザクション数のことである．数え上げるアイテムセットの最小サポート数を指定することで，高速な数え上げが可能となる．
連想ルール
連想ルール
「Aを買うならBも買いやすい」という事実を連想ルールといい，A⇒B と記述する．
ここで「Bも買いやすい」かどうかは，Bを買う確率 P(B) よりも，Aを買う場合でのBを買う条件付確率 P(B|A)が大きいということである．特に P(B|A) を連想ルールA⇒B の確信度といい，P(B|A)÷P(B)をリフト率という．一般にリフト率が大きい連想ルールがより強いルールであり，どのP(B)も十分小さいとみなせる場合には，確信度の大きいルールが強いと判断される．
各アイテムセットのトランザクション数がわかれば，次のように連想ルールを導くことができる．
まず，１つのアイテムセット{A,B,C,..}から，最初のアイテムAを取り出し，連想ルールの候補
B,C,..⇒A
を作る．今，アイテムセット{A,B,..}を含むトランザクション数を F({A,B,..}) とあらわすこととすると，
このリフト率は，
P(A|B,C,..)÷P(A) = F({A,B,C,..})÷F({B,C,..})÷F({A})
となる．これが大きい，すくなくとも１以上であれば，連想ルールに採用する．
元のアイテムセット{A,B,C,..}に戻り，次のアイテムBから，連想ルールの候補
A,C,..⇒B
をつくり，上記の処理を繰り返す．元のアイテムセットに属するアイテムについてすべて実行終えたら，残る他のアイテムセットについても，同じ処理を行えばよい．
アイテムセットを求めるアルゴリズム
**** read trandb D ********;
data D;
input tid item1;
cards;
100 1
100 3
100 4
200 2
200 3
200 5
300 1
300 2
300 3
300 5
400 2
400 5
;
%let support=0.5;
************************************************************;
* Association Rule Extract (Large Item Set Create Part) *;
* 1998/04/30 翔 *;
* D : Original Transaction DB *;
* Cn: Candidate itemset of n-th path *;
* Ln: Large itemset of n-th path *;
* macro var support and Dataset D are required *;
************************************************************;
************************************************************;
* observation count subroutine *;
************************************************************;
%global NOBS;
%macro subNOBS(dsn);
proc contents data=&dsn noprint out=NOBS;run;
data _null_;set NOBS(obs=1);call symput("NOBS",NOBS);run;
%mend;
************************************************************;
* MAIN *;
************************************************************;
proc sort data=D out=TID nodupkey;by tid;run;
%subNOBS(TID);
%let N=&NOBS;
%put N=&N;
data C1;set D;run;
%macro loop;
%let K=0;
%do %until(&NL=0 or &K=5);
%let K=%eval(&K+1);
proc summary data=C&K nway missing;
class item1-item&K;
output out=Ld&K(where=(_freq_>=&support*&n));
run;
proc sort data=C&K;by item1-item&K;run;
proc sort data=Ld&K;by item1-item&K;run;
data L&K;merge C&K(in=in1) Ld&K(in=in2);by item1-item&K;
if in1 and in2 then output;
run;
proc print data=C&K;var tid item1-item&K ;run;
proc print data=Ld&K;var item1-item&K _freq_;run;
proc print data=L&K;var tid item1-item&K _freq_;run;
%subNOBS(L&K);
%let NL=&NOBS;
%put NL=&NL;
%if &NL>0 %then %do;
%put K=&K;
%let K1=%eval(&k+1);
proc sql;
create table C&K1 as
select p.TID,%do i=1 %to &K;p.item&i,%end;q.item&K1
from L&K p, L1(keep=tid item1 rename=(item1=item&K1)) q
where p.TID=q.TID and p.item&K<q.item&K1;
run;
%end;
%end;
%mend loop;
%loop
/*
C1
OBS TID ITEM1
1 100 1
2 300 1
3 200 2
4 300 2
5 400 2
6 100 3
7 200 3
8 300 3
9 100 4
10 200 5
11 300 5
12 400 5
Ld1
OBS ITEM1 _FREQ_
1 1 2
2 2 3
3 3 3
4 5 3
L1
OBS TID ITEM1 _FREQ_
1 100 1 2
2 300 1 2
3 200 2 3
4 300 2 3
5 400 2 3
6 100 3 3
7 200 3 3
8 300 3 3
9 200 5 3
10 300 5 3
11 400 5 3
C2
OBS TID ITEM1 ITEM2
1 300 1 2
2 100 1 3
3 300 1 3
4 300 1 5
5 200 2 3
6 300 2 3
7 200 2 5
8 300 2 5
9 400 2 5
10 200 3 5
11 300 3 5
Ld2
OBS ITEM1 ITEM2 _FREQ_
1 1 3 2
2 2 3 2
3 2 5 3
4 3 5 2
L2
OBS TID ITEM1 ITEM2 _FREQ_
1 100 1 3 2
2 300 1 3 2
3 200 2 3 2
4 300 2 3 2
5 200 2 5 3
6 300 2 5 3
7 400 2 5 3
8 200 3 5 2
9 300 3 5 2
C3
OBS TID ITEM1 ITEM2 ITEM3
1 300 1 3 5
2 200 2 3 5
3 300 2 3 5
Ld3
OBS ITEM1 ITEM2 ITEM3 _FREQ_
1 2 3 5 2
L3
OBS TID ITEM1 ITEM2 ITEM3 _FREQ_
1 200 2 3 5 2
2 300 2 3 5 2
*/