算法的优点关联分析

① 关联分析 分析在哪些情况下，一种算法比其他算法好

灰色关联度分析法是一种多因素统计分析方法，它是以各因素的样本数据为依据用灰色关联度来描述因素间关系的强弱、大小和次序，若样本数据反映出的两因素变化的态势(方向、大小和速度等)基本一致，则它们之间的关联度较大

② 关联分析的关联分析的方法

Apriori算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最着名的关联规则挖掘算法之一。Apriori算法就是根据有关频繁项集特性的先验知识而命名的。它使用一种称作逐层搜索的迭代方法，k—项集用于探索（k+1）—项集。首先，找出频繁1—项集的集合．记做L1，L1用于找出频繁2—项集的集合L2，再用于找出L3，如此下去，直到不能找到频繁k—项集。找每个Lk需要扫描一次数据库。
为提高按层次搜索并产生相应频繁项集的处理效率，Apriori算法利用了一个重要性质，并应用Apriori性质来帮助有效缩小频繁项集的搜索空间。
Apriori性质：一个频繁项集的任一子集也应该是频繁项集。证明根据定义，若一个项集I不满足最小支持度阈值min_sup，则I不是频繁的，即P（I）<min_sup。若增加一个项A到项集I中，则结果新项集（I∪A）也不是频繁的，在整个事务数据库中所出现的次数也不可能多于原项集I出现的次数，因此P（I∪A）<min_sup，即（I∪A）也不是频繁的。这样就可以根据逆反公理很容易地确定Apriori性质成立。
针对Apriori算法的不足，对其进行优化：
1）基于划分的方法。该算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可能的频繁项集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频繁项集至少在某一个分块中是频繁项集保证的。
上面所讨论的算法是可以高度并行的。可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每一个循环结束后．处理器之间进行通信来产生全局的候选是一项集。通常这里的通信过程是算法执行时间的主要瓶颈。而另一方面，每个独立的处理器生成频繁项集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个杂凑树来产生频繁项集，更多关于生成频繁项集的并行化方法可以在其中找到。
2）基于Hash的方法。Park等人提出了一个高效地产生频繁项集的基于杂凑（Hash）的算法。通过实验可以发现，寻找频繁项集的主要计算是在生成频繁2—项集Lk上，Park等就是利用这个性质引入杂凑技术来改进产生频繁2—项集的方法。
3）基于采样的方法。基于前一遍扫描得到的信息，对它详细地做组合分析，可以得到一个改进的算法，其基本思想是：先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。这个算法相当简单并显着地减少了FO代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲（Dataskew）。分布在同一页面上的数据时常是高度相关的，不能表示整个数据库中模式的分布，由此而导致的是采样5%的交易数据所花费的代价同扫描一遍数据库相近。
4）减少交易个数。减少用于未来扫描事务集的大小，基本原理就是当一个事务不包含长度为志的大项集时，则必然不包含长度为走k+1的大项集。从而可以将这些事务删除，在下一遍扫描中就可以减少要进行扫描的事务集的个数。这就是AprioriTid的基本思想。 由于Apriori方法的固有缺陷．即使进行了优化，其效率也仍然不能令人满意。2000年，Han Jiawei等人提出了基于频繁模式树（Frequent Pattern Tree，简称为FP-tree）的发现频繁模式的算法FP-growth。在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP—tree中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。

③ 遗传算法的优缺点

优点：

1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行操作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传操作算子的运用。

另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。

2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。

3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。

另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。

4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。

5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。

缺点：

1、遗传算法在进行编码时容易出现不规范不准确的问题。

2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。

3、遗传算法效率通常低于其他传统的优化方法。

4、遗传算法容易出现过早收敛的问题。

(3)算法的优点关联分析扩展阅读

遗传算法的机理相对复杂，在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法。

函数ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。

为了设置options，需要用到下面这个函数：options=gaoptimset('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', ...)通过这个函数就能够实现对部分遗传算法的参数的设置。

④ 关联算法

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

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

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

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

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

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

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

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

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

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

⑤ 数据挖掘- 关联分析算法

关联分析，顾名思义就是找出哪几项之间是有关联关系的，举个例子：

以上是五个购物记录，从中我们可以发现，购买了尿布的人其中有3个购买了啤酒，那么久我们可以推测，尿布和啤酒之间有较强的关联关系，尽管他们之间看起来并没有什么联系，也就是能得到规则：

因为购物分析能较好地描述关联分析，所以又被叫做 购物篮分析 。
为了较好的描述这个分析的各种名词，我们把上面的表格重新设计一下：

把每一个购物订单中，涉及到的商品都变成1，没涉及到的变成0，也就是将各个商品的购买记录 二元化 。
当然肯定也有多个分类的情况。

那么面包，牛奶这些就叫数据集的 项 ，而他们组合起来的子集就叫做 项集 。可以为空，空集是不包含任何项的项集，如果一个项集包含k个子项，就叫做k-项集。
订单12345叫做 事务 ，某个项集在所有事务中出现多少次，叫做项集的 支持度计数 。

在上面的表格中，项集{啤酒、尿布、牛奶}的支持度计数为2，因为有两个事务（3、4）包含这一项集。

用 支持度 和 置信度 来衡量，假定存在规则 ，其中X和Y是 不相交 的项集，则支持度为：
其中N是数据集中的事务个数，相当于表示该规则在数据集中出现了多少次。
置信度为：

置信度的意思就是，在出现X的情况下，有多少次同时出现了Y，代表这个关联规则的频繁程度。

注意置信度的分母是 ，因此这个评价可能会存在一定的问题。

关联分析的核心目标就是找出支持度大于等于某个阈值， 同时 置信度大于等于某个阈值的所有规则，这两个阈值记为 和 。

为了更有效率的完成这个过程，通常把关联规则算法分为两步：

可以看出来，樱备首先要求得频繁项集，这步骤的开销很大，但是只需要考虑支持度就可以了，第二步只考虑置信度就可以了。

下面就可以分两步来解析算法：

首先我们可以把项集联想成一个树形结构，每层代表着不同的k-项集，依层递增，非叶子节点来自于他的几个父节点的并集，如图：

我们肯定不能通过传统的方式，遍历这些节点，算出支持度，然后筛选掉不满足最小支持度的那些，这样开销太大，因此我们引入先验原理，来辅助剪枝。

这个原理不难想象，假如一个项集{a,b}是非频繁项集，那么{a,b,c}肯定也是，因为ab是，在{a,b,c}中与之关联的c必须在ab出现之后才存在，因此他的支持度肯定不会大于{a,b}。

频繁的就是支持度大于等于最小支持度的项集，非频繁就是小于的。

我们可以利用这一定理，把非频繁项集的超集一并从树中减去，这样就能大大的降低计算次数，如图：

虚线圈上的，就是在{a,b}确定是非频繁项集之后，剪掉的超集，这些是不用计算的。

根据这个原理，可以说一下Apriori算法。

根据上面说的先验原理，Apriori算法先从项集宽度最低的1开始，遍历所有的项集支持度，找出频繁项集（因为第一层在找出支持度之前），之后根据先验原理，挑选任意两个频繁项集组成2-频繁项集（很简单，如果挑非频繁的，那组成的项集就不是频繁项集了），再用2-项集挑选3-项集，直到挑选不出更高层次的项集为止，把这些项集作为 候选项集 ，如图：

图中1-项集中，啤酒，面包，尿布，牛奶的支持度大于等于3（设 为3），则由他们组成2-项集，继续筛选满足支持度不小于3的项集，再由2-项集生成3-项集，这就是 Apriori 算法筛选频繁项集的基本步骤。总结如下：

上面提到了用k-1项集生成k-项脊稿毁集，那么如何才能最有效率的产生k-项集呢，这里用了 的方法，也就是找到一对（k-1）-项集，当他们的前（k-2）项都相同时，进行合并，合并之后的结果就是{ }，因为前k-2项是相同的。
举个例子：

上面说了如何产生候选项集，接下来就是如何更敬尘有效率的确定支持度计数了，同样，如果遍历一个一个查的话效率是很低的，我们可以用枚举的方法遍历每个事务包含的项集，以查找3-项集为例，如图：

因为我们要查3-项集，因此树状结构就分到3-项集为止。
因为3-项集的开头第一个项肯定在1，2，3之间，我们就设定这三个数为三个分支，无论到哪个节点，都严格按照这个来分（1在左，2在中，3在右），在下面的层次中如何碰到比123更大的，则再向右分，就可以得到图中的关于事务t的所有3-项集。

有了所有项集的列表，我们可以用候选项集去匹配这些项集，从而看t中是否包含候选项集，如果包含，则支持度+1。

可以使用Hash树来进行匹配，从而实现支持度计数。
如下图，就是一个Hash树的例子，每个内部节点都使用Hash函数 来确定应当沿着当前节点的哪个分支向下，所以1，4，7就到了同一分支。

我们对于单个事务，可以遍历Hash树，设事务为t，则保证所有包含属于事务t的候选3-项集的叶节点至少访问一次。

由于我们之前已经通过树的方式枚举出了t中所有的3-项集，那么我们跟这个Hash一走分支，找到对应3-项集的就+1支持度，即可算出每个候选项集的支持度。

提取规则相应的比较简单，设有 频繁项集Y ，我们忽略前件为空和后件为空的规则，每个频繁项集能产生 个关联规则，提取方法就是将Y划分为两个 非空 的子集X和Y-X，使得 满足 置信度阈值 也就是最小置信度。

同样的，提取规则也有一个原理：

参考频繁项集的寻找过程，我们可以利用树形结构对规则进行剪枝。
树的每层对应规则后件中的项数，如图：

假设规则{ } { }不满足置信度阈值的要求，那么可以丢弃后件包含{a}的所有规则，如上图所示。

至此我们经历了寻找频繁项集和提取规则的过程，基本Apriori算法就算完成了，不过还有一些需要考虑的细节。

在实际应用过程中，往往频繁项集产生的数量可能很大，所以很难表示，我们需要寻找一种方法，找到一些有代表性的频繁项集，以保证其描述性。

通常有如下两种方法：

如图：

这种表示很明显降低了需要表示项集的个数，我们需要别的候选项集，直接取极大频繁项集的子集就行，任意一个肯定都是。

但是这么做，表示不出他们子集的支持度，所以就需要再遍历数据集，确定非极大频繁项集的支持度，不是很方便。

所以我们还可以用闭频繁项集来表示。

先来看闭项集的概念：

那么闭频繁项集的概念就很好理解了：

如图，我们假设 是40%。

这种做法可以保证支持度和描述性。

之前举的例子都是二元分类的，要么1要么0，下面看多分类的，我们很容易想到可以用独热编码解决这个问题，把所有分类二元化，但是这样就存在一个问题，有的属性值可能会不够频繁，没办法成为频繁项集。
所以最好是把多分类的项根据实际情况进行分类化，不要针对每个属性都设置独热编码。

或者将不太频繁的属性值合并为一个称作其他的类别。

所以面对多分类属性，我们要做的就是：
独热编码二元化-针对这些值进行一定的合并，或者分类或者并为其他 - 删除冗余的项 - 避免包含多个来自同一属性的项的候选集（例如{ }，被写到了一个候选集中，但是实际上这种情况不可能发生，由于独热编码进行的二元化而产生了这种情况，需要避免。）

我们也会遇到一些连续属性，可以通过以下几种方式处理：

这种做法有一个问题就是分类的效果取决于区间的个数和跨度，如果取不好很难得到理想的结果。

如果要验证统计出的值是否具有统计意义，可以参考假设检验中针对不同比较的不同公式，这里不再举例。

把mini-Apriori算法中的支持度代入到Apriori算法的支持度中即可。

举个例子：

想要衡量模型的好与坏，肯定要有一个评估指标，我们可以根据业务实际去评价，这是主管评价，叫做 主观兴趣度度量 ，这个显然要结合业务，所以我们要看看一些客观指标。

