一种基于主题间最小平均相似度的最优LDA模型自动选择方法

摘要

本发明公开了一种基于主题间最小平均相似度的最优LDA模型自动选择方法，本方法为：在初始设定区间内改变K值，对于每一K值：将目标文档集合的主题个数初始值设为当前K值，利用LDA模型对该目标文档集合进行训练，得到K个主题‑词的概率分布向量；计算向量之间的平均相似度AC

说明书

技术领域

本发明涉及计算机科学下的自然语言处理、机器学习领域，具体为一种LDA模型最优主题个数的确定方法；由于主题个数最优直接决定LDA模型最优，所以本方法也叫最优LDA模型的一种确定方法。

背景技术

LDA(Latent Dirichlet Allocation)主题模型(Topic Model)自David Blei等在2003年提出以来(参考D.M.Blei,A.Y.Ng,and M.I.Jordan.Latent Dirichlet allocation.Journal of Machine Learning Research,3,993-1022,2003)，在文本挖掘、信息检索、计算广告、推荐系统、问答系统、知识图谱等涉及文本语义分析的领域得到了广泛应用。LDA模型是一种概率生成模型(参考赵鑫，社交媒体中用户话题兴趣建模与挖掘研究，北京大学优秀博士论文，2014)，它不再像传统的向量空间模型，仅仅把文档看成是词典空间上的表示，而是引入了主题空间的概念，从而实现了文本在主题空间上的表示。通过对主题概念的引入，该模型带来了两个好处：(1)实现了文本的低维表示,这非常有利于后续文本分类等之类的计算，避免出现“维数灾难”问题(文本由主题空间上的向量表示，向量的维数即主题空间的维度，由主题个数确定；相对常用的文本向量空间模型，这个维数通常要低得多。在向量空间模型中，文本向量维度由文本集合得到的词典空间的维数大小确定，通常远大于主题个数)；(2)挖掘出了文本集合背后隐含的语义信息，即主题，是文本语义建模一个强有力的工具。

由于LDA具有坚实的数学基础及良好的扩展性，对该模型自身的探索以及与其他方法的结合等研究，一直是自然语言处理学科、机器学习等领域的热点研究课题之一。其中关于LDA模型参数主题最优个数的确定方法，就是一个具体的研究难点。

通过文献检索，关于LDA模型最优主题个数确定方法，主要有以下几种：

(1)经验设定，在文本语义分析任务中，研究人员常常通过反复地调试主题的数目来观察实验效果的好坏，比如观察高概率的主题词汇的好坏、语义是否一致等等(参考赵鑫，社交媒体中用户话题兴趣建模与挖掘研究，北京大学优秀博士论文，2014)。经验性设定需要人参与，人为经验评判，结果不一定很准；不同人评判标准也有差异；若文档集合巨大，包含主题个数几十、上百，人工几乎无法一一进行经验判断，同时这不是一种自动化的确定方法。

(2)基于Perplexity的确定方法。针对一个文档集合，通过LDA文本建模训练后，基于计算结果，计算Perplexity值。一个较低的Perplexity值，对应着一个好的LDA模型，但最低Perplexity值的自动化确定方法目前还没有人提出。实际应用中，通常是大家根据Perplexity值--主题个数的变化曲线图，人为确定最低点，从而获得最优主题个数。

(3)基于非参数贝叶斯方法的变形扩展。比较有代表性的工作是Hierarchical Dirichlet Processes模型，它在一定程度上解决了主题模型中自动确定主题数目的问题，但是由于模型复杂，实际使用起来运行复杂度较高，代价太大(参考Teh,Y.W.；Jordan,M.I.；Beal,M.J.；Blei,D.M.(2006).Hierarchical Dirichlet Processes.Journal of the American Statistical Association.101:pp.1566–1581)。

(4)曹娟等提出了一种基于主题间最小平均相似度原理的最优LDA模型选择方法，其证明了“当主题之间平均相似度最小主题模型便最优”的结论，同时，提出了一种基于密度的最优主题个数选择算法，此算法是类比密度聚类算法DBSCAN思想提出，是一种相对较好的自动化确定方法。但由于算法思想假设、收敛条件、计算步长的确定方式等在实际应用中会有偏差，计算结果不一定准确、可靠(参考曹娟，张勇东，李锦涛，唐胜，一种基于密度的自适应最优LDA模型选择方法)。

发明内容

针对现有技术中存在的技术问题，本发明的目的在于提供一种自动确定最优主题个数方法，对比基于密度的算法，本发明提出的方法在实际应用中更直观、可靠。

本发明的技术方案为：

