Skip to main content
 首页 » 编程设计

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

2024年11月01日12linjiqin

我正在尝试使用 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 显然只需要计算矩阵的一半)

请您参考如下方法:

您是否尝试过估计一个 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。