频繁项集挖掘Apriori算法及其Python实现
发布时间:2020-12-14 05:04:01 所属栏目:大数据 来源:网络整理
导读:Apriori算法是通过限制候选产生发现频繁项集。 Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索(k+1)项集。首先,通过扫描数据库,累计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合,记为L1。然后,使用L1找出频繁2项集的
Apriori算法是通过限制候选产生发现频繁项集。 Apriori算法使用一种称为逐层搜索的迭代方法,其中k项集用于探索(k+1)项集。首先,通过扫描数据库,累计每个项的计数,并收集满足最小支持度的项,找出频繁1项集的集合,记为L1。然后,使用L1找出频繁2项集的集合L2,使用L2找出L3,如此下去,直到不能再找到频繁k项集。 为了提高频繁项集逐层产生的效率,一种称为先验性质(Apriori property)的重要性质用于压缩搜索空间。 先验性质:频繁项集的所有非空子集也一定是频繁的。 具体过程如下图所示: Python实现: 我们的期望: 输入:数据库中数据和最小支持度 实现如下: #coding=utf-8 # 全文utf-8编码
import sys
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,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: # 只要有一个不匹配,就返回False
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
D = [['A','B','C','D'],['B','E'],['A','D','D']]
F = apriori(D,0.7)
print 'nfrequent itemset:n',F
原文 http://www.jianshu.com/p/00103435ef89 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |