partitioning methods

Slide 1: 

Partitioning Methods in Data Mining By K.Subbiah @ Suresh, III-M.C.A, M.S.University .

Outline: 

Outline What is Cluster Analysis? A Categorization of Major Clustering Methods Partitioning Methods Hierarchical Methods Density-Based Methods Grid-Based Methods Model-Based Clustering Methods Summary

What is Cluster Analysis?: 

What is Cluster Analysis? Cluster: a collection of data objects Similar to one another within the same cluster Dissimilar to the objects in other clusters Cluster analysis Grouping a set of data objects into clusters Clustering is unsupervised classification : no predefined classes Typical applications As a stand-alone tool to get insight into data distribution As a preprocessing step for other algorithms

What Is Good Clustering?: 

What Is Good Clustering? A good clustering method will produce high quality clusters with high intra-class similarity low inter-class similarity The quality of a clustering result depends on both the similarity measure used by the method and its implementation. The quality of a clustering method is also measured by its ability to discover some or all of the hidden patterns.

Requirements of Clustering in Data Mining : 

Requirements of Clustering in Data Mining Scalability Ability to deal with different types of attributes Discovery of clusters with arbitrary shape Minimal requirements for domain knowledge to determine input parameters Able to deal with noise and outliers Insensitive to order of input records High dimensionality Incorporation of user-specified constraints Interpretability and usability

Major Clustering Approaches: 

Major Clustering Approaches Partitioning algorithms : Construct various partitions and then evaluate them by some criterion Hierarchy algorithms : Create a hierarchical decomposition of the set of data (or objects) using some criterion Density-based : based on connectivity and density functions Grid-based : based on a multiple-level granularity structure Model-based : A model is hypothesized for each of the clusters and the idea is to find the best fit of that model to each other

Partitioning Algorithms: Basic Concept: 

Partitioning Algorithms: Basic Concept Partitioning method: Construct a partition of a database D of n objects into a set of k clusters Given a k , find a partition of k clusters that optimizes the chosen partitioning criterion Heuristic methods: k-means and k- medoids algorithms k-means (MacQueen’67): Each cluster is represented by the center of the cluster k- medoids or PAM (Partition around medoids ) (Kaufman & Rousseeuw’87): Each cluster is represented by one of the objects in the cluster

The K-Means Clustering Method : 

The K-Means Clustering Method Given k , the k-means algorithm is implemented in 4 steps: Partition objects into k nonempty subsets Compute seed points as the centroids of the clusters of the current partition. The centroid is the center (mean point) of the cluster. Assign each object to the cluster with the nearest seed point. Go back to Step 2, stop when no more new assignment.

The K-Means Clustering Method :EXAMPLE: 

The K-Means Clustering Method :EXAMPLE .

Comments on the K-Means Method: 

Comments on the K-Means Method Strength Relatively efficient : O ( tkn ), where n is # objects, k is # clusters, and t is # iterations. Normally, k , t << n . Often terminates at a local optimum . The global optimum may be found using techniques such as: deterministic annealing and genetic algorithms Weakness Applicable only when mean is defined. Need to specify k, the number of clusters, in advance Unable to handle noisy data and outliers Not suitable to discover clusters with non-convex shapes

K-Means versus K-Modes : 

K-Means versus K-Modes A few variants of the k-means which differ in Selection of the initial k means Dissimilarity calculations Strategies to calculate cluster means Handling categorical data: k-modes (Huang’98) Replacing means of clusters with modes Using new dissimilarity measures to deal with categorical objects Using a frequency -based method to update modes of clusters A mixture of categorical and numerical data: k-prototype method

The K-Medoids Clustering Method: 

The K- Medoids Clustering Method Find representative objects, called medoids , in clusters PAM ( P artitioning A round M edoids, 1987) starts from an initial set of medoids and iteratively replaces one of the medoids by one of the non-medoids if it improves the total distance of the resulting clustering PAM works effectively for small data sets, but does not scale well for large data sets CLARA ( C lustering LAR ge A nalysis by Kaufmann 1990)

K-medoids algorithm: 

K-medoids algorithm Use real object to represent the cluster Select k representative objects arbitrarily repeat Assign each remaining object to the cluster of the nearest medoid Randomly select a nonmedoid object Compute the total cost, S, of swapping o j with o random If S < 0 then swap o j with o random until there is no change

