Skip to main content

Disambiguation Step 3: Clustering by Similarity Score

1. Constructing Canopies | 2. Applying Similarity Metrics | 3. Clustering by Similarity Score| 4. Clustering Algorithms Evaluation

The next step in the disambiguation process is to use a clustering algorithm to group mentions together. We use hierarchical agglomerative clustering to cluster inventors, assignees, and locations.

  1. Compute the similarity score for each pair of mentions within each canopy.
  2. Group together the two most similar records. For assignees, if there are more than 1,000 records in the canopy, only a sample are compared as described above for inventors, to reduce computational overhead.
  3. Repeat the comparisons between all mentions and the newly formed clusters from step 2.
    1. For assignees, the similarity between the cluster and any other mention is defined as the maximum similarity between any element in the cluster and the mention it is being compared with.[1]
    2. For locations, the similarity between the cluster and any other mention is defined as the similarity between the concatenation of all mentions in the cluster and the mention it is being compared with. Groups are represented by the canonical name when comparing similarity measures between a group and a mention.
  4. Each time records are clustered together, they form a node in the group that we are creating.
  5. After all the records in a canopy are formed into a group, the final clusters are any groups whose similarity score exceeds the empirically determined threshold.

All records in a canopy become clustered based on similarity scores. Each time records are clustered together, they form a node in a tree. After all records are formed into a tree, the final clusters are a subtree whose similarity score exceeds a determined threshold. To incrementally add data to a clustering produced by hierarchical agglomerative clustering, we use agglomerative clustering’s incremental variant, Grinch.[2]

 

[1] This is called single linkage.

[2] Monath, N., Kobren, A., Krishnamurthy, A., Glass, M. R., & McCallum, A. (2019). Scalable hierarchical clustering with tree grafting. In KDD '19: The 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1438–1448). Association for Computing Machinery. http://bit.ly/grinch_paper