computer

Chapter 12 – Cluster Analysis

© Galit Shmueli and Peter Bruce 2008

Data Mining for Business Intelligence

Shmueli, Patel & Bruce

Cluster Analysis

This file is based on data mining textbook by Shmuel, Patel, and Bruce as introduced on slide #1. It is being expanded and improved for MI375 students by Sean Eom

Cluster Analysis

Cluster analysis is a statistical technique applied to:

 Identify groups (clusters) of entities that have similar characteristics

In business, it is frequently used for

 segmenting markets into groups of similar customers

 Example: Claritas segmented US neighborhoods based on demographics & income:  “Furs & station wagons,”

 “Money & Brains”, …

Other Applications

 Periodic table of the elements

 Classification of species

 Grouping securities in portfolios

 Grouping firms for structural analysis of economy

 Army uniform sizes

Clustering Example #1 : Using a variable Goal: find clusters of similar authors in Decision

Support Systems. Table 1 (next slide) shows A Cocitation Frequency Matrix Data of 10 prominent professors/authors in DSS. Each of them does research on different subjects/topics.

Data: 10 authors, 1 variable (Author Cocitation Frequencies)

Source: This example is taken from Eom, Sean. (2015). Mining cocitation data with SAS Enterprise Guide. New Castle upon Tyne: Cambridge Scholars Publishing.

ACA and assumptions  The cocitation of authors occurs when a citing paper

cites any work of authors in reference lists.

 the fundamental premise of cocitation analysis is that:

 Authors whose works are cited together frequently are interpreted as having close relationships with one another.

 Cocitation is a measure of the perceived similarity, conceptual linkage, or cognitive relationship between two authors.

Table 1. Author Cocitation frequency Data Matrix (10 authors in DSS)

The cocitation frequency matrix may not be the best dataset for students. Think the frequency as the frequency of either telephone call or text messaging, which can be an indicator(strength) of relationship among people.

Fig. 1: The Input to the cluster analysis: a Distance (proximity) matrix

Table 2: Distance Matrix of 10 prominent professors/authors in DSS

Table 3: Correlations Matrix: Input to Produce Distance matrix

Measuring Distance Between Records

Distance Between Two Records

1. Euclidean Distance is most popular:

2. Correlation-based similarity

ACA uses Method = DCORR. which is described below.

DCORR Correlation transformed to

Euclidean distance as sqrt (1-CORR).

Converting the correlations matrix to distance matrix using DCORR , which is sqrt (1-CORR)

1. Cell b14 has formula “=sqrt(1-b1)”. The formula is copied to all other cells (b15 through b23). 2. At cell c15, enter the formula

“=sqrt(1-c2). Copy it to cells c16 through c23. Compare your results with the values in Table 2. If identical, repeatedly enter the DCORR formula and complete the distance matrix.

3. Your results (distance matrix) should be the same as Table 2.

Hierarchical Clustering

Hierarchical Methods: Use Agglomerative Methods

Agglomerative Methods

 Begin with n-clusters (each record its own cluster)

 Keep joining records into clusters until one cluster is left (the entire data set)

 Most popular

Divisive Methods

 Start with one all-inclusive cluster

 Repeatedly divide into smaller clusters

Clustering process  After the measure of similarity is determined between author

variables, what set of rules and procedures should be used to group all authors under study? These rules and procedures are also called clustering algorithms.

 There are two types of clustering algorithms: hierarchical and non- hierarchical. ACA uses hierarchical procedures to join all authors into one whole cluster.

 In the beginning, each author is a cluster. Each author in n author dataset matrix starts out its own cluster (n clusters). Based on the similarity measures discussed earlier, two authors who cocited together most frequently will be grouped as the first cluster. Now the total number of clusters becomes n-1. This process of clustering continues to form until the last one cluster from n clusters. This procedure is called agglomerative hierarchical clustering.

Understanding Cluster History  In the next step, we create a table that shows all

possible 45 combination of two authors [n*(n-1)/2] and their corresponding distances, sorted from the smallest to the largest (table 4).

Table 4. Sorted distance matrix

Analysis of the Clustering Process with Different Clustering Algorithms

 Single (shortest distance) Linkage Procedure (Method=SINGLE)

 The single linkage procedure (a.k.a., the nearest-neighbor approach) finds the shortest distance from any author in one cluster to any author in the other cluster. The single linkage cluster analysis (Table 5-9) shows cluster history beginning with CL 9 (Holsapple and Whinston). Before joining two authors with the shortest distance, we have ten authors. Each author is a separate cluster in the beginning. Therefore, the first cluster in Table 2 is CL9.

 Regardless of the clustering method used, there are two common rules in the agglomerative hierarchical clustering process.

