# ISTRAŽIVANJE PODATAKA

Istraživanje podataka je proces automatskog otkrivanja korisnih informacija u velikom skladištu podataka.

## 01 - Atributi

__Skup podataka__ je kolekcija objekata (slogova, uzoraka, entiteta...).

__Atributi__ su svojstva ili karakteristike objekata. __Vrednost atributa__ je broj ili simbol pridružen tom atributu.

#### Tipovi atributa

| Vrsta atributa | Tip atributa | Operacije | Primeri |
| -------------- | ------------ | ------------------- | ------------------------------------ |
| Kvalitativni | Imenski | = | poštanski kodovi, boja očiju, pol |
| Kvalitativni | Redni | =, <, > | redni brojevi zgrada u ulici |
| Kvantitativni | Intervalni | =, <, >, +, - | datumi u kalendaru |
| Kvantitativni | Razmerni | =, <, >, +, -, *, / | količina novca, godine, masa, dužina |

Atributi se takođe mogu deliti prema broju vrednosti koje sadrže - na __diskretne__ (konačan ili prebrojivo beskonačan) i __kontinualne__ (neprebrojivo beskonačan). Binarni su podvrsta diskretnih takva da mogu imati samo dve vrednosti.

__Asimetrični podaci__ su oni kod kojih su bitne samo ne-nula vrednosti.

**Kategorički atributi** su atributi koji dodeljuju slogu kategoriju iz konačnog skupa mogućih kategorija. Mogu biti imenski ili redni.

#### Tipovi skupova podataka

- slogovi
- matrica podataka - skup numeričkih atributa
- podaci u dokumentima - atributi istog tipa, asimetrični
- transakcioni podaci - transakcija (objekat) je skup stavki
- grafovi
- podaci sa poretkom
- prostorni podaci
- vremenski (zavisni) podaci
- redosledni podaci

#### Ostale napomene

Autokorelacija ili serijska korelacija je korelacija nekog podatka sa samim sobom u funkciji razmaka između merenja. Npr. ako pitamo da li je veća prostorna autokorelacija kod količine padavina ili temperature, ono što pitamo je ako na određenom prostoru izmerimo količinu padavina i izmerimo temperaturu, šta će od ta dva biti konzistentnije tj. u većoj korelaciji sa samim sobom kroz vreme. U ovom slučaju, to će biti temperatura, jer padavine uglavnom mnogo više variraju (mada to zavisi od klime regiona koji ispitujemo).

#### Šum i elementi van granice

Šum predstavlja modifikaciju originalnih vrednosti. Često se dešava kao proizvod greške u merenju, spoljnih uticaja, itd.

Elementi van granice su elementi s karakteristikama koje se značajno razlikuju od najvećeg broja objekata u skupu podataka. Oni nisu pogrešni i mogu biti vrlo značajni za istraživanje, samo u većoj meri odudaraju od proseka/očekivanja.

#### CRISP-DM

Cross Industry Standard Process for Data Mining

- Razumevanje posla - utvrđivanje ciljeva
- Razumevanje podataka - prikupljanje podataka, upoznavanje izvora i njihovih karakteristika, opisivanje podataka, provera kvaliteta podataka
- Priprema podataka - odabir, čišćenje, formatiranje, konstruisanje
- Modeliranje - odabir tehnika, izrada, i procena modela, tj. korišćenje metoda za analizu za dobijanje informacija iz podataka
- Evaluacija - procena rezultata, pregled procesa prikupljanja podataka, određivanje narednih koraka
- Razvoj - integracija novih znanja u svakodnevne poslovne procese kako bi se rešio originalni poslovni problem

#### Statistika

**Srednja vrednost** je prosek vrednosti nekog atributa.

**Varijansa** i **standardna devijacija** služe da se izmeri očekivana udaljenost nasumičnog elementa od srednje vrednosti nekog atributa iz skupa podataka.

**Standardna greška sredine** je mera koliko srednja vrednost može da varira od uzorka do uzorka iz iste distribucije.

Za uzorak od $n$ vrednosti $x_1,\ x_2,\ \dots,\ x_n$:

| naziv | engleski | oznaka | formula |
| ------------------------- | -------------------------------- | --------------------- | ---------------------------------------- |
| srednja vrednost | mean | $\mu$ | $\frac{1}{n}\sum_i x_i$ |
| varijansa | variance | $\sigma^2$ | $\frac{1}{n-1}\sum_i (x_i-\mu)^2$ |
| standardna devijacija | standard deviation (STD) | $\sigma$ | $\sqrt{\frac{1}{n-1}\sum_i (x_i-\mu)^2}$ |
| kovarijansa | covariance | $cov(x,y)$ | $\frac{1}{n-1}\sum_i(x_i-\mu_x)(y_i-\mu_y)$ |
| korelacija | correlation | $corr(x,y)$ | $\frac{cov(x,y)}{\sigma(x)\cdot\sigma(y)}$ |
| standardna greška sredine | standard error of the mean (SEM) | $\sigma_\overline{x}$ | $\frac{\sigma}{\sqrt{n}}$ |

__Iskrivljenost (eng. skewness)__ je mera asimetrije distribucije. Normalna distribucija je simetrična i ima vrednost asimetrije 0. Distribucija sa značajno pozitivnom asimetrijom ima dugi desni rep, a sa značajno negativnom dugi levi.

__Spljoštenost (eng. kurtosis)__ je mera postojanja ekstremne vrednosti. Za normalnu distribuciju, vrednost spljoštenosti je 0. Pozitivna vrednost spljoštenosti ukazuje na to da podaci prikazuju ekstremnije ekstreme od normalne distribucije, a negativna obrnuto.

__Mod (eng. mode)__ je vrednost koja se najčešće pojavljuje u skupu podataka.

__Medijana (eng. medijana)__ je vrednost koja deli slučajeve na pola nakon sortiranja. Ako je broj slučajeva paran, medijana je prosek dva srednja slučaja.

__Postotna vrednost ili percentil__ za neki izabrani broj $p$ definiše se poštujući uslov da je barem $p$% vrednosti u skupu manje ili jednako toj vrednosti, dok je barem $(100-p)$% vrednosti veće ili jednako od te vrednosti. Tri percentila (25, 50, i 75.) dele podatke na četiri jendaka dela, kao što ih medijana deli na dva. Ovi percentili se zovu prvi, drugi, i treći kvartil, i označavaju sa $Q_1$, $Q_2$, $Q_3$.

__Interkvartilni raspon__ je razlika $Q_3-Q_1$.

#### Obrada nedostajućih vrednosti, elemenata van granica, i ekstremnih vrednosti

- null - označeno `$null$`
- prazne niske i beline - normalne vrednosti
- blanko - korisnički definisane nedostajuće vrednosti

Metodi obrade nedostajućih vrednosti:

- fixed - zamena zadatom
- random - zamena nasumičnom
- expression - zamena rezultatom izraza
- algorithm - zamena rezultatom algoritma C&RT

Obrada elemenata van granica i ekstremnih vrednosti:

- coerce - zamena elementa najbližom vrednošću koja se ne smatra elementom van granica
- discard - odbacuju se slogovi sa elementima van granica u tom atributu
- nullify - zamenjuju se nedostajućim vrednostima
- coerrce outliers / discard extremes
- coerce outliers / nullify extremes

## 02

#### Mere bliskosti

- Sličnost - numerička vrednost sličnosti, što su dva objekta sličnija sličnost je veća, često u intervalu $[0, 1]$
- Različitost/rastojanje - isto, samo obrnuto
- Blizina označava ili sličnost ili različitost


__Rastojanje Minkovskog__:
$$
dist = (\sum_{k=1}^n|p_k-q_k|^r)^{1/r}
$$
gde je:

- $r$ parametar
- $n$ broj dimenzija (atributa)
- $p_k$ i $q_k$ su vrednosti atributa $k$-tog objekta $p$ i $q$

Primeri rastojanja Minskovskog:

- $r = 1$ je Menhetn rastojanje
- $r = 2$ je Euklidovo rastojanje
- $r\rightarrow\infty$ je "supremum" rastojanje, predstavlja maksimalne razlike između odgovarajućih komponenti vektora

__Standardizacija__ je svođenje na normalnu raspodelu. Formula: $\frac{(x_i-\mu)}{\sigma}$.

__Normalizacija__ je skaliranje ili neko drugo mapiranje na određeni interval, a određuje se po formuli: $\frac{(x_i-x_{min})}{(x_{max}-x_{min})}$.

Ako su $p$ i $q$ binarni vektori:
$$
M_{01}\ je\ broj\ atributa\ koji\ su\ 0\ u\ p\ i\ 1\ u\ q\\
M_{10}\ je\ broj\ atributa\ koji\ su\ 1\ u\ p\ i\ 0\ u\ q \\
M_{00}\ je\ broj\ atributa\ koji\ su\ 0\ u\ p\ i\ 0\ u\ q \\
M_{11}\ je\ broj\ atributa\ koji\ su\ 1\ u\ p\ i\ 1\ u\ q \\
$$
__Jednako uparivanje koeficijenata (eng. Simple Matching Coefficient)__:
$$
SMC = \frac{broj\ uparenih}{broj\ atributa}=\frac{M_{11}+M_{00}}{M_{01}+M_{10}+M_{00}+M_{11}}
$$
__Žakardovi koeficijenti__:

- koristi se na asimetričnim binarnim atributima

$$
J = \frac{broj\ parova\ 11}{broj\ ne\ oba-su-nula\ vrednosti\ atributa}=\frac{M_{11}}{M_{01}+M_{10}+M_{11}}
$$

__Kosinusna sličnost__:
$$
cos(p,q)=\frac{p\cdot q}{||p||\ ||q||}
$$
gde su:
- $p$ i $q$ vektori
- tačka je skalarni proizvod vektora
- $||d||=\sqrt{\sum{x_i^2}}$ je dužina vektora $d$
- koristi se za asimetrične podatke
- najčešća mera sličnosti dokumenata

__Korelacija__:
$$
r=\frac{kovarijansa(x,y)}{standardna\ devijacija(x)\cdot standardna\ devijacija(y)}
$$
Korelacija dva objekta koji imaju binarne ili neprekidne atribute je mera linearnog odnosa između njihovih atributa.

Kovarijansa je mera zajedničke varijabilnosti dve nasumične promenljive.


#### Priprema podataka

__Diskretizacija__ je transformacija neprekidnog atributa u kategorički atribut.

__Binarizacija__ je transformacija atributa u jedan ili više binarnih atributa. Npr. možemo kodirati brojeve iz intervala $[0,100]$ kao $0$ ili $1$ ako su veći ili manji ili jednaki od $50$ (transformacija u jedan atribut). Takođe ih možemo kodirati u 7 kolona tako da zapišemo njihovu binarnu reprezentaciju (transformacija u više atributa).

## 03

Mere za ocenu modela kod klasifikacije:
- __preciznost__ (eng. accuracy) $=\frac{broj\ slogova\ čija\ je\ klasa\ dobro\ predviđena\ modelom}{ukupan\ broj\ slogova}$
- __stopa greške__ (error rate) $=\frac{broj\ slogova\ čija\ je\ klasa\ loše\ predviđena\ modelom}{ukupan\ broj\ slogova}$

__Model klasifikacije__ se predstavlja kao drvo odlučivanja koje ima:

- __unutrašnje čvorove__ - Svaki unutrašnji čvor sadrži uslov nad test atributom koji služi za podelu slogova koje imaju različite karakteristike. Grane koje izlaze iz unutrašnjeg čvora odgovaraju mogućim vrednostima test atributa.
- __listove__ - Svakom listu je dodeljena jedna klasa.

__Klasifikacija sloga__: Počevši od korena drveta odlučivanja, primenjuje se test uslov nad slogom i prati se grana koja odgovara dobijenom rezultatu. Ukoliko se pri spuštanju niz drvo odlučivanja naiđe na unutrašnji čvor, postupak se ponavlja (test uslov se primenjuje na slog i prati se grana koja odgovara rezultatu testa). Ako se naiđe na list, slogu se dodeljuje klasa koja je pridružena tom listu.

#### Opšti algoritam

Neka je ___Dt___ skup slogova za trening koji se nalaze u čvoru t, a ___y = y1, ..., yc___ su oznake klasa.

Ako ___Dt___ sadrži samo slogove koji pripadaju jednoj klasi ___yt___ , tada je ___t___ list označen sa ___yt___ i tu se završava analiza te grane.

Ako ___Dt___ sadrži slogove koji se nalaze u više od jedne klase (tj. treba dalje da se deli), tada se koristi test atribut radi podele podataka u manje podskupove na osnovu nekog uslova. Na dobijene podskupove se zatim rekurzivno primenjuje kompletna procedura.

#### Mere nečistoće

__p(j|t)__ je relativna frekvencija klase __j__ u čvoru __t__.

__Ginijev indeks__
$$
Gini(t)=1-\sum_j[p(j|t)]^2
$$
__Entropija__
$$
Entropy(t)=-\sum_jp(j|t)\cdot log_2p(j|t)
$$
__Greška klasifikacije__
$$
Error(t)=1-max_jp(j|t)
$$
__Dobit__
$$
\Delta=I(parent)-\sum_{j=1}^k\frac{N(v_j)}{N}\cdot I(v_j)
$$

