An information-theoretic approach to combining object models

This paper introduces a new method for combining different object models. By determining a configuration of the models, which maximizes their mutual information, the proposed method creates a unified hypothesis from multiple object models on the fly without prior training. To validate the effectiveness of the proposed method, experiments are conducted in which human faces are detected and localized in images by combining different face models.     

Tree-based partitioning of date for association rule mining

The most computationally demanding aspect of Association Rule Mining is the identification and counting of support of the frequent sets of items that occur together sufficiently often to be the basis of potentially interesting rules. The task increases in difficulty with the scale of the data and also with its density. The greatest challenge is posed by data that is too large to be contained in primary memory, especially when high data density and/or low support thresholds give rise to very large numbers of candidates that must be counted. In this paper, we consider strategies for partitioning the data to deal effectively with such cases. We describe a partitioning approach which organises the data into tree structures that can be processed independently. We present experimental results that show the method scales well for increasing dimensions of data and performs significantly better than alternatives, especially when dealing with dense data and low support thresholds. Shakil Ahmed received a first class BSc (Hons) degree from Dhaka University, Bangladesh, in 1990; and an MSc (first class), also Dhaka University, in 1992. He received his PhD from The University of Liverpool, UK, in 2005. From 2000 onwards he is a member of the Data Mining Group at the Department of Computer Science of the University of Liverpool, UK. His research interests include data mining, Association Rule Mining and pattern recognition. Frans Coenen has been working in the field of Data Mining for many years and has written widely on the subject. He received his PhD from Liverpool Polytechnic in 1989, after which he took up a post as a RA within the Department of Computer Science at the University of Liverpool. In 1997, he took up a lecturing post within the same department. His current Data Mining research interests include Association rule Mining, Classification algorithms and text mining. He is on the programme committee for ICDM'05 and was the chair for the UK KDD symposium (UKKDD'05). Paul Leng is professor of e-Learning at the University of Liverpool and director of the e-Learning Unit, which is responsible for overseeing the University's online degree programmes, leading to degrees of MSc in IT and MBA. Along with e-Learning, his main research interests are in Data Mining, especially in methods of discovering Association Rules. In collaboration with Frans Coenen, he has developed efficient new algorithms for finding frequent sets and is exploring applications in text mining and classification.     

An efficient approach to mining indirect associations

Discovering association rules is one of the important tasks in data mining. While most of the existing algorithms are developed for efficient mining of frequent patterns, it has been noted recently that some of the infrequent patterns, such as indirect associations, provide useful insight into the data. In this paper, we propose an efficient algorithm, called HI-mine, based on a new data structure, called HI-struct, for mining the complete set of indirect associations between items. Our experimental results show that HI-mine's performance is significantly better than that of the previously developed algorithm for mining indirect associations on both synthetic and real world data sets over practical ranges of support specifications.     

An efficient genetic algorithm for automated mining of both positive and negative quantitative association rules

In this paper, a genetic algorithm (GA) is proposed as a search strategy for not only positive but also negative quantitative association rule (AR) mining within databases. Contrary to the methods used as usual, ARs are directly mined without generating frequent itemsets. The proposed GA performs a database-independent approach that does not rely upon the minimum support and the minimum confidence thresholds that are hard to determine for each database. Instead of randomly generated initial population, uniform population that forces the initial population to be not far away from the solutions and distributes it in the feasible region uniformly is used. An adaptive mutation probability, a new operator called uniform operator that ensures the genetic diversity, and an efficient adjusted fitness function are used for mining all interesting ARs from the last population in only single run of GA. The efficiency of the proposed GA is validated upon synthetic and real databases.     

Product portfolio identification based on association rule mining

It has been well recognized that product portfolio planning has far-reaching impact on the company's business success in competition. In general, product portfolio planning involves two main stages, namely portfolio identification and portfolio evaluation and selection. The former aims to capture and understand customer needs effectively and accordingly to transform them into specifications of product offerings. The latter concerns how to determine an optimal configuration of these identified offerings with the objective of achieving best profit performance. Current research and industrial practice have mainly focused on the economic justification of a given product portfolio, whereas the portfolio identification issue has been received only limited attention. This article intends to develop explicit decision support to improve product portfolio identification by efficient knowledge discovery from past sales and product records. As one of the important applications of data mining, association rule mining lends itself to the discovery of useful patterns associated with requirement analysis enacted among customers, marketing folks, and designers. An association rule mining system (ARMS) is proposed for effective product portfolio identification. Based on a scrutiny into the product definition process, the article studies the fundamental issues underlying product portfolio identification. The ARMS differentiates the customer needs from functional requirements involved in the respective customer and functional domains. Product portfolio identification entails the identification of functional requirement clusters in conjunction with the mappings from customer needs to these clusters. While clusters of functional requirements are identified based on fuzzy clustering analysis, the mapping mechanism between the customer and functional domains is incarnated in association rules. The ARMS architecture and implementation issues are discussed in detail. An application of the proposed methodology and system in a consumer electronics company to generate a vibration motor portfolio for mobile phones is also presented.     

