面向復雜網絡的中藥方劑配伍規律挖掘算法*

韓 楠，喬少杰，李天瑞，宮興偉，舒紅平，元昌安

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