上海交通大学硕士学位论文基于粒子群的C均值聚类算法的研究姓名：刘靖明申请学位级别：硕士专业：管理科学与工程指导教师：韩丽川20050101上海交通大学硕士学位论文 - 5 - 基于粒子群的 C均值聚类算法的研究 摘 要 数据挖掘是一个从大量数据中抽取挖掘出未知的 有价值模式或规律等知识的复杂过程 广泛应用于金融保险 市场营销 制造业零售业等行业中在数据挖掘中聚类是一个重要研究领域其目的是将数据库中的数据划分成具有一定意义的子类 使得不同子类中的数据尽可能不同 而同一子类中的数据尽可能相似 聚类被广泛地应用于金融领域地理信息系统卫星图象和信息检索等领域主要的聚类算法有基于划分的算法基于层次的算法基于密度的算法基于栅格的算法 基于模型的算法和模糊聚类算法 模糊聚类算法作为聚类算法的一种应用范围很广泛 尤其在模式识别和图像处理两个领域中得到相当成功的应用 C 均值聚类算法是聚类中基于划分的算法它包括 kmeans 算法硬 C 均值聚类算法和 FCM(模糊 C 均值聚类算法)由于其简单快速而有效而被广泛应用 但在应用过程中这些算法常常会在求解过程中陷入局部最小值 而且对初始值敏感 很多学者尝试用全局寻优算法来改进聚类算法比如遗传算法免疫规划和模拟退火算法虽然取得一定成效但是收敛精度和稳定性不高 粒子群算法是一种新的全局寻优算法自 1 9 9 5年提出后就成为研究的热点目前主要应用于函数优化神经网络训练工业系统优化与控制等领域中 粒子群算法易于实现 具有较强的全局寻优能力上海交通大学硕士学位论文 - 6 - 已有研究证明 和遗传算法相比一般情况下粒子群算法在优化速度和精度上有一定程度的改善 本文以数据挖掘算法中的 C 均值聚类算法为主要研究对象 在分析 k m e a n s 和 F C M 算法流程的基础上 将粒子群算法用于 k m e a n s 算法中提出基于粒子群的 K 均值算法 用大量随机产生的数据和国际标准法分类数据中的 I R I S数据来验证其有效性并将这种算法与已有的基于遗传算法的 K 均值算法进行比较 实验证明本文的粒子群 K 均值聚类算法在收敛精度和稳定性比遗传 K 均值聚类算法要好 然后进一步把粒子群算法和模糊 C 均值算法结合起来 用二阶段法实现了更具有广泛意义的基于粒子群的模糊C 均值算法 并与基于遗传算法的模糊 C 均值算法进行比较 实验证明本文提出的基本于粒子群的模糊C 均值算法改善了 F C M 易于陷入局部最小值的问题而且稳定性比基于遗传算法的模糊 C 聚类算法要好 本文的研究结果一定程度上解决了 C 均值聚类算法易陷入局部最小值和对初始值敏感的问题提高 C 均值算法的收敛精度在数据聚类中有很好的应用效果同时也是粒子群算法的一个新的尝试该研究将对粒子群算法的进一步推广和应用有一定的参考价值 为进一步研究粒子群算法在文本聚类中的应用奠定了基础 关键词聚类分析粒子群算法k m e a n s 算法F C M 算法粒子群聚类算法 上海交通大学硕士学位论文 - 7 - THE RESEARCH OF C-MEANS CLUSTERING ALGORITHM BASED ON PARTICLE SWARM OPTIMIZATION ABSTRACT Data mining is the process of abstracting unaware, potential and useful information and knowledge from plentiful, incomplete, noisy, fuzzy and stochastic data. As the hotspot of research, cluster analysis is one of the most important research domains of data mining. The motion of cluster analysis is that makes the data set into several clusters, a cluster is a collection of data objects that are similar to one another within the same cluster and dissimilar to the objects in other cluster. It has been widely applied into finance, GIS and web archive. The clustering algorithm includes Division-based, layer-based, Density-based, Grid-based, Model-based and fuzzy clustering algorithm. Fuzzy clustering algorithm is a sort of clustering algorithm, for it combines fuzzy theory and the clustering algorithm, it has been applied in more fields. C means algorithm including K-means (hard C means) algorithm and FCM (Fuzzy C means) algorithm has been widely applied since it is simple, fast and effective. However, C means algorithm has some problems to be resolved. Easy to get stuck on the local optima and be sensitive to the initial conditions is what this paper focuses on. Many experts try to use some algorithm with greater searching capability to improve it, such as genetic algorithm and antclass algorithm, since it improve the clustering results, on many occasions it still gets stuck on the local optima, especially when the dimension and size of the training data set and the number of the clusters become large. Particle Swarm Optimization is an excellent algorithm with global searching capability, which has been widely applied in the fields of function optimizationNN training and industry system optimization since it was proposed in 1995.Many experiments show that PSO has better clustering effect than genetic algorithm. In this paper Particle Swarm optimization is combined to improve global searching capability of C-means algorithm. Firstly this paper proposes a novel K-means clustering based on Particle Swarm Optimization algorithm and compares it with Genetic clustering algorithm. The theory analysis and experimental results show that the algorithm not only avoids the local optima, but also has greater searching capability than the existing genetic clustering algorithm. Secondly this paper proposes 上海交通大学硕士学位论文 - 8 - a novel Fuzzy C-means clustering based on Particle Swarm Optimization algorithm, and the experimental results show that the algorithm has great searching capability and great stability. This paper is about a new application of Particle Swarm Optimization which is helpful to the popularization of PSO. For clustering algorithm based on PSO has an excellent performance on the data mining, it could be expected to be applied on the web mining. KEY WORDS: Clustering analysis, PSO, K-means, FCM, clustering algorithm based on PSO 上海交通大学硕士学位论文 - 3 - 上海交通大学 学位论文原创性声明 本人郑重声明所呈交的学位论文是本人在导师的指导下独立进行研究工作所取得的成果除文中已经注明引用的内容外 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果 对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名刘靖明 日期2005 年 1 月 10 日 上海交通大学硕士学位论文 - 4 - 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留使用学位论文的规定同意学校保留并向国家有关部门或机构送交论文的复印件和电子版允许论文被查阅和借阅 本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段保存和汇编本学位论文 保密在 年解密后适用本授权书 本学位论文属于 不保密 请在以上方框内打 学位论文作者签名刘靖明 指导教师签名韩丽川 日期2 0 0 5 年 1 月 1 0 日 日期 2 0 0 5 年 1 月 1 0 日 上海交通大学硕士学位论文 - 11 - 第一章 绪论 1 . 1 引言 随着计算机硬件和软件的飞速发展 尤其是数据库技术与应用的日益普及 人们面临着快速扩张的数据海洋获取各种数据的能力提高得很快大量的数据被广泛使用例如商品条形码的广泛使用 企业信息化程度的提高 科学研究和政府部门中电子化事务处理技术的运用数据收集工具和技术的多元化(从文本扫描到卫星遥感)以及互联网的发展都带来了海量数据和信息 如何有效利用这一丰富数据海洋的宝藏为人类服务 已成为广大信息工作者所关注