apriori.md

文章目录

1. 1. 实现方法
2. 2. 算法实现如下

Apriori,关联规则挖掘算法，即找出来经常一起购买的商品。

  其中涉及两个概念：支持度和置信度。支持度support=P(AB),指AB同时发生的概率，置信度confidence=P(AB)/P(AB)/P(A),指A发生的基础上B发生的概率，当两者都大于阈值时，认为是频繁项集。
  频繁项集用到一个性质：所有频繁项集的子集都是频繁项集，反过来说，如果一个集合不是频繁项集，那么继续向上扩展仍不可能是频繁项集。

实现方法

---

1 扫描整个数据库，对每个候选项进行支持度计数得到C1

2 比较候选项支持度与最小支持度，产生1维最大项目集L1

3 由L1组合产生候选项集C2，组合时只选择只有最后一个不一致的项

4 扫描D对C2中的项计数，并按照阈值产生L2

5 按照这个步骤往复，直到L2组合后不产生新的频繁候选项集

算法实现如下

---

# -*- coding: UTF-8 -*-

def apriori(T,minsup):
	item = {}
	for t in T:
		for i in t:
			if i in item:
				item[i] += 1
			else:
				item[i] = 1
	citems = []
	for i in item.keys():
		citems.append([i])
	fitems = []
	all_count_items = []
	citems.sort()
	for key in citems:
		if item[key[0]]>=minsup:
			fitems.append(key)
			all_count_items.append(item[key[0]])
	

	all_fitems = fitems
	while fitems !=[]:
		citems = c_gen(fitems)
		count_items = get_count(T,citems)
		fitems = get_fitems(citems,count_items,minsup,T,all_count_items)
		for key in fitems:
			all_fitems.append(key)


	return all_fitems,all_count_items

def get_fitems(citems,count_items,minsup,T,all_count_items):
	'''
	从citems中找出来高于minsup的元素，然后返回
	'''
	temp = []
	for i in range(len(citems)):
		if count_items[i]>minsup:
			temp.append(citems[i])
			all_count_items.append(count_items[i])

	return temp




def get_count(T,citems):
	'''
	判断T中citems每个元素出现的次数，并返回频数数组
	'''
	count = []
	for key in citems:
		c = 0
		for t in T:
			flag = True;
			for i in key:
				if i not in t:
					flag = False
			if flag:
				c +=1
		count.append(c)
	return count

def c_gen(fitems):
	'''
	从fitems中生成下一个集合的citems，
	'''
	temp=[]
	for i in fitems:
		for j in fitems:
			key = []
			if(i !=j and i[:-1]==j[:-1]):
				key = i[:-1]
				key.append(i[-1])
				key.append(j[-1])
				key.sort()
			if key not in temp and key !=[]:
				temp.append(key)
	return temp

T = [['1','3','4'],['2','3','5'],['1','2','3','5'],['2','5']]
minsup = len(T)*0.3
F = apriori(T, minsup)
print F