并行动态位向量频繁闭合序列模式挖掘算法

计算机工程与科学

并行动态位向量频繁闭合序列模式挖掘算法

陈倩,刘云,高钰莹

(昆明理工大学信息工程与自动化学院,云南昆明 650500)

收稿日期:2017-11-22 修回日期:2018-01-24 出版日期:2018-10-25 发布日期:2018-10-25
基金资助:
国家自然科学基金（61262040）

A parallel dynamic bit vector based frequent

closed sequence pattern mining algorithm

CHEN Qian,LIU Yun,GAO Yuying

(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

Received:2017-11-22 Revised:2018-01-24 Online:2018-10-25 Published:2018-10-25

摘要/Abstract

摘要：

针对在时间和空间上都具有高计算成本的长序列数据库,一个更有效和更紧凑且可以完全提取信息的挖掘模式是当前的研究热点。提出一种并行动态位向量频繁闭合序列模式的挖掘算法（PDBVFCSP）,该算法采用多核处理器架构和DBV数据结构相结合的方式,有效加快了序列数据库的处理速度,并对搜索空间进行划分,尽早执行预处理序列的闭合检查,减少了所需的存储空间和挖掘频繁闭合序列模式的执行时间,克服了现有并行挖掘算法通信开销、同步和数据复制等问题。利用重新分配工作的动态负载平衡机制,解决处理器之间的负载均衡问题,最大限度地减少了CPU空闲时间。对DBVVDF算法和PDBVFCSP（24核）算法进行仿真比较,结果表明,PDBVFCSP算法在运行时间、内存使用和可伸缩性等方面都有较优的性能提升,且当内核数增加时,性能更优。

关键词: 数据挖掘, 闭合序列模式, 动态位向量, 多核处理器, PDBVFCSP算法

Abstract:

For long sequence databases, which have high computational costs both in time and space, a mining model that is more efficient and compact and can extract information completely is a current research hotspot. We propose a parallel dynamic bit vector based frequent closed sequence pattern mining algorithm (PDBV-FCSP), which combines the multicore processor architecture with the DBV data structure to effectively speed up the processing speed of the sequence database. The search space is divided, and the closed check of the preprocessing sequence is executed as early as possible, which reduces the required storage space and the execution time of mining the frequent closed sequence mode, and overcomes the problems of communication overhead, synchronization and data replication of the existing parallel mining algorithms. The dynamic load balancing mechanism for job redistribution is used to solve the load balancing problem of workloads among processors, thus minimizing the idle CPU time. Simulation results show that, compared with the DBVVDF algorithm, the PDBVFCSP algorithm has better performance in terms of running time, memory usage and scalability. And when the core number increases, the performance is better.

Key words: data mining, closed-sequence mode, dynamic bit vector, multi-core processor, PDBV-FCSP algorithm

陈倩,刘云,高钰莹. 并行动态位向量频繁闭合序列模式挖掘算法[J]. 计算机工程与科学.

CHEN Qian,LIU Yun,GAO Yuying.

A parallel dynamic bit vector based frequent

closed sequence pattern mining algorithm

[J]. Computer Engineering & Science.

[1]	赵琰, 马慧芳, 王文涛, 童海斌, 贺相春. 可靠响应表示增强的知识追踪方法[J]. 计算机工程与科学, 2024, 46(03): 535-544.
[2]	雷轩, 程光, 张玉健, 郭靓, 张付存. 基于电力网络态势感知平台的告警信息关联分析[J]. 计算机工程与科学, 2023, 45(07): 1197-1208.
[3]	王晨宇, 温浩珉, 郭晟楠, 林友芳, 万怀宇, . 面向快递员揽收到达时间预测的多任务深度时空网络[J]. 计算机工程与科学, 2023, 45(01): 136-144.
[4]	程小刚, 郭韧, 周长利, . 基于理性密码学的分布式隐私保护数据挖掘框架[J]. 计算机工程与科学, 2022, 44(10): 1781-1787.
[5]	王文涛, 马慧芳, 舒跃育, 贺相春. 基于上下文表示的知识追踪方法[J]. 计算机工程与科学, 2022, 44(09): 1693-1701.
[6]	刘云, 肖添. 网络日志数据中条件因果挖掘算法的优化研究[J]. 计算机工程与科学, 2021, 43(09): 1584-1590.
[7]	文凯, 许萌萌, 张许红, . 基于列表结构的加权可擦除项集挖掘算法[J]. 计算机工程与科学, 2021, 43(09): 1676-1683.
[8]	罗莉, 周宏伟, 周理, 潘国腾, 周海亮, 刘彬. 一种多核处理器直连接口QoS的设计与验证[J]. 计算机工程与科学, 2021, 43(04): 620-627.
[9]	熊中敏, 汪博, 陶然, 郑宗生, 陈明, . 一种基于主属性判定的关联规则挖掘约简算法[J]. 计算机工程与科学, 2021, 43(04): 738-745.
[10]	藏润强, 左美云, 郭鑫鑫. 基于Doc2Vec和BiLSTM的老年患者疾病预测研究[J]. 计算机工程与科学, 2020, 42(12): 2273-2279.
[11]	何望1,2，林果园1,2. 基于FP-Growth改进算法的云服务器故障数据分析[J]. 计算机工程与科学, 2020, 42(05): 770-775.
[12]	谭胜昔，贾金萍，赵斌，吉根林. 动态空间网络中的黑洞模式挖掘算法[J]. 计算机工程与科学, 2020, 42(02): 325-333.
[13]	何登平1，2，3，何宗浩1,2，李培强1,2. 基于Spark的并行化高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(10): 1723-1730.
[14]	陈胜发，贾瑞玉. 基于密度权重Canopy的改进K-medoids算法[J]. 计算机工程与科学, 2019, 41(10): 1823-1828.
[15]	何登平1,2,3，何宗浩1,2. 基于R-list的Top-K高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(07): 1318-1324.