Definíciók

Egyszerűen fogalmazva két objektum hasonlósága annak numerikus mértéke, hogy a két objektum mennyire hasonló. Ebből következik, hogy a hasonlóság nagyobb olyan objektumpárokra, amelyek jobban hasonlítanak egymáshoz. A hasonlóságok általában nemnegatívak és gyakran 0 (nincs hasonlóság) és 1 (teljes hasonlóság) közötti értékeket vesznek fel.

Két objektum különbözősége annak numerikus mértéke, hogy a két objektum mennyire különböző. A különbözőségek kisebbek az egymásra jobban hasonlító objektumpárokra. Előfordul, hogy a távolság kifejezést a különbözőség szinonimájaként alkalmazzák, bár, mint látni fogjuk, a távolságot gyakran a különbözőségek egy speciális csoportjára értik. A különbözőségek esetenként a [0;1] intervallumba esnek, de a 0-tól ∞ -ig terjedő tartomány alkalmazása is gyakori.

Transzformációk

Gyakran alkalmazunk transzformációkat, hogy hasonlóságot különbözőséggé alakítsunk, illetve megfordítva, különbözőséget hasonlósággá, vagy hogy úgy alakítsunk át egy szomszédsági mértéket, hogy egy megadott intervallumba, például a [0;1] -be essen. Lehetnek például olyan hasonlósági mértékeink, amelyek tartománya 1 és 10 közé esik, de a konkrét algoritmus vagy szoftver, amivel dolgozunk, lehet hogy úgy lett megtervezve, hogy csak különbözőségekkel, vagy csak [0;1] intervallumba eső hasonlóságokkal működik. Azért itt tárgyaljuk ezeket a kérdéseket, mert ilyen transzformációkat fogunk alkalmazni a későbbiekben, a szomszédság tárgyalása során. Továbbá, ezek a kérdések aránylag függetlenek a konkrét szomszédsági mértékek részleteitől.

A szomszédsági mértékek, főleg a hasonlóságok, gyakran úgy vannak definiálva vagy transzformálva, hogy az értékeik a [0;1] intervallumba essenek. Ennek röviden az az oka, hogy olyan skálát használjunk, amely a hasonlóság (vagy különbözőség) arányát mutatja két objektum között. Általában az ilyen transzformáció viszonylag egyszerű. Ha például az objektumok közötti hasonlóságok 1-től (egyáltalán nem hasonló) 10-ig (teljesen hasonló) terjednek, egy s'=(s−1)/9 transzformáció alkalmazásával elérhetjük, hogy a [0;1] intervallumba essenek, ahol s és s' az eredeti, illetve az új hasonlósági értékeket jelölik. Általánosabban, a hasonlóságok [0,1] intervallumra való leképezését a következő kifejezés adja: s'=(s−mins)/(maxs−mins) , ahol maxs és mins a maximális, illetve a minimális hasonlósági értékeket jelölik. Hasonlóképpen, a véges terjedelmű különbözőségi mértékeket is leképezhetjük a [0;1] intervallumra, a d'=(d−mind)/(maxd−mind) képlet alkalmazásával.

Azonban a szomszédsági mértékek [0;1] intervallumra történő leképezése során különböző komplikációk léphetnek fel. Ha például a hasonlósági mérték eredetileg a [0;∞] intervallumból veszi fel értékeit, akkor nemlineáris transzformációra van szükség, és az új skálán nem lesz ugyanolyan a kapcsolat az értékek között. Tekintsük a d'=d/(1+d) transzformációt egy olyan különbözőségi mértékre, amely értékei 0-tól ∞ -ig terjednek. A 0, 0,5, 2, 10 és 1000 különbözőségi értékekből rendre a 0, 0,33, 0,67, 0,90, 0,99 és 0,999 új különbözőségi értékek fognak előállni. Az eredeti különbözőségi skálán szereplő nagy értékek az 1-hez közeli értékek körül besűrűsödnek, de az, hogy ez előnyös-e vagy sem, az alkalmazástól függ. Egy másik lehetséges bonyodalom, hogy megváltozhat a szomszédsági mérték jelentése. Például a korreláció, amelyet később tárgyalunk, egy olyan hasonlósági mérték, mely a [−1;1] intervallumból veszi fel az értékeit. Ha úgy képezzük le a [0;1] intervallumra, hogy vesszük az abszolút értékét, elveszítjük az előjel-információkat, amelyek egyes alkalmazásoknál fontosak lehetnek. Lásd a 22. feladatot a 97. oldalon.

A hasonlóságok különbözőségekké alakítása és ennek megfordítása is viszonylag egyszerű, bár itt is felmerül a jelentés megőrzésének és a lineáris skálák nemlineárissá való átalakulásának kérdése. Ha a hasonlóság (vagy különbözőség) a [0;1] intervallumba esik, akkor a különbözőséget (hasonlóságot) a következőképpen definiálhatjuk: d=1−s ( s=1−d ). Egy másik egyszerű megközelítés, ha a hasonlóságot a különbözőség ellentettjeként definiáljuk (vagy fordítva). Ezt szemléltetendő, a 0, 1, 10 és 100 különbözőségi értékek rendre a 0, −1 , −10 és −100 hasonlósági értékekké transzformálhatók.

