基于改進(jìn)關(guān)聯(lián)規(guī)則算法的中醫(yī)治療癭病用藥規(guī)律挖掘

楊文敏，佘侃侃，葉 丹

（1.南京中醫(yī)藥大學(xué) 人工智能與信息技術(shù)學(xué)院；2.中科南京軟件技術(shù)研究院，江蘇 南京 210023）

0 引言

癭病是一中醫(yī)病證名，是以頸前喉結(jié)兩旁結(jié)塊腫大為主要臨床特征的一類疾?。?］?，F(xiàn)代醫(yī)學(xué)中癭病的臨床表現(xiàn)包括單純性甲狀腺腫、甲狀腺功能亢進(jìn)癥、甲狀腺炎、甲狀腺腺瘤、甲狀腺癌等以甲狀腺腫大為等［2］。近年來，隨著生活習(xí)慣的改變，甲狀腺疾病發(fā)病率明顯上升，甲狀腺癌成為全球發(fā)病率增長最快的常見腫瘤［3］。中醫(yī)針對(duì)癭病治療在中醫(yī)學(xué)中早有記載，并積累了豐富的經(jīng)驗(yàn)，挖掘臨床中醫(yī)藥治療癭病藥物之間的關(guān)聯(lián)規(guī)則，并結(jié)合中醫(yī)學(xué)中針對(duì)癭病的方劑配伍規(guī)律，可以更好地服務(wù)于癭病中醫(yī)治療。

數(shù)字化信息技術(shù)發(fā)展日新月異，為醫(yī)療健康產(chǎn)業(yè)發(fā)展注入新動(dòng)力［4］。隨著數(shù)據(jù)挖掘技術(shù)的不斷成熟，其在醫(yī)療，尤其在中醫(yī)藥領(lǐng)域中的應(yīng)用日益深入［5］。利用數(shù)據(jù)挖掘技術(shù)，可挖掘藥物之間的關(guān)聯(lián)規(guī)則，尋找藥物之間的聯(lián)系和用藥規(guī)律；在名老中醫(yī)臨床診治病證時(shí)，可通過對(duì)藥物關(guān)聯(lián)規(guī)則的挖掘，尋找核心藥群，深入了解組方規(guī)律，從而輔助診療。付喜芳等［6］分析黃宗瑁教授治療方中治療婦產(chǎn)科等疾病潛在的用藥配伍規(guī)律；龐晴等［7］探究倪青教授治療甲狀腺結(jié)節(jié)的用藥經(jīng)驗(yàn)與組方規(guī)律。上述研究運(yùn)用數(shù)據(jù)挖掘技術(shù)對(duì)中醫(yī)治療專病的用藥規(guī)律進(jìn)行關(guān)聯(lián)規(guī)則分析，但缺乏對(duì)具體挖掘關(guān)聯(lián)規(guī)則算法效率的深入探討。在數(shù)據(jù)快速轉(zhuǎn)換成有效信息的迫切需求下，關(guān)聯(lián)規(guī)則挖掘算法也被不斷改進(jìn)優(yōu)化并應(yīng)用于各數(shù)據(jù)挖掘任務(wù)。蔣茜茜等［8］利用改進(jìn)的Apriori 算法對(duì)高校體測數(shù)據(jù)進(jìn)行分析并對(duì)算法作效率對(duì)比；王慧敏等［9］提出一種融合Apriori 優(yōu)化算法對(duì)中醫(yī)治療抑郁癥用藥規(guī)律進(jìn)行挖掘，并與Relim 算法進(jìn)行對(duì)比，但對(duì)比效果不明顯，效率較低。因此，本文對(duì)中醫(yī)治療癭病的藥方數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則分析，同時(shí)提出改進(jìn)的FP-growth 算法，與兩種經(jīng)典的Apriori 改進(jìn)算法在中醫(yī)藥數(shù)據(jù)上的數(shù)據(jù)挖掘效率進(jìn)行比較。

1 相關(guān)算法

1.1 關(guān)聯(lián)規(guī)則基本概念