gde je:
- $I(x)$ - mera nečistoće u čvoru $x$
- $N(x)$ - broj slogova u čvoru $x$
- $N$ - broj slogova iz roditelja
- suma iterira kroz svu decu

#### C5.0

- samo za kategoričke ciljne vrednosti
- generiše stablo odlučivanja ili pravila pridruživanja
- deli uzorak na osnovu atributa sa najvećom informacionom dobiti (mera nečistoće: entropija), svaki poduzorak ponovo deli dok god može
- za kategoričke atribute se podrazumeva podela jedna vrednost - jedna grana, ali vrednosti mogu i da se grupišu
- na kraju se vrši potkresivanje u jednom prolazu primenom binarne granice pouzdanosti
- Opcije:
- korišćenje podeljenog skupa (trening i test skup)
- grupisanje kategoričkih podataka
- boosting - pravljenje više modela u nizu radi povećanja preciznosti. Prvi model se pravi na uobičajen način, a svaki sledeći se fokusira na instance koje su pogrešno klasifikovane prethodnim modelom. Za klasifikaciju instance se primenjuju svi modeli i koristi se sistem glasanja.
- unakrsna-validacija - pravljenje modela nad podskupovima radi procene preciznosti modela napravljenim nad celim skupom
- opcija za naklonost ka preciznosti ili uopštenosti modela
- očekivan procenat instanci sa greškom u trening skupu
- strogost pri potkresivanju - povećanjem vrednosti dobija se manje stablo
- minimalan broj instanci koji mora da bude u dete-čvoru nakon podele da bi se izvršila podela
- winnow atributes - izračunavanje važnosti atributa pre pravljenja modela
- matrica cene pogrešne klasifikacije

## 04

#### Mere za ocenu klasifikacionog modela

$$
accuracy=\frac{Broj\ slogova\ čija\ klasa\ je\ dobro\ predviđena\ modelom}{Ukupan\ broj\ slogova}\\
error\ rate=\frac{Broj\ slogova\ čija\ klasa\ nije\ dobro\ predviđena\ modelom}{Ukupan\ broj\ slogova}
$$

Problem skupa podataka sa neuravnoteženim klasama nastaje kad jednoj klasi pripada znatno više podataka nego drugoj, pa model tu klasu favorizuje jer tako ima veću verovatnoću pogotka, iako to znatno smanjuje accuracy za druge slučajeve. Pri binarnoj klasifikaciji, retka klasa se označava kao pozitivna, a većinska kao negativna.

__Matrica konfuzije__ je jedna od najbitnijih mera za ocenu klasifikacionog modela:

| | | Dodeljena | klasa |
| ------- | ---- | ------------------- | ------------------- |
| | | + | - |
| Stvarna | + | TRUE POSITIVE (TP) | FALSE NEGATIVE (FN) |
| klasa | - | FALSE POSITIVE (FP) | TRUE NEGATIVE (TN) |

Može se izračunati TP, TN, FP, FN rate, tako što se podeli odgovarajuće predviđanje sa ukupnim brojem stvarnih slučajeva. Npr:
$$
TPR = \frac{TP}{TP+FN}
$$
Još neke mere:

| pojam | engleski | oznaka | formula | interpretacija |
| -------- | -------- | -------- | -------- | -------- |
| preciznost | precision | $p$ | $\frac{TP}{TP+FP}$ | za sve klase: $\frac{broj\ pogođenih}{ukupan\ broј\ stavki}$|
| odziv | recall | $r$ | $\frac{TP}{TP+FN}$ | $\frac{broj\ pogođenih}{broj\ klasifikovanih\ kao\ razmatrana\ klasa}$ |

Bitna je još i veza:
$$
F_1=\frac{2rp}{r+p}=\frac{2}{\frac{1}{r}+\frac{1}{p}}
$$

$F_1$ je harmonijska sredina preciznosti i odziva i bliža je manjoj od tih vrednosti.

__ROC kriva (receiver operating characteristic curve)__

- grafički prikaz kompromisa između TPR i FPR
- x osa - FPR ili 1-specifičnost
- y osa - TPR ili osetljivost


Interpretacija određenih tačaka:

- (TPR=0 i FPR=0) - model svakoj instanci dodeljuje negativnu klasu
- (TPR=1 i FPR=1) - model svakoj instanci dodeljuje pozitivnu klasu
- (TPR=1 i FPR=0) - idealan model

