论文部分内容阅读
信息时代为我们带来了海量数据,如何帮助人们有效地收集和选择感兴趣的信息,并且在日益增多的信息中发现潜在有用的知识已经成为信息技术领域的热点问题。面对这样的挑战,数据挖掘和知识发现技术应运而生,并得以蓬勃发展。文本关联分析是文本挖掘领域的重要挖掘任务之一,它是从文档集合中找出不同词语之间的关系的过程。其多数方法是从数据挖掘领域的关联规则挖掘借鉴而来。首先,本文对基于关键字的文本关联分析的特点进行了研究,它与传统关系数据库项集间的关联分析类似。可以把文本看成事务、文本中的关键词看成事务中的项,这样文本数据库中关键字的关联分析问题就转化成事务数据库中事务项的关联分析问题。但由于文本数据库的高维稀疏性,对不同的文本集使用相同的最小支持度阈值而产生的频繁项集,其规模大小相差甚远。因此阈值的设定成为文本关联分析的一个难点。其次,本文重点研究了N个最频繁项集挖掘算法—IntvMatrix。该算法使用了阈值动态调整策略,这样就解决了阈值难以设定的问题,从而可以通过指定的频繁项集数目N来控制产生频繁项集的规模。但其缺点是构造倒排矩阵容易造成空间上的浪费,并且倒排矩阵中建立项之间的联系又需要多次扫描数据库,造成了时间上的浪费。然后,针对IntvMatrix算法存在的问题,本论文提出了一种基于改进的FP-Tree挖掘N个最频繁项集的算法。先对文本数据库的事务项以及整个数据库进行排序,同时将非频繁项删除,这样就大大减少了生成FP-Tree时搜索共享前缀的时间。接着在改进的FP-Tree的基础上来构造局部频繁项的COFI-Tree,就可以省去对非频繁项集的扫描。本算法依然采用了阈值动态调整这一策略,从而在技术上为产生N个最频繁项集作了保证。最后,通过在同一文本数据库的基础上设置不同频繁项集数N,对改进后的算法与IntvMatrix算法进行分析与比较。实验结果证明,由于采用改进后的FP-Tree来构造局部COFI-Tree,以及对算法中数据结构的优化,在挖掘文本数据库时,算法的时间和空间利用率得以提高。