劉莉萍 李歡 何正宏

摘? 要：針對中藥“性-效”數(shù)據(jù)關聯(lián)度高、屬性稀疏的問題，提出一種使用垂直數(shù)據(jù)格式生成類關聯(lián)規(guī)則的關聯(lián)分類算法（ECBA）。該算法通過將數(shù)據(jù)轉換為垂直格式而避免了經(jīng)典關聯(lián)分類算法（CBA）生成大量候選規(guī)則集、頻繁遍歷數(shù)據(jù)庫、產(chǎn)生無意義分類規(guī)則等不足。實驗結果表明，相較于傳統(tǒng)算法CBA，改進算法ECBA在規(guī)則生成時間、規(guī)則有效性以及準確率方面均有明顯提升，更適用于中藥“性-效”數(shù)據(jù)分析。

關鍵詞：關聯(lián)分類；中藥藥性；中藥功效；垂直數(shù)據(jù)；ECBA

中圖分類號：TP39；TP301.6? 文獻標識碼：A? 文章編號：2096-4706（2023）18-0150-05

Improvement of Association Classification Algorithm and Its Application in “Performance-Efficacy” Analysis of Traditional Chinese Medicine

LIU Liping1， LI Huan2， HE Zhenghong1

（1.Network and Information Technology Center， Jiangxi University of Chinese Medicine， Nanchang? 330004， China;

2.School of Computer Science， Jiangxi University of Chinese Medicine， Nanchang? 330004， China）

Abstract： Aiming at the problem of high correlation and sparse attributes of traditional Chinese medicine “performance-efficacy” data， an Association Classification Algorithm （ECBA） for generating class association rules using vertical data format is proposed. This algorithm avoids the shortcomings of the classical association classification algorithm （CBA） in generating a large number of candidate rule sets， frequently traversing the database， and generating meaningless classification rules by converting the data into a vertical format. The experimental results show that compared to the traditional algorithm CBA， the improved algorithm ECBA has significantly improved in rule generation time， rule effectiveness， and accuracy， making it more suitable for analyzing the “performance effectiveness” data of traditional Chinese medicine.

Keywords： association classification; traditional Chinese medicine property; traditional Chinese medicine efficacy; vertical data; ECBA

0? 引? 言

中醫(yī)藥是我國的國粹，是我國優(yōu)秀傳統(tǒng)文化的瑰寶。中藥藥性理論是先輩們在長期的行醫(yī)實踐中提煉出來的中藥學理論，藥效是根據(jù)中醫(yī)藥理論對藥物治療作用的高度概括，這些都是中藥理論的重要組成部分[1]。中藥藥性和中藥藥效簡稱“性-效”，是一個不可分割的有機整體，這也體現(xiàn)出中醫(yī)把人看作一個整體的觀念，“藥性互參”“性效結合”[2]。正是如此，在利用數(shù)據(jù)挖掘技術對中醫(yī)藥數(shù)據(jù)進行分析時更應該把數(shù)據(jù)之間的屬性緊密地聯(lián)系起來，而不能獨立地分割開來。關聯(lián)分類算法是通過挖掘出數(shù)據(jù)屬性之間所有規(guī)則集[3]，再從中選出最優(yōu)的規(guī)則用于分類，但傳統(tǒng)關聯(lián)分類算法CBA不能很好地適應中藥性效數(shù)據(jù)的特點?；诖?，本文提出一種改進算法（Eclat Classification Based on Association Rule， ECBA）。采用垂直數(shù)據(jù)表示格式，不生成候選項集，不需要對數(shù)據(jù)進行數(shù)字化處理，且產(chǎn)生的分類規(guī)則均為有效規(guī)則，相比于經(jīng)典關聯(lián)分類算法（Classification Based on Association Rule， CBA）具有更高的效率。

1? 關聯(lián)分類算法改進分析