AUC (eng. area under the ROC curve) - površina ispod ROC krive.

__Postupak rešavanja zadatka:__


Za modele __$M_1$__ i __$M_2$__ pravimo tablicu za TPR i FPR u kojoj sortiramo date verovatnoće od manje ka većoj. Pišemo ispod verovatnoća odgovarajuće klase (+ ili -). Nakon toga popunjavamo tabelu tako što poredimo šta bi bilo kad bi klasifikovao sve kao +, šta kad bi klasifikovao samo prvi kao - a sve ostalo kao +, šta kad bi klasifikovao prva dva kao - itd. Ograničenje je da uvek moraju da idu svi minusi, pa svi plusevi, a ne izmešano.

Za $M_1$ dobijamo:


Za $M_2$ dobijamo:


I onda samo nacrtamo ROC krive na osnovu TRP i FRP vrednosti iz tabela. Ako se ne vidi očigledno koji model je bolji, možemo da izračunamo površine (AUC) i uporedimo ih.

## 05

#### Unakrsna validacija

#### KNN

U algoritmu $K$ najbližih suseda klasifikacija instance je zasnovana na sličnosti sa drugim instancama. Test instanca se klasifikuje tako što se u trening skupu pronalazi $k$ najbližih instanci (suseda) i test instanci se dodeljuje klasa koja je najzastupljenija među $k$ najbližih suseda.

Osnovni parametri algoritma KNN su:
• $k$ - broj suseda
• $dist$ - funkcija za računanje rastojanja izmedu instanci

U najjednostavnijem obliku algoritma KNN, svaki sused ima istu težinu, te klasa koja je najzastupljenija medu susedima test instance se dodeljuje test instanci. U nekim okolnostima, bolje je susedima dodeliti težine tako da bliži susedi imaju veći uticaj pri određivanju klase test instance. Tada su težine suseda proporcionalne vrednosti $\frac{1}{d}$, gde je $d$ rastojanje suseda od test instance.

Za računanje rastojanja izmedu instanci najčešće se koriste Euklidsko i Menhetn rastojanje, zbog čega je u okviru preprocesiranja podataka potrebno izvršiti:
• pretvaranje kategoričkih atributa u numeričke
• transformisati numeričke atribute tako da imaju isti ili sličan opseg vrednosti

## 06

#### Naivni Bajesovski klasifikatori

Bajesova teorema: $P(C|A)=\frac{P(A|C)\cdot P(C)}{P(A)}$

Bajesovski klasifikatori koriste Bajesovu teoremu za predvidanje klase test instance.

Neka je dato:

* $A=(A_1, A_2, \dots, A_n)$ je test instanca
* atributi $A_1, A_2, \dots, A_n$ su svi međusobno nezavisni
* $C$ je potencijalna klasa u koju \elimo da procenimo da li treba da klasifikujemo datu test instancu

$\hat{C}=arg\ max_C\ \prod\limits_{i=1}^nP(A_i|C)\cdot P(C)$

Klasa u koju klasifikujemo je ona koja daje maksimalnu vrednost ovog proizvoda.

#### tf-idf

* $tf$ - frekvencija reči (term-frequency)
$tf(t,d)=0.5+0.5\cdot\frac{frekvencija\ terma\ t\ u\ dokumentu\ d}{najčešći\ term\ u\ dokumentu\ d}$

* $idf$ - inverzna frekvencija dokumenta (inverse document frequency)
$idf(t)=\log{\frac{ukupan\ broj\ dokumenata}{broj\ dokumenata\ koji\ sadrže\ term\ t}+1}$

#### Naivni Bajes za klasifikaciju teksta

* $\Theta_C=(\Theta_{C1}, \Theta_{C2}, \dots, \Theta_{Cn})$ - vektor parametara, gde je $\Theta_{Ci}$ verovatnoća da se term $i$ pojavi u instanci koja pripada klasi $C$
* $n$ - ukupan broj različitih reči u svim klasama
* $N_{Ci}$ - broj pojavljivanja terma (reči) $i$ u dokumentima klase C
* $N_{C}$ - ukupan broj pojavljivanja svih reči u klasi C
* $\alpha$ - korisnički zadat parametar

Formula za verovatnoću $\Theta_{Ci}$ je onda: $\Theta_{Ci}={\frac{N_{Ci}+\alpha}{N_C+\alpha\cdot n}}$

Klasifikacija test dokumenta $d$ sa termima $t_1, t_2, \dots, t_k$ se vrši računanjem:

