6. Lineární projekce dat do prostoru o méně dimenzích: metoda hlavních komponent (PCA), lineární diskriminační analýza (LDA). Nelineární metody redukce dimensionality (Sammonova projekce). (NI-PDD)

---

Projekce dat

• Snížení dimenze při zachování maxima informace (vzájemných vztahů bodů)
• Vyřazení redundantní informace, zrychlení výpočtu
• Nová podoba dat může být těžko interpretovatelná
• Každá metoda se snaží minimalizovat nějaké kritérium

Lineární transformace

Obecný vzorec pro lineární transformaci dat:

$$Y_i = U^T X_i$$

kde:

• $Y_i$ je výsledný vektor v redukovaném prostoru (rozměr $k×1$)
• $X_i$ je původní vektor příznaků (rozměr $n×1$)
• $U$ je transformační matice (rozměr $k×n$)
  • $k$ je počet dimenzí v novém prostoru
  • $n$ je počet dimenzí v původním prostoru

Důležité vlastnosti:

• Transformace je lineární kombinací původních příznaků
• Každý řádek matice $U$ představuje jeden nový příznak
• PCA i LDA jsou speciální případy této obecné transformace, liší se způsobem výpočtu matice $U$

Porovnání

Aspekt	PCA	LDA	Sammonova projekce
Projekce	Lineární	Lineární	Nelineární
Cíl	Maximalizace zachované variance dat	Maximalizace separace mezi třídami	Zachování vzdáleností mezi body
Optimalizace	Rozptyl dat podél nových os	Poměr mezitřídního a vnitrotřídního rozptylu	Sammonův stress (rozdíl vzdáleností)

Metoda hlavních komponent (PCA)

• Účel: Redukce dimenzionality dat při zachování co největší možné variability. Používá se k odstranění redundance a nalezení nových os (hlavních komponent), které vysvětlují co nejvíce rozptylu v datech.
• Vlastnosti:
  • Transformuje data do nového souřadného systému.
  • Hlavní komponenty jsou lineární kombinace původních příznaků.
  • První komponenta má největší rozptyl, každá další má menší rozptyl a je nekorelovaná s předchozími.
  • Nezohledňuje informace o třídách (není vhodná pro klasifikaci).
  • Maximální počet vlastnic vektoru je $N$ kde $N$ je počet původních dimenzi prostoru řešení
• Použití:
  • Komprese dat (např. obrazů).
  • Předzpracování dat pro strojové učení.
  • Vizualizace dat ve 2D nebo 3D prostoru.

Algoritmus

1. Standardizace dat: Pro každý příznak odečíst průměr a vydělit ho směrodatnou odchylkou, aby měly všechny příznaky stejnou váhu
2. Výpočet kovarianční matice: Z centrovaných dat vytvořit kovarianční matici, která vyjadřuje závislosti mezi příznaky
3. Vlastní čísla a vektory: Najít vlastní čísla a vlastní vektory kovarianční matice. Vlastní vektory určují nové osy (hlavní komponenty), vlastní čísla množství zachycené variance
4. Redukce dimenzí: Seřadit komponenty podle velikosti vlastních čísel a vybrat jen několik prvních. Projekcí vstupních dat na vybrané komponenty dojde ke snížení dimenzionality s minimální ztrátou informace

Lineární diskriminační analýza (LDA)

• Účel: Redukce dimenzionality při maximalizaci separace mezi třídami. Hledá projekci dat, která nejlépe odděluje jednotlivé třídy.

• Cíl optimalizace:

  • Maximalizovat: Vzdálenost mezi středy tříd (mezitřídní rozptyl)
  • Minimalizovat: Rozptyl bodů uvnitř každé třídy (vnitrotřídní rozptyl)
  • Výsledkem je maximalizace poměru mezitřídního a vnitrotřídního rozptylu

• Vlastnosti:

  • Na rozdíl od PCA využívá informace o příslušnosti dat ke třídám
  • Předpokládá normální rozdělení příznaků
  • Předpokládá stejné kovarianční matice pro všechny třídy
  • Vytváří lineární hranice mezi třídami
  • Maximální počet vlastnic vektoru je $N-1$ kde $N$ je počet původních dimenzi prostoru řešení
• Použití:
  • Klasifikace dat (rozpoznávání obličejů, textová analýza)
  • Redukce dimenzionality se zachováním diskriminačních informací
  • Vizualizace separace tříd

Algoritmus

1. Výpočet průměrů:
   • Spočítat průměrný vektor pro každou třídu
   • Spočítat celkový průměr všech dat
2. Výpočet rozptylových matic:
   • Vnitrotřídní matice: Měří, jak moc jsou body rozptýleny uvnitř každé třídy (snažíme se minimalizovat)
   • Mezitřídní matice: Měří, jak daleko jsou od sebe středy jednotlivých tříd (snažíme se maximalizovat)
3. Řešení eigen-problému:
   • Výpočet vlastních vektorů matice
   • Tyto vektory určují směry, ve kterých je poměr mezitřídního a vnitrotřídního rozptylu maximální
4. Projekce dat:
   • Výběr vlastních vektorů s největšími vlastními čísly
   • Projekce dat do nového prostoru s menší dimenzí
   • V novém prostoru jsou třídy co nejlépe odděleny
5. Výsledek:
   • Získáme transformační matici pro redukci dimenzionality
   • Můžeme použít jako klasifikátor pro nová data

Sammonova projekce

• Účel: Nelineární redukce dimenzionality, která zachovává vzdálenosti mezi body z původního prostoru co nejvěrněji v prostoru s nižším počtem dimenzí. Často se používá pro vizualizaci dat.
• Sammonův stress: Funkce chyby, která měří rozdíl mezi vzdálenostmi ve vysokodimenzionálním a nízkodimenzionálním prostoru, často vážený podle původních vzdáleností
• Vlastnosti:
  • Zachovává strukturu dat tím, že minimalizuje Sammonův stress.
  • Je nelineární metodou, což znamená, že neprovádí pouhou lineární transformaci os.
  • Výpočetně náročná, protože vyžaduje iterativní optimalizační metody.
• Použití:
  • Vizualizace dat ve 2D nebo 3D prostoru (např. pro explorativní analýzu).
  • Analýza podobností mezi objekty na základě jejich vzdáleností.

Algoritmus

1. Výpočet vzdáleností: Z originálního datového prostoru spočítat všechny párové Euklidovy (nebo jiné) vzdálenosti mezi body
2. Inicializace v nižším rozměru: Body v cílovém (typicky 2D) prostoru se buď náhodně rozmístí, nebo se použije např. PCA jako výchozí umístění
3. Iterativní minimalizace stressu: Typicky gradientní nebo jinou optimalizační metodou posouvat body v nízkodimenzionálním prostoru, dokud se Sammonův stress dále nezmenšuje
4. Výsledná mapa: Po skončení iterací získat rozmístění bodů, které co nejlépe zachovává strukturu vzdáleností z původního prostoru. Hodí se pro vizualizaci a explorativní analýzu.