陳彬嫣 唐德玉

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

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

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8228（2020）07-80-04

0引言

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

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

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

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

2改進(jìn)K-NN算法的研究

2.1 DBSCAN算法簡介

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

2.2熵權(quán)法簡介

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

3ded-KNN算法

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

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

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

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

（1）樣本平均密度

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

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

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

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

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

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

3.2算法的描述

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

5結(jié)束語

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

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