聚类分析

基于FCM算法的聚类分析

姓名：周大通 学号：20155228016 专业：电子与信息工程

摘要

FCM算法是一种基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。本文以FCM算法为基础在matlab上对7组均值不同服从Beta分布的700个数据进行聚类，并且对结果分析总结。 关键词：FCM算法，聚类

Abstract

FCM algorithm is a clustering algorithm based on partition, and its ideology is such that is divided into the same cluster object similarity between the largest and smallest similarity between different clusters. Fuzzy C-means algorithm is an ordinary C-means algorithm improvements, ordinary C-means algorithm for data classification is rigid, but flexible FCM is a fuzzy partition.In this paper, FCM algorithm based on matlab seven different group means obedience 700 beta distributed data cluster, and the results were analyzed and summarized. Keywords: FCM algorithm; clustering

一、聚类分析的概念

聚类分析指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程。它的目标就是在相似的基础上收集数据来分类。聚类分析是一种非监督分类，也就是说聚类分析基本上无先验知识可依据或参考，它可以从样本数据出发，自动进行分类。聚类分析可以作为其他很多算法的预处理步骤，比如在模式识别里，聚类可以用于语音识别、字符识别等；在机器学习中聚类分析可以应用于图像分割和机器视觉；在图像处理中聚类可以应用于数据压缩和信息检索。

聚类分析把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据，它是按不同对象之间的差异，根据距离函数的规律（大小，即远近）进行模式分类的[1][4]。

为了能将模式集划分成不同的类别，必须定义一种相似性的测度，来度量同一类样本间的类似性和不属于同一类样本间的差异性，如欧式距离等。由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类分析的聚类准则应是反应类别间相似性或分离性的函数，而本文采用FCM函数来实现随机数的聚类。

二、FCM算法介绍 2.1 FCM算法简介

模糊C均值聚类（FCM），即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬C均值聚类（HCM）方法的一种改进，是一种基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小[2]。 2.2 FCM算法描述

FCM把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1。

（2-1）

那么，FCM的价值函数（或目标函数）的一般化形式： ??????

? （2-2） 这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离；且?

是一个加权指数。构造如下新的

目标函数，可求得使式（2-2）达到最小值的必要条件：

????? ???????

（2-3）

? ? ?? ?

这里?j，j=1到n，是（2-1）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（2-2）达到最小的必要条件为： ? ???

和

（2-4）

（2-5）

由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM用下列步骤确定聚类中心ci和隶属矩阵U[1] 。

步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（2-1）中的约束条件。

步骤2：用式（2-4）计算c个聚类中心ci，i=1,…,c。

步骤3：根据式（2-2）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。

步骤4：用（2-5）计算新的U矩阵。返回步骤2。

上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用

另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。

通过上面的讨论，我们不难看出FCM算法需要两个参数一个是聚类数目C，另一个是参数m。一般来讲C要远远小于聚类样本的总个数，同时要保证C>1。对于m，它是一个控制算法的柔性的参数，如果m过大，则聚类效果会很次，而如果m过小则算法会接近HCM聚类算法。

算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征，可以认为是这个类的代表点。从算法的推导过程中我们不难看出算法对孤立点是敏感的[3]。

三、实验结果分析

本实验在MATLAB上进行编程实现，随机产生7组不同均值且服从Beta分布的数据，每组100个数据，一共700个数据，在二维坐标上表示700个样本点如图3-1所示；通过FCM算法将样本数据聚为3类，用不同颜色表示不同的聚类类别，在二维坐标上如图3-2所示。

图3-1 随机产生700个样本点