Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining

Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.

Fast FP-Growth for association rule mining

In this paper, we propose an efficient algorithm, called FFP-Growth (shortfor fast FP-Growth) , to mine frequent itemsets. Similar to FP-Growth, FFP-Growth searches theFP-tree in the bottom-up order, but need not construct conditional pattern bases and sub-FP-trees,thus, saving a substantial amount of time and space, and the FP-tree created by it is much smallerthan that created by TD-FP-Growth, hence improving efficiency. At the same time, FFP-Growth can beeasily extended for reducing the search space as TD-FP-Growth (M) and TD-FP-Growth (C). Experimentalresults show that the algorithm of this paper is effective and efficient.

A Novel Incremental Mining Algorithm of Frequent Patterns for Web Usage Mining

Because data warehouse is frequently changing, incremental data leads to old knowledge which is mined formerly unavailable. In order to maintain the discovered knowledge and patterns dynamically, this study presents a novel algorithm updating for global frequent patterns-IPARUC. A rapid clustering method is introduced to divide database into n parts in IPARUC firstly, where the data are similar in the same part. Then, the nodes in the tree are adjusted dynamically in inserting process by ＂pruning and laying back＂ to keep the frequency descending order so that they can be shared to approaching optimization. Finally local frequent itemsets mined from each local dataset are merged into global frequent itemsets. The results of experimental study are very encouraging. It is obvious from experiment that IPARUC is more effective and efficient than other two contrastive methods. Furthermore, there is significant application potential to a prototype of Web log Analyzer in web usage mining that can help us to discover useful knowledge effectively, even help managers making decision.

Improved Pattern Tree for Incremental Frequent-Pattern Mining

By analyzing the existing prefix-tree data structure, an improved pattern tree was introduced for processing new transactions. It firstly stored transactions in a lexicographic order tree and then restructured the tree by sorting each path in a frequency-descending order. While updating the improved pattern tree, there was no need to rescan the entire new database or reconstruct a new tree for incremental updating. A test was performed on synthetic dataset T1014D100K with 100 000 transactions and 870 items. Experimental results show that the smaller the minimum sup- port threshold, the faster the improved pattern tree achieves over CanTree for all datasets. As the minimum support threshold increased from 2% to 3.5%, the runtime decreased from 452.71 s to 186.26 s. Meanwhile, the runtime re- quired by CanTree decreased from 1 367.03 s to 432.19 s. When the database was updated, the execution time of im- proved pattern tree consisted of construction of original improved pattern trees and reconstruction of initial tree. The experiment results showed that the runtime was saved by about 15% compared with that of CanTree. As the number of transactions increased, the runtime of improved pattern tree was about 25% shorter than that of FP-tree. The improved pattern tree also required less memory than CanTree.

Backward Support Computation Method for Positive and Negative Frequent Itemset Mining

Association rules mining is a major data mining field that leads to discovery of associations and correlations among items in today’s big data environment. The conventional association rule mining focuses mainly on positive itemsets generated from frequently occurring itemsets (PFIS). However, there has been a significant study focused on infrequent itemsets with utilization of negative association rules to mine interesting frequent itemsets (NFIS) from transactions. In this work, we propose an efficient backward calculating negative frequent itemset algorithm namely EBC-NFIS for computing backward supports that can extract both positive and negative frequent itemsets synchronously from dataset. EBC-NFIS algorithm is based on popular e-NFIS algorithm that computes supports of negative itemsets from the supports of positive itemsets. The proposed algorithm makes use of previously computed supports from memory to minimize the computation time. In addition, association rules, i.e. positive and negative association rules (PNARs) are generated from discovered frequent itemsets using EBC-NFIS algorithm. The efficiency of the proposed algorithm is verified by several experiments and comparing results with e-NFIS algorithm. The experimental results confirm that the proposed algorithm successfully discovers NFIS and PNARs and runs significantly faster than conventional e-NFIS algorithm.

A Fast Distributed Algorithm for Association Rule Mining Based on Binary Coding Mapping Relation

Association rule mining is an important issue in data mining. The paper proposed an binary system based method to generate candidate frequent itemsets and corresponding supporting counts efficiently, which needs only some operations such as ＂and＂, ＂or＂ and ＂xor＂. Applying this idea in the existed distributed association rule mining al gorithm FDM, the improved algorithm BFDM is proposed. The theoretical analysis and experiment testify that BFDM is effective and efficient.

