模式识别大作业.docx

《模式识别大作业.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模式识别大作业模糊聚类算法　模糊聚类算法概述模糊聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求最优代价函数。在基于概率算法的聚类方法中将使用概率密度函数，为此要假定合适的模型，模糊聚类算法的向量可以同时属于多个聚类，从而摆脱上述问题。在模糊聚类算法中，定义了向量与聚类之间的近邻函数，并且聚类中向量的隶属度由隶属函数集合提供。对模糊方法而言，在不同聚类中的向量隶属函数值是相互关联的。硬聚类可以看成是模糊聚类方法的一个特例。模糊聚类算法的分类模糊聚类分析算法大致可分为三类[4]：1）分类数不定，根据不同要求对事物进行动态聚类，此

2、类方法是基于模糊等价矩阵聚类的，称为模糊等价矩阵动态聚类分析法。2）分类数给定，寻找出对事物的最佳分析方案，此类方法是基于目标函数聚类的，称为模c均值聚类。3）在摄动有意义的情况下，根据模糊相似矩阵聚类，此类方法称为基于摄动的模糊聚类分析法。模糊c均值（FCM）聚类算法算法描述模糊c均值聚类算法的步骤还是比较简单的，模糊c均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬c均值聚类（HCM）方法的一种改进。FCM把n个向量xi（i=1

3、,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1：(3.1)那么，FCM的价值函数（或目标函数）就是：，(3.2)这里uij介于0，1间；ci为模糊组I的聚类中心，dij=

4、

5、ci-xj

6、

7、为第I个聚类中心与第j个数据点间的欧几里德距离；且是一个加权指数。构造如下新的目标函数，可求得

8、使（3.2）式达到最小值的必要条件：(3.3)这里lj，j=1到n，是（3.1）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（3.2）达到最小的必要条件为：(3.4)和(3.5)由上述两个必要条件，模糊c均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U[1]：步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（3.1）中的约束条件步骤2：用式（3.4）计算c个聚类中心ci，i=1,…,c。步骤3：根据式（3.2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值

9、的改变量小于某个阀值，则算法停止。步骤4：用（3.5）计算新的U矩阵。返回步骤2。上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。设被分类的对象的集合为：X={x1，x2，…，xN}，其中每一个对象xk有n个特性指标，设为xk=(x1k，x2k，…，xnk)T,如果要把X分成c类，则它的每一个分类结果都对应一个c×N阶的Boolean矩阵U=[uik]c×N，对应的模糊

10、c划分空间为：Mfc={

11、uik∈[0，1]，i，k；=1，k;0<，i}在此空间上，模糊c均值算法如下：Repeatforl=1，2……Step1：computethecluseterprototypes(means)：Step2：competethedistance：Step3：Updatethepartitionmatrix：ForIfforalli=1，2，…，cOtherwise=0if>0，and∈[0，1]withUntil<3.2实验采用著名的iris数据集对算法进行测试实现，其中样本总数m=150，样本属性数n=4，设定的

12、划分内别k=3。运算次数为10次的输出结果：能对数组实现分类，但是分类正确率不是很理想。3.3FCM算法优缺点通过实验和算法的研究学习，不难发现FCM算法的优缺点[5-8]：首先，模糊c均值泛函Jm仍是传统的硬c均值泛函J1的自然推广。J1是一个应用很广泛的聚类准则，对其在理论上的研究已经相当的完善，这就为Jm的研究提供了良好的条件。其次，从数学上看，Jm与Rs的希尔伯特空间结构(正交投影和均方逼近理论)有密切的关联，因此Jm比其他泛函有更深厚的数学基础。最后，FCM聚类算法不仅在许多邻域获得了非常成功的应用，而且以该算法为基础，又提出基于

13、其他原型的模糊聚类算法，形成了一大批FCM类型的算法，比如模糊c线(FCL)，模糊c面(FCP)，模糊c壳(FCS)等聚类算法，分别实现了对呈线状、超平面状和“薄壳”状结构模式子