石艷敏 張守賓 朱習(xí)軍

(青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院 山東 青島 266061)

0 引 言

通過“四診”信息中醫(yī)學(xué)可以發(fā)現(xiàn)人體生理和病理的變化，故采用中醫(yī)辨證原理來診斷病癥，然后對癥下藥，治愈疾病[1]。作為患者的外在表現(xiàn)，癥狀是識別疾病的重要航標(biāo)，也是診斷證型的重要依據(jù)。因此，對癥狀正確分類(辯證過程)是治愈疾病的重要環(huán)節(jié)，也是確保療效的前提。為獲取更高的分類精確度，以及提高算法的效率，本文采用分類算法實現(xiàn)對某種證型的判定，即基于KNN算法在Hadoop平臺下分布式計算實現(xiàn)對多組癥狀群的分類。挖掘出癥狀-證型間的內(nèi)在聯(lián)系，即癥狀群所屬的證型類別，從而分析出癥狀與證型之間的密切關(guān)系[2]。

1 Hadoop平臺

Hadoop[3]是Apache基金會所開發(fā)的一個開源的分布式系統(tǒng)軟件框架。該框架具備的高可靠性、高擴展性、高容錯性和低成本等特點使其成為當(dāng)前運用最廣泛的云平臺框架。其核心組件包括：分布式文件系統(tǒng)[4](HDFS)、分布式計算框架[5](MapReduce)和資源管理系統(tǒng)YARN等，該框架通過組建集群的方式實現(xiàn)對大規(guī)模數(shù)據(jù)集的高速計算和存儲。目前已在谷歌、亞馬遜、Facebook、Yahoob百度等多個大型網(wǎng)站上得到應(yīng)用。能夠穩(wěn)定解決海量數(shù)據(jù)的存儲、計算分析以及資源的管理調(diào)度等問題，是當(dāng)前該領(lǐng)域炙手可熱的開發(fā)和運行處理大規(guī)模數(shù)據(jù)的軟件平臺，這對日益龐大的中醫(yī)病案數(shù)據(jù)來說，是一個新的發(fā)展契機。

MapReduce 編程模型[6]是一個基于分布式計算模式的軟件結(jié)構(gòu)。分布式計算過程可簡化抽象為兩個函數(shù)：Map函數(shù)和Reduce函數(shù)。首先由JobTracker負(fù)責(zé)將大規(guī)模任務(wù)分解；然后，Map函數(shù)執(zhí)行分解后的小任務(wù)并得到中間結(jié)果；最后，由Reduce函數(shù)執(zhí)行匯總得到最終結(jié)果。其MapReduce編程模型的處理流程主要分為以下幾個階段，如圖1所示。

圖1 Mapreduce模型計算過程

(1) 分塊分配階段：MapReduce模型將待處理數(shù)據(jù)集切分為固定大小的片Splits，其大小默認(rèn)為64 MB，每個Split創(chuàng)建一個map任務(wù)，這里可以根據(jù)具體數(shù)據(jù)情況，設(shè)置切片大小，創(chuàng)建更多的map任務(wù)個數(shù)。

(2) Map階段：Map函數(shù)繼承Mapper類，讀取屬于自己的數(shù)據(jù)片Split，并將其映射成鍵值對再經(jīng)過用戶自定義的map函數(shù)操作，獲得新的鍵值對，這些鍵值對將會作為中間結(jié)果，緩存在當(dāng)前節(jié)點，每臺機器都執(zhí)行同樣的操作。

(3) 將Map任務(wù)產(chǎn)生的中間結(jié)果周期性地寫入磁盤之前，將對這些鍵值對進(jìn)行二次排序，首先根據(jù)數(shù)據(jù)所屬的partition(partition是分割map每個節(jié)點的結(jié)果)分組，相同key的value放到一個集合中，然后每個partition中再按key排序。如果設(shè)定了Combiner，則將key相同的數(shù)據(jù)收集到一個List中，得到鍵值組。此處的Combiner能夠?qū)ap端輸出做一次整合，減少中間結(jié)果鍵值對數(shù)目，從而減少系統(tǒng)消耗。

