数据挖掘算法-Apriori Algorithm（关联规则）

核心提示： 3.解释三：P(X)，意思是事件X出现的概率；4.解释四：关联规则当中是有绝对支持度（个数）和相对支持度（百分比）之分的，数据挖掘算法-Apriori Algorithm（关联规则）(2)，置信度（Confidence/Strength）： 定义为 conf(X->Y) = supp(X

3.　解释三：P(X)，意思是事件X出现的概率；

4.　解释四：关联规则当中是有绝对支持度（个数）和相对支持度（百分比）之分的。

置信度（Confidence/Strength）： 定义为 conf(X->Y) = supp(X ∪ Y) / supp(X) = P(Y|X)。

在历史数据中，已经买了某某（例如：A、B）的支持度和经过挖掘的某规则（例如：A=>B）中A的支持度的比例，也就是说买了A和B的人和已经买了　A的人的比例，这就是对A推荐B的置信度（A=>B的置信度）< /span>

候选集（Candidate itemset）：通过向下合并得出的项集。定义为C[k]。

频繁集（Frequent itemset）：支持度大于等于特定的最小支持度（Minimum Support/minsup）的项集。表示为L[k]。注意，频繁集的子集一定是频繁集。

提升比率（提升度Lift）：lift(X -> Y) = lift(Y -> X) = conf(X -> Y)/supp(Y) = conf(Y -> X)/supp(X) = P(X and Y)/(P(X)P(Y))

经过关联规则分析后，针对某些人推销（根据某规则）比盲目推销（一般来说是整个数据）的比率，这个比率越高越好，我们称这个规则为强规则；

剪枝步

只有当子集都是频繁集的候选集才是频繁集，这个筛选的过程就是剪枝步；

【2】Apriori优化：Fp-tree 算法

关键点：以树形的形式来展示、表达数据的形态；可以理解为水在不同河流分支的流动过程；

生成Fp-tree的几个点：

扫描原始项目集；

排列数据；　

创建ROOT节点；

按照排列的数据进行元素的流动；

节点+1；

更多内容请自行学习

【3】Apriori优化：垂直数据分布

关键点：相当于把原始数据进行行转列的操作，并且记录每个元素的个数

更多内容请自行学习

【4】摘要：数据挖掘中关联规则算法的研究

Apriori核心算法过程如下：

过单趟扫描数据库D计算出各个1项集的支持度，得到频繁1项集的集合。

连接步：为了生成，预先生成,由2个只有一个项不同的属于的频集做一个（k-2）JOIN运算得到的。

剪枝步：由于是的超集，所以可能有些元素不是频繁的。在潜在k项集的某个子集不是中的成员是，则该潜在频繁项集不可能是频繁的可以从中移去。

通过单趟扫描数据库D，计算中各个项集的支持度，将中不满足支持度的项集去掉形成。

通过迭代循环，重复步骤2～4，直到有某个r值使得为空，这时算法停止。在剪枝步中的每个元素需在交易数据库中进行验证来决定其是否加入，这里的验证过程 是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库。可能产生大量的候选集，以及可能需要重复扫描数据库，是Apriori算法的两大缺点。

目前，几乎所有高效的发现关联规则的并行数据挖掘算法都是基于Apriori算法的，Agrawal和Shafer 提出了三种并行算法：计数分发（Count Distribution）算法、数据分发（Data Distribution）算法和候选分发（Candidate Distribute）算法。

【5】总结

例子就暂时不举例，因为网上的这些例子也是比较多的；

度量标准还有很多很多很多，如：Lift/Interest、All-confidence、Consine、Conviction、Jaccard、Leverage、Collective strength等等。

频繁数据模型的分类比较多，需要慢慢理解；

出处：http://gaizai.cnblogs.com/