郭 凱，艾菊梅

(東華理工大學(xué)信息工程學(xué)院，江西 南昌 330013)

0 引 言

近年來，國家衛(wèi)生健康委員會(huì)統(tǒng)計(jì)出我國腦中風(fēng)的發(fā)病率持續(xù)升高[1]，腦中風(fēng)疾病將對患者產(chǎn)生極大的影響，摧殘患者身心，且對患者家庭和整個(gè)社會(huì)都是一筆不小的負(fù)擔(dān)，那么如何能早期預(yù)測患者患病風(fēng)險(xiǎn)就變得非常重要。因此，通過充分挖掘歷史病歷數(shù)據(jù)，綜合人群各項(xiàng)身體指標(biāo)，建立起體系全面完善的腦中風(fēng)預(yù)測手段[2]，能夠協(xié)助醫(yī)護(hù)人員判斷一般人群是否有罹患腦中風(fēng)的可能性，以實(shí)現(xiàn)早診斷、早治療、早預(yù)防的目的?；诂F(xiàn)有的腦中風(fēng)數(shù)據(jù)，利用分類算法等構(gòu)建基于深度學(xué)習(xí)的腦中風(fēng)預(yù)測方法[3]，有利于幫助醫(yī)護(hù)人員對心腦血管疾病的預(yù)測和公眾對腦中風(fēng)的預(yù)防。

KNN算法簡單易實(shí)現(xiàn)，在疾病預(yù)測領(lǐng)域使用廣泛[4]，本文將KNN算法用于腦中風(fēng)的預(yù)測中。KNN算法優(yōu)點(diǎn)是可以處理具有2個(gè)以上類的數(shù)據(jù)集，并且對輸入數(shù)據(jù)不強(qiáng)加任何假設(shè)分布。KNN缺點(diǎn)也相對明顯[5]，KNN算法對樣本進(jìn)行分類時(shí)，要計(jì)算它與其他所有樣本之間的距離，根據(jù)距離遠(yuǎn)近進(jìn)行判斷分類，這樣非常消耗時(shí)間，影響算法效率。文獻(xiàn)[6]提出了一種基于聚類去噪的改進(jìn)KNN(C_KNN)算法來實(shí)現(xiàn)疾病情況的預(yù)測，該文先對數(shù)據(jù)進(jìn)行聚類找出噪音數(shù)據(jù)進(jìn)行清除，減小數(shù)據(jù)集，以此減少算法工作量和噪音數(shù)據(jù)干擾，提高算法準(zhǔn)確率和效率。文獻(xiàn)[7]提出了一種基于布雷-柯蒂斯(Bray Curtis)距離的加權(quán)k-最近鄰分類算法(B_KNN)來實(shí)現(xiàn)癲癇的檢測，該文主要是將KNN分類器中的歐氏距離替換為布雷-柯蒂斯距離。在高維空間中數(shù)據(jù)之間的布雷-柯蒂斯距離可以直接表示數(shù)據(jù)之間的相似性[8]。布雷-柯蒂斯距離具有在特征參數(shù)之前挖掘相關(guān)性的特點(diǎn)，對于度量高維空間中數(shù)據(jù)的相似性具有重要意義,以布雷-柯蒂斯距離取代歐氏距離能提高算法的準(zhǔn)確率。

上述2種算法在大數(shù)據(jù)分類預(yù)測和癲癇診斷方面有非常大的意義和作用，但在腦中風(fēng)領(lǐng)域中，因?yàn)橐l(fā)腦中風(fēng)的因素[9]很多，特征向量多且權(quán)重各不相同，一些病患的數(shù)據(jù)可能表現(xiàn)在不同特征向量上，簡單聚類去噪可能會(huì)對待測數(shù)據(jù)中較為重要的數(shù)據(jù)進(jìn)行清除，影響算法的準(zhǔn)確率[10]。直接用布雷-柯蒂斯距離取代歐氏距離也不理想，需要科學(xué)有效地對各特征向量進(jìn)行權(quán)重分配[11]。

針對上述問題，本文采用FLANN在總樣本中循環(huán)搜索待測樣本的最近鄰點(diǎn)[12]，記錄若干個(gè)最近鄰點(diǎn)作為最近鄰點(diǎn)子集，用最近鄰點(diǎn)子集與待測樣本進(jìn)行匹配，降低計(jì)算量，提高算法效率，降低其他樣本對待測樣本的干擾，提高算法準(zhǔn)確率[13]。KNN在處理高維數(shù)據(jù)時(shí)，對數(shù)據(jù)的各特征向量平等對待，容易出現(xiàn)誤差，影響算法的準(zhǔn)確率[9]，本文采用AHP方法[14]為各特征向量分配權(quán)重，正確處理各特征向量的影響，提高算法的準(zhǔn)確率。本文充分考慮KNN算法在腦中風(fēng)領(lǐng)域應(yīng)用的不足，在專家們的研究基礎(chǔ)上進(jìn)行相應(yīng)的改善：在考慮全體樣本的情況下使用最近鄰點(diǎn)子集替代全集[15]；針對腦中風(fēng)數(shù)據(jù)集特征向量多且權(quán)重各不相同的特點(diǎn)，使用AHP方法為各特征向量科學(xué)有效地分配權(quán)重。這在腦中風(fēng)領(lǐng)域?qū)⒏舆m用。

本文針對這2個(gè)KNN的缺點(diǎn)進(jìn)行相應(yīng)優(yōu)化后采用一組腦中風(fēng)的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，F(xiàn)_KNN算法比傳統(tǒng)KNN算法和上述的C_KNN算法、B_KNN算法準(zhǔn)確率更高且速率更快。

1 相關(guān)工作

1.1 AHP

層次分析法(The analytic hierarchy process)簡稱AHP，是美國運(yùn)籌學(xué)家托馬斯·塞蒂(T.L. Saaty)在20世紀(jì)70年代中期正式提出的。AHP是將與決策有關(guān)的因素分解成目標(biāo)、準(zhǔn)則、方案等層次，在此基礎(chǔ)之上進(jìn)行定性和定量分析的決策方法。將結(jié)果作為目標(biāo)層，各特征向量作為準(zhǔn)則層，而后兩兩比較特征向量，構(gòu)造準(zhǔn)則層判斷矩陣，通過不斷實(shí)驗(yàn)，最后得出最恰當(dāng)?shù)臋?quán)重分配[16]。

1.2 FLANN

FLANN(快速最近鄰搜索包)是一個(gè)對大數(shù)據(jù)集和高維特征進(jìn)行最近鄰搜索的算法的集合。在機(jī)器學(xué)習(xí)中，對于一個(gè)高維數(shù)據(jù)集，F(xiàn)LANN庫可以快速找到待測樣本的最近鄰樣本。

FLANN庫中的優(yōu)先搜索K-means樹算法[17]，它利用數(shù)據(jù)固有的結(jié)構(gòu)信息，根據(jù)數(shù)據(jù)的所有維度進(jìn)行聚類，對于需要高精度計(jì)算的情形效果極好[18]。K-means樹算法分為2大部分，步驟歸納為如下8步：

1.建立優(yōu)先搜索K-means tree:

1)建立一個(gè)層次化的K-means樹。

2)將每個(gè)層次聚類中心作為樹節(jié)點(diǎn)。

3)當(dāng)某個(gè)集群內(nèi)的點(diǎn)數(shù)量小于K時(shí)，將這些數(shù)據(jù)節(jié)點(diǎn)作為葉子節(jié)點(diǎn)。

2.在優(yōu)先搜索K-means tree中進(jìn)行搜索。

4)從根節(jié)點(diǎn)N開始檢索。

5)如果N是葉子節(jié)點(diǎn)則將同層次的葉子節(jié)點(diǎn)都加入到搜索結(jié)果。

6)如果N不是葉子節(jié)點(diǎn)，則找出最近的那個(gè)節(jié)點(diǎn)Cq，同層次的其他節(jié)點(diǎn)加入到優(yōu)先隊(duì)列中。

7)對Cq節(jié)點(diǎn)進(jìn)行遞歸搜索。

8)如果優(yōu)先隊(duì)列不為空且count

最終快速準(zhǔn)確地找到待測樣本的最近鄰樣本[19]。

1.3 KNN

KNN算法是一種基本的分類和回歸方法，優(yōu)點(diǎn)是簡單，易于理解，無需建模與訓(xùn)練，易于實(shí)現(xiàn)；缺點(diǎn)是惰性算法，內(nèi)存開銷大，對測試樣本分類時(shí)計(jì)算量大，性能較低。

