第 1 页第一章 绪 论§1.1 问题的提出信息技术的飞速发展造成了海量的数据累积。近年来，随着互联网和通信技术的飞速发展，世界上每天都会产生海量的数据，而且这些数据正在以惊人的速度增长。搜索引擎 Google 的数据量在 2000 年就超过了 1.5PB[1]。对于个人数据，根据存储设备提供商 EMC 公司的技术主管 James Rothnie 的报告，美国人平均一生会产生 100GB 的数据，包括金融信息，医疗信息，教育信息等。即时消息工具，电子邮件数据量都达数百TB[1]。网络数据已有大量的积累，根据 Antonio Gulli 的报告[2]，2005 年 1 月份，网络页已经达到 115亿，这个数值仍然在迅速增长。以上统计数据表明，我们已经生活在海量的网络数据中。我们不仅需要对这些网络数据进行合理的存储，并且急需研究网络海量数据处理理论和方法，以得到隐藏在海量网络数据后的潜在有用信息。在金融、商业、政治、军事等领域的网络资源中网络文本资源占了相当大的部分，如何建立合理的模型和选择合适的方法对网络文本进行处理正是本文研究的核心。同时，网络文本做为事件发生的一个主要体现媒介，其对于事件发生和进展的灵敏性使得海量网络文本挖掘对于研究事件发生、发展以及事件之间的相关性关系有重要意义，尤其是证券、军事等领域热点事件的发生与变化对海量网络文本的整体结构和特性有较强的影响。通过对海量网络文本数据的挖掘，能够发现网络文本与实际事件之间的相关性，可以为情报分析中的关联性分析提供支持。有关学者已经在相关领域进行了一些前沿性的研究。如何利用网络文本挖掘技术对政治、经济、军事等领域的文本进行处理以取得有用的信息，为方案制定、决策等活动提供信息支持是目前国际前沿研究热点。§1.2 国内外研究现状在文本挖掘技术中，文本分类是对海量文本进行处理和挖掘的一个重要应用领域，是文本挖掘技术中的基础研究工作。在国外，最初的文本分类是依靠手工进行的，不能满足大规模文本处理的要求，面对海量文本信息，需要发展自动文本分类技术。自动文本分类始于 20 世纪 50 年代末，H. P. Luhn 在这一领域进行了开创性的研究，他将词频统计思想用于文本分类。1960 年，Maron 发表了关于自动分类的第一篇论文[3]。其后 K.Sparck[4]、G.. Salton[5,6]等众多学者在这一领域进行了卓有成效的研究工作。自 20 世纪90 年代以来，基于统计和机器学习的文本分类方法[7]逐渐成为文本分类的主流技术。我国开展文本分类研究起步较晚。1981 年，侯汉清对计算机在文献分类工作中的术大学研究生院硕士学位论文第 5 页（空格），我们需要对已经形成的文本进行中文自动分词处理。汉语自动分词[28]（Automatic Segmentation of Chinese Word）是把输入计算机的汉语自动切分为词的序列的过程。实验证明好的预处理分词关键要有一个好的自动分词算法和建立一个好的词库，目前分词的常用算法有最大匹配法、最大概率法。在对中文文本研究中，经常使用中科院计算所研制出的汉语词法分析系统 ICTCLAS[29]（Institute of ComputingTechnology , Chinese Lexical Analysis System），该系统分词正确率可达 97％以上。3．特征抽取和选择特征抽取可看作从文本空间到特征空间的一种映射(Mapping)或变换(Transform)。特征选择是从一组特征中选出一部分最有代表性的特征。特征选择和特征抽取可以降低特征空间的维数，从而达到降低计算复杂度和提高分类的准确率的目的。特征的抽取一般是通过构造一个特征评价函数，把文本空间的数据投影到特征空间，得到在特征空间的值，然后根据特征空间中的值对每个特征进行评估，选择值最高的若干个特征[30]。常用的评估函数[31,32]主要有文本频率、互信息、2 统计量（CHI）、信息增益、期望交叉熵、优势率、多类优势率、类别区分词、文本证据权、基于词频差异的特征选取等。这些方法各有优劣，在计算复杂度和实际效果上各有偏重，而特征选择的好坏直接影响到挖掘分析的结果。4．特征表示特征表示主要是指利用所选定的特征集合来表示文本，从而将文本处理变为只需对所选择的特征集合进行分析和处理。特征表示模型有多种，常用的有布尔逻辑型、向量空间模型 (Vector Space Model, VSM)等。向量空间模型以所选择的特征项做为维度，将文本表示为高维空间的向量，在进行文本挖掘工作时只需对这些向量进行研究，本文的工作主要是基于向量空间模型。5．文本挖掘对文本进行了基于向量空间模型的特征表示后，原来所研究的目标文本就形式表示为一个高维空间中的向量，这些向量的分量就是经过对文本集合研究所选择的特征集合，我们基于这些向量可以进行文本的分类分析，聚类分析，相关性分析、分布分析、趋势分析等，还可以将文本段落、句子表示成为向量空间中的高维向量，经过提取后实现文本的主题段、主题句提取，实现自动文摘提取技术。2.1.2 向量空间模型（VSM）在该向量空间模型中，文本空间被看作是由一组正交向量张成的向量空间。文本集合被表示为一组高维向量。VSM 提供了一种文本表示的量化方法，向量空间模型中有如下定义[33]：术大学研究生院硕士学位论文第 4 页第二章 网络文本挖掘相关技术研究§2.1 文本挖掘的概念2.1.1 文本挖掘的一般过程网络文本挖掘的主要处理过程是对大量网页和文本进行收集选择，产生对研究目的有用的文本集合进行预处理、特征选择、特征表示、挖掘分析等。图 2.1 给出了文本挖掘的一般处理过程[25]。目 标 文本集合预处理特征选择抽取特征表示数据集挖掘分析可视化用户网络文本资源的收集处理图 2.1 文本挖掘一般过程1．网络文本资源收集及去噪网络文本资源由来自各种网络数据源的大量文本和网页组成，包括新闻网页、学术论文、聊天室的聊天记录、论坛发布的信息、网络对专题的讨论、BBS、数字图书馆、网络评论信息、电子邮件消息等。与传统数据库、数据仓库中结构化的数据不同，网络文本大部分是非结构、半结构性的。网络上大部分的文本既包含了标题、作者、出版日期、出版刊物名等结构化信息，又包含了摘要、内容、参考文献等非结构化信息，特别是很多文本中又加入了超链接的特殊成分。这些文本被称为半结构化文本，它们构成了网络信息源的主体。非结构、半结构的文本没有特定的模型描述，没有固定的数据结构。要对这类的信息进行挖掘，必须进行数据的结构化转换，并进行结构化数据的存储[26]。此外，网络文本处于不断的更新和变化中，对网络文本资源的收集需要从所选取的网络文本信息源进行定时的有目的的采集和处理所需要的网络文本资源，形成可以用于挖掘分析的文本数据库。程序能自动利用网页中超链接来收集相关主题的网页。为了提高数据的质量，需要对文本做去噪处理[27]，如清除图像文件、脚本程序等，从而得到可以为挖掘模型所利用的文本数据资源。2．预处理在对收集的大量网络文本选择去噪后，我们就得到了可以直接为挖掘模型所利用的文本数据集，本文主要的研究对象为中文文本，由于中文文本没有英文明显的分隔符号术大学研究生院硕士学位论文第 3 页然后根据证券价格的波动评价所提取的信息，对文本信息进行评价后，将其相关特征和评价结果写入数据库，建立了基于网络文本特征词的证券价格预测模型。2005 年梁循[23]研究了网络文本的信息流与证券价格波动之间的相关性关系，该模型利用了统计学的工具对二者的相关性进行了分析，给出了一段观察期内的整体相关性，定义了两个指标的评价标准，但没有就二者的相关性关系给出定量关系描述。2006年 Cheryl Aasheim 等[24]基于向量空间模型（VSM）研究了网络文本内容与证券价格波动的相关性，首先从股票论坛、聊天室、公共信息板、新闻网页下载所研究对象的有关网络文本集合，利用文本挖掘的相关技术和算法，用空间向量表示文本，再基于这些空间向量，发现了与价格波动相关的潜在信息。§1.3 本文的主要工作本文首先详细介绍了文本挖掘的基础知识和关键技术，根据本文研究对象的特点进行了实验研究，选择了适合本文研究对象特点的特征选择算法与文本分类算法。然后，利用文本挖掘的的相关技术，提出了基于 F-D 算法的网络事件图模型，通过对海量网络文本处理，形成了以中文特征词为结点的网络事件图，并利用词向量表示事件，研究了事件的相关性。最后对证券价格波动与网络文本信息流的相关性分析建立了模型，进行了实验研究。第二章阐述了文本挖掘的关键技术，介绍了向量空间模型、文本的特征选择算法、文本的分类算法等的基本思想、主要步骤，针对本文所研究的网络文本的特点进行了文本分类实验。第三章利用文本挖掘的的相关技术，提出了基于 F-D 算法的网络事件图模型，构建了中文特征词为结点的网络图，用词向量表示事件，基于该图模型进行事件的相关性分析。对 5.12汶川地震的网络文本进行了实验，研究了所发生事件的相关性。第四章研究了网络文本信息流与证券价格波动强度的相关性，构建了二者相关性研究模型，对国内证券市场进行了实验研究。第五章结束语，对本文的工作进行了归纳和总结，对今后该研究领域的发展方向提出了建设性的展望。最后是致谢和参考文献。术大学研究生院硕士学位论文第 2 页应用作了探讨[8]，并介绍了国外在计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。此后，我国陆续研制出一批计算机辅助分类系统和自动分类系统。近年来人们对文本分类进行了大量的研究，出现了很多文本分类的算法。这些算法主要有贝叶斯方法[9,10,11]、支持向量机方法[10,12,13]、k-最临近（KNN）方法[11,12]等。这些方法针对不同的应用需求，各有其优缺点。在事件相关性研究方面，国外已经有较多的研究成果，2007 年 MIT 的 Peter.Gloor[14,15,16]对互联网个体之间互相通信（email）情况进行研究，发现了互联网中相互联系的个体所表现出的整体特性与事件之间的相关关系。文献[14]将某一领域的科研团体做为研究结点，基于这些团体之间的 email 通信数据库，研究了这些团体的相互交流模式与其团队整体效率之间的相关性关系。文献[16]通过对网络结点相互通信模式的研究，对某些特定群体的行为进行了相关性分析。Heer J. Boyd[17]通过对安然公司网络通信记录的挖掘，发现了该公司内部的交流群体和该公司数据的漏洞。文献[18]通过对通信交流内容进行语义挖掘分析，对社会犯罪网络的内在联系进行了预测。近年来，网络文本挖掘用于事件相关性分析的研究在金融领域有较大的发展。对海量网络文本的挖掘信息与证券价格波动的相关关系的研究是国内外研究的热点。1998年 B. Wuthrich 等[19]研究了网络发布的相关文本与证券价格变化的相关性关系，并将该模型在亚洲的证券市场进行了验证。他们认为由领域专家决定的关键词的频率在股价波动中起着至关重要的作用，该模型首先计算新消息中关键词条的发生率，然后将关键词根据发生率赋予关键词权重，接着基于权重和训练文本集合的各参数产生分类规则，利用产生的规则对新到的证券网络文本进行分类，进而预测股价的结果（升高、降低或是不明显变化），最后将预测结果运用到实际股市的投资决策支持中。图 1.1 B. Wuthrich的相关性研究模型2004 年，Satoru Takahashi[20,21,22]对从网络提取的相关证券分析报告进行特征提取，www.cs.ust.hk/~beat/PredictGenerate rulesApply rulesOld news Old indexvaluesKey wordtuplesToday’snewsIndexvaluesAgent downloading and managing Web data术大学研究生院硕士学位论文第 7 页1 21 21( , )nk kkS d d w w  (2.2)另外一种常用的方法是用欧氏距离来衡量文本之间的距离[34]：21 21 21( , ) | |nk kkS d d w w  (2.3)2.1.3 文本特征选择算法基于向量空间模型对海量文本进行处理时，最大特点和困难是特征空间的高维性和文本向量的稀疏性。在中文文本分类中，通常采用词条作为最小的独立语义载体，原始的特征空间由可能出现在文章中的全部词条构成。而中文的词条总数有二十多万条，这样高维的特征空间对于处理大量文本的各种方法复杂度是非常高的。寻求一种有效的特征选择方法，降低特征空间的维数，提高分类的效率和精度，成为在向量空间模型基础上对大量文本进行处理需要首先面对的重要问题。因此我们需要进行维数压缩的工作，这样做的目的主要有两个：第一，为了提高程序的效率，提高运行速度；第二，所有词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大。为了提高分类精度，对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合。近年来通过对该问题的研究，形成了多种特征选择方法。1． 文本频率（Document Frequency，DF）词条的文本频率是指在训练文本集合中出现该词条的文本数, 采用 DF 作为特征抽取基于如下基本假设：DF 值低于某个阈值的词条是低频词，它们不含或含有较少的类别信息。将这样的词条从原始特征空间中移除，不但能够降低特征空间的维数，而且还有可能提高分类的精度。文本频率是最简单的特征抽取技术，由于其具有相对于训练语料规模的线性计算复杂度，它能够容易地被用于大规模语料统计。DF 方法形式简单，计算快捷，其不足之处在于，低频词可能包含更多有用的信息，而高频词可能包含较少的信息。2. 互信息（Mutual Information，MI）互信息来源于信息论，可由下式近似计算词条t和类别c的互信息[25]：    ( , ), logp t cMI t cp t p c(2.4)其中 p (t  , c )是全部文本集合中属于c类且包含词条t的文本的概率， p (t  )表示包含词条t的文本在总文本集合中的比例， p ( c )表示类别c的文本比例。若t和c无关， MI  t ,c 值自然为零。词条对于整个语料的互信息值为：术大学研究生院硕士学位论文第 6 页定义 2.1 文档：指一般的文献或文献中的片断，通常指一篇文本，记为D。定义 2.2 特征项：是指文本中含有且能够代表该文本性质的基本语言单位，记为T ,包括字、词、短语，概念等。定义 2.3 特征项权重ikw ：表示特征项kT 对文本iD 的重要程度。其计算方法主要利用tf  idf公式，目前存在多种形式的tf  idf公式，常用的归一化公式为：2loglogk iikkikikT DkNtfdfwNtfdf         （2.1）其中iktf 表示特征项kT 在文本iD 中出现的次数，kdf 表示含有特征项kT 的文本数量（即特征的文本频率），kdf 越高意味着特征项kT 区分不同类文本的作用越低； N 为总的文本数，分母为归一化因子；2logkkNidfdf   为逆向文本频率，kidf 越高意味着特征项kT 对于文本的区别作用越大。定义 2.4 向量空间模型：设文本集合中共有n个不同的特征项1 2, ,nT T  T，根据上述归一化公式计算文本 ( 1,..., )iD i  m的特征项权重ikw ，如果把特征项1 2, ,nT T  T看成一个高维坐标系，ikw 为高维坐标系的值，则( ) ( ) ( )1 2( , , , )d d di i i ind  w w  w就是这个高维空间中的一个向量，是文本iD 的向量表示。训练文本集就表示为词频矩阵，词频矩阵就是应用向量空间模型表示文本的一种形式，其表示方法如下：表 2.1 向量空间模型的词频矩阵1Character2Character3CharacternCharacter1File(1)i1w(1)i2w(1)i3w(1)inw2File(2)i1w(2)i2w(2)i3w(2)inw  ( i)ijwmFile( )1miw( )2miw( )3miw( m)inw使用向量空间模型表示文本，就可以使用如下的公式来计算文本之间的距离（如果向量是规范化的，则是向量之间夹角的余弦）：术大学研究生院硕士学位论文第 9 页整个语料的2 值，分别进行检验： 2 2max 1( ) max ( , )mi i t t c (2.9)其中 m 为类别数，从原始的特征空间中移除低于特定阈值的词条保留高于该阈值的词条作为表示文本的特征。5 类别区分词（Category-Discriminating Word，CDW）CDW 强调了词条对于类别的贡献作用，具有极强的类别指示意义，类别区分性较好的词，我们称之为“类别区分词”。其选取方法如下[25]：词条1t 对于类别ic 的后验概率分布为：        1 1 1 2 1 1| , | , , |nDistribute t  p c t p c t  p c t(2.10)其中，  1|ip c t 为贝叶斯后验概率：     111||i iip t c p cp c tp t (2.11)   1111 11|iidkkiV djkj ktf tp t cV tf t (2.12)     1 11|mi iip t p c p t c  (2.13) jktf t 表示词jt 在ic 类的第 k 篇文本中出现的次数。 V 为总词数，  |ip c t 表示文本包含词条t 时属于ic 类的条件概率，  |ip c t 表示文本不包含词条 t 时属于ic 类的条件概率。CDW 的挑选标准为：CDW  t   Max1   Max2(2.14)其中 Max1 为  1|ip c t ， i  1,2,  ,m中的最大值， Max 2为次大值。§2.2 文本分类算法2.2.1 支持向量机用于文本分类支持向量机（Support Vector Machine, SVM）是在统计学习理论的基础上发展起来的一种新的数据挖掘方法。支持向量机适合于解决二分类问题，建立多个支持向量机的分类器可以解决多类文本的分类问题。SVM 的分类原理就是在线性可分的情况下寻找一个最优超平面，使其在误判率最低的前提下达到最优的分类效果。对于一组线性可分术大学研究生院硕士学位论文第 10 页的文本向量，可以利用线性可分问题的 SVM 方法[35]进行求解。设训练样本为1 1( , ), ,( , ),nn n ix y  x y x R， { 1, 1}, 1,iy    i   n。在线性可分的情况下，存在一个超平面使这两类样本完全分开f ( x )  w,  x  b 0(2.15)其中，t nw  R，即1, , 01, , 0iiiw x byw x b        (2.16)w 为权重向量，b 为偏差。即要求点x和x满足：11wx bwx b     (2.17)SVM 选择可以将两类数据线性分离的并能使正反例之间间隔最大的超平面做为最优分类超平面，计算几何间隔 先将w归一化，1, , ,21( , , )21=w wx xw ww x w xww         (2.18)其中  u ,v表示u，v的内积，分类时要求集合间隔 最大，也就是使 w 最小，并且满足( ) 1 0i iy wx  b  (2.19)的条件。在两类样本中，过离最优分割超平面最近的点，作与最优分割超平面平行的两个超平面，位于这两个超平面上的样本使上式等式成立，这些样本称为支持向量。如图落于虚线上的点就是支持向量。术大学研究生院硕士学位论文第 8 页   max 1max ,ni iMI t MI t c (2.5)互信息值越大，词条对于分类的贡献越大。3.信息增益（Information Gain）信息增益根据某个特征项在文本中出现与否来计算它为文本类别预测所贡献的信息量，一般利用某一特征在文本中出现前后的信息熵之差来计算：2 1 22 21 0 11 1( ) ( )log ( ) ( | )log( ) ( | )j j jc m cjIG t p c p t m p c t mp c p c t m        (2.6)其中 p ( c )是训练文本属于类c的分值， ( 1)jp t  和 ( 0)jp t  分别表示包含和不包含jt 的文本的数量。 ( | )jp c t  m表示当文本包含或不包含jt 时，文本属于 c 类的条件概率。在预处理时可以计算所有词的信息增益，去掉那些IG值很低的词。4．2 统计（CHI）基于2 统计的特征选取方法是基于统计中皮尔逊提出的2 拟合检验法，通过构造统计量 2221 1k ki ii iin npnp   （实际频数-理论频数）理论频数(2.7)它的极限分布将服从于自由度为 k  1的2 分布，引入2 统计量被用于衡量一个特征词和一个类别之间的统计独立关系。表 2.2 文本类别与文本频数表其中 A 表示属于ic 类且包含 t 的文本频数，B 表示不属于ic 类且包含 t 的文本频数，C 表示属于ic 类但不包含 t 的文本频数，D 表示不属于ic 类且不包含 t 的文本频数。则 t 对于ic 类的2 值可由下式计算：22( )( , )( )( )( )( )iN AD CBt cA C B D A B C D    (2.8)其中 N 表示总的文本数。分别计算 t 对每个类别的2 值，再用下式计算词条对于T tic A Cic B D国防科学技术大学研究生院硕士学位论文第 11 页图2.2 支持向量机分类在线性可分情况下，求解最优超平面，即为求解二次规划问题21min2. .y ( ) 1 0, 1, ,i iws t wx b i n   (2.20)进行求解得几何间隔为**{sup vector}1 1ii portw (2.21)对x进行测试时，使用* * *1( ) * ,ni i iid x w x b y x x b      (2.22)来确定x的分类。对于非线性可分问题，SVM将低维空间的线性不可分问题映射成为高维空间中的线性可分问题，在高维空间中进行分类。2.2.2 K 近邻（KNN）文本分类算法KNN方法基于类别学习，每个文本代表n维空间中的一个点。当给定一个待分类的测试文本，KNN方法搜索模式空间，找出最接近给定文本的k 个训练样本，称为未知文本的k 个“近邻”。如果这k 个“近邻”中多数文本属于某一类，那么就把测试文本分为哪一类。临近性可以使用21 2 1 21dist(d ,d ) | ( , ) ( , )|nk kkW d t W d t  (2.23)欧式距离来定义。假设在 x的邻近区域集合中共有m 类样本，每个样本的训练文本数