中国科技论文在线中文稿件模板

Size: px

Start display at page:

Download "中国科技论文在线中文稿件模板"

镪方
5 years ago
Views:

1 面向领域的新闻话题发现的研究 * 米佳, 苗振江 ( 北京交通大学计算机与信息技术学院信息所, 北京 ) 5 摘要 : 互联网新媒体产生海量的半结构化新闻数据, 它们具备时效短, 动态性强, 结构不规范对社会舆论具有导向作用等特点如何将这些数据归类, 提炼出主题信息, 是本文研究的主要问题本文主要讨论如何将话题发现与追踪技术应用到新闻领域, 试图从新闻文本集合中, 找到主要的核心话题, 以专题的形式呈现给用户 10 本文首先研究了话题发现的关键技术, 分析话题发现体系结构的主要步骤, 包括文本预处理话题建模聚类算法等阶段, 得出文本聚类是其中的关键步骤 ; 接着, 阐述了各种聚类算法的原理及利弊 ; 最后, 从聚类的均匀性, 话题质量等方面, 比较几种算法的组合策略, 选取了在话题发现中使用较多的 single-pass 算法和 average-link 比较策略, 设计话题发现系统, 并阐述了话题发现在网络舆情监控中的实际应用 15 关键词 : 机器学习 ; 话题发现 ; 文本聚类 ;single-pass 算法中图分类号 : 请查阅中国图书馆分类法 Facing the field of news topic detection MI Jia 1, MIAO Zhenjiang 2 (1. BeiJing JiaoTong University, BeiJing ; 2. BeiJing JiaoTong University, Beijing ) Abstract: The Internet new media have mass of semi-structured data news. they have time limitation, strong dynamic and informal structure, which play a guiding role in social public opinions, etc. The methods of clustering these data and abstracting topic information are the main problem in this paper. This article mainly discuss how to find the topic and apply TDT to news field, trying to find the main core subject from sets of texts in the form of project presented to the user. Firstly, this paper studies the key technology of TDT and analyses of the architecture of the main topic detection steps, including the text pretreatment and topic modeling, clustering algorithm phases;secondly, draws text clustering is one of the key steps; Then, this paper expounds the principle of each kind of clustering algorithms and the pros; At last, makes comparison of several algorithm combination strategies from the cluster uniformity and the topic quality.this paper explores widely used single-pass algorithm and average-link strategy to design topic detection system and expounds the topic detection practical application.in network monitoring public opinion. Key words: TDT; text clustering; single-pass algorithm 0 引言互联网作为新媒体传播途径, 它的发展和创新模式引发前所未有的信息革命瑞典互联网市场研究公司 Royal Pingdom 在发布的 2011 年全球互联网产业发展状况报告中的数据显示,2011 年全球互联网用户总数接近 21 亿新兴的信息传播媒介, 如博客 (BLOG) RSS 百科全书 (Wiki) 数字图书馆社会网络 (SNS) P2P 即时信息 (IM) 以及 Twitter 微博, 它们的结构形式复杂, 没有统一的规则, 时效性较大, 内容变化较快如何从这些非结构化或者半结构化的海量 Web 数据超文本系统中, 提取用户需要的信息, 以结构化的数据形式提供给用户, 成为研究关注的问题 [1] 话题发现与追踪 (Topic Detection and Tracking, 简称 TDT) 技术为解决 Web2.0 时代的上述新问题提供了方向目前, 已经广泛应用于行业调研分析信息安全金融证券以及军事作者简介 : 米佳 (1980 年 ), 女, 中级讲师, 主要研究方向 : 人机交互. bjtu_learning@yahoo.cn - 1 -

