waashk/dblp huggingface dataset:
information retrieval based on collaborative filtering with latent interest semantic map. in this paper, we propose an information retrieval model called latent interest semantic map (lism), which features retrieval composed of both collaborative filtering(cf) and probabilistic latent semantic analysis (plsa). the motivation behind this study is that the relation between users and documents can be explained by the two different latent classes, where users belong probabilistically in one or more classes with the same interest groups, while documents also belong probabilistically in one or more class with the same topic groups. the novel aspect of lism is that it simultaneously provides a user model and latent semantic analysis in one map. this benefit of lism is to enable collaborative filtering in terms of user interest and document topic and thus solve the cold start problem.
mining quantitative correlated patterns using an information-theoretic approach. existing research on mining quantitative databases mainly focuses on mining associations. however, mining associations is too expensive to be practical in many cases. in this paper, we study mining correlations from quantitative databases and show that it is a more effective approach than mining associations. we propose a new notion of quantitative correlated patterns (qcps), which is founded on two formal concepts, mutual information and all-confidence. we first devise a normalization on mutual information and apply it to qcp mining to capture the dependency between the attributes. we further adopt all-confidence as a quality measure to control, at a finer granularity, the dependency between the attributes with specific quantitative intervals. we also propose a supervised method to combine the consecutive intervals of the quantitative attributes based on mutual information, such that the interval combining is guided by the dependency between the attributes. we develop an algorithm, qcomine, to efficiently mine qcps by utilizing normalized mutual information and all-confidence to perform a two-level pruning. our experiments verify the efficiency of qcomine and the quality of the qcps.
maximizing the spread of influence through a social network. models for the processes by which ideas and influence propagate through a social network have been studied in a number of domains, including the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of "word of mouth" in the promotion of new products. recently, motivated by the design of viral marketing strategies, domingos and richardson posed a fundamental algorithmic problem for such social network processes: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?we consider this problem in several of the most widely studied models in social network analysis. the optimization problem of selecting the most influential nodes is np-hard here, and we provide the first provable approximation guarantees for efficient algorithms. using an analysis framework based on submodular functions, we show that a natural greedy strategy obtains a solution that is provably within 63% of optimal for several classes of models; our framework suggests a general approach for reasoning about the performance guarantees of algorithms for these types of influence problems in social networks.we also provide computational experiments on large collaboration networks, showing that in addition to their provable guarantees, our approximation algorithms significantly out-perform node-selection heuristics based on the well-studied notions of degree centrality and distance centrality from the field of social networks.
ensemble-index: a new approach to indexing large databases. the problem of similarity search (query-by-content) has attracted much research interest. it is a difficult problem because of the inherently high dimensionality of the data. the most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. many dimensionality reduction techniques have been proposed, including singular value decomposition (svd), the discrete fourier transform (dft), the discrete wavelet transform (dwt) and piecewise polynomial approximation. in this work, we introduce a novel framework for using ensembles of two or more representations for more efficient indexing. the basic idea is that instead of committing to a single representation for an entire dataset, different representations are chosen for indexing different parts of the database. the representations are chosen based upon a local view of the database. for example, sections of the data that can achieve a high fidelity representation with wavelets are indexed as wavelets, but highly spectral sections of the data are indexed using the fourier transform. at query time, it is necessary to search several small heterogeneous indices, rather than one large homogeneous index. as we will theoretically and empirically demonstrate this results in much faster query response times.
on the need for time series data mining benchmarks: a survey and empirical demonstration. in the last decade there has been an explosion of interest in mining time series data. literally hundreds of papers have introduced new algorithms to index, classify, cluster and segment time series. in this work we make the following claim. much of this work has very little utility because the contribution made (speed in the case of indexing, accuracy in the case of classification and clustering, model accuracy in the case of segmentation) offer an amount of &ldquo;improvement&rdquo; that would have been completely dwarfed by the variance that would have been observed by testing on many real world datasets, or the variance that would have been observed by changing minor (unstated) implementation details.to illustrate our point, we have undertaken the most exhaustive set of time series experiments ever attempted, re-implementing the contribution of more than two dozen papers, and testing them on 50 real world, highly diverse datasets. our empirical results strongly support our assertion, and suggest the need for a set of time series benchmarks and more careful empirical evaluation in the data mining community.
finding surprising patterns in a time series database in linear time and space. the problem of finding a specified pattern in a time series database (i.e. query by content) has received much attention and is now a relatively mature field. in contrast, the important problem of enumerating all surprising or interesting patterns has received far less attention. this problem requires a meaningful definition of "surprise", and an efficient search technique. all previous attempts at finding surprising patterns in time series use a very limited notion of surprise, and/or do not scale to massive datasets. to overcome these limitations we introduce a novel technique that defines a pattern surprising if the frequency of its occurrence differs substantially from that expected by chance, given some previously seen data.
towards parameter-free data mining. most data mining algorithms require the setting of many input parameters. two main dangers of working with parameter-laden algorithms are the following. first, incorrect settings may cause an algorithm to fail in finding the true patterns. second, a perhaps more insidious problem is that the algorithm may report spurious patterns that do not really exist, or greatly overestimate the significance of the reported patterns. this is especially likely when the user fails to understand the role of parameters in the data mining process.data mining algorithms should have as few parameters as possible, ideally none. a parameter-free algorithm would limit our ability to impose our prejudices, expectations, and presumptions on the problem at hand, and would let the data itself speak to us. in this work, we show that recent results in bioinformatics and computational theory hold great promise for a parameter-free data-mining paradigm. the results are motivated by observations in kolmogorov complexity theory. however, as a practical matter, they can be implemented using any off-the-shelf compression algorithm with the addition of just a dozen or so lines of code. we will show that this approach is competitive or superior to the state-of-the-art approaches in anomaly/interestingness detection, classification, and clustering with empirical tests on time series/dna/text/video datasets.
bursty and hierarchical structure in streams. a fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. e-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. the published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. underlying much of the text mining work in this area is the following intuitive premise&mdash;that the appearance of a topic in a document stream is signaled by a &ldquo;burst of activity,&rdquo; with certain features rising sharply in frequency as the topic emerges.the goal of the present work is to develop a formal approach for modeling such &ldquo;bursts,&rdquo; in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. the approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions&semi; it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. the resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them.
maximally informative k-itemsets and their efficient discovery. in this paper we present a new approach to mining binary data. we treat each binary feature (item) as a means of distinguishing two sets of examples. our interest is in selecting from the total set of items an itemset of specified size, such that the database is partitioned with as uniform a distribution over the parts as possible. to achieve this goal, we propose the use of joint entropy as a quality measure for itemsets, and refer to optimal itemsets of cardinality k as maximally informative k-itemsets. we claim that this approach maximises distinctive power, as well as minimises redundancy within the feature set. a number of algorithms is presented for computing optimal itemsets efficiently.
robust space transformations for distance-based operations. for many kdd operations, such as nearest neighbor search, distance-based clustering, and outlier detection, there is an underlying &kgr;-d data space in which each tuple/object is represented as a point in the space. in the presence of differing scales, variability, correlation, and/or outliers, we may get unintuitive results if an inappropriate space is used.the fundamental question that this paper addresses is: "what then is an appropriate space?" we propose using a robust space transformation called the donoho-stahel estimator. in the first half of the paper, we show the key properties of the estimator. of particular importance to kdd applications involving databases is the stability property, which says that in spite of frequent updates, the estimator does not: (a) change much, (b) lose its usefulness, or (c) require re-computation. in the second half, we focus on the computation of the estimator for high-dimensional databases. we develop randomized algorithms and evaluate how well they perform empirically. the novel algorithm we develop called the hybrid-random algorithm is, in most cases, at least an order of magnitude faster than the fixed-angle and subsampling algorithms.
mining e-commerce data: the good, the bad, and the ugly. organizations conducting electronic commerce (e-commerce) can greatly benefit from the insight that data mining of transactional and clickstream data provides. such insight helps not only to improve the electronic channel (e.g., a web site), but it is also a learning vehicle for the bigger organization conducting business at brick-and-mortar stores. the e-commerce site serves as an early alert system for emerging patterns and a laboratory for experimentation. for successful data mining, several ingredients are needed and e-commerce provides all the right ones (the good). web server logs, which are commonly used as the source of data for mining e-commerce data, were designed to debug web servers, and the data they provide is insufficient, requiring the use of heuristics to reconstruct events. moreover, many events are never logged in web server logs, limiting the source of data for mining (the bad). many of the problems of dealing with web server log data can be resolved by properly architecting the e-commerce sites to generate data needed for mining. even with a good architecture, however, there are challenging problems that remain hard to solve (the ugly). lessons and metrics based on mining real e-commerce data are presented.
local sparsity control for naive bayes with extreme misclassification costs. in applications of data mining characterized by highly skewed misclassification costs certain types of errors become virtually unacceptable. this limits the utility of a classifier to a range in which such constraints can be met. naive bayes, which has proven to be very useful in text mining applications due to high scalability, can be particularly affected. although its 0/1 loss tends to be small, its misclassifications are often made with apparently high confidence. aside from efforts to better calibrate naive bayes scores, it has been shown that its accuracy depends on document sparsity and feature selection can lead to marked improvement in classification performance. traditionally, sparsity is controlled globally, and the result for any particular document may vary. in this work we examine the merits of local sparsity control for naive bayes in the context of highly asymmetric misclassification costs. in experiments with three benchmark document collections we demonstrate clear advantages of document-level feature selection. in the extreme cost setting, multinomial naive bayes with local sparsity control is able to outperform even some of the recently proposed effective improvements to the naive bayes classifier. there are also indications that local feature selection may be preferable in different cost settings.
improved robustness of signature-based near-replica detection via lexicon randomization. detection of near duplicate documents is an important problem in many data mining and information filtering applications. when faced with massive quantities of data, traditional duplicate detection techniques relying on direct inter-document similarity computation (e.g., using the cosine measure) are often not feasible given the time and memory performance constraints. on the other hand, fingerprint-based methods, such as i-match, are very attractive computationally but may be brittle with respect to small changes to document content. we focus on approaches to near-replica detection that are based upon large-collection statistics and present a general technique of increasing their robustness via multiple lexicon randomization. in experiments with large web-page and spam-email datasets the proposed method is shown to consistently outperform traditional i-match, with the relative improvement in duplicate-document recall reaching as high as 40-60%. the large gains in detection accuracy are offset by only small increases in computational requirements.
efficient handling of high-dimensional feature spaces by randomized classifier ensembles. handling massive datasets is a difficult problem not only due to prohibitively large numbers of entries but in some cases also due to the very high dimensionality of the data. often, severe feature selection is performed to limit the number of attributes to a manageable size, which unfortunately can lead to a loss of useful information. feature space reduction may well be necessary for many stand-alone classifiers, but recent advances in the area of ensemble classifier techniques indicate that overall accurate classifier aggregates can be learned even if each individual classifier operates on incomplete "feature view" training data, i.e., such where certain input attributes are excluded. in fact, by using only small random subsets of features to build individual component classifiers, surprisingly accurate and robust models can be created. in this work we demonstrate how these types of architectures effectively reduce the feature space for submodels and groups of sub-models, which lends itself to efficient sequential and/or parallel implementations. experiments with a randomized version of adaboost are used to support our arguments, using the text classification task as an example.
learning to detect malicious executables in the wild. in this paper, we describe the development of a fielded application for detecting malicious executables in the wild. we gathered 1971 benign and 1651 malicious executables and encoded each as a training example using n-grams of byte codes as features. such processing resulted in more than 255 million distinct n-grams. after selecting the most relevant n-grams for prediction, we evaluated a variety of inductive methods, including naive bayes, decision trees, support vector machines, and boosting. ultimately, boosted decision trees outperformed other methods with an area under the roc curve of 0.996. results also suggest that our methodology will scale to larger collections of executables. to the best of our knowledge, ours is the only fielded application for this task developed using techniques from machine learning and data mining.
reducing the human overhead in text categorization. many applications in text processing require significant human effort for either labeling large document collections (when learning statistical models) or extrapolating rules from them (when using knowledge engineering). in this work, we describe away to reduce this effort, while retaining the methods' accuracy, by constructing a hybrid classifier that utilizes human reasoning over automatically discovered text patterns to complement machine learning. using a standard sentiment-classification dataset and real customer feedback data, we demonstrate that the resulting technique results in significant reduction of the human effort required to obtain a given classification accuracy. moreover, the hybrid text classifier also results in a significant boost in accuracy over machine-learning based classifiers when a comparable amount of labeled data is used.
determining an author's native language by mining a text for errors. in this paper, we show that stylistic text features can be exploited to determine an anonymous author's native language with high accuracy. specifically, we first use automatic tools to ascertain frequencies of various stylistic idiosyncrasies in a text. these frequencies then serve as features for support vector machines that learn to classify texts according to author native language.
a two-way visualization method for clustered data. we describe a novel approach to the visualization of hierarchical clustering that superimposes the classical dendrogram over a fully synchronized low-dimensional embedding, thereby gaining the benefits of both approaches. in a single image one can view all the clusters, examine the relations between them and study many of their properties. the method is based on an algorithm for low-dimensional embedding of clustered data, with the property that separation between all clusters is guaranteed, regardless of their nature. in particular, the algorithm was designed to produce embeddings that strictly adhere to a given hierarchical clustering of the data, so that every two disjoint clusters in the hierarchy are drawn separately.
measuring and extracting proximity in networks. measuring distance or some other form of proximity between objects is a standard data mining tool. connection subgraphs were recently proposed as a way to demonstrate proximity between nodes in networks. we propose a new way of measuring and extracting proximity in networks called "cycle free effective conductance"(cfec). our proximity measure can handle more than two endpoints, directed edges, is statistically well-behaved, and produces an effectiveness score for the computed subgraphs. we provide an efficien talgorithm. also, we report experimental results and show examples for three large network data sets: a telecommunications calling graph, the imdb actors graph, and an academic co-authorship network.
proximus: a framework for analyzing very high dimensional discrete-attributed datasets. this paper presents an efficient framework for error-bounded compression of high-dimensional discrete attributed datasets. such datasets, which frequently arise in a wide variety of applications, pose some of the most significant challenges in data analysis. subsampling and compression are two key technologies for analyzing these datasets. proximus provides a technique for reducing large datasets into a much smaller set of representative patterns, on which traditional (expensive) analysis algorithms can be applied with minimal loss of accuracy. we show desirable properties of proximus in terms of runtime, scalability to large datasets, and performance in terms of capability to represent data in a compact form. we also demonstrate applications of proximus in association rule mining. in doing so, we establish proximus as a tool for preprocessing data before applying computationally expensive algorithms or as a tool for directly extracting correlated patterns. our experimental results show that use of the compressed data for association rule mining provides excellent precision and recall values (near 100%) across a range of support thresholds while reducing the time required for association rule mining drastically.
molecular feature mining in hiv data. we present the application of feature mining techniques to the developmental therapeutics program's aids antiviral screen database. the database consists of 43576 compounds, which were measured for their capability to protect human cells from hiv-1 infection. according to these measurements, the compounds were classified as either active, moderately active or inactive. the distribution of classes is extremely skewed: only 1.3 % of the molecules is known to be active, and 2.7 % is known to be moderately active.given this database, we were interested in molecular substructures (i.e., features) that are frequent in the active molecules, and infrequent in the inactives. in data mining terms, we focused on features with a minimum support in active compounds and a maximum support in inactive compounds. we analyzed the database using the levelwise version space algorithm that forms the basis of the inductive query and database system molfea (molecular feature miner). within this framework, it is possible to declaratively specify the features of interest, such as the frequency of features on (possibly different) datasets as well as on the generality and syntax of them. assuming that the detected substructures are causally related to biochemical mechanisms, it should be possible to facilitate the development of new pharmaceuticals with improved activities.