waashk/dblp huggingface dataset:
new cached-sufficient statistics algorithms for quickly answering statistical questions. this talk is about recent work on new ways to exploit preprocessed views of data tables for tractably solving big statistical queries. we'll describe deployments of these new algorithms in the realms of detecting killer asteroids and unnatural disease outbreaks.in recent years, several groups have looked at methods for pre-storing general sufficient statistics of the data in spatial data structures such as kd-trees and ball-trees so that both frequentist and bayesian statistical operations become fast for large datasets. in this talk we will look at two other classes of optimization required in important statistical queries.the first involves iterating over all spatial regions (big and small). the second involves detection of tracks from noisy intermittent observations separated far apart in time and space. we will also discuss the implications that have arisen from making these operations tractable. we will focus particularly ondetecting all asteroids in the solar system larger than pittsburgh's cathedral of learning (data to be collected over 2006-2010). early detection of emerging diseases based on national monitoring of health-related transactions..
algorithms for time series knowledge mining. temporal patterns composed of symbolic intervals are commonly formulated with allen's interval relations originating in temporal reasoning. this representation has severe disadvantages for knowledge discovery. the time series knowledge representation (tskr) is a new hierarchical language for interval patterns expressing the temporal concepts of coincidence and partial order. we present effective and efficient mining algorithms for such patterns based on itemset techniques. a novel form of search space pruning effectively reduces the size of the mining result to ease interpretation and speed up the algorithms. on a real data set a concise set of tskr patterns can explain the underlying temporal phenomena, whereas the patterns found with allen's relations are far more numerous yet only explain fragments of the data.
understandable models of music collections based on exhaustive feature generation with temporal statistics. data mining in large collections of polyphonic music has recently received increasing interest by companies along with the advent of commercial online distribution of music. important applications include the categorization of songs into genres and the recommendation of songs according to musical similarity and the customer's musical preferences. modeling genre or timbre of polyphonic music is at the core of these tasks and has been recognized as a difficult problem. many audio features have been proposed, but they do not provide easily understandable descriptions of music. they do not explain why a genre was chosen or in which way one song is similar to another. we present an approach that combines large scale feature generation with meta learning techniques to obtain meaningful features for musical similarity. we perform exhaustive feature generation based on temporal statistics and train regression models to summarize a subset of these features into a single descriptor of a particular notion of music. using several such models we produce a concise semantic description of each song. genre classification models based on these semantic features are shown to be better understandable and almost as accurate as traditional methods.
optimizing time series discretization for knowledge discovery. knowledge discovery in time series usually requires symbolic time series. many discretization methods that convert numeric time series to symbolic time series ignore the temporal order of values. this often leads to symbols that do not correspond to states of the process generating the time series and cannot be interpreted meaningfully. we propose a new method for meaningful unsupervised discretization of numeric time series called persist. the algorithm is based on the kullback-leibler divergence between the marginal and the self-transition probability distributions of the discretization symbols. its performance is evaluated on both artificial and real life data in comparison to the most common discretization methods. persist achieves significantly higher accuracy than existing static methods and is robust against noise. it also outperforms hidden markov models for all but very simple cases.
mining frequent neighboring class sets in spatial databases. we consider the problem of finding neighboring class sets. objects of each instance of a neighboring class set are grouped using their euclidean distances from each other. recently, location-based services are growing along with mobile computing infrastructure such as cellular phones and pdas. therefore, we expect to see the development of spatial databases that contains very large number of access records including location information. the most typical type would be a database of point objects. records of the objects may consist of "requested service name," "number of packet transmitted" in addition to x and y coordinate values indicating where the request came from. the algorithm presented here efficiently finds sets of "service names" that were frequently close to each other in the spatial database. for example, it may find a frequent neighboring class set, where "ticket" and "timetable" are frequently requested close to each other. by recognizing this, location-based service providers can promote a "ticket" service for customers who access the "timetable."
key semantics extraction by dependency tree mining. we propose a new text mining system which extracts characteristic contents from given documents. we define key semantics as characteristic sub-structures of syntactic dependencies in the given documents, and consider the following three tasks in this paper: 1)key semantics extraction: extracting characteristic syntactic dependency structures not only as ordered trees but also as unordered trees and free trees, 2)redundancy reduction: from the result of extraction, deleting redundant dependency structures such as sub-structures or equivalent structures of the others, and 3)phrase/sentence reconstruction: generating a phrase or sentence in a natural language corresponding to the extracted structure.our system is a combination of natural language processing techniques and tree mining techniques. the system consists of the following five units: 1) syntactic dependency analysis unit, 2) input filters, 3) characteristic ordered subtree extraction unit, 4) output filters, and 5) phrase/sentence reconstruction unit. although ordered trees are extracted in the third unit, the overall behavior of the system can be switched into the extraction of ordered trees, unordered trees, or free trees depending on which of the input filters is/are applied in the second step. the output filters delete redundant trees from the extraction result for efficient knowledge discovery. finally, phrases or sentences corresponding to the extracted subtrees are reconstructed by utilizing the input documents.we demonstrate the validity of our system by showing experimental results using real data collected at a help desk and tdt pilot corpus.
tracking dynamics of topic trends using a finite mixture model. in a wide range of business areas dealing with text data streams, including crm, knowledge management, and web monitoring services, it is an important issue to discover topic trends and analyze their dynamics in real-time. specifically we consider the following three tasks in topic trend analysis: 1)topic structure identification; identifying what kinds of main topics exist and how important they are, 2)topic emergence detection; detecting the emergence of a new topic and recognizing how it grows, 3)topic characterization; identifying the characteristics for each of main topics. for real topic analysis systems, we may require that these three tasks be performed in an on-line fashion rather than in a retrospective way, and be dealt with in a single framework. this paper proposes a new topic analysis framework which satisfies this requirement from a unifying viewpoint that a topic structure is modeled using a finite mixture model and that any change of a topic trend is tracked by learning the finite mixture model dynamically. in this framework we propose the usage of a time-stamp based discounting learning algorithm in order to realize real-time topic structure identification. this enables tracking the topic structure adaptively by forgetting out-of-date statistics. further we apply the theory of dynamic model selection to detecting changes of main components in the finite mixture model in order to realize topic emergence detection. we demonstrate the effectiveness of our framework using real data collected at a help desk to show that we are able to track dynamics of topic trends in a timely fashion.
distributed cooperative mining for information consortia. we consider the situation where a number of agents are distributed and each of them collects a data sequence generated according to an unknown probability distribution. here each of the distributions is specified by common parameters and individual parameters e.g., a normal distribution with an identical mean and a different variance. here we introduce a notion of an information consortium, which is a framework where the agents cannot show raw data to one another, but they like to enjoy significant information gain for estimating the respective distributions. such an information consortium has recently received much interest in a broad range of areas including financial risk management, ubiquitous network mining, etc. in this paper we are concerned with the following three issues: 1) how to design a collaborative strategy for agents to estimate the respective distributions in the information consortium, 2) characterizing when each agent has a benefit in terms of information gain for estimating its distribution or information loss for predicting future data, and 3) charracterizing how much benefit each agent obtains. in this paper we yield a statistical formulation of information consortia and solve all of the above three problems for a general form of probability distributions. specifically we propose a basic strategy for cooperative estimation and derive a necessary and sufficient condition for each agent to have a significant benefit.
mining product reputations on the web. knowing the reputations of your own and/or competitors' products is important for marketing and customer relationship management. it is, however, very costly to collect and analyze survey data manually. this paper presents a new framework for mining product reputations on the internet. it automatically collects people's opinions about target products from web pages, and it uses text mining techniques to obtain the reputations of those products.on the basis of human-test samples, we generate in advance syntactic and linguistic rules to determine whether any given statement is an opinion or not, as well as whether such any opinion is positive or negative in nature. we first collect statements regarding target products using a general search engine, and then, using the rules, extract opinions from among them and attach three labels to each opinion, labels indicating the positive/negative determination, the product name itself, and an numerical value expressing the degree of system confidence that the statement is, in fact, an opinion. the labeled opinions are then input into an opinion database.the mining of reputations, i.e., the finding of statistically meaningful information included in the database, is then conducted. we specify target categories using label values (such as positive opinions of product a) and perform four types of text mining: extraction of 1) characteristic words, 2) co-occurrence words, 3) typical sentences, for individual target categories, and 4) correspondence analysis among multiple target categories.actual marketing data is used to demonstrate the validity and effectiveness of the framework, which offers a drastic reduction in the overall cost of reputation analysis over that of conventional survey approaches and supports the discovery of knowledge from the pool of opinions on the web.
machine learning for online query relaxation. in this paper we provide a fast, data-driven solution to the failing query problem: given a query that returns an empty answer, how can one relax the query's constraints so that it returns a non-empty set of tuples? we introduce a novel algorithm, loqr, which is designed to relax queries that are in the disjunctive normal form and contain a mixture of discrete and continuous attributes. loqr discovers the implicit relationships that exist among the various domain attributes and then uses this knowledge to relax the constraints from the failing query.in a first step, loqr uses a small, randomly-chosen subset of the target database to learn a set of decision rules that predict whether an attribute's value satisfies the constraints in the failing query; this query-driven operation is performed online for each failing query. in the second step, loqr uses nearest-neighbor techniques to find the learned rule that is the most similar to the failing query; then it uses the attributes' values from this rule to relax the failing query's constraints. our experiments on six application domains show that loqr is both robust and fast: it successfully relaxes more than 95% of the failing queries, and it takes under a second for processing queries that consist of up to 20 attributes (larger queries of up to 93 attributes are processed in several seconds).
mining traffic data from probe-car system for travel time prediction. we are developing a technique to predict travel time of a vehicle for an objective road section, based on real time traffic data collected through a probe-car system. in the area of intelligent transport system (its), travel time prediction is an important subject. probe-car system is an upcoming data collection method, in which a number of vehicles are used as moving sensors to detect actual traffic situation. it can collect data concerning much larger area, compared with traditional fixed detectors. our prediction technique is based on statistical analysis using ar model with seasonal adjustment and mdl (minimum description length) criterion. seasonal adjustment is used to handle periodicities of 24 hours in traffic data. alternatively, we employ state space model, which can handle time series with periodicities. it is important to select really effective data for prediction, among the data from widespread area, which are collected via probe-car system. we do this using mdl criterion. that is, we find the explanatory variables that really have influence on the future travel time. in this paper, we experimentally show effectiveness of our method using probe-car data collected in nagoya metropolitan area in 2002.
using retrieval measures to assess similarity in mining dynamic web clickstreams. while scalable data mining methods are expected to cope with massive web data, coping with evolving trends in noisy data in a continuous fashion, and without any unnecessary stoppages and reconfigurations is still an open challenge. this dynamic and single pass setting can be cast within the framework of mining evolving data streams. in this paper, we explore the task of mining mass user profiles by discovering evolving web session clusters in a single pass with a recently proposed scalable immune based clustering approach (tecno-streams), and study the effect of the choice of different similarity measures on the mining process and on the interpretation of the mined patterns. we propose a simple similarity measure that has the advantage of explicitly coupling the precision and coverage criteria to the early learning stages, and furthermore requiring that the affinity of the data to the learned profiles or summaries be defined by the minimum of their coverage or precision, hence requiring that the learned profiles are simultaneously precise and complete, with no compromises.in our experiments, we study the task of mining evolving user profiles from web clickstream data (web usage mining) in a single pass, and under different trend sequencing scenarios, showing that compared oto the cosine similarity measure, the proposed similarity measure explicitly based on precision and coverage allows the discovery of more correct profiles at the same precision or recall quality levels.
clustering based large margin classification: a scalable approach using socp formulation. this paper presents a novel second order cone programming (socp) formulation for large scale binary classification tasks. assuming that the class conditional densities are mixture distributions, where each component of the mixture has a spherical covariance, the second order statistics of the components can be estimated efficiently using clustering algorithms like birch. for each cluster, the second order moments are used to derive a second order cone constraint via a chebyshev-cantelli inequality. this constraint ensures that any data point in the cluster is classified correctly with a high probability. this leads to a large margin socp formulation whose size depends on the number of clusters rather than the number of training data points. hence, the proposed formulation scales well for large datasets when compared to the state-of-the-art classifiers, support vector machines (svms). experiments on real world and synthetic datasets show that the proposed algorithm outperforms svm solvers in terms of training time and achieves similar accuracies.
semantic representation: search and mining of multimedia content. semantic understanding of multimedia content is critical in enabling effective access to all forms of digital media data. by making large media repositories searchable, semantic content descriptions greatly enhance the value of such data. automatic semantic understanding is a very challenging problem and most media databases resort to describing content in terms of low-level features or using manually ascribed annotations. recent techniques focus on detecting semantic concepts in video, such as indoor, outdoor, face, people, nature, etc. this approach works for a fixed lexicon for which annotated training examples exist. in this paper we consider the problem of using such semantic concept detection to map the video clips into semantic spaces. this is done by constructing a model vector that acts as a compact semantic representation of the underlying content. we then present experiments in the semantic spaces leveraging such information for enhanced semantic retrieval, classification, visualization, and data mining purposes. we evaluate these ideas using a large video corpus and demonstrate significant performance gains in retrieval effectiveness.
rapid detection of significant spatial clusters. given an n x n grid of squares, where each square has a count cij and an underlying population pij, our goal is to find the rectangular region with the highest density, and to calculate its significance by randomization. an arbitrary density function d, dependent on a region's total count c and total population p, can be used. for example, if each count represents the number of disease cases occurring in that square, we can use kulldorff's spatial scan statistic dk to find the most significant spatial disease cluster. a naive approach to finding the maximum density region requires o(n4) time, and is generally computationally infeasible. we present a multiresolution algorithm which partitions the grid into overlapping regions using a novel overlap-kd tree data structure, bounds the maximum score of subregions contained in each region, and prunes regions which cannot contain the maximum density region. for sufficiently dense regions, this method finds the maximum density region in o((n log n)2) time, in practice resulting in significant (20-2000x) speedups on both real and simulated datasets.
detection of emerging space-time clusters. we propose a new class of spatio-temporal cluster detection methods designed for the rapid detection of emerging space-time clusters. we focus on the motivating application of prospective disease surveillance: detecting space-time clusters of disease cases resulting from an emerging disease outbreak. automatic, real-time detection of outbreaks can enable rapid epidemiological response, potentially reducing rates of morbidity and mortality. building on the prior work on spatial and space-time scan statistics, our methods combine time series analysis (to determine how many cases we expect to observe for a given spatial region in a given time interval) with new "emerging cluster" space-time scan statistics (to decide whether an observed increase in cases in a region is significant), enabling fast and accurate detection of emerging outbreaks. we evaluate these methods on two types of simulated outbreaks: aerosol release of inhalational anthrax (e.g. from a bioterrorist attack) and floo ("fictional linear onset outbreak"), injected into actual baseline data (emergency department records and over-the-counter drug sales data from allegheny county). we demonstrate that our methods are successful in rapidly detecting both outbreak types while keeping the number of false positives low, and show that our new "emerging cluster" scan statistics consistently outperform the standard "persistent cluster" scan statistics approach.
learning relational probability trees. classification trees are widely used in the machine learning and data mining communities for modeling propositional data. recent work has extended this basic paradigm to probability estimation trees. traditional tree learning algorithms assume that instances in the training data are homogenous and independently distributed. relational probability trees (rpts) extend standard probability estimation trees to a relational setting in which data instances are heterogeneous and interdependent. our algorithm for learning the structure and parameters of an rpt searches over a space of relational features that use aggregation functions (e.g. average, mode, count) to dynamically propositionalize relational data and create binary splits within the rpt. previous work has identified a number of statistical biases due to characteristics of relational data such as autocorrelation and degree disparity. the rpt algorithm uses a novel form of randomization test to adjust for these biases. on a variety of relational learning tasks, rpts built using randomization tests are significantly smaller than other models and achieve equivalent, or better, performance.
using relational knowledge discovery to prevent securities fraud. we describe an application of relational knowledge discovery to a key regulatory mission of the national association of securities dealers (nasd). nasd is the world's largest private-sector securities regulator, with responsibility for preventing and discovering misconduct among securities brokers. our goal was to help focus nasd's limited regulatory resources on the brokers who are most likely to engage in securities violations. using statistical relational learning algorithms, we developed models that rank brokers with respect to the probability that they would commit a serious violation of securities regulations in the near future. our models incorporate organizational relationships among brokers (e.g., past coworker), which domain experts consider important but have not been easily used before now. the learned models were subjected to an extensive evaluation using more than 18 months of data unseen by the model developers and comprising over two person weeks of effort by nasd staff. model predictions were found to correlate highly with the subjective evaluations of experienced nasd examiners. furthermore, in all performance measures, our models performed as well as or better than the handcrafted rules that are currently in use at nasd.