OPTIMONOTONE MEASURES FOR OPTIMAL RULE DISCOVERY

Many studies have shown the limits of the support/confidence framework used in Apriori ‐like algorithms to mine association rules. There are a lot of efficient implementations based on the antimonotony property of the support, but candidate set generation (e.g., frequent item set mining) is still costly. In addition, many rules are uninteresting or redundant and one can miss interesting rules like nuggets. We are thus facing a complexity issue and a quality issue. One solution is to not use frequent itemset mining and to focus as soon as possible on interesting rules using additional interestingness measures. We present here a formal framework that allows us to make a link between analytic and algorithmic properties of interestingness measures. We introduce the notion of optimonotony in relation with the optimal rule discovery framework. We then demonstrate a necessary and sufficient condition for the existence of optimonotony. This result can thus be applied to classify the measures. We study the case of 39 classical measures and show that 31 of them are optimonotone. These optimonotone measures can thus be used with an underlying pruning strategy. Empirical evaluations show that the pruning strategy is efficient and leads to the discovery of nuggets using an optimonotone measure and without the support constraint.     

基于改进FP树的项项正相关关联规则挖掘

兴趣度量在关联规则挖掘中常用来发现那些潜在的令人感兴趣的模式,基于FP树结构的FP-growth算法是目前较高效的关联规则挖掘算法之一,如果挖掘潜在的有价值的低支持度模式,这种算法效率较低。为此,本文提出一种新的兴趣度量—项项正相关兴趣度量,该量度具有良好的反单调性,所得到的模式中任意一项在事务中的出现均可提升模式中其余项出现的可能性。同时,提出一种改进的FP挖掘算法,该算法采用一种压缩的FP树结构,并利用非递归调用方法来减少挖掘中建立额外条件模式树的开销。更为重要的是,在频繁项集挖掘中引入项项正相关兴趣度量剪枝策略,有效过滤掉非正相关长模式和无效项集,扩大了可挖掘支持度阈值范围。实验结果表明,该算法是有效和可行的。     

基于IF-THEN规则的决策树裁剪算法

决策树是机器学习和数据挖掘领域中一种基本的学习方法。文中分析了C4.5算法以及该算法不足之处,提出了一种决策树裁剪算法,其中以规则信息量作为判断标准。实验结果表明这种方法可以提高最终模型的预测精度,并能够很好克服数据中的噪音。     

一种基于粗糙集和神经规则法的数据挖掘新方法

确立了结合粗糙集理论和神经规则法进行数据挖掘的方法.首先通过粗糙集对需要挖掘的数据进行预处理,实现属性的约简,然后应用神经规则法进行网络剪枝和规则提取.通过实例计算表明,在结果置信度降低不多的情况下,可以得到简单明确的关联规则,并有效地提高数据挖掘的效率.     

Efficient Mining of Discriminating Relationships Among Attributes Involving Arithmetic Operations

Contrast patterns describe differences between two or more data sets or data classes; they have been proven to be useful for solving many kinds of problems, such as building accurate classifiers, defining clustering quality measures, and analyzing disease subtypes. This article investigates the mining of a new kind of contrast patterns, namely discriminating inter‐attribute functions (DIFs), which represent arithmetic‐expression‐based inter‐attribute relationships that distinguish classes of data. DIFs are an expressive and practical alternative of item‐based contrast patterns and can express discriminating relationships such as “weight/(height)² is more likely to be ≤25 in one class than in another class.” Besides introducing the DIF mining problem, this article makes theoretical and algorithmic contributions on the problem. We prove that DIF mining is MAX SNP‐hard. Regarding how to efficiently mine DIFs, we present a set of rules to prune the search space of arithmetic expressions by eliminating redundant ones (equivalent to some others). We give two algorithms: one for finding all DIFs satisfying given thresholds and another for finding certain optimal DIFs using genetic computation techniques. The former is useful when the number of attributes is small, whereas the latter is useful when that number is large; both use the redundant arithmetic‐expression pruning rules. A performance study shows that our techniques are effective and efficient for finding DIFs.     

挖掘所关注规则的多策略方法研究

通过数据挖掘,从大型数据库中发现了大量规则,如何选取所关注的规则,是知识发现的重要研究内容。该文研究了利用领域知识对规则的主观关注程度进行度量的方法,给出了一个能够度量规则的简洁性和新奇性的客观关注程度的计算函数,提出了选取用户关注的规则的多策略方法。     

影响关联规则挖掘的有趣性因素的研究

关联规则挖掘是数据挖掘研究中的一个重要方面,而其中一个重要问题是对挖掘出的规则的感兴趣程度的评估。实际应用中可从数据源中挖掘出大量的规则,但这些规则中的大部分对用户来说是不一定感兴趣的。关联规则挖掘中的有趣性问题可从客观和主观两个方面对关联规则的兴趣度进行评测。利用模板将用户感兴趣的规则和不感兴趣的规则区分开,以此来完成关联规则有趣性的主观评测;在关联规则的置信度和支持度基础上对关联规则的有趣性的客观评测增加了约束。     

