比较研究不同的聚类算法

A.J.Patil¹,C.S.Patil²,R.R.Karhe³,M.A.Aher⁴
SGDCOE E&TC学系(Jalgaon),印度马哈拉施特拉邦^{1、2、3、4}

文摘

本文详细研究和比较不同的基于聚类的图像分割算法。传统的硬聚类算法和聚类算法的软聚类算法。我们比较了硬与软模糊c - k - means算法(FCM)算法。克服传统的FCM的局限性我们也研究内核模糊c -意味着详细(KFCM)算法。k - means算法对噪声敏感和离群值,模糊c - k - means称为手段的延伸(FCM)介绍了。FCM数据点可以属于不止一个集群,每个数据点都有属于每个集群的隶属程度。KFCM使用映射函数并给出更好的性能比FCM的噪声损坏的图片。

关键字

集群、分割、k - means, FCM KFCM。

介绍

图像分割是一个数字图像的过程划分成多个部分(像素集,也被称为超像素)。图像分割是提取的要求的一些更有意义的特性来表示图像的地区。图像分割主要是用于定位对象和边界(线,曲线等)的图像。在图像分割中,标签是分配给每个像素进一步用于集团在集群使用标签之间的相似性。聚类分析或聚类过程组对象相似的标签在一个集群和另一组不同的对象或集群。它有许多应用在模式识别、数据挖掘、医学成像、文档检索、分组、机器学习的情况。集群包括几个算法根据没有。迭代、分组相似的对象在一个集群中,其噪声的鲁棒性。实现各种算法获得精确的集群。形成正确的集群是集群的主要任务包括组与小集群成员之间的距离。 Clustering can therefore be called as an multi-objective optimization problem. The appropriate clustering algorithm depends on the input data set and parameter settings which include the distance function to use, maximum no. of iterations, no. of clusters expected. And the proper results are achieved which are calculated on the basis of CAR(cluster accuracy rate).Clustering is actually not an automatic task but it can be called as an iterative process of knowledge discovery or interactive multi-objective optimization. It will often be necessary to modify data preprocessing and model parameters until the result achieves the desired properties.

许多聚类技术或策略实现了其中的两个主要类别的区分硬聚类和软聚类的算法。硬聚类允许数据点只属于一个集群,因此,它被称为硬边界或脆集群。然而,软聚类包括一个软边界数据点可以属于不止一个集群根据距离标准。它是通过使用成员函数来修改聚类算法。传统的聚类方法把一些限制的图片可能贫穷之下,强度重叠,有限的空间分辨率、噪声和强度变化异同。所以,为了克服这个任务的软聚类算法在实践中使用。硬聚类算法的k - means算法类型。这个算法的目的是将一个给定的数据集,数据点在同一集群是相似的,不同集群的数据点是彼此不同的。鉴于Macqueen于1967年,是一个最简单的无监督学习算法,解决著名的聚类问题。k - means算法是集群的要求应该是重叠的。 K-means is simple and easy to implement and thus it is practically used in many image clustering applications. It classifies a given data set through a certain no. of clusters (assume k clusters) fixed a priori. The idea is to define kcentroids one for each cluster. These cluster centroids should be correctly placed. So, they should be placed far as possible to obtain the correct result. The technique to overcome the drawbacks of hard clustering algorithms is the soft clustering algorithms. In Soft clustering algorithms, the data point can belong to more than one cluster which depends on distance criteria. Fuzzy clustering is the type of soft boundary clustering where adata point belongs to more than one cluster. In fuzzy clustering a membership function is used for distance measure and it lies approximately between 0 and 1. In hard clustering, data is divided into different clusters, where each data object belongs to only one cluster and either a 0(do not belong to the cluster) or 1 (belong to the cluster) is assigned to specify that whether the data point belong to the cluster or not. In fuzzy clustering, the data elements can belong to more than one cluster, and each element is associated with a set of membership levels. It is an iterative algorithm which finds the solution of the objective function and depending on initialization it can find more than one solution. These indicate the strength of the association between that data element and a particular cluster. Fuzzy clustering is a process of assigning these membership levels, and then using them to assign data objects to one or more clusters. The conventional k-means and the FCM (fuzzy c-means) both are sensitive to noise and the outliers and hence advancements in fuzzy clustering are done by introducing a mapping function in KFCM (kernel fuzzy c-means).So, the Euclidian distance is replaced by kernel tricks. An overview and comparison of different fuzzy clustering algorithms is involved. In this paper we will see the drawbacks of the k-means clustering algorithm which are overcame by our FCM (Fuzzy c-means) clustering algorithm. The rest of this paper is organized as follows. Section II gives the literature survey. Section III reviews the hard clustering technique which is the K-means clustering algorithm. Section IV describes the soft clustering algorithm the fuzzy c- means algorithm. Section V gives the detailed study of KFCM (kernel fuzzy c-means) algorithm Section VI compares the clustering results and section VII concludes the clustering algorithms.

文献调查

即使有一个聚类方法的使用兴趣不断增强模式识别(Anderberg1973),图像处理(耆那教徒和弗林1996)和信息检索(Rasmussen 1992;索尔顿海1991],集群在其他学科有丰富的历史(1988年Jain和配音),如生物学、精神病学、心理学、考古学、地质学、地理学、销售。k - means方法被认为是一个最流行的和标准的聚类方法。k - means的目标是将一个给定的数据集,数据点在同一集群相似和不同集群的数据点是不同的。它还要求集群重叠。满足上述需求的聚类算法分为脆聚类算法数据聚类方法。另一方面,算法,允许每一个数据点被指派给一个以上的集群分为模糊聚类方法。模糊c均值方法,提出在邓恩(1973)和改善Bezdek(1981),是一种模糊聚类方法,类似于k - means方法。k - means方法和模糊c均值方法可以被应用变化或改进措施毛和耆那教的不同选择的距离(1996)林德et al。(1980) Banerjee et al .(2005),并且可以与其他聚类技术相结合,例如,内核方法Zhang et al。(2003),达到更好的结果根据聚类问题的本质。

k - means算法

k - means聚类是一种矢量量化方法,被称为最好的聚类算法为基础的平方误差。k - means聚类的目标是开始一个初始分区和提供模式集群,这样的像素强度之间的误差属于集群和均值得到减少。这是通过增加了没有。的迭代。为了减少影响初始分区可以多次运行该算法使用不同的随机生成的初始分区,可以选择最好的其中最小的总距离的平方。

最简单、最常用的算法,采用平方误差准则是k - means算法。该算法将数据划分成K集群(C1, C2…CK),由中心或手段。每个集群计算的中心的意思是属于该集群的所有实例。k - means算法适用于超球面和紧凑的集群。这可能被视为一种gradient-decent过程,始于一组初始的K群集中心和迭代更新,以减少误差函数。T K - means算法的迭代执行的复杂性的样本量m实例,每个N的特征属性,是:O (T * K * m * N)。这个线性复杂度的原因之一的k - means算法。即使实例的数量大大大k - means可用于集群大型数据集,该算法在计算上有吸引力。因此,k - means算法优势相比其他聚类方法(如分层聚类方法)、非线性复杂性。k - means算法总结如下:

输入:n对象(点)和k。

算法:

步骤1。随机地方K点所代表的对象的空间集群。这些初始化集群的重心。

步骤2。将每个数据对象分配给该集团最近的重心。

步骤3。当所有对象分配k质心的位置重新计算。

步骤4。重复步骤2和3,直到满足停止条件。

k - means算法的停止准则如下:

“1。没有改变所有的集群成员。

2。当平方误差小于一些小阈值α平方误差Se是由,

其中mi是所有实例的集群cj意味着什么

Se (j) <α。所以,k - means完全达到局部最优,而不是全局最优。随着k - means是典型的划分聚类算法只适用于各向同性集群的数据集。此外,该算法对噪声很敏感和离群值这意味着即使对象是很远的重心仍被视为在集群和集群扭曲了形状的k - means不能保证收敛到全局最优的迭代优化过程。使用k - means算法往往局限于数值属性。

Haung(1998)提出了K-prototypes算法,基于k - means算法但删除数值数据的局限性,同时保留其效率。该算法和数字集群对象和分类属性的方式类似于k - means算法。数值属性的相似性度量方法是平方欧氏距离;分类属性的相似度测量的数量不匹配对象和集群原型。另一个分区算法,试图最小化SSE, K-medoids或PAM(分区medoids左右)。这种算法非常类似于k - means算法。它不同于后者主要在表示不同的集群。每个集群由集群中的最中心的对象,而不是通过隐式意味着可能不属于集群。K-medoids方法比k - means算法更健壮的噪声和异常值的存在,因为medoid受异常值影响较小。但是这个过程与k - means算法相比更加昂贵。 While k-means as well as k-medoids both need to specify the no. of clusters k.

模糊c均值算法

最著名的模糊聚类算法是FCM(模糊c),由Bezdek修改,改进原来的脆或k - means聚类算法。Bezdek改善集群的形成通过包括模糊性参数(M)的范围(1,N),这决定了集群的模糊程度。M = 1时称为脆点的聚类。当M > 1分中模糊性决定空间的程度增加。

在FCM,给定一个数据集的大小为n, X = {x1,…, xn}和FCM组X到c集群通过最小化加权数据和集群中心之间的距离定义为:

uij数据xj属于集群的成员我。FCM迭代更新原型(o1、o2、…、oc)和会员uij通过以下方程:

这个迭代停止,直到老会员的区别值和更新新的足够小。最后根据结果uij,我们分配数据xj到集群k, Uik是最大的成员值在所有uij (i = 1 c)。

模糊c允许数据点被分配到多个集群每个数据点都有一定程度的属于每个集群成员(或概率)。模糊c是一个非常重要的工具,图像处理在聚类对象在一个图像。传统的聚类算法是每个数据对象的分区算法只属于单独的集群。因此,集群在k - means是脱节的。模糊聚类(Hoppner, 2005)这一概念进行了扩展,提出了一个软聚类模式。在这里,模式是由隶属函数给每个集群。的分配模式集群大成员值提供了更好的性能。在一个模糊聚类得到这个会员的阈值时硬聚类可以被检索。

最受欢迎的模糊聚类算法的模糊c均值(FCM)算法。FCM提供良好的结果比硬但避免局部最小值的k - means算法收敛到局部最小值的平方误差准则。模糊聚类中最重要的问题是选择有许多模糊隶属函数的选择基于相似分解和集群重心。的目标函数提出了一种泛化的FCM算法。模糊的或关于一种集理论和逻辑谓词可能程度的适用性,而不是简单的真或假。模糊集的模糊逻辑的逻辑;一个模糊集潜在无限的真理valuesbetween 0和1。模糊聚类的中心思想是唯一的部分数据簇的集合。

FCM算法如下:

步骤1。初始化U = [ujj]成员矩阵,U (0)

步骤2。在k-step:计算中心向量C (k) = (cj)与U (k),

步骤3。更新U (^k),U (^{k + 1})

步骤4。如果| | U (^{k + 1 >})−U^k| | <∈然后停止;否则返回步骤2。

FCM算法应该指定以下参数集群的数量,c,“模糊性”指数,m,终止宽容,,norm-inducing矩阵、模糊划分矩阵U,必须初始化。

的决心。集群c,更重要的是对分区相比具有更大的影响和其他参数。当集群真实数据没有任何先验信息的数据结构,

一个通常假设底层集群的数量。然后选择聚类算法搜索c集群,不管他们是否出现在数据相关。两种主要的方法来确定。集群的有效措施和集群的迭代合并或插入。有效性措施标量指数评估了分区的美好。集群融合的基本思想是首先数量足够大的集群,并先后通过合并减少这个数字集群是相似的(兼容)对一些定义良好的标准。加权指数m是一个相当重要的参数,因为它大大影响结果的模糊性分区。从以上m方法1,分区变硬(μik∈{0,1})和vi是普通的集群。作为米→∞,分区变得完全模糊(μik = 1 / c)和集群意味着都等于Z的意思。

FCM算法停止迭代的标准U在连续两次迭代之间的差异小于终止参数。最大准则矩阵通常选用0.001,即使0.001 workswell在大多数情况下,减少计算时间复杂度。常见的选择是一个=我,给标准欧几里得范数。规范影响集群通过改变不同的衡量标准。欧几里得范数的诱发超球面集群(超球体表面恒定的会员)。对角线和规范生成超椭球集群。

内核模糊c均值

传统的FCM是柔软的扩展c均值聚类。每个集群被认为是模糊集和隶属函数措施的可能性,每个训练向量属于一个集群。所以,向量可能分配到多个集群。因此,它克服了硬聚类的一些缺点但它是有效的只有当数据重叠。因此,我们使用基于模糊c均值算法(KFCM)。在KFCM,数据和集群中心从原始空间映射到一个新的空间∅,所以,给出目标函数如下:

用目标函数,

因为我们知道k,新问显式,我们可以优化。

内核模糊c均值(KFCM)算法如下:

步骤1。修复c、达峰时间、m > 1> 0,一些积极的常数。

步骤2。初始化成员、C、m。

步骤3。在t = 1、2、…………,达峰时间

(一)更新所有原型与方程,

集群中心词可以获得:

与方程(b)更新所有会员,

会员U矩阵可以得到:

聚类结果

原始图像是图像合成测试图像,与两类灰色水平值0到255。我们有损坏它15%的盐和胡椒噪音和FCM和KFCM获得的结果。

