【大数据分析与挖掘】K-Means聚类算法
介绍
对于监督学习模型而言，在训练过程中每个样本都对应一个明确的目标值y。然而，在某些情况下缺乏这一明确的目标变量时，则采用另一种方法进行数据建模——无监督学习方法，在这一领域中聚类分析是最常用的技术之一
K-Means聚类算法基于距离远近的原理将目标数据划分为指定的k个簇，并从而使得样本呈现出 簇内差异显著地减少而与不同簇之间的距离明显增加 的特征。
聚类算法的目标就是利用已知数据将具有相似度高的样本集中至各自的簇中。
除了实现数据分隔之外，并且能够用于异常点监控。
其核心思想是通过计算样本点之间的距离来实现物以类聚。
区别
支持向量机、决策树等经典的机器学习算法主要用于分类问题的核心代表，在分析已知类别样本的基础上训练出能够识别类别特征的模型结构。与分类问题不同，在聚类分析中需要根据数据特征间的关联性将样本自动划分为若干类别组群，并使同一类别组群内的样本具有较高的相近程度与较低的异类相近程度。
具体步骤
- 从数据集中随机抽取k个样本点构成初始质心集合
- 计算所有样本点到各个质心之间的距离，并将每个样本归入与其距离最近的质心对应的簇类中
- 更新各质心中所有样本点的均值坐标，将其作为新的质心位置
- 循环迭代上述步骤直至质心位置收敛稳定并形成最终稳定的k个簇
优缺点
优点：
1.K-Means聚类算法的核心概念与操作流程直观且易于掌握，并且应用广泛且适应性强。
2.对于大数据集来说该算法具有良好的可扩展性和效率其计算复杂度接近线性达到O(NKt)其中N代表数据对象的数量K表示聚类簇的数量t为迭代次数。
缺点：
1.该算法中需要预先设定聚类簇的数量如果设置不合理可能会影响最终的聚类效果
2.合理的初始值选择对最终的聚类结果影响显著不同的初始中心可能导致较大的聚类结果差异
3.计算过程中会受到极端值的影响较大从而使得算法对离群数据较为敏感
4.该方法在处理非球形数据时效果欠佳主要由于其基于距离度量的特点无法有效识别具有复杂形状的数据分布
例题
Take a one-dimensional dataset {15, 15, 16, 19, 19, 20, 22, 28, 35, 40}, based on the fundamental steps of K-Means clustering algorithm. Assume K=2 and randomly select two initial cluster centers: specifically selecting the values of elements at positions corresponding to indices associated with numbers representing positions in the dataset. Use Euclidean distance as the similarity assessment criterion. What is the correct clustering outcome?
1.选择两个初始簇中心：K1=16，K2=22，计算每个点到簇中心的距离，第1次的聚类结果为：
{15，15，16，19，19}和{20，22，28，35，40}
2.重新计算两个簇的中心点，即：把各簇中所有数据的平均值 作为新的簇中心。
新的两个簇中心为：16.8 和 29 （均为虚点 ，即数据集中不存在的点）
重新计算每个点到两个新的簇中心的距离，第2次的聚类结果为：
{15，15，16，19，19，20，22}和{28，35，40}
3.重新计算两个簇的中心点，即：把各簇中所有数据的平均值 作为新的簇中心。
新的两个簇中心为：18 和 34.33 （均为虚点 ，即数据集中不存在的点）
重新计算每个点到两个新的簇中心的距离，第3次的聚类结果为：
{15，15，16，19，19，20，22}和{28，35，40}
4.重新计算两个簇的中心点，即：把各簇中所有数据的平均值 作为新的簇中心。
新的两个簇中心为：18 和 34.33 （均为虚点 ，即数据集中不存在的点）
发现两个簇中心已经不变了（或者跟旧的簇中心相比较，差距很小），说明两个簇中心已趋向稳定 ，算法结束。
故最终的聚类结果为：{15，15，16，19，19，20，22}和{28，35，40}
若为二维，则用欧式距离公式来计算距离。