理解关联规则apriori算法：Apriori算法是第一个关联规则挖掘算法，也是最经典的算法，它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接【类矩阵运算】与剪枝【去掉那些没必要的中间结果】组成。

理解关联规则apriori算法：

一、概念

表1 某超市的交易数据库交易号TID顾客购买的商品交易号TID顾客购买的商品

T1bread, cream, milk, teaT6bread, tea

T2bread, cream, milkT7beer, milk, tea

T3cake, milkT8bread, tea

T4milk, teaT9bread, cream, milk, tea

T5bread, cake, milkT10bread, milk, tea

定义一：设I={i1,i2,…,im}，是m个不同的项目的集合，每个ik称为一个项目。项目的集合I称为项集。其元素的个数称为项集的长度，长度为k的项集称为k-项集。引例中每个商品就是一个项目，项集为I={bread, beer, cake,cream, milk, tea}，I的长度为6。

定义二：每笔交易T是项集I的一个子集。对应每一个交易有一个唯一标识交易号，记作TID。交易全体构成了交易数据库D，|D|等于D中交易的个数。引例中包含10笔交易，因此|D|=10。

定义三：对于项集X，设定count(X⊆T)为交易集D中包含X的交易的数量，则项集X的支持度为：

support(X)=count(X⊆T)/|D|

引例中X={bread, milk}出现在T1，T2，T5，T9和T10中，所以支持度为0.5。

定义四：最小支持度是项集的最小支持阀值，记为SUPmin，代表了用户关心的关联规则的最低重要性。支持度不小于SUPmin 的项集称为频繁集，长度为k的频繁集称为k-频繁集。如果设定SUPmin为0.3，引例中{bread, milk}的支持度是0.5，所以是2-频繁集。

定义五：关联规则是一个蕴含式：

R：X⇒Y

其中X⊂I，Y⊂I，并且X∩Y=⌀。表示项集X在某一交易中出现，则导致Y以某一概率也会出现。用户关心的关联规则，可以用两个标准来衡量：支持度和可信度。

定义六：关联规则R的支持度是交易集同时包含X和Y的交易数与|D|之比。即：

support(X⇒Y)=count(X⋃Y)/|D|

支持度反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。

定义七：对于关联规则R，可信度是指包含X和Y的交易数与包含X的交易数之比。即：

confidence(X⇒Y)=support(X⇒Y)/support(X)

可信度反映了如果交易中包含X，则交易包含Y的概率。一般来说，只有支持度和可信度较高的关联规则才是用户感兴趣的。

定义八：设定关联规则的最小支持度和最小可信度为SUPmin和CONFmin。规则R的支持度和可信度均不小于SUPmin和CONFmin ，则称为强关联规则。关联规则挖掘的目的就是找出强关联规则，从而指导商家的决策。

这八个定义包含了关联规则相关的几个重要基本概念，关联规则挖掘主要有两个问题：找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集。

利用频繁项集生成所需要的关联规则，根据用户设定的最小可信度筛选出强关联规则。

目前研究人员主要针对第一个问题进行研究，找出频繁集是比较困难的，而有了频繁集再生成强关联规则就相对容易了。

二、理论基础

首先来看一个频繁集的性质。

定理：如果项目集X是频繁集，那么它的非空子集都是频繁集。

根据定理，已知一个k-频繁集的项集X，X的所有k-1阶子集都肯定是频繁集，也就肯定可以找到两个k-1频繁集的项集，它们只有一项不同，且连接后等于X。这证明了通过连接k-1频繁集产生的k-候选集覆盖了k-频繁集。同时，如果k-候选集中的项集Y，包含有某个k-1阶子集不属于k-1频繁集，那么Y就不可能是频繁集，应该从候选集中裁剪掉。Apriori算法就是利用了频繁集的这个性质。

三、算法步骤：

首先是测试数据：交易ID商品ID列表

T100I1，I2，I5

T200I2，I4

T300I2，I3

T400I1，I2，I4

T500I1，I3

T600I2，I3

T700I1，I3

T800I1，I2，I3，I5

T900I1，I2，I3

算法的步骤图：

可以看到，第三轮的候选集发生了明显的缩小，这是为什么呢？

请注意取候选集的两个条件：

1.两个K项集能够连接的两个条件是，它们有K-1项是相同的。所以，(I2，I4)和(I3，I5)这种是不能够进行连接的。缩小了候选集。

