C-均值聚类实验报告.doc

C-均值聚类实验报告.doc模式识别
作业 题目： C均值聚类算法实现
学 院： 电气信息工程学院
专 业： 电子工程系
班 级： 电子10-1班
姓 名： 赵南兵
学 号： 11号
指导教师： 钱 云
C均值聚类实验报告
一、 考试题目
基于聚类方法分类器设计
二、 考试要求
掌握c均值基本原理。
掌握流程图的画法。
熟悉归一化的算法。
掌握聚类方法分类器设计方法。
三、 考试分析
1、C均值聚类的算法原理
c均值聚类算法的步骤还是比较简单的，c均值聚类，即众所周知的模糊 ISODATA,是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。 1973年，Bezdek提出了该算法，作为早期硬c均值聚类（HCM）方法的一种改 进。
FCM把n个向量$ （i=l,2,...,n）分为c个模糊组，并求每组的聚类中心，使 得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模 糊划分，使得每个给定数据点用值在0,1间的隶属度来确定其属于各个组的程度。 与引入模糊划分相适应，隶属矩阵U允许有取值在0, 1间的元素。不过，加上 归一化规定，一个数据集的隶属度的和总等于1：
C
工"（7 = h *j = 1,…，M
i=l
那么，价值函数（或目标函数）就是：
w,C],・・・,c»£a=£匕陆
Z=1 1=1 j
这里Uij介于0, 1间；Ci为模糊组I的聚类中心,dij=IICi-Xjll为第I个聚类中心 与第j个数据点间的欧几里德距离；且加是一个加权指数。
构造如下新的目标函数，可求得使（）式达到最小值的必要条件：
_ C
J （U, C]，…,c<.,入，…,2”） = J（U,q,...,c<.） + 久 j u. q — 1）
这里九j, j=l到n,是（）式的n个约束式的拉格朗日乘子。对所有输入参 量求导，使式（）达到最小的必要条件为：
上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保 FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另 外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法， 多次运行FCMo
设被分类的对象的集合为：X = { Xi , X2 ,…，XN},其中每一个对象Xk有 n个特性指标，设为Xk = （ Xik , X2k，…，Xnk）T,如果要把X分成C类，则 它的每一个分类结果都对应一个cXN阶的Boolean矩阵U= [ uik ] cXN-对应的模 糊c划分空间为：
2、C均值聚类的实现步骤
C—均值算法步骤：
给出n个混合样本，令/=1 ,表示迭代运算次数，选取c个初始聚合中心
计算每个样本与聚合中心的距离:
（/））,* =1,2,...,”;/ = 1,2,...,
若 D(xk,Z,.(/)) = min {D(xk,Zy(/)),Z: = 1,2,.,
i nj
Zj⑵二一nj a
则 xk e a)：;
令/ = z+i = 2,计算新的集合中心:
计算误斧平方和厶值： “
c nj
厶(2)二》》忧)-Z,⑵『
7=1日
对每个聚合中的每个样本，计算：
必二^|£)—z,(/)心 1,2,...C 叫-1
Pi表示Jc减少的部分。
fl
/V —毗)- Zj (/) IF J 二 1,2, ...c J 幻 “•+1
几表示Jc增加的部分：p,7 =min{p..}
若Pn < Pn，则把样本移到聚合中心①中，并修改聚合中心和人值。
Zz(/ + l) = Zz(/) + ^--[Zz(/)-4)]
ni -1
乙(/ + 1) = Z,⑴+丄[乙⑴-牡)]
® +1
Jc (/ + 1)=丿C (/) 一 S - Pi)
判断：若 人(/+1)<人(/), 则1 = 1+1 ,返回④。否则，算法结束。
3、C均值聚类实验流程图


function a = Data_Normalized(a) amax二max (max (a)) ; %求矩阵中最大数 amin = min (min (a)) ; %求矩阵中最小数 [m, n]= size (a);
for i = 1: m
for j = 1: n
a(i, j)= (a(i, j)-amin)/(amax-amin);
end
end
2. C均值聚类程序
a=fopen(，data, txt') ;%打开文件
b二fscanf (a, '%f %f %f %f', [4, 150]) ；%按格式读入文件 b=b，;%转置