Algoritmy rodiny FOREL

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. ledna 2020; ověření vyžaduje 1 úpravu .

FOREL (Formal Element)  je shlukovací algoritmus založený na myšlence spojování objektů do jednoho shluku v oblastech jejich největší koncentrace.

Účel shlukování

Rozdělte vzorek na takový (dříve neznámý) počet taxonů , aby součet vzdáleností od objektů shluku ke středům shluků byl pro všechny shluky minimální. To znamená, že naším úkolem je identifikovat skupiny objektů co nejblíže u sebe, které na základě hypotézy podobnosti budou tvořit naše shluky.

Kvalitní funkcional minimalizovaný algoritmem

,

kde první součet je přes všechny ukázkové shluky, druhý součet je přes všechny objekty patřící do aktuálního shluku a  je středem aktuálního shluku a  je to vzdálenost mezi objekty.

Předpoklady pro práci

Vstupní data

Může být specifikován popisem vlastností objektů — lineárním prostorem nebo maticí párových vzdáleností mezi objekty.
Poznámka: ve skutečných úlohách je často nemožné nebo zbytečné uložit všechna data, takže potřebná data jsou shromažďována v procesu shlukování

Lze jej nastavit jak z apriorních úvah (znalost průměru clusteru), tak nastavit posuvným ovladačem.

Otisk

Shlukování do dříve neznámého počtu taxonů.

Jak to funguje

V každém kroku náhodně vybereme objekt ze vzorku, nafoukneme kolem něj kouli o poloměru R, vybereme těžiště uvnitř této koule a uděláme z ní střed nové koule. To znamená, že v každém kroku pohybujeme koulí ve směru lokální koncentrace vzorových objektů, to znamená, že se snažíme zachytit co nejvíce vzorových objektů koulí s pevným poloměrem. Poté, co se střed koule ustálí, označíme všechny objekty uvnitř koule s tímto středem jako seskupené a vyřadíme je ze vzorku. Tento postup opakujeme, dokud se celý vzorek neshlukuje.

Algoritmus

  1. Z výběru náhodně vybereme aktuální objekt;
  2. Označíme ukázkové objekty umístěné ve vzdálenosti menší než R od aktuálního;
  3. Vypočítáme jejich těžiště, označíme tento střed jako nový aktuální objekt;
  4. Opakujte kroky 2-3, dokud se nový aktuální objekt neshoduje se starým;
  5. Objekty uvnitř koule o poloměru R kolem aktuálního objektu označíme jako seskupené, vyhodíme je z výběru;
  6. Opakujte kroky 1-5, dokud nebude celý vzorek shlukovaný.

Pseudokód algoritmu v jazyce podobném C :

# define R 30 // šířka vyhledávání lokálního shlukování - vstupní parametr algoritmu clusterization_not_finished () ; // jsou všechny objekty seskupené get_random_object (); // vrátí libovolný neshlukovaný objekt get_neighbour_objects ( type * object ); // vrátí pole objektů umístěných < = R z aktuálního středu_objektů ( typ * hmotnost_objektů ) ; _ // vrátí těžiště zadaných objektů delete_objects ( type * mass_of_objects ) ; // odstraní zadané objekty z výběru ( již jsme je seskupili ) while ( clusterisation_not_finished ()) { current_object = get_random_object (); sousední_objekty = získat_objekty_souseda ( aktuální_objekt ); středový_objekt = střed_objektů ( sousední_objekty ); while ( středový_objekt ! = aktuální_objekt ) // dokud se těžiště nestabilizuje { aktuální_objekt = středový_objekt ; _ sousední_objekty = získat_objekty_souseda ( aktuální_objekt ); středový_objekt = střed_objektů ( sousední_objekty ); } odstranit_objekty ( sousední_objekty ); }

Heuristika těžiště

  • V lineárním prostoru těžiště;
  • V metrickém prostoru objekt, jehož součet vzdáleností je minimální, mezi všemi uvnitř koule;
  • Objekt, který uvnitř koule o poloměru R obsahuje maximální počet dalších objektů z celého výběru (pomalu);
  • Objekt, který obsahuje maximální počet objektů uvnitř koule o malém poloměru (z koule o poloměru R).

Pozorování

  • Je dokázána konvergence algoritmu v konečném počtu kroků;
  • V lineárním prostoru může být těžištěm libovolný bod v prostoru, v metrickém prostoru pouze objekt vzorku;
  • Čím menší R, tím více taxonů (shluků);
  • V lineárním prostoru dochází k hledání středu v čase O(n), v metrickém prostoru O(n²);
  • Algoritmus dosahuje nejlepších výsledků na vzorcích s dobrým splněním podmínek kompaktnosti;
  • Při opakování iterací je možné snížit parametr R pro nejrychlejší konvergenci;
  • Shlukování je velmi závislé na počáteční aproximaci (výběr objektu v prvním kroku);
  • Doporučuje se znovu spustit algoritmus, aby se eliminovala situace "špatného" shlukování kvůli neúspěšné volbě počátečních objektů.

Výhody

  1. Přesnost minimalizace kvalitativního funkčního (při úspěšném výběru parametru R);
  2. Vizualizace vizualizace shlukování;
  3. Konvergence algoritmu;
  4. Možnost operací na středech shluků - jsou známy v průběhu algoritmu;
  5. Schopnost vypočítat funkcionály střední kvality, například délku řetězce lokálních koncentrací;
  6. Možnost testovat hypotézy podobnosti a kompaktnosti v procesu operace algoritmu.

Nevýhody

  1. Relativně nízký výkon (vyřešeno zavedení funkce přepočítání hledání středu při přidání 1 objektu uvnitř koule);
  2. Špatná použitelnost algoritmu se špatnou separovatelností vzorku do shluků;
  3. Nestabilita algoritmu (závislost na volbě výchozího objektu);
  4. Libovolné rozdělení podle čísel do shluků;
  5. Potřeba apriorních znalostí o šířce (průměru) shluků.

Doplňky

Poté, co algoritmus pracuje na dokončeném shlukování, můžete provést některé akce:

  1. Výběr nejreprezentativnějších (reprezentativních) objektů z každého shluku. Můžete si vybrat středy shluků, můžete si vybrat několik objektů z každého shluku s ohledem na apriorní znalosti o požadované reprezentativnosti vzorku. Podle hotového shlukování tak máme možnost sestavit co nejreprezentativnější vzorek;
  2. Přepočet shlukování (multilevelness) metodou KNI.

Rozsah

  1. Řešení problémů se shlukováním;
  2. Řešení problémů klasifikace vzorku.

Viz také

Literatura