Categories

Calendar

May 2017
M T W T F S S
« Jun    
1234567
891011121314
15161718192021
22232425262728
293031  

漫谈 Clustering (番外篇): Dimensionality Reduction

本文是“漫谈 Clustering 系列”中的第 7 篇,参见本系列的其他文章。

由于总是有各种各样的杂事,这个系列的文章竟然一下子拖了好几个月,(实际上其他的日志我也写得比较少),现在决定还是先把这篇降维的日志写完。我甚至都以及忘记了在这个系列中之前有没有讲过“特征”(feature)的概念了,这里不妨再稍微提一下。机器学习应用到各个领域里,会遇到许多不同类型的数据要处理:图像、文本、音频视频以及物理、生物、化学等实验还有其他工业、商业以及军事上得到的各种数据,如果要为每一种类型的数据都设计独立的算法,那显然是非常不现实的事,因此,机器学习算法通常会采用一些标准的数据格式,最常见的一种格式就是每一个数据对应欧几里德空间里的一个向量。

如果原始的数据格式不兼容,那么就需要首先进行转换,这个过程通常叫做“特征提取”(Feature Extraction),而得到的标准数据格式通常叫做 Feature 。例如,一个最简单的将一个文本 Document 转化为向量的方法如下:

漫谈 Clustering (4): Spectral Clustering

本文是“漫谈 Clustering 系列”中的第 6 篇,参见本系列的其他文章。

如果说 K-means 和 GMM 这些聚类的方法是古代流行的算法的话,那么这次要讲的 Spectral Clustering 就可以算是现代流行的算法了,中文通常称为“谱聚类”。由于使用的矩阵的细微差别,谱聚类实际上可以说是一“类”算法。

Spectral Clustering 和传统的聚类方法(例如 K-means)比起来有不少优点:

和 K-medoids 类似,Spectral Clustering 只需要数据之间的相似度矩阵就可以了,而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。
由于抓住了主要矛盾,忽略了次要的东西,因此比传统的聚类算法更加健壮一些,对于不规则的误差数据不是那么敏感,而且 performance 也要好一些。许多实验都证明了这一点。事实上,在各种现代聚类算法的比较中,K-means 通常都是作为 baseline 而存在的。
计算复杂度比 K-means 要小,特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。

漫谈 Clustering (番外篇): Expectation Maximization

本文是“漫谈 Clustering 系列”中的第 5 篇,参见本系列的其他文章。

Expectation Maximization (EM) 是一种以迭代的方式来解决一类特殊最大似然 (Maximum Likelihood) 问题的方法,这类问题通常是无法直接求得最优解,但是如果引入隐含变量,在已知隐含变量的值的情况下,就可以转化为简单的情况,直接求得最大似然解。

我们会看到,上一次说到的 Gaussian Mixture Model 的迭代求解方法可以算是 EM 算法最典型的应用,而最开始说的 K-means 其实也可以看作是 Gaussian Mixture Model 的一个变种(固定所有的 ,并令 即可)。然而 EM 实际上是一种通用的算法(或者说是框架),可以用来解决很多类似的问题,我们最后将以一个中文分词的例子来说明这一点。

漫谈 Clustering (3): Gaussian Mixture Model

本文是“漫谈 Clustering 系列”中的第 4 篇,参见本系列的其他文章。

上一次我们谈到了用 k-means 进行聚类的方法,这次我们来说一下另一个很流行的算法:Gaussian Mixture Model (GMM)。事实上,GMM 和 k-means 很像,不过 GMM 是学习出一些概率密度函数来(所以 GMM 除了用在 clustering 上之外,还经常被用于 density estimation ),简单地说,k-means 的结果是每个数据点被 assign 到其中某一个 cluster 了,而 GMM 则给出这些数据点被 assign 到每个 cluster 的概率,又称作 soft assignment 。

