scikit-learn/scikit-learn — Issue #390: cluster.Ward crashes with empty heap
Author: jmetzen
Created: 2011-10-10 12:47:37+00:00
State: open

The fit method of the Ward class crashes frequently for me with an IndexError (due to exhausting the heap used internally in the ward_tree)

The following minimalistic test case reproduces the problem:

import numpy
from sklearn.neighbors import kneighbors_graph
from sklearn.cluster import Ward

data = map(eval, ['(0.0140, 0.1020)', '(0.0141, 0.0997)', '(0.0142, 0.0967)',
'(0.0142, 0.0951)', '(0.0141, 0.0954)', '(0.0139, 0.0961)',
'(0.0134, 0.0974)', '(0.0124, 0.0991)', '(0.0111, 0.1012)',
'(0.0094, 0.1035)', '(0.0074, 0.1052)', '(0.0057, 0.1044)',
'(0.0039, 0.1033)', '(0.0018, 0.1017)', '(-0.0005, 0.0996)',
'(-0.0030, 0.0973)', '(-0.0055, 0.0951)', '(-0.0076, 0.0952)',
'(-0.0094, 0.0959)', '(-0.0106, 0.0975)', '(-0.0111, 0.0999)',
'(-0.0107, 0.1034)', '(-0.0094, 0.1048)', '(-0.0076, 0.1047)',
'(-0.0053, 0.1053)', '(-0.0028, 0.1053)', '(-0.0001, 0.1053)',
'(0.0026, 0.1053)', '(0.0055, 0.1053)', '(0.0086, 0.1053)',
'(0.0121, 0.1053)', '(0.0161, 0.1053)', '(0.0164, 0.1051)',
'(0.0158, 0.1053)', '(0.0161, 0.1053)', '(0.0168, 0.1053)',
'(0.0167, 0.1053)', '(0.0167, 0.1053)', '(0.0167, 0.1053)',
'(0.0167, 0.1053)', '(0.0167, 0.1053)', '(0.0167, 0.1053)',
'(0.0167, 0.1053)', '(0.0167, 0.1053)', '(0.0168, 0.1053)',
'(0.0168, 0.1053)', '(0.0168, 0.1053)', '(0.0168, 0.1053)',
'(0.0168, 0.1053)', '(0.0168, 0.1053)', '(0.0168, 0.1053)',
'(0.0168, 0.1052)', '(0.0168, 0.1049)', '(0.0168, 0.1044)',
'(0.0168, 0.1037)', '(0.0168, 0.1027)', '(0.0168, 0.1012)',
'(0.0168, 0.0994)', '(0.0168, 0.0971)', '(0.0168, 0.0951)',
'(0.0168, 0.0951)', '(0.0168, 0.0952)', '(0.0168, 0.0955)',
'(0.0168, 0.0964)', '(0.0168, 0.0979)', '(0.0165, 0.1002)',
'(0.0159, 0.1032)', '(0.0154, 0.1049)', '(0.0147, 0.1046)',
'(0.0138, 0.1051)', '(0.0126, 0.1053)', '(0.0112, 0.1054)',
'(0.0097, 0.1053)', '(0.0079, 0.1053)', '(0.0060, 0.1053)',
'(0.0040, 0.1053)', '(0.0020, 0.1053)', '(-0.0002, 0.1053)',
'(-0.0026, 0.1053)', '(-0.0051, 0.1053)', '(-0.0077, 0.1053)',
'(-0.0104, 0.1053)', '(-0.0132, 0.1053)', '(-0.0160, 0.1053)',
'(-0.0187, 0.1053)', '(-0.0212, 0.1054)', '(-0.0239, 0.1053)',
'(-0.0267, 0.1054)', '(-0.0296, 0.1054)', '(-0.0327, 0.1054)',
'(-0.0360, 0.1054)', '(-0.0398, 0.1054)', '(-0.0441, 0.1054)',
'(-0.0486, 0.1054)', '(-0.0533, 0.1054)', '(-0.0584, 0.1054)',
'(-0.0601, 0.1053)', '(-0.0602, 0.1054)', '(-0.0600, 0.1053)',
'(-0.0596, 0.1054)'])
X = numpy.array(data)

connectivity = kneighbors_graph(X, n_neighbors=10)
ward = Ward(n_clusters=4, connectivity=connectivity).fit(X)
labeling = ward.labels_

import pylab
for l in numpy.unique(labeling):
pylab.plot(X[labeling == l, 0],
X[labeling == l, 1],
'o', color=pylab.cm.jet(float(l) / numpy.max(labeling + 1)))
pylab.scatter(X[:,0], X[:,1], )
pylab.show()

The traceback is:

Traceback (most recent call last):
File "minimal_error.py", line 42, in
ward = Ward(n_clusters=4, connectivity=connectivity).fit(X)
File "/usr/local/lib/python2.6/dist-packages/scikit_learn-0.9-py2.6-linux-x86_64.egg/sklearn/cluster/hierarchical.py", line 314, in fit
n_components=self.n_components, copy=self.copy)
File "/usr/local/lib/python2.6/dist-packages/scikit_learn-0.9-py2.6-linux-x86_64.egg/sklearn/cluster/hierarchical.py", line 135, in ward_tree
node = heapq.heappop(inertia)
IndexError: index out of range

The problem does not occur for a more densely connected neighbor graph (e.g. kneighbors_graph(X, n_neighbors=20)). An easy fix for the problem would be to replace in hierarchical.py:

# identify the merge
while True:
node = heapq.heappop(inertia)
i, j = node[1], node[2]
if used_node[i] and used_node[j]:
break

with:

# identify the merge
while len(inertia) > 0:
node = heapq.heappop(inertia)
i, j = node[1], node[2]
if used_node[i] and used_node[j]:
break
if len(inertia) == 0: break

However, I am not sure if there is not a more subtle problem in the implementation - should it be possible that the heap gets exhausted before the merging is finished?