METRIKUS ÉS ANTIMETRIKUS TEREK, ÉS REDUKCIÓJUK. Nagy István Budapesti Műszaki Főiskola, Neumann János Informatikai Kar

Informatika a felsőoktatásban 2008

Debrecen, 2008. augusztus 27-29.

METRIKUS ÉS ANTIMETRIKUS TEREK, ÉS REDUKCIÓJUK METRIC AND ANTIMETRIC SPACES AND THEIR REDUCTION

Nagy István Budapesti Műszaki Főiskola, Neumann János Informatikai Kar

Összefoglaló E tanulmány a metrikus, illetve transzformációkkal metrikussá alakítható (úgynevezett antimetrikus) terekben értelmezhető távolság-alapú hasonlóságokkal, csoportképzésekkel és térredukciókkal foglalkozik. Alapvetően azt fogjuk vizsgálni, hogy milyen következményekkel jár egy "tolerancia-szerű" tulajdonság bevezetése a metrikus térben, pontosabban, hogy milyen hatással van a metrikus térre, ha azokat a pontokat, melyek egy előre megadott értéket meghaladóan közel vannak egymáshoz, helyettesíthetőnek tekintjük egymással. Ezzel tulajdonképpen egy hasonlóságot értelmezünk a pontok között, azaz lényegében a hasonlóság és a metrika kapcsolatát vizsgáljuk. A szakirodalomban mind a távolságalapú hasonlóság fogalom, mind a metrikus terek redukciójának érdekében végzett csoportképzés (klaszterezés) elterjedten használatos. Jelen tanulmányban talán önkényesnek tűnik a metrikus térben egy határtávolság fogalom bevezetése, ám a segítségével képzett hasonlóság-, majd annak alapján definiált ekvivalencia-reláció új lehetőségeket biztosít a diszjunkt alterek létrehozásában és az ezekben való pontredukció területén.

Kulcsszavak metrikus tér, határtávolság, antimetrikus tér, határközelség, hasonlóság, környezeti és relatív helyettesíthetőség, redukció, galaxisok, mikrogalaxisok, klaszterezés.

Abstract This study is concerned with the distance based similarity, group composition and space reduction that exist in metric spaces and spaces that can be formed into metric spaces by transformations (antimetric spaces). The consequences of the introduction of a tolerance-like property to the metric space are investigated. To be more specific, we examine the effect of the substitution of points that are closer to each other by a predefined limit. By allowing such a substitution of the points with each other, a certain similarity is defined, thus we are analyzing the connection between similarity and metrics. Both the distance-based similarity and the reduction of metric spaces by the composition of groups (clusters) are widespread in the literature. The introduction of a limit distance to the metric spaces in the current study might seem peremptory, but the similarity and equivalence relations that are defined with the help of this distance make new opportunities for the creation of disjoint subspaces and on the field of point reduction.

Keywords Metric space, limit distance, antimetric space, limit proximity, similarity, ambient and relative interchangeability, reduction, galaxies, microgalaxies, clustering



Bevezetés Bár maga a hasonlóság nyilvánvalóan nem alkot metrikát (hiszen például minél nagyobb két objektum hasonlósági értéke, annál közelebb vannak egymáshoz a hasonlósági térben, tehát nem teljesülhet a távolságokra vonatkozó háromszög egyenlőtlenség), azonban látni fogjuk, hogy a hasonlósági teret a metrikus tér fogalmával azért mégiscsak definiálhatjuk. Az alábbiakban vizsgált tulajdonságok közül számunkra a legérdekesebb a "helyettesíthetőség" lesz, vagyis hogy egy kapcsolatrendszerbeli objektum milyen feltételekkel helyettesíthető egy másikkal oly módon, hogy a kapcsolatrendszerben elfoglalt helye egy megadott "tűréshatáron" belül maradjon. Tekintsük például a kirándulóbusz-feladatot, mely szerint a cél meghatározni egy kisvárosban azokat a helyeket, ahol célszerű megállnia a kirándulókat összeszedő busznak azzal a feltétellel, hogy az embereknek az egyes gyűjtőhelyekre ne kelljen 10 percnél többet sétálniuk. Nyilván megállhat minden egyes kiránduló házánál (így eljutunk az iskolabusz-feladathoz, ahol az energia-idő takarékosság jegyében már az a fő kérdés, hogy milyen sorrendben szedje össze a diákokat), de a 10 perc ~ 1 km feltételezéssel a kirándulók lakcímeinek és a város térképének ismeretében kialakíthatunk célszerű gyűjtőpontokat. Ekkor azt mondhatjuk, hogy az egyes kirándulók otthonainak halmazát (nevezzük ezt vizsgált halmaznak) helyettesíthetjük a kisebb elemszámú gyűjtőhalmazzal. Ebben az esetben még az is érdekes, hogy a gyűjtőhalmazban jórészt olyan elemek lesznek, melyek a vizsgált halmaznak nem is elemei. Persze a feladat megfogalmazható oly módon is, hogy a gyűjtőhalmaz mindenképpen részhalmaza legyen a vizsgált halmaznak. A fenti feladat analitikus megfogalmazása szerint csupán arra vagyunk kíváncsiak, hogy egy megadott gyűjtőponttal helyettesíthető-e adott kiránduló otthona, feltételezve az 1 km-nél nem nagyobb odasétálási határfeltételt. Az ilyen típusú feladatokat halmazredukciós feladatoknak nevezzük, és e cikk egyik fő célja e feladatok kitűzése és célszerű megoldása. A továbbiakban esetenként algoritmusokat fogunk megadni bizonyos objektumok konstruktív meghatározására. Ehhez szükségünk lesz a valamely halmazból való elemkiválasztás sorrendjének megkötésére. E célból vezetjük be a „ 〈− ” jellel jelölt szekvenciális elemkiválasztás műveletét, melynek segítségével egy indexhalmaz rendezettsége szerint növekvő sorrendben választjuk ki ennek elemeit. (Például j 〈− [1, n], vagy j 〈− In módon jelölve a számok növekvő módon való kiválasztását az 1, 2,... n számokat tartalmazó rendezett halmazból.) Az alábbiakban az egyértelmű használat érdekében néhány alapfogalmat definiálunk. Definíció. (Ekvivalencia és hasonlósági reláció) A reflexív, szimmetrikus, és tranzitív relációkat ekvivalencia relációnak, a reflexív, szimmetrikus, de nem feltétlenül tranzitív relációkat pedig hasonlósági relációnak nevezzük. (Az ekvivalencia reláció tehát egyben hasonlósági reláció is.)



Definíció. (Partícionálás) Ha egy A halmazon értelmezett egy E ekvivalencia reláció, akkor az A|E módon jelölt halmazt az A halmaz E ekvivalencia reláció szerinti partícionáltjának nevezzük, és ez olyan, közös elemeket nem tartalmazó, azaz diszjunkt halmazokból áll, melyek mindegyike az A halmaznak az E ekvivalencia reláció szerint ekvivalens elemeit tartalmazza (tehát minden halmaz egy-egy ekvivalencia osztály), és e halmazok egyesítése maga az A halmaz.

1. Metrikus terek

1.1. Alapfogalmak 1.1.1. Definíció. (Metrikus tér, távolságfüggvény, alaphalmaz, határtávolság) Tekintsünk egy A halmazt, és a rajta értelmezett λΑ : A×A→R, úgynevezett távolságfüggvényt, ahol R a valós számok halmaza. Ekkor az MΑ = 〈A,λΑ〉 struktúrát metrikus térnek nevezzük, ha .1. minden a,b∈A esetén λΑ(a,b) ≥ 0, .2. minden a,b∈A esetén λΑ(a,b) = 0 akkor és csak akkor, ha a = b, .3. minden a,b,c∈A esetén λΑ(a,c) ≤ λΑ(a,b) + λΑ(b,c), ezt nevezzük háromszög egyenlőtlenségnek, .4. minden a,b∈A esetén λΑ(a,b) = λΑ(b,a), ezt nevezzük szimmetria tulajdonságnak. Az A halmazt az MΑ metrikus tér alaphalmazának nevezzük, és Set(MΑ) módon is jelöljük. .5. A továbbiakban a metrikus térhez hozzárendelünk egy úgynevezett ΛA határtávolságot (ΛA∈R, ΛA ≥ 0). Az ezzel kiegészített metrikus teret MΑ = 〈A,λΑ,ΛA〉 módon jelöljük, és egyszerű korlátos metrikus térnek, de legtöbbször röviden ezt is csak metrikus térnek nevezzük. 1. Megjegyzés. (Elemek, pontok) A továbbiakban a szemléletesség érdekében egy metrikus tér elemei esetén az elem szó helyett gyakran fogjuk a pont szót használni. 2. Megjegyzés. (A szimmetriamentes metrikus tér) Lehetséges volna-e a szimmetria tulajdonságot csupán a metrikus tér fogalmát általánosító tulajdonságként tekinteni? Bár nagyon kézenfekvő a távolság fogalmáról feltételezni a szimmetriát (lehet-e a bálna a fejétől a farkáig hosszabb, mint a farkától a fejéig?), mégis meglepően sok példa hozható fel arra, hogy ez nem teljesül. Már a hétköznapi távolság meghatározás esetén is, gondoljunk csak az egyirányú utcákat kerülgető városi közlekedésre, vagy az egyenletes mozgás miatt gyakran távolság jelleggel használt "eltelt idő"-re (például könnyen lehet háromnegyed óra az út "oda" és félóra "vissza", ha a cél a hegy tetején lévő kilátó).



Már a háromszög egyenlőtlenség is szinte sugallja az aszimmetriát, hiszen a távolságfüggvénybeli paraméterek sorrendje szerint, vagyis az 〈a,b〉, 〈b,c〉 és 〈a,c〉 vektorok alapján célszerű egy a→c irányú elmozdulásra gondolni. Ugyan mi indokolná, hogy az ellenkező irányú elmozdulás körülményei azonosak legyenek? Annak oka, hogy a továbbiakban mégis szimmetrikusnak tételezzük fel a metrikus teret roppant egyszerűen az, hogy azok a tulajdonságok, melyekkel foglalkozni kívánunk csak a szimmetrikus metrikus terekben definiálhatók egyszerűen. Elképzelhető azonban egy olyan (kissé bonyolultabb) tárgyalás, mely a szimmetriát nem kívánja meg. 3. Megjegyzés. (A határtávolság jelentősége) A határtávolság az a fogalom, mely a bevezetőben említett "tolerancia-szerű" tulajdonságot megvalósítja. Jelentőségét az adja, hogy segítségével tudjuk majd a metrikus tér pontjait diszjunkt osztályokba (lásd galaxis), illetve részben átfedő finomabb struktúrákba (lásd mikrogalaxis) sorolni (klaszterezni), sőt még egyfajta hasonlóságot is tudunk segítségével értelmezni (szomszédsági reláció). A továbbiakban kizárólag olyan metrikus terekkel foglalkozunk, melyekben értelmezzük a határtávolságot. 4. Megjegyzés. (A határtávolság mértéke) Feltehető a kérdés, hogy vajon egy konkrét metrikus térben mekkora is legyen a határtávolság. E kérdésre azonban nem tudunk egyértelmű választ adni. Az esetek egy részében a feladat jellegéből adódik egy hozzávetőleges érték (lásd a kirándulóbusz-feladatot), más esetekben próbálkozásokkal célszerű a megfelelő értéket megkeresni (például a térben már létező legkisebb távolságértéktől elindulva). Tulajdonképpen még az is elképzelhető, hogy egy metrikus térben akár több határtávolságot is fölvegyünk (persze akkor a modell már lényegesen bonyolultabb lesz), hiszen – visszatérve a kirándulóbusz-feladatra – egy hegyvidékes környéken a 10 perces séta általában kisebb távolságot jelentene, mint egy sík vidéken. 1.1.2. Definíció. (Metrikus tér altere, távolságfüggvény megszorítása, valódi altér) Egy MB = 〈B,λB,ΛB〉 struktúrát az MA = 〈A,λA,ΛA〉 metrikus tér alterének nevezünk, és ezt MB ⊆ MA módon jelöljük, ha .1. B ⊆ A, .2. ΛB = ΛA, és .3. minden a,b∈B esetén λB(a,b) = λA(a,b). Ekkor bevezetjük a λB = [λA]B jelölést, és ez utóbbit a λA távolságfüggvény B halmazra vett megszorításának nevezzük. MA-nak az MB valódi altere, és ezt MB ⊂ MA módon jelöljük, ha MB ⊆ MA, de B ≠ A. 1.1.3. Állítás. A metrikus tér alterei is metrikusak, és ha MB ⊂ MA, akkor µ(B) < µ(A), ahol a µ függvény a paramétereként megadott halmaz elemeinek számát (számosságát) adja meg. Bizonyítás. Ha MB altere az MA metrikus térnek, akkor a definíció szerint az MA pontjait tartalmazza, és ezen pontok között ugyanazok a távolságok MB -ben mint MA -ban, tehát a metrikus tér tulajdonságai teljesülnek MB -re is. Az állítás második fele nyilvánvaló.



1.2. Metrikus tér környezeti redukciója Az alábbiakban a metrikus tér olyan redukcióit vizsgáljuk, ahol a redukció feltétele kizárólag a pontok egymástól való távolsága. 1.2.1. Definíció. (Szomszédsági reláció, ∼ gráf, ∼ halmaz, ∼ fok, ∼ mérték) .1. Az MΑ = 〈A,λΑ,ΛA〉 metrikus tér szomszédsági relációja, vagy szomszédsági gráfja: PA = {〈a,b〉 | a,b∈A, λΑ(a,b) ≤ ΛA} Az 〈a,b〉∈PA esetére bevezetjük az a ≈PA b, az 〈a,b〉∉PA esetre pedig az a ≈P/A b jelölést. .2. Valamely a∈A pont szomszédsági halmaza, vagy röviden szomszédsága: PA(a) = {b | b∈A, a ≈PA b}, az a pont valódi szomszédsága:

PA* (a) = PA(a) \ {a}, és az a pont szomszédsági foka: σA(a) = µ(PA(a)). .3. Valamely a∈A pont szomszédsági mértéke: ρA(a) = ∑ λA(a, b) . b∈PA ( a )

1.2.2. Állítás. (A szomszédsági reláció tulajdonságai) Egy metrikus tér szomszédsági relációja egy hasonlósági reláció a metrikus tér alaphalmaza fölött.

Bizonyítás. Mivel a szomszédsági reláció definíciója két pont közötti távolság fogalmán alapul, így a reflexivitás (∀a∈A: a ≈PA b), és a szimmetria (∀a,b∈A: a ≈PA b ⇒ b ≈PA a) nyilvánvalóan teljesül. A tranzitivitás korlátlanságát az akadályozza meg, hogy két pont között a szomszédsági reláció csak határtávolságnál kisebb távolság esetén áll fenn (így lehet olyan a,b,c∈A, melyekre bár a ≈PA b, és b ≈PA c, mégis a ≈P/A c). 1.2.3. Állítás. (A szomszédságok és az alaphalmaz kapcsolata) Egy metrikus tér pontjaihoz tartozó szomszédságok egyesítése megadja a metrikus tér alaphalmazát, azaz egy MA metrikus tér esetén

