2

我正在尝试使用sklearn.cluster.OPTICS对已计算的相似度（距离）矩阵进行聚类，该矩阵中填充了归一化余弦距离（0.0 到 1.0）

但无论我在max_eps和eps中给出什么，我都没有得到任何集群。

稍后我需要在超过 129'000 x 129'000 个项目的相似矩阵上运行 OPTICS，希望依靠 Dask 来保持低内存占用。

我正在为少量单词（每个向量 300 维）提取 fasttext 向量，并使用 dask-distance 从向量创建相似度矩阵。

结果是一个如下所示的矩阵：

sim == [[0.         0.56742118 0.42776633 0.42344265 0.84878847 0.87984235
  0.87468601 0.95224451 0.89341788 0.80922083]
 [0.56742118 0.         0.59779273 0.62900345 0.83004028 0.87549904
  0.887784   0.8591598  0.80752158 0.80960947]
 [0.42776633 0.59779273 0.         0.45120935 0.79292425 0.78556189
  0.82378645 0.93107747 0.83290157 0.85349163]
 [0.42344265 0.62900345 0.45120935 0.         0.81379353 0.83985011
  0.8441614  0.89824009 0.77074847 0.81297649]
 [0.84878847 0.83004028 0.79292425 0.81379353 0.         0.15328565
  0.36656755 0.79393195 0.76615941 0.83415538]
 [0.87984235 0.87549904 0.78556189 0.83985011 0.15328565 0.
  0.36000894 0.7792588  0.77379052 0.83737352]
 [0.87468601 0.887784   0.82378645 0.8441614  0.36656755 0.36000894
  0.         0.82404421 0.86144969 0.87628284]
 [0.95224451 0.8591598  0.93107747 0.89824009 0.79393195 0.7792588
  0.82404421 0.         0.521453   0.5784272 ]
 [0.89341788 0.80752158 0.83290157 0.77074847 0.76615941 0.77379052
  0.86144969 0.521453   0.         0.629014  ]
 [0.80922083 0.80960947 0.85349163 0.81297649 0.83415538 0.83737352
  0.87628284 0.5784272  0.629014   0.        ]]

例如，我可以使用 0.8 的阈值进行聚类

from dask import array as da
import dask_distance
import logging
import numpy as np
from sklearn.cluster import OPTICS
from collections import defaultdict

log = logging.warning
np.set_printoptions(suppress=True)


if __name__ == "__main__":
    array = np.load("vectors.npy")
    vectors = da.from_array(array)

    sim = dask_distance.cosine(vectors, vectors)

    sim = sim.clip(0.0, 1.0)

    m = np.max(sim)

    c = OPTICS(eps=-1, cluster_method="dbscan", metric="precomputed", algorithm="brute")
    clusters = c.fit(sim)

    words = [
        "icecream",
        "cake",
        "cream",
        "ice",
        "dog",
        "cat",
        "animal",
        "car",
        "truck",
        "bus",
    ]
    cs = defaultdict(list)
    for index, c in enumerate(clusters.labels_):
        cs[c].append(words[index])
    for v in cs.values():
        log(v)
    log(clusters.labels_)

哪个打印

['icecream', 'cake', 'cream', 'ice', 'dog', 'cat', 'animal', 'car', 'truck', 'bus']
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

但我原以为会有几个集群。

我已经为 OPTICS 中所有受支持的参数尝试了许多不同的值，但无法产生任何可用的或什至比一个更多的集群。

我正在使用以下版本：

python -V
Python 3.7.3

sklearn.__version__
'0.21.3'

dask.__version__
'2.3.0'

numpy.__version__
'1.17.0'

这是使用 sklearn DBSCAN 代替的外观

...
sim = sim.astype(np.float32)
c = DBSCAN(eps=0.7, min_samples=1, metric="precomputed", n_jobs=-1)
clusters = g.fit(sim)
...

产量

['icecream', 'cake', 'cream', 'ice']
['dog', 'cat', 'animal']
['car', 'truck', 'bus']
[0 0 0 0 1 1 1 2 2 2]

这是非常正确的，但内存占用要高得多（OPTICS 显然只需要计算矩阵的一半）

4

1 回答 1

2

您是否尝试过估计一个 129000x129000 矩阵需要多少内存 - 以及计算和使用它需要多长时间？！？我强烈怀疑 dask 在扩展这个方面是否会有帮助。您首先需要使用一些索引方法来避免任何 O(n²) 成本。用 k 个节点将 O(n²) 减少 k 倍并不足以让您达到可扩展的程度。

当您使用 时"precomputed"，您已经计算了完整的距离矩阵。现在，OPTICS 和 DBSCAN 都不会再次计算它（也不会只计算它的下半部分）——它们只会迭代这个巨大的矩阵，因为它们不能对它做出任何假设：即使它是对称的也不行。

为什么你认为eps=-1是对的？光学呢min_samples？如果不选择相同的参数，当然不会得到 OPTICS 和 DBSCAN 相似的结果。

OPTICS 使用您的参数找到的结果是正确的。没有任何点eps=-1是邻居，min_samples=5因此没有集群，所有点都应该标记为-1。

于 2019-09-11T07:11:14.633 回答