徐秀芳+徐森+徐静+安晶

摘 要：提出了一种改进的K均值算法用于X光片图像聚类。首先对X光片图像进行预处理，获取数据，然后将每个点的灰度值存储在灰度值矩阵中，最后用改进的K均值算法对灰度值矩阵进行聚类。对比实验结果表明，改进的K均值算法获得了更加优越的聚类结果。

关键词：X光片；K均值；聚类分析；簇中心；灰度

DOIDOI：10.11907/rjdk.162084

中图分类号：TP317.4

文献标识码：A文章编号：1672-7800（2016）012-0156-03

0 引言

随着科技在医学领域的应用，传统的放射诊断学成为医学影像的重要部分。X线摄影是临床最常用的医学检查方法，几乎适用于人体任何部位，它具有空间分辨率高、图像清晰、层析分明的特点，常用作医学诊断的辅助工具[1-3]。然而，由于在X光片成像时三维人体被显示为二维图像，所以人体器官显示会出现重叠和失真现象。通过将聚类分析技术应用于X光片数据，可为观察者提供更多信息，降低重叠和失真带来的影响[4]。

本文提出一种快速有效的X光片图像聚类算法，通过改进K均值算法的初始值选取方法，有效提高了聚类效果。对比实验表明，本文算法获得的聚类结果明显优于传统的K均值算法。

1 改进的K均值算法

X光片具有数据量巨大、数据点分布稀疏、存在大量近似点（灰度相同的点）的特性，所以并不是所有聚类方法都会产生比较好的结果。X光片图像数据存在大量数据点，导致进行聚类分析的算法时间复杂度和空间复杂度不能太高，否则消耗的时间和占用的内存会难以承受。

1.1 K均值聚类

在所有聚类算法中，K均值算法适应范围广泛，针对X光片图像数据而言，类与类之间区别明显，在处理大数据集时，算法时间和空间复杂度都表现良好。K均值用质心定义原型，一般情况下数据点属性的平均值被定义为质心。大部分情况下，一个簇中不仅包含一个数据点，中心点是一组点中最具代表性的点[1]。K均值聚类可以用于各种数据类型，因为只需要对象之间的邻近性度量。

K均值算法执行前，需要指定K值，K值表示希望从对象中得到簇的个数。算法开始执行时首先需要将每个点划分到距离最近的簇中。将所有点划分完后，计算每个簇的簇中心。重复划分所有点到最近的簇，并计算簇中心位置，直到簇不再变化。具体算法如下：①指定K个点作为初始质心；②Repeat；③将每个点指派到最近的质心，形成K个簇；④重新计算每个簇的质心；⑤Until；⑥质心不再变化。

其中，K均值算法中的第③步如下，流程如图1所示：

①Repeat；②比较数据点到每个簇中心的距离；③将数据点划分到距离其最近的数据中心；④Until；⑤每个数据点都被划分到了最近的簇中。

K均值算法中的第④步如下，流程如图2所示：

①Repeat；②数据点所在簇的簇内点数量加1；③数据点所在簇的总灰度=总灰度+数据点的灰度；④Until；⑤所有的数据点都被计算；⑥将每个簇的总灰度除以簇内点的数量得到簇的平均灰度。

K均值算法优点是适用范围广，当簇与簇之间聚类较远差异较大时，数据维度较低的数据点分布相对密集，效果要好些。对于处理大数据集，这个算法较高效。

计算的时间复杂度为O（NKt），其中N是数据对象数目，t是迭代次数。一般来说，K≤N，t≤N。K均值算法的空间复杂度需求不高，只需要存放数据点和质心。具体所需要的存储空间为O（（m+k）n），其中m是对象数量，n是属性数。

