<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/deep-catalan-roots-playing-with-stringdist/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://ikashnitsky.github.io/2018/deep-catalan-roots/"> Ilya Kashnitsky</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<h1>Preambule</h1>
<p>This academic year I am participating in <a rel="nofollow" href="https://www.demogr.mpg.de/en/education_career/european_doctoral_school_of_demography_1913/default.htm" target="_blank">European Doctoral School of Demography</a>. It is a unique one-year-long training for PhD students in demography. It keeps migrating across European research centers; this year Jim Vaupel’s research group in Odense hosts the program. Best demographers visit us to give us various one-week-long courses. Here we are, the EDSD cohort 2017/18:</p>
<p><a rel="nofollow" href="https://i1.wp.com/ikashnitsky.github.io/images/180604/our-cohort.jpg?ssl=1" target="_blank"><img alt="fig1" src="https://i1.wp.com/ikashnitsky.github.io/images/180604/our-cohort.jpg?w=456&ssl=1" data-recalc-dims="1"></a></p>
<h1>The creative task</h1>
<p>Back in February (yes, I know, that was a quarter of a year ago, EDSD is quite dense), <a rel="nofollow" href="https://twitter.com/VillavicencioFG" target="_blank">Francisco Villavichencio</a> gave us a fascinating lecture on probabilistic string matching. Pancho used the approach in <a rel="nofollow" href="https://link.springer.com/chapter/10.1007/978-3-319-19884-2_10" target="_blank">one of his PhD papers</a>, in which he squeezed some demographic knowledge from scarce Catalan data on marriages that happened back in 16-17 centuries. Each marriage record contains name of a bride, name and surname of a groom, and the same data for two pairs their of parents. Having data for period spanning several adjacent generations, Pancho linked kids to their parents, thus getting interval censored dataset on demographic events of Renaissance Catalans. From this data he managed to estimate life expectancy of that population! Just make sure you check the paper if you want more details:</p>
<blockquote>
<p>Villavicencio, F., Jordà, J. P., &amp; Pujadas-Mora, J. M. (2015). Reconstructing lifespans through historical marriage records of Barcelona from the sixteenth and seventeenth centuries. In <em>Population reconstruction</em> (pp. 199–216). Springer.</p>
</blockquote>
<p>Our assignment was to play with a sample of the dataset and link daughters, who got married in 1597–1629, to their possible parents, who got married in 1573–1617, using string distance metrics. But that’s not what I am about to show you.</p>
<h1>A side-walk solution</h1>
<p>While doing the assignment, I decided to check if there lived “re-incarnations” of my group-mates in Barcelona back in the day. Instead of linking daughters to parents I linked us, 20 young demographers from various countries, to Catalans from 16-17 century. Here is how I handed in the assignment =)</p>
<p><a rel="nofollow" href="https://i1.wp.com/ikashnitsky.github.io/images/180604/hand-in.jpg?ssl=1" target="_blank"><img alt="fig2" src="https://i1.wp.com/ikashnitsky.github.io/images/180604/hand-in.jpg?w=456&ssl=1" data-recalc-dims="1"></a></p>
<p>So, let’s dive into string distances and probabilistic string matching.</p>
<blockquote>
<p><strong>Important note!</strong> For the sake of post’s readability, this time I chose not to insert code chunks in the post. Instead, you are welcome to explore the <a rel="nofollow" href="https://github.com/ikashnitsky/deep-catalan-roots" target="_blank">github repo</a> that replicates all the analyses presented here. Since I cannot publish openly a big chunk of The Barcelona Historical Marriage Database, the guthub repo only contains minimal indicative data sample – 10 best matching records to each of the groupmate’s name.</p>
</blockquote>
<h1>Exploring the methods</h1>
<p>There are multiple ways to calculate string distances. Most popular are implemented in <code>stringdist</code> R package. I’m not going to present the methods themselve, just check <code>stringdist</code> <a rel="nofollow" href="https://cran.r-project.org/web/packages/stringdist/stringdist.pdf" target="_blank">documentation</a> if interested. All of the methods are pretty costly computationally. Even when each particular comparison happens quite fast, the problem is that for each person, for whom a match is being searched, we need to run the comparison with each of the records in the other dataset. Of course, when you want to use several methods and average the result of their “voting”, it takes even more time. Thus, a good idea is to narrow the list of candidates for matching as much as possible.</p>
<p>So, first I decided to compare the speed of these methods and choose the fastest for the first step comparison. Here is what I got calculating the distance between words “demography” and “democracy”.</p>
<p><a rel="nofollow" href="https://i2.wp.com/ikashnitsky.github.io/images/180604/benchmarking.png?ssl=1" target="_blank"><img alt="fig3" src="https://i2.wp.com/ikashnitsky.github.io/images/180604/benchmarking.png?w=456&ssl=1" data-recalc-dims="1"></a></p>
<p>As we see, there is quite some variation in the speed of different methods, and sometimes an iteration takes much longer than usual. The fastest method is “jw”, Jaro-Winker distance. I use it for filtering out the pairs of candidate names that definitely have nothing in common. The choice of the cutting-off threshold is, of course, arbitrary and is based on empirical tests. The trade-off here is, on the one hand, to narrow down the list of candidates for match but, on the other hand, not to throw away the possible match based on just one distance measure.</p>
<h1>Finally, let’s find our Catalan “ancestors”</h1>
<p>Instead of choosing some cut-off value I ranked the results of “jw” distance and filtered 10 best fitting results for each of the names of my fellows. For these pre-selected candidates I calculated also several other distance measures: “osa”, “lcs”, “qgram”, “cosine”, and “jaccard”. In the final tables I showed only 3 best matching results ranked by the geometric average of all the 6 calculated distances taken with equal weights.</p>
<h2>Here is the table for guys:</h2>
<p><a rel="nofollow" href="https://i1.wp.com/ikashnitsky.github.io/images/180604/edsd-males.png?ssl=1" target="_blank"><img alt="fig4" src="https://i1.wp.com/ikashnitsky.github.io/images/180604/edsd-males.png?w=456&ssl=1" data-recalc-dims="1"></a></p>
<p>My personal favorite here is <em>Hanbo Wo</em> becoming <em>Antonio Duc</em>.</p>
<h2>And a similar table for girls:</h2>
<p><a rel="nofollow" href="https://i2.wp.com/ikashnitsky.github.io/images/180604/edsd-females.png?ssl=1" target="_blank"><img alt="fig5" src="https://i2.wp.com/ikashnitsky.github.io/images/180604/edsd-females.png?w=456&ssl=1" data-recalc-dims="1"></a></p>
<p>Here I like <em>Elena Bastianelli</em> turning to <em>Elena Albanell</em>.</p>
<h1>Conclusions</h1>
<p>There are 20 people in our EDSD group, 10 guys and 10 girls. We come from different countries: Germany, Italy, China, United States, Russia, Spain, Mexico, Bosnia, Poland, Hungary, Estonia, and Denmark. Our names are quite different from that of 16-17 century Catalans. Still, using string distance matching we can find similarly named persons in the historical dataset. This fun example just exposes the power of formal text mining approach.</p>
<h1>Replication materials <a rel="nofollow" href="https://github.com/ikashnitsky/deep-catalan-roots" target="_blank">at github</a></h1>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://ikashnitsky.github.io/2018/deep-catalan-roots/"> Ilya Kashnitsky</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/p9ZLx3S_rUk" height="1"></a></div>