Exploiting highly qualified pattern with frequency and weight occupancy

By identifying useful knowledge embedded in the behavior of search engines, users can provide valuable information for web searching and data mining. Numerous algorithms have been proposed to find the desired interesting patterns, i.e., frequent pattern, in real-world applications. Most of those studies use frequency to measure the interestingness of patterns. However, each object may have different importance in these real-world applications, and the frequent ones do not usually contain a large portion of the desired patterns. In this paper, we present a novel method, called exploiting highly qualified patterns with frequency and weight occupancy (QFWO), to suggest the possible highly qualified patterns that utilize the idea of co-occurrence and weight occupancy. By considering item weight, weight occupancy and the frequency of patterns, in this paper, we designed a new highly qualified patterns. A novel Set-enumeration tree called the frequency-weight (FW)-tree and two compact data structures named weight-list and FW-table are designed to hold the global downward closure property and partial downward closure property of quality and weight occupancy to further prune the search space. The proposed method can exploit high qualified patterns in a recursive manner without candidate generation. Extensive experiments were conducted both on real-world and synthetic datasets to evaluate the effectiveness and efficiency of the proposed algorithm. Results demonstrate that the obtained patterns are reasonable and acceptable. Moreover, the designed QFWO with several pruning strategies is quite efficient in terms of runtime and search space.     

基于分类修剪的关联分类算法改进

针对现有关联分类算法资源消耗大、规则剪枝难、分类模型复杂的缺陷,提出了一种基于分类修剪的关联分类算法改进方案ACCP.根据分类属性值的不同对分类规则前项进行分块挖掘,并对频繁项集挖掘过程和规则修剪进行了改进,有效提高了分类准确率和算法运行效率.实验结果表明,此算法改进方案相比传统CBA算法和C4.5决策树算法有着更高的分类准确率,取得了较好的应用效果.     

关联规则挖掘AprioriTid算法优化研究

提出了一种基于事务压缩和项目压缩的AprioriTid优化算法。该算法的特点是：项目集采用关键字识别,同时对事务数据进行事务和项目压缩。从而省去了Apriori算法和AprioriTid算法中的剪枝和模式匹配步骤,减小了扫描事务数据库的大小,提高了发现规则的效率。通过实验表明,优化的算法执行效率明显优于AprioriTid算法。     

一种时态关联规则挖掘算法

时态关联规则挖掘是针对在一段时间范围内的关联挖掘,在现实中有较多的应用。现有的大多数时态关联挖掘算法或者需要多次扫描数据库,或者没有考虑各个项在数据集上出现或结束时间上的不同,因而挖掘性能受到较大的制约。为此,本文提出一种增量式的面向具有不同时间出现与结束的项的时态关联规则挖掘算法。为减少存储方面的开销,只需保存已挖掘过的历史数据集中的频繁1项集。为了减少数据的扫描量,通过有效的剪枝策略,有选择性地扫描相关事务项,至多只需扫描一次完整的数据库。实验证明,该算法具有较好的挖掘性能。     

Progressive partition miner: an efficient algorithm for mining general temporal association rules

We explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items of which each item contains an individual exhibition period. The current model of association rule mining is not able to handle the publication database due to the following fundamental problems, i.e., 1) lack of consideration of the exhibition period of each individual item and 2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm progressive-partition-miner (abbreviated as PPM) to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database in light of exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset based on the intrinsic partitioning characteristics. Algorithm PPM is also designed to employ a filtering threshold in each partition to early prune out those cumulatively infrequent 2-itemsets. The feature that the number of candidate 2-itemsets generated by PPM is very close to the number of frequent 2-itemsets allows us to employ the scan reduction technique to effectively reduce the number of database scans. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by other competitive schemes that are directly extended from existing methods. The correctness of PPM is proven and some of its theoretical properties are derived. Sensitivity analysis of various parameters is conducted to provide many insights into Algorithm PPM.     

Resolving inconsistencies and redundancies in declarative process models

Declarative process models define the behaviour of business processes as a set of constraints. Declarative process discovery aims at inferring such constraints from event logs. Existing discovery techniques verify the satisfaction of candidate constraints over the log, but completely neglect their interactions. As a result, the inferred constraints can be mutually contradicting and their interplay may lead to an inconsistent process model that does not accept any trace. In such a case, the output turns out to be unusable for enactment, simulation or verification purposes. In addition, the discovered model contains, in general, redundancies that are due to complex interactions of several constraints and that cannot be cured using existing pruning approaches. We address these problems by proposing a technique that automatically resolves conflicts within the discovered models and is more powerful than existing pruning techniques to eliminate redundancies. First, we formally define the problems of constraint redundancy and conflict resolution. Second, we introduce techniques based on the notion of automata-product monoid, which guarantees the consistency of the discovered models and, at the same time, keeps the most interesting constraints in the pruned set. The level of interestingness is dictated by user-specified prioritisation criteria. We evaluate the devised techniques on a set of real-world event logs.     