基于时间衰减模型的模糊会话关联规则挖掘算法

现有的关联规则挖掘算法没有考虑数据流中会话的非均匀分布特性和历史数据的作用,并且忽略了连续属性处理时的“尖锐边界”问题。针对这些问题,本文提出一种基于时间衰减模型的模糊会话关联规则挖掘算法。首先,针对数据流中会话的非均匀分布特性,基于时间片对会话进行划分,完整的保留了时间片内会话之间的相关性信息;然后,采用模糊集对会话的连续属性进行处理,增加了规则的兴趣度和可理解性;最后,在考虑历史数据作用和允许误差情况的基础上,基于时间衰减模型挖掘数据流中的临界频繁项集和模糊关联规则。实验结果表明,本文方法在提高时间效率、降低冗余率和增加规则兴趣度方面存在明显优势。     

An efficient approach for mining cross-level closed itemsets and minimal association rules using closed itemset lattices

Multilevel knowledge in transactional databases plays a significant role in our real-life market basket analysis. Many researchers have mined the hierarchical association rules and thus proposed various approaches. However, some of the existing approaches produce many multilevel and cross-level association rules that fail to convey quality information. From these large number of redundant association rules, it is extremely difficult to extract any meaningful information. There also exist some approaches that mine minimal association rules, but these have many shortcomings due to their naïve-based approaches. In this paper, we have focused on the need for generating hierarchical minimal rules that provide maximal information. An algorithm has been proposed to derive minimal multilevel association rules and cross-level association rules. Our work has made significant contributions in mining the minimal cross-level association rules, which express the mixed relationship between the generalized and specialized view of the transaction itemsets. We are the first to design an efficient algorithm using a closed itemset lattice-based approach, which can mine the most relevant minimal cross-level association rules. The parent–child relationship of the lattices has been exploited while mining cross-level closed itemset lattices. We have extensively evaluated our proposed algorithm’s efficiency using a variety of real-life datasets and performing a large number of experiments. The proposed algorithm has outperformed the existing related work significantly during the pervasive performance comparison.     

A data mining approach to database compression

Data mining can dig out valuable information from databases to assist a business in approaching knowledge discovery and improving business intelligence. Database stores large structured data. The amount of data increases due to the advanced database technology and extensive use of information systems. Despite the price drop of storage devices, it is still important to develop efficient techniques for database compression. This paper develops a database compression method by eliminating redundant data, which often exist in transaction database. The proposed approach uses a data mining structure to extract association rules from a database. Redundant data will then be replaced by means of compression rules. A heuristic method is designed to resolve the conflicts of the compression rules. To prove its efficiency and effectiveness, the proposed approach is compared with two other database compression methods. Chin-Feng Lee is an associate professor with the Department of Information Management at Chaoyang University of Technology, Taiwan, R.O.C. She received her M.S. and Ph.D. degrees in 1994 and 1998, respectively, from the Department of Computer Science and Information Engineering at National Chung Cheng University. Her current research interests include database design, image processing and data mining techniques. S. Wesley Changchien is a professor with the Institute of Electronic Commerce at National Chung-Hsing University, Taiwan, R.O.C. He received a BS degree in Mechanical Engineering (1989) and completed his MS (1993) and Ph.D. (1996) degrees in Industrial Engineering at State University of New York at Buffalo, USA. His current research interests include electronic commerce, internet/database marketing, knowledge management, data mining, and decision support systems. Jau-Ji Shen received his Ph.D. degree in Information Engineering and Computer Science from National Taiwan University at Taipei, Taiwan in 1988. From 1988 to 1994, he was the leader of the software group in Institute of Aeronautic, Chung-Sung Institute of Science and Technology. He is currently an associate professor of information management department in the National Chung Hsing University at Taichung. His research areas focus on the digital multimedia, database and information security. His current research areas focus on data engineering, database techniques and information security. Wei-Tse Wang received the B.A. (2001) and M.B.A (2003) degrees in Information Management at Chaoyang University of Technology, Taiwan, R.O.C. His research interests include data mining, XML, and database compression.     

