频繁项集挖掘算法

① 关联算法

关联, 指的是关联分析, 这里引用网络的定义.

通过关联分析, 可以挖掘出"由于某些事件的发生而引起另外一些事件的发生"之类的规则, 比如说"面包=>牛奶", 其中面包被称为规则的前项, 而牛奶则被称为规则的后项.

常用于关联分析的算法有Apriori算法, FP-growth算法, Eclat算法, 灰色关联法等, 下面将着重介绍Apriori算法.

在介绍Apriori算法之前, 我们先来了解几个概念:
1.事务: 一条交易记录称为一个事务
2.项: 交易中的每一个物品称为一个项
3.项集: 包含0个或多个项的集合
4.支持度计数: 项集在所有事务中出现的次数.
5.支持度: 支持度计数除于总的事务数.
6.频繁项集: 支持度大于等于某个阀值的项集.

关联规则的挖掘通常分为两步: 第一步, 找出所有的频繁项集; 第二步, 由频繁项集产没判答生强关联规则. 而Apriori算法则是挖掘频繁项集的基本算法.

可以看到以上每个过程均需要扫描一次数据, 为了提高频繁项集逐层迭代产生的效率, 需要利用一条重要性质, 其称为先验性质:

当然, 非频繁项集的所有超集也一定是非频繁的.

将先验性质应用到Apriori算法中就是将之枯慧前的过程分为两大部分, 连接步和剪枝步.
连接步: 连接步的目的是产生候选项集.
剪枝步: 应用先验性质对候选项集进行筛选, 将不满足先验性质的候选项集剔除, 再进而根据最小支持度找出频繁项集, 这样可以有效缩短计算量.

关联分析的目标是找出强关联规则, 因此这里的关联规则是指强关联规则, 我们把满足最小支持度和最小置信度的规则称为强关联规则.
对于规则A=>冲敏B, 置信度的计算公式就是项集{A, B}的支持度计数除于项集{A}的支持度计数.

优点: 简单, 易理解, 对数据要求低
缺点: 容易产生过多的候选项集, I/O负载大.

② 带你了解数据挖掘中的经典算法

数据挖掘的算法有很多，而不同的算法有着不同的优点，同时也发挥着不同的作用。可以这么说，算法在数据挖掘中做出了极大的贡献，如果我们要了解数据挖掘的话就不得不了解这些算法，下面我们就继续给大家介绍一下有关数据挖掘的算法知识。
1.The Apriori algorithm，
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。这个算法是比较复杂的，但也是十分实用的。
2.最大期望算法
在统计计算中，最大期望算法是在概率模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量。最大期望经常用在机器学习和计算机视觉的数据集聚领域。而最大期望算法在数据挖掘以及统计中都是十分常见的。
3.PageRank算法
PageRank是Google算法的重要内容。PageRank里的page不是指网页，而是创始人的名字，即这个等级方法是以佩奇来命名的。PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”，这个标准就是衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。
3.AdaBoost算法
Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器，然后把这些弱分类器集合起来，构成一个更强的最终分类器。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。这种算法给数据挖掘工作解决了不少的问题。
数据挖掘算法有很多，这篇文章中我们给大家介绍的算法都是十分经典的算法，相信大家一定可以从中得到有价值的信息。需要告诉大家的是，我们在进行数据挖掘工作之前一定要事先掌握好数据挖掘需呀掌握的各类算法，这样我们才能在工总中得心应手，如果基础不牢固，那么我们迟早是会被淘汰的。职场如战场，我们一定要全力以赴。

③ 利用Apriori算法产生频繁项集,(min sup=0.6),给出具体计算过程

Apriori算法是一种发现频繁项集的基本算法。算法使用频繁项集性质的先验知识。Apriori算法使用一种称为逐层搜索的迭代方法，其中K项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1.然后，使用L1找出频繁2项集的集合L2，使用L2找到L3，如此下去，直到不能再找到频繁k项集。Apriori算法的主要步骤如下：(1)扫描事务数据库中的每个事务，产生候选1．项集的集合Cl；(2)根据最小支持度min_sup，由候选l-项集的集合Cl产生频繁1一项集的集合Ll；(3)对k=l；(4)由Lk执行连接和剪枝操作，产生候选(k+1)．项集的集合Ck+l-(5)根据最小支持度min_sup，由候选(k+1)一项集的集合Ck+l产生频繁(k+1)-项集的集合Lk+1．(6)若L?≠①，则k．k+1，跳往步骤(4)；否则，跳往步骤(7)；(7)根据最小置信度min_conf,由频繁项集产生强关联规则，结束。

