检索结果-内蒙古大学图书馆

mining closed and maximal frequent subtrees from databases of labeled rooted trees

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2005年第2期17卷 190-202页

作者： Chi, Y Xia, Y Yang, YR Muntz, RR Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. One important problem in mining databases of trees is to find frequently occurring subtrees. Because of the combinatorial explosion, the number of frequent subtrees usually grows exponentially with the size of frequent subtrees and, therefore, mining all frequent subtrees becomes infeasible for large tree sizes. In this paper, we present CMTreeMiner, a computationally efficient algorithm that discovers only closed and maximal frequent subtrees in a database of labeled rooted trees, where the rooted trees can be either ordered or unordered. The algorithm mines both closed and maximal frequent subtrees by traversing an enumeration tree that systematically enumerates all frequent subtrees. Several techniques are proposed to prune the branches of the enumeration tree that do not correspond to closed or maximal frequent subtrees. Heuristic techniques are used to arrange the order of computation so that relatively expensive computation is avoided as much as possible. We study the performance of our algorithm through extensive experiments, using both synthetic data and data sets from real applications. The experimental results show that our algorithm is very efficient in reducing the search space and quickly discovers all closed and maximal frequent subtrees.

关键词： trees graph algorithms data mining mining methods and algorithms frequent subtree closed frequent subtree maximal frequent subtree

来源：评论

学校读者我要写书评

暂无评论

HARP: A practical projected clustering algorithm

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2004年第11期16卷 1387-1397页

作者： Yip, KY Cheung, DW Ng, MK Univ Hong Kong Dept Comp Sci & Informat Syst Hong Kong Hong Kong Peoples R China Univ Hong Kong Dept Math Hong Kong Hong Kong Peoples R China

In high-dimensional data, clusters can exist in subspaces that hide themselves from traditional clustering methods. A number of algorithms have been proposed to identify such projected clusters, but most of them rely on some user parameters to guide the clustering process. The clustering accuracy can be seriously degraded if incorrect values are used. Unfortunately, in real situations, it is rarely possible for users to supply the parameter values accurately, which causes practical difficulties in applying these algorithms to real data. In this paper, we analyze the major challenges of projected clustering and suggest why these algorithms need to depend heavily on user parameters. Based on the analysis, we propose a new algorithm that exploits the clustering status to adjust the internal thresholds dynamically without the assistance of user parameters. According to the results of extensive experiments on real and synthetic data, the new method has excellent accuracy and usability. It outperformed the other algorithms even when correct parameter values were artificially supplied to them. The encouraging results suggest that projected clustering can be a practical tool for various kinds of real applications.

关键词： data mining mining methods and algorithms clustering bioinformatics

来源：评论

学校读者我要写书评

暂无评论

Essential latent knowledge for protein-protein interactions: Analysis by an unsupervised learning approach

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2005年第2期2卷 119-130页

作者： Mamitsuka, H Kyoto Univ Inst Chem Res Uji 6110011 Japan

Protein-protein interactions play a number of central roles in many cellular functions, including DNA replication, transcription and translation, signal transduction, and metabolic pathways. A recent increase in the number of protein-protein interactions has made predicting unknown protein-protein interactions important for the understanding of living cells. However, the protein-protein interactions experimentally obtained so far are often incomplete and contradictory and, consequently, existing computational prediction methods have integrated evidence (latent knowledge of proteins) from different and more reliable sources. Analyzing the relationships between proteins and the latent knowledge is important to understanding the cellular processes. For this analysis, we propose a new probabilistic model for protein-protein interactions by considering the latent knowledge of proteins. We further present an efficient learning algorithm for this model, based on an EM algorithm. Experimental results have shown that in a supervised test setting, the proposed method outperformed five other competing methods by a statistically significant factor in all cases. Using the probability parameters of a trained model, we have further shown the latent knowledge that is essential to predicting protein-protein interactions. Overall, our experimental results confirm that our proposed model is especially effective for analyzing protein-protein interactions from a viewpoint of the latent knowledge of proteins.

关键词： biology and genetics machine learning data mining mining methods and algorithms

来源：评论

学校读者我要写书评

暂无评论

Pattern-Aided Regression Modeling and Prediction Model Analysis

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第9期27卷 2452-2465页

作者： Dong, Guozhu Taslimitehrani, Vahid Wright State Univ Dept Comp Sci & Engn Dayton OH 45435 USA Wright State Univ Kno E Sis Ctr Dayton OH 45435 USA

