关联分析
基本概念
**频繁模式(frequent pattern)**是频繁地出现在数据集中的模式(如项集、子序列或子结构)。
例子：购物篮分析
顾客可能会在一次购物同时购买哪些商品？
帮助设计不同的商店布局
经常同时购买的商品摆放近，增加两种商品的销售
经常同时购买的商品摆放远，诱发顾客挑选其它商品
帮助零售商规划什么商品降价出售
其中一种商品的降价可能既促使该商品又促使与它经常同时购买的商品的购买
关联规则(association rule) 是形如A=>B的蕴涵式，A，B都不是空集，且它们不相交，它们都是项的集合的子集。
支持度和置信度
support(A=>B) = P(A∪B)
confidence(A=>B) = P(B|A)=support_count(A∪B)/support_count(A)
同时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称为强规则。
上式定义的项集支持度有时称为相对支持度，而出现频度称为绝对支持度。
如果项集I的相对支持度满足预定义的最小支持度阈值(即I的绝对支持度满足对应的最小支持度计数阈值)，则I是频繁项集(frequent itemset)。
一般而言，关联规则的挖掘是一个两步的过程：
(1)找出所有的频繁项集
(2)由频繁项集产生强关联规则：这些规则必须满足最小支持度和最小置信度
第二步的开销远低于第一步，因此挖掘关联规则的总体性能由第一步决定。
**从大型数据集中挖掘频繁项集的主要挑战是，这种挖掘常常产生大量满足最小支持度阈值的项集。**这是因为如果一个项集是频繁的，则它的每个子集也是频繁的。
项集X在数据集D中是闭的(closed)，如果不存在真超项集Y(X中的每个项都在Y中，而Y中至少有一个项不在X中)使得Y与X在D中具有相同的支持度计数。项集X是数据集D中的闭频繁项集(closed frequent itemset)，如果X在D中是闭的和频繁的。项集X是D中的极大频繁项集(maximal frequent itemset)或极大项集(max-itemset)，如果X是频繁的，并且不存在超项集Y使得$X\subset Y$并且Y在D中是频繁的。
Apriori算法：通过限制候选产生发现频繁项集
Apriori算法使用一种称为逐层搜索的迭代方法，其中k项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1.。然后，使用L1找出频繁2项集的集合L2，使用L2找出L3，如此下去，直到不能再找到频繁k项集。找出每个Lk需要一次数据库的完整扫描。
先验性质：频繁项集的所有非空子集也一定是频繁的
反单调性：如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试
伪代码：
题目
下面有关序列模式挖掘算法的描述，错误的是？
C，
\1. Apriori算法 ：关联分析原始算法，用于从候选项集中发现频繁项集。两个步骤：进行自连接、进行剪枝。缺点：无时序先后性。
AprioriAll算法：AprioriAll算法与Apriori算法的执行过程是一样的，不同点在于候选集的产生，需要区分最后两个元素的前后。
AprioriSome算法：可以看做是AprioriAll算法的改进
AprioriAll算法和AprioriSome算法的比较：
（1）AprioriAll用 去计算出所有的候选Ck，而AprioriSome会直接用 去计算所有的候选 ，因为 包含 ，所以AprioriSome会产生比较多的候选。
（2）虽然AprioriSome跳跃式计算候选，但因为它所产生的候选比较多，可能在回溯阶段前就占满内存。
（3）如果内存占满了，AprioriSome就会被迫去计算最后一组的候选。
（4）对于较低的支持度，有较长的大序列，AprioriSome算法要好些。
\2. GPS算法：类Apriori算法。用于从候选项集中发现具有时序先后性的频繁项集。两个步骤：进行自连接、进行剪枝。缺点：每次计算支持度，都需要扫描全部数据集；对序列模式很长的情况，由于其对应的短的序列模式规模太大，算法很难处理。
\3. SPADE算法：改进的GPS算法，规避多次对数据集D进行全表扫描的问题。与GSP算法大体相同，多了一个ID_LIST记录，使得每一次的ID_LIST根据上一次的ID_LIST得到（从而得到支持度）。而ID_LIST的规模是随着剪枝的不断进行而缩小的。所以也就解决了GSP算法多次扫描数据集D问题。
\4. FreeSpan算法：即频繁模式投影的序列模式挖掘。核心思想是分治算法。基本思想为：利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片断。这一过程对数据和待检验的频繁模式集进行了分割，并且将每一次检验限制在与其相符合的更小的投影数据库中。
优点：减少产生候选序列所需的开销。缺点：可能会产生许多投影数据库，开销很大，会产生很多的
\5. PrefixSpan 算法：从FreeSpan中推导演化而来的。收缩速度比FreeSpan还要更快些。
http://blog.csdn.net/ztf312/article/details/50889238
Last updated
Was this helpful?