K-means

1 聚类是一种无监督的学习方法。聚类区别于分类，即事先不知道要寻找的内容，没有预先设定好的目标变量。

2 聚类将数据点归到多个簇中，其中相似的数据点归为同一簇，而不相似的点归为不同的簇。相似度的计算方法有很多，具体的应用选择合适的相似度计算方法。

3 K-means聚类算法，是一种广泛使用的聚类算法，其中k是需要指定的参数，即需要创建的簇的数目，K-means算法中的k个簇的质心可以通过随机的方式获得，但是这些点需要位于数据范围内。在算法中，计算每个点到质心得距离，选择距离最小的质心对应的簇作为该数据点的划分，然后再基于该分配过程后更新簇的质心。重复上述过程，直至各个簇的质心不再变化为止。

4 K-means算法虽然有效，但是容易受到初始簇质心的情况而影响，有可能陷入局部最优解。为了解决这个问题，可以使用另外一种称为二分K-means的聚类算法。二分K-means算法首先将所有数据点分为一个簇；然后使用K-means（k=2）对其进行划分；下一次迭代时，选择使得SSE下降程度最大的簇进行划分；重复该过程，直至簇的个数达到指定的数目为止。实验表明，二分K-means算法的聚类效果要好于普通的K-means聚类算法。

_____________________________________________________________

LDA

概率论中两大学派：

频率学派和贝叶斯学派。先验概率，后验概率，共轭分布和共轭先验是贝叶斯学派中的几个概念。原因是贝叶斯学派认为分布存在先验分布和后验分布的不同，而频率学派则认为一个事件的概率只有一个。

基本概率分布：

先验分布（prior probability），后验分布（posterior probability），似然函数（likelyhood function）,共轭分布(conjugacy)

共轭分布(conjugacy)：后验概率分布函数与先验概率分布函数具有相同形式

采用共轭先验的原因：

可以使得先验分布和后验分布的形式相同，这样一方面合符人的直观（它们应该是相同形式的）另外一方面是可以形成一个先验链，即现在的后验分布可以作为下一次计算的先验分布，如果形式相同，就可以形成一个链条。

为了使得先验分布和后验分布的形式相同，我们定义：

如果先验分布和似然函数可以使得先验分布和后验分布（posterior distributions）有相同的形式，那么就称先验分布与似然函数是共轭的。所以，共轭是指的先验分布(prior probability distribution)和似然函数(likelihood function)。如果某个随机变量Θ的后验概率 p(θ|x)和气先验概率p(θ)属于同一个分布簇的，那么称p(θ|x)和p(θ)为共轭分布，同时，也称p(θ)为似然函数p(x|θ)的共轭先验。

参数估计：

离散型随机变量分布：二项式分布，多项式分布；

连续型随机变量分布：正态分布。

他们都可以看作是参数分布，因为他们的函数形式都被一小部分的参数控制，比如正态分布的均值和方差，二项式分布事件发生的概率等。因此，给定一堆观测数据集（假定数据满足独立同分布），我们需要有一个解决方案来确定这些参数值的大小，以便能够利用分布模型来做密度估计。这就是参数估计。

从两个学派角度考虑参数估计：

频率学派：通过某些优化准则（比如似然函数）来选择特定参数值；

贝叶斯学派：假定参数服从一个先验分布，通过观测到的数据，使用贝叶斯理论计算对应的后验分布。

先验和后验的选择满足共轭，这些分布都是指数簇分布的例子。

PCA降维

PCA的思想其实简单的概括就是：选取包含信息量最多的方向对数据进行投影，其投影方向可以从最大化方差或者最小化投影误差两个角度来理解。方差大说明包含的信息量大。 所以PCA的思想就是通过最大化方差来找到合适的投影方向。

小结：

PCA，主成分分析，何为主成分？其实可以理解成一个个投影方向。而PCA要做的就是找到一个合适的投影方向，把原有的高维空间的数据映射到一个低维的空间，从而实现降维。

那么这个方向如何寻找的，标准是什么呢？PCA希望投影后的数据有尽可能大的方差。有了这个目标之后，我们就可以开始用数学语言取描述，后面如何求解这个优化的目标呢？拉格朗日乘子法，最后会发现把问题转成求特征值和特征向量的问题，得到这些投影方向后，自然降维的事情也就水到渠成了。

SVD与PCA关系：对数据集X做SVD就可以直接得到PCA的结果Y。SVD其实可以用来求PCA，当然SVD 在机器学习中用于推荐系统的作用也为大家所熟知。

—————————————————————————————

NLP知识梳理：

—————————————————————————————

文本挖掘的分词原理：

现代分词都是基于统计的分词，而统计的样本内容来自于一些标准的语料库。一句话要分词，我们要求的是概率最大分词结果，这里涉及到所有词的联合概率分布，以及简化版的马尔科夫假设；利用语料库建立的统计概率，对于一个新的句子，我们就可以通过计算各种分词方法对应的联合分布概率，找到最大概率对应的分词方法，即为最优分词。

N元模型，实际中N一般取4，即当前词依赖前4个词；

某些生僻词，或者相邻分词联合分布在语料库中没有，概率为0。这种情况我们一般会使用拉普拉斯平滑，即给它一个较小的概率值；

维特比算法与分词

对于一个有很多分词可能的长句子，我们当然可以用暴力方法去计算出所有的分词可能的概率，再找出最优分词方法。但是用维特比算法可以大大简化求出最优分词的时间。

大家一般知道维特比算法是用于隐式马尔科夫模型HMM解码算法的，但是它是一个通用的求序列最短路径的方法，不光可以用于HMM，也可以用于其他的序列最短路径算法，比如最优分词。

维特比算法采用的是动态规划来解决这个最优分词问题的，动态规划要求局部路径也是最优路径的一部分，很显然我们的问题是成立的。

—————————————————————————————

 

文本挖掘预处理之向量化与Hash Trick

词袋模型

总结下词袋模型的三部曲：分词（tokenizing），统计修订词特征值（counting）与标准化（normalizing）。

与词袋模型非常类似的一个模型是词集模型(Set of Words,简称SoW)，和词袋模型唯一的不同是它仅仅考虑词是否在文本中出现，而不考虑词频。词袋模型有很大的局限性，因为它仅仅考虑了词频，没有考虑上下文的关系，因此会丢失一部分文本的语义。但是大多数时候，如果我们的目的是分类聚类，则词袋模型表现的很好。

Hash Trick

向量化的方法很好用，也很直接，但是在有些场景下很难使用，比如分词后的词汇表非常大，达到100万+，此时如果我们直接使用向量化的方法，将对应的样本对应特征矩阵载入内存，有可能将内存撑爆，在这种情况下我们怎么办呢？第一反应是我们要进行特征的降维，说的没错！而Hash Trick就是非常常用的文本特征降维方法。

和PCA类似，Hash Trick降维后的特征我们已经不知道它代表的特征名字和意义。此时我们不能像上一节向量化时候可以知道每一列的意义，所以Hash Trick的解释性不强。

一般来说，只要词汇表的特征不至于太大，大到内存不够用，肯定是使用一般意义的向量化比较好。因为向量化的方法解释性很强，我们知道每一维特征对应哪一个词，进而我们还可以使用TF-IDF对各个词特征的权重修改，进一步完善特征的表示。

而Hash Trick用大规模机器学习上，此时我们的词汇量极大，使用向量化方法内存不够用，而使用Hash Trick降维速度很快，降维后的特征仍然可以帮我们完成后续的分类和聚类工作。当然由于分布式计算框架的存在，其实一般我们不会出现内存不够的情况。因此，实际工作中我使用的都是特征向量化。

—————————————————————————————

文本挖掘预处理之TF-IDF

TF-IDF是非常常用的文本挖掘预处理基本步骤，但是如果预处理中使用了Hash Trick，则一般就无法使用TF-IDF了，因为Hash Trick后我们已经无法得到哈希后的各特征的IDF的值。使用了IF-IDF并标准化以后，我们就可以使用各个文本的词特征向量作为文本的特征，进行分类或者聚类分析。当然TF-IDF不光可以用于文本挖掘，在信息检索等很多领域都有使用。因此值得好好的理解这个方法的思想。

—————————————————————————————

中文文本挖掘预处理流程总结

中文文本挖掘预处理特点

第一，中文文本是没有像英文的单词空格那样隔开的，因此不能直接像英文一样可以直接用最简单的空格和标点符号完成分词。所以一般我们需要用分词算法来完成分词;

第二，中文的编码不是utf8，而是unicode。这样会导致在分词的时候，和英文相比，我们要处理编码的问题。

 

中文文本挖掘预处理一：数据收集

 

第一种方法，常用的文本语料库在网上有很多，如果大家只是学习，则可以直接下载下来使用，但如果是某些特殊主题的语料库，比如“机器学习”相关的语料库，则这种方法行不通，需要我们自己用第二种方法去获取。

第二种使用爬虫的方法，开源工具有很多，通用的爬虫我一般使用beautifulsoup。但是我们我们需要某些特殊的语料数据，比如上面提到的“机器学习”相关的语料库，则需要用主题爬虫（也叫聚焦爬虫）来完成。这个我一般使用ache。 ache允许我们用关键字或者一个分类算法来过滤出我们需要的主题语料，比较强大。

 

中文文本挖掘预处理二：除去数据中非文本部分

 

这一步主要是针对我们用爬虫收集的语料数据，由于爬下来的内容中有很多html的一些标签，需要去掉。少量的非文本内容的可以直接用Python的正则表达式(re)删除, 复杂的则可以用beautifulsoup来去除。去除掉这些非文本的内容后，我们就可以进行真正的文本预处理了。

 

中文文本挖掘预处理三：处理中文编码问题

 

由于Python2不支持unicode的处理，因此我们使用Python2做中文文本预处理时需要遵循的原则是，存储数据都用utf8，读出来进行中文相关处理时，使用GBK之类的中文编码，在下面一节的分词时，我们再用例子说明这个问题。

 

中文文本挖掘预处理四：中文分词

 

常用的中文分词软件有很多，个人比较推荐结巴分词。

 

中文文本挖掘预处理五：引入停用词

 

在上面我们解析的文本中有很多无效的词，比如“着”，“和”，还有一些标点符号，这些我们不想在文本分析的时候引入，因此需要去掉，这些词就是停用词。常用的中文停用词表是1208个；

 

中文文本挖掘预处理六：特征处理

 

两种特征处理的方法，向量化与Hash Trick。而向量化是最常用的方法，因为它可以接着进行TF-IDF的特征处理。

 

中文文本挖掘预处理七：建立分析模型

 

有了每段文本的TF-IDF的特征向量，我们就可以利用这些数据建立分类模型，或者聚类模型了，或者进行主题模型的分析。比如我们上面的两段文本，就可以是两个训练样本了。此时的分类聚类模型和之前讲的非自然语言处理的数据分析没有什么两样。因此对应的算法都可以直接使用。而主题模型是自然语言处理比较特殊的一块，这个我们后面再单独讲。

—————————————————————————————

英文文本挖掘预处理流程总结

英文文本挖掘预处理特点

英文文本的预处理方法和中文的有部分区别。首先，英文文本挖掘预处理一般可以不做分词（特殊需求除外），而中文预处理分词是必不可少的一步。第二点，大部分英文文本都是uft-8的编码，这样在大多数时候处理的时候不用考虑编码转换的问题，而中文文本处理必须要处理unicode的编码问题。第三点就是拼写问题，很多时候，我们的预处理要包括拼写检查，比如“Helo World”这样的错误，我们不能在分析的时候讲错纠错。所以需要在预处理前加以纠正。第四点就是词干提取(stemming)和词形还原(lemmatization)。这个东西主要是英文有单数，复数和各种时态，导致一个词会有不同的形式。比如“countries”和"country"，"wolf"和"wolves"，我们期望是有一个词。

 

英文文本挖掘预处理一：数据收集

一样；

英文文本挖掘预处理二：除去数据中非文本部分

一样；

 

 英文文本挖掘预处理三：拼写检查更正

 

由于英文文本中可能有拼写错误，因此一般需要进行拼写检查。拼写检查，我们一般用pyenchant类库完成。找出错误后，我们可以自己来决定是否要改正。当然，我们也可以用pyenchant中的wxSpellCheckerDialog类来用对话框的形式来交互决定是忽略，改正还是全部改正文本中的错误拼写。

 

英文文本挖掘预处理四：词干提取(stemming)和词形还原(lemmatization)

 

词干提取(stemming)和词型还原(lemmatization)是英文文本预处理的特色。两者其实有共同点，即都是要找到词的原始形式。只不过词干提取(stemming)会更加激进一点，它在寻找词干的时候可以会得到不是词的词干。比如"imaging"的词干可能得到的是"imag", 并不是一个词。而词形还原则保守一些，它一般只对能够还原成一个正确的词的词进行处理。个人比较喜欢使用词型还原而不是词干提取。

 

英文文本挖掘预处理五：转化为小写

 

由于英文单词有大小写之分，我们期望统计时像“Home”和“home”是一个词。因此一般需要将所有的词都转化为小写。这个直接用python的API就可以搞定。

英文文本挖掘预处理六：引入停用词

 

在英文文本中有很多无效的词，比如“a”，“to”，一些短词，还有一些标点符号，这些我们不想在文本分析的时候引入，因此需要去掉，这些词就是停用词。

 

英文文本挖掘预处理七：特征处理

 

现在我们就可以用scikit-learn来对我们的文本特征进行处理了，在文本挖掘预处理之向量化与Hash Trick中，我们讲到了两种特征处理的方法，向量化与Hash Trick。而向量化是最常用的方法，因为它可以接着进行TF-IDF的特征处理。在文本挖掘预处理之TF-IDF中，我们也讲到了TF-IDF特征处理的方法。TfidfVectorizer类可以帮助我们完成向量化，TF-IDF和标准化三步。

 

英文文本挖掘预处理八：建立分析模型

 

有了每段文本的TF-IDF的特征向量，我们就可以利用这些数据建立分类模型，或者聚类模型了，或者进行主题模型的分析。此时的分类聚类模型和之前讲的非自然语言处理的数据分析没有什么两样。因此对应的算法都可以直接使用。而主题模型是自然语言处理比较特殊的一块，这个我们后面再单独讲。

—————————————————————————————

文本主题模型之潜在语义索引(LSI)

文本主题模型的问题特点

在数据分析中，我们经常会进行非监督学习的聚类算法，它可以对我们的特征数据进行非监督的聚类。而主题模型也是非监督的算法，目的是得到文本按照主题的概率分布。

聚类算法关注于从样本特征的相似度方面将数据聚类。比如通过数据样本之间的欧式距离，曼哈顿距离的大小聚类等。而主题模型，顾名思义，就是对文字中隐含主题的一种建模方法。比如从“人民的名义”和“达康书记”这两个词我们很容易发现对应的文本有很大的主题相关度，但是如果通过词特征来聚类的话则很难找出，因为聚类方法不能考虑到到隐含的主题这一块。

潜在语义索引(LSI)概述