This paper first introduces pattern aided regression (PXR) models, a new type of regression models designed to represent accurate and interpretable prediction models. This was motivated by two observations: (1) Regression modeling applications often involve complex diverse predictor-response relationships, which occur when the optimal regression models (of given regression model type) fitting two or more distinct logical groups of data are highly different. (2) State-of-the-art regression methods are often unable to adequately model such relationships. This paper defines PXR models using several patterns and local regression models, which respectively serve as logical and behavioral characterizations of distinct predictor-response relationships. The paper also introduces a contrast pattern aided regression (CPXR) method, to build accurate PXR models. In experiments, the PXR models built by CPXR are very accurate in general, often outperforming state-of-the-art regression methods by big margins. Usually using (a) around seven simple patterns and (b) linear local regression models, those PXR models are easy to interpret;in fact, their complexity is just a bit higher than that of (piecewise) linear regression models and is significantly lower than that of traditional ensemble based regression models. CPXR is especially effective for high-dimensional data. The paper also discusses how to use CPXR methodology for analyzing prediction models and correcting their prediction errors.

关键词： Correlation and regression analysis model validation and analysis error analysis data mining mining methods and algorithms

来源：评论

学校读者我要写书评

暂无评论

mining the Largest Dense Vertexlet in a Weighted Scale-free Graph

引用

FUNDAMENTA INFORMATICAE 2009年第1-2期96卷 1-25页

作者： Bandyopadhyay, Sanghamitra Bhattacharyya, Malay Indian Stat Inst Machine Intelligence Unit Kolkata 700108 India

An important problem of knowledge discovery that has recently evolved in various real-life networks is identifying the largest set of vertices that are functionally associated. The topology of many real-life networks shows scale-freeness, where the vertices of the underlying graph follow a power-law degree distribution. Moreover, the graphs corresponding to most of the real-life networks are weighted in nature. In this article, the problem of finding the largest group or association of vertices that are dense (denoted as dense vertexlet) in a weighted scale-free graph is addressed. Density quantifies the degree of similarity within a group of vertices in a graph. The density of a vertexlet is defined in a novel way that ensures significant participation of all the vertices within the vertexlet. It is established that the problem is NP-complete in nature. An upper bound on the order of the largest dense vertexlet of a weighted graph, with respect to certain density threshold value, is also derived. Finally, an O(n(2) log n) (n denotes the number of vertices in the graph) heuristic graph mining algorithm that produces an approximate solution for the problem is presented.

关键词： Graphs and networks scale-free mining methods and algorithms knowledge discovery bioinformatics

来源：评论

学校读者我要写书评

暂无评论

The combined technique for detection of artifacts in clinical electroencephalograms of sleeping newborns

引用

IEEE TRANSACTIONS ON INFORMATION TECHNOLOGY IN BIOMEDICINE 2004年第1期8卷 28-35页

作者： Schetinin, V Schult, J Univ Exeter Dept Comp Sci Exeter EX4 4QF Devon England Univ Jena TheorieLabor D-07740 Jena Germany

In this paper, we describe a new method combining the polynomial neural network and decision tree techniques in order to derive comprehensible classification rules from clinical electroencephalograms (EEGs) recorded from sleeping newborns. These EEGs are heavily corrupted by cardiac, eye movement, muscle, and noise artifacts and, as a consequence, some EEG features are irrelevant to classification problems. Combining the polynomial network and decision tree techniques, we discover comprehensible classification rules while also attempting to keep their classification error down. This technique is shown to outperform a number of commonly used machine learning technique applied to automatically recognize artifacts in the sleep EEGs.

关键词： feature evaluation and selection mining methods and algorithms neural nets

来源：评论

学校读者我要写书评

暂无评论

A probabilistic model for mining labeled ordered trees: Capturing patterns in carbohydrate sugar chains

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2005年第8期17卷 1051-1064页

作者： Ueda, N Aoki-Kinoshita, KF Yamaguchi, A Akutsu, T Mamitsuka, H Kyoto Univ Inst Chem Res Bioinformat Ctr Gokasho Uji 6110011 Japan

Glycans, or carbohydrate sugar chains, which play a number of important roles in the development and functioning of multicellular organisms, can be regarded as labeled ordered trees. A recent increase in the documentation of glycan structures, especially in the form of database curation, has made mining glycans important for the understanding of living cells. We propose a probabilistic model for mining labeled ordered trees, and we further present an efficient learning algorithm for this model, based on an EM algorithm. The time and space complexities of this algorithm are rather favorable, falling within the practical limits set by a variety of existing probabilistic models, including stochastic context-free grammars. Experimental results have shown that, in a supervised problem setting, the proposed method outperformed five other competing methods by a statistically significant factor in all cases. We further applied the proposed method to aligning multiple glycan trees, and we detected biologically significant common subtrees in these alignments where the trees are automatically classified into subtypes already known in glycobiology. Extended abstracts of parts of the work presented in this paper have appeared in [35], [4], and [3].