一种基于主题间最小平均相似度的最优LDA模型自动选择方法，其步骤包括：

1)在初始设定区间[K₀,K_MAX]内改变K值，对于选取的每一K值：将目标文档集合的主题个数初始值设为当前K值，利用LDA模型对该目标文档集合进行训练，得到K个主题-词的概率分布向量；计算该K个主题-词的概率分布向量之间的平均相似度AC_K并将其存储到全局平均相似度数组AC_Array；全局平均相似度数组AC_Array为一维数组；

2)从该全局平均相似度数组AC_Array中选取平均相似度最小值作为临时最小平均相似度；该临时最小平均相似度对应的主题个数为TEMP_Kbest；

3)在该全局平均相似度数组AC_Array中，以当前临时最小平均相似度所在位置为中心，将该中心右边的数组元素总个数记为NUM_R_TEMP_K_best，将该中心左边的数组元素总个数记为NUM_L_TEMP_K_best；

4)若NUM_R_TEMP_K_best大于N×NUM_L_TEMP_K_best，则输出主题个数K_best＝TEMP_K_best；若NUM_L_TEMP_K_best大于NUM_R_TEMP_K_best，则令K_MAX＝K_MAX+m，K₀＝Km，r＝r₀，重复步骤1)～4)；若NUM_L_TEMP_K_best小于NUM_R_TEMP_K_best且NUM_R_TEMP_K_best小于N×NUM_TEMP_L_K_best，则K_MAX＝N×NUM_L_TEMP_K_best，K₀＝Km，r＝r₁，重复步骤1)～4)，r₁大于r₀；

5)将主题个数K_best作为该目标文档集合的最佳主题个数，该主题个数K_best对应的LDA模型为该目标文档集合的最优LDA模型。

进一步的，根据K＝K₀+r*n改变K值，r为主题个数递增间隔数，n为正整数。

进一步的，计算该平均相似度AC_K的方法为：首先计算该K个主题-词的概率分布向量两两之间的相似度，然后计算各相似度的平均值得到该平均相似度AC_K。

进一步的，所述N取值为4。

进一步的，r₀为主题个数递增间隔的初始值；r₀＝3，K_MAX的初始值设为30，r₀＝10。

进一步的，所述m＝30。

本发明将按照LDA模型最优主题个数自动化查找问题的提出、解决思路、具体算法等几个部分进行阐述。

第一部分，LDA模型最优化主题个数自动确定问题的提出。

LDA模型在使用过程中，主题个数需要事先指定。指定不同的主题个数，LDA训练得到的数据也不一样。曹娟等已经证明，当主题之间平均相似度最小时，对应的LDA模型最优，这时便得到最优主题个数。基于这一个结论，如何设计算法，自动找到主题间最小相似度是个很有实用价值的研究课题。

下面举例说明，各文献中常用的人工确定最优主题个数的方法。针对具体的文档集合，计算并画出主题之间平均相似度随主题个数变化的趋势图，人工依据趋势图就能判定出最优主题个数。详细过程如下：首先，设定主题个数计算范围，包括设置主题个数的计算区间以及递增间隔；然后，在每个设定的主题个数下，进行相应的LDA模型训练，并计算出每个主题个数下主题之间的平均相似度。所有计算完成后，就可以画出主题之间平均相似度(纵坐标)随主题个数(横坐标)变化的趋势图，如图1至图3所示(这是在几个不同规模的数据集上做的实验)。依照变化趋势图，人工可以判断出全局平均相似度最小值的位置，随即判定出最优主题个数。

设计一个算法，将上述过程自动化，便是本发明要解决的问题。

第二部分，基于主题间最小平均相似度的最优LDA模型自动选择算法解决思路。

图1至图3只是部分实例。在不同的数据集上，平均相似度随主题个数变化的趋势图估计是各种各样的。面对一个具体的文档集合，若想得到最小平均相似度对应的主题个数，如何通过计算得到一个可参照的可靠的平均相似度随主题个数变化图成为解决问题的关键。而要解决这个问题，最关键的是确定变化图中横坐标范围(主题个数考察区间，起点和终点)和间隔(主题个数递增间隔)。本发明中，具体设计如下：

在本发明中，主题个数考察区间的起点(最小值)设置为2。起点设置过大，有可能错过最小平均相似度。

考虑主题个数计算区间的终点。LDA模型，主题个数可指定的最大值，理论上讲，不超过从本文档集合中得到的词典最大值(极端情况，一个词即表示一个主题，一个文档有多少不同的词，既有多少不同的主题)。但从目前各类文献的试验数据显示，最优的主题个数远不会达到这个值(因为通常是几十、上百个词，表示一个主题)。相反，相对于上述理论最大值，最优的主题个数，通常都是在靠近起点(最小值)端一边，所以通常大家试验中，主题个数考察方式都是从起点端(最小值)开始计算，然后按照一定间隔递增，计算到某个估算的最大值结束，这种方式能保证找到并最快地找到最佳主题个数。同时，由于寻找最佳主题个数过程中，要依据主题个数训练LDA模型，所以要考虑训练成本问题。主题个数指定数值越大，对应的LDA模型训练计算量就越大，计算时长可能会成数倍、数十倍的增长。所以，综合考虑以上因素，理想情形是，主题个数区间终点设置大小，既要保证区间包含最小平均相似度所对应的点，又要适当地多，以便能判定出后续变化趋势，保证找到的点是全局最小或者近似全局最小。本发明中，主题个数计算区间终点(最大值)，采用边判断边增加的方式进行，终点最大值按如下办法确定，以最小平均相似度所在的主题个数为中心，最大值数值是中心“右边”主题个数的5倍(中心“右边”主题个数对应的平均相似度均比中心处对应的最小平均相似度大)，本发明认为，通过这种方式，能在很大程度上刻画主题之间平均相似度随主题个数变化的趋势，能保证获得的最优主题个数是全局最优或近似全局最优，能以合理的代价最大程度地满足实际业务应用的需要。

主题个数递增间隔数的设置。为了不因间隔数的设置过大而错过全局最小平均相似度，同时又考虑计算量，本发明把初始递增间隔设置为3。

第三部分，本发明具体算法阐述，包括算法步骤，参数等。

本发明设计的LDA模型最优主题个数算法如下：

算法输入：目标文档集合，主题个数考察区间起点值K₀，终点值K_MAX，主题个数递增间隔数r。

算法输出：最优主题个数K_best，最优LDA模型获得的输出数据。

步骤：

1、令K₀＝2，同时，主题个数递增间隔r₀初始值设为3，K_MAX的初始值设为30；

2、按以下方式指定主题个数K，K＝K₀+r*n,n＝(0,1,2,……)，且K在区间内[K₀,K_MAX]，间隔数为r＝r₀；然后，循环进行以下计算步骤(2.1-2.3)，直到遍历所有的K(注：递增获得的主题个数最大值记为Km)：

