基于改进关联规则算法的中医治疗瘿病用药规律挖掘

杨文敏，佘侃侃，叶 丹

（1.南京中医药大学 人工智能与信息技术学院；2.中科南京软件技术研究院，江苏 南京 210023）

0 引言

瘿病是一中医病证名，是以颈前喉结两旁结块肿大为主要临床特征的一类疾病［1］。现代医学中瘿病的临床表现包括单纯性甲状腺肿、甲状腺功能亢进症、甲状腺炎、甲状腺腺瘤、甲状腺癌等以甲状腺肿大为等［2］。近年来，随着生活习惯的改变，甲状腺疾病发病率明显上升，甲状腺癌成为全球发病率增长最快的常见肿瘤［3］。中医针对瘿病治疗在中医学中早有记载，并积累了丰富的经验，挖掘临床中医药治疗瘿病药物之间的关联规则，并结合中医学中针对瘿病的方剂配伍规律，可以更好地服务于瘿病中医治疗。

数字化信息技术发展日新月异，为医疗健康产业发展注入新动力［4］。随着数据挖掘技术的不断成熟，其在医疗，尤其在中医药领域中的应用日益深入［5］。利用数据挖掘技术，可挖掘药物之间的关联规则，寻找药物之间的联系和用药规律；在名老中医临床诊治病证时，可通过对药物关联规则的挖掘，寻找核心药群，深入了解组方规律，从而辅助诊疗。付喜芳等［6］分析黄宗瑁教授治疗方中治疗妇产科等疾病潜在的用药配伍规律；庞晴等［7］探究倪青教授治疗甲状腺结节的用药经验与组方规律。上述研究运用数据挖掘技术对中医治疗专病的用药规律进行关联规则分析，但缺乏对具体挖掘关联规则算法效率的深入探讨。在数据快速转换成有效信息的迫切需求下，关联规则挖掘算法也被不断改进优化并应用于各数据挖掘任务。蒋茜茜等［8］利用改进的Apriori 算法对高校体测数据进行分析并对算法作效率对比；王慧敏等［9］提出一种融合Apriori 优化算法对中医治疗抑郁症用药规律进行挖掘，并与Relim 算法进行对比，但对比效果不明显，效率较低。因此，本文对中医治疗瘿病的药方数据进行关联规则分析，同时提出改进的FP-growth 算法，与两种经典的Apriori 改进算法在中医药数据上的数据挖掘效率进行比较。

1 相关算法

1.1 关联规则基本概念

关联规则反映数据库中项之间的关联关系。项的集合称为项集，包含k 个项集被称为k-项集，k 表示项集中项的数目，事务是项的集合，事务集是事务的集合。设I＝｛I1，I2，…，In｝是项的集，D 是事务集，若项集A 和项集B 均包含于集合I且均不为空集，且A∩B=∅，则关联规则A=＞B的支持度为s，置信度为c，分别如式（1）和式（2）所示。

其中，count（A∪B）表示A 和B 同时出现的事务个数，TotalCount表示事务集中事务的个数。

其中，count（A）表示出现A 的事务个数。

1.2 Apriori算法

Apriori 算法是一种经典算法，用于挖掘数据集中频繁项集和规则。本质上，Apriori 算法由两部分组成：找频繁项集和产生关联规则，

（1）依据支持度找频繁项集。首次扫描事务数据库D，获取所有项即得到所有候选1-项集，将所有候选1-项集组成的集合计作C1，统计C1每个项的计数，判断是否大于最小支持度，大于则为频繁1-项集，将所有频繁1-项集的集合记作L1，由L1自连接生成所有候选2-项集，所有候选2-项集组成的集合计作C2，同样通过C2找到所有满足最小支持度的频繁2-项集组成集合频繁2-项集L2，再由L2得到C2找到满足最小支持度的频繁3-项集L3，以此类推，从候选项集中找到满足最小支持度的频繁项集，直到找到频繁k项集集合Lk为空，得到所有频繁项集。

（2）依据置信度产生关联规则。扫描所有频繁项集，输出满足最小置信度的关联规则。

Apriori算法流程如图1所示。

Fig.1 Apriori algorithm flow图1 Apriori算法流程

Apriori 算法在多次扫描数据库时会产生大量候选项集，算法效率低、复杂度高［17］。

1.3 Apriori改进算法

针对Apriori 算法的不足，本文基于事务压缩技术［10］和基于散列技术［11］对Apriroi 算法进行改进，虽然两者的主要作用是在Apriori 算法的剪枝部分，但前者通过减少候选项集的大小，在经典Apriori 算法的基础上进一步减少数据库扫描次数，而后者则是通过不断减少数据库中事务集中事务的总量和长度，以提升效率［12］。这两种方法都对数据挖掘效率提升有一定帮助。

1.4 FP-growth算法