LSI是基于奇异值分解（SVD）的方法来得到文本的主题的。SVD可以这样解释：我们输入的有m个文本，每个文本有n个词。而Aij则对应第i个文本的第j个词的特征值，这里最常用的是基于预处理后的标准化TF-IDF值。这样我们通过一次SVD，就可以得到文档和主题的相关度，词和词义的相关度以及词义和主题的相关度。

LSI是最早出现的主题模型了，它的算法原理很简单，一次奇异值分解就可以得到主题模型，同时解决词义的问题，非常漂亮。但是LSI有很多不足，导致它在当前实际的主题模型中已基本不再使用。

　　　　主要的问题有：

1） SVD计算非常的耗时，尤其是我们的文本处理，词和文本数都是非常大的，对于这样的高维度矩阵做奇异值分解是非常难的。

2） 主题值的选取对结果的影响非常大，很难选择合适的k值。

3） LSI得到的不是一个概率模型，缺乏统计基础，结果难以直观的解释。

对于问题1），主题模型非负矩阵分解（NMF）可以解决矩阵分解的速度问题。对于问题2），这是老大难了，大部分主题模型的主题的个数选取一般都是凭经验的，较新的层次狄利克雷过程（HDP）可以自动选择主题个数。对于问题3），牛人们整出了pLSI(也叫pLSA)和隐含狄利克雷分布(LDA)这类基于概率分布的主题模型来替代基于矩阵分解的主题模型。

回到LSI本身，对于一些规模较小的问题，如果想快速粗粒度的找出一些主题分布的关系，则LSI是比较好的一个选择，其他时候，如果你需要使用主题模型，推荐使用LDA和HDP。

—————————————————————————————

文本主题模型之非负矩阵分解(NMF)

 非负矩阵分解(NMF)概述

非负矩阵分解(non-negative matrix factorization，以下简称NMF)是一种非常常用的矩阵分解方法，它可以适用于很多领域，比如图像特征识别，语音识别等，这里我们会主要关注于它在文本主题模型里的运用。

NMF的优化思路

NMF期望找到这样的两个矩阵W,H，使WH的矩阵乘积得到的矩阵对应的每个位置的值和原矩阵A对应位置的值相比误差尽可能的小。

NMF 用于文本主题模型

此时NMF可以这样解释：我们输入的有m个文本，n个词，而Aij对应第i个文本的第j个词的特征值，这里最常用的是基于预处理后的标准化TF-IDF值。k是我们假设的主题数，一般要比文本数少。NMF分解后，Wik对应第i个文本的和第k个主题的概率相关度，而Hkj对应第j个词和第k个主题的概率相关度。　注意到这里我们使用的是"概率相关度"，这是因为我们使用的是"非负"的矩阵分解，这样我们的W,HW,H矩阵值的大小可以用概率值的角度去看。从而可以得到文本和主题的概率分布关系。和LSI相比，我们不光得到了文本和主题的关系，还得到了直观的概率解释，同时分解速度也不错。当然NMF由于是两个矩阵，相比LSI的三矩阵，NMF不能解决词和词义的相关度问题。这是一个小小的代价。

NMF的其他应用

虽然我们是在主题模型里介绍的NMF，但实际上NMF的适用领域很广，除了我们上面说的图像处理，语音处理，还包括信号处理与医药工程等，是一个普适的方法。在这些领域使用NMF的关键在于将NMF套入一个合适的模型，使得W,HW,H矩阵都可以有明确的意义。

NMF主题模型小结

NMF作为一个漂亮的矩阵分解方法，它可以很好的用于主题模型，并且使主题的结果有基于概率分布的解释性。但是NMF以及它的变种pLSA虽然可以从概率的角度解释了主题模型，却都只能对训练样本中的文本进行主题识别，而对不在样本中的文本是无法识别其主题的。根本原因在于NMF与pLSA这类主题模型方法没有考虑主题概率分布的先验知识，比如文本中出现体育主题的概率肯定比哲学主题的概率要高，这点来源于我们的先验知识，但是无法告诉NMF主题模型。而LDA主题模型则考虑到了这一问题，目前来说，绝大多数的文本主题模型都是使用LDA以及其变体。

—————————————————————————————

 

文本主题模型之LDA(一) LDA基础

LDA贝叶斯模型

LDA是基于贝叶斯模型的，涉及到贝叶斯模型离不开“先验分布”，“数据（似然）”和"后验分布"三块。在朴素贝叶斯算法原理小结中我们也已经讲到了这套贝叶斯理论。在贝叶斯学派这里：

先验分布 + 数据（似然）= 后验分布

二项分布与Beta分布

二项分布共轭的分布其实就是Beta分布。Γ是Gamma函数，满足Γ(x)=(x−1)!

多项分布与Dirichlet 分布

多项分布和Dirichlet 分布也满足共轭关系

LDA主题模型

现在的问题是，基于这个LDA模型如何求解我们想要的每一篇文档的主题分布和每一个主题中词的分布呢？

一般有两种方法，第一种是基于Gibbs采样算法求解，第二种是基于变分推断EM算法求解。

—————————————————————————————

 

文本主题模型之LDA(二) LDA求解之Gibbs采样算法

LDA Gibbs采样算法流程总结

　　　　现在我们总结下LDA Gibbs采样算法流程。首先是训练流程：

1） 选择合适的主题数K, 选择合适的超参数向量α⃗ ,η⃗

2） 对应语料库中每一篇文档的每一个词，随机的赋予一个主题编号z

3)  重新扫描语料库，对于每一个词，利用Gibbs采样公式更新它的topic编号，并更新语料库中该词的编号。

4） 重复第3步的基于坐标轴轮换的Gibbs采样，直到Gibbs采样收敛。

5） 统计语料库中的各个文档各个词的主题，得到文档主题分布θd，统计语料库中各个主题词的分布，得到LDA的主题与词的分布βk。

 

　　　　下面我们再来看看当新文档出现时，如何统计该文档的主题。此时我们的模型已定，也就是LDA的各个主题的词分布βk已经确定，我们需要得到的是该文档的主题分布。因此在Gibbs采样时，我们的EDirichlet(βk)已经固定，只需要对前半部分EDirichlet(θd)进行采样计算即可。

　　　　现在我们总结下LDA Gibbs采样算法的预测流程：

1） 对应当前文档的每一个词，随机的赋予一个主题编号z

2)  重新扫描当前文档，对于每一个词，利用Gibbs采样公式更新它的topic编号。

3） 重复第2步的基于坐标轴轮换的Gibbs采样，直到Gibbs采样收敛。

4） 统计文档中各个词的主题，得到该文档主题分布。

 

LDA Gibbs采样算法小结 　　　

　　　　使用Gibbs采样算法训练LDA模型，我们需要先确定三个超参数K,α⃗ ,η⃗。其中选择一个合适的K尤其关键,这个值一般和我们解决问题的目的有关。如果只是简单的语义区分，则较小的K即可，如果是复杂的语义区分，则K需要较大，而且还需要足够的语料。

　　　　由于Gibbs采样可以很容易的并行化，因此也可以很方便的使用大数据平台来分布式的训练海量文档的LDA模型。以上就是LDA Gibbs采样算法。

　　　　后面我们会介绍用变分推断EM算法来求解LDA主题模型，这个方法是scikit-learn和spark MLlib都使用的LDA求解方法。

—————————————————————————————

 

文本主题模型之LDA(三) LDA求解之变分推断EM算法

变分推断EM算法求解LDA的思路

变分推断EM算法希望通过“变分推断(Variational Inference)”和EM算法来得到LDA模型的文档主题分布和主题词分布。

在EM算法的E步，由于θ,β,z的耦合，我们难以求出隐藏变量θ,β,z的条件概率分布，也难以求出对应的期望，需要“变分推断“来帮忙，这里所谓的变分推断，也就是在隐藏变量存在耦合的情况下，我们通过变分假设，即假设所有的隐藏变量都是通过各自的独立分布形成的，这样就去掉了隐藏变量之间的耦合关系。我们用各个独立分布形成的变分分布来模拟近似隐藏变量的条件分布，这样就可以顺利的使用EM算法了。

当进行若干轮的E步和M步的迭代更新之后，我们可以得到合适的近似隐藏变量分布θ,β,z和模型后验参数α,η，进而就得到了我们需要的LDA文档主题分布和主题词分布。

LDA的变分推断思路

 

　我们假设隐藏变量θ是由独立分布γ形成的，隐藏变量zz是由独立分布ϕ形成的，隐藏变量ββ是由独立分布λ形成的。这样我们得到了三个隐藏变量联合的变分分布q为：

我们的目标是用q(β,z,θ|λ,ϕ,γ)来近似的估计p(θ,β,z|w,α,η)，也就是说需要这两个分布尽可能的相似，用数学语言来描述就是希望这两个概率分布之间有尽可能小的KL距离，即：

其中D(q||p)D(q||p)即为KL散度或KL距离，对应分布q和p的交叉熵。即：

L(λ,ϕ,γ;α,η)是我们的对数似然的一个下界（第6式），所以这个L一般称为ELBO(Evidence Lower BOund)。那么这个ELBO和我们需要优化的的KL散度有什么关系呢？在(10)式中，由于对数似然部分和我们的KL散度无关，可以看做常量，因此我们希望最小化KL散度等价于最大化ELBO。那么我们的变分推断最终等价的转化为要求ELBO的最大值。现在我们开始关注于极大化ELBO并求出极值对应的变分参数λ,ϕ,γ。

 

极大化ELBO求解变分参数

我们希望最小化KL散度等价于最大化ELBO。那么我们的变分推断最终等价的转化为要求ELBO的最大值。现在我们开始关注于极大化ELBO并求出极值对应的变分参数λ,ϕ,γ。

有了ELBO的具体的关于变分参数λ,ϕ,γ的表达式，我们就可以用EM算法来迭代更新变分参数和模型参数了。

 

EM算法之E步：获取最优变分参数

有了前面变分推断得到的ELBO函数为基础，我们就可以进行EM算法了。但是和EM算法不同的是这里的E步需要在包含期望的EBLO计算最佳的变分参数。如何求解最佳的变分参数呢？通过对ELBO函数对各个变分参数λ,ϕ,γ分别求导并令偏导数为0，可以得到迭代表达式，多次迭代收敛后即为最佳变分参数。

