非负矩阵分解的文本聚类

文本分类、聚类算法中,最常见的障碍就是高维矩阵。对于具有一定规模的文本聚类很轻易会遇到维度成千上万的矩阵,如果按照常规计算方法,耗时将不可估量。而非负矩阵分解则是非常好的降维理论,利用非负矩阵分解我们可以将高维矩阵分解为可接受的小维矩阵,并保持其原矩阵的特征。这篇文章将介绍如何利用非负矩阵分解做文本聚类。非负矩阵分解英文全称是 Non-negative matrix factorization(NMF)。请您记住本文只做文本聚类,并不介绍如何中文分词。

下面的引用是Wikipedia对NMF的历史介绍:

Early work on non-negative matrix factorizations was performed by a Finnish group of researchers in the middle of the 1990s under the name positive matrix factorization. It became more widely known as non-negative matrix factorization after Lee and Seung investigated the properties of the algorithm and published some simple and useful algorithms for two types of factorizations. [Read →][1]

好了废话我不多说,相信对这篇文章感兴趣的人对NMF也应该有所了解。

我根据实际的情况来写这个工作过程。从我手头有的资料说起:

  1. 用于训练的样本数据,也就是已经做好分词的中文文本,类别已经标注 file1.txt~file50.txt 每10篇代表一大类(环境、教育、经济、体育、政治)
  2. 停用词表(如果您还没有,请在google里搜索)
  3. 待测试文本,属于上述5大类的文本,也是已经做好分词处理的
  4. 开发环境(可编译c代码即可)

整个文本分类可以分为3大部分:

  1. 文本的处理
  2. 利用NMF做矩阵分解
  3. 利用NMF得到的降维特征矩阵和相关数据分类待分类文本

注:请从宏观角度记住着3大部分

第一:建立VSM

实际上第一步文本的处理无非就是找到VSM (Vector space model) 向量空间模型。利用TF-IDF(term frequency–inverse document frequency)求出每个词的权重。这步的目的就是生成一个所有文章,所有词的一个矩阵。这个矩阵带有这些文本的特点。(tf-idf也就是 词频-逆文频率指数) 公式如下:

  • TF=某词在一文本中出现次数/这篇文本总词数
  • IDF=log(文本集合总数/这个词出现的文本个数)
  • TF*IDF就是这个词在特征矩阵的权重。

关于这个google数学之美系列中有很生动的介绍请自行研读, 我这里简单介绍,tf就是一个词在文本中出现的频率,idf则可以反映出这个词在整个文本集里的广泛程度。如果一个词出现的越广泛那么它的主题相关性就越低。就像google数学之美系列中介绍的一样“原子能 的 应用”这句话里“原子能”的广泛度应该比“应用”低,这个是个常识,至于“的”,由于它太广泛所以沦落到停用此表里了。

这个生成的矩阵大概是个什么样子呢?我随便写一个样子把。数据我瞎写的看看样子而已。

这里面的每个数据都是TF*IDF得到的。好下面我吧第一部分求VSM的代码贴一下:

截图显示该程序运行结果如下:

nmf1

经过这个程序会把50篇训练样本变成一个T_v.txt文件也就是这50篇文章的VSM,还有一个T_word.txt这个全部的词表。这是很好的开始,我们已经把一篇篇文章变成可以计算的数字了。

第二:VSM做NMF分解

接下来第2大步骤用NMF分解矩阵。这个步骤目的很简单,给VSM降维。因为VSM太庞大了,文本分类速度会很慢。NMF可以把一个非负矩阵X分解成2个非负矩阵B、H,满足X≈BH。矩阵分解的数学研究有很长历史,大家可以自己慢慢学习。至于矩阵分解后为何可以做文本分类,呵呵大家可以后悔自己上学的时候为什么没好好学习线性代数了,不过可以简单的理解为分解后的矩阵带有原矩阵的特点

第二步可以使用不同的矩阵分解方法,例如PCA(主成分分析)、ICA(独立成分分析)、SVD(奇异值分解)、VQ(矢量量化)等,它们各有特点。不过都是对原矩阵没有约束的,NMF则有非负这个约束条件。

NMF算法3个输入参数分别是X,R,IterateNum 。X是哪个大矩阵,R是降维后的B的秩,IterateNum 是NMF的迭代次数。NMF是迭代计算的,需要迭代次数。生成的BH会收敛。迭代次数越多BH越接近X。至于迭代多少次就可以自己可以测试,满足精度就可以了,否则NMF迭代计算比较费时间。

NMF算法2个输出分别是B和H。算法描述如下:

对上面这个伪代码做个解释。先说B,H的大小原矩阵X(w,h)的话 B(R,Xh) H(Xw,R) (注:w表示矩阵宽度,h表示高度)

初始化B,H是将2个矩阵的数据随机赋值,正浮点数范围(1.0~10.0)就可以了。接着第一步里B需要归一化,归一化的意思就是把B变成一个特殊的矩阵,特殊之处在于,B的每一列相加正好等于1。

第二步迭代IterateNum次,其中U’表示矩阵转置,.表示点乘就是矩阵对应位置数据相乘 ./就是点除对应位置相除。就是矩阵乘法。

下面贴一下NMF 的代码:

现在虽然代码已经贴出来了,但是有些细节还没介绍。NMF程序计算完,它把VSM生成的T_v.txt这个矩阵分解,生成了B和H。但是第3步的文本分类并不是直接利用生成的B、H,而是需要使用 B’ 和 B’ * X 。所以 T_B.txt 和 T_eigenvector.txt 这2个文件,T_B.txt 是分解出的矩阵B的转置,T_eigenvector.txt 则是 B’ * X 。所以保存这2个矩阵。

第三:文本文类

从实际角度考虑文本分类传入的参数应该是一个待分类的文本,输出是它属于哪个类别。这样需要计算的就是这个文本和哪个类别的相似度最高。

从程序计算的角度考虑,现在已经拥有的数据是训练样本生成的特征矩阵T_eigenvector.txt和B的转置T_B.txt 。所以待分类文本也需要做处理才能用于计算,当然是生成待分类文本的特征查询向量q,注意是q查询向量,也就是一个1xW的矩阵。这个向量应该在第一步建立的表征词表T_word.txt的基础上。因为这样才能保证待分类向量和训练样本在同一个语义集合。请仔细理解这里。

例如上面的例子中,我建立的表征词共8109个,那么如果要分类一个文件ABC.t×t 那么需要建立的这个向量便是ABC内的词映射到这8109个词上的统计表,使用tf计算权重。这个向量也是1×8109的。

接下来我就说明如何计算这个查询向量q和训练出来的特征矩阵的相似度。使用余弦距离计算2个向量的距离。T_eigenvector.txt的每一列表示一个训练文件的特征向量。余弦距离计算,传入的参数是2个同维的向量,而T_eigenvector.txt的每一列是个R维的向量,当然我们的这个查询向量q则有8109维。这时候大家应该想的了,需要第2步生成的哪个B’ ,也就是T_B.txt 。公式如下:

这个公式把查询向量q转化成R维。这样就可以计算这个查询向量和哪个训练文本相似度高了。

把q分别和T_eigenvector.txt的50列计算余弦距离。然后每10列求平均值,得到5列,这5列就是查询向量和5大类文本的相似度,越大的相似度越高。

下面写出代码:

这样通过上面的程序我们就实现了最后的分类部分。下面是一次试验结果R=80 IterateNum=80。

可以看到有2篇分类错误。而经济类文章被分入政治类,体育类被分入教育类,也是可以理解的。这些话题有很多重合的地方。