基于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