用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做科学计算,但是还没找到力所能及且自己觉得有意思的事情。而且我自己也才入门水平。

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

广度优先搜索和双向广度优先搜索求解Matrix67的迷宫问题的C语言实现

问题描述见 http://weibo.com/1915548291/z4eTPtAnv
简单来说,就是一个小迷宫。可以重复走,但是不能倒退。经过每条边都意味着执行一次运算,现在要2011从迷宫口进去,2012从迷宫口出来。
一个思想就是广度优先搜索,能够找到最短的路径。如果对每个状态标记祖先,就能回溯找到完整路径。自己实现了一个简单的Hash,因为最终步数并不多,所以对Hash的要求也不高。
之后又在广度优先搜索的基础上进行修改,实现了双向广度优先搜索。一个点从入口开始搜,一个点从出口开始搜。需要注意的是从出口开始搜的话,所有运算都是相反的。搜的时候会有两个队列,直到两边“碰头”为止。
测试结果中可以看到,双向广度优先搜索明显更快一些。
马上光棍节了,几个常量都定义的全是1,哈哈。

Continue reading »

第一次玩Hackathon

前几天去腾讯玩了一回Hackathon,确实很好玩,某种程度上比acmicpc还好玩。
之前根本没有打算进决赛的,所以复赛也没好好做。最近很忙,如果腾讯把时间推迟一周,我就肯定放弃了。
我们项目选题是分析微博/人人用户的特征,随便指定个人就能分析点有意思的东西出来。这个思路是yangzhe1991友情提供的。
爬数据、整理数据、分词、画图、前端展示。个人认为至少从代码量上看,可能是里面最累的项目(我可不愿意只做出半成品……)。这也是为什么第一天一直没有可展示的东西做出来的原因。队里BearForest也有做网站经验,所以配合起来比较容易,而javaman搞C++,主要负责后台数据处理。我们最不擅长美工,由于腾讯配了设计师,也容易很多(专业的人真NB啊……画图又快又好看)。前端其实是最容易做的,只有画柱状图和tag云略麻烦,但前者我以前做网站用过很好的插件,比较熟悉。所以前端放到最后再做,反正没有难度,结果就导致中间裁判们来“骚扰”的时候,实在没东西可以给他们看。
============据说中间插播广告效果最好============
ACM/ICPC信息站 http://acmicpc.info
ACMer博客瀑布流 http://blog.acmicpc.info
晒代码 http://shaidaima.com
acmicpc微博 http://weibo.com/acmicpc
acmicpc人人 http://renren.com/acmicpc
====================广告结束==================
三个人一夜没睡觉,期间BearForest喝了4罐红牛,javaman写了一首诗……
早上裁判们再来看的时候,都觉得我们突然就做出东西了……汗……其实因为整后台最花时间而已。
答辩一切顺利,程序没什么大bug,裁判们测试的几个人都算的还不错。其实除了微博,我们把人人网也做好了,只是正常人都不会记得自己或者其他人的人人主页地址的(因为一般都没有个性域名……),所以没特意找人玩了。早考虑到这点就暂时先不做了,多分析一个网站还是花了不少精力的。
晚上吃饭的时候,BearForest问我觉得能有第几名。我说估计在第三第四之间吧。结果就真的被我说中了……莫非是因为我抽中iPad导致RP用光,居然真的是第四名。略桑心。但是发现,前三好像都是app吧……诺基亚用户表示无法跟上app的潮流,所以只好一直搞web玩。
结论:Hackathon很好玩。
比起ACM来,Hackathon不会因为出题不好、数据出错而影响效果,也不会因为只考算法而不够全面。做出东西可以展示,时间也不是太长。确实很好玩。只是评价有一定难度。大家选题差距较大,评分标准没有ACM容易统一。个人认为Hackathon比AI大赛也好玩一些。如果存在一种结合了ACM和Hackathon的比赛形式也许会更好玩吧,不知道存在吗?
但可惜这不能经常玩,身体受不了。要是之前想过的每个点子都这种强度去搞,早就搞完了。而现在还有很多想法都搁置着。我和licstar都没什么空,有一些好玩的点子还都没有动手。并且平时维护已有的几个网站就已经比较累了。
收获公仔、抱枕、iPad、Kindle,还是很赚的啊。。。明年这时候也还没毕业,如果有空再去玩一下吧。
截至本文发布时,报道比赛结果的ACMICPC人人公共主页状态被转发145次,ACMICPC微博被转发80次。应该给我们无盈利的acmicpc.info团队一个宣传奖什么的 @_@

随机样本选择——快速求解机器学习中的优化问题

前阵子去参加了数学规划会议,报告很多,人也很多。或者说报告和人过多了……
有少数感兴趣的报告,这里谈一下全场最后一个报告。报告人是Jorge Nocedal,就是著名的LBFGS的作者。
他关注的问题是一类机器学习中非常常见的优化模型:
$J(w) = \frac{1}{N} \sum_{i=1}^N l(f(w; x_i); y_i)$
他谈到了机器学习里面常用的随机梯度下降法(stochastic gradient descent, SGD)。在实际大数据的情况下,他比经典优化方法效果要好。因为经典优化方法算一次下降方向就已经需要很大计算量了。
SGD需要的一次迭代计算量非常小,但是代价是他非常可能不是下降方向,而且需要一个有经验的人选择很好的步长(学习速率)。并且,在理论上,SGD的性质少,所以在优化这个方向里没什么人提到。即使是在计算上,Nocedal也提到SGD有个很大的缺点是不容易并行。
以上这些现象我在学习推荐系统SVD模型的时候也有一些感触。
所以他采用了另外一个思路,思想简单,效果却很好。而且能很好的利用上经典优化算法。经典算法都需要计算梯度。他的思想就是:只选取一部分样本来计算梯度。
这样有一个近似的梯度计算方法,用
$J_S(w)=\frac{1}{|S|} \sum_{i \in S} l(f(w; x_i); y_i)$
代替原来目标函数,求它的梯度。
其中S是样本集,样本集的大小相对于N来说很小。但是他也不能太小。只要有了梯度,很多算法都能用上了,比如说他文章中提到梯度方法,Newton-CG方法。S中的元素可以在每次迭代的时候随机选取。
但是需要面临的一个问题就是如何确定S的大小。他给出了一个公式用来确定S的大小是否合适。
$\| \nabla J_S(w) – \nabla J(w) \|_2 \le \theta \| \nabla J(w) \|_2 $
这个式子的含义就是样本集上的近似梯度和真实梯度足够接近。当然这个又回到了老问题,就是真实梯度计算量太大。于是他又做了一些近似变换,使得只需要计算在样本集S上的方差即可近似估计上式是否满足。
$ \frac{ \| Var^2_S( l(w; i) ) \|_1 }{ \| S \| } \le \theta ^2 \| \nabla J(w) \|_2 ^2 $
这样就可以每次迭代验证一下S是否足够大,如果不够大就扩大一下。
这个技巧部分解决了我对大规模优化计算的一些困惑,他可以利用上很多经典优化算法,并且又能让每次迭代的运算量不会太大。这个技巧也使得并行计算容易用上去了。
后面考虑去使用一下,算算某个实际例子测试一下效果。
Nocedal这篇论文的链接:http://users.eecs.northwestern.edu/~nocedal/PDFfiles/dss.pdf

使用Google Reader API

Google Reader是非常强大的RSS阅读器,更强大的是他提供了很多API,方便开发第三方应用。最近尝试了调用Google Reader API,发现网上资料不是很全,尤其是中文的,就再总结一下。

Continue reading »

libFM学习感想

libFM全称为Factorization Machine Library,是由Steffen Rendle于2010年提出的。最近由于他以libFM为队名,在KDD CUP 2012和刚刚结束的Music Hackathon中都取得了很不错的成绩,所以libFM引起了一些人的注意。我最近拜读了一下libFM的相关论文,以及源代码,也有一些收获,就总结一下。

Continue reading »

也说MinHash

之前突然想看看实时推荐系统有什么文章,看到Google文章中提到MinHash,然后看到xlvector的blog中还有网上也搜到其他一些blog中也有提到。它可以用来加速计算相似度,对于大规模数据,速度非常快。

Continue reading »

评分数据的存储——Mahout笔记之二

趁热打铁~
这是Mahout in action一书的第三章。

Continue reading »

推荐系统介绍——Mahout笔记之一

准备开始看Mahout in action~
Mahout是Java写的知名推荐系统工具之一,看的目的不是使用Mahout,目的是通过这份资料了解Mahout是怎么做的。

Continue reading »