Free Press

Úloha zahrnující strojové učení nemusí být lineární, ale má řadu známých kroků:

• Definice problému.
• Příprava dat.
• Učení základního modelu.
• Zlepšení podkladového modelu pomocí kvantitativních a kvalitativních hodnocení.
• Prezentace modelu.

Jedním z dobrých způsobů, jak se vyrovnat s novým problémem, je pracovat s identifikací a definicí problému co nejlépe a naučit se model, který zachycuje smysluplné informace z dat. Přestože problémy v oblasti rozpoznávání vzorů a strojového učení mohou být různého typu, lze je obecně rozdělit do tří kategorií:

• Učení pod dohledem:
  Systému jsou předloženy příklady vstupů a jejich požadované výstupy, které jsou dány „učitelem“, a cílem je naučit se obecné pravidlo, které mapuje vstupy na výstupy.
• Učení bez dohledu:
  Učícímu algoritmu nejsou zadány žádné značky a je ponecháno na něm, aby sám našel strukturu na vstupu. Učení bez dohledu může být cílem samo o sobě (objevování skrytých vzorců v datech) nebo prostředkem k dosažení cíle (učení příznaků).
• Učení s posilováním:
  Systém interaguje s dynamickým prostředím, ve kterém musí splnit určitý cíl (například řídit vozidlo nebo hrát hru proti soupeři). Systém dostává zpětnou vazbu v podobě odměn a trestů, když se pohybuje v problémovém prostoru.

Mezi učením pod dohledem a bez dohledu se nachází učení s polovičním dohledem, kdy učitel poskytuje neúplný tréninkový signál: tréninkovou množinu, ve které některé (často mnohé) cílové výstupy chybí. V tomto příspěvku se zaměříme na učení bez dohledu a shlukování dat.

Učení bez dohledu

V některých problémech rozpoznávání vzorů se trénovací data skládají ze souboru vstupních vektorů x bez odpovídajících cílových hodnot. Cílem v takových problémech učení bez dohledu může být objevit skupiny podobných příkladů v rámci dat, kde se jedná o tzv. shlukování, nebo určit, jak jsou data rozložena v prostoru, což se nazývá odhad hustoty. Zjednodušeně řečeno, pro n-vzorkový prostor x1 až xn nejsou pro každý vzorek k dispozici pravdivé štítky tříd, proto se nazývá učení bez učitele.

Problémy s neřízeným učením:

• Neřízené učení je ve srovnání s úlohami řízeného učení obtížnější.
• Jak poznáme, zda jsou výsledky smysluplné, když nejsou k dispozici štítky odpovědí?
• Nechat experta podívat se na výsledky (externí hodnocení)
• Definovat objektivní funkci na shlukování (interní hodnocení)

Proč je i přes tyto problémy Unsupervised Learning potřeba?

• Označování velkých souborů dat je velmi nákladné, a proto můžeme ručně označit jen několik příkladů. Příklad: Příklad: Rozpoznávání řeči
• Mohou nastat případy, kdy nevíme, do kolika/jakých tříd jsou data rozdělena. Příklad:

Učení bez dohledu lze dále rozdělit do dvou kategorií:

• Parametrické učení bez dohledu
  V tomto případě předpokládáme parametrické rozdělení dat. Předpokládá, že vzorová data pocházejí z populace, která se řídí pravděpodobnostním rozdělením založeným na pevné sadě parametrů. Teoreticky mají v normální rodině rozdělení všechny její členy stejný tvar a jsou parametrizovány střední hodnotou a směrodatnou odchylkou. To znamená, že pokud znáte střední hodnotu a směrodatnou odchylku a že rozdělení je normální, znáte pravděpodobnost jakéhokoli budoucího pozorování. Parametrické učení bez dohledu zahrnuje konstrukci modelů Gaussovských směsí a použití algoritmu Expectation-Maximization k předpovědi třídy daného vzorku. Tento případ je mnohem obtížnější než standardní učení pod dohledem, protože nejsou k dispozici žádné štítky odpovědí, a tudíž není k dispozici správná míra přesnosti pro kontrolu výsledku.
• Neparametrické učení bez dohledu
  V neparametrické verzi učení bez dohledu jsou data seskupena do shluků, přičemž každý shluk(snad) říká něco o kategoriích a třídách přítomných v datech. Tato metoda se běžně používá k modelování a analýze dat s malou velikostí vzorku. Na rozdíl od parametrických modelů neparametrické modely nevyžadují od modeláře žádné předpoklady o rozdělení populace, a proto se někdy označují jako metoda bez rozdělení.

Co je shlukování?

Shlukování lze považovat za nejdůležitější problém neřízeného učení; jako každý jiný problém tohoto druhu se tedy zabývá nalezením struktury v souboru neoznačených dat. Volná definice shlukování by mohla znít „proces uspořádání objektů do skupin, jejichž členové jsou si nějakým způsobem podobní“. Shluk je tedy soubor objektů, které jsou si mezi sebou „podobné“ a jsou „nepodobné“ objektům patřícím do jiných shluků.

Shlukování založené na vzdálenosti.

Při dané množině bodů s pojmem vzdálenosti mezi body seskupení bodů do určitého počtu shluků tak, že

• vnitřní (v rámci shluku) vzdálenosti by měly být malé i.e členové shluků jsou si blízcí/podobní.
• vnější (vnitroskupinové) vzdálenosti by měly být velké, tj. členové různých shluků jsou si nepodobní.

Cíle shlukování

Cílem shlukování je určit vnitřní seskupení v souboru neoznačených dat. Jak ale rozhodnout, co představuje dobré shlukování? Lze ukázat, že neexistuje žádné absolutně „nejlepší“ kritérium, které by bylo nezávislé na konečném cíli shlukování. V důsledku toho je to uživatel, kdo by měl toto kritérium dodat tak, aby výsledek shlukování vyhovoval jeho potřebám.

Jak na výše uvedeném obrázku poznáme, co je nejlepší řešení shlukování?

Pro nalezení konkrétního řešení shlukování , musíme definovat míry podobnosti pro shluky.

Míry blízkosti

Pro shlukování musíme definovat míru blízkosti pro dva datové body. Blízkost zde znamená, jak jsou si vzorky navzájem podobné/nepodobné.

• Míra podobnosti S(xi,xk): velká, pokud jsou si xi,xk podobné
• Míra nepodobnosti (nebo vzdálenosti) D(xi,xk): malá, pokud jsou si xi,xk podobné

Existují různé míry podobnosti, které lze použít.

• Vektory: Kosinová vzdálenost

• Soubory: Jaccardova vzdálenost

• Body: Euklidovská vzdálenost
  q=2

„Dobrá“ míra blízkosti je VELMI závislá na aplikaci. Shluky by měly být invariantní při transformacích „přirozených“ pro daný problém. Při shlukování se také nedoporučuje normalizovat data, která jsou čerpána z více rozdělení.

Algoritmy shlukování

Algoritmy shlukování lze klasifikovat podle níže uvedeného seznamu:

• Výlučné shlukování
• Překrývající se shlukování
• Hierarchické shlukování
• Pravděpodobnostní shlukování

V prvním případě jsou data seskupena výlučným způsobem, takže pokud určitý datový bod patří do určitého shluku, pak nemohl být zahrnut do jiného shluku. Jednoduchý příklad je znázorněn na obrázku níže, kde je oddělení bodů dosaženo přímkou na dvourozměrné rovině.

Druhý typ, shlukování s překrýváním, naopak používá ke shlukování dat fuzzy množiny, takže každý bod může patřit do dvou nebo více shluků s různým stupněm příslušnosti. V tomto případě budou data přiřazena k příslušné hodnotě příslušnosti.

Hierarchický shlukovací algoritmus je založen na sjednocení dvou nejbližších shluků. Počáteční podmínka je realizována nastavením každého datového bodu jako shluku. Po několika iteracích se dospěje k hledaným konečným shlukům.

Nakonec poslední druh shlukování využívá zcela pravděpodobnostní přístup.

V tomto blogu si povíme o čtyřech nejpoužívanějších shlukovacích algoritmech:

• K-means
• Fuzzy K-means
• Hierarchické shlukování
• Mixture of Gaussians

Každý z těchto algoritmů patří do jednoho z výše uvedených typů shlukování. Zatímco K-means je výhradní shlukovací algoritmus, Fuzzy K-means je překrývající se shlukovací algoritmus, hierarchické shlukování je zřejmé a konečně Mixture of Gaussians je pravděpodobnostní shlukovací algoritmus. V následujících odstavcích se budeme zabývat jednotlivými metodami shlukování.

K-means shlukování

K-means je jedním z nejjednodušších algoritmů učení bez dohledu, který řeší známý problém shlukování. Postupuje jednoduchým a snadným způsobem klasifikace daného souboru dat prostřednictvím určitého počtu shluků (předpokládejme k shluků), který je stanoven a priori. Hlavní myšlenkou je definovat k center, jedno pro každý shluk. Tyto středy by měly být umístěny chytrým způsobem, protože různé umístění způsobuje různé výsledky. Lepší volbou je tedy umístit je co nejdále od sebe. Dalším krokem je vzít každý bod patřící do dané sady dat a přiřadit jej k nejbližšímu centroidu. Pokud žádný bod nečeká na přiřazení, je první krok ukončen a provede se předčasné seskupení. V tomto okamžiku musíme znovu vypočítat k nových centroidů jako barycentrů shluků vzniklých v předchozím kroku. Poté, co máme těchto k nových centroidů, je třeba provést novou vazbu mezi stejnými body datové sady a nejbližším novým centroidem. Byla vytvořena smyčka. V důsledku této smyčky si můžeme všimnout, že k centroidů mění svou polohu krok za krokem, dokud se neprovedou další změny. Jinými slovy, centroidy se již dále nepohybují.

Nakonec je cílem tohoto algoritmu minimalizace účelové funkce, v tomto případě funkce čtvercové chyby. Objektivní funkce

kde

je zvolená míra vzdálenosti mezi datovým bodem xi a středem shluku cj, je ukazatel vzdálenosti n datových bodů od jejich příslušných středů shluků.

Algoritmus se skládá z následujících kroků:

• Nechť X = {x1,x2,x3,……..,xn} je množina datových bodů a V = {v1,v2,…….,vc} je množina center.
• Náhodně vyberte ‚c‘ center shluků.
• Vypočtěte vzdálenost mezi každým datovým bodem a centry shluků.
• Přiřaďte datový bod ke středu shluku, jehož vzdálenost od středu shluku je minimální ze všech středů shluku.
• Přepočítejte nový střed shluku pomocí:

kde, ‚ci‘ představuje počet datových bodů v i-tém shluku.

• Přepočítejte vzdálenost mezi každým datovým bodem a nově získanými středy shluků.
• Pokud nebyl žádný datový bod přeřazen, zastavte, jinak opakujte od kroku 3).

Ačkoli lze dokázat, že postup vždy skončí, algoritmus k-means nemusí nutně najít nejoptimálnější konfiguraci, která odpovídá minimu globální účelové funkce. Algoritmus je také značně citlivý na počáteční náhodně vybraná centra shluků. Pro snížení tohoto vlivu lze algoritmus k-means spustit vícekrát.

K-means je jednoduchý algoritmus, který byl přizpůsoben mnoha problémovým doménám. Jak uvidíme, je vhodným kandidátem na rozšíření pro práci s fuzzy vektory příznaků.

Postup k-means lze považovat za chamtivý algoritmus pro rozdělení n vzorků do k shluků tak, aby se minimalizoval součet čtverců vzdáleností ke středům shluků. Má však některé slabiny:

• Nebyl specifikován způsob inicializace středních hodnot. Jedním z oblíbených způsobů je náhodný výběr k vzorků.
• Může se stát, že množina vzorků nejbližších mi je prázdná, takže mi nelze aktualizovat. To je problém, který je třeba řešit při implementaci, ale obvykle se ignoruje.
• Výsledky závisí na hodnotě k a neexistuje optimální způsob, jak popsat nejlepší „k“.

Tento poslední problém je obzvláště nepříjemný, protože často nemáme možnost vědět, kolik shluků existuje. Ve výše uvedeném příkladu je výsledkem stejného algoritmu aplikovaného na stejná data následující shlukování se třemi středními hodnotami. Je lepší nebo horší než shlukování 2-means?“

Naneštěstí neexistuje obecné teoretické řešení pro nalezení optimálního počtu shluků pro libovolný soubor dat. Jednoduchým přístupem je porovnat výsledky více běhů s různými k třídami a vybrat nejlepší podle daného kritéria, ale musíme být opatrní, protože zvyšování k vede z definice k menším hodnotám chybové funkce, ale také zvyšuje riziko nadměrného přizpůsobení.

Fuzzy K-Means Clustering

