第八章 文本挖掘与WEB挖掘

1、文本数据挖掘与Web挖掘,文本数据挖掘概述,文本挖掘出现 文本数据属于半结构化数据 文本挖掘在1998年4月举行的第十届欧洲机器学习会议上第一次提出。 Kodratoff认为文本挖掘的目的是从文档集合中搜寻知识，并不试图改进自然语言理解，并不要求多高的自然语言理解能力，而只想利用该领域的成果，试图在一定的理解水平上尽可能多地提取知识。,基本概念 文本挖掘是一个从大量文本数据中提取以前未知的、有用的、可理解的、可操作的知识的过程。 主要任务 文本标引和短语提取 概念提取（聚类） 可视化显示和导航,文本挖掘从功能上的分类 文本总结 文本分类 文本聚类,文本总结是指从文档中抽取关键信息,用简洁的形式

2、对文档内容进行摘要或解释.从而用户不需要浏览全文就可以了解文档或文档集合的总体内容.文本总结在有些场合非常有用,例如,搜索引擎在向用户返回查询结果时,通常需要给出文档的摘要.目前,绝大部分搜索引擎采用的方法是简单地截取文档的前几行.,文本分类是指按照预先定义的分类体系,将文档集合的每个文档归入某个类别.这样,用户不但能够方便浏览文档,而且可以通过限制搜索范围来使文档的查找更为容易.目前,ahoo仍然是通过人工对文档进行分类,这大大限制了其索引页面的数目和覆盖范围.可以说研究文本分类有着广泛的商业前景和应用价值.,文本聚类与分类的不同在于,聚类没有预先定义的主题类别,是一种典型的无教师的机器学习

3、问题.它的目标是将文档集合分成若干簇,且同一簇内的文档相似度尽可能大.聚类的结果可以用来指导分类.,文本挖掘与数据挖掘的区别,文本挖掘与信息检索的区别,文本特征表示与提取,文本特征的表示 文档属于半结构化数据，文档的内容的表示使用自然语言，计算机很难处理理解。数据挖掘技术使用结构化的计算机能理解的数据，故需要对文本进行预处理，提取代表其特征的元数据。 文本特征分为： 描述性特征：文本的名称、日期、大小、类型 语义性特征：作者、机构、标题、内容 XML等文档结构标准可帮助我们抽取作者、机构等特征，但内容还是难以表示的特征，还是得借助自然语言处理技术,矢量空间模型（VSM）,在中,我们将文本文档视

4、为由一组词条(1,2,)构成,每一词条都赋以一定的权值,从而每一篇文档被映射为由一组词条矢量张成的向量空间中的一个向量.文本的匹配问题便可转化为向量空间中的向量匹配问题处理.,对于词条权值的处理,在文本学习中最常用的是表示法,它是一种文档的词集表示法,所有的词从文档中抽取出来,而不考虑词间的次序和文本的结构.,tfi(d)为ti在d中出现的频率,N为所有文档的数目，ni为含有词条ti文档数目,文本特征提取,经过以上步骤,得到的特征向量的维数是非常高的,如此高维的特征对即将进行的分类学习未必全是重要、有益的,而且高维的特征会大大增加机器的学习时间而产生与小得多的特征子集相关的学习分类结果.这便是

5、特征提取所要完成的工作.特征提取算法一般是构造一个评价函数,对每个特征进行评估,选取评估分值高的、预定数目的最佳特征作为特征子集.,信息论基础,它是C.E.Shannon四十年代末期，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题 ： 信源的描述，信息的定量度量、分析与计算 信道的描述，信道传输的定量度量、分析与计算。 信源、信道与通信系统之间的统计匹配，以及通信系统的优化 Shannon的三个编码定理。 信息论诞生五十年来，至今，仍然是指导通信技术发展的理论基础，是创新新通信体制的源泉 。,香农信息(概率信息),信息是事物运动状态或存在方式的不确定性的描

