javalda算法代码,java算法实现

NLP系列（三）LDA主题模型

LDA模型是NLP中很基础也是大家广为熟知的模型，在面试过程也经常遇到。本文简单讲述下其大致流程。

首先，我们来感受下LDA是什么，

看来，不同人在不同场景下对LDA的认识，那我们看下百科的解释：

看到这里我们只需要先记住： LDA的目的就是要识别主题，即把文档—词汇矩阵变成文档—主题矩阵（分布）和主题—词汇矩阵（分布）

对于语料库中的每篇文档，LDA定义了如下生成过程（generativeprocess）：

1.对每一篇文档，从主题分布中抽取一个主题；

2.从上述被抽到的主题所对应的单词分布中抽取一个单词；

3.重复上述过程直至遍历文档中的每一个单词。

语料库中的每一篇文档与T（通过反复试验等方法事先给定）个主题的一个多项分布 （multinomialdistribution）相对应，将该多项分布记为θ。每个主题又与词汇表（vocabulary）中的V个单词的一个多项分布相对应，将这个多项分布记为φ。

LDA的核心公式如下：

p(w|d)=p(w|t)*p(t|d)

直观的看这个公式，就是以Topic作为中间层，可以通过当前的θd和φt给出了文档d中出现单词w的概率。其中p(t|d)利用θd计算得到，p(w|t)利用φt计算得到。

实际上，利用当前的θd和φt，我们可以为一个文档中的一个单词计算它对应任意一个Topic时的p(w|d)，然后根据这些结果来更新这个词应该对应的topic。然后，如果这个更新改变了这个单词所对应的Topic，就会反过来影响θd和φt。

LDA算法开始时，先随机地给θd和φt赋值（对所有的d和t）。然后上述过程不断重复，最终收敛到的结果就是LDA的输出。再详细说一下这个迭代的学习过程：

1.针对一个特定的文档ds中的第i单词wi，如果令该单词对应的topic为tj，可以把上述公式改写为：

pj(wi|ds)=p(wi|tj)*p(tj|ds)

2.现在我们可以枚举T中的topic，得到所有的pj(wi|ds)，其中j取值1~k。然后可以根据这些概率值结果为ds中的第i个单词wi选择一个topic。最简单的想法是取令pj(wi|ds)最大的tj（注意，这个式子里只有j是变量），即argmax[j]pj(wi|ds)

3.然后，如果ds中的第i个单词wi在这里选择了一个与原先不同的topic，就会对θd和φt有影响了（根据前面提到过的这两个向量的计算公式可以很容易知道）。它们的影响又会反过来影响对上面提到的p(w|d)的计算。对D中所有的d中的所有w进行一次p(w|d)的计算并重新选择topic看作一次迭代。这样进行n次循环迭代之后，就会收敛到LDA所需要的结果了。

N个文档组成的语料库（? 1，? 2，"……" ，? ?），由V个词组成的词汇表。矩阵中的值表示了词?? 〖在文档?〗 ? 中出现的频率，主题用Z表示，下面对语料库中的每一个word随机指派一个主题编号? ?，统计每个?_?下出现的word次数，可得一个主题—词汇矩阵。

统计每个词代表的主题在每一个文档中出现的次数，可得出以下矩阵文档—主题矩阵

以上讲了大致LDA的感性认识，如果进行严格的数学推导请看这篇文章( )，本人认为是看到的不错的文章。

LDA对自己一直是一个谜，看了网上的很多资料，然后整理了几篇不错的，我在这里贴出来。本篇文章主要大致了解了下LDA的大致流程，如果真正搞懂其背后数学原理，还得反复看一下下面的文章：

LDA（LDA文档主题生成模型）_百度百科

相关问答

Q1: 降维算法二：LDA（Linear Discriminant Analysis）

学习分类算法，线性分类器最简单的就是LDA，它可以看做是简化版的SVM，如果想理解SVM这种分类器，那理解LDA就是很有必要的了。

谈到LDA，就不得不谈谈PCA，PCA是一个和LDA非常相关的算法，从推导、求解、到算法最终的结果，都有着相当的相似。

本次的内容主要是以推导数学公式为主，都是从算法的物理意义出发，然后一步一步最终推导到最终的式子，LDA和PCA最终的表现都是解一个矩阵特征值的问题，但是理解了如何推导，才能更深刻的理解其中的含义。本次内容要求读者有一些基本的线性代数基础，比如说特征值、特征向量的概念，空间投影，点乘等的一些基本知识等。除此之外的其他公式、我都尽量讲得更简单清楚。

LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种 supervised learning 。有些资料上也称为是Fisher’s Linear Discriminant，因为它被Ronald Fisher发明自1936年，Discriminant这次词我个人的理解是，一个模型，不需要去通过概率的方法来训练、预测数据，比如说各种贝叶斯方法，就需要获取数据的先验、后验概率等等。LDA是在 目前机器学习、数据挖掘领域经典且热门的一个算法 ，据我所知，百度的商务搜索部里面就用了不少这方面的算法。

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。要说明白LDA，首先得弄明白线性分类器( Linear Classifier )：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：

上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：

红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。下面我来推导一下二分类LDA问题的公式：

假设用来区分二分类的直线（投影函数)为：

LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值。

类别i的原始中心点为：（Di表示属于类别i的点)

类别i投影后的中心点为：

衡量类别i投影后，类别点之间的分散程度（方差）为：

最终我们可以得到一个下面的公式，表示LDA投影到w后的损失函数：

分类的目标是， 使得类别内的点距离越近越好（集中），类别间的点越远越好。 分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。

我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.

同样的将J(w)分子化为：

我们希望 分母越小越好，分子越大越好 ：

分母小，则每个类内部数据点比较聚集；

分子大，则两个类别的距离较远。

所以需要找出一个 W 使 J(W) 的值最大。

这样就可以用最喜欢的拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1（这是用拉格朗日乘子法一个很重要的技巧，在下面将说的PCA里面也会用到，如果忘记了，请复习一下高数），并作为拉格朗日乘子法的限制条件，带入得到：

这样的式子就是一个求特征值的问题了。

对于N(N2)分类的问题，我就直接写出下面的结论了：

二者都有降维的作用。

Q2: LDA在短文本分类方面的扩展模型有哪些

针对短文本存在的稀疏问题，有一系列的算法被提出。可以大致分为三类。第一类采用一种的简单的假设去学习隐含的主题，可以认为是基于窗口的算法，一个窗口内的词具有同一主题或者共现的词具有相同的主题，代表算法Dirichlet Multinomial Mixture (DMM) in conference KDD2014, Biterm Topic Model (BTM) in journal TKDE2016。第二类算法可以成为伪长文档算法，主要是把短文本聚合成伪长文档来增强词的共现信息，代表算法有Pseudo-Document-Based Topic Model (PTM) in conference KDD2016, Self-Aggregation-Based Topic Model (SATM) in conference IJCAI2015。 第三类是通过外部语料（如词嵌入）增强词的语义信息，代表算法有Generalized P´olya Urn (GPU) based Dirichlet Multinomial Mixturemodel (GPU-DMM) in conference SIGIR2016, Generalized P´olya Urn (GPU) based Poisson-based Dirichlet Multinomial Mixturemodel (GPU-PDMM) in journal TIS2017 and Latent Feature Model with DMM (LF-DMM) in journal TACL2015.。

这些算法的源代码都可以在这个基于JAVA的包里获取到网页链接。

Q3: 如何使用mahout对文档进行lda主题分析

利用sqoop将数据从MySQL导入到HDFS中,利用mahout的LDA的cvb实现对输入数据进行聚类,并将结果更新到数据库中。数据流向图如下

mahout算法分析

输入数据格式

为IntegerWritable, VectorWritable的matrix矩阵,key为待聚类文本的数字编号，value为待聚类文本的单词向量Vector, Vector的index为单词在字典中的编号, value为TFIDF值。

算法相关参数详解(不包含hadoop运行参数)

项目中所有参数设置均与mahout-0.9目录下的examples/bin/cluster-reuters.sh的147-172行设置一样，即

$SCOUT cvb -i ${WORK_DIR}/${ROWID_MATRIX_DIR}/matrix -o ${WORK_DIR}/${LDA_DIR} -k 20 -ow -x 20 -dict ${WORK_DIR}/${DICTIONARY_FILES} -dt ${WORK_DIR}/${LDA_TOPICS_DIR} -mt ${WORK_DIR}/${LDA_MODEL_DIR}

input -- 输入数据的hdfs路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-matrix-debug/matrix

dt -- 文档主题输出路径,保存了每个文档的相应topic的概率,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-topics

mt -- model的路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-lda-debug

k -- number of topics to learn,这里设置成20

