机器学习K-means

《机器学习K-means》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、机器学习报告非监督学习-----一些聚类算法聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术，聚类分析是指事先不了解一批样品中的每个样品的类别或者其他的先验知识，而唯一的分类依据是样品的特征，利用某种相似性度量的方法，把特征相同的或相近的分为一类，实现聚类分析。下面介绍五种聚类方法,每个算法的使用时有限的，不同的聚类酸腐蚀可以解决不同的问题。（一）K-means聚类K均值算法是一种常用的动态聚类算法，K均值算法能够使聚类集中所有样本到聚类中心的距离和最小。原理为：先选K个初始距离中心，计算每个样本到这K个中心的距离，找出最小距离把样本归入最近的聚类中心，然后对中心进行修改，得到

2、新的K个中心，再计算样本到K个中心的距离，重新归类，重新计算中心，修改中心。直到新的聚类中心等于聚类中心则结束。修改聚类中心的准则函数是：其中：是第个聚类；为第个聚类中心的样本数；为第个样本的聚类中心。K次平均算法的聚类准则是：聚类中心的选择应使准则函数的值最小。因此，令解上式得，其中上式表明，类得聚类中心应选为该类样本的均值。算法：Stept1:任选k个初始聚类中心Stept2:计算每个样本到k个聚类中心的距离，并按最近规则归类。若，则，其中：为聚类中心的样本聚类。在第k次迭代，分配各个样本X到k个聚类中心Stept3:从第二步的计算结果计算新的聚类中心。，其中上面应经证明，该聚类中

3、心可以使准则函数的值达到最小。Stept4;若新的聚类中心与前一个聚类中心相等，即则算法收敛，聚类结束。否则，转入第二步。K均值方法的特点：该算法的特点是运算结果受所选的聚类中心的数目，初始位置，模式样本的几何性质以及读入的次序的影响。在实际运用时，要试探选择不同的K值和起始聚类中心。如果模式样本为N个孤立的区域分布，则一般都能得到收敛结果。（二）Kmedoid方法Kmedoid方法同Kmeans方法类似，它们之间的差别就是Kmedoid方法中的最新的聚类中心是集合中的点到原来聚类中心的点最近距离的点，即：聚类中心都是集合中的点。Stept1:任选k个初始聚类中心Stept2:计算每个

4、样本到k个聚类中心的距离，并按最近规则归类。若，则，其中：为聚类中心的样本聚类。在第k次迭代，分配各个样本X到k个聚类中心Stept3：从第二步的计算结果计算新的聚类中心。，其中然后求解问题，得到的X定义为第J类得新的中心。即定义。Stept4：若新的聚类中心与前一个聚类中心相等，即则算法收敛，聚类结束。否则，转入第二步。通过算法过程可以发现，该算法与Kmeans方法除了第三步不同外，其他的过程都是相同的。下面给出Kmeans方法与Kmedoid方法对同一组数据的聚类结果。该图为Kmeans方法分为3类和4类得结果.可以发现该聚类中心并不是集合中本身的点。图为用Kmeans方法得到的3

5、类和4类的结果从图中可以看出，Kmedoid方法分类中，聚类中心点全是集合本身的点，且与Kmeans方法比较，聚类中心点近似的，且分类结果也差不多。注：Kmeans方法和Kmedoid方法对初始值要求比较敏感，且要求各类的密度差不多。（三)谱聚类为了能在任意形状的样本空间上聚类，且收敛于全局最优解，现研究利用谱方法来聚类。谱方法聚类是由数据点间相似关系建立矩阵，获取该矩阵的前n个特征向量，并且用它们来聚类不同的数据点。谱聚类方法建立在图论中的谱图理论上。谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G

6、(V,E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。针对这个问题，Shi和MalikEz提出了基于将图划分为两个子图的2-way目标函数Ncut：其中cut(A，B)是子图A，B间的边，又叫“边切集”。其中为连点之间定义的权重。我们可以看出改进后目标函数不仅满足类间样本间的相似度小，也满足类内样本间的相似度大。现令P是A的划分指示向量：其中为A中样本的个数，为B中样本的个数，为样本的总数。那么：问题可转化为：其中，且满足求该问题中的是离散的，为了解决该问题，我们将问题进行放松为连续的情况，转化为：S.t可得：由

7、L=D-W的性质，该问题的解为矩阵对应的第二最小特征值，取对应的特征向量。对应于第二最小特征值对应的特征向量X2则包含了图的划分信息。人们可以根据启发式规则在X2寻找划分点i，使得值大于等于X2i的划为A类，而小于X2i的划为B类。注：L=D-W称为Laplacian矩阵：Laplacian矩阵是对称半正定矩阵，因此它的所有特征值是实数且是非负的：如果G是c个连接部件，那么L有c个等于0的特征向量。如果G是连通的，第二个最小特征值不为0，则它是