高激励项集的挖掘研究

基于支持度的关联规则只能找出所有的频繁集,无法找到那些非频繁但效用很高的项集;基于效用的关联规则致力于发现所有高效用项集,无法找到效用不高但支持度与效用的积很大的项集。为克服支持度与效用的不足,提出了一种新的项集重要性的度量方法（即激励）及一种自下而上的挖掘高激励项集的算法HM-Two-Phase-Miner。激励集成了支持度与效用的优点,能同时表达项集的语义特性与统计特性。HM-Two-Phase-Miner利用事务权重激励向下封闭特性进行减枝,有效提高了算法的性能。     

A fuzzy coherent rule mining algorithm

In real-world applications, transactions usually consist of quantitative values. Many fuzzy data mining approaches have thus been proposed for finding fuzzy association rules with the predefined minimum support from the give quantitative transactions. However, the common problems of those approaches are that an appropriate minimum support is hard to set, and the derived rules usually expose common-sense knowledge which may not be interesting in business point of view. In this paper, an algorithm for mining fuzzy coherent rules is proposed for overcoming those problems with the properties of propositional logic. It first transforms quantitative transactions into fuzzy sets. Then, those generated fuzzy sets are collected to generate candidate fuzzy coherent rules. Finally, contingency tables are calculated and used for checking those candidate fuzzy coherent rules satisfy the four criteria or not. If yes, it is a fuzzy coherent rule. Experiments on the foodmart dataset are also made to show the effectiveness of the proposed algorithm.     

HHUIM：一种新的启发式高效用项集挖掘方法

针对基于启发式的高效用项集挖掘算法在挖掘过程中可能丢失大量项集的问题,提出一种新的启发式高效用项集挖掘算法HHUIM。HHUIM利用哈里斯鹰优化算法进行种群的更新,能够有效减少项集的丢失。提出并设计了鹰的替换策略,解决了搜索空间较大的问题,降低了适应度函数值低于最小效用阈值的鹰的数量。此外,提出存储回溯策略,可有效防止算法收敛过快达到局部最优。大量的实验表明,所提算法优于目前最先进的启发式高效用项集挖掘算法。     

An efficient algorithm for mining temporal high utility itemsets from data streams

Utility of an itemset is considered as the value of this itemset, and utility mining aims at identifying the itemsets with high utilities. The temporal high utility itemsets are the itemsets whose support is larger than a pre-specified threshold in current time window of the data stream. Discovery of temporal high utility itemsets is an important process for mining interesting patterns like association rules from data streams. In this paper, we propose a novel method, namely THUI (Temporal High Utility Itemsets)-Mine, for mining temporal high utility itemsets from data streams efficiently and effectively. To the best of our knowledge, this is the first work on mining temporal high utility itemsets from data streams. The novel contribution of THUI-Mine is that it can effectively identify the temporal high utility itemsets by generating fewer candidate itemsets such that the execution time can be reduced substantially in mining all high utility itemsets in data streams. In this way, the process of discovering all temporal high utility itemsets under all time windows of data streams can be achieved effectively with less memory space and execution time. This meets the critical requirements on time and space efficiency for mining data streams. Through experimental evaluation, THUI-Mine is shown to significantly outperform other existing methods like Two-Phase algorithm under various experimental conditions.     

基于项集归减的高维频繁高效用项集挖掘多目标优化方法

频繁高效用项集挖掘是数据挖掘的一项重要任务,挖掘到的项集由支持度和效用这2个指标衡量.在一系列用于解决这类问题的方法中,进化多目标方法能够提供1组高质量解以满足不同用户的需求,避免传统算法中支持度和效用的阈值难以确定的问题.但是已有多目标算法多采用0-1编码,使得决策空间的维度与数据集中项数成正比,因此,面对高维数据集会出现维度灾难问题.鉴于此,设计一种项集归减策略,通过在进化过程中不断对不重要项进行归减以减小搜索空间.基于此策略,进而提出一种基于项集归减的高维频繁高效用项集挖掘多目标优化算法(IR-MOEA),并针对可能存在的归减过度或未归减到位的个体提出基于学习的种群修复策略用以调整进化方向.此外还提出一种基于项集适应度的初始化策略,使得算法在进化初期生成利于后期进化的稀疏解.多个数据集上的实验结果表明,所提出算法优于现有的多目标优化算法,特别是在高维数据集上.     

Fuzzy utility mining with upper-bound measure

Fuzzy utility mining has been an emerging research issue because of its simplicity and comprehensibility. Different from traditional fuzzy data mining, fuzzy utility mining considers not only quantities of items in transactions but also their profits for deriving high fuzzy utility itemsets. In this paper, we introduce a new fuzzy utility measure with the fuzzy minimum operator to evaluate the fuzzy utilities of itemsets. Besides, an effective fuzzy utility upper-bound model based on the proposed measure is designed to provide the downward-closure property in fuzzy sets, thus reducing the search space of finding high fuzzy utility itemsets. A two-phase fuzzy utility mining algorithm, named TPFU, is also proposed and described for solving the problem of fuzzy utility mining. At last, the experimental results on both synthetic and real datasets show that the proposed algorithm has good performance.     

模糊Horn子句规则挖掘算法研究

模糊关联规则可以用自然语言来表达人类知识,受到数据挖掘与知识发现研究人员的广泛关注。但是,目前大多数模糊关联规则挖掘方法仍然基于经典关联规则的支持度和可信度测度。从模糊蕴涵的观点出发,定义了模糊Horn子句规则、支持度、蕴涵强度以及相关概念,提出了模糊Horn子句规则挖掘算法。该算法可以分解为3个步骤。首先,将定量数据库转换为模糊数据库。其次,挖掘模糊数据库中所有支持度不小于指定最小支持度阂值的频繁项目集。一旦得到了所有频繁项目集,就可以用一种直接的方法生成所有蕴涵强度不小于指定最小蕴涵强度阂值的模糊Horn子句规则。     

频繁和高效用项集挖掘

对从事务数据库中挖掘有意义的项集的研究已超过10年.然而,大多数的研究要么使用频繁度或支持度(如频繁项集挖掘),要么使用效用值或利润(如高效用项集挖掘)作为主要的衡量标准.单独使用这两种衡量方式都有各自的局限性,比如频繁度很高的项集其效用值有可能很低,而效用值很高的项集其频繁度往往很低,将这些项集推荐给用户没有意义.将这两种衡量标准综合考虑,希望找出那些频繁度和效用值都很高的项集.该项工作最大的挑战是效用值既不满足单调性也不满足反单调性.因此,提出了高效算法FHIMA.FHIMA采用PrefixSpan的思想,挖掘时能避免产生非频繁的候选项集.此外,还根据效用和质量上界的一些性质,有效地缩小了搜索空间,极大地提高了FHIMA算法的效率.     

Mining itemset utilities from transaction databases

The rationale behind mining frequent itemsets is that only itemsets with high frequency are of interest to users. However, the practical usefulness of frequent itemsets is limited by the significance of the discovered itemsets. A frequent itemset only reflects the statistical correlation between items, and it does not reflect the semantic significance of the items. In this paper, we propose a utility based itemset mining approach to overcome this limitation. The proposed approach permits users to quantify their preferences concerning the usefulness of itemsets using utility values. The usefulness of an itemset is characterized as a utility constraint. That is, an itemset is interesting to the user only if it satisfies a given utility constraint. We show that the pruning strategies used in previous itemset mining approaches cannot be applied to utility constraints. In response, we identify several mathematical properties of utility constraints. Then, two novel pruning strategies are designed. Two algorithms for utility based itemset mining are developed by incorporating these pruning strategies. The algorithms are evaluated by applying them to synthetic and real world databases. Experimental results show that the proposed algorithms are effective on the databases tested.     

Mining itemset utilities from transaction databases

