第41 卷第9 期自动化学报Vol. 41, No. 92015 年9 月ACTA AUTOMATICA SINICA September, 2015基于模式增长方式的高效用模式挖掘算法王乐1 熊松泉1 常艳芬1 王水1摘要高效用模式挖掘是数据挖掘领域的一个重要研究内容; 由于其计算过程包含对模式的内、外效用值的处理, 计算复杂度较大, 因此挖掘算法的主要研究热点问题就是提高算法的时间效率. 针对此问题, 本文给出一个基于模式增长方式的高效用模式挖掘算法HUPM-FP, 该算法可以从全局树上挖掘高效用模式, 避免产生候选项集. 实验中, 采用6 个典型数据集进行实验, 并和目前效率较好的算法FHM (Faster high-utility itemset mining) 做了对比, 实验结果表明本文给出的算法时空效率都有较大的提高, 特别是时间效率提高较大, 可以达到1 个数量级以上.关键词高效用模式, 频繁模式, 频繁项集, 数据挖掘引用格式王乐, 熊松泉, 常艳芬, 王水. 基于模式增长方式的高效用模式挖掘算法. 自动化学报, 2015, 41(9): 1616¡1626DOI 10.16383/j.aas.2015.c150056An Algorithm for Mining High Utility Patterns Based on Pattern-growthWANG Le1 XIONG Song-Quan1 CHANG Yan-Fen1 WANG Shui1Abstract High utility pattern mining is an important research topic in data mining. Because of the additional in-ner/outer utility processing workload, its computational complexity increases, and the improvement of its temporal e±-ciency is vital. To address this issue, a new pattern-growth mining algorithm is proposed for high utility pattern miningnamed HUPM-FP. This algorithm can mine high utility patterns from a global tree without generating candidate itemsets.Six classical datasets were used in our experiments for comparing with the state-of-art algorithm faster high-utility itemsetmining (FHM). The proposed HUPM-FP out-performed its counterpart signi¯cantly, especially for time e±ciency, whichwas up to 1 order of magnitude faster.Key words High utility pattern, frequent pattern, frequent itemset, data miningCitation Wang Le, Xiong Song-Quan, Chang Yan-Fen, Wang Shui. An algorithm for mining high utility patterns basedon pattern-growth. Acta Automatica Sinica, 2015, 41(9): 1616¡1626频繁模式(Frequent pattern, FP) 挖掘是数据挖掘中一项重要而基础的技术, 但是频繁模式挖掘仅仅考虑了一个项集(或模式) 在数据集中出现的频率, 没有考虑项集中各项的外部效用值(如重要度、利润、价格等) 和内部效用值(数量)[1¡6]; 例如对于一个购物单数据, 频繁模式挖掘只考虑一个购物单中有哪些商品, 而没有考虑一个购物单中商品的数量、价格或利润. 然而在现实的很多应用中, 这些效用值相关信息可以度量项集(模式) 的成本、利润值或其他重要度等信息. 由此, 在频繁模式挖掘的收稿日期2015-01-30 录用日期2015-06-07Manuscript received January 30, 2015; accepted June 7, 2015宁波市自然科学基金和攻关项目(2013A610115, 2014A610073,2013C10010), 浙江省教育厅一般科研项目(Y201432717), 宁波大红鹰学院大宗商品专项课题(1320133004) 资助Supported by Ningbo Natural Science Foundation & ResearchProgram (2013A610115, 2014A610073, 2013C10010), GeneralScienti¯c Research Fund of Zhejiang Provincial Education De-partment (Y201432717),and Bulk Commodity Special Fund ofNingbo Dahongying University (1320133004)本文责任编委周志华Recommended by Associate Editor ZHOU Zhi-Hua1. 宁波大红鹰学院信息工程学院宁波3151751. School of Information Engineering, Ningbo Dahongying Uni-versity, Ningbo 315175基础上, 提出了高效用模式(高效用项集) 挖掘, 即将事务项集中项的效用信息引入到模式挖掘中. 目前, 高效用模式挖掘也是数据挖掘领域的一个研究热点[7¡14].2004 年, 首先由Yao 等提出了高效用模式挖掘的定义和数学模型[15]: 在一个数据集D 上一个项集X 的效用值U(X), 被定义为X 在所有包含项集X 的事务t 上的效用值U(X, t) 的总和, 即;U(X) =Px2t U(X; t), 例如: \啤酒"+\尿布" 组合在所有包含这2 种商品的购物单中所产生的利润的总和, 即称为项集啤酒、尿布的效用值. 高效用项集挖掘的任务, 就是找出效用值不小于用户预先设定阈值(最小效用值) 的所有项集. 同时, 在文献[15] 中, Yao 等还提出一种挖掘算法, 该算法用项集的估计值来判断一个项集是否可能是高效用模式(这里也称为候选项集); 然后, 再扫描数据集来统计这些候选项集的真实效用值来判断是否是高效用模式. 但是, 当用户设定的阈值比较低时, 或数据集中每个记录比较长, 该算法会产生过多的候选项集, 从而统计候选项集的真实效用值的时空代价都比较大.2005 年, Liu 等[16] 提出了一个典型算法Two-9 期王乐等: 基于模式增长方式的高效用模式挖掘算法1617phase, 并且给出一个TWU (Transaction weightedutilization) 模型, 即一个项集的twu 值不小于用户设定的最小效用值, 该项集就是一个候选项集, 相对文献[15] 中的算法, 可以有效降低项集效用值的估计值. Two-phase 基于Apriori 算法和TWU 模型,该算法分为两步: 首先, 挖掘出所有的候选项集; 然后, 扫描数据集来计算候选项集的真实效用值. 算法Two-phase 的时空效率高于文献[15] 中的算法, 算法Two-phase 中的候选项集是采用算法Apriori 的层次方式产生的, 其时间和空间代价也是比较大的.Erwin 等[17] 提出了一个基于树结构的挖掘算法CTU-mine, 采用模式增长的方式来产生候选项集, 然后同算法Two-phase 相同, 还需要扫描数据集来计算候选项集的真实效用值. 该算法只是在挖掘稠密数据集或用户设定的阈值比较低的时候, 算法性能优于Two-phase 算法.Ahmed 等[18] 提出一个基于模式增长方式的挖掘算法IHUP (Incremental high utility pattern),该算法不需要多次扫描数据集来产生候选项集.针对算法IHUP, Tseng 等[19¡20] 提出算法UP-growth, 该算法主要是针对算法IHUP 中建树方法的改进, 减少候选项集的个数, 算法的时间效率有较大的提升. 算法IHUP 和UP-growth 都是采用模式增长的方式产生候选项集, 而不能直接从树上得到高效用模式.目前的算法主要通过两个阶段挖掘高效用模式,首先, 采用层次方式或模式增长方式找出候选项集;然后, 扫描数据集计算每个候选项集的真实效用值来判断该候选项集是否是高效用模式. 2012 年, Liu等提出一个更高效的算法HUI-miner (High utilityitemsets-miner)[21], 该算法不产生候选项集, 也不需要多次扫描数据集就可以挖掘到高效用模式, 相对UP-growth, 该算法的时空效率有较大程度的提高. 2014 年, 在算法HUI-miner 基础上, Fournier-Viger 等[14] 提出策略来优化HUI-miner, 并给出新的挖掘算法FHM (Faster high utility itemset min-ing); 相对算法HUI-miner, 该算法能有效降低挖掘过程中产生的项集个数, 从而算法的时间效率能提高到6 倍.尽管高效用模式挖掘算法的时空效率已有很多的提高, 但是算法的时间代价还是比较大, 挖掘算法时空效率的提升, 特别是时间效率的提高仍然为本领域的一个挑战. 本文给出一个新的算法HUPM-FP (High utility pattern mining based onFP-growth), 该算法采用模式增长方式来挖掘高效用模式, 但是这里可以直接采用模式增长的模式挖掘到高效用模式, 而不是候选项集.1 相关定义设D = ft1; t2; t3; ¢ ¢ ¢ ; tng 是一个含有效用信息的数据集, 其中该数据集包含有m 个不同的项(即I = fi1; i2; i3; ¢ ¢ ¢ ; img); tj (j =1; 2; 3; ¢ ¢ ¢ ; n) 是数据集D 中第j 个事务项集(j 被称为事务项集的ID), 事务项集tj 的数据形式为f(x1; c1); (x2; c2); ¢ ¢ ¢ ; (xv; cv)g (v 为事务项集中项的个数或事务项集的长度), 其中ck(k = 1; 2; ¢ ¢ ¢ ; v) 是项xk 在事务tj 中的数量, 记为q(xk; tj) 也被称为项xk 的内部效用值; 项集I 中项ir (r = 1; 2; 3; ¢ ¢ ¢ ;m) 的权重值记为p(ir), 该权重值也被称为项ir 的外部效用值. jDj 表示数据集D 中事务个数或数据集的大小.定义1. 项x 在事务t 中的效用值, 记为U(x; t), 其定义如下:U(x; t) = p(x)q(x; t) (1)定义2. 项集X 在事务t 中的效用值, 记为U(X; t), 其定义如下:U(X; t) =8<:0; 若X * tXx2XU(x; t); 若X µ t (2)定义3. 项集X 在数据集D 中的效用值, 记为u(X), 其定义如下:U(X) =Xt2Du(X; t) (3)定义4. 一个事务t 的效用值, 记为tu(t), 其定义如下:tu(t) =Xx2tU(x; t) (4)定义5. 在一个数据集D 中, 一个项集X 的事务权重效用值twu, 记为twu(X), 定义如下:twu(X) =Xt2D^t¶Xtu(t) (5)其中包含该项集的所有事务效用值的和.定义6. 一个项集/项X 的twu 值不小于预定义的最小效用值, 则该项集/项就是一个候选项集/项; 否则, 是非候选项集/项.twu(X) =Xt½D^t¶Xtu(t) (6)定义7. 在一个数据集中, 一个项集X 的支持数(Support number, SN) 是指那些包含项集X 的事务项集个数, 即为项集X 在数据集中出现的次数.1618 自动化学报41 卷性质1. 项集的事务权重效用值满足闭包属性:任一个候选项集的非空子集也是一个候选项集, 任一个非候选项集的超集也是一个非候选项集.2 HUPM-FP 算法HUPM-FP 算法采用模式增长的方式进行高效用模式挖掘, 该算法的主要工作分为2 步: 1) 将事务项集压缩到一棵树上, 该树上存储维护整个数据集上高效用模式的信息, 该树也称为一棵全局树; 2)从全局树上挖掘所有高效用模式.2.1 全局树的构建以表1 和表2 中的数据为例说明全局树的构建过程, 这里设定最小阈值为40. 构建步骤如下:步骤1. 扫描一遍数据集, 统计各项的效用值(Uitility)、事务权重效用值(twu)、支持数(SN), 如图1 (a) 中的头表H 所示.步骤2. 将头表H 中twu 值小于最小阈值40的项删除, 剩余项按SN 从大到小排序(这里也可以按utility 或twu 值排序), 并将头表中所有项的twu 值重新赋值为0. 如图1 (b) 中的头表H1 所示.步骤3. 第2 次扫描数据集, 将每个事务项集中不在头表H1 中的项删除, 并按头表中项的顺序排序, 然后依次添加到一棵树上; 并更新头表中相应项的twu 值.如表1 中的第一个事务项集经过删除不在头表H1 中的项和排序后, 得到(c, 3), (d, 3), (b, 3), (e,1); 然后添加到树T 上的结果如图1 (c) 所示, 其中添加的最后一个节点存储该项集的信息, 如uList =f6, 3, 12, 3g 表示该项集中项c、d、b 和e 的效用值, SN=1 表示次数; 当在添加该项集中项c 时, 将图1 全局树构建实例Fig. 1 An example of constructing a global tree9 期王乐等: 基于模式增长方式的高效用模式挖掘算法1619项c 的效用值累加到头表项c 对应的twu 值中, 当添加到项d 时, 将之前项c 和项d 的效用值和累加到头表项d 对应的twu 值中, 即当处理到每项x 时,将之前所有项和当前项x 的效用值和累加到头表项x 对应的twu 值中, 头表中twu 值更新后的结果如图1 (c) 中的头表所示. 添加表1 中第2 个事务项集后的结果如图1 (d) 所示. 当添加第3 个事务的时候, 因为该项集对应的最后一个节点在树上也已经存在了, 所以这里只需要将各项对应的效用值累加到uList 的对应项上, SN 增加1 即可, 结果如图1 (e) 所示. 第4 个事务项集添加到树上后的结果如图1 (f) 所示, 将所有事务项集添加到这棵树上后的结果如图1 (g) 所示, 更新后的头表如图1 (g) 中的图表所示. 其中树上每增加一个新节点时, 都将新节点的地址维护在头表对应项的link 中, 便于以后检索树上该项对应的所有节点, 如图1 (c)»(e) 所示,为了图例看起来清晰, 图1 (f)»(g) 上没有画link对应的线.表1 高效用数据集实例Table 1 An example of high-utility transaction datasetTID Transaction1 (b, 3), (c, 3), (d, 3), (e, 1)2 (b, 2), (c, 2), (g, 3)3 (b, 3), (c, 4), (f, 1)4 (a, 1), (c, 5), (d, 2)5 (a, 2), (b, 1), (c, 2), (d, 2), (e, 3)6 (c, 3), (d, 1), (g, 2)7 (a, 2), (c, 6), (d, 10)表2 利润表(外部效用值)Table 2 A pro¯t tableItem Pro¯ta 8b 4c 2d 1e 3f 2g 12.2 从全局树上挖掘高效用模式的算法在第2.1 节中, 将一个数据集维护在一棵全局树上, 并得到一个头表后, 算法HUPM-FP 就可以采用模式增长方式从全局树上挖掘高效用模式, 算法详细过程如算法1 所示.算法1. Ming(T, H, X)输入. 全局树T, 头表H, 初始值为空的项集X.输出. 高效用模式集HUPs.Begin1)　For each item Q in H do　　　　/* 从头表H 的最后一项开始处理*/2)　　　If (Q.twu ¸ minUti) then3)　　　　　X= X ∪Q;　　　　　/* 判断项集X 是否是高效用模式*/4)　　　　　If (Q.Ut ¸ minUti) then5)　　　　　　　将项集X 添加到HUPs ;6)　　　　　End if　　　　　/* 因为项集X 的twu 值不小于最小效用值, 可以为项集X 产生一个子树sT 和子头表sH */7)　　　　　subTree(sT, sH, Q.link)8)　　　　　If (sH 不为空) then9)　　　　　　　Ming(sT, sH, X);10)　　　　　End if11)　　　　　将项Q 从项集X 中删除;12)　　　End if13)　　　将树T 上所有节点Q 上的Ulist 和SN 移到或累加到父节点;14) End forEnd算法1 中, 处理树T 上项Q 时, 为其构建子树步骤如下(下文也将通过一个实例来说明子树的构建过程):步骤1. 扫描树T 上所有节点Q 到根节点路径上项, 并从节点Q 上得到路径上各项的效用值和项Q 在该路径上的效用值, 即可以计算出项Q 和其余各项组合项集的效用值(Utility)、事务权重效用值(twu)、支持数(SN), 并将其保存子头表sH 中.步骤2. 将头表子头表sH 中twu 值小于最小阈值的项集删除, 剩余项按SN 从大到小排序, 并将头表中所有项的twu 值重新赋值为0.步骤3. 再次扫描树T 上每个节点Q 到根节点路径上项, 即可得到一项集X, 删除X 中不在头表sH 中的项, 并按头表sH 排序, 并从相应节点Q上得到处理后X 中各项的效用值和支持数, 同构建全局, 将处理后的X 添加到一棵新树sT 中, 同时修改子头表中相应项的twu 值, 树T 上所有节点Q处理完, 即得到新的子树和子头表.算法1 是从头表的最后一项依次往上处理所有项, 每处理完一项, 该算法就挖掘到包含该项的所有高效用模式, 因此在此后的挖掘过程中, 这些已经被处理过的项的效用信息就不需要了, 而头表(以及算法1 中创建的子头表, 下面详细介绍子树和子头表的创建过程) 中的twu 值只包含没有被处理过项的效用信息, 因此算法1 第2) 行可以直接判断是否会存在包含项Q 的高效用模式, 如果存在, 接下来判1620 自动化学报41 卷断项集X 是否是一个高效用模式.在头表和子头表的创建过程中, 头表中的字段Utility 存放项集X 的效用值, 因此在算法1 的第4) 行中可以直接判断项集X 是否是高效用模式.全局树和子树在创建过程中, 是将一个项集Y (或包含项相同的项集) 的效用信息存放到该项集在树上的最后一个节点上, 以便当创建新的子树时,可以从树上得到项集Y 中每项的效用值; 同时为了处理上层节点的时候也能得到效用值信息, 因此当算法1 处理完树上最下层节点后, 将效用信息传递到父节点(如图2 (d) 所示, 当项b 被处理后, 节点b上的效用信息被上传到父节点, 上传后的结果如图2 (e) 所示).这里以图1 (f) 中的全局树和头表为例, 说明算法1 构建子树和子头表的过程. 当处理头表(图1 (f)) 中项e 的时候, 因为头表中项a 的twu 值不小于最小阈值40, 因此可以为项集X = feg 创建子树和子头表, 构建步骤如下:步骤1. 分别从树T (图1 (f)) 中可以得到包含项a 的3 个项集及效用值(fc; d; eg, uList=f6, 1,3g, SN=1; fc; d; b; eg, uList=f6, 3, 12, 3g, SN =1; fc; d; b; a; eg, uList=f4, 2, 4, 16, 3g, SN = 1),统计项e 和其余各项组合的效用值(Utility)、事务权重效用值(twu)、支持数(SN), 如图2 (a) 中的头表sH1 所示; 同时也按第2.1 节中步骤2 处理头表sH1, 得到如图2 (b) 所示的头表.步骤2. 如果新头表不为空, 则创建子树. 依次处理步骤1 中的3 个项集, 首先将项集X (X 指步骤1 中得到的3 个项集) 按sH1 中的顺序排序(这里不需要再考虑项e); 然后, 同第2.1 节中的步骤3 的方法将有序的项集添加到一棵树上, 和第2.1节中的区别是, 这里的最后一个节点上还存放项集feg 在X 中的效用值, 这里记为Ux, 第一个项集fc; d; eg添加到树上后的结果如图2 (c) 所示; 当添加项c 时, 需要将项c 和e 在项集fc; d; eg 的效用值和累加到子头表twu 中; 当添加项d 时, 需要将项集fc; dg 和项e 在项集fc; d; eg 的效用值和累加到子头表twu 中; 更新后的头表如图2 (c) 所示. 同样的方法将其余2 个项集依次添加到树上, 并更新头表, 得到的结果如图2 (d) 所示. 当子树创建以后,按算法1 递归的处理子树和子头表(如算法1 的第9 行).2.3 算法分析HUPM-FP 将项集效用信息存放到最后一个节点, 这也保证算法HUPM-FP 可以从树上得到高效用模式的真实效用值, 而不是估计的效用值, 因此不需要产生候选项集. 同时在创建子树的时候, 可以得到相关项集中每项的效用值(如图2 中子树的创建),而不是估计值, 这也保证能计算到头表中各项(或项集) 的真实效用值和新的twu 值(新的twu 值不包含已经处理过的项和不在头表中项的效用值), 因此,头表中的twu 值都比原始创建的twu 小, 如图1 (f)和图1 (b) 中的头表twu 值所示, 最终使算法减少创建子树和子头表的次数.图2 子树构建实例Fig. 2 An example of constructing a sub-tree9 期王乐等: 基于模式增长方式的高效用模式挖掘算法1621根据第2.1 节中全局树的创建过程, 没有丢失任何项的效用值, 可以从全局树上计算到任何项或项集的效用值. 当为项集或项X 创建子树的时候,从全局树上得到了所有包含X 的项集及各项的效用值, 根据第2.2 节中子树的创建过程, 也可以得到任何包含项集X 的项集Y 的效用值.以上原因是算法HUPM-FP 时间效率提高的主要原因. 本文第3 节给出了实验结果.以下证明算法HUPM-FP 能挖掘到所有的高效用模式. 首先假设项集Z 是任一个高效用模式.因为Z 是一个高效用模式, 则其任一非空子集的twu 值都不会小于最小阈值, 根据算法HUPM-FP,项集Z 中的所有项都会出现在全局树对应的头表中, 当项集Z 中的第一个项Z1 被处理, 并创建子头表的时候, 因为项集Z1 和Z 中其余各项的组合的twu 值都不小于最小阈值, 因此这些组合的项集都会出现子头表中; 当处理新头表中项Z1 和Z2 组合,并为其创建新子头表时, 同样项集Z1, Z2 和Z 中其余各项的组合的twu 值都不小于最小阈值, 项集Z1,Z2和Z 中其余各项的组合对出现在新的头表中, 依次处理下去, 一定能得到项集Z 是高效用模式. 因此算法HUPM-FP 能挖掘到所有的高效用模式.3 实验3.1 实验对比算法和实验平台由于算法FHM 的时空效率高于算法UP-growth 和HUI-miner 等算法, 是目前算法效率较高的算法, 因此本文新提出的算法HUPM-FP 仅和FHM 做了对比分析. 这两个算法都是采用Java 编程语言实现, 实验平台: Windows 7, 10GB Mem-ory (Java heap size is 1.5 GB), Intel Core i5-3320CPU 2.60 GHz.3.2 实验数据本节采用了6 个经典的数据集对算法进行实验分析, 这6 个数据集的特征如表3 所示, 其中表3 中T10.I4.D100K 是由IBM 数据产生器合成的数据集, 其他5 个数据集都是真实数据集. 表3 中前5 个数据集不包含项的内部和外部效用值, 在本节的实验中, 也采用文献[14, 17¡19] 中方法, 事务项集中项的个数(内部效用值) 都是随机产生的一个小于10 大于0 的整数; 项的单位效用值(外部效用值) 也是随机产生的一个数值(大于等于0.0100, 小于等于10.0000); 原始数据集Chess、Mushroom、T10.I4.D100K 和Retail 是从FIMI 网站下载[22]. 数据集Chain-store 是Califor-nia 一家连锁超市产生的数据[23], 该数据集包含内部效用值和外部效用值. 数据的稀疏度值越大表示数据集越稠密, 越小表示数据集越稀疏.算法HUPM-FP 和FHM 都是精确的挖掘算法, 能从数据集中挖掘出所有的高效用模式, 两个算法挖掘的结果都是相同的, 因此本节实验只从算法的时空效率上进行了比较.3.3 算法的时空效率在高效用模式挖掘算法中, 算法运行时间会随着最小效用值(最小阈值) 的降低而增加. 第一个实验测试了不同最小阈值下, 算法的运行时间和内存消耗对比. 图3 给出了两个对比算法分别在6个不同数据集上运行时间对比. 由图3 所示, 算法HUPM-FP 的时间效率可以提高1 个数量级以上,甚至在部分数据集上(如T10.I4.D100K、Chain-store、Chess 和Mushroom), 算法FHM 在较低的阈值下都发生了内存溢出.本文给出的算法HUPM-FP 的时间消耗可以分为两部分, 一部分是创建全局树的时间消耗, 另外是从全局树上挖掘高效用模式的时间消耗. 用数据集Retail、Chain-store、Connect 进行测试时, 随着最小阈值降低, 尽管高效用模式个数有增加, 但是总体个数不多, 没有引起从全局树上挖掘高效用模式的时间消耗的突增, 因此在这三个数据集上随着阈表3 数据集特征Table 3 Dataset characteristics数据集项数事务项集平均长度事务项集总数稀疏度(%)Chess 76 37 3 196 48.68Mushroom 119 23 8 124 19.33Connect 129 43 67 557 33.33Retail 16 470 10.3 88 162 0.06T10.I4.D100K 1 000 10 100 000 1Chain-store 46 086 7.2 1 112 949 0.01561622 自动化学报41 卷(a) T10.I4.D100K (b) Retail(c) Chain-store (d) Chess(e) Mushroom (f) Connect图3 运行时间Fig. 3 Running time值的降低, 算法HUPM-FP 时间效率变化比较平稳. 根据数据稀疏程度越稠密和最小阈值越小, 算法FHM 挖掘过程中产生的项集的个数会越多, 从而导致算法的时间消耗越多, 如在稠密数据集上Con-nect 进行测试时, 尽管在不同的阈值下产生的高效用模式个数比较少(如取35% 时, 高效用模式个数为0), 但是算法FHM 在执行过程中需要计算大量项集的效用值, 导致算法时间消耗较大.在大型数据集Chain-store 上进行测试时, 因为该数据集是测试数据集中最稀疏的, 当最小阈值在0.12%»0.08% 之间, 算法FHM 过程中处理的项集个数较少, 同时该数据集平均长度是几个数据集中最小的, 因此时间效率相对其他数据集差异度不大, 如最小阈值为0.12 %, 算法HUPM-FP 所需要时间为51 秒, 而算法FHM 需要66 秒; 但是随着最小阈值的降低, 算法的时间效率提高程度会明显9 期王乐等: 基于模式增长方式的高效用模式挖掘算法1623增大(如最小阈值为0.07 %, 算法HUPM-FP 所需要时间为67 秒, 而算法FHM 需要307 秒; 当最小阈值取0.06% 时, 算法FHM 已经发生内存溢出了,因此在该实验中最小值只测试到0.06 %; 实际上最小阈值取0.06% 时, 数据集中仅包含196 个高效用模式, 可能不满足用户需要的模式个数).由于Java 虚拟机自行负责内存管理并对编程不透明, 这里得到的内存开销存在一定的误差. 本节实验中的内存消耗值的提取方法如下: 在算法运行过程中, 插入多个测试点, 在每个测试点上, 先强行删除算法运行过程中产生的垃圾节点, 再提出当时的内存消耗值, 并以这些值中的最大者作为当前算法的内存消耗值.图4 给出了两种算法分别在6 个不同数据集上内存消耗对比. 由图4 所示, 在不同的最小阈值下, 相对算法FHM, 算法HUPM-FP 的空间效率有一定的提高. 除在数据集T10.I4.D100K 上, 算法HUPM-FP 随着最小阈值的降低内存消耗基本上没有变化, 这是因为算法在创建全局树后的内存消耗最大, 但是在创建完全局树后, 就可以将原始数据集从内存中移除, 而算法之后创建子树所用空间不大于原始数据集所占用的空间, 因此算法消耗最大内存仍为创建全局树后所有的内存空间, 即算法HUPM-FP 随着最小阈值的降低内存消耗基本上没有变化. 而在数据集T10.I4.D100K 上, 算法HUPM-FP 创建子树所用空间大于原始数据集所占用的空间, 而且随着最小阈值的降低, 创建子树所用空间增加, 因此在该数据集上, 随着最小阈值的降低该算法所用空间增加. 同时从算法在同样情况下是否发生内存溢出也反映出本文提出的算法HUPM-FP 的空间效率较高.3.4 算法扩展性第2 个实验测试了在不同数据量下算法的运行时间和内存消耗性能, 实验结果如图5 和图6. 这里分别取了一个稠密数据集Connect 和稀疏数据集Chain-store 进行了实验. 在Chain-store 上, 分别取原始数据集中前200 000 条、400 000 条、600 000条、800 000 条和1 000 000 条数据进行了测试, 其中最小阈值设定为0.1 %; 在Connect 上, 分别取原始数据集中前20 000 条、30 000 条、40 000 条、50 000条和60 000 条数据进行了测试, 最小阈值设定为32 %. 由图5 和图6 所示, 随着数据量的增加, 本文给出的算法HUPM-FP 的时空效率增加平稳; 并且总体时空效率都优于算法FHM.(a) T10.I4.D100K (b) Retail(c) Chain-store (d) Chess1624 自动化学报41 卷(e) Mushroom (f) Connect图4 内存消耗Fig. 4 Memory consumption(a) Chain-store (b) Connect图5 运行时间Fig. 5 Running time(a) Chain-store (b) Connect图6 内存消耗Fig. 6 Memory consumption9 期王乐等: 基于模式增长方式的高效用模式挖掘算法1625算法FHM 同Apriori 算法采用层次方式产生高效用模式, 该算法的时间消耗主要受所有层中产生项集数量的影响和数据集大小的影响, 因此算法过程中产生的项集个数越多, 算法的时间消耗越多;对于同样数量的项集个数, 数据量越多, 算法时间消耗越多. 对于图6 (b) 中的实验, 由于数据集中数据分布不均匀, 这导致了随着数据量的增加, 在同样最小阈值的情况下, 算法过程中产生的项集个数没有单调的增加, 当事务数增加到30 000 时, 过程中产生的项集个数171 162 为最多, 而当事务数增加到60 000, 又降低到27 021 个项集(见表4 所示), 因此当事务个数为30 000 时, 算法FHM 的时间消耗比较大. 通过对算法的内存消耗对比, 发现两个算法的内存消耗都随着数据量的增加成线性增加(该测试结果不包含垃圾节点占用空间, 垃圾节点累积到一定程度, 系统会自动回收垃圾所占用的空间).表4 数据集Connect 上的高效用模式个数Table 4 Number of high utility pattern on Connect数据量高效用模式个数FHM 算法过程中产生的模式个数20 000 6 186 105 09430 000 17 048 171 16240 000 8 476 111 23850 000 644 38 35360 000 150 27 0214 结论和建议本文提出一个新的高效用模式挖掘算法HUPM-FP, 该算法主要采用模式增长的方式来直接挖掘高效用模式, 而不是从树上先得到候选项集,因此本文算法的时空效率都得到了提升. 并采用6个典型数据集(包含真实数据集、合成数据集、稀疏数据集合稠密数据集) 进行了实验验证, 实验结果也表明了本文给出的算法时间和空间效率都有提高,特别是时间效率提高较大; 其中在4 个数据集的实验中, FHM 算法都发生了内存溢出, 而本文给出的算法仍然能有效地执行, 这也说明了本文算法的空间效率优于算法FHM.同时通过实验, 发现HUPM-FP 的主要时间和内存消耗是在维护全局树和子树上, 特别是当指定最小阈值较大时, 时间和内存空间消耗仍然还是比较大, 因此下一步还可以针对此问题进行优化.References1 Zhang Xiao-Jian,Wang Miao, Meng Xiao-Feng. An accuratemethod for mining top-k frequent pattern under di®erentialprivacy. Journal of Computer Research and Development,2014, 51(1): 104¡114(张啸剑, 王淼, 孟小峰. 差分隐私保护下一种精确挖掘top-k 频繁模式方法. 计算机研究与发展, 2014, 51(1): 104¡114)2 Mao Yu-Xing, Shi Bai-Le. An incremental method formining generalized association rules based on extendedcanonical-order tree. Journal of Computer Research and De-velopment, 2012, 49(3): 598¡606(毛宇星, 施伯乐. 基于扩展自然序树的概化关联规则增量挖掘方法.计算机研究与发展, 2012, 49(3): 598¡606)3 Wu Feng, Zhong Yan, Wu Quan-Yuan. Mining frequent pat-terns over data stream under the time decaying model. ActaAutomatica Sinica, 2010, 36(5): 674¡684(吴枫, 仲妍, 吴泉源. 基于时间衰减模型的数据流频繁模式挖掘. 自动化学报, 2010, 36(5): 674¡684)4 Li Hai-Feng, Zhang Ning, Zhu Jian-Ming, Cao Huai-Hu.Frequent itemset mining over time-sensitive streams. Chi-nese Journal of Computers, 2012, 35(11): 2283¡2293(李海峰, 章宁, 朱建明, 曹怀虎. 时间敏感数据流上的频繁项集挖掘算法. 计算机学报, 2012, 351333(11): 2283¡2293)5 Pan Yun-He, Wang Jin-Long, Xu Cong-Fu. State-of-the-arton frequent pattern mining in data streams. Acta Automat-ica Sinica, 2006, 32(4): 594¡602(潘云鹤, 王金龙, 徐从富. 数据流频繁模式挖掘研究进展. 自动化学报, 2006, 32(4): 594¡602)6 Chen Yin, Shan Si-Qing, Liu Lu, Li Yan. Minimum-redundant and lossless association rule-set representation.Acta Automatica Sinica, 2008, 34(12): 1490¡1496(陈茵, 闪四清, 刘鲁, 李岩. 最小冗余的无损关联规则集表述. 自动化学报, 2008, 34(12): 1490¡1496)7 Krishnamoorthy S. Pruning strategies for mining high util-ity itemsets. Expert Systems with Applications, 2015, 42(5):2371¡23818 Lan G C, Hong T P, Tseng V S, Wang S L. Applying themaximum utility measure in high utility sequential patternmining. Expert Systems with Applications, 2014, 41(11):5071¡50819 Lin C W, Hong T P, Lan G C,Wong J W, LinWY. E±cientupdating of discovered high-utility itemsets for transactiondeletion in dynamic databases. Advanced Engineering In-formatics, 2015, 29(1): 16¡2710 Lin C W, Lan G C, Hong T P. Mining high utility itemsetsfor transaction deletion in a dynamic database. IntelligentData Analysis , 2015, 19(1): 43¡25511 Manike C, Om H. Sliding-window based method to discoverhigh utility patterns from data streams. Computational In-telligence in Data Mining. India: Springer, 2015. 173¡18412 Yun U, Ryang H, Ryu K H. High utility itemset mining withtechniques for reducing overestimated utilities and pruningcandidates. Expert Systems with Applications, 2014, 41(8):3861¡387813 Zihayat M, An A J. Mining top-k high utility patterns overdata streams. Information Sciences, 2014, 285: 138¡16114 Fournier-Viger P, Wu C W, Zida S, Tseng V S. FHM:faster high-utility itemset mining using estimated utilityco-occurrence pruning. Foundations of Intelligent Systems.Switzerland: Springer, 2014. 83¡9215 Yao H, Hamilton H J, Butz G J. A foundational approachto mining itemset utilities from databases. In: Proceedingsof the 4th SIAM International Conference on Data Min-ing (ICDM 2004). Lake Buena Vista, FL, United States:Springer, 2004. 482¡48616 Liu Y, Liao W K, Choudhary A. A two-phase algorithm forfast discovery of high utility itemsets. Advances in Knowl-edge Discovery and Data Mining: Proceedings of the 9thPaci¯c-Asia Conference, PAKDD 2005, Hanoi, Vietnam.Berlin Heidelberg: Springer-Verlag, 2005. 689¡6951626 自动化学报41 卷17 Erwin A, Gopalan R P, Achuthan N R. CTU-mine: an e±-cient high utility itemset mining algorithm using the patterngrowth approach. In: Proceedings of the 7th IEEE Inter-national Conference on Computer and Information Tech-nology. Aizu-Wakamatsu, Fukushima, Japan: IEEE, 2007.71¡7618 Ahmed C F, Tanbeer S K, Jeong B S, Lee Y K. E±cienttree structures for high utility pattern mining in incremen-tal databases. IEEE Transactions on Knowledge and DataEngineering , 2009, 21(12): 1708¡172119 Tseng V S, Shie B E, Wu C W, Yu P S. E±cient algo-rithms for mining high utility itemsets from transactionaldatabases. IEEE Transactions on Knowledge and Data En-gineering , 2013, 25(8): 1772¡178620 Tseng V S, Wu C W, Shie B E, Yu P S. UP-growth: an e±-cient algorithm for high utility itemset mining. In: Proceed-ings of the 16th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. Washington D. C.,United States: ACM, 2010. 253¡26221 Liu M C, Qu J F. Mining high utility itemsets without can-didate generation. In: Proceedings of the 21st ACM Interna-tional Conference on Information and Knowledge Manage-ment (CIKM 2012). Maui, HI, United States: Associationfor Computing Machinery, 2012. 55¡6422 Generator I D. IBM data generator [Online], available:http://www.almaden.ibm.com/software/quest/Resources/index.shtml, October 1, 201023 Pisharath J, Liu Y, Ozisikyilmaz B, Narayanan R,Liao W K, Choudhary A, Memik G. NU-MineBenchversion 2.0 scource code and datasets [Online], avail-able: http://cucis.ece.northwestern.edu/projects/DMS/MineBench.html, July 1, 2011王乐宁波大红鹰学院信息工程学院讲师. 2013 年获得大连理工大学博士学位. 主要研究方向为数据挖掘.E-mail: wangleboro@163.com(WANG Le Lecturer at the Schoolof Information Engineering, NingboDahongying University. She receivedher Ph. D. degree in computer applica-tion from Dalian University of Technology in 2013. Hermain research interest is data mining.)熊松泉宁波大红鹰学院信息工程学院副教授. 2012 年获得同济大学硕士学位.主要研究方向为数据挖掘和嵌入式系统.E-mail: yisan-sky@qq.com(XIONG Song-Quan Associateprofessor at the School of InformationEngineering, Ningbo Dahongying Uni-versity. He received his master degreein computer application from Tongji University in 2012.His research interest covers data mining and embedded sys-tems.)常艳芬宁波大红鹰学院信息工程学院讲师. 2009 年获得同济大学硕士学位.主要研究方向为数据挖掘和软件工程.E-mail: cyf511@163.com(CHANG Yan-Fen Lecturer atthe School of Information Engineering,Ningbo Dahongying University. She re-ceived her master degree in computerapplication from Tongji University in 2009. Her researchinterest covers data mining and software engineering.)王水宁波大红鹰学院信息工程学院教授. 1989 年获得兰州大学学士学位.主要研究方向为数据挖掘和软件工程.本文通信作者.E-mail: seawan@163.com(WANG Shui Professor at theSchool of Information Engineering,Ningbo Dahongying University. He re-ceived his bachelor degree in theoretical physics fromLanzhou University in 1989. His research interest coversdata mining and software engineering. Corresponding au-thor of this paper.)