得出一个概率有很多好处,因为它的信息量比简单的一个结果要多,比如,我可以把这个概率转换为一个 score ,表示算法对自己得出的这个结果的把握。也许我可以对同一个任务,用多个方法得到结果,最后选取“把握”最大的那个结果;另一个很常见的方法是在诸如疾病诊断之类的场所,机器对于那些很容易分辨的情况(患病或者不患病的概率很高)可以自动区分,而对于那种很难分辨的情况,比如,49% 的概率患病,51% 的概率正常,如果仅仅简单地使用 50% 的阈值将患者诊断为“正常”的话,风险是非常大的,因此,在机器对自己的结果把握很小的情况下,会“拒绝发表评论”,而把这个任务留给有经验的医生去解决。

漫谈 Clustering (番外篇): Vector Quantization

本文是“漫谈 Clustering 系列”中的第 3 篇,参见本系列的其他文章。

在接下去说其他的聚类算法之前,让我们先插进来说一说一个有点跑题的东西:Vector Quantization 。这项技术广泛地用在信号处理以及数据压缩等领域。事实上,在 JPEG 和 MPEG-4 等多媒体压缩格式里都有 VQ 这一步。

Vector Quantization 这个名字听起来有些玄乎,其实它本身并没有这么高深。大家都知道,模拟信号是连续的值,而计算机只能处理离散的数字信号,在将模拟信号转换为数字信号的时候,我们可以用区间内的某一个值去代替着一个区间,比如,[0, 1) 上的所有值变为 0 ,[1, 2) 上的所有值变成 1 ,如此类推。其这就是一个 VQ 的过程。一个比较正式一点的定义是:VQ 是将一个向量空间中的点用其中的一个有限子集来进行编码的过程。

一个典型的例子就是图像的编码。最简单的情况,考虑一个灰度图片,0 为黑色,1 为白色,每个像素的值为 [0, 1] 上的一个实数。现在要把它编码为 256 阶的灰阶图片,一个最简单的做法就是将每一个像素值 x 映射为一个整数 floor(x*255) 。当然,原始的数据空间也并不以一定要是连续的。比如,你现在想要把压缩这个图片,每个像素只使用 4 bit (而不是原来的 8 bit)来存储,因此,要将原来的 [0, 255] 区间上的整数值用 [0, 15] 上的整数值来进行编码,一个简单的映射方案是 x*15/255 。

漫谈 Clustering (2): k-medoids

Samoyed

本文是“漫谈 Clustering 系列”中的第 2 篇,参见本系列的其他文章。

上一次我们了解了一个最基本的 clustering 办法 k-means ,这次要说的 k-medoids 算法,其实从名字上就可以看出来,和 k-means 肯定是非常相似的。事实也确实如此,k-medoids 可以算是 k-means 的一个变种。

k-medoids 和 k-means 不一样的地方在于中心点的选取,在 k-means 中,我们将中心点取为当前 cluster 中所有数据点的平均值:

漫谈 Clustering (1): k-means

本文是“漫谈 Clustering 系列”中的第 1 篇,参见本系列的其他文章。

好久没有写 blog 了,一来是 blog 下线一段时间,而租 DreamHost 的事情又一直没弄好;二来是没有太多时间,天天都跑去实验室。现在主要折腾 Machine Learning 相关的东西,因为很多东西都不懂,所以平时也找一些资料来看。按照我以前的更新速度的话,这么长时间不写 blog 肯定是要被闷坏的,所以我也觉得还是不定期地整理一下自己了解到的东西,放在 blog 上,一来梳理总是有助于加深理解的,二来也算共享一下知识了。那么,还是从 clustering 说起吧。

Clustering 中文翻译作“聚类”,简单地说就是把相似的东西分到一组,同 Classification (分类)不同,对于一个 classifier ,通常需要你告诉它“这个东西被分为某某类”这样一些例子,理想情况下,一个 classifier 会从它得到的训练集中进行“学习”,从而具备对未知数据进行分类的能力,这种提供训练数据的过程通常叫做 supervised learning (监督学习),而在聚类的时候,我们并不关心某一类是什么,我们需要实现的目标只是把相似的东西聚到一起,因此,一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了,因此 clustering 通常并不需要使用训练数据进行学习,这在 Machine Learning 中被称作 unsupervised learning (无监督学习)。