文本挖掘技术04-分类


1 文本自动分类技术 杨建武 Email:yangjw@pku.edu.cn 第四章: 北京大学计算机科学技术研究所 文本挖掘技术(2012春) 2 知识的组织  知识的结构和知识是孪生的兄弟  结构本身也是知识  分类体系  杜威十进制系统(图书分类),  国会图书馆的目录,  AMS(美国数学会)的数学知识体系,  美国专利内容的类别体系  Web catalogs  Yahoo以前的主页  Open Directory(http://www.dmoz.org/) • 志愿者共同维护与建设的最大的全球目录社区 3 Open Directory (http://www.dmoz.org/) 4 分类的概念  分类:对于给定一个对象,从一个事先定 好的分类体系中挑出一个(或者多个)最 适合该对象的类别。 对象:可以是任何东西 事先定好的分类体系:可能有结构 最适合:判断标准  便于今后查找是其最直接、最普遍的应用 5 分类体系  分类体系一般人工构造 政治、体育、军事  分类系统可以是层次结构 非学术性 学术性 人文与艺术 新闻与媒体 商业与经济 社会与文化 娱乐与休闲 政府与政治 教育 自然科学 社会科学 医疗与健康  分类模式  2类问题,属于或不属于 (binary)  多类问题,多个类别 (multi-class),可拆分成2 类问题  一个对象可以属于多类 (multi-label) 6 人工方法和自动方法  人工方法  知识工程的方法建立专家系统(80年代末期)  结果容易理解 足球 and 联赛体育类  费时费力 MEDLINE(National Library of Medicine) $2 million/year for manual indexing of journal articles  难以保证一致性和准确性(40%左右的准确率)  专家有时候凭空想象  自动的方法(学习)  快速  准确率相对高(准确率可达85%或者更高)  来源于真实文本,可信度高  结果可能不易理解 7 自动分类的优点  减小人工分类的繁杂工作  提高信息处理的效率  减小人工分类的主观性 8 文本自动分类的定义  Text Categorization (TC)  在给定的分类体系下,根据文本的内容自动地确 定文本关联的类别。  从数学角度来看,文本分类是一个映射的过程,  将未标明类别的文本映射到已有的类别中  该映射可以是一一映射或一对多的映射。  用数学公式表示如下: 合为分类体系中的类别集 为待分类的文本集合, 其中, : B ABAf  9 自动分类技术的发展 10 专家系统(late 1980s) 人工定义规则 11 专家系统  专家系统(人工定义规则) 太花时间 太难(最初看起来容易) 一致性问题 (规则集很大) 12 专家系统  美国人口调查局(1990)  十年人口统计资料的分析(2200万项资料)  232个产业类别和504个行业类别  $15 million if fully done by hand  人工定义规则  Expert System AIOCS  Development time: 192 person-months (2 people, 8 years)  Accuracy = 47%  基于机器学习的方法  最近邻分类方法 (Creecy ’92: 1-NN)  Development time: 4 person-months; Accuracy = 60% 13 统计学习取代知识工程 14 基于统计学习文本自动分类  基本步骤 定义分类体系 将预先分类过的文档作为训练集 从训练集中得出分类模型(需要测试过程,不 断细化) 用训练获得出的分类模型对其它文档加以分类  “文本分类”通常指“基于统计学习文本 自动分类” 15 文本分类基本步骤  1. 用户定义分类树  2. 用户为分类节点提供 训练文档  3. 特征选择  4. 训练  5. 自动分类 16 文本分类过程 待分类 文本 特征表示预处理 训练集 实例 训练 分类算法 校验集 校验策略 每个类的阈值 测试 结果类别表 阈值 策略 候选类列表 分类模型 训练过程 分类过程 17 自动分类技术发展 18 应用领域  门户网站(网页)  图书馆(电子资料)  情报/信息部门(情报处理)  政府、企业等(电子邮件) 文本分类实例 20 新闻自动分类  Given: Collection of example news stories already labeled with a category (topic).  Task: Predict category for news stories not yet labeled.  For our example, we’ll only get to see the headline(标题) of the news story.  We’ll represent categories using colors. (All examples with the same color belong to the same category.) 21 Amatil Proposes Two-for- Five Bonus Share Issue Jardine Matheson Said It Sets Two-for-Five Bonus Issue Replacing “B” Shares Bowater Industries Profit Exceed Expectations Citibank Norway Unit Loses Six Mln Crowns in 1986 Vieille Montagne Says 1986 Conditions Unfavourable Isuzu Plans No Interim Dividend Anheuser- Busch Joins Bid for San Miguel Italy’s La Fondiaria to Report Higher 1986 Profits Japan Ministry Says Open Farm Trade Would Hit U.S. Senator Defends U.S. Mandatory Farm Control Bill 新闻自动分类 企业个人事务 政府事务 人工标注的样例 22 能给一个新闻赋予什么颜色? ? Amatil Proposes Two-for-Five Bonus Share Issue Jardine Matheson Said It Sets Two- for-Five Bonus Issue Replacing “B” Shares Bowater Industries Profit Exceed Expectations Citibank Norway Unit Loses Six Mln Crowns in 1986 Vieille Montagne Says 1986 Conditions Unfavourable Isuzu Plans No Interim Dividend Anheuser-Busch Joins Bid for San Miguel Italy’s La Fondiaria to Report Higher 1986 Profits Japan Ministry Says Open Farm Trade Would Hit U.S. Senator Defends U.S. Mandatory Farm Control Bill 什么没看到之前, 分类预测:取多数? 新闻自动分类 23 Senate Panel Studies Loan Rate, Set Aside Plans Amatil Proposes Two-for-Five Bonus Share Issue Jardine Matheson Said It Sets Two- for-Five Bonus Issue Replacing “B” Shares Bowater Industries Profit Exceed Expectations Citibank Norway Unit Loses Six Mln Crowns in 1986 Vieille Montagne Says 1986 Conditions Unfavourable Isuzu Plans No Interim Dividend Anheuser-Busch Joins Bid for San Miguel Italy’s La Fondiaria to Report Higher 1986 Profits Japan Ministry Says Open Farm Trade Would Hit U.S. Senator Defends U.S. Mandatory Farm Control Bill 新闻自动分类 看见标题之后, 分类预测:? 24 Senate Panel Studies Loan Rate, Set Aside Plans Amatil Proposes Two-for-Five Bonus Share Issue Jardine Matheson Said It Sets Two- for-Five Bonus Issue Replacing “B” Shares Bowater Industries Profit Exceed Expectations Citibank Norway Unit Loses Six Mln Crowns in 1986 Vieille Montagne Says 1986 Conditions Unfavourable Isuzu Plans No Interim Dividend Anheuser-Busch Joins Bid for San Miguel Italy’s La Fondiaria to Report Higher 1986 Profits Japan Ministry Says Open Farm Trade Would Hit U.S. Senator Defends U.S. Mandatory Farm Control Bill 得到分类:政府事务 25 评价指标 26 评价指标  「准确率」(P, precision)  「召回率」(R, recall)  F-Measure   RP F 111 1    RP PRF  2 1 1 4 2 5 27 评价指标  每个类 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 fallout=b/(b+d)=false alarm rate, F=(β2+1)p·r/(β2p+r) Break Even Point, BEP, p=r的点 interpolated 11 point average precision (p-r曲线) 28 评价指标 所有类的总体评价 ii ii i RP RPF  2 1  宏平均 Macro  微平均 Micro       m i i m i ii n Fn FMicro 1 1 )(    m i iFmFMacro 1 1   ii i RP F 111 1    29 特征抽取 30 文档模型  布尔模型  向量空间模型  概率模型 31 特征抽取(feature extraction)  预处理  去掉html一些tag标记  停用词(stop words)去除、词根还原(stemming)  (中文)分词、词性标注、短语识别、…  词频统计 (TF, DF)  数据清洗:去掉噪声文档或文档内垃圾数据  文本表示  向量空间模型  降维技术  特征选择(Feature Selection)  特征重构(Re-parameterisation,如LSA) 32 向量空间模型  向量空间模型(Vector Space Model) M个无序标引项ti (特征),词根/词/短语/其他 每个文档dj可以用标引项向量来表示 •(a1j,a2j,…,aMj) 权重计算,N个训练文档 •AM*N= (aij) 相似度比较 • Cosine计算 • 内积计算 T3 T1 T2 D1 = 2T1+ 3T2 + 5T3 D2 = 3T1 + 7T2 + T3 Q = 0T1 + 0T2 + 2T3 7 3 2 5 33 Term的粒度  Character,字:中  Word,词:中国  Phrase,短语:中国人民银行  Concept,概念  同义词:开心 高兴 兴奋  相关词cluster,word cluster:葛非/顾俊  N-gram,N元组:中国 国人 人民 民银 银行  某种规律性模式:比如某个window中出现的固 定模式  David Lewis等认为:(英文分类中)使用优化合 并后的Words比较合适 34 权重计算方法  布尔权重(boolean weighting) aij=1(TFij>0) or 0 (TFij=0)  TFIDF型权重 TF: aij=TFij TF*IDF: aij=TFij*log(N/DFi) TFC: 对上面进行归一化 LTC: 降低TF的作用  k kkj iij ij DFNTF DFNTFa 2)]/log(*[ )/log(*    k kkj iij ij DFNTF DFNTFa 2)]/log(*)0.1[log( )/log(*)0.1log( 35 特征选择 36 特征选择  目的  避免过拟合(over fitting),提高分类准确度 • 如果经过某种学习之后的分类模型,使得训练文档适应得 很好(导致很高的自动分类精度),但对训练集之外的文 档显得差许多,则称此时的学习模型有 Over-fitting problem • 希望模型的表现对训练集和未知文档基本一致。  通过降维,大大节省计算时间和空间 • 样例空间涉及的总词项数很大(N在10万量级),但每篇文 档只涉及其中的一小部分(例如一篇网页通常只有几百个词)  基本信念:除那些stop words外,还有许多词 实际上对分类没什么贡献  但如何确定这些词? 37 特征选取的方法  文档频率法(DF, document frequency)  信息增益法(information gain)  互信息法(mutual information)  The test(chi-square,卡方拟合检验) 2 38 特征选择--DF  基于DF的启发式要点 太频繁的词项没有区分度 • Term的DF大于某个阈值去掉 太稀有的词项独立表达的类别信息不强 • 稀有词项的全局影响力不大 • 在训练集中,某些文档如果有某个稀有词项,它 们通常也会有一些常见词项(对那一类) • 和通常信息获取观念有些抵触:稀有的更有代表 性(这是一种ad hoc方法,不依据什么理论)  最容易实现,可扩展性好 39 相关表 Contingency table (matrix) 40 特征选择--熵  假设信息出现的概率空间 p = {p1, p2, …, pm} “硬币出现某一面”,“一篇文档属于某一类”  在引入某个词项t之前,系统的熵(即一 个随机文档落入某个类的概率空间的熵)  i ii PPtEntropy log)( ccP ii / nBAPi /)(  DCBAn  41 特征选择--熵  在观察到t以后,文档落入某个类ci的概率 就应该是条件概率P(ci|t) 对应于相关表中的A/(A+C) 注意,对不同的ci,每个分量不一定相同  term类别分布的熵: 该值越大,说明分布越均匀,越有可能出现 在较多的类别中; 该值越小,说明分布越倾斜,词可能出现在 较少的类别中  i ii tcPtcPtEntropy )|(log)|()( 42 特征选择--信息增益IG  信息增益(Information Gain, IG): 该term为整个分类所能提供的信息量 t出现与否导致的熵的变化 不考虑任何特征的熵和考虑该特征后的熵的 差值 )}]|(log)|(){( )}|(log)|(){([ )}(log)({ 1 1 1 tcPtcPtP tcPtcPtP cPcP i M i i i M i i i M i i          )Entropy( Expected)(EntropyGain(t) tSS  43 特征选择--互信息MI  互信息MI是评估两个随机变量X、Y相关 程度的一种度量  x y yPxP yxPyxPYXMI )()( ),(log),(),( 其中P (x,y)是变量取值(x,y)的概率 44 特征选择--互信息MI  X, Y分别对应词项t的出现情况和类别的出 现情况 看成随机事件,t可能出现0,1,2,…次(取决于要 用的文档模型); 类别有m种可能c={c1,c2,…,cm} 不混淆情况下,用t, c表示这两个随机变量  关心的P(t), P(c), P(t,c)都可以通过统计训练 集中的数据情况得到 如果用二元模型,即前面的“相关表”就足够, 如果是多元模型,也容易推广 45 特征选择--互信息MI  互信息(Mutual Information):MI越大 t和c共现程度越大  (N=A+B+C+D) ))((log)/)((*)/)(( /log )()( )(log),( CABA NA NCANBA NA cPtP ctPctI       m i iiAVG ctIcPtI 1 ),()()( ),()(max)( 1 ii m iMAX ctIcPtI  A B C D t ~t c ~c 46 特征选择--互信息MI  特点 MI(t,C)的值越大,t对于C的区分能力 越强 对同一个类,不同的词项,在同样 P(t|c)情况下,相对稀有的 t 会得到较 大的值 MI还可以解释为给定一个随机变量后 另外一个随机变量上的减少 47 特征选择 -- (卡方)  源于统计学的卡方分布(chi-square)  从(类,词项)相关表出发 考虑每一个类和每一个词项的相关情况, chi-square(t,c) 2 48 特征选择 -- (卡方)  χ2 统计量: 度量两者(term和类别)独立性的缺乏程度 χ2 越大,独立性越小,相关性越大 若AD40 no no yes yes yes 30..40 决策树方法 58 决策树方法  构造决策树 CART C4.5 (由ID3发展而来) CHAID  决策树的剪枝(pruning) 59 Attribute Selection Measure: Information Gain(ID3/C4.5)  选择信息增益最大的属性  S contains si tuples of class Ci for i = {1, …, m}  information measures info required to classify any arbitrary tuple s s s s,...,s,ss im i i m21 2 1 log)I(    60 Attribute Selection Measure: Information Gain(ID3/C4.5)  entropy of attribute A with values {a1,a2,…,av}  information gained by branching on attribute A )s,...,s(Is s...sE(A) mjj v j mjj 1 1 1   E(A))s,...,s,I(sGain(A) m  21 选择信息增益最大的属性作为判定的分支节点 61 Rocchio方法  Rocchio公式  分类  可以认为类中心向量法是它的特例 C Ci ij C Ci ij jcjc nn x n xww    ' 类C中心向量的权重 训练样本中正例个数 文档向量的权重    22c xw)( ijcj ijcj iic xw xwdCSV 62 K-NN分类方法 63 1-Nearest Neighbor (graphically) 64 kNN方法  一种Lazy Learning, Example-based Learning 新文本 k=1, A类 k=5,B类 k=10,B类 65 kNN方法的发展  Instance-Based Learning, Lazy Learning  Well-known approach to pattern recognition  Initially by Fix and Hodges (1951)  Theoretical error bound analysis by Duda & Hart (1957)  Applied to text categorization in early 90’s(YYM)  Among top-performing methods in TC evaluations  Scalable to large TC applications 66 kNN for Text Categorization (Yang YM, SIGIR-1994)  Represent documents as points (vectors).  Define a similarity measure for pair wise documents.  Tune parameter k for optimizing classification effectiveness.  Choose a voting scheme (e.g., weighted sum) for scoring categories  Threshold on the scores for classification decisions (不是简单排序取最高的,需要有个门槛). 67 Nearest Neighbor方法的要点  “Similar” item: We need a functional(可 操作的)definition of “similarity” if we want to apply this automatically.  要考虑多少邻居?  近邻的所有类别都算?还是只取那些出 现次数多的?如何作出最后的决定?  Does each neighbor get the same weight? 68 k的作用 69 K-NN using a weighted-sum voting Scheme 70 Category Scoring for Weighted-Sum  The score for a category is the sum of the similarity scores between the point to be classified and all of its k-neighbors that belong to the given category. where  x is the new point; c is a class  d is a classified point among the k-nearest neighbors of x;  sim(x,d) is the similarity between x and d;  I(d,c) = 1 iff point d belongs to class c; I(d,c) = 0 otherwise.    xofkNNd c cdIdxsimbxcscore ),(),()|( 71 kNN算法中k的取值 72 kNN算法中k的取值 73  优点  简单、有效 (among top-5 in benchmark evaluations)  重新训练的代价较低(类别体系的变化和训练集的变 化,在Web环境和电子商务应用中是很常见的)  计算时间和空间线性于训练集的规模(在一些场合不 算太大)  缺点  kNN是懒散学习方法(lazy learning, 基本上不学习), 一些积极学习的算法要快很多  类别评分不是规格化的(不像概率评分)  输出的可解释性不强,例如决策树的可解释性较强 kNN的优缺点 74  The n-dimensional input vector x is mapped into variable y by means of the scalar product and a nonlinear function mapping mk - f weighted sum Input vector x output y Activation function weight vector w  w0 w1 wn x0 x1 xn 神经网络分类 75 贝叶斯分类法 )()|()( )()|()|( jji i jji ij cPcdPdP cPcdPdcP  ,独立性假设   r k jikji cwPcdP 1 )|()|( 参数计算 Bayesian公式     1 )(|| )(1 )( )()( k k j k k jj j cNc cN cN cNccP 总文档个数 的文档个数   k kj ij j ji ji N N c cwcwP 不同词个数的次数类所有文档中出现的词在 类别文档中出现的次数在 1)|( 76 基于投票的方法  Bagging方法 将一个学习算法使用多次。 训练R个分类器fi, • 分类器之间其他相同只是参数不同; • 其中fi是通过从训练集合中随机取(取后放回)N篇 文档构成的训练集合训练得到的。 对于新文档d,用这R个分类器去分类,得到 的最多的那个类别作为d的最终类别。 77 基于投票的方法  Boosting方法 类似Bagging方法,但是训练是串行进行的, 第k个分类器训练时关注对前k-1分类器中错分 的文档,即不是随机取,而是加大取这些文档 的概率。 AdaBoost • 使用加权后选取的训练数据代替随机选取的训练样 本,将训练的焦点集中在比较难分的训练样本上; • 将弱分类器联合起来,使用加权的投票机制代替平 均投票机制,让分类效果好的弱分类器具有较大的 权重,而分类效果差的分类器具有较小的权重。 78 基于SVM的文本分类 79 SVM 基本原理 对于一组训练样本 ,),),...(,( 11 ll yxyx ,nRx }1,1{ y 在线性可分的情况下会有一个超平面 0)(  bxw 将这两类样本完 全分开;并且离 超平面最近的向 量与超平面之间 的距离最大。 最优分类超 平面 间隔 80 How SVMs work 81 How SVMs work 82 How SVMs work 83 How SVMs work 84 How SVMs work 85 How SVMs work 86 margin Support vectors How SVMs work 87 margin Support vectors How SVMs work 88 margin Support vectors How SVMs work 89 最优分类超平面 ,1])[(  bxwy ii li ,...,1 类别之间的分类间隔是: ||||/2 w 为描述分类超平面,可采用下面的形式:      1:,1)( 1:,1)( ii ii ywhenbxw ywhenbxw 即: 为求解最优超平面,可以看成解二次型规划问题: )2 1)( www  ( libwxy ii ,...,2,1,1])[(  最小化: 约束条件: (1) (2) 90 最优分类超平面 91 鞍点理论 )2 1)( www  ( libwxy ii ,...,2,1,1])[(  最小化: 约束条件:    l i iii bwxywwbwL 1 }1])[({)2 1),,(  ((3) 转化为如下的拉格朗日的极值问题(鞍点理论): 根据鞍点理论(导数求极值):               l i iii l i ii lixyww bwL liyb bwL 1 1 ,,1,0),,( ,,1,00),,(            (4) (5) 92 根据对偶理论与K-T条件,(参见非线性规划理论) 原问题转化为其对偶问题,求解如下泛函的最大 化 (即:将式(4)(5)代入式(3))           l i l i jijiji l i i l i i l i ii l i iii l i iii xxyy ybwxyww bwxywwL 1 11 111 1 )(2 1 )()()2 1 }1])[({)2 1)(    ( ( 满足约束: ,0 1    l i iiy ,0i li ,...,1 (6) (7) 对偶理论 (8) 公式(4) 公式(5) 93 分类函数 通过以上变换,将不等式约束转化为等式约束。并且可证 明:该二次规划问题存在唯一解,且解中只有一部分 0i 的样本对分类不起什么作用,有用的是 0i 样本, 这些样本称为支持向量。 最后的获得的分类函数为:         支持向量 **)(sgn)( bxxyxf iii (9)      l i l i jijiji l i i xxyyL 1 11 )(2 1)(  满足约束: ;0 1    l i iiy  ,0i li ,...,1 即:最大化: 0}1)({  bxwy iii 94 而对于线性不可分的情况,通过引入松弛变量 0i 相应的目标函数变为: 满足约束 ,iii bxwy  1])[( 最小化泛函:        l i iCwww 1 )(2 1),(  li ,...,1 优化过程与线性可分情况基本一致,(6)(7)不变,约束条件 (8)变为: Ci 0 其中,C为预定义的常数(惩罚因子) (10) (11) (12) 松弛因子 95 非线性SVM 0 ?  bwxi Classification using SVM (w,b) 0),( ? bwxK i In non linear case we can see this as 内积回旋: ),()( ii xxKZZ      l i l i jijiji l i i xxKyyW 1 11 ),(2 1)(  (核函数) Φ 96 特征空间与核函数  核函数的定义 核是一个函数k,对所有 , 成立。其中 是从输入空间X到特征空间F(Hilbert空间)的映射。 Xyx ,      yxyxk  , nRX : 97 特征空间与核函数  多项式核  高斯径向基函数核  Sigmoid核 (要满足Mercer’s条件) 98 训练算法  由于支持向量机在训练时需要进行样本 数L*L的二次方的矩阵的求解,因此,训 练速度慢,内存占用大。为此,需用一 些改进的算法来加快训练的进程,常用 的主要有: 块算法: 删除算法矩阵中对应Lagrange乘数 为零的行和列将不会影响最终的结果,逐步 排除非支持向量; 分解法:将大的矩阵计算分解成小的; SMO方法:每次只进行两个样本的优化,直 接代数解。 99 SVM 优缺点  现有样本有限信息情况下寻最优  转化为二次型寻优问题,全局最优(避 免局部极值)  在高维空间构造线性判别函数,实现原 空间的非线性判别函数  结构风险最小原理并不能严格证明好的 推广能力  学习机的VC维的分析尚没有通用方法 100 回归支持向量机(SVR) 101 排序支持向量机(Ranking SVM) x11 x12 x13 x21 x22 x23 w 102 其他分类方法  Regression based on Least Squares Fit (1991)  Nearest Neighbor Classification (1992) *  Bayesian Probabilistic Models (1992) *  Symbolic Rule Induction (1994)  Decision Tree (1994) *  Neural Networks (1995)  Rocchio approach (traditional IR, 1996) *  Support Vector Machines (1997) *  Boosting or Bagging (1997)*  Hierarchical Language Modeling (1998)  First-Order-Logic Rule Induction (1999)  Maximum Entropy (1999)  Hidden Markov Models (1999)  Error-Correcting Output Coding (1999)  ... 103 小结  自动分类的概念  分类效果的评价  特征选择 文档频率法(DF, document frequency) 信息增益法(information gain) 互信息法(mutual information) The χ2 test(chi-square)  分类算法 KNN SVM 104
还剩103页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

daisylam

贡献于2015-11-20

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf