80
Methods overview
Short reference about some linkage methods of hierarchical agglomerative cluster analysis (HAC).
Basic version of HAC algorithm is one generic; it amounts to updating, at each step, by the formula known as Lance-Williams formula, the proximities between the emergent (merged of two) cluster and all the other clusters (including singleton ...
62
Often they say that there is no other analytical technique as strongly of the "as you sow you shall mow" kind, as cluster analysis is.
I can imagine of a number dimensions or aspects of "rightness" of this or that clustering method:
Cluster metaphor. "I preferred this method because it constitutes clusters such (or such a way) which meets with my concept ...
28
I had the same questions when I tried learning hierarchical clustering and I found the following pdf to be very very useful.
http://www.econ.upf.edu/~michael/stanford/maeb7.pdf
Even if Richard is already clear about the procedure, others who browse through the question can probably use the pdf, its very simple and clear esp for those who do not have ...
24
Requirements for hierarchical clustering
Hierarchical clustering can be used with arbitrary similarity and dissimilarity measures. (Most tools expect a dissimilarity, but will allow negative values - it's up to you to ensure whether small or large valued will be preferred.).
Only methods based on centroids or variance (such as Ward's method) are special, ...
answered Aug 8 '15 at 6:21
Has QUIT--Anony-Mousse
39.1k7 gold badges56 silver badges96 bronze badges
19
1) The y-axis is a measure of closeness of either individual data points or clusters.
2) California and Arizona are equally distant from Florida because CA and AZ are in a cluster before either joins FL.
3) Hawaii does join rather late; at about 50. This means that the cluster it joins is closer together before HI joins. But not much closer. Note that the ...
16
Whereas $k$-means tries to optimize a global goal (variance of the clusters) and achieves a local optimum, agglomerative hierarchical clustering aims at finding the best step at each cluster fusion (greedy algorithm) which is done exactly but resulting in a potentially suboptimal solution.
One should use hierarchical clustering when underlying data has a ...
14
It changes the results. With k-means this should be straightforward to see: the mean of 0, 0 and 1 is different from 0 and 1. Usually this will also be the case for hierarchical clustering, but it depends on the linkage criteria, For example, complete linkage shouldn't be affected.
Speaking generally, I would argue for leaving it in. Having duplicates ...
14
One way or another, every clustering algorithm relies on some notion of “proximity” of points. It seems intuitively clear that you can either use a relative (scale-invariant) notion or an absolute (consistent) notion of proximity, but not both.
I will first try to illustrate this with an example, and then go on to say how this intuition fits with ...
14
Scalability
$k$ means is the clear winner here. $O(n\cdot k\cdot d\cdot i)$ is much better than the $O(n^3 d)$ (in a few cases $O(n^2 d)$) scalability of hierarchical clustering because usually both $k$ and $i$ and $d$ are small (unfortunately, $i$ tends to grow with $n$, so $O(n)$ does not usually hold). Also, memory consumption is linear, as opposed to ...
answered Nov 27 '15 at 23:47
Has QUIT--Anony-Mousse
39.1k7 gold badges56 silver badges96 bronze badges
12
This is because PCA scores are simply original data in a rotated coordinate frame.
Below on the left I show some example 2D data (100 points in 2D) and on the right the corresponding PCA scores. The data cloud simply gets rotated clockwise by approximately 45 degrees.
If it is not completely clear to you how one gets from the first subplot to the second ...
10
To apply most hierarchical clustering/heatmap tools you'll need to convert your correlation matrix into a distance matrix (ie 0 is close together, higher is further apart). This blog post covers some simple methods with R code.
However, a more computationally efficient method is to convert the correlation matrix to a graph, apply a cutoff so that it is ...
10
There are mostly red flag criteria. Properties of data that tell you that a certain approach will fail for sure.
if you have no idea what your data means stop analyzing it. you are just guessing animals in clouds.
if attributes vary in scale and are nonlinear or skewed. this can ruin your analysis unless you have a very good idea of appropriate ...
answered Feb 14 '16 at 20:24
Has QUIT--Anony-Mousse
39.1k7 gold badges56 silver badges96 bronze badges
9
I just wanted to add to the other answers a bit about how, in some sense, there is a strong theoretical reason to prefer certain hierarchical clustering methods.
A common assumption in cluster analysis is that the data are sampled from some underlying probability density $f$ that we don't have access to. But suppose we had access to it. How would we define ...
9
Epsilon is the local radius for expanding clusters. Think of it as a step size - DBSCAN never takes a step larger than this, but by doing multiple steps DBSCAN clusters can become much larger than eps.
If you want your "clusters" to have a maximum radius, that is a set cover type of problem, so you will probably want a greedy approximation. It's not a ...
answered Jul 26 '16 at 19:46
Has QUIT--Anony-Mousse
39.1k7 gold badges56 silver badges96 bronze badges
8
If you remove duplicates, you need to add weights to your data instead, otherwise the result may change (except for single-linkage clustering, I guess).
If your data set has few duplicates, this will likely cost you some runtime.
If your data set has lots of duplicates, it can accelerate the processing a lot to merge them and use weights instead. If you ...
answered May 18 '15 at 16:14
Has QUIT--Anony-Mousse
39.1k7 gold badges56 silver badges96 bronze badges
7
Recall that in hierarchical clustering, you must define a distance metric between clusters. For example, in hierarchical average linkage clustering (probably the most popular option), the distance between clusters is define as the average distance between all inter-cluster pairs. The distance between pairs must also be defined and could be, for example, ...
7
This is the intuition I came up with (a snippet from my blog post here).
A consequence of the richness axiom is that we can define two different distance functions, $d_1$ (top left) and $d_2$ (bottom left), that respectively put all the data points into individual clusters and into some other clustering. Then we can define a third distance function $d_3$ (...
6
Wang, Kaijun, Baijie Wang, and Liuqing Peng. "CVAP: Validation for cluster analyses." Data Science Journal 0 (2009): 0904220071.:
To measure the quality of clustering results, there are two kinds of
validity indices: external indices and internal indices.
An external
index is a measure of agreement between two partitions where the first
partition ...
answered Nov 10 '13 at 4:51
Franck Dernoncourt
40.7k28 gold badges151 silver badges267 bronze badges
6
The meaning of $\epsilon$ is that of the neighbourhood size. The neighbourhood of a point $p$, denoted by $N_{\epsilon}(p)$, is defined as the $N_{\epsilon}(p) = \{q \in D | dist(p,q) \leq \epsilon \}$. Here $D$ is a database of $n$ objects (points) and $q$ a query point.
$\epsilon$ is what would be constitute a reasonable radius for your particular problem. ...
6
Yes, you can do this and interpret it as you think. I have read about such an interpretation in the second chapter of Sophia Rabe-Hesketh and Anders Skrondal's Multilevel and Longitudinal Modeling using Stata book (Volume 1).
A more detailed explanation follows. Edit: I also added a simulation to demonstrate what is going on. Hat tip to Ariel Muldoon for a ...
5
IBM advises against using the Mahalanobis' distance in clustering. See here.
In hierarchical clustering, you need to define the distance between the clusters (as they are formed) and the remaining unclustered data points. So while the Mahalanobis' distance is a sensible measure between data points, it is hard to generalize it to a measure of the distance ...
5
Only single-linkage is optimal. Complete-linkage fails, so your intuition was wrong there. ;-)
As a simple example, consider the one-dimensional data set 1,2,3,4,5,6.
The (unique) optimum solution for complete linkage with two clusters is (1,2,3) and (4,5,6) (complete linkage height 2). The (unique) optimum solution with three clusters is (1,2), (3,4), (5,...
5
If you have done a hierarchical clustering, it outputs a progressive series of more inclusive clusters. If you want to use the hierarchical clustering to determine which users are similar, you can simply look at the returned dendrogram to see which users are joined at the lowest levels. The cophenetic distance makes this idea concrete. It is the inter-...
answered Mar 23 '14 at 4:19
gung - Reinstate Monica
131k79 gold badges345 silver badges641 bronze badges
5
I loaded your data into R and applied hierarchical clustering with Ward's method, which gave 3 clean cut clusters for your stations (Fig.1). Then I applied Principal Component Analysis on the scaled data which revealed that 71% of the information is explained by the first two components (Fig.2). A biplot of the first two components shows you how months (...
5
Transforming your data by subtracting the minimum from every value and dividing the differences by the range is often called normalizing. The transformed data will lie within the interval $[0, 1]$.
It is common to normalize all your variables before clustering. The fact that you are using complete linkage vs. any other linkage, or hierarchical ...
answered Jan 24 '16 at 15:09
gung - Reinstate Monica
131k79 gold badges345 silver badges641 bronze badges
5
PCA and SVD are not comparable. In short, SVD is a technique that one can use to compute the principal components in a PCA. It is possible to find the principal components without using SVD by calculating the eigenvalues and eigenvectors from the covariance matrix of the dataset.
Why PCA of data by means of SVD of the data?
provides more detailed ...
5
\begin{align}
\operatorname{Var}(\vec x) \propto \sum_{i=1}^n(x_i - \bar x)^2 &= \sum_i x_i^2 - 2\bar x \sum_ix_i + n \bar x^2 \\
&= \sum_i x_i^2 - n \bar x^2 = \sum_i x_i^2 - \frac 1n \left(\sum_i x_i\right)^2 = \text{ESS}.
\end{align}
I think $ESS$ is more sensible when talking about compression because $ESS = ||\vec x - \bar x \mathbf 1||^2_2$ ...
4
From the Conclusion of Murtaugh, F. & Legendre, P. (2011). Ward's Hierarchical Clustering Method: Clustering Criterion and Agglomerative Algorithm, ArXive:1111.6285v2 (pdf):
Two algorithms, Ward1 and Ward2...When applied to the same distance matrix D, they produce different results. This article has shown that when they are applied to the same ...
4
One quick point about fixed vs random effects: Both are ways to deal with lack of independence in the errors. If you include hospital as a fixed effect (dummy coding) then the errors are assumed to be independent conditional on hospital - which is totally legitimate. However, when you have many higher level units (k), modelling their means as a random effect ...
4
A perspective from Gelman & Hill's Data Analysis Using Regression and Multilevel/Hierarchical Models may point in a helpful direction. G&H entirely eschew the terms 'fixed' and 'random', arguing that these are misleading (see pp. 245-6). Instead, they emphasize describing the model itself, in terms of the assumptions it embodies, as they relate to ...
Only top voted, non community-wiki answers of a minimum length are eligible