设为首页收藏本站
开启辅助访问 切换到宽版

科学网

 找回密码
  注册
科学网 › 标签 › 聚类

tag 标签: 聚类

相关帖子

 版块 作者 回复/查看 最后发表

没有相关内容

相关日志

[转载]漫谈 Clustering
热度 4 JRoy 2012-10-11 00:38
Clustering 中文翻译作“聚类”，简单地说就是把相似的东西分到一组，同 Classification (分类)不同，对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做 supervised learning (监督学习)，而在聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在 Machine Learning 中被称作 unsupervised learning (无监督学习)。 漫谈 Clustering (1): k-means 那么让我们再回到 clustering 的问题上，暂且抛开原始数据是什么形式，假设我们已经将其映射到了一个欧几里德空间上，为了方便展示，就使用二维空间吧，如下图所示： 从数据点的大致形状可以看出它们大致聚为三个 cluster ，其中两个紧凑一些，剩下那个松散一些。我们的目的是为这些数据分组，以便能区分出属于不同的簇的数据，如果按照分组给它们标上不同的颜色，就是这个样子： 那么计算机要如何来完成这个任务呢？当然，计算机还没有高级到能够“通过形状大致看出来”，不过，对于这样的 N 维欧氏空间中的点进行聚类，有一个非常简单的经典算法，也就是本文标题中提到的 k-means 。在介绍 k-means 的具体步骤之前，让我们先来看看它对于需要进行聚类的数据的一个基本假设吧：对于每一个 cluster ，我们可以选出一个中心点 (center) ，使得该 cluster 中的所有的点到该中心点的距离小于到其他 cluster 的中心的距离。虽然实际情况中得到的数据并不能保证总是满足这样的约束，但这通常已经是我们所能达到的最好的结果，而那些误差通常是固有存在的或者问题本身的不可分性造成的。例如下图所示的两个高斯分布，从两个分布中随机地抽取一些数据点出来，混杂到一起，现在要让你将这些混杂在一起的数据点按照它们被生成的那个分布分开来： 由于这两个分布本身有很大一部分重叠在一起了，例如，对于数据点 2.5 来说，它由两个分布产生的概率都是相等的，你所做的只能是一个猜测；稍微好一点的情况是 2 ，通常我们会将它归类为左边的那个分布，因为概率大一些，然而此时它由右边的分布生成的概率仍然是比较大的，我们仍然有不小的几率会猜错。而整个阴影部分是我们所能达到的最小的猜错的概率，这来自于问题本身的不可分性，无法避免。因此，我们将 k-means 所依赖的这个假设看作是合理的。 基于这样一个假设，我们再来导出 k-means 所要优化的目标函数：设我们一共有 N 个数据点需要分为 K 个 cluster ，k-means 要做的就是最小化 这个函数，其中 在数据点 n 被归类到 cluster k 的时候为 1 ，否则为 0 。直接寻找 和 来最小化 并不容易，不过我们可以采取迭代的办法：先固定 ，选择最优的 ，很容易看出，只要将数据点归类到离他最近的那个中心就能保证 最小。下一步则固定 ，再求最优的 。将 对 求导并令导数等于零，很容易得到 最小的时候 应该满足： 亦即 的值应当是所有 cluster k 中的数据点的平均值。由于每一次迭代都是取到 的最小值，因此 只会不断地减小（或者不变），而不会增加，这保证了 k-means 最终会到达一个极小值。虽然 k-means 并不能保证总是能得到全局最优解，但是对于这样的问题，像 k-means 这种复杂度的算法，这样的结果已经是很不错的了。 下面我们来总结一下 k-means 算法的具体步骤： 选定 K 个中心 的初值。这个过程通常是针对具体的问题有一些启发式的选取方法，或者大多数情况下采用随机选取的办法。因为前面说过 k-means 并不能保证全局最优，而是否能收敛到全局最优解其实和初值的选取有很大的关系，所以有时候我们会多次选取初值跑 k-means ，并取其中最好的一次结果。 将每个数据点归类到离它最近的那个中心点所代表的 cluster 中。 用公式 计算出每个 cluster 的新的中心点。 重复第二步，一直到迭代了最大的步数或者前后的 的值相差小于一个阈值为止。 首先 3 个中心点被随机初始化，所有的数据点都还没有进行聚类，默认全部都标记为红色，如下图所示： 然后进入第一次迭代：按照初始的中心点位置为每个数据点着上颜色，这是代码中第 41 到 43 行所做的工作，然后 45 到 47 行重新计算 3 个中心点，结果如下图所示： 可以看到，由于初始的中心点是随机选的，这样得出来的结果并不是很好，接下来是下一次迭代的结果： 可以看到大致形状已经出来了。再经过两次迭代之后，基本上就收敛了，最终结果如下： 不过正如前面所说的那样 k-means 也并不是万能的，虽然许多时候都能收敛到一个比较好的结果，但是也有运气不好的时候会收敛到一个让人不满意的局部最优解，例如选用下面这几个初始中心点： 最终会收敛到这样的结果： 不得不承认这并不是很好的结果。不过其实大多数情况下 k-means 给出的结果都还是很令人满意的，算是一种简单高效应用广泛的 clustering 方法。 漫谈 Clustering (2): k-medoids 其实从名字上就可以看出来，和 k-means 肯定是非常相似的。事实也确实如此，k-medoids 可以算是 k-means 的一个变种。 k-medoids 和 k-means 不一样的地方在于中心点的选取，在 k-means 中，我们将中心点取为当前 cluster 中所有数据点的平均值： 并且我们已经证明在固定了各个数据点的 assignment 的情况下，这样选取的中心点能够把目标函数 最小化。然而在 k-medoids 中，我们将中心点的选取限制在当前 cluster 所包含的数据点的集合中。换句话说，在 k-medoids 算法中，我们将从当前 cluster 中选取这样一个点——它到其他所有（当前 cluster 中的）点的距离之和最小——作为中心点。k-means 和 k-medoids 之间的差异就类似于一个数据样本的均值 (mean) 和中位数 ( median ) 之间的差异：前者的取值范围可以是连续空间中的任意值，而后者只能在给样本给定的那些点里面选。那么，这样做的好处是什么呢？ 一个最直接的理由就是 k-means 对数据的要求太高了，它使用欧氏距离描述数据点之间的差异 (dissimilarity) ，从而可以直接通过求均值来计算中心点。这要求数据点处在一个欧氏空间之中。 然而并不是所有的数据都能满足这样的要求，对于数值类型的特征，比如身高，可以很自然地用这样的方式来处理，但是类别 (categorical) 类型的特征就不行了。举一个简单的例子，如果我现在要对犬进行聚类，并且希望直接在所有犬组成的空间中进行，k-means 就无能为力了，因为欧氏距离 在这里不能用了：一只 Samoyed 减去一只 Rough Collie 然后在平方一下？天知道那是什么！再加上一只 German Shepherd Dog 然后求一下平均值？根本没法算，k-means 在这里寸步难行！ 在 k-medoids 中，我们把原来的目标函数 中的欧氏距离改为一个任意的 dissimilarity measure 函数 ： 最常见的方式是构造一个 dissimilarity matrix 来代表 ，其中的元素 表示第 只狗和第 只狗之间的差异程度，例如，两只 Samoyed 之间的差异可以设为 0 ，一只 German Shepherd Dog 和一只 Rough Collie 之间的差异是 0.7，和一只 Miniature Schnauzer 之间的差异是 1 ，等等。 除此之外，由于中心点是在已有的数据点里面选取的，因此相对于 k-means 来说，不容易受到那些由于误差之类的原因产生的 Outlier 的影响，更加 robust 一些。 扯了这么多，还是直接来看看 k-medoids 的效果好了，由于 k-medoids 对数据的要求比 k-means 要低，所以 k-means 能处理的情况自然 k-medoids 也能处理，为了能先睹为快，我们偷一下懒，直接在 上一篇文章 中的 k-means 代码的基础上稍作一点修改，还用同样的例子。 可以看到 k-medoids 在这个例子上也能得到很好的结果： 而且，同 k-means 一样，运气不好的时候也会陷入局部最优解中： 如果仔细看上面那段代码的话，就会发现，从 k-means 变到 k-medoids ，时间复杂度陡然增加了许多：在 k-means 中只要求一个平均值 即可，而在 k-medoids 中则需要枚举每个点，并求出它到所有其他点的距离之和，复杂度为 。 看完了直观的例子，让我们再来看一个稍微实际一点的例子好了：Document Clustering ——那个永恒不变的主题，不过我们这里要做的聚类并不是针对文档的主题，而是针对文档的语言。实验数据是从 Europarl 下载的包含 Danish、German、Greek、English、Spanish、Finnish、French、Italian、Dutch、Portuguese 和 Swedish 这些语言的文本数据集。 在 N-gram-based text categorization 这篇 paper 中描述了一种计算由不同语言写成的文档的相似度的方法。一个（以字符为单位的） N-gram 就相当于长度为 N 的一系列连续子串。例如，由 hello 产生的 3-gram 为：hel、ell 和 llo ，有时候还会在划分 N-gram 之前在开头和末尾加上空格（这里用下划线表示）：_he、hel、ell、llo、lo_ 和 o__ 。按照 Zipf’s law ： The n th most common word in a human language text occurs with a frequency inversely proportional to n . 这里我们用 N-gram 来代替 word 。这样，我们从一个文档中可以得到一个 N-gram 的频率分布，按照频率排序一下，只保留频率最高的前 k 个（比如，300）N-gram，我们把叫做一个“Profile”。正常情况下，某一种语言（至少是西方国家的那些类英语的语言）写成的文档，不论主题或长短，通常得出来的 Profile 都差不多，亦即按照出现的频率排序所得到的各个 N-gram 的序号不会变化太大。这是非常好的一个性质：通常我们只要各个语言选取一篇（比较正常的，也不需要很长）文档构建出一个 Profile ，在拿到一篇未知文档的时候，只要和各个 Profile 比较一下，差异最小的那个 Profile 所对应的语言就可以认定是这篇未知文档的语言了——准确率很高，更可贵的是，所需要的训练数据非常少而且容易获得，训练出来的模型也是非常小的。 不过，我们这里且撇开分类（Classification）的问题，回到聚类（Clustering）上，按照前面的说法，在 k-medoids 聚类中，只需要定义好两个东西之间的距离（或者 dissimilarity ）就可以了，对于两个 Profile ，它们之间的 dissimilarity 可以很自然地定义为对应的 N-gram 的序号之差的绝对值。 europarl 数据集共有 11 种语言的文档，每种语言包括大约 600 多个文档。我为这七千多个文档建立了 Profile 并构造出一个 7038×7038 的 dissimilarity matrix ，最后在这上面用 k-medoids 进行聚类。构造 dissimilarity matrix 的过程很慢，在我这里花了将近 10 个小时。相比之下，k-medoids 的过程在内存允许的情况下，采用 向量化 的方法来做实际上还是很快的，并且通常只要数次迭代就能收敛了。实际的 k-medoids 实现可以在 mltk 中找到，今后如果有时间的话，我会陆续地把一些相关的比较通用的代码放到那里面。 最后，然我们来看看聚类的结果，由于聚类和分类不同，只是得到一些 cluster ，而并不知道这些 cluster 应该被打上什么标签，或者说，在这个问题里，包含了哪种语言的文档。由于我们的目的是衡量聚类算法的 performance ，因此直接假定这一步能实现最优的对应关系，将每个 cluster 对应到一种语言上去。一种办法是枚举所有可能的情况并选出最优解，另外，对于这样的问题，我们还可以用 Hungarian algorithm 来求解。 我们这里有 11 种语言，全排列有 11! = 39916800 种情况， 对于每一种排列，我们需要遍历一次 label list ，并数出真正的 label （语言）与聚类得出的结果相同的文档的个数，再除以总的文档个数，得到 accuracy 。假设每次遍历并求出 accuracy 只需要 1 毫秒的时间的话，总共也需要 11 个小时才能得到结果。看上去好像也不是特别恐怖，不过相比起来，用 Hungarian algorithm 的话，我们可以几乎瞬间得到结果。由于文章的篇幅已经很长了，就不在这里介绍具体的算法了，感兴趣的同学可以参考 Wikipedia ，这里我直接使用了一个现有的 Python 实现 。 虽然这个实验非常折腾，不过最后的结果其实就是一个数字：accuracy ——在我这里达到了 88.97% ，证明 k-medoids 聚类和 N-gram Profile 识别语言这两种方法都是挺不错的。最后，如果有感兴趣的同学，代码可以从 这里 下载。需要最新版的 scipy ， munkres.py 和 mltk 以及 Python 2.6 。 漫谈 Clustering (番外篇): Vector Quantization 在接下去说其他的聚类算法之前，让我们先插进来说一说一个有点跑题的东西： Vector Quantization 。这项技术广泛地用在信号处理以及数据压缩等领域。事实上，在 JPEG 和 MPEG-4 等多媒体压缩格式里都有 VQ 这一步。 Vector Quantization 这个名字听起来有些玄乎，其实它本身并没有这么高深。大家都知道，模拟信号是连续的值，而计算机只能处理离散的数字信号，在将模拟信号转换为数字信号的时候，我们可以用区间内的某一个值去代替着一个区间，比如， 上的一个实数。现在要把它编码为 256 阶的灰阶图片，一个最简单的做法就是将每一个像素值x映射为一个整数floor(x*255)。当然，原始的数据空间也并不以一定要是连续的。比如，你现在想要把压缩这个图片，每个像素只使用 4 bit （而不是原来的 8 bit）来存储，因此，要将原来的 区间上的整数值用 上的整数值来进行编码，一个简单的映射方案是x*15/255。 不过这样的映射方案颇有些 Naive ，虽然能减少颜色数量起到压缩的效果，但是如果原来的颜色并不是均匀分布的，那么的出来的图片质量可能并不是很好。例如，如果一个 256 阶灰阶图片完全由 0 和 13 两种颜色组成，那么通过上面的映射就会得到一个全黑的图片，因为两个颜色全都被映射到 0 了。一个更好的做法是结合聚类来选取代表性的点。 实际做法就是：将每个像素点当作一个数据，跑一下 K-means ，得到 k 个 centroids ，然后用这些 centroids 的像素值来代替对应的 cluster 里的所有点的像素值。对于彩色图片来说，也可以用同样的方法来做，例如 RGB 三色的图片，每一个像素被当作是一个 3 维向量空间中的点。 用本文开头那张 Rechard Stallman 大神的照片来做一下实验好了，VQ 2、VQ 10 和 VQ 100 三张图片分别显示聚类数目为 2 、10 和 100 时得到的结果，可以看到 VQ 100 已经和原图非常接近了。把原来的许多颜色值用 centroids 代替之后，总的颜色数量减少了，重复的颜色增加了，这种冗余正是压缩算法最喜欢的。考虑一种最简单的压缩办法：单独存储（比如 100 个）centroids 的颜色信息，然后每个像素点存储 centroid 的索引而不是颜色信息值，如果一个 RGB 颜色值需要 24 bits 来存放的话，每个（128 以内的）索引值只需要 7 bits 来存放，这样就起到了压缩的效果。 VQ 2 VQ 100 VQ 10 漫谈Clustering(3)Gaussian Mixture Model 我们谈到了用 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% 的阈值将患者诊断为“正常”的话，风险是非常大的，因此，在机器对自己的结果把握很小的情况下，会“拒绝发表评论”，而把这个任务留给有经验的医生去解决。 废话说了一堆，不过，在回到 GMM 之前，我们再稍微扯几句。我们知道，不管是机器还是人，学习的过程都可以看作是一种“归纳”的过程，在归纳的时候你需要有一些假设的前提条件，例如，当你被告知水里游的那个家伙是鱼之后，你使用“在同样的地方生活的是同一种东西”这类似的假设，归纳出“在水里游的都是鱼”这样一个结论。当然这个过程是完全“本能”的，如果不仔细去想，你也不会了解自己是怎样“认识鱼”的。另一个值得注意的地方是这样的假设并不总是完全正确的，甚至可以说总是会有这样那样的缺陷的，因此你有可能会把虾、龟、甚至是潜水员当做鱼。也许你觉得可以通过修改前提假设来解决这个问题，例如，基于“生活在同样的地方并且穿着同样衣服的是同一种东西”这个假设，你得出结论：在水里有并且身上长有鳞片的是鱼。可是这样还是有问题，因为有些没有长鳞片的鱼现在又被你排除在外了。 在这个问题上，机器学习面临着和人一样的问题，在机器学习中，一个学习算法也会有一个前提假设，这里被称作“ 归纳偏执 (bias) ”（bias 这个英文词在机器学习和统计里还有其他许多的意思）。例如线性回归，目的是要找一个函数尽可能好地拟合给定的数据点，它的归纳偏执就是“满足要求的函数必须是线性函数”。一个没有归纳偏执的学习算法从某种意义上来说毫无用处，就像一个完全没有归纳能力的人一样，在第一次看到鱼的时候有人告诉他那是鱼，下次看到另一条鱼了，他并不知道那也是鱼，因为两条鱼总有一些地方不一样的，或者就算是同一条鱼，在河里不同的地方看到，或者只是看到的时间不一样，也会被他认为是不同的，因为他无法归纳，无法提取主要矛盾、乎略次要因素，只好要求所有的条件都完全一样──然而哲学家已经告诉过我们了：世界上不会有任何样东西是完全一样的，所以这个人即使是有无比强悍的记忆力，也绝学不到任何一点 知识 。 这个问题在机器学习中称作“ 过拟合 (Overfitting) ”，例如前面的回归的问题，如果去掉“线性函数”这个归纳偏执，因为对于 N 个点，我们总是可以构造一个 N-1 次多项式函数，让它完美地穿过所有的这 N 个点，或者如果我用任何大于 N-1 次的多项式函数的话，我甚至可以构造出无穷多个满足条件的函数出来。如果假定特定领域里的问题所给定的数据个数总是有个上限的话，我可以取一个足够大的 N ，从而得到一个（或者无穷多个）“超级函数”，能够 fit 这个领域内所有的问题。然而这个（或者这无穷多个）“超级函数”有用吗？只要我们注意到 学习 的目的（通常）不是解释现有的事物，而是从中 归纳 出 知识 ，并能应用到 新的 事物上，结果就显而易见了。 没有归纳偏执或者归纳偏执太宽泛会导致 Overfitting ，然而另一个极端──限制过大的归纳偏执也是有问题的：如果数据本身并不是线性的，强行用线性函数去做回归通常并不能得到好结果。难点正在于在这之间寻找一个平衡点。不过人在这里相对于（现在的）机器来说有一个很大的优势：人通常不会孤立地用某一个独立的系统和模型去处理问题，一个人每天都会从各个来源获取大量的信息，并且通过各种手段进行整合处理，归纳所得的所有知识最终得以 统一 地存储起来，并能 有机 地组合起来去解决特定的问题。这里的“有机”这个词很有意思，搞理论的人总能提出各种各样的模型，并且这些模型都有严格的理论基础保证能达到期望的目的，然而绝大多数模型都会有那么一些“参数”（例如 K-means 中的 k ），通常没有理论来说明参数取哪个值更好，而模型实际的效果却通常和参数是否取到最优值有很大的关系，我觉得，在这里“有机”不妨看作是所有模型的参数已经自动地取到了最优值。另外，虽然进展不大，但是人们也一直都期望在计算机领域也建立起一个统一的知识系统（例如 语意网 就是这样一个尝试）。 废话终于说完了，回到 GMM 。按照我们前面的讨论，作为一个流行的算法，GMM 肯定有它自己的一个相当体面的归纳偏执了。其实它的假设非常简单，顾名思义，Gaussian Mixture Model ，就是假设数据服从 Mixture Gaussian Distribution ，换句话说，数据可以看作是从数个 Gaussian Distribution 中生成出来的。实际上，我们在 K-means 和 K-medoids 两篇文章中用到的那个例子就是由三个 Gaussian 分布从随机选取出来的。实际上，从 中心极限定理 可以看出，Gaussian 分布（也叫做正态 (Normal) 分布）这个假设其实是比较合理的，除此之外，Gaussian 分布在计算上也有一些很好的性质，所以，虽然我们可以用不同的分布来随意地构造 XX Mixture Model ，但是还是 GMM 最为流行。另外，Mixture Model 本身其实也是可以变得任意复杂的，通过增加 Model 的个数，我们可以任意地逼近任何连续的概率密分布。 每个 GMM 由 个 Gaussian 分布组成，每个 Gaussian 称为一个“Component”，这些 Component 线性加成在一起就组成了 GMM 的概率密度函数： 根据上面的式子，如果我们要从 GMM 的分布中随机地取一个点的话，实际上可以分为两步：首先随机地在这 个 Component 之中选一个，每个 Component 被选中的概率实际上就是它的系数 ，选中了 Component 之后，再单独地考虑从这个 Component 的分布中选取一个点就可以了──这里已经回到了普通的 Gaussian 分布，转化为了已知的问题。 那么如何用 GMM 来做 clustering 呢？其实很简单，现在我们有了数据，假定它们是由 GMM 生成出来的，那么我们只要根据数据推出 GMM 的概率分布来就可以了，然后 GMM 的 个 Component 实际上就对应了 个 cluster 了。根据数据来推算概率密度通常被称作 density estimation ，特别地，当我们在已知（或假定）了概率密度函数的形式，而要估计其中的参数的过程被称作“参数估计”。 现在假设我们有 个数据点，并假设它们服从某个分布（记作 ），现在要确定里面的一些参数的值，例如，在 GMM 中，我们就需要确定 、 和 这些参数。 我们的想法是，找到这样一组参数，它所确定的概率分布生成这些给定的数据点的概率最大，而这个概率实际上就等于 ，我们把这个乘积称作 似然函数 (Likelihood Function) 。通常单个点的概率都很小，许多很小的数字相乘起来在计算机里很容易造成浮点数下溢，因此我们通常会对其取对数，把乘积变成加和 ，得到 log-likelihood function 。接下来我们只要将这个函数最大化（通常的做法是求导并令导数等于零，然后解方程），亦即找到这样一组参数值，它让似然函数取得最大值，我们就认为这是最合适的参数，这样就完成了参数估计的过程。 下面让我们来看一看 GMM 的 log-likelihood function ： 由于在对数函数里面又有加和，我们没法直接用求导解方程的办法直接求得最大值。为了解决这个问题，我们采取之前从 GMM 中随机选点的办法：分成两步，实际上也就类似于 K-means 的两步。 估计数据由每个 Component 生成的概率（并不是每个 Component 被选中的概率）：对于每个数据 来说，它由第 个 Component 生成的概率为 由于式子里的 和 也是需要我们估计的值，我们采用迭代法，在计算 的时候我们假定 和 均已知，我们将取上一次迭代所得的值（或者初始值）。 估计每个 Component 的参数：现在我们假设上一步中得到的 就是正确的“数据 由 Component 生成的概率”，亦可以当做该 Component 在生成这个数据上所做的贡献，或者说，我们可以看作 这个值其中有 这部分是由 Component 所生成的。集中考虑所有的数据点，现在实际上可以看作 Component 生成了 这些点。由于每个 Component 都是一个标准的 Gaussian 分布，可以很容易分布求出最大似然所对应的参数值： 其中 ，并且 也顺理成章地可以估计为 。 重复迭代前面两步，直到似然函数的值收敛为止。 当然，上面给出的只是比较“直观”的解释，想看严格的推到过程的话，可以参考 Pattern Recognition and Machine Learning 这本书的第九章。有了实际的步骤，再实现起来就很简单了。 covariance 矩阵 singular 的情况，可以参见 这篇文章 。 函数返回的Px是一个 的矩阵，对于每一个 ，我们只要取该矩阵第 行中最大的那个概率值所对应的那个 Component 为 所属的 cluster 就可以实现一个完整的聚类方法了。对于最开始的那个例子，GMM 给出的结果如下： 相对于 之前 K-means 给出的结果 ，这里的结果更好一些，左下角的比较稀疏的那个 cluster 有一些点跑得比较远了。当然，因为这个问题原本就是完全有 Mixture Gaussian Distribution 生成的数据，GMM （如果能求得全局最优解的话）显然是可以对这个问题做到的最好的建模。 另外，从上面的分析中我们可以看到 GMM 和 K-means 的迭代求解法其实非常相似（都可以追溯到 EM 算法 ，下一次会详细介绍），因此也有和 K-means 同样的问题──并不能保证总是能取到全局最优，如果运气比较差，取到不好的初始值，就有可能得到很差的结果。对于 K-means 的情况，我们通常是重复一定次数然后取最好的结果，不过 GMM 每一次迭代的计算量比 K-means 要大许多，一个更流行的做法是先用 K-means （已经重复并取最优值了）得到一个粗略的结果，然后将其作为初值（只要将 K-means 所得的 centroids 传入gmm函数即可），再用 GMM 进行细致迭代。 如我们最开始所讨论的，GMM 所得的结果（Px）不仅仅是数据点的 label ，而包含了数据点标记为每个 label 的概率，很多时候这实际上是非常有用的信息。最后，需要指出的是，GMM 本身只是一个模型，我们这里给出的迭代的办法并不是唯一的求解方法。感兴趣的同学可以自行查找相关资料。 漫谈 Clustering (番外篇): Expectation Maximization Expectation Maximization (EM) 是一种以迭代的方式来解决一类特殊最大似然 (Maximum Likelihood) 问题的方法，这类问题通常是无法直接求得最优解，但是如果引入隐含变量，在已知隐含变量的值的情况下，就可以转化为简单的情况，直接求得最大似然解。 我们会看到，上一次说到的 Gaussian Mixture Model 的迭代求解方法可以算是 EM 算法最典型的应用，而最开始说的 K-means 其实也可以看作是 Gaussian Mixture Model 的一个变种（固定所有的 ，并令 即可）。然而 EM 实际上是一种通用的算法（或者说是框架），可以用来解决很多类似的问题，我们最后将以一个中文分词的例子来说明这一点。 为了避免问题变得太抽象，我们还是先从上一次的 Gaussian Mixture Model 说起吧。回顾一下我们之前要解决的问题：求以下 Log-likelihood function 的最大值： 但是由于在 函数里面又有加和，没法直接求。考虑一下 GMM 生成 sample 的过程：先选一个 Component ，然后再从这个 Component 所对应的那个普通的 Gaussian Distribution 里进行 sample 。我们可以很自然地引入一个隐含变量 ，这是一个 维向量，如果第 个 Component 被选中了，那么我们讲其第 个元素置为 1 ，其余的全为 0 。那么，再来看看，如果除了之前的 sample 的值之外，我们同时还知道了每个 所对应的隐含变量 的值，情况又会变成怎么样呢？ 因为我们同时观察到了 和 ，所以我们现在要最大化的似然函数也变为 。注意到 可以表示为： 而 的概率，当 的第 个元素为 1 的时候，亦即第 个 Component 被选中的时候，这个概率为 ，统一地写出来就是： 带入上面个式子，我们得到 的概率是一个大的乘积式（对比之前 是一个和式）。再替换到最开始的那个 Log-likelihood function 中，得到新的同时关于 sample 和隐含变量 的 Log-likelihood: 情况瞬间逆转，现在 和求和符号换了个位置，直接作用在普通的高斯分布上了，一下子就变成了可以直接求解的问题。不过，事情之所以能发展得如此顺利，完全依赖于一个我们伪造的假设：隐含变量的值已知。然而实际上我们并不知道这个值。问题的结症在这里了，如果我们有了这个值，所有的问题都迎刃而解了。回想一下，在类似的地方，我们是如何处理这样的情况的呢？一个很类似的地方就是（比如，在数据挖掘中）处理缺失数据的情况，一般有几种办法： 用取值范围类的随机值代替。 用平均值代替。 填 0 或者其他特殊值。 这里我们采取一种类似于平均值的办法：取期望。因为这里我们至少有 sample 的值，因此我们可以把这个信息利用起来，针对后验概率 来取期望。前面说过， 的每一个元素只有 0 和 1 两种取值，因此按照期望的公式写出来就是： 中间用 贝叶斯定理 变了一下形，最后得到的式子正是我们在 漫谈 GMM 中定义的 。因此，对于上面那个可以直接求解的 Log-likelihood function 中的 ，我们只要用其期望 亦即 代替即可。 到这里为止，看起来是一个非常完美的方法，不过仔细一看，发现还有一个漏洞：之前的 Log-likelihood function 可以直接求最大值是建立在 是已知情况下，现在虽然我们用 来代替了 ，但是实际上 是一个反过来以非常复杂的关系依赖所要求参数的一个式子，而不是一个“已知的数值”。解决这个问题的办法就是迭代。 到此为止，我们就勾勒出了整个 EM 算法的结构，同时也把上一次所讲的求解 GMM 的方法又推导了一遍。EM 名字也来源于此： Expectation 一步对应于求关于后验概率的期望亦即 ； Maximization 一步则对应于接下来的正常的最大似然的方法估计相关的参数亦即 、 和 。 如果你还没有厌烦这些公式的话，让我们不妨再稍微花一点时间，从偏理论一点的角度来简略地证明一下 EM 这个迭代的过程每一步都会对结果有所改进，除非已经达到了一个（至少是局部的）最优解。 现在我们的讨论将不局限于 GMM ，并使用一些稍微紧凑一点的符号。用 表示所有的 sample ，同时用 表示所有对应的隐含变量。我们的问题是要通过最大似然的方法估计出 中的参数 。在这里我们假设这个问题很困难，但是要优化 却很容易。这就是 EM 算法能够解决的那一类问题。 现在我们引入一个关于隐含变量的分布 。注意到对于任意的 ，我们都可以对 Log-likelihood Function 作如下分解： 其中 是分布 和 之间的 Kullback-Leibler divergence 。由于 Kullback-Leibler divergence 是非负的，并且只有当两个分布完全相同的时候才会取到 0 。因此我们可以得到关系 ，亦即 是 的一个下界。 现在考虑 EM 的迭代过程，记上一次迭代得出的参数为 ，现在我们要选取 以令 最大，由于 并不依赖于 ，因此 的上限（在 固定的时候）是一个定值，它取到这个最大值的条件就是 Kullback-Leibler divergence 为零，亦即 等于后验概率 。把它带入到 的表达式中可以得到 其中const是常量，而 则正是我们之前所得到的“同时包含了 sample 和隐含变量的 Log-likelihood function 关于后验概率的期望”，因此这个对应到 EM 中的“E”一步。 在接下来的“M”一步中，我们讲固定住分布 ，再选取合适的 以将 最大化，这次其上界 也依赖于变量 ，并会随着 的增大而增大（因为我们有前面的不等式成立）。一般情况下 增大的量会比 要多一些，这时候 Kullback-Leibler divergence 在新的参数 下又不为零了，因此我们可以进入下一轮迭代，重新回到“E”一步去求新的 ；另一方面，如果这里 Kullback-Leibler divergence 在新的参数下还是等于 0 ，那么说明我们已经达到了一个（至少是局部的）最优解，迭代过程可以结束了。 上面的推导中我们可以看到每一次迭代 E 和 M 两个步骤都是在对解进行改进，因此迭代的过程中得到的 likelihood 会逐渐逼近（至少是局部的）最优值。另外，在 M 一步中除了用最大似然之外，也可以引入先验使用 Maximum a Posteriori (MAP) 的方法来做。还有一些很困难的问题，甚至在迭代的过程中 M 一步也不能直接求出最大值，这里我们通过把要求放宽──并不一定要求出最大值，只要能够得到比旧的值更好的结果即可，这样的做法通常称作 Generalized EM (GEM)。 当然，一开始我们就说了，EM 是一个通用的算法，并不只是用来求解 GMM 。下面我们就来举一个用 EM 来做中文分词的例子。这个例子来源于论文 Self-supervised Chinese Word Segmentation 。我在上次 MSTC 搜索引擎系列小课堂讲文本处理的时候提到过。这里为了把注意力集中到 EM 上，我略去一些细节的东西，简单地描述一下基本的模型。 现在我们有一个字符序列 ，并希望得到一个模型 （依赖于参数 ）能用来将其词的序列 。按照 生成模型 的方式来考虑，将 看成是由 生成的序列的话，我们自然希望找到那个生成 的可能性最大的 ，亦即通过最大似然的方式来估计参数 。 然而我们不知道似然函数 应该如何去优化，因此我们引入 latent variable ，如果我们知道 的话，似然值很容易求得： 其中 的值是从模型 中已知的。但是现在我们不知道 的值，因此我们转而取其关于后验概率的期望： 然后将这个期望针对 最大化即完成了 EM 的一次迭代。具体的做法通常是先把一个初始文本（比如所有的 的集合）按照 N-gram 分割（N-gram 在 讲 K-medoids 的那篇文章 中介绍过）为 ，形成一个最初的辞典，而模型 的参数 实际上就描述了各个 N-gram 的概率 ，初始值可以直接取为频率值。有了辞典之后对于任意的 ，我们可以根据辞典枚举出所有可能的分割 ，而每个分割的后验概率 就是其中的单词的概率乘积。其他的就是标准的 EM 算法的迭代步骤了。 实际上在实际产品中我们会使用一些带了更多启发式规则的分词方法（比如 MMSEG ），而这个方法更大的用处在于从一堆文本中“学习”出一个词典来（也就是 ），并且这个过程是全自动的，主要有两个优点： 不需要人参与手工分词、标记等。 能自动从文本中学习，换句话说，你给它一些某个领域的专业文章，它能从中学习到这个领域的专业词汇来。 不管怎样，以上两点看起来都非常诱人。不过理论离实际往往还是有不少差距的。我不知道实际分词系统中有没有在用这样的方法来做训练的。之前我曾经用 Wikipedia （繁体中文）上抓下来的一些数据跑过一下小规模的试验，结果还可以，但是也并不如想像中的完美。因为当时也并没有弄明白 EM 是怎么一回事，加上这个过程本身计算负荷还是非常大的，也就没有深入下去。也许以后有时间可以再尝试一下。 漫谈 Clustering (4): Spectral Clustering 如果说 K-means 和 GMM 这些聚类的方法是古代流行的算法的话，那么这次要讲的 Spectral Clustering 就可以算是现代流行的算法了，中文通常称为“谱聚类”。由于使用的矩阵的细微差别，谱聚类实际上可以说是一“类”算法。 Spectral Clustering 和传统的聚类方法（例如 K-means）比起来有不少优点： 和 K-medoids 类似，Spectral Clustering 只需要数据之间的相似度矩阵就可以了，而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。 由于抓住了主要矛盾，忽略了次要的东西，因此比传统的聚类算法更加健壮一些，对于不规则的误差数据不是那么敏感，而且 performance 也要好一些。许多实验都证明了这一点。事实上，在各种现代聚类算法的比较中，K-means 通常都是作为 baseline 而存在的。 计算复杂度比 K-means 要小，特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。 突然冒出这么一个要求比 K-means 要少，结果比 K-means 要好，算得还比 K-means 快的东西，实在是让人不得不怀疑是不是江湖骗子啊。所以，是骡子是马，先拉出来溜溜再说。不过，在 K-medoids 那篇文章中曾经实际跑过 K-medoids 算法，最后的结果也就是一个 accuracy ，一个数字又不能画成图表之类的，看起来实在是没意思，而且 K-means 跑起来实在是太慢了，所以这里我还是稍微偷懒一下，直接引用一下一篇论文里的结果吧。 结果来自论文 Document clustering using locality preserving indexing 这篇论文，这篇论文实际上是提的另一种聚类方法（下次如果有机会也会讲到），不过在它的实验中也有 K-means 和 Spectral Clustering 这两组数据，抽取出来如下所示： k TDT2 Reuters-21578 K-means SC K-means SC 2 0.989 0.998 0.871 0.923 3 0.974 0.996 0.775 0.816 4 0.959 0.996 0.732 0.793 … 9 0.852 0.984 0.553 0.625 10 0.835 0.979 0.545 0.615 其中 TDT2 和 Reuters-21578 分别是两个被广泛使用的标准文本数据集，虽然在不同的数据集上得出来的结果并不能直接拿来比较，但是在同一数据集上 K-means 和 SC (Spectral Clustering) 的结果对比就一目了然了。实验中分别抽取了这两个数据集中若干个类别（从 2 类到 10 类）的数据进行聚类，得出的 accuracy 分别在上表中列出（我偷懒没有全部列出来）。可以看到，Spectral Clustering 这里完胜 K-means 。 这么强大的算法，再戴上“谱聚类”这么一个高深莫测的名号，若不是模型无比复杂、包罗宇宙，就肯定是某镇山之宝、不传秘籍吧？其实不是这样，Spectral Clustering 不管从模型上还是从实现上都并不复杂，只需要能求矩阵的特征值和特征向量即可──而这是一个非常基本的运算，任何一个号称提供线性代数运算支持的库都理应有这样的功能。而关于 Spectral Clustering 的秘籍更是满街都是，随便从地摊上找来一本，翻开便可以看到 Spectral Clustering 算法的全貌： 根据数据构造一个 Graph ，Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 。一个最偷懒的办法就是：直接用我们前面在 K-medoids 中用的相似度矩阵作为 。 把 的每一列元素加起来得到 个数，把它们放在对角线上（其他地方都是零），组成一个 的矩阵，记为 。并令 。 求出 的前 个特征值（在本文中，除非特殊说明，否则“前 个”指按照特征值的大小从小到大的顺序） 以及对应的特征向量 。 把这 个特征（列）向量排列在一起组成一个 的矩阵，将其中每一行看作 维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 个数据点分别所属的类别。 就是这么几步，把数据做了一些诡异的变换，然后还在背后偷偷地调用了 K-means 。到此为止，你已经可以拿着它上街去招摇撞骗了。不过，如果你还是觉得不太靠谱的话，不妨再接着往下看，我们再来聊一聊 Spectral Clustering 那几个“诡异变换”背后的道理何在。 其实，如果你熟悉 Dimensional Reduction （降维）的话，大概已经看出来了，Spectral Clustering 其实就是通过 Laplacian Eigenmap 的降维方式降维之后再做 K-means 的一个过程──听起来土多了。不过，为什么要刚好降到 维呢？其实整个模型还可以从另一个角度导出来，所以，让我们不妨先跑一下题。 在 Image Processing （我好像之前有听说我对这个领域深恶痛绝？）里有一个问题就是对图像进行 Segmentation （区域分割），也就是让相似的像素组成一个区域，比如，我们一般希望一张照片里面的人（前景）和背景被分割到不同的区域中。在 Image Processing 领域里已经有许多自动或半自动的算法来解决这个问题，并且有不少方法和 Clustering 有密切联系。比如我们在谈 Vector Quantization 的时候就曾经用 K-means 来把颜色相似的像素聚类到一起，不过那还不是真正的 Segmentation ，因为如果仅仅是考虑颜色相似的话，图片上位置离得很远的像素也有可能被聚到同一类中，我们通常并不会把这样一些“游离”的像素构成的东西称为一个“区域”，但这个问题其实也很好解决：只要在聚类用的 feature 中加入位置信息（例如，原来是使用 R、G、B 三个值来表示一个像素，现在加入 x、y 两个新的值）即可。 另一方面，还有一个经常被研究的问题就是 Graph Cut ，简单地说就是把一个 Graph 的一些边切断，让他被打散成一些独立联通的 sub-Graph ，而这些被切断的边的权值的总和就被称为 Cut 值。如果用一张图片中的所有像素来组成一个 Graph ，并把（比如，颜色和位置上）相似的节点连接起来，边上的权值表示相似程度，那么把图片分割为几个区域的问题实际上等价于把 Graph 分割为几个 sub-Graph 的问题，并且我们可以要求分割所得的 Cut 值最小，亦即：那些被切断的边的权值之和最小，直观上我们可以知道，权重比较大的边没有被切断，表示比较相似的点被保留在了同一个 sub-Graph 中，而彼此之间联系不大的点则被分割开来。我们可以认为这样一种分割方式是比较好的。 实际上，抛开图像分割的问题不谈，在 Graph Cut 相关的一系列问题中，Minimum cut （最小割）本身就是一个被广泛研究的问题，并且有成熟的算法来求解。只是单纯的最小割在这里通常并不是特别适用，很多时候只是简单地把和其他像素联系最弱的那一个像素给分割出去了，相反，我们通常更希望分割出来的区域（的大小）要相对均匀一些，而不是一些很大的区块和一些几乎是孤立的点。为此，又有许多替代的算法提出来，如 Ratio Cut 、Normalized Cut 等。 不过，在继续讨论之前，我们还是先来定义一下符号，因为仅凭文字还是很难表述清楚。将 Graph 表示为邻接矩阵的形式，记为 ，其中 是节点 到节点 的权值，如果两个节点不是相连的，权值为零。设 和 为 Graph 的两个子集（没有交集），那么两者之间的 cut 可以正式定义为： 先考虑最简单的情况，如果把一个 Graph 分割为两个部分的话，那么 Minimum cut 就是要最小化 （其中 表示 的补集）。但是由于这样经常会出现孤立节点被分割出来的情况，因此又出现了 RatioCut ： 以及 NormalizedCut ： 其中 表示 中的节点数目，而 。两者都可以算作 的“大小”的一种度量，通过在分母上放置这样的项，就可以有效地防止孤立点的情况出现，达到相对平均一些的分割。事实上， Jianbo Shi 的这篇 PAMI paper： Normalized Cuts and Image Segmentation 正是把 NormalizedCut 用在图像分割上了。 搬出 RatioCut 和 NormalizedCut 是因为它们和这里的 Spectral Clustering 实际上有非常紧密的联系。看看 RatioCut ，式子虽然简单，但是要最小化它却是一个 NP 难问题，不方便求解，为了找到解决办法，让我们先来做做变形。 令 表示 Graph 的所有节点的集合，首先定义一个 维向量 ： 再回忆一下我们最开始定义的矩阵 ，其实它有一个名字，叫做 Graph Laplacian ，不过，我们后面可以看到，其实有好几个类似的矩阵都叫做这个名字： Usually, every author just calls “his” matrix the graph Laplacian. 其实也可以理解，就好象现在所有的厂家都说自己的技术是“云计算”一样。这个 有一个性质就是： 这个是对任意向量 都成立的，很好证明，只要按照定义展开就可以得到了。把我们刚才定义的那个 带进去，就可以得到 另外，如果令 为各个元素全为 1 的向量的话，直接展开可以很容易得到 和 。由于 是一个常量，因此最小化 RatioCut 就等价于最小化 ，当然，要记得加上附加条件 以及 。 问题转化到这个样子就好求了，因为有一个叫做 Rayleigh quotient 的东西： 他的最大值和最小值分别等于矩阵 的最大的那个特征值和最小的那个特征值，并且极值在 等于对应的特征向量时取到。由于 是常数，因此最小化 实际上也就等价于最小化 ，不过由于 的最小的特征值为零，并且对应的特征向量正好为 （我们这里仅考虑 Graph 是联通的情况），不满足 的条件，因此我们取第二个小的特征值，以及对应的特征向量 。 到这一步，我们看起来好像是很容易地解决了前面那个 NP 难问题，实际上是我们耍了一个把戏：之前的问题之所以 NP 难是因为向量 的元素只能取两个值 和 中的一个，是一个离散的问题，而我们求的的特征向量 其中的元素可以是任意实数，就是说我们将原来的问题限制放宽了。那如何得到原来的解呢？一个最简单的办法就是看 的每个元素是大于零还是小于零，将他们分别对应到离散情况的 和 ，不过我们也可以采取稍微复杂一点的办法，用 的 K-means 来将 的元素聚为两类。 到此为止，已经有 Spectral Clustering 的影子了：求特征值，再对特征向量进行 K-means 聚类。实际上，从两类的问题推广到 k 类的问题（数学推导我就不再详细写了），我们就得到了和之前的 Spectral Clustering 一模一样的步骤：求特征值并取前 k 个最小的，将对应的特征向量排列起来，再按行进行 K-means 聚类。分毫不差！ 用类似的办法，NormalizedCut 也可以等价到 Spectral Clustering 不过这次我就不再讲那么多了，感兴趣的话（还包括其他一些形式的 Graph Laplacian 以及 Spectral Clustering 和 Random walk 的关系），可以去看这篇 Tutorial ： A Tutorial on Spectral Clustering 。 为了缓和一下气氛，我决定贴一下 Spectral Clustering 的一个简单的 Matlab 实现： function idx = spectral_clustering ( W, k ) D = diag ( sum ( W ) ) ; L = D-W; opt = struct ( 'issym' , true, 'isreal' , true ) ; = eigs ( L, D, k, 'SM' , opt ) ; idx = kmeans ( V, k ) ; end 最后，我们再来看一下本文一开始说的 Spectral Clustering 的几个优点： 只需要数据的相似度矩阵就可以了。这个是显然的，因为 Spectral Clustering 所需要的所有信息都包含在 中。不过一般 并不总是等于最初的相似度矩阵——回忆一下， 是我们构造出来的 Graph 的邻接矩阵表示，通常我们在构造 Graph 的时候为了方便进行聚类，更加强到“局部”的连通性，亦即主要考虑把相似的点连接在一起，比如，我们设置一个阈值，如果两个点的相似度小于这个阈值，就把他们看作是不连接的。另一种构造 Graph 的方法是将 n 个与节点最相似的点与其连接起来。 抓住了主要矛盾，忽略了次要的东西，Performance 比传统的 K-means 要好。实际上 Spectral Clustering 是在用特征向量的元素来表示原来的数据，并在这种“更好的表示形式”上进行 K-means 。实际上这种“更好的表示形式”是用 Laplacian Eigenmap 进行降维的后的结果，如果有机会，下次谈 Dimensionality Reduction 的时候会详细讲到。而降维的目的正是“抓住主要矛盾，忽略次要的东西”。 计算复杂度比 K-means 要小。这个在高维数据上表现尤为明显。例如文本数据，通常排列起来是维度非常高（比如，几千或者几万）的稀疏矩阵，对稀疏矩阵求特征值和特征向量有很高效的办法，得到的结果是一些 k 维的向量（通常 k 不会很大），在这些低维的数据上做 K-means 运算量非常小。但是对于原始数据直接做 K-means 的话，虽然最初的数据是稀疏矩阵，但是 K-means 中有一个求 Centroid 的运算，就是求一个平均值：许多稀疏的向量的平均值求出来并不一定还是稀疏向量，事实上，在文本数据里，很多情况下求出来的 Centroid 向量是非常稠密，这时再计算向量之间的距离的时候，运算量就变得非常大，直接导致普通的 K-means 巨慢无比，而 Spectral Clustering 等工序更多的算法则迅速得多的结果。 说了这么多，好像有些乱，不过也只能到此打住了。最后再多嘴一句，Spectral Clustering 名字来源于 Spectral theory ，也就是用特征分解来分析问题的理论了。 UPDATE 2011.11.23: 有不少同学问我关于代码的问题，这里更新两点主要的问题： 关于 LE 降维的维度和 Kmeans 聚类的类别数的关系：我上面的代码里，取成了一样的，但是这两者并不是要求一定要一样的。最初 Spectral Cluster 是分析聚两类的情况，就降到 1 维，然后用 thresholding 的方法来分成两类。对于K 类的情况，自然的类比就是降到 K-1 维，这也是和 LDA 保持一致。因为 Laplacian 矩阵的特征向量有一个全一的向量（对应于特征值 0 ），所以可以求 K 个特征向量然后把特征值 0 对应的那个特征向量去掉。但是在实际中并不一定要保持这两者一致的，也就是说，这个降维的维度可以作为一个参数进行调节的，选择效果好的参数。 关于示例代码：注意除非我在这里注明了是发布某个 software 或者 package 什么的，否则这里贴的代码主要都是为了示例作用，为了只显示出算法的主要部分，因此通常会省略掉一些实现细节，可以看成是“可执行的伪代码”，不推荐直接用这里的代码去跑实验之类的（包括其他 post 里的相关代码）。除非你想自己试验一下具体实现和改进，否则可以直接找网上现成的专用的 package ，比如 Spectral Clustering 可以考虑 这个包 。 漫谈 Clustering (番外篇): Dimensionality Reduction 由于总是有各种各样的杂事，这个系列的文章竟然一下子拖了好几个月，（实际上其他的日志我也写得比较少），现在决定还是先把这篇降维的日志写完。我甚至都以及忘记了在这个系列中之前有没有讲过“特征”（feature）的概念了，这里不妨再稍微提一下。机器学习应用到各个领域里，会遇到许多不同类型的数据要处理：图像、文本、音频视频以及物理、生物、化学等实验还有其他工业、商业以及军事上得到的各种数据，如果要为每一种类型的数据都设计独立的算法，那显然是非常不现实的事，因此，机器学习算法通常会采用一些标准的数据格式，最常见的一种格式就是每一个数据对应欧几里德空间里的一个向量。 如果原始的数据格式不兼容，那么就需要首先进行转换，这个过程通常叫做“特征提取”（Feature Extraction），而得到的标准数据格式通常叫做 Feature 。例如，一个最简单的将一个文本 Document 转化为向量的方法如下： 选定特征空间，这里采用三维欧氏空间，三个维度（依次）分别由 to 、be 和 the 表示。 假设待提取的文档是“To be, or not to be: that is the question:”，首先对其进行一些预处理，例如去掉单词的时态后缀、滤掉标点符号等，得到“to be or not to be that be the question”。 统计三个维度所对应的单词出现的频率：to 2 次，be 3 次，the 1 次。 该文档对应的向量即 。 当然，在实际中我们几乎不会这样人工设定空间的各个维度所对应的单词，而通常是从一个数据集中统计出所有出现的词，再将其中的一些挑选出来作为维度。怎样挑选呢？最简单的办法是根本不做任何挑选，或者简单地只是把出现频率太低的单词（维度）去掉。 不过，事实上我们通常会做更复杂一些的处理，例如，如果你是在做 sentiment analysis ，那么你通常会更加关注语气很重的词，比如 “bad”、“terrible”、“awesome” 等的重要性就比普通的词要大，此时你可以为每一个维度设一个权重，例如，给 “bad” 设置权重 2 ，那么出现 3 次的话，向量在该维度对应的值就为2*3 = 6。当然这样手工指定权重只在小范围内可行，如果要为数百万个维度指定权重，那显然是不可能的，另一个稍微自动一点的办法是 tf-idf 。 tf 就是 Term Frequency ，就和刚才说的单词出现的次数差不多，而 idf 则是 Inverse Document Frequency ，通常使用如下公式进行计算： 这相当于自动计算出来的每个单词的权重，其想法很简单：如果在许多文档中都出现的词（例如虚词、语气词等），它所包含的信息量通常会比较小，所以用以上的公式计算出来的权重也会相对较小；另一方面，如果单词并不是在很多文档中都出现的话，很有可能就是出现的那些文档的重要特征，因此权重会相对大一些。 前面说了一堆，其实主要是想要对 feature 做一些“预”处理，让它更“好”一些，手工设置维度的权重固然是很人力，其实 tf-idf 也是在假定了原始 feature 是 document 、term 这样的形式（或者类似的模型）的情况下才适用的（例如，在门禁之类的系统里，feature 可能有声音、人脸图像以及指纹等数据，就不能这样来处理），因此也并不能说是一种通用的方法。 然而，既然机器学习的算法可以在不考虑原始数据的来源和意义的情况下工作，那么 feature 的处理应该也可以。事实也是如此，包括 feature selection 和 dimensionality reduction 两个 topic 都有许多很经典的算法。前者通常是选出重要的 feature 的维度（并抛弃不重要的维度），而后者则是更广泛意义上的把一个高维的向量映射为一个低维向量，亦即“降维”，得到的结果 feature 的值已经不一定是原始的值，也可以把 feature selection 看作是 dimensionality reduction 的一种特殊情况。举一个例子，tf-idf 实际上不算 feature selection ，因为它（通常）并没有丢弃低权值的维度，并且处理过后的特征的每个维度都被乘上了一个权值，不再是原来的值了；但是它却可以被看作一种降维，虽然严格意义上来说维度并没有“降低”。简单来说降维可以看作一个函数，其输入是一个 D 维的向量，输出是一个 M 维的向量。 按照机器学习的方法的一贯作风，我们需要定义目标函数并进行最优化。不同的目标也就导致了不同的降维算法，这也正是今天要讲的话题。 然而，我们的目的究竟是什么呢？一个比较直接的问题是原始的数据量维度太高，我们无法处理，因此需要降维，此时我们通常希望在最大限度地降低数据的维度的前提下能够同时保证保留目标的重要的信息，就好比在做有损的数据压缩时希望压缩比尽量大但是质量损失不要太多。于是问题又转化为如何衡量对信息的保留程度了。 一个最直接的办法就是衡量 reconstruction error ，即 其中 是 所对应的低维表示再重新构造出来的高维形式，就相当于是压缩之后解压出来的结果，不过虽然有许多压缩方法都是无损的，就是说这个差值会等于零，但是大部分降维的结果都是有损的。不过我们仍然希望把上面的 reconstruction error 最小化。 另外一种方式是简单地使用 variance 来衡量所包含信息量，例如，我们要把一些 D 维的向量降为 1 维，那么我们希望这一维的 variance 达到最大化，亦即： 其中 是降维函数。推而广之，如果是降为 2 维，那么我希望第 2 维去关注第 1 维之外的 variance ，所以要求它在与第一维垂直的情况下也达到 variance 最大化。以此类推。 然而，当我们把降维函数 限定维线性的时候，两种途径会得到同样的结果，就是被广泛使用的 Principal Components Analysis (PCA) 。PCA 的降维函数是线性的，可以用一个 维的矩阵 来表示，因此，一个 D 维的向量 经过线性变换 之后得到一个 M 维向量，就是降维的结果。把原始数据按行排列为一个 维的矩阵 ，则 就是降维后的 维的数据矩阵，目标是使其 covariance 矩阵最大。在数据被规则化（即减去其平均值）过的情况下，协方差矩阵 （covariance） ，当然矩阵不是一个数，不能直接最大化，如果我们采用矩阵的 Trace （亦即其对角线上元素的和）来衡量其大小的话，要对 求最大化，只需要求出 的特征值和特征向量，将 M 个最大的特征值所对应的特征向量按列排列起来组成线性变换矩阵 即可。这也就是 PCA 的求解过程，得到的降维矩阵 可以直接用到新的数据上。如果熟悉 Latent Semantic Analysis (LSA) 的话，大概已经看出 PCA 和 Singular Value Decomposition (SVD) 以及 LSA 之间的关系了。以下这张图（引自《The Elements of Statistical Learning》）可以直观地看出来 PCA 做了什么，对于一些原始为二维的数据，PCA 首先找到了 variance 最大的那一个方向： PCA 作为一种经典的降维方法，被广泛地应用于机器学习、计算机视觉以及信息检索等各个领域，其地位类似于聚类中的 K-means ，在现在关于降维等算法的研究中也经常被作为 baseline 出现。然而，PCA 也有一些比较明显的缺点：一个就是 PCA 降维是线性变换，虽然线性变换计算方便，并且可以很容易地推广到新的数据上，然而有些时候线性变换也许并不合适，为此有许多扩展被提出来，其中一个就是 Kernel PCA ，用 Kernel Trick 来将 PCA 推广到非线性的情况。另外，PCA 实际上可以看作是一个具有 Gaussian 先验和条件概率分布的 latent variable 模型，它假定数据的 mean 和 variance 是重要的特征，并依靠 covariance 最大化来作为优化目标，而事实上这有时候对于解决问题帮助并不大。 一个典型的问题就是做聚类或分类，回想我们之前谈过的 Spectral Clustering ，就是使用 Laplacian eigenmap 降维之后再做 K-means 聚类，如果问题定下来了要对数据进行区分的话，“目的”就变得明朗了一些，也就是为了能够区分不同类别的数据，再考虑直观的情况，我们希望如果通过降维把高维数据变换到一个二维平面上的话，可以很容易“看”出来不同类别的数据被映射到了不同的地方。虽然 PCA 极力降低 reconstruction error ，试图得到可以代表原始数据的 components ，但是却无法保证这些 components 是有助于区分不同类别的。如果我们有训练数据的类别标签，则可以用 Fisher Linear Discriminant Analysis 来处理这个问题。 同 PCA 一样，Fisher Linear Discriminant Analysis 也是一个线性映射模型，只不过它的目标函数并不是 Variance 最大化，而是有针对性地使投影之后属于同一个类别的数据之间的 variance 最小化，并且同时属于不同类别的数据之间的 variance 最大化。具体的形式和推导可以参见《Pattern Classification》这本书的第三章 Component Analysis and Discriminants 。 当然，很多时候（比如做聚类）我们并不知道原始数据是属于哪个类别的，此时 Linear Discriminant Analysis 就没有办法了。不过，如果我们假设原始的数据形式就是可区分的的话，则可以通过保持这种可区分度的方式来做降维， MDS 是 PCA 之外的另一种经典的降维方法，它降维的限制就是要保持数据之间的相对距离。实际上 MDS 甚至不要求原始数据是处在一个何种空间中的，只要给出他们之间的相对“距离”，它就可以将其映射到一个低维欧氏空间中，通常是三维或者二维，用于做 visualization 。 不过我在这里并不打算细讲 MDS ，而是想说一下在 Spectral Clustering 中用到的降维方法 Laplacian Eigenmap 。同 MDS 类似，LE 也只需要有原始数据的相似度矩阵，不过这里通常要求这个相似度矩阵 具有局部性质，亦即只考虑局部领域内的相似性，如果点 和 距离太远的话， 应该为零。有两种很直接的办法可以让普通的相似度矩阵具有这种局部性质： 通过设置一个阈值，相似度在阈值以下的都直接置为零，这相当于在一个 -领域内考虑局部性。 对每个点选取 k 个最接近的点作为邻居，与其他的点的相似性则置为零。这里需要注意的是 LE 要求相似度矩阵具有对称性，因此，我们通常会在 属于 的 k 个最接近的邻居且/或反之的时候，就保留 的值，否则置为零。 构造好 之后再来考虑降维，从最简单的情况开始，即降到一维 ，通过最小化如下目标函数来实现： 从直观上来说，这样的目标函数的意义在于：如果原来 和 比较接近，那么 会相对比较大，这样如果映射过后 和 相差比较大的话，就会被权重 放大，因此最小化目标函数就保证了原来相近的点在映射过后也不会彼此相差太远。 令 为将 的每一行加起来所得到的对角阵，而 ，被称作是拉普拉斯矩阵，通过求解如下的特征值问题 易知最小的那个特征值肯定是 0 ，除此之外的最小的特征值所对应的特征向量就是映射后的结果。特征向量是一个 N 维列向量，将其旋转一下，正好是 N 个原始数据降到一维之后的结果。 类似地推广到 M 维的情况，只需要取除去 0 之外的最小的 M 个特征值所对应的特征向量，转置之后按行排列起来，就是降维后的结果。用 Matlab 代码写出来如下所示（使用了 knn 来构造相似度矩阵，并且没有用 heat kernel ）： %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 事实上，Laplacian Eigenmap 假设数据分布在一个嵌套在高维空间中的低维流形上， Laplacian Matrix 则是流形的 Laplace Beltrami operator 的一个离散近似。关于流形以及 Laplacian Eigenmap 这个模型的理论知识就不在这里做更多地展开了，下面看一个比较直观的例子 Swiss Roll 。 Swiss Roll 是一个像面包圈一样的结构，可以看作一个嵌套在三维空间中的二维流形，如下图所示，左边是 Swiss Roll ，右边是从 Swiss Roll 中随机选出来的一些点，为了标明点在流形上的位置，给它们都标上了颜色。 而下图是 Laplacian Eigenmap 和 PCA 分别对 Swiss Roll 降维的结果，可以看到 LE 成功地把这个流形展开把在流形上属于不同位置的点映射到了不同的地方，而 PCA 的结果则很糟糕，几种颜色都混杂在了一起。 另外，还有一种叫做 Locally Linear Embedding 的降维方法，它同 LE 一样采用了流形假设，并假定平滑流形在局部具有线性性质，一个点可以通过其局部邻域内的点重构出来。首先它会将下式最小化 以求解出最优的局部线性重构矩阵 ，对于距离较远的点 和 ， 应当等于零。这之后再把 当作已知量对下式进行最小化： 这里 成了变量，亦即降维后的向量，对这个式子求最小化的意义很明显了，就是要求如果原来的数据 可以以 矩阵里对应的系数根据其邻域内的点重构出来的话，那么降维过后的数据也应该保持这个性质。 经过一些变换之后得到的求解方法和 LE 类似，也是要求解一个特征值问题，实际上，从理论上也可以得出二者之间的联系（LE 对应于 而 LLE 对应于 ），如果感兴趣的话，可以参考 Laplacian Eigenmaps for Dimensionality Reduction and Data Representation 这篇论文里的对比。下面是两种方法在 Swiss Roll 数据上的结果，也是非常相似的： 有一点需要注意的是，LE 和 LLE 都是非线性的方法，PCA 得到的结果是一个投影矩阵，这个结果可以保存下来，在之后对任意向量进行投影，而 LE 和 LLE都是直接得出了数据降维之后的结果，但是对于新的数据，却没有得到一个“降维函数”，没有一个合适的方法得到新的数据的降维结果。所以，在人们努力寻求非线性形式扩展 PCA 的时候，另一些人则提出了 LE 和 LLE 的线性形式，分别叫做 Locality Preserving Projection 和 Neighborhood Preserving Embedding 。 在 LPP 中，降维函数跟 PCA 中一样被定为是一个线性变换，用一个降维矩阵 来表示，于是 LE 的目标函数变为 经过类似的推导，最终要求解的特征值问题如下： 得到的按照特征值从小到大排序的特征向量就组成映射矩阵 ，和 LE 不同的是这里不需要去掉第一个特征向量。另一点是在 LE 中的特征值是一个稀疏的特征值问题，在只需要求解最小的几个特征值的时候可以比较高效地求解，而这里的矩阵在乘以 之后通常就不再稀疏了，计算量会变得比较大，这个问题可以使用 Spectral Regression 的方法来解决，参见 Spectral Regression: A Unified Approach for Sparse Subspace Learning 这篇 paper 。如果采用 Kernel Trick 再把 LPP 非线性化的话，又会回到 LE 。而 LLE 的线性版本 NPE 也是采用了类似的办法来得到的，就不在这里多讲了。 另外，虽然 LE 是 unsupervised 的，但是如果训练数据确实有标签可用，也是可以加以利用的——在构造相似度矩阵的时候，属于同一类别的相似度要大一些，而不同类别的相似度则会小一些。 当然，除去聚类或分类之外，降维本身也是一种比较通用的数据分析的方法，不过有许多人批评降维，说得到的结果没有意义，不用说非线性，就是最简单的线性降维，除去一些非藏极端的特殊情况的话，通常将原来的分量线性组合一下都不会得到什么有现成的物理意义的量了。然而话也说回来，现在的机器学习几乎都是更 prefer “黑盒子”式的方法吧，比如决策树，各个分支对应与变量的话，它的决策过程其实人是可以“看到”或者说“理解”的，但是 SVM 就不那么“直观“了，如果再加上降维处理，就更加“不透明”了。不过我觉得这没什么不好的，如果只是靠可以清晰描诉出来的 rule 的话，似乎感觉神秘感不够，没法发展出“智能”来啊 ^_^bb 最后，所谓有没有物理意义，其实物理量不过也都是人为了描述问题方便而定义出来的吧。 漫谈 Clustering (5): Hierarchical Clustering 系列不小心又拖了好久，其实正儿八经的 blog 也好久没有写了，因为比较忙嘛，不过觉得 Hierarchical Clustering 这个话题我能说的东西应该不多，所以还是先写了吧（我准备这次一个公式都不贴 ）。Hierarchical Clustering 正如它字面上的意思那样，是层次化的聚类，得出来的结构是一棵树，如右图所示。在前面我们介绍过不少聚类方法，但是都是“平坦”型的聚类，然而他们还有一个更大的共同点，或者说是弱点，就是难以确定类别数。实际上，（在某次不太正式的电话面试里）我曾被问及过这个问题，就是聚类的时候如何确定类别数。 我能想到的方法都是比较 naive 或者比较不靠谱的，比如： 根据数据的来源使用领域相关的以及一些先验的知识来进行估计——说了等于没有说啊…… 降维到二维平面上，然后如果数据形状比较好的话，也许可以直观地看出类别的大致数目。 通过谱分析，找相邻特征值 gap 较大的地方——这个方法我只了解个大概，而且我觉得“较大”这样的词也让它变得不能自动化了。 当时对方问“你还有没有什么问题”的时候我竟然忘记了问他这个问题到底有没有什么更好的解决办法，事后真是相当后悔啊。不过后来在实验室里询问了一下，得到一些线索，总的来说复杂度是比较高的，待我下次有机会再细说（先自己研究研究）。 不过言归正传，这里要说的 Hierarchical Clustering 从某种意义上来说也算是解决了这个问题，因为在做 Clustering 的时候并不需要知道类别数，而得到的结果是一棵树，事后可以在任意的地方横切一刀，得到指定数目的 cluster ，按需取即可。 听上去很诱人，不过其实 Hierarchical Clustering 的想法很简单，主要分为两大类：agglomerative（自底向上）和 divisive（自顶向下）。首先说前者，自底向上，一开始，每个数据点各自为一个类别，然后每一次迭代选取距离最近的两个类别，把他们合并，直到最后只剩下一个类别为止，至此一棵树构造完成。 看起来很简单吧？ 其实确实也是比较简单的，不过还是有两个问题需要先说清除才行： 如何计算两个点的距离？这个通常是 problem dependent 的，一般情况下可以直接用一些比较通用的距离就可以了，比如欧氏距离等。 如何计算两个类别之间的距离？一开始所有的类别都是一个点，计算距离只是计算两个点之间的距离，但是经过后续合并之后，一个类别里就不止一个点了，那距离又要怎样算呢？到这里又有三个变种： Single Linkage：又叫做 nearest-neighbor ，就是取两个集合中距离最近的两个点的距离作为这两个集合的距离，容易造成一种叫做 Chaining 的效果，两个 cluster 明明从“大局”上离得比较远，但是由于其中个别的点距离比较近就被合并了，并且这样合并之后 Chaining 效应会进一步扩大，最后会得到比较松散的 cluster 。 Complete Linkage：这个则完全是 Single Linkage 的反面极端，取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的，限制非常大，两个 cluster 即使已经很接近了，但是只要有不配合的点存在，就顽固到底，老死不相合并，也是不太好的办法。 Group Average：这种方法看起来相对有道理一些，也就是把两个集合中的点两两的距离全部放在一起求一个平均值，相对也能得到合适一点的结果。 总的来说，一般都不太用 Single Linkage 或者 Complete Linkage 这两种过于极端的方法。整个 agglomerative hierarchical clustering 的算法就是这个样子，描述起来还是相当简单的，不过计算起来复杂度还是比较高的，要找出距离最近的两个点，需要一个双重循环，而且 Group Average 计算距离的时候也是一个双重循环。 另外，需要提一下的是本文一开始的那个树状结构图，它有一个专门的称呼，叫做 Dendrogram ，其实就是一种二叉树，画的时候让子树的高度和它两个后代合并时相互之间的距离大小成比例，就可以得到一个相对直观的结构概览。不妨再用 最开始 生成的那个三个 Gaussian Distribution 的数据集来举一个例子，我采用 Group Average 的方式来计算距离，agglomerative clustering 的代码很简单，没有做什么优化，就是直接的双重循环： 数据点又一千多个，画出来的 dendrogram 非常大，为了让结果看起来更直观一点，我把每个叶节点用它本身的 label 来染色，并且向上合并的时候按照权重混合一下颜色，最后把图缩放一下得到这样的一个结果（点击查看原图）： 或者可以把所有叶子节点全部拉伸一下看，在右边对齐，似乎起来更加直观一点： 从这个图上可以很直观地看出来聚类的结果，形成一个层次，而且也在总体上把上个大类分开来了。由于这里我把图横过来画了，所以在需要具体的 flat cluster 划分的时候，直观地从图上可以看成竖着划一条线，打断之后得到一片“森林”，再把每个子树里的所有元素变成一个“扁平”的集合即可。完整的 Python 代码如下： agglomerative clustering 差不多就这样了，再来看 divisive clustering ，也就是自顶向下的层次聚类，这种方法并没有 agglomerative clustering 这样受关注，大概因为把一个节点分割为两个并不如把两个节点结合为一个那么简单吧，通常在需要做 hierarchical clustering 但总体的 cluster 数目又不太多的时候可以考虑这种方法，这时可以分割到符合条件为止，而不必一直分割到每个数据点一个 cluster 。 总的来说，divisive clustering 的每一次分割需要关注两个方面：一是选哪一个 cluster 来分割；二是如何分割。关于 cluster 的选取，通常采用一些衡量松散程度的度量值来比较，例如 cluster 中距离最远的两个数据点之间的距离，或者 cluster 中所有节点相互距离的平均值等，直接选取最“松散”的一个 cluster 来进行分割。而分割的方法也有多种，比如，直接采用普通的 flat clustering 算法（例如 k-means）来进行二类聚类，不过这样的方法计算量变得很大，而且像 k-means 这样的和初值选取关系很大的算法，会导致结果不稳定。另一种比较常用的分割方法如下： 待分割的 cluster 记为 G ，在 G 中取出一个到其他点的平均距离最远的点 x ，构成新 cluster H； 在 G 中选取这样的点 x’ ，x’ 到 G 中其他点的平均距离减去 x’ 到 H 中所有点的平均距离这个差值最大，将其归入 H 中； 重复上一个步骤，直到差值为负。 到此为止，我的 hierarchical clustering 介绍就结束了。总的来说，在我个人看来，hierarchical clustering 算法似乎都是描述起来很简单，计算起来很困难（计算量很大）。并且，不管是 agglomerative 还是 divisive 实际上都是贪心算法了，也并不能保证能得到全局最优的。而得到的结果，虽然说可以从直观上来得到一个比较形象的大局观，但是似乎实际用处并不如众多 flat clustering 算法那么广泛。
个人分类: 科研笔记|6946 次阅读|6 个评论
共现分析乱弹（2）
zilu85 2012-8-11 11:14
2.聚类结果的判读问题 如何判读共现聚类分析的结果，或者具体地说，系统聚类的树状图中区分类的相似性阈值到底选多少？私下里认为：应当遵循一个“局部最优化”的原则。 以某个学科（如物理学）当前的研究结构的分析为例，我们对其高被引论文做了同被引聚类分析或者高频主题词的共现聚类分析，其结果反映了这个学科活动的实际状况，这是毋庸置疑的，但是我们要记住，我们也只是从一定程度上或者一定侧面上了解和表现了这个对象。对于这个学科的专家而言，多年的学习和研究在他们的脑子里已经形成了这个学科的知识框架结构，你偏要说你的共现分析结果是客观的，正确的，其实可能是武断的。我们和专家一样都是站在不同的角度看一个问题，何况我们毕竟是为人家服务的，“做事不由东，累死也无功”。 局部最优，就是强调在聚类的小范围内是合理的，最先聚集到一起的论文和词是有显著意义的，在树状结构图中最底层的几个小类是可以称作一个研究方向或者热点的；而在大范围上，不要通过聚类树状图说物理科学的研究主要分成几个大的部分，这几个大的部分又包括几个小的部分，......。就是说，遵循自下而上的原则，越往上其合理性就越差。你可以尝试对一组数据用不同的相思系数和不同类间距离的计算方法（如最大最小平均距离等），其小类是比较稳固的，大类则是多变的。 因此，在共现分析的具体实践中，除了在决定类数和解读聚类结果中保持“局部最优”的理念之外，还应当注意选择侧重局部最优的聚类算法，而不必追求全局参与的聚类算法。
个人分类: 文献计量学|4380 次阅读|0 个评论
【阅读笔记】Query日志挖掘、聚类
poson 2012-4-5 14:57
背景： 《Mining Concept Sequence from Large-Scale Search Logs for Context-Aware Query Suggestion》这是微软研究院的一篇论文。第一作者是南开大学 Liao Zhen ，主页是 http://kdd.nankai.edu.cn/showMemberAction.do?tp=0id=80 。 这篇论文的目的是Query推荐，也就是关键词推荐。在搜索引擎、广告竞价平台中，关键词推荐已经是标配的产品。 同样是搜索引个词，不同的人有不同的意图。这是为什么呢？原因是一个词可能对应到多个概念（或者说是多个类目）。例如“glodiator”（角斗士）这个词，用户可能是想搜索电影，也有人想搜索角斗士的历史，也可能是找著名的角斗士。其实这种情况搜索引擎已经解决的挺好了，搜索引擎一般会同时考虑准确率和多样性的问题，一般它会把用户query的多种意图都检索出来。例如“角斗士”这个Query，搜索引擎可能包百科页面（角斗士历史）、视频（电影）、blog（用户评价）、图片（电影海报、演员）都返回给检索用户。 在很多论文中，搜索引擎希望通过用户的查询或者浏览历史来做更好的判断。这个想法看似简单，时间上比较困难。试想，前一分钟用户还在搜索“nokia 手机”，后一分钟用户搜索“连衣裙”或者“nokia 手机壳”，一个是从手机概念转变为女装，另外一个是从手机概念转变为“手机配件”。在这种情况下，你必须记录每个用户在session时间内的浏览历史，根据用户查询的概念来看和当前的概念是否有关系。当当前的概念比较模糊的时候，看能否通过以前的历史做相应的补充。 聚类过程 论文中介绍的过程很简单，先做概念（concept）的聚类，然后找到concept，用每个concept中浏览次数最多的Query作为代表。用户浏览次数的最多的Query作为cluster的代表，这本身就是一种折中和简单的方法。或许从用cluster中提取一批具有代表性的词或者短语来代表更有说服力。 相关工作： 以前的工作更多的是看用户的点击反馈。关键词分类可以用点击反馈，CTR预估是点击返回，协同过滤也可以看成是点击反馈。 Session-Based approaches：Boldi 的Query-Flow方法 Doc-Click Based approaches：或者可以说是Query-Click URL based bipartite graph 方法。这里更多的是指Random Walk的方法。关注于通过二分图得到query的相关关系。 Query-Doc转移概率矩阵 从Baeza-Yates，Beeferman和Berger，Wen ，有不少通过二部图来计算query相似性，或者聚类的文章。 这里转移概率的定义没有什么特别的东西，甚至非常简单。就是通过query节点看发散概率，或者通过URL节点看发散概率。时间上在 《 Random Walks on the Click Graph 》 这篇文章中对转移概率的定义更加细致一些。 在这里实际上还是根据Q-U的矩阵× U-Q的矩阵 迭代最后再乘 Q-U的矩阵。 最终时间上还是得到一个Query-URL向量的一个VSM模型。两个Query直接的距离，转换为两个URL向量之间的距离。从本质上看，这个思想是非常基础的。但是论文后面的亮点是对Query距离计算。 Query用URL向量表示，那么如何减少需要计算的QueryPair 数量就是非常重要的。他把URL看成倒排索引，只有两个Query有共同的URL的时候才需要计算相关性。 后面很长的篇幅是将计算的实现，以及如何应用到分布式上面去。 Concept: 用cluster中Query的URL向量的均值向量表示。
个人分类: query rewrite|5021 次阅读|0 个评论
“类”是怎么得到的？
lg21c 2012-3-27 16:34
“类”，英文中的class，是怎么得到的？是天生的？其实“类”是人类为了认知便利而对事物的区分。有时区分是容易的，因为事物之间的区别明显，比如男人与女人，红色与白色，但这绝不意味着“类”是天生的。有时甚至在绝对意义下，事物之间的界限是模糊的，需要从能够得到的观察维度，人为地定出“类”，是所谓“类”是聚出来的。
个人分类: 连续论|2786 次阅读|0 个评论
关于聚类的一些经验及其在R中的实现
friendpine 2012-3-19 15:15
1 首先针对数据进行分析，回答下面的问题： 1 ）想用聚类方法解决什么问题。是想看数据的结构，还是想把数据分为很多类，还是有其他的目的。 2 ）数据本身的分布。针对样本聚类还是针对变量聚类？样本可能符合怎样的分布？变量又会符合怎样的分布？ 2 选择合适的聚类方法 针对聚类目的和数据的分布，选择合适的方法。一般来说，层次聚类比较适合用来分析数据的结构，因此可以用来做初步的聚类，从而对数据的结构有一个初步的了解。 k-means 聚类需要指定类别数。还有很多其他的聚类方法。针对数据分布，需要选择合理的方法计算聚类对象之间的相似性，一般采用基于距离或者基于相关性的方法。 3 确定聚类数 这个问题很难确定，除非已经有了很好的先验知识。这和下面的问题很相关。 4 评估聚类效果好坏 如果有金标准，则用它们来判断聚类效果是最合适的。如果没有的话，则首先要考虑聚类的目的，然后聚类结果应该与已有先验知识相吻合。 此外，还有一些方法可以用来判断聚类效果。一个是聚类结果是否稳定，即如果聚类方法涉及到参数的选择，可能有的结果对于参数很敏感；另外一个是不同聚类方法的一致性如何。如果不同的方法得到的聚类都很一致，则效果较好。 在R中有很多包可以做聚类分析，下面是CRAN上总结的用于聚类的包： 见（ http://cran.r-project.org/web/views/Cluster.html ） Hierarchical Clustering: Functionshclust()from package stats andagnes()from cluster are the primary functions for agglomerative hierarchical clustering, functiondiana()can be used for divisive hierarchical clustering. Faster alternatives tohclust()are provided by the packages fastcluster and flashClust . Functiondendrogram()from stats and associated methods can be used for improved visualization for cluster dendrograms. Package dynamicTreeCut contains methods for detection of clusters in hierarchical clustering dendrograms. hybridHclust implements hybrid hierarchical clustering via mutual clusters. Package isopam uses an algorithm which is based on the classification of ordination scores from isometric feature mapping. The classification is performed either as a hierarchical, divisive method or as non-hierarchical partitioning. Package LLAhclust provides likelihood linkage analysis hierarchical clustering. The package protoclust implements a form of hierarchical clustering that associates a prototypical element with each interior node of the dendrogram. Using the package'splot()function, one can produce dendrograms that are prototype-labeled and are therefore easier to interpret. pvclust is a package for assessing the uncertainty in hierarchical cluster analysis. It provides approximately unbiased p-values as well as bootstrap p-values. Package sparcl provides clustering for a set of n observations when p variables are available, where p n . It adaptively chooses a set of variables to use in clustering the observations. Sparse K-means clustering and sparse hierarchical clustering are implemented. Partitioning Clustering: Functionkmeans()from package stats provides several algorithms for computing partitions with respect to Euclidean distance. Functionpam()from package cluster implements partitioning around medoids and can work with arbitrary distances. Functionclara()is a wrapper topam()for larger data sets. Silhouette plots and spanning ellipses can be used for visualization. Package apcluster implements Frey's and Dueck's Affinity Propagation clustering. The algorithms in the package are analogous to the Matlab code published by Frey and Dueck. Package bayesclust allows to test and search for clusters in a hierarchical Bayes model. Package clues provides a clustering method based on local shrinking. Package clusterSim allows to search for the optimal clustering procedure for a given dataset. Package flexclust provides k-centroid cluster algorithms for arbitrary distance measures, hard competitive learning, neural gas and QT clustering. Neighborhood graphs and image plots of partitions are available for visualization. Some of this functionality is also provided by package cclust . Package kernlab provides a weighted kernel version of the k-means algorithm bykkmeansand spectral clustering byspecc. Packages kml and kml3d provide k-means clustering specifically for longitudinal (joint) data. Package optpart contains a set of algorithms for creating partitions and coverings of objects largely based on operations on similarity relations (or matrices). Package pdfCluster provides tools to perform cluster analysis via kernel density estimation. Clusters are associated to the maximally connected components with estimated density above a threshold. Package skmeans allows spherical k-Means Clustering, i.e. k-means clustering with cosine similarity. It features several methods, including a genetic and a simple fixed-point algorithm and an interface to the CLUTO vcluster program for clustering high-dimensional datasets. Package trimcluster provides trimmed k-means clustering. Package tclust also allows for trimmed k-means clustering. In addition using this package other covariance structures can also be specified for the clusters. Model-based Clustering: ML estimation: Package mclust fits mixtures of Gaussians using the EM algorithm. It allows fine control of volume and shape of covariance matrices and agglomerative hierarchical clustering based on maximum likelihood. It provides comprehensive strategies using hierarchical clustering, EM and the Bayesian Information Criterion (BIC) for clustering, density estimation, and discriminant analysis. Please note the license under which this package is distributed. Except for strict academic use, use of mclust (by itself or through other packages) requires payment of an annual license fee and completion of a license agreement. Package HDclassif provides functionhddcto fit Gaussian mixture model to high-dimensional data where it is assumed that the data lives in a lower dimension than the original space. mritc provides tools for classification using normal mixture models and (higher resolution) hidden Markov normal mixture models fitted by various methods. prabclus clusters a presence-absence matrix object by calculating an MDS from the distances, and applying maximum likelihood Gaussian mixtures clustering to the MDS points. Package MetabolAnalyze fits mixtures of probabilistic principal component analysis with the EM algorithm. Fitting finite mixtures of uni- and multivariate scale mixtures of skew-normal distributions with the EM algorithm is provided by package mixsmsn . Package movMF fits finite mixtures of von Mises-Fisher distributions with the EM algorithm. Package MFDA implements model-based functional data analysis. For grouped conditional data package mixdist can be used. Package mixRasch estimates mixture Rasch models, including the dichotomous Rasch model, the rating scale model, and the partial credit model with joint maximum likelihood estimation. Package pmclust allows to use unsupervised model-based clustering for high dimensional (ultra) large data. The package uses Rmpi to perform a parallel version of the EM algorithm for mixtures of Gaussians. Bayesian estimation: Bayesian estimation of finite mixtures of multivariate Gaussians is possible using package bayesm . The package provides functionality for sampling from such a mixture as well as estimating the model using Gibbs sampling. Additional functionality for analyzing the MCMC chains is available for averaging the moments over MCMC draws, for determining the marginal densities, for clustering observations and for plotting the uni- and bivariate marginal densities. Package bayesmix provides Bayesian estimation using JAGS. Package Bmix provides Bayesian Sampling for stick-breaking mixtures. Package bclust allows Bayesian clustering using a spike-and-slab hierarchical model and is suitable for clustering high-dimensional data. Package dpmixsim fits Dirichlet process mixture models using conjugate models with normal structure. Package profdpm determines the maximum posterior estimate for product partition models where the Dirichlet process mixture is a specific case in the class. Package mixAK contains a mixture of statistical methods including the MCMC methods to analyze normal mixtures with possibly censored data. Package GSM fits mixtures of gamma distributions. Package mcclust implements methods for processing a sample of (hard) clusterings, e.g. the MCMC output of a Bayesian clustering model. Among them are methods that find a single best clustering to represent the sample, which are based on the posterior similarity matrix or a relabelling algorithm. Package rjags provides an interface to the JAGS MCMC library which includes a module for mixture modelling. Other estimation methods: Package AdMit allows to fit an adaptive mixture of Student-t distributions to approximate a target density through its kernel function. Circular and orthogonal regression clustering using redescending M-estimators is provided by package edci . Robust estimation using Weighted Likelihood can be done with package wle . Package pendensity estimates densities with a penalized mixture approach. Other Cluster Algorithms: Package amap provides alternative implementations of k-means and agglomerative hierarchical clustering. Package biclust provides several algorithms to find biclusters in two-dimensional data. Package isa2 provides the Iterative Signature Algorithm (ISA) for biclustering. Package cba implements clustering techniques for business analytics like "rock" and "proximus". Package CHsharp clusters 3-dimensional data into their local modes based on a convergent form of Choi and Hall's (1999) data sharpening method. Package clue implements ensemble methods for both hierarchical and partitioning cluster methods. Package CoClust implements a cluster algorithm that is based on copula functions and therefore allows to group observations according to the multivariate dependence structure of the generating process without any assumptions on the margins. Fuzzy clustering and bagged clustering are available in package e1071 . Package compHclust provides complimentary hierarchical clustering which was especially designed for microarray data to uncover structures present in the data that arise from 'weak' genes. Package FactoClass performs a combination of factorial methods and cluster analysis. The hopach algorithm is a hybrid between hierarchical methods and PAM and builds a tree by recursively partitioning a data set. For graphs and networks model-based clustering approaches are implemented in packages latentnet and mixer . Package nnclust allows fast clustering of large data sets by constructing a minimum spanning tree for each cluster. For each cluster the procedure is stopped when the nearest-neighbour distance rises above a specified threshold. A set of clusters and a set of "outliers" not in any cluster is returned. The algorithm works best for well-separated clusters in up to 8 dimensions, and sample sizes up to hundreds of thousands. Package randomLCA provides the fitting of latent class models which optionally also include a random effect. Package poLCA allows for polytomous variable latent class analysis and regression. Package RPMM fits recursively partitioned mixture models for Beta and Gaussian Mixtures. This is a model-based clustering algorithm that returns a hierarchy of classes, similar to hierarchical clustering, but also similar to finite mixture models. Package segclust fits a segmentation/clustering model. A mixture of univariate gaussian distributions is used for the cluster structure and segments are assumed to arise because switching between clusters over time occurs. Self-organizing maps are available in package som . Several packages provide cluster algorithms which have been developped for bioinformatics applications. These packages include FunCluster for profiling microarray expression data, MMG for mixture models on graphcs, and ORIClust for order-restricted information-based clustering. Cluster-wise Regression: Package flexmix implements an user-extensible framework for EM-estimation of mixtures of regression models, including mixtures of (generalized) linear models. Package fpc provides fixed-point methods both for model-based clustering and linear regression. A collection of asymmetric projection methods can be used to plot various aspects of a clustering. Multigroup mixtures of latent Markov models on mixed categorical and continuous data (including time series) can be fitted using depmix or depmixS4 . The parameters are optimized using a general purpose optimization routine given linear and nonlinear constraints on the parameters. Package mixreg fits mixtures of one-variable regressions and provides the bootstrap test for the number of components. Package lcmm fits a latent class linear mixed model which is also known as growth mixture model or heterogeneous linear mixed model using a maximum likelihood method. moc fits mixture models to multivariate mixed data using a Newton-type algorithm. The component specific distribution may have one, two or three parameters. Covariates and concomitant variables can be specified as well as constraints for the parameters. mixtools provides fitting with the EM algorithm for parametric and non-parametric (multivariate) mixtures. Parametric mixtures include mixtures of multinomials, multivariate normals, normals with repeated measures, Poisson regressions and Gaussian regressions (with random effects). Non-parametric mixtures include the univariate semi-parametric case where symmetry is imposed for identifiability and multivariate non-parametric mixtures with conditional independent assumption. In addition fitting mixtures of Gaussian regressions with the Metropolis-Hastings algorithm is available. mixPHM fits mixtures of proportional hazard models with the EM algorithm. Package gamlss.mx fits finite mixtures of of gamlss family distributions. Additional Functionality: Mixtures of univariate normal distributions can be printed and plotted using package nor1mix . Packages gcExplorer and clusterfly allow to visualise the results of clustering algorithms. Package clusterGeneration contains functions for generating random clusters and random covariance/correlation matrices, calculating a separation index (data and population version) for pairs of clusters or cluster distributions, and 1-D and 2-D projection plots to visualize clusters. Alternatively MixSim generates a finite mixture model with Gaussian components for prespecified levels of maximum and/or average overlaps. This model can be used to simulate data for studying the performance of cluster algorithms. For cluster validation package clusterRepro tests the reproducibility of a cluster. Package clv contains popular internal and external cluster validation methods ready to use for most of the outputs produced by functions from package cluster and clValid calculates several stability measures. Package clustTool provides a GUI for clustering data with spatial information. Package clustvarsel provides variable selection for model-based clustering. Functionality to compare the similarity between two cluster solutions is provided bycluster.stats()in package fpc . clusterCons allows to calculate the consensus clustering result from re-sampled clustering experiments with the option of using multiple algorithms and parameters. The stability of k-centroid clustering solutions fitted using functions from package flexclust can also be validated viabootFlexclust()using bootstrap methods. Package MOCCA provides methods to analyze cluster alternatives based on multi-objective optimization of cluster validation indices. Package SDisc provides an integrated methodology for the identification of homogeneous profiles in a data distribution by including methods for data treatment and pre-processing, repeated cluster analysis, model selection, model reliability and reproducibility assessment, profiles characterization and validation by visual and table summaries. Package sigclust provides a statistical method for testing the significance of clustering results.
个人分类: 统计学与R语言学习|21950 次阅读|0 个评论
团拜会与鸡尾酒会上的聚类—趣味数据挖掘之七
热度 33 tangchangjie 2011-12-28 09:54
团拜会与鸡尾酒会上的聚类—趣味数据挖掘之七(唐常杰） 在硕博士生的数据挖掘课程中，聚类是难点，一文难尽。此文用宴会上的见闻，用 异于传统的 方式，从讲课PPT上取些素材（这样比较快），来说明聚类的一些概念，为下篇做些铺垫，下篇将通过通俗的例子说明一个著名的方法。 团拜会上一道风景线 岁末年初，参加了几个团拜会。朋友们都知道我对酒特过敏，宽容地让我以茶代酒，因而能在酒席上清醒地倾听、观察和记忆，并在这里调侃敬酒的艺术。 社会是由各种纽带联络而成的人的集合，敬酒是众多纽带中的一种。老百姓敬酒传达亲情友情；伟人（如罗斯福、斯大林）的敬酒也是政治；文人敬酒吟诗作赋，企业家敬酒不忘投资。作为数据挖掘阵地上的戒酒一兵，笔者在敬酒中观察到了聚类技术的应用。 敬酒与聚类技术 善敬酒者都是聚类专家，试看下例： “赵总，你我 同学 多年， 这一杯酒你要喝了， … “老张，你我 一 同扛过枪 ，这一杯酒你要干了 ,… “老李，你我 同乡 兼 同学 ， 感情深，这杯一口闷， …… 善劝酒者总是抓住自己与被敬酒者的相同点，说对方和自己聚在同一个“簇” ，令对方推迟不得，用的是对称聚类技术；“簇” --cluster ，有时也译为“类”。 当对方非常德高望重，不好意思把对方和自己聚成一簇，敬酒人会找几个同簇人士壮胆，说“我们几位同YYY，一起来敬..."; 有时，还分“簇”发起集团冲锋，让对方喝得尽兴；仔细思量，用的是非对称（或单侧）聚类技术。 常用敬酒词汇与短语还有：同学、同乡、同事、一同下过乡、一起扛过枪,...,等等。 如果一时找不到具体的共同点，对炎黄子孙，总可用“同胞”。 上述的 “同学”、“同乡”等名词, 相当于英文中的 Homo-Something, 在数据库技术中称为属性,对应英文单词 Attribute， 所以，这种敬酒技巧可泛称为 同A 技巧, 同 A 技巧的推广 同 A技巧还可推广。例如，假如那一天来临，科幻迷有机会到银河系中心开 联合星系 （联合国的推广）团拜会，来的都是广义人（外星智慧生命），见“人”都可称 同系 ( 同一个银河系 ) ；如果见到了我们这个太阳系的火星人，那简直是老乡见老乡，两眼泪汪汪(假定火星人也是两只眼睛），同在他乡为异客：“这一杯一定要干”，不干不解乡愁。 簇内相似度大，簇间相似度小 如果只往大处找共性（如 同胞 、 同星系 ），不足为荣，因为概念太大，而无特色。把一个大集合只聚成一类，最蹩脚的聚类家也会。 能干的聚类家于细微处见功夫，要找某些子集的特色，把大集合中的对象凝聚成若干个特色小簇，使得簇内相似度大，簇间相似度小，那才是万紫千红、信息量丰富的春天。 同 A 聚类 -- 投影到属性 A 上的小小区间 顾名思义， 同 A 即在属性 A 上的值相同或相近；前者投影到 属性 A 上一个点，是 严格的 同 A 聚类 ，后者投影到不太大的区间 ，是 宽松的同 A 聚类 。 巧得很，中华文明早为聚类作了准备。中文中有很多形如 “同某”的词汇，如同学，同乡，同志，同事，同袍，还有数学上的同态，同构，拓扑学中的同坯，等等。 图 1 中，横轴是 籍贯 ，纵轴是 班级 。图中的点代表学生。在横轴投影相近的那些点称为 同乡 ，在纵轴上投影相近的那些称为 同学 ，红圈中的点在双轴上投影都较近，所以是“ 同学 + 同乡 ”。多维的情形稍微复杂，但是思路是同样的。 图 1 同学与同乡 鸡尾酒会上人以群分 。国际学术会议常有鸡尾酒会方式的招待会（ reception ），人们端着酒杯，不断流动，笑声中交流学术，干杯时结识朋友。 聚类之主动 v s 分类之被动 鸡尾酒会上，常看到一群学子围住一个学术带头人；也常看到几位研究者坐在角落，一边品酒，一边在草稿上写写画画，讨论问题;偶尔也有不善交际的离群点（outlier),远离人群，在边沿灯下，“独酌无相亲，...对影成三人”。这里，影响聚群的 不是万有引力或电磁力，也不是强、弱相互作用，而是学术思想的 凝聚力 ，是人格魅力。 鸡尾酒会上没有人指挥谁谁应该到哪里。所遵循的是“物以类聚，人以群分”，聚类对象是主动的。 而在在分类中，对象是被动的，网络上时髦的“被”句型，是分类技术在社会生活中的体现，如菜园子张青“ 被 ”分类到地煞，豹子头林冲“ 被 ”分类到天罡。某人“被捐款”， 某人“被集资”，等等。 主动与 被动 之差别 ，是聚类和分类的最大区别。分类有训练集和测试集，它代表了人们主观意志对分类过程的监督，在机器学习中，分类又称为有监督的机器学习，而聚类称为无监督的学习。 坐标变换与聚类 观察 图 2， 左图是图1内容旋转45 o 的结果。在 XOY 坐标系中，不容易简单表达聚类准则。旋转 45 o 后，在新坐标系 X’OY’ 中，能直接看出 同乡 即 同 X' ， 同学 即 同 Y ’。 图2 （1）坐标旋转 （2）极坐标 令 θ =- 45 o ， 它顺时针旋转，就转回 XOY 平面，中学数学中有坐标变换公式： x'=xcos(-45 o )-ysin(-45 o ) ， y'=xsin(-45 o )+ycos(-45 o ) ； 下面讲 核函数 概念还要用到它，现在暂且 按下不表 。 坐标变换与核函数 聚类可以表现为在簇周围画一条紧边界。 考察图 2 右边的紫色扇面簇，在直角坐标系中的描述稍复杂一些，但在极坐标中却很简单。 坐标变换公式是： f(x,y)=r=x 2 +y 2 ， g(x, y)= θ =ArcSin(y/(x 2 +y 2 ) (1/2) ) 坐标变换后，扇面变成 r, θ 平面上的矩形，例如， { { （ r, θ） |1 ≤ r ≤ 2 , 45 o ≤θ 90 o } 是一个扇面 。 在 XOY 平面，扇面 边界是非线性的，在 r, θ 平面上，边界却是直线段！ 又例如， { （ r, θ） |0 ≤ r ≤ 1 , 0 ≤θ 360 o } 描述了图2（2）中的那个白色的园核。 于是，我们有理由 称 f(x,y) ， g(x, y) 为 核函数 或 类核函数 ， 可以这样来理解名称中的“核”字 ： （ 1 ）如果把图 2 右边看成是染色的青核桃， f(x,y) ≤ 1 所描述的正好是 中间哪个白色的 核 。 （ 2 ） 图 2 左边的坐标变换中类核函数是 f(x,y)=x’= xcos(-45 o )-ysin(-45 o ) , g(x,y)= y’=xsin(-45 o )+ycos(-45 o ) 。 设 a,b 为常数， X’=a, 是一条直线，也是一个 同乡簇 的中心线； Y’=b, 是一条直线 , 是一个 同学簇 的中心线； 点 (X', Y')=(a,b) 是一个点，是 同乡兼同学簇 的中心点； 中心线与中心点都与“核”概念相关，这也提示了选择和设计核函数的思路，设法引入曲线坐标系，综合考虑 坐标曲线簇与对象簇中心线、以及簇的边界的联系，设法联系原点与重要簇的中心，则核函数选择就有线索了。 核函数 (Kernal function) 是个较难懂的概念，在分类的支持向量机 SVM 技术中也要用到。 这里斗胆对核函数做了一个直观解释，有点反传统，未提及在对应的高维空间中的线性可分性，仅供辅助理解，科普不能代替严格的数学定义和证明，如有不妥，请专家指正。 多样化的距离 , 海内存知己，天涯若比邻 设描述人的维度有（ x,y,z,t, 籍贯， 感情，信仰，… .. ）。设人与人的距离为 d ， （1）把 d 定义为在籍贯维上投影的差别，得到的簇是同乡 ; （2）把 d 定义为在信仰维上投影的差别，得到的簇是同志。 （3）把 d 定义为在感情维上投影的差别，得到的簇是朋友。 如果两个人在信仰和感情上的投影一致，哪怕 x,y,z,t 有巨大的时空差别，也心心相印，这就是 “海内存知己，天涯若比邻 ”的数学描述或解释， 天涯 和 比邻 描述的是在不同维度上的距离。 正邪两方都会用科学规律， 二战时，德日意三国的欧式空间距离不小，却聚成了一个反人类集团，是在政治和利益两个维度上的投影相近。 Minkovski- 距离 p 维空间中两点的 Minkovski - 距离 当 q=1 ，结果为各维度上差别之和 ,又称 为 曼哈顿距离 .说的是，城市曼哈顿以方格子路为特色，（似乎济南老城区经纬路那一块也类似），从（x 1 ，y 1 )到 (x 2 , y 2 )，有若干条最短路径，虽然转弯的次数不同，但长度都是|x 1 -x 2 |+|y 1 -y 2 }。 当 q=2 ；是最普通的欧式空间距离。实践中，有时为夸大距离，采用 q=3 ；有时为了缩小差别，可用 q=3/2, 等等。 但是，一旦人们在聚类之初选择了距离类型，或多或少地加入了 主观干预， 极大地干预了最后结果，例如，如上面所述，选择不同的距离定义，似乎开始的差别不大，但可导致结果分别是 同乡 和 同志 ，这两个概念差之千里，同乡不一定是同志，蒋介石的奉化同乡中也有坚定的共产党员。 笔者以为，如果距离的类型也是挖掘出来的，而不是主观指定的，那才真的是“无监督”，或者，从分布熵的角度，避开距离来解决聚类，这方面也许还有许多工作，可供处于选题饥饿的博士生做。 为深入研究的准备 的准备 的准备 聚类 是数据挖掘中难度较大的内容，文献 中，用 70 多页的篇幅，扫描和检阅了相关的成果和方法，也只是一个为深入研究而做的准备；本文只是为哪个准备而做的准备的准备，从远处看看轮廓，讲讲思想 , 尝尝味道，有了这些铺垫，下篇将通过通俗的例子说明一个著名的方法 。 参考文献 Data Mining: Concepts and Techniques, 2nd ed., Jiawei Han and Micheline Kamber, Morgan Kaufmann, 2006. P P383-464. 有中译本，《数据挖掘，概念和技术》第二版，范明，孟小峰 等译， 机械工业出版社出版。 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之 一 2 烤鸭、面饼和甜 面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之 三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲 过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 团拜会和鸡尾酒会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二 其它系列博文的入口 唐常杰博客主页 科学博客主页
个人分类: 科普札记|18224 次阅读|65 个评论
[转载] 一个不错的Spectral Clustering方法的总结
热度 1 hjanime 2011-11-19 09:48
Spectral Clustering 轉自 bbs.sjtu.edu.cn 转自 bbs.sjtu.edu.cn 什么叫 Spectral Algorithm? 广义上来说，任何在演算法中用到 SVD/ 特征值分解的，都叫 Spectral Algorithm 。 从很老很老的 PCA/LDA ，到比较近的 Spectral Embedding/Clustering ，都属于这类。 一篇非常经典的教程 A Tutorial on Spectral Clustering.pdf A_Tutorial_on_Spectral_Clustering.pdf Spectral Clustering ， 中文通常称为 “ 谱聚类 ” 。由于使用的矩阵的细微差别，谱聚类实际上可以说是一 “ 类 ” 算法。 Spectral Clustering 和传统的聚类方法（例如 K-means ）比起来有不少优点： 1 ）和 K-medoids 类似， Spectral Clustering 只需要数据之间的相似度矩阵 就可以了，而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。 2 ）由于抓住了主要矛盾，忽略了次要的东西，因此比传统的聚类算法更加健壮一些，对于不规则的误差数据不是那么敏感，而且 performance 也要好一些。许多实验都证明了这一点。事实上，在各种现代聚类算法的比较中， K-means 通常都是作为 baseline 而存在的。 3 ）计算复杂度比 K-means 要小，特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。 Spectral Clustering 算法的全貌： 1 ）根据数据构造一个 Graph ， Graph 的每一个节点对应一个数据点，将相似的点连接起来，并且边的权重用于表示数据之间的相似度。把这个 Graph 用邻接矩阵的形式表示出来，记为 W 。 2) 把 的每一列元素加起来得到 N 个数，把它们放在对角线上（其他地方都是零），组成一个 N*N 的矩阵，记为 D 。并令 L = D - W 。 3) 求出 L 的前 k 个特征值（在本文中，除非特殊说明，否则 “ 前 k 个 ” 指按照特征值的大小从小到大的顺序）以及对应的特征向量。 4) 把这 k 个特征（列）向量排列在一起组成一个 N*k 的矩阵，将其中每一行看作 k 维空间中的一个向量，并使用 K-means 算法进行聚类。聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的 N 个数据点分别所属的类别。 为什么要用 SVD/ 特征值分解 ? 其实并不是为用而用，而是不得不用。 目前在研究领域碰到的很多基础问题都是 NP-hard 的，找一个比较好的近似演算法要费很大的精力；就算找到多项式的近似方法，也会出现实际使用上仍然太慢 / 解陷入局部极小等问题。 比如说用 K-means 聚类，建模本身已经够简单了，但它是 NP-hard 的，用传统的 EM 迭代作近似解会陷入局部极小。 反之， SVD 理论上只有唯一解，演算法速度相对又快，并且有大量理论结果及周边性质支持，可以算是一个很理想地能将 NP-hard 问题 “ 靠 ” 上去的模型； 它的另一个好处是，作为带约束二次规划的一种特殊情况，它对运算式为二次的目标函数的 “ 相容性 ” 比较好， “ 靠 ” 所要求的数学技巧不高，任何人，任何方向都 能拿来试试。 Spectral Algorithm 的几个方向 : 传统的如 PCA/LDA 用来做线性降维， 2000 年左右的一些 Spectral Embedding 及 Spectral Clustering ，还有周边的一些，如 Low-rank approximation 等等。 为什么先做降维再做 K-means ，效果会更好呢？ 另外，有趣的是 K-means 可以用 PCA 来做近似解。 K-means 是说找到 K 个点，使得所有点到这 K 个点的距离平方和最小； 而 SVD 是说找到一个子空间，使得所有点到这个子空间的距离平方和最小。 于是这两者就建立了联系， K-means 便 relax 到 SVD 上去了。 Spectral Clustering/Embedding: Spectral Clustering 可算是 Spectral Algorithm 的重头戏。 所谓 Clustering ，就是说聚类，把一堆东西（合理地）分成两份或者 K 份。 从数学上来说，聚类的问题就相当于 Graph Partition 的问题，即给定一个图 G = (V, E) ，如何把它的顶点集划分为不相交的子集，使得这种划分最好。 其难点主要有两个： 1. 这个 “ 合理 ” 其实相当难达到，随便设一个目标函数可能达不到希望的结果。 大家可以看了看 Ravi Kannan and Adrian Vetta, On clusterings: good, bad and spectral ，这里详细地讨论了一下准则的选择问题。 2. 即使我们定义了一个相当好的聚类准则，如何优化它又是一个问题。 对于 1 ，在 Spectral Clustering 这一块，各家有各家的想法。 主要有以下几种： a) 大名鼎鼎的 Normalized Cut ，还有一些变种如 Ratio Cut/Minmax cut. b) 和代数图论紧密相联的 Minimum conductance . c) 没有准则，但有证明的演算法 d) 不基于图，而是 reformulate 原来的聚类方法，使之变成 SVD 能解的问题 。 2 则完全被 1 的选取所决定。 Normalized Cut: 在图上，定义什么样的聚类最好，最简单的方法是圈定 K 个不相交顶点集之后，希望顶点集之间的边，其权值的和最小。 ( 边上的权值代表的是两头的顶点邻近的程度，或者说相似度）这就是所谓 MinCut （最小割）问题。 二类分类的最小割不是 NP-hard 的，但是这不能让人感到开心，因为 MinCut 这个准则对于聚类不好。 具体来说， Mincut 完全可能将离大部队过远的单个顶点与其他顶点分开 , 形成两类。 事实上，我们不仅仅要让割边的权和最小，而且要让这 K 个顶点集都差不多大，这样才符合聚类给人的直观感觉。 于是在 MinCut 的基础上，出现了 Normalized Cut. 思路很简单，将 Cut normalize 一下，除以表现顶点集大小的某种量度 ( 如 vol A = 所有 A 中顶点集的度之和 ) 。 也就是 Normalize Cut(A, B) = Cut(A, B) / volA + cut(A, B) / volB 然而这样一改， NP-hard 就来了。 这几乎是所有组合优化问题的恶梦。 怎么办呢？ 把组合优化问题连续化，即所谓减少约束，进行适当的 relax 。 那么为什么会和 SVD 扯上的呢？ 很简单，聚类是东西分成不相交集，也就是有正交的含义在里面；只是分东西必须是 0-1 式的，这种离散化，就是 np-hard 的原因。 我们把正交约束保留，但把离散变成连续的，聚类就变成了寻找（列）正交阵的优化问题，那正是 SVD 的火力所在！ 就这样，通过这种巧妙的 relax ， NP-hard 问题有了近似解。 且不说这近似解的质量如何，这种方法是相当令人振奋的。 （关于 Normalized Cut 近似解的质量 , 似乎没有什么文章能够给出严格的证明，只是实际效果不错就是了。） 值得一提的是， Normalized Cut 还和图上的 Markov chain 有紧密的关系 。 Normalized Cut 这个量度，换成 Markov chain 的语言就是在图上随机游走，子集间相互 “ 串门 ” 的概率大小。 相当有趣。
个人分类: 网络挖掘|17445 次阅读|1 个评论
[转载]K-MEANS聚类算法
bioyulj 2011-9-1 22:03
摘自 http://yunbio.com/1461 k-means是一类常用的clustering (unsupervised) 的算法，它将n个objects (vectors) 分成 k 个clusters. 由于k-means本身是NP-Hard, 所以常规的算法一般都是经验算法。 标准算法(也叫 Lloyd's算法，还有其他)步骤： 在数据集中随机选k （一般默认k=3）个objects作为初始均值(means), 这也是为什么称之为经验算法的原因。 根据每个object和这k个objects的距离（欧几里德）， 将数据空间分成k个clusters 将每个cluster的几何中心(中心，重心) 作为新的均值 重复2到3步，直到达到最优解，clusters不再变化 作为经验算法，它不能保证最后的解是全局最优（global optimum），很多时候都是local的最大值， 这个和最初随机选择的k个均值有关， 所以每次run同样的程序和数据，得到的结果可能不同。 网上有很多实例，建议用 R的kmeans function 实践一下，这个不在base里，需要安装。或者 matlab集成了这个方法 。
个人分类: 算法基础|3971 次阅读|0 个评论
<预测圈>第一问
热度 1 TUGJAYZHAB 2011-5-24 20:27
预测网刚刚开张, 接到了网开第一问: 能否简单解释一下该图 (PCA vs MDSM, angle vs. distance) 在那里简单答复道: 多元系统分类/聚类,要侧重角度, 方向, 而非距离, 量值. 多维空间的角度, 方向, 用两多元向量的夹角余弦值表示. 比如: (1,0)和(0,1)不同, 但和(5,0)相同, 共线. 可推广到多维空间, 多元系统. 由于在那里, 不好修改, 不能存, 回到自己博客, 继续以博文答复: 假如为城市发展定义5个指标: 面积, 人口, 公交总里程, 手机数目, 金融从业人员比例. 在5维指标空间, 一个小城市A的值是: A=(1,2,3,4,5) 而另一个大都市B的数量指标是: B=(10,20,30,40,50) 虽然, 两个城市在规模上有很大差别, 但在组织, 结构, 功能上, 我们可以认为它们在五维指标空间共线, 两者相似 A~B. 计算过程如下: 代表城市A的向量长度: L(A)= 根号 = 根号 = 根号 城市B的向量长度: L(B)= 根号 = 根号 = 根号 城市A的向量在五元指标空间的指向, 余弦值: 余弦值(A)= /根号 =(1^2/根号 + 2^2/根号 + 3^2/根号 + 4^2/根号 + 5^2/根号 ) 城市B的向量在五元指标空间的指向, 余弦值: 余弦值(B)= /根号 =(10^2/根号 + 20^2/根号 + 30^2/根号 + 40^2/根号 + 50^2/根号 ) 从多元向量分析的角度, 把城市作为多元指标空间的多元向量看, 两者在组织,结构,功能上是相等的. 主要参考文献: T. Jay Bai et al. Multi-dimensional sphere model and instantaneous vegetation trend analysis. Ecological Modeling 97(1997)75-86.
个人分类: TIME SERIES|1897 次阅读|1 个评论
k-mean算法综述
热度 2 liqqiao 2010-12-29 10:02
K-MEANS算法: k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个中心对象（引力中心）来进行计算的。 k-means算法的工作过程说明如下： 初始化：聚类数k，初始聚类中心x,迭代次数或者收敛条件。 首先,从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类； 然后,再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）； 再次，不断重复上面的过程直到满足收敛条件或者迭代次数为止. 目标：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开. 各种算法实现： function =cskmeans(x,k,nc) 　　%CSKMEANSK-Meansclustering-generalmethod. 　　% 　　%Thisimplementsthemoregeneralk-meansalgorithm,where 　　%HMEANSisusedtofindtheinitialpartitionandtheneach 　　%observationisexaminedforfurtherimprovementsinminimizing 　　%thewithin-groupsumofsquares. 　　% 　　% =CSKMEANS(X,K,NC)PerformsK-means 　　%clusteringusingthedatagiveninX. 　　% 　　%INPUTS:Xisthenxdmatrixofdata, 　　%whereeachrowindicatesanobservation.Kindicates 　　%thenumberofdesiredclusters.NCisakxdmatrixforthe 　　%initialclustercenters.IfNCisnotspecified,thenthe 　　%centerswillberandomlychosenfromtheobservations. 　　% 　　%OUTPUTS:CIDprovidesasetofnindexesindicatingcluster 　　%membershipforeachpoint.NRisthenumberofobservations 　　%ineachcluster.CENTERSisamatrix,whereeachrow 　　%correspondstoaclustercenter. 　　% 　　%SeealsoCSHMEANS 　　%W.L.andA.R.Martinez,9/15/01 　　%ComputationalStatisticsToolbox 　　warningoff 　　 =size(x); 　　ifnargin3 　　%Thenpicksomeobservationstobetheclustercenters. 　　ind=ceil(n*rand(1,k)); 　　%Wewilladdsomenoisetomakeitinteresting. 　　nc=x(ind,:)+randn(k,d); 　　end 　　%setupstorage 　　%integer1,...,kindicatingclustermembership 　　cid=zeros(1,n); 　　%Makethisdifferenttogettheloopstarted. 　　oldcid=ones(1,n); 　　%Thenumberineachcluster. 　　nr=zeros(1,k); 　　%Setupmaximumnumberofiterations. 　　maxiter=100; 　　iter=1; 　　while~isequal(cid,oldcid)itermaxiter 　　%Implementthehmeansalgorithm 　　%Foreachpoint,findthedistancetoallclustercenters 　　fori=1:n 　　dist=sum((repmat(x(i,:),k,1)-nc).^2,2); 　　 =min(dist);%assignittothisclustercenter 　　cid(i)=ind; 　　end 　　%Findthenewclustercenters 　　fori=1:k 　　%findallpointsinthiscluster 　　ind=find(cid==i); 　　%findthecentroid 　　nc(i,:)=mean(x(ind,:)); 　　%Findthenumberineachcluster; 　　nr(i)=length(ind); 　　end 　　iter=iter+1; 　　end 　　%Nowcheckeachobservationtoseeiftheerrorcanbeminimizedsomemore. 　　%Loopthroughallpoints. 　　maxiter=2; 　　iter=1; 　　move=1; 　　whileitermaxitermove~=0 　　move=0; 　　%Loopthroughallpoints. 　　fori=1:n 　　%findthedistancetoallclustercenters 　　dist=sum((repmat(x(i,:),k,1)-nc).^2,2); 　　r=cid(i);%Thisistheclusteridforx 　　%%nr,nr+1; 　　dadj=nr./(nr+1).*dist';%Alladjusteddistances 　　 =min(dadj);%minimumshouldbetheclusteritbelongsto 　　ifind~=r%ifnot,thenmovex 　　cid(i)=ind; 　　ic=find(cid==ind); 　　nc(ind,:)=mean(x(ic,:)); 　　move=1; 　　end 　　end 　　iter=iter+1; 　　end 　　centers=nc; 　　ifmove==0 　　disp('Nopointsweremovedaftertheinitialclusteringprocedure.') 　　else 　　disp('Somepointsweremovedaftertheinitialclusteringprocedure.') 　　end 　　warningon ---------------------------------------------------------------------------- matlab工具箱使用 首先我们装入数据集：kmeansdata loadkmeansdata; size(X) ans= 5604 数据形式为： 然后调用kmeans();选择k=4,距离采用cityblock（街区块，只能左右上下走，不能走对角），默认情况下是欧氏距离。随机选择初始聚类中心。 idx4=kmeans(X,4,'distance','city'); 返回的是560*1的列向量，表明各行数据所属的类别； 可以通过调用silhouette（）这个函数来观察结果。 =silhouette(X,idx4,'city'); xlabel('SilhouetteValue') ylabel('Cluster') 具体参见matlab说明 ----------------------------------------------------------------------------- C 语言实现 #include stdio.h #include math.h #define TRUE 1 #define FALSE 0 int N;//数据个数 int K;//集合个数 int * CenterIndex;//初始化质心数组的索引 double * Center;//质心集合 double * CenterCopy;//质心集合副本 double * AllData;//数据集合 double ** Cluster;//簇的集合 int * Top;//集合中元素的个数,也会用作栈处理 //随机生成 k 个数 x(0=x=n-1)作为起始的质心集合 void CreateRandomArray(int n, int k,int * center) { int i=0; int j=0; srand( (unsigned)time( NULL ) ); for( i=0;ik;++i)//随机生成 k 个数 { int a=rand()%n; //判重 for(j=0;ji;j++) { if(center ==a)//重复 { break; } } if(j=i)//如果不重复 加入 , { center =a; } else { i--; //如果重复,本次重新随机生成 } } } //返回距离最小的 心的序心 号心 心 质 心 int GetIndex(double value,double * center) { int i=0; int index=i;//最小的质心序号 double min=fabs(value-center );//距质心最小距离 for(i=0;iK;i++) { if(fabs(value-center )min)//如果比当前距离还小,更新最小的质心序号和距离值 { index=i; min=fabs(value-center ); } } return index; } //拷贝质心数组到副本 void CopyCenter() { int i=0; for(i=0;iK;i++) { CenterCopy =Center ; } } //初始化质心,随机生成法 void InitCenter() { int i=0; CreateRandomArray(N,K,CenterIndex);//产生随机的 K 个N 的不同的序列 for(i=0;iK;i++) { Center =AllData ];//将对应数据赋值给质心数组 } CopyCenter();//拷贝到质心副本 } //加入一个数据到一个 Cluster 集合 void AddToCluster(int index,double value) { Cluster ++]=value;//这里同进栈操作 } //重新计算簇集合 void UpdateCluster() { int i=0; int tindex; //将所有的集合清空,即将 TOP 置 0 for(i=0;iK;i++) { Top =0; } for(i=0;iN;i++) { tindex=GetIndex(AllData ,Center);//得到与当前数据最小的质心索引 AddToCluster(tindex,AllData ); //加入到相应的集合中 } } //重新计算质心集合,对每一簇集合中的元素加总求平均即可 void UpdateCenter() { int i=0; int j=0; double sum=0; for(i=0;iK;i++) { sum=0; //计算簇 i 的元素和 for(j=0;jTop ;j++) { sum+=Cluster ; } if(Top 0)//如果该簇元素不为空 { Center =sum/Top ;//求其平均值 } } } //判断 2 数组元素是否相等 int IsEqual(double * center1 ,double * center2) { int i; for(i=0;iK;i++) { if(fabs(center1 !=center2 )) { return FALSE; } } return TRUE; } //打印聚合结果 void Print() { int i,j; printf(-------------------------------------- ); for(i=0;iK;i++) { printf(第%d 组: 质心(%f),i,Center ); for(j=0;jTop ;j++) { printf(%f ,Cluster ); } } } //初始化聚类的各种数据 void InitData() { int i=0; int a; printf(输入数据个数: ); scanf(%d,N); printf(输入簇个数: ); scanf(%d,K); if(KN) { exit(0); } Center=(double *)malloc(sizeof(double)*K);//为质心集合申请空间 CenterIndex=(int *)malloc(sizeof(int)*K);//为质心集合索引申请空间 CenterCopy=(double *)malloc(sizeof(double)*K);//为质心集合副本申请空间 Top=(int *)malloc(sizeof(int)*K); AllData=http://blog.soso.com/qz.q/(double *)malloc(sizeof(double)*N);//为数据集合申请空间 Cluster=(double **)malloc(sizeof(double *)*K);//为簇集合申请空间 //初始化 K 个簇集合 for(i=0;iK;i++) { Cluster =(double *)malloc(sizeof(double)*N); Top =0; } printf(输入%d 数据: ,N); for(i=0;iN;i++) { scanf(%d,(a)); AllData =a; } InitCenter();//初始化质心集合 UpdateCluster();//初始化 K 个簇集合 } /* 算法描述: K 均值算法: 给定类的个数 K,将 N 个对象分到 K 个类中去, 使得类内对象之间的相似性最大,而类之间的相似性最小。 */ main() { int Flag=1;//迭代标志,若为 false,则迭代结束 int i=0; InitData();//初始化数据 while(Flag)//开始迭代 { UpdateCluster();//更新各个聚类 UpdateCenter();//更新质心数组 if(IsEqual(Center,CenterCopy))//如果本次迭代与前次的质心聚合相等,即已收敛,结束退出 { Flag=0; } else//否则将质心副本置为本次迭代得到的的质心集合 { CopyCenter();//将质心副本置为本次迭代得到的的质心集合 } } Print();//输出结果 getchar(); getchar(); }
个人分类: 科研|9289 次阅读|2 个评论
SPSS中的聚类分析
热度 1 xiezilai 2010-9-25 14:45
题外话：聚类理论都比我懂，在这只能做做笔记 1. TwoStep Cluster Analysis 刚接触它时莫名其妙，不明白为什么会有这一项。粗略了解后，感觉其主要特点一是可计算出最佳聚类个数，二是可处理分类变量（Categorical Variables）与连续性变量（Continuous Variables）。计算步骤包括：1）构建聚类特征数（Cluster Features Tree）；2）层次聚类。自动确定最佳聚类个数的方法是Schwarzs Bayesian Criterion（BIC）或Akaikes Information Criterion（AIC）。这俩准则是啥，知道的朋友记得告诉我。 在结果输出的Auto-Clustering表中（以BIC为例），第2列是BIC，其值最小时，一般认为聚类结果最理想；第3列是BIC变化，反映合并前后两种聚类结果的BIC变化情况，绝对值越大，聚类结果越理想；第4列是BIC变化率，同样反映合并前后的变化；第5列是最小距离变化率，一般认为值越大越理想。需要说明的是，虽然有4个统计指标，但不是根据某一个指标来确定聚类个数，而是综合考虑的结果。 2．数据标准化 Hierarchical Cluster 和TwoStep Cluster都能在分析中对数据进行标准化处理，K-Means Cluster则必须事先完成。 3．方差分析表 ANOVA表中的Sig.小于0.05，表明该指标在各类间存在显著性差异。指标的F值越大，表明该指标在聚类分析中越重要。
个人分类: SPSS学习|15154 次阅读|1 个评论
学术报告通知：如何确定给定数据集中的聚簇个数？
timy 2010-5-19 09:04
学术报告通知 题 目：如何确定给定数据集中的聚簇个数？ 报 告 人：徐硕 博士 时 间：2010年5月28日（星期五）上午9：00 地 点：中国科学技术信息研究所三层333教室 （北京复兴路15号，中央电视台西侧） 报告内容： 聚类分析就是将研究对象划分为不同的聚簇，使得每个聚簇中对象间的相似度尽可能高，而不同聚簇中对象间的相似度尽可能低。通过观察二维散点图人们可以很容易指出对应数据集中的聚簇结构，但让计算机从数据集中自动识别潜在的聚簇结构并不是一件容易的事。困难之一在于如何准确估计数据集中包含的聚簇个数，其根本原因在于目前缺乏一个评价聚类结果质量以及比较两种聚类结果的客观方式。 本报告将确定聚簇个数的方法分为三大类：内部度量法、外部度量法以及基于聚类稳定性的方法。除了对每种方法的原理进行介绍之外，还将重点介绍每种方法的优缺点以及各种方法间的关系，并针对一种典型应用场景给出一些指导性建议。 报告人简介： 徐硕，2003年获理学学士学位，2008年中国农业大学农业电气化与自动化专业，研究方向为计算机网络与智能信息处理，主要从事生物数据的数据挖掘工作，获工学博士学位。2008至今，进入我所从事博士后科研工作，合作导师为乔晓东研究员、朱礼军副研究员，研究课题为知识组织系统自动构建与应用关键技术研究。参与或主持的项目包括十一五国家科技支撑计划重点项目子课题、国家863项目、教育部人文社科研究项目、所重点工作项目、江苏省社科基金项目等。近5年来在国内外期刊和会议上发表或录用学术论文20余篇。 欢迎所内外各界人士踊跃参加！
个人分类: 同行交流|5607 次阅读|1 个评论
第三讲 数据中心化，样本聚类(草稿)
TUGJAYZHAB 2010-5-10 13:19
三个月的投资实验做完了，79个变量63天的数据已经有了（ http://www.sciencenet.cn/m/user_content.aspx?id=310937 ，316934，和316935）。下面， 根据第一讲的“基本概念”http://www.sciencenet.cn/m/user_content.aspx?id=274489 和第二讲的“基本运算法则” http://www.sciencenet.cn/m/user_content.aspx?id=276221 ，我们以 79*63 的数据为例，在这里演绎“数据中心化”和“向量聚类”的数据简缩问题，为“趋势分析”“推测”做准备。 现在，这仅是“草稿”，“大纲”，非“超友”非“超迷”不必往下看。待第三讲的讲稿完成后，我会分成几个博文登出来。 这里仅是个幌子，佔个位子，表示并督促我自己，我要开始写第三讲了（免得我去“反打假”，或去讨论“沙尘暴”）。 如何把63支向量归纳成二支向量，两点确定趋势。 如何把63支向量归纳成三支向量，三点确定拐点。 主要内容：向量加法的应用和样方聚类,向量的相似.向量夹角余弦.线性相关. Sample synthesis, vector addition, and Centralization: Identical vegetation and identical m-vectors, m-Vectors in the same line. Different vegetation and Orthogonal vectors. Relation between two samples and angle between the vectors. Cosine values. Related vectors, linear combination of two vectors, of three vectors. Centroid Vectors. M元系统的状态是由它的相对组成决定的，是用M元向量的方向来表示的。 相同向量 维数相同,各对应分量相等的两支向量互为相同向量。 两相同向量相乘，乘积可以用M个正方形表示，面积周长比最大，自己和自己最相似。 如果，向量随时间变化，系统前后状态的乘积倾向于变小（留待以后讨论）。 相同股市。(相关向量), 组成股票相同,各股票对应价格相等的两个股市为相同股市，或同一股市的两个相同状态。 用元,角,分不同单位表示同一股市状态. 同一射线上的点. alpha*A=A, alpha 实数. 不同季节的同一植被(季相),不同取样面积的匀质(Homougeneous)植被. 不同的股市(纽约和深圳)。 互相垂直的向量,内积等于零。A.B=0 不同的植被。没有共有种的两片植被。 向量相似 介乎于垂直,相似之间,相似的向量.维数相同. 股市间的关系与向量间的夹角, A,B。 夹角余弦表示向量的相似(白, 1982)。 余弦值的计算公式(定义式). 定义:COSA,B=A.B/(|A|*|B|) (其中:|A|=向量长度) 一般来说,从植被学来说所有发自原点射线上的点代表相同的植被,A=(0,1,3) 等同于A'=(0,2,6).按以上的分析,A和A'都是草地,而且是具有相同组成的草 地.我们把植被组成作为植被的质的指标,而把植被的量值作为量的指标. 换句话说,我们认为向量的方向代表指被的质,而向量的长度代表植被的量. 同时,我们把上例中A和A'在量值上的差异主要归因于可能的取样面积的差异, 取样季节的差异,丰年歉年的差异,取样手段的差异.并把它们作为植被动态 分析中需要首先滤去的噪音(Noise).因此,MDSM首先要把代表样方的在多维空 间中的点,除以它们的量值,向量长度.比较形象的说法是:把多维空间中的点 投影到多维超球面上.这便是超球面模型MultiDimensional Sphere Model MDSM的名字的由来.然后,在此基础上再进一步,根据投影在超球面上的分布, 来划分植被类型,并用形心向量来代表植被.并通过观察,分析植被在超球面 上投影的运动 来监测植被. 练习:计算 A,B=, B,C= A,C=0999757847, ARC=0.5 A,-A, B,-B, C,-C, =1, ARC= 归并样方 平行四边形的角平分线. 平均值组成中心向量(Centroid vector)。 练习:求向量A+B+C, (A+B+C)/3, 计算: A, 2B, A,B, A+B+C, (A+B+C)/3 2A=A. 在alpha*A+beta*B中, alpha, beta (权)不改变加向量的方向角,但却改变 了和向量(对角线)的方向. 线性组合=平面 讨论: 命题:A B两向量的所有线性组合,alph*A+betaB充满AB所确定的平面(二维空间). AB平面上的向量,必定是A和B的线性组合;而A和B的线性组合必定在平 面AOB上. 图2 alpha.A+beta.B: A,B,-B,-A向量,alpha,beta 标量.角平分线改变方向: beta=0, 角平分线=OA; alpha=0, 角平分线=OB. 所有的组合充满AB所确定的平面(二维空间): 两向量所组成的4扇面, A+B,AOB. 对顶角-A-B, 补角:A-B, 或B-A. 数据 取自时间k的N个样本(M个股票的股市)在时间K的状态用形心向量来表示。 Y(i,k)=Sigma , j=1,2,..n。 从多维空间(沿中心向量)向球心看,众样本围绕,拱卫着中心向量.中心向量是 代表. 任一样本都偏离形心. 中心化最大限度地滤去了来自随机样本的噪音,干扰。 实现滤波.复合样本(Compound Sample, Gauch, 1982)加强信号,减低噪音. Y(i,k),多变量时间系列问题(M-Time series),或时间动态(temporal dynamics). 根据向量的旋转,来表示,监测系统的变化,动态. 在本书所涉及的领域:股市,植被,我们用指数增长来描述,而把线性作为指数 增长的特例. 在增率接近于一时,时间段比较短时,几何增长接近于代数增长: 几何数列:1, 1.1, 1.21,.. (增率=10%) 代数数列:1, 1.1, 1.2,... (增幅=0.1) Y(i,j),多变量空间分布(Spatial dynamics)问题. 根据向量的旋转,来表示,监测系统空间动态. 空间分布,一般用线性模型来描述. MDSM所用的数据是双向数据,双下标变量,但我们不作为矩阵来处理. 不是一个整体,而是K个向量,时间系列 或J个向量,空间系列.研究时间空间的动态. 对于79*63的数据,要归纳/缩减成79*2的数据,才显示趋势,两点确定直线. 把79*63的数据,归纳/缩减成79*3的数据,才显示拐点,三点确定拐点. 如何把63支向量归纳成二支向量. 如何把63支向量归纳成三支向量. 有待展开,有待深入.待修改，待续。
个人分类: 第三讲|3756 次阅读|0 个评论
时间序列数据挖掘
郭崇慧 2010-1-14 13:14
时间序列是一种重要的高维数据类型，它是由客观对象的某个物理量在不同时间点的采样值按照时间先后次序排列而组成的序列，在经济管理以及工程领域具有广泛应用。例如证券市场中股票的交易价格与交易量、外汇市场上的汇率、期货和黄金的交易价格以及各种类型的指数等，这些数据都形成一个持续不断的时间序列。利用时间序列数据挖掘，可以获得数据中蕴含的与时间相关的有用信息，实现知识的提取 。时间序列数据本身所具备的高维性、复杂性、动态性、高噪声特性以及容易达到大规模的特性，因此时间序列挖掘是数据挖掘研究中最具有挑战性的十大研究方向之一 。目前重点的研究内容包括时间序列的模式表示、时间序列的相似性度量和查询、时间序列的聚类、时间序列的异常检测、时间序列的分类、时间序列的预测等。 由于时间序列数据本身所具备的高维性、复杂性、动态性、高噪声特性以及容易达到大规模的特性，直接在时间序列上进行数据挖掘不但在储存和计算上要花费高昂代价而且可能会影响算法的准确性和可靠性。时间序列的模式表示是一种对时间序列进行抽象和概括的特征表示方法，是在更高层次上对时间序列的重新描述 。时间序列的模式表示具有压缩数据、保持时间序列基本形态的功能，并且具有一定的除噪能力。常用的时间序列模式表示方法主要包含：频域表示法、分段线性表示法、符号表示法以及主成分分析表示法等。频域表示的基本思想是将时间序列从时域通过傅里叶变换或小波变换映射到频域，用很少的低频系数来代表原来的时间序列数据，这种方法虽然数据浓缩的效率很高，但是对噪声敏感，而且不直观。分段线性表示法的基本思想是用 K个直线段来近似代替原来的时间序列，这种方法能够实现数据压缩的目的，而且允许在时间轴上进行缩放，但实现过程较复杂，且要求事先给出直线段数K。K值的选择是一个关键因素，太小则丢失有用信息，太大又会产生过多的冗余信息。时间序列的符号化表示就是通过一些离散化方法将时间序列的连续实数值或者一段时间内的时间序列波形映射到有限的符号表上，将时间序列转换为有限符号的有序集合。符号化表示的优点在于可以利用许多字符串研究领域的成果，缺点在于如何选择合适的离散化算法，解释符号的意义，以及定义符号之间的相似性度量。主成分分析是一种常见的降维方法。在时间序列的模式表示中，通过对整个时间序列数据库的整体表示实现对整个时间序列数据库的特征提取和压缩。其优点在于计算精度高且对噪声数据的鲁棒性强，但由于在奇异值分解过程中涉及到特征值计算，计算开销较大。 时间序列的相似性度量是时间序列数据挖掘的基础 。时间序列由于其特定的形状特征, 使得目前常用的一些相似性度量和聚类方法失去了原有的优越性, 而几乎所有的时间序列挖掘算法都涉及到计算序列之间的相似性问题。目前，时间序列的相似性度量主要采用Lp范数（例如欧几里德距离）、动态时间弯曲距离、最长公共子序列、编辑距离、串匹配等。前两种相似性度量方法应用较为广泛。但是欧几里德距离不支持时间序列的线性漂移和时间弯曲，动态时间弯曲距离的计算量很大，不适合直接应用于海量时间序列的挖掘，从而限制了其在时间序列数据挖掘上的广泛应用。 虽然各种聚类方法已经在数据挖掘领域中得到了较为深入的研究，但这些方法大多是针对关系数据库中的静态数据对象而提出的。然而在现实世界中越来越多的应用涉及到流数据和时间序列数据等随时间变化的复杂动态数据对象的聚类分析。由于时间序列数据与静态数据有着极大的不同，故对其进行聚类分析有着很大的复杂性。近年来，涌现出许多时间序列聚类方法 ，这些时间序列数据聚类方法大体上可以分为三种，即基于原始数据的聚类、基于特征的聚类和基于模型的聚类。其中后两种方法的核心思想是利用时间序列的模式表示方法把时间序列数据转化为静态的特征数据或者是模型参数，然后再直接应用静态数据的聚类方法来完成聚类任务。 在对时间序列进行分析时, 经常希望能够发现这些时间序列在不同时间段的形态有何关联关系。这种关联关系一般表现为时间序列中频繁出现的变化模式和极少出现的变化模式。这种极少出现的变化模式称之为异常模式。在某些领域, 异常模式的发现对人们来说往往更有价值。例如, 医院可以从病人的心电图序列中发现异常模式从而进行诊断和治疗。按照异常的表现形式不同, 线性时间和空间上时间序列的异常主要可以分为点异常和模式异常两种, 它们都是用于发现一条时间序列上的异常情况的。模式异常是指在一条时间序列上与其他模式之间具有显著差异的模式。事实上, 点异常也可以认为是长度为1 的模式异常。目前已经提出多种时间序列异常检测方法，例如基于人工免疫系统的时间序列异常检测 、基于支持向量聚类的时间序列异常检测 以及后缀树和马尔可夫模型的时间序列异常检测 。 时间序列分类是时间序列数据分析中的重要任务之一. 不同于时间序列分析中常用的算法与问题，时间序列分类是要把整个时间序列当作输入，其目的是要赋予这个序列某个离散标记。它比一般分类问题困难，主要在于要分类的时间序列数据不等长，这使得一般的分类算法不能直接应用。即使是等长的时间序列，由于不同序列在相同位置的数值一般不可直接比较，一般的分类算法依然还是不适合直接应用。为了解决这些难点,通常有两种方法：第一，定义合适的距离度量（最常用的距离度量是DTW距离），使得在此度量意义下相近的序列有相同的分类标签，这类方法属于领域无关的方法；第二，首先对时间序列建模（利用序列中前后数据的依赖关系建立模型），再用模型参数组成等长向量来表示每条序列，最后用一般的分类算法进行训练和分类，这类方法属于领域相关的方法。文 分析了两类方法，并且分别在不同的合成数据集和实际数据集上比较了领域无关和领域相关的两类方法。结果发现在训练数据较少时，使用领域相关的算法比较合适；另一方面，领域无关的算法受噪声的影响相对较少。 预测是对尚未发生或目前还不明确的事物进行预先的估计和推测，是在现时对事物将要发生的结果进行探讨和研究，简单地说就是指从已知事件测定未知事件。进行预测的总原则是：认识事物的发展变化规律，利用规律的必然性进行科学预测。时间序列预测主要包括三种基本方法：内生时间序列预测技术；外生时间序列预测技术；主观时间序列预测技术。时间序列分析与预测在经济 、金融 、工程 等领域有着广泛的应用，研究成果也最为丰富，将另文讨论。 参考文献 1. Keogh E, Kasetty S. On the need for time series data mining benchmarks: a survey and empirical demonstration .Data Mining and Knowledge Discovery, 2003, 7(4): 349-371. 2. Yang Qiang, Wu Xindong. 10 challenging problems in data mining research. Interna tional Journal of Information Technology Decision Making, 2006, 5(4): 597-604. 3. Lin J, Keogh E, Lonardi S, Chiu B. A symbolic representation of time series, with implications for streaming algorithms. Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, 2003, Pages: 2 11. 4. Gullo F, Ponti G, Tagarelli A, Greco S. A time series representation model for accurate and fast similarity detection, Pattern Recognition, 2009, 42(11): 2998-3014. 5. Gunopulos D, Das G. Time series similarity measures. KDD00: Tutorial notes of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, 2000. 6. Literatures on Similarity-based Time Series Retrieval. http://www.cs.ust.hk/~leichen/readings/literaturesovertimeseries.htm 7. Liao T W. Clustering of time series data: a survey. Pattern Recognition, 2005, 38: 1857-1874 8. Dasgupta D, Forrest S. Novelty detection in time series data using ideas from immunology. In: Proceeding of the 5th International Conference on Intelligent Systems. 1996, Pages: 82- 87. 9. Ma J, Perkins S. Time-series Novelty Detection Using One-class Support Vector Machines. Procedding of International Joint Conference on Neural Networks, 2003. 10. Keogh E, Lonardi S. Finding surprising patterns in a time series database in linear time and space. Proceedings of the eighth ACM SIGKDD, 2002. 11. 杨一鸣， 潘嵘， 潘嘉林， 杨强， 李磊 . 时间序列分类问题的算法比较 . 计算机学报， 2007 ， 30 （ 8 ）： 1259-1265. 12. Clements M P （柯莱蒙兹）， Hendry D F （韩德瑞），陆懋祖 . 预测经济时间序列 . 北京大学出版社， 2008 13. Tsay R S （蔡瑞胸），潘家柱译 . 金融时间序列分析 . 机械工业出版社， 2006 14. 杨叔子．时间序列分析的工程应用（上下册）．第二版．华中科技大学出版社， 2007
个人分类: 科研笔记|30883 次阅读|4 个评论
蚁群聚类算法中确定相邻对象方法的改进
hldcyx 2009-8-31 05:57
1 前言 数据挖掘是一个多学科交叉的研究领域，涉及许多学科。聚类是数据挖掘的重要任务之一，目前主要的聚类算法可以划分为如下几类 ：划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法等。这些方法大多数需要一些参数限制，设定聚类的数目，而且聚类结果对初始状态及参数非常敏感。 近年来，一些学者应用群体智能 (Swarm Intelligence) 的思想研究聚类问题。因为群体智能源于对简单个体组成的群落社会系统的模拟，如蚁群、蜂群，在没有任何先验知识和无统一指挥的分布环境下，它们具有自我组织、合作、通信等特点。 Deneubourg 等首次模拟幼蚁自动分类 ( 即较小的幼虫在中心，较大的幼虫在外围 ) 及蚁尸聚积现象，提出了聚类基本模型。随后 Lumer 和 Faieta 在文献 中改进了 Deneubourg 的基本模型，提出了 LF 算法并应用于数据分析中。蚁群算法是一种新型的模拟进化算法，其在数据挖掘中的应用正逐步引起人们的关注 。但由于蚁群算法的研究历史很短，在实际问题中应用还较少，因此存在许多有待进一步研究改进的地方，如需要设置的参数太多、参数的设置还有一定难度、算法本身不能保证聚类纯度等。 本文在 LF 等基本模型的基础上引入相邻对象方向角和方向屏蔽角，对确定相邻对象的方法进行改进，并以矿山实际测量数据为数据源，对改进后的方法进行检验。 2 基本蚁群聚类算法的相邻对象的选取方法 蚁群聚类主要思想是 ：先将所有多维属性空间中的数据对象随机地投影到二维网格平面上，然后每只蚂蚁在二维平面上随机选择一个数据对象，随即蚂蚁计算该数据对象与邻域半径内其他数据对象之间在属性空间中的相似性。如果不相似，蚂蚁将数据对象拾起并随机移往别处，再计算与邻域半径内对象的相似性，直到移往与周围对象相似的地方被放下，并随机选择下一个数据对象；如果相似，蚂蚁将不会拾起该数据对象，而随机选择下一个数据对象。这样，数据对象通过被蚂蚁的不断拾起、移动与放下而被聚类。或者说，相似的对象被蚂蚁搬运集中到一起。简单说来，其思想就是不相似的搬走，相似的放下。 从蚁群聚类的主要思想可知，相似对象能否聚在一起，是由邻域内对象的相似性大小决定的。以 常用的 LF 算法为例，分析邻域内相邻对象的选取方法。在 LF 算法中，数据对象的相似度 f ( o i ) 由公式 (1) 确定，设蚂蚁在时刻 t 于位置 r 发现对象 o i ，则 o i 在 r 处与其邻域内对象 o j 的平均相似度定义为 ： (1) 其中， s 为邻域的边长， Neigh s s ( r ) 表示位置 r 周围面积为 s s 的正方形邻域。 d ( o i , o j ) 表示对象 o i 与对象 o j 在属性空间中的距离，常用欧氏 (Euclidean) 距离、余弦距离公式计算 ( 也可采用其它距离公式 ) 。 s 作为邻域的边长， 它给出了相似的邻域范围。相邻对象的选取方法就是将邻域范围内的所有对象作为相邻对象。这样的选取方法缺点在于所有的相邻对象都具有同样的重要性，没有体现不同方向的相邻对象在相似度计算中的不同影响。如图 1 所示， o i 为当前对象， s 为邻域边长，根据 LF 算法中相邻对象的选取方法，共八个相邻对象，其中 A 1 、 A 2 、 A 3 和 A 4 为第一类对象， B 1 、 B 2 、 B 3 和 B 4 为第二类对象。如果当前对象 o i 是第一类点，可能因为受第二类的四个点的影响，使得 f ( o i ) 很小，蚂蚁不能在此放下 o i ；另一方面， 如果当前对象 o i 是第二类点，可能因为受第二类的四个点的影响，使得 f ( o i ) 很大，导致蚂蚁在此放下 o i 。 3 相邻对象确定方法的改进 常用的相邻对象的确定方法由于没有考虑相邻对象之间方向关系，可能造成聚类速度缓慢甚至算法不收敛。在引入改进方法之前，先对几个概念进行定义。 相邻对象的方向角： o i 为当前对象， o j 和 o k 分别为 o i 的两个相邻对象，在二维网格平面上， o i 分别与 o j 、 o k 连线，两条连线之间形成的锐角叫做相邻对象 o j 和 o k 的方向角。如图 1 所示， 角就是 o i 的相邻对象 A 2 和 A 3 的方向角。 方向屏蔽角：是一个事先输入的角度常数，作用是与相邻对象的方向角进行比较，判断是否有相邻对象可以屏蔽，不参与相似度的计算。 新方法的基本过程描述如下： 第 1 步 初始化方向屏蔽角 ； 第 2 步 得到邻域范围内所有相邻对象 N j ( j =1,2, , k ) ，并计算当前对象到所有相邻对象在二维网格平面上的距离 D j ( j =1,2, , k ) 和所有相邻对象相互之间的方向角 nm ( n =1,2, , k , m =1,2, , k , n m ) ； 第 3 步 得到离当前对象最近的相邻对象 N i ，如果 im ( m =1,2, , k , i m ) ，将 N m 从相邻对象集中去掉； 第 4 步 按照 D j ( j =1,2, , k ) 从小到大依次对相邻对象进行检验，对相邻对象方向角小于屏蔽角的相邻对象进行屏蔽，最终得到屏蔽后的相邻对象集。 以图 1 所示的数据对象为例，当前对象为 o i ， 设方向屏蔽角为 10 ，用新方法最终得到相邻对象集为 { A 1 , A 2 , A 3 , A 4 } ， B 1 、 B 2 、 B 3 和 B 4 分别被 A 1 、 A 2 、 A 3 和 A 4 屏蔽掉了。 4 应用实例及结果分析 露天矿采场由于测量验收工作的需要，基本上每月都要对有采动的台阶位置进行测量，产生大量的测量数据，用手工对不同位置的数据进行分类是一件十分繁重的工作，采用数据聚类的方法不仅可以实现数据的自动聚类，又有利于台阶的自动生成。选用的实例数据是内蒙古某露天矿的台阶测量数据，如图 2 所示， 图中标有数字 1 、 2 、 3 和 4 附近的点为各台阶平盘的测量点。下面分别使用 LF 算法和改进后的算法对这些数据进行聚类。 LF 算法的参数设定为： k 1 =0.1 ， k 2 =0.15 ，相似系数 a= 250 ，邻域边长 s= 2 ，迭代次数 N =100000 ；改进后的算法除了增加屏蔽角 =10 外，其它参数以 LF 算法相同。图 3 是 LF 算法聚类结果的二维网格平面投影显示，图 4 是改进算法的聚类结果的二维网格平面投影显示，不同的类用不同形成的点表示，对这两个图的比较可以看出，两种算法都实现了对测量数据的精确聚类，但从聚类结果的形态分布看，改进算法的聚类结果形态分布优于 LF 算法的聚类结果。图 5 所示的两条曲线分别是 LF 算法和改进算法的相似度变化曲线，从图中可以看出，改进算法在迭代 20000 次附近就达到了稳定，而 LF 算法是在迭代 80000 次后才达到稳定，说明改进算法比 LF 算法聚类速度明显加快了。图 6 所示为聚类结果的空间实际位置。 5 结论 在基本模型的基础上，对蚁群聚类算法中相邻对象的确定方法做了一些改进。通过定义相邻对象的方向角和方向屏蔽角，实现确定相邻对象是否最终被选取。使用相同的实例数据和相同的参数，分别用 LF 算法和改进后的算法进行聚类，对聚类结果和相似度变化曲线进行分析比较，结果表明，改进后蚁群聚类算法有更优的聚类形态和更快的聚类速度，达到了预期的目的。 图 3 LF 算法的聚类结果 图 4 改进后算法的聚类结果 图 5 两种算法的相似度变化曲线 图 6 聚类结果的实际位置 图 1 相邻对象选取方法示意图 图 2 实例数据点位置分布
个人分类: 未分类|4591 次阅读|0 个评论
核聚类与支持向量聚类
热度 1 郭崇慧 2009-8-30 15:44
聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术 。作为一种常见的数据分析工具和无监督机器学习方法，聚类的目的是把数据集合分成若干类（或簇），使得每个类中的数据之间最大限度地相似，而不同类中的数据最大程度地不同。根据聚类算法所采用的基本思想，大致可以将它们分为五种 ，即划分聚类、层次聚类、基于密度的聚类、基于网格的聚类和基于模型的聚类。目前对聚类算法的研究正在不断深入，其中核聚类算法和谱聚类算法是近年来受到广泛关注的两种算法 。 核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高维特征空间中，并选取合适的 Mercer 核函数代替非线性映射的内积，在特征空间中进行聚类。该方法是普适的，它比经典的聚类方法有较大的改进。它通过非线性映射增加了数据点线性可分的概率，即能较好地分辨、提取并放大有用的特征，从而实现更为准确的聚类，算法收敛速度也较快。在经典聚类算法失效的情况下，核聚类算法常常能得到较好的聚类 结果 。 支持向量聚类（ Support Vector Clustering, SVC ）属于核聚类的一种，它以支持向量机（ Support Vector Machine, SVM ）为工具进行聚类 。它是 Ben-Hur 等在基于高斯核的 SVDD （ Support Vector Domain Description ）算法基础上进一步发展起来的无监督非参数型的聚类算法 。它的基本思想是：利用高斯核，将数据空间中的数据点映射到一个高维的特征空间中。再在特征空间中寻找一个能包围所有数据点象的半径最小的球，将这个球映回到数据空间，则得到了包含所有数据点的等值线集。这些等值线就是簇的边界。每一条闭合等值线包围的点属于同一个簇 。 SVC 算法主要分为两个阶段： SVC 训练阶段和聚类分配阶段。其中 SVC 训练阶段包括高斯核宽度系数的确定、核矩阵的计算、 Lagrange 乘子的计算、支持向量的选取和高维特征空间中特征球半径的计算。聚类分配阶段首先生成邻接矩阵，然后根据邻接矩阵进行聚类分配 。 SVC 算法具有两大显著优势：能产生任意形状的簇边界；能分析噪声数据点且能分离相互交叠的簇。这是许多聚类算法无法做到的。但 SVC 算法仍存在两个瓶颈： Lagrange 乘子的计算和邻接矩阵的计算。相对而言，后者需要消耗的计算时间远比前者多 。因此很多新的 SVC 算法都旨在提高邻接矩阵的计算效率 。 参考文献 Xu R, Wunsch D. Survey of Clustering Algorithms. IEEE Transaction on Neural Networks, 2005, 16(3): 645-678. Han J, Kamber M. Data Mining: Concepts and Techniques, Second Edition. Morgan Kaufmann, San Francisco , 2006. Filippone M, Camastra F, Masulli F, Rovetta S. A Survey of Kernel and Spectral Methods for Clustering. Pattern Recognition, 2008, 41(1): 176-190. 张莉，周伟达，焦李成 . 核聚类算法 . 计算机学报 , 2002, 25(6): 587-590. Burges C J C. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 1998, 2(2) : 121-167. Tax D M J, Duin R P W. Support Vector Domain Description. Pattern Recognition Letters, 1999, 20(11-13): 1191-1199. Ben-Hur A, Horn D, Siegelmann H T, Vapnik V. Support Vector Clustering. Journal of Machine Learning Research, 2001, 2(12): 125-137. Scholkopf B, Williamson R, Smola A, Shawe-Taylor J, Platt J. Support Vector Method for Novelty Detection. Advances in Neural Information Processing System 12. 2000: 582-588. 吕常魁，姜澄宇，王宁生 . 一种支持向量聚类的快速算法 . 华南理工大学学报 . 2005, 33(1): 6-9. Lee J, Lee D. An Improved Cluster Labeling Method for Support Vector Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(3): 461-464. Camastra F, Verri A. A Novel Kernel Method for Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005, 27(5):801-805.
个人分类: 科研笔记|15600 次阅读|12 个评论
复杂网络社区结构划分方法
热度 1 郭崇慧 2009-4-30 08:38
随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个社区或组构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏 。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站 ；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元 。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。 在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法 、谱平分法 、随机游走算法 和派系过滤算法 等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法 和基于边介数度量的分裂算法 等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法 、基于信息论的算法 、基于PCA的算法 和最大化模块度 的算法 等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法 ，且Bo Yang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC) 。 尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。 关于复杂网络社区发现问题更加系统深入的最新进展情况请看2009长篇综述文章 Community Detection in graphs by Santo Fortunato (arXiv:0906.0612) 参考文献 Girvan M, Newman M E J. Community structure in social and biological networks . PNAS, 2001, 99(12): 7821-7826. Newman M E J. Fast algorithm for detecting community structure in networks . Physical Review E, 2004, 69(6): 066133. Fell D A, Wagner A. The small world of metabolism . Nature(Biotechnology, 2000, (18): 1121-1122. Pool l, Kochen M. Contacts and Influence . Social Networks, 1978, (1): 1-48. Milgram S. The small world problem . Psychology Today, 1967, (2): 60-67. Kernighan B W, Lin S. An efficient heuristic procedure for portioning graphs . Bell System Technical Journal, 1970, 49: 291-307. Fiedler M. Algebraic connectivity of graphs . Czechoslovak Mathematical Journal, 1973, 23(98): 298-305. Pothen A, Simon H, Liou K P. Partitioning sparse matrices with eigenvectors of graphs . SIAM Journal on Matrix Analysis and Applications. 1990, 11(3): 430-452. P. Pons and M. Latapy. Computing Communities in Large Networks Using Random Walks . Computer and Information Sciences. 2005,284-293. G. Palla, I. Derenyi, I. Farkas et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society . Nature,2005 435(7043): 814-818. G. Palla, I. Farkas, P. Pollner, I. Derenyi et al. Directed network modules . Phys. New. J, 2007,186. Tyler J, Wilkinson D, Huberman B. Email as spectroscopy: Automated discovery of community structure within organizations . International Conference on Communities and Technologies, 2003, 81-96. F. Radicchi, C. Castellano, F. Cecconi et al. Defining and identifying communities in networks . Eur. Phys. J. B, 2004, 101: 2658-2663. Wu F, Huberman B A. Find communities in linear time: A physics approach . Euro. Phys. J B, 2003, 38: 331-338. Rosvall M, Bergstrom C T. An information-theoretic framework for resolving community structure in complex networks . PNAS, 2007, 104(18): 7327-7331. Chonghui Guo, Liang Zhang. An Analysis Method Based on PCA for the Community Structure in Complex Networks . Operations Research and Management Science, 2008, 17(6), 144-149. Newman M E J, Girvan M. Finding and evaluating community structure in networks . Physical Review E, 2004, 69 (2): 026113. Clauset A, Newman M E J, Moore C. Finding community structure in very large networks . Phys. Rev. E, 2004,70: 066111. Duch J, Arenas A. Community detection in complex networks using extreme optimization . Physical Review E,2005,72: 027104. R. Guimer and L. A. N. Amaral, Functional cartography of complex metabolic networks . Nature, 2005, 433: 895-900. A. Medus, G. Acua, and C. O. Dorso. Detection of community structures in networks via global optimization . Physica A, 2005, 358: 593-604. J. Reichardt and S. Bornholdt. Statistical Mechanics of Community Detection . Phys. Rev. E, 2006, 74: 016110. Newman M E J. Finding community structure in networks using the eigenvectors of matrices . Physical Review E, 2006, 74(3): 036104. P. Doreian and A. Mrvar. A Partitioning Approach to Structural Balance . Social Networks, 1996, 18(2): 149-168. Bo Yang, William K. Cheung, and Jiming Liu. Community Mining from Signed Social Networks . IEEE Transactions on Knowledge and Data Engineering. 2007, 19(10): 1333-1348.
个人分类: 科研笔记|17140 次阅读|6 个评论
聚类分析（Clustering Analysis）
热度 2 郭崇慧 2009-3-4 16:25
（博文后面的参考文献 是聚类分析方面非常好的三篇综述） 聚类作为数据挖掘与统计分析的一个重要的研究领域，近年来倍受关注。从机器学习的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。聚类方法作为一类非常重要的数据挖掘技术，其主要是依据样本间相似性的度量标准将数据集自动分成几个群组，且使同一个群组内的样本之间相似度尽量高，而属于不同群组的样本之间相似度尽量低的一种方法。聚类中的组不是预先定义的，而是根据实际数据的特征按照数据之间的相似性来定义的，聚类中的组也称为簇。一个聚类分析系统的输入是一组样本和一个度量样本间相似度（或距离）的标准，而输出则是簇集，即数据集的几个类，这些类构成一个分区或者分区结构。聚类分析的一个附加的结果是对每个类的综合描述，这种结果对于更进一步深入分析数据集的特性是尤其重要的。聚类方法尤其适合用来讨论样本间的相互关联从而对一个样本结构做一个初步的评价。数据挖掘中的聚类研究主要集中在针对海量数据的有效和实用的聚类方法上，聚类方法的可伸缩性、高维聚类分析、分类属性数据聚类、具有混合属性数据的聚类和非距离模糊聚类等问题是目前数据挖掘研究人员最为感兴趣的。 聚类已经被广泛应用于许多领域，例如生物学、药学、人类学、市场营销和经济学。聚类应用包括动植物分类、疾病分类、图像处理、模式识别和文本检索。例如，在商业方面，聚类分析可以帮助市场人员发现顾客群中所存在的不同特征的群组，并可以利用购买模式来描述这些具有不同特征的顾客组群。在生物学方面，聚类分析可以用来获取动物或植物所存在的层次结构，可根据基因功能对其进行分类以获得对人群中所固有的结构更深入的了解。聚类还可以从地球观测数据库中帮助识别具有相似的土地使用情况的区域，此外，还可以帮助分类识别互联网上的文档以便进行信息发现。 聚类分析是一个富有挑战性的研究领域，以下就是对数据挖掘中聚类分析的一些典型要求： (1) 可伸缩性(scalability)。实际应用要求聚类算法能够处理大数据集，且时间复杂度不能太高(最好是多项式时间)，消耗的内存空间也有限。目前，为了将算法拓展到超大数据库(VLDB)领域，研究人员已经进行了许多有益的尝试，包括：增量式挖掘、可靠的采样、数据挤压(data squashing)等。其中，数据挤压技术首先通过扫描数据来获得数据的统计信息，然后在这些统计信息的基础上进行聚类分析。比如BIRCH 算法中使用CF树就是属于数据挤压技术。 (2) 能够处理不同类型的属性。现实中的数据对象己远远超出关系型数据的范畴，比如空间数据、多媒体数据、遗传学数据、时间序列数据、文本数据、万维网上的数据、以及目前逐渐兴起的数据流。这些数据对象的属性类型往往是由多种数据类型综合而成的。 (3) 能够发现任意形状的簇。 (4) 尽量减少用于决定输入参数的领域知识。 (5) 能够处理噪声数据及孤立点。 (6) 对输入数据记录的顺序不敏感。 (7) 高维性(high-dimensional)。一个数据集可能包含若干维。较高的维数给聚类分析带来两个问题：首先，不相关的属性削弱了数据汇聚的趋势，使得数据分布非常稀疏。尽管这种情况在低维空间中并不多见，但是随着维数的增加，不相关属性的出现概率及数量也会增加，最后导致数据空间中几乎不存在簇。其次，高维使得在低维中很有效的区分数据的标准在高维空间中失效了。如在高维空间中，数据点到最近邻点的距离与到其他点的距离没有多少分别，从而导致最近邻查询在高维空间中不稳定，此时若根据接近度来划分簇，结果是不可信的。 (8) 能够根据用户指定的约束条件进行聚类。 (9) 聚类结果具有可解释性和可用性。 上述的要求使目前聚类分析研究的热点集中在设计能够有效、高效地对大数据库进行聚类分析的方法上。相关的研究课题包括：聚类方法的可扩展性、复杂形状和复杂数据类型的聚类分析及其有效高效性、高维聚类技术，以及混合数值属性与符号属性数据库中的聚类分析方法等。 参考文献： 1. Jain A K, Murty M N, Flynn P J. Data Clustering: A Review. ACM Computing Surveys, 1999, 31(3): 264-323. 2. Xu Rui, Donald Wunsch Ⅱ, Survey of Clustering Algorithms, IEEE Transactions on Neural Networks, 2005, 16(3): 645-678. 3. Omran M G H, Engelbrecht A P, Salman A. An overview of clustering methods. Intelligent Data Analysis, 2007, 11, 583-605
个人分类: 科研笔记|15651 次阅读|9 个评论
更多...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-6-4 07:38

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部