陳彬嫣 唐德玉

摘要：由于傳統(tǒng)kNN算法在不平衡數(shù)據(jù)中的分類誤差較大，故結(jié)合DBscAN算法、熵權(quán)法以及密度可達的思想，生成動態(tài)k值來改進KNN算法（ded-kNN）。以甲狀腺疾病為例用MATLAB編程驗證其在疾病預(yù)測中的應(yīng)用，結(jié)果表明，改進的算法分類性能得到很大提高。

關(guān)鍵詞：甲狀腺疾病;kNN算法;密度可達;疾病預(yù)測

中圖分類號：TP301 文獻標識碼：A 文章編號：1006-8228（2020）07-80-04

0引言

甲狀腺疾病是一種常見的由促甲狀腺激素水平異常引起的內(nèi)分泌系統(tǒng)疾病，患病人數(shù)占20%～50%，在內(nèi)分泌領(lǐng)域?qū)儆趦H次于糖尿病的第二大疾病。甲狀腺功能的實驗室檢查主要是通過測定促甲狀腺激素（TSH）、三碘甲狀腺原氨酸（T3）以及甲狀腺激素（T4）等指標來發(fā)現(xiàn)并根據(jù)臨床經(jīng)驗診斷出大部分甲狀腺疾病。由此可見，診斷過程摻雜著醫(yī)生的主觀判斷，不同的醫(yī)生的知識儲備和臨床經(jīng)驗有差異，勢必會造成一定的誤診率。本文提出一種ded-KNN算法，能有效克服傳統(tǒng)算法在不平衡數(shù)據(jù)分類中的局限，為醫(yī)生在甲狀腺疾病的診斷劃分中提供寶貴建議，對實現(xiàn)計算機輔助醫(yī)療診斷有一定的現(xiàn)實意義。

1傳統(tǒng)K-NN算法

K-NN（K-NearestNeighbor）算法，即K-鄰近算法是一種簡單有效的惰性分類算法。早在1968年，該算法由Cover和Hart研究提出，其基本思想是：通過選擇合適的距離函數(shù)分別計算出待測樣本與訓(xùn)練集中每一個樣本的距離，并選擇與待測樣本距離最小的K個訓(xùn)練樣本進行投票，票數(shù)最高的類別作為待測樣本的最終預(yù)測類別。近年來，基于其簡單有效且易于理解的特點，K-NN算法在人臉識別、文本分類還有醫(yī)學(xué)圖像識別與分類等熱門領(lǐng)域都得到了比較成功的應(yīng)用。

傳統(tǒng)的K-NN算法在多分類問題上具有獨特的優(yōu)勢，但也存在著明顯的不足，主要表現(xiàn)為：計算量大，分類速度慢;當樣本數(shù)據(jù)不平衡時，預(yù)測結(jié)果會偏向于多數(shù)類，影響少數(shù)類分類的正確率;計算距離時所有屬性都是同等重要的，缺乏區(qū)分度;K值的選取沒有統(tǒng)一標準。

2改進K-NN算法的研究

2.1 DBSCAN算法簡介

DBSCAN（Density-Based Spatial Clustering ofApplication with Noise）算法是一種典型的基于密度的聚類算法，在DBSCAN算法中，有兩個人為設(shè)定的參數(shù)：Eps鄰域和鄰域內(nèi)包含的最少對象數(shù)MinPts。根據(jù)設(shè)定的參數(shù)，DBSCAN算法通常將數(shù)據(jù)點分為三類：①核心點：在半徑Eps內(nèi)含有超過MinPts數(shù)目的點。②邊界點：在半徑Eps內(nèi)的數(shù)量小于MinPts，但是落在核心點的領(lǐng)域內(nèi)的點。③噪聲點：既不屬于核心點也不屬于邊界點的點。

2.2熵權(quán)法簡介

熵權(quán)法是確定指標權(quán)重的一種客觀評價法，通過比對待評價對象的各個指標在競爭意義上的激烈程度來確定該指標在決策問題上所能提供的有效信息的多寡，信息量越大，該指標越重要，權(quán)重就越大，從而客觀的計算出各個指標的權(quán)值。具體步驟如下。

3ded-KNN算法

本文在研究過程中嘗試結(jié)合了DBSCAN算法和熵權(quán)法，改進后的算法能夠減少一定的數(shù)據(jù)樣本并且克服傳統(tǒng)算法對屬性缺乏區(qū)分度的缺點，分類性能有所提高。但由于本文的算法主要針對不平衡數(shù)據(jù)，期望在精準率和召回率上取得更理想的結(jié)果，因此在上述方法的改進基礎(chǔ)上，提出了ded-KNN算法。

3.1基于密度可達的思想生成動態(tài)K值

傳統(tǒng)的K-NN算法對測試樣本進行分類時，為每個測試樣本分配K個最近鄰來進行投票選擇，大大影響了不平衡數(shù)據(jù)的準確率。黃雪原在2018年提出了基于密度可達的思想生成動態(tài)K值的改進方法嘲，其原理是對傳統(tǒng)K-NN算法生成的K個近鄰依次做密度可達檢測，若通過檢驗，則將該樣本加入新的動態(tài)K近鄰集，否則視為噪聲，將其剔除，最終對動態(tài)K近鄰集進行投票選擇，票數(shù)最多的類別為待測樣本的最終類別。本文參考其改進原理，為每一個待測樣本生成個性化的K值。實驗表明，動態(tài)的K近鄰集能更高效地對不平衡數(shù)據(jù)進行分類。

密度可達檢測主要依靠樣本平均密度以及類內(nèi)密度實現(xiàn)，下面對這些概念做出詳細的解釋：

（1）樣本平均密度

