Versione delle 08:09, 16 giu 2012 modifica AlessioMela (discussione \| contributi) Utenti autoverificati 16 837 modifiche +Voci correlate ← Differenza precedente		Versione delle 01:27, 24 lug 2012 modifica annulla GnuBotmarcoo (discussione \| contributi) Bot 959 174 modifiche m Bot: Fix tag <math> Differenza successiva →
Riga 7: ==Descrizione formale== Dati N oggetti con ''i'' attributi, modellizzati come vettori in uno spazio vettoriale i-dimensionale, definiamo <math>X={X_1,X_2,\ldots,X_N}\,</math> come insieme degli oggetti. Ricordiamo che si definisce [[Partizione (teoria degli insiemi)\|partizione]] degli oggetti il gruppo di insiemi <math>P={P_1,P_2,\ldots,P_K}\,</math> che soddisfano le seguenti proprietà: <math>\bigcup_1^{K} P_i = X</math> : l'unione di tutti i cluster deve contenere tutti gli oggetti di partenza; <math>\bigcap_1^{K} P_i = \varnothing</math> : ogni oggetto può appartenere ad un solo cluster; *<math>\varnothing \subset P_i \subset X</math> : almeno un oggetto deve appartenere ad un cluster e nessun cluster può contenere tutti gli oggetti. Ovviamente deve valere anche che <math>1 < K < N\,</math>; non avrebbe infatti senso né cercare un solo cluster né avere un numero di cluster pari al numero di oggetti. Una partizione viene rappresentata mediante una matrice <math>U \in \mathbb{N}^{K \times N}\,</math>, il cui generico elemento <math>u_{ij} = {0,1}\,</math> indica l'appartenenza dell'oggetto j al cluster i. Indichiamo quindi con <math>C={C_1,C_2,\ldots,C_K}\,</math> l'insieme dei K centroidi. A questo punto definiamo la funzione obiettivo come: ::<math>V(U,C) = \sum_{i=1}^{K} \sum_{X_j \in P_i} \|\|X_j - C_i \|\|^2 </math> e di questa calcoliamo il minimo seguendo la procedura iterativa vista sopra: # Genera <math>U_v\,</math> e <math>C_v\,</math> casuali # Calcola <math>U_n\,</math> che minimizza <math>V(U,C_v)\,</math> # Calcola <math>C_n\,</math> che minimizza <math>V(U_v,C)\,</math> # Se l'algoritmo converge ci si ferma, altrimenti <math>U_v = U_n , C_v=C_n\,</math> e torna al passo 2 Tipici criteri di convergenza sono i seguenti:

K-means: differenze tra le versioni