KNN最鄰近分類算法的實(shí)現(xiàn)原理[20]：為判斷待測樣本的類別，計(jì)算此樣本與所有已知類別樣本之間的距離，根據(jù)距離遠(yuǎn)近進(jìn)行排序，若前K個(gè)最近鄰已知樣本中那個(gè)所屬類別最多，即把未知樣本也歸為此類。KNN算法流程如圖1所示，算法步驟歸納為如下3步：

圖1 KNN算法流程圖

1)計(jì)算測試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離。

2)選取距離最近的K個(gè)點(diǎn)。

3)返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類。

2 F_KNN算法

在本文提出的基于FLANN改進(jìn)的KNN算法即F_KNN(循環(huán)搜索最近鄰)算法，其主要思想是在已知樣本中循環(huán)利用FLANN尋找待測樣本的最近鄰點(diǎn)，記錄此點(diǎn)，再從已知樣本中刪除這個(gè)最近鄰點(diǎn)，繼續(xù)尋找第2個(gè)待測樣本的最近鄰點(diǎn)。將記錄的若干個(gè)最近鄰點(diǎn)作為最近鄰點(diǎn)子集，利用最近鄰點(diǎn)子集來判斷待測樣本的所屬類別[21]。以最近鄰點(diǎn)子集代替整個(gè)已知樣本，計(jì)算出在計(jì)算距離時(shí)采用AHP分配特征向量的權(quán)重，求得子集中與待測樣本綜合距離最近的K個(gè)樣本，把K個(gè)最鄰近樣本中所屬類別占比較多的類別作為待測樣本的預(yù)測類別輸出。在F_KNN算法中，可減小計(jì)算量，極大提高算法的效率，降低各特征向量的影響，提高算法的準(zhǔn)確率[22]。F_KNN算法流程如圖2所示，算法步驟歸納為如下9步：

圖2 F_KNN算法流程圖

1)在已知樣本中建立K-means樹。

2)利用K-means樹快速尋找待測樣本的最近鄰點(diǎn)，并將此點(diǎn)記錄到最近鄰點(diǎn)子集中。

3)在已知樣本中刪除此點(diǎn)。

4)重復(fù)N次步驟1～步驟3。

5)將記錄的N個(gè)點(diǎn)作為最近鄰點(diǎn)子集。

6)使用AHP為各特征向量分配權(quán)重。

7)根據(jù)各特征向量權(quán)重計(jì)算待測樣本與子集中各樣本之間的綜合距離。

8)選取離待測樣本距離最近的K個(gè)點(diǎn)。

9)返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為待測樣本的預(yù)測分類。

在腦中風(fēng)預(yù)測領(lǐng)域，算法要結(jié)合患者的血壓、血糖、心臟病等多個(gè)因素來進(jìn)行預(yù)測診斷，簡單去除噪音數(shù)據(jù)可能會(huì)影響檢測結(jié)果[23]，而且特征向量較多且占比不同，需要一個(gè)科學(xué)有效的權(quán)重分配方法。F_KNN算法面對腦中風(fēng)領(lǐng)域預(yù)測進(jìn)行針對性的優(yōu)化，對待測樣本較為重要的樣本都進(jìn)行相應(yīng)的處理且減小算法的工作量[24]，同時(shí)使用AHP方法對各特征向量分配最為合適的權(quán)重。優(yōu)化后的F_KNN算法將更適用于腦中風(fēng)領(lǐng)域的預(yù)測。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)框架

3.1.1 數(shù)據(jù)集

本實(shí)驗(yàn)應(yīng)用的數(shù)據(jù)集為Kaggle官方提供的healthcare-dataset-stroke-data.csv數(shù)據(jù)集，含有5110組數(shù)據(jù)，每組數(shù)據(jù)包含12個(gè)信息，數(shù)據(jù)包含的信息如表1所示。

表1 數(shù)據(jù)集信息表

3.1.2 實(shí)驗(yàn)方案

實(shí)驗(yàn)中，使用JetBrains PyCharm 2017.1.2 x64作為程序后臺(tái)代碼開發(fā)IDE；測試平臺(tái)CPU:Intel(R) Core(TM) i5-6200U 2.4 GHz，顯卡:AMD Radeon R7 M370，操作系統(tǒng)：Microsoft Windows 10；記錄測試平臺(tái)上運(yùn)行算法的準(zhǔn)確率和時(shí)間。

3.2 實(shí)驗(yàn)流程

