聚类分析K-means算法综述.doc

聚类分析K-means算法综述摘要:介绍K-means聚类算法的概念,初步了解算法的基本步骤,通过对算法缺点的分析,对算法已有的优化方法进行简单分析,以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。关键词:K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势算法概述K-means聚类算法是一种基于质心的划分方法,输入聚类个数k,以及包含n个数据对象的数据库,输出满足方差最小标准的k个聚类。评定标准:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算。解释:基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心,然后根据一个数据对象与簇质心的距离,再将该对象赋予最近的簇。k-means算法基本步骤(1)从n个数据对象任意选择k个对象作为初始聚类中心(2)根据每个聚类对象的均值(中心对象),计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分(3)重新计算每个(有变化)聚类的均值(中心对象)(4)计算标准测度函数,当满足一定条件,如函数收敛时,则算法终止;如果条件不满足则回到步骤(2)形式化描述输入:数据集D,划分簇的个数k输出:k个簇的集合(1)从数据集D中任意选择k个对象作为初始簇的中心;(2)Repeat(3)For数据集D中每个对象Pdo(4)计算对象P到k个簇中心的距离(5)将对象P指派到与其最近(距离最短)的簇;(6)EndFor(7)计算每个簇中对象的均值,作为新的簇的中心;(8)Untilk个簇的簇中心不再发生变化对算法已有优化方法的分析(1)K-means算法中聚类个数K需要预先给定这个K值的选定是非常难以估计的,很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适,这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k,例如Is0DAIA算法"关于K一means算法中聚类数目K值的确定,在文献中,根据了方差分析理论,应用混合F统计量来确定最佳分类数,并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中,使用了一种结合全协方差矩阵RPCL算法,并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标:V(kkm)=Intra(k)+Inter(k)/Inter(kmax),其中kmax是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是:对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值,而且对次胜单元采用惩罚的方法使之远离输入值。(2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解不同的初始值,结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子,再利用迭代的重定位技术直到算法收敛。因此,初值的不同可能导致算法聚类效果的不稳定,并且,K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值,只有一个属于全局最小,由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围,因此通过迭代运算,目标