讨论k值以及初始聚类中心对聚类结果的影响_K均值聚类需要标准化数据吗

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

摘要：进入二十一世纪以来，科学技术的不断发展，使得数据挖掘技术得到了学者越来越多的关注。数据挖掘是指从数据库中发现隐含在大量数据中的新颖的、潜在的有用信息和规则的过程，是一种处理数据库数据的知识发现。数据挖掘一种新兴的交叉的学科技术，涉及了模式识别、数据库、统计学、机器学习和人工智能等多个领撤分类、聚类、关联规则是数据挖掘技术几个主要的研究领域。在数据挖掘的几个主要研究领域中，聚类是其中一个重要研究领域，对它进行深入研究不仅有着重要的理论意义，而且有着重要的应用价值。聚类分析是基于物以类聚的思想，将数据划分成不同的类，同一个类中的数据对象彼此相似，而不同类中的数据对象的相似度较低，彼此相异。目前，聚类分析已经广泛地应用于数据分析、图像处理以及市场研究等。传统的Ｋ均值聚类算法（K-Means）是一种典型的基于划分的聚类算法，该聚类算法的最大的优点就是操作简单，并且Ｋ均值聚类算法的可伸缩性较好，可以适用于大规模的数据集。但是Ｋ均值聚类算法最主要的缺陷就是：它存在着初始聚类个数必须事先设定以及初始质心的选择也具有随机性等缺陷,造成聚类结果往往会陷入局部最优解。论文在对现有聚类算法进行详细的分析和总结基础上，针对Ｋ均值聚类算法随机选取初始聚类中也的不足之处，探讨了一种改进的选取初始聚类中心算法。对初始聚类中心进行选取，然后根据初始聚类中也不断迭代聚类。改进的聚类算法根据一定的原则选择初始聚类中心，避免了Ｋ均值聚类算法随机选取聚类中心的缺点，从而避免了聚类陷入局部最小解，实验表明，改进的聚类算法能够提高聚类的稳定性与准确率。

关键词：聚类，聚类中心，k均值，相似度，距离

1 问题描述
聚类分析作为一种无监督机器学习方法，在信息检索和数据挖掘等领域都有很广泛的应用,例如金融分析、医学、生物分类、考古等众多领域。聚类的最终目的就是使同一类的数据对象之间相似度最大，彼此相似，而不同类的数据对象之间相似度最小，彼此相异。聚类算法是聚类分析的主要研究内容，自从20世纪80年代数据挖掘技术提出以来，许多学者都对聚类研究做出了贡献，主要体现在聚类算法的改进上，迄今为止，研究人员提出以下五种聚类算法，大体上可分为基于划分的聚类算法、基于网格的聚类算法、基于密度的聚类算法、基于层次的聚类算法和基于模型的聚类算法。基于划分的聚类算法是目前应用最广泛、最成熟的聚类算法，其中，Ｋ均值聚类算法一个比较简洁和快速，一种典型的基于划分的聚类算法，其思想简单、收敛速度快，已得到广泛的应用和研究，但是K均值算法存在着以下缺陷：初始聚类个数K必须事先设定，而实际中K值一般较难确定。而且对初始聚类中心十分敏感，由于随机选取初始聚类中心，不同的初始中心点会造成聚类结果的波动，易陷入局部最小解，同时Ｋ均值聚类算法具有易受噪声数据影响、难以发现非球状簇、无法适用于巨大数据集等缺陷。所以本文旨在探讨初始聚类中心的选择给定方式。

2 研究现状
聚类分析是一个活跃的领域，已有大量经典的聚类算法涌现，主要有基于划分的聚类算法、基于网格的聚类算法、基于密度的聚类算法、基于层次的聚类算法、基于模型的聚类算法、以及对传统的五种聚类算法的改进。聚类的研究现在还是富有一定的挑战性的，目前，己有众多学者提出了各种改进的聚类算法，针对不同的数据集，不同的聚类算法往往会取得不同的聚类效果，学者一般会根据数据集的不同来选择不同的聚类算法进行聚类，也就是说，目前并没有一种统一的聚类算法可在不同的数据集上取得较好的聚类结果。虽然现有的聚类算法比较多，但它们都会有这样那样的不足，数据集的不同也会影响不同聚类算法的聚类结果。研究和改善聚类算法、提高聚类结果的准确率一直以来是国内外专家、研究人员的重点工作之一。
本文讨论的K 均值聚类算法是一种常用的、典型的基于划分的聚类算法，具有简单易实现等特点。目前关于K均值聚类算法的改进有很多，K均值聚类国内外研究成果主要包括：文献[1]将决策树算法引入到 K 均值聚类算法的改进中，增强了算法的抗噪性，但算法的计算比较复杂；文献[2]将遗传算法引入到 K 均值聚类算法中，改善了算法的聚类效果；文献[3]提出了一种模糊 K 均值聚类算法，通过引入处罚项到目标函数中，使算法对初始聚类中心不再敏感，提高了算法的聚类效果；文献[4]提出一种 W-K 均值聚类算法，它将整个数据集看成一类，然后根据类中属性再对数据集划分直到达到所需类数目为止，算法对稀疏高维的数据集聚类比较好；为了克服K－means算法对初始中心的敏感性，研究者提出了许多改进算法。Wang[5]提出了基于相异度的K－means改进算法，其中初始聚类中心由相异度矩阵组成的霍夫曼树确定。郑丹等[6]通过k－distance图选择初始聚类中心。仝雪姣等[7]基于数据样本分布和利用贪心思想确定初始聚类中心。任倩等[8]首先运用Kruskal算法生成最小生成树，并按权值大小删去部分边后，以K个连通对象的均值作为初始聚类中心。文献[9-11]中从样本密度的特点出发，选择相互距离最远的K个处于高密度区域的样本作为初始聚类中心。文献[12]中则在样本密度信息的基础上进一步结合密度RPCL算法确定初始聚类中心。文献[13]中利用密度网格优化K－means聚类。这些基于密度的方法充分利用了样本空间中数据的分布状况，能够产生更优的初始聚类中心。

3 算法原理
K均值聚类算法(K-Means)
聚类就是按照某个特定标准（如距离准则）把一个数据集分割成不同的类，使得同一个类内的数据对象的相似性尽可能大，同时使不在同一个类中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同类的数据尽量分离。
K均值聚类算法是由Mac Que提出的。K均值聚类算法是一种经典的划分聚类算法，Ｋ均值聚类算法是一种迭代的聚类算法，在迭代的过程中不断移动聚类中心，直到聚类准则函数收敛为止。
Ｋ均值聚类篡法的基本思想
Ｋ均值聚类算法属于一种动态聚类算法，也称逐步聚类法，在聚类算法迭代之前，算法首先随机的从数据集中依次选取ｋ个数据对象作为ｋ个初始聚类中也，根据类中对象的均值，即聚类中也，依次将其他的数据对象划分到与其最近的聚类中也所在的类中，数据对象划分完毕，然后计算每个聚类的中心，更新聚类中心作为新的聚类中心点，迭代上述聚类过程。直到聚类中也不再发生变化，即聚类准则画数值收敛为止或者聚类准则函数连续值相差小于给定阀值。通常采用的目标函数即聚类准则函数为误差平方和准则函数。在每次迭代中都要考察样本的分类是否正确是Ｋ均值聚类算法的一个的特点。
在数据挖掘中，K 均值聚类算法广泛的应用于科学研究、数据统计分析等研究领域，是经典聚类算法之一。它是一种基于距离的硬聚类算法，基于距离的聚类算法主要是指采用距离函数作为相似性度量的评价指标，距离函数主要有如下几种：
1. 欧氏距离
欧氏距离的计算公式如下 

2.明氏距离

明氏距离是一种带有明氏距离的计算公式如下式
 
其中，t为一个正整数。
显而易见，当式中的t=2时，就得到欧式距离，所以欧氏距离可以看成明氏距离的一个特例。欧氏距离是聚类算法中用来度量数据对象间相异性最常用的方法之一。类似的相似度度量方法还有曼哈顿距离、切氏距离、马氏距离、兰氏距离等，只不过这些相似度度量方法不常用而已，分别定义如下：
曼哈顿距离：
 
马氏距离：
 
