k-means聚类算法的研究

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

??il?cjil|Cj|

12) Until E不再明显地改变或者聚类的成员不再变化 1.2.3 相关定义

（1）两个数据对象间的距离： ①明氏距离（Minkowski Distance）

d(xi,xj)?(?|xik-xjk|q)1/q （公式1）

k?1p这里的xi=( xi1，xi2，…，xip)和xj=( xj1，xj2，…，xjp)是两个p维的数据对象并且 i≠j。 ②欧式距离（Euclidean Distance）

当明氏距离中q=2时，公式1即欧式距离。

d(xi,xj)?(?|xik-xjk|2)1/2 （公式2）

k?1p③马氏距离（Mahalanobis Distance）

??(?ij)p?p （公式3）

1n(xki-xi)(xkj-xj)，i，j=1，2…，p。如果∑-1存在，则马氏距离为 其中?ij??n-1k?1

2dM(xi,xj)?(xi,xj)T??1(xi,xj) （公式4）

④兰式距离（Canberra Distance）：

1p|xik-xjk|dL(xi,xj)?? （公式5）

pk?1xik?xjk（2）准则函数E

对于K-means算法，通常使用准则函数E，也就是误差平方和（Sum of Squared Error，SSE）作为度量聚类质量的目标函数。

E???d2(Ci,x) （公式6）

i?1x?Cik其中，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函数如下:

osicKMeans.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

本文来源：https://www.bwwdw.com/article/oxm6.html