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.
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() lastname1 = name1.split() surname2 = name2.split() lastname2 = name2.split() 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:
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!
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.