基于Apriori改進算法的名老中醫治療糖尿病用藥規律研究

萬安慶+鮑劍洋+胡孔法

摘要：目的 改進Apriori算法以獲得更高效的數據挖掘方法，分析名老中醫治療糖尿病病案用藥規律。方法 提出1種垂直Apriori數據存儲方法，采用用差集方法改進的ADPM挖掘算法，對《國家級名老中醫糖尿病驗案良方》用藥規律進行數據挖掘。結果 經篩選，納入處方402首，包含高頻藥物24味、高頻藥物組合15組、高依賴度藥物組合18組，以補虛藥、清熱藥、活血化瘀藥、利水滲濕藥為主。結論 基于Apriori改進的ADPM算法能運用于用藥規律分析，發現高頻藥物、組合及藥物依賴關系，且具有更高的效率。

關鍵詞：數據挖掘；關聯規則；Apriori算法；ADPM算法；糖尿病；用藥規律

DOI：10.3969/j.issn.1005-5304.2017.12.024

中圖分類號：R2-05；R259.871 文獻標識碼：A 文章編號：1005-5304（2017）12-0097-05

Study on Medication Regularity of Famous TCM Doctors for Diabetes Based on Improved Apriori Algorithm WAN An-qing， BAO Jian-yang， HU Kong-fa （Nanjing University of Chinese Medicine， Nanjing 210023， China）

Abstract： Objective To analyze the medication regularity of TCM famous doctors for diabetes by using improved Apriori algorithm to obtain more efficient data mining methods. Methods This article put forward Apriori vertical data storage， and improved ADPM obtained by difference set method was used to conduct data mining to find out the medication regularity in Guo Jia Ji Ming Lao Zhong Yi Tang Niao Bing Yan An Liang Fang. Results After screening， 402 prescriptions were included， involving 24 kinds of high-frequency medicine， 15 high-frequency medical combinations， and 18 highly-dependent medical combinations， which were mainly tonifying deficiency medicine， clearing heat medicine， blood-activating and stasis-resolving medicine， and damp-draining diuretic medicine. Conclusion ADPM algorithm can be applied in the analysis on medication regularity and find out high-frequency medicine， medical combinations and medical dependent relation， with high efficiency.

Key words： data mining； association rules； Apriori algorithm； ADPM algorithm； diabetes； medication regularity

糖尿病是一種常見病內分泌代謝疾病，嚴重影響患者的身心健康。中醫治療糖尿病歷史悠久，《素問》及《靈樞》均有“消渴”記載。隨著中醫科研不斷發展，中醫治療糖尿病相關研究從過去散在的、相對滯后的狀態逐漸發展為擁有系統化、規范化標準的模式，展現了中醫治療糖尿病的獨特優勢[1-3]。而研究當代名老中醫治療糖尿病驗案良方對治療該病臨床用藥具有重要參考價值和指導意義。

采用數據挖掘手段能發現隱藏在中醫藥數據中的規律。其中關聯規則分析在中醫藥數據挖掘中有著

基金項目：國家自然科學基金（81674099、81503499）；江蘇省“青藍工程”資助項目（2016年）

通訊作者：鮑劍洋，E-mail：bjy_163@163.com

廣泛的應用[4-5]。目前，關聯規則挖掘算法主要有Apriori和FP-Growth，Apriori通過候選集生成和情節的向下封閉檢測2個階段來挖掘頻繁項集，需要多次掃描數據庫，數據量大時效率降低。FP-Growth只需掃描2次數據庫，但是需多次迭代頻繁模式樹。2種算法均為水平數據存儲模式，而垂直數據存儲的頻繁模式挖掘算法在性能上要優于水平數據存儲模式[6-7]。為提高關聯規則算法效率，本研究針對傳統算法的不足，提出基于Apriori改進的ADPM（Apriori based Diabetes Prescription Mining Arithmetic）算法，該算法避免了多次掃描數據庫及多次迭代頻繁模式樹，利用垂直數據存儲的優勢，結合差集方法減小挖掘過程中候選集生成規模、加快迭代過程，提高頻繁模式挖掘效率。

1 基本概念

垂直數據存儲的Apriori算法將事務數據中的項作為鍵，每個項對應的事務編號作為值，生成新的事務數據庫，以加快頻繁集生成速度。其算法思想是由頻繁k項依次求并集，若2個頻繁k項集具有相同的k-1項前綴則這2個頻繁k項集可運算生成候選k+1項集。然后對候選集剪枝，滿足支持度即加入頻繁k+1項集，再計算候選k+2項集，剪枝生成頻繁k-2項集。如此迭代，直到求出所有的頻繁項集。endprint

垂直數據存儲的Apriori算法采用深度優先正向搜索策略，因此無法充分利用Apriori先驗性質對候選集進行剪枝。此外，對2個頻繁k項集的前綴進行比對耗費大量的時間，尤其在不能生成新的頻繁項集的情況下。而隨著迭代的加深，頻繁項集的增長，這種前綴比對更加耗時，為此本研究提出了改進后的ADPM算法。

