Metoda de grupare este sarcina de a grupa un set de obiecte în așa fel încât acestea din același grup să fie mai asemănătoare între ele decât cu obiectele din alte industrii. Este sarcina principală a extragerii datelor și o tehnică generală de analiză statistică utilizată în multe domenii, inclusiv învățarea automată, recunoașterea modelelor, recunoașterea imaginilor, regăsirea informațiilor, compresia datelor și grafica pe computer.
Problemă de optimizare
Metoda de grupare în sine nu este un algoritm specific, ci o sarcină generală care trebuie rezolvată. Acest lucru poate fi realizat cu diverși algoritmi care diferă semnificativ în înțelegerea a ceea ce constituie un grup și a modului de a-l găsi eficient. Utilizarea metodei de grupare pentru formarea metasubiecților include utilizarea unui grup cudistanțe mici între membri, regiuni dense ale spațiului, intervale sau anumite distribuții statistice. Prin urmare, gruparea poate fi formulată ca o problemă de optimizare cu mai multe obiective.
Metoda adecvată și setările parametrilor (inclusiv elemente precum funcția de distanță de utilizat, pragul de densitate sau numărul de clustere așteptate) depind de setul de date individual și de utilizarea dorită a rezultatelor. Analiza ca atare nu este o sarcină automată, ci un proces iterativ de descoperire a cunoștințelor sau de optimizare interactivă cu mai multe obiective. Această metodă de grupare include încercări de încercare și eroare. Este adesea necesară modificarea parametrilor de preprocesare a datelor și a modelului până când rezultatul atinge proprietățile dorite.
Pe lângă termenul „clustering”, există o serie de cuvinte cu semnificații similare, inclusiv clasificare automată, taxonomie numerică, ambiologie și analiză tipologică. Diferențele subtile constă adesea în utilizarea metodei de grupare pentru a forma relații cu metasubiecții. În timp ce în extragerea datelor sunt de interes grupurile rezultate, în clasificarea automată este deja puterea discriminatorie care îndeplinește aceste funcții.
Analiza grupurilor s-a bazat pe numeroase lucrări ale lui Kroeber în 1932. A fost introdus în psihologie de Zubin în 1938 și de Robert Tryon în 1939. Și aceste lucrări au fost folosite de Cattell din 1943 pentru a indica clasificarea metodelor de grupare în teorie.
Termen
Conceptul de „cluster” nu poate fi definit cu precizie. Acesta este unul dintre motivele pentru care există atât de multe metode de grupare. Există un numitor comun: un grup de obiecte de date. Cu toate acestea, diferiți cercetători folosesc modele diferite. Și fiecare dintre aceste utilizări ale metodelor de grupare implică date diferite. Conceptul găsit de diverși algoritmi diferă semnificativ în proprietățile sale.
Folosirea metodei de grupare este cheia pentru înțelegerea diferențelor dintre instrucțiuni. Tiparele tipice de grup includ:
- Centroid s. Acesta este, de exemplu, când gruparea k-means reprezintă fiecare grup cu un vector mediu.
- Model de conexiune s. Aceasta este, de exemplu, gruparea ierarhică, care construiește modele bazate pe conectivitate la distanță.
- Model de distribuție s. În acest caz, clusterele sunt modelate folosind metoda clustering pentru a forma distribuții statistice metasubiecte. Cum ar fi separarea normală multivariată, care este aplicabilă algoritmului de maximizare a așteptărilor.
- Model de densitate s. Acestea sunt, de exemplu, DBSCAN (Spatial Clustering Algorithm with Noise) și OPTICS (Order Points for Structure Detection), care definesc clusterele ca regiuni dense conectate în spațiul de date.
- Model subspațial c. În biclustering (cunoscut și ca co-clustering sau două moduri), grupurile sunt modelate cu ambele elemente și cu atributele adecvate.
- Model s. Unii algoritmi nurelație rafinată pentru metoda lor de grupare pentru a genera rezultate meta-subiecte și pentru a oferi pur și simplu gruparea informațiilor.
- Model bazat pe graficul s. O clică, adică un subset de noduri, astfel încât fiecare două conexiuni din partea de margine poate fi considerată ca un prototip al formei clusterului. Slăbirea cererii totale este cunoscută sub denumirea de cvasi-clici. Exact același nume este prezentat în algoritmul de grupare HCS.
- Modele neuronale s. Cea mai cunoscută rețea nesupravegheată este harta auto-organizată. Și aceste modele pot fi de obicei caracterizate ca similare cu una sau mai multe dintre metodele de grupare de mai sus pentru formarea rezultatelor meta-subiectului. Include sisteme subspațiale atunci când rețelele neuronale implementează forma necesară de analiză a componentelor principale sau independente.
Acest termen este, de fapt, un set de astfel de grupuri, care de obicei conțin toate obiectele din setul de metode de grupare a datelor. În plus, poate indica relația dintre clustere unul cu celăl alt, cum ar fi o ierarhie de sisteme integrate unul în celăl alt. Gruparea poate fi împărțită în următoarele aspecte:
- Metoda de grupare a centrului dur. Aici, fiecare obiect aparține unui grup sau se află în afara acestuia.
- Sistem moale sau neclar. În acest moment, fiecare obiect aparține deja într-o anumită măsură oricărui cluster. Se mai numește și metoda de grupare fuzzy c-means.
Și diferențe mai subtile sunt, de asemenea, posibile. De exemplu:
- Cluster de partiţionare strictă. Aicifiecare obiect aparține exact unui grup.
- Partiționare strictă în cluster cu valori aberante. În acest caz, este posibil ca obiectele să nu aparțină niciunui cluster și să fie considerate inutile.
- Agrupare suprapusă (de asemenea, alternativă, cu vizualizări multiple). Aici, obiectele pot aparține mai multor ramuri. De obicei implică grupuri solide.
- Metode de grupare ierarhică. Obiectele care aparțin unui grup copil aparțin și subsistemului părinte.
- Formarea subspațiului. Deși similar cu grupurile care se suprapun, în cadrul unui sistem definit în mod unic, grupurile reciproce nu ar trebui să se suprapună.
Instrucțiuni
După cum sa menționat mai sus, algoritmii de grupare pot fi clasificați pe baza modelului lor de cluster. Următoarea recenzie va enumera numai cele mai proeminente exemple ale acestor instrucțiuni. Deoarece pot exista peste 100 de algoritmi publicati, nu toți oferă modele pentru clusterele lor și, prin urmare, nu pot fi clasificați cu ușurință.
Nu există un algoritm de grupare corect în mod obiectiv. Dar, după cum sa menționat mai sus, instrucțiunea este întotdeauna în câmpul de vedere al observatorului. Cel mai potrivit algoritm de grupare pentru o anumită problemă trebuie adesea ales experimental, cu excepția cazului în care există un motiv matematic pentru a prefera un model față de altul. Trebuie remarcat faptul că un algoritm proiectat pentru un singur tip de obicei nu funcționeazăun set de date care conține un subiect radical diferit. De exemplu, k-means nu pot găsi grupuri neconvexe.
Clustering bazat pe conexiune
Această uniune este cunoscută și sub numele ei, modelul ierarhic. Se bazează pe ideea tipică că obiectele sunt mai conectate la părțile învecinate decât la cele care sunt mult mai îndepărtate. Acești algoritmi conectează obiecte, formând grupuri diferite, în funcție de distanța lor. Un grup poate fi descris în principal prin distanța maximă necesară pentru a conecta diferitele părți ale clusterului. La toate distanțele posibile se vor forma alte grupuri, care pot fi reprezentate cu ajutorul unei dendrograme. Aceasta explică de unde provine denumirea comună „clustering ierarhic”. Adică, acești algoritmi nu oferă o singură partiție a setului de date, ci oferă în schimb o ordine extinsă de autoritate. Datorită lui, există o scurgere unul cu celăl alt la anumite distanțe. Într-o dendrogramă, axa y indică distanța la care grupurile se unesc. Și obiectele sunt aranjate de-a lungul liniei X, astfel încât grupurile să nu se amestece.
Clusterul bazat pe conexiune este o întreagă familie de metode care diferă în modul în care calculează distanțele. Pe lângă alegerea obișnuită a funcțiilor de distanță, utilizatorul trebuie să decidă și criteriul de conectare. Deoarece un cluster este format din mai multe obiecte, există multe opțiuni pentru a-l calcula. O alegere populară este cunoscută sub numele de grupare cu o singură pârghie, aceasta este metodalegătura completă, care conține UPGMA sau WPGMA (ansamblu neponderat sau ponderat de perechi cu medie aritmetică, cunoscut și sub denumirea de grupare a legăturilor medii). În plus, sistemul ierarhic poate fi aglomerativ (începând cu elemente individuale și combinându-le în grupuri) sau divizibil (începând cu un set complet de date și împărțindu-l în secțiuni).
Cluster distribuit
Aceste modele sunt cel mai strâns legate de statisticile care se bazează pe împărțiri. Clusterele pot fi ușor definite ca obiecte care aparțin, cel mai probabil, aceleiași distribuții. O caracteristică utilă a acestei abordări este că este foarte asemănătoare cu modul în care sunt create seturile de date artificiale. Prin eșantionarea obiectelor aleatoare dintr-o distribuție.
Deși baza teoretică a acestor metode este excelentă, ele suferă de o problemă cheie, cunoscută sub numele de supraadaptare, cu excepția cazului în care sunt impuse limite asupra complexității modelului. O asociere mai mare va explica de obicei datele mai bine, ceea ce face dificilă alegerea metodei potrivite.
Model de amestec gaussian
Această metodă folosește tot felul de algoritmi de maximizare a așteptărilor. Aici, setul de date este de obicei modelat cu un număr fix (pentru a evita suprascrierea) de distribuții gaussiene care sunt inițializate aleatoriu și ai căror parametri sunt optimizați iterativ pentru a se potrivi mai bine cu setul de date. Acest sistem va converge către un optim local. De aceea pot da mai multe alergărirezultate diferite. Pentru a obține cea mai strânsă grupare, caracteristicile sunt adesea atribuite distribuției Gauss la care este cel mai probabil să aparțină. Și pentru grupurile mai blânde, acest lucru nu este necesar.
Clusterul bazat pe distribuție creează modele complexe care pot surprinde în cele din urmă corelația și dependența dintre atribute. Cu toate acestea, acești algoritmi impun o povară suplimentară utilizatorului. Pentru multe seturi de date din lumea reală, este posibil să nu existe un model matematic definit concis (de exemplu, presupunând că o distribuție Gaussiană este o presupunere destul de puternică).
Clustering bazat pe densitate
În acest exemplu, grupurile sunt definite practic ca zone cu impermeabilitate mai mare decât restul setului de date. Obiectele din aceste părți rare, care sunt necesare pentru a separa toate componentele, sunt de obicei considerate puncte de zgomot și de margine.
Cea mai populară metodă de grupare bazată pe densitate este DBSCAN (Spatial Noise Clustering Algorithm). Spre deosebire de multe metode mai noi, are o componentă de cluster bine definită numită „accesibilitatea densității”. Similar cu clustering-ul bazat pe link, se bazează pe puncte de conexiune aflate în anumite praguri de distanță. Cu toate acestea, această metodă colectează numai acele articole care îndeplinesc criteriul de densitate. În versiunea originală, definită ca numărul minim de alte obiecte din această rază, clusterul este format din toatearticolele legate de densitate (care pot forma un grup cu formă liberă, spre deosebire de multe alte metode) și toate obiectele care se află în intervalul permis.
O altă proprietate interesantă a DBSCAN este că complexitatea sa este destul de scăzută - necesită un număr liniar de interogări de interval în baza de date. Și, de asemenea, neobișnuit este că va găsi în esență aceleași rezultate (acest lucru este determinist pentru punctele centrale și de zgomot, dar nu pentru elementele de limită) în fiecare rulare. Prin urmare, nu este nevoie să-l rulați de mai multe ori.
Principalul dezavantaj al DBSCAN și OPTICS este că se așteaptă la o scădere a densității pentru a detecta granițele clusterului. De exemplu, în seturile de date cu distribuții gaussiene care se suprapun - un caz de utilizare comun pentru obiectele artificiale - limitele clusterelor generate de acești algoritmi apar adesea arbitrare. Acest lucru se întâmplă deoarece densitatea grupurilor este în continuă scădere. Și într-un set de date de amestec gaussian, acești algoritmi depășesc aproape întotdeauna metodele precum gruparea EM, care sunt capabile să modeleze cu precizie aceste tipuri de sisteme.
Deplasarea medie este o abordare de grupare în care fiecare obiect se deplasează în zona cea mai densă din vecinătate pe baza unei estimări a întregului nucleu. În final, obiectele converg către maximele locale de impenetrabilitate. Similar cu gruparea k-means, acești „atractori de densitate” pot servi ca reprezentanți pentru un set de date. Dar schimbarea mediepoate detecta clustere de formă arbitrară similare cu DBSCAN. Datorită procedurii iterative costisitoare și estimării densității, deplasarea medie este de obicei mai lentă decât DBSCAN sau k-Means. În plus, aplicabilitatea algoritmului tipic de schimbare la datele cu dimensiuni mari este dificilă din cauza comportamentului neuniform al estimării densității nucleului, ceea ce duce la fragmentarea excesivă a coziilor clusterului.
Evaluare
Verificarea rezultatelor grupării este la fel de dificilă ca și gruparea în sine. Abordările populare includ scoring „intern” (unde sistemul este redus la o singură măsură a calității) și, desigur, scoring „extern” (unde gruparea este comparată cu o clasificare existentă „adevăr de bază”). Iar scorul manual al expertului uman și scorul indirect sunt găsite examinând utilitatea grupării în aplicația dorită.
Măsurile de semnalizare interne suferă de problema că reprezintă caracteristici care pot fi considerate ele însele ținte de grupare. De exemplu, este posibil să grupați datele date de coeficientul Silhouette, cu excepția faptului că nu există un algoritm eficient cunoscut pentru a face acest lucru. Folosind o astfel de măsură internă pentru evaluare, este mai bine să comparați asemănarea problemelor de optimizare.
Marca exterioară are probleme similare. Dacă există astfel de etichete de „adevăr de bază”, atunci nu este nevoie să grupați. Și în aplicațiile practice, de obicei nu există astfel de concepte. Pe de altă parte, etichetele reflectă doar o posibilă partiție a setului de date, ceea ce nu înseamnăcă nu există altă grupare (poate chiar mai bună).
Deci nici una dintre aceste abordări nu poate judeca în cele din urmă calitatea reală. Dar aceasta necesită o evaluare umană, care este foarte subiectivă. Cu toate acestea, astfel de statistici pot fi informative în identificarea clusterelor proaste. Dar nu ar trebui să ignorăm evaluarea subiectivă a unei persoane.
Marcă interioară
Când rezultatul unei grupări este evaluat pe baza datelor care au fost ele însele grupate, acesta este denumit acest termen. Aceste metode atribuie, în general, cel mai bun rezultat unui algoritm care creează grupuri cu similaritate ridicată în interiorul grupurilor și scăzută între grupuri. Unul dintre dezavantajele utilizării criteriilor interne în evaluarea clusterului este că scorurile ridicate nu conduc neapărat la aplicații eficiente de regăsire a informațiilor. De asemenea, acest scor este orientat către algoritmi care utilizează același model. De exemplu, gruparea k-means optimizează în mod natural distanțele caracteristicilor, iar un criteriu intern bazat pe acesta este probabil să supraestimeze gruparea rezultată.
De aceea, aceste măsuri de evaluare sunt cele mai potrivite pentru a-ți face o idee despre situațiile în care un algoritm funcționează mai bine decât altul. Dar asta nu înseamnă că fiecare informație oferă rezultate mai fiabile decât altele. Perioada de valabilitate măsurată de un astfel de indice depinde de afirmația că structura există în setul de date. Un algoritm dezvoltat pentru unele tipuri nu are nicio șansă dacă setul conține radicalcompoziție diferită sau dacă evaluarea măsoară criterii diferite. De exemplu, gruparea k-means poate găsi doar clustere convexe, iar mulți indici de scor asumă același format. Într-un set de date cu modele neconvexe, este inadecvat să se utilizeze k-medii și criterii tipice de evaluare.
Evaluare externă
Cu acest tip de grupare, rezultatele grupării sunt evaluate pe baza datelor care nu au fost utilizate pentru grupare. Adică, cum ar fi etichetele de clasă cunoscute și testele externe. Astfel de întrebări constau într-un set de articole preclasificate și sunt adesea create de experți (oameni). Ca atare, trusele de referință pot fi văzute ca standardul de aur pentru evaluare. Aceste tipuri de metode de scor măsoară cât de aproape este gruparea de clasele de referință date. Cu toate acestea, s-a discutat recent dacă acest lucru este adecvat pentru date reale sau numai pentru seturi sintetice cu adevărul real de fond. Deoarece clasele pot conține structură internă, iar atributele existente pot să nu permită separarea clusterelor. De asemenea, din punct de vedere al descoperirii cunoștințelor, reproducerea faptelor cunoscute poate să nu producă neapărat rezultatul așteptat. Într-un scenariu special de grupare restrânsă în care metainformațiile (cum ar fi etichetele de clasă) sunt deja utilizate în procesul de grupare, nu este trivial să păstrați toate informațiile în scopuri de evaluare.
Acum este clar ce nu se aplică metodelor de grupare și ce modele sunt folosite în aceste scopuri.
