FP-Growth算法在中藥數(shù)據(jù)挖掘中的應(yīng)用

張 博

(亳州職業(yè)技術(shù)學(xué)院信息工程系,亳州236800)

數(shù)據(jù)挖掘就是從大型數(shù)據(jù)庫的數(shù)據(jù)中提取人們感興趣的知識(shí).這些知識(shí)是隱含的、實(shí)現(xiàn)未知的潛在的有用信息,通過數(shù)據(jù)挖掘技術(shù),用戶可以從數(shù)據(jù)庫中提取有用的知識(shí)、規(guī)律和深層次信息,同時(shí)還可以從不同角度觀察和分析挖掘結(jié)果.

中藥方劑是中國(guó)傳統(tǒng)醫(yī)學(xué)的重要組成部分,由于中藥方劑主要是歷代醫(yī)生的手工匯總,其整體性、辯證性等特征過于抽象和定性化,無法像西方醫(yī)學(xué)那樣能夠準(zhǔn)確的定量.而將數(shù)據(jù)挖掘技術(shù)應(yīng)用于中藥方劑的配伍研究中,是把我國(guó)傳統(tǒng)的中醫(yī)藥資源和現(xiàn)代信息技術(shù)相結(jié)合的重要途徑.

亳州地處安徽北部,氣候和土壤適宜中藥材的生長(zhǎng),自古以來就有中藥材種植和交易的歷史,被譽(yù)為＂中華藥都＂.亳州是神醫(yī)華佗的故里,得天獨(dú)厚的中醫(yī)藥資源為中藥方劑的研究提供了堅(jiān)實(shí)的基礎(chǔ),同時(shí)也為本文進(jìn)行中藥方劑的數(shù)據(jù)挖掘工作提供了豐富的資源.

1 關(guān)聯(lián)規(guī)則

在中醫(yī)觀點(diǎn)中,很多癥狀的診斷之間是存在著關(guān)聯(lián)性.而在藥方的搭配上,也同樣存在著很多關(guān)聯(lián)性.以關(guān)聯(lián)規(guī)則為主要算法的數(shù)據(jù)挖掘,是分析中藥關(guān)聯(lián)性的有效方法.

數(shù)據(jù)關(guān)聯(lián)是某種事物發(fā)生時(shí)其它事物會(huì)發(fā)生的一種聯(lián)系,是數(shù)據(jù)庫中存在的一類重要的可被發(fā)現(xiàn)的知識(shí).而關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘是從大量的、有噪聲的、模糊的實(shí)際數(shù)據(jù)中,抽取隱含在其中的、人們事先不知道的、但又潛在有用的關(guān)聯(lián)信息和知識(shí)的過程.

Apriori算法是一種常見的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法.其核心是基于兩階段頻集思想的遞推算法.該關(guān)聯(lián)規(guī)則在分類上屬于單維、單層、布爾關(guān)聯(lián)規(guī)則.該算法的基本思想是:首先找出所有的頻繁集,這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣.然后由頻集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則,這些規(guī)則必須滿足最小支持度和最小可信度.然后使用第1步找到的頻集產(chǎn)生期望的規(guī)則,產(chǎn)生只包含集合的項(xiàng)的所有規(guī)則,其中每一條規(guī)則的右部只有一項(xiàng),這里采用的是中規(guī)則的定義.一旦這些規(guī)則被生成,那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來.為了生成所有頻集,使用了遞推的方法.

Apriori算法易于實(shí)現(xiàn),但在實(shí)際中存在有一些難以克服的缺陷:如對(duì)數(shù)據(jù)庫的掃描次數(shù)過于頻繁、會(huì)產(chǎn)生大量候選集合等,這樣就使得Apriori算法的時(shí)間和空間復(fù)雜度過大.因此,在本文中,提出了基于FP-Growth算法的中藥數(shù)據(jù)挖掘算法,并將算法應(yīng)用在中藥配方的關(guān)聯(lián)度方面,進(jìn)行了探討.

2 FP-Growth算法

(1)FP-tree

在介紹FP-Growth方法之前,對(duì)FP-tree做如下定義:

①頻繁模式樹(Frequent Pattern tree)簡(jiǎn)稱為FP-tree,是滿足下列條件的一個(gè)樹結(jié)構(gòu):它由一個(gè)根節(jié)點(diǎn)(值為null)、項(xiàng)前綴子樹(作為子女)和一個(gè)頻繁項(xiàng)頭表組成.

