Skip to content

polyfuzz.linkage

single_linkage(matches, min_similarity=0.8)

Single linkage clustering from column 'From' to column 'To'

matches contains three columns: From, To, and Similarity where Similarity is already the minimum similarity score and thus no checking for minimum similarity is necessary.

Parameters:

Name Type Description Default
matches DataFrame

contains the columns From, To, and Similarity used for creating groups

required
min_similarity float

minimum similarity between strings before they can be merged into a group

0.8

Returns:

Type Description
clusters

The populated clusters cluster_mapping: The mapping from a string to a cluster cluster_name_map: The mapping from a string to the representative string in its respective cluster

Source code in polyfuzz\linkage.py
def single_linkage(matches: pd.DataFrame,
                   min_similarity: float = 0.8) -> Tuple[Mapping[int, List[str]],
                                                         Mapping[str, int],
                                                         Mapping[str, str]]:
    """ Single linkage clustering from column 'From' to column 'To'

    `matches` contains three columns: *From*, *To*, and *Similarity* where
    *Similarity* is already the minimum similarity score and thus no checking
    for minimum similarity is necessary.

    Arguments:
        matches: contains the columns *From*, *To*, and *Similarity* used for creating groups
        min_similarity: minimum similarity between strings before they can be merged into a group

    Returns:
        clusters: The populated clusters
        cluster_mapping: The mapping from a string to a cluster
        cluster_name_map: The mapping from a string to the representative string
                          in its respective cluster
    """
    matches = matches.loc[matches.Similarity > min_similarity, :]

    cluster_mapping = {}
    cluster_id = 0

    for row in matches.itertuples():

        # If from string has not already been mapped
        if not cluster_mapping.get(row.From):

            # If the to string has not already been mapped
            if not cluster_mapping.get(row.To):
                cluster_mapping[row.To] = cluster_id
                cluster_mapping[row.From] = cluster_id
                cluster_id += 1

            # If the to string has already been mapped
            else:
                cluster_mapping[row.From] = cluster_mapping.get(row.To)

    # Populate the clusters
    clusters = {}
    for key, value in cluster_mapping.items():
        clusters.setdefault(value, [])
        clusters[value].append(key)

    cluster_name_map = {key: clusters.get(value)[0] for key, value in cluster_mapping.items()}

    return clusters, cluster_mapping, cluster_name_map