第5章 文本挖掘

第5章文本挖掘5.1文本挖掘基础11文本挖掘将数据挖掘的成果用于分析以自然语言描述将数据挖掘的成果用于分析以自然语言描述的文本，这种方法被称为文本挖掘的文本，这种方法被称为文本挖掘((TextTextMining)Mining)或文本知识发现或文本知识发现((KnowledgeKnowledgeDiscoveryinText).DiscoveryinText).利用文本切分技术，抽取文本特征，将文本数据转化为能描述文本内容的结构化数据，然后利用聚类、分类技术和关联分析等数据挖掘技术发现新的概念和获取相应的关系。22文本挖掘与数据挖掘的区别文本挖掘与数据挖掘的区别„„文本挖掘：文档本身是半结构化的或非结构化文本挖掘：文档本身是半结构化的或非结构化的，无确定形式并且缺乏机器可理解的语义。的，无确定形式并且缺乏机器可理解的语义。„„数据挖掘：其对象以数据库中的结构化数据为数据挖掘：其对象以数据库中的结构化数据为主，并利用关系表等存储结构来发现知识。数主，并利用关系表等存储结构来发现知识。数据挖掘的技术不适用于文本挖掘，或至少需要据挖掘的技术不适用于文本挖掘，或至少需要预处理。预处理。33文本挖掘的过程文本挖掘的过程„„预处理预处理„„特征抽取特征抽取„„特征选择特征选择„„文本分类文本分类„„文本聚类文本聚类„„模型评价模型评价4文本特征表示„特征表示是指以一定的特征项如词条或描述来代表文档信息。特征表示模型有多种，常用的有布尔逻辑型、向量空间型、概率型等。向量空间模型„VSM中，将每个文本文档看成是一组词条（T1，T2，T3，…，Tn）构成，对于每一词条Ti，根据其在文档中的重要程度赋予一定的权值，可以将其看成一个n维坐标系，W1，W2，…，Wn为对应的坐标值，因此每一篇文档都可以映射为由一组词条矢量张成的向量空间中的一点，对于所有待挖掘的文档都用词条特征矢量（T1，W1；T2，W2；T3，W3；…；Tn，Wn）表示。„将文档表达为一个矢量，看作向量空间中的一个点。5.2预处理„5.2.1分词„把中文的汉字序列切分成有意义的词，就是中文分词，也称为切词。„“我是一个学生”分词的结果是：我是一个学生。„和平民主和平、民主；和、平民、主„提高人民生活水平提高、高人、人民、民生、生活、活水、水平„大学生活象白纸大学、生活、象、白纸大学生、活象、白纸1分词基本方法„最大匹配法„最大概率法分词„最短路径分词方法最大匹配法„S1=计算语言学课程是三个课时设定最大词长MaxLen=5S2=（1）S2=“”；S1不为空，从S1左边取出候选子串W=计算语言学；（2）查词表，“计算语言学”在词表中，将W加入到S2中，S2=“计算语言学/”，并将W从S1中去掉，此时S1=课程是三个课时；（3）S1不为空，于是从S1左边取出候选子串W=课程是三个；（4）查词表，W不在词表中，将W最右边一个字去掉，得到W=课程是三；（5）查词表，W不在词表中，将W最右边一个字去掉，得到W=课程是；（6）查词表，W不在词表中，将W最右边一个字去掉，得到W=课程（7）查词表，W在词表中，将W加入到S2中，S2=“计算语言学/课程/”，并将W从S1中去掉，此时S1=“是三个课时”；（8）S1不为空，于是从S1左边取出候选子串W=是三个课时；（9）查词表，W不在词表中，将W最右边一个字去掉，得到W=是三个课；（10）查词表，W不在词表中，将W最右边一个字去掉，得到W=是三个；（11）查词表，W不在词表中，将W最右边一个字去掉，得到W=是三（12）查词表，W不在词表中，将W最右边一个字去掉，得到W=“是”，这时W是单字，将W加入到S2中，S2=“计算语言学/课程/是/”，并将W从S1中去掉，此时S1=三个课时；（21）S2=“计算语言学/课程/是/三/个/课时/”，此时S1=。（22）S1为空，输出S2作为分词结果，分词过程结束。其它基于匹配的分词方法最大匹配法（MaximumMatchingmethod）匹配的方向是从左向右。„逆向最大匹配法（ReverseMaximummethod）匹配方向与MM法相反，是从右向左。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。„双向匹配法(Bi-directionMatchingmethod)比较MM法与RMM法的分词结果，从而决定正确的分词。„最佳匹配法（OptimumMatchingmethod,OM法）将词典中的单词按它们在文本中的出现频度的大小排列，高频度的单词排在前，频度低的单词排在后，从而提高匹配的速度。2停用词（stopword）„指文档中出现的连词，介词，冠词等并无太大意义的词。„英文中常用的停用词有the，a,it等„中文中常见的有“是”，“的”，“地”等。„停用词消除可以减少term的个数，降低存储空间。停用词的消除方法：（1）查表法：建立一个停用词表，通过查表的方式去掉停用词。（2）基于DF的方法：统计每个词的DF，如果超过总文档数目的某个百分比(如80%)，则作为停用词去掉。5.2.2文档模型„布尔模型„向量空间模型„概率模型1布尔模型„每个词在一篇文档中是否出现，对应权值为0或1„优点：简单、易理解、简洁的形式化。„缺点：准确匹配，信息需求的能力表达不足。2向量空间模型„向量空间模型中将文档表达为一个矢量，看作向量空间中的一个点。5.2.3特征表示„特征表示是指以一定特征项(如词条)来代表文档，在文本挖掘时只需对这些特征项进行处理，从而实现对非结构化的文本处理。这是一个非结构化向结构化转换的处理步骤。1布尔模型„布尔模型是向量空间模型的一种简化，它是一种简单的严格匹配向量模型，定义了一个二值映射函数f:T→{0,1}，权值Wi={0，1}。„布尔模型实现简单，检索速度快。它只需要进行简单的0－1匹配就能判断检索条件同文档的关系，从而将检索文档分为两个集合：匹配集和非匹配集。„因为布尔模型忽略了文档项频，所以无法在匹配结果集中进行相关性大小的排序。在许多检索系统中得到应用，如Yahoo、搜狐等诸多著名网络检索站点均采用了布尔模型。2向量空间模型„用特征向量（T1，W1；T2，W2；T3，W3；…；Tn，Wn）表示文档。„Ti是词条项，Wi是Ti在文档中的重要程度，即将文档看作是由一组相互独立的词条组构成，把T1，T2…，Tn看成一个n维坐标系中的坐标轴，对于每一词条，根据其重要程度赋以一定的权值Wi，作为对应坐标轴的坐标值。„权重Wi用词频表示，词频分为绝对词频和相对词频。绝对词频，即用词在文本中出现的频率表示文本；相对词频，即为归一化的词频，目前使用最为频繁的是TF*IDF（TermFrequency*InverseDocumentFrequency）。„tf(d,t)表示词条t在文档d中的出现次数，df(t)表示词条t在文本集合中出现过的文本数目。InverseDocumentFrequencyN表示文本总数。表示文档词频的词频矩阵表示文档词频的词频矩阵dd11dd22dd33dd44dd55dd66tt113223228585353569691515320320tt223613619090767657571313370370tt332525333316016048482212212626tt443030140140707020120116163535对于词条t和某一文本d来说，词条t在该文本d的权重计算公式：如果一个词条在整个文本集合中出现的频率很高，即趋近于0，从而使得该词条在文本中的权重很小，所以词条对文本的区分度很低。„所以我们通常根据w(d,t)值的大小，选择指定数目的词条作为文本的特征项，生成文本的特征向量。这种算法一方面突出了文档中用户需要的词，另一方面，又消除了在文本中出现频率较高但与文本语义无关的词条的影响。对于单词数较多的静态文本特征选择效果较好。5.2.4文本间相似性„基于向量空间模型的常用方法欧氏距离„空间两点的欧氏距离：向量内积相似度余弦相似度效率：大量计算两两文档间相似都时，为降低计算量，先对文档进行向量进行单位化。5.2.5特征选择„特征提取算法一般是构造一个评价函数，对每个特征进行评估，然后把特征按分值高低排队，预定数目分数最高的特征被选取。„常用的评估函数有文本频数、信息增益（InformationGain）、期望交叉熵(ExpectedCrossEntropy)、互信息(MutualInformation)等。文本频数„词的DF小于某个阈值去掉(太少，没有代表性)。„词的DF大于某个阈值也去掉(太多，没有区分度)。信息增益„信息增益是一种基于熵的评估方法，定义为某特征项为整个分类系统所能提供的信息量。是不考虑任何特征的熵与考虑该特征之后熵的差值。它根据训练数据计算出各个特征项的信息增益，删除信息增益很小的特征项，其余的按照信息增益的大小进行排序，获得指定数目的特征项。)}]|(log)|(){()}|(log)|(){([)}(log)({)Entropy(Expected)(EntropyGain(t)111tcPtcPtPtcPtcPtPcPcPSSiMiiiMiiiMiit∑∑∑===−+−−−=−=期望交叉熵„期望交叉熵反映了文本类别的概率分布和在出现了某个特定词条条件下的文本类别的概率分布之间的距离。某词条的交叉熵越大，表示它对文本类别分布的影响越大。(|)()()(|)log()iiiiPctCEtptPctPc=∑互信息„体现了特征项与类别之间的关联程度，对于在某类别Ci中出现频率高，而在其它类别中出现频率低的特征项将获得较高的互信息，因此也就有可能被选取为该类别的特征。))((log)()|(log)()()(log),(BACANAtPctPcPtPctPctI++×==∧=∑==miiiAVGctIcPtI1),()()(),()(max)(1iimiMAXctIcPtI==ABCDt~tc~c5.3文本分类文本分类„„给定分类体系，将文本分到某个或者某几个类给定分类体系，将文本分到某个或者某几个类别中。别中。„„11分类算法分类算法决策树（DecisionTrees）KNN算法(K-NearestNeighbour)贝叶斯网络（BayesNetwork）神经网络（NeuralNetworks）22分类过程分类过程„训练阶段:(1)定义类别集合C={c1，c2，…，ci，，，cm}；(2)给出训练文档集合S={s1，s2…，sj，…，sn}，每个训练文档sj被标上所属的类别标识ci；(3)统计S中所有文档的特征矢量V(sj)，确定代表C中每个类别的特征矢量V(ci)。3评价指标总体评价5.4文本聚类„1步骤DocumentrepresentationDimensionalityreductionApplyingaclusteringalgorithmEvaluatingtheeffectivenessoftheprocess2评价指标总体评价3聚类方法„划分的方法„层次的方法„基于密度的方法„基于网格的方法例KNN垃圾邮件过滤算法考虑在训练文本集中与新文本距离最近的K篇文本，根据这K篇文本所属的类别判定新文本所属的类别。1）根据特征项集合描述训练文本向量。2)在新文本到达后，根据特征词分词新文本，确定新文本的向量表示。3)在训练文本集中选出与新文本最相似的K个文本，K初始值定为几百到几千之间。4)在新文本的K个邻居中，依次计算每类的权重，5)比较类的权重，将文本分到权重最大的那个类别中。例贝叶斯邮件过滤算法对于给定的向量d(w1,w2,wn），属于第Ck类的概率：