平均樣本密度表示數(shù)據(jù)集中每個樣本與其周圍樣本的距離疏密程度，其計算見式（3）：其中m表示每個樣本計算平均樣本密度的周圍樣本數(shù)，本文研究的數(shù)據(jù)患病類與非患病類的比例約為l：3，因此設(shè)置m為3。dij表示距離第i個樣本從小到大排列的樣本中，第i個與原來樣本之間的距離值。

（2）類內(nèi)密度

類內(nèi)密度是在樣本平均密度的基礎(chǔ)上每個類別的類內(nèi)平均密度，并以此作為后續(xù)操作中K個近鄰密度可達檢測的對應(yīng)類閾值。其計算見式（4）：

其中ni表示第i個類別所含的樣本個數(shù)，meanj表示第i個類別中每個樣本的平均密度。

（3）動態(tài)K近鄰集

將原始的K近鄰中篩選出與其對應(yīng)類別處在相同樣本密度范圍的y個近鄰組合成每個待測樣本的動態(tài)K近鄰集，并將其余近鄰視為噪聲然后剔除。

3.2算法的描述

根據(jù)上述方法的原理，本文結(jié)合了DBSCAN算法、熵權(quán)法和基于密度可達的思想生成動態(tài)K值，改進了傳統(tǒng)K-NN算法，即ded-KNN算法。以下描述算法。

（1）對原始數(shù)據(jù)進行數(shù)據(jù)預(yù)處理后，利用DBSCAN算法剔除噪聲數(shù)據(jù)。

（2）將剔除噪聲后的數(shù)據(jù)作為新的原始數(shù)據(jù)，采用熵權(quán)法計算出每一項指標的權(quán)重并且對每一條數(shù)據(jù)即每個患者的甲狀腺疾病診斷記錄進行加權(quán)處理。

（3）計算出加權(quán)后的數(shù)據(jù)集中每個樣本的樣本平均密度，并以此為依據(jù)計算出各個類別的類內(nèi)密度。

（4）根據(jù)本文測試數(shù)據(jù)的不平衡性，篩選每一類疾病樣本的1/10作為測試集，剩余作為訓(xùn)練集。

（5）計算測試集中每一個待測樣本分別與訓(xùn)練集中每個樣本的歐氏距離，并選出K個最小距離的樣本組成原始K近鄰集。

（6）以（3）中算出的類內(nèi)密度作為閾值，來判斷K個近鄰是否與其對應(yīng)的類密度可達，是則將該近鄰加入動態(tài)K近鄰集，否則將其視為噪聲點剔除。

（7）對每個待測樣本的動態(tài)K近鄰集進行投票選擇，得票最多的類別作為待測樣本的類別。

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

本文選用UCI網(wǎng)站的甲狀腺數(shù)據(jù)集，由于大部分數(shù)據(jù)庫中的屬性相同，本文將五個小數(shù)據(jù)集與thyroid0387進行合并整理，得到12944條診斷記錄。每條記錄包括29個屬性值和一個診斷情況，以診斷情況作為分類標準。經(jīng)過數(shù)據(jù)預(yù)處理，共得到數(shù)據(jù)12387條，選取每個類別的1/10作為測試集，剩余的為訓(xùn)練集。

為了區(qū)分改進過程中的不同算法，將只用DBSCAN算法剔除噪聲點的稱為DBSCAN-KNN算法，結(jié)合DBSCAN算法和熵權(quán)法的稱為DEntropy-KNN算法，在DEntropy-KNN算法基礎(chǔ)上綜合了基于密度可達思想生成動態(tài)K值方法的稱為ded-KNN算法。以K=3時為例，分步改進的三種算法與傳統(tǒng)K-NN算法對比結(jié)果如表1所示。

為了更直觀的看出每種算法的分類性能，接下來將用折線圖展示傳統(tǒng)K-NN算法與改進過程中的三種K-NN算法在不同K值下準確率、精準率、召回率以及F1值的對比。

通過圖1～圖4可以發(fā)現(xiàn)，改進的K-NN算法在相同的數(shù)據(jù)集上較傳統(tǒng)的K-NN算法在準確率、精確率、召回率以及F1值上均有一定程度的提高，其中ded-KNN算法的效果最佳，尤其在召回率的提升上效果顯著，很好地解決了傳統(tǒng)算法對于不平衡數(shù)據(jù)分類的誤差問題。說明本文提出的ded-KNN算法在甲狀腺疾病預(yù)測上有一定的優(yōu)勢，可以作為一種新的預(yù)測模型在臨床醫(yī)療上加以利用。

5結(jié)束語

隨著數(shù)據(jù)時代的到來，醫(yī)療事業(yè)也在全力加速實現(xiàn)數(shù)據(jù)化，然而現(xiàn)實中的醫(yī)療數(shù)據(jù)往往是分布不均的不平衡數(shù)據(jù)，這對現(xiàn)有分類算法在不平衡數(shù)據(jù)的容忍程度上提出了重大的挑戰(zhàn)。本文提出的ded-KNN算法在對甲狀腺疾病預(yù)測中取得了良好的結(jié)果，有效克服少數(shù)類分類誤差的問題，對臨床上疾病預(yù)測和醫(yī)生輔助治療有一定的現(xiàn)實意義。

盡管本文提出的ded-KNN算法能夠有效降低不平衡數(shù)據(jù)在分類問題上帶來的負面影響，但對于分類算法的優(yōu)化工作而言還存在進步空間，醫(yī)學(xué)數(shù)據(jù)總是龐大且復(fù)雜，因此分類效率是非常重要的，鑒于時間與水平有限，本文剔除噪聲后速率提升并不明顯。因此在未來對算法的改進工作中可以針對醫(yī)學(xué)數(shù)據(jù)的特性研究如何快速且有效的找到K個近鄰，避免重復(fù)計算，減少算法的計算開銷。