The rationale behind mining frequent itemsets is that only itemsets with high frequency are of interest to users. However, the practical usefulness of frequent itemsets is limited by the significance of the discovered itemsets. A frequent itemset only reflects the statistical correlation between items, and it does not reflect the semantic significance of the items. In this paper, we propose a utility based itemset mining approach to overcome this limitation. The proposed approach permits users to quantify their preferences concerning the usefulness of itemsets using utility values. The usefulness of an itemset is characterized as a utility constraint. That is, an itemset is interesting to the user only if it satisfies a given utility constraint. We show that the pruning strategies used in previous itemset mining approaches cannot be applied to utility constraints. In response, we identify several mathematical properties of utility constraints. Then, two novel pruning strategies are designed. Two algorithms for utility based itemset mining are developed by incorporating these pruning strategies. The algorithms are evaluated by applying them to synthetic and real world databases. Experimental results show that the proposed algorithms are effective on the databases tested.     

Effective utility mining with the measure of average utility

Frequent-itemset mining only considers the frequency of occurrence of the items but does not reflect any other factors, such as price or profit. Utility mining is an extension of frequent-itemset mining, considering cost, profit or other measures from user preference. Traditionally, the utility of an itemset is the summation of the utilities of the itemset in all the transactions regardless of its length. The average utility measure is thus adopted in this paper to reveal a better utility effect of combining several items than the original utility measure. It is defined as the total utility of an itemset divided by its number of items within it. The average-utility itemsets, as well as the original utility itemsets, does not have the “downward-closure” property. A mining algorithm is then proposed to efficiently find the high average-utility itemsets. It uses the summation of the maximal utility among the items in each transaction with the target itemset as the upper bound to overestimate the actual average utilities of the itemset and processes it in two phases. As expected, the mined high average-utility itemsets in the proposed way will be fewer than the high utility itemsets under the same threshold. The proposed approach can thus be executed under a larger threshold than the original, thus with a more significant and relevant criterion. Experimental results also show the performance of the proposed algorithm.     

Maintaining the discovered high-utility itemsets with transaction modification

Most approaches for discovering frequent itemsets derive association rules from a binary database. Profit, cost, and quantity are not considered in traditional association-rule mining. Utility mining was proposed to measure the utilities of purchase products to derive highutility itemsets (HUIs). Many algorithms have been proposed to efficiently find HUIs from a static database. In real-world applications, transactions are inserted, deleted, or modified in dynamic situations. Existing batch approaches have to re-process the updated database since previously discovered HUIs are not maintained. In this paper, a Fast UPdated (FUP) strategy with utility measure and a maintenance algorithm, called FUP-HUI-MOD, are developed to efficiently maintain and update discovered HUIs. When transactions are modified, the proposed algorithm partitions the transactions before and after the modification into two parts, creating four cases. Each case is maintained using a specific procedure to update the discovered HUIs. Based on the designed FUP-HUI-MOD algorithm, the original database is not required to be rescanned each time compared to the state-of-the-art high-utility itemset mining algorithms in batch mode. Experiments are conducted to show that the proposed algorithm outperforms batch algorithms in maintaining HUIs.     

向量内积策略的多支持度正负关联规则挖掘

在研究负关联规则相关特性的基础上,将向量内积引入到该领域,提出了一种基于向量内积的多最小支持度正负关联规则挖掘算法。考虑到事务数据库中各项集分布不均而导致的单一最小支持度难以设定的问题,采用了多最小支持度策略,设计了一种能同时挖掘出频繁与非频繁项集,以及从这些项集中挖掘出正负关联规则的算法。实验结果表明,该算法仅需扫描一次数据库,且具有动态剪枝,不保留中间候选项和节省大量内存等优点,对事务数据库中负关联规则的挖掘具有重要意义。     

Finding frequent itemsets over online data streams