K均值算法缺点主要有：①算法执行前需要人为设定簇的个数，但是簇的个数常常难以估计；②在K均值算法中每一次对数据点进行划分都是由上一次划分得到的簇中心决定的，所以K均值算法的最终结果是由最初选取的簇中心决定的。选择不适当的数据点作为初始的簇中心（比如彼此靠得很近的数据点），就可能导致最后结果偏差。因此初始值的选取成为K均值算法无法回避的问题。目前为止，还没有发现一个适应范围很广的初始值选取方法；③K均值算法需要在一次次迭代中不断修改簇中心，每次修改后都需要将所有点重新划分。当数据量很大时，这样的操作十分消耗时间。所以，在面对海量数据计算时需要改进算法，以降低时间复杂度；④K均值算法的聚类划分特性，决定了它在处理非球状簇、不同尺寸、不同密度簇时，结果令人不满意，而且K均值算法受离群点和噪声的影响较大。

1.2 改进的K均值算法

本文首先对X光片进行预处理，然后从图片中获取数据，获得图像中每个点的灰度值，存储在灰度值矩阵G中。Gij表示图像中第i行、第j列点的灰度。对数据点进行聚类后，可以将处于同一个簇的点用同一种颜色在图片上标出，从而进行直观判断。

由于K均值算法的聚类结果受初始簇中心影响极大，簇中心选取错误会导致很差的集成结果，所以k个初始簇中心选取至关重要。本文改进了传统K均值算法，流程如图3所示，主要步骤如下：①随机选取1个簇中心；②Repeat；③再随机选取1个簇中心；④比较选取的簇中心和之前选取的簇中心灰度值是否相同；⑤若相同则重新选取并回到步骤④；⑥Until；⑦簇中心的个数达到k个；⑧Repeat；⑨计算每个点到各个簇中心的距离；⑩找出每个点到各个簇中心的最短距离；B11将点划分到相应簇中，并修改Lij的值；B12重新计算每个簇的中心；B13Until；B14每个簇的中心都不再变化。

在k个初始簇中心选取比较理想的情况下，k个聚类中心均匀地分布在图像的数据点中，此情况下获得的聚类结果会比较理想。此时，K均值算法和改进的K均值算法获得的聚类结果基本一致。

在k个初始簇中心选取较差的情况下，K均值算法会得到“空簇”，产生较差的聚类结果，而改进的K均值算法不会遇到这种问题。当出现相同灰度值的簇，这个簇中心会被重新选取，从而使得每个簇中都会有一定数量的数据点，保证了迭代能正常进行。

2 实验

选取一张X光片作为原始数据，如图4所示。使用改进的K均值算法得到的结果如图5所示。原始的K均值算法聚类结果受初始值影响较大，时好时坏，在初始簇中心选取到灰度值相同的点时就会出现如图6所示的情况，有比较多的空簇。如图7所示的聚类结果仅在初始簇中心选择较好，没有发生簇中心重叠的情况下才会出现。

改进的K均值算法虽然在k个初始簇中心选取上作了改进，使彼此不会有相同的灰度值，但这并不保证k个点会均匀地分布在所有数据点中，如果k个点彼此聚类比较近，仍会对簇的结果造成影响。

3 结语

本文提出了一种快速有效的X光片图像聚类算法，通过改进K均值算法的初始质心选取，有效提高了聚类效果。对比实验显示，本文提出的算法获得的聚类结果明显优于传统的K均值算法，验证了算法的有效性。

参考文献：

[1] 史盛君，宋立新，赵阳.基于神经网络的乳腺X光片中肿块检测法[J].哈尔滨理工大学学报，2008，13（6）：101-104.

[2] 王彦明，钱建忠，潘晨.基于SVM-2DPCA的X光胸片异常筛查[J].计算机工程， 2009， 35（18）：170-172.

[3] 董亮，朱磊，苗凤娟，等.基于DM642的X光片医学辅助诊断系统[J].电子技术应用， 2012， 37（7）：129-131.

[4] PANG NING TAN，MICHALE STEINBACH.数据挖掘导论[M].北京：人民邮电出版社，2011.

[5] 孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报， 2008，19（1）：48-61.

（责任编辑：杜能钢）