一种改进的K-means聚类算法在图像分割中的应用

k-means算法

一．算法简介

k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。

二．划分聚类方法对数据集进行聚类时包括如下三个要点：

（1）选定某种距离作为数据样本间的相似性度量

k-means聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。

假设给定的数据集 ，X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid),

xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分别是样本xi和xj对应d个描述属性A1,A2,…Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。

欧式距离公式如下：

（2）选择评价聚类性能的准则函数

k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；|1,2,...,mXxmtotal21,dijikjkkdxxxx

各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。

数据挖掘课程报告

聚类分析K-means算法综述

摘 要 ：介绍 K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。

关键词 ：K-means聚类算法 基本步骤 优化方法 应用领域 研究方向 应用发展趋势

算法概述

K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含 n个数据对象的数据库，输出满足方差最小标准的k个聚类。

评定标准 ：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。

解 释 ：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。

k-means 算法基本步骤

（1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心

（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分

（3） 重新计算每个（有变化）聚类的均值（中心对象）

（4） 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2）

形式化描述

输入：数据集D，划分簇的个数k

输出：k个簇的集合

（1） 从数据集D中任意选择k个对象作为初始簇的中心；

（2） Repeat

（3） For数据集D中每个对象P do

（4） 计算对象P到k个簇中心的距离

（5） 将对象P指派到与其最近（距离最短）的簇； 数据挖掘课程报告

（6） End For

（7） 计算每个簇中对象的均值，作为新的簇的中心；

（8） Until k个簇的簇中心不再发生变化

对算法已有优化方法的分析

(1)K-means算法中聚类个数K需要预先给定

这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标： V(kkm) = Intra(k) + Inter(k) /

泰山医学院学报　ＪＯＵＲＮＡＬ　ＯＦ　ＴＡＩＳＨＡＮ　ＭＥＤＩＣＡＬ　ＣＯＬＬＥＧＥ　Ｖｏ１．２７　Ｎｏ．６　２００６　

改进的ＫＮＮ算法及其在医学图像处理中的应用　

王清，马华，孙静，韩忠东　

（泰山医学院信息工程学院，山东泰安２７１０１６）　

摘要：目的　利用最近邻ＫＮＮ算法对ＭＲ图像分割时，要靠人的经验从图像中选出部分像素作为训练样本，本　文就是为了减少人的劳动并且使算法自动进行。方法　用速度快的ｋ一均值聚类算法得到的聚类中心作为参考，将　与之相近的部分像素作为训练样本。此外，在应用ＫＮＮ方法前，还利用边界跟踪法剔除人脑ＭＲ图像中颅骨和肌肉　等非脑组织，避免非脑组织对大脑结构分割的干扰。结果　能较好地将ＭＲ图像分割出脑白质、灰质、脊髓三部分图　像。结论实验表明，改进的ＫＮＮ方法减少了对人工的参与，并且取得了很好的分割效果。　关键词：ＫＮＮ算法；Ｋ一均值聚类；磁共振成像；图像分割　中图分类号：ＴＰ３９１．４１文献标识号：Ａ文章编号：１００４－７１１５（２００６）０６－０５６４－０３　

Ｍｏｄｉｆｉｅｄ　Ｋ—－ＮＮ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　Ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　Ｍｅｄｉｃａｌ　Ｉｍａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ　

ＷＡＮＧ　Ｑ垤，ＭＡ　Ｈｕａ，ＳＵＮ　Ｊｉｎｇ，／／ＡＮ　Ｚｈｏｎｇ一幽凡ｇ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔａｉｓｈａｎ　Ｍｅｄｉｃａｌ　Ｃｏｌｌｅｇｅ，Ｔａｉａｎ　２７１０１６）　

