Scipy稀疏-距离矩阵（Scikit或Scipy）

Question

我正在尝试在Scikit-learn的DictVectorizer返回的Scipy稀疏矩阵上计算最近邻聚类。但是，当我尝试使用Scikit-learn计算距离矩阵时，无论是通过pairwise.euclidean_distances还是pairwise.pairwise_distances使用“欧几里得”距离，都会收到错误消息。我原本以为Scikit-learn可以计算这些距离矩阵。

我的矩阵高度稀疏，形状为：<364402x223209稀疏矩阵，类型为，在压缩稀疏行格式中有728804个存储元素>。

我还尝试了Scipy中的pdist和kdtree等方法，但收到了其他无法处理结果的错误。

请问有人可以指点我一个有效的解决方案，使我能够计算距离矩阵和/或最近邻结果吗？

一些示例代码：

import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.neighbors import NearestNeighbors
from sklearn.metrics import pairwise
import scipy.spatial

file = 'FileLocation'
data = []
FILE = open(file,'r')
for line in FILE:
    templine = line.strip().split(',')
    data.append({'user':str(int(templine[0])),str(int(templine[1])):int(templine[2])})
FILE.close()

vec = DictVectorizer()
X = vec.fit_transform(data)

result = scipy.spatial.KDTree(X)

错误：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Library/Frameworks/Python.framework/Versions/3.2/lib/python3.2/site-packages/scipy/spatial/kdtree.py", line 227, in __init__
    self.n, self.m = np.shape(self.data)
ValueError: need more than 0 values to unpack

同样地，如果我运行：

scipy.spatial.distance.pdist(X,'euclidean')

我得到以下结果：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Library/Frameworks/Python.framework/Versions/3.2/lib/python3.2/site-packages/scipy/spatial/distance.py", line 1169, in pdist
    [X] = _copy_arrays_if_base_present([_convert_to_double(X)])
  File "/Library/Frameworks/Python.framework/Versions/3.2/lib/python3.2/site-packages/scipy/spatial/distance.py", line 113, in _convert_to_double
    X = X.astype(np.double)
ValueError: setting an array element with a sequence.

最后，使用scikit-learn中的NearestNeighbor会导致内存错误：

nbrs = NearestNeighbors(n_neighbors=10, algorithm='brute')

- user2694306

---

你遇到了什么样的错误？你正在运行哪些代码？ - jorgeca

请将以下信息编辑到您的问题中：一个最小的示例，展示您正在做什么，以及您遇到的实际错误。 - jorgeca

谢谢！现在看起来好多了。 - jorgeca

您想计算X的所有行之间的距离吗？因此需要一个大小为364402x364402的数组？ - Juh_

是的和不是。由于它是一个稀疏矩阵，我希望能够智能计算距离并将结果存储在类似稀疏矩阵的数据结构中。这与Mahout的处理方式类似。 - user2694306

Answer 1

首先，您不能在稀疏矩阵中使用KDTree和pdist，必须将其转换为密集型（您可以选择是否这样做）：

>>> X
<2x3 sparse matrix of type '<type 'numpy.float64'>'
        with 4 stored elements in Compressed Sparse Row format>

>>> scipy.spatial.KDTree(X.todense())
<scipy.spatial.kdtree.KDTree object at 0x34d1e10>
>>> scipy.spatial.distance.pdist(X.todense(),'euclidean')
array([ 6.55743852])

其次，来自文档：

对于小数据样本而言，高效的暴力邻居搜索方法可能非常有竞争力。然而，随着样本数N的增长，暴力方法很快变得不可行。

你可以尝试使用“ball_tree”算法，并查看它是否能够处理你的数据。

- alko

---

我原本尝试了Ball Tree算法，但它给出了一个警告，表示必须回退到暴力算法。你知道有哪些基于Python的方法可以实际计算这些维度的矩阵上的稀疏距离矩阵吗？ - user2694306

你的欧几里得距离矩阵必须是密集型的（可能没有任何零值，我猜），因此它需要占用超过74 GB的内存空间。我怀疑这根本不可能。 - alko

Answer 2

根据您的评论：

由于它是一个稀疏矩阵，我希望能够智能计算距离并将结果存储在类似的稀疏矩阵中。

基本数学表明，只有在输入矩阵包含大量重复项的情况下才可能实现这一点，因为欧几里得距离仅对两个完全相等的点为零（这实际上是距离公理之一）。因此，如果删除重复项，则可能起作用。

否则，根据您的问题，您可能可以使用sklearn.metrics.pairwise_distances_argmin_min或余弦相似性X * X.T，其排序顺序与欧几里得距离相反。

- Fred Foo