文本挖掘.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,2025/10/14 周二,1,主要内容,文本挖掘的背景,文本挖掘的过程,特征抽取,特征选择,文本分类,文本聚类,模型评价,2025/10/14 周二,2,文本挖掘的背景,传统的自然语言理解是对文本进行较低层次的理解，主要进行基于词、语法和语义信息的分析，并通过词在句子中出现的次序发现有意义的信息,。,文本高层次理解的对象可以是仅包含简单句子的单个文本也可以是多个文本组成的文本集，但是现有的技术手段虽然基本上解决了单个句子的分析问题，但是还很难覆盖所有的语言现象，特别是对整个段落或篇章的理解还无从下手。,将数据挖掘的成果用于分析以自然语言描述的文本，这种方法被称为文本挖掘,(Text Mining),或文本知识发现,(Knowledge Discovery in Text).,2025/10/14 周二,3,文本挖掘的背景（续）,文本挖掘与数据挖掘的区别：,文本挖掘：文档本身是半结构化的或非结构化的，无确定形式并且缺乏机器可理解的语义；,数据挖掘：其对象以数据库中的结构化数据为主，并利用关系表等存储结构来发现知识,因此，数据挖掘的技术不适用于文本挖掘，或至少需要预处理。,2025/10/14 周二,6,提纲,文本挖掘的背景,文本挖掘的过程,特征抽取,特征选择,文本分类,文本聚类,模型评价,国内外研究状况,2025/10/14 周二,7,文本特征抽取,定义：文本特征指的是关于文本的元数据,分类：,描述性特征：文本的名称、日期、大小、类型等。,语义性特征：文本的作者、标题、机构、内容等。,2025/10/14 周二,8,特征抽取,(feature extraction),预处理,去掉,html,一些,tag,标记,禁用词,(stop words),去除、词根还原,(stemming),(,中文,),分词、词性标注、短语识别、,词频统计,TF,i,j,:,特征,i,在文档,j,中出现次数，词频,(Term Frequency),DF,i,:,所有文档集合中出现特征,i,的文档数目，文档频率,(Document Frequency),数据清洗：去掉不合适的噪声文档或文档内垃圾数据,文本表示,向量空间模型,降维技术,特征选择,(Feature Selection),特征重构,(Re-parameterisation,，如,LSI),2025/10/14 周二,9,文本表示,向量空间模型,(Vector Space Model),M,个无序标引项,t,i,(,词条项,特征,),，词根,/,词,/,短语,/,其他,每个文档,d,可以用标引项向量来表示,权重计算，,N,个训练文档,W,M*N,=(w,ij,),词项的权重,:0,1,tf(,词频,=term frequency),tf*idf,2025/10/14 周二,10,文本表示,词频矩阵,行对应关键词,t,，列对应文档,d,向量,将每一个文档视为空间向量,v,向量值反映单词,t,与文档,d,的关联度,矩阵元素可以是词频，也可以是布尔型。,表示文档词频的词频矩阵,d,1,d,2,d,3,d,4,d,5,d,6,t,1,322,85,35,69,15,320,t,2,361,90,76,57,13,370,t,3,25,33,160,48,221,26,t,4,30,140,70,201,16,35,2025/10/14 周二,11,中文特征词,(Term),的粒度,Character,，字：中,Word,，词：中国,Phrase,，短语：中国人民银行,Concept,，概念,同义词：开心 高兴 兴奋,相关词,cluster,，,word cluster,：葛非,/,顾俊,N-gram,，,N,元组：中国 国人 人民 民银 银行,某种规律性模式：比如某个,window,中出现的固定模式,2025/10/14 周二,12,主要的分词方法,最大匹配法（,Maximum Matching method,MM,法）：选取包含,6-8,个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。,逆向最大匹配法（,Reverse Maximum method,RMM,法）：匹配方向与,MM,法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。,双向匹配法（,Bi-direction Matching method,BM,法）：比较,MM,法与,RMM,法的分词结果，从而决定正确的分词。,最佳匹配法（,Optimum Matching method,OM,法）：将词典中的单词按它们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词排在后，从而提高匹配的速度。,联想,-,回溯法（,Association-Backtracking method,AB,法）：采用联想和回溯的机制来进行匹配。,2025/10/14 周二,13,英文特征词,一般采用,keyword,无需分词,单词之间有空格分开。,停用词,（,stop word,）,，指文档中出现的连词，介词，冠词等并无太大意义,的,词。例如,在英文中常用的停用词有,the,，,a,it,等；在中文中常见的有“是”，“的”，“地”等。,索引词（标引词，关键祠）,:,可以用于指代文档内容的预选词语,一般为名词或名词词组。,词干提取,countries=country,，,interesting=interest,2025/10/14 周二,14,权重计算方法,布尔权重,(boolean weighting),a,ij,=1(TF,ij,0)or(TF,ij,=0)0,TFIDF,型权重,TF:a,ij,=TF,ij,TF*IDF:a,ij,=TF,ij,*log(N/DF,i,),TFC:,对上面进行归一化,LTC:,降低,TF,的作用,基于熵概念的权重,(Entropy weighting),称为,term i,的某种熵,如果,term,分布极度均匀：熵等于,-1,只在一个文档中出现：熵等于,0,2025/10/14 周二,15,特征选择,(1),基于,DF,Term,的,DF,小于某个阈值去掉,(,太少，没有代表性,),Term,的,DF,大于某个阈值也去掉,(,太多，没有区分度,),信息增益,(Information Gain,IG),：该,term,为整个分类所能提供的信息量,(,不考虑任何特征的熵,和,考虑该特征后的熵,的差值,),2025/10/14 周二,16,特征选择,(2),term,的熵：该值越大，说明分布越均匀，越有可能出现在较多的类别中；该值越小，说明分布越倾斜，词可能出现在较少的类别中,相对熵,(not,交叉熵,),：也称为,KL,距离,(Kullback-Leibler divergence),，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。,2025/10/14 周二,17,特征选择,(3),2,统计量：度量两者,(term,和类别,),独立性的缺乏程度，,2,越大，独立性越小，相关性越大,(,若,ADBC,则类和词独立,N=A+B+C+D),互信息,(Mutual Information),：,MI,越大,t,和,c,共现程度越大,A,B,C,D,t,t,c,c,2025/10/14 周二,18,特征选择,(4),Robertson&Sparck Jones,公式,其他,Odds:,Term Strength:,2025/10/14 周二,19,特征选择方法的性能比较,(1),2025/10/14 周二,20,特征选择方法的性能比较,(2),2025/10/14 周二,21,特征选择方法的性能比较,(3),YangYi-ming,2025/10/14 周二,22,特征重构,隐性语义索引,(LSI),奇异值分解,(SVD),：,A=(a,ij,)=U,V,T,A,M*N,U,M*R,R*R,(,对角阵,),V,N*R,R=MIN(M,N),取,对角上的前,k,个元素，得,k,A,k,=,U,k,k,V,k,T,U,k,由,U,的前,k,列组成，,V,k,由,V,的前,k,列组成,文档,d,在,LSI,对应的向量,d,=d,T,U,k,-1,在已有的,LSI,中增加新的,word,或者,document,，不需要重新计算,Folding-in,方法,SVD-updating,方法,2025/10/14 周二,23,提纲,文本挖掘的背景,文本挖掘的过程,特征建立,特征选择,文本分类,文本聚类,2025/10/14 周二,24,文本分类,定义：给定分类体系，将文本分到某个或者某几个类别中。,分类体系一般人工构造,政治、体育、军事,中美关系、恐怖事件,分类系统可以是层次结构，如,yahoo!,分类模式,2,类问题，属于或不属于,(binary),多类问题，多个类别,(multi-class),，可拆分成,2,类问题,一个文本可以属于多类,(multi-label),这里讲的分类主要基于内容,很多分类体系,:Reuters,分类体系、中图分类,2025/10/14 周二,25,文本分类的过程,文本表示,训练过程,分类过程,训练文本,统计,统计量,特征表示,学习,分类器,新文本,文本特征表示,类别,2025/10/14 周二,26,自动文本分类方法,Rocchio,方法,Na,ve Bayes,kNN,方法,决策树方法,decision tree,Decision Rule Classifier,The Widrow-Hoff Classifier,神经网络方法,Neural Networks,支持向量机,SVM,基于投票的方法,(voting method),2025/10/14 周二,27,Rocchio,方法,可以认为类中心向量法是它的特例,Rocchio,公式,分类,类,C,中心向量的权重,训练样本中正例个数,文档向量的权重,2025/10/14 周二,28,Na,ve Bayes,参数计算,Bayes,公式,2025/10/14 周二,29,kNN,方法,一种,Lazy Learning,Example-based Learning,新文本,k=1,A,类,k=4,，,B,类,k=10,，,B,类,带权重计算，计算权重和最大的类。,k,常取,3,或者,5,。,2025/10/14 周二,30,决策树方法,构造决策树,CART,C4.5(,由,ID3,发展而来,),CHAID,决策树的剪枝,(pruning),2025/10/14 周二,31,Decision Rule Learning,wheat&form,WHEAT,wheat&commodity WHEAT,bushels&export WHEAT,wheat&agriculture WHEAT,wheat&tonnes WHEAT,wheat&winter&soft WHEAT,(,粗糙集,)RoughSet,逻辑表达式,(AQ11,算法,),学习到如下规则,2025/10/14 周二,32,The Widrow-Hoff Classifier,Online Learning,类,c,向量的第,j,个分量,x,i,的第,j,个分量,Learning Rate,Target Value(0 or 1),2025/10/14 周二,33,Neural Network,.,.,.,.,.,c,1,c,2,c,n,Input Layer,Hidden Layer,Output Layer,Backpropagation,2025/10/14 周二,34,支持向量机,Support Vector Machine,Support Vector,Optimal,Separating,Hyperplane,2025/10/14 周二,35,基于投票的方法,Bagging,方法,训练,R,个分类器,f,i,，分类器之间其他相同就是参数不同。其中,f,i,是通过从训练集合中,(N,篇文档,),随机取,(,取后放回,)N,次文档构成的训练集合训练得到的。,对于新文档,d,，用这,R,个分类器去分类，得到的最多的那个类别作为,d,的最终类别,Boosting,方法,类似,Bagging,方法，但是训练是串行进行的，第,k,个分类器训练时关注对前,k-1,分类器中错分的文档，即不是随机取，而是加大取这些文档的概率,AdaBoost,AdaBoost MH,2025/10/14 周二,36,分类方法的评估,邻接表,每个类,Precision=a/(a+b),Recall=a/(a+c),fallout=b/(b+d)=false alarm rate,accuracy=(a+d)/(a+b+c+d),error=(b+c)/(a+b+c+d)=1-accuracy,miss rate=1-recall,F=(,2,+1)p.r/(,2,p+r),Break Even Point,BEP,p=r,的点,如果多类排序输出，采用,interpolated 11 point average precision,所有类：,宏平均,:,对每个类求值，然后平均,微平均,:,将所有文档一块儿计算，求值,真正相关的,真正不相关的,系统判定相关的,a,b,系统判定不相关的,c,d,2025/10/14 周二,37,评价指标：,P,与,R,的融合,2025/10/14 周二,38,提纲,文本挖掘的背景,文本挖掘的过程,特征建立,特征集缩减,知识模式提取,文本分类,文本聚类,模型评价,国内外研究状况,