本文使用F_KNN算法對腦中風(fēng)進(jìn)行預(yù)測的思路為先初步處理數(shù)據(jù)，完善數(shù)據(jù)集，再使用F_KNN算法對數(shù)據(jù)集進(jìn)行訓(xùn)練與測試，最后進(jìn)行10折交叉驗(yàn)證求得算法準(zhǔn)確率。實(shí)驗(yàn)的具體流程如圖3所示，實(shí)驗(yàn)歸納為如下6步：

圖3 實(shí)驗(yàn)流程圖

Step1補(bǔ)充缺失數(shù)據(jù)。數(shù)據(jù)集中BMI(體重指數(shù))缺失了3.93%，以中間值28.10替代缺失值并且對類別變量使用獨(dú)熱編碼,將字符串類別轉(zhuǎn)換為數(shù)值。

Step2劃分?jǐn)?shù)據(jù)集。對腦中風(fēng)數(shù)據(jù)集的5110組數(shù)據(jù)進(jìn)行劃分，3577(70%)組數(shù)據(jù)作為訓(xùn)練集，1533(30%)作為測試集。

Step3建立最近鄰點(diǎn)子集。本文循環(huán)使用FLANN來尋找與待分類樣本最近的N個(gè)點(diǎn)作為最近鄰點(diǎn)子集，因?yàn)楦魈卣飨蛄康臋?quán)重不同，所以綜合距離和實(shí)際的距離并不相等，為了減小誤差，N一般要大于K,才能找到離待測樣本綜合距離最近的K個(gè)點(diǎn)。經(jīng)過反復(fù)實(shí)驗(yàn)，本文采用N=6K，在縮小子集降低計(jì)算量提高效率的同時(shí)不影響準(zhǔn)確率。

Step4計(jì)算距離。由于數(shù)據(jù)集是高維數(shù)據(jù)集，含有多個(gè)特征向量，每個(gè)特征向量對分類結(jié)果的影響差別很大，因此首先要確定每個(gè)特征向量的權(quán)重。本文采用AHP來確定各特征向量權(quán)重，把是否中風(fēng)作為目標(biāo)層，各特征向量作為準(zhǔn)則層，而后兩兩比較特征向量，通過不斷實(shí)驗(yàn)，最后得出最恰當(dāng)?shù)臋?quán)重分配，如圖4所示。

圖4 特征向量分配圖

經(jīng)過實(shí)驗(yàn)對比，本文計(jì)算距離時(shí)采用歐氏距離效果最佳，故本文采用AHP計(jì)算各特征向量權(quán)重后，再計(jì)算2個(gè)樣本之間的歐氏距離，最后根據(jù)各特征向量權(quán)重求2個(gè)樣本之間的綜合距離。

Step5判斷待測樣本類別。對所有距離進(jìn)行升序排序得出離待測樣本最近的前K個(gè)點(diǎn)，前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為待測樣本的預(yù)測分類。

Step610折交叉驗(yàn)證[25]。為了充分利用數(shù)據(jù)集對算法效果進(jìn)行測試，進(jìn)行10折交叉驗(yàn)證，再求其均值，作為對算法準(zhǔn)確性的估計(jì)。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 對比實(shí)驗(yàn)

本文引用上述提到的C_KNN和B_KNN同樣對腦中風(fēng)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，最后將F_KNN、C_KNN、B_KNN、傳統(tǒng)KNN的結(jié)果進(jìn)行比較分析。

C_KNN算法通過聚類，將訓(xùn)練集中同一類別的樣本按照相似度分成若干個(gè)子類別，形成多個(gè)聚類中心。聚類后，出現(xiàn)一些沒有分類成任何小聚類的樣本。這些文本一般屬于噪聲樣本，該類樣本的代表性較小，可去除這些樣本，在最后KNN算法對待測樣本進(jìn)行計(jì)算時(shí)，選取與待測樣本最為接近的子集取代全集進(jìn)行計(jì)算，將大大降低KNN算法的計(jì)算復(fù)雜度，提高KNN算法的時(shí)間效率。

B_KNN算法以布雷-柯蒂斯距離取代KNN算法中的歐氏距離，通過這種方法來挖掘樣本之間的相似性對待測樣本進(jìn)行比較，可以一定程度上提高算法的準(zhǔn)確率。首先利用Bray Curtis距離計(jì)算訓(xùn)練集中y(y=(y1,y2，…，yN))與采樣點(diǎn)之間的距離。