AN INCREMENTAL UPDATING ALGORITHM FOR MINING ASSOCIATION RULES

In this letter, on the basis of Frequent Pattern(FP) tree, the support function to update FP-tree is introduced, then an Incremental FP (IFP) algorithm for mining association rules is proposed. IFP algorithm considers not only adding new data into the database but also reducing old data from the database. Furthermore, it can predigest five cases to three cases.The algorithm proposed in this letter can avoid generating lots of candidate items, and it is high efficient.

Elicitation of Association Rules from Information on Customs Offences on the Basis of Frequent Motives

The fight against fraud and trafficking is a fundamental mission of customs. The conditions for carrying out this mission depend both on the evolution of economic issues and on the behaviour of the actors in charge of its implementation. As part of the customs clearance process, customs are nowadays confronted with an increasing volume of goods in connection with the development of international trade. Automated risk management is therefore required to limit intrusive control. In this article, we propose an unsupervised classification method to extract knowledge rules from a database of customs offences in order to identify abnormal behaviour resulting from customs control. The idea is to apply the Apriori principle on the basis of frequent grounds on a database relating to customs offences in customs procedures to uncover potential rules of association between a customs operation and an offence for the purpose of extracting knowledge governing the occurrence of fraud. This mass of often heterogeneous and complex data thus generates new needs that knowledge extraction methods must be able to meet. The assessment of infringements inevitably requires a proper identification of the risks. It is an original approach based on data mining or data mining to build association rules in two steps: first, search for frequent patterns (support >= minimum support) then from the frequent patterns, produce association rules (Trust >= Minimum Trust). The simulations carried out highlighted three main association rules: forecasting rules, targeting rules and neutral rules with the introduction of a third indicator of rule relevance which is the Lift measure. Confidence in the first two rules has been set at least 50%.

An efficient algorithm for mining closed itemsets

This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overheads of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.

Mining φ-Frequent Itemset Using FP-Tree

The problem of association rule mining has gained considerable prominence in the data mining community for its use as an important tool of knowledge discovery from large scale databases. And there has been a spurt of research activities around this problem. However, traditional association rule mining may often derive many rules in which people are uninterested. This paper reports a generalization of association rule mining called φ association rule mining. It allows people to have different interests on different itemsets that arethe need of real application. Also, it can help to derive interesting rules and substantially reduce the amount of rules. An algorithm based on FP tree for mining φ frequent itemset is presented. It is shown by experiments that the proposed methodis efficient and scalable over large databases.

Mining Software Repository for Cleaning Bugs Using Data Mining Technique

Despite advances in technological complexity and efforts,software repository maintenance requires reusing the data to reduce the effort and complexity.However,increasing ambiguity,irrelevance,and bugs while extracting similar data during software development generate a large amount of data from those data that reside in repositories.Thus,there is a need for a repository mining technique for relevant and bug-free data prediction.This paper proposes a fault prediction approach using a data-mining technique to find good predictors for high-quality software.To predict errors in mining data,the Apriori algorithm was used to discover association rules by fixing confidence at more than 40%and support at least 30%.The pruning strategy was adopted based on evaluation measures.Next,the rules were extracted from three projects of different domains;the extracted rules were then combined to obtain the most popular rules based on the evaluation measure values.To evaluate the proposed approach,we conducted an experimental study to compare the proposed rules with existing ones using four different industrial projects.The evaluation showed that the results of our proposal are promising.Practitioners and developers can utilize these rules for defect prediction during early software development.

NIA2: A fast indirect association mining algorithm