最终我们的E步就是用（23）（24）（26）式来更新三个变分参数。当我们得到三个变分参数后，不断循环迭代更新，直到这三个变分参数收敛。当变分参数收敛后，下一步就是M步，固定变分参数，更新模型参数α,η了。

EM算法之M步：更新模型参数

由于我们在E步，已经得到了当前最佳变分参数，现在我们在M步就来固定变分参数，极大化ELBO得到最优的模型参数α,η。求解最优的模型参数α,η的方法有很多，梯度下降法，牛顿法都可以。LDA这里一般使用的是牛顿法，即通过求出ELBO对于α,ηα,η的一阶导数和二阶导数的表达式，然后迭代求解α,ηα,η在M步的最优解。

 

LDA变分推断EM算法流程总结

下面总结下LDA变分推断EM的算法的概要流程。

　　　　输入：主题数K,M个文档与对应的词。

1） 初始化α,η向量。

2）开始EM算法迭代循环直到收敛。

a) 初始化所有的ϕ,γ,λ，进行LDA的E步迭代循环,直到λ,ϕ,γ收敛。

(i) for d from 1 to M:

            for n from 1 to Nd:

                          for k from 1 to K:

　　　　　　　　　按照(23)式更新ϕnk

                                标准化ϕnk使该向量各项的和为1.

　　　　　　　　　按照(24) 式更新γk。

  (ii) for k from 1 to K:

                   for i from 1 to V:

　　　　　　　　按照(26) 式更新λki。

   (iii)如果ϕ,γ,λ均已收敛，则跳出a)步，否则回到(i)步。

b) 进行LDA的M步迭代循环， 直到α,η收敛

(i) 按照(27)(28)式用牛顿法迭代更新α,η直到收敛

c) 如果所有的参数均收敛，则算法结束，否则回到第2)步。

算法结束后，我们可以得到模型的后验参数α,η,以及我们需要的近似模型主题词分布λ,以及近似训练文档主题分布γ。

—————————————————————————————

EM算法原理总结

 

EM算法也称期望最大化（Expectation-Maximum,简称EM）算法，它是一个基础算法，是很多机器学习领域算法的基础，比如隐式马尔科夫算法（HMM）， LDA主题模型的变分推断等等。本文就对EM算法的原理做一个总结。

 

EM算法要解决的问题

我们经常会从样本观察数据中，找出样本的模型参数。 最常用的方法就是极大化模型分布的对数似然函数。

但是在一些情况下，我们得到的观察数据有未观察到的隐含数据，此时我们未知的有隐含数据和模型参数，因而无法直接用极大化对数似然函数得到模型分布的参数。怎么办呢？这就是EM算法可以派上用场的地方了。

EM算法解决这个的思路是使用启发式的迭代方法，既然我们无法直接求出模型分布参数，那么我们可以先猜想隐含数据（EM算法的E步），接着基于观察数据和猜测的隐含数据一起来极大化对数似然，求解我们的模型参数（EM算法的M步)。由于我们之前的隐藏数据是猜测的，所以此时得到的模型参数一般还不是我们想要的结果。不过没关系，我们基于当前得到的模型参数，继续猜测隐含数据（EM算法的E步），然后继续极大化对数似然，求解我们的模型参数（EM算法的M步)。以此类推，不断的迭代下去，直到模型分布参数基本无变化，算法收敛，找到合适的模型参数。

 

EM算法流程

 

EM算法的收敛性思考

1） EM算法能保证收敛吗？

2） EM算法如果收敛，那么能保证收敛到全局最大值吗？　　

首先我们来看第一个问题, EM算法的收敛性。要证明EM算法收敛，则我们需要证明我们的对数似然函数的值在迭代的过程中一直在增大。

EM算法可以保证收敛到一个稳定点，但是却不能保证收敛到全局的极大值点，因此它是局部最优的算法，当然，如果我们的优化目标L(θ,θj)L(θ,θj)是凸的，则EM算法可以保证收敛到全局最大值，这点和梯度下降法这样的迭代算法相同。至此我们也回答了上面提到的第二个问题。

 

如果我们从算法思想的角度来思考EM算法，我们可以发现我们的算法里已知的是观察数据，未知的是隐含数据和模型参数，在E步，我们所做的事情是固定模型参数的值，优化隐含数据的分布，而在M步，我们所做的事情是固定隐含数据分布，优化模型参数的值。比较下其他的机器学习算法，其实很多算法都有类似的思想。比如SMO算法（支持向量机原理(四)SMO算法原理），坐标轴下降法(Lasso回归算法： 坐标轴下降法与最小角回归法小结), 都使用了类似的思想来求解问题。

—————————————————————————————

隐马尔科夫模型HMM（一）HMM模型

隐马尔科夫模型（Hidden Markov Model，以下简称HMM）是比较经典的机器学习模型了，它在语言识别，自然语言处理，模式识别等领域得到广泛的应用。当然，随着目前深度学习的崛起，尤其是RNN，LSTM等神经网络序列模型的火热，HMM的地位有所下降。

