關聯(lián)分類算法改進及其在中藥“性-效”分析中的應用
2023-11-24 06:08:05劉莉萍李歡何正宏
現(xiàn)代信息科技 2023年18期
劉莉萍 李歡 何正宏
摘? 要：針對中藥“性-效”數據關聯(lián)度高、屬性稀疏的問題，提出一種使用垂直數據格式生成類關聯(lián)規(guī)則的關聯(lián)分類算法（ECBA）。該算法通過將數據轉換為垂直格式而避免了經典關聯(lián)分類算法（CBA）生成大量候選規(guī)則集、頻繁遍歷數據庫、產生無意義分類規(guī)則等不足。實驗結果表明，相較于傳統(tǒng)算法CBA，改進算法ECBA在規(guī)則生成時間、規(guī)則有效性以及準確率方面均有明顯提升，更適用于中藥“性-效”數據分析。
關鍵詞：關聯(lián)分類；中藥藥性；中藥功效；垂直數據；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ī)實踐中提煉出來的中藥學理論，藥效是根據中醫(yī)藥理論對藥物治療作用的高度概括，這些都是中藥理論的重要組成部分[1]。中藥藥性和中藥藥效簡稱“性-效”，是一個不可分割的有機整體，這也體現(xiàn)出中醫(yī)把人看作一個整體的觀念，“藥性互參”“性效結合”[2]。正是如此，在利用數據挖掘技術對中醫(yī)藥數據進行分析時更應該把數據之間的屬性緊密地聯(lián)系起來，而不能獨立地分割開來。關聯(lián)分類算法是通過挖掘出數據屬性之間所有規(guī)則集[3]，再從中選出最優(yōu)的規(guī)則用于分類，但傳統(tǒng)關聯(lián)分類算法CBA不能很好地適應中藥性效數據的特點?；诖?，本文提出一種改進算法（Eclat Classification Based on Association Rule， ECBA）。采用垂直數據表示格式，不生成候選項集，不需要對數據進行數字化處理，且產生的分類規(guī)則均為有效規(guī)則，相比于經典關聯(lián)分類算法（Classification Based on Association Rule， CBA）具有更高的效率。
1? 關聯(lián)分類算法改進分析
關聯(lián)規(guī)則技術挖掘數據之間的關聯(lián)性、相關性和其他有趣的聯(lián)系，但不進行預測。分類是通過找出數據屬性和類別之間某種特殊的關系而建立一種分類器，用于對未知數據進行類別預測。關聯(lián)規(guī)則與分類之間既有區(qū)別又有聯(lián)系，直至1998年，新加坡國立大學Liu教授首次提出將這兩種技術整合到一起，形成一種新的分類方法——關聯(lián)分類算法[4]。由于CBA算法在UCI（UC Irvine Machine Learning Repository）數據集上表現(xiàn)出非常高的準確率，優(yōu)于傳統(tǒng)分類算法（如C4.5、SVM、人工神經網絡等），因此引起眾多研究者的密切關注。相繼有學者在CBA算法的基礎上提出了改進算法。1999年，Dong等人[5]提出了基于顯露模式的分類方法（Classification by Aggregating Emerging Patterns， CAEP）。顯露模式是指不同類別下項集支持度有明顯差異的那些項集，實驗表明CAEP算法在海量數據或高維數據中均取得比CBA算法和C4.5算法更高的準確率。2000年，Wang等人[6]結合關聯(lián)規(guī)則和決策樹的優(yōu)點提出了關聯(lián)決策樹ADT算法，該方法不再同時使用支持度和置信度來選擇分類規(guī)則，而是根據置信度高低來選擇分類規(guī)則，再通過準確率驅動構建決策樹。2001年，Li等人[7]基于多類關聯(lián)規(guī)則提出一種準確有效的CMAR算法（Classification based on Multiple Class-Association Rules），該算法通過FP-growth算法生成分類關聯(lián)規(guī)則，但不限制其生成規(guī)則的數量，在預測未知實例時，基于多個規(guī)則判定其所屬類別標簽。雖然這樣提高了分類準確率，但卻造成候選集數量過多，規(guī)則冗余的問題。Baralis等人提出一種懶（Lazy）分類規(guī)則剪枝方法，直接通過迭代的方法將產生錯誤分類的規(guī)則全部剪去，雖然提高了分類的準確率，但并不適用于大規(guī)模數據集。Hao等人[8]提出一種預測型關聯(lián)規(guī)則分類方法（Classification based on Predictive Association Rules， CPAR），該算法基于貪婪算法的思想直接從訓練數據中尋找關聯(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ī)則項集就是形如
2.2? ECBA算法設計
在生成類關聯(lián)規(guī)則時由于CBA算法采用的是Apriori算法的思想，因此也繼承了其缺點，需要不斷掃描數據庫，產生大量的候選項集，造成了極大的I/O負擔，影響算法的運行效率。CBA算法應用于中醫(yī)藥“性-效”數據時，由于該算法需要對數據進行數字化處理，對于中藥藥性的22個特征，有就記為1，沒有則記為0，但是中藥的屬性十分稀疏，會造成取0的值偏多，那么在產生分類規(guī)則時會產生一些沒有意義的規(guī)則，雖然提高了分類準確率，但卻沒有什么實際意義。Eclat算法采用的是垂直數據格式，通過求交運算產生頻繁項集，既能減少掃描數據庫的次數，又能避免產生沒有意義的分類規(guī)則。ECBA算法就是基于Eclat算法的思想對其進行改進的基礎上而產生的，在保留原始數據特征的情況下，提高算法的運行效率。
如表2所示為水平數據格式表示方式，TID表示事務的ID，類別為事務所屬的類別，屬性即為事務所包含的屬性值。如表3所示為垂直數據格式表示方式，屬性為數據中出現(xiàn)的所有屬性，包含屬性的TID即為含有該屬性所有事務的ID值，同時每個事務所對應的類別標簽要與事務ID一同存儲，后續(xù)需要計算規(guī)則支持度與置信度。算法ECBA使用的是垂直數據格式，如表3所示，之后通過對事務數據ID求交來挖掘頻繁項集，生成類關聯(lián)規(guī)則集的算法ECBA-RG過程描述如表4所示。
對于稀疏矩陣類型的數據直接根據數據屬性生成頻繁項集，Eclat算法根據事務ID求交來直接獲取頻繁項集，而事務ID與所屬類別一一對應，可以直接與項集構造類關聯(lián)規(guī)則，并計算出支持度與置信度。改進的ECBA-RG算法只需掃描一次數據庫，不產生候選項集，在生成類關聯(lián)規(guī)則集階段節(jié)省了運行時間，減少了資源消耗，提高了算法的運行效率。得到類關聯(lián)規(guī)則集CARs后，需要從中挑選出最優(yōu)的分類規(guī)則來構造分類器，ECBA算法采用的是啟發(fā)式方法，選出優(yōu)先級高的規(guī)則來覆蓋數據庫中的數據，算法描述如表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? 實驗數據
實驗數據來源于全國中醫(yī)藥行業(yè)高等教育“十三五”規(guī)劃教材《中藥學》收錄的主藥及其附藥共568種中藥數據，選取的中藥屬性為“四氣”“五味”“歸經”等24個屬性。為了統(tǒng)一數據，將“微辛”“微溫”“微甘”等直接統(tǒng)一為“辛”“溫”“甘”。部分數據如表6所示。另外還選取了UCI數據集上的Facebook、Australia、Car、seeds、Iris5個數據集進行對比實驗，實驗設置的最小支持度閾值為0.01，最小置信度閾值為0.5。
3.2? 結果分析
為了驗證ECBA算法在中藥“性-效”領域的適用性，選取了補虛藥和清熱藥兩個數據集，補虛藥又細分為補氣藥、補陽藥、補血藥、補陰藥四個小類，清熱藥細分為清熱瀉火藥、清熱燥濕藥、清熱解毒藥、清熱涼血藥、清虛熱藥五個小類，部分實驗數據如表6所示。實驗采用十折交叉驗證，將數據分成10份，選取其中的9份作為訓練集，剩下1份作為測試集，最終結果取10次實驗的平均值。
改進的關聯(lián)分類算法生成的類關聯(lián)規(guī)則均為有效規(guī)則，如表7所示為CBA和ECBA算法生成的分類規(guī)則，可以看到，CBA算法中排在首位的規(guī)則為熱的屬性取0，即不包含“熱”這個屬性就把它歸為清熱解毒藥，這明顯不符合現(xiàn)實需求，這是因為性效數據所構成的稀疏矩陣大部分屬性為0，因此容易生成無效規(guī)則，而ECBA算法在生成類關聯(lián)規(guī)則時采用垂直數據的思想，有效避免了無意義規(guī)則的生成。
如表8所示為改進算法ECBA和CBA在不同數據集上的運行效率對比，實驗選取了具有不同實例數、屬性數和類別數的數據集。從表8中可以看出，改進關聯(lián)分類算法ECBA在生成規(guī)則階段的運行時間明顯少于CBA算法的運行時間，兩種算法生成類關聯(lián)規(guī)則集的時間對比如圖1所示。從圖1中可以明顯看出，相較于CBA算法，ECBA算法大大減少了規(guī)則生成時間，數據集越大，屬性數越多，ECBA算法的優(yōu)勢越明顯。從數據集分類的錯誤率來看，改進的關聯(lián)分類算法相比原始算法有所提高，在清熱藥、補虛藥的數據集上變化較小是因為CBA算法會生成大量無意義的分類規(guī)則，但又能對數據進行正確分類，而改進關聯(lián)分類算法不生成無意義規(guī)則又保證了分類準確率，提高了算法的魯棒性。Iris數據集上算法的分類準確率有所降低，則是由于改進關聯(lián)分類算法更適用于屬性間差異較大的數據集，屬性間差異較小則會降低規(guī)則的分類準確率，這也是下一步算法改進需要考慮的問題。綜上所述，改進的關聯(lián)分類算法在規(guī)則生成階段及分類準確率方面均有一定的提升。
4? 結? 論
本文針對傳統(tǒng)具有非線性特征的中藥數據提出一種改進的關聯(lián)分類算法ECBA，相比經典關聯(lián)分類算法CBA，避免了大量候選規(guī)則集的生成，減少了I/O消耗。通過借鑒垂直數據格式的思想，在中藥數據集上產生的規(guī)則更具解釋性。通過在中藥“性-效”數據集以及UCI數據集上的實驗，驗證了改進算法明顯提高了生成類關聯(lián)規(guī)則的時間，分類規(guī)則更有效，分類準確率也有所提高，更適用于中藥領域的數據分析。由于改進算法ECBA的針對性較強，接下來的研究將要考慮如何進一步提高分類規(guī)則的適用性，減少構建分類器的規(guī)則數量，以及減少參數設置的影響。
參考文獻：
[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ī)藥數據挖掘；李歡（1995—），女，漢族，江西萍鄉(xiāng)人，助教，碩士，主要研究方向：中醫(yī)藥數據挖掘；何正宏（1980—），男，漢族，江西南昌人，工程師，碩士，主要研究方：網絡管理、網絡安全。
