Hierarchical clustering

library(swirl)
swirl()
library(fields)

We’ll find the closest two points and put them together in | one cluster, then find the next closest pair in the updated picture, | and so forth. We’ll repeat this process until we reach a reasonable | stopping place.

There are several ways to measure | distance or similarity. Euclidean distance and correlation similarity | are continuous measures, while Manhattan distance is a binary | measure.

Euclidean distance is what you learned about in high school algebra. | Given two points on a plane, (x1,y1) and (x2,y2), the Euclidean | distance is the square root of the sums of the squares of the | distances between the two x-coordinates (x1-x2) and the two | y-coordinates (y1-y2). You probably recognize this as an application | of the Pythagorean theorem which yields the length of the hypotenuse | of a right triangle.

Euclidean distance is distance “as the crow flies”. Many | applications, however, can’t realistically use crow-flying distance. | Cars, for instance, have to follow roads. In this case, we can use Manhattan or city block distance

You want to travel from the point at the lower left to the one on the | top right. The shortest distance is the Euclidean (the green line), | but you’re limited to the grid, so you have to follow a path similar | to those shown in red, blue, or yellow. These all have the same | length (12) which is the number of small gray segments covered by | their paths.

More formally, Manhattan distance is the sum of the absolute values
of the distances between each coordinate, so the distance between the
points (x1,y1) and (x2,y2) is |x1-x2|+|y1-y2|. As with Euclidean
distance, this too generalizes to more than 2 dimensions.

dist(dataFrame)

Run the R command dist with the argument dataFrame to compute the | distances between all pairs of these points. By default dist uses | Euclidean distance. Entry (i,j) | indicates the distance between points i and j. Clearly you need only | a lower triangular matrix since the distance between points i and j | equals that between j and i.

simple function which | you can call which creates a dendrogram for you

 hc<-hclust(distxy)
plot(hc)
plot(as.dendrogram(hc))
abline(h=1.5, col="blue")

We see that by cutting at .4 we have 5 clusters, indicating that this | distance is small enough to break up our original grouping of points.

abline(h=.4, col="red")

at .05, we are getting 12

 abline(h=.05, col="green")

So the number of clusters in your data depends on where you draw the | line!

There are several ways to measure the distances between clusters of points. We’ll just mention two. The first | is called complete linkage and it says that if you’re trying to | measure a distance between two clusters, take the greatest distance | between the pairs of points in those two clusters. Obviously such | pairs contain one point from each cluster

To measure distance

dist(dFsm)

The second way to measure a distance between two clusters that we’ll | just mention is called average linkage. First you compute an | “average” point in each cluster (think of it as the cluster’s center | of gravity). You do this by computing the mean (average) x and y | coordinates of the points in the cluster. | Then you compute the distances between each cluster average to | compute the intercluster distance.

The last method of visualizing data we’ll mention in this lesson | concerns heat maps. Wikipedia (http://en.wikipedia.org/wiki/Heat_map) | tells us a heat map is “a graphical representation of data where the | individual values contained in a matrix are represented as colors. | … Heat maps originated in 2D displays of the values in a data | matrix. Larger values were represented by small dark gray or black | squares (pixels) and smaller values by lighter squares.”

heatmap()
heatmap(dataMatrix, col = cm.colors(25) )
data("mtcars")
heatmap(mt)

Once you decide basics, such as defining a distance | metric and linkage method, hierarchical clustering is deterministic.