Mining maximal hyperclique pattern: A hybrid search strategy

A hyperclique pattern is a new type of association pattern that contains items which are highly affiliated with each other. Specifically, the presence of an item in one transaction strongly implies the presence of every other item that belongs to the same hyperclique pattern. In this paper, we present an algorithm for mining maximal hyperclique patterns, which specifies a more compact representation of hyperclique patterns and are desirable for many applications, such as pattern-based clustering. Our algorithm exploits key advantages of both the Depth First Search (DFS) strategy and the Breadth First Search (BFS) strategy. Indeed, we adapt the equivalence pruning method, one of the most efficient pruning methods of the DFS strategy, into the process of the BFS strategy. Our experimental results show that the performance of our algorithm can be orders of magnitude faster than standard maximal frequent pattern mining algorithms, particularly at low levels of support.     

On the strength of hyperclique patterns for text categorization

The use of association patterns for text categorization has attracted great interest and a variety of useful methods have been developed. However, the key characteristics of pattern-based text categorization remain unclear. Indeed, there are still no concrete answers for the following two questions: Firstly, what kind of association pattern is the best candidate for pattern-based text categorization? Secondly, what is the most desirable way to use patterns for text categorization? In this paper, we focus on answering the above two questions. More specifically, we show that hyperclique patterns are more desirable than frequent patterns for text categorization. Along this line, we develop an algorithm for text categorization using hyperclique patterns. As demonstrated by our experimental results on various real-world text documents, our method provides much better computational performance than state-of-the-art methods while retaining classification accuracy.     

Tree pattern mining with tree automata constraints

Most work on pattern mining focuses on simple data structures such as itemsets and sequences of itemsets. However, a lot of recent applications dealing with complex data like chemical compounds, protein structures, XML and Web log databases and social networks, require much more sophisticated data structures such as trees and graphs. In these contexts, interesting patterns involve not only frequent object values (labels) appearing in the graphs (or trees) but also frequent specific topologies found in these structures. Recently, several techniques for tree and graph mining have been proposed in the literature. In this paper, we focus on constraint-based tree pattern mining. We propose to use tree automata as a mechanism to specify user constraints over tree patterns. We present the algorithm CoBMiner which allows user constraints specified by a tree automata to be incorporated in the mining process. An extensive set of experiments executed over synthetic and real data (XML documents and Web usage logs) allows us to conclude that incorporating constraints during the mining process is far more effective than filtering the interesting patterns after the mining process.     

Mining frequent patterns with the pattern tree

Mining frequent patterns with a frequent pattern tree (FP-tree in short) avoids costly candidate generation and repeatedly occurrence frequency checking against the support threshold. It therefore achieves much better performance and efficiency than Apriori-like algorithms. However, the database still needs to be scanned twice to get the FP-tree. This can be very time-consuming when new data is added to an existing database because two scans may be needed for not only the new data but also the existing data. In this research we propose a new data structure, the pattern tree (P-tree in short), and a new technique, which can get the P-tree through only one scan of the database and can obtain the corresponding FP-tree with a specified support threshold. Updating a P-tree with new data needs one scan of the new data only, and the existing data does not need to be re-scanned. Our experiments show that the P-tree method outperforms the FP-tree method by a factor up to an order of magnitude in large datasets. A preliminary version of this paper has been published in theProceedings of the 2002 IEEE International Conference on Data Mining (ICDM ’02), 629–632. Hao Huang: He is pursuing his Ph.D. degree in the Department of Computer Science at the University of Virginia. His research interests are Gird Computing, Data Mining and their applications in Bioinformatics. He received his M.S. in Computer Science from Colorado School of Mines in 2001. Xindong Wu, Ph.D.: He is Professor and Chair of the Department of Computer Science at the University of Vermont, USA. He holds a Ph.D. in Artificial Intelligence from the University of Edinburgh, Britain. His research interests include data mining, knowledge-based systems, and Web information exploration. He has published extensively in these areas in various journals and conferences, including IEEE TKDE, TPAMI, ACM TOIS, IJCAI, AAAI, ICML, KDD, ICDM, and WWW. Dr. Wu is the Executive Editor (January 1, 1999-December 31, 2004) and an Honorary Editor-in-Chief (starting January 1, 2005) of Knowledge and Information Systems (a peer-reviewed archival journal published by Springer), the founder and current Steering Committee Chair of the IEEE International Conference on Data Mining (ICDM), a Series Editor of the Springer Book Series on Advanced Information and Knowledge Processing (AI&KP), and the Chair of the IEEE Computer Society Technical Committee on Computational Intelligence (TCCI). He served as an Associate Editor for the IEEE Transactions on Knowledge and Data Engineering (TKDE) between January 1, 2000 and December 31, 2003, and is the Editor-in-Chief of TKDE since January 1, 2005. He is the winner of the 2004 ACM SIGKDD Service Award. Richard Relue, Ph.D.: He received his Ph.D. in Computer Science from the Colorado School of Mines in 2003. His research interests include association rules in data mining, neural networks for automated classification, and artificial intelligence for robot navigation. He has been an Information Technology consultant since 1992, working with Ball Aerospace and Technology, Rational Software, Natural Fuels Corporation, and Western Interstate Commission for Higher Education (WICHE).     

