Keywords: 数据挖掘,关联规则挖掘
Goal: 寻找频繁项目集
频繁项目集: 例,对于项目集L和事务数据库D,所有满足用户指定的最小支持度的项目集.
最大频繁项目集: 在频繁项目集中所有不被其他元素包含的频繁项目集.
支持度: L1属于L,L1在事务数据库D所占的百分比

例子:
用户指定支持度为2
有下面的项目集:


A出现的次数有3次,大于2,属于频繁项目集.
AB出现次数也是3次,大于2,也属于频繁项目集.
所有项目集按照规则就是:{A,B,C,D,E,AB,AC,AD,BC,BD,BE,CD,CE,ABC,ABD,ACD,BCE,ABCD}
按照最大频繁项目集的定义,ABCD,BCE都没有被其他元素包含,所以最大频繁项目集为{ABCD,BCE}.
ABC被ABCD包含,所以它并不是最大频繁项目集.
频繁项目集是形成关联规则的基础,所以采用最优的算法来构造频繁项目集是主要的工作.

所以引入了一种FP-tree算法:
       2000年,HAN提出了一个称为FP-tree的算法.该算法只进行2次数据库扫描.它直接压缩数据库成一个频繁模式树,作后通过这课树生成关联规则.
算法关键步骤:第一步是利用事物数据库中的数据构造FP-tree;第二步是从FP_tree中挖掘频繁模式.
仅通过案例来说明如何构造:
最小支持度取3

构造如下:
(1) 第一次扫描原始项目集,得到1-频项目集{f4,c4,a4,b3,m3,o3,p3}(数字表示其出现个数,不满足大于等于3的被排除)
(2) 创建ROOT节点,第二次扫描项目集,得到每个原始项目集中的满足支持度的分枝,例:1号项目集满足支持度的元素有f,c,a,m,p;2号项目集中满足支持度的元素有f,c,a,b,o等等,把他们都看做是树的分枝;
          将整理后项目集中的元素构造为如下树


       字母后面数字表示在公共前缀出现次数.根据该树可以回溯最低节点,找到对应节点的频繁模式:例,对于p来说,有三个回溯路径:{f,c,a,m,p}{f,c,a,o,p}{f,b,m,p} -- 这三个为p的条件模式基,因为这三个条件只包含一个频度节点<c:3>,所以产生的频度模式为cp:3
        下图表示挖掘过程


       这就是基本的FP-tree过程.对于恶意软件分类采用数据挖掘的方法还是可行的,希望在能尽管找到数据挖掘与恶意软件分类的具体实施过程.