String Matching and Clustering

Question

I have a pretty simple problem. A large set of unique strings that are to various degrees not clean, and in reality they in fact represent the same underlying reality. They are not person names, but they could be. So for example Dr. John Holmes and Dr. Jon Holms are more than likely the same person. From the list of unqiue strings I want to cluster together those that possibly match the same underlying reality. There is no restrictions on the size of the cluster (i.e. I am not expecting only one match per string).

I calculate the distance between strings using the Jaro-Distance with jellyfish in python. But then I wondered how I cluster them together? I was unable to figure out how to do this using scipy clusters as I am working with strings, not floats, so I decided to work according to the following algorithm.

1. Make the first object the centroid for the first cluster
2. For the next object, calculate the similarity with each existing cluster centroid If the highest calculated similarity is over some threshold value then add the object to the relevant cluster and re-determine the centroid of that cluster, otherwise use the object to initiate a new cluster.
3. If any object remains to be clustered then return to step

Also, I decided to strip out generic components of the strings to improve the matches. In the name example above, this would give Dr. John Holmes, and J. Holmes a better chance of matching if 'Dr' is stripped out as a generic component.

I created a Stripped Class that has an attribute that is the original unique string, and then attribute that is a stripped version (stripped of the generic components). This is becasue once stripped many of the strings could have exactly the same values, and I need to be able to identify which original string they identify.

The code is posted below. It works well, except that the size/number of clusters is not independent of the order in which the strings are evaluated. So the results do differ.

In the final function, the SLink fucntion is called inside another function

I would specifically like to know if anyone knows of a better way to implement this type of clustering? If anyone has comments on how I could improve my code, and if anyone has any information about clustering strings in scipy.

In an IPython notebook I go through in more detail how I could refine this system, including using another function to verify the clusters using alternate data points relating to each string (such as age). If anyone would like to view that and offer guidance, then please see the following link:

http://nbviewer.ipython.org/gist/MajorGressingham/7876252

I think as the functions were somewhat trial and error and unplanned, they may have got a bit out of control. Any guidance appreciated. I am a researcher living in Bangladesh, a total programming data tripper sadly, but trying to get better every day.

class Stripped:
    'Common base class for all stripped stings'

    def __init__(self, original, GenericAll, GenericWhite = None, DelWhite = False):
        # Class attribute that is the string in its original format

        self.original = original
        StrVal = original.lower()
        StrVal = re.sub('[^A-Za-z0-9 ' ']+', ' ', StrVal)

        #strip out all occurences of sub-strings from GenericAll list that appear anywhere in the string
        for word in GenericAll:
            RegEx1 = re.compile('' + word)
            StrVal = re.sub(RegEx1, '', StrVal)

        # If provided as argument strip out all occurences of sub-string when that sub string is surrounded by 
        # whitespace (i.e. is not part of another substring-sequence)
        if not GenericWhite == None:
            for word in GenericWhite:
                RegEx2 = re.compile(r'\b' + word + r'\b')
                StrVal = re.sub(RegEx2, '', StrVal)

        # Removes special characters, removes all whitespace
        if DelWhite == True:
            StrVal = StrVal.replace(' ', '')

        # Class attribute that is the stipped string
        self.stripped = StrVal

GenericAll is a list of substrings to be stripped from each string wherever the sub string appears in the string. GenericWhite is a list of substrings that are stripped only if they are surrounded by whitespace.

And the function that implements the clustering

