面向复杂网络的中药方剂配伍规律挖掘算法*

韩 楠，乔少杰，李天瑞，宫兴伟，舒红平，元昌安

1.成都信息工程大学 管理学院，成都 610103

2.成都信息工程大学 网络空间安全学院，成都 610225

3.西南交通大学 信息科学与技术学院，成都 610031

4.成都信息工程大学 软件工程学院，成都 610225

5.广西师范学院 科学计算与智能信息处理广西高校重点实验室，南宁 530023

面向复杂网络的中药方剂配伍规律挖掘算法*

韩 楠1，乔少杰2+，李天瑞3，宫兴伟3，舒红平4，元昌安5

1.成都信息工程大学 管理学院，成都 610103

2.成都信息工程大学 网络空间安全学院，成都 610225

3.西南交通大学 信息科学与技术学院，成都 610031

4.成都信息工程大学 软件工程学院，成都 610225

5.广西师范学院 科学计算与智能信息处理广西高校重点实验室，南宁 530023

+Corresponding autho author:r:E-mail:qiaoshaojie@gmail.com

HAN Nan,QIAO Shaojie,LITianrui,etal.Prescription compatibilitym ining algorithm of traditionalChinesemedicineover complex networks.Journalof Frontiersof Com puter Scienceand Technology,2017,11(7)：1159-1165.

针对传统方剂配伍规律分析方法的不足，提出一种面向复杂网络的新型中药（traditional Chinese medicine，TCM）方剂配伍规律挖掘算法。根据中药方剂特性并结合点式互信息构建TCM网络模型，结合TCM网络的小世界特性提出TCM网络的局部适应度模型，分析TCM网络的特性并挖掘TCM网络中配伍关系紧密、相似度较大的药物群。以4 000余首经典方剂作为实验对象，验证了所提方法具有较好的有效性，与经典LFM（local fitness measure）算法对比，平均模块度值提高了0.05，为中药方剂的配伍规律进行探索及新药研发提供了新思路。

中药；数据挖掘；配伍；复杂网络；药物群

1 引言

在方剂配伍研究领域，诸多学者利用复杂网络[1]对方剂配伍规律的挖掘进行大量研究。胡金亮等人[2]分析研究了慢阻肺基地诊疗常见证候分布规律及中药（traditional Chinesemedicine，TCM）核心药组组合特点，研究成果具有很好的联想分析归类作用。雷蕾等人[3]为临床治疗心绞痛血瘀证的方剂构建中药复杂网络。杨铭等人[4]利用复杂网络，结合生存分析模型，对中医肿瘤临床的生存数据进行挖掘。田旷等人[5]对不同疗效的中药配伍网络进行建模，依据构建的零模式来寻找两个网络之间的显著性差异。乔少杰等人[6]利用基因表达式编程技术挖掘方证关系，挖掘复方中药物之间的依赖性。

2 TCM网络模型的构建

2.1 方剂药物重要性及连接度

每味药物在方剂中所起的重要程度是存在差异的，其重要程度与药物在方剂中的位置相关，药物越靠后重要程度越小[7]。基于这一思想，给出单方中药重要性IH（importance of Chinese herb）定义：

其中，hi表示方剂组成列表中第i味药物，1≤i≤n，n为单方中组成的药物个数。

方剂中任意两种药物之间的连接度（connection degree，CD）取对应的IH均值，定义如下：

其中，i,j≤n，表示方剂中任意两个药物位置下标。

假设共用m首方剂，则药物之间总的连接度（total connection degree，TCD）定义如下：

其中，bool(hi,hj)表示hi和hj两个药物是否存在第m首方剂，如果其值存在，为1，否则为0。

2.2 基于药物连接度的点式互信息

点互信息（pointw isemutual information，PM I）是信息论中用以度量两个事件的相互关系或相似性，其原始定义如下：

PM I在文献[8]中得到广泛应用，但用在方剂药物网络中往往会受到配伍频率较低的影响。因此结合上文提出的药物间共现连接度，给出如下度量两两药物的关联度TP的定义如下：

2.3 方剂药物组网

根据单方得到的药物网络是一个无向有权完全子图，原始方剂集合通过单方叠加得到的方剂网络连接过于密集，在药物群发现阶段，社团划分算法无法对如此密集的方剂网络图进行有效划分，通过设置阈值，以减小网络规模，并得到具有稀疏性的网络。因此，首先根据如上方法计算得出方剂药物间的TP值，然后移除低于阈值的边，由此得到稀疏的TCM网络，进而进行重叠性药物群的发现。

3 中药复杂网络基本概念

定义1（TCM网络）在一个无向有权图G(V,E,W)的TCM网络中，对于给定的中药方剂集合，以药物作为网络G的顶点，V={v1,v2,…,vn}表示G中所有顶点集合，根据药物的TP值构建顶点之间的边集E={(vi,vj)|vi,vj∈V}，药物顶点 vi和 vj间的关联度权值W={wij|(vi,vj)∈E}。

定义2（点权值）点权值指与当前节点vi直接相连的所有邻居节点连边的权值之和，则vi的点权值表示为，其中vk是vi的邻居节点。

定义3（社团适应度）社团适应度定义如下：

式（6）中，δl(C)表示社团划分的局部密度；ε为社团内部连边；|C|表示社团节点个数，当ε=n×(n-1)/2时，社团C可表示为完全子图。式（7）中，δr(C)用以衡量社团C内部边与外部边权重的比值关系，其值越大反映局部社团划分效果越好；Kin(C)表示两个节点都在社团C内的边权值之和；Kout(C)表示一个节点在社团C内部，另一个节点在社团C外部的边权值之和。α为可调因子，当α较大时，发现的社团较小，反之较大，α通常取1.0。式（8）定义的f(C)为社团内部节点对社团C的贡献程度，其值越大表示社团内部相似度越大；反之越小。

对于节点 j，判断其添加前后对当前社团适应度f(C)的影响，如添加节点 j后 f(C)变大，则将该节点加入当前社团C，否则进行下一个节点的判断：

根据式（9），当前社团的局部适应度达到最大值，即向社团添加新节点不能令社团的局部适应度值继续增大，则完成此社团的划分，社团已经到达最佳社团适应度 fmax。

定义4（模块度函数）模块度函数用EQw表示，是一个用于衡量网络社团结构划分结果质量好坏的标准，本文采用文献[9]提出的扩展模块度EQ函数作为衡量重叠社团的一个标准，由于原EQ函数用于无权图，将其扩展应用于加权网络：

其中，W表示权值矩阵；w为所有连边节点的权值之和；Qu表示第u个节点所属的社团个数；wu表示节点u的点权值；δ(Cu,Cv)表示如果两个节点处于同一个社团，其值为1，否则为0。

4 重叠药物群检测算法

4.1 初始药物群检测

算法1初始药物群发现算法

输入：G(V,E,W)，种子节点s，适应度因子α

输出：单个初始药物群Cs

9. end if

10. elsebreak；

11.endwhile

12.U←A；

13.end while

14.outputCs；

算法1中N(s)表示节点的邻居节点；U表示当前处理社团内部节点所有不在社团内部的邻居节点；A是社团在每轮向外进行扩展过程中，不属于社团Cs的邻居节点集合。

算法1的主要操作为：（1）获取种子节点s，初始化当前社团Cs包含s，集合U为s的邻居节点集合N(s)（第1行）。（2）社团Cs的扩充过程如算法第2～13行所示。按照式（8）、（9）选择最佳的节点v，如果存在v使得社团适应度fmax增大，则将v添加到社团Cs中，从U集合中移除v，并将节点v的邻居节点不在Cs中的节点添加到集合A中（第4～11行）。（3）如果集合A重新赋值，对集合V进行社团发现的迭代操作。

4.2 相似药物群合并

一些药物群之间具有较高的重叠性，需要将其合并以提高发现的药物群的质量。本节利用式（11）给出的药物群重叠度概念对上节得到的初始药物群进行合并操作，最终实现药物群的发现。

式中，|Ci⋂Cj|表示两个药物群集合之间重叠的个数；min(|Ci|,|Cj|)表示取两个药物群集合的较小者。在实验中设置O(Ci,Cj)=0.5。

5 实验结果分析

本文所使用的TCM数据包含近4 000余首经典方剂，方剂来源为《太平惠民和剂局方》、《景岳全书》、《圣济总录》、《中国药典》等。在进行方剂的组网之前，经过加工预处理，统计得出TCM网络包括1 577味中药节点和97 103条边。

5.1 TCM网络静态拓扑特征分析

复杂网络节点度可以初步反映出复杂网络中节点的重要性。由图1可以看出，TCM网络符合复杂网络的幂律分布特性[10]，即药物配伍网络中只有少部分药物作为核心，绝大多数药物按照中医药学理论与核心药物进行配伍。图2中药物之间的TP值最大为166.4，其中在0～20.0内占所有药物连边数的94.5%，平均TP值为9.37，一定程度上说明了在传统中医药方剂配伍应用中，只有较少的药对频繁地出现在不同的方剂中。

Fig.1 Node degree distribution of TCM networks图1 TCM网络药物节点度分布

Fig.2 Distribution ofTPvalue in TCM networks图2 TCM网络用药TP值分布

通过分析发现，与甘草进行配对的药物较多，正是因为甘草具有调和诸药的功效。另外，根据计算得到TCM网络的平均最短路径 ＜l＞为2.84，说明TCM网络的＜l＞较小，符合复杂网络小世界特性[11]。

在图论中，聚集系数C[12]用于表示一个图形中节点聚集程度的度量，节点i的聚集下Ci=2ei/ki(ki-1)，小世界网络和全连接网络都具有较大的聚类系数。本实验中TCM网络药物节点的平均聚类系数C为0.627，说明该网络具有较高的聚集性。

5.2 TP值对构建方剂网络的影响

在发现药物团时需要设置阈值TPmin，由于该阈值具体取值较难确定，实验对TPmin在[0,40]之间取值的情况进行分析讨论。

如图3所示，平均节点度 ＜k＞值在TPmin取值为2.0之前迅速降低，之后趋于平缓。通过设置TPmin大于2.0，可以移除大多数低频且低相关的药物边。

Fig.3 Influenceof differentTPminon ＜k＞图3 不同TPmin对＜k＞的影响

需要进一步验证本文方法和LFM算法[13]在多尺度的TPmin值下的药物群划分结果。LFM算法往往具有很大的随机性，本文方法则能够较好地克服这一问题。EQw模块度值作为衡量两种算法运行结果发现药物群的质量的一个标准，其值越大表示社区划分结果越好。如图4所示，TPmin在[0,40]之间取值，EQw值平均提高了0.05。图5是两种方法在不同TPmin取值下最大药物群包含的药物数量，可以发现本文方法发现的最大药物群所包含的药物个数均小于LFM算法，能够发现的药物群个数更多。主要原因在于本文方法在最大化药物群适应度的同时考虑药物群内部药物节点之间联系的紧密程度，所以能够发现的药物群的个数更多，结果如图6所示。

6 结论及展望

本文基于复杂网络提出构建TCM网络模型的方法，通过设置不同的网络阈值发现不同尺度的药物群。对比LFM算法，本文方法可以有效发现内部配伍联系更加紧密、相似度更大的药物群。后期研究包括：在构建TCM网络时考虑药物的使用剂量，采用并行化处理发现TCM网络核心药物节点等，利用进化算法研究复方药物间的依赖性[14]，应用关联规则分析方法挖掘方剂的配伍规律[15]。

Fig.4 ChangeofmodularityEQww ithTPmin图4 模块度EQw随TPmin的变化

Fig.5 Change of the numberof herbs in the largestherb groupsw ithTPmin图5 最大药物群包含药物个数随TPmin的变化

Fig.6 Change of the numberof herb groupsw ith TPmin图6 药物群个数随TPmin的变化

[1]Strogatz SH.Exploring complex networks[J].Nature,2001,410(6825):268-276.

[2]Hu Jinliang,Li Suyun,Zhang Xinghong,etal.Study on syndrome distribution and Chinese medicine composition of AECOPD based on complex networks[J].Modernization of Traditional Chinese Medicine and Materia Medica-World Scienceand Technology,2015,17(6):1268-1273.

