Apriori算法的Python实现

Apriori算法是数据挖掘中频发模式挖掘的鼻祖,从60年代就开始流行,其算法思想也十分简单朴素,首先挖掘出长度为1的频繁模式,然后k=2

将这些频繁模式合并组成长度为k的频繁模式,算出它们的频繁次数,而且要保证其所有k-1长度的子集也是频繁的,值得注意的是,为了避免重复,合并的时候,只合并那些前k-2个字符都相同,而k-1的字符一边是少于另一边的。

以下是算法的Python实现:

__author__ = 'linfuyuan'
min_frequency = int(raw_input('please input min_frequency:'))
file_name = raw_input('please input the transaction file:')
transactions = []


def has_infrequent_subset(candidate, Lk):
    for i in range(len(candidate)):
        subset = candidate[:-1]
        subset.sort()
        if not ''.join(subset) in Lk:
            return False
        lastitem = candidate.pop()
        candidate.insert(0, lastitem)
    return True


def countFrequency(candidate, transactions):
    count = 0
    for transaction in transactions:
        if transaction.issuperset(candidate):
            count += 1
    return count


with open(file_name) as f:
    for line in f.readlines():
        line = line.strip()
        tokens = line.split(',')
        if len(tokens) > 0:
            transaction = set(tokens)
            transactions.append(transaction)
currentFrequencySet = {}
for transaction in transactions:
    for item in transaction:
        time = currentFrequencySet.get(item, 0)
        currentFrequencySet[item] = time + 1
Lk = set()
for (itemset, count) in currentFrequencySet.items():
    if count >= min_frequency:
        Lk.add(itemset)
print ', '.join(Lk)

while len(Lk) > 0:
    newLk = set()
    for itemset1 in Lk:
        for itemset2 in Lk:
            cancombine = True
            for i in range(len(itemset1)):
                if i < len(itemset1) - 1:
                    cancombine = itemset1[i] == itemset2[i]
                    if not cancombine:
                        break
                else:
                    cancombine = itemset1[i] < itemset2[i]
                    if not cancombine:
                        break
            if cancombine:
                newitemset = []
                for char in itemset1:
                    newitemset.append(char)
                newitemset.append(itemset2[-1])
                if has_infrequent_subset(newitemset, Lk) and countFrequency(newitemset, transactions) >= min_frequency:
                    newLk.add(''.join(newitemset))
    print ', '.join(newLk)
    Lk = newLk

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源优测

Python3插入排序

Python3插入排序 前言 为什么要开始写Python3算法系列呢? 一是很长很长时间没专门练习练习这种基本功 二是想把这个系列以基本代码的方式给写出来,提...

27360
来自专栏算法修养

pta习题集5-16 朋友圈

某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我...

33870
来自专栏ACM算法日常

I'm Telling the Truth(二分图)- HDU 3729

二分图:设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点...

9540
来自专栏Petrichor的专栏

pytorch: tensor类型的构建与相互转换

其中,torch.Tensor、torch.rand、torch.randn 均默认生成 torch.FloatTensor型 :

25260
来自专栏移动开发面面观

排序备忘

排序是算法的一项基础能力,也是面试必考题。如何写一个恰当的排序,也是一个软件工程师的基本必备技能。

7610
来自专栏程序员互动联盟

到底能不能越过C直接学C++?

现在有好多人都比较迷茫,学习C++是不是需要先学习C语言? 其实这个问题不难,就是直接了解两者的联系和区别就可以给出答案。下面我们来看看他俩到底有什么关系。 ?...

45540
来自专栏怀英的自我修炼

怀英漫谈2-JS语法初涉

今天碰了一下JS的语法,想与你聊聊这个。这篇文章适合前端设计师,不过在文末,我也为你准备了一些感悟,有兴趣的不妨跳到最后一看。 总体来看,JS的语法和Java的...

383100
来自专栏我是业余自学C/C++的

redis_3.0.7_sds.h_sdslen()

21830
来自专栏算法修养

一道数据处理的算法题

有一份5000万个用户的数据,有一份2亿个用户看电影的记录。只有1G的内存,找到看电影最多的前1000个用户? 应该怎么做呢? 我一开始的想法,哎呀,快速排序!...

36560
来自专栏用户2442861的专栏

求两个等长有序数组的中位数的logN算法 分治法

http://blog.csdn.net/yangliuy/article/details/7194199

62320

扫码关注云+社区

领取腾讯云代金券