区块链 人工智能

使用Apriori算法进行关联分析

Apriori 算法

引言:数据挖掘与机器学习

有时候,人们会对机器学习与数据挖掘这两个名词感到困惑。如果你翻开一本冠以机器学习之名的教科书,再同时翻开一本名叫数据挖掘的教材,你会发现二者之间有相当多重合的内容。比如机器学习中也会讲到决策树和支持向量机,而数据挖掘的书里也必然要在决策树和支持向量机上花费相当的篇幅。可见二者确有相当大的重合面,但如果细研究起来,二者也的确是各自不同的领域。

大体上看,数据挖掘可以视为数据库、机器学习和统计学三者的交叉。简单来说,对数据挖掘而言,数据库提供了数据管理技术,而机器学习和统计学则提供了数据分析技术。所以你可以认为数据挖掘包含了机器学习,或者说机器学习是数据挖掘的弹药库中一类相当庞大的弹药集。既然是一类弹药,其实也就是在说数据挖掘中肯定还有其他非机器学习范畴的技术存在。Apriori算法就属于一种非机器学习的数据挖掘技术。

我们都知道数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 而机器学习是以数据为基础,设法构建或训练出一个模型,进而利用这个模型来实现数据分析的一类技术。这个被训练出来的机器学习模型当然也可以认为是我们从数据中挖掘出来的那些潜在的、有意义的信息和知识。在非机器学习的数据挖掘技术中,我们并不会去建立这样一个模型,而是直接从原数据集入手,设法分析出隐匿在数据背后的某些信息或知识。在后续介绍Apriori算法时,你会相当明显地感受到这一特点。

apriori 在拉丁语中指 “来自以前”。当定义问题时,通常会使用先验知识或者假设,这被称作 “一个先验” (a priori)。在贝叶斯统计中,使用先验知识作为条件进行推断常见。先验知识可能来自领域知识,先前的一些测量结果,等等。

Apriori定律

  • Apriori定律1: 如果一个集合是频繁项集,则它的所有子集都是频繁项集。

    例如:假设一个集合{A,B}是频繁项集,即A、B同时出现在一条记录的次数大于等于最小支持度min_support,则它的子集{A},{B}出现次数必定大于等于min_support,即它的子集都是频繁项集。

  • Apriori定律2: 如果一个集合不是频繁项集,则它的所有超集都不是频繁项集。

    例如:假设集合{A}不是频繁项集,即A出现的次数小于 min_support,则它的任何超集如{A,B}出现的次数必定小于min_support,因此其超集必定也不是频繁项集。

示例代码

总结

每次增加频繁项集的大小,Apriori算法都会重新扫描整个数据集。当数据集很大时,这会显著降低止频繁项集发现的速度。

下一章将会介绍 FP-growth算法,与Apriori算法相比,该算法只需要对数据进行两次遍历,能显著加快发现频繁项集的速度。

参考: