数字图像聚类技术研究

数字图像聚类技术研究多媒体是一种极其重要的信息资源，现代技术已能运用各种手段大量地采集和产生各种类型的多媒体信息数据，而多媒体信息中占有举足轻重作用的一种就是图像信息。近年来随着需求的增加、工艺技术的进步，以各种方式获取的图像信息的数量得到了飞速的增长，进入新世纪后，有人估计世界每年产生的新图像已达800亿幅，信息膨胀已给人类带来过多的信息量以致超出了人的接受能力，有鉴于此，如何快速、准确、高效的从浩如烟海的图像信息源（比如网络）中获取有用的信息就变得极为重要，近年来国际上广泛开展了基于内容的图像检索研究，而其中图像聚类与检索技术已取得相当进展，在各个领域已得到了广泛的应用。所谓图像聚类就是在给出的图像集合中，根据图像的内容，在无先验知识的条件下，将图像分成有意义的簇。对于图像聚类，最引人注目的特征属性是颜色、纹理和形状等。目前有很多有效的聚类技术，如层次聚类算法、基于分割的算法、划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。1引言在图像检索的过程中我们同样面临着分类的任务，具体地讲就是图像的聚类。所谓图像聚类就是将未知类别的一组图像分成若干类的过程，也称无监督学习或无教师学习。聚类分析的思路比较直观，根据各个待分类图像特征的相似程度来进行分类，将在特征空间中聚集在一起的样本点划分为一类。选择合适的聚类算法对图像库中的图像进行聚类，是我们的核心任务之一。因此根据实际科研情况,选择一个好的聚类算法对后续的研究工作是非常关键的。聚类的定义:聚类是将数据划分成群组的过程。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务,这样最相似的数据就聚集成簇。聚类与分类的不同点:聚类的类别取决于数据本身;而分类的类别是由数据分析人员预先定义好的。聚类算法的分类:一般可分为基于层次的,基于划分的,基于密度的,基于网格的和基于模型的五种.2聚类的定义聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相关的，而不同组的对象是不相关的，组内相似度越大，组间差别度越大，聚内效果就越好。聚类分析技术作为强大的辅助工具在科学研究、社会服务、市场营销等多个领域发挥了巨大的作用。因此聚类分析技术研究也成为一个热点课题。3聚类方法目前，在聚类的算法主要可分为以下几种：划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。下面主要介绍划分方法和层次方法：图13.1基于层次的聚类方法层次聚类算法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶而下形成，层次聚类算法可以进一步分为凝聚型的聚类算法和分裂型的聚类算法。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。3.1.1两种基本的层次聚类方法凝聚的层次聚类是将这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。大部分的层次聚类方法都属于一类，它们在簇间的相似度的定义有点不一样。主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。1．BIRCH算法BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)算法使用了一种叫做CF-树(聚类特征树，即ClusteringFeatureTree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。2．CURE算法CURE(ClusteringUsingRepresentative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。3．ROCK算法CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。ROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。4．Chameleon算法Chameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇。Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n2)的时间。总的来说，层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。（b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。分裂的层次聚类是将像这样的自顶向下的策略与凝聚的层次聚类有些不一样，它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直达满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了某一个阈值。3.1.2基于距离度量的方法在凝聚和分裂的层次聚类之间，我们又依据计算簇间的距离的不同，分为下面的几类方法：单连锁（singlelinkage）,又称最近邻（nearestneighbor）方法。指两个不一样的簇之间任意两点之间的最近距离。这里的距离是表示两点之间的相异度，所以距离越近，两个簇相似度越大。这种方法最善于处理非椭圆结构。却对于噪声和孤立点特别的敏感，取出距离很远的两个类之中出现一个孤立点时，这个点就很有可能把两类合并在一起。距离公式如公式1所示。||min),(/,min/ppccdjpcpjii（1）（1）全连锁（comlpetelinkage），又称最远邻（furthestneighbor）方法。指两个不一样的簇中任意的两点之间的最远的距离。它面对噪声和孤立点很不敏感，趋向于寻求某一些紧凑的分类，但是，有可能使比较大的簇破裂。距离公式如公式2所示。||max),(/,max/ppccdjpcpjii（2）(2)组平均方法(grouPaveragelinkage)，定义距离为数据两两距离的平均值。这个方法倾向于合并差异小的两个类，产生的聚类具有相对的鲁棒性。距离公式如公式3所示。jicpjpjiavgnnppccdi/||),(//（3）（3）平均值方法(centroidlinkage),现计算各个类的平均值，然后定义平均值之差为两类的距离。距离公式如公式3.4所示。||),(jijimeanmmccd（4）（4）其中ic,jc是两个类，||/pp为对象p和/p之间的距离，in，jn分别为ic,jc的对象个数，im，jm分别为类ic,jc的平均值。3.2基于划分的聚类方法给定一个数据库包含个数据对象以及数目K的即将生成的簇,一个划分类的算法将对象分为K个划分，其中，这里的每个划分分别代表一个簇，并且K=。其中的K需要人为指定。它一般从一个初始划分开始，然后通过重复的控制策略，使某个准则函数最优化。因此，它可以被看作是一个优化问题，而优化问题往往是NP-难问题。基于划分的聚类方法的优缺点跟层次的聚类方法的优缺点刚刚好反，层次聚类算法的优点恰恰是划分聚类方法的缺点，反之亦然。根据它们之间的优缺点，人们往往会更趋向于使用划分的聚类方法，所以，本文着重于讲解基于划分的聚类方法。基于划分的聚类算法有许多，下面介绍几中常见的基于划分的聚类算法。3.2.1K-meansk-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。k-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。该算法的迭代的终止条件是直至中心点收敛。因此，K-means算法需要优化的目标函数是：21kiiiECpmp（5）其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。而K-medoids算法跟k-means算法的不同之处在于K-medoids用接近聚类中心的一个对象来表示每个簇而K-means用簇中对象的平均值来表示每个簇。输入:簇的数目k和包含n个对象的数据集。输出:k个簇。方法：（1）对于数据对象集,任意选取k个对象作为初始的簇中心;（2）根据簇中对象的平均值,将每个对象重新赋给最相似的簇;（3）更新簇的平均值,即计算每个簇中对象的平均值;（4）重复(2)(3);（5）直到不再发生变化。（a）(b)(c)3.2.2模糊C均值算法C-均值聚类算法：1．条件及约定设待分类的模式特征矢量集为Nxxx,,,21，类的数目c是事先确定的。2．基本思路设方法取定c类和选取c个初始聚类中心，按最小距离原则将各模式分配到c类中的某一类，之后不断地计算类心和调整个模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。3．算法步骤（1）任选c个模式特征矢量作为初始聚类中心：)0()0(2)0(1,,,czzz，令0k。（2）将待分类的模式特征矢量集),,2,1}({Nixi中的模式逐个按最小距离原则分划给c类中的某一类，即如果)()(minkijjkildd，Ni,,2,1，存在一个cl,,2,1。则判定)1(klix。式中)(kijd表示ix和)(kj的中心)(kjz的距离，上角标表示迭代次数。于是产生新的聚类),,2,1()1(cjkj。（3）计算重新分类后的各类中心cjxnzkjixikjkj,,2,1,1)1()1()1(式中)1(kjn为)1(kj类中所含模式的个数。因为这一步采取平均的方法计算调整后各类的中心，且定为c类，故称为C-均值法。（4）如果),,2,1()()1(cjzzkjkj，则结束；否则，1kk，转至（2）。应用C-均值聚类算法实现图像聚类：这里假设图像分割成c个区域，其图像大小为NM的灰度图像，任意位置),(yx处的灰度值为)255),(0)(,(yxgyxg。因此，灰度图像可采用集合方式描述为NyMxyxgG,,2