關(guān)聯(lián)規(guī)則反映數(shù)據(jù)庫中項(xiàng)之間的關(guān)聯(lián)關(guān)系。項(xiàng)的集合稱為項(xiàng)集，包含k 個(gè)項(xiàng)集被稱為k-項(xiàng)集，k 表示項(xiàng)集中項(xiàng)的數(shù)目，事務(wù)是項(xiàng)的集合，事務(wù)集是事務(wù)的集合。設(shè)I＝｛I1，I2，…，In｝是項(xiàng)的集，D 是事務(wù)集，若項(xiàng)集A 和項(xiàng)集B 均包含于集合I且均不為空集，且A∩B=?，則關(guān)聯(lián)規(guī)則A=＞B的支持度為s，置信度為c，分別如式（1）和式（2）所示。

其中，count（A∪B）表示A 和B 同時(shí)出現(xiàn)的事務(wù)個(gè)數(shù)，TotalCount表示事務(wù)集中事務(wù)的個(gè)數(shù)。

其中，count（A）表示出現(xiàn)A 的事務(wù)個(gè)數(shù)。

1.2 Apriori算法

Apriori 算法是一種經(jīng)典算法，用于挖掘數(shù)據(jù)集中頻繁項(xiàng)集和規(guī)則。本質(zhì)上，Apriori 算法由兩部分組成：找頻繁項(xiàng)集和產(chǎn)生關(guān)聯(lián)規(guī)則，

（1）依據(jù)支持度找頻繁項(xiàng)集。首次掃描事務(wù)數(shù)據(jù)庫D，獲取所有項(xiàng)即得到所有候選1-項(xiàng)集，將所有候選1-項(xiàng)集組成的集合計(jì)作C1，統(tǒng)計(jì)C1每個(gè)項(xiàng)的計(jì)數(shù)，判斷是否大于最小支持度，大于則為頻繁1-項(xiàng)集，將所有頻繁1-項(xiàng)集的集合記作L1，由L1自連接生成所有候選2-項(xiàng)集，所有候選2-項(xiàng)集組成的集合計(jì)作C2，同樣通過C2找到所有滿足最小支持度的頻繁2-項(xiàng)集組成集合頻繁2-項(xiàng)集L2，再由L2得到C2找到滿足最小支持度的頻繁3-項(xiàng)集L3，以此類推，從候選項(xiàng)集中找到滿足最小支持度的頻繁項(xiàng)集，直到找到頻繁k項(xiàng)集集合Lk為空，得到所有頻繁項(xiàng)集。

（2）依據(jù)置信度產(chǎn)生關(guān)聯(lián)規(guī)則。掃描所有頻繁項(xiàng)集，輸出滿足最小置信度的關(guān)聯(lián)規(guī)則。

Apriori算法流程如圖1所示。

Fig.1 Apriori algorithm flow圖1 Apriori算法流程

Apriori 算法在多次掃描數(shù)據(jù)庫時(shí)會(huì)產(chǎn)生大量候選項(xiàng)集，算法效率低、復(fù)雜度高［17］。

1.3 Apriori改進(jìn)算法

針對(duì)Apriori 算法的不足，本文基于事務(wù)壓縮技術(shù)［10］和基于散列技術(shù)［11］對(duì)Apriroi 算法進(jìn)行改進(jìn)，雖然兩者的主要作用是在Apriori 算法的剪枝部分，但前者通過減少候選項(xiàng)集的大小，在經(jīng)典Apriori 算法的基礎(chǔ)上進(jìn)一步減少數(shù)據(jù)庫掃描次數(shù)，而后者則是通過不斷減少數(shù)據(jù)庫中事務(wù)集中事務(wù)的總量和長度，以提升效率［12］。這兩種方法都對(duì)數(shù)據(jù)挖掘效率提升有一定幫助。

1.4 FP-growth算法

FP-Growth［19］算法基于Apriori 原理，通過事務(wù)集D 存儲(chǔ)到FP-tree（Frequent Pattern tree）頻繁項(xiàng)樹，進(jìn)而挖掘頻繁項(xiàng)和關(guān)聯(lián)規(guī)則。算法流程主要包括構(gòu)建頻繁項(xiàng)樹和從頻繁項(xiàng)樹中挖掘頻繁項(xiàng)集兩個(gè)步驟［20］：