2 领域本文主要依托话题发现与追踪这个背景, 从 Web 文本挖掘与聚类分析结合点展开, 采用文本聚类相关算法应用于新闻话题识别, 提高识别检测质量 1 TDT 核心思想及架构 TDT 的相关探索工作最早自 1996 年开始, 是美国国防高级研究计划总署 (DAPRA) 卡耐基梅隆大学龙系统公司马萨诸塞大学的联合合作项目, 着手考察广播新闻中的事件识别和追踪在研究中,TDT 评测会议对 TDT 涉及的重要概念进行了如下定义 : 定义 1: 话题 (Topic), 就是一个核心事件或活动以及与之直接相关的事件或活动定义 2: 事件 (Event) 通常由某些原因条件引起, 发生在特定时间地点, 涉及某些对象 ( 人或物 ), 并可能伴随某些必然结果包括事件名称事件时间事件人物事件地点等要素话题识别与跟踪系统主要包括数据采集数据预处理文本聚类文本分类等模块要实现这一过程, 首先要利用网页采集器即网络爬虫将多个站点的信息收集起来进行过滤清理形成有效的 Web 文本集, 接着对 Web 本文数据进行预处理, 形成文档的结构化表示, 再将文本进行聚类和分类以实现话题识别和跟踪图 1 给出了 TDT 的系统架构图 1 TDT 系统架构图 2 话题识别主要技术 65 话题发现技术主要包括 : 网页文本采集文本预处理话题模型表示特征提取和度量文本相似度计算和比较策略运用等内容话题发现系统的模型如图 2 所示 : - 2 -

3 图 2 话题发现系统模型 2.1 新闻语料采集 70 本文没有采用传统的语料库, 而是从四大门户网站 ( 新浪搜狐腾讯网易 ) 上采集原始的新闻报道作为实验语料数据采集阶段主要是从上述网站抓取网页信息资源存储到本地计算机网页的采集形式分为人工采集和机器自动采集两种目前主要使用的是基于网络爬虫的自动采集方式, 这种方式确保有效及时地跟踪与检测迅速变化的网络资源 [2] 2.2 文本预处理文本分析是文本挖掘信息检索的一个首要问题, 是指对文本的表示及其特征项的选取文本表示的目的是将无结构或半结构化的原始文本转变为计算机可以识别存储处理的结构化信息它包括文本预处理文本表示模型特征选择特征提取等几个阶段文本预处理是将原始的文档集合 ( 其中包括文字图像表格各种符号等元素 ) 通过去噪分词去掉停用词等步骤转换为有意义的文字序列 2.3 话题表示模型要判断某个报道是否和话题相关, 首先就需要解决话题和报道如何表示便于计算和比较, 即话题 / 报道用什么模型来表示 TDT 中最重要的问题就是为话题和报道建立表示模型主题模型是一种使用产生式模型来挖掘文本主题的方法, 是在已经知道文本单词的情况下, 反推出文本集的主题分布情况目前, 被广泛的应用与主题挖掘文本检索和社交网络分析等领域, 以及计算机视觉图像等领域 [3] 比较常用的话题表示模型包括 : 向量空间模型 (SVM) 概率模型词汇链和图模型等 2.4 特征选择 90 文本经过文本预处理后得到特征集合, 其中的特征数以万计, 有的特征未必是重要和有效的, 高维特征集合会加剧算法的负担, 需要进行恰当的特征选择, 降低时间复杂度, 提高文本挖掘的准确率常见的特征选择统计量有 : 文档频率互信息信息增益 X 2 统计交叉熵几率比等, 它们的共同处理方式都是计算每个特征的某种统计量, 然后将统计量与阈值 T 比较, 把统计量值小于 T 的特征去掉, 保留有效特征, 降低文本向量的维数, 提高运行速度和系统精度 2.5 特征抽取 95 特征降维最重要的方法是从原始的特征集合中, 抽取出一个维数更小更独立的特征空 - 3 -

