Învățare nesupravegheată și gruparea datelor

O sarcină care implică învățarea automată poate să nu fie liniară, dar are un număr de etape bine cunoscute:

Definirea problemei.
Pregătirea datelor.
Învățarea unui model de bază.
Îmbunătățiți modelul subiacent prin evaluări cantitative și calitative.
Prezentați modelul.

O modalitate bună de a se împăca cu o nouă problemă este de a lucra prin identificarea și definirea problemei în cel mai bun mod posibil și de a învăța un model care să capteze informații semnificative din date. În timp ce problemele de recunoaștere a modelelor și de învățare automată pot fi de diferite tipuri, ele pot fi clasificate în linii mari în trei categorii:

Învățare supervizată:
Sistemului i se prezintă exemple de intrări și ieșirile dorite ale acestora, date de un „profesor”, iar scopul este de a învăța o regulă generală care corelează intrările cu ieșirile.
Învățare nesupravegheată:
Nu se dau etichete algoritmului de învățare, lăsându-l pe acesta să găsească singur structura în datele de intrare. Învățarea nesupravegheată poate fi un scop în sine (descoperirea modelelor ascunse în date) sau un mijloc pentru atingerea unui scop (învățarea caracteristicilor).
Învățarea prin întărire:
Un sistem interacționează cu un mediu dinamic în care trebuie să îndeplinească un anumit obiectiv (cum ar fi conducerea unui vehicul sau un joc împotriva unui adversar). Sistemul primește feedback în termeni de recompense și pedepse pe măsură ce navighează în spațiul său de probleme.

Între învățarea supravegheată și cea nesupravegheată se află învățarea semisupravegheată, în care profesorul oferă un semnal de instruire incomplet: un set de instruire în care lipsesc unele (adesea multe) dintre ieșirile țintă. Ne vom concentra pe învățarea nesupravegheată și pe gruparea datelor în această postare pe blog.

Învățare nesupravegheată

În unele probleme de recunoaștere a tiparelor, datele de instruire constau dintr-un set de vectori de intrare x fără valori țintă corespunzătoare. Scopul în astfel de probleme de învățare nesupravegheată poate fi acela de a descoperi grupuri de exemple similare în cadrul datelor, unde se numește clusterizare, sau de a determina modul în care datele sunt distribuite în spațiu, cunoscut sub numele de estimare a densității. Pentru a prezenta în termeni mai simpli, pentru un spațiu cu n eșantioane de la x1 la xn, etichetele de clasă adevărate nu sunt furnizate pentru fiecare eșantion, de aceea este cunoscută sub numele de învățare fără profesor.

Probleme cu învățarea nesupravegheată:

Învățarea nesupravegheată este mai dificilă în comparație cu sarcinile de învățare supravegheată…
Cum știm dacă rezultatele sunt semnificative din moment ce nu sunt disponibile etichete de răspuns?
Lăsăm expertul să se uite la rezultate (evaluare externă)
Definiți o funcție obiectivă privind gruparea (evaluare internă)

De ce este necesară învățarea nesupravegheată în ciuda acestor probleme?

Annotarea seturilor mari de date este foarte costisitoare și, prin urmare, putem eticheta manual doar câteva exemple. Exemplu: Recunoașterea vorbirii
Există cazuri în care nu știm în câte/în ce clase sunt împărțite datele. Exemplu: Data Mining
S-ar putea să dorim să folosim gruparea pentru a obține o idee despre structura datelor înainte de a proiecta un clasificator.

Învățarea nesupravegheată poate fi clasificată în continuare în două categorii:

