SOCR EduMaterials AnalysisActivities HierarchicalClustering

From Socr

(Difference between revisions)
Jump to: navigation, search
(Input Data examples)
(Hierarchical Clustering Applet: Data Input)
Line 62: Line 62:
</center>  
</center>  
-
* List-like file format:
+
* 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:  
-
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 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.  
** The labels of the nodes can not contain any of the previous separators.  

Revision as of 16:58, 22 July 2012

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

We will demonstrate Hierarchical Clustering using a SOCR built-in example. The data is the distances (in kilometer) between five Spanish cities, and it is represented as a symmetric matrix with headings. The five objects (cities) are: Barcelona, Madrid, San Sebastian, Sevilla, and Valencia.

  • 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. You should see the data displayed in 5 columns: Barcelona, Madrid, San Sebastian, Sevilla, and Valencia.
  • As displayed, the numbers are in the form of a symmetric matrix where each cell value represents the distance between the current city (of the column) and one of the other four cities. For example, the “0.0” on the top left corner indicates that Barcelona and itself are the same cluster, and the “639.0” on the right indicates that the distance between Madrid and Barcelona is 639 kilometers, and so on.
  • After we inputting the data, now we use the computer to calculate the resulting dendrogram -- click on the Calculate button. The default method of calculating the distances between clusters is the Unweighted Average method. Select the DENDROGRAM panel to see the output:

The dendrogram to the right of the menu bar summarizes the results of Hierarchical Clustering analysis (using unweighted average method) nicely: As is clear from the graph, the two closest cities are Madrid and Valencia, and they are the first to be merged. The next closest two clusters, as determined by the unweighted average method, is Barcelona and the previously merged two clusters – and so on.

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.

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.





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