1

我正在尝试使用 HDBSCAN 算法在包含 146,000 个观察值的大型数据集上实现聚类。当我使用（默认）Minkowski/Euclidean 距离度量对这些观察结果进行聚类时，整个数据的聚类很顺利，只需要 8 秒。但是，我正在尝试使用我自己的指标执行聚类。在对数据子集进行操作时，这很好，尽管速度要慢得多。但是，当尝试在完整数据集上实现它时，我立即遇到内存错误。这是有道理的，因为由于数据集的大小，成对距离矩阵将占用大约 150GB。然而，这让我想知道使用默认度量如何没有这样的问题，同时查看 HDBSCAN 源代码显示在这种情况下还调用了 Sklearn 的成对距离，这将返回整个矩阵。

我的指标代码和一些结果：

import hdbscan
import pandas as pd
import time
import numpy as np
from numpy.linalg import norm


def spex_distance(a, b):
    euclidean = norm(a[:2] - b[:2])  
    exp_vec_a, exp_vec_b = a[2:], b[2:]  
    cos_sim = np.dot(exp_vec_a, exp_vec_b) / (norm(exp_vec_a) * norm(exp_vec_b))
    if cos_sim > 0:
        return euclidean / cos_sim
    else:
        return np.inf


def main():
    data = pd.read_pickle(file_location)
    small_data = data[:1000]

    t0 = time.time()
    hdb_custom = hdbscan.HDBSCAN(metric=spex_distance)
    hdb_custom.fit(small_data)
    print(f"Time needed for clustering subset with custom metric: {time.time()-t0}") # 10 sec

    t0 = time.time()
    hdb_default = hdbscan.HDBSCAN()
    hdb_default.fit(small_data)
    print(f"Time needed for clustering subset with default metric: {time.time()-t0}") # 0.03 sec

    t0 = time.time()
    hdb_default.fit(data)
    print(f"Time needed for clustering full dataset with default metric: {time.time()-t0}") # 9 sec

    hdb_custom.fit(data) # fails with memory error
4

1 回答 1

1

sklearn 的 BallTree 的 KDTree 支持的指标可以利用这些数据结构比计算全距离矩阵更节省内存和更快（假设数据的维度足够低，因此 BallTree 的 KDTree 是有效的）。自定义指标将需要替代代码路径，因此要困难得多。原则上，可以在 MST 构建阶段使用 Prim 算法，以便在“根据需要”的基础上计算距离，并且所需的内存比完整的成对距离矩阵要少——事实上，这就是代码的工作方式当数据维度太高而无法应用基于树的方法时，标准距离函数。这比较慢（在 O(N^2) 而不是 O(N log N) 处缩放），但会起作用。不幸的是，为了提高效率，当前的代码需要过去可以通过 C/Cython 访问的距离度量。这排除了自定义指标。可以用 C 或 Cython 编写距离函数，将其包含在源文件中，然后编译包含您的度量的 hdbscan 的自定义版本。这将允许使用较低内存的方法，但可能比您愿意做的工作更多。

于 2021-12-12T18:17:29.807 回答