6、述。 在通信系统中形式上传输的是消息，但实质上传输的是信息,信源,信宿,信道,消息,干扰或噪声,（发信者）,（收信者）,通信系统框图,样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息的集合。 对于离散消息的集合，概率测度是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度称为一个概率空间。表示：X，P 在离散情况下： 其中， 为选择符号 作为消息的概率，称为先验概率,信源数学模型,后验概率：条件概率 接收端收到消息（符号） 后而发送端发的是 的概率。 自信息：消息 发生后所含有的信息量，反映了消息 发生前的不确定性：,三.信源熵 信源熵 定义：信源各个离散消息的自信息量

7、的数学期望（即概率加权的统计平均值）为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时也称为无条件熵或熵函数，简称熵。 公式： 熵函数的自变量是X,表示信源整体，实质上是无记忆信源平均不确定度的度量。 单位：以2为底，比特/符号,信源熵的性质,确定性 最大离散熵定理：信源X中包含n个不同离散消息时，信源熵H(X)有 ，当且仅当X中各个消息出现的概率全相等时，上式取等号。 表明等概率信源的不确定性最大，具有最大熵，且为 P(Ui)互相接近,H(U)就大;反之也然,互信息,后验熵：当接收到输出符号V=vj后，信源的平均不确定性，即输入符号U的信息度量 条件熵：对后验熵在输出符号集V

8、中求期望 称为信道疑义度。表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存有不确定性（有疑义），这是由于存在干扰（噪声）引起的。 H(U|V)H(U)，表明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。,互信息：先验的不确定性减去收到输出符号集V后尚存在的不确定性，表示收信者获得的信息量,文本互信息量特征抽取算法,（1）初始情况下特征集包含所有该类中出现的词 （2）对每个词，计算词和类别的互信息量 P(W|Cj)表示词W在类别Cj中出现的比重,P(W)表示W在所有训练文本中的比重,其中，,（3）对于该类中所有的词，依据上面计算的互信息量排序 （4）抽取一定数量的词作

9、为特征项 将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示,文本分类,自动文档分类的一般做法：以一组预先分类过的文档作为训练集，对训练集进行分析以得出分类模式，测试分类模式，不断地细化，之后就用这些模式对其他联机文档进行分类。 基于关联的分类方法处理过程： 通过信息检索和关联分析提出关键字和词汇 使用已经有的词类，或基于专家知识，或使用某些关键字分类方法，生成关键字和词的概念层次或类层次结构 词关联挖掘方法用于发现关联词，它可以最大化区分文档的不同类别，这导致对每一类文档有一组关联规则。这些关联规则可以用于对新的文档的分类,文本分类具体过程,训练阶段 定义类别集合C=c

10、1,ci,.cm 给出已分类好的训练文档集合S= s1,si,sm 对S集中的文档进行词条提取,去除停用词,然后统计词频,每篇文档生成一个向量d 计算向量d中每个词条的互信息量,设置初始阈值k0(如0.75),进行维数压缩 根据TFIDF公式计算每个词条的权值wi 生成特征向量表,每篇文档表示为向量,ti为特征项词条,wi为对应的权值. 对每一类中的特征项词条ti,计算其在该类所有文档特征向量中权值的算术平均值wi,作为该词条在类别特征向量中的权值 构造类别特征向量c:,分类阶段 对测试文档集合T= d1,dk,dr中的每个待分类文档dk，计算V(dk) 与每个V(ci)之间的相似度sim(d

11、k,ci) 选取相似度最大的一个类别作为dk的类别 n(dk,ci)为V(dk) 和V(ci)具有的相同词条数, n0(dk,ci)为V(dk) 和V(ci)具有的所有词条数.,关联分析,基于关键字的关联分析首先对文本数据进行分析，词根处理，关键字提取等预处理，然后调用关联规则挖掘算法进行挖掘。 每一个文档视为一个事务，文档中的关键字组可视为事务中的一组事务项，这样就可以将文档数据库中的关键字关联挖掘问题变成事务数据库中事务项的关联挖掘 词的识别和词级关联挖掘在文本分析中的优点： 词和词组被自动标记 挖掘算法的执行时间和无意义的结果将极大减少 根据用户挖掘的需要，可以使用关联挖掘或最大模式挖掘

