在数据挖掘中聚类和分类的原理被广泛的应用.
聚类即无监督的学习.
分类即有监督的学习.
通俗一点的讲就是:聚类之前是未知样本的分类.而是根据样本本身的相似性进行划分为相似的类簇.而分类
是已知样本分类,则需要将样本特征和分类特征进行匹配,进而将每个样本归入给出的特定的类.
由于本文是对聚类算法中的k-means算法的实现,所以接下来主要进行一些聚类算法的介绍.
聚类算法包括多种,可按如下分配:
1.划分法:基于此种思想的聚类算法包括 k-means,PAM,CLARA,CLARANS,STIRR.
2.层次法:基于此种思想的聚类算法包括BIRCH,CURE,Rock,Chamlean
3.密度法:基于此种思想的聚类算法包括DBSCAN,OPTICS,DENCluE,FDBSCAN,InCremental DBSCAN
4.网格法:基于此种思想的聚类算法包括STING,WaveCluster,OptiGrid
5.模型法:基于此种思想的聚类算法包括AutoClass,COBWEB,CLASSIT
6.神经网络:基于思想网络的聚类算法有两种:其一 自组织特征映射 其二 竞争学习
而k-means是基于划分思想.所以在这里介绍一下划分聚类思想:
1.对一组样本数据首先随机确定K个聚类中心
2.后来通过反复的迭代改变聚类中心,使得不断优化.而不断优化的意思是:同一类样本距离聚类中心越来越近,
而不同类样本之间距离越来越远.而最终收敛于聚类中心的位置不再移动.
既然k-means是基于这样的划分思想,那么当然k-means的算法思想精髓和划分思想是一致的.
k-means算法如下:
1.设样本为X{x(1),x(2)........}
2.首先在样本中随机选取k个聚类中心.
3.然后对除开聚类中心外的样本点计算到每个聚类中心的距离.将样本归类到距离样本中心最近的样本点.这便实
现了最初的聚类
4.再对每个类重新计算其聚类中心.然后重新对除开聚类中心的样本点计算到三个聚类中心的距离.将样本归类到距
离样本中心最近的样本点,这便实现了第一次优化聚类.
5.重复步骤四,直到两次聚类中心的位置不再变化,这便完成了最终的聚类
K-means matlab实现如下:(k=3)
1 clc; 2 clear; 3 4 ClomStatic=[1,2,3,25,26,27,53,54,55]; 5 len=length(ClomStatic);%求向量ClomStatic的长度 6 7 k=3; %给定的类别数目 8 9 %产生三个随机整数,随机聚类中心 10 p=randperm(len); 11 Temp=p(1:k); 12 Center=zeros(1,k); 13 for i=1:k 14 Center(i)=ClomStatic(Temp(i)); 15 end 16 17 18 19 %计算除聚类中心外的样本数据到聚类中心的距离,然后进行聚类 20 TempDistance=zeros(len,3); 21 while 1 22 23 Circulm=1; 24 25 p1=1; 26 p2=1; 27 p3=1; 28 29 JudgeEqual=zeros(1,k); 30 if(Circulm~=1) 31 clear Group1 Group2 Group3; 32 end 33 for i=1:len 34 for j=1:3 35 TempDistance(i,j)=abs(ClomStatic(i)-Center(j)); 36 end 37 [RowMin RowIndex]=min(TempDistance(i,:)); 38 if(RowIndex==1) 39 Group1(p1)=ClomStatic(i); 40 p1=p1+1; 41 elseif(RowIndex==2) 42 Group2(p2)=ClomStatic(i); 43 p2=p2+1; 44 elseif(RowIndex==3) 45 Group3(p3)=ClomStatic(i); 46 p3=p3+1; 47 end 48 end 49 50 len1=length(Group1); 51 len2=length(Group2); 52 len3=length(Group3); 53 54 55 %计算Group1,Group2,Group3的均值 56 MeanGroup1=mean(Group1); 57 MeanGroup2=mean(Group2); 58 MeanGroup3=mean(Group3); 59 60 61 %分别计算每个类中距离均值最近的一个点作为新的聚类中心 62 AbsGroup1=zeros(1,len1); 63 for t=1:len1 64 AbsGroup1(t)=floor(abs(Group1(t)-MeanGroup1)); 65 end 66 [MaxAbsGroup1 MaxAbsGroup1Index]=min(AbsGroup1); 67 NewCenter(1)=Group1(MaxAbsGroup1Index); 68 clear AbsGroup1; 69 70 AbsGroup2=zeros(1,len2); 71 for t=1:len2 72 AbsGroup2(t)=floor(abs(Group2(t)-MeanGroup2)); 73 end 74 [MaxAbsGroup2 MaxAbsGroup2Index]=min(AbsGroup2); 75 NewCenter(2)=Group2(MaxAbsGroup2Index); 76 clear AbsGroup2; 77 78 AbsGroup3=zeros(1,len3); 79 for t=1:len3 80 AbsGroup3(t)=floor(abs(Group3(t)-MeanGroup3)); 81 end 82 [MaxAbsGroup3 MaxAbsGroup3Index]=min(AbsGroup3); 83 NewCenter(3)=Group3(MaxAbsGroup2Index); 84 clear AbsGroup3; 85 86 %判断新的类和旧类的聚类中心是否不同,不同则继续聚类,否则聚类结束 87 JudgeEqual=zeros(1,k); 88 for i=1:k 89 JudgeEqual=(NewCenter==Center); 90 end 91 92 S=0; 93 for i=1:k 94 if(JudgeEqual(i)==1) 95 S=S+1; 96 end 97 end 98 99 if(S==3)100 break;101 end102 103 Circulm=Circulm+1;104 end
聚类结果如下: