K-means算法和KNN算法

github: 智能算法的课件和参考资料以及实验代码

K-means是最为常用的聚类算法，该算法是将相似的样本归置在一起的一种无监督算法。采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。

算法主要步骤可描述如下：

随机产生K个初始聚类中心。
计算测试点到聚类中心的距离，选择距离最近的聚类中心将测试点归类。
更新每类的聚类中心。
重复步骤2、3迭代更新，直至聚类中心不再改变，或者新的聚类中心与前一步聚类中心的距离小于某个值

KNN算法是最简单的分类算法，如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。算法主要步骤可描述如下：

1、计算已知类别数据集中的点与当前点之间的距离；

2、按照距离递增依次排序；

3、选取与当前点距离最小的k个点

4、确定k个点在所在类别的出现频率

5、返回k个点出现频率最高的类别作为当前点的预测分类

下面直接给出代码(matlab实现):

k-means算法:

clear all;close all; clc;
% 第一组数据
mul=[0,0]; % 均值
S1=[.1 0;0 .1]; % 协方差
data1=mvnrnd(mul, S1, 100); % 产生高斯分布数据
% 第二组数据
mu2=[1.25 1.25];
S2=[.1 0;0 .1];
data2=mvnrnd(mu2,S2,100);
% 第三组数据
mu3=[-1.25;1.25]
S3=[.1 0;0 .1]
data3=mvnrnd(mu3,S3,100)
% 显示数据
plot(data1(:,1),data1(:, 2),'b+');
hold on;
plot(data2(:,1),data2(:,2),'r+');
plot(data3(:,1),data3(:,2),'g+');
grid on; % 在画图的时候添加网格
% 三类数据合成一个不带标号的数据类
data=[data1;data2;data3];
N=3; % 设置聚类数目k的值
[m,n]=size(data); % 300x2矩阵
pattern=zeros(m,n+1);
center=zeros(N,n); % 初始化聚类中心 3x2
pattern(:,1:n)=data(:,:);
for x=1:N
	center(x,:)=data(randi(300,1),:); % 第一次随机产生聚类中心
end
while 1
	distance=zeros(1,N);
	num=zeros(1,N);
	new_center=zeros(N,n);
	for x=1:m
		for y=1:N 
			% 这里使用的是欧氏距离
			distance(y)=norm(data(x,:)-center(y,:)); % 计算每个样本到每个类中心的距离 
		end
		% min函数有三种调用形式 
		% min(A): 返回一个行向量，是每列最小值
		% [Y, U]=min(A): 返回行向量Y和U, Y向量记录A的每列的最小值，U向量记录每列最小值的行号
		% min(A, dim): dim取1或2.dim取1时，该函数与max(A)完全相同;dim为2时，返回列向量，其第
		% i个元素是A矩阵的第i行上的最小值
		[~,temp]=min(distance);
		pattern(x,n+1)=temp;
	end
	k=0;
	for y=1:N
		% 遍历所有样本，找到属于第y类的样本,并重新计算簇中心
		for x=1:m
			if pattern(x,n+1)==y
				new_center(y,:)=new_center(y,:)+pattern(x,1:n)
				num(y)=num(y)+1 % 计算第y类的所属样本个数，便于求均值
			end
		end
		new_center(y,:)=new_center(y,:)/num(y);
		if norm(new_center(y,:)-center(y,:))<0.1
			k=k+1
		end
	end
	if k==N
		break;
	else
		center=new_center
	end
end
[m,n]=size(pattern) % m=300,n=3

% 显示聚类后的数据
figure;
hold on;
for i=1:m
	% 属于不同类别的样本画成不一样的r、b、g颜色的*状，最终的簇中心为黑色圆圈
	if pattern(i,n)==1
		plot(pattern(i,1),pattern(i,2),'r*');
		plot(center(1,1),center(1,2),'ko');
	elseif pattern(i,n)==2
		plot(pattern(i,1),pattern(i,2),'g*');
		plot(center(2,1),center(2,2),'ko');
	elseif pattern(i,n)==3
		plot(pattern(i,1),pattern(i,2),'b*');
		plot(center(3,1),center(3,2),'ko');
	end
end 
grid on;

实验结果:

原始数据raw data 由于起始的簇中心选取很重要，因此性能也会变化，下面是不好的结果

K-means算法和KNN算法

良好的聚类结果:

K-means算法和KNN算法

下面给出了简单的分类算法KNN(用于分类的数据github下载):

clear all;close all;clc;
load data; % 读取数据
Data = data;
% ?100个样本进行归?化处? min-max标准化方法[0,1]区间
% 缺点是当有新的数据加入时，max和min可能发生变化，需要重新定?
for i=1:100 
	for j=1:3
		Data(i,j)=(data(i,j)-min(data(:,j)))/(max(data(:,j))-min(data(:,j)));
	end
end
D1=Data(1:80,:);
D2=Data(81:100,:);
k=20; % 训练集是80个样本，测试集是20个样?
for i=1:20
	temp=D2(i,1:3)
	for j=1:80 % 计算每个测试样本到训练样本的距离向量
		distance(j)=norm(temp-D1(j,1:3));
	end
	[distance1,index]=sort(distance); %升序排列
	In=index(1:k); % 统计周围20个训练样本的类别情况
	l1=length(find(D1(In,4)==1));
	l2=length(find(D1(In,4)==2));
	l3=length(find(D1(In,4)==3));
	[maxl,class(i)]=max([l1,l2,l3]); % class(i)是每个样本所属类别的20行向?
end
class
ratio=length(find((class'-D2(:,4))==0))/20 % 统计正确率是%90

可以看到分类效果不是很好，后面我们会利用PCA和异常数据监测来提高分类的性能。这里只是介绍最简单的算法

总结:

K-means缺点:

(1) K是事先给定的，K值的选定是非常难以估计的

(2) 对异常数据很敏感。在计算质心的过程中，如果某个数据很异常，在计算均值的

时候，会对结果影响非常大

KNN优缺点:

优点：

精度高，对异常值不敏感，无数据输入假定

缺点:

计算量大，样本不平衡时分类结果误差大

改进: 事先对样本进行剪辑，除去对分类作用不大的样本权值的方法(和该样本距离小的邻域权值大)

K-means算法和KNN算法

相关推荐