不同的聚类算法的聚类结果如图2所示。FCM(模糊c)和KFCM(内核模糊c -意味着)算法相比,通过两幅图像合成测试图像和大脑图像和相应的聚类结果如图2和图3所示。

图2说明了聚类结果的图像原始图像(无花果。2 (a)],损坏的图像(无花果。2 (b)], FCM的结果(无花果。2 (c)], KFCM结果(无花果。2 (d)]。

从图2我们可以观察到,FCM和KFCM提供了图像分割,即使图像是破坏,噪音降低到多少程度相比,损坏的图像。FCM消除了噪声给图像的聚类结果和KFCM减少噪音的程度比FCM和提供了更好的聚类。

下一个图像是大脑的形象。在这幅图像高斯噪声3%添加到原始图像和FCM和KFCM观察结果。

在这方面,原始图像(无花果。3(a)], is the image of a brain then it is corrupted by 5% Gaussian noise [Fig.3 (b)], and the clustering results obtained are shown in [Fig.3 (c)] and [Fig.3 (d)]. From the results we can observe that the clustering accuracy of KFCM is better than FCM. Thus, we can see from the above two experiments that by using a mapping function the KFCM gives better performance when compared with the FCM.

结论

集群技术大多是无监督的方法可以用来组织数据分组基于单个数据项之间的相似之处。大多数clusteringalgorithms并不取决于假设匹配传统统计方法,如统计数据的分布。因此,在先验知识的情况下存在了非常重要的作用。在本文中,我们讨论了硬k - means算法允许更好的效率,但对噪声和离群值更敏感。软聚类算法引入了一个向量表达的百分比指向每个集群的归属感。FCM(模糊c)可能收敛速度比k - means,但计算复杂度也在不断增加。FCM工作在数据重叠的情况。对于非线性版本的FCM KFCM给出更好的结果。它不需要预先所需数量的集群;它决定了集群的数据的数量和收益更好的性能比FCM的噪音。 Hence the clustering algorithms had many applications in segmentation, magnetic resonance, imaging (MRI), analysis of network traffic, Fourier transform infrared spectroscopy (FTIR).

数据乍一看


图1	图2	图3

引用

帕拉维·埃呀尔Thakur ChelpaLingam,“广义空间基于内核的模糊c均值聚类图像分割的算法,“IJSR卷,2期2013年5月。
杨Y。,Zheng Ch., and Lin P., "Fuzzy c-means Clustering Algorithm with a Novel PenaltyTerm for Image Segmentation", Opto-Electronics Review, Vol.13, No.4, Pp.309-315, 2005.
Bezdek J.C.“模式识别与模糊目标函数算法”一个¯¼充气出版社,纽约,1981年。
j·c·邓恩,“模糊ISODATA过程及其使用的相对检测紧凑,布置得井然有序集群,”j .控制论3卷,32-57,1973页。
吴Z,谢,W。X Yu J.P.“模糊c均值聚类算法基于内核法”:学报第五国际会议上计算智能和多媒体应用,Pp 49-56, 2003。
SteliosKrinidis VassiliosChatzis,”一个健壮的当地信息模糊c均值聚类算法”,IEEE图像处理,19卷,2010年5月5号。
Gimiami M,在特征空间聚类”为核心的“美世的内核,IEEE神经网络,13卷,3号,pp780 - 784, 2002。
李应Chun-yan Yu Ai-lian Liu Jing-hong Liu“小说修改内核模糊c均值聚类算法在图像分割”,IEEE计算机科学与工程国际会议CSE /跨/ IUCC 2011。
Anderberg m R。,1973年。聚类分析的应用。学术出版社。
普拉特W。,1991年。数字图像处理,约翰威利& Sons,纽约。
科尔曼·g·b·h·c·安德鲁斯,1979。“聚类图像分割”,Proc IEEE 67:773 - 785。
程,h . D, x h .江y .太阳和j·王,2001年。彩色图像分割:进展和前景,模式识别,Vol.34, 2259 - 2281。
y . c . Liaw j . z . c .赖,w . Lo”使用分类矢量量化压缩图像的图像恢复,”模式识别、35卷,2002年,页181 - 192。
j . z . c .赖、t·j·黄和y . c . Liaw”快速k - means聚类算法使用群集中心位移,“模式识别,42卷,2009年,页2551 - 2556。
r . l .大炮j . v .戴夫,j . c . Bezdek”模糊c均值聚类算法的高效实现,”IEEE PAMI, 8卷,1986年,页248 - 255。