机器学习笔记 Week8 聚类

学习笔记(Machine Learning) Week8

全部笔记PDF版:http://vdisk.weibo.com/s/J4rRX/1373287206

Week8 由两部分内容构成:

  1. 聚类
  2. 降维

1 聚类(Clustering)

1.1K-均值算法

K-均值是最普及的聚类算法,算法接受一个未标记的数据集,然后将数据聚类成不同的组。

K-均值是一个迭代算法,假设我们想要将数据聚类成n个组,其方法为:

  1. 首先选择K个随机的点,称为聚类中心(cluster centroids)
  2. 对于数据集中的每一个数据,按照距离K个中心点的距离,将其与距离最近的中心点关联起来,与同一个中心点关联的所有点聚成一类
  3. 计算每一个组的平均值,将该组所关联的中心点移动到平均值的位置
  4. 重复步骤2-4直至中心点不再变化

下面是一个聚类示例:

71f098cajw1e5nslfvkddj20sh0et41l

71f098cajw1e5nslga1wpj20sh0et77g

71f098cajw1e5nslhjyrij20sh0etq65

用μ12,...,μk来表示聚类中心,用c(1),c(2),...,c(m)来存储与第i个实例数据最近的聚类中心的索引,K-均值算法的伪代码如下:
Repeat {
for i = 1 to m
c(i) := index (form 1 to K) of cluster centroid closest to x(i)
for k = 1 to K
μk := average (mean) of points assigned to cluster k
}
算法分为两个步骤,第一个for循环是赋值步骤,第二个for循环是聚类中心的移动。

K-均值算法也可以很便利地用于将数据分为许多不同组,即使在没有非常明显区分的组群的情况下也可以。下图所示的数据集包含身高和体重两项特征构成的,利用K-均值算法将数据分为三类,用于帮助确定将要生产的T-恤衫的三种尺寸。

QQ截图20130704115346

1.2优化目标

K-均值最小化问题,是要最小化所有的数据点与其所关联的聚类中心点之间的距离之和,因此K-均值的代价函数(又称畸变函数Distortion function)为:

图片1

其中μc(i)代表与x(i)最近的聚类中心点。
我们的的优化目标便是找出使得代价函数最小的c(1),c(2),...,c(m)和μ12,...,μk

图片2

回顾刚才给出的K-均值迭代算法,我们知道,第一个循环是用于减小c(i)引起的代价,而第二个循环则是用于减小μi引起的代价。迭代的过程一定会是每一次迭代都在减小代价函数,不然便是出现了错误。

1.3随机初始化

在运行K-均值算法的之前,我们首先要随机初始化所有的聚类中心点,下面介绍怎样做:

  1. 我们应该选择K<m,即聚类中心点的个数要小于所有训练集实例的数量
  2. 随机选择K个训练实例,然后令K个聚类中心分别与这K个训练实例相等

K-均值的一个问题在于,它有可能会停留在一个局部最小值处,而这取决于初始化的情况。

为了解决这个问题,我们通常需要多次运行K-均值算法,每一次都重新进行随机初始化,最后再比较多次运行K-均值的结果,选择代价函数最小的结果。这种方法在K较小的时候(2-10)还是可行的,但是如果K较大,这么作也可能不会有明显地改善。

1.4选择聚类数

没有所谓最好的选择聚类数的方法,通常是需要根据不同的问题,人工进行选择的。选择的时候思考我们运用K-均值算法聚类的动机是什么,然后选择能最好服务于该目的标聚类数。

例如,我们的T-恤制造例子中,我们要将用户按照身材聚类,我们可以分成3个尺寸S,M,L也可以分成5个尺寸XS,S,M,L,XL,这样的选择是建立在回答“聚类后我们制造的T-恤是否能较好地适合我们的客户”这个问题的基础上作出的。

课程地址:https://class.coursera.org/ml-003/class/index

Leave a Reply

Your email address will not be published. Required fields are marked *