一种改进的K均值聚类算法及其应用开题报告

1. 研究目的与意义

在这信息大爆炸的大数据时代，全球的信息量每秒都在高速增长。聚类分析主要就是对数据进行分类，指事先不了解一批样本中的每一个样本的类别或其他的先验知识，而唯一的分类根据是样本的特征，利用某种相似度度量的方法，把特征相同或相似的归为一类，实现聚类划分。在此基础上1956年出现了K均值聚类，它是首先把输入点分为至K个初始化分组，可以使用一些随机或者一些启发式数据，然后计算每组的中心点，根据中心点的位置把样本分到离它最近的中心，重新确定分组，再继续重复不断地计算中心并重新分组，直到收敛，即样本不再改变分组（中心点位置不再改变）为止。

然而在实际操作中，Kmeans算法主要通过迭代搜索获得聚类的划分结果。虽然Kmeans算法运算速度快，占用内存小，比较适合于大样本量的情况，但是聚类结果受初始凝聚点的影响很大，不同的初始点选择会导致截然不同的结果。并且当按最近邻归类时，如果遇到与两个聚类中心距离相等的情况，不同的选择也会造成不同的结果。因此，K均值动态聚类法具有因初始聚类中心的不确定性而存在较大偏差的情况。为此对K均值算法的初始聚类中心的选择方法进行了改进，提出了一种从数据对象分布出动态寻找并确定初始聚类中心的思路以及基于这种思路的改进算法。

2. 国内外研究现状分析

[1]罗岚-k均值聚类算法的优化-现代经济信息，文章编号：1001-828x(2016)002-000106-02

为了避免离群点影响结果，首先应当处理好离群点。但是处理它不代表删掉它。通过预处理，移除具有异乎寻常影响的点，往往可以有效减少对簇中心选择的判断失误。比如，删除过小的聚簇，或者将彼此接近的一些聚簇合并成一个更大的聚簇 [7]。其次，鉴于簇中心的选择相当关键，为了减小由于簇中心选取不当带来的误差，可以在点到簇的每一次指派之后，都适当的增加质心的数量，更新原来的质心。原始的算法规则是所有的点都指派到簇中以后再更新簇中心，这样操作的局限就在于不能够及时的更正由于质心不准确而引起聚类效果不佳的影响。而改进后的算法能够及时调整质心，增量更新，并且可以调整点的相对权值。

[2] 安计勇 高贵阁 史志强 孙磊-一种改进的k均值文本聚类算法-transducer and microsystem technologies 2015年第34卷第5期

3. 研究的基本内容与计划

在K均值算法中，选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率，此方法就是如何找到与数据在空间分布上尽可能一致的初始聚类中心。对数据进行划分，最根本的目的是使一个聚类中的对象是相似的，而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度。相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到K个初始中心，它们分别代表了相似程度较大的数据集合，那么就找到了与数据在空间分布上相一致的初始聚类中心。下面有两种选举初始聚类中心的方法。1.基于最小距离的初始聚类中心选取法；2.基于最小二叉树的方法。其他几个改进方法暂略，本文将选取其中一个来研究。

还有一种是基于取样思想的改进K均值算法，本文就其思想结合MATLAB来研究并实现应用。本文主要工作量就是MATLAB实现和场景应用。

4. 研究创新点

鉴于初始聚类中心对k均值聚类算法的影响，以及k均值聚类算法的不足，构造了改进k均值的聚类算法。

该算法通过两种方法选取初始聚类中心，然后在给定初始聚类中心的基础上再次使用k均值聚类算法，从而得出聚类结果。

全部样本与已知样本完全符合。