Universitatea babeş-bolyai cluj-napoca

2.6. Metoda Fuzzy C-means

Tehnica fuzzy a celor c medii (Fuzzy C-means) este o tehnică de clustering care permite unui element din setul de date să aparțină cu un anumit grad de apartenență, la una sau mai multe grupe. În analiza non-fuzzy, sau hard clustering, informația este divizată în clustere crisp, unde fiecare entitate aparține unui singur cluster.[6] Asocierea unui obiect cu un cluster se face cu ajutorul gradelor de apartenență:

Pentru hard clustering:

Pentru fuzzy clustering:

Metoda fuzzy este folosită frecvent în recunoașterea modelelor și se bazează pe minimizarea următoarei funcții obiectiv:

unde: este mulțimea entităților, fiecare având câte m caracteristici; este mulțimea centroizilor, unde k este numărul de clusteri; orice metrică folosită pentru calculul distanței dintre un element și centroidul unui cluster se notează cu ; m – gradul de fuzzyficare, cu o valoare cuprinsă în intervalul , folosit pentru a controla diferențele dintre gradele de apartenență. Nu există nici o bază teoretică pentru alegerea optimă a valorii lui m, dar de obicei se alege valoarea reprezintă matricea gradelor de apartenență; u_ij este gradul de apartenență al elementului x_i la clusterul j, care trebuie să satisfacă următoarele condiții:

Etapele algoritmului Fuzzy C-means:

1. 
   Inițializarea centroizilor K;
   
2. 
   Calculul elementelor matricei gradelor de apartenență U, care să satisfacă cele două condiții de mai sus, folosind următoarea formulă:
   

unde

3. 
   Calcularea centroizilor Kj folosind formula:
   

4. 
   Repetarea pașilor 2) și 3) până când se ajunge la minimul valorii lui J.
   

Gruparea fuzzy se face printr-un proces iterativ de optimizare, în care se urmărește minimizarea funcției obiectiv, cu actualizarea gradului de apartenență u_ij a elementului la clusterul j. Procesul de grupare se va sfârși când va fi îndeplinită condiția:
unde este criteriul de oprire, iar v – numărul iterațiilor procedeului de optimizare.

Algoritmul poate fi considerat:

AlegeCentroiziiInițiali(K,k);

Câttimp (nu s-a ajuns la valoarea minimă a funcției obiectiv J)

CalculeazăMatriceaGradelorDeApartenență;

Recalculează centroizii;

RecalculeazăFuncțiaObiectiv;

Sf-câttimp

Astfel, entitățile din setul de date de intrare sunt atașate unui cluster prin intermediul valorii medii corespunzătoare funcției de apartenență. Din această cauză se folosește matricea U, a cărei elemente sunt numere între 0 și 1, care reprezintă gradul de apartenență dintre o entitate și un anumit centroid. [6]

2.7. Mãsuri de calitate

O etapă importantă o reprezintă evaluarea algoritmilor de clustering. Așadar, fiecare algoritm de clustering aplicat pe același set de date va grupa datele în funcție de metrica folosită, ceea ce face ca analiza eficienței algoritmilor să fie foarte dificilă. În general, rata eficienţei algoritmilor de clustering este calculată în funcţie de omogenitatea clusterilor rezultaţi şi gradul de diferenţiere dintre aceştia, determinând diferite distanțe între entități și clusteri. Astfel, se pot aplica două măsuri de calitate sau de validare: externe și interne. [13]

Măsurile externe de calitate permit analiza rezultatelor algoritmilor, însă necesită existența unor seturi de date etichetate încă dinaintea fazei de testare. Acestea pot fi: precizia de a plasa o entitate în grupul corespunzător, acuratețea cu care entitățile sunt grupate corect în cadrul clusterilor sau entropia care indică omogenitatea unui cluster. În practică, măsurile externe sunt greu de determinat deoarece acestea necesită existența unor date etichetate dinainte și compararea rezultatelor clusteringului cu informațiile cunoscute.

Câteva măsuri externe de calitate sunt:

• 
  Acuratețea: reprezintă procentajul de entități grupate corect în clusteri.
  
