7.1 如何处理分类属性？

面试官：如何处理分类的属性？

        二元属性即是/否，比如可以提取到{网络购物=是}->{关注隐私=是}，暗示大部分网购的都会关注个人隐私。标称属性，表示类别或者状态，比如衡量文化程度，可以是研究生、本科生、高中生等。
        提取方法是，先将属性转化为项，目的是使用关联规则算法。
        其中标称属性可以转换成若干个二元属性实现，比如：文化程度=大学，文化程度=研究生，文化程度=高中。
        在关联分析处理二元化数据时，要考虑：
            （1）属性值可能不够频繁，不能成为频繁模式的一部分。解决办法是可以将属性值分组，将许多不太频繁的属性值聚合成一个类别。比如可以把北京、天津、河北聚合成京津冀地区。
            （3）当新建的项变成频繁项时，计算时间可能会增加，因为需要用更多时间处理由这些项产生的候选项集。解决方法是，避免产生多个来自同一属性项的候选项集。

7.2 如何处理连续属性？

面试官：关联分析中，如何处理包含连续属性的关联规则？

程序员大树：
包含连续属性的关联规则称为量化关联规则。
处理的主要方法有：
       （II）区间太窄，可能因为缺乏支持度而丢失某些模式。较窄的区间的的规则支持度会低于最小支持度阈值，而被丢失。
比较容易的解决方式是，考虑临近区间的所有可能分组情况。但这样也会带来问题：
        （I）计算特别复杂。如果取值范围划分成k个部分，则有C_n^k种情况，把每种情况都去计算，这样特别繁琐。另外如果包含频繁子项集的区间，也必然是频繁的，因此会产生过多的候选项集。
        （II）提取到许多冗余规则。冗余体现在，会有很多特化规则。比如有规则：
    R1: {年龄∈[8,10]}→{走路=是}
    R2: {年龄∈[8,12]}→{走路=是}
    则R1是R2的特化，R2是R1的泛化。如果两个规则置信度相同，则R2更有趣，因为它涵盖范围更广，因此R1是多余的。
    （2）统计学方法。我们可以基于统计学，使用假设检验方法提取量化规则。
我们定义量化关联规则：A→t:μ ，A是频繁项集，t是连续目标属性，μ是A覆盖事务的平均值。μ^'是A未覆盖事务的平均值。检验目标是看μ和μ^'差是否大于用户给定的阈值∆。
建立两个相反假设，分别称作原假设和备择假设。
其中，是支持A的事务个数，是不支持A的事务个数。是支持A的事务t的标准差，是不支持A事务t的标准差。原假设下，Z是标准正太分布。计算实际Z值与临界比较，如果，则拒绝原假设，并可以认为该量化规则是有趣的。

7.3 如何处理概念分层？ 

面试官：什么是概念分层？概念分层怎么表示层级关系？概念分层有什么优缺点？

程序员大树：
概念分层是在特定域中的各种实体或概念的多层组织，可以基于特定分类标准或领域知识来定义。
 
概念分层可以用有向无环图表示。概念分层中的父子关系，可以通过有向边之间的路径进行提现。比如点p到点c的边，可以称作p是c的父母，c是p的子女。
使用概念分层作为关联分析的方法，优点如下：
    （1）原先位于层次结构下层的项可能因为没有足够的支持度而不在频繁项集中出现，而使用了概念分层则可以出现。比如子结点的支持度很低，而其父母结点的支持度很高，不用概念分层，则会丢失有趣模式、
    （2）概念分层的低层由于发现规则特殊，可能不如高层令人感兴趣，使用概念分层，可以将特殊转化成一般概念。比如具体的{全脂牛奶}→{白面包}、{脱脂牛奶}→{黑面包}，不如{牛奶}→{面包}有效。

概念分层的局限性如下：
    （1）处于高层的项比处于底层的项有更高的支持度计数，这样阈值太高就只能提取较高层的项，而阈值太低就会产生太多模式，其中很多还不是真实的。
    （2）概念分层引入增加了关联分析的计算时间。因为项的个数多，宽度大，算法产生的频繁模式个数可能会随事务变宽而指数增加。
    （3）概念分层会产生冗余规则。比如{x}→{y}，如果存在更一般的规则{X}→{Y}，则原规则是冗余的。一般来讲，如果两个规则具有相似的置信度，则较低层项的规则是冗余的，因为其可能被祖先的规则所概括。

