k-means聚类算法的研究1．k-means算法简介1.1 k-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.2 k-means算法实现步骤k-means聚类算法的处理流程如下：首先，随机选择k个对象，每个对象代表一个簇的初始均值或中心；对剩余的每个对象，根据其与各簇中心的距离，将它指派到最近（或最相似）的簇，然后计算每个簇的新均值，得到更新后的簇中心；不断重复，直到准则函数收敛。

通常，采用平方误差准则，即对于每个簇中的每个对象，求对象到其中心距离的平方和，这个准则试图生成的k个结果簇尽可能地紧凑和独立。

1.2.1 k-means聚类算法的形式化描述算法：k-means输入：聚类个数k，以及包含n个数据对象的数据库D输出：满足方差最小标准的k个聚类处理流程：Step1 从n个数据对象任意选择k个对象作为初始聚类中心；Step2 根据簇中对象的平均值，将每个对象重新赋给最类似的簇；Step3 更新簇的平均值，即计算每个簇中对象的平均值；Step4 循环Step2到Step3直到每个聚类不再发生变化为止。

1.2.2 k-means聚类算法的具体步骤1)Function k-means（）2)输入：包含n个对象的数据集及簇的数目3)输出：k个簇的集合4)初始化k个簇中心{w1，w2，…，w k}，其中w j= i l，j ∈{1,2，…，k}，l ∈{1,2，…，n}5)使每一个聚类C j与簇中心w j中相对应6)repeat7)for每一个输入向量i l，其中l ∈{1,2，…，n } do8)将i l分配给最近的簇中心w j*所属的聚类C j*（即|i l—w j*|≦|i l—w j|），j ∈（1,2，…，k））9)for 每一个聚类C j，其中j ∈{1,2，…，k}10)将簇中心更新为当前的C j中所有样本的中心点，即|iwjlj cij lC∈∑=11)计算准则函数E12) Until E 不再明显地改变或者聚类的成员不再变化1.2.3 相关定义（1）两个数据对象间的距离：①明氏距离（Minkowski Distance ）∑==p k x x x x d 11/qq jk ik j i )|-|(),( （公式1）这里的x i =( x i1，x i2，…，x ip )和x j =( x j1，x j2，…，x jp )是两个p 维的数据对象并且 i≠j 。

②欧式距离（Euclidean Distance ）当明氏距离中q=2时，公式1即欧式距离。

∑==p k x x x x d 11/22jk ik j i )|-|(),( （公式2）③马氏距离（Mahalanobis Distance ）p p ⨯=∑)(ij σ （公式3） 其中∑==nk x x x x n 1j k j i k i ij )-)(-(1-1σ，i ，j=1，2…，p 。

如果∑-1存在，则马氏距离为 ),(),(),(j i 1T j i j i 2x x x x x x d M -∑= （公式4）④兰式距离（Canberra Distance ）：∑=+=p k L x x x x x x d 1jkik jk ik j i |-|p 1),( （公式5） （2）准则函数E对于K-means 算法，通常使用准则函数E ，也就是误差平方和（Sum of Squared Error ，SSE ）作为度量聚类质量的目标函数。

∑∑=∈=ki C x i x d E 1i 2),(C （公式6）其中，d( )表示两个对象之间的距离，可以利用明氏、欧式、马氏或兰氏距离求得。

对于相同的k 值，更小的SSE 说明簇中对象越集中。

对于不同的k 值，越大的k 值应该越小的SSE 。

2．k-means 算法应用实例k-means 聚类广泛应用于地球科学、信息技术、决策科学、医学、行为学和商业智能等领域。

现以其在气象、遥感两个方面的应用为例，使用MATLAB语言编程，实现k-means算法的应用。

2.1 k-means算法应用实例（一）以我国主要城市2008年1～4月份的平均气温数据为基础，使用MATLAB语言编程，实现k-means算法。

2.1.1 算法代码（1）k-means算法主程序k=3;x =[ -3.0 0.6 9.1 15.8-3.6 -0.7 8.6 15.8-2.0 2.5 10.6 16.3-5.5 -3.3 7.1 13.1-12.1 -9.3 3.4 11.4-12.6 -7.9 3.8 12.2-15.6 -9.4 3.0 12.1-17.6 -10.5 2.7 11.34.2 4.0 11.4 15.91.52.5 11.3 15.63.7 3.9 12.7 17.11.02.7 12.5 16.811.0 9.1 15.3 19.33.5 5.5 14.6 18.7-2.0 1.0 10.3 16.3-0.7 2.8 12.1 16.91.2 4.9 14.4 18.52.3 5.5 15.2 18.912.8 11.6 20.1 23.29.4 10.4 19.1 22.916.9 13.3 20.9 25.36.27.3 15.5 19.03.7 5.4 13.4 17.21.02.2 11.8 15.710.7 8.5 13.7 18.01.5 1.4 5.6 10.1-1.7 1.8 12.5 16.4-6.6 -4.1 9.1 13.8-9.6 -7.9 3.4 8.3-10.2 -7.7 7.3 13.4-15.6 -9.6 5.2 11.1];[n,d] = size(x);bn=round(n/k*rand);%第一个随机数在前1/K的范围内nc=[x(bn,:);x(2*bn,:);x(3*bn,:)];%初始聚类中心for i=1:length(x),if cid(i)==1,plot(x(i,1),x(i,2),'r*') % 显示第一类hold onelseif cid(i)==2,plot(x(i,1),x(i,2),'b*') %显示第二类hold onelseif cid(i)==3,plot(x(i,1),x(i,2),'g*') %显示第三类hold onendendendendstrt=['红色*为第一类；蓝色*为第二类；绿色*为第三类' ];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);% Make this different to get the loop started.oldcid = ones(1,n);% The number in each cluster.nr = zeros(1,k);% Set up maximum number of iterations.maxgn= 100;iter = 1;while iter < maxgn%计算每个数据到聚类中心的距离for i = 1:ndist = sum((repmat(x(i,:),k,1)-nc).^2,2);[m,ind] = min(dist); % 将当前聚类结果存入cid中cid(i) = ind;endfor i = 1:k%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心ind = find(cid==i);nc(i,:) = mean(x(ind,:));% 统计每一类的数据个数nr(i) = length(ind);endend% Now check each observation to see if the error can be minimized some more. % Loop through all points.maxiter = 2;iter = 1;move = 1;while iter < maxiter & move ~= 0move = 0;% 对所有的数据进行再次判断，寻求最佳聚类结果for i = 1:ndist = sum((repmat(x(i,:),k,1)-nc).^2,2);r = cid(i); % 将当前数据属于的类给rdadj = nr./(nr+1).*dist'; % 计算调整后的距离[m,ind] = min(dadj); % 早到该数据距哪个聚类中心最近if ind ~= r % 如果不等则聚类中心移动cid(i) = ind;%将新的聚类结果送给cidic = find(cid == ind);%重新计算调整当前类别的聚类中心nc(ind,:) = mean(x(ic,:));move = 1;endenditer = iter+1;endcenters = nc;if move == 0disp('No points were moved after the initial clustering procedure.')elsedisp('Some points were moved after the initial clustering procedure.')end2.1.2 使用数据2.1.3 分类效果及结果分析（1）聚类过程No points were moved after the initial clustering procedure.cid =Columns 1 through 182 2 2 1 1 1 1 1 2 2 2 23 2 2 2 2 2Columns 19 through 313 3 3 3 2 2 3 2 2 1 1 1 1nr =9 16 6centers =-11.7111 -7.7444 5.0000 11.85560.6625 2.8750 11.6313 16.375011.1667 10.0333 17.4333 21.2833（2）分类效果图图1 案例一效果图（3）分类结果分析在本案例中主要是对全国主要城市的气温进行k-means聚类分析，从而总结出不同地区相同时间段内气温变化的相似性和差异性。