• 
  Entropia: indică omogenitatea unui cluster. O entropie scăzută îndică o omogenitate mare, ceea ce este de dorit, și invers. Această măsură poate lua valori din intervalul [0,1]. Astfel, un cluster cu un singur element va avea valoarea entropiei egală cu 0. Valoarea entropiei unui cluster va fi 1 dacă el conține un număr egal de elemente din fiecare cluster al soluției reale. Formula pentru calculul entropiei în cadrul unui cluster este:
  

unde pr_ij reprezintă raportul dintre numărul de elemente din clusterul j conținute în clusterul i.

Calculul entropiei pentru soluția de clustering a unui set de date cu k grupuri este dat de formula:
unde nr_i este numărul de elemente determinate pentru clusterul C_i, iar nr – numărul real de elemente din acel cluster.

• 
  Precizia: este probabilitatea ca o entitate să fie plasată în clusterul corespunzător. [13]
  

Măsurile interne de calitate nu necesită cunoașterea dinainte a clusterilor de care ar aparține entitățile grupate. Dintre acestea amintim: distanța intra-cluster (compactitatea), distanța inter-cluster (separabilitatea), echilibrul dintre clusterii formați (din puctul de vedere al numărului de entități asignate). Deoarece acestea uneori pot fi relativ greu de determinat, și în special pot duce la rezultate neconcludente, s-a introdus utilizarea diferitelor tipuri de indecși, dintre care cei mai cunoscuți sunt: indexul Davies-Bouldin[4] (caută echilibrul între compactitate și separabilitate, astfel încât gradul de împrăștiere a datelor în cadrul spațiului de căutare să fie mic), indexul Dunn (încearcă să maximizeze distanța inter-cluster și să o minimizeze pe cea intra-cluster) care însă în anumite cazuri pot ignora tendințele majoritare de grupare a entităților în clusteri, descoperind doar entități izolate care pot schimba uneori radical măsura de calitate generală.[m01 de la radu]

Câteva măsuri interne de calitate sunt:

• 
  Compactitatea: măsoară cât de compacte sunt entitățile din cadrul unui cluster:
  

unde C este clusterul curent, nr_C reprezintă numărul de entități din cluster, K este centroidul lui C și x_i o entitate. Astfel, această măsură exprimă gradul de similaritate dintre elementelor unui cluster. Compactitatea se mai numește și distanță intra-cluster și poate lua valori din intervalul , cu cât valoarea sa e mai mică, cu atât rezultatul este mai bun.

• 
  Separabilitatea: măsoară disimilaritatea dintre clusterii creați și mai este cunoscută și sub numele de distanță inter-cluster:
  

unde se măsoară dinstanța dintre centroizi. Astfel, pentru fiecare cluster se determină clusterul cel mai apropiat. Pe baza acestei metrici se caută clusterii care vor maximiza această valoare, așadar se vor căuta clusterii cei mai distanțați.

• 
  Echilibrul: măsoară cât de echilibrați sunt clusterii formați din puctul de vedere al numărului de entități componente. Formula folosită este:
  

cu domeniul de valori , iar valoarea maximă 1 se obține atunci când toți clusterii au același număr de elemente, iar o valoare scăzută, apropiată de 0 se poate obține atunci când numărul de entități ale clusterilor diferă foarte mult. Chiar dacă această metrică este considerată o măsură a calității, pe date reale este puțin probabil ca aceasta să fie relevantă, dat fiind faptul că poate fi un fapt normal ca numărul de elemente dintr-un cluster să difere mult.

• 
  Indexul Davies-Bouldin: este o măsură care combină primele două metrici. Considerăm dispersia:
  

Indexul Davies-Bouldin va fi:

unde este distanța dintre cei doi clusteri, care poate fi considerată la alegere, de exemplu .

Acest index caută echilibrul între compactitate și separabilitate, astfel încât gradul de împrăștiere a datelor în cadrul spațiului de căutare să fie mic, căutându-se minimizarea lui.

• 
  Indexul Dunn: se bazează pe ideea de a identifica seturi de clusteri, care sunt compacte şi bine separate. Scopul principal al măsurii este de a maximiza distantele inter-cluster şi a minimiza distantele intra-cluster:
  