7.4 什么是序列模式？

面试官：什么是序列模式？

程序员大树：
序列可以看成是元素的有序列表，记作s=<e1,e2,e3,…,en>。
数据序列：单个数据对象相关联的事件有序列表。
序列模式：给定的序列数据集D和用户指定最小支持度阈值minsup，序列模式发现的任务是找出支持度大于或等于minsup的所有序列。
产生序列模式一种暴力求解方法，枚举所有可能性，并统计各自的支持度。给定n个事件的集合，会依次产生候选1-序列，候选2-序列等等。
序列模式的发现，可以采用类Apriori算法，迭代地产生新的候选k-序列，剪掉（k-1）序列非频繁候选，对留下的候选计数，识别序列模式。
候选的产生：可以对频繁（k-1）序列合并，产生候选K序列。
候选合并的原则是，去掉第一个事件得到的子序列，与去掉最后一个事件得到的子序列相同，这样可以保证候选是两个序列最后一个事件的连接，从而避免产生重复的候选。
比如有两个序列是<1，2，3>， <2，3，4>，因为去掉首尾事件1，4之后，得到的子序列都是<2，3>，故可以合并，得到候选<1，2，3，4>。
再比如，有两序列是<1，2，3>， <1，2，5>，因为去掉首尾事件之后是2，3和1，2，并不相同，所以不必合并。

7.5 什么是子图模式？

面试官：有如何对图数据进行挖掘？

程序员大树：
图数据挖掘的目的是，在图集合中，发现公共子结构，可以称作频繁子图挖掘。
挖掘子图如果用暴力的方法，复杂性会呈几何性暴涨，故这里推荐使用一种类Apriori算法找出频繁子图，总体步骤是：
    （1）候选产生：合并频繁（k-1）子图对，得到候选K子图。
    （2）候选剪枝：丢弃包含非频繁（k-1）子图的所有候选k子图。
    （3）支持度计数：统计包含每个候选图的个数。
    （4）候选删除：丢弃支持度小于minsup的所有候选子图。
        子图的候选产生：合并频繁（k-1）子图对，得到候选K子图。对于k是图中定点的个数。通过增加顶点的方法扩展子图，称作顶点增长。
        顶点增长合并子图过程：两个邻接矩阵M1，M2合并时，如果删除M1最后一行和M2最后一列，得到的子矩阵相同，则结果是M1基础上，添加上M2的最后一行和最后一列。
        候选剪枝：丢弃包含非频繁（k-1）子图的所有候选k子图。实现方法是，相继从k子图删除边，看对应的（k-1）子图是否连通且频繁。如果不是，则候选k子图可以丢弃。判断两个图是否拓扑等价，称为图同构问题。
        处理图同构的标准方法是，将每个图映射成唯一的表达式，称作图代码，如果两个图是同构的，则他们的图代码一定相同。
        因为遍历顺序的不同，会得到不同的邻接矩阵，先找到一种特定表示形式的图邻接矩阵M。接下来将矩阵同过行列变换，转化为上三角矩阵M’。图代码是对M’上三角元素逐列连接得到的。这样可以保证，尽管观察的角度不同，但最终的投影代码是相同的。

7.6 什么是非频繁模式？

面试官：之前我们讨论的都是频繁模式，对于非频繁模式，该如何处理？

程序员大树：
        非频繁模式是一个支持度小于阈值minsup的项集或者规则。尽管大部分非频繁模式不是令人感兴趣的，但其中一些对分析是有用的，尤其是涉及到数据负相关时。负相关指的是一些竞争项，比如茶和咖啡，可以互相替代。

        挖掘非频繁模式的问题是，如何识别有趣的非频繁模式，以及如何有效发现非频繁模式。
        识别可以用负模式，它包括了负项集和负关联规则。
        负项集X的定义是：X=A∪B，其中A是正项集合，B是负项集合；s(X) ≥minsup。
        负关联规则：规则是从负项集提取的；规则支持度≥minsup；规则置信度≥minsup。
        发现非频繁项集，可以使用基于间接关联的支持度期望。
        间接关联：有时一对项并不是直接关联的，而是通过一系列中介集合间接关联。
 
        间接关联的产生：
        （1）可以先用Apriori增长算法，产生频繁项集。
        （2）然后合并每对频繁k-项集得到候选间接关联(a,b,Y) ，其中a,b是一对项，Y是他们公共中介。
        （3）合并频繁项集得到候选间接关联。