Text Clustering Using Frequent Weighted Utility Itemsets

ABSTRACT

Text clustering is an important topic in text mining. One of the most effective methods for text clustering is an approach based on frequent itemsets (FIs), and thus, there are many related algorithms that aim to improve the accuracy of text clustering. However, these do not focus on the weights of terms in documents, even though the frequency of each term in each document has a great impact on the results. In this work, we propose a new method for text clustering based on frequent weighted utility itemsets (FWUI). First, we calculate the Term Frequency (TF) for each term in documents to create a weight matrix for all documents. The weights of terms in documents are based on the Inverse Document Frequency. Next, we use the Modification Weighted Itemset Tidset (MWIT)-FWUI algorithm for mining FWUI from a number matrix and the weights of terms in documents. Finally, based on frequent utility itemsets, we cluster documents using the MC (Maximum Capturing) algorithm. The proposed method has been evaluated on three data sets consisting of 1,600 documents covering 16 topics. The experimental results show that our method, using FWUI, improves the accuracy of the text clustering compared to methods using FIs.     

一种基于最大加权频繁项目集的数据库相似性判别算法

在引入最大加权频繁项目集之后,给出一种新的数据库相似性度量模型,并提出基于最大加权频繁项目集的数据库相似性度量算法．该算法可有效地改进基于最大频繁项目集的数据库相似性度量方法,提高数据库相似性度量准确性．在实际应用中,改进模型为分布多库环境下数据挖掘的数据准备提供有效的框架,因而具有重要的使用价值．     

生成频繁项目集的一种贪心算法

在关联规则的研究中生成频繁项目集是一个重要的研究课题。该文引入“二进制位向量”数据结构,并采用“袋子”之思想,提出了一种一遍扫描而生成所有频繁项目集之贪心算法。     

一种频繁核心项集的快速挖掘算法

传统的频繁核心项集挖掘需多次生成和反复扫描数据库,导致生成效率低下。为此,提出一种快速生成频繁核心项集算法FMEP。该算法使用Rymon枚举树作为搜索空间,并采用分而治之的策略选择特定的路径进行剪枝。利用频繁核心项集特有的反单调性质,可以快速地判断某一个候选项集是否为频繁核心项集,而无需和所有直接子集的析取支持度进行比较。通过上述方法,可以达到快速挖掘的目的。实验结果证明,该算法能够在挖掘出所有的频繁核心项集精简表示元素的同时,降低消耗时间,与MEP算法相比,在密集型数据集上的时间可缩短2倍以上,在稀疏型数据集上时间至少缩短30%。     

一个频繁闭项集高效挖掘算法

提出了一种基于堆栈的频繁闭项集挖掘算法SBFCI（Stack Based Frequent Closed Itemsets Generation）,该算法采用栈技术避免了以往基于FP—tree的算法需对每个后缀模式递归构造FP—tree,并在上挖掘的弊端。从而大幅缩减了生成频繁闭项集的时间与空间开销。     

一种挖掘频繁项集和频繁闭包项集的算法

文章基于AprioriTid和挖掘闭包项集算法Close提出了一种新算法FFC算法,该算法能同时生成频繁项集和频繁闭包项集。提高效率的同时又为挖掘无冗余规则奠定了基础。     

一种挖掘最大频繁项集的深度优先算法

最大频繁项集挖掘是许多数据挖掘应用中的重要问题．提出一种新的深度优先搜索最大频繁项集的算法．该算法采用位图数据格式,结合了流行的各种有效剪枝技术,并使用局部最大频繁项集来进行高效的超集存在判断,明显地加速了最大频繁项集的生成,从而降低了CPU时间．     

频繁集挖掘算法研究

归纳分析了关联规则的典型挖掘算法及其思想,并通过实例比较各算法之间的差别,同时讨论了各种算法的优化技术,分析了他们的适应性及优缺点.     

频繁项集挖掘算法研究

频繁项集挖掘是许多数据挖掘任务中的关键问题,也是关联规则挖掘算法的核心,所以提高频繁项集的生成效率一直是近几年数据挖掘领域研究的热点之一.本文以频繁项集挖掘算法的搜索方式和计数方式为主线,分析频繁项集挖掘中的代表性算法及其中的关键技术和方法,对近年来相关研究的新进展做了介绍和评述,并指出了未来的研究方向.     

一种基于ESEquivPS的封闭频繁项集挖掘算法

本文提出一种基于ESEquivPS(扩展支持度相等性剪枝策略)的封闭频繁项集挖掘算法ECFIMA。该算法采用深度优先和广度优先相结合的策略访问搜索空间,使用垂直位图向量格式存储表示项集和事务数据库,同时利用基本剪枝策略、相等性剪枝策略、扩展支持度相等性剪枝策略1和扩展支持度相等性剪枝策略2进行候选空间剪枝,并采用多种不同特性的测试数据集进行实验。实验结果表明,ECFIMA算法是一种高效的封闭频繁项集挖掘算法,在多种测试数据集上性能都优于CHARM算法,尤其是在拥有大量长的封闭频繁项集的测试数据集上,效率比CHARM算法提高约2~3倍。     

