Archive: 一月, 2013

用pLSA实现博文分类

pLSA应该是做文本聚类的,不是文本分类的。
不过我是杂牌军,非专业人士,自己看的pLSA,所以会yy还能用到哪里去。
出发点是这样一个问题:有若干博文,需要将他们自动分类为ACM竞赛相关博文,非ACM竞赛的技术相关博文,非技术博文三种类型。这个问题的来源是因为 blog.acmicpc.info 这个网站的需要,在完成后会实际上线使用。目前也有一个正在进行中的比赛针对这个问题: http://acmicpc.info/archives/1194
因为需要实际上线用,难点在于占用资源不能太多,运行时间不能太长,不能用第三方工具。但是可以用第三方工具做训练,预测的时候不用就行了。

题中给出了5000个文章。可以先对这5000个文章用pLSA聚类,提出主题。
首先,我们要对文章做预处理,预处理主要包括几个方面:
1)去除网页标签:正则表达式替换即可,<[^>]*>替换成一个空格。
2)html实体替换:主要包括&nbsp;替换成空格,&lt;替换成<之类的,如果用PHP语言,可以使用htmlspecialchars_decode函数。
3)分离文字和代码:有几个策略,高级一点的是检测代码位置,一般在<pre>标签中间或者<textarea>标签中间,当然也有可能两边没标签,只能根据内容检测。如果要用这个方法,则前面去除标签步骤应该后做。山寨一点的办法就是把ASCII码全当成代码分离出来,效果也还行。
4)统计每个文章的词,这里可以使用ICTCLAS做分词,建议添加一些人工词,比如一些算法相关词汇。ICTCLAS支持UTF8等多种编码格式。输出中也提供了词性,我们只需要统计名词和用户自定义词即可,其他的词都丢掉。词太多和词太少的文章丢掉,不拿来训练。

然后要用pLSA算法,可以学习这个博文:概率语言模型及其变形系列(1)-PLSA及EM算法,在看这篇之前先看文本语言模型的参数估计-最大似然估计、MAP及贝叶斯估计可能效果更好。

实际写程序,就是个迭代,说夸张点,只有加减乘除等基本运算,核心代码很短。他文章中给出了式子。
设定一个合理的主题数量,然后就可以聚类,算出$p(w_j|z_k)$,就是每个主题下选中每个单词的概率。

下面就是讨论怎么用到博客的分类中去。
根据$p(w_j|z_k)$,列出各个主题下概率最高的单词,然后人工判断他们有多大概率属于目标的三类文章。分别设定一个权值,我们可以记为$p(t_l|z_k)$,也即主题$z_k$属于文章类型$t_l$的概率。
实际预测的时候只需要关键词列表$w_j$,主题下选中各单词的概率$p(w_j|z_k)$,还有人工设定的分类概率$p(t_l|z_k)$
然后拿到一篇新文章,不必做分词和之前训练时的繁杂的预处理,只要用关键词列表扫一遍即可,直接寻找子串,每匹配上一次关键词就粗略的认为关键词出现了一次。这样简单,也不需要第三方库了。
可以跑一次只包含一个文章的pLSA,并且$p(w_j|z_k)$固定为之前算出来的数值不动,只迭代更新$p(z_k|d)$。算出$p(z_k|d)$之后,利用$\sum_k p(t_l|z_k)p(z_k|d)$算出文章属于每一类的概率。选取最高的一个概率做分类即可。

这里面人工的工作量只有设定$p(t_l|z_k)$,因为主题数很少,所以人工的工作量非常小。
当然,说归说,做起来还有很多小问题。我粗略的写了一个版本,也没仔细设定很准确的$p(t_l|z_k)$,已经就可以达到80%以上分类正确率,数据文件大小,运行时间等都满足问题要求,占用资源很少。只要再做一些细微的修正,我觉得由此再改进到90%以上应该问题不大。期待比赛中有更好的思路和程序。

这个思路应该同样可以用于更广泛的博文分类,或者新闻分类等。

VPS、全局优化、Python、并行

说说最近的事,找不到一个合适的标题,就以若干关键字为题好了。

最近购买了一个VPS,新年特价,30刀一年,2G内存,续费仍然是30刀一年。对,你没看错,没有少写一个0
据说这家超售很严重,但是技术水平不错,不大看得出来。
有了VPS就可以继续肆无忌惮的挂网站、爬网页什么的了。实测CPU很给力,跑程序很快。但是毕竟是便宜货,刚入手两星期左右,今天差不多挂了10个小时才修复,看在价格上也就不说什么了。
科院选课助手 ishangke.net 目前已经迁移过去了。由于配置的提升,一些耗费内存、CPU的操作有明显变快。
预计一个月内可能会上线一个和音乐有关的小站,请期待。兴奋的是,以前从未发布过类似的东西。不过悲观的认为,不会有几个用户吧。
最近在想一个相关的问题,我如何通过网上能获得到的数据,进行音乐推荐呢?目前还没好主意。

这段时间在外访问,生活上比国内要无聊很多。这边的老师在做一些全局优化的问题,针对的是实际工程上的问题。我完全不懂背景,单从数学上来看,就是说有一个非常复杂的函数,复杂到求一次函数值需要解一大堆东西。函数本身也写不出表达式,只是给自变量能求出函数值而已。目的是用最短的时间尽可能找到函数最小值。由于求一次函数值花费时间很多,比如要将近一分钟。所以花费的时间就约等于函数值计算的次数。也就是要尽量少的找一些点求值,却希望找到最小值点。基本思想就是用一个函数去插值,但是为了求解到全局最优,又不能一直去找一堆距离很近的点,也要去尝试一些“未探索的区域”。所以对这两个目标进行一种权衡。

这边的程序都有Matlab和Python两个版本。老师说是Matlab要付费所以后来的程序都选择编写Python版本,于是果然看到了国外开始用Python进行科学计算的实例了。但是我用的太少,稍微补了一下Python和NumPy的基本知识,略有收获。第一步的任务只是用现有的程序去测试一个实际问题,感觉难度不大,具体意义大不大,由于不了解问题背景,我也没有发言权。我觉得有必要做点什么在国内宣传一下使用Python做科学计算,但是还没找到力所能及且自己觉得有意思的事情。而且我自己也才入门水平。

我感觉他这里的并行应该是希望能到集群上跑,但是他这里没有集群环境,用的是一些配置很不错的多核服务器。然后程序采用的是单机多进程,不是多线程。所以逻辑上来说移植到集群上并行跑问题不是太大,只要找到相应的工具应该就能办到。