其中， 表示样本协方差阵的逆阵，T在运算里表示矩阵的转置。

 
一般我们都采用欧氏距离作为相似性度量函数。也就是说，如果两个数据对象的距离比较近。说明二者比较相似，距离比较远，说明二者不相似。所谓的硬聚类算法是指数据集中的数据对象要么属于这个簇，要么属于其它的簇，并不存在模糊的概念。Ｋ均值聚类算法具有简单快速、适于处理大数据集等优点，但它缺点同样存在，比如易陷入局部最小解、需要事先指定聚类数目等等。目前，国内外许多改进的聚类算法都是在Ｋ均值聚类算法思想基础上做出的深入的研究。本节重点介绍了Ｋ均值聚类算法原理，在基于Ｋ均值聚类算法随机选取初始聚类中易陷入局部最小解的情况下，提出了一种改进的Ｋ均值聚类初始聚类中心点选取的算法，实验证明该聚类算法能够有效的避免聚类结果陷入局部最优解，很好的提高聚类的准确度。

传统Ｋ均值聚类篡法的的流程

具体步骤为：
首先利用随机选取从数据集中抽取 K 个数据对象作为初始聚类中心；然后计算剩余数据对象与各个聚类中心的欧几里德距离，按照距离最小原则来划分类别;完成一轮聚类后，再计算每一类的平均值，用 K 个平均值作为新的 K 个聚类中心,再计算剩余的数据对象与这 K 个聚类中心的欧几里德距离，再按照距离最小原则划分类别，循环反复，直到满足某个终止条件迭代才停止。这个终止条件可以是下面的任意一个：                              
(1)目标函数相对于上一次的改变量小于某个阈值；                     
(2)迭代次数大于给定的阈值.
不难看出，K 均值聚类算法存在以下问题：
(1)初始聚类中心随机选取，容易选到噪声数据和孤立点，使算法的迭代次数增多，算法的时间性能变差，另外，受噪声数据和孤立点的影响算法还容易陷入局部极值；
(2)算法没有考虑到各个数据对象对聚类的影响是不同的，单纯地从欧几里德距离上去决策分类。这样就导致，如果待聚类数据集中存在很多噪声数据和孤立点，那么算法的聚类准确性就不高。
(3)对于处理小量的低维的数据集，K 均值聚类算法在单机上运行没有什么问题，但在处理海量的高维的数据时，K 均值聚类算法在单机上的时间性能和空间性能都很差。

2 关于初始点选取的改进：
最简单的传统的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点，但是该方法在有些情况下的效果较差容易陷入局部极值。
还有其他的一些方法：
1)选择彼此距离尽可能远的K个点 
2)先对数据用层次聚类算法或者Canopy算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
选择彼此距离尽可能远的K个点的思想是：首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最短距离最大的那个点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。

例1. 考虑图一中的12个点，最坏情况下，选择中间附近的点作为初始点，比如（6,8）。离他最远的点是（12,3）。因此下一步我们选择（12,3）。

 

                                                                                   图一
剩余的10个点中，离（6.8）或（12,3）的最短距离最大的那个点是（2,2）。该点到（6,8）的距离是7.21，到（12,3）的距离是10.05，因此它的“得分”是7.21.很容易检查其他的点到（6,8）或（12,3）中至少一个点的最短距离都小于7.21.因此，最终我们选择（6,8），（12,3）和（2,2）作为初始点。

在这里本文关于初始点的选取，提出了两种自己的改进方法。
第一种改进结合第一种方法进行了改进，主要是对于第一个点进行改进，不随机选取一个点，而是从所有的数据点中选出密度最大的一个点作为第一个初始聚类中心点，某种程度上避免了选到离群点的可能，当然半径我们需要调节一个合适的值。然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最短距离最大的那个点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。
  该方法经过测试效果很好，用该方法确定初始类簇点之后运行KMeans得到的结果全部都能完美区分五个类簇。