（1）構(gòu)建FP 樹。具體過程如下：①初始化FP-tree 創(chuàng)建根節(jié)點(diǎn)T=null；②根據(jù)頭指針表，從FP-tree 的根結(jié)點(diǎn)開始更新FP-tree：如果當(dāng)前事務(wù)項(xiàng)的第一個(gè)元素項(xiàng)存在于FP-tree 中，則更新這個(gè)子節(jié)點(diǎn)的計(jì)數(shù)值，否則創(chuàng)建新的子節(jié)點(diǎn)，依次對(duì)當(dāng)前事務(wù)項(xiàng)的其他數(shù)據(jù)集進(jìn)行同樣操作［21］；③依次將所有事務(wù)項(xiàng)的數(shù)據(jù)項(xiàng)插入到FP-tree 中。

（2）從FP-tree 中挖掘頻繁項(xiàng)集。從構(gòu)建好的FP 樹中獲得頻繁項(xiàng)的前綴路徑［13］，然后將前綴路徑作為新的數(shù)據(jù)集構(gòu)建條件FP 樹，再在新的FP 樹中的獲得頻繁項(xiàng)并以此構(gòu)建條件FP 樹。根據(jù)此規(guī)律，直到條件FP 樹中只有一個(gè)頻繁項(xiàng)集為止［22］。

1.5 FP-growth算法改進(jìn)

FP-growth 算法利用FP-tree 存儲(chǔ)關(guān)于頻繁項(xiàng)集的壓縮信息，相較于Apriori 算法，在挖掘頻繁項(xiàng)集時(shí)，只對(duì)事務(wù)數(shù)據(jù)庫掃描兩次，極大提高了數(shù)據(jù)頻繁項(xiàng)集的挖掘速度。但在構(gòu)建FP-tree 樹時(shí)，重復(fù)事物項(xiàng)也會(huì)構(gòu)建重復(fù)tree，導(dǎo)致關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘效率降低。

1.5.1 散列技術(shù)

散列技術(shù)通過散列函數(shù)將要檢索的項(xiàng)與索引（散列、散列值）關(guān)聯(lián)起來［14］，將數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來，形成一種便于檢索的數(shù)據(jù)保存格式，生成一種便于搜索的數(shù)據(jù)結(jié)構(gòu)［15］。

1.5.2 改進(jìn)算法主要思想

針對(duì)在事務(wù)項(xiàng)重復(fù)項(xiàng)較多的事務(wù)集數(shù)據(jù)庫，本文在此基礎(chǔ)上提出一種FP-growth 改進(jìn)算法，通過散列技術(shù)進(jìn)一步對(duì)數(shù)據(jù)進(jìn)行壓縮，通過創(chuàng)建空數(shù)據(jù)字典D_dict=｛key1：vaule1，key2：value2，…｝用于存儲(chǔ)key-value 映射關(guān)系集合，key對(duì)應(yīng)原事務(wù)集D 中的不重復(fù)的事務(wù)，value對(duì)應(yīng)事務(wù)出現(xiàn)的頻次，通過遍歷得到壓縮后數(shù)據(jù)字典D_dict，再進(jìn)行后面兩次的數(shù)據(jù)遍歷操作時(shí)，遍歷次數(shù)減少，進(jìn)一步縮短了FP-growth 算法創(chuàng)建FP-tree 的時(shí)間。改進(jìn)算法總體流程如算法1所示。

算法1FP-growth改進(jìn)算法

1.5.3 改進(jìn)算法主要流程

改進(jìn)的FP-growth 針對(duì)原始事務(wù)數(shù)據(jù)集中的重復(fù)事務(wù)集重復(fù)生成頻繁項(xiàng)樹的問題，通過遍歷事務(wù)集生成事務(wù)項(xiàng)-事務(wù)項(xiàng)頻次映射關(guān)系保存在數(shù)據(jù)字典中，從而壓縮原始事務(wù)集，減少頻繁項(xiàng)樹數(shù)的生成。算法主要改進(jìn)部分流程如圖2所示。

