模糊C均值聚类算法的C 实现代码讲解
模糊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}上的模糊子集
~
A。对于有限个对
象x
1，x
2
，……，x
n
模糊集合
~
A可以表示为：
}
|)
),
(
{(
~
X
x
x
x
A
i
i
i
A
∈
=μ (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 个向量x i （i=1,2,…,n ）分为c 个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM 与HCM 的主要区别在于FCM 用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U 允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1：
∑==?=c
i ij
n j u
1
,...,1,1 (6.9)
那么，FCM 的价值函数（或目标函数）就是式（6.2）的一般化形式：
∑∑∑====c
i n
j
ij m ij c
i i c d u J c c U J 1
2
1
1),...,,(， (6.10)
这里u ij 介于0，1间；c i 为模糊组I 的聚类中心，d ij =||c i -x j ||为第I 个聚类中心与第j 个数据点间的欧几里德距离；且[)∞∈,1m 是一个加权指数。
构造如下新的目标函数，可求得使（6.10）式达到最小值的必要条件：
∑∑∑∑∑∑=====-+=-+=n
j c
i ij j c
i n
j
ij m ij n
j c
i ij j c n c u d u u c c U J c c U J 1
1
1
2
11
111)1()
1(),...,,(),...,,,...,,(λλλλ (6.11)
这里λj ，j=1到n ，是（6.9）式的n 个约束式的拉格朗日乘子。对所有输入参量
求导，使式（6.10）达到最小的必要条件为：
∑∑===
n j m ij
n
j j
m ij
i u x u
c 1
1 (6.12)
和
∑=-???
? ??=
c
k m kj ij ij d d u 1)
1/(21
(6.13)
由上述两个必要条件，模糊C 均值聚类算法是一个简单的迭代过程。在批处理方式运行时，FCM 用下列步骤确定聚类中心c i 和隶属矩阵U[1]：
步骤1：用值在0，1间的随机数初始化隶属矩阵U ，使其满足式（6.9）中的约束条件
步骤2：用式（6.12）计算c 个聚类中心c i ，i=1,…,c 。
步骤3：根据式（6.10）计算价值函数。如果它小于某个确定的阀值，或它相对上次价值函数值的改变量小于某个阀值，则算法停止。
步骤4：用（6.13）计算新的U 矩阵。返回步骤2。 上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM 收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM 。
模糊c 均值聚类算法如下： Reapeat for l=1 2 3……..
Step 1:compute the cluseter prototypes(means):
Step 2:compete the distance:
Step 3:Update the partition matrix:
算法改进
1）在模糊聚类的目标函数中Bezdek引入了加权指数m，使Dum的聚类准则变成m=2时候的特例，从数学上说m的出现不自然且没有必要，
但如果不给以虑属度乘以权值，那么从硬聚类准则函数到软聚类目标
函数的推广准则是无效的，参数m又称为平滑因子，控制着模式早模
糊类间的分享程度，因此，要实现模糊c聚类就要选择一适合的m，
然而最佳的m的选取目前还缺乏理论，监管存在一些经验值或经验范
围，但没有面向问题的优选方法，也缺少参数m的有效性评价准则2）尽管模糊聚类是一种无监督的分类，但现在的聚类算法却=需要应用聚类原型的先验条件，否则算法会产生误导，从未破坏算法的无监督
性和自动化。
3）因为模糊聚类目标是非凸的，而模糊C均值聚类算法的计算过程又是迭代爬山，一次很容易陷入局部极值点，从而得不到最优解或满意解，
同时，大数据量下算法耗时也是困扰人们的一大难题，这2个问题目
前还不能得到全面的解决。
4）FCM类型的聚类算法属于划份方法，对于1组给定的样本集，不管数据中有无聚类结构，也不问分类结果是否有效，总把数据划分到C个
子类中，换言之，现有的聚类分析与聚类趋势，以及有效分析是隔离
的分离得。
5）FCM的聚类算法是针对特征空间中的点集设计的，对于特殊类型的数据，比如在样本每维特征的赋值不是一个数，而是一个区间。集合和
模糊数时，FCM类型的算法无法直接处理
模糊C均值聚类算法存在上述缺点，改进的算法正确率能达到更高。Fcm 算法在处理小数据集的时候是有效的，但随着数据容量和维数的增加，迭代步骤会显著增加，而且在迭代的每一步都要对整个数据集进行操作，无法满足数据挖掘时的需要。
改进算法的思想是首先采用随机抽样的办法，从数据集中选取多个样本，对每个样本应用FCM算法，将得到的结果作为初始群体，然后再利用遗传算法对聚类结果进行优化，选取其中的最优解做为问题的输出，由于采样技术显著的压缩了问题的规模，而遗传又可以对结果进行全局最优化处理，因此在时间性能和聚类质量上都能获得较满意的结果。
遗传算法是美国Michigon大学的John Holland研究机器学习时创立的一种新型的优化算法，它的主要优点是：遗传算法是从一系列点的群体开始搜索而不是从单个样本点进行搜索，遗传算法利用适应值的相关信息，无需连续可导或其他辅助信息，遗传算法利用转移概率规则，而非确定性规则进行迭代，遗传算法搜索过程中，以对群体进行分化以实现并行运算，遗传算法经过遗传变异和杂交算子的作用，以保证算法以概率1收敛到全局最优解—具有较好的全局特性，其次遗传算法占用计算机的内存小，尤其适用计算复杂的非线性问题。
遗传算法的设计部分
（1）种群中个体的确定
聚类的关键问题是聚类中心的确定，因此可以选取聚类中心作为种群的个体，由于共有C个聚类中心，而每个聚类中心是一个S维的实数向量，因此每个个体的初始值是一个c*s维的市属向量。
（2）编码
常用的编码方式有二进制与实数编码，由于二进制编码的方式搜索能力最强，且交叉变异操作简单高效，因此采用二进制的编码方式，同时防止在进行交叉操作时对优良个体造成较大的破坏，在二进制编码的方式中采用格雷码的编码形式。
每个染色体含c*s个基因链，每个基因链代表一维的数据，由于原始数据中各个属性的取值可能相差很大，因此需首先对数据进行交换以统一基因链的长度，可以有以下两种变换方式。
1扫描整个数据集，确定每维数据的取值范围，然后将其变换到同一量级，在保留一定有效位的基础上取整，根据有效位的个数动态的计算出基因链的长度。
2对数据进行正规化处理，即将各维数据都变换到相同的区间，可以算出此时的基因链长度为10。
（3）适应度函数
由于在算法中只使用了聚类中心V，而未使用虑属矩阵u,因此需要对FCM聚类算法的目标函数进行改进，以适用算法的要求，
和目标函数是等价的，由于遗传算法的
适用度一般取值极大，因此可取上式的倒数作为算法的使用度函数。
（4）初始种群的确定
初始种群的一般个体由通过采样后运行FCM算法得到的结果给出，另外的一般个体通过随机指定的方法给出，这样既保证了遗传算法在运算之初就利用背景知识对初始群体的个体进行了优化，使算法能在一个较好的基础上进行，又使得个体不至于过分集中在某一取值空间，保证了种群的多样性。
（5）遗传操作
选择操作采用保持最优的锦标赛法，锦标赛规模为2，即每次随机取2个个体，比较其适应度，较大的作为父个体，并保留每代的最优个体
作为下一代，交叉方式一般采用单点交叉或多点交叉法进行，经过试验
表明单点交叉效果较好，因此采用单点交叉法，同时在交叉操作中，应
该对每维数据分开进行，以保证较大的搜索空间和结果的有效性，变异
操作采用基本位变异法。
（6）终止条件的确定
遗传算法在以下二种情况下终止
a最佳个体保持不变的代数达到设定的阈值
b遗传操作以到达给定的最大世代数
算法具体步骤如下
1确定参数，如聚类个数样本集大小种群规模最大世代数交叉概率
和变异概率等。
2对数据集进行多次采样并运行FCM算法，得到初始种群的一般个体，
通过随机制定产生另一半个体。
3对数据集进行正规化处理并编码。
4计算初始种群中个体的适应度。
5对种群进行遗传操作产生下一代，在操作的过程中，应该排除产生的
无效个体。
6计算个体的适应度，如果满足终止条件，则算法结束，否则转到5继
续
在理论上讲进行遗传操作的样本容量越大，聚类的误差越小，由于采样技术显著压缩了问题规模，而遗传算法又可以对全局进行最优化
处理，因此改进的算法在时间与性能上都能获得较满意的结果，此算法
利用采样技术来提高算法的运行速度，利用遗传算法对聚类进行优化，
避免陷入局部最优解，在性能上相比于传统的模糊C均值聚类算法获得
较大提高。
算法实现
·采用VC++进行编写
文档的读取
#include "data.h"
//函数定义
double **DataRead(char*name,int row,int col)
{
double **p=new double* [row];
ifstream infile;
infile.open(name,ios::in);
for(int i=0;i { p[i]=new double[col]; for(int j=0;j { infile>>p[i][j]; } } infile.close(); cout<<"成功读取数据文件:"< return p; //释放内存 for(i=0;i { delete[]p[i]; } delete[]p; } 文档的保存 #include "data.h" void DataSave(double**data,int row,int col,char*name) { int i,j; ofstream outfile; //打开文件，输出数据 outfile.open(name,ios::out); outfile.setf(ios::fixed); outfile.precision(4); for(i=0;i { for(j=0;j { outfile< } outfile< } outfile< outfile.close(); } 数据标准化处理 #include "data.h" double **Standardize(double **data,int row,int col) { int i,j; double* a=new double[col]; //矩阵每列的最大值 double* b=new double[col]; //矩阵每列的最小值 double* c=new double[row]; //矩阵列元素 for(i=0;i { //取出数据矩阵的各列元素 for(j=0;j { c[j]=Data[j][i]; } a[i]=c[0],b[i]=c[0]; for(j=0;j { //取出该列的最大值 if(c[j]>a[i]) { a[i]=c[j]; } //取出该列的最小值 if(c[j] { b[i]=c[j]; } } } //数据标准化 for(i=0;i { for(j=0;j { data[i][j]=(data[i][j]-b[j])/(a[j]-b[j]); } } cout<<"完成数据极差标准化处理!\n"; delete[]a; delete[]b; delete[]c; return data; } 生成样本虑属矩阵 #include "data.h" void Initialize(double **u, int k, int row) { int i,j; //初始化样本隶属度矩阵 srand(time(0)); for(i=0;i { for(j=0;j { u[i][j]=(double)rand()/RAND_MAX;//得到一个小于1的小数隶属度 }//rand()函数返回0和RAND_MAX之间的一个伪随机数 } } 数据归一化处理 #include "data.h" void Normalize(double **u,int k,int col) { int i,j; double *sum=new double[col]; //矩阵U的各列元素之和 for(j=0;j { double dj=0; for(i=0;i { dj=dj+U[i][j]; sum[j]=dj;//隶属度各列之和 } } for(i=0;i { for(j=0;j { u[i][j]=U[i][j]/sum[j]; }//规一化处理(每列隶属度之和为1) } } 迭代过程 #include "data.h" #include "func.h"//对模糊C均值进行迭代运算,并返回有效性评价函数的值double Update(double**u,double**data,double**center,int row,int col, int k) { int i,j,t; double **p=NULL; for(i=0;i { for(j=0;j { //模糊指数取2 u[i][j]=pow(u[i][j],2); } } //根据隶属度矩阵计算聚类中心 p=MatrixMul(u,k,row,data,row,col); for(i=0;i { //计算隶属度矩阵每行之和 double si=0; for(j=0;j { si+=u[i][j]; } for(t=0;t { center[i][t]=p[i][t]/si; //类中心 } } //计算各个聚类中心i分别到所有点j的距离矩阵dis(i,j) double* a=new double[col]; //第一个样本点 double* b=new double[col]; //第二个样本点 double**dis=new double*[k]; //中心与样本之间距离矩阵 for(i=0;i { dis[i]=new double[row]; } for(i=0; i { //聚类中心 for(t=0; t { a[t]=center[i][t]; //暂存类中心 } //数据样本 for(j=0; j { for(t=0; t { b[t]=data[j][t];//暂存一样本 } double d=0; //中心与样本之间距离的计算 for(t=0; t { d+=(a[t]-b[t])*(a[t]-b[t]); //d为一中心与所有样本的距离的平方和 } dis[i][j]=sqrt(d); //距离 } } //根据距离矩阵计算隶属度矩阵 for(i=0;i { for(j=0;j { double temp=0; for(t=0;t { //dis[i][j]依次除以所在列的各元素,加和； //模糊指数为2.0 temp+=pow(dis[i][j]/dis[t][j],2/(2.0-1));//一个类中心和一个元素的距离平方与 } u[i][j]=1/temp;//所有类与该元素距离平方的和的商 } } //计算聚类有效性评价函数 double func1=0; for(i=0;i { double func2=0; for(j=0;j { func2+=pow(u[i][j],2.0)*pow(dis[i][j],2); } func1+=func2; } double obj_fcn=1/(1+func1); return obj_fcn; //内存释放 delete[]a; delete[]b; for(i=0;i { delete[]dis[i]; } delete[]dis; } 详细过程 #include "data.h" #include "func.h" #include "max.h" //全局变量定义 double **Data; //数据矩阵 double **Center; //聚类中心矩阵double **U; //样本隶属度矩阵 int m; //样本总数 int n; //样本属性数 int k; //设定的划分类别数 int main() { int Lab; //数据文件标号 int num; //算法运行次数 /////////////////////////////////////////////////////////////// cout<<"模糊C均值聚类算法:"< cout<<"1-iris.txt; 2-wine.txt; 3-ASD_12_2.txt; 4-ASD_14_2.txt"< cout<<"请选择数据集: Lab="; cin>>Lab; cout<<"设定运行次数: mum="; cin>>num; //各次运行结束后的目标函数 double* Index=new double[num]; //各次运行结束后的聚类正确率 double* R=new double [num]; //num次运行的平均目标函数及平均正确率 double M_Index=0; double M_R=0; //FCM聚类算法运行num次，并保存记录与结果 for(int i=0;i { int j; double epsilon=1e-4; int e=0; int nx=0; //记录连续无改进次数 int E[200]={0}; if(i>0) { cout< cout< } cout<<"第"< //读取数据文件 if(Lab==1) { m=150; n=4; k=3; Data=DataRead("dataset\\iris.txt",m,n); } else if(Lab==2) m=178; n=13; k=3; Data=DataRead("dataset\\wine.txt",m,n); } else if(Lab==3) { m=535; n=2; k=12; Data=DataRead("dataset\\ASD_12_2.txt",m,n); } else if(Lab==4) { m=685; n=2; k=14; Data=DataRead("dataset\\ASD_14_2.txt",m,n); } //数据极差标准化处理 Data=Standardize(Data,m,n); //聚类中心及隶属度矩阵,内存分配 Center=new double*[k]; U=new double *[k]; for(j=0;j { Center[j]=new double[n]; U[j]=new double[m]; } //隶属度矩阵的初始化 Initialize(U, k, m); //对隶属度矩阵进行归一化 Normalize(U,k,m); //历次迭代过程中的目标函数 double Objfcn[100]={0}; cout<<"第"< cout<<"开始迭代过程!"< cout<<"*******************************"< //输出精度为小数点后5位 cout.precision(5); //固定格式 cout.setf(ios::fixed); //目标函数连续20代无改进，停止该次聚类迭代过程while(e<20) { nx++; //聚类迭代过程 Objfcn[nx]=Update(U,Data,Center,m,n,k); //统计目标函数连续无改进次数e if(nx>0 && Objfcn[nx]-Objfcn[nx-1] e++; } else { e=0; } E[nx]=e; } //输出结果到文件，保存 ofstream outfile("运行记录.txt",ios::app); outfile<<"第"< outfile<<"开始迭代过程!"< outfile<<"*******************************"< outfile.precision(5); outfile.setf(ios::fixed); for(int n1=1;n1<=nx;n1++) { cout<<"e["< Objfcn[" < //保存数据文件 outfile<<"e["< < } cout< outfile< outfile.close(); //本次运行的最大目标函数 Index[i]=Objfcn[nx]; //保存聚类正确率，输出聚类结果： R[i]=Result(Lab, U, k, m, i); //内存释放 for(j=0;j { delete[]Center[j]; delete[]U[j]; } delete[]Center; delete[]U; } //////////////////////////统计平均/////////////////////////////////// double temp1=0, temp2=0; for(i=0;i { temp1+=Index[i]; temp2+=R[i]; } //计算各次结果的统计平均 M_Index=(double)temp1/num; M_R=(double)temp2/num; cout<<"////////////////////////////////////////////////////////// ////"< cout< //输出精度为小数点后6位 cout.precision(6); //固定格式 cout.setf(ios::fixed); cout<<"平均目标函数: "< //统计结果文件保存 ofstream resultfile("聚类结果.txt",ios::app); resultfile<<"//////////////////////////////////////////////////// //////////"< resultfile< //输出精度为小数点后6位 resultfile.precision(6); //固定格式 resultfile.setf(ios::fixed); resultfile<<"平均目标函数: "< return 0; } 采用著名的iris数据集对程序进行测试， 运算次数输入10次 能对数组实现分类，但是分类正确率不是很理想，没达到预期的90%以上 总结 这次综合实习，首先我学会了模糊C均值聚类算法，以前没接触过，也不知道何为数据集，数据集是做啥用的，增加了自己的见解，其次增强了自我学习能力，平时学习的学习都是老师已经安排好得内容，看啥知识都已经知道，只需要安心的看就能学会，都是书本上的知识，没有联系实际，一般都是一些理论算法，算法比较简单而且古老，但这次综合实习通过自己从网上查找资料学习，了解算法的详细步骤，研究算法的不足，虽然查找资料学习的过程比较繁琐，但总算在最后学会了模糊C均值聚类算法，也对算法的改进有所了解，人工智能学习的GA遗传算法进行了改进，通过这次综合实习，我对不懂得知识的学习有了一个比较系统的学习过程，为以后的自我学习打下了基础，模糊C均值聚类算法的程序是用c++实现的，通过对程序的而研究，我对于文件的读取保存计算的迭代 过程等都已经非常的了解，对于以前所学的进行了一次复习，这次综合实现收获 很大，自己所学的东西学会了如何使用，不同的算法进行衔接进行优化，实现对 最优解的优化，感谢朱老师的帮助使我能顺利的完成综合实习。 参考文献 [1] 高新波，模糊c均值聚类算法中加权指数m的研究[J],电子学报，2000，28（4）：80-83 [2] 朱剑英，应用模糊数学方法的若干关键问题及处理方法[j].模糊系统与数学，1992，11（2）：57-63 [3] 刘蕊洁张金波刘锐，模糊c均值聚类算法，重庆工学院学报，2007-21-1 [4] 高新波。模糊聚类分析及其应用[M].西安：西安电子科学出版社，2004 [5] 高新波，谢维信.模糊聚类理论发展及应用的研究进展[J].科学 通报，1999，44（21）：2241-2251 [6] 张洁，高新波，焦李成.基于特征加权的模糊聚类新算法[J],电 子学报，2006，34（1）：412-420 [7] Chan K P, Cheung Y S. Clustering of clusters [J]. Pattern Recognition,1992,25(2):211-217 [8] Spragins J.Learning without a teacher[J].IEEE Transactions of Infornation Theory,2005,23(6):223-230. [9] Babusk R . FUZZY AND NEURAL CONTROL[M].Nethealands:Delft FCM模糊c均值 1、原理详解 模糊c-均值聚类算法fuzzy c-means algorithm (FCMA)或称（FCM）。在众多模糊聚类算法中，模糊C-均值（FCM）算法应用最广泛且较成功，它通过优化目标函数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到自动对样本数据进行分类的目的。 聚类的经典例子 然后通过机器学习中提到的相关的距离开始进行相关的聚类操作 经过一定的处理之后可以得到相关的cluster，而cluster之间的元素或者是矩阵之间的距离相对较小，从而可以知晓其相关性质与参数较为接近 C-Means Clustering： 固定数量的集群。 每个群集一个质心。 每个数据点属于最接近质心对应的簇。 1.1关于FCM的流程解说其经典状态下的流程图如下所示 集群是模糊集合。 一个点的隶属度可以是0到1之间的任何数字。 一个点的所有度数之和必须加起来为1。 1.2关于k均值与模糊c均值的区别 k均值聚类：一种硬聚类算法，隶属度只有两个取值0或1，提出的基本根据是“类内误差平方和最小化”准则，进行相关的必要调整优先进行优化看是经典的欧拉距离，同样可以理解成通过对于cluster的类的内部的误差求解误差的平方和来决定是否完成相关的聚类操作；模糊的c均值聚类算法：一种模糊聚类算法，是k均值聚类算法的推广形式，隶属度取值为[0 1]区间内的任何数，提出的基本根据是“类内加权误差平方和最小化”准则； 这两个方法都是迭代求取最终的聚类划分，即聚类中心与隶属度值。两者都不能保证找到问题的最优解，都有可能收敛到局部极值，模糊c均值甚至可能是鞍点。 1.2.1关于kmeans详解 K-means算法是硬聚类算法，是典型的基于原型的目标函数聚类方法的代表，它是数据点到原型的某种距离作为优化的目标函数，利用函数求极值的方法得到迭代运算的调整规则。K-means算法以欧式距离作为相似度测度，它是求对应某一初始聚类中心向量V最优分类，使得评价指标J最小。算法采用误差平方和准则函数作为聚类准则函数。 关于其优点： K-均值聚类分析是一种硬划分，它把每一个待识别的对象严格的划分到某一类中，具有非此即彼的性质。而实际上高光谱值目标在形态和类属方面存在着中介性，没有确定的边界来区分。因此需要考虑各个像元属于各个类别的隶属度问题，进行软划分，从而更好的区分。 设要进行聚类分析的图像像元数N ，图像像元集合{}N x x x X ,...,,21=，其中 {} T p k k k k x x x x ,...,,2 1=，p 为波段数。设把图像分为C 个类别，每个类别的聚类中心 ),...,,(21p i i i i v v v v =，聚类中心集合{}c v v v V ,...,,21=。用ik u 表示像元k x 隶属于以i v 为中心的类别i 的隶属度，定义隶属度矩阵U 为[]N C ik u U ?=。 矩阵U 中每一列的元素表示所对应的像元隶属于C 个类别中各个类的隶属度。满足一下约束条件： ???? ?????≤≤===>∑∑==10,...2,1;,...,2,1. (101) 1ik C i ik N k ik u N k C i u u 对隶属度ik u 进行了迷糊化，ik u 可取0和1之间的任意实数，这样一个像元可以同时隶 属于不同的类别，但其隶属度的总和总是等于1，这符合高光谱像元的实际情况。而属于硬聚类的K-均值聚类，其隶属度具有非此即彼的性质，隶属度ik u 只能取0或1。 定义目标函数J 为 ∑∑==?=N k C i ik m ik m d u V U J 11 2)()(),( 22)(i k ik v x d -=为Euclidean 距离；[)∞∈,1m 为模糊加权指数（当m=1时，同K- 均值的目标函数一致）。最优化的类就是使目标函数取最小值的类，如果一类中的所有点都 贴近于它们的类中心，则目标函数很小。 FCM 算法步骤： （1） 确定聚类数C ，加权指数m ，终止误差ε，最大迭代次数LOOP 。 （2） 初始化隶属度矩阵) 0(U （3） 开始循环，当迭代次数为IT （IT=0,1,2…,C ）时，根据) (IT U 计算C-均值向量， 即C i u x u U N k N k m ik k m ik IT ,...,2,1],))(/()([1 1 ) (==∑∑== （4） 对k=1,2,…,N ，按以下公式更新) (IT U 为) 1(+IT U ： 若i k v x ≠对所有的i v (i=1,2,…,C)满足，则对此k x 计算 C i v x d d u i k C j m jk ik ik ,...,2,1,,])([1112 =≠=-=-∑ 若对某一个i v ，有k x 满足i k v x =，则对应此k x ，令)(0;1i j u u jk ik ≠==。这样把聚 类中心与样本一致的情形去掉，把隶属度模糊化为0和1之间的实数。 （5） 若ε<+)1() (-IT IT U U 或IT>LOOP ，停止；否则置IT=IT+1，并返回第三步。 FCM 算法允许自由选取聚类个数，每一向量按其指定的隶属度]1,0[∈ik u 聚类到每一聚类中心。FCM 算法是通过最小化目标函数来实现数据聚类的。 function [center, U, obj_fcn] = FCMClust(data, cluster_n, options) % FCMClust.m 采用模糊C均值对数据集data聚为cluster_n类 % 用法： % 1. [center,U,obj_fcn] = FCMClust(Data,N_cluster,options); % 2. [center,U,obj_fcn] = FCMClust(Data,N_cluster); % 输入： % data ---- nxm矩阵,表示n个样本,每个样本具有m的维特征值 % N_cluster ---- 标量,表示聚合中心数目,即类别数 % options ---- 4x1矩阵，其中 % options(1): 隶属度矩阵U的指数，>1 (缺省值: 2.0) % options(2): 最大迭代次数(缺省值: 100) % options(3): 隶属度最小变化量,迭代终止条件(缺省值: 1e-5) % options(4): 每次迭代是否输出信息标志(缺省值: 1) % 输出： % center ---- 聚类中心 % U ---- 隶属度矩阵 % obj_fcn ---- 目标函数值 % Example: % data = rand(100,2); % [center,U,obj_fcn] = FCMClust(data,2); % plot(data(:,1), data(:,2),'o'); % hold on; % maxU = max(U); % index1 = find(U(1,:) == maxU); % index2 = find(U(2,:) == maxU); % line(data(index1,1),data(index1,2),'marker','*','color','g'); % line(data(index2,1),data(index2,2),'marker','*','color','r'); % plot([center([1 2],1)],[center([1 2],2)],'*','color','k') % hold off; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%% if nargin ~= 2 & nargin ~= 3, %判断输入参数个数只能是2个或3个 error('Too many or too few input arguments!'); end data_n = size(data, 1); % 求出data的第一维(rows)数,即样本个数 in_n = size(data, 2); % 求出data的第二维(columns)数，即特征值长度 % 默认操作参数 default_options = [2; % 隶属度矩阵U的指数 100; % 最大迭代次数 1e-5; % 隶属度最小变化量,迭代终止条件 模糊C均值聚类算法及实现 ————————————————————————————————作者：————————————————————————————————日期： 模糊C均值聚类算法及实现 摘要：模糊聚类是一种重要数据分析和建模的无监督方法。本文对模糊聚类进行了概述，从理论和实验方面研究了模糊c均值聚类算法，并对该算法的优点及存在的问题进行了分析。该算法设计简单，应用范围广，但仍存在容易陷入局部极值点等问题，还需要进一步研究。关键词：模糊c均值算法；模糊聚类；聚类分析 Fuzzy c-Means Clustering Algorithm and Implementation Abstract: Fuzzy clustering is a powerful unsupervised method for the analysis of data and construction of models.This paper presents an overview of fuzzy clustering and do some study of fuzzy c-means clustering algorithm in terms of theory and experiment.This algorithm is simple in design,can be widely used,but there are still some problems in it,and therefore,it is necessary to be studied further. Key words: fuzzy c-Mean algorithm；fuzzy clustering；clustering analysis 1 引言 20世纪90年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常方便地获取和存储大量的数据。但是，面对大规模的数据，传统的数据分析工具只能进行一些表层的处理，比如查询、统计等，而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地、自动地把数据转换成有用信息和知识的技术和工具，这种对强有力数据分析工具的迫切需求使得数据挖掘技术应运而生。 将物理或抽象对象的集合分组成由类似的对象组成的多个类的过程称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。 聚类是一种重要的数据分析技术，搜索并且识别一个有限的种类集合或簇集合，进而描述数据。聚类分析作为统计学的一个分支，己经被广泛研究了许多年。 模糊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}上的模糊子集 ~ A。对于有限个对 象x 1，x 2 ，……，x n 模糊集合 ~ A可以表示为： } |) ), ( {( ~ X x x x A i i i A ∈ =μ (6.1) 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。 FCM算法需要两个参数一个是聚类数目C，另一个是参数m。一般来讲C要远远小于聚类样本的总个数，同时要保证C>1。对于m，它是一个控制算法的柔性的参数，如果m过大，则聚类效果会很次，而如果m过小则算法会接近HCM 聚类算法。 算法的输出是C个聚类中心点向量和C*N的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均 模糊c均值聚类FCM算法的MATLAB代码 我做毕业论文时需要模糊C-均值聚类，找了好长时间才找到这个，分享给大家： FCM算法的两种迭代形式的MA TLAB代码写于下,也许有的同学会用得着: m文件1/7: function [U,P,Dist,Cluster_Res,Obj_Fcn,iter]=fuzzycm(Data,C,plotflag,M,epsm) % 模糊C 均值聚类FCM: 从随机初始化划分矩阵开始迭代 % [U,P,Dist,Cluster_Res,Obj_Fcn,iter] = fuzzycm(Data,C,plotflag,M,epsm) % 输入: % Data: N×S 型矩阵,聚类的原始数据,即一组有限的观测样本集, % Data 的每一行为一个观测样本的特征矢量,S 为特征矢量 % 的维数,N 为样本点的个数 % C: 聚类数,1 关于模糊C均值聚类 聚类是这样一个过程, 它将特征向量以自组织的模式分组 到类中。假设{ (q): q= 1, , Q}是一组特征向量的集合, 每个 特征向量 (q) = ( 1(q) , , N (q) )有N 个组件。聚类的过程通常 就是根据最小距离赋值原则将Q 个特征向量分配到K 个簇{c(k) : k = 1, , K} 中。 FCM 是目前广泛采用的一种聚类算法。模糊c-均值聚类是模糊聚类算法中 非常有效的一种, 它能给出每个样本隶属于某个聚类的隶属度, 即使对于 很难明显分类的变量, 模糊c- 均值聚类也能得到较为满意的效果。FCM 算法使用了最小化整个权重的均方差的思想。 模糊c-均值聚类算法 fuzzy c-means algorithm (FCMA)或称（ FCM）模糊聚类分析作为无监督机器学习的主要技术之一，是用模糊理论对 重要数据分析和建模的方法，建立了样本类属的不确定性描述，能比较客 观地反映现实世界，它已经有效地应用在大规模数据分析、数据挖掘、矢 量量化、图像分割、模式识别等领域，具有重要的理论与实际应用价值， 随着应用的深入发展，模糊聚类算法的研究不断丰富。在众多模糊聚类算 法中，模糊C-均值（ FCM）算法应用最广泛且较成功，它通过优化目标函 数得到每个样本点对所有类中心的隶属度，从而决定样本点的类属以达到 自动对数据样本进行分类的目的。 假设样本集合为X={x1 ，x2 ，…，xn }，将其分成c 个模糊组，并求 每组的聚类中心cj （ j=1，2，…，C），使目标函数达到最小。 下面是FCM算法在MATLAB中的使用案例： data = rand(100,2); plot(data(:,1), data(:,2),'o'); [center,U,obj_fcn]=fcm(data,3); maxU = max(U); index1 = find(U(1,:) == maxU); index2 = find(U(2,:) == maxU); index3 = find(U(3,:) == maxU); figure; line(data(index1,1),data(index1,2),'linestyle','*','color','k'); 模糊C均值聚类分析 20世纪90年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常方便地获取和存储大量的数据。但是，面对大规模的数据，传统的数据分析工具只能进行一些表层的处理，比如查询、统计等，而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地、自动地把数据转换成有用信息和知识的技术和工具，这种对强有力数据分析工具的迫切需求使得数据挖掘技术应运而生。 将物理或抽象对象的集合分组成由类似的对象组成的多个类的过程称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。 聚类是一种重要的数据分析技术，搜索并且识别一个有限的种类集合或簇集合，进而描述数据。聚类分析作为统计学的一个分支，己经被广泛研究了许多年。而且，聚类分析也已经广泛地应用到诸多领域中，包括数据分析、模式识别、图像处理以及市场研究。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。在商务上，聚类能帮助市场分析人员从客户基本信息库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房屋的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。基于层次的聚类算法文献中最早出现的Single-Linkage层次聚类算法是1957年在Lloyd的文章中最早出现的，之后MacQueen独立提出了经典的模糊C均值聚类算法，FCM算法中模糊划分的概念最早起源于Ruspini的文章中，但关于FCM的算法的详细的分析与改进则是由Dunn和Bezdek完成的。 聚类分析是多元统计分析的一种，也是非监督模式识别的一个重要分支，在模式分类、图像处理和模糊规则处理等众多领域中获得最广泛的应用。它把一个没有类别标记的样本集按某种准则划分为若干个子集(类)，使相似的样本尽可能的归为一类，而将不相似的样本尽量划分到不同的类中。硬聚类把每个待辨识的对象严格地划分到某类中，具有非此即彼的性质，模糊聚类由于能够描述样本类 实验二模糊C均值聚类 实验目的： 学会使用MATLAB软件进行模糊C均值聚类，学会如何进行迭代并观察迭代过程。 实验学时：4学时 实验内容： 1、认真阅读guide.doc文件，通过给出的英文的例子学习进行C均值聚类的具体步骤。 2、在学习完所给的例子后进行实际操作。根据表格提供的固定资本和人力资本等进行聚类分布。进一步熟悉和掌握熟悉FUZZY CLUSTERING. 实验日期：2013年4月24日 实验过程： 1、查看所给数据表格（如下），由经济学理论知，GDP的产出状况是由固定资本的投入和人力资源的投入决定的。因此，实际上我们只需要选取固定资本和人力资源这两组数据进行处理就行了。 2、通过学习guide中的范例，将所给的defcm.m程序进行重新编辑。其具体程序如下： function [NCentres, M] = defcm(Centres, q) Tiles = [ 5.9489 1.3600 1 4.0308 1.3990 1 2.0314 0.3850 1 1.4208 1.2810 1 8.0396 1.7480 1 2.2450 1.0880 1 3.1038 0.8940 1 2.0523 1.1550 1 1.6534 0.9470 1 2.7298 1.0260 1 1.6223 0.8690 -1 1.0337 0.7960 -1 1.1099 0.9310 -1 0.3114 1.0220 -1 0.8112 0.6140 -1 0.7494 0.7850 -1 1.9210 0.6530 -1 1.3820 1.0000 -1 0.9171 0.6660 -1 0.8342 0.5460 -1 0.8127 0.6200 -1 0.8127 0.6200 -1 1.0410 0.5630 -1 0.5756 0.2990 -1 1.0166 0.4660 -1 1.3588 0.5240 -1 1.0307 0.5740 -1 0.8544 0.4590 -1 1.508 0.5500 -1 1.5036 0.5180 -1 2.0226 0.9110 -1 ] ; % 将固定资本和人力资本的数据按GDP的平均值进行分类，大于平均值的分为一类，记为1，小于平均值的分为一类，记为-1 Tiles(:, 1) = log(Tiles(:, 1)) ; Tiles(:, 2) = log(Tiles(:, 2)) ; clf ; hold off; plot(Tiles(1:16, 1), Tiles(1:16, 2), 'ob') ; axis([-1.5 2.5 -1.5 2.5]) ; xlabel('固定资本') ; ylabel('人力资本') ; title('Tiles data: o = whole tiles, * = cracked tiles, x = centres') ; FCM 算法是一种基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C 均值算法是普通C 均值算法的改进，普通C 均值算法对于数据的划分是硬性的，而FCM 则是一种柔性的模糊划分。在介绍FCM 具体算法之前我们先介绍一些模糊集合的基本知识。 6.1.1 模糊集基本知识[21] 首先说明隶属度函数的概念。隶属度函数是表示一个对象x 隶属于集合A 的程度的函数，通常记做μA (x)，其自变量范围是所有可能属于集合A 的对象（即集合A 所在空间中的所有点），取值范围是[0,1]，即0<= μA (x)<=1。μA (x)=1表示x 完全隶属于集合A ，相当于传统集合概念上的x ∈A 。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A ，或者叫定义在论域X={x}上的模糊子集~ A 。对于有限个对象x 1，x 2，……，x n 模糊集合~ A 可以表示为： }|)),({(~ X x x x A i i i A ∈=μ (6.1) 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。 6.1.2 K 均值聚类算法(HCM)介绍 K 均值聚类，即众所周知的C 均值聚类，已经应用到各种领域。它的核心思想如下：算法把n 个向量x j (1,2…,n)分为c 个组G i (i=1,2,…,c)，并求每组的聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。当选择欧几里德距离为组j 中向量x k 与相应聚类中心c i 间的非相似性指标时，价值函数可定义为： ∑∑∑=∈=-== c i Gi x k i k c i k c x Ji J 1 ,2 1 )||||( (6.2) 这里∑∑=∈-= c i Gi x k i k k c x Ji 1 ,2 )||||(是组i 内的价值函数。这样J i 的值依赖于G i 的几何特性和c i 的位置。 一般来说，可用一个通用距离函数d(x k ,c i )代替组I 中的向量x k ，则相应的总价值函数可表示为： ∑∑∑==∈-== c i c i Gi x k i k k c x Ji J 1 1 ,))d(( (6.3) 为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（6.2）式。 划分过的组一般用一个c ×n 的二维隶属矩阵U 来定义。如果第j 个数据点x j 属于组i ，则U 中的元素u ij 为1；否则，该元素取0。一旦确定聚类中心ci ，可导出如下使式（6.2）最小u ij ： ?? ???-≤-≠=其它 ， 如果对每个0,12 2 k j i j ij c x c x i k u (6.4) 模糊C均值聚类算法及实现 摘要：模糊聚类是一种重要数据分析和建模的无监督方法。本文对模糊聚类进行了概述，从理论和实验方面研究了模糊c均值聚类算法，并对该算法的优点及存在的问题进行了分析。该算法设计简单，应用范围广，但仍存在容易陷入局部极值点等问题，还需要进一步研究。关键词：模糊c均值算法；模糊聚类；聚类分析 Fuzzy c-Means Clustering Algorithm and Implementation Abstract: Fuzzy clustering is a powerful unsupervised method for the analysis of data and construction of models.This paper presents an overview of fuzzy clustering and do some study of fuzzy c-means clustering algorithm in terms of theory and experiment.This algorithm is simple in design,can be widely used,but there are still some problems in it,and therefore,it is necessary to be studied further. Key words: fuzzy c-Mean algorithm；fuzzy clustering；clustering analysis 1 引言 20世纪90年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常方便地获取和存储大量的数据。但是，面对大规模的数据，传统的数据分析工具只能进行一些表层的处理，比如查询、统计等，而不能获得数据之间的内在关系和隐含的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能地、自动地把数据转换成有用信息和知识的技术和工具，这种对强有力数据分析工具的迫切需求使得数据挖掘技术应运而生。 将物理或抽象对象的集合分组成由类似的对象组成的多个类的过程称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。 聚类是一种重要的数据分析技术，搜索并且识别一个有限的种类集合或簇集合，进而描述数据。聚类分析作为统计学的一个分支，己经被广泛研究了许多年。而且，聚类分析也已经广泛地应用到诸多领域中，包括数据分析、模式识别、图像处理以及市场研究[1]。通过聚类，人们能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。在商务上，聚类能帮关于模糊c均值聚类算法
模糊C均值聚类 及距离函数的优缺点
FCMClust(模糊c均值聚类算法MATLAB实现)
模糊C均值聚类算法及实现
模糊C均值聚类算法的C 实现代码讲解
模糊c均值聚类+FCM算法的MATLAB代码
模糊C均值聚类算法
模糊C均值聚类
模糊C均值聚类程序
模糊c均值聚类
模糊C均值聚类算法及实现