Using association rules to mine for strong approximate dependencies

In this paper we deal with the problem of mining for approximate dependencies (AD) in relational databases. We introduce a definition of AD based on the concept of association rule, by means of suitable definitions of the concepts of item and transaction. This definition allow us to measure both the accuracy and support of an AD. We provide an interpretation of the new measures based on the complexity of the theory (set of rules) that describes the dependence, and we employ this interpretation to compare the new measures with existing ones. A methodology to adapt existing association rule mining algorithms to the task of discovering ADs is introduced. The adapted algorithms obtain the set of ADs that hold in a relation with accuracy and support greater than user-defined thresholds. The experiments we have performed show that our approach performs reasonably well over large databases with real-world data.     

Large-scale regulatory network analysis from microarray data: modified Bayesian network learning and association rule mining

We present two algorithms for learning large-scale gene regulatory networks from microarray data: a modified information-theory-based Bayesian network algorithm and a modified association rule algorithm. Simulation-based evaluation using six datasets indicated that both algorithms outperformed their unmodified counterparts, especially when analyzing large numbers of genes. Both algorithms learned about 20% (50% if directionality and relation type were not considered) of the relations in the actual models. In our empirical evaluation based on two real datasets, domain experts evaluated subsets of learned relations with high confidence and identified 20–30% to be “interesting” or “maybe interesting” as potential experiment hypotheses.     

Privacy-preserving algorithms for distributed mining of frequent itemsets

Standard algorithms for association rule mining are based on identification of frequent itemsets. In this paper, we study how to maintain privacy in distributed mining of frequent itemsets. That is, we study how two (or more) parties can find frequent itemsets in a distributed database without revealing each party’s portion of the data to the other. The existing solution for vertically partitioned data leaks a significant amount of information, while the existing solution for horizontally partitioned data only works for three parties or more. In this paper, we design algorithms for both vertically and horizontally partitioned data, with cryptographically strong privacy. We give two algorithms for vertically partitioned data; one of them reveals only the support count and the other reveals nothing. Both of them have computational overheads linear in the number of transactions. Our algorithm for horizontally partitioned data works for two parties and above and is more efficient than the existing solution.     

基于量化相关模式的多值关联规则挖掘算法

为了解决多值关联规则挖掘中忽视罕见且有价值的非频繁模式的问题,提出了一种新的多值关联规则挖掘算法-QCoMine.该算法引入了量化相关模式的概念,通过考察多值属性间互信息熵和全置信度,找到具有强信息关系的属性集进而产生规则.实验结果表明,由于在属性层和区间层进行了剪枝,因此缩减了搜索空间,提高了算法的性能,且得到更高置信度、更有价值的规则.     

An evolutionary algorithm to discover quantitative association rules from huge databases without the need for an a priori discretization

Association rules are one of the most frequently used tools for finding relationships between different attributes in a database. There are various techniques for obtaining these rules, the most common of which are those which give categorical association rules. However, when we need to relate attributes which are numeric and discrete, we turn to methods which generate quantitative association rules, a far less studied method than the above. In addition, when the database is extremely large, many of these tools cannot be used. In this paper, we present an evolutionary tool for finding association rules in databases (both small and large) comprising quantitative and categorical attributes without the need for an a priori discretization of the domain of the numeric attributes. Finally, we evaluate the tool using both real and synthetic databases.     

分布式抽样关联规则挖掘算法的研究

介绍了假日旅游信息数据挖掘的概念,提出了一种改进的分布式抽样关联规则挖掘算法DS-ARM,给出了算法的实现过程,并对算法性能进行了测试,利用DS-ARM算法对假日旅游者在目的地的旅游行为模式进行了研究。     

A novel approach to adaptive relational association rule mining

