数据挖掘与机器学习：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项集生成函数如下：

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

其中 dataset 为数据集列表。

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

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

伪代码示例：

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

编程要求：

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

测试说明：

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

预期输出：4

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个元素相同的项


                ##########end##########
                if l1[0:size - 2] == l2[0:size - 2]:  
                    ##########begin##########
                    #只有最后一项不同时，生成下一候选项

                    
                    ##########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))

通过代码：
 

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]
                    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))

第二关：候选剪枝

任务描述：

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

相关知识：

为了完成本关任务，你需要掌握：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​ 中。 检查函数主体如下：

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 

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

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

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

编程要求：

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

测试说明：

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

预期输出：2

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中函数定义

        
        ##########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个元素相同的项


                ##########end##########
                if l1[0:size - 2] == l2[0:size - 2]:  
                    ##########begin##########
                    #只有最后一项不同时，生成下一候选项
                    #检查该候选项的子集是否都在Lk-1中



                    ##########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))

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:
            sub_Ck = Ck_item - frozenset([item])
            if sub_Ck not in 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]
                    if self.has_infrequent_subset(Ck_item, Lk_1):
                        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))

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

任务描述：

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

相关知识：

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

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

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

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

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 

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

编程要求：

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

测试说明：

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

预期输出：6

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):  # 两次遍历Lk-1，找出前n-1个元素相同的项
                l1 = list(lk_list[i])
                l2 = list(lk_list[j])
                l1.sort()
                l2.sort()
                if l1[0:size - 2] == l2[0:size - 2]:  # 只有最后一项不同时，生成下一候选项
                    Ck_item = lk_list[i] | lk_list[j]
                    if self.has_infrequent_subset(Ck_item, Lk_1):  # 检查该候选项的子集是否都在Lk-1中
                        Ck.add(Ck_item)
        return Ck

    def has_infrequent_subset(self, Ck_item, Lk_1):  # 检查候选项Ck_item的子集是否都在Lk-1中
        for item in Ck_item:
            sub_Ck = Ck_item - frozenset([item])
            if sub_Ck not in Lk_1:
                return False
        return True

    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:
                ##########begin##########
                # 检查候选集ck中的每一项是否出现在事务t中



                ##########end##########
        t_num = float(len(data_set))
        for item in item_count:
            ##########begin##########
            # 将满足支持度的候选项添加到频繁项集中


            
            ##########end##########
        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)
    print(len(l2))

 通过代码：

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):  # 两次遍历Lk-1，找出前n-1个元素相同的项
                l1 = list(lk_list[i])
                l2 = list(lk_list[j])
                l1.sort()
                l2.sort()
                if l1[0:size - 2] == l2[0:size - 2]:  # 只有最后一项不同时，生成下一候选项
                    Ck_item = lk_list[i] | lk_list[j]
                    if self.has_infrequent_subset(Ck_item, Lk_1):  # 检查该候选项的子集是否都在Lk-1中
                        Ck.add(Ck_item)
        return Ck

    def has_infrequent_subset(self, Ck_item, Lk_1):  # 检查候选项Ck_item的子集是否都在Lk-1中
        for item in Ck_item:
            sub_Ck = Ck_item - frozenset([item])
            if sub_Ck not in Lk_1:
                return False
        return True

    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:
                ##########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


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)
    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 树的构建。 首先构建节点类：

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

 然后构建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 

其中如果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}

开始你的任务吧，祝你成功！文章来源地址https://www.toymoban.com/news/detail-469740.html

import itertools
import time

filename = "data.csv"

min_support = 2

#读取数据集
with open(filename) as f:
    content = f.readlines()

content = [x.strip() for x in content]
print(content)

Transaction = []                  #保存事务列表
Frequent_items_value = {}         #保存所有频繁项集字典

#将数据集的内容添加到事物列表
for i in range(0,len(content)):
    Transaction.append(content[i].split())

#获得频繁一项集
def frequent_one_item(Transaction,min_support):
    candidate1 = {}

    for i in range(0,len(Transaction)):
        for j in range(0,len(Transaction[i])):
            if Transaction[i][j] not in candidate1:
                candidate1[Transaction[i][j]] = 1
            else:
                candidate1[Transaction[i][j]] += 1

    frequentitem1 = []                      #获得满足最小支持度的频繁一项集
    for value in candidate1:
        if candidate1[value] >= min_support:
            frequentitem1 = frequentitem1 + [[value]]
            Frequent_items_value[tuple(value)] = candidate1[value]

    return frequentitem1

values = frequent_one_item(Transaction,min_support)
print(values)
print(Frequent_items_value)


