apriori アルゴリズム
ちょっとあまりに稚拙だが、
相関性分析におけるaprioriアルゴリズムをpythonで書いたので、書き残す。
#!/usr/bin/env python
items=['beer','nuts','cheese','jam','butter']
testdata=[ ['beer','nuts','cheese'],
['beer','nuts','jam'],
['beer','butter'],
['nuts','cheese'],
['beer','nuts','cheese','jam'],
['butter'],
['beer','nuts','jam','butter'],
['jam'] ]
def apriori_gen(flst,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:
tmp.append(f)
return [ list(t) for t in tmp]
def support_func(num,idata,xlst):
isum,usum=set(range(num)),set()
for x in xlst:
if x in idata:
isum=isum.intersection(set(idata[x]))
usum=usum.union(set(idata[x]))
lisum,lusum=len(isum),len(usum)
if lusum==0:lisum=0
return lisum,lusum
def create_idata(testdata):
idata={}
num=len(testdata)
for i in items:
for j in range(num):
if i in testdata[j]:
if idata.has_key(i):
idata[i].append(j)
else:
idata[i]=[j]
return idata,num
def apriori_func(idata,tran_num,f,min_support,max_k):
sol=[]
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)
if k==1:f1=n_f[:]
if max_k<=k: break
f=apriori_gen(n_f,f1)
k+=1
return sol
def apriori(testdata,items,min_support,max_k):
idata,tran_num = create_idata(testdata)
f=[ [i] for i in items]
return apriori_func(idata,tran_num,f,min_support,max_k)
sol=apriori(testdata,items,3.0/8.0,4)
print solaprioriアルゴリズムは、アイテムの組み合わせにおける頻度を計算するもの。
たとえば購買のトランザクションデータがあったときに、どの商品の組み合わせを一緒に購入しているのか？の分析ができる。データ分析における相関分析(アソシエーション分析)と呼ばれるもののベースの情報を提供する。
例のプログラムの場合、itemsが各商品である。testdataの一行ごとが各購入のトランザクションデータとみなされる。
普通に各商品の相関分析をしようとした場合、(商品 x 商品)の組み合わせを全トランザクションで試して、同じトランザクションに現れる頻度を計算すればよい。(商品 x 商品)だから 商品数^2を試すことになる。
ところが、これだけでは分析としては物足りなくて、(商品 x 商品 x 商品)の３組の組み合わせ、(商品 x 商品 x 商品 x 商品)の４組の組み合わせ、のようにN組分の商品の組み合わせに対しても相関を分析したい。しかし、これでは商品数^Nの分だけ全トランザクションでの頻度を調べることになる。計算量が莫大だ。
これを効率よく分析するのが、aprioriアルゴリズム。
具体的には、上記プログラム、min_supportのように頻度を調べる最低値を決めておく。で、N+1組の組み合わせを調べる前に、あらかじめこの最低値より頻度が少ないとわかる組み合わせを、N組の計算結果から調べて削除する、というのがアルゴリズムのあらましである。
具体的な実装としては、以下となる。
- アイテムN組の組み合わせ(apiori_func関数のf)の頻度を調べる
- 頻度の結果から最低値min_supportより大きくなった組み合わせを次の組み合わせの候補(apriori関数のn_f)とする。(min_supportより小さくなった組み合わせは、それ以上、別のアイテムが増えて頻度が増えることはないため、最低値min_supportより頻度が少ないとして削除できる。)
- 次の組み合わせ候補(n_f)から、N+1組の組み合わせを生成(apriori_gen関数)する。N+1組の組み合わせで調べるべきは、2.で作成した候補が含まれる組み合わせであることから、N組の組み合わせから和集合を探して、N+1組(cardinarity=N+1)になればよい。(和集合の探す当ては、ソースのように、アイテム(これは1組の組み合わせ)か自分自身(N組の組み合わせ)として、ループ回数を減らすしている。)
- これを次の組み合わせ候補がなくなるまで繰り返す。
文で書くと結構ややこしい。
プログラムでは、ソースを簡単にするために、いったん、testdataをアイテムからトランザクション種類を引ける辞書型(idata)に変換している。(create_idata関数)
これを使って、それぞれのアイテムから引いたトランザクションのリストを集合として積をとれば、各アイテムの組み合わせの頻度がわかる。(support_func関数。ついでに和集合もとっている)
パラメータとして、組み合わせ数の上限(max_k)を決めて、調整できるようにしておく。
例のitems,testdataの例で言うと、2組の組み合わせ(商品 x 商品)では、
>>> for i in sorted([l for l in sol if len(l[0])==2 and l[1]<3.0/8.0],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['cheese', 'beer'] 0.25 ['butter', 'beer'] 0.25 ['butter', 'nuts'] 0.125 ['cheese', 'jam'] 0.125 ['butter', 'jam'] 0.125 ['butter', 'cheese'] 0.0
が次の候補に外れて、
>>> for i in sorted([l for l in sol if len(l[0])==2 and l[1]>=3.0/8.0],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['beer', 'nuts'] 0.5 ['beer', 'jam'] 0.375 ['cheese', 'nuts'] 0.375 ['jam', 'nuts'] 0.375
を含む組み合わせが、3組の組み合わせ(商品 x 商品 x 商品)の調べる候補となる。3組の商品組み合わせで調べているのは、これだけ。
>>> for i in sorted([l for l in sol if len(l[0])==3 ],key=lambda x:x[1],reverse=True):print i[0],i[1] ... ['beer', 'jam', 'nuts'] 0.375 ['cheese', 'beer', 'nuts'] 0.25 ['cheese', 'jam', 'nuts'] 0.125
ちなみに、相関ルール分析としては、次のような原因と結果ルールを導くのが目的なので、
- 「AならばBである(A → B)」
- 「AかつCならばBである(A,C → B)」
上記で計算した頻度( = 支持度)のほかに条件付確率( = 信頼度)とか、リフト値(信頼度 / Pr(結果))を計算して各確率を考量する必要がある。
- 支持度 ... Pr(A,B) や Pr(A,B,C)
- 信頼度 ... Pr(B|A)=Pr(A,B)/Pr(A) や Pr(B|(A,C)) = Pr(A,B,C)/Pr(A,C)
- リフト値 ... Pr(B|A)/Pr(B) や Pr(B|(A,C))/Pr(B)
いずれも、aprioriアルゴリズムで算出した結果を組み合わせて計算できる。
