waashk/dblp huggingface dataset:
mining plans for customer-class transformation. we consider the problem of mining high-utility plansfrom historical plan databases that can be used to transformcustomers from one class to other, more desirable classes.traditional data mining algorithms are focused on findingfrequent sequences. but high frequency may not imply lowcosts and high benefits. traditional markov decision process(mdp) algorithms are designed to address this issueby bringing in the concept of utility, but these algorithmsare also known to be expensive to execute. in this paper,we present a novel algorithm auplan which automaticallygenerates sequential plans with high utility by combiningdata mining and ai planning. these high-utility plans couldbe used to convert groups of customers from less desirablestates to more desirable ones. our algorithm adapts theapriori algorithm by considering the concepts of plans andutilities. we show through empirical studies that planningusing our integrated algorithm produces high-utility plansefficiently.
regression clustering. complex distribution in real-world data is oftenmodeled by a mixture of simpler distributions. clusteringis one of the tools to reveal the structure of this mixture.the same is true to the datasets with chosen responsevariables that people run regression on. withoutseparating the clusters with very different responseproperties, the residue error of the regression is large.input variable selection could also be misguided to ahigher complexity by the mixture. in regressionclustering (rc), k (>1) regression functions are appliedto the dataset simultaneously which guide the clusteringof the dataset into k subsets each with a simplerdistribution matching its guiding function. each functionis regressed on its own subset of data with a muchsmaller residue error. both the regressions and theclustering optimize a common objective function. wepresent a rc algorithm based on k-harmonic meansclustering algorithm and compare it with other existingrc algorithms based on k-means and em.
on precision and recall of multi-attribute data extraction from semistructured sources. machine learning techniques for data extraction fromsemistructured sources exhibit different precision and recallcharacteristics. however to date the formal relationship betweenlearning algorithms and their impact on these twometrics remains unexplored. this paper proposes a formalizationof precision and recall of extraction and investigatesthe complexity-theoretic aspects of learning algorithms formulti-attribute data extraction based on this formalism. weshow that there is a tradeoff between precision/recall of extractionand computational efficiency and present experimentalresults to demonstrate the practical utility of theseconcepts in designing scalable data extraction algorithmsfor improving recall without compromising on precision.
a polygonal line algorithm based nonlinear feature extraction method. we propose a polygonal line based principal curve algorithm for nonlinear feature extraction, in which the nonlinearities among the multivariable data can be described by a set of local linear models. the proposed algorithm integrates the linear pca approach with the polygonal line algorithm to represent complicated nonlinear data structure. statistical redundancy elimination for high dimensional data is also discussed for describing the underlying principal curves without much loss of information among the original data sets. the polygonal line algorithm can produce robust and accurate nonlinear curve estimation for different multivariate data types, and it is helpful in reducing the computation complexity for existing principal curve approaches when the sample size is large.
segmenting customer transactions using a pattern-based clustering approach. grouping customer transactions into categories helpsunderstand customers better. the marketing literaturehas concentrated on identifying important segmentationvariables (e.g. customer loyalty) and on using clusteringand mixture models for segmentation. the data miningliterature has provided various clustering algorithms forsegmentation. in this paper we investigate using"pattern-based" clustering approaches to groupingcustomer transactions. we argue that there are clustersin transaction data based on natural behavioral patterns,and present a new technique, yaca, that groupstransactions such that itemsets generated from eachcluster, while similar to each other, are different fromones generated from others. we present experimentalresults from user-centric web usage data thatdemonstrates that yaca generates a highly effectiveclustering of transactions.
learning rules from highly unbalanced data sets. this paper presents a simple and effective rule learning algorithm for highly unbalanced data sets. by using the small size of the minority class to its advantage this algorithm can conduct an almost exhaustive search for patterns within the known fraudulent cases. this algorithm was designed for and successfully applied to a law enforcement problem, which involves discovering common patterns of fraudulent transactions.
on the stationarity of multivariate time series for correlation-based data analysis. multivariate time series (mts) data sets are common in various multimedia, medical and financial application domains. these applications perform several data-analysis operations on large number of mts data sets such as similarity searches, feature-subset-selection, clustering and classifications. correlation-based techniques, such as principal component analysis (pca), have proven to improve the efficiency of many of the above-mentioned data-analysis operations on mts, which implies that the correlation coefficientsconcisely represent the original mts data. however, if the statistical properties (e.g., variance) of mts data change over time dimension, i.e., mts data is non-stationary, the correlation coefficients are not stable. in this paper, we propose to utilize the stationarity of the mts data sets, in order to represent the original mts data more stably, as well as concisely with the correlation coefficients. that is, before performing any correlation-based data analysis, we first executes the stationarity test to decide whether the mts data is stationary or not, i.e., whether the correlation is stable or not. subsequently, for a non-stationary mts data set, we difference it to render the data set stationary. even though our approach is general, to focus the discussion we describe our approach within the context of our previously proposed technique for mts similarity search. in order to show the validity of our approach, we performed several experiments on four real-world data sets. the results show that the performance of our similarity search technique have significantly improved in terms of precision/recall.
visualizing global manifold based on distributed local data abstractions. mining distributed data for global knowledge is getting more attention recently. the problem is especially challenging when data sharing is prohibited due to local constraints like limited bandwidth and data privacy. in this paper, we investigate how to derive the embedded manifold (as a 2-d map)for a horizontally partitioned data set, where data cannot be shared among the partitions directly. we propose a model-based approach which computes hierarchical local data abstractions, aggregates the abstractions, and finally learns a global generative model — generative topographic mapping (gtm) based on the aggregated data abstraction. we applied the proposed method to two benchmarking data sets and demonstrated that the accuracy of the derived manifold can effectively be controlled by adjusting the data granularity level of the adopted local abstraction.
agile: a general approach to detect transitions in evolving data streams. in many applications such as e-commerce, system diagnosis and telecommunication services, data arrives in streams at a high speed. it is common that the underlying process generating the stream may change over time, either as a result of the fundamental evolution or in response to some external stimulus. detecting these changes is a very challenging problem of great practical importance. the overall volume of the stream usually far exceeds the available main memory and access to the data stream is typically performed via a linear scan in ascending order of the indices of the records. in this paper, we propose a novel approach, agile, to monitor streaming data and to detect distinguishable transitions of the underlying processes. agile has many advantages over the traditional hidden markov model, e.g., agile only requires one scan of the data.
infominer+: mining partial periodic patterns with gap penalties. in this paper, we focus on mining periodic patterns allowing some degreeof imperfection in the form of random replacement from a perfectperiodic pattern. information gain was proposed to identify patternswith events of vastly different occurrence frequencies and adjust forthe deviation from a pattern. however, it does not take any penaltyif there exists some gap between the pattern occurrences. in manyapplications, e.g., bio-informatics, it is important to identify subsequencesthat a pattern repeats perfectly (or near perfectly). as a solution,we extend the information gain measure to include a penaltyfor gaps between pattern occurrences. we call this measure as generalizedinformation gain. furthermore, we want to find subsequences' such that for a pattern p , the generalized information gain of pin s' is high. this is particularly useful in locating repeats in dnasequences. in this paper, we developed an effective mining algorithm,infominer+, to simultaneously mine significant patterns and the as-sociatedsubsequences.
mining california vital statistics data. vital statistics data offer a fertile ground for data mining. in this paper, we discuss the results of a data-mining project on the causes of death aspect of the vital statistics data in the state of california. a data-mining tool called cubist is used to build predictive models out of two million cases over a nine-year period. the objective of our study is to discover knowledge (trends, correlations or patterns) that may not be gleaned through standard techniques. the generated predictive models allow pertinent state agencies to gain insight into various aspects of the death rates in the state of california, to predict health issues related to the causes of death, to offer an aid to decision or policy-making process and to provide useful information services to the customers. the results obtained in our study contain valuable new information.
postprocessing decision trees to extract actionable knowledge. most data mining algorithms and tools stop at discoveredcustomer models, producing distribution informationon customer profiles. such techniques, when applied to industrialproblems such as customer relationship management(crm), are useful in pointing out customers who arelikely attritors and customers who are loyal, but they requirehuman experts to postprocess the mined information manually.most of the postprocessing techniques have been limitedto producing visualization results and interestingnessranking, but they do not directly suggest actions that wouldlead to an increase the objective function such as profit. inthis paper, we present a novel algorithm that suggest actionsto change customers from an undesired status (suchas attritors) to a desired one (such as loyal) while maximizingobjective function: the expected net profit. we developthese algorithms under resource constraints that areabound in reality. the contribution of the work is in takingthe output from an existing mature technique (decisiontrees, for example), and producing novel, actionable knowledgethrough automatic postprocessing.
a comparison study on algorithms for incremental update of frequent sequences. the problem of mining frequent sequences is to extractfrequently occurring subsequences in a sequence database.algorithms on this mining problem include gsp, mfs, andspade. the problem of incremental update of frequent sequencesis to keep track of the set of frequent sequences asthe underlying database changes. previous studies have extendedthe traditional algorithms to efficiently solve the up-dateproblem. these incremental algorithms include ism,gsp+and mfs+. each incremental algorithm has its owncharacteristics and they have been studied and evaluatedseparately under different scenarios. this paper presentsa comprehensive study on the relative performance of theincremental algorithms as well as their non-incrementalcounterparts. our goal is to provide guidelines on thechoice of an algorithm for solving the incremental updateproblem given the various characteristics of a sequencedatabase.
fd_mine: discovering functional dependencies in a database using equivalences. the discovery of fds from databases has recentlybecome a significant research problem. in this paper, wepropose a new algorithm, called fd_mine. fd_minetakes advantage of the rich theory of fds to reduce boththe size of the dataset and the number of fds to bechecked by using discovered equivalences. we show thatthe pruning does not lead to loss of information.experiments on 15 uci datasets show that fd_mine canprune more candidates than previous methods.
dimensionality reduction using kernel pooled local discriminant information. we study the use of kernel subspace methods for learninglow-dimensional representations for classification. we proposea kernel pooled local discriminant subspace methodand compare it against several competing techniques: generalizedfisher discriminant analysis (gda) and kernelprincipal components analysis (kpca) in classificationproblems. we evaluate the classification performance ofthe nearest-neighbor rule with each subspace representation.the experimental results demonstrate the efficacy ofthe kernel pooled local subspace method and the potentialfor substantial improvements over competing methods suchas kpca in some classification problems.
speculative markov blanket discovery for optimal feature selection. in this paper we address the problem of learning the markov blanket of a quantity from data in an efficient manner. markov blanket discovery can be used in the feature selection problem to find an optimal set of features for classificationtasks, and is a frequently-used preprocessing phase in data mining, especially for high-dimensional domains. our contribution is a novel algorithm for the induction of markov blankets from data, called fast-iamb, that employs a heuristic to quickly recover the markov blanket. empirical results show that fast-iamb performs in many cases faster and more reliably than existing algorithms without adversely affecting the accuracy of the recovered markov blankets.
discriminant analysis: a unified approach. linear discriminant analysis (lda) as a dimension reduction method is widely used in data mining and machine learning. it however suffers from the small sample size (sss) problem when data dimensionality is greater than the sample size. many modified methods have been proposed to address some aspect of this difficulty from a particular viewpoint. a comprehensive framework that provides a complete solution to the sss problem is still missing. in this paper, we provide a unified approach to lda, and investigate the sss problem in the framework of statistical learning theory. in such a unified approach, our analysis results in a deeper understanding of lda. we demonstrate that lda (and its nonlinear extension) belongs to the same framework where powerful classifiers such as support vector machines (svms) are formulated. in addition, this approach allows us to establish an error bound for lda. finally our experiments validate our theoretical analysis results.
a new optimization criterion for generalized discriminant analysis on undersampled problems. a new optimization criterion for discriminant analysis ispresented. the new criterion extends the optimization criteriaof the classical linear discriminant analysis (lda) byintroducing the pseudo-inverse when the scatter matricesare singular. it is applicable regardless of the relative sizesof the data dimension and sample size, overcoming a limitationof the classical lda. recently, a new algorithm calledlda/gsvd for structure-preserving dimension reductionhas been introduced, which extends the classical lda tovery high-dimensional undersampled problems by using thegeneralized singular value decomposition (gsvd). the solutionfrom the lda/gsvd algorithm is a special case of thesolution for our generalized criterion in this paper, which isalso based on gsvd.we also present an approximate solution for our gsvd-basedsolution, which reduces computational complexity byfinding sub-clusters of each cluster, and using their centroidsto capture the structure of each cluster. this reducedproblem yields much smaller matrices of which the gsvdcan be applied efficiently. experiments on text data, withup to 7000 dimensions, show that the approximation algorithmproduces results that are close to those produced bythe exact algorithm.
learning weighted naive bayes with accurate ranking. naive bayes is one of most effective classification algorithms. in many applications, however, a ranking of examples are more desirable than just classification. how to extend naive bayes to improve its ranking performance is an interesting and useful question in practice. weighted naive bayes is an extension of naive bayes, in which attributes have different weights. this paper investigates how to learn a weighted naive bayes with accurate ranking from data, or more precisely, how to learn the weights of a weighted naive bayes to produce accurate ranking. we explore various methods: the gain ratio method, the hill climbing method, and the markov chain monte carlo method, the hill climbing method combined with the gain ratio method, and the markov chain monte carlo method combined with the gain ratio method. our experiments show that a weighted naive bayes trained to produce accurate ranking outperforms naive bayes.
an efficient data mining technique for discovering interesting sequential patterns. mining sequential patterns is to discover sequentialpurchasing behaviors of most customers from a largeamount of customer transactions. in this paper, a datamining language is presented. from the data mininglanguage, use s can specify the interested items and thecriteria of the sequential patterns to be discovered. also,an efficient data mining technique is proposed to ext actthe sequential patterns according to the uses` requests.
bagging with adaptive costs. ensemble methods have proved to be highly effective in improving the performance of base learners under most circumstances. in this paper, we propose a new algorithm that combines the merits of some existing techniques, namely bagging, arcing and stacking. the basic structure of the algorithm resembles bagging. however, the misclassification cost of each training point is repeatedly adjusted according to its observed out-of-bag vote margin. in this way, the method gains the advantage of arcing - building the classifier the ensemble needs - without fixating on potentially noisy points. computational experiments show that this algorithm performs consistently better than bagging and arcing with linear and nonlinear base classifiers. in view of the characteristics of bacing, a hybrid ensemble learning strategy, which combines bagging and different versions of bacing, is proposed and studied empirically.
sentiment analyzer: extracting sentiments about a given topic using natural language processing techniques. we present sentiment analyzer (sa) that extracts sentiment(or opinion) about a subject from online text documents.instead of classifying the sentiment of an entire documentabout a subject, sa detects all references to the givensubject, and determines sentiment in each of the referencesusing natural language processing (nlp) techniques. oursentiment analysis consists of 1) a topic specific featureterm extraction, 2) sentiment extraction, and 3) (subject,sentiment) association by relationship analysis. sa utilizestwo linguistic resources for the analysis: the sentiment lexiconand the sentiment pattern database. the performanceof the algorithms was verified on online product review articles("digital camera" and "music" reviews), and moregeneral documents including general webpages and newsarticles.
sharing classifiers among ensembles from related problem domains. a classification ensemble is a group of classifiers that all solve the same prediction problem in different ways. it is well-known that combining the predictions of classifiers within the same problem domain using techniques like bagging or boosting often improves the performance. this research shows that sharing classifiers among different but closely related problem domains can also be helpful. in addition, a semi-definite programming based ensemble pruning method is implemented in order to optimize the selection of a subset of classifiers for each problem domain. computational results on a catalog dataset indicate that the ensembles resulting from sharing classifiers among different product categories generally have larger aucs than those ensembles trained only on their own categories. the pruning algorithm not only prevents the occasional decrease of effectiveness caused by conflicting concepts among the problem domains, but also provides a better understanding of the problem domains and their relationships.
mining genes in dna using genescout. in this paper, we present a new system, calledgenescout, for predicting gene structures in vertebrate genomicdna. the system contains specially designed hiddenmarkov models (hmms) for detecting functional sites includingprotein-translation start sites, mrna splicing junctiondonor and acceptor sites, etc. our main hypothesisis that, given a vertebrate genomic dna sequence s, it isalways possible to construct a directed acyclic graph gsuch that the path for the actual coding region of s is inthe set of all paths on g. thus, the gene detection problemis reduced to that of analyzing the paths in the graphg. a dynamic programming algorithm is used to find theoptimal path in g. the proposed system is trained usingan expectation-maximization (em) algorithm and its performanceon vertebrate gene prediction is evaluated usingthe 10-way cross-validation method. experimental resultsshow the good performance of the proposed system and itscomplementarity to a widely used gene detection system.
learning through changes: an empirical study of dynamic behaviors of probability estimation trees. in practice, learning from data is often hampered by the limited training examples. in this paper, as the size of training data varies, we empirically investigate several probability estimation tree algorithms over eighteen binary classification problems. nine metrics are used to evaluate their performances. our aggregated results show that ensemble trees consistently outperform single trees. confusion factor trees(cft) register poor calibration even as training size increases, which shows that cfts are potentially biased if data sets have small noise. we also provide analysis on the observed performance of the tree algorithms.
integrating hidden markov models and spectral analysis for sensory time series clustering. we present a novel approach for clustering sequences of multi-dimensional trajectory data obtained from a sensor network. the sensory time-series data present new challenges to data mining, including uneven sequence lengths, multi-dimensionality and high levels of noise. we adopt a principled approach, by first transforming all the data into an equal-length vector form while keeping as much temporal information as we can, and then applying dimensionality and noise reduction techniques such as spectral clustering to the transformed data. experimental evaluation on synthetic and real data shows that our proposed approach outperforms standard model-based clustering algorithms for time series data.