第八章 文本挖掘与WEB挖掘

文本数据挖掘与Web挖掘文本数据挖掘概述文本挖掘出现文本数据属于半结构化数据文本挖掘在1998年4月举行的第十届欧洲机器学习会议上第一次提出。Kodratoff认为文本挖掘的目的是从文档集合中搜寻知识，并不试图改进自然语言理解，并不要求多高的自然语言理解能力，而只想利用该领域的成果，试图在一定的理解水平上尽可能多地提取知识。基本概念文本挖掘是一个从大量文本数据中提取以前未知的、有用的、可理解的、可操作的知识的过程。主要任务文本标引和短语提取概念提取（聚类）可视化显示和导航文本挖掘从功能上的分类文本总结文本分类文本聚类文本总结是指从文档中抽取关键信息,用简洁的形式对文档内容进行摘要或解释.从而用户不需要浏览全文就可以了解文档或文档集合的总体内容.文本总结在有些场合非常有用,例如,搜索引擎在向用户返回查询结果时,通常需要给出文档的摘要.目前,绝大部分搜索引擎采用的方法是简单地截取文档的前几行.文本分类是指按照预先定义的分类体系,将文档集合的每个文档归入某个类别.这样,用户不但能够方便浏览文档,而且可以通过限制搜索范围来使文档的查找更为容易.目前,Ｙahoo仍然是通过人工对Ｗｅｂ文档进行分类,这大大限制了其索引页面的数目和覆盖范围.可以说研究文本分类有着广泛的商业前景和应用价值.文本聚类与分类的不同在于,聚类没有预先定义的主题类别,是一种典型的无教师的机器学习问题.它的目标是将文档集合分成若干簇,且同一簇内的文档相似度尽可能大.聚类的结果可以用来指导分类.文本挖掘与数据挖掘的区别数据挖掘文本挖掘研究对象用数字表示的、结构化的数据无结构或半结构化的文本对象结构关系数据库自由开放的文本目标抽取知识、预测以后的状态检索相关信息、提取意义，分类方法归纳学习、决策树、神经网络、粗糙集、遗传算法标引、概念提取、关联分析、语言学成熟度从1994年开始得到广泛应用从2000年开始得到广泛应用文本挖掘与信息检索的区别信息检索文本挖掘方法论目标驱动，用户需要提出明确的查询要求用户无法预知挖掘结果着眼点着重于文档中的字、词、链接着重于理解文本的结构和内容目的帮助用户发现资源提取文本中隐含的知识评价指标查准率（Precision）、查全率（Recall）收益（Gain）、置信度（Certainty）、简洁性（Simplicity）使用场合从海量信息中定位用户想要的资源层次上高于信息检索，可用来改善信息检索文本特征表示与提取文本特征的表示文档属于半结构化数据，文档的内容的表示使用自然语言，计算机很难处理理解。数据挖掘技术使用结构化的计算机能理解的数据，故需要对文本进行预处理，提取代表其特征的元数据。文本特征分为：描述性特征：文本的名称、日期、大小、类型语义性特征：作者、机构、标题、内容XML等文档结构标准可帮助我们抽取作者、机构等特征，但内容还是难以表示的特征，还是得借助自然语言处理技术矢量空间模型（VSM）在ＶＳＭ中,我们将文本文档视为由一组词条(Ｔ1,Ｔ2,…,Ｔｎ)构成,每一词条都赋以一定的权值Ｗｉ,从而每一篇文档被映射为由一组词条矢量张成的向量空间中的一个向量.文本的匹配问题便可转化为向量空间中的向量匹配问题处理.))(,);......;(,()(11dwtdwtdVnn对于词条权值Ｗｉ的处理,在文本学习中最常用的是ＴＦＩＤＦ表示法,它是一种文档的词集表示法,所有的词从文档中抽取出来,而不考虑词间的次序和文本的结构.)log()()(iiinNdtfdwtfi(d)为ti在d中出现的频率,N为所有文档的数目，ni为含有词条ti文档数目文本特征提取经过以上步骤,得到的特征向量的维数是非常高的,如此高维的特征对即将进行的分类学习未必全是重要、有益的,而且高维的特征会大大增加机器的学习时间而产生与小得多的特征子集相关的学习分类结果.这便是特征提取所要完成的工作.特征提取算法一般是构造一个评价函数,对每个特征进行评估,选取评估分值高的、预定数目的最佳特征作为特征子集.信息论基础它是C.E.Shannon四十年代末期，以客观概率信息为研究对象，从通信的信息传输问题中总结和开拓出来的理论。主要研究的问题：信源的描述，信息的定量度量、分析与计算信道的描述，信道传输的定量度量、分析与计算。信源、信道与通信系统之间的统计匹配，以及通信系统的优化—Shannon的三个编码定理。信息论诞生五十年来，至今，仍然是指导通信技术发展的理论基础，是创新新通信体制的源泉。香农信息(概率信息)信息是事物运动状态或存在方式的不确定性的描述。在通信系统中形式上传输的是消息，但实质上传输的是信息信源信宿信道消息干扰或噪声（发信者）（收信者）通信系统框图样本空间：某事物各种可能出现的不同状态，即所有可能选择的消息的集合。对于离散消息的集合，概率测度是对每一个可能选择的消息指定一个概率。一个样本空间和它的概率测度称为一个概率空间。表示：[X，P]在离散情况下：其中，为选择符号作为消息的概率，称为先验概率)(,),(),(,,,)(2121qquPuPuPuuuuPU)(iuPiu信源数学模型后验概率：条件概率—接收端收到消息（符号）后而发送端发的是的概率。自信息：消息发生后所含有的信息量，反映了消息发生前的不确定性：)|(jivuPjviuiuiu)(log)(1log)(iiiuPuPuI三.信源熵信源熵定义：信源各个离散消息的自信息量的数学期望（即概率加权的统计平均值）为信源的平均信息量，一般称为信源的信息熵，也叫信源熵或香农熵，有时也称为无条件熵或熵函数，简称熵。公式：熵函数的自变量是X,表示信源整体，实质上是无记忆信源平均不确定度的度量。单位：以2为底，比特/符号)(log)(])(1[log)]([)(212iniiiixpxpxpExIEXH信源熵的性质确定性最大离散熵定理：信源X中包含n个不同离散消息时，信源熵H(X)有，当且仅当X中各个消息出现的概率全相等时，上式取等号。表明等概率信源的不确定性最大，具有最大熵，且为P(Ui)互相接近,H(U)就大;反之也然0)0,,1,0()0,,0,1()0,1(HHHn2lognXH2log)(互信息后验熵：当接收到输出符号V=vj后，信源的平均不确定性，即输入符号U的信息度量条件熵：对后验熵在输出符号集V中求期望称为信道疑义度。表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存有不确定性（有疑义），这是由于存在干扰（噪声）引起的。H(U|V)H(U)，表明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。)|(log)|(])|(1[log)]|([)|(212jinijijijijvupvupvupEvuIEvUH)|(log)|()()]|([)|(211jinijinjjjvupvupvpvUHEVUH互信息：先验的不确定性减去收到输出符号集V后尚存在的不确定性，表示收信者获得的信息量)|()(),(VUHUHVUI文本互信息量特征抽取算法（1）初始情况下特征集包含所有该类中出现的词（2）对每个词，计算词和类别的互信息量P(W|Cj)表示词W在类别Cj中出现的比重,P(W)表示W在所有训练文本中的比重))()|(log(WPCWPj其中，||1||1||1),(||),(1)|(VsDiisDiijdWNVdWNCWP（3）对于该类中所有的词，依据上面计算的互信息量排序（4）抽取一定数量的词作为特征项将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示文本分类自动文档分类的一般做法：以一组预先分类过的文档作为训练集，对训练集进行分析以得出分类模式，测试分类模式，不断地细化，之后就用这些模式对其他联机文档进行分类。基于关联的分类方法处理过程：通过信息检索和关联分析提出关键字和词汇使用已经有的词类，或基于专家知识，或使用某些关键字分类方法，生成关键字和词的概念层次或类层次结构词关联挖掘方法用于发现关联词，它可以最大化区分文档的不同类别，这导致对每一类文档有一组关联规则。这些关联规则可以用于对新的文档的分类文本分类具体过程训练阶段定义类别集合C={c1,……,ci,…….cm}给出已分类好的训练文档集合S={s1,……,si,……,sm}对S集中的文档进行词条提取,去除停用词,然后统计词频,每篇文档生成一个向量d计算向量d中每个词条的互信息量,设置初始阈值k0(如0.75),进行维数压缩根据TFIDF公式计算每个词条的权值wi生成特征向量表,每篇文档表示为向量t1,w1;t2,w2;,,tn,wn,ti为特征项词条,wi为对应的权值.对每一类中的特征项词条ti,计算其在该类所有文档特征向量中权值的算术平均值wi,作为该词条在类别特征向量中的权值构造类别特征向量c:t,w;t,w;,,t,w分类阶段对测试文档集合T={d1,……,dk,……,dr}中的每个待分类文档dk，计算V(dk)与每个V(ci)之间的相似度sim(dk,ci)选取相似度最大的一个类别作为dk的类别n(dk,ci)为V(dk)和V(ci)具有的相同词条数,n0(dk,ci)为V(dk)和V(ci)具有的所有词条数.:),(),(),(:0最常用的相似度表示最简单的相似度表示ikikikcdncdncdsim关联分析基于关键字的关联分析首先对文本数据进行分析，词根处理，关键字提取等预处理，然后调用关联规则挖掘算法进行挖掘。每一个文档视为一个事务，文档中的关键字组可视为事务中的一组事务项，这样就可以将文档数据库中的关键字关联挖掘问题变成事务数据库中事务项的关联挖掘词的识别和词级关联挖掘在文本分析中的优点：词和词组被自动标记挖掘算法的执行时间和无意义的结果将极大减少根据用户挖掘的需要，可以使用关联挖掘或最大模式挖掘算法文本聚类文本聚类是一种典型的无教师的机器学习问题。目前的文本聚类方法大致可分为层次凝聚法和平面划分法两种类型层次凝聚法将给定的文档集合D={d1,……,di,……,dn}中的每个文档di看作是一个具有单成员的簇ci={di}，这些簇构成了D的一个聚类C={c1,……,ci,……,cn}计算C中每对簇（ci，cj）之间的相似度sim(ci，cj)选取具有最大相似度的簇对argmaxsim(ci，cj),并将ci和cj合并为一个新的簇ck=ciUcj,从而构成了D的一个新的聚类C={c1,……,ck,……,cn-1}重复上述步骤，直至C中剩下一个簇为止注：该过程构造出一棵生成树，包含了簇的层次信息以及簇间的相似度，是最为常用的聚类方法，但因为要大量计算所有簇间的相似度，所以运行速度慢，不适合于大量文档的集合平面划分法与层次凝聚法的区别在于，它将文档集合水平地分割为若干个簇，而不是生成层次化的簇树。对给定的文档集合D={d1,……,di,……,dn}，该法过程：确定要生成的簇的数目k按照某种原则生成k个聚类中心作为聚类的种子S={s1,……,si,……,sk}对D中的每个文档di,依次计算它与各个种子sj的相似度sim(di,sj)选取具有最大相似度的簇对argmaxsim(di,sj)，将di归入以sj为聚类中心的簇cj，从而得到D的一个聚类C={c1,…,ck}重复步骤2、3、4若干次，以得到较为稳定的聚类结果。注：该方法运行速度较快，但是必须事先确定k取值，且种子选取的好坏对聚类结果有较大的影响Web挖掘Web信息的特点Web信息特别庞大Web信息非常复杂Web信息是动态的Web信息使用者复杂Web信息中“垃圾”非常多Web挖掘分类Web挖掘定义：从的资源和行为中抽取感兴趣的、有用的模式和隐含的信息Web挖掘分类Web内容挖掘Web结构挖掘Web使用记录挖掘Web结构