機械学習(八)—Aprioriアルゴリズム
11844 ワード
要旨:本稿ではAprioriアルゴリズムを簡単に紹介し,Pythonにより実現し,さらにUCIデータベースにおけるリブキノコデータセットと組み合わせてアルゴリズムを検証した.
「ビールとおむつ」の例は多くの人が聞いたことがあるだろう.スーパーでは、おむつとビールの2つの風馬牛が合わない商品が並んでいるという興味深い現象が発見された.しかし、この奇妙な措置はおむつとビールの販売台数を大幅に増加させた.これは冗談ではなく、米国のウォルマートチェーンスーパーで起きた実例だ.もともと、アメリカの女性は家で子供の世話をしているので、退勤して家に帰る途中で子供のためにおむつを買うように夫に言いつけ、夫はおむつを買うと同時に自分の好きなビールを買うように言いつけていた.この発見は業者に大量の利益をもたらしたが、煙の海のように雑然としたデータから、ビールとおむつ販売のつながりをどのように発見したのだろうか.このような大規模なデータから物品間の隠れた関係を発見する方法は関連分析と呼ばれ,本論文で主に研究する一般的な分析方法であり,Aprioriアルゴリズムは最も有名な関連規則マイニングアルゴリズムの一つである.次に,このアルゴリズムをめぐって学習を展開する.
関連分析
関連分析は、大規模なデータセットで興味深い関係を探すタスクです.これらのタスクには、頻繁なアイテムセットと関連ルールの2つの形式があります.頻繁なアイテムセットは、よく1つに現れるアイテムの集合です.関連ルールは、2つのアイテムの間に強い関係がある可能性があることを示しています.この2つの概念は、ある店の取引リストと組み合わせて説明することができます.
取引番号
商品
0
豆乳、イチゴ
1
イチゴ、おむつ、ビール、唐辛子ソース
2
豆乳、おむつ、キュウリ、ビスケット
3
キュウリ、ビスケット、おむつ、ビール
4
きゅうり、ビール、おむつ、きゅうり
頻度アイテムセットとは、「ビール、おむつ、ビスケット」など、よく一緒に現れるアイテムの集合のことで、頻度アイテムセットの一例ですが、上記の表によればおむつ->ビールという関連ルールもあります.
大規模なデータを関連分析してデータ間に存在する興味深い関係を発見するには、問題が来て、どのような関係が面白いのでしょうか.この面白さはどのように定義されているのでしょうか.サポート(support)と信頼性(信頼性confidence)で定義できます.1つのアイテムセットの支持度とは、データセットがそのアイテムセット記録を含む割合を指し、前例では{豆乳}の支持度は2/5、{ビール、おむつ}の支持度は3/5であった.信頼性は,{おむつ}->{ビール}のような関連規則に対して定義され,支持度({おむつ,ワイン})/支持度(おむつ)と定義される.
二Apriori原理
上記では,検出データ間の関係をサポート度と信頼性により定義した.商品リストには、単一の商品からなる頻繁なアイテムセットが存在する可能性があり、もちろん2つ以上の商品からなる頻繁なアイテムセットも存在することを知っています.頻繁なアイテムセットのサポート度を計算する場合、通常はすべての商品リストを遍歴して求める必要があります.リスト数が少ない場合は問題ありませんが、リスト数が千以上ある場合、計算量が大きすぎて、この方法は適用されません.
では、上記の問題をどのように解決すればいいのか、Aprioriの原理は解決できます!Aprioriの原理は、あるアイテムセットが頻繁であれば、そのすべてのサブセットも頻繁であるに違いないということです.この原理は表面的にはあまり役に立たないが,逆に,1つのアイテムセットが非頻繁アイテムセットである場合,対応するスーパーセットはすべて非頻繁アイテムセットである.これにより、1つのアイテムセットが非頻繁なアイテムセットであることを決定した後、対応するスーパーセットのサポート度を計算しないことができます.これは、アイテムセット数の指数的な増加を大幅に回避し、頻繁なアイテムセットをより合理的に計算することができます.
トリプルAprioriアルゴリズム
(1)Aprioriアルゴリズムを用いて頻繁なアイテムセットを発見する
Aprioriアルゴリズムは、頻繁なアイテムセットを発見するための方法です.Aprioriアルゴリズムの2つの入力パラメータは,それぞれ最小支持度とデータセットである.このアルゴリズムは、まず、すべての単一物品のアイテムセットリストを生成し、巡回した後、最小サポート要件を満たさないアイテムセットを削除する.次に、残りのセットを組み合わせて2つの要素を含むアイテムセットを生成し、最小サポート度を満たさないアイテムセットを削除します.最小サポートを満たさないすべてのアイテムセットを削除するまで、この手順を繰り返します.
まずpythonを使用して、すべての単一のアイテムに対応するアイテムセットを生成し、次のコードで頻繁なアイテムセットを得る関数を構築します.
上記のコードをテストします.
構築された単一の商品アイテムセットと組み合わせて、上記のコードが利用可能であると判断します.これに基づいて、以前の分析と組み合わせて完全なアルゴリズムを構築し、コードは以下の通りです.
これにより,頻繁なアイテムセットを得るという考え方が実現され,以下で検証する.
結果は、すべての頻繁なアイテムセットと対応するサポート度であり、予想に合致します.
(2)頻度項目集中から関連ルールを掘り起こす
頻繁なアイテムセットはAprioriアルゴリズムを使用して探すことができます.もちろん、関連ルールを見つける必要があります.頻繁なアイテムセットがあると仮定すると、「...->...」と表す関連ルールがある可能性があります.しかし、逆に必ずしも成立するとは限らない(矢印の左側に対応する集合が前件であり、矢印の右側に対応する集合が後件である).
前節では,最小支持度を用いて頻繁な項セットを量子化し,対応する信頼性を用いて関連規則を量子化した.1つのルールp->Hの信頼性はsupport(P|H)/support(P)と定義され、その関連ルールを見つけるために、可能なルールのリストを作成し、各ルールの信頼性をテストし、信頼性の最小要求と結びつけて、関連ルールを得ることができます.頻繁なアイテムセットを探すのと同様に、頻繁なアイテムセットごとに多くの関連ルールを生成できます.これにより、多くの関連ルールが生成されます.Aprioriの原理と結びつけて,ある規則が最小信頼性の要求を満たさない場合,その規則のすべてのサブセットも最小信頼性の要求を満たさないため,テストを必要とする規則の数を減らし,問題を簡略化することができる.
関連ルールを探す考えは、頻繁なアイテムセットからルールリストを作成し、まずルールの右側を1つの要素に限定し、これらのルールをテストし、次に残りのルールを結合して新しいルールリストを作成し、ルールの右側を2つの要素に制限し、このように一歩一歩実現します.コードは以下の通りです.
次に、上記の手順をテストします.
上記のプログラムの結果は,信頼性閾値minConfを交換することで異なる関連規則を得ることができる小さなデータセットでアルゴリズムが実現できることを示している.
四毒キノコの特徴を発見する
上記ではAprioriアルゴリズムを小さなデータセットに適用しましたが、本節ではアルゴリズムを実際のデータに適用します.頻繁なアイテムセットではなく、特定の規則的な特徴を探している場合があります.本節では、毒キノコのいくつかの共通の特徴を探し、毒キノコ特有の特徴を発見し、UCIデータベースからデータセットmushroomを探します.dat,そのうち第1の特徴は有毒または無毒を示し,2は有毒を示す.次のテストを行います.
結果は次のとおりです.
これにより毒キノコに関する特徴が発見される.
これが私のこのアルゴリズムに対する理解と総括であり、間違いは避けられない.
「ビールとおむつ」の例は多くの人が聞いたことがあるだろう.スーパーでは、おむつとビールの2つの風馬牛が合わない商品が並んでいるという興味深い現象が発見された.しかし、この奇妙な措置はおむつとビールの販売台数を大幅に増加させた.これは冗談ではなく、米国のウォルマートチェーンスーパーで起きた実例だ.もともと、アメリカの女性は家で子供の世話をしているので、退勤して家に帰る途中で子供のためにおむつを買うように夫に言いつけ、夫はおむつを買うと同時に自分の好きなビールを買うように言いつけていた.この発見は業者に大量の利益をもたらしたが、煙の海のように雑然としたデータから、ビールとおむつ販売のつながりをどのように発見したのだろうか.このような大規模なデータから物品間の隠れた関係を発見する方法は関連分析と呼ばれ,本論文で主に研究する一般的な分析方法であり,Aprioriアルゴリズムは最も有名な関連規則マイニングアルゴリズムの一つである.次に,このアルゴリズムをめぐって学習を展開する.
関連分析
関連分析は、大規模なデータセットで興味深い関係を探すタスクです.これらのタスクには、頻繁なアイテムセットと関連ルールの2つの形式があります.頻繁なアイテムセットは、よく1つに現れるアイテムの集合です.関連ルールは、2つのアイテムの間に強い関係がある可能性があることを示しています.この2つの概念は、ある店の取引リストと組み合わせて説明することができます.
取引番号
商品
0
豆乳、イチゴ
1
イチゴ、おむつ、ビール、唐辛子ソース
2
豆乳、おむつ、キュウリ、ビスケット
3
キュウリ、ビスケット、おむつ、ビール
4
きゅうり、ビール、おむつ、きゅうり
頻度アイテムセットとは、「ビール、おむつ、ビスケット」など、よく一緒に現れるアイテムの集合のことで、頻度アイテムセットの一例ですが、上記の表によればおむつ->ビールという関連ルールもあります.
大規模なデータを関連分析してデータ間に存在する興味深い関係を発見するには、問題が来て、どのような関係が面白いのでしょうか.この面白さはどのように定義されているのでしょうか.サポート(support)と信頼性(信頼性confidence)で定義できます.1つのアイテムセットの支持度とは、データセットがそのアイテムセット記録を含む割合を指し、前例では{豆乳}の支持度は2/5、{ビール、おむつ}の支持度は3/5であった.信頼性は,{おむつ}->{ビール}のような関連規則に対して定義され,支持度({おむつ,ワイン})/支持度(おむつ)と定義される.
二Apriori原理
上記では,検出データ間の関係をサポート度と信頼性により定義した.商品リストには、単一の商品からなる頻繁なアイテムセットが存在する可能性があり、もちろん2つ以上の商品からなる頻繁なアイテムセットも存在することを知っています.頻繁なアイテムセットのサポート度を計算する場合、通常はすべての商品リストを遍歴して求める必要があります.リスト数が少ない場合は問題ありませんが、リスト数が千以上ある場合、計算量が大きすぎて、この方法は適用されません.
では、上記の問題をどのように解決すればいいのか、Aprioriの原理は解決できます!Aprioriの原理は、あるアイテムセットが頻繁であれば、そのすべてのサブセットも頻繁であるに違いないということです.この原理は表面的にはあまり役に立たないが,逆に,1つのアイテムセットが非頻繁アイテムセットである場合,対応するスーパーセットはすべて非頻繁アイテムセットである.これにより、1つのアイテムセットが非頻繁なアイテムセットであることを決定した後、対応するスーパーセットのサポート度を計算しないことができます.これは、アイテムセット数の指数的な増加を大幅に回避し、頻繁なアイテムセットをより合理的に計算することができます.
トリプルAprioriアルゴリズム
(1)Aprioriアルゴリズムを用いて頻繁なアイテムセットを発見する
Aprioriアルゴリズムは、頻繁なアイテムセットを発見するための方法です.Aprioriアルゴリズムの2つの入力パラメータは,それぞれ最小支持度とデータセットである.このアルゴリズムは、まず、すべての単一物品のアイテムセットリストを生成し、巡回した後、最小サポート要件を満たさないアイテムセットを削除する.次に、残りのセットを組み合わせて2つの要素を含むアイテムセットを生成し、最小サポート度を満たさないアイテムセットを削除します.最小サポートを満たさないすべてのアイテムセットを削除するまで、この手順を繰り返します.
まずpythonを使用して、すべての単一のアイテムに対応するアイテムセットを生成し、次のコードで頻繁なアイテムセットを得る関数を構築します.
# -*- coding: cp936 -*-
'''
Apriori
Ben
2015.09.28
'''
#coding:utf-8
from numpy import *
def loadData():
return[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
def createC1(dataSet):
c1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in c1:
c1.append([item])
c1.sort()
return map(frozenset,c1)
def scanD(D,Ck,minSupport):
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):# tid can
if not ssCnt.has_key(can):
ssCnt[can] = 1
else:
ssCnt[can] += 1
numItems = float(len(D))
retList = []
supportData = {}
for key in ssCnt:
support = ssCnt[key] / numItems
if support >= minSupport:
retList.insert(0,key)
supportData[key] = support
return retList,supportData上記のコードをテストします.
#test
dataSet = loadData()
c1 = createC1(dataSet)
D = map(set,dataSet)
L1,supportData = scanD(D,c1,0.5)
print L1
print supportData構築された単一の商品アイテムセットと組み合わせて、上記のコードが利用可能であると判断します.これに基づいて、以前の分析と組み合わせて完全なアルゴリズムを構築し、コードは以下の通りです.
#
def aprioriGen(Lk,k):
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1,lenLk):
L1 = list(Lk[i])[:k-2]
L2 = list(Lk[j])[:k-2]
L1.sort()
L2.sort()
if L1 == L2:
retList.append(Lk[i]|Lk[j])
return retList
def apriori(dataSet,minSupport = 0.5):
C1 = createC1(dataSet)
D = map(set,dataSet)
L1,supportData = scanD(D,C1,minSupport)
L = [L1]
k = 2
while (len(L[k-2]) > 0):
Ck = aprioriGen(L[k-2],k)
Lk,supK = scanD(D,Ck,minSupport)
supportData.update(supK)
L.append(Lk)
k += 1
return L,supportDataこれにより,頻繁なアイテムセットを得るという考え方が実現され,以下で検証する.
dataSet = loadData()
minSupport = 0.5
a,b = apriori(dataSet,minSupport)
print a
print b結果は、すべての頻繁なアイテムセットと対応するサポート度であり、予想に合致します.
(2)頻度項目集中から関連ルールを掘り起こす
頻繁なアイテムセットはAprioriアルゴリズムを使用して探すことができます.もちろん、関連ルールを見つける必要があります.頻繁なアイテムセットがあると仮定すると、「...->...」と表す関連ルールがある可能性があります.しかし、逆に必ずしも成立するとは限らない(矢印の左側に対応する集合が前件であり、矢印の右側に対応する集合が後件である).
前節では,最小支持度を用いて頻繁な項セットを量子化し,対応する信頼性を用いて関連規則を量子化した.1つのルールp->Hの信頼性はsupport(P|H)/support(P)と定義され、その関連ルールを見つけるために、可能なルールのリストを作成し、各ルールの信頼性をテストし、信頼性の最小要求と結びつけて、関連ルールを得ることができます.頻繁なアイテムセットを探すのと同様に、頻繁なアイテムセットごとに多くの関連ルールを生成できます.これにより、多くの関連ルールが生成されます.Aprioriの原理と結びつけて,ある規則が最小信頼性の要求を満たさない場合,その規則のすべてのサブセットも最小信頼性の要求を満たさないため,テストを必要とする規則の数を減らし,問題を簡略化することができる.
関連ルールを探す考えは、頻繁なアイテムセットからルールリストを作成し、まずルールの右側を1つの要素に限定し、これらのルールをテストし、次に残りのルールを結合して新しいルールリストを作成し、ルールの右側を2つの要素に制限し、このように一歩一歩実現します.コードは以下の通りです.
#
def generateRules(L,supportData,minConf = 0.7):
bigRuleList = []
for i in range(1,len(L)):
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]
if (i > 1):
rulesFromConseq(freqSet,H1,supportData,bigRuleList,minConf)
else:
calcConf(freqSet,H1,supportData,bigRuleList,minConf)
return bigRuleList
#
def calcConf(freqSet,H,supportData,brl,minConf = 0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet - conseq]
if conf >= minConf:
print freqSet - conseq,'-->',conseq,'conf:',conf
brl.append((freqSet-conseq,conseq,conf))
prunedH.append(conseq)
return prunedH
#
def rulesFromConseq(freqSet,H,supportData,br1,minConf = 0.7):
m = len(H[0])
if (len(freqSet)>(m + 1)):
Hmp1 = aprioriGen(H,m+1)
Hmp1 = calcConf(freqSet,Hmp1,supportData,br1,minConf)
if (len(Hmp1) > 1):
rulesFromConseq(freqSet,Hmp1,supportData,br1,minConf)次に、上記の手順をテストします.
#test
dataSet = loadData()
minSupport = 0.5
L,suppData = apriori(dataSet,minSupport)
rules = generateRules(L,suppData,minConf = 0.5)
print rules上記のプログラムの結果は,信頼性閾値minConfを交換することで異なる関連規則を得ることができる小さなデータセットでアルゴリズムが実現できることを示している.
四毒キノコの特徴を発見する
上記ではAprioriアルゴリズムを小さなデータセットに適用しましたが、本節ではアルゴリズムを実際のデータに適用します.頻繁なアイテムセットではなく、特定の規則的な特徴を探している場合があります.本節では、毒キノコのいくつかの共通の特徴を探し、毒キノコ特有の特徴を発見し、UCIデータベースからデータセットmushroomを探します.dat,そのうち第1の特徴は有毒または無毒を示し,2は有毒を示す.次のテストを行います.
mushDatSet = [line.split() for line in open('mushroom.dat').readlines()]
L,supportData = apriori(mushDatSet,minSupport = 0.3)
for item in L[1]:
if item.intersection('2'):
print item結果は次のとおりです.
frozenset(['2', '59'])
frozenset(['39', '2'])
frozenset(['2', '67'])
frozenset(['2', '34'])
frozenset(['2', '23'])
frozenset(['2', '86'])
frozenset(['76', '2'])
frozenset(['90', '2'])
frozenset(['2', '53'])
frozenset(['93', '2'])
frozenset(['63', '2'])
frozenset(['2', '28'])
frozenset(['2', '85'])
frozenset(['2', '36'])これにより毒キノコに関する特徴が発見される.
これが私のこのアルゴリズムに対する理解と総括であり、間違いは避けられない.