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.

Frequent item sets mining from high-dimensional dataset based on a novel binary particle swarm optimization

A novel binary particle swarm optimization for frequent item sets mining from high-dimensional dataset(BPSO-HD) was proposed, where two improvements were joined. Firstly, the dimensionality reduction of initial particles was designed to ensure the reasonable initial fitness, and then, the dynamically dimensionality cutting of dataset was built to decrease the search space. Based on four high-dimensional datasets, BPSO-HD was compared with Apriori to test its reliability, and was compared with the ordinary BPSO and quantum swarm evolutionary(QSE) to prove its advantages. The experiments show that the results given by BPSO-HD is reliable and better than the results generated by BPSO and QSE.

Mining association rule efficiently based on data warehouse

The conventional complete association rule set was replaced by the least association rule set in data warehouse association rule mining process. The least association rule set should comply with two requirements: 1) it should be the minimal and the simplest association rule set; 2) its predictive power should in no way be weaker than that of the complete association rule set so that the precision of the association rule set analysis can be guaranteed. By adopting the least association rule set, the pruning of weak rules can be effectively carried out so as to greatly reduce the number of frequent itemset, and therefore improve the mining efficiency. Finally, based on the classical Apriori algorithm, the upward closure property of weak rules is utilized to develop a corresponding efficient algorithm.

Improvement of Mining Fuzzy Multiple-Level Association Rules from Quantitative Data

Data-mining techniques have been developed to turn data into useful task-oriented knowledge. Most algorithms for mining association rules identify relationships among transactions using binary values and find rules at a single-concept level. Extracting multilevel association rules in transaction databases is most commonly used in data mining. This paper proposes a multilevel fuzzy association rule mining model for extraction of implicit knowledge which stored as quantitative values in transactions. For this reason it uses different support value at each level as well as different membership function for each item. By integrating fuzzy-set concepts, data-mining technologies and multiple-level taxonomy, our method finds fuzzy association rules from transaction data sets. This approach adopts a top-down progressively deepening approach to derive large itemsets and also incorporates fuzzy boundaries instead of sharp boundary intervals. Comparing our method with previous ones in simulation shows that the proposed method maintains higher precision, the mined rules are closer to reality, and it gives ability to mine association rules at different levels based on the user’s tendency as well.

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.

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 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.

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.

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.

Mining item-item and between-set correlated association rules

To overcome the failure in eliminating suspicious patterns or association rules existing in traditional association rules mining, we propose a novel method to mine item-item and between-set correlated association rules. First, we present three measurements: the association, correlation, and item-set correlation measurements. In the association measurement, the all-confidence measure is used to filter suspicious cross-support patterns, while the all-item-confidence measure is applied in the correlation measurement to eliminate spurious association rules that contain negatively correlated items. Then, we define the item-set correlation measurement and show its corresponding properties. By using this measurement, spurious association rules in which the antecedent and consequent item-sets are negatively correlated can be eliminated. Finally, we propose item-item and between-set correlated association rules and two mining algorithms, I&ISCoMine_AP and I&ISCoMine_CT. Experimental results with synthetic and real retail datasets show that the proposed method is effective and valid.

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.

Association Rule Mining and Its Application

Several algorithms in data mining technique have been studied recently, among which association is one of the most important techniques. In this paper, we introduce theory of association rule in data mining, and analyze the characteristics of postal EMS service. We create a data warehouse model for EMS services and give the procedure of applying association rule mining based on it. In the end, we give an example of the whole mining procedure. This EMS Data warehouse model and association rule mining technique have been applied in a practical Postal CRM System.

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.

Multi-Scaling Sampling： An Adaptive Sampling Method for Discovering Approximate Association Rules

One of the obstacles of the efficient association rule mining is theexplosive expansion of data sets since it is costly or impossible to scan large databases, esp., formultiple times. A popular solution to improve the speed and scalability of the association rulemining is to do the algorithm on a random sample instead of the entire database. But how toeffectively define and efficiently estimate the degree of error with respect to the outcome of thealgorithm, and how to determine the sample size needed are entangling researches until now. In thispaper, an effective and efficient algorithm is given based on the PAC (Probably Approximate Correct)learning theory to measure and estimate sample error. Then, a new adaptive, on-line, fast samplingstrategy - multi-scaling sampling - is presented inspired by MRA (Multi-Resolution Analysis) andShannon sampling theorem, for quickly obtaining acceptably approximate association rules atappropriate sample size. Both theoretical analysis and empirical study have showed that the Samplingstrategy can achieve a very good speed-accuracy trade-off.

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 filtered 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 t_m 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.

