基于遺傳算法的中藥藥對挖掘系統(tǒng)的設(shè)計與實現(xiàn)

基于遺傳算法的中藥藥對挖掘系統(tǒng)的設(shè)計與實現(xiàn)

1

引言1.1

背景我國作為最大的中藥材資源國，有著傳統(tǒng)中醫(yī)藥文明的發(fā)祥地的地位，但是如今正面臨著諸多挑戰(zhàn)。我國，在世界的中藥市場上卻未能占有基本的主導(dǎo)地位。反而日本、韓國等國家成功地利用現(xiàn)代數(shù)據(jù)挖掘科技把中藥行業(yè)發(fā)展成現(xiàn)代產(chǎn)業(yè)，占據(jù)了國際市場相當(dāng)?shù)姆蓊~，因此，繼承和發(fā)展中醫(yī)藥不僅是中醫(yī)界也是全國其他科研院校和科研機構(gòu)的重要課題。中藥對數(shù)據(jù)挖掘就是利用藥對數(shù)據(jù)庫從大量的中藥對中抽取隱含的、未知的、有意義的藥物組配模式。中藥對數(shù)據(jù)挖掘?qū)橹嗅t(yī)方劑理論研究和中醫(yī)臨床用藥研究提供重要模式參考，也為方劑配伍理論研究，尤其是新藥對、新藥組發(fā)現(xiàn)研究提供新方法和現(xiàn)代技術(shù)手段。1.2

意義關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的重要技術(shù)之一，它能反映在事務(wù)數(shù)據(jù)庫中數(shù)據(jù)項之間同時出現(xiàn)的規(guī)律，并發(fā)現(xiàn)不同數(shù)據(jù)項之間的聯(lián)系。關(guān)聯(lián)規(guī)則通過量化的數(shù)字描述數(shù)據(jù)項A的出現(xiàn)對數(shù)據(jù)項B的出現(xiàn)產(chǎn)生的影響。例如在大型商場中牛奶的銷售對面包的銷售的影響，發(fā)現(xiàn)這樣的規(guī)則不僅可以應(yīng)用于商品貨架設(shè)計、貨存安排，而且可以根據(jù)購買模式對用戶進行分類，制定相應(yīng)商務(wù)決策、銷售策略。由于關(guān)聯(lián)規(guī)則挖掘具有重要的現(xiàn)實意義，吸引了許多學(xué)者的研究，提出了眾多的關(guān)聯(lián)規(guī)則挖掘算法。目前，所有的關(guān)聯(lián)規(guī)則挖掘算法都是基于支持度-置信度框架理論，具有較多的局限性。本文通過分析這些不足之處，引入雙向關(guān)聯(lián)規(guī)則的概念，實現(xiàn)了基于遺傳算法的雙向關(guān)聯(lián)規(guī)則挖掘算法。2

理論基礎(chǔ)2.1

關(guān)聯(lián)規(guī)則及存在的問題關(guān)聯(lián)規(guī)則是形如A=>B的蘊涵式，挖掘關(guān)聯(lián)規(guī)則分為兩步：第一步是識別所有的頻繁項集，即支持度不小于用戶指定的最小支持度的項集；第二步是從頻繁項集中構(gòu)造其置信度不低于用戶給定最小置信度的規(guī)則，即強規(guī)則。這種基于支持度-置信度框架理論的關(guān)聯(lián)規(guī)則挖掘方法存在如下問題：（1）不能有效地發(fā)現(xiàn)低支持度高置信度的有趣規(guī)則基于支持度-置信度框架理論的關(guān)聯(lián)規(guī)則挖掘方法找到的強規(guī)則必須同時滿足最小支持度閾值和最小置信度閾值，但有時人們感興趣的規(guī)則往往是低支持度高置信度的[8]。例如，超市中兩物品A和B，它們的銷售量雖然很低，但經(jīng)常是同時被顧客購買，管理人員希望將這種低支持度高置信度的規(guī)則找出來。（2）不能確定“相互依賴”的規(guī)則關(guān)聯(lián)規(guī)則反映A、B同時出現(xiàn)的概率和A出現(xiàn)的條件下B出現(xiàn)的條件概率。這樣的規(guī)則只能確定A對B的“依賴”，不能同時確定B對A的“依賴”，但很多時候人們感興趣的是“相互依賴”的規(guī)則。例如，中藥的藥組藥對中，藥之間必須是“相互依賴”的，如果藥物A和B是藥對，則必須是A通常與B配伍，同時B也是通常與A配伍。如果只是A通常與B配伍，但B并不常與A配伍，則A和B不是藥對，因為B通常是只起輔助藥性作用的藥，這類藥常在各種方劑中出現(xiàn)。用基于支持度-置信度框架理論的關(guān)聯(lián)規(guī)則挖掘方法不能找出上述中藥藥組藥對。（3）找到的強規(guī)則并不一定是有趣的，甚至是錯誤的假定對分析涉及的家用電腦和VCD播放機的事務(wù)感興趣。在所分析的10000個事務(wù)中，6000個事務(wù)包含家用電腦，7500個事務(wù)包含VCD播放機，4000個事務(wù)同時包含家用電腦和VCD播放機。運行傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘程序，最小支持度30%，最小置信度60%，將發(fā)現(xiàn)下面的關(guān)聯(lián)規(guī)則：

