【作者】 钱铁云；

【导师】 王元珍；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2006， 博士

【摘要】 信息存储技术和通信技术的飞速发展使得越来越多的文字信息开始以计算机可读的形式存在,并且其数量每天都在增加和更新。对大量电子文档进行有效的过滤并进行自动分类组织,将有助于文档的检索和分析。关联分类作为基于规则分类方法的一种扩展,已经引起了众多研究者的兴趣,但其在文本领域的应用仍未得到充分的重视。为了使关联分类更好地适合文本分类的需要,对关联文本分类中存在的主要问题进行了深入细致的分析,提出了相应的解决策略,取得了比现有文本分类系统更好的精度和效率。围绕关联文本分类的关键技术完成了以下工作:比较和分析了不同支持度阈值对关联分类系统性能的影响。证明了在文本分类中,较低的支持度设置可以提供更大的词典和对数据更全面的描述,因而有利于分类性能的提高,但这同时也会导致规则数目的急剧膨胀和噪声比例的上升,规则抽取工作将变得更加低效和困难。在深入探讨影响规则抽取速度因素的基础上,针对规则抽取中的规则评估和规则筛选,分别提出了两种优化技术。在评估阶段,提出一种“数据缓存”和“倒转匹配”相结合的优化技术,避免了对原始数据集的多次遍历及对每个文档求子集操作所带来的巨大开销;在筛选阶段,提出一种“垂直修剪”的优化技术,代替目前常用的完全方式的“一般-特殊”序裁剪,该方法在保证区分性能的同时可明显减少计算时间。系统研究了关联分类环境下的特征选择问题。分析了在关联分类中按传统的预处理方式选择特征所导致的问题,阐述了在关联分类环境下设计新的特征选择方法的必要性。通过证明支持度、置信度与特征选择常用度量之间存在的转换关系,提出一种将特征选择集成到规则评估阶段的新方法,从而解决了预选特征不能保证成为频繁项的难题,同时总结对比了各种特征选择的常用度量在关联分类中的性能表现。在此基础上,提出了一个结合特征选择和规则选择的快速规则抽取算法FARE。提出一种新的关联区分算法ACA,该算法引入了一种“接受者决定”思想,以便当多条存在“一般-特殊”序的规则匹配同一测试文档时,由测试文档本身自适应地选择其最佳匹配规则,以取得准确率和召回率之间的合理平衡。ACA还引入规范因子和置信区间的概念,以消除因分类器之间规则数量和质量差异而导致的区分性能下降。此外,ACA提出利用类别特征词形成虚拟规则以对部分无法匹配的测试文档进行区分。对比实验表明利用ACA区分算法可以取得比其它区分算法更高的精度。对不同关联模式在文本分类中的应用进行了深入的探索。提出了一种基于句子级别约束的2-阶段规则选择方法,同时对句子级别分类方法的优缺点进行了深入分析:利用句子级别约束可加快规则选择的速度,在某些应用中表现出良好的区分性能,但另一方面,规则过少、难以匹配等问题限制了其进一步的推广使用。因循这一研究思路,进一步提出在文档级别利用超级关联组合替代频繁项进行分类的方法,并从候选规则数目、训练时间和区分性能等多个角度比较了两种模式对分类系统的影响,得出了超级关联组合比频繁项更适合作为候选模式的重要结论。与其它著名文本分类算法如SVM的对比还表明,以超级关联组合作为候选模式,结合快速规则抽取算法FARE和关联区分算法ACA,可以取得媲美或超过SVM的区分效果,且其时间开销远远小于SVM。在深入分析中文语言学特性对关联文本分类的影响的基础上,提出利用prefix-hash-tree完成中文文档向事务数据的转换,并提出利用词汇类频率量化划分和过滤中文词汇,以有效缩减事务数据库规模,提高训练和区分算法的效率以及区分的精度。以此为基础开发的自动文本分类工具已成功应用于多个电子政务项目。更多还原

【Abstract】 With the rapid expansion of electronic publication from World Wide Web, intranet and digital library, it becomes more and more important to index or organize textual information category by category. The large volume of information makes it almost impossible to manually determine the label. Therefore it would be helpful to automatically examine the text and categorize documents into one or more topics by a text classification system.As a rule-based method, associative classification has attracted great interest and a variety of useful methods have been developed. This dissertation applies associative classification into text area. It discusses the key problems arising from the current approaches and then develops a new framework to address these problems. The methods proposed in this thesis are proven to outperform state-of-art classification algorithms in terms of both computational performance and classification accuracy.Support threshold is a crucial parameter related to associative classification. This dissertation first demonstrates that low support threshold conduces to better classifiers since it provides larger vocabulary size and more general description of data, and meanwhile it brings in the difficulty of rule extraction due to the huge amount of rule number. In order to remove really bad rules while keeping beneficial ones, we present a general-to-specific pruning method to eliminate rules with both lower confidence and lower support. However, it is quite time consuming to judge general-to-specific ordering among different rules. So we exploit a vertical pruning strategy, which retains the same power of complete pruning but substantially reduces the time cost.Feature selection, a major research area in information retrieval due to its capability of noise removal and dimensionality deduction, has played an important role in text classification. All current systems use feature selection as a separate preprocess procedure. In the context of associative text classification, predefined features may not naturally become frequent itemsets. We describe that the traditional metrics in feature selection can be transformed into expressions of support and confidence. Moreover, we develop a method to integrate feature selection into rule exaction process. By doing so, we can compute these metric almost for free and dynamically determine the best feature number without saving multiple copies of original data.This thesis also intensifies the classification method. If there are multiple rules exhibiting general-to-specific relationship matching the same test file, a“receiver deciding”strategy is adopted to adaptively select the best matching rule of the receiver (test document). Through this way, we get trade-off between high precision and high recall. We also introduce a norm factor and a confidence interval to counteract the deterioration caused by the quality and quantity imbalance among different classifiers.Different association patterns are chosen as candidate patterns for text classification in this thesis. First, sentential level frequent itemsets, along with a special rule selection and classification algorithm, are introduced into text classification, and the cons and pros of such an approach are thoroughly analyzed. Second, we compare two document level association patterns, hyperclique patterns and frequent patterns, from the aspects of rule number, training time and classification performance, and we draw an important conclusion that hyperclique patterns are more suitable for text categorization tasks than frequent itemstes. Moreover, extensive experiments on several real data sets show that our hyperclique based associative text classification reaches higher performance than SVM.At the end of this dissertation, we analyze the influence of characteristics of Chinese on text categorization. We design a prefix-hash-tree data structure to convert Chinese document into transaction data. Also, class frequency of terms is defined to quantify, partition and filter Chinese words. As a consequence, the size of database is greatly reduced and classification accuracy is improved. Related tool has been successfully applied to e-government domain.更多还原