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

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