模式识别大作业-k近邻

题目

对sonar和wdbc中数据(如表1所示)进行分类，并将实验结果填入表中。

表1 实验数据 类别数 特征维数 样本个数 w1=357 wdbc 2 30 w2=212 w1=98 sonar 2 60 w2=110 解：

实验结果

Sonar Wdbc

准确率 0.5569 0.8514

K-Means聚类算法

一.算法思想

K-均值算法的主要思想是先在需要分类的数据中寻找K组数据作为初始聚类中心，然后计算其他数据距离这三个聚类中心的距离，将数据归入与其距离最近的聚类中心，之后再对这K个聚类的数据计算均值，作为新的聚类中心，继续以上步骤，直到新的聚类中心与上一次的聚类中心值相等时结束算法。

在本次算法实现中，选择在两类样本点中随机选择两个点作为两类数据的初始聚类中心，然后在开始迭代，计算，直至找到最优分类。

二.算法流程图

开始 读入要分类的数据 设置初始聚类中心

三.程序运行结果

计算数据到K个聚类中心的距离 将数据分入与其距离最小的聚类 计算新的聚类中心 聚类中心是否收否 敛？ 是 输出K个分好的聚类 结束

1、对sonar数据进行k均值聚类

表一：sonar（Kmeans）

运行次数 准确率

1 0.5913

2 0.6030

3 0.5048

4 0.5817

5 0.4904 6 0.5192

7 0.6731 8 0.5721

9 0.5096 10 0.5240 平均准确率 0.5569

程序迭代次数：6

得到第一类聚类中心是

（0.0325 0.0443 0.0469 0.0585 0.0717 0.0983 0.1162 0.1306 0.1742 0.1990 0.2179 0.2389 0.2562 0.2737 0.2965 0.3458 0.3568 0.3937 0.4486 0.5130 0.5266 0.4825 0.4894 0.5234 0.5312 0.5745 0.5790 0.6056 0.5951 0.5803 0.5220 0.4791 0.5020 0.5387 0.5508 0.5327 0.4823 0.4541 0.4271 0.3914 0.2724 0.2381 0.2208 0.1799 0.1263 0.0908 0.0525 0.0223 0.0161 0.0144 0.0118 0.0118 0.0091 0.0089 0.0094 0.0073）

得到第二类聚类中心是

（0.0264 0.0336 0.0413 0.0501 0.0781 0.1097 0.1263 0.1383 0.1811 0.2159 0.2510 0.2596 0.2874 0.3155 0.3397 0.4055 0.4647 0.5007 0.5511 0.7411 0.7769 0.7957 0.7943 0.8032 0.8037 0.7669 0.6808 0.5814 0.4900 0.4060 0.3473 0.2916 0.2621 0.2630 0.2661 0.2453 0.2422 0.2450 0.2252 0.1943 0.1778 0.1447 0.1193 0.0919 0.0514

0.0107 0.6043 0.0091 0.6771 0.3547 0.3225 0.2353 0.2418 0.0189 0.0160 0.0126 0.0098 0.0102 0.0081 0.0075 0.0068 0.0072 0.0067 0.0058）

2、对wdbc数据进行k均值聚类

表二：wdbc（Kmeans）

运行次数 准确率

1 0.8514

2 0.8514

3 0.8514

运行了几次程序，发现准确率一直保持不变，分析可能是由于两类数据比较集中而类间距离又足够大导致，随机选择的样本点对数据分类没有产生什么影响。

程序迭代次数：11

得到的第一类聚类中心是： 1.0e+003 *

（0.0194 0.0217 0.1282 1.1859 0.0001 0.0001 0.0002 0.0001 0.0002 0.0001 0.0007 0.0012 0.0053 0.0957 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0237 0.0289 0.1585 1.7530 0.0001 0.0004 0.0004 0.0002 0.0003 0.0001 ）

得到的第二类聚类中心是： 1.0e+003 *

（0.0126 0.0186 0.0811 0.4961 0.0001 0.0001 0.0001 0.0000 0.0002 0.0001 0.0003 0.0012 0.0022 0.0238 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0140 0.0247 0.0919 0.6196 0.0001 0.0002 0.0002 0.0001 0.0003 0.0001）

四.实验总结

用k均值聚类方法对sonar和wdbc的识别率分别是0.5569和0.8514。主要原因可能是sonar数据中两类数据类间不够分离，类内距离不够紧密，而wdbc数据中两类数据的点类内相对集中，类间足够分离。

用k均值聚类对wdbc数据识别率较高。

经过几个晚上的艰苦奋斗，努力学习，不断请教前辈大神和上网查询，不断

调试程序，最终才得以成功运行，我对这几种判别方法有了更深层次的认识，同时对matlab这个强大的数值计算软件应用的也更加熟练，山重水复疑无路，柳暗花明又一村，自己的能力也就是在不断的发现错误，改正错误中得到了提升。

五.程序代码及分析

1、对sonar数据进行k均值聚类代码及分析 function km k=2;

da=xlsread('C:\\Users\\lisai\\Desktop\\sonar');%½«Êý¾Ý´æÈëµ½daÖÐ s=0;%sÓÃÀ´±£´æÁ½ÀàÊý¾Ý¸öÊý for c=1:208 if da(c,61)==1 s=s+1; B(s)=c; end end

D=da(B,:);%½«1ÀàÊý¾Ý´æÈëµ½DÖÐ out=randperm(s)'; data=out(1);

x1=D(data,1:60); %Ëæ»ú´Ó1ÀàÊý¾ÝÖÐÑ¡È¡1¸öÑù±¾ cid(1,:)=x1; cid(1,31)=0;