def SlinkSC(ClassList, Threshold):
#1
    random.shuffle(ClassList)


    Clusters = []
    ClustersStripped = []
    Centroid = []
    Scores = []

    for StrippedClass in ClassList:     
        SPScores = []
        Matched = 0

        if len(Clusters) == 0:
            Clusters.append([StrippedClass.original])
            ClustersStripped.append([StrippedClass.stripped])
            Centroid.append([StrippedClass.stripped, StrippedClass.original])
            Scores.append([])
            continue

        for ClustNum in xrange(len(Clusters)):
            Dist = jf.jaro_distance(StrippedClass.stripped, Centroid[ClustNum][0])
            SPScores.append(Dist)

        MaxVal = max(SPScores)
        MaxInd = SPScores.index(max(SPScores))

        if MaxVal >= Threshold:
            Clusters[MaxInd].append(StrippedClass.original)
            ClustersStripped[MaxInd].append(StrippedClass.stripped)

            if len(Scores[MaxInd]) == 0:
                Scores[MaxInd].append(MaxVal)               
            else:
                if MaxVal > Scores[MaxInd][0]:
                    Scores[MaxInd][0] = MaxVal
                    Centroid[MaxInd][0] = StrippedClass.stripped
                    Centroid[MaxInd][1] = StrippedClass.original
            Matched = 1

        if Matched ==0:       
            Clusters.append([StrippedClass.original])
            ClustersStripped.append([StrippedClass.stripped])
            Centroid.append([StrippedClass.stripped, StrippedClass.original])
            Scores.append([])

    return [Clusters, ClustersStripped, Centroid]

ClassList is a list of Stripped Class obejcts created from the unique strings that are to be clustered. Threshold is the threshold above which strings will be clustered when distance between the centorid and the string being evaluated is calcuated as the jaro-distance.

Lastly I wrote a function that sort of combines all of the above, but also clusters the clusters, and calls the clustering function recursively until no more clusters are found. It also references the data frame from which the strings are pulled. In theory, if two non-indentical strings represent the same undelying reality, this third data point should be equal for the non-identical stings that are above the Jaro-Distance threshold. This function directly modifies the data frame from which both the list of unqiue strings and the verifying data point are drawn, until no more modifications are possible.

That looks like this:

 def ClustersRecursive2(Threshold, df, col1, col2, GenericAll, GenericWhite = None, DelWhite = False):
    Styles = df[col1].unique()
    ClassList = [Stripped(style, GenericAll, GenericWhite, DelWhite) for style in Styles]
    ClustersDict = {}
    Clusters = SlinkSC(ClassList, Threshold)
    ClustersOriginal = Clusters[0]
    ClustersCentroid = Clusters[2]
    IndList = [x for x in xrange(len(ClustersOriginal)) if len(ClustersOriginal[x]) > 1]   
    MultiClusters = [ClustersOriginal[Ind] for Ind in IndList]
    MultiCentroid = [ClustersCentroid[Ind] for Ind in IndList]

   if len(MultiClusters) == 0:
        return 
    else:
        Counter = 0
        for cluster in xrange(len(MultiClusters)):
            MultiSMV = list(itertools.chain(*[df[df[col1] == elem][col2].unique() for elem in MultiClusters[cluster]]))
            if len(set(MultiSMV)) == 1:
                ClustersDict[MultiCentroid[cluster][1]] = MultiClusters[cluster]
                Counter +=1
            else:
                if len(MultiSMV) == len(MultiClusters[cluster]):
                    for smv in list(set(MultiSMV)):
                        if MultiSMV.count(smv) >= 2:
                            BoolList = [True if elem == smv else False for elem in MultiSMV]
                            StrList = [MultiClusters[cluster][x] for x in xrange(len(BoolList)) if BoolList[x] == True]
                            StrList.sort(lambda x, y: cmp(len(x), len(y)))
                            ClustersDict[StrList[0]] = StrList
                            Counter +=1

    #Cluster the Clusters
    ClusClusList = [Stripped(style, GenericAll, GenericWhite, DelWhite) for style in ClustersDict.keys()]
    ClusClusters = SlinkSC(ClusClusList, Threshold)
    ClusClusOrig = ClusClusters[0]
    ClusClusCentroid = ClusClusters[0]
    IndList2 = [x for x in xrange(len(ClusClusOrig)) if len(ClusClusOrig[x]) > 1]
    MultiClusClus = [ClusClusOrig[Ind] for Ind in IndList2]
    if len(MultiClusClus) > 0:
        for CCluster in xrange(len(MultiClusClus)):
            MultiSMVCC = list(itertools.chain(*[df[df[col1] == elem][col2].unique() for elem in MultiClusClus[CCluster]]))
            if len(set(MultiSMVCC)) == 1:
                NewList = []
                for x in xrange(1, len(MultiClusClus[CCluster])):
                    NewList.extend(ClustersDict[MultiClusClus[CCluster][x]])
                    del ClustersDict[MultiClusClus[CCluster][x]]
                ClustersDict[MultiClusClus[CCluster][0]].extend(NewList)


    StringMap = {}
    for key, value in ClustersDict.iteritems():
        for elem in value:
            StringMap[elem] = key


    if Counter == 0:
        return 
    else:
        for row in DF.index:
            try:
                df[col1][row] = StringMap[df[col1][row]]
            except KeyError:
                pass


        ClustersRecursive(Threshold, df, col1, col2, GenericAll, GenericWhite = None, DelWhite = False) 

Answer 1

Here's a quick illustration of how to use scipy.cluster.hierarchy.linkage to hierarchically cluster a group of strings according to their Jaro score. I'm not going to try to solve your actual problem, just show how to use the SciPy interface.

If you read the documentation for scipy.cluster.hierarchy.linkage you'll see that it takes as its first argument:

A condensed or redundant distance matrix. A condensed distance matrix is a flat array containing the upper triangular [part] of the distance matrix.

What does that mean? The idea is that if you have a matrix giving distances between your words, for example:

       │CHEESE CHORES GEESE  GLOVES
───────┼───────────────────────────
CHEESE │    0   0.222  0.177  0.444     
CHORES │0.222       0  0.422  0.333
GEESE  │0.177   0.422      0  0.300
GLOVES │0.444   0.333  0.300      0

Then the condensed distance matrix is a flattened array containing the numbers in the upper triangle: that is, the part of the matrix above the diagonal of zeroes. In this case, it's the array [0.222, 0.177, 0.444, 0.422, 0.333, 0.3]. Here's how to compute the condensed distance matrix:

1. Define a distance function that takes coordinates \$(i, j)\$ and returns the distance between word \$i\$ and word \$j\$. Despite the function being named jaro_distance, this score is actually a measure of similarity rather than difference, so we need to subtract it from 1 to get a distance measure.

   >>> from jellyfish import jaro_distance
   >>> words = 'CHEESE CHORES GEESE GLOVES'.split()
   >>> def d(coord):
   ...     i, j = coord
   ...     return 1 - jaro_distance(words[i], words[j])
   

2. Use numpy.triu_indices to get the coordinates of the upper triangle:

   >>> import numpy as np
   >>> np.triu_indices(len(words), 1)
   (array([0, 0, 0, 1, 1, 2]), array([1, 2, 3, 2, 3, 3]))
   

3. Use numpy.apply_along_axis to apply the distance function to the coordinates of the upper triangle just computed:

   >>> np.apply_along_axis(d, 0, _)
   array([ 0.22222222,  0.17777778,  0.44444444,  0.42222222,  0.33333333,
           0.3       ])
   

Pass this array to scipy.cluster.hierarchy.linkage:

>>> import scipy.cluster.hierarchy
>>> scipy.cluster.hierarchy.linkage(_)
array([[ 0.        ,  2.        ,  0.17777778,  2.        ],
       [ 1.        ,  4.        ,  0.22222222,  3.        ],
       [ 3.        ,  5.        ,  0.3       ,  4.        ]])

What does this mean? The documentation says:

A 4 by \$n-1\$ matrix \$Z\$ is returned. At the \$i\$th iteration, clusters with indices \$Z[i, 0]\$ and \$Z[i, 1]\$ are combined to form cluster \$n + i\$. A cluster with an index less than \$n\$ corresponds to one of the \$n\$ original observations. The distance between clusters \$Z[i, 0]\$ and \$Z[i, 1]\$ is given by \$Z[i, 2]\$. The fourth value \$Z[i, 3]\$ represents the number of original observations in the newly formed cluster.

So at the first iteration, words 0 (CHEESE) and 2 (GEESE) are combined to form a new cluster (#4) containing 2 original observations.

At the second iteration, word 1 (CHORES) and cluster #4 are combined to form a new cluster (#5) containing 3 original observations.

And at the third iteration, word 3 (GLOVES) and cluster #5 are combined to form a new cluster (#6) containing all 4 original observations.

This corresponds to the following hierarchical clustering:

                  6       
            ┌─────┴─────┐ 
            5           │
       ┌────┴────┐      │
       4         │      │
    ┌──┴──┐      │      │
 CHEESE GEESE CHORES GLOVES