一、无监督学习介绍

机器学习算法分类(不同角度)：

贪婪 vs. 懒惰
参数化 vs. 非参数化
有监督 vs. 无监督 vs. 半监督
……

什么是无监督学习？（unsupervised learning）

解释 1

有监督：涉及人力(human label)的介入
无监督：不牵扯人力(是否要通过人来给一些label分辨属于哪些类别)

解释 2

给定一系列数据: x1 , x2 , . . . , xN
- 有监督：期望的输出同样给出 y1 , y2 , . . . , yN
- 无监督：没有期望输出

解释 3

有监督：学习的知识关注条件分布 P(Y|X)
- X = 样例（用其特征来表示）, Y = 类别
无监督：学习的知识关注联合分布 P(X)，
- X： X1 , X2, …, Xn
半监督学习：通过一些（少量）有标注的数据和很多无标注的数据学习条件分布 P(Y|X)

对于监督学习：

我们通过多个样例来训练模型，对于一个需要预测的样例xn+1，我们通过训练完的模型对其进行预测，得到yn+1，(x一般很复杂，有多种特征值，y一般比较简单，比如是某分类)如：

对于无监督学习

对于给的一组x1…xn，我们一般会预测下一个xn+1是什么样，或者x1…xn它们是一个什么样的结构组成的。

对于半监督学习

有一堆数据(1,2…n…m)，有一些是由标注的，还有一些是没有y的(m>>n)，对于有标注的那部分，我们还是以监督学习的方法的到模型去预测输入的样例。我们用100个数据去学习10000个数据，我们可以看对于那些没有标注(y)的，哪些与有标注的相类似(如果不使用基于实例的学习方法的话)。

无标注数据的结构

无监督学习中最重要的就是学到无标注数据的结构

构建模型找到输入的合理表示
- 可以用来做决策、预测未知数据、将输入高效迁移到其他学习器等
发现数据的结构
- 一篇学术论文包含题目、摘要……
- 半结构化网页中蕴含结构化信息
- 图片中的像素不是随机生成的
- 不同的用户兴趣组

对于一张图片，我们随即交换像素点和RGB后：

而实际上它是这样一张图片：

这里的结构信息就是什么样的像素RGB它们是在一起的。此外还涉及一些语义信息，比如我们在图片中可以看到有树，草地，天空，这些经过分割后，下一步才会做一些理解，比如右下角是一朵向日葵，阳光，中间的两个分开的房子…

ps:一个有趣的小问题：如果我们不知道它是一棵树，那怎么把它分割成一棵树了呢？如果没有办法把它分割出来，又怎么能知道它是一棵树呢？

我们可以用无标注数据干什么

数据聚类
- 在没有预先定义的类别时将数据分为不同的组(cluster/class)
降维
- 减少所需要考虑的变量数量(去掉较小的特征值。比如SVD矩阵分解方法。)
离群点检测
- 识别机器学习系统在训练中未发现的新数据/信号 Identification of new or unknown data or signal that a Machine Learning system is not aware of during training
刻画数据密度

二、聚类介绍

什么是聚类？

将相似的对象归入同一个“类”
- “Birds of a feather flock together. ” “物以类聚，人以群分”
- 发现数据的结构
使得同一个类中的对象互相之间关联更强
- 同一个类中的对象相似
- 不同类中的对象有明显差异
核心问题：相似度定义(距离)
- 簇/类内(intra-cluster)相似度
- 簇/类间(inter-cluster)相似度

什么样的聚类好？

通常，我们认为类内距离小，类间距离大的聚类更好。

聚类类型

软聚类（soft clustering） vs. 硬聚类（hard clustering）

软：同一个对象可以属于不同类
硬：同一个对象只能属于一个类(用的比较多)

如：

层次聚类 vs. 非层次聚类

层次：一个所有类间的层次结构（tree）
非层次：平的，只有一层

如:

聚类的应用

生物学
- 将同源序列分组到基因家族中
- 基因数据的相似度往往在聚类中被用于预测种群结构
图像处理 e.g. 自动相册
经济 – 尤其是市场商务智能
- 找到不同的顾客群体，e.g. 保险
WWW
- 文档/事件聚类，e.g. 每周新闻摘要
- WEB日志分析，e.g. 找到相似的用户
……

数据聚类需要什么？

无标注数据
对象间的距离或相似度度量
（可选）类间的距离或相似度度量
聚类算法
- 层次聚类
- K-means、K-mediods
- ……

数据

向量 x ∈ D1 × D2 · · · × DN
类型
- 实数值 Real: D=R
- 二值 Binary: D = {v1 ,v2 } e.g., {Female, Male}
- 非数值 Nominal: D = {v1 ,v2 ,…,vM} e.g., {Mon, Tue, Wed, Thu, Fri, Sat, Sun}
- 有序值 Ordinal: D = R or D = {v1 ,v2 ,…,vM}
- 用于顺序非常重要的场景 e.g., 排名

相似度度量

相似度 = ps:反比也不一定就是倒数
实数值数据
- 内积
- 余弦相似度
- 基于核
- …
回顾基于实例学习中的距离度量
- Minkowski 距离
  - Manhattan 距离、Euclidean 距离、Chebyshev 距离
- ……

非数值
- E.g. “Boston”, “LA”, “Pittsburgh”
- 或 “男” , “女”,
- 或 “弥散”, “球形”, “螺旋”, “风车”
- 二值
- 用对应的语义属性
  - E.g. Sim(Boston, LA) = a*dist(Boston, LA)-1 ,
  - Sim(Boston, LA) = a*(|size(Boston) – size(LA)|) / Max(size(cities))
- 用相似度矩阵

有序值
- E.g. “小” , “中”, “大”, “特大”
- 归一化成 [0,1] 间的实数值：
  - max(v)=1, min(v)=0, 其他进行插值
  - E.g. “小”=0, “中”=0.33, etc.
- 然后就可以使用实数值变量的相似度度量
- 可以用相似度矩阵

三、层次聚类

层次地构建一个类，比如一个由不同类组成的树状结构
- 父节点所涵盖的点被分割为兄弟类
以不同的粒度解释数据

凝聚式层次聚类算法(Agglomerative, bottom-up)

通过迭代过程得到嵌套式聚类结构
算法：（以文档聚类为例）
- 计算文档之间的相似系数
- 把n个文档中的每一个分配给自己构成一个簇
- 把最相似的两个簇类ci和cj合并成一个
  - 用新构成的簇类代替原来的两个簇
  - 重新计算其他簇与新生成簇之间的相似性
重复上述过程，直到只剩下k个簇(k可以等于1)