大型数据集的HDBSCAN处理

Question

我正在尝试使用HDBSCAN算法在一个由146,000个观测数据组成的大型数据集上实现一个集群。当我用(默认的)Minkowski/欧几里得距离度量对这些观测数据进行聚类时，整个数据的聚类效果很好，只需8秒。但是，我试图用自己的度量来执行集群。当对数据的子集进行操作时，这很好，尽管速度要慢得多。但是，当试图在完整数据集上实现它时，我会立即得到一个内存错误。这是有意义的，考虑到数据集的大小，成对距离矩阵将占用大约150 up。然而，这让我想知道如何使用默认的度量没有这样的问题，同时查看HDBSCAN源代码显示，在这种情况下也调用Sklearn的配对距离，这将返回整个矩阵。此外，我想知道我的度量是否有解决办法，或者唯一的解决方案是访问+- 150 of的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支持的度量可以利用这些数据结构，与计算全距离矩阵相比，这些数据结构具有更高的内存效率和更快的速度(假设数据是低维的，因此KDTrees of BallTrees是有效的)。自定义度量将需要一个可选的代码路径，因此这要困难得多。原则上，可以将Prim的算法用于MST构建阶段，这样就可以在“需要”的基础上计算距离，并且所需的内存比完全成对的距离矩阵所需的内存要少--这实际上就是当数据太高时，代码对于标准距离函数的工作方式，而不适合基于树的方法。这是比较慢的(在O(N^2)而不是O(N log N)上缩放)，但是会工作。不幸的是，为了提高效率，当前代码需要通过C/Cython访问的距离度量。这就排除了自定义度量。可以用C或Cython编写距离函数，包括源文件，并编译包含度量的自定义hdbscan版本。这将允许一个较低的内存方法工作，但可能是比你愿意做的更多的工作。