②項(xiàng)前綴子樹中的每個(gè)結(jié)點(diǎn)包括三個(gè)域:item_name、count和 node_link,其中:item_name 記錄結(jié)點(diǎn)表示的項(xiàng)的標(biāo)識(shí);count記錄到達(dá)該結(jié)點(diǎn)的子路徑的事務(wù)數(shù);node_link用于連接樹中相同標(biāo)識(shí)的下一個(gè)結(jié)點(diǎn),如果不存在相同標(biāo)識(shí)下一個(gè)結(jié)點(diǎn),則值為“null” .

③為了方便樹遍歷,創(chuàng)建一個(gè)頻繁項(xiàng)頭表(frequent item header table),頻繁項(xiàng)頭表的表項(xiàng)包括一個(gè)頻繁項(xiàng)標(biāo)識(shí)域:item_name和一個(gè)指向樹中具有該項(xiàng)標(biāo)識(shí)的第一個(gè)頻繁項(xiàng)結(jié)點(diǎn)的頭指針:head of node_link.

(2)FP-Growth算法

FP-Growth算法使用一種緊縮的數(shù)據(jù)結(jié)構(gòu)Fptree來存儲(chǔ)查找頻繁項(xiàng)目集所需要的全部信息.將提供頻繁項(xiàng)目集的數(shù)據(jù)庫壓縮到FP-tree中,但保留項(xiàng)集關(guān)聯(lián)信息;然后,將壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫,每個(gè)關(guān)聯(lián)一個(gè)頻繁項(xiàng)目集.這樣避開了產(chǎn)生候選項(xiàng)集的步驟,極大的減少了數(shù)據(jù)交換和頻繁匹配的開銷,并且將數(shù)據(jù)庫頻繁模式的挖掘問題轉(zhuǎn)化成挖掘FP-tree的問題.因此,在挖掘效率上FP-Growth算法明顯優(yōu)于Apriori算法,特別是在稠密數(shù)據(jù)庫中,頻繁項(xiàng)集的長(zhǎng)度很大的情況下,FPGrowth算法的優(yōu)勢(shì)越明顯.

其具體步驟如下:

①掃描事務(wù)數(shù)據(jù)庫D一遍,得到頻繁項(xiàng)的集合F和每個(gè)頻繁項(xiàng)的支持度.把F按支持度遞降排序,然后構(gòu)造FP-tree

②挖掘FP-tree.由每個(gè)長(zhǎng)度為1的頻繁模式(初始后綴模式)開始,構(gòu)造它的條件模式基,然后構(gòu)造它的(條件)FP-tree,并遞歸地對(duì)該樹進(jìn)行挖掘.模式增長(zhǎng)通過后綴模式與條件FP-tree產(chǎn)生的頻繁模式連接實(shí)現(xiàn).

③直到結(jié)果FP-tree為空,或者其只包含一個(gè)路徑,這個(gè)路徑可以生成所有子路徑的組合,每個(gè)組合都是一個(gè)頻繁模式.

一旦由數(shù)據(jù)庫D中的事務(wù)找出頻繁項(xiàng)集,就可以從它們中產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則(強(qiáng)關(guān)聯(lián)規(guī)則滿最小支持度和最小置信度).由于規(guī)則由頻繁項(xiàng)集產(chǎn)生,每個(gè)規(guī)則自動(dòng)地滿足最小支持度,所以輸出的規(guī)則是強(qiáng)關(guān)聯(lián)規(guī)則.

3 基于FP-Growth算法的中藥數(shù)據(jù)挖掘

方劑配伍的主要工作是提出適合中藥方劑數(shù)據(jù)挖掘的算法,并將算法應(yīng)用于數(shù)據(jù)挖掘模式的研究中.針對(duì)中藥方劑的數(shù)據(jù)特點(diǎn),提出改進(jìn)的數(shù)據(jù)挖掘模式和算法,使用最大頻繁關(guān)聯(lián)模式對(duì)中藥方劑進(jìn)行研究,然后對(duì)藥物配伍規(guī)律與藥物藥性結(jié)合起來進(jìn)行數(shù)據(jù)挖掘的研究.

下面我們以中藥方劑中的溫中祛寒劑來說明通過FP-Growth算法發(fā)現(xiàn)中藥的藥性關(guān)聯(lián)規(guī)則.