12、算法,文本聚类,文本聚类是一种典型的无教师的机器学习问题。目前的文本聚类方法大致可分为层次凝聚法和平面划分法两种类型,层次凝聚法,将给定的文档集合D= d1,di,dn中的每个文档di看作是一个具有单成员的簇ci=di，这些簇构成了D的一个聚类C= c1,ci,cn 计算C中每对簇（ ci，cj）之间的相似度sim(ci，cj) 选取具有最大相似度的簇对arg max sim(ci，cj),并将ci和cj合并为一个新的簇ck=ciUcj,从而构成了D的一个新的聚类C= c1,ck,cn-1 重复上述步骤，直至C中剩下一个簇为止 注：该过程构造出一棵生成树，包含了簇的层次信息以及簇间的相似度，是

13、最为常用的聚类方法，但因为要大量计算所有簇间的相似度，所以运行速度慢，不适合于大量文档的集合,平面划分法,与层次凝聚法的区别在于，它将文档集合水平地分割为若干个簇，而不是生成层次化的簇树。 对给定的文档集合D= d1,di,dn，该法过程： 确定要生成的簇的数目k 按照某种原则生成k个聚类中心作为聚类的种子S=s1,si,sk 对D中的每个文档di,依次计算它与各个种子sj的相似度sim(di, sj) 选取具有最大相似度的簇对arg max sim(di, sj)，将di归入以sj为聚类中心的簇cj，从而得到D的一个聚类C=c1,ck 重复步骤2、3、4若干次，以得到较为稳定的聚类结果。 注

14、：该方法运行速度较快，但是必须事先确定k取值，且种子选取的好坏对聚类结果有较大的影响,Web挖掘,Web信息的特点,Web信息特别庞大 Web信息非常复杂 Web信息是动态的 Web信息使用者复杂 Web信息中“垃圾”非常多,Web挖掘分类,Web挖掘定义：从WWW的资源和行为中抽取感兴趣的、有用的模式和隐含的信息 Web挖掘分类,Web内容挖掘,Web结构挖掘,Web使用记录挖掘,Web结构的挖掘,目的:发现页面的结构和web的结构,在此基础上对页面进行分类和聚类从而找到权威页面 PageRank是典型的Web结构挖掘算法，其基本思想如下: 如果页面u包含一个指向页面v的超链接，即存在lin

15、k(u,v)。页面间的超链接构成了一个有向图G:对于每个页面构成有向图G的一个节点;当且仅当u中包含指向页面v的超链接时，存在着从u到v的有向边(u, v):,对于节点v来说，节点b,c,u对于v的权值大小有贡献，因为这三个节点都存在到v的有向边。指向某一节点的有向边越多，其节点（页面）质量越高。这种简单的算法的主要缺点是仅仅考虑的链接数量（所有的链接都是等价的），而没有考虑源节点自身的质量即权值高低。Web上文档间超链接的情况往往是高质量的文档中包含高质量的链接，源节点的质量对于被链接文档质量评介的作用高于数量上的影响。 为了解决链接数量和源节点的质量问题，斯坦福大学的S.Brin和L.pa

16、ge提出了PageRank算法:某一Web文档的PageRank值等于所有包含指向该文档的源文档的PageRank值与源文档链接总数之比的和，即: 其中。是衰减因子，一般取0.1 - 0.2;n为有向图G中节点的数量; outlink(u)为节点u包含的超链接数量。,Hub/authority方法,现实中当我们搜索某个给定话题的Web页面时，不仅希望得到相关的Web页面，而且希望检索到的Web页面是权威Web页面。也就是说，检索到的页面具有高质量，或对该主题具有权威性。由于Web链接结构对于实现这些需求存在很大的局限性，人们提出了另外一种重要的Web页面，称为Hub页面 Hub页面是指一个或多

