Complemente de Informatica - Forum Forum Index Complemente de Informatica - Forum
Discutie (libera) despre proiectul la Complemente de Informatica
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Notiuni de baza

 
Post new topic   Reply to topic    Complemente de Informatica - Forum Forum Index -> Clustering
View previous topic :: View next topic  
Author Message
traian.rebedea
Site Admin


Joined: 19 Oct 2006
Posts: 101

PostPosted: Wed Nov 08, 2006 7:24 pm    Post subject: Notiuni de baza Reply with quote

Gruparea datelor este o tehnică de analiză statistică a datelor, folosită cu succes în diverse subdomenii ale inteligenţei artificiale, precum învăţarea automată, minarea datelor, recunoaşterea formelor şi analiza imaginilor. Gruparea este o modalitate de partiţionare a datelor în subseturi – grupuri, clustere – astfel încât datele din fiecare grup să aibă o caracteristică comună. De obicei, gruparea datelor se face în funcţie de proximitatea elementelor de grupat, pentru aceasta folosindu-se o funcţie distanţă.

Gruparea datelor poate fi privită ca o tehnică de generalizare, întrucât datele de intrare sunt împărţite în clase de echivalenţă folosind anumite criterii. Toate elementele ce formează o clasă de echivalenţă moştenesc atributele grupului din care fac parte. Din acest punct de vedere, este evident că gruparea datelor este o metodă de învăţare automată. Întrucât mediul înconjurător oferă numai datele de intrare, fără a avea informaţii despre corectitudinea acţiunilor întreprinse în cadrul procesului de învăţare, gruparea este o metodă de învăţare nesupervizată. Caracteristica acesteia este faptul că mediul înconjurător nu oferă informaţii despre corectitudinea acţiunilor întreprinse. Folosită ca o tehnică de generalizare, gruparea este utilizată într-o gamă variată de domenii unde este nevoie de extragerea informaţiilor utile dintr-un volum foarte mare de date.

Algoritmii de grupare pot fi împărţiţi folosind mai multe criterii. O prima clasificare este în algoritmi divizivi (top-down) şi algoritmi aglomerativi (bottom-up). Procesarea top-down porneşte cu toate datele într-un singur grup, pe care apoi îl rafinează în subgrupuri. Algoritmii aglomerativi, consideră fiecare element ca un grup separat, iar acestea sunt grupate ulterior. În funcţie de rezultatul grupării, avem de a face cu algoritmi ierarhici şi algoritmi de tip centroid („flat”). Algoritmii ierarhici oferă ca rezultat o structură arborescentă ce poate fi vizualizată ca o dendrogramă. Arborii respectivi pot fi binari sau cu număr aleator de succesori.

De asemenea, gruparea poate fi tare („hard”) sau slabă („soft”). Gruparea tare va produce clustere ce nu se întrepătrund, adică fiecare element aparţine unui singur grup. Gruparea slabă asignează fiecărui obiect o probabilitate de a fi membrul unui grup. Algoritmii ierarhici folosesc aproape întotdeauna o grupare tare, numai cei de tip centroid abordând şi gruparea slabă.
Back to top
View user's profile Send private message Send e-mail
traian.rebedea
Site Admin


Joined: 19 Oct 2006
Posts: 101

PostPosted: Sun Nov 19, 2006 2:50 am    Post subject: Algoritmi ierarhici vs algoritmi de tip centroid Reply with quote

Pentru o comparatie intre principalele metode de grupare, urmati link-ul.
Back to top
View user's profile Send private message Send e-mail
ianghelcovici



Joined: 20 Nov 2006
Posts: 3

PostPosted: Tue Dec 26, 2006 12:15 am    Post subject: Reply with quote

Am o mica nelamurire aici...

Eu am ajuns pana in stadiul in care stirile luate de pe diferite RSS-uri sunt prelucrate (scot stop-words si extrag radacinile cuvintelor).... Si, daca am inteles bine, as avea nevoie de o metoda de a vedea cat de "departe" sunt anumite cuvinte.

