K-means实验报告

《K-means实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、人工智能大作业目录1.问题描述22.设计要求23.需求分析34.详细设计35.测试及运行结果46.程序源码及注释57.课程设计心得体会1514人工智能大作业1.问题描述k-means算法是根据聚类中的均值进行聚类划分的聚类算法。输入：聚类个数k，以及包含n个数据对象的数据。输出：满足方差最小标准的k个聚类。处理流程：Step1.从n个数据对象任意选择k个对象作为初始聚类中心；Step2.循环Step3到Step4直到每个聚类不再发生变化为止；Step3.根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并

2、根据最小距离重新对相应对象进行划分；Step4.重新计算每个（有变化）聚类的均值（中心对象）k-means算法的工作过程说明如下：首先从n个数据对象任意选择k个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：(1)其中E为数据库中所有对象的均方差之和，p为代表对象的空间中的一个

3、点，mi为聚类Ci的均值(p和mi均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。2.设计要求首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。14人工智能大作业输入：聚类个数k，以及包含n个数据对象的数据库。输出：满足方差

4、最小标准的k个聚类3.需求分析K-Mean是一种分割式分群方法，其主要目标是要在大量高纬的资料点中找出具有代表性的资料点；这些资料点可以称为群中心，代表点；然后再根据这些群中心，进行后续的处理，这些处理可以包含1）资料压缩：以少数的资料点来代表大量的资料，达到资料压缩的功能；2）资料分类：以少数代表点来代表特点类别的资料，可以降低资料量及计算量；分割式分群法的目的是希望尽量減小每个群聚中，每一点与群中心的距离平方差（squareerror）。假設我们現在有一組包含c个群聚的資料，其中第k个群聚可以用集合Gk來表示，假设Gk包

5、含nk个資料{x1,x2,…,xnk），此群聚中心为yk，则该群聚的平方差ek可以定义为：ek=Si

6、xi-yk

7、2，其中xi是属于第k群的资料点。而这c个群聚的总和平方差E便是每个群聚的平方差总和：E=Sk=1~cek我们分群的方法，就改成是一个最佳化的問題，換句话說，我們要如何选取c个群聚以及相关的群中心，使得E的值为最小。4.详细设计k-means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此算法以k为参数，把n个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个

8、簇中对象的平均值（被看作簇的重心）来进行。此算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。k-means算法是一种较典型的逐点修改迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类中心：一个象元样本按某一原则，归属于某一组类后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一次象元素聚类；逐批修改类中心：在14人工智能大作业全部象元样本按某一组的

9、类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。k-means算法把N个点聚集成K个组合的算法，要求任意输入K各对象作为初始中心点，这个的最大疑问就是怎么能够通过这随便选择的K个点来达到满足要求的K个组合呢。K-means算法其实每次迭代都会改变中心，也就是初始的K各对象作为中心点

10、在每一次迭代后都会更新。首先以这K各顶点作为初始K个聚类的中心顶点，第一轮计算所有的其他顶点与这个K个顶点的相似度，取相似度最大的或者说与这K个顶点中某个顶点距离最近的顶点加入这个顶点所代表的cluster中，注意在第一轮检测所有顶点的距离并判断其属于哪个簇的过程中，这K各簇的中心仍然是以