FP-growth算法的实现方法研究

事务数据库中频繁模式的挖掘研究作为关联规则等许多数据挖掘问题的核心工作,已经研究了许多年。早期算法大都是Apriori型算法,即首先产生候选集,然后在候选集的基础上找出频繁模式,候选集的产生往往是耗时的,特别是挖掘富模式或长模式时。JianweiHan等人提出了一种新颖的数据结构FP-tree及基于其上的FP-growth算法,用于有效的富模式与长模式挖掘。由于不同的实现方法可能会导致不同的挖掘效率,该文在讨论FP-growth算法的基础上,采用了几种不同的方法来实现它,并用几个数据库对它们的性能进行了比较。     

Building an interaction design pattern language: A case study

Interaction design patterns are a proven way to communicate good design. However, current pattern collections are not sufficiently powerful and generative to be used as a guide for designing an entire application such as those used in complex business environments. This study shows how we built and validated interaction design patterns that serve as the specification for the redesign of an application. Additionally, they were integrated into a pattern language, as a ruleset for human–computer interaction (HCI) non-professionals to continue development of the application. We demonstrate how individual phases in the redesign of an application can be matched with the process of creating an interaction design pattern language. To facilitate the writing of individual interaction design patterns as well as the development of the pattern language as a whole, a combination of user interviews, controlled experiments and analytical methods has been applied successfully.     

The organization of interaction design pattern languages alongside the design process

This work explores the possibility of taking the structural characteristics of approaches to interaction design as a basis for the organization of interaction design patterns. The Universal Model of the User Interface (Baxley, 2003) is seen as well suited to this; however, in order to cover the full range of interaction design patterns the model had to be extended slightly. Four existing collections of interaction design patterns have been selected for an analysis in which the patterns have been mapped onto the extended model. The conclusion from this analysis is that the use of the model supports the process of building a pattern language, because it is predictive and helps to complete the language. If several pattern writers were to adopt the model, a new level of synergy could be attained among these pattern efforts. A concluding vision would be that patterns could be transferred freely between pattern collections to make them as complete as possible.     

Mining user access patterns with traversal constraint for predicting web page requests

The recent increase in HyperText Transfer Protocol (HTTP) traffic on the World Wide Web (WWW) has generated an enormous amount of log records on Web server databases. Applying Web mining techniques on these server log records can discover potentially useful patterns and reveal user access behaviors on the Web site. In this paper, we propose a new approach for mining user access patterns for predicting Web page requests, which consists of two steps. First, the Minimum Reaching Distance (MRD) algorithm is applied to find the distances between the Web pages. Second, the association rule mining technique is applied to form a set of predictive rules, and the MRD information is used to prune the results from the association rule mining process. Experimental results from a real Web data set show that our approach improved the performance over the existing Markov-model approach in precision, recall, and the reduction of user browsing time. Mei-Ling Shyu received her Ph.D. degree from the School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN in 1999, and three Master's degrees from Computer Science, Electrical Engineering, and Restaurant, Hotel, Institutional, and Tourism Management from Purdue University. She has been an Associate Professor in the Department of Electrical and Computer Engineering (ECE) at the University of Miami (UM), Coral Gables, FL, since June 2005, Prior to that, she was an Assistant Professor in ECE at UM dating from January 2000. Her research interests include data mining, multimedia database systems, multimedia networking, database systems, and security. She has authored and co-authored more than 120 technical papers published in various prestigious journals, refereed conference/symposium/workshop proceedings, and book chapters. She is/was the guest editor of several journal special issues. Choochart Haruechaiyasak received his Ph.D. degree from the Department of Electrical and Computer Engineering, University of Miami, in 2003 with the Outstanding Departmental Graduating Student award from the College of Engineering. After receiving his degree, he has joined the National Electronics and Computer Technology Center (NECTEC), located in Thailand Science Park, as a researcher in Information Research and Development Division (RDI). His current research interests include data/ text/ Web mining, Natural Language Processing, Information Retrieval, Search Engines, and Recommender Systems. He is currently leading a small group of researchers and programmer to develop an open-source search engine for Thai language. One of his objectives is to promote the use of data mining technology and other advanced applications in Information Technology in Thailand. He is also a visiting lecturer for Data Mining, Artificial Intelligence and Decision Support Systems courses in many universities in Thailand. Shu-Ching Chen received his Ph.D. from the School of Electrical and Computer Engineering at Purdue University, West Lafayette, IN, USA in December, 1998. He also received Master's degrees in Computer Science, Electrical Engineering, and Civil Engineering from Purdue University. He has been an Associate Professor in the School of Computing and Information Sciences (SCIS), Florida International University (FIU) since August, 2004. Prior to that, he was an Assistant Professor in SCIS at FIU dating from August, 1999. His main research interests include distributed multimedia database systems and multimedia data mining. Dr. Chen has authored and co-authored more than 140 research papers in journals, refereed conference/symposium/workshop proceedings, and book chapters. In 2005, he was awarded the IEEE Systems, Man, and Cybernetics Society's Outstanding Contribution Award. He was also awarded a University Outstanding Faculty Research Award from FIU in 2004, Outstanding Faculty Service Award from SCIS in 2004 and Outstanding Faculty Research Award from SCIS in 2002.     

High-utility pattern mining: A method for discovery of high-utility item sets

We present an algorithm for frequent item set mining that identifies high-utility item combinations. In contrast to the traditional association rule and frequent item mining techniques, the goal of the algorithm is to find segments of data, defined through combinations of few items (rules), which satisfy certain conditions as a group and maximize a predefined objective function. We formulate the task as an optimization problem, present an efficient approximation to solve it through specialized partition trees, called High-Yield Partition Trees, and investigate the performance of different splitting strategies. The algorithm has been tested on “real-world” data sets, and achieved very good results.     

Discovering pattern-based subspace clusters by pattern tree

Traditional clustering models based on distance similarity are not always effective in capturing correlation among data objects, while pattern-based clustering can do well in identifying correlation hidden among data objects. However, the state-of-the-art pattern-based clustering methods are inefficient and provide no metric to measure the clustering quality. This paper presents a new pattern-based subspace clustering method, which can tackle the problems mentioned above. Observing the analogy between mining frequent itemsets and discovering subspace clusters, we apply pattern tree – a structure used in frequent itemsets mining to determining the target subspaces by scanning the database once, which can be done efficiently in large datasets. Furthermore, we introduce a general clustering quality evaluation model to guide the identifying of meaningful clusters. The proposed new method enables the users to set flexibly proper quality-control parameters to meet different needs. Experimental results on synthetic and real datasets show that our method outperforms the existing methods in both efficiency and effectiveness.     

基于候选组合频繁模式的骨干网蠕虫检测研究

现有的网络蠕虫检测方法大多都是基于包的检测,针对骨干网IP流检测的研究较少,同时也不能很好地描述蠕虫的攻击模式。为此研究了一种在骨干网IP流数据环境下的蠕虫检测方法,通过流活跃度增长系数和目的地址增长系数定位可疑源主机,接着采用基于候选组合频繁模式的挖掘算法(CCFPM),将候选频繁端口模式在FP树路径中进行匹配来发现蠕虫及其攻击特性,实验证明该方法能快速地发现未知蠕虫及其端口扫描模式。     

A metamodeling approach for pattern specification and management

The formal specification of design patterns is central to pattern research and is the foundation of solving various pattern-related problems.In this paper,we propose a metamodeling approach for pattern specification,in which a pattern is modeled as a meta-level class and its participants are meta-level references.Instead of defining a new metamodel,we reuse the Unified Modeling Language(UML)metamodel and incorporate the concepts of Variable and Set into our approach,which are unavailable in the UML but essential for pattern specification.Our approach provides straightforward solutions for pattern-related problems,such as pattern instantiation,evolution,and implementation.By integrating the solutions into a single framework,we can construct a pattern management system,in which patterns can be instantiated,evolved,and implemented in a correct and manageable way.     

增量更新关联规则数据库挖掘算法研究

随着数据库技术的不断发展及数据库管理系统的广泛应用,大型数据库系统己经在各行各业普及,数据库中存储的数据量急剧增大,数据挖掘便是从海量数据库中挖掘有效或重要信息的过程。关联规则挖掘是数据挖掘领域一个非常重要的研究课题,被广泛地应用于商业界、医疗保险、金融业、电信部门等。随着时间的推移,挖掘数据库的规模会发生不断变化,人们对数据的需求也会有所不同,因此如何从扩展数据库中高效地对已经推导出的关联规则进行更新具有非常重要的应用价值,这就是所谓的增量式挖掘关联规则的问题。     

一种基于F-矩阵的最大频繁项目集快速挖掘算法

最大频繁项目集挖掘是多种数据挖掘应用研究的一个重要方面,最大频繁项目集的快速挖掘算法研究是当前研究的热点。传统的最大频繁项目集挖掘算法要多遍扫描数据库并产生大量的候选项目集。为此,该文提出了基于F-矩阵的最大频繁项目集快速挖掘算法FMMFIBFM,FMMFIBFM采用FP-tree的存储结构,仅须扫描数据库两遍且不产生候选频繁项目集,有效地提高了频繁项目集的挖掘效率。实验结果表明,FMMFIBFM算法是有效可行的。     

入侵检测系统中的数值型关联规则挖掘方法

入侵检测技术弥补了传统安全机制的一些缺陷。基于数据挖掘的入侵检测系统的挖掘算法尚有不足之处。通过对聚类分析和关联分析的算法分别进行改进，构建出新的基于数值属性关联规则挖掘算法的入侵检测系统。运用此系统进行入侵检测实验，实验结果证明改进的算法效果良好。