waashk/dblp huggingface dataset:
mining, indexing, and querying historical spatiotemporal data. in many applications that track and analyze spatiotemporal data, movements obey periodic patterns; the objects follow the same routes (approximately) over regular time intervals. for example, people wake up at the same time and follow more or less the same route to their work everyday. the discovery of hidden periodic patterns in spatiotemporal data, apart from unveiling important information to the data analyst, can facilitate data management substantially. based on this observation, we propose a framework that analyzes, manages, and queries object movements that follow such patterns. we define the spatiotemporal periodic pattern mining problem and propose an effective and fast mining algorithm for retrieving maximal periodic patterns. we also devise a novel, specialized index structure that can benefit from the discovered patterns to support more efficient execution of spatiotemporal queries. we evaluate our methods experimentally using datasets with object trajectories that exhibit periodicity.
estimating missed actual positives using independent classifiers. data mining is increasingly being applied in environments having very high rate of data generation like network intrusion detection [7], where routers generate about 300,000 -- 500,000 connections every minute. in such rare class data domains, the cost of missing a rare-class instance is much higher than that of other classes. however, the high cost for manual labeling of instances, the high rate at which data is collected as well as real-time response constraints do not always allow one to determine the actual classes for the collected unlabeled datasets. in our previous work [9], this problem of missed false negatives was explained in context of two different domains -- "network intrusion detection" and "business opportunity classification". in such cases, an estimate for the number of such missed high-cost, rare instances will aid in the evaluation of the performance of the modeling technique (e.g. classification) used. a capture-recapture method was used for estimating false negatives, using two or more learning methods (i.e. classifiers). this paper focuses on the dependence between the class labels assigned by such learners. we define the conditional independence for classifiers given a class label and show its relation to the conditional independence of the features sets (used by the classifiers) given a class label. the later is a computationally expensive problem and hence, a heuristic algorithm is proposed for obtaining conditionally independent (or less dependent) feature sets for the classifiers. initial results of this algorithm on synthetic datasets are promising and further research is being pursued.
visual data mining using principled projection algorithms and information visualization techniques. we introduce a flexible visual data mining framework which combines advanced projection algorithms from the machine learning domain and visual techniques developed in the information visualization domain. the advantage of such an interface is that the user is directly involved in the data mining process. we integrate principled projection algorithms, such as generative topographic mapping (gtm) and hierarchical gtm (hgtm), with powerful visual techniques, such as magnification factors, directional curvatures, parallel coordinates and billboarding, to provide a visual data mining framework. results on a real-life chemoinformatics dataset using gtm are promising and have been analytically compared with the results from the traditional projection methods. it is also shown that the hgtm algorithm provides additional value for large datasets. the computational complexity of these algorithms is discussed to demonstrate their suitability for the visual data mining framework.
generating semantic annotations for frequent patterns with context analysis. as a fundamental data mining task, frequent pattern mining has widespread applications in many different domains. research in frequent pattern mining has so far mostly focused on developing efficient algorithms to discover various kinds of frequent patterns, but little attention has been paid to the important nextstep - interpreting the discovered frequent patterns. although some recent work has studied the compression and summarization of frequent patterns, the proposed techniques can only annotate a frequent pattern with non-semantical information (e.g. support), which provides only limited help for a user to understand the patterns.in this paper, we propose the novel problem of generating semantic annotations for frequent patterns. the goal is to annotate a frequent pattern with in-depth, concise, and structured information that can better indicate the hidden meanings of the pattern. we propose a general approach to generate such anannotation for a frequent pattern by constructing its context model, selecting informative context indicators, and extracting representative transactions and semantically similar patterns. this general approach has potentially many applications such as generating a dictionary-like description for a pattern, finding synonym patterns, discovering semantic relations, and summarizing semantic classes of a set of frequent patterns. experiments on different datasets show that our approach is effective in generating semantic pattern annotations.
discovering evolutionary theme patterns from text: an exploration of temporal text mining. temporal text mining (ttm) is concerned with discovering temporal patterns in text information collected over time. since most text information bears some time stamps, ttm has many applications in multiple domains, such as summarizing events in news articles and revealing research trends in scientific literature. in this paper, we study a particular ttm task -- discovering and summarizing the evolutionary patterns of themes in a text stream. we define this new text mining problem and present general probabilistic methods for solving this problem through (1) discovering latent themes from text; (2) constructing an evolution graph of themes; and (3) analyzing life cycles of themes. evaluation of the proposed methods on two different domains (i.e., news articles and literature) shows that the proposed methods can discover interesting evolutionary theme patterns effectively.
a mixture model for contextual text mining. contextual text mining is concerned with extracting topical themes from a text collection with context information (e.g., time and location) and comparing/analyzing the variations of themes over different contexts. since the topics covered in a document are usually related to the context of the document, analyzing topical themes within context can potentially reveal many interesting theme patterns. in this paper, we generalize some of these models proposed in the previous work and we propose a new general probabilistic model for contextual text mining that can cover several existing models as special cases. specifically, we extend the probabilistic latent semantic analysis (plsa) model by introducing context variables to model the context of a document. the proposed mixture model, called contextual probabilistic latent semantic analysis (cplsa) model, can be applied to many interesting mining tasks, such as temporal text mining, spatiotemporal text mining, author-topic analysis, and cross-collection comparative analysis. empirical experiments show that the proposed mixture model can discover themes and their contextual variations effectively.
finding simple intensity descriptions from event sequence data. sequences of events are an important type of data arising in various applications, including telecommunications, bio-statistics, web access analysis, etc. a basic approach to modeling such sequences is to find the underlying intensity functions describing the expected number of events per time unit. typically, the intensity functions are assumed to be piecewise constant. we therefore consider different ways of fitting intensity models to event sequence data. we start by considering a bayesian approach using markov chain monte carlo (mcmc) methods with varying number of pieces. these methods can be used to produce posterior distributions on the intensity functions and they can also accomodate covariates. the drawback is that they are computationally intensive and thus are not very suitable for data mining applications in which large numbers of intensity functions have to be estimated. we consider dynamic programming approaches to finding the change points in the intensity functions. these methods can find the maximum likelihood intensity function in o(n2k) time for a sequence of n events and k different pieces of intensity. we show that simple heuristics can be used to prune the number of potential change points, yielding speedups of several orders of magnitude. the results of the improved dynamic programming method correspond very closely with the posterior averages produced by the mcmc methods.
sleeved coclustering. a cocluster of a m x n matrix x is a submatrix determined by a subset of the rows and a subset of the columns. the problem of finding coclusters with specific properties is of interest, in particular, in the analysis of microarray experiments. in that case the entries of the matrix x are the expression levels of $m$ genes in each of $n$ tissue samples. one goal of the analysis is to extract a subset of the samples and a subset of the genes, such that the expression levels of the chosen genes behave similarly across the subset of the samples, presumably reflecting an underlying regulatory mechanism governing the expression level of the genes.we propose to base the similarity of the genes in a cocluster on a simple biological model, in which the strength of the regulatory mechanism in sample j is hj, and the response strength of gene i to the regulatory mechanism is gi. in other words, every two genes participating in a good cocluster should have expression values in each of the participating samples, whose ratio is a constant depending only on the two genes. noise in the expression levels of genes is taken into account by allowing a deviation from the model, measured by a relative error criterion. the sleeve-width of the cocluster reflects the extent to which entry i,j in the cocluster is allowed to deviate, relatively, from being expressed as the product gihj.we present a polynomial-time monte-carlo algorithm which outputs a list of coclusters whose sleeve-widths do not exceed a prespecified value. moreover, we prove that the list includes, with fixed probability, a cocluster which is near-optimal in its dimensions. extensive experimentation with synthetic data shows that the algorithm performs well.
a distributed learning framework for heterogeneous data sources. we present a probabilistic model-based framework for distributed learning that takes into account privacy restrictions and is applicable to scenarios where the different sites have diverse, possibly overlapping subsets of features. our framework decouples data privacy issues from knowledge integration issues by requiring the individual sites to share only privacy-safe probabilistic models of the local data, which are then integrated to obtain a global probabilistic model based on the union of the features available at all the sites. we provide a mathematical formulation of the model integration problem using the maximum likelihood and maximum entropy principles and describe iterative algorithms that are guaranteed to converge to the optimal solution. for certain commonly occurring special cases involving hierarchically ordered feature sets or conditional independence, we obtain closed form solutions and use these to propose an efficient alternative scheme by recursive decomposition of the model integration problem. to address interpretability concerns, we also present a modified formulation where the global model is assumed to belong to a specified parametric family. finally, to highlight the generality of our framework, we provide empirical results for various learning tasks such as clustering and classification on different kinds of datasets consisting of continuous vector, categorical and directional attributes. the results show that high quality global models can be obtained without much loss of privacy.
a new multi-view regression approach with an application to customer wallet estimation. motivated by the problem of customer wallet estimation, we propose a new setting for multi-view regression, where we learn a completely unobserved target (in our case, customer wallet) by modeling it as a "central link" in a directed graphical model, connecting multiple sets of observed variables. the resulting conditional independence allows us to reduce the maximum discriminative likelihood estimation problem to a convex optimization problem for exponential linear models. we show that under certain modeling assumptions, in particular, when there exist two conditionally independent views and the noise is gaussian, this problem can be reduced to a single least squares regression. thus, for this specific, but widely applicable setting, the "unsupervised" multi-view problem can be solved via a simple supervised learning approach. this reduction also allows us to test the statistical independence assumptions underlying the graphical model and perform variable selection. we demonstrate the effectiveness of our approach on our motivating problem of customer wallet estimation and on simulation data.
efficient multidimensional data representations based on multiple correspondence analysis. in the on line analytical processing (olap) context, exploration of huge and sparse data cubes is a tedious task which does not always lead to efficient results. in this paper, we couple olap with the multiple correspondence analysis (mca) in order to enhance visual representations of data cubes and thus, facilitate their interpretations and analysis. we also provide a quality criterion to measure the relevance of obtained representations. the criterion is based on a geometric neighborhood concept and a similarity metric between cells of a data cube. experimental results on real data proved the interest and the efficiency of our approach.
aggregating time partitions. partitions of sequential data exist either per se or as a result of sequence segmentation algorithms. it is often the case that the same timeline is partitioned in many different ways. for example, different segmentation algorithms produce different partitions of the same underlying data points. in such cases, we are interested in producing an aggregate partition, i.e., a segmentation that agrees as much as possible with the input segmentations. each partition is defined as a set of continuous non-overlapping segments of the timeline. we show that this problem can be solved optimally in polynomial time using dynamic programming. we also propose faster greedy heuristics that work well in practice. we experiment with our algorithms and we demonstrate their utility in clustering the behavior of mobile-phone users and combining the results of different segmentation algorithms on genomic sequences.
yale: rapid prototyping for complex data mining tasks. kdd is a complex and demanding task. while a large number of methods has been established for numerous problems, many challenges remain to be solved. new tasks emerge requiring the development of new methods or processing schemes. like in software development, the development of such solutions demands for careful analysis, specification, implementation, and testing. rapid prototyping is an approach which allows crucial design decisions as early as possible. a rapid prototyping system should support maximal re-use and innovative combinations of existing methods, as well as simple and quick integration of new ones.this paper describes yale, a free open-source environment forkdd and machine learning. yale provides a rich variety of methods whichallows rapid prototyping for new applications and makes costlyre-implementations unnecessary. additionally, yale offers extensive functionality for process evaluation and optimization which is a crucial property for any kdd rapid prototyping tool. following the paradigm of visual programming eases the design of processing schemes. while the graphical user interface supports interactive design, the underlying xml representation enables automated applications after the prototyping phase.after a discussion of the key concepts of yale, we illustrate the advantages of rapid prototyping for kdd on case studies ranging from data pre-processing to result visualization. these case studies cover tasks like feature engineering, text mining, data stream mining and tracking drifting concepts, ensemble methods and distributed data mining. this variety of applications is also reflected in a broad user base, we counted more than 40,000 downloads during the last twelve months.
extracting targeted data from the web. tom m. mitchell is author of the textbook "machine learning" (mcgraw hill, 1997), president of the american association for artificial intelligence and a member of the national research council's computer science and telecommunications board. he is vice president and chief scientist at whizbang labs and is currently on a two-year leave of absence from carnegie mellon university where he is the fredkin professor of learning and ai in the school of computer science and founding director of cmu's center for automated learning and discovery. mitchell's research interests span many areas of machine learning theory and practice. his current work at whizbang labs involves developing machine learning methods for extracting information from text. for example, whizbang has developed the world's largest database of job openings by training its software to automatically locate and extract detailed information from job postings on corporate web sites (see www.flipdog.com).
efficient computations via scalable sparse kernel partial least squares and boosted latent features. kernel partial least squares (kpls) has been known as a generic kernel regression method and proven to be competitive with other kernel regression methods such as support vector machines for regression (svm) and kernel ridge regression. kernel boosted latent features (kblf) is a variant of kpls for any differentiable convex loss functions. it provides a more flexible framework for various predictive modeling tasks such as classification with logistic loss and robust regression with l1 norm loss, etc. however, kpls and kblf solutions are dense and thus not suitable for large-scale computations. sparsification of kpls solutions has been studied for dual and primal forms. for dual sparsity, it requires solving a nonlinear optimization problem at every iteration step and its computational burden limits its applicability to general regression tasks.in this paper, we propose simple heuristics to approximate sparse solutions for kpls and the framework is also applied for sparsifying kblf solutions. the algorithm provides an interesting "path" from a maximum residual criterion based algorithm with orthogonality conditions to the dense kpls/kblf. with the orthogonality, it differentiates itself from many existing forward selection-type algorithms. the computational advantage is illustrated by benchmark datasets and comparison to svm is done.
experimental design for solicitation campaigns. data mining techniques are routinely used by fundraisers to select those prospects from a large pool of candidates who are most likely to make a financial contribution. these techniques often rely on statistical models based on trial performance data. this trial performance data is typically obtained by soliciting a smaller sample of the possible prospect pool. collecting this trial data involves a cost; therefore the fundraiser is interested in keeping the trial size small while still collecting enough data to build a reliable statistical model that will be used to evaluate the remainder of the prospects.we describe an experimental design approach to optimally choose the trial prospects from an existing large pool of prospects. prospects are clustered to render the problem practically tractable. we modify the standard d-optimality algorithm to prevent repeated selection of the same prospect cluster, since each prospect can only be solicited at most once.we assess the benefits of this approach on the kdd-98 data set by comparing the performance of the model based on the optimal trial data set with that of a model based on a randomly selected trial data set of equal size.
information extraction, data mining and joint inference. although information extraction and data mining appear together in many applications, their interface in most current systems would better be described as serial juxtaposition than as tight integration. information extraction populates slots in a database by identifying relevant subsequences of text, but is usually not aware of the emerging patterns and regularities in the database. data mining methods begin from a populated database, and are often unaware of where the data came from, or its inherent uncertainties. the result is that the accuracy of both suffers, and accurate mining of complex text sources has been beyond reach.in this talk i will describe work in probabilistic models that perform joint inference across multiple components of an information processing pipeline in order to avoid the brittle accumulation of errors. after briefly introducing conditional random fields, i will describe recent work in information extraction leveraging factorial state representations, entity resolution, and transfer learning, as well as scalable methods of inference and learning. i'll close with some recent work on probabilistic models for social network analysis, and a demonstration of rexa.info, a new research paper search engine.
data filtering for automatic classification of rocks from reflectance spectra. the ability to identify the mineral composition of rocks and soils is an important tool for the exploration of geological sites. for instance, nasa intends to design robots that are sufficiently autonomous to perform this task on planetary missions. spectrometer readings provide one important source of data for identifying sites with minerals of interest. reflectance spectrometers measure intensities of light reflected from surfaces over a range of wavelengths. spectral intensity patterns may in some cases be sufficiently distinctive for proper identification of minerals or classes of minerals. for some mineral classes, carbonates for example, specific short spectral intervals are known to carry a distinctive signature. finding similar distinctive spectral ranges for other mineral classes is not an easy problem. we propose and evaluate data-driven techniques that automatically search for spectral ranges optimized for specific minerals. in one set of studies, we partition the whole interval of wavelengths available in our data into sub-intervals, or bins, and use a genetic algorithm to evaluate a candidate selection of subintervals. as alternatives to this computationally expensive search technique, we present an entropy-based heuristic that gives higher scores for wavelengths more likely to distinguish between classes, as well as other greedy search procedures. results are presented for four different classes, showing reasonable improvements in identifying some, but not all, of the mineral classes tested.