基于改進(jìn)GA?SVM的智能推薦診斷掛號算法

陳俊梅+周晉陽+張慧英

摘 要： 為提高患者就醫(yī)效率設(shè)計了一套智能推薦診斷掛號算法，對大量的歷史病案文本進(jìn)行訓(xùn)練和機(jī)器學(xué)習(xí)，以患者特征為依據(jù)進(jìn)行分類并推薦相應(yīng)的科室。使用遺傳算法與支持向量機(jī)結(jié)合進(jìn)行特征值提取和參數(shù)優(yōu)化，以核函數(shù)參數(shù)和文本特征值作為遺傳算法的染色體執(zhí)行選擇、交叉和變異操作，為提高遺傳算法效率并避免陷入局部最優(yōu)值，在遺傳算法初始化群體階段使用加權(quán)深度優(yōu)先搜索和輪盤賭結(jié)合的機(jī)制以保證種群多樣性，并對交叉概率和變異概率進(jìn)行自適應(yīng)優(yōu)化，在保留有用遺傳信息的同時實現(xiàn)全局搜索。實驗結(jié)果表明，該算法在有效降低特征值數(shù)目的同時提高了分類精度。

關(guān)鍵詞： 改進(jìn)遺傳算法； 支持向量機(jī)； 智能醫(yī)療系統(tǒng)； 智能推薦診斷掛號算法

中圖分類號： TN911?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）11?0115?04

Intelligent?recommendation diagnosis registration algorithm based on improved GA?SVM

CHEN Junmei1， ZHOU Jinyang1， ZHANG Huiying2

（1. Department of Biomedical Engineering， Changzhi Medical College， Changzhi 046000， China；

2. Department of Basic Medicine， Changzhi Medical College， Changzhi 046000， China）

Abstract： An intelligent?recommendation diagnosis registration algorithm was designed to improve the efficiency of medical treatment. The intelligent medical system performs training and machine learning for a large number of historical medical record texts， and classifies and recommends the appropriate medical departments for patients according to the patient characteristics. The genetic algorithm （GA） is combined with support vector machine to extract the characteristic value and optimize the parameter. The kernel function parameters and text characteristic values are taken as the chromosomes of the genetic algorithm to execute the selection， crossover and mutation operations. To improve the efficiency of GA， and avoid trapping in local optimum， the mechanism combining weighted depth?first search with roulette is used in the group initialization stage with GA to guarantee the population diversity， and performs with adaptive optimization to the crossover probability and mutation probability， which can realize the global search while reserving the useful genetic information. The experiment results show that the algorithm can improve the classification accuracy while reducing the quantity of characteristic values.

Keywords： improved genetic algorithm； support vector machine； intelligent medical system； intelligent?recommendation diagnosis registration system

0 引 言

現(xiàn)代醫(yī)學(xué)分工精細(xì)化為門診患者自助掛號帶來了一定的困擾，患者及其家人因缺乏專業(yè)基礎(chǔ)知識而且選擇主觀性大，易出現(xiàn)掛號時因科室較多難于選擇而費時低效，甚至存在掛錯科室的現(xiàn)象，給患者和醫(yī)院都帶來了不便，這是醫(yī)療辦提高自助掛號準(zhǔn)確率的主要原因。如今電子病案普及應(yīng)用日益加大，大量病案文本的存在為智能醫(yī)療系統(tǒng)進(jìn)行文本特征分析提供了便利，通過特征分析和識別結(jié)果，患者及其家人可進(jìn)行初判進(jìn)行準(zhǔn)確掛號，給患者帶來便利的同時可較大地提高醫(yī)療效率[1]。但大量的電子病案文本特征及海量的冗余信息為相關(guān)應(yīng)用的特征值選擇帶來了較大的困擾[2]，目前常用的文本特征選擇包括粒子群優(yōu)化算法、遺傳算法、序列選擇算法、關(guān)聯(lián)規(guī)則選擇算法等[3]，此外神經(jīng)網(wǎng)絡(luò)、樸素貝葉斯分類、KNN文本分類、支持向量機(jī)（Support Vector Machine，SVM）等分類方法也被應(yīng)用于這一領(lǐng)域[4]，其中SVM是一種較優(yōu)的選擇，該方法基于結(jié)構(gòu)風(fēng)險最小化原則和學(xué)習(xí)統(tǒng)計理論，與傳統(tǒng)的學(xué)習(xí)方法相比，SVM可較好地克服局部極小點、過擬合、維數(shù)災(zāi)難和小樣本等問題，利用構(gòu)設(shè)的最優(yōu)分類可實現(xiàn)對未知樣本的最小分類誤差。因此得到較多的關(guān)注和研究，但是SVM仍有許多需要完善之處，主要表現(xiàn)為沒有統(tǒng)一標(biāo)準(zhǔn)進(jìn)行參數(shù)選取，傳統(tǒng)參數(shù)選取方法依據(jù)經(jīng)驗進(jìn)行拼湊[5]，之前利用粒子群算法對SVM進(jìn)行優(yōu)化取得了一定效果，但易陷入局部極小值[6]。本文選擇遺傳算法（Genetic Algorithm，GA）和SVM結(jié)合進(jìn)行病案文本特征選取，并針對遺傳算法的不足，進(jìn)行交叉概率、變異概率自適應(yīng)優(yōu)化和加權(quán)深度優(yōu)先搜索機(jī)制優(yōu)化初始化群體以提高算法性能，實現(xiàn)智能推薦診斷掛號算法。

1 電子病案文本分類原理

如同其他SVM算法應(yīng)用，電子病案文本樣本將分為訓(xùn)練樣本和測試樣本。首先需對電子病案文本進(jìn)行預(yù)處理[7]，主要是提取關(guān)鍵詞以描述處理過程，包括去停用詞、中文分詞等，從而將文本轉(zhuǎn)換成SVM處理所需的形式。設(shè)文本集合為，特征詞集合為，文本集合中的一個文檔可表示為，其中各個元素對應(yīng)特征詞集合中的特征值，其計算方法如下：

（1）

式中：表示特征詞在第個文檔中出現(xiàn)的頻率；為出現(xiàn)特征詞的文本總數(shù)；表示文本總數(shù)。

式（1）是一種權(quán)值計算方法，采用的是TF/IDF計算法，其中IDF表征特征詞出現(xiàn)在整個文本集中的頻率，TF表征特征詞在對應(yīng)單一文本中出現(xiàn)的概率。

之后構(gòu)造SVM分類算法的分類器，其本質(zhì)是利用非線性映射將輸入向量映射到某個高維特征空間并在該空間構(gòu)設(shè)最優(yōu)分類超平面，最優(yōu)分類的標(biāo)準(zhǔn)是將兩類正確分開的同時保證分類間隔最大[8]，其示意圖如圖1所示。

圖1 卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

SVM分類器的輸入是各個病案文本，輸出是多個病種中的一個，而多分類問題是一個求解約束條件下的凸二次規(guī)劃問題，即：

（2）

式中為懲罰因子，主要用于調(diào)整分類器的誤分類率和泛化能力的折衷。引入拉格朗日因子法解決優(yōu)化問題，拉格朗日函數(shù)為：

（3）

式中：和均為Lagrange函數(shù)的乘子向量。

其對偶問題為：

（4）

式中為核函數(shù)，可得最終的判決函數(shù)為：

（5）

目前常用的核函數(shù)包括線性核函數(shù)、多項式核函數(shù)、徑向基核函數(shù)等[9]，其中徑向基核函數(shù)對高維非線性數(shù)據(jù)有較強(qiáng)的分析能力，而且參數(shù)僅有懲罰因子和標(biāo)準(zhǔn)化參數(shù)因此將其作為病案文本分類SVM的核函數(shù)，其表達(dá)式為：

