基于聚类的智能图像分析算法
摘要
智能图像处理技术在众多领域得到了广泛应用。在具有监控、报警等功能的安防系统中，在自然基因显微系统中，在模式识别系统中等，智能图像处理技术都起到了不可小觑的作用。
目前基于内容的智能图像识别与分类技术在准确性具体应用方面还面临着许多难题。本文通过介绍智能图像分析方法及相关算法理论，重点研究以SVM算法为代表的监督分类算法及以k-means聚类算法为代表的费监督分类算法，并结合Hu图像矩不变特征，对图像进行聚类分析及分类。在理论学习的基础上，运用MatLab实现算法并验证应用效果。
有监督分类方面，本文采用了提取能够较好的保持图像的边缘、形状等特性的Hu 矩不变特征作为训练特征，分类方法采用了基于聚类的SVM算法。在提取出训练样本的特征值后，将其输入SVM的训练网络进行训练。最后将待分类图片输入即可得到分类结果。本文计算出了该非监督分类方式分类结果的准确性，并对其进行了分析与讨论。
无监督分类方面，本文采用了k-means分类方法。预先设定好分类的类别数后，输入待分类图片，则系统通过调用分类函数，将自动分类的结果输出。
在算法研究的基础上，设计并实现了水果图像智能分析应用系统，具有创建特征值数据库、创建训练网络、图像有监督分类和图像无监督分类等功能。当进行图像有监督分类，即SVM算发分类时，准确率可达到将近70%。
关键词SVM k-means图像分类
Intelligent Image Analysis Based on Clustering Algorithm
ABSTRACT
Intelligent image processing technology has been widely applied in many fields. In monitoring and alarm security system, in natural gene microscope, and in the middle pattern recognition system, intelligent image processing technology has played highly important role.
Currently content-based image recognition and classification of intelligent technology are facing many problems in specific application for accuracy. This paper will describes intelligent image analysis method and algorithm theory, meanwhile combines with the same characteristics of HU image moments, and focuses on the SVM algorithm for classification and supervision of representatives of the costs of supervised classification algorithms. In the theoretical study, verify the application of results based on the use of MatLab algorithm.
In the phase of supervising classification, this paper used Hu moments invariant feature as a training feature that can keep the extracted image edge, shape and other characteristics using SVM-based clustering algorithm. After extracting samples? characteristic value, put into SVM?s training network to have training. Finally the input image can be classified by the classification results. This paper concludes the approach to the classification of non-supervised classification accuracy of the results meanwhile analyzes and discusses the accuracy.
This paper used K-menas classification method in the field of unsupervised classification. After pre-configuring data, put into classified image, and then by calling the classification function, the system will output the results of automatic classification.
Based on algorithm, design and implementation of fruit intelligent image analysis application system with a characteristic value database, training network, image supervised classification and image unsupervised classification features. When the image has supervised classification, the SVM classification count classification, the accuracy rate can reach nearly 70%.
KEY WORDS SVM k-means Image classification
目录
第一章绪论 (1)
1.1智能图像分析概述 (1)
1.1.1课题背景 (1)
1.1.2国内外研究现状 (2)
1.2聚类分析 (3)
1.3课题目标及本文研究内容 (3)
1.3.1预期目标 (3)
1.3.2主要研究内容 (3)
1.3.3系统方案 (4)
1.3.4本文的结构 (4)
第二章技术基础 (5)
2.1图像特征 (5)
2.2图像分类方法 (5)
2.2.1图像分类概念 (5)
2.2.2图像分类原理 (6)
2.2.3图像分类方法 (6)
2.3MatLab及图像智能处理工具箱 (7)
第三章图像矩不变特征提取 (9)
3.1图像矩不变特征介绍 (11)
3.2图像矩不变特征提取 (12)
第四章分类算法 (14)
4.1SVM分类算法 (14)
4.2k-means分类算法 (16)
第五章基于MatLab的图像分析软件实现 (19)
5.1软件功能及系统流程 (19)
5.2关键函数详述 (19)
5.2.1图像灰度化 (19)
5.2.2图像平滑与图像锐化 (20)
5.2.2.1中值滤波 (20)
5.2.2.2图像锐化 (21)
5.2.3Hu矩不变特征值 (21)
5.2.4SVM神经网络的建立和训练 (22)
5.2.5k-means分类函数 (24)
第六章系统测试 (26)
6.1系统界面 (26)
6.2功能测试及统计 (30)
6.2.1训练样本 (30)
6.2.2结果与分析 (30)
第七章结论与展望 (33)
7.1结果与结论 (33)
7.2问题与展望 (33)
7.3心得体会 (33)
参考文献 (35)
致谢 (36)
北京邮电大学本科毕业设计（论文）
第一章绪论
1.1智能图像分析概述
随着我国人民生活水平的提高，数码相机、DV机等摄影器材得到了极大范围的普及，数字图像的数量也在飞速增长，同时，互联网的普及使得人们对于图像检索的需求大大增加。近年来，为了满足人们日益增长的生活、学习、工作、娱乐等各方面的需要，数字图书馆中储存了数以万计的图像。
图像处理技术从一开始就是一个基于线性代数、统计理论和物理学之上，具有很强理论背景的研究领域，它需要广泛的基础知识，包括计算机科学、数字信号处理、随机过程和统计数学、矩阵分析、信息论、控制论和最优化理论等。同时，图像处理又是一门与应用紧密结合的学科，应用领域涉及计算机视觉、地理、气象、航空航天、医疗保健、刑事侦查等。
1.1.1课题背景
在20世纪初，运用机器来处理图片是一件非常困难的事。但随着计算机硬件、图像获取设备、显示设备的不断改进和各种高性能能工作站的出现，图像处理技术迅猛发展。而信息时代的到来，又无疑使图像处理技术进入了一个更加蓬勃发展的阶段，特别是以多媒体技术、通信技术、信息存储技术和以Internet为代表的计算机网络技术的加速发展以及高清晰度电视的深入应用研究，图像处理技术研究和应用前景更为广阔。
数字图像处理所涉及的知识非常广泛，具体的研究方法种类繁多。传统的图像处理技术主要集中在图像的获取、变换、增强、恢复（还原）、压缩编码、分割与边缘提取等方面，并且随着新工具、新方法的不断出现，这些图像处理技术也一直在更新与发展。近十多年来，随着信息技术的发展，图像特征分析、图像配准、图像融合、图像分类、图像识别、基于内容的图像检索与图像数字水印等领域取得长足的进展。这些图像处理技术反映了人类的智力活动，它在计算机上模仿、延伸和扩展了人的智能，具有智能化处理功能，因而称之为智能图像处理技术。其中最具代表性的是图像分类技术以及基于内容的图像检索。
图像分类就是利用计算机对图像进行定量分析，把图像中的每个像元或区域划归为若干个类别中的一种，以代替人的视觉判读。图像分类的过程就是模式识别的过程，是目视判读的延伸和发展。
图像分类主要用于遥感、医学与军事等领域。以遥感图像分析为例，遥感技术是通过对遥感传感器接收到的电磁波辐射信息特征的分析来识别地物类型的，这可以通过人工目视解释来实现，或是用计算机进行自动分类处理，也可以用人工目视解释与计算机自动分类处理相结合来实现。用计算机对遥感图像进行地物类型识别是遥感图像数字处
理的一个重要内容，也是模式识别技术在遥感技术领域中的具体应用。
基于内容的图像检索就是根据图像的语义和感知特征进行检索，具体实现就是从图像数据中提取出特定的信息线索（或特征指标），然后根据这些线索从大量存储在图像数据库的图像中进行查找，检索出具有相似特征的图像数据。与传统的基于关键词的数据库检索相比，具有相似度检索、近似检索和要求给出检索结果的集合限制等特点。
人们常说“物以类聚，人以群分”。面对数量庞大的图像信息，寻找一种方便快捷、直接有效的对图像进行分类方法已经成为进行图像处理工作的重要基础和必不可少的重要环节，尤其是对于基于内容的图像检索具有极其重要的作用。聚类分析分类方法是先对图像按照某种相似性原则进行聚类，把相似的图像聚合为一类，检索过程在类内进行，从而大大的缩小图像检索范围，就能够达到快速、准确检索图像的目的。
1.1.2国内外研究现状
人类从一出生，人眼就在不断地接受、分析和理解周围的景物，这是人类的一种本能活动。在计算机技术的不断发展中，人类更是将这一本能发挥的淋漓尽致。在20世纪70-80年代，图像处理的研究方向主要集中于用图像变换和数学模型来表征图像信号。20世纪80年代中期，各种高性能的工作站和个人电脑应用的普及使图像处理研究和应用不再仅仅是大机构和大型学术团体的“专利”。现在随着Internet的广泛普及。图像处理技术和应用前景将更为广阔。
从应用的角度来看，数字照相技术、电子影像、数字化电视机、图像数据库和多媒体技术的出现都在推动这一领域不断地向前发展。总的来说，图像处理技术将不再局限于电子工程研究领域，它已设计到其他学科，如计算机科学、地理、医疗保健、刑事侦查等领域。另外，除了处理位于可视频谱范围的图像信号外，在过去的20年里，对射电望远镜形成的图像、红外图像、合成孔径雷达（Synthetic Aperture Radar.SAR）图像的研究都非常活跃。特别是CT和核磁共振的利用都极大地丰富了这一领域研究的内容。除了上述这些研究领域外，图像处理技术研究人员还积极地眷力于纹理和图形形状的分析与识别、运动检测与估计、图像处理并行系统、图像处理技术的软硬兼研究等工作。
由于图像处理技术从一开始就具有很强的理论背景，因此一些具有高鲁棒性的图像处理算法已经应用到消费类型的产品中，一些较成熟的算法也已逐步形成公认的标准。如在20世纪80年代末逐步规划形成、20世纪90年代全面公布的H.263，JEPG，MPEG-2等图像压缩与传输标准使图像处理技术在产业化方面取得巨大的成功。最近的成果也将在JPEG2000标准中体现——标准中将用近年来图像变换研究的新成果：小波变换来取代原来的DCT变换，这是因为小波变换克服了傅里叶变换不具有时频局部性质的缺陷，并且和DCT一样具有快速算法。
图像处理技术发展非常快，随着基础理论研究的不断推前、更新，各种新颖的图像处理技术层出不穷。就近年来产生了大量研究结果的图像分类算法来说，从有无监督的
监督划分为有监督分类和无监督分类。无监督分类方法中K-means分类方法得到了广泛的研究，Paredes等利用K-means算法对训练图像块区生成的KD树进行类似类别搜索，得到了不错的分类效果。但传统K-means算法搜索匹配效率低，特别是对于高维的大型数据集，搜索分类非常费时。Stefan Berchtold 等提出了一种预先计算K-means不相似测度的动态解空间的方法，简化了计算，提高了搜索分类效率。Bin Zhang等采用基于聚类的树算法加速K-means，而不用预先计算K-means不相似测度的特性和矩阵式，从而更大的加快了算法的速度，并减小了计算准确性的损失。另一类在图像分类中广泛使用的有监督分类方法是支持向量机（SVM）分类。何灵敏等采用基于径向基核函数的SVM方法对遥感图像分类，并证实采用一对多的SVM分类方法比BP神经网络方法更适合于对复杂小样本多原数据的分类，蒋芸等将粗糙集理论与SVM结合起来，利用粗糙集理论处理大数据量、消除冗余信息等方面的优势，减少训练数据，提高了SVM的分类能力。大部分SVM方法都采用单一的核函数的类型，当采用局部核函数则学习能力强、泛化性能较弱，采用全局性核函数则泛化性能强、学习能力较弱。
1.2聚类分析
聚类分析(cluster analysis)是一种将研究对象分为相对同质的群组(clusters)的统计分析技术。聚类分析也叫分类分析(classification analysis)或数值分类(numerical taxonomy)，是用数学的方法来研究和处理给定对象的分类,即对同类型对象抽象出其共性,从而形成类。
聚类分析是一种数值分类方法（即完全是根据数据关系）。要进行聚类分析就要首先建立一个由某些事物属性构成的指标体系，或者说是一个变量组合。入选的每个指标必须能刻画事物属性的某个侧面，所有指标组合起来形成一个完备的指标体系，它们互相配合可以共同刻画事物的特征。所谓完备的指标体系，是说入选的指标是充分的，其它任何新增变量对辨别事物差异无显著性贡献。如果所选指标不完备，则导致分类偏差。
简单地说，聚类分析的结果取决于变量的选择和变量值获取的两个方面。变量选择越准确、测量越可靠，得到的分类结果越是能描述事物各类间的本质区别。
1.3课题目标及本文研究内容
1.3.1预期目标
本论文拟将智能分类技术应用于图像的自动识别，以水果图像分类为目标,研究其特征提取方法及智能分类算法，实现基于Matlab平台的水果图像智能分析软件。
1.3.2主要研究内容
论文主要研究内容包括：
图像特征提取方法研究：分析图像的典型特征,并研究Hu矩不变特征值的计算方法。
分类算法研究:在理解算法原理的基础上运用算法，实现算法功能并分析比较算法性能。
智能图像分析软件实现: 系统以MatLab为平台，通过用户界面形式实现了基于聚类的智能图像分类软件，具有建立根据现有图库训练网络、对任一图像实现分类并以图文结合方式展现分类结果等功能。
1.3.3系统方案
论文以水果图像的分类为目标，通过图像的预处理、特征提取与分类，基于MatLab 实现图像的智能分析。在图像预处理阶段，系统将对输入图像进行灰度化、中值滤波以及锐化并提取图像边缘的操作。特征提取阶段，系统将计算出输入图像的圆度、拉伸度、周长等中间值，将这些必要的中间值带入Hu特征迭代计算公式，即可获得后续处理所需要的特征值向量。分类阶段，系统为用户提供了选择界面。当使用者选择SVM分类方法时，系统将通过使用图库训练学习的方式得到分类结果。当使用者选择K-means分类时，系统将得到自主聚类的分类结果。
1.3.4本文的结构
本文分为七个部分，各部分的内容依次如下：
第一章，绪论。介绍要解决的主要问题问题。
第二章，技术基础。介绍本文涉及到的知识以及使用的工具。
第三章，图像矩不变特征提取。对本文采用的训练特征进行详细介绍。
第四章，分类算法。对本文用到的两类不同的分类算法进行详细介绍。
第五章，算法软件实现。对系统涉及的核心算法、关键函数以及系统界面进行详细的介绍。
第六章，系统测试。
第七章，结论与展望。论文的成果总结及不足展望。
第二章技术基础
2.1图像特征
图像特征指的是图像场中可用作图像标志的属性，通常可以分为统计特征与视觉特征两大类。统计特征包括直方图、频谱和矩等，是人为特征，需要经过变换才能得到。视觉特征指的是具有直观意义的图像的形状与颜色特征，如颜色、纹理、形状等。图像特征的提取和分析是智能图像分析的关键步骤。近年来，随着多媒体技术的发展，许多图像特征被研究人员发掘并利用，为进一步的图像处理提供了极大地便利。
对于某幅特定图像，根据不同的需要，通常要提取其不同的特征，因而一幅图像又有了许多不同的表达方式。也就是说，图像的不同特征从各个角度反映了图像在这个特定维度中的特点。
在图像统计特征中，直方图描述的是图片显示范围内的灰度分布曲线，它的横轴从左到右代表照片从黑（暗部）到白（亮度）的像素数量。频谱是以横轴纵轴的波纹方式，记录画出图像中包含的各种信号频率的图形资料，是图像信号的频域表征。矩特征表征了图像区域的几何特征,又称为几何矩，其具有平移、旋转、尺度等特性的不变特征，又称其为不变矩。也是本文中应用到得特征。
在视觉特征中，颜色特征是一种全局特征,表征了图像区域所对应的景物的表面性质，是基于像素点的特征。纹理特表征了图像区域所对应景物的表面性质征，也是一种全局特征，但是纹理特征不是基于像素点的特征，它需要在包含多个像素点的区域中进行统计计算。形状特征由其集合属性（长短、距离、面积、凹凸）、统计属性（投影）、拓扑属性（欧拉数、连通）表征，是图像最本质的特征反映。不变矩特征由于其在图像平移、伸缩、旋转时均保持不变，而且具有全局性，是图像识别的主要方法，广泛的应用于机器视觉、目标识别与分类、纹理分析等等。Hu首先提出了七个几何不变矩用于图像识别，利用不变矩进行形状识别获得了广泛的应用。后来人们进行了多方面的研究，发现不变矩还具有绝对的独立性，没有信息冗余现象，抽样性能好，抗噪能力强，更适合用于几何不变图像描述和识别。本文就将使用到Hu的不变矩特征。
2.2图像分类方法
2.2.1图像分类概念
从人眼角度看，提高图像对比对、增加视觉维度、进行空间变换或滤波，其目的就是让人们能够凭借知识和经验，根据图像色调、亮度、位置、纹理以及结构等特征，准确的对图像类型或者目标，做出正确的判断和解释，并根据当下的需求，对所需图像进行绘制处理。
图像分类就是通过计算机对图像进行定量的分析的过程，把图像中的各个像素或者
区域划归到若干类别中的一类去，以代替人眼的视觉判读。图像分类的过程其实是一个模式识别的过程，是人眼目视判读的延续以及发展。图像分类具有计算精度高、速度快、图像测量准确度高等特点。
2.2.2 图像分类原理
图像分类的理论依据是：图像中的同类景物在相同条件下，应具有相同或类似的光谱信息特征，从而体现出某种同类景物的某种内在相似性，即同类景物像素的特征向量将聚类于同一特征的空间区域，从而不同的景物的光谱信息特征和空间信息特征不同，它们将聚类于不同特征的空间区域。
从统计决策理论来看，图像分类在数学上就是对呈现统计可变的数据作出决策的过程。将一个像素归入任一类别的决策，可以说是统计上的一种明智的“猜测”。统计决策比较成熟，对模式不太复杂的应用已经相当的成功，但不能反映模式结构特性，概率表示形式使使用上也存在局限性。
神经网络分类方法是只能信息处理的重要内容，它可以处理一些环境复杂、背景不清楚、推理规则不明确的问题。
2.2.3 图像分类方法
用统计方法进行图像分类时，首先从待分类对象中提取能够反映对象属性的特征向量，并将这些向量定义在一个特征空间之中。之后运用统计决策的方法对特征空间进行划分，用以区分不同特征对应的对象，进而达到分类的目的。同时，在分类的过程中，按照有无样本学习可以分为非监督分类法和监督分类法。
监督分类就是用已知的类别样本选择特征参数和建立判别函数，对各个像素进行分类。通常意义上的监督分类包含以下两个具体的分类方法。
1. 最小距离分类法
最小距离分类法是最简单的监督分类方法。这种方法的基本思想是：从训练样本中提取各个类别对应的均值向量并求出待测向量到各个均值向量的距离，比较后将待测类别归入距离最小的一类中。
设待分类像素T n x x x x ]...[21=到类别i ω的距离为
式（2-1）
其中，m 为类别数，i z 为类i ω的中心。
当
则 i x ω∈
}{min 1j m
j i d d <<=||
||i i z x d -=）（m i ,...,2,1=
2. 最大似然分类（多类分类）
最大似然分类建立在贝叶斯准则上，其分类正确率最高，是风险最小的判决分析。在n 维特征空间中，待测像素T n x x x x ]...[21=对于类i ω的条件概率密度函数)/(i x P ω和类
i ω的先验概率)(i P ω均已知，则最大似然分类法建立的判别函数集为：
)/()()(i i i x P P x D ωω=（m i ,...2,1=）
式（2-2） 若
)}({min )(1x D x D j m j i <<= 则 当x 服从高维正态分布时，有 )]()(2
1ex p[||)2(1
)/(1212i i T i i z x z x i x P n -∑--∑=-πω 式（2-3） 而非监督分类则需要在进行分类之前获得类别的先验属性，通过这个属性求出判别函数中的未知参数。在先验属性未知的情况下将所有样本就将所有样本划分为若干个类别的方法称为费监督分类，这种方法是根据像素间的相似度大小进行聚类。在聚类过程中，通常是按照某种相似性准则来对样本进行合并或分离。
像素聚类有两种途径：迭代法与非迭代法。迭代法先给定一个初始分类，然后通过迭代算法找到能够使准则函数取极值的最优聚类结果，因此这是一个动态聚类分析过程。常用动态聚类法有K-means 算法、LBG 算法和分裂算法。
2.3 MatLab 及图像智能处理工具箱
MatLab 是Matrix Laboratory （矩阵实验室）的缩写，是一款由美国Math Works 公司出品的商业数学软件。MatLab 是一款用于数据可视化、算法开发、数据分析以及数值计算的高级技术计算语言和交互式环境。除了矩阵运算、绘制函数/数据图像等常用功能外，MatLab 还可以用来创建用户界面及与调用其它语言（包括C ，C++和FORTRAN ）编写的程序。
尽管MatLab 主要用于数值运算，但利用为数众多的附加工具箱（Toolbox ）它也适合不同领域的应用，例如图像处理、控制系统设计与分析、信号处理与通讯、金融建模和分析等。另外还有一个配套软件包Simulink ，提供了一个可视化开发环境，常用于系统模拟、动态/嵌入式系统开发等方面。
本系统的功能实现就是是借助MatLab 的工具箱完成的。Vapnik 经过多年研究，提出了统计学理论和一种新的经验建模工具：支持向量机（Support Vector Machine,SVM ）。SVM 的训练是依据统计学理论中的结构风险最小化原则，在最小化经验风险的同时最小化SVM 的模型复杂度，提高了模型的泛化能力。尽管如此，SVM 训练为一个有约束的二次规划问题，其约束条件数等于训练样本容量，因此在用于大训练样本容量的建模
i
x ω∈
问题时，会导致训练时间过长。针对SVM这一缺点，Suykens提出了损失函数为二次函数，约束条件为等式形式的支持向量机：最小二乘支持向量机（Least Squares Support Vector Machine,LSSVM）。LSSVM的训练问题为一个线性方程组求解问题，相对于SVM 训练的二次规划问题求解，其计算量有了很大的降低。
此次系统所用的工具包为由比利时鲁汶大学的K.Pelckmans以及J.A.K.Suykens等开发的LS-SVMlab Toolbox（Version 1.5）。此工具箱实现了基于SVM算法的多类分类。此外，在展现运行结果时用到了MatLab中的GUI用户界面设计。图形用户界面（Graphical User Interface，简称 GUI，又称图形用户接口）是指采用图形方式显示的计算机操作用户接口。
第三章图像矩不变特征提取
常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。
一颜色特征
（一）特点：颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。
（二）常用的特征提取与匹配方法
颜色直方图。其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。
（三）常用的颜色空间：RGB颜色空间、HSV颜色空间。
颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。
二纹理特征
（一）特点：纹理特征也是一种全局特征，它也描述了图像或图像区域所对应景物的表面性质。但由于纹理只是一种物体表面的特性，并不能完全反映出物体的本质属性，所以仅仅利用纹理特征是无法获得高层次图像内容的。与颜色特征不同，纹理特征不是基于像素点的特征，它需要在包含多个像素点的区域中进行统计计算。在模式匹配中，这种区域性的特征具有较大的优越性，不会由于局部的偏差而无法匹配成功。作为一种统计特征，纹理特征常具有旋转不变性，并且对于噪声有较强的抵抗能力。但是，纹理特征也有其缺点，一个很明显的缺点是当图像的分辨率变化的时候，所计算出来的纹理可能会有较大偏差。另外，由于有可能受到光照、反射情况的影响，从2-D图像中反映出来的纹理不一定是3-D物体表面真实的纹理。
（二）常用的特征提取与匹配方法
纹理特征描述方法分类
（1）统计方法统计方法的典型代表是一种称为灰度共生矩阵的纹理特征分析方法Gotlieb 和Kreyszig 等人在研究共生矩阵中各种统计特征基础上，通过实验，得出灰度共生矩阵的四个关键特征：能量、惯量、熵和相关性。统计方法中另一种典型方法，则是从图像的自相关函数（即图像的能量谱函数）提取纹理特征，即通过对图像的能量谱函数的计算，提取纹理的粗细度及方向性等特征参数
（2）几何法
所谓几何法，是建立在纹理基元（基本的纹理元素）理论基础上的一种纹理特征分
析方法。纹理基元理论认为，复杂的纹理可以由若干简单的纹理基元以一定的有规律的形式重复排列构成。在几何法中，比较有影响的算法有两种：V oronio 棋盘格特征法和结构法。
（3）模型法
模型法以图像的构造模型为基础，采用模型的参数作为纹理特征。典型的方法是随机场模型法，如马尔可夫（Markov）随机场（MRF）模型法和Gibbs 随机场模型法（4）信号处理法
纹理特征的提取与匹配主要有：灰度共生矩阵、Tamura 纹理特征、自回归纹理模型、小波变换等。
灰度共生矩阵特征提取与匹配主要依赖于能量、惯量、熵和相关性四个参数。Tamura 纹理特征基于人类对纹理的视觉感知心理学研究，提出6种属性，即：粗糙度、对比度、方向度、线像度、规整度和粗略度。自回归纹理模型（simultaneous auto-regressive, SAR）是马尔可夫随机场（MRF）模型的一种应用实例。
三形状特征
（一）特点：各种基于形状特征的检索方法都可以比较有效地利用图像中感兴趣的目标来进行检索，但它们也有一些共同的问题，
（二）常用的特征提取与匹配方法
通常情况下，形状特征有两类表示方法，一类是轮廓特征，另一类是区域特征。图像的轮廓特征主要针对物体的外边界，而图像的区域特征则关系到整个形状区域。
几种典型的形状特征描述方法：
（1）边界特征法该方法通过对边界特征的描述来获取图像的形状参数。其中Hough 变换检测平行直线方法和边界方向直方图方法是经典方法。Hough 变换是利用图像全局特性而将边缘像素连接起来组成区域封闭边界的一种方法，其基本思想是点—线的对偶性；边界方向直方图法首先微分图像求得图像边缘，然后，做出关于边缘大小和方向的直方图，通常的方法是构造图像灰度梯度方向矩阵。
（2）傅里叶形状描述符法
傅里叶形状描述符(Fourier shape descriptors)基本思想是用物体边界的傅里叶变换作为形状描述，利用区域边界的封闭性和周期性，将二维问题转化为一维问题。由边界点导出三种形状表达，分别是曲率函数、质心距离、复坐标函数。
（3）几何参数法
形状的表达和匹配采用更为简单的区域特征描述方法，例如采用有关形状定量测度（如矩、面积、周长等）的形状参数法（shape factor）。在QBIC 系统中，便是利用圆度、偏心率、主轴方向和代数不变矩等几何参数，进行基于形状特征的图像检索。
四空间关系特征
特点：所谓空间关系，是指图像中分割出来的多个目标之间的相互的空间位置或相对方向关系，这些关系也可分为连接/邻接关系、交叠/重叠关系和包含/包容关系等。通常空间位置信息可以分为两类：相对空间位置信息和绝对空间位置信息。前一种关系强
调的是目标之间的相对情况，如上下左右关系等，后一种关系强调的是目标之间的距离大小以及方位。显而易见，由绝对空间位置可推出相对空间位置，但表达相对空间位置信息常比较简单。
空间关系特征的使用可加强对图像内容的描述区分能力，但空间关系特征常对图像或目标的旋转、反转、尺度变化等比较敏感。另外，实际应用中，仅仅利用空间信息往往是不够的，不能有效准确地表达场景信息。为了检索，除使用空间关系特征外，还需要其它特征来配合。
常用的特征提取与匹配方法：
提取图像空间关系特征可以有两种方法：一种方法是首先对图像进行自动分割，划分出图像中所包含的对象或颜色区域，然后根据这些区域提取图像特征，并建立索引；另一种方法则简单地将图像均匀地划分为若干规则子块，然后对每个图像子块提取特征，并建立索引。
3.1图像矩不变特征介绍
矩特征主要表示了图像区域内的几何特征,又称为几何矩，由于其具有平移、旋转、尺度等特性的不变特征，所以又称其为矩不变。在图像处理中，几何矩不变可以被用来当做一个重要的特征来表示物体，可以据此特征来对图像进行分类等操作。
几何矩是在在1962年被Hu(Visual pattern recognition by moment invariants)提出的，矩不变的主要思想是通过使用对变换不敏感的基于区域的几个矩作为形状特征。矩是描述图像特征的算子，在图像分析与模式识别领域中有重要的应用。迄今为止，常见的矩描述子可以分为以下几种：正交矩、几何矩、旋转矩和复数矩。其中几何矩最早被提出并且形式最简单，所以对它的研究最为充分。几何矩对简单图像有一定的描述能力，虽然在区分度上不如其他三种矩，但与其他算子比较起来，较为简单，一般通过一个数字就可表达。
矩不变特征的优越性，特别是其具有的旋转不变形、图形的扭曲伸缩等不变形，对于本系统的分类训练具有极其重要的作用。比如，输入系统的待分类图片中的感兴趣区域很可能由于拍摄角度的问题扭曲、拉伸、变形等，但是矩不变特征的这一特性很好的避免了此类操作造成的误差，提高了系统的分类准确度。以下是两个矩不变特征的图像检索实例。
图3-1 旋转不变性
图3-2 扭曲、伸缩性变不变性
从图3-1中的图像检索结果可以看出，形状检索算法对于图像的旋转具有不变性。图3-2检索的结果证明形状检索算法对于图像的扭曲。伸缩形变具有不变性，并对图像的基本形状特性具有鲁棒性，在具有一定形变的干扰情况下，仍能得出较好的图像检索结果。
3.2 图像矩不变特征提取
数字图像是通过一个数字矩阵表征的。图像f(x ，y)的(p+q)阶几何矩定义为: 式中),(y x f 是图像的灰度。
矩在统计学中通常被用来反映随机变量的分布情况，当被推广到力学中，它用作描述空间物体的质量分布。同理，如果我们将图像的灰度值看作是一个二维或三维的密度分布函数，则矩方法就可用于图像分析领域并且用作图像特征的提取。最常用的，物体的零阶矩显示了图像的“质量”：
?
?
∞
∞
-∞
∞
-=dxdy y x f ),(m 00 式（3-1）
一阶矩(10
01m ,m )用于确定图像质心(
c
c Y X ,)：
00
010010m /m ;m /m ==c c Y X 式（3-2）
若将坐标原点移至c
X 和
c
Y 处，就得到了对于图像位移不变的中心矩。如
dxdy
y x f Y y X x M
x N
y q c p c pq ),()()(11
∑∑==--=μ...)2,1,0,(=q p
式（3-3）
Hu 在文中提出了7个几何矩的不变量，这些不变量满足于图像平移、伸缩和旋转
不变。如果定义
pq r pq pq μμη/=
2/)(q p r +=，,...3,2=+q p
Hu 的7种矩为：
在本系统中，使用SVM 神经网络对图像进行分类时，需要提取图像的Hu 矩不变特征。特征提取具体步骤如下：
（1）对初始图库图像和待分类图像进行二图像滤波、直方图均衡、图像均衡、边缘检测、二值法锐化等预处理，将目标从背景中分割出来。经过以上步骤后，目标被突出，图像背景被弱化，从而使目标更容易辨识；
图3-3 图像分割与特征提取
（2）通过MatLab 中的自有函数对初始图库图像和待分类图像进行提取面积、矩形度、原型度、拉伸度以及周长等特征值，为之后的Hu 矩不变特征做好准备；
（3）通过带入步骤（2）的运算结果计算出初始图库图像和待分类图像的面积、矩形度和伸长度。并按照上文提到的算法计算出每幅图像的7个矩不变特征。这样一来每幅图像就包含了10个特征值，建立一个数组，将特征值存储进去即可。
])()(3)[)(3(])(3))[()(3())((4])(3))[((])()(3)[)(3(])(3))[()(3()
()()3()3(4)(2032121230032112302032121230123003217032112301120321212300220620321212300321032120321212301230123052
03212123042
032121230311
2
20220202201ηηηηηηηηηηηηηηηηφηηηηηηηηηηηφ
ηηηηηηηηηηηηηηηηφ
ηηηηφηηηηφηηηφηηφ+-++--+-++-=++++-+-=+-++-++-++-=+++=-+-=+-=+=
第四章 分类算法
本系统在图像分类的功能上，既使用到了监督分类方法，又使用到了非监督分类方法。一下就将这两种分类方法对应的具体算法进行主要介绍。本文使用到了支持向量机分类算法（SVM ）以及K-means 分类算法。
4.1 SVM 分类算法
1. 算法简介
支持向量机（SVM ，Support Vector Machine ）是在高维特征空间使用线性函数假设空间的学习系统。它将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面。分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。支持向量机由一个来自最优化理论的学习算法训练，该算法实现了一个由统计学习理论导出的学习偏置[1]。
2. 算法详述 （1）二类分类
SVM 是从线性可分情况下的最优分类面发展而来的，主要思想可用图1的两维情况说明。
图中，实心点和空心点代表两类样本，H 为分类线，H1、H2分别为过各类中离分
类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔（margin ）。所谓最优分类线就是要求分类线不但能将两类正确分开（训练错误率为0），而且使分类间隔最大。分类线方程为 0=+?b w x 。
对于二类模式分类问题，设有训练样本n i y x i i ,...,2,1},,{:S 1=，其中为模
式向量，}
1,1{-+∈i y 为类别标号，n 为样本容量，则将SVM 优化问题约束条件由不等
式改为等式，并将经验风险函数改为二次函数，则可得如式（4-1）所示约束优化问题：
图4-1 最优分类面
p
i x ?∈
..221),,(min 2
1
t s e w w e b w J i
n i T i =∑+?=γ n
i e b x w y i i T i ,...,2,1,1])([=-=+??? 式（4-1）
式中，
b
x w i T +?)(?为高维特征空间中的分类超平面，w 和b 为分类超平面的参数；
i
e 为第i 个样本点的训练误差，则
2
1
i
n
i e =∑为经验风险；2||||w w w T =?衡量了学习机器的复杂
性；0>γ为惩罚因子，作用是在训练中平衡学习的复杂性和经验风险。 根据约束优化理论，式（4-1）的解由其对应的如式（4-3）所示的Lagrange 泛函数
的鞍点给出：
}
1])([{),,();,,(1i i T i i n
i e b x w y a e b w J a e b w L +-+?∑-==? 式（4-3）
式中i a
为Lagrange 乘子，取值为一切实数。根据式（4-3）的鞍点条件，可得下式：
????????????
?=-=+???=???=?=??=??=??=?=??∑=n i e b x w y e a e y a b x y w w i T i i
T
n
i i i i ,...,2,1,1])([0L 0L 00L )
(0L
1
?αγ?α 式（4-4）
从式（4-4）的第三式可知，
i α正比于其对应的样本上的训练误差。将上述式子合
并，可通过如下式所示的线性方程组求解出
i α和b 。
??????=??????????????+Ω-1001a b I y y T
γ
式（4-5）
式（4-5）中，I 为n 维的单位矩阵，1为n 维的元素全是1的列向量，Ω为n 维对称方阵，其元素为),
()(,j T i j i j i x x y y ???=Ω其中
),
,()()(j i j T i x x k x x =???而),(??k 为核函
数，因此
)
,(,j i j i j i x x k y y =Ω为Ω的第i 行j 列元素。
求解（2.20）得到b 和a 之后，则可以得到如下的分类函数：
∑=+=n
1
j j j j b )x k(x,y (x)y
?α 式（4-6）
模式向量x 的类别由判别函数))(?sgn(c(x )x y =决定，其中)sgn(?为符号函数。
（2）多类分类
显然上述分类只能应用于二类模式分类问题，当LSSVM 应用于多类问题时，假设
∑∑∑===+?=l t i k n k l i i T i i k i e w w e b w J 12
,11,i 221),,(min γ
给定l 类分类问题的训练样本,,...2,1},,{:2n i y x S j i =其中j y 为l 维的由-1和+1组成的
l 维向量，当i x 为第j 类时，j y 的第j 个元素为-1，其余皆为+1。将训练样本2S 存储为两个数据矩阵X 和Y ，它们的第i 行分别为i i y x 和。根据SRM 原则可得到式（4-7）所示的约束优化问题：
?????
??=-=+?-=+?-=+?n k e b x w y e b x w y e b x w y t s l k l k T l l k k k T k k k T k ,...,2,1,1])([1])([1])([..,,2,222,1
,111,???
式（4-7）
而通过与二类支持向量机类似的变换，式（4-7）的解由下式给出：
?
?????=??????????????+Ω-??100)(1)(i i i i
T
i
a b I y y γ
l i ,...,2,1= 式（4-8）
式中，i y ?为Y 的第i 列，而)(i Ω由元素),(,,,)(k j k i j i j i i x x k y y =Ω组成，)(i a 为对应i y ?的Lagrange 乘子向量，i b 为对应i y ?的常数项。求解完毕后，则可建立下述LSSVM 函数：
∑==+=n
i j i ij ij j l j b x x k y x y
1
,...,2,1,),()(?α 式（4-9）
而模式向量x 的类别由判别函数l j x y
x c j j ,...,2,1)),(?sgn()(==输出组成的向量c 决定。
3. 算法流程
输入：包含n 个对象的训练库以及待测样本图像 输出：待测图像的分类结果 1.给定训练集 2.求解二次规划问题 3.计算参数w 和b
4.构造判别辩解，求得判决函数
5.对待测样本进行分类并输出分类结果
4.2 k-means 分类算法
1. 算法简介
毕业论文（设计）论文（设计）题目：PAM聚类算法的分析与实现 系别： 专业： 学号： 姓名： 指导教师： 时间：
毕业论文（设计）开题报告 系别:计算机与信息科学系专业:网络工程 学号姓名高华荣 论文（设计）题目PAM聚类算法的分析与实现 命题来源□√教师命题□学生自主命题□教师课题 选题意义(不少于300字): 随着计算机技术、网络技术的迅猛发展与广泛应用，人们面临着日益增多的业务数据，这些数据中往往隐含了大量的不易被人们察觉的宝贵信息，为了得到这些信息，人们想尽了一切办法。数据挖掘技术就是在这种状况下应运而生了。而聚类知识发现是数据挖掘中的一项重要的内容。 在日常生活、生产和科研工作中，经常要对被研究的对象经行分类。而聚类分析就是研究和处理给定对象的分类常用的数学方法。聚类就是将数据对象分组成多个簇，同一个簇中的对象之间具有较高的相似性，而不同簇中的对象具有较大的差异性。 在目前的许多聚类算法中，PAM算法的优势在于：PAM算法比较健壮，对“噪声”和孤立点数据不敏感；由它发现的族与测试数据的输入顺序无关；能够处理不同类型的数据点。 研究综述(前人的研究现状及进展情况，不少于600字): PAM（Partitioning Around Medoid,围绕中心点的划分）算法是是划分算法中一种很重要的算法，有时也称为k-中心点算法，是指用中心点来代表一个簇。PAM算法最早由Kaufman和Rousseevw提出，Medoid的意思就是位于中心位置的对象。PAM算法的目的是对n个数据对象给出k个划分。PAM算法的基本思想：PAM算法的目的是对成员集合D中的N个数据对象给出k个划分，形成k个簇，在每个簇中随机选取1个成员设置为中心点，然后在每一步中，对输入数据集中目前还不是中心点的成员根据其与中心点的相异度或者距离进行逐个比较，看是否可能成为中心点。用簇中的非中心点到簇的中心点的所有距离之和来度量聚类效果，其中成员总是被分配到离自身最近的簇中，以此来提高聚类的质量。 由于PAM算法对小数据集非常有效，但对大的数据集合没有良好的可伸缩性，就出现了结合PAM的CLARA（Cluster LARger Application）算法。CLARA是基于k-中心点类型的算法，能处理更大的数据集合。CLARA先抽取数据集合的多个样本，然后用PAM方法在抽取的样本中寻找最佳的k个中心点，返回最好的聚类结果作为输出。后来又出现了CLARNS（Cluster Larger Application based upon RANdomized
数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集
实验三 K-Means聚类算法 一、实验目的 1) 加深对非监督学习的理解和认识 2) 掌握动态聚类方法K-Means 算法的设计方法 二、实验环境 1) 具有相关编程软件的PC机 三、实验原理 1) 非监督学习的理论基础 2) 动态聚类分析的思想和理论依据 3) 聚类算法的评价指标 四、算法思想 K-均值算法的主要思想是先在需要分类的数据中寻找K组数据作为初始聚类中心，然后计算其他数据距离这三个聚类中心的距离，将数据归入与其距离最近的聚类中心，之后再对这K个聚类的数据计算均值，作为新的聚类中心，继续以上步骤，直到新的聚类中心与上一次的聚类中心值相等时结束算法。 实验代码 function km(k,A)%函数名里不要出现“-” warning off [n,p]=size(A);%输入数据有n个样本，p个属性 cid=ones(k,p+1);%聚类中心组成k行p列的矩阵,k表示第几类，p是属性 %A(:,p+1)=100; A(:,p+1)=0; for i=1:k %cid(i,:)=A(i,:); %直接取前三个元祖作为聚类中心 m=i*floor(n/k)-floor(rand(1,1)*(n/k)) cid(i,:)=A(m,:); cid; end Asum=0; Csum2=NaN; flags=1; times=1; while flags flags=0; times=times+1; %计算每个向量到聚类中心的欧氏距离 for i=1:n
for j=1:k dist(i,j)=sqrt(sum((A(i,:)-cid(j,:)).^2));%欧氏距离 end %A(i,p+1)=min(dist(i,:));%与中心的最小距离 [x,y]=find(dist(i,:)==min(dist(i,:))); [c,d]=size(find(y==A(i,p+1))); if c==0 %说明聚类中心变了 flags=flags+1; A(i,p+1)=y(1,1); else continue; end end i flags for j=1:k Asum=0; [r,c]=find(A(:,p+1)==j); cid(j,:)=mean(A(r,:),1); for m=1:length(r) Asum=Asum+sqrt(sum((A(r(m),:)-cid(j,:)).^2)); end Csum(1,j)=Asum; end sum(Csum(1,:)) %if sum(Csum(1,:))>Csum2 % break; %end Csum2=sum(Csum(1,:)); Csum; cid; %得到新的聚类中心 end times display('A矩阵，最后一列是所属类别'); A for j=1:k [a,b]=size(find(A(:,p+1)==j)); numK(j)=a; end numK times xlswrite('data.xls',A);
聚类分析算法解析 一、不相似矩阵计算 1.加载数据 data(iris) str(iris) 分类分析是无指导的分类，所以删除数据中的原分类变量。 iris$Species<-NULL 2. 不相似矩阵计算 不相似矩阵计算，也就是距离矩阵计算，在R中采用dist()函数，或者cluster包中的daisy()函数。dist()函数的基本形式是 dist(x, method = "euclidean", diag = FALSE, upper = FALSE, p = 2) 其中x是数据框（数据集），而方法可以指定为欧式距离"euclidean", 最大距离"maximum", 绝对值距离"manhattan", "canberra", 二进制距离非对称"binary" 和明氏距离"minkowski"。默认是计算欧式距离，所有的属性必须是相同的类型。比如都是连续类型，或者都是二值类型。 dd<-dist(iris) str(dd) 距离矩阵可以使用as.matrix()函数转化了矩阵的形式，方便显示。Iris数据共150例样本间距离矩阵为150行列的方阵。下面显示了1~5号样本间的欧式距离。 dd<-as.matrix(dd)
二、用hclust()进行谱系聚类法（层次聚类） 1.聚类函数 R中自带的聚类函数是hclust()，为谱系聚类法。基本的函数指令是 结果对象 <- hclust（距离对象, method=方法） hclust()可以使用的类间距离计算方法包含离差法"ward"，最短距离法"single"，最大距离法"complete"，平均距离法"average"，"mcquitty"，中位数法 "median" 和重心法"centroid"。下面采用平均距离法聚类。 hc <- hclust(dist(iris), method="ave") 2.聚类函数的结果 聚类结果对象包含很多聚类分析的结果，可以使用数据分量的方法列出相应的计算结果。 str(hc) 下面列出了聚类结果对象hc包含的merge和height结果值的前6个。其行编号表示聚类过程的步骤，X1，X2表示在该步合并的两类，该编号为负代表原始的样本序号，编号为正代表新合成的类；变量height表示合并时两类类间距离。比如第1步，合并的是样本102和143，其样本间距离是0.0，合并后的类则使用该步的步数编号代表，即样本-102和-143合并为1类。再如第6行表示样本11和49合并，该两个样本的类间距离是0.1，合并后的类称为6类。 head (hc$merge,hc$height)
论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对
聚类算法的种类：
--------------------------------------------------------- 几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示：
--------------------------------------------------------- 目前聚类分析研究的主要内容： 对聚类进行研究是数据挖掘中的一个热门方向，由于以上所介绍的聚类方法都 存在着某些缺点，因此近些年对于聚类分析的研究很多都专注于改进现有的聚 类方法或者是提出一种新的聚类方法。以下将对传统聚类方法中存在的问题以 及人们在这些问题上所做的努力做一个简单的总结： 1 从以上对传统的聚类分析方法所做的总结来看，不管是k-means方法，还是CURE方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在 现实数据中，聚类的数目是未知的，通常要经过不断的实验来获得合适的聚类 数目，得到较好的聚类结果。 2 传统的聚类方法一般都是适合于某种情况的聚类，没有一种方法能够满足各 种情况下的聚类，比如BIRCH方法对于球状簇有很好的聚类性能，但是对于不 规则的聚类，则不能很好的工作；K-medoids方法不太受孤立点的影响，但是 其计算代价又很大。因此如何解决这个问题成为当前的一个研究热点，有学者 提出将不同的聚类思想进行融合以形成新的聚类算法，从而综合利用不同聚类 算法的优点，在一次聚类过程中综合利用多种聚类方法，能够有效的缓解这个 问题。 3 随着信息时代的到来，对大量的数据进行分析处理是一个很庞大的工作，这 就关系到一个计算效率的问题。有文献提出了一种基于最小生成树的聚类算法，该算法通过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就不需要计算而直接丢弃，这样就极大地提高了计算效率，降 低了计算成本。 4 处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规 模数据和低维数据时性能比较好，但是当数据规模增大，维度升高时，性能就 会急剧下降，比如k-medoids方法处理小规模数据时性能很好，但是随着数据 量增多，效率就逐渐下降，而现实生活中的数据大部分又都属于规模比较大、 维度比较高的数据集。有文献提出了一种在高维空间挖掘映射聚类的方法PCKA （Projected Clustering based on the K-Means Algorithm），它从多个维度中选择属性相关的维度，去除不相关的维度，沿着相关维度进行聚类，以此对 高维数据进行聚类。 5 目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好 的被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大， 因此如何有效的消除噪声的影响，提高处理现实数据的能力还有待进一步的提高。
对数据进行聚类分析实验报告 1.方法背景 聚类分析又称群分析，是多元统计分析中研究样本或指标的一种主要的分类方法，在古老的分类学中，人们主要靠经验和专业知识，很少利用数学方法。随着生产技术和科学的发展，分类越来越细，以致有时仅凭经验和专业知识还不能进行确切分类，于是数学这个有用的工具逐渐被引进到分类学中，形成了数值分类学。近些年来，数理统计的多元分析方法有了迅速的发展，多元分析的技术自然被引用到分类学中，于是从数值分类学中逐渐的分离出聚类分析这个新的分支。结合了更为强大的数学工具的聚类分析方法已经越来越多应用到经济分析和社会工作分析中。在经济领域中，主要是根据影响国家、地区及至单个企业的经济效益、发展水平的各项指标进行聚类分析，然后很据分析结果进行综合评价，以便得出科学的结论。 2.基本要求 用FAMALE.TXT、MALE.TXT和/或test2.txt的数据作为本次实验使用的样本集，利用C均值和分级聚类方法对样本集进行聚类分析，对结果进行分析，从而加深对所学内容的理解和感性认识。 3.实验要求 （1）把FAMALE.TXT和MALE.TXT两个文件合并成一个，同时采用身高和体重数据作为特征，设类别数为2，利用C均值聚类方法对数据进行聚类，并将聚类结果表示在二维平面上。尝试不同初始值对此数据集是否会造成不同的结果。 （2）对1中的数据利用C均值聚类方法分别进行两类、三类、四类、五类聚类，画出聚类指标与类别数之间的关系曲线，探讨是否可以确定出合理的类别数目。 （3）对1中的数据利用分级聚类方法进行聚类，分析聚类结果，体会分级聚类方法。。（4）利用test2.txt数据或者把test2.txt的数据与上述1中的数据合并在一起，重复上述实验，考察结果是否有变化，对观察到的现象进行分析，写出体会 4.实验步骤及流程图 根据以上实验要求，本次试验我们将分为两组：一、首先对FEMALE 与MALE中数据组成的样本按照上面要求用C均值法进行聚类分析，然后对FEMALE、MALE、test2中数据组成的样本集用C均值法进行聚类分析，比较二者结果。二、将上述两个样本用分即聚类方法进行聚类，观察聚类结果。并将两种聚类结果进行比较。 （1）、C均值算法思想
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；
（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
基于k—means聚类算法的试卷成绩分析研 究 第39卷第4期 2009年7月 河南大学(自然科学版) JournalofHenanUniversity(NaturalScience) V o1.39NO.4 Ju1.2009 基于k—means聚类算法的试卷成绩分析研究 谭庆' (洛阳师范学院信息技术学院,河南洛阳471022) 摘要:研究_rk-means聚类算法,并将此算法应用于高校学生试卷成绩分析中.首先对数据进行了预处理,然后 使用k-means算法,对学生试卷成绩进行分类评价.用所获得的结果指导学生的学习和今后的教学工作. 关键词:数据挖掘;聚类;k-means算法;试卷成绩 中圈分类号:TP311文献标志码:A文章编号:1003—4978(2009)04—0412—04 AnalysisandResearchofGradesofExaminationPaper BasedonK—meansClusteringAlgorithm TANQing (Acaderny.l,InformationTechnologY,LuoyangNormalUniversity,LuoyangHenan47102 2,China) Abstract:Thispaperresearcheslhekmeansclusteringalgorithmandappliesittotheanalysiso fthegradedataof examinationpaperofhighereducationschoolSstudents.Firstly,itpreprocessesthedatabefor eminingThen,it usesthek—
K-均值聚类算法报告 摘要 K-均值是聚类方法中长用的一种划分方法，有很多优点，本文主要对K-均值是聚类方法的产生，工作原理，一般步骤，以及它的源码进行简单的介绍，了解K-均值是聚类！！！ （一）课题名称：K-均值聚类(K-means clustering) （二）课题分析： J.B.MacQueen 在 1967 年提出的K-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为： K-means 算法的特点——采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配： ① 指定聚类，即指定数据到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。 ② 修改聚类中心。 优点：本算法确定的K 个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O(NKt)，其中N是数据对象的数目，t是迭代的次数。一般来说，K< （1）从 n个数据对象任意选择 k 个对象作为初始聚类中心； （2）循环（3）到（4）直到每个聚类不再发生变化为止； （3）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； （4）重新计算每个（有变化）聚类的均值（中心对象） k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 （三）总体检索思路： 利用goole，百度，搜狗等搜索引擎及校内的一些数据库进行相关内容的检索。主要检索内容为K-均值聚类算法的工作原理，一般步骤，源码。 （四）检索过程记录： 关键词：K-均值聚类算法 搜索引擎：百度 检索内容：①K-均值聚类算法工作原理 ②K-均值聚类算法的一般步骤 ③K-均值聚类算法的源码 嵌入式方向工程设计实验报告 学院班级：130712 学生学号：13071219 学生姓名：杨阳 同作者：无 实验日期：2010年12月 聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即 第24卷第5期 2007年5月 计算机应用研究 Application Resea心h of Computers V01.24.No.5 Mav 2007 基于聚类分析的K—means算法研究及应用爿: 张建萍1,刘希玉2 (1.山东师范大学信息科学与工程学院,山东济南250014;2.山东师范大学管理学院,山东济南250014 摘要:通过对聚类分析及其算法的论述,从多个方面对这些算法性能进行比较,同时以儿童生长发育时期的数据为例通过聚类分析的软件和改进的K.means算法来进一步阐述聚类分析在数据挖掘中的实践应用。 关键词:数据挖掘;聚类分析;数据库;聚类算法 中图分类号:TP311文献标志码:A 文章编号:1001—3695(200705—0166-03 Application in Cluster’s Analysis Is Analyzed in Children DeVelopment Period ZHANG Jian—pin91,UU Xi—yu。 (1.coz比伊矿,咖mo砌n 5c掂Me&E蟛袱^增,|s胁础增Ⅳo丌mf‰洫瑙毋,五n 帆5^a蒯D昭250014,吼i胁;2.cozz学矿讹加舻删眦, s^0n幽凡g舳丌Mf‰i孵璐匆,^加n乩。砌。昭250014,傩iM Abstract: nis paper passed cluster’s analysis and its algorithm corTectly,compared these algorithm perfbrnlances f}om a lot of respects,and explained that cluster analysis excavates the practice application of in datum further to come through software and impmved K—means aIgorithm,cIuster of analysis at the same time practise appIication. Key words:data mining; cluster analysis; database; cluster algorithm 随着计算机硬件和软件技术的飞速发展,尤其是数据库技 术的普及,人们面临着日益扩张的数据海洋,原来的数据分析工具已无法有效地为决策者提供决策支持所需要的相关知识, 从而形成一种独特的现象“丰富的数据,贫乏的知识”。数据挖掘…又称为数据库中知识发现(Knowledge Discovery from Database,KDD,它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。目的是在大量的数据中发现人们感兴趣的知识。 常用的数据挖掘技术包括关联分析、异类分析、分类与预测、聚类分析以及演化分析等。由于数据库中收集了大量的数据,聚类分析已经成为数据挖掘领域的重要技术之一。 1问题的提出 随着社会的发展和人们生活水平的提高,优育观念嵋一。逐渐渗透到每个家庭,小儿的生长发育越来越引起家长们的重视。中国每隔几年都要进行全国儿童营养调查,然而用手工计算的方法在大量的数据中分析出其中的特点和规律,显然是不现实的,也是不可行的。为了有效地解决这个问题,数据挖掘技术——聚类分析发挥了巨大的作用。 在数据挖掘领域,聚类算法经常遇到一些问题如聚类初始点的选择H J、模糊因子的确定‘5o等,大部分均已得到解决。现在的研究工作主要集中在为大型的数据库有效聚类分析寻找适当的方法、聚类算法对复杂分布数据和类别性数据聚类的有效性以及高维数据聚类技术等方面。本文通过对聚类分析算法的分析并重点 各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类 1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解 系统聚类分析方法 聚类分析是研究多要素事物分类问题的数量方法。基本原理是根据样本自身的属性，用数学方法按照某种相似性或差异性指标，定量地确定样本之间的亲疏关系，并按这种亲疏关系程度对样本进行聚类。 常见的聚类分析方法有系统聚类法、动态聚类法和模糊聚类法等。 1. 聚类要素的数据处理 假设有m 个聚类的对象，每一个聚类对象都有个要素构成。它们所对应的要素数据可用表3.4.1给出。（点击显示该表）在聚类分析中，常用的聚类要素的数据处理方法有如下几种。 ①总和标准化 ②标准差标准化 ③极大值标准化 经过这种标准化所得的新数据，各要素的极大值为1，其余各数值小于1。 ④极差的标准化 经过这种标准化所得的新数据，各要素的极大值为1，极小值为0，其余的数值均在0与1之间。 2. 距离的计算 距离是事物之间差异性的测度，差异性越大，则相似性越小，所以距离是系统聚类分析的依据和基础。 ①绝对值距离 选择不同的距离，聚类结果会有所差异。在地理分区和分类研究中，往往采用几种距离进行计算、对比，选择一种较为合适的距离进行聚类。 例：表3.4.2给出了某地区九个农业区的七项指标，它们经过极差标准化处理后，如表3.4.3所示。 对于表3.4.3中的数据，用绝对值距离公式计算可得九个农业区之间的绝对值距离矩阵： 3. 直接聚类法 直接聚类法是根据距离矩阵的结构一次并类得到结果。 ▲ 基本步骤： ①把各个分类对象单独视为一类； ②根据距离最小的原则，依次选出一对分类对象，并成新类；③如果其中一个分类对象已归于一类，则把另一个也归入该类；如果一对分类对象正好属于已归的两类，则把这两类并为一类；每一次归并，都划去该对象所在的列与列序相同的行；④那么，经过m-1次就可以把全部分类对象归为一类，这样就可以根据归并的先后顺序作出聚类谱系图。 ★直接聚类法虽然简便，但在归并过程中是划去行和列的，因而难免有信息损失。因此，直接聚类法并不是最好的系统聚类方法。 [举例说明]（点击打开新窗口，显示该内容） 例：已知九个农业区之间的绝对值距离矩阵，使用直接聚类法做聚类分析。 解： 根据上面的距离矩阵，用直接聚类法聚类分析：聚类算法分析报告汇总
基于聚类分析的Kmeans算法研究及应用概要
各种聚类算法的比较
系统聚类分析方法
相关主题
文本预览