waashk/dblp huggingface dataset:
density-based clustering of uncertain data. in many different application areas, e.g. sensor databases, location based services or face recognition systems, distances between odjects have to be computed based on vague and uncertain data. commonly, the distances between these uncertain object descriptions are expressed by one numerical distance value. based on such single-valued distance functions standard data mining algorithms can work without any changes. in this paper, we propose to express the similarity between two fuzzy objects by distance probability functions. these fuzzy distance functions assign a probability value to each possible distance value. by integrating these fuzzy distance functions directly into data mining algorithms, the full information provided by these functions is exploited. in order to demonstrate the benefits of this general approach, we enhance the density-based clustering algorithm dbscan so that it can work directly on these fuzzy distance functions. in a detailed experimental evaluation based on artificial and real-world data sets, we show the characteristics and benefits of our new approach.
a parallel learning algorithm for text classification. text classification is the process of classifying documents into predefined categories based on their content. existing supervised learning algorithms to automatically classify text need sufficient labeled documents to learn accurately. applying the expectation-maximization (em) algorithm to this problem is an alternative approach that utilizes a large pool of unlabeled documents to augment the available labeled documents. unfortunately, the time needed to learn with these large unlabeled documents is too high. this paper introduces a novel parallel learning algorithm for text classification task. the parallel algorithm is based on the combination of the em algorithm and the naive bayes classifier. our goal is to improve the computational time in learning and classifying process. we studied the performance of our parallel algorithm on a large linux pc cluster called pirun cluster. we report both timing and accuracy results. these results indicate that the proposed parallel algorithm is capable of handling large document collections.
a multiple tree algorithm for the efficient association of asteroid observations. in this paper we examine the problem of efficiently finding sets of observations that conform to a given underlying motion model. while this problem is often phrased as a tracking problem, where it is called track initiation, it is useful in a variety of tasks where we want to find correspondences or patterns in spatial-temporal data. unfortunately, this problem often suffers from a combinatorial explosion in the number of potential sets that must be evaluated. we consider the problem with respect to large-scale asteroid observation data, where the goal is to find associations among the observations that correspond to the same underlying asteroid. in this domain, it is vital that we can efficiently extract the underlying associations.we introduce a new methodology for track initiation that exhaustively considers all possible linkages. we then introduce an exact tree-based algorithm for tractably finding all compatible sets of points. further, we extend this approach to use multiple trees, exploiting structure from several time steps at once. we compare this approach to a standard sequential approach and show how the use of multiple trees can provide a significant benefit.
a graph-theoretic approach to extract storylines from search results. we present a graph-theoretic approach to discover storylines from search results. storylines are windows that offer glimpses into interesting themes latent among the top search results for a query; they are different from, and complementary to, clusters obtained through traditional approaches. our framework is axiomatically developed and combinatorial in nature, based on generalizations of the maximum induced matching problem on bipartite graphs. the core algorithmic task involved is to mine for signature structures in a robust graph representation of the search results. we present a very fast algorithm for this task based on local search. experiments show that the collection of storylines extracted through our algorithm offers a concise organization of the wealth of information hidden beyond the first page of search results.
structure and evolution of online social networks. in this paper, we consider the evolution of structure within large online social networks. we present a series of measurements of two such networks, together comprising in excess of five million people and ten million friendship links, annotated with metadata capturing the time of every event in the life of the network. our measurements expose a surprising segmentation of these networks into three regions: singletons who do not participate in the network; isolated communities which overwhelmingly display star structure; and a giant component anchored by a well-connected core region which persists even in the absence of stars.we present a simple model of network growth which captures these aspects of component structure. the model follows our experimental results, characterizing users as either passive members of the network; inviters who encourage offline friends and acquaintances to migrate online; and linkers who fully participate in the social evolution of the network.
hierarchical topic segmentation of websites. in this paper, we consider the problem of identifying and segmenting topically cohesive regions in the url tree of a large website. each page of the website is assumed to have a topic label or a distribution on topic labels generated using a standard classifier. we develop a set of cost measures characterizing the benefit accrued by introducing a segmentation of the site based on the topic labels. we propose a general framework to use these measures for describing the quality of a segmentation; we also provide an efficient algorithm to find the best segmentation in this framework. extensive experiments on human-labeled data confirm the soundness of our framework and suggest that a judicious choice of cost measures allows the algorithm to perform surprisingly accurate topical segmentations.
clustering seasonality patterns in the presence of errors. clustering is a very well studied problem that attempts to group similar data points. most traditional clustering algorithms assume that the data is provided without measurement error. often, however, real world data sets have such errors and one can obtain estimates of these errors. we present a clustering method that incorporates information contained in these error estimates. we present a new distance function that is based on the distribution of errors in data. using a gaussian model for errors, the distance function follows a chi-square distribution and is easy to compute. this distance function is used in hierarchical clustering to discover meaningful clusters. the distance function is scale-invariant so that clustering results are independent of units of measuring data. in the special case when the error distribution is the same for each attribute of data points, the rank order of pair-wise distances is the same for our distance function and the euclidean distance function. the clustering method is applied to the seasonality estimation problem and experimental results are presented for the retail industry data as well as for simulated data, where it outperforms classical clustering methods.
algorithms for storytelling. we formulate a new data mining problem called storytelling as a generalization of redescription mining. in traditional redescription mining, we are given a set of objects and a collection of subsets defined over these objects. the goal is to view the set system as a vocabulary and identify two expressions in this vocabulary that induce the same set of objects. storytelling, on the other hand, aims to explicitly relate object sets that are disjoint (and hence, maximally dissimilar) by finding a chain of (approximate) redescriptions between the sets. this problem finds applications in bioinformatics, for instance, where the biologist is trying to relate a set of genes expressed in one experiment to another set, implicated in a different pathway. we outline an efficient storytelling implementation that embeds the cartwheels redescription mining algorithm in an a* search procedure, using the former to supply next move operators on search branches to the latter. this approach is practical and effective for mining large datasets and, at the same time, exploits the structure of partitions imposed by the given vocabulary. three application case studies are presented: a study of word overlaps in large english dictionaries, exploring connections between genesets in a bioinformatics dataset, and relating publications in the pubmed index of abstracts.
learning spatially variant dissimilarity (svad) measures. clustering algorithms typically operate on a feature vector representation of the data and find clusters that are compact with respect to an assumed (dis)similarity measure between the data points in feature space. this makes the type of clusters identified highly dependent on the assumed similarity measure. building on recent work in this area, we formally define a class of spatially varying dissimilarity measures and propose algorithms to learn the dissimilarity measure automatically from the data. the idea is to identify clusters that are compact with respect to the unknown spatially varying dissimilarity measure. our experiments show that the proposed algorithms are more stable and achieve better accuracy on various textual data sets when compared with similar algorithms proposed in the literature.
mining a stream of transactions for customer patterns. transaction data can arrive at a ferocious rate in the order that transactions are completed. the data contain an enormous amount of information about customers, not just transactions, but extracting up-to-date customer information from an ever changing stream of data and mining it in real-time is a challenge. this paper describes a statistically principled approach to designing short, accurate summaries or signatures of high dimensional customer behavior that can be kept current with a stream of transactions. a signature database can then be used for data mining and to provide approximate answers to many kinds of queries about current customers quickly and accurately, as an empirical study of the calling patterns of 96,000 wireless customers who made about 18 million wireless calls over a three month period shows.
combining partitions by probabilistic label aggregation. data clustering represents an important tool in exploratory data analysis. the lack of objective criteria render model selection as well as the identification of robust solutions particularly difficult. the use of a stability assessment and the combination of multiple clustering solutions represents an important ingredient to achieve the goal of finding useful partitions. in this work, we propose a novel way of combining multiple clustering solutions for both, hard and soft partitions: the approach is based on modeling the probability that two objects are grouped together. an efficient em optimization strategy is employed in order to estimate the model parameters. our proposal can also be extended in order to emphasize the signal more strongly by weighting individual base clustering solutions according to their consistency with the prediction for previously unseen objects. in addition to that, the probabilistic model supports an out-of-sample extension that (i) makes it possible to assign previously unseen objects to classes of the combined solution and (ii) renders the efficient aggregation of solutions possible. in this work, we also shed some light on the usefulness of such combination approaches. in the experimental result section, we demonstrate the competitive performance of our proposal in comparison with other recently proposed methods for combining multiple classifications of a finite data set.
the data mining approach to automated software testing. in today's industry, the design of software tests is mostly based on the testers' expertise, while test automation tools are limited to execution of pre-planned tests only. evaluation of test outputs is also associated with a considerable effort by human testers who often have imperfect knowledge of the requirements specification. not surprisingly, this manual approach to software testing results in heavy losses to the world's economy. the costs of the so-called "catastrophic" software failures (such as mars polar lander shutdown in 1999) are even hard to measure. in this paper, we demonstrate the potential use of data mining algorithms for automated induction of functional requirements from execution data. the induced data mining models of tested software can be utilized for recovering missing and incomplete specifications, designing a minimal set of regression tests, and evaluating the correctness of software outputs when testing new, potentially flawed releases of the system. to study the feasibility of the proposed approach, we have applied a novel data mining algorithm called info-fuzzy network (ifn) to execution data of a general-purpose code for solving partial differential equations. after being trained on a relatively small number of randomly generated input-output examples, the model constructed by the ifn algorithm has shown a clear capability to discriminate between correct and faulty versions of the program.
new em derived from kullback-leibler divergence. we introduce a new em framework in which it is possible not only to optimize the model parameters but also the number of model components. a key feature of our approach is that we use nonparametric density estimation to improve parametric density estimation in the em framework. while the classical em algorithm estimates model parameters empirically using the data points themselves, we estimate them using nonparametric density estimates.there exist many possible applications that require optimal adjustment of model components. we present experimental results in two domains. one is polygonal approximation of laser range data, which is an active research topic in robot navigation. the other is grouping of edge pixels to contour boundaries, which still belongs to unsolved problems in computer vision.
similarity analysis on government regulations. government regulations are semi-structured text documents that are often voluminous, heavily cross-referenced between provisions and even ambiguous. multiple sources of regulations lead to difficulties in both understanding and complying with all applicable codes. in this work, we propose a framework for regulation management and similarity analysis. an online repository for legal documents is created with the help of text mining tool, and users can access regulatory documents either through the natural hierarchy of provisions or from a taxonomy generated by knowledge engineers based on concepts. our similarity analysis core identifies relevant provisions and brings them to the user's attention, and this is performed by utilizing both the hierarchical and referential structures of regulations to provide a better comparison between provisions. preliminary results show that our system reveals hidden similarities that are not apparent between provisions based on node content comparisons.
cryptographically private support vector machines. we propose private protocols implementing the kernel adatron and kernel perceptron learning algorithms, give private classification protocols and private polynomial kernel computation protocols. the new protocols return their outputs - either the kernel value, the classifier or the classifications - in encrypted form so that they can be decrypted only by a common agreement by the protocol participants. we show how to use the encrypted classifications to privately estimate many properties of the data and the classifier. the new svm classifiers are the first to be proven private according to the standard cryptographic definitions.
bias and controversy: beyond the statistical deviation. in this paper, we investigate how deviation in evaluation activities may reveal bias on the part of reviewers and controversy on the part of evaluated objects. we focus on a 'data-centric approach' where the evaluation data is assumed to represent the 'ground truth'. the standard statistical approaches take evaluation and deviation at face value. we argue that attention should be paid to the subjectivity of evaluation, judging the evaluation score not just on 'what is being said' (deviation), but also on 'who says it' (reviewer) as well as on 'whom it is said about' (object). furthermore, we observe that bias and controversy are mutually dependent, as there is more bias if there is higher deviation on a less controversial object. to address this mutual dependency, we propose a reinforcement model to identify bias and controversy. we test our model on real-life data to verify its applicability.
passenger-based predictive modeling of airline no-show rates. airlines routinely overbook flights based on the expectation that some fraction of booked passengers will not show for each flight. accurate forecasts of the expected number of no-shows for each flight can increase airline revenue by reducing the number of spoiled seats (empty seats that might otherwise have been sold) and the number of involuntary denied boardings at the departure gate. conventional no-show forecasting methods typically average the no-show rates of historically similar flights, without the use of passenger-specific information.we develop two classes of models to predict cabin-level no-show rates using specific information on the individual passengers booked on each flight. the first of these models computes the no-show probability for each passenger, using both the cabin-level historical forecast and the extracted passenger features as explanatory variables. this passenger-level model is implemented using three different predictive methods: a c4.5 decision-tree, a segmented naive bayes algorithm, and a new aggregation method for an ensemble of probabilistic models. the second cabin-level model is formulated using the desired cabin-level no-show rate as the response variable. inputs to this model include the predicted cabin-level no-show rates derived from the various passenger-level models, as well as simple statistics of the features of the cabin passenger population. the cabin-level model is implemented using either linear regression, or as a direct probability model with explicit incorporation of the cabin-level no-show rates derived from the passenger-level model outputs.the new passenger-based models are compared to a conventional historical model, using train and evaluation data sets taken from over 1 million passenger name records. standard metrics such as lift curves and mean-square cabin-level errors establish the improved accuracy of the passenger-based models over the historical model. all models are also evaluated using a simple revenue model, and it is shown that the cabin-level passenger-based model can produce between 0.4% and 3.2% revenue gain over the conventional model, depending on the revenue-model parameters.
feature bagging for outlier detection. outlier detection has recently become an important problem in many industrial and financial applications. in this paper, a novel feature bagging approach for detecting outliers in very large, high dimensional and noisy databases is proposed. it combines results from multiple outlier detection algorithms that are applied using different set of features. every outlier detection algorithm uses a small subset of features that are randomly selected from the original feature set. as a result, each outlier detector identifies different outliers, and thus assigns to all data records outlier scores that correspond to their probability of being outliers. the outlier scores computed by the individual outlier detection algorithms are then combined in order to find the better quality outliers. experiments performed on several synthetic and real life data sets show that the proposed methods for combining outputs from multiple outlier detection algorithms provide non-trivial improvements over the base algorithm.
effective localized regression for damage detection in large complex mechanical structures. in this paper, we propose a novel data mining technique for the efficient damage detection within the large-scale complex mechanical structures. every mechanical structure is defined by the set of finite elements that are called structure elements. large-scale complex structures may have extremely large number of structure elements, and predicting the failure in every single element using the original set of natural frequencies as features is exceptionally time-consuming task. traditional data mining techniques simply predict failure in each structure element individually using global prediction models that are built considering all data records. in order to reduce the time complexity of these models, we propose a localized clustering-regression based approach that consists of two phases: (1) building a local cluster around a data record of interest and (2) predicting an intensity of damage only in those structure elements that correspond to data records from the built cluster. for each test data record, we first build a cluster of data records from training data around it. then, for each data record that belongs to discovered cluster, we identify corresponding structure elements and we build a localized regression model for each of these structure elements. these regression models for specific structure elements are constructed using only a specific set of relevant natural frequencies and merely those data records that correspond to the failure of that structure element. experiments performed on the problem of damage prediction in a large electric transmission tower frame indicate that the proposed localized clustering-regression based approach is significantly more accurate and more computationally efficient than our previous hierarchical clustering approach, as well as global prediction models.
the distributed boosting algorithm. in this paper, we propose a general framework for distributed boosting intended for efficient integrating specialized classifiers learned over very large and distributed homogeneous databases that cannot be merged at a single location. our distributed boosting algorithm can also be used as a parallel classification technique, where a massive database that cannot fit into main computer memory is partitioned into disjoint subsets for a more efficient analysis. in the proposed method, at each boosting round the classifiers are first learned from disjoint datasets and then exchanged amongst the sites. finally the classifiers are combined into a weighted voting ensemble on each disjoint data set. the ensemble that is applied to an unseen test set represents an ensemble of ensembles built on all distributed sites. in experiments performed on four large data sets the proposed distributed boosting method achieved classification accuracy comparable or even slightly better than the standard boosting algorithm while requiring less memory and less computational time. in addition, the communication overhead of the distributed boosting algorithm is very small making it a viable alternative to the standard boosting for large-scale databases.