一种改进的动态k-均值聚类算法.PDFVIP

计 算 机 系 统 应 用 2013 年 第 22 卷 第 5 期 一种改进的动态k-均值聚类算法① 胡 伟 ( 山西财经大学 实验教学中心, 太原 030006) 摘 要: 针对经典k-均值聚类方法只能处理静态数据聚类的问题, 本文提出一种能够处理动态数据的改进动态k- 均值聚类算法, 称为 Dynamical K-means 算法. 该方法在经典 k-均值方法的基础上, 通过对动态变化的数据集中 新加入样本进行分析和处理, 根据聚类目标函数改变的实际情况选择最相似的类别进行局部更新或进行全局经 典 k-均值聚类, 有效检测发生聚类概念漂移和没有发生聚类概念漂移的情况, 从而实现了动态数据的在线聚类, 避免了经典 k-均值方法在动态数据中每次都要对全部数据重新聚类而导致算法速度过慢的问题. 标准数据集和 人工社会网络数据集上的实验结果表明, 与经典k-均值聚类方法相比, 本文提出的动态k-均值聚类方法能快速高 效地处理动态数据聚类问题, 并有效地检测动态数据聚类过程中所产生的概念漂移问题. 关键词: K-均值聚类; 动态 k-均值算法; 动态数据; 概念漂移 Research and Realization of a Web Information Extraction and Knowledge Presentation System HU Wei (Experimental Teaching Center, Shanxi University of Finance and Economics, Taiyuan 030006, China) Abstract: This paper presents an improved dynamical k-means clustering model to solve the dynamical problem, called Dynamical K-means algorithm, in order to solve the problem that only solving the constant clustering problems of classical k-means clustering method. Based on classical k-means method, by analysis and solving the new adding samples of dynamical training data set, local renew or global clustering is performed by the changing range of objective function, and the dynamical data are clustered online. The speed of classical k-means algorithm is slow by the reiterative clustering is needed of every online clustering step, but the speed of Dynamical K-means algorithm is accelerated. Simulation results on standard and artificial social network datasets demonstrate that comparing with classical k-means clustering means, the excellent clustering results can be obtained by this method and the concept drifting phenomenon can be monitored efficiently. Key words: K-means clustering; dynamical K-means algorithm; dynamical data; concept drifting 随着信息技术尤其是数据库技术的不断发展,