buys(X,“computer”)buys(X,“vcd-player”)

[support=40%,confidence=66%]該規(guī)則是強關(guān)聯(lián)規(guī)則?？墒聦嵣?，電腦和VCD播放機是負相關(guān)的，買其中之一實際上減少了買另一種的可能性，因為購買VCD播放機的可能性是75%，大于66%。

2.2

雙向關(guān)聯(lián)規(guī)則定義1（雙向關(guān)聯(lián)規(guī)則）：設(shè)I={i1,i2,…,im}是項的集合，任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合，使得T

I。每個事務(wù)有一個標(biāo)示符，稱作TID。設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng)AT。如果AI，BI，并且A∩B=?，則形如AóB的表達式稱為雙向關(guān)聯(lián)規(guī)則。顯然雙向關(guān)聯(lián)規(guī)則是同時滿足A=>B和B=>A的規(guī)則。反過來也可以說同時滿足A=>B和B=>A的規(guī)則是雙向關(guān)聯(lián)規(guī)則。所有雙向關(guān)聯(lián)規(guī)則AóB有兩個置信度。一個是關(guān)聯(lián)規(guī)則A=>B的置信度：conf(A=>B)=P(B|A)=P(AB)/P(A)另一個是關(guān)聯(lián)規(guī)則B=>A的置信度：conf(A=>B)=P(A|B)=P(AB)/P(B)置信度conf(A=>B)表示A出現(xiàn)的條件下B出現(xiàn)的條件概率，也就是A和B同時出現(xiàn)的概率與A出現(xiàn)的概率的比值。它反映了A對B的依賴程度。它的值越大，則A對B的依賴越強；反之，值越小，則A對B的依賴越弱。如果值為1，則意味著A的每一次出現(xiàn)都伴隨著B的出現(xiàn)（反過來則不一定），A對B是100%的依賴。置信度conf(B=>A)表示B出現(xiàn)的條件下A出現(xiàn)的條件概率，也就是B和A同時出現(xiàn)的概率與B出現(xiàn)的概率的比值。它反映了B對A的依賴程度。它的值越大，則B對A的依賴越強；反之，值越小，則B對A的依賴越弱。如果值為1，則意味著B的每一次出現(xiàn)都伴隨著A的出現(xiàn)（反過來則不一定），B對A是100%的依賴。雙向關(guān)聯(lián)規(guī)則AóB的這兩個置信度共同反映了A和B的相互依賴程度。我們很多時候?qū)ο嗷ヒ蕾嚦潭雀叩囊?guī)則——即下面定義的強雙向規(guī)則感興趣。定義2（強雙向規(guī)則）：規(guī)則A=>B和B=>A同時滿足最小置信度閾值（min_conf）的雙向規(guī)則稱作強雙向規(guī)則。下面把上述概念推廣到多個項集之間的情況。定義3（n個項集的雙向關(guān)聯(lián)規(guī)則）：設(shè)CiìI(2<i≤n),并且Ci∩Cj=?(2<i≤n，2<j≤n,i≠j)，n項集C1、C2、…,Cn的雙向關(guān)聯(lián)規(guī)則為同時滿足C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的規(guī)則，此時C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1的置信度分別為：

Conf(C1=>C2C3…Cn)=P(C2C3…Cn|C1)=P(C1C2…Cn)/P(C1)

Conf(C2=>C1C3…Cn)=P(C1C3…Cn|C2)=P(C1C2…Cn)/P(C2)……Conf(Cn=>C1C3…C(n-1))=P(C1C2…C(n-1)|Cn)=P(C1C2…Cn)/P(Cn)

如果C1=>C2C3…Cn、C2=>C1C3…Cn、…、Ci=>C1C2…Ci-1Ci+1…Cn、…、Cn=>C1C2…Cn-1同時滿足最小置信度閾值（min_conf），則項集C1、C2、…、Cn的雙向關(guān)聯(lián)規(guī)則是強雙向規(guī)則。項的集合稱為項集(itemset)，包含k個項的項集稱為k-項集。我們把上述概念用于k-項集，可得到如下定義：定義4（項的置信度）：設(shè)Tk={I1,I2,…,Ik}是一個k-項集，Ii（1≤I≤k）是Tk的一項，則k-項集Tk的項Ii的置信度conf(Ii,Tk)為事務(wù)數(shù)據(jù)庫D中包含{Ii}的事務(wù)同時包含{I1,I2,…,I(i-1),I(i+1),…,Ik}的百分比，即：

Conf(Ii,Tk)=P({I1,I2,…,I(i-1),I(i+1),,Ik}|{Ii})=P({I1,I2,…,Ii,…,Ik})/P({Ii})定義5（k-項集強雙向規(guī)則）：設(shè)Tk={I1,I2,…,Ik}是事務(wù)數(shù)據(jù)庫D中一個k-項集，如果Tk的任一項的置信度都滿足最小置信度閾值(min_conf)，則稱k-項集Tk為符合強雙向規(guī)則的k-項集，簡稱k-項集強雙向規(guī)則。2.3

