Web 文本挖掘（TextMining）技术

[日期：2007-01-04]

来源：  作者：

[字体：大 中 小]

文本挖掘的起源

　　文本数据库（web文档数据）

　　半结构化数据（semistructure data）

　　信息检索技术（information retrieval）

　　Web文本挖掘的过程

　　Web文本挖掘的一般处理过程
　　
　　特征的建立

　　特征集的缩减

　　学习与知识模式的提取

　　知识模式

　　模式质量的评价

　　文档集

　　文本特征的建立

　　定义：文本特征指的是关于文本的元数据。

　　分类：

　　　　描述性特征：文本的名称、日期、大小、类型等。

　　　　语义性特征：文本的作者、标题、机构、内容等。

　　表示（文档建模）：

　　采用向量空间模型（VSM）（矩阵）

　　特征向量

　　（其中ti为词条项，wi(d)为ti在d中的权值）

　　文本特征评价函数的数学表示

　　信息增益（information gain）

　　期望交叉熵（expected cross entropy）
　　
　　互信息（mutual information）

　　F是对应于单词W的特征；

　　P(W)为单词W出现的概率；

　　P(Ci)为第i类值的出现概率；

　　p(Ci|W)为单词W出现时属于第i类的条件概率。
　　
　　文本特征评价函数的数学表示(续)

　　文本证据权（the weight of evidence for text）

　　词频（word frequency）

　　P(W)为单词W出现的概率；

　　P(Ci)为第i类值的出现概率；

　　p(Ci|W)为单词W出现时属于第i类的条件概率；

　　TF(W)为单词在文档集中出现的次数。

　　文档建模

　　词频矩阵

　　行对应关键词t，列对应文档d向量将每一个文档视为空间向量v向量值反映单词t与文档d的关联度 表示文档词频的词频矩阵


　　文档相似度计算


余弦计算法（cosine measure）

余弦相似度定义： "略"
缺点：文档“无限”，导致矩阵增大，计算量增加


特征集的缩减


潜在语义标引（latent semantic indexing）方法利用矩阵理论中的“奇异值分解（singular value decomposition,SVD）”技术，将词频矩阵转化为奇异矩阵（K×K）

潜在语义标引方法基本步骤：

1.建立词频矩阵，frequency matrix

2.计算frequency matrix的奇异值分解

分解frequency matrix成3个矩阵U，S，V。U和V是正交矩阵（UTU=I），S是奇异值的对角矩阵（K×K）

3.对于每一个文档 d，用排除了SVD中消除后的词的新的向量替换原有的向量

4.保存所有向量集合，用高级多维索引技术为其创建索引

5.用转换后的文档向量进行相似度计算


其他文本检索标引技术

倒排索引（inverted index）

一种索引结构，包含两个哈希表索引表或两个B+树索引表

找出与给定词集相关的所有文档

找出与指定文档相关的所有词

易实现，但不能处理同义词和多义词问题，posting_list非常长，存储开销大

签名文件（signature file）

doc_1, ... , doc_n

Term_n

tn_1, ... ,tn_n

Doc_n


┇


┇


┇


┇


doc_1, ... , doc_ j


Term_2


t2_1, ... ,t2_n


Doc_2


doc_1, ... , doc_i


Term_1


t1_1, ... ,t1_n


Doc_1


posting_list

term_ID

posting_list

doc_ID

词表(term_table)

文档表（document_table）

词性标注

定义：将句子中兼类词的词性根据上下文唯一地确定下来。

兼类词分类：

同型异性异义兼类词：例如：领导（动词/名词）

同型异性同义兼类词：例如：小时（量词/名词）

异型同性同义兼类词：例如：电脑，计算机

自动词性标注就是用计算机来自动地给文本中的词标注词类。

在英语、汉语等自然语言中，都存在着大量的词的兼类现象，这给文本的自动词性标注带来了很大的困难。因此，如何排除词类歧义，是文本自动词性标注研究的关键问题。

标注技术路线：基于概率统计和基于规则

自动词类标注

早在60年代，国外学者就开始研究英语文本的自动词类标注问题，提出了一些消除兼类词歧义的方法，建立了一些自动词性标注系统。

1971年，美国布朗大学的格林（Greene）和鲁宾（Rubin）建立了TAGGIT系统，采用了86个词类标记，利用了3300条上下文框架规则（context frame rules）来排除兼类词歧义，自动标注正确率达到77%.

