waashk/dblp huggingface dataset:
workload-aware anonymization. protecting data privacy is an important problem in microdata distribution. anonymization algorithms typically aim to protect individual privacy, with minimal impact on the quality of the resulting data. while the bulk of previous work has measured quality through one-size-fits-all measures, we argue that quality is best judged with respect to the workload for which the data will ultimately be used.this paper provides a suite of anonymization algorithms that produce an anonymous view based on a target class of workloads, consisting of one or more data mining tasks, as well as selection predicates. an extensive experimental evaluation indicates that this approach is often more effective than previous anonymization techniques.
simple and effective visual models for gene expression cancer diagnostics. in the paper we show that diagnostic classes in cancer gene expression data sets, which most often include thousands of features (genes), may be effectively separated with simple two-dimensional plots such as scatterplot and radviz graph. the principal innovation proposed in the paper is a method called vizrank, which is able to score and identify the best among possibly millions of candidate projections for visualizations. compared to recently much applied techniques in the field of cancer genomics that include neural networks, support vector machines and various ensemble-based approaches, vizrank is fast and finds visualization models that can be easily examined and interpreted by domain experts. our experiments on a number of gene expression data sets show that vizrank was always able to find data visualizations with a small number of (two to seven) genes and excellent class separation. in addition to providing grounds for gene expression cancer diagnosis, vizrank and its visualizations also identify small sets of relevant genes, uncover interesting gene interactions and point to outliers and potential misclassifications in cancer data sets.
sampling from large graphs. given a huge real graph, how can we derive a representative sample? there are many known algorithms to compute interesting measures (shortest paths, centrality, betweenness, etc.), but several of them become impractical for large graphs. thus graph sampling is essential.the natural questions to ask are (a) which sampling method to use, (b) how small can the sample size be, and (c) how to scale up the measurements of the sample (e.g., the diameter), to get estimates for the large graph. the deeper, underlying question is subtle: how do we measure success?.we answer the above questions, and test our answers by thorough experiments on several, diverse datasets, spanning thousands nodes and edges. we consider several sampling methods, propose novel methods to check the goodness of sampling, and develop a set of scaling laws that describe relations between the properties of the original and the sample.in addition to the theoretical contributions, the practical conclusions from our work are: sampling strategies based on edge selection do not perform well; simple uniform random node selection performs surprisingly well. overall, best performing methods are the ones based on random-walks and "forest fire"; they match very accurately both static as well as evolutionary graph patterns, with sample sizes down to about 15% of the original graph.
graphs over time: densification laws, shrinking diameters and possible explanations. how do real graphs evolve over time? what are "normal" growth patterns in social, technological, and information networks? many studies have discovered patterns in static graphs, identifying properties in a single snapshot of a large network, or in a very small number of snapshots; these include heavy tails for in- and out-degree distributions, communities, small-world phenomena, and others. however, given the lack of information about network evolution over long periods, it has been hard to convert these findings into statements about trends over time.here we study a wide range of real graphs, and we observe some surprising phenomena. first, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like o(log n) or o(log(log n)).existing graph generation models do not exhibit these types of behavior, even at a qualitative level. we provide a new graph generator, based on a "forest fire" spreading process, that has a simple, intuitive justification, requires very few parameters (like the "flammability" of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.
incremental maintenance of quotient cube for median. data cube pre-computation is an important concept for supporting olap(online analytical processing) and has been studied extensively. it is often not feasible to compute a complete data cube due to the huge storage requirement. recently proposed quotient cube addressed this issue through a partitioning method that groups cube cells into equivalence partitions. such an approach is not only useful for distributive aggregate functions such as sum but can also be applied to the holistic aggregate functions like median.maintaining a data cube for holistic aggregation is a hard problem since its difficulty lies in the fact that history tuple values must be kept in order to compute the new aggregate when tuples are inserted or deleted. the quotient cube makes the problem harder since we also need to maintain the equivalence classes. in this paper, we introduce two techniques called addset data structure and sliding window to deal with this problem. we develop efficient algorithms for maintaining a quotient cube with holistic aggregation functions that takes up reasonably small storage space. performance study shows that our algorithms are effective, efficient and scalable over large databases.
mining risk patterns in medical data. in this paper, we discuss a problem of finding risk patterns in medical data. we define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. we characterise the problem of mining risk patterns as an optimal rule discovery problem. we study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. the method has been applied to a real world data set to find patterns associated with an allergic event for ace inhibitors. the algorithm has generated some useful results for medical researchers.
very sparse random projections. there has been considerable interest in random projections, an approximate algorithm for estimating distances between pairs of points in a high-dimensional vector space. let a in rn x d be our n points in d dimensions. the method multiplies a by a random matrix r in rd x k, reducing the d dimensions down to just k for speeding up the computation. r typically consists of entries of standard normal n(0,1). it is well known that random projections preserve pairwise distances (in the expectation). achlioptas proposed sparse random projections by replacing the n(0,1) entries in r with entries in -1,0,1 with probabilities 1/6, 2/3, 1/6, achieving a threefold speedup in processing time.we recommend using r of entries in -1,0,1 with probabilities 1/2√d, 1-1√d, 1/2√d for achieving a significant √d-fold speedup, with little loss in accuracy.
clustering moving objects. due to the advances in positioning technologies, the real time information of moving objects becomes increasingly available, which has posed new challenges to the database research. as a long-standing technique to identify overall distribution patterns in data, clustering has achieved brilliant successes in analyzing static datasets. in this paper, we study the problem of clustering moving objects, which could catch interesting pattern changes during the motion process and provide better insight into the essence of the mobile data points. in order to catch the spatial-temporal regularities of moving objects and handle large amounts of data, micro-clustering [20] is employed. efficient techniques are proposed to keep the moving micro-clusters geographically small. important events such as the collisions among moving micro-clusters are also identified. in this way, high quality moving micro-clusters are dynamically maintained, which leads to fast and competitive clustering result at any given time instance. we validate our approaches with a through experimental evaluation, where orders of magnitude improvement on running time is observed over normal k-means clustering method [14].
an integrated framework on mining logs files for computing system management. traditional approaches to system management have been largely based on domain experts through a knowledge acquisition process that translates domain knowledge into operating rules and policies. this has been well known and experienced as a cumbersome, labor intensive, and error prone process. in addition, this process is difficult to keep up with the rapidly changing environments. in this paper, we will describe our research efforts on establishing an integrated framework for mining system log files for automatic management. in particular, we apply text mining techniques to categorize messages in log files into common situations, improve categorization accuracy by considering the temporal characteristics of log messages, develop temporal mining techniques to discover the relationships between different events, and utilize visualization tools to evaluate and validate the interesting temporal patterns for system management.
automated detection of frontal systems from numerical model-generated data. fronts are significant meteorological phenomena of interest. the extraction of frontal systems from observations and model data can greatly benefit many kinds of research and applications in atmospheric sciences. due to the huge amount of observational and model data available nowadays, automated extraction of front systems is necessary. this paper presents an automated method to detect frontal systems from numerical model-generated data. in this method, a frontal system is characterized by a vector of features, comprised of parameters derived from the model wind field. k-means clustering is applied to the generated sample set of the feature vectors to partition the feature space and to identify clusters representing the fronts. the probability that a model grid belongs to a front is estimated based on its feature vector. the probability image is generated corresponding to the model grids. a hierarchical thresholding technique is applied to the probability image to identify the frontal systems and a gaussian bayes classifier is trained to determine the proper threshold value. this is followed by post processing to filter out false signatures. experiment results from this method are in good agreement with the ones identified by the domain experts.
construct robust rule sets for classification. we study the problem of computing classification rule sets from relational databases so that accurate predictions can be made on test data with missing attribute values. traditional classifiers perform badly when test data are not as complete as the training data because they tailor a training database too much. we introduce the concept of one rule set being more robust than another, that is, able to make more accurate predictions on test data with missing attribute values. we show that the optimal class association rule set is as robust as the complete class association rule set. we then introduce the k-optimal rule set, which provides predictions exactly the same as the optimal class association rule set on test data with up to k missing attribute values. this leads to a hierarchy of k-optimal rule sets in which decreasing size corresponds to decreasing robustness, and they all more robust than a traditional classification rule set. we introduce two methods to find k-optimal rule sets, i.e. an optimal association rule mining approach and a heuristic approximate approach. we show experimentally that a k-optimal rule set generated by the optimal association rule mining approach performs better than that by the heuristic approximate approach and both rule sets perform significantly better than a typical classification rule set (c4.5rules) on incomplete test data.
mining heterogeneous gene expression data with time lagged recurrent neural networks. heterogeneous types of gene expressions may provide a better insight into the biological role of gene interaction with the environment, disease development and drug effect at the molecular level. in this paper for both exploring and prediction purposes a time lagged recurrent neural network with trajectory learning is proposed for identifying and classifying the gene functional patterns from the heterogeneous nonlinear time series microarray experiments. the proposed procedures identify gene functional patterns from the dynamics of a state-trajectory learned in the heterogeneous time series and the gradient information over time. also, the trajectory learning with back-propagation through time algorithm can recognize gene expression patterns vary over time. this may reveal much more information about the regulatory network underlying gene expressions. the analyzed data were extracted from spotted dna microarrays in the budding yeast expression measurements, produced by eisen et al. the gene matrix contained 79 experiments over a variety of heterogeneous experiment conditions. the number of recognized gene patterns in our study ranged from two to ten and were divided into three cases. optimal network architectures with different memory structures were selected based on akaike and bayesian information statistical criteria using two-way factorial design. the optimal model performance was compared to other popular gene classification algorithms such as nearest neighbor, support vector machine, and self-organized map. the reliability of the performance was verified with multiple iterated runs.
a robust and efficient clustering algorithm based on cohesion self-merging. data clustering has attracted a lot of research attention in the field of computational statistics and data mining. in most related studies, the dissimilarity between two clusters is defined as the distance between their centroids, or the distance between two closest (or farthest) data points. however, all of these measurements are vulnerable to outliers, and removing the outliers precisely is yet another difficult task. in view of this, we propose a new similarity measurement referred to as cohesion, to measure the inter-cluster distances. by using this new measurement of cohesion, we design a two-phase clustering algorithm, called cohesion-based self-merging (abbreviated as csm), which runs in linear time to the size of input data set. combining the features of partitional and hierarchical clustering methods, algorithm csm partitions the input data set into several small subclusters in the first phase, and then continuously merges the subclusters based on cohesion in a hierarchical manner in the second phase. as shown by our performance studies, the cohesion-based clustering is very robust and possesses the excellent tolerance to outliers in various workloads. more importantly, algorithm csm is shown to be able to cluster the data sets of arbitrary shapes very efficiently, and provide better clustering results than those by prior methods.index terms: data mining, data clustering, hierarchical clustering, partitional clustering
discovering informative content blocks from web documents. in this paper, we propose a new approach to discover informative contents from a set of tabular documents (or web pages) of a web site. our system, infodiscoverer, first partitions a page into several content blocks according to html tag <table> in a web page. based on the occurrence of the features (terms) in the set of pages, it calculates entropy value of each feature. according to the entropy value of each feature in a content block, the entropy value of the block is defined. by analyzing the information measure, we propose a method to dynamically select the entropy-threshold that partitions blocks into either informative or redundant. informative content blocks are distinguished parts of the page, whereas redundant content blocks are common parts. based on the answer set generated from 13 manually tagged news web sites with a total of 26,518 web pages, experiments show that both recall and precision rates are greater than 0.956. that is, using the approach, informative blocks (news articles) of these sites can be automatically separated from semantically redundant contents such as advertisements, banners, navigation panels, news categories, etc. by adopting infodiscoverer as the preprocessor of information retrieval and extraction applications, the retrieval and extracting precision will be increased, and the indexing size and extracting complexity will also be reduced.
visually mining and monitoring massive time series. moments before the launch of every space vehicle, engineering discipline specialists must make a critical go/no-go decision. the cost of a false positive, allowing a launch in spite of a fault, or a false negative, stopping a potentially successful launch, can be measured in the tens of millions of dollars, not including the cost in morale and other more intangible detriments. the aerospace corporation is responsible for providing engineering assessments critical to the go/no-go decision for every department of defense space vehicle. these assessments are made by constantly monitoring streaming telemetry data in the hours before launch. we will introduce viztree, a novel time-series visualization tool to aid the aerospace analysts who must make these engineering assessments. viztree was developed at the university of california, riverside and is unique in that the same tool is used for mining archival data and monitoring incoming live telemetry. the use of a single tool for both aspects of the task allows a natural and intuitive transfer of mined knowledge to the monitoring task. our visualization approach works by transforming the time series into a symbolic representation, and encoding the data in a modified suffix tree in which the frequency and other properties of patterns are mapped onto colors and other visual properties. we demonstrate the utility of our system by comparing it with state-of-the-art batch algorithms on several real and synthetic datasets.
distributed data mining in a chain store database of short transactions. in this paper, we broaden the horizon of traditional rule mining by introducing a new framework of causality rule mining in a distributed chain store database. specifically, the causality rule explored in this paper consists of a sequence of triggering events and a set of consequential events, and is designed with the capability of mining non-sequential, inter-transaction information. hence, the causality rule mining provides a very general framework for rule derivation. note, however, that the procedure of causality rule mining is very costly particularly in the presence of a huge number of candidate sets and a distributed database, and in our opinion, cannot be dealt with by direct extensions from existing rule mining methods. consequently, we devise in this paper a series of level matching algorithms, including level matching (abbreviatedly as lm), level matching with selective scan (abbreviatedly as lms), and distributed level matching (abbreviatedly as distibuted lm), to minimize the computing cost needed for the distributed data mining of causality rules. in addition, the phenomena of time window constraints are also taken into consideration for the development of our algorithms. as a result of properly employing the technologies of level matching and selective scan, the proposed algorithms present good efficiency and scalability in the mining of local and global causality rules. scale-up experiments show that the proposed algorithms scale well with the number of sites and the number of customer transactions.index terms: knowledge discovery, distributed data mining causality rules, triggering events, consequential events
induction of semantic classes from natural language text. many applications dealing with textual information require classification of words into semantic classes (or concepts). however, manually constructing semantic classes is a tedious task. in this paper, we present an algorithm, unicon, for unsupervised induction of concepts. some advantages of unicon over previous approaches include the ability to classify words with low frequency counts, the ability to cluster a large number of elements in a high-dimensional space, and the ability to classify previously unknown words into existing clusters. furthermore, since the algorithm is unsupervised, a set of concepts may be constructed for any corpus.
dirt @sbt@discovery of inference rules from text. in this paper, we propose an unsupervised method for discovering inference rules from text, such as "x is author of y &ap; x wrote y", "x solved y &ap; x found a solution to y", and "x caused y &ap; y is triggered by x". inference rules are extremely important in many fields such as natural language processing, information retrieval, and artificial intelligence in general. our algorithm is based on an extended version of harris' distributional hypothesis, which states that words that occurred in the same contexts tend to be similar. instead of using this hypothesis on words, we apply it to paths in the dependency trees of a parsed corpus.
maximum profit mining and its application in software development. while most software defects (i.e., bugs) are corrected and tested as part of the lengthy software development cycle, enterprise software vendors often have to release software products before all reported defects are corrected, due to deadlines and limited resources. a small number of these defects will be escalated by customers and they must be resolved immediately by the software vendors at a very high cost. in this paper, we develop an escalation prediction (ep) system that mines historic defect report data and predict the escalation risk of the defects for maximum net profit. more specifically, we first describe a simple and general framework to convert the maximum net profit problem to cost-sensitive learning. we then apply and compare several well-known cost-sensitive learning approaches for ep. our experiments suggest that the cost-sensitive decision tree is the best method for producing the highest positive net profit and comprehensible results. the ep system has been deployed successfully in the product group of an enterprise software vendor.