關聯(lián)規(guī)則技術挖掘數(shù)據(jù)之間的關聯(lián)性、相關性和其他有趣的聯(lián)系，但不進行預測。分類是通過找出數(shù)據(jù)屬性和類別之間某種特殊的關系而建立一種分類器，用于對未知數(shù)據(jù)進行類別預測。關聯(lián)規(guī)則與分類之間既有區(qū)別又有聯(lián)系，直至1998年，新加坡國立大學Liu教授首次提出將這兩種技術整合到一起，形成一種新的分類方法——關聯(lián)分類算法[4]。由于CBA算法在UCI（UC Irvine Machine Learning Repository）數(shù)據(jù)集上表現(xiàn)出非常高的準確率，優(yōu)于傳統(tǒng)分類算法（如C4.5、SVM、人工神經(jīng)網(wǎng)絡等），因此引起眾多研究者的密切關注。相繼有學者在CBA算法的基礎上提出了改進算法。1999年，Dong等人[5]提出了基于顯露模式的分類方法（Classification by Aggregating Emerging Patterns， CAEP）。顯露模式是指不同類別下項集支持度有明顯差異的那些項集，實驗表明CAEP算法在海量數(shù)據(jù)或高維數(shù)據(jù)中均取得比CBA算法和C4.5算法更高的準確率。2000年，Wang等人[6]結合關聯(lián)規(guī)則和決策樹的優(yōu)點提出了關聯(lián)決策樹ADT算法，該方法不再同時使用支持度和置信度來選擇分類規(guī)則，而是根據(jù)置信度高低來選擇分類規(guī)則，再通過準確率驅動構建決策樹。2001年，Li等人[7]基于多類關聯(lián)規(guī)則提出一種準確有效的CMAR算法（Classification based on Multiple Class-Association Rules），該算法通過FP-growth算法生成分類關聯(lián)規(guī)則，但不限制其生成規(guī)則的數(shù)量，在預測未知實例時，基于多個規(guī)則判定其所屬類別標簽。雖然這樣提高了分類準確率，但卻造成候選集數(shù)量過多，規(guī)則冗余的問題。Baralis等人提出一種懶（Lazy）分類規(guī)則剪枝方法，直接通過迭代的方法將產(chǎn)生錯誤分類的規(guī)則全部剪去，雖然提高了分類的準確率，但并不適用于大規(guī)模數(shù)據(jù)集。Hao等人[8]提出一種預測型關聯(lián)規(guī)則分類方法（Classification based on Predictive Association Rules， CPAR），該算法基于貪婪算法的思想直接從訓練數(shù)據(jù)中尋找關聯(lián)規(guī)則，通過信息增益的方法選擇最優(yōu)的規(guī)則進行分類，有效減少了資源空間的消耗，但其分類準確率與CMAR相差無幾。

2? 改進關聯(lián)分類算法ECBA

2.1? CBA算法簡介

關聯(lián)分類算法CBA主要分為兩個部分：關聯(lián)規(guī)則生成和構建分類器。關聯(lián)規(guī)則生成采用的是類似Apriori的算法，生成所有滿足最小支持度和最小置信度的類關聯(lián)規(guī)則項集。一個關聯(lián)規(guī)則項集就是形如的鍵值對，其中condset是項集的集合，一個項集即一個屬性及其對應的取值（attribute，integer-value），y是數(shù)據(jù)集的一個類標簽，表示類關聯(lián)規(guī)則condset→ y。表1給出一個簡單的數(shù)據(jù)集，表中的A和B表示數(shù)據(jù)的兩個屬性，C表示數(shù)據(jù)類別。那么類關聯(lián)規(guī)則（A = I1）∩（B = I3）→ y，表示當A = I1并且B = I3時該樣本屬于類別0。定義項集支持度計數(shù)condsetCount表示數(shù)據(jù)集中包含condset的樣本個數(shù)，規(guī)則（A = I1）∩（B = I3）→ y的項集支持度condsetCount = 3（屬性A = I1和屬性B = I3共同出現(xiàn)的次數(shù)）；其規(guī)則支持度計數(shù)rulesupCount = 2是數(shù)據(jù)集包含屬性A = I1和屬性B = I3以及類別為0的次數(shù)。由此可以定義類關聯(lián)規(guī)則的支持度support = rulesupCount / | D |×100%，置信度confidence = rulesupCount / condsupCount×100%。CBA算法的第一步就是從數(shù)據(jù)集中生成所有滿足最小支持度閾值和最小置信度閾值的類關聯(lián)規(guī)則（稱為CARs）。第二步是采用數(shù)據(jù)庫覆蓋的方法構建分類器。首先按照置信度、支持度的高低對CARs進行排序，如果遇到項集置信度、支持度相等的情況，則取先生成的規(guī)則。依次取CARs中的規(guī)則對數(shù)據(jù)集進行覆蓋，如果滿足則對數(shù)據(jù)進行標記，直至遍歷完整個數(shù)據(jù)集，然后把被覆蓋的數(shù)據(jù)從數(shù)據(jù)集中刪除，將剩下的數(shù)據(jù)組成新的數(shù)據(jù)集，再用下一條規(guī)則去覆蓋，如此循環(huán)往復，當不再遍歷數(shù)據(jù)庫時，則選擇一個默認的類別對數(shù)據(jù)進行歸類，默認類別的選擇原則一般是選擇出現(xiàn)頻率較高的類別。被選中的一系列規(guī)則構成了我們的分類器，可以用于對新數(shù)據(jù)進行預測。

2.2? ECBA算法設計

