模式识别大作业二

k-means算法的应用。

一、问题描述。

用c-means算法对所给数据进行聚类，并已知类別数为2，随机初始样本聚类中心，进行10次求解，并计算聚类平均正确率。

二、算法简介。

1）在 1967 年提出的k-means算法[22]到目前为止用于科学和工业应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为聚类准则函数。

若是第聚类中的样本数目，是这些样本的均值，即。

把中的各样本y与均值间的误差平方和对所有的类相加后为。

是误差平方和聚类准则，它是样本集y和类别集的函数。度量了用c个聚类中心代表c个样本子集时所产生的总的误差平方。

2）k-means算法的工作原理：算法首先随机从数据集中选取 k个点作为初始聚类中心，然后计算各个样本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果相邻两次的聚类中心没有任何变化，说明样本调整结束，聚类准则函数已经收敛。

本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心也不会有任何变化，这标志着已经收敛，因此算法结束。

三、具体步骤。

1、数据初始化：类别数c=2，样本类标trueflag(n,1) （其中n为样本个数）;

2、初始聚类中心：用随机函数随机产生1~n中的2个数，选取随机数所对应的样本为初始聚类中心(mmnow)；

3、更新样本分类：计算每个样本到两类样本中心的距离，根据最小距离法则，样本将总是分到距离较近的类别；

4、更替聚类中心：根据上一步的分类，重新计算两个聚类中心（mmnext）；

5、判断终止条件：当样本聚类中心不再发生变化即mmnow==mmnext时，转5）；否则，更新mmnow，将mmnext附给mmnow，即mmnow=mmnext，转2）；

6、计算正确率：将dtat(i,1)与trueflag(i,1)（i=1~n）进行比较，统计正确分类的样本数，并计算正确率c_meanstrue(1,ii)。（ii=1~10）；

7、将上述过程循环10次，得到10次的正确率，并计算平均正确率**e。

四、实验数据。

表1 实验数据。

五、实验结果。

运用k-means算法，分别对每个文件的数据进行10次分类**。初始时在样本空间中随机取两个样本，之后记录每次**后各聚类中w1,w2所占的比例，填入下表。

表二实验结果。

由上表数据可得出结论：k-means算法在wdbc中能得到很理想的结果，然而在sanor中却不能有效地将w1，w2分类。

六、源**。

a = xlsread('c:\users\gaole\desktop\',a:bi');

a = a';

n = 208; %样本总数。

w = 60; %样本维数。

index = randperm(n);

index(1)

index(2)

m1 = a(1:w, index(1));

m2 = a(1:w, index(2));

n = 0; %循环次数。

je0 = 0; %上一次总误差平方和。

while(1)

y1 = zeros(w+1, 208);

num1 = 0;

y2 = zeros(w+1, 208);

num2 = 0;

for i=3:208

最近邻聚类 if(sqrt(dot((a(1:w,index(i))-m1),(a(1:w,index(i))-m1)))sqrt(dot((a(1:

w,index(i))-m2),(a(1:w,index(i))-m2)))

num1 = num1 + 1;

y1(:,num1) =a(:,index(i));

elsenum2 = num2 + 1;

y2(:,num2) =a(:,index(i));

endend

m1 = mean(y1(1:w, 1:num1), 2);

m2 = mean(y2(1:w, 1:num2), 2);

je1 = 0;

je2 = 0;

je = 0;

计算新聚类集的误差平方和。

for i=1:num1

je1 = je1 + dot((y1(1:w, i) -m1),(y1(1:w, i) -m1));

endfor i=1:num2

je2 = je2 + dot((y2(1:w, i) -m2), y2(1:w, i) -m2));

endn = n + 1;

je = je1 + je2;

je0 = abs(je - je0);

if n > 500

break;

endif je0 <0.0001

break;

elseje0 = je;

endend

c1 = 0;

c2 = 0;

for i=1:num1

if y1(w+1,i)==1

c1 = c1 + 1;

elsec2 = c2 + 1;

endend

disp('第一聚类中w1有：')

c1/num1

disp('第一聚类中w2有：')

c2/num1

c1 = 0;

c2 = 0;

for i=1:num2

if y2(w+1,i)==1

c1 = c1 + 1;

elsec2 = c2 + 1;

endend

disp('第二聚类中w1有：')

c1/num2

disp('第二聚类中w2有：')

c2/num2

b = dlmread('c:\users\gaole\desktop\')

b = b';

a = zeros(31,569);

a(1:30,:)b(3:32,:)

a(31, :b(2, :处理文件，调整矩阵a

n = 569; %样本总数。

w = 30; %样本维数。

index = randperm(n);

m1 = a(1:w, index(1));

m2 = a(1:w, index(2));

n = 0; %循环次数。

je0 = 0; %上一次总误差平方和。

while(1)

y1 = zeros(w+1, n);

num1 = 0;

y2 = zeros(w+1, n);

num2 = 0;

for i=3:n

if(sqrt(dot((a(1:w,index(i))-m1),(a(1:w,index(i))-m1)))sqrt(dot((a(1:

w,index(i))-m2),(a(1:w,index(i))-m2)))

num1 = num1 + 1;

y1(:,num1) =a(:,index(i));

elsenum2 = num2 + 1;

y2(:,num2) =a(:,index(i));

endend

m1 = mean(y1(1:w, 1:num1), 2);

m2 = mean(y2(1:w, 1:num2), 2);

je1 = 0;

je2 = 0;

je = 0;

for i=1:num1

je1 = je1 + dot((y1(1:w, i) -m1),(y1(1:w, i) -m1));

endfor i=1:num2

je2 = je2 + dot((y2(1:w, i) -m2), y2(1:w, i) -m2));

endn = n + 1;

je = je1 + je2;

je0 = abs(je - je0);

if n > 500

模式识别大作业 二

模式识别大作业 二

模式识别大作业

模式识别大作业

其他用户还读了

模式识别大作业二

模式识别大作业二