[SciPy-user] problem with spatial.kdtree.sparse_distance_matrix

[josef...@gmail.com]

I would like to get the distance_matrix of all point in a 2d array,
but it looks like kdtree cannot create a sparse distance matrix with
itself. Is this intentional, a bug, or am I doing something wrong?
Using a small distortion in the data works.
I followed the example in the testfile (BTW: in class
test_sparse_distance_matrix, M is often empty in the examples I tried,
with given r=0.3).

Josef

>>> from scipy import spatial as ssp
>>> r = 1
>>> xs2 = np.random.randn(4,50)
>>> T1 = ssp.KDTree(xs2,leafsize=2)
>>> M = T1.sparse_distance_matrix(T1, r)
Traceback (most recent call last):
File "<pyshell#73>", line 1, in <module>
M = T1.sparse_distance_matrix(T1, r)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 628, in sparse_distance_matrix
other.tree, Rectangle(other.maxes, other.mins))
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 611, in traverse
result[i,j] = d
File "\Programs\Python25\Lib\site-packages\scipy\sparse\dok.py",
line 222, in __setitem__
del self[(i,j)]
KeyError: (0, 0)
>>> T1b = ssp.KDTree(xs2.copy(),leafsize=2)
>>> M = T1.sparse_distance_matrix(T1b, r)
Traceback (most recent call last):
File "<pyshell#75>", line 1, in <module>
M = T1.sparse_distance_matrix(T1b, r)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 628, in sparse_distance_matrix
other.tree, Rectangle(other.maxes, other.mins))
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 611, in traverse
result[i,j] = d
File "\Programs\Python25\Lib\site-packages\scipy\sparse\dok.py",
line 222, in __setitem__
del self[(i,j)]
KeyError: (0, 0)

using a small distortion works:

>>> T1b = ssp.KDTree(xs2.copy()+1e-8,leafsize=2)
>>> M = T1.sparse_distance_matrix(T1b, r)
>>> len(M)
110
_______________________________________________
SciPy-user mailing list
SciPy...@scipy.org
http://projects.scipy.org/mailman/listinfo/scipy-user

[josef...@gmail.com]

On Fri, Feb 20, 2009 at 5:09 PM, <josef...@gmail.com> wrote:
> I would like to get the distance_matrix of all point in a 2d array,
> but it looks like kdtree cannot create a sparse distance matrix with
> itself. Is this intentional, a bug, or am I doing something wrong?
> Using a small distortion in the data works.
> I followed the example in the testfile (BTW: in class
> test_sparse_distance_matrix, M is often empty in the examples I tried,
> with given r=0.3).
>
> Josef
>

The problem is more general:
KDTree.sparse_distance_matrix fails when there are zero distance
points in the two trees, even if they are otherwise different.

Example:

>>> xs3 = np.random.randint(0,3,200).reshape(50,4)
>>> xs4 = np.random.randint(0,3,200).reshape(50,4)
>>> ds34 = ssp.distance_matrix(xs3,xs4)
>>> np.min(ds34)
0.0
>>> T3 = ssp.KDTree(xs3,leafsize=2)
>>> T4 = ssp.KDTree(xs4,leafsize=2)
>>> M = T3.sparse_distance_matrix(T4, r)

Traceback (most recent call last):

File "<pyshell#113>", line 1, in <module>
M = T3.sparse_distance_matrix(T4, r)

File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 628, in sparse_distance_matrix
other.tree, Rectangle(other.maxes, other.mins))
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 623, in traverse
traverse(node1.less,less1,node2.less,less2)
File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",

line 618, in traverse
traverse(node1.less,less,node2,rect2)

File "C:\Josef\_progs\building\scipy\scipy-trunk-new-r5551\dist\scipy-0.8.0.dev5551.win32\Programs\Python25\Lib\site-packages\scipy\spatial\kdtree.py",
line 611, in traverse
result[i,j] = d
File "\Programs\Python25\Lib\site-packages\scipy\sparse\dok.py",
line 222, in __setitem__
del self[(i,j)]

KeyError: (7, 19)

[Anne Archibald]

2009/2/20 <josef...@gmail.com>:

> On Fri, Feb 20, 2009 at 5:09 PM, <josef...@gmail.com> wrote:
>> I would like to get the distance_matrix of all point in a 2d array,
>> but it looks like kdtree cannot create a sparse distance matrix with
>> itself. Is this intentional, a bug, or am I doing something wrong?
>> Using a small distortion in the data works.
>> I followed the example in the testfile (BTW: in class
>> test_sparse_distance_matrix, M is often empty in the examples I tried,
>> with given r=0.3).
>>
>> Josef
>>
>
> The problem is more general:
> KDTree.sparse_distance_matrix fails when there are zero distance
> points in the two trees, even if they are otherwise different.

This was actually a bug in dok_matrix (setting an already-zero element
to zero failed), which is now fixed in SVN.

Anne

[josef...@gmail.com]

On Sat, Feb 21, 2009 at 12:03 PM, Anne Archibald
<peridot...@gmail.com> wrote:
> 2009/2/20 <josef...@gmail.com>:
>> On Fri, Feb 20, 2009 at 5:09 PM, <josef...@gmail.com> wrote:
>>> I would like to get the distance_matrix of all point in a 2d array,
>>> but it looks like kdtree cannot create a sparse distance matrix with
>>> itself. Is this intentional, a bug, or am I doing something wrong?
>>> Using a small distortion in the data works.
>>> I followed the example in the testfile (BTW: in class
>>> test_sparse_distance_matrix, M is often empty in the examples I tried,
>>> with given r=0.3).
>>>
>>> Josef
>>>
>>
>> The problem is more general:
>> KDTree.sparse_distance_matrix fails when there are zero distance
>> points in the two trees, even if they are otherwise different.
>
> This was actually a bug in dok_matrix (setting an already-zero element
> to zero failed), which is now fixed in SVN.
>
> Anne
>

thank you, I will try it out soon.

Josef