基于隐结构模型和频繁项集的针刺治疗慢性前列腺炎辨证取穴规律

目的:探讨针刺治疗慢性前列腺炎的辨证取穴规律,为临床治疗慢性前列腺炎提供帮助。方法:检索国家知识基础设施数据库(CNKI)、中文科技期刊数据库(CCD)等数据库中关于针刺辨证论治慢性前列腺炎的文献,构建包含症状、证型、穴位处方的慢性前列腺炎病历数据库,运用隐结构模型分析、频繁项集等方法,分析针刺治疗慢性前列腺炎的辨证取穴规律。结果:共纳入文献64篇,涉及穴位91个,症状248项。高频穴位如三阴交、中极等;高频症状包括舌体瘀点瘀斑、苔黄腻、滴白、尿急等;构建隐结构模型,得出慢性前列腺炎主要证型有湿热下注、肾阳不足等;挖掘出症状-穴位频繁项集、症状-证型-穴位频繁项集各4项。症状-穴位频繁项集如“尿急+滴白+阳痿+早泄+肾俞+足三里”,症状-证型-穴位频繁项集如“尿频+尿急+苔黄腻+滴白+舌体瘀点瘀斑+湿热瘀阻+三阴交+会阴”,提示治疗时可根据相应症状判定证型及选择对应穴位。结论:针刺治疗慢性前列腺炎多以三阴交、中极、关元等为主要穴位,穴位配伍依据临床情况辨证选穴,此可为临床治疗慢性前列腺炎提供参考。

扩展WIT-树融合Diffset策略的频繁加权项集快速挖掘算法

针对当前算法从加权项事务数据库挖掘频繁加权项集(FWI)时效率不高的问题,提出了一种基于加权项集-Tidset树结构的FWI快速挖掘算法。首先,提出了一种加权项集-Tidset树结构;然后,使用最小加权项集阈值和向下闭合性质修剪非频繁节点;最后,利用Diffset策略允许以内存有效方式快速计算项集的加权支持度。实验结果表明,当输入数据库中FWI数较大时,提出的算法明显降低了FWI挖掘时间。相比基于先验的算法,算法平均可节省99.37%的耗时;相比基于位矩阵的加权频繁项集生成算法,提出的算法可节省99.06%的耗时,明显提升了频繁加权项集挖掘效率。

基于隐结构模型与频繁项集探讨特发性肺纤维化的辨证用药规律

目的:探讨中医治疗特发性肺纤维化(IPF)的辨证用药规律,为临床治疗IPF提供参考。方法:在中国知网、万方数据知识服务平台、PubMed、Embase等数据库中,检索建库至2021年8月8日辨证应用中药汤剂治疗IPF的相关文献,提取证型、症状及中药处方信息,构建IPF医案数据库,采用隐结构模型、频繁项集等数据挖掘方法分析中药汤剂内服治疗IPF的辨证用药规律。结果:共纳入文献39篇,包含病例1497例。纳入文献共包含症状163个,如咳嗽、乏力、气短等,将频次3的53个症状作为显变量构建IPF的隐结构模型,该模型提示气虚血瘀是IPF的常见证型。纳入文献包含的处方中共涉及中药163味,其中高频药物包括黄芪、甘草、丹参、当归、党参等;挖掘出“症状-中药”频繁项集5项,如“胸痛乏力+舌有瘀斑+脉沉细+丹参+桃仁+党参”;“证型-症状-中药”频繁项集4项,如“气虚血瘀+胸闷乏力+舌有瘀斑+黄芪+丹参+当归”。结论:气虚血瘀是IPF的临床常见证型,中药汤剂治疗IPF多以黄芪、甘草、丹参为主要药物,药物配伍根据临床辨证选择。