Most existing research on authorship attribution uses various lexical, syntactic and semantic features. In this paper we demonstrate an effective template-based approach for combining various syntactic features of a document for authorship analysis. The parse-tree based features that we propose are independent of the topic of a document and reflect the innate writing styles of authors. We show that the use of templates including sub-trees of parse trees in conjunction with other syntactic features result in improved author attribution rates. Another contribution is the demonstration that Dempster’s rule based combination of evidence from syntactic features performs better than other evidence-combination methods. We also demonstrate that our methodology works well for the case where actual author is not included in the candidate author set.

Core periphery structure is a meso-scale property of complex networks. Core periphery structures can help identify the relationships between cohesive core clusters surrounded by sparse peripheries. The knowledge about such relationships can have many practical applications in real world complex networks. For example, in a web based network between all blogs on different topics, peripheries connecting popular groups could help in the study of flow of information across the web. In this paper, we propose a construction of core periphery structures for weighted graphs. We present a greedy growth based algorithm to extract core periphery structures in weighted graphs. We also score the core periphery associations as a measure of distance between them. Through extensive experimentation using two synthetic and two real world Protein-Protein Interaction (PPI) networks, we demonstrate the usefulness of core periphery structures over simple overlapping clusters obtained by a state of the art clustering algorithm called ClusterONE.

The problem of discovering all formal concepts embedded in a binary relational dataset is of significant interest for many data analysis and processing problems. The problem of enumerating all concepts for a dataset is known to be NP-hard. A number of Map-Reduce based algorithms have been developed to conquer the difficulty of processing large datasets. But these algorithms are not very scalable because at core all these algorithms stick to a DFS based sequential search for individual concepts, applying Map-Reduce formalism to parallelize the processing at nodes of the DFS tree. We have present here a completely different and Map-Reduce based formulation for parallelizing the concept discovery problem. One major difference of our approach is that we seek to find a sufficient set of concepts only, and this sufficient set can be used to generate all other concepts in the lattice. This formulation is not very suitable for sequential execution but adapts extremely well to the parallel environments based on Map-Reduce operators. We show in this paper that our algorithm is significantly faster than all the known Map-reduce formulations for discovering concepts in binary relational datasets. We have presented in this paper the outline of the theoretical foundations for our algorithm and empirical tests with a number of benchmarking datasets. We also show that the computationally very difficult problem of finding 3-clusters in pairs of binary relational datasets can also be made very efficient by our formulation.