第二种改进方法是首先选出密度最大的那个点，然后减去他周围最近的n个点（数据总数除以k）；然后再找到剩余数据点中密度最大的点，然后减去他周围最近的n个点，以此类推直到找到k个初始点。次方法适用于每一类数据点个数相等的情况。此方法选出的初始点也基本都分在了不同的簇中，但是相对于第一种有一定的局限性。
关于初始点K值确定的一种简单的方法：
关于k的个数的确定：我们可能不知道在K均值中正确的k值。但是，如果能够在不同的K下对聚类结果的质量进行评价，我们往往能够猜测到正确的k值。如果给定一个合适的簇指标，如平均半径或直径，只要我们假设的簇的数目等于或高于真实的簇的数目，该指标上升会趋势会很缓慢。但是一旦试图得到少于真实数目的簇时，该指标会急剧上升。

 

                                                                                          图二
如图中当簇数目低于数据中真实的簇数目时，平均直径或其他分散指标会快数上升
通过上面提供的方法，我们在当簇的个数不知道的时候，可以通过它大致的获取簇的数目。

4 算法实现
1、实验开发环境
实验硬件： 一台处理器为intel（R）Pentium（R）G840 2.8GHz 内存4GB 的PC机
操作系统： Windows 7的64位
开发软件： Matlab2016a
2、传统K-means聚类算法步骤：
给定一个数据点集合和需要的聚类数目k（由用户指定），k均值算法根据某个距离函数反复把数据分入k个聚类中。
1）初始化。输入数据点集合X，并指定聚类类数N，在X中随机选取N个对象作为初始聚类中心；
2）设定迭代终止条件。比如最大循环次数或者聚类中心收敛误差容限；
3）更新样本属于哪个类。根据相似度准则将数据对象分配到最接近的类；
4）更新类的中心位置。以每一类的平均向量作为新的聚类中心；
反复执行第3步和第4步直至满足终止条件。
3、本文关于初始聚类中心选取的改进：
1） 首先从所有的数据点中选出密度最大的一个点作为第一个初始聚类中心点；
2）然后选择距离该点最远的那个点作为第二个初始类簇中心点；
3）再选择距离前两个点的最短距离最大的那个点作为第三个初始类簇的中心点，以此类推，直
至选出K个初始类簇中心点
3、实验步骤   
（1）首先我们使用传统的K均值算法利用MATLAB随机生成五组高斯分布数据，再合成一个数据组。
（2）随机选取5个数据作为初始聚类中心点，然后用编写的K均值MATLAB程序对数据组进行聚类记录结果。
（3）从所有的数据点中选出密度最大的一个点作为第一个初始聚类中心点，在程序编程中我们求出每个数据点的N个点的近邻（N可适当设置这里我们先设为6，然后比较近邻的半径选出最小半径即是最大密度点）。然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最短距离最大的那个点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点，最后对数据进行聚类。

5 实验结果
 

6 结论
经过这段时间对K均值算法的学习以及动手实践，使我对聚类算法中这个最经典的算法有了更进一步的了解。明白了K均值的算法流程和核心问题。通过查阅资料学习了很多对于他的改进算法，并在本文中对K均值的一种改进算法加进了一点新的方法，使得第一个初始聚类中心不需要随机选取，而是选取最大密度点。对于一些典型的凸形状中心密度大的类型数据第一个初始点很接近它的类中心点。
K-means聚类算法优点：
（1）算法简单、快速；
（2）对大数据集效率较高；
（3）当簇接近高斯分布时，它的效果较好。
K-means聚类算法缺点：
(1) 在簇的平均值可被定义的情况下才能使用，可能不适用于某些应用；
(2) 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适；
(3) 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果；
(4) 该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的；
(5) 若簇中含有异常点，将导致均值偏离严重（即:对噪声和孤立点数据敏感）；
(6) 不适用于发现非凸形状的簇或者大小差别很大的簇。
K-means算法缺点的改进：
针对上述第(3)点，不随机选取聚类中心，而是从所有的数据点中选出密度最大的一个点作为第一个初始聚类中心点。然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最短距离最大的那个点作为第三个初始类簇的中心点，以此类推，直至选出K个初始类簇中心点。

一个一个加公式和图片太麻烦了所以后面就直接把我做的PDF用截图粘了上来，之后我会发程序代码。有需要的可以留言。
 

2020年1月2日：以上内容是我一门课程的大作业，所以写的很啰嗦，不喜勿喷。代码实现我发在了我其他的文章中，大家需要可以去我的博客里找一下。感谢支持的朋友，以后我会根据自己的理解好好写一些东西，之前写的确实不怎么用心，勿怪。