基于Aho_Corasick算法的中医药数据清洗方法

郭春丽　纪树峰　林源　黄海松　王俐良

摘  要： 中医药经过数千年的发展，积累了大量的各种类型的数据。很多研究人员利用大数据技术，对方剂或药品数据预处理后，使用相关算法挖掘和探寻疾病诊疗规律，为新药研制、疾病诊治、醫学科研提供科学的依据。但随着方剂规模的增大，人工预处理的方式效率低且易出错。因此，文章提出一种基于Aho_Corasick算法的清洗方法，将药物作为模式串，对方剂或药品的药物信息进行识别，规范统一方剂中的药物名称，为后续挖掘工作提供高质量的数据。实验结果显示，准确率达到95%以上，数据清洗效果明显。

关键词： 中医药; 大数据技术; Aho_Corasick算法; 预处理; 数据清洗

中图分类号：TP3          文献标识码：A       文章编号：1006-8228（2022）03-77-04

Abstract： Traditional Chinese Medicine （TCM） is accumulated a large number of various types of data after being thousands of years. Many researchers use big data technology to mine and explore the rules of disease diagnosis after preprocessing the data of prescription and/or drug， so as to provide scientific basis for new drug development， disease diagnosis and treatment， and medical research. However， with the increase of prescriptions' scale， it is inefficient and error-prone in the manual pre-process method. Therefore， a cleaning method based on Aho_Corasick algorithm is proposed in this paper. The drugs are used as pattern strings， and then their names are identified from prescriptions or TCM to make them a standard and uniform， so as to provide high-quality TCM data prepared for subsequent mining work. The experimental results show that the accuracy are more than 95%， and the data cleaning effect is obvious.

Key words： TCM; big data technology; Aho_Corasick algorithm; pre-process; data cleaning

0 引言

中医药是我国传统文化灿烂宝库中的重要组成部分，蕴藏了丰富的中医经验知识。很多研究者利用大数据技术从中医药挖掘药物的配伍规律，为中医药的临床推广提供科学的量化依据。

文献[1]从4000余首经典方剂中，根据中药方剂特性构建中药网络模型，从1577味中药节点和97103条边中挖掘出复杂网络中配伍关系紧密、相似度较大的药物群。文献[2]利用国医堂名老中医治疗肺癌的2666条处方数据，处理方剂信息和药物属性信息，构建中药加权网络，找出核心药物再进行药物社团划分。文献[3]应用关联规则分析技术，挖掘隐含在消渴病复方数据中的配伍规律。文献[4]采用FP-Growth算法挖掘中药方剂的隐藏信息，分析中药的配伍规律和斗谱的编排，提高中药调剂效率。以上研究使用的方剂数量不大，可人工处理验证。但对于海量的数据，处理方剂等数据源里药材名称不规范、术语概念不统一的问题[5]，必须依赖于技术手段，确保中药材的术语名称统一，为后续数据挖掘做好准备。

本文采用Aho_Corasick算法根据《中华本草》、《中国药典》等标准的中药材名称，按照数据一致性、完整性、正确性的规则，对中成药的成分信息进行清洗，为中医药挖掘提供高质量的基础数据。

1 数据清洗的概念

数据清洗是数据挖掘前对数据预处理的一关键环节，是通过分析“脏数据”的产生原因和存在形式，利用现有的技术手段和方法去清洗“脏数据”，将“脏数据”转化为满足数据质量或应用要求的数据，从而提高数据集的数据质量[6]。主要包括以下几大类。

⑴ 重复数据：相同属性的值也相同，这样的记录被认为是重复记录，可通过合并或删除重复记录。

⑵ 缺失数据：数据内容残缺不完整，比如关键属性的值为NULL、空值或未知等。若不完整的数据用于挖掘，会影响抽取模式的正确性。

⑶ 错误数据：属性的值不正确，比如中医药研究的是成分至少含有一种中药材的中成药、方剂等对象，对于成分全部为西药的记录被认为是错误数据，可直接删除。

⑷ 异常数据：是指名称不规范引起的冲突，比如处方中用的波蔻，经查证，实为云南草寇的俗名[7]。这类情况较为普遍，一种中药材有多个别名，需要对其规范统一。

2 数据清洗的设计

本文的中医药主要指药厂生产的中成药数据，包含药品名称、成分、功效等信息，共有10679条数据。

2.1 清洗的规则

中成药信息的数据挖掘，主要是分析中成药成分里中药材之间的关系。一条中成药数据是一个record，数据的清洗集中在名称name、成分elements这两个属性，针对这两个属性对重复数据、缺失数据、错误数据、异常数据进行判别。

⑴ record[i].name=record[j].name，则是重复数据，作删除处理。

⑵ record[i].name=‘’或record[i].elements=‘’，则是缺失数据，作删除处理。

⑶ elements不含有中药材的数据是错误数据。也就是说，从elements匹配出一个或多个中药材的数据是正确数据。中药材有标准的名称，从网上爬取后存储到数据库中，主要有中药材的标准名称、别名、药效、产区等信息，共有1759条记录。如表1。

对错误数据的判别问题简化为：

输入：文本串，即长度为n的不规则字符串elements：T1，T2，T3，…，Tn。

模式串，即k种中药材P1，P2，……，Pk组成。

过程：文本串的某个字符Tj（[j≤n]）与任意模式串对应位置的字符p均不相同，则称文本串Tj处发生了失配;若某个模式串Pi（[i≤k]）与文本串的一个子串相同，则模式串Pi匹配成功。

输出：匹配出所有的Pi构成集合S，集合S[=∅]，则说明elements中没有中药材，则作删除处理;

集合S[≠∅]，则说明elements含有中药材，则数据正常。