U PA ( x) = A .

x∈A

Bizonyítás. Közvetlenül következik a szomszédság és a halmazegyesítés műveletének fogalmából. 1.2.4. Definíció. (Környezeti reláció, galaktikus rendszer, galaxisok) .1. Az MA = 〈A,λA,ΛΑ〉 metrikus tér környezeti relációja: EA = {〈a,b〉 | a,b∈A, ∃x1,..,xn∈A: (x1 = a, xn = b, ∀i∈[1,n-1]: xi ≈PA xi+1)} Az 〈a,b〉∈EA esetére bevezetjük az a E≡A b jelölést.



.2. Bevezetjük még az MA metrikus tér galaktikus rendszerének fogalmát: MA = {Mk | Mk = 〈Ak,λk,ΛA〉, Ak ⊆ A, ∀a,b∈Ak: a E≡A b, λk = [λΑ]Ak},

ahol az MA elemeit a továbbiakban az MA metrikus tér galaxisainak fogjuk nevezni. 1.2.5. Állítás. (A környezeti reláció tulajdonságai) Egy metrikus tér környezeti relációja egy ekvivalencia reláció a metrikus tér alaphalmaza fölött.

Bizonyítás. Mivel a környezeti reláció definíciója a szomszédság fogalmán alapul, ami egy halmazhoz való tartozást jelent, így a reflexivitás, és a szimmetria nyilvánvalóan teljesül. A tranzitivitás pedig abból következik, hogy a környezeti reláció a pontok közötti szomszédságot láncszerűen kiterjeszti. 1.2.6. Állítás. (A galaxisok tulajdonságai) Legyen MA egy galaktikus rendszer az MA = 〈A,λΑ,ΛA〉 metrikus tér fölött. Ekkor teljesülnek az alábbiak: .1. A galaxisok maguk is metrikus terek, és alterei az eredeti metrikus térnek, azaz minden Mk∈MA esetén Mk ⊆ MA. .2. A galaxisok alaphalmazai az eredeti metrikus tér alaphalmazának a környezeti reláció szerinti partíciói, más szóval minden galaxis egy-egy ekvivalencia osztályt alkot a környezeti reláció szerint, azaz {Ak | Ak = Set(Mk), Mk = 〈Ak,λk,ΛA〉, λk = [λΑ]Ak, Mk∈MA} = A|EA,

azaz .2.1. minden a,b∈Ak esetén (ahol Ak = Set(Mk), Mk∈MA) a E≡A b, .2.2. minden Aj, Ak esetén (ahol Aj = Set(Mj), Ak = Set(Mk), Mj,Mk∈MA) Aj ∩ Ak = ∅, .2.3.

U

Ak Ak = Set ( Mk ) Mk∈MA

= A.

.3. A metrikus tér szomszédsági gráfjában minden galaxist egy-egy összefüggő, a többiekkel közös pontot nem tartalmazó, azaz diszjunkt részgráf reprezentál.

Bizonyítás. .1. A galaxisok nyilvánvalóan alterei az eredeti metrikus térnek, így a korábbiak szerint metrikusak is. .2. Ez közvetlenül következik abból, hogy a környezeti reláció egy ekvivalencia reláció. .3. Minden galaxis gráfja összefüggő, hiszen egy galaxison belül a környezeti reláció a szomszédsági relációban lévő pontok sorozatán keresztül biztosítja a tranzitivitást. A különböző galaxisok gráfjai pedig diszjunktak, hiszen, ha valamely kettő között vezetne akár egy él is, akkor az azáltal reprezentált szomszédsági reláció révén a környezeti reláció már összekötné a két galaxist, amelyik ilyen módon már egy volna. Megjegyzés. Az MA galaktikus rendszer tehát az MA metrikus tér egy partícionálása (klaszterezése), melyet az MA téren értelmezett ΛA határtávolság tett lehetővé a felhasználásával definiált szomszédsági (hasonlósági) és környezeti (ekvivalencia) relációk révén.



1.2.7. Definíció. (Metrikus tér környezeti redukáltja, redukciós tábla, redukciós ráták) Az MB = 〈B,λB,ΛB〉 metrikus teret az MA = 〈A,λA,ΛA〉 metrikus tér ΛA határtávolságra vonatkozó környezeti redukáltjának, vagy röviden redukáltjának nevezzük, és ezt MB = RedE(MA) módon jelöljük, ha .1. az MB altere az MA-nak, azaz MB ⊆ MA, .2. minden a∈ A \ B esetén van olyan b∈B, melyre a∈PA(b), továbbá a RedE transzformációt környezeti redukciós eljárásnak nevezzük.

Bevezetjük a redukciós táblát, mely általános áttekintést ad a redukciós eljárás eredményéről: QBA = {〈b, σA(b), ρA(b)〉 | b∈B}, ahol σA(b): a b∈B pont szomszédsági foka az MA térben, azaz σA(b) = µ(PA(b)), és ρA(b): a b∈B pont szomszédsági mértéke az MA térben, azaz ρA(b) = ∑ λA(b, x ) . x∈PA ( b )

Végül bevezetjük a pontredukciós, az élredukciós és az illeszkedési rátát, melyeket a RedE környezeti redukciós eljárás minősítő paramétereinek is nevezünk. A pontredukciós ráta: µ ( B) . ΦBA = µ ( A) Az élredukciós ráta: µ ( PB ) , ΨBA = µ ( PA) ahol PA, illetve PB az MA, illetve MB terek szomszédsági gráfjai. Az illeszkedési ráta: ρA(b) ∑ b∈B ΧBA = . ∑ ρA(a ) a∈A

1.2.8. Tétel. (A teljességi tétel) Az MB = 〈B,λB,ΛB〉 metrikus tér akkor és csak akkor környezeti redukáltja az MA = 〈A,λA,ΛA〉 metrikus térnek, azaz MB = RedE(MA), ha .1. az MB altere az MA-nak, azaz MB ⊆ MA, .2. az MB pontjaihoz tartozó szomszédságok egyesítése megadja az MA alaphalmazát, azaz

U PA(b) = A .

b∈B

Bizonyítás. Közvetlenül következik a környezeti redukált és a szomszédság fogalmából. Megjegyzés. Egy metrikus tér valamely határtávolságra vonatkozó környezeti redukciójának jogosultságát az a feltételezés biztosítja, hogy a redukált tér egy pontja megfelelően reprezentálja a hozzá



elég közeli pontokat (melyek az eredeti térben a határtávolságon belül vannak), vagyis e közelség egyfajta hasonlóságot, azaz helyettesíthetőséget fejez ki. A teljességi tétel alapján tehát e hasonlóságra vonatkozóan egy környezeti redukált metrikus tér egyenértékű az eredeti metrikus térrel. 1.2.9. Definíció. (Környezeti határredukált, minimális környezeti redukált) Egy MB = 〈B,λB,Λ〉 metrikus teret az MA = 〈A,λA,Λ〉 metrikus tér Λ határtávolságra vonatkozó környezeti határredukáltjának, vagy egyszerűen csak határredukáltjának nevezünk, ha .1.1. MB = RedE(MA), .1.2. nincs olyan MC∈MA, melyre MC = RedE(MA), és MC ⊂ MB egyaránt teljesülne. Az MB az MA metrikus térnek az Λ határtávolságra vonatkozó minimális környezeti redukáltja, vagy röviden csak minimális redukáltja, ha .2.1. MB az MA határredukáltja, és .2.2. az MA összes határredukáltja közül az MB tartalmazza a legkevesebb pontot.

Megjegyzés. Természetesen egy metrikus térnek több határredukáltja, sőt akár több minimális redukáltja is lehet. A későbbiekben bemutatunk egy kvázioptimális eljárást a metrikus terek redukciójára. 1.2.10. Definíció. (Mikrogalaktikus rendszer, mikrogalaxisok, gyűjtőpontok, helyettesített pontok) Legyen egy MA = 〈A,λA,ΛA〉 metrikus tér határredukáltja MB = 〈B,λB,ΛA〉. .1. Ekkor az MA tér MB szerinti mikrogalaktikus rendszere MBA = {mb | b∈B, mb = PA(b)}, ahol az MBA elemeit mikrogalaxisoknak nevezzük (az indexezést esetenként elhagyjuk), és .2. egy b∈B pontot az mb = PA(b) mikrogalaxis gyűjtőpontjának, a B halmazt a gyűjtőhalmazának, a PA* (b) = PA(b) \ {b} halmazt pedig a helyettesített pontok halmazának nevezzük.

Megjegyzés. 1. Egy mikrogalaxis tehát nem más, mint egy határredukált tér valamely pontjának szomszédsága az eredeti metrikus térben, a mikrogalaxis jelentőségét pedig az adja, hogy a pontjait a szomszédsági reláció által definiált hasonlóság értelmében helyettesíteni tudjuk a gyűjtőpontjával. (A gyűjtőpontokat ezért helyettesítő pontoknak is nevezhetjük.) 2. Egy metrikus térnek több határredukáltja, így több mikrogalaktikus rendszere is lehet. 1.2.11. Állítás. (Mikrogalaxisok tulajdonságai) Legyen M az MA metrikus tér egy mikrogalaktikus rendszere. Ekkor fennállnak az alábbiak: .1. a mikrogalaxisok maguk is metrikus terek, és alterei az eredeti metrikus térnek, azaz minden m∈M esetén m ⊆ MA, .2. a mikrogalaxisok alaphalmazainak egyesítése az eredeti metrikus tér alaphalmaza, azaz

U Set (m) = Set (MA) ,

m∈M

.3. minden mikrogalaxishoz egyértelműen megadható az a galaxis, melynek altere, azaz minden m∈M mikrogalaxis esetén van olyan Mk∈MA galaxis, melyre m ⊆ Mk,



.4. az egy galaxison belüli mikrogalaxisok egymásba átjárhatók, azaz minden Mk∈MA galaxis, és mp,mr∈M mikrogalaxis esetén, ha mp,mr ⊆ Mk, akkor léteznek olyan x1,..,xn∈Set(Mk) pontok, melyekre PA(x1) = mp, PA(xn) = mr, továbbá minden i∈[1, n-1] esetén van olyan z∈PA(xi), melyre z∈PA(xi+1) is teljesül.

Bizonyítás. .1. A mikrogalaxisok nyilván alterei az eredeti metrikus térnek, tehát metrikusak is. .2. Ez az állítás következik a teljességi tételből. .3. Mivel a galaxist előállító környezeti reláció egy ekvivalencia reláció, így annak tranzitivitása miatt egy galaxis alaphalmaza zárt a szomszédságra vonatkozóan (vagyis minden benne szereplő pont szomszédságának minden pontja egyben a galaxis pontja is). .4. Ez következik az előzőekben hivatkozott tranzitivitásból, az ott leírt logika szerint. 1.2.12. Definíció. (A "legtöbb szomszéd" környezeti redukciós eljárás) Legyen adott az MA = 〈A,λA,ΛA〉 metrikus tér, és egy MB = 〈B,λB,ΛB〉 metrikus térben legyen λB = [λA]B, ΛB = ΛA, a B alaphalmazt pedig állítsa elő az alábbi eljárás:

B=

U D(Zi ) , i∈[1, n −1]

ahol Zi az i-edik redukáló munkahalmaz, és minden i > 0 esetén Zi = Zi-1 \ D(Zi-1) \

U T ( Zk ) ,

k∈[0, i −1]

melyben • Z0 = A, D(Z0) = ∅, T(Z0) = ∅, • az n értékét az határozza meg, hogy Zn-1 ≠ ∅, és Zn = ∅, • D(Zi) a Zi redukált gyűjtőpontjainak halmaza (a helyettesítő pontok halmaza), és D(Zi) = {xj | xj∈C(Zi), F(xj,Zi) ≠ ∅}, ahol C(Zi) a Zi gyűjtőpontjainak halmaza (az MA metrikus térben legnagyobb szomszédsági fokú, azaz maximális szomszédszámú pontok halmaza), és

C(Zi) = {xj | xj∈Zi, σA(xj) = Max({σA(y) | y∈Zi})}, amelyben ♦ σA(xj) = µ(PA(xj)), és ♦ PA(xj) az xj pont szomszédsága az MA térben, F(xj,Zi) az xj pont szomszédfelosztó halmaza, és ennek rekurzív megadása: minden xj∈C(Zi) és j 〈− [1, µ(C(Zi))] esetén F(xj,Zi) = PA(xj) \

•

U D(Zk ) \ U T (Zk ) \ [U F]( xm, Zi ) ,

k∈[0, i −1]

k∈[0, i −1]

m∈ 0 , j −1

amelyben ♦ a ” 〈− ” jelöli a szekvenciális elemkiválasztás műveletét, és ♦ D(Z0) = ∅, T(Z0) = ∅, F(x0,Zi) = ∅, ahol x0 egy fiktív szimbólum, T(Zk) a Zk helyettesített pontjainak halmaza, és T(Zk) =

UW ( x , Z ) , j

xj∈D ( Zk )

k



ahol W(xj,Zk) az xj pont (xj∈D(Zk)) saját szomszédainak halmaza, és W(xj,Zk) = F(xj,Zk) \ D(Zk). 1.2.13. Állítás. (A "legtöbb szomszéd" redukció tulajdonságai) .1. A "legtöbb szomszéd" környezeti redukciós eljárásban szereplő rekurziók véges számú lépésben befejeződnek. .2. E redukcióban a kiindulási MA = 〈A,λA,ΛA〉 metrikus térnek a származtatott MB = 〈B,λB,ΛB〉 tér a határredukáltja, ahol B a származtatott alaphalmaz, λB = [λA]B, és ΛB = ΛA.

Bizonyítás. .1. A "legtöbb szomszéd" redukció lényege, hogy az aktuális redukáló munkahalmazból kiemeljük a mindenkori legnagyobb szomszédsági fokú pontokat (mint gyűjtőpontokat), valamint a szomszédságukban lévő egyéb pontokat. Így biztos, hogy az i+1-edik redukáló munkahalmaz kisebb, mint az i-edik. .2. Az eljárás során az aktuális redukáló munkahalmazból csak a gyűjtőpontokat és a szomszédsági pontokat emeljük ki, tehát a gyűjtőpontokból létrehozott származtatott alaphalmazból előállítható az eredeti metrikus tér alaphalmaza. A teljességi tétel alapján tehát a származtatott alaphalmazú tér az eredetinek redukáltja, mivel pedig további redukció nem lehetséges (kiürült a redukáló munkahalmaz), így határredukáltja is. Megjegyzés. A "legtöbb szomszéd" redukció tehát a metrikus terek környezeti redukciójának egy kvázioptimális eljárása. Ez alatt azt értjük, hogy az eljárás alapgondolatát jelentő, legnagyobb szomszédsági fokú (azaz legtöbb szomszédot tartalmazó) gyűjtőpontokra alapozott redukció nyilvánvalóan nem mindig ad minimális redukált teret, ám azért feltehetően elég jó (elég kicsi) redukciós rátákat biztosít. (Ez persze egy intuitív eljárás jóságának intuitív indoklása...) 1.2.14. Példa. (A "legtöbb szomszéd" redukció) Egy gyakorlati példán keresztül bemutatjuk a "legtöbb szomszéd" redukciós eljárást. Tekintsük a bevezetőben említett kirándulóbusz-feladatot, melyben a távolságokat például háztömbökben értjük, és a gyűjtőpontokkal szemben az a követelmény, hogy senkinek se kelljen 3 háztömbnyi távolságnál többet gyalogolnia, továbbá a találkozó mindenképpen valamelyik kiránduló házánál legyen. Legyen 15 kiránduló, és lakóhelyüket az alábbi ábra vázolja. (Itt csak azon pontok közötti távolságokat jelöli összekötő egyenes, és rajtuk lévő távolságérték, amelyek 3-nál nem nagyobbak.) i• a •

