企业官网建设流程全解析

大家现在可以来读一下这篇内容, 这里的算法是用来挖掘关联规则的频繁项集的。这个算法的核心意思呢, 是通过候选集生成以及情节的向下检测这两个步骤来完成任务。另外, 它已经在商业领域、网络安全领域等众多方面得到了比较广泛的使用。

因为大数据这个概念现在很热, 所以啤酒跟尿布的那个故事大家都知道得挺多了。大家都会去想, 到底是怎么发现那个买啤酒的人一般也会顺手买尿布的情况的呢。在数据挖掘这一行里, 有专门用来找频繁项集还有关联规则的算法, 这些算法可以给出来答案。

这篇文章先是简单说一下这些算法是怎么回事, 然后接着把那些基本的小概念讲一讲, 再往后就很详细地介绍各个算法是怎么做的具体策略和具体的步骤都是什么样子, 文章的最最后部分给出了实现的代码。

1.算法简介

这个算法是一个经典的用于挖掘频繁项集和关联规则的数据挖掘算法。字母 A 在拉丁语里面指的是来自于过去的含义。当人们去定义一个具体的问题时候, 通常都会使用一些已经存在的知识或者是一些特定的假设情况, 这种做法被叫做做一个先验的概念, 也就是说对应的是 a 这个位置上的词语。

这个算法之所以会用到这样的命名方式, 其根本的原因在于它所使用的机制是依赖于频繁项集本身所具备的那些先验性质的, 而具体提到的一个性质就是, 如果一个集合被称为是频繁的, 那么从该集合里面取出来的所有不等于空的子集也都应该被判定为是频繁的情况。该算法采用一种叫做逐层搜索的迭代式方法。

在这个方法里, 它会使用k项集去探索(k+1)项集。一开始, 系统会扫描整个数据库。它会累计每一个项的出现次数。接着, 它会筛选出那些满足最小支持度的项并收集起来。这样就能找出频繁1项集的集合了。这个集合被记为L1。然后, 它就利用L1去找频繁2项集。

找到的这个集合就是L2。之后, 它再用L2去找L3。这个过程就一直重复下去。直到再也找不到新的频繁k项集为止, 程序就停止运行。当每一个Lk一旦被找出来的时候, 那就必定需要针对数据库进行完整扫描这样的做法, 这个算法通过使用频繁项集所具备的先验性质来对搜索空间实行压缩。

2. 基本概念

我们设那个由item1加上省略号再加上一堆别的项所组成的大括号为所有项的集, 这里面每一个叫作项的东西都得符合k等于一二直到m这样的条件, 然后把所有这些项放在一块儿就组成了一个被称为项集的玩意儿, 这里面要是包含了k个项的话, 那我们就可以称它为k项集, 括号里再标注一句k减一的写法。

事务是指项集, 它是某一个更大集合的子集, 每个事务都和一个被称为Tid的唯一标识符相关联。由多个不同的事务组合在一起便构形成称为D的事务集。这种结构构成了用于进行关联规则挖掘的事务型数据库的基础内容。

关联规则指的是那种形如A推出B这样的蕴涵式, 这里面A和B都是集合里面的子集, 而且这两个子集都不能是空集合, 同时A这个子集和B这个子集之间没有共同的部分。

支持度（）, 关联规则的支持度的定义是这样的, 它是下面这样被表述出来的:

那个P(A并B)呢, 是现在的人用来表示这个事务它是包含了集合A和集合B的那个并集的一个概率, 意思也就是它包含了在A里面所有的每一个项以及包括了在B里面所有的每一个项这样的几率, 这个地方你要特别注意一下, 得跟那个后面说的P(A or B)给它区别开, 因为后者这个是专门表示说这个事务只要是包含了A或者是包含了B当中的任意一个情况的一个概率而已。

关联规则的置信度, 它的定义是这样的。

所谓项集的出现频度, 也就是大家通常所说的计数, 在专业领域里它又被简称为项集的频度或者支持度计数, 那么它具体是指什么呢? 它指的就是那些包含了该特定项集的事务的数量的总和。

所谓的频繁项集就是, 如果一个项集I的相对支持度满足了人们事先定义好的那个最小支持度的阈值。这个意思也就是说, 项集I它出现的那个频度是大于相应的最小出现频度也就是支持度计数的那个阈值的。那么这样的话, 我们就可以确认项集I属于频繁项集。

所谓的强关联规则就是指那些, 它必须要满足最小的支持度,并且它也必须满足最小置信度的那个关联规则, 意思就是这些关联规则也就是大家想要去挖掘的那些内容。

3. 实现的具体步骤, 也就是操作过程。

从通常的情况上来讲, 大家在进行关联规则的挖掘工作的时候, 这整个流程大体上可以被拆分成上下两个具体的步骤来逐一完成。

找出所有的频繁项集

从那些频繁出现的项目组合里面, 去产生出强度高的关联规则。

3.去把那些频繁出现的项集给挖掘出来。

3.这里先给出那些相关定义的说明。

先进行连接步骤, 也就是把频繁项集Lk-1和自己连接起来, 这样操作以后, 就可以产生候选k项集Ck。

算法里面有一个假设, 就是项集里面的那些项, 是按照字典顺序排好队的。如果在这个集合$Lk-1$里头的某两个元素, 也就是两个项集, 它们的前面的$k-2$个项都是一样的话, 那么我们就说这两个项集是可以进行连接的。

所以, 由连接这个动作产生的那个结果项集, 就包括了一些东西, 具体的内容就是这里写的那些项目符号加省略号再配上项目符号这样的形式。连接这样一个步骤, 是被包含在下面提到的那个代码里面的函数之中的。

