郑会 何静 李鹏

摘 要： 医疗诊断与预测因数据量太大而需要流式存储，使得频繁项集挖掘出现耗时大，效率低下等问题。以解决这些问题为目的，研究了一种改进的基于大规模数据流的频繁项集挖掘方法，即增量式频繁项集挖掘方法。文章的重要结果是，该方法可结合历史数据与当前数据簇，快速求出近似全局支持度，并找出全局频繁项集集合。将该方法应用于Apriori算法上，通过实验得出了该增量式Apriori方法具有高效率的结论。

关键词： 医疗诊断与预测; 关联规则; 增量式算法; 数据流

中图分类号：G642          文献标识码：A     文章编号：1006-8228（2021）08-53-04

Research on the incremental Apriori algorithm for medical diagnosis and prediction

Zheng Hui， He Jing， Li Peng

（School of Computer Science， Nanjing University of Posts and Telecommunications， Nanjing， Jiangsu 210023， China）

Abstract： Medical diagnosis and prediction need streaming storage because of the large amount of data， which makes frequent itemset mining time-consuming and inefficient. In order to solve these problems， an improved frequent itemset mining method for large-scale data stream is studied， i.e.， the incremental frequent itemset mining method. The important result of this paper is that this method can combine the historical data with the current data cluster to quickly find out the approximate global support， and find out the set of global frequent itemsets. Applying the method to Apriori algorithm， the conclusion is obtained through experiments that the incremental Apriori algorithm has a high efficiency.

Key words： medical diagnosis and prediction; association rule; incremental algorithm; data stream

0 引言

在疾病診断与预测上，关联规则算法有不可替代的优势，但在求解大数据问题时，该算法通常执行效率低下，其根本原因在于频繁项集挖掘过程耗时较长[1]。本文通过研究频繁项集挖掘算法的现有问题，并为了避免重复扫描大规模数据，本文采取了增量式Apriori方法的构建方案，该方法通过持续性因子筛选出需要保存的局部频繁项集统计信息;提出了近似全局支持度值的计算过程，以保证增量式频繁项集的准确率;同时提出了增量式频繁挖掘算法的求解步骤。

1 现有问题

医疗数据具有如下特点：①数据来源广泛，比如数据来源可能包括诊断数据、医疗数据与体检数据等[2];②数据更新频繁发生，每当个体进行新的诊断、治疗或体检时，都会产生新的数据并被存储到相关疾病数据库中。因此，医学数据库会持续地进行更新[3]。

随着医学数据库的更新，训练出的诊断/预测模型也应随之变化，这样才能使诊断/预测模型的实时性得到保证[4]。对于如何保持该实时性，理想化的做法是每当有新的记录，计算机就重新建模，基于新模型挖掘频繁项集与关联规则[5]，然后利用新的关联规则对个体进行疾病诊断与预测[6]。但这个理想化做法容易出现以下几个问题。

问题1：随着医学数据规模的不断增加，医学数据库的量级也在持续增大，使得构建模型所需时间不断延长。

问题2：当医学数据库中数据达到某个量级时，模型会因为耗时太长而丧失时效性。

问题3：频繁地建立疾病诊断/预测模型，会增加计算资源和人力等相关成本。

由此得出，根据数据更新来频繁地更新并持续地建模并不现实。为此，如何构建具有实时性、高效性的增量式模型[8]就是本文要解决的一个重要问题。

2 方法构建方案

在医学领域上采用关联规则算法具有明显的优势，关联规则算法可以挖掘出数据潜在关系与关联[7]，从而可以在医学领域上协助实现医疗诊断与预测[8]。但是，其在应用中仍存在一些不足。

⑴ 没有解决频繁项集挖掘过程中效率低下的问题。

⑵ 并不适用于对大数据问题的处理，特别是在处理增量式医疗大数据时还未发挥应有的作用。

针对频繁项集挖掘在处理大数据时效率低下的问题，本文将阐述如何对算法进行改进，探讨实现大数据增量式的频繁项集挖掘方法，以此来提升关联规则挖掘算法效率。

2.1 方法主要目的

本文通过研究增量式频繁挖掘算法，以期达到如下两个目标。

目标1：在每一批次数据簇中，都能直接保留全局频繁项集到候选频繁项集集合;

目标2：成功过滤掉其他所有非潜在的全局频繁项集，从而实现对存储空间的最大优化。

2.2 研究内容与创新性

本文采取近似的频繁项集挖掘方法，该方法主要是通过对每个批次数据簇中的局部频繁项集与潜在全局频繁项集的存储，在此基础上获得全局支持度计算所需的数据统计摘要信息，从而达到尽可能地保留全局频繁项集的目的。为获得这些全局支持度值的统计信息，需要做到以下几点。

⑴ 对于某一批次中被认定为频繁的项集，直接保存该局部频繁项集及其支持度信息。

