titl CZ OPVK_MU_vlevo_2
Bregmanove divergencie
1
Bregmanove divergencie
Využitie indexovacích štruktúr pre efektívne podobnostné vyhľadávanie
Lukáš Holecy

zahlavi CZ
Ľudské vnímanie podobnosti často nie je metrické
Distribúcia pravdepodobnosti
Rozdiel signálov
Porovnanie rôznych atribútov obrázkov (farby, textúry, tvary)
Sledovanie pohybu
A dalšie
2
Bregmanove divergencie

zahlavi CZ
Bregmanová divergencia
*
*
*
*
* Každá Bregmanova divergencia je založená na nejakej rýdzo konvexnej funkcii f
Bregmanove divergencie
3

zahlavi CZ
Kullback-Leibler divergence
Založené na funkcii:
Itakura-Saito divergence
Založené na funkcii:
Squared Euclidean
Založené na funkcii:
4
Bregmanove divergencie

zahlavi CZ
http://www.sonycsl.co.jp/person/nielsen/BregmanDivergence/
Grafická reprezentácia
Bregmanove divergencie
5

zahlavi CZ
Bregmanové divergencie nie sú symetrické
Má ľahké riešenie:
V Bregmanových divergenciách neplatí trojuholníková nerovnosť
Nemá ľahké riešenie
Špeciálne indexovacie štruktúry  pre každú Bregmanovú divergenciu
Univerzálna indexovacia štruktúra
Problém
Bregmanove divergencie
6

zahlavi CZ
Máme d rozmerný priestor S v ktorom vyhľadávame
Rozšírime priestor S na d + 1 rozmerný priestor S+, tak, že každému vektoru x v prestore S
pridáme nový rozmer  ktorého hodnota bude f(x) kde f je funkcia podľa ktorej je definovaná
konkrétna Bregmanová divergencia.
Pre nejaky query point budeme vždy počitat D(x,q) nie D(q,x)
Použijeme nejakú štruktúru, ktorá využíva bounding rectangle
Napr. R-Strom, VA File
Obecná metóda pre všetky Bregmanové divergencie
Bregmanove divergencie
7

zahlavi CZ
Vychádza z B-Stromu
Vhodný i pre plošné data
http://gis.umb.no/gis/applets/rtree2/jdk1.1/
Algoritmus 1KNN:
Vstup: R-tree T, Query q
Výstup: Set S
1: Set the k-nearest neighbor set S as empty
2: Set threshold distance θ = ∞
3: Clear a priority queue Q
4: Enqueue the root of T into Q
5: while Q is not empty do
6:    Dequeue the head node N from Q
7:    if N is a leaf node then
8:      for each point p stored in N do
9:        if Df (p,q) <θ then
10:        Insert p into S and update θ
11:   else
12:     for each child node M of N do
13:       Retrieve the MBR R of M
14:       if LB(R,q) < θ then
15:         Enqueue M into Q with LB(R,q)
16: Return points in S
R-Strom
Bregmanove divergencie
8

zahlavi CZ
Každé x z množiny S+ je pokryté MBR R len ak LRi ≤ xi ≤ Uri
a zároveň LRi+1 ≤ xi+1 ≤ Uri+1
Ako zistit LB(R, q)
Bregmanove divergencie
9

zahlavi CZ
Každé x z množiny S+ je pokryté MBR R len ak LRi ≤ xi ≤ Uri
a zároveň LRi+1 ≤ xi+1 ≤ Uri+1
Ako zistit UB(R, q)
Bregmanove divergencie
10

zahlavi CZ
- Vypočítame raz na začiatku vyhľadávania
Na to, aby sme mohli vyradit z vyhladavania cely MBR staci, ak LB je väčšie ako θ. To či je väčšie
dokážeme vypočítať v O(d) krokoch, pretoze stačí pre každú dimenziu
nájsť menšiu hodnotu medzi               a                .
11
Bregmanove divergencie

zahlavi CZ OPVK_MU_vlevo_2
Bregmanove divergencie
12
•Děkuji za pozornost.