waashk/dblp huggingface dataset:
exploiting wikipedia as external knowledge for document clustering. in traditional text clustering methods, documents are represented as "bags of words" without considering the semantic information of each document. for instance, if two documents use different collections of core words to represent the same topic, they may be falsely assigned to different clusters due to the lack of shared core words, although the core words they use are probably synonyms or semantically associated in other forms. the most common way to solve this problem is to enrich document representation with the background knowledge in an ontology. there are two major issues for this approach: (1) the coverage of the ontology is limited, even for wordnet or mesh, (2) using ontology terms as replacement or additional features may cause information loss, or introduce noise. in this paper, we present a novel text clustering method to address these two issues by enriching document representation with wikipedia concept and category information. we develop two approaches, exact match and relatedness-match, to map text documents to wikipedia concepts, and further to wikipedia categories. then the text documents are clustered based on a similarity metric which combines document content information, concept information as well as category information. the experimental results using the proposed clustering framework on three datasets (20-newsgroup, tdt2, and la times) show that clustering performance improves significantly by enriching document representation with wikipedia concepts and categories.
primal sparse max-margin markov networks. max-margin markov networks (m3n) have shown great promise in structured prediction and relational learning. due to the kkt conditions, the m3n enjoys dual sparsity. however, the existing m3n formulation does not enjoy primal sparsity, which is a desirable property for selecting significant features and reducing the risk of over-fitting. in this paper, we present an l1-norm regularized max-margin markov network (l1-m3n), which enjoys dual and primal sparsity simultaneously. to learn an l1-m3n, we present three methods including projected sub-gradient, cutting-plane, and a novel em-style algorithm, which is based on an equivalence between l1-m3n and an adaptive m3n. we perform extensive empirical studies on both synthetic and real data sets. our experimental results show that: (1) l1-m3n can effectively select significant features; (2) l1-m3n can perform as well as the pseudo-primal sparse laplace m3n in prediction accuracy, while consistently outperforms other competing methods that enjoy either primal or dual sparsity; and (3) the em-algorithm is more robust than the other two in pre-diction accuracy and time efficiency.
spatial-temporal causal modeling for climate change attribution. attribution of climate change to causal factors has been based predominantly on simulations using physical climate models, which have inherent limitations in describing such a complex and chaotic system. we propose an alternative, data centric, approach that relies on actual measurements of climate observations and human and natural forcing factors. specifically, we develop a novel method to infer causality from spatial-temporal data, as well as a procedure to incorporate extreme value modeling into our method in order to address the attribution of extreme climate events, such as heatwaves. our experimental results on a real world dataset indicate that changes in temperature are not solely accounted for by solar radiance, but attributed more significantly to co2 and other greenhouse gases. combined with extreme value modeling, we also show that there has been a significant increase in the intensity of extreme temperatures, and that such changes in extreme temperature are also attributable to greenhouse gases. these preliminary results suggest that our approach can offer a useful alternative to the simulation-based approach to climate modeling and attribution, and provide valuable insights from a fresh perspective.
fast approximate spectral clustering. spectral clustering refers to a flexible class of clustering procedures that can produce high-quality clusterings on small data sets but which has limited applicability to large-scale problems due to its computational complexity of o(n3) in general, with n the number of data points. we extend the range of spectral clustering by developing a general framework for fast approximate spectral clustering in which a distortion-minimizing local transformation is first applied to the data. this framework is based on a theoretical analysis that provides a statistical characterization of the effect of local distortion on the mis-clustering rate. we develop two concrete instances of our general framework, one based on local k-means clustering (kasp) and one based on random projection trees (rasp). extensive experiments show that these algorithms can achieve significant speedups with little degradation in clustering accuracy. specifically, our algorithms outperform k-means by a large margin in terms of accuracy, and run several times faster than approximate spectral clustering based on the nystrom method, with comparable accuracy and significantly smaller memory footprint. remarkably, our algorithms make it possible for a single machine to spectral cluster data sets with a million observations within several minutes.
extracting discriminative concepts for domain adaptation in text mining. one common predictive modeling challenge occurs in text mining problems is that the training data and the operational (testing) data are drawn from different underlying distributions. this poses a great difficulty for many statistical learning methods. however, when the distribution in the source domain and the target domain are not identical but related, there may exist a shared concept space to preserve the relation. consequently a good feature representation can encode this concept space and minimize the distribution gap. to formalize this intuition, we propose a domain adaptation method that parameterizes this concept space by linear transformation under which we explicitly minimize the distribution difference between the source domain with sufficient labeled data and target domains with only unlabeled data, while at the same time minimizing the empirical loss on the labeled data in the source domain. another characteristic of our method is its capability for considering multiple classes and their interactions simultaneously. we have conducted extensive experiments on two common text mining problems, namely, information extraction and document classification to demonstrate the effectiveness of our proposed method.
a generalized co-hits algorithm and its application to bipartite graphs. recently many data types arising from data mining and web search applications can be modeled as bipartite graphs. examples include queries and urls in query logs, and authors and papers in scientific literature. however, one of the issues is that previous algorithms only consider the content and link information from one side of the bipartite graph. there is a lack of constraints to make sure the final relevance of the score propagation on the graph, as there are many noisy edges within the bipartite graph. in this paper, we propose a novel and general co-hits algorithm to incorporate the bipartite graph with the content information from both sides as well as the constraints of relevance. moreover, we investigate the algorithm based on two frameworks, including the iterative and the regularization frameworks, and illustrate the generalized co-hits algorithm from different views. for the iterative framework, it contains hits and personalized pagerank as special cases. in the regularization framework, we successfully build a connection with hits, and develop a new cost function to consider the direct relationship between two entity sets, which leads to a significant improvement over the baseline method. to illustrate our methodology, we apply the co-hits algorithm, with many different settings, to the application of query suggestion by mining the aol query log data. experimental results demonstrate that coregu-0.5 (i.e., a model of the regularization framework) achieves the best performance with consistent and promising improvements.
connections between the lines: augmenting social networks with text. network data is ubiquitous, encoding collections of relationships between entities such as people, places, genes, or corporations. while many resources for networks of interesting entities are emerging, most of these can only annotate connections in a limited fashion. although relationships between entities are rich, it is impractical to manually devise complete characterizations of these relationships for every pair of entities on large, real-world corpora. in this paper we present a novel probabilistic topic model to analyze text corpora and infer descriptions of its entities and of relationships between those entities. we develop variational methods for performing approximate inference on our model and demonstrate that our model can be practically deployed on large corpora such as wikipedia. we show qualitatively and quantitatively that our model can construct and annotate graphs of relationships and make useful predictions.
snare: a link analytic system for graph labeling and risk detection. classifying nodes in networks is a task with a wide range of applications. it can be particularly useful in anomaly and fraud detection. many resources are invested in the task of fraud detection due to the high cost of fraud, and being able to automatically detect potential fraud quickly and precisely allows human investigators to work more efficiently. many data analytic schemes have been put into use; however, schemes that bolster link analysis prove promising. this work builds upon the belief propagation algorithm for use in detecting collusion and other fraud schemes. we propose an algorithm called snare (social network analysis for risk evaluation). by allowing one to use domain knowledge as well as link knowledge, the method was very successful for pinpointing misstated accounts in our sample of general ledger data, with a significant improvement over the default heuristic in true positive rates, and a lift factor of up to 6.5 (more than twice that of the default heuristic). we also apply snare to the task of graph labeling in general on publicly-available datasets. we show that with only some information about the nodes themselves in a network, we get surprisingly high accuracy of labels. not only is snare applicable in a wide variety of domains, but it is also robust to the choice of parameters and highly scalable-linearly with the number of edges in a graph.
correlated itemset mining in roc space: a constraint programming approach. correlated or discriminative pattern mining is concerned with finding the highest scoring patterns w.r.t. a correlation measure (such as information gain). by reinterpreting correlation measures in roc space and formulating correlated itemset mining as a constraint programming problem, we obtain new theoretical insights with practical benefits. more specifically, we contribute 1) an improved bound for correlated itemset miners, 2) a novel iterative pruning algorithm to exploit the bound, and 3) an adaptation of this algorithm to mine all itemsets on the convex hull in roc space. the algorithm does not depend on a minimal frequency threshold and is shown to outperform several alternative approaches by orders of magnitude, both in runtime and in memory requirements.
sustainable operation and management of data center chillers using temporal data mining. motivation: data centers are a critical component of modern it infrastructure but are also among the worst environmental offenders through their increasing energy usage and the resulting large carbon footprints. efficient management of data centers, including power management, networking, and cooling infrastructure, is hence crucial to sustainability. in the absence of a 'first-principles' approach to manage these complex components and their interactions, data-driven approaches have become attractive and tenable. results: we present a temporal data mining solution to model and optimize performance of data center chillers, a key component of the cooling infrastructure. it helps bridge raw, numeric, time-series information from sensor streams toward higher level characterizations of chiller behavior, suitable for a data center engineer. to aid in this transduction, temporal data streams are first encoded into a symbolic representation, next run-length encoded segments are mined to form frequent motifs in time series, and finally these metrics are evaluated by their contributions to sustainability. a key innovation in our application is the ability to intersperse "don't care" transitions (e.g., transients) in continuous-valued time series data, an advantage we inherit by the application of frequent episode mining to symbolized representations of numeric time series. our approach provides both qualitative and quantitative characterizations of the sensor streams to the data center engineer, to aid him in tuning chiller operating characteristics. this system is currently being prototyped for a data center managed by hp and experimental results from this application reveal the promise of our approach.
anomalous window discovery through scan statistics for linear intersecting paths (sslip). anomalous windows are the contiguous groupings of data points. in this paper, we propose an approach for discovering anomalous windows using scan statistics for linear intersecting paths (sslip). a linear path refers to a path represented by a line with a single dimensional spatial coordinate marking an observation point. our approach for discovering anomalous windows along linear paths comprises of the following distinct steps: (a) cross path discovery: where we identify a subset of intersecting paths to be considered, (b) anomalous window discovery: where we outline three order invariant algorithms, namely sslip, brute force-sslip and central brute force-sslip, for the traversal of the cross paths to identify varying size directional windows along the paths. for identifying an anomalous window we compute an unusualness metric, in the form of a likelihood ratio to indicate the degree of unusualness of this window with respect to the rest of the data. we identify the window with the highest likelihood ratio as our anomalous window, and (c) monte carlo simulations: to ascertain whether this window is truly anomalous and not just a random occurrence we perform hypothesis testing by computing a p-value using monte carlo simulations. we present extensive experimental results in real world accident datasets for various highways with known issues(code and data available from [27], [21]). our results show that our approach indeed is effective in identifying anomalous traffic accident windows along multiple intersecting highways.
user grouping behavior in online forums. online forums represent one type of social media that is particularly rich for studying human behavior in information seeking and diffusing. the way users join communities is a reflection of the changing and expanding of their interests toward information. in this paper, we study the patterns of user participation behavior, and the feature factors that influence such behavior on different forum datasets. we find that, despite the relative randomness and lesser commitment of structural relationships in online forums, users' community joining behaviors display some strong regularities. one particularly interesting observation is that the very weak relationships between users defined by online replies have similar diffusion curves as those of real friendships or co-authorships. we build social selection models, bipartite markov random field (bimrf), to quantitatively evaluate the prediction performance of those feature factors and their relationships. using these models, we show that some features carry supplementary information, and the effectiveness of different features vary in different types of forums. moreover, the results of bimrf with two-star configurations suggest that the feature of user similarity defined by frequency of communication or number of common friends is inadequate to predict grouping behavior, but adding node-level features can improve the fit of the model.
information theoretic regularization for semi-supervised boosting. we present novel semi-supervised boosting algorithms that incrementally build linear combinations of weak classifiers through generic functional gradient descent using both labeled and unlabeled training data. our approach is based on extending information regularization framework to boosting, bearing loss functions that combine log loss on labeled data with the information-theoretic measures to encode unlabeled data. even though the information-theoretic regularization terms make the optimization non-convex, we propose simple sequential gradient descent optimization algorithms, and obtain impressively improved results on synthetic, benchmark and real world tasks over supervised boosting algorithms which use the labeled data alone and a state-of-the-art semi-supervised boosting algorithm.
sentiment analysis of blogs by combining lexical knowledge with text classification. the explosion of user-generated content on the web has led to new opportunities and significant challenges for companies, that are increasingly concerned about monitoring the discussion around their products. tracking such discussion on weblogs, provides useful insight on how to improve products or market them more effectively. an important component of such analysis is to characterize the sentiment expressed in blogs about specific brands and products. sentiment analysis focuses on this task of automatically identifying whether a piece of text expresses a positive or negative opinion about the subject matter. most previous work in this area uses prior lexical knowledge in terms of the sentiment-polarity of words. in contrast, some recent approaches treat the task as a text classification problem, where they learn to classify sentiment based only on labeled training data. in this paper, we present a unified framework in which one can use background lexical information in terms of word-class associations, and refine this information for specific domains using any available training examples. empirical results on diverse domains show that our approach performs better than using background knowledge or training data in isolation, as well as alternative approaches to using lexical knowledge with text classification.
differentially private recommender systems: building privacy into the netflix prize contenders. we consider the problem of producing recommendations from collective user behavior while simultaneously providing guarantees of privacy for these users. specifically, we consider the netflix prize data set, and its leading algorithms, adapted to the framework of differential privacy. unlike prior privacy work concerned with cryptographically securing the computation of recommendations, differential privacy constrains a computation in a way that precludes any inference about the underlying records from its output. such algorithms necessarily introduce uncertainty--i.e., noise--to computations, trading accuracy for privacy. we find that several of the leading approaches in the netflix prize competition can be adapted to provide differential privacy, without significantly degrading their accuracy. to adapt these algorithms, we explicitly factor them into two parts, an aggregation/learning phase that can be performed with differential privacy guarantees, and an individual recommendation phase that uses the learned correlations and an individual's data to provide personalized recommendations. the adaptations are non-trivial, and involve both careful analysis of the per-record sensitivity of the algorithms to calibrate noise, as well as new post-processing steps to mitigate the impact of this noise. we measure the empirical trade-off between accuracy and privacy in these adaptations, and find that we can provide non-trivial formal privacy guarantees while still outperforming the cinematch baseline netflix provides.
intelligent file scoring system for malware detection from the gray list. currently, the most significant line of defense against malware is anti-virus products which focus on authenticating valid software from a white list, blocking invalid software from a black list, and running any unknown software (i.e., the gray list) in a controlled manner. the gray list, containing unknown software programs which could be either normal or malicious, is usually authenticated or rejected manually by virus analysts. unfortunately, along with the development of the malware writing techniques, the number of file samples in the gray list that need to be analyzed by virus analysts on a daily basis is constantly increasing. in this paper, we develop an intelligent file scoring system (ifss for short) for malware detection from the gray list by an ensemble of heterogeneous base-level classifiers derived by different learning methods, using different feature representations on dynamic training sets. to the best of our knowledge, this is the first work of applying such ensemble methods for malware detection. ifss makes it practical for virus analysts to identify malware samples from the huge gray list and improves the detection ability of anti-virus software. it has already been incorporated into the scanning tool of kingsoft's anti-virus software. the case studies on large and real daily collection of the gray list illustrate that the detection ability and efficiency of our ifss system outperforms other popular scanning tools such as nod32 and kaspersky.
: a random walk model for combining trust-based and item-based recommendation. collaborative filtering is the most popular approach to build recommender systems and has been successfully employed in many applications. however, it cannot make recommendations for so-called cold start users that have rated only a very small number of items. in addition, these methods do not know how confident they are in their recommendations. trust-based recommendation methods assume the additional knowledge of a trust network among users and can better deal with cold start users, since users only need to be simply connected to the trust network. on the other hand, the sparsity of the user item ratings forces the trust-based approach to consider ratings of indirect neighbors that are only weakly trusted, which may decrease its precision. in order to find a good trade-off, we propose a random walk model combining the trust-based and the collaborative filtering approach for recommendation. the random walk model allows us to define and to measure the confidence of a recommendation. we performed an evaluation on the epinions dataset and compared our model with existing trust-based and collaborative filtering methods.