HDBSCAN 处理大型数据集

Question

我正在尝试使用 HDBSCAN 算法对包含 146,000 个观测值的大型数据集实施聚类。当我使用（默认）Minkowski/Euclidean 距离度量对这些观察结果进行聚类时，整个数据的聚类效果很好，仅需 8 秒。但是，我正在尝试使用我自己的指标执行聚类。在对数据的子集进行操作时，这很好，尽管速度要慢得多。但是，当尝试在完整数据集上实施它时，我立即收到内存错误。这是有道理的，因为由于数据集的大小，成对距离矩阵将占用大约 150GB。然而，这让我想知道使用默认度量怎么没有这样的问题，同时查看 HDBSCAN 源代码表明在这种情况下还调用了 Sklearn 的成对距离，这将 return 整个矩阵。此外，我想知道我的指标是否有解决方法，或者唯一的解决方案是否是访问 +- 150GB 的 RAM。

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

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

Answer 1

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

HDBSCAN 处理大型数据集

HDBSCAN handling of large datasets

python

cluster-analysis

hdbscan