Search

Extended Conflict-Based Search (XCBS) is a distributed agent-based approach which has been used for path finding and scheduling of spatially extended agents on a traversable network. The algorithm arrives at an optimal schedule while resolving conflicts between pairs of agents one at a time. In this chapter, we propose XCBS with Awareness wherein a conflicting agent plan is resolved with respect to the proposed route plan of other agents. The approach allows multiple conflicts to be resolved simultaneously, avoids cascading conflicts in the new plans and shows an improved efficiency in terms of nodes explored and time taken to arrive at the solution.

Measuring influence, through centrality measures, has been a center-piece of research in the analysis of complex social networks, such as finding coherent communities (clusters) and locating trend setters (prototypes) in viral marketing. Even though there exists a few axiomatic frameworks associated with some specific forms of influence measures in the literature, these formal frameworks are not generic in nature in terms of characterizing the space of influence measures for complex social networks. To address this research gap, we propose a generic axiomatic framework, in this paper, to capture most of the key intrinsic properties of any influence measure in networks. We further analyze certain popular centrality measures using this framework. Interestingly, our analysis reveals that none of the centrality measures considered satisfies all the desirable axioms. We finally conclude this paper by stating an appealing conjecture on a potential impossibility theorem associated with the proposed axiomatic framework.

Outlier detection is an important data mining task with many contemporary applications. Clustering based methods for outlier detection try to identify the data objects that deviate from the normal data. However, the uncertainty regarding the cluster membership of an outlier object has to be handled appropriately during the clustering process. Additionally, carrying out the clustering process on data described using categorical attributes is challenging, due to the difficulty in defining requisite methods and measures dealing with such data. Addressing these issues, a novel algorithm for clustering categorical data aimed at outlier detection is proposed here by modifying the standard $$k$$k-modes algorithm. The uncertainty regarding the clustering process is addressed by considering a soft computing approach based on rough sets. Accordingly, the modified clustering algorithm incorporates the lower and upper approximation properties of rough sets. The efficacy of the proposed rough $$k$$k-modes clustering algorithm for outlier detection is demonstrated using various benchmark categorical data sets.

Although clustering is one of the central tasks in machine learning for the last few decades, analysis of clustering irrespective of any particular algorithm was not undertaken for a long time. In the recent literature, axiomatic frameworks have been proposed for clustering and its quality. But none of the proposed frameworks has concentrated on the computational aspects of clustering, which is essential in current big data analytics. In this paper, we propose an axiomatic framework for clustering which considers both the quality and the computational complexity of clustering algorithms. The axioms proposed by us necessarily associate the problem of clustering with the important concept of incremental learning and divide and conquer learning. We also propose an order independent incremental clustering algorithm which satisfies all of these axioms in some constrained manner.

Outlier detection being an important data mining problem has attracted a lot of research interest in the recent past. As a result, various methods for outlier detection have been developed particularly for dealing with numerical data, whereas categorical data needs some attention. Addressing this requirement, we propose a two-phase algorithm for detecting outliers in categorical data based on a novel definition of outliers. In the first phase, this algorithm explores a clustering of the given data, followed by the ranking phase for determining the set of most likely outliers. The proposed algorithm is expected to perform better as it can identify different types of outliers, employing two independent ranking schemes based on the attribute value frequencies and the inherent clustering structure in the given data. Unlike some existing methods, the computational complexity of this algorithm is not affected by the number of outliers to be detected. The efficacy of this algorithm is demonstrated through experiments on various public domain categorical data sets.

We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

SIMULATED ANNEALING FOR SELECTING OPTIMAL INITIAL SEEDS IN THE K-MEANS ALGORITHM

Hybrid hierarchical clustering techniques which combine the characteristics of different partitional clustering techniques or partitional and hierarchical clustering techniques are interesting. In this paper, efficient bottom-up hybrid hierarchical clustering (BHHC) techniques have been proposed for the purpose of prototype selection for protein sequence classification. In the first stage, an incremental partitional clustering technique such as leader algorithm (ordered leader no update (OLNU) method) which requires only one database (db) scan is used to find a set of subcluster representatives. In the second stage, either a hierarchical agglomerative clustering (HAC) scheme or a partitional clustering algorithm-'K-medians' is used on these subcluster representatives to obtain a required number of clusters. Thus, this hybrid scheme is scalable and hence would be suitable for clustering large data sets and we also get a hierarchical structure consisting of clusters and subclusters and the representatives of which are used for pattern classification. Even if more number of prototypes are generated, classification time does not increase much as only a part of the hierarchical structure is searched. The experimental results (classification accuracy (CA) using the prototypes obtained and the computation time) of the proposed algorithms are compared with that of the hierarchical agglomerative schemes, K-medians and nearest neighbour classifier (NNC) methods. The proposed methods are found to be computationally efficient with reasonably good CA.

This paper introduces a novel incremental approach to clustering interval data. The method employs rough set theory to capture the inherent uncertainty involved in cluster analysis. Our experimental results show that it produces meaningful cluster abstractions for interval data at a minimal computational expense.

Synthetic pattern generation is one of the strategies to overcome the curse of dimensionality, but it has its own drawbacks. Most of the synthetic pattern generation techniques take more time than simple classification. In this paper, the authors propose a new strategy to reduce the time and memory requirements by applying prototyping as an intermediate step in the synthetic pattern generation technique. Results show that through the proposed strategy, classification can be done much faster without compromising much in terms of classification accuracy, in fact for some cases it gives better accuracy in lesser time. The classification time and accuracy can be balanced according to available memory and computing power of a system to get the best possible results.

