Cílem tohoto článku je navázat na přístupy pro přesný a přibližný join představené v prvním díle této série, který vyšel na tomto portálu na začátku minulého roku a ukázat možnosti výpočtu různých měr založených na tokenizaci a kalkulaci nákladů transformace řetězců s využitím nástroje SAS. Postupně vznikající framework bude použit pro benchmark jednotlivých strategií pro porovnávání a slučování. Jednotlivé algoritmy zveřejňuji, aby bylo možné kdykoliv znovu zopakovat jednotlivé fáze v rámci benchmarku realizovaných experimentů. Uvedené míry vzdálenosti lze použít uvnitř DATA STEP aplikovaného na data set představující kartézský součin možných porovnávaných řetězců.
V rámci tohoto dílu představím následující metriky vzdálenosti:
Následující kód je součástí všech níže uvedených metrik vzdálenosti a jeho výsledek představuje podklad pro výpočet charakteristik pro evaluaci příslušné strategie pro porovnávání a slučování. Evaluace vychází z tzv. Matice záměn používané běžně při zjišťování charakteristik kvality klasifikačního modelu. V rámci níže uvedeného algoritmu jsou postupně napočítávány počty příkladů, které byly pomocí příslušné metriky správně porovnávny a označeny za shodné (True-True), nesprávně označeny za shodné (True-False), nesprávně označeny za odlišné (False-True) a správně označeny za odlišné (False-False).
%macro ConfMatrix(prefix,rel=N); retain &prefix.TT &prefix.TF &prefix.FT &prefix.FF &prefix.NR; &prefix.T1 = 0; &prefix.F1 = 0; &prefix.T2 = 0; &prefix.F2 = 0; if &rel then &prefix.T1 = 1; else &prefix.F1 = 1; if &prefix.Flag = 1 then &prefix.T2 = 1; else &prefix.F2 = 1; if _N_ = 1 then &prefix.TT = &prefix.T1 * &prefix.T2; else &prefix.TT = &prefix.TT + (&prefix.T1 * &prefix.T2); if _N_ = 1 then &prefix.TF = &prefix.T1 * &prefix.F2; else &prefix.TF = &prefix.TF + (&prefix.T1 * &prefix.F2); if _N_ = 1 then &prefix.FT = &prefix.F1 * &prefix.T2; else &prefix.FT = &prefix.FT + (&prefix.F1 * &prefix.T2); if _N_ = 1 then &prefix.FF = &prefix.F1 * &prefix.F2; else &prefix.FF = &prefix.FF + (&prefix.F1 * &prefix.F2); if _N_ = 1 then &prefix.NR = 1; else &prefix.NR = &prefix.NR + 1; drop &prefix.T1 &prefix.F1 &prefix.T2 &prefix.F2; %mend ConfMatrix;
Vlastní výpočet charakteristik kvality porovnání je realizován pomocí makra ConfMatrixMeasures. Vstupními parametry tohoto makra jsou počet záznamů (NR) a prefix určující příslušnost jednotlivých napočtených statistik ke konkrétní míře podobnosti. Použitými charakteristikami jsou míra chyby, recall, senzitivita, specificita, správnost, přesnost a F1 metrika popsané např. v (Berka, 2003).
%macro ConfMatrixMeasures(NR,prefix=N); &prefix.ErrMeasure = (&prefix.FT + (&prefix.TT + &prefix.TF) / 2) / &NR; &prefix.Recall = &prefix.TT / (&prefix.TT + &prefix.TF); &prefix.Senzitivity = &prefix.TT / (&prefix.TT + &prefix.FF); &prefix.Specificity = &prefix.TF / (&prefix.TF + &prefix.FT); &prefix.Accuracy = (&prefix.TT + &prefix.TF) / (&prefix.TT + &prefix.TF + &prefix.FT + &prefix.FF); &prefix.Precission = &prefix.TT / (&prefix.TT + &prefix.FT); &prefix.F1Measure = (2 * &prefix.precission * &prefix.Recall) / (&prefix.Precission * &prefix.Recall); %mend ConfMatrixMeasures;
Parametr refSize představuje velikost referenčního atributu, inSize přestavuje velikost vstupního (porovnávaného) atributu, pomocí parametru cutoff lze nastavit prahovou hodnotu pro vyhodnocení shody (0 – 1). V případě použití kódu pro účely benchmarku při apriorní znalosti shody porovnávaných řetězců obsahuje parameter rel název primárního klíče, pomocí něhož lze ověřit správnost shody.
%macro Levenshtein(refSize,inSize,cutoff,maxobs,rel=N); /* definice polí pro jednotlivé znaky porovnávaných řetězců */ array LevRef[&refSize] $1; array LevIn[&inSize] $1; /* definice matice pro výpočet transformace vstupního řetězce na výstupní */ array LevMatrix[&refSize,&inSize] 8; /* naplnění pole pro porovnávaný řetězec */ do m = 1 to length(i) + 1; LevMatrix[m,1] = m - 1; if m <= length(i) then LevIn[m] = substr(i,m,1); end; /* naplnění pole pro referenční řetězec */ do n = 1 to length(r) + 1; LevMatrix[1,n] = n - 1; if n <= length(r) then LevRef[n] = substr(r,n,1); end; drop m n; /* vlastní výpočet nákladů transformace porovnávaného řetězce na referenční řetězec */ do z = 2 to length(i) + 1; do x = 2 to length(r) + 1; if LevRef[z-1] = LevIn[x-1] then cost = 0; else cost = 1; LevMatrix[z,x] = min( LevMatrix[z-1,x]+1, LevMatrix[z,x-1]+1, LevMatrix[z-1,x-1] + cost ); LevCosts = LevMatrix[z,x]; end; end; drop z x cost; /* nápočet skóre určující náklady transformace */ LevScore = 1 - LevCosts / max(length(i),length(r)); /* pokud je skóre vyšší než prahová hodnota, je dosaženo shody */ if LevScore >= &cutoff then LevFlag = 1; else LevFlag = 0; /* vymazání pracovních proměnných */ %do n = 1 %to &refSize; drop LevRef&n LevIn&n; %end; %do m = 1 %to %eval(&refSize * &inSize); drop LevMatrix&m; %end; /* pokud je specifikovan klic, provadi se napocet matice zamen */ %if &rel ^= "N" %then %do; %put tohle je klic: &rel; %ConfMatrix(Lev,rel=&rel); %end; /* přidání labelu pro cílové atributy */ attrib LevFlag label = "Levenshteinova vzdálenost - příznak podobnosti" LevCosts label = "Levenshteinova vzdálenost - kalkulované náklady" LevScore label = "Levenshteinova vzdálenost - kalkulované skóre" ; %mend Levenshtein;
Hammingova vzdálenost dvou numerických řetězců shodné délky je počet nekorespondujících si čísel. Podle (Batini & Scannapieco, 2006) je používána nejčastěji pro porovnávání poštovních kódů nebo identifikačních čísel sociálního pojištění. Zobecněním na všechny znaky (někdy nazýváno jako tzv. Matching coefficient) je počet neshodujících se znaků dvou řetězců.
/* refSize = velikost referenčního řetězce inSize = velikost porovnávaného řetězce cutoff = prahová hodnota */ %macro HammingDist(refSize,inSize,cutoff,maxobs,rel=N); if length(i) = length(r) then do; array HDRef[&refSize] $1; array HDIn[&inSize] $1; HDCosts = 0; do z = 1 to max(length(i),length(r)); if z <= length(r) then HDRef[z] = substr(r,z,1); if z <= length(i) then HDIn[z] = substr(i,z,1); if missing(HDRef[z]) = 1 and missing(HDIn[z]) = 1 then HDCosts = HDCosts + 0; else if HDRef[z] = HDIn[z] then HDCosts = HDCosts + 0; else HDCosts = HDCosts + 1; end; HDScore = 1 - (HDCosts / length(i)); if HDScore >= &cutoff then HDFlag = 1; else HDFlag = 0; end; else HDFlag = 0; drop z; %do n = 1 %to &refSize; drop HDRef&n HDIn&n; %end; %if &rel ^= "N" %then %do; %ConfMatrix(HD,rel=&rel); %end; attrib HDFlag label = "Hammingova vzdálenost - příznak podobnosti" HDCosts label = "Hammingova vzdálenost - kalkulované náklady" HDScore label = "Hammingova vzdálenost - kalkulované skóre" ; %mend HammingDist;
Damerau-Levenshteinova vzdálenost vychází z Levenshteinovy vzdálenosti, ale navíc uvažuje možnost výskytu překlepů. Z toho důvodu nepenalizuje v nákladech záměnu dvou po sobě jdoucích znaků v řetězci.
%macro DamLevDist(refSize,inSize,cutoff,maxobs,rel=N);
array DLRef[&refSize] $1;
array DLIn[&inSize] $1;
array DLMatrix[&refSize,&inSize] 8;
do m = 1 to length(i) + 1;
DLMatrix[m,1] = m - 1;
if m <= length(i) then DLIn[m] = substr(i,m,1);
end;
do n = 1 to length(r) + 1;
DLMatrix[1,n] = n - 1;
if n <= length(r) then DLRef[n] = substr(r,n,1);
end;
drop m n;
do z = 2 to length(i) + 1;
do x = 2 to length(r) + 1;
if DLRef[z-1] = DLIn[x-1] then cost = 0; else cost = 1;
DLMatrix[z,x] = min(
DLMatrix[z-1,x]+1,
DLMatrix[z,x-1]+1,
DLMatrix[z-1,x-1] + cost
);
/* specificka forma zohledneni preklepu */
if(z > 2 and x > 2 and DLRef[z] = DLIn[x-1] and DLRef[z-1] = DLIn[x]) then
DLMatrix[z,x] = min(
DLMatrix[z,x],
DLMatrix[z-2, x-2] + cost
);
DLCosts = DLMatrix[z,x];
end;
end;
drop z x cost;
DLScore = 1 - DLCosts / max(length(i),length(r));
if DLScore >= &cutoff then DLFlag = 1; else DLFlag = 0;
%do n = 1 %to &refSize;
drop DLRef&n DLIn&n;
%end;
%do m = 1 %to %eval(&refSize * &inSize);
drop DLMatrix&m;
%end;
%if &rel ^= "N" %then %do;
%ConfMatrix(DL,rel=&rel);
%end;
attrib
DLFlag label = "Damerau-Lavenshteinova vzdálenost - pøíznak podobnosti"
DLCosts label = "Damerau-Lavenshteinova vzdálenost - kalkulované náklady"
DLScore label = "Damerau-Lavenshteinova vzdálenost - kalkulované skóre"
;
%mend DamLevDist;
Needleman-Wunchova vzdálenost (též Sellersova vzdálenost) opět vychází z Levenshteinovy vzdálenosti s tím, že do kalkulace nákladů započítává koeficient G umožňující větší penalizaci transformací. Levenshteinovu vzdálenost lze považovat za speciální případ Needleman-Wunchovy vzdálenosti pro G = 1.
%macro NeedleWunschDist(refSize,inSize,cutoff,maxobs,G,rel=N); array NWRef[&refSize] $1; array NWIn[&inSize] $1; array NWMatrix[&refSize,&inSize] 8; do m = 1 to length(i) + 1; NWMatrix[m,1] = m - 1; if m <= length(i) then NWIn[m] = substr(i,m,1); end; do n = 1 to length(r) + 1; NWMatrix[1,n] = n - 1; if n <= length(r) then NWRef[n] = substr(r,n,1); end; drop m n; do z = 2 to length(i) + 1; do x = 2 to length(r) + 1; if NWRef[z-1] = NWIn[x-1] then cost = 0; else cost = 1; NWMatrix[z,x] = min( NWMatrix[z-1,x]+&G, NWMatrix[z,x-1]+&G, NWMatrix[z-1,x-1] + cost ); NWCosts = NWMatrix[z,x]; end; end; drop z x cost; NWScore = 1 - NWCosts / max(length(i),length(r)); if NWScore >= &cutoff then NWFlag = 1; else NWFlag = 0; %do n = 1 %to &refSize; drop NWRef&n NWIn&n; %end; %do m = 1 %to %eval(&refSize * &inSize); drop NWMatrix&m; %end; %if &rel ^= "N" %then %do; %put tohle je klic: &rel; %ConfMatrix(NW,rel=&rel); %end; attrib NWFlag label = "Needleman-Wunschova vzdálenost - pøíznak podobnosti" NWCosts label = "Needleman-Wunschova vzdálenost - kalkulované náklady" NWScore label = "Needleman-Wunschova vzdálenost - kalkulované skóre" ; %mend NeedleWunschDist;
Smith-Watermanova vzdálenost je modifikací Needleman-Wunchovy vzdálenosti s tím, že při kalkulaci nákladů zvyšuje skóre za každou shodu a snižuje za každou neshodu a rovněž parametr G namísto přičtení odečítá. Takto upravené skóre transformace maximalizuje. Podle (Batini & Scannapieco, 2006) algoritmus efektivně řeší výskyt zkratek, chybějících hodnot a překlepů.
%macro SmithWatermanDist(refSize,inSize,cutoff,maxobs,G,rel=N); array SWRef[&refSize] $1; array SWIn[&inSize] $1; array SWMatrix[&refSize,&inSize] 8; do m = 1 to length(i) + 1; SWMatrix[m,1] = m - 1; if m <= length(i) then SWIn[m] = substr(i,m,1); end; do n = 1 to length(r) + 1; SWMatrix[1,n] = n - 1; if n <= length(r) then SWRef[n] = substr(r,n,1); end; drop m n; do z = 2 to length(i) + 1; do x = 2 to length(r) + 1; if SWRef[z-1] = SWIn[x-1] then cost = 0; else cost = 1; SWMatrix[z,x] = min( SWMatrix[z-1,x]-&G, SWMatrix[z,x-1]-&G, SWMatrix[z-1,x-1] - cost ); SWCosts = SWMatrix[z,x]; end; end; drop z x cost; SWScore = 1 - SWCosts / max(length(i),length(r)); if SWScore >= &cutoff then SWFlag = 1; else SWFlag = 0; %do n = 1 %to &refSize; drop SWRef&n SWIn&n; %end; %do m = 1 %to %eval(&refSize * &inSize); drop SWMatrix&m; %end; %if &rel ^= "N" %then %do; %put tohle je klic: &rel; %ConfMatrix(SW,rel=&rel); %end; attrib SWFlag label = "Smith-Watermanova vzdálenost - příznak podobnosti" SWCosts label = "Smith-Watermanova vzdálenost - kalkulované náklady" SWScore label = "Smith-Watermanova vzdálenost - kalkulované skóre" ; %mend SmithWatermanDist;
Jaccardův koeficient porovnává délku průniku množin S a T s délkou jejich sjednocení. Je příkladem metriky založené na tokenizaci porovnávaných řetězců, tj. jejich rozdělení na jednotlivé části pomocí předem definovaného oddělovače, např. mezery.
%macro Jaccard(refSize,inSize,cutoff,maxobs,rel=N);
array JacRef[&refSize] $1;
array JacIn[&inSize] $1;
do m = 1 to length(i);
JacIn[m] = substr(i,m,1);
end;
do n = 1 to length(r);
JacRef[n] = substr(r,n,1);
end;
do w = 1 to length(i);
do v = 1 to length(i);
if w ^= v and JacIn[w] = JacIn[v] and JacIn[v] ^= '#' then JacIn[v] = '#';
end;
end;
do x = 1 to length(r);
do y = 1 to length(r);
if x ^= y and JacRef[x] = JacRef[y] and JacRef[y] ^= '#' then JacRef[y] = '#';
end;
end;
prunik = 0;
sjednoceni = 0;
/* spočtení průniku a sjednocení porovnávaného a referenčního řetězce */
do t = 1 to max(length(i),length(r));
do u = 1 to max(length(i),length(r));
if JacIn[t] ^= '#' or JacRef[u] ^= '#' then do;
if JacIn[t] = JacRef[u] then do;
prunik = prunik + 1;
JacRef[u] = '#';
end;
end;
end;
end;
do p = 1 to max(length(i),length(r));
if missing(JacIn[p]) = 0 and JacIn[p] not in ('#',' ') then sjednoceni = sjednoceni + 1;
if missing(JacRef[p]) = 0 and JacRef[p] not in ('#',' ') then sjednoceni = sjednoceni + 1;
end;
/* výpočet vlastního skóre Jaccardova koeficientu */
JacScore= prunik / sjednoceni;
/* smazání pomocných proměnných */
drop p t u x y m n v w prunik sjednoceni;
%do n = 1 %to &refSize;
drop JacRef&n JacIn&n;
%end;
/* výpočet matice záměn */
%if &rel ^= "N" %then %do;
%put tohle je klic: &rel;
%ConfMatrix(JAC,rel=&rel);
%end;
/* porovnání skóre s prahovou hodnotou */
if JacScore >= &cutoff then JacFlag = 1; else JacFlag = 0;
attrib
JacFlag label = "Jaccardův koeficient - příznak podobnosti"
JacScore label = "Jaccardův koeficient - kalkulované skóre"
;
%mend Jaccard;