免规则采集器列表算法(两个关联规则分析()概念())

　　免规则采集器列表算法(两个关联规则分析()概念())

　　相关分析

　　关联分析是在*敏*感*词*数据集中寻找有趣关系的任务。这种关系有两种形式：

　　1.频率项集（frequency item sets）：一些经常同时出现的元素的集合——使用支持度量

　　2.关联规则：表示两个元素之间有很强的关系——使用可信度度量

　　以下示例说明了上述两个概念：

　　表 1 简单交易列表

　　交易编号产品

　　0豆浆、生菜

　　1个生菜，尿布，酒，甜菜

　　2个生菜，尿布，酒，橙汁

　　3个生菜，豆浆，尿布，酒

　　4个生菜，豆浆，尿布，橙汁

　　频繁项集是经常一起出现的元素的集合。上表中的集合 {wine, diapers, soymilk} 是频繁项集的一个例子。还可以找到像“diapers --> wine”这样的关联规则，这意味着如果有人买了尿布，那么他很可能也买了酒。利用频繁项集和关联规则，商家可以更好地了解顾客的消费行为，因此关联规则分析的例子大多来自零售行业。

　　要了解关联分析，我们首先需要了解以下三个问题：

　　1.如何定义这些有用的关系？

　　2.如何定义这些关系的强度？

　　3.频繁的定义是什么？

　　要回答上述问题，最重要的是理解两个概念：支持和可信度。

　　支持度（用于频繁项集量化）：一个项集的支持度定义为数据集中收录该项的记录占总记录的比例。从表1可以看出，项目集{soymilk}的支持度为4/5；5条交易记录中有3条收录{soymilk, diapers}，所以{soymilk, diapers}的支持度为3/5.

　　可信度或置信度（用于关联规则量化）：为{diaper}-->{wine}等关联规则定义，该规则的可信度定义为“support({diapers,wine})/support( {尿布}）”。在表1中可以发现{diapers, wine}的支持度为3/5，{diapers}的支持度为4/5，所以关联规则“diapers --> wine”的置信度是 3/4 = 0.75，这意味着对于所有收录“尿布”的记录，关联规则适用于 75% 的记录。

　　先验原理

　　假设我们经营一家杂货店，所以我们对经常一起购买的商品非常感兴趣。假设我们只有 4 个项目：项目 0、项目 1、项目 2、项目 3. 那么如何获得可以一起购买的项目组合？

　　

　　上图显示了所有可能的项目组合。从上到下的下一个集合是Ø，它表示一个不收录任何项目的空集合。项目集之间的线表示两个或多个集可以组合成一个更大的集。采集。

　　我们的目标是找到经常一起购买的物品的集合。这里使用集合的支持度来衡量它出现的频率。对集合发生的支持是指收录该集合的事务记录的比例。比如上图，计算{0,3}的支持度，直白的思路就是遍历每条记录，统计收录0和3的记录数，再除以总记录数得到支持消费。这仅适用于单个集合 {0,3}。要获得对每个可能集合的支持，需要多次重复上述过程。对于上图，虽然只有4个item，但是需要遍历数据15次。随着项目数量的增加，遍历次数急剧增加。对于收录 N 个项目的数据集，有

　　

　　项集的组合。所以即使是一家只卖 100 件商品的商店也会有

　　

　　可能的组合。计算量太大。

　　为了减少计算时间，研究人员发现了 Apriori 原理，它可以帮助我们减少感兴趣的频繁项集的数量。

　　Apriori 原理：如果一个项集是一个频繁项集，那么它的所有子集也是频繁的。也就是说，如果 {0,1} 是频繁的，那么 {0}, {1} 也必须是频繁的。

　　这个原理直观上是没用的，但反过来也有用，也就是说，如果一个项集是不频繁的，那么它的所有超集也是不频繁的。如下所示：

　　

　　先验算法

　　优点：易于编码和实现

　　缺点：在大型数据集上可能会更慢

　　适用数据类型：数值或名义数据

　　Apriori算法的一般流程

　　采集数据：使用任何方法 准备数据：任何数据类型都可以，因为我们只保存集 分析数据：使用任何方法 训练算法：使用 Apriori 算法查找频繁项集 测试算法：无测试过程 使用算法：用于发现频繁项集和项之间的关联规则使用 Apriori 算法发现频繁项集

　　如上所述，关联分析有两个目标：发现频繁项集和发现关联规则。首先，我们需要找到频繁项集，然后根据频繁项集得到关联规则。

　　Apriori 是一种发现频繁项集的方法。

　　该算法首先为所有单个项目生成项目集列表；

　　然后扫描事务记录，看看哪些项集满足最低支持要求，那些不满足最低支持的集合将被剔除；

　　然后，将剩余的集合组合起来，生成一个收录两个元素的项集；

　　接下来，重新扫描事务记录以删除不满足最小支持的项集，并重复直到所有项集都被删除。

　　数据集扫描的伪代码：

　　对于数据集 tran 中的每条交易记录：

　　对于每个候选项目集可以：

　　检查 can 是否是 tran 的子集：

　　如果是，增加can的计数值

　　对于每个候选项目集：

　　如果它的支持度不低于最小值，保持它

　　返回所有频繁项集的列表

　　代码显示如下：

　　def loadDataSet():

'''创建一个用于测试的简单的数据集'''

return [ [ 1, 3, 4 ], [ 2, 3, 5 ], [ 1, 2, 3, 5 ], [ 2, 5 ] ]

def createC1( dataSet ):

'''

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

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

'''

C1 = []

for transaction in dataSet:

for item in transaction:

if [ item ] not in C1:

C1.append( [ item ] )

C1.sort()

#原书python2环境代码,return map( frozenset, C1 )

return list(map( frozenset, C1 ))

#数据集ck,包含候选集合的列表D,感兴趣项集的最小支持度minSupport

def scanD( D, Ck, minSupport ):

'''

计算Ck中的项集在数据集合D(记录或者transactions)中的支持度,

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

'''

ssCnt = {}

for tid in D:

print('tid=',tid)

# 对于每一条transaction

for can in Ck:

print('can=',can)

# 对于每一个候选项集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

dataSet=loadDataSet()

print(dataSet)

C1=createC1(dataSet)

print(C1)

D=list(map(set,dataSet))

print('D=',D)

L1,suppData0=scanD(D,C1,0.5)

print('L1=',L1)

print('supData0=',suppData0)

　　运行结果：

　　D:\>python apriori.py

[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]

D= [{1, 3, 4}, {2, 3, 5}, {1, 2, 3, 5}, {2, 5}]

tid= {1, 3, 4}

can= frozenset({1})

can= frozenset({2})

can= frozenset({3})

can= frozenset({4})

can= frozenset({5})

tid= {2, 3, 5}

can= frozenset({1})

can= frozenset({2})

can= frozenset({3})

can= frozenset({4})

can= frozenset({5})

tid= {1, 2, 3, 5}

can= frozenset({1})

can= frozenset({2})

can= frozenset({3})

can= frozenset({4})

can= frozenset({5})

tid= {2, 5}

can= frozenset({1})

can= frozenset({2})

can= frozenset({3})

can= frozenset({4})

can= frozenset({5})

L1= [frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})]

