#coding=utf-8 # 全文utf-8编码
import sys
D = [['A','B','C','D'],['B','C','E'],['A','B','C','E'],['B','D','E'],['A','B','C','D']]
F = apriori(D, 0.7)
def apriori(D, minSup):
'''频繁项集用keys表示,
key表示项集中的某一项,
cutKeys表示经过剪枝步的某k项集。
C表示某k项集的每一项在事务数据库D中的支持计数
'''
C1 = {}
for T in D:
for I in T:
if I in C1:
C1[I] += 1
else:
C1[I] = 1
print C1
_keys1 = C1.keys()
keys1 = []
for i in _keys1:
keys1.append([i])
n = len(D)
cutKeys1 = []
for k in keys1[:]:
if C1[k[0]]*1.0/n >= minSup:
cutKeys1.append(k)
cutKeys1.sort()
keys = cutKeys1
all_keys = []
while keys != []:
C = getC(D, keys)
cutKeys = getCutKeys(keys, C, minSup, len(D))
for key in cutKeys:
all_keys.append(key)
keys = aproiri_gen(cutKeys)
return all_keys
def getC(D, keys):
'''对keys中的每一个key进行计数'''
C = []
for key in keys:
c = 0
for T in D:
have = True
for k in key:
if k not in T:
have = False
if have:
c += 1
C.append(c)
return C
def getCutKeys(keys, C, minSup, length):
'''剪枝步'''
for i, key in enumerate(keys):
if float(C[i]) / length < minSup:
keys.remove(key)
return keys
def keyInT(key, T):
'''判断项key是否在数据库中某一元组T中'''
for k in key:
if k not in T:
return False
return True
def aproiri_gen(keys1):
'''连接步'''
keys2 = []
for k1 in keys1:
for k2 in keys1:
if k1 != k2:
key = []
for k in k1:
if k not in key:
key.append(k)
for k in k2:
if k not in key:
key.append(k)
key.sort()
if key not in keys2:
keys2.append(key)
return keys2
print '\nfrequent itemset:\n', F
I2NvZGluZz11dGYtOCAgICAgICAgICAgICAgICAgICAgICAgICMg5YWo5paHdXRmLTjnvJbnoIEKaW1wb3J0IHN5cwpEID0gW1snQScsJ0InLCdDJywnRCddLFsnQicsJ0MnLCdFJ10sWydBJywnQicsJ0MnLCdFJ10sWydCJywnRCcsJ0UnXSxbJ0EnLCdCJywnQycsJ0QnXV0KRiA9IGFwcmlvcmkoRCwgMC43KQpkZWYgYXByaW9yaShELCBtaW5TdXApOgoJCgknJyfpopHnuYHpobnpm4bnlKhrZXlz6KGo56S677yMCglrZXnooajnpLrpobnpm4bkuK3nmoTmn5DkuIDpobnvvIwKCWN1dEtleXPooajnpLrnu4/ov4fliarmnp3mraXnmoTmn5Br6aG56ZuG44CCCglD6KGo56S65p+Qa+mhuembhueahOavj+S4gOmhueWcqOS6i+WKoeaVsOaNruW6k0TkuK3nmoTmlK/mjIHorqHmlbAKCScnJwoKCUMxID0ge30KCWZvciBUIGluIEQ6CgkJZm9yIEkgaW4gVDoKCQkJaWYgSSBpbiBDMToKCQkJCUMxW0ldICs9IDEKCQkJZWxzZToKCQkJCUMxW0ldID0gMQoKCXByaW50IEMxCglfa2V5czEgPSBDMS5rZXlzKCkKCglrZXlzMSA9IFtdCglmb3IgaSBpbiBfa2V5czE6CgkJa2V5czEuYXBwZW5kKFtpXSkKCgluID0gbGVuKEQpCgljdXRLZXlzMSA9IFtdCglmb3IgayBpbiBrZXlzMVs6XToKCQlpZiBDMVtrWzBdXSoxLjAvbiA+PSBtaW5TdXA6CgkJCWN1dEtleXMxLmFwcGVuZChrKQoJCgljdXRLZXlzMS5zb3J0KCkKCgoJa2V5cyA9IGN1dEtleXMxCglhbGxfa2V5cyA9IFtdCgl3aGlsZSBrZXlzICE9IFtdOgoJCUMgPSBnZXRDKEQsIGtleXMpCgkJY3V0S2V5cyA9IGdldEN1dEtleXMoa2V5cywgQywgbWluU3VwLCBsZW4oRCkpCgkJZm9yIGtleSBpbiBjdXRLZXlzOgoJCQlhbGxfa2V5cy5hcHBlbmQoa2V5KQoJCWtleXMgPSBhcHJvaXJpX2dlbihjdXRLZXlzKQoKCXJldHVybiBhbGxfa2V5cwoKZGVmIGdldEMoRCwga2V5cyk6CgknJyflr7lrZXlz5Lit55qE5q+P5LiA5Liqa2V56L+b6KGM6K6h5pWwJycnCglDID0gW10KCWZvciBrZXkgaW4ga2V5czoKCQljID0gMAoJCWZvciBUIGluIEQ6CgkJCWhhdmUgPSBUcnVlCgkJCWZvciBrIGluIGtleToKCQkJCWlmIGsgbm90IGluIFQ6CgkJCQkJaGF2ZSA9IEZhbHNlCgkJCWlmIGhhdmU6CgkJCQljICs9IDEKCQlDLmFwcGVuZChjKQoJcmV0dXJuIEMKCmRlZiBnZXRDdXRLZXlzKGtleXMsIEMsIG1pblN1cCwgbGVuZ3RoKToKCScnJ+WJquaeneatpScnJwoJZm9yIGksIGtleSBpbiBlbnVtZXJhdGUoa2V5cyk6CgkJaWYgZmxvYXQoQ1tpXSkgLyBsZW5ndGggPCBtaW5TdXA6CgkJCWtleXMucmVtb3ZlKGtleSkKCXJldHVybiBrZXlzCgoKCmRlZiBrZXlJblQoa2V5LCBUKToKCScnJ+WIpOaWremhuWtleeaYr+WQpuWcqOaVsOaNruW6k+S4reafkOS4gOWFg+e7hFTkuK0nJycKCWZvciBrIGluIGtleToKCQlpZiBrIG5vdCBpbiBUOgoJCQlyZXR1cm4gRmFsc2UKCXJldHVybiBUcnVlCgoKZGVmIGFwcm9pcmlfZ2VuKGtleXMxKToKCScnJ+i/nuaOpeatpScnJwoJa2V5czIgPSBbXQoJZm9yIGsxIGluIGtleXMxOgoJCWZvciBrMiBpbiBrZXlzMToKCQkJaWYgazEgIT0gazI6CgkJCQlrZXkgPSBbXQoJCQkJZm9yIGsgaW4gazE6CgkJCQkJaWYgayBub3QgaW4ga2V5OgoJCQkJCQlrZXkuYXBwZW5kKGspCgkJCQlmb3IgayBpbiBrMjoKCQkJCQlpZiBrIG5vdCBpbiBrZXk6CgkJCQkJCWtleS5hcHBlbmQoaykKCQkJCWtleS5zb3J0KCkKCQkJCWlmIGtleSBub3QgaW4ga2V5czI6CgkJCQkJa2V5czIuYXBwZW5kKGtleSkKCQkJCglyZXR1cm4ga2V5czIKCgoKCgpwcmludCAnXG5mcmVxdWVudCBpdGVtc2V0OlxuJywgRgo=