Indirect association is a high level relationship between items and frequent item sets in data. There are many potential applications for indirect associations, such as database marketing, intelligent data analysis, web -log analysis, recommended system, etc. Existing indirect association mining algorithms are mostly based on the notion of post - processing of discovery of frequent item sets. In the mining process, all frequent item sets need to be generated first, and then they are fihered and joined to form indirect associations. We have presented an indirect association mining algorithm （NIA） based on anti -monotonicity of indirect associations whereas k candidate indirect associations can be generated directly from k - 1 candidate indirect associations, without all frequent item sets generated. We also use the frequent itempair support matrix to reduce the time and memory space needed by the algorithm. In this paper, a novel algorithm （NIA2） is introduced based on the generation of indirect association patterns between itempairs through one item mediator sets from frequent itempair support matrix. A notion of mediator set support threshold is also presented. NIA2 mines indirect association patterns directly from the dataset, without generating all frequent item sets. The frequent itempair support matrix and the notion of using tm as the support threshold for mediator sets can significantly reduce the cost of joint operations and the search process compared with existing algorithms. Results of experiments on a real - word web log dataset have proved NIA2 one order of magnitude faster than existing algorithms.

Adaptive associative classification with emerging frequent patterns

In this paper, we propose an enhanced associative classification method by integrating the dynamic property in the process of associative classification. In the proposed method, we employ a support vector machine（SVM） based method to refine the discovered emerging ~equent patterns for classification rule extension for class label prediction. The empirical study shows that our method can be used to classify increasing resources efficiently and effectively.

基于Flag-Prefix-Tree的频繁模式挖掘改进算法

稀疏数据集上,条件FP-Tree无法有效压缩且频繁构造开销大,使用伪构造的问题是数据项目未经压缩和过滤导致额外的遍历代价。文章提出了一种简单而新颖的标志前缀树(Flag-Prefix-Tree)和一种新的挖掘稀疏数据集上频繁模式的算法FPT-Mine。通过Flag-Prefix-Tree中的flag,伪构造条件树可以巧妙地过滤不频繁项目。而且flag可以在挖掘过程中递归地重用,只有非常小的开销,但节省了遍历不频繁项目的大量开销。FPT-Mine以自上向下的顺序遍历Flag-Prefix-Tree,并为每个频繁模式创建一个临时根表(Root table)来伪构造条件树,这样就不需要在每个节点上维护父节点和兄弟节点的链接。此外,FPT-Mine在树上应用了合并技术,这使得FlagPrefix-Tree越来越小。研究表明,FPT-Mine在各种稀疏数据集中具有高性能和可扩展性。FPT-Mine在所有测试数据集中的性能都优于FP-growth,当最小支持度阈值降低时,算法之间的差距增大。

频繁项集挖掘研究前沿及展望

频繁项集挖掘是数据挖掘领域的核心任务之一,其目标是发现在数据库中频繁出现的模式。这些模式对于关联规则、分类、异常检测等多个数据挖掘任务都具有重要作用。由于随着项集大小的增加,项集的组合数量呈指数级增长,导致计算复杂性急剧上升,研究人员一直在努力开发高效的算法来解决这一问题。面向频繁项集挖掘的算法、紧凑表示和前沿应用,深入探讨不同技术的的工作原理、优势和局限性,从而对这一领域的研究现状进行全面总结。最后,进一步探讨了该领域的前沿发展趋势,指出计算效率、基于约束的频繁项集挖掘、模式的可解释性以及算法在不同领域的创新应用等未来潜在研究方向。

Efficient Mining of Frequent Closed XML Query Pattern

Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.

关联规则在胸腔闭式引流管非计划拔管事件中的分析应用

目的挖掘住院患者胸腔闭式引流管非计划拔管(UEX)事件发生的关联因素,制订防范策略,降低胸腔闭式引流管UEX发生率。方法回顾性分析本院2018年1月至2021年9月期间上报的156例胸腔闭式引流管UEX事件,采用Apriori算法进行数据挖掘,探讨胸腔闭式引流管UEX事件的关联规则。结果使用χ^(2)检验对得到的关联规则进行有效性评定,最后结合专业知识获取强关联规则11条。住院患者胸腔闭式引流管UEX事件风险因素包括年龄≥60岁、吸烟史、文盲、男性、呼吸系统疾病、内科患者、5~10年护士、二级护理、清醒患者、评估不到位、夜班、管道留置1~5 d、轻度疼痛、床上活动时、敷贴固定、未二次固定、固定松脱。结论通过数据挖掘,深入分析胸腔闭式引流管UEX事件各因素间的关联规则,为胸腔闭式引流管理UEX防范管理体系的构建提供了科学、准确的指导意义。