CWYAlpha

Just another WordPress.com site

Thought this was cool: 用pLSA实现博文分类

leave a comment »


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%以上应该问题不大。期待比赛中有更好的思路和程序。

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

from Dora Blog: http://diaorui.net/?p=406

Written by cwyalpha

四月 11, 2013 在 3:53 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: