waashk/dblp huggingface dataset:
use of ranked cross document evidence trails for hypothesis generation. this paper focuses on detecting how concepts are linked across multiple textdocuments by generating an evidence trail explaining the connection. a traditional search involving, for example, two or more person names willattempt to find documents mentioning both of these individuals. this researchfocuses on a different interpretation of such a query: what is the best evidencetrail across documents that explains a connection between these individuals? for example, allmay be good golfers. a generalization ofthis task involves query terms representing general concepts (e.g. indictment,foreign policy). such queries reflect a special case oftext mining. previous attempts to solve this problem have focused on graphapproaches involving hyperlinked documents, and link analysis tools exploiting named entities. a new robust framework is presented, based on (i) generating concept chain graphs, a hybrid content representation, (ii) performing graph matching to select candidate subgraphs, and (iii) subsequently using graphical models to validate hypotheses using ranked evidence trails. we adapt the duc data set for cross-document summarization to evaluate evidence trails generated by this approach.
weighting versus pruning in rule validation for detecting network and host anomalies. for intrusion detection, the lerad algorithm learns a succinct set of comprehensible rules for detecting anomalies, which could be novel attacks. lerad validates the learned rules on a separate held-out validation set and removes rules that cause false alarms. however, removing rules with possible high coverage can lead to missed detections. we propose to retain these rules and associate weights to them. we present three weighting schemes and our empirical results indicate that, for lerad, rule weighting can detect more attacks than pruning with minimal computational overhead.
enhancing semi-supervised clustering: a feature projection perspective. semi-supervised clustering employs limited supervision in the form of labeled instances or pairwise instance constraints to aid unsupervised clustering and often significantly improves the clustering performance. despite the vast amount of expert knowledge spent on this problem, most existing work is not designed for handling high-dimensional sparse data. this paper thus fills this crucial void by developing a semi-supervised clustering method based on spherical k-means via feature projection (screen). specifically, we formulate the problem of constraint-guided feature projection, which can be nicely integrated with semi-supervised clustering algorithms and has the ability to effectively reduce data dimension. indeed, our experimental results on several real-world data sets show that the screen method can effectively deal with high-dimensional data and provides an appealing clustering performance.
efficient ticket routing by resolution sequence mining. it problem management calls for quick identification of resolvers to reported problems. the efficiency of this process highly depends on ticket routing---transferring problem ticket among various expert groups in search of the right resolver to the ticket. to achieve efficient ticket routing, wise decision needs to be made at each step of ticket transfer to determine which expert group is likely to be, or to lead to the resolver. in this paper, we address the possibility of improving ticket routing efficiency by mining ticket resolution sequences alone, without accessing ticket content. to demonstrate this possibility, a markov model is developed to statistically capture the right decisions that have been made toward problem resolution, where the order of the markov model is carefully chosen according to the conditional entropy obtained from ticket data. we also design a search algorithm, called variable-order multiple active state search(vms), that generates ticket transfer recommendations based on our model. the proposed framework is evaluated on a large set of real-world problem tickets. the results demonstrate that vms significantly improves human decisions: problem resolvers can often be identified with fewer ticket transfers.
the minimum consistent subset cover problem and its applications in data mining. in this paper, we introduce and study the minimum consistent subset cover (mcsc) problem. given a finite ground set x and a constraint t, find the minimum number of consistent subsets that cover x, where a subset of x is consistent if it satisfies t. the mcsc problem generalizes the traditional set covering problem and has minimum clique partition, a dual problem of graph coloring, as an instance. many practical data mining problems in the areas of rule learning, clustering, and frequent pattern mining can be formulated as mcsc instances. in particular, we discuss the minimum rule set problem that minimizes model complexity of decision rules as well as some converse k-clustering problems that minimize the number of clusters satisfying certain distance constraints. we also show how the mcsc problem can find applications in frequent pattern summarization. for any of these mcsc formulations, our proposed novel graph-based generic algorithm cag can be directly applicable. cag starts by constructing a maximal optimal partial solution, then performs an example-driven specific-to-general search on a dynamically maintained bipartite assignment graph to simultaneously learn a set of consistent subsets with small cardinality covering the ground set. our experiments on benchmark datasets show that cag achieves good results compared to existing popular heuristics.
scaling up text classification for large file systems. we combine the speed and scalability of information retrieval with the generally superior classification accuracy offered by machine learning, yielding a two-phase text classifier that can scale to very large document corpora. we investigate the effect of different methods of formulating the query from the training set, as well as varying the query size. in empirical tests on the reuters rcv1 corpus of 806,000 documents, we find runtime was easily reduced by a factor of 27x, with a somewhat surprising gain in f-measure compared with traditional text classification.
exploiting duality in summarization with deterministic guarantees. summarization is an important task in data mining. a major challenge over the past years has been the efficient construction of fixed-space synopses that provide a deterministic quality guarantee, often expressed in terms of a maximum-error metric. histograms and several hierarchical techniques have been proposed for this problem. however, their time and/or space complexities remain impractically high and depend not only on the data set size n, but also on the space budget b. these handicaps stem from a requirement to tabulate all allocations of synopsis space to different regions of the data. in this paper we develop an alternative methodology that dispels these deficiencies, thanks to a fruitful application of the solution to the dual problem: given a maximum allowed error, determine the minimum-space synopsis that achieves it. compared to the state-of-the-art, our histogram construction algorithm reduces time complexity by (at least) a blog2n over logε* factor and our hierarchical synopsis algorithm reduces the complexity by (at least) a factor of log2b over logε* + logn in time and b(1-log b over log n) in space, where ε* is the optimal error. these complexity advantages offer both a space-efficiency and a scalability that previous approaches lacked. we verify the benefits of our approach in practice by experimentation.
scan: a structural clustering algorithm for networks. network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. many algorithms find clusters by maximizing the number of intra-cluster edges. while such algorithms find useful and interesting structures, they tend to fail to identify and isolate two kinds of vertices that play special roles - vertices that bridge clusters (hubs) and vertices that are marginally connected to clusters (outliers). identifying hubs is useful for applications such as viral marketing and epidemiology since hubs are responsible for spreading ideas or disease. in contrast, outliers have little or no influence, and may be isolated as noise in the data. in this paper, we proposed a novel algorithm called scan (structural clustering algorithm for networks), which detects clusters, hubs and outliers in networks. it clusters vertices based on a structural similarity measure. the algorithm is fast and efficient, visiting each vertex only once. an empirical evaluation of the method using both synthetic and real datasets demonstrates superior performance over other methods such as the modularity-based algorithms.
from frequent itemsets to semantically meaningful visual patterns. data mining techniques that are successful in transaction and text data may not be simply applied to image data that contain high-dimensional features and have spatial structures. it is not a trivial task to discover meaningful visual patterns in image databases, because the content variations and spatial dependency in the visual data greatly challenge most existing methods. this paper presents a novel approach to coping with these difficulties for mining meaningful visual patterns. specifically, the novelty of this work lies in the following new contributions: (1) a principled solution to the discovery of meaningful itemsets based on frequent itemset mining; (2) a self-supervised clustering scheme of the high-dimensional visual features by feeding back discovered patterns to tune the similarity measure through metric learning; and (3) a pattern summarization method that deals with the measurement noises brought by the image data. the experimental results in the real images show that our method can discover semantically meaningful patterns efficiently and effectively.
partial example acquisition in cost-sensitive learning. it is often expensive to acquire data in real-world data mining applications. most previous data mining and machine learning research, however, assumes that a fixed set of training examples is given. in this paper, we propose an online cost-sensitive framework that allows a learner to dynamically acquire examples as it learns, and to decide the ideal number of examples needed to minimize the total cost. we also propose a new strategy for partial example acquisition (pas), in which the learner can acquire examples with a subset of attribute values to reduce the data acquisition cost. experiments on uci datasets show that the new pas strategy is an effective method in reducing the total cost for data acquisition.
a framework for community identification in dynamic social networks. we propose frameworks and algorithms for identifying communities in social networks that change over time. communities are intuitively characterized as "unusually densely knit" subsets of a social network. this notion becomes more problematic if the social interactions change over time. aggregating social networks over time can radically misrepresent the existing and changing community structure. instead, we propose an optimization-based approach for modeling dynamic community structure. we prove that finding the most explanatory community structure is np-hard and apx-hard, and propose algorithms based on dynamic programming, exhaustive search, maximum matching, and greedy heuristics. we demonstrate empirically that the heuristics trace developments of community structure accurately for several synthetic and real-world examples.
fast direction-aware proximity for graph mining. in this paper we study asymmetric proximity measures on directed graphs, which quantify the relationships between two nodes or two groups of nodes. the measures are useful in several graph mining tasks, including clustering, link prediction and connection subgraph discovery. our proximity measure is based on the conceptof escape probability. this way, we strive to summarize the multiple facets of nodes-proximity, while avoiding some of the pitfalls to which alternative proximity measures are susceptible. a unique feature of the measures is accounting for the underlying directional information. we put a special emphasis on computational efficiency, and develop fast solutions that are applicable in several settings. our experimental study shows the usefulness of our proposed direction-aware proximity method for several applications, and that our algorithms achieve a significant speedup (up to 50,000x) over straight forward implementations.
scalable look-ahead linear regression trees. most decision tree algorithms base their splitting decisions on a piecewise constant model. often these splitting algorithms are extrapolated to trees with non-constant models at the leaf nodes. the motivation behind look-ahead linear regression trees (llrt) is that out of all the methods proposed to date, there has been no scalable approach to exhaustively evaluate all possible models in the leaf nodes in order to obtain an optimal split. using several optimizations, llrt is able to generate and evaluate thousands of linear regression models per second. this allows for a near-exhaustive evaluation of all possible splits in a node, based on the quality of fit of linear regression models in the resulting branches. we decompose the calculation of the residual sum of squares in such a way that a large part of it is pre-computed. the resulting method is highly scalable. we observe it to obtain high predictive accuracy for problems with strong mutual dependencies between attributes. we report on experiments with two simulated and seven real data sets.
machine learning for stock selection. in this paper, we propose a new method called prototype ranking (pr) designed for the stock selection problem. pr takes into account the huge size of real-world stock data and applies a modified competitive learning technique to predict the ranks of stocks. the primary target of pr is to select the top performing stocks among many ordinary stocks. pr is designed to perform the learning and testing in a noisy stocks sample set where the top performing stocks are usually the minority. the performance of pr is evaluated by a trading simulation of the real stock data. each week the stocks with the highest predicted ranks are chosen to construct a portfolio. in the period of 1978-2004, pr's portfolio earns a much higher average return as well as a higher risk-adjusted return than cooper's method, which shows that the pr method leads to a clear profit improvement.
corroborate and learn facts from the web. the web contains lots of interesting factual information about entities, such as celebrities, movies or products. this paper describes a robust bootstrapping approach to corroborate facts and learn more facts simultaneously. this approach starts with retrieving relevant pages from a crawl repository for each entity in the seed set. in each learning cycle, known facts of an entity are corroborated first in a relevant page to find fact mentions. when fact mentions are found, they are taken as examples for learning new facts from the page via html pattern discovery. extracted new facts are added to the known fact set for the next learning cycle. the bootstrapping process continues until no new facts can be learned. this approach is language-independent. it demonstrated good performance in experiment on country facts. results of a large scale experiment will also be shown with initial facts imported from wikipedia.
pictor: an interactive system for importing data from a website. we present a demonstration of an interactive wrapper induction system, called pictor, which is able to minimize labeling cost, yet extract data with high accuracy from a website. our demonstration will introduce two proposed technologies: record-level wrappers and a wrapper-assisted labeling strategy. these approaches allow pictor to exploit previously generated wrappers, in order to predict similar labels in a partially labeled webpage or a completely new webpage. our experiment results show the effectiveness of the pictor system.
generalized component analysis for text with heterogeneous attributes. we present a class of richly structured, undirected hidden variable models suitable for simultaneously modeling text along with other attributes encoded in different modalities. our model generalizes techniques such as principal component analysis to heterogeneous data types. in contrast to other approaches, this framework allows modalities such as words, authors and timestamps to be captured in their natural, probabilistic encodings. a latent space representation for a previously unseen document can be obtained through a fast matrix multiplication using our method. we demonstrate the effectiveness of our framework on the task of author prediction from 13 years of the nips conference proceedings and for a recipient prediction task using a 10-month academic email archive of a researcher. our approach should be more broadly applicable to many real-world applications where one wishes to efficiently make predictions for a large number of potential outputs using dimensionality reduction in a well defined probabilistic framework.
interpretable nonnegative matrix decompositions. a matrix decomposition expresses a matrix as a product of at least two factor matrices. equivalently, it expresses each column of the input matrix as a linear combination of the columns in the first factor matrix. the interpretability of the decompositions is a key issue in many data-analysis tasks. we propose two new matrix-decomposition problems: the nonnegative cx and nonnegative cur problems, that give naturally interpretable factors. they extend the recently-proposed column and column-row based decompositions, and are aimed to be used with nonnegative matrices. our decompositions represent the input matrix as a nonnegative linear combination of a subset of its columns (or columns and rows). we present two algorithms to solve these problems and provide an extensive experimental evaluation where we assess the quality of our algorithms' results as well as the intuitiveness of nonnegative cx and cur decompositions. we show that our algorithms return intuitive answers with smaller reconstruction errors than the previously-proposed methods for column and column-row decompositions.
truth discovery with multiple conflicting information providers on the web. the world-wide web has become the most important information source for most of us. unfortunately, there is no guarantee for the correctness of information on the web. moreover, different web sites often provide conflicting information on a subject, such as different specifications for the same product. in this paper we propose a new problem called veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that is provided by various web sites. we design a general framework for the veracity problem, and invent an algorithm called truthfinder, which utilizes the relationships between web sites and their information, i.e., a web site is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy web sites. an iterative method is used to infer the trustworthiness of web sites and the correctness of information from each other. our experiments show that truthfinder successfully finds true facts among conflicting information, and identifies trustworthy web sites better than the popular search engines.
mining templates from search result records of search engines. metasearch engine, comparison-shopping and deep web crawling applications need to extract search result records enwrapped in result pages returned from search engines in response to user queries. the search result records from a given search engine are usually formatted based on a template. precisely identifying this template can greatly help extract and annotate the data units within each record correctly. in this paper, we propose a graph model to represent record template and develop a domain independent statistical method to automatically mine the record template for any search engine using sample search result records. our approach can identify both template tags (html tags) and template texts (non-tag texts), and it also explicitly addresses the mismatches between the tag structures and the data structures of search result records. our experimental results indicate that this approach is very effective.
joint optimization of wrapper generation and template detection. many websites have large collections of pages generated dynamically from an underlying structured source like a database. the data of a category are typically encoded into similar pages by a common script or template. in recent years, some value-added services, such as comparison shopping and vertical search in a specific domain, have motivated the research of extraction technologies with high accuracy. almost all previous works assume that input pages of a wrapper induction system conform to a common template and they can be easily identified in terms of a common schema of url. however, we observed that it is hard to distinguish different templates using dynamic urls today. moreover, since extraction accuracy heavily depends on how consistent input pages are, we argue that it is risky to determine whether pages share a common template solely based on urls. instead, we propose a new approach that utilizes similarity between pages to detect templates. our approach separates pages with notable inner differences and then generates wrappers, respectively. experimental results show that our proposed approach is feasible and effective for improving extraction accuracy.
extracting relevant named entities for automated expense reimbursement. expense reimbursement is a time-consuming and labor-intensive process across organizations. in this paper, we present a prototype expense reimbursement system that dramatically reduces the elapsed time and costs involved, by eliminating paper from the process life cycle. our complete solution involves (1) an electronic submission infrastructure that provides multi- channel image capture, secure transport and centralized storage of paper documents; (2) an unconstrained data mining approach to extracting relevant named entities from un-structured document images; (3) automation of auditing procedures that enables automatic expense validation with minimum human interaction. extracting relevant named entities robustly from document images with unconstrained layouts and diverse formatting is a fundamental technical challenge to image-based data mining, question answering, and other information retrieval tasks. in many applications that require such capability, applying traditional language modeling techniques to the stream of ocr text does not give satisfactory result due to the absence of linguistic context. we present an approach for extracting relevant named entities from document images by combining rich page layout features in the image space with language content in the ocr text using a discriminative conditional random field (crf) framework. we integrate this named entity extraction engine into our expense reimbursement solution and evaluate the system performance on large collections of real-world receipt images provided by ibm world wide reimbursement center.