k均值算法改进(k均值的算法流程)
00-1010之前,机器学习中引入了监督学习,利用离散回归和神经网络模型算法解决手写数字的识别问题。今天,我们介绍一种机器学习中的无监督学习算法,——K均值算法。
无监督学习是一种与有监督学习相反的算法分类,意味着样本没有对应的“标签”。比如上一期识别手写数码照片的例子,样本是照片的像素数据,标签是照片所代表的数字。无监督学习没有这个标签,所以对样本没有准确的“答案”。无监督学习主要用于解决样本的聚类问题。
K-means算法是一种迭代聚类分析算法,包括以下步骤:
随机选取k个对象作为初始聚类中心,计算每个对象与每个聚类中心的距离,将每个对象分配到最接近它的聚类中心,取同一聚类中对象的平均值作为新的聚类中心,从第二步开始循环,直到聚类中心不再变化。
K均值算法
代码实现
%的样本是随机排列的。randidx=randperm(size(X,1));
%取前k个随机样本作为聚类中心。
质心=X(randidx(1:K),);x为样本矩阵,每行为一个样本,每列为样本的维数,质心随机选取k个样本矩阵作为聚类中心。
00-1010%遍历所有样本
对于i=1:size(X,1)
距离=9999999999;
对于j=1:K
%距离公式:A(a1,a2)与B(b1,b2)的距离在偏旁下为(A1-B1) 2 (A2-B2) 2。
dist=sum((X(i,) -质心(j,))。^ 2);
if距离
idx(I)=j;
距离=dist
结束
结束时间
Endfor循环通过两层。第一层是遍历所有样本,找到每个样本所属的聚类中心。第二个循环是遍历所有的聚类中心,计算样本到聚类中心的距离,找出离聚类中心的最小距离,以聚类中心作为样本的聚类中心。
随机初始化
模式1:循环样本计数=0(K,1);对于i=1 : m
id=idx(I);
%累积聚类中心下的所有样本。
质心(id,)=质心(id,) X(i,);
计数(id)=计数(id)1;
结束时间
%意味着作为新的集群中心。
质心=质心。/count;方法二:循环聚类中心(效率更高)对于i=1:K
%直接通过均值函数计算均值。
质心(I,)=平均值(X(idx==i,),1);
End可以看出,matlab内置的均值函数可以更方便地计算出矩阵对应行的均值,计算过程会比累加法更高效。
分配聚类中心
如上图所示,有一些未标记的2D坐标点。通过一些基本的判断,我们可以把上面的数据大致分为左上、中右、左下三个聚类,但是中间位置的一些点可能划分得不好,如下图所示。
但是我们如何让机器对我们进行分类呢?机器如何决定这些中间点?那么让我们运行上面提到的书面的K-means算法。
如图,是运行K-means算法的第一步:随机初始化后聚类。我们可以看到图中绿色、蓝色和红色的分布,由于聚类中心是随机的,初始聚类中心不正确,所以我们继续运行K-means算法的下一步。
ps://p26.toutiaoimg.com/origin/pgc-image/a98403f9f33b47c69705c1aebd2b5687?from=pc">以绿色的聚类来举例,绿色的聚类通过一次均值计算之后,新的聚类中心点上升了许多。根据新的聚类中心点,再计算样本归属时,则会判断出下方的点已经不再属于绿色,而属于蓝色,因此就对之前的聚类进行了修正。
再看之前比较有疑问的绿色聚类与红色聚类之间的中间点(灰色框中所示),这几个点在感官上距离两个聚类都差不多,但根据与聚类中心点的计算对比,从数值上计算得出这几个点实际上属于红色聚类。
进行多次循环之后,聚类中心点不再变化,则说明K均值算法应用成功,分出了3个聚类并用不同颜色表示。
图片压缩
我们知道,图片是由许多像素点组成的,而每个像素点需要有RGB值。所谓RGB值是一种颜色标准,是通过对红(R)、绿(G)、蓝(B)三个颜色通道的变化以及它们相互之间的叠加来得到各式各样的颜色的。每个颜色的强度值是0-255,刚好是1个字节的大小。而3个颜色就是3个字节的大小,所以每个像素点所占大小为3字节,即24比特(故又称24位真彩色图,有1677万多色)。
以一张700*700像素的图为例,一共有490,000个像素点,每个像素点占24比特,合计11,760,000比特。如果能够应用K均值算法来实现图片的压缩呢?
压缩的前提数据有冗余,或者近似冗余。一张图片中数十万的像素点,肯定有许多像素点的RGB值是比较相似的,即图片中可能有某些位置都是同一个颜色。那么就可以应用K均值算法,将图片分成许多个聚类,用一张聚类表来存储每个聚类的颜色值,再用一张像素表来存储每个像素所在的聚类,就可以达到压缩的目的。
我选择了K=16,即有16个聚类,则原图片从1677万色变成了16色。聚类表占用的大小为16 * 24bit,即384比特。16个聚类是2的4次方只需要4个比特就可以存储聚类信息,则像素表的大小为490,000 * 4,即1,960,000。总大小为1,960,000+384=1,960,384比特,通过计算可得(压缩后大小/压缩前大小),压缩率为16.67%。即如果是100KB的图片,压缩后的大小只有16.67KB。
图片数据处理
% 调用imread读取图片 A = double(imread('test.png')); % 将像素值处理到0-1 A = A / 255; % 将数据从3维降到2维 img_size = size(A); X = reshape(A, img_size(1) * img_size(2), 3);获取聚类中心
% 随机初始化 initial_centroids = kMeansInitCentroids(X, K); % 调用之前写好的K均值算法 [centroids, idx] = runkMeans(X, initial_centroids, max_iters);压缩
% 调用之前写好的“分配聚类中心” idx = findClosestCentroids(X, centroids);解压缩
% 通过聚类表获取原始像素值 X_recovered = centroids(idx,:); % 将数据升至3维 X_recovered = reshape(X_recovered, img_size(1), img_size(2), 3);压缩效果展示
可以看到,压缩后的图片仍然具有较清晰的轮廓,只是色彩没有那么丰富(只有16种颜色),某些细节有一些失真,但是不影响图片的整体表达。