4 间常用的特征抽取方法有 : 特征聚类主成份分析潜在语义索引和 LDA 等 3 将文本聚类应用到话题识别文本聚类的主要思想 : 使同类文档的相似度较大, 而不同类文档的相似度较小由于聚类不需要训练过程, 不用预先对文档手工标注类别, 因而具有较强的灵活性和自动化处理能力 [4] 在实际的分析应用中, 可以将聚类过程分解为三个环节 :(1) 获取结构化的文本集 ; (2) 执行聚类算法 ;(3) 选取合适的聚类阈值现有的聚类算法根据原理不同, 大致可以分为 : 划分法层次法基于密度的方法基于模型的方法 [5] 没有哪一种聚类算法有绝对优势, 适用于所有应用不同的应用环境下应该选用不同的算法 [6] 下面给出这几种算法在算法效率数据敏感性和处理高维数据方面的比较, 如下表所示 : 表 1 典型聚类算法性能比较性能算法算法效率异常数据敏感性高维性 K-means 一般敏感一般 CURE 较高不敏感一般 DBSCAN 一般敏感一般 SOM 一般敏感高聚类系统的整体性能评价通常采用两种指标 : 纯度和 F 值, 采用的数据一般是各种常用的文本语料以及包含多个不同主题的 Web 文档集合 [7] 对于类别 r 的纯度定义如下 : P(Sr)= 整体聚类结果的纯度定义为 : Purity = k nr P( Sr ) r 1 n 这里, n' 表示属于预定义类 i 且被分配到第 r 个聚类的文档个数,nr 表示第 r 个聚类 r 类别中的文档个数 F 值的定义是参照信息检索的评价原则, 将每个聚类结果看作是查询的结果, 对于一个聚类类别 r 和原来的预定义类别 i 有如下定义 : recall(i,r)=n(i,r)/ni precision(i,r)= n(i,r)/nr 其中 n(i,r) 是聚类 r 中包含类别 i 中的文档的个数,nr 是聚类形成的类别个数,ni 是预定义类别的个数 [8] 则聚类 r 和类别 i 之间的 f 值计算如下 : f(i,r)=(2*recall(i,r)*precision(i,r))/(precision(i,r)+recall(i,r)) 整体聚类结果的 F 值定义如下, 其中 n 是所有测试文档的个数 : F= ni max{ f ( i, r)} n i 1 max( n' r ) n r - 4 -

5 4 将文本聚类应用到话题识别 130 本章主要介绍话题发现系统的主要原理和技术, 包括系统结构系统功能和实现 [9] 本系统的设计平台采用 VisualStudio6.0, 核心部分采用 C++ 编码实现实验语料是从四大门户网站 ( 新浪搜狐腾讯网易 ) 上采集原始的新闻报道 4.1 系统的流程分析系统的整体流程如下图所示 : 图 3 系统整体流程图系统的主要框架分为两个模块 : 聚类模块和新文本处理模块在聚类模块中, 对原始文本进行文本预处理, 建立话题模型, 然后使用聚类算法进行聚类分析, 经过标注类别标识得到聚类模型 [10] 在新文本处理模块中, 首先对新文本进行建模, 然后利用聚类分析得到的聚类模型进行判断, 得到新文本的类别分析结果, 将文本归入该类系统中, 话题建模和聚类算法分析是系统流程的核心部分 4.2 系统的功能模块话题发现系统包括 : 分词特征选取选择话题模型话题聚类查看结果等功能模块本系统的特征选取主要使用 X 2 统计, 话题模型使用 VSM 向量空间模型进行文本特征表示, 采用 TF-IDF 模型计算特征词权重, 提取特征词, 构建用于聚类的文本向量本系统的话题聚类模块采用带缓冲的 Single-pass 增量聚类算法, 使用包含标准化特征词权重的文本向量来计算文本的相似度, 采用 average-link 比较策略计算 Web 文本和已有类簇的相似度, 聚类完成后即能检测到新的舆情热点话题带缓冲的 Single-pass 算法是读入 n 篇文章后在全局范围内寻求最优解, 能求出聚类后各文章与类中其它文章之间的相似度以及与类心的平均相似度其时间复杂度与 Single-pass 是同一数量级, 但需要一定的存储空间用于存储所有文章之间的相似度一般而言, 需要的存储空间为 n*(n-1)/2 由于多数文章间的相似度很低, 达不到阈值, 所以即使处理上万文章, 相似度所用存储空间也可以接收, 是个典型的稀疏矩阵 4.3 实验结果及分析 155 通过对话题发现算法的分析, 给出了算法各步骤可能的替换方案, 将各种方案比较组合, 形成四种可能的替换方案, 即 : - 5 -

