waashk/dblp huggingface dataset:
on the use of linear programming for unsupervised text classification. we propose a new algorithm for dimensionality reduction and unsupervised text classification. we use mixture models as underlying process of generating corpus and utilize a novel, l1-norm based approach introduced by kleinberg and sandler [19]. we show that our algorithm performs extremely well on large datasets, with peak accuracy approaching that of supervised learning based on support vector machines (svms) with large training sets. the method is based on the same idea that underlies latent semantic indexing (lsi). we find a good low-dimensional subspace of a feature space and project all documents into it. however our projection minimizes different error, and unlike lsi we build a basis, that in many cases corresponds to the actual topics. we present results of testing of our algorithm on the abstracts of arxiv - an electronic repository of scientific papers, and the 20 newsgroup dataset - a small snapshot of 20 specific newsgroups.
recommender systems in commerce and community. recommender systems have been revolutionizing the way shoppers and information seekers find what they want. we will study some of the tremendous successes and spectacular failures of recommenders in e-commerce to understand the causes of the success or failure. we will leverage that understanding into a set of principles for successfully applying recommenders to business problems. finally, we will study the economic and social forces that are shaping the evolution of recommenders, and peer into the crystal ball to glimpse the directions the technology will be going in the future.
mass collaboration and data mining. mass collaboration is a new "p2p"-style approach to large-scale knowledge sharing, with applications in customer support, focused community development, and capturing knowledge distributed within large organizations. effectively supporting this paradigm raises many technical challenges, and offers intriguing opportunities for mining massive amounts of data captured continually from user interactions. data mining offers the promise of increased business intelligence, and also improved user experiences, leading to increased participation and greater quality in the knowledge that is captured, both of which are central objectives in mass collaboration. in this talk, i will introduce mass collaboration and discuss some important data mining related issues.
regularized discriminant analysis for high dimensional, low sample size data. linear and quadratic discriminant analysis have been used widely in many areas of data mining, machine learning, and bioinformatics. friedman proposed a compromise between linear and quadratic discriminant analysis, called regularized discriminant analysis (rda), which has been shown to be more flexible in dealing with various class distributions. rda applies the regularization techniques by employing two regularization parameters, which are chosen to jointly maximize the classification performance. the optimal pair of parameters is commonly estimated via cross-validation from a set of candidate pairs. it is computationally prohibitive for high dimensional data, especially when the candidate set is large, which limits the applications of rda to low dimensional data.in this paper, a novel algorithm for rda is presented for high dimensional data. it can estimate the optimal regularization parameters from a large set of parameter candidates efficiently. experiments on a variety of datasets confirm the claimed theoretical estimate of the efficiency, and also show that, for a properly chosen pair of regularization parameters, rda performs favorably in classification, in comparison with other existing classification methods.
turning cartwheels: an alternating algorithm for mining redescriptions. we present an unusual algorithm involving classification trees---cartwheels---where two trees are grown in opposite directions so that they are joined at their leaves. this approach finds application in a new data mining task we formulate, called redescription mining. a redescription is a shift-of-vocabulary, or a different way of communicating information about a given subset of data; the goal of redescription mining is to find subsets of data that afford multiple descriptions. we highlight the importance of this problem in domains such as bioinformatics, which exhibit an underlying richness and diversity of data descriptors (e.g., genes can be studied in a variety of ways). cartwheels exploits the duality between class partitions and path partitions in an induced classification tree to model and mine redescriptions. it helps integrate multiple forms of characterizing datasets, situates the knowledge gained from one dataset in the context of others, and harnesses high-level abstractions for uncovering cryptic and subtle features of data. algorithm design decisions, implementation details, and experimental results are presented.
a multinomial clustering model for fast simulation of computer architecture designs. computer architects utilize simulation tools to evaluate the merits of a new design feature. the time needed to adequately evaluate the tradeoffs associated with adding any new feature has become a critical issue. recent work has found that by identifying execution phases present in common workloads used in simulation studies, we can apply clustering algorithms to significantly reduce the amount of time needed to complete the simulation. our goal in this paper is to demonstrate the value of this approach when applied to the set of industry-standard benchmarks most commonly used in computer architecture studies. we also look to improve upon prior work by applying more appropriate clustering algorithms to identify phases, and to further reduce simulation time.we find that the phase clustering in computer architecture simulation has many similarities to text clustering. in prior work on clustering techniques to reduce simulation time, k-means clustering was used to identify representative program phases. in this paper we apply a mixture of multinomials to the clustering problem and show its advantages over using k-means on simulation data. we have implemented these two clustering algorithms and evaluate how well they can characterize program behavior. by adopting a mixture of multinomials model, we find that we can maintain simulation result fidelity, while greatly reducing overall simulation time. we report results for a range of applications taken from the spec2000 benchmark suite.
privacy preserving regression modelling via distributed computation. reluctance of data owners to share their possibly confidential or proprietary data with others who own related databases is a serious impediment to conducting a mutually beneficial data mining analysis. we address the case of vertically partitioned data -- multiple data owners/agencies each possess a few attributes of every data record. we focus on the case of the agencies wanting to conduct a linear regression analysis with complete records without disclosing values of their own attributes. this paper describes an algorithm that enables such agencies to compute the exact regression coefficients of the global regression equation and also perform some basic goodness-of-fit diagnostics while protecting the confidentiality of their data. in more general settings beyond the privacy scenario, this algorithm can also be viewed as method for the distributed computation for regression analyses.
clinical and financial outcomes analysis with existing hospital patient records. existing patient records are a valuable resource for automated outcomes analysis and knowledge discovery. however, key clinical data in these records is typically recorded in unstructured form as free text and images, and most structured clinical information is poorly organized. time-consuming interpretation and analysis is required to convert these records into structured clinical data. thus, only a tiny fraction of this resource is utilized. we present remind, a bayesian framework for reliable extraction and meaningful inference from nonstructured data. remind integrates and blends the structured and unstructured clinical data in patient records to automatically created high-quality structured clinical data. this structuring allows existing patient records to be mined for quality assurance, regulatory compliance, and to relate financial and clinical factors. we demonstrate remind on two medical applications: (a) extract "recurrence", the key outcome for measuring treatment effectiveness, for colon cancer patients (ii) extract key diagnoses and complications for acute myocardial infarction (heart attack) patients, and demonstrate the impact of these clinical factors on financial outcomes.
interactive deduplication using active learning. deduplication is a key operation in integrating data from multiple sources. the main challenge in this task is designing a function that can resolve when a pair of records refer to the same entity in spite of various data inconsistencies. most existing systems use hand-coded functions. one way to overcome the tedium of hand-coding is to train a classifier to distinguish between duplicates and non-duplicates. the success of this method critically hinges on being able to provide a covering and challenging set of training pairs that bring out the subtlety of deduplication function. this is non-trivial because it requires manually searching for various data inconsistencies between any two records spread apart in large lists.we present our design of a learning-based deduplication system that uses a novel method of interactively discovering challenging training pairs using active learning. our experiments on real-life datasets show that active learning significantly reduces the number of instances needed to achieve high accuracy. we investigate various design issues that arise in building a system to provide interactive response, fast convergence, and interpretable output.
combining clustering and co-training to enhance text classification using unlabelled data. in this paper, we present a new co-training strategy that makes use of unlabelled data. it trains two predictors in parallel, with each predictor labelling the unlabelled data for training the other predictor in the next round. both predictors are support vector machines, one trained using data from the original feature space, the other trained with new features that are derived by clustering both the labelled and unlabelled data. hence, unlike standard co-training methods, our method does not require a priori the existence of two redundant views either of which can be used for classification, nor is it dependent on the availability of two different supervised learning algorithms that complement each other.we evaluated our method with two classifiers and three text benchmarks: webkb, reuters newswire articles and 20 newsgroups. our evaluation shows that our co-training technique improves text classification accuracy especially when the number of labelled examples are very few.
cross-training: learning probabilistic mappings between topics. classification is a well-established operation in text mining. given a set of labels a and a set da of training documents tagged with these labels, a classifier learns to assign labels to unlabeled test documents. suppose we also had available a different set of labels b, together with a set of documents db marked with labels from b. if a and b have some semantic overlap, can the availability of db help us build a better classifier for a, and vice versa? we answer this question in the affirmative by proposing cross-training: a new approach to semi-supervised learning in presence of multiple label sets. we give distributional and discriminative algorithms for cross-training and show, through extensive experiments, that cross-training can discover and exploit probabilistic relations between two taxonomies for more accurate classification.
predicting the product purchase patterns of corporate customers. this paper describes tippps (time interleaved product purchase prediction system), which analyses billing data of corporate customers in a large telecommunications company in order to predict high value upsell opportunities. the challenges presented by this prediction problem are significant. firstly, the diversity of products used by corporate telecommunications customers is huge. this, coupled with low product take-up rates, makes this a problem of learning from a very high dimensional feature space with very few minority examples. further, it is important to give priority specifically to the identification of those new customers who are of high value. these challenges are overcome by introducing a number of modifications to standard data pre-processing and machine learning algorithms, the most important of which are time-interleaving of data and value weighting. time interleaving is the concatenation of examples from multiple time periods, thus increasing the number of training examples, and hence the number of minority examples. value weighting assigns importance to minority examples in proportion to the dollar value of take-up, thus biasing the system to identify high value customers. these modifications create a novel algorithm that makes the prediction system practical and usable.comparison with other techniques designed for similar problems shows that the expected average improvement in ranking accuracy achieved using these modifications is 3.7%. tippps has been in operation for several months and has been successful in identifying many upsell opportunities that were not identified by using the previous manual system.
using structure indices for efficient approximation of network properties. statistics on networks have become vital to the study of relational data drawn from areas such as bibliometrics, fraud detection, bioinformatics, and the internet. calculating many of the most important measures - such as betweenness centrality, closeness centrality, and graph diameter-requires identifying short paths in these networks. however, finding these short paths can be intractable for even moderate-size networks. we introduce the concept of a network structure index (nsi), a composition of (1) a set of annotations on every node in the network and (2) a function that uses the annotations to estimate graph distance between pairs of nodes. we present several varieties of nsis, examine their time and space complexity, and analyze their performance on synthetic and real data sets. we show that creating an nsi for a given network enables extremely efficient and accurate estimation of a wide variety of network statistics on that network.
sampling-based sequential subgroup mining. subgroup discovery is a learning task that aims at finding interesting rules from classified examples. the search is guided by a utility function, trading off the coverage of rules against their statistical unusualness. one shortcoming of existing approaches is that they do not incorporate prior knowledge. to this end a novel generic sampling strategy is proposed. it allows to turn pattern mining into an iterative process. in each iteration the focus of subgroup discovery lies on those patterns that are unexpected with respect to prior knowledge and previously discovered patterns. the result of this technique is a small diverse set of understandable rules that characterise a specified property of interest. as another contribution this article derives a simple connection between subgroup discovery and classifier induction. for a popular utility function this connection allows to apply any standard rule induction algorithm to the task of subgroup discovery after a step of stratified resampling. the proposed techniques are empirically compared to state of the art subgroup discovery algorithms.
mining knowledge-sharing sites for viral marketing. viral marketing takes advantage of networks of influence among customers to inexpensively achieve large changes in behavior. our research seeks to put it on a firmer footing by mining these networks from data, building probabilistic models of them, and using these models to choose the best viral marketing plan. knowledge-sharing sites, where customers review products and advise each other, are a fertile source for this type of data mining. in this paper we extend our previous techniques, achieving a large reduction in computational cost, and apply them to data from a knowledge-sharing site. we optimize the amount of marketing funds spent on each customer, rather than just making a binary decision on whether to market to him. we take into account the fact that knowledge of the network is partial, and that gathering that knowledge can itself have a cost. our results show the robustness and utility of our approach.
dense itemsets. frequent itemset mining has been the subject of a lot of work in data mining research ever since association rules were introduced. in this paper we address a problem with frequent itemsets: that they only count rows where all their attributes are present, and do not allow for any noise. we show that generalizing the concept of frequency while preserving the performance of mining algorithms is nontrivial, and introduce a generalization of frequent itemsets, dense itemsets. dense itemsets do not require all attributes to be present at the same time; instead, the itemset needs to define a sufficiently large submatrix that exceeds a given density threshold of attributes present.we consider the problem of computing all dense itemsets in a database. we give a levelwise algorithm for this problem, and also study the top-$k$ variations, i.e., finding the k densest sets with a given support, or the k best-supported sets with a given density. these algorithms select the other parameter automatically, which simplifies mining dense itemsets in an explorative way. we show that the concept captures natural facets of data sets, and give extensive empirical results on the performance of the algorithms. combining the concept of dense itemsets with set cover ideas, we also show that dense itemsets can be used to obtain succinct descriptions of large datasets. we also discuss some variations of dense itemsets.
admit: anomaly-based data mining for intrusions. security of computer systems is essential to their acceptance and utility. computer security analysts use intrusion detection systems to assist them in maintaining computer system security. this paper deals with the problem of differentiating between masqueraders and the true user of a computer terminal. prior efficient solutions are less suited to real time application, often requiring all training data to be labeled, and do not inherently provide an intuitive idea of what the data model means. our system, called admit, relaxes these constraints, by creating user profiles using semi-incremental techniques. it is a real-time intrusion detection system with host-based data collection and processing. our method also suggests ideas for dealing with concept drift and affords a detection rate as high as 80.3% and a false positive rate as low as 15.3%.
improving spatial locality of programs via data mining. in most computer systems, page fault rate is currently minimized by generic page replacement algorithms which try to model the temporal locality inherent in programs. in this paper, we propose two algorithms, one greedy and the other stochastic, designed for program specific code restructuring as a means of increasing spatial locality within a program. both algorithms effectively decrease average working set size and hence the page fault rate. our methods are more effective than traditional approaches due to use of domain information. we illustrate the efficacy of our algorithms on actual data mining algorithms.
treedt: gene mapping by tree disequilibrium test. we introduce and evaluate treedt, a novel gene mapping method which is based on discovering and assessing tree-like patterns in genetic marker data. gene mapping aims at discovering a statistical connection from a particular disease or trait to a narrow region in the genome. in a typical case-control setting, data consists of genetic markers typed for a set of disease-associated chromosomes and a set of control chromosomes. a computer scientist would view this data as a set of strings.treedt extracts, essentially in the form of substrings and prefix trees, information about the historical recombinations in the population. this information is used to locate fragments potentially inherited from a common diseased founder, and to map the disease gene into the most likely such fragment. the method measures for each chromosomal location the disequilibrium of the prefix tree of marker strings starting from the location, to assess the distribution of disease-associated chromosomes.we evaluate experimentally the performance of treedt on realistic, simulated data sets, and comparisons to state of the art methods (tdt, hpm) show that treedt is very competitive.
selection, combination, and evaluation of effective software sensors for detecting abnormal computer usage. we present and empirically analyze a machine-learning approach for detecting intrusions on individual computers. our winnow-based algorithm continually monitors user and system behavior, recording such properties as the number of bytes transferred over the last 10 seconds, the programs that currently are running, and the load on the cpu. in all, hundreds of measurements are made and analyzed each second. using this data, our algorithm creates a model that represents each particular computer's range of normal behavior. parameters that determine when an alarm should be raised, due to abnormal activity, are set on a per-computer basis, based on an analysis of training data. a major issue in intrusion-detection systems is the need for very low false-alarm rates. our empirical results suggest that it is possible to obtain high intrusion-detection rates (95%) and low false-alarm rates (less than one per day per computer), without "stealing" too many cpu cycles (less than 1%). we also report which system measurements are the most valuable in terms of detecting intrusions. a surprisingly large number of different measurements prove significantly useful.
frequent-subsequence-based prediction of outer membrane proteins. a number of medically important disease-causing bacteria (collectively called gram-negative bacteria) are noted for the extra "outer" membrane that surrounds their cell. proteins resident in this membrane (outer membrane proteins, or omps) are of primary research interest for antibiotic and vaccine drug design as they are on the surface of the bacteria and so are the most accessible targets to develop new drugs against. with the development of genome sequencing technology and bioinformatics, biologists can now deduce all the proteins that are likely produced in a given bacteria and have attempted to classify where proteins are located in a bacterial cell. however such protein localization programs are currently least accurate when predicting omps, and so there is a current need for the development of a better omp classifier. data mining research suggests that the use of frequent patterns has good performance in aiding the development of accurate and efficient classification algorithms. in this paper, we present two methods to identify omps based on frequent subsequences and test them on all gram-negative bacterial proteins whose localizations have been determined by biological experiments. one classifier follows an association rule approach, while the other is based on support vector machines (svms). we compare the proposed methods with the state-of-the-art methods in the biological domain. the results demonstrate that our methods are better both in terms of accurately identifying omps and providing biological insights that increase our understanding of the structures and functions of these important proteins.