This paper introduces a novel clustering scheme employing a combination of rough set theory and fuzzy set theory to generate meaningful abstractions from web access logs. Our experimental results show that the proposed scheme is capable of capturing the semantics involved in web access logs at an acceptable computational expense.

In this paper, an efficient hierarchical clustering algorithm, suitable for large data sets is proposed for effective clustering and prototype selection for pattern classification. It is another simple and efficient technique which uses incremental clustering principles to generate a hierarchical structure for finding the subgroups/subclusters within each cluster. As an example, a two level clustering algorithm--'Leaders-Subleaders', an extension of the leader algorithm is presented. Classification accuracy (CA) obtained using the representatives generated by the Leaders-Subleaders method is found to be better than that of using leaders as representatives. Even if more number of prototypes are generated, classification time is less as only a part of the hierarchical structure is searched.

Cluster analysis has been widely applied in many areas such as data mining, geographical data processing, medicine, classification of statistical findings in social studies and so on. Most ofthese domains deal with massive collections of data. Hence the methods to handle them must be efficient both in terms of the number of data set scans and memory usage.

This paper deals with the task of finding a set of prototypes from the training set. A reduced set is obtained which is used instead of the training set when nearest neighbour classification is used. Prototypes are added in an incremental fashion, where at each step of the algorithm, the number of prototypes selected keeps on increasing. The number of patterns in the training data classified correctly also keeps on increasing till all patterns are classified properly. After this, a deletion operator is used where some prototypes which are not so useful are removed. This method has been used to obtain the prototypes for a variety of benchmark data sets and results have been presented.

Many real world networks evolve over time indicating their dynamic nature to cope up with the changing real life scenarios. Detection of various categories of anomalies, also known as outliers, in graph representation of such network data is essential for discovering different irregular connectivity patterns with potential adverse effects such as intrusions into a computer network. Characterizing the behavior of such anomalies (outliers) during the evolution of the network over time is critical for their mitigation. In this context, a novel method for an effective characterization of network anomalies is proposed here by defining various categories of graph outliers depending on their temporal behavior noticeable across multiple instances of a network during its evolution. The efficacy of the proposed method is demonstrated through an experimental evaluation using various benchmark graph data sets.

Three stochastic search techniques have been used to find the optimal sequence of operations required to restore supply in an electrical distribution system on the occurrence of a fault. The three techniques are the genetic algorithm, simulated annealing and the tabu search. The performance of these techniques has been compared. A large distribution system of over 29 substations, 2500 nodes and 120 feeders has been used.

In classification of binary featured data, distance computation is carried out by considering each feature. We represent the given binary data as run-length encoded data. This would lead to a compact or compressed representation of data. Further, we propose an algorithm to directly compute the Manhattan distance between two such binary encoded patterns. We show that classification of data in such compressed form would improve the computation time by a factor of 5 on large handwritten data. The scheme is useful in large data clustering and classification which depend on distance measures.

Mining data in nonlossy compressed form provide an important direction in data mining. It is interesting to examine whether by preparing to avoid some features in the given representation of patterns, we would still be able to generate an abstraction that is as accurate in classification as the one with original feature set. In this chapter, we propose a lossy compression scheme. We demonstrate its efficiency and accuracy on practical datasets. The scheme consists of recognizing a pattern as a sequence of features and identifying subsequences. We identify blocks of features and find a subsequence of their values. We identify unique subsequences. The number of unique subsequences can be pruned by choosing only frequent items that exceed a chosen support value. The number of unique subsequences can further be pruned by choosing to replace less frequent subsequences by their more frequent nearest neighbors. This results in lossy compression in two levels. Generating compressed testing data forms an interesting scheme too. We demonstrate significant reduction in data and its working on large handwritten digit data. We provide bibliographic notes and references at the end of the chapter.

Mining large datasets in a compressed domain are an interesting direction in data mining. In this chapter, we propose a nonlossy compression scheme. It is based on run-length encoding of binary-valued features or floating-point-valued features that are appropriately quantized into binary-valued data. The proposed algorithm compresses a given dataset in terms of runs and computes the dissimilarity in the compressed domain directly. This results in significant gains in computation time and storage. We provide a detailed discussion on relevant terms, algorithms, and its performance. We demonstrate efficiency of its working on classification of unseen compressed patterns. We discuss applicability of the scheme to genetic algorithms where classification happens to be a fitness function. We provide a few application scenarios in data mining. We provide theoretical discussions on the scheme. Bibliographic notes provide a brief discussion on important relevant references. A list of references is provided in the end.

Efficiency in algorithms for data mining can be achieved through identifying representative prototypes or representative features and base explorative study only on those subsets. It is interesting to examine whether both of them can be achieved simultaneously through lossy compression and efficient clustering algorithms on large datasets. We study this aspect in the present chapter. We further examine whether there is a preference in sequencing both these activities; specifically, we examine clustering followed by compression and compression followed by clustering. We provide a detailed discussion on background material that includes definition of various terms, parameters, choice of thresholds in reducing number of patterns and features, etc. We study eight combinations of lossy compression scenarios. We demonstrate that these lossy compression scenarios with compressed information provide a better classification accuracy than the original dataset. In this direction, we implement the proposed scheme on two large datasets, one with binary-valued features and the other with float-point-valued features. At the end of the chapter, we provide bibliographic notes and a list of references.