A negáció transzformáció eredményeképpen előálló hasonlóságok nincsenek a [0;1] terjedelemre korlátozva, de ha ez szükséges, alkalmazhatunk olyan transzformációkat, mint az s= 1 d+1 , s= e −d , vagy s=1− d−mind maxd−mind . Az s= 1 d+1 transzformáció alkalmazásával a 0, 1, 10, 100 különbözőségeket rendre a következő értékekké alakítjuk: 1, 0,5, 0,09, 0,01. Az s= e −d transzformációval ezekből rendre az 1,00, 0,37, 0,00, 0,00 értékek, míg az s=1− d−mind maxd−mind alkalmazásával rendre az 1,00, 0,99, 0,00, 0,00 értékek állnak elő. Ebben a részben a különbözőségek hasonlóságokká alakítására koncentráltunk. Az ellenkező irányú konverziót a 98. oldalon a 23. feladatban tárgyaljuk.

Általánosságban, bármilyen monoton csökkenő függvény felhasználásával átalakíthatunk különbözőségeket hasonlóságokká, és fordítva. Természetesen más tényezőket is figyelembe kell venni mind a hasonlóságok különbözőségekké alakításakor, mind ennek fordítottja esetén, mind pedig egy szomszédsági mérték értékeinek más skálára való leképezésekor. Megemlíthetjük a jelentés megőrzésével, a skála torzulásával és az adatelemző eszközök követelményeivel kapcsolatos kérdéseket, de ez a lista nyilván nem teljes.

A több attribútummal rendelkező objektumok szomszédságát általában úgy határozzuk meg, hogy azok egyedi attribútumainak szomszédságait egyesítjük, ezért először az egyetlen attribútummal rendelkező objektumok szomszédságát tárgyaljuk. Tekintsük az egyetlen névleges attribútummal leírt objektumokat. Mit jelentene két ilyen objektum esetén, hogy hasonlóak? Mivel a névleges attribútumok csak az objektumok különbözőségéről hordoznak információkat, csak azt mondhatjuk, hogy két objektumnak ugyanaz-e az értéke vagy sem. Ezért ebben az esetben hagyományosan úgy definiáljuk a hasonlóságot, hogy értéke 1, ha az attribútumok megegyeznek és 0 egyébként. A különbözőséget ellentétes módon definiálhatjuk: 0, ha az attribútumok megegyeznek, és 1, ha nem.

Egyszerű sorrendi attribútummal rendelkező objektumok esetén a helyzet bonyolultabb, mivel figyelembe kell vennünk a sorrendre vonatkozó információkat. Tekintsünk egy olyan attribútumot, ami egy termék, például egy csokiszelet minőségét méri a {gyenge,elfogadható,átlagos,jó,finom} skálán. Ésszerűnek tűnik, hogy egy P1 termék, amely értékelése finom, közelebb van egy P2, jó értékelésű termékhez, mint egy P3 termékhez, amelynek értékelése átlagos. Hogy ezt a megfigyelést számszerűsítsük, a sorrendi attribútum értékeit gyakran leképezzük egymást követő egész számokra, 0-tól vagy 1-től kezdve, például {gyenge=0,elfogadható=1,átlagos=2,jó=3,finom=4} . Ekkor d(P1,P2)=3−2=1 , vagy ha azt akarjuk, hogy a különbözőség értéke 0 és 1 közé essen, d(P1,P2)= 3−2 4 =0,25 . Sorrendi attribútumok hasonlóságát s=1−d módon definiálhatjuk.

A hasonlóság (különbözőség) sorrendi attribútumokra adott ezen definíciója valószínűleg kényelmetlen érzést kelt az Olvasóban, mivel egyenlő távolságokat tételez fel, pedig ez nincs így. Ellenkező esetben intervallum vagy hányados attribútumunk lenne. Vajon az elfogadható és a jó értékek között tényleg ugyanannyi a különbség, mint az átlagos és a finom értékek között? Valószínűleg nem, de a gyakorlatban korlátozottak a lehetőségeink, és további információk hiányában ez a sorrendi attribútumok közötti szomszédság definiálásának szabványos módja.

Intervallum vagy hányados attribútumokra a két objektum különbözőségének magától értetődő mértéke az értékeik abszolút különbsége. Összehasonlíthatjuk például a jelenlegi súlyunkat az egy évvel korábbi súlyunkkal úgy, hogy ``10 kilóval nehezebb vagyok''. Az ehhez hasonló esetekben a különbözőségek jellemzően inkább 0-tól ∞ -ig terjednek, mint 0-tól 1-ig. Az intervallum vagy hányados attribútumok hasonlósága jellemzően egy, a korábban leírtakhoz hasonló, a különbözőséget hasonlósággá alakító transzformáció révén fejezhető ki.

A 2.7. táblázat összegzi ezeket a részeket. Ebben a táblázatban x és y a két objektum, amelyek egy, a jelölt típusba tartozó attribútummal rendelkeznek. Emellett d(x,y) illetve s(x,y) jelöli x és y különbözőségét illetve hasonlóságát. Más megközelítések is lehetségesek, azonban ezek a leggyakoribbak.

A következő két szakaszban összetettebb szomszédsági mértékekkel foglalkozunk, amelyek több attribútumot tartalmazó objektumokra vonatkoznak: (1) adatobjektumok különbözőségeivel és (2) adatobjektumok hasonlóságaival. Ez a felosztás teszi lehetővé számunkra, hogy még természetesebben mutassuk be az alkalmazott szomszédsági mértékek mögötti indokokat. Hangsúlyozzuk azonban, hogy a hasonlóságok különbözőségekkel, illetve fordítva, a különbözőségek hasonlóságokká alakíthatóak át a korábban leírt módokon.

Ebben a szakaszban különböző típusú különbözőségekkel foglalkozunk. A távolságok tárgyalásával kezdjük, amelyek meghatározott tulajdonságokkal rendelkező különbözőségek, és ezután adunk példákat általánosabb különbözőségekre.

Távolságok

Először néhány példát mutatunk, majd a távolság egy formálisabb definícióját adjuk az összes távolságra érvényes közös tulajdonságok alapján. Két pont, x és y közötti d euklideszi távolságot egy-, két-, három- vagy magasabb dimenziójú térben a következő képlettel adjuk meg:

d(x,y)= ∑ k=1 n ( x k − y k ) 2 , (2.1)

ahol n a dimenziók száma, és x k illetve y k pedig x és y k -adik attribútumai (koordinátái). Ezt a képletet a 2.15. ábrával és a 2.8. és 2.9. táblázatokkal szemléltetjük, melyek egy ponthalmazt, ezen pontok x és y koordinátáit, és az ezen pontok párjainak távolságát tartalmazó távolsági mátrixot mutatják.

(2.1) egyenlet által adott euklideszi távolsági mértéket (2.2) egyenletben leírt Minkowski távolság metrika általánosítja:

d(x,y)= ( ∑ k=1 n | x k − y k | r ) 1/r , (2.2)

ahol r egy paraméter. A három leggyakoribb példa Minkowski távolságra a következő.

d(x,y)= lim r→∞ ( ∑ k=1 n | x k − y k | r ) 1/r . (2.3)

Ne tévesszük össze az r paramétert a dimenziók (attribútumok) számával, n -el. Az euklideszi, Manhattan és szuprémum távolságok n minden 1,2,3,… értékére definiáltak, és minden dimenzióban különböző módszereket határoznak meg az egyes dimenziók különbségének a teljes távolságban való egyesítésére.

A 2.10., illetve 2.11. táblázatok a 2.8. táblázat adatainak felhasználásával adják meg az L 1 és az L ∞ távolság szomszédsági mátrixait. Megjegyezzük, hogy mindezek a távolsági mátrixok szimmetrikusak, azaz az ij -edik elemük megegyezik a ji -edik elemükkel. A 2.9. táblázatban például az első oszlop negyedik sora és az első sor negyedik oszlopa is az 5,1 értéket tartalmazza.

A távolságok, mint például az euklideszi távolság, néhány közismert tulajdonsággal rendelkeznek. Ha az x és y pontok távolsága d(x,y) , akkor a következő tulajdonságok teljesülnek.

1. Pozitivitás

2. Szimmetria

d(x,y)=d(y,x) minden x -re és y -ra.

3. Háromszög egyenlőtlenség

d(x,z)≤d(x,y)+d(y,z) minden x , y és z pontra.

Metrikáknak nevezzük az olyan mértékeket, amelyek mindhárom tulajdonsággal rendelkeznek. Egyesek a távolság kifejezést csak olyan különbözőségi mértékekre használják, amelyek ezekkel a tulajdonságokkal rendelkeznek, de ezt a gyakorlatot gyakran megszegik. Az itt leírt három tulajdonság egyaránt hasznos és matematikailag jól kezelhető. Továbbá, ha fennáll a háromszög egyenlőtlenség, akkor ezen tulajdonság felhasználásával növelhetjük az olyan módszerek hatékonyságát (ideértve például a klaszterezést), amelyek ezen tulajdonság meglététől függenek. (Lásd a 25. feladatot.) Mindazonáltal sok különbözőség nem elégít ki egyet vagy többet a metrikák tulajdonságai közül. Ilyen mértékekre adunk két példát.

2.14. Példa (Nem-metrikus különbözőségek: halmazkülönbségek)

Ez a példa két halmaz különbségének a halmazelméletben definiált fogalmán alapul. Ha adott két halmaz, A és B , A−B azon elemek halmaza, amelyek A-nak elemei, de nem szerepelnek B -ben. Például, ha A={1,2,3,4} és B={2,3,4} , akkor A−B={1} és B−A=∅ , az üres halmaz. Definiálhatjuk az A és B halmazok d távolságát a következőképpen: d(A,B)= méret (A−B) , ahol a  méret  egy olyan függvény, amely egy halmaz elemszámát adja vissza. Ez a távolsági mérték, ami egy 0-nál nagyobb vagy egyenlő egész érték, nem elégíti ki a pozitivitási tulajdonság második részét, a szimmetria tulajdonságot, és a háromszög egyenlőtlenséget. Azonban megoldható, hogy ezek a tulajdonságok fennálljanak, amennyiben a különbözőségi mértéket a következőképpen módosítjuk: d(A,B)= méret (A−B)+ méret (B−A) . Lásd a 19. feladatot exer:set_difference. oldalon.

2.15. Példa (Nem-metrikus különbözőségek: idő)

Ez a példa egy még mindennapibb példát ad olyan különbözőségi mértékre, ami nem metrikus, mégis hasznos. Definiáljuk a nap időpontjainak távolságát a következőképpen:

d( t 1 , t 2 )={ t 2 − t 1 , ha t 1 ≤ t 2 24+( t 2 − t 1 ), ha t 1 ≥ t 2 }. (2.4)

Szemléltetésképpen, d(1PM,2PM) = 1 óra, míg d(2PM,1PM) = 23 óra. Egy ilyen definíció értelmes lehet például, ha a következő kérdést akarjuk megválaszolni: ``Ha egy esemény minden nap délután 1-kor következik be, és most délután 2 van, meddig kell várnom, hogy az esemény ismét bekövetkezzen?''