（6）

在此基礎(chǔ)上判決函數(shù)最小化問題可轉(zhuǎn)化為的設(shè)置問題。研究表明，懲罰因子用于分類器的誤分類率和泛化能力的折衷，其值越小表示懲罰越小，學(xué)習(xí)機(jī)器復(fù)雜度低但經(jīng)驗風(fēng)險值大，其值越大表示懲罰越大，對錯分樣本的懲罰也越大；標(biāo)準(zhǔn)化參數(shù)影響高維特征空間樣本數(shù)據(jù)分布的復(fù)雜程度，其值變化會改變特征空間維數(shù)，從而影響結(jié)構(gòu)風(fēng)險范圍。因此需要尋找全局范圍內(nèi)最優(yōu)的，本文使用遺傳算法優(yōu)化SVM以獲取全局最優(yōu)結(jié)果。

2 基于改進(jìn)的GA?SVM的分類算法

2.1 GA?SVM原理

遺傳算法建立在達(dá)爾文進(jìn)化論基礎(chǔ)上，用于在計算機(jī)上模擬生命進(jìn)化機(jī)制以搜索最優(yōu)解，主要以優(yōu)勝劣汰、適者生存等原則進(jìn)行搜索求解，其主要優(yōu)點是不需要復(fù)雜運(yùn)算和建模，只需遺傳算法的三種算子即可獲取最優(yōu)解[10]。常規(guī)遺傳算法主要包括染色體編碼、種群規(guī)模、適應(yīng)度函數(shù)和遺傳算子。

種群個體可用長度為的二進(jìn)制串表示，其值為1則選擇該特征，其值為0則不選擇該特征，從而建立種群個體及對應(yīng)特征。由于病案文本的特殊性，種群個體的染色體主要包含兩部分，分別是SVM的參數(shù)及病案特征值。

種群規(guī)模大小直接影響遺傳算法的性能，目前常用取值區(qū)間為以綜合算法復(fù)雜度與種群多樣性的平衡。

適應(yīng)度函數(shù)是遺傳算法指引搜索的惟一信息，用于評價各碼串對問題的適應(yīng)程度，需遵循的原則包括：選用的特征子集盡可能少；應(yīng)可實現(xiàn)通用；有利于提高分類準(zhǔn)確性。

綜合考慮各種因素，可得適應(yīng)度函數(shù)為：

（7）

式中：為病種分類準(zhǔn)確度；為選擇特征值的數(shù)目；為調(diào)節(jié)權(quán)重參數(shù)，用于調(diào)節(jié)病種分類準(zhǔn)確率及特征值數(shù)目，其值越大病種分類準(zhǔn)確率越高，但特征值選擇的數(shù)目越多。

遺傳算子主要包括選擇算子、交叉算子和變異算子，選擇算子將父代中適應(yīng)度值高的染色體復(fù)制到子代中，同時淘汰適應(yīng)度值低的個體，一般使用輪盤賭法進(jìn)行選擇運(yùn)算，該方法可有效避免算法陷入局部最優(yōu)解；交叉算子是隨機(jī)選擇種群中的一對個體，互相交換染色體部分?jǐn)?shù)字串形成新的個體，本文使用單點交叉法，染色體間隨機(jī)選擇4個數(shù)字串進(jìn)行交叉，交叉概率為；變異算子是以很小概率即變異概率改變遺傳基因，即將染色體中數(shù)字串的值取反，從而提高種群多樣性并防止搜索停滯。的計算方法如下所示：

（8）

（9）

式中：為變異個體對應(yīng)的適應(yīng)度值；為兩個交叉?zhèn)€體的適應(yīng)度值；分別為進(jìn)化代中適應(yīng)度值的最大值、平均值；為交叉子代適應(yīng)度值分別大于、等于平均值時的交叉概率；為變異子代適應(yīng)度值分別大于、等于平均值時的交叉概率。

