机器学习(7) -- k-means 聚类

根据大家的提议,从今天起每次算法介绍完之后会给大家一个用python编写的实例刚打架参考

Clustering

 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的情况。

图9-3 K均值算法的演示

通过上述描述,下面我们形式化K均值算法。

输入:

  • K (number of clusters)
  • Training set

, where x^{(i)}\in R^n (drop x_{0}=1 convention)

算法:

Randomly initialize K cluster centroids \mu_{1},...,\mu_{K}\in R^n

Repeat { for i = 1 to m c^{(i)} := index (from 1 to K ) of cluster centroid closest to x^{(i)} for k = 1 to K \mu_{k} := average (mean) of points assigned to cluster }

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

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

其中

都是被分配给簇\mu_{k} 的样本。

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

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

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

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

9.3 Optimization objective

重新描述在K均值算法中使用的变量:c^{(i)} = index of cluster (1,2,…, K ) to which example x^{(i)} is currently assigned\mu_{k} = cluster centroid k (\mu_{k}\in R^n )\mu_{c^{(i)}} = cluster centroid of cluster to which example x^{i} has been assigned

使用这些变量,定义我们的cost function如下:

所以我们的优化目标就是

结合9.2节所描述的算法,可以发现:

  • 在簇分配步骤中,我们的目标是通过改变c^{(1)},...,c^{(m)} 最小化J函数(固定\mu_{1},...,\mu_{K} )
  • 在移动簇中心步骤中,我们的目标通过改变\mu_{1},...,\mu_{K}

最小化J函数(固定c^{(1)},...,c^{(m)}

注意,在K均值算法中,cost function不可能能增加,它应该总是下降的(区别于梯度下降法)。

9.4 Random Initialization

下面介绍一种值得推荐的初始化簇中心的方法。

  1. 确保K < m,也就是确保簇的数量应该小于样本数;
  2. 随机选择K个训练样本;
  3. 令K个簇中心\mu_{1},...,\mu_{K}

等于K个训练样本。

K均值算法可能陷入局部最优。为了减少这种情况的发生,我们可以基于随机初始化,多次运行K均值算法。所以,算法变成如下形式(以运行100次为例:效率与准确性的tradeoff)

For i = 1 to 100 { Randomly initialize K-means. Run K-means. Get

Compute cost function (distortion)

} Pick clustering that gave lowest cost

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的两种不同情况

附例程的python代码

print __doc__

# Author: Guodongwei 2016-06-08

#License: BSD 3 clause

import numpy as np

import matplotlib.pyplot as plt

from sklearn.cluster import KMeans

from sklearn.datasets import make_blobs

plt.figure(figsize=(12, 12))

n_samples = 1500

random_state = 170

X, y = make_blobs(n_samples=n_samples, random_state=random_state)

# Incorrect number of clusters

y_pred = KMeans(n_clusters=2, random_state=random_state).fit_predict(X)

plt.subplot(221)

plt.scatter(X[:, 0], X[:, 1], c=y_pred)

plt.title("Incorrect Number of Blobs")

# Anisotropicly distributed data

transformation = [[ 0.60834549, -0.63667341], [-0.40887718, 0.85253229]]

X_aniso = np.dot(X, transformation)

y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_aniso)

plt.subplot(222)

plt.scatter(X_aniso[:, 0], X_aniso[:, 1], c=y_pred)

plt.title("Anisotropicly Distributed Blobs")

# Different variance

X_varied, y_varied = make_blobs(n_samples=n_samples,

cluster_std=[1.0, 2.5, 0.5],

random_state=random_state)

y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_varied)

plt.subplot(223)

plt.scatter(X_varied[:, 0], X_varied[:, 1], c=y_pred)

plt.title("Unequal Variance")

# Unevenly sized blobs

X_filtered = np.vstack((X[y == 0][:500], X[y == 1][:100], X[y == 2][:10]))

y_pred = KMeans(n_clusters=3, random_state=random_state).fit_predict(X_filtered)

plt.subplot(224)

plt.scatter(X_filtered[:, 0], X_filtered[:, 1], c=y_pred)

plt.title("Unevenly Sized Blobs")

plt.show()

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2016-06-08

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

SoftMax回归详解

Contents 1 关键词 2 引言 3 代价函数 4 softmax回归模型参数化的特点 5 权重衰减 6 softmax与logistics回归的关系 1...

4368
来自专栏Spark学习技巧

读懂Word2Vec之Skip-Gram

本教程将介绍Word2Vec的skip gram神经网络体系结构。我这篇文章的目的是跳过对Word2Vec的一般的介绍和抽象见解,并深入了解其细节。具体来说,我...

3777
来自专栏mantou大数据

[机器学习Lesson 2]代价函数之线性回归算法

x(1) 指的是 第一个训练集里值为2104的输入值, 这个就是第一行里的x x(2) 等于1416。这是第二个x y(1) 等于460,这是第一个训练集样本的...

50510
来自专栏数据科学与人工智能

【深度学习】深度学习概述:从感知机到深度网络

近些年来,人工智能领域又活跃起来,除了传统了学术圈外,Google、Microsoft、facebook等工业界优秀企业也纷纷成立相关研究团队,并取得了很多令人...

33410
来自专栏机器学习与自然语言处理

信息量,熵,交叉熵,相对熵与代价函数

如果有⼈告诉我们⼀个相当不可能的事件发⽣了,我们收到的信息要多于我们被告知某个很可能发⽣的事件发⽣时收到的信息。如果我们知道某件事情⼀定会发⽣,那么我们就不会接...

1277
来自专栏计算机视觉战队

前馈神经网络和BP算法简单教程

吴立德老师亲自讲解前馈神经网络和BP算法,让初学者对基础更加了解,对以后网络的改建和创新打下基础,值得好好学习!希望让很多关注的朋友学习更多的基础知识,打下牢固...

3516
来自专栏编程

深度学习中的损失函数总结以及Center Loss函数笔记

目标函数,损失函数,代价函数 损失函数度量的是预测值与真实值之间的差异.损失函数通常写做L(y_,y).y_代表了预测值,y代表了真实值. 目标函数可以看做是优...

6178
来自专栏用户2442861的专栏

深度学习概述:从感知机到深度网络

http://www.cnblogs.com/xiaowanyer/p/3701944.html

931
来自专栏IT派

对数几率回归 —— Logistic Regression

首先,在引入LR(Logistic Regression)模型之前,非常重要的一个概念是,该模型在设计之初是用来解决0/1二分类问题,虽然它的名字中有回归二字,...

1312
来自专栏自学笔记

Neural Network

重新回顾一下一开始学的PLA,preceptron learning Algorithm。PLA适用于二维及高维的线性可分的情况,如果是非线性可分的数据,如果使...

2412

扫码关注云+社区

领取腾讯云代金券