Stanford机器学习笔记-9. 聚类(Clustering)

9. Clustering 

Content   9. Clustering     9.1 Supervised Learning and Unsupervised Learning     9.2 K-means algorithm     9.3 Optimization objective     9.4 Random Initialization     9.5 Choosing the Number of Clusters

9.1 Supervised Learning and Unsupervised Learning

我们已经学习了许多机器学习算法,包括线性回归,Logistic回归,神经网络以及支持向量机。这些算法都有一个共同点,即给出的训练样本自身带有标记。比如,使用线性回归预测房价时,我们所使用的每一个训练样本是一个或多个变量(如面积,楼层等)以及自身带有的标记即房价。而使用Logistic回归,神经网络和支持向量机处理分类问题时,也是利用训练样本自身带有标记即种类,例如进行垃圾邮件分类时是利用已有的垃圾邮件(标记为1)和非垃圾邮件(标记为0),进行数字识别时,变量是每个像素点的值,而标记是数字本身的值。我们把使用带有标记的训练样本进行学习的算法称为监督学习(Supervised Learning)。监督学习的训练样本可以统一成如下形式,其中x为变量,y为标记。

显然,现实生活中不是所有数据都带有标记(或者说标记是未知的)。所以我们需要对无标记的训练样本进行学习,来揭示数据的内在性质及规律。我们把这种学习称为无监督学习(Unsupervised Learning)。所以,无监督学习的训练样本如下形式,它仅包含特征量。

图9-1形象的表示了监督学习与无监督学习的区别。图(1)表示给带标记的样本进行分类,分界线两边为不同的类(一类为圈,另一类为叉);图(2)是基于变量x1和x2对无标记的样本(表面上看起来都是圈)进行聚类(Clustering)

图9-1 一个监督学习与无监督学习的区别实例

无监督学习也有很多应用,一个聚类的例子是:对于收集到的论文,根据每个论文的特征量如词频,句子长,页数等进行分组。聚类还有许多其它应用,如图9-2所示。一个非聚类的例子是鸡尾酒会算法,即从带有噪音的数据中找到有效数据(信息),例如在嘈杂的鸡尾酒会你仍然可以注意到有人叫你。所以鸡尾酒会算法可以用于语音识别(详见wikipedia)。

quora上有更多关于监督学习与无监督学习之间的区别的讨论

图9-2 一些聚类的应用

9.2 K-means algorithm

聚类的基本思想是将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个""(cluster)。划分后,每个簇可能有对应的概念(性质),比如根据页数,句长等特征量给论文做簇数为2的聚类,可能得到一个大部分是包含硕士毕业论文的簇,另一个大部分是包含学士毕业论文的簇。

K均值(K-means)算法是一个广泛使用的用于簇划分的算法。下面说明K均值算法的步骤:

  1. 随机初始化K个样本(点),称之为簇中心(cluster centroids)
  2. 簇分配: 对于所有的样本,将其分配给离它最近的簇中心;
  3. 移动簇中心:对于每一个簇,计算属于该簇的所有样本的平均值,移动簇中心到平均值处;
  4. 重复步骤2和3,直到找到我们想要的簇(即优化目标,详解下节9.3)

图9-3演示了以特征量个数和簇数K均为2的情况。

上述算法中,第一个循环对应了簇分配的步骤:我们构造向量c,使得c(i)的值等于x(i)所属簇的索引,即离x(i)最近簇中心的索引。用数学的方式表示如下:

第二个循环对应移动簇中心的步骤,即移动簇中心到该簇的平均值处。更数学的方式表示如下:

其中

都是被分配给簇

的样本。

如果有一个簇中心没有分配到一个样本,我们既可以重新初始化这个簇中心,也可以直接将其去除。

经过若干次迭代后,该算法将会收敛,也就是继续迭代不会再影响簇的情况。

在某些应用中,样本可能比较连续,看起来没有明显的簇划分,但是我们还是可以用K均值算法将样本分为K个子集供参考。例如根据人的身高和体重划分T恤的大小码,如图9-4所示。

图9-4 K-means for non-separated clusters

9.3 Optimization objective

9.4 Random Initialization

9.5 Choosing the Number of Clusters

选择K的取值通常是主观的,不明确的。也就是没有一种方式确保K的某个取值一定优于其他取值。但是,有一些方法可供参考。

The elbow method : 画出代价J关于簇数K的函数图,J值应该随着K的增加而减小,然后趋于平缓,选择当J开始趋于平衡时的K的取值。如图9-5的(1)所示。

但是,通常这条曲线是渐变的,没有很显然的"肘部"。如图9-5的(2)所示。

图9-5 代价J关于簇数K的曲线图

注意:随着K的增加J应该总是减少的,否则,一种出错情况可能是K均值陷入了一个糟糕的局部最优。

一些其他的方法参见wikipedia

当然,我们有时应该根据后续目的( later/downstream purpose )来确定K的取值。还是以根据人的身高和体重划分T恤的大小码为例,若我们想将T恤大小划分为S/M/L这3种类型,那么K的取值应为3;若想要划分为XS/S/M/L/XL这5种类型,那么K的取值应为5。如图9-6所示。

图9-6 划分T恤size的两种不同情况

【推荐阅读】讨论K均值算法的缺点

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习之旅

理论:聚类算法思路总结

常见的为欧式距离(L1 norm)&&p=2,拓展的可以有闵可夫斯基距离(L2 norm)&&p=1:

462
来自专栏WD学习记录

机器学习 学习笔记(5) 线性回归

给定数据集D={(x1,y1),(x2,y2),...,(xm,ym)},其中xi=(xi1;xi2;xi3;...;xid),yi是实数。线性回归试图学得一个...

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

机器学习(28)【降维】之sklearn中PCA库讲解与实战

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 前言 在(机器学习(27)【降维】之...

4086
来自专栏https://www.cnblogs.com/L

【机器学习】--Kmeans从初识到应用

Kmeans算法一般在数据分析前期使用,选取适当的k,将数据分类后,然后分类研究不同聚类下数据的特点。

532
来自专栏小鹏的专栏

感知机--模型与策略

看到模型和策略,应该很快联想到了李航的《统计学习方法》,统计学习方法的三要素定义为:模型、策略、算法。 感知机 感知机是二分类的线性分类模型,输入为实例的...

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

深度学习之DNN与前向传播算法

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 深度神经网络(Deep Neu...

2874
来自专栏AILearning

【机器学习实战】第8章 预测数值型数据:回归

第8章 预测数值型数据:回归 <script type="text/javascript" src="http://cdn.mathjax.org/mathj...

3636
来自专栏ATYUN订阅号

5种主要聚类算法的简单介绍

AiTechYun 编辑:Yining 聚类是一种机器学习技术,它涉及到数据点的分组。给定一组数据点,我们可以使用聚类算法将每个数据点划分为一个特定的组。理论上...

2674
来自专栏算法channel

北大才女笔记:这样学习线性回归和梯度下降(上篇)

我们说到,机器学习中主要的两个任务就是回归和分类。如果读者有高中数学基础,我们很容易回忆到我们高中学习过的一种回归方法——线性回归。我们将这种方法泛化,就可以得...

870
来自专栏机器之心

教程 | 从头开始:用Python实现带随机梯度下降的Logistic回归

选自machine learning mastery 机器之心编译 参与:Jane W、Panda logistic 回归是一种著名的二元分类问题的线性分类算...

47110

扫描关注云+社区