另外，由于中药材的名称之间有包含关系，比如，人参、人参叶、人参芦、猫人参、人参子是五种不同的中药材，elements含有人参叶时，会匹配出{人参叶，人参}，对于这种清洗后造成的数据不准确需要再进一步处理。

⑷ name名称不规范导致的异常数据，不仅仅可以参照中药材的别名，还需要有一些中药材的业务知识。完成上面三种类型数据清洗后，再从清洗出的脏数据里进行人工核验。这种类型的数据量不多，暂不属于本文的范畴。

2.2 清洗的流程

数据清洗的流程如图1所示，具体过程如下。

⑴ 从中成药原始数据中读取每一条记录。

⑵ 根据重复数据、缺失数据的规则进行判断，若符合规则，则对记录进行删除。

⑶ 匹配出中药材。首先需要使用标准的中药材名称构建模式集，中药材名称都是中文，这里考虑对中文的支持;其次，选用多模式匹配的算法，读取每条中成药记录的成分信息，匹配出中药材名称。

⑷ 对匹配结果再次处理：对于少量有包含关系的中药材名称，匹配的结果不够准确。比如原成分信息中含有土茯苓，匹配的结果是{土茯苓、茯苓}，这种需进一步处理，即匹配后的中药材有包含关系的，只取长度较长的中药材，再把匹配的中药材集合拼接成一个字符串作为该中成药清洗后的成分信息。

⑸ 验证结果：用清洗后的数据，与原始数据进行比较，检查验证清洗的效果。

3 應用实验

3.1 实验过程

本文采用Aho_Corasick算法（简称AC算法），它是将多个模式串构建成有限状态自动机，实现以此扫描文本串完成多个模式串的匹配，时间复杂度为[O（n）][8]。

AC算法先建立一个初始状态 0，逐一读入每个模式串的每个字符，生成一个trie树（二叉检索树），并进一步线索化，生成一个有向图。其中，有限状态自动机用三个函数来表示：goto函数、failure函数和output函数[9]。

⑴ goto函数，也叫做转移函数，它的作用是在当前状态下输入下一个要比较文本的字符后可以达到的下一个状态，此函数的生成需要扫描所有模式串的每个字符，时间复杂度随着所有模式串的总长度线性增加。

⑵ failure函数，也叫做失效函数，表示当输入的字符不匹配时应该转移到的下一个状态，它的生成时间与所有模式串的总长度成正比。

⑶ output函数，也叫做输出函数，是输出匹配成功的模式串。

清洗时发现中药材名称有一些是包含关系，比如表1中第四条记录中的“炙甘草”与第五条记录的“甘草，功效不同，它们属于不同的中药材。清洗时，“炙甘草”被识别成为“甘草”和“炙甘草”两种药材，对数据造成二次“污染”。经过识别统计，331种中药材存在和其他中药材名称有包含关系，如表2。

这里采取以下策略进行二次清洗：清洗后药品成分信息中的多种中药材，若名称存在包含关系，则比较它们的长度，保留长度长的中药材，另一种作删除处理。清洗前后的示例数据如表3。

3.2 实验分析

使用AC算法进行清洗后，中成药的总记录数为7038条，正确数据与“脏数据”的比例分别为65.9%、34.1%，耗时2.5秒。

对清洗结果进行验证时，采用召回率、正确率对清洗效果进行衡量。

清洗后的数据，被正确判定为正例数a=7038，b=96，c=10679-7038=3641，其中96条数据是把成分含有“酒”或“醋”的数据错误判断为正例。比如药品“灯盏花素”，成分信息是“灯盏花素.辅料为乙二胺四醋酸二钠、维生素c”，虽然“醋”是属于中药材，但“醋”只是成分信息中的一个字眼，并不是真正使用到的中药材;药品“酒石酸美托洛尔胶囊”，成分信息是“本品主要成份为：酒石酸美托洛尔”，虽然“酒”属于中药材，但“酒”不是真正使用的中药材。

根据以上式子，最终计算得到r=65.91%，p=98.65%，f=79.02%。可以很明显地看出清洗效果明显，数据质量显著提高。

4 结束语

目前，很多研究重视数据挖掘的算法，对数据准备工作研究的比较少。本文使用Aho_Corsick算法，以1759条药物作为模式串，将中成药的成分信息进行识别，规范统一中成药成分的药物名称，清洗准确度高。

下一步工作，可以再对中成药的成分信息进行挖掘，发现他们之间的配伍规律，为中医药事业的传承提供更科学的数据参考。

参考文献（References）：

[1] 韩楠，乔少杰，李天瑞，等.面向复杂网络的中药方剂配伍规律挖掘算法[J].计算机科学与探索，2017，11（7）：1159-1165

[2] 何菊，戴彩艳，胡晨骏，等.基于属性相似度的中药加权网络构建及社团划分方法[J].中药研究，2019，21（12）：2746-2752

[3] 姚美村，艾路，袁月梅，等消渴病复方配伍规律的关联规则分析[J].北京中医药大学学报，2002，25（6）：48

[4] 肖汉杰.基于数据挖掘的药材并发关系和调剂效率提升研究[D].昆明：昆明理工大学，2013

[5] 贾李蓉，崔蒙.中医药科学数据研究进展[J].南京中医药大学学报，2012，28（5）：495-497

[6] 孔钦，叶长青，孙赟.大数据下数据预处理方法研究[J].计算机技术与发展，2018，28（5）：1-4

[7] 王善法.中药一物一名及处方调配[J].时珍国医国药，2000，11（2）：153

[8] Aho A V， Corasick M J. Efficient String Matching： An Aid to Bibliographic Search[J].Communications of the ACM，1975，18（6）：333-340

[9] 舒银东.基于有限状态自动机的多模式匹配算法研究[D].合肥：合肥工业大学，2011

3761501908266