模式识别实验---C-均值算法与模糊C均值聚类的比较
实验一、C-均值算法与模糊C 均值聚类的比较
一、实验目的
1. 通过对算法的编程实现，加强对该算法的认识和理解，提高自身的知识水平
和编程能力，认识模式识别在生活中的应用； 2. 深入理解C 均值和模糊C 均值的基本原理； 3. 采用两种分类方式进行仿真；
二、 实验原理
1.C 均值的原理；
C 均值聚类算法是一种典型的无监督动态聚类算法。该算法是在类别数目已知（=k ）的条件下进行的，能够使聚类结果的距离平方和最小，即算法的基础是误差平方和准则。其基本过程是建立初始的聚心和聚类，通过多次迭代，逐渐调整各类的聚心和各像元的类别，直至得到聚类准则约束下的最好结果为止。
本实验的具体过程如下：
选择初始类别中心，假设有c 个类别，设置其中心分别为(1)(1)(1)1
2,,,c Z Z Z 在第k 步迭代中，对于任何一个像元x(是一个N 维向量，N 是高光谱图像的
波段数目)，按如下方法把它调整到。各类别中的某一个类别中去。
令d(x ，y)为向量x ，y 之间的距离，若：
()()(,)(,)k k i j d x Z d x Z <=， j = 1 2 … c (j i ≠)
则()k i x S ∈，其中()k i S 是以()k i Z 为中心的类。
由上一步得到的()k i S （i =1 2…c ）个类别新的中心(1)k i Z +
()
(1)1k i k i x S i
Z x N +∈=
∑
其中N i 是类别()k i S 的数目。(1)k i Z +是按照最小J 的原则，J 的表达式为：
()
(1)1
(,)k i c
k i
i x S J d x Z
+=∈=∑
∑
对所有的i =1 2…c 。如果，(1)()k k i i Z Z +=，则迭代结束（在程序中，则按照每个类别的对应的那些像素不再变化，则停止迭代），否则转到第二步继续迭代。
2．模糊C 均值的原理
在数字图像由于存在混合像素的原因，也就是说一个像素中不仅存在一类地物，因而采用硬分类方式往往不合适，而模糊C 均值就是引入模糊集对每个像
素的划分概率不单单是用0或1这样的硬分类方式，而是0和1之间的范围内（包括0和1）。
定义{},1,2,...,i x i n =是n 个样本组成的样本集合，c 为预定的类别数目，
,1,2,...,i m i c =为每个聚类中心，()j i u x 是第i 个样本对于第j 类的隶属度函数。用隶属度函数定义的聚类损失函数可以写为：
2
11
(),c
n
b f j i i j j i J u x x m ==??=-??∑∑
其中，1b >是一个可以控制聚类结果的模糊程度的常数。
在不同的隶属度定义方法下最小化式的损失函数，就得到不同的模糊聚类方法。其中最有代表的是模糊C 均值方法，它要求一个样本对于各个聚类的隶属度之和为1，即
1()1,c
j
i
j u x ==∑ 1,2,...
,i n = 在条件式下求得其极小值，令f J 对i m 和()j i u x 的偏导数为0，可得必要条件：
1
1
(),1,2,...,()n
b
j i i i i n
b
j i i u x x m j c u x ==????=
=????
∑
∑
，
()()
()
()
1/121/121
1/(),1,2,...,1/b i
j
j
i
c
b i
j
k x m u x i n x m --=-=
=-∑ 1,2,...,j c =。
用迭代的方法求解上式，就是模糊C 均值算法。算法步骤如下：
1） .设定聚类数目c 和参数b 。
2） 初始化各个聚类中心i m 。
3）重复下面的运算，直到各个样本的隶属度值稳定：
当算法收敛时，就得到了各类的聚类中心和各个样本对于各类的隶属度值，从而完成了模糊聚类划分。
三、 实验要求
1.编写C-均值算法，并用上表数据按下列条件分别测试。
（a ） c=2(类别数)；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)
（b ） c=2(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)。将得到的结
果与（a ）中结果比较，并解释差别，包括迭代次数的差别。 （c ） c=3(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2) （d ） c=2(类别数)；初始聚类的均值：m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，
m3(0)=(-0.1,-0.1,0.1)。将得到的结果与（a ）与（c ）中结果比较，并解释差别，包括迭代次数的差别。 2.重做（1），但利用模糊C 均值聚类，并设置:b=2。并与C-均值算法比较。
四、 实验结果及分析
1、c=2(类别数)；初始聚类的均值：m1(0)=(1,1,1),m2(0)=(-1,1,-1)
在设定初始中心m1(0)=(1,1,1),m2(0)=(-1,1,-1)情况下分得的结果如图1，绿色和红色分别是两种不同的种类。C 均值聚类（K 均值聚类）是采用欧氏距离作为类别的相似性度量，也就是说与某个类别中心相聚最近就判属于这类。由图1可以看出绿色“o ”和红色“*”两种种类中间存在着一个较大的间距，因而可以将这两类样本区别开来。
10
X1
the first results of kmeans
X2
X 3
图1 分类结果
在同样的初始聚类中心条件下，我们采用模糊C 均值方式对样本进行分类，
因为模糊C 均值属于一种软分类方式，因而得到的结果只能用隶属度来描述，对于模糊C 均值的相似度描述是依赖于样本与类均值间的二范数（欧式距离）。结果如表2所示，P1表示样本属于第一类的概率，P2表示样本属于第二类的概率。从这我们也可以很明显看出C 均值和模糊C 均值间的差别，C 均值是属于一种硬分类方式，所以分类结果只能用0或1来表示，然而，实际中存在着介于“是”与“不是”间的类别，采用硬分类方式就得不到合理的结果。
迭代次数比较，C 均值经过2次迭代结束，而模糊C 均值却需要5次迭代才能结束，这也许引起的一个主要原因是循环结束条件不一致。
表2、模糊C 均值的分类结果
2、c=2(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,-1)
在设定初始中心m1(0)=(0,0,0),m2(0)=(1,1,-1)情况下分得的结果如图2，绿色和红色分别是两种不同的种类。显而易见，实验二的结果和实验一的结果一致，这可能由于初始中心的选取不合理引起的结果。此外，最为主要的原因可能是，绿色“o ”和红色“*”两类之间的间隔确实较远，在分两类的情况下确实只会导致这样的结果。
10
X1
the second results of kmeans
X2
X 3
图2 分类结果
由表3可见，在硬分类的条件下，无法对红色“*”类别进行合理的描述，而模糊C 均值却能给出一个较为合理的分析。对于C 均值迭代结束是3，而模糊C 均值的迭代次数为7。由此可见，迭代次数不仅依赖于样本本身，还依赖于初
值的选取。
3、c=3(类别数)；初始聚类的均值：m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)
在设定初始中心m1(0)=(0,0,0),m2(0)=(1,1,1)，m3(0)=(-1,0,2)情况下分得的结果如图3，绿色“o ”、红色“*”和蓝色“x ”分别是三种不同的种类。如图3可见，在实验一和实验二中的某一类被分成两个子类，这主要是C 均值只利用到均值特征，而没有利用方差特征，对于上两个实验中某一类的类内方差较大，所以不能简单的把它当做一类对待，采用分三类的方式就能得到一个更好的实验结果。
10
X1
the third results of kmeans
X2
X 3
图3 分类结果
C 均值分类迭代次数为3，而模糊C 均值迭代次数为11，模糊C 均值所需的迭代次数较多。当然不仅影响这个结果主要原因依赖于程序本身的设计。而C 均值方法是引用MATLAB 自带的程序。
4、c=3(类别数)；初始聚类的均值（初始聚类中心）：m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，m3(0)=(-0.1,-0.1,0.1)
在设定初始中心m1(0)=(-0.1,0,0.1),m2(0)=(0,-0.1,0.1)，m3(0)=(-0.1,-0.1,0.1)情况下分得的结果如图4，绿色“o ”、红色“*”和蓝色“x ”分别是三种不同的种类。如图4可见，实验四的结果与实验三的结果不一致，从而说明初值的选择对实验结果有较大的影响。对于那种类似较难区分的数据，我们应该根据经验等合理方式来给定。
-10
10
X1
the fourth results of kmeans
X2
X 3
图4 分类结果
C 均值分类迭代次数为4，而模糊C 均值迭代次数为17。从以上结果，可以看出迭代次数依赖于程序本身、初始类别中心和样本数据。
四、程序
close all
clear all
clc
dataset=load('F:\experience1.mat');
center1=[1 1 1;-1 1 -1];
center2=[0 0 0;1 1 -1];
center3=[0 0 0;1 1 1;-1 0 2];
center4=[-0.1 0 0.1;0 -0.1 0.1;-0.1 -0.1 0.1];
%%%%%%%%kmeans
[k_class1,C1,sumd1,D1]=kmeans(dataset.data,2,'start',center1);
one1=dataset.data(find(k_class1==1),:);
second1=dataset.data(find(k_class1==2),:);
scatter3(one1(:,1),one1(:,2),one1(:,3),'*','r')
hold on
scatter3(second1(:,1),second1(:,2),second1(:,3),'o','g')
hold off
xlabel('X1','Fontsize',15);ylabel('X2','Fontsize',15);zlabel('X3' ,'Fontsize',15);title('the first results of kmeans','Fontsize',15) %%%%%%%%%%%%%
[k_class2,C2,sumd2,D2]=kmeans(dataset.data,2,'start',center2);
one2=dataset.data(find(k_class2==1),:);
second2=dataset.data(find(k_class2==2),:);
figure,scatter3(one2(:,1),one2(:,2),one2(:,3),'*','r')
hold on
scatter3(second2(:,1),second2(:,2),second2(:,3),'o','g')
hold off
xlabel('X1','Fontsize',15);ylabel('X2','Fontsize',15);zlabel('X3' ,'Fontsize',15);title('the second results of kmeans','Fontsize',15) %%%%%%%%%%%%%%%%%%%%
[k_class3,C3,sumd3,D3]=kmeans(dataset.data,3,'start',center3);
one3=dataset.data(find(k_class3==1),:);
second3=dataset.data(find(k_class3==2),:);
third3=dataset.data(find(k_class3==3),:);
figure,scatter3(one3(:,1),one3(:,2),one3(:,3),'*','r')
hold on
scatter3(second3(:,1),second3(:,2),second3(:,3),'o','g')
hold on
scatter3(third3(:,1),third3(:,2),third3(:,3),'x','b')
hold off
xlabel('X1','Fontsize',15);ylabel('X2','Fontsize',15);zlabel('X3' ,'Fontsize',15);title('the third results of kmeans','Fontsize',15) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
[k_class4,C4,sumd4,D4]=kmeans(dataset.data,3,'start',center4);
one4=dataset.data(find(k_class4==1),:);
second4=dataset.data(find(k_class4==2),:);
third4=dataset.data(find(k_class4==3),:);
figure,scatter3(one4(:,1),one4(:,2),one4(:,3),'*','r')
hold on
scatter3(second4(:,1),second4(:,2),second4(:,3),'o','g')
hold on
scatter3(third4(:,1),third4(:,2),third4(:,3),'x','b')
hold off
xlabel('X1','Fontsize',15);ylabel('X2','Fontsize',15);zlabel('X3' ,'Fontsize',15);title('the fourth results of kmeans','Fontsize',15) %%%fcm
[class_jwei1,fuzzy_jwei1]=fcm_jwei(dataset.sample,2,center1',2);
[class_jwei2,fuzzy_jwei2]=fcm_jwei(dataset.sample,2,center2',2);
[class_jwei3,fuzzy_jwei3]=fcm_jwei(dataset.sample,2,center3',3);
[class_jwei4,fuzzy_jwei4]=fcm_jwei(dataset.sample,2,center4',3);
子函数fcm_jwei部分
function
[class_center,fuzzy,time]=fcm_jwei(sample,b,initial_center,class_num) % close all
% clear all
% clc
% dataset=load('F:\?￡ê?ê?±e2010\experience1.mat');
% initial_center=[0 0 0;1 1 1;-1 0 2]';
% b=2;
% class_num=3;
% sample=dataset.sample;
%%%%%%%%%%%%
%sample is a two demention matrix,each row is a feature
[feature_num,sample_num]=size(sample);
fuzzy=zeros(class_num,sample_num);
class_center=initial_center;
class_cen=initial_center;
time=0;
while(1)
for i=1:sample_num
for j=1:class_num
fuzzy(j,i)=(sample(:,i)-class_center(:,j))'*...
(sample(:,i)-class_center(:,j))+eps;
fuzzy(j,i)=fuzzy(j,i).^(-(1/(b-1)));
end
end
normal_fuzzy=sum(fuzzy,1);
for j=1:class_num
fuzzy(j,:)=fuzzy(j,:)./normal_fuzzy;
end
for j=1:class_num
sum_fuzzy=sum((fuzzy(j,:).^b),2)+eps;
for k=1:feature_num
class_center(k,j)=((fuzzy(j,:).^b)*sample(k,:)')/(sum_fuzzy);
end
end
time=time+1;
if
sum(sum((class_center-class_cen).*(class_center-class_cen)))<0.001;
break;
end
class_cen=class_center;
end
关于模糊c均值聚类算法
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最小。算法采用误差平方和准则函数作为聚类准则函数。 关于其优点：
模糊C均值聚类 及距离函数的优缺点
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 算法是通过最小化目标函数来实现数据聚类的。
FCM聚类算法介绍
FCM 聚类算法介绍 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 ：
FCMClust(模糊c均值聚类算法MATLAB实现)
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 个分离开的子集 ，每个子集是一个类， 它们分别包 含 个 样本 。 为了衡量聚类的质量，采用误差平方和聚类准则函数 式中 为类中样本的均值： 是c 个子集合的中心，可以用来代表c 个类。 误差平方和 聚类准则函数是样本与集合中心的函数。在样本集X 给定的情况下， 其取值取决于c 个集合“中心”。 它描述n 个试验样本聚合成c 个类时，所产生的总误差平方和 越小越好。 误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布。 C-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标数最小化，从而使生成的簇尽可能地紧凑和独立。 首先，随机选取k 个对象作为初始的k 个簇的质心； 然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。 12{,,...,}n X x x x =X c X X X ,.....,,21c n n n ,......,,21c J ∑∑==-= c j n k j k c j m x J 11 2 ||||j m ∑==j n j j j j x n m 1 1 c j ,....,2,1=j m c J c J
模糊C均值聚类算法及实现
模糊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均值聚类算法的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的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均
模糊c均值聚类+FCM算法的MATLAB代码
模糊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 均值聚类算法 C 均值算法属于聚类技术中一种基本的划分方法,具有简单、快速的优点。其基本思想是选取c 个数据对象作为初始聚类中心,通过迭代把数据对象划分到不同的簇中,使簇内部对象之间的相似度很大,而簇之间对象的相似度很小。对C 均值算法的初始聚类中心选择方法进行了改进,提出了一种从数据对象分布出发动态寻找并确定初始聚类中心的思路以及基于这种思路的改进算法。 1、C-均值聚类算法 ① 给出n 个混合样本，令1=I ，表示迭代运算次数，选取c 个初始聚合中心)1(j Z ，c j ,...,2,1=； ② 计算每个样本与聚合中心的距离))(,(I Z x D j k ，n k ,....,2,1=，c j ,...,2,1=。 若},...,2,1)),(,({min ))(,(,...,2,1n k I Z x D I Z x D j k c j i k ===，则i k w x ∈。 ③ 计算c 个新的集合中心：∑== +j n k j k j j x n I Z 1 )(1)1(，c j ,...,2,1=。 ④ 判断：若)()1(I Z I Z j j ≠+，c j ,...,2,1=，则1+=I I ，返回②，否则算法结束。 2、C-均值改进算法的思想 在C-均值算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,此方法就是如何找到与数据在空间分布上尽可能相一致的初始聚类中心。对数据进行划分,最根本的目的是使得一个聚类中的对象是相似的,而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度,相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到C 个初始中心,它们分别代表了相似程度较大的数据集合,那么就找到了与数据在空间分布上相一致的初始聚类中心。 目前，初始聚类中心选取的方法有很多种，在此仅介绍两种： 1）基于最小距离的初始聚类中心选取法 其主要思想： (1) 计算数据对象两两之间的距离; (2) 找出距离最近的两个数据对象,形成一个数据对象集合A1 ,并将它们从总的数据集合U 中删除; (3) 计算A1 中每一个数据对象与数据对象集合U 中每一个样本的距离,找出在U 中与A1 中最近的数据对象,将它并入集合A1 并从U 中删除, 直到A1 中的数据对象个数到达一定阈值; (4) 再从U 中找到样本两两间距离最近的两个数据对象构成A2 ,重复上面的过程,直到形成k 个对象集合; (5) 最后对k 个对象集合分别进行算术平均,形成k 个初始聚类中心。 这种方法和Huffman 算法一样。后一种算法介绍是是基于最小二叉树的方法，看 模糊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均值聚类算法的实现2009 年12月14 日 模糊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均值聚类算法及实现 摘要：模糊聚类是一种重要数据分析和建模的无监督方法。本文对模糊聚类进行了概述，从理论和实验方面研究了模糊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均值聚类算法
模糊C均值聚类
模糊C均值聚类程序
模糊c均值聚类
模糊C均值聚类算法的实现
模糊C均值聚类算法及实现