融合Apriori優(yōu)化算法與Relim算法的抑郁癥用藥規(guī)律挖掘

王慧敏　龔慶悅　胡孔法　邵榮強　陳燕

摘 要：為明確中醫(yī)治療抑郁癥用藥規(guī)律，融合Apriori優(yōu)化算法與Relim算法，采用數(shù)據(jù)挖掘技術進行分析。針對傳統(tǒng)Apriori算法頻繁掃描數(shù)據(jù)庫從而生成大量候選項集的缺點，改變其原有剪枝方式以減少掃描次數(shù)。將改進后的Apriori算法與無需產(chǎn)生候選項集的Relim算法就中醫(yī)治療抑郁癥的方劑數(shù)據(jù)進行關聯(lián)規(guī)則分析，并繪制兩個算法時間效率圖。結果發(fā)現(xiàn)，兩種算法在挖掘藥物頻繁項集與關聯(lián)規(guī)則的結果基本相同，通過分析發(fā)現(xiàn)，中醫(yī)常以疏肝、理氣、補腎、滋陰等藥物為主治療抑郁癥。改進后的Apriori算法可降低數(shù)據(jù)庫掃描次數(shù)，較傳統(tǒng)Apriori算法運行效率有所提高，Relim算法在空間利用率和時間執(zhí)行率上均略優(yōu)于改進后的Apriori算法。兩種算法挖掘結果體現(xiàn)出中醫(yī)治療抑郁癥注重疏肝理氣、補腎滋陰、調(diào)理氣血等特點?；陉P聯(lián)規(guī)則的方法可作為中醫(yī)用藥規(guī)律分析的重要工具。

關鍵詞：關聯(lián)規(guī)則;Apriori優(yōu)化算法;Relim算法;抑郁癥

DOI：10. 11907/rjdk. 192722

中圖分類號：TP391 ? 文獻標識碼：A??????????????? 文章編號：1672-7800（2020）003-0190-04

Combining Improved Apriori Algorithm and Relim Algorithm to

Mine Medication Rules for Depression

WANG Hui-min，GONG Qing-yue，HU Kong-fa，SHAO Rong-qiang，CHEN Yan

（School of Artificial Intelligence and Information Technology in Nanjing University of Chinese Medicine， Nanjing 210023， China）

Abstract： Improved Apriori Algorithm and Relim Algorithm were combined and? data mining technology was employed to identify the medication rules for depression. Aiming at the shortcomings of frequently scanning the database in the traditional Apriori algorithm to generate a large number of candidate itemsets， the original pruning method was changed to reduce the number of scans. The improved Apriori algorithm and Relim algorithm without generating candidate itemsets were used to mine the prescription data of traditional Chinese medicine for treating depression and compare the performance of the two algorithms by time efficiency graphs. The two algorithms are basically the same in mining frequent itemsets and association rules of drugs. Through analysis， it is found that traditional Chinese medicine often treats depression by treating drugs such as soothing liver， regulating qi， nourishing kidney and nourishing yin. The improved Apriori algorithm can reduce the number of database scans， which improves the operating efficiency of the traditional Apriori algorithm. The Relim algorithm is slightly better than the improved Apriori algorithm in terms of space utilization and time execution rate. The mining results of the two algorithms both reflect the characteristics of traditional Chinese medicine in the treatment of depression， such as dispelling liver and regulating qi， nourishing kidney-Yin， and regulating qi and blood. The method based on association rules can be an important tool for the analysis of traditional Chinese medicine.

Key Words： association rules; improved Apriori algorithm; relim algorithm; depression

0 引言

數(shù)據(jù)挖掘旨在發(fā)現(xiàn)數(shù)據(jù)庫信息潛在的交叉聯(lián)系與隱含知識。作為數(shù)據(jù)挖掘最重要的分支之一，關聯(lián)規(guī)則挖掘可識別給定數(shù)據(jù)庫中項目之間的關聯(lián)關系和頻繁模式[1]。

它由兩個子任務組成：先根據(jù)某個預定閾值發(fā)現(xiàn)頻繁項集，再生成滿足約束條件的關聯(lián)規(guī)則[2]。關聯(lián)規(guī)則不僅在商業(yè)數(shù)據(jù)分析中發(fā)揮重要作用，在其它領域也得到廣泛應用[3-5]。

