基于聚类分析的图像分割的研究和应用.doc

1、基于聚类分析的图像分割的研究和应用摘 要聚类分析是数据挖掘的重要研究内容之一，在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是近几年国内迅速开始发展起来的一门新技术,其研究涉及机器学习、神经网络、统计学多个学科领域的知识，其发展对未来社会的各个领域的作用将会越来越大。图像分割是图像分析中的一个基本问题，随着技术的进步,图像使用的越来越多,对图像的分割也越来越引起人们的重视。本文主要是通过数据挖掘中聚类分析算法对图像进行分割。本文首先简要概述了本课题的背景、国内外动态；其次又详细介绍了数据挖掘的基本知识和聚类分析的各种算法；然后具体给出了如何利用聚类分析中的k-means算法在RGB和H

2、SV颜色空间下实现图像分割；最后，通过图像分割系统在遥感中的应用，验证系统的有效性。关键词 数据挖掘 聚类分析 图像分割 k-means HSVThe research and application of image segmentation based on clustering analysisABSTRACTClustering analysis is one of the most important directions of research of data mining and it plays an important role in the identification o

3、f datas intrinsic structure aspect. Data mining is a new technology which has developed rapidly in recent years. Its study involves machine learning, neural network, statistics and many other subjects and its development has been more and more significant to every field of the society. Image segment

4、ation is one of the basic problems of image analysis. With the development of technology, the image will be used more widely and image analysis will get more and more peoples closer attention.This paper mainly uses clustering analysis of data mining to implement image segmentation. It first briefly

5、outlines the topics background, the domestic and foreign tendencies. Next, it introduces detailed basic acknowledge of data mining and every algorithm of clustering analysis. Then it realizes the function of image segmentation by k-means algorithm under the colorful space of RGB and HSV. At last, th

6、e application of the image segmentation system in remote image will be used to test its validation.KEYWORDS Data Mining Clustering Analysis Image Segmentation K-means HSV目录1前言11.1 研究的目的和意义11.2 国内外研究动态11.3 研究的主要内容和论文结构22.数据挖掘中的聚类分析技术42.1 数据挖掘概述42.1.1 数据挖掘基本概念42.1.2 数据挖掘的分类42.1.3 数据挖掘过程52.1.4 数据挖掘方法62

7、.2 聚类分析算法介绍72.2.1 聚类概念82.2.2 聚类分析算法的类别83.基于K-means聚类算法图像分割系统的设计与实现153.1 图像分割153.2 RGB和HSV颜色空间153.2.1 RGB颜色空间153.2.2 HSV颜色空间163.2.3 RGB与HSV颜色空间比较163.3 图像分割系统的整体设计173.3.1 系统的整体功能模块设计173.3.2系统的整体处理流程设计173.4 图像分割系统的实现183.4.1 系统实现环境183.4.2 各功能模块实现183.2 实验分析224. 遥感图像在图像分割系统的应用234.1 遥感的基本概念234.1.1 遥感的定义234

8、.1.2 遥感的基本原理234.1.3 遥感数据的分类234.2 遥感图像分割244.2.1 遥感图像的RGB颜色空间下图像分割244.2.2 遥感图像的HSV颜色空间下图像分割254.2.3 RGB和HSV颜色空间下图像分割效果比较26总结27谢辞28参考文献291前言1.1 研究的目的和意义聚类分析研究有很长的历史，几十年来，其重要性及其研究方向的交叉特性得到人们的肯定。聚类分析是数据挖掘研究方向的重要研究内容之一，在识别数据的内在结构方面有极其重要的作用。数据挖掘技术是从上个世纪80年代开始发展起来的一门交叉学科,涉及到数据库、统计学、人工只能和机器学习多个领域。计算机的应用普及产生了大

9、量数据，数据挖掘就是利用上述学科的技术进行大量的数据处理。数据挖掘的应用范围非常的广泛，从农业生产的预测到基因分类，从信用卡欺诈到税务稽查，数据挖掘技术对未来社会的各个领域将起到越来越大的作用。图象分割是指将图像分解为各具特性的区域并提取出感兴趣目标的技术和过程，它是图像理解、模式识别和计算机视觉领域中一个十分重要且又十分困难的问题,是计算机视觉技术中首要的关键步骤。图象分割在工业自动化、在线产品检验、生产过程控制、文档图象处理、遥感和生物医学图象分析、图象编码、保安监视,以及军事、体育和农业工程等方面已得到广泛的应用。图象分割是指在一幅彩色图像中分离出主要的色彩一致的区域，随着技术的进步,图

10、像使用的越来越多,对图像的分割也越来越引起人们的重视。据国外专家预测，在今后的510年内，随着数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。1.2 国内外研究动态1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出“在数据库中的知识发现”(KDD: Knowledge Discovery in Database)技术，1991、1993、1994年又相继举行了KDD专题讨论会。1995年，在美国计算机年会(ACM)上，提出了数据挖掘(DM: Data Mining)的概念，即通过从数据库中抽取隐含的、未知的、具有潜在使用价值信息的过程。由于数据库中的数据

11、被形象地比喻为矿床，因此，数据挖掘一词很快流传开来。由于它应用的普遍性及由此带来的高效益，新型的数据分析技术-数据挖掘成为一个具有广阔应用前景的热门研究方向。KDD的研究吸引了大量的各个领域的专家和研究机构从事该领域的研究。许多公司纷纷推出了自己的数据挖掘系统。我国的数据挖掘研究开始于90年代中期，到90年代中后期，初步形成了知识发现和数据挖掘的基本框架。自90年代中期一批研究成果（学术论文)逐渐发表在计算机学报、计算机研究与发展、软件学报、人工智能与模式识别等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术研究为

12、主，实际应用上处于起步阶段。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究。与国外相比，国内对DMKD的研究稍晚，没有形成整体力量。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研究，如清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究；华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发

13、现以及Web数据挖掘；我校数据仓库与数据挖掘课题组在数据仓库与数据挖掘相结合方面的研究取得了较大的进展，目前正积极推进研究成果在金融、统计、商业和制造业领域的应用。因此，国内迫切需要对国外的数据挖掘技术记性剖析，在掌握核心技术的前提下才能真正超越。1.3 研究的主要内容和论文结构本文主要内容就是利用聚类分析中的K-MEANS算法在RGB和HSV颜色空间下实现图像分割系统，并应用于遥感图像，其具体有下面几方面内容：1、 了解数据挖掘的概念，熟悉聚类分析的思想算法，特别掌握k-means算法的思想及句体实现。2、 基于数据挖掘聚类分析方法，完成RGB颜色空间下的图像分割系统。3、 研究RGB和HS

14、V颜色空间的转换关系，实现RGB空间到HSV空间转换，从而实现HSV空间下的图像分割。4、 将图像分割系统应用于遥感图像分割，并对分割结果进行分析。按照本文的主要内容，本文的论文结构如下：第一章 ：前言。本章主要简单介绍了本论文的目的和意义、国内外研究动态和研究的主要内容。第二章 ：数据挖掘技术中的聚类分析技术。本章主要介绍了数据挖掘概述和聚类分析各种算法。第三章 ：图像分割系统的实现。本章首先介绍了图像分割系统的概念，然后又具体给出了系统的结构设计和程序流程设计，最后给出了具体结构的各模块设计实现。第四章 ：遥感图像在图像分割系统中的应用。本章主要是将图像分割系统应用到遥感图像的聚类分析中，

15、并在RGB、HSV两种颜色空间下进行图像分割，进行比较、总结。第五章 ：总结。272.数据挖掘中的聚类分析技术2.1 数据挖掘概述2.1.1 数据挖掘基本概念数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键数据。简而言之，数据挖掘其实是一类深层次的数据分析方法。从这个角度数据挖掘也可以描述为：按企业制定的业务目标，对大量的企业数据进行探索和分析

16、，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。2.1.2 数据挖掘的分类数据挖掘设计的科学领域和方法很多，有很多种分类方法。根据挖掘任务，可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模型发现、依赖关系或以来模型发现、异常和趋势发现等。下面将具体介绍各种方法。关联分析(association analysis)关联规则挖掘是由Rakesh Apwal等人首先提出的。两个或两个以上变量的取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中隐藏的关联网。

17、一般用支持度和可信度两个阀值来度量关联规则的相关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 聚类分析(clustering)聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。分类(classification)分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预测。预测(predication)预测是利用历史数

18、据找出变化规律，建立模型，并由此模型对未来数据的种类及特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。时序模式(time-series pattern)时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。偏差分析(deviation)在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照之间的差别。2.1.3 数据挖掘过程数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的、有效的、可实用的信息

19、，并使用这些信息做出决策或丰富知识。数据挖掘的基本过程和主要步骤如图2.1所示：逻辑数据库被选择的数据据预处理后的数据被转换的数据据据被抽取的信息息被同化的知识识选择 善而从 择择择预处理转换挖掘分析和同化图2.1过程中各步骤的大体内容如下：1确定业务对象，清晰地定义出业务问题。认清数据挖掘的目的是数据挖掘的重要一步，挖掘的最后结构不可预测，但要探索的问题应该是有预见的，为了数据挖掘而挖掘则带有盲目性，是不会成功的。2数据准备。(1)数据选择。搜索所有与业务对象有关的内部和外部数据信息，并从中选择出适用于数据挖掘应用的数据。(2)数据预处理。研究数据的质量，进行数据的集成、变换、归约、压缩等为

20、进一步的分析作准备，并确定将要进行的挖掘操作的类型。(3)数据转换。将数据转换成一个分析模型，这个分析模型是针对挖掘算法建立的这是数据挖掘成功的关键。3数据挖掘。对所得到的经过转换的数据进行挖掘。除了完善和选择合适的挖掘算法外，其余一切工作都能自动地完成。4结果分析。解释并评估结果。其使用的分析方法一般应视挖掘操作而定，通常会用到可视化技术。5知识同化。将分析所得到的知识集成到业务信息系统的组织结构中去。2.1.4 数据挖掘方法神经网络方法神经网络由于本身良好的自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分

21、3大类：以感知机、BP反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以Hopfield的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以ART模型、Koholon模型为代表的，用于聚类的自组织映射方法。神经网络方法的缺点是黑箱性，人们难以理解网络的学习和决策过程。本文用到了Kohonen自组织神经网络，具体将在后面讲述。遗传算法遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中被加以应用。决策树方法决策树是一种常用于预测模型的算法，它

22、通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。粗集方法粗集理论是一种研究不精确、不确定知识的数学工具。粗集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗集处理的对象是类似二维关系表的信息表。覆盖正例排斥反例方法它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则(选择子的合取式)。统计分析方法在数据库字段项之间存在两种关系：函数关系(能用函数公式

23、表示的确定性关系)和相关关系(不能用函数公式表示，但仍是相关确定性关系)，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计(求大量数据中的最大值、最小值、总和、平均值等)、回归分析(用回归方程来表示变量间的数量关系)、相关分析(用相关系数来度量变量间的相关程度)、差异分析(从样本统计量的值得出差异来确定总体参数之间是否存在差异)等。模糊集方法即利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。有人在传统模糊理论和概率统计的基础上，提出了定性定量

24、不确定性转换模型云模型，并形成了云理论。2.2 聚类分析算法介绍聚类分析研究有很长的历史，几十年来，其重要性及与其他研究方向的交叉特性得到人们的肯定。聚类是数据挖掘、模式识别等研究方向的重要研究内容之一，在识别数据的内在结构方面具有极其重要的作用，聚类主要应用于模式识别中的语音识别、字符识别等，机器学习中的聚类算法应用于图像分割和机器视觉，图像处理中聚类用于数据压缩和信息检索，聚类的另一个主要应用是数据挖掘(多关系数据挖掘)、时空数据库应用(GIS等)、序列和异类数据分析等，此外，聚类还应用于统计科学，值得一提的是，聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作

25、用。2.2.1 聚类概念迄今为止，聚类还没有一个学术界公认的定义，这里给出 EverittIs 在1974年关于聚类所下的定义：一个类簇内的实体是相似的，不同类簇的实体是不相似的；一个类簇是测试空间中点的会聚，同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离；类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域，它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。聚类过程：1) 数据准备：包括特征标准化和降维，2) 特征选择：从最初的特征中选择最有效的特征，并将其存储于向量中，3) 特征提取：通过对所选择的特征进行转换形成新的突出特征，4) 聚类(或分组)：首先

26、选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量；5) 聚类结果评估：是指对聚类结果进行评估，评估主要有3种：外部有效性评估、内部有效性评估和相关性测试评估。2.2.2 聚类分析算法的类别没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法，有多种聚类算法。聚类算法有多种分类方法，聚类算法可以分为以下几大类：分割聚类方法(Partitioning Method)、层次聚类方法(Hierarchical Method)、基于密度(Density-Based)的聚类方法、基于网格(Grid

27、-Based)的聚类方法、基于模型(Model-Based)的聚类方法等等。1基于划分的方法:所谓基于划分的方法(Partitioning Method)是指给定一个包含n个数据对象的数据集，以及要生成的簇的数目K，采用一个划分准则（称为相似度函数）将数据对象组织为K个划分(k=n)，每个划分代表一个簇，使同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。为了使该方法适用于大规模数据集，以及处理复杂形状的聚类，出现了若干基于划分方法的扩展方法。该类方法的典型代表是K-Means方法，其次有K-Medoids方法，PAM方法，C

28、LARA方法，CLARANS方法等。2基于层次聚类的方法:基于层次的聚类方法将数据对象在不同的阶段组成不同粒度的簇，在簇的分裂和合并过程中不断改善聚类的效果，以达到逐步求精的目的。根据层次分解是自底向上还是自顶向下形成，层次的聚类方法可以进一步分为凝聚的(Agglomeration)和分裂的(Divisive)层次聚类。凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。分裂的层次聚类：这种自顶向下的策略与凝聚的层次聚类相反，它首先

29、将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇或者达到了某个终结条件，例如达到了某个希望的簇数目，或者两个最近的簇之间的距离超过了某个阈值。例如，DIANA方法的处理过程中，所有的对象初始都放在一个簇中。根据一些原则（如簇中最临近对象的最大欧氏距离），将该簇分裂。簇的分裂过程反复进行，直到最终每个新的簇只包含一个对象。四个广泛采用的簇间距离度量方法如下：最小距离：最大距离： 平均值的距离：平均距离：这里|p-p,|两个对象p和p,之间的距离，m是簇Ci的平均值，而ni是簇Ci中对象的数目。3基于密度的方法基于密度的聚类方法是为了发现任意形状的聚类结果而提出的。这类方法

30、将簇看作是数据空间中被低密度区域分割开的高密度对象区域。DBSCAN(Density Based Spatial Clustering of Applications with Noise)就是一个基于密度的聚类算法。该算法将具有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。它定义簇为密度相连的点的最大集合。基于密度的聚类的基本想法涉及一些新的定义。 给定对象半径内的区域称为该对象的-邻域。 如果一个对象的-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。 给定一个对象集合D，如果p是在q的-邻域内，而q是一个核心对象，我们说对象p从对象q出发是