遺傳算法簡介遺傳算法（GeneticAlgorithm,GA）是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學(xué)和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應(yīng)性的提高。從某種程度上說遺傳算法是對生物進化過程進行的數(shù)學(xué)方式仿真。這一點體現(xiàn)了自然界中"物競天擇、適者生存"進化過程。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價,把問題的解表示成染色體，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機會。在算法中也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群染色體，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，也即一個適應(yīng)度函數(shù)中來評價。并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的染色體進行復(fù)制,淘汰低適應(yīng)度的個體，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代染色體群。對這個新種群進行下一輪進化，至到最適合環(huán)境的值。由于遺傳算法是由進化論和遺傳學(xué)機理而產(chǎn)生的搜索算法，所以在這個算法中會用到很多生物遺傳學(xué)知識，下面是將會用到的一些術(shù)語說明：一、染色體(Chromosome)染色體又可以叫做基因型個體(individuals),一定數(shù)量的個體組成了群體(population),群體中個體的數(shù)量叫做群體大小。二、基因(Gene)基因是串中的元素，基因用于表示個體的特征。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。三、適應(yīng)度(Fitness)各個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness)。為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進行度量的函數(shù)，叫適應(yīng)度函數(shù).這個函數(shù)是計算個體在群體中被使用的概率。四、種群（population）染色體帶有特征的個體的集合稱為種群。該集合個體數(shù)稱為種群個體的大小。3

需求分析及設(shè)計方案由于事務(wù)數(shù)據(jù)庫一般只具有對大量數(shù)據(jù)的存取、檢索功能，對于用戶的一般性的使用可以滿足，然而，正是由于數(shù)據(jù)庫中存放了大量的數(shù)據(jù)，不同的數(shù)據(jù)項，以及多個數(shù)據(jù)項之間還存在有大量的隱含的、未知的、有意義的數(shù)據(jù)關(guān)系，這些關(guān)系對于用戶有著及其重要的作用，所以數(shù)據(jù)挖掘便在此情況下產(chǎn)生了。遺傳算法是數(shù)據(jù)挖掘技術(shù)中的一個重要算法。這是由于它具有快捷、簡便、魯棒性強、適于并行處理以及高效、實用等顯著特點，在各類結(jié)構(gòu)對象的優(yōu)化過程中顯示出明顯的優(yōu)勢。它的思想源于生物遺傳學(xué)和適者生存的自然規(guī)律，是具有“生存＋檢測”的迭代過程的搜索算法。遺傳算法以一種群體中的所有個體為對象，并利用隨機化技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；初始種群編碼、初始群體個數(shù)的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計、控制參數(shù)設(shè)定五個要素組成了遺傳算法的核心內(nèi)容。與傳統(tǒng)的搜索方法相比，遺傳算法具有如下特點：（1）搜索過程不直接作用在變量上，而是在參數(shù)集進行了編碼的個體。此編碼操作，使得遺傳算法可直接對結(jié)構(gòu)對象（集合、序列、矩陣、樹、圖、鏈和表）進行操作。（2）搜索過程是從一組解迭代到另一組解，采用同時處理群體中多個個體的方法，降低了陷入局部最優(yōu)解的可能性，并易于并行化。（3）采用概率的變遷規(guī)則來指導(dǎo)搜索方向，而不采用確定性搜索規(guī)則。對搜索空間沒有任何特殊要求，只利用適應(yīng)性信息，不需要導(dǎo)數(shù)等其它輔助信息，適應(yīng)范圍更廣。中國自古以來就有著傳統(tǒng)中醫(yī)藥文明的發(fā)祥地的地位,中藥是我國特有的資源，但是中國本土中醫(yī)學(xué)長期以來的發(fā)展并不是很大，在國際醫(yī)學(xué)界就更不具有很強的地位。多年的時間過去了，中藥方劑的更新和發(fā)展并沒有很大的變化，很多都還建立在很久以前就有的方劑基礎(chǔ)之上，沒有出現(xiàn)比較多的較新的方劑，應(yīng)用遺傳算法的數(shù)據(jù)挖掘系統(tǒng)在此情況下可以發(fā)揮著及其重要的作用。通過數(shù)據(jù)系統(tǒng)能夠在藥對數(shù)據(jù)庫的大量數(shù)據(jù)中，找到很多隱含的、未知的、并很有應(yīng)用價值的藥對藥組以及很多的有意義的藥物組配的規(guī)則和模式。中藥對數(shù)據(jù)挖掘還將為中醫(yī)方劑理論研究和中醫(yī)臨床用藥研究提供重要模式參考，也為方劑配伍理論研究，尤其是新藥對、新藥組發(fā)現(xiàn)研究提供新方法和現(xiàn)代技術(shù)手段。在系統(tǒng)進行數(shù)據(jù)挖掘過程中，為了減少對事務(wù)數(shù)據(jù)庫的掃描、提高挖掘效率，本文先把事務(wù)數(shù)據(jù)庫轉(zhuǎn)化成位圖矩陣，然后再在此位圖矩陣上挖掘有