时间戳

首页 > 解决方案 > Scipy 聚类；使用物理闵可夫斯基度量？

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

问题描述

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

http://mathworld.wolfram.com/MinkowskiMetric.html 有关详细信息，请参见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 首先支持指标。

标签： pythonscipy

解决方案

坏消息是确实内置的指标（尤其是名为 Minkowski 的指标）不支持负权重。我怀疑这样做的原因是，在适当的度量中，您只能拥有d(x,y) = 0当且仅当x = y，这违反了 Minkowski 度量。这可能是在任何加权指标中缺乏对负权重的支持的原因scipy，另请参阅此 github 线程中的注释。

好消息是文档有问题scipy.cluster.hierarchy.fclusterdata（现在在 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.

而实际实现fclusterdata只是将metric输入参数传递给pdist，这允许自定义可调用对象传递为metric：

metric: str or function, optional

果然，我们可以定义自己的 Minkowski 度量函数并将其传递fclusterdata给给定一个负数将返回，并且无法签入）。有了这个合理的警告，类似以下的作品：pdistnp.sqrtnannannp.isfinitelinkage

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 倍，并且只需编译一次（您甚至可以将编译后的函数缓存在磁盘上，这样就不必每次都编译你运行你的脚本）。

推荐阅读