waashk/dblp huggingface dataset:
extracting redundancy-aware top-k patterns. observed in many applications, there is a potential need of extracting a small set of frequent patterns having not only high significance but also low redundancy. the significance is usually defined by the context of applications. previous studies have been concentrating on how to compute top-k significant patterns or how to remove redundancy among patterns separately. there is limited work on finding those top-k patterns which demonstrate high-significance and low-redundancy simultaneously.in this paper, we study the problem of extracting redundancy-aware top-k patterns from a large collection of frequent patterns. we first examine the evaluation functions for measuring the combined significance of a pattern set and propose the mms (maximal marginal significance) as the problem formulation. the problem is known as np-hard. we further present a greedy algorithm which approximates the optimal solution with performance bound o(log k) (with conditions on redundancy), where k is the number of reported patterns. the direct usage of redundancy-aware top-k patterns is illustrated through two real applications: disk block prefetch and document theme extraction. our method can also be applied to processing redundancy-aware top-k queries in traditional database.
attack detection in time series for recommender systems. recent research has identified significant vulnerabilities in recommender systems. shilling attacks, in which attackers introduce biased ratings in order to influence future recommendations, have been shown to be effective against collaborative filtering algorithms. we postulate that the distribution of item ratings in time can reveal the presence of a wide range of shilling attacks given reasonable assumptions about their duration. to construct a time series of ratings for an item, we use a window size of k to group consecutive ratings for the item into disjoint windows and compute the sample average and sample entropy in each window. we derive a theoretically optimal window size to best detect an attack event if the number of attack profiles is known. for practical applications where this number is unknown, we propose a heuristic algorithm that adaptively changes the window size. our experimental results demonstrate that monitoring rating distributions in time series is an effective approach for detecting shilling attacks.
discovering interesting patterns through user's interactive feedback. in this paper, we study the problem of discovering interesting patterns through user's interactive feedback. we assume a set of candidate patterns (ie, frequent patterns) has already been mined. our goal is to help a particular user effectively discover interesting patterns according to his specific interest. without requiring a user to explicitly construct a prior knowledge to measure the interestingness of patterns, we learn the user's prior knowledge from his interactive feedback. we propose two models to represent a user's prior: the log linear model and biased belief model. the former is designed for item-set patterns, whereas the latter is also applicable to sequential and structural patterns. to learn these models, we present a two-stage approach, progressive shrinking and clustering, to select sample patterns for feedback. the experimental results on real and synthetic data sets demonstrate the effectiveness of our approach.
identifying bridging rules between conceptual clusters. a bridging rule in this paper has its antecedent and action from different conceptual clusters. we first design two algorithms for mining bridging rules between clusters in a database, and then propose two non-linear metrics for measuring the interestingness of bridging rules. bridging rules can be distinct from association rules (or frequent itemsets). this is because (1) bridging rules can be generated by infrequent itemsets that are pruned in association rule mining; and (2) bridging rules are measured by the importance that includes the distance between two conceptual clusters, whereas frequent itemsets are measured by only the support.
exploiting a support-based upper bound of pearson's correlation coefficient for efficiently identifying strongly correlated pairs. given a user-specified minimum correlation threshold θ and a market basket database with n items and t transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. however, when the number of items and transactions are large, the computation cost of this query can be very high. in this paper, we identify an upper bound of pearson's correlation coefficient for binary variables. this upper bound is not only much cheaper to compute than pearson's correlation coefficient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. a two-step all-strong-pairs correlation que ry (taper) algorithm is proposed to exploit these properties in a filter-and-refine manner. furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common zipf or linear rank-support distributions. experimental results from synthetic and real data sets exhibit similar trends and show that the taper algorithm can be an order of magnitude faster than brute-force alternatives.
k-means clustering versus validation measures: a data distribution perspective. k-means is a well-known and widely used partitional clustering method. while there are considerable research efforts to characterize the key features of the k-means clustering algorithm, further investigation is needed to understand how data distributions can have impact on the performance of k-means clustering. to that end, in this paper, we provide a formal and organized study of the effect of skewed data distributions on k-means clustering. along this line, we first formally illustrate that k-means tends to produce clusters of relatively uniform size, even if input data have varied "true" cluster sizes. in addition, we show that some clustering validation measures, such as the entropy measure, may not capture this uniform effect and provide misleading information on the clustering performance. viewed in this light, we provide the coefficient of variation (cv) as a necessary criterion to validate the clustering results. our findings reveal that k-means tends to produce clusters in which the variations of cluster sizes, as measured by cv, are in a range of about 0.3-1.0. specifically, for data sets with large variation in "true" cluster sizes (e.g., cv > 1.0), k-means reduces variation in resultant cluster sizes to less than 1.0. in contrast, for data sets with small variation in "true" cluster sizes (e.g., cv < 0.3), k-means increases variation in resultant cluster sizes to greater than 0.3. in other words, for the earlier two cases, k-means produces the clustering results which are away from the "true" cluster distributions.
utility-based anonymization using local recoding. privacy becomes a more and more serious concern in applications involving microdata. recently, efficient anonymization has attracted much research work. most of the previous methods use global recoding, which maps the domains of the quasi-identifier attributes to generalized or changed values. however, global recoding may not always achieve effective anonymization in terms of discernability and query answering accuracy using the anonymized data. moreover, anonymized data is often for analysis. as well accepted in many analytical applications, different attributes in a data set may have different utility in the analysis. the utility of attributes has not been considered in the previous methods.in this paper, we study the problem of utility-based anonymization. first, we propose a simple framework to specify utility of attributes. the framework covers both numeric and categorical data. second, we develop two simple yet efficient heuristic local recoding methods for utility-based anonymization. our extensive performance study using both real data sets and synthetic data sets shows that our methods outperform the state-of-the-art multidimensional global recoding methods in both discernability and query answering accuracy. furthermore, our utility-based method can boost the quality of analysis using the anonymized data.
mining progressive confident rules. many real world objects have states that change over time. by tracking the state sequences of these objects, we can study their behavior and take preventive measures before they reach some undesirable states. in this paper, we propose a new kind of pattern called progressive confident rules to describe sequences of states with an increasing confidence that lead to a particular end state. we give a formal definition of progressive confident rules and their concise set. we devise pruning strategies to reduce the enormous search space. experiment result shows that the proposed algorithm is efficient and scalable. we also demonstrate the application of progressive confident rules in classification.
dynamic syslog mining for network failure monitoring. syslog monitoring technologies have recently received vast attentions in the areas of network management and network monitoring. they are used to address a wide range of important issues including network failure symptom detection and event correlation discovery. syslogs are intrinsically dynamic in the sense that they form a time series and that their behavior may change over time. this paper proposes a new methodology of dynamic syslog mining in order to detect failure symptoms with higher confidence and to discover sequential alarm patterns among computer devices. the key ideas of dynamic syslog mining are 1) to represent syslog behavior using a mixture of hidden markov models, 2) to adaptively learn the model using an on-line discounting learning algorithm in combination with dynamic selection of the optimal number of mixture components, and 3) to give anomaly scores using universal test statistics with a dynamically optimized threshold. using real syslog data we demonstrate the validity of our methodology in the scenarios of failure symptom detection, emerging pattern identification, and correlation discovery.
extracting key-substring-group features for text classification. in many text classification applications, it is appealing to take every document as a string of characters rather than a bag of words. previous research studies in this area mostly focused on different variants of generative markov chain models. although discriminative machine learning methods like support vector machine (svm) have been quite successful in text classification with word features, it is neither effective nor efficient to apply them straightforwardly taking all substrings in the corpus as features. in this paper, we propose to partition all substrings into statistical equivalence groups, and then pick those groups which are important (in the statistical sense) as features (named key-substring-group features) for text classification. in particular, we propose a suffix tree based algorithm that can extract such features in linear time (with respect to the total number of characters in the corpus). our experiments on english, chinese and greek datasets show that svm with key-substring-group features can achieve outstanding performance for various text classification tasks.
discovering outlier filtering rules from unlabeled data: combining a supervised learner with an unsupervised learner. this paper is concerned with the problem of detecting outliers from unlabeled data. in prior work we have developed smartsifter, which is an on-line outlier detection algorithm based on unsupervised learning from data. on the basis of smartsifter this paper yields a new framework for outlier filtering using both supervised and unsupervised learning techniques iteratively in order to make the detection process more effective and more understandable. the outline of the framework is as follows: in the first round, for an initial dataset, we run smartsifter to give each data a score, with a high score indicating a high possibility of being an outlier. next, giving positive labels to a number of higher scored data and negative labels to a number of lower scored data, we create labeled examples. then we construct an outlier filtering rule by supervised learning from them. here the rule is generated based on the principle of minimizing extended stochastic complexity. in the second round, for a new dataset, we filter the data using the constructed rule, then among the filtered data, we run smartsifter again to evaluate the data in order to update the filtering rule. applying of our framework to the network intrusion detection, we demonstrate that 1) it can significantly improve the accuracy of smartsifter, and 2) outlier filtering rules can help the user to discover a general pattern of an outlier group.
a unifying framework for detecting outliers and change points from non-stationary time series data. we are concerned with the issues of outlier detection and change point detection from a data stream. in the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. in this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.
on-line unsupervised outlier detection using finite mixtures with discounting learning algorithms. outlier detection is a fundamental issue in data mining, specifically in fraud detection, network intrusion detection, network monitoring, etc. smartsifter is an outlier detection engine addressing this problem from the viewpoint of statistical learning theory. this paper provides a theoretical basis for smartsifter and empirically demonstrates its effectiveness. smartsifter detects outliers in an on-line process through the on-line unsupervised learning of a probabilistic model (using a finite mixture model) of the information source. each time a datum is input smartsifter employs an on-line discounting learning algorithm to learn the probabilistic model. a score is given to the datum based on the learned model with a high score indicating a high possibility of being a statistical outlier. the novel features of smartsifter are: (1) it is adaptive to non-stationary sources of data&semi; (2) a score has a clear statistical/information-theoretic meaning&semi; (3) it is computationally inexpensive&semi; and (4) it can handle both categorical and continuous variables. an experimental application to network intrusion detection shows that smartsifter was able to identify data with high scores that corresponded to attacks, with low computational costs. further experimental application has identified a number of meaningful rare cases in actual health insurance pathology data from australia's health insurance commission.
fast mining of spatial collocations. spatial collocation patterns associate the co-existence of non-spatial features in a spatial neighborhood. an example of such a pattern can associate contaminated water reservoirs with certain deceases in their spatial neighborhood. previous work on discovering collocation patterns converts neighborhoods of feature instances to itemsets and applies mining techniques for transactional data to discover the patterns. we propose a method that combines the discovery of spatial neighborhoods with the mining process. our technique is an extension of a spatial join algorithm that operates on multiple inputs and counts long pattern instances. as demonstrated by experimentation, it yields significant performance improvements compared to previous approaches.
beyond classification and ranking: constrained optimization of the roi. classification has been commonly used in many data mining projects in the financial service industry. for instance, to predict collectability of accounts receivable, a binary class label is created based on whether a payment is received within a certain period. however, optimization of the classifier does not necessarily lead to maximization of return on investment (roi), since maximization of the true positive rate is often different from maximization of the collectable amount which determines the roi under a fixed budget constraint. the typical cost sensitive learning does not solve this problem either since it involves an unknown opportunity cost due to the budget constraint. learning the ranks of collectable amount would ultimately solve the problem, but it tries to tackle an unnecessarily difficult problem and often results in poorer results for our specific target. we propose a new algorithm that uses gradient descent to directly optimize the related monetary measure under the budget constraint and thus maximizes the roi. by comparison with several classification, regression, and ranking algorithms, we demonstrate the new algorithm's substantial improvement of the financial impact on our clients in the financial service industry.
linear prediction models with graph regularization for web-page categorization. we present a risk minimization formulation for learning from both text and graph structures which is motivated by the problem of collective inference for hypertext document categorization. the method is based on graph regularization formulated as a well-formed convex optimization problem. we present numerical algorithms for our formulation, and show that such combination of local text features and link information can lead to improved predictive accuracy.
summarizing itemset patterns: a profile-based approach. frequent-pattern mining has been studied extensively on scalable methods for mining various kinds of patterns including itemsets, sequences, and graphs. however, the bottleneck of frequent-pattern mining is not at the efficiency but at the interpretability, due to the huge number of patterns generated by the mining process.in this paper, we examine how to summarize a collection of itemset patterns using only k representatives, a small number of patterns that a user can handle easily. the k representatives should not only cover most of the frequent patterns but also approximate their supports. a generative model is built to extract and profile these representatives, under which the supports of the patterns can be easily recovered without consulting the original dataset. based on the restoration error, we propose a quality measure function to determine the optimal value of parameter k. polynomial time algorithms are developed together with several optimization heuristics for efficiency improvement. empirical studies indicate that we can obtain compact summarization in real datasets.
on the discovery of significant statistical quantitative rules. in this paper we study market share rules, rules that have a certain market share statistic associated with them. such rules are particularly relevant for decision making from a business perspective. motivated by market share rules, in this paper we consider statistical quantitative rules (sq rules) that are quantitative rules in which the rhs can be any statistic that is computed for the segment satisfying the lhs of the rule. building on prior work, we present a statistical approach for learning all significant sq rules, i.e., sq rules for which a desired statistic lies outside a confidence interval computed for this rule. in particular we show how resampling techniques can be effectively used to learn significant rules. since our method considers the significance of a large number of rules in parallel, it is susceptible to learning a certain number of "false" rules. to address this, we present a technique that can determine the number of significant sq rules that can be expected by chance alone, and suggest that this number can be used to determine a "false discovery rate" for the learning procedure. we apply our methods to online consumer purchase data and report the results.
enhancing the lift under budget constraints: an application in the mutual fund industry. a lift curve, with the true positive rate on the y-axis and the customer pull (or contact) rate on the x-axis, is often used to depict the model performance in many data mining applications, especially in the area of customer relationship management (crm). typically, these applications concern only the model accuracy at a relatively small pull or contact/intervention rate of the whole customer base, which is predetermined by a budget constraint for the project, e.g., how many customers can be contacted every month. in this paper, we address the important problem of enhancing the lift (true positive rate) at a specified pull rate. we propose two distinct algorithms, which are applicable to different scenarios. in particular, when the binary class label of the training set is extracted from a continuous variable, we can optimize a training objective which takes into account the specified pull rate rather than the class prior, based on the often ignored continuous variable. in those cases where only the binary class label is available during training, we propose a constrained optimization algorithm to maximize the true positive rate related to a specific decision threshold at which the specified pull rate is achieved. we applied both algorithms to our projects of predicting defection (decline in account value) of mutual fund accounts for two major u.s. mutual fund companies and achieved substantial enhancement of the lift at the specified pull rate.
closegraph: mining closed frequent graph patterns. recent research on pattern discovery has progressed form mining frequent itemsets and sequences to mining structured patterns including trees, lattices, and graphs. as a general data structure, graph can model complicated relations among data with wide applications in bioinformatics, web exploration, and etc. however, mining large graph patterns in challenging due to the presence of an exponential number of frequent subgraphs. instead of mining all the subgraphs, we propose to mine closed frequent graph patterns. a graph g is closed in a database if there exists no proper supergraph of g that has the same support as g. a closed graph pattern mining algorithm, closegraph, is developed by exploring several interesting pruning methods. our performance study shows that closegraph not only dramatically reduces unnecessary subgraphs to be generated but also substantially increases the efficiency of mining, especially in the presence of large graph patterns.