Categories

Calendar

February 2009
M T W T F S S
« Jan   Mar »
 1
2345678
9101112131415
16171819202122
232425262728  

漫谈 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 要小,特别是在像文本数据或者平凡的图像数据这样维度非常高的数据上运行的时候。

(\d+|\d*\.\d+)

我在之前的 blog 上专门有一个分类叫做 Bug Archive ,用于记录自己平时碰到的应该记录下来的 bug ,现在我觉得这个分类大概还得继续下去吧。因为记录的目的是希望自己以后不要再犯同样的错误,所以通常实际记录下来的其实也都是非常低级的 bug 了。毕竟复杂的 bug 一方面本身也比较难重现,再者遇到了也不是很羞愧的事情。

但是低级的 bug 就不一样了,低级的 bug 并不是指它本身很低级,而是对于你来说不应该会犯的错误——比如,在你最熟悉的地方出现问题。就像今天要说的这个 bug 一样。我想,如果你熟悉正则表达式,大概在打开本文之前就看出来标题里的正则表达式有问题了;如果一开始没有看出来,现在我告诉你它有问题,你再去看一眼,应该也知道问题的所在了。当然,如果你对正则表达式不熟悉,那也只能说这个问题对你来说不是低级的 bug 。

灵峰探梅

今天可以说是正式寒假的最后一天,明天就正式开始上课了,正好有不少俱乐部 staff 都已经回校了,于是大家组织起来去了趟“灵峰探梅”。逃票路线正是两年前 cc98 Linux 天地版版聚时走的那条路吧。挺累的,我还是不要又码一篇流水帐出来了,就贴一点照片吧。

统计论文被引用的情况

昨天被导师叫过去分配了一个非常苦力的任务:统计他的论文被引用的情况。确切地说就是对于他的每篇论文,列出所有引用该论文的出版物,当然,所有的条目都要以标准的论文参考文献的格式给出详细信息来。因为这个毕竟是自己统计的,最后还要拿去图书馆查询、审核、盖章、等等等等。据说申请项目要用,看来这就是国内的现状吧?整天都忙这些事情,还有几个人能抽出空余时间去做正事呢?一直不明白何老师为啥要回国来。当然,从我自己的经历来看,很多事情其实也没有那么多的为什么,至于事情已经这样发生了,事后再要说个所以然出来,也并不是那么有必要的。

一开始我被这工作量给吓到了,那么多的论文,我怎么去找所有引用的啊?后来被告知只要包含 Google Scholar 上已经收录了的就可以了。不过大概一共有一千多 paper 吧,据说去年周 core 他们做得很辛苦。何老师给了我一个 Word 文档,说是之前的版本,其实只要在这基础上把更新的加进去就可以了。听起来好像工作量减少了许多,但是对于那种几百篇引用的论文,我去 Google Scholar 上找出来,然后每篇依次检查是否以前已经记录下来了,再决定要不要添加,看起来还不如直接无视之前的版本从头来呢。而且那个 Word 文档里面杂乱的格式,还有一些直接从 Google Scholar 上复制下来的还带着超链接的文本,对我来说颇有些不可忍受啊。然后何老师说,你去发动实验室的同学大家一起弄吧。-.-bb 大概这对我来说才是最困难的吧,那些认识但是却不是特别熟悉的人,就是你也不好意思去找人家帮忙,人家找你帮忙你也不好意思拒绝的那种,所以我也只有象征性地问问“最近超忙”的周 core ,他毕竟去年辛苦过一次了,于是还是不要拖他下水了。

寒假期间的一些画

今天学校本科生开始报道,这意味新学期开始了,也就是寒假结束了——怎么老是觉得自己还没开始过呢,它就结束了?不过其实寒假也不短了,有些颓废,基本没有看什么书。不过也确实做了几件事情,比如跑完了实验室的一组实验,又比如终于把 Blog 重新上线于是我又可以经常灌水了。我在异乡春节那篇文章里还提到了两件事:

一是想玩空之轨迹 3rd ,但是硬盘空间不够。其实那无非是给自己找一个不要颓废的借口,真要玩游戏,还能腾不出空间来?于是我就腾出来了。所以寒假还做了一件事就是了了这个心愿,不过 3rd 的故事确实稍有些灰暗了,但总的来说感觉整个系列的世界设定还是非常生动的,一看就知道是虚构的,但是又虚构得跟真的一样,那种感觉,就好比九州幻想里的世界一样,真的就此完结,还真觉得有些浪费呢。
再就是说我春节(或者说那天是元宵?反正我也弄不清楚)那天跑去画画了。其实事实是我那一段时间几乎天天都跑出去画。如果是执着的画家也就算了,像我这种破烂的业余水平,拿着一个小破素描本,一两支铅笔和一个完全没有轮廓的橡皮,顶着寒风站在那写生,怎么老是觉得像是在自虐呢?但不管怎么说总是比整日窝在屋里听歌发呆打瞌睡要好些。

其实对于美好的东西,也总是会希望自己也能创造出来,想写出漂亮的程序,想画出漂亮的画,其实应该是很类似的动机吧。虽然总是画得不好,但是站在自己的水平上看,也还是有几张看得过去,特别是发现后面几天比前面几天稍有进步之后,也是非常欣喜的。用照相机照了一些出来,效果很差,不过还是决定挑几张放在这里:

训练数据对分类器性能的影响

之前一个朋友托我试验一下训练数据的不平衡性对分类器会有多大影响,他所用的分类器是支持向量机(SVM),用来做文本分类。这本身是一个已经研究得比较多的领域了,也已经有比较成熟甚至可以直接在生产中使用的工具(比如这里要用的 LIBSVM)了。当然分类器是由训练数据训练出来的模型,所以训练数据肯定会对其造成直接的影响,这里所说的不平衡性就是各个类别的训练 sample 数目不平衡,比如,在二元分类的情况下,有 1000 个正例和 1 个反例,这就是严重的不平衡。正好最近实验室要做的实验也和这有点关系,我就动手试验了一下训练数据对分类器的性能的影响。有一点要说明的是,这里的“性能 (Performance)”并不是程序的运行时间和效率那个意思,特定到分类的问题上,我们可以用某一个指定的指标(比如 precision 、accuracy、error rate 等)来对结果进行衡量,衡量的结果的好坏,就是这个算法的 performance 。虽然有点难以接受,但是似乎做 research 的时候算法从“运行时间”这个角度来讲的“性能”通常都不在考虑范围之内。^_^bb

ELPA: Emacs Lisp Package Archive

TeX 有 CTAN,Perl 有 CPAN,Python 有 PyPI 和 easy_install (虽然好像至今还不支持自动 uninstall),Ruby 有 RubyForge 和 gem ,诸如 Eclipse 、NetBeans、Firefox 这样的大型软件都有方便的插件/扩展查找和自动安装的功能,更别说各大流行的 Linux 发行版所带的那些包管理器了。然而号称具有无穷可扩展性的超强编辑器:GNU Emacs ,虽然确实具有无数的扩展,但是这些扩展往往各式各样、散落各地,并且正是由于这无穷的扩展性,让各个扩展的安装定制方式千奇百怪,很难统一在一起。我想这也是 Emacs 长久以来一直没有统一的扩展管理的原因之一吧。

不过一直被人们说成不“Modern”的 Emacs 近年来也确实有发愤图强,添加了 GTK 界面的支持,新的编码系统,对 XFT 的支持等等。而 EmacsWiki 的兴起也终于让大部分的 Emacs 相关的信息有了一个统一的汇集地,大部分的扩展都可以在上面找到相关的下载和安装指南。不过这离自动管理还有一定的距离。不过,再后来,我们终于有了 ELPA (Emacs Lisp Package Archive) 。

V8 Javascript 引擎设计理念

本文翻译自 Google 的开源 Javascript 引擎 V8 的在线文档。其实我都没有真正翻译过什么东西,本来我的英文就比较一般,中文语言组织也很弱。而且许多文档(比如这篇)基本上如果是对此感兴趣的人,直接阅读英文原文文档肯定都是没有问题的。不过既然突然心血来潮,就试一试吧,能力总是要锻炼才会有的。我自己对 Language VM 比较感兴趣,V8 其实并不是一个 VM ,因为它是直接编译为本地机器码执行的,但是也有不少相通的地方。废话少说,下面是译文。

Netscape Navigator 在 90 在年代中期对 JavaScript 进行了集成,这让网页开发人员对 HTML 页面中诸如 form 、frame 和 image 之类的元素的访问变得非常容易。由此 JavaScript 很快成为了用于定制控件和添加动画的工具,到 90 年代后期的时候,大部分的 JavaScript 脚本仅仅完成像“根据用户的鼠标动作把一幅图换成另一幅图”这样简单的功能。

随着最近 AJAX 技术的兴起,JavaScript 现在已经变成了实现基于 web 的应用程序(例如我们自己的 Gmail)的核心技术。JavaScript 程序从聊聊几行变成数百 KB 的代码。JavaScript 被设计于完成一些特定的任务,虽然 JavaScript 在做这些事情的时候通常都很高效,但是性能已经逐渐成为进一步用 JavaScript 开发复杂的基于 web 的应用程序的瓶颈。

漫谈 Clustering (番外篇): Expectation Maximization

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

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

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

Backup & Restore WordPress Blog

Google recently released a tool for converting between different blogs. I haven’t tried that tool yet, but I guess you’d have two blogs simultaneously online for converting. So the traditional way of backing up the blog data is still necessary to prevent accidentally lost of data or planned blog migration.

WordPress provided a convenient way to […]