waashk/dblp huggingface dataset:
statistical entity-topic models. the primary purpose of news articles is to convey information about who, what, when and where. but learning and summarizing these relationships for collections of thousands to millions of articles is difficult. while statistical topic models have been highly successful at topically summarizing huge collections of text documents, they do not explicitly address the textual interactions between who/where, i.e. named entities (persons, organizations, locations) and what, i.e. the topics. we present new graphical models that directly learn the relationship between topics discussed in news articles and entities mentioned in each article. we show how these entity-topic models, through a better understanding of the entity-topic relationships, are better at making predictions about entities.
a quickstart in frequent structure mining can make a difference. given a database, structure mining algorithms search for substructures that satisfy constraints such as minimum frequency, minimum confidence, minimum interest and maximum frequency. examples of substructures include graphs, trees and paths. for these substructures many mining algorithms have been proposed. in order to make graph mining more efficient, we investigate the use of the "quickstart principle", which is based on the fact that these classes of structures are contained in each other, thus allowing for the development of structure mining algorithms that split the search into steps of increasing complexity. we introduce the graph/sequence/tree extraction (gaston) algorithm that implements this idea by searching first for frequent paths, then frequent free trees and finally cyclic graphs. we investigate two alternatives for computing the frequency of structures and present experimental results to relate these alternatives.
graph-based anomaly detection. anomaly detection is an area that has received much attention in recent years. it has a wide variety of applications, including fraud detection and network intrusion detection. a good deal of research has been performed in this area, often using strings or attribute-value data as the medium from which anomalies are to be extracted. little work, however, has focused on anomaly detection in graph-based data. in this paper, we introduce two techniques for graph-based anomaly detection. in addition, we introduce a new method for calculating the regularity of a graph, with applications to anomaly detection. we hypothesize that these methods will prove useful both for finding anomalies, and for determining the likelihood of successful anomaly detection within graph-based data. we provide experimental results using both real-world network intrusion data and artificially-created data.
a hit-miss model for duplicate detection in the who drug safety database. the who collaborating centre for international drug monitoring in uppsala, sweden, maintains and analyses the world's largest database of reports on suspected adverse drug reaction incidents that occur after drugs are introduced on the market. as in other post-marketing drug safety data sets, the presence of duplicate records is an important data quality problem and the detection of duplicates in the who drug safety database remains a formidable challenge, especially since the reports are anonymised before submitted to the database. however, to our knowledge no work has been published on methods for duplicate detection in post-marketing drug safety data. in this paper, we propose a method for probabilistic duplicate detection based on the hit-miss model for statistical record linkage described by copas & hilton. we present two new generalisations of the standard hit-miss model: a hit-miss mixture model for errors in numerical record fields and a new method to handle correlated record fields. we demonstrate the effectiveness of the hit-miss model for duplicate detection in the who drug safety database both at identifying the most likely duplicate for a given record (94.7% accuracy) and at discriminating duplicates from random matches (63% recall with 71% precision). the proposed method allows for more efficient data cleaning in post-marketing drug safety data sets, and perhaps other applications throughout the kdd community.
evaluating classifiers' performance in a constrained environment. in this paper, we focus on methodology of finding a classifier with a minimal cost in presence of additional performance constraints. rocch analysis, where accuracy and cost are intertwined in the solution space, was a revolutionary tool for two-class problems. we propose an alternative formulation, as an optimization problem, commonly used in operations research. this approach extends the rocch analysis to allow for locating optimal solutions while outside constraints are present. similarly to the rocch analysis, we combine cost and class distribution while defining the objective function. rather than focusing on slopes of the edges in the convex hull of the solution space, however, we treat cost as an objective function to be minimized over the solution space, by selecting the best performing classifier(s) (one or more vertex in the solution space). the linear programming framework provides a theoretical and computational methodology for finding the vertex (classifier) which minimizes the objective function.
programming the k-means clustering algorithm in sql. using sql has not been considered an efficient and feasible way to implement data mining algorithms. although this is true for many data mining, machine learning and statistical algorithms, this work shows it is feasible to get an efficient sql implementation of the well-known k-means clustering algorithm that can work on top of a relational dbms. the article emphasizes both correctness and performance. from a correctness point of view the article explains how to compute euclidean distance, nearest-cluster queries and updating clustering results in sql. from a performance point of view it is explained how to cluster large data sets defining and indexing tables to store and retrieve intermediate and final results, optimizing and avoiding joins, optimizing and simplifying clustering aggregations, and taking advantage of sufficient statistics. experiments evaluate scalability with synthetic data sets varying size and dimensionality. the proposed k-means implementation can cluster large data sets and exhibits linear scalability.
towards nic-based intrusion detection. we present and evaluate a nic-based network intrusion detection system. intrusion detection at the nic makes the system potentially tamper-proof and is naturally extensible to work in a distributed setting. simple anomaly detection and signature detection based models have been implemented on the nic firmware, which has its own processor and memory. we empirically evaluate such systems from the perspective of quality and performance (bandwidth of acceptable messages) under varying conditions of host load. the preliminary results we obtain are very encouraging and lead us to believe that such nic-based security schemes could very well be a crucial part of next generation network security systems.
experimental comparisons of online and batch versions of bagging and boosting. bagging and boosting are well-known ensemble learning methods. they combine multiple learned base models with the aim of improving generalization performance. to date, they have been used primarily in batch mode, i.e., they require multiple passes through the training data. in previous work, we presented online bagging and boosting algorithms that only require one pass through the training data and presented experimental results on some relatively small datasets. through additional experiments on a variety of larger synthetic and real datasets, this paper demonstrates that our online versions perform comparably to their batch counterparts in terms of classification accuracy. we also demonstrate the substantial reduction in running time we obtain with our online algorithms because they require fewer passes through the training data.
personalization from incomplete data: what you don't know can hurt. clickstream data collected at any web site (site-centric data) is inherently incomplete, since it does not capture users' browsing behavior across sites (user-centric data). hence, models learned from such data may be subject to limitations, the nature of which has not been well studied. understanding the limitations is particularly important since most current personalization techniques are based on site-centric data only. in this paper, we empirically examine the implications of learning from incomplete data in the context of two specific problems: (a) predicting if the remainder of any given session will result in a purchase and (b) predicting if a given user will make a purchase at any future session. for each of these problems we present new algorithms for fast and accurate data preprocessing of clickstream data. based on a comprehensive experiment on user-level clickstream data gathered from 20,000 users' browsing behavior, we demonstrate that models built on user-centric data outperform models built on site-centric data for both prediction tasks.
mining for misconfigured machines in grid systems. grid systems are proving increasingly useful for managing the batch computing jobs of organizations. one well-known example is intel, whose internally developed netbatch system manages tens of thousands of machines. the size, heterogeneity, and complexity of grid systems make them very difficult, however, to configure. this often results in misconfigured machines, which may adversely affect the entire system.we investigate a distributed data mining approach for detection of misconfigured machines. our grid monitoring system (gms) non-intrusively collects data from all sources (log files, system services, etc.) available throughout the grid system. it converts raw data to semantically meaningful data and stores this data on the machine it was obtained from, limiting incurred overhead and allowing scalability. afterwards, when analysis is requested, a distributed outliers detection algorithm is employed to identify misconfigured machines. the algorithm itself is implemented as a recursive workflow of grid jobs. it is especially suited to grid systems, in which the machines might be unavailable most of the time and often fail altogether.
anf: a fast and scalable tool for data mining in massive graphs. graphs are an increasingly important data source, with such important graphs as the internet and the web. other familiar graphs include cad circuits, phone records, gene sequences, city streets, social networks and academic citations. any kind of relationship, such as actors appearing in movies, can be represented as a graph. this work presents a data mining tool, called anf, that can quickly answer a number of interesting questions on graph-represented data, such as the following. how robust is the internet to failures? what are the most influential database papers? are there gender differences in movie appearance patterns? at its core, anf is based on a fast and memory-efficient approach for approximating the complete "neighbourhood function" for a graph. for the internet graph (268k nodes), anf's highly-accurate approximation is more than 700 times faster than the exact computation. this reduces the running time from nearly a day to a matter of a minute or two, allowing users to perform ad hoc drill-down tasks and to repeatedly answer questions about changing data sources. to enable this drill-down, anf employs new techniques for approximating neighbourhood-type functions for graphs with distinguished nodes and/or edges. when compared to the best existing approximation, anf's approach is both faster and more accurate, given the same resources. additionally, unlike previous approaches, anf scales gracefully to handle disk resident graphs. finally, we present some of our results from mining large graphs using anf.
visualizing changes in the structure of data for exploratory feature selection. using visualization techniques to explore and understand high-dimensional data is an efficient way to combine human intelligence with the immense brute force computation power available nowadays. several visualization techniques have been developed to study the cluster structure of data, i.e., the existence of distinctive groups in the data and how these clusters are related to each other. however, only few of these techniques lend themselves to studying how this structure changes if the features describing the data are changed. understanding this relationship between the features and the cluster structure means understanding the features themselves and is thus a useful tool in the feature extraction phase.in this paper we present a novel approach to visualizing how modification of the features with respect to weighting or normalization changes the cluster structure. we demonstrate the application of our approach in two music related data mining projects.
carpenter: finding closed patterns in long biological datasets. the growth of bioinformatics has resulted in datasets with new characteristics. these datasets typically contain a large number of columns and a small number of rows. for example, many gene expression datasets may contain 10,000-100,000 columns but only 100-1000 rows.such datasets pose a great challenge for existing (closed) frequent pattern discovery algorithms, since they have an exponential dependence on the average row length. in this paper, we describe a new algorithm called carpenter that is specially designed to handle datasets having a large number of attributes and relatively small number of rows. several experiments on real bioinformatics datasets show that carpenter is orders of magnitude better than previous closed pattern mining algorithms like closet and charm.
automatic mining of fruit fly embryo images. we present femine, an automatic system for image-based gene expression analysis. we perform experiments on the largest publicly available collection of drosophila ish (in situ hybridization) images, showing that our femine system achieves excellent performance in classification, clustering, and content-based image retrieval. the major innovation of femine is the use of automatically discovered latent spatial "themes" of gene expressions, lges, in the whole-embryo context, as opposed to patterns in nearly disjoint portions of an embryo proposed in previous methods.
automatic multimedia cross-modal correlation discovery. given an image (or video clip, or audio song), how do we automatically assign keywords to it? the general problem is to find correlations across the media in a collection of multimedia objects like video clips, with colors, and/or motion, and/or audio, and/or text scripts. we propose a novel, graph-based approach, "mmg", to discover such cross-modal correlations.our "mmg" method requires no tuning, no clustering, no user-determined constants; it can be applied to any multimedia collection, as long as we have a similarity function for each medium; and it scales linearly with the database size. we report auto-captioning experiments on the "standard" corel image database of 680 mb, where it outperforms domain specific, fine-tuned methods by up to 10 percentage points in captioning accuracy (50% relative improvement).
discovering word senses from text. inventories of manually compiled dictionaries usually serve as a source for word senses. however, they often include many rare senses while missing corpus/domain-specific senses. we present a clustering algorithm called cbc (clustering by committee) that automatically discovers word senses from text. it initially discovers a set of tight clusters called committees that are well scattered in the similarity space. the centroid of the members of a committee is used as the feature vector of the cluster. we proceed by assigning words to their most similar clusters. after assigning an element to a cluster, we remove their overlapping features from the element. this allows cbc to discover the less frequent senses of a word and to avoid discovering duplicate senses. each cluster that a word belongs to represents one of its senses. we also present an evaluation methodology for automatically measuring the precision and recall of discovered senses.
document preprocessing for naive bayes classification and clustering with mixture of multinomials. naive bayes classifier has long been used for text categorization tasks. its sibling from the unsupervised world, the probabilistic mixture of multinomial models, has likewise been successfully applied to text clustering problems. despite the strong independence assumptions that these models make, their attractiveness come from low computational cost, relatively low memory consumption, ability to handle heterogeneous features and multiple classes, and often competitiveness with the top of the line models. recently, there has been several attempts to alleviate the problems of naive bayes by performing heuristic feature transformations, such as idf, normalization by the length of the documents and taking the logarithms of the counts. we justify the use of these techniques and apply them to two problems: classification of products in yahoo! shopping and clustering the vectors of collocated terms in user queries to yahoo! search. the experimental evaluation allows us to draw conclusions about the promise that these transformations carry with regard to alleviating the strong assumptions of the multinomial model.
probabilistic query models for transaction data. we investigate the application of bayesian networks, markov random fields, and mixture models to the problem of query answering for transaction data sets. we formulate two versions of the querying problem: the query selectivity estimation (i.e., finding exact counts for tuples in a data set) and the query generalization problem (i.e., computing the probability that a tuple will occur in new data). we show that frequent itemsets are useful for reducing the original data to a compressed representation and introduce a method to store them using an adtree data structure. in an extension of our earlier work on this topic we propose several new schemes for query answering based on the compressed representation that avoid direct scans of the data at query time. experimental results on real-world transaction data sets provide insights into various tradeoffs involving the offline time for model-building, the online time for query-answering, the memory footprint of the compressed data, and the accuracy of the estimate provided to the query.
disease progression modeling from historical clinical databases. this paper considers the problem of modeling disease progression from historical clinical databases, with the ultimate objective of stratifying patients into groups with clearly distinguishable prognoses or suitability for different treatment strategies. to meet this objective, we describe a procedure that first fits clinical variables measured over time to a disease progression model. the resulting parameter estimates are then used as the basis for a stepwise clustering procedure to stratify patients into groups with distinct survival characteristics. as a practical illustration, we apply this procedure to survival prediction, using a liver transplant database from the national institute of diabetes and digestive and kidney diseases (niddk).
sequential cost-sensitive decision making with reinforcement learning. recently, there has been increasing interest in the issues of cost-sensitive learning and decision making in a variety of applications of data mining. a number of approaches have been developed that are effective at optimizing cost-sensitive decisions when each decision is considered in isolation. however, the issue of sequential decision making, with the goal of maximizing total benefits accrued over a period of time instead of immediate benefits, has rarely been addressed. in the present paper, we propose a novel approach to sequential decision making based on the reinforcement learning framework. our approach attempts to learn decision rules that optimize a sequence of cost-sensitive decisions so as to maximize the total benefits accrued over time. we use the domain of targeted' marketing as a testbed for empirical evaluation of the proposed method. we conducted experiments using approximately two years of monthly promotion data derived from the well-known kdd cup 1998 donation data set. the experimental results show that the proposed method for optimizing total accrued benefits out performs the usual targeted-marketing methodology of optimizing each promotion in isolation. we also analyze the behavior of the targeting rules that were obtained and discuss their appropriateness to the application domain.
on mining cross-graph quasi-cliques. joint mining of multiple data sets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. for example, in cross-market customer segmentation, a group of customers who behave similarly in multiple markets should be considered as a more coherent and more reliable cluster than clusters found in a single market. as another example, in bioinformatics, by joint mining of gene expression data and protein interaction data, we can find clusters of genes which show coherent expression patterns and also produce interacting proteins. such clusters may be potential pathways.in this paper, we investigate a novel data mining problem, mining cross-graph quasi-cliques, which is generalized from several interesting applications such as cross-market customer segmentation and joint mining of gene expression data and protein interaction data. we build a general model for mining cross-graph quasi-cliques, show why the complete set of cross-graph quasi-cliques cannot be found by previous data mining methods, and study the complexity of the problem. while the problem is difficult, we develop an efficient algorithm, crochet, which exploits several interesting and effective techniques and heuristics to efficaciously mine cross-graph quasi-cliques. a systematic performance study is reported on both synthetic and real data sets. we demonstrate some interesting and meaningful cross-graph quasi-cliques in bioinformatics. the experimental results also show that algorithm crochet is efficient and scalable.
extracting collective probabilistic forecasts from web games. game sites on the world wide web draw people from around the world with specialized interests, skills, and knowledge. data from the games often reflects the players' expertise and will to win. we extract probabilistic forecasts from data obtained from three online games: the hollywood stock exchange (hsx), the foresight exchange (fx), and the formula one pick six (f1p6) competition. we find that all three yield accurate forecasts of uncertain future events. in particular, prices of so-called "movie stocks" on hsx are good indicators of actual box office returns. prices of hsx securities in oscar, emmy, and grammy awards correlate well with observed frequencies of winning. fx prices are reliable indicators of future developments in science and technology. collective predictions from players in the f1 competition serve as good forecasts of true race outcomes. in some cases, forecasts induced from game data are more reliable than expert opinions. we argue that web games naturally attract well-informed and well-motivated players, and thus offer a valuable and oft-overlooked source of high-quality data with significant predictive value.