The K-Medoids Clustering Method: 

The K- Medoids Clustering Method

The K-Medoids Clustering Method (select the randomly K-Medoids): 

The K- Medoids Clustering Method ( select the randomly K- Medoids )

The K-Medoids Clustering Method (Allocate to Each Point to Closest Medoid) : 

The K- Medoids Clustering Method ( Allocate to Each Point to Closest Medoid )

The K-Medoids Clustering Method (Allocate to Each Point to Closest Medoid) : 

The K- Medoids Clustering Method ( Allocate to Each Point to Closest Medoid )

The K-Medoids Clustering Method (Determine New Medoid for each Cluster) : 

The K- Medoids Clustering Method ( Determine New Medoid for each Cluster )

The K-Medoids Clustering Method (Allocate to each point to Closest Medoid ) : 

The K- Medoids Clustering Method ( Allocate to each point to Closest Medoid )

The K-Medoids Clustering Method (Stop the process ) : 

The K- Medoids Clustering Method ( Stop the process )

Hierarchical Clustering: 

Hierarchical Clustering Use distance matrix as clustering criteria. This method does not require the number of clusters k as an input, but needs a termination condition agglomerative (AGNES) Bottom-up divisive (DIANA) Top-down c d e a b ab de cde abcde

More on Hierarchical Clustering Methods: 

More on Hierarchical Clustering Methods Major weakness of agglomerative clustering methods do not scale well: time complexity of at least O ( n 2 ), where n is the number of total objects can never undo what was done previously Integration of hierarchical with distance-based clustering BIRCH (1996) : uses CF-tree and incrementally adjusts the quality of sub-clusters CURE (1998 ): selects well-scattered points from the cluster and then shrinks them towards the center of the cluster by a specified fraction CHAMELEON (1999) : hierarchical clustering using dynamic modeling

BIRCH (1996): 

BIRCH (1996) Birch : Balanced Iterative Reducing and Clustering using Hierarchies , by Zhang, Ramakrishnan , Livny (SIGMOD ’ 96) Incrementally construct a CF (Clustering Feature) tree, a hierarchical data structure for multiphase clustering Phase 1: scan DB to build an initial in-memory CF tree (a multi-level compression of the data that tries to preserve the inherent clustering structure of the data) Phase 2: use an arbitrary clustering algorithm to cluster the leaf nodes of the CF-tree Scales linearly : finds a good clustering with a single scan and improves the quality with a few additional scan. Weakness : handles only numeric data, and sensitive to the order of the data record.

CURE (Clustering Using REpresentatives ): 

CURE ( C lustering U sing RE presentatives ) CURE : proposed by Guha , Rastogi & Shim, 1998 Stops the creation of a cluster hierarchy if a level consists of k clusters Uses multiple representative points to evaluate the distance between clusters, adjusts well to arbitrary shaped clusters and avoids single-link effect

Drawbacks of Distance-Based Method: 

Drawbacks of Distance-Based Method Drawbacks of square-error based clustering method Consider only one point as representative of a cluster Good only for convex shaped , similar size and density, and if k can be reasonably estimated

Cure: The Algorithm: 

Cure: The Algorithm Draw random sample s . Partition sample to p partitions with size s/p Partially cluster partitions into s/ pq clusters Eliminate outliers By random sampling If a cluster grows too slow , eliminate it. Cluster partial clusters. Label data in disk

Summary: 

Summary Cluster analysis groups objects based on their similarity and has wide applications Measure of similarity can be computed for various types of data Clustering algorithms can be categorized into partitioning methods, hierarchical methods, density-based methods, grid-based methods, and model-based methods Outlier detection and analysis are very useful for fraud detection, etc. and can be performed by statistical, distance-based or deviation-based approaches There are still lots of research issues on cluster analysis, such as constraint-based clustering

References: 

References [MacQueen, 1967] J.B., MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations”, Proc. Symp. Math. Statist.and Probability (5th), 281-297,(1967). [Kantardzic, 2003] M., Kantardzic, “ Data Mining: Concepts, Methods and Algorithms ”, Wiley, (2003) . WWW.Google.co.uk

Thank u…..: 

Thank u…..