论文部分内容阅读
摘要：由于传统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个近邻，避免重复计算，减少算法的计算开销。
关键词：甲状腺疾病;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个近邻，避免重复计算，减少算法的计算开销。