Při fuzzy shlukování má každý bod určitou pravděpodobnost příslušnosti ke každému shluku, nikoliv úplnou příslušnost pouze k jednomu shluku, jak je tomu v případě tradičního k-means. Fuzzy k-means se konkrétně snaží vypořádat s problémem, kdy se body nacházejí poněkud mezi středy nebo jsou jinak nejednoznačné, a to nahrazením vzdálenosti pravděpodobností, která samozřejmě může být nějakou funkcí vzdálenosti, například může mít pravděpodobnost vzhledem k inverzní hodnotě vzdálenosti. Fuzzy k-means používá vážený centroid založený na těchto pravděpodobnostech. Procesy inicializace, iterace a ukončení jsou stejné jako u k-means. Výsledné shluky se nejlépe analyzují jako pravděpodobnostní rozdělení, nikoli jako tvrdé přiřazení štítků. Je třeba si uvědomit, že k-means je speciálním případem fuzzy k-means, kdy je použitá pravděpodobnostní funkce jednoduše 1, pokud je datový bod nejblíže centroidu, a 0 v opačném případě.

Algoritmus fuzzy k-means je následující:

• Předpokládejme pevný počet shluků K.
• Inicializace: Náhodně inicializujte k-means μk spojené se shluky a vypočítejte pravděpodobnost, že každý datový bod Xi je členem daného shluku K,
  P(PointXiHasLabelK|Xi,K).
• Iterace: Přepočítejte centroid shluku jako vážený centroid daný pravděpodobností členství všech datových bodů Xi :

• Ukončení: Iterace probíhá až do dosažení konvergence nebo do dosažení uživatelem zadaného počtu iterací (iterace může být zachycena na některých lokálních maximech nebo minimech)

Pro lepší pochopení můžeme uvažovat tento jednoduchý jednorozměrný příklad. Je dána určitá množina dat, předpokládejme, že ji reprezentujeme jako rozloženou na ose. To ukazuje následující obrázek:

Při pohledu na obrázek můžeme identifikovat dva shluky v blízkosti dvou koncentrací dat. Budeme je označovat pomocí „A“ a „B“. V prvním přístupu uvedeném v tomto tutoriálu – algoritmu k-means – jsme každý datový bod přiřadili k určitému centroidu; proto tato funkce příslušnosti vypadala takto:

V přístupu Fuzzy k-means naopak stejný daný datový bod nepatří výhradně do přesně definovaného shluku, ale může být umístěn uprostřed. V tomto případě funkce příslušnosti sleduje hladší linii, která naznačuje, že každý datový bod může patřit do několika shluků s různým rozsahem příslušnosti.

Na výše uvedeném obrázku patří datový bod zobrazený jako červeně vyznačené místo spíše do shluku B než do shluku A. V případě, že se jedná o shluk s různým rozsahem příslušnosti, patří datový bod spíše do shluku A než do shluku B. Hodnota 0,2 „m“ označuje stupeň příslušnosti takového datového bodu k A.

Algoritmy hierarchického shlukování

Při souboru N položek, které mají být shlukovány, a matici vzdáleností (nebo podobnosti) N*N je základní postup hierarchického shlukování následující:

• Začněte přiřazením každé položky ke shluku, takže pokud máte N položek, máte nyní N shluků, z nichž každý obsahuje právě jednu položku. Vzdálenosti (podobnosti) mezi shluky nechť jsou stejné jako vzdálenosti (podobnosti) mezi položkami, které obsahují.
• Najděte nejbližší (nejpodobnější) dvojici shluků a spojte je do jednoho shluku, takže nyní máte o jeden shluk méně.
• Vypočítejte vzdálenosti (podobnosti) mezi novým shlukem a každým ze starých shluků.
• Pak opakujte kroky 2 a 3, dokud nebudou všechny položky shlukovány do jednoho shluku o velikosti N.

Shlukování jako směs Gaussů

Existuje ještě jeden způsob řešení problémů shlukování: přístup založený na modelu, který spočívá v použití určitých modelů pro shluky a pokusu o optimalizaci shody mezi daty a modelem.

V praxi lze každý shluk matematicky reprezentovat parametrickým rozdělením, například Gaussovým. Celý soubor dat je tedy modelován směsí těchto rozdělení.
Mixový model s vysokou pravděpodobností má tendenci mít následující vlastnosti:

• složková rozdělení mají vysoké „vrcholy“ (data v jednom shluku jsou těsná);
• směsový model dobře „pokrývá“ data (dominantní vzory v datech jsou zachyceny složkovými rozděleními).

Hlavní výhody shlukování založeného na modelu:

