Lukáš Janák
Zdroj:„Discovery of Spatial Association Rules in Geographic Information Databases
Krzysztof Koperski, Jiawei HanSimon Fraser University
Burnaby. B.C., Canada V5A 1S6e-mail: {koperski,han}@cs.sfu.ca
Hledání prostorových asociačních pravidel v prostorových
databázích
Obsah prezentace
• Základní pojmy– GIS– Data mining– Asociační pravidla– Víceúrovňová asociační pravidla
• Prostorová asociační pravidla• Příklad (+ aproximační algoritmy)• Asociace v praxi• GRASS a asociace• Závěr
Základní pojmy I
• GIS„soubor nástrojů pro sběr, ukládání, vyhledávání, transformaci azobrazování prostorových dat z reálného světa pro jednotlivé účely“
• Prostorová data„data, která se vztahují k určitým místům v prostoru, a pro která jsou na potřebné úrovni rozlišení známé lokalizace těchto míst“
• Geografická data„druh prostorových dat. Známá geografická poloha místa na Zemi, ke kterému se data vztahují“
• Prostorová databáze (v širším smyslu)Databáze s prostorovými daty
Základní pojmy II
• Geoprvek– „základní prostorová entita popisovaná prostorovými daty“– Např. řeka, důl, studna…– Odkazujeme se jedinečným identifikátorem – adresa, kód. – Popis geoprvku – 5 složek:
Geometrická - poloha + geometrické vlastnostiPopisná – negeometrické vlastnosti (atributy)Časová…Vztahová...Funkční...
– Jak to implementovat?
Základní pojmy III
• Vektorový datový model (zjednodušeně) – Pro geoprvky je odděleně vedena geometrická (prostorová databáze) a popisná složka (relační databáze)
– Spojeno přes jedinečný identifikátor– Geoprvky znázorněny pomocí geometrických prvků: bod, linie, plocha
Příklad:Bod (id_bod, x, y)Plocha (id_plocha, id_linie:multi)Linie (id_linie, id_plocha_p, id_ plocha_l, id_bod:multi)
Parcela (id_parcela, id_majitel, rozloha, id_plocha)Rybník (id_rybník, id_majitel, rozloha, id_plocha)
Data Minig I
• Data Minig– Integrovaný obor matematiky, ekonomie a informatiky – Česky : „dolování znalostí z dat“– Obor vznikl jako reakce na myšlenku využít dlouhodobě ukládaná data (do archivů… ) nejen ke svému původnímu účelu, ale i k získání dalších poznatků
– Využití:• Podpora strategické rozhodování ve firmě• Nové poznatky socilogie, politologie, biologie …
– Definice:„Dolováním znalostí nazýváme proces netriviálního
získávání implicitní, dříve neznámé a potencionálně užitečné informace z dat“
∧∧∧∧∧
Data Minig II
• Metody dolování:– statistických charakteristiky,– korelační a regresní analýza,– multidimenzionální statistické metody,– diskriminační a faktorovou analýzu,– hledání asociací,– shlukovou analýzu,– konstrukce rozhodovacích stromů,– a mnoho dalších (fantazii se meze nekladou)
• SQL pouze jako pomocný prostředek
∧∧∧∧∧
Asociace I
• Asociace– Hledání vztahů mezi některými podmnožinami atributů– Pro atributy A a B mohl být vztah například typu:
• „jestliže A=1, pak B=5“ (implikace)• „A=1 právě tehdy, když B=5“ (asociace)• „hodnoty A korelují s B“ (korelace)
• Pojmy:– Výraz typu A = y nazveme formule (predikát), označíme F Např.: F1 = věk (30-40), F2 = plat (10 000 - 20 000)
– Složená formule: ¬F1 , F1 ∧ F2 , F1 ∨ F2, ….– Sentence (pravidlo):
F1 ⇒ F2antecedent ⇒ sukcedent
– Př.:věk (30-40) ⇒ plat (10 000 - 20 000)
∧∧∧∧∧
Asociace II
• Pojmy:– s ... spolehlivost… určuje „sílu“ implikace– p ... podpora … určuje „významnost“ implikace
• Příklad kompletního pravidla
„věk (30-40) ⇒ plat (10 000 - 20 000) s(66,7%) p(33,3%)”„kouření ⇒ infarkt ∨ rakovina_plic s(80,0%) p(25,0%)”
• Spolehlivost pravidla F1 ⇒ F2 je pravděpodobnost toho, že jeden objekt vyhovuje predikátům z antecedentu a zároveň sukcedentu .
• Podpora pravidla F1 ⇒ F2, je podíl počtu objektů, které vyhovují formuli antecedentu i sukcedentu ku celkovému počtu objektů .
• V praxi máme zdanou dolní mez pro s i pro p a hledáme pouze silnápravidla
∧∧∧∧∧
Asociace III
• Hledání asociací– Triviální algoritmusPostupné generování všechny možné kombinace predikátů na levé i pravé straně pravidla a testovat v datech, je-li výsledkem silné asociační pravidlo. Exponenciální časová složitostí.
– Apriori algoritmusNejprve jsou vyhledány kombinace antecedentu, které dosahují minimální stanovené hodnoty podpory a z nich jsou generovány silné asociace (takové, které navíc dosahují i minimální spolehlivosti).
∧∧∧∧∧
Asociace - Příklad• Vstup
18.11.2005SL 60061 00039
27.08.2005E 420 CDI37 00040
16.02.2005A 160 CDI22 00018
06.05.2005E 420 CDI35 00033
24.10..2005C 230 27 00033
13.10.2005A 15025 00043
20.04.2005A 160 CDI25 00031
11.07.2005C 230 31 00027
21.06.2005A 15020 00039
09.01.2005SL 60050 00041
18.04.2005E 420 CDI42 00042
11.11.2005A 160 CDI27 00033
26.05.2005E 420 CDI36 00032
25.11.2005C 230 27 00031
08.09.2005A 15025 00051
03.01.2005A 160 CDI25 00035
05.03.2005C 230 30 00025
01.01.2005A 15020 00041
DatumTypPlatVěk
∧∧∧∧∧
Úprava DB (kategorizace)• Věk: 20 - 30… 1
30 - 40 … 240 – 50 … 350 - 60 … 4
• Plat(tis.): 20 – 30 … 130 – 40 … 240 – … 3
• Typ: A150, A 160 … 1C230, E420 … 2
SL600 … 3• Datum: kvartály 1 - 4
Asociace - Příklad• Upravený vstup
4332
3223
1111
2222
4212
4113
2112
3221
2112
1333
2233
4112
2222
4212
3114
1112
1221
1113
DatumTypPlatVěk
∧∧∧∧∧
• Ptáme se:– Jaký je vztah mezi věkem a platem?– Jaký je vztah mezi platem a typem?– Jaký je vztah mezi věkem a typem?– Jaký je vztah mezi datem a typem?
• Vztah věk a plat:
00142123
1262
0211
321Věk / plat
Asociace - Příklad• Vztah věk a plat (pokr.):
„věk (30-40) ⇒ plat (20 000 - 30 000) s(67%) p(33%)”
• Další:„plat (20 000 - 30 000) ⇒ typ (A 150, A 160) s(80%) p(44%)“„plat (30 000 - 40 000) ⇒ typ (C 230, E 420) s(100%) p(28%)”
„plat nad 40 000 ⇒ typ (SL 600) s(67%) p(11%)”„datum (4. - 6.) ⇒ typ (C 230, E 420) s(60%) p(17%)”„věk (30 - 40) ⇒ typ (A150, A160) s(44%) p(22%)”
„věk (30-40) a plat (20 000- 30 000) ⇒ typ (A 150, A 160) s(67%) p (22%)”
0014
2123
1262
0211
321Věk /plat
∧∧∧∧∧
Asociace IV
• Víceúrovňová asociační pravidla– Pracuje se na různých konceptuálních úrovních– Různý způsob kategorizace:
– Důsledek – jiná pravidla:
„plat nad 40 000 ⇒ typ (C 230, E 420) s(33%) p(11%)”„plat nad 40 000 ⇒ typ (SL 600) s(67%) p(11%)”
„plat nad 40 000 ⇒ typ (C 230, E 420, SL 600) s(100%) p(11%)”
Typ: A150, A160 … 1 C230, E420 … 2
SL600 … 3
Typ: A150, A 160 … 1C230, E420, SL600 … 2
Asociace IV
• Víceúrovňová asociační pravidla (pokr.) – Kategorie lze uspořádat hiearchycky
1A150, A 160Levnější
2C230, E420, SL600
Dražší
Typ
1A150, A 160
Levný
2C230, E420Středně d.
3SL600Drahý
(Typ (Levnější (A150,A160), (Dražší (Středně d. (C320,E420),Drahý(SL600)))))
Prostorová asociační pravidla
• Co chceme najít? Pravidla typu:
Neboli:„92% měst v Britské Kolumbii na břehu vodní plochy je blízko USA“
• Odkud?Prostorová databáze
• Jak?Postup založený na využití poznatků z postupů dolování různých typů asociačních pravidel (víceúrovňová pravidla…) u jiných typů dat aprostorové analýze
Prostorová asociační pravidla
• Definice:„Prostorové asociační pravidlo je asociační pravidlo, které obsahuje alespoň jeden prostorový predikát“
• Prostorový predikát– protíná, je_uvnitř, je_vně, sousedí, pokrývá, je_pokryt– severně-, jižně- , západně- , východně položeno – je_blízko, je_daleko
Příkladje (X, dům) a je_blízko (X, pláž)→je_drahý (X)
3 typy predikátů!!!
Příklad – zadání úkolu
• Zdroj datGeografická databáze s údaji o Britské Kolumbii (CAN) se strukturou:
město (název, typ, počet_obyvatel, geo, …)komunikace (název, typ, geo, …)voda (název, typ, geo, …)důl (název, typ, geo, …)hranice (název, typ, administrativní_oblast_1,
administrativní_oblast_2, geo, …).
• GeoMiner
Příklad – konceptuální hierarchie
• Nutné pro získávání více-úrovňových asociačních pravidel• Konceptuální hierarchie pro voda (3 úrovně):(voda (moře (průliv(Georgia_Strait,…), záliv (…),…),
řeka (velká_řeka (Fraser_River,…), …), jezero (velké_jezero(Okanagan_Lake,…),…) ,…) ,…)
• Podobně lze organizovat i prostorové predikáty (topologické vztahy). Např. predikát je_poblíž pokrývá množinu predikátů protíná, sousedí, obsahuje a je_blízko.
• A také popisné predikáty…
Příklad – zadání úkolu
• Cíle analýzyPředpokládejme, že uživatel má zájem nalézt na mapě Britské Kolumbie silné prostorové vztahy mezi velkými městy a „blízkými“ objekty – doly, hranicemi států, vodními plochami a významnými komunikacemi.
• Dotaz pro GeoMinerdiscover spatial association rules
inside British Columbia
from komunikace K, voda V, důl D, hranice H
in relevance to město M
where je_poblíž (M.geo, X.geo) and X in {K,V,D,H}
and M.typ=“velkoměsto“
and K.typ in {dálnice}
and V.typ in {moře, oceán, velké jezero, velká řeka}
and H.administrativní_oblast_1 in “B.C.“
and H.administrativní_oblast_2 in “U.S.A.“
Příklad – zpracování dotazu
1. Vyhledání objektů relevantních k dotazu
1. velkoměsta (v B.C. splňuje 40 měst)2. dálnice3. moře, oceány, velká jezera a velké řeky4. doly5. hranice B.C. a USA
komunikace (název, typ, geo, …)
2. Nalezení objektů z množin 2 – 5, které jsou vůči nalezeným velkoměstům v množině 1 ve vztahu je_poblíž.
Příklad – zpracování dotazu
2. Nalezení objektů… (pokr.)• Nutno implementovat efektivně vzhledem k počtu
objektů ale zároveň stačí aproximace• Možná řešení: MBR, plane sweeping, R*-stromy1. MBR (MOO)
• Aproximace geoprvku obdélníku2. Plane sweeping (metoda pohyblivé přímky)
• Preparata & Shamos, 1985
• obecná metoda používaná při řešení rovinných problémů• posunování vertikální přímky, kterou horizontálně po rovině• přímka postupně zasahuje jeden po druhém objekty v rovině • když dojde k takovéto události, je vyřešen dílčí problém na přímce • použití:
– Vyhledávání průsečíků přímek (O(n log n + k))– Vyhledání průsečíku hran polygonů -> průnik polygonů– Vyhledávaní průniků obdélníků (MBR,MOO)
Příklad – zpracování dotazu
2. Plane sweeping - příklad
Příklad – zpracování dotazu
3. R*- stromy• DS pro zachycení prostorových vztahů• Varianta R-stromů• Vnitřní uzly obsahují záznamy tvaru (I, ukazatel),
• ukazatel ukazuje na podstrom v R-stromu• I pokrývá všechny MBR, které se vyskytují v podstromě
• List obsahuje ukazatel na prostorový objekt• Problém: MBR se mohou překrývat -> složité vyhledávání• Řešení: optimalizace při konstrukci R-stromu • R-stromy:
• minimalizovat objem odpovídající oblasti I• R*-stromy:
• optimalizace velikosti ohraničujícího prostoru• velikosti okraje I• velikosti překrytí těchto prostorů
Příklad – zpracování dotazu
3. R*- stromy – příklad• Aplikace R*-stromů na zjišťování průniků p. objektů• Aproximace objektu lichoběžníky -> vybudování R*-stromu
pro 1 objekt
Příklad – zpracování dotazu
3. R*- stromy – vyhledávaní průniků• Hledám 2 lichoběžníky v průniku• Pokud nemají průnik 2 MMO, tak nemohou mít ani
žádné jimi pokryté lichoběžníky• Nutno projít 2 R*-stromy v čase O(n1 + n2)
Příklad – zpracování dotazu
…………
…
AlallaUS highway_97 Okanagan_LakePentincton
highway_97 Prince_George
US highway_1,highway_17
Juan_de_Fuca_StraitSaanich
US highway_1,highway_17
Juan_de_Fuca_StraitVictoria
DůlHraniceKomunikaceVodaVelkoměsto
je (X, velkoměsto) → je_poblíž (X, voda) (80%)(nejvyšší konceptuální úroveň dat a predikátů)
Příklad – zpracování dotazu
3. Upřesňující výpočet pro predikáty. Každý predikát je_poblíž je nahrazen konkrétním predikátem
(protíná, sousedí, obsahuje a je_blízko)
Juan_de_Fuca_Strait <sousedí, J.Fuca_Strait>
<je_blízko , US><protíná, highway_97><sousedí,Okanagan_Lake>Pentincton
<protíná, highway_97>Prince_George
<je_blízko , US><protíná, highway_1><protíná, highway_17>
<sousedí, J.Fuca_Strait> Saanich
<je_blízko , US> <protíná, highway_1><protíná, highway_17>
<sousedí, J.Fuca_Strait> Victoria
HraniceKomunikaceVodaVelkoměsto
Příklad – zpracování dotazu• Z předchozí tabulky získáme:
je (X, velkoměsto) → je_blízko (X, dálnice) (73%)je (X, velkoměsto) protíná (X, dálnice) → sousedí (X,voda) (86%)
(nejvyšší konceptuální úroveň dat a zpřesnění predikátů)
29<je_blízko, dálnice> 1
28<je_blízko, us_hranice> 1
25<sousedí, voda>, <protíná, dálnice> 2
23<sousedí, voda>, <je_blízko, us_hranice> 2
26<je_blízko, us_hranice>, <protíná, dálnice> 2
22<sousedí, voda>, <je_blízko, us_hranice>, <protíná, dálnice> 3
29<protíná, dálnice> 1
32<sousedí, voda> 1
Počet Frekventované množiny k-predikátů k
∧
∧
Příklad – zpracování dotazu
4. Upřesňující výpočet pro data – dle konceptuální hierarchie.
a) Druhá úroveň
11<sousedí, moře>, < je_blízko, provincial_highway> 2
22<je_blízko, us_hranice>, < je_blízko, provincial_highway> 2
28<je_blízko, us_hranice> 1
21<protíná, provincial_highway> 1
24< je_blízko, provincial_highway> 1
15<sousedí, moře>, <je_blízko, us_hranice> 2
19<je_blízko, us_hranice>, <protíná, provincial_highway> 2
10<sousedí, voda>, <je_blízko, us_hranice>, <protíná, dálnice> 3
11<sousedí, řeka> 1
21<sousedí, moře> 1
Počet Frekventované množiny k-predikátůk
Příklad – zpracování dotazu
b) Třetí úroveň
je (X, velkoměsto) → sousedí (X, moře) (53%)(2. konceptuální úroveň dat a zpřesnění predikátů)
je (X, velk.) sousedí (X, georgia_st) → je_blízko (X, us) (78%)(3. konceptuální úroveň dat a zpřesnění predikátů)
28<je_blízko, us_hranice> 1
7<sousedí, georgia_strait>, <je_blízko, us_hranice> 2
10<sousedí, fraser_river> 1
9<sousedí, georgia_strait> 1
Počet Frekventované množiny k-predikátů k
∧
Algoritmus
• Vstup1. Prostorová databáze s popisnou složkou a množina
konceptuálních hierarchií2. Dotaz nad bází dat3. Dva numerické parametry pro každou konceptuální úroveň:
• minimální podpora• minimální spolehlivost
• VýstupSilná víceúrovňová prostorová asociační pravidla pro množinu relevantních objektů a vztahů.
• Popis algoritmuRaději ne…
Asociace v praxi• Projekt GeoMiner pravděpodobně zastaven, nebo alespoň
přerušen ??? (záhada č.1)• Projekt SPIN!
– zaměřený na nové možnosti pro analýzu prostorových dat– implementaci platformy pro data mining prostorových dat– subsystém SPADA– http://www.ais.fraunhofer.de/KD/SPIN/
• Existuje software (komerční i free), které s funkcemi, které lze zařadit do metod DM:– shlukování– statistické analýzy (modelování, korelace, regrese) – v podstatě jde o aplikaci DM metod nad popisnou složkou GIS +
rozšíření o možnosti vizualizace výsledků
GRASS a asociace• GRASS lze rozšířit o rozhraní pro statistickou analýzu dat a grafickou
prezentaci výsledku – R– http://www.geog.uni-hannover.de/grass/statsgrass/grass_geostats.html
• Systém R poskytuje širokou škálu statistických technik a algoritmů strojového učení, např. klasifikace, shlukováni, lineární a nelineární modelováni, asociační pravidla apod.
• Tomáš Buk, Petr Kuba, Luboš Popelinský : GRR (záhada č.2)– je systém pro dolování v geografickém informačním systému GRASS– grafické uživatelské rozhraní– rozhraní pro komunikaci se systémem R– rozhraní pro komunikaci s vlastním geografickým informačním systémem. – http://gis.vsb.cz/GISEngl/Publications/GIS_Ova/2003/Referaty/popelinsky.htm
Závěr
• Možnosti využití– Geografie– Biologie– Energetika– Ochrana životního prostředí – jiné oblasti (záleží na fantazii…)
Bonus
Děkuji za pozornost