Valoarea acestui index poate aparține intervalului și cu cât este mai mare, cu atât calitatea rezultatului este mai bună.

Chiar dacă aceste tipuri de măsuri interne ale calității se folosesc destul de mult, acest domeniu de cercetare este încă la început, datorită faptului că rezultatele pot varia destul de mult. În anumite cazuri, aceste metrici pot ignora tendințele majoritare de grupare a entităților în clusteri, descoperind doar entități izolate care pot schimba uneori radical măsura de calitate generală. [6][13]

3. Aplicații ale Analizei Cluster

3.1. Domenii de aplicații

Analiza cluster este folosită în numeroase domenii academice, precum bilogia (în cadrul grupării speciilor de animale), lingvistica (gruparea dialectelor), medicină, neuroștiințe, segmentarea pieței, marketing, sisteme de recomandare sau cercetare educațională.

3.1.1. Electroenergetică

3.1.2. Segmentarea pieței

Segmentarea pieței reprezintă cea mai importantă aplicație a analizei cluster. Răspunsul diverșilor stimuli de marketing, precum prețul, campaniile promoționale, atributele produselor sau poziționarea acestora, de către anumite tipuri de grupuri este o problemă principală pentru analiști. Abordarea acesteia începe cu realizarea unui set de variabile care sunt relevante pentru produsele în cauză, cum ar fi: diverse beneficii, preferințe pentru mărci, iar apoi extragerea unui eșantion reprezentativ de consumatori. În cazul în care numărul de variabile este ridicat, pot fi aplicate tehnici de analiză factorială în vederea reducerii lor. În urma analizei se pot obține grupuri care pot fi comparate cu variabile care descriu consumatorii sau cu alte variabile folosite la grupare, putând oferi analiștilor de marketing anumite modele pentru a ajunge la piețele țintă. [14]

3.1.3. Probleme de recunoaștere de imagini

Recunoaşterea şi regăsirea anumitor tipuri de imagini poate fi crucială în anumite domenii. De exemplu, în medicină, cu ajutorul radiografiilor, a unor capturi de imagini din tomografii sau din ecografii, care se află în fişele personale ale pacienţilor unui spital trebuie uneori selectaţi toţi aceia care suferă de o anumită boală care poate fi determinată în urma analizei imaginii respective.

De asemenea, în domeniul militar şi cel al siguranţei în aeroporturi recunoaşterea imaginilor poate fi extrem de importantă pentru supravegherea şi regăsirea în baza de date a unor persoane, echipamente, arme, etc.

În ultimii ani, programele de clustering au fost folosite intensiv în astronomie. Astfel, dupa ce imaginile au fost preluate cu ajutorul unor telescoape performante, în funcţie de anumite caracteristici, corpurile cereşti au putut fi clasificate cu acurateţe mărită.

Robotica este unul dintre domeniile în care aceste sisteme sunt foarte des folosite. Spre exemplu, un robot care asamblează piese trebuie să le poată identifica. Toate aceasta se pot realiza cu ajutorul programelor specializate, care practic indexează bazele de date cu conţinut multimedia.

3.1.4. Medicină

3.1.5. Web mining

3.2. Îmbunătățiri aduse tehnicilor de clustering. Hibridizare.

Problemele de clustering apar în tot mai multe domenii și de aceea se încearcă eficientizarea acestora prin diferite metode. Căteva direcții noi de cercetare sunt următoarele: combinarea agenților inteligenți cu tehnici de clustering, hibridizarea tehnicilor de clustering,

3.2.1. Clustering și agenți inteligenți în web mining

În probleme de data mining s-au încercat combinarea unor algoritmi cunoscuți de clustering cu agenți inteligenți. La sistemele de analiză Web s-a observat faptul că din cauza analizei în timp real, analizatorul web nu reușește performanțe deosebite în cazul în care acesta trebuie atât să realizeze analiza conținutului folosind clustering, cât și să analizeze continuu rezultatele obținute. Din acest motiv un agent inteligent a fost însărcinat să grupeze conținutul analizat cu ajutorul unui algoritm de clustering. În acest caz, sistemul realizat este unul multi-agent, compus din doi agenți agenți, unul care realizează clustering propriu-zis și altul care evaluează performanțele algoritmului de clustering aplicat. Agenții pot schimba informații despre clusteri între ei, iar întregul sistem pote determina numărul de clusteri existenți. Algoritmul de clustering folosit este K-Means, însă sunt folosite și rețele Kohonen – hărți cu auto-organizare (Self Organizing Maps - SOM) și Principal Component Analysis (PCA). Pentru a testa această aplicație s-au folosit setul de date Iris din UCI Repository [15], și s-au aplicat pe rând PCA, SOM și apoi K-Means, ajungându-se la o performanță în recunoașterea clusterilor de 99.48%. [16]

3.2.2. Clustering folosit în sisteme predictive

Pentru a elimina limitările anumitor tehnici de clustering, cum ar fi Fuzzy C-Means, s-a încercat dezvoltarea unor algoritmi hibrizi. Astfel, s-a combinat Fuzzy C-Means, care e un algoritm rapid, însă e sensibil la datele de inițializare, la fel ca si K-Means, cu Rețele Neuronale multistrat și cu Algoritmi Genetici. Modelul rezultat, Genetic Fuzzy Neural Network (GFNN) a fost folosit pentru crearea unui model utilizat la predicția falimentului unor instituții și investitori, pe baza analizelor financiare. Rata de predicție corectă a sistemului bazat pe algoritmul hibrid fiind de 98.33%.[17]

3.2.3. Clustering în cadrul GIS (Geographical Information System)

Sistemul GIS (Geographical Information System) a fost introdus în anul 1960 și este utilizat la studiul căilor de comunicație, planificarea dezvoltării managementului localităților, managementul datelor spațiale, a rețelelor publice de apă, canalizare, electricitate, dar putând fi folosit și la localizarea și monitorizarea vehiculelor publice. Conceptual, GIS reprezintă o stivă de hărți, în cadrul căreia fiecare strat este corelat cu celelalte. Acest tip de sisteme dețin baze de date hibride, unde informațiile sunt atât atribute de diverse tipuri, cât și informații spațiale.

Bazele de date folosite în cadrul GIS sunt complexe și foarte mari din perspectiva numărului de obiecte existente, atribute sau caracteristici spațiale. Un astfel de sistem este conceput în așa fel încât să poată accesa o bază de date sub formă de hărți, care pot fi suprapuse, combinate sau analizate, fiind caracterizate de obiecte geometrice. Legăturile dintre obiectele care sunt situate în același strat sau în straturi diferite pot fi extrem de complexe mai ales datorită atributelor care implică proprietăți geometrice, topologice sau semantice. Este imposibil ca un utilizator să poată identifica anumite informații greu de descoperit în interiorul unei astfel de baze de date din cauza complexității acesteia, iar acesta este motivul pentru care au fost introduse metode de clustering pentru identificarea unor atribute necunoscute anterior, în scopul generalizării acestora. Acest tip de abordare este relativ nou, introdus mai întâi de Jiang în lucrarea [18].

Jiang a utilizat tehnici de clustering pentru identificarea caracteristicilor cartografice necesare întocmirii unui sistem GIS. Atributele elementelor inițiale au fost coordonatele geometrice x și y, astfel încât procesul de generalizarea a implicat doar proprietățile geometrice ale elementelor. Baza de date a cuprins 179 de obiecte, iar pentru determinarea caracteristicilor necesare pentru procesul de generalizare s-au folosit două tehnici de clustering: K-means și clustering ierarhic. În urma aplicării metodei K-means au fost obținute 100 de grupuri, iar modelele rezultate în urma procesului de determinare de caracteristici generale au respectat poziționarea spațială a obiectelor din baza de date. În urma aplicării clusteringului ierarhic, pentru baza de date inițială s-a observat că cea mai bună metodă metodă a fost cea a distanței medii (average linkage), iar cea mai bună măsura pentru a reflecta dinstanța dintre obiecte a fost distanța Euclidiană. [11]