2

3

• d

b • 2 3

3 2

• e

c • 2 3

2

m•

2

• f

3

• g

2

h•

•j 3 3

•k

u • 2

3

• v

w • 2

Megoldás. Legyen MA = 〈A,λA,ΛA〉 egy metrikus tér, ahol A = {a, b, c, d, e, f, g, h, i, j, k, m, u, v, w}, és ΛA = = 3. A fenti ábra tulajdonképpen az MA szomszédsági gráfját mutatja be (tehát csak azon pontok közötti távolságokat jelöli összekötő egyenes, melyek szomszédsági relációban állnak egymással).



1. iterációs szint

1.1. lépés. (A redukáló munkahalmaz meghatározása) Z1 = A = {a, b, c, d, e, f, g, h, i, j, k, m, u, v, w} Mivel Z1 ≠ ∅, így folytatjuk az 1. iterációs szint lépéssorozatát. 1.2. lépés. (Táblázatos összefoglaló: a redukáló munkahalmaz elemeinek szomszédságai, szomszédsági fokai és szomszédsági mértékei MA-ban) x∈Z1 a b c d e f g h i j k m u v w

PA(x) {a, b, d} {a, b, c, d, e} {b, c, e, f} {a, b, d, e} {b, c, d, e, f} {c, e, f, g} {f, g} {h, m} {i, m} {j, m} {k, m} {h, i, j, k, m} {u, v, w} {u, v, w} {u, v, w}

σA(x) 3 >> 5 << 4 4 >> 5 << 4 2 2 2 2 2 >> 5 << 3 3 3

ρA(x) 5 10 7 7 10 8 3 2 2 3 3 10 5 4 5

1.3. lépés. (A gyűjtőpontok halmazának kijelölése) C(Z1) = {b, e, m} 1.4. lépés. (A szomszédfelosztó halmazok meghatározása) F(b,Z1) = PA(b) \ D(Z0) \ T(Z0) \ F(x0,Z1) = = {a, b, c, d, e} \ ∅ \ ∅ \ ∅ = {a, b, c, d, e} F(e,Z1) = PA(e) \ D(Z0) \ T(Z0) \ (F(x0,Z1) ∪ F(b,Z1)) = = {b, c, d, e, f} \ ∅ \ ∅ \ {a, b, c, d, e} = { f } F(m,Z1) = PA(m) \ D(Z0) \ T(Z0) \ (F(x0,Z1) ∪ F(b,Z1) ∪ F(e,Z1)) = = {h, i, j, k, m} 1.5. lépés. (A redukált gyűjtőpontok halmazának meghatározása) D(Z1) = {x | x∈C(Z1), F(x,Z1) ≠ ∅} = {b, e, m} 1.6. lépés. (A redukált gyűjtőpontok saját szomszédai halmazának meghatározása) W(b,Z1) = F(b,Z1) \ D(Z1) = {a, b, c, d, e} \ {b, e, m} = {a, c, d} W(e,Z1) = F(e,Z1) \ D(Z1) = { f } \ {b, e, m} = { f } W(m,Z1) = F(m,Z1) \ D(Z1) = {h, i, j, k, m} \ {b, e, m} = {h, i, j, k} 1.7. lépés. (A helyettesített pontok halmazának meghatározása) T(Z1) =

UW ( x , Z ) = {a, c, d}∪{ f }∪{h, i, j, k } = {a, c, d, f, h, i, j, k} j

x j∈ D ( Z 1 )

1




2.1. lépés. (A redukáló munkahalmaz meghatározása) Z2 = Z1 \ D(Z1) \ T(Z1) = {g, u, v, w} Mivel Z2 ≠ ∅, így folytatjuk a 2. iterációs szint lépéssorozatát. 2.2. lépés. (Táblázatos összefoglaló) x∈Z2 g u v w

σA(x) 2 >> 3 << >> 3 << >> 3 <<

PA(x) {f, g} {u, v, w} {u, v, w} {u, v, w}

ρA(x) 3 5 4 5

2.3. lépés. (A gyűjtőpontok halmazának kijelölése) C(Z2) = {u, v, w} 2.4. lépés. (A szomszédfelosztó halmazok meghatározása) F(u,Z2) = PA(u) \ (D(Z0) ∪ D(Z1)) \ (T(Z0) ∪ T(Z1)) \ F(x0,Z2) = = {u, v, w} \ (∅ ∪ {b, e, m}) \ (∅ ∪ {a, c, d, f, h, i, j, k}) \ ∅ = {u, v, w} F(v,Z2) = PA(v) \ (D(Z0) ∪ D(Z1)) \ (T(Z0) ∪ T(Z1)) \ (F(x0,Z2) ∪ F(u,Z2)) = = {u, v, w} \ (∅ ∪ {b, e, m}) \ (∅ ∪ {a, c, d, f, h, i, j, k}) \ {u, v, w} = ∅ F(w,Z2) = PA(w) \ (D(Z0) ∪ D(Z1)) \ (T(Z0) ∪ T(Z1)) \ \ (F(x0,Z2) ∪ F(u,Z2) ∪ F(v,Z2)) = ∅ 2.5. lépés. (A redukált gyűjtőpontok halmazának meghatározása) D(Z2) = {x | x∈C(Z2), F(x,Z2) ≠ ∅} = {u} 2.6. lépés. (A redukált gyűjtőpontok saját szomszédai halmazának meghatározása) W(u,Z2) = F(u,Z2) \ D(Z2) = {u, v, w} \ {u} = {v, w} 2.7. lépés. (A helyettesített pontok halmazának meghatározása) T(Z2) =

UW ( x , Z j

2

) = {v, w}

xj ∈ D ( Z 2 )


3.1. lépés. (A redukáló munkahalmaz meghatározása) Z3 = Z2 \ D(Z2) \ T(Z2) = {g} Mivel Z3 ≠ ∅, így folytatjuk a 3. iterációs szint lépéssorozatát. 3.2. lépés. (Táblázatos összefoglaló) x∈Z3 g

PA(x) {f, g}

σA(x) >> 2 <<

3.3. lépés. (A gyűjtőpontok halmazának kijelölése) C(Z3) = {g}

ρA(x) 3



3.4. lépés. (A szomszédfelosztó halmazok meghatározása) F(g,Z3) = PA(g) \ (D(Z0) ∪ D(Z1) ∪ D(Z2)) \ (T(Z0) ∪ T(Z1) ∪ T(Z2)) \ F(x0,Z2) = = {f, g} \ {b, e, m, u} \ {a, c, d, f, h, i, j, k, v, w } \ ∅ = {g} 3.5. lépés. (A redukált gyűjtőpontok halmazának meghatározása) D(Z3) = {x | x∈C(Z3), F(x,Z3) ≠ ∅} = {g} 3.6. lépés. (A redukált gyűjtőpontok saját szomszédai halmazának meghatározása) W(g,Z3) = F(g,Z2) \ D(Z3) = {g} \ {g} = ∅ 3.7. lépés. (A helyettesített pontok halmazának meghatározása) T(Z3) =

