K均值算法
之前介绍了机器学习中的监督式学习，并用了离散回归与神经网络模型算法来处理手写数字的辨认问题。今日咱们介绍一种机器学习中的非监督式学习算法——K均值算法。
所谓非监督式学习，是一种与监督式学习相对的算法归类，是指样本并没有一个与之对应的“标签”。例如上一期中的辨认手写数字相片的比如，样本是相片的像素数据，而标签则是相片代表的数字。非监督式学习由于没有这个标签，因而就没有对样本的一个精确的“答案”。非监督式学习主要是用来处理样本的聚类问题。
K均值算法是一种迭代求解的聚类分析算法，其进程为：
随机选取K个目标作为初始的聚类中心核算每个目标与各个聚类中心之间的间隔把每个目标分配给间隔它最近的聚类中心将同一聚类中的目标的平均值作为新的聚类中心从第2步开端循环，直到聚类中心不再改变代码完成随机初始化
%样本随机摆放\nrandidx=randperm(size(X,1));\n%取前K个随机样本作为聚类中心\ncentroids=X(randidx(1:K),:);
其间X为样本矩阵，每一行为一个样本，每一列为样本的维度，centroids便是随机出的K个作为聚类中心的样本矩阵。
分配聚类中心
%遍历一切样本\nfori=1:size(X,1)\ndistance=9999999999;\nforj=1:K\n%间隔公式：A(a1,a2)与B(b1,b2)之间的间隔为根号下(a1-b1)^2+(a2-b2)^2\ndist=sum((X(i,:)-centroids(j,:)).^2);\nifdist<distance\nidx(i)=j;\ndistance=dist;\nend\nendfor\nendfor
经过两层循环，第一层为遍历一切样本，找到每个样本所属的聚类中心。第二层循环为遍历一切聚类中心，核算样本与聚类中心的间隔，找出与类聚中心最小的间隔，将该类聚中心作为样本的类聚中心。
更新聚类中心方法一：循环样本
count=zeros(K,1);\nfori=1:m\nid=idx(i);\n%累加该聚类中心下的一切样本\ncentroids(id,:)=centroids(id,:)+X(i,:);\ncount(id)=count(id)+1;\nendfor\n%均值作为新的聚类中心\ncentroids=centroids./count;
方法二：循环类聚中心（功率更高）
fori=1:K\n%直接经过mean函数核算均值\ncentroids(i,:)=mean(X(idx==i,:),1);\nend
能够看到，经过matlab内置的mean函数，能够愈加快捷的核算出矩阵对应行的均值，而且核算进程也会比累加的方法履行愈加高效。
进程演示
如上图所示，有一些无标签的二维坐标点。经过一些根本的判别，咱们大致能够将上述的数据分为左上、中右部、左下三个聚类，可是有些中心方位的点或许不太好区分，如下图所示。
可是怎么才能让机器为咱们做出分类呢？机器又怎么决议计划这些处于中心方位的点呢？所以咱们来运转上述现已写好的K均值算法。
如图所示，是运转了K均值算法的第一步：随机初始化后的聚类。能够看到图中的绿色、蓝色、赤色散布，由于聚类中心点是随机的，初始的聚类中心并不正确，所以咱们持续运转K均值算法的投掷进程。
以绿色的聚类来举例，绿色的聚类经过一次均值核算之后，新的聚类中心点上升了许多。依据新的聚类中心点，再核算样本归属时，则会判别出下方的点现已不再归于绿色，而归于蓝色，因而就对之前的聚类进行了批改。
再看之前比较有疑问的绿色聚类与赤色聚类之间的中心点（灰色框中所示），这几个点在感官上间隔两个聚类都差不多，但依据与聚类中心点的核算比照，从数值上核算得出这几个点实际上归于赤色聚类。
进行屡次循环之后，聚类中心点不再改变，则阐明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读取图片\nA=double(imread('test.png'));\n%将像素值处理到0-1\nA=A/255;\n%将数据从3维降到2维\nimg_size=size(A);\nX=reshape(A,img_size(1)*img_size(2),3);
获取聚类中心
%随机初始化\ninitial_centroids=kMeansInitCentroids(X,K);\n%调用之前写好的K均值算法\n[centroids,idx]=runkMeans(X,initial_centroids,max_iters);
紧缩
%调用之前写好的“分配聚类中心”\nidx=findClosestCentroids(X,centroids);
解紧缩
%经过聚类表获取原始像素值\nX_recovered=centroids(idx,:);\n%将数据升至3维\nX_recovered=reshape(X_recovered,img_size(1),img_size(2),3);
紧缩作用展现
能够看到，紧缩后的图片依然具有较明晰的概括，仅仅颜色没有那么丰厚（只要16种颜色），某些细节有一些失真，可是不影响图片的全体表达。
总结K均值算法是最常用也是最简略的非监督式学习聚类算法第一步的随机聚类中心对聚类成果有必定影响，因而能够运转屡次以到达比较好的聚类成果将聚类算法的思维作用在图片上，能够到达图片紧缩的意图。假如想要有更好的图片质量，能够进步聚类数量K，但这样会得到较差的紧缩率，需求在实践中以平衡。
