K-Means聚类-基于人脸数据实现.doc

数学与计算机学院 课程名称: 模式识别 题 目: K-Means聚类目 录 一 K-means聚类介绍 2 二 K-means算法描述 3 三 K-means算法matlab实现-基于人脸数据实现 7 1 数据读入 7 2 算法运行结果 8 四 K-means算法的总结和心得 9 五 附录——核心算法的主要源代码 10 参考文献 13 K-Means聚类 一 K-means聚类介绍 1967年,J.B.MacQueen提出了K-means算法,是一种基于质心的经典聚类算法。K-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。 k个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。算法过程如下： 1）从N个文档随机选取K个文档作为质心 2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类 3）重新计算已经得到的各个类的质心 4）迭代2～3步直至新的质心与原质心相等或小于指定阈值，算法结束 C个聚类有各聚类本身尽可能的紧凑而各聚类之间尽可能的分开的特点。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。对于以上的说法，首先要知道K的值，也就是说C是手动设置得到，至于如何选择质心，最简单的方式无异于，随机选取质心了，然后多次运行，选取效果最好的那个结果。这个方法简单但不见得有效，有很大的可能是得到局部最优。另一种复杂的方式时，随机选取一个质心，然后计算离这个质心最远的样本点，对于每个后继质心都选取以及选去过的最远点。使用这种方式，可以确保质心是随机的，并且是散开的。然后是如何定义最近的概念，对于欧式空间中的点，可以使用欧式空间，对于文档可以用余弦相似性等等，对于给定的数据，可能适应于多种合适的邻近性度量。至于其他问题，有离群点的处理。离群点可能过度影响簇的发现，导致簇的最终发布会于我们的预想有较大的出入，所以提前发现并剔除离群点是有不要的。还有簇分裂和簇合并，使用较大的C，往往会使得聚类的结果看上去更加合理，但很多情况下，我们并不想增加簇的个数。这时可以交替采用簇分裂和簇合并，这种方式可以避开局部极小，并且能够得到具有期望个数簇的结果。 二 K-means算法描述 K-means算法是一种很常用的聚类算法，其基本思想是，通过迭代寻找聚类的一种划分方案，使得用这聚类的均值来代表相应各类样本所得到总体误差最小。 从上图中，我们可以看到，A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。 然后，K-Means的算法如下： 随机在图中取K（这里K=2）个种子点。 然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点） 接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步） 然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。 这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法” ：原理： 基础是最小误差平方和准则。 i是第i聚类i中的样本数目，mi这些样本的均值，即 i中的个样本与均值mi的误差平方和对所有类相加后为 Je误差平方和聚类准则，它是样本集Y和类别集函数。Je了用聚类中心m1m2，···，mc样本子集1，Γ2，···，c时所产生总的误差平方。对于的聚类，Je值当然是不同的，使Je的聚类是误差平方和准则下的最优结果。这种的聚类通常称为最小方差划分。 ）误差平方和无法用解析的方法最小化，只能用迭代的方法，通过不断调整的类别归属来求解。 类别划分方法： 已经有一个划分方案，它把在类别k中。 考查下面的调整：如果把k类移到j类中则这两个类别发生变化，k类少了一个样本而，Γj类多了一个样本而，其余不影响。调整后，两类的均值分别变为 ，两类各自的误差平方和也分别变为 平方和的变化只取决于这两个变化。 ，移出一个样本会带来k类均方误差的减小，移入这个样本又会导致j类的均方误差增大。