数字图像处理论文

1、甘肃政法学院本科课程设计数据仓库与数据挖掘题 目 基于FCM算法的聚类研究计算机科学学院(系)信息管理与信息系统专业2011级本科班学 号 姓 名 指导教师 成 绩 完成时间 2013 年 12 月基于FCM算法的聚类研究摘 要：本文在阐述聚类分析方法的基础上重点研究FCM聚类算法。FCM算法是一种基于划分的聚类算法，它的思想是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。最后基于MATLAB实现了对图像信息的聚类。关键词：FCM；聚类算法；MTALABCluster Analysis Based on FCM Algorithm Abstract: This paper

2、describes the basis of cluster analysis methods and focus on the FCM clustering algorithm. FCM algorithm is a clustering algorithm based on division and the idea is to make it to the same cluster is divided into the biggest similarity between the objects, while the minimum similarity between differe

3、nt clusters. Finally, I realize the implementation of image information of the cluster based on MATLAB.Key words: FCM; Clustering algorithm ;MTALAB目 录第1章 概述1第2章 聚类分析方法12.1 聚类分析12.2 主要聚类算法的分类2第3章 模糊聚类算法43.1图像分割43.2 模糊聚类43.3模糊C均值算法53.4 算法步骤53.5基于weka下的FCM聚类分析63.6基于MATLAB下的灰度图像分割分析7第5章 FCM聚类结果12致 谢13参考

4、文献13第1章 概述1.1研究背景由于计算机和数据采集技术的进步，数据挖掘获得了非常广泛的应用。数据挖掘帮助用户发现隐藏在大型数据库种的规律和模式，它融合了人工智能、统计、机器学习、模式识别和数据库等多种学科的理论、方法与技术。数据挖掘模型包括决策树、关联规则、聚类、神经网络、粗糙集、概念格、遗传算法、序列模式、贝叶斯、支持向量机、模糊集和基于案例的推理。其中，聚类是数据挖掘领域的核心技术，被广泛应用于相似搜索、顾客划分、趋势分析、金融投资和信息检索等领域。聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到

5、分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。而模糊C均值(Fuzzy C-means, FCM)聚类方法，属于基于目标函数的模糊聚类算法的范畴。模糊C均值聚类方法是基于目标函数的模糊聚类算法理论中最为完善、应用最为广泛的一种算法。模糊c均值算法最早从硬聚类目标函数的优化中导出的。为了借助目标函数法求解聚类问题，人们利用均方逼近理论构造了带约束的非线性规划函数，以此来求解聚类问题，从此类内平方误差和WGSS

6、(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出，Dun首先将其推广到加权WGSS函数，后来由Bezdek扩展到加权WGSS的无限族，形成了FCM聚类算法的通用聚类准则。从此这类模糊聚类蓬勃发展起来，目前已经形成庞大的体系。 第2章 聚类分析方法2.1 聚类分析聚类分析就是根据对象的相似性将其分群，聚类是一种无监督学习方法，它不需要先验的分类知识就能发现数据下的隐藏结构。它的目标是要对一个给定的数据集进行划分，这种划分应满足以下两个特性：类内相似性：属于同一类的数据应尽可能相似。类间相异性：属于不同类的数据应尽可能相异。

7、图2.1是一个简单聚类分析的例子。 图2.1 聚类分析的例子聚类分析是数据挖掘的一项重要功能，而聚类算法是目前研究的核心，聚类分析就是使用聚类算法来发现有意义的聚类，即“物以类聚”。虽然聚类也可起到分类的作用，但和大多数分类或预测不同。大多数分类方法都是演绎的，即人们事先确定某种事物分类的准则或各类别的标准，分类的过程就是比较分类的要素与各类别标准，然后将各要素划归于各类别中。确定事物的分类准则或各类别的标准或多或少带有主观色彩。聚类分析是归纳的，不需要事先确定分类的准则来分析数据对象，不考虑己知的类标记。一般情况下，训练数据中不提供类标记，因为不知道从何开始，聚类可以用于产生这种标记。对象根

8、据最大化类内的相似性，最小化类间的相似性的原则进行聚类或分组，它通过一些计算来把观测进行合理的分类，使得同类的观测比较接近，不同类的观测相差较多。所形成的每个簇可看成一个对象类，由它可以导出规则。聚类增强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。2.2 主要聚类算法的分类聚类方法包含很多类型的算法，主要可以分为划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法等几个大类。（l）划分方法给定一个包含n个对象或数据行的数据集，划分方法将数据集划分为k个子集(划分)，其中每个子集均代表一个聚类，即将数据分为k组。这些组满足以下要求：1.每组至少应包含一个对象；2.每个对

9、象必须只能属于某一组。后一个要求在一些模糊划分方法中可以放宽。给定需要划分的个数k，一个划分方法首先创建一个初始划分，然后利用循环再定位技术，即通过移动不同划分(组)中的对象来改变划分内容。一个好的划分衡量标准通常是使得同一个组中的对象“相近”或彼此相关，而不同组中的对象“较远”或彼此不同。为获得基于划分聚类分析的全局最优结果，需要穷举所有可能的对象划分，为此大多数应用采用的常用启发方法包括：k-均值算法，算法中的每一个聚类均用相应聚类中对象的均值来表示；k-medoid算法，算法中的每一个聚类均用相应聚类中离聚类中心最近的对象来表示。这些启发聚类方法在分析中小规模数据集以发现圆形或球状聚类时

10、工作得很好，但当分析处理大规模数据集或复杂数据类型时效果较差，需要对其进行扩展。（2）层次方法层次方法是通过分解所给定的数据对象集来创建一个层次。根据层次分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个对象均为一个单独的组开始，逐步将这些(对象)组进行合并，直到这些组位于层次顶端或满足终止条件为止。自上而下层次方法从所有均属于一个组的对象开始，每一次循环将组分解为更小的组，直到每个对象构成一组或满足终止条件为止。（3）基于密度的方法大多数划分方法是基于对象间距离进行聚类的，这类方法仅能发现圆形或球状的聚类而较难发现具有任意形状的聚类。而基于密度概念的聚类方

11、法实际上就是不断增长所获得的聚类，直到“邻近”(数据对象或点)密度超过一定域值(如：一个聚类中的点数，或一个给定半径内必须包含至少的点数)为止。这种方法可以用于消除数据中的噪声(异常数据)，以及帮助发现任意形状的聚类。常用的基于密度的方法，如k-最近邻方法是根据某个对象与其相邻的k个对象的距离和来判断其是否为异常数据。（4）基于网格的方法基于网格的方法将对象空间划分为有限数目的单元以形成网格结构，所有聚类操作均是在这一网格结构上进行的。这种方法的主要优点是，由于与数据对象个数无关，而仅与划分对象空间的网格数相关，从而执行时间显得相对较快。基于网格的方法主要包括GRIDCLUS, BANG-CL

12、USTERY, STING, wave cluster等（5）基于模型的方法基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它采用了标准的统计方法，并考虑了“噪声”或异常数据，可以自动确定聚类个数，因此可以产生具有鲁棒性的聚类方法。还有一些聚类算法是将几种聚类方法的思想结合在一起的，因此有时很难明确界定一个聚类算法究竟属于哪一个聚类方法类别。此外一些应用也需要将多个聚类技术结合起来才能实现其应用目标。第3章 模糊聚类算法3.1图像分割原理和聚类概述基本原理：根据图像的组成结构和应用需求将图

13、像划分为若干个互不相交的子区域的过程。这些子区域四某种意义下具有共同属性的像素的连通集合。常用方法有：（1）以区域为对象进行分割，以相似性原则作为分割的依据，即可根据图像的灰度、色彩、变换关系等方面的特征相似来划分图像的子区域，并将各像素划归到相应物体或区域的像素聚类方法，即区域法；（2）以物体边界为对象进行分割，通过直接确定区域间的边界来实现分割；（3）先检测边缘像素，再将边缘像素连接起来构成边界形成分割。聚类是将数据对象分成类或簇的过程，使同一簇中的对象之间具有很高的相似度，而不同簇中的对象高度相异。聚类源于许多研究领域，包括数据挖掘、统计学、生物学和机器学习。通过自动聚类能够识别对象空间

14、中稠密和稀疏区域，从而发现全局分布模式和数据属性之间有趣的相关。聚类分析已经广泛地应用于许多领域，包括市场研究、模式识别、数据分析和图像处理。聚类还可以用于离群点检测，如信用卡欺诈检测和监控电子商务中的犯罪活动。聚类分析是一种寻求数据的自然聚集结构的重要方法，是概念描述和偏差分析的先决条件。聚类是一种处理大量的、繁杂的、属性众多的且没有类标志数据的有效方法；在知识发现的过程中，聚类经常被作为其他数据挖掘任务的前奏。分析成为数据挖掘和知识发现领域中的最重要的课题之一，迄今为止，人们已经提出了许多数据聚类的算法，解决各种领域的聚类问题，如传统的聚类方法，空间数据的聚类方法和统计学中的聚类算法等。对

15、象间的相似性是聚类的核心，而对相似性进行度量是用以区别对象的主要基础，相似性的度量方法主要有两类，即距离和相似系数。距离通常用于数值型数据，距离越接近0，相似性越大；相似系数通常用于分类型数据，相似系数越接近1，相似性越大。聚类分析通常是基于距离的，通过构造一个 m 维空间的距离函数，利用这个距离函数来进行聚类。令为维空间中一组对象，、，是和之间的距离。距离的定义通常应满足以下四条性质：1)2) ，03) ，=4) ，在聚类分析中，一般只要求距离函数满足前三条性质。常用的距离公式如下： 1) 闵科夫斯基(Minkowski)距离，是距离的最通常的形式，如式3-1： （3-1） 2) 曼哈顿（M

16、anhattan）距离，即各属性之差的绝对值的和，如式3-2： （3-2） 3) 欧式（Euclidean）距离，即各属性之差的平方和的平方根，如式3-3： （3-3） 4) 切比雪夫（Chebyshev）距离，即各属性之差的最大值，如式3-4： （3-4）3.2 模糊聚类模糊聚类中，每个样本不再仅属于某一类，而是以一定的隶属度属于每一类，也即通过模糊聚类分析，得到了的样本属于各个类别的不确定性程度，即建立起了样本对于类别的不确定性的描述， 这样更能准确地反映现实世界。模糊聚类不需要训练样本，可直接通过机器学习达到自动分类的目的。模糊聚类不但可以从原始数据中直接提取特征，还能对已经得到的特征进

17、行优选和降维操作，以免造成“维数灾难” 。常用模糊聚类算法有：模糊 C-均值FCM(Fuzzy C-Means) 算法。该算法是在传统 C均值算法中应用了模糊技术。模糊划分的概念最早由Ruspin于1969年提出的提出，利用这一概念人们提出了多种聚类方法。模糊聚类分析按照聚类过程的不同大致可以分为三大类：（l）基于模糊关系的分类法其中包括谱系聚类算法(又称系统聚类法)、基于等价关系的聚类算法、基于相似关系的聚类算法和图论聚类算法等等。它是研究比较早的一种方法，但是由于它不能适用于大数据量的情况，所以在实际中的应用并不广泛。文献对这方面的研究进行了综述。（2）基于目标函数的模糊聚类算法该方法把聚

18、类分析归结成一个带约束的非线性规划问题，通过优化求解获得数据集的最优模糊划分和聚类。该方法设计简单、解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于计算机实现。因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法已成为聚类分析研究的主流。（3）基于神经网络的模糊聚类算法它是兴起比较晚的一种算法，主要是采用竞争学习算法来指导网络的聚类过程，可以解决传统的模糊聚类算法在大数据量时的耗时问题。它现在已经成为聚类分析研究的重要组成部分。文献把改进的模糊聚类算法和径向基函数(RBF)神经网络结合起来建模，得到一种映射能力较强的自组织RBF神经网络。文献将模糊聚类结合多

19、层前馈神经网络(MFN)建立了综合神经网络模型(FCMMFN)。文献利用模糊控制策略将算法与经典的Kohonen算法有机地结合起来，使网络性能到了很大改善。文献将模糊推理规则转化为模糊RBF网络模型。3.3模糊C均值算法模糊C-均值聚类算法是一种逐步迭代的算法，每步迭代都沿着目标函数减小的方向进行。首先，需要对一些数据进行初始化：1. 待聚类数据总个数 ；2. 聚类类别数C , ；3. 迭代停止阈值；4. 聚类原型模式，；5. 迭代计数器 ，；6. 加权指数m，在后面的章节我们可以分析得到，m一般情况取。初始化成功后，开始实现具体算法：1）根据式（4-1）计算各个数据的隶属函数 用于更新划分矩

20、阵：对于，如果， ，则有： （3-5）其中为样本与第i类的聚类原型之间的距离度量。 如果，使得 ，则有：。并且对1） 根据公式（4-1）更新聚类原型模式矩阵：（3-6）2）迭代计数器，循环步骤1）2），直到公式（4-3）成立，并得到划分矩阵和聚类原型： （3-7）从上面所描述的算法步骤中不难看出，整个计算的过程就是反复修改聚类中心和分类矩阵的过程。经过这种反复修改的过程之后，该算法的收敛性已经得以证明。 对于每一个模糊隶属度，由控制模糊度的权重指数；为相似性测度。其中： 数据样本维数（灰度图像时为1）； 像素点数目； 像素特征（灰度图像时，表示灰度值）； 图像分割类别数； 像素点属于第类的隶属

21、度； 第类聚类中心。3.4 算法步骤Step1：设置目标函数精度，模糊指数（通常取2），最大迭代次数；Step2：初始化模糊聚类中心；Step3：由式（3-5）更新模糊划分矩阵和聚类中心Step4：若或则结束聚类；否则，并转Step3；Step5：由所得得到各像素点分类结果。3.5基于weka下的FCM聚类分析 Weka中本身没有添加算法FuzzyCMeans，这就需要自己添加算法FuzzyCMeans，这里不给出添加步骤。添加算法FuzzyCMeans后在clusterers中选择算法，在choose里面选择FuzzyCMeans的结果如图所示：图3.1FuzzyCMeans算法运行结果如图

22、图3.2对glass中的数据进行聚类，结果如图所示：图3.3根据FuzzyCMeans算法的计算公式可知，用隶属度来确定每个点隶属于某个聚类的程度，可以将glass的数据分为两个聚类，一个聚类的模糊集，所包涵元素为113个占53%，一个聚类的模糊集，包含元素为100个，占47%。3.6基于MATLAB下的灰度图像分割分析图像分割的基本思想是：将高于某一灰度的像素划分到一个区域中，将低于某灰度的像素划分到另一区域中，这种基于灰度阀值的分割方法称为灰度门限法。灰度门限法是基本的图像分割方法，也是基于区域的分割方法。直方图阀值法是利用灰度直方图求双峰或多峰，选择两峰之间的谷底作为阀值。运行程序，得到

23、结果如图所示：图3.4 原始图像图3.5 原图像的二值直方图图3.6 阀值法分割结果图第5章 FCM聚类结果图5.1 原图像图 5.2 读入图像的像素图图 5.3 聚类结果图图5.1是原图像，图5.2是读入图像的像素信息后显示出来的结果，图5.3是最终结果，由图可得到它将图片成功地聚为黑、白、深灰和浅灰四类。致 谢在此我非常要感谢的是我的指导老师xxx副教授，同时我还要感谢帮助过我的同学，没有他们的帮助我不可能完成这样顺利，谢谢！参考文献1 陈安, 陈宁, 周龙驤.数据挖掘技术及应用.科学出版社.2006.03:25-30.2 Jiawei Han, Micheline Kamber.数据挖掘

24、概念与技术.第二版.机械工业出版社.2007.03:273-274.3 David Hand, Heikki Mannila, Padhraic Smyth.数据挖掘原理.机械工业出版社.2003.04:7-10.4 冯少荣, 肖文俊.DBSCAN聚类算法的研究与改进.中国矿业大学学报.2008,37(1).5 谭勇, 荣秋生.一个基于DBSCAN聚类算法的实现.计算机工程.2004,30(13). 附 录tmp=imread(E:11.jpg);IM=tmp(:,:,1);IM=double(IM);figure(1); imshow(uint8(IM);%functionIX2=fcm(I

25、M);maxX,maxY=size(IM);IMM=cat(4,IM,IM,IM,IM);%(4类)cc1=8;cc2=50;cc3=120;cc4=200;ttFcm=0;while(ttFcm8) ttFcm=ttFcm+1; c1=repmat(cc1,maxX,maxY); c2=repmat(cc2,maxX,maxY); c3=repmat(cc3,maxX,maxY); c4=repmat(cc4,maxX,maxY); c=cat(4,c1,c2,c3,c4); ree=repmat(0.000001,maxX,maxY); ree1=cat(4,ree,ree,ree,ree

26、); distance=IMM-c; distance=distance.*distance+ree1; daoShu=1./distance; daoShu2=daoShu(:,:,1)+daoShu(:,:,2)+daoShu(:,:,3)+daoShu(:,:,4); distance1=distance(:,:,1).*daoShu2; u1=1./distance1; distance2=distance(:,:,2).*daoShu2; u2=1./distance2; distance3=distance(:,:,3).*daoShu2; u3=1./distance3; distance4=distance(:,:,4).*daoShu2; u4=1./distance4; ccc1=sum(sum(u1.*u1.*IM)/sum(sum(u1.*u1); ccc2=sum(sum