UW ( x , Z ) = ∅ j

3

xj ∈ D ( Z 3 )


4.1. lépés. (A redukáló munkahalmaz meghatározása) Z4 = Z3 \ D(Z3) \ T(Z3) = {g} \ {g} \ ∅ = ∅ Mivel Z4 = ∅, így az iterációs eljárást befejezzük. 5. Eredmény szint A származtatott alaphalmaz (ahol n = 4):

B=

U D(Zi ) = D(Z1) ∪ D(Z2) ∪ D(Z3) = {b, e, m} ∪ {u} ∪ {g} = {b, e, m, u, g}.

i∈[1, n −1]

Tehát a fenti MA = 〈A,λA,ΛA〉 metrikus tér (A = {a, b, c, d, e, f, g, h, i, j, k, m, u, v, w}) környezeti határredukáltja ΛA = 3 határtávolság esetén az MB = 〈B,λB,ΛB〉 metrikus tér, ahol λB = [λA]B, ΛB = ΛA, és B = {b, e, m, u, g}. Ezek után a redukciós eljárás redukciós táblája: QBA

x∈B b e m u g

σA(x) 5 5 5 3 2

ρA(x) 10 10 10 5 3

A pontredukciós ráta: µ ( B) 5 ΦBA = = = 33% , µ ( A) 15 tehát sikerült a harmadára csökkenteni a metrikus tér pontjainak számát oly módon, hogy az eredményül kapott térre a teljességi tétel még érvényes maradjon (vagyis az eredetivel egyenértékű, azaz egy redukált teret kapjunk). Az élredukciós ráta: µ ( PB ) 1 = = 6% . ΨBA = µ ( PA) 17



Az illeszkedési ráta: ρA(b) ∑ 38 b∈B = = 90% . ΧBA = ∑ ρA(a ) 42 a∈A

Megjegyzés. Amint a "legtöbb szomszéd" redukciós eljárás tulajdonságait bemutató állítás megjegyzésénél már említettük, ez a módszer határredukáltat, de nem feltétlenül minimális redukáltat ad eredményként. Például a fenti feladat esetében a {b, f, m, u} alaphalmazú tér a minimális redukált (és persze ezzel pontszámban ekvivalens minimális redukáltak még a {b, f, m, v} és a {b, f, m, w} alaphalmazú terek), ahol a pontredukciós ráta már csak 27% értékű, az élredukciós ráta 0%, míg az illeszkedési ráta 33/42 = 79% értékre csökken, sőt a {b, f, m, v} halmaz esetén ez utóbbi már csak 32/42 = 76%. 1.2.15. Definíció. (Irányított környezeti redukciós eljárás) Legyen MA = 〈A,λA,ΛA〉 egy metrikus tér, és jelölje V az úgynevezett védett gyűjtőpontok halmazát (V ⊆ A). Ekkor a "legtöbb szomszéd" redukciós eljárásban a Zi redukáló munkahalmazban az xj gyűjtőpont szomszédfelosztó halmaza minden xj∈C(Zi) és j 〈− [1, µ(C(Zi))] esetén legyen a következő:

F(xj,Zi) = PA(xj) \

U D(Zk ) \ U T (Zk ) \ [U F]( xm, Zi ) \ (V \ {xj}),

k∈[0, i −1]

k∈[0, i −1]

m∈ 0 , j −1

ahol a jelölések megegyeznek a "legtöbb szomszéd" redukciós eljárásbeliekkel. Megjegyzés. Az irányított környezeti redukciós eljárás alkalmazására akkor van szükség, amikor a metrikus tér bizonyos pontjai (a védett gyűjtőpontok V halmazának elemei) valamilyen szempontból nélkülözhetetlenek, így annak ellenére nem helyettesíthetők, hogy vannak más pontok is a szomszédságukban. Ilyen eset fordulhat elő például akkor, ha egy pont bármely helyettesítéséhez tartozó tolerancia érték negatív lenne (lásd később a metrikus tér relatív redukciójánál). 1.2.16. Példa. (Irányított környezeti redukció) Az alábbi példában a korábban bemutatott "legtöbb szomszéd" redukciós példát egészítjük ki a V = {a, i, v, w} védett gyűjtőpontok halmazával. Ez utóbbinak a szemléletes jelentése például az lehet, hogy az e halmazbeli kirándulók mozgássérültek, így fontos, hogy az ő lakhelyük mindenképpen gyűjtőpont legyen.

Megoldás. A redukció lépései az előző példabeliektől csak a szomszédfelosztó halmaz meghatározásánál térnek el. Végeredményként a B = {a, b, e, g, i, m, u, v, w}. származtatott alaphalmazt kapjuk. Az eljárás láthatóan ezúttal sem adott minimális redukáltat. Az ehhez tartozó ΦBA = 9/15 = 60% pontredukciós ráta rosszabb érték, mint a feladatnak szintén megfelelő (egyébként minimális redukált) {a, e, g, i, m, v, w} alaphalmazhoz tartozó ΦBA = = 47% érték.



1.2.17. Definíció. (A "legközelebbi szomszéd" kiegészítő redukciós eljárás) A "legtöbb szomszéd" redukciós eljáráson többféleképpen lehet javítani. Az egyik kiegészítő módszer a "legközelebbi szomszéd" kiválasztása. Ennek lényege, hogy az azonos (legtöbb) szomszédszámú pontok közül azokat választjuk ki, melyeknek a szomszédsági mértékük a legkisebb. Ekkor jelölje Y(Zi) az MA legnagyobb szomszédsági fokú pontjait a Zi redukáló munkahalmazban, azaz Y(Zi) = {xj | xj∈Zi, σA(xj) = Max({σA(y) | y∈Zi})}, és C(Zi) pedig ezek közül a legkisebb szomszédsági mértékűeket, azaz C(Zi) = {xj | xj∈Y(Zi), ρA(xj) = Min({ρA(y) | y∈Y(Zi)})}. Ekkor az eljárás további része változatlan. 1.2.18. Példa. (A "legközelebbi szomszéd" kiegészítő redukciós eljárás) Ha a "legtöbb szomszéd" redukciós eljárásban a "legközelebbi szomszéd" kiegészítő eljárást is alkalmazzuk, akkor az eredeti eljárásban gyakorlatilag véletlen módon (a rendezettség alapján) kiválasztott ρA(u) = 5 szomszédsági mértékű u pont helyett a kétségtelenül célszerűbb ρA(v) = 4 szomszédsági mértékű v pontot választottuk volna ki, hiszen ez összességében közelebb van az általa helyettesített másik két ponthoz, mint az u pont. (A szomszédsági mérték kisebb értéke éppen ezt az "összességében közelebb" tulajdonságot fejezi ki.) Ekkor a redukáló eljárás hatékonyságát a redukált tér mérete szempontjából jellemző pont- és élredukciós ráta ugyan megegyezik az eredetivel, de az illeszkedési ráta a 38/42 = 90% értékről a 37/42 = 88% értékre csökken (az eredeti redukcióval kapott {b, e, m, u, g} helyett tehát a {b, e, m, v, g} redukciós halmazt tekintve).

