混合kNN算法在2型糖尿病預(yù)測診斷中的研究

崔波 朱曉軍

摘 ?要： 2型糖尿?。═2DM）原始醫(yī)療數(shù)據(jù)具有廣維度、多噪聲、強耦合、非線性等特點。傳統(tǒng)的kNN算法不能很好地利用全局信息，對異常值也不敏感，并且算法中的近鄰值k以及權(quán)重的確定對于實驗結(jié)果有很明顯的影響，因此，提出一種混合kNN算法（IPCA?kNN）預(yù)測診斷2型糖尿病患者的新型預(yù)測模型。采用ISODATA算法對離散點進行剔除，數(shù)據(jù)集中的缺失值使用隨機加權(quán)熱卡（BB?Hotdeck）算法進行插補;構(gòu)造kNN分類器時使用主成分分析（PCA）對每個屬性賦不同權(quán)重，對于k值的確定使用交叉驗證中的K?fold Cross Validation（K?CV）算法，通過準確度、敏感度和特異度驗證所提模型有效。

關(guān)鍵詞： 2型糖尿病; 預(yù)測診斷; 混合kNN; 數(shù)據(jù)處理; 仿真實驗; 結(jié)果分析

中圖分類號： TN912?34; TP202 ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）20?0164?05

Hybrid kNN algorithm for predictive diagnosis of type 2 diabetes

CUI Bo， ZHU Xiaojun

（Taiyuan University of Technology， Taiyuan 030024， China）

Abstract： The original medical data of type 2 diabetes mellitus （T2DM） has some characteristics， such as wide dimensionality， multi?noise， strong coupling， nonlinearity. The traditional k?Nearest Neighbor （kNN） algorithm can't make good use of the global information and insensitivity to outliers， and the determination of the nearest neighbor value k and the weight in the algorithm has obvious influence on the experimental results. Therefore， a new predictive model of hybrid kNN （IPCA?kNN） algorithm is proposed to predict and diagnose the patients with T2DM. The iterative self?organized data analysis （ISODATA） is used to eliminate the discrete points. The missing values in the data set are interpolated by means of Bayesian Bootstrap?Hotdeck （BB?Hotdeck） algorithm. When constructing the kNN classifier， the principal component analysis （PCA） is used to assign different weights to each attribute， the K?fold cross validation （K?CV） in cross?validation is used to determine the value of K. The validity of the model is verified by accuracy， sensitivity and specificity.

Keywords： Type 2 diabetes; predictive diagnosis; hybrid kNN; data processing; simulation experiment; result analysis

0 ?引 ?言

來自國際糖尿病聯(lián)盟（IDF）的資料顯示，2017年全球共有糖尿病患者4.25億，預(yù)計到2040年這一數(shù)字將上升到6.42億，糖尿病已成為新世紀全球最大的人類健康危機之一[1]。而中國糖尿病患者數(shù)量排第一，其中2型糖尿病約占所有確診的糖尿病成人病例的90%～95%。目前，大多數(shù)分類、鑒定和診斷治療都基于化學(xué)和物理測試，從這些結(jié)果中獲得推論來預(yù)測T2DM。但是，由于用于測試的各種參數(shù)的不確定性，會使預(yù)測產(chǎn)生錯誤，反而可能降低疾病控制和治愈的可能性。根據(jù)N. Esfandiari等人提出的定義 “從醫(yī)學(xué)數(shù)據(jù)中提取隱藏的、具有潛在價值的和新穎的信息，以提高準確性，減少時間和成本，構(gòu)建以健康保護為目的的決策支持系統(tǒng)”[2]。因此，基于機器學(xué)習(xí)和數(shù)據(jù)挖掘的新型預(yù)測模型的構(gòu)建對于2型糖尿病患者早期診斷并隨后提供適當?shù)闹委熓怯葹橹匾摹?/p>

2008年，K. Polat等人已證明kNN是一種思想簡單但十分有效的分類技術(shù)，可以用于糖尿病的分類診斷，并且達到了71.9%的準確度[3]。在此基礎(chǔ)上，2013年，Y. A. Christobel等人使用平均插補方法取代缺失值，提出了一種新的基于類的k最近鄰（CkNN）方法，該方法對糖尿病數(shù)據(jù)分類準確度為78.16%，但是該方法沒有考慮kNN對離群點不敏感、數(shù)據(jù)不平衡等缺點[4]。仲媛等人提出了利用SVM來確定特征的權(quán)重，即基于特征加權(quán)算法FWkNN（Feature Weighted kNN），對準確度有一定的提升，但是無法很好地解決離散點對于預(yù)測準確度的影響。2016年，曾勇等人提出了基于BP神經(jīng)網(wǎng)絡(luò)的自適應(yīng)偽最近鄰分類，考慮BP神經(jīng)網(wǎng)絡(luò)的輸入值時，選擇了計算待測試數(shù)據(jù)點和樣本集中每一類別樣本集中的各個近鄰的距離值[5]。2017年，M. Maniruzzaman等人使用高斯過程分類（GPC）[6]，預(yù)測診斷的準確度為81.97%。本文主要針對kNN算法對離群點不敏感、數(shù)據(jù)不平衡、如何合理選擇k值及確定權(quán)重不足提出改進方法，設(shè)計一種混合kNN算法預(yù)測診斷2型糖尿病患者的新型預(yù)測模型，即IPCA?kNN。預(yù)測診斷模型使用加利福尼亞大學(xué)歐文分校機器學(xué)習(xí)數(shù)據(jù)庫知識庫（UC Irvine Machine Learning Repository）中的Pima印第安人糖尿病數(shù)據(jù)集（Pima Indians Diabetes Dataset），使用準確度（ACC）、敏感度（SE）、特異度（SP），綜合評估了本研究所提出的混合IPCA?kNN分類模型的表現(xiàn)。

1 ?相關(guān)算法介紹

1.1 ?迭代自組織數(shù)據(jù)分析法

常用的K?means算法最早由MacQueen在1967年提出，屬于無監(jiān)督聚類方法，無監(jiān)督的數(shù)據(jù)聚類是一個任務(wù)，將點分配給聚類，同時估計聚類的位置和形狀[7]。本文使用歐幾里德距離測量，改進的K?means算法——迭代自組織數(shù)據(jù)分析法（ISODATA）算法可以設(shè)定指標參數(shù)決定是否進行“合并”或“分裂”，具有自動調(diào)節(jié)最優(yōu)類別數(shù)k的能力，用于檢測數(shù)據(jù)集中離散點，準確度較高。詳細過程如下：

1） 初始化預(yù)期聚類中心、類中最少樣本數(shù)、每個聚類中樣本距離分布的標準差、兩聚類中心的最小距離、每次迭代運算中可合并的最多對數(shù)以及迭代運算次數(shù);

2） 計算各類中樣本的距離指標函數(shù);

3） 判斷各聚類域中的樣本數(shù)目是否符合初始參數(shù)的設(shè)定，調(diào)整聚類中心數(shù)目;

4） 修正各個聚類中心并計算每個聚類域中的樣本與各個聚類中心間的平均距離以及全部樣本與其對應(yīng)的距離中心的總平均距離;

5） 判斷分裂、合并以及迭代運算，重新確定聚類中心數(shù);

6） 重復(fù)迭代，若需要改變初始參數(shù)，則轉(zhuǎn)到步驟1）;若不需要改變則轉(zhuǎn)步驟2）;若為最后一次迭代，則結(jié)束。

1.2 ?隨機加權(quán)熱卡（BB?Hotdeck）算法

熱卡填充法（Hotdeck）插補是隨機地從回答樣本中抽取回答單元來替代缺失數(shù)據(jù)，而隨機加權(quán)通過給每個試驗樣本隨機加權(quán)進行分布參數(shù)和參數(shù)區(qū)間估計，而不需要了解總體分布[8]。BB?Hotdeck算法描述如下：

1） 根據(jù)分類變量將數(shù)據(jù)集分為兩層即0和1，將每層中沒有缺失數(shù)據(jù)的行（row）定義為[Ycom]，而有缺失數(shù)據(jù)的行定義為[Ymiss];

2） 利用隨機加權(quán)法（BB）從[Ycom]中隨機抽取某一行（或某幾行）來替換缺失行，便得到一個完整的數(shù)據(jù)集，從而可以用標準的統(tǒng)計方法來分析該數(shù)據(jù)集;

3） 重復(fù)上述步驟n次，并對n次分析結(jié)果進行綜合分析。

1.3 ?主成分分析（PCA）

數(shù)據(jù)集中的每個屬性（指標）對于預(yù)測診斷都有其意義，但是各個指標的貢獻度未必相同，保留原始數(shù)據(jù)特征采用PCA對每個指標進行加權(quán)，加權(quán)后的數(shù)據(jù)再使用kNN進行分類。PCA算法的原理如下：

1）輸入訓(xùn)練數(shù)據(jù)集 [D=x1，y1，x2，y2，…，][xn，yn]訓(xùn)練集為[Dtr]，測試集為[Dte]，其中[xi∈D]為實例的特征向量，[yi∈Dc1，c2，…，ck]為實例的類別，i=1，2，…，n。

2） 取訓(xùn)練數(shù)據(jù)集構(gòu)造測試樣本矩陣 [X=Dtr= xT1xT2?xTn= x11x12…x1px21x22…x2p????xn1xn2…xnp]，其中，[xij]表示第i組樣本數(shù)據(jù)中的第j個變量的值。

3） 對訓(xùn)練樣本X進行變換得[Y=yijn×p]，其中， [yij= xij， ?對正指標-xij，對逆指標]。

4） 對Y做標準化變換得標準化矩陣[Z=zT1zT2?zTn= z11z12…z1pz21z22…z2p????zn1zn2…znp]，其中，[zij= yij-yjsj]，[yj]，[sj]分別為Y陣中第j列的均值和標準值。

5） 計算標準化矩陣Z的樣本相關(guān)系數(shù)陣 [R= [rij]p×p=ZTZn-1]。

6） 計算特征值 [R-λIp=0] ， 解得p個特征值[λ1≥λ2≥…≥λp≥0]。

7） 求解[Rb= λjb]，得單位向量[b0j=bj||bj||]。

8） 計算[zi= （zi1，zi2，…，zip）T]的m個主成分分量[uij=zTib0j，j=1，2，…，m] ，得到?jīng)Q策矩陣[U=uT1uT2?uTn= u11u12…u1mu21u22…u2m????up1up2…upm]，其中，[ui]為第i個變量的主成分向量。

9） 主成分模型如下：

[F1= u11w1+u21w2+…+uL1wLF2= u12w1+u22w2+…+uL2wL? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? Fm= u1mw1+u2mw2+…+uLmwL]

式中：[F1，F(xiàn)2，…，F(xiàn)m]為分析后得到的m個主成分;[uij]為決策矩陣中系數(shù)。

10） [uij= fijλi，j=1，2，…，m]，其中[fij]為初始因子載荷。

11） 構(gòu)建綜合評價函數(shù)。

[FZ=j=1m（λjk）Fj= a1w1+a2w2+…+aLwL， ? ? ? ? k= λ1+λ2+…+λm]

式中，[a1，a2，…，aL]，即指標[w1，w2，…，wL]在主成分中的綜合重要度。

12） [VZi= j=1Laj]，可得各指標的權(quán)重為[ωi=VZii=1hVZi]。

1.4 ?k最近鄰算法（kNN）

kNN算法由于無需估計參數(shù)、適合多類交叉或重疊分類問題、易于實現(xiàn)等優(yōu)點被廣泛使用各個領(lǐng)域。kNN算法原理如下：

1） 將各指標權(quán)重賦予訓(xùn)練集和測試集，得到新的數(shù)據(jù)集[L=ωix1，y1，ω2x2，y2，…，ωnxn，yn];

2） 計算測試數(shù)據(jù)與各個訓(xùn)練數(shù)據(jù)之間的距離[d（x，y）]，距離公式選擇歐氏距離，并對這些距離從小到大排序，[d（x，y）=k=1nxk-yk2] ;

由圖4和表3可以看出，本文提出的IPCA?kNN新型2型糖尿病預(yù)測診斷模型，對于PID測試集準確度達到91.54%，敏感度達到90.43%，特異度達到94.31%，分類的準確度高于其他部分分類算法，對于2型糖尿病的預(yù)測診斷具有較好的效果，可以作為一種新的預(yù)測模型加以利用。

4 ?結(jié) ?語

