機械学習実戦---読書ノート:11章Aprioriアルゴリズムを用いた関連分析
7382 ワード
#!/usr/bin/env python
# encoding: utf-8
'''
<> 11 Apriori
:
1
:
:
2 Apriori
:
:
:
:
:
:
:
0 ，
1 ， ， ，
2 ， ， ，
3 ， ， ，
4 ， ， ，
: 。
，{ } 4/5
5 3 : { ， }，{ ， } 3/5
:
/ :
: { }->{ } 。
: " ({ ， })/ ({ })
{ ， } 3/5, { } 4/5，
-> =3/4=0.75
， ， 75% 。
3 Apriori
: 。
: ， 。
， 。
: {0, 1} ， {0} {1} 。
apriori: 。 ， ， 。
: 。
， 。
: Apriori ， 。
4 Apriori
: 。
: ， 。
。
Apriori :
:
:
1:
2： ，
3:
4： ， 。
5： ， 。
5 Apriori
:
0
k
k+1
apriori :
: dataSet( ， )； minSupport( )
: ( ， frozenset )
:
1: 1 C1， :
1.1 ( )
1.1.1 ；
1.1.2 ， ；
1.2 ， fronzenset
2: C1， L1, ,
:
2.1: ssCnt
2.2: C1 。
2.2.1 C1 ， 。
2.3: 。
2.4: 2.1 ssCnt ， 。
2.4.1 ，
2.4.2
2.5: ，
3: L， k=2
4: L[k-2] 0， 5； ， ， L
5： L[k-2] k， Ck, :
5.1
5.2 k-2 ， ，
5.3 ， Ck
6: Ck, Lk Lk ，
7: L Lk, k
:
Ck, ， --> Lk
Lk, k+1 -> Ck+1
Ck+1, ， --> Lk+1
'''
def loadDataSet():
return [ [1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5] ]
'''
: 1
:
1:
2: ；
2.1 ， ；
3: ， fronzenset
'''
def createC1(dataSet):
if not dataSet:
return frozenset()
result = []
for arr in dataSet:
for value in arr:
if [value] not in result:
result.append([value])
result.sort()
'''
frozenset: ， ，
。
'''
return map(frozenset, result)
'''
: C1 L1。
: D, Ck, minSupport
:
:
1: ssCnt
2: C1 。
2.1 C1 ， 。
3: 。
4: 1 ssCnt ， 。
4.1 ，
4.2
5: ，
: 。
，
， ， 。
'''
def scanD(D, Ck, minSupport):
if not D or not Ck:
print "D is empty or Ck is empty, D is: {D} , Ck is: {Ck}".format(D=D, Ck=Ck)
canToTimes = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
if canToTimes.has_key(can):
canToTimes[can] += 1
else:
canToTimes[can] = 1
result = []
canToSupport = {}
length = len(D)
for can, times in canToTimes.iteritems():
support = float(times) / length
if support >= minSupport:
result.insert(0, can)
canToSupport[can] = support
return result, canToSupport
'''
:
: Lk, k( +1)
: Ck。
: {0}, {1}，{2} ， {0, 1}, {0, 2} {1,2}
:
1:
2: k-2 ， ，
'''
def aprioriGen(Lk, k):
if not Lk or k < 2:
print "Lk is empty or k < 2, Lk: {Lk}, k: {k}".format(Lk=Lk, k=k)
return
length = len(Lk)
results = []
for i in range(length):
for j in range(i + 1, length):
list1 = list(Lk[i])[: k - 2]
list2 = list(Lk[j])[: k - 2]
list1.sort()
list2.sort()
if list1 == list2:
result = Lk[i] | Lk[j]
results.append(result)
return results
'''
:
: dataSet( ， )； minSupport( )
: ( ， frozenset )
:
1: 1 C1， :
1.1 ( )
1.1.1 ；
1.1.2 ， ；
1.2 ， fronzenset
2: C1， L1, ,
:
2.1: ssCnt
2.2: C1 。
2.2.1 C1 ， 。
2.3: 。
2.4: 2.1 ssCnt ， 。
2.4.1 ，
2.4.2
2.5: ，
3: L， k=2
4: L[k-2] 0， 5； ， ， L
5： L[k-2] k， Ck, :
5.1
5.2 k-2 ， ，
5.3 ， Ck
6: Ck, Lk Lk ，
7: L Lk, k
:
Ck, ， --> Lk
Lk, k+1 -> Ck+1
Ck+1, ， --> Lk+1
...
'''
def apriori(dataSet, minSupport=0.5):
C1 = createC1(dataSet)
D = map(set, dataSet)
L1, supportDict = scanD(D, C1, minSupport)
L = [L1]
k = 2
while len(L[k - 2]) > 0:
Ck = aprioriGen(L[k-2], k)
Lk, partialSupportDict = scanD(D, Ck, minSupport)
supportDict.update(partialSupportDict)
# note, Lk may be empty, if Lk is empty, it needs to end this recycle
if not Lk:
break
L.append(Lk)
k += 1
return L, supportDict
def process():
dataSet = loadDataSet()
L, supportDict = apriori(dataSet)
print " : {supportDict}".format(
supportDict=supportDict
)
for i, arr in enumerate(L):
print " {length} : {arr} ".format(length=i+1, arr=arr)
# C1 = createC1(dataSet)
# print "C1: {C1}".format(C1=C1)
# D = map(set, dataSet)
# print "D: {D}".format(D=D)
# minSupport = 0.5
# L1, canToSupport = scanD(D, C1, minSupport)
# print "L1: {L1},canToSupport: {canToSupport}".format(L1=L1, canToSupport=canToSupport)
if __name__ == "__main__":
process()