waashk/dblp huggingface dataset:
querying multiple sets of discovered rules. rule mining is an important data mining task that has been applied to numerous real-world applications. often a rule mining system generates a large number of rules and only a small subset of them is really useful in applications. although there exist some systems allowing the user to query the discovered rules, they are less suitable for complex ad hoc querying of multiple data mining rulebases to retrieve interesting rules. in this paper, we propose a new powerful rule query language rule-ql for querying multiple rulebases that is modeled after sql and has rigorous theoretical foundations of a rule-based calculus. in particular, we first propose a rule-based calculus rc based on the first-order logic, and then present the language rule-ql that is at least as expressive as the safe fragment of rc. we also propose a number of efficient query evaluation techniques for rule-ql and test them experimentally on some representative queries to demonstrate the feasibility of rule-ql.
single-shot detection of multiple categories of text using parametric mixture models. in this paper, we address the problem of detecting multiple topics or categories of text where each text is not assumed to belong to one of a number of mutually exclusive categories. conventionally, the binary classification approach has been employed, in which whether or not text belongs to a category is judged by the binary classifier for every category. in this paper, we propose a more sophisticated approach to simultaneously detect multiple categories of text using parametric mixture models (pmms), newly presented in this paper. pmms are probabilistic generative models for text that has multiple categories. our pmms are essentially different from the conventional mixture of multinomial distributions in the sense that in the former several basis multinomial parameters are mixed in the parameter space, while in the latter several multinomial components are mixed. we derive efficient learning algorithms for pmms within the framework of the maximum a posteriori estimate. we also empirically show that our method can outperform the conventional binary approach when applied to multitopic detection of world wide web pages, focusing on those from the "yahoo.com" domain.
what's the code?: automatic classification of source code archives. there are various source code archives on the world wide web. these archives are usually organized by application categories and programming languages. however, manually organizing source code repositories is not a trivial task since they grow rapidly and are very large (on the order of terabytes). we demonstrate machine learning methods for automatic classification of archived source code into eleven application topics and ten programming languages. for topical classification, we concentrate on c and c++ programs from the ibiblio and the sourceforge archives. support vector machine (svm) classifiers are trained on examples of a given programming language or programs in a specified category. we show that source code can be accurately and automatically classified into topical categories and can be identified to be in a specific programming language class.
finding partial orders from unordered 0-1 data. in applications such as paleontology and medical genetics the 0-1 data has an underlying unknown order (the ages of the fossil sites, the locations of markers in the genome). the order might be total or partial: for example, two sites in different parts of the globe might be ecologically incomparable, or the ordering of certain markers might be different in different subgroups of the data. we consider the following problem. given a table over a set of 0-1 variables, find a partial order for the rows minimizing a score function and being as specific as possible. the score function can be, e.g., the number of changes from 1 to 0 in a column (for paleontology) or the likelihood of the marker sequence (for genomic data). our solution for this task first constructs small totally ordered fragments of the partial order, then finds good orientations for the fragments, and finally uses a simple and efficient heuristic method for finding a partial order that corresponds well with the collection of fragments. we describe the method, discuss its properties, and give empirical results on paleontological data demonstrating the usefulness of the method. in the application the use of the method highlighted some previously unknown properties of the data and pointed out probable errors in the data.
privacy preserving association rule mining in vertically partitioned data. privacy considerations often constrain data mining projects. this paper addresses the problem of association rule mining where transactions are distributed across sources. each site holds some attributes of each transaction, and the sites wish to collaborate to identify globally valid association rules. however, the sites must not reveal individual transaction data. we present a two-party algorithm for efficiently discovering frequent itemsets with minimum support levels, without either site revealing individual transaction values.
privacy-preserving -means clustering over vertically partitioned data. privacy and security concerns can prevent sharing of data, derailing data mining projects. distributed knowledge discovery, if done correctly, can alleviate this problem. the key is to obtain valid results, while providing guarantees on the (non)disclosure of data. we present a method for k-means clustering when different sites contain different attributes for a common set of entities. each site learns the cluster of each entity, but learns nothing about the attributes at other sites.
camouflaged fraud detection in domains with complex relationships. we describe a data mining system to detect frauds that are camouflaged to look like normal activities in domains with high number of known relationships. examples include accounting fraud detection for rating and investment, insider attacks on corporate networks, and health care insurance fraud. our goal is to help analysts who are overwhelmed with information about companies or on-line system access logs or insurance claims to focus their attentions on features that cause damage in the future. we focused on accounting fraud where the task is to detect the subset of companies that were potentially committing accounting fraud within the total population of public companies that file quarterly and annual filings with the securities and exchange commission (sec). using (a) representation of changes, (b) a mix of decision tree learning, locally weighted logistic regression, k-means clustering, and constant regression in a two phase pipe line, we developed models that rank companies based on the probability of forecasting future damaging performance. the learned models were tested extensively over four years with public data available from sec filings and private data available from rating companies and investment firms. cross validation experiments and analyst based validation of private experiments were found to show that the approach performed as well as or better than domain experts and discovered new relationships that domain experts did not use on a regular basis. finally, the detections preceded public knowledge of such problems by six to eighteen months.
non-linear dimensionality reduction techniques for classification and visualization. in this paper we address the issue of using local embeddings for data visualization in two and three dimensions, and for classification. we advocate their use on the basis that they provide an efficient mapping procedure from the original dimension of the data, to a lower intrinsic dimension. we depict how they can accurately capture the user's perception of similarity in high-dimensional data for visualization purposes. moreover, we exploit the low-dimensional mapping provided by these embeddings, to develop new classification techniques, and we show experimentally that the classification accuracy is comparable (albeit using fewer dimensions) to a number of other classification procedures.
rotation invariant distance measures for trajectories. for the discovery of similar patterns in 1d time-series, it is very typical to perform a normalization of the data (for example a transformation so that the data follow a zero mean and unit standard deviation). such transformations can reveal latent patterns and are very commonly used in datamining applications. however, when dealing with multidimensional time-series, which appear naturally in applications such as video-tracking, motion-capture etc, similar motion patterns can also be expressed at different orientations. it is therefore imperative to provide support for additional transformations, such as rotation. in this work, we transform the positional information of moving data, into a space that is translation, scale and rotation invariant. our distance measure in the new space is able to detect elastic matches and can be efficiently lower bounded, thus being computationally tractable. the proposed methods are easy to implement, fast to compute and can have many applications for real world problems, in areas such as handwriting recognition and posture estimation in motion-capture data. finally, we empirically demonstrate the accuracy and the efficiency of the technique, using real and synthetic handwriting data.
indexing multi-dimensional time-series with support for multiple distance measures. although most time-series data mining research has concentrated on providing solutions for a single distance function, in this work we motivate the need for a single index structure that can support multiple distance measures. our specific area of interest is the efficient retrieval and analysis of trajectory similarities. trajectory datasets are very common in environmental applications, mobility experiments, video surveillance and are especially important for the discovery of certain biological patterns. our primary similarity measure is based on the longest common subsequence (lcss) model, that offers enhanced robustness, particularly for noisy data, which are encountered very often in real world applications. however, our index is able to accommodate other distance measures as well, including the ubiquitous euclidean distance, and the increasingly popular dynamic time warping (dtw). while other researchers have advocated one or other of these similarity measures, a major contribution of our work is the ability to support all these measures without the need to restructure the index. our framework guarantees no false dismissals and can also be tailored to provide much faster response time at the expense of slightly reduced precision/recall. the experimental results demonstrate that our index can help speed-up the computation of expensive similarity measures such as the lcss and the dtw.
1-dimensional splines as building blocks for improving accuracy of risk outcomes models. transformation of both the response variable and the predictors is commonly used in fitting regression models. however, these transformation methods do not always provide the maximum linear correlation between the response variable and the predictors, especially when there are non-linear relationships between predictors and the response such as the medical data set used in this study. a spline based transformation method is proposed that is second order smooth, continuous, and minimizes the mean squared error between the response and each predictor. since the computation time for generating this spline is o(n), the processing time is reasonable with massive data sets. in contrast to cubic smoothing splines, the resulting transformation equations also display a high level of efficiency for scoring. data used for predicting health outcomes contains an abundance of non-linear relationships between predictors and the outcomes requiring an algorithm for modeling them accurately. thus, a transformation that fits an adaptive cubic spline to each of a set of variables is proposed. these curves are used as a set of transformation functions on the predictors. a case study of how the transformed variables can be fed into a simple linear regression model to predict risk outcomes is presented. the results show significant improvement over the performance of the original variables in both linear and non-linear models.
on interactive visualization of high-dimensional data using the hyperbolic plane. we propose a novel projection based visualization method for high-dimensional datasets by combining concepts from mds and the geometry of the hyperbolic spaces. our approach hyperbolic multi-dimensional scaling (h-mds) extends earlier work [7] using hyperbolic spaces for visualization of tree structures data ( "hyperbolic tree browser" ).by borrowing concepts from multi-dimensional scaling we map proximity data directly into the 2-dimensional hyperbolic space (h2). this removes the restriction to "quasihierarchical", graph-based data -- limiting previous work. since a suitable distance function can convert all kinds of data to proximity (or distance-based) data this type of data can be considered the most general.we used the circular poincar&eacute; model of the h2 which allows effective human-computer interaction: by moving the "focus" via mouse the user can navigate in the data without loosing the "context". in h2 the "fish-eye" behavior originates not simply by a non-linear view transformation but rather by extraordinary, non-euclidean properties of the h2. especially, the exponential growth of length and area of the underlying space makes the h2 a prime target for mapping hierarchical and (now also) high-dimensional data.we present several high-dimensional mapping examples including synthetic and real world data and a successful application for unstructured text. by analyzing and integrating multiple film critiques from news:rec.art.movies.reviews and the internet movie database, each movie becomes placed within the h2. here the idea is, that related films share more words in their reviews than unrelated. their semantic proximity leads to a closer arrangement. the result is a kind of high-level content structured display allowing the user to explore the "space of movies".
anonymizing sequential releases. an organization makes a new release as new information become available, releases a tailored view for each data request, releases sensitive information and identifying information separately. the availability of related releases sharpens the identification of individuals by a global quasi-identifier consisting of attributes from related releases. since it is not an option to anonymize previously released data, the current release must be anonymized to ensure that a global quasi-identifier is not effective for identification. in this paper, we study the sequential anonymization problem under this assumption. a key question is how to anonymize the current release so that it cannot be linked to previous releases yet remains useful for its own release purpose. we introduce the lossy join, a negative property in relational database design, as a way to hide the join relationship among releases, and propose a scalable and practical solution.
mining concept-drifting data streams using ensemble classifiers. recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. in this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. we train an ensemble of classification models, such as c4.5, ripper, naive beyesian, etc., from sequential chunks of the data stream. the classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
closet+: searching for the best strategies for mining frequent closed itemsets. mining frequent closed itemsets provides complete and non-redundant results for frequent pattern analysis. extensive studies have proposed various strategies for efficient frequent closed itemset mining, such as depth-first search vs. breadthfirst search, vertical formats vs. horizontal formats, tree-structure vs. other data structures, top-down vs. bottom-up traversal, pseudo projection vs. physical projection of conditional database, etc. it is the right time to ask "what are the pros and cons of the strategies?" and "what and how can we pick and integrate the best strategies to achieve higher performance in general cases?"in this study, we answer the above questions by a systematic study of the search strategies and develop a winning algorithm closet+. closet+ integrates the advantages of the previously proposed effective strategies as well as some ones newly developed here. a thorough performance study on synthetic and real data sets has shown the advantages of the strategies and the improvement of closet+ over existing mining algorithms, including closet, charm and op, in terms of runtime, memory usage and scalability.
mining unexpected rules by pushing user dynamics. unexpected rules are interesting because they are either previously unknown or deviate from what prior user knowledge would suggest. in this paper, we study three important issues that have been previously ignored in mining unexpected rules. first, the unexpectedness of a rule depends on how the user prefers to apply the prior knowledge to a given scenario, in addition to the knowledge itself. second, the prior knowledge should be considered right from the start to focus the search on unexpected rules. third, the unexpectedness of a rule depends on what other rules the user has seen so far. thus, only rules that remain unexpected given what the user has seen should be considered interesting. we develop an approach that addresses all three problems above and evaluate it by means of experiments focusing on finding interesting rules.
web object indexing using domain knowledge. a web object is defined to represent any meaningful object embedded in web pages (e.g. images, music) or pointed to by hyperlinks (e.g. downloadable files). in many cases, users would like to search for information of a certain 'object', rather than a web page containing the query terms. to facilitate web object searching and organizing, in this paper, we propose a novel approach to web object indexing, by discovering its inherent structure information with existed domain knowledge. in our approach, first, layered lsi spaces are built for a better representation of the hierarchically structured domain knowledge, in order to emphasize the specific semantics and term space in each layer of the domain knowledge. meanwhile, the web object representation is constructed by hyperlink analysis, and further pruned to remove the noises. then an optimal matching between the web object and the domain knowledge is performed, in order to pick out the structure attributes of the web object from the knowledge. finally, the obtained structure attributes are used to re-organize and index the web objects. our approach also indicates a new promising way to use trust-worthy deep web knowledge to help organize dispersive information of surface web.
topics over time: a non-markov continuous-time model of topical trends. this paper presents an lda-style topic model that captures not only the low-dimensional structure of data, but also how the structure changes over time. unlike other recent work that relies on markov assumptions or discretization of time, here each topic is associated with a continuous distribution over timestamps, and for each generated document, the mixture distribution over topics is influenced by both word co-occurrences and the document's timestamp. thus, the meaning of a particular topic can be relied upon as constant, but the topics' occurrence and correlations change significantly over time. we present results on nine months of personal email, 17 years of nips research papers and over 200 years of presidential state-of-the-union addresses, showing improved topics, better timestamp prediction, and interpretable trends.
summarizing itemset patterns using probabilistic models. in this paper, we propose a novel probabilistic approach to summarize frequent itemset patterns. such techniques are useful for summarization, post-processing, and end-user interpretation, particularly for problems where the resulting set of patterns are huge. in our approach items in the dataset are modeled as random variables. we then construct a markov random fields (mrf) on these variables based on frequent itemsets and their occurrence statistics. the summarization proceeds in a level-wise iterative fashion. occurrence statistics of itemsets at the lowest level are used to construct an initial mrf. statistics of itemsets at the next level can then be inferred from the model. we use those patterns whose occurrence can not be accurately inferred from the model to augment the model in an iterative manner, repeating the procedure until all frequent itemsets can be modeled. the resulting mrf model affords a concise and useful representation of the original collection of itemsets. extensive empirical study on real datasets show that the new approach can effectively summarize a large number of itemsets and typically significantly outperforms extant approaches.
pattern-based similarity search for microarray data. one fundamental task in near-neighbor search as well as other similarity matching efforts is to find a distance function that can efficiently quantify the similarity between two objects in a meaningful way. in dna microarray analysis, the expression levels of two closely related genes may rise and fall synchronously in response to a set of experimental stimuli. although the magnitude of their expression levels may not be close, the patterns they exhibit can be very similar. unfortunately, none of the conventional distance metrics such as the lp norm can model this similarity effectively. in this paper, we study the near-neighbor search problem based on this new type of similarity. we propose to measure the distance between two genes by subspace pattern similarity, i.e., whether they exhibit a synchronous pattern of rise and fall on a subset of dimensions. we then present an efficient algorithm for subspace near-neighbor search based on pattern similarity distance, and we perform tests on various data sets to show its effectiveness.
item selection by "hub-authority" profit ranking. a fundamental problem in business and other applications is ranking items with respect to some notion of profit based on historical transactions. the difficulty is that the profit of one item not only comes from its own sales, but also from its influence on the sales of other items, i.e., the "cross-selling effect". in this paper, we draw an analogy between this influence and the mutual reinforcement of hub/authority web pages. based on this analogy, we present a novel approach to the item ranking problem.we apply this ranking approach to solve two selection problems. in size-constrained selection, the maximum number of items that can be selected is fixed. in cost-constrained selection, there is no maximum number of items to be selected, but there is some cost associated with the selection of each item. in both cases, the question is what items should be selected to maximize the profit. empirically, we show that this method finds profitable items in the presence of cross-selling effect.