Data Quality CZ - portál věnující se tématu kvalitních dat

Porovnávání řetězců s využitím nástroje BASE SAS– 2. díl

[1.12.2013] D. Pejčoch

Úvod

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ů.

Představení jednotlivých component

V rámci tohoto dílu představím následující metriky vzdálenosti:

Matice záměn

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;

Levenshteinova vzdálenost

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

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

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-Wunschova vzdálenost

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

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

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;

Použitá literatura

Komentáře ke článku

Stránka byla naposledy aktualizována dne 4.5.2015
Powered by HOLOPAGE
©2011 - 2015 D. Pejčoch