waashk/dblp huggingface dataset:
dynamics of conversations. how do online conversations build? is there a common model that human communication follows? in this work we explore these questions in detail. we analyze the structure of conversations in three different social datasets, namely, usenet groups, yahoo! groups, and twitter. we propose a simple mathematical model for the generation of basic conversation structures and then refine this model to take into account the identities of each member of the conversation.
discriminative topic modeling based on manifold learning. topic modeling has been popularly used for data analysis in various domains including text documents. previous topic models, such as probabilistic latent semantic analysis (plsa) and latent dirichlet allocation (lda), have shown impressive success in discovering low-rank hidden structures for modeling text documents. these models, however, do not take into account the manifold structure of data, which is generally informative for the non-linear dimensionality reduction mapping. more recent models, namely laplacian plsi (lapplsi) and locally-consistent topic model (ltm), have incorporated the local manifold structure into topic models and have shown the resulting benefits. but these approaches fall short of the full discriminating power of manifold learning as they only enhance the proximity between the low-rank representations of neighboring pairs without any consideration for non-neighboring pairs. in this paper, we propose discriminative topic model (dtm) that separates non-neighboring pairs from each other in addition to bringing neighboring pairs closer together, thereby preserving the global manifold structure as well as improving the local consistency. we also present a novel model fitting algorithm based on the generalized em and the concept of pareto improvement. as a result, dtm achieves higher classification performance in a semi-supervised setting by effectively exposing the manifold structure of data. we provide empirical evidence on text corpora to demonstrate the success of dtm in terms of classification accuracy and robustness to parameters compared to state-of-the-art techniques.
large linear classification when data cannot fit in memory. recent advances in linear classification have shown that for applications such as document classification, the training can be extremely efficient. however, most of the existing training methods are designed by assuming that data can be stored in the computer memory. these methods cannot be easily applied to data larger than the memory capacity due to the random access to the disk. we propose and analyze a block minimization framework for data larger than the memory size. at each step a block of data is loaded from the disk and handled by certain learning methods. we investigate two implementations of the proposed framework for primal and dual svms, respectively. as data cannot fit in memory, many design considerations are very different from those for traditional algorithms. experiments using data sets 20 times larger than the memory demonstrate the effectiveness of the proposed method.
versatile publishing for privacy preservation. motivated by the insufficiency of the existing quasi-identifier/sensitive-attribute (qi-sa) framework on modeling real-world privacy requirements for data publishing, we propose a novel versatile publishing scheme with which privacy requirements can be specified as an arbitrary set of privacy rules over attributes in the microdata table. to enable versatile publishing, we introduce the guardian normal form (gnf), a novel method of publishing multiple sub-tables such that each sub-table is anonymized by an existing qi-sa publishing algorithm, while the combination of all published tables guarantees all privacy rules. we devise two algorithms, guardian decomposition (gd) and utility-aware decomposition (uad), for decomposing a microdata table into gnf, and present extensive experiments over real-world datasets to demonstrate the effectiveness of both algorithms.
fast query execution for retrieval models based on path-constrained random walks. many recommendation and retrieval tasks can be represented as proximity queries on a labeled directed graph, with typed nodes representing documents, terms, and metadata, and labeled edges representing the relationships between them. recent work has shown that the accuracy of the widely-used random-walk-based proximity measures can be improved by supervised learning - in particular, one especially effective learning technique is based on path-constrained random walks (pcrw), in which similarity is defined by a learned combination of constrained random walkers, each constrained to follow only a particular sequence of edge labels away from the query nodes. the pcrw based method significantly outperformed unsupervised random walk based queries, and models with learned edge weights. unfortunately, pcrw query systems are expensive to evaluate. in this study we evaluate the use of approximations to the computation of the pcrw distributions, including fingerprinting, particle filtering, and truncation strategies. in experiments on several recommendation and retrieval problems using two large scientific publications corpora we show speedups of factors of 2 to 100 with little loss in accuracy.
automatic malware categorization using cluster ensemble. in this paper, resting on the analysis of instruction frequency and function-based instruction sequences, we develop an automatic malware categorization system (amcs) for automatically grouping malware samples into families that share some common characteristics using a cluster ensemble by aggregating the clustering solutions generated by different base clustering algorithms. we propose a principled cluster ensemble framework for combining individual clustering solutions based on the consensus partition. the domain knowledge in the form of sample-level constraints can be naturally incorporated in the ensemble framework. in addition, to account for the characteristics of feature representations, we propose a hybrid hierarchical clustering algorithm which combines the merits of hierarchical clustering and k-medoids algorithms and a weighted subspace k-medoids algorithm to generate base clusterings. the categorization results of our amcs system can be used to generate signatures for malware families that are useful for malware detection. the case studies on large and real daily malware collection from kingsoft anti-virus lab demonstrate the effectiveness and efficiency of our amcs system.
malstone: towards a benchmark for analytics on large data clouds. developing data mining algorithms that are suitable for cloud computing platforms is currently an active area of research, as is developing cloud computing platforms appropriate for data mining. currently, the most common benchmark for cloud computing is the terasort (and related) benchmarks. although the terasort benchmark is quite useful, it was not designed for data mining per se. in this paper, we introduce a benchmark called malstone that is specifically designed to measure the performance of cloud computing middleware that supports the type of data intensive computing common when building data mining models. we also introduce malgen, which is a utility for generating data on clouds that can be used with malstone.
fast euclidean minimum spanning tree: algorithm, analysis, and applications. the euclidean minimum spanning tree problem has applications in a wide range of fields, and many efficient algorithms have been developed to solve it. we present a new, fast, general emst algorithm, motivated by the clustering and analysis of astronomical data. large-scale astronomical surveys, including the sloan digital sky survey, and large simulations of the early universe, such as the millennium simulation, can contain millions of points and fill terabytes of storage. traditional emst methods scale quadratically, and more advanced methods lack rigorous runtime guarantees. we present a new dual-tree algorithm for efficiently computing the emst, use adaptive algorithm analysis to prove the tightest (and possibly optimal) runtime bound for the emst problem to-date, and demonstrate the scalability of our method on astronomical data sets.
active learning for biomedical citation screening. active learning (al) is an increasingly popular strategy for mitigating the amount of labeled data required to train classifiers, thereby reducing annotator effort. we describe a real-world, deployed application of al to the problem of biomedical citation screening for systematic reviews at the tufts medical center's evidence-based practice center. we propose a novel active learning strategy that exploits a priori domain knowledge provided by the expert (specifically, labeled features)and extend this model via a linear programming algorithm for situations where the expert can provide ranked labeled features. our methods outperform existing al strategies on three real-world systematic review datasets. we argue that evaluation must be specific to the scenario under consideration. to this end, we propose a new evaluation framework for finite-pool scenarios, wherein the primary aim is to label a fixed set of examples rather than to simply induce a good predictive model. we use a method from medical decision theory for eliciting the relative costs of false positives and false negatives from the domain expert, constructing a utility measure of classification performance that integrates the expert preferences. our findings suggest that the expert can, and should, provide more information than instance labels alone. in addition to achieving strong empirical results on the citation screening problem, this work outlines many important steps for moving away from simulated active learning and toward deploying al for real-world applications.
unifying dependent clustering and disparate clustering for non-homogeneous data. modern data mining settings involve a combination of attribute-valued descriptors over entities as well as specified relationships between these entities. we present an approach to cluster such non-homogeneous datasets by using the relationships to impose either dependent clustering or disparate clustering constraints. unlike prior work that views constraints as boolean criteria, we present a formulation that allows constraints to be satisfied or violated in a smooth manner. this enables us to achieve dependent clustering and disparate clustering using the same optimization framework by merely maximizing versus minimizing the objective function. we present results on both synthetic data as well as several real-world datasets.
mining uncertain data with probabilistic guarantees. data uncertainty is inherent in applications such as sensor monitoring systems, location-based services, and biological databases. to manage this vast amount of imprecise information, probabilistic databases have been recently developed. in this paper, we study the discovery of frequent patterns and association rules from probabilistic data under the possible world semantics. this is technically challenging, since a probabilistic database can have an exponential number of possible worlds. we propose two effcient algorithms, which discover frequent patterns in bottom-up and top-down manners. both algorithms can be easily extended to discover maximal frequent patterns. we also explain how to use these patterns to generate association rules. extensive experiments, using real and synthetic datasets, were conducted to validate the performance of our methods.
discovering frequent patterns in sensitive data. discovering frequent patterns from data is a popular exploratory technique in datamining. however, if the data are sensitive (e.g., patient health records, user behavior records) releasing information about significant patterns or trends carries significant risk to privacy. this paper shows how one can accurately discover and release the most significant patterns along with their frequencies in a data set containing sensitive information, while providing rigorous guarantees of privacy for the individuals whose information is stored there. we present two efficient algorithms for discovering the k most frequent patterns in a data set of sensitive records. our algorithms satisfy differential privacy, a recently introduced definition that provides meaningful privacy guarantees in the presence of arbitrary external information. differentially private algorithms require a degree of uncertainty in their output to preserve privacy. our algorithms handle this by returning 'noisy' lists of patterns that are close to the actual list of k most frequent patterns in the data. we define a new notion of utility that quantifies the output accuracy of private top-k pattern mining algorithms. in typical data sets, our utility criterion implies low false positive and false negative rates in the reported lists. we prove that our methods meet the new utility criterion; we also demonstrate the performance of our algorithms through extensive experiments on the transaction data sets from the fimi repository. while the paper focuses on frequent pattern mining, the techniques developed here are relevant whenever the data mining output is a list of elements ordered according to an appropriately 'robust' measure of interest.
compressed fisher linear discriminant analysis: classification of randomly projected data. we consider random projections in conjunction with classification, specifically the analysis of fisher's linear discriminant (fld) classifier in randomly projected data spaces. unlike previous analyses of other classifiers in this setting, we avoid the unnatural effects that arise when one insists that all pairwise distances are approximately preserved under projection. we impose no sparsity or underlying low-dimensional structure constraints on the data; we instead take advantage of the class structure inherent in the problem. we obtain a reasonably tight upper bound on the estimated misclassification error on average over the random choice of the projection, which, in contrast to early distance preserving approaches, tightens in a natural way as the number of training examples increases. it follows that, for good generalisation of fld, the required projection dimension grows logarithmically with the number of classes. we also show that the error contribution of a covariance misspecification is always no worse in the low-dimensional space than in the initial high-dimensional space. we contrast our findings to previous related work, and discuss our insights.
nonnegative shared subspace learning and its application to social media retrieval. although tagging has become increasingly popular in online image and video sharing systems, tags are known to be noisy, ambiguous, incomplete and subjective. these factors can seriously affect the precision of a social tag-based web retrieval system. therefore improving the precision performance of these social tag-based web retrieval systems has become an increasingly important research topic. to this end, we propose a shared subspace learning framework to leverage a secondary source to improve retrieval performance from a primary dataset. this is achieved by learning a shared subspace between the two sources under a joint nonnegative matrix factorization in which the level of subspace sharing can be explicitly controlled. we derive an efficient algorithm for learning the factorization, analyze its complexity, and provide proof of convergence. we validate the framework on image and video retrieval tasks in which tags from the labelme dataset are used to improve image retrieval performance from a flickr dataset and video retrieval performance from a youtube dataset. this has implications for how to exploit and transfer knowledge from readily available auxiliary tagging resources to improve another social web retrieval system. our shared subspace learning framework is applicable to a range of problems where one needs to exploit the strengths existing among multiple and heterogeneous datasets.
negative correlations in collaboration: concepts and algorithms. this paper studies efficient mining of negative correlations that pace in collaboration. a collaborating negative correlation is a negative correlation between two sets of variables rather than traditionally between a pair of variables. it signifies a synchronized value rise or fall of all variables within one set whenever all variables in the other set go jointly at the opposite trend. the time complexity is exponential in mining. the high efficiency of our algorithm is attributed to two factors: (i) the transformation of the original data into a bipartite graph database, and (ii) the mining of transpose closures from a wide transactional database. applying to a yeast gene expression data, we evaluate, by using pearson's correlation coefficient and p-value, the biological relevance of collaborating negative correlations as an example among many real-life domains.
multiple kernel learning for heterogeneous anomaly detection: algorithm and aviation safety case study. the world-wide aviation system is one of the most complex dynamical systems ever developed and is generating data at an extremely rapid rate. most modern commercial aircraft record several hundred flight parameters including information from the guidance, navigation, and control systems, the avionics and propulsion systems, and the pilot inputs into the aircraft. these parameters may be continuous measurements or binary or categorical measurements recorded in one second intervals for the duration of the flight. currently, most approaches to aviation safety are reactive, meaning that they are designed to react to an aviation safety incident or accident. in this paper, we discuss a novel approach based on the theory of multiple kernel learning to detect potential safety anomalies in very large data bases of discrete and continuous data from world-wide operations of commercial fleets. we pose a general anomaly detection problem which includes both discrete and continuous data streams, where we assume that the discrete streams have a causal influence on the continuous streams. we also assume that atypical sequences of events in the discrete streams can lead to off-nominal system performance. we discuss the application domain, novel algorithms, and also discuss results on real-world data sets. our algorithm uncovers operationally significant events in high dimensional data streams in the aviation industry which are not detectable using state of the art methods.
semantic relation extraction with kernels over typed dependency trees. an important step for understanding the semantic content of text is the extraction of semantic relations between entities in natural language documents. automatic extraction techniques have to be able to identify different versions of the same relation which usually may be expressed in a great variety of ways. therefore these techniques benefit from taking into account many syntactic and semantic features, especially parse trees generated by automatic sentence parsers. typed dependency parse trees are edge and node labeled parse trees whose labels and topology contains valuable semantic clues. this information can be exploited for relation extraction by the use of kernels over structured data for classification. in this paper we present new tree kernels for relation extraction over typed dependency parse trees. on a public benchmark data set we are able to demonstrate a significant improvement in terms of relation extraction quality of our new kernels over other state-of-the-art kernels.
fast nearest-neighbor search in disk-resident graphs. link prediction, personalized graph search, fraud detection, and many such graph mining problems revolve around the computation of the most "similar" k nodes to a given query node. one widely used class of similarity measures is based on random walks on graphs, e.g., personalized pagerank, hitting and commute times, and simrank. there are two fundamental problems associated with these measures. first, existing online algorithms typically examine the local neighborhood of the query node which can become significantly slower whenever high-degree nodes are encountered (a common phenomenon in real-world graphs). we prove that turning high degree nodes into sinks results in only a small approximation error, while greatly improving running times. the second problem is that of computing similarities at query time when the graph is too large to be memory-resident. the obvious solution is to split the graph into clusters of nodes and store each cluster on a disk page; ideally random walks will rarely cross cluster boundaries and cause page-faults. our contributions here are twofold: (a) we present an efficient deterministic algorithm to find the k closest neighbors (in terms of personalized pagerank) of any query node in such a clustered graph, and (b) we develop a clustering algorithm (rwdisk) that uses only sequential sweeps over data files. empirical results on several large publicly available graphs like dblp, citeseer and live-journal (~ 90 m edges) demonstrate that turning high degree nodes into sinks not only improves running time of rwdisk by a factor of 3 but also boosts link prediction accuracy by a factor of 4 on average. we also show that rwdisk returns more desirable (high conductance and small size) clusters than the popular clustering algorithm metis, while requiring much less memory. finally our deterministic algorithm for computing nearest neighbors incurs far fewer page-faults (factor of 5) than actually simulating random walks.
biosnowball: automated population of wikis. internet users regularly have the need to find biographies and facts of people of interest. wikipedia has become the first stop for celebrity biographies and facts. however, wikipedia can only provide information for celebrities because of its neutral point of view (npov) editorial policy. in this paper we propose an integrated bootstrapping framework named biosnowball to automatically summarize the web to generate wikipedia-style pages for any person with a modest web presence. in biosnowball, biography ranking and fact extraction are performed together in a single integrated training and inference process using markov logic networks (mlns) as its underlying statistical model. the bootstrapping framework starts with only a small number of seeds and iteratively finds new facts and biographies. as biography paragraphs on the web are composed of the most important facts, our joint summarization model can improve the accuracy of both fact extraction and biography ranking compared to decoupled methods in the literature. empirical results on both a small labeled data set and a real web-scale data set show the effectiveness of biosnowball. we also empirically show that biosnowball outperforms the decoupled methods.
the topic-perspective model for social tagging systems. in this paper, we propose a new probabilistic generative model, called topic-perspective model, for simulating the generation process of social annotations. different from other generative models, in our model, the tag generation process is separated from the content term generation process. while content terms are only generated from resource topics, social tags are generated by resource topics and user perspectives together. the proposed probabilistic model can produce more useful information than any other models proposed before. the parameters learned from this model include: (1) the topical distribution of each document, (2) the perspective distribution of each user, (3) the word distribution of each topic, (4) the tag distribution of each topic, (5) the tag distribution of each user perspective, (6) and the probabilistic of each tag being generated from resource topics or user perspectives. experimental results show that the proposed model has better generalization performance or tag prediction ability than other two models proposed in previous research.