基于Aho_Corasick算法的中醫(yī)藥數(shù)據(jù)清洗方法

郭春麗　紀樹峰　林源　黃海松　王俐良

摘? 要： 中醫(yī)藥經(jīng)過數(shù)千年的發(fā)展，積累了大量的各種類型的數(shù)據(jù)。很多研究人員利用大數(shù)據(jù)技術，對方劑或藥品數(shù)據(jù)預處理后，使用相關算法挖掘和探尋疾病診療規(guī)律，為新藥研制、疾病診治、醫(yī)學科研提供科學的依據(jù)。但隨著方劑規(guī)模的增大，人工預處理的方式效率低且易出錯。因此，文章提出一種基于Aho_Corasick算法的清洗方法，將藥物作為模式串，對方劑或藥品的藥物信息進行識別，規(guī)范統(tǒng)一方劑中的藥物名稱，為后續(xù)挖掘工作提供高質(zhì)量的數(shù)據(jù)。實驗結果顯示，準確率達到95%以上，數(shù)據(jù)清洗效果明顯。

關鍵詞： 中醫(yī)藥; 大數(shù)據(jù)技術; Aho_Corasick算法; 預處理; 數(shù)據(jù)清洗

中圖分類號：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 引言

中醫(yī)藥是我國傳統(tǒng)文化燦爛寶庫中的重要組成部分，蘊藏了豐富的中醫(yī)經(jīng)驗知識。很多研究者利用大數(shù)據(jù)技術從中醫(yī)藥挖掘藥物的配伍規(guī)律，為中醫(yī)藥的臨床推廣提供科學的量化依據(jù)。

文獻[1]從4000余首經(jīng)典方劑中，根據(jù)中藥方劑特性構建中藥網(wǎng)絡模型，從1577味中藥節(jié)點和97103條邊中挖掘出復雜網(wǎng)絡中配伍關系緊密、相似度較大的藥物群。文獻[2]利用國醫(yī)堂名老中醫(yī)治療肺癌的2666條處方數(shù)據(jù)，處理方劑信息和藥物屬性信息，構建中藥加權網(wǎng)絡，找出核心藥物再進行藥物社團劃分。文獻[3]應用關聯(lián)規(guī)則分析技術，挖掘隱含在消渴病復方數(shù)據(jù)中的配伍規(guī)律。文獻[4]采用FP-Growth算法挖掘中藥方劑的隱藏信息，分析中藥的配伍規(guī)律和斗譜的編排，提高中藥調(diào)劑效率。以上研究使用的方劑數(shù)量不大，可人工處理驗證。但對于海量的數(shù)據(jù)，處理方劑等數(shù)據(jù)源里藥材名稱不規(guī)范、術語概念不統(tǒng)一的問題[5]，必須依賴于技術手段，確保中藥材的術語名稱統(tǒng)一，為后續(xù)數(shù)據(jù)挖掘做好準備。

本文采用Aho_Corasick算法根據(jù)《中華本草》、《中國藥典》等標準的中藥材名稱，按照數(shù)據(jù)一致性、完整性、正確性的規(guī)則，對中成藥的成分信息進行清洗，為中醫(yī)藥挖掘提供高質(zhì)量的基礎數(shù)據(jù)。

1 數(shù)據(jù)清洗的概念

數(shù)據(jù)清洗是數(shù)據(jù)挖掘前對數(shù)據(jù)預處理的一關鍵環(huán)節(jié)，是通過分析“臟數(shù)據(jù)”的產(chǎn)生原因和存在形式，利用現(xiàn)有的技術手段和方法去清洗“臟數(shù)據(jù)”，將“臟數(shù)據(jù)”轉(zhuǎn)化為滿足數(shù)據(jù)質(zhì)量或應用要求的數(shù)據(jù)，從而提高數(shù)據(jù)集的數(shù)據(jù)質(zhì)量[6]。主要包括以下幾大類。

⑴ 重復數(shù)據(jù)：相同屬性的值也相同，這樣的記錄被認為是重復記錄，可通過合并或刪除重復記錄。

⑵ 缺失數(shù)據(jù)：數(shù)據(jù)內(nèi)容殘缺不完整，比如關鍵屬性的值為NULL、空值或未知等。若不完整的數(shù)據(jù)用于挖掘，會影響抽取模式的正確性。

⑶ 錯誤數(shù)據(jù)：屬性的值不正確，比如中醫(yī)藥研究的是成分至少含有一種中藥材的中成藥、方劑等對象，對于成分全部為西藥的記錄被認為是錯誤數(shù)據(jù)，可直接刪除。

