Educoder-候选生成Apriori算法

任务描述

本关任务：编写一个能实现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集合。

根据提示，在右侧编辑器补充代码，生成候选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个元素相同的项
                # 数据集列表里面的lk_list[i]单个元素，不是列表类型转化
                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 Ck_item not in Ck:
                        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))