文档视界 最新最全的文档下载
当前位置:文档视界 > 基于聚类分析的图像分割研究毕业论文

基于聚类分析的图像分割研究毕业论文

毕业论文声明

本人郑重声明:

1.此毕业论文是本人在指导教师指导下独立进行研究取得的成果。除了特别加以标注地方外,本文不包含他人或其它机构已经发表或撰写过的研究成果。对本文研究做出重要贡献的个人与集体均已在文中作了明确标明。本人完全意识到本声明的法律结果由本人承担。

2.本人完全了解学校、学院有关保留、使用学位论文的规定,同意学校与学院保留并向国家有关部门或机构送交此论文的复印件和电子版,允许此文被查阅和借阅。本人授权大学学院可以将此文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本文。

3.若在大学学院毕业论文审查小组复审中,发现本文有抄袭,一切后果均由本人承担,与毕业论文指导老师无关。

4.本人所呈交的毕业论文,是在指导老师的指导下独立进行研究所取得的成果。论文中凡引用他人已经发布或未发表的成果、数据、观点等,均已明确注明出处。论文中已经注明引用的内容外,不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究成果做出重要贡献的个人和集体,均已在论文中已明确的方式标明。

学位论文作者(签名):

年月

关于毕业论文使用授权的声明

本人在指导老师的指导下所完成的论文及相关的资料(包括图纸、实验记录、原始数据、实物照片、图片、录音带、设计手稿等),知识产权归属华北电力大学。本人完全了解大学有关保存,使用毕业论文的规定。同意学校保存或向国家有关部门或机构送交论文的纸质版或电子版,允许论文被查阅或借阅。本人授权大学可以将本毕业论文的全部或部分内容编入有关数据库进行检索,可以采用任何复制手段保存或编汇本毕业论文。如果发表相关成果,一定征得指导教师同意,且第一署名单位为大学。本人毕业后使用毕业论文或与该论文直接相关的学术论文或成果时,第一署名单位仍然为大学。本人完全了解大学关于收集、保存、使用学位论文的规定,同意如下各项内容:按照学校要求提交学位论文的印刷本和电子版本;学校有权保存学位论文的印刷本和电子版,并采用影印、缩印、扫描、数字化或其它手段保存或汇编本学位论文;学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务;学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入学校有关数据库和收录到《中国学位论文全文数据库》进行信息服务。在不以赢利为目的的前提下,学校可以适当复制论文的部分或全部内容用于学术活动。

论文作者签名:日期:

指导教师签名:日期:

毕业设计(论文)题目:基于聚类分析的图像分割研究

毕业设计(论文)原创性声明

本人郑重声明:所提交的毕业设计(论文),是本人在导师指导下,独立进行研究工作所取得的成果。除文中已注明引用的内容外,本毕业设计(论文)不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体,均已在文中以明确方式标明并表示了谢意。

论文作者签名:

日期:2014年6月2日

第一章绪论 (1)

1.1图像分割的背景及意义 (1)

1.2图像分割的研究现状 (3)

1.3本文的主要工作 (5)

第二章聚类分析理论 (7)

2.1 聚类分析概述 (7)

2.2 常见的聚类算法 (12)

2.3 模糊聚类算法 (14)

2.4图像分割方法 (16)

2.5本章总结 (18)

第三章基于K-means算法的图像分割方法 (19)

3.1RGB颜色空间 (19)

3.2定义和概述 (19)

3.3 简单的例子介绍 (21)

3.4 k-means图像分割 (23)

3.5改进的k-均值聚类图像分割算法 (27)

3.6本章总结 (31)

第四章基于FCM算法的图像分割 (32)

4.1模糊聚类的概念 (32)

4.2FCM算法的概述 (34)

4.3本章总结 (43)

总结与展望 (44)

5.1总结 (44)

5.2研究展望 (45)

结束语 (46)

致谢 (47)

参考文献 (48)

附录A (52)

基于K-means算法的matlab源程序 (52)

附录B (54)

基于K-均值聚类改进前的matlab源程序 (54)

附录C (57)

基于FCM聚类算法的matlab源程序 (57)

在飞速发展的信息时代,图像是人类获取信息的重要手段之一,因而图像的处理就变得极其重要。而图像分割通常是为了进一步对图像进行分析、识别、跟踪、理解、压缩编码等,分割的好坏直接影响后期的图像识别和理解。

图像分割是指将一幅图像分解成若干互不相交区域的集合,其实质是一个像素的聚类过程。本文以图像分割的聚类实质为线索,对近几年国内外最新的图像分割算法进行了分析比较,指出了聚类在这个领域的重要性。本论文针对聚类算法在图像分割中的应用,主要涉及了以下几个内容:

(1)详细介绍当前图像分割以及聚类分析的研究背景,现状。

(2)对基于模糊K均值的图像分割算法进行探讨,并对K均值算法进行改进,通过粗糙集理论提供 K-均值聚类所需要的初始类的个数和均值,提高了聚类的效率和分类的精度。

(3)对基于标准模糊 C 均值聚类的图像分割算法进行了探讨,研究了基于模糊聚类的图像分割方法中初始类别数的选取、初始类中心和初始隶属度矩阵的确定等问题。

(4)将基于模糊K均值的图像分割算法与基于标准模糊 C 均值聚类的图像分割算法进行对比分析。

关键词:聚类分析,模糊聚类,图像分割,K均值算法,C均值算法

ABSTRACT

The rapid development in the information age , the image is an important means of human access to information , and thus the image processing becomes extremely important. And the image segmentation of the image is usually performed to further analysis, identification , tracking , understanding , compression , etc., directly affects the post- split image recognition and understanding.Image segmentation refers to the collection of an image is decomposed into several disjoint regions , and its essence is a pixel clustering process . In this paper, image segmentation clustering substantive clue , at home and abroad in recent years, image segmentation algorithms are analyzed and compared , pointed out the importance of clustering in this field . This thesis clustering algorithm for image segmentation , mainly related to the following elements :

( 1 ) a detailed description of current research background image segmentation and clustering analysis of the status .

( 2 ) image segmentation algorithm based on fuzzy K-means were discussed , and the K-means algorithm is improved , providing the initial class and the mean number of K- means clustering required by rough set theory , improve the efficiency of clustering and classification accuracy.

( 3 ) the standard image segmentation algorithm based on fuzzy C -means clustering were discussed , studied to select the initial number of categories based on fuzzy clustering method of image segmentation , determining the initial cluster centers and the initial membership matrix of other issues.

( 4 ) the segmentation algorithm for image segmentation algorithm based on fuzzy C-means clustering standard comparative analysis based on K-means fuzzy image .

Keywords: cluster analysis , fuzzy clustering , image segmentation , K -means algorithm , C -means algorithm

第一章绪论

在当前快速发展信息化时代,通过图像来获取信息是人类认识世界改造世界的重要方式之一,由此看来图像的处理就变得十分重要1。图像处理(image processing),用计算机对图像进行分析,以达到所需结果的技术。又称影像处理。基本内容图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组,该数组的元素称为像素,其值为一整数,称为灰度值。图像处理技术的主要内容包括图像压缩,增强和复原,匹配、描述和识别3个部分2。常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。其中图像分割的目的是为了后续对图像进行分析、识别、跟踪、理解、压缩编码等,分割的准确性直接影响后续任务的效果,具有极其重要的意义。所以本课题将研究方向确定在利用图像分割技术来进行图像的识别3。

1.1图像分割的背景及意义

聚类分析研究有很长的历史,几十年来,其重要性及其研究方向的交叉特性得到人们的肯定。聚类分析是数据挖掘研究方向的重要研究内容之一,在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是从上世纪80年代开始发展起来的一门交叉学科,涉及到数据库、统计学、人工智能和机器学习多个领域。计算机的应用普及产生了大量数据,数据挖掘就是利用上述学科的技术进行大量的数据处理。数据挖掘的应用范围非常的广泛,从农业生产的预测到基因分类,从信用卡欺诈到税务稽查,数据挖掘技术对未来社会的各个领域将起到越来越大的作用4。

在一副图像中,我们在通常情况下只是对其中的某些目标感兴趣,它们通常在要分割的图像中占据一定的区域,而且在某些特性上与周围的图像存在一定的差别。这些差别有时候可能是特别明显的,也有可能是非常微小的,以至于人的肉眼无法察觉的到的。图像分割是按照一定的制约规则把图像划分为若干个互不相交,具有特定性质的区域,是把我们关注的区域从需要分割的图像中提取出来,从此进行进一步研究和处理的技术。它使得其中的图像分析和识别等处理过程中所要处理的数据量大大减少了,同时有保留了有关图像结构特征的信息。图像分割的结果是图像特征提取和识别等图像理解的基础,对图像分割的研究一直是数字图像处理技术的焦点和热点。关于图像分割的概念有很多,但最终都归于一个基本思想,即图像分割时根据实际需求与应用,按照指定特征信息,对图像中有意义的边界、兴趣区域或者对相一致的区域(灰度、颜色、纹理等)进行分解和

提取的技术和过程5。

图像分割的数学解释:假定一幅图像中所有像素的集合为F ,有关均匀性的假设为()P ?。分割定义把F 划分为若干子集{}12,,,n S S S L ,其中每个子集都构成一个空间连通区域。用四个条件进行数学描述,即6:

①1n

j j S F ==U ;

②(),j i S S i j =?≠I ;

③()(),j P S TRUE j =?;

④()(),i j P S S FLASE i j =≠U 。

式中,?为空集。

图像分割的重要性,可以从图像工程的三个层次来理解,如图1.1所示。图像工程是指对图像进行采样、量化、编码、传输、增强、边缘检测、分割、形态分析、目标识别、目标表达等一系列的加工处理、分析和理解的综合工程技术。 图像工程根据抽象程度和研究方法的不同分为三个层次:图像处理、图像分析和图像理解。而图像分割是图像识别和图像理解的基础,分割的好坏结果直接影响到后期的识别和理解7。

基于聚类分析的图像分割研究毕业论文

图1.1图像分割在图像工程中的位置

图像分割在实际中也已得到广泛的应用,例如在工业自动化,在线产品检验,以及军事、体育、农业工程等方面8。概括来说,在各种图像应用中,只要需对图像目标进行提取,测量等都离不开图像分割。 图像分割技术的发展与许多其它学科和领域,例如数学、物理、心理学、电子学、计算机科学等学科密切相关。近年来,随着各学科许多新理论和方法的提出,人们也提出了许多结合一些特定

理论、方法和工具的分割技术9。每当有新的数学工具或方法提出来,人们就试着将其用于图像分割,因而提出了不少特殊的算法。例如利用马尔可夫随机场、数学形态学、模拟退火、遗传算法、聚类分析。新的分割算法还在不断涌现。其中,基于聚类分析的图像分割方法是图像分割领域中一类极其重要和应用相当广泛的算法,其在应用领域取得的巨大成功引起了广大关注10。

1.2图像分割的研究现状

基于聚类分析的图像分割方法是图像领域中一类极其重要和应用相当广泛的算法,无论是灰度图像分割、彩色图像分割还是纹理图像或者其他类型的图像分割,都可运用聚类分析方法11。聚类是把具有相似性质的事物区分开并加以分类,它是运用数学方法对处理给定对象的进行分类。聚类问题是一个古老的问题,是伴随人类的产生和发展而不断深化的一个问题,有关聚类分析的理论和应用的研究己有大量的文献。经典分类学是从单个因素或有限几个因素出发,凭经验和专业知识对事物分类,这种分类具有非此即彼的特性,分出的类别界限很清晰。随着认识的深入,发现这种分类不适用于具有模糊性的分类问题,如图像中的区域之间的边界就往往是模糊不清的。模糊数学的产生为上述软分类提供了数学基础,由此产生了模糊聚类分析12。用普通数学方法进行分类的聚类法称为普通聚类分析,而把应用模糊数学方法进行分析的聚类分析称为模糊聚类分析。由于图像技术本身的复杂性和相关性,在图像处理过程中出现了不确定性和不精确性。这种不确定性和不精确性主要体现在图像灰度的不确定性、几何形状的不确定性和不确定性知识等。这种不确定性是经典的数学理论无法解决的,并且这种不确定性不是随机的,因而不适于用概率论来解决13。因为模糊理论对于图像的这种不确定性有很好的描述能力,所以可以引入模糊理论作为有效描述图像特点和人的视觉特性的模型和方法。近年来一些学者致力于将模糊理论引入到图像处理中,取得很好的效果,经过专家学者几十年的研究,图像的模糊处理技术获得极大的发展。基于模糊理论的图像分割方法主要可分为模糊阈值分割和模糊聚类分割。图像分割的实质简单地说是一个按照像素属性(灰度,纹理,颜色等)聚类的过程14。因此,聚类分析就广泛应用于图像分割之中。其中模糊聚类分割方法是最先提出、也是最经典的一种图像模糊分割方法。本文中基于聚类分析的图像分割算法主要是针对模糊聚类算法应用于图像分割中的介绍和研究。实际中应用最为广泛的模糊聚类方法是模糊C-均值算法(Fuzzy C-Means),简称FCM,本文中的模糊聚类算法也特指模糊C均值算法15。FCM算法首先是由Ruspini提出的,但真正有效的方法是由Dunn给出的。1974 年Dunn将硬C-均值聚类算法

推广到模糊情形,同年,Bezdek将Dunn的方法一般化,建立了模糊C-均值聚类理论。1980 年Bezdek又证明了模糊C-均值聚类算法的收敛性,并讨论了模糊C-均值聚类算法与硬C-均值聚类算法的关系16。从此,基于目标函数的模糊聚类方法蓬勃发展起来,目前从不同的角度对基于目标函数的模糊聚类方法进行研究,归纳起来主要集中在以下四个方面:模糊聚类新方法的研究、实现途径的研究、聚类有效性的研究和模糊聚类的应用研究。 FCM 算法采用迭代法优化目标函数来获得对数据集的模糊分类,算法具有很好的收敛性。采用模糊 C-均值聚类的方法进行图像分割的优点是避免了设定阈值的问题,并且能解决阈值化分割难以解决的多个分支的分割问题。FCM 适合于图像中存在不确定性和模糊性的特点,同时 FCM 算法是属于无监督的分类方法,聚类过程中不需要任何人工的干预,很适合于自动分割的应用领域17。利用FCM算法进行图像分割主要有以下难点和问题:

聚类类别数C的确定

在聚类进行之前必需给定类的数目,否则聚类无法进行。在实际应用中,尤其是自动化的系统中这是不太现实的。均值聚类方法中最困难的是图像分割的类别数的确定。

初始类中心初始隶属度矩阵的确定

模糊聚类分割方法必须给出初始聚类中心和确定初始隶属度矩阵。根据数学分析理论任何一个迭代并且最后收敛的序列,如果迭代的初始值比较接近于最后的收敛结果的话,收敛的速度会明显提高,迭代次数也会较大幅度地减小。同时,也因为接近最后结果陷入其它局部最优的可能性减小。另外,如果聚类迭代的初始值接近于某个局部极值的话,就很有可能最终陷入局部极值,从而得不到全局最优值,所以FCM算法对初始值相当敏感。在没有任何先验知识也没有任何辅助手段的情况下,系统可以采用随机选取类中心的办法。但那样就过于盲目,而且很容易陷入局部最优迭代,收敛速度可能很低,迭代的次数也可能会增加很多,这样也就会增加计算时间。所以初始参数的确定,对于计算量的降低显得尤其重要。然而目前尚无有效的理论指导,如何选择合适的聚类初始值仍然是一个难题。迭代过程中的大计算量问题

由于聚类是一个非线性优化过程,聚类迭代算法在一般情况下收敛速度较慢。图像分割是一个样本量很大的分类问题,尤其当特征空间是多维空间时(如彩色图像分割时的三维颜色空间聚类时)迭代算法中计算量过大而且只能串行,耗时很多,基于模糊聚类的计算量就更大了,使得FCM算法的实际应用具有一定的局限性,更不用说实时应用了。为了解决模糊聚类中大计算量的问题,降低计算时间,人们一般从三个方面来考虑:选择接近最后结果的初始值,尽可能地减少迭代的次数;改进算法,减少每一轮迭代的计算量;设计快速的实现算法。丁

震等人提出了一种针对模糊聚类的快速二值化方法,该方法将图像映射到灰度特征空间,然后在特征空间中进行聚类,显然特征空间中灰度级是很少的,而图像的像素则是大样本集,这样一来计算量大幅度降低,分割质量也还可以。但是该算法只适用于将图像分割成目标和背景两类的灰度图像应用。

空间信息的使用

模糊均值聚类方法分割的另一个问题是它只考虑到了灰度特征或彩色图像的色特征,忽略了图像中固有的丰富的空间信息,从而导致它对噪声比较敏感,而且使得分割出的区域往往不连续,导致本属于同类的像素没有连在一起,不能形成有意义的子图。如何有效地利用空间信息,提高分割质量,同时又不至于大幅增加计算量是一个很有意义的研究课题。

聚类的后处理的问题

由于模糊聚类法分割是一般都没有有效地利用图像像素之间的空间关系信息,容易导致分割出来的区域可能不连续;另一个分割时类别数未必是正确的,往往有过分割的可能。于是一般在聚类完成后对分割出的结果需要进行一些合并类的后处理,使得最后分割出的区域都是有意义的。针对模糊聚类FCM存在的这个问题,Ray等人提出了一种基于解微分方程的曲线进化的方法,该方法利用截集理论来演变分割图中的几何曲线,进而描述图像的区域。该方法不失为一种较好的后处理方法,它排除了分割图中的不连续性,使得各区域之间的边界是封闭和连续的。但该方法的边界曲线演变过程的计算复杂度很高,非常耗时;它存在的另一个问题是后处理过程可能会产生新的分割错误。然而,好的后处理方法应该分析聚类后存在的各种不同的问题,然后采用不同的方法进行处理,既要降低计算复杂度,又要避免引入新的噪声。二十几年来,研究工作者们对传统FCM算法进行不断的研究,提出许多不同的改进,但上述问题仍然没有完全解决。

1.3本文的主要工作

本文在介绍图像分割的定义、方法、应用及研究意义和研究现状以及支持向量机的基础理论之后做了如下任务:

(1)详细介绍当前图像分割以及聚类分析的研究背景,现状。

(2)介绍了基于聚类算法的图像分割的算法步骤,以及本文所使用MATLAB软件工具;

(3)对基于模糊K均值的图像分割算法进行探讨,并对K均值算法进行改进,通过粗糙集理论提供 K-均值聚类所需要的初始类的个数和均值,提高了聚类的效率和分类的精度。

(4)对基于标准模糊 C 均值聚类的图像分割算法进行了探讨,研究了基于模糊聚类的图像分割方法中初始类别数的选取、初始类中心和初始隶属度矩阵的确定等问题

(5)总结了本文的主要研究内容,并就本文尚存在的不足进行了展望。

第二章聚类分析理论

聚类分析是一种新兴的多元统计方法,是当代分类学与多元分析的结合。聚

类分析是将分类对象置于一个多维空间中,依据样本间关联的度量标准将其自动分成几个群组,且使同一群组内的样本相似,而属于不同群组的样本相异的一组

方法。聚类的样本是用度量指针的一个向量表示,即用多维空间的一个点来表示。

同类中的样本比属于不同类的样本彼此具有更高的相似性。聚类分析通常是基于

距离的,通过构造一个 m 维空间的距离函数,利用这个距离函数来进行聚类。

2.1 聚类分析概述

迄今为止,聚类还没有一个学术界公认的定义,这里给出EverittIs在1974年关于聚类所下的定义:一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离;类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域,它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。

定义 2.1簇(Cluster):一个数据对象的集合。在同一簇中,对象具有相似性,不同簇中,对象之间是相异的。

定义 2.2聚类分析(Clustering analysis):把一个给定的数据对象集合分成不同的簇,即在空间 X 中给定一个有限的取样点集或从数据库中取得有限个例子的集合,{xi}ni=1。聚类的目标是将数据聚集成类,使得类间的相似性最小,而类内的相似性尽可能得大。

没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集中所呈现出来的多种多样的结构,根据数据在聚类中积聚规则以及应用这些规则的方法,有多种聚类算法。聚类算法有多种分类方法:

1.划分方法

给定一个包含n 个对象的数据集,划分方法将数据集划分为k 个子集。

其中每个子集均代表一个聚类(K<=n)。给定需要划分的个数k,一个划分方法

创建一个初始划分,然后利用循环再定位技术,即通过移动不同划分中的对象来

改变划分内容。一个好的划分衡量标准通常就是同一个组中的对象彼此相近或相

关,而不同组中的对象较远或差距较大。主要的划分方法有:K-means 聚类法和

K-medoid 聚类法。K-means 聚类法在处理海量数据库方面较有效,特别是对数

值属性处理,它对异常数据很敏感。PAM(围绕中心对象进行划分)方法是最初提出的K-medoid 聚类算法之一。K-medoid 聚类算法比K-means 聚类算法在

处理异常数据和噪声数据方面更为鲁棒,但是前者的处理时间要比后者更大。2.层次方法

层次方法就是通过分解所给定的数据对象集来创建一个层次。根据层次分解

形成的方式,可以将层次方法分为自下而上(也称凝聚方式)和自上而下(也称分割方式)两种类型。自下而上的层次方法从每个对象均为一个单独的组开始, 逐步将这些组进行合并,直到组合并到了层次顶端或满足终止条件为止。自上而下层次方法从所有对象均属于一个组开始,每一次循环将其分解为更小的组,直到每个对象构成一组或满足终止条件为止。

BIRCH 和CURE 算法就是层次方法的实例。

3.基于密度方法

基于密度的聚类方法就是不断增长所获得的聚类直到邻近密度小于一定阈

值为止。这种方法可以用于消除数据中的噪声(异常数据)。DBSCAN 就是一个

典型的基于密度的方法,该方法根据密度阈值不断增长聚类。

4.基于网格方法

基于网格方法将对象空间划分为有限数目的单元以形成网格结构。所有聚

类操作均是在这一网格结构上进行的。这种方法主要优点就是处理事件由于与数据对象个数无关而仅与划分对象空间的网格数相关,从而显得相对较快。STING 就是一个典型的基于网格的方法。

5.基于模型方法

基于模型的方法就是为每个聚类假设一个模型,再去发现符合相应模型的

数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它根据标准统计方法并考虑到“噪声”或异常数据,可以自动确定聚类个数,因此它可以产生很鲁棒的聚类方法。如神经网络方法。

2.1.1聚类分析中的数据类型

数据挖掘的一个重要步骤是数据准备,这包括对选定的数据进行规范化、整合和预处理等等,这是进行数据挖掘的前提,也同样是聚类算法能正常实施的必要前提。要对数据对象进行聚类,基于统计方法,其最重要的前提是要计算各个数据对象之间的距离—即相异度,针对不同的数据类型有不同的相异度计算方法。许多基于内存的聚类算法常使用以下两种有代表性的数据结构:数据矩阵和相异度矩阵。

数据矩阵与相异度矩阵

x(i=1,2,...,n),对每个对象选择了P个变量,设聚类问题中有n个对象:

i

用间隔尺度测定后,第i 个对象的第j 个变量的观测值用

ij x 表示,则这n 个对象所有

P 个变量的观测值可以看成是如下的 n ×p 矩阵:

11

11p np n x x x x ?? ? ? ? ? ???

K M O M L (2.1) 矩 阵 (2.1)常被称为数据矩阵,它是对象-变量结构的数据表达方式,其中 第i 个对象的P 个变量的观测值可以记为向量:

i x =()1,2,...i i ip

x x x T (2.2) 聚类中常用的另外一种数据结构是相异度矩阵,它存储的是n 个对象两两之间的 近似性,表现形式为一个 n ×n 矩阵:

(2.3)

其中 d(i,j) , 是对象 i 与对象 1 之间相异性的量化表示,通常它是一个非负的数值,当对象 i 和对象 j 越相似和越“接近”, d(i,j) , 的值就越接近。反之,如果两个对象越不同或相距“越远”, d(i,j) , 的值就越大。显然d(i,j) ,=d(i,j) ,且d(i,j) , =0,因此可以得到形如(2.3)的矩阵。相异度矩阵是对象-对象结构的一种数据表达方式。

2.1.2聚类分析的典型要求

聚类是一个富有挑战性的研究领域,它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求如下。

1) 可伸缩性

许多聚类算法在小于200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类又可能会导致偏差

的结果。我们需要具有高度可伸缩性的算法。

2)处理不同类型属性的能力

许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary),分类/标称类型(categorical/nominal),序数型(ordinal)数据,或者这些数据类型的混合。

3)发现任意形状的聚类

许多聚类算法基于欧几里的距离或者曼哈坦距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度合密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

4)处理噪声数据的能力

绝大多数现实世界中的数据库都包含了孤立点,空缺,未知数据或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。

5)对于输入记录的顺序不敏感

一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以

不同的顺序提交同一个算法时,可能生成差别很大的聚类结果。开发对数据输入

顺序布敏感的算法具有重要的意义。

6)高维性(high dimensionality)

一个数据库或者数据仓库可能包含若干维或者属性。许多聚类三算法擅长处

