数据挖掘-频繁项集

基本概念

支持度：两种商品同时被购买占事务总数的比例，反映发现该规则的有用性

置信度：购买一个商品的顾客中同时购买另一个商品的顾客所占比例，反映规则的确定性。

支持度 =支持度({A ∪C}) = 50%

置信度= 支持度({A ∪C})/支持度({A}) = 66.6%

项集：项的集合，如集合{computer，antivirus_software}是一个2项集

频繁项集：同时满足最小支持度阈值和最小置信度阈值的规则

决策树：决策树算法采用树形结构，使用层层推理来实现最终的分类。决策树由下面几种元素构成：

• 根节点：包含样本的全集
• 内部节点：对应特征属性测试
• 叶节点：代表决策的结果

  

  ··

  单维挖掘方法

  可以分为三类：Apriori算法，基于频繁模式增长的算法（如FP-growth算法），使用垂直数据格式的算法

  1). Apriori算法

  频繁项集先验性质： 频繁项集的所有非空子集也一定是频繁的。

  基本思想：使用逐层搜索的迭代方法，其中k项集用于探索（k+1）项集，使用先验性质压缩搜索空间。

  如何使用L(k-1)找到L(k): 通过连接步和剪枝步完成。连接步通过将L(k-1)与自身连接产生候选k项集集合。剪枝步从候选k项集确定L(k)。

  例子：

  

  C 2 C_2 C2​中的{1，2}，{1，5}被剪枝， L 2 L_2 L2​中第一项与2、3、4项不用再考虑

  从事务数据库中构建FP-树

  使用FP-树循环的产生频繁模式路径

  对于每一个项，先构造它的条件模式基，然后构造它的条件FP-树，重复

  —> 每一条子路径都是一个频繁模式

  条件模式基：最能够成功条件者，是原支持度最高者

  

  FP树挖掘：

  • 从头表的最后一项p开始：

    直接频繁集是(p:3)

    p存在于2条路径当中：路径和路径。包含p的路径出现了2次，同时也会有出现了3次，出现了4次。但是我们只关注（目的是找出包含p的所有频繁集合）。出现了1次。

    p就有2个前缀路径{(fcam:2),(cb:1)}。这两条前缀路径称之为p的子模式基（subpattern-base），也叫做p的条件模式基（因为这个子模式基是在p存在的前提条件下）。

    再为这个条件子模式基构造一个FP树：

    

    由于频繁集的阈值是3，剪枝之后只剩下一个分支(c:3)

    频繁项目集{cp:3}

    • 倒数第二项m

      (m:3)

      在FP树中存在的两条路径和，频繁条件子模式基就是{ (fca:2),(fcab:1)}，得到

      {fcam:3}

      • 倒数第三项

        (b:3)

        三条路径,,，形成的频繁条件子模式基为{(fca:1),(f:1),(c:1)}，构建成的ＦＰ树中的所有节点的频率均小于3,那么FP树为空，结束递归

        • 倒数第四位

          (a:3)

          有一条路径，频繁条件子模式基为{(fc:3)}

          {(fa:3),(ca:3),(fca:3),(a:3)}

          • 倒数第五位

            只有一条路径,频繁条件子模式基为{(f:3)}

            {(fc:3),(c:4)}

            • 最后一位

              {(f:4)}

              流程表：

              

              此部分图片来源于monsion-FP树构造

              `

              提高Apriori算法效率：

              基于散列的技术：将事务产生的k项集散列到散列表的不同桶中，并增加相应桶计数，对应桶计数小于支持度阈值不可能是频繁的，可以从候选集中删除。这一技术可以显著地压缩需要考察的k项集

              事务压缩：不包含任何频繁k项集的事务不可能包含任何频繁(k+1)项集，因此在其后的考虑时，可以加上标记或删除。

              划分：分两个阶段，阶段一把D划分成n个分区，找出每个分区的局部频繁项集，组合所有局部频繁项集形成候选项集； 阶段二评估每个候选的实际支持度，找出候选项集中的全局频繁项集。整个过程只需要两次数据库扫描。

              抽样：基本思想是选取数据库D的随机样本S，然后再S中搜索频繁项集。这种方法牺牲了一些精度换取了有效性，可能会丢失一些全局频繁项集

              动态项集计数： 基本思想是奖数据库划分为用开始点标记的块。不像Apriori算法仅在每次完整的数据库扫描前确定新的候选，这种变形中，可以再任何开始点添加新的候选集。该变形需要的数据库扫描笔Apriori算法少。

              多层关联规则挖掘

              统一支持度：对所有层使用相同的最小支持度

              • 优点:只有一个最小的支持度阈值

              • 缺点:较低层次抽象的项不大可能像较高层次抽象的项出现的那么频繁

                • 太高⇒会遗失低层的关联规则
                • 太低⇒会产生太多的高层关联规则

                  递减支持度:在较低层使用较小的最小支持度

                  有四种搜索策略:

                  • 逐层独立
                  • 层交叉k-项集过滤
                  • 层交叉单项过滤
                  • 受控的层交叉单项过滤

                    多层关联规则的冗余过滤：其父项是冗余的

                    ··

                    高效挖掘：

                    • 首先应用粗糙/廉价操作(超集覆盖)
                    • 接着在一个充分递减的候选集上应用昂贵的算法

                      由关系数据库和数据仓库挖掘多维关联规则

                      多维规则: 涉及两个或两个以上的维或谓词

                      维间关联规则 (没有重复的谓词)

                      a g e ( X , ” 19 − 25 ” ) ∧ o c c u p a t i o n ( X , “ s t u d e n t ” ) ⇒ b u y s ( X , “ c o k e ” ) age(X,”19-25”) ∧ occupation(X,“student”) ⇒buys(X,“coke”) age(X,”19−25”)∧occupation(X,“student”)⇒buys(X,“coke”)

                      混合维关联规则 (有重复的谓词)

                      a g e ( X , ” 19 − 25 ” ) ∧ b u y s ( X , “ p o p c o r n ” ) ⇒ b u y s ( X , “ c o k e ” ) age(X,”19-25”) ∧ buys(X, “popcorn”) ⇒ buys(X, “coke”) age(X,”19−25”)∧buys(X,“popcorn”)⇒buys(X,“coke”)

                      ··

                      模式评估

                      并非所有强关联规则都是有趣的，比如项集计算机游戏和录像可能满足强关联规则，但是它们是负相关的。

                      提升度：一种相关性的度量，结果值大于1是正相关，为1表示独立，小于1表示负相关。

                      相关性度量还有最大置信度和余弦。

                      ··

                      由关联挖掘到相关分析

                      客观度量：支持度和置信度

                      主观度量：一个规则(模式)是有趣的

                      • 是非预期的(令用户吃惊的)
                      • 或可控制的 (用户可以用它来做一些事情)

                        缺点：

                        

                        

                        也就是条件概率P(A|B)

                        ··

                        ·