waashk/dblp huggingface dataset:
a new efficient probabilistic model for mining labeled ordered trees. mining frequent patterns is a general and important issue in data mining. complex and unstructured (or semi-structured) datasets have appeared in major data mining applications, including text mining, web mining and bioinformatics. mining patterns from these datasets is the focus of many of the current data mining approaches. we focus on labeled ordered trees, typical datasets of semi-structured data in data mining, and propose a new probabilistic model and its efficient learning scheme for mining labeled ordered trees. the proposed approach significantly improves the time and space complexity of an existing probabilistic modeling for labeled ordered trees, while maintaining its expressive power. we evaluated the performance of the proposed model, comparing it with that of the existing model, using synthetic as well as real datasets from the field of glycobiology. experimental results showed that the proposed model drastically reduced the computation time of the competing model, keeping the predictive power and avoiding overfitting to the training data. finally, we assessed our results using the proposed model on real data from a variety of biological viewpoints, verifying known facts in glycobiology.
discriminant adaptive nearest neighbor classification. nearest neighbor classification expects the class conditional probabilities to be locally constant, and suffers from bias in high dimensions. we propose a locally adaptive form of nearest neighbor classification to try to ameliorate this curse of dimensionality. we use a local linear discriminant analysis to estimate an effective metric for computing neighborhoods. we determine the local decision boundaries from centroid information, and then shrink neighborhoods in directions orthogonal to these local decision boundaries, and elongate them parallel to the boundaries. thereafter, any neighborhood-based classifier can be employed, using the modified neighborhoods. the posterior probabilities tend to be more homogeneous in the modified neighborhoods. we also propose a method for global dimension reduction, that combines local dimension information. in a number of examples, the methods demonstrate the potential for substantial improvements over nearest neighbor classification.
discovering complex matchings across web query interfaces: a correlation mining approach. to enable information integration, schema matching is a critical step for discovering semantic correspondences of attributes across heterogeneous sources. while complex matchings are common, because of their far more complex search space, most existing techniques focus on simple 1:1 matchings. to tackle this challenge, this paper takes a conceptually novel approach by viewing schema matching as correlation mining, for our task of matching web query interfaces to integrate the myriad databases on the internet. on this "deep web," query interfaces generally form complex matchings between attribute groups (e.g., [author] corresponds to [first name, last name] in the books domain). we observe that the co-occurrences patterns across query interfaces often reveal such complex semantic relationships: grouping attributes (e.g., [first name, last name]) tend to be co-present in query interfaces and thus positively correlated. in contrast, synonym attributes are negatively correlated because they rarely co-occur. this insight enables us to discover complex matchings by a correlation mining approach. in particular, we develop the dcm framework, which consists of data preparation, dual mining of positive and negative correlations, and finally matching selection. unlike previous correlation mining algorithms, which mainly focus on finding strong positive correlations, our algorithm cares both positive and negative correlations, especially the subtlety of negative correlations, due to its special importance in schema matching. this leads to the introduction of a new correlation measure, $h$-measure, distinct from those proposed in previous work. we evaluate our approach extensively and the results show good accuracy for discovering complex matchings.
graphical models for data mining. i will discuss the use of graphical models for data mining. i will review key research areas including structure learning, variational methods, a relational modeling, and describe applications ranging from web traffic analysis to aids vaccine design.
maximal boasting. we introduce the boasting problem, wherein useful trends in historical ordinal data (rankings) are discovered. claims of the form "our object was ranked r or better in x of the last t time units," are formalized, and maximal claims (boasts) of this form are defined under two natural partial orders. for the first partial order, we give an efficient and optimal algorithm for finding all such maximal claims. for the second, we apply a classical result from computational geometry to achieve an algorithm whose running time is significantly more efficient than that of a naïve one. finally, we connect this boasting problem to a novel variation of the problem of finding optimized confidence association rules as originally posed by fukuda, et al. [2], and give an efficient algorithm for solving a simplification of the new problem.
ga-based rule enhancement in concept learning. we describe an application of dogma, a ga-based theory revision system, to mdl-based rule enhancement in supervised concept learning. the system takes as input classification data and a rule-based classification theory, produced by some rule-based learner, and builds a second, hopefully more accurate, model of the data. unlike most theory revision systems dogma doesn''t revise the initial rules, but builds instead a completely new theory, using stochastic sampling and adaptation of the initial rules. the search for the new model is guided by a mdl-based complexity measure. the proposed methodology offers a partial solution both to the local mimima trap of fast greedy rule-based concept learners, and to the time complexity problem of ga-based concept learners. as an example we show how the system improves rules produced by c4.5rules.
combining email models for false positive reduction. machine learning and data mining can be effectively used to model, classify and discover interesting information for a wide variety of data including email. the email mining toolkit, emt, has been designed to provide a wide range of analyses for arbitrary email sources. depending upon the task, one can usually achieve very high accuracy, but with some amount of false positive tradeoff. generally false positives are prohibitively expensive in the real world. in the case of spam detection, for example, even if one email is misclassified, this may be unacceptable if it is a very important email. much work has been done to improve specific algorithms for the task of detecting unwanted messages, but less work has been report on leveraging multiple algorithms and correlating models in this particular domain of email analysis.emt has been updated with new correlation functions allowing the analyst to integrate a number of emt's user behavior models available in the core technology. we present results of combining classifier outputs for improving both accuracy and reducing false positives for the problem of spam detection. we apply these methods to a very large email data set and show results of different combination methods on these corpora. we introduce a new method to compare multiple and combined classifiers, and show how it differs from past work. the method analyzes the relative gain and maximum possible accuracy that can be achieved for certain combinations of classifiers to automatically choose the best combination.
mining for proposal reviewers: lessons learned at the national science foundation. in this paper, we discuss a prototype application deployed at the u.s. national science foundation for assisting program directors in identifying reviewers for proposals. the application helps program directors sort proposals into panels and find reviewers for proposals. to accomplish these tasks, it extracts information from the full text of proposals both to learn about the topics of proposals and the expertise of reviewers. we discuss a variety of alternatives that were explored, the solution that was implemented, and the experience in using the solution within the workflow of nsf.
mining hepatitis data with temporal abstraction. the hepatitis temporal database collected at chiba university hospital between 1982--2001 was recently given to challenge the kdd research. the database is large where each patient corresponds to 983 tests represented as sequences of irregular timestamp points with different lengths. this paper presents a temporal abstraction approach to mining knowledge from this hepatitis database. exploiting hepatitis background knowledge and data analysis, we introduce new notions and methods for abstracting short-term changed and long-term changed tests. the abstracted data allow us to apply different machine learning methods for finding knowledge part of which is considered as new and interesting by medical doctors.
visualization support for a user-centered kdd process. viewing knowledge discovery as a user-centered process that requires an effective collaboration between the user and the discovery system, our work aims to support an active role of the user in that process by developing synergistic visualization tools integrated in our discovery system d2ms. these tools provide an ability of visualizing the entire process of knowledge discovery in order to help the user with data preprocessing, selecting mining algorithms and parameters, evaluating and comparing discovered models, and taking control of the whole discover process. our case-studies with two medical datasets on meningitis and stomach cancer show that, with visualization tools in d2ms, the user gains better insight in each step of the knowledge discovery process as well the relationship between data and discovered knowledge.
learning the unified kernel machines for classification. kernel machines have been shown as the state-of-the-art learning techniques for classification. in this paper, we propose a novel general framework of learning the unified kernel machines (ukm) from both labeled and unlabeled data. our proposed framework integrates supervised learning, semi-supervised kernel learning, and active learning in a unified solution. in the suggested framework, we particularly focus our attention on designing a new semi-supervised kernel learning method, i.e., spectral kernel learning (skl), which is built on the principles of kernel target alignment and unsupervised kernel design. our algorithm is related to an equivalent quadratic programming problem that can be efficiently solved. empirical results have shown that our method is more effective and robust to learn the semi-supervised kernels than traditional approaches. based on the framework, we present a specific paradigm of unified kernel machines with respect to kernel logistic regresions (klr), i.e., unified kernel logistic regression (uklr). we evaluate our proposed uklr classification scheme in comparison with traditional solutions. the promising results show that our proposed uklr paradigm is more effective than the traditional classification approaches.
a perspective on databases and data mining. we discuss the use of database methods for data mining. recently impressive results have been achieved for some data mining problems using highly specialized and clever data structures. we study how well one can manage by using general purpose database management systems. we illustrate our ideas by investigating the use of a dbms for a well-researched area: the discovery of association rules. we present a simple algorithm, consisting of only union and intersection operations, and show that it achieves quite good performance on an efficient dbms. our method can incorporate inheritance hierarchies to the association rule algorithm easily. we also present a technique that effectively reduces the number of database operations when searching large search spaces that contain only few interesting items. our work shows that database techniques are promising for data mining: general architectures can achieve reasonable results.
diagnosing extrapolation: tree-based density estimation. there has historically been very little concern with extrapolation in machine learning, yet extrapolation can be critical to diagnose. predictor functions are almost always learned on a set of highly correlated data comprising a very small segment of predictor space. moreover, flexible predictors, by their very nature, are not controlled at points of extrapolation. this becomes a problem for diagnostic tools that require evaluation on a product distribution. it is also an issue when we are trying to optimize a response over some variable in the input space. finally, it can be a problem in non-static systems in which the underlying predictor distribution gradually drifts with time or when typographical errors misrecord the values of some predictors.we present a diagnosis for extrapolation as a statistical test for a point originating from the data distribution as opposed to a null hypothesis uniform distribution. this allows us to employ general classification methods for estimating such a test statistic. further, we observe that cart can be modified to accept an exact distribution as an argument, providing a better classification tool which becomes our extrapolation-detection procedure. we explore some of the advantages of this approach and present examples of its practical application.
discovering additive structure in black box functions. many automated learning procedures lack interpretability, operating effectively as a black box: providing a prediction tool but no explanation of the underlying dynamics that drive it. a common approach to interpretation is to plot the dependence of a learned function on one or two predictors. we present a method that seeks not to display the behavior of a function, but to evaluate the importance of non-additive interactions within any set of variables. should the function be close to a sum of low dimensional components, these components can be viewed and even modeled parametrically. alternatively, the work here provides an indication of where intrinsically high-dimensional behavior takes place.the calculations used in this paper correspond closely with the functional anova decomposition; a well-developed construction in statistics. in particular, the proposed score of interaction importance measures the loss associated with the projection of the prediction function onto a space of additive models. the algorithm runs in linear time and we present displays of the output as a graphical model of the function for interpretation purposes.
natural communities in large linked networks. we are interested in finding natural communities in large-scale linked networks. our ultimate goal is to track changes over time in such communities. for such temporal tracking, we require a clustering algorithm that is relatively stable under small perturbations of the input data. we have developed an efficient, scalable agglomerative strategy and applied it to the citation graph of the nec citeseer database (250,000 papers; 4.5 million citations). agglomerative clustering techniques are known to be unstable on data in which the community structure is not strong. we find that some communities are essentially random and thus unstable while others are natural and will appear in most clusterings. these natural communities will enable us to track the evolution of communities over time.
cyclic pattern kernels for predictive graph mining. with applications in biology, the world-wide web, and several other areas, mining of graph-structured objects has received significant interest recently. one of the major research directions in this field is concerned with predictive data mining in graph databases where each instance is represented by a graph. some of the proposed approaches for this task rely on the excellent classification performance of support vector machines. to control the computational cost of these approaches, the underlying kernel functions are based on frequent patterns. in contrast to these approaches, we propose a kernel function based on a natural set of cyclic and tree patterns independent of their frequency, and discuss its computational aspects. to practically demonstrate the effectiveness of our approach, we use the popular nci-hiv molecule dataset. our experimental results show that cyclic pattern kernels can be computed quickly and offer predictive performance superior to recent graph kernels based on frequent patterns.
frequent subgraph mining in outerplanar graphs. in recent years there has been an increased interest in algorithms that can perform frequent pattern discovery in large databases of graph structured objects. while the frequent connected subgraph mining problem for tree datasets can be solved in incremental polynomial time, it becomes intractable for arbitrary graph databases. existing approaches have therefore resorted to various heuristic strategies and restrictions of the search space, but have not identified a practically relevant tractable graph class beyond trees. in this paper, we define the class of so called tenuous outerplanar graphs, a strict generalization of trees, develop a frequent subgraph mining algorithm for tenuous outerplanar graphs that works in incremental polynomial time, and evaluate the algorithm empirically on the nci molecular graph dataset.
revi-miner, a kdd-environment for deviation detection and analysis of warranty and goodwill cost statements in automotive industry. revi-miner is a kdd-environment which supports the detection and analysis of deviations in warranty and goodwill cost statements. the system was developed within the framework of a cooperation between daimlerchrysler research & technology and global service and parts (gsp) and is based upon the crisp-dm methodology as a widely accepted process model for the solution of data mining problems. also, we have implemented different approaches based on machine learning and statistics which can be utilized for data cleaning in the preprocessing phase. the data mining models applied have been developed by using a statistical deviation detection approach. the tool supports controllers in their task of auditing the authorized repair shops. in this paper we describe the development phases which have led to revi-miner.
navigating massive data sets via local clustering. this paper introduces a scalable method for feature extraction and navigation of large data sets by means of local clustering, where clusters are modeled as overlapping neighborhoods. under the model, intra-cluster association and external differentiation are both assessed in terms of a natural confidence measure. minor clusters can be identified even when they appear in the intersection of larger clusters. scalability of local clustering derives from recent generic techniques for efficient approximate similarity search. the cluster overlap structure gives rise to a hierarchy that can be navigated and queried by users. experimental results are provided for two large text databases.
mining viewpoint patterns in image databases. the increasing number of image repositories has made image mining an important task because of its potential in discovering useful image patterns from a large set of images. in this paper, we introduce the notion of viewpoint patterns for image databases. viewpoint patterns refer to patterns that capture the invariant relationships of one object from the point of view of another object. these patterns are unique and significant in images because the absolute positional information of objects for most images is not important, but rather, it is the relative distance and orientation of the objects from each other that is meaningful. we design a scalable and efficient algorithm to discover such viewpoint patterns. experiments results on various image sets demonstrate that viewpoint patterns are meaningful and interesting to human users.
spin: mining maximal frequent subgraphs from graph databases. one fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. in large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. in this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. this may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude.our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.
data mining techniques to improve forecast accuracy in airline business. predictive models developed by applying data mining techniques are used to improve forecasting accuracy in the airline business. in order to maximize the revenue on a flight, the number of seats available for sale is typically higher than the physical seat capacity (overbooking). to optimize the overbooking rate, an accurate estimation of the number of no-show passengers (passengers who hold a valid booking but do not appear at the gate to board for the flight) is essential. currently, no-shows on future flights are estimated from the number of no-shows on historical flights averaged on booking class level. in this work, classification trees and logistic regression models are applied to estimate the probability that an individual passenger turns out to be a no-show. passenger information stored in the reservation system of the airline is either directly used as explanatory variable or used to create attributes that have an impact on the probability of a passenger to be a no-show. the total number of no-shows in each booking class or on the total flight is then obtained by accumulating the individual no-show probabilities over the entity of interest. we show that this forecasting approach is more accurate than the currently used method. in addition, the selected models lead to a deepened insight into passenger behavior.
mining complex models from arbitrarily large databases in constant time. in this paper we propose a scaling-up method that is applicable to essentially any induction algorithm based on discrete search. the result of applying the method to an algorithm is that its running time becomes independent of the size of the database, while the decisions made are essentially identical to those that would be made given infinite data. the method works within pre-specified memory limits and, as long as the data is iid, only requires accessing it sequentially. it gives anytime results, and can be used to produce batch, stream, time-changing and active-learning versions of an algorithm. we apply the method to learning bayesian networks, developing an algorithm that is faster than previous ones by orders of magnitude, while achieving essentially the same predictive performance. we observe these gains on a series of large databases "generated from benchmark networks, on the kdd cup 2000 e-commerce data, and on a web log containing 100 million requests.