模式识别作业

模式识别作业模糊C-均值聚类分析的应用学院、系电子信息工程学院自动化系专业名称模式识别与智能系统年级2009级学生姓名郭佳学号30956028目录1．前言.......................................................................................................................12．模糊C均值算法.....................................................................................................22.1FCM算法准则..............................................................................................22.2模糊C均值算法步骤.....................................................................................32.2.1简介........................................................................................................32.2.2FCM算法具体步骤..............................................................................43．模糊C均值聚类算法的Matlab实现................................................................53.1实验数据.........................................................................................................53.2模糊C均值聚类程序分析............................................................................73.3Matlab实现及结果分析..............................................................................73.3.1前29组数据的聚类分析......................................................................73.3.249组数据的聚类分析......................................................................15总结.............................................................................................................................20参考文献.....................................................................................................................211模糊C-均值聚类分析的应用1．前言聚类就是按照一定的要求和规律对事物进行区分和分类的过程，在这一过程中没有任何关于类分的先验知识，仅靠事物间的相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类分析则是指用数学的方法研究和处理给定对象的分类。“人以群分，物以类聚”，聚类是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并认识事物间的相似性。传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，同一事物属于且仅属于所划定类别中的某一类，具有非此即彼的性质。例如在描述人的很多特征之一——性别的时候，很容易就可以对人进行分类，因为性别只有男性和女性之分，因此这种分类的类别界限是分明的、清晰的、不含糊的，属于普通集合理论的范畴。而实际上大多数对象并没有严格的属性，它们在形态和类属方面存在着中介性，适合进行软划分，用普通集合的理论往往不能完全解决具有模糊性的分类问题。例如：将人按身高分为：高个子、中等个子、矮个子；图1-1所示经典硬聚类无法解决的聚类问题示意图，I部分代表高个子，II部分代表矮个子，但是他们的交集部分，用传统的硬聚类分析方法就无法解决。图1-1经典硬聚类无法解决的聚类问题示意图在此基础上，Zadeh提出的模糊集理论为这种软划分提供了有力的分析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。应该指出，基于模糊集理论的模糊逻辑本身并不是模糊的，而是用来对“模糊”进行处理以2达到消除模糊的逻辑。事实上，模糊逻辑是一种精确地解决不精确、不完全信息的方法，其最大的特点就是用它可以比较自然的处理人类的概念。具体地说，模糊逻辑是通过模糊集合来工作的，模糊集合与传统集合的本质区别在于：(1)传统集合对集合中的元素关系进行严格区分，一个元素要么属于此集合，要么不属于此集合，并且不存在介于二者之间的情况；(2)模糊集合则具有灵活的隶属关系，允许元素在一个集合中部分隶属。元素在模糊集合中的隶属度可以是从0到1之间的任何值，而不像在传统集合中要么是0要么是1，这样模糊集合可以从“不隶属”到“隶属”逐级的过渡。正是由于模糊聚类具有样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样本对于类别的不确定性的描述，能更客观地反映现实世界，从而成为聚类分析研究的主流。为了优化聚类分析的目标函数，人们提出了现在相当流行和应用广泛的模糊C-均值FCM(FuzzyC-means)聚类算法。该算法是从硬C-均值HCM(HardC-means)聚类算法发展而来的。2．模糊C均值算法2.1FCM算法准则给定数据集{}1,2,...nXxxx=，其中每个元素包含s个属性。模糊聚类就是要将X划分为c个类，1,2{...}cvvvv=为C个类的聚类中心在模糊划分中，每一个样本点不能严格地被划分到某一类，而是以一定的隶属度属于某一类。令iju表示第j个样本点第i个类的隶属度。且满足下式:[],0,1.ijiju?（2.1）11.cijjiu==å(2.2)1.nijijuN=å(2.3)FCM算法的目标函数为:211(,)ncmijijjiJUVud===邋(2.4)3其中，||||ijjidxv=-为样本点jx与聚类中心iv之间的距离则FCM算法就是要求满足11.cijjiu==å的情况下目标函数J的最小值，J的条件极值可以由拉格朗日乘数法求得。首先，J在(2.4)式下的条件极值可以表示成(2.5)式,其中函数l为常数:2111(,)(1)cncmijijijikiJUVudul====+-邋?（2.5）对iju求偏导经过计算后得：21/(1)211()ijcijmkkjudd-==å，用同样的方法(,)JUV为最小值时iv的值为：11()()nmikkkinmikkuxvu===åå(i=1,2…c)2.2模糊C均值算法步骤2.2.1简介FCM算法有五个参数((0)U，A，c，m，ε)，改变任何一个参数都将影响到FCM聚类的最终结果。(1)(0)U为初始隶属度矩阵，它直接影响到聚类中心的初始值，隶属度可以看做是数据对聚类中心作用力强度的表征，隶属度越大，数据对类中心的吸引力就越大，类中心的下一次迭代值受它的影响也就越大，从而影响到算法的迭代次数，也就影响了算法的计算时间。(2)对称矩阵A，对称矩阵A也是一个重要参数,当A=I时，聚类类似于球状分布，当聚类形状为球状时，可给A赋予不同的矩阵形式，以适应不同的聚类要求，例如，聚类近似于条状或带形分布时。(3)聚类数目c，c是影响聚类精度和聚类速度的参数，若c较大，就会使原本密集的簇分开；若c值较小则会使原本是比较分离的簇合并，使聚类结果不能满足客户的需要，计算所需要的系统内存和时间也要成倍的增加，这有时候是不4能容忍的。(4)加权指数m，Zadeh认为“加权指数m控制着模糊类间的分享程度”。参数m控制着FCM聚类结果的模糊性，m值越大，所得到的分类矩阵模糊程度就越大。当m→∞时，U中所有的元素接近1/c，距离就失去了意义。所以要使用FCM算法分析数据就必需选取合适的m值。当然这并不意味着小的m值就对应好的聚类结果，因为较大的加权指数m还具有抑制噪声的功能，在噪声污染的数据中模糊聚类有着重要的作用。因此在不同的应用领域，m值的选取也有其不同的范围。(5)收敛阈值ε，ε也是影响聚类精度和聚类速度的参数。数值过大时，会导致算法过早收敛，聚类结果不稳定，特别是在初始参数不确定的条件下，这种现象更为普遍和明显。当阈值过小时，则可能会导致过度计算，既浪费时间，又可能发生无法收敛的问题。2.2.2FCM算法具体步骤初始化：取模糊加权指数m=2，聚类的类别数c(2≤c≤n)，n为数据样本点的个数，迭代停止阈值ε，初始的聚类中心值0V，以及迭代次数b=0；步骤一：用公式(2-7)计算由隶属度的值所组成的划分矩阵()bU：当0ikd当0ikd=(2-7)步骤二：用公式(2-8)更新聚类中心。()(1)1()1()()nmbikkbkinmbikkuxvu+===åå(2-8)步骤三：若v(b)-v(b+1)ε，则算法停止并输出划分U和聚类中心V，否则令b=b+1，转向执行步骤一。()2()1()1()1(),1bikbcikmbjjkbikudikdu-=ìïï=ïïïíïïïï=ïîå53．模糊C均值聚类算法的Matlab实现3.1实验数据_Record_XYZTypeRecord_#11739.941675.152395.963Record_#2373.33087.052429.474Record_#31756.7716521514.983Record_#4864.451647.312665.91Record_#5222.853059.542002.334Record_#6877.882031.663071.181Record_#71803.581583.122163.053Record_#82352.122557.041411.532Record_#9401.33259.942150.984Record_#10363.343477.952462.864Record_#111571.171731.041735.333Record_#12104.83389.832421.834Record_#13499.853305.752196.224Record_#142297.283340.14535.622Record_#152092.623177.21584.322Record_#161418.791775.892772.91Record_#171845.591918.812226.493Record_#182205.363243.741202.692Record_#192949.163244.44662.422Record_#201692.621867.52108.973Record_#211680.671575.781725.13Record_#222802.883017.111984.982Record_#23172.783084.492328.654Record_#242063.543199.761257.2126Record_#251449.581641.583405.121Record_#261651.521713.28157