Fig.2 Flow of improved FP-growth algorithm圖2 改進(jìn)FP-growth算法流程

2 數(shù)據(jù)挖掘?qū)嶒?yàn)及結(jié)果分析

本文通過比較改進(jìn)的關(guān)聯(lián)規(guī)則算法對(duì)名老中醫(yī)臨床診治癭病的藥物組合進(jìn)行關(guān)聯(lián)規(guī)則分析，并針對(duì)算法性能給出對(duì)應(yīng)的結(jié)果比較。實(shí)驗(yàn)結(jié)果包括關(guān)聯(lián)規(guī)則結(jié)果和算法性能比較兩部分。

2.1 原數(shù)據(jù)

本文數(shù)據(jù)來源于名老中醫(yī)臨床診治癭病的多條臨床數(shù)據(jù)記錄，每條記錄包括患者的基本信息（性別、年齡）、臨床表現(xiàn)、舌像、脈象、標(biāo)準(zhǔn)化方藥、劑量等。本文實(shí)驗(yàn)所用到的數(shù)據(jù)列為標(biāo)準(zhǔn)化方藥列，也即中醫(yī)臨床診治患者的方劑數(shù)據(jù)（方劑數(shù)據(jù)示例：｛（醋柴胡5，炙鱉甲（先煎）10，鹿角片（先煎）10，夏枯草10，海藻10，炙僵蠶10，仙靈脾10，桃仁10，制南星10，牡蠣（先煎）25，山慈菇12，巴戟肉10，金毛狗脊15，川續(xù)斷15，當(dāng)歸10）｝）。

2.2 數(shù)據(jù)預(yù)處理

本文數(shù)據(jù)來源于名老中醫(yī)臨床診治癭病的方劑數(shù)據(jù)，選取數(shù)據(jù)中的方劑數(shù)據(jù)，對(duì)方劑數(shù)據(jù)中的標(biāo)準(zhǔn)化方藥進(jìn)行預(yù)處理操作，包括對(duì)方劑中藥物缺失的數(shù)據(jù)進(jìn)行刪除，去除藥物劑量，并結(jié)合《中醫(yī)方劑大辭典》進(jìn)一步對(duì)藥名進(jìn)行規(guī)范，整理得到296 條中醫(yī)藥治療癭病的方劑數(shù)據(jù)。以每一方劑為一事務(wù)，每個(gè)方劑中每一藥物為一項(xiàng)整理得到中醫(yī)藥數(shù)據(jù)事務(wù)集。

2.3 實(shí)驗(yàn)過程

經(jīng)過數(shù)據(jù)預(yù)處理的中醫(yī)數(shù)據(jù)D=｛｛桔梗，生薏米，茯苓，炒白術(shù)，貓爪草，川芎，當(dāng)歸，山海螺，山慈姑粉，壁虎，蜂房，皂刺，炒枳殼，浙貝粉，牡蠣｝，｛太子參，炒僵蠶，炒杏仁，桔梗，壁虎，蜂房，皂刺，元胡，川芎，當(dāng)歸，葶藶子，白芍，制五靈脂，炒川楝子，砂仁，丹參，炒枳殼，茯苓，炒白術(shù)，浙貝粉｝…｝，通過不同的算法進(jìn)行用藥規(guī)律數(shù)據(jù)挖掘，通過控制變量法統(tǒng)計(jì)各算法運(yùn)行時(shí)間，在相同環(huán)境下，統(tǒng)計(jì)算法運(yùn)行時(shí)間并將其作為衡量算法效率的標(biāo)準(zhǔn)。

2.4 癭病用藥規(guī)律數(shù)據(jù)挖掘結(jié)果

