基于FLANN改進的KNN醫(yī)療分類算法

郭 凱，艾菊梅

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

0 引 言

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

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

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

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

本文針對這2個KNN的缺點進行相應優(yōu)化后采用一組腦中風的數據集進行實驗，實驗結果表明，F_KNN算法比傳統(tǒng)KNN算法和上述的C_KNN算法、B_KNN算法準確率更高且速率更快。

1 相關工作

1.1 AHP

層次分析法(The analytic hierarchy process)簡稱AHP，是美國運籌學家托馬斯·塞蒂(T.L. Saaty)在20世紀70年代中期正式提出的。AHP是將與決策有關的因素分解成目標、準則、方案等層次，在此基礎之上進行定性和定量分析的決策方法。將結果作為目標層，各特征向量作為準則層，而后兩兩比較特征向量，構造準則層判斷矩陣，通過不斷實驗，最后得出最恰當的權重分配[16]。

1.2 FLANN

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

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

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

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

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

3)當某個集群內的點數量小于K時，將這些數據節(jié)點作為葉子節(jié)點。

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

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

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

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

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

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

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

1.3 KNN

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

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

圖1 KNN算法流程圖

1)計算測試數據與各個訓練數據之間的距離。

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

3)返回前K個點中出現頻率最高的類別作為測試數據的預測分類。

2 F_KNN算法

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

圖2 F_KNN算法流程圖

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

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

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

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

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

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

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

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

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

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

3 實驗分析

3.1 實驗框架

3.1.1 數據集

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

表1 數據集信息表

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；記錄測試平臺上運行算法的準確率和時間。

3.2 實驗流程

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

圖3 實驗流程圖

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

Step2劃分數據集。對腦中風數據集的5110組數據進行劃分，3577(70%)組數據作為訓練集，1533(30%)作為測試集。

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

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

圖4 特征向量分配圖

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

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

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

4 實驗結果及分析

4.1 對比實驗

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

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

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

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

4.2 實驗分析

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

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

圖5 不同算法準確率對比圖

從圖5可以看出在面對腦中風數據集時，F_KNN表現最為良好，準確率波動不大且一直較高，在K取值為6時達到最大值0.9642。這表明F_KNN算法的分類性能更高，表現更好。

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

F1值[27]是一個綜合評價分類效果的指標，計算公式如下：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個計時器，計算每次代碼運行的時間，用來比較算法的效率。本文選擇當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算法提高了分類準確率且極大提高了分類效率。在處理高維且數據較大的數據集時，優(yōu)化后的KNN算法優(yōu)勢明顯，具有較好的應用前景。

5 結束語

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

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