Algoritmii familiei FOREL

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 14 ianuarie 2020; verificarea necesită 1 editare .

FOREL (Element formal) este un algoritm de grupare bazat pe ideea combinării obiectelor într-un singur cluster în zonele cu cea mai mare concentrație.

Scopul grupării

Împărțiți proba într-un astfel de număr (necunoscut anterior) de taxoni, astfel încât suma distanțelor de la obiectele clusterului la centrele clusterului să fie minimă pentru toate clusterele. Adică, sarcina noastră este să identificăm grupuri de obiecte cât mai apropiate unele de altele, care, în virtutea ipotezei de similitudine, vor forma clusterele noastre.

Calitatea funcțională minimizată de algoritm

F=\sum _{{j=1}}^{k}\sum _{{x\in K_{j}}}\rho (x,W_{j}),

unde prima însumare este peste toate grupurile de mostre, a doua însumare este peste toate obiectele aparținând clusterului curent și este centrul clusterului curent și este distanța dintre obiecte. $X$ $K_{j}$ $W_j$ $\rho (x,y)$

Condiții preliminare pentru muncă

Îndeplinirea ipotezei compactității , care presupune că obiectele apropiate unele de altele cu o probabilitate mare aparțin aceluiași cluster (taxon).
Prezența unui spațiu liniar sau metric de obiecte grupate.

Date de intrare

Eșantionarea grupată

Poate fi specificat prin descrierile de caracteristici ale obiectelor - un spațiu liniar sau o matrice de distanțe în perechi între obiecte.
Notă: în sarcinile reale, este adesea imposibil sau inutil să stocați toate datele, astfel încât datele necesare sunt colectate în procesul de grupare

Parametrul R este raza de căutare pentru concentrațiile locale

Poate fi setat atât din considerente a priori (cunoașterea diametrului clusterului), cât și reglat prin control glisant.

În modificări, este posibil să se introducă parametrul k — numărul de clustere.

Amprentă

Agruparea într-un număr necunoscut anterior de taxoni.

Cum funcționează

La fiecare pas, selectăm aleatoriu un obiect din probă, umflam o sferă cu raza R în jurul lui, alegem centrul de greutate din interiorul acestei sfere și îl facem centrul noii sfere. Adică, la fiecare pas deplasăm sfera în direcția concentrației locale a obiectelor de probă, adică încercăm să surprindem cât mai multe obiecte de probă cu o sferă de rază fixă. După ce centrul sferei se stabilizează, marchem toate obiectele din interiorul sferei cu acest centru ca grupate și le aruncăm din probă. Repetăm acest proces până când întreaga probă este grupată.

Algoritm

Selectăm aleatoriu obiectul curent din selecție;
Marcăm obiectele eșantion situate la o distanță mai mică decât R de cel curent;
Le calculăm centrul de greutate, marchem acest centru ca un nou obiect curent;
Repetați pașii 2-3 până când noul obiect curent se potrivește cu cel vechi;
Marcăm obiectele din interiorul sferei cu raza R în jurul obiectului curent ca grupate, le aruncăm din selecție;
Repetați pașii 1-5 până când întreaga probă este grupată.

Pseudocod al algoritmului într-un limbaj asemănător C :

# define R 30 // lățimea de căutare a grupării locale - parametrul de intrare al algoritmului clusterization_not_finished () ; // sunt toate obiectele grupate get_random_object (); // returnează un obiect arbitrar non- cluster get_neighbour_objects ( tip * obiect ); // returnează o matrice de obiecte situate <= R din centrul_obiectelor curente ( tip * masa_obiectelor ) ; // returnează centrul de greutate al obiectelor specificate delete_objects ( tip * mass_of_objects ); // elimină obiectele specificate din selecție ( le -am grupat deja ) while ( clusterisation_not_finished ()) { current_object = get_random_object (); obiecte_vecin = get_neighbour_objects ( obiect_curent ); centru_obiect = centru_obiecte ( obiecte_vecinate ); while ( obiect_centru ! = obiect_curent ) // până când centrul de greutate se stabilizează { obiect_curent = obiect_centru ; obiecte_vecin = get_neighbour_objects ( obiect_curent ); centru_obiect = centru_obiecte ( obiecte_vecinate ); } şterge_obiecte ( obiecte_vecinate ); }