31、直接密度可达的。 如果存在对象链，,对,是从关于和MinPts直接密度可达的，则对象p是从对象q关于和MinPts密度可达的(Density-Reachable)。 如果对象集合D中存在一个对象O，使得对象p和q是从O关于和MinPts密度可达的，那么对象p和q是关于和MinPts密度相连的(Density-Connected）。密度可达是直接密度可达的传递闭包，这种关系是非对称的。只有核心对象之间是相互密度可达的。然而，密度相连性是一个对称的关系。一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。DBSCAN通过检查数据库中每个点的-邻域来寻

32、找聚类。如果一个点p的-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象。这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。如果采用空间索引,DBSCAN的计算复杂度是O(nlogn)，这里n是数据库中对象的数目。否则，计算复杂度是O(n2),另外，该算法对用户定义的参数是敏感的。尽管DBSCAN能根据给定输入参数和MinPts对对象进行聚类，但它仍将选择能产生可接受的聚类结果的参数值的责任留给了用户。事实上，这也是许多其它聚类算法的共性问题。对于实际中的高维数据集合而言，参数的设置通

33、常是依靠经验，难以确定。绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。而且，实际中的高维数据集合经常分布不均，全局密度参数不能刻画其内在的聚类结构。4基于网格的方法基于网格的聚类方法采用一个多分辨率的网格数据结构。它将空间量化为有限数目的单元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，仅依赖于量化空间中每一维上的单元数目。基于网格方法的有代表性的例子包括：STING，它利用存储在网格单元中的统计信息；WaveCIuster，它用一种小波转换方法来聚类对象；CLIQUE，它是在高维数据空间中

34、基于网格和密度的聚类方法。STING(Statistical Information Grid)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。高层单元的统计参数可以很容易地从低层单元的计算得到。当这些统计信息用于回答查询时，统计参数的使用可以按照自顶向下的基于网格的方法。首先，在层次结构中选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次的每个单元，我们计算置信度区间（

35、或者估算其概率范围），用以反映该单元与给定查询的关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。这个处理过程反复进行，直到达到底层。此时，如果查询要求被满足，那么返回相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据，直到它们满足查询要求。由于STING采用了一个多分辨率的方法来进行聚类分析，STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量。而且，STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系。因此，结果所有的聚类边界或者是水平的，或者是竖直的

36、，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。WaveCluster也是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。WaveC1uster是一个基于网格和密度的算法。它符合一个好的聚类算法的许多要求：它能有效地处理大数据集合，发现任意形状的簇，成功地处理孤立点，对于输入的顺序不敏感，不要求指定诸如结果簇的数目或邻域的半径等输入参数。在实验分析中，WaveCluster在效率和聚类质量上优于BIRCH，CLARANS和DBSCAN。实验分析也发现WaveCluster

37、 能够处理多达20维的数据。5 基于模型的聚类方法基于模型的聚类方法试图优化给定的数据和某些数学模型之间的适应性。这样的方法经常是基于这样的假设：数据是根据潜在的概率分布生成的。基于模型的方法主要有两类：统计学方法和神经网络方法。下面分别讨论之。1、统计学方法概念聚类是机器学习中的一种聚类方法，给出一组未标记的对象，它产生对象的一个分类模式。与传统的聚类不同，概念聚类除了确定相似对象的分组外，还向前走了一步，为每组对象发现了特征描述，即每组对象代表了一个概念或类。因此，概念聚类是一个两步的过程：首先进行聚类，然后给出特征描述。在这里，聚类质量不再只是单个对象的函数，而且加入了如导出的概念描述的

38、简单性和一般性等因素。概念聚类的绝大多数方法采用了统计学的途径，在决定概念或聚类时使用概率度量。概率描述用于描述导出的概念。COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性-值对来描述。COBWEB以一个分类树的形式创建层次聚类。它采用了一个启发式估算度量分类效用来指导树的构建。COBWEB的工作过程：COBWEB将对象增量地加入到分类树中。给定一个新的对象，COBWEB沿着一条适当的路径向下，修改计数，寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。如果对象不属于树中现有的任何概

39、念，COBWEB就计算为给定对象创建一个新的节点所产生的分类效用。它与基于现存节点的计算相比较。根据产生最高分类效用的划分，对象被置于一个已存在的类，或者为它创建一个新类。COBWEB可以自动修正划分中类的数目。它不需要用户提供这样的输入参数。上面提到的两个操作符对于对象的输入顺序非常敏感。为了降低它对输入顺序的敏感度，COBWEB有两个额外的操作符：合并(Merging)和分裂(Splitting)。当一个对象被加人，两个最好的候选节点可以考虑合并为单个类。此外，COBWEB考虑在现有的分类中分裂最佳的候选节点的孩子。这些决定基于分类效用。合并和分裂操作符使得COBWEB执行一种双向的搜索，

40、例如，一个合并可以撤消一个以前的分裂。当然，COBWEB也有若干局限性。首先，它基于这样一个假设：在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储聚类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。CLASSIT是COBWEB的扩展，用以处理连续性数据的增量聚类。它在每个节点中为每个属性存储一个连续的正态分布（即平均值和标准偏差），采用一个修正的分类效用度量。该度量是连

41、续属性上的积分，而不像COBWEB那样取离散属性上的和。但是，它与COBWEB存在类似的问题，因此不适用于聚类大型数据库的数据。在产业界，AntoClass是一个比较流行的聚类方法，它采用贝叶斯统计分析来估算结果簇的数目。将概念聚类方法应用到数据挖掘中需要进一步的研究。2、神经网络方法神经网络方法将每个簇描述为一个标本(Exemplar)。标本作为聚类的“原型”，不一定对应一个特定的数据实例或对象。根据某些距离度量，新的对象可以被分配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预测。这里，讨论神经网络聚类的两个比较著名的方法。第一个是竞争学习(Competitiv

42、e Learning)，第二个是自组织特征映射（本文还将对其进行更为详细的讨论），这两种方法都涉及有竞争的神经单元。竞争学习采用了若干个单元的层次结构（或者人造的“神经元”），它们以一种“胜者全取(Winner-Take-A11)”的方式对系统当前处理的对象进行竞争。在一个簇中获胜的单元成为活跃的，而其他是不活跃的。各层之间的连接是激发式的(Excitatory)在某个给定层次中的单元可以接收来自低一层次所有单元的输入。在一层中活动单元的布局代表了高一层的输入模式。在某个给定层次中，一个簇中的单元彼此竞争，对低一层的输出模式做出反应。一个层次内的联系是抑制式的(Inhibitory)，以便在任

43、何簇中只有一个单元是活跃的。获胜的单元修正它与簇中其他单元连接上的权重，以便未来它能够对与当前对象相似或一样的对象做出较强的反应。如果我们将权重看作定义一个标本，那么新的对象被分配给具有最近标本的簇。结果簇的数目和每个簇中单元的数目是输入参数。在聚类过程结束时，每个簇可以被看作一个新的“特征”，它检测对象的某些规律性。这样，产生的结果簇可以被看作一个低层特征向高层特征的映射。使用自组织特征映射(Self-Organizing feature Map,SOM)，聚类也是通过若干个单元竞争当前对象来进行的。权重向量最接近当前对象的单元成为获胜的或活跃的单元。为了更接近输入对象，对获胜单元及其最近的

44、邻居的权重进行调整。SOM假设在输入对象中存在一些拓扑结构或顺序，单元将最终在空间中呈现这种结构。单元的组织形成一个特征映射。SOM被认为类似于大脑的处理过程，对在二维或三维空间中可视化高维数据是有用的。神经网络聚类方法与实际的大脑处理有很强的理论联系。由于时间复杂性和数据的复杂性，需要进行进一步的研究来使它适用于大型数据库。聚类分析的特点和目前存在的问题：聚类分析技术的特征是在没有先验知识的前提下，对有原始数据构成的数据集进行数据类别的分析。综上所述，聚类分析目前存在的关键问题为：算法的动态自适应性和运算结果的精确性尚待进一步提高；聚类分析算法的时空复杂度仍待降低；对大数据量、复杂数据类型数

45、据库的聚类分析系统缺乏实用性。针对于目前聚类分析算法多样性，各种算法在不同的问题域中有不同表现的特点，不同方法之间的结合成为聚类分析研究中的一个主要方向。3.基于K-means聚类算法图像分割系统的设计与实现本章首先介绍了图像分割系统的概念，然后又具体给出了系统的结构设计和程序流程设计，最后给出了具体结构的各模块设计实现。3.1 图像分割图象分割是指将图像分解为各具特性的区域并提取出感兴趣目标的技术和过程，它是图像理解、模式识别和计算机视觉领域中一个十分重要且又十分困难的问题,是计算机视觉技术中首要的关键步骤。图像分割的基础就是像素间的相似性和跳变性。所谓相似性是指在某个区域内像素具有某种相似

46、的特性;所谓跳变性，是指特性的不连续。所以图像处理的关键之处就是对包含有大量各式各样景物信息的图像进行分解。分解的最终结果是图像被分解成一些具有某种特征的最小成分，称为图像的基元。相对于整幅图像来说，这种基元更容易被快速处理。图象分割在工业自动化、在线产品检验、生产过程控制、文档图象处理、遥感和生物医学图象分析、图象编码、保安监视,以及军事、体育和农业工程等方面已得到广泛的应用。彩色图象分割是指在一幅彩色图像中分离出主要的色彩一致的区域，随着技术的进步,彩色图像使用的越来越多,对彩色图像的分割也越来越引起人们的重视。3.2 RGB和HSV颜色空间3.2.1 RGB颜色空间RGB(red, gr

47、een, blue)是最流行的颜色空间。计算机颜色显示器显示颜色的原理与彩色电视机一样，都是采用R、G、B相加混色的原理，通过发射出三种不同强度的电子束，使屏幕内侧覆盖的红、绿、蓝磷光材料发光而产生颜色的。这种颜色的表示方法称为RGB颜色空间表示。在多媒体计算机技术中，用得最多的是RGB颜色空间表示。 根据三基色原理，用基色光单位来表示光的量，则在RGB颜色空间，任意色光F都可以用R、G、B三色不同分量的相加混合而成： Fr R + g G + b B 我们可知自然界中任何一种色光都可由R、G、B三基色按不同的比例相加混合而成，当三基色分量都为0（最弱）时混合为黑色光；当三基色分量都为k（最强）时混合为白色光。任一颜色F是这个立方体坐标中的一点，调整三色系数r、g、b中的任一系数都会改变F的坐标值，也即改变了F的色值。RGB颜色空间采用物理三基色表示，因而物理意义很清楚，适合彩色显像管工作。然而这一体制并不适应人的视觉特点。因而，产生了其他不同的颜色空间表示法。3.2.2 HSV颜色空间HSV(hue, saturation, value)表示色相、饱和度和亮度，这个颜色空间的模型对应于圆柱坐标系中的一个圆锥形子集，圆锥的顶面对应于V=1，它包含RGB模型中的R=1，G=1，B=1三个面，所代表的颜