K-means方法是一种非监督学习的算法，它解决的是聚类问题。
1、算法简介：K-means方法是聚类中的经典算法，数据挖掘十大经典算法之一；算法接受参数k,然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足聚类中的对象相似度较高，而不同聚类中的对象相似度较小。
2、算法思想：以空间中k个点为中心进行聚类，对最靠近他们的对象归类，通过迭代的方法，逐次更新各聚类中心的值，直到得到最好的聚类结果。
3、算法描述：
（1）适当选择c个类的初始中心；
（2）在第k次迭代中，对任意一个样本，求其到c各中心的距离，将该样本归到距离最短的那个中心所在的类；
（3）利用均值等方法更新该类的中心值；
（4）对于所有的C个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束；否则继续迭代。
4、算法举例：
我们假设药物A、B、C、D有两个特征值，分别是药物重量以及PH值。
首先我们把上面的数据画到二位坐标系当中A(1,1),B(2,1),C(4,3),D(5,4)A(1,1),B(2,1),C(4,3),D(5,4)：
初始时，我们先假设药物A为聚类1的中心点，B为聚类2的中心点，那么初始时的中心坐标分别为c1=(1,1),c2=(2,1)c1=(1,1),c2=(2,1)，矩阵D的第一行代表各个点到中心点c1c1的距离，第二行代表各个点到中心点c2c2的距离；那么初始矩阵D0D0表示成如下：
D0=[01103.612.8354.24]D0=[013.615102.834.24]
矩阵GG代表样本应该归属于哪个聚类，第一行代表各个点是否属于中心c1c1所在的类（0代表不在，1代表在），第二行代表各个点是否属于中心c2c2所在的类（0代表不在，1代表在）；那么此时G0G0表示成如下：
G0=[10010101]G0=[10000111]
由矩阵G0G0可知A药物属于一个类，B、C、D属于一类；
然后，利用均值等方法更新该类的中心值。
c1=（1,1）c1=（1,1）
c2=（2+4+53,1+3+43）=(133,83)
上图是更新后的坐标图，对应的中心点也发生了变化。
因为中心点跟上次不一样了，所以我们又可以对样本点进行重新划分。划分的方法还是跟以前一模一样，我们先计算出矩阵D1D1表示成如下：
D1=[03.1412.363.610.4751.89]D1=[013.6153.142.360.471.89]
此时G1G1表示成如下：
G1=[10100101]G1=[11000011]
由矩阵G1G1可知A、B药物属于一个类，C、D属于一类；
然后，利用均值等方法再次更新该类的中心值。
c1=（1+22,1+12）=(1.5,1)c1=（1+22,1+12）=(1.5,1)
c2=（4+52,3+42）=(4.5,3.5)c2=（4+52,3+42）=(4.5,3.5)
上图是更新后的坐标图，对应的中心点也发生了变化。
因为中心点跟上次不一样了，所以我们又可以对样本点进行重新划分。划分的方法还是跟以前一模一样，我们先计算出矩阵D2D2表示成如下：
D2=[0.54.300.53.543.200.714.610.71]D2=[0.50.53.204.614.303.540.710.71]
此时G2G2表示成如下：
G2=[10100101]G2=[11000011]
由矩阵G2G2可知A、B药物属于一个类，C、D属于一类；
然后，利用均值等方法再次更新该类的中心值。
c1=（1+22,1+12）=(1.5,1)c1=（1+22,1+12）=(1.5,1)
c2=（4+52,3+42）=(4.5,3.5)c2=（4+52,3+42）=(4.5,3.5)
因为对应的中心点并没有发生变化，所以迭代停止，计算完毕。
本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。
适用范围：
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
缺点：
1、聚类中心的个数K 需要事先给定，但在实际中这个 K 值的选定是非常难以估计的，很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；
2、Kmeans需要人为地确定初始聚类中心，不同的初始聚类中心可能导致完全不同的聚类结果。（可以使用K-means++算法来解决）
K-means、和KNN算法比较
KNN(K-Nearest Neighbor)介绍
算法思路：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
看下面这幅图：
KNN的算法过程是是这样的：
从上图中我们可以看到，图中的数据集是良好的数据，即都打好了label，一类是蓝色的正方形，一类是红色的三角形，那个绿色的圆形是我们待分类的数据。
如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形
如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形
我们可以看到，KNN本质是基于一种数据统计的方法！其实很多机器学习算法也是基于数据统计的。
KNN是一种memory-based learning，也叫instance-based learning，属于lazy learning。即它没有明显的前期训练过程，而是程序开始运行时，把数据集加载到内存后，不需要进行训练，就可以开始分类了。
具体是每次来一个未知的样本点，就在附近找K个最近的点进行投票。
KNN和K-Means的区别
网友评论