⑷ 異常數(shù)據(jù)：是指名稱不規(guī)范引起的沖突，比如處方中用的波蔻，經(jīng)查證，實為云南草寇的俗名[7]。這類情況較為普遍，一種中藥材有多個別名，需要對其規(guī)范統(tǒng)一。

2 數(shù)據(jù)清洗的設計

本文的中醫(yī)藥主要指藥廠生產(chǎn)的中成藥數(shù)據(jù)，包含藥品名稱、成分、功效等信息，共有10679條數(shù)據(jù)。

2.1 清洗的規(guī)則

中成藥信息的數(shù)據(jù)挖掘，主要是分析中成藥成分里中藥材之間的關系。一條中成藥數(shù)據(jù)是一個record，數(shù)據(jù)的清洗集中在名稱name、成分elements這兩個屬性，針對這兩個屬性對重復數(shù)據(jù)、缺失數(shù)據(jù)、錯誤數(shù)據(jù)、異常數(shù)據(jù)進行判別。

⑴ record[i].name=record[j].name，則是重復數(shù)據(jù)，作刪除處理。

⑵ record[i].name=‘’或record[i].elements=‘’，則是缺失數(shù)據(jù)，作刪除處理。

⑶ elements不含有中藥材的數(shù)據(jù)是錯誤數(shù)據(jù)。也就是說，從elements匹配出一個或多個中藥材的數(shù)據(jù)是正確數(shù)據(jù)。中藥材有標準的名稱，從網(wǎng)上爬取后存儲到數(shù)據(jù)庫中，主要有中藥材的標準名稱、別名、藥效、產(chǎn)區(qū)等信息，共有1759條記錄。如表1。

對錯誤數(shù)據(jù)的判別問題簡化為：

輸入：文本串，即長度為n的不規(guī)則字符串elements：T1，T2，T3，…，Tn。

模式串，即k種中藥材P1，P2，……，Pk組成。

過程：文本串的某個字符Tj（[j≤n]）與任意模式串對應位置的字符p均不相同，則稱文本串Tj處發(fā)生了失配;若某個模式串Pi（[i≤k]）與文本串的一個子串相同，則模式串Pi匹配成功。

輸出：匹配出所有的Pi構成集合S，集合S[=?]，則說明elements中沒有中藥材，則作刪除處理;

集合S[≠?]，則說明elements含有中藥材，則數(shù)據(jù)正常。

另外，由于中藥材的名稱之間有包含關系，比如，人參、人參葉、人參蘆、貓人參、人參子是五種不同的中藥材，elements含有人參葉時，會匹配出{人參葉，人參}，對于這種清洗后造成的數(shù)據(jù)不準確需要再進一步處理。

⑷ name名稱不規(guī)范導致的異常數(shù)據(jù)，不僅僅可以參照中藥材的別名，還需要有一些中藥材的業(yè)務知識。完成上面三種類型數(shù)據(jù)清洗后，再從清洗出的臟數(shù)據(jù)里進行人工核驗。這種類型的數(shù)據(jù)量不多，暫不屬于本文的范疇。

2.2 清洗的流程

數(shù)據(jù)清洗的流程如圖1所示，具體過程如下。

⑴ 從中成藥原始數(shù)據(jù)中讀取每一條記錄。

⑵ 根據(jù)重復數(shù)據(jù)、缺失數(shù)據(jù)的規(guī)則進行判斷，若符合規(guī)則，則對記錄進行刪除。

⑶ 匹配出中藥材。首先需要使用標準的中藥材名稱構建模式集，中藥材名稱都是中文，這里考慮對中文的支持;其次，選用多模式匹配的算法，讀取每條中成藥記錄的成分信息，匹配出中藥材名稱。

⑷ 對匹配結果再次處理：對于少量有包含關系的中藥材名稱，匹配的結果不夠準確。比如原成分信息中含有土茯苓，匹配的結果是{土茯苓、茯苓}，這種需進一步處理，即匹配后的中藥材有包含關系的，只取長度較長的中藥材，再把匹配的中藥材集合拼接成一個字符串作為該中成藥清洗后的成分信息。

⑸ 驗證結果：用清洗后的數(shù)據(jù)，與原始數(shù)據(jù)進行比較，檢查驗證清洗的效果。

3 應用實驗

3.1 實驗過程

本文采用Aho_Corasick算法（簡稱AC算法），它是將多個模式串構建成有限狀態(tài)自動機，實現(xiàn)以此掃描文本串完成多個模式串的匹配，時間復雜度為[O（n）][8]。

AC算法先建立一個初始狀態(tài) 0，逐一讀入每個模式串的每個字符，生成一個trie樹（二叉檢索樹），并進一步線索化，生成一個有向圖。其中，有限狀態(tài)自動機用三個函數(shù)來表示：goto函數(shù)、failure函數(shù)和output函數(shù)[9]。