剪枝策略

先验性质是存在的, 这个性质是任何东西都逃避不了的事实, 那就是任何一个不频繁的k减1项集, 它绝对不是频繁k项集的子集。因此, 如果一个候选的k项集, 也就是符号写为Ck的这个东西, 它的k减1项子集没有出现在Lk减1里面的话, 那么说这个候选的东西, 也就绝对不可能是什么频繁的东西。

所以, 它就可以从这个Ck集合里面被删除掉。这么一来, 我们就能够获得一个已经被压缩了的Ck了。在下面的代码当中提到的那个函数, 它是用来判断是不是满足先验性质的。这个函数的内部, 是包含剪枝这么个步骤的。什么意思? 就是说一旦发现不满足那个先验性质的话, 就把那些不要的东西给剪掉了。

删除策略

我们使用已经压缩好的Ck去扫描所有的交易数据, 具体来说, 就是对Ck里面的每一个项目各自统计出现频次, 然后把那些达不到最低支持度要求的项目给剔除掉, 这样最终就能得到频繁k项集了, 关于那个具体的删除做法, 是包含在接下来代码里所写的那个函数之中的。

3.1.2 步骤

每一个候选的1项集, 它都是属于集合C1里面的一个成员。算法把数据库里所有的那种事务给好好地扫一遍, 从而得到每一个单独的数据项, 并且用一种方式去生成C1这个集合, 具体的办法可以去看一下下面那个写在代码里面的函数。

紧接着, 要对之前得到的每一个单独数据项进行计数。最后, 再根据那个最小的支持度数值作为标准, 把这个C1集合里面所有不符合要求的数据项全部删掉, 就这么个操作过程下来, 就能获得最终的频繁1项集L1。

对于由L1跟自身的连接所生成的那些集合来说, 要实施剪枝策略, 这样做的目的是为了得到一个叫做C2的候选2项集的集合。接着, 需要去扫描所有的交易数据事务。

针对在C2这个集合里面的每一个项, 都要进行计数操作。同样的道理也要适用, 那就是要从C2里面把那些不满足最小支持度要求的项全部删除掉, 通过这种操作方式来最终获得那些频繁出现的2项集, 也就是L2。

对L2通过自连接运算所形成的集合施加剪枝策略, 以此构建出由候选3项集组成的集合C3。紧接着, 针对全部事务展开遍历操作, 并分别对属于C3的各个项目执行频数统计工作。与之类似的做法是, 参考预设的最低支持度阈值, 从C3中剔除那些没有达标的项, 继而筛选生成频繁3项集这一最终结果L3。

按照这种方法继续往下进行, 针对Lk-1通过自身关联所生成的那个集合实施修剪处理办法, 借此制造出候选的k项集合Ck。随后, 去遍历所有的交易数据记录, 并且对处于Ck内部的每一个项目元素分别执行统计次数操作。

接下来, 依据预先设定的最低支持度阈值标准, 从Ck中剔除那些没能达到要求的物品组合, 经过这一番筛选操作之后, 最终便能得到所谓的频繁k项集。

3.就是2, 这个内容讲的是从那个频繁出现的项集集合里面去产生出相关的关联规则。

当频繁项集被找出来后, 就可以直接从这些频繁项集中去产出强关联规则。那么, 产出的具体步骤是什么呢, 具体的情况如下。

对于每一个频繁项集来说, 它所产生的所有不是空的那个子集, 都是频繁项集。

针对每一个非空集合s而言, 倘若。

那么就输出s除以l减去s这样一个表达式, 其中这个数值是被定义为最小置信度阈值的。

4. 这里提供相关的示例, 并给出相应的代码实现。

下图所展示的情况, 是对提取频繁项集的一个样例进行的图解。

这篇文章是用咱们手里这个样例的数据来写代码, 好把那个算法给实现出来。写代码的时候要留心下面这两点问题:

大家知道, 算法会默认项集中的各个项目是按照字典里面的那个顺序排好队的, 可是集合这个东西它本身是没有固定顺序的, 所以呢, 我们在碰到需要换的时候, 就得把那种set这种形式的东西转成list, 或者反过来, 做一下相互之间的转换才行。

因为在使用字典来记录项集的支持度值的时候, 程序里面是需要用到那个项集作为键来查找的。不过要注意到一个情况, 就是可变集合是不好直接放到字典里去当那个键用的, 所以为了能把这个事儿给办成呢, 我们得挑个合适的时机, 顺手把那个会变来变去的集合给它转换成个固定不变的集合同样可以叫它固定集合。

"""

# Python 2.7

# Filename: apriori.py

# Author: llhthinker

# Email: hangliu56[AT]gmail[DOT]com

# Blog: http://www.cnblogs.com/llhthinker/p/6719779.html

# Date: 2017-04-16

"""

def load_data_set():

"""

Load a sample data set (From Data Mining: Concepts and Techniques, 3th Edition)

Returns:

A data set: A list of transactions. Each transaction contains several items.

"""

data_set = [['l1', 'l2', 'l5'], ['l2', 'l4'], ['l2', 'l3'],

['l1', 'l2', 'l4'], ['l1', 'l3'], ['l2', 'l3'],

['l1', 'l3'], ['l1', 'l2', 'l3', 'l5'], ['l1', 'l2', 'l3']]

return data_set

def 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 C1

def 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 True

def 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 Ck

def 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 Lk

def 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_data

def 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_list

if __name__ == "__main__":

"""

Test

"""

data_set = load_data_set()

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

big_rules_list = generate_big_rules(L, support_data, min_conf=0.7)

for Lk in L:

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]

把程序跑起来之后所给出的执行结果的情况, 具体如下图所示。