您的位置: 首页  >  文章  >  一文搞懂K-means聚类算法（理论+实现）

一文搞懂K-means聚类算法（理论+实现）

分类: 文章 • 2023-03-30 09:48:59

导读：k-均值算法（英文：k-means clustering），属于比较常用的算法之一，文本首先介绍聚类的理论知识包括什么是聚类、聚类的应用、聚类思想、聚类优缺点等等；然后通过k-均值聚类案例实现及其可视化有一个直观的感受，针对算法模型进行分析和结果优化提出了二分k-means算法。最后我们调用机器学习库函数，很短的代码完成聚类算法。

理论介绍

聚类

       什么是聚类

统计数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性，常见的包括在坐标系中更加短的空间距离等。

       聚类的应用

在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。诸如此类，聚类有着广泛的实际应用。

K-means（k均值）聚类算法

       什么是k-means聚类算法

k-平均算法（英文：k-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把 n个点划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。k-平均聚类与k-近邻之间没有任何关系（后者是另一流行的机器学习技术）。

K-Means 是发现给定数据集的 K 个簇的聚类算法, 之所以称之为K-均值，是因为它可以发现 K 个不同的簇, 且每个簇的中心采用簇中所含值的均值计算而成。簇个数 K 是用户指定的, 每一个簇通过其质心（centroid）, 即簇中所有点的中心来描述。聚类与分类算法的最大区别在于, 分类的目标类别已知，而聚类的目标类别是未知的。

       发展历史

虽然其思想能够追溯到1957年的Hugo Steinhaus，术语“k-均值”于1967年才被James MacQueen 首次使用。标准算法则是在1957年被Stuart Lloyd作为一种脉冲码调制的技术所提出，但直到1982年才被贝尔实验室公开出版。在1965年，E.W.Forgy发表了本质上相同的方法，所以这一算法有时被称为Lloyd-Forgy方法。更高效的版本则被Hartigan and Wong提出。

       算法描述

已知观测集一文搞懂K-means聚类算法（理论+实现），其中每个观测都是一个 d-维实向量，k-平均聚类要把这 n个观测划分到k个集合中(k≤n),使得组内平方和最小。换句话说，它的目标是找到使得下式满足的聚类一文搞懂K-means聚类算法（理论+实现），

一文搞懂K-means聚类算法（理论+实现）

其中 一文搞懂K-means聚类算法（理论+实现） 是 一文搞懂K-means聚类算法（理论+实现） 中所有点的均值。

       k-means术语

  • 簇: 所有数据的点集合，簇中的对象是相似的。
  • 质心: 簇中所有点的中心（计算所有点的均值而来）.
  • SSE: Sum of Sqared Error（误差平方和）, 它被用来评估模型的好坏，SSE 值越小，表示越接近它们的质心. 聚类效果越 好。由于对误差取了平方，因此更加注重那些远离中心的点（一般为边界点或离群点）。详情见kmeans的评价标准。
    有关簇和质心术语更形象的介绍, 请参考下图:

一文搞懂K-means聚类算法（理论+实现）

       k-means应用场景

kmeans，用于数据集内种类属性不明晰，希望能够通过数据挖掘出或自动归类出有相似特点的对象的场景。其商业界的应用场景一般为挖掘出具有相似特点的潜在客户群体以便公司能够重点研究、对症下药。

例如，在2000年和2004年的美国总统大选中，候选人的得票数比较接近或者说非常接近。任一候选人得到的普选票数的最大百分比为50.7%而最小百分比为47.9% 如果1%的选民将手中的选票投向另外的候选人，那么选举结果就会截然不同。 实际上，如果妥善加以引导与吸引，少部分选民就会转换立场。尽管这类选举者占的比例较低，但当候选人的选票接近时，这些人的立场无疑会对选举结果产生非常大的影响。如何找出这类选民，以及如何在有限的预算下采取措施来吸引他们？ 答案就是聚类（Clustering)。

那么，具体如何实施呢？首先，收集用户的信息，可以同时收集用户满意或不满意的信息，这是因为任何对用户重要的内容都可能影响用户的投票结果。然后，将这些信息输入到某个聚类算法中。接着，对聚类结果中的每一个簇（最好选择最大簇 ）， 精心构造能够吸引该簇选民的消息。最后， 开展竞选活动并观察上述做法是否有效。

另一个例子就是产品部门的市场调研了。为了更好的了解自己的用户，产品部门可以采用聚类的方法得到不同特征的用户群体，然后针对不同的用户群体可以对症下药，为他们提供更加精准有效的服务。

       k-means算法思想

先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：

  • 没有（或最小数目）对象被重新分配给不同的聚类。
  • 没有（或最小数目）聚类中心再发生变化。
  • 误差平方和局部最小。

得到相互分离的球状聚类，在这些聚类中，均值点趋向收敛于聚类中心。 一般会希望得到的聚类大小大致相当，这样把每个观测都分配到离它最近的聚类中心（即均值点）就是比较正确的分配方案。

相关推荐