Press "Enter" to skip to content

AI遮天传 ML-无监督学习

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

一、无监督学习介绍

 

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

贪婪 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)

对于监督学习:

 

 

我们通过多个样例<xi,yi>来训练模型,对于一个需要预测的样例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)

 

类相似度

 

 

实例:意大利城市的层次聚类

 

 

 

 

 

 

分裂式层次聚类(Divisive, top-down)

 

根据一个类中最大的间隔进行分裂

 

 

    1. 最大平均类内距离的点:Splinter group

 

    1. 其他点 :保持不变(Old party)

 

    1. 重复以下操作直到不再发生改变: 把满足MinDist_to_Splinter >= MinDis_to_Old的点:Splinter

 

 

 

分裂式层次聚类vs. 凝聚式层次聚类

 

 

层次聚类的相关讨论

 

优点

可以从不同粒度观察数据,十分灵活
可以方便适应各种形式的相似度定义
因此适用于各种属性类型

缺点

停止条件不确定
计算开销大、很难应用到大的数据集上

神经科学数据分析中的应用

 

 

四、K-means 聚类

 

算法:

给定一个类分配方案C,确定每个类的 均值向量 :{g1,…,gk}。
给定K个均值向量的集合{g1,…,gk},把每个对象分配给距离均值 最近 的类。
重复上述过程直到评价函数不发生变化。

不保证找到最优解

 

 

 

 

算法的收敛性

 

 

 

 

K-means 算法特性小结

 

模型: 向量空间模型

 

策略: 最小化类内对象的欧式距离

 

算法: 迭代

 

硬聚类

 

非层次

 

K-means 算法举例

 

 

应用举例:不仅仅是聚类 —— 图像压缩

 

数据:所有像素

 

特征:RGB值

 

 

每个像素根据所属类的中心对应的 {R,G,B} 值进行重画

 

K-means讨论:如何确定“k”?

问题驱动

通常问题本身会设定一个需要的 K 值

只有满足下列条件之一时,可以是 ”数据驱动” 的

数据不稀疏
度量的维度没有明显噪音

如果 K 值没有给定

计算类间不相似度 Wk (与类间相似度相反) (或者检验类内相似度) —— 与 K 相关的函数
一般来说, K 值增加,Wk 值降低

方法1:

 

 

方法2 :

 

 

K-means :更多讨论

当数据呈几个紧凑且互相分离的云状时效果很好
对于非凸边界的类或类大小非常不一致的情况也适用
对噪声和离群点非常敏感

五、K- medoids

 

用 medoid – 用 最靠近类中心的对象 作为类的参考点 而不是用类的均值

 

基本策略:

找到 n 对象中的 k 个类,随机确定每个类的 代表对象
迭代:

其他所有对象根据距离最近的类中心进行类的分配
计算使得cost最小的类中心

重复直到不再发生变化
代价函数:类内对象与类中心的 平均不相似度

K- medoids改进算法:PAM(Partitioning Around Medoids)

 

基本策略:

找到 n 对象中的 k 个类,随机确定每个类的 代表对象
迭代:

其他所有对象根据距离最近的类中心进行类的分配
随机用一个非中心对象替换类中心
类的质量提高则保留替换

类的质量

 

代价函数:类内对象与类中心的 平均不相似度

 

如总代价为20

 

 

K-Medoids讨论

 

优点:

当存在 噪音和孤立点 时, K-medoids 比 K-means 更鲁棒
如果能够迭代所有情况,那幺最终得到的划分一定是最优的划分,即聚类 结果最好

缺点:

K-medoids 对于小数据集工作得很好, 但不能很好地用于大数据集
计算中心的步骤 时间复杂度是O(n^2) ,运行速度较慢

基于大样本的改进算法:CLARA(Clustering LARge Applications)

 

基本策略:当面对大样本量时:

每次随机选取样本量中的一小部分进行PAM聚类
将剩余样本按照最小中心距离进行归类
在各次重复抽样聚类的结果中,选取误差最小,即中 心点代换代价最小的结果作为最终结果

无监督学习总结

 

有监督 v.s. 无监督学习

 

聚类

数据及相似度度量

层次聚类

凝聚式 (从下到上)
分裂式 (从上到下)

K-means 聚类

 

K-medoids 聚类(及其变种与改进:PAM,CLARA)

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。