基于Apriori改進(jìn)算法的名老中醫(yī)治療糖尿病用藥規(guī)律研究

萬安慶+鮑劍洋+胡孔法

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

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法；ADPM算法；糖尿病；用藥規(guī)律

DOI：10.3969/j.issn.1005-5304.2017.12.024

中圖分類號(hào)：R2-05；R259.871 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

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

采用數(shù)據(jù)挖掘手段能發(fā)現(xiàn)隱藏在中醫(yī)藥數(shù)據(jù)中的規(guī)律。其中關(guān)聯(lián)規(guī)則分析在中醫(yī)藥數(shù)據(jù)挖掘中有著

基金項(xiàng)目：國(guó)家自然科學(xué)基金（81674099、81503499）；江蘇省“青藍(lán)工程”資助項(xiàng)目（2016年）

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

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

1 基本概念

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

垂直數(shù)據(jù)存儲(chǔ)的Apriori算法采用深度優(yōu)先正向搜索策略，因此無法充分利用Apriori先驗(yàn)性質(zhì)對(duì)候選集進(jìn)行剪枝。此外，對(duì)2個(gè)頻繁k項(xiàng)集的前綴進(jìn)行比對(duì)耗費(fèi)大量的時(shí)間，尤其在不能生成新的頻繁項(xiàng)集的情況下。而隨著迭代的加深，頻繁項(xiàng)集的增長(zhǎng)，這種前綴比對(duì)更加耗時(shí)，為此本研究提出了改進(jìn)后的ADPM算法。

定義1：設(shè)t（PX）為項(xiàng)集PX的TidSet（PX包含的事務(wù)ID集合），d（PX）為項(xiàng)集P和項(xiàng)集X的差集，d（PX）表示存在于t（P）中但不存在于t（PX）的事務(wù)ID集合，由集合的性質(zhì)可以得到d（PX）=

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

由定義可知，ADPM算法中使用將待挖掘項(xiàng)集轉(zhuǎn)換成其差集的方式，這樣對(duì)于部分事務(wù)數(shù)據(jù)庫(kù)，通過轉(zhuǎn)換成差集的方式可較大程度減小參與并運(yùn)算集合的大小。定義的性質(zhì)中s（PXY）=s（PX）-

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

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

2 算法描述

2.1 算法形式

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

①定義數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)垂直轉(zhuǎn)換的事務(wù)數(shù)據(jù)。

TYPEDEFSTRUCT _ADPM_DATA{ //存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)

setfreq_patt //頻繁項(xiàng)集

intf_count = 0 //支持度計(jì)數(shù)

settrans_sets //項(xiàng)集所在事務(wù)

}Adpm_Data， *pAdpm_Data

vectordiff_data_sets //一項(xiàng)集存儲(chǔ)

②輸入支持度support，輸入事務(wù)數(shù)據(jù)庫(kù)DataSource。

Iuput：support

Iuput：DataSource

③掃描事務(wù)數(shù)據(jù)集讀取事務(wù)數(shù)據(jù)并將事務(wù)數(shù)據(jù)庫(kù)序列化。

④將數(shù)據(jù)存儲(chǔ)方式轉(zhuǎn)換成集合的差集形式存儲(chǔ)，生成一項(xiàng)頻繁項(xiàng)集。

FOR item IN DataSource

convert_to_diff_item（item）

IF diff_item_support> support

diff_data_sets.push（diff_item）

END IF

END FOR

⑤反復(fù)迭代直至計(jì)算出所有滿足支持度的頻繁項(xiàng)集。

DO FOR itemA IN diff_data_sets

FOR itemB IN diff_data_sets

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

//滿足生成高項(xiàng)集的條件

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 //當(dāng)ItemA中元素個(gè)數(shù)<2時(shí)無法再生成高次頻繁項(xiàng)集

2.2 挖掘過程

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

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

3 算法應(yīng)用

