关联分类算法改进及其在中药“性-效”分析中的应用

刘莉萍 李欢 何正宏

摘  要：针对中药“性-效”数据关联度高、属性稀疏的问题，提出一种使用垂直数据格式生成类关联规则的关联分类算法（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—），男，汉族，江西南昌人，工程师，硕士，主要研究方：网络管理、网络安全。