對(duì)中醫(yī)藥數(shù)據(jù)事務(wù)集進(jìn)行數(shù)據(jù)挖掘，將各算法的最小支持度和最小置信度分別設(shè)置為0.3 和0.8。并且，運(yùn)用這幾種改進(jìn)關(guān)聯(lián)規(guī)則算法進(jìn)行數(shù)據(jù)挖掘，算法挖掘的頻繁項(xiàng)集結(jié)果相同，皆為23 個(gè)頻繁項(xiàng)集，且頻繁1、2、3 項(xiàng)集相同，頻繁項(xiàng)集具體如表1 所示，藥物關(guān)聯(lián)規(guī)則如表2 所示。各算法在中醫(yī)藥治療癭病的數(shù)據(jù)事務(wù)集挖掘的用藥規(guī)律結(jié)果相同，相互印證，證明算法挖掘結(jié)果的有效性。結(jié)合表1對(duì)挖掘結(jié)果進(jìn)行分析發(fā)現(xiàn)，夏枯草、制香附、玄參、天冬、炙僵蠶等為中醫(yī)治療癭病的常用藥，草枯草清肝瀉火，制香附行氣解郁，玄參滋陰降火，天冬養(yǎng)陰清熱，玄參、制香附=＞夏枯草，醋柴胡=＞夏枯草相關(guān)聯(lián)，這幾種藥物活血化淤、滋陰降火，互為佐助，體現(xiàn)了中醫(yī)治療癭病以理氣化痰、消癭散結(jié)為基本治則［16］。

Table 1 Mining results of frequent itemsets表1 頻繁項(xiàng)集挖掘結(jié)果

2.5 關(guān)聯(lián)規(guī)則算法比較

對(duì)挖掘結(jié)果正確性的討論結(jié)束后，進(jìn)一步對(duì)算法效率進(jìn)行分析。為了直觀地對(duì)改進(jìn)算法在中醫(yī)藥數(shù)據(jù)上的挖掘性能進(jìn)行對(duì)比，采用控制變量法分別在設(shè)置不同的最小支持度和不同最小置信度的情況下，對(duì)算法運(yùn)行時(shí)間進(jìn)行可視化展示，實(shí)現(xiàn)對(duì)改進(jìn)的FP-growth 算法，以及基于事務(wù)壓縮技術(shù)和散列技術(shù)兩種技術(shù)改進(jìn)的Apriori 算法進(jìn)行運(yùn)行時(shí)間比較。

取不同的最小支持度對(duì)中醫(yī)藥數(shù)據(jù)進(jìn)行挖掘，結(jié)果如圖3 所示。針對(duì)中醫(yī)藥數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，兩種改進(jìn)的Apriori 算法與經(jīng)典的Apriori 相比，算法優(yōu)化效果不明顯，其中基于事物壓縮技術(shù)的Apriori算法效率稍高。

Table 2 Association rules mining results表2 關(guān)聯(lián)規(guī)則挖掘結(jié)果

Fig.3 Comparison of execution time between Apriori algorithm and improved Apriori algorithm圖3 Apriori算法與Apriori改進(jìn)算法執(zhí)行時(shí)間比較

同樣，對(duì)改進(jìn)的FP-growth 算法與傳統(tǒng)的FP-growth 算法進(jìn)行運(yùn)行時(shí)間對(duì)比，如圖4 所示?？梢钥闯?，改進(jìn)的FPgrowth 算法效率相比傳統(tǒng)的FP-growth 算法有明顯提升，隨著最小支持度的逐漸減小，改進(jìn)的FP-growth 算法運(yùn)行時(shí)間與FP-growth 算法以及上文改進(jìn)Apriori 算法中效率更優(yōu)的基于事物壓縮技術(shù)的Apriori 算法的運(yùn)行時(shí)間相差越來越大，而在支持度閾值大于0.12 時(shí)，候選頻繁項(xiàng)集較少，運(yùn)行時(shí)間差距較小，趨向一致。

各算法取不同的最小置信度，相同最小支持度時(shí)同樣對(duì)中醫(yī)藥數(shù)據(jù)進(jìn)行挖掘，結(jié)果如圖5 所示，相同條件下改進(jìn)的FP-growth 運(yùn)行時(shí)間最短，優(yōu)于本文其他算法。

2.6 實(shí)驗(yàn)結(jié)論

