Cluster analysis' is a class of statistical techniques that can be applied to data that exhibit “natural” groupings. Cluster analysis sorts through the raw data and groups them into clusters. A cluster is a group of relatively homogeneous cases or observations. Objects in a cluster are similar to each other. They are also dissimilar to objects outside the cluster, particularly objects in other clusters.
In Marketing, Cluster analysis can be used for:-
Segmenting the market and determining target markets
Product positioning and New Product Development
Selecting test markets
Clustering Methods:
objects are organized into an hierarchical structure as part of the procedure
examples:
Divisive clustering - start by treating all objects as if they are part of a single large cluster, then divide the cluster into smaller and smaller clusters
Agglomerative clustering - start by treating each object as a separate cluster, then group them into bigger and bigger clusters
Difference in Two clustering methods:Agglomerative vs. Divisive Clustering
Once the measure of association as well as the method for determining the distances between clusters have been considered, out last choice for cluster analysis follows. There are two methods for proceeding...
Agglomerative Clustering:
(Leaves to trunk)
• We start out with all sample units in n clusters of size 1.
• Then, at each step of the algorithm, the pair of clusters with the shortest distance are combined into a single cluster.
• The algorithm stops when all sample units are combined into a single cluster of size n.
Divisive Clustering:
(Trunk to leaves)
• We start out with all sample units in a single cluster of size n.
• Then, at each step of the algorithm, clusters are partitioned into a pair of daughter clusters, selected to maximize the distance between each daughter.
• The algorithm stops when sample units are partitioned into n clusters of size 1.
Agglomerative clustering methods Methods for grouping multivariate data into clusters. Suppose there are n data items. The agglomerative clustering methods start by regarding these as n separate clusters of size 1. The two clusters judged closest together (on some criterion) are then merged to reduce the number of clusters to (n − 1). This procedure continues until all the items are collected into a single cluster.
Agglomerative algorithms begin with each element as a separate cluster and merge them into successively larger clusters. Divisive algorithms begin with the whole set and proceed to divide it into successively smaller clusters.
This method builds the hierarchy from the individual elements by progressively merging clusters. In our example, we have six elements {a} {b} {c} {d} {e} and {f}. The first step is to determine which elements to merge in a cluster. Usually, we want to take the two closest elements, according to the chosen distance.
Optionally, one can also construct a distance matrix at this stage, where the number in the i-th row j-th column is the distance between the i-th and j-th elements. Then, as clustering progresses, rows and columns are merged as the clusters are merged and the distances updated. This is a common way to implement this type of clustering, and has the benefit of caching distances between clusters. A simple agglomerative clustering algorithm is described in thesingle-linkage clustering page; it can easily be adapted to different types of linkage.
Suppose we have merged the two closest elements b and c, we now have the following clusters {a}, {b, c}, {d}, {e} and {f}, and want to merge them further. To do that, we need to take the distance between {a} and {b c}, and therefore define the distance between two clusters. Usually the distance between two clusters and is one of the following:
The maximum distance between elements of each cluster (also called complete linkage clustering):
The minimum distance between elements of each cluster (also called single-linkage clustering):
The mean distance between elements of each cluster (also called average linkage clustering):
The sum of all intra-cluster variance.
The increase in variance for the cluster being merged.
The probability that candidate clusters spawn from the same distribution function (V-linkage).
Each agglomeration occurs at a greater distance between clusters than the previous agglomeration, and one can decide to stop clustering either when the clusters are too far apart to be merged (distance criterion) or when there is a sufficiently small number of clusters (number criterion).
Algorithm for Agglomerative clustering (simplified):
1. Initially, put each article in its own cluster.
2. Among all current clusters, pick the two clusters with the smallest distance.
3. Replace these two clusters with a new cluster, formed by merging the two original ones.
4. Repeat the above two steps until there is only one remaining cluster in the pool.
Thus, the agglomerative clustering algorithm will result in a binary cluster tree with single article clusters as its leaf nodes and a root node containing all the articles.
Source:http://www.stat.psu.edu/online/courses/stat505/18_cluster/06_cluster_versus.html
http://www.norusis.com/pdf/SPC_v13.pdf
http://www.highbeam.com/doc/1O106-agglomerativeclstrngmthds.html
http://en.wikipedia.org/wiki/Cluster_analysis
No comments:
Post a Comment