FP-Growth［19］算法基于Apriori 原理，通过事务集D 存储到FP-tree（Frequent Pattern tree）频繁项树，进而挖掘频繁项和关联规则。算法流程主要包括构建频繁项树和从频繁项树中挖掘频繁项集两个步骤［20］：

（1）构建FP 树。具体过程如下：①初始化FP-tree 创建根节点T=null；②根据头指针表，从FP-tree 的根结点开始更新FP-tree：如果当前事务项的第一个元素项存在于FP-tree 中，则更新这个子节点的计数值，否则创建新的子节点，依次对当前事务项的其他数据集进行同样操作［21］；③依次将所有事务项的数据项插入到FP-tree 中。

（2）从FP-tree 中挖掘频繁项集。从构建好的FP 树中获得频繁项的前缀路径［13］，然后将前缀路径作为新的数据集构建条件FP 树，再在新的FP 树中的获得频繁项并以此构建条件FP 树。根据此规律，直到条件FP 树中只有一个频繁项集为止［22］。

1.5 FP-growth算法改进

FP-growth 算法利用FP-tree 存储关于频繁项集的压缩信息，相较于Apriori 算法，在挖掘频繁项集时，只对事务数据库扫描两次，极大提高了数据频繁项集的挖掘速度。但在构建FP-tree 树时，重复事物项也会构建重复tree，导致关联规则数据挖掘效率降低。

1.5.1 散列技术

散列技术通过散列函数将要检索的项与索引（散列、散列值）关联起来［14］，将数据压缩成摘要，使得数据量变小，将数据的格式固定下来，形成一种便于检索的数据保存格式，生成一种便于搜索的数据结构［15］。

1.5.2 改进算法主要思想

针对在事务项重复项较多的事务集数据库，本文在此基础上提出一种FP-growth 改进算法，通过散列技术进一步对数据进行压缩，通过创建空数据字典D_dict=｛key1：vaule1，key2：value2，…｝用于存储key-value 映射关系集合，key对应原事务集D 中的不重复的事务，value对应事务出现的频次，通过遍历得到压缩后数据字典D_dict，再进行后面两次的数据遍历操作时，遍历次数减少，进一步缩短了FP-growth 算法创建FP-tree 的时间。改进算法总体流程如算法1所示。

算法1FP-growth改进算法

1.5.3 改进算法主要流程

改进的FP-growth 针对原始事务数据集中的重复事务集重复生成频繁项树的问题，通过遍历事务集生成事务项-事务项频次映射关系保存在数据字典中，从而压缩原始事务集，减少频繁项树数的生成。算法主要改进部分流程如图2所示。

Fig.2 Flow of improved FP-growth algorithm图2 改进FP-growth算法流程

2 数据挖掘实验及结果分析

本文通过比较改进的关联规则算法对名老中医临床诊治瘿病的药物组合进行关联规则分析，并针对算法性能给出对应的结果比较。实验结果包括关联规则结果和算法性能比较两部分。

2.1 原数据

本文数据来源于名老中医临床诊治瘿病的多条临床数据记录，每条记录包括患者的基本信息（性别、年龄）、临床表现、舌像、脉象、标准化方药、剂量等。本文实验所用到的数据列为标准化方药列，也即中医临床诊治患者的方剂数据（方剂数据示例：｛（醋柴胡5，炙鳖甲（先煎）10，鹿角片（先煎）10，夏枯草10，海藻10，炙僵蚕10，仙灵脾10，桃仁10，制南星10，牡蛎（先煎）25，山慈菇12，巴戟肉10，金毛狗脊15，川续断15，当归10）｝）。

2.2 数据预处理

本文数据来源于名老中医临床诊治瘿病的方剂数据，选取数据中的方剂数据，对方剂数据中的标准化方药进行预处理操作，包括对方剂中药物缺失的数据进行删除，去除药物剂量，并结合《中医方剂大辞典》进一步对药名进行规范，整理得到296 条中医药治疗瘿病的方剂数据。以每一方剂为一事务，每个方剂中每一药物为一项整理得到中医药数据事务集。

2.3 实验过程

经过数据预处理的中医数据D=｛｛桔梗，生薏米，茯苓，炒白术，猫爪草，川芎，当归，山海螺，山慈姑粉，壁虎，蜂房，皂刺，炒枳壳，浙贝粉，牡蛎｝，｛太子参，炒僵蚕，炒杏仁，桔梗，壁虎，蜂房，皂刺，元胡，川芎，当归，葶苈子，白芍，制五灵脂，炒川楝子，砂仁，丹参，炒枳壳，茯苓，炒白术，浙贝粉｝…｝，通过不同的算法进行用药规律数据挖掘，通过控制变量法统计各算法运行时间，在相同环境下，统计算法运行时间并将其作为衡量算法效率的标准。

2.4 瘿病用药规律数据挖掘结果

