数字图像聚类技术研究

数字图像聚类技术研究多媒体是一种极其重要的信息资源，现代技术已能运用各种手段大量地采集和产生各种类型的多媒体信息数据，而多媒体信息中占有举足轻重作用的一种就是图像信息。近年来随着需求的增加、工艺技术的进步，以各种方式获取的图像信息的数量得到了飞速的增长，进入新世纪后，有人估计世界每年产生的新图像已达800亿幅，信息膨胀已给人类带来过多的信息量以致超出了人的接受能力，有鉴于此，如何快速、准确、高效的从浩如烟海的图像信息源（比如网络）中获取有用的信息就变得极为重要，近年来国际上广泛开展了基于内容的图像检索研究，而其中图像聚类与检索技术已取得相当进展，在各个领域已得到了广泛的应用。所谓图像聚类就是在给出的图像集合中，根据图像的内容，在无先验知识的条件下，将图像分成有意义的簇。对于图像聚类，最引人注目的特征属性是颜色、纹理和形状等。目前有很多有效的聚类技术，如层次聚类算法、基于分割的算法、划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。1引言 在图像检索的过程中我们同样面临着分类的任务，具体地讲就是图像的聚类。所谓图像聚类就是将未知类别的一组图像分成若干类的过程，也称无监督学习或无教师学习。聚类分析的思路比较直观，根据各个待分类图像特征的相似程度来进行分类，将在特征空间中聚集在一起的样本点划分为一类。选择合适的聚类算法对图像库中的图像进行聚类，是我们的核心任务之一。 因此根据实际科研情况,选择一个好的聚类算法对后续的研究工作是非常关键的。聚类的定义:聚类是将数据划分成群组的过程。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务,这样最相似的数据就聚集成簇。聚类与分类的不同点:聚类的类别取决于数据本身;而分类的类别是由数据分析人员预先定义好的。聚类算法的分类:一般可分为基于层次的,基于划分的,基于密度的, 基于网格的和基于模型的五种.2 聚类的定义 聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相关的，而不同组的对象是不相关的，组内相似度越大，组间差别度越大，聚内效果就越好。聚类分析技术作为强大的辅助工具在科学研究、社会服务、市场营销等多个领域发挥了巨大的作用。因此聚类分析技术研究也成为一个热点课题。 3聚类方法 目前，在聚类的算法主要可分为以下几种：划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。下面主要介绍划分方法和层次方法：图13.1 基于层次的聚类方法层次聚类算法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶而下形成，层次聚类算法可以进一步分为凝聚型的聚类算法和分裂型的聚类算法。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。3.1.1两种基本的层次聚类方法凝聚的层次聚类是将这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。大部分的层次聚类方法都属于一类，它们在簇间的相似度的定义有点不一样。主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。1BIRCH算法BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即Clustering Feature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。2CURE算法CURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。3ROCK算法CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。ROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。4Chameleon算法Chameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇。Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n2)的时间。总的来说，层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。（b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。分裂的层次聚类是将像这样的自顶向下的策略与凝聚的层次聚类有些不一样，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直达满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了某一个阈值。3.1.2基于距离度量的方法在凝聚和分裂的层次聚类之间，我们又依据计算簇间的距离的不同，分为下面的几类方法：单连锁（single linkage）,又称最近邻（nearest neighbor）方法。指两个不一样的簇之间任意两点之间的最近距离。这里的距离是表示两点之间的相异度，所以距离越近，两个簇相似度越大。这种方法最善于处理非椭圆结构。却对于噪声和孤立点特别的敏感，取出距离很远的两个类之中出现一个孤立点时，这个点就很有可能把两类合并在一起。距离公式如公式1所示。 （1） （1）全连锁（comlpete linkage），又称最远邻（furthest neighbor）方法。指两个不一样的簇中任意的两点之间的最远的距离。它面对噪声和孤立点很不敏感，趋向于寻求某一些紧凑的分类，但是，有可能使比较大的簇破裂。距离公式如公式2所示。 （2） (2) 组平均方法(grou Paverage linkage)，定义距离为数据两两距离的平均值。这个方法倾向于合并差异小的两个类，产生的聚类具有相对的鲁棒性。距离公式如公式3所示。 （3） （3）平均值方法(centroid linkage),现计算各个类的平均值，然后定义平均值之差为两类的距离。距离公式如公式3.4所示。 （4） （4）其中,是两个类，|为对象p和之间的距离，分别为,的对象个数，分别为类,的平均值。3.2 基于划分的聚类方法给定一个数据库包含个数据对象以及数目K的即将生成的簇,一个划分类的算法将对象分为K个划分，其中，这里的每个划分分别代表一个簇，并且K3; DENCLUE 算法是一个基于一组密度分布函数的聚类算法。该算法主要基于下面的想法： (1) 每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在领域内的影响，被称为影响函数； (2) 数据空间的整体密度可以被模型化为所有数据点的影响函数的总和； (3) 聚类可以通过确定密度吸引点来得到，这里的密度吸引点是全局密度函数的局部最大。3.4基于网格法主要思想是将空间区域划分若干个具有层次结构的矩形单元，不同层次的单元对应于不同的分辨率网格，把数据集中的所有数据都映射到不同的单元网格中，算法所有的处理都是以单个单元网格为对象，其处理速度要远比以元组为处理对象的效率要高的多。代表性算法有：STING算法、CLIQUE 算法、WAVE-CLUSTER 算法等。STING(statistical information grid) 算法首先将空间区域划分为若干矩形单元，这些单元形成一个层次结构，每个高层单元被划分为多个低一层的单元。单元中预先计算并存储属性的统计信息，高层单元的统计信息可以通过底层单元计算获得。这种算法的优点是效率很高，而且层次结构有利于并行处理和增量更新；其缺点是聚类的边界全部是垂直或是水平的，与实际情况可能有比较大的差别，影响聚类的质量。CLIQUE(clustering in quest)算法综合了基于密度和基于网格的聚类方法。其主要思想是将多维数据空间划分为多个矩形单元，通过计算每一个单元中数据点中全部数据点的比例的方法确定聚类。其优点是能够有效处理高维度的数据集，缺点是聚类的精度有可能会降低。WaveCluster(clustering using wavelet transformation)算法是一种采用小波变换的聚类方法。其首先使用多维数据网格结构汇总区域空间数据，用多维向量空间表示多维空间中的数据对象，然后使用小波变换方法对特征空间进行处理，发现特征空间中的稠密区域。最终通过多次小波变换，获得多分辨率的聚类。3.5基于模型法给每一个聚类假定一个模型，然后去寻找能够很好地满足这个模型的数据集。常用的模型主要有两种：一种是统计学的方法，代表性算法是COBWEB算法；另一种是神经网络的方法，代表性的算法是竞争学习算法。COBWEB 算法是一种增量概念聚类算法。这种算法不同于传统的聚类方法，它的聚类过程分为两步：首先进行聚类，然后给出特征描述。因此，分类质量不再是单个对象的函数，而且也加入了对聚类结果的特征性描述。竞争学习算法属于神经网络聚类。它采用若干个单元的层次结构，以一种“胜者全取”的方式对系统当前所处理的对象进行竞争。COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。它以一个分类树的形式创建层次聚类。分类树的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数沿着“最佳”匹配节点的路径在树中向下移动。寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。但如果对象不属于树中现有的任何概念，则为该对象创建一个新类。CORWEB的优点在于：他不需要用户输入参数来确定分类的个数，它可以自动修正划分中类的数目。缺点是：首先，它基于这样一个假设：在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。3.6各类算法比较基于上述的分析，下面对常用聚类算法的性能从可伸缩性、发现聚类的形状、对“噪声”的敏感性、对数据输入顺序的敏感性、高维性和是否是硬聚类六个方面进行比较，如表1所示。算法可伸缩性发现聚类的形状对“噪声”的敏感性对数据输入顺序的敏感性高维性K-means不好凸形敏感敏感不好FCM好任意形状敏感不敏感好EM不好任意形状敏感不敏感不好KHM好任意形状敏感不敏感不好SNN好任意形状敏感不敏感好CLARANS好球形及凸形不敏感很敏感一般CURE差任意形状不敏感敏感好BIRCH差球形或凸形一般不太敏感好STING好任意形状不敏感不敏感好DBSCAN较好任意形状不敏感敏感一般COBWEB较好任意形状一般敏感好FCM好任意形状敏感不敏感好k-means好球形或凸形敏感不敏感好表1：各类算法比较4、总结 聚类分析是图像处理中一种非常有用的技术，它可作为特征和分类算法的预处理步骤，这些算法再在生成的簇上进行处理，也可将聚类结果用于进一步关联分析还可以作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步分析其应用范围涉及商务，生物，地理，web文档分类，仿真等诸多领域。 聚类能更好地应用到现实生活中是很必要的。这些新算法正努力把静态的聚类推向动态的、适应性强的、带约束条件的及与生活联系紧密的聚类。同时，对目前可有效处理二维和小的数据集的聚类方法进行强化和修改，以使其能处理大的和高维的数据，这也是努力的一个方向。参考文献1G.H.Omran,P.Engelbrecht and salman.Intelligent Data Analysis:An overview of clustering methods.2007,583-605.2宋余庆，谢从华，朱玉全等基于近似密度函数的医学图像聚类分析研究J计算机研究与发展，2006，43(1 1)：194719523宋余庆，王春红，陈健美等基于高斯混合密度模型的医学图像聚类方法J江苏大学学报(自然科学版)，2009，30(3)：2932964 段明秀.层次聚类算法的研究及应用D:硕士学位论文.长沙：中南大学,2009.5G.Hamerly and C.Elkan,CIKM-2002:Alternatives to the K-means Algorithm that Find Better Clusterings.2002,600-607.6B.zhang,Generalized K-Harmonic Means-Boosting in Unsupervised Learning.Technical Report HPL-2000-137.Hewlett-Packard Labs,2000.7 J.MacQueen, SomeMethods for Classication and Analysis ofMultivariate Observations. In Proceedings Fifth Berkeley Symposium on Mathematics, Statistics and Probability, vol. 1, 1967, 281297.8 乔小妮，张明新，史变霞.一种基于密度的 K-means 算法.电脑开发与应用.2008.21(10).9-11 9 傅德胜，周辰. 基于密度的改进 K 均值算法及实现.计算机应用.2011.31(2).432-434 10 张丽芳.3 种聚类算法性能比较分析.长江大学学报.2009.6(2).250-251 1l李艳灵，沈轶基于空间邻域信息的FCM图像分割算法J华中科技大学学报：自然科学版200937(6)：56-5912 杨善林，李永森，胡笑旋，等Kmeans算法中k值优化问题研究J系统工程理论与实践，2006，26(2)：9710113 于剑，程乾生模糊聚类方法中的最佳聚类数的搜索范围J中国科学(E辑)，2002，32(2)：27428014CLIFTON CHRISTOPHER W， MULLIGAN DEIRDRE K， RAGHU RAMAKRISHNAN. Data Mining and Privacy： An OverviewM.Knowledge Discovery and Data Mining.1996：193.15 乔小妮，张明新，史变霞.一种基于密度的 K-means 算法.电脑开发与应用.2008.21(10).9-11 16 傅德胜，周辰. 基于密度的改进 K 均值算法及实现.计算机应用.2011.31(2).432-434 17 周代红，遗传聚类算法及其在医学图像分割中的应用，山东：曲阜师范大学18 沈宏斌，王士同，吴小俊.利群模糊核聚类算法J.软件学报，2004,15:1021-1029 19 薛耿剑，王毅一种改进的模糊核聚类算法J中国医学影像技术，200521(10)：1609-161 120 庄恒扬 , 沈新平 , 陆建飞 , 黄丽芬 . 模糊聚类计算方法的理论分析 . 江苏农业学报.1998.19(3).37-41 21 孙即祥.现代模式识别 M .长沙: 国防科技大学出版社, 2002: 13- 45. 22 李飞, 薛彬, 黄亚楼.初始中心优化的K-Means 聚类算法 J .计算机科学, 2002, 29( 7) : 94- 96.