什么样的问题需要HMM模型

使用HMM模型时我们的问题一般有这两个特征：１）我们的问题是基于序列的，比如时间序列，或者状态序列。２）我们的问题中有两类数据，一类序列数据是可以观测到的，即观测序列；而另一类数据是不能观察到的，即隐藏状态序列，简称状态序列。

有了这两个特征，那么这个问题一般可以用HMM模型来尝试解决。这样的问题在实际生活中是很多的。比如：我现在在打字写博客，我在键盘上敲出来的一系列字符就是观测序列，而我实际想写的一段话就是隐藏序列，输入法的任务就是从敲入的一系列字符尽可能的猜测我要写的一段话，并把最可能的词语放在最前面让我选择，这就可以看做一个HMM模型了。再举一个，我在和你说话，我发出的一串连续的声音就是观测序列，而我实际要表达的一段话就是状态序列，你大脑的任务，就是从这一串连续的声音中判断出我最可能要表达的话的内容。

HMM模型的定义

齐次马尔科夫链假设。即任意时刻的隐藏状态只依赖于它前一个隐藏状态，这个我们在MCMC(二)马尔科夫链中有详细讲述。当然这样假设有点极端，因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态，可能是前两个或者是前三个。但是这样假设的好处就是模型简单，便于求解。

 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。

一个HMM模型，可以由隐藏状态初始概率分布ΠΠ, 状态转移概率矩阵AA和观测状态概率矩阵BB决定。Π,AΠ,A决定状态序列，BB决定观测序列。因此，HMM模型可以由一个三元组λλ表示如下：

λ=(A,B,Π)

 

HMM观测序列的生成

HMM模型的三个基本问题

—————————————————————————————

 

回顾HMM问题一：求观测序列的概率

我们已知HMM模型的参数λ=(A,B,Π)λ=(A,B,Π)。其中AA是隐藏状态转移概率的矩阵，BB是观测状态生成概率的矩阵， ΠΠ是隐藏状态的初始概率分布。同时我们也已经得到了观测序列O={o1,o2,…oT}O={o1,o2,…oT},现在我们要求观测序列OO在模型λλ下出现的条件概率P(O|λ)P(O|λ)。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。

虽然上述方法有效，但是如果我们的隐藏状态数NN非常多的那就麻烦了，此时我们预测状态有NTNT种组合，算法的时间复杂度是O(TNT)O(TNT)阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。

用前向算法求HMM观测序列的概率

前向后向算法是前向算法和后向算法的统称，这两个算法都可以用来求HMM观测序列的概率。我们先来看看前向算法是如何求解这个问题的。

前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。从递推公式可以看出，我们的算法时间复杂度是O(TN2)O(TN2)，比暴力解法的时间复杂度O(TNT)O(TNT)少了几个数量级。

用后向算法求HMM观测序列的概率

熟悉了用前向算法求HMM观测序列的概率，现在我们再来看看怎么用后向算法求HMM观测序列的概率。

后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？

—————————————————————————————

隐马尔科夫模型HMM（三）鲍姆-韦尔奇算法求解HMM参数

略

—————————————————————————————

HMM最可能隐藏状态序列求解概述

维特比算法概述

维特比算法是一个通用的解码算法，是基于动态规划的求序列最短路径的方法。

既然是动态规划算法，那么就需要找到合适的局部状态，以及局部状态的递推公式。

维特比算法总结

如果大家看过之前写的文本挖掘的分词原理中的维特比算法，就会发现这两篇之中的维特比算法稍有不同。主要原因是在中文分词时，我们没有观察状态和隐藏状态的区别，只有一种状态。但是维特比算法的核心是定义动态规划的局部状态与局部递推公式，这一点在中文分词维特比算法和HMM的维特比算法是相同的，也是维特比算法的精华所在。

维特比算法也是寻找序列最短路径的一个通用方法，和dijkstra算法有些类似，但是dijkstra算法并没有使用动态规划，而是贪心算法。同时维特比算法仅仅局限于求序列最短路径，而dijkstra算法是通用的求最短路径的方法。

—————————————————————————————

条件随机场CRF(一)从随机场到线性链条件随机场

条件随机场(Conditional Random Fields, 以下简称CRF)是给定一组输入序列条件下另一组输出序列的条件概率分布模型，在自然语言处理中得到了广泛应用。本系列主要关注于CRF的特殊形式：线性链(Linear chain) CRF。

什么样的问题需要CRF模型

从随机场到马尔科夫随机场

从马尔科夫随机场到条件随机场

 

 

知识点：lda，lsi，svd，pca，hash_trick，plsa

https://www.cnblogs.com/zy230530/p/7029025.html

https://www.jianshu.com/p/bb7bce40a15a

https://blog.csdn.net/july_2/article/details/12710147

https://blog.csdn.net/qq_22238533/article/details/79451141

https://blog.csdn.net/qq_22238533/article/details/79460711

精读：

https://www.cnblogs.com/pinard/p/6805861.html

———————————————————————————————-

K-means

步骤：

用到以下模块：

from sklearn.cluster import KMeans

from sklearn.feature_extraction.text import TfidfTransformer # Tfidf高频无用词过滤