指标的评价往往依赖于相依表，这个相依表有点类似于混淆矩阵：

其中A，B代表在事务中出现，!A,!B代表没有在事务中出现，空列空行例如 代表A的支持度计数， 表示包含B但是不包含A的事务的个数。

最基本的就是置信度和支持度了，但是这两种指标都很难做到客观评价模型，会受到多种因素的影响。

我们可以用 兴趣因子 来衡量模型：
首先我们引入 提升度 的概念，它用于计算规则置信度和 规则后件 中项集的支持度之间的比率，

对于二元变量，提升度等价于另一种称作兴趣因子的客观度量，定义为：
其中N是事务个数。
如果

但是兴趣因子有一定局限性，看上图，{p,q}和{r,s}的兴趣因子分别为1.02和4.08，虽然p和q同时出现在88%的文档中，但是他们的兴趣因子接近于1，表明他们相互独立，另一方面，{r,s}的兴趣因子闭{p,q}的高，但是r和s很少出现在一个文档中，这种情况下，置信度要比兴趣因子更可信，置信度表明p和q之间的联系94.6%远高于r和s之间。

另外还可以引入 相关系数 ，逻辑类似于向量的相关系数：

相关度的值从-1到1，如果变量相互独立，则Φ=0。

他的局限性在于在食物中把同时出现和同时不出现视为同等重要，这往往不符合实际规律，同时对于倾斜的变量很难度量。

IS度量 可以用于处理非对称二元变量，定义如下：
IS数学上等价于二元变量的余弦度量。
但是IS取决于A和B的支持度，所以存在与置信度度量类似的问题——即使是不相关或者负相关的模式，度量值也可能相当大。

支持度，全置信度，可以应用于较大的项集，兴趣因子，IS、PS、Jaccard系数等使用多维相依表中的频率，可以扩展到多个变量。

针对大多数项具有较低或中等的频率，但是少数项具有很高频率的数据集。

交叉支持模式是一个项集 ，他的支持度比率是：
小于用户指定的阈值 。

需要保证全置信度小于上面的支持度比率，而全置信度是：
其中 .

全置信度能够确保项集中的项之间是强关联的，例如，假定一个项集X的全置信度是80%，如果X中的一个项出现在某个事物中，则X中其他的项至少也有80%的几率属于同一个事务，这种强关联模式又称 超团模式 。

⑥ 举例说明何谓算法,特点是什么评价一个算法的优劣,主要从哪些因素分析

评价算法优劣的四个分析因素：

1.正确性

能正确地实现预定的功能，满足具体问题的需要。处理数据使用的算法是否得当，能不能得到预想的结果。

2.易读性

易于阅读、理解和交流，便于调试、修改和扩充。写出的算法，能不能让别人看明白，能不能让别人明白算法的逻辑？如果通俗易懂，在系统调试和修改或者功能扩充的时候，使系统维护更为便捷。

3.健壮性

输入非法数据，算法也能适当地做出反应后进行处理，不会产生预料不到的运行结果。数据的形式多种多样，算法可能面临着接受各种各样的数据，当算法接收到不适合算法处理的数据，算法本身该如何处理呢？如果算法能够处理异常数据，处理能力越强，健壮性越好。

4.时空性

算法的时空性是该算法的时间性能和空间性能。主要是说算法在执行过程中的时间长短和空间占用多少问题。

算法处理数据过程中，不同的算法耗费的时间和内存空间是不同的。

(6)算法的优点关联分析扩展阅读：

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要的特性。

（1）、有穷性

一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。

（2）、确定性

算法中每一条指令必须有明确的含义，读者理解时不会产生二义性。即对于相同的输入只能得到相同的输出。

（3）、可行性

一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

（4）、输入

一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。

（5）、输出

一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

⑦ 最小二乘法、回归分析法、灰色预测法、决策论、神经网络等5个算法的使用范围及优缺点是什么

最小二乘法：通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。优点：实现简单，计算简单。缺点：不能拟合非线性数据.
回归分析法：指的是确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。在大数据分析中，回归分析是一种预测性的建模技术，它研究的是因变量（目标）和自变量（预测器）之间的关系。这种技术通常用于预测分析，时间序列模型以及发现变量之间的因果关系。优点：在分析多因素模型时，更加简单和方便，不仅可以预测并求出函数，还可以自己对结果进行残差的检验，检验模型的精度。缺点：回归方程式只是一种推测，这影响了因子的多样性和某些因子的不可测性，使得回归分析在某些情况下受到限制。
灰色预测法：
色预测法是一种对含有不确定因素的系统进行预测的方法 。它通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。它用等时间距离观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或者达到某一特征量的时间。优点：对于不确定因素的复杂系统预测效果较好，且所需样本数据较小。缺点：基于指数率的预测没有考虑系统的随机性，中长期预测精度较差。
决策树：在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。优点：能够处理不相关的特征；在相对短的时间内能够对大型数据源做出可行且效果良好的分析；计算简单，易于理解，可解释性强；比较适合处理有缺失属性的样本。缺点：忽略了数据之间的相关性；容易发生过拟合（随机森林可以很大程度上减少过拟合）；在决策树当中,对于各类别样本数量不一致的数据，信息增益的结果偏向于那些具有更多数值的特征。
神经网络：优点：分类的准确度高；并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系；具备联想记忆的功能。缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。

⑧ 最大最小距离算法的优缺点

该算法的优缺点如下：
1、最大最小距离算法的优点是算法实现简单，处理大数据集的能力较强。
2、缺点是最大最小御锋拦距离算法对噪音数据敏感，在存在噪音数据的情况下，聚类中基圆心可能偏移真正的类别中心较远。
最大最小距离又称基于路径的距离，由Fischer首先应用于聚类中。由于簇是由它们的凝聚性定义的，所以人们更关注穿过高密度区域数据对象的路径。因此，路径中密度最低的部分应该决定该路径的总体成本。换句话说，沿着一条路径的最大不同决定了它的代价。最大最小距离是镇胡一种度量，它包含了一个数据集的基础全局几何。

⑨ Arnoldi算法的优缺点

1.优点：适合稀疏数据集。算法原理简单，易实现。适合事务数据库的关联规则挖掘。2.缺点：可能产生庞大的候选集。算法需多次遍历数据集，算法效率低，耗时。
Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

⑩ 第九章 数据关联规则分析算法——基于Apriori算法的关联项分析

9.1 基于Apriori算法的关联分析

Aprior算法是关联规则分析中较为经典的频繁项集算法。关联规则反映的是两个或多个事物相互之间的依存性和关联性。如果两个或者多个事物相互之间存在一定的关联关系，则它们之间存在一种关联规则使得它们之间可以进行搭配。

9.1.1 基本概要

Apriori算法利用频繁项集的先验知识，不断地按照层次进行迭代，计算数据集中的所有可能的频繁项集，它的分析主要包括两个核心部分。

1、根据支持度找出频繁项集；

2、根据置信度产生关联规则。

9.1.2 Apriori算法原理

基本流程：

1、扫描历史数据，并对每项数据进行频率次数统计。

2、构建候选集 ，并计算其支持度，即数据出现频率次数与总数的比。

3、对候选项集进行筛选，筛选的数据项支持度应当不小于最小支持度，从而形成频繁项集 .

4、对频繁项集 进行连接生成候选集 ，重复上述步骤，最终形成频繁K项集或者最大频繁项集。

Apriori算法存在两大定理：

1、如果一个集合是频繁项集，那么它的所有子集都是频繁集合。

2、如果一个集合它不是频繁集合，那么它的所有超集都不是频繁项集。

9.1.3 Apriori算法优缺点

优：运算过程非常简单，理论方法也比较容易理解，对数据特征的要求也相对较低。

缺：

1、产生候选集是产生较多的组合，没有考虑将一些无关的元素排除后再进行组合。

2、每次计算项集的过程中都会扫描元素的数据表。

针对不足推出不断改进的Apriori算法：

1、将数据表（事务表）进行压缩。

2、利用哈希表的快速查找特性对项集进行计数统计。

3、合理选样。