论文部分内容阅读
数据所表征的归属类是在数据之间复杂联系的背后隐藏的一种难以被人们发现的模式。目前,已经有很多种聚类分析的方法被用在数据挖掘中来分析这种模式,这些方法各有利弊,有一些算法已经付诸实践。K均值就是其中一种简单易行的算法,但是该算法却存在着很多弊端。K均值算法中需要由用户来确定待聚类的个数K,而且初始的聚类中心也有很大的不确定性,这就导致了该方法具有不稳定性且容易陷入局部最优解,而得不到全局最优解。图像分割是实现视觉理解的基础,但由于图像结构和内容不同,要实现快速通用的图像分割仍然是一个难题。聚类分析可以在图像没有先验知识时进行初步分割。基于聚类分析的图像分割方法对样本空间的约束小,分割算法的通用性好。无论是灰度图像、彩色图像分还是纹理图像,都可以应用聚类分析方法完成分割。但是基于聚类分析的分割方法还不完善,主要因为聚类分析计算量大,存在极值问题和对噪声样本敏感。对上述K均值方法存在的问题进行了研究,利用K均值方法对于数据二分的结果较为稳定的特点,设计并实现了并行二分K均值算法。该算法调用K均值对数据按照细胞分裂的方式进行切分,构建一棵满二叉树,当叶子结点数超过数据的类别数时对叶子结点进行部分合并,进而获得最终的聚类结果在此过程中,并且把并行二分K均值方法应用于图像分割。本文的研究工作主要要包括以下几方面:(1)用并行二分K均值方法与已经有的二分K均值方法进行对比实验,实验证实并行二分K均值相比于二分K均值具有较低的时间复杂度和较好的聚类效果。并行二分K均值方法保留了K均值方法处理大规模数据的优点并且比其时间复杂度更低。通过实验结果表明,并行二分K均值算法具有较高的运行效率,比K均值,二分K均值更适合于处理大规模数据。(2)把并行二分K均值算法用于图像分割领域上,和传统的K均值算法做了对比实验,实验结果表明:在图像分割效果相当的情况下,并行二分K均值算法比K均值算法的处理时间降低了25%。实验证明,本文提出的算法是快速有效的,在获得较好图像分割结果的同时,比一般算法耗时更少。