Conventional data mining methods for finding frequent itemsets require considerable computing time to produce their results from a large data set. Due to this reason, it is almost impossible to apply them to an analysis task in an online data stream where a new transaction is continuously generated at a rapid rate. An algorithm for finding frequent itemsets over an online data stream should support flexible trade-off between processing time and mining accuracy. Furthermore, the most up-to-date resulting set of frequent itemsets should be available quickly at any moment. To satisfy these requirements, this paper proposes a data mining method for finding frequent itemsets over an online data stream. The proposed method examines each transaction one-by-one without any candidate generation process. The count of an itemset that appears in each transaction is monitored by a lexicographic tree resided in main memory. The current set of monitored itemsets in an online data stream is minimized by two major operations: delayed-insertion and pruning. The former is delaying the insertion of a new itemset in recent transactions until the itemset becomes significant enough to be monitored. The latter is pruning a monitored itemset when the itemset turns out to be insignificant. The number of monitored itemsets can be flexibly controlled by the thresholds of these two operations. As the number of monitored itemsets is decreased, frequent itemsets in the online data stream are more rapidly traced while they are less accurate. The performance of the proposed method is analyzed through a series of experiments in order to identify its various characteristics.     

An improved data mining approach using predictive itemsets

In this paper, we present a mining algorithm to improve the efficiency of finding large itemsets. Based on the concept of prediction proposed in the (n, p) algorithm, our method considers the data dependency in the given transactions to predict promising and non-promising candidate itemsets. Our method estimates for each level a different support threshold that is derived from a data dependency parameter and determines whether an item should be included in a promising candidate itemset directly. In this way, we maintain the efficiency of finding large itemsets by reducing the number of scanning the input dataset and the number candidate items. Experimental results show our method has a better efficiency than the apriori and the (n, p) algorithms when the minimum support value is small.     

一种无冗余的Web日志挖掘算法

Web日志挖掘是Web数据挖掘的一个重要研究领域。Web日志挖掘通过发现Web日志中用户的访问规律和模式,可以提取出其中潜在的规律和信息,人们对这个领域的研究也日益重视。然而,传统的基于关联规则的Web日志挖掘算法都是基于所有关联规则的。这种方式往往挖掘产生大量的候选规则,而且存在大量冗余的规则。提出了一种新的无冗余的Web日志挖掘算法,该算法通过引入频繁闭项集合最小关联规则的概念,从而解决了以往基于所有关联规则挖掘算法中出现的上述问题。     

一种结合散列与位表挖掘频繁项目集算法

在频繁项集的挖掘中,很多算法都是基于Apriori的。这些算法有两个共同的问题:一是把整个数据库装入内存,占用大量的空间;二是在产生候选项集和计算支持度时花费了大量的时间。为了提高效率,提出了一种基于位表挖掘频繁项目集的算法Hash-BFI。按照水平和垂直的方向把数据库压缩到位表内,以大大节省内存空间。引入散列函数计算频繁二项集,完全通过AND, OR运算得到候选项集和计算候选项集支持度,并进行剪枝,从而提高了算法效率。     

基于粗糙集和单事务项组合的关联规则挖掘算法

Apriori算法必须反复地扫描数据库才能求出频繁项集,效率较低,且不支持更新挖掘。为了解决这些问题,提出了一种基于粗糙集、单事务项组合和集合运算的关联规则挖掘算法。本算法首先利用粗糙集进行属性约简,对新决策表中的每个事务进行“数据项”组合并标记地址,然后利用集合运算的方法计算支持度和置信度即可挖掘出有效规则。本算法只需要一次扫描数据库,同时有效地支持了关联规则的更新挖掘。应用实例和实验结果表明,本算法明显优于Apriori算法,是一种有效且快速的关联规则挖掘算法。     

最大值控制的多最小支持度关联规则挖掘算法

大部分关联规则挖掘算法使用同一最小支持度阈值进行挖掘，但在实际使用中由干各项目发生频率的不同，理应有不同的最小支持度支持。该文提出了一种多最小支持度关联规则挖掘算法，为每一项目设置一最小支持度，同时在生成舒选集和最大频繁集的过程中使用最大值控制来实现剪枝，有效地提高了该算法的效率，最后用一个超市销售物品的例子来说明该算法的使用。