一种频繁项集的快速挖掘算法

关联规则的发现是数据挖掘的一个重要方面,产生频繁项集是其中一个关键步骤。提出了一种基于十字链表快速挖掘频繁项集的算法,该算法只需扫描一次数据库,充分利用已有信息产生频繁项集,无需存储候选项集。通过与其它一些算法比较,说明该算法有更好的性能。     

频繁项集挖掘算法综述

该文基于频繁项集挖掘算法的研究现状,采用自底向上遍历搜索、自顶向下遍历搜索和混合遍历搜索的分类方法,对现有的频繁项集挖掘算法进行归纳分类,分析和比较了各类别中具有代表性的挖掘算法,总结每种算法各方面的特性.同时,对一些特殊的频繁项集挖掘算法也作了简单介绍.旨在使读者全面掌握频繁项集挖掘算法目前的研究水平,便于研究者对已有的算法进行改进,提出具有更好性能的新的分类算法,也便于使用者在应用时对算法的选择和使用.     

基于异集产生频繁项集的研究

如何从密集数据库中高效挖掘频繁项集一直是数据挖掘领域研究的难点和重点。文章介绍了一种新的数据存储格式—异集。将密集数据库转换为异集数据库,可大幅度降低数据库的规模、挖掘过程产生的中间结果以及CPU计算时间。该文给出了一个基于异集数据库的频繁项集的挖掘算法,实验表明该算法有效。     

频繁项集挖掘算法综述

频繁项集挖掘算法是关联规则挖掘问题的关键,是数据挖掘领域的一个研究热点.自从Apriori算法提出至今,学者提出来大量的关于频繁项集挖掘的算法.本文按照挖掘方式将这些算法分成三类,即宽度优先、深度优先、宽度和深度相结合,并对每类算法进行了全面的综述及深入的分析,并给出了以后的研究方向.     

基于有向项集图的频繁集挖掘优化算法

关联规则挖掘是数据挖掘研究中一个非常重要的研究领域。文章利用有向项集图(DISG)来存储有关频繁项集的信息,提出了利用深度优先的策略进行搜索的频繁项集挖掘的优先算法UDBDG(Updated DFS Based DISG)。最后分析了算法在时间和空间上的复杂度并以mushroom数据库为例进行了试验。试验结果证明算法对于处理稠密集数据是有效的。     

挖掘最大频繁项集的优化方法

通过对Apriori算法以及已有相关研究工作的分析,从数据库维数压缩、项存储结构以及剪枝几个方面对算法进行了优化,并从理论与试验两方面验证了优化算法的有效性。     

一种基于上三角项集矩阵的频繁项集挖掘算法

分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于上三角项集矩阵的频繁项集挖掘优化算法。本算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率。     

多谓词约束下基于模式增长的频繁项集挖掘算法

针对多维关联规则中挖掘事务数据库的所有频繁项集这一问题,提出了基于维约束进行求解的构想。采用模式增长的挖掘方法并根据渭词约束特征,设计了两种频繁项集挖掘算法,其中MCMF11算法在指定约束下构建模式树并进行频繁项集挖掘,而节点向量约束的算法MCMF12在预先挖掘出无约束频繁项集的情况下,依据给定约束对已有频繁集及模式树进行更新搜索,因此需要开销更多的主存,但在更新过程中有更高的效率。理论分析和实验结果都表明了MCMFI算法的完备性和有效性。     

一种挖掘最大频繁集的算法

挖掘频繁项目集是关联规则应用中的关键问题.目前挖掘频繁集主要有Apriori算法和频繁树法两大类.本文提出与上述两类算法完全不同的高效挖掘最大频繁集的算法:最小支持数最小组合算法(MSMCA).该算法不产生候选频繁集,能较大减少计算量的开销.此外,在此算法的研究中,本文提出另一个子课题:重复数列中最小支持数最小组合算法研究.     

Parametric Algorithms for Mining Share Frequent Itemsets

Itemset share, the fraction of some numerical total contributed by items when they occur in itemsets, has been proposed as a measure of the importance of itemsets in association rule mining. The IAB and CAC algorithms are able to find share frequent itemsets that have infrequent subsets. These algorithms perform well, but they do not always find all possible share frequent itemsets. In this paper, we describe the incorporation of a threshold factor into these algorithms. The threshold factor can be used to increase the number of frequent itemsets found at a cost of an increase in the number of infrequent itemsets examined. The modified algorithms are tested on a large commercial database. Their behavior is examined using principles of classifier evaluation from machine learning.