聚类clustering

图9-1形象的表示了监督学习与无监督学习的区别。图(1)表示给带标记的样本进行分类，分界线两边为不同的类(一类为圈，另一类为叉)；图(2)是基于变量x1和x2对无标记的样本(表面上看起来都是圈)进行聚类(Clustering)。

图9-1 一个监督学习与无监督学习的区别实例

无监督学习也有很多应用，一个聚类的例子是：对于收集到的论文，根据每个论文的特征量如词频，句子长，页数等进行分组。聚类还有许多其它应用，如图9-2所示。

K-means algorithm

聚类的基本思想是将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个"簇"(cluster)。划分后，每个簇可能有对应的概念(性质)，比如根据页数，句长等特征量给论文做簇数为2的聚类，可能得到一个大部分是包含硕士毕业论文的簇，另一个大部分是包含学士毕业论文的簇。

K均值(K-means)算法是一个广泛使用的用于簇划分的算法。下面说明K均值算法的步骤：

随机初始化K个样本(点)，称之为簇中心(cluster centroids)；

簇分配: 对于所有的样本，将其分配给离它最近的簇中心；

移动簇中心：对于每一个簇，计算属于该簇的所有样本的平均值，移动簇中心到平均值处；

重复步骤2和3，直到找到我们想要的簇（即优化目标，详解下节9.3）

图9-3演示了以特征量个数和簇数K均为2的情况。

图9-3 K均值算法的演示

有限混合模型

是一个具有k个部分的混合的分布

EM 算法(Expectation Maximisation) algorithm

简版：猜（E-step）,反思（M-step）,重复；

啰嗦版：

你知道一些东西（观察的到的数据）， 你不知道一些东西（观察不到的），你很好奇，想知道点那些不了解的东西。怎么办呢，你就根据一些假设（parameter）先猜（E-step），把那些不知道的东西都猜出来，假装你全都知道了; 然后有了这些猜出来的数据，你反思一下，更新一下你的假设（parameter）, 让你观察到的数据更加可能(Maximize likelihood; M-stemp); 然后再猜，在反思，最后，你就得到了一个可以解释整个数据的假设了。

一、机器学习中的参数估计问题

此时，使用极大似然估计便能够估计出模型中的参数。但是，如果此时的标签是未知的，称为隐变量，如无监督的学习问题，典型的如K-Means聚类算法，此时不能直接通过极大似然估计估计出模型中的参数。

二、EM算法简介

    在上述存在隐变量的问题中，不能直接通过极大似然估计求出模型中的参数，EM算法是一种解决存在隐含变量优化问题的有效方法。EM算法是期望极大(Expectation Maximization)算法的简称，EM算法是一种迭代型的算法，在每一次的迭代过程中，主要分为两步：即求期望(Expectation)步骤和最大化(Maximization)步骤。

如何评价聚类结果的好坏？ Evaluating the Cluster Outputs

半监督学习Semi-supervised Learning

介绍

什么是半监督学习？既有有标记数据 xr，又有无标记数据 xu，一般无标记数据的数量远大于有标记数据。半监督学习又可以分为两种：

Transductive learning:无标记数据就是Testing data.

Inductive learning:无标记数据不是 testing data，假设在训练时不知道 testing set.

为什么要用半监督学习（Semi-supervised learning）？

因为收集数据比较容易，但是收集label数据的代价却很昂贵。

半监督学习与直推式学习的区别:

这个网上也有论述.主要就是半监督学习是归纳式的,生成的模型可用做更广泛的样本;而直推式学习仅仅为了当前无标记样本的分类.

简单的说,前者使用无标记样本,为了以后其他样本更好的分类.

后者只是为了分类好这些有限的无标记样本.

下面几个图来生动形象地诠释半监督的好处:

上图中,只有两个标记样本,X,O,剩下绿点是无标记的样本.通过无标记样本的加入,原来的分类界限从0移到了0.5处,更好地拟合了样本的现实分布.

self-training算法:

还是两个样本集合:Labled={(xi,yi)};Unlabled= {xj}.

执行如下算法

Repeat:

1.      用L生成分类策略F;

2.      用F分类U,计算误差

3.      选取U的子集u,即误差小的,加入标记.L=L+u;

重复上述步骤,直到U为空集.

上面的算法中,L通过不断在U中,选择表现良好的样本加入,并且不断更新子集的算法F,最后得到一个最有的F.

Self-training的一个具体实例:最近邻算法

记d(x1,x2)为两个样本的欧式距离,执行如下算法:

Repeat:

1.      用L生成分类策略F;

2. 选择x = argmin d(x, x0). 其中x∈U,min x0∈L.也就是选择离标记样本最近的无标记样本.

2.      用F给x定一个类别F(x).

3.      把(x,F(x))加入L中

重复上述步骤,直到U为空集.

上面算法中,也就是定义了self-training的”误差最小”,也就是用欧式距离来定义”表现最好的无标记样本”,再用F给个标记,加入L中,并且也动态更新F.

下面是这种算法的效果图:

上图从两个点出发,不断加入最近邻点,不断更新F.

上面的算法表现良好,当然更多的是表现不好.如下:

 

 Active Learning主动学习