s=0;%sÓÃÀ´±£´æÁ½ÀàÊý¾Ý¸öÊý for c=1:208 if da(c,61)==2 s=s+1; B(s)=c; end end

D=da(B,:);%½«2ÀàÊý¾Ý´æÈëµ½DÖÐ out=randperm(s)'; data=out(1);

x2=D(data,1:60); %Ëæ»ú´Ó2ÀàÊý¾ÝÖÐÑ¡1¸öÑù±¾ cid(2,1:60)=x2; cid(2,61)=0; A=da(:,1:60);

[n,p]=size(A);%ÊäÈëÊý¾ÝÓÐn¸öÑù±¾£¬p¸öÊôÐÔ A(:,p+1)=0; Asum=0; Csum2=NaN; flags=1;

while flags flags=0;

%¼ÆËãÿ¸öÏòÁ¿µ½¾ÛÀàÖÐÐĵÄÅ·ÊϾàÀë for i=1:n for j=1:k

dist(i,j)=sqrt(sum((A(i,:)-cid(j,:)).^2));%Å·ÊϾàÀë end

%A(i,p+1)=min(dist(i,:));%ÓëÖÐÐĵÄ×îС¾àÀë [x,y]=find(dist(i,:)==min(dist(i,:))); [c,d]=size(find(y==A(i,p+1))); if c==0 %˵Ã÷¾ÛÀàÖÐÐıäÁË flags=flags+1; A(i,p+1)=y(1,1); else continue; end end i; flags; for j=1:k Asum=0;

[r,c]=find(A(:,p+1)==j); cid(j,:)=mean(A(r,:),1); for m=1:length(r)

Asum=Asum+sqrt(sum((A(r(m),:)-cid(j,:)).^2)); end

Csum(1,j)=Asum; end

sum(Csum(1,:)); Csum2=sum(Csum(1,:)); Csum;

cid; %µÃµ½ÐµľÛÀàÖÐÐÄ end B=A; B; right=0; sort1=0; sort2=0; for ii=1:208 if B(ii,61)==1 sort1=sort1+1; end end sort1;

for ii=1:208 if B(ii,61)==2 sort2=sort2+1; end end sort2; for ii=1:208

if B(ii,61)==da(ii,61) right=right+1; end end

acc=right/208 cid

2、对wdbc数据进行k均值聚类代码及分析 function km2

da1=importdata('C:\\Users\\lisai\\Desktop\\wdbc.txt');%½«Êý¾Ý´æÈëµ½daÖÐ da=da1.data; %½«Êý¾ÝÓò´æÈëµ½AÖÐ k=2;

for jj=1:569 str1='M';

str2=da1.textdata(jj,2); if strcmp(str2,str1)==1 da(jj,31)=1; else

da(jj,31)=2; end end

s=0;%kÓÃÀ´±£´æÁ½ÀàÊý¾Ý¸öÊý for c=1:569 if da(c,31)==1 s=s+1; B(s)=c; end end

D=da(B,:);%½«1ÀàÊý¾Ý´æÈëµ½DÖÐ out=randperm(s)'; data=out(1);

x1=D(data,1:30); %Ëæ»ú´Ó1ÀàÊý¾ÝÖÐÑ¡È¡50¸öÑù±¾ cid(1,:)=x1; cid(1,31)=0;

s=0;%kÓÃÀ´±£´æÁ½ÀàÊý¾Ý¸öÊý for c=1:569 if da(c,31)==2

s=s+1; B(s)=c; end end

D=da(B,:);%½«1ÀàÊý¾Ý´æÈëµ½DÖÐ out=randperm(s)'; data=out(1);

x2=D(data,1:30); %Ëæ»ú´Ó1ÀàÊý¾ÝÖÐÑ¡È¡50¸öÑù±¾ cid(2,1:30)=x2; cid(2,31)=0; A=da(:,1:30);

[n,p]=size(A);%ÊäÈëÊý¾ÝÓÐn¸öÑù±¾£¬p¸öÊôÐÔ A(:,p+1)=0; Asum=0; Csum2=NaN; flags=1; while flags flags=0;

%¼ÆËãÿ¸öÏòÁ¿µ½¾ÛÀàÖÐÐĵÄÅ·ÊϾàÀë for i=1:n for j=1:k

dist(i,j)=sqrt(sum((A(i,:)-cid(j,:)).^2));%Å·ÊϾàÀë end

%A(i,p+1)=min(dist(i,:));%ÓëÖÐÐĵÄ×îС¾àÀë [x,y]=find(dist(i,:)==min(dist(i,:))); [c,d]=size(find(y==A(i,p+1))); if c==0 %˵Ã÷¾ÛÀàÖÐÐıäÁË flags=flags+1; A(i,p+1)=y(1,1); else continue; end end i; flags; for j=1:k Asum=0;

[r,c]=find(A(:,p+1)==j); cid(j,:)=mean(A(r,:),1); for m=1:length(r)

Asum=Asum+sqrt(sum((A(r(m),:)-cid(j,:)).^2)); end

Csum(1,j)=Asum; end

sum(Csum(1,:));

%if sum(Csum(1,:))>Csum2 % break; %end

Csum2=sum(Csum(1,:)); Csum;

cid; %µÃµ½ÐµľÛÀàÖÐÐÄ end B=A; B; right=0; sort1=0; sort2=0; for ii=1:569 if B(ii,31)==1 sort1=sort1+1; end end sort1; for ii=1:569 if B(ii,31)==2 sort2=sort2+1; end end sort2; for ii=1:569

if B(ii,31)==da(ii,31) right=right+1; end end

acc=right/569; cid