waashk/dblp huggingface dataset:
mining statistically important equivalence classes and delta-discriminative emerging patterns. the support-confidence framework is the most common measure used in itemset mining algorithms, for its antimonotonicity that effectively simplifies the search lattice. this computational convenience brings both quality and statistical flaws to the results as observed by many previous studies. in this paper, we introduce a novel algorithm that produces itemsets with ranked statistical merits under sophisticated test statistics such as chi-square, risk ratio, odds ratio, etc. our algorithm is based on the concept of equivalence classes. an equivalence class is a set of frequent itemsets that always occur together in the same set of transactions. therefore, itemsets within an equivalence class all share the same level of statistical significance regardless of the variety of test statistics. as an equivalence class can be uniquely determined and concisely represented by a closed pattern and a set of generators, we just mine closed patterns and generators, taking a simultaneous depth-first search scheme. this parallel approach has not been exploited by any prior work. we evaluate our algorithm on two aspects. in general, we compare to lcm and fpclose which are the best algorithms tailored for mining only closed patterns. in particular, we compare to epminer which is the most recent algorithm for mining a type of relative risk patterns, known as minimal emerging patterns. experimental results show that our algorithm is faster than all of them, sometimes even multiple orders of magnitude faster. these statistically ranked patterns and the efficiency have a high potential for real-life applications, especially in biomedical and financial fields where classical test statistics are of dominant interest.
boostcluster: boosting clustering by pairwise constraints. data clustering is an important task in many disciplines. a large number of studies have attempted to improve clustering by using the side information that is often encoded as pairwise constraints. however, these studies focus on designing special clustering algorithms that can effectively exploit the pairwise constraints. we present a boosting framework for data clustering,termed as boostcluster, that is able to iteratively improve the accuracy of any given clustering algorithm by exploiting the pairwise constraints. the key challenge in designing a boosting framework for data clustering is how to influence an arbitrary clustering algorithm with the side information since clustering algorithms by definition are unsupervised. the proposed framework addresses this problem by dynamically generating new data representations at each iteration that are, on the one hand, adapted to the clustering results at previous iterations by the given algorithm, and on the other hand consistent with the given side information. our empirical study shows that the proposed boosting framework is effective in improving the performance of a number of popular clustering algorithms (k-means, partitional singlelink, spectral clustering), and its performance is comparable to the state-of-the-art algorithms for data clustering with side information.
efficient mining of iterative patterns for software specification discovery. studies have shown that program comprehension takes up to 45% of software development costs. such high costs are caused by the lack-of documented specification and further aggravated by the phenomenon of software evolution. there is a need for automated tools to extract specifications to aid program comprehension. in this paper, a novel technique to efficiently mine common software temporal patterns from traces is proposed. these patterns shed light on program behaviors, and are termed iterative patterns. they capture unique characteristic of software traces, typically not found in arbitrary sequences. specifically, due to loops, interesting iterative patterns can occur multiple times within a trace. furthermore, an occurrence of an iterative pattern in a trace can extend across a sequence of indefinite length. since a program behavior can be manifested in numerous ways, analyzing a single trace will not be sufficient. iterative pattern mining extends sequential pattern and episode minings to discover frequent iterative patterns which occur repetitively both within a program trace and across multiple traces. in this paper, we present cliper (closed iterative pattern miner) to efficiently mine a closed set of iterative patterns. a performance study on several simulated and real datasets shows the efficiency of our mining algorithm and effectiveness of our pruning strategy. our case study on jboss application server confirms the usefulness of mined patterns in discovering interesting software behavioral specification.
a probabilistic framework for relational clustering. relational clustering has attracted more and more attention due to its phenomenal impact in various important applications which involve multi-type interrelated data objects, such as web mining, search marketing, bioinformatics, citation analysis, and epidemiology. in this paper, we propose a probabilistic model for relational clustering, which also provides a principal framework to unify various important clustering tasks including traditional attributes-based clustering, semi-supervised clustering, co-clustering and graph clustering. the proposed model seeks to identify cluster structures for each type of data objects and interaction patterns between different types of objects. under this model, we propose parametric hard and soft relational clustering algorithms under a large number of exponential family distributions. the algorithms are applicable to relational data of various structures and at the same time unifies a number of stat-of-the-art clustering algorithms: co-clustering algorithms, the k-partite graph clustering, bregman k-means, and semi-supervised clustering based on hidden markov random fields.
nestedness and segmented nestedness. consider each row of a 0-1 dataset as the subset of the columns for which the row has an 1. then a dataset is nested, if for all pairs of rows one row is either a superset or subset of the other. the concept of nestedness has its origins in ecology, where approximate versions of it has been used to model the species distribution in different locations. we argue that nestedness and its extensions are interesting properties of datasets, and that they can be applied also to domains other than ecology. we first define natural measures of nestedness and study their properties. we then define the concept of k-nestedness: a dataset is (almost) k-nested if the set of columns can be partitioned to k parts so that each part is (almost) nested. we consider the algorithmic problems of computing how far a dataset is from being k-nested, and for finding a good partition of the columns into k parts. the algorithms are based on spectral partitioning, and scale to moderately large datasets. we apply the methods to real data from ecology and from other applications, and demonstrate the usefulness of the concept.
expertise modeling for matching papers with reviewers. an essential part of an expert-finding task, such as matching reviewers to submitted papers, is the ability to model the expertise of a person based on documents. we evaluate several measures of the association between an author in an existing collection of research papers and a previously unseen document. we compare two language model based approaches with a novel topic model, author-persona-topic (apt). in this model, each author can write under one or more "personas," which are represented as independent distributions over hidden topics. examples of previous papers written by prospective reviewers are gathered from the rexa database, which extracts and disambiguates author mentions from documents gathered from the web. we evaluate the models using a reviewer matching task based on human relevance judgments determining how well the expertise of proposed reviewers matches a submission. we find that the apt topic model outperforms the other models.
multiscale topic tomography. modeling the evolution of topics with time is of great value in automatic summarization and analysis of large document collections. in this work, we propose a new probabilistic graphical model to address this issue. the new model, which we call the multiscale topic tomography model (mttm), employs non-homogeneous poisson processes to model generation of word-counts. the evolution of topics is modeled through a multi-scale analysis using haar wavelets. one of the new features of the model is its modeling the evolution of topics at various time-scales of resolution, allowing the user to zoom in and out of the time-scales. our experiments on science data using the new model uncovers some interesting patterns in topics. the new model is also comparable to lda in predicting unseen data as demonstrated by our perplexity experiments.
mining optimal decision trees from itemset lattices. we present dl8, an exact algorithm for finding a decision tree that optimizes a ranking function under size, depth, accuracy and leaf constraints. because the discovery of optimal trees has high theoretical complexity, until now few efforts have been made to compute such trees for real-world datasets. an exact algorithm is of both scientific and practical interest. from a scientific point of view, it can be used as a gold standard to evaluate the performance of heuristic constraint-based decision tree learners and to gain new insight in traditional decision tree learners. from the application point of view, it can be used to discover trees that cannot be found by heuristic decision tree learners. the key idea behind our algorithm is that there is a relation between constraints on decision trees and constraints on itemsets. we show that optimal decision trees can be extracted from lattices of itemsets in linear time. we give several strategies to efficiently build these lattices. experiments show that under the same constraints, dl8 obtains better results than c4.5, which confirms that exhaustive search does not always imply overfitting. the results also show that dl8 is a useful and interesting tool to learn decision trees under constraints.
domain-constrained semi-supervised mining of tracking models in sensor networks. accurate localization of mobile objects is a major research problem in sensor networks and an important data mining application. specifically, the localization problem is to determine the location of a client device accurately given the radio signal strength values received at the client device from multiple beacon sensors or access points. conventional data mining and machine learning methods can be applied to solve this problem. however, all of them require large amounts of labeled training data, which can be quite expensive. in this paper, we propose a probabilistic semi supervised learning approach to reduce the calibration effort and increase the tracking accuracy. our method is based on semi-supervised conditional random fields which can enhance the learned model from a small set of training data with abundant unlabeled data effectively. to make our method more efficient, we exploit a generalized em algorithm coupled with domain constraints. we validate our method through extensive experiments in a real sensor network using crossbow mica2 sensors. the results demonstrate the advantages of methods compared to other state-of-the-art object-tracking algorithms.
applying collaborative filtering techniques to movie search for better ranking and browsing. we propose a new ranking method, which combines recommender systems with information search tools for better search and browsing. our method uses a collaborative filtering algorithm to generate personal item authorities for each user and combines them with item proximities for better ranking. to demonstrate our approach, we build a prototype movie search and browsing engine called mad6 (movies, actors and directors; 6 degrees of separation). we conduct offline and online tests of our ranking algorithm. for offline testing, we use yahoo! search queries that resulted in a click on a yahoo! movies or internet movie database (imdb) movie url. our online test involved 44 yahoo! employees providing subjective assessments of results quality. in both tests, our ranking methods show significantly better recall and quality than imdb search and yahoo! movies current search.
febrl -: an open source data cleaning, deduplication and record linkage system with a graphical user interface. matching records that refer to the same entity across data-bases is becoming an increasingly important part of many data mining projects, as often data from multiple sources needs to be matched in order to enrich data or improve its quality. significant advances in record linkage techniques have been made in recent years. however, many new techniques are either implemented in research proof-of-concept systems only, or they are hidden within expensive 'black box' commercial software. this makes it difficult for both researchers and practitioners to experiment with new record linkage techniques, and to compare existing techniques with new ones. the febrl (freely extensible biomedical record linkage) system aims to fill this gap. it contains many recently developed techniques for data cleaning, deduplication and record linkage, and encapsulates them into a graphical user interface (gui). febrl thus allows even inexperienced users to learn and experiment with both traditional and new record linkage techniques. because febrl is written in python and its source code is available, it is fairly easy to integrate new record linkage techniques into it. therefore, febrl can be seen as a tool that allows researchers to compare various existing record linkage techniques with their own ones, enabling the record linkage research community to conduct their work more efficiently. additionally, febrl is suitable as a training tool for new record linkage users, and it can also be used for practical linkage projects with data sets that contain up to several hundred thousand records.
structured entity identification and document categorization: two tasks with one joint model. traditionally, research in identifying structured entities in documents has proceeded independently of document categorization research. in this paper, we observe that these two tasks have much to gain from each other. apart from direct references to entities in a database, such as names of person entities, documents often also contain words that are correlated with discriminative entity attributes, such age-group and income-level of persons. this happens naturally in many enterprise domains such as crm, banking, etc. then, entity identification, which is typically vulnerable against noise and incompleteness in direct references to entities in documents, can benefit from document categorization with respect to such attributes. in return, entity identification enables documents to be categorized according to different label-sets arising from entity attributes without requiring any supervision. in this paper, we propose a probabilistic generative model for joint entity identification and document categorization. we show how the parameters of the model can be estimated using an em algorithm in an unsupervised fashion. using extensive experiments over real and semi-synthetic data, we demonstrate that the two tasks can benefit immensely from each other when performed jointly using the proposed model.
locality sensitive hash functions based on concomitant rank order statistics. locality sensitive hash functions are invaluable tools for approximate near neighbor problems in high dimensional spaces. in this work, we are focused on lsh schemes where the similarity metric is the cosine measure. the contribution of this work is a new class of locality sensitive hash functions for the cosine similarity measure based on the theory of concomitants, which arises in order statistics. consider n i.i.d sample pairs, {(x1; y1); (x2; y2); : : : ;(xn; yn)} obtained from a bivariate distribution f(x, y). concomitant theory captures the relation between the order statistics of x and y in the form of a rank distribution given by prob(rank(yi)=j-rank(xi)=k). we exploit properties of the rank distribution towards developing a locality sensitive hash family that has excellent collision rate properties for the cosine measure. the computational cost of the basic algorithm is high for high hash lengths. we introduce several approximations based on the properties of concomitant order statistics and discrete transforms that perform almost as well, with significantly reduced computational cost. we demonstrate the practical applicability of our algorithms by using it for finding similar images in an image repository.
an inductive database prototype based on virtual mining views. we present a prototype of an inductive database. our system enables the user to query not only the data stored in the database but also generalizations (e.g. rules or trees) over these data through the use of virtual mining views. the mining views are relational tables that virtually contain the complete output of data mining algorithms executed over a given dataset. the prototype implemented into postgresql currently integrates frequent itemset, association rule and decision tree mining. we illustrate the interactive and iterative capabilities of our system with a description of a complete data mining scenario.
context-aware query suggestion by mining click-through and session data. query suggestion plays an important role in improving the usability of search engines. although some recently proposed methods can make meaningful query suggestions by mining query patterns from search logs, none of them are context-aware - they do not take into account the immediately preceding queries as context in query suggestion. in this paper, we propose a novel context-aware query suggestion approach which is in two steps. in the offine model-learning step, to address data sparseness, queries are summarized into concepts by clustering a click-through bipartite. then, from session data a concept sequence suffix tree is constructed as the query suggestion model. in the online query suggestion step, a user's search context is captured by mapping the query sequence submitted by the user to a sequence of concepts. by looking up the context in the concept sequence sufix tree, our approach suggests queries to the user in a context-aware manner. we test our approach on a large-scale search log of a commercial search engine containing 1:8 billion search queries, 2:6 billion clicks, and 840 million query sessions. the experimental results clearly show that our approach outperforms two baseline methods in both coverage and quality of suggestions.
arnetminer: extraction and mining of academic social networks. this paper addresses several key issues in the arnetminer system, which aims at extracting and mining academic social networks. specifically, the system focuses on: 1) extracting researcher profiles automatically from the web; 2) integrating the publication data into the network from existing digital libraries; 3) modeling the entire academic network; and 4) providing search services for the academic network. so far, 448,470 researcher profiles have been extracted using a unified tagging approach. we integrate publications from online web databases and propose a probabilistic framework to deal with the name ambiguity problem. furthermore, we propose a unified modeling approach to simultaneously model topical aspects of papers, authors, and publication venues. search services such as expertise search and people association search have been provided based on the modeling results. in this paper, we describe the architecture and main features of the system. we also present the empirical evaluation of the proposed methods.
get another label? improving data quality and data mining using multiple, noisy labelers. this paper addresses the repeated acquisition of labels for data items when the labeling is imperfect. we examine the improvement (or lack thereof) in data quality via repeated labeling, and focus especially on the improvement of training labels for supervised induction. with the outsourcing of small tasks becoming easier, for example via rent-a-coder or amazon's mechanical turk, it often is possible to obtain less-than-expert labeling at low cost. with low-cost labeling, preparing the unlabeled part of the data can become considerably more expensive than labeling. we present repeated-labeling strategies of increasing complexity, and show several main results. (i) repeated-labeling can improve label quality and model quality, but not always. (ii) when labels are noisy, repeated labeling can be preferable to single labeling even in the traditional setting where labels are not particularly cheap. (iii) as soon as the cost of processing the unlabeled data is not free, even the simple strategy of labeling everything multiple times can give considerable advantage. (iv) repeatedly labeling a carefully chosen set of points is generally preferable, and we present a robust technique that combines different notions of uncertainty to select data points for which quality should be improved. the bottom line: the results show clearly that when labeling is not perfect, selective acquisition of multiple labels is a strategy that data miners should have in their repertoire; for certain label-quality/cost regimes, the benefit is substantial.
bridging centrality: graph mining from element level to group level. despite the pervasiveness of networks as models for real world systems ranging from the internet, the world wide web to gene regulation and scientific collaborations, only a limited number of metrics capable of characterizing these systems are available. the existing metrics for characterizing networks have broad specificity and lack the selectivity for many applications. the purpose of this paper is to identify and critically evaluate a metric, termed bridging centrality, which is highly selective for identifying bridges in networks. the properties of bridges are unique compared to the other network metrics. for a diverse range of data sets, we found that networks are highly susceptible to disruption but robust to loss structural integrity upon targeted deletion of bridging nodes. a novel graph clustering approach, termed `bridge cut', utilizing bridging edges as module boundary is also proposed. the modules identified by the bridge cut algorithm are more effective than the other graph clustering methods. thus, bridging centrality is a network metric with unique properties that may aid in network analysis from element to group level in various areas including systems biology and national security applications.