(4) Reduce階段：用戶定義Reduce函數(shù)繼承于Reducer類，通過與對應(yīng)的數(shù)據(jù)節(jié)點通信，獲取數(shù)據(jù)并整合排序。再經(jīng)過Reduce函數(shù)自定義操作，將輸入的中間鍵值轉(zhuǎn)化為新的鍵值對，并將結(jié)果輸出到HDFS或者HBase中。用戶可以指定Reducer的個數(shù)，個數(shù)越多則效率越快，但不可超過mapper個數(shù)。

2 KNN算法

KNN(K-Nearest Neighbor)分類算法[7]是比較經(jīng)典的機器學(xué)習(xí)算法之一，它由Cover和Hart在1968年提出。主要應(yīng)用對一些未知事物的分類，基于距離準(zhǔn)則來判斷未知事物所屬的類別。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，故KNN方法較其他方法對于類別域重疊較多或交叉的待分樣本集更為適合[8]。

當(dāng)p分別等于1、2、∞時，度量函數(shù)分別為曼哈頓距離、歐式距離和切比雪夫距離。

3 KNN算法并行化設(shè)計

KNN算法串行實現(xiàn)的時間復(fù)雜度為O(nm)，n、m分別表示樣本總數(shù)和屬性數(shù)目。因此該算法的計算量隨n、m的增大以n×m形式增長。但每個待分類樣本都可以獨立進(jìn)行KNN分類，因此可以基于Hadoop平臺中MapReduce模型并行化計算求解高復(fù)雜度問題[9]。在Hadoop分布式計算平臺上實現(xiàn)KNN算法，首先是worker節(jié)點將訓(xùn)練集和測試集從HDFS文件系統(tǒng)下載到本地節(jié)點，啟動Map計算過程，并根據(jù)所選擇的度量距離公式計算測試樣本與訓(xùn)練樣本的距離。最后將中間計算結(jié)果送到Reduce節(jié)點規(guī)約生成最終結(jié)果。

任務(wù)中將訓(xùn)練集和預(yù)測集讀取到內(nèi)存中進(jìn)行切分處理，計算測試樣本與訓(xùn)練樣本的距離；在Combine和Reduce進(jìn)行排序和統(tǒng)計的工作。

3.1 Mapper的設(shè)計

Mapper主要包括三個函數(shù)：setup()、map()、cleanup()。首先調(diào)用內(nèi)置Split函數(shù)讀取樣本片并轉(zhuǎn)換成特定格式文件，之后遍歷計算測試樣本與每個訓(xùn)練樣本的度量距離，存放在context集合形成鍵值對映射。主要流程為：

(1) 初始化數(shù)組List1，大小等同于測試數(shù)據(jù)量，對應(yīng)形式為<行號，樣本>。

(2) 根據(jù)所選度量函數(shù)計算每個測試樣本與本節(jié)點中訓(xùn)練樣本的距離值。

(3) 輸出數(shù)據(jù)>，對應(yīng)形式為<行號，向量集合<訓(xùn)練樣本類別,度量距離>>。

3.2 Combiner的設(shè)計

Combiner相當(dāng)于一次本地的Reduce操作，它在Map函數(shù)輸出的集合中取出鍵值，進(jìn)行篩選和排序：對每一個測試樣本所對應(yīng)的向量集合，按照度量距離選取K個最近鄰樣本作為Reduce節(jié)點的輸入，從而節(jié)約Reduce節(jié)點的計算和通信開銷。具體流程為：首先將Map節(jié)點的鍵值對存入ArryList集合，然后按value增序排序，最后每個測試樣本根據(jù)設(shè)定的K選取K條記錄傳給Reduce節(jié)點。Combiner需要輸入/輸出的格式都是即>。

3.3 Reducer的設(shè)計

Reducer主要任務(wù)是進(jìn)行規(guī)約獲取K個近鄰，計算多數(shù)近鄰樣本的類別，并賦予測試樣本。模型中執(zhí)行shuffle操作，即：將不同Map節(jié)點上同一測試樣本的數(shù)據(jù)送到一個節(jié)點上執(zhí)行排序、分類以及輸出操作。輸入數(shù)據(jù)形式為<測試樣本號,vector<訓(xùn)練樣本類標(biāo)識,度量距離>>；輸出數(shù)據(jù)形式為<測試樣本號,類標(biāo)識>。

并行的KNN分類算法流程如圖2所示。

圖2 KNN算法Mapreduce并行化原理

4 基于Hadoop的中醫(yī)癥狀群分類應(yīng)用

本文選擇中醫(yī)哮喘病病案[10]作為研究對象，所使用的證型及對應(yīng)的癥狀群是根據(jù)歷史病案數(shù)據(jù)經(jīng)關(guān)聯(lián)分析算法及名醫(yī)總結(jié)提取而來，主要證型有寒哮證、熱哮證、腎虛熱哮證、腎虛寒哮證、肺脾氣虛證五類證型。證型及其對應(yīng)的癥狀群如表1所示。

表1 不同證型及對應(yīng)癥狀群

由于中醫(yī)病案的特性，癥狀描述客觀度不強，因此在處理樣本數(shù)據(jù)時首先將癥狀進(jìn)行數(shù)據(jù)量化[11]。本文選取“咳嗽”、“呼吸”、“咯痰”、“胸悶”、“喘息”、“氣急”、“哮鳴音”、“舌質(zhì)”、“苔色”、“厚薄”、“舌滑膩”、“脈位”、“流暢度”、“紫紺”、“小便”、“口干”，以及“寒熱”17個癥狀屬性進(jìn)行表述，并對應(yīng)“風(fēng)哮證”、“熱哮證”、“寒哮證”、“腎虛寒哮證”以及“腎虛熱哮證”5個證型。量化準(zhǔn)則為：1) 若病案中不涉及對應(yīng)的癥狀，則該癥狀默認(rèn)為“正?！被颉盁o”；2) 涉及該癥狀而無描述輕重時默認(rèn)為“中”。癥狀所對應(yīng)的中醫(yī)描述及其量化取值,如表2所示。

表2 癥狀量化表

續(xù)表2

本文將KNN算法基于Hadoop平臺應(yīng)用于中醫(yī)哮喘病癥狀群的分類預(yù)測中。所采用的訓(xùn)練數(shù)據(jù)集是根據(jù)10 662例哮喘病中醫(yī)病案整理而來。詳細(xì)證型數(shù)據(jù)如表3所示。

表3 樣本數(shù)據(jù)統(tǒng)計

部分量化的病案數(shù)據(jù)如圖3所示。

圖3 部分病案數(shù)據(jù)

KNN算法是一種基于懶操作的算法，因此只有在輸入測試數(shù)據(jù)進(jìn)行預(yù)測計算時，才會處理訓(xùn)練數(shù)據(jù)。例輸入量化測試樣本：[1,2,2,0,2,1,3,0,1,0,1,1,0,0,0,0,0]，輸出預(yù)測種類為W。即對應(yīng)中醫(yī)癥狀群：微咳痰多、呼吸急促、喘憋氣逆、喉中哮鳴如水擊聲、易咯、面色青晦、舌苔白滑、脈弦浮緊。輸出預(yù)測證型為：寒哮證。結(jié)合證型中的總結(jié)的癥狀表現(xiàn)，可以確定其判斷正確。為驗證MapReduce編程模型的性能，選取病案中的一半作為測試用例，即5 331條作為預(yù)測病案。則KNN算法在Hadoop平臺運行5 331次，所得準(zhǔn)確率為98.12%，其建模耗時相比于單一傳統(tǒng)分類算法以及集成學(xué)習(xí)算法均有較大提升。

5 結(jié) 語

本文將KNN分類算法布局到Hadoop平臺，依據(jù)MapReduce編程模型實現(xiàn)分布計算，從而在保證分類準(zhǔn)確的前提下較大提高了分類建模時間。該平臺不僅可以滿足大數(shù)據(jù)量的分類計算，而且改善建模時間與數(shù)據(jù)量成正比的困境。通過中醫(yī)癥狀群分類應(yīng)用，驗證了KNN分類算法在Hadoop平臺的可行性，為后續(xù)應(yīng)用于更大數(shù)據(jù)量法分類預(yù)測奠定了基礎(chǔ)。