SOCR EduMaterials AnalysisActivities HierarchicalClustering

From Socr

Revision as of 17:41, 4 September 2013 by IvoDinov (Talk | contribs)
(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Contents

SOCR Analysis Hierarchical Clustering Analysis Activity

Overview

This SOCR Activity demonstrates the utilization of the SOCR Analyses package for statistical computing. In particular, it shows how to use Hierarchical Clustering and how to interpret the output results.

Background

Hierarchical Clustering is a technique of clustering analysis which aims to build a hierarchy (top-down ordering) of clusters. Hierarchical clustering is classified as a connectivity-based clustering algorithm, as it builds models based on distance connectivity (i.e., distances between different clusters). There are various ways to compute the distances – for example, in the single linkage method, the distance between two clusters is computed as the distance between the two closest elements in the two clusters, whereas in the complete linkage method, it is computed as the distance between the two farthest elements in the two clusters. In essence, the paradigm of hierarchical clustering boils down to the following steps:

  1. Designate every object/item to a new cluster - if you have X items, then there should be X clusters, with each of them containing just one object.
  2. Calculate the distances between all the current clusters: If each cluster only contains one object, then the distance between each pair is the same as the distance between the objects they contain. If each cluster contain more than one item, then the distance between each pair can be determined using one of the connectivity based methods: Single linkage, complete linage, unweighted average, weighted average, unweighted centroid, weighted centroid, joint between-within, etc.
  3. Based on the distances calculated from step 1, find the closest pair of clusters and merge them into a single cluster, so that there is one less cluster now.
  4. Repeat steps 2 and 3, until all objects are merged into a single cluster of size X.

The results of the above algorithm is usually presented in a dendrogram, which is essentially a tree structure displaying the top-down ordering of clusters under the selected method of distance calculation.

Activity Goals

The goals of this activity are to expose learners to:

  • Inputting data in the correct formats;
  • Reading results of Hierarchical Clustering;
  • Making interpretation of the resulting dendrogram.


Hierarchical Clustering Applet: Data Input

Go to SOCR Analyses and select Hierarchical Clustering from the drop-down list of SOCR analyses, in the left panel. There are two ways to enter data in the SOCR Hierarchical Clustering applet:

  • Click on the Example button on the top of the right panel.
  • Load a text file containing the correctly formatted data by clicking on “Load” button inside the menu bar of DENDROGRAM panel. See below for currently supported data formats.
  • Paste your own data from a spreadsheet into SOCR Hierarchical Clustering data table.

The following is a list of our supported data formats, applying to both ways of inputting (i.e., file “Load” button and copy-paste from spreadsheet).

  • Matrix-like file format: Each line in the text file contains a data matrix row. The characteristics of these files are:
    • The matrix must be symmetric, and the diagonal elements must be zeros.
    • Within each row, the elements are separated by: spaces (‘ ’), tab character, semicolon (‘;’), comma (‘,’) or vertical bar (‘|’).
    • It is possible to include the names in an additional first row or column, but not in both.
    • If present, the labels of the nodes can not contain any of the previous separators. Some different representations for the previous matrix could be:
Node_aNode_bNode_cNode_d
0.0 2.0 4.0 7.0
2.0 0.0 2.0 5.0
4.0 2.0 0.0 3.0
7.0 5.0 3.0 0.0

Or it's transpose

Node_a0.02.04.07.0
Node_b2.00.02.05.0
Node_c4.02.00.03.0
Node_d7.05.03.00.0
  • List-like file format: Each line in the text file contains three elements, which represent the labels of two nodes and the distance (or weight) between them. The characteristics of these files are:
    • The separators between the three elements may be: spaces (‘ ’), tab character, semicolon (‘;’), comma (‘,’) or vertical bar (‘|’).
    • The labels of the nodes can not contain any of the previous separators.
    • Distances from an element to itself (e.g. “a a 0.0”) must not be included.
    • The Hierarchical Clustering applet accepts either the presence or absence of the symmetric data elements, i.e., if the distance between nodes a and b is 2.0, it is possible to include in the list the line “a b 2.0”, or both “a b 2.0” and “b a 2.0”. If both are present, the program checks if they are equal.

Input Data examples

The following simple examples demonstrate the three list‐like files discussed above:

  • Simple list:
ab2
ac4
ad7
bc2
bd5
cd3
  • Complete list:
ab2
ac4
ad7
ba2
bc2
bd5
ca4
cb2
cd3
da7
db5
dc3
  • Matrix‐like with node labels in the first column, data separated by spaces:
0.0 2.0 4.0 7.0
2.0 0.0 2.0 5.0
4.0 2.0 0.0 3.0
7.0 5.0 3.0 0.0

Hierarchical Clustering Example: Primate Evolution

We will demonstrate Hierarchical Clustering using a SOCR built-in example. DNA data representing the molecular phylogeny and evolution of primate mitochondrial DNA is obtained from Hayasaka, Gojobori, and Horai (1988). In this homoplasy example, the primate distance matrix was computed by Makarenkov and Legendre, (2004) and is shown below:

  • As you start the SOCR Analyses Applet, click on Hierarchical Clustering from the combo box in the left panel. Here's what the screen should look like.
  • The left part of the panel looks like this (make sure that the Hierarchical Clustering is showing in the drop-down list of analyses, otherwise you won't be able to find the correct dataset and will not be able to reproduce the results!)
  • In the SOCR Hierarchical Clustering analysis, there is one SOCR built-in example. Click on the Example 1 button.

The dendrogram to the right of the menu bar summarizes the results of Hierarchical Clustering analysis (using unweighted average method) nicely. To change the method used to calculate the distances between clusters, click on the drop-down menu to the right of “Clustering Algorithm” inside the menu bar, and you will see a list of supported methods: Single linkage, complete linage, unweighted average, weighted average, unweighted centroid, weighted centroid and joint between-within. After selecting, click on the “Update” button on the top left, and the dendrogram will then be updated according to the method selected. The user can simultaneous load a text file of correctly formatted data without affecting the current open dendrogram.

As you notice, the dendrogram is a preferable way of displaying the algorithm of hierarchical clustering, as it gives the user a birds-eye view of the merging process without losing significant information.

SpeciesHomo_sapiensPanGorillaPongoHylobatesMacaca_fuscataMacaca_mulattaMacaca_fascicular.Macaca_sylvanusSaimiri_sciureusTarsius_syrichtaLemur_catta
Homo_sapiens00.0890.1040.1610.1820.2320.2330.2490.2560.2730.3220.308
Pan0.08900.1060.1710.1890.2430.2510.2680.2490.2840.3210.309
Gorilla0.1040.10600.1660.1890.2370.2350.2620.2440.2710.3140.293
Pongo0.1610.1710.16600.1880.2440.2470.2620.2410.2840.3030.293
Hylobates0.1820.1890.1890.18800.2470.2390.2570.2420.2690.3090.296
Macaca_fuscata0.2320.2430.2370.2440.24700.0360.0840.1240.2890.3140.282
Macaca_mulatta0.2330.2510.2350.2470.2390.03600.0930.120.2930.3160.289
Macaca_fascicular.0.2490.2680.2620.2620.2570.0840.09300.1230.2870.3110.298
Macaca_sylvanus0.2560.2490.2440.2410.2420.1240.120.12300.2870.3190.287
Saimiri_sciureus0.2730.2840.2710.2840.2690.2890.2930.2870.28700.320.285
Tarsius_syrichta0.3220.3210.3140.3030.3090.3140.3160.3110.3190.3200.252
Lemur_catta0.3080.3090.2930.2930.2960.2820.2890.2980.2870.2850.2520

Below is the same data where all distance matrix values are converted to integers (multiplying the original values by 1,000).

SpeciesHomo_sapiensPanGorillaPongoHylobatesMacaca_fuscataMacaca_mulattaMacaca_fascicular.Macaca_sylvanusSaimiri_sciureusTarsius_syrichtaLemur_catta
Homo_sapiens089104161182232233249256273322308
Pan890106171189243251268249284321309
Gorilla1041060166189237235262244271314293
Pongo1611711660188244247262241284303293
Hylobates1821891891880247239257242269309296
Macaca_fuscata23224323724424703684124289314282
Macaca_mulatta23325123524723936093120293316289
Macaca_fascicular.24926826226225784930123287311298
Macaca_sylvanus2562492442412421241201230287319287
Saimiri_sciureus2732842712842692892932872870320285
Tarsius_syrichta3223213143033093143163113193200252
Lemur_catta3083092932932962822892982872852520
  • You can also load these data in the SOCR 3D Viewer (requires Java 3D) (specify 12x12) to see the distance matrix as an image gradient in 3D.
  • Run the clustering analysis to get a result like the hierarchical tree shown below:
  • Note that this classification agrees with the phylogenetic tree hierarchy previously reported:

Note

If you happen to click on the Clear button in the middle of the procedure, all the data will be cleared out. Simply start over from step 1 and click on an EXAMPLE button for the data you want.

See also

References




Translate this page:

(default)

Deutsch

Español

Français

Italiano

Português

日本語

България

الامارات العربية المتحدة

Suomi

इस भाषा में

Norge

한국어

中文

繁体中文

Русский

Nederlands

Ελληνικά

Hrvatska

Česká republika

Danmark

Polska

România

Sverige

Personal tools