关键词： biology and genetics machine learning data mining mining methods and algorithms

来源：评论

学校读者我要写书评

暂无评论

Pruning and visualizing generalized association rules in parallel coordinates

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2005年第1期17卷 60-70页

作者： Yang, L Western Michigan Univ Dept Comp Sci Kalamazoo MI 49008 USA

One fundamental problem for visualizing frequent itemsets and association rules is how to present a long border of frequent itemsets in an itemset lattice. Another problem comes from the lack of an effective visual metaphor to represent many-to-many relationships. This paper proposes an approach for visualizing frequent itemsets and many-to-many association rules by a novel use of parallel coordinates. An association rule is visualized by connecting items in the rule, one item on each parallel coordinate, with continuous polynomial curves. In the presence of item taxonomy, each coordinate can be used to visualize an item taxonomy tree which can be expanded or shrunk by user interaction. This user interaction introduces a border, which separates displayable itemsets from nondisplayable ones, in the generalized itemset lattice. Only those itemsets that are both frequent and displayable are considered to be displayed. This approach of visualizing frequent itemsets and association rules has the following features: 1) It is capable of visualizing many-to-many rules and itemsets with many items. 2) It is capable of visualizing a large number of itemsets or rules by displaying only those ones whose items are selected by the user. 3) The closure properties of frequent itemsets and association rules are inherently supported such that the implied ones are not displayed. Usefulness of this approach is demonstrated through examples.

关键词： association rules data visualization data mining interactive data exploration mining methods and algorithms

来源：评论

学校读者我要写书评

暂无评论

The discrete basis problem

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2008年第10期20卷 1348-1362页

作者： Miettinen, Pauli Mielikainen, Taneli Gionis, Aristides Das, Gautam Mannila, Heikki Univ Helsinki Helsinki Inst Informat Technol FI-00014 Helsinki Finland Aalto Univ FI-00014 Helsinki Finland Nokia Res Ctr Palo Alto Syst Res Ctr Palo Alto CA 94304 USA Yahoo Res Barcelona 08003 Spain Univ Texas Arlington Dept Comp Sci & Engn Arlington TX 76019 USA

Matrix decomposition methods represent a data matrix as a product of two factor matrices: one containing basis vectors that represent meaningful concepts in the data and another describing how the observed data can be expressed as combinations of the basis vectors. Decomposition methods have been studied extensively, but many methods return real-valued matrices. Interpreting real-valued factor matrices is hard if the original data is Boolean. In this paper, we describe a matrix decomposition formulation for Boolean data, the Discrete Basis Problem. The problem seeks for a Boolean decomposition of a binary matrix, thus allowing the user to easily interpret the basis vectors. We also describe a variation of the problem, the Discrete Basis Partitioning Problem. We show that both problems are NP-hard. For the Discrete Basis Problem, we give a simple greedy algorithm for solving it;for the Discrete Basis Partitioning Problem, we show how it can be solved using existing methods. We present experimental results for the greedy algorithm and compare it against other well-known methods. Our algorithm gives intuitive basis vectors, but its reconstruction error is usually larger than with the real-valued methods. We discuss the reasons for this behavior.

关键词： mining methods and algorithms clustering classification and association rules text mining

来源：评论

学校读者我要写书评

暂无评论

On mining approximate and exact fault-tolerant frequent itemsets

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2018年第2期55卷 361-391页

作者： Liu, Shengxin Poon, Chung Keung City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Caritas Inst Higher Educ Sch Comp & Informat Sci Hong Kong Hong Kong Peoples R China

Robust frequent itemset mining has attracted much attention due to the necessity to find frequent patterns from noisy data in many applications. In this paper, we focus on a variant of robust frequent itemsets in which a small amount of "faults" is allowed in each item and each supporting transaction. This problem is challenging since computing fault-tolerant support count is NP-hard and the anti-monotone property does not hold when the amount of allowable faults is proportional to the size of the itemset. We develop heuristic methods to solve an approximation version of the problem and propose speedup techniques for the exact problem. Experimental results show that our heuristic algorithms are substantially faster than the state-of-the-art exact algorithms while the error is acceptable. In addition, the proposed speedup techniques substantially improve the efficiency of the exact algorithms.

关键词： Data mining mining methods and algorithms Frequent itemsets Fault tolerance Approximate support count

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：