基于LDA模型的文本分类研究

wingsun908

贡献于2015-04-07

字数:0 关键词: 机器学习

Computer Engineering and Applications计算机工程与应用2011,47(13) 1 引言 文本自动分类[1]是信息检索与数据挖掘领域的研究热点 与核心技术,近年来得到了广泛的关注和快速的发展,已经取 得了惊人的进展。它是信息检索、机器学习和自然语言处理 的热点和关键技术之一。文本自动分类的目标是从已知的文 本训练集合中找到分类规则,得到一个学习器,并且使该学习 器在对今后未知的新文本分类时,具有较好的预测精度。文 本分类系统主要包括文本表示、预处理、特征降维、分类方法 和效果评估5个部分。 在文本分类中,文本表示通常选择向量空间模型(Vector Space Model,VSM)算法,选择词作为特征项,将文档集构造 为一个高维、稀疏的词条-文本矩阵。在构造分类器之前,对于 词条-文本矩阵的降维,有利于提高分类器的效率和性能。经 常使用的特征提取的评价函数包括文档词频(Document Fre- quency,DF)、卡方(Chi-Square,CHI)、互信息(Mutual Informa- tion,MI)、信息增益(Information Gain,IG)、术语强度(Term Strength,TS)[2]等。这些方法的一个共同特点就是假定词之间 是互相独立,正交的。通过计算词项和类别之间存在的某种 特定关系对词进行筛选,从而达到降维的目的。这类方法忽 视了词的同义和多义情况,没有考虑词与词之间语义上的联系。 潜在语义索引(Latent Semantic Indexing,LSI)[3]就是一 种根据词条的共现信息探查词条之间内在的语义联系的方 法。LSI在文本分类中的应用得到了深入的研究,降维效果显 著,但在LSI模型中,对稀有类别很重要的分类特征,可能因为 在整个文档集中不重要而被滤掉,最终的分类性能往往会受 损。而且,算法实现的复杂性也是LSI模型不可忽视的一个问题。 基于此,本文提出了一种基于LDA(Latent Dirichlet Allo- cation)模型的文本分类方法。避免了文本表示方法采用VSM 方法产生的高维稀疏特征空间的问题,同时又克服了采用LSI 所带来的分类性能受损问题。在语料库上进行的分类实验表 明,是一种能有效提高文本分类性能和效率的文本分类器构 造的新方法。 2 LDA基本思想 LDA[4]对离散数据集(如文档集)建模的概率增长模型,是 一个三层贝叶斯模型,对文档进行一个简短的描述,保留本质 基于LDA模型的文本分类研究 姚全珠,宋志理,彭 程 YAO Quanzhu,SONG Zhili,PENG Cheng 西安理工大学 计算机科学与工程学院,西安 710048 School of Computer Science & Engineering,Xi’an University of Technology,Xi’an 710048,China YAO Quanzhu,SONG Zhili,PENG Cheng.Research on text categorization based on LDA.Computer Engineering and Applications,2011,47(13):150-153. Abstract:When the text corpuses are high-dimensional and large-scale,the traditional dimension reduction algorithms will ex- pose their limitations.A Chinese text categorization algorithm based on LDA is presented.In the discriminative frame of Sup- port Vector Machine(SVM),Latent Dirichlet Allocation(LDA) is used to give a generative probabilistic model for the text corpus,which reduces each document to fixed valued features——The probabilistic distribution on a set of latent topics. Gibbs sampling is used for parameter estimation.In the process of modeling the corpus,a latent topics-document matrix asso- ciated with the corpus has been constructed for training SVM.Standard method of Bayes is used for reference to get the best number of topics.Compared to Vector Space Model(VSM) for text expression combined SVM and the classifier based on Latent Semantic Indexing(LSI) combined SVM,the experimental result shows that the proposed method for text categori- zation is practicable and effective. Key words:text categorization;Latent Dirichlet Allocation(LDA);Gibbs sampling;Bayes statistics theory 摘 要:针对传统的降维算法在处理高维和大规模的文本分类时存在的局限性,提出了一种基于LDA模型的文本分类算法,在 判别模型SVM框架中,应用LDA概率增长模型,对文档集进行主题建模,在文档集的隐含主题-文本矩阵上训练SVM,构造文本 分类器。参数推理采用Gibbs抽样,将每个文本表示为固定隐含主题集上的概率分布。应用贝叶斯统计理论中的标准方法,确定 最优主题数T。在语料库上进行的分类实验表明,与文本表示采用VSM结合SVM,LSI结合SVM相比,具有较好的分类效果。 关键词:文本分类;潜在狄利克雷分配(LDA)模型;Gibbs抽样;贝叶斯统计理论 DOI:10.3778/j.issn.1002-8331.2011.13.043 文章编号:1002-8331(2011)13-0150-04 文献标识码:A 中图分类号:TP181 作者简介:姚全珠(1960—),男,博士,教授,主要研究方向为数据库,软件工程方法学,自然语言处理,机器学习;宋志理(1985—),男,硕士生; 彭程(1985—),男,硕士生。E-mail:274130384@qq.com 收稿日期:2009-08-11;修回日期:2009-10-11 150 2011,47(13) 的统计信息,有助于高效地处理大规模的文档集。 下面是LDA模型应用于文档集主题建模的符号约定: (1)词是文本数据的基本单元,是用{1,2,…,V}索引的词 表的分项。词表中的第v个词用一个V维的向量w表示,其中 对于任意 u ¹ v ,wv = 1wu = 0 。 (2)文档是 N 个词的序列,用 d ={}w1w2wn 表示,wn 是序列中的第n个词。 (3)文档集是M个文档的集合,表示成 D ={}d1d2dM。 假设有k个主题,则文档d中的第i个词汇 wi 的概率可以 表示为如下: P()wi = åj = 1 T P()wi|zi = j P()zi = j (1) 其 中 ,zi 是 潜 在 变 量 ,表 示 第 i 个 词 汇 wi 取 自 该 主 题 , P()wi|zi = j 是词汇 wi 属于主题 j 的概率,P()zi = j 给出文档 d 属于主题j的概率。第j个主题表示为词表中V个词的多项式 分布 φ j wi = P()wi|zi = j ,文本表示成K个隐含主题上的随机混合 θ d j = P()zi = j 。于是文本d中“发生”词汇w的概率为: P()w|d = åj = 1 T φ j w•θ d j (2) 通过EM(期望最大化算法)求最大似然函数: l()αβ = åi = 1 M log p()di|αβ (3) 的最大似然估计量α、β,估计α、β的参数值,从而确定 LDA 模 型。其中文本d“发生”的条件概率分布: P()d|αβ = Γ æ èç ö ø÷åi αi Õi Γ()αi æ èç ö ø÷Õi = 1 k θ αi - 1 i æ è çç ö ø ÷÷ån = 1 N åi = 1 k Õj = 1 V ()θi βij w j n dθ (4) 存在θ,β配对,无法计算出解析式,需要求出近似解。在 LDA模型中,可采用Laplace近似、变分推理(Variational Infer- ence)、Gibbs 抽样以及期望-扩散(Expectation Propagation)等 近似推理算法获取待估参数值。Thomas L.Griffiths[5]等人提 出 Gibbs 抽样在困惑度和运行速度方面均优于变分推理和期 望-扩散算法。 3 基于LDA模型的文本分类 基于 LDA 模型的文本分类方法使用 LDA 为语料库及文 本建模。将文本表示为固定主题上的概率分布,利用 MCMC 中的 Gibbs 抽样进行推理,间接计算模型参数,获取文本在主 题集上的概率分布,d ={}K1K2KT,T 为主题数。在文档 集的隐含主题-文本矩阵上训练SVM,构造文本分类系统。主 要包括预处理、模型选择、语料库建模、分类方法、效果评估 5 个部分。 待分类文本是语料库训练时没有处理过的新文本,如果 对于每一个未知文本,都将其加入语料库后重新训练,则非常 浪费时间,也没有必要。本文的做法是,只对预处理后的待分 类文本运行Gibbs抽样算法,以减少迭代次数。分类的具体步 骤如下: (1)应用贝叶斯统计理论中的标准方法,推理出有效信息 P()w|T,确定最优主题数T,使模型对于语料库数据中的有效 信息拟合最佳。 (2)采用LDA模型对语料库进行主题建模,参数推理采用 Gibbs 抽样,迭代足够多的次数,每个文本表示固定隐含主题 集上的概率分布。得到文档集的隐含主题-文本矩阵 At ´ d ,t 表示隐含主题集的主题数量,d表示文档数。 (3)在LDA模型建模得到的文档集的隐含主题-文本矩阵 上训练支持向量机(SVM),构造文本分类器,得到 SVM 分类 模型。 (4)将预处理后的待分类文本作为式(9)中的文本d,运行 Gibbs抽样算法,迭代较少的次数,按式(10)、式(11)计算对应 的 ϕ 和 θ 值。获得待分类文本d的隐含主题集的概率分布向量。 (5)引入SVM分类模型,预测待分类文本的类别。 3.1 模型选择 采用 LDA 模型对整个文档集进行主题建模,主题数 T 对 LDA模型拟合文档集的性能影响很大。本文采用贝叶斯统计 中标准方法予以解决。为此首先确定α,β的值,然后为T选择 合适的值。这实际上是一个模型选择的问题。在 LDA 模型 中,α 和 β 分别是 θ 和 ϕ 上的 Dirichlet 先验概率假设,其自然 共轭的特点说明通过对 θ 和 ϕ 积分可以求取联合概率 P()wz 的值。 P()wz = P()w|z P()z (5) 并且 θ 和 ϕ 分别单独出现于右式第一项和第二项。对 ϕ 积分 得到 P()w|z 值如下: P()w|z = æ è çç ö ø ÷÷ Γ()Wβ Γ()β W T åj = 1 TÕw Γ()n()w j + β Γ()n(). j + Wβ (6) 其中,Γ(). 是标准的gamma函数,n()w j 表示词汇w分配给主题 j的频数,n(). j 表示分配给主题j的所有词数。因为 P()w|T 可以 近似为一系列 P()w|z 的调和平均值。所以按下式求取其值: 1 P()w|T = 1 M åm = 1 M 1 P()w|z()m (7) 其中M为Gibbs抽样算法迭代次数。 通过式(7)以计算出采用不同主题数 T 对语料库建模的 P()w|T 值。由 P()w|T 值与模型对语料库有效信息拟合程度 成正比,确定最优主题数T。 3.2 参数估计 MCMC(Markov Chain Monte Carlo)是从一个复杂的概 率分布抽取样本值的近似迭代方法,它允许马尔可夫链(Mar- kov)收敛于目标分布,然后从 Markov 链中抽样,Markov 链的 每个状态是对于采样变量值的赋值,状态之间的转换遵循着 简单的规则。Gibbs抽样[5]作为 MCMC的一种简单实现形式, 其目的是构造收敛于某目标概率分布的Markov链,并从链中 抽样被认为接近该概率分布值的样本。于是给出目标概率分 布函数成为了采用 Gibbs 抽样的关键。采用 Gibbs 抽样,在所 有变量的当前值和文档集的基础上,从它们的分布上来抽样 所有的变量值,转换到下一状态。 采用Gibbs抽样的LDA模型完整的概率模型如下: wi|ziϕ()zi ~Discrete()ϕ()zi ϕ~Dirichlet()β zi|ϕ()di ~Discrete()θ()di (8) 姚全珠,宋志理,彭 程:基于LDA模型的文本分类研究 151 Computer Engineering and Applications计算机工程与应用2011,47(13) θ~Dirichlet()α LDA 模型为易于处理训练语料之外的新文本,便于模型 参数的推理,对θ()d 和 ϕ()z 分别作对称的Dirichlet(α)、Dirichlet(β) 先验概率假设。为了获取文本的主题概率分布,本文没有将 ϕ 和θ作为参数直接计算,而是考虑词汇w对于主题的后验概率 P()w|z ,利用Gibbs抽样间接求得 ϕ 和θ的值。对于LDA模型, 仅仅需要对主题的词汇分配,也就是变量z进行抽样。记后验 概率为:P()zi = j|z-iwi ,计算公式如下: P()z-i = j|z-iw µ n()w -ij + β n()• -ij + Wβ • n()di -ij + α ndi -i• + Tα (9) 式(9)是非标准化的概率分布,真正计算时需要除以所有词汇 主题分配的概率之和。 z-i 表示所有 zk()k ¹ i 的分配;zwi -ij 表 示词汇 wi 分配给主题j的次数;z()• -ij 表示分配给主题j的所有 词汇;n()di -ij 表示文本 di 中分配给主题j的词汇;n()di -i• 表示文本 di 中所有分配了主题的词汇。所有词汇个数都不包括此次 zi = j 的分配。 Gibbs算法详述如下: (1)zi 被初始化为1到T的某个随机整数,i取1,2,…,N, N是语料库中所有出现文本中词汇记号个数,与词汇表大小V 和词汇出现的位置相关。此为Markov链的初始状态。 (2)根据式(6)获取 Markov 链的下一状态,迭代足够多 次,直到 Markov 链接近目标分布,记录 zi 的当前值。对于每 一个单一的样本 zi ,可以按下式估算 ϕ 和 θ 的值。 ϕÙ()w j = n()w j + β n()• j + Wβ (10) θÙ()d = n()d j + α n()d • + Tα (11) n()w j 表示词汇 w 分配给主题 j 的频数,n()• j 表示分配给主题 j 的 所有词汇数,n()d j 表示文本d中分配给主题j的词汇数,n()d • 表 示文本d中所有分配主题的词汇数。 4 实验结果和分析 4.1 实验语料 采用的实验数据是复旦大学公开的一个语料库,共分9个 类别,共9 318篇文本,其中训练语料2 000篇,测试语料7 318 篇。类别分别为航空、计算机、艺术、环境、农业、经济、政治、 体育、历史。 4.2 评估方法 为了评估文本自动分类系统的性能,评估方法选择传统 的评估标准:正确率P、召回率R、F1值、宏平均正确率Macro_P、 宏平均召回率 Macro_R、宏平均 F1 值、微平均 F1 值。计算公 式如下: Pi = Ti Ci (12) Ri = Ti Ni (13) F1i = 2 ´ Pi ´ Ri Pi + Ri (14) Macro_P = 1 k åi = 1 k Pk (15) Macro_F1 = 2 ´ Macro_P ´ Macro_R Macro_P + Macro_R(16) Micro_P = åi = 1 k Ti åi = 1 k Ci (17) 其中 Ti、Ci、Ni 表示第i类的结果中正确的文本个数,结果中出 现的个数和实际包含的文本个数。由于只进行单类别分类 (一个文档只给出一个预测类别),因此微平均的P,R和F1三 者相等。 4.3 实验结果比较与分析 语料库经过中科院计算所汉语词法分析系统 ICTCLAS 进行分词,并去除停用词。 首先,通过实验研究主题数目 T 对 Gibbs 抽样算法的影 响。令 α = 50/T,β = 0.01(此为经验值,这种取值在本语料库 上有较好效果)。T取不同的值分别运行Gibbs抽样算法,检测 log P()w|T 的值的变化。实验结果如图1所示。 由图 1 可以看出,当主题数目 T 为 100 时,log P()w|T 最 大,随后急剧减少。说明 T 为 100 时,模型对于语料库数据中 的有效信息拟合最佳。因此后续实验选择T值为100。 采用 LDA 模型对整个文档集进行主题建模,迭代 1 000 次。每个文本表示为包含 100 个主题的主题集上的多项式分 布,得到文档集的隐含主题-文本矩阵 At ´ d 。在 At ´ d 上构造 SVM分类器。 文本表示选择VSM,结合中文分类中较好的MI抽取特征 项,构造 SVM 分类器的方法,作为对比实验 1。采用 LSI 对词 条-文本矩阵进行 SVD 分解,构造潜在语义矩阵,实现特征降 维,分类算法选择SVM,作为对比实验2。在LSI中,实验选取 svdlibc 进行 SVD 分解生成语义空间,考虑到 K 值过小引起有 用信息流失和K值过大存储空间的限制,K值一般在100~300, 本文中根据训练文档集,对K取不同的值进行测试,最后采用 的 K 值为 200。实验选取 libsvm 作为 SVM 训练的实验环境。 实验结果见图2和表2。 类别编号 1 2 3 4 5 6 7 8 9 类别 航空 计算机 艺术 环境 农业 经济 政治 体育 历史 文本数量 640 1 357 740 1 217 1 021 1 600 1 024 1 253 466 分布/(%) 6.87 14.56 7.94 13.06 10.96 17.17 10.99 13.45 5.00 表1 语料库中各类文本的分布表 0 20 40 60 80 100 120 140 160 180 1.55 1.60 1.65 1.70 1.75 1.80 主题数(T) log P ( w | T ) ×107 图1 logP(w|T)与T的关系图 152 2011,47(13) 通过图 2 和表 2 可以看出,基于 LDA 模型的文本文类方 法,采用Gibbs抽样进行参数推理和估计,选择SVM作为分类 算 法 。 构造的文本自动分类系统的 Macro_P、Macro_R、 Macro_F1和Micro_P平均达到91%,均高于其他两种方法,获 得了较好的分类效果。 5 结束语 基于 LDA 模型的文本分类方法采用 LDA 主题建模模型 作为文本表示方法,每个文本表示为固定隐含主题集上的概 率分布。分类算法选择支持向量机(SVM)。避免了文本表示 方法采用VSM方法产生的高维稀疏特征空间的问题,同时又 克服了采用 LSI 所带来的分类性能受损问题。一个主题数为 100 的 LDA 模型对文档集进行主题建模,将特征空间减少了 99.6%,极大地缩短了SVM训练时间,而且实验表明其分类性 能并未受损,与其他方法相比,得到了显著提高。是一种能有 效提高文本分类性能和效率的文本分类器构造的新方法。 参考文献: [1] 苏金树,张博峰,徐昕.基于机器学习的文本分类技术研究进展[J]. 软件学报,2006,17(9). [2] 伍建军,康耀红.文本分类特征降维方式的研究[J].湖南大学学报: 自然科学版,2007,25(1). [3] Deerwester S,Dumais S T A.Indexing by latent semantic analy- sis[J].Journal of the Society for Information Science,1990,41(6). [4] Blei D,Ng A,Jordan M.Latent dirichlet allocation[J].Journal of Machine Learning Research,2003,3(4/5). [5] Griffiths T L,Steyvers M.Finding scientific topics[J].PNAS, 2004,101(1). [6] Chang Chih-Chung,Lin Chih-Jen.LIBSVM:A library for sup- port vector machine[EB/OL].(2001).http://www.csie.ntu.edu.tw/ ~cjlin/libsvm. 航空 计算机 艺术 农业环境 经济 政治 体育 历史 类别 1.00 0.95 0.90 0.85 0.80 0.75 0.70 0.65 0.60 F 1 值 VSM+SVM LDA LSI+SVM 图2 三种方法的各小类F1值结果对比图 方法 VSM+SVM LSI+SVM Gibbs-LDA+SVM Macro_P 0.851 694 0.882 884 0.914 282 Macro_R 0.852 486 0.879 212 0.911 499 Macro_F1 0.852 090 0.881 044 0.912 975 Micro_F1 0.874 283 0.898 333 0.919 177 表2 三种方法的宏平均和微平均对比表 [22] Liu D,Ning P,Li R.Establishing pairwise keys in distributed sensor networks[J].ACM Trans on Inf Syst Secur,2005,8(1): 41-77. [23] Delgosha F,Fekri F.Key pre-distribution in wireless sensor net- works using multivariate polynomials[C]//2nd Ann IEEE Com- mun Society Conf on Sensor and Ad Hoc Commun Net- works-SECON’05,Santa Clara,CA,2005. [24] Liu D,Ning P.Location-based pairwise key establishments for static sensor networks[C]//Proc of the 1st ACM Workshop on Security of Ad Hoc and Sensor Networks.New York:ACM Press,2003:72-82. [25] Dini G,Savino I.S2RP:A secure and scalable rekeying proto- col for wireless sensor networks[C]//IEEE Proceedings of MASS 2006,2006. [26] Liu Fang,Cheng Xiuzhen.A self-configured key establishment scheme for large-scale sensor networks[C]//IEEE Proceedings of MASS 2006,2006. (上接82页) 5 结束语 结合盲签名和消息恢复签名,基于离散对数构造了一个 指定接收者的盲签名方案。通过对方案安全性及效率性分析 表明,该方案不仅满足恢复消息盲签名的性质,而且只有指定 的接收者才能恢复出消息,具有保密性,其效率也优于文献[2]。 参考文献: [1] Chaum D.Blind signatures for untraceable payments[C]//Advanc- es in Cryptology Crypto’82.New York,USA:Plenum Press, 1983:199-203. [2] 张学军.高效的基于身份具有消息恢复的盲签名[J].计算机工程与 应用,2008,44(32):19-21. [3] 杨晓元,梁中银,郭耀,等.一个高效的无证书盲签名方案[J].南京 邮电大学学报:自然科学版,2009,29(3):37-42. [4] 苏万力,张跃余,张晓红,等.无证书盲签名方案[J].电子科技大学 学报,2009,38(4):533-536. [5] 夏满民,谷利泽.一种新型的代理盲签名方案[J].北京邮电大学学 报,2006,29(3):48-52. [6] 李霞,杨长海.基于椭圆曲线的门限多代理盲多签名方案[J].计算 机工程,2009,35(13):169-171. [7] 成林,亢保元,王国瞻.一种部分盲签名方案[J].计算机工程,2010, 36(8):163-164. [8] Nyberg K,Rueppel R A.Message recovery for signature schemes based on the discrete logarithm problem[C]//Advances in Cryptology-Eurocrypt’94.Heidelberg Berlin:Springer,1994:175-190. (上接73页) 姚全珠,宋志理,彭 程:基于LDA模型的文本分类研究 153

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 6 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档