在生成類關聯(lián)規(guī)則時由于CBA算法采用的是Apriori算法的思想，因此也繼承了其缺點，需要不斷掃描數(shù)據(jù)庫，產(chǎn)生大量的候選項集，造成了極大的I/O負擔，影響算法的運行效率。CBA算法應用于中醫(yī)藥“性-效”數(shù)據(jù)時，由于該算法需要對數(shù)據(jù)進行數(shù)字化處理，對于中藥藥性的22個特征，有就記為1，沒有則記為0，但是中藥的屬性十分稀疏，會造成取0的值偏多，那么在產(chǎn)生分類規(guī)則時會產(chǎn)生一些沒有意義的規(guī)則，雖然提高了分類準確率，但卻沒有什么實際意義。Eclat算法采用的是垂直數(shù)據(jù)格式，通過求交運算產(chǎn)生頻繁項集，既能減少掃描數(shù)據(jù)庫的次數(shù)，又能避免產(chǎn)生沒有意義的分類規(guī)則。ECBA算法就是基于Eclat算法的思想對其進行改進的基礎上而產(chǎn)生的，在保留原始數(shù)據(jù)特征的情況下，提高算法的運行效率。

如表2所示為水平數(shù)據(jù)格式表示方式，TID表示事務的ID，類別為事務所屬的類別，屬性即為事務所包含的屬性值。如表3所示為垂直數(shù)據(jù)格式表示方式，屬性為數(shù)據(jù)中出現(xiàn)的所有屬性，包含屬性的TID即為含有該屬性所有事務的ID值，同時每個事務所對應的類別標簽要與事務ID一同存儲，后續(xù)需要計算規(guī)則支持度與置信度。算法ECBA使用的是垂直數(shù)據(jù)格式，如表3所示，之后通過對事務數(shù)據(jù)ID求交來挖掘頻繁項集，生成類關聯(lián)規(guī)則集的算法ECBA-RG過程描述如表4所示。

對于稀疏矩陣類型的數(shù)據(jù)直接根據(jù)數(shù)據(jù)屬性生成頻繁項集，Eclat算法根據(jù)事務ID求交來直接獲取頻繁項集，而事務ID與所屬類別一一對應，可以直接與項集構造類關聯(lián)規(guī)則，并計算出支持度與置信度。改進的ECBA-RG算法只需掃描一次數(shù)據(jù)庫，不產(chǎn)生候選項集，在生成類關聯(lián)規(guī)則集階段節(jié)省了運行時間，減少了資源消耗，提高了算法的運行效率。得到類關聯(lián)規(guī)則集CARs后，需要從中挑選出最優(yōu)的分類規(guī)則來構造分類器，ECBA算法采用的是啟發(fā)式方法，選出優(yōu)先級高的規(guī)則來覆蓋數(shù)據(jù)庫中的數(shù)據(jù)，算法描述如表5所示。

3? 實驗結果與分析

本次實驗的環(huán)境為Windows 10×64位操作系統(tǒng)，Inter（R） Core（TM） i5-3470 CPU @3.20 GHz @3.20 GHz處理器，8 GB內存的PC，開發(fā)工具為PyCharm 、Python 3.6。

3.1? 實驗數(shù)據(jù)

實驗數(shù)據(jù)來源于全國中醫(yī)藥行業(yè)高等教育“十三五”規(guī)劃教材《中藥學》收錄的主藥及其附藥共568種中藥數(shù)據(jù)，選取的中藥屬性為“四氣”“五味”“歸經(jīng)”等24個屬性。為了統(tǒng)一數(shù)據(jù)，將“微辛”“微溫”“微甘”等直接統(tǒng)一為“辛”“溫”“甘”。部分數(shù)據(jù)如表6所示。另外還選取了UCI數(shù)據(jù)集上的Facebook、Australia、Car、seeds、Iris5個數(shù)據(jù)集進行對比實驗，實驗設置的最小支持度閾值為0.01，最小置信度閾值為0.5。

3.2? 結果分析

為了驗證ECBA算法在中藥“性-效”領域的適用性，選取了補虛藥和清熱藥兩個數(shù)據(jù)集，補虛藥又細分為補氣藥、補陽藥、補血藥、補陰藥四個小類，清熱藥細分為清熱瀉火藥、清熱燥濕藥、清熱解毒藥、清熱涼血藥、清虛熱藥五個小類，部分實驗數(shù)據(jù)如表6所示。實驗采用十折交叉驗證，將數(shù)據(jù)分成10份，選取其中的9份作為訓練集，剩下1份作為測試集，最終結果取10次實驗的平均值。

改進的關聯(lián)分類算法生成的類關聯(lián)規(guī)則均為有效規(guī)則，如表7所示為CBA和ECBA算法生成的分類規(guī)則，可以看到，CBA算法中排在首位的規(guī)則為熱的屬性取0，即不包含“熱”這個屬性就把它歸為清熱解毒藥，這明顯不符合現(xiàn)實需求，這是因為性效數(shù)據(jù)所構成的稀疏矩陣大部分屬性為0，因此容易生成無效規(guī)則，而ECBA算法在生成類關聯(lián)規(guī)則時采用垂直數(shù)據(jù)的思想，有效避免了無意義規(guī)則的生成。

如表8所示為改進算法ECBA和CBA在不同數(shù)據(jù)集上的運行效率對比，實驗選取了具有不同實例數(shù)、屬性數(shù)和類別數(shù)的數(shù)據(jù)集。從表8中可以看出，改進關聯(lián)分類算法ECBA在生成規(guī)則階段的運行時間明顯少于CBA算法的運行時間，兩種算法生成類關聯(lián)規(guī)則集的時間對比如圖1所示。從圖1中可以明顯看出，相較于CBA算法，ECBA算法大大減少了規(guī)則生成時間，數(shù)據(jù)集越大，屬性數(shù)越多，ECBA算法的優(yōu)勢越明顯。從數(shù)據(jù)集分類的錯誤率來看，改進的關聯(lián)分類算法相比原始算法有所提高，在清熱藥、補虛藥的數(shù)據(jù)集上變化較小是因為CBA算法會生成大量無意義的分類規(guī)則，但又能對數(shù)據(jù)進行正確分類，而改進關聯(lián)分類算法不生成無意義規(guī)則又保證了分類準確率，提高了算法的魯棒性。Iris數(shù)據(jù)集上算法的分類準確率有所降低，則是由于改進關聯(lián)分類算法更適用于屬性間差異較大的數(shù)據(jù)集，屬性間差異較小則會降低規(guī)則的分類準確率，這也是下一步算法改進需要考慮的問題。綜上所述，改進的關聯(lián)分類算法在規(guī)則生成階段及分類準確率方面均有一定的提升。

4? 結? 論

本文針對傳統(tǒng)具有非線性特征的中藥數(shù)據(jù)提出一種改進的關聯(lián)分類算法ECBA，相比經(jīng)典關聯(lián)分類算法CBA，避免了大量候選規(guī)則集的生成，減少了I/O消耗。通過借鑒垂直數(shù)據(jù)格式的思想，在中藥數(shù)據(jù)集上產(chǎn)生的規(guī)則更具解釋性。通過在中藥“性-效”數(shù)據(jù)集以及UCI數(shù)據(jù)集上的實驗，驗證了改進算法明顯提高了生成類關聯(lián)規(guī)則的時間，分類規(guī)則更有效，分類準確率也有所提高，更適用于中藥領域的數(shù)據(jù)分析。由于改進算法ECBA的針對性較強，接下來的研究將要考慮如何進一步提高分類規(guī)則的適用性，減少構建分類器的規(guī)則數(shù)量，以及減少參數(shù)設置的影響。

參考文獻：

[1] 王君平.中西醫(yī)并重，讓古老瑰寶重煥光彩 [N].人民日報，2019-12-02.

[2] 呂春艷，呂邵娃，李國玉，等.中藥性味拆分與組合藥理效應的研究進展 [J].中國中藥雜志，2018，43（14）：2892-2898.

[3] 秦晨普，張云華.基于分類修剪的關聯(lián)分類算法改進 [J].計算機系統(tǒng)應用，2019，28（4）：194-198.

[4] LIU B，HSU W，MA Y M . Integrating classification and association rule mining [EB/OL].[2023-02-05].https：//dl.acm.org/doi/abs/10.5555/3000292.3000305.

[5] DONG G Z，ZHANG X Z，WONG L，et al. CAEP： Classification by aggregating emerging patterns [EB/OL].[2023-01-15].https：//dl.acm.org/doi/10.5555/647856.738224.

[6] WANG K，ZHOU S Q，HE Y. Growing decision trees on support-less association rules [EB/OL].[2023-01-09].https：//dl.acm.org/doi/pdf/10.1145/347090.347147.

[7] LI W M，HAN J W，PEI J. CMAR：Accurate and efficient classification based on multiple class-association rules [C]//Proceedings 2001 IEEE International Conference on Data Mining. San Jose：IEEE，2001：369-376.

[8] HAO Z X，WANG X，YAO L，et al. Improved Classification Based on Predictive Association Rules [C]//2009 IEEE International Conference on Systems， Man and Cybernetics. San Antonio：IEEE，2009：1165-1170.

作者簡介：劉莉萍（1996—），女，漢族，江西吉安人，助教，碩士，主要研究方向：中醫(yī)藥數(shù)據(jù)挖掘；李歡（1995—），女，漢族，江西萍鄉(xiāng)人，助教，碩士，主要研究方向：中醫(yī)藥數(shù)據(jù)挖掘；何正宏（1980—），男，漢族，江西南昌人，工程師，碩士，主要研究方：網(wǎng)絡管理、網(wǎng)絡安全。