精华内容
下载资源
问答
  • PCA、LDAKmeans、SVD/EVD、谱聚类之间的关系  最近在研究谱聚类时,迁移到主成分分析(PCA),发现两者有着惊人的相似之处,同时还牵扯到Kmeans、SVD,甚至LDA也有相通的地方(虽然LDA是有监督学习),因此在...

    PCA、LDA、Kmeans、SVD/EVD、谱聚类之间的关系

     最近在研究谱聚类时,迁移到主成分分析(PCA),发现两者有着惊人的相似之处,同时还牵扯到Kmeans、SVD,甚至LDA也有相通的地方(虽然LDA是有监督学习),因此在这里写一篇总结,描述一下以上各个模型之间的共通性,有助于加深对这一类无监督学习算法的理解。


    PCA与SVD/EVD的关系

      首先,从SVD入手:

    X(d×N)=UΣVTXXT=UΛUT X ( d × N ) = U Σ V T → X X T = U Λ U T

    UTXXTU=Λ U T X X T U = Λ

      然后,这是PCA的目标:

    minWs.t.WTXXTWWTW=I min W W T X X T W s . t . W T W = I

      因此PCA的实现,既可以对协方差矩阵 XXT(d×d) X X ( d × d ) T 做特征值分解,也可以直接对 X X 做奇异值分解。


    Kmeans与SVD/EVD的关系

      首先从SVD出发:

    X(d×N)=UΣVTXTX=VΛVT

    VTXTXV=Λ V T X T X V = Λ

      然后看Kmeans。Kmeans对误差的分布有要求,即要求误差服从标准正态分布,因此,Kmeans在处理非标准正态分布的数据集时,聚类效果会比较差。Kmeans聚类的每一次迭代,是根据现有的 k k 个类中心,样本根据自身与中心的距离判断类归属,然后计算出每一个类的中心进入下一次迭代。由于Kmeans的核心是基于样本与类中心的欧式距离,伊霓裳可以将Kmeans聚类的目标理解为:划分K个类 C=C1,C2,,CK C = C 1 , C 2 , ⋯ , C K ,使得各类样本到各自类中心的欧式距离之和最小。

    ===minCkiCk||xiμk||22minCkiCk(xTixi2xTiμk+μTkμk)minC(ixTixik1nki,jCkxTixj)minC(Tr(XTX)Tr(HXTXH)) min C ∑ k ∑ i ∈ C k | | x i − μ k | | 2 2 = min C ∑ k ∑ i ∈ C k ( x i T x i − 2 x i T μ k + μ k T μ k ) = min C ( ∑ i x i T x i − ∑ k 1 n k ∑ i , j ∈ C k x i T x j ) = min C ( T r ( X T X ) − T r ( H X T X H ) )

    maxHs.t.Tr(HTXTXH)HTH=IK×K ⇔ max H T r ( H T X T X H ) s . t . H T H = I K × K

      这里需要引入指示矩阵 HN×K H N × K ,它是正交矩阵:

    Hij={1Nk0xiCjxiCj H i j = { 1 N k x i ∈ C j 0 x i ∉ C j

      我们先把服从上面这个定义的指示矩阵称为“正经的”指示矩阵,因为接下来会有松弛化的。
      那么Kmeans在做的其实就是遍历所有划分,但这是一个NP hard问题,所以它选择从一个出发点(初始值)按照一种规则(要求每个样本被归到距离最近的一类中)迭代分割方案,构造出不同的 H H ,直到收敛。
      虽然Kmeans在这里推导出来的目标形式上和上面的SVD推出的表达式是一样的,但Kmeans实际上并没有做SVD。可以理解为Kmeans的解H是离散且正交的。
      另一方面,我们还可以将 XTX X T X 看做线性内积核函数计算的相似度矩阵,即将Kmeans的目标函数推广为 minTr(HTSH) min T r ( H T S H ) ,这里 S=XTX S = X T X 。而Kernel-Kmeans不使用欧式距离作为相似性测度,而是使用核函数计算相似度,即 S=ϕ(x)Tϕ(x) S = ϕ ( x ) T ϕ ( x ) ,例如高斯RBF K(xi,xj)=exp((xixj)2/2σ2) K ( x i , x j ) = e x p ( − ( x i − x j ) 2 / 2 σ 2 )


    PCA与Kmeans的关系

      如上所述,Kmeans是一个有贼心没贼胆的怂货,因为限定了 H H 的形式,所以它只能是离散取值的,于是Kmeans只能乖乖地在各种正经的指示矩阵之间跳转,直到找到最佳方案。如果再进一步,无视H的离散性,而是直接去对相似度矩阵 XTX X T X 做特征值分解,根据瑞利熵的性质,取若干最大特征值对应的特征向量拼起来就是 H H 了,只是现在算出来的H不再像“正经”定义的那样,它可能统一行里有多个取值,甚至可能取负数,但是它就是满足Kmeans最优化目标的条件。
      现在看看PCA,Kmeans和PCA有什么联系呢?PCA做了Kmeans不敢做的事情,特征值分解。根据上面的分析,当Kmeans的相似性度量取欧式距离时,对数据进行奇异值分解后的左右矩阵就有了特殊的意义: U=W U = W V=H V = H

    X=UΣVT=WΣHTH=XTWΣ X = U Σ V T = W Σ H T → H = X T W Σ

      我们来看一下PCA计算的松弛化指示矩阵 H H 有什么意义。首先,XTW可以看做是将 X X 进行一次正交变换,它将数据从原始空间变换到一个新的空间,数据在这里的投影方差最大化了。接着,XTWΣ可以看做是对变换后的数据各维度分别进行缩放,这个可以忽略不计。因此,Kmeans的簇的指示矩阵 H H (松弛化)实际上就是PCA投影之后的数据,可以说PCA实际上是在进行一种松弛化的Kmeans聚类。虽然PCA是在找正交变换,Kmeans是在划分簇类,但它们在做的几乎是同一件事情。


    Kmeans与谱聚类的关系

      谱聚类中RatioCut是对拉普拉斯矩阵L进行特征值分解(目标为 minHHTLH min H H T L H ),NCult则是对标准化过的拉普拉斯矩阵 D1/2LD1/2 D − 1 / 2 L D − 1 / 2 做特征值分解(目标为 minHHTD1/2LD1/2H min H H T D − 1 / 2 L D − 1 / 2 H ),但两个矩阵都可以看做是一种相似性矩阵。与Kmeans类似,谱聚类里的 H H 也是指示矩阵,但与Kmeans不同,谱聚类选择无视H的离散约束,对相似度矩阵(拉普拉斯矩阵)进行特征值分解,得到松弛化的 H H 。由上面的分析可知,H是原始数据 X X 映射到新空间后的结果,虽然它是松弛化的指示变量,但并不能直接用来指示聚类结果。最后还需要用H作为数据继续Kmeans聚类,得到最终结果。
      我认为谱聚类相当于Kernel Kmeans+松弛化指示矩阵,因为谱聚类的相似度矩阵使用拉普拉斯矩阵(我认为这里相似度矩阵、邻接矩阵、拉普拉斯矩阵是等价的),所以是核化的。
      谱聚类的突破有两点,首先没有限制相似性度量用欧氏距离,而是用拉普拉斯矩阵将相似度扩展为任意函数。其次,它将原问题(NP难)松弛化,用特征值分解的方式获得样本在新空间中的表达。


    谱聚类与PCA的关系

      谱聚类的流程有点像:首先将原始数据映射到一个新的空间,然后做Kmeans。我认为谱聚类的前半部分相当于Kernel PCA。Kernel PCA对核函数映射过的相似度矩阵(原本是协方差)进行特征值分解,而谱聚类对拉普拉斯矩阵(也是相似度)进行特征值分解。如果说普通PCA是将原始数据进行正交变换映射到新的空间,那么谱聚类和Kernel PCA就是对原始数据进行某种非线性变换映射到新的空间。
      很多时候对数据进行线性变换仍然无法获得良好的可分性,但引入非线性性则可能做得到,这也是核方法存在的意义,从这个角度上看谱聚类,它就是核化的PCA+Kmeans聚类。


    PCA与LDA的关系

      LDA(线性判别分析)是带label的,它是有监督学习,要求投影后同一类别的投影点尽可能接近,不同各类别的类中心之间既可能远。对于普通的二类LDA,假设有两类,类均值(中心) μj μ j ,类协方差 Covj C o v j

    μj=1NjxCjx μ j = 1 N j ∑ x ∈ C j x

    Covj=xCj(xμj)(xμj)T C o v j = ∑ x ∈ C j ( x − μ j ) ( x − μ j ) T

    于是定义定义类内散度和类间散度:

    Sw=Cov1+Cov2|Sb=(μ1μ2)(μ1μ2)T S w = C o v 1 + C o v 2 | S b = ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T

    投影后类中心间距:

    ||wTμ1wTμ2||2=wT(μ1μ2)(μ1μ2)Tw=wTSbw | | w T μ 1 − w T μ 2 | | 2 = w T ( μ 1 − μ 2 ) ( μ 1 − μ 2 ) T w = w T S b w

    投影后类内方差:

    wTCov1w+wTCov2w=wTSww w T C o v 1 w + w T C o v 2 w = w T S w w

    因此目标是:

    argmaxwJ(w)=wTSbwwTSww arg ⁡ max w J ( w ) = w T S b w w T S w w

      PCA的目标是一个瑞利熵,LDA的目标则是一个广义瑞利熵,他们的求解是类似的,都是对某个矩阵进行特征值分解,从而得到变换基。从原理上,PCA仅在最大化类间距离,但PCA中的“类”,是指每一个特征维度。


    参考资料

    PCA,Kmeans,NMF和谱聚类之间的联系
    聚类–谱聚类
    降维–主成分分析(PCA)
    线性判别分析LDA原理总结

    展开全文
  • import org.apache.spark.ml.clustering.{KMeans, LDA} import org.apache.spark.SparkConf import org.apache.spark.ml.feature.VectorAssembler import org.apache.spark.sql.SparkSession import scala.util....

    一、环境配置

    1.spark2.1.0-cdh5.7.0(自编译)

    2.cdh5.7.0

    3.scala2.11.8

    4.centos6.4

    二、环境准备

    参考https://blog.csdn.net/u010886217/article/details/90312617

    三、代码实现

    1.测试数据集iris样例

    5.1,3.5,1.4,0.2,Iris-setosa
    4.9,3.0,1.4,0.2,Iris-setosa
    4.7,3.2,1.3,0.2,Iris-setosa
    4.6,3.1,1.5,0.2,Iris-setosa
    5.0,3.6,1.4,0.2,Iris-setosa
    5.4,3.9,1.7,0.4,Iris-setosa
    4.6,3.4,1.4,0.3,Iris-setosa
    5.0,3.4,1.5,0.2,Iris-setosa
    4.4,2.9,1.4,0.2,Iris-setosa
    4.9,3.1,1.5,0.1,Iris-setosa
    5.4,3.7,1.5,0.2,Iris-setosa
    4.8,3.4,1.6,0.2,Iris-setosa
    4.8,3.0,1.4,0.1,Iris-setosa
    4.3,3.0,1.1,0.1,Iris-setosa
    5.8,4.0,1.2,0.2,Iris-setosa
    ...

    2.Kmeans算法

    package sparktest
    
    import org.apache.spark.ml.clustering.{KMeans, LDA}
    import org.apache.spark.SparkConf
    import org.apache.spark.ml.feature.VectorAssembler
    import org.apache.spark.sql.SparkSession
    
    import scala.util.Random
    
    object cluster_kmeans {
      def main(args: Array[String]): Unit = {
        val conf = new SparkConf().setMaster("local").setAppName("iris")
        val spark = SparkSession.builder().config(conf).getOrCreate()
    
        val file = spark.read.format("csv").load("iris.data")
        file.show()
    
        import spark.implicits._
        val random = new Random()
        val data = file.map(row => {
          val label = row.getString(4) match {
            case "Iris-setosa" => 0
            case "Iris-versicolor" => 1
            case "Iris-virginica" => 2
          }
    
          (row.getString(0).toDouble,
            row.getString(1).toDouble,
            row.getString(2).toDouble,
            row.getString(3).toDouble,
            label,
            random.nextDouble())
        }).toDF("_c0", "_c1", "_c2", "_c3", "label", "rand").sort("rand")
        val assembler = new VectorAssembler()
          .setInputCols(Array("_c0", "_c1", "_c2", "_c3"))
          .setOutputCol("features")
    
        val dataset = assembler.transform(data)
        val Array(train, test) = dataset.randomSplit(Array(0.8, 0.2))
        train.show()
    
        val kmeans = new KMeans().setFeaturesCol("features").setK(3).setMaxIter(20)
        val model = kmeans.fit(train)
        model.transform(train).show()
    
      }
    }
    

    3.LDA算法

    package sparktest
    
    import org.apache.spark.ml.clustering.{KMeans, LDA}
    import org.apache.spark.SparkConf
    //import org.apache.spark.ml.evaluation.ClusteringEvaluator
    import org.apache.spark.ml.feature.VectorAssembler
    import org.apache.spark.sql.SparkSession
    
    import scala.util.Random
    
    object cluster_lda {
      def main(args: Array[String]): Unit = {
        val conf = new SparkConf().setMaster("local").setAppName("iris")
        val spark = SparkSession.builder().config(conf).getOrCreate()
    
        val file = spark.read.format("csv").load("iris.data")
        file.show()
    
        import spark.implicits._
        val random = new Random()
        val data = file.map(row => {
          val label = row.getString(4) match {
            case "Iris-setosa" => 0
            case "Iris-versicolor" => 1
            case "Iris-virginica" => 2
          }
    
          (row.getString(0).toDouble,
            row.getString(1).toDouble,
            row.getString(2).toDouble,
            row.getString(3).toDouble,
            label,
            random.nextDouble())
        }).toDF("_c0", "_c1", "_c2", "_c3", "label", "rand").sort("rand")
        val assembler = new VectorAssembler()
          .setInputCols(Array("_c0", "_c1", "_c2", "_c3"))
          .setOutputCol("features")
    
        val dataset = assembler.transform(data)
        val Array(train, test) = dataset.randomSplit(Array(0.8, 0.2))
        train.show()
    
    
        val lda = new LDA().setFeaturesCol("features").setK(3).setMaxIter(40)
        val model = lda.fit(train)
        val prediction = model.transform(train)
        //prediction.show()
        val ll = model.logLikelihood(train)
        val lp = model.logPerplexity(train)
    
        // Describe topics.
        val topics = model.describeTopics(3)
        prediction.select("label","topicDistribution").show(false)
        println("The topics described by their top-weighted terms:")
        topics.show(false)
        println(s"The lower bound on the log likelihood of the entire corpus: $ll")
        println(s"The upper bound on perplexity: $lp")
      }
    }

     

     

    展开全文
  • 文本话题聚类(Kmeans/LDA

    千次阅读 2019-03-30 21:23:51
    LDA 概率论中两大学派: 频率学派贝叶斯学派。先验概率,后验概率,共轭分布共轭先验是贝叶斯学派中的几个概念。原因是贝叶斯学派认为分布存在先验分布后验分布的不同,而频率学派则认为一个事件的概率...

    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)是比较经典的机器学习模型了,它在语言识别,自然语言处理,模式识别等领域得到广泛的应用。当然,随着目前深度学习的崛起,尤其是RNNLSTM等神经网络序列模型的火热,HMM的地位有所下降。

    什么样的问题需要HMM模型

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

    有了这两个特征,那么这个问题一般可以用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维,把稀疏的高级矩阵变成一个计算起来会比较轻松的小矩阵

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

     

    展开全文
  • 网络食品安全问题话题发现的LDA-Kmeans算法
  • 其中特征提取是人脸识别中的最关键的技术,我们主要运用主成分分析(PCA)算法对图像的主成分进行分析提取,然后用每人10张人脸图像的5张作为训练样本,运用LDA算法寻找最佳的投影向量进行投影,使得类间的差异尽可能...
  • 本文目录如下:第5章 Spark ML聚类算法5.1 基于中心的聚类—Kmeans (K-均值) 聚类算法5.1.1 K-均值聚类算法主要步骤5.1.2 K-均值算法聚类效果演示5.1.3 初始化聚类中心点5.1.4 Kmeans模型参数详解5.2 LDA 主题聚类...

    第5章 Spark ML聚类算法

    • 问题描述: 假设在你的硬盘驱动器上有很多文件夹,里面存放着大量的 mp3 文件。现在,如果可以构建一个 预测模型,从而可以帮助你自动将 类似的歌曲 进行 分类,并将它们组织成你喜欢的类别,例如乡村、说唱、摇滚等。这种将 mp3 文件分配到不同组的动作,使得 mp3 文件能以 无人监督 的方式被添加到相应的播放列表中。
    • 在之前的章节中,我们假设你已经获得了 正确标记数据 的训练数据集。遗憾的是,当我们在真实世界中收集数据 (假如我们想将大量音乐分成有兴趣的播放列表) 时,我们往往无法如此奢侈。如果我们无法直接访问这些 mp3 文件的元数据,我们怎么可能将它们分成不同的组?
    • 在这里, 聚类 算法通常是解决问题的核心。
    • 简而言之,在无监督的机器学习问题中,训练数据集的正确类别往往是不可用或未知的。
    • 换言之,无监督学习算法 的主要目的是探索未标记的输入数据中的未知/隐藏模式。

    5.1 基于中心的聚类—Kmeans (K-均值) 聚类算法

    • K-均值算法 的基本思想是初始随机给定 K簇中心,按照 最邻近原则 把待分类样本点分到各个 。然后按 平均法 重新计算各个 簇的质心,从而确定新的簇心。一直迭代,直到簇心的移动距离小于某个给定的值。

    5.1.1 K-均值聚类算法主要步骤

    K-均值算法 主要分为如下几个步骤:

    • (1) 为待聚类的点寻找 聚类中心;
    • (2) 计算每个点到 聚类 中心的距离,将每个点聚类到离该点最近的 聚类 中去;
    • (3) 计算每个 聚类 中所有点的坐标平均值,并将这个平均值作为新的 聚类中心
    • (4) 反复执行(2)(3),直到 聚类中心 不再进行大范围移动或者聚类次数达到要求为止。

    5.1.2 K-均值算法聚类效果演示

    下面展示了对 n 个样本点进行 K-均值算法 聚类的效果,这里 k2
    在这里插入图片描述

    5.1.3 初始化聚类中心点

    K-均值++算法 选择初始中心点的基本思想就是: 初始的聚类中心之间的相互距离要 尽可能远。初始化过程如下:

    • (1) 从输入的数据点集合中随机选择一个点作为第一个聚类中心;
    • (2) 对于数据集中的每一个点x,计算它与最近聚类中心 (指已选择的聚类中心) 的距离 D(x);
    • (3) 选择一个新的数据点作为新的聚类中心,选择的原则是: D(x) 较大的点,被选取作为聚类中心的概率较大;
    • (4) 重复 (2)(3),直到k 个聚类中心被选出来;
    • (5) 利用这 k 个初始的聚类中心来运行标准的 K-均值算法

    从上面的算法描述可以看到,算法的关键是第 (3) 步,如何将 D(x) 反映到点被选择的概率上。一种算法如下。

    • (1) 随机从点集 D 中选择一个点作为初始的中心点。
    • (2) 计算每一个点到最近中心点的距离 Si,对所有 Si 求和得到 sum
    • (3) 然后再取一个随机值,用权重的方式计算下一个 “种子点”。取随机值random(0<random<sum),对点集 D 循环做 random - = Si 运算,直到 random <0,那么点i就是下一个中心点。
    • (4) 重复 (2)(3),直到 k 个聚类中心被选出来。
    • (5) 利用这 k 个初始的聚类中心来运行标准的 k-均值算法

    5.1.4 Kmeans模型参数详解

    在这里插入图片描述
    聚类中心点初始化方法:
    在这里插入图片描述


    5.2 LDA 主题聚类算法

    暂略…

    展开全文
  • 对鸢尾花数据集月亮数据集,分别采用线性LDA、k-meansSVM算法进行二分类可视化分析(python) 一、线性判别分析LDA 1、LDA介绍 线性判别分析(linear discriminant analysis,LDA)是对费舍尔的线性鉴别方法的归纳,...
  • 运用SURF+KMeans聚类+LDA文本主题模型实现图片自动分类
  • 可以发现,使用kmeans和BisectingKMeans,聚类结果一般是不一样的。 GMM高斯混合模型 def main(args: Array[String]): Unit = { val spark = SparkSession.builder().master("local[2]").getOrCreate() val ...
  • 整理一下学到的关于Bayes、PCA、LDAKmeans的知识。  首先说,Bayes。贝叶斯理论是根据事件发生的概率来进行估计。其实生活中我们在无意中也会用到,就是根据之前的经验,哪些事情发生的概率大,哪些事件发生的...
  • kmeans DBSCAN LDA聚类 TSNE对聚类效果进行可视化展示 对代码进行记录,方便以后使用 kmeans聚类代码 from sklearn.cluster import KMeans km_cluster = KMeans(n_clusters=3, max_iter=300, n_init=40,init='k-...
  • 基于LDA的改进K_means算法在文本聚类中的应用
  • 基于SIFT+Kmeans+LDA的图片分类器的实现源码 博文 基于SIFT+Kmeans+LDA的图片分类器的实现源码 博文
  • 不知哪日,无意中未来的同学潘潘聊到了图像处理,聊到了她的论文《基于LDA的行人检测》,出于有一年半工作经验的IT男人的本能,就一起开始学习研究这篇“论文”了。众所周知,老师给学生设置论文题目的,起初都是...
  • 目录一、线性LDA法1.LDA内涵2.处理鸢尾花数据集3.处理月亮数据集二、k-means法1.k-means内涵2.处理鸢尾花数据集3.处理月亮数据集三、SVM算法1.SVM算法内涵2.处理鸢尾花数据集3.处理月亮数据集四、浅谈SVM算法的优缺 ...
  • 本文主要在Spark平台下实现一个机器学习应用,该应用主要涉及LDA主题模型以及K-means聚类。通过本文你可以了解到: 文本挖掘的基本流程 LDA主题模型算法 K-means算法 Spark平台下LDA主题模型实现 Spark平台下基于...
  • 数据处理1.1 分词1.2 清洗2 gensim构造Dictionary、corpora以及使用TF-IDF2.1 词典创建2.2 corpus创建2.3 词袋转为TF-IDF3 创建LDA模型3.1 结果查看3.2 评估指标4.sklearn实现聚类4.1 构造特征4.2 KMeans4.3 评估...
  • 文本聚类(一)—— LDA 主题模型

    千次阅读 多人点赞 2020-09-20 16:09:07
    因工作需要,近期需要做一些文本聚类方面的事情,算法方面主要选择的是传统的机器学习算法,主要尝试的是 LDA 主题模型 K-Means 聚类算法,使用的数据集是 THUCNews 新闻文本分类数据集,其中只使用了训练集 cnews...
  • LDA(二) 文本聚类

    千次阅读 2018-12-17 14:56:33
    一、算法原理:使用Kmeans...2. 构造词典,corpus_tfidf, 最后构造 corpus_lda 3. Kmeans聚类,pred 是对语料的聚类结果列表。 pred = kmean.predict(tfidf_vec) #!/usr/bin/python # -*- coding:utf8 -*- ...
  • 针对目前国内的英语作文辅助批阅系统缺少准确而高效的跑题检测算法的问题,提出了一种结合LDA和word2vec的跑题检测算法。该算法利用LDA模型对文档建模并通过word2vec对文档进行训练,利用得到的文档主题词语之间的...
  • 这是《Python数据挖掘课程》系列文章,前面很多文章都讲解了数据挖掘、机器学习,这篇文章主要讲解LDA和pyLDAvis算法,同时讲解如何读取CSV文本内容进行主题挖掘及可视化展示。文章比较基础,希望对你有所帮助,提供...
  • 基于SIFT+Kmeans+LDA的图片分类器的实现源码 博文参考:http://www.cnblogs.com/freedomshe/archive/2012/04/24/2468747.html-The pictures classifier based on SIFT, Kmeans and LDA. Blog Reference: ...
  • 本文主要在Spark平台下实现一个机器学习应用,该应用主要涉及LDA主题模型以及K-means聚类。通过本文你可以了解到:文本挖掘的基本流程LDA主题模型算法K-means算法Spark平台下LDA主题模型实现Spark平台下基于LDA的K-...
  • bert2vec+kmeans

    2019-08-20 16:34:04
    from bert_serving....from sklearn.cluster import KMeans #ivy_nie bc = BertClient() def wordsCluster(text, vectorSize, classCount): ‘’’ text:输入文本的本地路径 vectorSize:词向量大小 classCount:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,386
精华内容 954
关键字:

lda和kmeans