1983年，里奇（G. Leech）和加塞德（R. Garside）等人建立了CLAWS系统，用概率统计的方法来进行自动词性标注，他们使用了133×133的词类共现概率矩阵，通过统计模型来消除兼类词歧义，自动标注的正确率达到了96%.

1988年，德洛斯（S. J. DeRose）对CLAWS系统作了一些改进，利用线性规划的方法来降低系统的复杂性，提出了VOLSUNGA算法，大大地提高了处理效率，使自动词性标注的正确率达到了实用的水平。

　　基于概率统计的CLAWS算法


　　CLAWS是英语Constituent-Likelihood Automatic Word-tagging System（成分似然性自动词性自动标注系统）的简称，它是1983年玛沙尔(Mashall)在给LOB语料库（拥有各类文体的英国英语语料库，库容量为100万词）作自动词性标注时提出的一种算法。具体做法是：

　　先从待标注的LOB语料库中选出来部分语料，叫做“训练集”（Training Set）, 对训练集中的语料逐词进行词性的人工标注, 然后利用计算机对训练集中的任意两个相邻标记的同现概率进行统计，形成一个相邻标记的同现概率矩阵。

　　进行自动标注时，系统从输入文本中顺序地截取一个有限长度的词串，这个词串的首词和尾词的词性应该是唯一的，这样的词串叫做跨段(span)，记为W0,W1,W2,…,Wn,Wn+1。其中， W0和Wn+1 都是非兼类词， W1,W2,…,Wn 是n个兼类词。

　　利用同现概率矩阵提供的数据来计算这个跨段中由各个单词产生的每个可能标记的概率积，并选择概率积最大的标记串作为选择路径(path),以这个路径作为最佳结果输出。

　　VOLSUNGA算法

　　VOLSUNGA算法对CLAWS算法的改进主要有两个方面。在最佳路径的选择方面，不是最后才来计算概率积最大的标记串，而是沿着从左至右的方向，采用“步步为营”的策略，对于当前考虑的词，只保留通往该词的最佳路径，舍弃其他路径，然后再从这个词出发，将这个路径同下一个词的所有标记进行匹配，继续找出最佳的路径，舍弃其他路径，这样一步一步地前进，直到整个跨段走完，得出整个跨段的最佳路径作为结果输出。

　　根据语料库统计出每个词的相对标注概率(Relative Tag Probability)，并用这种相对标注概率来辅助最佳路径的选择。

　　VOLSUNGA算法大大地降低了CLAWS算法的时间复杂度和空间复杂度，提高了自动词性标注的准确率。

　　统计方法的缺陷

　　CLAWS算法和VOLSUNGA算法都是基于统计的自动标注方法，仅仅根据同现概率来标注词性。但是，同现概率仅只是最大的可能而不是唯一的可能，以同现概率来判定兼类词，是以舍弃同现概率低的可能性前提的。

　　为了提高自动词性标注的正确率，还必须辅之以基于规则的方法，根据语言规则来判定兼类词。

　　基于规则的标注

　　基于规则的方法通过考虑上下文中的词及标记对兼类词的影响决定兼类词的词性，常常作为基于概率统计方法的补充。将统计方法和规则方法结合被认为是解决词性标注问题的最佳手段。

　　在统计语料规模较大的情况下，结合给定最小支持度及最小可信度，首先发现大于最小支持度常用模式集，然后生成关联规则。若此规则的可信度大于给定的最小可信度，则得到词性规则。只要最小可信度定义得足够高，获得的规则就可以用于处理兼类词的情况。（规则依赖于词与词性的各种组合，挖掘过程较为复杂）


基于规则的词性标注（续）

　　主要依靠上下文来判定兼类词。
　　这是一张白纸（“白”出现在名词”纸”之前，判定为形容词）

　　他白跑了一趟（“白”出现在动词“跑”之前，判定为副词）

　　词性连坐：在并列的联合结构中，联合的两个成分的词类应该相同，如果其中一个为非兼类词，另一个为兼类词，则可把兼类词的词性判定为非兼类词的词性。

　　我读了几篇文章和报告

　　“文章”为名词，是非兼类词，“报告”为动-名兼类词，由于处于联合结构中，故可判定“报告”为名词。

　　清华大学计算机系黄昌宁等采用统计方法建立了一个自动词性标注系统，标注正确率达96.8%，自动标注的速度为每秒175个汉字。

　　自动语义标注

　　一词多义，形成了词的多义现象，自动语义标注主要是解决词的多义问题。

　　一词多义也是自然语言中的普遍现象，但是，在一定的上下文中，一个词一般只能解释为一种语义。

　　所谓自动语义标注，就是计算机对出现在一定上下文中的词语的语义进行判定，确定其正确的语义并加以标注。

　　语义自动标注的方法


　　以字义定词义

　　词=字+…+字

　　利用检索上下文中出现的相关词的方法来确定多义词的义项

　　词之间的亲和程度（pen）

　　利用上下文搭配关系来确定多义词的词义

　　词性搭配（plan）

　　用最大可能义项来消解多义

　　选择多义词各个义项中使用频度最高的义项为它在文本中的当前义项。这显然不是一种科学的办法，但仍然有一定的正确率。

　　据统计，用最大可能义项来消解多义，对于封闭文本，正确率仅为67.5%，对于开放文本，正确率更低，仅为64.8%。

　　目前不少机器翻译系统，都采用这种最大可能义项来确定多义词的词义，，这是这些机器翻译系统译文质量低劣的主要原因之一。

　　其他文本检索标引技术（续）


　　签名文件（signature file）

　　定义：是一个存储数据库中每一个文档的特征记录的文件

　　方法：每一个特征对应一个固定长度的位串，一个比特位对应一个词汇，若某一位对应的词出现在文档中则，则该位置1，否则置0。

S1

S2

　　按位操作进行匹配，确定文档的相似形

　　可以多词对应一个比特位，来减少位串的长度，但增加搜素开销，存在多对一映射的缺点。
略...


学习与知识模式的提取

文本源

文本结构分析器

文本分类器

中文文本挖掘模型结构示意图

分词及非用词处理

特征提取

名字识别

日期处理

数字处理

文本摘要生成器

用户界面

用户浏览

检索结果

学习与知识模式的提取（续）

　　分词

定义：在中文文本的词与词之间加上空格。

非用词（停用词）

定义：在文本中起辅助作用的词。

分类：

虚词：英文中的“a,the,of,for,with,in,at, …”

中文中的“的，地，得，…”

实词：数据库会议上的论文中的“数据库”一词，视为非用词

词根问题

compute , computes , computed 视为同一个词（变形而已）


　　自动分词


　　自动分词的用处：

　　中文文本的自动检索、过滤、分类及摘要

　　中文文本的自动校对

　　汉外机器翻译

　　汉字识别与汉语语音识别的后处理

　　汉语语音合成

　　以句子为单位的汉字键盘输入

　　汉字简繁体转换


　　主要的分词方法


　　最大匹配法（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法）：采用联想和回溯的机制来进行匹配。

　　模型质量的评价

　　文本检索的基本度量

　　{relevant}：与某查询相关的文档的集合。

　　{retrieved}：系统检索到的文档的集合。

　　{relevant} ∩ {retrieved}：既相关又被检索到的实际文档的集合。

　　查准率(precision)：既相关又被检索到的实际文档与检索到的文档的百分比。

　　查全率(recall)：既相关又被检索到的实际文档与查询相关的文档的百分比。


　　模型质量的评价实例

　　{relevant} ={A,B,C,D,E,F,G,H,I,J} = 10

　　{retrieved} = {B, D, F,W,Y} = 5

　　{relevant} ∩ {retrieved} ={B,D,F} = 3

　　查准率：precision = 3/5 = 60%

　　查全率：recall = 3/10 = 30%
　　B,D,F 相关并被检索到的文档
　　所有文档 A,C,E,G,H, I, J相关的文档 W,Y检索到的文档


　　文本分类
　　一般方法

　　将预先分类过的文档作为训练集从训练集中得出分类模式（需要测试过程，不断细化）用导出的分类模式对其它文档加以分类

　　基于关联的分类方法

　　通过信息检索技术和关联分析技术提出关键字和词汇利用已有的词类生成关键字和词的概念层次(文档类别)，利用关联挖掘方法去发现关联词， 进而区分各类文档（每一类文档对应一组关联规则）用关联规则去对新的文档分类。

　　Web文档的自动分类

　　利用超链接中的信息进行分类统计方法

　　马尔可夫随机场（Markov Random Field,MRF）结合宽松标识（Relaxation Labeling ,RL) 由Weblog数据进行文档分类。


　　文本聚类

　　层次聚类法

　　平面划分法（k-means算法）

　　简单贝叶斯聚类法