其中，N為樣本的特征個(gè)數(shù)。顯然，b=0表示樣本完全相同，而b=1是2個(gè)樣本之間可以觀察到的最大差異。

4.2 實(shí)驗(yàn)分析

本文從準(zhǔn)確率、召回率和F1值3個(gè)方面對F_KNN算法進(jìn)行評(píng)價(jià)。

準(zhǔn)確率是正確樣本數(shù)(Sc)比實(shí)際樣本數(shù)(Sm)，計(jì)算公式為:Pc=Sc/Sm。利用最優(yōu)參數(shù)訓(xùn)練好的F_KNN與C_KNN、B_KNN和傳統(tǒng)KNN對腦中風(fēng)數(shù)據(jù)集進(jìn)行分類得到分類的準(zhǔn)確率對比如圖5所示。

圖5 不同算法準(zhǔn)確率對比圖

從圖5可以看出在面對腦中風(fēng)數(shù)據(jù)集時(shí)，F(xiàn)_KNN表現(xiàn)最為良好，準(zhǔn)確率波動(dòng)不大且一直較高，在K取值為6時(shí)達(dá)到最大值0.9642。這表明F_KNN算法的分類性能更高，表現(xiàn)更好。

召回率[26]是用實(shí)驗(yàn)正確樣本數(shù)(Sc)除以所有正確樣本數(shù)(So)。計(jì)算公式如下：Pr=Sc/So。F_KNN算法與傳統(tǒng)KNN算法的召回率對比如圖6所示。

F1值[27]是一個(gè)綜合評(píng)價(jià)分類效果的指標(biāo)，計(jì)算公式如下：F1=Pc·Pr·2/(Pc+Pr)。F_KNN與C_KNN、B_KNN和傳統(tǒng)KNN的F1值對比如圖6所示。

圖6 不同算法召回率與F1值對比圖

從圖6中可以看出F_KNN的F1值最高，召回率偏高，這表明F_KNN算法的鄰域穩(wěn)定性更優(yōu)。

本文在實(shí)驗(yàn)代碼運(yùn)行中添加1個(gè)計(jì)時(shí)器，計(jì)算每次代碼運(yùn)行的時(shí)間，用來比較算法的效率。本文選擇當(dāng)K取不同值時(shí)運(yùn)行F_KNN與C_KNN、B_KNN和傳統(tǒng)KNN各20次，取平均時(shí)長，時(shí)長對比圖如圖7所示。

圖7 不同算法運(yùn)行時(shí)間對比圖

從圖7可以看出F_KNN算法的運(yùn)行時(shí)間遠(yuǎn)低于傳統(tǒng)的KNN算法和B_KNN算法，也低于C_KNN算法，這表明F_KNN算法的效率最高。

綜上所述，優(yōu)化后的F_KNN算法提高了分類準(zhǔn)確率且極大提高了分類效率。在處理高維且數(shù)據(jù)較大的數(shù)據(jù)集時(shí)，優(yōu)化后的KNN算法優(yōu)勢明顯，具有較好的應(yīng)用前景。

5 結(jié)束語

本文工作主要圍繞腦中風(fēng)疾病預(yù)測開展。首先系統(tǒng)地介紹KNN算法的基本原理并分析KNN算法在高維數(shù)據(jù)集運(yùn)用中的缺陷。針對KNN算法的缺陷，本文使用AHP為特征向量分配權(quán)重；使用FLANN尋找最近鄰點(diǎn)子集，取代全集，減少算法計(jì)算量，對算法進(jìn)行優(yōu)化。最后實(shí)驗(yàn)從準(zhǔn)確率、召回率、F1值3個(gè)方面驗(yàn)證F_KNN算法比傳統(tǒng)KNN算法更加有效。

本文優(yōu)化后的F_KNN算法在醫(yī)療大數(shù)據(jù)方面的應(yīng)用，不僅縮短了算法的預(yù)測時(shí)間，而且可以取得更好的預(yù)測效果。將F_KNN算法運(yùn)用在疾病預(yù)測領(lǐng)域，可以簡單快速地預(yù)測用戶的身體狀況，對用戶起到一個(gè)早診斷、早治療的效果，能幫助醫(yī)護(hù)人員對用戶的疾病進(jìn)行初步的預(yù)測和預(yù)防。