Cvičení 12: Vlastnosti klastrování

Z přednášky

Vlastnosti dobrého klastrování

Funkce vzdálenosti $d: S \times S \rightarrow \mathbb{R}$ je funkce t.ž.

• pro $i,j\in S$ s.t. $i\neq j$ máme $d(i,j) \geq 0$
• pro $i,j\in S$ platí $i = j$ právě tehdy když $d(i,j) = 0$
• (ne nutně - tj. vzdálenost nemusí být metrika) $d(i,k) \leq d(i,j) + d(i,j)$

Funkce klastrování $f$ dělí $S$ do klastrů. Definujeme $\mathcal{P}$ množinu všech možných dělení $\Gamma$ množiny $S$ do klastrů. Klastrovací funkci $f$ uvažujeme jako funkci vzdálenosti $d$ která vrací nějaké dělení $\Gamma$.

Požadavky na klastrování

• nezávislost na škálování (scale-invariance)

  Pro každou vzdálenost $d$ a každé $\alpha > 0$, máme $f(d) = f(\alpha d)$. kde $\alpha d$ znamená, že každá $i,j$ jsou ve vzdálenosti $\alpha d(i,j)$.

• bohatost (richness)

  $\text{Range}(f)$ je rovné všem možným dělením $S$, neboli pro každé dělení dokážeme najít funkci vzdálenosti takovou, že $f(d) = \Gamma$.

• konzistence

  Nechť $d$ a $d'$ jsou dvě funkce vzdálenosti. Pokud $f(d) = \Gamma$, a $d'$ je $\Gamma$-transformace $d$, pak $f(d') = \Gamma$, kde $d'$ je $\Gamma$-transformace $d$ pokud

  • $\forall i, j \in S$ ze stejného klastru náležejícího do $\Gamma$ máme $d'(i, j) \leq d(i,j)$
  • $\forall i, j \in S$ z různých klastrů náležejících do $\Gamma$ máme $d'(i, j) \geq d(i,j)$
  • když zkrátíme vzdálenosti uvnitř klastrů zvětšíme vzdálenosti mezi klastry, dostaneme stejný výsledek, tj. $f(d') = f(d)$.

Single-linkage klastrování

1. Inicializace: každý bod má vlastní klastr
2. Krok: spoj dva nejbližší klastry
3. Konec: podle předem definovaného kritéria

Možná kritéria k zastavení:

• podmínka $k$-klastrů: zastavíme když máme právě $k$ klastrů.

  Poznámka: Nedokážeme získat každé dělení - chybí bohatost (richness)

• podmínka vzdálenosti $r$: přidáváme hrany do vzdálenosti $r$.

  Poznámka: Není nezávislé na škálování.

• podmínka $\alpha$-škálování: Přidáme hrany váhy $\leq \alpha \max_{i,j} d(i,j)$

  Poznámka: Dá se ukázat, že není konzistentní.

Věta: (Kleinberg 2002)

(a) Pro každé $k \geq 1$, a každé $n \geq k$, single-linkage klastrování se zastavovací podmínkou $k$-klastrů splňuje nezávislost na škálování a konzistenci.

(b) Pro každé kladné $\alpha < 1$, a každé $n \geq 3$, single-linkage klastrování se zastavovací podmínkou $\alpha$-škálování splňuje nezávislost na škálování a bohatost.

(c) Pro každé $r > 0$, a každé $n \geq 2$, single-linkage klastrování se zastavovací podmínkou vzdálenosti $r$ splňuje bohatost a konzistenci.

Věta: (Kleinberg 2002) Pro každé $n \geq 2$ platí, že neexistuje žádná klastrovací funkce $f$ splňující nezávislost na škálování, bohatost a konzistenci.

Plyne z věty níže. Dělení $\Gamma'$ je zjemnění dělení $\Gamma$ pokud pro každou množinu $C'\in \Gamma'$, exituje $C \in \Gamma$ t.ž. $C'\subseteq C$.

Definujeme částečné uspořádání, kde $\Gamma' \preceq \Gamma$ pokud $\Gamma'$ je zjemnění $\Gamma$. Uvažujme antiřetězec jako množinu prvků neporovnatelných prvků.

Věta: (Kleinberg 2002) Pokud klastrovací funkce $f$ splňuje nezávislost na škálování a konzistenci, pak >$\text{Range}(f)$ je antiřetězec.

Poznámka: Množina všech dělení netvoří antiřetězec, tj. $f$ nemůže splnit bohatost.

Věta: (Kleinberg 2002) Pro každý antiřetězec různých dělení $\mathcal{A}$ existuje klastrovací funkce $f$ splňující nezávislost na škálování a konzistenci, pro kterou $\text{Range}(f) = \mathcal{A}$.

Úlohy

Úloha 1: (z 10. cvičení)

Nechť $P$ je graf isomorfní cestě na $n$ vrcholech. Spočítej modularitu pro rozdělení vrcholů $P$ na dvě části, které odpovídá odebrání jedné hrany cesty, tj. dostaneme dvě cesty obsahující po řadě $r$ a $n-r$ vrcholů.

Úloha 2:

Isometrie $i$ pro dvě funkce vzdálenosti $d$ a $d'$ na $S$ množině bodů je permutace $i: S \rightarrow S$ taková, že $d'(i(x), i(y)) = d(x,y)$ pro všechny body $x,y \in S$.

Klastrovací funkce $f$ je nezávislá na isometrii pokud splňuje následující: pro každé dvě funkce vzdálenosti $d$ a $d'$ a isometrii $i$ mezi nimi, body $i(x)$ a $i(y)$ leží ve stejném klastru $f(d')$ právě tehdy, když $x$ a $y$ leží ve stejném klastru $f(d)$. Jinými slovy, klastrovací funkce je závisí pouze na vzdálenosti, nikoli na označení bodů.

Pozorování: Zastavovací podmínka $k$-klastrů není nezávislá na isometrii.

Klastrování je triviální, pokud platí jedna z následujících podmínek:

• celá množina $S$ tvoří jeden velký klastr (tj. existuje jediný klastr velikosti $|S|$)
• každý bod $S$ leží ve vlastním klastru (tj. každý klastr obsahuje právě jeden bod)

Dokažte následující variantu Kleinbergovy věty:

Věta: Neexistuje žádná netriviální klastrovací funkce nezávislá na isometrii, která by byla zároveň konzistentní a nezávislá na škálování.

Nápověda: Zamyslete se, jak může vypadat výstup libovolné klastrovací funkce nezávislé na isometrii pro funkci vzdálenosti $d_1$, kde $d_1(x,y) = 1\ \forall x,y \in S, x \neq y$. Pokuste se výsledek zobecnit na libovolnou funkci vzdálenosti s použitím předpokladů o vlastnostech klastrovací funkce.