Tag Archives: 聚类

K-Means 聚类

预先选择聚集数量k。

  1. 初始化k个中心点
  2. 每一次迭代时:
    将每个数据点分配给与其“最近”的中心点
    对每一个中心点,更新其新的位置为所有属于其的节点的“平均位置"
  3. 重复1-2 直至收敛(一次迭代后,没有数据点被重新分配过)

仍旧是之前层次聚类时用到的例子数据:

得到2个聚集,聚集1为0,1,2三个数据点,聚集2为3,4,5三个数据,看下可视化结果,看看这个聚类是否有直觉上的意义。

红色点为聚集的中心位置

figure_1

用scikit learn的kmeans,对例子数据聚类:

结果是一致的。

如何选择k?

  • 尝试不同的k,看各个数据点到所属中心点的距离。
    如果k较少,则会有许多较大的距离
    如果k较大,则距离通常非常小

如何选择一开始的k个中心点?

  1. 抽样
    抽样一部分数据点,使用层次聚类,找出k的值
    从层次聚类的k个类中各取一个点作为中心点
  2. 先随机选一个点作为中心点
    再剩下点中,找到一个与已选点距离最远的点作为中心点
    反复上述过程直至获得k个点

Hierarchical Clustering 层次聚类

从下至上的层次聚类:

  1. 初始时,每一个数据点单独构成一个聚集
  2. 不断地将最近的两个聚集合并

需要决定:

  1. 聚集之间的距离度量
  2. 定义聚集合并后如何表示
  3. 何时停止聚类

常见方法:

  • 用中心点表示聚集,中心点与聚集内各个节点“最近”(平均距离最小、最大距离最小,距离的平方和最小等等)
  • 用聚集于聚集的中心点之间的距离表示聚集之间的距离

例子:

6个数据点:(1,2),(2,1),(0,0),(5,3),(5,0),(4,1)

输出的是每一轮合并聚集后,新聚集内包括的数据点

scipy中有层次聚类,对例子数据的聚类结果与上面一直。

figure_1

聚类的终止标准:

  1. 预先设定聚集数量k,一旦形成k个聚集就停止
  2. 当新生成的聚集的“凝聚力”(cohesion)小于阈值

凝聚力:

  1. 聚集的直径 = 全局中节点之间的最大距离
  2. 聚集内节点与中心点之间的距离超过预先设定的最大值
  3. 聚集内的节点密度大于预先设定值

 

Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

什么样的聚集是好的聚集?

  1. 希望聚集内的相互连接尽量多
  2. 希望聚集内的节点与聚集外的节点之间连接尽量少

定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。

先用AGM生成一个网络:

CutPlot1

假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:

Cut值并不是一个非常好的指标,如果包含度为1的节点,那么仅仅由节点一个节点构成的聚类,Cut值为1。

另一个可能的指标是Conductance(越低越好):

phi(A) = frac{text{cut(A)}}{min(vol(A), 2m-vol(A))}

其中:

  1. cut(A)是聚集A的cut分值
  2. vol(A)是聚集A的所有节点的度的和
  3. m 是网络内边的总数

2  图谱理论(Spectral Graph Theory)和谱聚类

分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。

CutPlot1

定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差:

该矩阵有两个重要属性:

  1. 特征值都是非负实数
  2. 特征向量都是实数,并且相互垂直

一些通过线性代数可获得事实:

令拉普拉斯矩阵的特征值为lambda,特征向量为x

特征向量有两个重要属性:

  1. 是单位向量:sum_ix_i^2=1
  2. 与第一个特征向量垂直:sum_ix_icdot 1 = 0

特征值lambda _2是该表达式的最优解:

min_{x}frac{x^TMx}{x^Tx}=min_{x}sum_{i,j}(x_i-x_j)^2

因此上面的最小化问题的物理意义是将节点一部分放在<0出,另一部分放在>0处(sum_ixi=0)  ,并且使得连接两端的边尽量地小(min_{x}sum_{i,j}(x_i-x_j)^2

具体参见Rayleigh quotientFiedler vector,以及一个挺有帮助的slides

谱聚类步骤:

  1. 预处理:用拉普拉斯矩阵表示网络
  2. 分解:计算矩阵的特征值和特征向量,找到lambda_2对应的特征向量x(这样每一个节点就用一个值来表示了)
  3. 聚类:决定若干分割值,根据特征向量的值与分割值的关系,将各个节点归属到不同聚集

分割点的选择:

  1. 简单地选择0或者中位数
  2. 尝试最小化正则化的1维cut值

如果希望有多个聚集,方法有两类:

  1. 递归地进行2分聚类
  2. lambda_2lambda_3等后续特征值对应的特征向量进行K-means

机器学习笔记 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