waashk/dblp huggingface dataset:
privacy preserving data classification with rotation perturbation. data perturbation techniques are one of the most popular models for privacy preserving data mining [3, 1]. it is especially convenient for applications where the data owners need to export/publish the privacy-sensitive data. a data perturbation procedure can be simply described as follows. before the data owner publishes the data, they randomly change the data in certain way to disguise the sensitive information while preserving the particular data property that is critical for building the data models. several perturbation techniques have been proposed recently, among which the most typical ones are randomization approach [3] and condensation approach [1].
the anatomy of a hierarchical clustering engine for web-page, news and book snippets. in this paper, we investigate the web snippet hierarchical clustering problem in its full extent by devising an algorithmic solution, and a software prototype called snaket (accessible at http://roquefort.di.unipi.it/), that: (1) draws the snippets from 16 web search engines, the amazon collection of books a9.com, the news of google news and the blogs of blogline; (2) builds the clusters on-the-fly (ephemeral clustering) in response to a user query without adopting any pre-defined organization in categories; (3) labels the clusters with sentences of variable length, drawn from the snippets and possibly missing some terms, provided they are not too many;
association rules enhanced classification of underwater acoustic signal. classification of underwater acoustic signal is one ofthe important fields of pattern recognition. inspired bythe experience of training man experts in sonar, wepropose a two-phase training algorithm to exploit theassociation rules to reveal the understandable intrinsicrules contributing to correct classification in the knownmisclassification datasets in this paper. preliminaryexperimental results demonstrate the potential ofclassification association rules to enhance the accuracyof classification of underwater acoustic signals.
communication efficient construction of decision trees over heterogeneously distributed data. we present an algorithm designed to efficiently construct a decision tree over heterogeneously distributed data without centralizing. we compare our algorithm against a standard centralized decision tree implementation in terms of accuracy as well as the communication complexity. our experimental results show that by using only 20% of the communication cost necessary to centralize the data we can achieve trees with accuracy at least 80% of the trees produced by the centralized version.
fast frequent string mining using suffix arrays. we present a method to mine strings that are frequent in one database and infrequent in another. the method uses suffix- and lcp-arrays that can be computed extremely fast and space efficiently, and further exhibit a good locality behavior. experiments with several biologically relevant data sets show that our approach outperforms existing methods in terms of time and space.
a synchronization based algorithm for discovering ellipsoidal clusters in large datasets. this paper introduces a new scalable approach to clusteringbased on synchronization of pulse-coupled oscillators. eachdata point is represented by an integrate-and-fire oscillator, and the interaction between oscillators is defined according to the relative similarity between the points. the set of oscillators will self-organize into stable phase-locked subgroups. our approach proceeds by loading only a subset of the data and allowing it to self-organize. groups ofsynchronized oscillators are then summarized and purged from memory. we show that our method is robust, scales linearly, and can determine the number of clusters. the proposedapproach is empirically evaluated with several synthetic data sets and is used to segment large color images.
privacy-preserving frequent pattern mining across private databases. privacy consideration has much significance in the application of data mining. it is very important that the privacy of individual parties will not be exposed when data mining techniques are applied to a large collection of data about the parties. in many scenarios such as data warehousing or data integration, data from the different parties form a many-to-many schema. this paper addresses the problem of privacy-preserving frequent pattern mining in such a schema across two dimension sites. we assume that sites are not trusted and they are semi-honest. our method is based on the concept of semi-join and does not involve data encryption which is used in most previous work. experiments are conducted to study the efficiency of the proposed models.
functional trees for classification. the design of algorithms that explore multiple representation languages and explore different search space has an intuitive appeal.in this context of classification problems, algorithmsthat generate multivariate trees are able to explore multiplerepresentation languages by using decision test based on acombination of attributes.the same applies to models threesalgorithms, in regression domains, but using linear models atleaf nodes.in this paper we study where to use combinations of attributes in decision tree learning.we present an algorithm for multivariate tree learning that combines a univariate decision tree with a discriminant function by means of constructiveinduction.this algorithm is able to use decision nodes with multivariate tests, and leaf nodes that predict a class using adiscrimnant. multivariate decision nodes are built when growing the tree, while functional leaves are built when pruning the tree.functional trees can be seen as a generalization of multivariate trees.our algorithm was compared against to its components and two simplified versions using 30 benchmark datasets. the experimental evaluation shows that our algorithm has clear advantages with respect to the generalization ability and model sizes at statistically significant.
cole: a cooperative data mining approach and its application to early diabetes detection. we present cole, a cooperative data mining approach for discovering hybrid knowledge. it employs multiple different data mining algorithms, and combines results from them to enhance the mined knowledge. for our medical application area, we analyse several focusing strategies that allowed us to gain medically significant results.
feature selection for building cost-effective data stream classifiers. a stream classifier is a decision model that assigns a class label to a data stream, based on its arriving data. various features of the stream can be used in the classifier, each of which may have different relevance to the classification task and different cost in obtaining its value. as time passes by, some less costly features may become more relevant, but the time needed for decision may be considered as a cost. a challenge is how to balance the different costs when building a cost-effective classifier. this paper proposes a new feature selection strategy that extends the traditional relief algorithm in two aspects: (1) estimate the classification cost associated with each feature, and (2) order all the features with a score that combines both cost estimation and classification relevance. a classifier is then built with the selected features using a traditional classification method. experimental results show that classifiers constructed with this strategy are indeed cost effective.
mining generalized association rules for sequential and path data. while association rules for set data se and describe relations between parts of set valued objects completely, association rules for sequential data are restricted by specific interpretations of the subsequence relation: contiguous subsequences describe localfeatures of a sequence valued object, noncontiguous subsequences its global features. we model both types of features with generalized subsequences that describe local deviations by wildcards, and present a new algorithm of apriori type for mining all generalized subsequences with prescribed minim m support from a given database of sequences. furthermore we show that the givenalgorithm automatically takes into account an eventually underlying graph structure, i.e., is applicable to path data also.
a tight upper bound on the number of candidate patterns. in the context of mining for frequent patterns using the standard level wise algorithm, the following question arises: given the current level and the current set of frequentpatterns, what is the maximal number of candidate patterns that can be generated on the next level? we answer this question by providing a tight upper bound, derived from a combinatorial result from the sixties by kruskal andkatona. our result is useful to educe the number of databasescans.
esrs: a case selection algorithm using extended similarity-based rough sets. a case selection algorithm selects representative casesfrom a large data set for future case-based reasoningtasks. this paper proposes the esrs algorithm, based onextended similarity-based rough set theory, which selectsa reasonable number of the representative cases whilemaintaining satisfactory classification accuracy. it alsocan handle noise and inconsistent data. experimentalresults on synthetic and real sets of cases showed that itspredictive accuracy is similar to that of well-knownmachine learning systems on standard data sets, while ithas the advantage of being applicable to any data setwhere a similarity function can be defined.
a scalable collaborative filtering framework based on co-clustering. collaborative filtering-based recommender systems have become extremely popular in recent years due to the increase in web-based activities such as e-commerce and online content distribution. current collaborative filtering (cf) techniques such as correlation and svd based methods provide good accuracy, but are computationally expensive and can be deployed only in static off-line settings. however, a number of practical scenarios require dynamic real-time collaborative filtering that can allow new users, items and ratings to enter the system at a rapid rate. in this paper, we consider a novel cf approach based on a recently proposed weighted co-clustering algorithm [1] that involves simultaneous clustering of users and items. we design incremental and parallel versions of the co-clustering algorithm and use it to build an efficient real-time cf framework. empirical evaluation demonstrates that our approach provides an accuracy comparable to that of the correlation and matrix factorization based approaches at a much lower computational cost.
a machine learning approach to improve congestion control over wireless computer networks. in this paper, we present the application of machine learning techniques to the improvement of the congestion control of tcp in wired/wireless networks. tcp is sub-optimal in hybrid wired/wireless networks because it reacts in the same way to losses due to congestion and losses due to link errors. we thus propose to use machine learning techniques to build automatically a loss classifier from a database obtained by simulations of random network topologies. several machine learning algorithms are compared for this task and the best method for this application turns out to be decision tree boosting. it outperforms ad hoc classifiers proposed in the networking literature.
combining labeled and unlabeled data for text classification with a large number of categories. we develop a framework to incorporate unlabeled data in the error-correcting output coding (ecoc)setup by decomposing multiclass problems into multiple binary problems and then use co-training to learn the individual binary classification problems. we show that our method isespecially useful for classification tasks involving a large number of categories where co-training doesn't perform very well by itself and when combined with ecoc, outperforms several other algorithms that combine labeled and unlabeled data for text classification in terms of accuracy, precision-recall tradeoff, and efficiency.
using text mining to infer semantic attributes for retail data mining. current data mining techniques usually do not have amechanism to automatically infer semantic features inherentin the data being "mined". the semantics are eitherinjected in the initial stages (by feature construction) or byinterpreting the results produced by the algorithms. bothof these techniques have proved effective but require a lotof human effort. in many domains, semantic informationis implicitly available and can be extracted automaticallyto improve data mining systems. in this paper, we present acase study of a system that is trained to extract semantic featuresfor apparel products and populate a knowledge basewith these products and features. we show that semanticfeatures of these items can be successfully extracted by applyingtext learning techniques to the descriptions obtainedfrom websites of retailers. we also describe several applicationsof such a knowledge base of product semantics that wehave built including recommender systems and competitiveintelligence tools and provide evidence that our approachcan successfully build a knowledge base with accurate factswhich can then be used to create profiles of individual customers,groups of customers, or entire retail stores.
loaded: link-based outlier and anomaly detection in evolving data sets. in this paper, we present loaded, an algorithm for outlier detection in evolving data sets containing both continuous and categorical attributes. loaded is a tunable algorithm, wherein one can trade off computation for accuracy so that domain-specific response times are achieved. experimental results show that loaded provides very good detection and false positive rates, which are several times better than those of existing distance-based schemes.
an algorithm for in-core frequent itemset mining on streaming data. frequent itemset mining is a core data mining operation and has been extensively studied over the last decade. this paper takes a new approach for this problem and makes two major contributions. first, we present a one pass algorithm for frequent itemset mining, which has deterministic bounds on the accuracy, and does not require any out-of-core summary structure. second, because our one pass algorithm does not produce any false negatives, it can be easily extended to a two pass accurate algorithm. our two pass algorithm is very memory efficient, and allows mining of datasets with large number of distinct items and/or very low support levels. our detailed experimental evaluation on synthetic and real datasets shows the following. first, our one pass algorithm is very accurate in practice. second, our algorithm requires significantly lower memory than manku and motwani's one pass algorithm and the multi-pass apriori algorithm. our two pass algorithm outperforms apriori and fp-tree when the number of distinct items is large and/or support levels are very low. in other cases, it is quite competitive, with possible exception of cases where the average length of frequent itemsets is quite high.
dependency derivation in industrial process data. in many industrial processes, finding dependencies and the creation of dependency graphs can increase the understanding of the system significantly. this knowledge can then be used for further optimization and variable selection. most of the measured attributes in these cases come in the form of time series. there are several ways of determining correlation between series, most of them suffering from specific problems when applied to real-world data. here, awell performing measure based on the mutual information rate is derived and discussed with results from both synthetic and real data.
scalable model-based clustering by working on data summaries. the scalability problem in data mining involves the developmentof methods for handling large databases withlimited computational resources. in this paper, we presenta two-phase scalable model-based clustering framework:first, a large data set is summed up into sub-clusters; then,clusters are directly generated from the summary statisticsof sub-clusters by a specifically designed expectation-maximization(em) algorithm. taking example for gaussianmixture models, we establish a provably convergentem algorithm, emads, which embodies cardinality, mean,and covariance information of each sub-cluster explicitly.combining with different data summarization procedures,emads is used to construct two clustering systems:gemads and bemads. the experimental results demonstratethat they run several orders of magnitude faster thanthe classic em algorithm with little loss of accuracy. theygenerate significantly better results than other model-basedclustering systems using similar computational resources.
svd based term suggestion and ranking system. in this paper, we consider the application of the singular value decomposition (svd) to a search term suggestion system in a pay-for-performance search market. we propose a novel positive and negative refinement method based on orthogonal subspace projections. we demonstrate that svd subspace-based methods: 1) expand coverage by reordering the results, and 2) enhance the clustered structure of the data. the numerical experiments reported in this paper were performed on overture's pay-per-performance search market data.
on evaluating performance of classifiers for rare classes. predicting rare classes effectively is an important problem.the definition of effective classifier, embodied in theclassifier evaluation metric, is however very subjective, dependenton the application domain. in this paper, a widevariety of point-metrics are put into a common analyticalcontext defined by the recall and precision of the target rareclass. this enables us to compare various metrics in an objective,domain-independent manner. we judge their suitabilityfor the rare class problems along the dimensions oflearning difficulty and levels of rarity. this yields manyvaluable insights. in order to address the goal of achievingbetter recall and precision, we also propose a way ofcomparing classifiers directly based on the relationships betweenrecall and precision values. it resorts to a compositepoint-metric only when recall-precision based comparisonsyield conflicting results.
text classification with evolving label-sets. we introduce the evolving label-set problem encountered in building real-world text classification systems. this problem arises when a text classification system trained on a label-set encounters documents of unseen classes at deployment time. we design a class-detector module that monitors unlabeled data, detects new classes, and suggests them to the administrator for inclusion in the label-set. we propose abstractions that group together tokens under human understandable concepts and provide a mechanism of assigning importance to unseen terms. we present generative algorithms leveraging the notion of support of documents in a model for (1) selecting documents of proposed new classes, and (2) automatically triggering detection of new classes. experiments on three real world taxonomies show that our methods select new class documents with high precision, and trigger emergence of new classes with low false-positive and false-negative rates.
evaluating boosting algorithms to classify rare classes: comparison and improvements. classification of rare vents has many important data mining applications. boosting is a promising meta-techniquethat improves the classification performance of any weak classifier. so far, no systematic study has been conducted to evaluate how boosting performs for the task of mining rare classes. in this paper, we evaluate three existing categories of boosting algorithms from the single viewpoint of how they update the example weights in eachiteration, and discuss their possible effect on recall andprecision of the rare class. we propose enhanced algorithms in two of the categories, and justify their choice of weightupdating parameters theoretically. using some specially designed synthetic datasets, we compare the capability of all the algorithms from the rare class perspective. theresults support our qualitative analysis, and also indicate that our enhancements bring an extra capability for achieving better balance between recall and precision in mining rareclasses.
non-redundant data clustering. data clustering is a popular approach for automatically finding classes, concepts, or groups of patterns. in practice this discovery process should avoid redundancies with existing knowledge about class structures or groupings, and reveal novel, previously unknown aspects of the data. in order to deal with this problem, we present an extension of the information bottleneck framework, called coordinated conditional information bottleneck, which takes negative relevance information into account by maximizing a conditional mutual information score subject to constraints. algorithmically, one can apply an alternating optimization scheme that can be used in conjunction with different types of numeric and non-numeric attributes. we present experimental results for applications in text mining and computer vision.
a formal model for user preference. personalization and recommendation systems requireformalized model for user preference. this paper presentsthe formal model of preference including positivepreference and negative preference. for rare events, weapply the probability of random occurrence in order toreduce noise effects caused by data sparseness. paretodistribution is adopted for the random occurrenceprobability. we also present the method for combininginformation of joint feature variables in different sizes bydynamic weighting using random occurrence probability.
fast and exact out-of-core k-means clustering. clustering has been one of the most widely studied topics in data mining and k-means clustering has been one of the popular clustering algorithms. k-means requires several passes on the entire dataset, which can make it very expensive for large disk-resident datasets. in view of this, a lot of work has been done on various approximate versions of k-means, which require only one or a small number of passes on the entire dataset. in this paper, we present a new algorithm which typically requires only one or a small numberof passes on the entire dataset, and provably produces the same cluster centers as reported by the original k-means algorithm. the algorithm uses sampling to create initial cluster centers, and then takes one or more passes over the entire dataset to adjust these cluster centers. we provide theoretical analysis to show that the cluster centers thus reported are the same as the ones computed by the original k-means algorithm. experimental results from a number of real and synthetic datasets show speedup between a factor of 2 and 4.5, as compared to k-means.
an agglomerative hierarchical clustering using partial maximum array and incremental similarity computation method. as the tractable amount of data is growing in computer science area, fast clustering algorithm is being required because traditional clustering algorithms are not so feasible for very large and high dimensional data. many studies have been reported for clustering of large database, but most of them circumvent this problem by using the approximation method to result in thedeterioration of accuracy. in this paper, we propose a new clustering algorithm by means of partial maximum array, which can realize the agglomerative hierarchical clustering with the same accuracy to the brute-force algorithm and has o(n 2 ) time complexity. and we alsopresent the incremental method of similarity computation which substitutes the scalar calculation for the time-consuming calculation of vector similarity. the experimental results show that clustering becomes significantly fast for large and high dimensional data.