Euristica centrului de greutate

În spațiul liniar, centrul de masă;
Într-un spațiu metric, un obiect, suma distanțelor până la care este minimă, între toate în interiorul sferei;
Un obiect care, in interiorul unei sfere de raza R, contine numarul maxim de alte obiecte din intreaga selectie (lent);
Obiectul care conține numărul maxim de obiecte în interiorul unei sfere de rază mică (dintr-o sferă de rază R).

Observații

Se dovedește convergența algoritmului într-un număr finit de pași;
În spațiul liniar, centrul de greutate poate fi un punct arbitrar în spațiu, în spațiul metric, doar obiectul probei;
Cu cât R este mai mic, cu atât mai mulți taxoni (clusters);
În spațiul liniar, căutarea centrului are loc în timp O(n), în spațiul metric O(n²);
Algoritmul realizează cele mai bune rezultate pe probe cu o bună îndeplinire a condițiilor de compactitate;
La repetarea iterațiilor, este posibilă scăderea parametrului R, pentru cea mai rapidă convergență;
Clusteringul este foarte dependent de aproximarea inițială (selectarea obiectului în primul pas);
Se recomandă re-executarea algoritmului pentru a elimina situația de clustering „proastă”, din cauza unei alegeri nereușite a obiectelor inițiale.

Beneficii

Precizia minimizării calității funcționale (cu o selecție cu succes a parametrului R);
Vizualizarea vizualizării grupării;
Convergența algoritmului;
Posibilitatea operațiunilor pe centrele clusterelor - acestea sunt cunoscute în cursul algoritmului;
Abilitatea de a calcula funcționale de calitate intermediară, de exemplu, lungimea unui lanț de concentrații locale;
Posibilitatea de a testa ipoteze de asemănare și compactitate în procesul de operare a algoritmului.

Dezavantaje

Performanță relativ scăzută (se rezolvă introducerea funcției de recalculare a căutării centrului la adăugarea a 1 obiect în interiorul sferei);
Aplicabilitate slabă a algoritmului cu separabilitate slabă a probei în clustere;
Instabilitatea algoritmului (dependența de alegerea obiectului inițial);
Partiționare arbitrară după număr în clustere;
Necesitatea cunoștințelor a priori despre lățimea (diametrul) clusterelor.

Suplimente

După ce algoritmul a lucrat la gruparea finală, puteți efectua câteva acțiuni:

Selectarea celor mai reprezentative (reprezentative) obiecte din fiecare cluster. Puteți alege centrele de clustere, puteți alege mai multe obiecte din fiecare cluster, ținând cont de cunoștințele a priori despre reprezentativitatea necesară a eșantionului. Astfel, conform grupării finalizate, avem posibilitatea de a construi eșantionul cel mai reprezentativ;
Recalcularea grupării (multilevelness) folosind metoda KNI.

Domeniul de aplicare

Rezolvarea problemelor de clustering;
Rezolvarea problemelor de clasificare a unui eșantion.

Vezi și

analiza grupului

Literatură

Vorontsov K. V. Prelegeri despre clustering și algoritmi de scalare multidimensională , Universitatea de Stat din Moscova, 2007
Zagoruiko N. G., Yolkina V. N., Lbov G. S. Algoritmi pentru detectarea modelelor empirice. - Novosibirsk: Nauka, 1985. - 999 p.
Zagoruiko NG Metode aplicate de analiză a datelor și a cunoștințelor. - Novosibirsk: IM SO RAN, 1999. - 270 p. - ISBN 5-86134-060-9 .