The paper focuses on the adaptive relational association rule mining problem. Relational association rules represent a particular type of association rules which describe frequent relations that occur between the features characterizing the instances within a data set. We aim at re-mining an object set, previously mined, when the feature set characterizing the objects increases. An adaptive relational association rule method, based on the discovery of interesting relational association rules, is proposed. This method, called ARARM (Adaptive Relational Association Rule Mining) adapts the set of rules that was established by mining the data before the feature set changed, preserving the completeness. We aim to reach the result more efficiently than running the mining algorithm again from scratch on the feature-extended object set. Experiments testing the method's performance on several case studies are also reported. The obtained results highlight the efficiency of the ARARM method and confirm the potential of our proposal.     

Novel measurement for mining effective association rules

Mining association rules are widely studied in data mining society. In this paper, we analyze the measure method of support–confidence framework for mining association rules, from which we find it tends to mine many redundant or unrelated rules besides the interesting ones. In order to ameliorate the criterion, we propose a new method of match as the substitution of confidence. We analyze in detail the property of the proposed measurement. Experimental results show that the generated rules by the improved method reveal high correlation between the antecedent and the consequent when the rules were compared with that produced by the support–confidence framework. Furthermore, the improved method decreases the generation of redundant rules.     

Efficient algorithms for distortion and blocking techniques in association rule hiding

Data mining provides the opportunity to extract useful information from large databases. Various techniques have been proposed in this context in order to extract this information in the most efficient way. However, efficiency is not our only concern in this study. The security and privacy issues over the extracted knowledge must be seriously considered as well. By taking this into consideration, we study the procedure of hiding sensitive association rules in binary data sets by blocking some data values and we present an algorithm for solving this problem. We also provide a fuzzification of the support and the confidence of an association rule in order to accommodate for the existence of blocked/unknown values. In addition, we quantitatively compare the proposed algorithm with other already published algorithms by running experiments on binary data sets, and we also qualitatively compare the efficiency of the proposed algorithm in hiding association rules. We utilize the notion of border rules, by putting weights in each rule, and we use effective data structures for the representation of the rules so as (a) to minimize the side effects created by the hiding process and (b) to speed up the selection of the victim transactions. Finally, we study the overall security of the modified database, using the C4.5 decision tree algorithm of the WEKA data mining tool, and we discuss the advantages and the limitations of blocking.     

Artificial intelligence for BIM content management and delivery: Case study of association rule mining for construction detailing

The proliferation of Building Information Modeling (BIM) applications, in tandem with the extensive variation of building products, pose new demands on design and engineering firms to efficiently manage and reuse BIM content (i.e., data-rich parametric model objects and assembly details). Tasks such as classifying BIM objects, indexing them with meta-data (e.g., category), and searching digital libraries to load objects into models still plague practice with inefficient manual workflows. This research aims to improve the productivity of BIM content management and retrieval by developing an AI-backed BIM content recommender system. Using data from a case-study firm, this research extracted content from over 30,000 technical BIM views (e.g., plans, sections, details) in historical projects to build an unsupervised machine-learning prototype with association rule mining. This prototype explicated the strength of relationships among co-occurring BIM objects. Using this prototype as the backbone AI-engine in live BIM sessions, this research developed a context-aware recommender system that dynamically provides BIM users with a set of objects associable with their modeling context (e.g., type of view, existing objects in the model) and human–computer interactions (e.g., objects selected by the user). By mining association data from hundreds of historical projects, this development marks a departure from the existing prototypes that rely on explicit coding, recurring user input, or subjective ratings to recommend BIM content to users. The simulation and experimental implementation of this recommender system yielded high efficacy in predicting content needs and achieved significant savings in the time spent on conventional BIM workflows.     

Preserving privacy in association rule mining with bloom filters

Privacy preserving association rule mining has been an active research area since recently. To this problem, there have been two different approaches—perturbation based and secure multiparty computation based. One drawback of the perturbation based approach is that it cannot always fully preserve individual’s privacy while achieving precision of mining results. The secure multiparty computation based approach works only for distributed environment and needs sophisticated protocols, which constrains its practical usage. In this paper, we propose a new approach for preserving privacy in association rule mining. The main idea is to use keyed Bloom filters to represent transactions as well as data items. The proposed approach can fully preserve privacy while maintaining the precision of mining results. The tradeoff between mining precision and storage requirement is investigated. We also propose δ-folding technique to further reduce the storage requirement without sacrificing mining precision and running time.     

一种基于Apriori的动态关联规则挖掘方法

文章介绍了一种动态关联规则的挖掘方法，该方法的核心思想是仅使用更新的事务和前面阶段的挖掘结果，用Apriori类算法作为局部过程来产生频集，并给出了具体的动态挖掘算法。