Near-Duplicate Clustering

Problem

Cluster items whose pairwise similarity reaches a threshold.

Union item i and j whenever sim_matrix[i][j] >= threshold, taking the transitive closure of the relation. Return cluster ids assigned in order of first occurrence (0, 1, 2, ...) for items 0..n-1.

Test cases

case 1

in: [[[1,0.9,0.1],[0.9,1,0.2],[0.1,0.2,1]],0.8]

expected: [0,0,1]

case 2

in: [[[1,0.6,0.1],[0.6,1,0.7],[0.1,0.7,1]],0.5]

expected: [0,0,0]

case 3

in: [[[1,0],[0,1]],0.1]

expected: [0,1]

Starter codePython

def cluster_duplicates(sim_matrix, threshold):
    # Your code here
    pass

3 test cases · run your code against them in the editor