$\hat{C}=arg\ max_C\ P(C)\prod\limits_{i=1}^k \Theta_{Ci}$

Radi lakšeg izračunavanja može se koristiti:

$\hat{C}=arg\ max_C\ [\log{P(C) + \sum\limits_{i=1}^k\log{P(t_i|C)}}]$

## 08

#### K-means (K-sredina)

Klasteruje tako što pridružuje klastere najbližim centroidama, a onda ažurira centroide u svakoj iteraciji. Početne centroide su zadati parametar ili se biraju nasumično. Zadat je parametar K tj. ciljni broj klastera. Rastojanja se mogu računati raznim merama rastojanja, a centroide se uglavnom ažuriraju kao prosek vrednosti iz klastera.

Postupak rađenja zadatka:
1. izračuna se distanca svih od svake centroide
2. svaki element koji nije centroida se pridruži klasteru najbliže centroide
3. centroide se ažuriraju na prosek elemenata iz klastera kome pripadaju
4. postupak se ponavlja sve dok se ne desi iteracija u kojoj korak 3. nije promenio ni jednu centroidu

#### Kvalitet klasterovanja

__Suma kvadrata greške__ (eng. Sum of Squared Error) je suma kvadrata rastojanja svih elemenata svakog klastera od odgovarajuće centroide: $SEE=\sum\limits_{i=1}^K \sum\limits_{x\in C_i} dist(c_i,x)^2$.

__Silueta koeficijent__ (eng. Silhouette Coefficient) je mera koliko su instance grupisane sa instancama sličnim njima samima.

$$
s=\frac{b-a}{max(a,b)}
$$

* a - prosečno rastojanje između instance i ostalih instanci u istom klasteru
* b - prosečno rastojanje između instance i svih instanci iz najbližeg susednog klastera

Interpretacija:
* blizu -1: neispravno, raspršeno grupisanje
* blizu +1: gusto grupisanje

## 09

#### Hijerarhijsko klasterovanje

Hijerarhijsko klasterovanje se zasniva na slojevitoj iterativnoj podeli ili spajanju podataka u klastere na osnovu neke mere sličnosti ili različitosti. U odnosu na ta dva pristupa deli se na:

* Sakupljajuće: Inicijalno je svaka instanca zaseban klaster. U svakom koraku se spajaju dva najbliža/najsličnija klastera sve dok sve instance ne pripadaju istom (jednom) klasteru. Na kraju se bira podela na klastere koja je bila međukorak pri dolaženju do jedinstvenog klastera.
* Razdvajajuće: Inicijalno sve instance pripadaju jednom klasteru. U svakom koraku se jedan klaster deli na dva dela sve dok ne ostanu klasteri sa po jednom instancom. Treba definisati odabir klastera koji će se deliti i postupak deljenja. Na kraju se kao podela na klastere bira međukorak pri dolaženju do pojedinačnih instanci.

Pri primeni hijerarhijskog sakupljajućeg klasterovanja, potrebno je izabrati meru za računanje bliskosti dve instance (npr. euklidsko rastojanje, kosinusna sličnost ...), kao i kako se računa bliskost dva klastera. Za odredivanje bliskosti klastera mogu se koristiti veze:
* najbolja (min, single) veza - bliskost dva klastera je jednaka bliskosti najbližeg para instanci iz različitih klastera
* najgora (max, complete) veza - bliskost dva klastera je jednaka bliskosti najudaljenijeg para instanci iz različitih klastera
* prosečna (avg) veza - bliskost dva klastera je jednaka prosečnoj bliskosti parova instanci iz različitih klastera.

| veza | prednosti | mane |
| -------- | -------- | -------- |
| single | pogodna za neeliptičke klastere | osetljiva na šum i elemente van granica |
| complete | otporna na šum i elemente van granica | sklonost ka globularnim klasterima i razbijanju velikih klastera |
| average | otporna na šum i elemente van granica | sklonost ka globularnim klasterima |

Na sledećoj slici su nažvrljane stavke iz tabele.
Za single vezu, zbog blizine dve vrednosti na rubovima klastera celi klasteri se registruju kao bliski, iako oni to očito nisu.
Za complete vezu, prečnik velikog klastera (ljubičasta linija) je velik, što ograničava rast klastera jer je najveća razdaljina progresivno duža. Mali klasteri (uokvireni zeleno) su skloniji da se spoje globularno s jednim lokalnim nego npr. eliptično po dužini.


#### DBScan

## 11 - Pravila pridruživanja

#### Apriori