论文研究-基于隐含狄利克雷分布的Single-Pass新闻聚类算法 .pdf

发布时间：2022-05-30 发布人：admin 分类：说明书资料大小：0.31M 资料格式：pdf 举报版权申诉

weixin_39840914-11582493-16359647317516740848.pdf-第1页.png

第1页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第2页.png

第2页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第3页.png

第3页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第4页.png

第4页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第5页.png

第5页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第6页.png

第6页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第7页.png

第7页 / 共12页

weixin_39840914-11582493-16359647317516740848.pdf-第8页.png

第8页 / 共12页

文本预览

中国科技论文在线基于隐含狄利克雷分布的 Single-Pass 新闻 http://www.paper.edu.cn 聚类算法冯文杰，熊翱** （北京邮电大学网络技术研究院，北京 100876）摘要：提出一种基于隐含狄利克雷分布的 Single-Pass 新闻聚类算法。首先对新闻的线索文档进行了 LDA 主题聚类，将其映射到新闻集合聚类结果上，再使用 Single-Pass 聚类算法进行增量式聚类。最后进行了仿真实验，实验结果表明，该方法可以有效提高聚类算法的性能与准确率。关键词：LDA；Single-Pass；聚类算法中图分类号：TP301 Single-Pass News Clustering Algorithm Based on Latent Dirichlet allocation FENG Wenjie, XIONG Ao 100876) (Beijing University of Posts and Telecommunications, Institute of Network Technology, Beijing Abstract: A Single-Pass news clustering algorithm based on Latent Dirichlet allocation is proposed. Firstly, by using Latent Dirichlet allocation Clustering algorithm to cluster the news clue document. Then mapping it to the news document model and use Single-Pass clustering method to complete incremental updating. Finally, the experimental results show that this method can highly enhance the performance and accuracy of clustering algorithm. Key words: LDA; Single-Pass; Clustering algorithm 0 引言在网络新闻系统的数据挖掘任务中，新闻文本进行主题聚类较为重要的任务；通过主题抽取聚类，能更好地对相关新闻数据进行分析，为新闻系统运营、内容推广提供决策依据。网络新闻主题的聚类分析算法应该具有高效、准确及易于拓展等特点。传统的聚类算法一般包含层次化聚类算法、划分式聚类算法以及基于密度的聚类算法等等。在新闻文本聚类算法领域，一般会在对新闻文本完成特征量化、文本建模后，使用这三类聚类算法进行文本聚类。这些方法很适合小规模、离线式的聚类算法系统，但是却不适宜在实际网络新闻系统中部署；因为网络新闻是实时更新，这就要求聚类算法必须具备增量式更新的能力；同时，传统的新闻文本聚类算法中的文本模型过于简单，每个词语都拥有一致的文档级别，经常发生语义混乱的问题；例如在 NBA 相关的新闻中，“邓肯”与“石佛”应该是指代一个人，后者是绰号，但这却是两个词；而在教育新闻中，“邓肯”指代的可能是美国教育部长“阿恩·邓肯”；这样一来，这些新闻之间就有可能会被错误聚类；它们指代的并不是同一个“主题”，却因为词语相同而被聚类在一起。隐含狄利克雷分布(Latent Dirichlet Allocation)主题模型[1]可以很好的解决语义不清问题，因为其引入了主题元素，文档、主题、词语构成了新闻的实际生成结果，从而提高了聚作者简介：冯文杰（1993-），男，主要研究方向：数据挖掘，移动互联网通信联系人：熊翱（1974-），男，副教授、硕导，主要研究方向：网络管理与通信软件. E-mail: xiongao@bupt.edu.cn - 1 - 5 10 15 20 25 30 35 40

45 50 55 60 65 70 http://www.paper.edu.cn 中国科技论文在线类算法的准确性。但 LDA 模型的求解依赖于吉布斯采样方法[2]，需要多轮迭代，对于大型语料库的主题聚类操作需要耗费很长的时间，由于采样统计的特性，也难以做到增量式更新。因此，针对上述问题，本章节提出了基于隐含狄利克雷分布(Latent Dirichlet Allocation) 的 Single-Pass 聚类算法，该方法充分考虑到了网络新闻主题的特点，引入了网络新闻生产系统中的新闻线索数据，根据时序策略调整了聚类算法，改进了对新闻隐语义识别、算法增量式拓展的能力。 1 文本预处理 1.1 文本分词与停用词去除在新闻文档聚类算法之前，需要将新闻文档进行预处理。首先要进行文本分词与停用词去除；文本分词是将文本中的语句分割，提取出由词语组成的文档语料库。在中文文字分词领域，常见的分词方法有逐词遍历方法、并行分词方法、机械分词法；停用词去除是将语言中没有意义的介词、冠词及连词等虚词去除，这些词语并不会影响新闻文本本身的特性，没有文本结构化意义，应该提前去除，另外在新闻文档中，有一些常用的高频词汇也是无价值的，应当提前去除，图 1 包含了一部分低价值词汇：图 1 新闻低价值词汇 Fig. 1 News Low-Value Vocabulary 由于分词、停用词去除并非本文的研究重点，所以在此选择了由中科院计算技术研究所开发的汉语词法分析系统 ICTCLAS[3]。系统提供了多种编程语言库的实现，可以对本文的语料进行分词、实体识别、词性标注、新词识别。在中科院的测试中，该系统的中文分词精度达到了 98.45%，性能足以应付需求； 1.2 文本表示模型 VSM 经过文本预处理后，得到的是一个去除了噪声的词语集合，需要通过特定的文本表示模型来表示；根据使用的文本表示模型数学方法进行区分，可以分为三种：基于集合论的模型、基于代数论的模型、基于概率统计的模型。本文采用了最为常用的基于代数论的模型，即 VSM 空间向量模型。它是由 Salton 教授[4]提出的基于代数论的模型，随后在自然语言处理领域得到了广泛的应用；Salton 教授将其成功部署于 SMART（System for the Manipulation and Retrieval of Text）文本检索系统中，是经典和常用的文本表示方法之一。它的优点是非常简单、灵活，对文本特征的表达很好。适合用于计算文本相似度。 1.3 TF-IDF 词频特征算法在 VSM 模型中，如何确定向量特征的权值不是固定的，可以根据实际需求来选择权重计算公式；本文采用了被广泛应用的 TF-IDF 算法，此算法由 Salton[5]学者提出；Salton 认为文档中特征项的权重由两点决定：首先，在一个文档中，某个特征项出现的次数决定了此特征项的重要程度，出现的越多说明特征项很可能是主题词汇。其次，对于整个文档数据集， - 2 -

75 80 85 90 95 中国科技论文在线 http://www.paper.edu.cn 要统计这个特征项在多少个文档数据集中出现过，出现的数量少，说明特征项区分度高，非常稀有，在其出现的文档中，这些特征项的重要性很高。根据这个思想，就要综合考虑“词频”（TF）和“逆文档频率”（IDF）的影响，TF 说明了词的出现频率，IDF 说明了词语在文档中的常见程度。数学说明如下：对于给定的文档集合 n ，使用 in 来表示第 i 篇文档。给定一个词库集合 w ，假设要统计某个词语在文档 in 的词频，那么可以按照以下公式来计算： N n 1={ , , }i }j , W w 1={ , S w S jwS 代表词语 jw 在文档 in 中出现的次数， inS 代表文档 in 的总词语数量。计算逆文档频率的公式为： TF w  n i j j IDF w j  log      N   1  C n i 那么 TF-IDF 值为：则文档 in 的 VSM 模型表示中，某特征项 jw 的权重可以表示为： TFIDF w IDF w IDF w TF w TF w w     j j j j j j (1) (2) (3) (4) 由于新闻标题中的词语更能体现新闻报道的核心内容，所以考虑新闻文档中的标题词语权重应当更高，可以将词频统计公式 1 进行修改： aT w S w (5) TF w j  j  S n i j 在修正的公式中， jwS 仍然表示 jw 在文档中的出现次数， jwT 表示 jw 在文章标题中出现的次数。修正的公式认为出现在标题中的词语重要性更强，所以对此词频乘上一个加权系数 a ，根据多次实验，将这个加权参数设定为 3 时能比较好地反应标题的重要性，本文也选取这个参数作为加权值。 2 新闻聚类算法 2.1 隐含狄利克雷分布主题模型与求解方法 2.1.1 LDA 主题模型 100 105 隐含狄利克雷分布主题模型（以下简称 LDA）是一种典型的词袋模型，即其先不考虑新闻文档的组成结果，而是先考虑如何通过词袋来生成一篇文章；首先它认为一篇文章是由一组词语构成的集合，词语与词语之间没有顺序及先后的关系，因此主题模型更加简单；一篇文章可以包含很多个主题，而文档中的每一个词都由其中的一个主题来生成；在 LDA 模型中，一篇文章的生成步骤如下： 1．从狄利克雷分布中采样，即可生成并确定文档 i 的主题分布 i 2．根据步骤 1 中得到的主题分布 i，对其进行采样，并输出文档 i 中的词语 j 的所属 - 3 -