supData0= {frozenset({4}): 0.25, frozenset({5}): 0.75, frozenset({2}): 0.75, fro

zenset({3}): 0.75, frozenset({1}): 0.5}

　　分析如下：

　　组织完整的 Apriori 算法

　　假代码：

　　当集合中的元素个数大于 0 时：

　　构建收录 k 个项目的候选集列表

　　检查数据，确认每个项集都是频繁项集

　　保留频繁项集，构建由k+1项组成的候选项集列表

　　代码显示如下：

　　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 )

print('k=',k,'\n Ck=',Ck,'\n L[k-2]',L[k-2])

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

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

suppData.update( supK )

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

L.append( Lk )

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

k += 1

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

return L, suppData

dataSet=loadDataSet()

L1,suppData0=apriori(dataSet,0.5)

##print(dataSet)

##C1=createC1(dataSet)

##print(C1)

##D=list(map(set,dataSet))

##print('D=',D)

##L1,suppData0=scanD(D,C1,0.5)

print('L1=',L1)

print('supData0=',suppData0)

　　结果：

　　D:\>python apriori.py

k= 2

Ck= [frozenset({1, 3}), frozenset({1, 2}), frozenset({1, 5}), frozenset({2, 3})

, frozenset({3, 5}), frozenset({2, 5})]

L[k-2] [frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})]

k= 3

Ck= [frozenset({2, 3, 5})]

L[k-2] [frozenset({3, 5}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2,

3})]

k= 4

Ck= []

L[k-2] [frozenset({2, 3, 5})]

L1= [[frozenset({1}), frozenset({3}), frozenset({2}), frozenset({5})], [frozense

t({3, 5}), frozenset({1, 3}), frozenset({2, 5}), frozenset({2, 3})], [frozenset(

{2, 3, 5})], []]

supData0= {frozenset({5}): 0.75, frozenset({3}): 0.75, frozenset({2, 3, 5}): 0.5

, frozenset({1, 2}): 0.25, frozenset({1, 5}): 0.25, frozenset({3, 5}): 0.5, froz

enset({4}): 0.25, frozenset({2, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({1}

): 0.5, frozenset({1, 3}): 0.5, frozenset({2}): 0.75}

　　分析：

　　step1.Initial=2，调用aprioriGen生成候选项集Ck

　　step2.调用scanD根据Ck创建Lk，丢弃不满足最小支持度要求的项集。

　　stpe3.Lk列表加入L，同时k递增，重复上述过程

　　step4.Lk为空，函数返回L--频繁列表和字典supportData-itemset的支持度并退出。

　　在运行结果中，

　　k=2时，aprioriGen生成2个元素的6个候选项集列表

　　Ck= [frozenset({1, 3}),frozenset({1, 2}),frozenset({1, 5}),frozenset({2, 3})

　　,frozenset({3, 5}),frozenset({2, 5})]

　　然后通过scanD过滤掉2个不满足最小支持度的集合，所以将下面4个元素加入到频繁项集列表中

　　[frozenset({3, 5})，frozenset({1, 3})，frozenset({2, 5})，frozenset({2,3})]

　　当 k=3 时，生成 1 元素候选集列表 Ck= [frozenset({2, 3, 5})]。注意：由于集合的第一个元素用于比较，因此只有集合 freezeset({2, 5})、frozenset({2,3})] 会被合并。

　　候选项集列表中的元素集支持度为0.5，满足最小支持度，故加入频繁项集列表。

　　K=4，CK=[]

　　程序返回一个频繁项集（9 个元素）的列表，然后退出。

　　L1= [[frozenset({1})，frozenset({3})，frozenset({2})，frozenset({5})]，[frozense

　　t({3, 5})，frozenset({1, 3})，frozenset({2, 5})，frozenset({2, 3})]，[frozenset(

　　{2, 3, 5})], []]