from sklearn.feature_extraction.text import CountVectorizer #文本特征提取方法

———————————————————————————————-

文本数据预处理：

sklearn 中 CountVectorizer、TfidfTransformer 和 TfidfVectorizer

https://blog.csdn.net/m0_37324740/article/details/79411651

当Kmeans聚类的K没有指定时，可以通过肘部法来估计聚类数量

https://blog.csdn.net/xiligey1/article/details/82457271

———————————————————————————————-

corpus_train = "./corpus_train.txt" #训练集，[文章id,paper]

cluster_docs = "./cluster_result_document.txt" #输出聚类主题文章[文章id,主题id]

cluster_keywords = "./cluster_result_keyword.txt" #输出主题关键词[主题id,关键词]

num_clusters = 7 #聚类簇个数，超参

tfidf_train,word_dict=tfidf_vector(corpus_train) #预处理训练语料、构建词典得到[(文档矩阵索引对) 得分]、[词典索引对]

———————————————————————————————-

关于得分构成，

count_v1= CountVectorizer(max_df=0.4,min_df=0.01)#向量化

counts_train = count_v1.fit_transform(corpus_train) #预处理，把文档内容处理成[(文档矩阵索引对) 词频]

tfidftransformer = TfidfTransformer()

tfidf_train = tfidftransformer.fit(counts_train).transform(counts_train) #将上面文档词频矩阵拟合归一化[(文档矩阵索引对) 得分]

———————————————————————————————-

best_kmeans(tfidf_train,word_dict) #输入[(文档矩阵索引对) 得分]、[词典索引对]，寻找最佳聚类个数，此处用的肘部法

———————————————————————————————-

关于肘部法寻找最佳参数：

def best_kmeans(tfidf_matrix,word_dict):  

import matplotlib.pyplot as plt

from matplotlib.font_manager import FontProperties

from sklearn.cluster import KMeans

from scipy.spatial.distance import cdist

import numpy as np

K = range(1, 10)

meandistortions = []

for k in K:

    print (k,'****'*5)

    kmeans = KMeans(n_clusters=k)

    kmeans.fit(tfidf_matrix)    

   meandistortions.append(sum(np.min(cdist(tfidf_matrix.toarray(), kmeans.cluster_centers_, 'euclidean'), axis=1)) / tfidf_matrix.shape[0])

plt.plot(K, meandistortions, 'bx-')

plt.grid(True)

plt.xlabel('Number of clusters')

plt.ylabel('Average within-cluster sum of squares')

plt.title('Elbow for Kmeans clustering')

plt.show()

———————————————————————————————-

start=time.time()

cluster_kmeans(tfidf_train,word_dict,cluster_docs,cluster_keywords,num_clusters)

———————————————————————————————-

关于聚类：

km = KMeans(n_clusters=num_clusters)#根据超参聚类

order_centroids = km.cluster_centers_.argsort()[:, ::-1] # 按离质心的距离排列聚类中心，由近到远

后续选择出靠近每个主题最近的前50个特征

———————————————————————————————-

end=time.time()

print("Time—>" + str(end-start))

 

 

LDA

用到以下模块：

from gensim.models import LdaModel,TfidfModel,LsiModel

from gensim import corpora

if __name__=="__main__":

    corpus_path = "./corpus_train.txt"

    cluster_keyword_lda = './cluster_keywords_lda.txt'

    cluster_keyword_lsi = './cluster_keywords_lsi.txt'

sentence_dict,dictionary,corpus,corpus_tfidf=create_data(corpus_path)

———————————————————————————————-

关于create_data()：

sentence_dict[count]=line[1] #保存文档内容

sentences.append(line[1].split(' ')) #构建语料

#对文本进行处理，得到文本集合中的词表

dictionary = corpora.Dictionary(sentences) #构造词典，变成[词,id]

#利用词表，对文本进行bow词袋模型表示

corpus = [dictionary.doc2bow(text) for text in sentences]

#利用bow，对文本进行tfidf表示

tfidf=TfidfModel(corpus)

corpus_tfidf=tfidf[corpus]#用tfidf过滤出高频无用词

return sentence_dict,dictionary,corpus,corpus_tfidf

———————————————————————————————-

lsi_model(sentence_dict,dictionary,corpus,corpus_tfidf,cluster_keyword_lsi)

———————————————————————————————-

关于lsi聚类：

lsi = LsiModel(corpus=corpus_tfidf, id2word=dictionary, num_topics=11) #设置主题个数参数，调包然后存储

———————————————————————————————-

lda_model(sentence_dict, dictionary, corpus, corpus_tfidf,cluster_keyword_lda)

———————————————————————————————-

关于lda聚类：

lda = LdaModel(corpus=corpus_tfidf, id2word=dictionary, num_topics=11)#调包训练，存储

#利用lsi模型，对文本进行向量表示，这相当于与tfidf文档向量表示进行了降维，维度大小是设定的主题数目

#这里选择53维，把所有语料都降维到53维，把稀疏的高级矩阵变成一个计算起来会比较轻松的小矩阵

#也把一些没有用的燥音给过滤掉了