中国科技论文在线主题簇 ,i jZ http://www.paper.edu.cn 3．对狄利克雷分布中采样，生成某个主题 ,i 4．最后从词语的多项式分布 , LDA 的生成模型可以由下图的贝叶斯网络结构描述，其中和均为狄利克雷分布中 jZ 代表某个特定的主题聚类，即文档 i 所属的聚类簇。中采样生成最终的词语 ,i jZ 的词语分布 )i jZ ( jw 的超参数； i是主题的聚类簇分布， ,i jw 是文档 i 中的第 j 个词。 ,i 110 图 2 隐含狄利克雷分布主题模型贝叶斯网络结构 Fig. 2 LDA Model Bayesian network structure 115 因此，整个模型中的所有可见变量以及隐藏变量的联合概率分布是： (  w z , i i , )    , , | i N   j 1  (       ) ( ( ) ( ) ( | | | | w i , j i z i , j i Z i , j )) (6) 最后，为了得到新闻文档的词语分布的最大似然估计，先对公式 6 中的 i、 , )i jZ ( 进行积分，再对 ,i jZ 求和，得到以下公式：    )   w i ( , |   i z i (  w z , i i , )    , , | i (7) 120 最后根据吉布斯采样算法即可以求解模型。 2.1.2 吉布斯采样求解 LDA 主题模型 125 130 使用采用吉布斯采样是求解 LDA 模型常用的选择；其具体过程如下： 1．遍历文章词库中的所有词语，为其随机分配一个主题类。以概率分布的方式解释，， k 代表主题，其满足多项分布； K 为主题的个数。而 m表 k Mult K (1 )  ~ m nZ 即 , 示第 m篇文章， n 表示文章中的第 n 个词。 2．使用这些符号定义： k mn 表示在文档 m中 k 主题簇所属词语出现的次数； kn 表示 k 主 kn 表示在题簇中所属的词语数量； mn 表示在 m文档中的词语所属主题簇数量之和； t k 主题对应的 t 词出现的次数。对 k mn , mn , 3．然后对以下的操作进行重复迭代运算。 4．遍历语料库中的所有词语语料，若已经将当前文档 m的 t 词归入主题簇 k 中。则将 kn 均减去 1，即先取出当前的词语，根据 LDA 中主题概率公式 8，重新 kn 进行统计，完成初始化。 mn , mn , k kn , t kn , t - 4 -

中国科技论文在线 http://www.paper.edu.cn 采样得到词语所属聚类簇，在对应的 k 即此概率分布： mn , mn , kn , t kn 上分别加上 1。 (  z i  k z w ) , | i   ( n t k , i    t )  ( n k m i  ,   k ) ( V  t 1  ( n t k ,  i   t )) (8) 5．在吉布斯采样器迭代完成后，根据计算得到概率分布，使用公式 9 即可计算主题- 词语矩阵，这个矩阵描述了主题与语料库中词语的关系。根据公式 10，可以计算新闻文档-主题矩阵，这个矩阵确定了最有可能的主题分布。也就完成了实际的新闻文档主题聚类过程。 n ( t   k n ( k m      t  k ) ( ) ( n k n m    t  k ) ) (9) (10) 吉布斯采样求解方法对语料的输入规模较为敏感，算法复杂度较高；为了得到稳定的概率分布，需要进行多次的迭代轮数，而且因为采样统计推断、采样分配无序的特性，故而 LDA 主题聚类模型不适合增量式更新，同时也不利于并行化实现，很难通过分布式架构解决这一问题。 2.2 Single-Pass 新闻聚类算法 Single-Pass 是一种典型的层次聚类算法，由 Papka R 等学者[6]于 1998 年提出。主要用于新主题发现、文章聚类等领域。其核心算法思想是流式数据聚类；给定按照时间次序到来的新闻数据流，该算法按顺序处理一次新输入的流式数据；根据当前数据集与已生成的聚类簇进行比较；如果按照一定规则与阈值寻找到了确定的近似簇，则将新数据归入此类簇中；如果没有合适的归入类簇，则将这个新数据作为一个新类；如此反复执行，知道完成所有的数据聚类任务。整个过程中，只对数据进行一次读取操作，所以称为单次（Single）。下图给出了 Single-Pass 聚类算法对流数据处理的过程。图 3 Single-Pass 流程 Fig. 3 Single-Pass Process Single-Pass 聚类算法开销小，对于每一个输入数据，只读入了一次，由于其时序的特性很适合应用于网络新闻系统；但由于对输入顺序敏感，所以如果入库较早的新闻数据噪声大、新闻本身质量低，就会造成聚类效果不理想；而且由于其依赖于 VSM 模型文本建模，因此仍然会有语义不清问题。 - 5 - 135 140 145 150 155 160

中国科技论文在线 3 基于隐含狄利克雷分布改进的 Single-Pass 聚类算法 http://www.paper.edu.cn 3.1 算法设计针对隐含狄利克雷分布主题模型聚类算法与 Single-Pass 聚类算法有着各自的优势与不足，在推广到实际的网络新闻系统中时，都不适合作为单独的数据挖掘工具。为了设计一种适合于网络新闻系统的新闻聚类算法，应当明确网络新闻系统中新闻主题聚类算法的大体需求。首先，网络新闻系统中的新闻文本具有时序特性，所以在考虑增量式更新时，必须充分考虑顺序输入的特点，以保证网络新闻系统聚类算法的可拓展性。其次，在网络新闻生产系统中，有很多隐含的信息备份废弃了，例如新闻文档的采编、线索信息文档，这些概要性的文档结构很简洁，但又包含了大部分的新闻主要信息，一般在新闻生产过程中都要依据这些信息来生产实际新闻；但在众多的新闻聚类算法中，这些数据信息都没有得到合理利用了，所以应当加以利用。尤其是字数短但总结性很强的概要性文档，非常适合用于 LDA 主题模型聚类算法，在这种情况下，LDA 主题模型聚类算法的时间复杂度将会大幅度降低，同时也能生成合理的聚类结果。因此本文提出了一种基于隐含狄利克雷分布的 Single-Pass 聚类算法，它可以预先进行离线部署，对每篇新闻文档所属的线索采编文档生成一个新的文档库，首先对线索采编文档库进行 LDA 主题模型聚类算法，通过设定迭代次数的吉布森采样方法，对文档所属聚类簇进行多次采样，得到基于新闻线索语料的聚类结果，将其映射到网络新闻的原文档，形成新闻文档的聚类结果集合。根据这个聚类集合，对于后续生产的新闻，直接采取 Single-Pass 增量式聚类算法，将新生产新闻与当前聚类簇的主题向量计算相似度，同时改进新闻聚类簇中的主题向量计算公式，即可以使用新闻热度来计算每个聚类簇的主题向量；最后确定其所属聚类簇。 3.2 数据模型（1）新闻文档信息集合与新闻线索信息集合，表示新闻系统中的新闻集合与其对应的新 c 来 n 来表示 i 条新闻的集合，用集合 C c 1={ , , }i , }i N n 1={ , 闻线索文档集合，用集合表示这 i 个新闻的线索文档。（2）分词后的线索文档语料库，记为 CW 。（3）使用向量空间模型与 TF-IDF 词频统计算法对集合 N 中的新闻文档进行文档模型处理，对于集合 N n 1={ , n ，新闻文本 in 可以表示为： , }i n =( i in , i 2 （4）每次输出的新闻主题聚类结果集合 i 1 , t w t w , , , (11) i i 1 q ，每个聚类簇都包含了算法输出后 Q q 1={ , t w ) , , }k in 2 属于该聚类簇的新闻。（5）在算法更新时刻，新加入的新闻 jp ,也通过向量空间表示： p j =( （6）新闻访问量统计集合，使用集合（7）新闻主题聚类簇质心向量，通过将每个主题簇中的全部新闻进行统计，得到这个簇 j 1 , , t w t w , j j 2 1 S s 1={ , j 2 jn jn ) t w , , , s 表示，用于计算主题。 , }i (12) - 6 - 165 170 175 180 185 190 195

中国科技论文在线 http://www.paper.edu.cn 的质心向量，使用新闻文本向量平均值来表示： Topic k  1 q k q k  n k ( k 1  s i s topic k ) (13) 200 k Topic 代表新闻主题簇 kq 的质心向量，即主题向量。 kq 则代表聚类后 s 表示聚类所 topic 公式 13 中，所得到的新闻主题簇 kq 中所属的新闻总量。 is 表示新闻阅读量，得簇中新闻的总阅读量，这两者用于改进主题向量质心选取，热度越高的新闻应该提供更高的权重。 kn 表示归属于主题簇 kq 中的新闻 kn 的文档向量。 k （8）新闻 jp 与给定主题向量 k Topic 的相似度 ( Sim p Topic ，通过余弦距离公式来计算 ) , j k 新闻与主题向量的相似度： 205 Sim p Topic k ( , j )   w w ki i w 2 ji   w 2 ki ji i i (14) 3.3 算法步骤用流程图对算法流程描述： - 7 -

中国科技论文在线 http://www.paper.edu.cn 210 215 图 4 算法流程 Fig. 4 Algorithm process 算法步骤如下： 1．使用 ICTCLAS 分词系统，对集合 N 与集合 C 中的文档进行单独的分词，将结果保存在两个单独的新闻文档语料库 NW 与 CW 。 2．根据 CW 语料库中的语料，作为吉布斯采样器的输入，根据预先设定的主题聚类簇个数 K ，先为每个词语随机分配一个聚类簇；根据公式 8 中的转移概率，计算每个词语的新聚类簇分布概率，再与均匀分布进行对比抽样，即可为词语分配新的主题聚类簇；通过多次迭代，达到稳定收敛后，即可得到最终聚类结果。此时文档-主题 - 8 -

分享到：

赞收藏

资料库

论文研究-基于隐含狄利克雷分布的Single-Pass新闻聚类算法 .pdf

相关推荐

开发技术

热门标签

最新资料