Fig.4 Comparison of execution time of five algorithms圖4 FP-growth改進(jìn)算法與傳統(tǒng)算法執(zhí)行時(shí)間比較

Fig.5 Comparison of execution time of five algorithms圖5 5種算法執(zhí)行時(shí)間比較

改進(jìn)的FP-growth 算法針對(duì)事務(wù)項(xiàng)重復(fù)和事務(wù)項(xiàng)較多的中醫(yī)藥臨床方劑數(shù)據(jù)集，減少了傳統(tǒng)FP-growth 首次遍歷數(shù)據(jù)庫生成的頻繁項(xiàng)樹數(shù)量，在傳統(tǒng)FP-growth 算法的首次遍歷中醫(yī)臨床方劑數(shù)據(jù)集之前增加一次遍歷，統(tǒng)計(jì)每一個(gè)方劑事務(wù)出現(xiàn)在事務(wù)集中的頻次，壓縮生成新的數(shù)據(jù)集，再進(jìn)行傳統(tǒng)FP-growth 后續(xù)挖掘。實(shí)驗(yàn)結(jié)果表明，控制變量不變的情況下，改進(jìn)的FP-growth 算法在運(yùn)行時(shí)間上最短，針對(duì)傳統(tǒng)的FP-growth 以及改進(jìn)的Apriori 算法在中醫(yī)藥數(shù)據(jù)挖掘中的應(yīng)用，改進(jìn)的FP-growth 算法效率有了一定提升，優(yōu)于本文其他對(duì)比算法。在挖掘結(jié)果相同的情況下，針對(duì)名老中醫(yī)臨床治療癭病的用藥規(guī)律研究，中醫(yī)藥數(shù)據(jù)挖掘研究者可更快地得到數(shù)據(jù)挖掘結(jié)果，能夠更好地輔助中醫(yī)臨床診治癭病患者，并且，結(jié)合數(shù)據(jù)挖掘結(jié)果，中醫(yī)也能夠更快地進(jìn)行中醫(yī)用藥優(yōu)化。

3 結(jié)語

本文采用兩種改進(jìn)的關(guān)聯(lián)規(guī)則算法對(duì)中醫(yī)治療癭病用藥進(jìn)行規(guī)律挖掘，實(shí)驗(yàn)中，改進(jìn)的FP-growth 算法與Apriori算法所挖掘的頻繁項(xiàng)集基本相同，所得到的關(guān)聯(lián)規(guī)則一致，均體現(xiàn)了中醫(yī)治療癭病理氣化痰，消癭散結(jié)的基本治則。通過實(shí)驗(yàn)結(jié)果比較改進(jìn)的關(guān)聯(lián)規(guī)則算法性能，研究表明，改進(jìn)的Apriori 算法在進(jìn)行中醫(yī)藥數(shù)據(jù)挖掘時(shí)，算法效果差別不大，而改進(jìn)的FP-growth 算法優(yōu)于傳統(tǒng)的FPgrowth 算法，相比改進(jìn)的Apriori 算法更好地提高了中醫(yī)藥數(shù)據(jù)挖掘效率，運(yùn)行時(shí)間遠(yuǎn)少于經(jīng)典Apriori 算法和改進(jìn)的Apriori 算法。本文基于改進(jìn)的關(guān)聯(lián)規(guī)則算法對(duì)中醫(yī)治療癭病進(jìn)行用藥規(guī)律挖掘，通過研究中醫(yī)臨床診治癭病的用藥規(guī)律，探索更加高效的數(shù)據(jù)挖掘方式，挖掘結(jié)果對(duì)于后續(xù)中醫(yī)臨床診治癭病患者具有重要指導(dǎo)和參考意義［18］。同時(shí)，研究中也存在一些問題，比如未增加其他變量對(duì)算法效率進(jìn)行分析。未來將繼續(xù)探索其他關(guān)聯(lián)規(guī)則算法在不同中醫(yī)藥數(shù)據(jù)上的效率表現(xiàn)，針對(duì)不同中醫(yī)藥數(shù)據(jù)集特點(diǎn)尋求最高效的挖掘算法。