④ 数据挖掘的十大经典算法，总算是讲清楚了，想提升自己的赶快收藏

一个优秀的数据分析师，除了要掌握基本的统计学、数据分析思维、数据分析工具之外，还需要掌握基本的数据挖掘思想，帮助我们挖掘出有价值的数据，这也是数据分析专家和一般数据分析师的差距所在。

国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.

不仅仅是选中的十大算法，其实参加评选的18种算法，实际上随便拿出一种来都可以称得上是经典算法，它们在数据挖掘领域都产生了极为深远的影响。今天主要分享其中10种经典算法，内容较干，建议收藏备用学习。

1. C4.5

C4.5算法是机器学习算法中的一种分类决策树算法,其核心算法是ID3算法. C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效（相对的CART算法只需要扫描两次数据集，以下仅为决策树优缺点）。

2. The k-means algorithm 即K-Means算法

k-means algorithm算法是一个聚类算法，把n的对象根据他们的属性分为k个分割，k < n。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均 方误差总和最小。

3. Support vector machines

支持向量机，英文为Support Vector Machine，简称SV机（论文中一般简称SVM）。它是一种监督式学习的方法，它广泛的应用于统计分类以及回归分析中。支持向量机将向量映射到一个更 高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。一个极好的指南是C.J.C Burges的《模式识别支持向量机指南》。van der Walt 和 Barnard 将支持向量机和其他分类器进行了比较。

4. The Apriori algorithm

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。

5. 最大期望(EM)算法

在统计计算中，最大期望（EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然 估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

6. PageRank

PageRank是Google算法的重要内容。2001年9月被授予美国专利，专利人是Google创始人之一拉里·佩奇（Larry Page）。因此，PageRank里的page不是指网页，而是指佩奇，即这个等级方法是以佩奇来命名的。

PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票， 被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自 学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。

7. AdaBoost

Adaboost是一种迭代算法，其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器 (强分类器)。其算法本身是通过改变数据分布来实现的，它根据每次训练集之中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权 值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。

8. kNN: k-nearest neighbor classification

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

9. Naive Bayes

在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。

同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。 但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属 性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

10. CART: 分类与回归树

CART, Classification and Regression Trees。 在分类树下面有两个关键的思想。第一个是关于递归地划分自变量空间的想法（二元切分法）；第二个想法是用验证数据进行剪枝（预剪枝、后剪枝）。在回归树的基础上的模型树构建难度可能增加了，但同时其分类效果也有提升。

参考书籍：《机器学习实战》

⑤ 关联规则挖掘算法的介绍

学号：17020110019    姓名：高少魁

【嵌牛导读】关联规则挖掘算法是数据挖掘中的一种常用算法，用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。这里将对该算法进行简单的介绍，之后通过Apriori算法作为实例演示算法执行结果。

【嵌牛鼻子】数据挖掘    关联规则挖掘    python

【嵌牛正文】

一、算法原理

1、基本概念

关联规则用于发现隐藏在大型数据集中令人感兴趣的频繁出现的模式、关联和相关性。 而 Apriori算法则是经典的挖掘频繁项集的关联规则算法，它通过层层迭代来寻找频繁项集，最后输出关联规则：首先扫描数据集，得到 1-频繁项集，记为 L1，通过合并 L1得到 2-频繁项集 L2，再通过 L2找到 L3，如此层层迭代，直到找不到频繁项集为止。

在Apriori算法中，定义了如下几个概念：

⚫ 项与项集 ：设 I={i1,i2,…,im}是由 m个不同项构成的集合，其中的每个 ik(k=1,2,…,m)被称为一个项 (Item)，项的集合 I被称为项集和，即项集。在实验中，每一条购物记录可以被看做 一个项集，用户购买的某个商品即为一个项。

⚫ 事务与事务集：神乎事务 T是项集 I的一个子集，而事务的全体被称为事务集。

⚫ 关联规则：形如 A=>B的表达式，其中， A和 B都属于项集 I，且 A与 B不相交。

⚫ 支持度：定义如下 support(A=>B) = P(A B)，即 A和 B所含的项在事务集中同时出现的概率。

⚫ 置信度：定义如下 confidence(A⇒B)=support(A⇒B)/support(A)=P(A B)/P(A)=P(B|A)，即如果事务包含 A，则事务中同时出现 B的概率。

