waashk/dblp huggingface dataset:
a general framework for accurate and fast regression by data summarization in random decision trees. predicting the values of continuous variable as a function of several independent variables is one of the most important problems for data mining. a very large number of regression methods, both parametric and nonparametric, have been proposed in the past. however, since the list is quite extensive and many of these models make rather explicit, strong yet different assumptions about the type of applicable problems and involve a lot of parameters and options, choosing the appropriate regression methodology and then specifying the parameter values is a none-trivial, sometimes frustrating, task for data mining practitioners. choosing the inappropriate methodology can have rather disappointing results. this issue is against the general utility of data mining software. for example,linear regression methods are straightforward and well-understood. however, since the linear assumption is very strong, its performance is compromised for complicated non-linear problems. kernel-based methods perform quite well if the kernel functions are selected correctly. in this paper, we propose a straightforward approach based on summarizing the training data using an ensemble of random decisions trees. it requires very little knowledge from the user, yet is applicable to every type of regression problem that we are currently aware of. we have experimented on a wide range of problems including those that parametric methods performwell, a large selection of benchmark datasets for nonparametric regression, as well as highly non-linear stochastic problems. our results are either significantly better than or identical to many approaches that are known to perform well on these problems.
scaling multi-class support vector machines using inter-class confusion. support vector machines (svms) excel at two-class discriminative learning problems. they often outperform generative classifiers, especially those that use inaccurate generative models, such as the na&iuml;ve bayes (nb) classifier. on the other hand, generative classifiers have no trouble in handling an arbitrary number of classes efficiently, and nb classifiers train much faster than svms owing to their extreme simplicity. in contrast, svms handle multi-class problems by learning redundant yes/no (one-vs-others) classifiers for each class, further worsening the performance gap. we propose a new technique for multi-way classification which exploits the accuracy of svms and the speed of nb classifiers. we first use a nb classifier to quickly compute a confusion matrix, which is used to reduce the number and complexity of the two-class svms that are built in the second stage. during testing, we first get the prediction of a nb classifier and use that to selectively apply only a subset of the two-class svms. on standard benchmarks, our algorithm is 3 to 6 times faster than svms and yet matches or even exceeds their accuracy.
mining tree queries in a graph. we present an algorithm for mining tree-shaped patterns in a large graph. novel about our class of patterns is that they can contain constants, and can contain existential nodes which are not counted when determining the number of occurrences of the pattern in the graph. our algorithm has a number of provable optimality properties, which are based on the theory of conjunctive database queries. we propose a database-oriented implementation in sql, and report upon some initial experimental results obtained with our implementation on graph data about food webs, about protein interactions, and about citation analysis.
tumor cell identification using features rules. advances in imaging techniques have led to large repositories of images. there is an increasing demand for automated systems that can analyze complex medical images and extract meaningful information for mining patterns. here, we describe a real-life image mining application to the problem of tumour cell counting. the quantitative analysis of tumour cells is fundamental to characterizing the activity of tumour cells. existing approaches are mostly manual, time-consuming and subjective. efforts to automate the process of cell counting have largely focused on using image processing techniques only. our studies indicate that image processing alone is unable to give accurate results. in this paper, we examine the use of extracted features rules to aid in the process of tumor cell counting. we propose a robust local adaptive thresholding and dynamic water immersion algorithms to segment regions of interesting from background. meaningful features are then extracted from the segmented regions. a number of base classifiers are built to generate features rules to help identify the tumor cell. two voting strategies are implemented to combine the base classifiers into a meta-classifier. experiment results indicate that this process of using extracted features rules to help identify tumor cell leads to better accuracy than pure image processing techniques alone.
creating social networks to improve peer-to-peer networking. we use knowledge discovery techniques to guide the creation of efficient overlay networks for peer-to-peer file sharing. an overlay network specifies the logical connections among peers in a network and is distinct from the physical connections of the network. it determines the order in which peers will be queried when a user is searching for a specific file. to better understand the role of the network overlay structure in the performance of peer-to-peer file sharing protocols, we compare several methods for creating overlay networks. we analyze the networks using data from a campus network for peer-to-peer file sharing that recorded anonymized data on 6,528 users sharing 291,925 music files over an 81-day period. we propose a novel protocol for overlay creation based on a model of user preference identified by latent-variable clustering with hierarchical dirichlet processes (hdps). our simulations and empirical studies show that the clusters of songs created by hdps effectively model user behavior and can be used to create desirable network overlays that outperform alternative approaches.
non-redundant clustering with conditional ensembles. data may often contain multiple plausible clusterings. in order to discover a clustering which is useful to the user, constrained clustering techniques have been proposed to guide the search. typically, these techniques assume background knowledge in the form of explicit information about the desired clustering. in contrast, we consider the setting in which the background knowledge is instead about an undesired clustering. such knowledge may be obtained from an existing classification or precedent algorithm. the problem is then to find a novel, "orthogonal" clustering in the data. we present a general algorithmic framework which makes use of cluster ensemble methods to solve this problem. one key advantage of this approach is that it takes a base clustering method which is used as a black box, allowing the practitioner to select the most appropriate clustering method for the domain. we present experimental results on synthetic and text data which establish the competitiveness of this framework.
the predictive power of online chatter. an increasing fraction of the global discourse is migrating online in the form of blogs, bulletin boards, web pages, wikis, editorials, and a dizzying array of new collaborative technologies. the migration has now proceeded to the point that topics reflecting certain individual products are sufficiently popular to allow targeted online tracking of the ebb and flow of chatter around these topics. based on an analysis of around half a million sales rank values for 2,340 books over a period of four months, and correlating postings in blogs, media, and web pages, we are able to draw several interesting conclusions.first, carefully hand-crafted queries produce matching postings whose volume predicts sales ranks. second, these queries can be automatically generated in many cases. and third, even though sales rank motion might be difficult to predict in general, algorithmic predictors can use online postings to successfully predict spikes in sales rank.
correlating synchronous and asynchronous data streams. in a variety of modern mining applications, data are commonly viewed as infinite time ordered data streams rather as finite data sets stored on disk. this view challenges fundamental assumptions commonly made in the context of several data mining algorithms.in this paper, we study the problem of identifying correlations between multiple data streams. in particular, we propose algorithms capable of capturing correlations between multiple continuous data streams in a highly efficient and accurate manner. our algorithms and techniques are applicable in the case of both synchronous and asynchronous data streaming environments. we capture correlations between multiple streams using the well known technique of singular value decomposition (svd). correlations between data items, and the svd technique in particular, have been repeatedly utilized in an off-line (non stream) data mining problems, for example forecasting, approximate query answering, and data reduction.we propose a methodology based on a combination of dimensionality reduction and sampling to make the svd technique suitable for a data stream context. our techniques are approximate, trading accuracy with performance, and we analytically quantify this tradeoff. we present a through experimental evaluation, using both real and synthetic data sets, from a prototype implementation of our technique, investigating the impact of various parameters in the accuracy of the overall computation. our results indicate, that correlations between multiple data streams can be identified very efficiently and accurately. the algorithms proposed herein, are presented as generic tools, with a multitude of applications on data stream mining problems.
wavelet synopsis for data streams: minimizing non-euclidean error. we consider the wavelet synopsis construction problem for data streams where given n numbers we wish to estimate the data by constructing a synopsis, whose size, say b is much smaller than n. the b numbers are chosen to minimize a suitable error between the original data and the estimate derived from the synopsis.several good one-pass wavelet construction streaming algorithms minimizing the l2 error exist. for other error measures, the problem is less understood. we provide the first one-pass small space streaming algorithms with provable error guarantees (additive approximation) for minimizing a variety of non-euclidean error measures including all weighted lp (including l∞) and relative error lp metrics.in several previous works solutions (for weighted l2, l∞ and maximum relative error) where the b synopsis coefficients are restricted to be wavelet coefficients of the data were proposed. this restriction yields suboptimal solutions on even fairly simple examples. other lines of research, such as probabilistic synopsis, imposed restrictions on how the synopsis was arrived at. to the best of our knowledge this paper is the first paper to address the general problem, without any restriction on how the synopsis is arrived at, as well as provide the first streaming algorithms with guaranteed performance for these classes of error measures.
unweaving a web of documents. we develop an algorithmic framework to decompose a collection of time-stamped text documents into semantically coherent threads. our formulation leads to a graph decomposition problem on directed acyclic graphs, for which we obtain three algorithms --- an exact algorithm that is based on minimum cost flow and two more efficient algorithms based on maximum matching and dynamic programming that solve specific versions of the graph decomposition problem. applications of our algorithms include superior summarization of news search results, improved browsing paradigms for large collections of text-intensive corpora, and integration of time-stamped documents from a variety of sources. experimental results based on over 250,000 news articles from a major newspaper over a period of four years demonstrate that our algorithms efficiently identify robust threads of varying lengths and time-spans.
mining relational data through correlation-based multiple view validation. commercial relational databases currently store vast amounts of real-world data. the data within these relational repositories are represented by multiple relations, which are inter-connected by means of foreign key joins. the mining of such interrelated data poses a major challenge to the data mining community. unfortunately, traditional data mining algorithms usually only explore one relation, the so-called target relation, thus excluding crucial knowledge embedded in the related so-called background relations. in this paper, we propose a novel approach for classifying relational such domains. this strategy employs multiple views to capture crucial information not only from the target relation, but also from related relations. this information is integrated into the relational mining process. the framework presented here, firstly, explore the relational domain to partition its features space into multiple subsets. subsequently, these subsets are used to construct multiple uncorrelated views, based on a novel correlation-based view validation method, against the target concept. finally, the knowledge possessed by multiple views are incorporated into a meta-learning mechanism to augment one another. based on this framework, a wide range of conventional data mining methods can be applied to mine relational databases. our experiments on benchmark real-world data sets show that the proposed method achieves promising results both in terms of overall accuracy obtained and run time, when compared with two other relational data mining approaches.
quantifying trends accurately despite classifier error and class imbalance. this paper promotes a new task for supervised machine learning research: quantification - the pursuit of learning methods for accurately estimating the class distribution of a test set, with no concern for predictions on individual cases. a variant for cost quantification addresses the need to total up costs according to categories predicted by imperfect classifiers. these tasks cover a large and important family of applications that measure trends over time.the paper establishes a research methodology, and uses it to evaluate several proposed methods that involve selecting the classification threshold in a way that would spoil the accuracy of individual classifications. in empirical tests, median sweep methods show outstanding ability to estimate the class distribution, despite wide disparity in testing and training conditions. the paper addresses shifting class priors and costs, but not concept drift in general.
finding similar files in large document repositories. hewlett-packard has many millions of technical support documents in a variety of collections. as part of content management, such collections are periodically merged and groomed. in the process, it becomes important to identify and weed out support documents that are largely duplicates of newer versions. doing so improves the quality of the collection, eliminates chaff from search results, and improves customer satisfaction.the technical challenge is that through workflow and human processes, the knowledge of which documents are related is often lost. we required a method that could identify similar documents based on their content alone, without relying on metadata, which may be corrupt or missing.we present an approach for finding similar files that scales up to large document repositories. it is based on chunking the byte stream to find unique signatures that may be shared in multiple files. an analysis of the file-chunk graph yields clusters of related files. an optional bipartite graph partitioning algorithm can be applied to greatly increase scalability.
pragmatic text mining: minimizing human effort to quantify many issues in call logs. we discuss our experiences in analyzing customer-support issues from the unstructured free-text fields of technical-support call logs. the identification of frequent issues and their accurate quantification is essential in order to track aggregate costs broken down by issue type, to appropriately target engineering resources, and to provide the best diagnosis, support and documentation for most common issues. we present a new set of techniques for doing this efficiently on an industrial scale, without requiring manual coding of calls in the call center. our approach involves (1) a new text clustering method to identify common and emerging issues; (2) a method to rapidly train large numbers of categorizers in a practical, interactive manner; and (3) a method to accurately quantify categories, even in the face of inaccurate classifications and training sets that necessarily cannot match the class distribution of each new month's data. we present our methodology and a tool we developed and deployed that uses these methods for tracking ongoing support issues and discovering emerging issues at hp.
farming the web for systematic business intelligence (invited talk, abstract only). the technologies of data warehousing, data mining, hypertext analysis, information visualization, and web information resources are rapidly converging. the challenge is to architect these technologies into a system for systematic business intelligence for a corporation. we need to move from an information refining process that is often haphazard and narrow to one that is reliable and continuous. web farming is a new area that suggests a methodology and architecture for accomplishing this.
experiments with random projections for machine learning. dimensionality reduction via random projections has attracted considerable attention in recent years. the approach has interesting theoretical underpinnings and offers computational advantages. in this paper we report a number of experiments to evaluate random projections in the context of inductive supervised learning. in particular, we compare random projections and pca on a number of different datasets and using different machine learning methods. while we find that the random projection approach predictively underperforms pca, its computational advantages may make it attractive for certain applications.
integrating feature and instance selection for text classification. instance selection and feature selection are two orthogonal methods for reducing the amount and complexity of data. feature selection aims at the reduction of redundant features in a dataset whereas instance selection aims at the reduction of the number of instances. so far, these two methods have mostly been considered in isolation. in this paper, we present a new algorithm, which we call fis (feature and instance selection) that targets both problems simultaneously in the context of text classificationour experiments on the reuters and 20-newsgroups datasets show that fis considerably reduces both the number of features and the number of instances. the accuracy of a range of classifiers including na&iuml;ve bayes, tan and lb considerably improves when using the fis preprocessed datasets, matching and exceeding that of support vector machines, which is currently considered to be one of the best text classification methods. in all cases the results are much better compared to mutual information based feature selection. the training and classification speed of all classifiers is also greatly improved.
empirical bayesian data mining for discovering patterns in post-marketing drug safety. because of practical limits in characterizing the safety profiles of therapeutic products prior to marketing, manufacturers and regulatory agencies perform post-marketing surveillance based on the collection of adverse reaction reports ("pharmacovigilance").the resulting databases, while rich in real-world information, are notoriously difficult to analyze using traditional techniques. each report may involve multiple medicines, symptoms, and demographic factors, and there is no easily linked information on drug exposure in the reporting population. kdd techniques, such as association finding, are well-matched to the problem, but are difficult for medical staff to apply and interpret.to deploy kdd effectively for pharmacovigilance, lincoln technologies and glaxosmithkline collaborated to create a webbased safety data mining web environment. the analytical core is a high-performance implementation of the mgps (multi-item gamma poisson shrinker) algorithm described previously by dumouchel and pregibon, with several significant extensions and enhancements. the environment offers an interface for specifying data mining runs, a batch execution facility, tabular and graphical methods for exploring associations, and drilldown to case details. substantial work was involved in preparing the raw adverse event data for mining, including harmonization of drug names and removal of duplicate reports.the environment can be used to explore both drug-event and multi-way associations (interactions, syndromes). it has been used to study age/gender effects, to predict the safety profiles of proposed combination drugs, and to separate contributions of individual drugs to safety problems in polytherapy situations.
mining from open answers in questionnaire data. surveys are an important part of marketing and customer relationship management, and open answers (i.e., answers to open questions) in particular may contain valuable information and provide an important basis for making business decisions. we have developed a text mining system that provides a new way for analyzing open answers in questionnaire data. the product is able to perform the following two functions: (a) accurate extraction of characteristics for individual analysis targets, (b) accurate extraction of the relationships among characteristics of analysis targets. in this paper, we describe the working of our text mining system. it employs two statistical learning techniques: rule analysis and correspondence analysis for performing the two functions. our text mining system has already been put into use by a number of large corporations in japan in the performance of text mining on various types of survey data, including open answers about brand images, open answers about company images, complaints about products, comments written on home pages, business reports, and help desk records. in this it has been found to be useful in forming a basis for effective business decisions.
clustering spatial data using random walks. discovering significant patterns that exist implicitly in huge spatial databases is an important computational task. a common approach to this problem is to use cluster analysis. we propose a novel approach to clustering, based on the deterministic analysis of random walks on a weighted graph generated from the data. our approach can decompose the data into arbitrarily shaped clusters of different sizes and densities, overcoming noise and outliers that may blur the natural decomposition of the data. the method requires only o(n log n) time, and one of its variants needs only constant space.
user-centered design for kdd. during initial development, kdd solutions often focus heavily on algorithms, architectures, software, hardware, and systems engineering challenges, without first thoroughly exploring how end-users will employ the new kdd technology. as a result of such "system-centered" design, many useless features are implemented that prolong development and significantly add to life cycle cost, while making the system hard to operate and use. this presentation will describe an alternate "user-centered" approach -- borrowed from the consumer products industry -- that can produce kdd solutions with shorter development cycles, lower costs, and much better usability.