基于聚类分析的图像分割研究-学位论文.doc

南京邮电大学通达学院毕 业 设 计（论 文）题 目： 基于聚类分析的图像分割研究 专 业： 信息工程 学生姓名： 朱丹青 班级学号： 100002 10000215 指导教师： 李雷 指导单位： 理学院 日期： 2014 年 1月 16 日 至 2014 年 6 月 13 日毕业设计（论文）原创性声明本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。 论文作者签名： 日期： 年 6月 2日 目录第一章 绪论11.1图像分割的背景及意义11.2图像分割的研究现状31.3本文的主要工作5第二章 聚类分析理论72.1 聚类分析概述72.2 常见的聚类算法122.3 模糊聚类算法142.4图像分割方法162.5本章总结18第三章 基于K-means算法的图像分割方法193.1颜色空间193.2定义和概述193.3 简单的例子介绍213.4 k-means图像分割233.5改进的k-均值聚类图像分割算法273.6本章总结31第四章 基于FCM算法的图像分割324.1模糊聚类的概念324.2FCM算法的概述344.3本章总结43总结与展望445.1总结445.2研究展望45结束语46致谢47参考文献48附录A52基于K-means算法的matlab源程序52附录B54基于K-均值聚类改进前的matlab源程序54附录C57基于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南京邮电大学通达学院2014届本科生毕业设计(论文)第一章 绪论 在当前快速发展信息化时代，通过图像来获取信息是人类认识世界改造世界的重要方式之一，由此看来图像的处理就变得十分重要1。图像处理(image processing)，用计算机对图像进行分析，以达到所需结果的技术。又称影像处理。基本内容 图像处理一般指数字图像处理。数字图像是指用数字摄像机、扫描仪等设备经过采样和数字化得到的一个大的二维数组，该数组的元素称为像素，其值为一整数，称为灰度值。图像处理技术的主要内容包括图像压缩，增强和复原，匹配、描述和识别3个部分2。 常见的处理有图像数字化、图像编码、图像增强、图像复原、图像分割和图像分析等。其中图像分割的目的是为了后续对图像进行分析、识别、跟踪、理解、压缩编码等，分割的准确性直接影响后续任务的效果，具有极其重要的意义。所以本课题将研究方向确定在利用图像分割技术来进行图像的识别3。1.1图像分割的背景及意义 聚类分析研究有很长的历史，几十年来，其重要性及其研究方向的交叉特性得到人们的肯定。聚类分析是数据挖掘研究方向的重要研究内容之一，在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是从上世纪80年代开始发展起来的一门交叉学科，涉及到数据库、统计学、人工智能和机器学习多个领域。计算机的应用普及产生了大量数据，数据挖掘就是利用上述学科的技术进行大量的数据处理。数据挖掘的应用范围非常的广泛，从农业生产的预测到基因分类，从信用卡欺诈到税务稽查，数据挖掘技术对未来社会的各个领域将起到越来越大的作用4。 在一副图像中，我们在通常情况下只是对其中的某些目标感兴趣，它们通常在要分割的图像中占据一定的区域，而且在某些特性上与周围的图像存在一定的差别。这些差别有时候可能是特别明显的，也有可能是非常微小的，以至于人的肉眼无法察觉的到的。图像分割是按照一定的制约规则把图像划分为若干个互不相交，具有特定性质的区域,是把我们关注的区域从需要分割的图像中提取出来，从此进行进一步研究和处理的技术。它使得其中的图像分析和识别等处理过程中所要处理的数据量大大减少了，同时有保留了有关图像结构特征的信息。图像分割的结果是图像特征提取和识别等图像理解的基础，对图像分割的研究一直是数字图像处理技术的焦点和热点。关于图像分割的概念有很多，但最终都归于一个基本思想，即图像分割时根据实际需求与应用，按照指定特征信息，对图像中有意义的边界、兴趣区域或者对相一致的区域（灰度、颜色、纹理等）进行分解和提取的技术和过程5。 图像分割的数学解释：假定一幅图像中所有像素的集合为，有关均匀性的假设为。分割定义把划分为若干子集，其中每个子集都构成一个空间连通区域。用四个条件进行数学描述，即6：；。式中，为空集。 图像分割的重要性，可以从图像工程的三个层次来理解，如图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 中给定一个有限的取样点集或从数据库中取得有限个例子的集合，xini=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聚类分析中的数据类型数据挖掘的一个重要步骤是数据准备，这包括对选定的数据进行规范化、整合和预处理等等，这是进行数据挖掘的前提，也同样是聚类算法能正常实施的必要前提。要对数据对象进行聚类，基于统计方法，其最重要的前提是要计算各个数据对象之间的距离即相异度，针对不同的数据类型有不同的相异度计算方法。许多基于内存的聚类算法常使用以下两种有代表性的数据结构：数据矩阵和相异度矩阵。 数据矩阵与相异度矩阵 设聚类问题中有n个对象:(i=1,2,.,n)，对每个对象选择了P个变量，用间隔尺度测定后，第i个对象的第j个变量的观测值用表示，则这n个对象所有P个变量的观测值可以看成是如下的 np 矩阵: （2.1）矩 阵 (2.1)常被称为数据矩阵，它是对象变量结构的数据表达方式，其中 第i个对象的P个变量的观测值可以记为向量:=T (2.2)聚类中常用的另外一种数据结构是相异度矩阵，它存储的是n个对象两两之间的近似性，表现形式为一个 nn 矩阵: (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表示:， (2.4) 其中是与之间的距离函数，如欧氏距离。目标函数J 其实就是每个数据点与所在簇的质心的距离之和，所以，J值越小，簇就越紧凑，相对越独立。因此，算法通过不断优化J的取值来寻求好的聚类方案，当J取极小值时，对应的聚类方案即是最优方案。根据聚类结果的表达方式可以将聚类算法划分为：硬K-means（HCM）算法、模糊K-means（FCM）算法和概率K-means 算法（PCM）。K-means 算法描述如下：步骤 1) 随机选取k个对象作为初始的簇的质心; 步骤 2) 计算对象与各个族的质心的距离，将对象划分到距离其最近的簇 ; 步骤 3) 重新计算每个新簇的均值，即质心;步骤 4) 若簇的质心不再变化，则返回划分结果，否则转步骤2）.k-means 算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显时，它的效果较好。面对大规模数据集，该算法是相对可扩展的，并且具有较高的效率。算法的复杂度为O(nkt),其中，n为数据集中对象的数目，k为期望得到的簇的数目，t为迭代的次数。通常情况下，算法可以终止于局部最优解。 但是，kmeans算法只有在簇的平均值被定义的情况下才能使用。这可能不适用于某些应用，例如涉及有分类属性的数据。其次，这种算法要求事先给出要生成的簇的数目k，显然，这在某些应用中是不实际的。另外，k-means算法不适用于发现非凸面形状的簇，或者大小差别很大的簇。还有，它对于噪音和孤立点数据是敏感的。 kmeans算法有很多变种，例如，k-模算法用模代替簇的平均值，用新的相异性度量方法来处理分类对象，用基于频率的方法来修改聚类的模。而k平均算法和k模算法相结合，用来处理有数值类型和分类类型属性的数据，就产生了k-原型算法。2 .2. 2 D BSCAN 算法DBSCAN 算法可以将足够高密度的区域划分为簇, 并可以在带有 “噪声” 的空间数据库中发现任意形状的聚类 。 DBSCAN 通过检查数据库中每个点的E 2邻域来寻找聚类 。 如果一个点 P 的 E 2 邻域包含多于M inP ts 个点, 则创建一个以 P 作为核心对象的新簇 。然后反复地寻找从这些核心对象直接密度可达的对象, 当没有新的点可以被添加到任何簇时, 该过程结束 。 如果采用空间索引, DBSCAN 的计算复杂度是O(n log n ) 。 2.2.3 STING算法STING（Statistical Information Grid)算法是一种基于网格的多分辨率聚类方法，它将空间区域划分为若干矩形网格单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构，高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息，如平均值、最大值、最小值等，被预先计算和存储。 高层单元的统计参数可以很容易地从低层单元的计算得到。这些统计参数包括:属性无关的参数count；属性相关的参数m(平均值)，s(标准方差)，min(最小值)，max(最大值)，以及该单元中属性值遵循的分布(distribution)类型，例如正态分布、平均分布、指数分布或无(如果分布未知)。当数据被装载进数据库时，底层单元的参数count、m、s, min和max直接进行计算。如果分布的类型事先知道，distribution的值可以由用户指定，也可以通过假设检验来获得。 统计参数的使用可以按照以下自顶向下的基于网格的方法:首先，在层次结构中选定一层作为查询处理的开始点。通常该层包含少量的单元。对当前层次的每个单元，我们计算置信度区间或者估算其概率范围，用以反映该单元与给定查询的关联程度，不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。这个过程反复进行，直到达到底层。此时，如果满足查询条件，那么返回相关单元的区域。否则，检索和进一步处理相关单元中的数据，直到它们满足查询条件。 与其他聚类方法相比，STING算法的优点在于: (1) 由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，所有基于网格的计算是独立于查询的； (2) 网格结构有利于并行处理和增量更新； (3) 算法效率很高。STING算法通过扫描一次数据库来计算单元的统计信息，产生聚类的时间复杂度是On)，其中n为对象的数目。在层次结构建好后，查询处理的时间复杂度是O(g)，其中g是最低网格单元的数目，通常远远小于n 。 STING 算法的性能取决于最底层单元的粒度，该粒度也决定着聚类结果的质量。STING算法在粒度较大时，速度非常快，但这时聚类的质量不够好。当粒度较小时，聚类结果的质量好，但处理的代价会增加。2.3 模糊聚类算法2.3.1 模糊聚类算法概述模糊聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算