Friday, April 5, 2013

基于LDA的博客分类算法


题目:给定一篇acmer的博客,输出博客类型。分三种:1.acm有关(包括解题报告,参赛感言,退役贴等)2.acm无关的技术贴(如网络数据库等)3.其它(比如聊谁谁谁的音乐之类)
已知信息5000篇博客的内容和题目(无类标)

思路
由于待分类的博客都是acmer的博客,所以其实范围比较小,拥有acmer自身的特点,比如OJ, 算法之类的词便是常客,代码也会经常出现在文章中。

笔者给出的解题方法中,包括2个层次:1直接根据某些特征判断类别(只对12类有效)21)无效时,采用第二种统计概率的方法(也可以装X地叫做数据挖掘的方法)。即通过2个条件投票:
    a. 代码部分占文章总体的比例。算法认为代码所占比例越高,越可能是12
   b. 利用训练数据训练出的model,来预测新的blog文章的类别

1)中所述,实质上就是作者根据自身经验assert一些1类或2类的条件,一旦文章满足某个条件,则该博客分类结束。
2)中所述,a是直接在读入文章时,统计代码字符占博客总字符的比例,笔者设定的条件是此比例高于50%时,算作第1类(此处仅是为成为第1类投一票,并非就此可决定它就是第1类,下同);若此比例在20%~50%之间,算作第2类;否则算作第3类。若某一博客的1 2 3类票数相等,优先判断为第1类。或许看上去不合理,但是由于待分类博客的特点,绝大多数的博文都是第1类,此举在实际中的效果并不差。

以下讲述训练model的过程。
   1.训练数据是无类标的博文,需要首先预处理数据,包括:1)去掉html标签。2)去掉中文stop words
    2.对于经过步骤1clear后的数据,去掉代码部分(判断代码部分可用html标签),再进行分词,以此作为训练modelInput data.
    3.笔者利用Mallet中的Topic Modeling来标注训练数据(Mallet中的TMLDA实现)。笔者给LDA设置了10topic,即所有训练数据都会被分为这10topic中的某一个topic中去。再人工review10topic中各自属于哪个类(123类),可见其实工作量很小。说到此,看上去,其实LDA的主要作用就是给训练数据标类标。没错,笔者只用到了这点。
  4.当数据有了类标就好办了,此时就是一个supervised的分类问题的训练model部分。笔者采用的是Naïve Bayesian classification. 说白了就是统计出一堆概率,再用在预测时。统计的是:P[word | classID],即某词word在类别classID下的概率。笔者只用了相对高频的词,所为高频的定义随手设的。还有一个概率是p[classID],即某个类的概率。
到此,model就建完了。就是一堆概率算完了。

以下讲述利用model来预测类标的过程。
    1.  对于一篇输入的blog,首先clear(去html, code,不需分词,分词就太复杂了)
    2. 统计code比例,得出第一票
    3. model中的高频词,遍历blog,若出现高频词,则更新p[word|classID],最后取使∏p[word|classID] * p[classID]得到最大值的classID作为此blog的类标。
最后,此blog的类标就出来了。笔者最后测试,准确率约70%(挺低的,但上述方法的改进空间也很大)

读到这里,可能你还有部分疑问:
    1. LDA是什么?
    2. Naïve Bayesian Classification是什么情况?
    3. 怎样用Mallet处理中文的?
Mallet 不支持中文的,尤其不能分词。笔者采用的方法是先自己分词分好,再将其编码为数字,作为Mallet的输入。
关于MalletTopic Modeling的用法,详见:http://lillianxiong.blogspot.com/2013/02/new-to-mallet-machine-learning.html

最后的最后,我做这个题目,其实只是想要那个Moleskine的本子。求不卡~