Jaro-Winkler távolság

A Jaro-Winkler távolság megméri a két húr közötti hasonlóságot . Ez egy William E. Winkler által 1999-ben javasolt változat , amely a Jaro-távolságból származik (1989, Matthew A. Jaro ), és amelyet főleg másolatok felderítésére használnak.

Az eredmény úgy normalizálódik, hogy a mértéke 0 és 1 között legyen, tehát a nulla a hasonlóság hiányát jelenti, az 1 pedig az összehasonlított húrok egyenlőségét.

Ez az intézkedés különösen alkalmas rövid karakterláncok, például nevek vagy jelszavak feldolgozására.

Távolság Jarótól

A Jaro közötti távolság láncok és határozza meg: s1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}

dj=13(m|s1|+m|s2|+m-tm){\ displaystyle d_ {j} = {\ frac {1} {3}} \ balra ({\ frac {m} {| s_ {1} |}} + {\ frac {m} {| s_ {2} | }} + {\ frac {mt} {m}} \ jobbra}}

vagy:

• |sén|{\ displaystyle | s_ {i} |}a karakterlánc hossza  ;sén{\ displaystyle s_ {i}}
• m{\ displaystyle m}az egyező karakterek száma (lásd alább);
• t{\ displaystyle t}az átültetések száma (lásd alább).

Két azonos karakter és és akkor tekinthető egymásnak megfelelőnek, ha a távolságuk (azaz a különbözõ húrokban elfoglalt pozícióik közötti különbség) nem haladja meg: s1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}

⌊max(|s1|,|s2|)2⌋-1{\ displaystyle \ left \ lfloor {\ frac {\ max (| s_ {1} |, | s_ {2} |)} {2}} \ right \ rfloor -1}.

A száma átültetések összehasonlításával kapott i-edik megfelelő jellege a a i-edik megfelelő jellege a . Az, hogy hányszor különböznek ezek a karakterek, kettővel elosztva, megadja az átültetések számát . s1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}

Jaro-Winkler távolság

A Winkler által bevezetett módszer olyan előtag-együtthatót használ, amely előnyben részesíti a ( előtaggal ) kezdődő húrokat . Figyelembe véve a két lánc és azok Jaro-Winkler távolság van: o{\ displaystyle p}ℓ{\ displaystyle \ ell}ℓ≤4{\ displaystyle \ ell \ leq 4}s1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}dw{\ displaystyle d_ {w}}

dw=dj+(ℓo(1-dj)){\ displaystyle d_ {w} = d_ {j} + (\ ell p (1-d_ {j}))}}

vagy:

• dj{\ displaystyle d_ {j}}Jaro távolsága a és közötts1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}
• ℓ{\ displaystyle \ ell} a közös előtag hossza (legfeljebb 4 karakter)
• o{\ displaystyle p}olyan együttható, amely lehetővé teszi a közös előtagú húrok előnyben részesítését. Winkler értéket kínálo=0.1{\ displaystyle p = 0,1}

Példák

Vagy két lánc: MARTHA és MARHTA . Felállítjuk a levelezési táblázatukat . Itt a maximális távolság 6/2 - 1 = 2. Az alábbi táblázat sárga négyzeteiben tehát 1-t írunk be, ha a karakterek megegyeznek (van egyezés ), és egyébként 0-t: s1{\ displaystyle s_ {1}} s2{\ displaystyle s_ {2}}

	M	NÁL NÉL	R	T	H	NÁL NÉL
M	1	0	0	0	0	0
NÁL NÉL	0	1	0	0	0	0
R	0	0	1	0	0	0
H	0	0	0	0	1	0
T	0	0	0	1	0	0
NÁL NÉL	0	0	0	0	0	1

• m=6.{\ displaystyle m = 6} (1-es szám a táblázatban)
• |s1|=6.{\ displaystyle | s_ {1} | = 6}
• |s2|=6.{\ displaystyle | s_ {2} | = 6}
• A megfelelő karakterek : {M, A, R, T, H, A} és {M, A, R, H, T, A} . Ezeknek a rendezett halmazoknak a figyelembevételével tehát 2 párunk van (T / H és H / T) különböző megfelelő karakterekkel , azaz két féltranszpozícióval. Honnans1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}t=22=1{\ displaystyle t = {\ frac {2} {2}} = 1}

Jaro távolsága:

dj=13(6.6.+6.6.+6.-16.)=0,944{\ displaystyle d_ {j} = {\ frac {1} {3}} \ bal ({\ frac {6} {6}} + {\ frac {6} {6}} + {\ frac {6-1 } {6}} \ jobbra = 0 {,} 944}

A Jaro-Winkler távolság hosszúság előtaggal válik o=0,1{\ displaystyle p = 0 {,} 1}ℓ=3{\ displaystyle \ ell = 3}

dw=0,944+(3×0,1(1-0,944))=0,961{\ displaystyle d_ {w} = 0 {,} 944+ (3 \ szor 0 {,} 1 (1-0 {,} 944)) = 0 {,} 961}

A Dwayne és DUANE láncok találunk: s1{\ displaystyle s_ {1}} s2{\ displaystyle s_ {2}}

• m=4{\ displaystyle m = 4}
• |s1|=6.{\ displaystyle | s_ {1} | = 6}
• |s2|=5.{\ displaystyle | s_ {2} | = 5}
• t=0{\ displaystyle t = 0}

Jaro távolsága:

dj=13(46.+45.+4-04)=0,822{\ displaystyle d_ {j} = {\ frac {1} {3}} \ bal ({\ frac {4} {6}} + {\ frac {4} {5}} + {\ frac {4-0 } {4}} \ jobbra = 0 {,} 822}

Jaro-Winkleré  : ℓ=1{\ displaystyle \ ell = 1}

dw=0v822+(1×0,1(1-0,822))=0,84.{\ displaystyle d_ {w} = 0v822 + (1 \ szer 0 {,} 1 (1-0 {,} 822)) = 0 {,} 84}

A DIXON és DICKSONX láncokkal a következőket kapjuk: s1{\ displaystyle s_ {1}} s2{\ displaystyle s_ {2}}

	D	én	x	O	NEM
D	1	0	0	0	0
én	0	1	0	0	0
VS	0	0	0	0	0
K	0	0	0	0	0
S	0	0	0	0	0
O	0	0	0	1	0
NEM	0	0	0	0	1
x	0	0	0	0	0

Kiszámoljuk az egyezési kritérium maximális távolságát

⌊max(|s1|,|s2|)2⌋-1=⌊8.2⌋-1=3{\ displaystyle \ left \ lfloor {\ frac {\ max (| s_ {1} |, | s_ {2} |)} {2}} \ right \ rfloor -1 = \ lfloor {\ frac {8} {2 }} \ rfloor -1 = 3}.

• m=4{\ displaystyle m = 4}(a két X nem nem egyezik , mert több, mint 3 karakter szélesek)
• |s1|=5.{\ displaystyle | s_ {1} | = 5}
• |s2|=8.{\ displaystyle | s_ {2} | = 8}
• t=0{\ displaystyle t = 0}

Jaro távolsága:

dj=13(45.+48.+4-04)=0,767{\ displaystyle d_ {j} = {\ frac {1} {3}} \ bal ({\ frac {4} {5}} + {\ frac {4} {8}} + {\ frac {4-0 } {4}} \ jobbra = 0,767}

Jaro-Winkler távolság  : ℓ=2{\ displaystyle \ ell = 2}

dw=0,767+(2×0,1(1-0,767))=0,813{\ displaystyle d_ {w} = 0 {,} 767+ (2 \ alkalommal 0 {,} 1 (1-0 {,} 767)) = 0 {,} 813}

Megjegyzések és hivatkozások

• (en) Jaro, MA , „  Advances in record linking methodology as used to the 1985 census of Tampa Florida  ” , Journal of the American Statistics Society , vol.  84, n o  406,1989, P.  414-420
• (en) Jaro, MA, „  Nagy közegészségügyi adatállomány valószínűségi összekapcsolása  ” , Statistics in Medicine , vol.  14,1995, P.  491–498 ( online olvasás )
• (en) Winkler, WE , „  A rekordok összekapcsolásának állapota és az aktuális kutatási problémák  ” , Jövedelemstatisztika részleg, Bevételi Szolgálat R99 / 04. kiadvány ,1999( online olvasás )
• (en) Winkler, WE , „  A rekordok összekapcsolásának áttekintése és az aktuális kutatási irányok  ” , kutatási jelentéssorozat, RRS ,2006( online olvasás )

Külső linkek

• (en) OpenSource megvalósítás Java-ban és .NET-ben
• (en) Eredeti megvalósítás a C
• Megvalósítás Delphiben
• Egyszerű C megvalósítás

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">