改进的K-means算法
针对经典的K-means算法的一些缺点,许多学者在原K-means的基础上提出了一些改进的方法。大体集中在距离的计算,初始点簇中心的优化选择等方面。
由于典型的K-means算法中,初始点簇中心的选择是随机的。算法的在选取随机的初始聚类中心时,可能会得到一个次最优聚类,具有较高的平方误差。解决方法之一是采用多次运算,每次使用一组不同的随机初始中心,然后选取具有最小总误差平方和的簇集[10]。
好的初始中心的选择,能够极大的减少算法所需时间,减少聚类结果的误差总和。优化初始中心的选择成为重要的研究点。总体来说,笔者将优化选择总结为两个研究方向,其一是直接对所有点簇进行处理,其二是先取样分析,通过各种对样本的分析方法得到初始点簇中心。
A、直接对所有点簇进行处理
这种方法的缺陷是很明显的,在空间数据量较小的情况下,它确实能够快速的完成初始聚类中心的优化,但是在数据量较大的情况下,运算量会成倍数增加。
《一种改进的K-means聚类算法》一文中,研究了优化K-means算法中优化初始的聚类中心。为了找到与数据在空间分布上相一致且相似程度较大的数据集合,采取下列步骤:
(1) 计算数据对象两两之间的距离;
(2) 找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;
(3) 计算A1 中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1 中最近的数据对象,将它并入集合A1 并从U 中删除,直到A1 中的数据对象个数到达一定阈值;
(4) 再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;
(5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。
B、通过处理采样样本优化初始聚类中心
采用这种方法,样本的采集非常重要,样本的代表性越充分,聚类中心的选择就越优良。
在韩晓洪,胡彧的《K-means聚类算法的研究》一文中,提出先进行l次取样,然后在对取样的数据集采用K-means算法进行聚类,这样会产生l×k聚类中心。然后再对这l×k个聚类中心采取以下方法:先计算对象两两之间距离,再筛掉m个与其他对象之间距离之和最大的对象;从剩下的聚类中心中选出距离最大的两个点作为两个不同类的聚类中心;从剩余的聚类中心中找出和其他聚类中心的距离之和最大的点,作为另一个聚类中心为止。直到选出k个聚类中心。
在王磊,戚飞虎的《大矢量空间聚类的遗传K-means算法》一文中提到,将遗传算法用于聚类分析上。文中将遗传算法与K-means相结合,使用遗传算法的思想,模仿生物学进化过程,在交叉操作中引入K-means算法,最终通过选择操作、交叉操作和变异操作等得到聚类结果,并通过实验验证了该算法的在大矢量空间聚类分析中的优良性能[11]。
也有一些学者提出了K值优化的问题,如在李永森,杨善林,马溪骏等的《空间聚类算法中的k值优化问题研究》一文中,认为在一些实际应用中(如物流配送),可以使用距离代价函数改进K-means算法,并认为距离代价函数当类内距离和类际距离函数函数相等时是距离代价函数的一个极值点,通过该极值点能较快地找到K的最优解。
上一页 [1] [2] [3] [4] [5] [6]
数据挖掘中的聚类算法的研究_聚类在数据挖掘中的应用 第6页下载如图片无法显示或论文不完整,请联系qq752018766