6.1 什么是关联分析？

面试官：关联关系是什么？

程序员大树：关联分析的任务就是从数据集中挖掘出频繁项集，然后从频繁项集中提取出事物之间的强关联规则，辅助决策。

面试官：那么什么时候会用到关联分析？

关联分析应用在项不多的情况下，从整体数据中挖掘潜在关联。具体应用场景可分为如下几个：
（1）产品推荐与引导。关联分析做推荐时，主要用于个性化不强的场景。比如根据购买记录，通过关联分析发现群体购买习惯的内在共性，指导超市产品摆放。
（2）发掘潜在客户，精准营销。当通过关联分析，发现许多购买A的用户还会购买B，即有规则A—>B，可通过有购买B产品行为的用户，找到A产品的潜在意向用户，进行精准营销。
（3）特征筛选。在特征工程中，需要对特征进行筛选。对特征筛选包括：保留与目标变量关联大的特征，删除高度相关的特征。在一般使用的相关性系数方法中，只能判断两个变量间的相关性，而通过关联分析得到的规则，可以判断多个变量之间的关系。

面试官：怎么对关联规则做有效性判别？

程序员大树：关联规则的支持度（support）：衡量频繁项集的频繁贡献度。支持度(support)从字面上理解就是支持的程度，一个项集的支持度(support)被定义为数据集中包含该项集的记录所占的比例。
     设W中有s％的事务同时支持物品集A和B，s％称为{A，B}的支持度，即:

num(A∪B)表示含有物品集{A,B}的事务集的个数，不是数学中的并集。

（2）关联规则的置信度（confidence）：置信度(confidence)揭示了A出现时B是否一定出现，如果出现，则出现的概率是多大。
用公式表示是，物品A->B的置信度=物品{A,B}的支持度 / 物品{A}的支持度：

面试官：如何发现有效关联规则？

程序员大树：
    1. 挖掘频繁项集：找到满足支持度阈值的项集，这些项集叫做频繁项集。
    （1）Apriori（先验）算法。
        先验原理：如果一个项集是频繁项集，则它的所有子集也是频繁项集。相反，如果一个项集不是频繁项集，那么其所有超集也都不是频繁项集（剪枝）。
    （2）FP增长算法（FP-growth）
FP-growth算法基于Apriori构建，但采用了高级的数据结构（FP树）减少扫描次数，大大加快了算法速度。
    2. 挖掘关联规则：从上一步中产生的频繁项集中，找到高置信度的规则，这些规则被称为强规则（strong rule）。
    上一步基于支持度进行频繁项集的挖掘，这里基于置信度进行关联规则的挖掘。
    将频繁项集Y划分为两个非空子集X和Y-X，计算X→Y-X的置信度，如果大于设定的置信度阈值，即为有效规则。
    原理：如果X→Y-X是一条低可信度规则，那么所有其他以包含Y-X的子集（指Y的子集）为后件的规则均为低可信度的（剪枝）。
    反之，如果X→Y-X是一条高可信度规则，那么其他以包含Y-X的子集为后件的规则可以进入到下一轮的迭代层次搜索中，继续进行判别，直至搜索停止。

6.2 什么是频繁项集？

面试官：关联分析这里有哪些概念？

程序员大树：有以下概念需要知道：
事务：每一条交易称为一个事务。
项：交易里的每个物品称为一个项。
项集：包括零个或多个项的集合叫做项集。
k−项集：包括k个项的项集叫做k-项集，比如{Cola}叫做1-项集，{Cola, Egg}叫做2-项集。
支持度计数：一个项集出如今几个事务其中，它的支持度计数就是几。
比如{Diaper, Beer}出如今事务002、003和004中。所以它的支持度计数是3。
支持度：支持度计数除以总的事务数。比如上例中总的事务数为4，{Diaper, Beer}的支持度计数为3。所以它的支持度是3÷4=75%。说明有75%的人同一时候买了Diaper和Beer。
频繁项集：支持度大于或等于某个阈值的项集就叫做频繁项集。
前件和后件：对于规则{Diaper}→{Beer}，{Diaper}叫做前件。{Beer}叫做后件。
置信度：对于规则{Diaper}→{Beer}，{Diaper, Beer}的支持度计数除于{Diaper}的支持度计数。为这个规则的置信度。比如规则{Diaper}→{Beer}的置信度为3÷3=100%。说明买了Diaper的人100%也买了Beer。
强关联规则：大于或等于最小支持度阈值和最小置信度阈值的规则叫做强关联规则。关联分析的最终目标就是要找出强关联规则。
频繁项集的传递性：
频繁项集的子项集也都是频繁项集。非频繁项集的超集也都是非频繁项集。

6.3 产生频繁项集有哪些方法？

面试官：产生频繁项集有哪些方法？

程序员大树：
    （1）项集格遍历。格结构常用来表示所有可能的项集。对频繁项集的搜索可以看成是遍历项集格。可以使用的搜索策略有：从一般到特殊、特殊到一般、双向搜索。从一般到特殊，适用于从非频繁项集开始搜索。对于稠密事务，使用从特殊到一般更优一些，可以用先验原理减掉极大频繁项集的所有子集。双向搜索有助于加快确定频繁项集边界。
    （2）等价类。遍历也可以将网格划分为两个不相交的等价类，并依次再每个等价类中搜索频繁项集。
    （3）宽度优先和深度优先。宽度优先是从频繁1-项集，再到频繁2-项集，一直到没有新频繁项集产生为止。深度优先遍历是从结点开始支持度计数，判断它是否频繁，直到非频繁点，然后再回溯到下个分支。深度优先适合发现极大频繁星际，比宽度优先能更快地检测到频繁项集边界，并能及时剪枝。

6.4 什么是FP增长算法？

面试官：什么是FP增长算法？

程序员大树：
    FP增长算法，采用FP树的紧凑数据结构组织数据，并从中直接提取频繁项集。FP代表频繁模式（Frequent Pattern）。FP树通过链接（link）来连接相似元素，被连起来的元素项可以看成一个链表。我们可以把事物映射到FP树的一条路径来构造。路径相互重叠的越多，使用FP的压缩效果越好。
FP算法的过程：
    输入：数据集、最小值尺度
    输出：FP树、头指针表
1. 遍历数据集，统计各元素项出现次数，创建头指针表
2. 移除头指针表中不满足最小值尺度的元素项
3. 第二次遍历数据集，创建FP树。对每个数据集中的项集：
    3.1 初始化空FP树
    3.2 对每个项集进行过滤和重排序
    3.3 使用这个项集更新FP树，从FP树的根节点开始：
        3.3.1 如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值
        3.3.2 否则，创建新的子节点，更新头指针表
        3.3.3 对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程
        我们可以根据出现的频率，绘制出头指针表（Header Table）的数据结构，用来记录各项元素出现次数。
同时可以绘制FP树如下：
 

6.5 如何评估关联效果？

面试官：如何评估关联效果？

如果lift(A,B)<1，则说明A的出现和B的出现是负相关的；
如果lift(A,B)>1，则A和B是正相关的，意味A的出现对B的出现有促进作用；
如果lift(A,B)=1，则说明A和B是独立的，没有相关性。