Învățarea nesupravegheată parametrică
În acest caz, presupunem o distribuție parametrică a datelor. Se presupune că datele din eșantion provin dintr-o populație care urmează o distribuție de probabilitate bazată pe un set fix de parametri. Teoretic, într-o familie normală de distribuții, toți membrii au aceeași formă și sunt parametrizate prin medie și abatere standard. Aceasta înseamnă că, dacă cunoașteți media și abaterea standard și că distribuția este normală, cunoașteți probabilitatea oricărei observații viitoare. Învățarea parametrică nesupravegheată implică construirea de modele de amestecuri gaussiene și utilizarea algoritmului de maximizare a așteptărilor pentru a prezice clasa eșantionului în cauză. Acest caz este mult mai dificil decât învățarea supravegheată standard, deoarece nu există etichete de răspuns disponibile și, prin urmare, nu există o măsură corectă a acurateței disponibilă pentru a verifica rezultatul.
Învățarea neparametrică nesupravegheată
În versiunea neparametrizată a învățării nesupravegheate, datele sunt grupate în clustere, unde fiecare cluster(sperăm) spune ceva despre categoriile și clasele prezente în date. Această metodă este utilizată în mod obișnuit pentru a modela și analiza date cu eșantioane de dimensiuni mici. Spre deosebire de modelele parametrice, modelele neparametrice nu necesită ca modelatorul să facă nici o presupunere despre distribuția populației, astfel încât sunt uneori denumite metode fără distribuție.

Ce este Clustering?

Clustering poate fi considerată cea mai importantă problemă de învățare nesupravegheată; astfel, ca orice altă problemă de acest tip, se ocupă cu găsirea unei structuri într-o colecție de date neetichetate. O definiție liberă a clustering-ului ar putea fi „procesul de organizare a obiectelor în grupuri ai căror membri sunt similari într-un anumit fel”. Un cluster este, prin urmare, o colecție de obiecte care sunt „similare” între ele și care sunt „disimilare” față de obiectele aparținând altor clustere.

Gruparea bazată pe distanțe.

Dat fiind un set de puncte, cu o noțiune de distanță între puncte, gruparea punctelor într-un anumit număr de clustere, astfel încât

distanțele interne (în cadrul clusterelor) să fie mici i.e membrii clusterelor sunt apropiați/similari între ei.
Distanțele externe (în interiorul clusterelor) ar trebui să fie mari, adică membrii unor clustere diferite sunt diferiți.

Obiectivele grupării

Obiectivul grupării este de a determina gruparea internă într-un set de date neetichetate. Dar cum să decidem ce constituie o bună grupare? Se poate demonstra că nu există un criteriu absolut „cel mai bun” care să fie independent de scopul final al clusterizării. În consecință, utilizatorul este cel care ar trebui să furnizeze acest criteriu, în așa fel încât rezultatul clusterizării să corespundă nevoilor sale.

În imaginea de mai sus, cum putem ști care este cea mai bună soluție de clusterizare?

Pentru a găsi o anumită soluție de clusterizare , trebuie să definim măsurile de similaritate pentru clustere.

Măsuri de proximitate

Pentru clusterizare, trebuie să definim o măsură de proximitate pentru două puncte de date. Proximitatea înseamnă aici cât de asemănătoare/disimilare sunt eșantioanele unul față de celălalt.

Măsura de similitudine S(xi,xk): mare dacă xi,xk sunt similare
Măsura de disimilaritate (sau distanță) D(xi,xk): mică dacă xi,xk sunt similare

Există diferite măsuri de similaritate care pot fi utilizate.

Vectori: Cosine Distance

este o măsură de distanță aleasă între un punct de date xi și centrul clusterului cj, este un indicator al distanței dintre cele n puncte de date și centrele lor de cluster respective.

Agoritmul este compus din următoarele etape:

Să fie X = {x1,x2,x3,……..,xn} setul de puncte de date și V = {v1,v2,…….,vc} setul de centre.
Selectați aleatoriu ‘c’ centre de cluster.
Calculați distanța dintre fiecare punct de date și centrele de cluster.
Asemnați punctul de date la centrul de cluster a cărui distanță față de centrul de cluster este minimă dintre toate centrele de cluster.
Recalculați noul centru de cluster folosind:

unde, ‘ci’ reprezintă numărul de puncte de date din clusterul ith.

Recalculează distanța dintre fiecare punct de date și centrele noilor clustere obținute.
Dacă nici un punct de date nu a fost realocat, atunci se oprește, altfel se repetă de la pasul 3).

Deși se poate dovedi că procedura se va termina întotdeauna, algoritmul k-means nu găsește neapărat cea mai optimă configurație, corespunzătoare minimului funcției obiectiv globale. Algoritmul este, de asemenea, sensibil în mod semnificativ la centrele de cluster inițiale selectate aleatoriu. Algoritmul k-means poate fi rulat de mai multe ori pentru a reduce acest efect.

K-means este un algoritm simplu care a fost adaptat la multe domenii de probleme. După cum vom vedea, este un bun candidat pentru a fi extins pentru a lucra cu vectori de caracteristici fuzzy.

Procedura k-means poate fi privită ca un algoritm lacom pentru împărțirea celor n eșantioane în k clustere, astfel încât să se minimizeze suma distanțelor la pătrat față de centrele clusterelor. Are însă câteva puncte slabe:

Nu a fost specificat modul de inițializare a mediilor. Un mod popular de a începe este de a alege la întâmplare k dintre eșantioane.
Se poate întâmpla ca setul de eșantioane cel mai apropiat de mi să fie gol, astfel încât mi nu poate fi actualizat. Aceasta este o problemă care trebuie tratată în timpul implementării, dar este în general ignorată.
Rezultatele depind de valoarea lui k și nu există o modalitate optimă de a descrie cel mai bun „k”.

Această ultimă problemă este deosebit de supărătoare, deoarece adesea nu avem cum să știm câte clustere există. În exemplul prezentat mai sus, același algoritm aplicat acelorași date produce următoarea clasificare pe 3 medii. Este aceasta mai bună sau mai proastă decât gruparea în 2 medii?

Din păcate, nu există o soluție teoretică generală pentru a găsi numărul optim de clustere pentru orice set de date dat. O abordare simplă este de a compara rezultatele mai multor rulări cu diferite clase k și de a o alege pe cea mai bună în funcție de un anumit criteriu, dar trebuie să fim atenți, deoarece creșterea lui k duce la valori mai mici ale funcției de eroare prin definiție, dar crește și riscul de supraajustare.

Fuzzy K-Means Clustering

În fuzzy clustering, fiecare punct are o probabilitate de apartenență la fiecare cluster, mai degrabă decât să aparțină în totalitate unui singur cluster, așa cum este cazul în k-means tradițional. Fuzzy k-means încearcă în mod specific să abordeze problema în care punctele se află oarecum între centre sau sunt ambigue prin înlocuirea distanței cu probabilitatea, care, desigur, ar putea fi o funcție a distanței, cum ar fi o probabilitate în raport cu inversul distanței. Fuzzy k-means utilizează un centroid ponderat pe baza acestor probabilități. Procesele de inițializare, iterație și încheiere sunt aceleași cu cele utilizate în cazul k-means. Clusterele rezultate sunt analizate cel mai bine ca distribuții probabilistice, mai degrabă decât ca o atribuire strictă de etichete. Trebuie să ne dăm seama că k-means este un caz special de fuzzy k-means când funcția de probabilitate folosită este pur și simplu 1 dacă punctul de date este cel mai apropiat de un centroid și 0 în caz contrar.

Algoritmul fuzzy k-means este următorul:

Să presupunem un număr fix de clustere K.
Inițializare: Se inițializează aleatoriu k-means μk asociat cu clusterele și se calculează probabilitatea ca fiecare punct de date Xi să fie membru al unui anumit cluster K,
P(PointXiHasLabelK|Xi,K).
Iterare: Se recalculează centroidul clusterului ca centroid ponderat, având în vedere probabilitățile de apartenență a tuturor punctelor de date Xi :

Încheiere: Iterați până la convergență sau până când se atinge un număr de iterații specificat de utilizator (iterația poate fi blocată la unele maxime sau minime locale)

Pentru o mai bună înțelegere, putem lua în considerare acest exemplu simplu mono-dimensional. Dat fiind un anumit set de date, să presupunem că îl reprezentăm ca fiind distribuit pe o axă. Figura de mai jos arată acest lucru:

Urmărind imaginea, putem identifica două clustere în apropierea celor două concentrări de date. Ne vom referi la ele folosind „A” și „B”. În prima abordare prezentată în acest tutorial – algoritmul k-means – am asociat fiecare punct de date cu un anumit centroid; prin urmare, această funcție de apartenență arăta astfel:

În abordarea Fuzzy k-means, în schimb, același punct de date dat nu aparține exclusiv unui cluster bine definit, ci poate fi plasat într-o cale de mijloc. În acest caz, funcția de apartenență urmează o linie mai netedă pentru a indica faptul că fiecare punct de date poate aparține mai multor clustere cu grade diferite de apartenență.

În figura de mai sus, punctul de date indicat ca punct marcat cu roșu aparține mai degrabă clusterului B decât clusterului A. Valoarea 0,2 a lui ‘m’ indică gradul de apartenență la A pentru un astfel de punct de date.

Algoritmi de clusterizare ierarhică

Dat fiind un set de N elemente care urmează să fie grupate și o matrice de distanțe (sau de similaritate) N*N, procesul de bază al clusterizării ierarhice este următorul:

Începeți prin a atribui fiecare element unui cluster, astfel încât, dacă aveți N elemente, aveți acum N clustere, fiecare conținând doar un singur element. Lăsați distanțele (asemănările) dintre clustere să fie aceleași cu distanțele (asemănările) dintre elementele pe care le conțin.
Căutați cea mai apropiată (cea mai asemănătoare) pereche de clustere și uniți-le într-un singur cluster, astfel încât acum aveți un cluster mai puțin.
Calculați distanțele (asemănările) dintre noul cluster și fiecare dintre vechile clustere.
Repetați pașii 2 și 3 până când toate elementele sunt grupate într-un singur cluster de dimensiune N.

Clustering as a Mixture of Gaussians

Există o altă modalitate de abordare a problemelor de clusterizare: o abordare bazată pe model, care constă în utilizarea anumitor modele pentru clustere și încercarea de a optimiza potrivirea dintre date și model.

În practică, fiecare cluster poate fi reprezentat matematic de o distribuție parametrică, cum ar fi o gaussiană. Prin urmare, întregul set de date este modelat printr-un amestec al acestor distribuții.
Un model de amestec cu probabilitate ridicată tinde să aibă următoarele trăsături:

distribuțiile componente au „vârfuri” ridicate (datele dintr-un cluster sunt strânse);
modelul de amestec „acoperă” bine datele (modelele dominante din date sunt captate de distribuțiile componente).

Principalele avantaje ale grupării bazate pe model:

sunt disponibile tehnici de inferență statistică bine studiate;
flexibilitate în alegerea distribuției componente;
obținerea unei estimări a densității pentru fiecare grup;
este disponibilă o clasificare „soft”.

Mixture of Gaussians
Cea mai utilizată metodă de clusterizare de acest tip se bazează pe învățarea unui amestec de Gaussians:

Un model de amestec este un amestec de k distribuții componente care, în mod colectiv, formează o distribuție de amestec f(x):

Anexa αk reprezintă contribuția celei de-a k-a componente în construirea lui f(x). În practică, distribuțiile parametrice (de exemplu, gaussienii), sunt adesea utilizate deoarece s-a lucrat mult pentru a înțelege comportamentul lor. Dacă înlocuiți fiecare fk(x) cu o gaussiană, obțineți ceea ce se numește modele de amestec gaussian (GMM).

Algoritmul EM

