# String Matching and Clustering

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)

• (i) Do you have any test data? (ii) Can you explain in more detail why you decided not to use any of the methods in scipy.cluster.hierarchy? – Gareth Rees Dec 10 '13 at 11:32
• Actually I would love to use scipy, but didn't understand the mechanics of doing that. The jaro-distance does not obey triangulation rules, so I'm not sure it is possible. The Jaccard metric is available in scipy hierachy methods, but I kept getting a message saying that my strings could not become floats when creating the matrix. Backstory is I posted this on stackoverflow basically asking for help with scipy and I was referred here as I actually have code. – Woody Pride Dec 10 '13 at 14:59
• So it sounds as if you tried to use one of the SciPy clustering methods (which one?) but couldn't figure out how to use it, so you gave up and wrote your own. Is that right? – Gareth Rees Dec 10 '13 at 15:35
• That pretty much sums it up! Basically I know little about clustering, and found the above simple program format and decided to write my own. I looked into hierarchical clustering but essentially got stuck even creating the matrix. I'm not familiar with the package, and don't fully understand the method. I was looking at hierarchical clustering as k-means seemed tough as I would have no idea how to specify k. Plus I can fully get my head around jaro distance (hamming etc. just does not seem as good) and that metric is not available with scipy. Should I go back and try with scipy you reckon? – Woody Pride Dec 10 '13 at 15:39
• Also, could not work out how to do it with strings. Would I have to convert them to a float somehow? or to unicode? – Woody Pride Dec 10 '13 at 15:39

## 1 Answer

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

• hey, thanks so much, ive not got round to looking at this yet today, but i will tomo. I see you edited my jellyfish question. Should i split out the jaro distance question? It turns out the levenshtein one is buggy, its been confirmed by the developer, the jaro distance bug has not been confirmed (i may have got it wrong). – Woody Pride Dec 11 '13 at 18:26
• Amazing! Very short and useful, they probably should include similar functionality in any data-processing software like Excel, etc – Kochede May 8 '15 at 10:13
• Do anyone know how implement this in javascript? – Isak La Fleur May 18 '17 at 7:36