17、个Web页面，它提供了指向权威页面的链接集合。Hub页面本身可能并不突出，或者说可能没有几个链接指向它们。但是，Hub页面却提供了指向就某个公共话题而言最为突出的站点链接。此类页面可以是主页上的推荐链接列表，例如一门课程主页上的推荐参考文献站点，或商业站点上的相关信息站点。 Hub页面起到了隐含说明某话题权威页面的作用。通常，好的Hub是指向许多好的权威的页面;好的权威是指由许多好的Hub所指向的页面。这种Hub与authority之间的相互作用，可用于权威页面的挖掘和高质量Web结构和资源的自动发现。这就是Hub/authority方法的基本思想。,HITS算法,算法HITS是利用Hub/a

18、uthority方法的搜索算法，具体算法如下: (1)提交查询词给搜索引擎 将查询词提交普通的基于相似度的搜索引擎，搜索引擎返回n个页面，把这n个页面作为根集S。由根集进一步扩展，加入所有由根集中的页所指的页，以及所有指向根集页的页，扩展为一个更大的集合一基本集T。基本集中的所有Hub页面为集合V1，所有权威Web页面为集合V2。 (2)计算页面的权威权重和Hub权重 给基本集中的每个页面赋予一个非负的权威权重ap，和非负的Hub权重hp，而将所有的a和h值初始为同一常数，如初始值为常数1,Hub权重hp和权威权重ap的计算公式为:,(3)比较、确定页面的权威权重和Hub权重 对页面的权威权重

19、和Hub权重进行计算并且输出一组具有较大权威权重的页面和其较大Hub权重的页面。,Web使用记录的挖掘,除了Web内容和Web链接结构，Web挖掘的另一个重要任务是Web使用记录挖掘，它通过挖掘Web日志记录来发现用户访问Web页面的模式。通过分析和探究Web日志记录中的规律，可以识别电子商务的潜在客户，增强对最终用户的Internet信息服务的品质，并改进Web服务器系统的性能和结构。 Web日志挖掘可以自动、快速的发现网络用户的浏览模式，如频繁访问路径、频繁访问页组、用户聚类等。在用户浏览模式识别的基础上，一种方法是根据这些模式手工改进站点结构，达到方便用户浏览的目的。另外一种更加有效、自

20、动化程度更高的方法是让站点自动根据当前用户的浏览模式来动态调整定制站点结构和页面内容，根据用户的行为特征为其提供个性化服务。 目前研究较多的Web使用记录挖掘技术和工具可分为两大类:模式发现和模式分析。,模式发现,用户访问模式的发现采用了来自人工智能、数据挖掘、信息论等领域的成熟技术，从Web使用记录中挖掘知识。 在模式发现中，首先要解决的问题就是数据的预处理，它主要包括如下两个部分: 数据清洗(Data Cleaning)：包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题; 交易识别(Transaction identification)：是指将页面访问序列划分为代表we

21、b业务或用户会话的逻辑单元。 在对业务进行了划分后，就可以根据具体的分析需求选择访问模式发现的技术，如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。,Web使用记录的常用挖掘算法,统计分析 对Web日志进行统计可以获得有关站点使用的基本信息，如页面访问次数，日平均访问人数，最受用户欢迎的页面等。除此之外，还可以进行有限的错误分析，如非法用户登录等。这些统计数据都是基于用户浏览页面的时间，用户的浏览路径和路径长度等信息。虽然统计提供不能报告深层的数据分析，但是这些统计数据对于提高系统的性能、安全性以及优化站点结构和市场决策大有帮助。目前己有许多Web流量分析工具，如WebTrends等，实现了这些基本的统计功能。,关联规则。 关联规则指发现用户会话中经常被用户一起访问的页面集合，这些页面之间并没有顺序关系。如果关联规则中的页面之间没有超链接，则这是一个我们感兴趣的关联规则。挖掘关联规则通常使用Apriori算法或其变形算法。,聚类 聚类分析是把具有相似特征的用户或数据项规类，它可以帮助进行市场决策。在Web日志挖掘中，聚类分析主要集中于用户聚类和页面聚类。用户聚类将具有相似浏览行为的用户归类，利用这类知识可以在电子商务中进行市场分隔或者为用户提供个性化Web页面内容。页面聚类则是将内容相关的页面归类，搜索引擎可以利用这些信息为用户的查询提供相关的超链接。,分类 分类