基于联邦强化学习的分布式模型剪枝

联邦学习系统中, 在资源受限的边缘端进行本地模型训练存在一定的挑战. 计算、存储、能耗等方面的限制时刻影响着模型规模及效果. 传统的联邦剪枝方法在联邦训练过程中对模型进行剪裁, 但仍存在无法根据模型所处环境自适应修剪以及移除一些重要参数导致模型性能下降的情况. 本文提出基于联邦强化学习的分布式模型剪枝方法以解决此问题. 首先, 将模型剪枝过程抽象化, 建立马尔可夫决策过程, 使用DQN算法构建通用强化剪枝模型, 动态调整剪枝率, 提高模型的泛化性能. 其次设计针对稀疏模型的聚合方法, 辅助强化泛化剪枝方法, 更好地优化模型结构, 降低模型的复杂度. 最后, 在多个公开数据集上将本方法与不同基线方法进行比较. 实验结果表明, 本文所提出的方法在保持模型效果的同时减少模型复杂度.     

On the Kalman filtering method in neural network training andpruning

In the use of the extended Kalman filter approach in training and pruning a feedforward neural network, one usually encounters the problems of how to set the initial condition and how to use the result obtained to prune a neural network. In this paper, some cues on the setting of the initial condition are presented with a simple example illustrated. Then based on three assumptions: 1) the size of training set is large enough; 2) the training is able to converge; and 3) the trained network model is close to the actual one, an elegant equation linking the error sensitivity measure (the saliency) and the result obtained via an extended Kalman filter is devised. The validity of the devised equation is then testified by a simulated example.     

On Mining Instance-Centric Classification Rules

Many studies have shown that rule-based classifiers perform well in classifying categorical and sparse high-dimensional databases. However, a fundamental limitation with many rule-based classifiers is that they find the rules by employing various heuristic methods to prune the search space and select the rules based on the sequential database covering paradigm. As a result, the final set of rules that they use may not be the globally best rules for some instances in the training database. To make matters worse, these algorithms fail to fully exploit some more effective search space pruning methods in order to scale to large databases. In this paper, we present a new classifier, HARMONY, which directly mines the final set of classification rules. HARMONY uses an instance-centric rule-generation approach and it can assure that, for each training instance, one of the highest-confidence rules covering this instance is included in the final rule set, which helps in improving the overall accuracy of the classifier. By introducing several novel search strategies and pruning methods into the rule discovery process, HARMONY also has high efficiency and good scalability. Our thorough performance study with some large text and categorical databases has shown that HARMONY outperforms many well-known classifiers in terms of both accuracy and computational efficiency and scales well with regard to the database size     

相关测度与增量式支持度和信任度的计算

通过相关测度的定义,从理论上探讨了增量式规则发现问题,并把分类规则挖掘和关联规则挖掘联系起来进行研究,为该问题的深入研究奠定了理论基础.相关测度刻画了给定关系和相关集合的数字特征.对相关测度的概念、定义、性质以及与支持度和信任度的关系等方面作了详细的分析和探讨,给出了基于相关集合的支持度和信任度的定义及计算方法.证明了测度增量定理和支持度增量定理,并给出了增量式支持度和信任度的计算公式.另外还详细地分析了数据增量对关联规则和信任度的影响,探讨了基于新支持度的候选项的修剪问题.所提出的相关测度及其思想为研究既能用于分类规则又能用于关联规则的统一数据挖掘方法提供了有价值的新思路.     

Mining frequent arrangements of temporal intervals

The problem of discovering frequent arrangements of temporal intervals is studied. It is assumed that the database consists of sequences of events, where an event occurs during a time-interval. The goal is to mine temporal arrangements of event intervals that appear frequently in the database. The motivation of this work is the observation that in practice most events are not instantaneous but occur over a period of time and different events may occur concurrently. Thus, there are many practical applications that require mining such temporal correlations between intervals including the linguistic analysis of annotated data from American Sign Language as well as network and biological data. Three efficient methods to find frequent arrangements of temporal intervals are described; the first two are tree-based and use breadth and depth first search to mine the set of frequent arrangements, whereas the third one is prefix-based. The above methods apply efficient pruning techniques that include a set of constraints that add user-controlled focus into the mining process. Moreover, based on the extracted patterns a standard method for mining association rules is employed that applies different interestingness measures to evaluate the significance of the discovered patterns and rules. The performance of the proposed algorithms is evaluated and compared with other approaches on real (American Sign Language annotations and network data) and large synthetic datasets.