郭 凱，艾菊梅

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

0 引 言

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

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

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

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

本文針對這2個KNN的缺點進行相應(yīng)優(yōu)化后采用一組腦中風(fēng)的數(shù)據(jù)集進行實驗，實驗結(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，是美國運籌學(xué)家托馬斯·塞蒂(T.L. Saaty)在20世紀(jì)70年代中期正式提出的。AHP是將與決策有關(guān)的因素分解成目標(biāo)、準(zhǔn)則、方案等層次，在此基礎(chǔ)之上進行定性和定量分析的決策方法。將結(jié)果作為目標(biāo)層，各特征向量作為準(zhǔn)則層，而后兩兩比較特征向量，構(gòu)造準(zhǔn)則層判斷矩陣，通過不斷實驗，最后得出最恰當(dāng)?shù)臋?quán)重分配[16]。

1.2 FLANN

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

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

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

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

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

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

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

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

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

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

7)對Cq節(jié)點進行遞歸搜索。

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

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

1.3 KNN

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

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

圖1 KNN算法流程圖

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

2)選取距離最近的K個點。

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

2 F_KNN算法

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

圖2 F_KNN算法流程圖

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

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

3)在已知樣本中刪除此點。

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

5)將記錄的N個點作為最近鄰點子集。

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

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

8)選取離待測樣本距離最近的K個點。

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

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

3 實驗分析

3.1 實驗框架

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

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

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

3.1.2 實驗方案

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

3.2 實驗流程

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

圖3 實驗流程圖

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

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

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

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

圖4 特征向量分配圖

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

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

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

4 實驗結(jié)果及分析

4.1 對比實驗

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

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

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

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

4.2 實驗分析

本文從準(zhǔn)確率、召回率和F1值3個方面對F_KNN算法進行評價。

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

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

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

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

F1值[27]是一個綜合評價分類效果的指標(biāo)，計算公式如下：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)。

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

圖7 不同算法運行時間對比圖

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

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

5 結(jié)束語

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

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