A hasonlóságokra jellemzően nem áll fenn a háromszög egyenlőtlenség (vagy egy azzal analóg tulajdonság), de a szimmetria és a pozitivitás jellemzően igen. Konkrétan, ha s(x,y) az x és y pontok hasonlósága, akkor a hasonlóságok jellemző tulajdonságai a következők:

1. s(x,y)=1 akkor és csak akkor, ha x = y ( 0≤s≤1).

2. s(x,y)=s(y,x) minden x -re és y -ra (szimmetria).

A hasonlósági mértékekre nincs általános megfelelője a háromszög egyenlőtlenségnek. Azonban esetenként lehetséges annak bizonyítása, hogy egy hasonlósági mérték könnyedén átalakítható egy metrikus távolsággá. A koszinusz és Jaccard hasonlósági mértékek, amelyeket rövidesen tárgyalunk, ennek két példája. Továbbá, meghatározott hasonlósági mértékekre a háromszög egyenlőtlenség szellemében lehetséges, hogy két hasonló objektum hasonlóságára matematikai korlátokat határozzunk meg.

2.16. Példa (Egy nem szimmetrikus hasonlósági mérték)

Tekintsünk egy kísérletet, melyben embereket kérünk meg, hogy néhány karaktert osztályozzanak, ahogy azok felvillannak a képernyőn. Az erre a kísérletre vonatkozó tévesztési mátrix tartalmazza azt, hogy milyen gyakran osztályozzák az egyes karaktereket saját magukként, és milyen gyakran osztályozzák egy másikként. Tegyük fel például, hogy a ``0'' 200 alkalommal tűnt fel, és ``0''-nak sorolták be 160 alkalommal, de 40 alkalommal ``o''-nak. Hasonlóképpen feltételezzük, hogy az ``o'' 200 alkalommal jelent meg, és ``o''-nak sorolták be 170 alkalommal, de ``0''-ként 30 alkalommal. Ha ezeket a darabszámokat a két karakter közötti hasonlóság egy mértékének tekintjük, akkor egy olyan hasonlósági mértéket kapunk, amely nem szimmetrikus. Ilyen esetekben a hasonlósági mértéket gyakran szimmetrikussá teszik az s'(x,y)=s'(y,x)=(s(x,y)+s(y,x))/2 meghatározásával, ahol s' jelöli az új hasonlósági mértéket.

Ebben a részben konkrét példákat mutatunk néhány hasonlósági és különbözőségi mértékre.

Hasonlósági mértékek bináris adatokra

Az olyan objektumok hasonlósági mértékeit, amelyek csak bináris attribútumokkal rendelkeznek, hasonlósági együtthatóknak nevezzük, és jellemzően 0 és 1 között veszik fel értékeiket. Az 1 érték azt jelzi, hogy a két objektum teljesen hasonló, míg a 0 érték azt jelzi, hogy az objektumok egyáltalán nem hasonlítanak. Számos okfejtés ismert arról, hogy bizonyos esetekben az egyik együttható miért jobb egy másiknál.

Legyen x és y két olyan objektum, amelyek n darab bináris attribútumból állnak. Két ilyen objektum, azaz két bináris vektor összehasonlítása a következő négy mennyiséghez (gyakorisághoz) vezet:

f 00 = azon attribútumok száma, ahol x=0 és y=0

f 01 = azon attribútumok száma, ahol x=0 és y=1

f 10 = azon attribútumok száma, ahol x=1 és y=0

f 11 = azon attribútumok száma, ahol x=1 és y=1

Egyszerű egyezés együttható Az egyszerű egyezés együttható (SMC -- Simple Matching Coefficient) egy gyakran használt hasonlósági együttható, melyet a következőképpen definiálunk:

SMC= egyezőattribútumértékekszáma attribútumokszáma = f 11 + f 00 f 01 + f 10 + f 11 + f 00 . (2.5)

Ez a mérték egyformán számolja a jelenlévő és a hiányzó értékeket. Ebből következik, hogy az SMC akkor használható, ha olyan hallgatókat keresünk, akik hasonlóan válaszoltak a kérdésekre egy csak igaz-hamis kérdésekből álló teszten.

Jaccard együttható Tegyük fel, hogy x és y olyan adatobjektumok, amelyeket egy tranzakciós mátrix két sora (két tranzakciója) reprezentál (lásd a 2.1.2. szakaszt). Ha minden aszimmetrikus bináris attribútum egy termékhez tartozik egy áruházban, akkor egy 1-es a tétel megvásárlását jelzi, míg egy 0 azt, hogy a tételt nem vásárolták meg. Mivel azok a termékek, amelyeket az adott vevő nem vett meg, jóval nagyobb számúak, mint azok, amelyeket megvett, egy olyan hasonlósági mérték, mint például az SMC , azt mutatná, hogy minden tranzakció nagyon hasonló. Ezért használják gyakran a Jaccard együtthatót aszimmetrikus bináris attribútumokból álló objektumok kezelésére. A gyakran J -vel jelölt Jaccard együtthatót a következő egyenlet adja:

J= az egyező előfordulások száma a 00 egyezéseken kívüli attribútumok száma = f 11 f 01 + f 10 + f 11 . (1.6)

2.17. Példa (Az SMC és a Jaccard hasonlósági együtthatók)

Hogy szemléltessük a két hasonlósági mérték közötti különbséget, kiszámítjuk az SMC -t és a J -t a következő két bináris vektorra.

x=(1,0,0,0,0,0,0,0,0,0) y=(0,0,0,0,0,0,1,0,0,1) f 01 =2    azon attribútumok száma, ahol x értéke 0, y értéke pedig 1

f 10 =2    azon attribútumok száma, ahol x értéke 1, y értéke pedig 0

f 00 =2    azon attribútumok száma, ahol x értéke 0, y értéke pedig 0

f 11 =2    azon attribútumok száma, ahol x értéke 1, y értéke pedig 1

SMC= f 11 + f 00 f 01 + f 10 + f 11 + f 00 = 0+7 2+1+0+7 =0,7 J= f 11 f 01 + f 10 + f 11 = 0 2+1+0 =0

Koszinusz hasonlóság

A dokumentumokat gyakran vektorokként ábrázoljuk, ahol minden attribútum egy adott kifejezés (szó) előfordulási gyakoriságát fejezi ki a dokumentumban. Természetesen ez ennél bonyolultabb, mivel bizonyos gyakori szavakat figyelmen kívül hagyunk, és különböző előfeldolgozási módszerek felhasználásával kezeljük ugyanazon szó különböző formáit, a dokumentumok különböző hosszúságait és a szavak különböző gyakoriságait.

Bár a dokumentumoknak több ezer vagy több tízezer attribútuma (kifejezése) van, minden dokumentum ritka, mivel viszonylag kevés nem-nulla attribútuma van. (A dokumentumoknál használt normalizáló módszerek nem hoznak létre nem-nulla bejegyzéseket nulla bejegyzések helyén, azaz megőrzik a ritkaságot.) Így, csakúgy mint a tranzakciós adatoknál, a hasonlóság nem függ a 0 értékek számától, mivel nem valószínű, hogy két dokumentum ugyanazokat a szavakat ``nem tartalmazza'', ezért ha megszámolnánk a 0-0 egyezéseket, a legtöbb dokumentum nagy mértékben hasonlítana a többi dokumentumhoz. Ezért egy dokumentumokra alkalmazott hasonlósági mértéknek figyelmen kívül kell hagynia a 0-0 egyezéseket, csakúgy, mint a Jaccard mértéknek, de emellett tudnia kell nem bináris vektorokat kezelni. A következőkben definiált koszinusz hasonlóság a dokumentumok hasonlóságának egyik legelterjedtebb mértéke. Ha x és y két dokumentumvektor, akkor

cos(x,y)= x•y ∥x∥    ∥y∥ , (2.7)

ahol • jelzi a vektorok belső szorzatát, x•y= ∑ k=1 n x k y k , ∥x∥ pedig az x vektor hossza, ‖ x ‖= ∑ k=1 n x k 2 = x⋅x .

2.18. Példa (Két dokumentumvektor koszinusz hasonlósága)

Ebben a példában kiszámoljuk a koszinusz hasonlóságot a következő két adatobjektum között, amelyek dokumentumvektorokat is reprezentálhatnak:

x=(3,2,0,5,0,0,0,2,0,0) y=(1,0,0,0,0,0,0,1,0,2) x•y=3*1+2*0+0*0+5*0+0*0+0*0+0*0+2*1+0*0+0*2=5 ∥x∥= 3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0 =6,48 ∥y∥= 1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2 =2,45 cos(x,y)=0,31

Mint ahogy a 2.16. ábra mutatja, a koszinusz hasonlóság valójában az x és y által bezárt szög koszinuszának a mértéke. Ezért ha a koszinusz hasonlóság 1, akkor az x és y által bezárt szög 0 ∘ -os, és x és y a nagyságukat (hosszukat) leszámítva megegyeznek. Ha a koszinusz hasonlóság 0, akkor az x és y által bezárt szög 90 ∘ -os, és nincsenek közös kifejezéseik (szavaik).

A (2.7) egyenlet felírható (2.8) egyenlet formájában.

cos(x,y)= x ∥x∥ ⋅ y ∥y∥ =x'⋅y', (2.8)

ahol x'=x/∥x∥ és y'=y/∥y∥ . Azzal, hogy x -et és y -t elosztjuk a hosszukkal, normalizáljuk őket, hogy a hosszuk 1 legyen. Ez azt jelenti, hogy a koszinusz hasonlóság nem veszi figyelembe a két adatobjektum nagyságát a hasonlóság kiszámítása során. (Ha a nagyság fontos, akkor az euklideszi távolság jobb választásnak bizonyulhat.) Az 1 hosszúságú vektorokra a koszinusz távolság egy egyszerű belső szorzattal számítható ki. Következésképpen, ha nagyon sok objektum közötti koszinusz távolságot számítunk ki, az objektumok egységnyi hosszra való normalizálása csökkenti a szükséges időt.

Kiterjesztett Jaccard együttható (Tanimoto együttható)

A kiterjesztett Jaccard együttható használható dokumentumadatokhoz, és bináris attribútumok esetén a Jaccard együtthatóvá egyszerűsödik. A kiterjesztett Jaccard együttható Tanimoto együtthatóként is ismert. (Azonban egy másik együttható is ismert Tanimoto együttható néven.) Ezt az együtthatót, amit EJ -vel fogunk jelölni, a következő egyenlet definiálja:

EJ(x,y)= x⋅y ∥x ∥ 2 +∥y ∥ 2 −x⋅y . (2.9)

Korreláció

Két bináris vagy folytonos változókkal rendelkező adatobjektum közötti korreláció az objektumok attribútumai közötti lineáris kapcsolat mértéke. (Az attribútumok közötti korreláció kiszámítását, ami ismertebb, hasonlóképpen definiálhatjuk.) Konkrétabban, a két adatobjektum, x és y , közötti Pearson-féle korrelációs együtthatót a következő egyenlettel definiáljuk:

 korreláció (x,y)= kovariancia(x,y)  szórás (x)* szórás (y) = s xy s x s y , (2.10)

