• 数据挖掘与机器学习：Apripori算法

    目录

    第一关：候选生成 

    任务描述：

    相关知识：

    一、Apripori算法候选生成：

    二、Apripori算法候选生成代码实现：

    编程要求：

    测试说明：

    第二关：候选剪枝

    任务描述：

    相关知识：

    Apripori算法候选剪枝：

    Apripori算法候选剪枝代码实现：

    编程要求：

    测试说明：

    第三关：基于遍历的支持度计算

    任务描述：

    相关知识：

    一、基于遍历的支持度计算：

    二、基于遍历的支持度计算代码实现：

    编程要求：

    测试说明：

    第四关：基于hash的支持度计算

    任务描述：

    相关知识：

    一、基于hash的支持度计算：

    二、基于hash的支持度计算代码实现：

    编程要求：

    测试说明：

    第一关：候选生成 

    任务描述：

     本关任务：编写一个能实现Apripori算法候选生成的小程序。

    相关知识：

     为了完成本关任务，你需要掌握：1.Apripori 算法候选生成，2.Apripori 算法候选生成代码实现。

    一、Apripori算法候选生成：

     Apripori算法利用自连接生成候选集：

    自连接：对Lk​中的2个k项集l1​和l2​，若l1​和l2​有且仅有1个项不同，则将l1​∪l2​加入Ck+1​。

    直观理解：生成可能的(k+1)项集：

     上图为频繁3项集L3​生成候选4项集C4​过程示例，可以看到L3​中的2个3项集ABC和ABD有且仅有1个项不同，则将 ABC∪ABD=ABCD 加入C4​。

    二、Apripori算法候选生成代码实现：

     Apripori 算法候选1项集生成函数如下：

    1. def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    2.     c1 = set()
    3.     for i in dataset:
    4.         for j in i:
    5.             item = frozenset([j])
    6.             c1.add(item)
    7.     return c1

    其中 dataset 为数据集列表。

    Apripori 算法候选 k 项集生成函数(无剪枝操作)代码思路如下：

    1. 创建Ck集合。
    2. 获取Lk_1的长度。
    3. 将Lk_1转换为列表。
    4. 两次遍历Lk-1，找出前n-1个元素相同的项。
    5. 只有最后一项不同时，生成下一候选项。
    6. 返回Ck集合。

    伪代码示例：

    1. def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    2.     Ck = set()
    3.      l = len(Lk_1)
    4.      lk_list = list(Lk_1)
    5.     for i in range(l):
    6.         for j in range(i + 1, l):  
    7.             # 两次遍历Lk-1，找出前n-1个元素相同的项
    8.             # 只有最后一项不同时，生成下一候选项
    9.     return Ck

    编程要求：

     根据提示，在右侧编辑器补充代码，生成候选3项集C3​。

    测试说明：

    平台会对你编写的代码进行测试：

    预期输出：4

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.  
    10.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    11.         Ck = set()
    12.         l = len(Lk_1)
    13.         lk_list = list(Lk_1)
    14.         for i in range(l):
    15.             for j in range(i + 1, l):  
    16.                 ##########begin##########
    17.                 # 两次遍历Lk-1，找出前n-1个元素相同的项
    18.  
    19.  
    20.                 ##########end##########
    21.                 if l1[0:size - 2] == l2[0:size - 2]:  
    22.                     ##########begin##########
    23.                     #只有最后一项不同时，生成下一候选项
    24.  
    25.                     
    26.                     ##########end##########
    27.         return Ck
    28.  
    29.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):  
    30.         item_count = {}  
    31.         Lk = set()
    32.        
    33.         for t in data_set:  
    34.             for item in ck:  
    35.                 if item.issubset(t):
    36.                     if item not in item_count:
    37.                         item_count[item] = 1
    38.                     else:
    39.                         item_count[item] += 1
    40.         t_num = float(len(data_set))
    41.         for item in item_count:  
    42.             if item_count[item] / t_num >= min_support:
    43.                 Lk.add(item)
    44.                 support_data[item] = item_count[item]
    45.         return Lk
    46.  
    47.  
    48. if __name__ == "__main__":
    49.  
    50.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    51.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    52.     apriori = Apriori()
    53.     support_data = {}
    54.     c1 = apriori.create_c1(data)
    55.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    56.     c2 = apriori.create_ck(l1, size=2)
    57.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c2, min_support=0.2, support_data=support_data)
    58.     c3 = apriori.create_ck(l2, size=3)
    59.     print(len(c3))

     

    通过代码：
     

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.  
    10.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    11.         Ck = set()
    12.         l = len(Lk_1)
    13.         lk_list = list(Lk_1)
    14.         for i in range(l):
    15.             for j in range(i + 1, l):  
    16.                 ##########begin##########
    17.                 # 两次遍历Lk-1，找出前n-1个元素相同的项
    18.                 l1 = list(lk_list[i])
    19.                 l2 = list(lk_list[j])
    20.                 l1.sort()
    21.                 l2.sort()
    22.                 ##########end##########
    23.                 if l1[0:size - 2] == l2[0:size - 2]:  
    24.                     ##########begin##########
    25.                     #只有最后一项不同时，生成下一候选项
    26.                     Ck_item = lk_list[i] | lk_list[j]
    27.                     Ck.add(Ck_item)
    28.                     ##########end##########
    29.         return Ck
    30.  
    31.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):  
    32.         item_count = {}  
    33.         Lk = set()
    34.        
    35.         for t in data_set:  
    36.             for item in ck:  
    37.                 if item.issubset(t):
    38.                     if item not in item_count:
    39.                         item_count[item] = 1
    40.                     else:
    41.                         item_count[item] += 1
    42.         t_num = float(len(data_set))
    43.         for item in item_count:  
    44.             if item_count[item] / t_num >= min_support:
    45.                 Lk.add(item)
    46.                 support_data[item] = item_count[item]
    47.         return Lk
    48.  
    49.  
    50. if __name__ == "__main__":
    51.  
    52.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    53.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    54.     apriori = Apriori()
    55.     support_data = {}
    56.     c1 = apriori.create_c1(data)
    57.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    58.     c2 = apriori.create_ck(l1, size=2)
    59.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c2, min_support=0.2, support_data=support_data)
    60.     c3 = apriori.create_ck(l2, size=3)
    61.     print(len(c3))

    第二关：候选剪枝

    任务描述：

     本关任务：编写一个能实现候选剪枝的小程序。

    相关知识：

    为了完成本关任务，你需要掌握：1.Apripori 算法候选剪枝，2.Apripori 算法候选剪枝代码实现。 

    Apripori算法候选剪枝：

    候选集的剪枝操作基于两个定理： 定理1：若某项集是频繁项集，则它的所有子集都是频繁项集。 例如：{a, b, c}是频繁项集，则{a}、{b}、{c}、{a, b}、{b, c}、{a, c}也是频繁项集。

    定理2：若某项集不是频繁项集，则它的所有超集都不是频繁项集。 例如：{a, b}不是频繁项集，则{a, b, c}也不是频繁项集。

    基于以上两个定理，我们需要对进行连接操作后的候选集进行剪枝操作，减小搜索空间。

    剪枝：对 Ck+1​ 中的某项集 c ，若 c 的某大小为 k 的子集 s 不存在于Lk​ ，则将 c 从 Ck+1 删除。

     上图为剪枝过程例图，蓝色表示项集在频繁3项集中，可以看到在生成的候选4项集 ABCE 中，其子集ABE 并不在频繁3项集中，所以剪枝删去。

    Apripori算法候选剪枝代码实现：

     剪枝的核心在于检查候选项集 Ck​ 的子集是否都在频繁项集 Lk−1​ 中。 检查函数主体如下：

    1. def has_infrequent_subset(self, Ck_item, Lk_1):  # 检查候选项Ck_item的子集是否都在Lk-1中
    2.     for item in Ck_item:
    3.         sub_Ck = Ck_item - frozenset([item])
    4.         #进行条件判断，如果存在候选项Ck_item子集不在Lk-1中则返回False
    5.     return True

     在候选生成中添加剪枝伪代码示例：

    1. def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    2.     Ck = set()
    3.     l = len(Lk_1)
    4.     lk_list = list(Lk_1)
    5.     for i in range(l):
    6.         for j in range(i + 1, l):  
    7.             # 两次遍历Lk-1，找出前n-1个元素相同的项
    8.             # 只有最后一项不同时，生成下一候选项
    9.             # 检查该候选项的子集是否都在Lk-1中
    10.                 Ck.add(Ck_item)
    11.     return Ck

    比起无剪枝的候选生成，多了一个判断该候选项的子集是否都在Lk-1中的条件判断。 

    编程要求：

    根据提示，在右侧编辑器补充代码，对生成的候选集剪枝。 

    测试说明：

    平台会对你编写的代码进行测试。

    预期输出：2

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.     
    10.     def has_infrequent_subset(self, Ck_item, Lk_1):  
    11.         ##########begin##########
    12.         # 检查候选项Ck_item的子集是否都在Lk-1中函数定义
    13.  
    14.         
    15.         ##########end##########
    16.         return True
    17.  
    18.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    19.         Ck = set()
    20.         l = len(Lk_1)
    21.         lk_list = list(Lk_1)
    22.         for i in range(l):
    23.             for j in range(i + 1, l):  
    24.                 ##########begin##########
    25.                 # 两次遍历Lk-1，找出前n-1个元素相同的项
    26.  
    27.  
    28.                 ##########end##########
    29.                 if l1[0:size - 2] == l2[0:size - 2]:  
    30.                     ##########begin##########
    31.                     #只有最后一项不同时，生成下一候选项
    32.                     #检查该候选项的子集是否都在Lk-1中
    33.  
    34.  
    35.  
    36.                     ##########end##########
    37.         return Ck
    38.  
    39.     
    40.  
    41.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data): 
    42.         item_count = {}  
    43.         Lk = set()
    44.         for t in data_set:  
    45.             for item in ck:  
    46.                 if item.issubset(t):
    47.                     if item not in item_count:
    48.                         item_count[item] = 1
    49.                     else:
    50.                         item_count[item] += 1
    51.         t_num = float(len(data_set))
    52.         for item in item_count:  
    53.             if item_count[item] / t_num >= min_support:
    54.                 Lk.add(item)
    55.                 support_data[item] = item_count[item]
    56.         return Lk
    57.  
    58.  
    59. if __name__ == "__main__":
    60.  
    61.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    62.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    63.     apriori = Apriori()
    64.     support_data = {}
    65.     c1 = apriori.create_c1(data)
    66.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    67.     c2 = apriori.create_ck(l1,size=2)
    68.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data,ck=c2,min_support=0.2,support_data=support_data)
    69.     c3 = apriori.create_ck(l2, size=3)
    70.     print(len(c3))

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.     
    10.     def has_infrequent_subset(self, Ck_item, Lk_1):  
    11.         ##########begin##########
    12.         # 检查候选项Ck_item的子集是否都在Lk-1中函数定义
    13.         for item in Ck_item:
    14.             sub_Ck = Ck_item - frozenset([item])
    15.             if sub_Ck not in Lk_1:
    16.                 return False
    17.         ##########end##########
    18.         return True
    19.  
    20.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    21.         Ck = set()
    22.         l = len(Lk_1)
    23.         lk_list = list(Lk_1)
    24.         for i in range(l):
    25.             for j in range(i + 1, l):  
    26.                 ##########begin##########
    27.                 # 两次遍历Lk-1，找出前n-1个元素相同的项
    28.                 l1 = list(lk_list[i])
    29.                 l2 = list(lk_list[j])
    30.                 l1.sort()
    31.                 l2.sort()
    32.                 ##########end##########
    33.                 if l1[0:size - 2] == l2[0:size - 2]:  
    34.                     ##########begin##########
    35.                     #只有最后一项不同时，生成下一候选项
    36.                     #检查该候选项的子集是否都在Lk-1中
    37.                     Ck_item = lk_list[i] | lk_list[j]
    38.                     if self.has_infrequent_subset(Ck_item, Lk_1):
    39.                         Ck.add(Ck_item)
    40.                     ##########end##########
    41.         return Ck
    42.  
    43.     
    44.  
    45.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data): 
    46.         item_count = {}  
    47.         Lk = set()
    48.         for t in data_set:  
    49.             for item in ck:  
    50.                 if item.issubset(t):
    51.                     if item not in item_count:
    52.                         item_count[item] = 1
    53.                     else:
    54.                         item_count[item] += 1
    55.         t_num = float(len(data_set))
    56.         for item in item_count:  
    57.             if item_count[item] / t_num >= min_support:
    58.                 Lk.add(item)
    59.                 support_data[item] = item_count[item]
    60.         return Lk
    61.  
    62.  
    63. if __name__ == "__main__":
    64.  
    65.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    66.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    67.     apriori = Apriori()
    68.     support_data = {}
    69.     c1 = apriori.create_c1(data)
    70.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    71.     c2 = apriori.create_ck(l1,size=2)
    72.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data,ck=c2,min_support=0.2,support_data=support_data)
    73.     c3 = apriori.create_ck(l2, size=3)
    74.     print(len(c3))

    第三关：基于遍历的支持度计算

    任务描述：

     本关任务：编写一个能实现基于遍历的支持度计算的小程序。

    相关知识：

    为了完成本关任务，你需要掌握：1.基于遍历的支持度计算，2.基于遍历的支持度计算代码实现。

    一、基于遍历的支持度计算：

     

    二、基于遍历的支持度计算代码实现：

     基于遍历的支持度计算函数如下：

    1. def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):  # 通过候选项ck生成lk，基于遍历的支持度计算并将各频繁项的支持度保存到support_data字典中
    2.     item_count = {}  # 用于标记各候选项在数据集出现的次数
    3.     Lk = set()
    4.     for t in tqdm(data_set):  # 遍历数据集
    5.         for item in ck:  
    6.             #检查候选集ck中的每一项是否出现在事务t中
    7.     t_num = float(len(data_set))
    8.     for item in item_count:  # 将满足支持度的候选项添加到频繁项集中
    9.         if item_count[item] / t_num >= min_support:
    10.             Lk.add(item)
    11.             support_data[item] = item_count[item]
    12.     return Lk

     其中 data_set 为数据集，ck 为候选 k 项集，min_support为最小支持度， support_data 为各项的支持度记录字典。遍历数据集for循环中检查候选集ck中的每一项是否出现在事务t中请同学自行完成。

    编程要求：

    根据提示，在右侧编辑器补充代码，使用遍历计算支持度。 

    测试说明：

    平台会对你编写的代码进行测试：

    预期输出：6

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.  
    10.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    11.         Ck = set()
    12.         l = len(Lk_1)
    13.         lk_list = list(Lk_1)
    14.         for i in range(l):
    15.             for j in range(i + 1, l):  # 两次遍历Lk-1，找出前n-1个元素相同的项
    16.                 l1 = list(lk_list[i])
    17.                 l2 = list(lk_list[j])
    18.                 l1.sort()
    19.                 l2.sort()
    20.                 if l1[0:size - 2] == l2[0:size - 2]:  # 只有最后一项不同时，生成下一候选项
    21.                     Ck_item = lk_list[i] | lk_list[j]
    22.                     if self.has_infrequent_subset(Ck_item, Lk_1):  # 检查该候选项的子集是否都在Lk-1中
    23.                         Ck.add(Ck_item)
    24.         return Ck
    25.  
    26.     def has_infrequent_subset(self, Ck_item, Lk_1):  # 检查候选项Ck_item的子集是否都在Lk-1中
    27.         for item in Ck_item:
    28.             sub_Ck = Ck_item - frozenset([item])
    29.             if sub_Ck not in Lk_1:
    30.                 return False
    31.         return True
    32.  
    33.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):  # 通过候选项ck生成lk，基于遍历的支持度计算并将各频繁项的支持度保存到support_data字典中
    34.         item_count = {}  # 用于标记各候选项在数据集出现的次数
    35.         Lk = set()
    36.         # 基于遍历的支持度计算
    37.         for t in data_set:  # 遍历数据集
    38.             for item in ck:
    39.                 ##########begin##########
    40.                 # 检查候选集ck中的每一项是否出现在事务t中
    41.  
    42.  
    43.  
    44.                 ##########end##########
    45.         t_num = float(len(data_set))
    46.         for item in item_count:
    47.             ##########begin##########
    48.             # 将满足支持度的候选项添加到频繁项集中
    49.  
    50.  
    51.             
    52.             ##########end##########
    53.         return Lk
    54.  
    55.  
    56. if __name__ == "__main__":
    57.  
    58.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    59.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    60.     apriori = Apriori()
    61.     support_data = {}
    62.     c1 = apriori.create_c1(data)
    63.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    64.     c2 = apriori.create_ck(l1,size=2)
    65.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data,ck=c2,min_support=0.2,support_data=support_data)
    66.     print(len(l2))

     通过代码：

    1. class Apriori():
    2.     def create_c1(self, dataset):  # 遍历整个数据集生成c1候选集
    3.         c1 = set()
    4.         for i in dataset:
    5.             for j in i:
    6.                 item = frozenset([j])
    7.                 c1.add(item)
    8.         return c1
    9.  
    10.     def create_ck(self, Lk_1, size):  # 通过频繁项集Lk-1创建ck候选项集
    11.         Ck = set()
    12.         l = len(Lk_1)
    13.         lk_list = list(Lk_1)
    14.         for i in range(l):
    15.             for j in range(i + 1, l):  # 两次遍历Lk-1，找出前n-1个元素相同的项
    16.                 l1 = list(lk_list[i])
    17.                 l2 = list(lk_list[j])
    18.                 l1.sort()
    19.                 l2.sort()
    20.                 if l1[0:size - 2] == l2[0:size - 2]:  # 只有最后一项不同时，生成下一候选项
    21.                     Ck_item = lk_list[i] | lk_list[j]
    22.                     if self.has_infrequent_subset(Ck_item, Lk_1):  # 检查该候选项的子集是否都在Lk-1中
    23.                         Ck.add(Ck_item)
    24.         return Ck
    25.  
    26.     def has_infrequent_subset(self, Ck_item, Lk_1):  # 检查候选项Ck_item的子集是否都在Lk-1中
    27.         for item in Ck_item:
    28.             sub_Ck = Ck_item - frozenset([item])
    29.             if sub_Ck not in Lk_1:
    30.                 return False
    31.         return True
    32.  
    33.     def generate_lk_by_ck_ergodic(self, data_set, ck, min_support, support_data):  # 通过候选项ck生成lk，基于遍历的支持度计算并将各频繁项的支持度保存到support_data字典中
    34.         item_count = {}  # 用于标记各候选项在数据集出现的次数
    35.         Lk = set()
    36.         # 基于遍历的支持度计算
    37.         for t in data_set:  # 遍历数据集
    38.             for item in ck:
    39.                 ##########begin##########
    40.                 # 检查候选集ck中的每一项是否出现在事务t中
    41.                 if item.issubset(t):
    42.                     if item not in item_count:
    43.                         item_count[item] = 1
    44.                     else:
    45.                         item_count[item] += 1
    46.                 ##########end##########
    47.         t_num = float(len(data_set))
    48.         for item in item_count:
    49.             ##########begin##########
    50.             # 将满足支持度的候选项添加到频繁项集中
    51.              if item_count[item] / t_num >= min_support:
    52.                 Lk.add(item)
    53.                 support_data[item] = item_count[item]
    54.             ##########end##########
    55.         return Lk
    56.  
    57.  
    58. if __name__ == "__main__":
    59.  
    60.     data = [['a','c','e'],['b','d'],['b','c'],['a','b','c','d'],['a','b'],['b','c'],['a','b'],
    61.             ['a','b','c','e'],['a','b','c'],['a','c','e']]
    62.     apriori = Apriori()
    63.     support_data = {}
    64.     c1 = apriori.create_c1(data)
    65.     l1 = apriori.generate_lk_by_ck_ergodic(data_set=data, ck=c1, min_support=0.2, support_data=support_data)
    66.     c2 = apriori.create_ck(l1,size=2)
    67.     l2 = apriori.generate_lk_by_ck_ergodic(data_set=data,ck=c2,min_support=0.2,support_data=support_data)
    68.     print(len(l2))

    第四关：基于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}

    可构建如下 hash 树： 树的每个内部结点都使用hash函数h(p)=p mod 3来确定应当沿着当前结点的哪个分支向下。例如，项 1，4 和 7 应当散列到相同的分支(即最左分支)，因为除以 3 之后它们都具有相同的余数。所有的候选项集都存放在hash树的叶结点中。下图图中显示的 hash 树包含 15个候选 3-项集，分布在 9 个叶结点中。

    构建过程如下：

    给定一个事务 t , 跟哪些候选 3 项集匹配？例如下图中的例子：

    匹配过程如下：

    考虑一个事务 t={1,2,3,5,6} 。为了更新候选项集的支持度计数，必须这样遍历 Hash 树:所有包含属于事务 t 的候选 3 -项集的叶结点至少访问一次。

    注意：包含在t中的候选 3 -项集必须以项 1，2或3 开始，如上图中第一层前缀结构所示。这样，在Hash树的根结点，事务中的项 1，2 和 3 将分别散列。项 1 被散列到根结点的左子女，项 2 被散列到中间子女，而项 3 被散列到右子女。在树的下一层，事务根据上图中的第二层结构列出的第二项进行散列。

    例如，在根结点散列项1之后，散列事务的项 2、3 和 5 。项 2 和 5 散列到中间子女，而 3 散列到右子女，如上图所示。继续该过程，直至到达 Hash 树的叶结点。存放在被访问的叶结点中的候选项集与事务进行比较，如果候选项集是该事务的子集，则增加它的支持度计数。在这个例子中，访问了 9 个叶结点中的 5 个， 15 个项集中的 9 个与事务进行比较。可以看到匹配过程只需要进行 11 次比较。

    二、基于hash的支持度计算代码实现：

    基于 hash 的支持度计算关键在于 hash 树的构建。 首先构建节点类：

    1. #Hash节点类定义
    2. class Hash_node:
    3.     def __init__(self):
    4.         self.children = {}           #指向子节点的指针
    5.         self.Leaf_status = True      #了解当前节点是否为叶子节点的状态
    6.         self.bucket = {}             #在储存桶中包含项目集

     然后构建hash树类：

    1. #构造得到Hash树类
    2. class HashTree:
    3.     # class constructor
    4.     def __init__(self, max_leaf_count, max_child_count):
    5.         self.root = Hash_node()
    6.         self.max_leaf_count = max_leaf_count
    7.         self.max_child_count = max_child_count
    8.         self.frequent_itemsets = []
    9.     # 进行递归插入以生成hashtree
    10.     def recursively_insert(self, node, itemset, index, count):
    11.         if index == len(itemset):
    12.             if itemset in node.bucket:
    13.                 node.bucket[itemset] += count
    14.             else:
    15.                 node.bucket[itemset] = count
    16.             return
    17.         if node.Leaf_status:                             #如果node是叶结点
    18.             if itemset in node.bucket:
    19.                 node.bucket[itemset] += count
    20.             else:
    21.                 node.bucket[itemset] = count
    22.             if len(node.bucket) == self.max_leaf_count:  #如果储存桶容量增加
    23.                 for old_itemset, old_count in node.bucket.items():
    24.                     hash_key = self.hash_function(old_itemset[index])  #对下一个索引做哈希
    25.                     if hash_key not in node.children:
    26.                         node.children[hash_key] = Hash_node()
    27.                     self.recursively_insert(node.children[hash_key], old_itemset, index + 1, old_count)
    28.                 del node.bucket
    29.                 node.Leaf_status = False
    30.         else:                                            
    31.             #如果node不是是叶结点
    32.             #需要进行递归式的嵌入
    33.     def insert(self, itemset):
    34.         itemset = tuple(itemset)
    35.         self.recursively_insert(self.root, itemset, 0, 0)
    36.     # 添加支持度到候选项集中. 遍历树并找到该项集所在的储存桶.
    37.     def add_support(self, itemset):
    38.         Transverse_HNode = self.root
    39.         itemset = tuple(itemset)
    40.         index = 0
    41.         while True:
    42.             if Transverse_HNode.Leaf_status:
    43.                 if itemset in Transverse_HNode.bucket:    #在此储存桶中找到项集
    44.                     Transverse_HNode.bucket[itemset] += 1 #增加此项目集的计数
    45.                 break
    46.             hash_key = self.hash_function(itemset[index])
    47.             if hash_key in Transverse_HNode.children:
    48.                 Transverse_HNode = Transverse_HNode.children[hash_key]
    49.             else:
    50.                 break
    51.             index += 1
    52.     def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
    53.         if node.Leaf_status:
    54.             for key, value in node.bucket.items():
    55.                 if value >= support_count:                       #如果满足支持数条件
    56.                     frequent_itemsets.append(list(key))          #将其添加到频繁项集中
    57.                     Frequent_items_value[key] = value
    58.             return
    59.         for child in node.children.values():
    60.             self.get_frequent_itemsets(child, support_count,frequent_itemsets)
    61.     # 用于构造hash树的hash函数定义
    62.     def hash_function(self, val):
    63.         return int(val) % self.max_child_count

    其中如果node不是叶结点，需要进行递归式的嵌入，请同学自行完成。
    提示：

    调用hash函数计算hash值。
    判断hash值是否在子节点中。
    如果不在就构建新节点。
    调用recursively_insert嵌入。

    编程要求：

     根据提示，在右侧编辑器补充代码，构造正确的hash树类实现hash的支持度计算。

    测试说明：

    平台会对你编写的代码进行测试：

    预期输出：

    1. ['1 3 5', '2 4', '1 2 3 4', '1 2', '2 3', '1 2', '2 3', '1 2 3 5', '1 2 3', '1 3 5']
    2. [['1'], ['3'], ['5'], ['2'], ['4']]
    3. {('1',): 7, ('3',): 7, ('5',): 3, ('2',): 8, ('4',): 2}
    4. All frequent itemsets with their support count:
    5. {('1',): 7, ('3',): 7, ('5',): 3, ('2',): 8, ('4',): 2, ('1', '3'): 5, ('1', '5'): 3, ('1', '2'): 5, ('3', '5'): 3, ('2', '3'): 5, ('2', '4'): 2, ('1', '3', '5'): 3, ('1', '2', '3'): 3}

    开始你的任务吧，祝你成功！

    1. import itertools
    2. import time
    3.  
    4. filename = "data.csv"
    5.  
    6. min_support = 2
    7.  
    8. #读取数据集
    9. with open(filename) as f:
    10.     content = f.readlines()
    11.  
    12. content = [x.strip() for x in content]
    13. print(content)
    14.  
    15. Transaction = []                  #保存事务列表
    16. Frequent_items_value = {}         #保存所有频繁项集字典
    17.  
    18. #将数据集的内容添加到事物列表
    19. for i in range(0,len(content)):
    20.     Transaction.append(content[i].split())
    21.  
    22. #获得频繁一项集
    23. def frequent_one_item(Transaction,min_support):
    24.     candidate1 = {}
    25.  
    26.     for i in range(0,len(Transaction)):
    27.         for j in range(0,len(Transaction[i])):
    28.             if Transaction[i][j] not in candidate1:
    29.                 candidate1[Transaction[i][j]] = 1
    30.             else:
    31.                 candidate1[Transaction[i][j]] += 1
    32.  
    33.     frequentitem1 = []                      #获得满足最小支持度的频繁一项集
    34.     for value in candidate1:
    35.         if candidate1[value] >= min_support:
    36.             frequentitem1 = frequentitem1 + [[value]]
    37.             Frequent_items_value[tuple(value)] = candidate1[value]
    38.  
    39.     return frequentitem1
    40.  
    41. values = frequent_one_item(Transaction,min_support)
    42. print(values)
    43. print(Frequent_items_value)
    44.  
    45.  
    46. # 从事物中删除不频繁的一项集
    47. Transaction1 = []
    48. for i in range(0,len(Transaction)):
    49.     list_val = []
    50.     for j in range(0,len(Transaction[i])):
    51.         if [Transaction[i][j]] in values:
    52.             list_val.append(Transaction[i][j])
    53.     Transaction1.append(list_val)
    54.  
    55.  
    56. #Hash节点类定义
    57. class Hash_node:
    58.     def __init__(self):
    59.         self.children = {}           #指向子节点的指针
    60.         self.Leaf_status = True      #了解当前节点是否为叶子节点的状态
    61.         self.bucket = {}             #在储存桶中包含项目集
    62.  
    63. #构造得到Hash树类
    64. class HashTree:
    65.     # class constructor
    66.     def __init__(self, max_leaf_count, max_child_count):
    67.         self.root = Hash_node()
    68.         self.max_leaf_count = max_leaf_count
    69.         self.max_child_count = max_child_count
    70.         self.frequent_itemsets = []
    71.  
    72.     # 进行递归插入以生成hashtree
    73.     def recursively_insert(self, node, itemset, index, count):
    74.         if index == len(itemset):
    75.             if itemset in node.bucket:
    76.                 node.bucket[itemset] += count
    77.             else:
    78.                 node.bucket[itemset] = count
    79.             return
    80.  
    81.         if node.Leaf_status:
    82.             ##########begin##########
    83.             #如果node是叶结点所进行的操作代码
    84.  
    85.  
    86.             ##########end##########                             
    87.             
    88.         else:
    89.             ##########begin##########
    90.             #如果node不是是叶结点所进行的操作代码
    91.  
    92.  
    93.             ##########end##########
    94.             
    95.  
    96.     def insert(self, itemset):
    97.         itemset = tuple(itemset)
    98.         self.recursively_insert(self.root, itemset, 0, 0)
    99.  
    100.     # 添加支持度到候选项集中. 遍历树并找到该项集所在的储存桶.
    101.     def add_support(self, itemset):
    102.         Transverse_HNode = self.root
    103.         itemset = tuple(itemset)
    104.         index = 0
    105.         while True:
    106.             if Transverse_HNode.Leaf_status:
    107.                 if itemset in Transverse_HNode.bucket:    #在此储存桶中找到项集
    108.                     Transverse_HNode.bucket[itemset] += 1 #增加此项目集的计数
    109.                 break
    110.             hash_key = self.hash_function(itemset[index])
    111.             if hash_key in Transverse_HNode.children:
    112.                 Transverse_HNode = Transverse_HNode.children[hash_key]
    113.             else:
    114.                 break
    115.             index += 1
    116.  
    117.  
    118.     # 基于hash的支持度计算
    119.     def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
    120.         ##########begin##########
    121.         #获取频繁项集函数定义
    122.  
    123.  
    124.         
    125.         ##########end##########
    126.     # hash function for making HashTree
    127.     def hash_function(self, val):
    128.         return int(val) % self.max_child_count
    129.  
    130. #生成hashTree
    131. def generate_hash_tree(candidate_itemsets, max_leaf_count, max_child_count):
    132.     htree = HashTree(max_child_count, max_leaf_count)             #create instance of HashTree
    133.     for itemset in candidate_itemsets:
    134.         htree.insert(itemset)                                     #to insert itemset into Hashtree
    135.     return htree
    136.  
    137. #to generate subsets of itemsets of size k
    138. def generate_k_subsets(dataset, length):
    139.     subsets = []
    140.     for itemset in dataset:
    141.         subsets.extend(map(list, itertools.combinations(itemset, length)))
    142.     return subsets
    143.  
    144. def subset_generation(ck_data,l):
    145.     return map(list,set(itertools.combinations(ck_data,l)))
    146.  
    147.  
    148. # 候选生成
    149.  
    150. def apriori_generate(dataset,k):
    151.     ck = []
    152.     #join step
    153.     lenlk = len(dataset)
    154.     for i in range(lenlk):
    155.         for j in range(i+1,lenlk):
    156.             L1 = list(dataset[i])[:k - 2]
    157.             L2 = list(dataset[j])[:k - 2]
    158.             if L1 == L2:
    159.                 ck.append(sorted(list(set(dataset[i]) | set(dataset[j]))))
    160.  
    161.     #prune step
    162.     final_ck = []
    163.     for candidate in ck:
    164.         all_subsets = list(subset_generation(set(candidate), k - 1))
    165.         found = True
    166.         for i in range(len(all_subsets)):
    167.             value = list(sorted(all_subsets[i]))
    168.             if value not in dataset:
    169.                 found = False
    170.         if found == True:
    171.             final_ck.append(candidate)
    172.  
    173.     return ck,final_ck
    174.  
    175.  
    176. # 候选剪枝
    177.  
    178. def generateL(ck,min_support):
    179.     support_ck = {}
    180.     for val in Transaction1:
    181.         for val1 in ck:
    182.             value = set(val)
    183.             value1 = set(val1)
    184.  
    185.             if value1.issubset(value):
    186.                 if tuple(val1) not in support_ck:
    187.                     support_ck[tuple(val1)] = 1
    188.                 else:
    189.                     support_ck[tuple(val1)] += 1
    190.     frequent_item = []
    191.     for item_set in support_ck:
    192.         if support_ck[item_set] >= min_support:
    193.             frequent_item.append(sorted(list(item_set)))
    194.             Frequent_items_value[item_set] = support_ck[item_set]
    195.  
    196.     return frequent_item
    197.  
    198. # apriori算法主函数
    199. def apriori(L1,min_support):
    200.     k = 2;
    201.     L = []
    202.     L.append(0)
    203.     L.append(L1)
    204.     max_leaf_count = 6  #每个hash树节点的最大容量
    205.     max_child_count = 6  #每个hash树节点的最大子节点数
    206.  
    207.     start = time.time()
    208.     while(len(L[k-1])>0):
    209.         ck,final_ck = apriori_generate(L[k-1],k)                 #生成候选项集
    210.         # print("C%d" %(k))
    211.         # print(final_ck)
    212.         h_tree = generate_hash_tree(ck,max_leaf_count,max_child_count)       #生成hash树
    213.         if (k > 2):
    214.             while(len(L[k-1])>0):
    215.                 l = generateL(final_ck, min_support)
    216.                 L.append(l)
    217.                 # print("Frequent %d item" % (k))
    218.                 # print(l)
    219.                 k = k + 1
    220.                 ck, final_ck = apriori_generate(L[k - 1], k)
    221.                 # print("C%d" % (k))
    222.                 # print(final_ck)
    223.             break
    224.         k_subsets = generate_k_subsets(Transaction1,k)                  #生成事物子集
    225.         for subset in k_subsets:
    226.             h_tree.add_support(subset)                                  #像hash树的项集添加支持数
    227.         lk = []
    228.         h_tree.get_frequent_itemsets(h_tree.root,min_support,lk)                  #获取频繁项集
    229.         # print("Frequent %d item" %(k))
    230.         # print(lk)
    231.         L.append(lk)
    232.         k = k + 1
    233.     end = time.time()
    234.     return L,(end-start)
    235.  
    236. L_value,time_taken = apriori(values,min_support)
    237. #print("final L_value")
    238. #print(L_value)
    239. print("All frequent itemsets with their support count:")
    240. print(Frequent_items_value)
    1. import itertools
    2. import time
    3.  
    4. filename = "data.csv"
    5.  
    6. min_support = 2
    7.  
    8. #读取数据集
    9. with open(filename) as f:
    10.     content = f.readlines()
    11.  
    12. content = [x.strip() for x in content]
    13. print(content)
    14.  
    15. Transaction = []                  #保存事务列表
    16. Frequent_items_value = {}         #保存所有频繁项集字典
    17.  
    18. #将数据集的内容添加到事物列表
    19. for i in range(0,len(content)):
    20.     Transaction.append(content[i].split())
    21.  
    22. #获得频繁一项集
    23. def frequent_one_item(Transaction,min_support):
    24.     candidate1 = {}
    25.  
    26.     for i in range(0,len(Transaction)):
    27.         for j in range(0,len(Transaction[i])):
    28.             if Transaction[i][j] not in candidate1:
    29.                 candidate1[Transaction[i][j]] = 1
    30.             else:
    31.                 candidate1[Transaction[i][j]] += 1
    32.  
    33.     frequentitem1 = []                      #获得满足最小支持度的频繁一项集
    34.     for value in candidate1:
    35.         if candidate1[value] >= min_support:
    36.             frequentitem1 = frequentitem1 + [[value]]
    37.             Frequent_items_value[tuple(value)] = candidate1[value]
    38.  
    39.     return frequentitem1
    40.  
    41. values = frequent_one_item(Transaction,min_support)
    42. print(values)
    43. print(Frequent_items_value)
    44.  
    45.  
    46. # 从事物中删除不频繁的一项集
    47. Transaction1 = []
    48. for i in range(0,len(Transaction)):
    49.     list_val = []
    50.     for j in range(0,len(Transaction[i])):
    51.         if [Transaction[i][j]] in values:
    52.             list_val.append(Transaction[i][j])
    53.     Transaction1.append(list_val)
    54.  
    55.  
    56. #Hash节点类定义
    57. class Hash_node:
    58.     def __init__(self):
    59.         self.children = {}           #指向子节点的指针
    60.         self.Leaf_status = True      #了解当前节点是否为叶子节点的状态
    61.         self.bucket = {}             #在储存桶中包含项目集
    62.  
    63. #构造得到Hash树类
    64. class HashTree:
    65.     # class constructor
    66.     def __init__(self, max_leaf_count, max_child_count):
    67.         self.root = Hash_node()
    68.         self.max_leaf_count = max_leaf_count
    69.         self.max_child_count = max_child_count
    70.         self.frequent_itemsets = []
    71.  
    72.     # 进行递归插入以生成hashtree
    73.     def recursively_insert(self, node, itemset, index, count):
    74.         if index == len(itemset):
    75.             if itemset in node.bucket:
    76.                 node.bucket[itemset] += count
    77.             else:
    78.                 node.bucket[itemset] = count
    79.             return
    80.  
    81.         if node.Leaf_status:
    82.             ##########begin##########
    83.             #如果node是叶结点所进行的操作代码
    84.             if itemset in node.bucket:
    85.                 node.bucket[itemset]+=count
    86.             else:
    87.                 node.bucket[itemset]=count
    88.                 if len(node.bucket)==self.max_leaf_count:
    89.                     如果储存桶容量增加
    90.                 for old_itemset, old_count in node.bucket.items():
    91.                     hash_key = self.hash_function(old_itemset[index])  #对下一个索引做哈希
    92.                     if hash_key not in node.children:
    93.                         node.children[hash_key] = Hash_node()
    94.                     self.recursively_insert(node.children[hash_key], old_itemset, index + 1, old_count)
    95.                 del node.bucket
    96.                 node.Leaf_status = False
    97.  
    98.  
    99.  
    100.             ##########end##########                             
    101.             
    102.         else:
    103.             ##########begin##########
    104.             #如果node不是是叶结点所进行的操作代码
    105.             hash_key=self.hash_function(itemset[index])
    106.             if hash_key not in node.children:
    107.                 node.children[hash_key]=Hash_node()
    108.             self.recursively_insert(node.children[hash_key],itemset,index+1,count)
    109.  
    110.  
    111.  
    112.             ##########end##########
    113.             
    114.  
    115.     def insert(self, itemset):
    116.         itemset = tuple(itemset)
    117.         self.recursively_insert(self.root, itemset, 0, 0)
    118.  
    119.     # 添加支持度到候选项集中. 遍历树并找到该项集所在的储存桶.
    120.     def add_support(self, itemset):
    121.         Transverse_HNode = self.root
    122.         itemset = tuple(itemset)
    123.         index = 0
    124.         while True:
    125.             if Transverse_HNode.Leaf_status:
    126.                 if itemset in Transverse_HNode.bucket:    #在此储存桶中找到项集
    127.                     Transverse_HNode.bucket[itemset] += 1 #增加此项目集的计数
    128.                 break
    129.             hash_key = self.hash_function(itemset[index])
    130.             if hash_key in Transverse_HNode.children:
    131.                 Transverse_HNode = Transverse_HNode.children[hash_key]
    132.             else:
    133.                 break
    134.             index += 1
    135.  
    136.  
    137.     # 基于hash的支持度计算
    138.     def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
    139.         ##########begin##########
    140.         #获取频繁项集函数定义
    141.         if node.Leaf_status:
    142.             for key, value in node.bucket.items():
    143.                 if value >= support_count: 
    144.                     #如果满足支持数条件
    145.                     frequent_itemsets.append(list(key))          #将其添加到频繁项集中
    146.                     Frequent_items_value[key] = value
    147.             return
    148.         for child in node.children.values():
    149.             self.get_frequent_itemsets(child, support_count,frequent_itemsets)
    150.  
    151.  
    152.  
    153.         
    154.         ##########end##########
    155.     # hash function for making HashTree
    156.     def hash_function(self, val):
    157.         return int(val) % self.max_child_count
    158.  
    159. #生成hashTree
    160. def generate_hash_tree(candidate_itemsets, max_leaf_count, max_child_count):
    161.     htree = HashTree(max_child_count, max_leaf_count)             #create instance of HashTree
    162.     for itemset in candidate_itemsets:
    163.         htree.insert(itemset)                                     #to insert itemset into Hashtree
    164.     return htree
    165.  
    166. #to generate subsets of itemsets of size k
    167. def generate_k_subsets(dataset, length):
    168.     subsets = []
    169.     for itemset in dataset:
    170.         subsets.extend(map(list, itertools.combinations(itemset, length)))
    171.     return subsets
    172.  
    173. def subset_generation(ck_data,l):
    174.     return map(list,set(itertools.combinations(ck_data,l)))
    175.  
    176.  
    177. # 候选生成
    178.  
    179. def apriori_generate(dataset,k):
    180.     ck = []
    181.     #join step
    182.     lenlk = len(dataset)
    183.     for i in range(lenlk):
    184.         for j in range(i+1,lenlk):
    185.             L1 = list(dataset[i])[:k - 2]
    186.             L2 = list(dataset[j])[:k - 2]
    187.             if L1 == L2:
    188.                 ck.append(sorted(list(set(dataset[i]) | set(dataset[j]))))
    189.  
    190.     #prune step
    191.     final_ck = []
    192.     for candidate in ck:
    193.         all_subsets = list(subset_generation(set(candidate), k - 1))
    194.         found = True
    195.         for i in range(len(all_subsets)):
    196.             value = list(sorted(all_subsets[i]))
    197.             if value not in dataset:
    198.                 found = False
    199.         if found == True:
    200.             final_ck.append(candidate)
    201.  
    202.     return ck,final_ck
    203.  
    204.  
    205. # 候选剪枝
    206.  
    207. def generateL(ck,min_support):
    208.     support_ck = {}
    209.     for val in Transaction1:
    210.         for val1 in ck:
    211.             value = set(val)
    212.             value1 = set(val1)
    213.  
    214.             if value1.issubset(value):
    215.                 if tuple(val1) not in support_ck:
    216.                     support_ck[tuple(val1)] = 1
    217.                 else:
    218.                     support_ck[tuple(val1)] += 1
    219.     frequent_item = []
    220.     for item_set in support_ck:
    221.         if support_ck[item_set] >= min_support:
    222.             frequent_item.append(sorted(list(item_set)))
    223.             Frequent_items_value[item_set] = support_ck[item_set]
    224.  
    225.     return frequent_item
    226.  
    227. # apriori算法主函数
    228. def apriori(L1,min_support):
    229.     k = 2;
    230.     L = []
    231.     L.append(0)
    232.     L.append(L1)
    233.     max_leaf_count = 6  #每个hash树节点的最大容量
    234.     max_child_count = 6  #每个hash树节点的最大子节点数
    235.  
    236.     start = time.time()
    237.     while(len(L[k-1])>0):
    238.         ck,final_ck = apriori_generate(L[k-1],k)                 #生成候选项集
    239.         # print("C%d" %(k))
    240.         # print(final_ck)
    241.         h_tree = generate_hash_tree(ck,max_leaf_count,max_child_count)       #生成hash树
    242.         if (k > 2):
    243.             while(len(L[k-1])>0):
    244.                 l = generateL(final_ck, min_support)
    245.                 L.append(l)
    246.                 # print("Frequent %d item" % (k))
    247.                 # print(l)
    248.                 k = k + 1
    249.                 ck, final_ck = apriori_generate(L[k - 1], k)
    250.                 # print("C%d" % (k))
    251.                 # print(final_ck)
    252.             break
    253.         k_subsets = generate_k_subsets(Transaction1,k)                  #生成事物子集
    254.         for subset in k_subsets:
    255.             h_tree.add_support(subset)                                  #像hash树的项集添加支持数
    256.         lk = []
    257.         h_tree.get_frequent_itemsets(h_tree.root,min_support,lk)                  #获取频繁项集
    258.         # print("Frequent %d item" %(k))
    259.         # print(lk)
    260.         L.append(lk)
    261.         k = k + 1
    262.     end = time.time()
    263.     return L,(end-start)
    264.  
    265. L_value,time_taken = apriori(values,min_support)
    266. #print("final L_value")
    267. #print(L_value)
    268. print("All frequent itemsets with their support count:")
    269. print(Frequent_items_value)

  • 相关阅读:
    如何打造一个优秀的品牌？创立品牌的真正目的是什么？
    （附源码）ssm招聘网站 毕业设计 250858
    基于MYSQL的论坛管理系统数据库设计项目实战
    【iOS】—— 响应者链和事件传递链
    SQL优化--主键查询
    谷歌牛人发布小说式《算法图解》，竟被人扒下来，在GitHub开源了
    cmdline（二）：uboot cmdline怎么传？&&cmdline kernel怎么用？
    编程前置：句子联想游戏
    Nginx 无法正确加载静态文件，静态文件加载404或者为html；Nginx 配置访问指定url路径项目部署；
    MySQL中如何识别低效的索引
  • 原文地址：https://blog.csdn.net/m0_58153897/article/details/127756637