# 从事物中删除不频繁的一项集
Transaction1 = []
for i in range(0,len(Transaction)):
    list_val = []
    for j in range(0,len(Transaction[i])):
        if [Transaction[i][j]] in values:
            list_val.append(Transaction[i][j])
    Transaction1.append(list_val)


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

#构造得到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是叶结点所进行的操作代码


            ##########end##########                             
            
        else:
            ##########begin##########
            #如果node不是是叶结点所进行的操作代码


            ##########end##########
            

    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


    # 基于hash的支持度计算
    def get_frequent_itemsets(self, node, support_count,frequent_itemsets):
        ##########begin##########
        #获取频繁项集函数定义


        
        ##########end##########
    # hash function for making HashTree
    def hash_function(self, val):
        return int(val) % self.max_child_count

#生成hashTree
def generate_hash_tree(candidate_itemsets, max_leaf_count, max_child_count):
    htree = HashTree(max_child_count, max_leaf_count)             #create instance of HashTree
    for itemset in candidate_itemsets:
        htree.insert(itemset)                                     #to insert itemset into Hashtree
    return htree

#to generate subsets of itemsets of size k
def generate_k_subsets(dataset, length):
    subsets = []
    for itemset in dataset:
        subsets.extend(map(list, itertools.combinations(itemset, length)))
    return subsets

def subset_generation(ck_data,l):
    return map(list,set(itertools.combinations(ck_data,l)))


# 候选生成

def apriori_generate(dataset,k):
    ck = []
    #join step
    lenlk = len(dataset)
    for i in range(lenlk):
        for j in range(i+1,lenlk):
            L1 = list(dataset[i])[:k - 2]
            L2 = list(dataset[j])[:k - 2]
            if L1 == L2:
                ck.append(sorted(list(set(dataset[i]) | set(dataset[j]))))

    #prune step
    final_ck = []
    for candidate in ck:
        all_subsets = list(subset_generation(set(candidate), k - 1))
        found = True
        for i in range(len(all_subsets)):
            value = list(sorted(all_subsets[i]))
            if value not in dataset:
                found = False
        if found == True:
            final_ck.append(candidate)

    return ck,final_ck


# 候选剪枝

def generateL(ck,min_support):
    support_ck = {}
    for val in Transaction1:
        for val1 in ck:
            value = set(val)
            value1 = set(val1)

            if value1.issubset(value):
                if tuple(val1) not in support_ck:
                    support_ck[tuple(val1)] = 1
                else:
                    support_ck[tuple(val1)] += 1
    frequent_item = []
    for item_set in support_ck:
        if support_ck[item_set] >= min_support:
            frequent_item.append(sorted(list(item_set)))
            Frequent_items_value[item_set] = support_ck[item_set]

    return frequent_item

# apriori算法主函数
def apriori(L1,min_support):
    k = 2;
    L = []
    L.append(0)
    L.append(L1)
    max_leaf_count = 6  #每个hash树节点的最大容量
    max_child_count = 6  #每个hash树节点的最大子节点数

    start = time.time()
    while(len(L[k-1])>0):
        ck,final_ck = apriori_generate(L[k-1],k)                 #生成候选项集
        # print("C%d" %(k))
        # print(final_ck)
        h_tree = generate_hash_tree(ck,max_leaf_count,max_child_count)       #生成hash树
        if (k > 2):
            while(len(L[k-1])>0):
                l = generateL(final_ck, min_support)
                L.append(l)
                # print("Frequent %d item" % (k))
                # print(l)
                k = k + 1
                ck, final_ck = apriori_generate(L[k - 1], k)
                # print("C%d" % (k))
                # print(final_ck)
            break
        k_subsets = generate_k_subsets(Transaction1,k)                  #生成事物子集
        for subset in k_subsets:
            h_tree.add_support(subset)                                  #像hash树的项集添加支持数
        lk = []
        h_tree.get_frequent_itemsets(h_tree.root,min_support,lk)                  #获取频繁项集
        # print("Frequent %d item" %(k))
        # print(lk)
        L.append(lk)
        k = k + 1
    end = time.time()
    return L,(end-start)

L_value,time_taken = apriori(values,min_support)
#print("final L_value")
#print(L_value)
print("All frequent itemsets with their support count:")
print(Frequent_items_value)

import itertools
import time

filename = "data.csv"

min_support = 2

#读取数据集
with open(filename) as f:
    content = f.readlines()

content = [x.strip() for x in content]
print(content)

Transaction = []                  #保存事务列表
Frequent_items_value = {}         #保存所有频繁项集字典

#将数据集的内容添加到事物列表
for i in range(0,len(content)):
    Transaction.append(content[i].split())

