（计算机应用技术专业论文）网络舆情分析中的特征提取研究.pdf

摘要 摘要 随着互联网的普及和发展，网络作为继传统媒体之后的第四媒体，其影响 已经全面而深刻地渗入到了人们的政治、经济、文化生活等各个方面。网络传 播具有自由性、交互性、开放性、虚拟性和隐蔽性等特点，既提供了大量进步、 健康、有益的提倡性信息，也有不少反动、迷信、低级的误导性言论，因此对 网络舆情进行分析和预警已经成为一个非常重要的现实需求。 网络公共舆情的来源按交流方式主要分为两类。一类以b b s 为代表，数据 之问具有明显的交流关系，对b b s 的内容监控可以直接使用文本挖掘的技术； 另一类以公共聊天室为代表，聊天数据不具有明显的交流关系，对公共聊天室 的内容安全监控需要构建聊天室的社会网络，即发现用户之洲的交流关系。而 上述两类场景的监控都首先必须对网络数据进行特征提取，将数据转化为计算 机可以处理的格式，然后彳。可以使用各种分析技术对数据进行挖掘。 本文以网络舆情分析为背景，重点研究面向b b s 和公共聊天室两类代表性 数据的特征提取问题。针对这两种数据，我们分别设计了相应的针对性的特征 提取方法：并最终围绕这两类数据环境，构建了一个网络舆情监控原型系统。 论文的主要工作包括： 1 设计了针对b b s 数据的特征提取方法。首先，考虑到帖子标题的重要性， 修改了经典权重计算的t f 木i d f 方法，将帖子标题中的单词权重加大：其次，鉴 于大多数b b s 数据具有明显的短文本特点：关键词稀疏，信息不完备等，我们 根据帖子之间的回复关系构建了一棵回复关系树，在树的每条回复链上从上到 下和自下而上地进行特征的传递和权重的调整，可以有效改变原来帖子特征的 稀疏性，使它的信息更加趋于完整，主题更加明确，这样将能够改善我们文本 挖掘算法的效果。 2 构造了有效的聊天室社会网络挖掘中的特征提取方法。针对聊天室数据 的特点和聊天室社会网络挖掘的需要，我们对m u t t o n 方法的启发式规则进行了 修正和进一步扩充，并且引入内容相似性特征；然后采用集成学习的策略，基 于多特征融合进行聊天室社会网络挖掘。 3 综合本文提出的上述两种特征提取方法，设计并实现了一个网络舆情监 控原型系统。 摘要 关键词：舆情分析特征提取集成学习社会网络挖掘 n a b s t r a c t a b s t r a c t w i t ht h ep o p u i a t i o na n dd e v e l o p m e n to fi n t e m e t ，n e t w o r k ，a st h ef o u r t hm e d i a f o l l o w st h et r a d i t i o n a lo n e s ，i sb r i n g i n ga p r o f o u n di m p a c to np o l i t i c a l ，e c o n o m i ca n d c u l t u r a ii i f eo fa l lh u m a ns o c i e t i e s n e t w o r kt r a n s m i s s i o nh a l st h ea t t r i b u t e so f 舶e d o m ，i n t e r a c t i v i 吼o p e r u l e s s ，v i r t u a la n dh i d i n g i tc a nn o t0 n l yb r i n gal o to f p r o g r e s s i v e ，h e a i m ya n dp r o f i t a b 王ep o s i t i v ei n f o 吼a t i o n ，b u ta l s oc o n t a i n ss o m e r e a c t i o n a 吼s u p e r s t i t i o u sa n dl o wm k e dn e g a t i v e i n f o n n a t i o n t h e r e f o r e ，t h e r e s e a r c ho nn e 帆o r kp u b l i co p i n i o na n a l y s i sa n df o r e c a s th a sb e c o m ea ni m p o r t a n t a c t u a ld e m a n d t h es o u r c e so fn e t w o r kp u b l i co p i n i o nc a nb ed i v i d e di n t ot w ok i n d s t h e 磊r s t l ( i n di sr e p r e s e n t e db yb b s ，w h o s ed a t ah a so b v i o u sc o m m u n i c a t i o n a lr e l a t i o n s h i p t h et e x tm i l l i n gm e t h o dc a nb ea d o p t e dt om o n i t o rt h eb b sd i r e c t l y d i f f e r e n tw i t h t h ef i r s t “n d ，t h es e c o n dk i n do fs o u r c ei sr e p r e s e n t e db yt h ec h a tr o o m ，w h o s ed a t a d o e s n th a v eo b v i o u sc o m m u n i c a t i o n a ir e l a t i o n s h i d t h es o c i a ln e t w o r ko fc h a tr o o m s h o u l db ec o n s t r u c t e d ，、v h i c hi sa l s ot od i s c o v e rt h ec o m m u n i c a t i o n a jr e l a t i o n s h i p b e t w e e nu s e r s ，t om o n i t o rt h ec o n t e n t so ft h ec h a tr o o m i nt h em o n i t o r i n gp r o c e s so f t h et w ok i n d so fn e t w o r k p u b l i co p i n i o n ，f i r s t l y ，f b a t u r e sm u s tb ee x t r a c t e df r o mt h e n e t w o r kd a t aa n dc o n v e r t e dt oaf o m l a t ，w h i c hc a nb ep r o c e s s e db yc o m p u t e r a n d t l e ns o m ea n a l y s i st e c h n o l o g i e sc a nb eu s e dt om i n et h ed a t a u n d e rt h eb a c k g r o u n do ft h en e t 、v o r kp u b l i co p i n i o n ，t h i sp a p e rf o c u s e so nt h e f e a t i l r ee x t r a c t i o np r o b l e m so fb b sa n dc h a tr o o md a t ar e s p e c t i v e l y 。f o re a c hk i n do f d a t 如、v ed e s i g nas p e c i a lf e a t u r ee x t r a c t i o nm e t h o da n dc o n s t r u c tap u b l i co p i n i o n m o i l i t o r i n gp r o t o t y p es y s t e m t h em a i nw o r ko ft h i sp a p e ri n c l u d e s ： 1 d e s i g n i n gaf e a t u r ee x t r a c t i o nm e t h o df o rb b sd a t a f i r s t l y ，c o n s i d e r i n gt h e i m p o 豫m c eo ft h ep o s tt i t l e ，w em o d i f yt h et r a d i t i o n a lt f 幸i d fm e t h o da n di n c r e a s e t h ew e i g h to ft h ew o r d si n t i t l e s e c o n d l y ，i nv i e wo ft h eb b sd a t ah a v i n gt h e c h a r a c t e r i s t i c so fs p a r s ek e y w o r d sa n du n c o m p l e t e di n f o r m a t i o n ，、v ec o n s t r u c ta r 印l y t r eb a s i n go nt h er e p l yr e l a t i o n t h ef e a t u r e sa r et r a n s m i t t e da i l dt h e i rw e i 曲t sa r e i i i 图索弓 图索引 图2 1b b s 同复关系树。9 图2 2 自动采集流群图1 0 图2 3 爬虫1 ：作原理l l 图2 4w 曲页面文本抽取1 2 图2 5 具有同复关系且出现相同单词的两篇帖子：2 l 图2 。6 具有同复关系的两篇帖子2 l 图2 7b b s 数据格式2 4 图2 8b b s 分类算法训练过程2 5 图2 9b b s 分类算法测试过程2 6 图2 1 0m a c r o f l 和特征选择数r 的关系曲线：3 0 图2 1 1 分类效果和高权重词传递个数h 的关系曲线3 0 图3 1 一个简单的社会网络示意图：3 4 图3 2 启发式规则无法处理的例子3 8 图3 3 社会网络挖捌方法框图4 2 图3 4t s 对误报率的影响4 7 图3 5t s 对漏报率的影响4 7 图3 6 迭代次数对误报率和漏报率的影响：4 8 图4 1 系统体系结构图4 9 图4 2 预处理模块5 0 图4 3 话题发现示意图5 l 图4 4 话题追踪模块5 2 图4 5 人物关注模块：5 2 图4 6 社会网络挖掘模块5 3 6 1 表索引 表索引 表2 1 不同分类算法的结果比较2 9 表3 1 二种方法的漏报率和误报率比较4 6 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 专况矽 作者繇强易 么斫年旷月2 7 日 第l 章引言 渠道表达自己的真实想法。近几年来，国内外的每一重大事件，几乎都在网络 媒体上引发剧烈的反响与激烈的辩论，甚至产生巨大的舆论力量。网络舆情不 仅形成迅速，而且对社会生活的各个方面产生了极大影响。因此，对网络公共 舆情进行分析和预警逐步成为社会管理者面临的重大课题。 网络公共舆情的来源按交流方式主要分为两类。一类以b b s 为代表，数据 内容分为主贴与回帖，具有明显的交流关系，对b b s 的内容监控可以直接使用 文本分类、聚类等文本挖掘技术：另一类以公共聊天室为代表，聊天数据不具 有明显的交流关系，对公共聊天室的内容安全监控首先需要进行聊天室社会网 络挖掘，即发现用户间的交流关系。而无论是对b b s 数据进行内容挖掘还是对 公共聊天室进行社会网络挖掘，都需要先对网络数据进行特征提取，将数据的 特征转化为计算机可以处理的格式，然后才可以使用各种数据挖掘技术对数据 进行挖掘。 本文就以网络舆情分析为背景，重点研究其中的b b s 和公共聊天室两类数 据的特征提取问题。针对这两种数据，我们分别设计了相应的针对性的特征提 取方法。 1 2 研究现状 1 2 ib b s 监控领域现状 从国内外研究现状来看，目前关于b b s 数据的文本挖掘以及b b s 监控的研 究总体还处于起步阶段，研究还不多。 国内主要工作有：李昕、朱永盛、武港山( 2 0 0 6 ) 通过话题线索分析、指定作 者所有消息的分析和基于关键词的消息语义分析来发现论坛中的语义漂移。蒋 凡、王煦法等( 2 0 0 5 ) 通过计算词语在回帖传播链上的影响力，提出了一种根据对 有影响力词语聚类的方法来发现b b s 中具有影响力的主题。奚伟鹏，李听等( 2 0 0 5 ) 提出了一种按话题线索抽取网络论坛信息的方法。于静、赵燕平( 2 0 0 5 ) 使用混合 过滤模型对b b s 数据进行过滤，并引入社会网络技术进行辅助分析。由于b b s 数据中存在明显的回复关系，因此可以直接构建出其中的社会网络。他们使用 社会网络分析技术对所发现的危险信息进行深入分析，发现中心人物及群落分 布形态、信息传播渠道、行为模式及影响规律。黄东平和田芳( 2 0 0 4 ) 将b b s 中 2 第1 章引言 对经过扩展的聊天数据进行话题检测。实验结果表明，这种结合社会网络分析 的方法能够有效提高话题检测的准确度。 1 3 本文的主要工作与内容安排 本文以网络舆情分析为背景，重点研究面向b b s 和公共聊天室两类代表性 数据的特征提取问题。针对这两种数据，我们分别设计了相应的针对性的特征 提取方法；并最终围绕这两类数据环境，构建了一个网络舆情监控原型系统。 论文的主要工作与特色有： 针对b b s 数据的短文本特性，提出了一种基于回复关系树的b b s 数据特征 提取方法。首先，考虑到原帖标题的重要性，修改了经典权重计算的t f 幸i d f 方法，将原帖标题中的单词权重进行了调整：其次，鉴于大多数b b s 数据 具有明显的短文本特点：关键词稀疏，信息不完备，话题类别属性很不清楚 等，我们根据帖子上下文之闯的回复关系构建成一棵回复关系树，在树的每 条回复链上从上到下和从下到上进行特征的传递和权重的调整，可以有效改 变原来帖子特征的稀疏性，使它的信息更加趋于完整，主题更加明确。实验 表明，将这种方法应用到传统的文本分类算法中，将能够很好的改善起其分 类效果。 构造了有效的聊天室社会网络挖掘中的特征提取方法。针对聊天室数据的特 点和聊天室社会网络挖掘的需要，我们对m u t t o n 方法的启发式规则进行了 修正和进一步扩充，并且引入内容相似性特征：然后采用集成学习的策略， 基于多特征融合进行聊天室社会网络挖掘。实验表明，该方法能有效地提高 社会网络挖掘的准确性。 设计并实现了一个网络舆情监控原型系统，并将上述两种特征提取方法应用 到其中，取得了较好的效果。 本文共分五章，各章节的内容安排如下： 第章引言。本章首先介绍了网络舆情监控的背景知识，然后讨论了b b s 和聊天室两种场景下的研究现状。 第二章b b s 数据的特征提取。本章首先对b b s 作了一个简单介绍，分析 了b b s 数据的特点，然后介绍了b b s 监控中涉及到的各种挖掘技术，包括数据 第2 章b b s 数据的特征提取 第2 章b b s 数据的特征提取 本章首先对b b s 作一个简介，分析b b s 数据的特点：然后介绍我们针对 b b s 数据设计的各种挖掘技术，包括数据采集、数据预处理、特征表示、特征 选择以及我们专门针对b b s 数据设计的数据特征权重调整算法。最后给出实验 分析。 2 1b b s 简介 b b s 即网上论坛，是英文b u l l e t i nb o a r ds y s t e m ( 电子公告系统) 的缩写， 是互联网最知名的服务项目之一。它最早可追溯到克瑞森和苏斯于1 9 7 8 年编写 的“计算机公告牌系统”，是8 0 年代末随着国际互联网的开始流行而迅速发展 起来的。 大多数网站的b b s 就像现实生活中的公告板一样，用户可以在不同的讨论 区获取不同的信息，还可以将自己要发布的信息或回应网友的帖子张贴到公告 板上，与其他网友展丌讨论。b b s 通常分为几个讨论区，每个讨论区都有自己 的主题，比如科大b b s 就有振兴中华、贴图、电影天地、工作就业等4 0 0 多个 讨论区，从讨论区的名称就可以知道它的讨论主体及范围。 b b s 是互联网上使用最多的一种信息交流方式，人们可以方便地在b b s 中 ，讨论问题，发表言论，交流信息。b b s 上的舆论互动参与形成了一种强势的舆 论氛围，人们就共同感兴趣的话题展开讨论，各种思想观点不断撞击，实现了 真正意义上的舆论互动。登陆国内各大网站的b b s ，我们都能发现，这里汇集 着大量的新闻和观点，国际和国内的一些突发性新闻和重要新闻在这里都可以 看见，系统阐述的观点和大胆妄想的观点也不在少数；同时，由于网民地域、 行业及阶层分布广，论坛中可以听到不同声音，可以说是民声的集散地。在浩 瀚的帖子中，有的帖子不能引起关注，就很快被新贴覆盖了，然而能反映重大 事件、引起人们兴趣的帖子却得到网友的追捧，越来越多的人参与到讨论中， 很快成为热点话题；其中的一些经网友转载，更加壮大了网络舆论的声势，甚 至吸引传统媒体参与其中，实现了网络舆论和现实的互动。 7 第2 章b b s 数据的特征提取 网络b b s 扩大了人们获取信息的自由度的同时，也为人们提供了发表言论 的最大自由。如今，任何人都可以通过自己的电脑将想法和信息张贴到网上， 让其他人分享，甚至进行辩论，人们甚至把b b s 称为“自由的乐土”。然而，不 加节制的自由也带来了一系列的问题：信息垃圾堵塞通道、虚假信息欺骗世人、 色情暴力误导少年等。而b b s 具有的开放性、实时性、多话题交错等特点，使 得在其中进行恶意活动会更加隐蔽。从近几年开始，b b s 的这一特点已越来越被 某些特定群体人员有意识地使用，借以达到他们的特殊目的，b b s 所带来的负面 影响已经显现，因此，对b b s 进行监控已经成为一个非常重要的现实需求。 b b s 监控需要解决数据的特征提取、关联性处理、f 常异常信息的判别、 话题检测及跟踪等技术。其中，特征提取是一个关键，它是对b b s 内容进行分 析、识别与跟踪的基础。 2 2b b s 数据的特点 b b s 中的数据与传统的长文本数据相比，有自己明显的特点： ( 1 ) 实时性非常强，数量巨大。我国拥有1 3 0 万个b b s 论坛，各大论坛的数 据随时都在更新。 ( 2 ) 以发表时间排序。 ( 3 ) 内容杂乱，同一个讨论区经常出现多话题的交错。 ( 4 ) b b s 下的数据不同于传统的纯文本数据，b b s 数据中的每一条消息除了 消息正文外，还有标题、作者、发布时间等特征。 ( 5 ) 大部分b b s 数据具有短文本的性质，类似于聊天室中的数据，回复消息 尤其如此。消息长度一般都比较短，关键词数量很少，一般只有几十个字符， 甚至只有几个。比如b b s 论坛的回帖中常常只出现“顶! “赞! ”“很好! ”等一 个词。错误噪音多，用语不规范。存在着大量省略、缩写、指代现象以及拼写 错误。 ( 6 ) b b s 数据之间不是相互独立，而是具有回复关系。b b s 数据中的消息分 为两种，一种称为源消息，即新发布了一个帖子；另一种称为回复消息，即是 对一个帖子的回帖。比如a 是源消息，b 是对a 的回帖，那么b 就称作回复消 息，而c 是对b 的再次回帖或者还是对a 的回帖，同样称作回复消息。一般地， 两种消息可以通过标题清楚地分刀：，比如源消息标题为“a b c ”，则回复消息的标 8 第2 章b b s 数据的特征提取 题通常为“r e ：a b c ”。这样，不同于纯文本数据之间的相互独立，b b s 下的数据 具有了相关性源消息和它的所有回复消息，在形式上构成了一个具有时序 性的回复链，如果考虑具体的回复关系，那么将构成一棵具有偏序关系的树， 我们称之为回复关系树。如图2 1 所示，a 为源消息，b 、c 直接回复a ，而d 、 e 、f 又直接回复b 。它们构成了一棵回复关系树，a b d 是回复关系树上的 一个回复链。 图2 1b b s 网复关系树 ( 7 ) 语义漂移：回复链上随着消息数量的增加，这些消息序列不可避免地会 存在语义漂移的情况，即b b s 用户讨论的中心议题已经发生了转变。这样，在 同一个消息序列中，可能会出现多个话题相互交织在一起，有的话题甚至已经 偏离到与原贴完全无关，这给我们的话题发现和话题追踪带来了很大的困难。 2 3b b s 数据的采集 b b s 数据具有海量、多样、异构、动态变化等特性，要准确迅速地获取所 9 第2 章b b s 数据的特征提取 需要的数据越来越难。我们针对b b s 设计了自动采集工具，采用的采集技术包 括：网络爬虫模块、数据抽取模块。流程如下： 抓取 参数设戤 2 3 1 网络爬虫 下载 图2 2 自动采集流程图 储 所谓网络爬虫，中文又称为网络机器人或者网络蜘蛛。它是一个自动提取 网页的程序，从力维网上下载网页。传统爬虫从一个或若干初始网页的u r l 丌 始，获得初始网页上的u r l ：在抓取网页的过程中，不断从当前页面上抽取新 的u r l 放入队列，直到满足系统的一定停止条件。 本系统采用的爬虫工作原理及关键技术如图2 3 所示。 爬虫的工作流程较为复杂，需要根据一定的网页分析算法过滤与主题无关 的链接，保留有用的链接并将其放入等待抓取的u r l 队列。然后，它将根据一 定的搜索策略从队列中选择下一步要抓取的网页u r l ，并重复上述过程，直到 达到系统的某一条件时停止。另外，所有被爬虫抓取的网页将会被系统存贮， 进行一定的分析、过滤，以便之后的处理。 l o 第2 章b b s 数据的特征提取 图2 3 爬虫1 ：作原理 2 3 2 基于模板的w 曲页面文本抽取 所谓w 曲页面文本抽取就是从w e b 页面中把自己关注和需要的信息提取出 来，把别的无用信息过滤掉的过程。目前常用的w 曲页面文本抽取方法为基于 模板的抽取方法，它具有速度快，准确性高的优点。但是对于每一种采用不同 结构或不同风格的w | e b 页面，要定制不同的模板。如图2 4 所示。 第2 章b b s 数据的特征提取 图2 4w 曲页面文本抽取 w 曲页面文本抽取的具体方法为：把文档输入h t m lp a r s e r ，按照文档对 象模型( d o m ) 生成一种树形表示，通过模板中对树各结点的标注来完成对w i e b 页面的抽取。比如我们要找到b b s 每篇帖子的标题、作者、正文等，就要在 w 曲页面中相应的标签中抽取。 2 4b b s 数据的预处理 计算机本身并不具备人类的智能，人可以通过阅读文章，根据自身的理解 能力获得对文章内容的认识，但计算机并不能“读懂”文章，从根本上说，计 算机只认识0 和l 。因此，在对b b s 数据进行分类聚类之前，首先要对训练和 测试的数据进行一系列的预处理，表示成一个个特征，转化为机器学习算法易 于处理的向量形式。很显然，这样做将丢失大量关于文章内容的信息，但是这 1 2 第2 章b b s 数据的特征提取 种表示可以使文本的处理形式化，并且可以取得较好的挖掘效果。传统长文本 下的一些预处理技术也同样适用于b b s 下的短文本数据。预处理步骤如下： ( 1 ) 文本分词 词是文本挖掘中使用最广泛的特征。对于英文文本及类似语种的文本来说， 因为这些语种采用空格或标点将词隔开，所以词的获取变得非常简单。但是对 于中文文本，除了标点符号之外，词语之间没有明显的分隔符，因此需要专门 的分词工具。中文分词不是我们的研究重点，因此我们采用了中国科学院计算 技术研究所的分词系统i c t c l a s ( i n s t i t u t eo fc o m p u t i n gt e c l l n o l o g y ，c h i n e s e l l e x i c a la n a l y s i ss y s t e m ) ，并在此基础上作了一定的修改，以满足我们的实际需 要。 ( 2 ) 停用词表 将一些在文本中出现频率高但是含义虚泛的词放入停用词表。这些词在不 同的语言环境有不同的表示。例如在英语中的a ，a n d ，t h i s ，a t ，i n ，中文中的 “的，得，地，这，尽管，但是”等，保证出现在停用词表中的词不能选作文 档特征。 ( 3 ) 稀有词处理 有些词条在整个文档集中出现的频率都很低，它们也不适合作为文本的特 征项。通过对文档集进行词条频率统计并设计一个词频阈值，只要是词条频度 低于这个词频阈值的词就被删除。 ( 4 ) 单词归并 为了降低特征维数，提高效率，采取单词归并和同义词归并的策略，把表 达形式不同而含义相同的或是含义相似的词作为同一个词条处理。如英文中的 f o o t b a l l 和s o c c e r ，中文的“电脑 和“计算机”等。 ( 5 ) 同根词处理 由于英文中存在着各种时态、语念和名词的单复数表示，因此英文单词常 常有多种形式，比如t a l k 还有其他形式t a l k i n g 、t a l k e d 等。但是这些形式基本上 都表示同一个意思，因此我们采用取词根的技术把它们都还原到用同一个词根 来表示。 第2 章b b s 数据的特征提取 特征，出现的概率，即出现特征f 的文本数除以文本总数；p ( f ) 表示特征f 不出现 的概率，即不包含特征f的文本数除以文本总数：p(c，l r ) 表示出现特征f 的文本 属于类别c ，的概率，即出现特征，并且属于类别c ，的文本数除以出现特征f 的文本 数；p(q l丁)表示不包含特征，的文本属于类别e的概率，即不包含特征，并且属于类别c 的文本数除以不包含特征f 的文本数。 ( 3 ) 互信息 假设彳莲猫攀薹塞霉堙刑萋l 坠醚珑酬j 菱羹囊喘茹霎奏墓套攘蓁i 萋哺研 囊；翼量滴矧霪羹副蓬蓼褊并萋甄型囊i 羹囊霎萋萋鲢；巍型璺| 星徭薹塑甏鋈 影蚓匝雾袈镨嬲 娑薹霎萋薹震薹塞囊冀羹羹篓鬟薹 羹鬻 褂茧蓟剖i 乏嗣荤锪鳓够嚣；雾善；i ；雩i ；j 蓁薹藉埔一刭澎1 5 i 臻裂蝼匿蹬 匿蛳冀蚕m 鸣佯j 较囊霎鲑缎缓譬羹鹅野薹区别开来的特征项，这种特征项不仅要有较高的出现频率，还要在文档集 合中较少的文档中出现。将频率因子和文档集合因子相乘就可以实现此目的， 这就是文本挖掘中常用的i f 事i d f公式： w p 劬岛芦脚( 瓦) = c 厂( 瓦) 矽( 瓦) ( 2 4 ) 其中j 为文档号，七为特征项编号。 我们引入规则化因子来消除文档长度对计算结果的影响，使得权重值落在 【o ，l 】区间内。假定w 代表特征项的权值，最后的规格化因子定义为： 毒 或喜 ( 2 。5 ) 娶i 匿i 、“j oe c t o r | 1 一。l 这样，最后t f 毒i d f 的归一化计算公式如下： 。 驯o g ( 嵩圳 2 6 ) 其中，f 为文本编号；七为特征项编号：以表示特征七在文本，中一共出现 第2 章b b s 数据的特征提取 2 7b b s 数据的特征权重调整算法 上面介绍的经典权重计算方法t f i d f 方法是一种基于统计的方法，对长文 本非常适用，但当用于大多数为短文本形式的b b s 数据时就不再有很好的效果。 下面从两个方面阐述我们设计的针对b b s 数据的特征权重调整算法。 ( 1 ) t f 乖i d f 方法将所有的单词平等对待，但是b b s 数据是半结构化的，每 篇原帖有标题和正文之分，一般来说，出现在文章标题中的单词表达文章主题 的能力比f 文中的其它词要强。因此，如果一个特征出现在文章标题中，它的 权重相应地应该加强。我们对t f 木i d f 方法的公式进行修f ，对于b b s 数据中 的原贴f ，记它的标题特征集合为z ，则特征七的权重为 2 刚吮1 0 9 ( 裳“) ( 2 1 7 ) 其中， = b 笼丢 口 1 ，为标题权重的调整系数：吮表示特征七在原帖f 的标题和e 文中一共出 现的次数；为总的文档数；m 含有特征七的文档数：为一个经验常数。 ( 2 ) 对于b b s 数据中的回帖，大都非常短，包含的关键词稀疏，不能反映 个话题的全貌，它只是参与了一个话题的讨论。我们经常会看到，一个回帖 只是一句话，甚至只是几个词，单纯地看它，根本不知道发帖人想表达什么意 思，只有再参考他所回复的帖子和别人回复他的帖子，才能明白他想表达的信 息。这样，b b s 数据中的文本便不再独立，由于回复关系而具有了相关性。若 想准确地判断回帖所参与讨论的话题，必须考虑它的上下文关系，即它所回复 的贴和回复它的贴。而且，由于存在语义漂移的现象，b b s 数据中回帖的主题 可能已经偏离了原帖的主题，随着回复链的加长，偏离可能越严重，所以它的 类别信息不能单纯由原帖决定，而应该考虑整个回复链对它的影响。因此计算 权重时不仅要考虑帖子本身的单词，还要考虑它所回复的帖子对它的影响以及 回复它的帖子对它的影响。前者对应回复关系树从上到下特征信息的传递，后 者对应回复关系树从下到上特征信息的传递。影响系数随着回复链的长度而变 第2 章b b s 数据的特征提取 实际运用中，由于权重的范围设定在【o ，l 】区间内，所以如果以 l ，则令 = l 。 设c 2 譬，则e 中单词的权重计算公式为 屹2 喈 ( 2 2 3 ) e 中的前办个高权重词( 不包括和父结点p 的单词交集) 也要向上传递给 父节点p ，不过权重要衰减，衰减系数为五，0 允 父结点p 中单词权重修正的公式为 w 破= 旯屹，( o 兄 1 ) 矿七也 ( 2 2 5 ) 这样，高权重词在向上传递的过程中，权重将按指数衰减，逐渐变得不再 是高权重词，停止向上传递。即随着回复链的增长，帖子向上的影响力逐渐减 弱。 经过上面两个特征传递的过程，可以有效改变原来帖子特征的稀疏性，使 它的信息更加趋于完整，主题更加明确，这样将能够有效地改善我们文本挖掘 算法的效果。 2 8 实验分析 为了检验我们提出的针对b b s 数据的特征提取方法的效果和效率，我们将 之应用到具体的b b s 文本分类问题中。实验中我们的分类算法采用中心向量法， 特征选择采用信息增益的方法，然后比较使用和不使用我们的特征提取方法两 种情况下的分类效果。 第2 章b b s 数据的特征提取 也可以设定一个分类阈值，如果文本向量到各个类别中心的距离都小于这 个阈值，则认为它不属于任何类。 中心向量晚= ( 。，：，) 的构建方法非常简单，即为训练集合中类别 嚷的所有文本构成的集合= 五，玩：， 的中心向量，公式如下： ：击羔k ， 。丽备k ， ( 2 2 7 ) 其中，l i 为第七类训练样本的总数，k ，为第七类的第f 个样本在第维特 征上的取值。该算法的特点是容易实现，训练过程特别简单，训练时间较短。 训练过程流程图如图2 8 所示： 输入训练样本 数据预处理 特征的向量表示 特征选择 计算每个类别的向量中心 图2 8b b s 分类算法训练过程 将每种类别的训练样本转换为特征向量表示后，再经过特征选择过程，获 得降维处理后的特征表示。然后计算每个类别的中心向量，训练过程结束。 第2 章b b s 数据的特征提取 在测试过程中引入我们提出的b b s 特征提取方法，测试过程如图2 9 所示。 每个主题的所有帖子( 包括原帖和回帖) 构建成一棵回复关系树，然后在树上 进行特征的传递和权重的调整，最后将每个结点( 即每篇帖子) 的向量表示输 入分类器获得分类结果。 图2 9b b s 分类算法测试过程 2 8 3 分类评估指标 文本分类从根本上来说就是一个映射过程，评估文本分类方法的指标主要 第2 章b b s 数据的特征提取 表2 1 不同分类算法的结果比较 m i c orm i c r opm i c r o f l m a c r 0r m a c r opm a c r o f l 中心向量法o 6 8 4 4 2 40 8 0 8 4 9 4o 7 4 1 3 0 4o 6 9 0 8 2 8o 7 9 1 1 0 8o 7 3 7 5 7 5 我们的方法o 9 0 4 7 4 60 9 0 9 7 3 20 9 0 7 2 3 2o 9 0 3 3 5 50 8 9 7 9 5 0o 9 0 0 6 4 4 从表2 1 中可以看出，传统的中心向量分类算法应用到b b s 文档分类问题 中时，分类效果并不理想，这主要是因为大多数b b s 数据具有短文本的特点， 特别是回帖，大都非常短，特征词稀疏，信息不完备。但当使用了我们设计的 针对b b s 数据的特征提取方法以后，分类效果明显提高，这证明我们的方法确 实是有效果的。 ( 2 ) 重要参数对分类性能的影响 经过实验，我们发现对分类效果影响较大的参数是特征选择个数，和高权重 词传递个数厅。 图2 1 0 显示了m a c r o f l 随特征选择数r 的变化曲线。可以看出，其它参数 不变的情况下，当特征选择数r 大于1 0 0 0 时，可以保持很高的分类精度，甚至 在有些情况下可以比没有经过降维处理的算法获得更好的分类效果：当特征选 择数r 小于1 0 0 0 时，分类的准确性会急剧下降。这种现象符合文献( 苏弛p i 妻器蠢! 鋈旆萌稀i 睢 所有类别文档总 数的比率： e 舰阳一尺= 争 ( 2 3 l f 微观准确率m i c r o - p 是所有类别中被正确分类的文档数e 与被分类算法 识别为相应类别的文 第2 章b b s 数据的特征提取 o 9 4 o ，9 2 o 9 o 8 8 o 8 6 0 8 4 o 8 2 。o 8 0 7 8 o 7 6 o 7 4 o 7 2 图2 1 0m a c r o f i 和特征选择数r 的关系曲线 l23456 789l ol l1 2 高权重词传递个数h 2 9 本章小结 一m a c r o f l ； _ 1 一m i c r o f l 图2 1 1 分类效果利高权重词传递个数h 的关系曲线 本章我们首先对b b s 作了一个简单介绍，分析了b b s 数据的特点，然后介 第3 章聊天室社会网络挖掘中的特征提取 3 2 聊天室数据的特点 与普通的静态长文本相比，聊天数据具有短文本的特性，其特点主要有以 下几个方面： ( 1 ) 将聊天数据拆开来看，每一条聊天消息常常是非常简短的，通常只有一 句话或几个词，有时甚至没有任何意义，属于典型的短文本数据，不能提供充 分的信息进行处理。因此我们没有办法通过对聊天数据的逐条分析来进行数据 挖掘。 ( 2 ) 聊天室中的数据经常含有大量的拼写错误和语法错误，增加了数据预处 理阶段的难度，我们必须想办法除掉这些噪声，修正错误。 ( 3 ) 聊天室中的数据经常包含一些缩写词、生造词或别字，有些甚至已经成 为网络交流中的惯用语。用户常常使用一些特别的词来表示某些信息，比如所 谓的“火星文”等，这些词实际上并不是真f 的单词，但它们在聊天数据中频 繁的出现。 ( 4 ) 聊天数据中包含着多个话题的交错。这是因为在同一个聊天室中，用户 所谈论的话题可能分为多个，但是由于聊天的实时性，多个话题的消息会交替 的出现。 ( 5 ) 聊天室中用户的昵称可以随意更改，我们无法通过昵称来追踪每一个用 户。 3 3 聊天室数据的采集 目前，在网络上的聊天形式主要分为两种：i n s t a n tm e s s a g i n g ( i m ) 和i n t e m e t r e l a yc h a t ( i r c ) 。其中，i n s t a i l tm e s s a 百n g 是一种基于客户端的点对点的网络交 流方式，通常一个话题的讨论只有少数人参加，比较流行的i n s t a n tm e s s a g i n g 软 件如m s n 、q q 和m o om e s s e n g e r 等。而i n t e m e tr e l a yc h a t 是一种基于服务 器的网络交流方式，每个人发送的聊天信息都要首先被传送到一个固定的服务 器，然后再经由这台服务器发送给相应的接收者，比较流行的i n t e m e tr e l a yc h a t 软件有x c h a t 和m i r c 等。 i r c 目前已经成为最普遍的网络聊天方式之一，在一个i r c 服务器上通常 包括几十个甚至上百个的聊天频道，和i n s t a i l tm e s s a g i n g 相比，更容易采集到大 第3 章聊天室社会网络挖掘的特征提取 量的聊天数据，因此我们选用i r c 聊天室作为数据源进行数据采集。我们编写 了一个聊天机器人，它能够自动登录指定的聊天频道，采集到该频道内所有的 聊天数据。 3 4 聊天室数据的预处理 由于从聊天室中获得的数据纷繁芜杂，很多内容对社会网络挖掘来说都是 没有帮助的，所以我们首先要对聊天数据进行预处理，提取出对推断社会网络 有用的信息。该过程包含以下几步： 数据过滤 聊天数据中含有很多类型的消息，包括：j o i n 、q u i t 、n o t i c e 、m e s s a g e 和 n i c k c h a n g e 。“j o i n ”类型的消息表示某用户登录到聊天室；“q u i t ”类型的消息 表示某用户退出了聊天室：“n o t i c e ”类型的消息是聊天室系统向所有用户发布 的公告：“m e s s a g e ”类型的消息是聊天室用户之间实际交流的信息： “n i c k c h a n g e 类型的消息指的是用户昵称的改变。这5 种消息里面，“j o i n ”、 “q u i t 和“n o t i c e ”类型的消息对社会网络的挖掘都是没有帮助的，因此我们 过滤掉这些消息，只保留“m e s s a g e ”和“n i c k c h a i l g e 类型的消息。 特征词提取 聊天数据的特征词提取是指提取出“m e s s a g e 类型消息中的发布时间、昵 称和关键词特征。将这些信息按照一定的格式提取出来，才能交给后面的挖掘 算法处理。 呢称统一 昵称统一处理是指根据“n i c k c h a n g e ”类型的消息将同一用户使用的多个 昵称统一成为其使用的第一个昵称。这样做的目的是为了给每一个用户统一身 份。因为在聊天室中，每一个用户都可以随意地改变其昵称，所以在一个频道 中可能存在一个用户使用多个昵称的情况。在聊天室中，当用户在线改变其昵 称时，聊天室会自动发布一条“n i c k c h a n g e 类型的消息，该消息中包含用户 原来使用的昵称和新的昵称。我们可以通过扫描所有的“m e s s a g e ”类型的消息， 将发送者的昵称统一改成其所使用的第一个呢称。 子话题时间片跨度 我们引入了子话题时间片跨度四，认为硒之内的数据在讨论同一个话题。 3 6 第3 章聊天窒社会网络挖掘中的特缸e 提取 我们将聊天数据划分成大小为弼的一个个时i 日j 片。同时，为了避免将同一话题 的数据分到两个不同的时间片内，我们规定相邻时间片之间有5 0 的重叠。 3 5 基于规则的特征提取方法 如前面的分析，聊天室中的社会网络挖掘是非常困难的。针对这一问题， m u t t o n ( 2 0 0 4 ) 提出的基于聊天室数据时序性特征的挖掘可以说是目前唯一取得 一定成功的方法。该方法的基本思想是在分析聊天数据时序性特征的基础上， 创建出反映用户之间交流关系的规则，然后利用这些规则来挖掘用户之间的交 流关系，即社会网络。m u t t o n 提出了三条启发式规则，并用这些规则来推断社 会网络。该方法