2.如果一个项集是频繁集，那么它不存在不是子集的频繁集。比如(I1，I2)和(I1，I4)得到(I1，I2，I4)，而(I1，I2，I4)存在子集(I1，I4)不是频繁集。缩小了候选集。

第三轮得到的2个候选集，正好支持度等于最小支持度。所以，都算入频繁集。

这时再看第四轮的候选集与频繁集结果为空

可以看到，候选集和频繁集居然为空了！因为通过第三轮得到的频繁集自连接得到{I1，I2，I3，I5}，它拥有子集{I2,I3,I5}，而{I2,I3,I5}不是频繁集，不满足：频繁集的子集也是频繁集这一条件，所以被剪枝剪掉了。所以整个算法终止，取最后一次计算得到的频繁集作为最终的频繁集结果：

也就是：['I1,I2,I3', 'I1,I2,I5']

四、代码：

编写Python代码实现Apriori算法。代码需要注意如下两点：由于Apriori算法假定项集中的项是按字典序排序的，而集合本身是无序的，所以我们在必要时需要进行set和list的转换；

由于要使用字典(support_data)记录项集的支持度，需要用项集作为key，而可变集合无法作为字典的key，因此在合适时机应将项集转为固定集合frozenset。def local_data(file_path): import pandas as pd

dt = pd.read_excel(file_path)

data = dt['con']

locdata = [] for i in data:

locdata.append(str(i).split(",")) # print(locdata) # change to [[1,2,3],[1,2,3]]

length = [] for i in locdata:

length.append(len(i)) # 计算长度并存储

# print(length)

ki = length[length.index(max(length))] # print(length[length.index(max(length))]) # length.index(max(length)读取最大值的位置，然后再定位取出最大值

return locdata,kidef create_C1(data_set): """

Create frequent candidate 1-itemset C1 by scaning data set.

Args:

data_set: A list of transactions. Each transaction contains several items.

Returns:

C1: A set which contains all frequent candidate 1-itemsets """

C1 = set() for t in data_set: for item in t:

item_set = frozenset([item])

C1.add(item_set) return C1def is_apriori(Ck_item, Lksub1): """

Judge whether a frequent candidate k-itemset satisfy Apriori property.

Args:

Ck_item: a frequent candidate k-itemset in Ck which contains all frequent

candidate k-itemsets.

Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

Returns:

True: satisfying Apriori property.

False: Not satisfying Apriori property. """

for item in Ck_item:

sub_Ck = Ck_item - frozenset([item]) if sub_Ck not in Lksub1: return False return Truedef create_Ck(Lksub1, k): """

Create Ck, a set which contains all all frequent candidate k-itemsets

by Lk-1's own connection operation.

Args:

Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.

k: the item number of a frequent itemset.

Return:

Ck: a set which contains all all frequent candidate k-itemsets. """

Ck = set()

len_Lksub1 = len(Lksub1)

list_Lksub1 = list(Lksub1) for i in range(len_Lksub1): for j in range(1, len_Lksub1):

l1 = list(list_Lksub1[i])

l2 = list(list_Lksub1[j])

l1.sort()

l2.sort() if l1[0:k-2] == l2[0:k-2]:

Ck_item = list_Lksub1[i] | list_Lksub1[j] # pruning

if is_apriori(Ck_item, Lksub1):

Ck.add(Ck_item) return Ckdef generate_Lk_by_Ck(data_set, Ck, min_support, support_data): """

Generate Lk by executing a delete policy from Ck.

Args:

data_set: A list of transactions. Each transaction contains several items.

Ck: A set which contains all all frequent candidate k-itemsets.

min_support: The minimum support.

support_data: A dictionary. The key is frequent itemset and the value is support.

Returns:

Lk: A set which contains all all frequent k-itemsets. """

Lk = set()

item_count = {} for t in data_set: for item in Ck: if item.issubset(t): if item not in item_count:

item_count[item] = 1 else:

item_count[item] += 1

t_num = float(len(data_set)) for item in item_count: if (item_count[item] / t_num) >= min_support:

Lk.add(item)

support_data[item] = item_count[item] / t_num return Lkdef generate_L(data_set, k, min_support): """

Generate all frequent itemsets.

Args:

data_set: A list of transactions. Each transaction contains several items.

k: Maximum number of items for all frequent itemsets.

min_support: The minimum support.

Returns:

L: The list of Lk.

support_data: A dictionary. The key is frequent itemset and the value is support. """

support_data = {}

C1 = create_C1(data_set)

L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)

Lksub1 = L1.copy()

L = []

L.append(Lksub1) for i in range(2, k+1):

Ci = create_Ck(Lksub1, i)

Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)

Lksub1 = Li.copy()

L.append(Lksub1) return L, support_datadef generate_big_rules(L, support_data, min_conf): """

Generate big rules from frequent itemsets.

Args:

L: The list of Lk.

support_data: A dictionary. The key is frequent itemset and the value is support.

min_conf: Minimal confidence.

Returns:

big_rule_list: A list which contains all big rules. Each big rule is represented

as a 3-tuple. """

big_rule_list = []

sub_set_list = [] for i in range(0, len(L)): for freq_set in L[i]: for sub_set in sub_set_list: if sub_set.issubset(freq_set):

conf = support_data[freq_set] / support_data[freq_set - sub_set]

big_rule = (freq_set - sub_set, sub_set, conf) if conf >= min_conf and big_rule not in big_rule_list: # print freq_set-sub_set, " => ", sub_set, "conf: ", conf big_rule_list.append(big_rule)

sub_set_list.append(freq_set) return big_rule_listif __name__ == "__main__": """

Test """

file_path = "test_aa.xlsx"

data_set,k = local_data(file_path)

L, support_data = generate_L(data_set, k, min_support=0.2)

big_rules_list = generate_big_rules(L, support_data, min_conf=0.4) print(L) for Lk in L: if len(list(Lk)) == 0: break

print("="*50) print("frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport") print("="*50) for freq_set in Lk: print(freq_set, support_data[freq_set]) print() print("Big Rules") for item in big_rules_list: print(item[0], "=>", item[1], "conf: ", item[2])

文件格式：

test_aa.xlsxname con

T1 2,3,5T2 1,2,4T3 3,5T5 2,3,4T6 2,3,5T7 1,2,4T8 3,5T9 2,3,4T10 1,2,3,4,5

环境

python版本：3.5

数据来源

数据来自51CTO网站的分享，点此下载

关联规则

所谓关联规则，就是指现实中同时发生两种不同事情之间的相关联程度，具体分析可以参考这篇博客，讲的很清晰

数据分析

这是数据文件

数据文件

其中movies中电影信息的内容如图所示

movies.dat

每行分别为电影id，电影名字，电影类型，每项之间用::分隔，rating.dat为收集的用户打分记录，users.dat为用户id对应的用户信息，personalRating.txt为个人打分，用来找到规律后为个人推荐电影，ratings.dat文件内容如图所示

ratings.dat

其中分别为用户id，电影id，评分(1-5分)，评分时间，总共一百万行多点的数据。我设置评分3分以上算是喜欢，最小支持度为0.2，最小置信度为0.5,下面是代码实现

# -*- coding: utf-8 -*-

"""

Apriori exercise.

Created on Sun Oct 26 11:09:03 2017

@author: FWW

"""

import time

def createC1( dataSet ):

'''

构建初始候选项集的列表，即所有候选项集只包含一个元素，

C1是大小为1的所有候选项集的集合

'''

C1 = []

for transaction in dataSet:

for item in transaction:

if [ item ] not in C1:

C1.append( [ item ] )

C1.sort()

return list(map( frozenset, C1 ))

def scanD( D, Ck, minSupport ):

'''

计算Ck中的项集在事务集合D的每个transactions中的支持度,

返回满足最小支持度的项集的集合，和所有项集支持度信息的字典。

'''

ssCnt = {}

for tid in D:

# 对于每一条transaction

for can in Ck:

# 对于每一个候选项集can，检查是否是transaction的一部分

# 即该候选can是否得到transaction的支持

if can.issubset( tid ):

ssCnt[ can ] = ssCnt.get( can, 0) + 1

numItems = float( len( D ) )

retList = []

supportData = {}

for key in ssCnt:

# 每个项集的支持度

support = ssCnt[ key ] / numItems

# 将满足最小支持度的项集，加入retList

if support >= minSupport:

retList.insert( 0, key )

# 汇总支持度数据

supportData[ key ] = support

return retList, supportData

# Aprior算法

def aprioriGen( Lk, k ):

