dedi-kNN算法在甲狀腺疾病預測中的研究

陳彬嫣 唐德玉

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

關鍵詞：甲狀腺疾病;kNN算法;密度可達;疾病預測

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

0引言

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

1傳統K-NN算法

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

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

2改進K-NN算法的研究

2.1 DBSCAN算法簡介

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

2.2熵權法簡介

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

3ded-KNN算法

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

3.1基于密度可達的思想生成動態K值

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

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

（1）樣本平均密度

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

（2）類內密度

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

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

（3）動態K近鄰集

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

3.2算法的描述

根據上述方法的原理，本文結合了DBSCAN算法、熵權法和基于密度可達的思想生成動態K值，改進了傳統K-NN算法，即ded-KNN算法。以下描述算法。

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

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

（3）計算出加權后的數據集中每個樣本的樣本平均密度，并以此為依據計算出各個類別的類內密度。

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

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

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

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

4實驗結果及分析

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

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

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

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

5結束語

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

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