　　K-最近邻参照聚类法

　　分级聚类法

　　基于概念的文本聚类

　 层次聚类法

　　具体过程

将文档集D={d1, … ,di , … ,dn} 中的每一个文档di看作是一个具有单个成员的类Ci={di}，这些类构成了D的一个聚类C={c1, … ,ci , … ,cn}；

计算C中每对类（ ci , cj ）之间的相似度sim(ci , cj )；

选取具有最大相似度的类对arg max sim(ci , cj ),并将ci 和cj合并为一个新的类ck=ci∪cj ，从而构成D的一个新的类C={c1, … ,cn-1}；

重复上述步骤，直到C中只剩下一个类为止。


…


…


　　平面划分法


　　将文档集D={d1, … ,di , … ,dn}水平地分割为的若干类，具体过程：

　　1. 确定要生成的类的数目 k；

　　2. 按照某种原则生成k个聚类中心作为聚类的种子 S={s1, … ,sj , … ,sk}；

　　3. 对D中的每一个文档di ，依次计算它与各个种子sj的相似度sim(di , sj )；

　　4. 选取具有最大的相似度的种子arg max sim(di , sj ), 将di归入以sj 为聚类中心的类Cj ，从而得到D的一个聚类C={c1, … ,ck}；

　　5. 重复步骤2~4若干次，以得到较为稳定的聚类结果。

　　该方法速度快，但k要预先确定，种子选取难

　　自动文摘、自动摘要

　　定义：

　　就是利用计算机自动地从原始文档中提取全面准确地反映该文档中心内容的简单连贯的短文。

　　自动文摘系统

　　自动文摘系统应能将原文的主题思想或中心内容自动提取出来。

　　文摘应具有概况性、客观性、可理解性和可读性。

　　系统适用于任意领域。

　　1995年自动文摘系统评测

　　⑴ 3个系统都可以按指定的比率从原文中摘取一部分语句。

　　⑵ 抽取的文摘都是原文中的语句，只有单位2的文摘中剔除了一些中文数字。

　　⑶ 三个系统的文摘几乎完全不相重合。

　　与专家的文摘完全不同

　　相关内容

　　汉字输入与汉语语料库

　　语料库中汉语书面文本的自动短语定界与句法标注

　　机器词典的建造

　　术语数据库

　　机器翻译

　　计算机辅助文本校对

　　情报自动检索系统

　　汉语语音识别系统

　　汉语语音合成系统

　　汉字识别系统

　　国内研究情况

　　《计算机学报》99（1）

　　《软件学报》98-99（4）

　　《清华大学学报》（4）

　　汉语基本名词短语分析模型、识别模型、文本词义标注、语言建模、分词歧义算法、上下文无关分析、语素和构词研究

黄昌宁


清华大学计算机科学与技术系

手写汉字识别（动态匹配）、 汉字识别 多分类器集成（综合识别法）、《名片自动录入系统的实现》
丁晓青
吴佑寿

清华大学电子工程系
《计算机研究与发展》98（4）
《软件学报》97（1）
其它
翻译、汉语分词、自然语言接口、句法分析、语义分析、音字转换、自动分词

陈肇雄
中科院计算机语言信息工程研究中心
主要期刊及发表数量


《北京邮电大学学报》

《情报学报》


自动标注汉语词类（神经网络模型）、自动文摘（文摘语文本结构关系）、提出了基于言语行为理论的话语分析方法


钟义信


北京邮电大学信息工程系
《中文自动摘要系统》、基于神经网络的自动分类优化算法

王永成

上海交通大学电脑应用研究所

《计算机研究与发展》97-99（5）

《软件学报》98（1）

音字转换、自动文摘、手写汉字识别、自动分词、《中文词句快速查找系统》


王开铸

王小龙


哈尔滨工业大学计算机科学与工程系

《软件学报》97-00（7）

《上海交通大学学报》（3）


　　语句语义、自然语言模型、构造语义解释模型（增量式）、树形分层数据库方法（非结构化数据知识方法）、范例推理


陆汝占

海交通大学计算机科学与工程系

主要期刊及发表数量


《计算机研究与发展》97-99（5）

《软件学报》97-99（3）

《小型微型计算机系统》97-99（4）

《东北大学学报》97-99（10）