6 (1) 经典 Single-pass 聚类算法 + 对应的权值计算方法 +single-link 比较策略 ; (2) 经典 Single-pass 聚类算法 + 对应的权值计算方法 +average-link 比较策略 ; (3) 带缓冲的 Single-pass 聚类算法 + 对应的权值计算方法 +single-link 比较策略 ; (4) 带缓冲的 Single-pass 聚类算法 + 对应的权值计算方法 +avg-link 比较策略 ; 使用 0.3 的相似度阈值, 分别使用四种组合方案对 900 篇文章进行话题发现, 得到 (1)single-link 和 average-link 相比较, 后者得到的类要显著地小于前者 (2) 带缓冲的 single-pass 得到的聚类中文章的数目, 要远远少于传统的 single-pass 方法所得到的结果, 前者只有后者的三分之一产生这种差别的原因 : 采用 single-link 策略时, 当前文章只需与某一类中的一篇文章的相似度高于一定阈值即可判定为同类, 相对比较容易 ; 采用 average-link 策略时, 当前文章必须与某一类的中心相似度高于一定阈值时才判定为同类, 相对较难因此, 采用 average-link 策略时, 得到的类要显著地小于使用 single-link 与传统的 single-pass 方法比较, 带缓冲的 single-pass 方法, 在计算权值时, 使用的 DF 值为缓冲区内的所有文章的 DF 值, 更能客观的反映当前所处理文章的特点, 避免主题泛化产生大类的情况就具体组合方案而言, 方案 1 存在如下问题 :1 聚类后得到的类的大小极度不均衡, 识别出的话题的质量相当差, 很多不属于同一个话题的报道都被聚到同一个话题中 ;2 通常, 一篇新闻报道可以属于多个话题, 或者说不同的话题下也可以有相同的新闻报道, 但此方案识别出的话题不能满足这种要求组合方案 2 中比较策略为 average-link, 使得聚类后产生的大类数量大大减少, 得到的类比较均衡, 识别出的话题质量有所改善但是, 聚类后得到的前几个大类, 尺寸相对还是比较大, 基本不存在话题中心, 识别出的话题质量很差组合方案 3 中, 聚类策略和权值比较方法得到改变, 使得产生的类更为均匀, 话题质量得到改善, 但任然会有大类的情况产生组合方案 4 结合了方案 2 和方案 3 的优点, 聚类后产生的类大小更为均衡, 话题中心突出, 识别质量显著提高, 更容易为用户所接受 5 结论本文给出了 TDT 的核心思想和系统架构 ; 介绍了 Web 文本预处理, 包括网页预处理文本分词等关键步骤 ; 比较了文本分词的几种方法和优缺点适用范围 ; 论述了话题表示模型, 主要有向量空间模型图模型词汇链 LDA 模型, 说明了特征提取和特征度量的方法 ; 介绍了文本相似度计算方法 ; 阐述了文本聚类的基础知识 ; 分析几种主要聚类方法原理和优缺点, 找出适合应用于话题识别的聚类方法 ; 讨论了话题热度指标以及话题发现在网络舆情监控中的应用论述话题发现系统的结构与功能, 主要使用四种聚类算法和比较策略组合方案, 选取带缓冲的 single-pass 聚类方法 +average-link 比较策略实现 [ 参考文献 ] (References) 195 [1] 王志明.Web 新闻专题组织与生成系统研究 [D]. 长沙 : 中南大学,2008. [2] 王健.Web 信息分类与自动摘要的研究 [D]. 天津 : 天津大学,2006. [3] 万小军, 杨建武. 在线主题检测与应用 [J]. 华南理工大学学报 ( 自然科学版 ),2004,32 [4] 赵慧杰. 面向论坛的话题发现跟踪及传播技术研究 [D]. 哈尔滨 : 哈尔滨工程大学,2010. [5] 李保利, 俞士汶. 话题识别与跟踪研究 [J]. 计算机工程与应用,2003,39(17):

7 [6] Christian Wartena and Rogier Brussee.Topic Detection by Clustering Keywords[J].19th International Conference on Database and Expert Systems Application. [7] Shan Jin,Hermant Misra, Thomas Sikora, Joemon Jose.Automatic Topic Detection Strategy for Information Retrieval In Spoken Document[J].WIAMIS,2009 [8] Lei Shi, Bai Sun,Liang Kong and Yan Zhang. Web Forum Sentiment Analysis based on Topics[J].IEEE Ninth International Conference on Computer and Information Technology [9] 盛振华. 面向 WEB 对象的聚类技术研究 [D]. 浙江 : 浙江大学,2010. [10] 陈嘉勇. 基于 WEKA 平台的文本聚类研究与实现 [J]. 中国管理信息化,2009,12(21) - 7 -

Microsoft Word - 专论综述1.doc

Microsoft Word - 专论综述1.doc 1 基于协同过滤的高考志愿推荐系统徐兰静, 李珊, 严钊 ( 南京航空航天大学经济与管理学院, 南京 211100) 摘要 : 近年来信息过载问题的出现使得个性化推荐技术应运而生, 其中协同过滤推荐技术通过在用户和信息之间建立联系, 被