python - sklearn OPTICS 和预先计算的余弦矩阵不产生簇

Question

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

但是无论我在 ma​​x_eps 和 eps 中给出什么，我都不会得到任何簇。

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

我正在为少量单词提取 fasttext 向量(每个向量 300 维)并使用 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 显然只需要计算矩阵的一半)

Answer 1

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

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

为什么你认为 eps=-1 是正确的？ OPTICS 的 min_samples 怎么样？如果你不选择相同的参数，你当然不会得到与 OPTICS 和 DBSCAN 相似的结果。

用你的参数OPTICS查到的结果是正确的。在 eps=-1 时，没有点是邻居，并且 min_samples=5 因此没有簇，所有点都应标记为 -1。