Repository: scikit-learn/scikit-learn
Pull request: MRG add dendrogram example
Fixes #6788, fixes #3464.

This PR stores the distances in the AgglomerativeClustering object if they are computed, and adds an example to plot the corresponding dendrogram.
It's based on #3464 with some fixes.

We don't have access to the number of data points per node, but that is easy to compute. If there's a better vectorized way I'm all ears! But I assume this is mostly useful for smaller datasets anyway.

Problem statement:
dendrogram question
Hi,

I'm running a AgglomerativeClustering algorithm. For further analysis, I would like to plot a dendrogram, but scikit-learn currently does not provide a dendrogram plot. How would you suggest to plot the dendrogram and cut the dendrogram to get x number of clusters/groups?

Thanks,
Arnold

Hints from issue discussion:
For the plotting-part, Michael Waskoms [seaborn](https://stanford.edu/~mwaskom/software/seaborn/examples/structured_heatmap.html) could be interesting.

[This](http://docs.scipy.org/doc/scipy-0.14.0/reference/cluster.hierarchy.html#module-scipy.cluster.hierarchy) should help you.

@AlexanderFabisch thanks, from the dendrogram i see which samples is within which cluster. a sample has multiple features... how can i see which feature is the most crucial one?

I think we had this discussion before, though I don't remember when / where exactly. maybe @GaelVaroquaux remembers? I think having dendrograms in sklearn would be nice.

@amueller  A dendrogram example was proposed in PR https://github.com/scikit-learn/scikit-learn/pull/3464

Any news on this issue?

Commit message: add dendrogram example

Patch to review:
diff --git a/examples/cluster/plot_agglomerative_dendrogram.py b/examples/cluster/plot_agglomerative_dendrogram.py
new file mode 100644
index 0000000000000..5735a4bb18063
--- /dev/null
+++ b/examples/cluster/plot_agglomerative_dendrogram.py
@@ -0,0 +1,53 @@
+# Authors: Mathew Kallada, Andreas Mueller
+# License: BSD 3 clause
+"""
+=========================================
+Plot Hierarachical Clustering Dendrogram
+=========================================
+This example plots the corresponding dendrogram of a hierarchical clustering
+using AgglomerativeClustering and the dendrogram method available in scipy.
+"""
+
+import numpy as np
+
+from matplotlib import pyplot as plt
+from scipy.cluster.hierarchy import dendrogram
+from sklearn.datasets import load_iris
+from sklearn.cluster import AgglomerativeClustering
+
+
+def plot_dendrogram(model, **kwargs):
+    # Create linkage matrix and then plot the dendrogram
+
+    # create the counts of samples in each node
+    counts = np.zeros(model.children_.shape[0])
+    n_samples = len(model.labels_)
+    for i, merge in enumerate(model.children_):
+        current_count = 0
+        for j in [0, 1]:
+            if merge[j] < n_samples:
+                current_count += 1
+            else:
+                current_count += counts[merge[j] - n_samples]
+        counts[i] = current_count
+
+    linkage_matrix = np.column_stack([model.children_, model.distances_,
+                                      counts]).astype(float)
+
+    # Plot the corresponding dendrogram
+    dendrogram(linkage_matrix, **kwargs)
+
+
+iris = load_iris()
+X = iris.data
+
+# setting distance_threshold=0 ensures we compute the full tree.
+model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)
+
+model = model.fit(X)
+fig = plt.figure(figsize=(25, 10))
+plt.title('Hierarchical Clustering Dendrogram')
+# plot the top three levels of the dendrogram
+plot_dendrogram(model, truncate_mode='level', p=3)
+plt.xlabel("Number of points in node (or index of point if no parenthesis).")
+plt.show()
diff --git a/sklearn/cluster/hierarchical.py b/sklearn/cluster/hierarchical.py
index 17aae14589511..33957c2da6f0e 100644
--- a/sklearn/cluster/hierarchical.py
+++ b/sklearn/cluster/hierarchical.py
@@ -859,10 +859,10 @@ def fit(self, X, y=None):
          self.n_leaves_,
          parents) = out[:4]
 
-        if distance_threshold is not None:
-            distances = out[-1]
+        if return_distance:
+            self.distances_ = out[-1]
             self.n_clusters_ = np.count_nonzero(
-                distances >= distance_threshold) + 1
+                self.distances_ >= distance_threshold) + 1
         else:
             self.n_clusters_ = self.n_clusters
 


Code review comments:
diff_hunk: @@ -0,0 +1,53 @@
+# Authors: Mathew Kallada, Andreas Mueller
+# License: BSD 3 clause
+"""
+=========================================
+Plot Hierarachical Clustering Dendrogram
+=========================================
+This example plots the corresponding dendrogram of a hierarchical clustering
+using AgglomerativeClustering and the dendrogram method available in scipy.
+"""
+
+import numpy as np
+
+from matplotlib import pyplot as plt
+from scipy.cluster.hierarchy import dendrogram
+from sklearn.datasets import load_iris
+from sklearn.cluster import AgglomerativeClustering
+
+
+def plot_dendrogram(model, **kwargs):
+    # Create linkage matrix and then plot the dendrogram
+
+    # create the counts of samples in each node
+    counts = np.zeros(model.children_.shape[0])
+    n_samples = len(model.labels_)
+    for i, merge in enumerate(model.children_):
+        current_count = 0
+        for j in [0, 1]:
+            if merge[j] < n_samples:
path: examples/cluster/plot_agglomerative_dendrogram.py
text: @user1:
```suggestion
            if child_idx < n_samples:
```

diff_hunk: @@ -0,0 +1,53 @@
+# Authors: Mathew Kallada, Andreas Mueller
+# License: BSD 3 clause
+"""
+=========================================
+Plot Hierarachical Clustering Dendrogram
+=========================================
+This example plots the corresponding dendrogram of a hierarchical clustering
+using AgglomerativeClustering and the dendrogram method available in scipy.
+"""
+
+import numpy as np
+
+from matplotlib import pyplot as plt
+from scipy.cluster.hierarchy import dendrogram
+from sklearn.datasets import load_iris
+from sklearn.cluster import AgglomerativeClustering
+
+
+def plot_dendrogram(model, **kwargs):
+    # Create linkage matrix and then plot the dendrogram
+
+    # create the counts of samples in each node
+    counts = np.zeros(model.children_.shape[0])
+    n_samples = len(model.labels_)
+    for i, merge in enumerate(model.children_):
+        current_count = 0
+        for j in [0, 1]:
+            if merge[j] < n_samples:
+                current_count += 1
+            else:
+                current_count += counts[merge[j] - n_samples]
path: examples/cluster/plot_agglomerative_dendrogram.py
text: @user1:
```suggestion
                current_count += counts[child_idx - n_samples]
```

diff_hunk: @@ -0,0 +1,53 @@
+# Authors: Mathew Kallada, Andreas Mueller
+# License: BSD 3 clause
+"""
+=========================================
+Plot Hierarachical Clustering Dendrogram
+=========================================
+This example plots the corresponding dendrogram of a hierarchical clustering
+using AgglomerativeClustering and the dendrogram method available in scipy.
+"""
+
+import numpy as np
+
+from matplotlib import pyplot as plt
+from scipy.cluster.hierarchy import dendrogram
+from sklearn.datasets import load_iris
+from sklearn.cluster import AgglomerativeClustering
+
+
+def plot_dendrogram(model, **kwargs):
+    # Create linkage matrix and then plot the dendrogram
+
+    # create the counts of samples in each node
+    counts = np.zeros(model.children_.shape[0])
+    n_samples = len(model.labels_)
+    for i, merge in enumerate(model.children_):
+        current_count = 0
+        for j in [0, 1]:
+            if merge[j] < n_samples:
+                current_count += 1
path: examples/cluster/plot_agglomerative_dendrogram.py
text: @user1:
```suggestion
                current_count += 1  # leaf node
```

diff_hunk: @@ -0,0 +1,53 @@
+# Authors: Mathew Kallada, Andreas Mueller
+# License: BSD 3 clause
+"""
+=========================================
+Plot Hierarachical Clustering Dendrogram
+=========================================
+This example plots the corresponding dendrogram of a hierarchical clustering
+using AgglomerativeClustering and the dendrogram method available in scipy.
+"""
+
+import numpy as np
+
+from matplotlib import pyplot as plt
+from scipy.cluster.hierarchy import dendrogram
+from sklearn.datasets import load_iris
+from sklearn.cluster import AgglomerativeClustering
+
+
+def plot_dendrogram(model, **kwargs):
+    # Create linkage matrix and then plot the dendrogram
+
+    # create the counts of samples in each node
+    counts = np.zeros(model.children_.shape[0])
+    n_samples = len(model.labels_)
+    for i, merge in enumerate(model.children_):
+        current_count = 0
+        for j in [0, 1]:
path: examples/cluster/plot_agglomerative_dendrogram.py
text: @user1:
```suggestion
        for child_idx in merge:
```