kmeans 聚类算法实现程序.txt

KMEANS聚类算法实现程序

%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);






















%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