Seorang nasabah Bank Mandiri bernama Anto Febrianto selalu mentranfer uangnya ke BCA setiap bulan dengan nama AntoFebriant. Dari dua nama tersebut kita mungkin bisa dengan mudah memahami keduanya adalah orang yang sama. Bagaimana caranya agar sistem dapat mengetaui kalau itu adalah orang yang sama dengan cepat pada ratusan juta record transaksi setiap bulan? Hal ini dapat dilakukan dengan pengembangan teknik Levenshtein Distance. Silahkan cek wikipedia untuk mengenal Levenshtein Distance. Topik yang saya bahas disini adalah bagaimana menggunakan Leveshtein Distance untuk menyelesaikan masalah nyata di lapangan.
Hal yang perlu diperhatikan adalah sebagai berikut:
- Levenshtein Distance dari dua kata yang identik adalah 0. Misalnya PERTAMINA dan PERTAMINA memiliki distance 0 karena sama. Apabila kita bandingkan antara PERTAMINA dengan PERTAMINI nilainya adalah 1 karena ada satu karakter yang berbeda.
- Dari nilai yang obsolut diatas, tidak ada kejelasan kapan kita bisa yakin bahwa dua kalimat tertentu adalah sama meskipun distance-nya adalah 4. Kita harus mengubahnya ke dalam persentase sehingga bisa lebih intuitive menentukan treshold kesamaan dua nama.
- Beberapa stop word (kata tidak penting) harus dihapus. Pada kasus perbankan, kata kata seperti PT, Persero, Tbk, Sdr. Mrs. Ny. Tn. harus dihapus karena attribute yang tidak bisa membedakan antara nasabah yang satu dengan yang lain.
Berikut kodenya:
package com.anto.udfprm;
import java.util.HashMap;
import java.util.Map;
import org.apache.hadoop.hive.ql.exec.UDF;
import org.apache.hadoop.hive.ql.metadata.HiveException;
import org.apache.hadoop.io.Text;
public class _antoUDFLevenshtein extends UDF {
public Float evaluate(Text s1, Text s2) throws HiveException{
if (s1 == null || s2 == null) {
return null;
}
return computeLevenshteinDistance(s1.toString(), s2.toString());
}
private static int minimum(int a, int b, int c) {
if (a<=b && a<=c)
return a;
if (b<=a && b<=c)
return b;
return c;
}
private static float computeLevenshteinDistance(String s1, String s2) {
//kumpulkan daftar stop word
String stopword="SERVIS|SERVICE|HOLDING|GROUP|LEASING|(T\\.?B\\.?K\\.?)|PERSR|PERSERO|(L\\.?T\\.?D\\.?)|(P\\.?T\\.?E\\.?)|(C\\.?V\\.?)|(P\\.?T\\.?)|\\d\\d\\d*|[\\_\\-\\*\\&\\^\\%\\$\\#\\@\\(\\)\\+\\=\\`\\~\\,\\.\\/\\<\\>\"\']";
String s1String= s1.toString().toUpperCase().replaceAll(stopword, " ");
//atur spasi dan susun rapi nama standard yang baru
String[] s1_ins= s1String.split(" ");
String s1_new="";
for (String s1_in: s1_ins) {
if (s1_in.trim().length()!=0) {
s1_new = s1_new + " "+(s1_in).trim();
}
}
s1_new= s1_new.trim();
String s2String= s2.toString().toUpperCase().replaceAll(stopword, " ");
String[] s2_ins= s2String.split(" ");
String s2_new="";
for (String s2_in: s2_ins) {
if (s2_in.trim().length()!=0) {
s2_new = s2_new + " "+(s2_in).trim();
}
}
s2_new= s2_new.trim();
//Ubah huruf romawi jadi angka
Map romawi= new HashMap();
romawi.put("I", "1"); romawi.put("II", "2"); romawi.put("III", "3"); romawi.put("IV", "4"); romawi.put("V", "5");
romawi.put("VI", "6"); romawi.put("VII", "7"); romawi.put("VIII", "8"); romawi.put("IX", "9"); romawi.put("X", "10");
romawi.put("XI", "11"); romawi.put("XII", "12"); romawi.put("XIII", "13"); romawi.put("XIV", "14"); romawi.put("XV", "15");
romawi.put("XVI", "16"); romawi.put("XVII", "17"); romawi.put("XVIII", "18"); romawi.put("XIX", "19"); romawi.put("XX", "20");
s1_ins= s1_new.split(" ");
int len= s1_ins.length-1;
s1_new="";
int n=0;
for (String s1_in: s1_ins) {
if (n==len){
if (romawi.containsKey(s1_in.trim())){
s1_new = s1_new + " "+romawi.get(s1_in.trim());
} else {
s1_new = s1_new + " "+(s1_in).trim();
}
} else {
s1_new = s1_new + " "+(s1_in).trim();
}
n++;
}
s1_new= s1_new.trim();
s2_ins= s2_new.split(" ");
len= s2_ins.length-1;
s2_new="";
n=0;
for (String s2_in: s2_ins) {
if (n==len){
if (romawi.containsKey(s2_in.trim())){
s2_new = s2_new + " "+romawi.get(s2_in.trim());
} else {
s2_new = s2_new + " "+(s2_in).trim();
}
} else {
s2_new = s2_new + " "+(s2_in).trim();
}
n++;
}
s2_new= s2_new.trim();
char[] str1= s1_new.toCharArray();
char[] str2= s2_new.toCharArray();
int[][] distance = new int[str1.length+1][];
for(int i=0; i<=str1.length; i++) {
distance[i] = new int[str2.length+1];
distance[i][0] = i;
}
for(int j=0; j=lenstr2) {
if (lenstr1>dist){
return (lenstr1 - dist)/lenstr1;
} else {
return 0;
}
} else {
if (lenstr2>dist){
return ((lenstr2 - dist)/lenstr2);
} else {
return 0;
}
}
}
}
Kode tersebut dipaket ke dalam Jar kemudian diupload ke hadoop melalui Hue.
Setelah itu, fungsi di buat pada hive.
Selanjutnya diuji,
Demikian, kita sudah bisa membuat fungsi UDF pada hive dan membuat kasus menarik untuk Big Data yakni String Similarity.
