摘要：目的 改进Apriori算法以获得更高效的数据挖掘方法，分析名老中医治疗糖尿病病案用药规律。方法 提出1种垂直Apriori数据存储方法，采用用差集方法改进的ADPM挖掘算法，对《国家级名老中医糖尿病验案良方》用药规律进行数据挖掘。结果 经筛选，纳入处方402首，包含高频药物24味、高频药物组合15組、高依赖度药物组合18组，以补虚药、清热药、活血化瘀药、利水渗湿药为主。结论 基于Apriori改进的ADPM算法能运用于用药规律分析，发现高频药物、组合及药物依赖关系，且具有更高的效率。
关键词：数据挖掘；关联规则；Apriori算法；ADPM算法；糖尿病；用药规律
DOI：10.3969/j.issn.1005-5304.2017.12.024
中图分类号：R2-05；R259.871 文献标识码：A 文章编号：1005-5304（2017）12-0097-05
Study on Medication Regularity of Famous TCM Doctors for Diabetes Based on Improved Apriori Algorithm WAN An-qing， BAO Jian-yang， HU Kong-fa （Nanjing University of Chinese Medicine， Nanjing 210023， China）
Abstract： Objective To analyze the medication regularity of TCM famous doctors for diabetes by using improved Apriori algorithm to obtain more efficient data mining methods. Methods This article put forward Apriori vertical data storage， and improved ADPM obtained by difference set method was used to conduct data mining to find out the medication regularity in Guo Jia Ji Ming Lao Zhong Yi Tang Niao Bing Yan An Liang Fang. Results After screening， 402 prescriptions were included， involving 24 kinds of high-frequency medicine， 15 high-frequency medical combinations， and 18 highly-dependent medical combinations， which were mainly tonifying deficiency medicine， clearing heat medicine， blood-activating and stasis-resolving medicine， and damp-draining diuretic medicine. Conclusion ADPM algorithm can be applied in the analysis on medication regularity and find out high-frequency medicine， medical combinations and medical dependent relation， with high efficiency.
Key words： data mining； association rules； Apriori algorithm； ADPM algorithm； diabetes； medication regularity
糖尿病是一种常见病内分泌代谢疾病，严重影响患者的身心健康。中医治疗糖尿病历史悠久，《素问》及《灵枢》均有“消渴”记载。随着中医科研不断发展，中医治疗糖尿病相关研究从过去散在的、相对滞后的状态逐渐发展为拥有系统化、规范化标准的模式，展现了中医治疗糖尿病的独特优势[1-3]。而研究当代名老中医治疗糖尿病验案良方对治疗该病临床用药具有重要参考价值和指导意义。
采用数据挖掘手段能发现隐藏在中医药数据中的规律。其中关联规则分析在中医药数据挖掘中有着
基金项目：国家自然科学基金（81674099、81503499）；江苏省“青蓝工程”资助项目（2016年）
通讯作者：鲍剑洋，E-mail：bjy_163@163.com
广泛的应用[4-5]。目前，关联规则挖掘算法主要有Apriori和FP-Growth，Apriori通过候选集生成和情节的向下封闭检测2个阶段来挖掘频繁项集，需要多次扫描数据库，数据量大时效率降低。FP-Growth只需扫描2次数据库，但是需多次迭代频繁模式树。2种算法均为水平数据存储模式，而垂直数据存储的频繁模式挖掘算法在性能上要优于水平数据存储模式[6-7]。为提高关联规则算法效率，本研究针对传统算法的不足，提出基于Apriori改进的ADPM（Apriori based Diabetes Prescription Mining Arithmetic）算法，该算法避免了多次扫描数据库及多次迭代频繁模式树，利用垂直数据存储的优势，结合差集方法减小挖掘过程中候选集生成规模、加快迭代过程，提高频繁模式挖掘效率。
1 基本概念
垂直数据存储的Apriori算法将事务数据中的项作为键，每个项对应的事务编号作为值，生成新的事务数据库，以加快频繁集生成速度。其算法思想是由频繁k项依次求并集，若2个频繁k项集具有相同的k-1项前缀则这2个频繁k项集可运算生成候选k+1项集。然后对候选集剪枝，满足支持度即加入频繁k+1项集，再计算候选k+2项集，剪枝生成频繁k-2项集。如此迭代，直到求出所有的频繁项集。
垂直数据存储的Apriori算法采用深度优先正向搜索策略，因此无法充分利用Apriori先验性质对候选集进行剪枝。此外，对2个频繁k项集的前缀进行比对耗费大量的时间，尤其在不能生成新的频繁项集的情况下。而随着迭代的加深，频繁项集的增长，这种前缀比对更加耗时，为此本研究提出了改进后的ADPM算法。
定義1：设t（PX）为项集PX的TidSet（PX包含的事务ID集合），d（PX）为项集P和项集X的差集，d（PX）表示存在于t（P）中但不存在于t（PX）的事务ID集合，由集合的性质可以得到d（PX）=
t（P）-t（PX）=t（P）-t（X）。见图1。
由定义可知，ADPM算法中使用将待挖掘项集转换成其差集的方式，这样对于部分事务数据库，通过转换成差集的方式可较大程度减小参与并运算集合的大小。定义的性质中s（PXY）=s（PX）-
|d（PXY）|=s（PY）-|d（PYX）|，表明在使用差集时，同一候选集的生成方式有多种，选择PX和PY中较小的集合来计算s（PXY）可以进一步减小参与并运算的集合大小，提升算法效率。
此外，算法通过缩小生成高频繁项集时迭代运算的循环规模，在循环过程中及时跳出，减少无意义并运算和无意义候选集生成数量来提升算法速度。垂直Apriori算法规定只有具有相同前缀的频繁k项集才能生成候选k+1项集，在2个频繁k项集并运算前需要验证是否满足该条件。ADPM算法中通过对前一步得到频繁k-1项集按编码排序，依次取出2个做并运算生成候选k项集，遇到首项不同即跳出，而无需将所有项集的前缀进行比对，从而缩小迭代运算的循环规模，提高算法效率。
2 算法描述
2.1 算法形式
ADPM算法核心过程伪代码描述如下：
①定义数据结构存储垂直转换的事务数据。
TYPEDEFSTRUCT _ADPM_DATA{ //存储数据结构
set
intf_count = 0 //支持度计数
set
}Adpm_Data， *pAdpm_Data
vector
②输入支持度support，输入事务数据库DataSource。
Iuput：support
Iuput：DataSource
③扫描事务数据集读取事务数据并将事务数据库序列化。
④将数据存储方式转换成集合的差集形式存储，生成一项频繁项集。
FOR item IN DataSource
convert_to_diff_item（item）
IF diff_item_support> support
diff_data_sets.push（diff_item）
END IF
END FOR
⑤反复迭代直至计算出所有满足支持度的频繁项集。
DOFOR itemA IN diff_data_sets
FOR itemB IN diff_data_sets
IF itemA ！= itemB&&itemA（k-1）==itemB（k-1）
//满足生成高项集的条件
result_set = itemA∪convert_to_diff_item（itemB） //生成候选集
IF result_set_support> support
PRINT result_set
END IF
END IF
END FOR
END FOR
WHILE ItemA_size>=2 //当ItemA中元素个数<2时无法再生成高次频繁项集
2.2 挖掘过程
对比垂直Apriori算法和ADPM算法效率，设测试数据集表1为治疗糖尿病方剂数据。对测试数据集进行频繁模式挖掘，设置频繁模式挖掘的支持度为50%，表1中数据库中数据事务条数L_D=6，满足支持度计数S_D≥6×50%=3的项集为频繁项集。序列化后的数据分别表示黄芪（a）、山药（b）、茯苓（c）、丹皮（d）、泽泻（e）、熟地（f）、山茱萸（g）。将原始水平格式数据（见表1）垂直转化成事务数据库倒排表并进行频繁一项集挖掘得到结果（见表2）。算法挖掘过程见图2、图3，红叉表示剪枝。
对于测试数据集表1，对比图2、图3的运算过程可以发现，生成候选2项集时，垂直Apriori算法参与运算的集合规模共有21个元素，而ADPM算法只有9个元素；生成候选3项集时，垂直Apriori算法有18个，ADPM算法有10个；整个挖掘过程参与并运算的集合垂直Apriori算法为39个，ADPM算法为19个，数量大大减少。因此对于一些事务数据集，如这里的测试数据集表1，ADPM算法在生成候选集时能很大程度减小集合大小，加快候选集生成速度，提升算法效率。
3 算法应用
名老中医治疗糖尿病方案是将中医药学基本理论、前贤医家经验与当今临床实践结合，解决临床诊断问题的典范，代表当前中医学术和临床技能的最高水平[8]。通过数据挖掘手段，发现其中的用药规律，对教学和临床用药有极大的指导意义和参考价值。
本研究采用使用C++语言结合R数据挖掘平台开发ADPM算法，对名老中医治疗糖尿病数据挖掘分析。软件环境为：Window2008、Codeblocks、C++11，硬件环境为：2 GHz 4核CPU、4G内存。
3.1 数据来源
《国家级名老中医糖尿病验案良方》[9]中名老中医治疗糖尿病验案，包括朱良春、周仲瑛、方和谦、邓铁涛等95位名家良方，选案丰富，处方精妙。
3.2 数据处理
按照全国高等中医药院校规划教材（第九版）《中药学》[10]进行数据预处理：①去除重复数据、清洗异常数据；②对方剂中的药物别名进行规范，如“三七”“田七”“金不换”规范为“三七”；③标明产地的但无明显功效差异的，如“宁夏枸杞”规范为“枸杞子”，“吉林人参”规范为“人参”，“东阿阿胶”规范为“阿胶”；④对有明显功效差异不可相互替代的同种药物不同炮制品，分别录入，如“生甘草”“炙甘草”。通过数据预处理得到有效方剂402首，涉及药物349味，总用药频次4711次。
3.3 算法对比
通过对名老中医治疗糖尿病方剂数据预处理得到有效方剂402条，原始数据相对较少，观察挖掘效率不明显。为直观观察改进算法的挖掘效率，将原始数据简单扩大250倍，得到算法效率测试数据库，其中共有待挖掘条目100 500条，项目数309项，项集平均长度为12。对比ADPM算法和垂直数据存储的Apriori算法，运行耗时见图4。支持度较大时，ADPM算法效率有少量提升；支持度较小时，ADPM算法效率提升明显。
3.4 挖掘结果
将处理得到的数据导入数据库。使用ADPM算法进行挖掘分析。得到高频药物（支持度>15%）24味（见表3），2味药高频药物组合15组（见表4），无3项及以上高频药物组合。
设置支持度>5%，置信度>90%，得到药物间关联关系，见表5。不设置置信度，根据对支持度>5%的药物关联关系绘制药物依赖关系网图，见图5，连线越粗表示关联越紧密。
图5表明，中医药治疗糖尿病共涉及18类中药，使用频次最高的5类依次为补虚药、清热药、活血化瘀药、利水渗湿药、收涩药，共占78.44%，使用频率排在每类首位的药物分别为黄芪、生地、丹参、茯苓、山茱萸，可見名老中医治疗糖尿病主要是益气养阴，兼以清热活血、化瘀利水。
4 结语
中医药体系高度复杂，治病因时、因地、因人制宜，挖掘分析难度大。中医病案数据中蕴含的知识对临床用药和教育教学有重要指导作用，为更有效地发现中医药治疗糖尿病用药方案中的规律，本研究基于Apriori提出了改进的ADPM算法，ADPM算法在挖掘频繁模式时有更小的候选集和更小的迭代规模，效率更高。通过ADPM算法数据采集、预处理、频繁项挖掘、关联规则分析挖掘了名老中医治疗糖尿病用药数据，并绘制了中医药治疗糖尿病常用药物关系网图。随着数据分析处理技术在中医药这一复杂体系中应用越来越广，应改进传统算法以更适应中医药数据特点。
参考文献：
[1] 栗明，丁常宏，方芳.糖尿病中医治疗进展[J].中医药信息，2012，29（6）：112-115.
[2] 仝小林.糖尿病中医认识及研究进展评述[J].北京中医药，2016， 36（6）：509-512.
[3] 牟新，庄爱文，马国玲，等.237例临床期糖尿病肾病患者中医证候聚类分析[J].中华中医药学刊，2016，34（2）：332-335.
[4] 杨和亮，谌松霖，李金波.基于数据挖掘的针灸治疗膝关节骨性关节炎取穴规律研究[J].中国中医药信息杂志，2017，24（1）：95-98.
[5] 宋京美，吴嘉瑞，姜迪.基于数据挖掘的国家级名老中医治疗肿瘤用药规律研究[J].中国中医药信息杂志，2015，22（6）：50-53.
[6] ARINCY N， SITANGGANG I S. Association rules mining on forest fires data using FP-Growth and ECLAT algorithm[C]//2015 3rd International Conference on Adaptive and Intelligent Agroindustry， IEEE，2015：274-277.
[7] 章志刚.云计算环境下频繁项目集挖掘算法研究[D].南京：南京师范大学，2015.
[8] 徐蕴，魏琦，汤大朋，等.2006-2015年中国期刊全文数据库中医基础理论研究文献计量分析[J].中医杂志，2017，58（5）：418-422.
[9] 徐江燕，毋莹玲，杨建宇.国家级名老中医糖尿病验案良方[M].郑州：中原农民出版社，2013.
[10] 钟赣生.中药学[M].北京：中国中医药出版社，2012.
（收稿日期：2017-04-18）
（修回日期：2017-05-12；编辑：向宇雁）