定義1：設t（PX）為項集PX的TidSet（PX包含的事務ID集合），d（PX）為項集P和項集X的差集，d（PX）表示存在于t（P）中但不存在于t（PX）的事務ID集合，由集合的性質可以得到d（PX）=

t（P）-t（PX）=t（P）-t（X）。見圖1。

由定義可知，ADPM算法中使用將待挖掘項集轉換成其差集的方式，這樣對于部分事務數據庫，通過轉換成差集的方式可較大程度減小參與并運算集合的大小。定義的性質中s（PXY）=s（PX）-

|d（PXY）|=s（PY）-|d（PYX）|，表明在使用差集時，同一候選集的生成方式有多種，選擇PX和PY中較小的集合來計算s（PXY）可以進一步減小參與并運算的集合大小，提升算法效率。

此外，算法通過縮小生成高頻繁項集時迭代運算的循環規模，在循環過程中及時跳出，減少無意義并運算和無意義候選集生成數量來提升算法速度。垂直Apriori算法規定只有具有相同前綴的頻繁k項集才能生成候選k+1項集，在2個頻繁k項集并運算前需要驗證是否滿足該條件。ADPM算法中通過對前一步得到頻繁k-1項集按編碼排序，依次取出2個做并運算生成候選k項集，遇到首項不同即跳出，而無需將所有項集的前綴進行比對，從而縮小迭代運算的循環規模，提高算法效率。

2 算法描述

2.1 算法形式

ADPM算法核心過程偽代碼描述如下：

①定義數據結構存儲垂直轉換的事務數據。

TYPEDEFSTRUCT _ADPM_DATA{ //存儲數據結構

setfreq_patt //頻繁項集

intf_count = 0 //支持度計數

settrans_sets //項集所在事務

}Adpm_Data， *pAdpm_Data

vectordiff_data_sets //一項集存儲

②輸入支持度support，輸入事務數據庫DataSource。

Iuput：support

Iuput：DataSource

③掃描事務數據集讀取事務數據并將事務數據庫序列化。

④將數據存儲方式轉換成集合的差集形式存儲，生成一項頻繁項集。

FOR item IN DataSource

convert_to_diff_item（item）

IF diff_item_support> support

diff_data_sets.push（diff_item）

END IF

END FOR

⑤反復迭代直至計算出所有滿足支持度的頻繁項集。

DO FOR itemA IN diff_data_sets

FOR itemB IN diff_data_sets

IF itemA ！= itemB&&itemA（k-1）==itemB（k-1）

//滿足生成高項集的條件

result_set = itemA∪convert_to_diff_item（itemB） //生成候選集

IF result_set_support> support

PRINT result_set

END IF

END IF

END FOR

END FOR

WHILE ItemA_size>=2 //當ItemA中元素個數<2時無法再生成高次頻繁項集

2.2 挖掘過程

對比垂直Apriori算法和ADPM算法效率，設測試數據集表1為治療糖尿病方劑數據。對測試數據集進行頻繁模式挖掘，設置頻繁模式挖掘的支持度為50%，表1中數據庫中數據事務條數L_D=6，滿足支持度計數S_D≥6×50%=3的項集為頻繁項集。序列化后的數據分別表示黃芪（a）、山藥（b）、茯苓（c）、丹皮（d）、澤瀉（e）、熟地（f）、山茱萸（g）。將原始水平格式數據（見表1）垂直轉化成事務數據庫倒排表并進行頻繁一項集挖掘得到結果（見表2）。算法挖掘過程見圖2、圖3，紅叉表示剪枝。

對于測試數據集表1，對比圖2、圖3的運算過程可以發現，生成候選2項集時，垂直Apriori算法參與運算的集合規模共有21個元素，而ADPM算法只有9個元素；生成候選3項集時，垂直Apriori算法有18個，ADPM算法有10個；整個挖掘過程參與并運算的集合垂直Apriori算法為39個，ADPM算法為19個，數量大大減少。因此對于一些事務數據集，如這里的測試數據集表1，ADPM算法在生成候選集時能很大程度減小集合大小，加快候選集生成速度，提升算法效率。

3 算法應用

名老中醫治療糖尿病方案是將中醫藥學基本理論、前賢醫家經驗與當今臨床實踐結合，解決臨床診斷問題的典范，代表當前中醫學術和臨床技能的最高水平[8]。通過數據挖掘手段，發現其中的用藥規律，對教學和臨床用藥有極大的指導意義和參考價值。

本研究采用使用C++語言結合R數據挖掘平臺開發ADPM算法，對名老中醫治療糖尿病數據挖掘分析。軟件環境為：Window2008、Codeblocks、C++11，硬件環境為：2 GHz 4核CPU、4G內存。

3.1 數據來源

