K近邻算法在医学影像中的应用

　　一、 K近邻算法基本概念
　　K-近邻算法（KNN, K-Nearest Neighbor）是模式识别中最古老的机器学习方法之一。KNN算法能够灵活地融合不同类型的数据，并且能够适应不规则的特征空间。在模式识别这个领域中， k 最近邻算法（KNN）是一种主要用于分类以及回归的非参数统计方法 ，是一种惰性学习的算法。惰性学习在最开始的时候不会根据已有的样本创建目标函数,只是简单的把训练用的样本储存好,后期需要对新进入的样本进行判断的时候才开始分析新进入样本与已存在的训练样本之间的关系,并据此确定新实例(新进入样本)的目标函数值。KNN分类的基本原理如下图所示，
　　图3.4.1 K近邻算法原理图
　　上图中，所有样本可以使用一个二维向量表征。图中，蓝色方形样本和红色三角形样本为已知分类样本。若使用KNN对图中未知分类样本A进行分类，当K=3时，其三近邻中有2个红色样本和1个蓝色样本，因此预测该待分类样本为红色样本；当K=5时，其三近邻中有3个红色样本和2个蓝色样本，因此预测该待分类样本为蓝色样本。
　　KNN算法有以下几个要素：数据集 （data set）；样本的向量表示 （Vector representation of samples），即不管是当前已知的样本数据集，还是将来可能出现的待分类样本，都必须可以用向量的形式加以表征。样本的向量表现形式，构筑了问题的解空间，即囊括了样本所有可能出现的情况。向量的每一个维度，刻画样本的一个特征，必须是量化的，可比较的；样本间距离的计算方法 （The calculation method of sample distance），包括欧式距离， 余弦距离,曼哈顿距离
　　K是一个重要参数，当k选不同值时会产生不同的结果。通常，k值的设定采用交叉检验的方式（以k=1为基准）
　　选择较小的K值，就相当于用较小的领域中的训练实例进行预测，＂学习＂近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是＂学习＂的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
　　选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
　　K=N（N为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。
　　在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。
　　二、 K近邻算法在医学影像中的应用
　　KNN算法在医学图像处理领域应用更加广泛，对于乳腺癌的检测、脑部图像分类与检测
　　以及脑卒中检测有着很好的分类效果。主要是应用于医学图像分类包括MRI分类、指纹真假识别、心率检测分类等。
　　1、基于 K -最近邻规则的磁共振颅脑图像分割算法
　　一种简单实用的磁共振颅脑图像分割算法 K-最近邻( 简称 K-NN) 规则, 并利用该算法对磁共振颅脑图像进行分割研究。首先利用边界跟踪法对磁共振颅脑图像进行预处理, 将 MRI 图像转换为二值图像，利用边界跟踪得到大脑结构的边界线，根据边界线提取大脑结构，剔除颅骨和肌肉等非脑组织, 只留大脑结构。
　　图3.4.2用边界跟踪法进行预处理
　　然后利用 K-NN 规则对大脑结构进行分割, 根据解剖学的知识, 从原始图像的不同区域 中选取部分象素并给出标记作为训练样本, 把该训练样本记作集合，
　　确定未分象素 z 的最近邻数k 的值，选择欧氏距离 d 作为距离测度，对每个未分类像素 z 进行归类处理,即根据像素间的欧氏距离基于简单多数投票原则对像素分类到即 WM 、GM 、CSF 和背景四个区域中。分割算法在预处理步中能精确地分割出大脑结构, 在 K-NN 分割步中能很好地从大脑结构中分割出白质(WM) 、灰质(GM) 和脑脊液(CSF)。
　　图3.4.3 用KNN算法进行分割
　　2、利用K近邻算法对视网膜眼底图像微动脉瘤进行自动检测
　　糖尿病性视网膜病变(DR)是导致新失明的主要原因之一。早期准确地发现微动脉瘤对糖尿病视网膜病变的诊断和分级具有重要意义。然而，眼科医生手动诊断糖尿病患者是一项耗时的工作，而且容易出错。因此，糖尿病患者视网膜的自动分析是眼科医生筛查更大人群的迫切需要。微动脉瘤是糖尿病视网膜病变的重要病变。在眼底图像中，MAs表现为微小血管附近的小而圆的点。它们可能是唯一的病变，存在于DR的最早阶段，并在疾病的发展过程中一直存在。因此，在计算机辅助筛选系统中MAs的检测是必不可少的。
　　提出了一种眼底图像中MAs（微动脉瘤）的自动检测方法。该方法包括四个主要步骤:预处理、候选特征提取、特征提取和分类。在KNN分类器中提取了27个包含局部特征和轮廓特征的特征，用于区分真MAs和伪MAs。该方法已在两个公共数据库(ROC和e-optha)上进行了评估。实验结果证明了该方法的有效性和有效性，具有应用于临床诊断的潜力。
　　图3.4.5 预处理流程
　　视网膜眼底图像往往是光照不均匀、对比度差和噪声图像。MAs在低亮度和低对比度区域几乎不可见。为了减少这些缺陷，制作出适合MA候选图像和特征提取的图像。文章采用了照明均衡、限制对比度的自适应平均直方图和降噪三个步骤对原始图像进行了预处理。 接着进行候选提取步骤在整个检测过程中起着重要的作用。该步骤的主要目标是减少与MAs不相似的对象的数量。但是，在这一步中丢失的任何真实的MAs都不能在以后恢复。
　　Lazar提出的特征源自剖面分析。本文将这些特征定义为轮廓特征。并添加了三个新的轮廓特征来提高性能。但这些剖面特征不能很好地反映MAs的整体特征。因此也研究了MA及其周围环境，并提出在分类中加入局部特征。因此，在该分类器中，除了形状和强度特征与 轮廓特征外，还使用了局部特征。
　　最后将第二步中提取到的特征用一个27维的特征向量来表示，然而，不同的特征fi具有不同的范围和值，这对于一些分类器来说是不利的。这些特征的均值和单位方差都归一化为，其是特征向量的均值，是标准差。为了为特征集选择合适的分类器，我们选择了三个监督分类器作为底层分类器:K近邻(K Nearest Neighbor ,KNN)、朴素贝叶斯(Naive Bayes ,NB)和Adaboost。在ROC数据库上测试了这三个分类器。结果表明，KNN (k = 14)和Adaboost有相似的性能，都优于NB分类器。文章选择KNN (k = 14)分类器进行分类，分类效果如下图所示。
　　图3.4.6 三种分类器的ROC曲线