x -- 模型迭代次数,也就是需要多少次迭代来生成最后的Model,默认值20

seed -- Random seed,生成初始readModel时的种子,默认值System.nanoTime() % 10000

dict -- 字典路径,这里是/home/hadoop-user/scout_workspace/scout/dataset/reuters-out-seqdir-sparse-lda/dictionary.file-*

a -- Smoothing for document/topic distribution, document/topic分布的平滑系数,默认为1.0E-4

e -- Smoothing for topic/term distribution, topic/term分布的平滑系数,默认为1.0E-4

关于a和e,根据描述,a和e的合适取值为k/50(k为topic数量),但是这个网页还保留着mahout ldatopics的命令介绍,而mahout 0.8,0.9均没有该命令,推测应该是比较陈旧的内容,因此还是根据cluster-reuters.sh中的设置来，也就是采取默认值。

mipd -- 这个参数非常重要，对于每个文档程序是先用RandomSeed来生成一个初始的readModel然后进行mipd次迭代，算出最终的model进行更新，这里选默认值10次

LDA算法程序分析

算法的大致流程如下

1.解析参数与Configuration设置

2.读取Model(第一次运行时没有这个过程)

如果hfds上面已经有部分model，那么程序将读取最后一个model，并以这个model作为初始readModel来继续进行算法迭代，也就是说有类似于断电-重启的机制

3.运行算法迭代(Mapper过程)生成LDA模型

这个过程是最为复杂的阶段，许多地方我也不是很明白，我将尽最大努力进行解释

首先分析Mapper,即CachingCVB0Mapper,顾名思义就是能够缓存的Mapper，表现在其readModel的选取上面，如果目录里面不存在任何model则用RandomSeed初始化一个readModel，否则读取最近的一个model。程序将model划分为readModel和writeModel，这两个都是TopicModel类，并由ModelTrainer来进行调度和管理

CachingCVB0Mapper整个过程如下图所示(清晰大图见附件)

在上面这个整体框架下,mahout程序应用了CVB0 Algorithm来计算LDA模型, 在map过程中通过对向量docTopic和矩阵docTopicModel的反复迭代求解，算出每个document的docTopicModel并且在update writeModel阶段将docTopicModel矩阵进行向量的相加操作，经历完所有的map过程后得到整个corpus的docTopicModel矩阵，最终在cleanup过程中将topic的index作为key，矩阵docTopicModel作为value写入reduce。该过程涉及到的算法如下所示

CVB0算法分析图解(清晰大图见附件)

4.利用生成的LDA模型推导出topic的概率分布

算法总结

可以看出算法本质上面就是bayes公式和EM算法的结合

E过程就是首先假定一个均匀分布且归一化的topic概率分布向量docTopics，利用该值通过贝叶斯公式算出单词 - 主题的概率分布矩阵 docTopicModel(见CVB0算法分析图解中的第一步)

M过程就是根据生成的docTopicModel进行CVB0算法分析图解中的2,3,4,5步重新计算得到新的docTopics

然后反复重复 E - M 过程n次，得到收敛后的docTopics和docTopicModel，其中docTopicModel可以用于lda模型的更新，而docTopics就是我们聚类需要的topic概率分布向量

算法后记

几点问题还没有得到解决

1.在mahout中是按照下面的式子计算docTopicModel的

double termTopicLikelihood =

(topicTermRow.get(termIndex) + eta) * (topicWeight + alpha)/ (topicSum + eta * numTerms);

疑问就是该式子比贝叶斯公式添加了几个平滑系数项，这样写的理论依据在哪里，来源于哪篇著作或者论文，平滑系数eta和alpha分别是代表什么含义，如何选取这两个系数。

2.CVB0算法分析图解中第2步进行归一化的理论依据，即为什么要进行归一化

3.update writeModel过程中对于topicTermCounts的计算

即为什么要在每次map时候对p(topic | term)进行累加，还没有完全想明白

项目运行环境

hadoop-1.2.1

sqoop-1.4.4

mahout-0.9

关于环境的安装部署请参考相关文章，这里不多加赘述。上面三个软件在我本机的都是部署在/home/hadoop-user/mahout_workspace/目录下。另外自己写的scout项目部署在/home/hadoop-user/scout_workspace/目录下

项目代码

项目代码已经放到Github上有兴趣的同学可以下载下来看下，重点查看bin目录下的脚本文件以及driver,export,analyzer等几个包下的java文件

整个项目架构分析

