对 中国达人秀 走红的分析与思考.docx

对K-means算法初始聚类中心选取的优化
中南林业科技大学计算机与信息工程学院 薛京花 刘震宇 崔适时
【摘要】针对传统K-means算法对初始聚类中心选取的问题,提出了基于数据样本密度和距离来选取初始聚类中心的改进
K-means算法,该算法保证了初始中心点集的第一点为确定的(最大密度点),在基于距离最远的其他中心点搜索过程中,得到的中心点也基本上是确定的,消除了初始中心点选择的随机性,同时保证了获得较高质量的初始中心点。理论分析和实验结果表明:改进的k-means算法是一种有效的入侵检测方法,根据此方法设计的入侵检测系统是有效可行的。
【关键词】K-means算法;初始聚类中心;入侵检测
类间有干扰点的情况。
新的初始聚类中心选取方法直观上,类中心应处于所代表
类的中心部分,所有属于该类的样本都在其周围某一邻域内。因而在空间上,类中心所处的位置样本点分布密度较大。同时,在样本点密度连续的范围内,应该只具有一个聚类中心,否则就会出现两个类交错在一起的情况。因此,初始类中心的选择应该满足两个条件:
①类中心所处位置样本点密度较高;
②类中心之间的距离应尽可能地大。
因此,在初始点的选择上,应考虑两个因素:密度因素和聚类因素。由于类中心所处位置总是在样本比较密集的地方,因而总是存在某些样本距离类中心比较近。如果能够找到这些样本并作为初始类中心,就能避免k-means算法因为初始化不合理而出现的种种问题。
①样本点密度的度量
对于一个数据集,当样本呈团状分布时,根据一般常识,某个样本点周围其它样本点越多时,则该样本点处的样本分布密度就越大, 则该样本点对于分类的影响就越

聚类分析是源于许多研究领域, 包括数据挖掘,统计学,生物学, 以及机器学习[1]。设想要求对一个数据对象的集合进行分析,但与分类不同的是,它要求划分的类是未知的。那么我们就需要聚类分析中的基于多种不同思想的聚类算法, 主要有基于划分的算法、基于层次的算法、基于密度的算法、基于网络的算法和基于模型的算法等。这些算法都能取得不错的聚类效果, 其中应用最多且算法逻辑思维比较简单的就是基于K-means算法。
1967年, K-means算法,是一种基于质心的经典聚类算法。K-means算法以k为参数,把n个对象分为k个簇,以使簇内具有较高的相似度,而簇间的相似度较低。相似度的计算根据一个簇中对象的平均值(被看作簇的重心)来进行。K-means算法的处理流程如下:首先,随机地选择k个对象,每个对象初始地代表了一个簇的平均值或中心。对剩余的每个对象,根据其与各个簇中心的距离, 将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。
-means算法的改进
无论是原始K-means算法还是使用了聚类准则函数的K-means算法, 他们有一个共同的特点:在算法的初始阶段都需要随机的选取k个点作为初始聚类中心点,然后在此基础上进行迭代。
k-means算法初值选取的现有方法
针对初值选取的问题,目前主要有以下几种选取方法[3][4]:
①任意的选取k个样本数据作为初始聚类中心。
②把全部混合样本直观地分成k
类,计算各类均值作为初始聚类中心。
③依据经验选取有代表性的