⑴ goto函數(shù)，也叫做轉(zhuǎn)移函數(shù)，它的作用是在當前狀態(tài)下輸入下一個要比較文本的字符后可以達到的下一個狀態(tài)，此函數(shù)的生成需要掃描所有模式串的每個字符，時間復雜度隨著所有模式串的總長度線性增加。

⑵ failure函數(shù)，也叫做失效函數(shù)，表示當輸入的字符不匹配時應該轉(zhuǎn)移到的下一個狀態(tài)，它的生成時間與所有模式串的總長度成正比。

⑶ output函數(shù)，也叫做輸出函數(shù)，是輸出匹配成功的模式串。

清洗時發(fā)現(xiàn)中藥材名稱有一些是包含關系，比如表1中第四條記錄中的“炙甘草”與第五條記錄的“甘草，功效不同，它們屬于不同的中藥材。清洗時，“炙甘草”被識別成為“甘草”和“炙甘草”兩種藥材，對數(shù)據(jù)造成二次“污染”。經(jīng)過識別統(tǒng)計，331種中藥材存在和其他中藥材名稱有包含關系，如表2。

這里采取以下策略進行二次清洗：清洗后藥品成分信息中的多種中藥材，若名稱存在包含關系，則比較它們的長度，保留長度長的中藥材，另一種作刪除處理。清洗前后的示例數(shù)據(jù)如表3。

3.2 實驗分析

使用AC算法進行清洗后，中成藥的總記錄數(shù)為7038條，正確數(shù)據(jù)與“臟數(shù)據(jù)”的比例分別為65.9%、34.1%，耗時2.5秒。

對清洗結果進行驗證時，采用召回率、正確率對清洗效果進行衡量。

清洗后的數(shù)據(jù)，被正確判定為正例數(shù)a=7038，b=96，c=10679-7038=3641，其中96條數(shù)據(jù)是把成分含有“酒”或“醋”的數(shù)據(jù)錯誤判斷為正例。比如藥品“燈盞花素”，成分信息是“燈盞花素.輔料為乙二胺四醋酸二鈉、維生素c”，雖然“醋”是屬于中藥材，但“醋”只是成分信息中的一個字眼，并不是真正使用到的中藥材;藥品“酒石酸美托洛爾膠囊”，成分信息是“本品主要成份為：酒石酸美托洛爾”，雖然“酒”屬于中藥材，但“酒”不是真正使用的中藥材。

根據(jù)以上式子，最終計算得到r=65.91%，p=98.65%，f=79.02%?？梢院苊黠@地看出清洗效果明顯，數(shù)據(jù)質(zhì)量顯著提高。

4 結束語

目前，很多研究重視數(shù)據(jù)挖掘的算法，對數(shù)據(jù)準備工作研究的比較少。本文使用Aho_Corsick算法，以1759條藥物作為模式串，將中成藥的成分信息進行識別，規(guī)范統(tǒng)一中成藥成分的藥物名稱，清洗準確度高。

下一步工作，可以再對中成藥的成分信息進行挖掘，發(fā)現(xiàn)他們之間的配伍規(guī)律，為中醫(yī)藥事業(yè)的傳承提供更科學的數(shù)據(jù)參考。

參考文獻（References）：

[1] 韓楠，喬少杰，李天瑞，等.面向復雜網(wǎng)絡的中藥方劑配伍規(guī)律挖掘算法[J].計算機科學與探索，2017，11（7）：1159-1165

[2] 何菊，戴彩艷，胡晨駿，等.基于屬性相似度的中藥加權網(wǎng)絡構建及社團劃分方法[J].中藥研究，2019，21（12）：2746-2752

[3] 姚美村，艾路，袁月梅，等消渴病復方配伍規(guī)律的關聯(lián)規(guī)則分析[J].北京中醫(yī)藥大學學報，2002，25（6）：48

[4] 肖漢杰.基于數(shù)據(jù)挖掘的藥材并發(fā)關系和調(diào)劑效率提升研究[D].昆明：昆明理工大學，2013

[5] 賈李蓉，崔蒙.中醫(yī)藥科學數(shù)據(jù)研究進展[J].南京中醫(yī)藥大學學報，2012，28（5）：495-497

[6] 孔欽，葉長青，孫赟.大數(shù)據(jù)下數(shù)據(jù)預處理方法研究[J].計算機技術與發(fā)展，2018，28（5）：1-4

[7] 王善法.中藥一物一名及處方調(diào)配[J].時珍國醫(yī)國藥，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] 舒銀東.基于有限狀態(tài)自動機的多模式匹配算法研究[D].合肥：合肥工業(yè)大學，2011

3761501908266