ahol a következő szokásos statisztikai jelöléseket és definíciókat alkalmaztuk:

kovariancia(x,y)= s xy = 1 n−1 ∑ k=1 n ( x k − x ¯ ) ( y k − y ¯ ) (2.11)

szórás(x)= s x = 1 n−1 ∑ k=1 n ( x k − x ¯ ) 2

szórás(y)= s y = 1 n−1 ∑ k=1 n ( y k − y ¯ ) 2

x ¯ = 1 n ∑ k=1 n x k az X átlaga

y ¯ = 1 n ∑ k=1 n y k az y átlaga

2.19. Példa (Tökéletes korreláció)

A korreláció mindig a −1 és 1 közötti tartományban van. Az 1 ( −1 ) értékű korreláció azt jelenti, hogy x és y tökéletes pozitív (negatív) kapcsolatban állnak egymással, azaz x k =a y k +b , ahol a és b konstansok. A következő két, x -re és y -ra vonatkozó értéksorozat olyan eseteket mutat, ahol a korreláció −1 illetve 1. Az egyszerűség kedvéért x és y átlagát mindkét esetben 0-nak választottuk.

x=(−3,6,0,3,−6)

y=(1,−2,0,−1,2)

x=(3,6,0,3,6)

y=(1,2,0,1,2)

2.20. Példa (Nemlineáris kapcsolatok)

Ha a korreláció értéke 0, akkor a két adatobjektum attribútumai között nincs lineáris kapcsolat. Nemlineáris kapcsolat azonban még lehet. A következő példában y k = x k 2 , ennek ellenére korrelációjuk 0.

x=(−3,−2,−1,0,1,2,3) y=(9,4,1,0,1,4,9)

2.21. Példa (A korreláció szemléltetése)

Könnyű megítélni az x és y adatobjektumok közötti korrelációt, ha a megfelelő attribútumértékek párjait ábrázoljuk. A 2.17. ábra néhány ilyen grafikont mutat, ahol x -nek és y -nak 30 attribútuma volt, és ezen attribútumok értékei (normális eloszlás alapján) véletlenszerűen lettek generálva, így az x és y közötti korreláció −1 -től 1-ig terjed. A grafikonokon minden kör a 30 attribútum egyikét jelöli; az x koordináta az x egyik attribútumának értéke, míg az y koordináta ugyanazon attribútum értéke y -nál.

Ha úgy transzformáljuk x -et és y -t, hogy kivonjuk az átlagaikat és normalizáljuk őket, hogy a hosszuk 1 legyen, akkor a korrelációjuk kiszámítható úgy, hogy egyszerűen vesszük a belső szorzatukat. Megjegyezzük, hogy ez nem ugyanaz a standardizálás, mint amit más helyzetekben használunk, amikor az x k' =( x k − x ¯ )/ s x és y k' =( y k − y ¯ )/ s y transzformációkat végezzük el.

Bregman divergencia* Ebben a szakaszban a Bregman divergenciát ismertetjük röviden, amely néhány közös tulajdonsággal rendelkező szomszédsági függvény egy családja. Eredményeképpen olyan általános adatbányászati algoritmusokat, például klaszterező algoritmusokat alkothatunk, amelyek tetszőleges Bregman divergenciával működnek. Erre konkrét példa a K -közép klaszterező algoritmus (lásd 8.2. fejezetet). Megjegyezzük, hogy ehhez a szakaszhoz a vektorkalkulus ismeretére van szükség.

A Bregman divergenciák veszteség- vagy torzításfüggvények. Hogy megértsük a veszteségfüggvény fogalmát, tekintsük a következőket. Legyen x és y két pont, ahol y -t tekintjük az eredeti pontnak, és x annak valamilyen torzulása vagy közelítése. Például, x lehet egy generált pont úgy, hogy véletlen zajt adtunk y -hoz. A cél az, hogy megmérjük a torzítást vagy veszteséget, ami annak az eredménye, hogy y -t közelítettük x -szel. Természetesen x és y minél hasonlóbbak, a veszteség vagy torzítás annál kisebb. Így a Bregman divergenciákat használhatjuk különbözőségi mértékként.

Formálisabban a következő definíciót kapjuk.

2.6. Definíció (Bregman divergencia) Ha adott egy ϕ szigorúan konvex függvény (pár kisebb megszorítással, amelyek általában teljesülnek), akkor az ezen függvény által generált D(x,y) Bregman divergenciát (veszteségfüggvényt) a következő egyenlet adja:

D(x,y)=ϕ(x)−ϕ(y)−〈∇ϕ(y),(x−y)〉, (2.12)

ahol ∇ϕ(y) a ϕ y -ban kiértékelt gradiense, x−y x és y vektorkülönbsége, és 〈∇ϕ(y),(x−y)〉 a ∇ϕ(x) és (x−y) vektorok belső szorzata. Az euklideszi tér pontjaira a belső szorzat egyszerű skalárszorzat.

D(x,y) felírható D(x,y)=ϕ(x)−L(x) alakban, ahol L(x)=ϕ(y)+〈∇ϕ(y),(x−y)〉 egy olyan sík egyenlete, ami y -ban érinti a ϕ függvényt. A kalkulus terminológiájával L(x) ϕ linearizálása az y pont körül, és a Bregman divergencia csupán a különbség egy függvény és annak egy közelítése között. A különböző Bregman divergenciákat úgy kapjuk, hogy különböző függvényeket választunk ϕ -nek.

