嵌入式方向工程设计实验报告学院班级：130712学生学号：13071219学生姓名：杨阳同作者：无实验日期：2010年12月聚类算法分析研究1 实验环境以及所用到的主要软件Windows Vista NetBeans6.5.1 Weka3.6MATLAB R2009a2 实验内容描述聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。
其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。
本文中对近年来聚类算法的研究现状与新进展进行归纳总结。
一方面对近年来提出的较有代表性的聚类算法，从算法思想。
关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。
最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。
实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。
然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。
下面简单描述一下K 均值聚类的步骤。
K 均值算法首先随机的指定K 个类中心。
然后：（1）将每个实例分配到距它最近的类中心，得到K 个类；（2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。
重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。
在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。
然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。
3 实验过程3.1K 均值聚类算法3.1.1 K 均值聚类算法理论K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。
K 均值算法的划分理论基础是21min ick ik A i x v ∈=-∑∑ （1）其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即1,i N kk i k i ix v x A N ==∈∑（2）其中i N 表示在数据集i A 中的对象数。
3.1.2 算法的基本过程1:step 任意选择K 个对象作为初始的类的中心； 2:step repeat ；3:step 根据类中的平均值,将每个数据点 (重新)赋给最相近的类； 4:step 更新类的平均值；5:step until 不再发生变化,即没有对象进行被重新分配时过程结束。
3.1.3 算法代码分析K 均值聚类算法的代码分析过程如下首先调用clust_normalize （）函数将数据集标准化具体过程如下 data=clust_normalize(data,'range'); 下面是对K 均值算法的初始化 if max(size(param.c))==1, c = param.c;index=randperm(N);v=X(index(1:c),:);v = v + 1e-10;v0=X(index(1:c)+1,:);v0 = v0 - 1e-10; elsev = param.c; c = size(param.c,1); index=randperm(N);v0=X(index(1:c)+1,:);v0 = v0 + 1e-10; end iter = 0;接着是迭代求解直到满足要求的解或者达到最大的迭代值 while prod(max(abs(v - v0))), iter = iter +1; v0 = v;for i = 1:c这里是用来计算欧氏距离dist(:,i) = sum([(X - repmat(v(i,:),N,1)).^2],2); end下面将分类结果赋值[m,label] = min(dist');distout=sqrt(dist);下面计算分类中心for i = 1:cindex=find(label == i);if ~isempty(index)v(i,:) = mean(X(index,:));elseind=round(rand*N-1);v(i,:)=X(ind,:);endf0(index,i)=1;endJ(iter) = sum(sum(f0.*dist));if param.visclfhold onplot(v(:,1),v(:,2),'ro')colors={'r.' 'gx' 'b+' 'ys' 'md' 'cv' 'k.' 'r*' 'g*' 'b*' 'y*' 'm*' 'c*' 'k*' };for i=1:cindex = find(label == i);if ~isempty(index)dat=X(index,:);plot(dat(:,1),dat(:,2),colors{i})endendhold offpause(0.1)endend保存求解结果result.cluster.v = v;result.data.d = distout;计算划分矩阵f0=zeros(N,c);for i=1:cindex=find(label == i);f0(index,i)=1;endresult.data.f=f0;result.iter = iter;result.cost = J;3.1.4实验配置实验过程配置比较简单只需按照如下介绍即可。
将路径修改为MATLAB工具箱的相应路径在次是“E:\MATLAB\toolbox\FUZZCLUST”如下path(path,'E:\MATLAB\toolbox\FUZZCLUST')选择数据集在实验中选择了IRIS数据集，因此IRIS=1。
在下面选择哪个数据集只需将相应的值置为1其他两个置为0。
wine=0;iris=1;wisc=0;if wineload winedat.txtdata=winedat(:,1:end-1);C=winedat(:,end);endif irisload irisdata=iris(:,1:4);C=zeros(length(data),1);for i=1:3C(find(iris(:,4+i)==1))=i;endendif wiscwisc数据预处理wisc=wk1read('wisconsin.wk1');NI=9;NT=length(wisc);data.X=[wisc(:,11) wisc(:,2:10)];data.X=sortrows(data.X,1);[I,J]=find(data.X(:,7)~=0);data.X=data.X(I,:);[I,J]=find(data.X(:,1)==2);data.X(I,1)=1;[I,J]=find(data.X(:,1)==4);data.X(I,1)=2;C=data.X(:,1);data=data.X(:,2:end);end数据标准化data.X=data;data=clust_normalize(data,'range');下面的参数在FCM模糊聚类时用到param.m=2;如下参数是设置分类数即K=3param.c=3;param.val=1;param.vis=0;result=Kmeans(data,param);result=validity(result,data,param);[d1,d2]=max(result.data.f');Cc=[];for i=1:param.cCi=C(find(d2==i));dum1=hist(Ci,1:param.c);[dd1,dd2]=max(dum1);Cc(i)=dd2;end3.1.5实验效果实验中使用了UCI的IRIS数据集和WINE数据集，实验的结果如下图1)IRIS数据集实验结果MATLAB实验输出的图形如下图１ PCA图图２ Conventional Sammon mapping 图图３ Fuzzy Sammon mapping 图并且可在实验中得到MATLAB的算法评价指标如下2)WINE数据集实验结果MATLAB实验输出的图形如下图 4 PCA图图 5 Conventional Sammon mapping 图图 6 Fuzzy Sammon mapping 图并且可在实验中得到MATLAB 的算法评价指标如下将该算法在两种不同数据集中的测试结果对比如下3.1.6 K 均值聚类算法的相关特点该算法试图找出使平方误差值最小的K 个划分。
当结果类是密集的，而类与类之间区分明显时，它的效果较好。
算法复杂度()o nkt ，其中t 是迭代次数。
因此其可扩展性较好，对大数据集处理有较高的效率。
算法常以局部最优结束。
全局最优要穷举所有可能的划分。
缺点：不适合发现非凸面状的类。
不适合大小差别较大的类。
对于噪声和孤立点是敏感的，由于少量的该类数据对平均值产生较大的影响。
3.2 FCM 模糊聚类算法FCM 算法也是一种基于划分的聚类算法，它的思想就是使得被划分到同一类的对象之间相似度最大，而不同类之间的相似度最小。
模糊C 均值算法是普通C 均值算法的改进，普通C 均值算法对于数据的划分是硬性的，而FCM 则是一种柔性的模糊划分。
在介绍FCM 具体算法之前我们先介绍一些模糊集合的基本知识。
3.2.1 FCM 模糊聚类算法的理论 1) 理论基础-模糊集基本知识首先说明隶属度函数的概念。
隶属度函数是表示一个对象x 隶属于集合A 的程度的函数，通常记做()A x μ，其自变量范围是所有可能属于集合A 的对象（即集合A 所在空间中的所有点），取值范围是[]0,1，即()01A x μ≤≤。