落园 » 统计学习精要(The Elements of Statistical Learning)课堂笔记(二十四):聚类|专注经济视角下的互联网

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十四):聚类

聚类讲的比较简单...怎么感觉老师不怎么待见unsupervised learning捏?...

---------------笔记开始---------------------

1. 一般概念

1)分类与聚类(分类标识)

评测纯度。我们有测试集\{x_{i}\},这样定义纯度为p_{k}=\frac{m_{k}}{N_{k}}\leq1,\forall k.

2) 输入

  • 特征向量的表示:\{x_{i},1\leq i\leq N\},x_{i}\in\mathbb{R}^{p}
  • 相似矩阵的表示:S=\{s_{ij},1\leq i,j\leq N\},其中相似度的计算可以是s_{ij}=(x_{i}-\bar{x},x_{j}-\bar{x})的内积。显然,向量表示很容易可以计算相似度表示。
  • 距离矩阵的表示(不相似度):D=\{d(i,j),1\leq i,j\leq N\},其中距离可以用二阶范数定义,比如d(i,j)=\left\Vert x_{i}-x_{j}\right\Vert ^{2}

3) 输出: \{c_{k}\},对应K个聚类。这里还分为:

  • 非层次的
  • 层次的(类似于树结构)

2. K-means方法(非层次聚类)

(注意不要和KNN搞混了,都是K开头的...)

1) K-means方法(特征表示)

输入:\{x_{i},1\leq i\leq N\},K——聚类的个数。

算法:

初始化,随机选定类中心\{c_{k}\}.

  • (i)根据\{c_{k}\}分配x_{i}到距离最近的类。
  • (ii)修改\{c_{k}\},使得c'(k)=mean(x_{i}|x_{i}\in C_{k})。重复上面两步。

2) K-medoids方法(相似度表示)

输入:s,k

初始化。然后根据\arg\min_{c_{k}}s(x_{i},c_{k})分配x_{i},再按照\arg\max_{c_{k}}\sum_{x\in C_{k}}s(x_{i},c_{k})确定新的中心。

3) 模糊的K-means方法

输入:\{x_{i},1\leq i\leq N\},K

初始化。

  • (i) \forall x_{i},计算\left\Vert x_{i}-c_{k}\right\Vert ,\forall k,然后根据这个距离的比重来“软”分配x_{i}(需要归一化分配权重)。
  • (ii) \forall c_{k},利用c_{k}中的x_{i}进行加权平均。

重复上述两步。

4) 谱聚类(向量表示)

输入:\{x_{i},1\leq i\leq N\},K

然后对原始数据做转换,形成新的数据集\{z_{i},1\leq i\leq N\},然后再做K-means聚类。

其中转换的步骤如下:

  • (i) 计算相似矩阵S
  • (ii) 计算L=D-S,其中D=\left[\begin{array}{ccc}D_{1}\\ & \ddots\\ & & D_{N} \end{array}\right]D_{i}=\sum_{j=1}^{N}D_{ij}
  • (iii)计算L最小的K个特征值对应的特征向量
  • (iv)让U=(u_{1},\cdots,u_{k}),则z_{i}是U的第i行,这样就从p维降到了K维。
  • (v)对Z进行K-means聚类。

3. 层次聚类

1) 自底向上的方法(聚合)

初始:每个x_{i}都为一类

而后对于最相似的两类,合并到一类。对于类的最相似,可以定义为距离最近的类。而对于距离,则可以定义为三者之一:

  • (i) d_{AB}=\min d(i,j),i\in A,j\in B,称之为单连。
  • (ii) d_{AB}=\max d(i,j),i\in A,j\in B,称之为全连。
  • (iii) d_{AB}=\frac{\sum d(i,j)}{\left\Vert A\right\Vert \left\Vert B\right\Vert }.

2) 自顶向下的方法(分裂)

初始:所有的x作为一类。选用一种非层次的方法进行聚类,递归使用。

例子:二分法。

初始:G=\{x_{i}\}H=\emptyset。而后选择离G最远的一个点g。

修改G'=G\backslash gH=H\bigcup g。重复步骤,选择离H近的离G远的逐渐加入H。

直到分不动了,彻底分为两类。

---------------------

下节课讲的是降维方法。


Comments

  • Tao says:

    "老师不怎么待见unsupervised learning捏?" 好像这里面没有什么定理可以证明,所以也就没法发好杂志,做的人就少了。可能是因为对结果好坏的衡量很少有好的方法。几十年了,就是大名鼎鼎的k-means的性质也就一两篇理论文章而已。我费劲的做的也很痛苦。


  • Tao says:

    问我吗?如果你做过工程,就发现聚类在编码和数据压缩中起很核心作用,基本上以点带面的思想。数据降维也是这样的思想,到最近的sparse coding 都在走这些路。你做evaluation的,不用太做exploration,所以不太需要。经济学家关心因果关系,更不关心底层数据处理这些了。


    • liyun says:

      原来是这些地儿!我怎么感觉都是cs的人在鼓捣的呢,哈哈。话说我在这边唯一见过的就是麦肯锡卖给我们好贵的一个用户聚类,聚出来六七类的样子...第一反应就是聚类好值钱...


  • 紫颜 says:

    怎么也搜不到二十三,统计精要页面的二十三链接到二十四T-T


Leave a Reply

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