在中醫(yī)藥領域，關聯(lián)規(guī)則可用于中醫(yī)組方規(guī)律挖掘、中醫(yī)文獻挖掘及臨床病歷挖掘等研究，以輔助中醫(yī)診斷，為臨床診治提供參考[6-8]。如趙平等[9]采用關聯(lián)規(guī)則挖掘中醫(yī)文獻中治療腎性貧血方劑的組方規(guī)律;周琳等[10]對海量的中醫(yī)臨床數(shù)據(jù)和古籍醫(yī)案進行挖掘以提取有用的疾病診治知識，提高醫(yī)療服務準確度和效率。大多數(shù)研究均采用經(jīng)典Apriori算法，雖然挖掘結果有一定借鑒意義，但其挖掘過程耗時費力。為提高挖掘工作效率，本文采用優(yōu)化Apriori算法與不需要產(chǎn)生候選項集的Relim算法對中醫(yī)治療抑郁癥用藥規(guī)律進行分析。

盡管經(jīng)典Apriori算法性能無法與最先進的深度優(yōu)先方法相提并論[11]，但Apriori算法始終被視為重要的關聯(lián)規(guī)則挖掘算法。因為其基本思想是找到所有頻繁項集，算法結構簡單且易于實現(xiàn)。而基于深度優(yōu)先的算法不僅需面對FP樹構造的復雜性，且存儲節(jié)點記錄會消耗內(nèi)存。為提高Apriori算法工作效率，許多研究者提出了改進方法。Bhandari等[12]提出將Apriori算法和FP-growth相結合以改善Apriori算法在重復掃描數(shù)據(jù)庫時的局限性;Yang等[13]提出通過添加事務權重的概念并生成事務布爾矩陣，以便掃描數(shù)據(jù)庫一次即可達到目標;Yang等[14]在網(wǎng)頁挖掘日志的問題上利用自動化的概念減少Apriori算法掃描數(shù)據(jù)庫的時間;而Borgelt[15]提出的Relim算法不需要生成候選項集即可挖掘頻繁項集，大幅提高了挖掘過效率，其速度并不慢于FP-growth算法，卻不需要建立復雜的頻繁樹結構，通過事務鏈表組的方式進行挖掘，可節(jié)省較大空間。

本文以避免重復掃描數(shù)據(jù)庫和減少候選項集的生成為目標，對經(jīng)典Apriori算法進行改進，以提高算法效率。優(yōu)化后的Apriori算法較原算法在運行速率上有較大提升，并將其與Relim算法在挖掘中醫(yī)治療抑郁癥的藥物組合上的表現(xiàn)作比較。

1 相關算法

1.1 Apriori算法

Apriori算法實質(zhì)是根據(jù)候選項集找頻繁項集[16]。算法利用頻繁項集性質(zhì)的先驗知識，對整個目標事務數(shù)據(jù)庫采用逐層搜索的迭代方法進行挖掘，以找出所有滿足條件的頻繁項集，最后通過對獲得的頻繁項集進行計算生成關聯(lián)規(guī)則[17]。其算法流程如下。

Step 1：掃描整個數(shù)據(jù)集D，并計算各數(shù)據(jù)項i在D中出現(xiàn)的頻次，根據(jù)公式（1）設置最小支持度并找出滿足最小支持度閾值的項集，即頻繁一項集[L1]。將剩下的不滿足最小支持度的數(shù)據(jù)項刪除。

Step 2：連接步，通過[Lk-1]與自身連接產(chǎn)生候選k項集的集合，記為[Ck]。

Step 3：剪枝步，掃描數(shù)據(jù)集，確定[Ck]中每個候選項集的頻次，其中不小于支持度閾值的候選項集即為頻繁項集，從而確定[Lk]。由此可知，[Ck]為[Lk]的超集，根據(jù)支持度度量反單調(diào)性可知，如果一個集合不是頻繁項集，則其所有超集都不是頻繁項集，可將這樣的非頻繁候選項集直接從[Ck]中剔除，即為對k項集的剪枝操作。

Step 4：重復迭代Step2和Step3操作，直至不再出現(xiàn)更高階的頻繁項集。

Step 5：對上述步驟產(chǎn)生的所有頻繁項集進行計算得出關聯(lián)規(guī)則，再根據(jù)滿足最小支持度閾值和最小置信度閾值條件的頻繁項集產(chǎn)生強關聯(lián)規(guī)則。置信度如式（2）所示。

