1 引言
随着信息网络的快速发展和信息技术的广泛应用，客户关系管理系统、电子商务系统、监控系统等各类信息系统得以部署，从这些系统中可以获取大量的事务日志。事务日志一般包括活动内容、执行时间、参与者等信息[1]。通过对日志信息进行挖掘，可以发现在给定时间段内经常共同出现在同一地点的对象(用户、车辆、人群等)，而这些在时空上频繁共现的对象，即为伴随模式。伴随模式通常蕴含着事物间潜在的关系，因此伴随模式的挖掘被广泛应用于各类信息系统中。例如，利用学生卡管理系统的刷卡数据推断学生的时空共现，有利于构建和分析真实社会网络[1]；在车辆智能监测记录系统的过车数据中挖掘伴随车辆，有利于公安部门搜寻有结伴作案的嫌疑车辆[2]；基于移动通信基站 IP 数据的伴随人员推荐，有利于移动运营商向潜在的用户推荐服务；基于用户位置签到数据的伴随人群发现，有利于解决所在签到地点的资源配置和规划决策问题[3]。
现有伴随模式可分为轨迹伴随模式和频繁伴随模式，轨迹伴随模式是指在设定的时间长度阈值上，具有相同或相似运动轨迹的移动对象群体；频繁伴随模式是指在设定时间内频繁出现在多个不同数据流上的一组对象[4]。伴随模式挖掘方法可分为轨迹相似度算法和关联规则算法。
轨迹相似性算法一般用于挖掘轨迹伴随模式，该算法通过构建对象的移动序列，求得对象之间移动轨迹的最长公共子序列，当最长公共子序列的长度达到设定阈值，则判定这些对象存在伴随关系。赵新勇等[5]提出了基于车牌自动识别数据的最长公共子序列算法，以实现伴随车辆的检测和识别；Zheng 等[6]提出了一种基于密度聚类的伴随模式挖掘算法，用于发现蕴含在轨迹数据中的伴随模式；SHEIN 等[7]提出了一种微聚类算法用于发现轨迹数据流中的松散伴随模式。然而，轨迹相似度算法需要事先指定待比对的对象，才能通过其轨迹数据找出与其存在伴随关系的其他对象。若挖掘数据中所有的伴随模式，轨迹相似度算法会耗费大量的时间。
关联规则算法一般用于挖掘频繁伴随模式，相比轨迹相似度算法，关联规则算法能够高效地挖掘出数据中所有的伴随模式[8]，它将一定时间范围内一起出现的对象集作为事务集(伴随数据集)，通过所设定的支持度阈值，挖掘出存在伴随关系的频繁项集。常用的频繁伴随模式挖掘方法主要是利用滑动窗口或时间切片方法，来划定伴随数据集，再运用关联规则算法挖掘出伴随模式。王齐童等[9]提出了基于时空数据的滑动窗口方法用于划定伴随数据集，并将剪枝算法、贪心算法与 Apriori 技术相结合，对移动对象的伴随模式进行挖掘；朱美玲等[10]提出了基于车牌识别流数据的 PlatoonFinder 算法来挖掘伴随车辆，其中利用了滑动窗口划定伴随数据集；Liu 等[11]采用滑动窗口划定伴随数据集，并利用改进 SeqStream算法挖掘伴随车辆；陈瑶等[12]通过时间切片划定伴随数据集，并基于 Spark 计算框架的矩阵剪枝频繁项集挖掘算法发现伴随车辆；刘惠惠等[8]通过时间切片划定伴随数据集，基于 Spark 计算框架的 FP-Growth 算法挖掘伴随车辆。此外，还有学者采用聚类算法划定伴随数据集。YAO 等[13]采用 DBSCAN 算法对轨迹数据进行聚类，然后利用FP-Growth算法挖掘蕴含在轨迹数据的伴随模式；YAO 等[14]采用 HDBSCAN 算法，解决了传统 DBSCAN算法在处理密度不同的聚类问题时遇到的困难，再利用FP-Growth 算法挖掘伴随模式。虽然上述学者在伴随模式挖掘方面取得了一些成果，但是现有划定伴随数据集的方法主要应用于轨迹数据，并非事务日志数据；而且上述成果尚未利用伴随模式挖掘结果生成关联规则，无法进一步获得和分析对象间潜在的关联关系。
事务日志是一种大规模的历史静态数据，由于传统串行的滑动窗口算法和 FP-Growth 算法只能调用单一线程进行计算，无法充分利用多核配置的加速性能，随着数据规模的扩张，会导致挖掘伴随模式的时间急剧增加。目前计算机技术的快速发展促进了多核处理器与并行计算框架的发展与应用，然而现有的 Hadoop 和 Spark 并行计算框架不够轻量，难以对串行的算法进行并行化改造，不利于应用的迁移和扩展[15]，并且通信成本、负载平衡和 I/O 操作会导致运维费用较高[16]。为此，本文在共享内存的多核平台上，提出一种基于事务日志的伴随模式挖掘框架，该框架以 Java 的并发性和 Fork/Join 并行计算技术为基础，包括划定伴随数据集、频繁项集挖掘和关联规则挖掘3 部分。在划定伴随数据集部分，本文提出一种多核并行滑动窗口(parallel sliding window，PSW)算法，通过对事务日志数据库进行划分，能够并行地在各个子数据库上划定子伴随数据集 。
2 伴随模式挖掘框架
2.1 框架结构及问题描述
伴随模式挖掘框架结构如图 1 所示，由划定伴随数据集、频繁项集挖掘、关联规则挖掘 3 部分组成。
计算机职称论文参考
2.2 Fork/Join 并行技术
Fork/Join 框架是 Java 提供的一个用于并行执行任务的轻量级框架，能够充分利用多核 CPU 性能，提高程序的运行效率。该框架便于学习和实现，可以简化开发人员编写并行程序的工作[17]。
Fork/Join 采用分治思想[18]，通过递归分割大规模复杂的父任务，形成多个小规模简单的子任务；然后把各个子任务分配到不同的 CPU 线程中开始并行计算；最后合并所有子任务的执行结果，得到最终的任务结果。Fork/Join 可以根据问题规模的阈值来控制子任务的计算规模，采用线程池对工作线程进行统一管理，避免因线程的多次创建和关闭造成资源被不断消耗的问题。图 2为 Fork/Join 框架并行计算原理。
计算机职称论文怎么写
工作窃取算法是 Fork/Join 框架中一种用来实现负载均衡、提高运算性能的方法，其实际上是一种工作任务的调度方法。它的基本思想是当一个线程把自身任务队列中全部任务执行完毕后，该线程会从其他未执行完毕的线程任务队列中窃取任务执行，避免线程处于闲置状态，从而能够保证负载均衡，提高 CPU 的利用率，减少程序的处理时间。
在 compute（）方法中，首先需要判断事务数据库的规模是否小于阈值，本文用 start 与 end 的差值( 1start n ，1end n ， start end )来表示事务日志数据库的规模，用Threshold 来表示阈值。Threshold 的设定是决定 Fork/Join 框架执行时间的关键因素，其大小需要根据经验或实验分析来设定[19]，本文将 Threshold 设定为 1。如果差值小于等于阈值，则执行子任务，即执行 ComputePswPfp 方法；如果差值大于阈值，则对任务进行第一次分解。第一次分解完成后，程序会再次进行判定，如果 start 与 end 的差值仍大于阈值，则利用 invokeAll（）方法对分解后的任务进行递归分解，直到满足条件为止。
3 实验研究
3.1 实验配置
本文基于某城市某社区门禁刷卡数据进行实验，以2020 年 4 月-9 月全天采集到的门禁刷卡数据作为数据集，数据集共包含 12 万余条事务日志记录，涉及 930 位对象，14 个地点，实验前已对数据进行了清洗和隐私处理。实验在单台计算机上进行，处理器为 Intel Core i7-6700 3.40 GHz(4 核 8 线程)，内存大小为 8 GB，操作系统为 64 位 Windows10，JDK 版本为 1.8，采用 MySQL数据库存储事务日志记录。
3.2 实验内容和结果分析
为了验证本文所提出算法的时间复杂度，本文在不同数据规模下，使用 PDBSCAN、PTS、PSW 算法对事务日志数据进行划定伴随数据集实验，以及采用 PApriori算法、PFP-Growth 算法对伴随数据集进行频繁项集挖掘实验，实验结果如图 3 所示。在未标明参数的情况下，默认各算法的参数如表 1 所示。本文使用时间差来度量PDBSCAN 算法中两个对象之间的距离(相似性)，因此表中 PDBSCAN 算法的邻域半径单位为分钟。
为了探究并行度对本文所提出算法的影响，本文对算法在同一台计算机上的 CPU 可运行线程数进行了限制，以测试在同一记录数(记录数为 107,186 条)、不同并行度下算法运行时间，实验结果如图 4 所示。由图 4 可知，随着线程数的增加，PSW 算法、PFP-Growth 算法的运行时间均不断降低。因此对于计算规模较大的任务，较多的可运行线程数将可以更加显著地提高本文所提出的改进算法的效率。
3.3 关联规则可视化展示
为了帮助用户直观地从大量规则中筛选出有效的强关联规则，并分析出项与项之间的关联关系，本文利用SpringBoot 技术设计了一个基于 HTML 与 Echarts 的动态数据显示前端，使其成为关联规则挖掘结果可视化的承载体，关联规则的散点图和网图如图 7 和图 8 所示。实验中规则的支持度阈值设置为 0.0001，置信度阈值设置为 30%，提升度阈值设置为 10，共生成 502 条规则。支持度阈值很小的原因是本文频繁项集在伴随数据集中出现的频次一般很小。
在图 7 中，x 轴表示置信度，y 轴表示支持度，点的明暗表示规则的支持度计数，点的大小表示提升度。由图 7 可以看出所有规则在散点图中的分布，其中支持度和置信度较低，而提升度较高的规则集中于散点图的底部，这有助于用户调整支持度阈值、置信度阈值和提升度阈值，以筛选出相关性更高的规则。
图 8 只截取了关联规则可视化网图的一部分，没有包含所有的关联规则。图中圆点表示项，较大的圆形表示规则，圆形的大小表示规则的支持度计数，箭头表示规则内部项与项的关系。从图 8 可以看出不同规则之间如何共享一个前件，并可发现哪个前件是网图的中心，这有利于用户直观地发现规则中项与项之间一对一、一对多、多对多的关系。
4 总结
随着事务日志的数据规模不断扩大，传统基于滑动窗口的伴随数据集划定方法，以及传统 FP-Growth 算法，无法充分利用计算机的多核性能，导致挖掘伴随模式的时间急剧增加，为此本文提出基于 Fork/Join 并行技术的伴随模式挖掘框架。该框架包括划定伴随数据集、频繁项集挖掘和关联规则挖掘 3 部分。
本文所提出的伴随模式挖掘框架目前仅适用于静态历史的事务日志数据。下一步本文将研究如何实时地从事务日志数据流中挖掘伴随模式，拟利用分布式计算框架对数据流进行切片，并改进滑动窗口和关联规则算法，以满足实时挖掘伴随模式的需求。
参考文献（略）