DM 5 文本分类 QBai 21-08-2006

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Web,数据挖掘,:-,文本分类与网页分类,Dr. Qingyuan Bai,School of Computer Science,Faculty of Mathematics and Computer Science,Fuzhou University,Email:,1,文本分类的产生,文本分类作为文本挖掘的一个重要内容，具有十分广泛的应用意义。它的产生是为了,处理大规模电子文档,，帮助人们有效的,检索、查询、过滤和利用信,息,。它能够较好的解决大量文档信息归类的问题，可以应用到很多情况下，包括文章图书分类，文档自动索引、邮件分类、文档过滤、元数据自动生成、类似于,Yahoo,等的,Web,资源层次分类等； 近几年尤其是在,WEB,网页分类上得到广泛的应用。,2,文本分类的定义,文本分类是指根据文档的,内容或属性,将大量的文档归到,一个或多个类别,的过程。文本分类的关键问题是如何构造一个,分类函数或分类模型,(,也称为分类器,),并利用此分类模型将未知文档映射到给定的类别空间。,3,文本分类的一般过程,文本分类一般包括了文本表达、分类器的选择与训练、,分类结果的评价与反馈等过程，如图所示：,文本,集,预处理与,文本表示,分类器,评价,分类结果特征和概要,词典,分类模型,标准结果,特征抽取,4,文本分类的主要功能模块,预处理：将原始语料格式化为同一格式，便于后继的统一处理；,统计：词频统计，项（单词、概念）与分类的相关概率；,特征抽取：从文本中抽出反映文本,主题的特征,；,分类器：分类器的训练；,评价：分类器的输出结果分析。,5,中文文本分类要点,1.,样本集选择：如每类,1000,个样本,2.,分词（切词）,3.,词预处理（去掉无用词，有停用词表）,4.,选特征词（根据词在文本集中的词频，词在文本集各文本出现的次数占文本数的比例或其他方法：,IG,互信息，对文本集中的词排序，加权）,5.,特征选择：按特征词顺序选出由多少词组成向量（样本的表示）,2000-5000,6.,学习方法（,1,）,决策树方法，朴素贝叶斯方法,（,2,）,k-,近邻，,SVM,。,6,文本分类的关键技术,自动分词,文本表示,特征抽取,分类器的构造,质量,评价,7,自动分词技术,在进行文本分类之前要先进行信息预处理，这里信息预处,理是指,抽取,代表文本特征的元数据（,特征项,），通常选用,词作为,文本特征,的元数据。,而中文的预处理要比英文的预处理要复杂的多，因为汉语,的基元是字而不是词，句子中的词语间没有固定的分隔符,（如空格），因此必需对中文文本进行,词条切分处理,。,汉语,自动分词,是机器翻译、文献标引、信息检索、自然语,言理解与处理、文本挖掘等领域的基础。,8,中文自动分词方法,基于,词典和规则,的方法，应用词典匹配、汉语词法、约束矩阵等知识进行分词,基于,统计的方法,:,将汉语基于字与词的统计信息，如相邻字间互信息、词频及相应贡献信息等应用于分词,混和方法,9,中文自动分词方法,(,续,),在以上三种方法的基础上，又可将分词的方法归纳如下 ：,1.,词典匹配法,:,如最大匹配法、逆向匹配法、双向扫描法,2.,设立标志法,:,如切分标志法、统计标引法、多层次列举法,3.,词频统计法,:,如高频优先法、基于期望法、最少分词词频法,4.,联想词群法,:,如联想回溯,AB,法、词链法、多遍扫描联想法,5.,语义语用法,:,如邻接约束法、综合匹配法、后缀分词法,6.,知识与规则法,:,如切词规则法、切分与语义校正法、规则,描述切词法,10,文本表示,向量空间法,（,VSM,Vector Space Mode,）,SOW,（,Set of Word,）文本表示方法,基于文档语义的表示方法,11,文本表示,向量空间法,这种表示方法把文档看作是由一组,正交词条,矢量所组成的矢量空间，每个文档为其中的一个,范化特征矢量,，从而将文档信息的匹配问题转化为向量空间的匹配问题。,向量空间法是用的,最多的一种文本表示方法,，通常用于朴素贝叶斯（,Nave Bayes,）支持向量机（,SVM,）、,K,近邻（,KNN,）、神经元网络方法（,NN,）和,Rocchio,等文本分类算法。,12,文本表示,SOW,SOW,（,Set of Word,）文本表示方法丢弃了关于特征词的词频信息，这类算法只关心某个特征词在,文档中是否出现。,像,C4.5,、,Ripper,、,FOIL,等基于符号表示的规则归纳算法就基于这种表示方式。这类算法不关心特征词出现,次数的多少,，学习到的结果通常是规则的形式，比较容易解释，也比较容易跟专家知识库接口,。,13,文本表示,基于文档语义的表示方法,由于语言中同义词、一词多义现象普遍存在，前面两种表示方式,无法刻画文本的语义信息,，因此基于文档语义的表示方法也是近几年研究的重点,普林斯顿大学,Miller,等人构造的,WordNet,系统是一个比较完整的语义词典。国内李晓黎等人提出一种基于概念推理模型进行文本分类的方法，董振武等人提出的,知网,是一个描述中文概念和概念间关系的语义知识库。,14,特征抽取,虽然对文本的原始描述特征很多（常以数万维计），但这,些特征中的大多数，对文本的最终识别效果并无贡献。在,文本分类方法中，有以下几种具有代表性的识别特征选择,方法，来有效的滤掉那些对最终识别结果无太大贡献的原,始描述特征：,文档频率（,DF,）,信息增益（,IG,）,相互信息 （,MI,）,X,2,统计（,CHI,）,相对信息（,CG,）,15,文档频率（,DF,）,它是指出现,某特征,的文档数与文档总数,之比,。,DF,值较小的特征将被忽略,，其潜在的假设就是文档,频率较小的特征更有可能是干扰噪声，而非有效识别特征。,信息增益 （,IG,）,它是一种在机器学习领域应用较为广泛的,特征选择方法。,公式如下：,其中：,m,为不同类型的文档数；,为某一类,文档集合， 表示,特征,t,不出现。,特征抽取,16,相互信息（,MI,）,它是一种广泛用于建立词关联统计模型的,标准。特征,t,与,C,类文档之间的互信息定义如下：,；,X,2,统计（,CHI,）,它认为特征,t,与,c,类文档之间非独立关系，类,似于具有一维自由度的,X,2,分布,。计算公式如下：,；,其中：,A,为特征,t,与文档,c,类同时出现的次数；,B,为特征,t,出现,而,c,类文档不出现的次数；,C,为,c,类文档出现而特征,t,不出现,的次数；,N,为文档总数,；,D,为特征,t,与,c,类文档均不出现的次数,特征抽取,17,特征抽取,相对信息,（,CG,）,它是一种用于只有正反两种类型样本的,特征性能评估,。,它根据特征,t,在,c,类文档和,c,类出现频率,多寡而形成的,信息熵之差,， 构成了衡量特征,t,优劣的相,对信息。其计算公式如下：,。,根据测试， 信息增益（,IG,）和,X,2,统计（,CHI,）方法具有,明显的优势；而相互信息（,MI,）方法效果最差。,18,文本分类的方法,Nave Bayes,分类法,(,详细介绍,),基于实例的分类法,支持向量机（,Support Vector Machines,，,SVM,）,神经网络,Boosting,回归模型,在线线性分类器,19,文本分类方法,Nave Bayes,分类法,Nave Bayes,分类法假设文本数据为一个参数模型，使,用训练样本进行贝叶斯最小错误率估计（,Bayes,optimal,estimates,）。 对新的测试文档使用贝叶斯规则计算文,档的后验概率，进行分类。之所以称为,Nave,，是因为它,基于贝叶斯假设（,Nave Bayes Assumption,）：,对给定的类内容，样本中的所有属性相互独立。,Nave Bayes,分类器是应用比较广泛的文本分类器，虽然,它易于理解，计算简单，分类效果基本能满足要求， 但,其关于词项独立性的假设受到,很多研究者的质疑。可解释,性不够理想。,20,Nave Bayes,算法步骤,STEP1,:,计算特征词属于每个类别的几率,向量，,其中：,STEP2:,在新文本到达时，根据特征词分词，然后按下面,公式计算该文本 属于类 的几率,：,21,Nave Bayes,算法步骤（续）,在以上公式中， ，,为相似含,义，,为类的总数， 为,在,中的词频，,n,为,特征词总数。,是模型参数。,STEP3:,比较新文本属于所有类的几率，,将其分到几率最大的那个类别中。,22,文本分类方法,KNN,分类法,基于实例的分类法也称为,“懒惰学习系统,（,Lazy Learning,System,），这种方法不建立类别明确的、直接的表达，而是依赖于训练集文档的分类来推断待定文档的类别。,最常见的基于实例的分类器为,KNN,分类器，其基本思想是：,给定一个测试文档，系统在训练集中查找离它最近的,k,个邻,居，根据这些邻居的分类来给该文档的候选分类评分，并用邻居与文档之间的相似度来加权。,KNN,的计算时间和训练文本集的文本数目成线性关系，,分类效果比较好，是最有效的文本分类方法之一,。,23,文本分类方法支持向量机（,SVM,）,支持向量机（,Support Vector Machines,，,SVM,）由,Vapnik,在,1995,年提出，用于解决二分类模式识别问题，而,Joachims,最早将,SVM,方法用于文本分类。 支持向量机集成了降维和分类， 它将文本分类问题变为一系列二分类问题。 从几何上说，支持向量机就是要在,r,维空间中寻找最佳决策面， 该决策面能最好的区分正例和反例，使正例和反例之间的分类间隔最大。,SVM,分类器的文本分类效果很好，是最好的分类器之一。,其缺点是其核函数的选择缺乏指导，,难以针对具体的问题选,择最佳的核函数,； 另外,SVM,训练速度极大的受到训练集规模,的影响，,计算开销比较大。,24,质量评价,在机器学习基础上进行的文本分类使我们得到了隐含的、先前未知的、潜在的知识、规则和信息。但这些信息是否是有价值的或是在某种意义下满足用户目标，这就需要对模型质量进行评价。,用于对学习器进行评估的常用方法有两种：,预留法（,Hold,out,）,保持法,交叉验证法（,Cross,validation,）,25,质量评价,预留法,这种方法把数据集分成训练集和测试集两部分。通常训练集包含初始数据集中的,三分之二数据,，,而其余的三分之一则作为测试数据集,。学习器使用训练集数据来构造分类器，然后使用这个分类器对测试集进行分类，得出的错误率就是评估错误率。,这种方法的优点是速度快，但由于仅使用训练集的数据来构造分类器，因此它没有充分利用所有的数据来进行学习。如果使用所有的数据，可能会构造出更精确的分类器。,26,质量评价,交叉验证法,这种方法把数据集分成,k,个互不相交的数据子集， 大小大致相同。学习器进行,k,次训练和测试； 每一次学习器使用去除一个子集的剩余数据作为训练集，用被,去除,的子集做测试集。取,k,次错误率的平均值作为评估错误率。,这种评估方法准确度的提高是以运行时间为代价的。,通常,预留法评估用在最初试验性场合,，或者多于,5000,条记录的数据集；,交叉验证法用于建立最终的分类器,，或者很小的数据集。,27,质量评价评价指标,在,Web,上检索文本有下列指标：,分类正确率,（,Classification Accuracy,）、,精度,（,Precision,）和,召回率,（,Recall,）、收益（,Gain,）、支持率（,Support,）、置信度（,Certainty,）等来衡量所发现知识的有效性，可用性和可理解性。,28,质量评价评价指标,精确率是所有判断的文本中与人工分类结果吻合的文本所占,的比率，其数学公式表示如下：,精确率（,precision,）,召回率是分类正确的文本数与人工分类应有结果吻合的文本,所占的比率，其数学公式表示如下：,召回率（,recall,）,。,29,质量评价评价指标,准确率和查全率反映了分类质量的两个不同方面，两者必,须综合考虑，不可偏废，因此，存在一种新的评估指标，,F1,测试值，其数学公式如下,：,。,30,网页分类的出现,网页分类是随着互联网上网页数量的增加，在文本分类的基础上发展而来得。,它是,WEB,挖掘的基础和前提。,网页分类技术与文本分类基本相同，但由于网页具有丰富的结构信息，如何利用这些信息来提高分类效果是目前网页分类领域的研究重点。,下面主要介绍一下网页分类中的特征表示。,31,网页分类特征表示,根据,Web,网页的具体特性,一般可以从两个方面来选取网页特征项,:,一,.,提取网页内容中的大段文本,;,二,.,利用网页中的有关标识符及其结构特征 。,32,网页分类特征表示（续）,在网页中可以选为特征项的内容包括：,与,之间的词，它们是用来表示该,网页的标题,的,而一般标题中出现的词往往是网页主题的一个缩影,;,和,之间的词,(,其中是,1,6,的整数,),这些词在网页中表现的是,网页某段落的标题词,具有很强的概括性 ；,33,网页分类特征表示（续）,等等标识符之间的词,它们也都在不同程度上表示了网页中,这些词的重要性,。,标签中的内容虽在浏览器中不显示,但它对于识别网页的类别却可以起很大的作用。,超链是网页中一个很重要的特征，利用网页间的超链关系应该有利于提高分类效果。,A Study of Approaches to Hypertext Categorization,中提出了利用网页之间的超链信息的四种规则：,34,网页分类特征表示（续）,规则,1,：,None,，属于类,A,的网页的邻居与,A,没什么关系。,规则,2,：,Encyclopedia,，属于类,A,的网页的邻居也都属于,A,。,规则,3,：,Co-referencing,，属于类,A,的网页的邻居尽管不属于,A,但主题相同。,规则,4,：,Preclassified,，存在一个网页上的超链所指向的网页都属于同一个类。,35,网页分类特征表示（续）,根据上述链接关系，有以下几种表示网页的方法。,Page Only,（满足,None,）：,特征项为网页页面内的词,。,Linked Words,（满足,Encyclopedia,）,：,特征项是在前者基础上,再把待分类网页的邻居页中的词添加进来。,Tagged Words,（满足,Co-referencing,）,：,特征项是在,Page Only,的基础上，再把待分类网页的邻居网页中的词加前缀后添加进来。,Linked Names,（满足,Preclassified,）,:,仅用待分类网页超链指向的网页的名字来表示,忽略它自己包含的词。,36,网页分类特征表示（续）,下,面是在三个数据集,Hooovers28,、,Hoovers255,、,Univ6,上选择不同的特征项和分类算法得到比较结果 （,F1,）：,37,文本分类和网页分类的进一步研究,新的分类算法的提出。,分类算法的性能对文本分类和网页分类有决定性的影响，如支持向量机（,SVM,）,的出现，使分类精度有了绝对提高，朴素贝叶斯不可超越的。,2.,寻找表示文档的,更本质的表示方法,，如分析网页中的文本和结构的语义信息，或许会取得比单纯用统计信息更好的分类效果。,38,文本挖掘：,NLP,与数据挖掘的结合,一、文本挖掘概述,二、文本分类,三、文本聚类,四、文本摘要,39,一、文本挖掘概述,1.,文本挖掘：从文本中挖掘知识并加以利用,2.,文本挖掘的一般框架：,预处理程序,大量文本,（包括训练文本集合与测试文本集合）,特征提取,规则挖,掘算法,后置处理,知识采掘,规则筛选,模型评估,结果反馈,结果利用,3.,预处理,规范化,过滤无关及次要数据,(,依赖于挖掘目标,);,单词切分；,词性标注；,40,4.,特征抽取与文本表示,特征选取,(,单词,/,短语，语法特征,/,结构标记,/,特殊符号等,),特征集要求：完全性，区分性,文本表示,-,词袋法,V,(,d,),=,（,T,1,，,W,1,；,T,2,，,W,2,；,.,；,T,n,，,W,n,),权值函数,-,词频型：,W,i, k,=,TF,i, k,-,布尔函数：,W,i, k,=1(,当,TF,i, k,=1),或,0(,当,TF,i,k,=0),；,-,平方根函数,:,W,i, k,= (,TF,i, k,),1/2,；,-,对数函数：,W,i, k,=,log(,TF,i, k,+1),-,TF,IDF,函数：,W,i, k,=,TF,i, k,log(,N/N,k,+0.5);,.,41,5.,特征约减与归一化,-,文档频率阈值（门限）：,N,0,-,信息增益：,-,互信息,:,-,期望交叉熵,：,-,文本证据权,-,x,2,统计,(CHI),，单词权,(TS) .,42,1.,目标：,按照预先定义的主题类别,为文档集合中的每个文档,确定一个（或多个）类别,.,2.,方法：,向量空间法（,VSM),，,Bayes,分类器，支持向量机,K-,近邻法，决策树，神经网络，回归模型，,3.,过程,：,确定主题类别,产生训练文本集,-,文本标注,生成分类模型,根据分类模型，计算测试集合中每个文档与各主题类别的相似度,/,距离,/,概率,（需预先确定阈值），确定文档类别,分类模型评价与改进,-,后置处理,二、文本分类,43,三、文本聚类,1.,目标,将文档集合分成若干簇,要求同一簇内文档内容的相似度尽可能大,而不同簇间的相似度尽可能小,.,2.,方法,层次凝聚法（,G_HAC,），平面划分法（,K_means,）,3.,克服独立性假设缺陷,-,特征矩阵与相异矩阵,假设有,N,个文本作为观察样本，每个样本有,q,个特征，那么数据,可以用一个,N*q,特征矩阵来描述，而文本之间的关系可以用一个,N*N,相异,矩阵来描述，矩阵的（,i,j,）元的取值为样本,i,与样本,j,的不同特征数。,44,四、文本摘要,1.,目标,对一篇（或多篇相似）文本的内容进行概括总结，生成其摘要,方便用户浏览,.,2.,方法,Page One,法、结构抽取法、中心词汇法、语言理解法、聚类法,45,文本摘要的出现,自动文本摘要在我们身边随处可见,新闻标题,论文摘要,小说的故事梗概,自动文本摘要产生的必然性,万维网上文本数据的迅速增长，人们很难浏览关于某一主题的所有网页，因此必须借助于自动工具来帮助人们获取信息，自动工具包括搜索引擎、文本分类、文本摘要等。,46,文本摘要的定义,文本摘要是指，从单文本（或多文本）中为特定用户和任务提取出最重要（或最关心的）的信息，形成一个经过删减的版本。,摘要应包含原文的核心内容或用户感兴趣的内容,并以语意连贯的段落乃至篇章形式输出。,摘要应具有概括性、客观性、可理解性和可读性。,47,文本摘要的分类,指示型,和,信息型,（,Indicative/ Informative),：,指示型摘要为还需要进一步阅读原文档的用户提供了参考功能，也就是说,指示摘要,是用来帮助用户决定是否需要阅读原文档的；,信息摘要,在一定程度上覆盖了原文档中所有的重要信息，可以作为原文档的某种替代，而用户就不再需要考虑原文档。,48,提取型,和,摘要型,（,Extraction/Abstract,）,提取型文摘,的内容完全由从输入文档中拷贝的内容组成。因此，一个典型的、压缩率为,10,的提取，将从原文档中拷贝,10,的内容。这,10,的内容指的是以文档中的词，或句子，甚至是段落为基准的提取量；,摘要型,的内容则包含了一些输入文档中没有表达的东西。例如，在摘要中可能加入了对原文的评价等。而摘要中涉及的原文中的,句子也不需要完全对应,。,文本摘要的分类,49,通用摘要,和,特定摘要,（,Generic/Query-based,）,通用摘要面对的是一般的、广泛的用户，基于文本内容的摘要；特定摘要是针对特定领域或人群的摘要，以（主题或查询）为中心的方式产生摘要。,单文档摘要,和,多文档摘要,（,Single-document/Multidocuments,）,单文档摘要是指在一个文档上生成摘要；而多文档摘要是指从一些相关的文档集中生成摘要。,文本摘要的分类,50,摘要过程分为三个阶段：分析、转化、合成。,1,分析：,这一阶段分析输入的文档，构建文本的,内部表示；,2,转化：,又称为提炼，完成文档,从内部表示到摘要表示的转化。,如果对提取的摘要不进行压缩、一致性等后期处理，将直接输出。,3,综合：,摘要表示将还原为,自然语言的形式输出,。,文本摘要的过程,51,自然语言处理的方法,表面级方法,（,Surface-level,）,实体级方法（,Entity -level,）,论述级方法（,Discourse -level,）,机器学习的方法,文本摘要的方法,52,表面级方法指用文本表层特征来表示信息，这些特征被有选择性地结合起来产生一个有效的信息描述函数。这些特征包括：,主题特征（基于短语词频统计的重要特征短语）,;,位置信息（特征在文本、段落中的位置、区域深度、或位于某特殊区域）；,背景（文章标题中出现的短语、文本的起始部分、或用户的查询信息） ；,提示词短语（例如： 表总结的：“总之” ；表强调的：“重要的” 等）,表面级方法,53,基于表面级方法形成文摘过程中,一般先要通过预处理,生成用空间向量来表示的句子和文章。然后可以根据不同的权重或相似度计算方法来选择比较重要的句子。如下述三种方法：,根据,TF-ISF(ISF,与,IDF,对应，表示一个词在句子中出现次数的倒数,),计算每个词的权重，然后计算每个句子的平均权重，最后按照权重排序，挑出前,n,个句子,.,通过欧氏距离,对文中句子进行聚类，从每个类中选出一个句子作代表。,计算每个句子与文档的相关性，选出最高的句子放入摘要，并将该句子中的词从整个文章和其他句子删除，重新计算。,表面级方法,54,表面级方法一,:,Luhn,算法,Luhn,算法的核心思想是为文章中的每一个句子赋予一个意义值，那些具有最大意义值的句子将会被抽取出来作为摘要，其中句子的意义值是通过句中意义词的个数计算得到的。,确定“意义词集”：意义词应该是文章中的“中”频词集。,/,高频词通常为停用词，而低频词又因出现次数太少，没有对表达文章意义有太大贡献。,计算句子权重：,找出句中满足如下条件的区间，即区间两端为意义词，区间中的相邻意义词之间的距离不超过,n,，,n,是一个经验值；然后用区间中意义词个数的平方除以区间的长度，所得的商即为句子的意义值。,55,表面级方法一,:,Luhn,算法,图示句子的意义值为,42 / 7=2.3,。,计算出所有句子意义值后，可依据意义值对整个文章的句子进行排序，按照压缩率选取意义值最大的句子作为摘要输出。,56,表面级方法二,:,Edumundsonian,算法,Edumundsonian,算法依据四种形式特征来对文中的句子,赋予权重。,这四种特征为：,F,（词频）、,T,（标题）、,L,（位置）和,C,（线索词）加权公式为：,57,信息检索系统（,IR,）,问题回答系统（,Q&A,）,智能收集系统,多媒体新闻系统,文本摘要的应用,58,上海交通大学,王永成教授从,80,年代末就开始研究自动摘录技术,1997,年研制了中文文献自动摘要系统。,东北大学,80,年代末,姚天顺教授和香港城市理工大学联合开展了“中文全文自动摘要系统”的研究,该系统采用脚本知识表示,通过与用户交互获取文摘。,复旦大学,吴立德教授等研制的自动文摘系统分析了篇章段落之间的语义联系,建立了语义网,具有一定的篇章理解能力,并能对任意文章给出任意长度的摘要,哈尔滨工业大学,王开铸教授等人提出了偏重于篇章物理结构的“篇章计算模型”,并于,1992,年研制了一个基于篇章理解的军事领域自动文摘实用系统 。,国内研究情况,59,Web,数据挖掘,一、,Web,挖掘概况,二、,Web,搜索引擎,三、,Web,内容挖掘,四、,Web,结构挖掘,五、,Web,使用挖掘,60,一、,Web,挖掘概况,1. Web,挖掘研究的意义,2. Internet,（,WWW,）特点,3. Web,挖掘的含义和研究范畴,61,Web,是大的信息源，如何利用它。,如搜索引擎的开发、维护，搜索引擎的质量和效率的改进与提高，权威页面的确定，,Web,文档分类，,Web Log,挖掘，智能查询，网上信息抽取，信息过滤，信息推荐，,Web,数据仓库的建立等等,。,Web,挖掘研究具有理论和实践上的双重价值。万维网的特点决定了网络挖掘的复杂性，有些是,NP-Hard,问题。,1. Web,挖掘研究的意义,62,2. WWW,特点,海量性,:,当今世界最大、最丰富的信息源，信息内容无所不包,(2),动态性,网上信息不断更新以保持其时效性,网站和网页时刻在增长、变化,(3),分布性,:,网上信息来源于全球，分布于全球，服务于全球,(4),开放性,:,万维网中绝大多数信息是全球开放的,(5),结构复杂性,:,信息结构复杂多样，多数是无结构或半结构化的,63,Web,内容挖掘,:,基于网页内容及其描述,Web,结构挖掘,:,基于,WWW,组织和超链结构,Web,使用挖掘,:,基于用户对,WWW,的存取行为,3. Web,挖掘研究范畴,64,Web,挖掘,Web,结构挖掘,Web,内容挖掘,Web,使用挖掘,网页,内容,挖掘,检索,结果,挖掘,定制,使用,跟踪,存取,模式,挖掘,网络,组织,挖掘,网络,引用,挖掘,图,1,网络挖掘的研究范畴,媒体,信息,挖掘,65,1.,搜索引擎的评价指标,查全率,(,召回率,),检索到的信息条目数与满足条件的目标信息条目数的比率,查准率,(,精度,),检索到的,相关,信息条目数与检索到的信息条目数的比率,检索耗时,二、,Web,搜索引擎,(Search Engine),66,2.,搜索引擎主要类型,(1),人工维护搜索索引型,优点,:,准确率高,速度快,缺点,:,覆盖面窄,跟不上信息的快速增长,典型,: Yahoo!,虚拟图书馆,(,如,OCLC),(2),Internet,网络搜索蜘蛛,特点,:,覆盖面宽,分类自动化程度高,缺陷,:,准确度低,需用户自己过滤信息,典型,: Alta Vista, Lycos, Excite,67,(3) (,多,),元搜索引擎,(,中介引擎,),特点,:,自身不具备搜索索引,依靠其它搜索,引擎并综合处理检索结果,;,覆盖面广,缺陷,:,对特定领域的针对性差,典型,:Inference Find,Dogpile, Metafind,(4) URL,直接检索式,(5),综合搜索引擎,上述搜索引擎的结合,68,3.,检索方式,基于层次主题方式,基于关键词,/,短语,/,字段,/,逻辑限定方式,基于自然语言理解方式,基于挖掘语言的检索方式,(SQL,式,),WebSQL,WebOQL,W3QL,WebLog,UnQl,WebML,4.,搜索引擎结构,(1),信息采集器,(Agent,Robot),(2),文本分析与分类器,(3),信息存储,(,索引表,),(4),检索界面,69,有用信息匮乏,检索方式有待进一步改进,检索召回率和精度低,跟不上信息的快速增长和变化,为用户提供的检索导航信息缺乏,为用户定制服务能力差,Web,挖掘试图解决上述问题,5.,搜索引擎存在的问题,70,研究主要集中在,:,Web,信息表示和描述、信息采集、过滤和提炼、 重复数据消除、 数据模式抽取、数据模型表示、异构集成和存储、网页分类、聚类与摘要、 基于文本内容的查询和优化、数据仓库及,OLAP,以及基于,XML,的上述专题研究。,三、,Web,内容挖掘,71,是基于,WWW,组织、,Web,文档结构和超链接关系,的,Web,挖掘形式,不仅仅局限于文档之间的超链结构,还包括文档内部的结构、文档,URL,中的目录路径结构等。该种挖掘方式很少单独进行，一般与,Web,内容挖掘、,Web,使用挖掘相结合。,1.,网络虚拟视图生成与网络导航,2.,信息分类体系与索引结构重组,3.,利用超文本结构信息进行文本分类,4.,根据引用关系确定网页重要性,四、,Web,结构挖掘,72,从用户对网络的使用方式和行为中挖掘有用模式，主要是针对,Web access Logs,的挖掘,目标,：（,1,）分析系统性能（根据用户行为预测最佳搜索路径）,（,2,）改进系统设计,（,3,）理解用户意图,相关研究,：,（,1,）用于导航的用户虚拟视图生成,（,2,）基于用户群体共同兴趣的信息推荐,（,3,）基于用户个性化搜索兴趣模式学习的服务定制,（,4,）用户访问行为预测,/Markov,模型,五、,Web,使用信息挖掘,73,0. Web,使用信息挖掘综述,1/7,文献,1,提出最大前向引用的概念,用于在,Web,日志预处理阶段辩识用户访问事务,;2,从,Web,日志中发掘频繁访问路径,;3,利用,Web,日志对,Web,访问者进行聚类,.,Web,使用信息挖掘包含三个阶段,:,数据预处理、模式发现、模式分析和应用。,数据预处理,可使用的数据,:IP,地址、页面访问时间,/Web Log,内容数据：,Web,页面的实际数据,/,页面抽取,结构数据,: Web,页面之间的链接,74,0. Web,使用信息挖掘综述,2/7,数据预处理的结果,:,一个页面集合,P=p1,p2,pn,和一个用户事务集,T=t1,t2,tm,其中,ti,是,P,的子集,.,从概念上讲,我们可以把每一个事务,t,看成是一个具有,k,长度的序列对,t=, p,i,t,为页面,w,i,t,为,p,i,在事务,t,中的权,.,用户事务可以被看成集合（不考虑页面间的顺序），也可以被看成序列（考虑页面间的顺序）。对于序列分析和频繁浏览模式的发掘，必须保留事务中的顺序信息。对于聚类、分类和关联规则发掘，可以把用户事务看成集合，表示成,n,维页面向量，分量是页面在事务中的权重，这样得到（,m,n,）的用户事务,-,页面矩阵。,75,0. Web,使用信息挖掘综述,3/7,模式发现：,关联规则挖掘技术：在事务中发掘页面与页面之间的非序列关系。关联规则的生成基于页面在事务中的共现模式，即关联规则中的页面经常在同一个会话中被访问。,/,不考虑页面之间被访问的顺序。,序列模式：在时间戳有序的事务集中找出这样的内部事务模式，即一些页面被访问后紧接着另一些页面也被访问了。,Markov,模型常用来发掘序列模式。,76,0. Web,使用信息挖掘综述,4/7,通常地，一个,Markov,模型由一个状态集合,s1,s2,sn,和一个状态转移概率矩阵,M,组成，其中,M=(Pi,j),n,n, pi,j,表示从状态,si,转移到状态,sj,的概率。可以用,Markov,模型对页面访问序列进行建模，把从一个页面的访问到另一个页面的访问看成是状态的转移，用,Markov,链描述页面访问之间的概率转移。,聚类：可以进行两种聚类，即用户聚类,(,具有相似浏览模式的用户类,),和页面聚类,(,具有相关内容的页面类,),。,PageGather,算法,4,5,基于页面在用户访问会话中的共现对,Web,站点的页面作聚类。对聚类结果中的每一个簇，系统自动生成一个包含该簇中所有页面链接的,Web,页面，称为索引页面。每一个索引页面反映了一组用户可能具有的共同兴趣。,77,0. Web,使用信息挖掘综述,5/7,模式发现：,聚类：,6,基于,Web,服务器日志对,Web,页面进行聚类。,7,对用户的评价记录进行聚类，作为协同过滤的先前步骤，以弥补,KNN,算法的规模问题。,分类：在,Web,使用信息挖掘中，分类可用于为一组特定用户建立简档,为此需要抽取并选择最能描述这组特定用户的特征,.,分类可以用有指导的学习算法,比如,决策树、,Bayes,分类器、,KNN,分类器、,SVM,等。,78,0. Web,使用信息挖掘综述,6/7,模式分析和应用：,Web,个性化：目标是根据用户偏好向用户动态地提供特定内容，即，把当前用户的会话和通过挖掘得到的使用模式进行匹配,得到该用户的兴趣偏好,然后根据这个预测,向该用户推荐一组对象,如链接、广告等。,8,9,把关联规则挖掘技术应用于推荐系统。,9,提出,top-N,推荐系统。首先系统从订购信息中挖掘出关联规则，然后把消费者的历史订购信息和规则左部进行匹配，找出其支持的所有规则，把这些规则的右部（商品）按可信度向消费者推荐头,N,个商品。,10,提出把语义知识集成到基于,Web,使用信息挖掘的个性化过程中。,79,0. Web,使用信息挖掘综述,7/7,1M.Chen. Data mining for path traversal patterns in a Web environment. CDCS96.,2H.Mannila. Discovering generalized episodes using minimal occurrences. KDDM96.,3T.Yan et al. From user access patterns to dynamic hypertext linking. W3C96.,4M.Perkowitz, O.Etzioni. Towards adaptive Web sites: Conceptual framework and case study. AI118(2000),245-275.,5M.Perkowitz, O.Etzioni. Adaptive Web sites: Automatically synthesizing Web pages. AAAI98.,6,苏中 等，基于,Web-Log Mining,的,Web,文档聚类，软件学报，,2002,。,7M.O Conner et al., Clustering Items for Collaborative Filtering. SIGIR99.,8B.Mobasher et al., Elective Personalization Based on Association Rule Discovery from Web Usage Data. WIDM2001.,9B.Sarwar et al., Analysis of Recommender Algorithms for EC. EC2000.,10H.Dai et al., Integrating Semantic Knowledge with Web Usage Mining for Personalization.,80,1.,路径聚类,:,在,Web,站点中的知识发现,1,Web站点的结构图:K-paths聚类,N11,N23,N21,N22,N32,N43,N41,N42,N34,N44,N31,N45,N33,81,1.,路径聚类,:,在,Web,站点中的知识发现,2,假设一个页面中有,k,个链接,一个用户面对该页面中的这些链接进行访问,如果他首先访问第,l,个,那么代表了他对该链接所达的页面的兴趣要大于其它链接所达的页面,即,Interest(l)Interest(l), l=l,k, ll,即,用户对,Web,站点的访问存在某种有序关系,这种有序关系反映的是用户的一种访问兴趣,.,先访问的节点具有较大的访问兴趣,因此需要一种聚类方法把这种有序关系挖掘出来,.,即,从用户的访问日志中得到具有相似用户访问兴趣的聚类,.,聚类之前先要在,Web,的日志中识别用户访问事务,.,在,Log,中根据某个时间窗口找到每一个访问者的访问记录集,称为该访问者的一个访问事务,t=,它相当于一个用户对站点的一条访问路径,.,全体用户的访问事务集就是他们在一个时间段内对站点的访问路径集,.,然后按路径进行分割聚类,.,82,2.,在,Web,站点中用,Markov,链来做链接预测,1,本文提出一种基于用户过去访问行为的,markov,模型来做链接预测。,1.,首先建立,markov,模型，主要是对服务器的日志进行处理。构造出整个网站的链接结构，包含页面；链接；权,(,页面之间连接被访问的次数,),。,Markov,模型是一个矩阵，它的横纵两列表示页面，对应的交叉点表示两个页面之间发生跳转的概率。,2.,下一步,对上面建立起来的,markov,转变阵进行矩阵压缩，矩阵压缩是采用比较矩阵的内连相似度与外连相似度，而总的相似度是二者相乘，当小于我们所设定的,值，我们就认为这两行,(,列,),是可以合并的。最后产生了压缩后的,markov,转变阵。,3.,提出了一种矩阵压缩算法来聚合类似的用户访问行为，对矩阵的压缩，主要的目的是能够提高预测的速度。,83,2.,在,Web,站点中用,Markov,链来做链接预测,2,4.,用最大前向路径的方法使得预测更有效。最大前向路径是对部分用户访问数据中出现的页面回退的现象进行处理，如果用户访问了某页面后回退，这时我们认为它所访问的页面是不重要的，把它抛弃掉。,5.,最后是一个,m,序,n,步的,markov,预测。,m,序,n,步的,markov,预测是根据前面所访问的,m,个页面预测接后面将要访问的,n,个页面，即,能够一次预测,n,个页面而不仅仅是预测一个页面。,84,Thank you!,85,