waashk/dblp huggingface dataset:
lungcad: a clinically approved, machine learning system for lung cancer detection. we present lungcad, a computer aided diagnosis (cad) system that employs a classification algorithm for detecting solid pulmonary nodules from ct thorax studies. we briefly describe some of the machine learning techniques developed to overcome the real world challenges in this medical domain. the most significant hurdle in transitioning from a machine learning research prototype that performs well on an in-house dataset into a clinically deployable system, is the requirement that the cad system be tested in a clinical trial. we describe the clinical trial in which lungcad was tested: a large scale multi-reader, multi-case (mrmc) retrospective observational study to evaluate the effect of cad in clinical practice for detecting solid pulmonary nodules from ct thorax studies. the clinical trial demonstrates that every radiologist that participated in the trial had a significantly greater accuracy with lungcad, both for detecting nodules and identifying potentially actionable nodules; this, along with other findings from the trial, has resulted in fda approval for lungcad in late 2006.
distributed multivariate regression based on influential observations. large-scale data sets are sometimes logically and physically distributed in separate databases. the issues of mining these data sets are not just their sizes, but also the distributed nature. the complication is that communicating all the data to a central database would be too slow. to reduce communication costs, one could compress the data during transmission. another method is random sampling. we propose an approach for distributed multivariate regression based on sampling and discuss its relationship with the compression method. the central idea is motivated by the observation that, although communication is limited, each individual site can still scan and process all the data it holds. thus it is possible for the site to communicate only influential samples without seeing data in other sites. we exploit this observation and derive a method that provides tradeoff between communication cost and accuracy. experimental results show that it is better than the compression method and random sampling.
pebl: positive example based learning for web page classification using svm. web page classification is one of the essential techniques for web mining. specifically, classifying web pages of a user-interesting class is the first step of mining interesting information from the web. however, constructing a classifier for an interesting class requires laborious pre-processing such as collecting positive and negative training examples. for instance, in order to construct a "homepage" classifier, one needs to collect a sample of homepages (positive examples) and a sample of non-homepages (negative examples). in particular, collecting negative training examples requires arduous work and special caution to avoid biasing them. we introduce in this paper the positive example based learning (pebl) framework for web page classification which eliminates the need for manually collecting negative training examples in pre-processing. we present an algorithm called mapping-convergence (m-c) that achieves classification accuracy (with positive and unlabeled data) as high as that of traditional svm (with positive and negative data). our experiments show that when the m-c algorithm uses the same amount of positive examples as that of traditional svm, the m-c algorithm performs as well as traditional svm.
automatic labeling of multinomial topic models. multinomial distributions over words are frequently used to model topics in text collections. a common, major challenge in applying all such topic models to any text mining problem is to label a multinomial topic model accurately so that a user can interpret the discovered topic. so far, such labels have been generated manually in a subjective way. in this paper, we propose probabilistic approaches to automatically labeling multinomial topic models in an objective way. we cast this labeling problem as an optimization problem involving minimizing kullback-leibler divergence between word distributions and maximizing mutual information between a label and a topic model. experiments with user study have been done on two text data sets with different genres.the results show that the proposed labeling methods are quite effective to generate labels that are meaningful and useful for interpreting the discovered topic models. our methods are general and can be applied to labeling topics learned through all kinds of topic models such as plsa, lda, and their variations.
efficiently handling feature redundancy in high-dimensional data. high-dimensional data poses a severe challenge for data mining. feature selection is a frequently used technique in pre-processing high-dimensional data for successful data mining. traditionally, feature selection is focused on removing irrelevant features. however, for high-dimensional data, removing redundant features is equally critical. in this paper, we provide a study of feature redundancy in high-dimensional data and propose a novel correlation-based approach to feature selection within the filter model. the extensive empirical study using real-world data shows that the proposed approach is efficient and effective in removing redundant and irrelevant features.
characterising the difference. characterising the differences between two databases is an often occurring problem in data mining. detection of change over time is a prime example, comparing databases from two branches is another one. the key problem is to discover the patterns that describe the difference. emerging patterns provide only a partial answer to this question. in previous work, we showed that the data distribution can be captured in a pattern-based model using compression [12]. here, we extend this approach to define a generic dissimilarity measure on databases. moreover, we show that this approach can identify those patterns that characterise the differences between two distributions. experimental results show that our method provides a well-founded way to independently measure database dissimilarity that allows for thorough inspection of the actual differences. this illustrates the use of our approach in real world data mining.
redundancy based feature selection for microarray data. in gene expression microarray data analysis, selecting a small number of discriminative genes from thousands of genes is an important problem for accurate classification of diseases or phenotypes. the problem becomes particularly challenging due to the large number of features (genes) and small sample size. traditional gene selection methods often select the top-ranked genes according to their individual discriminative power without handling the high degree of redundancy among the genes. latest research shows that removing redundant genes among selected ones can achieve a better representation of the characteristics of the targeted phenotypes and lead to improved classification accuracy. hence, we study in this paper the relationship between feature relevance and redundancy and propose an efficient method that can effectively remove redundant genes. the efficiency and effectiveness of our method in comparison with representative methods has been demonstrated through an empirical study using public microarray data sets.
classifying large data sets using svms with hierarchical clusters. support vector machines (svms) have been promising methods for classification and regression analysis because of their solid mathematical foundations which convery several salient properties that other methods hardly provide. however, despite the prominent properties of svms, they are not as favored for large-scale data mining as for pattern recognition or machine learning because the training complexity of svms is highly dependent on the size of a data set. many real-world data mining applications involve millions or billions of data records where even multiple scans of the entire data are too expensive to perform. this paper presents a new method, clustering-based svm (cb-svm), which is specifically designed for handling very large data sets. cb-svm applies a hierarchical micro-clustering algorithm that scans the entire data set only once to provide an svm with high quality samples that carry the statistical summaries of the data such that the summaries maximize the benefit of learning the svm. cb-svm tries to generate the best svm boundary for very large data sets given limited amount of resources. our experiments on synthetic and real data sets show that cb-svm is highly scalable for very large data sets while also generating high classification accuracy.
supervised probabilistic principal component analysis. principal component analysis (pca) has been extensively applied in data mining, pattern recognition and information retrieval for unsupervised dimensionality reduction. when labels of data are available, e.g., in a classification or regression task, pca is however not able to use this information. the problem is more interesting if only part of the input data are labeled, i.e., in a semi-supervised setting. in this paper we propose a supervised pca model called sppca and a semi-supervised pca model called s2ppca, both of which are extensions of a probabilistic pca model. the proposed models are able to incorporate the label information into the projection phase, and can naturally handle multiple outputs (i.e., in multi-task learning problems). we derive an efficient em learning algorithm for both models, and also provide theoretical justifications of the model behaviors. sppca and s2ppca are compared with other supervised projection methods on various learning tasks, and show not only promising performance but also good scalability.
learning and making decisions when costs and probabilities are both unknown. in many machine learning domains, misclassification costs are different for different examples, in the same way that class membership probabilities are example-dependent. in these domains, both costs and probabilities are unknown for test examples, so both cost estimators and probability estimators must be learned. this paper first discusses how to make optimal decisions given cost and probability estimates, and then presents decision tree learning methods for obtaining well-calibrated probability estimates. the paper then explains how to obtain unbiased estimators for example- dependent costs, taking into account the difficulty that in general, probabilities and costs are not independent random variables, and the training examples for which costs are known are not representative of all examples. the latter problem is called sample selection bias in econometrics. our solution to it is based on nobel prize-winning work due to the economist james heckman. we show that the methods we propose are successful in a comprehensive comparison with metacost that uses the well-known and difficult dataset from the kdd''98 data mining contest.
joint cluster analysis of attribute and relationship data withouta-priori specification of the number of clusters. in many applications, attribute and relationship data areavailable, carrying complementary information about real world entities. in such cases, a joint analysis of both types of data can yield more accurate results than classical clustering algorithms that either use only attribute data or only relationship (graph) data. the connected k-center (ckc) has been proposed as the first joint cluster analysis model to discover k clusters which are cohesive on both attribute and relationship data. however, it is well-known that prior knowledge on the number of clusters is often unavailable in applications such as community dentification and hotspot analysis. in this paper, we introduce and formalize the problem of discovering an a-priori unspecified number of clusters in the context of joint cluster analysis of attribute and relationship data, called connected x clusters (cxc) problem. true clusters are assumed to be compact and distinctive from their neighboring clusters in terms of attribute data and internally connected in terms of relationship data. different from classical attribute-based clustering methods, the neighborhood of clusters is not defined in terms of attribute data but in terms of relationship data. to efficiently solve the cxc problem, we present jointclust, an algorithm which adopts a dynamic two-phase approach. in the first phase, we find so called cluster atoms. we provide a probability analysis for thisphase, which gives us a probabilistic guarantee, that each true cluster is represented by at least one of the initial cluster atoms. in the second phase, these cluster atoms are merged in a bottom-up manner resulting in a dendrogram. the final clustering is determined by our objective function. our experimental evaluation on several real datasets demonstrates that jointclust indeed discovers meaningful and accurate clusterings without requiring the user to specify the number of clusters.
transforming classifier scores into accurate multiclass probability estimates. class membership probability estimates are important for many applications of data mining in which classification outputs are combined with other sources of information for decision-making, such as example-dependent misclassification costs, the outputs of other classifiers, or domain knowledge. previous calibration methods apply only to two-class problems. here, we show how to obtain accurate probability estimates for multiclass problems by combining calibrated binary probability estimates. we also propose a new method for obtaining calibrated two-class probability estimates that can be applied to any classifier that produces a ranking of examples. using naive bayes and support vector machine classifiers, we give experimental results from a variety of two-class and multiclass domains, including direct marketing, text categorization and digit recognition.
training structural svms with kernels using sampled cuts. discriminative training for structured outputs has found increasing applications in areas such as natural language processing, bioinformatics, information retrieval, and computer vision. focusing on large-margin methods, the most general (in terms of loss function and model structure) training algorithms known to date are based on cutting-plane approaches. while these algorithms are very efficient for linear models, their training complexity becomes quadratic in the number of examples when kernels are used. to overcome this bottleneck, we propose new training algorithms that use approximate cutting planes and random sampling to enable efficient training with kernels. we prove that these algorithms have improved time complexity while providing approximation guarantees. in empirical evaluations, our algorithms produced solutions with training and test error rates close to those of exact solvers. even on binary classification problems where highly optimized conventional training methods exist (e.g. svm-light), our methods are about an order of magnitude faster than conventional training methods on large datasets, while remaining competitive in speed on datasets of medium size.
pattern lattice traversal by selective jumps. regardless of the frequent patterns to discover, either the full frequent patterns or the condensed ones, either closed or maximal, the strategy always includes the traversal of the lattice of candidate patterns. we study the existing depth versus breadth traversal approaches for generating candidate patterns and propose in this paper a new traversal approach that jumps in the search space among only promising nodes. our leaping approach avoids nodes that would not participate in the answer set and reduce drastically the number of candidate patterns. we use this approach to efficiently pinpoint maximal patterns at the border of the frequent patterns in the lattice and collect enough information in the process to generate all subsequent patterns.
real-time ranking with concept drift using expert advice. in many practical applications, one is interested in generating a ranked list of items using information mined from continuous streams of data. for example, in the context of computer networks, one might want to generate lists of nodes ranked according to their susceptibility to attack. in addition, real-world data streams often exhibit concept drift, making the learning task even more challenging. we present an online learning approach to ranking with concept drift, using weighted majority techniques. by continuously modeling different snapshots of the data and tuning our measure of belief in these models over time, we capture changes in the underlying concept and adapt our predictions accordingly. we measure the performance of our algorithm on real electricity data as well as asynthetic data stream, and demonstrate that our approach to ranking from stream data outperforms previously known batch-learning methods and other online methods that do not account for concept drift.
estimating rates of rare events at multiple resolutions. we consider the problem of estimating occurrence rates of rare eventsfor extremely sparse data, using pre-existing hierarchies to perform inference at multiple resolutions. in particular, we focus on the problem of estimating click rates for (webpage, advertisement) pairs (called impressions) where both the pages and the ads are classified into hierarchies that capture broad contextual information at different levels of granularity. typically the click rates are low and the coverage of the hierarchies is sparse. to overcome these difficulties we devise a sampling method whereby we analyze aspecially chosen sample of pages in the training set, and then estimate click rates using a two-stage model. the first stage imputes the number of (webpage, ad) pairs at all resolutions of the hierarchy to adjust for the sampling bias. the second stage estimates clickrates at all resolutions after incorporating correlations among sibling nodes through a tree-structured markov model. both models are scalable and suited to large scale data mining applications. on a real-world dataset consisting of 1/2 billion impressions, we demonstrate that even with 95% negative (non-clicked) events in the training set, our method can effectively discriminate extremely rare events in terms of their click propensity.
distributed classification in peer-to-peer networks. this work studies the problem of distributed classification in peer-to-peer(p2p) networks. while there has been a significant amount of work in distributed classification, most of existing algorithms are not designed for p2p networks. indeed, as server-less and router-less systems, p2p networks impose several challenges for distributed classification: (1) it is not practical to have global synchronization in large-scale p2p networks; (2)there are frequent topology changes caused by frequent failure and recovery of peers; and (3) there are frequent on-the-fly data updates on each peer. in this paper, we propose an ensemble paradigm for distributed classification in p2p networks. under this paradigm, each peer builds its local classifiers on the local data and the results from all local classifiers are then combined by plurality voting. to build local classifiers, we adopt the learning algorithm of pasting bites to generate multiple local classifierson each peer based on the local data. to combine local results, we propose a general form of distributed plurality voting (dpv) protocol in dynamic p2p networks. this protocol keeps the single-site validity for dynamic networks, and supports the computing modes of both one-shot query and continuous monitoring. we theoretically prove that the condition (bob check this 'c')ω0 for sending messages used in dpv0 is locally communication-optimal to achieve the above properties. finally, experimental results on real-world p2p networks show that: (1) the proposed ensemble paradigm is effective even if there are thousands of local classifiers; (2) in most cases, the dpv0 algorithm is local in the sense that voting is processed using information gathered from a very small vicinity, whose size is independent of the network size; (3) dpv0 is significantly more communication-efficient than existing algorithms for distributed plurality voting.
efficiently mining frequent trees in a forest. mining frequent trees is very useful in domains like bioinformatics, web mining, mining semistructured data, and so on. we formulate the problem of mining (embedded) subtrees in a forest of rooted, labeled, and ordered trees. we present treeminer, a novel algorithm to discover all frequent subtrees in a forest, using a new data structure called scope-list. we contrast treeminer with a pattern matching tree mining algorithm (patternmatcher). we conduct detailed experiments to test the performance and scalability of these methods. we find that treeminer outperforms the pattern matching approach by a factor of 4 to 20, and has good scaleup properties. we also present an application of tree mining to analyze real web logs for usage patterns.
mining correlated bursty topic patterns from coordinated text streams. previous work on text mining has almost exclusively focused on a single stream. however, we often have available multiple text streams indexed by the same set of time points (called coordinated text streams), which offer new opportunities for text mining. for example, when a major event happens, all the news articles published by different agencies in different languages tend to cover the same event for a certain period, exhibiting a correlated bursty topic pattern in all the news article streams. in general, mining correlated bursty topic patterns from coordinated text streams can reveal interesting latent associations or events behind these streams. in this paper, we define and study this novel text mining problem. we propose a general probabilistic algorithm which can effectively discover correlated bursty patterns and their bursty periods across text streams even if the streams have completely different vocabularies (e.g., english vs chinese). evaluation of the proposed method on a news data set and a literature data set shows that it can effectively discover quite meaningful topic patterns from both data sets: the patterns discovered from the news data set accurately reveal the major common events covered in the two streams of news articles (in english and chinese, respectively), while the patterns discovered from two database publication streams match well with the major research paradigm shifts in database research. since the proposed method is general and does not require the streams to share vocabulary, it can be applied to any coordinated text streams to discover correlated topic patterns that burst in multiple streams in the same period.