该项目的初始数据保存在MySQL中, 算法分析需要map/reduce过程以及hdfs文件系统的参与, 最后将结果更新至MySQL,整个过程如图所示

Q4: 降维算法之LDA(线性判别降维算法)--有监督

    LDA在模式识别领域( 比如人脸识别，舰艇识别等图形图像识别领域 )中有非常广泛的应用，因此我们有必要了解下它的算法原理。  

  不同于PCA方差最大化理论， LDA算法的思想是将数据投影到低维空间之后，使得同一类数据尽可能的紧凑，不同类的数据尽可能的分散 。因此，LDA算法是一种有监督的机器学习算法。同时，LDA有如下两个假设：(1)原始数据根据样本均值进行分类。(2)不同类的数据拥有相同的协方差矩阵。当然，在实际情况中，不可能满足以上两个假设。但是 当数据主要是由均值来区分的时候，LDA一般都可以取得很好的效果 。

    （1）计算类内散度矩阵

    （2）计算类间散度矩阵

    （3）计算矩阵

    （4）对矩阵 进行特征分解，计算最大的d个最大的特征值对应的特征向量组成W。

    （5）计算投影后的数据点

以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外，还可以用于分类。 一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布 ， 这样利用LDA进行投影后，可以利用极大似然估计计算各个累呗投影数据的均值和方差，进而得到该类别高斯分布的概率密度函数 。当一个新的样本到来后，我们可以将它投影，然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数，计算它属于这个类别的概率，最大的概率对应的类别即为预测类别。LDA应用于分类现在似乎也不是那么流行。

    class sklearn.discriminant_analysis.LinearDiscriminantAnalysis(solver='svd', shrinkage=None, priors=None, n_components=None, store_covariance=False, tol=0.0001)

参数：

（1）solver: str类型，默认值为"svd"，

    svd:使用奇异值分解求解，不用计算协方差矩阵，适用于特征数量很大的情形，无法使用参数收缩(shrinkage)。

    lsqr:最小平方QR分解，可以结合shrinkage使用。

    eigen：特征值分解，可以结合shrinkage使用。

 （2）shrinkage: str or float类型，默认值为None

    是否使用参数收缩

    None:不使用参数收缩

    auto:str，使用Ledoit-Wolf lemma

    浮点数：自定义收缩比例。

   （3）components：int类型，需要保留的特征个数，小于等于n-1

属性：

（1）covariances_：每个类的协方差矩阵，shape = [n_features, n_features]

（2）means_：类均值，shape = [n_features, n_feateures]

（3）priors_：归一化的先验概率。

（4）rotations_：LDA分析得到的主轴，shape = [n_features, n_component]

（5）scalings_：数组列表，每个高斯分布的方差σ

     特点：

        降维之后的维数最多为类别数-1。所以当数据维度很高，但是类别数少的时候，算法并不适用 。LDA算法既可以用来降维，又可以用来分类。但是目前来说，主要还是用于降维。在我们 进行图像识别相关的数据分析时，LDA是一个有力的工具 。

    优点：

   （1） LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优 。

   （2）在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。

    缺点：

    （1）LDA不适合非高斯分布样本进行降维，PCA也存在这个问题。

    （2）LDA降维最多降到类别数K-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。 当然目前有一些LDA的进化版算法可以绕过这个问题 。

    （3） LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好 。

    （4）LDA可能过度拟合数据。

    二者都有 降维 的作用。

1.左 边是PCA，属于无监督方法 ，当数据没有标签时可以用它。 右边是LDA，属于监督学习方法 。考虑了数据的分类信息，这样数据在低维空间上就可以分类了，减少了很多的运算量。

2. PCA主要是从特征的协方差角度考虑，追求的是在降维之后能够最大化保持数据的内在信息 。它不考虑分类信息，因此降低维度后，信息损失降到最低，但分类上可能会变得更加困难。 LDA追求的是降维后的数据点尽可能容易被区分 。降维后的样本数据在新的维度空间有最大的类间距离和最小的类内方差，数据在低维空间有最佳的可分离性。

3. PCA降维后的维度数目是和数据维度相关的 ，原始数据是n维，那么PCA后维度为1、2~n维。 LDA后的维度数目是和类别的个数相关的 ，原始数据是n维，一共有C个类别，那么LDA后维度为1、2~C-1维。

4. PCA投影的坐标系都是正交的 。 LDA关注分类能力，不保证投影到的坐标系是正交的 。