k-means聚类算法的研究全解

k-means聚类算法的研究1．k-means算法简介1.1k-means算法描述给定n个对象的数据集D和要生成的簇数目k，划分算法将对象组织划分为k个簇（k=n），这些簇的形成旨在优化一个目标准则。例如，基于距离的差异性函数，使得根据数据集的属性，在同一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”。划分聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数收敛时，得到最终聚类结果。这类方法分为基于质心的（Centroid-based）划分方法和基于中心的（Medoid-based）划分方法，而基于质心的划分方法是研究最多的算法，其中k-means算法是最具代表和知名的。k-means算法是1967年由MacQueen首次提出的一种经典算法，经常用于数据挖掘和模式识别中，是一种无监督式的学习算法，其使用目的是对几何进行等价类的划分，即对一组具有相同数据结构的记录按某种分类准则进行分类，以获取若干个同类记录集。k-means聚类是近年来数据挖掘学科的一个研究热点和重点，这主要是因为它广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智能等领域。迄今为止，很多聚类任务都选择该算法。k-means算法是应用最为广泛的聚类算法。该算法以类中各样本的加权均值（成为质心）代表该类，只用于数字属性数据的聚类，算法有很清晰的几何和统计意义，但抗干扰性较差。通常以各种样本与其质心欧几里德距离总和作为目标函数，也可将目标函数修改为各类中任意两点间欧几里德距离总和，这样既考虑了类的分散度也考虑了类的紧致度。k-means算法是聚类分析中基于原型的划分聚类的应用算法。如果将目标函数看成分布归一化混合模型的似然率对数，k-means算法就可以看成概率模型算法的推广。k-means算法基本思想：（1）随机的选K个点作为聚类中心；（2）划分剩余的点；（3）迭代过程需要一个收敛准则，此次采用平均误差准则。（4）求质心（作为中心）；（5）不断求质心，直到不再发生变化时，就得到最终的聚类结果。k-means聚类算法是一种广泛应用的聚类算法，计算速度快，资源消耗少，但是k-means算法与初始选择有关系，初始聚类中心选择的随机性决定了算法的有效性和聚类的精度，初始选择不一样，结果也不一样。其缺陷是会陷于局部最优。1.2k-means算法实现步骤k-means聚类算法的处理流程如下：首先，随机选择k个对象，每个对象代表一个簇的初始均值或中心；对剩余的每个对象，根据其与各簇中心的距离，将它指派到最近（或最相似）的簇，然后计算每个簇的新均值，得到更新后的簇中心；不断重复，直到准则函数收敛。通常，采用平方误差准则，即对于每个簇中的每个对象，求对象到其中心距离的平方和，这个准则试图生成的k个结果簇尽可能地紧凑和独立。1.2.1k-means聚类算法的形式化描述算法：k-means输入：聚类个数k，以及包含n个数据对象的数据库D输出：满足方差最小标准的k个聚类处理流程：Step1从n个数据对象任意选择k个对象作为初始聚类中心；Step2根据簇中对象的平均值，将每个对象重新赋给最类似的簇；Step3更新簇的平均值，即计算每个簇中对象的平均值；Step4循环Step2到Step3直到每个聚类不再发生变化为止。1.2.2k-means聚类算法的具体步骤1)Functionk-means（）2)输入：包含n个对象的数据集及簇的数目3)输出：k个簇的集合4)初始化k个簇中心{w1，w2，…，wk}，其中wj=il，j∈{1,2，…，k}，l∈{1,2，…，n}5)使每一个聚类Cj与簇中心wj中相对应6)repeat7)for每一个输入向量il，其中l∈{1,2，…，n}do8)将il分配给最近的簇中心wj*所属的聚类Cj*（即|il—wj*|≦|il—wj|），j∈（1,2，…，k））9)for每一个聚类Cj，其中j∈{1,2，…，k}10)将簇中心更新为当前的Cj中所有样本的中心点，即||iwjljcijlC11)计算准则函数E12)UntilE不再明显地改变或者聚类的成员不再变化1.2.3相关定义（1）两个数据对象间的距离：①明氏距离（MinkowskiDistance）pkxxxxd11/qqjkikji)|-|(),(（公式1）这里的xi=(xi1，xi2，…，xip)和xj=(xj1，xj2，…，xjp)是两个p维的数据对象并且i≠j。②欧式距离（EuclideanDistance）当明氏距离中q=2时，公式1即欧式距离。pkxxxxd11/22jkikji)|-|(),(（公式2）③马氏距离（MahalanobisDistance）pp)(ij（公式3）其中nkxxxxn1jkjikiij)-)(-(1-1，i，j=1，2…，p。如果∑-1存在，则马氏距离为),(),(),(ji1Tjiji2xxxxxxdM（公式4）④兰式距离（CanberraDistance）：pkLxxxxxxd1jkikjkikji|-|p1),(（公式5）（2）准则函数E对于K-means算法，通常使用准则函数E，也就是误差平方和（SumofSquaredError，SSE）作为度量聚类质量的目标函数。kiCxixdE1i2),(C（公式6）其中，d()表示两个对象之间的距离，可以利用明氏、欧式、马氏或兰氏距离求得。对于相同的k值，更小的SSE说明簇中对象越集中。对于不同的k值，越大的k值应该越小的SSE。2．k-means算法应用实例k-means聚类广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智能等领域。现以其在气象、遥感两个方面的应用为例，使用MATLAB语言编程，实现k-means算法的应用。2.1k-means算法应用实例（一）以我国主要城市2008年1～4月份的平均气温数据为基础，使用MATLAB语言编程，实现k-means算法。2.1.1算法代码（1）k-means算法主程序k=3;x=[-3.00.69.115.8-3.6-0.78.615.8-2.02.510.616.3-5.5-3.37.113.1-12.1-9.33.411.4-12.6-7.93.812.2-15.6-9.43.012.1-17.6-10.52.711.34.24.011.415.91.52.511.315.63.73.912.717.11.02.712.516.811.09.115.319.33.55.514.618.7-2.01.010.316.3-0.72.812.116.91.24.914.418.52.35.515.218.912.811.620.123.29.410.419.122.916.913.320.925.36.27.315.519.03.75.413.417.21.02.211.815.710.78.513.718.01.51.45.610.1-1.71.812.516.4-6.6-4.19.113.8-9.6-7.93.48.3-10.2-7.77.313.4-15.6-9.65.211.1];[n,d]=size(x);bn=round(n/k*rand);%第一个随机数在前1/K的范围内nc=[x(bn,:);x(2*bn,:);x(3*bn,:)];%初始聚类中心[cid,nr,centers]=kmeans(x,k,nc)%调用kmeans函数fori=1:length(x),ifcid(i)==1,plot(x(i,1),x(i,2),'r*')%显示第一类holdonelseifcid(i)==2,plot(x(i,1),x(i,2),'b*')%显示第二类holdonelseifcid(i)==3,plot(x(i,1),x(i,2),'g*')%显示第三类holdonendendendendstrt=['红色*为第一类；蓝色*为第二类；绿色*为第三类'];text(-4,-3.6,strt);（2）kmeans函数如下:%BasicKMeans.m主类function[cid,nr,centers]=kmeans(x,k,nc)[n,d]=size(x);%设置cid为分类结果显示矩阵cid=zeros(1,n);%Makethisdifferenttogettheloopstarted.oldcid=ones(1,n);%Thenumberineachcluster.nr=zeros(1,k);%Setupmaximumnumberofiterations.maxgn=100;iter=1;whileitermaxgn%计算每个数据到聚类中心的距离fori=1:ndist=sum((repmat(x(i,:),k,1)-nc).^2,2);[m,ind]=min(dist);%将当前聚类结果存入cid中cid(i)=ind;endfori=1:k%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心ind=find(cid==i);nc(i,:)=mean(x(ind,:));%统计每一类的数据个数nr(i)=length(ind);enditer=iter+1;end%Nowcheckeachobservationtoseeiftheerrorcanbeminimizedsomemore.%Loopthroughallpoints.maxiter=2;iter=1;move=1;whileitermaxiter&move~=0move=0;%对所有的数据进行再次判断，寻求最佳聚类结果fori=1:ndist=sum((repmat(x(i,:),k,1)-nc).^2,2);r=cid(i);%将当前数据属于的类给rdadj=nr./(nr+1).*dist';%计算调整后的距离[m,ind]=min(dadj);%早到该数据距哪个聚类中心最近ifind~=r%如果不等则聚类中心移动cid(i)=ind;%将新的聚类结果送给cidic=find(cid==ind);%重新计算调整当前类别的聚类中心nc(ind,:)=mean(x(ic,:));move=1;endenditer=iter+1;endcenters=nc;ifmove==0disp('Nopointsweremovedaftertheinitialclusteringprocedure.')elsedisp('Somepointsweremovedaftertheinitialclusteringprocedure.')end2.1.2使用数据城市1月2月3月4月北京-30.69.115.8天津-3.6-0.78.615.8石家庄-22.510.616.3太原-5.5-3.37.113.1呼和浩特-12.1-9.33.411.4沈阳-12.6-7.93.812.2长春-15.6-9.4312.1哈尔滨-17.6-10.52.711.3上海4.2411.415.9南京1.52.511.315.6杭州3.73.912.717.1合肥12.712.516.8福州119.115.319.3南昌3.55.514.618.7济南-2110.316.3郑州-0.72.812.116.9武汉1.24.914.418.5长沙2.35.515.218.9广州12.811.620.123.2南宁9.410.419.122.9海口16.913.320.925.3重庆6.27.315.519成都3.75.413.417.2贵阳12.211.815.7昆明10.78.513.718拉萨1.51.45.610.1西安-1.71.812.516.4兰州-6.6-4.19.113.8西宁-9.6-7.93.48.3银川-10.2-7.77.313.4乌鲁木齐-15.6-9.65.211.12.1.3分类效果及结果分析（1）聚类过程Nopointsweremovedaftert