基于划分的聚类算法研究与应用

论文摘要

基于划分的聚类算法主要有K均值和K中心点算法,其他的方法都是这两种算法的变种。然而,K均值算法聚类结果有波动,取决于初始的K个中心点选择。造成这一结果的原因是K均值法初始时是随机选取中心点,迭代过程可能会终止于一个局部极值点,而这个极值点很可能不是最优点;传统的K中心点的聚类算法虽然能够得到较好的局部搜索结果,但需要很长的计算时间。为了改进K均值算法结果的波动性,本文提出一种优化初始点的K均值算法:先用一种方法探测数据集内的分布区域,分析数据集内的分布情况,然后根据数据集的分布情况,生成一颗聚类树;每次聚类时,根据用户输入的参数K,对这棵聚类树用二分查找,确定一个合适的相似度阀值,使得这棵树产生K+X（X＞0,根据实际情况选择）划分,再把其中的平均相似度较小的X个区域划分到其他K簇中。最后,得到的K个簇,计算每一簇的中心,找出离这个中心最近的点作为初始的聚类中心。本文的方法是根据数据点的分布情况来选择初始中心,实验结果证明,有效避免了随机选择带来的聚类结果的波动性,比传统的K均值算法有着更高的查准率和查全率。为了使K中心点算法既能快速实现局部搜索过程,又能得到较好的局部极大解,本文作如下改进:当用一个更好的非中心对象替代某个中心对象后,先在每一个簇中找一个较优的初始聚类中心,然后找出使当前簇内目标函数值最大的对象并用其替代原来的中心对象,再重新分配剩余的对象。这样能够使目标函数值以更快的速度增加,从而加快收敛到局部极大解的速度。实验结果证明了本文做的改进,比传统的算法有着更快的收敛速度和更高的准确率。最后,本文把改进的算法应用于大连市公安局网上作战系统,对违法犯罪信息进行了聚类分析。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文主要内容
• 2 聚类分析算法及应用
• 2.1 聚类分析定义
• 2.2 常用的聚类分析算法
• 2.2.1 基于划分的算法
• 2.2.2 基于层次的算法
• 2.2.3 基于密度的算法
• 2.2.4 基于网格的算法
• 2.2.5 几种常用算法比较
• 2.3 聚类分析的应用实例
• 3 基于K均值聚类算法分析及其改进
• 3.1 K均值算法
• 3.1.1 K均值思想
• 3.1.2 K均值分析及其缺点
• 3.2 文本处理模型
• 3.2.1 文本的表示
• 3.2.2 中文文本的分词和预处理
• 3.3 相似度及其计算
• 3.3.1 TFIDF算法
• 3.3.2 TFIDF的改进
• 3.4 聚类分析中的孤立点的问题
• 3.5 特征选择与降维
• 3.5.1 特征降维的重要性
• 3.5.2 特征数目对结果的影响
• 3.6 一种初始聚类中心的选取方法
• 3.6.1 算法思想
• 3.6.2 算法步骤
• 3.6.3 算法分析
• 4 基于K中心点聚类算法的改进
• 4.1 K中心点比K均值的优越性
• 4.2 基于目标函数极大值的改进
• 4.3 基于初始聚类中心选择的改进
• 5 实验结果及应用
• 5.1 聚类结果评价
• 5.2 实验结果及分析
• 5.3 算法应用
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