聚类算法分析

撰写人：_日 期：_课程名称： 数据挖掘 实验项目： 聚类算法分析研究 班 级： 学 号： 学生姓名： 精品范文模板 可修改删除聚类算法分析研究1 实验环境以及所用到的主要软件Windows Vista 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.1 K均值聚类算法3.1.1 K均值聚类算法理论K均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K均值算法的划分理论基础是（1）其中是划分的聚类数，是已经属于第类的数据集是相应的点到第类的平均距离，即（2）其中表示在数据集中的对象数。3.1.2 算法的基本过程任意选择K个对象作为初始的类的中心；根据类中的平均值,将每个数据点 (重新)赋给最相近的类；更新类的平均值；不再发生变化,即没有对象进行被重新分配时过程结束。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;else v = 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:c index=find(label = i); if isempty(index) v(i,:) = mean(X(index,:); else ind=round(rand*N-1); v(i,:)=X(ind,:); end f0(index,i)=1; end J(iter) = sum(sum(f0.*dist); if param.vis clf hold on plot(v(:,1),v(:,2),ro) colors=r. gx b+ ys md cv k. r* g* b* y* m* c* k* ; for i=1:c index = find(label = i); if isempty(index) dat=X(index,:); plot(dat(:,1),dat(:,2),colorsi) end end hold off pause(0.1) end end保存求解结果result.cluster.v = v;result.data.d = distout;计算划分矩阵 f0=zeros(N,c);for i=1:c index=find(label = i); f0(index,i)=1;end result.data.f=f0;result.iter = iter;result.cost = J;3.1.4 实验配置实验过程配置比较简单只需按照如下介绍即可。将路径修改为MATLAB工具箱的相应路径在次是“E:MATLABtoolboxFUZZCLUST”如下path(path,E:MATLABtoolboxFUZZCLUST)选择数据集在实验中选择了IRIS数据集，因此IRIS=1。在下面选择哪个数据集只需将相应的值置为1其他两个置为0。wine=0;iris=1;wisc=0;if wine load winedat.txt data=winedat(:,1:end-1); C=winedat(:,end);endif iris load iris data=iris(:,1:4); C=zeros(length(data),1); for i=1:3 C(find(iris(:,4+i)=1)=i; end endif wisc wisc数据预处理 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.c Ci=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的算法评价指标如下表格 1 IRIS数据集算法评价指标PC1CENaN2) WINE数据集实验结果MATLAB实验输出的图形如下图 4 PCA图图 5 Conventional Sammon mapping 图图 6 Fuzzy Sammon mapping 图并且可在实验中得到MATLAB的算法评价指标如下表格 2 WINE数据集算法评价指标PC1CENaN将该算法在两种不同数据集中的测试结果对比如下表格 3 不同数据集的算法指标对比KmeansPCCEIRIS1NaNWINE1NaN3.1.6 K均值聚类算法的相关特点该算法试图找出使平方误差值最小的K个划分。当结果类是密集的，而类与类之间区分明显时，它的效果较好。算法复杂度，其中是迭代次数。因此其可扩展性较好，对大数据集处理有较高的效率。算法常以局部最优结束。全局最优要穷举所有可能的划分。缺点：不适合发现非凸面状的类。不适合大小差别较大的类。对于噪声和孤立点是敏感的，由于少量的该类数据对平均值产生较大的影响。3.2 FCM模糊聚类算法FCM算法也是一种基于划分的聚类算法，它的思想就是使得被划分到同一类的对象之间相似度最大，而不同类之间的相似度最小。模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。在介绍FCM具体算法之前我们先介绍一些模糊集合的基本知识。3.2.1 FCM模糊聚类算法的理论1) 理论基础-模糊集基本知识首先说明隶属度函数的概念。隶属度函数是表示一个对象隶属于集合的程度的函数，通常记做，其自变量范围是所有可能属于集合的对象（即集合所在空间中的所有点），取值范围是，即。表示完全隶属于集合，相当于传统集合概念上的。一个定义在空间上的隶属度函数就定义了一个模糊集合，或者叫定义在论域上的模糊子集。在聚类的问题中，可以把聚类生成的类看成模糊集合，因此每个样本点隶属于每个类的隶属度就是区间里面的值。2) FCM的算法理论1973年，Bezdek提出了该算法，并作为早期硬C均值聚类（HCM）方法的一种改进，命名为模糊C均值聚类简称FCM是一种目标函数法。假设将样本空间要分为个类，则类中心集使下式的目标函数值最小（3）（4）且有其中被称为模糊隶属度矩阵。表示的是数据隶属于类中心的隶属度。是模糊加权参数，用于控制在模糊类间的程度依据参考的文献中一般取值为15。应用拉格朗日乘法并基于上述约束可得到如下式 （5）且 （6）其中是到第类中心的欧氏距离，即。3.2.2 FCM模糊聚类算法的过程置初始化参数值，包含模糊加权参数值和聚类数，以及迭代的次数和算法终止误差。随机化置初始化聚类的中心。计算隶属度矩阵可通过（5）式计算得来。依据（6）式迭代计算聚类的中心。检验是否成立，成立则算法结束否则。3.2.3 算法代码分析FCM聚类算法的代码分析过程如下参数检查并初始化默认参数if exist(param.m)=1, m = param.m;else m = 2;end;if exist(param.e)=1, e = param.m;else e = 1e-4;end;N,n = size(X);Nf0,nf0 = size(f0); X1 = ones(N,1);初始化模糊划分矩阵rand(state,0)if max(Nf0,nf0) = 1, % only number of cluster given c = f0; mm = mean(X); %mean of the data (1,n) aa = max(abs(X - ones(N,1)*mm); % v = 2*(ones(c,1)*aa).*(rand(c,n)-0.5) + ones(c,1)*mm; for j = 1 : c, xv = X - X1*v(j,:); d(:,j) = sum(xv*eye(n).*xv),2); end; d = (d+1e-10).(-1/(m-1); f0 = (d ./ (sum(d,2)*ones(1,c); else c = size(f0,2); fm = f0.m; sumf = sum(fm); v = (fm*X)./(sumf*ones(1,n); %end;f = zeros(N,c); iter = 0; 该参数用来迭代计数迭代求解直到满足实验要求的精度while max(max(f0-f) e iter = iter + 1; f = f0; 下面计算分类中心 fm = f.m; sumf = sum(fm); v = (fm*X)./(sumf*ones(1,n); for j = 1 : c, xv = X - X1*v(j,:); d(:,j) = sum(xv*eye(n).*xv),2); end; distout=sqrt(d); J(iter) = sum(sum(f0.*d); d = (d+1e-10).(-1/(m-1); f0 = (d ./ (sum(d,2)*ones(1,c);endfm = f.m; sumf = sum(fm);求解结果保存result.data.f=f0;result.data.d=distout;result.cluster.v=v;result.iter = iter;result.cost = J;3.2.4 实验配置实验配置过程与K均值算法的实验配置过程基本相同，只是在FCM模糊聚类算法实验中要用到模糊隶属度参数，一般将其设置在15之间在实验中设置如下param.m=2。也可以根据需要对其进行修改。3.2.5 实验效果实验中使用了UCI的IRIS数据集和WINE数据集，实验的结果如下图1) IRIS数据集实验结果MATLAB实验输出的图形如下图 7 PCA图图 8 Conventional Sammon mapping 图图 9 Fuzzy Sammon mapping 图并且可在实验中得到MATLAB的算法评价指标如下表格 4 IRIS数据集算法评价指标PC0.7420CE0.46822) WINE数据集实验结果MATLAB实验输出的图形如下图 0 PCA图图 11 Conventional Sammon mapping 图图 12 Fuzzy Sammon mapping 图并且可在实验中得到MATLAB的算法评价指标如下表格 5 WINE数据集算法评价指标PC0.5033CE0.8546将该算法在两种不同数据集中的测试结果对比如下表格 6 不同数据集的算法指标对比FCMPCCEIRIS0.74200.4682WINE0.50330.85463.2.6 FCM模糊聚类算法特点FCM算法需要两个参数一个是聚类数目，另一个是参数。一般来讲要远远小于聚类样本的总个数，同时要保证。对于，它是一个控制算法的柔性的参数，如果过大，则聚类效果会很次，而如果过小则算法会接近K均值聚类算法。算法的输出是个聚类中心点向量和的一个模糊划分矩阵，这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征，可以认为是这个类的中心代表。FCM算法是图像分割使用最多的方法之一，它的成功主要归功于为解决每个图像像素的隶属需要引入了模糊性。与K均值聚类相比较来说FCM能够保留初始图像的更多信息。FCM对孤立点和其他人造图像非常敏感。3.3 算法评价在算法的评价指标中选择指标PC和CE作为以上算法的评价指标。PC-Partition Coefficient 用来测量在类之间的重复数量，其由Beadek定义如下其中的是数据点在类中的隶属度系数。CE-Classification Entropy 用来测量划分类的模糊度，与PC有一定的相似性。其定义如下对于文中涉及到的K均值聚类算法和FCM模糊聚类算法在同一数据集中的实验对比如下对于数据集IRIS的对比如下表表格7 IRIS数据集下的评价指标对比IRISPCCEKmeans1NaNFCM0.74200.4682对于数据集WINE的对比如下表表格7 WINE数据集下的评价指标对比WINEPCCEKmeans1NaNFCM0.50330.8546有时也用所谓的文档关联来评测聚类方法。文档关联是指属于同一个类别的任意两个文档之间所形成的“文档对”关系。基于文档关联的聚类评测方法，其考察的基本对象就是“文档对”。这里的文档其实就是分类的数据对。3.4 基于weka的聚类分析3.4.1 数据的预处理从网站下载的WINE原始数据集wine.data文件，而Weka软件需要的是ARFF文件格式的数据。因此需要将数据转换成Weka支持的ARFF文件格式的。转换过程如下首先用记事本方式打开文件发现文件中的数据之间是以逗号来划分的，因此可以将数据文件的名称改为wine.csv。然后，打开Weka选择Tools选项下的ArffViewer如下图打开ArffViewer后选择File选项下的Open弹出如下图的打开窗口，在文件类型一栏选择CSV data files（*.csv）项。然后找到相应的文件后单击打开后如下图接下来选择File选项下的Save as 后弹出如下图在文件名栏输入相应的文件名后单击保存即可得到相应的arff格式的数据集文件。K均值算法只能处理数值型的属性，遇到分类型的属性时要把它变为若干个取值0和1的属性。WEKA将自动实施这个分类型到数值型的变换，而且WEKA会自动对数值型的数据作标准化。WEKA中的StringToWordVector过滤器能将ARFF文件中的文本数据转换为空间向量模型,它同时拥有分词、特征表示、特征 提取等功能。在Explorer中的Reprocess界面导入ARFF文件,选择StringToWordVector过滤器,再设置相关参数。3.4.2 聚类过程进入Explorer中的Preprocess 界面单击Open file后弹出如下图的数据集选择窗口，选择WINE.arff数据集文件后打开。然后可以在Filter下的choose中选择需要的过滤器参数。接下来选择Cluster选项界面，在Clusterer中选择choose来选择Weka中提供的聚类算法 Clusters下的SimpleKMeans,然后设置参数如下图即为修改“numClusters”为3就是我们要将数据聚类为3类即K=3，下面的“seed”参数是要设置一个随机种子，依此产生一个随机数，用来得到K均值算法中第一次给出的K个簇中心的位置，这里暂时让它就为10，设置完成后单击OK返回。然后选中“Cluster Mode”的“Use training set”，点击“Start”按钮，观察右边“Clusterer output”给出的聚类结果如下= Run information =Scheme: Weka.clusterers.SimpleKMeans -N 3 -A Weka.core.EuclideanDistance -R first-last -I 500 -S 10Relation: WINEDATInstances: 177Attributes: 14 1.42E+01 1.71E+00 2.43E+00 1.56E+01 1.27E+02 2.80E+00 3.06E+00 2.80E-01 2.29E+00 5.64E+00 1.04E+00 3.92E+00 1.07E+03 1Test mode: evaluate on training data= Model and evaluation on training set =kMeans=Number of iterations: 7Missing values globally replaced with mean/modeCluster centroids: Cluster#Attribute Full Data 0 1 2 (177) (59) (49) (69)=1.42E+01 13.0006 13.7305 13.1612 12.26231.71E+00 2.3399 2.01 3.3445 1.90862.43E+00 2.3662 2.4585 2.4347 2.23861.56E+01 19.5169 17.2814 21.4388 20.06381.27E+02 99.5876 106.5424 99.0204 94.04352.80E+00 2.2923 2.8486 1.6782 2.25263.06E+00 2.0234 2.9795 0.798 2.07622.80E-01 0.3623 0.2888 0.4508 0.36232.29E+00 1.5869 1.8937 1.1631 1.62575.64E+00 5.0553 5.4895 7.3451 3.0581.04E+00 0.957 1.0666 0.6859 1.05573.92E+00 2.6043 3.1507 1.6902 2.78621.07E+03 745.678 1116.1017 627.551 512.82611 1.9435 1.0169 2.9796 2Clustered Instances0 59 ( 33%)1 49 ( 28%)2 69 ( 39%)也可以在左下角“Result list”中这次产生的结果上点右键，“View in separate window”在新窗口中浏览结果。3.4.3 结果分析首先我们注意到结果中有这么一行： 这是评价聚类好坏的标准，数值越小说明同一类实例之间的距离越小。也许你得到的数值会不一样；实际上如果把seed参数改一下，得到的这个数值就可能会不一样。我们应该多尝试几个seed，并采纳这个数值最小的那个结果。接下来Cluster centroids:之后列出了各个类中心的位置。对于数值型的属性，类中心就是它的均值（Mean）；分类型的就是它的众数（Mode）， 也就是说这个属性上取值为众数值的实例最多。对于数值型的属性，还给出了它在各个类里的标准差（Std Devs）。最后的Clustered Instances是各个类中实例的数目及百分比如下Clustered Instances0 59 ( 33%)1 49 ( 28%)2 69 ( 39%)实际的聚类各类中的实例分配如下Number of Instances class 1 59class 2 71class 3 48通过对比可以得出聚类的结果还是比较满意的。为了观察可视化的聚类结果，我们在左下方Result list列出的结果上右击，点Visualize cluster assignments。弹出的窗口给出了各实例的散点图。最上方的两个框是选择横坐标和纵坐标，第二行的color是散点图着色的依据，默认是根 据不同的类Cluster给实例标上不同的颜色，如下图从图中很容易看出聚类的结果由不同颜色区分。可以在这里点Save把聚类结果保存成ARFF文件。在这个新的ARFF文件中，instance_number属性表示某实例的编号，Cluster属性表示聚类算法给出的该实例所在的类。3.4.4 实验扩展聚类算法在数据挖掘里面被称之为无监督学习（unsupervised learning），这是与分类算法（supervised learning）相对的。所谓无监督学习就是在预先不知道样本类别的情况下，由聚类算法来判别样本的类别的一种学习方法。但是在Weka中还有一个问题就是所提供的聚类算法有限难以满足具体需要，基于此问题在阅读了相关文献后发现可以通过扩展Weka的聚类算法来满足具体的实验需要。通过分析实验的相关代码可以得到Weka中聚类的一般过程主要如下1. 读入需预测样本2. 初始化聚类算法（并设置参数）3. 使用聚类算法对样本进行聚类4. 打印聚类结果大概过程可实现如下 Instances ins = null; Instances tempIns = null; SimpleKMeans KM = null; DistanceFunction disFun = null; try File file= new File(data.arff); ArffLoader loader = new ArffLoader(); loader.setFile(file); ins = loader.getDataSet(); KM = new SimpleKMeans(); KM.setNumClusters(2); KM.buildClusterer(ins); tempIns = KM.getClusterCentroids(); System.out.println(CentroIds: + tempIns); catch(Exception e) e.printStackTrace(); 首先读入样本过程比较简单可以调用ArffLoader()函数和setFile()函数以及getDataSet()函数等在构建聚类器时也是通过现有的类来实现的。SimpleKMean是最简单的KMeans算法，因为聚类算法的核心是通过距离来得到类别（类间相异，类内相似），所以需要有一个计算距离的公式常见的就是欧几里得距离了。将SimpleKMean计算距离的方法默认为欧几里得距离。Weka中提供了设置距离函数的接口setDistanceFunction(DistanceFunction df)，可以方便我们设置自己的距离计算方法。在聚类过程中将样本的类别属性放在里面是不符合常识的，因为样本类别属性包含了大量的类别信息，可能诱导聚类算法得到很好的效果。但是这与我们的初衷是相背离的，所以在聚类之前我们要记住删除掉类别属性。在第四步打印聚类结果是一个很简单的信息，里面包括了聚类的几个中心点。在写程序时可以使用ClusterEvaluation类来打印更多的信息。3.4.5 扩展Weka算法在扩展之前Weka中的聚类算法如下图显然没有实验所需的FCM模糊聚类算法，因此需要通过扩展加入FCM聚类算法。了解Weka聚类器的相关接口，是在Weka中实现扩展聚类方法的基础。Weakclusterers包里边放的就是各种聚类算法以及聚类器接口和评估器接口，其中有K-means、EM、Cobweb、DBScan等算法，分析Weka的源代码中可以得到，core包是Weka的核心，gui包是处理图形界面等。最重要的是Weka.core包。该包中又有3个类是重中之重，实现首先就从这里入手。这3个类是Instances(实例集)类，Attribute(属性)类和Instance(实例)类，Weka里边的每个算法都会用到这3个类。聚类器类结构是实现聚类算法的另一个关键。在了解Weka聚类器的接口之后，就可以在Weka中设计与实现新的聚类分析方法。要把新编写的聚类算法容入Weka中，需要相应的Waka中的包和Java的包。下面介绍在Weka中扩展加入FCM模糊聚类算法的具体实现1 下载Weka的源代码解压后如下图2 编写新算法，所编写的新算法必须符合Weka 的接口标准。此处所需的FCM算法可从Weka中文站上下载FuzzyCMeans算法。3 直接将FuzzyCMeans.java 源程序考到weka.clusterers 包下。4 再修改，在#Lists the Clusterers I want to choose from的weka.clusterers.Clusterer=下加入：。5 在NetBeans中新建工程选择基于现有源代码的Java项目单击下一步后如下图填入相应的项目名称并单击浏览找到项目文件夹然后单击下一步单击添加文件夹选择源代码文件夹如图然后单击下一步可以看到导入的Java源代码文件如下图单击完成后可以看到如下图从中可以看到工程中有错误，因此需要将错误修改后才能编译工程。找到错误的位置如下图通过分析后修改过程大概如下加入所需的未导入的Java包import weka.classifiers.rules.DecisionTableHashKey;import weka.core.Attribute;import weka.core.DistanceFunction;import weka.core.EuclideanDistance;import weka.core.ManhattanDistance;import weka.core.RevisionUtils;实现接口中的抽象方法 public String getRevision() return RevisionUtils.extract($Revision: 1.40 $); 同时将上述错误中的错误类型代码修改掉即可。到此错误代码已经基本修改完成保存后如下图可以看到工程中已经没有错误了。现在编译工程后运行就可以在Weka的Explorer界面上的Cluster选项卡中的聚类算法中找到新添加的FuzzyCMeans聚类算法，到此FCM算法已经成功地添加到Weka软件中，接着将工程打包成jar包就可以在以后的实验中使用了。添加过程中最关键的问题是要弄清楚Weka的内核以及其接口标准，然后编写出符合此规范的新算法。下面在实验中使用FCM模糊聚类算法来实现对WINE数据集的聚类。首先选择Applications下的Explorer如下图然后在Preprocess中在Open file中选择WINE.arff文件打开后在Cluster选项的choose中选择FuzzyCMeans如下图然后设置参数如下图然后单击OK后返回，然后选中“Cluster Mode”的“Use training set”，点击“Start”按钮，观察右边“Clusterer output”给出的聚类结果如下实验结果中的Clustered Instances如下Clustered Instances0 49 ( 28%)1 72 ( 41%)2 56 ( 32%)与前面给出的实际数据相比较吻合实验结果比较满意。第 36 页 共 36 页免责声明：图文来源于网络搜集，版权归原作者所以若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。