|
|||||
|
本文是“漫谈 Clustering 系列”中的第 7 篇，参见本系列的其他文章。 由于总是有各种各样的杂事，这个系列的文章竟然一下子拖了好几个月，（实际上其他的日志我也写得比较少），现在决定还是先把这篇降维的日志写完。我甚至都以及忘记了在这个系列中之前有没有讲过“特征”（feature）的概念了，这里不妨再稍微提一下。机器学习应用到各个领域里，会遇到许多不同类型的数据要处理：图像、文本、音频视频以及物理、生物、化学等实验还有其他工业、商业以及军事上得到的各种数据，如果要为每一种类型的数据都设计独立的算法，那显然是非常不现实的事，因此，机器学习算法通常会采用一些标准的数据格式，最常见的一种格式就是每一个数据对应欧几里德空间里的一个向量。 如果原始的数据格式不兼容，那么就需要首先进行转换，这个过程通常叫做“特征提取”（Feature Extraction），而得到的标准数据格式通常叫做 Feature 。例如，一个最简单的将一个文本 Document 转化为向量的方法如下： 本文是“漫谈 Clustering 系列”中的第 6 篇，参见本系列的其他文章。 如果说 K-means 和 GMM 这些聚类的方法是古代流行的算法的话，那么这次要讲的 Spectral Clustering 就可以算是现代流行的算法了，中文通常称为“谱聚类”。由于使用的矩阵的细微差别，谱聚类实际上可以说是一“类”算法。 Spectral Clustering 和传统的聚类方法（例如 K-means）比起来有不少优点： 和 K-medoids 类似，Spectral Clustering 只需要数据之间的相似度矩阵就可以了，而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。 本文是“漫谈 Clustering 系列”中的第 5 篇，参见本系列的其他文章。 Expectation Maximization (EM) 是一种以迭代的方式来解决一类特殊最大似然 (Maximum Likelihood) 问题的方法，这类问题通常是无法直接求得最优解，但是如果引入隐含变量，在已知隐含变量的值的情况下，就可以转化为简单的情况，直接求得最大似然解。 我们会看到，上一次说到的 Gaussian Mixture Model 的迭代求解方法可以算是 EM 算法最典型的应用，而最开始说的 K-means 其实也可以看作是 Gaussian Mixture Model 的一个变种（固定所有的 ，并令 即可）。然而 EM 实际上是一种通用的算法（或者说是框架），可以用来解决很多类似的问题，我们最后将以一个中文分词的例子来说明这一点。 本文是“漫谈 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 系列”中的第 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 。 Samoyed 本文是“漫谈 Clustering 系列”中的第 2 篇，参见本系列的其他文章。 上一次我们了解了一个最基本的 clustering 办法 k-means ，这次要说的 k-medoids 算法，其实从名字上就可以看出来，和 k-means 肯定是非常相似的。事实也确实如此，k-medoids 可以算是 k-means 的一个变种。 k-medoids 和 k-means 不一样的地方在于中心点的选取，在 k-means 中，我们将中心点取为当前 cluster 中所有数据点的平均值： 本文是“漫谈 Clustering 系列”中的第 1 篇，参见本系列的其他文章。 好久没有写 blog 了，一来是 blog 下线一段时间，而租 DreamHost 的事情又一直没弄好；二来是没有太多时间，天天都跑去实验室。现在主要折腾 Machine Learning 相关的东西，因为很多东西都不懂，所以平时也找一些资料来看。按照我以前的更新速度的话，这么长时间不写 blog 肯定是要被闷坏的，所以我也觉得还是不定期地整理一下自己了解到的东西，放在 blog 上，一来梳理总是有助于加深理解的，二来也算共享一下知识了。那么，还是从 clustering 说起吧。 Clustering 中文翻译作“聚类”，简单地说就是把相似的东西分到一组，同 Classification (分类)不同，对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做 supervised learning (监督学习)，而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在 Machine Learning 中被称作 unsupervised learning (无监督学习)。 |
 |
||||
|
Copyright © 2021 Free Mind - All Rights Reserved |
|||||
by pluskid, on 2009-06-20, in 
Comments