学习
实践
活动
专区
工具
TVP
写文章

K-Means聚类

到目前为止,我们花了大量的笔墨在有监督算法的学习上。它们有标签、典型,也易于理解。那么下面我们将要开始介绍无监督学习算法,它们没有标签。

无监督学习主要有两大类,聚类和降维。我们先介绍几种常用的聚类的算法,这一篇先来看K-Means算法。

K-Means算法流程

假设我们有一个数据集D,即

我们的目的是什么呢?是将这个数据集分成K类,或者说分成K个簇。我们设簇的集合为C,那么C=。

下面是K-Means算法的步骤:

·        步骤1

从数据D中随机选取K个样本,作为聚类中心,我们设这K个中心分别为。

·        步骤2

计算数据D中每个样本到这K个中心的距离,即

我们一般用L2范数,也叫欧式距离来计算。在计算出距离之后,把每个样本点划分到最近的中心点。

·        步骤3

对于这K个簇,重新计算它们的中心点。

·        步骤4

重复步骤2和步骤3,直到中心点不再发生变化,或者达到我们所需的迭代次数。最后输出分类好的K个簇,即C=。

K-Means关键点

1.K值的选择

通常情况下,K值是人为设定的。因为我们事先并不知道数据能分成几个簇,因此只能靠人工来判断。

2.中心点的选择

一般我们随机来选择K个中心点,但这并不是最好的方法,后面我们会介绍优化的方法。

3.距离的度量

这里我们一般用欧式距离来度量,上文有介绍过。

4.损失函数

假设所有的样本点被分成了K个簇,那么每个簇的中心点向量为

因此,K个簇的总的均方误差就是

我们的目标就是最小化这个误差E。

算法优化

1.K个中心点的选择

前面我们介绍到,随机选取中心点并不是一个很好的方法。这里有一种改进的方法,叫做k-means++方法。这种方法的步骤是这样的:

·        步骤1

从所有样本点中随机选取1个作为中心点,我们记为m1。计算其他所有的样本点到中心点m的距离,选择距离最远的那个样本点作为第二个新的聚类中心m2。

·        步骤2

计算所有样本点到这两个中心点m1和m2的距离,将样本归类到靠近它们的中心点。

·        步骤3

把到中心点距离最远的那个样本再次作为新的中心点。

·        步骤4

重复步骤2和步骤3,直到达到K个中心点。此时,我们就可以用上文介绍过的算法流程进行运算。

2.大量数据的情况

当样本量数据非常大时,由于我们的算法要计算每个样本到中心点的距离,因此不可避免的会发生耗时长、计算量大等状况。为了解决这个问题,有人提出了Mini Batch K-Means算法。

这种算法的原理也很简单,就是对原始的大样本进行随机不放回采样,然后对每个采样进行K-Means聚类。为了提高准确性,通常要进行多次采样和多次聚类,最后选取最合适的簇来进行分类。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20201225A02L3900?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券