[3]Lei Lei,Yang Ce,Wen Xianrong,etal.Study on formulating rules of Chinese herbal formula for treating angina blood stasis syndrome[J].World Chinese Medicine,2013,8(9):1101-1104.

[4]Yang M ing,Li Jiaqi,Jiao Lijing,etal.Effective core formulae for lung cancer based on complex network and survival analysis[J].China Journal of Chinese Materia Medica,2015,40(22):4482-4490.

[5]Tian Kuang,Du Ninglin.Multiscale backbone based network comparison algorithm for effective herbal interaction analysis[J].Electronic Science&Technology,2015,2(2):243-249.

[6]Qiao Shaojie,Tang Changjie,Han Nan,etal.M ining the compatibility law ofmultidimensionalmedicines based on dependencemode sets[J].Journal of Sichuan University:Engineering Science Edition,2007,39(4):134-138.

[7]Li Shao,Zhang Bo,Jiang Duo,et al.Herb network construction and co-module analysis for uncovering the combination rule of traditional Chinese herbal formulae[J].BMC Bioinformatics,2010,11(11):1-12.

[8]Wu Lifang,Wang Dan,Guo Cheng,etal.User profiling by combining topic modeling and pointw ise mutual information(TM-PM I)[C]//LNCS 9517:Proceedings of the 22nd International Conference on Multimedia Modeling,M iam i,USA,Jan4-6,2016.Berlin,Heidelberg:Springer,2016:152-161.

[9]Shen Huawei,Cheng Xueqi,Cai Kai.Detectoverlapping and hierarchical community structure in networks[J].Physica A:StatisticalMechanicsand ItsApplications,2009,388(8):1706-1712.

[10]Barabosi A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[11]Watts D J,Strogatz S H.Collective dynam ics of‘smallworld’networks[J].Nature,1998,393(4):440-442.

[12]Soffer SN,Vázquez A.Network clustering coefficientw ithout degree-correlation biases[J].Physical Review E,2005,71(5):057101.

[13]LancichinettiA,Fortunato S,Kertész J.Detecting the overlapping and hierarchical community structure of complex networks[J].New Journalof Physics,2008,11(3):19-44.

[14]Qiao Shaojie,Tang Changjie,Jin Huidong,etal.KISTCM:know ledge discovery system for traditional Chinesemedicine[J].Applied Intelligence,2010,32(3):346-363.

[15]Han Jiawei,Pei Jian,Yin Yiwen.M ining frequent patterns w ithout candidate generation[J].ACM SIGMOD Record,2000,29(2):1-12.

附中文参考文献：

[2]胡金亮,李素云,张兴红,等.基于复杂网络AECOPD证候分布及中药组合研究[J].世界科学技术-中医药现代化,2015,17(6):1268-1273.

[3]雷蕾,杨策,温先荣,等.基于复杂网络的心绞痛血瘀证中药组方研究[J].世界中医药,2013,8(9):1101-1104.

[4]杨铭,李嘉旗,焦丽静,等.基于复杂网络结合生存分析的中医药治疗肺癌的核心有效处方的发现研究[J].中国中药杂志,2015,40(22):4482-4490.

[5]田旷,杜宁林.基于多尺度骨干网的网络比较算法——面向药物配伍分析[J].电子科学技术,2015,2(2):243-249.

[6]乔少杰,唐常杰,韩楠,等.基于依赖模式集挖掘组方药物多维配伍规律[J].四川大学学报:工程科学版,2007,39(4):134-138.

韩楠（1984—），女，陕西宝鸡人，2012年于成都中医药大学获得博士学位，现为成都信息工程大学讲师，主要研究领域为中医数据挖掘。

QIAO Shaojiewas born in 1981.He received the Ph.D.degree from Sichuan University in 2009.Now he is a professor and M.S.supervisor at Chengdu University of Information Technology,and the seniormember of CCF.His research interests include databasesand datamining.