#获得频繁一项集
def frequent_one_item(Transaction,min_support):
    candidate1 = {}

    for i in range(0,len(Transaction)):
        for j in range(0,len(Transaction[i])):
            if Transaction[i][j] not in candidate1:
                candidate1[Transaction[i][j]] = 1
            else:
                candidate1[Transaction[i][j]] += 1

    frequentitem1 = []                      #获得满足最小支持度的频繁一项集
    for value in candidate1:
        if candidate1[value] >= min_support:
            frequentitem1 = frequentitem1 + [[value]]
            Frequent_items_value[tuple(value)] = candidate1[value]

    return frequentitem1

values = frequent_one_item(Transaction,min_support)
print(values)
print(Frequent_items_value)


# 从事物中删除不频繁的一项集
Transaction1 = []
for i in range(0,len(Transaction)):
    list_val = []
    for j in range(0,len(Transaction[i])):
        if [Transaction[i][j]] in values:
            list_val.append(Transaction[i][j])
    Transaction1.append(list_val)


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

#构造得到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##########
            

    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


    # 基于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##########
    # hash function for making HashTree
    def hash_function(self, val):
        return int(val) % self.max_child_count

#生成hashTree
def generate_hash_tree(candidate_itemsets, max_leaf_count, max_child_count):
    htree = HashTree(max_child_count, max_leaf_count)             #create instance of HashTree
    for itemset in candidate_itemsets:
        htree.insert(itemset)                                     #to insert itemset into Hashtree
    return htree

#to generate subsets of itemsets of size k
def generate_k_subsets(dataset, length):
    subsets = []
    for itemset in dataset:
        subsets.extend(map(list, itertools.combinations(itemset, length)))
    return subsets

def subset_generation(ck_data,l):
    return map(list,set(itertools.combinations(ck_data,l)))


# 候选生成

def apriori_generate(dataset,k):
    ck = []
    #join step
    lenlk = len(dataset)
    for i in range(lenlk):
        for j in range(i+1,lenlk):
            L1 = list(dataset[i])[:k - 2]
            L2 = list(dataset[j])[:k - 2]
            if L1 == L2:
                ck.append(sorted(list(set(dataset[i]) | set(dataset[j]))))

    #prune step
    final_ck = []
    for candidate in ck:
        all_subsets = list(subset_generation(set(candidate), k - 1))
        found = True
        for i in range(len(all_subsets)):
            value = list(sorted(all_subsets[i]))
            if value not in dataset:
                found = False
        if found == True:
            final_ck.append(candidate)

    return ck,final_ck


# 候选剪枝

def generateL(ck,min_support):
    support_ck = {}
    for val in Transaction1:
        for val1 in ck:
            value = set(val)
            value1 = set(val1)

            if value1.issubset(value):
                if tuple(val1) not in support_ck:
                    support_ck[tuple(val1)] = 1
                else:
                    support_ck[tuple(val1)] += 1
    frequent_item = []
    for item_set in support_ck:
        if support_ck[item_set] >= min_support:
            frequent_item.append(sorted(list(item_set)))
            Frequent_items_value[item_set] = support_ck[item_set]

    return frequent_item

# apriori算法主函数
def apriori(L1,min_support):
    k = 2;
    L = []
    L.append(0)
    L.append(L1)
    max_leaf_count = 6  #每个hash树节点的最大容量
    max_child_count = 6  #每个hash树节点的最大子节点数

    start = time.time()
    while(len(L[k-1])>0):
        ck,final_ck = apriori_generate(L[k-1],k)                 #生成候选项集
        # print("C%d" %(k))
        # print(final_ck)
        h_tree = generate_hash_tree(ck,max_leaf_count,max_child_count)       #生成hash树
        if (k > 2):
            while(len(L[k-1])>0):
                l = generateL(final_ck, min_support)
                L.append(l)
                # print("Frequent %d item" % (k))
                # print(l)
                k = k + 1
                ck, final_ck = apriori_generate(L[k - 1], k)
                # print("C%d" % (k))
                # print(final_ck)
            break
        k_subsets = generate_k_subsets(Transaction1,k)                  #生成事物子集
        for subset in k_subsets:
            h_tree.add_support(subset)                                  #像hash树的项集添加支持数
        lk = []
        h_tree.get_frequent_itemsets(h_tree.root,min_support,lk)                  #获取频繁项集
        # print("Frequent %d item" %(k))
        # print(lk)
        L.append(lk)
        k = k + 1
    end = time.time()
    return L,(end-start)

L_value,time_taken = apriori(values,min_support)
#print("final L_value")
#print(L_value)
print("All frequent itemsets with their support count:")
print(Frequent_items_value)

到了这里，关于数据挖掘与机器学习：Apripori算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！