nltk/nltk — Issue #151: SVD in VectorSpaceClusterer is broken with recent version of numpy
Author: alexrudnick
Created: 2012-01-17 06:27:14+00:00
State: open

What version of NLTK are you using? 2.0b8 (the relevant code at http://nltk.googlecode.com/svn/trunk/doc/api/nltk.cluster.util-pysrc.html is the same)

I am running this in Python 2.7 with version 1.5.0 of numpy.

What steps will reproduce the problem?

>>> import numpy
>>> from nltk import cluster
>>> from nltk.cluster.util import euclidean_distance
>>> vector_lists = [[1,1,2,3,1],[2,2,3,1,4],[6,4,2,1,5],[6,3,6,1,3],[1,1,5,3,9],[8,6,7,4,6],[6,7,5,7,4],[6,3,2,1,3],[5,5,5,5,5],[6,3,2,5,4],[6,4,3,2,5],[6,4,3,5,2],[5,4,3,2,7],[6,5,6,5,4],[6,5,6,5,4],[3,4,3,4,2],[3,4,3,4,7],[3,4,3,4,1],[4,5,6,4,4]]
>>> vectors = [numpy.array(f) for f in vector_lists]
>>> kmc = cluster.KMeansClusterer(2,euclidean_distance,svd_dimensions=2,initial_means=[[0,0,0,0,1],[0,0,0,1,0]])
>>> clustered = kmc.cluster(vectors,True,True)

This produces errors due to apparently outdated uses of numpy in VectorSpaceClusterer. For example:

* Line 42 has array(vectors), which should be numpy.array(vectors)
* Line 44 has numpy.Float64, which should be numpy.float64
* Line 47 uses numpy.matrixmultiply(S, Dt), which should be numpy.dot(S, Dt) per http://www.mail-archive.com/numpy-discussion@lists.sourceforge.net/msg01519.html

Even with those three fixes, I get the following output:

k-means trial 0
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/util.py", line 51, in cluster
self.cluster_vectorspace(vectors, trace)
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/kmeans.py", line 70, in cluster_vectorspace
self._cluster_vectorspace(vectors, trace)
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/kmeans.py", line 101, in _cluster_vectorspace
index = self.classify_vectorspace(vector)
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/kmeans.py", line 125, in classify_vectorspace
dist = self._distance(vector, mean)
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/util.py", line 114, in euclidean_distance
diff = u - v
ValueError: shape mismatch: objects cannot be broadcast to a single shape

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

earlier comments

neatnate said, at 2011-04-08T17:18:12.000Z:

Hmm, I had chosen initial_means in the original space. Now if I replace all instances of numpy.matrixmultiply() with numpy.dot(), and pick centroids in the reduced-dimensionality space, I get the following:

>>> import numpy
>>> from nltk import cluster
>>> from nltk.cluster.util import euclidean_distance
>>> vector_lists = [[1,1,2,3,1],[2,2,3,1,4],[6,4,2,1,5],[6,3,6,1,3],[1,1,5,3,9],[8,6,7,4,6],[6,7,5,7,4],[6,3,2,1,3],[5,5,5,5,5],[6,3,2,5,4],[6,4,3,2,5],[6,4,3,5,2],[5,4,3,2,7],[6,5,6,5,4],[6,5,6,5,4],[3,4,3,4,2],[3,4,3,4,7],[3,4,3,4,1],[4,5,6,4,4]]
>>> vectors = [numpy.array(f) for f in vector_lists]
>>> kmc = cluster.KMeansClusterer(2,euclidean_distance,svd_dimensions=2,initial_means=[[-1,0],[-1,1]])
>>> clustered = kmc.cluster(vectors,True,True)
k-means trial 0
iteration
iteration
iteration
iteration
iteration
iteration
iteration
[[-0.51776743 -0.43321962 -0.43745199 -0.38135288 -0.45545953]
[ 0.3050992 0.28111006 -0.03706012 0.32361216 -0.84958421]] [[ -3.4254092 0.6333413 ]
[ -5.41752109 -2.01348651]
[ -8.37303758 -1.0433937 ]
[ -8.77870686 0.22642419]
[ -8.38144145 -6.27451273]
[-14.06178981 0.0649765 ]
[-12.81771016 2.48001331]
[ -7.0288989 0.37466466]
[-11.12625727 0.11588546]
[ -9.00976995 0.81952909]
[ -9.19184246 -0.75684166]
[ -8.96952249 2.76274746]
[ -9.58499409 -2.76110927]
[-11.62601715 1.23350875]
[-11.62601715 1.23350875]
[ -7.03486733 1.52383771]
[ -9.312165 -2.72408334]
[ -6.57940779 2.37342192]
[-10.20912942 0.2996982 ]]
Traceback (most recent call last):
File "", line 1, in
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/util.py", line 56, in cluster
return [self.classify(vector) for vector in vectors]
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/site-packages/nltk-2.0b8-py2.7.egg/nltk/cluster/util.py", line 69, in classify
vector = numpy.dot(self._Tt, vector)
ValueError: matrices are not aligned

I think the multiplication it's trying to perform is between

[[-0.51776743 -0.43321962 -0.43745199 -0.38135288 -0.45545953]
[ 0.3050992 0.28111006 -0.03706012 0.32361216 -0.84958421]]

and

[-3.4254092 0.6333413]

Is the issue that part of the code assumes the centroids are in the reduced-dimensionality space, while another part assumes they are in the original space?

neatnate said, at 2011-04-08T18:09:17.000Z:

I think I've fixed it by requiring the initial_means argument to be of the original dimensionality and then projecting it to the target space. Will post a patch shortly.