乔少杰（1981—），男，山东招远人，2009年于四川大学获得博士学位，现为成都信息工程大学教授、硕士生导师，CCF高级会员，主要研究领域为数据库，数据挖掘。

LITianruiwasborn in 1969.He received the Ph.D.degree from Southwest Jiaotong University in 2002.Now he is a professor and Ph.D.supervisor at Southwest Jiaotong University.His research interest is intelligent information processing.

李天瑞（1969—），男，福建莆田人，2002年于西南交通大学获得博士学位，现为西南交通大学教授、博士生导师，主要研究领域为智能信息处理。

GONG Xingweiwas born in 1991.He is an M.S.candidate at Southwest Jiaotong University.His research interest isdatamining.

宫兴伟（1991—），男，重庆潼南人，西南交通大学硕士研究生，主要研究领域为数据挖掘。

SHU Hongping was born in 1974.He received the Ph.D.degree from Sichuan University in 2010.Now he isa professorand M.S.supervisoratChengdu University of Information Technology.His research interestis datam ining.

舒红平（1974—），男，重庆潼南人，2010年于四川大学获得博士学位，现为成都信息工程大学教授、硕士生导师，主要研究领域为数据挖掘。

YUAN Chang'an was born in 1964.He received the Ph.D.degree from Sichuan University in 2006.Now he is a professorand M.S.supervisoratGuangxiTeachers Education University.His research interest is datam ining.

元昌安（1964—），男，安徽肥东人，2006年于四川大学获得博士学位，现为广西师范学院教授、硕士生导师，主要研究领域为数据挖掘。

Prescription Com patibility M ining A lgorithm of Traditional Chinese M edicine over Com p lex Networks*

HAN Nan1,QIAO Shaojie2+,LITianrui3,GONG Xingwei3,SHU Hongping4,YUAN Chang'an5
1.SchoolofManagement,Chengdu University of Information Technology,Chengdu 610103,China
2.Schoolof CyberSecurity,Chengdu University of Information Technology,Chengdu 610225,China
3.Schoolof Information Scienceand Technology,Southwest Jiaotong University,Chengdu 610031,China
4.Schoolof Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China
5.Science Computing and Intelligent Information Processing of Guangxi Higher Education Key Laboratory,Guangxi Teachers Education University,Nanning 530023,China

Aiming to overcome the drawbacksof traditional Chinesemedicine(TCM)prescription analysis,this paperproposes a new complex networks-based TCM prescriptionm ining algorithm,which creates the TCM networks by combining the characteristicsof prescriptionsand pointmutual information.This paperalso proposesa new local fitnessmodel of TCM networks by integrating the feature of small world,which can analyze the characteristics of TCM networks and discover the closely linked and sim ilar herb groups.Extensive experiments are conducted on more than 4000 prescriptions to evaluate the effectiveness of the proposed algorithm.Compared w ith the LFM(local fitnessmeasure)algorithm,the results show that the averagemodularity can be improved by 0.05.The proposed algorithm can be applied to explore the compatibility of prescriptions and provide new ideas for the research and developmentof new medicines.

traditionalChinesemedicine;datam ining;compatibility;complex networks;herb group

as born in 1984.She

the Ph.D.degree from Chengdu University of TraditionalChinese Medicine in 2012.Now she is a lecturer at Chengdu University of Information Technology.Her research interest is data mining in traditionalChinesemedicine.

A

：TP391

*The NationalNatural Science Foundation of China under GrantNos.61100045,61363037(国家自然科学基金);the Planning Foundation for Humanitiesand Social SciencesofM inistry of Education of China under GrantNo.15YJAZH058(教育部人文社会科学研究规划基金);theYouth Foundation forHumanitiesand SocialSciencesofM inistry of Education of ChinaunderGrantNo.14YJCZH046(教育部人文社会科学研究青年基金);the SoftScience Foundation of Chengdu underGrantNo.2015-RK00-00059-ZF(成都市软科学项目);the Science Foundation of EducationalComm ission of Sichuan Province underGrantNo.14ZB0458(四川省教育厅资助科研项目).

Received 2016-04,Accepted 2016-06.

CNKI网络优先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1139.006.htm l