基于基因表達式編程挖掘中醫(yī)方證關(guān)系.pdfVIP

第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.2005文章編號1001-9081（2005）11-2679-02基于基因表達式編程挖掘中醫(yī)方證關(guān)系余弦1唐常杰1張歡1喬少杰1蔣永光2劉娟2韓佩玉21四川大學計算機學院成都6100652成都中醫(yī)大學基礎(chǔ)醫(yī)學院成都610075Cos,摘要中醫(yī)學方證關(guān)系分析是中藥研究課題的重點和難點，基因表達式編程(GEP)是遺傳計算家族的新成員，有強大的函數(shù)發(fā)現(xiàn)功能。為解決中醫(yī)方-證關(guān)系的函數(shù)挖掘的特殊困難，本文提出了新的方法，主要工作包括：1)分析了簡單方證模型SFSM的不足，針對中醫(yī)學方證數(shù)據(jù)的特點提出結(jié)構(gòu)簡單、高效，占用空間少的主次分離指針編碼2）提出基于罰函數(shù)的單方適應(yīng)度值計算和基于相似度的中醫(yī)學癥狀組平均相似度函數(shù)，實現(xiàn)了基于基因表達式的方證關(guān)系函數(shù)發(fā)現(xiàn)算法MRAGEP,獲得了一個出人意外的方證函數(shù)，不但有很好的精度，而且符合中醫(yī)主次證原理，可解釋性好，得到部分中醫(yī)專家的肯定。3）通過詳盡的實驗證明了算法的正確性和有效性，正確率達到了62.5關(guān)鍵詞基因表達式編程函數(shù)發(fā)現(xiàn)傳統(tǒng)中醫(yī)藥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號)，四川省青年軟件創(chuàng)新工程(350號)，2國家中醫(yī)藥管理局基金項目“中藥復方配伍規(guī)律的數(shù)據(jù)多維分析方法研究”（2003-JP-40）作者簡介：1余弦(1981)，女，碩士研究生，研究方向：數(shù)據(jù)庫與知識工程；1唐常杰，博士生導師，教授，研究方向：數(shù)據(jù)庫與知識工程，數(shù)據(jù)挖掘；本文聯(lián)系作者：唐常杰；1張歡，1喬少杰：碩士研究生，研究方向：數(shù)據(jù)庫與知識工程。2蔣永光教授，博士生導師，研究方向：中醫(yī)方劑學。2劉娟，2韓佩玉碩士研究生研究方向：中醫(yī)方劑學。第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.2005KeywordGeneExpressionProgramming,FunctionFinding,TraditionalChineseMedicine1引言中醫(yī)學(TraditionalChineseMedicine)歷史久遠，源遠流長，是我國無數(shù)醫(yī)藥學家與疾病作抗爭的經(jīng)驗與教訓的結(jié)晶。辨證論治中醫(yī)診療疾病的核心方法，“辨證”旨在辨別疾病當前階段的病因、病機、病性、病位等，是論治、遣方和用藥的依據(jù)。近年來，中醫(yī)辨證的量化研究已經(jīng)成為了跨學科的前沿課題。四川大學和成都中醫(yī)藥大學合作課題組對這個難題進行了深入研究，針對方劑和證的特點，采用基因表達式編程方法，設(shè)計了新型編碼方式和基于方證距離的適應(yīng)度函數(shù)，獲得了好的效果。本文的主要工作包括：1)針對中醫(yī)數(shù)據(jù)的特點提出結(jié)構(gòu)簡單，緊湊，高效，占用空間少的編碼方式2)提出了基于相似度的中醫(yī)學癥狀組平均相似度函數(shù)和基于基因表達式的方證關(guān)系函數(shù)發(fā)現(xiàn)算法3)通過詳盡的實驗證明了算法的正確性和有效性，正確率達到了62.5%本文的余下部分組織如下：第2節(jié)介紹了中醫(yī)學中的方證關(guān)系和GEP的基本概念和思想；第3節(jié)介紹了中醫(yī)方證分析，簡單方證關(guān)系模型SFSM和中醫(yī)學中的癥狀組主次分離指針編碼。第4節(jié)介紹了中醫(yī)學中的癥狀組平均距離適應(yīng)度函數(shù)，第5節(jié)介紹了基于基因表達式的方證關(guān)系函數(shù)發(fā)現(xiàn)算法；第6部分用詳盡和準確的實驗驗證了這個方法的有效性及優(yōu)越性。最后部分總結(jié)了本文的工作，并對未來的工作做出了展望。2相關(guān)工作與基本概念2.1中醫(yī)學中的方證關(guān)系證(syndrome)是對一組有內(nèi)在聯(lián)系的癥狀(symptom)進行診斷后的名稱。本研究進行的辨證量化研究，是針對古代存集下來的大量方劑而進行的，是對已知的方劑主治癥狀所進行的證的判定。一個證包含一組癥狀，有主癥,次癥之分，主癥為判定證的重要性指征，在進行判定時，須具備一個以上，其權(quán)重比次癥大1。建立了關(guān)于判定證的知識表即基本證候表。例如：膀胱濕熱證如表1所示：表1基本證候表中的膀胱濕熱編碼分類證主癥次癥2.3.5濕熱膀胱濕熱發(fā)熱，尿痛，小便頻數(shù)，小便淋瀝，小便灼熱腰痛，尿血，尿膿，小便黃，小便少，癃閉，舌紅，苔黃，苔膩，脈滑，脈數(shù)辨證的難點在于：1)模糊性。證可由多個不同癥狀排列組合而成，即證候的診斷具有模糊性,如:“脾氣虛證”就包括了氣虛、脾虛、舌脈等諸多內(nèi)容1。膀胱濕熱證包括了主癥(a)發(fā)熱，尿痛，小便頻數(shù)，小便淋瀝，小便灼熱.(b)腰痛,尿血，尿膿，小便黃，小便少，癃閉，舌紅，苔黃，苔膩，脈滑，脈數(shù)。2)復雜性,證內(nèi)容的復雜性：證1常常由一種或多種病機要素構(gòu)成。如“食不下，下利清谷,面虛浮,面色萎黃無華,畏寒,少氣懶言,神疲乏力,舌淡白，脈沉緩無力”.每首方(formula)均對應(yīng)了一系列癥狀，列于癥狀表中，通過編號與方劑表、藥物表相聯(lián)。第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.2005如：編號為1的桂枝湯，其所主治的癥狀為癥狀表中編號為1所有的癥狀，如下:惡風、惡寒、自汗、發(fā)熱、鼻鳴、干嘔。表2癥狀表中的桂枝湯癥狀組方編號規(guī)范癥狀1惡寒1惡風1發(fā)熱1干嘔1鼻鳴1自汗方證分析旨在挖掘出證與方劑癥狀的相關(guān)性。通過方劑中一系列癥狀，如上圖中的規(guī)范癥狀，與證中主癥與次癥的關(guān)系來判斷出方劑的證1。2.2GEP簡介F.Candida于2001年草創(chuàng)了新的進化計算模型基因表達式編程(GeneExpressionProgramming,GEP)。GEP具有遺傳算法的簡單性和遺傳編程的功能性。在對很多問題的求解效率上,比普通的遺傳編程高2到4個數(shù)量級。關(guān)于GEP的研究和應(yīng)用參見28等。多染色體的GEP求解時,對處理對象編碼形成染色體（chromosome）,每個染色體由多個基因（gene）組成，每個基因用函數(shù)連接函數(shù)（link-fuction）連接起來。GEP采用表達式樹的編碼方式。例1說明了基因組的形成。例1：對于表達式)cos(yxxy+-(2.1)其對應(yīng)的表達式樹ExpressionTree（ET）表示為圖1所示：YXC-+XY圖1ExpressionTree其中C表示cos函數(shù)，對ET進行層次遍歷得到序列：C-*+xyxy(2.2)在例1中的序列2.2稱為表達式2.1的K表達式。其中函數(shù)集FunctionSet為cos()-+*，終結(jié)符集合TerminalSet為yx,.基因由頭部和尾部組成。頭部可由所有字符組成，尾部則只由終結(jié)符組成。若頭部長度為h,尾部長度th（n-1）+1,其中n為函數(shù)集合中運算符的最大目數(shù)。GEP的編碼方式保證了染色體總是能夠解碼為有效的表達式樹。GEP的遺傳操作與遺傳算法GA6(GeneticAlgorithm)和遺傳編程GP（GeneticProgramming）大同小異。第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.20053方證關(guān)系分析方證關(guān)系的最初想法是由成都中醫(yī)藥大學的研究小組提出，該研究小組提出了一種簡單方證關(guān)系模型SFSM(simpleFormulaandSyndromeModel)。SFSM建模步驟如下：算法1：SFSM輸入：某一首方F輸出：輸入的方所對應(yīng)的最可能的N個證步驟：1）for（eachFormulainF）/對于方F中的每個癥狀2）for(eachSyndrome)/在基本證候表中查詢3）if(InMainSymptomTableSymptom)/若出現(xiàn)在某個證的主癥中4）thenSyndromeSymptom+=a；/權(quán)重加a5）elseif(InMinorTableSymptom)/若出現(xiàn)在某個證的次癥中6）thenSyndromeSymptom+=b；/權(quán)重加b7）endif8）endif9）endfor10）endfor11）returnTopNSyndrome（）；/返回得分最高的n個證實驗表明，上述方法正確率只有30%35，其原因如下：1)對主癥、次癥給予的權(quán)重（a、b）對結(jié)果的影響非常大,一般取a=2,b=1。但是權(quán)重具體是多少則完全由人工依據(jù)經(jīng)驗指定，主觀性比較大。2)SFSM的數(shù)學模型是(y=ax1+bx2)，但是從結(jié)果來看這個線性的模型顯然無法滿足要求。為了滿足以上需求，根據(jù)現(xiàn)有算法的不足和實驗分析，我們提出了融合了基因表達式編程和主次分離指針編碼技術(shù)的方法。3.1癥狀組主次分離指針編碼編碼是GEP求解問題的物質(zhì)基礎(chǔ)，編碼的目的是把中醫(yī)學中的癥狀組形成遺傳信息載體-染色體chromosome.。GEP的染色體由多個基因通過連接算符組成，基因分為頭部和尾部，頭部可由函數(shù)集和終結(jié)符組成，尾部只能由終結(jié)符組成。中醫(yī)學的編碼難點和要點在（1）證的數(shù)值化：（2）方的數(shù)值化。為了表達方便，表3為本文中將要用到的數(shù)據(jù)庫表名及其內(nèi)容：表3方證訓練數(shù)據(jù)庫中的表符號名稱意義Tsyn基本證候證候表為每個證賦予唯一的自然數(shù)編號（Index_syn）Tsym癥狀表將基本證候表中出現(xiàn)的主、次癥狀以不重復的方式排列，為各個癥狀賦予唯一的自然數(shù)編號（Index_sym）Tfor方劑表為基本證候表中出現(xiàn)的每一個方賦予唯一的自然數(shù)編號(Index_for)Trainingdata訓練集包含Tfor，Tsyn，Tsym的方證訓練數(shù)據(jù)庫第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.20053.1.1證的數(shù)值化處理為了便于編碼，需要先將中醫(yī)學中的”證”進行數(shù)值化處理。定義1證主串（SynMainStr）：設(shè)L1為某個證Syndromei的主癥個數(shù)，若整數(shù)數(shù)組Array1L1中的元素為Syndromei中的主癥在Tsym中的編號（Index_sym），則稱Array1L1為Syndromei的證主串（SynMainStr）。定義2證次串（SynMinorStr）：設(shè)L2為某個證Syndromei的次癥個數(shù)，若整數(shù)數(shù)組Array2L2中的元素為Syndromei中的次癥在Tsym中的編號（Index_sym），則稱ArrayL2為Implicationi的證次串（SynMinorStr）。在程序中，證主串和證次串用結(jié)構(gòu)SynStruct實現(xiàn)：SynStructintindex；/證的編號intSynMainStr_MAX_SYMPTOM；/證主串intSynMinorStr_MAX_SYMPTOM；/證次串SYNDROME；其中_MAX_SYMPTOM為一個證中所含癥狀的最大數(shù)目，數(shù)組在初始化時填0。有了上述結(jié)構(gòu)，一個證就可以由唯一的SYNDROME結(jié)構(gòu)確定。例2：癥狀表Tsym=（胸痛，1），（脅脹滿，2），（肢冷，3），（脅痛，4），（畏寒，5），（納差，6），（大便溏，7），（胸悶，8），（氣短，9），（面白，10），（頭痛，11），（自汗，12），（惡風，13），（脈促，14），（腹?jié)M，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輸出：證的編碼結(jié)構(gòu)Syndrome步驟：1.Syndrome.index=GetSyndromeNum(SynName)；/在證候表中查到該證的編號2.Syndrome.SynMainStr=0；3.i=0；4.for(eachMainSym)/填充證主串5.Syndrome.SynMainStri+=GetSymptomNum(MainSym)；/*通過癥狀名查找癥狀編號*/第25卷地11期計算機應(yīng)用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；通過這個算法，就可以完成對一個證的數(shù)值化處理了。若n為某證的癥狀個數(shù)，m為總癥狀個數(shù)，查找按照二分法，則算法復雜度為O(nlog2m).3.1.2方的數(shù)值化處理：方的數(shù)值化處理思想與證相似，這里不再祥述，注意：方的癥狀沒有主、次之分，其數(shù)據(jù)結(jié)構(gòu)為：FormuStructintindex；/方的編號intSymptomStr_MAX_SYMPTOM；/癥狀串FORMULA；方的編碼算法與證的編碼算法類似：算法3方編碼算法FORC(FormulaCode）：輸入：方名ForName輸出：方的編碼結(jié)構(gòu)Formula步驟：13.Formula.index=GetFormulaNum(ForName)；/在方劑表中查到該方的編號14.Formula.SymptomStr=0；15.i=0；16.for(eachSymptom)/填充癥狀串17.Prescription.SymptomStri+=GetSymptomNum(Symptom)；/*通過癥狀名查找癥狀編號*/18.endfor19.returnFormula；通過這個算法，就可以完成對一個方的數(shù)值化處理了。以上的編碼方式我們稱為主次分離指針編碼，其編碼方式有以下優(yōu)點：。1)編碼實現(xiàn)了從字符串向數(shù)值數(shù)組的轉(zhuǎn)化。2)數(shù)組中每個整數(shù)代表了相應(yīng)癥狀在癥狀表中的位置，相當于一個指向相應(yīng)癥狀的指針，占用空間少。3)分為主串和次串，分別搜索，快速簡單，操作更加方便。3.1.3相似度的設(shè)定為了能夠以數(shù)字值化的方法來衡量方、證間的關(guān)系,我們引入了相似度的概念：定義3（主相似度HMA，次相似度HMI)：1)設(shè)F為一個方（FORMULA）：若F.SymptomStri0，則稱F.SymptomStri為F中的第i個癥，i1，,_MAX_SYMPTOM；第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.20052)設(shè)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的主癥個數(shù)為主相似度HMA(MajorHomology)；4)稱滿足F.SymptomStri=S.SynMinorStrk的次癥個數(shù)為次相似度HMI(MinorHomology)。在GEP程序中終結(jié)符集合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；容易看出，若方中癥狀個數(shù)為n，證中癥狀個數(shù)為m，則算法3的計算復雜度O(nm)。次相似度算法和主相似度算法相似，故省略。4中醫(yī)學中的癥狀組適應(yīng)度函數(shù)設(shè)計4.1適應(yīng)度函數(shù)簡介模擬生物的遺傳和進化規(guī)律，GEP使用適應(yīng)度（FitnessFunction）來度量群體中個體有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度高的參加遺傳活動的概率就大。CandidaFerreira提出了兩種適應(yīng)度計算方法：)(1=-=njjjTCMrorFitnessAbsoluteEr(4-1)100(Re1-=jjjnjTTCMrFitnesslativeErro(4-2)分別被稱為絕對誤差（4-1）和(4-2)稱為相對誤差。其中M稱為選擇范圍（RangofSelection）。Tj為第j個觀測值，Cj為第j個數(shù)據(jù)輸入公式的結(jié)果值，n表示測試數(shù)據(jù)的個數(shù)。在統(tǒng)計學中,用于評價兩組數(shù)據(jù)符合程度的方法是采用復相關(guān)系數(shù)。適應(yīng)度計算方法：SSTSSEntFitnessnCoefficieCorrelatio-=1(4-3)第25卷地11期計算機應(yīng)用Vol.25.No,112005年11月ComputerApplicationsNov.2005=-=njjjCTSSE12)(=-=njjTTSST12)(其中，T為Tj的平均值。4.2中醫(yī)學中的癥狀組適應(yīng)度函數(shù)以上的適應(yīng)度函數(shù)不適用于中醫(yī)的特殊環(huán)境，需要設(shè)計一種新穎的適應(yīng)度函數(shù)。首先我們引入：定義4（差距值）設(shè)P是一個方，F(xiàn)是P對應(yīng)的證，m1，m2分別是方P對證F的主相似度和次相似度（m1，m20），yf（a，b）進化后某一函數(shù)，F(xiàn)1是一個證，F(xiàn)1F，且m3，m4分別是方P對證F1的主相似度和次相似度（m3，m40）1)設(shè)y=f（m1，m2）稱y為最優(yōu)計算值（BestValue）。2)設(shè)y1=f（m3，m4），如果y1y，則稱yy1為差距值。易知差距值全為負值。由定義2，可推導出以下性質(zhì)：性質(zhì)11)當BestValue不是最大時：