后缀树及其算法在文本挖掘中的应用研究-国家科技图书文献中心.doc

PAGE  PAGE 5 后缀树及其算法在文本挖掘中的应用研究 李海涛 (中国科学技术信息研究所，?北京 100038) 【摘要】 本文首先引入了一种新颖的数据结构——后缀树的相关概念，在此基础上，对其特点和算法的构建进行了论述，并探讨了后缀树及其算法在中文分词、关联分析中的应用，然后以中文文档聚类为例，结合中文需要分词的特点，设计出了基于后缀树聚类算法的聚类系统结构。 【关键词】短语、短语串、后缀树、关联分析、聚类 The Study of Suffix Tree and its Arithmetic’s Application in Text Mining Li haitao (Institute of Scientific Technical Information of China, Beijing 100038) 【Abstract】 This paper introduces a novel data structure — suffix tree conception, and then discusses its particularity and its Arithmetic’s constructing process, discusses suffix tree and its Arithmetic’s Application in Chinese word segmentation and association analyses, at last takes the Chinese document clustering as an example ,considering the need of Chinese word segmentation, designs the clustering system’s structure based on suffix tree clustering Arithmetic. 【Keywords】 phrase, phrase cluster, suffix tree, association analyses, clustering 1. 引言 存储信息使用最多的是文本，事实上，最近研究表明公司信息有80%包含在文本文档中，所以文本挖掘被认为比数据挖掘具有更高的商业潜力。文本挖掘是抽取有效、新颖、有用、可理解的、散布在文本文件中的有价值知识，并利用这些知识更好地组织信息的过程。 文本挖掘的主要研究内容包括关联分析、文本分类、文本聚类等。 关联分析是首先收集经常一起出现的关键字、词汇或短语，然后找出其关联和相互关系[1]。在这里笔者将其分为字、词和短语三种级别的关联分析。 文本分类是按照预先定义的主题类别，为文档集合中的每个文档确定一个类别。这样用户不但能够方便地浏览文档，而且可以限制有哪些信誉好的足球投注网站范围来使文档的有哪些信誉好的足球投注网站更容易、快捷。 文本聚类的目标和文本分类是一样的，只是实现的方法不同，文本聚类是无教师的机器学习，在文档归类之前没有定义好的类可供选择，在文本聚类时，将所有类型接近的文档归为一类，使类型相同的文档尽量归为一???，类型不相同的尽量隔离开来，聚类的标准可以是文本的属性，也可以是文本的内容。 2. 后缀树相关概念 2.1 短语 文中短语是一个具有一个或者更多的词的有序序列，一个短语可能是任意的长度，但该序列不会穿过短语边界。短语边界是文档解析器识别特殊语法记号时插入到短语间的，这些记号可以是标点符号标记(句号‘。’逗号‘，’分号‘；’问号‘？’等) 或者 HTML 标签 (例如p, br, li, td等)，文档的开头和结尾也被认为是短语边界[2]。 2.2 短语串 一个短语串就是一个至少被两个文档共享的短语和包含该短语的所有文档。一个最大短语串必须满足在不减少文档的数量的情况下，该短语串的短语不能用任何该语言类型的词来扩充。 2.3 后缀树 一个后缀树是一种数据结构，它支持有效的字符串匹配和查询。 一个具有m个词的字符串S的后缀树T，就是一个包含一个根节点的有向树，该树恰好带有m个叶子，这些叶子被赋予从1到m的标号。 每一个内部节点，除了根节点以外，都至少有两个子节点，而且每条边都用S的一个非空子串来标识。出自同一节点的任意两条边的标识不会以相同的词开始。后缀树的关键特征是：对于任何叶子i，从根节点到该叶子所经历的边的所有标识串联起来后恰好拼出S的从i位置开始的后缀，即S[i,…,m]。树中节点的标识被定义为从根到该节点的所有边的标识的串联。 图1示意了字符串 I know you know I know 的后缀树。内部节点用圆来表示，叶子用矩形来表示,该例子中有六个叶子，被标号为1到6。 终止字符在图中被省略掉了。 图