Quote:
De obicei, gruparea datelor se face în funcţie de proximitatea elementelor de grupat, pentru aceasta folosindu-se o funcţie distanţă.


Cum fac acest lucru ? Eu m-am gandit sa folosesc wordnet dar din pacate api-ul de java nu functioneaza (sau nu am fost eu in stare sa imi dau seama cum sa rulez macar exemplele lor Confused). Sau daca gresesc cu ceva in ce spun, macar sa aflu de pe acum sa nu mai pierd timpul degeaba.

Multumesc,
Ionut Anghelcovici
Back to top
View user's profile Send private message
traian.rebedea
Site Admin


Joined: 19 Oct 2006
Posts: 101

PostPosted: Wed Dec 27, 2006 3:11 am    Post subject: Reply with quote

Pentru clustering este necesara o functie pentru determinarea similaritatii intre obiectele ce sunt supuse procesului de grupare. In cazul de fata, este necesara calcularea similaritatii intre doua stiri diferite.

Pentru aceasta, nu este neaparat necesar sa folositi Wordnet pentru a determina distanta semantica intre cuvinte, ci este suficient sa eliminati cuvintele de stop si sa extrageti radacinile cuvintelor. In plus, puteti folosi un tagger pentru a afla partile de vorbire din cadrul fiecarei stiri si sa folositi numai verbele si substantivele, de exemplu.

In schimb, trebuie sa calculati cat de apropiate sunt stirile intre ele. Privind stirile ca documente text, exista mai multe masuri de similaritate pe care le puteti folosi. Mai multe despre acest capitol, gasiti aici.
Back to top
View user's profile Send private message Send e-mail
ianghelcovici



Joined: 20 Nov 2006
Posts: 3

PostPosted: Wed Dec 27, 2006 3:35 pm    Post subject: Reply with quote

Pai... daca am inteles bine, asta inseamna ca daca am doua stiri care vorbesc despre exact acelasi lucru, dar folosesc sinonime (practic aceeasi stire in care fiecare cuvant este inlocuit de sinonimul lui) vor fi in clustere diferite, nu ?
Back to top
View user's profile Send private message
traian.rebedea
Site Admin


Joined: 19 Oct 2006
Posts: 101

PostPosted: Wed Dec 27, 2006 7:28 pm    Post subject: Reply with quote

Desigur ca utilizarea Wordnet-ului pentru a gasi distanta semantica intre cuvinte, imbunatateste rezultatele gruparii.

In schimb, o alta varianta ar fi sa coborati un pic pragul pentru care stirile sunt incadrate intr-un grup. Acest lucru nu ofera rezultate la fel de bune ca Wordnet-ul, dar grupurile vor fi mai mari. In schimb, exista sanse mai mari de supraaglomerare a grupurilor.

Eu va incurajez sa folositi Wordnet-ul pentru rezultate cat mai bune si note cat mai mari, dar nu e o conditie obligatorie. Se poate face clustering si fara a folosi Wordnet.

Ma intereseaza in acest punct ce algoritm de clustering si de masuri de similaritate veti folosi.
Back to top
View user's profile Send private message Send e-mail
alex_neamtu



Joined: 27 Oct 2006
Posts: 7

PostPosted: Fri Jan 12, 2007 7:10 pm    Post subject: Reply with quote

Am si eu o intrebare... poate e stupida...
Daca aplic stemmerul pe un text mai pot folosi Wordnet? Eu am dat search pe wordnet la "presidenti" radacina lui "presidential" si a dat "Your search did not return any results".
Back to top
View user's profile Send private message Yahoo Messenger
traian.rebedea
Site Admin


Joined: 19 Oct 2006
Posts: 101

PostPosted: Fri Jan 12, 2007 8:50 pm    Post subject: Reply with quote

Stemming-ul se aplica abia dupa etapa de cautare a cuvintelor in Wordnet. Din cate stiu eu, Wordnet face si el un stemming destul de simplu pentru verbe si substantive.

Totusi eu cred ca este bine sa folosesti si stemmerul lui Porter, dupa interogarea Wordnet-ului.
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Complemente de Informatica - Forum Forum Index -> Clustering All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group