2.22. Példa. Egy konkrét példát adunk négyzetes euklideszi távolságot használva, de csak egy dimenzióra szorítkozunk, hogy a matematikai hátteret egyszerűsítsük. Legyenek x és y valós számok, ϕ(t) pedig a ϕ(t)= t 2 valós függvény. Ebben az esetben a gradiens a deriválttá redukálódik, a belső szorzat pedig szorzássá. Konkrétan (2.12) egyenletből (2.13) egyenletet kapjuk.

D(x,y)= x 2 − y 2 −2y(x−y)= (x−y) 2 (2.13)

A 2.18. ábra mutatja a példához tartozó grafikont y=1 mellett. A Bregman divergencia x két értékéhez, x=2 -höz és x=3 -hoz, van feltüntetve.

Ebben a szakaszban néhány fontos kérdést tárgyalunk a szomszédsági mértékekkel kapcsolatban: (1) hogyan kezeljük azokat az eseteket, amikor az attribútumok skálája eltérő és/vagy az attribútumok korreláltak, (2) hogyan számoljuk a szomszédságot különböző típusú, például kvantitatív és kvalitatív attribútumokból álló, objektumok között, és (3) hogyan kezeljük a szomszédság kiszámítását, amikor az egyes attribútumoknak különböző súlyaik vannak, azaz amikor nem minden attribútum járul hozzá egyenlően az objektumok szomszédságához.

Standardizálás és korreláció távolsági mértékeknél

A távolsági mértékek egy fontos kérdése, hogy hogyan kezeljük azt a helyzetet, amikor az egyes attribútumok értékeinek különböző a terjedelme. (Ezt a helyzetet gyakran úgy írják le, hogy ``a változók skálája különbözik''.) Korábban az euklideszi távolságot használtuk, hogy emberek közötti távolságot mérjünk két attribútumra, a korra és a jövedelemre alapozva. Ha ezeket az attribútumokat nem standardizáljuk, akkor a két ember közötti távolságban túlsúlyba kerül a jövedelem.

Ehhez kapcsolódó kérdés, hogy hogyan számoljuk a távolságot, ha egyes attribútumok között korreláció figyelhető meg, esetleg az értékek terjedelmeinek különbsége mellett. Az euklideszi távolság egy általánosítása, a Mahalanobis távolság, hasznos abban az esetben, ha az attribútumok korreláltak, különböző az attribútumok értékeinek terjedelme (különböző a szórásuk), és az adatok eloszlása közelítőleg Gauss (normális). Speciálisan, az x és y objektumok (vektorok) közötti Mahalanobis távolságot a következőképpen definiáljuk:

mahalanobis(x,y)=(x−y) Σ −1 (x−y) T , (2.14)

ahol Σ −1 az adatok kovarianciamátrixának az inverze. Megjegyezzük, hogy a Σ kovarianciamátrix az a mátrix, amelynek ij -edik eleme az i -edik és a j -edik attribútumok (2.11) egyenletben definiált kovarianciája.

2.23 Példa. A 2.19. ábrán 1000 pont látható, amelyek x és y attribútumainak korrelációja 0,6. Ha euklideszi távolsággal mérjük, akkor az ellipszis hosszabb tengelyének két szemközti végén elhelyezkedő két nagy pont távolsága 14,7, Mahalanobis távolság esetén azonban csak 6. A gyakorlatban a Mahalanobis távolság kiszámítása költséges, de érdemes lehet alkalmazni korrelált attribútumokkal rendelkező adatok esetén. Ha az attribútumok között viszonylag kismértékű korreláció van, terjedelmük viszont különböző, akkor elegendő a változók standardizálása is.

Heterogén attribútumok hasonlóságainak összekapcsolása

Az előző hasonlósági definíciók olyan megközelítéseken alapultak, amelyek feltételezték, hogy az összes attribútum egyforma típusú. Ha az attribútumok különböző típusúak, akkor egy általános megközelítésre van szükség. Egy egyszerű megközelítés, ha a 2.7. táblázat segítségével minden attribútumra külön-külön kiszámítjuk a hasonlóságot, majd ezeket összekapcsoljuk egy olyan módszerrel, amely egy 0 és 1 közötti hasonlóságot eredményez. A teljes hasonlóságot jellemzően az egyedi attribútumok hasonlóságainak átlagaként definiálják.

Sajnos ez a megközelítés nem működik jól, ha attribútumok közül néhány aszimmetrikus. Ha például minden attribútum aszimmetrikus bináris attribútum, akkor az előbb javasolt hasonlósági mérték az egyszerű egyezés együtthatóvá egyszerűsödik, egy olyan mértékké, amely nem megfelelő aszimmetrikus bináris attribútumok kezelésére. Ezt a problémát úgy orvosolhatjuk a legegyszerűbben, ha az aszimmetrikus attribútumokat kihagyjuk a hasonlóság kiszámításából, amennyiben az értékük 0 mindkét objektum esetén, amelyeknek a hasonlóságát számoljuk. Hasonló megközelítéssel a hiányzó értékek is jól kezelhetőek.

Összegezve, a 2.1. algoritmussal hatékonyan számítható ki az x és y , különböző típusú attribútumokkal rendelkező objektumok teljes hasonlósága. Ez az eljárás könnyen módosítható úgy, hogy különbözőségekkel is működjön.