理低维数据,可能只涉及两到三维。人类最多在三维的情况下能够很好地判断聚

类的质量。在高维空间中聚类数据对象时非常有挑战性的,特别是考虑到这样的

数据可能非常稀疏,而且高度偏斜。

2.1.3聚类分析的一般步骤

在实际应用聚类分析中,根据有无领域知识参与可将整个过程分解为三个环

节,每个环节都有其明确的任务,这样对于整个聚类分析的过程就会有更清晰的

认识,如图 1.1 所示。

基于聚类分析的图像分割研究毕业论文

图1.1聚类的一般步骤

第一步是特征抽取。

它的输入是原始样本,由领域专家决定使用哪些特征来深刻地刻画样本的本质性质和结构。它的结果输出是一个矩阵,矩阵的每一行是一个样本,每一列是一个特征指标变量。选取特征的优劣将直接影响以后的分析和决策。如果第一步就选择了和聚类意图根本无关的特征变量,那企图得到良好的聚类结果则无异于缘木求鱼。合理的特征选取方案应当使得同类样本在特征空间中相距较近,异类样本则相距较远。在有些应用场合还需要将得到的样本矩阵进行一些后处理工作。比如为了统一量纲就对变量进行标准化处理,这样采用不同量纲的变量才具有可比性;有些场合可能选择的特征变量太多,不利于以后的分析和决策,这时可以先进行降维处理;仅凭经验和领域知识选择的特征变量有可能是相关的,进行主成分分析就可以消除变量间的相关性,从而得到一些相互独立的特征变量。

第二步是执行聚类算法,获得聚类谱系图。

它的输入是一个样本矩阵,它把一个样本想象成特征变量空间中的一个点。聚类

算法的目的就是获得能够反映 X 维空间中这些样本点之间的最本质的“簇成一团”性质。这一步没有领域专家的参与,它除了几何知识外不考虑任何的领域知识,不考虑特征变量在其领域中的特定含义,仅仅认为它是特征空间中一维而己。

聚类算法的输出一般是一个聚类谱系图,由粗到细地反映了所有的分类情况;或 者直接给出具体的分类方案,包括总共分成几类,每类具体包含那些样本点等等。

第三步是选取合适的分类阈值。

在得到了聚类谱系图之后,领域专家凭借经验和领域知识,根据具体的应用场合, 决定阈值的选取。选定阈值之后,就能够从聚类谱系图上直接看出分类方案。领 域专家还可以对聚类结果结合领域知识进行进一步的分析,从而加深样本点和特 征变量的认识。

总之,实际应用聚类分析是一个需要多方参与的过程,它无法脱离开领域专 家的参与,聚类算法仅仅是整个聚类流程中的一环而己,光依靠聚类算法一般不 会得到令人满意的效果。

2.2 常见的聚类算法

2.2.1 K-means 算法

K-means 聚类算法是给定类的个数 K ,利用距离最近的原则,将 N 个对象 分到 K 个类中去,聚类的结果由 K 个聚类中心来表达,基于给定的聚类目标函数(或称聚类效果判别函数),算法采用迭代更新的方法,每一次迭代过程都是向目标函数值减少的方向进行;在每一轮中,依据 k 个参照点将其周围的点分别组成 k 个簇,而每个簇的几何中心将被作为下一轮迭代的参照点,迭代使得选取的参照点越来越接近真实的簇几何中心,使得类内对象之间的相似性最大,类之间的相似性最小。

聚类效果的好坏用目标函数 J 表示:11(,)i k ij j i i j n j d x c ===∑∑, (2.4) 其中(,)ij j i d x c 是j x 与i

c 之间的距离函数,如欧氏距离。目标函数J 其实就是每个数据点与所在 簇的质心的距离之和,所以,J 值越小,簇就越紧凑,相对越独立。因此,算法 通过不断优化J 的取值来寻求好的聚类方案,当J 取极小值时,对应的聚类方案 即是最优方案。根据聚类结果的表达方式可以将聚类算法划分为:硬K-means

(HCM )算法、模糊K-means (FCM )算法和概率K-means 算法(PCM )。

K-means 算法描述如下:

相关文档
  • 图像分割毕业论文

  • 图像分割技术应用

  • 图像分割毕业设计

  • 图像分割程序设计

  • 图像区域分割算法

  • 图像处理毕业论文