waashk/dblp huggingface dataset:
a novel method for detecting outlying subspaces in high-dimensional databases using genetic algorithm. detecting outlying subspaces is a relatively new research problem in outlier-ness analysis for high-dimensional data. an outlying subspace for a given data point p is the subspace in which p is an outlier. outlying subspace detection can facilitate a better characterization process for the detected outliers. it can also enable outlier mining for highdimensional data to be performed more accurately and efficiently. in this paper, we proposed a new method using genetic algorithm paradigm for searching outlying subspaces efficiently. we developed a technique for efficiently computing the lower and upper bounds of the distance between a given point and its kth nearest neighbor in each possible subspace. these bounds are used to speed up the fitness evaluation of the designed genetic algorithm for outlying subspace detection. we also proposed a random sampling technique to further reduce the computation of the genetic algorithm. the optimal number of sampling data is specified to ensure the accuracy of the result. we show that the proposed method is efficient and effective in handling outlying subspace detection problem by a set of experiments conducted on both synthetic and real-life datasets.
query-sensitive similarity measure for content-based image retrieval. similarity measure is one of the keys of a high-performance content-based image retrieval (cbir) system. given a pair of images, existing similarity measures usually produce a static and constant similarity score. however, an image can usually be perceived with different meanings and therefore, the similarity between the same pair of images may change when the concept being queried changes. this paper proposes a query-sensitive similarity measure, qsim, which takes the concept being queried into account in measuring image similarities, by exploiting the query image as well as the images labeled by user in the relevance feedback process. experimental comparisons to state-of-the-art techniques show that qsim has superior performance.
forecasting skewed biased stochastic ozone days: analyses and solutions. much work on skewed, stochastic, high dimensional, and biased datasets usually implicitly solve each problem separately. recently, we have been approached by texas commission on environmental quality (tceq) to help them build highly accurate ozone level alarm forecasting models for the houston area, where these technical difficulties come together in one single problem. key characteristics of this problem that are challenging and interesting include: 1) the dataset is sparse (72 features, and 2% or 5% positives depending on the criteria of "ozone days"), 2) evolving over time from year to year, 3) limited in collected data size (7 years or around 2500 data entries), 4) contains a large number of irrelevant features, 5) is biased in terms of "sample selection bias", and 6) the true model is stochastic as a function of measurable factors. besides solving a difficult application problem, this dataset offers a unique opportunity to explore new and existing data mining techniques, and to provide experience and guidance for similar problems. our main technical focus addresses on how to estimate reliable probability given both sample selection bias and a large number of irrelevant features, and how to choose the most reliable decision threshold to predict the unknown future with different distribution. on the application side, the prediction accuracy of our approach is 20% higher in recall (correctly detects 1 to 3 more ozone days, depending on the year) and 10% higher in precision (15 to 30 fewer false alarm days per year) than state-of-the-art methods used by air quality control scientists, and these results are significant for tceq.
multi-tier granule mining for representations of multidimensional association rules. it is a big challenge to promise the quality of multidimensional association mining. the essential issue is how to represent meaningful multidimensional association rules efficiently. currently we have not found satisfactory approaches for solving this challenge because of the complicated correlation between attributes. multi-tier granule mining is an initiative for solving this challenging issue. it divides attributes into some tiers and then compresses the large multidimensional database into granules at each tier. it also builds association mappings to illustrate the correlation between tiers. in this way, the meaningful association rules can be justified according to these association mappings.
incremental mining of frequent query patterns from xml queries for caching. existing studies for mining frequent xml query patterns mainly introduce a straightforward candidate generate-and-test strategy and compute frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of xml query patterns transformed from user queries. however, it is nontrivial to maintain such discovered frequent patterns in real xml databases because there may incur frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent ones. accordingly, existing proposals are inefficient for the evolution of the transaction database. to address these problems, this paper presents an efficient algorithm ips-fxqpminer for mining frequent xml query patterns without candidate maintenance and costly tree-containment checking. we transform xml queries into sequences through a oneto- one mapping and then mine the frequent sequences to generate frequent xml query patterns. more importantly, based on ips-fxqpminer, an efficient incremental algorithm, incre-fxqpminer is proposed to incrementally mine frequent xml query patterns, which can minimize the i/o and computation requirements for handling incremental updates. our experimental study on various real-life datasets demonstrates the efficiency and scalability of our algorithms over previous known alternatives.
delta-tolerance closed frequent itemsets. in this paper, we study an inherent problem of mining frequent itemsets (fis): the number of fis mined is often too large. the large number of fis not only affects the mining performance, but also severely thwarts the application of fi mining. in the literature, closed fis (cfis) and maximal fis (mfis) are proposed as concise representations of fis. however, the number of cfis is still too large in many cases, while mfis lose information about the frequency of the fis. to address this problem, we relax the restrictive definition of cfis and propose the \delta-tolerance cfis (\delta- tcfis). mining \delta-tcfis recursively removes all subsets of a \delta-tcfi that fall within a frequency distance bounded by \delta. we propose two algorithms, cfi2tcfi and minetcfi, to mine \delta-tcfis. cfi2tcfi achieves very high accuracy on the estimated frequency of the recovered fis but is less efficient when the number of cfis is large, since it is based on cfi mining. minetcfi is significantly faster and consumes less memory than the algorithms of the state-of-the-art concise representations of fis, while the accuracy of minetcfi is only slightly lower than that of cfi2tcfi.
data mining approaches to criminal career analysis. narrative reports and criminal records are stored digitally across individual police departments, enabling the collection of this data to compile a nation-wide database of criminals and the crimes they committed. the compilation of this data through the last years presents new possibilities of analyzing criminal activity through time. augmenting the traditional, more socially oriented, approach of behavioral study of these criminals and traditional statistics, data mining methods like clustering and prediction enable police forces to get a clearer picture of criminal careers. this allows officers to recognize crucial spots in changing criminal behaviour and deploy resources to prevent these careers from unfolding. four important factors play a role in the analysis of criminal careers: crime nature, frequency, duration and severity. we describe a tool that extracts these from the database and creates digital profiles for all offenders. it compares all individuals on these profiles by a new distance measure and clusters them accordingly. this method yields a visual clustering of these criminal careers and enables the identification of classes of criminals. the proposed method allows for several user-defined parameters.
a novel scalable algorithm for supervised subspace learning. subspace learning approaches aim to discover important statistical distribution on lower dimensions for high dimensional data. methods such as principal component analysis (pca) do not make use of the class information, and linear discriminant analysis (lda) could not be performed efficiently in a scalable way. in this paper, we propose a novel highly scalable supervised subspace learning algorithm called as supervised kampong measure (skm). it assigns data points as close as possible to their corresponding class mean, simultaneously assigns data points to be as far as possible from the other class means in the transformed lower dimensional subspace. theoretical derivation shows that our algorithm is not limited by the number of classes or the singularity problem faced by lda. furthermore, our algorithm can be executed in an incremental manner in which learning is done in an online fashion as data streams are received. experimental results on several datasets, including a very large text data set rcv1, show the outstanding performance of our proposed algorithm on classification problems as compared to pca, lda and a popular feature selection approach, information gain (ig).
constructing ensembles for better ranking. we propose a novel algorithm, rankde, to build an ensemble using an extra artificial dataset. rankde aims at improving the overall ranking performance, which is crucial in many machine learning applications. this algorithm constructs artificial datasets that are diverse with the current training dataset in terms of ranking. we conduct experiments with real-world data sets to compare rankde with some traditional and state-of-the-art ensembling algorithms of bagging, adaboost, decorate and rankboost in terms of ranking. the experiments showthat rankdeoutperforms bagging, decorate, adaboost, and rankboost when limited data is available. when enough training data is available, it is competitive with decorate and adaboost
graphrank: statistical modeling and mining of significant subgraphs in the feature space. we propose a technique for evaluating the statistical significance of frequent subgraphs in a database. a graph is represented by a feature vector that is a histogram over a set of basis elements. the set of basis elements is chosen based on domain knowledge and consists generally of vertices, edges, or small graphs. a given subgraph is transformed to a feature vector and the significance of the subgraph is computed by considering the significance of occurrence of the corresponding vector. the probability of occurrence of the vector in a random vector is computed based on the prior probability of the basis elements. this is then used to obtain a probability distribution on the support of the vector in a database of random vectors. the statistical significance of the vector/subgraph is then defined as the p-value of its observed support. we develop efficient methods for computing p-values and lower bounds. a simplified model is further proposed to improve the efficiency. we also address the problem of feature vector mining, a generalization of itemset mining where counts are associated with items and the goal is to find significant sub-vectors. we present an algorithm that explores closed frequent sub-vectors to find significant ones. experimental results show that the proposed techniques are effective, efficient, and useful for ranking frequent subgraphs by their statistical significance.
diverse topic phrase extraction through latent semantic analysis. we propose a novel algorithm for extracting diverse topic phrases in order to provide summary for large corpora. previous works often ignore the importance of diversity and thus extract phrases crowded on some hot topics while failing to cover other less obvious but important topics. we solve this problem through document re-weighting and phrase diversification by using latent semantic analysis (lsa). experiments on various datasets show that our new algorithm can improve relevance as well as diversity over different topics for topic phrase extraction problems.
secure distributed k-anonymous pattern mining. privacy-preserving data mining is an important area that studies privacy issues of data mining. when the goal is to share data mining results, two privacy-related problems may arise. the first one is how to compute the data-mining results among several parties without sharing the data. cryptography-based primitives are the basic tool used to develop ad-hoc secure multi-party computation protocols that share information as less as possible during the computation under different adversary models. the second one is how to produce data mining results that provably do not contain threats to the anonymity of individuals. the concept of k-anonymity has been used to discover anonymity-preserving frequent patterns, and centralized algorithms have been developed. in this paper and for the first time, we study how to produce anonymity-preserving data mining results in a distributed environment. we present two privacy-preserving strategies and show their feasibility through experimental analysis.
a balanced ensemble approach to weighting classifiers for text classification. this paper studies the problem of constructing an effective heterogeneous ensemble classifier for text classification. one major challenge of this problem is to formulate a good combination function, which combines the decisions of the individual classifiers in the ensemble. we show that the classification performance is affected by three weight components and they should be included in deriving an effective combination function. they are: (1) global effectiveness, which measures the effectiveness of a member classifier in classifying a set of unseen documents; (2) local effectiveness, which measures the effectiveness of a member classifier in classifying the particular domain of an unseen document; and (3) decision confidence, which describes how confident a classifier is when making a decision when classifying a specific unseen document. we propose a new balanced combination function, called dynamic classifier weighting (dcw), that incorporates the afore-mentioned three components. the empirical study demonstrates that the new combination function is highly effective for text classification.
stagger: periodicity mining of data streams using expanding sliding windows. sensor devices are becoming ubiquitous, especially in measurement and monitoring applications. because of the real-time, append-only and semi-infinite natures of the generated sensor data streams, an online incremental approach is a necessity for mining stream data types. in this paper, we propose stagger: a one-pass, online and incremental algorithm for mining periodic patterns in data streams. stagger does not require that the user pre-specify the periodicity rate of the data. instead, stagger discovers the potential periodicity rates. stagger maintains multiple expanding sliding windows staggered over the stream, where computations are shared among the multiple overlapping windows. small-length sliding windows are imperative for early and real-time output, yet are limited to discover short periodicity rates. as streamed data arrives continuously, the sliding windows expand in length in order to cover the whole stream. larger-length sliding windows are able to discover longer periodicity rates. stagger incrementally maintains a tree-like data structure for the frequent periodic patterns of each discovered potential periodicity rate. in contrast to the fourier/wavelet-based approaches used for discovering periodicity rates, stagger not only discovers a wider, more accurate set of periodicities, but also discovers the periodic patterns themselves. in fact, experimental results with real and synthetic data sets show that stagger outperforms fourier/wavelet-based approaches by an order of magnitude in terms of the accuracy of the discovered periodicity rates. moreover, realdata experiments demonstrate the practicality of the discovered periodic patterns.
semi-supervised kernel regression. insufficiency of training data is a major obstacle in machine learning and data mining applications. many different semi-supervised learning algorithms have been proposed to tackle this difficulty by leveraging a large amount of unlabeled data. however, most of them focus on semi-supervised classification. in this paper we propose a semi-supervised regression algorithm named semi-supervised kernel regression (sskr). while classical kernel regression is only based on labeled examples, our approach extends it to all observed examples using a weighting factor to modulate the effect of unlabeled examples. experimental results prove that sskr significantly outperforms traditional kernel regression and graph-based semi-supervised regression methods.
using an ensemble of one-class svm classifiers to harden payload-based anomaly detection systems. unsupervised or unlabeled learning approaches for network anomaly detection have been recently proposed. in particular, recent work on unlabeled anomaly detection focused on high speed classification based on simple payload statistics. for example, payl, an anomaly ids, measures the occurrence frequency in the payload of n-grams. a simple model of normal traffic is then constructed according to this description of the packets' content. it has been demonstrated that anomaly detectors based on payload statistics can be "evaded" by mimicry attacks using byte substitution and padding techniques. in this paper we propose a new approach to construct high speed payload-based anomaly ids intended to be accurate and hard to evade. we propose a new technique to extract the features from the payload. we use a feature clustering algorithm originally proposed for text classification problems to reduce the dimensionality of the feature space. accuracy and hardness of evasion are obtained by constructing our anomaly-based ids using an ensemble of one-class svm classifiers that work on different feature spaces.
mining maximal quasi-bicliques to co-cluster stocks and financial ratios for value investment. we introduce an unsupervised process to co-cluster groups of stocks and financial ratios, so that investors can gain more insight on how they are correlated. our idea for the co-clustering is based on a graph concept called maximal quasi-bicliques, which can tolerate erroneous or/and missing information that are common in the stock and financial ratio data. compared to previous works, our maximal quasi-bicliques require the errors to be evenly distributed, which enable us to capture more meaningful co-clusters. we develop a new algorithm that can efficiently enumerate maximal quasi-bicliques from an undirected graph. the concept of maximal quasi-bicliques is domain-independent; it can be extended to perform co-clustering on any set of data that are modeled by graphs.
cosmic: conceptually specified multi-instance clusters. recently, more and more applications represent data objects as sets of feature vectors or multi-instance objects. in this paper, we propose cosmic, a method for deriving concept lattices from multi-instance data based on hierarchical density-based clustering. the found concepts correspond to groups or clusters of multi-instance objects having similar instances in common. we demonstrate that cosmic outperforms compared methods with respect to efficiency and cluster quality and is capable to extract interesting patterns in multi-instance data sets.
a feature selection and evaluation scheme for computer virus detection. anti-virus systems traditionally use signatures to detect malicious executables, but signatures are over-fitted features that are of little use in machine learning. other more heuristic methods seek to utilize more general features, with some degree of success. in this paper, we present a data mining approach that conducts an exhaustive feature search on a set of computer viruses and strives to obviate over-fitting. we also evaluate the predictive power of a classifier by taking into account dependence relationships that exist between viruses, and we show that our classifier yields high detection rates and can be expected to perform as well in real-world conditions.
discovering partial orders in binary data. we approach the problem of discovering interesting orders in data. in many applications, it is more important to find interesting partial orders since there is often no clear ordering between certain sets of elements. furthermore, a partial order is more robust against partially erroneous data. we present the notion of fundamental partial orders (fpo), and argue that any partial order that satisfies this property is an interesting partial order. to mine such partial orders, we present a two-stage methodology that first finds an interesting total order, and then discovers a partial order satisfying fpo using this total order. to illustrate, we focus on {0, 1} data. this is an important problem with many applications, e.g., in paleontology, where we chronologically order fossil sites by minimizing lazarus counts. we present the experimental results of our method on paleontological data, and show that it outperforms existing approaches. the techniques developed here are general and can be abstracted for mining partial orders in any setting.
biclustering protein complex interactions with a biclique finding algorithm. biclustering has many applications in text mining, web clickstream mining, and bioinformatics. when data entries are binary, the tightest biclusters become bicliques. we propose a flexible and highly efficient algorithm to compute bicliques. we first generalize the motzkin-straus formalism for computing the maximal clique from l_1 constraint to l_p constraint, which enables us to provide a generalized motzkin-straus formalism for computing maximal-edge bicliques. by adjusting parameters, the algorithm can favor biclusters with more rows less columns, or vice verse, thus increasing the flexibility of the targeted biclusters. we then propose an algorithmto solve the generalized motzkin- straus optimization problem. the algorithm is provably convergent and has a computational complexity of o(|e|) where |e| is the number of edges. using this algorithm, we bicluster the yeast protein complex interaction network. we find that biclustering protein complexes at the protein level does not clearly reflect the functional linkage among protein complexes in many cases, while biclustering at protein domain level can reveal many underlying linkages. we show several new biologically significant results.
entity resolution with markov logic. entity resolution is the problem of determining which records in a database refer to the same entities, and is a crucial and expensive step in the data mining process. interest in it has grown rapidly in recent years, and many approaches have been proposed. however, they tend to address only isolated aspects of the problem, and are often ad hoc. this paper proposes a well-founded, integrated solution to the entity resolution problem based on markov logic. markov logic combines first-order logic and probabilistic graphical models by attaching weights to first-order formulas, and viewing them as templates for features of markov networks. we show how a number of previous approaches can be formulated and seamlessly combined in markov logic, and how the resulting learning and inference problems can be solved efficiently. experiments on two citation databases show the utility of this approach, and evaluate the contribution of the different components.