nltk/nltk — Issue #154: nltk.cluster.KMeansClusterer.cluster() raises AssertionError
Author: alexrudnick
Created: 2012-01-17 06:27:18+00:00
State: open

NLTK default installation on Ubuntu 10.10, nltk.__version__=='2.0b8'

"""What is the expected output? What do you see instead?"""

When using the nltk.cluster.KMeansClusterer, an AssertionError is raised in
nltk/cluster/kmeans.py/_centroid() (line 154) on this line of code:

def _centroid(self, cluster):
assert len(cluster) > 0

The problem occurs in the function that calls it, _cluster_vectorspace().
In the following lines of code, it is possible that self.classify_vectorspace()
never returns a particular index and the list at that index in clusters will be
empty. When _centroid is mapped over clusters, that empty list will cause an
AssertionError:

clusters = [[] for m in range(self._num_means)]
for vector in vectors:
index = self.classify_vectorspace(vector)
clusters[index].append(vector)
...
new_means = map(self._centroid, clusters)

"""What steps will reproduce the problem? (e.g. include Python source code)"""
I've attached a bzipped tarball of a pickle file with the list of numpy arrays
I'm attempting to cluster. Entering these commands in the interactive
console will reproduce the problem exactly:

Python 2.6.6 (r266:84292, Sep 15 2010, 16:22:56)
[GCC 4.4.5] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from pickle import Unpickler
>>> from nltk.cluster.kmeans import KMeansClusterer
>>> from nltk.cluster import cosine_distance
>>> with open('numpy_arrays.pickle', 'rb') as fh:
... arrays = Unpickler(fh).load()
...
>>> kmc = KMeansClusterer(11, cosine_distance, repeats=50)
>>> clusters = kmc.cluster(arrays, assign_clusters=True, trace=True)
k-means trial 0
iteration
iteration
clusters=11
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/lib/pymodules/python2.6/nltk/cluster/util.py", line 51, in cluster
self.cluster_vectorspace(vectors, trace)
File "/usr/lib/pymodules/python2.6/nltk/cluster/kmeans.py", line 70, in cluster_vectorspace
self._cluster_vectorspace(vectors, trace)
File "/usr/lib/pymodules/python2.6/nltk/cluster/kmeans.py", line 110, in _cluster_vectorspace
new_means = map(self._centroid, clusters)
File "/usr/lib/pymodules/python2.6/nltk/cluster/kmeans.py", line 154, in _centroid
assert len(cluster) > 0
AssertionError

Migrated from http://code.google.com/p/nltk/issues/detail?id=666