融合Apriori优化算法与Relim算法的抑郁症用药规律挖掘

王慧敏　龚庆悦　胡孔法　邵荣强　陈燕

摘 要：为明确中医治疗抑郁症用药规律，融合Apriori优化算法与Relim算法，采用数据挖掘技术进行分析。针对传统Apriori算法频繁扫描数据库从而生成大量候选项集的缺点，改变其原有剪枝方式以减少扫描次数。将改进后的Apriori算法与无需产生候选项集的Relim算法就中医治疗抑郁症的方剂数据进行关联规则分析，并绘制两个算法时间效率图。结果发现，两种算法在挖掘药物频繁项集与关联规则的结果基本相同，通过分析发现，中医常以疏肝、理气、补肾、滋阴等药物为主治疗抑郁症。改进后的Apriori算法可降低数据库扫描次数，较传统Apriori算法运行效率有所提高，Relim算法在空间利用率和时间执行率上均略优于改进后的Apriori算法。两种算法挖掘结果体现出中医治疗抑郁症注重疏肝理气、补肾滋阴、调理气血等特点。基于关联规则的方法可作為中医用药规律分析的重要工具。

关键词：关联规则;Apriori优化算法;Relim算法;抑郁症

DOI：10. 11907/rjdk. 192722

中图分类号：TP391   文献标识码：A                文章编号：1672-7800（2020）003-0190-04

Combining Improved Apriori Algorithm and Relim Algorithm to

Mine Medication Rules for Depression

WANG Hui-min，GONG Qing-yue，HU Kong-fa，SHAO Rong-qiang，CHEN Yan

（School of Artificial Intelligence and Information Technology in Nanjing University of Chinese Medicine， Nanjing 210023， China）

Abstract：
Improved Apriori Algorithm and Relim Algorithm were combined and  data mining technology was employed to identify the medication rules for depression. Aiming at the shortcomings of frequently scanning the database in the traditional Apriori algorithm to generate a large number of candidate itemsets， the original pruning method was changed to reduce the number of scans. The improved Apriori algorithm and Relim algorithm without generating candidate itemsets were used to mine the prescription data of traditional Chinese medicine for treating depression and compare the performance of the two algorithms by time efficiency graphs. The two algorithms are basically the same in mining frequent itemsets and association rules of drugs. Through analysis， it is found that traditional Chinese medicine often treats depression by treating drugs such as soothing liver， regulating qi， nourishing kidney and nourishing yin. The improved Apriori algorithm can reduce the number of database scans， which improves the operating efficiency of the traditional Apriori algorithm. The Relim algorithm is slightly better than the improved Apriori algorithm in terms of space utilization and time execution rate. The mining results of the two algorithms both reflect the characteristics of traditional Chinese medicine in the treatment of depression， such as dispelling liver and regulating qi， nourishing kidney-Yin， and regulating qi and blood. The method based on association rules can be an important tool for the analysis of traditional Chinese medicine.

Key Words：
association rules; improved Apriori algorithm; relim algorithm; depression

0 引言

数据挖掘旨在发现数据库信息潜在的交叉联系与隐含知识。作为数据挖掘最重要的分支之一，关联规则挖掘可识别给定数据库中项目之间的关联关系和频繁模式[1]。

它由两个子任务组成：先根据某个预定阈值发现频繁项集，再生成满足约束条件的关联规则[2]。关联规则不仅在商业数据分析中发挥重要作用，在其它领域也得到广泛应用[3-5]。

在中医药领域，关联规则可用于中医组方规律挖掘、中医文献挖掘及临床病历挖掘等研究，以辅助中医诊断，为临床诊治提供参考[6-8]。如赵平等[9]采用关联规则挖掘中医文献中治疗肾性贫血方剂的组方规律;周琳等[10]对海量的中医临床数据和古籍医案进行挖掘以提取有用的疾病诊治知识，提高医疗服务准确度和效率。大多数研究均采用经典Apriori算法，虽然挖掘结果有一定借鉴意义，但其挖掘过程耗时费力。为提高挖掘工作效率，本文采用优化Apriori算法与不需要产生候选项集的Relim算法对中医治疗抑郁症用药规律进行分析。

