数据挖掘之Apriori算法
第一关：候选生成
任务描述
本关任务：编写一个能实现Apriori算法候选生成的小程序。
相关知识
为完成本任务你需要掌握Apriori算法的基本原理包括1Apriori算法候选生成这一核心环节以及2Apriori算法候选生成的具体实现步骤
Apriori 算法候选生成
Apriori算法通过self-joining操作来生成候选集：从直观上讲，则是生成所有可能的(k+1)项集合的过程。具体而言，在处理Lk中的两个k项集l₁和l₂时（其中l₁和l₂仅相差一个项目），我们将它们的并集(l₁ ∪ l₂)加入到Ck+1中。
以图为例，在频繁项集L₃的创建过程中（即生成候选4项集C₄），可以看出：L₃中任意两个3-项集（如ABC和ABD）仅相差一个元素，则可将它们的并集（即ABCD）合并后加入到C₄中
Apriori 算法候选生成代码实现
Apriori 算法候选1项集生成函数如下：
def create_c1(self, dataset): # 遍历整个数据集生成c1候选集
c1 = set()
for i in dataset:
for j in i:
item = frozenset([j])
c1.add(item)
return c1
python其中 dataset 为数据集列表。
Apriori 算法候选 k 项集生成函数(无剪枝操作)代码思路如下：
初始化C_k集合；
计算L_{k-1}的长度；
将L_{k-1}转为列表；
双重遍历过程L_{k-1}, 寻找前n−1个元素完全相同的项；
仅最后一个元素存在差异时,生成下一候选选项；
输出结果至C_k集合中；
伪代码示例：
def create_ck(self, Lk_1, size): # 通过频繁项集Lk-1创建ck候选项集
Ck = set()
l = len(Lk_1)
lk_list = list(Lk_1)
for i in range(l):
for j in range(i + 1, l):
# 两次遍历Lk-1，找出前n-1个元素相同的项
# 只有最后一项不同时，生成下一候选项
return Ck
python编程要求
根据提示，在右侧编辑器补充代码，生成候选3项集C3。
代码填写
class Apriori():
def create_c1(self, dataset): # 遍历整个数据集生成c1候选集
c1 = set()
for i in dataset:
for j in i:
item = frozenset([j])
c1.add(item)
return c1
def create_ck(self, Lk_1, size): # 通过频繁项集Lk-1创建ck候选项集
Ck = set()
l = len(Lk_1)
lk_list = list(Lk_1)
for i in range(l):
for j in range(i + 1, l):
##########begin##########
# 两次遍历Lk-1，找出前n-1个元素相同的项
l1 = list(lk_list[i])
l2 = list(lk_list[j])
l1.sort()
l2.sort()
##########end##########
if l1[0:size - 2] == l2[0:size - 2]:
##########begin##########
#只有最后一项不同时，生成下一候选项
Ck_item = lk_list[i] | lk_list[j]
if len(Ck_item) == size:
Ck.add(Ck_item)
##########end##########
return Ck
def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):
item_count = {}
Lk = set()
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]
return Lk
if __name__ == "__main__":
data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
['a','b','c','e'],['a','b','c'],['a','c','e']]
apriori = Apriori()
support_data = {}
c1 = apriori.create_c1(data)
l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
c2 = apriori.create_ck(l1, size=2)
l2 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c2, min_support=0.2, support_data=support_data)
c3 = apriori.create_ck(l2, size=3)
print(len(c3))
python
第二关：候选剪枝
任务描述
本关任务：编写一个能实现候选剪枝的小程序。
相关知识
为了完成本关任务, 你需要熟练掌握: 1. Apriori 算法的候选剪枝, 2. Apriori 算法候选剪枝的具体实施
Apriori 算法候选剪枝
候选集遵循两个定理进行剪枝操作： 定理1指出：如果某个集合是频繁项集，则其所有的子集合均为频繁项集。例如：如果集合{a, b, c}是频繁项集，则其单元素子集合{a}、{b}、{c}；双元素子集合{a, b}、{b, c}以及{a, c}均为该条件下的频繁项集。
定理2： 如果某项集不是一个频繁项集，则其所有的超集同样也不是频繁项集。 举个例子来说：如果{a, b}不是一个频繁项集，那么添加第三个元素c后形成的集合{a, b, c}也不会是一个频繁项集。
依据上述两个定理所述内容，请问您是否需要我们对处理后所得的候选集合实施剪枝处理以缩减其搜索范围？
剪枝操作定义为，在剪枝操作中对某个项集c∈C_{k+1}来说，当且仅当该项集c包含一个大小为k的子集集合s，并且这个s不在L_k集合中出现过时，则该项集c被移除出C_{k+1}集合。
此图为剪枝流程例图, 蓝色标志项集在频繁3项集中. 观察到生成的候选4项集 ABCE 中的子项集 ABE 未包含在其中. 因此剔除 ABCE.
Apriori 算法候选剪枝代码实现
剪枝的关键在于验证候选项集 Ck 的部分集合是否全部包含在频繁项集 Lk−1 中。
其中的主体功能如下：
def has_infrequent_subset(self, Ck_item, Lk_1): # 检查候选项Ck_item的子集是否都在Lk-1中
for item in Ck_item:
sub_Ck = Ck_item - frozenset([item])
#进行条件判断，如果存在候选项Ck_item子集不在Lk-1中则返回False
return True
python在候选生成中添加剪枝伪代码示例：
def create_ck(self, Lk_1, size): # 通过频繁项集Lk-1创建ck候选项集
Ck = set()
l = len(Lk_1)
lk_list = list(Lk_1)
for i in range(l):
for j in range(i + 1, l):
# 两次遍历Lk-1，找出前n-1个元素相同的项
# 只有最后一项不同时，生成下一候选项
# 检查该候选项的子集是否都在Lk-1中
Ck.add(Ck_item)
return Ck
python
相较于未剪枝的候选生成过程而言，在本算法中增加了一个对候选选项子集是否全部包含在Lk-1中的条件判断。
编程要求
根据提示，在右侧编辑器补充代码，对生成的候选集剪枝。
代码填写
class Apriori():
def create_c1(self, dataset): # 遍历整个数据集生成c1候选集
c1 = set()
for i in dataset:
for j in i:
item = frozenset([j])
c1.add(item)
return c1
def has_infrequent_subset(self, Ck_item, Lk_1):
##########begin##########
# 检查候选项Ck_item的子集是否都在Lk-1中函数定义
for item in Ck_item: #对于Ck_item集合中的每一个元素进行迭代
subset = Ck_item - set([item])#通过创建新的集合subset，移除当前迭代的item，来生成Ck_item的子集
if subset not in Lk_1: #检查新生成的子集subset是否在频繁项集Lk_1中
return False
##########end##########
return True
def create_ck(self, Lk_1, size): # 通过频繁项集Lk-1创建ck候选项集
Ck = set()
l = len(Lk_1)
lk_list = list(Lk_1)
for i in range(l):
for j in range(i + 1, l):
##########begin##########
# 两次遍历Lk-1，找出前n-1个元素相同的项
l1 = list(lk_list[i])
l2 = list(lk_list[j]) #将当前两个频繁项集转换成列表形式
l1.sort()
l2.sort() #对列表进行排序
##########end##########
if l1[0:size - 2] == l2[0:size - 2]:
##########begin##########
#只有最后一项不同时，生成下一候选项
#检查该候选项的子集是否都在Lk-1中
Ck_item = lk_list[i] | lk_list[j]#降负荷条件的两个频繁项集合并成一个新的候选集Ck_item
if len(Ck_item) == size and self.has_infrequent_subset(Ck_item,Lk_1): #检查长度是否为size
Ck.add(Ck_item)
##########end##########
return Ck
def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):
item_count = {}
Lk = set()
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]
return Lk
if __name__ == "__main__":
data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
['a','b','c','e'],['a','b','c'],['a','c','e']]
apriori = Apriori()
support_data = {}
c1 = apriori.create_c1(data)
l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
c2 = apriori.create_ck(l1,size=2)
l2 = apriori.generate_lk_by_ck_ergodic(data_set=data,ck=c2,min_support=0.2,support_data=support_data)
c3 = apriori.create_ck(l2, size=3)
print(len(c3))
python
第三关：基于遍历的支持度计算
任务描述
本关任务：编写一个能实现基于遍历的支持度计算的小程序。
相关知识
为完成本关任务目标，请您熟练掌握以下两种方法：第一种方法是通过遍历过程进行的权重值计算；第二种方法是针对该问题设计的具体编码方案。
基于遍历的支持度计算
在候选生成及剪枝的基础上，我们通过频繁 k 项集 L_k 获得了候选 k+1 项集 $C_{k+1}$。随后，在计算 $C_{k+1}$ 中每个项集的支持度后，并筛选出支持度较高的作为频繁项集 `L_{k+1}$。
一种常见的做法是遍历所给定的数据集，并检查候选项集合中的每一个元素是否存在于该数据集中对应的事物中。随后，在计算出各候选项的支持度后，人为设定一个最低的支持度阈值；当候选项中某一项的支持度高于或等于这一最低阈值时，则将其加入到最终的频繁项集合中
基于遍历的支持度计算代码实现
基于遍历的支持度计算函数如下：
def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data): # 通过候选项ck生成lk，基于遍历的支持度计算并将各频繁项的支持度保存到support_data字典中
item_count = {} # 用于标记各候选项在数据集出现的次数
Lk = set()
for t in tqdm(data_set): # 遍历数据集
for item in ck:
#检查候选集ck中的每一项是否出现在事务t中
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]
return Lk
python
其中 data_set 是指所研究的数据集合，在候选 k 项集中选取 min_support 最小支持度以上的项目组合，并以 support_data 字典形式记录各候选项的支持度值。通过 for 循环结构依次处理每个事务 t，在验证候选 k 项集中各项目是否存在于事务 t 内后，请同学们自行完成后续操作步骤
编程要求
根据提示，在右侧编辑器补充代码，使用遍历计算支持度。
代码填写
# 缺失部分的填写
def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data): # 通过候选项ck生成lk，基于遍历的支持度计算并将各频繁项的支持度保存到support_data字典中
item_count = {} # 用于标记各候选项在数据集出现的次数
Lk = set()
# 基于遍历的支持度计算
for t in data_set: # 遍历数据集
for item in ck: #遍历item
##########begin##########
# 检查候选集ck中的每一项是否出现在事务t中
if item.issubset(t):
if item not in item_count:
item_count[item] = 1
else:
item_count[item] += 1
##########end##########
t_num = float(len(data_set))
for item in item_count:
##########begin##########
# 将满足支持度的候选项添加到频繁项集中
if item_count[item] / t_num >= min_support:
Lk.add(item)
support_data[item] = item_count[item]
##########end##########
return Lk
python
第四关：基于hash的支持度计算
任务描述
本关任务：编写一个能实现基于 hash 的支持度计算的小程序。
相关知识
为完成此任务,需掌握:1.hash 基础的支持度计算,2.hash 基础的支持度计算编码过程
基于hash的支持度计算
基于遍历的支持度计算效率较低，在此背景下建议采用hash结构进行优化处理；通过将所有候选项集以hash结构组织起来，并对每条事务只需匹配对应桶内的候选项集即可显著减少处理时间
假设有15个候选3-项集: {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, {2 3 4}, {5 6 7}, {3 4 5}, {3 5 6}, {3 5 7}, {6 8 9}, {3 6 7}, {3 6 8}
可以构建如下的哈希树：在该结构中每个内部节点均采用哈希函数h(p)=p mod3来决定向哪个子路径延伸。举例来说，在哈希表中项1、4和7将被分配到同一个子路径（即最左侧路径），这是因为它们除以3后的余数相同。所有候选三元素集合都被存储在哈希树的叶子节点上。如图所示，在该哈希树结构中共有15个候选三元素集合均匀地分布在9个叶子节点上。
构建过程如下：
给定一个事务 t , 跟哪些候选 3 项集匹配？例如下图中的例子：
匹配过程如下：
考虑一个集合t={1,2,3,5,6} 。为了更新候选项集的支持度计数，在该哈希树中所有包含属于事务t的候选3-项集的叶子节点都至少被访问一次
请特别注意候补三元组必须以一、二或三开头，在Hash树根节点中它们会被分配到不同的子节点位置。具体来说，请看下文：它们会被分配到各自的子节点位置。根据图示中的第二层结构列出的第二部分信息进一步说明了这一过程。
例如，在根节点处存储了散列项1之后（其子项2、3和5被存储在中间子节点中），而项3则存储在右子节点中（如上图所示）。这一过程将不断重复直至抵达Hash树的所有叶子节点（叶子节点）。所有被访问过的叶子节点对应的候选项目集合将与事务进行对比分析（如果候选项目集合是该事务的一个子集，则增加其计数值）。由此可见，在上述例子中总共进行了9次候选项目集合与事务的对比分析（其中5次是成功的），并且对9个候选项目集进行了与事务的比较操作。
基于hash的支持度计算代码实现
基于 hash 的支持度计算关键在于 hash 树的构建。 首先构建节点类：
#Hash节点类定义
class Hash_node:
def __init__(self):
self.children = {} #指向子节点的指针
self.Leaf_status = True #了解当前节点是否为叶子节点的状态
self.bucket = {} #在储存桶中包含项目集
python然后构建hash树类：
#构造得到Hash树类
class HashTree:
# class constructor
def __init__(self, max_leaf_count, max_child_count):
self.root = Hash_node()
self.max_leaf_count = max_leaf_count
self.max_child_count = max_child_count
self.frequent_itemsets = []
# 进行递归插入以生成hashtree
def recursively_insert(self, node, itemset, index, count):
if index == len(itemset):
if itemset in node.bucket:
node.bucket[itemset] += count
else:
node.bucket[itemset] = count
return
if node.Leaf_status: #如果node是叶结点
if itemset in node.bucket:
node.bucket[itemset] += count
else:
node.bucket[itemset] = count
if len(node.bucket) == self.max_leaf_count: #如果储存桶容量增加
for old_itemset, old_count in node.bucket.items():
hash_key = self.hash_function(old_itemset[index]) #对下一个索引做哈希
if hash_key not in node.children:
node.children[hash_key] = Hash_node()
self.recursively_insert(node.children[hash_key], old_itemset, index + 1, old_count)
del node.bucket
node.Leaf_status = False
else:
#如果node不是是叶结点
#需要进行递归式的嵌入
def insert(self, itemset):
itemset = tuple(itemset)
self.recursively_insert(self.root, itemset, 0, 0)
# 添加支持度到候选项集中. 遍历树并找到该项集所在的储存桶.
def add_support(self, itemset):
Transverse_HNode = self.root
itemset = tuple(itemset)
index = 0
while True:
if Transverse_HNode.Leaf_status:
if itemset in Transverse_HNode.bucket: #在此储存桶中找到项集
Transverse_HNode.bucket[itemset] += 1 #增加此项目集的计数
break
hash_key = self.hash_function(itemset[index])
if hash_key in Transverse_HNode.children:
Transverse_HNode = Transverse_HNode.children[hash_key]
else:
break
index += 1
def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
if node.Leaf_status:
for key, value in node.bucket.items():
if value >= support_count: #如果满足支持数条件
frequent_itemsets.append(list(key)) #将其添加到频繁项集中
Frequent_items_value[key] = value
return
for child in node.children.values():
self.get_frequent_itemsets(child, support_count,frequent_itemsets)
# 用于构造hash树的hash函数定义
def hash_function(self, val):
return int(val) % self.max_child_count
python
其中如果node不是叶结点，需要进行递归式的嵌入，请同学自行完成。 提示：
- 执行hash函数以求取其值。
- 检查该hash值是否存在于子节点集合中。
- 若不在，则生成新的节点。
- 调用递归插入算法将其纳入结构。
编程要求
按照提示，在右侧编辑器中添加代码块，并正确构建hash树类对象以实现支持度计算功能
代码填写
#缺失部分的填写
#构造得到Hash树类
class HashTree:
# class constructor
def __init__(self, max_leaf_count, max_child_count):
self.root = Hash_node()
self.max_leaf_count = max_leaf_count
self.max_child_count = max_child_count
self.frequent_itemsets = []
# 进行递归插入以生成hashtree
def recursively_insert(self, node, itemset, index, count):
if index == len(itemset):
if itemset in node.bucket:
node.bucket[itemset] += count
else:
node.bucket[itemset] = count
return
if node.Leaf_status:
##########begin##########
#如果node是叶结点所进行的操作代码
if itemset in node.bucket:
node.bucket[itemset]+=count
else:
node.bucket[itemset]=count
if len(node.bucket)==self.max_leaf_count:
#检查当前存储桶的项集数量是否达到最大容量
for old_itemset, old_count in node.bucket.items():
hash_key = self.hash_function(old_itemset[index])
#对下一个索引做哈希
if hash_key not in node.children:
node.children[hash_key] = Hash_node()
self.recursively_insert(node.children[hash_key], old_itemset, index + 1, old_count)
del node.bucket
node.Leaf_status = False
##########end##########
else:
##########begin##########
#如果node不是是叶结点所进行的操作代码
hash_key = self.hash_function(itemset[index])
if hash_key not in node.children:
node.children[hash_key] = Hash_node()
self.recursively_insert(node.children[hash_key],itemset,index + 1,count)
##########end##########
# 基于hash的支持度计算
def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
##########begin##########
#获取频繁项集函数定义
if node.Leaf_status:
for key, value in node.bucket.items():
if value >= support_count:
#如果满足支持数条件
frequent_itemsets.append(list(key))
#将其添加到频繁项集中
Frequent_items_value[key] = value
return
for child in node.children.values():
self.get_frequent_itemsets(child, support_count,frequent_itemsets)
##########end##########
python
完成！