Step 6：輸出所有滿足條件的頻繁項集和強關聯(lián)規(guī)則。

1.2 Apriori優(yōu)化算法

由于原始算法在剪枝這一步篩選候選頻繁k項集時，每判斷一次k-1維子集是否存在于[Lk-1]中，就需掃描一次頻繁k-1項集。序列越多，遍歷時間越長。該過程非常耗時且會產(chǎn)生大量候選頻繁項集，影響算法效率[18]。為避免重復掃描數(shù)據(jù)集帶來的不利影響，對算法進行優(yōu)化，在整個剪枝過程中只掃描一次[Lk-1]。對于[Lk-1]中任意元素A，判斷A是否為[Ck]中元素B的子集。如果是，則將B的計數(shù)加1。示例說明如表1所示。

根據(jù)表1所示，此時k=4，直接將[Lk-1]中的元素與[Ck]中的元素進行比較，只有[ Ck]中{[i1]，[i2]，[i3]，[i4]}的計數(shù)為4，則將它記為頻繁候選項集，得到[C'k={i1，i2，i3，i4}]。而原算法需先得出[Ck]中各元素項數(shù)為k-1項的子集，如要判斷元素{[i1]，[i2]，[i3]，[i4]}，要先得到它的子集{[i1]，[i2]，[i3]}，{[i2]，[i3]，[i4]}，{[i1]，[i3]，[i4]}，{[i1]，[i2]，[i4]}，然后判斷這些子集是否均為[Lk-1]中的元素，如果是則保留，否則刪除，計算復雜度明顯高于優(yōu)化后的算法。

1.3 Relim算法

受FP-growth算法的啟發(fā)，Relim算法基本思想與其相似，采用遞歸消除的方法，在不產(chǎn)生候選項集的情況下對頻繁項集進行挖掘[19]。但不同的是，Relim算法無需構建頻繁項集樹，而是將數(shù)據(jù)分到單個鏈表中，由組成的事務鏈表組進行頻繁項集挖掘。其算法流程如下所示。

Step 1：掃描整個數(shù)據(jù)集，計算每個數(shù)據(jù)項頻次，并按照頻次大小遞增排列各項，得到項集I。

Step 2：再次掃描數(shù)據(jù)集，設置最小支持度閾值min_sup，將小于min_sup的數(shù)據(jù)項從各事務中刪除，并將事務中的數(shù)據(jù)項按其頻次進行遞增排序。

Step 3：為新事務列表中的所有數(shù)據(jù)項創(chuàng)建一個單向數(shù)據(jù)鏈表，其中每個項均將得到一個支持度計數(shù)器和一個指針。計數(shù)器的值描述為以該項為首項的事務總數(shù)，指針則用來保存相關事務的關聯(lián)信息，以此組成事務鏈表。再將所有事務鏈表按I的順序得到一個事務鏈表組。

Step 4：先從以頻次最小的項為首的事務鏈表開始掃描，輸出該鏈表中支持度大于min_sup的項集。掃描完成后將該鏈表計數(shù)器值歸為0，再刪除該鏈表。

Step 5：構造一個用于保存除原首項外，以后繼項為新首項的事務關聯(lián)信息數(shù)據(jù)鏈表組，其結構與Step3中的事務鏈表組相似，將其稱為原首項前綴事務鏈表組。

Step 6：將前綴事務鏈表組與相應的被刪除的事務鏈表組合并組成一個新的事務鏈表組。

Step 7：根據(jù)Step4—Step6所述，遞歸地對新事務鏈表組中的第2個事務鏈表進行挖掘。

Step 8：直至挖到最后一個事務鏈表，指針指向空數(shù)組時停止挖掘，并輸出頻繁項集。

2 抑郁癥用藥規(guī)律挖掘

本文通過使用改進的Apriori算法與Relim算法在中醫(yī)治療抑郁癥藥物組合方面進行分析，并比較兩種算法性能。研究結果可分為中藥關聯(lián)規(guī)則挖掘結果與算法比較結果兩方面，整個實驗過程使用Python編程實現(xiàn)。

2.1 數(shù)據(jù)預處理

本文中醫(yī)治療抑郁癥方劑數(shù)據(jù)來源于《中醫(yī)方劑大辭典》[20]，通過以“肝氣郁結”、“憂思抑郁”、“思慮過多”、“情緒不安”、“氣機郁滯”等為檢索詞，篩選出237首有關中醫(yī)治療抑郁癥方劑。對該數(shù)據(jù)進行預處理，刪除所選方劑中沒有明確藥物組成和藥物主治功能的方劑數(shù)據(jù)，并將同一種藥物的不同名稱統(tǒng)一為一個名稱，修改不規(guī)范的藥名。如將“苡仁”、“薏苡”統(tǒng)一為“薏苡仁”，“杭白芍”、“炒白芍”統(tǒng)一為“白芍”等。最終將數(shù)據(jù)整理成符合條件的方劑共234首，中藥共354味。

2.2 關聯(lián)規(guī)則挖掘結果

由上述算法流程可知，改進Apriori算法與Relim算法挖掘方式不同，需分別建立適合其挖掘的數(shù)據(jù)庫。設置支持度閾值為0.07，置信度閾值為0.6，經(jīng)兩種算法挖掘的頻繁項集結果見表2、表3，生成的關聯(lián)規(guī)則結果見表4。

由表2—表4可看出，兩種算法挖掘出的藥物頻繁項集和關聯(lián)規(guī)則基本相同，相互印證了算法結果可靠性，均體現(xiàn)了中醫(yī)在治療抑郁癥上的用藥規(guī)律。如常用藥柴胡、川芎、木香、陳皮等可以調(diào)理氣血，改善抑郁癥患者整體“閉塞”狀態(tài);頻繁藥人參與白術均是重要的補氣藥物，兩藥相配可培元固本，調(diào)補患者因長期抑郁狀態(tài)帶來的身體機能損耗，增強體力。

2.3 算法對比討論

從算法結構來看，Apriori算法通過產(chǎn)生候選項集進而確定頻繁項集，改進的Apriori算法并沒有改變原算法結構。而Relim算法無需建立頻繁項集樹，不需要產(chǎn)生候選項集，是通過建立事務鏈表組產(chǎn)生頻繁項集的。

從空間利用率來看，Apriori算法由于會產(chǎn)生候選項集，因而要額外占用部分內(nèi)存，而Relim算法在挖掘過程中采用建立事務鏈表組的方法，每挖掘完一個事務鏈表就將該鏈表刪除，立刻釋放內(nèi)存。所以，Relim算法空間利用率優(yōu)于Apriori算法。

從時間效率來看，如圖1所示，最小支持度越小，各個算法花費時間越多且Apriori原算法效率最差。在支持度閾值設置較低情況下，3種算法均會產(chǎn)生大量頻繁項集，由于Apriori原算法需重復多次掃描數(shù)據(jù)庫，而改進后的Apriori算法只需掃描一次數(shù)據(jù)庫，運行時間比原始算法明顯縮短。Relim算法不需要多次掃描數(shù)據(jù)庫，也無需產(chǎn)生候選項集，通過事務鏈表組活動，運行速率最快。當支持度閾值增大，能產(chǎn)生的頻繁項集減少，各算法效率逐漸接近。

3 結語

本文采用兩種不同的關聯(lián)規(guī)則算法對中醫(yī)治療抑郁癥用藥的組方規(guī)律進行挖掘，并比較算法性能。由上述實驗可知，兩種算法挖掘結果可相互印證，所挖掘的頻繁項集和產(chǎn)生的關聯(lián)規(guī)則基本相同，均體現(xiàn)出中醫(yī)治療抑郁癥注重疏肝理氣、補腎滋陰、調(diào)理氣血等特點。從算法性能上來看，改進的Apriori算法大幅提高了原算法運行速率，節(jié)省了大量運行時間，而Relim算法在空間利用率與時間執(zhí)行率上均略優(yōu)于改進后的Apriori算法。下一步可考慮引入更多算法比較研究中醫(yī)在其它病癥上的用藥規(guī)律，除了方劑藥物特性外，還可從劑量、炮制、藥物性味歸經(jīng)等方面入手，拓寬研究思路。

參考文獻：

[1]SHARMA S ， BHATIA S. Analysis of association rule in data mining[C]. The Second International Conference，2016：1-4.

[2]YUAN X. An improved Apriori algorithm for mining association rules[C]. Guilin：International Conference On computer Science and Artificial Intelligence，2016.

[3]YAO L， XU Z， ZHOU X， et al. Data science and digital business：synergies between association rules and collaborative filtering in recommender system： an application to auto industry[M]. Berlin：Springer，2019.

[4]徐哲煒，鄭成航，張涌新，等. 基于改進關聯(lián)規(guī)則算法的燃煤電廠脫硫系統(tǒng)工況參數(shù)優(yōu)化[J]. 中國電機工程學報，2017（15）：138-144，311.

[5]HUH J H，KIM H B，KIM J. A method of modeling of basic big data analysis for Korean medical tourism： a machine learning approach using Apriori algorithm[C]. Singapore：? International Conference on Information Science & Applications，2017.

[6]王倩，金衛(wèi)，生慧. 兩種關聯(lián)規(guī)則算法在中醫(yī)藥治療方面的應用及比較[J]. 吉林中醫(yī)藥， 2015（1）：14-17.

[7]蘇克雷，葉娟，張業(yè)清，等. 基于數(shù)據(jù)挖掘的江浙滬名老中醫(yī)膏方醫(yī)案關聯(lián)解析[J]. 中華中醫(yī)藥雜志， 2019（6）：2721-2727.

[8]張奇，李濤，許勇鋼，等. 基于關聯(lián)規(guī)則挖掘治療多發(fā)性硬化所用中藥對患者T細胞亞群的影響[J]. 中國中西醫(yī)結合雜志，2016（4）：425-429.

[9]趙平，張法榮. 腎性貧血方劑組方規(guī)律中醫(yī)文獻分析[J]. 山東中醫(yī)藥大學學報，2019（2）：25-29.

[10]周琳，劉樹春. 關聯(lián)規(guī)則在中醫(yī)臨床信息分析中的應用[J]. 中國中醫(yī)藥圖書情報雜志， 2014（4）：13-15，21.

[11]BORGELT C. Frequent item set mining[J]. Wiley Interdisciplinary Reviews：Data Mining and Knowledge Discovery，2012，2（6）：437-456.

[12]BHANDARI A，GUPTA A，DAS D. Improvised Apriori algorithm using frequent pattern tree for real time applications in data mining[J]. Procedia Computer Science，2015，46：644-651.

[13]YANG Q，F(xiàn)U Q， WANG C， et al. A matrix-based Apriori algorithm improvement[C].Guangzhou：2018 IEEE Third International Conference on Data Science in Cyberspace， 2018.

[14]YANG J，HUANG H，JIN X. Mining web access sequence with improved Apriori algorithm[C]. 2017 IEEE International Conference on Computational Science and Engineering （CSE） and IEEE International Conference on Embedded and Ubiquitous Computing （EUC）， 2017：780-784.

[15]BORGELT C. Keeping things simple： finding frequent item sets by recursive elimination[C]. International Workshop on Open Source Data Mining：Frequent Pattern Mining Implementations，2005：66-70.

[16]陳方健，張明新，楊昆. 一種具有跳躍式前進的 Apriori 算法[J]. 計算機應用與軟件，2015（3）：34-36.

[17]曾子賢，鞏青歌，張俊. 改進的關聯(lián)規(guī)則挖掘算法——MIFP-Apriori算法[J]. 科學技術與工程， 2019（16）：216-220.

[18]陳志飛，馮鈞. 一種基于Apriori算法的優(yōu)化挖掘算法[J]. 計算機與現(xiàn)代化， 2016（9）：1-5.

[19]VIJAYARANI S，SHARMILA S. Comparative analysis of association rule mining algorithms[C].Tamilnadu： International Conference on Inventive Computation Technologies，2016.

[20]彭懷仁. 中醫(yī)方劑大辭典[M]. 北京：人民衛(wèi)生出版社，1996.

[21]汪玉薇，解丹，李曉東， 等. 基于改進關聯(lián)規(guī)則算法的中醫(yī)處方規(guī)律挖掘研究[J]. 世界科學技術-中醫(yī)藥現(xiàn)代化，2019（3）：348-349.

（責任編輯：江 艷）

收稿日期：2019-12-20

基金項目：國家自然科學基金項目（81674099 ）;江蘇省中醫(yī)藥管理局項目（YB2017008）

作者簡介：王慧敏（1994-），女，南京中醫(yī)藥大學人工智能與信息技術學院碩士研究生，研究方向為中醫(yī)藥信息學;龔慶悅（1972-），女，博士，南京中醫(yī)藥大學人工智能與信息技術學院副教授，研究方向為中醫(yī)藥信息學。本文通訊作者：龔慶悅。