尽管经典Apriori算法性能无法与最先进的深度优先方法相提并论[11]，但Apriori算法始终被视为重要的关联规则挖掘算法。因为其基本思想是找到所有频繁项集，算法结构简单且易于实现。而基于深度优先的算法不仅需面对FP树构造的复杂性，且存储节点记录会消耗内存。为提高Apriori算法工作效率，许多研究者提出了改进方法。Bhandari等[12]提出将Apriori算法和FP-growth相结合以改善Apriori算法在重复扫描数据库时的局限性;Yang等[13]提出通过添加事务权重的概念并生成事务布尔矩阵，以便扫描数据库一次即可达到目标;Yang等[14]在网页挖掘日志的问题上利用自动化的概念减少Apriori算法扫描数据库的时间;而Borgelt[15]提出的Relim算法不需要生成候选项集即可挖掘频繁项集，大幅提高了挖掘过效率，其速度并不慢于FP-growth算法，却不需要建立复杂的频繁树结构，通过事务链表组的方式进行挖掘，可节省较大空间。

本文以避免重复扫描数据库和减少候选项集的生成为目标，对经典Apriori算法进行改进，以提高算法效率。优化后的Apriori算法较原算法在运行速率上有较大提升，并将其与Relim算法在挖掘中医治疗抑郁症的药物组合上的表现作比较。

1 相关算法

1.1 Apriori算法

Apriori算法实质是根据候选项集找频繁项集[16]。算法利用频繁项集性质的先验知识，对整个目标事务数据库采用逐层搜索的迭代方法进行挖掘，以找出所有满足条件的频繁项集，最后通过对获得的频繁项集进行计算生成关联规则[17]。其算法流程如下。

Step 1：扫描整个数据集D，并计算各数据项i在D中出现的频次，根据公式（1）设置最小支持度并找出满足最小支持度阈值的项集，即频繁一项集[L1]。将剩下的不满足最小支持度的数据项删除。

Step 2：连接步，通过[Lk-1]与自身连接产生候选k项集的集合，记为[Ck]。

Step 3：剪枝步，扫描数据集，确定[Ck]中每个候选项集的频次，其中不小于支持度阈值的候选项集即为频繁项集，从而确定[Lk]。由此可知，[Ck]为[Lk]的超集，根据支持度度量反单调性可知，如果一个集合不是频繁项集，则其所有超集都不是频繁项集，可将这样的非频繁候选项集直接从[Ck]中剔除，即为对k项集的剪枝操作。

Step 4：重复迭代Step2和Step3操作，直至不再出现更高阶的频繁项集。

Step 5：对上述步骤产生的所有频繁项集进行计算得出关联规则，再根据满足最小支持度阈值和最小置信度阈值条件的频繁项集产生强关联规则。置信度如式（2）所示。

Step 6：输出所有满足条件的频繁项集和强关联规则。

1.2 Apriori优化算法

由于原始算法在剪枝这一步筛选候选频繁k项集时，每判断一次k-1维子集是否存在于[Lk-1]中，就需扫描一次频繁k-1项集。序列越多，遍历时间越长。该过程非常耗时且会产生大量候选频繁项集，影响算法效率[18]。为避免重复扫描数据集带来的不利影响，对算法进行优化，在整个剪枝过程中只扫描一次[Lk-1]。对于[Lk-1]中任意元素A，判断A是否为[Ck]中元素B的子集。如果是，则将B的计数加1。示例说明如表1所示。