'''

由初始候选项集的集合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

C1 = createC1( dataSet )

# 将dataSet集合化，以满足scanD的格式要求

D = list(map( set, dataSet ))

# 构建初始的频繁项集，即所有项集只有一个元素

L1, suppData = scanD( D, C1, minSupport )

L = [ L1 ]

# 最初的L1中的每个项集含有一个元素，新生成的

# 项集应该含有2个元素，所以 k=2

k = 2

while ( len( L[ k - 2 ] ) > 0 ):

Ck = aprioriGen( L[ k - 2 ], k )

Lk, supK = scanD( D, Ck, minSupport )

# 将新的项集的支持度数据加入原来的总支持度字典中

suppData.update( supK )

# 将符合最小支持度要求的项集加入L

L.append( Lk )

# 新生成的项集中的元素个数应不断增加

k += 1

# 返回所有满足条件的频繁项集的列表，和所有候选项集的支持度信息

return L, suppData

def calcConf( freqSet, H, supportData, brl, minConf=0.5 ):

'''

计算规则的可信度，返回满足最小可信度的规则。

freqSet(frozenset):频繁项集

H(frozenset):频繁项集中所有的元素

supportData(dic):频繁项集中所有元素的支持度

brl(tuple):满足可信度条件的关联规则

minConf(float):最小可信度

'''

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, brl, minConf=0.5 ):

'''

对频繁项集中元素超过2的项集进行合并。

freqSet(frozenset):频繁项集

H(frozenset):频繁项集中的所有元素，即可以出现在规则右部的元素

supportData(dict):所有项集的支持度信息

brl(tuple):生成的规则

'''

m = len( H[ 0 ] )

if m == 1:

calcConf( freqSet, H , supportData, brl, minConf )

# 查看频繁项集是否大到移除大小为 m　的子集

if len( freqSet ) > m + 1:

Hmp1 = aprioriGen( H, m + 1 )

Hmp1 = calcConf( freqSet, Hmp1, supportData, brl, minConf )

# 如果不止一条规则满足要求，进一步递归合并

if len( Hmp1 ) > 1:

rulesFromConseq( freqSet, Hmp1, supportData, brl, minConf )

def recommendMovies(rules,personal_list,movie_list):

recommend_list = []

sup_list = []

for rule in rules:

if rule[0] <= personal_list:

for movie in rule[1]:

if movie_list[movie-1] not in recommend_list:

recommend_list.append(movie_list[movie-1])

sup_list.append(rule[2])

for recommend in recommend_list:

i = recommend_list.index(recommend)

print('Recommend you to watch',recommend,',',round(sup_list[i]*100,2),'% people who is similar to you like it!')

def generateRules( L, supportData, minConf=0.5 ):

'''

根据频繁项集和最小可信度生成规则。

L(list):存储频繁项集

supportData(dict):存储着所有项集(不仅仅是频繁项集)的支持度

minConf(float):最小可信度

'''

bigRuleList = []

for i in range( 1, len( L ) ):

for freqSet in L[ i ]:

# 对于每一个频繁项集的集合freqSet

H1 = [ frozenset( [ item ] ) for item in freqSet ]

# 如果频繁项集中的元素个数大于2，需要进一步合并

if i > 1:

rulesFromConseq( freqSet, H1, supportData, bigRuleList, minConf )

else:

calcConf( freqSet, H1, supportData, bigRuleList, minConf )

return bigRuleList

if __name__ == '__main__':

# 导入数据集

start_time = time.time()

file_object = open('ratings.dat')

movies_object = open('movies.dat')

personal_object = open('personalRatings.txt')

file_list = []

try:

all_the_text = file_object.read()

origin_list = (line.split('::') for line in all_the_text.split('\n'))

tem_list = []

for line in origin_list:

if len(file_list)

file_list.append(tem_list)

tem_list = []

else:

if int(line[2])>3:

tem_list.append(int(line[1]))

movies_text = movies_object.read()

movies_list = []

for item in (line.split('::') for line in movies_text.split('\n')):

if item[1] not in movies_list:

movies_list.append(item[1])

personal_text = personal_object.read()

personal_list = []

for item in (line.split('::') for line in personal_text.split('\n')):

if int(item[2])>3:

personal_list.append(int(item[1]))

finally:

file_object.close()

movies_object.close()

personal_object.close()

print('Read file sucess in',time.time()-start_time,'s')

# 选择频繁项集

L, suppData = apriori( file_list, 0.2 )

rules = generateRules( L, suppData, minConf=0.5 )

#print ('rules:\n', rules)

print ('Caculate rules success in',time.time()-start_time,'s')

recommendMovies(rules,frozenset(personal_list),movies_list)

print ('The program completes in',time.time()-start_time,'s')

运行结果

2017-11-05 14-53-20屏幕截图.png

读文件用了1.3秒，运行花了14秒，相信之后用numpy数组改进一下运行速度会更快