Ａｂｓｔｒａｃｔ：Ｏ￣ｅｃｆｉｖｅ：ｗｈｅｎ　ｍａｇｎｅｔｉｃ　ｒｅｓｏｎａｎｃｅ（ＭＲ）ｉｍａｇｅｓ　ａｒｅ　ｓｅｇｍｅｎｔｅｄ　ｂｙ　ｋ—ｎｅａｒｅｓｔ　ｎｅｉｉｇｈｂｏｒ（ＫＮＮ）ａｌｇｏ—　ｒｉｔｈｍ－ｉｔ　ｉｓ　ｎｅｃｅｓｓａｒｙ　ｔｏ　ｓｅｌｅｃｔ　ｓｏｍｅ　ｐｉｘｅｌｓ　ａｓ　ｔｒａｉｎｉｎｇ　ｓａｍｐｌｅｓ　ｔｈｒｏｕｇｈ　ｈｕｍａｎ　ｅｘｐｅｒｉｅｎｃｅ．Ｉｔ　ｉｓ　ｄｉｓｃｕｓｓｅｄ　ｔｏ　ａｌｌｅｖｉａｔｅ　ｈｕｍａｎ　ｌａｂｏｒ　ａｎｄ　ｍａｋｅ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｃｅｅｄ　ａｕｔｏｍａｔｉｃａｌｌｙ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｍｅｔｈｏｄｓ：Ｓｏｍｅ　ｐｉｘｅｌｓ，ｒｅｆｅｒｒｉｎｇ　ｔｏ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｃｅｎｔｅｒｓ　ｏｂｔａｉｎｅｄ　ｂｙ　ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ，ａｒｅ　ｒｅｇａｒｄｅｄ　８８　ｔｒａｉｎｉｎｇ　ｓａｍｐｌｅｓ．Ｉｎ　ａｄｄｉｔｉｏｎ，ｂｅｆｏｒｅ　ＫＮＮ　ｍｅｔｈｏｄ　ｉｓ　ａｐｐｌｉｅｄ，　ｅｄｇｅ—ｔｒａｃｉｎｇ　ｍｅｔｈｏｄ　ｉｓ　ｕｓｅｄ　ｔｏ　ｍｏｖｅ　ｔｈｅ　ｎｏｎ—ｂｒａｉｎ　ｔｉｓｓｕｅｓ－ｓｕｃｈ　ａｓ　ｓｋｕｌｌ　ａｎｄ　ｍｕｓｃｌｅ，ｉｎ　ｏｒｄｅｒ　ｔｏ　ａｖｏｉｄ　ｔｈｅ　ｎｏｎ—ｂｒａｉｎ　ｔｉｓｓｕｅｓ　ｂｅｒｉｎｇ　ｉｍａｇｅ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｆｏｒ　ｂｒａｉｎ　ｓｔｒｕｃｔｕｒｅ．Ｒｅｓｕｌｔｓ：Ａ　ＭＲ　ｉｍａｇｅ　ｃａｎ　ｂｅ　ｓｅｇｍｅｎｔｅｄ　ｉｎｔｏ　ｔｈｒｅｅ　ｑｕａｌｉｔｙ　ｉｍａｇｅｓ：ｇｒａｙ　ｍａｔｔｅｒ（ＧＭ）。ｗｈｉｔｅ　ｍａｔｔｅｒ（ＷＭ）ａｎｄ　ｃｅｒｅｂｒｏｓｐｉｎａｌ　ｆｌｕｉｄ（ＣＳＦ）ｔｈｒｏｕｇｈ　ｍｅｔｈｏｄｓ　ｕｓｅｄ　ｉｎ　ｔｈｅ　ｐａｐｅｒ．Ｃｏｎｃｌｕｓｉｏｎ　Ｔｅｓｔｓ　ｓｈｏｗ　ｍｏｄｉｆｉｅｄ　ＫＮＮ　ｍｅｔｈｏｄ　ｃａｎ　ｂｅ　ｉｎｄｅｐｅｎｄｅｎｔ　ｏｆ　ｍａｎｕａｌ　ｗｏｒｋ　ａｎｄ　ｏｂｔａｉｎ　ｇｏｏｄ　ｓｅｇｍｅｎｔａｔｉｏｎ　ｒｅｓｕｌＬ　Ｋｅｙ　ｗｏｒｄｓ：ｋ—ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒ　ａｌｇｏｒｉｔｈｍ，ｋ—ｍｅａｎｓ　ｃｌｕｓｔｅｒｉｎｇ，ｍａｇｎｅｔｉｃ　ｒｅｓｏｎａｎｃｅ　ｉｍａｇｉｎｇ（ＭＲＩ），ｉｍａｇｅ　ｓｅｇｍｅｎ—　ｔａｔｉｏｎ　

K-Means聚类算法

K-Means聚类算法是一种常用的无监督学习算法，在数据挖掘、图像处理、信号处理等领域有广泛的应用。聚类算法是将相似的对象归为一类，不同的类之间尽可能的不相似。K-Means聚类算法是一种基于距离测量的算法，它将数据点分为K个簇，每个簇的中心点与相应的数据点之间的距离最小。

1.初始化K个簇的中心点。

2.将每个数据点分配到离它最近的簇中。

3.计算每个簇的新中心点。

4.重复步骤2和3，直到簇的中心点不再发生变化或达到预定的循环次数。

在算法中，K是指聚类的簇数，每个簇的中心点是从数据点中随机选择的。在第二个步骤中，每个数据点会被分配到离它最近的簇中，这一步是K-Means聚类算法最重要的一步。在第三个步骤中，每个簇的新中心点是通过计算该簇中所有数据点的平均值得到的。

1.简单易懂：K-Means聚类算法实现简单，易于理解。

2.计算速度快：该算法的时间复杂度为O(K*n*I)，其中n是数据点的数量，I是迭代次数，因此算法速度较快。

3.可用于大规模数据：K-Means聚类算法可以处理大规模的数据集。

1.对初始值敏感：算法中随机选择簇的中心点，这会影响聚类结果。如果初始值不理想，聚类结果可能会很糟糕。

2.需要指定簇数：需要事先指定簇的数量K，这对于有些问题来说可能是一个难点。

3.对数据分布的要求较高：K-Means聚类算法对数据分布的要求较高，如果数据分布不太符合预期，聚类结果可能会非常差。

在实际应用中，K-Means聚类算法可以用于数据挖掘、模式识别、图像分割等领域。例如，在图像处理中，可以使用K-Means聚类算法将像素分为不同的颜色组。在信号处理中，可以使用K-Means聚类算法将信号分为不同的频段组。实际应用中，需要根据具体问题来选择聚类算法。