waashk/dblp huggingface dataset:
detecting graph-based spatial outliers: algorithms and applications (a summary of results). identification of outliers can lead to the discovery of unexpected, interesting, and useful knowledge. existing methods are designed for detecting spatial outliers in multidimensional geometric data sets, where a distance metric is available. in this paper, we focus on detecting spatial outliers in graph structured data sets. we define statistical tests, analyze the statistical foundation underlying our approach, design several fast algorithms to detect spatial outliers, and provide a cost model for outlier detection procedures. in addition, we provide experimental results from the application of our algorithms on a minneapolis-st.paul(twin cities) traffic dataset to show their effectiveness and usefulness.
experimental study of discovering essential information from customer inquiry. this paper reports the result of our experimental study on a new method of applying an association rule miner to discover useful information from customer inquiry database in a call center of a company. it has been claimed that association rule mining is not suited for text mining. to overcome this problem, we propose (1) to generate sequential data set of words with dependency structure from the japanese text database, and (2) to employ a new method for extracting meaningful association rules by applying a new rule selection criterion. each inquiry in the sequential data was represented as a list of word pairs, each of which consists of a verb and its dependent noun. the association rules were induced regarding each pair of words as an item. the rule selection criterion comes from our principle that we put heavier weights to co-occurrence of multiple items more than single item occurrence. we regarded a rule important if the existence of the items in the rule body significantly affects the occurrence of the item in the rule head. the selected rules were then categorized to form meaningful information classes. with this method, we succeeded in extracting useful information classes from the text database, which were not acquired by only simple keyword retrieval. also, inquiries with multiple aspects were properly classified into corresponding multiple categories.
probabilistic workflow mining. in several organizations, it has become increasingly popular to document and log the steps that makeup a typical business process. in some situations, a normative workflow model of such processes is developed, and it becomes important to know if such a model is actually being followed by analyzing the available activity logs. in other scenarios, no model is available and, with the purpose of evaluating cases or creating new production policies, one is interested in learning a workflow representation of such activities. in either case, machine learning tools that can mine workflow models are of great interest and still relatively unexplored. we present here a probabilistic workflow model and a corresponding learning algorithm that runs in polynomial time. we illustrate the algorithm on example data derived from a real world workflow.
a bayesian network framework for reject inference. most learning methods assume that the training set is drawn randomly from the population to which the learned model is to be applied. however in many applications this assumption is invalid. for example, lending institutions create models of who is likely to repay a loan from training sets consisting of people in their records to whom loans were given in the past; however, the institution approved loan applications previously based on who was thought unlikely to default. learning from only approved loans yields an incorrect model because the training set is a biased sample of the general population of applicants. the issue of including rejected samples in the learning process, or alternatively using rejected samples to adjust a model learned from accepted samples only, is called reject inference.the main contribution of this paper is a systematic analysis of different cases that arise in reject inference, with explanations of which cases arise in various real-world situations. we use bayesian networks to formalize each case as a set of conditional independence relationships and identify eight cases, including the familiar missing completely at random (mcar), missing at random (mar), and missing not at random (mnar) cases. for each case we present an overview of available learning algorithms. these algorithms have been published in separate fields of research, including epidemiology, econometrics, clinical trial evaluation, sociology, and credit scoring; our second major contribution is to describe these algorithms in a common framework.
modeling and predicting personal information dissemination behavior. in this paper, we propose a new way to automatically model and predict human behavior of receiving and disseminating information by analyzing the contact and content of personal communications. a personal profile, called communitynet, is established for each individual based on a novel algorithm incorporating contact, content, and time information simultaneously. it can be used for personal social capital management. clusters of communitynets provide a view of informal networks for organization management. our new algorithm is developed based on the combination of dynamic algorithms in the social network field and the semantic content classification methods in the natural language processing and machine learning literatures. we tested communitynets on the enron email corpus and report experimental results including filtering, prediction, and recommendation capabilities. we show that the personal behavior and intention are somewhat predictable based on these models. for instance, "to whom a person is going to send a specific email" can be predicted by one's personal social network and content analysis. experimental results show the prediction accuracy of the proposed adaptive algorithm is 58% better than the social network-based predictions, and is 75% better than an aggregated model based on latent dirichlet allocation with social network enhancement. two online demo systems we developed that allow interactive exploration of communitynet are also discussed.
evaluating similarity measures: a large-scale study in the orkut social network. online information services have grown too large for users to navigate without the help of automated tools such as collaborative filtering, which makes recommendations to users based on their collective past behavior. while many similarity measures have been proposed and individually evaluated, they have not been evaluated relative to each other in a large real-world environment. we present an extensive empirical comparison of six distinct measures of similarity for recommending online communities to members of the orkut social network. we determine the usefulness of the different recommendations by actually measuring users' propensity to visit and join recommended communities. we also examine how the ordering of recommendations influenced user selection, as well as interesting social issues that arise in recommending communities within a real social network.
monic: modeling and monitoring cluster transitions. there is much recent work on detecting and tracking change in clusters, often based on the study of the spatiotemporal properties of a cluster. for the many applications where cluster change is relevant, among them customer relationship management, fraud detection and marketing, it is also necessary to provide insights about the nature of cluster change: is a cluster corresponding to a group of customers simply disappearing or are its members migrating to other clusters? is a new emerging cluster reflecting a new target group of customers or does it rather consist of existing customers whose preferences shift? to answer such questions, we propose the framework monic for modeling and tracking of cluster transitions. our cluster transition model encompasses changes that involve more than one cluster, thus allowing for insights on cluster change in the whole clustering. our transition tracking mechanism is not based on the topological properties of clusters, which are only available for some types of clustering, but on the contents of the underlying data stream. we present our first results on monitoring cluster transitions over the acm digital library.
generating english summaries of time series data using the gricean maxims. we are developing technology for generating english textual summaries of time-series data, in three domains: weather forecasts, gas-turbine sensor readings, and hospital intensive care data. our weather-forecast generator is currently operational and being used daily by a meteorological company. we generate summaries in three steps: (a) selecting the most important trends and patterns to communicate; (b) mapping these patterns onto words and phrases; and (c) generating actual texts based on these words and phrases. in this paper we focus on the first step, (a), selecting the information to communicate, and describe how we perform this using modified versions of standard data analysis algorithms such as segmentation. the modifications arose out of empirical work with users and domain experts, and in fact can all be regarded as applications of the gricean maxims of quality, quantity, relevance, and manner, which describe how a cooperative speaker should behave in order to help a hearer correctly interpret a text. the gricean maxims are perhaps a key element of adapting data analysis algorithms for effective communication of information to human users, and should be considered by other researchers interested in communicating data to human users.
self-organizing wireless sensor networks in action. wireless sensor networks (wsn) composed of large numbers of small devices that self-organize are being investigated for a wide variety of applications. two key advantages of these networks over more traditional sensor networks are that they can be dynamically and quickly deployed, and that they can provide fine-grained sensing. applications, such as emergency response to natural or manmade disasters, detection and tracking, and fine grained sensing of the environment are key examples of applications that can benefit from these types of wsn. current research for these systems is widespread. however, many of the proposed solutions are developed with simplifying assumptions about wireless communication and the environment, even though the realities of wireless communication and environmental sensing are well known. many of the solutions are evaluated only by simulation. in this talk i describe a fully implemented system consisting of a suite of more than 30 synthesized protocols. the system supports a power aware surveillance, tracking and classification application running on 203 xsm motes and evaluated in a realistic, large-area environment. technical details and evaluations are presented. i end with a discussion of opportunities and problems for data mining related to wsn.
support envelopes: a technique for exploring the structure of association patterns. this paper introduces support envelopes---a new tool for analyzing association patterns---and illustrates some of their properties, applications, and possible extensions. specifically, the support envelope for a transaction data set and a specified pair of positive integers (m,n) consists of the items and transactions that need to be searched to find any association pattern involving m or more transactions and n or more items. for any transaction data set with m transactions and n items, there is a unique lattice of at most m*n support envelopes that captures the structure of the association patterns in that data set. because support envelopes are not encumbered by a support threshold, this support lattice provides a complete view of the association structure of the data set, including association patterns that have low support. furthermore, the boundary of the support lattice---the support boundary---has at most min(m,n) envelopes and is especially interesting since it bounds the maximum sizes of potential association patterns---not only for frequent, closed, and maximal itemsets, but also for patterns, such as error-tolerant itemsets, that are more general. the association structure can be represented graphically as a two-dimensional scatter plot of the (m,n) values associated with the support envelopes of the data set, a feature that is useful in the exploratory analysis of association patterns. finally, the algorithm to compute support envelopes is simple and computationally efficient, and it is straightforward to parallelize the process of finding all the support envelopes.
discovery of climate indices using clustering. to analyze the effect of the oceans and atmosphere on land climate, earth scientists have developed climate indices, which are time series that summarize the behavior of selected regions of the earth's oceans and atmosphere. in the past, earth scientists have used observation and, more recently, eigenvalue analysis techniques, such as principal components analysis (pca) and singular value decomposition (svd), to discover climate indices. however, eigenvalue techniques are only useful for finding a few of the strongest signals. furthermore, they impose a condition that all discovered signals must be orthogonal to each other, making it difficult to attach a physical interpretation to them. this paper presents an alternative clustering-based methodology for the discovery of climate indices that overcomes these limitiations and is based on clusters that represent regions with relatively homogeneous behavior. the centroids of these clusters are time series that summarize the behavior of the ocean or atmosphere in those regions. some of these centroids correspond to known climate indices and provide a validation of our methodology; other centroids are variants of known indices that may provide better predictive power for some land areas; and still other indices may represent potentially new earth science phenomena. finally, we show that cluster based indices generally outperform svd derived indices, both in terms of area weighted correlation and direct correlation with the known indices.
generalizing the notion of support. the goal of this paper is to show that generalizing the notion of support can be useful in extending association analysis to non-traditional types of patterns and non-binary data. to that end, we describe a framework for generalizing support that is based on the simple, but useful observation that support can be viewed as the composition of two functions: a function that evaluates the strength or presence of a pattern in each object (transaction) and a function that summarizes these evaluations with a single number. a key goal of any framework is to allow people to more easily express, explore, and communicate ideas, and hence, we illustrate how our support framework can be used to describe support for a variety of commonly used association patterns, such as frequent itemsets, general boolean patterns, and error-tolerant itemsets. we also present two examples of the practical usefulness of generalized support. one example shows the usefulness of support functions for continuous data. another example shows how the hyperclique pattern---an association pattern originally defined for binary data---can be extended to continuous data by generalizing a support function.
probabilistic author-topic models for information discovery. we propose a new unsupervised learning technique for extracting information from large text collections. we model documents as if they were generated by a two-stage stochastic process. each author is represented by a probability distribution over topics, and each topic is represented as a probability distribution over words for that topic. the words in a multi-author paper are assumed to be the result of a mixture of each authors' topic mixture. the topic-word and author-topic distributions are learned from data in an unsupervised manner using a markov chain monte carlo algorithm. we apply the methodology to a large corpus of 160,000 abstracts and 85,000 authors from the well-known citeseer digital library, and learn a model with 300 topics. we discuss in detail the interpretation of the results discovered by the system including specific topic and author models, ranking of authors by topic and topics by author, significant trends in the computer science literature between 1990 and 2002, parsing of abstracts by topics and authors and detection of unusual papers by specific authors. an online query interface to the model is also discussed that allows interactive exploration of author-topic models for corpora such as citeseer.
query, analysis, and visualization of hierarchically structured data using polaris. in the last several years, large olap databases have become common in a variety of applications such as corporate data warehouses and scientific computing. to support interactive analysis, many of these databases are augmented with hierarchical structures that provide meaningful levels of abstraction that can be leveraged by both the computer and analyst. this hierarchical structure generates many challenges and opportunities in the design of systems for the query, analysis, and visualization of these databases.in this paper, we present an interactive visual exploration tool that facilitates exploratory analysis of data warehouses with rich hierarchical structure, such as might be stored in data cubes. we base this tool on polaris, a system for rapidly constructing table-based graphical displays of multidimensional databases. polaris builds visualizations using an algebraic formalism derived from the interface and interpreted as a set of queries to a database. we extend the user interface, algebraic formalism, and generation of data queries in polaris to expose and take advantage of hierarchical structure. in the resulting system, analysts can navigate through the hierarchical projections of a database, rapidly and incrementally generating visualizations for each projection.
exploiting response models: optimizing cross-sell and up-sell opportunities in banking. the banking industry regularly mounts campaigns to improve customer value by offering new products to existing customers. in recent years this approach has gained significant momentum because of the increasing availability of customer data and the improved analysis capabilities in data mining. typically, response models based on historical data are used to estimate the probability of a customer purchasing an additional product and the expected return from that additional purchase. even with these computational improvements and accurate models of customer behavior, the problem of efficiently using marketing resources to maximize the return on marketing investment is a challenge. this problem is compounded because of the capability to launch multiple campaigns through several distribution channels over multiple time periods. the combination of alternatives creates a complicated array of possible actions. this paper presents a solution that answers the question of what products, if any, to offer to each customer in a way that maximizes the marketing return on investment. the solution is an improvement over the usual approach of picking the customers that have the largest expected value for a particular product because it is a global maximization from the viewpoint of the bank and allows for the effective implementation of business constraints across customers and business units. the approach accounts for limited resources, multiple sequential campaigns, and other business constraints. furthermore, the solution provides insight into the cost of these constraints, in terms of decreased profits, and thus is an effective tool for both tactical campaign execution and strategic planning.
a streaming ensemble algorithm (sea) for large-scale classification. ensemble methods have recently garnered a great deal of attention in the machine learning community. techniques such as boosting and bagging have proven to be highly effective but require repeated resampling of the training data, making them inappropriate in a data mining context. the methods presented in this paper take advantage of plentiful data, building separate classifiers on sequential chunks of training points. these classifiers are combined into a fixed-size ensemble using a heuristic replacement strategy. the result is a fast algorithm for large-scale or streaming data that classifies as well as a single decision tree built on all the data, requires approximately constant memory, and adjusts quickly to concept drift.
combining linguistic and statistical analysis to extract relations from web documents. the world wide web provides a nearly endless source of knowledge, which is mostly given in natural language. a first step towards exploiting this data automatically could be to extract pairs of a given semantic relation from text documents - for example all pairs of a person and her birthdate. one strategy for this task is to find text patterns that express the semantic relation, to generalize these patterns, and to apply them to a corpus to find new pairs. in this paper, we show that this approach profits significantly when deep linguistic structures are used instead of surface text patterns. we demonstrate how linguistic structures can be represented for machine learning, and we provide a theoretical analysis of the pattern matching approach. we show the benefits of our approach by extensive experiments with our prototype system leila.
beyond streams and graphs: dynamic tensor analysis. how do we find patterns in author-keyword associations, evolving over time? or in data cubes, with product-branch-customer sales information? matrix decompositions, like principal component analysis (pca) and variants, are invaluable tools for mining, dimensionality reduction, feature selection, rule identification in numerous settings like streaming data, text, graphs, social networks and many more. however, they have only two orders, like author and keyword, in the above example.we propose to envision such higher order data as tensors,and tap the vast literature on the topic. however, these methods do not necessarily scale up, let alone operate on semi-infinite streams. thus, we introduce the dynamic tensor analysis (dta) method, and its variants. dta provides a compact summary for high-order and high-dimensional data, and it also reveals the hidden correlations. algorithmically, we designed dta very carefully so that it is (a) scalable, (b) space efficient (it does not need to store the past) and (c) fully automatic with no need for user defined parameters. moreover, we propose sta, a streaming tensor analysis method, which provides a fast, streaming approximation to dta.we implemented all our methods, and applied them in two real settings, namely, anomaly detection and multi-way latent semantic indexing. we used two real, large datasets, one on network flow data (100gb over 1 month) and one from dblp (200mb over 25 years). our experiments show that our methods are fast, accurate and that they find interesting patterns and outliers on the real datasets.
a hybrid unsupervised approach for document clustering. we propose a hybrid, unsupervised document clustering approach that combines a hierarchical clustering algorithm with expectation maximization. we developed several heuristics to automatically select a subset of the clusters generated by the first algorithm as the initial points of the second one. furthermore, our initialization algorithm generates not only an initial model for the iterative refinement algorithm but also an estimate of the model dimension, thus eliminating another important element of human supervision. we have evaluated the proposed system on five real-world document collections. the results show that our approach generates clustering solutions of higher quality than both its individual components.