Bulanık Mantık Text Alan Arama Eşleşmede NAME
Transkript
Bulanık Mantık Text Alan Arama Eşleşmede NAME
04.06.2011 Bulanık Mantık Text Alan Arama Eşleşmede NAME-3 Teknolojisi Yazan : Koray Korkut Copyright © 2011 Askon Bilişim 1 04.06.2011 İçindekiler 1 TEXT ALANLAR ÜZERİNDE YAPILAN ARAMA / EŞLEME İŞLEMLERİNDE VARYASYON PROBLEMİ .... 3 2 VARYASYON PROBLEMİNİ AŞMAK İÇİN DİĞER KLASİK METODLAR ................................................. 4 3 2.1 Soundex ve Benzeri Metodlar ................................................................................................. 4 2.2 Eşleştirme Kodları .................................................................................................................... 4 NAME-3 TEKNOLOJİSİ ...................................................................................................................... 5 3.1 Çoklu Anahtarlar...................................................................................................................... 6 3.2 Arama Aralıkları ....................................................................................................................... 7 3.3 Eşleştirme Amaçları ................................................................................................................. 7 Copyright © 2011 Askon Bilişim 2 04.06.2011 1 TEXT ALANLAR ÜZERİNDE YAPILAN ARAMA / EŞLEME İŞLEMLERİNDE VARYASYON PROBLEMİ Veritabanındaki bir kaydı kişi adı, firma adı, adres, konu gibi alanlar üzerinden arama/eşleme ihtiyacı pek çok uygulamada karşımıza çıkıyor. Bu uygulamalara aşağıdaki temel örnekleri verebiliriz; TC Kimlik Numarası, Vergi Numarası gibi bir ID numarası olmayan mevcut şahıs ya da kurumsal müşterilerin ünvan,kimlik,adres,telefon bilgileri kullanılarak tekilleştirilmesi. Yeni müşteri kaydı yaratılırken kişinin ya da firmanın mevcut bir müşteri olup olmadığı kontrolü. Müşteri numarasını bilmeyen bir müşterinin çağrı merkezini aradığında kaydına kimlik bilgileri ile ulaşılması. Telemarketing kampanyalarında potansiyel müşteri listesinin mevcut müşteriler ile karşılaştırılarak gereksiz aramaların önlenmesi. İstihbarat ya da pazarlama faaliyetleri amacıyla aynı evde oturan hane halkının tespiti. Ne var ki bu gibi free text alanlar varyasyona son derece açık alanlardır. Bu sebeple bu gibi alanlar üzerinde arama yaparken aradığımız kayda varyasyonlara rağmen ulaşmak için çok kullanılan yöntemlerden biri Wildcard arama metodur. Nispeten az sayıda kayıt içeren veritabanlarında Wildcard metodu aranan kayıtların sonuç setine dahil edilmesi için etkili bir metoddur ancak milyonlarca kayıt içeren bir veritabanında dönen sonuç seti o kadar büyük olur ki içinden aradığımız kaydı seçmek imkansız hale gelmektedir. Her durumda Wildcard metodu ile dönen kayıtların aradığımız kayıt olup olmadığını teyyit için gözle kontrol gerekmektedir. Wildcard metodu insan müdahelesi gerektirmeyen otomatik prosesler için uygun değildir. Sonuç olarak Wildcard metodu kurumsal uygulamalarda text arama eşleme ihtyaçlarını karşılamak için yetersiz kalmaktadır. Free text alanlarda varyasyon problemini aşmak için kullanılan diğer alternatif metodlara geçmeden önce bu varyasyonların sebeplerine kısaca değinmekte fayda var. Bunların bazılarını aşağıdaki şekilde sınıflandırabiliriz. Hatalar o Typographic hatalar ( Klavyede yanlış tuşa basmaktan kaynaklanan yazım hataları ) o Fonotik hatalar ( Spelling hataları ) Copyright © 2011 Askon Bilişim 3 04.06.2011 Yazım formatından ve ortamından kaynaklanan farklılıklar o Karakter seti farklılıkları o Büyük, küçük harf farkları o Kısaltmalar o Kelime sıralamasındaki farklar o Eksik ya da fazla kelimeler Bu varyasyonlara aşağıdaki örnekleri gösterebiliriz. Ahmet Levent Öztürk Ahmet Levend Öztürk Ahmet Öztürk Ahmet L. Öztürk Levent Öztürk Hamidiye Mah. Serakent Sit. Petunya Blk. D:8 34408 Kağıthane/İstanbul Hamidiye Mh. Serakent Sit. Söyler Cd. Petunya Blok Da:8 Kağıthane/İST Askon Bilişim Danışmanlık ve Ticaret Ltd. Şti. Askon Bilişim Dan. Ve Tic. Ltd. Şti. Türkiye Radyo Televizyon Kurumu TRT 2 VARYASYON PROBLEMİNİ AŞMAK İÇİN DİĞER KLASİK METODLAR Bahsettiğimiz problemleri aşmak için yetersiz kaldığı noktaları yukarıda açıkladığımız Wildcard metodu ile birlikte aşağıdaki yöntemler de geliştirimiştir. 2.1 Soundex ve Benzeri Metodlar Bu tip metodlar kelimeleri fonotik kurallar ve tipik yazım hatalarını göz önüne alarak stabil kodlara çevirme algoritmalarına dayanır. Bu şekilde hata ve varyasyona rağmen kelimeler aynı stabil koda dönüştürülmeye çalışılır. Bu algoritmalar İngilizce fonotik kuralları göz önüne alınarak geliştirildiğinden Türkçe kelimelerde çok etkin olamamaktadır. Ayrıca kelime bazlı metodlar olup birden fazla kelime içeren alanlardaki eksik/fazla kelimelerden ve sıralama farklarından oluşan varyasyonları kompanse etmek için tasarlanmamışlardır. Aynı şekilde kısaltmaları da kompanse edemezler. 2.2 Eşleştirme Kodları Bu yaklaşım kaydı oluşturan alanların bir kısmının kombinasyonundan eşleştirme kodları üretilmesine dayanır. Mesela kişi ad ve soyadının ilk üçer harfi ve doğum yılı birleştirilerek bir kod oluşturulur ve bu kod veritabanında kaydı indekslemek için kullanılır. Eğer tek bir kod ile yetinmeyip her kayıt için farklı alan kombinasyonlarında birden fazla kod oluşturulursa bu metod kısmen başarılı olmaktadır Copyright © 2011 Askon Bilişim 4 04.06.2011 ancak yine de dönen sonuç setindeki kaydın aranan kayıt olup olmadığına karar vermek için insan kontrolü gerekmektedir. Bu metod da insan müdahalesi olmadan eşleşme kararı vermesi gereken otomatik prosesler için uygun değildir. 3 NAME-3 TEKNOLOJİSİ Yukarıdaki açıklamalardan çıkarımda bulanabileceğimiz şekilde ideal text alan arama/eşleme çözümü aşağıdaki özelliklere sahip olmalıdır. 1. Doğru kayıtları kaçırmadan veritabanından çekilecek aday kayıt setini mantıklı ölçüde küçültebilmeli. 2. İnsan kontrolüne gerek kalmadan aday kayıtların eşleşme kararını verebilmeli. 3. Performansı kabul edilebilir sınırlar içerisinde olmalı. Hızla genişleyen müşteri veritabanları text alan arama eşleme sistemleri üzerinde yukarıdaki saydığımız üç özelliğin tümünü sağlama konusunda baskı yaratmaktadır. Bu özelliklerin tümünü sağlayan dünyadaki en güçlü teknoloji aşağıda detaylarını anlatacağımız NAME-3 teknolojisidir. NAME-3 teknolojisi Avustralya’da çok sayıda gelen göçmen başvuru kayıtlarının eşleştirilmesi amacı ile ilk olarak tasarlanmıştır ve konusunda dünyadaki en etkin algoritmayı içermektedir. NAME-3 isim (her türlü text alanı gerçek hayatta bir öğeyi temsil eden isim olarak kabul edebiliriz) alanları üzerinde üç farklı aşamada gerçekleşen bir arama/eşleme algoritmasıdır. Bu aşamalar aşağıdaki şekilde sıralanmaktadır. 1. Çoklu Anahtarlar ( Multiple Keys ) 2. Arama Aralıkları ( Search Ranges ) 3. Eşleştirme Amaçları ( Matching Purposes ) NAME-3 Teknolojisini veritabanındaki tüm kayıtlar için çoklu anahtarlar yaratılması, arama sırasında hangi anahtar kombinasyonlarının veritabanından çekileceğine karar verilmesi ve son olarak veritabanından çekilen aday kayıtların belirlenen alanlar kullanılarak puanlanması olarak özetleyebiliriz. Copyright © 2011 Askon Bilişim 5 04.06.2011 NAME-3 Algoritması Çoklu Anahtarlar Arama Aralıkları Eşleştirme Amaçları •Veritabanındaki tüm kayıtlar için birden fazla kelime kombinasyonu içerecek şekilde oluşturulur. •Kelimelerin rastlanma sıklığına göre seçiciliği ayarlanır. •Farklı kelime sıralamaları ve kombinasyonlarına göre anahtarlar üzerinden arama yapılarak aday kayıt seti belirlenir. •İş amacının gerektirdiği performans/kalite dengesine uygun olarak tarama genişliği farklılaştırılabilir. •İş amacına uygun olarak aday kayıtların belirlenen alanlar üzerinden puanlanmasını sağlar. •Eşik puanı geçen aday kayıtlar eşleşmiş kabul edilir. 3.1 Çoklu Anahtarlar İsmi oluşturan olası farklı kelime kombinasyonları için birden fazla arama anahtarı yaratılarak veritabanında saklanır. Bu şekilde kelime sıralamasındaki farklar ya da eksik/fazla kelimeler kompanse edilmiş olur. Çoklu anahtarlar çoğunlukla ad-soyad, ünvan, adres gibi tek bir alan üzerinde yaratılır. ( Ancak çok büyük veritabanlarında aday kayıt setini daha da küçültmek için tercihen birden fazla alan kullanılabilir ). Anahtarlar yaratılırken seçici olmayan, alanların çoğunda geçen kelimeler için anahtar yaratılmaz. Buna örnek olarak şirket ünvanlarındaki Limited, Ltd., Şti., Ticaret, Tic. gibi kelimeleri verebiliriz. Bunlar NAME-3 algoritmasında Noise Word olarak adlandırılırlar ve ülkeye has look-up tablolarında saklanırlar ve her alan tipi için (Şahıs Adı, Şirket Adı, Adres vs..) farklı olarak tanımlanabilirler . Yine kayıtların çoğunda olmayan ancak çok sık rastlanan kelimer anahtarların ancak ikincil kısmında kullanılırlar. Bunlara şirket ünvanlarındaki İnşaat, Bankası, Hastanesi, Müdürlüğü vs.. gibi kelimeleri örnek verebiliriz. Bunlar NAME-3 algoritmasında Minor Word olarak adlandırılır ve yine ülkeye has look-up tablolarda saklanır. (Ülkeye ve dile özel bu tanımların tutulduğu dosyaya Name-3 algoritmasında popülasyon dosyası adı verilmektedir ). Noise ve Minor word tanımlarında olmayan her kelime Major word olarak kabul edilir. Çoklu anahtarlar yaratılırken isimdeki her Major-Major ve Major-Minor kombinasyonu için farklı bir anahtar yaratılır. Ancak isimde hiç Major kelime yok ise tek başına Minor kelime içeren anahtar yaratılmaktadır. Major kelimelerin rastlanma sıklığının da anahtar yaratılması sırasında etkisi vardır. Bunun için yeterince çok sayıda kayıt içeren bir örnek veri seti üzerinde frekans analizi yapılır ve bu frekans analizi sonucu da popülasyon dosyasına kaydedilir. Anahtarlar yaratılırken Major word nispeten sık rastlanan bir kelime ise bu anahtarın toleransı daha dar tutulur (zira toleransa izin verildiği ölçüde zaten büyük olan aday kayıt seti daha da büyüyecektir ) Copyright © 2011 Askon Bilişim 6 04.06.2011 ancak Major word nispeten az rastlanan bir kelime ise bu anahtarın toleransı geniş tutulur(aday kayıt seti küçük olacağından makul seviyede farklılaşmış kayıtlar da aday setine dahil edilebilir) . Bu şekilde anahtarlar tek bir alan üzerinde yaratılmasına rağmen doğru kayıtları yakalayabilirken aday kayıt setini yeteri kadar küçültecek seviyede seçici olabilmektedir. Anahtarların tek bir alan üzerinde yaratılması ancak yine de yeteri kadar seçici olması aramanın bütün alanlara bağımlı olmasını önleyerek hataların maksimum derecede tolere edilmesini sağlamaktadır. 3.2 Arama Aralıkları Aramayı gerektiren iş amacına uygun olarak veritabanından aranan kayıt ile benzer kayıtları çekmek için daha önce yaratılmış çoklu anahtar kombinasyonlarının hangi genişlikte taranacağına algoritma tarafından karar verilir. Bazı uygulamalarda aranan kaydın kaçırılmasından doğacak risk büyük olurken bekleme süresinin nispeten uzun olması tolere edilebilir. Örneğin sahteciliği önleme amaçlı otomatik çalışan bir tarama prosesi kayıt başına 10 saniye beklemeyi tolere edebilir. Böyle bir uygulamada olası bütün kombinasyonları tarayan geniş bir arama aralığı tercih edilebilir. Ancak Call Center’da müşteri ismiyle kaydı arayan kullanıcı için bu bekleme süresi tolere edilebilir seviyede değildir. Burada ekrana en olası seçenekler süratle getirilmelidir. Bu sebeple dar bir arama tercih edilecektir. Kullanıcı aradığı kaydı bulamaz ise farklı bir kombinasyon yazarak tekrar aramayı deneyebilir ancak %95 durumda aradığı kayıt ilk aramada gelecektir. Ne kadar genişlikte bir arama yapılacağına bağlı olarak aranan isimdeki kelimelerin farklı sıralamasındaki kombinasyonları içeren anahtarlar da aramaya dahil edilebilir. Şimdiye kadar anlatılanlardan çıkarım yapılabileceği üzere çoklu anahtarlar iş amacına uygun arama aralıkları ile birlikte kullanıldığında hem kelime sıralamasındaki farklar, hem de eksik fazla kelimelerden doğan farkları kompanse edebilecek bir esneklik sunmaktadır. 3.3 Eşleştirme Amaçları Yukarıda belirttiğimiz gibi veritabanından aday kayıtların çekilmesi anahtarlar vasıtasıyla gerçekleşir. Ancak genellikle anahtarlar tek başına aradığımız kaydı diğer kayıtlar içerisinden ayırmak için yeterli değildir. Gelen aday kayıtları iş amacımıza uygun olan alanlar listesi üzerinden puanlayarak her kaydın bizim aradığımız kayda ne kadar benzediğini derecelendiren bir sisteme ihtiyacımız vardır. NAME-3 algoritması bu amaçla Eşleştirme Amaçlarını kullanır. Eşleştirme Amacı kısaca eşleştirmede hangi alanların kullanılacağını ve bu alanların nispi ağırlık katsayısını içeren bir tanımlamadır. Aranan kayıt ve aday kayıtların her biri her bir alan üzerinden 0-100 arasında bir puanlama üzerinden eşleştirilerek puanlanır ve her alanın puanı tanımlı katsayı ile çarpılır. Bulunan puan toplam katsayıya bölünerek her aday kayıt için 0-100 arasında bir eşleşme puanı ortaya çıkar. İş amacına uygun bir eşik seviyesi belirlenerek belli bir puanın üzerindeki kayıtların otomatik olarak eş olduğu kararı verilebilir. Yine tercihe göre belli bir puan aralığı insan kontrolü gerektiren gri bölge olarak tanımlanabilir. Eşik seviyesinin altında kalan kayıtlar farklı kabul edilerek değerlendirmeye alınmayabilir. NAME-3 eşleştirme algoritması onlarca parametre içerebilen kompleks ve bir o kadar da esnek bir algoritmadır.( Mesela Eşleşme Amacı tanımında hangi alanın hangi puan altında kalırsa katsayısının sıfır olarak kabul edileceği gibi parametreler vardır. Adres, telefon gibi değişebilen alanların eşleşmeme durumunda puana negatif etkisi olsun istemeyiz ama eşleşir ise pozitif etkisi olsun isteriz. Bu parametre bunun gibi durumlar için kullanılmaktadır. ) Copyright © 2011 Askon Bilişim 7 04.06.2011 Dünyanın en büyük müşteri veritabanlarında başarı ve performans ile uygulanan NAME-3 teknolojisi bir dizi el değişikliğinden sonra bugün dünyada Veri Entegrasyon teknolojileri konusunda lider firmalardan biri olan Informatica tarafından satın alınmış ve bu firmanın ürünleri içerisinde text arama/eşleme çekirdek teknolojisi olarak kullanılmaktadır. Copyright © 2011 Askon Bilişim 8