⑵ 对于当前批次数据簇中非频繁而有潜力的项集，即潜在的全局频繁的项集，同样保存该潜在频繁项集及其支持度信息。

⑶ 对于当前批次数据簇中非频繁且无潜力的项集，直接忽略其支持度信息。

由此，本文研究的增量式频繁项集挖掘（增量式Apriori）算法中，只需对每个批次数据簇分别进行局部频繁项集挖掘，就能得到潜在的全局频繁项集，根据全局候选频繁项集的相关统计信息即可计算得出全局支持度值，从而确定全局频繁项集。本文还分析近似算法的误差估计，进一步限制近似算法的误差。

3 方法的求解步骤

本文通过对增量式频繁项集挖掘方法的构建，来实现数据流数据频繁项集挖掘方法，以下对该方法的具体步骤作详细说明。

3.1 批次频繁项集与持续性因子

持续性因子k表示，如果某项集在某一批次数据簇中是频繁的，则该项集的信息将至少被统计k 次，具体如下。①如果一个项集在第i批次数据簇中是频繁的，那么即使它在之后批次的数据簇中不是频繁的，候选全局频繁项集还是会对其相关信息进行保存与统计，直到第i+k批次数据簇。②如果该项集在后续的k个批次的数据簇中都不是频繁的，则该项集在第i+k+1批次中将被视为普通项集。根据②，如果当前项集在第i+k+1个数据簇中是频繁的，那么需将其支持度计算所需统计信息进行保存;但如果该项集在第i+k+1个数据簇中是不频繁的，那么无须对其全局支持度计算相关信息进行保存。当然，在第i批次到第i+k+1批次个数据簇之间的每个数据簇中，若该项集出现局部频繁，则需要将局部频繁项集保存为候选频繁项集，同时重新赋值当前持续性因子k ，并对接下来的k个数据簇项集相对应的频繁信息进行累计，并持续地继续统计其信息。

持续性因子k可以扩展到根据数据簇批次不同而動态调整。一个简单的办法是根据不同批次数据簇进行数据欧式距离测算，当相邻两个数据簇欧式距离越大，则加大持续性因子;反之，则减少持续性因子。这里，根据数据分布来变化的持续性因子是本文提出的增量式算法的一个创新。

历史数据簇频繁项集集合重点对历史全局候选频繁项集集合进行描述，具体来说：①针对当前批次数据簇之前全部批次数据簇组成的数据集合，对这些数据集合的局部频繁项集集合进行挖掘，并存储其所有支持度相关信息，用以计算项集的全局近似支持度值;②在频繁项集挖掘算法，如Apriori算法的基础上，持续进行频繁项集挖掘。

3.2 支持度计算与近似方法误差估计

假设m_1个频繁的数据簇中支持度值的总和为s_1，并对剩下的所有非频繁数据簇中的统计信息进行统计，并在此基础上设m_2个数据簇中的支持度值总和为s_2。而m_2作为所有项集中的非频繁项集数据簇数，其值远远小于所有项集中频繁项集数据簇数值，此时有：

m_2m_1

则该项集的全局支持度可近似地表示为：

ASupp= 1/m （s_1+（（m-m_1 ）×s_2）/m_2 ） ⑴

其中，ASupp表示的是近似支持度（approximate support）。

由于公式⑴是一个近似计算公式，因此必然会存在误差，为证明该公式的准确性，本节重点对近似算法的误差进行统计，从而对该算法进行更客观的评估。本节通过支持度值的上界与下界进行分析，实验对近似公式⑴的误差进行估计。在本文中，Supp表示支持度（Support）的统计值。

假设支持度阀值（最小支持度值）为μ ，可得近似支持度的上界，有：

Supp ≤?Supp=（s_1+s_2+（m-m_1-m_2）×μ）/m ⑵

同时得其支持度的下界，有：

Supp≥▁Supp= （s_1+s_2）/m ⑶

于是，近似支持度值计算方法的误差范围有如下表示：

|ASupp-Supp|≤?Supp-▁Supp

=（m-m_1-m_2）×μ/m ⑷

基于对当前所有频繁项集信息的整理，可得到一个关于频繁项集的简单估计即该项集的数据簇数量之和为m_1+m_2，且该值接近于数据簇总数m。因此，当m→∞时，误差估计自然趋近于零;反之亦然，当m_2→∞时，则该项集的支持度近似值出现以下情况：①或许不能收敛;②或许能收敛但收敛于的数值低于阀值μ。如果非频繁项集的近似支持度可以收敛，则其对应为频繁的m_1个数据簇的支持度值是收敛的，且收敛于数据簇总数量m。

增量式Apriori方法的具体步骤如图1所示。

⑴ 根据模型参数选择数据批次大小与持续性因子值;

⑵ 对于数据流批量数据中接收一批次的数据作为当前数据簇;

⑶ 计算当前批次数据簇与前一批次数据簇之间的欧式距离;当前批次数据为第一批次数据簇时，欧式距离默认赋值为最小值0;

⑷ 根据持续性因子抽取已处理过的数据摘要信息，包括历史数据簇中支持度信息，从而获得m_1，s_1，m_2，s_2的值;

⑸ 结合前面的数据摘要信息，对当前批次数据簇进行频繁项集挖掘;

⑹ 输出当前频繁项集结果，如果有一下批次数据则重复上述步骤⑵-⑸。

3.3 方法实验分析

本节主要进行方法实验分析。实验数据主要以数据生成器所生成的随机数据集为基础，将该数据集应用到Apriori方法[9-10]中。在本节实验中，仅展示出算法的固定持续性因子的情况。

实验涉及的参数：持续性的因子k=3;最小支持度阀值μ=0.10。

如图2所示，随着数据簇批次的增多，总体数据量会相应增加，传统的Apriori算法需要在每次对数据簇批次重复扫描的基础上实现对全局频繁项集的挖掘，而利用增量式Apriori方法却只需一次扫描数据，因此可节省大量时间，提高算法效率。本节实验设定数据簇总批次为30。实验过程中，不但对每一批次算法消耗时间进行了对比，同时也对比了全部批次算法消耗时间的平均值，并将其作为算法对比度量之一。在图2中，当数据批次数大于15时，增量式Apriori方法耗费时间明显低于其他对比方法。这说明数据量越大，增量式的方法的优势越明显。

4 结束语

为了解决关联规则与频繁项集挖掘求解大规模数据耗时较长的问题，本文展示了一种增量式频繁项集挖掘方法并将其作用于Apriori，即增量式Apriori。通过对持续性频繁项集挖掘算法与近似的计算全局支持度算法的整合，来计算近似全局支持度值，从而找出全局频繁项集。通常来说，数据量级越高，增量式频繁项集挖掘方法找出的频繁项集集合，与真实频繁项集集合的结果越趋于一致。通过数据生成器模拟疾病相关数据，基于这些数据进行实验对比分析，结果表明，相比标准Apriori算法，增量式Apriori方法具有效率高及性能稳定等优点。

参考文献（References）：

[1] 古良云.频繁模式挖掘方法的研究[D].江南大学硕士学位论文，2020.

[2] 李力恒，王晓磊.智能可穿戴式医疗设备在医疗数据信息安全中的应用[J].自动化与仪器仪表，2020.3.

[3] 张玥，倪珺珉，王坚，宋小康，赵宇翔.基于关联规则挖掘的健康信息学主题分析——以dHealth会议为例[J].信息资源管理学报，2020.10（6）：90-100

[4] 陈晨，王妮，黄艳群，周阳，李盛俊，陈卉.基于居民健康大数据的肥胖与常见慢病关联规则分析[J].北京生物医学工程，2020.39（4）：406-411

[5] 柯文俊，高金华，沈华伟，刘悦，程学旗.基于改进Apriori算法的问题模板无监督抽取方法[J].中文信息学报，2020.34（10）：76-84

[6] 张千，方丽华，王庆玮，孙晓，梁鸿，张万义.基于机器学习的疾病诊断模型研究[J].计算机与数字工程，2020.48（7）：1705-1709

[7] 王青松，姜富山，李菲.大数据环境下基于关联规则的多标签学习算法[J].计算机科学，202047（5）：90-95

[8] Mohapatra Ankita， Sangita Khare， and Deepa Gupta.

Analysis of Tuberculosis Disease Using Association Rule Mining.In Advances in Artificial Intelligence and Data Engineering[J]. Springer， Singapore，2021：995-1008

[9] Wang Xiaoli， KuiSu， and Zhanbo Liu. Analysis of Diabetic

Association Rules Based on Apriori Algorithms.In Data Processing Techniques and Applications for Cyber-Physical Systems （DPTA 2019）[J].Springer，Singapore，2020：555-563

[10] Wang Chunxia， and Xiaoyue Zheng. Application of

improved time series Apriori algorithm by frequent itemsets in association rule data mining based on temporal constraint[J].Evolutionary Intelligence），2020.12（1）：39-49

收稿日期：2021-03-24

基金項目：本课题得到江苏省科技支撑计划项目（BE2019740）; 江苏省高等学校自然科学研究项目（18KJA520008，20KJB520001）; 江苏省高校研究生科研创新计划项目（SJKY19_0761，SJKY19_0759，KYCX20_0759）

作者简介：郑会（1985-），女，河北廊坊人，博士，博士后，主要研究方向：数据挖掘，电子健康。

通讯作者：李鹏（1979-），男，福建长汀人，博士，教授，主要研究方向：高等教育研究、信息网络。