·144 智能系统学报 第4卷 或从小到大)顺序排列 调性约束)或由小到大（简洁反单调性约束）创建 FP-tree:一个字典树，每个节点是一个对偶(r List表； tem-name,.F),其中item-name是项名，F是由FP- 2)初始化FP-tree,根指针T为“NULL”: tree的根节点至当前节点的路径上所有项组成的项 3)ForDB中的每个事务t 集的支持度 ①事务的项集已经是T的一个分支（仔 2.2建立FP-tree 树){ 建立FP-tree的步骤如下： ② 该分支上的节点N的支持度增加1； 1)把项按照A的值从大到小顺序排序，放进 ③ List中该项集的每个单项的支持度增加 List表中 1,} 2)扫描事务数据库，根据List中项的顺序建立 ④ Else FP-tree,把每次涉及到的项的支持度（卿List表中项 ⑤ 创建新的节点N,存放事务T的项集： 的δ值)加1，直到最后一个事务，同时建立相同项 ⑥ 节点N和T连接起来； 之间的连接.此时包含非频繁项的树建立完毕， ⑦ 具有相同项的节点连接起来；} 如图所示 ⑧Endf List Root ⑨End For 65 4)fN的支持度小于最小支持度 60a 5)删除节点N以及和N有关的连接： 55e 2 6)End If 40d3 23建立满足约束的条件树找出最大频繁模式 e:I 35 首先从Lst表中最后一项开始，判断各项是否 30b4 b:1-=b:1 满足给定的条件.如果不满足，则不用建立该项的条 件树，这样就把约束放到了挖掘过程中，根据约束的 图1包含非频繁项的树的结构 性质来降低搜索空间.如果找到满足约束的项，则建 Fig 1 Tree included infrequent item set 立该项的条件树，并把该树中的非频繁项即局部非 3)查Ls表去掉表中非频繁项.当去掉非频繁项 频繁项去掉.由图2可知，最后一项是b,b满足假设 时，根据连接重新调整树的结构.由图1中List可知f 的简洁性约束C,=min (sA)≥30，b的条件树 的支持度小于2，去掉项f后的FP-tree如图2所示. 如图3所示.由于b的条件树中没有局部非频繁项， Root 所以不用再重新调整该树的结构 List e:2 h4 60 c:I 30b 4 h 图2FP-tree结构 图3b的条件树 Fig 2 FP-tree structure Fig 3 Condition-tree of b 算法1建立FP-tree的算法】 然后用该树的分支两两相交来得到局部最大 输入：DB,最小支持度8，简洁性约束； 频繁模式.例如b的条件树前2个分支bcae:1和 输出：FP-tee bcda:1相交得到bca:2然后按照支持度由大到小 方法： 的顺序插入到最大模式树中.最大模式树初始值为 1)按照每个单项的属性A值由大到小（简洁单 空，如果某项集已存在于最大模式树中或是已存在 的最大模式树的子集，则不再插入该项集.挖掘完b 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net(或从小到大 )顺序排列. FP2tree:一个字典树 ,每个节点是一个对偶 ( i2 tem2name, F ) ,其中 item2name是项名 , F是由 FP2 tree的根节点至当前节点的路径上所有项组成的项 集的支持度. 2. 2 建立 FP2tree 建立 FP2tree的步骤如下 : 1)把项按照 A 的值从大到小顺序排序 ,放进 List表中. 2)扫描事务数据库 ,根据 L ist中项的顺序建立 FP2tree,把每次涉及到的项的支持度 (即 L ist表中项 的 δ值 )加 1,直到最后一个事务 ,同时建立相同项 之间的连接. 此时包含非频繁项的树建立完毕 , 如图 1所示. 图 1 包含非频繁项的树的结构 Fig. 1 Tree included infrequent item set 3)查 List表去掉表中非频繁项.当去掉非频繁项 时 ,根据连接重新调整树的结构. 由图 1中 List可知 f 的支持度小于 2,去掉项 f后的 FP2tree如图 2所示. 图 2 FP2tree结构 Fig. 2 FP2tree structure 算法 1 建立 FP2tree的算法. 输入 : DB, 最小支持度 δ,简洁性约束 ; 输出 : FP2tree 方法 : 1)按照每个单项的属性 A值由大到小 (简洁单 调性约束 )或由小到大 (简洁反单调性约束 )创建 List表 ; 2)初始化 FP2tree,根指针 T为“NULL”; 3) For DB中的每个事务 t ① If事务 t的项集已经是 T的一个分支 (子 树 ) { ② 该分支上的节点 N 的支持度增加 1; ③ List中该项集的每个单项的支持度增加 1; } ④ Else { ⑤ 创建新的节点 N,存放事务 T的项集; ⑥ 节点 N 和 T连接起来 ; ⑦ 具有相同项的节点连接起来 ; } ⑧ End If ⑨End For 4) IfN 的支持度小于最小支持度 5)删除节点 N 以及和 N 有关的连接 ; 6) End If 2. 3 建立满足约束的条件树找出最大频繁模式 首先从 L ist表中最后一项开始 ,判断各项是否 满足给定的条件. 如果不满足 ,则不用建立该项的条 件树 ,这样就把约束放到了挖掘过程中 ,根据约束的 性质来降低搜索空间. 如果找到满足约束的项 ,则建 立该项的条件树 ,并把该树中的非频繁项即局部非 频繁项去掉. 由图 2可知 ,最后一项是 b, b满足假设 的简洁性约束 Cs = m in (s. A ) ≥ 30, b的条件树 如图 3所示. 由于 b的条件树中没有局部非频繁项 , 所以不用再重新调整该树的结构. 图 3 b的条件树 Fig. 3 Condition2tree of b 然后用该树的分支两两相交来得到局部最大 频繁模式. 例如 b的条件树前 2个分支 bcae: 1和 bcda: 1相交得到 bca: 2. 然后按照支持度由大到小 的顺序插入到最大模式树中. 最大模式树初始值为 空 ,如果某项集已存在于最大模式树中或是已存在 的最大模式树的子集 ,则不再插入该项集. 挖掘完 b ·144· 智 能 系 统 学 报 第 4卷