方劑學(xué)中的溫中祛寒方劑主要有5個(gè):理中湯、吳茱萸湯、大建中湯、小建中湯、縮脾飲,每個(gè)方劑的組成如下:理中湯(人參、白術(shù)、干姜、炙甘草);吳茱萸湯(吳茱萸、人參、大棗、生姜);大建中湯(川椒、干姜、人參、飴糖);小建中湯(酒芍藥、桂枝、炙甘草、生姜、大棗、飴糖);縮脾飲(縮砂仁、煨草果、烏梅肉、葛根、白扁豆、炙甘草).

根據(jù)以上方劑的成分進(jìn)行編碼如下:人參為I1,白術(shù)為 I2,干姜為I3,炙甘草為I4,吳茱萸為I5,大棗為I6,生姜為I7,川椒為 I8,飴糖為 I9,酒芍藥為I10,桂枝為I11,縮砂仁為 I12,煨草果為 I13,烏梅肉為I14,葛根為I15,白扁豆為I16.理中湯為事務(wù)T1,吳茱萸為事務(wù)T2,大建中湯為事務(wù)T3,小建中湯為事務(wù)T4,縮脾飲為事務(wù)T5.

接下來,建立溫中祛寒劑的數(shù)據(jù)庫如下:

表1 溫中祛寒劑數(shù)據(jù)庫

設(shè)最小支持度為2,得到符合條件的按照支持度排序的項(xiàng)集如下:

表2 支持度為2的項(xiàng)集

由頻繁項(xiàng)集構(gòu)建FP-tree,如圖1所示:

圖1 根據(jù)溫中驅(qū)寒劑建立的FP-tree

對(duì)FP-tree進(jìn)行數(shù)據(jù)挖掘,可以得到方劑中的頻繁模式:

表3 通過條件模式基挖掘

從表3的挖掘過程中,我們可以得到如下的中藥組合關(guān)系:

①大棗、生姜;②人參、干姜;③人參、炙甘草;

這些組合還需要結(jié)合具體的中醫(yī)治療的實(shí)踐來進(jìn)一步驗(yàn)證和篩選,以達(dá)到最佳的藥性組合.

4 總 結(jié)

由于方劑中的藥物不僅關(guān)聯(lián),而且大量藥物之間存在相互的藥性作用,所以將數(shù)據(jù)挖掘技術(shù)應(yīng)用在中藥方劑配伍的研究上,具有很大的發(fā)展前景.本文中只是進(jìn)行了小范圍的數(shù)據(jù)樣本的實(shí)驗(yàn),在后期的工作中,會(huì)依靠已經(jīng)建立的各專業(yè)中藥數(shù)據(jù)庫的資源,進(jìn)一步擴(kuò)大樣本和方劑的范圍,從而找到具有更好療效的中藥組合,為中藥方劑的配伍提供可靠的研究依據(jù).

[1]姚美村,袁月梅,艾 路,喬延江.數(shù)據(jù)挖掘及其在中醫(yī)藥現(xiàn)代化研究中的應(yīng)用[J].北京中醫(yī)藥大學(xué)學(xué)報(bào),2002,25(5):20-24.

[2]喬延江,李澎濤,蘇剛強(qiáng),肖培銀,王永炎.中藥(方劑)KDD研究開發(fā)的意義[J].北京中醫(yī)藥大學(xué)學(xué)報(bào),1998,21(3):15-17.

[3]李 亞.中醫(yī)名方配伍技巧[M].北京科學(xué)技術(shù)出版社,2003:45-47.

[4]謝 含.數(shù)據(jù)挖掘在中醫(yī)藥文獻(xiàn)研究中的應(yīng)用[J].中醫(yī)藥信息,2005,22(6):125-127.

[5]王瑞祥.基于FP-growth算法的中藥關(guān)聯(lián)程度分析[J].遼寧中醫(yī)藥大學(xué)學(xué)報(bào),2007,9(4):7-8.

[6]劉閩碧.基于FP-growth算法的中藥配方數(shù)據(jù)挖掘[J].醫(yī)學(xué)信息,2009,22(12):2629-2630.

[7]顧紅其.面向電子商務(wù)的WEB挖掘中關(guān)聯(lián)算法的研究[D].蘇州大學(xué)碩士論文,2009:25-29.

[8]高 明.關(guān)聯(lián)規(guī)則挖掘算法的研究及其應(yīng)用[D].山東師范大學(xué)碩士論文,2006.