Actionable high-coherent-utility fuzzy itemset mining

Many fuzzy data mining approaches have been proposed for finding fuzzy association rules with the predefined minimum support from quantitative transaction databases. Since each item has its own utility, utility itemset mining has become increasingly important. However, common problems with existing approaches are that an appropriate minimum support is difficult to determine and that the derived rules usually expose common-sense knowledge, which may not be interesting from a business point of view. This study thus proposes an algorithm for mining high-coherent-utility fuzzy itemsets to overcome problems with the properties of propositional logic. Quantitative transactions are first transformed into fuzzy sets. Then, the utility of each fuzzy itemset is calculated according to the given external utility table. If the value is larger than or equal to the minimum utility ratio, the itemset is considered as a high-utility fuzzy itemset. Finally, contingency tables are calculated and used for checking whether a high-utility fuzzy itemset satisfies four criteria. If so, it is a high-coherent-utility fuzzy itemset. Experiments on the foodmart and simulated datasets are made to show that the derived itemsets by the proposed algorithm not only can reach better profit than selling them separately, but also can provide fewer but more useful utility itemsets for decision-makers.     

基于多最小支持度的多层模糊关联规则挖掘

为了在事务数据库中发现关联规则,在现实挖掘应用中,经常采用不同的标准去判断不同项目的重要性,管理项目之间的分类关系和处理定量数据集这3个方法去处理问题,因此提出一个在定量事务数据库中采用多最小支持度,在项目集中获取隐含知识的多层模糊关联规则挖掘算法。该挖掘算法使用两种支持度约束和至上而下逐步细化的方法推导出频繁项集,同时可以发现交叉层次的模糊关联规则。通过实例证明了该挖掘算法在多最小支持度约束下推导出的多层模糊关联规则是易于理解和有意义的,具有很好的效率和伸缩性。     

A genetic-fuzzy mining approach for items with multiple minimum supports

Data mining is the process of extracting desirable knowledge or interesting patterns from existing databases for specific purposes. Mining association rules from transaction data is most commonly seen among the mining techniques. Most of the previous mining approaches set a single minimum support threshold for all the items and identify the relationships among transactions using binary values. In the past, we proposed a genetic-fuzzy data-mining algorithm for extracting both association rules and membership functions from quantitative transactions under a single minimum support. In real applications, different items may have different criteria to judge their importance. In this paper, we thus propose an algorithm which combines clustering, fuzzy and genetic concepts for extracting reasonable multiple minimum support values, membership functions and fuzzy association rules from quantitative transactions. It first uses the k-means clustering approach to gather similar items into groups. All items in the same cluster are considered to have similar characteristics and are assigned similar values for initializing a better population. Each chromosome is then evaluated by the criteria of requirement satisfaction and suitability of membership functions to estimate its fitness value. Experimental results also show the effectiveness and the efficiency of the proposed approach.     

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

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

An improved approach to find membership functions and multiple minimum supports in fuzzy data mining

Fuzzy mining approaches have recently been discussed for deriving fuzzy knowledge. Since items may have their own characteristics, different minimum supports and membership functions may be specified for different items. In the past, we proposed a genetic-fuzzy data-mining algorithm for extracting minimum supports and membership functions for items from quantitative transactions. In that paper, minimum supports and membership functions of all items are encoded in a chromosome such that it may be not easy to converge. In this paper, an enhanced approach is proposed, which processes the items in a divide-and-conquer strategy. The approach is called divide-and-conquer genetic-fuzzy mining algorithm for items with Multiple Minimum Supports (DGFMMS), and is designed for finding minimum supports, membership functions, and fuzzy association rules. Possible solutions are evaluated by their requirement satisfaction divided by their suitability of derived membership functions. The proposed GA framework maintains multiple populations, each for one item’s minimum support and membership functions. The final best minimum supports and membership functions in all the populations are then gathered together to be used for mining fuzzy association rules. Experimental results also show the effectiveness of the proposed approach.     

A GA-based Fuzzy Mining Approach to Achieve a Trade-off Between Number of Rules and Suitability of Membership Functions

Data mining is most commonly used in attempts to induce association rules from transaction data. Transactions in real-world applications, however, usually consist of quantitative values. This paper thus proposes a fuzzy data-mining algorithm for extracting both association rules and membership functions from quantitative transactions. We present a GA-based framework for finding membership functions suitable for mining problems and then use the final best set of membership functions to mine fuzzy association rules. The fitness of each chromosome is evaluated by the number of large 1-itemsets generated from part of the previously proposed fuzzy mining algorithm and by the suitability of the membership functions. Experimental results also show the effectiveness of the framework.     

Genetic-Fuzzy Data Mining With Divide-and-Conquer Strategy

Data mining is most commonly used in attempts to induce association rules from transaction data. Most previous studies focused on binary-valued transaction data. Transaction data in real-world applications, however, usually consist of quantitative values. This paper, thus, proposes a fuzzy data-mining algorithm for extracting both association rules and membership functions from quantitative transactions. A genetic algorithm (GA)-based framework for finding membership functions suitable for mining problems is proposed. The fitness of each set of membership functions is evaluated by the fuzzy-supports of the linguistic terms in the large 1-itemsets and by the suitability of the derived membership functions. The evaluation by the fuzzy supports of large 1-itemsets is much faster than that when considering all itemsets or interesting association rules. It can also help divide-and-conquer the derivation process of the membership functions for different items. The proposed GA framework, thus, maintains multiple populations, each for one item's membership functions. The final best sets of membership functions in all the populations are then gathered together to be used for mining fuzzy association rules. Experiments are conducted to analyze different fitness functions and set different fitness functions and setting different supports and confidences. Experiments are also conducted to compare the proposed algorithm, the one with uniform fuzzy partition, and the existing one without divide-and-conquer, with results validating the performance of the proposed algorithm.     

Genetic-fuzzy mining with multiple minimum supports based on fuzzy clustering

Data mining is the process of extracting desirable knowledge or interesting patterns from existing databases for specific purposes. Most of the previous approaches set a single minimum support threshold for all the items and identify the relationships among transactions using binary values. In real applications, different items may have different criteria to judge their importance. In the past, we proposed an algorithm for extracting appropriate multiple minimum support values, membership functions and fuzzy association rules from quantitative transactions. It used requirement satisfaction and suitability of membership functions to evaluate fitness values of chromosomes. The calculation for requirement satisfaction might take a lot of time, especially when the database to be scanned could not be totally fed into main memory. In this paper, an enhanced approach, called the fuzzy cluster-based genetic-fuzzy mining approach for items with multiple minimum supports (FCGFMMS), is thus proposed to speed up the evaluation process and keep nearly the same quality of solutions as the previous one. It divides the chromosomes in a population into several clusters by the fuzzy k-means clustering approach and evaluates each individual according to both their cluster and their own information. Experimental results also show the effectiveness and the efficiency of the proposed approach.     

Utilizing Genetic Algorithms to Optimize Membership Functions for Fuzzy Weighted Association Rules Mining

It is not an easy task to know a priori the most appropriate fuzzy sets that cover the domains of quantitative attributes for fuzzy association rules mining. In general, it is unrealistic that experts can always provide such sets. And finding the most appropriate fuzzy sets becomes a more complex problem when items are not considered to have equal importance and the support and confidence parameters required for the association rules mining process are specified as linguistic terms. Existing clustering based automated methods are not satisfactory because they do not consider the optimization of the discovered membership functions. In order to tackle this problem, we propose Genetic Algorithms (GAs) based clustering method, which dynamically adjusts the fuzzy sets to provide maximum profit based on user specified linguistic minimum support and confidence terms. This is achieved by tuning the base values of the membership functions for each quantitative attribute with respect to two different evaluation functions maximizing the number of large itemsets and the average of the confidence intervals of the generated rules. To the best of our knowledge, this is the first effort in this direction. Experiments conducted on 100 K transactions from the adult database of United States census in year 2000 demonstrate that the proposed clustering method exhibits good performance in terms of the number of produced large itemsets and interesting association rules.     

Multi-objective genetic algorithms based automated clustering for fuzzy association rules mining

Researchers realized the importance of integrating fuzziness into association rules mining in databases with binary and quantitative attributes. However, most of the earlier algorithms proposed for fuzzy association rules mining either assume that fuzzy sets are given or employ a clustering algorithm, like CURE, to decide on fuzzy sets; for both cases the number of fuzzy sets is pre-specified. In this paper, we propose an automated method to decide on the number of fuzzy sets and for the autonomous mining of both fuzzy sets and fuzzy association rules. We achieve this by developing an automated clustering method based on multi-objective Genetic Algorithms (GA); the aim of the proposed approach is to automatically cluster values of a quantitative attribute in order to obtain large number of large itemsets in less time. We compare the proposed multi-objective GA based approach with two other approaches, namely: 1) CURE-based approach, which is known as one of the most efficient clustering algorithms; 2) Chien et al. clustering approach, which is an automatic interval partition method based on variation of density. Experimental results on 100 K transactions extracted from the adult data of USA census in year 2000 showed that the proposed automated clustering method exhibits good performance over both CURE-based approach and Chien et al.’s work in terms of runtime, number of large itemsets and number of association rules.     

Mining association rules from quantitative data

Data-mining is the process of extracting desirable knowledge or interesting patterns from existing databases for specific purposes. Most conventional data-mining algorithms identify the relationships among transactions using binary values, however, transactions with quantitative values are commonly seen in real-world applications. This paper thus proposes a new data-mining algorithm for extracting interesting knowledge from transactions stored as quantitative values. The proposed algorithm integrates fuzzy set concepts and the apriori mining algorithm to find interesting fuzzy association rules in given transaction data sets. Experiments with student grades at I-Shou University were also made to verify the performance of the proposed algorithm.     

Mining Fuzzy Multiple-Level Association Rules from Quantitative Data

Machine-learning and 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. Transactions with quantitative values and items with hierarchical relationships are, however, commonly seen in real-world applications. This paper proposes a fuzzy multiple-level mining algorithm for extracting knowledge implicit in transactions stored as quantitative values. The proposed algorithm adopts a top-down progressively deepening approach to finding large itemsets. It integrates fuzzy-set concepts, data-mining technologies and multiple-level taxonomy to find fuzzy association rules from transaction data sets. Each item uses only the linguistic term with the maximum cardinality in later mining processes, thus making the number of fuzzy regions to be processed the same as the number of original items. The algorithm therefore focuses on the most important linguistic terms for reduced time complexity.     

Determining membership functions and minimum fuzzy support in finding fuzzy association rules for classification problems

This paper propose a new method, that employs the genetic algorithm, to find fuzzy association rules for classification problems based on an effective method for discovering the fuzzy association rules, namely the fuzzy grids based rules mining algorithm (FGBRMA). It is considered that some important parameters, including the number and shapes of membership functions in each quantitative attribute and the minimum fuzzy support, are not easily user-specified. Thus, the above-mentioned parameters are automatically determined by a binary string or chromosome is composed of two substrings: one for each quantitative attribute by the coding method proposed by Ishibuchi and Murata, and the other for the minimum fuzzy support. In each generation, the fitness value, which maximizes the classification accuracy rate and minimizes the number of fuzzy rules, of each chromosome can be obtained. When reaching the termination condition, a chromosome with maximum fitness value is then used to test its performance. For classification generalization ability, the simulation results from the iris data and the appendicitis data demonstrate that proposed method performs well in comparison with other classification methods.     

一种矩阵和排序索引关联规则数据挖掘算法

在关联规则挖掘算法中,Apriori由于多次对数据库进行扫描会产生较多的候选集,在多次扫描数据库的情况下容易产生I/O开销问题,并引起数据挖掘效率低.矩阵关联规则在数据挖掘过程中没有删除非频繁项集,致使存在较多的无效扫描,对于挖掘效率的提高也不明显.该文提出了一种改进的矩阵和排序索引关联规则数据挖掘算法,首先,删除不需...     

一种基于倒排索引树的增量更新关联挖掘算法

增量更新关联规则挖掘主要解决事务数据库中交易记录不断更新和最小支持度发生变化时关联规则的维护问题。针对目前诸多增量更新关联规则挖掘算法存在效率低、计算成本高、规则难以维护等问题,提出一种基于倒排索引树的增量更新关联挖掘算法。该算法有效地将倒排索引技术与树型结构相结合,使得交易数据库中的数据不断更新和最小支持度随应用环境不同而不断改变时,以实现无需扫描原始交易数据库和不产生候选项集的情况下生成频繁项集。实验结果表明,该算法只需占用较小的存储空间、且检索项集的效率较高,能高效地解决增量更新关联规则难以维护的问题。     

Using a hash-based method with transaction trimming for miningassociation rules

We examine the issue of mining association rules among items in a large database of sales transactions. Mining association rules means that, given a database of sales transactions, to discover all associations among items such that the presence of some items in a transaction will imply the presence of other items in the same transaction. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items that appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying, within this candidate set, these itemsets that meet the large itemset requirement. Generally, this is done iteratively for each large k-itemset in increasing order of k, where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate sets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we develop an effective algorithm for the candidate set generation. It is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. The advantage of the proposed algorithm also provides us the opportunity of reducing the amount of disk I/O required. An extensive simulation study is conducted to evaluate performance of the proposed algorithm     

一种基于事务修剪的约束关联规则的挖掘算法

针对一类常见而简单的规则中有项或缺项的约束,提出了一种基于事务数据修剪的约束关联规则的快速挖掘算法。该算法先扫描一遍数据库对事务进行水平和纵向的修剪,接着在修剪后的数据集上挖掘频繁项集,形成规则的候选头集、体集和规则项集,最后一次扫描后由最小可信度约束得到所要求的关联规则。实验表明,与按简洁约束采取的一般策略相比,该算法的性能有较明显的提高。     

一种发现模糊关联规则的FTDA2算法

模糊关联规则在模糊集理论的基础上发现关联规则,频繁项集挖掘是数据挖掘的关键问题。Apriori算法在查找频繁项集时,需要对数据库进行多次扫描,通过模式匹配检查一个很大的候选集合,降低了算法执行效率。针对该问题提出FTDA2算法,该算法对事务数据库进行一次扫描,记录对计算频繁项集支持度有贡献的事务。比较FTDA2算法与其他算法,通过实验证明其有效性。     

Mining fuzzy sequential patterns from quantitative transactions

Many researchers in database and machine learning fields are primarily interested in data mining because it offers opportunities to discover useful information and important relevant patterns in large databases. Most previous studies have shown how binary valued transaction data may be handled. Transaction data in real-world applications usually consist of quantitative values, so designing a sophisticated data-mining algorithm able to deal with various types of data presents a challenge to workers in this research field. In the past, we proposed a fuzzy data-mining algorithm to find association rules. Since sequential patterns are also very important for real-world applications, this paper thus focuses on finding fuzzy sequential patterns from quantitative data. A new mining algorithm is proposed, which integrates the fuzzy-set concepts and the AprioriAll algorithm. It first transforms quantitative values in transactions into linguistic terms, then filters them to find sequential patterns by modifying the AprioriAll mining algorithm. Each quantitative item uses only the linguistic term with the maximum cardinality in later mining processes, thus making the number of fuzzy regions to be processed the same as the number of the original items. The patterns mined out thus exhibit the sequential quantitative regularity in databases and can be used to provide some suggestions to appropriate supervisors.     

一种快速挖掘约束性关联规则的算法

提出一种快速挖掘约束性关联规则的算法,其适用于挖掘带约束条件的频繁项目集.该算法通过数字区间的数值自动递减产生候选频繁项,并用二进制的逻辑操作计算支持数和用数字特征减少扫描事务的个数.算法的原理简单有效,能够有效减少扫描的时间和产生候选频繁项的时间,与现有的约束性关联规则挖掘算法和基于二进制的挖掘算法相比,其效率得到明显提高.