C均值聚类实验报告.doc

模式识别 作业 题目： C均值聚类算法实现 学 院： 电气信息工程学院 专 业： 电子工程系 班 级： 电子 10-1班 姓 名： 赵南兵 学 号： 11号 指导教师： 钱 云 C均值聚类实验报告 一、考试题目 基于聚类方法分类器设计 二、考试要求 1.掌握C均值基本原理。 2.掌握流程图的画法。 3.熟悉归一化的算法。 4.掌握聚类方法分类器设计方法。 三、考试分析 1、C均值聚类的算法原理 c均值聚类算法的步骤还是比较简单的，c均值聚类，即众所周知的模糊ISODATA，是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。1973年，Bezdek提出了该算法，作为早期硬c均值聚类（HCM）方法的一种改进。 FCM把n个向量xi（i=1,2,…,n）分为c个模糊组，并求每组的聚类中心，使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分，使得每个给定数据点用值在0，1间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应，隶属矩阵U允许有取值在0，1间的元素。不过，加上归一化规定，一个数据集的隶属度的和总等于1： 那么，价值函数（或目标函数）就是： ， 这里uij介于0，1间；ci为模糊组I的聚类中心，dij=||ci-xj||为第I个聚类中心与第j个数据点间的欧几里德距离；且是一个加权指数。 构造如下新的目标函数，可求得使（3.2）式达到最小值的必要条件： 这里(j，j=1到n，是（3.1）式的n个约束式的拉格朗日乘子。对所有输入参量求导，使式（3.2）达到最小的必要条件为： 和 上述算法也可以先初始化聚类中心，然后再执行迭代过程。由于不能确保FCM收敛于一个最优解。算法的性能依赖于初始聚类中心。因此，我们要么用另外的快速算法确定初始聚类中心，要么每次用不同的初始聚类中心启动该算法，多次运行FCM。 设被分类的对象的集合为：X = { x1 ， x2 ，…，xN}，其中每一个对象xk有n 个特性指标，设为xk = ( x1k ，x2k ， …， xnk) T , 如果要把X 分成c 类，则它的每一个分类结果都对应一个c×N 阶的Boolean矩阵U= [ uik ] c×N，对应的模糊c划分空间为： 2、C均值聚类的实现步骤 C－均值算法步骤： ① 给出n个混合样本，令 ，表示迭代运算次数，选取c个初始聚合中心 ② 计算每个样本与聚合中心的距离: 若 则 ③令 计算新的集合中心： 计算误差平方和 值： ④ 对每个聚合中的每个样本，计算： 表示 减少的部分 。 表示 增加的部分： 若 ，则把样本 移到聚合中心 中，并修改聚合中心和 值。 ⑤ 判断：若 则 ，返回④。否则，算法结束。 3、C均值聚类实验流程图 四．ATLAB程序及其注解 归一化程序 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 C均值聚类程序 a=fopen(data.txt);%打开文件 b=fscanf(a,%f %f %f %f,[4,150]);%按格式读入文件 b=b;%转置 aa=zeros(1,4);%用于计算內积的数据暂存矩阵 bb=zeros(1,4); key=1;%循环条件判断值 Jet=0;%临时误差 ex=0;%交换变量 lac=0;%位置记录值 tem=0;%临时比较变量 max=0;%最大误