基于改進關聯規則算法的中醫治療癭病用藥規律挖掘

楊文敏，佘侃侃，葉 丹

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

0 引言

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

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

1 相關算法

1.1 關聯規則基本概念

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

其中，count（A∪B）表示A 和B 同時出現的事務個數，TotalCount表示事務集中事務的個數。

其中，count（A）表示出現A 的事務個數。

1.2 Apriori算法

Apriori 算法是一種經典算法，用于挖掘數據集中頻繁項集和規則。本質上，Apriori 算法由兩部分組成：找頻繁項集和產生關聯規則，

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

（2）依據置信度產生關聯規則。掃描所有頻繁項集，輸出滿足最小置信度的關聯規則。

Apriori算法流程如圖1所示。

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

Apriori 算法在多次掃描數據庫時會產生大量候選項集，算法效率低、復雜度高［17］。

1.3 Apriori改進算法

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

1.4 FP-growth算法

FP-Growth［19］算法基于Apriori 原理，通過事務集D 存儲到FP-tree（Frequent Pattern tree）頻繁項樹，進而挖掘頻繁項和關聯規則。算法流程主要包括構建頻繁項樹和從頻繁項樹中挖掘頻繁項集兩個步驟［20］：

（1）構建FP 樹。具體過程如下：①初始化FP-tree 創建根節點T=null；②根據頭指針表，從FP-tree 的根結點開始更新FP-tree：如果當前事務項的第一個元素項存在于FP-tree 中，則更新這個子節點的計數值，否則創建新的子節點，依次對當前事務項的其他數據集進行同樣操作［21］；③依次將所有事務項的數據項插入到FP-tree 中。

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

1.5 FP-growth算法改進

FP-growth 算法利用FP-tree 存儲關于頻繁項集的壓縮信息，相較于Apriori 算法，在挖掘頻繁項集時，只對事務數據庫掃描兩次，極大提高了數據頻繁項集的挖掘速度。但在構建FP-tree 樹時，重復事物項也會構建重復tree，導致關聯規則數據挖掘效率降低。

1.5.1 散列技術

散列技術通過散列函數將要檢索的項與索引（散列、散列值）關聯起來［14］，將數據壓縮成摘要，使得數據量變小，將數據的格式固定下來，形成一種便于檢索的數據保存格式，生成一種便于搜索的數據結構［15］。

1.5.2 改進算法主要思想

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

算法1FP-growth改進算法

1.5.3 改進算法主要流程

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

Fig.2 Flow of improved FP-growth algorithm圖2 改進FP-growth算法流程

2 數據挖掘實驗及結果分析

本文通過比較改進的關聯規則算法對名老中醫臨床診治癭病的藥物組合進行關聯規則分析，并針對算法性能給出對應的結果比較。實驗結果包括關聯規則結果和算法性能比較兩部分。

2.1 原數據

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

2.2 數據預處理

本文數據來源于名老中醫臨床診治癭病的方劑數據，選取數據中的方劑數據，對方劑數據中的標準化方藥進行預處理操作，包括對方劑中藥物缺失的數據進行刪除，去除藥物劑量，并結合《中醫方劑大辭典》進一步對藥名進行規范，整理得到296 條中醫藥治療癭病的方劑數據。以每一方劑為一事務，每個方劑中每一藥物為一項整理得到中醫藥數據事務集。

2.3 實驗過程

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

2.4 癭病用藥規律數據挖掘結果

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

Table 1 Mining results of frequent itemsets表1 頻繁項集挖掘結果

2.5 關聯規則算法比較

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

取不同的最小支持度對中醫藥數據進行挖掘，結果如圖3 所示。針對中醫藥數據進行關聯規則挖掘時，兩種改進的Apriori 算法與經典的Apriori 相比，算法優化效果不明顯，其中基于事物壓縮技術的Apriori算法效率稍高。

Table 2 Association rules mining results表2 關聯規則挖掘結果

Fig.3 Comparison of execution time between Apriori algorithm and improved Apriori algorithm圖3 Apriori算法與Apriori改進算法執行時間比較

同樣，對改進的FP-growth 算法與傳統的FP-growth 算法進行運行時間對比，如圖4 所示。可以看出，改進的FPgrowth 算法效率相比傳統的FP-growth 算法有明顯提升，隨著最小支持度的逐漸減小，改進的FP-growth 算法運行時間與FP-growth 算法以及上文改進Apriori 算法中效率更優的基于事物壓縮技術的Apriori 算法的運行時間相差越來越大，而在支持度閾值大于0.12 時，候選頻繁項集較少，運行時間差距較小，趨向一致。

各算法取不同的最小置信度，相同最小支持度時同樣對中醫藥數據進行挖掘，結果如圖5 所示，相同條件下改進的FP-growth 運行時間最短，優于本文其他算法。

2.6 實驗結論

Fig.4 Comparison of execution time of five algorithms圖4 FP-growth改進算法與傳統算法執行時間比較

Fig.5 Comparison of execution time of five algorithms圖5 5種算法執行時間比較

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

3 結語

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