waashk/dblp huggingface dataset:
scalable tensor decompositions for multi-aspect data mining. modern applications such as internet traffic, telecommunication records, and large-scale social networks generate massive amounts of data with multiple aspects and high dimensionalities. tensors (i.e., multi-way arrays) provide a natural representation for such data. consequently, tensor decompositions such as tucker become important tools for summarization and analysis.one major challenge is how to deal with high-dimensional, sparse data. in other words, how do we compute decompositions of tensors where most of the entries of the tensor are zero. specialized techniques are needed for computing the tucker decompositions for sparse tensors because standard algorithms do not account for the sparsity of the data. as a result, a surprising phenomenon is observed by practitioners: despite the fact that there is enough memory to store both the input tensors and the factorized output tensors, memory overflows occur during the tensor factorization process. to address this intermediate blowup problem, we propose memory-efficient tucker (met). based on the available memory, met adaptively selects the right execution strategy during the decomposition. we provide quantitative and qualitative evaluation of met on real tensors. it achieves over 1000x space reduction without sacrificing speed; it also allows us to work with much larger tensors that were too big to handle before. finally, we demonstrate a data mining case-study using met.
non-negative matrix factorization on manifold. recently non-negative matrix factorization (nmf) has received a lot of attentions in information retrieval, computer vision and pattern recognition. nmf aims to find two non-negative matrices whose product can well approximate the original matrix. the sizes of these two matrices are usually smaller than the original matrix. this results in a compressed version of the original data matrix. the solution of nmf yields a natural parts-based representation for the data. when nmf is applied for data representation, a major disadvantage is that it fails to consider the geometric structure in the data. in this paper, we develop a graph based approach for parts-based data representation in order to overcome this limitation. we construct an affinity graph to encode the geometrical information and seek a matrix factorization which respects the graph structure. we demonstrate the success of this novel algorithm by applying it on real world problems.
xcrawl: a high-recall crawling method for web mining. web mining systems exploit the redundancy of data published on the web to automatically extract information from existing web documents. the first step in the information extraction process is thus to locate within a limited period of time as many web pages as possible that contain relevant information, a task which is commonly accomplished by applying focused crawling techniques. the performance of such a crawler can be measured by its "recall", i.e. the percentage of documents found and identified as relevant compared to the number of existing documents. a higher recall value implies that more redundant data is available, which in turn leads to better results in the subsequent fact extraction phase. in this paper, we propose xcrawl, a new focused crawling method which outperforms state-of-the-art approaches with respect to recall values achievable within a given period of time. this method is based on a new combination of ideas and techniques used to identify and exploit navigational structures of websites, such as hierarchies, lists or maps. in addition, automatic query generation is applied to rapidly collect web sources containing target documents. the proposed crawling technique was inspired by the requirements of a web mining system developed to extract product and service descriptions and was evaluated in different application scenarios. comparisons with existing focused crawling techniques reveal that the new crawling method leads to a significant increase in recall whilst maintaining precision.
tefe: a time-efficient approach to feature extraction. with the rapid evolution of internet applications, people all over the world are sharing pictures, videos and audios online, and thus, content-based analysis is often demanded. test efficiency is crucial to the success of online information processing. one obstacle to high-speed testing is the time cost of feature extraction for test objects, particularly for objects with complex representation such as images, videos and audios. in this paper, we study the problem of reducing test time cost by extracting cheap but sufficient features. we propose the tefe (time-efficient feature extraction) approach, which balances between the test accuracy and test time cost by extracting a proper subset of features for each test object. in the implementation, tefe trains a sequence of support vector machines and classifies each test object cascadingly. empirical study shows that tefe is time efficient while holding a classification accuracy close to that of using all features. it also shows that the test time is linearly adjustable in tefe.
what sperner family concept class is easy to be enumerated? we study the problem of enumerating concepts in a sperner family concept class using subconcept queries, which is a general problem including maximal frequent itemset mining as its instance. though even the theoretically best known algorithm needs quasi-polynomial time to solve this problem in the worst case, there exist practically fast algorithms for this problem. this is because many instances of this problem in real world have low complexity in some measures. in this paper, we characterize the complexity of sperner family concept class by the vc dimension of its intersection closure and its characteristic dimension, and analyze the worst case time complexity on the enumeration problem of its concepts in terms of the vc dimension. we also showed that the vc dimension of real data used in data mining is actually small by calculating the vc dimension of some real datasets using a new algorithm closely related to the introduced two measures, which does not only solve the problem but also let us know the vc dimension of the intersection closure of the target concept class.
maximum margin clustering with pairwise constraints. maximum margin clustering (mmc), which extends the theory of support vector machine to unsupervised learning, has been attracting considerable attention recently. the existing approaches mainly focus on reducing the computational complexity of mmc. the accuracy of these methods, however, has not always been guaranteed. in this paper, we propose to incorporate additional side-information, which is in the form of pairwise constraints, into mmc to further improve its performance. a set of pairwise loss functions are introduced into the clustering objective function which effectively penalize the violation of the given constraints. we show that the resulting optimization problem can be easily solved via constrained concave-convex procedure (cccp). moreover, for constrained multi-class mmc, we present an efficient cutting-plane algorithm to solve the sub-problem in each iteration of cccp. the experiments demonstrate that the pairwise constrained mmc algorithms considerably outperform the unconstrained mmc algorithms and two other clustering algorithms that exploit the same type of side-information.
metropolis algorithms for representative subgraph sampling. while data mining in chemoinformatics studied graph data with dozens of nodes, systems biology and the internet are now generating graph data with thousands and millions of nodes. hence data mining faces the algorithmic challenge of coping with this significant increase in graph size: classic algorithms for data analysis are often too expensive and too slow on large graphs. while one strategy to overcome this problem is to design novel efficient algorithms, the other is to 'reduce' the size of the large graph by sampling. this is the scope of this paper: we will present novel metropolis algorithms for sampling a 'representative' small subgraph from the original large graph, with 'representative' describing the requirement that the sample shall preserve crucial graph properties of the original graph. in our experiments, we improve over the pioneering work of leskovec and faloutsos (kdd 2006), by producing representative subgraph samples that are both smaller and of higher quality than those produced by other methods from the literature.
one-class collaborative filtering. many applications of collaborative filtering (cf), such as news item recommendation and bookmark recommendation, are most naturally thought of as one-class collaborative filtering (occf) problems. in these problems, the training data usually consist simply of binary data reflecting a user's action or inaction, such as page visitation in the case of news item recommendation or webpage bookmarking in the bookmarking scenario. usually this kind of data are extremely sparse (a small fraction are positive examples), therefore ambiguity arises in the interpretation of the non-positive examples. negative examples and unlabeled positive examples are mixed together and we are typically unable to distinguish them. for example, we cannot really attribute a user not bookmarking a page to a lack of interest or lack of awareness of the page. previous research addressing this one-class problem only considered it as a classification task. in this paper, we consider the one-class problem under the cf setting. we propose two frameworks to tackle occf. one is based on weighted low rank approximation; the other is based on negative example sampling. the experimental results show that our approaches significantly outperform the baselines.
document-word co-regularization for semi-supervised sentiment analysis. the goal of sentiment prediction is to automatically identify whether a given piece of text expresses positive or negative opinion towards a topic of interest. one can pose sentiment prediction as a standard text categorization problem, but gathering labeled data turns out to be a bottleneck. fortunately, background knowledge is often available in the form of prior information about the sentiment polarity of words in a lexicon. moreover, in many applications abundant unlabeled data is also available. in this paper, we propose a novel semi-supervised sentiment prediction algorithm that utilizes lexical prior knowledge in conjunction with unlabeled examples. our method is based on joint sentiment analysis of documents and words based on a bipartite graph representation of the data. we present an empirical study on a diverse collection of sentiment prediction problems which confirms that our semi-supervised lexical models significantly outperform purely supervised and competing semi-supervised techniques.
discovering significant patterns in multi-stream sequences. discovering significant patterns in synchronized multi-stream sequences also known as multi-attribute event sequences (multi-sequences), is an important problem in many domains, including monitoring systems and information retrieval. in this paper we propose a new approach for assessing significance of multi-stream patterns in multi-attribute event sequences. in experiments on physiological multi-stream data we show applicability of our method.
clustering documents with active learning using wikipedia. wikipedia has been applied as a background knowledge base to various text mining problems, but very few attempts have been made to utilize it for document clustering. in this paper we propose to exploit the semantic knowledge in wikipedia for clustering, enabling the automatic grouping of documents with similar themes. although clustering is intrinsically unsupervised, recent research has shown that incorporating supervision improves clustering performance, even when limited supervision is provided. the approach presented in this paper applies supervision using active learning. we first utilize wikipedia to create a concept-based representation of a text document, with each concept associated to a wikipedia article. we then exploit the semantic relatedness between wikipedia concepts to find pair-wise instance-level constraints for supervised clustering, guiding clustering towards the direction indicated by the constraints. we test our approach on three standard text document datasets. empirical results show that our basic document representation strategy yields comparable performance to previous attempts; and adding constraints improves clustering performance further by up to 20%.
frequent subgraph retrieval in geometric graph databases. discovery of knowledge from geometric graph databases is of particular importance in chemistry and biology, because chemical compounds and proteins are represented as graphs with 3d geometric coordinates. in such applications, scientists are not interested in the statistics of the whole database. instead they need information about a novel drug candidate or protein at hand, represented as a query graph. we propose a polynomial-delay algorithm for geometric frequent subgraph retrieval. it enumerates all subgraphs of a single given query graph which are frequent geometric $\epsilon$-subgraphs under the entire class of rigid geometric transformations in a database. by using geometric$\epsilon$-subgraphs, we achieve tolerance against variations in geometry. we compare the proposed algorithm to gspan on chemical compound data, and we show that for a given minimum support the total number of frequent patterns is substantially limited by requiring geometric matching. although the computation time per pattern is larger than for non-geometric graph mining,the total time is within a reasonable level even for small minimum support.
scaling up classifiers to cloud computers. as the size of available datasets has grown from megabytes to gigabytes and now into terabytes, machine learning algorithms and computing infrastructures have continuously evolved in an effort to keep pace. but at large scales, mining for useful patterns still presents challenges in terms of data management as well as computation. these issues can be addressed by dividing both data and computation to build ensembles of classifiers in a distributed fashion, but trade-offs in cost, performance, and accuracy must be considered when designing or selecting an appropriate architecture. in this paper, we present an abstraction for scalable data mining that allows us to explore these trade-offs. data and computation are distributed to a computing cloud with minimal effort from the user, and multiple models for data management are available depending on the workload and system configuration. we demonstrate the performance and scalability characteristics of our ensembles using a wide variety of datasets and algorithms on a condor-based pool with chirp to handle the storage.
measuring proximity on graphs with side information. this paper studies how to incorporate side information (such as users' feedback) in measuring node proximity on large graphs. our method (prosin) is motivated by the well-studied random walk with restart (rwr). the basic idea behind prosin is to leverage side information to refine the graph structure so that the random walk is biased towards/away from some specific zones on the graph. our case studies demonstrate that prosin is well-suited in a variety of applications, including neighborhood search, center-piece subgraphs, and image caption. given the potential computational complexity of prosin, we also propose a fast algorithm (fast-prosin) that exploits the smoothness of the graph structures with/without side information. our experimental evaluation shows that fast-prosin achieves significant speedups (up to 49x) over straightforward implementations.
clustering geospatial objects via hidden markov random fields. this paper addresses the problem of clustering objects located and correlated geographically and containing multiple attributes. for the clustering problem, it is necessary to consider both the similarities of the attributes and the spatial dependencies of the objects. a new clustering framework using hidden markov random fields (hmrfs) and gaussian distributions and new potential models of hmrfs for irregularly located geospatial objects are proposed in this paper. experimental results for systematic data and two real-world data showed the availability of the proposed algorithms.
boosting relational sequence alignments. the task of aligning sequences arises in many applications. classical dynamic programming approaches require the explicit state enumeration in the reward model. this is often impractical: the number of states grows very quickly with the number of domain objects and relations among these objects. relational sequence alignment aims at exploiting symbolic structure to avoid the full enumeration. this comes at the expense of a more complex reward model selection problem: virtually infinitely many abstraction levels have to be explored. in this paper, we apply gradient-based boosting to leverage this problem. specifically, we show how to reduce the learning problem to a series of relational regressions problems. the main benefit of this is that interactions between states variables are introduced only as needed, so that the potentially infinite search space is not explicitly considered. as our experimental results show, this boosting approach can significantly improve upon established results in challenging applications.
anti-monotonic overlap-graph support measures. in graph mining, a frequency measure is anti-monotonic if the frequency of a pattern never exceeds the frequency of a subpattern. the efficiency and correctness of most graph pattern miners relies critically on this property. we study the case where the dataset is a single graph. vanetik, gudes and shimony already gave sufficient and necessary conditions for anti-monotonicity of measures depending only on the edge-overlaps between the intances of the pattern in a labeled graph. we extend these results to homomorphisms, isomorphisms and homeomorphisms on both labeled and unlabeled, directed and undirected graphs, for vertex and edge overlap. we show a set of reductions between the different morphisms that preserve overlap. we also prove that the popular maximum independent set measure assigns the minimal possible meaningful frequency, introduce a new measure based on the minimum clique partition that assigns the maximum possible meaningful frequency and introduce a new measure sandwiched between the former two based on the poly-time computable lovasz theta-function.
disco: distributed co-clustering with map-reduce: a case study towards petabyte-scale end-to-end mining. huge datasets are becoming prevalent; even as researchers, we now routinely have to work with datasets that are up to a few terabytes in size. interesting real-world applications produce huge volumes of messy data. the mining process involves several steps, starting from pre-processing the raw data to estimating the final models. as data become more abundant, scalable and easy-to-use tools for distributed processing are also emerging. among those, map-reduce has been widely embraced by both academia and industry. in database terms, map-reduce is a simple yet powerful execution engine, which can be complemented with other data storage and management components, as necessary. in this paper we describe our experiences and findings in applying map-reduce, from raw data to final models, on an important mining task. in particular, we focus on co-clustering, which has been studied in many applications such as text mining, collaborative filtering, bio-informatics, graph mining. we propose the distributed co-clustering (disco) framework, which introduces practical approaches for distributed data pre-processing, and co-clustering. we develop disco using hadoop, an open source map-reduce implementation. we show that disco can scale well and efficiently process and analyze extremely large datasets (up to several hundreds of gigabytes) on commodity hardware.
prediction of skin penetration using machine learning methods. improving predictions of the skin permeability coefficient is a difficult problem. it is also an important issue with the increasing use of skin patches as a means of drug delivery. in this work, we apply k-nearest-neighbour regression, single layer networks, mixture of experts and gaussian processes to predict the permeability coefficient. we obtain a considerable improvement over the quantitative structure-activity relationship (qsars) predictors. we show that using five features, which are molecular weight, solubility parameter, lipophilicity, the number of hydrogen bonding acceptor and donor groups, can produce better predictions than the one using only lipophilicity and the molecular weight. the gaussian process regression with five compound features gives the best performance in this work.
a novel language-model-based approach for image object mining and re-ranking. one leading framework for image object mining is the bag-of-words (bow) approach. the idea is to encode an image as a collection of visual words of the quantized local patches. objects in the image can then be retrieved through inferring the semantic topics associated with the set of visual words. however, the visual bow mining framework is apt to suffer from the so-called term-mismatch problem (a.k.a. vocabulary problem). this is caused by the poverty of query information, and consequently becomes an obstacle to deal with synonymy (i.e., different visual words for describing the same object). in this paper, we propose a novel language-model-based approach with pseudo-relevance feedback for addressing the vocabulary problem in visual bow mining. we employ the pseudo positive images produced in response to the original query as a set of “cues” to gradually refine the query language model. unlike traditional approaches that only ruggedly append feedback information into the original query, the proposed approach reconstructs the query language model with finer granularities so that the query concepts can be captured more accurately. the proposed approach is experimentally evaluated using two different types of image object databases. our algorithms are shown to bring significant improvement in the retrieval accuracy over a non-feedback baseline, and achieve better performance than conventional feedback approaches.
bayesian co-clustering. in recent years, co-clustering has emerged as a powerful data mining tool that can analyze dyadic data connecting two entities. however, almost all existing co-clustering techniques are partitional, and allow individual rows and columns of a data matrix to belong to only one cluster. several current applications, such as recommendation systems and market basket analysis, can substantially benefit from a mixed membership of rows and columns. in this paper, we present bayesian co-clustering (bcc) models, that allow a mixed membership in row and column clusters. bcc maintains separate dirichlet priors for rows and columns over the mixed membership and assumes each observation to be generated by an exponential family distribution corresponding to its row and column clusters. we propose a fast variational algorithm for inference and parameter estimation. the model is designed to naturally handle sparse matrices as the inference is done only based on the non-missing entries. in addition to finding a co-cluster structure in observations, the model outputs a low dimensional co-embedding, and accurately predicts missing values in the original matrix. we demonstrate the efficacy of the model through experiments on both simulated and real data.