waashk/dblp huggingface dataset:
collusion in the u.s. crop insurance program: applied data mining. this paper quantitatively analyzes indicators of agent (policy seller), adjuster (indemnity claim adjuster), producer (policy purchaser/holder) indemnity behavior suggestive of collusion in the united states department of agriculture (usda) risk management agency (rma) national crop insurance program. according to guidance from the federal law and using six indicator variables of indemnity behavior, those entities equal to or exceeding 150% of the county mean (computed using a simple jackknife procedure) on all entity-relevant indicators were flagged as "anomalous." log linear analysis was used to test (i) hierarchical node-node arrangements and (2) a non-recursive model of node information sharing. chi-square distributed deviance statistic identified the optimal log linear model. the results of the applied data mining technique used here suggest that the non-recursive triplet and agent-producer doublet collusion probabilistically accounts for the greatest proportion of waste, fraud, and abuse in the federal crop insurance program. triplet and agent-producer doublets need detailed investigation for possible collusion. hence, this data mining technique provided a high level of confidence when 24 million records were quantitatively analyzed for possible fraud, waste, or other abuse of the crop insurance program administered by the usda rma, and suspect entities reported to usda. this data mining technique can be applied where vast amounts of data are available to detect patterns of collusion or conspiracy as may be of interest to the criminal justice or intelligence agencies.
gplag: detection of software plagiarism by program dependence graph analysis. along with the blossom of open source projects comes the convenience for software plagiarism. a company, if less self-disciplined, may be tempted to plagiarize some open source projects for its own products. although current plagiarism detection tools appear sufficient for academic use, they are nevertheless short for fighting against serious plagiarists. for example, disguises like statement reordering and code insertion can effectively confuse these tools. in this paper, we develop a new plagiarism detection tool, called gplag, which detects plagiarism by mining program dependence graphs (pdgs). a pdg is a graphic representation of the data and control dependencies within a procedure. because pdgs are nearly invariant during plagiarism, gplag is more effective than state-of-the-art tools for plagiarism detection. in order to make gplag scalable to large programs, a statistical lossy filter is proposed to prune the plagiarism search space. experiment study shows that gplag is both effective and efficient: it detects plagiarism that easily slips over existing tools, and it usually takes a few seconds to find (simulated) plagiarism in programs having thousands of lines of code.
mining data records in web pages. a large amount of information on the web is contained in regularly structured objects, which we call data records. such data records are important because they often present the essential information of their host pages, e.g., lists of products or services. it is useful to mine such data records in order to extract information from them to provide value-added services. existing automatic techniques are not satisfactory because of their poor accuracies. in this paper, we propose a more effective technique to perform the task. the technique is based on two observations about data records on the web and a string matching algorithm. the proposed technique is able to mine both contiguous and non-contiguous data records. our experimental results show that the proposed technique outperforms existing techniques substantially.
identifying non-actionable association rules. building predictive models and finding useful rules are two important tasks of data mining. while building predictive models has been well studied, finding useful rules for action still presents a major problem. a main obstacle is that many data mining algorithms often produce too many rules. existing research has shown that most of the discovered rules are actually redundant or insignificant. pruning techniques have been developed to remove those spurious and/or insignificant rules. in this paper, we argue that being a significant rule (or a non-redundant rule), however, does not mean that it is a potentially useful rule for action. many significant rules (unpruned rules) are in fact not actionable. this paper studies this issue and presents an efficient algorithm to identify these non-actionable rules. experiment results on many real-life datasets show that the number of non-actionable rules is typically quite large. the proposed technique thus enables the user to focus on fewer rules and to be assured that the remaining rules are non-redundant and potentially useful for action.
discovering the set of fundamental rule changes. the world around us changes constantly. knowing what has changed is an important part of our lives. for businesses, recognizing changes is also crucial. it allows businesses to adapt themselves to the changing market needs. in this paper, we study changes of association rules from one time period to another. one approach is to compare the supports and/or confidences of each rule in the two time periods and report the differences. this technique, however, is too simplistic as it tends to report a huge number of rule changes, and many of them are, in fact, simply the snowball effect of a small subset of fundamental changes. here, we present a technique to highlight the small subset of fundamental changes. a change is fundamental if it cannot be explained by some other changes. the proposed technique has been applied to a number of real-life datasets. experiments results show that the number of rules whose changes are unexplainable is quite small (about 20% of the total number of changes discovered), and many of these unexplainable changes reflect some fundamental shifts in the application domain.
incremental context mining for adaptive document classification. automatic document classification (dc) is essential for the management of information and knowledge. this paper explores two practical issues in dc: (1) each document has its context of discussion, and (2) both the content and vocabulary of the document database is intrinsically evolving. the issues call for adaptive document classification (adc) that adapts a dc system to the evolving contextual requirement of each document category, so that input documents may be classified based on their contexts of discussion. we present an incremental context mining technique to tackle the challenges of adc. theoretical analyses and empirical results show that, given a text hierarchy, the mining technique is efficient in incrementally maintaining the evolving contextual requirement of each category. based on the contextual requirements mined by the system, higher-precision dc may be achieved with better efficiency.
on computing, storing and querying frequent patterns. extensive efforts have been devoted to developing efficient algorithms for mining frequent patterns. however, frequent pattern mining remains a time-consuming process, especially for very large datasets. it is therefore desirable to adopt a "mining once and using many times" strategy. unfortunately, there has been little work reported on managing and organizing a large set of patterns for future use. in this paper, we propose a disk-based data structure, cfp-tree (condensed frequent pattern tree), for organizing frequent patterns discovered from transactional databases. in addition to an efficient algorithm for cfp-tree construction, we also developed algorithms to efficiently support two important types of queries, namely queries with minimum support constraints and queries with item constraints, against the stored patterns, as these two types of queries are basic building blocks for complex frequent pattern related mining tasks. comprehensive experimental study has been conducted to demonstrate the effectiveness of cfp-tree and efficiency of related algorithms.
discovering unexpected information from your competitors' web sites. ever since the beginning of the web, finding useful information from the web has been an important problem. existing approaches include keyword-based search, wrapper-based information extraction, web query and user preferences. these approaches essentially find information that matches the user's explicit specifications. this paper argues that this is insufficient. there is another type of information that is also of great interest, i.e., unexpected information, which is unanticipated by the user. finding unexpected information is useful in many applications. for example, it is useful for a company to find unexpected information bout its competitors, e.g., unexpected services and products that its competitors offer. with this information, the company can learn from its competitors and/or design counter measures to improve its competitiveness. since the number of pages of a typical commercial site is very large and there are also many relevant sites (competitors), it is very difficult for a human user to view each page to discover the unexpected information. automated assistance is needed. in this paper, we propose a number of methods to help the user find various types of unexpected information from his/her competitors' web sites. experiment results show that these techniques are very useful in practice and also efficient.
mining frequent item sets by opportunistic projection. in this paper, we present a novel algorithm opportune project for mining complete set of frequent item sets by projecting databases to grow a frequent item set tree. our algorithm is fundamentally different from those proposed in the past in that it opportunistically chooses between two different structures, array-based or tree-based, to represent projected transaction subsets, and heuristically decides to build unfiltered pseudo projection or to make a filtered copy according to features of the subsets. more importantly, we propose novel methods to build tree-based pseudo projections and array-based unfiltered projections for projected transaction subsets, which makes our algorithm both cpu time efficient and memory saving. basically, the algorithm grows the frequent item set tree by depth first search, whereas breadth first search is used to build the upper portion of the tree if necessary. we test our algorithm versus several other algorithms on real world datasets, such as bms-pos, and on ibm artificial datasets. the empirical results show that our algorithm is not only the most efficient on both sparse and dense databases at all levels of support threshold, but also highly scalable to very large databases.
a framework for ontology-driven subspace clustering. traditional clustering is a descriptive task that seeks to identify homogeneous groups of objects based on the values of their attributes. while domain knowledge is always the best way to justify clustering, few clustering algorithms have ever take domain knowledge into consideration. in this paper, the domain knowledge is represented by hierarchical ontology. we develop a framework by directly incorporating domain knowledge into clustering process, yielding a set of clusters with strong ontology implication. during the clustering process, ontology information is utilized to efficiently prune the exponential search space of the subspace clustering algorithms. meanwhile, the algorithm generates automatical interpretation of the clustering result by mapping the natural hierarchical organized subspace clusters with significant categorical enrichment onto the ontology hierarchy. our experiments on a set of gene expression data using gene ontology demonstrate that our pruning technique driven by ontology significantly improve the clustering performance with minimal degradation of the cluster quality. meanwhile, many hierarchical organizations of gene clusters corresponding to a sub-hierarchies in gene ontology were also successfully captured.
the ioc algorithm: efficient many-class non-parametric classification for high-dimensional data. this paper is about a variant of k nearest neighbor classification on large many-class high dimensional datasets.k nearest neighbor remains a popular classification technique, especially in areas such as computer vision, drug activity prediction and astrophysics. furthermore, many more modern classifiers, such as kernel-based bayes classifiers or the prediction phase of svms, require computational regimes similar to k-nn. we believe that tractable k-nn algorithms therefore continue to be important.this paper relies on the insight that even with many classes, the task of finding the majority class among the k nearest neighbors of a query need not require us to explicitly find those k nearest neighbors. this insight was previously used in (liu et al., 2003) in two algorithms called kns2 and kns3 which dealt with fast classification in the case of two classes. in this paper we show how a different approach, ioc (standing for the international olympic committee) can apply to the case of n classes where n > 2.ioc assumes a slightly different processing of the datapoints in the neighborhood of the query. this allows it to search a set of metric trees, one for each class. during the searches it is possible to quickly prune away classes that cannot possibly be the majority.we give experimental results on datasets of up to 5.8 x 105 records and 1.5 x 103 attributes, frequently showing an order of magnitude acceleration compared with each of (i) conventional linear scan, (ii) a well-known independent sr-tree implementation of conventional k-nn and (iii) a highly optimized conventional k-nn metric tree search.
rule interestingness analysis using olap operations. the problem of interestingness of discovered rules has been investigated by many researchers. the issue is that data mining algorithms often generate too many rules, which make it very hard for the user to find the interesting ones. over the years many techniques have been proposed. however, few have made it to real-life applications. since august 2004, we have been working on a major application for motorola. the objective is to find causes of cellular phone call failures from a large amount of usage log data. class association rules have been shown to be suitable for this type of diagnostic data mining application. we were also able to put several existing interestingness methods to the test, which revealed some major shortcomings. one of the main problems is that most existing methods treat rules individually. however, we discovered that users seldom regard a single rule to be interesting by itself. a rule is only interesting in the context of some other rules. furthermore, in many cases, each individual rule may not be interesting, but a group of them together can represent an important piece of knowledge. this led us to discover a deficiency of the current rule mining paradigm. using non-zero minimum support and non-zero minimum confidence eliminates a large amount of context information, which makes rule analysis difficult. this paper proposes a novel approach to deal with all of these issues, which casts rule analysis as olap operations and general impression mining. this approach enables the user to explore the knowledge space to find useful knowledge easily and systematically. it also provides a natural framework for visualization. as an evidence of its effectiveness, our system, called opportunity map, based on these ideas has been deployed, and it is in daily use in motorola for finding actionable knowledge from its engineering and other types of data sets.
clustering pair-wise dissimilarity data into partially ordered sets. ontologies represent data relationships as hierarchies of possibly overlapping classes. ontologies are closely related to clustering hierarchies, and in this article we explore this relationship in depth. in particular, we examine the space of ontologies that can be generated by pairwise dissimilarity matrices. we demonstrate that classical clustering algorithms, which take dissimilarity matrices as inputs, do not incorporate all available information. in fact, only special types of dissimilarity matrices can be exactly preserved by previous clustering methods. we model ontologies as a partially ordered set (poset) over the subset relation. in this paper, we propose a new clustering algorithm, that generates a partially ordered set of clusters from a dissimilarity matrix.
fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams. patterns of contrast are a very important way of comparing multi-dimensional datasets. such patterns are able to capture regions of high difference between two classes of data, and are useful for human experts and the construction of classifiers. however, mining such patterns is particularly challenging when the number of dimensions is large. this paper describes a new technique for mining several varieties of contrast pattern, based on the use of zero-suppressed binary decision diagrams (zbdds), a powerful data structure for manipulating sparse data. we study the mining of both simple contrast patterns, such as emerging patterns, and more novel and complex contrasts, which we call disjunctive emerging patterns. a performance study demonstrates our zbdd technique is highly scalable, substantially improves on state of the art mining for emerging patterns and can be effective for discovering complex contrasts from datasets with thousands of attributes.
unsupervised learning on k-partite graphs. various data mining applications involve data objects of multiple types that are related to each other, which can be naturally formulated as a k-partite graph. however, the research on mining the hidden structures from a k-partite graph is still limited and preliminary. in this paper, we propose a general model, the relation summary network, to find the hidden structures (the local cluster structures and the global community structures) from a k-partite graph. the model provides a principal framework for unsupervised learning on k-partite graphs of various structures. under this model, we derive a novel algorithm to identify the hidden structures of a k-partite graph by constructing a relation summary network to approximate the original k-partite graph under a broad range of distortion measures. experiments on both synthetic and real datasets demonstrate the promise and effectiveness of the proposed model and algorithm. we also establish the connections between existing clustering approaches and the proposed model to provide a unified view to the clustering approaches.
co-clustering by block value decomposition. dyadic data matrices, such as co-occurrence matrix, rating matrix, and proximity matrix, arise frequently in various important applications. a fundamental problem in dyadic data analysis is to find the hidden block structure of the data matrix. in this paper, we present a new co-clustering framework, block value decomposition(bvd), for dyadic data, which factorizes the dyadic data matrix into three components, the row-coefficient matrix r, the block value matrix b, and the column-coefficient matrix c. under this framework, we focus on a special yet very popular case -- non-negative dyadic data, and propose a specific novel co-clustering algorithm that iteratively computes the three decomposition matrices based on the multiplicative updating rules. extensive experimental evaluations also demonstrate the effectiveness and potential of this framework as well as the specific algorithms for co-clustering, and in particular, for discovering the hidden block structure in the dyadic data.
adversarial learning. many classification tasks, such as spam filtering, intrusion detection, and terrorism detection, are complicated by an adversary who wishes to avoid detection. previous work on adversarial classification has made the unrealistic assumption that the attacker has perfect knowledge of the classifier [2]. in this paper, we introduce the adversarial classifier reverse engineering (acre) learning problem, the task of learning sufficient information about a classifier to construct adversarial attacks. we present efficient algorithms for reverse engineering linear classifiers with either continuous or boolean features and demonstrate their effectiveness using real data from the domain of spam filtering.
learning nonstationary models of normal network traffic for detecting novel attacks. traditional intrusion detection systems (ids) detect attacks by comparing current behavior to signatures of known attacks. one main drawback is the inability of detecting new attacks which do not have known signatures. in this paper we propose a learning algorithm that constructs models of normal behavior from attack-free network traffic. behavior that deviates from the learned normal model signals possible novel attacks. our ids is unique in two respects. first, it is nonstationary, modeling probabilities based on the time since the last event rather than on average rate. this prevents alarm floods. second, the ids learns protocol vocabularies (at the data link through application layers) in order to detect unknown attacks that attempt to exploit implementation errors in poorly tested features of the target software. on the 1999 darpa ids evaluation data set [9], we detect 70 of 180 attacks (with 100 false alarms), about evenly divided between user behavioral anomalies (ip addresses and ports, as modeled by most other systems) and protocol anomalies. because our methods are unconventional there is a significant non-overlap of our ids with the original darpa participants, which implies that they could be combined to increase coverage.
tensor-cur decompositions for tensor-based data. motivated by numerous applications in which the data may be modeled by a variable subscripted by three or more indices, we develop a tensor-based extension of the matrix cur decomposition. the tensor-cur decomposition is most relevant as a data analysis tool when the data consist of one mode that is qualitatively different than the others. in this case, the tensor-cur decomposition approximately expresses the original data tensor in terms of a basis consisting of underlying subtensors that are actual data elements and thus that have natural interpretation in terms ofthe processes generating the data. in order to demonstrate the general applicability of this tensor decomposition, we apply it to problems in two diverse domains of data analysis: hyperspectral medical image analysis and consumer recommendation system analysis. in the hyperspectral data application, the tensor-cur decomposition is used to compress the data, and we show that classification quality is not substantially reduced even after substantial data compression. in the recommendation system application, the tensor-cur decomposition is used to reconstruct missing entries in a user-product-product preference tensor, and we show that high quality recommendations can be made on the basis of a small number of basis users and a small number of product-product comparisons from a new user.