服装方面的文本分类系统

服装方面的文本分类系统 中图分类号:TP311.5 单位代号:11903 号: 密 级: 学 SHANGHAI UNIVERSITY MASTER’S THESIS 题 目 作 者 学科专业 计算机软件与理论 导 师 完成日期 2010年2月 上海大学 本论文经答辩委员会全体委员审查，确认 符合上海大学硕士学位论文质量要求。 答辩委员会签名: 主任: 委员: 导 师: 答辩日期: 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 原 创 性 声 明 本人声明:所呈交的论文是本人在导师指导下进行的研究工作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名:___________日 期__________ 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即:学校有权保留论文及送交论文复印件，允许论文被查阅和借阅;学校可以公布论文的全部或部分内容。 (保密的论文在解密后应遵守此规定) 签 名:__________ 导师签名:___ _____日期:__________ II 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 上海大学工学硕士学位论文 基于 硕 士 生: 导 师: 学科专业:计算机软件与理论 上海大学计算机工程与科学学院 2010 年 2 月 III 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University A Dissertation Submitted to Shanghai University for the Degree of Master in Engineering The M.D. Candidate: Supervisor: Major:Computer Software and Theory School of Computer Engineering and Science Shanghai University February, 2010 IV 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 摘 要 随着科技的发展和网络的普及，人们可获得的数据量越来越多，这些数据多数是以文本形式存在的。面对如此大规模而急剧膨胀的信息数据，如何有效地组织和管理这些数据，使得快速、准确、全面地从中找到用户所需要的信息是当前信息科学与技术领域所面临的一大挑战。文本分类作为处理和组织大量文本数据的关键技术，可以在较大程度上解决信息的这一复杂问题，方便用户快速、准确地得到所需要的信息。 本文分析比较目前常用的权重算法，得出目前常用权重算法应用于文本分类时的不足之处，并在TFIDF的基础上，结合文本分类的需要，改进TFIDF形成了一种新的权重算法。为提高文本分类的速度，本文在总结前人成果的基础上，提出一种新的文本分类算法。算法首先用贝叶斯聚类法聚类，分成几块，减少计算量。然后求文档网络(即最小世界网络)，将距离中心向量远的样本进行裁剪，然后对裁剪后的训练样本进行文本分类。 为了为本文文本分类研究工作提供实验平台，本文 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 实现了一个服装描述文本分类系统，该系统由关键短语抽取模块、特征选择模块、文本分类模块组成。三个模块之间相互独立且具有统一的接口，对其中任何一个模块的更改对其他模块都不会产生影响，同时由于具有统一的接口，所以模块之间的调用也十分的方便。 为了验证本文提出的算法的有效性和可行性，本文在服装描述文本分类系统上对相同的测试文本集在未裁剪和裁剪后两种情况下进行了对比验证实验并对实验结果进行了分析。实验证明封闭测试和开放测试中，无论是准确率和召回率，经过裁剪后的训练文本用于文本分类的效果都有所提高，从而证明了本文提出的算法的有效性和可行性。 关键词:权重 特征选择 文本分类系统 I 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University ABSTRACT With the development of technology and network penetration, it is more and more data available, most of these data is the text exist.Faced with such a large scale and rapid expansion of information and data, how to effectively organize and manage data to make fast, accurate and comprehensive user needs to find the information is current information science and technology faces a major challenge. Text classification process and organize large amount of text as the key technology of data, in a large extent, this complex problem solving information, user quickly and accurately obtain the information they need. This paper analyzes the comparative weight of the commonly used algorithms, the commonly used weight obtained the text classification algorithm is applied to the inadequacies and TFIDF based on the combination of text classification needs, to improve the formation of a new TFIDF weighting algorithm. To improve the speed of text classification, this paper summarizes the basis of previous results, a new text classification method. Firstly, clustering by Bayesian clustering method, divided into a few, reduce the amount of calculation. Then find the document network (ie, minimum World Network), will be far from the center of the sample vector cut, then cut the text after the classification of training samples. Text classification in order to provide this experimental platform, the paper design and implement a clothing description text classification system, the system consists of a key phrase extraction module, feature selection module, the text categorization module. Three modules are independent and have a unified interface, on any one module will not change the impact on other modules, and because with a unified interface, so the calls between modules is also very convenient. In order to verify the validity of the proposed algorithm and the feasibility of this classification system in the garment description text test text on the same set of cut and cutting without the latter two cases were compared with experiment and the experimental results verify the analysis. Experiments show that the closed test and open test, both precision and recall rate, after cutting through the training text for text classification results are improved, which proves the proposed algorithm is effective and feasible. Keywords: feature selection weight text categorization system II 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 目 录 摘 要................................................................ I ABSTRACT............................................................. II 第一章 绪论........................................................... 1 1.1课题研究目的与意义 ....................................................................................................... 1 1.2国内外研究状况 ............................................................................................................... 2 1.3研究的主要內容 ............................................................................................................... 4 1.4 论文的组织 ...................................................................................................................... 5 第二章 文本分类理论基础及相关算法..................................... 6 2.1分词 .................................................................................................................................. 6 2.1.1中文分词 .................................................................................................................... 6 2.1.1关键短语 .................................................................................................................. 17 2.1.1关键短语的获取 ...................................................................................................... 18 2.2停用词处理....................................................................................................................... 7 2.3特征选择 .......................................................................................................................... 8 2.3.1文档频率 .................................................................................................................... 9 2.3.2期望交叉熵 ................................................................................................................ 9 2.3.3信息增益 .................................................................................................................. 10 2.3.4互信息 ..................................................................................................................... 11 2.3.5文本证据权 .............................................................................................................. 11 22.3.6统计 ..................................................................................................................... 12 , 2.4特征加权 ........................................................................................................................ 12 2.4.1布尔权重 .................................................................................................................. 13 2.4.2词频权重 .................................................................................................................. 13 2.4.3IDF权重 ................................................................................. 错误～未定义 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 签。17 2.4.4基于嫡概念的权重 ............................................................... 错误～未定义书签。18 2.4.5TFIDF权重 ................................................................................................................. 14 III 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 2.4.6改进权重 .................................................................................................................. 21 2.5文本表示 ........................................................................................................................ 14 2.5.1布尔模型 .................................................................................................................. 14 2.5.2向量空间模型 .......................................................................................................... 15 2.5.2基于类特征表示模型............................................................................................... 15 2.6小结 ................................................................................................................................ 15 第三章 基于文档网络的样本裁剪方法................................... 25 3.1基本概念 ..................................................................................... 错误～未定义书签。22 3.4小结 ............................................................................................. 错误～未定义书签。24 第六章 结论与展望.................................................... 42 6.1结论 ................................................................................................................................ 42 6.2展望 ................................................................................................................................ 42 参考文献............................................................. 44 作者在攻读硕士学位期间公开发表的论文................................. 47 作者在攻读硕士学位期间所作的项目..................................... 48 致 谢............................................................. 49 IV 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 第一章 绪论 1.1课题研究背景与意义 我们正处在一个信息急剧丰富的时代，即信息时代，信息技术已经涉及到了生活的各个方面。信息技术使得知识传播的速度大大加快，人们获取信息的速度也大大提高。人们时时刻刻自觉不自觉地接触到信息。特别是近十多年来，随着Internet的广泛应用，互联网上的数据增长迅速。截止到2010年3月，全球网页服务器数大约206,675,938个，涉及到的网页基本上都是静态文本的形式。 面对如此大规模而急剧膨胀的信息数据，如何有效地组织和管理这些数据，使得快速、准确、全面地从中找到用户所需要的信息是当前信息科学与技术领域所面临的一大挑战。文本分类作为处理和组织大量文本数据的关键技术，可以在较大程度上解决信息的这一复杂问题，方便用户快速、准确地得到所需要的信息。因此，自动文本分类已作为一项具有较大实用价值的关键技术，得到了广泛关注，取得了很大进展。 文本分类作为信息过滤、信息检索、语义辨析、数字化图书馆等领域的技术基础，有着广阔的应用前景。 1. 信息过滤 网络上信息的获取非常方便，但是获得的信息量越大，人们对信息的处理就越困难。信息过滤就是对这些信息量进行过滤，保留相关信息，去除无关信息。信息过滤有两个显著的特点，那就是个性化和主动化。既可以将用户反感的信息过滤掉，也可以将用户感兴趣的信息过滤出来，主动地推送给用户。现在较典型的应用就是邮件过滤。 2. 信息检索 文本分类最早应用在信息检索领域，将大量的文本信息按主题层次归类组织极大地简化了对信息的检索。如果按照类别对文本进行检索或对检索结果进行文本分类，都可以提高检索的查准率。 3. 语义辨析 语义辨析是确定多义词在不同的语言环境中的含义，显然其涉及到自然语言处理和机器翻译。对中文文本分类来说，语义辨析是自然语言理解与分类中很重要的环节。 4. 数字图书馆 1 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 图书馆的数字化管理已是大势所趋，图书期刊全文数字化的比重日益增大。对图书进行归类时，图书管理员不可能对各个学科都非常了解，因此使用自动文本分类技术，可以帮助图书管理员正确地对图书资料进行归类。 1.2国内外研究状况 国外对于文本分类的研究开展较早。20世纪50年代末，H.P.Luhn在这一领域进行了开创性的研究，他首先将词频统计的思想应用于文本分类中。1960年Maron在Jounanl of ASM上发表了有关自动分类的第一篇论文《On relevance，probabilistic indexing，and information retrieval》。1962年博科(H.Borko)等人提出了利用因子分析法进行文献的自动分类。之后许多学者在这一领域进行了卓有成效的研究。文本自动分类主要经过了三个发展阶段。 第一阶段是20世纪80年代前。在这一时期，模式识别和信息检索相继发展成一门学科。Maron和Kuhn提出了概率标引模型，并应用于信息检索领域。1962年Rosenblatt设计了感知机，通过具有阈值的神经元处理二类分类问题。Salton于1975年提出了向量空间模型用于对文本进行描述。这一阶段主要是集中在对分类理论的研究，应用方面则主要是用于信息检索。 第二阶段是20世纪80年代到90年代。这一阶段主要是采用传统的知识工程技术，根据专家提供的知识形成规则，手工建立分类器。这实际上是专家系统。这一时期，Hayes等设计的CONSTRUE是典型的代表。信息检索技术逐渐成熟应用，最著名的信息检索系统是Salton的SMART系统。这一阶段分类器的特点:一是依赖于专家;二是面向特定的领域，一旦应用领域发生变化，需要重新生成规则;三是分类器建设周期长，工作量大，分类质量难以保证。 第三阶段是20世纪90年代之后。互联网技术的发展，网页数据量急剧增加，耗时、灵活性差、应用难度大的知识工程方法越来越不能满足实际应用的需要，于是逐渐被机器学习的方法取而代之。基于机器学习的文本分类方法克服了以前手工建立分类器的缺点，使得文本分类具有了真正的实用价值。这一时期分类器的特点:一是分类知识源于机器对训练样本集的自动学习，不再依赖于专家;二是学习、分类过程不用人工干预，分类效率和准确率都有不同提高。 2 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University Yang对KNN文本分类器的分类性能进行了深入研究，并把它的分类性能和朴素贝叶斯分类器、神经网络、最小线性平方、支持向量机等分类器进行了实验对比，实验结果表明KNN文本分类器是分类性能表现良好的一种文本分类模型。Yang提出的这种按距离对类别进行加权的KNN称为Whirl算法。Sebastiani对KNN、神经网络、朴素贝叶斯、Roeehio、决策树等多种分类方法进行了综述。Lim使用启发式信息对KNN进行权重调节，提高了KNN分类器的分类性能。 为了提高分类速度，Makoto等提出先将样本用层次贝叶斯聚类法(Hierarchical Bayesian Clustering，HBC)进行聚类，然后用聚类中心代替训练集对新文本进行KNN分类。Lam提出了一种使用广义样本进行KNN分类的方法。 国内的文本分类研究起步比较晚，始于上世纪80年代初。1981年，侯汉清对计算机在文献分类工作中的应用进行了探讨，并介绍了国外在计算机管理分类、计算机分类检索、计算机自动分类、计算机编制分类等方面的概况。此后，国内的研究者在英文文本分类研究的基础上，结合中文文本的特定知识，然后应用于中文之上，形成中文文本自动分类研究体系。 网页自动分类是将文本分类方法应用到网页资源中。主要有以下几个步骤:文本预处理、分词、权重计算、特征提取、降维过程、分类器分类。这些关键技术的研究和实现对最终的分类算法都有一定程度上的影响。自从1980年代初自动分词被提出以来，有众多的研究者进行了研究，涌现了许多成功的汉语分词系统。如北京航空航天大学的CDWS和CWSS分词系统，分词速度为200字每秒;清华大学黄昌宁、马晏等开发的SEG系统，分词速度为258字每秒;中科院计算所的汉语词法分析系统ICTCLAS等等。在文本分类中，特征选择方法大致有:特征频度、文档频度、特征熵、交互信息、信息增益、期望交叉熵、文本证据权等。这些统计量从不同的角度度量特征对分类所起的作用。2005年，李荣陆等人使用最大熵模型进行了中文文本分类;通过模拟实验比较和分析了不同的中文文本特征生成方法、不同的特征数目以及在使用平滑技术的情况下，基于最大熵模型的分类器的分类性能[l6]。王建会等人提出了互依赖和等效半径的概念，并将两者相结合，提出一种基于互依赖和等效半径、易更新的SECTILE分类算法; SECTILE算法计算复杂度较低，而且 3 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 扩展性能较好，适用于大规模场合。2006年，尚文倩等人介绍了另一种新的基于基尼指数的文本特征选择算法;使用基尼指数原理进行了文本特征选择的研究，构造了基于基尼指数的适合于文本分类特征选择的特征选择评估函数。 李荣陆、胡运发等采用基于密度的训练样本裁剪方法加快了KNN分类器的分类速度，提高了分类的准确率。李蓉、叶世伟、史忠植等将kNN和SVM相结合，提高了分类器的分类性能，并很好地解决了核函数参数的选择 卜凡军提出了一种改进的KNN文本分类算法—PKNN，该算法基于投影寻踪理论和iDistance索引结构，能够通过对一维投影距离的搜索快速获得与待分类样本最近的小样本库，然后通过计算与小样本库内文本的相似度即可获得最近的K个样本，而无须与整个训练样本库的文本进行计算，因而在保证分类精度的同时明显提高了计算的效率。 1.3研究的主要內容 本文对文本分类的理论基础及相关技术，包括分词、特征选择、特征加权及分类算法等进行了全面的探讨和研究。特征选择是文本分类的关键技术之一，特征选择结果的好坏将会直接影响文本分类的分类效率和分类效果，所以本文详细探讨了特征选择技术，并在TFIDF的基础上提出了一种权重算法。为了提高分类速度，本文在Makoto、Lam、李荣陆等人研究成果的基础上，提出了综合运用贝叶斯聚类法和文档网络的算法。本文设计了一个服装方面的文本分类系统，在此系统上对本文所提特征选择方法和文本分类方法的速度和准确度进行了实验验证。 论文主要研究内容如下: (1)分析比较目前常用的权重算法，得出目前常用权重算法应用于文本分类时的不足之处，并在TFIDF的基础上，结合文本分类的需要，改进TFIDF形成了一种新的权重算法; (2) 为提高文本分类的速度，本文在总结前人成果的基础上，提出一种新的文本分类算法。算法首先用贝叶斯聚类法聚类，分成几块，减少计算量。然后求文档网 4 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 络(即最小世界网络)，将距离中心向量远的样本进行裁剪，不仅减小了训练样本的规模，而且实验证明提高了分类效果。 (3)设计实现了一个集中文分词、特征选择、文本分类功能于一体的服装方面的文本分类系统，对文中提到的权重算法和文本分类方法进行实验验证。 1.4 论文的组织 本文所有内容都围绕研究课题展开，具体来说，论文共分为六个章节，论文的结构以及各章节的主要内容如下: 第一章介绍本研究课题的研究背景及研究意义、文本分类技术的国内外研究现状以及本文主要研究内容及论文的组织结构。 第二章对文本分类的理论基础及相关算法进行了详细的介绍，主要包括分词、特征选择、特征加权、分类算法，从而为后续的研究工作奠定基础。 第三章对文本分类的关键技术进行了深入研究，对文本分类的权重算法进行了探讨并根据TFIDF改进了权重算法，研究了文本的向量空间模型和基于类特征的表示。 第四章深入研究了基于文档网络的样本裁剪方法，并研究了文本网络的构造。算法首先用贝叶斯聚类法聚类，分成几块，减少计算量。然后求文档网络(即最小世界网络)，选距离中心向量远的一个代替最小世界网络。反复上述步骤直到满足条件。每个聚类块不大于规定个数的代表样本。 第五章介绍本文实验方法并对实验结果进行分析。主要内容包括文本分类系统的设计、文本分类系统的实验测试及实验结果的分析。 第六章总结与展望，主要对论文所做的工作做简单总结，并对以后进一步研究方向进行了展望。 5 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 第二章 文本分类理论基础及相关算法 文本分类作为数据挖掘的一个新主题，己经引起人们的极大兴趣。文本分类技术的深入研究和在信息检索领域中的应用，进一步提高了信息检索的精度和效率。本章主要介绍了中文文本分类的基本概念和文本分类的相关技术和算法，主要有中文分词、特征选择算法、权重算法和应用较为广泛的分类算法。 2.1分词 2.1.1中文分词 分词主要是针对汉语、阿拉伯语等东方语言文本来说的，对于英语、法语等西方语言中词与词是使用空格隔开的，因此不需要进行分词处理。目前中文分词方法至少有十几种，其中最常见的有:正向最大匹配法、反向最大匹配法、双向最大匹配法、设立切分标志法、最佳匹配法以及机械分词加歧义校正法和知识分词方法等等。这些方法虽然名称各异，分词速度也不尽相同，但从本质上可将它们分为三类:基于词典的分词方法、基于理解的分词方法、基于统计的分词方法。 基于词典的分词方法又叫做机械分词方法,它是按照一定的策略将待切分的字符串与词典中的词进行对比，若在词典中找到该字符串，则匹配成功(即分出一个词)。按照分词方向的不同，基于词典的分词方法可以分为正向匹配和逆向匹配;按照长度的不同，可以分为最大匹配和最小匹配;按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种基于词典分词方法如下:正向最大匹配法、逆向最大匹配法、双向最大匹配法。 在实际应用中,常常将上述方法结合起来。例如，将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。 基于理解的分词方法又称人工智能分词法，该方法是通过让计算机模拟人对句子的理解,达到识别词的效果。基本思想就是在分词的同时进行语法、语义分析,利用 6 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 语法和语义来处理歧义现象。它主要有三个部分:分词系统、语法语义分析系统、控制部分。在控制部分的协调下,分词系统可以获得有关词、句子等的语法和语义信息来对分词歧义进行判断,即模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性,难以将各种语言信息组织成机器可直接读取的形式,因此目前还没有出现实用的基于理解的分词系统。 基于统计的分词方法，在汉语中，词是稳定的字组合，因此在上下文中，相邻的字同时出现的次数越多，它就越有可能是一个词。因此字与字相邻出现的频率或概率能够较好的反映成词的可信度可以对语料中相邻出现的各个字的组合的频度进行统计，计算它们的互现信息互现信息体现了汉字之间结合关系的紧密程度当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个新词。该方法不需要词典，因此叫做无词典分词法或统计分词方法。 基于统计的分词算法的基本思想是:找出待分词文本中的所有可能的切分结果，对每个切分结果利用能够反映语言特征的统计数据计算它的出现概率，然后从结果中选取概率最大的一种。 总之，基于词典的分词方法不能识别出新词，易产生歧义;而基于统计的分词算法也有一定的局限性，总是抽出一些共现频度较高的字符串，其中包括不是词的常用字组，时间和空间复杂度都比较大。因此我们设计分词系统使用一部基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 2.2停用词处理 停用词指的是那些出现频率很高但是对文本分类却没有太大作用的词。经过分词处理的文本，并不是所有的特征都对构造向量空间模型和分类有帮助，相反，将对文本分类没有帮助的词作为特征项，会对分类的精度造成很大的影响。无论是中文还其他语言，都有很多停用词。停用词几乎出现在任何一个文本中，但是它们对这个文本所表达的内容几乎没有任何贡献，更多的作用是在语法上。所以如果以这 7 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 些单词作为文本特征的话，即使是内容上完全不同的两个文本也会因为这些共有的特征而很难被区分开来。因此，有必要将这些词从原始的文本中过滤掉，这个过程称为停用词过滤或停用词处理 停用词主要是指文本中的助词、副词、连词、代词、叹词、疑问词、量词、数词等。例如:助词中的“的，得，地，呢”;副词中的“尤其，特别，很，十分”;连词中的“和，及，或者”;代词词中的“我，你，他，其”;叹词中的“啊，喂，哎呀”;疑问词中文中的“为什么，哪里”;量词中的“个，只，辆，斤，次”;数词中的“第一，第二，一倍”。可以看出，在文本中这些词在不同文本中的词频和在同一文本中的词频是非常大的，如果不除去，会对特征选取造成很大的影响。 通过将出现在停用词表中的单词直接进行过滤，方法简单，也能将一些对分类无用的单词滤掉，防止这些在文本中大量出现的词将有用词“淹没”。实际上我们可以将这一过程理解为特征空间的降维，只不过这种降维工作的实现比较粗糙。 2.3特征选择 去停用词后，特征空间的维数有所降低，这就是被称为文本特征空间的粗降维过程。虽然如此，特征空间的维数仍然是成千上万维，文档分类的一个核心难题就是特征空间的高维性(high dimensionality)。这对于大多数的分类器来说，是难以忍受的，而且这么多维的特征对将进行的分类过程来说未必都是有益的，甚至有些会大大干扰训练效果、降低分类性能，因此有必要采取措施进一步地降低特征空间的维数。因此必须通过特征选择来进行降维，保存那些对分类贡献大的特征。 所谓特征选择是指从最初的n个特征中选取t(t 标识 采样口标识规范化 下载危险废物标识 下载医疗器械外包装标识图下载科目一标识图大全免费下载产品包装标识下载 文本内容的贡献度和区分文本分类的能力。在特征子集中的特征词，有些特征词的区分类别能力强，有些特征词的区分类别能力弱，有些特征词甚至是噪音，因此有必有对这些特征词进行进加权处理，其目的就是要尽量提高具有强区分类别能力特征词的权重，降低那些弱区分类 12 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 别能力特征词的权重，抑制噪音特征词。因此特征项的权重综合反映了该特征项对标识文本内容的贡献度和文本内容之间的区分能力。特征项在不同文本中出现的频率满足一定的统计规律，因此可以通过特征项的频率特性计算其权重。一个有效的特征项集合必须具有以下两个特点: 1.完全性:特征项能够完整反映目标文本的内容; 2.区分性:特征项具有将目标文本和其它文本相区分的能力。 根据其特点，特征项权重的计算满足以下原则:一是正比于特征项在文本中出现的频率;二是反比于文本集中出现该特征项的文档频率。 有很多的学者对特征权重的估算方法进行了大量的研究，最经典并被广泛使用的特征权重估算方法还是TF-IDF方法。文本分类中常用的特征权重估算方法有:布尔权重、词频权重、IDF权重、基于嫡概念的权重、TFIDF权重等。 2.4.1布尔权重 布尔权重也被称作均权，布尔权重是最简单的一种权重估算方法，这种方法将所有特征同等对待，既不突出也不抑制任何一个特征。如果某个词在文本中出现，其权重则为1，否则为0。 10tf,,ik (2.7) W,,ik00tf,ik, 其中为特征项在文本中出现的次数。这种方法的缺点是无法体现一wDtfkiik 个词在文本中的重要程度。 2.4.2词频权重 词频权重又称TF权重，或称特征项频率权重。词频，是指特征词在文本中出现的次数。不同类别的文档，在特征项的出现频率上有很大差异，所以特征词频率信息可以作为文本分类的重要参考之一。一般情况下，某一特征词词频较大在该类文本中具有较高的权重，或者说该特征词对该类文本具有比较大的代表性。其权重计算公式为: 13 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University tftf,0,ikik (2.8) W,,ik00tf,ik, 其中，含义同上。实际分类中，各个文本的长度基本上都不相同，甚至相差tfik 很大，各文本包含的字数、词数也可能差别会很大，这对词频会造成直接影响，因此要对词频作归一化处理。 2.4.3基于熵概念的权重 熵(entropy)是系统状态不确定性的一种度量，特征词中所包含信息量的多少，基于熵概念的权重能够很好地反映特征词与类别之间的相关程度: 对上式分析可知，当特征词分布极度均匀时，的值为-1，而只在一个 文档中出现时，的值为0。 2.5分类算法 目前最常使用的文本分类算法有:中心向量算法、kNN分类算法、朴素贝叶斯分类算法、支持向量机，具体描述如下: 2.5.1中心向量算法 类中心向量最近距离判别算法的思想十分简单。该方法根据算术平均值对训练集中的每类生成一个代表该类的中心向量，即该中心向量的每一维是训练集里该类中该维权值的平均值。训练过程的任务是生成所有类别的中心向量，而在分类阶段，系统利用最近距离判别法确定文档的类别，即把文档分到与其最相似的类别中。 14 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 2.5.2 KNN算法 KNN全称是k-nearest neighbor，它是最著名的模式识别统计学方法之一，己经有四十多年的历史，很早就被用于文本分类研究。它是在Reuters语料(包括21450版本和Apte给出的集合)上取得最好结果的文本分类算法之一。 KNN分类算法也是基于向量间相似度的分类方法。其思想非常简单:取待分类样本d的k个近邻，用这k个近邻中来判定待分类样本d属于哪一类。规则中一个显然的问题是:当样本分布密度不均匀时，只按照前k个近邻样本的顺序而不考虑它们的距离差别是不适当的，会造成分类器分类性能的下降。因此，根据各个近邻距待分类样本的距离不同对它们的作用进行加权，一直是人们研究的热点。目前，kNN分类通常采用的加权 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 是以近邻与待分类样本之间的相似度作为加权因子，比经典的kNN获得了更高的分类精度。 2.5.3支持向量机 支持向量机(Support Vector Machine，简称SVM)是Vapnik与Corters于1995年首先提出的，在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。传统统计模式识别的方法都是在样本数目足够多的前提下进行研究，所提出的各种方法只有在样本数趋于无穷大时其性能才有理论上的保证，而在多数实际应用中，样本数目通常是有限的，很多传统方法都难以取得理想的效果。 Vapnik等人早在20世纪60年代就开始研究有限样本情况下的机器学习问题，在1992到1995年间，有限样本情况下的机器学习理论研究逐渐成熟起来，形成了一个较完善的理论体系-统计学习理论，目前仍处在不断发展阶段。 2.6小结 本章论述了文本分类的理论基础及相关算法。分词部分主要介绍了中文分词。特征选择算法部分总结了常用的几种特征选择方法，包括文档频率、期望交叉熵、信息增益、互信息和文本证据权。特征加权算法介绍了布尔权重、词频权重和基 15 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 于熵概念的权重。最后介绍了常用的分类算法，包括中心向量算法、KNN算法和支持向量机。这些为后续章节的研究提供了理论和技术依据。 16 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 第三章 文本分类关键技术 3.1关键短语 3.1.1关键短语的概念 相对来说，文本分类需要的资源方面研究的较少，如文本表示中特征项的粒度选择和获取,特别是概念、短语、词和字究竟哪个更适合作为文本表示的特征项的问题缺乏系统的研究。文本分类的进一步改进不仅在算法方面，还应该立足于影响文本分类最底层、最根本的因素,即文本表示中的特征项，文本分类的改进应该专注于提高特征项的完整独立程度。相对于字、词和N元组，关键短语结构稳定、语义完整、统计意义较强，更有利于表达文本内容特征，提高文本分类的效果。 在文本分类方法中，向量空间模型基于这样一个关键假设:文章中词条出现的顺序是无关的，对于文档的类别所起的作用是相互独立的。但实际上,句子中词条之间根本不是独立的，同样的词，其顺序不同，表达的含义就不相同。由此，向量空间模型一定的缺陷在于它没有考虑文本上下文间的语义关系和潜在的概念结构(如词汇间的共现关系、顺序关系等)，特征项之间独立性不够,不能充分反映出文本总体面貌。在概率模型中,也存在类似的贝叶斯假设,即特征项之间被假定为是相互条件独立的。 因为难以克服贝叶斯假设和向量空间模型的先天缺陷，因此，基于其之上的很多算法准确率都不够理想。最基本最有效的改进还应该是从向量空间模型和概率模型的文本表示入手，文本分类的改进应该专注于提高特征项的完整独立程度。比如用语义概念、词汇之间的互信息或搭配来提高特征项满足独立性假设的能力。例如,“医药”词语只会归类到“医药”类,“板块”词语则倾向于归入到“地理”类,“医药板块”短语语义更独立完整,更适合表示文本内容,可准确分到“经济—股市基金”类。 因此,我们认为文本分类的改进还应该立足于影响文本分类最底层、最根本的因素:文本表示中的特征项。文本分类的改进应该专注于提高特征项的完整独立程度。 17 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 简单地说，关键短语是具有强文本表示功能的特征短语。所谓强文本表示功能，是指在文本表示时，能将文本的内容特征(例如领域类别、主题思想、中心意义等)鲜明地表示出来。例如，常见的虚词性成分(如“总而言之”)的文本表示功能较弱，而一些领域性强的体词性成分(如“封闭式基金”)则文本表示功能较强。具体地说，可以从三个角度来界定关键短语: 1.结构上:结构较稳定，具有一定的凝固性。 2.语义上:表意完整单一、所指明确，在意义上有一定的完整性和专指性。 3.统计上:在大规模真实文本中具有一定的流通度，并非临时性的组合，可重用性强，具有统计上的意义。 3.1.2关键短语的获取 目前国内外有许多基于规则、统计或规则统计结合的短语发现方法。与基于词典的方法相比较，基于统计的分词方法具有一些难得的优点，如不受待处理文本的领域限制、不需要词典、能够有效地自动排除歧义、能够识别新词怪词等。基于统计的中文分词方法主要思想是:词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻出现的概率或频率能较好反映成词的可信度。最常用的基于统计的分词方法原理有三种:互信息原理、n-gram原理及t测试原理。基于n-gram原理的分词方法是一种常用的基于统计的分词方法，其基本思想是:一个单词的出现与其上下文环境中出现的单词密切相关，第n个词的出现与其前n-1个词相关。设是长度为n的字串，则字串w的wwwL12n 似然度用方程表示为: n PWPwwww()(|),L ,,，,，,121iinini,1i 从公式上看，基于n-gram原理的方法非常复杂，且其中的概率参数需要通过大规模的语料库来计算。鉴于此，本文提出了一个统计的基于互信息原理的扫描中文文本分词方法，该方法较n-gram方法降低了词频统计的工作量，且算法的计算复杂度也较低。 定义1:对有序汉字串AB中汉字A、B之间的互信息定义为: 18 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University PABPAB(,)(,) IABPABPAB(,)max((,)log,(,)log),PAPB()() 其中，P(A,B)为汉字串AB出现的概率，P(A)为汉字A出现的概率，P(B)为汉字B出现的概率。假定它们在语料库中出现的次数分别计为n(A)、n(B)、n(AB),n是统计语料库中的词频总数。上式可简化为: nABnAB(,)(,) IABPABPAB(,)max((,)log,(,)log),nAnB()() 互信息反映的是字与字之间的静态结合，汉字之间的互信息体现了汉字之间结合关系的紧密程度，互信息值越大表示汉字之间关系越紧密。当某一字串结合的紧密程度高于给定的阈值时，便可认为此字串可能构成了一个词。对训练文本中相邻出现的各个字之间组合的频度进行统计，计算出相邻字出现的频率，用这个频率与字单独出现的频率进行比较，计算出汉字之间的互信息，进而判断该字串是否组成词语。 基于互信息的分词方法对训练文本中相邻出现的各个字的组合频度进行统计，通过计算长为m的字串中相邻字之间的互信息来判断是否构成m字词，m大于2的任何整数。本方法中对m字词的判断基于如下的假设，对m字串中的任意相邻的字及 (i>=1且i<= m-1)，均有给定阈值。 wwIww(,),ii，1ii，1 在进行分词之前首先对文档进行预处理，利用显式和隐式的切分标记，如标点符号、数字、ASCII字符以及出现频率高、构词能力差的单字词、数词、单字常用量词模式等将训练文本切分成短的汉字串，这大大地减少了需要统计的无效字串的数量和高频单字或量词边界串。 3.2权重算法 3.2.1 TF权重 特征频率(Term Frequency, TF)也称为词频，是指特征词在文本中出现的次数。在不同类别的文档中，特征项的出现频率应该都是不同的，所以特征词频率信息可以作为文本分类的重要参考之一。词频权重简单认为特征词出现的频率和它在 19 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 文本中的权重成正比，如果某特征词在一类文档中出现的频率越大，那么该特征词在该类文档中权重就越大，或者说该特征词对该类文档具有比较大的代表性。词频的计算公式为: 其中， (表示特征词在文档中出现的次数。 实际应用中，由于不同类别文本的长度不可能存在一致，这样就会对词频权重造成直接的影响，因此应对词频权重做归一化处理以消除这种影响。另外，仅考虑特征频率会造成对高频特征词的过度依赖，忽略了那些带有很大信息量的低频特征词。 3.2.2 IDF权重 IDF(Inverse Document Frequency)权重，又称反比文档频率。反文档频率反映的是特征词在文档集中分布情况。IDF的思想是:在一部分文档中出现的特征词的重要程度要高于那些在大多数文档中都出现的特征词，如果包含特征词的的IDF权重越大，也就是说出现特征词的文档数越小，那么特征词的文本区分能力也就越大。这体现了信息论中集中度的思想，具有一定的合理性。IDF的公式如下: 其中，N表示训练集中的文档总数，表示包含特征词的文档数，是一个经验值，一般取0.01、0.1、1。IDF能弱化一些在大多数文档中都出现的高频特征项的重要度，同时增强一些在小部分文档中出现的低频特征项的重要度。 3.2.3 TFIDF权重 TFIDF(Term Frequency-Inverse Document Frequency)是由salton和Buckley于1988年提出并用于信息检索领域，后来被应用于文本分类和聚类等数据挖掘中的特征加权。TFIDF权重综合考虑了TF权重和IFD权重的优点和不足，是目前加权效果最好的权重计算方法，广泛应用于文本处理领域。因为TFIDF满足有效的特征项集合必须具有以下两个特点:一是特征词在文档中出现次数越多，越重要;二是文本 20 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 集中含有特征词的文档数大越大越不重要。 TFIDF权重，利用了词频和文本频率两种信息，公式如下: N log()Wtf,，ikiknl，k 其中，N，，的含义和上面的相同。根据香农理论，如果特征项在所有tfnlikk 文本中出现的频率越高，那么它所包含的信息熵就越小;如果项的出现较为集中，即只在少数文本中有较高的频率，那么它就有较高的信息熵。 TFIDF特征权重估算公式认为区分文本类别能力高的特征词应该是在某个 文本中出现频率足够高，并在训练集中其他文本内出现频率足够低的特征，并 给予这样的特征高权重值。为了消除文本长度对特征权重的影响，通常要对特征的权重进行归一化处理。 3.2.4改进权重 TFIDF针对信息检索提出的，而对于文本分类和聚类来说并不那么有效。对于文本分类和聚类来说，文档频率高的特征词比文档频率低的单词更为重要，这点与信息检索中的IDF观点正好相反。此外，TFIDF仅表达了一个特征词对一个文本的区分能力，并没有包含这个特征词区分类别的能力。而对于文本分类或聚类来说，更为重要的是一个特征词对类的区分能力，因此，近来越来越多的人对TFIDF用于文本分类和聚类提出了质疑，并进行了许多改进，使得它能适用于该领域。 比较有代表性的有:国内的陆玉昌教授等用传统的特征函数，像互信息、信息增益、期望交叉熵等取代TFIDF公式中的IDF部分，提高了分类性能。国外的S.Shankar等，他们采用基尼的纯度公式对IDF进行加权，并成功的应用于质心法分类。根据以上的分析，用于文本分类的TFIDF加权算法的主要缺点在于公式中的IDF部分，因此为了改进这一缺点，设计了另外一种改进特征权重方法。 根据TFIDF并没有包含这个特征词区分类别的能力，针对这一特点进行改进。要对特征项权重在类内计算，对于每个类的特征项有不同的权重。权重计算一要包含TF部分，二要有类别的区分能力。类别的区分能力表现在两个方面:一是在类 21 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 内出现的文档频率较高，二是在类外的文档频率很低。依据上面的论述，权重可以这样计算，权重公式如下: WtfPwPw,，，,()(1())ikikcc 其中，是特征项在C类中的概率，是特征项在C类外的概率。 Pw()Pw()cc 3.3文本表示模型 3.3.1向量空间模型 向量空间模型(Vector Space Modal，或称词组向量模型)，是由Salton教授等人在20世纪60年代提出的，一直以来都是信息检索领域最为经典的计算模型。它使用向量表示文本，最早用于信息检索领域，成功应用于著名的SMART系统中，后来这项技术又在文本分类领域得到了广泛的应用。该模型现已经成为最简便、最高效的文本表示模型之一。 向量空间模型的最基本思想就是用“词袋"来表示文本。也就是将每一个不同的词都看成特征空间中独立的一维，将每一个文本看成是特征空问中的一个向量。向量空间模型有M个无序特征项W，词根/词/短语/其他每个文档Di都可以用特征项i 向量来表示(W，W，(((，W)。 li2jMj 图3(1向量空间模型 文本分类时，对若干已有类标签的训练集进行必要的数据处理，如分词， 降维，特征加权，并通过学习形成一个文本分类函数，形成类别的中心向量。 22 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 当有文本需要分类时，对它做必要的处理后，用向量空问模型表示出该文本， 然后通过计算它和类别中心向量的相似度，来判断该文本的类别信息。 相似度的计算形式有几种方案，如通过内积计算、余弦计算(Cosine计算) 等形式求相似度。其中，直接用内积计算相似度的形式，计算强度低，但是误 差较大。内积计算公式如下式所示: 而余弦形式的好处是，正好是一个介于0到l的数，如果向量一致就是1，如果正交就是0，符合相似度百分比的特性，余弦的计算方法为，向量内积/各个向量的模的乘积。余弦计算公式如下式所示: 综上所述，一个文本要表示成向量形式，必须经过分词，特征提取，权重 计算等步骤。 3.3.2扩展的向量模型 潜在语义索引(LSI)最早是一种用于信息检索中的自动索引技术，是一种将 文本信息组织成语义空间结构的方法，它认为在文本中的词与词之间存在着某 种联系，即潜在的语义结构，并通过分析词与它所处上下文环境之间的关联关 系抽取出隐藏在文本背后的这种更为高层的语义结构，从而能在语义层面上对 文本进行检索，进而大幅度提高信息检索的性能。 LSI是在向量空间的基础上进行词条关系处理的，并基于这样一种断言，即 大量的文档集合中存在隐含的关于词语使用的语义结构，这种语义由于部分的 被文档中词的语义和形式上的多样性所掩盖而不明显。因此，LSI试图绕过自然 语言理解，运用统计运算的方法来发现词语使用的潜在的语义结构，获得文档 潜在的语义概念空间结构，从而利用概念索引取代关键词索引。 在LSI模型中，一个文档库可以表示为一个的词-文档大矩阵A。这里，n表示文档库中的文档数，m表示文档库中包含的所有不同的词的个数。也就 23 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 是说，每一个不同的词对应于矩阵A的一行，每一个文档对应于矩阵A的一列。 A表示为: 潜在语义索引模型利用特征项与文档对象之间的内在关系形成信息的语义 结构。这种语义结构通常是通过对特征项文档矩阵使用奇异值分解 (Singular-Value Decomposition，SVD)方法来实现的，把小的奇异值去掉，从而 形成新的语义空间。 3.3.3基于类特征表示 总之，每个类的特征词大都不是正交的，但基本上都是很有类区分能力的，在该类中出现次数较多，在其它类中出现较少。如果类内的特征词都是正交的，我们可以把待分类文档用每个类内特征词表示。即待分类文档可以对应每个类特征词表示成不同的形式。如下图所示: 图3(2基于类特征表示图 即把待分类文档用每个类的特征词表示成不同的形式，这样很大程度的降低了向量的维数。后面的实验将证明这不会影响分类准确性，有时还可能提高分类性能。因为这种表示只保留了类内的特征词，去掉了和本类无关的词，而没有必要把应用训练样本和待分类样本都映射到高维空间中，极大程度地降低了向量的维数。假设有A、B、C、D四个类，如一个属于股票类的待分类样本，其讲述了关于房地产的股票信息，100个特征词中可能会包含一个或几个其它的特征词，我们用股票类的特征词表示该文本时几乎不遗漏文本信息，而把它很好的表示出来 24 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 3.4小结 本章论述了文本分类的关键技术。首先介绍了文本分类中特征词的采用的粒度级别，即关键短语的概念，并分析了关键短语获取的算法和技术。然后本章着重介绍了权重算法TFIDF权重，并在此基础上对权重算法进行了改进，使得本文采用的权重算法更有利于文本分类，算法在实验中得到了验证。最后本章介绍了文本的数学表示模型，包括向量空间模型、扩展的向量模型和基于类特征表示的方法，这样的文本表示模型便利了文本分类。 第四章 基于文档网络的KNN分类器样本裁剪方法 为了提高分类速度，Makoto等提出先将样本用层次贝叶斯聚类法(Hierarehieal Bayesian clustering，HBC)进行聚类，然后用聚类中心代替训练集对新文本进行kNN分类。Lam提出了一种使用广义样本进行KNN分类的方法。国内的李荣陆、胡运发等采用基于密度的训练样本裁剪方法加快了kNN分类器的分类速度，提高了分类的准确率。李蓉、叶世伟、史忠植等将kNN和SVM相结合，提高了分类器的分类性能，并很好地解决了核函数参数的选择。给合上面两种方法的特点，本文对算法进行改进，提出了基于文档网络的样本裁剪算法。 4.1层次聚类算法 层次聚类的方法最早是Willet 提出的HACM(Hierarchical Agglomerative Clustering Method)，后来在此基础上提出的应用最广泛的聚类方法有SLM(Single Link Method)、CLM(Complete Link Method)、GALM(Group Average Link Method)、WM(Ward’s Method)。在不同的方法中，人们研究了获得较高的计算效率的问题。 4.1.1层次聚类算法的抽象描述 层次聚类又被称作系统聚类，通过将已有的类别两两比较，找出最相近的类别合并，最终所有的数据都被聚到单一的类别中。由于有较大的搜索空间，层次聚类 25 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 比平面划分法容易获得较高的精度，其代价是算法的速度下降了许多。层次聚类得到的结果是一颗聚类树，可以通过比较每一步聚类的结果选择最合理的聚类个数。聚类分为分割方式和凝聚方式两种。 超图聚类(hyper graph cluster)是一种针对高维空间的数据挖掘算法。在超图中一条边可以连接多于两个顶点。超图聚类是一种自顶向下进行分割的层次聚类过程，通过将权重最低的边删除，将一个连通图一分为二。划分过程将在类别的数量达到一个指定的值时停止。超图算法可以处理非完全图，不要求知道任意两点见的相似度(数据缺失)，因而具有较大的灵活性。 大部分的层次聚类算法都采用的是凝聚方式。这种方式只需给出局部的优化目标函数，然后再进行遍历搜索即可，因而简单易行。层次凝聚算法的基本思路如下: D,{d,d,？,d,？,d}12in1. 在初始化阶段，对于给定的文档集合 ，将D中的 c,{d}ii每个文档作为一个独立的类别，即 。 ,,argmaxsim(c,c)jksim(c,c)jk,jk2. 根据某种相似性度量()，将最相似()的两 ˆˆc,cjkc个类别合并为一个类别。 3. 重复2)直到只有一个类别，或达到某种可接受的标准时算法停止。 1 2 3 4 5 6 7 文8 档 9 10 11 12 13 14 0 13 步骤 图 4.1 凝聚方式的层次聚类过程 一般地说，由于层次算法是局部优化，采用分割方式的问题在于如果一开始将本属于同一个类别的对象划分的不同类别中，算法无法修正这种错误，从而使得错 26 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 误被积累起来，影响了聚类的效果;类似，凝聚方式下，算法可能在初期就将不同类别的对象合并到一个类中，并将这种错误延续到最后。 由于启发式算法需要考虑收敛性的问题，且受数据的(特性，输入顺序，误差等)影响较大，而层次凝聚算法没有这些弊端，算法复杂度易于控制。基于这些考虑本文中的算法将以层次凝聚算法为基础进行讨论。 4.1.2层次贝叶斯聚类算法 层次贝叶斯聚类算法(HBC, Hierarchical Bayesian clustering)是一个典型的凝聚式的层次聚类算法，它使用后验概率作为最大化的目标函数，取得了良好的聚类效果。算法思路清晰简明，在此进行简单的介绍，作为本文后续讨论的一个基础。。 HBC算法在每一步中都选择两个类别合并为一个类别。选择的依据是使合并后 P(C|D)P(C|D)分类方案的后验概率最大，即每一步进行局部优化的目标函数为。 D,{d,d,？,d,？,d}12inCDD其中是文档的集合，分类方案表示类别的集合，是对 c,D,c,c,,,,i,jC,{c,c,？,c,？,c}iij12im的一个划分:，。 c,{d},1,i,nii在聚类的初始阶段，每个文档被看作一个独立的类别，即，此 CC0k时的分类方案为。假设现在已经完成第k步，其分类方案是，我们需要为k+1 c,cCxyk，1步选择最优的聚类方案的关键是选择合适的两个类别进行合并。 P(C|D),P(c|d),,kcc,,Cd P(d|c)P(c),,,P(d)cc,,Cd ||cP(c),c,C,P(d|c),,c||P(D)cc,,CdPC(C),P(c),c,CPC(C),SC(c)SC(c),P(d|c),,P(D)c,Cd,c 其中 C,C,{c,c}，{c,c}CCk，1kxyxykk，1和之间显然有，于是: SC(c,c)P(C|D)PC(C)xyk，1k，1,P(C|D)PC(C)SC(c)SC(c)kkxy 27 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University P(C|D)P(C|D)kk，1由于对k+1步而言，是已知常数，我们无须直接计算，就 PC(C),1k，1,A,A,1c,cPC(C)xyk可以找到最佳的。上式中第一项采用近似估计值是一个 P(T,t|d)P(T,t|c)P(d|c),P(d),P(T,t)t常数。应用贝叶斯理论可以得到条件概率， tT,t其中表示从样本集中取出一个特征词恰好为的事件。 P(C|D)P(C|D)kk，1，1ˆˆ(c,c)argmax,xycc(,)xyP(C|D)P(C|D)kk至此我们已经得到的表达式，显然即是 ˆˆc,cP(C|D)xyk，1使得最大化的两个类别。所以第k+1步应将合并为一个类别。 综合上的讨论，我们可以给出形式化的算法如下: Input: :包含n个文档的输入数据 D,{d,d,？,d,？,d}12in Initialize: ， C,{c,c,？,c,？,c}c,{d},1,i,n12imii 为所有的计算 c,1,i,nSC(c)ii 为所有的计算 c,c,1,i,j,nSC(c,c)ijij for k=1 to n-1 do SC(cc),xyˆˆ (c,c)argmax ,xy(c,c)xySC(c)SC(c)xy ˆˆˆˆ C,C,{c,c}，{c,c}kk,1xyxy 为中所有的计算 Cc,c,1,i,j,nSC(c,c)ijijk Function SC(c) P(d|c)Return ,d,c 算法 4.1 HBC算法 HBC算法经过测试，并与Single-link Mehtod、Ward’s Method作了对比，在聚 类的准确度方面取得了非常显著的改善。对包含1072篇文章(日文)的数据集进行 聚类的结果显示Single-link 的准确率最多达到62%，Ward’s 可以接近70%，而HBC 则获得了74%的较高准确率。 28 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 4.2贝叶斯后验模型的层次聚类 4.2.1贝叶斯模型选择 在最近几年的研究文献中，一类基于概率模型的聚类分析技术逐渐被研究者所关注。研究人员通过分析数据与各种概率模型之间的匹配问题，提出了一系列新的聚类算法。同时这方面的研究也表明，许多传统的聚类算法都可以解释为某种概率模型的近似。常用的KNN算法和Ward’s方法也可以用特定情形下的多元正态模型加以解释。实际上本文丄一节中介绍的HBC算法就是一种基于概率模型的聚类算法。 4.2.2文本聚类的贝叶斯后验模型 ,聚类算法中的模型选择的核心是对不同的分类方案的后验概率进行比较，找出有最大后验概率的分类方案。与通常的化简方法不同，我们没有将最大化后验概argmaxP(,|D)argmaxP(D|,),,,率近似为最大化似然函数，而是通过给出的一个 P(,|D)具体的形式，来直接得到后验概率的形式。 d, 为了表示分类方案，我们考虑每一篇文章都有一个对应的概率矢量 K(d)(d)(d)(d)(d),,,(,,,？,,),,,1,12Kk(d),,KDk1，，是预期的类别数。这样与数据对应 (d),,|D|dkK着一个行列的矩阵，他的每一个元素表示文章在多大程度上属于类c,k,别，从而可以表示任意的分类方案。可以将的后验概率表示为: ,P(,|D),P(|D) ,,P()P(D|),,,P()P(D|),, ,P(,)P(D|,) 我们假设每篇文章的产生过程是相互独立的，相应的每篇文章的类别矢量也是 P(,|D)相互独立的，则可以表示为: 29 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University dd()()P(,|D),P(,)P(d|,),d,D K()()ddP(d|,),,P(d|c),kk,1k通常情况下由全概率公式可以给出，这正是文档的混合模型，上式在数学上很难处理。幸运的是由于我们采用非模糊聚类，聚类算法 ,,所考虑的每一个潜在划分方案都是将每个文档划入特定的类别中的，也就是说 1if ,dc,k(d),,,k(d),0else,,,中类别矢量只能有一个分量为1，其他的分量都为零:。 (d),在这种情况下的取值只有下面几种可能: ,,(1,0,？,0,0),1 ,,(0,1,,0,0),？2 ,,？？？？？？？ ,,(0,0,,1,0),？,1K ,,(0,0,,0,1)？K,,,,,K (d)(d)c(d),,,P(d|,),P(d|c(d))对于满足的类别矢量显然有，这里表示类别 (d),,,矢量中唯一不为0的分量。这样我们就可以给出每一个潜在的划分方案的后验概率为: ,d()P(,|D),P(,)P(d|c(d)),d,D K(d)(d)P(,|D),P(,),P(d|c),kk,,P(,|D)1k,d,D与相比，就非常容易计算了。变换一下形式可以得到: K,，，P(,|D),P(,)P(d|c),,kk,,1kcdk 后面将看到，与通常的似然模型相比，采用这一后验模型大大降低了参数学习的复杂度，可以直接求解精确的最大后验估计，避免了似然模型采用EM算法估计最大似然概率引起的复杂性和计算量。进而在这一点上，避免了EM算法陷入局部极大值引起的误差。 30 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 4.3文档网络(小世界网络模型) 基于Milgram的人类社会关系网络研究成果，Watts和Strogatz提出小世界网络模型，该模型可用于分析复杂网络的结构、特性及行为，它属于复杂网络理论范畴。他们给出小世界网络模型的拓扑结构是介于同规模的规则网络与同规模的随机网络之间，其小世界特性可从模型构造过程中表现出来，如图4-1所示。构造过程是从一个含有N个节点的志最邻近耦合网络(规则网络)开始，以概率p随机地重新连接网络中的每一条边，要求任两个节点间至多只能有一条边，且每一个节点都不能有边与自身相连。P=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p值就可以控制完全规则网络到完全随机网络的过渡。在网络拓扑结构过渡中，用于描述网络结构统计特性的变量，如图的平均最短路径长度、聚类系数及节点的度分布等，若满足平均最短距离小、聚类系数值大及节点的度分布近似符合Possion分布的条件，则此时的网络结构呈现小世界特性，即小世界网络模型。 图4-1 WS小世界模型生成图 设G为一个图，是图G中节点的集合，N是图G中节点个数，i(i?)是图G中任一节点，表示节点i和节点j之间的最短路径长度，是图G的子图，它表示与节点i相邻的那些节点(有边直接相连的节点)之间的连接所形成网络。为子图的节点个数，图G的平均最短路径L和聚类系数C的定义如下: 1. 平均路径长度 31 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University dij 假设网络中有n个节点，两个节点i和j之间的最短距离定义为连接这两个节点的最短路径上的边数，即最短路径长度。网络的平均路径长度L定义为网络中任意两个节点之间的距离的平均值，即 nn,12Ld,,,ijnn,(1)iji,,，11 2. 聚类系数 ki 假设网络中有n个节点，一个节点i有条边将i节点它和其他节点相连，kkii这个节点就称为节点i的邻居，并且把这应个节点所组成的图称为i的邻接点子 kkk(1)/2,kiiii图。显然，在这个节点之间最多可能有条边。如果这个节点之间实 ECii际存在的边数，则节点i的聚类系数定义为二者比值。网络的聚类系数C定义为网络中所有节点聚类系数的平均值，即 nn2E11i,,CC,,i,nnkk(1),,11iiii 与同规模的规则网络图和随机网络图的统计特性相比，小世界网络的统计特性的特点是它的平均最短路径值长度与随机网络的长度接近，它的聚类系数与规则网络的接近。 4.4基于文档网络的样本裁剪算法 使用KNN对文本进行分类时，当训练样本较大时，会导致很高的计算开销，而且，训练文档分布的不均匀性也会造成分类准确率的下降。 目前主要通过两种途径来减小KNN方法的计算量:一种途径是通过快速搜索算法，在尽量短的时间内找到测试样本的最近邻;另一种途径是在原来的训练样本集中选取一些代表样本作为新的训练样本，或删除原来的训练样本集中的某些样本，并将剩下的样本作为新的训练样本，从而达到减小训练样本集的目的。本文主要讨论后一种途径。对于这种途径最主要的方法是Hartde的Condensing算法、Wilson 的Editing算法和Deijver的MultiEdit算法，Kuncheva使用遗传算法在这方面也进行了一些研究，但是这些方法在训练样本集中每增加或删除一个样本时，都要对样本进 32 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 行一次测试，反复迭代直到样本集不再变化，这对于有成百上千的训练文档来说，其工作量是非常巨大的。并且，这些方法都没有考虑训练样本分布的不均匀性对分类准确率的影响。 设n维向量为一个文档，为包含个文档的、具有类标识的文档集。具有m个类，，„，的文本分类问题，其KNN分类决策过程如下:对于一个给定的测试文档X，分别计算它与训练样本集中 每一个文档的距离(或相似度)，找到与之最近的个训练文档，其中属于类的文档数有个，则我们定义判别函数为 , 那么分类的决策规则为 若，则决策。 kNN方法实际上是一种基于类比的学习方法，这就要求训练样本中样本必须具有代表性，这种代表性不仅应该体现在样本间的语义距离(或相似度)上，还应该体现在样本分布是否均匀上。 本文的改进算法主要针对样本间的语义距离上，算法运用文档网络(即最小世界网络)，对距离中心向量远的样本进行裁剪，从而减小了训练样本集。 4.5小结 本章首先介绍了层次贝叶斯聚类和文档网络即小世界网络模型，然后在前人的研究成果上进行改进，提出了一种基于文档网络的样本剪裁方法。基于文档网络的KNN分类器样本裁剪算法首先将样本用层次贝叶斯聚类法进行聚类，然后使用提出的方法对样本进行裁剪，进一步提高样本训练和分类速度。实验结果显示，这种方法不仅减少了训练样本的数量，使kNN方法的计算量降低，而且减少了训练样本分布不均匀性对分类性能的影响，提高了分类的准确率和召回率。 33 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 第五章 实验及结果分析 5.1服装描述文本分类系统 结合项目实践和本文实验的需要，同时也为今后的研究工作搭建可以使用的实验平台，本文设计了一个服装描述文本分类系统，该分类系统由关键短语抽取模块、特征选择模块、文本分类模块组成。通过第三章中对关键短语的阐述，系统设计了关键短语抽取模块。系统使用本文改进的权重算法，结合特征选择算法设计了特征选择算法。系统根据第四章的分类算法，设计了文本分类模块。系统对本文提出的算法进行了验证，并和以前的算法进行了对比分析，从而验证了本文算法的有效性和可行性。 5.1.1系统框架 在综合考虑项目需求和研究需求的基础上，本文对服装描述文本分类系统进行了模块化设计，即服装描述文本分类系统由关键短语抽取模块、特征选择模块、文本分类模块三个模块组成，三个模块之间通过简单有效的接口相连，相互之间独立透明，对其中任何一模块的修改都不会对其他模块产生影响，可以通过修改其中的任一模块，从而进行对该模块的单独研究，提高了本文系统的可研究性。 34 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 图5-1 系统框架图 本文系统的处理流程如下:服装描述文本集中的文本经过关键短语抽取模块处理后，表示为一个个关键短语组成的集合;通过特征选择模块选出最能代表某一类特征的特征词;经过本文的改进权重算法计算后把文本表示为分类器可以识别的文本表示模型;最后文本表示模型经过系统分类模块的处理得到分类结果。通过对分类结果的分析比较，可以验证本文提出的算法的有效性和可行性。该服装描述文本分类系统的三个模块的将在下面几小节详细介绍。 5.1.2关键短语抽取模块 本文关键短语抽取模块是在ICTCLAS分词组件的基础上实现的。 ICTCLAS(Institute of Computing Technolog，Chinese Lexical Analysis System)是中国科学院计算技术研究所在多年研究工作的基础上研制出的汉语词法分析系统，其主要功能包括中文分词、词性标注、命名实体识别、新词识别等，除此之外该汉语词法分析系统还支持用户词典，支持GBK、UTF-8、UNICODE等多种编码格式。 ICTCLAS几乎把汉语词法分析的所有环节都统一到了一个完整的理论框架中，它能够获得很好的整体效果。而且ICTCLAS实现了分词效率和分词精度的平衡，目前ICTCLAS的版本是ICTCLAS2011。ICTCLAS 2011的内核版本5.0，改版后分词速度更快;稳定性更高。ICTCLAS 2011c/c++/c#版、JNI版均支持多线程调用。以往版本需要进行编码转换，统一转换成GB2312之后才能做进一步处理。系统当前版本支持GB2312、GBK、UTF-8、BIG5等编码。以上编码无需做任何转换，即可进行后续处理。用户可指定需要处理数据的具体编码(有利于提高速度)也可让系统自动识别编码。本版新增了对繁体中文即BIG5的识别处理。 本版对Windows7支持良好。支持大用户词典，可以说ICTCLAS是当前世界上最好的汉语词法分析器之一。 本文的关键短语抽取模块是基于ICTCLAS的java版本构造的。ICTCLAS分词组件通过对大量语料库的训练，统计出汉语词汇的词频和跳转频率，然后利用这些统计结果对汉语句子进行切分，从而得到一个个关键短语。ICTCLAS分词模块内部 35 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 带有默认的停用词表，可以在分词时对停用词进行过滤，提高分词的效率和准确度，从而提高分类的准确性。 5.1.3特征选择模块 本文服装描述文本分类系统的特征选择模块是借助Lucene实现的。 Lucene是一个全文检索引擎的框架，其开发语言为java。Lucene的目的是为开发人员提供一个全文检索引擎工具包，以方便他们在此基础上建立完整的全文检索引擎，或实现全文检索功能。 全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，索引中包含该词在文章中出现的次数和位置信息，当用户查询时，检索程序根据事先建立的索引进行查找，并将查找的结果反馈给用户(全文检索的常用方法主要有按字检索法和按词检索法。按字检索是指以字为单位建立索引，检索时将词分为字的组合，然后对索引进行查询。按词检索是指以词为单位建立索引，检索时也以词为单位对索引进行查询。 本文的特征选择模块在ICTCLAS分词模块对文本进行分词的基础上，利用Lucene的全文检索功能为各个类别，以及总的文档集合建立词与文档的索引，然后从总的文档集的词与文档的索引中读取索引词作为训练词库，读取索引词在各个类别中的文档频、词频、位置等信息，利用本文所提出的改进权重算法计算特征词的权重，然后计算出索引词的综合度量指标，选择特定数目的索引词作为特征词集合，然后把文本表示为分类器可以识别的文本表示模型。 5.1.4分类模块 本文服装描述文本分类系统的分类模块是在Weka基础上实现的。 Weka是一款免费的，非商业化的机器学习、数据挖掘开源软件。1993年The University of Waikato开始了对Weka的开发，最初开发语言使用的是C，1997年Weka开发小组使用Java语言对Weka进行了重新编写，同时对Weka数据挖掘的相关算法进行了大量改进。2005年8月，Weka开发小组在第ll届ACMSIGKDD国 36 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 际会议上荣获了数据挖掘和知识探索领域的最高服务奖，至此，Weka系统开始得到广泛认可。现今为止，Weka仍被认为是最完备的数据挖掘工具之一。 Weka作为一个公开的数据挖掘平台，集成了包括数据预处理、分类、聚类、关联规则挖掘等大量能够承担数据挖掘任务的机器学习算法。实际应用中，开发人员根据实际需要还可以在Weka平台的基础上开发出更多的数据挖掘算法，以满足实际需要。 本文的分类模块首先借助Weka使用层次贝叶斯聚类对训练文本进行聚类，然后使用本文提出的基于文档网络的样本裁剪方法对样本进行裁剪，最后借助Weka使用KNN对文本进行分类。根据分类结果， 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 本文所提出的算法的有效性和可行性。 5.2实验设置及实验数据 5.2.1实验设置 通过上面的介绍可知，本文的服装描述文本分类系统的三个主要功能模块都使用了Java开源工具包进行开发，这样提高了系统开发的效率。实验系统为Windows Xp。开发语言为Java语言，开发环境为Eclipse。机器配置为:CPU为Pentium(R) Dual-Core CPU T4300 @2.10GHz，内存为2.00GB。 5.2.2实验数据 根据测试语料库是否为训练语料库的一部分这一标准，测试分为封闭性测试和开放性测试。封闭性测试即测试语料库为训练语料库的一部分或整体;开放性测试即测试语料库不属于训练语料库。本文进行了封闭性测试和开放性测试。 本文实验数据来源为实验室项目中使用的服装描述中文文本，该语料库共分为:女装、男装、内衣、男鞋、女鞋、运动鞋、童装7类别，共4548篇文档。3101篇用于训练文本，剩下的1447篇文档做为测试文本。 37 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 图5-2 服装描述训练文本 该中文文本分类语料库的文本全部为txt文件，每个txt文件的名称全部为数值，同时以不同的数值开头作为类别的区分标识，其中女装类用数值0开头表示、男装类以数值1开头表示、内衣类以数值2开头表示、男鞋类以数值3开头表示、女鞋类以数值4开头表示、运动鞋类以数值5开头表示、童装类以数值6开头表示。以女装类为例，因为女装类的类别区分标识为0，所以所有女装类中的文本都是以数值0开头的，如下图5-2所示。 图中只罗列了类别中的部分文档。 图5-2 女装类的训练文本 5.3实验结果分析 系统使用了本文提到的基于文档网络的样本裁剪算法。训练文本分为女装、男装、内衣、男鞋、女鞋、运动鞋、童装7类别，共3101篇文档。裁剪情况如图5-3所示。 38 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 图5-3 训练样本裁剪情况表 下面是系统的算法在未裁剪和裁剪后的实验测试对比图。 图5-4 封闭测试准确率对比图 图5-5 封闭测试召回率对比图 39 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 图5-6 开放测试准确率对比图 图5-7 开放测试召回率对比图 从图5-4到图5-7，我们可以看到，不管各类别的训练文档数目是否分布均与，也不管是在封闭测试还是开放测试中，使用本文提出的算法训练文本进行裁剪，然后对裁剪后的训练样本进行分类，取得了更高的分类准确率和召回率。 综上所述，基于文档网络的KNN分类器文本裁剪算法不仅降低了文本分类的时间复杂度，还能提高分类的准确度和召回率，从而验证了本文提出算法的可行性和有效性。 40 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 5.4小结 本章详细阐述了本文服装描述文本分类系统的系统框架、各个模块的设计、实验设置以及实验数据。通过对分类系统相同的实验数据集上的未裁剪情况下和裁剪后情况下的对比分析，得知在封闭测试和开放测试中，裁剪后的训练样本用于分类的效果都优于未裁剪的训练样本，从而验证了本文提出的基于文档网络的样本裁剪算法的可行性和有效性。 41 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 第六章 结论与展望 6.1结论 本文在研究文本分类的基础上，总结前人的研究成果，对样本裁剪算法进行了重点研究，在此过程中做了如下工作: (1)对文本分类的理论基础和相关算法，包括分词、特征选择、特征加权和文本分类算法等做了比较全面的介绍。详细分析了文本分类的几种关键技术，得出目前常用权重算法应用于文本分类的不足之处，并在TFIDF的基础上，结合文本分类的需要，改进TFIDF形成了一种新的权重算法; (2)为提高文本分类的速度，本文在总结前人成果的基础上，提出一种新的文本分类算法。算法首先用贝叶斯聚类法聚类，分成几块，减少计算量。然后求文档网络(即最小世界网络)，将距离中心向量远的样本进行裁剪，不仅减小了训练样本的规模，而且实验证明提高了分类效果。 (3)综合运用ICTCLAS、Lucene、Weka等开源工具设计实现了一个服装描述文本分类系统。系统集关键短语抽取、特征选择、文本分类三个模块于一体，各个模块之间通过简单有效的接口相连。系统不仅可以为文中提到的权重算法和文本分类方法进行实验验证，还可以为以后的文本分类研究提过实验平台。 (4)在相同的实验数据集上对未裁剪情况下的文本分类和裁剪后情况下的文本分类进行了大量的对比实验，并对实验结果进行了分析。通过验证实验得知，无论是封闭测试还是开放测试，经过本文提出的裁剪算法裁剪后的训练文本用于文本分类，准确率和召回率都有所提高，从而验证了本文提出算法的可行性和有效性。 6.2展望 文本分类涉及到的技术比较多，包括分词技术、特征选择技术、分类算法的选择等等，其中任何一种技术都可以作为研究的重点。本文主要对文本分类中的权重算法进行了总结分析，改进了权重算法使得更适于文本分类。本文还总结前人的研究成果，提出了基于文档网络的KNN分类器样本裁剪算法，而其中还存在许多值得进一步探讨和研究的地方。本文的下一步工作主要有以下几个方面: 42 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University (1)本文的关键短语抽取模块使用的是开源分词组件ICTCLAS的java版本，本文只是对分词的词典进行了补充，下一步的工作可以考虑对ICTCLAS的java开源版本进行进一步的研究和改进，提高分词的速度和正确性，以提高本文中系统的分类效率。 (2)本文采用基于文档网络的样本裁剪算法，虽然经过裁剪后的训练文本用于文本分类的效果优于未裁剪情况下的文本分类效果，但是从实验数据可知，分类的效果还有待完善，在以后的工作中，可以对本文提出的裁剪算法进行改善。 (3)本文的算法采用层次贝叶斯聚类算法，分类采用了KNN算法，下一步工作中，本文将对聚类和分类算法进行改进，以进一步提高分类效果。 43 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 参考文献 [1]Ralph Grishman. Information extraction: Techniques and Challenges. InMaria Teresa Pazienza,editor, Information Extraction. Sp ringer -Verlag, Lecture Nots in Artificial Intelligence, Room, 1997 [2] Proceedings of the Third Message Understanding Conference (MUC -3) . Morgan Kaufmann,May, 1991 [3] Proceedings of the FourthMessage Understanding Conference (MUC -4) . Morgan Kaufmann, 1992 [4] Proceedings of the Fifth Message Understanding Conference (MUC -5) . Baltimore,MD, August, 1993. Morgan Kaufmann [5] Rohini K. Srihari;Wei Li; Cheng Niu ; Thomas Cornell. InfoXtract:A Customizable Intermediate Level Information Extraction Engine. In Proceedings of HLT/NAACL 2003Workshop on Software Engineering and Architecture of Language Technology Systems ( SEALTS) . 2003:52 – 59 [6] Srihari, R. andW. Li. A Question Answering System Supported by Information Extraction. In Proceedings ofANLP 2000. Seattle. 2000 [7] 李保利，陈玉忠，俞士汶.信息抽取研究综述.计算机工程与应用，2003,NO.10 [8]甘立国(中文文本分类系统盼研究与实现[D](北京:北京化工大学，2006( [9]王涛(文本自动分类研究[J](图书馆学研究，2007，12(3):40-44( [10]荣光(中文文本分类方法研究[D](山东:山东师范大学，2009( [11] V.Vapnik(Nature of Statistical Learning Thcory[M](New York:Springer Press,2000( [12]史伟(中文自动分词关键技术研究与实现[D](四川:电子科技大学，2008( [13]Kai Ying Liu，Jia Heng(Research of automatic Chinese word segmentation[C](Proceedings of 2002 International Conference on Machine Learning and Cybemetics，2002:805-809( [14]van Leeuwen J(Approaches in machine leaming[M](ALGORITHMS IN AMBIENT INTELLIGENCE(2004:1 5 l-1 66 [15]Sebastiani F(Machine learning in automated text categorization[J](ACM Computing Surveys， 2002，34(1):l-47( [16]苏金树，张博锋，徐听(基于机器学习的文本分类技术研究进展[J](软件学报，2006， 17(9):1848—1859 [17]Wang BY Zhang SM(A novel text classification algorithm based on Naive Bayesand 44 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University KL-divergence[C](International Conference on Parallel and Distributed Computing，2005: 913(915 [18]Yang Lihua，Dai Qi，Guo Yanjun(Study on KNN Text Categorization Algorithm[J](Control& Automation(2006:269-270 [19]李荣陆，干建会，陈晓云，陶晓鹏，胡运发(使用最人熵模型进行中文文本分类[J](计算机研究与发展(2005，42(1):94-101 [20]王建会，王洪伟，申展，胡运发(一种实用高效的文本分类算法[J](计算机研究与发展( 2005，42(1):89-97 [21]尚文倩，黄厚宽，刘玉玲，林永民，瞿有利，董红斌(文本分类中基于基尼指数的特征选择算法研究[J](计算机研究与发展(2006，43(10):1688-1694 [22]B(V-Dasarhaty(Nearest Neighbor(NN)Nomrs:NN Paaem Classifieatiion Techniques[M]( Los Almaiots，Caliofmia:IEEE Computer Society Perss，1991( [23]Jiawei Han，Micheline Kamber(Data Mining:Concepts and Techniques，Second Edition[M]( San Fransisco:Morgan Kaufmann Publishers，March 2006 [24]V(N(Vapnik(The Nature of Statistical Leaming Theory[M](New York:Springer-Verlag(1 995 [25]Thorsten Joachims(Text Categorization with Support Vector Machines:Learning with Many Relevant Features[C](Proceedings of ECML-98，10th European Conference on Machine Learning(1 997 [26]Remco R(Bouckaert(Bayesian Network Classifiers in Weka(2004 [27]Remco R(Bouckaert:Naive Bayes Classifiers That Perform Well with Continuous Variables[C](Australian Conference on Artificial Intelligence 2004:1089-1094 [28]陈涛，宋妍，谢阳群(基于IIG和LSI组合特征提取方法的文本聚类研究[J](情报学 报，2005，24(4):203-209 [29]Keyun Hu,Lili Diao，Chunyi Shi(A Heuristic Optimal Reduct Algorithm，22nd intl(Sym[C]( In:intelligent data engineering and automated learning(IDEAL2000)，Hong Kong，2000-ll [30]Lei Y Huan L(Efficiently Handling Feature Redundancy in High—Dimensional[C](In:Data SIGKDD’03，2003:685(690 [31]I Guyon，A Elisseeff(An introduction to variable and feature selection[J](Journal of Machine Learning Research(2003(3):1157-l182 [32]L Yu，H Liu(FCBF-Feature Selection for High-Dimensional Data[C](In Proceedings of the twentieth International Conference on Machine Learning，Washington DC，USA(2003:856- 45 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 863 [33]王峻(朴素贝叶斯分类模型的研究与应用[D](合肥:合肥工业大学计算机应用技术，2006 [34]叶振宇(基于关联规则和向量空间模型的文本分类研究[D](南京:东南大学软件工程， 2005 [35]Van R0sbergen C(J(1nformmion Retrieval(2”edition)[M](London:Butterworths，1979 [36]Soucy E Mineau G W(Beyond TFIDF weighting for text categorization in the vector space model[C](Proceedings of International Joint Conference on Artificial Intelligence(Edinburgh， Scotland，UK，2005:l130一l135 [37]Cancho，R(F(I(and R(V(Sole，The small world of human language[C]//Proceedings of The Royal Society of London，London，2001(Series B，Biological Sciences(268(2001): 2261-2265( [38] Li，M(，W(-C(Lee，and A(Sivasubramaniam(Semantic Small World:An Overlay Network for Peer-to—Peer Search[C]//Proceedings of the 12th IEEE International Conference on Network Protocols(ICNP2004)(Berlin，Germany(2004:180-189( [39]Blansche A，Gancarski P'Korczak J J(MACLAW:A modular approach for clustering withlocal attribute weighting[J](Pattern Recognition Letters(2006，27(11):1299-1306 [40]Matsunaga L A，EBECKE N F E Two novel term weighting for text categorization[C]( th Proceedings of the 9ernational Conference on Data Mining，Protection,Detection and other Security Technologies，Data Mining(Cadiz，Spain，2008，40:105-l14( 46 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 作者在攻读硕士学位期间公开发表的论文 【1】论文题目:信息抽取中基于DOM树的过滤器方法的研究 期刊:微计算机信息 (出版时间2008.11月) 【3】论文题目:《Functional Dependency Maintenance and Lossless Join Decomposition in XML Model Decomposition》 会议:SKG2006 国际会议，出版时间2006.11月,IEEE society 47 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 作者在攻读硕士学位期间所作的项目 【1】服装行业专业搜索引擎系统 48 上海大学硕士学位论文 The Postgraduate Thesis of Shanghai University 致 谢 感谢党，感谢国家～ 49