[BUG] cosine distance is broken on DBSCAN

[royinx]

Describe the bug

DBSCAN with cosine distance cannot perform clustering. Line print(DBSCAN_cosine.core_sample_indices_) returns [] Please reproduce the issues with the following code.

---

Also, thanks to #212 giving me the idea to debug. Since Euclidean distance is used currently, cosine distance can be supported today by normalizing your vectors to unit norm. In the meantime, we can certainly work to add cosine & L1 distance.

While i don't know what eps is the best when unit norm is used. After several attempts , seems eps=0.7 for euclidean is the closest result to DBSCAN_cosine. anyone can tell me the true value of eps transforming from cosine distance to euclidean distance ?

---

Steps/Code to reproduce bug Download testing data data.npy data_(84,512)_3clusters.npy

from sklearn import cluster
import numpy as np
import cuml
import cupy as cp

def main():
    # init data
    arr= np.load("data.npy")
    arr_norm = arr/np.linalg.norm(arr, axis=1, keepdims=True)
    arr_norm[np.isnan(arr_norm)] = 0

    # =================================== DBSCAN ===================================
    DBSCAN_cosine = cluster.DBSCAN(min_samples=5, eps=0.25, metric="cosine").fit(arr)
    labels = DBSCAN_cosine.labels_.tolist()
    print("sklean \t DBSCAN \t cosine \t", labels)

    # =================================== Optics ===================================
    optics_cosine = cluster.OPTICS(min_samples=5, max_eps=0.25, metric="cosine", cluster_method="dbscan").fit(arr)
    labels = optics_cosine.labels_.tolist()
    print("sklean \t optics \t cosine \t", labels)

    optics_euclidean = cluster.OPTICS(min_samples=5, max_eps=0.7, metric="euclidean", cluster_method="dbscan").fit(arr_norm)
    labels = optics_euclidean.labels_.tolist()
    print("sklean \t optics \t euclidean \t", labels)

    # =================================== cuML ===================================

    arr_norm = cp.array(arr_norm)
    DBSCAN_euclidean = cuml.DBSCAN(eps=0.7, min_samples=5, metric="euclidean", output_type="cupy")
    DBSCAN_euclidean.fit(arr_norm)
    labels_ = DBSCAN_euclidean.labels_
    labels_ = list(cp.asnumpy(labels_))
    print("cuML \t DBSCAN \t euclidean \t", labels_)

    arr = cp.asarray(arr)
    DBSCAN_cosine = cuml.DBSCAN(eps=0.25, min_samples=5, metric="cosine", output_type="cupy")
    DBSCAN_cosine.fit(arr)
    labels_ = DBSCAN_cosine.labels_
    labels_ = list(cp.asnumpy(labels_))
    print("cuML \t DBSCAN \t cosine \t", labels_)

    print(DBSCAN_euclidean.core_sample_indices_)
    print(DBSCAN_cosine.core_sample_indices_)

if __name__ == "__main__":
    main()

[georgeliu95]

Hey @royinx, I think this issue is caused by #5360. I reproduce it as you described:

sklean   DBSCAN      cosine      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sklean   optics      cosine      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sklean   optics      euclidean   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
cuML     DBSCAN      euclidean   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
cuML     DBSCAN      cosine      [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 20 21 22 23 24 25 26
 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
 51 52 53 54 55 56 57 58 59]
[]

After fixing it, you will get:

sklean   DBSCAN      cosine      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sklean   optics      cosine      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
sklean   optics      euclidean   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
cuML     DBSCAN      euclidean   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
cuML     DBSCAN      cosine      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 20 21 22 23 24 25 26
 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
 51 52 53 54 55 56 57 58 59]
[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 20 21 22 23 24 25 26
 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
 51 52 53 54 55 56 57 58 59]