基于层次的Kmeans初始化算法.pdfVIP

基于层次的 K －means 初始化算法 汤九斌，陆建峰，唐振民，杨静宇 （南京理工大学计算机系，南京 ２１００９４） ［摘要］　Ｋ －ｍｅａｎｓ 算法是一种常用的聚类算法，但是聚类中心的初始化是其中的一个难点。 笔者提出了一 个基于层次思想的初始化方法。 一般聚类问题均可看作加权聚类，通过层层抽样减少数据量，然后采用自顶 向下的方式，从抽样结束层到原始数据层，每层都进行聚类，其中每层初始聚类中心均通过对上层聚类中心 进行换算得到，重复该过程直到原始数据层，可得原始数据层的初始聚类中心。 模拟数据和真实数据的实验 结果均显示基于层次抽样初始化的Ｋ －ｍｅａｎｓ 算法不仅收敛速度快、聚类质量高，而且对噪声不敏感，其性能 明显优于现有的相关算法。 ［关键词］　层次技术；初始聚类中心；加权数据；Ｋ 平均聚类 ［中图分类号］　ＴＰ３１１　［文献标识码］　Ａ　［文章编号］　１０００９－１７４２（２００８）１１－００７４－０６ 数据进行随机抽样，例如，抽取原数据的 １％，然后 1　引言 在抽样后的数据上采用 ＥＭ 算法进行聚类，得到一 聚类分析在模式识别、数据挖掘等领域，起着非 组聚类中心，然后，重复上述过程（再重新抽样和进 常重要的作用。 近些年来，随着数据挖掘研究的深 行聚类），假设重复 n 次，那么就得到 n 组聚类中 入，聚类分析日益受到重视［１］ 。Ｋ －ｍｅａｎｓ 算法是较 心；然后对上述所有采样的数据，利用n 组聚类中心 常用的聚类算法之一，其中聚类中心的初始化对该 采用Ｋ －ｍｅａｎｓ 算法再进行聚类，选取性能最佳的 算法的性能影响很大。 若选取的初始聚类中心不合 一组，作为最终的初始聚类中心。 从他们论文所提 适，将不仅影响收敛速度，还有可能使算法陷入局部 供的结果来看，该方法能够适用于大规模的数据，并 最优，但目前许多参考文献往往绕开该问题。 迄今 且总体性能较好。 为止，对聚类算法中聚类中心初始化的研究相对较 Ｋｈａｎ 和Ａｈｍａｄ 提出了一种基于属性的初始化 少，且没有简单通用的好方案，重复不同的随机选择 方法［９］ 。 其方法的主要思想是，数据点的每个属性 似乎成为了事实上的方法［２］ 。 Ｐｅｎａ 等对目前常用 可以为初始化提供信息，利用这一点，首先获得比类 的初始化算法从聚类质量（有效性）、聚类方法的敏 别数多的初始聚类中心，然后再进行合并，使得初始 感性（鲁棒性）和收敛速度（即效率）等方面进行了 聚类中心的个数等于类别数。 实验结果显示，该方 实验比较研究［３］ ，结果表明随机初始化方法和Ｋａｕｆ唱 法的性能优于随机化的初始化方法。 ｍａｎ 方法［４］ （ＫＡ）在有效性和鲁棒性方面均优于 笔者提出了基于层次方法的聚类中心初始化方 Ｆｏｒｇｙ 方法［５］ ［６］ 法（ＨＩＫＭ），通过分层聚类，找到较好的初始聚类中 （ＦＡ）和 Ｍａｃｑｕｅｅｎ 方法 （ＭＡ），其中 ＫＡ 在收敛速度方面优于随机化方法。 心。 该算法采用误差平方和最小作为聚类测度，首 最近，Ｂｒａｄｌｙ 和Ｆａｙｙａｄ 等人对目前的一些初始 先采用金字塔结构，对原始数据进行层层抽样，在抽 点选择的方法进行了评述，并指出“在离散数据上 样后的数据上进行聚类。 尽管抽样后数据有所减 采用ＥＭ 算法和随机的初始化方法相比，并没有什 少，但对 Ｋ －ｍｅａｎｓ 算法而言，原始信息却损失较 么提高” ［７，８］ 。 在文献［７］中，其算法思想：首先对 少，抽样后的数据能较