Expectația-Maximizarea presupune că datele dumneavoastră sunt compuse din mai multe distribuții normale multivariate (rețineți că aceasta este o ipoteză foarte puternică, în special atunci când fixați numărul de clustere!). Altfel spus, EM este un algoritm pentru maximizarea unei funcții de verosimilitate atunci când unele dintre variabilele din modelul dvs. sunt neobservate (adică atunci când aveți variabile latente).
Ați putea întreba în mod corect, dacă încercăm doar să maximizăm o funcție, de ce nu folosim pur și simplu mașinăria existentă pentru maximizarea unei funcții. Ei bine, dacă încercați să o maximizați luând derivate și punându-le la zero, descoperiți că, în multe cazuri, condițiile de ordinul întâi nu au o soluție. Există o problemă de tipul „oul și găina” în sensul că, pentru a rezolva parametrii modelului, trebuie să cunoașteți distribuția datelor neobservate; dar distribuția datelor neobservate este o funcție a parametrilor modelului.

Expectația-Maximizare încearcă să ocolească această problemă prin ghicirea iterativă a unei distribuții pentru datele neobservate, apoi estimarea parametrilor modelului prin maximizarea a ceva care este o limită inferioară a funcției de verosimilitate reale și repetarea până la convergență:

Algoritmul de așteptare-maximizare

Începeți cu o ghicire a valorilor parametrilor modelului
Pasul E: Pentru fiecare punct de date care are valori lipsă, utilizați ecuația modelului dumneavoastră pentru a rezolva distribuția datelor lipsă, având în vedere presupunerea actuală a parametrilor modelului și datele observate (rețineți că rezolvați o distribuție pentru fiecare valoare lipsă, nu pentru valoarea așteptată). Acum că avem o distribuție pentru fiecare valoare lipsă, putem calcula așteptarea funcției de verosimilitate în raport cu variabilele neobservate. Dacă presupunerea noastră pentru parametrii modelului a fost corectă, această verosimilitate așteptată va fi verosimilitatea reală a datelor noastre observate; dacă parametrii nu au fost corecți, va fi doar o limită inferioară.
M-step: Acum că avem o funcție de verosimilitate așteptată fără variabile neobservate în ea, maximizați funcția așa cum ați face-o în cazul complet observat, pentru a obține o nouă estimare a parametrilor modelului dumneavoastră.
Repetați până la convergență.

Probleme asociate cu gruparea

Există o serie de probleme cu gruparea. Printre acestea:

tratarea cu un număr mare de dimensiuni și cu un număr mare de elemente de date poate fi problematică din cauza complexității timpului;
eficacitatea metodei depinde de definiția „distanței” (pentru clusterizarea bazată pe distanțe). Dacă nu există o măsură evidentă a distanței, trebuie să o „definim”, ceea ce nu este întotdeauna ușor, mai ales în spații multidimensionale;
rezultatul algoritmului de clusterizare (care în multe cazuri poate fi el însuși arbitrar) poate fi interpretat în diferite moduri.

Aplicații posibile

Agoritmii de clusterizare pot fi aplicați în multe domenii, de exemplu:

Marketing: găsirea unor grupuri de clienți cu un comportament similar, având în vedere o bază de date mare de date despre clienți care conține proprietățile acestora și înregistrările de cumpărare anterioare;
Biologie: clasificarea plantelor și animalelor având în vedere caracteristicile acestora;
Asigurări: identificarea grupurilor de deținători de polițe de asigurare auto cu un cost mediu ridicat al cererilor de despăgubire; identificarea fraudelor;
Studii privind cutremurele: gruparea epicentrelor observate ale cutremurelor pentru a identifica zonele periculoase;
World Wide Web: clasificarea documentelor; gruparea datelor de tip weblog pentru a descoperi grupuri cu modele de acces similare.

Free Press

Învățare nesupravegheată și gruparea datelor

Lasă un răspuns Anulează răspunsul