基于基因表达式编程挖掘中医方证关系.pdf

第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.2005文章编号1001-9081（2005）11-2679-02基于基因表达式编程挖掘中医方证关系余弦1唐常杰1张欢1乔少杰1蒋永光2刘娟2韩佩玉21四川大学计算机学院成都6100652成都中医大学基础医学院成都610075Cos,摘要中医学方证关系分析是中药研究课题的重点和难点，基因表达式编程(GEP)是遗传计算家族的新成员，有强大的函数发现功能。为解决中医方-证关系的函数挖掘的特殊困难，本文提出了新的方法，主要工作包括：1)分析了简单方证模型SFSM的不足，针对中医学方证数据的特点提出结构简单、高效，占用空间少的主次分离指针编码2）提出基于罚函数的单方适应度值计算和基于相似度的中医学症状组平均相似度函数，实现了基于基因表达式的方证关系函数发现算法MRAGEP,获得了一个出人意外的方证函数，不但有很好的精度，而且符合中医主次证原理，可解释性好，得到部分中医专家的肯定。3）通过详尽的实验证明了算法的正确性和有效性，正确率达到了62.5关键词基因表达式编程函数发现传统中医药MiningFormula-SyndromeRelationshipinTraditionalChineseMedicinewithGeneExpressionProgrammingYUxian1,TANGChang-Jie1,ZHANGhuan1,QIAOshaojie1,JIANGyongguang2,LIUjuan2,HANpeiyu21.SchoolofComputerScienceandEngineeringSichuanUniversity2.BasictheoryDepartmentChengduUniversityofTraditionalChineseMedicineAbstract:.FormualSyndromeRelationshipinTraditionalChineseMedicine(TCM)isanimportantanddifficulttasksintheresearchofTCM,GeneExpressionProgramming(GEP)isanewpowerfultoolforKnowledgediscovery.TosolvetheproblemforFormualSyndromeRelationship,thisarticleproposesannewapproach.Themaincontributionsinclude:(a)AnalysestheshortageofSimpleFormulaandSyndromeModel(SFSM),proposeseffectiveandspace-savingcodingmethod.(b)proposinganewconceptMajorHomology(HMA)andMinorHomology(HMI)forFormulaandSyndromeanddesignsaspecialfitnessfunctionbasedonPenaltyfunctionmethod,andimplementsMindingRelationshipArithmeticbasedonImprovedGeneExpressionProgramming(MRAGEP),gainsanamazingfunctionwhichhasgoodprecisionandaccuracyandaffirmationoftheTraditionalChineseMedicineexperts(c)Conductextensiveexperimentstoprovetheeffectivenessoftheapproach.,theaccuracyofMRAGEPis62.5%.1基金项目：国家自然科学基金(60473071)，高等学校博士学科点专项科研基金SRFDP(20020610007号)，四川省青年软件创新工程(350号)，2国家中医药管理局基金项目“中药复方配伍规律的数据多维分析方法研究”（2003-JP-40）作者简介：1余弦(1981)，女，硕士研究生，研究方向：数据库与知识工程；1唐常杰，博士生导师，教授，研究方向：数据库与知识工程，数据挖掘；本文联系作者：唐常杰；1张欢，1乔少杰：硕士研究生，研究方向：数据库与知识工程。2蒋永光教授，博士生导师，研究方向：中医方剂学。2刘娟，2韩佩玉硕士研究生研究方向：中医方剂学。第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.2005KeywordGeneExpressionProgramming,FunctionFinding,TraditionalChineseMedicine1引言中医学(TraditionalChineseMedicine)历史久远，源远流长，是我国无数医药学家与疾病作抗争的经验与教训的结晶。辨证论治中医诊疗疾病的核心方法，“辨证”旨在辨别疾病当前阶段的病因、病机、病性、病位等，是论治、遣方和用药的依据。近年来，中医辨证的量化研究已经成为了跨学科的前沿课题。四川大学和成都中医药大学合作课题组对这个难题进行了深入研究，针对方剂和证的特点，采用基因表达式编程方法，设计了新型编码方式和基于方证距离的适应度函数，获得了好的效果。本文的主要工作包括：1)针对中医数据的特点提出结构简单，紧凑，高效，占用空间少的编码方式2)提出了基于相似度的中医学症状组平均相似度函数和基于基因表达式的方证关系函数发现算法3)通过详尽的实验证明了算法的正确性和有效性，正确率达到了62.5%本文的余下部分组织如下：第2节介绍了中医学中的方证关系和GEP的基本概念和思想；第3节介绍了中医方证分析，简单方证关系模型SFSM和中医学中的症状组主次分离指针编码。第4节介绍了中医学中的症状组平均距离适应度函数，第5节介绍了基于基因表达式的方证关系函数发现算法；第6部分用详尽和准确的实验验证了这个方法的有效性及优越性。最后部分总结了本文的工作，并对未来的工作做出了展望。2相关工作与基本概念2.1中医学中的方证关系证(syndrome)是对一组有内在联系的症状(symptom)进行诊断后的名称。本研究进行的辨证量化研究，是针对古代存集下来的大量方剂而进行的，是对已知的方剂主治症状所进行的证的判定。一个证包含一组症状，有主症,次症之分，主症为判定证的重要性指征，在进行判定时，须具备一个以上，其权重比次症大1。建立了关于判定证的知识表即基本证候表。例如：膀胱湿热证如表1所示：表1基本证候表中的膀胱湿热编码分类证主症次症2.3.5湿热膀胱湿热发热，尿痛，小便频数，小便淋沥，小便灼热腰痛，尿血，尿脓，小便黄，小便少，癃闭，舌红，苔黄，苔腻，脉滑，脉数辨证的难点在于：1)模糊性。证可由多个不同症状排列组合而成，即证候的诊断具有模糊性,如:“脾气虚证”就包括了气虚、脾虚、舌脉等诸多内容1。膀胱湿热证包括了主症(a)发热，尿痛，小便频数，小便淋沥，小便灼热.(b)腰痛,尿血，尿脓，小便黄，小便少，癃闭，舌红，苔黄，苔腻，脉滑，脉数。2)复杂性,证内容的复杂性：证1常常由一种或多种病机要素构成。如“食不下，下利清谷,面虚浮,面色萎黄无华,畏寒,少气懒言,神疲乏力,舌淡白，脉沉缓无力”.每首方(formula)均对应了一系列症状，列于症状表中，通过编号与方剂表、药物表相联。第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.2005如：编号为1的桂枝汤，其所主治的症状为症状表中编号为1所有的症状，如下:恶风、恶寒、自汗、发热、鼻鸣、干呕。表2症状表中的桂枝汤症状组方编号规范症状1恶寒1恶风1发热1干呕1鼻鸣1自汗方证分析旨在挖掘出证与方剂症状的相关性。通过方剂中一系列症状，如上图中的规范症状，与证中主症与次症的关系来判断出方剂的证1。2.2GEP简介F.Candida于2001年草创了新的进化计算模型基因表达式编程(GeneExpressionProgramming,GEP)。GEP具有遗传算法的简单性和遗传编程的功能性。在对很多问题的求解效率上,比普通的遗传编程高2到4个数量级。关于GEP的研究和应用参见28等。多染色体的GEP求解时,对处理对象编码形成染色体（chromosome）,每个染色体由多个基因（gene）组成，每个基因用函数连接函数（link-fuction）连接起来。GEP采用表达式树的编码方式。例1说明了基因组的形成。例1：对于表达式)cos(yxxy+-(2.1)其对应的表达式树ExpressionTree（ET）表示为图1所示：YXC-+XY图1ExpressionTree其中C表示cos函数，对ET进行层次遍历得到序列：C-*+xyxy(2.2)在例1中的序列2.2称为表达式2.1的K表达式。其中函数集FunctionSet为cos()-+*，终结符集合TerminalSet为yx,.基因由头部和尾部组成。头部可由所有字符组成，尾部则只由终结符组成。若头部长度为h,尾部长度th（n-1）+1,其中n为函数集合中运算符的最大目数。GEP的编码方式保证了染色体总是能够解码为有效的表达式树。GEP的遗传操作与遗传算法GA6(GeneticAlgorithm)和遗传编程GP（GeneticProgramming）大同小异。第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.20053方证关系分析方证关系的最初想法是由成都中医药大学的研究小组提出，该研究小组提出了一种简单方证关系模型SFSM(simpleFormulaandSyndromeModel)。SFSM建模步骤如下：算法1：SFSM输入：某一首方F输出：输入的方所对应的最可能的N个证步骤：1）for（eachFormulainF）/对于方F中的每个症状2）for(eachSyndrome)/在基本证候表中查询3）if(InMainSymptomTableSymptom)/若出现在某个证的主症中4）thenSyndromeSymptom+=a；/权重加a5）elseif(InMinorTableSymptom)/若出现在某个证的次症中6）thenSyndromeSymptom+=b；/权重加b7）endif8）endif9）endfor10）endfor11）returnTopNSyndrome（）；/返回得分最高的n个证实验表明，上述方法正确率只有30%35，其原因如下：1)对主症、次症给予的权重（a、b）对结果的影响非常大,一般取a=2,b=1。但是权重具体是多少则完全由人工依据经验指定，主观性比较大。2)SFSM的数学模型是(y=ax1+bx2)，但是从结果来看这个线性的模型显然无法满足要求。为了满足以上需求，根据现有算法的不足和实验分析，我们提出了融合了基因表达式编程和主次分离指针编码技术的方法。3.1症状组主次分离指针编码编码是GEP求解问题的物质基础，编码的目的是把中医学中的症状组形成遗传信息载体-染色体chromosome.。GEP的染色体由多个基因通过连接算符组成，基因分为头部和尾部，头部可由函数集和终结符组成，尾部只能由终结符组成。中医学的编码难点和要点在（1）证的数值化：（2）方的数值化。为了表达方便，表3为本文中将要用到的数据库表名及其内容：表3方证训练数据库中的表符号名称意义Tsyn基本证候证候表为每个证赋予唯一的自然数编号（Index_syn）Tsym症状表将基本证候表中出现的主、次症状以不重复的方式排列，为各个症状赋予唯一的自然数编号（Index_sym）Tfor方剂表为基本证候表中出现的每一个方赋予唯一的自然数编号(Index_for)Trainingdata训练集包含Tfor，Tsyn，Tsym的方证训练数据库第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.20053.1.1证的数值化处理为了便于编码，需要先将中医学中的”证”进行数值化处理。定义1证主串（SynMainStr）：设L1为某个证Syndromei的主症个数，若整数数组Array1L1中的元素为Syndromei中的主症在Tsym中的编号（Index_sym），则称Array1L1为Syndromei的证主串（SynMainStr）。定义2证次串（SynMinorStr）：设L2为某个证Syndromei的次症个数，若整数数组Array2L2中的元素为Syndromei中的次症在Tsym中的编号（Index_sym），则称ArrayL2为Implicationi的证次串（SynMinorStr）。在程序中，证主串和证次串用结构SynStruct实现：SynStructintindex；/证的编号intSynMainStr_MAX_SYMPTOM；/证主串intSynMinorStr_MAX_SYMPTOM；/证次串SYNDROME；其中_MAX_SYMPTOM为一个证中所含症状的最大数目，数组在初始化时填0。有了上述结构，一个证就可以由唯一的SYNDROME结构确定。例2：症状表Tsym=（胸痛，1），（胁胀满，2），（肢冷，3），（胁痛，4），（畏寒，5），（纳差，6），（大便溏，7），（胸闷，8），（气短，9），（面白，10），（头痛，11），（自汗，12），（恶风，13），（脉促，14），（腹满，15），（噎膈，16），（胀痛，17）胸阳不振证表4胸阳不振证分类证主症次症阳虚胸阳不振胸痛，胸闷，畏寒，肢冷，气短面白，自汗，脉促证主串：1，8，5，3，9证次串：10，12，14SynStructindex=20；/胸阳不振证在证候表中的编号SynMainStr=1,8,5,3,9；SynMinorStr=10,12,14；下面的给出证的编码算法：算法2证编码算法SYNC(SyndromeCode）：输入：证名SynName输出：证的编码结构Syndrome步骤：1.Syndrome.index=GetSyndromeNum(SynName)；/在证候表中查到该证的编号2.Syndrome.SynMainStr=0；3.i=0；4.for(eachMainSym)/填充证主串5.Syndrome.SynMainStri+=GetSymptomNum(MainSym)；/*通过症状名查找症状编号*/第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.20056.endfor7.Syndrome.SynMinorStr=0；8.i=0；9.for(eachMinorSym)/填充证次串10.Syndrome.SynMinorSymi+=GetSymptomNum(MinorSym)；11.endfor12.returnSyndrome；通过这个算法，就可以完成对一个证的数值化处理了。若n为某证的症状个数，m为总症状个数，查找按照二分法，则算法复杂度为O(nlog2m).3.1.2方的数值化处理：方的数值化处理思想与证相似，这里不再祥述，注意：方的症状没有主、次之分，其数据结构为：FormuStructintindex；/方的编号intSymptomStr_MAX_SYMPTOM；/症状串FORMULA；方的编码算法与证的编码算法类似：算法3方编码算法FORC(FormulaCode）：输入：方名ForName输出：方的编码结构Formula步骤：13.Formula.index=GetFormulaNum(ForName)；/在方剂表中查到该方的编号14.Formula.SymptomStr=0；15.i=0；16.for(eachSymptom)/填充症状串17.Prescription.SymptomStri+=GetSymptomNum(Symptom)；/*通过症状名查找症状编号*/18.endfor19.returnFormula；通过这个算法，就可以完成对一个方的数值化处理了。以上的编码方式我们称为主次分离指针编码，其编码方式有以下优点：。1)编码实现了从字符串向数值数组的转化。2)数组中每个整数代表了相应症状在症状表中的位置，相当于一个指向相应症状的指针，占用空间少。3)分为主串和次串，分别搜索，快速简单，操作更加方便。3.1.3相似度的设定为了能够以数字值化的方法来衡量方、证间的关系,我们引入了相似度的概念：定义3（主相似度HMA，次相似度HMI)：1)设F为一个方（FORMULA）：若F.SymptomStri0，则称F.SymptomStri为F中的第i个症，i1，,_MAX_SYMPTOM；第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.20052)设S为一个证（SYNDROME），对于j，k=1，,_MAX_SYMPTOM，有：a)若S.SynMainStrj0，则称S.SynMainStrj为S中第j个主症b)若S.SynMinorStrk0，则称S.SynMinorStrk为S中第k个次症，；3)称满足F.SymptomStri=S.SynMainStrj的主症个数为主相似度HMA(MajorHomology)；4)称满足F.SymptomStri=S.SynMinorStrk的次症个数为次相似度HMI(MinorHomology)。在GEP程序中终结符集合TerminalSet的定义为变量(a,b)，其中a。变量a,b分别为和HMA和HMI，下面给出了主相似度算法GetHMA：算法4GetHMA输入：方Formula，证Syndrome输出：主相似度HMA1.HMAvalue:=0，i:=0,j:=0；2.for(eachSymptomiinFormula)/*取出方的每一个症状*/3.for(eachSynMainStrjinSyndrome)/*取出证的每一个症状*/4.if(Formula.SymptomStriSyndrome.SynMainStrj+)5.HMA=HMA+1；/*如果是同一个症状HMA1*/6.i+；7.endfor；8.endfor；9.returnHMA；容易看出，若方中症状个数为n，证中症状个数为m，则算法3的计算复杂度O(nm)。次相似度算法和主相似度算法相似，故省略。4中医学中的症状组适应度函数设计4.1适应度函数简介模拟生物的遗传和进化规律，GEP使用适应度（FitnessFunction）来度量群体中个体有助于找到最优解的优良程度。适应度高的参加遗传活动的概率就大。CandidaFerreira提出了两种适应度计算方法：)(1=-=njjjTCMrorFitnessAbsoluteEr(4-1)100(Re1-=jjjnjTTCMrFitnesslativeErro(4-2)分别被称为绝对误差（4-1）和(4-2)称为相对误差。其中M称为选择范围（RangofSelection）。Tj为第j个观测值，Cj为第j个数据输入公式的结果值，n表示测试数据的个数。在统计学中,用于评价两组数据符合程度的方法是采用复相关系数。适应度计算方法：SSTSSEntFitnessnCoefficieCorrelatio-=1(4-3)第25卷地11期计算机应用Vol.25.No,112005年11月ComputerApplicationsNov.2005=-=njjjCTSSE12)(=-=njjTTSST12)(其中，T为Tj的平均值。4.2中医学中的症状组适应度函数以上的适应度函数不适用于中医的特殊环境，需要设计一种新颖的适应度函数。首先我们引入：定义4（差距值）设P是一个方，F是P对应的证，m1，m2分别是方P对证F的主相似度和次相似度（m1，m20），yf（a，b）进化后某一函数，F1是一个证，F1F，且m3，m4分别是方P对证F1的主相似度和次相似度（m3，m40）1)设y=f（m1，m2）称y为最优计算值（BestValue）。2)设y1=f（m3，m4），如果y1y，则称yy1为差距值。易知差距值全为负值。由定义2，可推导出以下性质：性质11)当BestValue不是最大时：