2.1针对目标文档集合，设定该目标文档集合的主题个数初始值为K，利用LDA模型对该目标文档集合进行训练，每次训练完成后，得到K个主题-词的概率分布向量，每个向量用z_i表示，i＝(1，2，.....,K)，z_i＝{β_i，1，β_i，2，，…，β_i，V，}，其中，β_i，1表示向量文档集合中每个词在这个主题i下的概率值，V是由文档集合获得的词典的大小(LDA模型训练，请参考Heinrich>

2.2上述训练完成后，按照以下公式，计算模型获得的主题之间的平均相似度，记为AC_K，下标K表示主题个数为K，依次追加到一个全局平均相似度数组AC_Array中，AC_Array数组为一维数组。

首先，计算两主题之间相似度，计算公式如下：

然后，计算主题之间的平均相似度，计算公式如下：

3、计算临时最小平均相似度。对步骤2.2中的平均相似度数组AC_Array[2,K_MAX]求最小值，得到临时最小平均相似度及此时对应的主题个数TEMP_K_best。

4、在进行完步骤3后，考察算法继续运行或算法终止。

考察临时最小平均相似度(对应的主题个数TEMP_K_best)在平均相似度数组AC_Array中位置分布情况:

在数组AC_Array中，以临时最小平均相似度所在位置为“中心”，“中心”右边的数组元素总个数记为NUM_R_TEMP_K_best，“中心”左边的数组元素总个数记为NUM_L_TEMP_K_best，

(1)若NUM_L_TEMP_K_best大于NUM_R_TEMP_K_best，则令K_MAX＝K_MAX+m(本发明中m＝30)，K₀＝Km,r＝r₀转入步骤2；

(2)若NUM_L_TEMP_K_best小于NUM_R_TEMP_K_best且NUM_R_TEMP_K_best小于4×NUM_TEMP_L_K_best，则K_MAX＝4×NUM_L_TEMP_K_best,K₀＝Km，r＝10，转入步骤2。

(3)若NUM_R_TEMP_K_best大于4×NUM_L_TEMP_K_best，终止计算，并令K_best＝TEMP_K_best。

5、针对目标文档集合，输出最佳主题个数K_best；认定此主题个数(K_best)下相应的LDA模型是最优LDA模型；依据上述步骤2的计算，此LDA模型已经训练过，即可输出此LDA模型训练得到的相关数据，包括主题-词的概率分布向量、文档-主题概率分布向量(这些数据是LDA模型从目标文档集合中挖掘出的隐含语义信息)，便可用于其它计算。

本发明的有益效果

为了检验本发明提出的算法的实际效果，本算法在3个不同的数据集上进行了数据实验。实验表明(详见附图4至图6)，在无人为干扰的情况下，都能准确地自动地确定出最优主题个数。同时，画出的主体之间平均相似度随主题个数变化图，显示了变化趋势，表明找到的确实是最优个数。

附图说明

图1文档集合1-平均相似度随主题个数变化图；

图2文档集合2-平均相似度随主题个数变化图；

图3文档集合3-平均相似度随主题个数变化图；

图4文档集合1-平均相似度随主题个数变化图2(最优主题个数29)；

图5文档集合2-平均相似度随主题个数变化图2(最优主题个数131)；

图6文档集合3-平均相似度随主题个数变化图2(最优主题个数50)；

图7为本发明的方法流程图。

具体实施方式

为使本发明的上述特征和优点能更明显易懂，下文特举实施例，并配合所附图作详细说明如下。

本发明实施非常简单，只要按照算法步骤，编写程序实施即可，本发明的方法流程如图7所示，其详细算法如下：

算法输入：目标文档集合，主题个数考察区间起点值K₀，终点值K_MAX，主题个数递增间隔数r。

算法输出：最优主题个数K_best，此时获得的LDA模型的输出。

步骤：

1、令K₀＝2，同时，主题个数递增间隔r₀初始值设为3，K_MAX的初始值设为30；

2、按以下方式指定主题个数K，K＝K₀+r*n,n＝(0,1,2,……)，且K在区间内[K₀,K_MAX]，间隔数为r＝r₀；然后，循环进行以下计算步骤(2.1-2.3)，直到遍历所有的K(注：递增获得的主题个数最大值记为Km)：

2.1针对目标文档集合，设定该目标文档集合的主题个数初始值为K，利用LDA模型对该目标文档集合进行训练，每次训练完成后，得到K个主题-词的概率分布向量，每个向量用z_i表示，i＝(1，2，.....,K)，z_i＝{β_i，1，β_i，2，，…，β_i，V，}，其中，β_i，1表示向量文档集合中每个词在这个主题i下的概率值，V是由文档集合获得的词典的大小(LDA模型训练，请参考Heinrich>

2.2上述训练完成后，按照以下公式，计算模型获得的主题之间的平均相似度，记为AC_K，下标K表示主题个数为K，依次追加到一个全局平均相似度数组AC_Array中，AC_Array数组为一维数组。

首先，计算两主题之间相似度，计算公式如下：

然后，计算主题之间的平均相似度，计算公式如下：

3、计算临时最小平均相似度。对步骤2.2中的平均相似度数组AC_Array[2,K_MAX]求最小值，得到临时最小平均相似度及此时对应的主题个数TEMP_K_best。

4、在进行完步骤3后，考察算法继续运行或算法终止。

考察临时最小平均相似度(对应的主题个数TEMP_K_best)在平均相似度数组AC_Array中位置分布情况:

在数组AC_Array中，以临时最小平均相似度所在位置为“中心”，“中心”右边的数组元素总个数记为NUM_R_TEMP_K_best，“中心”左边的数组元素总个数记为NUM_L_TEMP_K_best，

(1)若NUM_L_TEMP_K_best大于NUM_R_TEMP_K_best，则令K_MAX＝K_MAX+m(本发明中m＝30)，K₀＝Km,r＝r₀转入步骤2；

(2)若NUM_L_TEMP_K_best小于NUM_R_TEMP_K_best且NUM_R_TEMP_K_best小于4×NUM_TEMP_L_K_best，则K_MAX＝4×NUM_L_TEMP_K_best,K₀＝Km，r＝10，转入步骤2。

(3)若NUM_R_TEMP_K_best大于4×NUM_L_TEMP_K_best，终止计算，并令K_best＝TEMP_K_best。

5、针对目标文档集合，输出最佳主题个数K_best；认定此主题个数(K_best)下相应的LDA模型是最优LDA模型；依据上述步骤2的计算，此LDA模型已经训练过，即可输出此LDA模型训练得到的相关数据，包括主题-词的概率分布向量、文档-主题概率分布向量(这些数据是LDA模型从目标文档集合中挖掘出的隐含语义信息)，便可用于其它计算。

以上实施仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。