waashk/dblp huggingface dataset:
data mining with sparse grids using simplicial basis functions. recently we presented a new approach [18] to the classification problem arising in data mining. it is based on the regularization network approach but, in contrast to other methods which employ ansatz functions associated to data points, we use a grid in the usually high-dimensional feature space for the minimization process. to cope with the curse of dimensionality, we employ sparse grids [49]. thus, only o(hn-1nd-1) instead of o(hn-d) grid points and unknowns are involved. here d denotes the dimension of the feature space and hn = 2-n gives the mesh size. we use the sparse grid combination technique [28] where the classification problem is discretized and solved on a sequence of conventional grids with uniform mesh sizes in each dimension. the sparse grid solution is then obtained by linear combination. in contrast to our former work, where d-linear functions were used, we now apply linear basis functions based on a simplicial discretization. this allows to handle more dimensions and the algorithm needs less operations per data point.we describe the sparse grid combination technique for the classification problem, give implementational details and discuss the complexity of the algorithm. it turns out that the method scales linearly with the number of given data points. finally we report on the quality of the classifier built by our new method on data sets with up to 10 dimensions. it turns out that our new method achieves correctness rates which are competitive to that of the best existing methods.
a microeconomic data mining problem: customer-oriented catalog segmentation. the microeconomic framework for data mining [7] assumes that an enterprise chooses a decision maximizing the overall utility over all customers where the contribution of a customer is a function of the data available on that customer. in catalog segmentation, the enterprise wants to design k product catalogs of size r that maximize the overall number of catalog products purchased. however, there are many applications where a customer, once attracted to an enterprise, would purchase more products beyond the ones contained in the catalog. therefore, in this paper, we investigate an alternative problem formulation, that we call customer-oriented catalog segmentation, where the overall utility is measured by the number of customers that have at least a specified minimum interest t in the catalogs. we formally introduce the customer-oriented catalog segmentation problem and discuss its complexity. then we investigate two different paradigms to design efficient, approximate algorithms for the customer-oriented catalog segmentation problem, greedy (deterministic) and randomized algorithms. since greedy algorithms may be trapped in a local optimum and randomized algorithms crucially depend on a reasonable initial solution, we explore a combination of these two paradigms. our experimental evaluation on synthetic and real data demonstrates that the new algorithms yield catalogs of significantly higher utility compared to classical catalog segmentation algorithms.
web site mining: a new way to spot competitors, customers and suppliers in the world wide web. when automatically extracting information from the world wide web, most established methods focus on spotting single html-documents. however, the problem of spotting complete web sites is not handled adequately yet, in spite of its importance for various applications. therefore, this paper discusses the classification of complete web sites. first, we point out the main differences to page classification by discussing a very intuitive approach and its weaknesses. this approach treats a web site as one large html-document and applies the well-known methods for page classification. next, we show how accuracy can be improved by employing a preprocessing step which assigns an occurring web page to its most likely topic. the determined topics now represent the information the web site contains and can be used to classify it more accurately. we accomplish this by following two directions. first, we apply well established classification algorithms to a feature space of occurring topics. the second direction treats a site as a tree of occurring topics and uses a markov tree model for further classification. to improve the efficiency of this approach, we additionally introduce a powerful pruning method reducing the number of considered web pages. our experiments show the superiority of the markov tree approach regarding classification accuracy. in particular, we demonstrate that the use of our pruning method not only reduces the processing time, but also improves the classification accuracy.
a component-based framework for knowledge discovery in bioinformatics. motivation: in the field of bioinformatics there is an emerging need to integrate all knowledge discovery steps into a standardized modular framework. indeed, component-based development can significantly enhance reusability and productivity for short timeline projects with a small team. we present interactive knowledge discovery and data mining (ikdd), an application framework written in java that was specifically designed for these purposes.results: ikdd consists of a component-based architecture and a web-based tool for pre-clinical research and prototype development. the platform provides an intuitive and consistent interface to create and maintain components, e.g., data structures, algorithms and utilities to load, save and visualize data and pipelines. the rich-featured tool supplies database connectivity, workflow processing and rapid prototype building. the architecture was carefully designed using an object-oriented approach that respects crucial goals: usability, openness, robustness and functionality, especially in the abstraction and description of the components, which distinguishes it from other packages. ikdd is well-suited to serve as a public repository of components, to run scientific experiments with a high-level of reproducibility, and also to rapidly build prototypes. this paper describes the general architecture, and demonstrates through examples the ease by which a complex scenario implementation can be facilitated with ikdd.
price prediction and insurance for online auctions. online auctions are generating a new class of fine-grained data about online transactions. this data lends itself to a variety of applications and services that can be provided to both buyers and sellers in online marketplaces. we collect data from online auctions and use several classification algorithms to predict the probable-end prices of online auction items. this paper describes the feature extraction and selection process, and several machine learning formulations of the price prediction problem. as a prototype application, we developed auction price insurance that uses the predicted end-price to offer price insurance to sellers in online auctions. we define price insurance as a service that offers insurance to auction sellers that guarantees a price for their goods, for an appropriate premium. if the item sells for less than the insured price, the seller is reimbursed for the difference. we show that our price prediction techniques are accurate enough to offer price insurance as a profitable business. while this paper deals specifically with online auctions, we believe that this is an interesting case study that applies to dynamic markets where the price of the goods is variable and is affected by both internal and external factors that change over time.
to buy or not to buy: mining airfare data to minimize ticket purchase price. as product prices become increasingly available on the world wide web, consumers attempt to understand how corporations vary these prices over time. however, corporations change prices based on proprietary algorithms and hidden variables (e.g., the number of unsold seats on a flight). is it possible to develop data mining techniques that will enable consumers to predict price changes under these conditions?this paper reports on a pilot study in the domain of airline ticket prices where we recorded over 12,000 price observations over a 41 day period. when trained on this data, hamlet --- our multi-strategy data mining algorithm --- generated a predictive model that saved 341 simulated passengers $198,074 by advising them when to buy and when to postpone ticket purchases. remarkably, a clairvoyant algorithm with complete knowledge of future prices could save at most $320,572 in our simulation, thus hamlet's savings were 61.8% of optimal. the algorithm's savings of $198,074 represents an average savings of 23.8% for the 341 passengers for whom savings are possible. overall, hamlet saved 4.4% of the ticket price averaged over the entire set of 4,488 simulated passengers. our pilot study suggests that mining of price data available over the web has the potential to save consumers substantial sums of money per annum.
funnel report mining for the msn network. data mining research has long concentrated on the five main areas: clustering, association discovery, classification, forecasting and sequential patterns. web data mining projects are concerned mainly with text mining, user segmentation, forecasting web usage and analyzing users' clickstream patterns. we present a new type of web usage mining called funnel analysis or funnel report mining. a funnel report is a study of the retention behavior among a series of pages or sites. for example, of all hits on the home page of www.msn.com, what percentages of those are followed by hits to moneycentral.msn.com? what percentage of www.msn.com hits are followed by moneycentral.msn.com, and then www.msnbc.com? what are the most interesting funnels starting with www.msn.com? where does the greatest drop off rate occur after a user has hit msnbc? funnel reports are extremely useful in e-business because they give product planners an idea of how usable and well-structured their site is. from our experience performing web usage mining for the msn network of sites, funnel reports are requested even more than user segmentation analyses, site affiliation studies and classification exercises. in this paper, we define a framework for funnel analysis and provide a tree-based solution we have been using successfully to extract all relevant funnels using only one scan of the data file.
online novelty detection on temporal sequences. in this paper, we present a new framework for online novelty detection on temporal sequences. this framework include a mechanism for associating each detection result with a confidence value. based on this framework, we develop a concrete online detection algorithm, by modeling the temporal sequence using an online support vector regression algorithm. experiments on both synthetic and real world data are performed to demonstrate the promising performance of our proposed detection algorithm.
privacy preserving mining of association rules. we present a framework for mining association rules from transactions consisting of categorical items where the data has been randomized to preserve privacy of individual transactions. while it is feasible to recover association rules and preserve privacy using a straightforward "uniform" randomization, the discovered rules can unfortunately be exploited to find privacy breaches. we analyze the nature of privacy breaches and propose a class of randomization operators that are much more effective than uniform randomization in limiting the breaches. we derive formulae for an unbiased support estimator and its variance, which allow us to recover itemset supports from randomized datasets, and show how to incorporate these formulae into mining algorithms. finally, we present experimental results that validate the algorithm by applying it on real datasets.
k-ttp: a new privacy model for large-scale distributed environments. secure multiparty computation allows parties to jointly compute a function of their private inputs without revealing anything but the output. theoretical results [2] provide a general construction of such protocols for any function. protocols obtained in this way are, however, inefficient, and thus, practically speaking, useless when a large number of participants are involved.the contribution of this paper is to define a new privacy model -- k-privacy -- by means of an innovative, yet natural generalization of the accepted trusted third party model. this allows implementing cryptographically secure efficient primitives for real-world large-scale distributed systems.as an example for the usefulness of the proposed model, we employ k-privacy to introduce a technique for obtaining knowledge -- by way of an association-rule mining algorithm -- from large-scale data grids, while ensuring that the privacy is cryptographically secure.
regularized multi--task learning. past empirical work has shown that learning multiple related tasks from data simultaneously can be advantageous in terms of predictive performance relative to learning these tasks independently. in this paper we present an approach to multi--task learning based on the minimization of regularization functionals similar to existing ones, such as the one for support vector machines (svms), that have been successfully used in the past for single--task learning. our approach allows to model the relation between tasks in terms of a novel kernel function that uses a task--coupling parameter. we implement an instance of the proposed approach similar to svms and test it empirically using simulated as well as real data. the experimental results show that the proposed method performs better than existing multi--task learning methods and largely outperforms single--task learning using svms.
dimension induced clustering. it is commonly assumed that high-dimensional datasets contain points most of which are located in low-dimensional manifolds. detection of low-dimensional clusters is an extremely useful task for performing operations such as clustering and classification, however, it is a challenging computational problem. in this paper we study the problem of finding subsets of points with low intrinsic dimensionality. our main contribution is to extend the definition of fractal correlation dimension, which measures average volume growth rate, in order to estimate the intrinsic dimensionality of the data in local neighborhoods. we provide a careful analysis of several key examples in order to demonstrate the properties of our measure. based on our proposed measure, we introduce a novel approach to discover clusters with low dimensionality. the resulting algorithms extend previous density based measures, which have been successfully used for clustering. we demonstrate the effectiveness of our algorithms for discovering low-dimensional m-flats embedded in high dimensional spaces, and for detecting low-rank sub-matrices.
fragments of order. high-dimensional collections of 0--1 data occur in many applications. the attributes in such data sets are typically considered to be unordered. however, in many cases there is a natural total or partial order &pr; underlying the variables of the data set. examples of variables for which such orders exist include terms in documents, courses in enrollment data, and paleontological sites in fossil data collections. the observations in such applications are flat, unordered sets; however, the data sets respect the underlying ordering of the variables. by this we mean that if a &pr; b &pr; c are three variables respecting the underlying ordering &pr;, and both of variables a and c appear in an observation, then, up to noise levels, variable b also appears in this observation. similarly, if a1 &pr; a2 &pr; &hellip; &pr; al-1 &pr; ai is a longer sequence of variables, we do not expect to see many observations for which there are indices i < j < k such that ai and ak occur in the observation but aj does not.in this paper we study the problem of discovering fragments of orders of variables implicit in collections of unordered observations. we define measures that capture how well a given order agrees with the observed data. we describe a simple and efficient algorithm for finding all the fragments that satisfy certain conditions. we also discuss the sometimes necessary postprocessing for selecting only the best fragments of order. also, we relate our method with a sequencing approach that uses a spectral algorithm, and with the consecutive ones problem. we present experimental results on some real data sets (author lists of database papers, exam results data, and paleontological data).
assessing data mining results via swap randomization. the problem of assessing the significance of data mining results on high-dimensional 0--1 datasets has been studied extensively in the literature. for problems such as mining frequent sets and finding correlations, significance testing can be done by standard statistical tests such as chi-square, or other methods. however, the results of such tests depend only on the specific attributes and not on the dataset as a whole. moreover, the tests are difficult to apply to sets of patterns or other complex results of data mining algorithms. in this article, we consider a simple randomization technique that deals with this shortcoming. the approach consists of producing random datasets that have the same row and column margins as the given dataset, computing the results of interest on the randomized instances and comparing them to the results on the actual data. this randomization technique can be used to assess the results of many different types of data mining algorithms, such as frequent sets, clustering, and spectral analysis. to generate random datasets with given margins, we use variations of a markov chain approach which is based on a simple swap operation. we give theoretical results on the efficiency of different randomization methods, and apply the swap randomization method to several well-known datasets. our results indicate that for some datasets the structure discovered by the data mining algorithms is expected, given the row and column margins of the datasets, while for other datasets the discovered structure conveys information that is not captured by the margin counts.
fast discovery of connection subgraphs. we define a connection subgraph as a small subgraph of a large graph that best captures the relationship between two nodes. the primary motivation for this work is to provide a paradigm for exploration and knowledge discovery in large social networks graphs. we present a formal definition of this problem, and an ideal solution based on electricity analogues. we then show how to accelerate the computations, to produce approximate, but high-quality connection subgraphs in real time on very large (disk resident) graphs.we describe our operational prototype, and we demonstrate results on a social network graph derived from the world wide web. our graph contains 15 million nodes and 96 million edges, and our system still produces quality responses within seconds.
algorithms for discovering bucket orders from data. ordering and ranking items of different types are important tasks in various applications, such as query processing and scientific data mining. a total order for the items can be misleading, since there are groups of items that have practically equal ranks.we consider bucket orders, i.e., total orders with ties. they can be used to capture the essential order information without overfitting the data: they form a useful concept class between total orders and arbitrary partial orders. we address the question of finding a bucket order for a set of items, given pairwise precedence information between the items. we also discuss methods for computing the pairwise precedence data.we describe simple and efficient algorithms for finding good bucket orders. several of the algorithms have a provable approximation guarantee, and they scale well to large datasets. we provide experimental results on artificial and a real data that show the usefulness of bucket orders and demonstrate the accuracy and efficiency of the algorithms.
reverse testing: an efficient framework to select amongst classifiers under sample selection bias. one of the most important assumptions made by many classification algorithms is that the training and test sets are drawn from the same distribution, i.e., the so-called "stationary distribution assumption" that the future and the past data sets are identical from a probabilistic standpoint. in many domains of real-world applications, such as marketing solicitation, fraud detection, drug testing, loan approval, sub-population surveys, school enrollment among others, this is rarely the case. this is because the only labeled sample available for training is biased in different ways due to a variety of practical reasons and limitations. in these circumstances, traditional methods to evaluate the expected generalization error of classification algorithms, such as structural risk minimization, ten-fold cross-validation, and leave-one-out validation, usually return poor estimates of which classification algorithm, when trained on biased dataset, will be the most accurate for future unbiased dataset, among a number of competing candidates. sometimes, the estimated order of the learning algorithms' accuracy could be so poor that it is not even better than random guessing. therefore,a method to determine the most accurate learner is needed for data mining under sample selection bias for many real-world applications. we present such an approach that can determine which learner will perform the best on an unbiased test set, given a possibly biased training set, in a fraction of the computational cost to use cross-validation based approaches.
deriving marketing intelligence from online discussion. weblogs and message boards provide online forums for discussion that record the voice of the public. woven into this mass of discussion is a wide range of opinion and commentary about consumer products. this presents an opportunity for companies to understand and respond to the consumer by analyzing this unsolicited feedback. given the volume, format and content of the data, the appropriate approach to understand this data is to use large-scale web and text data mining technologies.this paper argues that applications for mining large volumes of textual data for marketing intelligence should provide two key elements: a suite of powerful mining and visualization technologies and an interactive analysis environment which allows for rapid generation and testing of hypotheses. this paper presents such a system that gathers and annotates online discussion relating to consumer products using a wide variety of state-of-the-art techniques, including crawling, wrapping, search, text classification and computational linguistics. marketing intelligence is derived through an interactive analysis framework uniquely configured to leverage the connectivity and content of annotated online discussion.
mining images on semantics via statistical learning. in this paper, we have proposed a novel framework to enable hierarchical image classification via statistical learning. by integrating the concept hierarchy for semantic image concept organization, a hierarchical mixture model is proposed to enable multi-level modeling of semantic image concepts and hierarchical classifier combination. thus, learning the classifiers for the semantic image concepts at the high level of the concept hierarchy can be effectively achieved by detecting the presences of the relevant base-level atomic image concepts. to effectively learn the base-level classifiers for the atomic image concepts at the first level of the concept hierarchy, we have proposed a novel adaptive em algorithm to achieve more effective model selection and parameter estimation. in addition, a novel penalty term is proposed to effectively eliminate the misleading effects of the outlying unlabeled images on semi-supervised classifier training. our experimental results in a specific image domain of outdoor photos are very attractive.