⚫ 频繁项集：如果项集 I的支持度满足事先定义好的最小支持度阈慧液值（即 I的出现频度大于相应的最小出现频度阈值），则 I是频繁项集。

⚫ 强关联规则：满足最小支持度和最小置信度的关联规则，即待挖掘的关联规则。

根据以上概念，要实现关联规则的挖掘，首先要找到所有的频繁项集，之后找出强关联规则（即通过多次扫描数据集，找出频繁集，然后产生关联规则）。

2、挖掘频繁项集

在该步骤中有两个较为重要的部分 ：连接和修剪。连接步骤即使用k-1频繁项集，通过连接得到 k-候选项集，并且只有相差一个项的项集才能进行连接，如 {A,B}和 {B,C}连接成为 {A,B,C}。修剪步骤基于一个性质：一个 k-项集，如果它的一个 k-1项集（子集）不是频繁的，那么它本身也不可能是频繁的。 因此可以基于这个性质，通过判断先验性质来对候选集进行修剪。

3、产生关联规则

经过连接和修剪之后，即找到了所有的频繁项集，此时可以在此基础上产生关联规则，步骤如下

（1）对于每个频繁项集 l，产生 l的所有非空子集（这些非空子集一定是频繁项集）；

（2）对于 l的每一个非空子集 x，计算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那么规则 x => (l-x)”成立。

二、算法设计

1、数据集

通过语句 import xlrd导入相关的库来进行数据的读取 。数据内容为十条购物记录 ，每条购物记录有若干个商品，表示某个顾客的购买记录 ，如图

对于数据加载部分 使用了 xlrd库中的函数 open_workbook来 打开一个表格文件，使用sheet_by_index函数得到一个工作表， row_values函数即可读取表格中的内容。由于每个购物记录的商品数不一定相同，导致读取的内容含有空格 (’ ’)，因此对数据进行删减以得到紧凑的数据 ，最终读取数据的结果以列表的游碧悉形式返回。

2、连接

对于连接部分，主要目标是根据已有的k-1频繁项集生成 k-候选频繁项集。算法步骤为：首先将项集中的项按照字典顺序排序，之后将 k-1项集中两个项作比较，如果两个项集中前 k-2个项是相同的，则可以通过或运算（|）将它们连接起来。

3、修剪

修剪操作主要使用一个判断函数，通过传入连接操作后的项集和之前的k-1频繁项集，对新的项集中的每一个项的补集进行判断，如果该补集不是 k-1频繁项集的子集，则证明新的项集不满足先验性质，即一个频繁项集的所有非空子集一定是频繁的 ，否则就满足先验形式。返回布尔类型的参数来供调用它的函数作判断。

经过连接和修剪步骤之后，项基要成为频繁项集还必须满足最小支持度的条件，笔者设计了generateFrequentItems函数来对连接、修剪后产生的 k-候选项集进行判断，通过遍历数据集，计算其支持度，满足最小支持度的项集即是 一个频繁项集，可将其返回。

以上，经过不断的遍历、连接、修剪、删除，可将得到的所有结果以列表形式返回。笔者还设计了字典类型的变量 support_data，以得到某个频繁项集及其支持度 。

4、挖掘关联规则

generateRules函数用来挖掘关联规则，通过传入 最小置信度、 频繁项集及其 支持度来生成规则 。根据定理：对于频繁项集 l的每一个非空子集 x，计算 confidence(x => (l-x))，如果 confidence(x => (l-x)) confmin，那么规则 x => (l-x)”成立，因此，该函数重点在扫描频繁项集，得到每一个子集，并计算置信度，当置信度满足条件（即大于等于最小置信度）时，生成一条规则。在函数中，使用了元组来表示一条规则，元组中包含 x、 l-x以及其置信度 ，最后返回生成的所有规则的列表。

三、算法执行结果

设置最大频繁项集数k为 3，最小支持度为 0.2，最小置信度为 0.8 使用 pycharm运行程序 ，得到以下结果：

由图中结果可以看出，对于频繁 1-项集，有五个满足的项集，频繁 2-项集有 6个，频繁 3-项集有 2个，它们都满足支持度大于或等于最小支持度 0.2。根据频繁项集，程序得到的关联规则有三条，即 {面包 }=>{牛奶 }，，{鸡蛋 }=>{牛奶 }，，{面包，苹果 }=>{牛奶 其中，这些规则的置信度都是 1.0，满足大于或等于最小置信度 0.8的条件 。

四、程序源码