關聯分類算法改進及其在中藥“性-效”分析中的應用

劉莉萍 李歡 何正宏

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

關鍵詞：關聯分類；中藥藥性；中藥功效；垂直數據；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? 引? 言

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

1? 關聯分類算法改進分析

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

2? 改進關聯分類算法ECBA

2.1? CBA算法簡介

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

2.2? ECBA算法設計

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

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

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

3? 實驗結果與分析

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

3.1? 實驗數據

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

3.2? 結果分析

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

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

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

4? 結? 論

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

參考文獻：

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

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

[3] 秦晨普，張云華.基于分類修剪的關聯分類算法改進 [J].計算機系統應用，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—），女，漢族，江西吉安人，助教，碩士，主要研究方向：中醫藥數據挖掘；李歡（1995—），女，漢族，江西萍鄉人，助教，碩士，主要研究方向：中醫藥數據挖掘；何正宏（1980—），男，漢族，江西南昌人，工程師，碩士，主要研究方：網絡管理、網絡安全。