2.1. algoritmus Heterogén objektumok hasonlóságai

1: A k -adik attribútumra kiszámítjuk az s k (x,y) hasonlóságot a [0;1] tartományban

2: Definiáljuk a δ k indikátorváltozót a k -adik attribútumra a következőképpen:

δ k ={ 0, ha a k-adik attribútum aszimmetrikus és és mindkét objektumnál 0 értéket vesz fel, vagy ha a k-adik attribútumnak az egyik objektumban hiányzik az értéke, 1, egyébként

3: Számítsuk ki a teljes hasonlóságot a két objektum között a következő képlettel:

hasonlóság(x,y)= ∑ k=1 n δ k s k (x,y) ∑ k=1 n δ k (2.11)

Súlyok használata

A korábbiakban többnyire az összes attribútumot egyenlőként kezeltük a szomszédság kiszámítása során. Ez nem előnyös, ha egyes attribútumok fontosabbak a szomszédság definíciójában, mint mások. Ezen helyzetek kezelésére módosíthatjuk a szomszédsági képleteket úgy, hogy minden attribútumot hozzájárulása szerint súlyozunk.

Ha a w k súlyok összege 1, akkor (2.15) egyenlet a következőképpen alakul:

hasonlóság(x,y)= ∑ k=1 n w k δ k s k (x,y) ∑ k=1 n δ k . (2.16)

A Minkowski távolság definíciója is módosítható a következőképpen:

d(x,y)= ( ∑ k=1 n w k | x k − y k | r ) 1/r . (2.17)

A következőkben néhány olyan általános megfigyelést ismertetünk, amelyek segíthetnek. Először, a szomszédsági mérték típusának illeszkednie kell az adatok típusához. Sűrű, folytonos adatok számos típusánál gyakran használnak metrikus távolságmértéket, például euklideszi távolságot. A folytonos attribútumok szomszédságát leggyakrabban különbségek formájában fejezik ki, és a távolságmértékek jól definiált módot adnak ezen különbségek teljes szomszédsági mértékké való összekapcsolására. Bár az attribútumok skálája és fontossága különbözhet, ezeket a kérdéseket gyakran kezelni tudjuk a fentebb leírt módszerekkel.

Ritka adatokra, amelyek gyakran tartalmaznak aszimmetrikus attribútumokat, általában olyan hasonlósági mértékeket alkalmazunk, amelyek figyelmen kívül hagyják a 0-0 egyezéseket. Ez fogalmi szinten azt a tényt tükrözi, hogy két komplex objektum esetén a hasonlóság inkább a közös tulajdonságok számától függ, mint a mindkettőnél hiányzó tulajdonságok számától. Konkrétabban, ritka, aszimmetrikus adatoknál a legtöbb objektumnak csak néhány tulajdonságát írják le az attribútumok, és így ezek az objektumok nagyon hasonlóak azon tulajdonságok szempontjából, amelyekkel nem rendelkeznek. Az ilyen adatokhoz megfelelőek a koszinusz, Jaccard és kiterjesztett Jaccard mértékek.

Vannak olyan további jellemzői is az adatvektoroknak, melyeket figyelembe kell venni. Tegyük fel például, hogy idősorokat akarunk összehasonlítani. Ha az idősorok nagysága fontos (például minden idősor egy szervezet összes eladását mutatja a különböző évekre), akkor használhatjuk az euklideszi távolságot. Ha az idősorok különböző mennyiségeket (például vérnyomást és oxigénfogyasztást) ábrázolnak, akkor általában azt akarjuk meghatározni, hogy nagyságuk helyett az idősorok alakja egyforma-e. Ekkor megfelelőbb a korreláció, ami beépített normalizációt használ és kezeli a nagyság- és szintbeli különbségeket.

Egyes esetekben az adatok transzformálása vagy normalizálása azért fontos, hogy ezáltal egy megfelelő hasonlósági mértéket kapjunk, mivel az ilyen transzformációk nem mindig részei szomszédsági mértékeknek. Idősorokban például lehetnek olyan trendek vagy periodikus mintázatok, amelyek jelentős hatással vannak a hasonlóságra. Emellett a hasonlóság helyes kiszámításához szükséges lehet az időbeli eltérések figyelembevétele. Végül lehet, hogy két idősor csak meghatározott időintervallumokban hasonló. Erős kapcsolat figyelhető meg például a hőmérséklet és a földgázfelhasználás között, de csak a fűtési szezonban.

A gyakorlati megfontolások is fontosak lehetnek. Egyes esetekben egy adott területen már használatban van egy vagy több szomszédsági mérték, és így annak kérdését, hogy melyik szomszédsági mértéket használjuk, már korábban megválaszolták. Máskor előfordulhat, hogy a használt szoftvercsomag vagy klaszterező algoritmus drasztikusan lecsökkenti a lehetőségeinket. Ha a hatékonyság szempont, akkor olyan szomszédsági mértéket érdemes választanunk, aminek van olyan tulajdonsága, mint például a háromszög egyenlőtlenség, ami lecsökkenti a szomszédsági számítások számát. (Lásd 25. feladatot.)

Ha azonban a bevett gyakorlat vagy a gyakorlati szempontok nem írnak elő egy alternatívát, akkor a megfelelő szomszédsági mérték kiválasztása időigényes feladat lehet, amihez a szakterületi ismereteket és a mérték használatának céljait egyaránt alaposan át kell tekinteni. Szükséges lehet több különböző mérték kiértékelése, hogy lássuk, melyik adja azt az eredményt, aminek a legtöbb értelme van.