糖尿病已成為影響全球居民健康的主要慢性非傳染病之一，其中2型糖尿病的早??期診斷對預(yù)防及治療至關(guān)重要。本文提出一種混合kNN的預(yù)測診斷模型，即IPCA?kNN，用于分類識別T2DM患者。本文提出的模型好處之一是避免了刪除過多的原始數(shù)據(jù)，確保了實驗數(shù)據(jù)的高質(zhì)量，在此基礎(chǔ)上解決了kNN離散點敏感、權(quán)重?zé)o法確定等不足;另一點是，模型使用靈敏度、特異度和準確度共同來評價模型分類性能，通過與其他方法比較，結(jié)果表明本研究所提出的方法性能優(yōu)于其他算法，可以作為預(yù)測診斷T2DM的新型預(yù)測模型。

T2DM的預(yù)測診斷是一個復(fù)雜的問題，因此，在未來的研究中，應(yīng)該再更新更完整的糖尿病數(shù)據(jù)集對本文的新型預(yù)測診斷模型進行測試。其次，可以利用Map?Reduce編程技術(shù)將本文提出的IPCA?kNN算法并行化，提高分類器的效率。

注：本文通訊作者為朱曉軍。

參考文獻

[1] 李詠梅.糖尿病的流行現(xiàn)狀與預(yù)防[J].心理醫(yī)生，2016，22 （31）：266?267.

LI Yongmei. Prevalence and prevention of diabetes [J]. Psychologist， 2016， 22（31）： 266?267.

[2] ESFANDIARI N， BABAVALIAN M R， MOGHADAM A M E， et al. Knowledge discovery in medicine： current issue and future trend [J]. Expert systems with applications， 2014， 41（9）： 4434?4463.

[3] POLAT K， SALIH G?NE， ARSLAN A. A cascade learning system for classification of diabetes disease： generalized discriminant analysis and least square support vector machine [J]. Expert systems with applications， 2008， 34（1）： 482?487.

[4] CHRISTOBEL Y A， SIVAPRAKASAM P. A new classwise k nearest neighbor （CKNN） method for the classification of diabetes dataset [J]. International journal of engineering & advanced technology， 2013， 2（3）： 396?400.

[5] 曾勇，舒歡，胡江平，等.基于BP神經(jīng)網(wǎng)絡(luò)的自適應(yīng)偽最近鄰分類[J].電子與信息學(xué)報，2016，38（11）：2774?2779.

ZENG Yong， SHU Huan， HU Jiangping， et al. Adaptive pseudo nearest neighbor classification based on BP neural network [J]. Journal of electronics & information technology， 2016， 38（11）： 2774?2779.

[6] MANIRUZZAMAN M， KUMAR N， MENHAZUL ABEDIN M， et al. Comparative approaches for classification of diabetes mellitus data： machine learning paradigm [J]. Computer methods and programs in biomedicine， 2017， 152： 23?34.

[7] ZHANG J Y， PENG L Q， ZHAO X X， et al. Robust data clustering by learning multi?metric Lq?norm distances [J]. Expert systems with applications， 2012， 39（1）： 335?349.

[8] 萬讓鑫，吳西良.基于Bayesian Bootstrap小樣本產(chǎn)品性能可靠性評估[J].信息技術(shù)，2012（5）：174?176.

WAN Rangxin， WU Xiliang. Performance reliability assessment based on Bayesian Bootstrap method [J]. Information technology， 2012（5）： 174?176.

[9] 周志華.機器學(xué)習(xí)[M].北京：清華大學(xué)出版社，2016.

ZHOU Zhihua. Machine learning [M]. Beijing： Tsinghua University Press， 2016.

[10] HAN Jiawei， KAMBER M. Data mining concepts and techniques [M]. Waltham： Morgan Kaufmann Publishers， 2012.

[11] BOZKURT M R， YURTAY N， YILMAZ Z， et al. Comparison of different methods for determining diabetes [J]. Turkish journal of electrical engineering and computer sciences， 2014， 22（4）： 1044?1055.

[12] CHRISTOBEL Y A， SIVAPRAKASAM P. A new classwise k nearest neighbor （CKNN） method for the classification of diabetes dataset [J]. International journal of engineering & advanced technology， 2013， 2（3）： 396?400.