模糊C均值聚类算法的C++实现代码.doc

模糊C均值聚类算法的实现
研讨背景

聚类分析是多元统计分析的一种，也是无监督模式识别的一个重要分支，在模式分类图像处理和模糊规则处理等众多领域中获得最广泛的运用。它把一个没有类别标记的样本按照某种准绳划分为若干子集，使类似的样本尽可能归于一类，而把不类似的样本划分到不同的类中。硬聚类把每个待识别的对象严厉的划分某类中，具有非此即彼的性质，而模糊聚类建立了样本对类别的不确定描述，更能客观的反应客观世界，从而成为聚类分析的主流。
模糊聚类算法是一种基于函数最优方法的聚类算法，使用微积分计算技术求最优代价函数，在基于概率算法的聚类方法中将使用概率密度函数，为此要假定合适的模型，模糊聚类算法的向量可以同时属于多个聚类，从而摆脱上述问题。
模糊聚类分析算法大致可分为三类
1）分类数不定，根据不同要求对事物进行动态聚类，此类方法是基于模糊等价矩阵聚类的，称为模糊等价矩阵动态聚类分析法。
2）分类数给定，寻觅出对事物的最好分析方案，此类方法是基于目标函数聚类的，称为模糊C均值聚类。
3）在摄动成心义的情况下，根据模糊类似矩阵聚类，此类方法称为基于摄动的模糊聚类分析法
我所学习的是模糊C均值聚类算法，要学习模糊C均值聚类算法要先了解虑属度的含义，隶属度函数是表示一个对象x隶属于集合A的程度的函数，通常记做μA(x)，其自变量范围是所有可能属于集合A的对象（即集合A所在空间中的所有点），取值范围是[0,1]，即0<=μA(x)<=1。μA(x)=1表示x完全隶属于集合A，相当于传统集合概念上的x∈A。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A，或者叫定义在论域X={x}上的模糊子集。对于无量个对象x1，x2，……，xn模糊集合可以表示为：
(6.1)
有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因而，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。
FCM算法需求两个参数一个是聚类数目C，另一个是参数m。普通来讲C要远远小于聚类样本的总个数，同时要保证C>1。对于m，它是一个控制算法的柔性的参数，如果m过大，则聚类效果会很次，而如果m过小则算法会接近HCM聚类算法。
算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属准绳就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征，可以认为是这个类的代表点。
从算法的推导过程中我们不难看出，算法对于满足正态分布的数据聚类效果会很好，另外，算法对孤立点是敏感的。
聚类算法是一种比较新的技术，基于曾次的聚类算法文献中最早出现的Single-Linkage层次聚类算法是1957年在Lloyd的文章中最早出现的，以后MacQueen独立提出了经典的模糊C均值聚类算法，FCM算法中模糊划分的概念最早起源于Ruspini的文章中，但关于FCM的算法的详细的分析与改进则是由Dunn和Bezdek完成的。
模糊c均值聚类算法因算法简单收敛速度快且能处理大数据集，解决问题范围广，易于运用计算机实现等特点受到了越来越多人的关注，并运用于各个领域。

算法描述
模糊C均值聚类算法的步骤还是比较简单的，模糊C均值聚类（FCM），即尽人皆知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为初期硬C均值聚类（HCM）方法的一种改进。
FCM把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非类似性目标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1：
(6.9)
那么，FCM的价值函数（或目标函数）就是式（6.2）的普通化方式：
，(6.10)
这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离；且是一个加权指数。
构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件：
(6.11)
这里j，j=1到n，是（6.9）式的n个束缚式的拉格朗日乘子。对所有输入参量求导，使式（6.10）达到最小的必要条件为：
(6.12)
和
(6.13)
由上述两个必要条件，模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运转时，FCM用以下步骤确定聚类中心ci和隶属矩阵U[1]：
步骤1：用值在0，1间的随机数初始化隶属矩阵U，使其满足式（6.9）中的束缚条件
步骤2：用