1.3. Metrikus tér relatív redukciója Ezúttal a metrikus tér pontjainak egy adott ponttól való távolsága szerint fogjuk a metrikus tér redukcióját elvégezni. 1.3.1. Definíció. (Relatív helyettesíthetőség a metrikus térben) Tekintsük az MA = 〈A,λA,ΛA〉 metrikus teret, továbbá legyen a,b,x∈A, és λA(a,x) ≤ ΛA. Ekkor a b pont helyettesítheti az a pontot az x pontra és az ΛA határtávolságra vonatkozóan, és ezt b~a〈x,ΛA〉 módon jelöljük, ha λA(b,x) ≤ ΛA. Ha a,b,x∈A, és λA(a,x) ≤ ΛA esetén λA(b,x) > ΛA, akkor azt mondjuk, hogy az a pontot nem helyettesítheti a b pont az x pontra és az ΛA határtávolságra vonatkozóan, és ezt b ~/ a〈x,ΛA〉 módon jelöljük. 1.3.2. Állítás. (A relatív helyettesíthetőség elégséges feltétele) Tekintsük az MA = 〈A,λA,ΛA〉 metrikus teret, és legyen a,b,x∈A. Ha λA(b,a) + λA(a,x) ≤ ΛA, akkor b~a〈x,ΛA〉.



Bizonyítás. Mivel a háromszög egyenlőtlenség szerint a legrosszabb esetben λ(b,x) = λ(b,a) + λ(a,x), így ha λA(b,a) + λA(a,x) ≤ ΛA, akkor nyilván λA(a,x) ≤ ΛA és λA(b,x) ≤ ΛA, tehát a definíció szerint b ~ a〈x,ΛA〉. Megjegyzés. Feltehető volna a kérdés, mi szükség van fenti állításban megfogalmazott közvetett (minimális) helyettesíthetőségi feltételre (λA(b,a) + λA(a,x) ≤ ΛA), amikor a definíció megadja a közvetlen feltételt (λA(a,x) ≤ ΛA esetén λA(b,x) ≤ ΛA is teljesüljön). Ráadásul ez a közvetett feltétel a lehető legrosszabb esetet tételezi fel. Ugyanis tekintsük azt a geometriai értelmezést, melyben a b, az a és az x pontok egy bax háromszöget alkotnak. Ekkor a bx oldal hossza (hiszen a λA(b,x) érték ezt fejezi ki) attól függ, hogy a b pont hogyan helyezkedik el az ax által meghatározott egyeneshez képest. A háromszög egyenlőtlenség által meghatározott legnagyobb érték (λA(b,a) + λA(a,x)) arra az elfajult esetre vonatkozik, ha a b pont éppen rajta van az ax egyenesen, de nem az a pontnak az x pont felé eső oldalán, hanem az ellenkező oldalon. Ez tehát a legrosszabb eset. Ha a b pont bárhol másutt van, akkor a fenti közvetett helyettesíthetőségi feltétel nem teljesülése (λA(b,a) + λA(a,x) > ΛA) esetén is fennállhat a helyettesíthetőség definíciószerinti feltétele. (Például b = x és λA(a,x) = ΛA esetén nyilván λA(b,a) = λA(a,x), tehát λA(b,a) + λA(a,x) = 2 ∗ ΛA. A legszélsőségesebb eset, ha az x pont az ab egyenes felezőpontján van, tehát λA(b,a) = 2 ∗ λA(a,x), továbbá λA(a,x) = ΛA. Ekkor már λA(b,a) + λA(a,x) = 3 ∗ ΛA. Mindkét esetben λA(b,x) ≤ ΛA, tehát a definíció szerint b~a〈x, ΛA〉.) A λA(b,a) és a λA(a,x) értékekre vonatkozó minimális helyettesíthetőségi feltétel tehát lényegesen szigorúbb, mint a definíció szerinti λA(b,x) értékre vonatkozó feltétel. Azonban mi van akkor, ha bármilyen okból nem ismerjük a λA(b,x) értéket? Tegyük fel, hogy ismert a λA(a,x) érték, és meg tudjuk határozni a λA(b,a) értéket, azonban a λA(b,x) érték ismeretlen. Mikor fordulhat ilyen elő? Például akkor, ha az x pontról meglévő egyetlen ismeretünk éppen a λA(a,x) érték (vagyis nem tudjuk, hogy hol helyezkedik el az MA metrikus térben). Ilyenkor valóban nem tehetünk mást, mint hogy a legrosszabb esetet tételezzük fel és a bx oldalhoz a λA(b,a) + λA(a,x) távolságot rendeljük hozzá, a b pontnak pedig egy későbbi, az x pontra vonatkozó és a c ponttal való helyettesíthetőségi vizsgálatánál már ebből az értékből indulunk ki. A metrikus térben így elvégzett pontredukció ugyan nem mindig a legkedvezőbb, de biztosan nem fog hamis helyettesítéshez vezetni. 1.3.3. Állítás. (Relatív helyettesíthetőség tulajdonságai) A relatív helyettesíthetőség egy hasonlósági reláció, azaz reflexív és szimmetrikus, de nem korlátlanul tranzitív.

Bizonyítás. A reflexivitás (∀a∈A: a~a〈x,ΛA〉), és a szimmetria (∀a,b,x∈A: b~a〈x,ΛA〉 ⇒ a~b〈x,ΛA〉) a fenti definíciókból triviálisan következik, a teljes A halmazra vonatkozó általános tranzitivitást viszont az ΛA határtávolságra vonatkozó korlátosság akadályozza meg (így lehet olyan a,b,c∈A, melyekre valamely x∈A esetén bár c~b〈x,ΛA〉 és b~a〈x,ΛA〉, mégis c ~/ a〈x,ΛA〉).



1.3.4. Definíció. (Metrikus tér relatív redukáltja) Egy MB = 〈B,λB,ΛB〉 metrikus teret az MA = 〈A,λA,ΛA〉 metrikus tér x∈A pontjára vonatkozó, vagy csak röviden x-relatív redukáltjának nevezünk, és ezt MB = RedR(MA,x) módon jelöljük, ha .1. az MB altere az MA-nak, azaz MB ⊆ MA, .2. x∈ B, .3. minden a∈ A \ B pont esetén létezik olyan b∈B pont, melyre b~a〈x,ΛA〉 módon az a pontot helyettesítheti a b pont.

2. Antimetrikus terek

2.1. Definíció. (Antimetrikus tér, közelségfüggvény, határközelség) Tekintsük az A halmazt, és a rajta értelmezett νA : A×A → (0, 1] függvényt, melyet közelségfüggvénynek nevezünk, és ahol (0, 1] a 0 és 1 közötti balról nyílt, jobbról zárt intervallum valós számainak halmaza, és az 1 értéket maximális közelségi értéknek nevezzük. Ekkor az SA = 〈A,νA〉 struktúrát antimetrikus térnek nevezzük, ha az MA = 〈A,λA〉 struktúra egy metrikus tér, ahol a λA távolságfüggvényt minden a,b∈A esetén az alábbi, úgynevezett metrikus transzformáció határozza meg: 1 −1. λA(a, b ) = νA(a, b ) A továbbiakban hozzárendelünk az antimetrikus térhez egy úgynevezett NA határközelséget (NA∈(0, 1]), és az ezzel kiegészített antimetrikus teret SA = 〈A,νA,NA〉 módon jelöljük, és egyszerű korlátos antimetrikus térnek, de legtöbbször röviden ezt is csak antimetrikus térnek nevezzük. Az antimetrikus tér elemeit is általában pontoknak fogjuk nevezni.

1. Megjegyzés. (Egy alternatív metrikus transzformáció) A közelségi függvényből távolságfüggvény létrehozására alkalmas még a λA(a,b) = 1 – νA(a,b) metrikus transzformáció is. 2. Megjegyzés. (Hasonlósági tér) Az antimetrikus teret egy tipikus gyakorlati alkalmazása miatt hasonlósági térnek is nevezzük. 2.2. Definíció. (Általánosított antimetrikus tér) Az antimetrikus tér fogalmát több irányban is általánosíthatjuk. Az alábbiakban a legegyszerűbbet mutatjuk be. Legyen a közelségfüggvény νA : A×A → (0, Nmx], ahol Nmx∈R, Nmx > 0 a maximális közelségi érték. Ekkor az SA = 〈A,νA,NA,Nmx〉 struktúrát általánosított antimetrikus térnek nevezzük, ha az NA határközelségre NA∈[0, Nmx] teljesül, és az MA = 〈A,λA〉 struktúra egy metrikus tér, ahol a λA távolságfüggvényt minden a,b∈ A esetén az alábbi metrikus transzformáció határozza meg: 1 1 − . λA(a, b ) = νA(a, b ) Nmx