In many emerging data mining situations we encounter multiple large binary relational datasets that are generated independently but are semantically interconnected and must be mined simultaneously to obtain an integrated effect of the data residing in all of them. The idea of finding 3-clusters is increasingly used in situations where one has to concurrently mine two distinct datasets that share a common domain along a dimension. By discovering 3-clusters, one can obtain important insights on the underlying connections between the objects of different domains. All the 3-clustering algorithms for binary datasets presented till now are able to find 3-clusters where the two distinct bi-clusters in a 3-cluster are strict, that is, the rectangle formed by the bi-clusters contains only `1' entries. However, in many real world applications the datasets are very sparse and finding a relaxed bi-cluster, that allows some zeros in the bi-clusters' rectangles, is very valuable. In this paper, we present a novel search based algorithm that finds relaxed 3-clusters from two binary datasets that share a domain. Each identified 3-cluster involves two relaxed bi-clusters whose overlap in the sets of objects is maximal. Through our algorithm, we are also able to exert finer control over the percentage of 1 s allowed in each of the bi-clusters. We validate the effectiveness of our algorithm by using synthetic and real binary datasets from different domains. Our results show that our notion of 3-cluster is able to produce more meaningful results when compared to 3-clusters with strict requirement of all ones.

Prediction of a spindle's health is of critical significance in a manufacturing environment. Unexpected breakdowns in a spindles functioning can lead to high costs and production delays. Therefore, developing methods which can predict the time-to-failure of a spindle and its bearings can be of significant importance. One of the main challenges for successful prediction by a purely data-driven techniques is the management and analysis of a huge volume of spindle's monitored operational data. In this paper, we build a regression and clustering based prediction methodology, suitable for exploiting very high volumes of monitored data, for a spindle's time-to-failure prediction. We conquer the problem of dealing with huge volumes of monitored data by aggregating features related to spindle vibration acceleration in the frequency domain for 24-72 hour windows of time. A Fast Fourier Transform analysis of the spindle vibration and angular acceleration data is used to extract twelve aggregated frequency domain features to train regression models. Further, a graph clustering algorithm is used to improve the feature selection and thus the accuracy of the predictions. Once the model is trained, it can be used to make predictions based upon energy bursts observed over 24-72 hour windows. This can prove to be very useful as a cost effective prognostic tool that can be easily deployed in the manufacturing industry. The spindle data used in the paper has been collected at Techsolve Inc. over three run-to-failure experiments performed on a spindle test-bed. In this paper, we present our model-building methodology along with an experimental setup and empirical evaluation of the prediction models and results.

Most existing methods for clustering temporal data are based on either a strict similarity metric or a precisely defined temporal profile such as a sine, exponential wave etc. Also, these methods compute similarity metric across the entire time-span of the objects. However these types of temporal patterns are more useful in many biological analysis, where it is important to observe gene expression pattens across arbitrary subintervals. These types of temporal patterns are very useful in bioinformatics, where it is important to observe gene expression pattens across arbitrary subintervals. In this paper we present an algorithm for searching for multiple contiguous temporal subintervals within which the selected objects demonstrate existence of clear patterns. We demonstrate the power and advantages of our algorithm by using a synthetic dataset and a pharmacokinetics dataset for which other researchers have recently published their results. We compare and contrast our results with these results to show superiority of our approach.

Heterogeneous information networks are pervasive in applications ranging from bioinformatics to e-commerce. As a result, unsupervised learning and clustering methods pertaining to such networks have gained significant attention recently. Nodes in a heterogeneous information network are regarded as objects derived from distinct domains such as 'authors' and 'papers'. In many cases, feature sets characterizing the objects are not available, hence, clustering of the objects depends solely on the links and relationships amongst objects. Although several previous studies have addressed information network clustering, shortcomings remain. First, the definition of what constitutes an information network cluster varies drastically from study to study. Second, previous algorithms have generally focused on non-overlapping clusters, while many algorithms are also limited to specific network topologies. In this paper we introduce a game theoretic framework (GHIN) for defining and mining clusters in heterogeneous information networks. The clustering problem is modeled as a game wherein each domain represents a player and clusters are defined as the Nash equilibrium points of the game. Adopting the abstraction of Nash equilibrium points as clusters allows for flexible definition of reward functions that characterize clusters without any modification to the underlying algorithm. We prove that well-established definitions of clusters in 2-domain information networks such as formal concepts, maximal bi-cliques, and noisy binary tiles can always be represented as Nash equilibrium points. Moreover, experimental results employing a variety of reward functions and several real world information networks illustrate that the GHIN framework produces more accurate and informative clusters than the recently proposed NetClus and state of the art MDC algorithms.

The concept of Triclusters has been investigated recently in the context of two relational datasets that share labels along one of the dimensions. By simultaneously processing two datasets to unveil triclusters, new useful knowledge and insights can be obtained. However, some recently reported methods are either closely linked to specific problems or constrain datasets to have some specific distributions. Algorithms for generating triclusters whose cell-values demonstrate simple well known statistical properties, such as upper bounds on standard deviations, are needed for many applications. In this paper we present a 3-Clustering algorithm that searches for meaningful combinations of biclusters in two related datasets. The algorithm can handle situations involving: (i) datasets in which a few data objects may be present in only one dataset and not in both datasets, (ii) the two datasets may have different numbers of objects and/or attributes, and (iii) the cell-value distributions in two datasets may be different. In our formulation the cell-values of each selected tricluster, formed by two independent biclusters, are such that the standard deviations in each bicluster obeys an upper bound and the sets of objects in the two biclusters overlap to the maximum possible extent. We present validation of our algorithm by presenting the properties of the 3-Clusters discovered from a synthetic dataset and from a real world cross-species genomic dataset. The results of our algorithm unveil interesting insights for the cross-species genomic domain.

Binary data occurs often in several real world applications ranging from social networks to bioinformatics. Extracting patterns from such data has been a focus of fundamental data mining tasks including association rule analysis, sequence mining and bi-clustering. Recently, the utility of banded structures in binary matrices has been pointed out with applications in paleontology, bioinformatics and social networking. A binary matrix has a banded structure if both the rows and columns can be permuted so that the 1's exhibit a staircase pattern down the rows, along the leading diagonal. In this paper we show the correspondence between bi-clustering and banded structures in matrices; and the mmbs (Mine Maximally Banded Sub-matrices) algorithm is presented as a direct result of this correspondence. The current state of the art algorithm, mbs, only allows for the discovery of a single band and assumes a fixed column permutation. On the other hand mmbs facilitates the discovery of multiple bands that may possibly be overlapping or segmented. Our experimental results, presented here, clearly indicate the advantage of mmbs over mbs with both, synthetic and real data sets.

In this paper we present an efficient algorithm for simultaneous traversal of concept lattices of two distinct but related binary datasets.

A fundamental task of data analysis is comprehending what distinguishes clusters found within the data. We present the problem of mining distinguishing sets which seeks to find sets of objects or attributes that induce that most change among the incremental bi-clusters of a binary dataset. Unlike emerging patterns and contrast sets which only focus on statistical differences between support of itemsets, our approach considers distinctions in both the attribute space and the object space. Viewing the lattice of bi-clusters formed within a data set as a weighted directed graph, we mine the most significant distinguishing sets by growing a maximal cost spanning tree of the lattice. In this paper we present a weighting function for measuring distinction among bi-clusters in the lattice and the novel MIDS algorithm. MIDS simultaneously enumerates bi-clusters, constructs the bi-cluster lattice, and computes the distinguishing sets. The efficient computational performance of MIDS is exhibited in a performance test on real world and benchmark data sets. The utility of distinguishing sets is also demonstrated with experiments on synthetic and real data.

It has been said that the only constant in life is change. This rule can also be directly applied to the lives of organizations. Any organization of non-trivial size, scope, life expectancy or function, is destined to change. An organization without

Conventional clustering algorithms group similar data points together along one dimension of a data table. Bi-clustering simultaneously clusters both dimensions of a data table. 3-clustering goes one step further and aims to concurrently cluster two data tables that share a common set of row labels, but whose column labels are distinct. Such clusters reveal the underlying connections between the elements of all three sets. We present a novel algorithm that discovers 3-clusters across vertically partitioned data. Our approach presents two new and important formulations: first we introduce the notion of a 3-cluster in partitioned data; and second we present a mathematical formulation that measures the quality of such clusters. Our algorithm discovers high quality, arbitrarily positioned, overlapping clusters, and is efficient in time. These results are exhibited in a comprehensive study on real datasets.

A fundamental task of data analysis is comprehending what distinguishes clusters found within the data. We present the problem of mining distinguishing sets; which seeks to find sets of objects or attributes that induce the most incremental change between adjacent bi-clusters of a binary dataset. Viewing the lattice of bi-clusters formed within a data set as a weighted directed graph, we mine the most significant distinguishing sets by growing a maximal-cost spanning tree of the lattice.

A major challenge in building recommender systems is organizing the recommendation space since, the underlying data organization scheme has a significant impact on the overall performance and capabilities of the recommender system. Lattices offer a natural scheme to encode the recommender space, and their structural properties could be leveraged to efficiently retrieve recommendations. In our lattice-based approach, we present a generic framework and algorithms for building recommender systems. The algorithms convert user ratings into concepts; organize concepts into coherent lattices by imposing constraints based on collaborative filtering, and enable fast querying of lattices for generating recommendations. A lattice-based model also offers interesting insights into the complex higher-level interrelationships between entities in the data. We apply our algorithms on two real-world datasets and demonstrate their capabilities in generating quality recommendations in real-time.

Identification of short repeated patterns (motifs) in genomic sequences is the key to many problems in bioinformatics. The promoter regions of genes are an important target of search for such motifs (transcription factor binding sites). We present a new algorithm, Mortice, for detecting potential binding sites which are present in a given set of genomic sequences. An informed search is performed by organizing the input patterns and their variants in a graph. Such a strategy efficiently leads to the desired solutions. The background is modeled as a Markov process and a composite score function is used. We demonstrate the performance of our algorithm by testing it on real-life data sets from yeast and human promoter sequences. We compared the performance with several popular algorithms and found that other algorithms work well with lower organisms like yeast but only a couple of them work well with human data. We show that our algorithm scales linearly with the size of input dataset. We compare the computational efficiency of our algorithm with other algorithms and show that it performs faster for different datasets and motif sizes

We consider the problem of mining multivariate time series data for discovering (i) frequently occurring substring patterns in a dimension, (ii) temporal associations among these substring patterns within or across different dimensions, and (iii) large intervals that sustain a particular mode of operation. These represent patterns at three different levels of abstraction for a dataset having very fine granularity. Discovery of such temporal associations in a multivariate setting provides useful insights which results in a prediction and diagnostic capability for the domain. In this paper we present a methodology for efficiently discovering all frequent patterns in each dimension of the data using Suffix Trees; then clustering these substring patterns to construct equivalence classes of similar (approximately matching) patterns; and then searching for temporal dependencies among these equivalence classes using an efficient search algorithm. Modes of operation are then inferred as summarization of these temporal dependencies. Our method is generalizable, scalable, and can be adapted to provide robustness against noise, shifting, and scaling factors

We present a search algorithm for mining closed sets in high dimensional binary datasets. Our algorithm is designed for dense datasets, where the percentage of 1's in the dataset is usually higher than 10%, and the total number of closed sets is much larger than the number of objects in the dataset. Our algorithm is memory efficient since, unlike many other closed set mining algorithms, it does not require all patterns mined so far to be kept in the memory. Optimization techniques are introduced in this paper, and we also present a parallel version of our algorithm.

Streaming data may consist of multiple drifting concepts each having its own underlying data distribution. We present an ensemble learning based approach to handle the data streams having multiple underlying modes. We build a global set of classifiers from sequential data chunks; ensembles are then selected from this global set of classifiers, and new classifiers created if needed, to represent the current concept in the stream. The system is capable of performing any-time classification and to detect concept drift in the stream. In streaming data historic concepts are likely to reappear so we don't delete any of the historic classifiers. Instead, we judiciously select only pertinent classifiers from the global set while forming the ensemble set for a classification task.

Identification of transcription factor binding site in DNA sequences is a frequently performed task in bioinformatics. However, current methods of search produce a large number of false positives as these motifs are short and degenerate. We propose an implicit model of cooperative binding of transcription factors. We hypothesize that flanking regions of binding sites have a different composition compared to regions which do not have that binding site. Using statistically significant motifs in flanking region of true binding sites as features, we design a SVM classifier for discriminating true binding sites from false positives. We demonstrate the effectiveness of our method on a data set of experimentally verified p53 binding sites. We were able to obtain an overall accuracy of 80% and 76% on cross- validation and independent test set, respectively. By analyzing the features, we identified known as well as potentially new binding partners of p53.

We present an approach to computing the covariance matrix with federated databases. This is a useful tool in principal components analysis and other pattern recognition methodologies. The databases are implicitly joined by a set of arbitrary shared attributes. We compute the covariance matrix exactly rather than an approximation. We show the correctness of the approach with minimal data exchanged. Each node shares the composition of the global result. We assume that the values for shared attributes are allowed to be shared. Each node is allowed to ask for information and it will be truthfully given the summary it requests. We provide no proof of theorems or lemmas due to lack of space.

No abstract available.

We present a levelwise search algorithm for finding subspace clusters in high dimensional data satisfying various properties besides the commonly used minimum density property. A set of such properties are summarized and a user can choose any of these properties. A lattice is built with all the discovered clusters which enables further analysis and discovery of useful knowledge about the clusters and their inter-relationships.

Most of the current subspace clustering methods find non-overlapping clusters of similar objects. We present a new subspace clustering algorithm that has two valuable capabilities not available in most of the current methods. First, it finds possibly overlapping subspace clusters; and second, it can discover clusters that preserve some user-specified interesting properties. Our methods build a lattice of these subspace clusters and it further enables discovery of meaningful linkage-chains in terms of objects or attributes among distant clusters. Our algorithm can be applied to graph data, social network data, and biological data to obtain a better understanding of the substructures inherent in the data space.

We present in this paper the problem of discovering sets of attribute-value pairs in high dimensional data sets that are of interest not because of co-occurrence alone, but due to their value in serving as cores for potential classifiers of clusters. We present our algorithm in the context of a gene-expression dataset. Gene expression data, in most situations, is insufficient for clustering algorithms and any statistical inference because for 6000+ genes, typically only 10s and at most 100s of data points become available. It is difficult to use statistical techniques to design a classifier for such immensely under-specified data. The observed data, though statistically, insufficient contains some information about the domain. Our goal is to discover as much information about all potential classifiers as possible from the data and then summarize this knowledge. This summarization provides insights into the composition of potential classifiers. We present here algorithms and methods for mining a high dimensional data set, exemplified by a gene expression data set, for mining such information.

We consider the problem of mining databases containing time series data for discovering typical temporal patterns. A gene micro-array database may contains temporal expression profiles of thousands of genes and it would be insightful to determine time intervals during which a number of genes share their expression levels. In another example temporal profiles of electricity consumption during a day are recorded and such records for a number of years may be stored in a database. Our goal is to determine typical temporal behaviors of utility consumption and the days on which such behaviors are expressed. An interesting temporal pattern is a subsequence of observed values that is shared by profiles in a reasonably large number of records.

In this paper we present a formal view of an ‘imagination’ type of hypothesis generation process performed with the probabilistic knowledge of a domain. We outline a formalism for focused construction of interesting hypothetical situation-descriptions. Our formalism for the ‘imagining agent’ seeks to construct consistent, minimal, and desirable situation-descriptions by selecting suitable domain attributes and probabilistic dependency relationships from the available domain knowledge. An interestingness criterion made available to the imagining agent helps it in focusing its efforts towards ‘imagining’ only the interesting situation-descriptions.

Different ways of representing probabilistic relationships among the attributes of a domain ar examined, and it is shown that the nature of domain relationships used in a representation affects the types of reasoning objectives that can be achieved. Two well-known formalisms for representing the probabilistic among attributes of a domain. These are the dependence tree formalism presented by C.K. Chow and C.N. Liu (1968) and the Bayesian networks methodology presented by J. Pearl (1986). An example is used to illustrate the nature of the relationships and the difference in the types of reasoning performed by these two representations. An abductive type of reasoning objective that requires use of the known qualitative relationships of the domain is demonstrated. A suitable way to represent such qualitative relationships along with the probabilistic knowledge is given, and how an explanation for a set of observed events may be constituted is discussed. An algorithm for learning the qualitative relationships from empirical data using an algorithm based on the minimization of conditional entropy is presented.>