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

所需积分/C币:17 2019-08-20 06:40:32 319KB .PDF

基于隐含狄利克雷分布的Single-Pass新闻聚类算法,冯文杰,熊翱,提出一种基于隐含狄利克雷分布的Single-Pass新闻聚类算法。首先对新闻的线索文档进行了LDA主题聚类,将其映射到新闻集合聚类结果上,�
山国武技论文在线 要统计这个特祉项在多少个文档数据集中岀现过,出现的数量少,说明特征项区分度高,非 常稀有,在其出现的文档中,这些特征项的重要性很髙。 根据这个思想,就要综合考虑词频()和逆文档频率()的影响,说明了 词的出现频率,说明了词语在文档中的常见程度。数学说明如下: 对于给定的文档集合 ,使用来表示第篇文档。给定一个词库集合 假设要统计某个词语在文档的词频,那么可以按照以下公式来计算: 代表词语在文档中出现的次数,代表文档的总词语数量 计算逆文档频率的公式为 那么 值为: 则文档的模型衣示中,某特征项的权重可以衣示为: 由于新闻标题中的词语更能体现新闻报道的核心内容,所以考虑新闻文档中的标题词语 权重应当更高,可以将词频统计公式进行修改: 在修正的公式中,仍然表小在文档中的出现次数,表小在文章标题中出现 的次数。修正的公式认为出现在标题中的词语重要性更强,所以对此词频乘上一个加权系数 ,根据多次实验,将这个加权参数设定为吋能比较好地反应标题的重要性,本文也选取 这个参数作为加杖值。 新闻聚类算法 隐含狄利克雷分布主题模型与求解方法 主题模型 隐含狄利克雷分布主题模型(以下简称)是一种典型的词袋模型,即其先不考虑 新闻文档的组成结果,而是先考虑如何通过词袋来生成一篇文章;首先它认为一篇文章是由 组词语构成的集合,词语与词语之间没有顺序及先后的关系,因此主题模型更加简单 篇文章可以包含很多个主题,而文档中的每一个词都由其中的一个主题来生成;在模 型中,一篇文章的生成步骤如下 从狄利克雷分布α中采样,即可生成并确定文档的主题分布b 根据步骤中得到的主题分布O,对其进行采样,并输出文档中的词语的所属 山国武技论文在线 主题簇 对狄利克雷分布中采样,生成某个主题的词语分布 最后从词语的多项式分布的中采样成最终的词语 的生成模型可以由下图的贝叶斯网络结构描述,其中和B均为狄利克雷分布中 的超参数;O是主题的聚类簇分布,代表某个特定的主题聚类,即文档所属的聚类簇 是文档中的第个词。 K Z H+W 图隐含狄利克雷分布主题模型贝叶斯K终结构 因此,整个模型中的所有可见变量以及隐藏变量的联合概率分布是: 0aB=∏eap6pp 最后,为了得到新闻文档的词语分布的最大似然估计,先对公式中的日、p进 行积分,再对求和,得到以下公式: B=∫>0aB 最后根据吉布斯采样算法即可以求解模型 吉布斯采样求解主题模型 使用采用吉布斯采样是求解模型常用的选择;其具体过稈如下 遍历文章词厍中的所有词语,为其随机分配一个主题关。以概率分布的方式解释, 代表主题,其满足多项分布;为主题的个数。而表 示第篇文章,表示文章中的第个词。 使用这些符号定义:表示在文档中主题簇所属词语出现的次数;表示主 题簇中所属的词语数量:表示在文档中的词语所属主题簇数量之和;表示在 主题对应的词出现的次数。对 进行统计,完戊初始化。 然后对以下的操作进行重复迭代运算。 遍历语料库中的所有词语语料,若己经将当前文档的词归入主题簇中。则将 均减去,即先取出当前的词语,根据 中主题概率公式,重新 山国武技论文在线 采样得到词语所属聚类簇,在对应的 上分别加上。 即此概率分布: +B ∑+B 在吉布斯釆样器迭代完成后,根据计算得到概率分布,使用公式即可计算主题 词语矩阵φ,这个矩阵描述了主题与语料库中词语的关系。根据公式,叮以计算 新闻文档主题矩阵θ,这个矩阵确定了最有可能的主题分布。也就亢成了实际的新 闻文档主题聚类过程。 d=+/+ 日 吉布斯采样求解方法对语料的输入规模较为敏感,算法复杂度较晑;为了得到稳定的概 率分布,需要进行多次的迭代纶数,而且因为采样统计推断、采样分配无序的特性,故而 主题聚类模型不适合增量式更新,同时也不利于并行化实现,很难通过分布式架构解 决这一问题。 新闻聚类算法 是一种典型的层次聚类算法,由 等学者于年提出。主要用于 新主题发现、文章聚类等领域。其核心算法思想是流式数据聚类:给定按照时间次序到来的 新闻数据流,该算法按顺序处理一次新输入的流式数据;根据当前数据集与已生成的聚类簇 进行比较;如果按照一定规则与阈值寻找到了确定的近似簇,则将新数据归入此类簇中;如 果没有合适的归入类簇,则将这个新数据作为一个新类;如此反复执行,知道完成所有的数 据聚类仼务。整个过程中,只对数据进行·次读取操作,所以称为单次( 。下图给 聚类算法对流数据处理的过程。 B聚类簇 A类簇 时间序列 B A A 图 流程 聚类算法开销小,对于每一个输入数据,只读入了一次,由于其时序的特性 很适合应用于网络新闻系统;但由于对输入顺序敏感,所以如果入库较早的新闻数据噪声大、 新闻本身质量低,就会造成聚类效果不埋想;而且由于其依赖于模型文本建模,因此 仍然会有语义不清问题。 山国武技论文在线 基于隐含狄利克雷分布改进的 聚类算法 算法设计 针对隐含狄利克雷分布主题模型聚类算法与 聚类算法有着各自的优势与不 足,在推广到实际的网络新闻系统中时,都不适合作为单独的数据挖掘工具。为了设计一种 适合于K络新闻系统的新闻聚类算法,应当明确网络新闻系统中新闻主题聚类算法的大体需 求 首先,网络新闻系统中的新闻文木具有时序特性,所以在考虑增量式更新时,必须充分 考虑顺序输入的特点,以保证网络新闻系统聚类算法的可拓展性 其次,在网络新闰生产系统中,有很多隐含的信息备份废弃了,例如新闻文档的采编、 线索信息文档,这些概要性的文档结构很简洁,但又包含了大部分的新闻主要信息,一般在 新闻生产过程中都要依据这些信息来生产实际新闻;但在众多的新闻聚类算法中,这些数据 信息都没有得到合理利用了,所以应当加以利用。尤其是字数短但总结性很强的概要性文档, 非常适合用亍主题模型聚类算法,在这种情况下,主题模型聚类算法的时间复杂 度将会大幅度降低,同时也能生成合理的聚关结果 因此本文提出了一种基于隐含狄利克雷分布的 聚类算法,它可以顶先进行 离线部署,对每篇新闻文档所属的线索釆编文档生成一个新的文档库,首先对线索采编文档 库进行主题模型聚类算法,通过设定迭代次数的吉布森采样方法,对文档所属聚类簇 进行多次釆样,得到基于新闻线索语料的聚类结果,将其映射到网络新闻的原文档,形成新 闻文档的聚类结果集合。根据这个聚类集合,对于后续生产的新闻,直接采取 增量式聚类算法,将新生产新闻与当前聚类簇的主题向量计算相似度,同时改进新闻聚类簇 中的主題向量计算公式,即可以使用新闻热度来计算每个聚类簇的主题向量:最后确定其所 属聚类簇。 数据模型 ()新闻文档信息集合与新闻线索信息集合,表示新闻系统中的新闻集合与其对应的新 闻线索文档集合,用集合 来表小条新闻的集合,用集合 来 表示这个新闻的线索文档。 ()分词后的线索文档语料库,记为 ()使用向量空间模型与 词频统计算法对集合中的新闻文档进行文档模型处 理,对于集合 新闻文本可以表示为 ()每次输出的新闻主题聚类结果集合 ,每个聚类簇都包含了算法输出后 属于该聚类簇的新闻。 ()在算法更新时刻,新加入的新闻也通过向量空间表示: ()新闻访问量统计集合,使用集合 表示,用计算主题 ()新闻主题聚类簇质心向量,通过将每个主题簇中的全部新闰进行统计,得到这个簇 山国武技论文在线 的质心向量,使用新闻文本向量平均值来表示: 公式中 代表斯闻主题簇的质心向量,即主题向量。则代表聚类后 所得到的新闻主题簇中所属的新闻总量。表示新闻阅读量,表示聚类所 得簇中新闻的总阅读量,这两者用于改进主趣向量质心选取,热度越高的新闻应该 提供更高的权重。表示归属」主题簇中的新闻的文档向量。 ()新闻与给定主题向量的相似度 ,通过余弦距离公式来计算 新闻与主题向量的相似度: 算法步骤 用流程图对算法流程描述 山国武技论文在线 开始 输入新闻集合以及 新闻文档的线索集 合,进行分词,得 到话料库 判是 香线素语料库 加我浅寮语料库 加载新闻语料库, 输入吉布斯采样器 使用5 NM TF* IDF 算法表示语料 多次迭代,得出线 素·主题聚类概率 结果,映射到新闻 主题聚类结果 计算每个聚类中 的主题向量 根据时序关系,加 载新发布新闻 计算新闻与聚类簇 断有无新 主题向量相愀度 发布新闻 归入某簇或新建新 闻簇 算法结束 图算法流程 算法步骤如卜: 使用 分词系统,对集合与集合中的文档进行单独的分词,将结果保 存在两个单独的新闻文档语料库与 根据语料库中的语料,作为吉布斯采样器的输入,根据预先设定的主题聚类簇 个数,先为每个词语随机分配一个聚类簇;根据公式中的转移概率,计算每个 词语的新聚类簇分布慨率,再与均匀分布进行对比抽样,即可为词话分配新的⊥题 聚类簇;通过多次迭代,达到稳定收敛后,即可得到最终裹类结果。此时文档主题 山国武技论文在线 聚类簇概率矩阵可根据公式计算得岀,即可得到文档所属最大概率的聚类簇,即 完成了线索语料库的聚类。将其映射到新闻文档集合上,就得到了网络新闻数据聚 类输出。 完成初始新闻集合的聚类后,对于增量式生产出的新闻,按照时间顺序,读取新的 篇新闻报道,计算与每个已经存在的主题向量间的相似度 ,比较这些相似度,得到其中相似度最大的主题向量以及其 对应的新闻簇 若 ≥δ(δ为预先设定的阈值,即创建新聚类阈值),则将此新闻 归入新闻主题簇,同时吏新的主题向量,否则创建一个新的主题聚类簇 继续检査有无新报道新闻,并跳转至算法第步。当某阶段的聚类任务已经完成,则算 法结束,输出结果。 实验与结果分析 本小节对菜新闻报业集闭的网络新闻数据集合进行实验,将其标题、正文、发稿前线索 文档等语料进行整理,得到个主题,每个主题包含篇报道。共计条新闻,选取 其中时序靠前的条新闻作为已有新闻,进行主题聚类,其他的条新闻作为新 发布新闻,通过时序顺序输入后续主題聚类算法。对比实验使用全文吉布斯采样实验以及未 改进的 聚类算法作为对比算法。 实验参数设置如下 )根据文献,在主题模型的超参数选择中,α参数取值与主题数有关,其与 主题数乘积为常数,本实验中α参数的多个取值对实验结果影响很小,因此α参数 取值为 参数取值为初始主题聚类数量设置为。 ()根据多篇 聚类算法相关研究文献表明,将簇相似阈值δ设定为 较为合适,在木文中,经过多次的实验,δ设定在时,实验效果最好,实验中 同时采取两种阈值进行实验。 ()吉布斯样方法达代次数会明显影响实验结果;在针对新闻全文语料库的实验中, 由于语料库较大,通常需要次左右才能达到收敛状态;但针对新闻线索语料库, 由于语料库规模缩小,迭代次数也变小;在多次实验中,通常只要达到次左仁 就早已收敛,所以在本实验中将线索语料库的吉布斯采样次数设计为次,对比 实验中的全文语料库吉布斯采样迭代次数设计为 当阈值δ设定在时,表为对比实验的结果,耗时函数以时间复杂度最高的全局 算法作为基准,通过算法运算耗时比例定义耗时函数,由于实验库语料的规模较大 仝局算法在收敛后只有不稳定性,表中数据为其平均评价指标,表为其多次实验后统 计的最高、最低评价指标状态。 算法按照时序输入,只要阈值给定,输入结果不 变,那么输出结果就不会变;而木文提岀的改进算法也很稳定,多次实验中波动较小,取其 平均值展示在表,表则展示了本文改进算法的波动性。 表实验结果 全局准确率全同召回率 全局值 耗时函数 山国武技论文在线 全局 算 算法 改进算法 表 算法实验结果 算法 全局准确率 全局召回率 全局值 耗时函数 表现最好 平均值 表现最差 表改进算法实验结果 全局准确率全召回率个同值 耗时函数 表现最好 平均值 表现最差 算法评价指标对比图1 120.00% 10000% 80.00% 6000% 4000 20.00% 0.00% 全局LDA法 Sinlge-Pas9法 文进算法 ■全局准确率■全局召回率■全局F值■耗时函数 图算法评价指标对比图 从表与图可以看出,在平均情况下,对整个新闻文本语料库进行全局主题模 型算法后得岀的聚类全局准确率、召回率、全局值等指标是最好的,此时算法拥有 很好的聚类效果,改进算法的准确率、召回率不如全局算法,但相差较小; 聚类算法效果般,但非常稳定,同吋考虑时间复杂度的情况下, 聚类算法与改 进算法要远远优于全局算法 从表中可以看出,全局算法由于语料库较大,在多次迭代(次)后,仍然 可能出现多次采样转移不稳定的情况,这就导致了其在多次实验中会拥有不同的性能指标, 虽然最高效果与平均指标仍然较高,但表现最差的情况下的聚类准确率较低,这个时候

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源