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 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

机器学习(七) ——logistic回归

机器学习(七)——logistic回归 (原创内容,转载请注明来源,谢谢) 一、概述 1、基本概念 logistic回归(logisticre...

3226
来自专栏目标检测和深度学习

卷积神经网络工作原理直观的解释

742
来自专栏数据派THU

开发者必看:超全机器学习术语词汇表!

来源:机器之心 本文长度为12243字,建议阅读8分钟 本文编译自谷歌开发者机器学习术语表项目,介绍了该项目所有的术语与基本解释。 A 准确率(accuracy...

2916
来自专栏机器学习之旅

理论:正则化-Lasso规约

图中,红色的线存在明显的过拟合,绿色的线才是合理的拟合曲线,为了避免过拟合,我们可以引入正则化。

672
来自专栏SimpleAI

【DL笔记1】Logistic Regression:最基础的神经网络

从【DL笔记1】到【DL笔记N】,是我学习深度学习一路上的点点滴滴的记录,是从Coursera网课、各大博客、论文的学习以及自己的实践中总结而来。从基本的概念、...

532
来自专栏AI研习社

如何解决机器学习中的数据不平衡问题?

在机器学习任务中,我们经常会遇到这种困扰:数据不平衡问题。 数据不平衡问题主要存在于有监督机器学习任务中。当遇到不平衡数据时,以总体分类准确率为学习目标的传统分...

3449
来自专栏超然的博客

Context-Aware Network Embedding for Relation Modeling

论文:http://www.aclweb.org/anthology/P17-1158

671
来自专栏SIGAI学习与实践平台

网络表征学习综述

当前机器学习在许多应用场景中已经取得了很好的效果,例如人脸识别与检测、异常检测、语音识别等等,而目前应用最多最广泛的机器学习算法就是卷积神经网络模型。但是大多应...

823
来自专栏ATYUN订阅号

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

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

2704
来自专栏SeanCheney的专栏

《Scikit-Learn与TensorFlow机器学习实用指南》 第5章 支持向量机

支持向量机(SVM)是个非常强大并且有多种功能的机器学习模型,能够做线性或者非线性的分类,回归,甚至异常值检测。机器学习领域中最为流行的模型之一,是任何学习机器...

832

扫码关注云+社区