python - Scipy 聚类；使用物理闵可夫斯基度量？

Question

所以今天早上我了解到 Minkowski 度量并不总是意味着；

请参阅wolfram了解详情。

显然在 scipy 中它只是一个 p-范数。 Scipy 可以选择对 p 范数进行加权，但只能使用正权重，因此无法实现相对论 Minkowski 度量。

我想对相对论 4 维空间中的点进行层次聚类。两点；

a = [a_time, a_x, a_y, a_z]

b = [b_time, b_x, b_y, b_z]<​​

它们之间的距离应该是；

invarient_s(a, b) = sqrt(-(a_time-b_time)^2 + (a_x-b_x)^2 + (a_y-b_y)^2 + (a_z-b_z)^2)

我正在使用 python 工作，最好使用 scipy 的 fcluster 。在我编写自己的集群之前，是否可以在 fcluster 中获取此指标？我可以添加到可用指标列表中吗？

编辑；看起来只有 fclusterdata首先支持指标。

Answer 1

坏消息是内置指标(尤其是名为 Minkowski 的指标)确实不支持负权重。我怀疑这样做的原因是，在适当的指标中，当且仅当 x = y 时，才可以有 d(x,y) = 0，这是违反的闵可夫斯基度量。这可能是 scipy 中的任何加权指标都不支持负权重的原因，另请参阅 this github thread 中的注释.

好消息是 scipy.cluster.hierarchy.fclusterdata 的文档有问题( now fixed in master )，因为它声称

metric: str, optional

    The distance metric for calculating pairwise distances.
    See distance.pdist for descriptions and linkage to verify
    compatibility with the linkage method.

而实际的 implementation of fclusterdata只需将 metric 输入参数传递给 pdist ，它允许自定义可调用对象作为 metric 传递:

metric: str or function, optional

果然，我们可以定义自己的 Minkowski 度量函数并将其传递给 fclusterdata，但我们必须确保所有点在空间上分离，否则我们会得到复杂的距离和 pdist 将大声失败(提示“有限”数据，因为 np.sqrt 当给定负数时将返回 nan 和 nan 在 linkage 中的 np.isfinite 检查失败)。有了这个合理的警告，类似以下的作品就可以了:

from scipy.cluster.hierarchy import fclusterdata 
from numpy.random import default_rng  # only for dummy data 

# generate random data, use new random machinery for best practices 
N = 10 
rng = default_rng() 
X = rng.random((N, 4)) * [0.01, 1, 1, 1]  # make them all space-like 

def physical_minkowski(v1, v2): 
    """Return the proper Minkowski metric for 4-vectors with signature -+++"""
    return np.sqrt(([-1, 1, 1, 1] * v1).dot(v2)) 

fclusterdata(X, t=1, metric=physical_minkowski)                               
# returns uninteresting array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], dtype=int32)

由于上述函数可能会被调用很多次，因此使用 numba.njit 对其进行编译以提高性能可能是有意义的。只需要进行一点小小的更改即可实现这一点:

import numba

@numba.njit 
def jitted_minkowski(v1, v2): 
    return np.sqrt((np.array([-1, 1, 1, 1]) * v1).dot(v2)) 

我使用 IPython 的内置 %timeit 魔法和 N = 1000 对上述两个指标函数进行了计时，以进行合理的比较:

>>> %timeit scipy.spatial.distance.pdist(X, metric=physical_minkowski)
... %timeit scipy.spatial.distance.pdist(X, metric=jitted_minkowski)
2.2 s ± 90.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
385 ms ± 12.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这意味着对于较大的 4 向量集，JIT 编译版本的速度要快 5 倍，并且编译只需完成一次(您甚至可以将编译后的函数缓存在磁盘上，这样就不必编译每次运行脚本时都会发生)。