Ok, začněme mluvit o DBSCAN.
Hustotní prostorové shlukování aplikací se šumem (DBSCAN) je dobře známý algoritmus shlukování dat, který se běžně používá při dolování dat a strojovém učení.
Na základě množiny bodů (uvažujme v dvojrozměrném prostoru, jak je znázorněno na obrázku) DBSCAN seskupuje body, které jsou si blízké, na základě měření vzdálenosti (obvykle euklidovské vzdálenosti) a minimálního počtu bodů. Jako odlehlé body označuje také body, které se nacházejí v oblastech s nízkou hustotou.
Parametry:
Algoritmus DBSCAN vyžaduje v zásadě 2 parametry:
eps: určuje, jak blízko by si měly být body, aby byly považovány za součást shluku. To znamená, že pokud je vzdálenost mezi dvěma body menší nebo rovna této hodnotě (eps), jsou tyto body považovány za sousedy.
minPoints: minimální počet bodů pro vytvoření husté oblasti. Pokud například nastavíme parametr minPoints na hodnotu 5, pak k vytvoření husté oblasti potřebujeme alespoň 5 bodů.
Odhad parametrů:
Odhad parametrů je problémem každé úlohy dolování dat. Abychom mohli zvolit dobré parametry, musíme rozumět jejich použití a mít alespoň základní předchozí znalosti o datové sadě, kterou budeme používat.
eps: pokud je zvolená hodnota eps příliš malá, velká část dat nebude shlukována. Bude považována za odlehlé hodnoty, protože nesplňují počet bodů pro vytvoření husté oblasti. Na druhou stranu, pokud je zvolená hodnota příliš vysoká, shluky se spojí a většina objektů bude ve stejném shluku. Hodnota eps by měla být zvolena na základě vzdálenosti souboru dat (k jejímu zjištění můžeme použít graf k-vzdálenosti), ale obecně jsou vhodnější malé hodnoty eps.
minPoints: Obecně platí, že minimální minPoints lze odvodit z počtu dimenzí (D) v souboru dat, protože minPoints ≥ D + 1. Větší hodnoty jsou obvykle lepší pro soubory dat se šumem a vytvoří významnější shluky. Minimální hodnota minPoints musí být 3, ale čím větší je soubor dat, tím větší hodnotu minPoints je třeba zvolit.
Další informace o odhadu parametrů najdete zde.
Proč bychom měli používat DBSCAN?
Algoritmus DBSCAN by měl sloužit k hledání asociací a struktur v datech, které je obtížné najít ručně, ale které mohou být relevantní a užitečné pro hledání vzorů a předpovídání trendů.
Metody shlukování se obvykle používají v biologii, medicíně, sociálních vědách, archeologii, marketingu, rozpoznávání znaků, systémech řízení atd.
Přemýšlejme v praktickém využití DBSCAN. Předpokládejme, že máme elektronický obchod a chceme zlepšit prodej tím, že zákazníkům doporučíme relevantní produkty. Nevíme přesně, co naši zákazníci hledají, ale na základě souboru dat můžeme předpovědět a doporučit relevantní produkt konkrétnímu zákazníkovi. Na náš soubor dat (založený na databázi elektronického obchodu) můžeme použít DBSCAN a najít shluky na základě produktů, které uživatelé zakoupili. Pomocí těchto shluků můžeme najít podobnosti mezi zákazníky, například zákazník A koupil 1 pero, 1 knihu a 1 nůžky a zákazník B koupil 1 knihu a 1 nůžky, pak můžeme zákazníkovi B doporučit 1 pero. To je jen malý příklad použití DBSCAN, ale lze jej použít v mnoha aplikacích v několika oblastech.
Jak jej můžeme snadno implementovat?
Jak jsem již napsal (rada: nevěřte všemu, co napíšu), DBSCAN je známý algoritmus, proto se nemusíte bát jej implementovat sami. Můžete použít některou z knihoven/balíků, které lze najít na internetu. Zde je seznam odkazů, na kterých můžete najít implementaci DBSCAN: Matlab, R, R, Python, Python.
Vytvořil jsem také aplikaci (v portugalštině), která didakticky vysvětluje, jak DBSCAN funguje. Aplikace byla napsána v C++ a najdete ji na Githubu.