Prin exemplele prezentate s-a demonstrat că tehnicile de clustering pot constitui un suport important în diferite procese.

4. Prezentarea aplicației

4.1. Motivație

Aplicația este concepută cu scopul de a realiza o analiză comparativă între diferite tipuri de clustering, în vederea observării de diferențe între rezultatele și performanțele generale obținute de fiecare algoritm în parte. Aceasta dorește să surprindă motivațiile care stau la baza apariției noilor tendințe din Inteligența Artificială în general și la unii algoritmi de clustering în particular.

În cadrul 2-ClustSystem au fost implementați doi algoritmi cunoscuți din clustering, Fuzzy C-means și K-means, precum și diferite măsuri de performanță a rezultatelor obținute în urma aplicării de algoritmi de clustering, precum: distanța inter-cluster, distanța intra-cluster, indexul Dunn, indexul Davies-Bouldin. Totodată, aplicația oferă facilitatea de a observa modul aproximativ de dispoziție a datelor în clusteri prin intermediul unui grafic de dispersie.

Concluzii

Bibliografie

1. Mitchell, Tom. Machine Learning. Boston : McGraw-Hill Science/Engineering/Math, 1997.

2. MacKay, David J. C. Information Theory, Inference and Learning Algorithms. Cambridge : Cambridge University Press, 2003.

3. Nilsson, Nils J. Introduction to Machine Learning: an early draft of a proposed textbook. Stanford : s.n., 1998.

4. Russel, Stuart J. și Norvig, Peter. Artificiall Inteligence A Modern Approach. New Jersey : Alan Apt, 1995.

5. Analyzing Animated Movie Contents for Automatic Video Indexing. Ionescu, B., și alții. 2011, Machine Learning Techniques for Adaptive Multimedia Retrieval: Technologies Applications and Perspectives.

6. Gan, G., Ma, C. și Wu, J. Data Clustering: Theory, Algorithms and Applications. Philadelphia : SIAM, 2007.

7. Petrescu, Mary. Clustering Ierarhic. Craiova : Else, 2010.

8. Tryon, R. C. Cluster Analysis. Ann Arbor : MI: Edwards Brothers, 1939.

9. Hapgood, Adrian A. Intelligent Systems for Engineers and Scientists. Boca Raton, Florida : CRC Press LLC, 2000.

10. Pop, Horia F. Sisteme inteligente în probleme de clasificare. Cluj-Napoca : Mediamira, 2004.

11. Cârțină, Gheorghe, Grigoraș, Gheorghe și Bobric, Elena-Crenguța. Tehnici de clustering în modelarea fuzzy. Aplicații în Electroenergetică. Iași : Venus, 2005.

12. SciKits. 4.2. Clustering - scikits.learn v0.8 documentation. scikit-leanr: machine learning in Python. [Interactiv] 1 January 2011. [Citat: 23 May 2012.] http://scikit-learn.org/0.8/modules/clustering.html.

13. Ongoing Research in Document Classification at the "Lucian Blaga" University of Sibiu. Crețulescu, R. G. Delft : s.n., 2011. the 5th International Symposium on Intelligent Distributed Computing IDC2011.

14. Muntean, C. Spss Analiza Cluster. Scribd.com. [Interactiv] 27 January 2011. http://ro.scribd.com/doc/47654684/Spss-Analiza-Cluster#outer_page_4.

15. Frank, A și Asuncion, A. UCI Machine Learning Repository: Iris Data Set. UCI Machine Learning Repository. [Interactiv] 2010. http://archive.ics.uci.edu/ml.

16. Park, Jung-Eun și Oh, Kyung-Whan. Multi-Agent Systems for Intelligent Clustering. s.l. : World Academy of Science, Engineering and Technology, 2005.

17. Martin, A., și alții. A hybrid model for bankruptcy prediction using Genetic Algorithm, Fuzzy C-Means and MARS. International Journal on Soft Computing ( IJSC ). Bhangalore : s.n., 2011.

18. Jiang, B. Spatial Clustering forMining Knowledge in Support of Generalization Processes in GIS. Leicester : ICA, 2004.