ch8 文本挖掘

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第八章 文本挖掘,文本挖掘概念,关于文本挖掘名字,Text Mining,Text Data Mining,Knowledge Discovery in Text,Knowledge Discovery in Textual Data,Text Mining is mainly about somehow extracting the information and knowledge from text,对,KDD,定义进行扩展，文本挖掘是从大量文本数据中抽取隐含的、未知的、可能有用的信息。,文本挖掘,文本挖掘是数据挖掘的一个分支，它是把文本型信息源作为分析的对象，利用定量计算和定性分析的方法，从中寻找信息的结构、模型、模式等各种隐含的知识这种知识对用户而言是新颖的，具有潜在价值。因此，文本挖掘技术的出现为文本信息的整理、分析、挖掘提供了有效手段。,文本挖掘概念,文本挖掘的研究意义,电子化的文本数量不断增长,Web,中,99%,的可分析信息是以文本形式存在的,Web,网页总量超过,100,亿,每天新增网页数千万,机构内,90%,信息以文本形式存在,数字化图书馆、数字化档案馆,数字化办公,传统的检索技术,基于关键词的简单检索,主要应用,新一代搜索引擎,互联网内容安全,互联网非法内容分不,企业知识管理,企业内知识共享、企业相关外部信息,Call center notes categorization,CRM systems,个人智能信息访问,E-mail categorization and routing,研究难点,语言难点：文本不是给计算机阅读的,复杂的语言结构：语法语义,更困难的：歧义,多语言,KDD,算法难点,大规模的数据集,高维,过适应,over fitting,变化的数据和知识,噪声数据,挖掘出的模式的可理解性,文本挖掘模型结构示意图,文本挖掘任务分类,Search and retrieval,Semantic analysis,Clustering,Categorization,Feature extraction,Ontology building,Dynamic focus,应用实例,应用实例,文本特征提取技术,语言特征理解系统,分词,实例,和平民主,和平、民主,和、平民、主,提高人民生活水平,提高、高人、人民、民生、生活、活水、水平,大学生活象白纸,大学、生活、象、白纸、,大学生、活象、白纸,分词,基本方法,最大匹配法,最大概率法,最短路径分词方法,难点,分词歧义,未登录新词,最大匹配法示例,S1=“,计算语言学课程是三个课时”,设定最大词长,MaxLen,=5,S2=“,计算语言学”、“课程”、“是”、“三”、“个”、“课时”,最大匹配法示例,其他基于匹配的分词方法,最大匹配法,逆向最大匹配法,双向匹配法,最佳匹配法,联想,-,回溯法,最大概率法分词,基本思想是：,一个待切分的汉字串可能包含多种分词结果,将其中概率最大的那个作为该字串的分词结果,最大概率法分词,文档模型,布尔模型,向量空间模型,经典概率模型,布尔模型,一种简单的检索模型，它建立在经典的集合论和布尔代数的基础上。,遵循两条基本规则,:,每个索引词在一篇文档中只有两种状态：出现或不出现，对应权值为,0,或,1,。,文档检索,布尔逻辑运算,布尔模型,文档表示,一个文档被表示为关键词的集合,布尔模型,文档表示,优点：简单、易理解、简洁的形式化,缺点：匹配准确性、信息需求能力表达不足,向量空间模型,向量空间模型,(Vector Space Model, VSM),相比于布尔模型要求的准确匹配,Salton,在,60,年代末提出的,VSM,模型采用了,“,部分匹配,”,的检索策略（即：出现部分索引词也可以出现在检索结果中）。,向量空间模型,若干独立的词项被选作索引项,( index terms) or,词表,vocabulary,索引项代表了一个应用中的重要词项,计算机科学图书馆中的索引项应该是哪些呢,?,向量空间模型,这些索引项是不相关的,un-correlated (,或者说是正交的,orthogonal),，形成一个向量空间,vector space,文档集一般表示,向量空间中的,N,个文档可以用一个矩阵表示,矩阵中的一个元素对应于文档中一个词项的权重。“,0”,意味着该词项在文档中没有意义，或该词项不在文档中出现。,TFIDF,举例,文本：“俄罗斯频繁发生恐怖事件，俄罗斯的安全部门加大打击恐怖主义的力度。”,文本间相似性计算,a similarity measure can represent the similarity between two documents, two queries, or one document and one query,􀂙,it is possible to rank the retrieved documents in the order of presumed importance,􀂾,A similarity,measureis,a function which computes the degree of,similaritybetween,a pair of text objects,􀂾,There are a large number of similarity measures proposed in the literature, because the,bestsimilarity,measure doesnt,exist(yet,!),基于概率模型的相关度,查询与文档之间的相关性􀂾,Okapi,系统􀂙,伦敦城市大学开发,􀂙,20,世纪,80,年代末问世􀂙,在,TREC,比赛中，有不少参加者采用,Okapi,系统取得了很好的成绩。􀂙,不过，,Okapi,系统不是免费的，并且不提供源代码,http:/www.soi.city.ac.uk/andym/OKAPI-PACK/index.html,基于,VSM,的相关度计算方法,基于向量空间模型的常用方法􀂙,欧氏距离􀂙,向量内积􀂙,向量夹角余弦,相似度度量,内积,(Inner Product,),文档,D,和查询式,Q,可以通过内积进行计算,:,dik,是文档,di,中的词项,k,的权重，,qk,是查询式,Q,中词项,k,的权重,对于二值向量,内积是查询式中的词项和文档中的词项相互匹配的数量,对于加权向量,内积是查询式和文档中相互匹配的词项的权重乘积之和,内积,举例,内积的属性,内积值没有界限,不象概率值，要在,(0,1),之间,对长文档有利,内积用于衡量有多少词项匹配成功，而不计算有多少词项匹配失败,长文档包含大量独立词项，每个词项均多次出现，因此一般而言，和查询式中的词项匹配成功的可能性就会比短文档大。,余弦,(Cosine),相似度度量,信息检索,Document Retrieval is defined as the,maching,of some stated user query against useful parts of free-text records.,向量空间模型,向量模型的优点在于：,术语权重的算法提高了检索的性能,部分匹配的策略使得检索的结果文档集更接近用户的检索需求,可以根据结果文档对于查询串的相关度通过,Cosine Ranking,等公式对结果文档进行排序,信息检索,信息检索（,information retrieval,，,IR,），将信息按一定的方式组织和存储起来，并根据用户的需要找出有关信息的过程。,发展的几个阶段,手工检索,(,早期,情报检索,),穿孔卡片检索,(1950s),计算机检索,(,面向主题,1960s),联机检索（,1970s,1980s),Web,检索,(1990s),信息检索,信息检索：从非结构化的文档集中找出与用户需求相关的信息,和其他相关技术的区别,和数据库的区别,数据库是结构化数据,和情报检索的区别,情报检索介绍如何利用情报检索工具,信息检索,信息检索系统,主要组件,建倒排索引（,Inverted File,）,每个文档都可以用一系列关键词来表示，从检索目的来说，这些关键词描述了文档的内容。只要找到文档，便可以找到文档中的关键词。,反过来，如果按关键词建立到文档的索引，便可以根据关键词快速地检索到相关文档。,信息检索系统,建倒排索引,具体地，关键词被存储在索引文件,(index file),中,(,比如，按字母顺序存储,),，对于每个关键词，都有一个指针链表，该表中的每个指针指向与该关键词相关的某个文档，所有指针链表构成置入文件,(posting file),。,这种倒排文件的方法几乎被当前所有的商用,IR,系统所采用。,信息检索系统,信息检索系统,信息检索系统,检索性能的评估,系统评价主要包括,功能评价，即评价一个系统是否完成了它所侧重的目标。,性能评价，主要指标是时间与空间的开销。（如：对数据检索系统的评价）,信息检索系统：由于用户的查询请求本身具有模糊性，检出的结果不一定是精确答案。需要依照与查询的相关度，对结果集合的准确度进行评价。其性能评价还包括检索效果的评价。,检索性能评估,评估的类型,实验室评估和真实环境评估，两者不同。有时，结果出入也较大。,由于在实验室封闭环境下的评估具有可重复性，目前仍是主流。,还有对交互查询进行评测，需要考查界面的设计、系统引导、会话持续时间等因素。,检索评估基础,检索评估基础,:,建立在测试参考集和一定的评价测度基础之上。,测试集由一个文档集、一组信息查询实例、对应于每个信息查询实例的一组相关文档（由专家提供）所组成。,检索策略的评估,对一个给定检索策略,S,，,对每个信息查询实例，评测由,S,检出的结果集合与由专家提供的相关文档集之间的相似性，量化这一指标。,关于知识的组织,知识的结构问题和知识是孪生的,结构本身也是知识,Ontologies,杜威十进制系统（图书分类），国会图书馆的目录，,AMS,（美国数学会）的数学知识体系，美国专利内容的类别体系,Web catalogs,Yahoo,，搜狐,&,Dmoz,（,Open Directory,）,共性的问题：,人工维护,中国图书馆图书分类法简表 （,22,类,）,（,5,个大类）,A,马克思主义、列宁主义、毛泽东思想、邓小平理论,B,哲学、宗教,C,社会科学总论,D,政治、法律,E,军事,F,经济,G,文化、科学、教育、体育,H,语言、文字,I,文学,J,艺术,K,历史、地理,N,自然科学总论,O,数理科学和化学,P,天文学、地球科学,Q,生物科学,R,医药、卫生,S,农业科学,T,工业技术,U,交通运输,V,航空、航天,X,环境科学、安全科学,Z,综合性图书,Web catalogs,Tianwang,in Pku,2002,年,Yahoo,！,webpage,Web catalogs,Yahoo,！,分类的概念,分类：给定一个对象，从一个事先定好的分类体系中挑出一个（或者多个）最适合该对象的类别。,􀂙对象：可以是任何东西,􀂙事先定好的分类体系：可能有结构,􀂙最适合：判断标准,􀂾便于今后查找是其最直接、最普遍的应用,分类体系,分类体系一般人工构造,政治、体育、军事,分类系统可以是层次结构,分类模式,二类问题：属于或不属于,多类问题,一个对象可以属于多类,人工方法和自动方法,人工方法,􀂙知识工程的方法建立专家系统,(80,年代末期,),􀂙结果容易理解,􀂙费时费力,MEDLINE(NationalLibrary,of Medicine) $2 million/,yearfor,manual indexing of journal articles,􀂙难以保证一致性和准确性,(40%,左右的准确率,),􀂙专家有时候凭空想象,人工方法和自动方法,􀂾自动的方法,(,学习,),􀂙结果可能不易理解,􀂙快速,􀂙准确率相对高,(,准确率可达,85%,或者更高,),􀂙来源于真实文本，可信度高,文本自动分类定义,Text Categorization (TC),在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。,从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一、一对多的映射。,用数学公式表示如下：,A,为待分类的文本集合，,B,为分类体系中的类别集，,应用领域,门户网站（网页）,􀂾图书馆（电子资料）,􀂾情报,/,信息部门（情报处理）,􀂾政府、企业等（电子邮件）,文本自动分类,基本步骤,定义分类体系,将预先分类过的文档作为训练集,从训练集中得出分类模型（需要测试过程，不断细化）,用训练获得出的分类模型对其它文档加以分类,文本分类基本步骤,文本分类过程,文本分类实例,新闻自动分类,新闻自动分类,Given: Collection of example news stories already labeled with a,category(topic,).,Task: Predict category for news stories not yet labeled.,For our example, well only get to see the headline,（标题）,of the news story.,Well represent categories using colors. (All examples with the same color belong to the same category.),人工标注的样例,什么没看到之前,看见标题,得到分类：政府事务,评价指标,分类结果评估的主要指标,准确率,召回率,F,测度值,评价指标,准确率：所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学公式表示如下：,查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率，其数学公式表示如下：,评价指标,主要指标,准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废，因此，存在一种新的评估指标，,F1,测试值，其数学公式如下：,评价指标,每一个类的评价指标,Precision=a/(,a+b,),􀂙,Recall=a/(,a+c,),􀂙,miss rate=1-recall,􀂙,accuracy=(,a+d)/(a+b+c+d,), error=(,b+c)/(a+b+c+d,)=1-accuracy,􀂙,评价指标,所有类的总体评价,特征选取,特征选取,目的,避免过拟合（,over fitting,），提高分类准确度,如果经过某种学习之后的分类模型，使得训练文档适应得很好（导致很高的自动分类精度），但对训练集之外的文档显得差许多，则称此时的学习模型有,Over-fitting problem,希望模型的表现对训练集和未知文档基本一致。,特征选取,目的,通过降维，大大节省计算时间和空间,样例空间涉及的总词项数很大（,N,在,10,万量级），但每篇文档只涉及其中的一小部分（例如一篇网页通常只有几百个词）（到,1/10,1/100,，甚至更多）,特征选取,基本信念：除那些,stop words,外，还有许多词实际上对分类没什么贡献,􀂾但如何确定这些词？,特征选取的方法,文档频率法（,DF, document frequency,）􀂾,信息增益法（,information gain,）􀂾,互信息法（,mutual information,）􀂾,The test,（,chi-square,，开方拟合检验）,特征选择,-DF,基于DF的启发式要点,太频繁的词项没有区分度,Term的DF大于某个阈值去掉,太稀有的词项独立表达的类别信息不强,稀有词项的全局影响力不大,在训练集中，某些文档如果有某个稀有词项，它们通常也会有一些常见词项（对那一类,）,和通常信息获取观念有些抵触：稀有的更有代表性（这是一种ad,hoc方法，不依据什么理论,）,最容易实现，可扩展性好,特征选择,-,熵,设信息出现（例如“硬币出现某一面”，“一篇文档属于某一类”）的概率空间,p = p1, p2, , pm,在引入某个词项,t,之前，系统的熵（即一个随机文档落入某个类的概率空间的熵）,特征选择,-,熵,在观察到,t,以后，文档落入某个类,ci,的概率就应该是条件概率,P(ci|t,),􀂙,对应于相关表中的,A/A+C,􀂙,注意，对不同的,ci,，每个分量不一定相同,term,类别分布的熵：􀂙,该值越大，说明分布越均匀，越有可能出现在较多的类别中；􀂙,该值越小，说明分布越倾斜，词可能出现在较少的类别中,特征选择,信息增益,信息增益,(Information Gain, IG),：,该,term,为整个分类所能提供的信息量,t,出现与否导致的熵的变化,不考虑任何特征的熵和考虑该特征后的熵的差值,特征选择,互信息,MI,统计语言学建模的一种方法，是评估两个随机变量,X, Y,相关程度的一种度量,其中,P (,x,y,),是变量取值（,x,y,）的概率,特征选择,互信息,MI,X, Y,分别对应词项,t,的出现情况和类别的出现情况,看成随机事件，,t,可能出现,0,1,2,次（取决于要用的文档模型）；,类别有,m,种可能,c=c1,c2,cm,不混淆情况下，用,t, c,表示这两个随机变量,关心的,P(t,),P(c,),P(t,c,),都可以通过统计训练集中的数据情况得到,􀂙如果用二元模型，即前面的,“,相关表,”,就足够，,􀂙如果是多元模型，也容易推广,特征选择,互信息,MI,特点,MI(t,C,),的值越大，,t,对于,C,的区分能力越强,对同一个类，不同的词项，在同样,P(t|c,),情况下，相对稀有的,t,会得到较大的值,MI,还可以解释为给定一个随机变量后另外一个随机变量上的减少,特征选择,（卡方）,源于统计学的卡方分布,(chi-square),从（类，词项）相关表出发,考虑每一个类和每一个词项的相关情况，,chi-,square(t,c,),特征选择,（卡方）,统计量,度量两者,(term,和类别,),独立性的缺乏程度,2,越大，独立性越小，相关性越大,若,ADBC,则类和词独立, N=A+B+C+D,特征选择,实现自动文本分类的方法,分类算法,Rocchio,方法,决策树（,Decision Trees,）,􀂾,KNN,算法,(K-Nearest,Neighbour,),􀂾贝叶斯网络（,BayesNetwork,）,􀂾神经网络（,Neural Networks,）,Classifier :,Rocchio,method,每一类确定一个中心点（代表元），计算待分类的文档与各类代表元间的距离，并作为判定是否属于该类的判据。,构造方法：给定一个类，训练集中所有属于这个类的文档对应向量的分量用正数表示，所有不属于这个类的文档对应向量的分量用负数表示，然后把所有的向量加起来，得到的和向量就是这个类的原型向量,Rocchio,method,定义两个向量的相似度为这两个向量夹角的余弦，逐一计算训练集中所有文档和原型向量的相似度，然后按一定的算法从中挑选某个相似度作为界,给定一篇文档，如果这篇文档与原型向量的相似度比界大，则这篇文档属于这个类，否则这篇文档就不属于这个类。,Rocchio,算法的突出优点是容易实现，计算（训练和分类）特别简单，它通常用来实现衡量分类系统性能的基准系统，而实用的分类系统很少采用这种算法解决具体的分类问题。,Rocchio,method,缺点,:,如果对那些类间距离比较大而类内距离比较小的类别分布情况，,Rocchio,分类器能达到较好的分类精度，而对于那些达不到这种“良好分布”的类别分布情况，,Rocchio,分类器方法效果比较差。,但由于其计算简单、迅速，所以这种方法经常被用于对分类时间要求较高的应用之中，并成为和其他分类方法比较的标准。,决策树方法,决策树方法,构造决策树,􀂙,CART,􀂙,C4.5 (,由,ID3,发展而来,),􀂙,CHAID,􀂾决策树的剪枝,(pruning),KNN,方法,1-Nearest Neighbor,Did anyone try to find the most similar labeled item and then just guess the same color?,􀂙,This is 1-Nearest,NeighborSenate,1-Nearest Neighbor (graphically),KNN,方法,一种,Lazy Learning, Example-based Learning,KNN,方法,优点,简单、有效,(among top-5 in benchmark evaluations),重新训练的代价较低（包括类别体系的变化和训练集的变化，在,Web,环境和电子商务应用中是很常见的）,计算时间和空间线性于训练集的规模,（在一些场合不算太大）,KNN,方法,缺点,不很适合在线分类，响应速度较慢,􀂙,kNN,是懒散学习方法（,lazy learning,基本上不学习），一些积极学习（,eager learning,）的算法要快很多,􀂙其实是一个时间分配问题：学习时间和工作时间的权衡，“磨刀不误砍柴功”？,􀂾类别评分不是规格化的（不像概率评分）,􀂙和其他评分方法的比较，以及和其他评分方法的结合是一个,open problem.,􀂾输出的可解释性不强,􀂙例如决策树方法的可解释性较强,神经网络分类,贝叶斯分类,文本分类小节,自动分类的概念,分类效果的评价,特征选择,文档频率法（,DF, document frequency,）,信息增益法（,information gain,）,互信息法（,mutual information,）,The 2test,（,chi-square,）,􀂾分类算法,􀂙,KNN,􀂙,SVM,文本聚类,Document Clustering (,DC)is,partitioning a set of documents into groups or clusters,Clusters should be computed to,Contain similar documents,Separate as much as possible different documents,For instance, if similarity between documents is defined to capture semantic relatedness, documents in a cluster should deal with the same topics, and topics in each cluster should be different,文本聚类,Guiding the,organizationof,a document collection (e.g. Sahami98),Progressively clustering groups of documents allow to build a topic hierarchy,Supporting browsing and interactive retrieval,Grouping retrieved documents to allow a faster relevant documents selection process,Some search engines (,Vivisimo,),Pre-processing for other tasks, e.g.,To detect the main semantic dimensions of the text collection and to support a kind of concept indexing ,Karypis,& Han 00,For text summarization,文本聚类,文本聚类基本步骤,As other text processing tasks, DC has several steps,Document representation,Dimensionality reduction,Applying a clustering algorithm,Evaluating the effectiveness of the process,文本聚类基本步骤,用户指定用于聚类的数据集合,特征选取,聚合,:,将每个文档分配到相应的类中,标注,:,给每个聚类选择关键词,文档间距离,向量空间模型,(Vector Space Model),􀂙,M,个无序标引项,ti,(,特征,),，词根,/,词,/,短语,/,其他􀂙,每个文档,dj,可以用标引项向量来表示,(a1j,a2j,aMj,),􀂙,权重计算，,N,个训练文档,AM*N= (,aij,),􀂙,相似度计算,Cosine,计算,内积计算,评价指标,准确率（,P, precision,）,召回率（,R, recall,）,F,Measure,􀂾,评价指标,聚类算法评价,聚类方法的好坏：该方法是否能发现某些或所有的隐含模式；,一个好的聚类方法要能产生高质量的聚类结果,簇，这些簇要具备以下两个特点：,高的簇内相似性,低的簇间相似性,聚类结果的好坏取决于：,聚类方法采用的相似性评估方法,该方法的具体实现；,话题检测跟踪技术,Topic Detection and Tracking (TDT),话题识别与跟踪，作为一项旨在帮助人们应对信息过载问题的研究，以新闻专线（,Newswire,）、广播、电视等媒体信息流为处理对象，将语言形式的信息流分割为不同的新闻报道（,News Story,），监控对新话题的报道，并将涉及某个话题的报道组织起来以某种方式呈现给用户。,话题检测跟踪技术,Topic Detection and Tracking (TDT),它的研究目标是要实现按话题查找、组织和利用来自多种新闻媒体的多语言信息。这类新技术是现实中急需的，比如：自动监控各种信息源（如广播、电视等），并从中识别出各种突发事件、新事件以及关于已知事件的新信息，这可广泛用于信息安全、证券市场分析等领域。另外，还可以找出有关用户某一感兴趣话题的所有报道，研究这一话题的发展历程等等。,相关概念,Event (,事件,),A specific thing that happens at a specific time and place along with all necessary preconditions and unavoidable consequences.,Specific elections, accidents, crimes and natural disasters are examples of events.,Eg,. 911,事件,Activity (,活动,),An activity is a connected set of actions that have a common focus or purpose.,Specific campaigns, investigations, and disaster relief efforts are examples of activities.,Eg,.,党的十七大、北京奥运会,相关概念,Topic,（话题、主题）,an event or activity, along with all directly related events and activities,Topic,􀃆,Event, 1,􀃆,n, n 1,Sometimes, Topic Event (99,年前,),Topic Example,WHAT: 35 or 40 young Mountain Hikers were lost in an avalanche in France around the 20th of January.,WHERE:,Orres, France,WHEN: January 4, 1998,相关概念,Story (,报道,),A story is a newswire article or a segment of a news broadcast with a coherent news focus.,They must contain at least two independent, declarative clauses (,子句,).,话题识别与跟踪研究集中于五个子任务,对新闻报道的切分（,Story Segmentation,）：将连续的广播、电视新闻节目的语音或文字记录分割为不同的报道；,新事件的识别（,New event detection,，,Formerly First Story Detection,）：即在新闻报道信息流中识别出对一个新话题的首次报道；,话题识别与跟踪子任务,报道关系识别（,Story link detection,）：判断两个随机选择的新闻报道是否讨论同一个话题；,话题识别（,Topic detection,）：识别出系统未知的话题，并将相关报道也识别出来；,话题跟踪（,Topic tracking,）：监控新闻报道信息流以发现与某一已知话题有关的新报道；,话题识别与跟踪子任务,报道切分,Story Segmentation,报道切分,对新闻报道的切分是指将从一个信息源获得的语言信息流分割为不同的新闻报道。,这一任务只适用于对来自广播、电视等媒体的音频数据的处理。,一段新闻节目通常包含很多条报道，但是这些节目本身很少在不同的新闻报道间设置明显的分隔标记。,比如，商业广告就很可能出现在某篇报道的中间。要切分的语料或数据可以是音频记录本身，也可以是由人工或通过自动语音识别（,ASR, Automatic Speech Recognition,）从音频记录得到的文字记录,新事件识别,新事件识别任务的目标是识别出以前没有讨论过的新闻话题的出现，比如一次炸弹爆炸、火山喷发、某个政治丑闻等等。,这项任务也被看作是对一个话题识别系统的透明测试，因为判断每个报道是否讨论了一个新话题是一个话题识别系统的基础。,新事件识别,圆形和菱形分别代表语料中的两个不同的话题，每个话题有一个最初的报道。,报道关系识别,在报道关系识别任务中，系统对给定的两篇新闻报道做出判断，即它们是否讨论同一个话题。,这项技术是其他几项任务的一个重要的核心技术。一个好的关系识别系统也可用于解决话题跟踪、识别以及对新发生事件的检测等问题。,话题识别,话题识别意在将输入的新闻报道归入不同的话题簇，并在需要的时候建立新的话题簇。,从本质上看，这项研究等同于无指导的（系统无法预先知道该有多少话题簇、什么时候建立这些话题簇）聚类研究。,话题识别,话题识别作为一种增量聚类，可以划分为两个阶段：,识别出新事件的出现；,将描写先前遇到的话题的报道归入相应的话题簇。,话题识别,显然，第一个阶段就是对新发生事件的识别。话题识别任务是对新事件识别任务的一个自然的扩展。,但是，这两项任务的区别也是很明显的：前者关心将谈论某个话题的所有新闻报道归入一个话题簇，如果仅仅不能正确识别出对某个话题的首次报道，问题并不严重；后者则正好相反，它只关心系统能否将引出某个话题的第一篇报道识别出来,话题跟踪,话题跟踪就是要识别出关于某个已知话题的新闻报道，通常要事先给出一个或几个已知的、关于该话题的新闻报道。,这项研究类似于信息检索领域基于例子的查询以及信息过滤研究。,话题跟踪,话题跟踪：监控新闻报道信息流以便发现与某一已知话题有关的新报道；,步骤：首先给出一组样本报道，训练得到一个话题模型，然后系统在后续报道中要能识别出其后关于此话题的所有报道。,实质：显然可以把话题跟踪看作是一种特殊的二元分类问题。,文本分类技术是话题跟踪的基础,话题跟踪,应用,TDTLightHouse,James Allan, University of Massachusetts,马萨诸塞大学,Amherst,分校智能信息检索中心,TDTLightHouse,系统建立在交互式信息检索系统,LightHouse,系统之上,TDT,核心系统则运行在后台,对模拟的新闻信息流进行话题检测，新闻信息流按照话题形成一个个话题类簇,TDTLightHouse,的客户端实时查询检测结果，并以图示化的界面展现给用,TDT,研究历史,话题识别与跟踪的基本思想源于,1996,年，当时美国国防高级研究计划委员会（,DARPA,）提出需要一种能自动确定新闻信息流中话题结构的技术。,随后，来自,DARPA,、卡内基,梅隆大学、,Dragon,系统公司以及麻萨诸塞大学的研究者开始定义话题识别与跟踪研究的内容，并开发用于解决问题的初步技术。这些初始研究及评测后来被命名为,TDT 1997,或,TDT pilot,。,TDT,研究历史,从,1996,年下半年到,1997,年进行的,TDT,初始研究非常成功，它把研究问题以易于处理和能够评测的方式确定下来，标志着话题识别与跟踪这一新的自然语言处理研究方向的正式确立。,TDT,研究历史,为了推动话题识别与跟踪研究的发展，借鉴信息抽取（,MUC,）、信息检索（,TREC,）等研究的成功经验，,DARPA,以及后来的美国国家标准技术研究所（,NIST,）资助并主持了话题识别与跟踪系列评测会议（,TDT,）。这是一种评测驱动的研究方式。从,1998,年到,2002,年，已经成功举办过,5,次大规模的公开评测。,信息过滤,从动态的信息流中将满足用户兴趣的信息挑选出来，用户的兴趣一般在较长一段时间内比较稳定不会改变,(,静态,),。,典型的信息过滤系统,信息过滤系统的特点,新信息的产生速度很快，相对来说，人的兴趣变化比较缓慢，可以看成相对静态的和稳定的。,信息过滤主要借用信息检索和用户建模,(User modeling),两个领域的技术。,用户的需求或者兴趣通常采用,User Profile,建模来表示。,新信息到来的时候，根据用户的,User Profile,，有选择地挑出信息给用户。,信息过滤与信息检索,信息过滤,(IF),与信息检索,(IR),IF,可以看成广义,IR,的一部分，即和,AdhocRetrieval,相对的一种任务模式。,IR,通常采用,Pull,模式，而,IF,通常采用,Push,模式。,和,AdhocRetrieval,相比：,IF,信息源动态，用户需求,(,采用,User Profile,来表示,),相对静态；,IR,信息源相对静态，用户需求,(,采用,Query,来表示,),动态变化,IR,可以认为面向一次性的查询而使用，而,IF,是面向用户的长期需求的重复使用,IF,一般要关注用户建模，涉及用户隐私问题。而,IR,一般不需要。,Ad hoc retrieval,Collection,“Fixed Size”,Q2,Q3,Q1,Q4,Q5,Filtering,Documents Stream,User 1,Profile,User 2,Profile,Docs for,User 1,Docs Filtered,for User 2,信息过滤与信息分类,IF vs. IC (Info. Classification),IF,可以采用,IC,中的分类算法。,某些场合下人们所称的,“,信息过滤,”,实际就是一个,IC,问题。如不经过用户,Profile,调整的垃圾邮件过滤。,IC,中的,Category,通常不会变化，相对而言，,IF,的,User Profile,会动态调整。,信息过滤与信息提取,信息提取,(Information Extraction, IE),是从无格式数据源中抽取相关字段的过程。比如抽取恐怖事件的时间、地点、人物等字段。,IE,中不太关注相关性，而只关注相关的字段。,IF,中要关注相关性。,信息过滤的应用,信息过滤应用,搜索引擎检索结果的过滤：,Google,􀂾个人的邮件过滤,􀂾新闻订阅和过滤,􀂾浏览器过滤,􀂾面向儿童的过滤系统,􀂾面向客户的过滤系统和推荐系统,IF,分类,-,按,Initiative of operation,分,主动,(Active),的,IF,系统,主动搜集信息，并将相关信息发送给用户,通常采用,Push,操作,会造成信息过载问题，所以该系统要尽力建立精确的,User Profile,。,代表系统,BackWeb,被动,(Passive),的,IF,系统,不负责为用户搜集信息,通常用于邮件和新闻组信息过滤,代表系统,GHOSTS,按,Location of operation,分,在信息源端过滤,将用户的,Profile,发送给信息提供者，后者将和用户,Profile,匹配的信息回送给用户,用户通常需要付费，,在过滤服务器端过滤,信息提供者将信息发送给过滤服务器,过滤服务器根据用户的,Profile,将匹配信息发给用户,在用户端过滤,是一个局部过滤系统,如,outlook,的过滤功能。,从过滤方法分,基于感知的过滤,(Cognitive filtering),也称为基于内容的过滤,(Content-based filtering),将文档内容和用户的,Profile,进行相似度计算,基于社会的过滤,(Sociological filtering),也称为协同过滤,(Collaborative filtering),对某个用户的,Profile,进行匹配时，通过用户之间的相似度来计算,Profile,和文档的匹配程度,基于社会过滤的系统常常称为推荐系统,(Recommendation systems),社会过滤常常使用用户建模,(User modeling),及用户聚类,(User clustering),等技术。,社会过滤一般不单独使用，常常和基于内容的过滤配合使用。,基于内容的过滤与协同过滤,垃圾邮件的定义,垃圾邮件是指􀂙向未主动请求的用户发送的电子邮件如广告、刊物或其他资料,;,􀂙或没有明确的退信方法、发信人、回信地址等的邮件,;,􀂙或者利用网络从事违反网络服务供应商的安全策略或服务条款的行为和其他预计会导致投诉的邮件。,垃圾邮件过滤,目前邮件内容过滤技术可以分为两种方法：基于规则和基于统计的方法。,基于规则的方法就是在邮件内容中寻找特定的模式，例如主题包含“免费”。,基于统计的就是使用统计方法解决邮件的二元分类问题，其中分类机跟据垃圾邮件和正常邮件的样本训练出来。在垃圾邮件过滤技术中最常用的统计方法就是贝叶斯准则。,垃圾邮件过滤,基于规则方法的优点是规则可以共享，因此它的推广性很强。一个人写出的规则可以提供给多个人，多个服务器使用。然而它的缺点就是更新速度慢。因为规则一般都是人工编写生成，所以新规则的产生速度跟不上新垃圾邮件出现的速度，换句话说，它的时效性较差。,垃圾邮件过滤,基于统计的方法的优点就是分类机由程序自动训练出来，只要及时更新样本训练集就可以使分类机更新的速度跟得上垃圾邮件出现的速度，即它的时效性很强。然而该方法的缺点就是分类机不能共享，某个用户用自己的邮件样本集训练出来的分类机对其他用户可能效果不佳，因此该方法的推广性较差。,