1
$\begingroup$

I want to encode names of people for similarity comparison between them such that a name like 'Sarah' is closer when represented in vector to a name like 'Sarah connor', something very similar to what word2vec does but it uses sentences to train but I only have list of words. Using string matching algorithms like Levenshtein distance and Jaccard Index, I can find similarity between them but this can't be used to derive vector embeddings of these words satisfying above conditions, or can they ? If not is there a way to encode these list of names such that the condition of similar names (based on characters and other conditions) are closer in n-dimensional space, n being the vector length of these embeddings.

$\endgroup$
1
$\begingroup$

You can do that. I propose the simplest one conditioned on the fact that number of data is not very large. In case you need more ideas please drop a comment.

In this case, you can use the idea of similarity encoding based on Fuzzy String Matching and get the spectral embedding. The amount of data is crucial here as you need to do order of $n^2$ comparisons to get affinity matrix for spectral embedding. Follow the code bellow (and get a wonderful idea from this paper)

data = ['sarah connor', 'sara jones', 'jack blabla', 'jackie jones', ' jakob blabla', 'sara conor']
n = len(data)

aff_mat = np.zeros((n,n)) # This is the S matrix in the paper
D = np.zeros((n,n))

for ii in range(n):
    for jj in range(n):
        name1 = data[ii]
        name2 = data[jj]
    
        surname1 = name1.split()[0]
        lastname1 = name1.split()[1]
    
        surname2 = name2.split()[0]
        lastname2 = name2.split()[1]
    
        aff_name1_name2 = fuzz.ratio(surname1,surname2) + fuzz.ratio(lastname1,lastname2)
        # Fuzz ratios are betweein 0 and 100 and we add 2 of them 
        # so we normalize the whole score to 0 and 1 by dividing by 200
        aff_mat[ii,jj] = aff_name1_name2/200
    
for ii in range(n):
    D[ii,ii] = np.sum(aff_mat[:,ii])

L = D - aff_mat # This is Laplacian matrix

Having the Laplacian matrix, you simply calculate the eigenvectors, directly from the code inside the paper. Here I choose second and third eigenvector as the forst eigenvector is trivial. please not that there are tones of ways to calculate Laplacian matrix and what we did here is different that the one in the paper. So despite the paper which chooses first $k$ eigenvectors, we drop the first one. For more details on this you may refer to the literature.

# compute eigenvectors / eigenvalues of L
evals, evcts = eig(L)
# extract "smallest" 2 eigenvectors (ignoring first one)
sortedevals = argsort(evals)
U = evcts[:,sortedevals[1:3]]

Now U is your embedding in 2 dimensions. Just plot and see the result:

for (x,y), label in zip(U, data):
    plt.text(x, y, label, ha='center', size=10)
plt.xlim((-1,1))
plt.ylim((-1,1))
plt.show()

and this is the result:

enter image description here

Now it's up to you how you would like to query similar names. The main job is done.

PS: As obvious above, I assumed you are interested in similarity of both first names and last names. In case you want the same code only for first name just simply take the $lastname$ variable out.

Hope it helped. Good Luck!

| improve this answer | |
$\endgroup$
  • $\begingroup$ I found this paper as well but I have a dataset of 62000 rows, calculating the matrix was taking a lot of time, I had my machine on for around 6 hours. I am thinking of a workaround of calculating similarity values based only on the initial characters of the dataset. By initial characters I will also include the initial characters of non starting words in a single word string for comparison. This is not the best method I know but it'll get me decent results. If you have any ideas regarding how to reduce the complexity from quadratic to anything below, it would be helpful $\endgroup$ – Rishabh Sharma Jun 29 at 12:00
0
$\begingroup$

I've not tried it, but it sounds like sklearn's Isomap might do the job, with metric='precomputed' and passing X as the distance matrix computed with Levenshtein/Jaccard/whatever. Have a look through the User Guide for the other manifold learning approaches, but Isomap stands out as applicable to me.

See also https://stats.stackexchange.com/q/353298/232706

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.