• k dispozici jsou dobře prozkoumané statistické inferenční techniky;
• flexibilita při výběru komponentního rozdělení;
• získat odhad hustoty pro každý shluk;
• k dispozici je „měkká“ klasifikace.

Směs Gaussů
Nejpoužívanější metoda shlukování tohoto druhu je založena na učení směsi Gaussů:

Model směsi je směs k složkových rozdělení, která dohromady tvoří rozdělení směsi f(x):

Příspěvek αk představuje příspěvek k-té komponenty při konstrukci f(x). V praxi se často používají parametrická rozdělení (např. gaussova), protože na pochopení jejich chování bylo vykonáno mnoho práce. Pokud každé fk(x) nahradíte gaussem, získáte tzv. gaussovské směsové modely (GMM).

Algoritmus EM

Expectation-Maximization předpokládá, že vaše data jsou složena z více vícerozměrných normálních rozdělení (všimněte si, že je to velmi silný předpoklad, zejména pokud stanovíte počet shluků!). Alternativně řečeno, EM je algoritmus pro maximalizaci věrohodnostní funkce, když jsou některé z proměnných ve vašem modelu nepozorované (tj. když máte latentní proměnné).
Můžete se spravedlivě ptát, když se snažíme pouze maximalizovat funkci, proč prostě nepoužijeme existující mechanismus pro maximalizaci funkce. No, pokud se pokusíte maximalizovat tak, že vezmete derivace a nastavíte je na nulu, zjistíte, že v mnoha případech podmínky prvního řádu nemají řešení. Problém slepice a vejce spočívá v tom, že k řešení parametrů modelu potřebujete znát rozdělení nepozorovaných dat; ale rozdělení nepozorovaných dat je funkcí parametrů modelu.

Expectation-Maximization se to snaží obejít tím, že iterativně odhadne rozdělení nepozorovaných dat, pak odhadne parametry modelu maximalizací něčeho, co je dolní hranicí skutečné věrohodnostní funkce, a opakuje to až do konvergence:

Algoritmus Expectation-Maximization

• Začněte s odhadem hodnot parametrů vašeho modelu
• E-step: Pro každý datový bod, který má chybějící hodnoty, použijte rovnici svého modelu k řešení rozdělení chybějících dat vzhledem k vašemu aktuálnímu odhadu parametrů modelu a vzhledem k pozorovaným datům (všimněte si, že řešíte rozdělení pro každou chybějící hodnotu, nikoliv pro očekávanou hodnotu). Nyní, když máme rozdělení pro každou chybějící hodnotu, můžeme vypočítat očekávání pravděpodobnostní funkce vzhledem k nepozorovaným proměnným. Pokud byl náš odhad parametrů modelu správný, bude tato očekávaná pravděpodobnost skutečnou pravděpodobností našich pozorovaných dat; pokud parametry nebyly správné, bude to pouze dolní mez.
• M-krok: Nyní, když máme funkci očekávané věrohodnosti bez nepozorovaných proměnných, maximalizujte funkci stejně jako v případě plně pozorovaných proměnných, abyste získali nový odhad parametrů modelu.
• Krok opakujte až do konvergence.

Problémy spojené se shlukováním

S shlukováním existuje řada problémů. Mezi ně patří:

• zpracování velkého počtu dimenzí a velkého počtu datových položek může být problematické kvůli časové složitosti;
• účinnost metody závisí na definici „vzdálenosti“ (u shlukování na základě vzdálenosti). Pokud neexistuje zřejmá míra vzdálenosti, musíme ji „definovat“, což není vždy snadné, zejména ve vícerozměrných prostorech;
• výsledek algoritmu shlukování (který může být v mnoha případech sám o sobě libovolný) lze interpretovat různými způsoby.

Možné aplikace

Algoritmy shlukování lze použít v mnoha oblastech, například:

• marketing: nalezení skupin zákazníků s podobným chováním vzhledem k velké databázi údajů o zákaznících obsahující jejich vlastnosti a záznamy o nákupech v minulosti;
• biologie: klasifikace rostlin a živočichů vzhledem k jejich vlastnostem;
• pojišťovnictví:
• Studie zemětřesení: shlukování pozorovaných epicenter zemětřesení za účelem identifikace nebezpečných zón;
• World Wide Web: klasifikace dokumentů; shlukování dat z weblogů za účelem odhalení skupin s podobnými vzorci přístupu.