aprioriアルゴリズム(2)
前回のaprioriアルゴリズムについて。
このアルゴリズムの肝は、調査する頻度の最低値を決めておいて、"あらかじめこの最低値より頻度が少ないとわかる組み合わせを、N+1組の計算をするときに、N組の計算結果から調べて削除する"ことであり、これがapriori_gen関数であった。
具体的に言うと、アイテムの集合 $I$があったときに、その部分集合 $ X,Y \subseteq I $ の組み合わせが発生する頻度を $ \textrm{Supp}(X) , \textrm{Supp}(Y) $ と書くとすると、
\[ X \subseteq Y \longrightarrow \textrm{Supp}(Y) < \textrm{Supp}(X) \]
という関係が成り立つことを、利用している。
$ X $ が調査する頻度の最低値$min\_support$を下回っていたことがわかれば、$ \textrm{Supp}(X) < min\_support $ であり、 $ X \subseteq Y $ なら、$ \textrm{Supp}(Y) < min\_support $ となることがわかので、$Y$の頻度は計算しなくてもよい。
- $Y$の組み合わせで、$X$が部分集合として含まれるものは調査に除外してよい。
逆に言うと、頻度最低値$min\_support$を超える集合を部分集合として含むものであれば、調査する必要が発生する。
例のプログラムでは、N組の組み合わせの集合 に A．同じN組の組み合わせ集合か、B. 1組の組み合わせの集合(頻度の少ないものは除外済み) のどちらかを掛け合わせて、集合として、N+1組になるものを計算しているが、実は、この方法では、1.で示した除外してよい組み合わせが、含まれてしまう可能性がある。
仮に、N組の組み合わせが、以下だったとしたとき、
\[ X_N = \{ item_1,item_2, ... , item_N \} \ \]
和集合の確認をして、N+1組の組み合わせが、
\[ Y_{N+1} = \{ item_1,item_2, ... , item_N , item_{N+1} \} \]
となったとする。
$X_N$ が最小頻度以上の想定なので、$Y_{N+1}$ も最小頻度以上の可能性はある。しかし、今の例のアルゴリズムでは、追加となった$item_{N+1}$を含んだ部分集合が、N組以下の組み合わせの計算時に最小頻度以下として除外された集合の可能性は否定できない。
これを単純に確認する方法としては、事前に最小頻度の組み合わせとして除外された組み合わせを保持しておいて、N組組み合わせ生成の際に、それらの部分集合が含まれていないかチェックする方法であろう。
def apriori_gen(flst,ex_f,items_list):
if len(flst)<items_list:addlst=flst
else:addlst=items_list
tmp=[ ]
for i in flst:
for j in addlst:
n=len(i)
f=set(i).union(set(j))
if len(f)==n+1 and f not in tmp:
if [1 for l in ex_f if set(l) in f]==[ ]:
tmp.append(f)
return [ list(t) for t in tmp ]
def apriori_func(idata,tran_num,f,min_support,max_k):
sol=[ ]
ex_f=[ ]
k=1
while f!=[ ]:
n_f=[ ]
print "f[%d]=%d" % (k,len(f))
for x in f:
isum,usum = support_func(tran_num,idata,x)
sup=1.0*isum/tran_num
if sup >= min_support:
sol.append([ x,sup,(isum,usum) ])
n_f.append(x)
else:
ex_f.append(x)
if k==1:f1=n_f[:]
if max_k <= k: break
f=apriori_gen(n_f,ex_f,f1)
k+=1
return sol
ex_fを使って除外する集合をチェックする。
しかし、この方法も微妙で、除外する組み合わせが多くなればなるほど、apriori_genのチェックに非常に時間を要してしまう。
こういった問題を回避できるのが、もっと別の方法のアルゴリズムとして、FP-Treeアルゴリズムである。集合の頻度の高いもの順に組み合わせを木構造化することで、こういった組み合わせ検索の問題が回避されている。(もちろんメモリを使うことになるのだが)
このアルゴリズムの実装についてはまた今度。