2.3. Állítás. (Az antimetrikus tér tulajdonságai) Legyen SA = 〈A,νA〉 egy antimetrikus tér. Ekkor teljesülnek az alábbiak: .1. minden a,b∈A esetén νA(a,b) ≥ 0, .2. minden a,b∈A esetén νA(a,b) = 1 ⇔ a = b, .3. minden a,b,c∈A esetén 1 νA(a, c ) ≥ , 1 1 + −1 νA(a, b ) νA(b, c ) ahol ez utóbbit nevezzük közelségi (vagy inverz) háromszög egyenlőtlenségnek. .4. ha 〈A,λA〉 egy szimmetrikus metrikus tér, ahol minden a,b∈A esetén a λA távolságfüggvényt a metrikus transzformáció határozza meg a νA közelségi függvényből, akkor az 〈A,νA〉 antimetrikus tér is szimmetrikus, azaz minden a,b∈A esetén νA(a,b) = νA(b,a).

Bizonyítás. Az .1., .2. és a .4. pontok közvetlenül következnek az antimetrikus tér definíciójából, illetve a metrikus tér definíciójának azonos pontjaiból, a .3. pont pedig a metrikus tér háromszög egyenlőtlenségéből következik, ha a távolságfüggvény-értékek helyett a metrikus transzformációt írjuk, majd megfelelő átrendezésekkel a νA(a,c) értéket kifejezzük. 2.4. Definíció. (Relatív helyettesíthetőség az antimetrikus térben) Tekintsük az SA = 〈A,νA,NA〉 antimetrikus teret, és legyen az a,b,x∈A. Ekkor a b pontot helyettesítheti az a pont az x pontra és az NA határközelségre vonatkozóan, és ezt b~a〈x,NA〉 módon jelöljük, ha νA(a,x) ≥ NA esetén νA(b,x) ≥ NA is teljesül. Ha a,b,x∈A, és νA(a,x) ≥ NA esetén νA(b,x) < NA, akkor azt mondjuk, hogy a b pontot nem helyettesítheti az a pont az x pontra és az NA határközelségre vonatkozóan, és ezt b ~/ a〈x,NA〉 módon jelöljük. 2.5. Állítás. (Relatív helyettesíthetőség feltétele) Tekintsük az SA = 〈A,νA,NA〉 antimetrikus teret, és legyen a,b,x∈A. Ekkor b~a〈x,NA〉, ha 1 ≥ NA. 1 1 + −1 νA(a, b ) νA(b, c )

Bizonyítás. A közelségekre vonatkozó (inverz) háromszög egyenlőtlenségből és az antimetrikus helyettesíthetőség definíciójából közvetlenül következik.

Irodalomjegyzék

Metrikus Hasonlóság: http://www.inf.u-szeged.hu/oktatas/jegyzetek/CsirikJanos/mesterseges_intelligencia/MI12.ppt http://erg.bme.hu/szakkepzes/2felev/pszichometria/Tobbdimenzios_skalazas1.pdf http://www.animakonyv.hu/index.php?BODY=BookInfo&OP=details&ID=75901&VISIT=1



Gotoh távolság: http://phylogeny-cafe.elte.hu/personnel/miklos/PhD5.pdf http://www.ifi.uzh.ch/ddis/fileadmin/user_upload/kiefer/simpack/javadoc/simpack/measure/external/simm etrics/SmithWatermanGotoh.html http://escher.elis.ugent.be/publ/Edocs/DOC/P106_072.pdf

Hamming távolság: http://hu.wikipedia.org/wiki/Hamming-t%C3%A1vols%C3%A1g

Hellinger távolság: http://www.oplab.sztaki.hu/tanszek/download/I_Tobbsz_dont_modsz.pdf http://www.econ.unideb.hu/oktatas_es_kutatas/oktatasi_anyagok/download/20070307_Diszkriminancia.pdf

Jaccard hasonlóság: http://www.hik.hu/tankonyvtar/site/books/b137/ch03s03s02s02.html http://info.ilab.sztaki.hu/~lukacs/AdatbanyaEA2005/dm05_03_klaszterezes.pdf http://www.mbt-ak.mtesz.hu/Tartalom/2003/88-1_2-Korsos.pdf http://www-phch.chem.elte.hu/magyar/sokvaltozos/J1-2.fej.pdf

Klaszterezés: http://www.cs.uiuc.edu/~hanj/bk2/07.ppt http://info.ilab.sztaki.hu/~lukacs/AdatbanyaEA2005/klaszterezes.pdf http://www.cse.iitb.ac.in/dbms/Data/Courses/CS632/1999/clustering/node21.html http://64.233.183.104/search?q=cache:kU6xOorj3LUJ:webni.innen.hu/Klaszterez_c3_a9s+Klaszterez%C3 %A9s&hl=en&ct=clnk&cd=8&gl=uk http://www.inf.unideb.hu/valseg/dolgozok/igloi/tvstat/cluster0.pdf

Levenshtein távolság: http://en.wikipedia.org/wiki/Levenshtein http://categorizer.tmit.bme.hu/~domi/textmining/textmining06.ppt http://textmining.tmit.bme.hu http://digitus.itk.ppke.hu/~sass/nyelvtech07/ea/nyelvtech07_ea_05.pdf

Mahalanobis távolság: http://isi.cbs.nl/glossary/term865.htm http://www.gupt.bme.hu/letolt/hajdu/okonometria/MultiVar/BETbroker.pdf

Manhattan távolság: http://www-phch.chem.elte.hu/magyar/sokvaltozos/J1-2.fej.pdf http://jegyzet.sth.sze.hu/ftp/!Muinfo/!Felsobb_eves/Nem_szakiranyos/Statisztikai_algoritmusok_(sz13)/08 _osztalyoz/11-stat9(klasz).pdf http://www.inf.u-szeged.hu/~katona/gis.pdf

Minkowski távolság: http://hu.wikipedia.org/wiki/Minkowski-t%C3%A9r http://www.econ.unideb.hu/oktatas_es_kutatas/oktatasi_anyagok/download/20070307_Faktor_klaszter.pdf



Monge Elkan távolság: http://www.dcs.shef.ac.uk/~sam/stringmetrics.html http://secondstring.sourceforge.net/doc/iiweb03.pdf

Needleman-Wunch távolság: http://biokemia.bio.u-szeged.hu/oktatas/Makro/Makromol%20man%203rd.ppt

Smith-Waterman távolság: http://www.inf.u-szeged.hu/~banhalmi/adatb/3_eloadas.ppt http://angel.elte.hu/~fij/homepage/okt/gbi/07osz/pdf/gbi2-07osz.pdf http://phylogeny-cafe.elte.hu/personnel/miklos/PhD1.pdf

Soundex távolság: http://dict.mstier.de/?Form=dict2&Database=*&Query=way http://www.dcs.uni-pannon.hu/CIR/cikkek/Database_Theory.pdf http://www.prog.hu/leveltar/level/200556/SQL+lista+RE+tisztitas.html

METRIKUS ÉS ANTIMETRIKUS TEREK, ÉS REDUKCIÓJUK. Nagy István Budapesti Műszaki Főiskola, Neumann János Informatikai Kar

Recommend Documents