数字图像聚类术研究.doc

数字图像聚类技术研究 多媒体是一种极其重要的信息资源，现代技术已能运用各种手段大量地采集和产生各种类型的多媒体信息数据，而多媒体信息中占有举足轻重作用的一种就是图像信息。近年来随着需求的增加、工艺技术的进步，以各种方式获取的图像信息的数量得到了飞速的增长，进入新世纪后，有人估计世界每年产生的新图像已达800亿幅，信息膨胀已给人类带来过多的信息量以致超出了人的接受能力，有鉴于此，如何快速、准确、高效的从浩如烟海的图像信息源（比如网络）中获取有用的信息就变得极为重要，近年来国际上广泛开展了基于内容的图像检索研究，而其中图像聚类与检索技术已取得相当进展，在各个领域已得到了广泛的应用。 所谓图像聚类就是在给出的图像集合中，根据图像的内容，在无先验知识的条件下，将图像分成有意义的簇。对于图像聚类，最引人注目的特征属性是颜色、纹理和形状等。目前有很多有效的聚类技术，如层次聚类算法、基于分割的算法、 划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法 1引言 在图像检索的过程中我们同样面临着分类的任务，具体地讲就是图像的聚类。所谓图像聚类就是将未知类别的一组图像分成若干类的过程，也称无监督学习或无教师学习。聚类分析的思路比较直观，根据各个待分类图像特征的相似程度来进行分类，将在特征空间中聚集在一起的样本点划分为一类。选择合适的聚类算法对图像库中的图像进行聚类，是我们的核心任务之一。 ,选择一个好的聚类算法对后续的研究工作是非常关键的。聚类的定义:聚类是将数据划分成群组的过程。通过确定数据之间在预先制定的属性上的相似性来完成聚类任务,这样最相似的数据就聚集成簇。聚类与分类的不同点:聚类的类别取决于数据本身;而分类的类别是由数据分析人员预先定义好的。聚类算法的分类:一般可分为基于层次的,基于划分的,基于密度的, 基于网格的和基于模型的五种. 2 聚类的定义 　　聚类分析仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，组内的对象相互之间是相关的，而不同组的对象是不相关的，组内相似度越大，组间差别度越大，聚内效果就越好。聚类分析技术作为强大的辅助工具在科学研究、社会服务、市场营销等多个领域发挥了巨大的作用。因此聚类分析技术研究也成为一个热点课题。 　　目前，在聚类的算法主要可分为以下几种：划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。 层次聚类算法，它是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶而下形成，层次聚类算法可以进一步分为凝聚型的聚类算法和分裂型的聚类算法。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。 3.1.1两种基本的层次聚类方法 凝聚的层次聚类是将这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。大部分的层次聚类方法都属于一类，它们在簇间的相似度的定义有点不一样。 主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。 1．BIRCH算法 BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即Clustering Feature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。 BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。 2．CURE算法 CURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。