Improving the quality of the Turkish address records by using Levenshtein distance algorithm

Abstract

Adres bir kimsenin arandığında bulunabileceği yerdir. Bu temel kavram basit gibi görünse de doğruluğu ve tutarlılığı çok önemlidir. Günümüz dünyasında şirketlerin müşterilerine ulaşmasının temel yolu olarak kullandıkları adreslerin yanlış olmasının getirdiği mali yük oldukça fazladır. Adres yazımında yanlışlıklar Türkiye' deki bütün adresler için tam bir standart oluşturulamamasından kaynaklanmaktadır. Bu durumda kişiler adresleri kendi kafalarındaki standarda göre yazmaktadır. Bu yazım şeklinde en çok yapılan hatalar sokak, mahalle ve cadde gibi bileşenler için standart dışı kısaltmalar kullanılması; il,ilçe veya diğer adres bileşenlerinde anlamsız kısaltmalar oluşturulmasıdır.Bu çalışmanın amacı bu tip hataların tespit edilip düzeltilerek adres kalitesinin iyileştirilmesidir. Bunun için öncelikle adreslerdeki standart dışı kısaltmalar ve anlamsız karakterler tespit edilip, daha önceden belirlenmiş olan doğrularıyla değiştirilir. İl, ilçe, semt ve ya mahalle gibi bileşenlerde yapılmış kısaltmalar için ise kelimeler arasındaki benzerlikleri algılayabilcek bir algoritmaya ihtiyaç vardır. Literatürde bu ihtiyaca yönelik birçok algoritma vardır. Bu çalışmada Levenshtein uzaklık algoritmasını (LUA) esas alan bir yaklaşım kullanılmıştır. Levenshtein uzaklığı iki kelime arasındaki harf değişiklik miktarını ölçebilen bir yapıdır . Her ne kadar bu çalışmada kelime benzerliklerinin ölçümü için kullanılan temel algortima LUA olsa da, LUA üzerinde değişiklikler yapılıp elde edilen daha hızlı bir uzaklık algoritması da kullanılmıştır. Adreslerdeki standart dışı kısaltmaların değiştirilmesinden sonra adresler bileşenlerine göre sıfırdan beşe kadar altı sınıfa ayrılır. Daha sonra bu adresler üzerindeki özel durumlar tespit edilir.Gerekli bileşenler üzerinde PTT tarafından sağlanan referans adresler kullanılarak o bileşen için daha etkili olan algoritma uygulanır ve iyileştirme işlemi tamamlanır. Adres kalitesi iyileştirmesini gerçekleştirmek için bir uygulama geliştirilmiştir. Uygulama kullanılarak tekil ve ya çoklu adres iyileştirmesi gerçekleştirmek ve farklı tekniklerin sonuçlarını karşılaştırılabilmek mümkündür. Geliştirilen uygulamanın performansını ölçmek için bir finans şirketinden alınan hatalı adres kümesi kullanılmıştır. İyileştirme işleminin sonucunda adresler sahip oldukları son değerlere göre tekrar sınıflanır. Bütün işlemlerin tamamlanmasından sonra bazı adres sınıflarında yüzde 90a varan iyileştirme oranlarına ulaşılmıştır.Anahtar Kelimeler: Metin Benzerliği; Veri Temizliği; Adres Doğrulaması ; Kelime Tanıma ve Doğrulama; Levenshtein Uzaklığı.

Address is the place where someone can be found when others look for him or her. This basic notion seems simple but its accuracy and consistency are very important. The cost of inaccurate addresses which are used by companies as a basic way of contacting to their customer is quite rising. There occur mistakes in address writing because of the fact that there is no unique standardization constituted for all addresses in Turkey. Turkish addresses are mostly written in the standard of address writers? mind in this situation. Frequently done mistakes in this address writing are not using standard abbreviations for address components such as street, road, parish and using meaningless shortening on city, county or other address components.The aim of this study is finding these mistakes and improving the address quality with verification of addresses. First of all to do this, nonstandard abbreviations and meaningless characters are determined and replaced with true ones which are specified before. An algorithm is needed that can find similarity between the words to find similar words for the components of addresses such as city, county, districts or parishes which are shortened inaccurately. There are several algorithms in the literature for this purpose. In this study, an approach based on the Levenshtein Distance Algorithm (LDA) is used. Levenshtein distance is a metric for measuring the amount of difference between two sequences. Although LDA is used as a core algorithm to find similarity between words, another faster algorithm which is the modified version of LDA is also used. Addresses are classified from zero to five according to their components after abbreviation replacement operations are accomplished. Then special situation on address components are determined.Reference dataset provided by PTT is used on required address components with the algorithm which is more effective for that specified component and then improvement process is completed. An application is developed to do the address quality improvement. By using the application it is possible to do single or bulk addresses improvements and to compare the results of the different correction techniques. The incorrect address sets taken from a financial company are used to test the performance of the developed application. Addresses are reclassified according to their last values after the improvement process. As a result of all these processes, improvement rates up to 90 percent are reached for some address classes.Keywords: String Similarity; Data Cleaning; Address Verification; Text Recognition and Correction; Levenshtein Distance.