名老中醫(yī)治療糖尿病方案是將中醫(yī)藥學(xué)基本理論、前賢醫(yī)家經(jīng)驗(yàn)與當(dāng)今臨床實(shí)踐結(jié)合，解決臨床診斷問題的典范，代表當(dāng)前中醫(yī)學(xué)術(shù)和臨床技能的最高水平[8]。通過數(shù)據(jù)挖掘手段，發(fā)現(xiàn)其中的用藥規(guī)律，對(duì)教學(xué)和臨床用藥有極大的指導(dǎo)意義和參考價(jià)值。

本研究采用使用C++語言結(jié)合R數(shù)據(jù)挖掘平臺(tái)開發(fā)ADPM算法，對(duì)名老中醫(yī)治療糖尿病數(shù)據(jù)挖掘分析。軟件環(huán)境為：Window2008、Codeblocks、C++11，硬件環(huán)境為：2 GHz 4核CPU、4G內(nèi)存。

3.1 數(shù)據(jù)來源

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

3.2 數(shù)據(jù)處理

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

3.3 算法對(duì)比

通過對(duì)名老中醫(yī)治療糖尿病方劑數(shù)據(jù)預(yù)處理得到有效方劑402條，原始數(shù)據(jù)相對(duì)較少，觀察挖掘效率不明顯。為直觀觀察改進(jìn)算法的挖掘效率，將原始數(shù)據(jù)簡(jiǎn)單擴(kuò)大250倍，得到算法效率測(cè)試數(shù)據(jù)庫(kù)，其中共有待挖掘條目100 500條，項(xiàng)目數(shù)309項(xiàng)，項(xiàng)集平均長(zhǎng)度為12。對(duì)比ADPM算法和垂直數(shù)據(jù)存儲(chǔ)的Apriori算法，運(yùn)行耗時(shí)見圖4。支持度較大時(shí)，ADPM算法效率有少量提升；支持度較小時(shí)，ADPM算法效率提升明顯。

3.4 挖掘結(jié)果

將處理得到的數(shù)據(jù)導(dǎo)入數(shù)據(jù)庫(kù)。使用ADPM算法進(jìn)行挖掘分析。得到高頻藥物（支持度>15%）24味（見表3），2味藥高頻藥物組合15組（見表4），無3項(xiàng)及以上高頻藥物組合。

設(shè)置支持度>5%，置信度>90%，得到藥物間關(guān)聯(lián)關(guān)系，見表5。不設(shè)置置信度，根據(jù)對(duì)支持度>5%的藥物關(guān)聯(lián)關(guān)系繪制藥物依賴關(guān)系網(wǎng)圖，見圖5，連線越粗表示關(guān)聯(lián)越緊密。

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

4 結(jié)語

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

參考文獻(xiàn)：

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

[2] 仝小林.糖尿病中醫(yī)認(rèn)識(shí)及研究進(jìn)展評(píng)述[J].北京中醫(yī)藥，2016， 36（6）：509-512.

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

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

[5] 宋京美，吳嘉瑞，姜迪.基于數(shù)據(jù)挖掘的國(guó)家級(jí)名老中醫(yī)治療腫瘤用藥規(guī)律研究[J].中國(guó)中醫(yī)藥信息雜志，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] 章志剛.云計(jì)算環(huán)境下頻繁項(xiàng)目集挖掘算法研究[D].南京：南京師范大學(xué)，2015.

[8] 徐蘊(yùn)，魏琦，湯大朋，等.2006-2015年中國(guó)期刊全文數(shù)據(jù)庫(kù)中醫(yī)基礎(chǔ)理論研究文獻(xiàn)計(jì)量分析[J].中醫(yī)雜志，2017，58（5）：418-422.

[9] 徐江燕，毋瑩玲，楊建宇.國(guó)家級(jí)名老中醫(yī)糖尿病驗(yàn)案良方[M].鄭州：中原農(nóng)民出版社，2013.

[10] 鐘贛生.中藥學(xué)[M].北京：中國(guó)中醫(yī)藥出版社，2012.

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

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