机器学习(十九) ——K-均值算法理论

机器学习(十九)——K-均值算法理论

(原创内容,转载请注明来源,谢谢)

一、概述

K均值(K-Means)算法,是一种无监督学习(Unsupervisedlearning)算法,其核心是聚类(Clustering),即把一组输入,通过K均值算法进行分类,输出分类结果。

由于K均值算法是无监督学习算法,故这里输入的样本和之前不同了,输入的样本只有样本本身,没有对应的样本分类结果,即这里的输入的仅仅是{x(1),x(2),…x(m)},每个x没有对应的分类结果y(i),需要我们用算法去得到每个x对应的y。

K均值算法,常用的场景包括市场分析中分析不同用户属于哪类用户、社交网络中分析用户之间的关系、计算机集群设计分析、星系形成过程分析等。

无监督学习和监督学习输入的区别如下图:

二、算法基本步骤

1、前提

现假设数据点有m个,需要有K个分类。

2、步骤

1)随机初始化K个点,作为K个分类的中心点,每个中心点称为聚类中心(cluster centroid),也成为簇。下图是K=2时,随机选2个簇。

2)根据K个中心点,遍历所有样本,分别计算每个样本到每个中心点的距离,把样本分到最近的举例。

3)分类完成后,根据分类完成的结果,计算在每个分类中的样本的平均值,把聚类中心移动到这些平均值中。

4)重复步骤2、步骤3,直到聚类中心稳定。

综上,步骤如下:

3、特殊情况

当随机选到的某个聚类中心,如果在一次分类中,没有一个样本被分到这个聚类中心,则如果有固定的分类结果数量要求,则需要重新随机选择初始聚类中心,重新进行K均值计算。为了速度较快,可以存储这些没有任何分类结果的点,在随机初始聚类中心时,避免选到这些点。

三、代价函数

1、符号

在K均值算法中,K(大写)表示分类结果数量(K=3表示样本要分成3类),k(小写)表示第k个聚类中心, C(i)表示样本x(i)所属的聚类中心编号,μk表示第k个聚类中心的位置,μC(i)表示x(i)所属的聚类中心位置。

例如,x(i)被分类到第5个聚类中心,则C(i)=5,μC(i)=μ5。

2、代价函数

K均值算法的代价函数,又称为K均值算法的dispulsion函数,公式如下:

可以证明,对于代价函数的公式:

1)K均值算法的第二步(即选好聚类中心后,需要把每个样本分类到对应的聚类中心),对于优化代价函数而言,相当于固定μ的值,来计算J(c)的最优情况。

2)算法的第三步(即通过计算每个聚类的样本均值重新选定聚类中心),对于优化代价函数而言,相当于通过μ的优化来确定最优的J。

四、初始化聚类中心

1、前提

随机初始化聚类中心,前提是要求总的分类数量K小于样本数量m,否则分类没有意义。

2、步骤

1)在m个样本中,随机选出K个样本。

2)令μ1、μ2…μk等于这K个样本。

简单来说,即在样本中随机初始化聚类中心,而不是漫无目的的在整个坐标系中来随机。

3、存在问题——局部最小值

K均值算法的代价函数,也存在局部最优解(极小值)的情况,这个对于K均值算法来说非常不好,如下图所示:

上图左边是待分类的样本,右边上方是根据日常经验来说应该被分类的样子,而右边下面两个分类结果,都是出现局部极小值的结果。即一开始随机初始化的时候,有两个初始化点都被初始化在本来应该被分在一个类的“地盘”,这就导致后面优化的时候,会不断的按这个本来就错误的方式来优化。

4、解决方案

为了避免局部最小值的情况,可以多次进行K均值算法的运算。每次分类稳定后,记录该分类的方式,以及该分类方式下最终的代价函数(即每个点到聚类中心点的距离的平方和),然后取这些分类结果中,带价值最小的分类方式,作为最终的分类方式。

如下图所示:

通常而言,当执行K均值算法超过50次,则最终一般可以避免局部最优解的错误分类结果。

另外,局部最优解,一般只在K比较小(K在2~10左右)的时候容易发生,当K非常大时,通常不会发生局部最优解,或者说这种局部最优解和最佳解的差距也不是非常大,可以接受。

五、确定分类数量K

在不确定要分几类时,需要确定分类数量K。

1、方法一:肘部法则

肘部法则(ElbowMethod),即通过改变K值,描绘出K和代价函数J的图像,并且确定在某个K时,代价函数降低的最多(图像类似人类的肘部),则取这个K作为应当的分类结果,如下图的左边的图像所示。

但是肘部法则存在问题,如上图的右图所示,当K-J的图像,不存在一个剧烈的降低点(从图像中无法明确哪个K是肘部),而是比较平缓的降低,则此时无法通过肘部法则来明确选择哪个K是最佳的。

2、方法二

当肘部法则无法确定K时,更通用的方式,是分析当前的业务场景,并且通过业务场景,来明确所需要的分类结果。

例如下图是根据 身高和体重的人群分布,需要确定设计的T恤衫的尺寸。例如可以分为3类(左图)、5类(右图),分类都是合理的。

此时,就需要通过认为的经验分析,明确应该选哪种K作为最佳分类。

六、小结

K均值算法,作为无监督学习方法,其思想和分析方式,和监督学习算法有比较大的不同。应当明确,监督学习是提前告知分类结果,而无监督学习并没有提前告知分类结果,他们是有不同的业务场景,因此必然设计思想完全不同。

——written by linhxx 2018.01.22

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

直观理解深度学习的卷积操作,超赞!

近几年随着功能强大的深度学习框架的出现,在深度学习模型中搭建卷积神经网络变得十分容易,甚至只需要一行代码就可以完成。

2461
来自专栏云时之间

深度学习与TensorFlow:VGG论文笔记

马毅老师曾说过:”如果你没有看过近30年的经典论文,你是做不出成果的”.现如今深度学习如此火热,一些关键节点发布的文章更应该好好的阅读,因此我想在未来的一段时间...

3355
来自专栏鸿的学习笔记

分类问题中维度诅咒(上)

在本文中,我们将讨论所谓的“维度的诅咒”,并解释为什么在设计分类器时很重要。在以下部分中,我将提供对这个概念的直观解释。

1311
来自专栏机器之心

学界 | 田渊栋等人论文:何时卷积滤波器容易学习?

选自arXiv 机器之心编译 参与:黄小天、刘晓坤 近日,田渊栋等人在 arXiv 上发表了一篇题为《When is a Convolutional Filte...

38014
来自专栏企鹅号快讯

机器学习——K-均值算法理论

机器学习(十九) ——K-均值算法理论 (原创内容,转载请注明来源,谢谢) 一、概述 K均值(K-Means)算法,是一种无监督学习(Unsupervisedl...

24810
来自专栏磐创AI技术团队的专栏

干货 | 基于深度学习的目标检测算法综述(三)

目标检测(Object Detection)是计算机视觉领域的基本任务之一,学术界已有将近二十年的研究历史。近些年随着深度学习技术的火热发展,目标检测算法也从基...

6241
来自专栏磐创AI技术团队的专栏

基于深度学习的计算机视觉应用之目标检测

目标检测作为图像处理和计算机视觉领域中的经典课题,在交通监控、图像检索、人机交互等方面有着广泛的应用。它旨在一个静态图像(或动态视频)中检测出人们感兴趣的目标对...

3937
来自专栏云时之间

深度学习与神经网络:BP神经网络

BP神经网络现在来说是一种比较成熟的网络模型了,因为神经网络对于数字图像处理的先天优势,特别是在图像压缩方面更具有先天的优势,因此,我这一段时间在研究神经网络的...

4839
来自专栏云时之间

通过BP神经网络对于图像压缩的实现

BP神经网络现在来说是一种比较成熟的网络模型了,因为神经网络对于数字图像处理的先天优势,特别是在图像压缩方面更具有先天的优势,因此,我这一段时间在研究神经网络的...

40710
来自专栏大数据文摘

手把手:基于概率编程Pyro的金融预测,让正则化结果更有趣!

1702

扫码关注云+社区

领取腾讯云代金券