崔波 朱曉軍

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

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

中圖分類號(hào)： TN912?34; TP202 ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ?文章編號(hào)： 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 ?引 ?言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 ?主成分分析（PCA）

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

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

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

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

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

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

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

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

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

9） 主成分模型如下：

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

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

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

11） 構(gòu)建綜合評(píng)價(jià)函數(shù)。

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

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

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

1.4 ?k最近鄰算法（kNN）

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

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

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

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

4 ?結(jié) ?語(yǔ)

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

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

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

參考文獻(xiàn)

[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é)報(bào)，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] 萬(wàn)讓鑫，吳西良.基于Bayesian Bootstrap小樣本產(chǎn)品性能可靠性評(píng)估[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] 周志華.機(jī)器學(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.