对中医药数据事务集进行数据挖掘，将各算法的最小支持度和最小置信度分别设置为0.3 和0.8。并且，运用这几种改进关联规则算法进行数据挖掘，算法挖掘的频繁项集结果相同，皆为23 个频繁项集，且频繁1、2、3 项集相同，频繁项集具体如表1 所示，药物关联规则如表2 所示。各算法在中医药治疗瘿病的数据事务集挖掘的用药规律结果相同，相互印证，证明算法挖掘结果的有效性。结合表1对挖掘结果进行分析发现，夏枯草、制香附、玄参、天冬、炙僵蚕等为中医治疗瘿病的常用药，草枯草清肝泻火，制香附行气解郁，玄参滋阴降火，天冬养阴清热，玄参、制香附=＞夏枯草，醋柴胡=＞夏枯草相关联，这几种药物活血化淤、滋阴降火，互为佐助，体现了中医治疗瘿病以理气化痰、消瘿散结为基本治则［16］。

Table 1 Mining results of frequent itemsets表1 频繁项集挖掘结果

2.5 关联规则算法比较

对挖掘结果正确性的讨论结束后，进一步对算法效率进行分析。为了直观地对改进算法在中医药数据上的挖掘性能进行对比，采用控制变量法分别在设置不同的最小支持度和不同最小置信度的情况下，对算法运行时间进行可视化展示，实现对改进的FP-growth 算法，以及基于事务压缩技术和散列技术两种技术改进的Apriori 算法进行运行时间比较。

取不同的最小支持度对中医药数据进行挖掘，结果如图3 所示。针对中医药数据进行关联规则挖掘时，两种改进的Apriori 算法与经典的Apriori 相比，算法优化效果不明显，其中基于事物压缩技术的Apriori算法效率稍高。

Table 2 Association rules mining results表2 关联规则挖掘结果

Fig.3 Comparison of execution time between Apriori algorithm and improved Apriori algorithm图3 Apriori算法与Apriori改进算法执行时间比较

同样，对改进的FP-growth 算法与传统的FP-growth 算法进行运行时间对比，如图4 所示。可以看出，改进的FPgrowth 算法效率相比传统的FP-growth 算法有明显提升，随着最小支持度的逐渐减小，改进的FP-growth 算法运行时间与FP-growth 算法以及上文改进Apriori 算法中效率更优的基于事物压缩技术的Apriori 算法的运行时间相差越来越大，而在支持度阈值大于0.12 时，候选频繁项集较少，运行时间差距较小，趋向一致。

各算法取不同的最小置信度，相同最小支持度时同样对中医药数据进行挖掘，结果如图5 所示，相同条件下改进的FP-growth 运行时间最短，优于本文其他算法。

2.6 实验结论

Fig.4 Comparison of execution time of five algorithms图4 FP-growth改进算法与传统算法执行时间比较

Fig.5 Comparison of execution time of five algorithms图5 5种算法执行时间比较

改进的FP-growth 算法针对事务项重复和事务项较多的中医药临床方剂数据集，减少了传统FP-growth 首次遍历数据库生成的频繁项树数量，在传统FP-growth 算法的首次遍历中医临床方剂数据集之前增加一次遍历，统计每一个方剂事务出现在事务集中的频次，压缩生成新的数据集，再进行传统FP-growth 后续挖掘。实验结果表明，控制变量不变的情况下，改进的FP-growth 算法在运行时间上最短，针对传统的FP-growth 以及改进的Apriori 算法在中医药数据挖掘中的应用，改进的FP-growth 算法效率有了一定提升，优于本文其他对比算法。在挖掘结果相同的情况下，针对名老中医临床治疗瘿病的用药规律研究，中医药数据挖掘研究者可更快地得到数据挖掘结果，能够更好地辅助中医临床诊治瘿病患者，并且，结合数据挖掘结果，中医也能够更快地进行中医用药优化。

3 结语

本文采用两种改进的关联规则算法对中医治疗瘿病用药进行规律挖掘，实验中，改进的FP-growth 算法与Apriori算法所挖掘的频繁项集基本相同，所得到的关联规则一致，均体现了中医治疗瘿病理气化痰，消瘿散结的基本治则。通过实验结果比较改进的关联规则算法性能，研究表明，改进的Apriori 算法在进行中医药数据挖掘时，算法效果差别不大，而改进的FP-growth 算法优于传统的FPgrowth 算法，相比改进的Apriori 算法更好地提高了中医药数据挖掘效率，运行时间远少于经典Apriori 算法和改进的Apriori 算法。本文基于改进的关联规则算法对中医治疗瘿病进行用药规律挖掘，通过研究中医临床诊治瘿病的用药规律，探索更加高效的数据挖掘方式，挖掘结果对于后续中医临床诊治瘿病患者具有重要指导和参考意义［18］。同时，研究中也存在一些问题，比如未增加其他变量对算法效率进行分析。未来将继续探索其他关联规则算法在不同中医药数据上的效率表现，针对不同中医药数据集特点寻求最高效的挖掘算法。