《國家級名老中醫糖尿病驗案良方》[9]中名老中醫治療糖尿病驗案，包括朱良春、周仲瑛、方和謙、鄧鐵濤等95位名家良方，選案豐富，處方精妙。

3.2 數據處理

按照全國高等中醫藥院校規劃教材（第九版）《中藥學》[10]進行數據預處理：①去除重復數據、清洗異常數據；②對方劑中的藥物別名進行規范，如“三七”“田七”“金不換”規范為“三七”；③標明產地的但無明顯功效差異的，如“寧夏枸杞”規范為“枸杞子”，“吉林人參”規范為“人參”，“東阿阿膠”規范為“阿膠”；④對有明顯功效差異不可相互替代的同種藥物不同炮制品，分別錄入，如“生甘草”“炙甘草”。通過數據預處理得到有效方劑402首，涉及藥物349味，總用藥頻次4711次。

3.3 算法對比

通過對名老中醫治療糖尿病方劑數據預處理得到有效方劑402條，原始數據相對較少，觀察挖掘效率不明顯。為直觀觀察改進算法的挖掘效率，將原始數據簡單擴大250倍，得到算法效率測試數據庫，其中共有待挖掘條目100 500條，項目數309項，項集平均長度為12。對比ADPM算法和垂直數據存儲的Apriori算法，運行耗時見圖4。支持度較大時，ADPM算法效率有少量提升；支持度較小時，ADPM算法效率提升明顯。

3.4 挖掘結果

將處理得到的數據導入數據庫。使用ADPM算法進行挖掘分析。得到高頻藥物（支持度>15%）24味（見表3），2味藥高頻藥物組合15組（見表4），無3項及以上高頻藥物組合。

設置支持度>5%，置信度>90%，得到藥物間關聯關系，見表5。不設置置信度，根據對支持度>5%的藥物關聯關系繪制藥物依賴關系網圖，見圖5，連線越粗表示關聯越緊密。

圖5表明，中醫藥治療糖尿病共涉及18類中藥，使用頻次最高的5類依次為補虛藥、清熱藥、活血化瘀藥、利水滲濕藥、收澀藥，共占78.44%，使用頻率排在每類首位的藥物分別為黃芪、生地、丹參、茯苓、山茱萸，可見名老中醫治療糖尿病主要是益氣養陰，兼以清熱活血、化瘀利水。

4 結語

中醫藥體系高度復雜，治病因時、因地、因人制宜，挖掘分析難度大。中醫病案數據中蘊含的知識對臨床用藥和教育教學有重要指導作用，為更有效地發現中醫藥治療糖尿病用藥方案中的規律，本研究基于Apriori提出了改進的ADPM算法，ADPM算法在挖掘頻繁模式時有更小的候選集和更小的迭代規模，效率更高。通過ADPM算法數據采集、預處理、頻繁項挖掘、關聯規則分析挖掘了名老中醫治療糖尿病用藥數據，并繪制了中醫藥治療糖尿病常用藥物關系網圖。隨著數據分析處理技術在中醫藥這一復雜體系中應用越來越廣，應改進傳統算法以更適應中醫藥數據特點。

參考文獻：

[1] 栗明，丁常宏，方芳.糖尿病中醫治療進展[J].中醫藥信息，2012，29（6）：112-115.

[2] 仝小林.糖尿病中醫認識及研究進展評述[J].北京中醫藥，2016， 36（6）：509-512.

[3] 牟新，莊愛文，馬國玲，等.237例臨床期糖尿病腎病患者中醫證候聚類分析[J].中華中醫藥學刊，2016，34（2）：332-335.

[4] 楊和亮，諶松霖，李金波.基于數據挖掘的針灸治療膝關節骨性關節炎取穴規律研究[J].中國中醫藥信息雜志，2017，24（1）：95-98.

[5] 宋京美，吳嘉瑞，姜迪.基于數據挖掘的國家級名老中醫治療腫瘤用藥規律研究[J].中國中醫藥信息雜志，2015，22（6）：50-53.

[6] ARINCY N， SITANGGANG I S. Association rules mining on forest fires data using FP-Growth and ECLAT algorithm[C]//2015 3rd International Conference on Adaptive and Intelligent Agroindustry， IEEE，2015：274-277.

[7] 章志剛.云計算環境下頻繁項目集挖掘算法研究[D].南京：南京師范大學，2015.

[8] 徐蘊，魏琦，湯大朋，等.2006-2015年中國期刊全文數據庫中醫基礎理論研究文獻計量分析[J].中醫雜志，2017，58（5）：418-422.

[9] 徐江燕，毋瑩玲，楊建宇.國家級名老中醫糖尿病驗案良方[M].鄭州：中原農民出版社，2013.

[10] 鐘贛生.中藥學[M].北京：中國中醫藥出版社，2012.

（收稿日期：2017-04-18）

（修回日期：2017-05-12；編輯：向宇雁）endprint