2023年8月2日发(作者：)
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，…，wk}，其中wj= il，j ∈{1,2，…，k}，l ∈{1,2，…，n}
5) 使每一个聚类Cj与簇中心wj中相对应
6) repeat
7) for每一个输入向量il，其中l ∈{1,2，…，n } do
8) 将il分配给最近的簇中心wj*所属的聚类Cj*
（即|il—wj*|≦|il—wj|），j ∈（1,2，…，k））
9) for 每一个聚类Cj，其中j ∈{1,2，…，k}
10) 将簇中心更新为当前的Cj中所有样本的中心点，即wj11) 计算准则函数E
ilcjil|Cj| 12) Until E不再明显地改变或者聚类的成员不再变化
1.2.3 相关定义
（1）两个数据对象间的距离：
①明氏距离（Minkowski Distance）
d(xi,xj)(|xik-xjk|q)1/qk1p （公式1）
这里的xi=(
xi1，xi2，…，xip)和xj=(
xj1，xj2，…，xjp)是两个p维的数据对象并且 i≠j。
②欧式距离（Euclidean Distance）
当明氏距离中q=2时，公式1即欧式距离。
d(xi,xj)(|xik-xjk|2)1/2k1p （公式2）
③马氏距离（Mahalanobis Distance）
(ij)pp （公式3）
1n(xki-xi)(xkj-xj)，i，j=1，2…，p。如果∑-1存在，则马氏距离为 其中ijn-1k1
2dM(xi,xj)(xi,xj)T1(xi,xj) （公式4）
④兰式距离（Canberra Distance）：
1p|xik-xjk|dL(xi,xj) （公式5）
pk1xikxjk（2）准则函数E
对于K-means算法，通常使用准则函数E，也就是误差平方和（Sum of Squared Error，SSE）作为度量聚类质量的目标函数。
Ed2(Ci,x) （公式6）
i1xCik其中，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.3
4.2 4.0 11.4 15.9
1.5 2.5 11.3 15.6
3.7 3.9 12.7 17.1
1.0 2.7 12.5 16.8
11.0 9.1 15.3 19.3
3.5 5.5 14.6 18.7
-2.0 1.0 10.3 16.3
-0.7 2.8 12.1 16.9
1.2 4.9 14.4 18.5
2.3 5.5 15.2 18.9
12.8 11.6 20.1 23.2
9.4 10.4 19.1 22.9
16.9 13.3 20.9 25.3
6.2 7.3 15.5 19.0
3.7 5.4 13.4 17.2
1.0 2.2 11.8 15.7
10.7 8.5 13.7 18.0
1.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,:)];%初始聚类中心
[cid,nr,centers] = kmeans(x,k,nc)%调用kmeans函数 for i=1:length(x),
if cid(i)==1,
plot(x(i,1),x(i,2),'r*') % 显示第一类
hold on
else
if cid(i)==2,
plot(x(i,1),x(i,2),'b*') %显示第二类
hold on
else
if cid(i)==3,
plot(x(i,1),x(i,2),'g*') %显示第三类
hold on
end
end
end
end
strt=['红色*为第一类；蓝色*为第二类；绿色*为第三类' ];
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:n
dist = sum((repmat(x(i,:),k,1)-nc).^2,2);
[m,ind] = min(dist); % 将当前聚类结果存入cid中
cid(i) = ind;
end
for i = 1:k
%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心
ind = find(cid==i);
nc(i,:) = mean(x(ind,:));
% 统计每一类的数据个数
nr(i) = length(ind);
end
iter = iter + 1; end
% 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 ~= 0
move = 0;
% 对所有的数据进行再次判断，寻求最佳聚类结果
for i = 1:n
dist = sum((repmat(x(i,:),k,1)-nc).^2,2);
r = cid(i); % 将当前数据属于的类给r
dadj = nr./(nr+1).*dist'; % 计算调整后的距离
[m,ind] = min(dadj); % 早到该数据距哪个聚类中心最近
if ind ~= r % 如果不等则聚类中心移动
cid(i) = ind;%将新的聚类结果送给cid
ic = find(cid == ind);%重新计算调整当前类别的聚类中心
nc(ind,:) = mean(x(ic,:));
move = 1;
end
end
iter = iter+1;
end
centers = nc;
if move == 0
disp('No points were moved after the initial clustering procedure.')
else
disp('Some points were moved after the initial clustering procedure.')
end
2.1.2 使用数据
城 市 1月 2月 3月 4月
北 京 -3 0.6 9.1 15.8
天 津 -3.6 -0.7 8.6 15.8
石 家 庄 -2 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 12.1
哈 尔 滨 -17.6 -10.5 2.7 11.3
上 海 4.2 4 11.4 15.9
南 京 1.5 2.5 11.3 15.6
杭 州 3.7 3.9 12.7 17.1
合 肥 1 2.7 12.5 16.8
福 州 11 9.1 15.3 19.3 南 昌 3.5 5.5 14.6 18.7
济 南 -2 1 10.3 16.3
郑 州 -0.7 2.8 12.1 16.9
武 汉 1.2 4.9 14.4 18.5
长 沙 2.3 5.5 15.2 18.9
广 州 12.8 11.6 20.1 23.2
南 宁 9.4 10.4 19.1 22.9
海 口 16.9 13.3 20.9 25.3
重 庆 6.2 7.3 15.5 19
成 都 3.7 5.4 13.4 17.2
贵 阳 1 2.2 11.8 15.7
昆 明 10.7 8.5 13.7 18
拉 萨 1.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
2.1.3 分类效果及结果分析
（1）聚类过程
No points were moved after the initial clustering procedure.
cid =
Columns 1 through 18
2 2 2 1 1 1 1 1 2 2 2 2 3 2
2 2 2 2
Columns 19 through 31
3 3 3 3 2 2 3 2 2 1 1 1 1
nr =
9 16 6
centers =
-11.7111 -7.7444 5.0000 11.8556
0.6625 2.8750 11.6313 16.3750
11.1667 10.0333 17.4333 21.2833 （2）分类效果图
图1 案例一效果图
（3）分类结果分析
在本案例中主要是对全国主要城市的气温进行k-means聚类分析，从而总结出不同地区相同时间段内气温变化的相似性和差异性。但由于数据的原因，效果不是很明显。
综合海陆位置、海拔以及经纬度等多种地理学因素，可以得出：第一类红色代表北纬40°以北地区，第二类蓝色代表北纬25°～40°之间的地区，第三类绿色代表北纬25°以南地区。
2.2 k-means算法应用实例（二）
此案例主要是k-means算法在遥感图像中的应用：将某一区域的遥感图像波段信息进行标准化处理，标准化的方法为平均值标准化，即（某一波段像元灰度值减去该波段像元灰度平均值）/该波段像元灰度平均值。
2.2.1 算法代码
（1）k-means算法主程序
%k-means算法主程序
k=4;
x =[ 1.2126 2.1338 0.5115 0.2044
-0.9316 0.7634 0.0125 -0.2752
-2.9593 0.1813 -0.8833 0.8505
3.1104 -2.5393 -0.0588 0.1808
-3.1141 -0.1244 -0.6811 0.9891
-3.2008 0.0024 -1.2901 0.9748 -1.0777 1.1438 0.1996 0.0139
-2.7213 -0.1909 0.1184 0.1013
-1.1467 1.3820 0.1427 -0.2239
1.1497 1.9414 -0.3035 0.3464
2.6993 -2.2556 0.1637 -0.0139
-3.0311 0.1417 0.0888 0.1791
-2.8403 -0.1809 -0.0965 0.0817
1.0118 2.0372 0.1638 -0.0349
-0.8968 1.0260 -0.1013 0.2369
1.1112 1.8802 -0.0291 -0.1506
1.1907 2.2041 -0.1060 0.2167
-1.0114 0.8029 -0.1317 0.0153
-3.1715 0.1041 -0.3338 0.0321
0.9718 1.9634 0.0305 -0.3259
-1.0377 0.8889 -0.2834 0.2301
-0.8989 1.0185 -0.0289 0.0213
-2.9815 -0.4798 0.2245 0.3085
-0.8576 0.9231 -0.2752 -0.0091
-3.1356 0.0026 -1.2138 0.7733
3.4470 -2.2418 0.2014 -0.1556
2.9143 -1.7951 0.1992 -0.2146
3.4961 -2.4969 -0.0121 0.1315
-2.9341 -0.1071 -0.7712 0.8911
-2.8105 -0.0884 -0.0287 -0.1279
3.1006 -2.0677 -0.2002 -0.1303
0.8209 2.1724 0.1548 0.3516
-2.8500 0.3196 0.1359 -0.1179
-2.8679 0.1365 -0.5702 0.7626
-2.8245 -0.1312 0.0881 -0.1305
-0.8322 1.3014 -0.3837 0.2400
-2.6063 0.1431 0.1880 0.0487
-3.1341 -0.0854 -0.0359 -0.2080
0.6893 2.0854 -0.3250 -0.1007
1.0894 1.7271 -0.0176 0.6553
-2.9851 -0.0113 0.0666 -0.0802
1.0371 2.2724 0.1044 0.3982
-2.8032 -0.2737 -0.7391 1.0277
-2.6856 0.0619 -1.1066 1.0485
-2.9445 -0.1602 -0.0019 0.0093
1.2004 2.1302 -0.1650 0.3413
3.2505 -1.9279 0.4462 -0.2405
-1.2080 0.8222 0.1671 0.1576
-2.8274 0.1515 -0.9636 1.0675
2.8190 -1.8626 0.2702 0.0026
1.0507 1.7776 -0.1421 0.0999
-2.8946 0.1446 -0.1645 0.3071 -1.0105 1.0973 0.0241 0.1628
-2.9138 -0.3404 0.0627 0.1286
-3.0646 -0.0008 0.3819 -0.1541
1.2531 1.9830 -0.0774 0.2413
1.1486 2.0440 -0.0582 -0.0650
-3.1401 -0.1447 -0.6580 0.9562
-2.9591 0.1598 -0.6581 1.1937
-2.9219 -0.3637 -0.1538 -0.2085
2.8948 -2.2745 0.2332 -0.0312
-3.2972 -0.0219 -0.0288 -0.1436
-1.2737 0.7648 0.0643 0.0858
-1.0690 0.8108 -0.2723 0.3231
-0.5908 0.7508 -0.5456 0.0190
0.5808 2.0573 -0.1658 0.1709
2.8227 -2.2461 0.2255 -0.3684
0.6174 1.7654 -0.3999 0.4125
3.2587 -1.9310 0.2021 0.0800
1.0999 1.8852 -0.0475 -0.0585
-2.7395 0.2585 -0.8441 0.9987
-1.2223 1.0542 -0.2480 -0.2795
-2.9212 -0.0605 -0.0259 0.2591
3.1598 -2.2631 0.1746 0.1485
0.8476 1.8760 -0.2894 -0.0354
2.9205 -2.2418 0.4137 -0.2499
2.7656 -2.1768 0.0719 -0.1848
-0.8698 1.0249 -0.2084 -0.0008
-1.1444 0.7787 -0.4958 0.3676
-1.0711 1.0450 -0.0477 -0.4030
0.5350 1.8110 -0.0377 0.1622
0.9076 1.8845 -0.1121 0.5700
-2.7887 -0.2119 0.0566 0.0120
-1.2567 0.9274 0.1104 0.1581
-2.9946 -0.2086 -0.8169 0.6662
1.0536 1.9818 -0.0631 0.2581
-2.8465 -0.2222 0.2745 0.1997
-2.8516 0.1649 -0.7566 0.8616
-3.2470 0.0770 0.1173 -0.1092
-2.9322 -0.0631 -0.0062 -0.0511
-2.7919 0.0438 -0.1935 -0.5023
0.9894 1.9475 -0.0146 -0.0390
-2.9659 -0.1300 0.1144 0.3410
-2.7322 -0.0427 -1.0758 0.9718
-1.4852 0.8592 -0.0503 -0.1373
2.8845 -2.1465 -0.0533 -0.1044
-3.1470 0.0536 0.1073 0.3323
2.9423 -2.1572 0.0505 0.1180 -3.0683 0.3434 -0.6563 0.8960
1.3215 2.0951 -0.1557 0.3994
-0.7681 1.2075 -0.2781 0.2372
-0.6964 1.2360 -0.3342 0.1662
-0.6382 0.8204 -0.2587 0.3344
-3.0233 -0.1496 -0.2607 -0.0400
-0.8952 0.9872 0.0019 0.3138
-0.8172 0.6814 -0.0691 0.1009
-3.3032 0.0571 -0.0243 -0.1405
0.7810 1.9013 -0.3996 0.7374
-0.9030 0.8646 -0.1498 0.1112
-0.8461 0.9261 -0.1295 -0.0727
2.8182 -2.0818 -0.1430 -0.0547
2.9295 -2.3846 -0.0244 -0.1400
1.0587 2.2227 -0.1250 0.0957
3.0755 -1.7365 -0.0511 0.1500
-1.3076 0.8791 -0.3720 0.0331
-2.8252 -0.0366 -0.6790 0.7374
-2.6551 -0.1875 0.3222 0.0483
-2.9659 -0.1585 0.4013 -0.1402
-3.2859 -0.1546 0.0104 -0.1781
-0.6679 1.1999 0.1396 -0.3195
-1.0205 1.2226 0.1850 0.0050
-3.0091 -0.0186 -0.9111 0.9663
-3.0339 0.1377 -0.9662 1.0664
0.8952 1.9594 -0.3221 0.3579
-2.8481 0.1963 -0.1428 0.0382
1.0796 2.1353 -0.0792 0.6491
-0.8732 0.8985 -0.0049 0.0068
1.0620 2.1478 -0.1275 0.3553
3.4509 -1.9975 0.1285 -0.1575
-3.2280 -0.0640 -1.1513 0.8235
-0.6654 0.9402 0.0577 -0.0175
-3.2100 0.2762 -0.1053 0.0626
3.0793 -2.0043 0.2948 0.0411
1.3596 1.9481 -0.0167 0.3958
-3.1267 0.1801 0.2228 0.1179
-0.7979 0.9892 -0.2673 0.4734
2.5580 -1.7623 -0.1049 -0.0521
-0.9172 1.0621 -0.0826 0.1501
-0.7817 1.1658 0.1922 0.0803
3.1747 -2.1442 0.1472 -0.3411
2.8476 -1.8056 -0.0680 0.1536
-0.6175 1.4349 -0.1970 -0.1085
0.7308 1.9656 0.2602 0.2801
-1.0310 1.0553 -0.2928 -0.1647 -2.9251 -0.2095 0.0582 -0.1813
-0.9827 1.2720 -0.2225 0.2563
-1.0830 1.1158 -0.0405 -0.1181
-2.8744 0.0195 -0.3811 0.1455
3.1663 -1.9241 0.0455 0.1684
-1.0734 0.7681 -0.4725 -0.1976];
[n,d] = size(x);
bn=round(n/k*rand);%第一个随机数在前1/K的范围内
nc=[x(bn,:);x(2*bn,:);x(3*bn,:);x(4*bn,:)];%初始聚类中心
[cid,nr,centers] = kmeans(x,k,nc)%调用kmeans函数
for i=1:150,
if cid(i)==1,
plot(x(i,1),x(i,2),'r*') % 显示第一类
hold on
else
if cid(i)==2,
plot(x(i,1),x(i,2),'b*') %显示第二类
hold on
else
if cid(i)==3,
plot(x(i,1),x(i,2),'g*') %显示第三类
hold on
else
if cid(i)==4,
plot(x(i,1),x(i,2),'k*') %显示第四类
hold on
end
end
end
end
end
strt=['红色*为第一类；蓝色*为第二类；绿色*为第三类；黑色*为第四类' ];
text(-4,-3.6,strt);
（2）kmeans函数
kmeans函数同案例（一）
2.2.2 使用数据
（由于数据太多，就不在此表述，数据已经在程序中表述）
2.2.3 分类效果图及结果分析
（1）聚类过程
No points were moved after the initial clustering procedure.
cid = Columns 1 through 18
1 4 2 3 2 2 4 2 4 1 3 2 2 1
4 1 1 4
Columns 19 through 36
2 1 4 4 2 4 2 3 3 3 2 2 3 1
2 2 2 4
Columns 37 through 54
2 2 1 1 2 1 2 2 2 1 3 4 2 3
1 2 4 2
Columns 55 through 72
2 1 1 2 2 2 3 2 4 4 4 1 3 1
3 1 2 4
Columns 73 through 90
2 3 1 3 3 4 4 4 1 1 2 4 2 1
2 2 2 2
Columns 91 through 108
2 1 2 2 4 3 2 3 2 1 4 4 4 2
4 4 2 1
Columns 109 through 126
4 4 3 3 1 3 4 2 2 2 2 4 4 2
2 1 2 1
Columns 127 through 144
4 1 3 2 4 2 3 1 2 4 3 4 4 3
3 4 1 4
Columns 145 through 150
2 4 4 2 3 4
nr =
30 55 25 40
centers = 0.9952 1.9979 -0.0785 0.2296
-2.9629 -0.0230 -0.2970 0.3411
3.0234 -2.0986 0.1021 -0.0506
-0.9569 0.9978 -0.1237 0.0493
（2）分类效果图
图2 案例二效果图
（3）分类结果分析
k-means算法在本案例中主要是对遥感图像像元灰度值进行聚类分析，从而确定地物类型，最后根据像元灰度值的特定规律，结合地理学知识，对遥感图像进行解译。
综合遥感波段知识，可以得出：第一类红色的代表居民地，第二类蓝色代表植被，第三类绿色代表水体，第四类黑色的代表裸岩。 【参考文献】
[1] 陈晓春. 基于K-Means和EM算法的聚类分析[J].福建电脑，2009,2：79-80.
[2] 步媛媛，关忠仁. 基于K-means聚类算法的研究[J]. 西南民族大学学报，2009,35（1）：198-200.
[3] 陈寿文,李明东. 基于面向对象思想K-Means算法实现[J]. 滁州学院学报，2008,10（3）：42-44.
[4] 黄振华,向阳，张波，王栋，刘啸岭. 一种进行K-Means聚类的有效方法[J]. 模式识别与人工智能，2010,23（4）：516-521.
[5] 陈燕.数据挖掘技术与应用[M]. 北京:清华大学出版社,2011.
[6] 蒋盛益,李霞,郑琪.数据挖掘原理与实践[M]. 北京:电子工业出版社,2011.
[7] 邵峰晶,于忠清,王金龙，孙仁诚. 数据挖掘原理与算法[M]. 北京:科学出版社,2011.
2023年8月2日发(作者：)
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，…，wk}，其中wj= il，j ∈{1,2，…，k}，l ∈{1,2，…，n}
5) 使每一个聚类Cj与簇中心wj中相对应
6) repeat
7) for每一个输入向量il，其中l ∈{1,2，…，n } do
8) 将il分配给最近的簇中心wj*所属的聚类Cj*
（即|il—wj*|≦|il—wj|），j ∈（1,2，…，k））
9) for 每一个聚类Cj，其中j ∈{1,2，…，k}
10) 将簇中心更新为当前的Cj中所有样本的中心点，即wj11) 计算准则函数E
ilcjil|Cj| 12) Until E不再明显地改变或者聚类的成员不再变化
1.2.3 相关定义
（1）两个数据对象间的距离：
①明氏距离（Minkowski Distance）
d(xi,xj)(|xik-xjk|q)1/qk1p （公式1）
这里的xi=(
xi1，xi2，…，xip)和xj=(
xj1，xj2，…，xjp)是两个p维的数据对象并且 i≠j。
②欧式距离（Euclidean Distance）
当明氏距离中q=2时，公式1即欧式距离。
d(xi,xj)(|xik-xjk|2)1/2k1p （公式2）
③马氏距离（Mahalanobis Distance）
(ij)pp （公式3）
1n(xki-xi)(xkj-xj)，i，j=1，2…，p。如果∑-1存在，则马氏距离为 其中ijn-1k1
2dM(xi,xj)(xi,xj)T1(xi,xj) （公式4）
④兰式距离（Canberra Distance）：
1p|xik-xjk|dL(xi,xj) （公式5）
pk1xikxjk（2）准则函数E
对于K-means算法，通常使用准则函数E，也就是误差平方和（Sum of Squared Error，SSE）作为度量聚类质量的目标函数。
Ed2(Ci,x) （公式6）
i1xCik其中，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.3
4.2 4.0 11.4 15.9
1.5 2.5 11.3 15.6
3.7 3.9 12.7 17.1
1.0 2.7 12.5 16.8
11.0 9.1 15.3 19.3
3.5 5.5 14.6 18.7
-2.0 1.0 10.3 16.3
-0.7 2.8 12.1 16.9
1.2 4.9 14.4 18.5
2.3 5.5 15.2 18.9
12.8 11.6 20.1 23.2
9.4 10.4 19.1 22.9
16.9 13.3 20.9 25.3
6.2 7.3 15.5 19.0
3.7 5.4 13.4 17.2
1.0 2.2 11.8 15.7
10.7 8.5 13.7 18.0
1.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,:)];%初始聚类中心
[cid,nr,centers] = kmeans(x,k,nc)%调用kmeans函数 for i=1:length(x),
if cid(i)==1,
plot(x(i,1),x(i,2),'r*') % 显示第一类
hold on
else
if cid(i)==2,
plot(x(i,1),x(i,2),'b*') %显示第二类
hold on
else
if cid(i)==3,
plot(x(i,1),x(i,2),'g*') %显示第三类
hold on
end
end
end
end
strt=['红色*为第一类；蓝色*为第二类；绿色*为第三类' ];
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:n
dist = sum((repmat(x(i,:),k,1)-nc).^2,2);
[m,ind] = min(dist); % 将当前聚类结果存入cid中
cid(i) = ind;
end
for i = 1:k
%找到每一类的所有数据，计算他们的平均值，作为下次计算的聚类中心
ind = find(cid==i);
nc(i,:) = mean(x(ind,:));
% 统计每一类的数据个数
nr(i) = length(ind);
end
iter = iter + 1; end
% 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 ~= 0
move = 0;
% 对所有的数据进行再次判断，寻求最佳聚类结果
for i = 1:n
dist = sum((repmat(x(i,:),k,1)-nc).^2,2);
r = cid(i); % 将当前数据属于的类给r
dadj = nr./(nr+1).*dist'; % 计算调整后的距离
[m,ind] = min(dadj); % 早到该数据距哪个聚类中心最近
if ind ~= r % 如果不等则聚类中心移动
cid(i) = ind;%将新的聚类结果送给cid
ic = find(cid == ind);%重新计算调整当前类别的聚类中心
nc(ind,:) = mean(x(ic,:));
move = 1;
end
end
iter = iter+1;
end
centers = nc;
if move == 0
disp('No points were moved after the initial clustering procedure.')
else
disp('Some points were moved after the initial clustering procedure.')
end
2.1.2 使用数据
城 市 1月 2月 3月 4月
北 京 -3 0.6 9.1 15.8
天 津 -3.6 -0.7 8.6 15.8
石 家 庄 -2 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 12.1
哈 尔 滨 -17.6 -10.5 2.7 11.3
上 海 4.2 4 11.4 15.9
南 京 1.5 2.5 11.3 15.6
杭 州 3.7 3.9 12.7 17.1
合 肥 1 2.7 12.5 16.8
福 州 11 9.1 15.3 19.3 南 昌 3.5 5.5 14.6 18.7
济 南 -2 1 10.3 16.3
郑 州 -0.7 2.8 12.1 16.9
武 汉 1.2 4.9 14.4 18.5
长 沙 2.3 5.5 15.2 18.9
广 州 12.8 11.6 20.1 23.2
南 宁 9.4 10.4 19.1 22.9
海 口 16.9 13.3 20.9 25.3
重 庆 6.2 7.3 15.5 19
成 都 3.7 5.4 13.4 17.2
贵 阳 1 2.2 11.8 15.7
昆 明 10.7 8.5 13.7 18
拉 萨 1.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
2.1.3 分类效果及结果分析
（1）聚类过程
No points were moved after the initial clustering procedure.
cid =
Columns 1 through 18
2 2 2 1 1 1 1 1 2 2 2 2 3 2
2 2 2 2
Columns 19 through 31
3 3 3 3 2 2 3 2 2 1 1 1 1
nr =
9 16 6
centers =
-11.7111 -7.7444 5.0000 11.8556
0.6625 2.8750 11.6313 16.3750
11.1667 10.0333 17.4333 21.2833 （2）分类效果图
图1 案例一效果图
（3）分类结果分析
在本案例中主要是对全国主要城市的气温进行k-means聚类分析，从而总结出不同地区相同时间段内气温变化的相似性和差异性。但由于数据的原因，效果不是很明显。
综合海陆位置、海拔以及经纬度等多种地理学因素，可以得出：第一类红色代表北纬40°以北地区，第二类蓝色代表北纬25°～40°之间的地区，第三类绿色代表北纬25°以南地区。
2.2 k-means算法应用实例（二）
此案例主要是k-means算法在遥感图像中的应用：将某一区域的遥感图像波段信息进行标准化处理，标准化的方法为平均值标准化，即（某一波段像元灰度值减去该波段像元灰度平均值）/该波段像元灰度平均值。
2.2.1 算法代码
（1）k-means算法主程序
%k-means算法主程序
k=4;
x =[ 1.2126 2.1338 0.5115 0.2044
-0.9316 0.7634 0.0125 -0.2752
-2.9593 0.1813 -0.8833 0.8505
3.1104 -2.5393 -0.0588 0.1808
-3.1141 -0.1244 -0.6811 0.9891
-3.2008 0.0024 -1.2901 0.9748 -1.0777 1.1438 0.1996 0.0139
-2.7213 -0.1909 0.1184 0.1013
-1.1467 1.3820 0.1427 -0.2239
1.1497 1.9414 -0.3035 0.3464
2.6993 -2.2556 0.1637 -0.0139
-3.0311 0.1417 0.0888 0.1791
-2.8403 -0.1809 -0.0965 0.0817
1.0118 2.0372 0.1638 -0.0349
-0.8968 1.0260 -0.1013 0.2369
1.1112 1.8802 -0.0291 -0.1506
1.1907 2.2041 -0.1060 0.2167
-1.0114 0.8029 -0.1317 0.0153
-3.1715 0.1041 -0.3338 0.0321
0.9718 1.9634 0.0305 -0.3259
-1.0377 0.8889 -0.2834 0.2301
-0.8989 1.0185 -0.0289 0.0213
-2.9815 -0.4798 0.2245 0.3085
-0.8576 0.9231 -0.2752 -0.0091
-3.1356 0.0026 -1.2138 0.7733
3.4470 -2.2418 0.2014 -0.1556
2.9143 -1.7951 0.1992 -0.2146
3.4961 -2.4969 -0.0121 0.1315
-2.9341 -0.1071 -0.7712 0.8911
-2.8105 -0.0884 -0.0287 -0.1279
3.1006 -2.0677 -0.2002 -0.1303
0.8209 2.1724 0.1548 0.3516
-2.8500 0.3196 0.1359 -0.1179
-2.8679 0.1365 -0.5702 0.7626
-2.8245 -0.1312 0.0881 -0.1305
-0.8322 1.3014 -0.3837 0.2400
-2.6063 0.1431 0.1880 0.0487
-3.1341 -0.0854 -0.0359 -0.2080
0.6893 2.0854 -0.3250 -0.1007
1.0894 1.7271 -0.0176 0.6553
-2.9851 -0.0113 0.0666 -0.0802
1.0371 2.2724 0.1044 0.3982
-2.8032 -0.2737 -0.7391 1.0277
-2.6856 0.0619 -1.1066 1.0485
-2.9445 -0.1602 -0.0019 0.0093
1.2004 2.1302 -0.1650 0.3413
3.2505 -1.9279 0.4462 -0.2405
-1.2080 0.8222 0.1671 0.1576
-2.8274 0.1515 -0.9636 1.0675
2.8190 -1.8626 0.2702 0.0026
1.0507 1.7776 -0.1421 0.0999
-2.8946 0.1446 -0.1645 0.3071 -1.0105 1.0973 0.0241 0.1628
-2.9138 -0.3404 0.0627 0.1286
-3.0646 -0.0008 0.3819 -0.1541
1.2531 1.9830 -0.0774 0.2413
1.1486 2.0440 -0.0582 -0.0650
-3.1401 -0.1447 -0.6580 0.9562
-2.9591 0.1598 -0.6581 1.1937
-2.9219 -0.3637 -0.1538 -0.2085
2.8948 -2.2745 0.2332 -0.0312
-3.2972 -0.0219 -0.0288 -0.1436
-1.2737 0.7648 0.0643 0.0858
-1.0690 0.8108 -0.2723 0.3231
-0.5908 0.7508 -0.5456 0.0190
0.5808 2.0573 -0.1658 0.1709
2.8227 -2.2461 0.2255 -0.3684
0.6174 1.7654 -0.3999 0.4125
3.2587 -1.9310 0.2021 0.0800
1.0999 1.8852 -0.0475 -0.0585
-2.7395 0.2585 -0.8441 0.9987
-1.2223 1.0542 -0.2480 -0.2795
-2.9212 -0.0605 -0.0259 0.2591
3.1598 -2.2631 0.1746 0.1485
0.8476 1.8760 -0.2894 -0.0354
2.9205 -2.2418 0.4137 -0.2499
2.7656 -2.1768 0.0719 -0.1848
-0.8698 1.0249 -0.2084 -0.0008
-1.1444 0.7787 -0.4958 0.3676
-1.0711 1.0450 -0.0477 -0.4030
0.5350 1.8110 -0.0377 0.1622
0.9076 1.8845 -0.1121 0.5700
-2.7887 -0.2119 0.0566 0.0120
-1.2567 0.9274 0.1104 0.1581
-2.9946 -0.2086 -0.8169 0.6662
1.0536 1.9818 -0.0631 0.2581
-2.8465 -0.2222 0.2745 0.1997
-2.8516 0.1649 -0.7566 0.8616
-3.2470 0.0770 0.1173 -0.1092
-2.9322 -0.0631 -0.0062 -0.0511
-2.7919 0.0438 -0.1935 -0.5023
0.9894 1.9475 -0.0146 -0.0390
-2.9659 -0.1300 0.1144 0.3410
-2.7322 -0.0427 -1.0758 0.9718
-1.4852 0.8592 -0.0503 -0.1373
2.8845 -2.1465 -0.0533 -0.1044
-3.1470 0.0536 0.1073 0.3323
2.9423 -2.1572 0.0505 0.1180 -3.0683 0.3434 -0.6563 0.8960
1.3215 2.0951 -0.1557 0.3994
-0.7681 1.2075 -0.2781 0.2372
-0.6964 1.2360 -0.3342 0.1662
-0.6382 0.8204 -0.2587 0.3344
-3.0233 -0.1496 -0.2607 -0.0400
-0.8952 0.9872 0.0019 0.3138
-0.8172 0.6814 -0.0691 0.1009
-3.3032 0.0571 -0.0243 -0.1405
0.7810 1.9013 -0.3996 0.7374
-0.9030 0.8646 -0.1498 0.1112
-0.8461 0.9261 -0.1295 -0.0727
2.8182 -2.0818 -0.1430 -0.0547
2.9295 -2.3846 -0.0244 -0.1400
1.0587 2.2227 -0.1250 0.0957
3.0755 -1.7365 -0.0511 0.1500
-1.3076 0.8791 -0.3720 0.0331
-2.8252 -0.0366 -0.6790 0.7374
-2.6551 -0.1875 0.3222 0.0483
-2.9659 -0.1585 0.4013 -0.1402
-3.2859 -0.1546 0.0104 -0.1781
-0.6679 1.1999 0.1396 -0.3195
-1.0205 1.2226 0.1850 0.0050
-3.0091 -0.0186 -0.9111 0.9663
-3.0339 0.1377 -0.9662 1.0664
0.8952 1.9594 -0.3221 0.3579
-2.8481 0.1963 -0.1428 0.0382
1.0796 2.1353 -0.0792 0.6491
-0.8732 0.8985 -0.0049 0.0068
1.0620 2.1478 -0.1275 0.3553
3.4509 -1.9975 0.1285 -0.1575
-3.2280 -0.0640 -1.1513 0.8235
-0.6654 0.9402 0.0577 -0.0175
-3.2100 0.2762 -0.1053 0.0626
3.0793 -2.0043 0.2948 0.0411
1.3596 1.9481 -0.0167 0.3958
-3.1267 0.1801 0.2228 0.1179
-0.7979 0.9892 -0.2673 0.4734
2.5580 -1.7623 -0.1049 -0.0521
-0.9172 1.0621 -0.0826 0.1501
-0.7817 1.1658 0.1922 0.0803
3.1747 -2.1442 0.1472 -0.3411
2.8476 -1.8056 -0.0680 0.1536
-0.6175 1.4349 -0.1970 -0.1085
0.7308 1.9656 0.2602 0.2801
-1.0310 1.0553 -0.2928 -0.1647 -2.9251 -0.2095 0.0582 -0.1813
-0.9827 1.2720 -0.2225 0.2563
-1.0830 1.1158 -0.0405 -0.1181
-2.8744 0.0195 -0.3811 0.1455
3.1663 -1.9241 0.0455 0.1684
-1.0734 0.7681 -0.4725 -0.1976];
[n,d] = size(x);
bn=round(n/k*rand);%第一个随机数在前1/K的范围内
nc=[x(bn,:);x(2*bn,:);x(3*bn,:);x(4*bn,:)];%初始聚类中心
[cid,nr,centers] = kmeans(x,k,nc)%调用kmeans函数
for i=1:150,
if cid(i)==1,
plot(x(i,1),x(i,2),'r*') % 显示第一类
hold on
else
if cid(i)==2,
plot(x(i,1),x(i,2),'b*') %显示第二类
hold on
else
if cid(i)==3,
plot(x(i,1),x(i,2),'g*') %显示第三类
hold on
else
if cid(i)==4,
plot(x(i,1),x(i,2),'k*') %显示第四类
hold on
end
end
end
end
end
strt=['红色*为第一类；蓝色*为第二类；绿色*为第三类；黑色*为第四类' ];
text(-4,-3.6,strt);
（2）kmeans函数
kmeans函数同案例（一）
2.2.2 使用数据
（由于数据太多，就不在此表述，数据已经在程序中表述）
2.2.3 分类效果图及结果分析
（1）聚类过程
No points were moved after the initial clustering procedure.
cid = Columns 1 through 18
1 4 2 3 2 2 4 2 4 1 3 2 2 1
4 1 1 4
Columns 19 through 36
2 1 4 4 2 4 2 3 3 3 2 2 3 1
2 2 2 4
Columns 37 through 54
2 2 1 1 2 1 2 2 2 1 3 4 2 3
1 2 4 2
Columns 55 through 72
2 1 1 2 2 2 3 2 4 4 4 1 3 1
3 1 2 4
Columns 73 through 90
2 3 1 3 3 4 4 4 1 1 2 4 2 1
2 2 2 2
Columns 91 through 108
2 1 2 2 4 3 2 3 2 1 4 4 4 2
4 4 2 1
Columns 109 through 126
4 4 3 3 1 3 4 2 2 2 2 4 4 2
2 1 2 1
Columns 127 through 144
4 1 3 2 4 2 3 1 2 4 3 4 4 3
3 4 1 4
Columns 145 through 150
2 4 4 2 3 4
nr =
30 55 25 40
centers = 0.9952 1.9979 -0.0785 0.2296
-2.9629 -0.0230 -0.2970 0.3411
3.0234 -2.0986 0.1021 -0.0506
-0.9569 0.9978 -0.1237 0.0493
（2）分类效果图
图2 案例二效果图
（3）分类结果分析
k-means算法在本案例中主要是对遥感图像像元灰度值进行聚类分析，从而确定地物类型，最后根据像元灰度值的特定规律，结合地理学知识，对遥感图像进行解译。
综合遥感波段知识，可以得出：第一类红色的代表居民地，第二类蓝色代表植被，第三类绿色代表水体，第四类黑色的代表裸岩。 【参考文献】
[1] 陈晓春. 基于K-Means和EM算法的聚类分析[J].福建电脑，2009,2：79-80.
[2] 步媛媛，关忠仁. 基于K-means聚类算法的研究[J]. 西南民族大学学报，2009,35（1）：198-200.
[3] 陈寿文,李明东. 基于面向对象思想K-Means算法实现[J]. 滁州学院学报，2008,10（3）：42-44.
[4] 黄振华,向阳，张波，王栋，刘啸岭. 一种进行K-Means聚类的有效方法[J]. 模式识别与人工智能，2010,23（4）：516-521.
[5] 陈燕.数据挖掘技术与应用[M]. 北京:清华大学出版社,2011.
[6] 蒋盛益,李霞,郑琪.数据挖掘原理与实践[M]. 北京:电子工业出版社,2011.
[7] 邵峰晶,于忠清,王金龙，孙仁诚. 数据挖掘原理与算法[M]. 北京:科学出版社,2011.
发布评论