2.2 加權(quán)深度優(yōu)先搜索機(jī)制優(yōu)化

由于傳統(tǒng)的遺傳算法隨機(jī)產(chǎn)生初始種群，有一定概率在算法開始時陷入局部最優(yōu)[11]，為避免這種情況出現(xiàn)，結(jié)合使用輪盤賭和加權(quán)深度優(yōu)先搜索方法產(chǎn)生遺傳算法的初始種群，以自適應(yīng)、啟發(fā)式的初始化方法保證群體分布的均勻性、搜索速度，從而保證種群多樣性。

設(shè)初始種群數(shù)目為為種群中各個體賦予對應(yīng)的權(quán)值，對各節(jié)點進(jìn)行深度優(yōu)先搜索時，根據(jù)對應(yīng)的大小使用輪盤賭機(jī)制選定節(jié)點，找到符合要求的路徑后生成初始種群的染色體并對路徑上所有個體權(quán)值減1，重復(fù)上述步驟直至生成滿足群體規(guī)模要求的染色體數(shù)目。

2.3 交叉概率與變異概率修正

式（8），式（9）所示的傳統(tǒng)遺傳算法代表的搜索進(jìn)程仍存在一定缺陷，主要風(fēng)險是易陷入早熟導(dǎo)致無法搜索到全局最優(yōu)值[12]，分析遺傳算法過程可發(fā)現(xiàn)遺傳算法的初期由于不同個體間差異大，較小的變異概率和較大的交叉概率可實現(xiàn)有用遺傳信息的保存，而隨著遺傳算法進(jìn)程的不斷深入，子代個體間適應(yīng)度值逐漸趨向一致，較大的變異概率和較小的交叉概率可有效增加種群個體的多樣性，更有利于進(jìn)行全局搜索。基于這一理念，本文對交叉概率和變異概率進(jìn)行優(yōu)化，進(jìn)行自適應(yīng)生成，其計算方法如下所示：

（10）

（11）

式中：為個體對應(yīng)遺傳代數(shù)；為最大遺傳代數(shù)；分別為第代個體的交叉概率和變異概率；分別為交叉概率修正常數(shù)、變異概率修正常數(shù)。通過這種逐代交叉概率和變異概率修正，實現(xiàn)其值在不同進(jìn)化代數(shù)的自適應(yīng)調(diào)整，在保留有用遺傳信息的同時實現(xiàn)全局搜索。

2.4 改進(jìn)的GA?SVM算法

改進(jìn)的GA?SVM算法應(yīng)用于智能推薦診斷掛號的流程如圖2所示。對電子病案文本特征值進(jìn)行預(yù)處理，主要包括去除冗余信息和數(shù)據(jù)降維，然后從已有的個特征中按選取原則選擇個特征，從而實現(xiàn)最優(yōu)化指標(biāo)，最后對輸出結(jié)果進(jìn)行譯碼可獲得徑向基核函數(shù)參數(shù)與病案特征的最優(yōu)值。

3 實驗驗證

為驗證算法性能，數(shù)據(jù)來源于山西長治某兒科醫(yī)院的皮膚粘膜淋巴結(jié)綜合征、猩紅熱、風(fēng)疹三種疾病共1 000例病案，三類疾病均在一定程度上存在發(fā)熱、頭痛、食欲減退、咽喉痛、皮疹等癥狀，選取其中900例為訓(xùn)練樣本，其余100例為測試樣本，測試算法根據(jù)病癥特征進(jìn)行分類的準(zhǔn)確性。為測試改進(jìn)算法的效果，將本文算法（IGA?SVM）與

從表1可以看出，通過本文算法對特征值選擇的優(yōu)化，其數(shù)目由198個降至132個，去除了冗余特征值，提高了系統(tǒng)運(yùn)算效率，而且算法的分類精度優(yōu)于GA?SVM和PSO?SVM兩種算法分類精度，這是由于本文算法在種群初始化過程中使用輪盤賭和加權(quán)深度優(yōu)先搜索方法保證了種群的多樣性，同時對交叉概率和變異概率進(jìn)行自適應(yīng)優(yōu)化，在保留有用遺傳信息的同時實現(xiàn)全局搜索，提高了算法的性能。本文算法的分類歷史曲線如圖3所示，顯示了算法在優(yōu)化參數(shù)過程中不斷選擇最優(yōu)進(jìn)化結(jié)果，在28次迭代后曲線較為平緩，說明算法在多次跳出局部最優(yōu)之后最終達(dá)到全局最優(yōu)，優(yōu)化了算法的分類結(jié)果。

4 結(jié) 語

本文將遺傳算法和支持向量機(jī)結(jié)合應(yīng)用于智能醫(yī)療系統(tǒng)，目的是為患者提供掛號科室推薦，正確、高效的推薦結(jié)果是系統(tǒng)的必然要求。為提高算法分類精度，針對遺傳算法的不足進(jìn)行了分析，對其種群初始化過程和進(jìn)化過程進(jìn)行了優(yōu)化。實驗結(jié)果表明，優(yōu)化后算法的性能優(yōu)于常規(guī)的遺傳算法及PSO?SVM，分類精度得到了一定程度的提升，在智能醫(yī)療領(lǐng)域具有一定的應(yīng)用前景。

參考文獻(xiàn)

[1] HEIKKINEN V， KORPELA I， TOKOLA T， et al. An SVM classification of tree species radiometric signatures based on the Leica ADS40 sensor [J]. IEEE transactions on geoscience and remote sensing， 2011， 49（11）： 4539?4551.

[2] 宋淑彩，龐慧，丁學(xué)鈞.GA?SVM算法在文本分類中的應(yīng)用研究[J].計算機(jī)仿真，2011，28（1）：222?225.

[3] 楊梅，卿曉霞，王波.基于改進(jìn)遺傳算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化方法[J].計算機(jī)仿真，2009，26（5）：198?201.

[4] 朱文靜，白靜.一種混沌人工魚群算法對SVM參數(shù)的優(yōu)化及應(yīng)用[J].微電子學(xué)與計算機(jī)，2016，33（3）：90?94.

[5] BIN G F， GAO J J， LI X J， et al. Early fault diagnosis of rotating machinery based on wavelet packets?empirical decomposition feature extraction and neural network [J]. Mechanical systems and signal processing， 2012， 27（1）： 696?711.

[6] 胡天騏，單劍鋒，宋曉濤.基于改進(jìn)PSO?LSSVM的模擬電路故障診斷方法[J].計算機(jī)技術(shù)與發(fā)展，2015，25（6）：193?196.

[7] FU A M， SUN G Q， GUO Z F， et al. Forest cover classification with MODIS images in northeastern Asia [J]. IEEE journal of selected topics in applied earth observations remote sensing， 2010， 3（2）： 178?189.

[8] 劉東平，單甘霖，張岐龍，等.基于改進(jìn)遺傳算法的支持向量機(jī)參數(shù)優(yōu)化[J].微計算機(jī)應(yīng)用，2010，31（5）：11?15.

[9] 馬元良，裴生雷.基于改進(jìn)遺傳算法的SVM參數(shù)優(yōu)化研究[J].計算機(jī)仿真，2010，27（8）：150?153.

[10] 巨志斌.遺傳算法在車牌特征選擇的應(yīng)用研究[J].計算機(jī)仿真，2010，27（12）：331?335.

[11] 徐勝舟，裴承丹.基于遺傳算法和支持向量機(jī)的乳腺腫塊識別[J].計算機(jī)仿真，2015，32（2）：432?435.

[12] 王福林，王吉權(quán)，吳昌友，等.實數(shù)遺傳算法的改進(jìn)研究[J].生物數(shù)學(xué)學(xué)報，2006，21（1）：153?158.