RULES TO APPLY Rule No. 1 (Measuring distance between single entity):

 (1A)Start with two entities (authors, A & B) from the top of the sorted distance matrix. They (A & B) and will be Cluster (N-1), unless either one or two authors belong to any clusters formed in the previous step.

 Start with the next two authors. Check whether either one of the two authors (B & C) belongs to any clusters formed in the previous step.

 IF so,

 (1B)THEN the other of the two (C) become a member of a new cluster with three (or more) members (the members of the cluster formed in the previous step + the other of the two;

 (1C)ELSE the next two authors (C & D) form a new cluster.

RULES TO APPLY Rule No. 2 (Measuring distance between Clusters):

 Start with the next two authors. Check whether the two authors belong to any clusters formed in the previous step.

 (2A) IF the two authors (A & D) belong to a Cluster formed in the previous step, THEN no action is necessary and move to the next two authors in the sorted distance matrix.

 Start with the next two authors. Check whether the two authors belong to any clusters formed in the previous step.

 (2B)IF each author of the next two belongs to two different Clusters formed in the previous step, THEN form a new cluster by joining the two clusters.

Measuring distance between two clusters

Think these two countries as Clusters of cities: the Portugal cluster and the Spain cluster

Single linkage (minimum distance) is the distance between Lisbon and Serville.

Complete linkage (maximum distance) is the distance between Lisbon and Barcelona.

Centroid distance is the distance between the two cluster centroids, computed by software. Roughly speaking, between Madrid and the center location in Portugal.

Figure 2. the Portugal cluster and the Spain cluster

Table 5. Cluster History with Single Linkage

The process of building Cluster History using the rules  Step 1:

 Data: row 2 of the sorted distance matrix (Holsapple & Whinston)

 Rule to apply: #1A

 Outcome  Create CL 9 (N-1) Holsapple & Whinston, freq (2)

 Step 2:  Data: row 3 of the sorted distance matrix (Bonczek & Whinston)

 Rule to apply: #1B

 Outcome  Cluster 8 CL9 + Bonczek, freq (3)

The process of building Cluster History using the rules  Step 3:

 Data: row 4 of the sorted distance matrix (Bonczek & Holsapple)

 Rule to apply: #2A

 Outcome  No action

 Step 4:  Data: row 5 of the sorted distance matrix (Carlson & Sprague)

 Rule to apply: #1C

 Outcome  Cluster 7 (Carlson & Sprague), freq (2)

The process of building Cluster History using the rules  Step 5:

 Data: row 6 of the sorted distance matrix (Keen & Scott-Morton)

 Rule to apply: #1C

 Outcome

 Create cluster 6 (Keen & Scott-Morton), freq (2)

 Step 6:  Data: row 7 of the sorted distance matrix (Scott-Morton & Sprague)

 Rule to apply: #2B

 Outcome

 Cluster 5 (cl 7 & cl6), freq (4)

The process of building Cluster History using the rules  Step 7:

 Data: row 8 of the sorted distance matrix (Carlson & Keen)

 Rule to apply: #2A

 Outcome  none

 Step 8:  Data: row 9 of the sorted distance matrix (Carlson & Scott-Morton)

 Rule to apply: #2A

 Outcome  none

The process of building Cluster History using the rules  Step 9:

 Data: row 10 of the sorted distance matrix (Gallupe & Nunamaker)

 Rule to apply: #1C

 Outcome

 Create cluster 4 (Gallupe & Nunamaker), freq (2)

 Step 10:  Data: row 11 of the sorted distance matrix (Keen & Sprague)

 Rule to apply: #2B

 Outcome  none

The process of building Cluster History using the rules  Step 11:

 Data: row 12 of the sorted distance matrix (DeSanctise & Nunamaker)

 Rule to apply: #1B

 Outcome

 Create cluster 3 (DeSanctis, CL4), freq (3)

 Step 12:  Data: row 13 of the sorted distance matrix (Keen & Sprague)

 Rule to apply: #2B

 Outcome  none

The process of building Cluster History using the rules  Step 13:

 Data: row 14 of the sorted distance matrix (Carlson & Holsapple)

 Rule to apply: #2B

 Outcome

 Create cluster 2 (cl5 + cl8), freq (7)

 Step 14:  Data: row 15 of the sorted distance matrix (Carlson & Whinston)

 Rule to apply: #2A

 Outcome  none

The process of building Cluster History using the rules  Step 15:

 Data: row 16 of the sorted distance matrix (Bonczek & Carlson) row 17 of the sorted distance matrix (Holsapple & Sprague row 18 of the sorted distance matrix (Sprague & Whinston) row 19 of the sorted distance matrix (Bonczek & Sprague) row 20 of the sorted distance matrix (Holsapple & Scott-Morton) row 21 of the sorted distance matrix (Scott-Morton & Whinston) row 22 of the sorted distance matrix (Holsapple & Keen)

 row 23 of the sorted distance matrix (Bonczek & Scott-Morton) row 24 of the sorted distance matrix (Keen & Whinston row 25 of the sorted distance matrix (Bonczek & Keen)

 Rule to apply: #2A

 Outcome

 none

 Step 16:  Data: row 26 of the sorted distance matrix (DeSantis & Scott-Morton)

 Rule to apply: #2B

 Outcome  Create cluster 1, CL2 + CL3, 10 (freq)

The final cluster

Step 17: Data: row 27 through 46 of the sorted distance matrix Rule to apply: #2A Outcome

none

Table 6. Cluster History with Single Linkage

Figure 2. Single linkage cluster dendrogram

Table 11. Complete (maximum distance) link cluster history

Figure 4. Complete link cluster dendrogram

Table 10. Cluster history with average linkage method

Figure 3. Average link cluster dendrogram

Clustering Example #2: Public Utilities Goal: find clusters of similar utilities

Data: 22 firms, 8 variables

 Fixed-charge covering ratio

 Rate of return on capital

 Cost per kilowatt capacity

 Annual load factor

 Growth in peak demand

 Sales

 % nuclear

 Fuel costs per kwh

Company Fixed_charge RoR Cost Load D Demand Sales Nuclear Fuel_Cost

Arizona 1.06 9.2 151 54.4 1.6 9077 0 0.628 Boston 0.89 10.3 202 57.9 2.2 5088 25.3 1.555 Central 1.43 15.4 113 53 3.4 9212 0 1.058 Commonwealth 1.02 11.2 168 56 0.3 6423 34.3 0.7 Con Ed NY 1.49 8.8 192 51.2 1 3300 15.6 2.044 Florida 1.32 13.5 111 60 -2.2 11127 22.5 1.241 Hawaiian 1.22 12.2 175 67.6 2.2 7642 0 1.652 Idaho 1.1 9.2 245 57 3.3 13082 0 0.309 Kentucky 1.34 13 168 60.4 7.2 8406 0 0.862 Madison 1.12 12.4 197 53 2.7 6455 39.2 0.623 Nevada 0.75 7.5 173 51.5 6.5 17441 0 0.768 New England 1.13 10.9 178 62 3.7 6154 0 1.897 Northern 1.15 12.7 199 53.7 6.4 7179 50.2 0.527 Oklahoma 1.09 12 96 49.8 1.4 9673 0 0.588 Pacific 0.96 7.6 164 62.2 -0.1 6468 0.9 1.4 Puget 1.16 9.9 252 56 9.2 15991 0 0.62 San Diego 0.76 6.4 136 61.9 9 5714 8.3 1.92 Southern 1.05 12.6 150 56.7 2.7 10140 0 1.108 Texas 1.16 11.7 104 54 -2.1 13507 0 0.636 Wisconsin 1.2 11.8 148 59.9 3.5 7287 41.1 0.702 United 1.04 8.6 204 61 3.5 6650 0 2.116 Virginia 1.07 9.3 174 54.3 5.9 10093 26.6 1.306

Low fuel cost, low sales

Sales & Fuel Cost: 3 rough clusters can be seen

High fuel cost, low sales

Low fuel cost, high sales

Extension to More Than 2 Dimensions

In prior example, clustering was done by eye

Multiple dimensions require formal algorithm with

 A distance measure

 A way to use the distance measure in forming clusters

We will consider two algorithms: hierarchical and non- hierarchical

Hierarchical Clustering

Hierarchical Methods

Agglomerative Methods

 Begin with n-clusters (each record its own cluster)

 Keep joining records into clusters until one cluster is left (the entire data set)

 Most popular

Divisive Methods

 Start with one all-inclusive cluster

 Repeatedly divide into smaller clusters

A Dendrogram shows the cluster hierarchy

Measuring Distance

Between records

Between clusters

Measuring Distance Between Records

Distance Between Two Records

Euclidean Distance is most popular:

Normalizing

Problem: Raw distance measures are highly influenced by scale of measurements

Solution: normalize (standardize) the data first  Subtract mean, divide by std. deviation

 Also called z-scores

Example: Normalization

For 22 utilities:

Avg. sales = 8,914

Std. dev. = 3,550

Normalized score for Arizona sales:

(9,077-8,914)/3,550 = 0.046

Data Downloaded

Choose Cluster  Hierarchical Clustering

Move all 8 variables from Variables to Selected Variables

Make sure to “normalize input data” and use “single linkage” to produce Figure 12.3.

For Categorical Data: Similarity

Similarity metrics based on this table:

 Matching coef. = (a+d)/p

 Jaquard’s coef. = d/(b+c+d)

 Use in cases where a matching “1” is much greater evidence of similarity than matching “0” (e.g. “owns Corvette”)

0 1 0 a b 1 c d

To measure the distance between records in terms of two 0/1 variables, create table with counts:

Other Distance Measures

 Correlation-based similarity

 Statistical distance (Mahalanobis)

 Manhattan distance (absolute differences)

 Maximum coordinate distance

 Gower’s similarity (for mixed variable types: continuous & categorical)

Measuring Distance Between Clusters

Minimum Distance (Cluster A to Cluster B)

 Also called single linkage

 Distance between two clusters is the distance between the pair of records Ai and Bj that are closest

Maximum Distance (Cluster A to Cluster B)

 Also called complete linkage

 Distance between two clusters is the distance between the pair of records Ai and Bj that are farthest from each other

Average Distance

 Also called average linkage

 Distance between two clusters is the average of all possible pair-wise distances

Centroid Distance

 Distance between two clusters is the distance between the two cluster centroids.

 Centroid is the vector of variable averages for all records in a cluster

The Hierarchical Clustering Steps (Using Agglomerative Method)

1. Start with n clusters (each record is its own cluster)

2. Merge two closest records into one cluster

3. At each successive step, the two clusters closest to each other are merged

Dendrogram, from bottom up, illustrates the process

Records 12 & 21 are closest & form first cluster

Reading the Dendrogram See process of clustering: Lines connected lower down are merged earlier

 10 and 13 are merged next

Determining number of clusters: For a given “distance between clusters”, a horizontal line intersects the clusters that are that far apart, to create clusters

 E.g., at distance of 4.6 (red line in next slide), data can be reduced to 2 clusters -- The smaller of the two is circled

 At distance of 3.6 (green line) data can be reduced to 6 clusters, including the circled cluster

Validating Clusters

Interpretation

Goal: obtain meaningful and useful clusters

Caveats:

(1) Random chance can often produce apparent clusters

(2) Different cluster methods produce different results

Solutions:

 Obtain summary statistics

 Also review clusters in terms of variables not used in clustering

 Label the cluster (e.g. clustering of financial firms in 2008 might yield label like “midsize, sub-prime loser”)

Desirable Cluster Features

Stability – are clusters and cluster assignments sensitive to slight changes in inputs? Are cluster assignments in partition B similar to partition A?

Separation – check ratio of between-cluster variation to within-cluster variation (higher is better)

Nonhierarchical Clustering: K-Means Clustering

K-Means Clustering Algorithm

1. Choose # of clusters desired, k

2. Start with a partition into k clusters

 Often based on random selection of k centroids

3. At each step, move each record to cluster with closest centroid

4. Recompute centroids, repeat step 3

5. Stop when moving records increases within-cluster dispersion

K-means Algorithm: Choosing k and Initial Partitioning

Choose k based on the how results will be used

 e.g. “How many market segments do we want?”

Also experiment with slightly different k’s

Initial partition into clusters can be random, or based on domain knowledge

 If random partition, repeat the process with different random partitions

XLMiner Output: Cluster Centroids

We chose k = 3

4 of the 8 variables are shown

Cluster Fixed_charge RoR Cost Load_factor

Cluster-1 0.89 10.3 202 57.9

Cluster-2 1.43 15.4 113 53

Cluster-3 1.06 9.2 151 54.4

Distance Between Clusters

Clusters 1 and 2 are relatively well-separated from each other, while cluster 3 not as much

Distance

between Cluster-1 Cluster-2 Cluster-3

Cluster-1 0 5.03216253 3.16901457

Cluster-2 5.03216253 0 3.76581196

Cluster-3 3.16901457 3.76581196 0

Within-Cluster Dispersion

Clusters 1 and 2 are relatively tight, cluster 3 very loose

Conclusion: Clusters 1 & 2 well defined, not so for cluster 3

Next step: try again with k=2 or k=4

Data summary (In Original coordinates)

Cluster #Obs

Average

distance in

cluster

Cluster-1 12 1748.348058

Cluster-2 3 907.6919822

Cluster-3 7 3625.242085

Overall 22 2230.906692

Summary  Cluster analysis is an exploratory tool. Useful only

when it produces meaningful clusters

 Hierarchical clustering gives visual representation of different levels of clustering

 On other hand, due to non-iterative nature, it can be unstable, can vary highly depending on settings, and is computationally expensive

 Non-hierarchical is computationally cheap and more stable; requires user to set k

 Can use both methods

 Be wary of chance results; data may not have definitive “real” clusters