　　词性标注、继承理论（将无限的自然语言处理转换成有限的类别处理）、中文信息自动抽取、词类搭配规则、语音识别模型、文本的时间信息分析（时态逻辑）、短语结构规则自动获取方法、模糊聚类分析用于语音识别领域、语言异化、基于神经网络的模糊知识自动获取方法、英文中动词的远程搭配、中文姓名识别、汉语文本自动分类模型设计与实现、词汇消歧


姚天顺

朱靖波


东北大学 9

《计算机研究与发展》97（1）

部分汉语语法分析器

吴立德

复旦大学

主要期刊及发表数量



《电路与系统学报》（1）

《华南理工大学学报》（1）


手写汉字识别（弹性网格方向分解特征、动态衰减调节径向函数（RBF DDA））


徐秉铮


华南理工大学电子与通信工程系


11


《北京大学学报》（1）

《中文信息学报》（1）


汉语单句谓语中心词识别


俞志汶

魏志方


北京大学计算语言研究所


10


主要期刊及发表数量


内容


带头人


校、院、所


序号


国内研究情况（续）




上海交通大学电脑应用研究所


自动分词（60年代）

自动标引（70年代）


东北大学


清华大学计算机科学与技术系


北京邮电大学信息工程系


中科院计算机语言信息工程研究中心


哈尔滨工业大学计算机科学与工程系


上海交通大学


东北大学


英文中动词的远程搭配


北京邮电大学信息工程系


哈尔滨工业大学


北京邮电大学信息工程系


自动文摘


校、院、所


内容




哈尔滨工业大学计算机科学与工程系


东北大学


上海交通大学计算机科学与工程系


中科院计算机语言信息工程研究中心


音字转换


清华大学电子工程系


哈尔滨工业大学


北京大学计算语言研究所


东北大学


华南理工大学电子与通信工程系


汉字识别


清华大学计算机科学与技术系


复旦大学计算机科学系


中科院计算机语言信息工程研究中心


语义分析 语法分析 句法分析


校、院、所


内容


中文分词系统Cseg&Tag


《名片自动录入系统的实现》


《中文词句快速查找系统》


《中文自动摘要系统》


上海交通大学计算机科学与工程系


TH-OCR汉字识别系统（optical character recognition）


清华大学


哈尔滨工业大学计算机科学与工程系


上海交通大学电脑应用研究所


中科院计算机语言信息工程研究中心


《自然语言人机接口的设计与实现》


东北大学


清华大学计算机科学与技术系

识别模型

校、院、所

内容

基于规则的机器翻译系统(国外)


乔治敦大学的机译系统

法国格勒诺布尔大学的俄法机译系统

加拿大的TAUM-METEO系统

日本的ATLAS

日本的其他实用性机译系统

法国纺织研究所的 TITUS-IV 系统

美国的SYSTRAN系统

美国的WEIDNER系统

美国的PAHO系统

德国的METAL系统

德国的SUSY系统

EUROTRA系统

日本的Mu系统与ODA计划

DLT系统




基于规则的机器翻译系统（国内）


俄汉机译系统

英汉题录机译系统TITLE

汉-法/英/日/俄/德多语言机器翻译系统FAJRA

“译星”英汉系统

“高立”英汉系统

863-IMT/EC英汉系统

Matrix英汉系统

通译英汉-汉英系统

雅信英汉系统

Readworld英汉系统

Sino-Trans汉英-汉日机译系统

E-to-J英日机器翻译系统




国外本挖掘工具


IBM的文本智能挖掘机

高级 搜索引擎(Advanced Search Engine)——TextMiner；

Web访问工具(Web Access Tools)——包括Web搜索引擎NetQuestion和Web Crawler；

文本分析工具(Text Analysis Tools)。

IBM的TextMiner ：其主要功能是特征抽取、文档聚集、文档分类和检索。

支持16种语言的多种格式文本的数据检索；

采用深层次的文本分析与索引方法；

支持全文搜索及索引搜索，搜索的条件可以是自然语言和布尔逻辑条件；

是Client/Server结构的工具，支持大量的并发用户做检索任务；

联机更新索引，同时又能完成其它的搜索任务。

国外文本挖掘工具（续）

Autonomy公司最核心的产品是Concept Agents。

在经过训练以后，它能自动地从文本中抽取概念。

TelTech公司

提供专家服务；

专业文献检索服务；

产品与厂商检索服务；

　　TelTech成功的关键是建立了高性能的知识结构。它采用主题法，其主题词表分为不同专业，共有3万多个，由数位知识工程师维护，每周更新500～1200个词。

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=27793