根据表1所示，此时k=4，直接将[Lk-1]中的元素与[Ck]中的元素进行比较，只有[ Ck]中{[i1]，[i2]，[i3]，[i4]}的计数为4，则将它记为频繁候选项集，得到[C"k={i1，i2，i3，i4}]。而原算法需先得出[Ck]中各元素项数为k-1项的子集，如要判断元素{[i1]，[i2]，[i3]，[i4]}，要先得到它的子集{[i1]，[i2]，[i3]}，{[i2]，[i3]，[i4]}，{[i1]，[i3]，[i4]}，{[i1]，[i2]，[i4]}，然后判断这些子集是否均为[Lk-1]中的元素，如果是则保留，否则删除，计算复杂度明显高于优化后的算法。

1.3 Relim算法

受FP-growth算法的启发，Relim算法基本思想与其相似，采用递归消除的方法，在不产生候选项集的情况下对频繁项集进行挖掘[19]。但不同的是，Relim算法無需构建频繁项集树，而是将数据分到单个链表中，由组成的事务链表组进行频繁项集挖掘。其算法流程如下所示。

Step 1：扫描整个数据集，计算每个数据项频次，并按照频次大小递增排列各项，得到项集I。

Step 2：再次掃描数据集，设置最小支持度阈值min_sup，将小于min_sup的数据项从各事务中删除，并将事务中的数据项按其频次进行递增排序。

Step 3：为新事务列表中的所有数据项创建一个单向数据链表，其中每个项均将得到一个支持度计数器和一个指针。计数器的值描述为以该项为首项的事务总数，指针则用来保存相关事务的关联信息，以此组成事务链表。再将所有事务链表按I的顺序得到一个事务链表组。

Step 4：先从以频次最小的项为首的事务链表开始扫描，输出该链表中支持度大于min_sup的项集。扫描完成后将该链表计数器值归为0，再删除该链表。

Step 5：构造一个用于保存除原首项外，以后继项为新首项的事务关联信息数据链表组，其结构与Step3中的事务链表组相似，将其称为原首项前缀事务链表组。

Step 6：将前缀事务链表组与相应的被删除的事务链表组合并组成一个新的事务链表组。

Step 7：根据Step4—Step6所述，递归地对新事务链表组中的第2个事务链表进行挖掘。

Step 8：直至挖到最后一个事务链表，指针指向空数组时停止挖掘，并输出频繁项集。

2 抑郁症用药规律挖掘

本文通过使用改进的Apriori算法与Relim算法在中医治疗抑郁症药物组合方面进行分析，并比较两种算法性能。研究结果可分为中药关联规则挖掘结果与算法比较结果两方面，整个实验过程使用Python编程实现。

2.1 数据预处理

本文中医治疗抑郁症方剂数据来源于《中医方剂大辞典》[20]，通过以“肝气郁结”、“忧思抑郁”、“思虑过多”、“情绪不安”、“气机郁滞”等为检索词，筛选出237首有关中医治疗抑郁症方剂。对该数据进行预处理，删除所选方剂中没有明确药物组成和药物主治功能的方剂数据，并将同一种药物的不同名称统一为一个名称，修改不规范的药名。如将“苡仁”、“薏苡”统一为“薏苡仁”，“杭白芍”、“炒白芍”统一为“白芍”等。最终将数据整理成符合条件的方剂共234首，中药共354味。

2.2 关联规则挖掘结果

由上述算法流程可知，改进Apriori算法与Relim算法挖掘方式不同，需分别建立适合其挖掘的数据库。设置支持度阈值为0.07，置信度阈值为0.6，经两种算法挖掘的频繁项集结果见表2、表3，生成的关联规则结果见表4。

由表2—表4可看出，两种算法挖掘出的药物频繁项集和关联规则基本相同，相互印证了算法结果可靠性，均体现了中医在治疗抑郁症上的用药规律。如常用药柴胡、川芎、木香、陈皮等可以调理气血，改善抑郁症患者整体“闭塞”状态;频繁药人参与白术均是重要的补气药物，两药相配可培元固本，调补患者因长期抑郁状态带来的身体机能损耗，增强体力。

2.3 算法对比讨论

从算法结构来看，Apriori算法通过产生候选项集进而确定频繁项集，改进的Apriori算法并没有改变原算法结构。而Relim算法无需建立频繁项集树，不需要产生候选项集，是通过建立事务链表组产生频繁项集的。

从空间利用率来看，Apriori算法由于会产生候选项集，因而要额外占用部分内存，而Relim算法在挖掘过程中采用建立事务链表组的方法，每挖掘完一个事务链表就将该链表删除，立刻释放内存。所以，Relim算法空间利用率优于Apriori算法。

从时间效率来看，如图1所示，最小支持度越小，各个算法花费时间越多且Apriori原算法效率最差。在支持度阈值设置较低情况下，3种算法均会产生大量频繁项集，由于Apriori原算法需重复多次扫描数据库，而改进后的Apriori算法只需扫描一次数据库，运行时间比原始算法明显缩短。Relim算法不需要多次扫描数据库，也无需产生候选项集，通过事务链表组活动，运行速率最快。当支持度阈值增大，能产生的频繁项集减少，各算法效率逐渐接近。

3 结语

本文采用两种不同的关联规则算法对中医治疗抑郁症用药的组方规律进行挖掘，并比较算法性能。由上述实验可知，两种算法挖掘结果可相互印证，所挖掘的频繁项集和产生的关联规则基本相同，均体现出中医治疗抑郁症注重疏肝理气、补肾滋阴、调理气血等特点。从算法性能上来看，改进的Apriori算法大幅提高了原算法运行速率，节省了大量运行时间，而Relim算法在空间利用率与时间执行率上均略优于改进后的Apriori算法。下一步可考虑引入更多算法比较研究中医在其它病症上的用药规律，除了方剂药物特性外，还可从剂量、炮制、药物性味归经等方面入手，拓宽研究思路。

参考文献：

[1]SHARMA S ， BHATIA S. Analysis of association rule in data mining[C]. The Second International Conference，2016：1-4.

[2]YUAN X. An improved Apriori algorithm for mining association rules[C]. Guilin：International Conference On computer Science and Artificial Intelligence，2016.

[3]YAO L， XU Z， ZHOU X， et al. Data science and digital business：synergies between association rules and collaborative filtering in recommender system：
an application to auto industry[M]. Berlin：Springer，2019.

[4]徐哲炜，郑成航，张涌新，等. 基于改进关联规则算法的燃煤电厂脱硫系统工况参数优化[J]. 中国电机工程学报，2017（15）：138-144，311.

[5]HUH J H，KIM H B，KIM J. A method of modeling of basic big data analysis for Korean medical tourism：
a machine learning approach using Apriori algorithm[C]. Singapore：  International Conference on Information Science & Applications，2017.

[6]王倩，金卫，生慧. 两种关联规则算法在中医药治疗方面的应用及比较[J]. 吉林中医药， 2015（1）：14-17.

[7]苏克雷，叶娟，张业清，等. 基于数据挖掘的江浙沪名老中医膏方医案关联解析[J]. 中华中医药杂志， 2019（6）：2721-2727.

[8]张奇，李涛，许勇钢，等. 基于关联规则挖掘治疗多发性硬化所用中药对患者T细胞亚群的影响[J]. 中国中西医结合杂志，2016（4）：425-429.

[9]趙平，张法荣. 肾性贫血方剂组方规律中医文献分析[J]. 山东中医药大学学报，2019（2）：25-29.

[10]周琳，刘树春. 关联规则在中医临床信息分析中的应用[J]. 中国中医药图书情报杂志， 2014（4）：13-15，21.

[11]BORGELT C. Frequent item set mining[J]. Wiley Interdisciplinary Reviews：Data Mining and Knowledge Discovery，2012，2（6）：437-456.

[12]BHANDARI A，GUPTA A，DAS D. Improvised Apriori algorithm using frequent pattern tree for real time applications in data mining[J]. Procedia Computer Science，2015，46：644-651.

[13]YANG Q，FU Q， WANG C， et al. A matrix-based Apriori algorithm improvement[C].Guangzhou：2018 IEEE Third International Conference on Data Science in Cyberspace， 2018.

[14]YANG J，HUANG H，JIN X. Mining web access sequence with improved Apriori algorithm[C]. 2017 IEEE International Conference on Computational Science and Engineering （CSE） and IEEE International Conference on Embedded and Ubiquitous Computing （EUC）， 2017：780-784.

[15]BORGELT C. Keeping things simple：
finding frequent item sets by recursive elimination[C]. International Workshop on Open Source Data Mining：Frequent Pattern Mining Implementations，2005：66-70.

[16]陈方健，张明新，杨昆. 一种具有跳跃式前进的 Apriori 算法[J]. 计算机应用与软件，2015（3）：34-36.

[17]曾子贤，巩青歌，张俊. 改进的关联规则挖掘算法——MIFP-Apriori算法[J]. 科学技术与工程， 2019（16）：216-220.

[18]陈志飞，冯钧. 一种基于Apriori算法的优化挖掘算法[J]. 计算机与现代化， 2016（9）：1-5.

[19]VIJAYARANI S，SHARMILA S. Comparative analysis of association rule mining algorithms[C].Tamilnadu：
International Conference on Inventive Computation Technologies，2016.

[20]彭怀仁. 中医方剂大辞典[M]. 北京：人民卫生出版社，1996.

[21]汪玉薇，解丹，李晓东， 等. 基于改进关联规则算法的中医处方规律挖掘研究[J]. 世界科学技术-中医药现代化，2019（3）：348-349.

（责任编辑：江 艳）

收稿日期：2019-12-20

基金项目：国家自然科学基金项目（81674099 ）;江苏省中医药管理局项目（YB2017008）

作者简介：王慧敏（1994-），女，南京中医药大学人工智能与信息技术学院硕士研究生，研究方向为中医药信息学;龚庆悦（1972-），女，博士，南京中医药大学人工智能与信息技术学院副教授，研究方向为中医药信息学。本文通讯作者：龚庆悦。