Apprendimento non supervisionato - Cronologia

Mirko Tavosanis: Riformulazioni

2025-06-07T09:40:21Z

Riformulazioni

← Versione meno recente		Versione delle 09:40, 7 giu 2025
Riga 1:		Riga 1:
	~~= Apprendimento~~ non supervisionato =		In informatica, l’apprendimento non supervisionato è una forma di apprendimento automatico in cui gli algoritmi analizzano dati non etichettati, ovvero privi di indicazioni esplicite su categorie, classi o risultati attesi.

	L’apprendimento non supervisionato è una forma di apprendimento automatico in cui gli algoritmi analizzano dati non etichettati, ovvero privi di indicazioni esplicite su categorie, classi o risultati attesi.		A differenza dell’apprendimento supervisionato — dove ogni esempio nei dati è associato a una risposta nota (come un’etichetta di classe o un valore numerico) — nell’apprendimento non supervisionato l’algoritmo non riceve alcuna guida su cosa dovrebbe imparare. Il sistema riceve soltanto gli input grezzi e cerca di scoprire, in modo autonomo, schemi, raggruppamenti o relazioni nascoste nei dati. L’obiettivo è individuare strutture latenti che possano descrivere in modo utile l’organizzazione interna dell’insieme di dati.

	A differenza dell’apprendimento supervisionato — dove ogni esempio nei dati è associato a una risposta nota (come un’etichetta di classe o un valore numerico) — nell’apprendimento non supervisionato l’algoritmo non riceve alcuna guida su cosa dovrebbe imparare.

	Il sistema riceve soltanto gli input grezzi e cerca di scoprire, in modo autonomo, schemi, raggruppamenti o relazioni nascoste nei dati. L’obiettivo è individuare strutture latenti che possano descrivere in modo utile l’organizzazione interna dell’insieme di dati.

	== Clustering ==		== Clustering ==

	Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato.		Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato. È una tecnica che mira a raggruppare "oggetti" simili all’interno di un unico gruppo, detto cluster. Ogni cluster è caratterizzato da una massima somiglianza interna e da una minima somiglianza rispetto agli altri cluster, secondo un determinato indice di similarità.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>
	È una tecnica che mira a raggruppare "oggetti" simili all’interno di un unico gruppo, detto cluster. Ogni cluster è caratterizzato da una massima somiglianza interna e da una minima somiglianza rispetto agli altri cluster, secondo un determinato indice di similarità.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>

	Per esempio, si consideri il caso in cui vengano registrati gli spettri di centomila stelle. È possibile identificare, a partire da questi dati, diversi tipi di stelle? E quanti sarebbero, con quali caratteristiche distintive? Termini come “gigante rossa” o “nana bianca” ~~risultano familiari, ma~~ non corrispondono a etichette esplicite presenti in natura: si tratta di categorie costruite a posteriori attraverso un'attività umana di analisi e classificazione. Gli astronomi, infatti, hanno dovuto applicare tecniche di clustering non supervisionato, analizzando le somiglianze negli spettri per raggruppare le stelle in classi omogenee sulla base delle loro proprietà fisiche.<ref>Russell e Norvig, ''Artificial Intelligence. A Modern Approach'', p. 789.</ref>		Per esempio, si consideri il caso in cui vengano registrati gli spettri di centomila stelle. È possibile identificare, a partire da questi dati, diversi tipi di stelle? E quanti sarebbero, con quali caratteristiche distintive? Termini come “gigante rossa” o “nana bianca” non corrispondono a etichette esplicite presenti in natura: si tratta di categorie costruite a posteriori attraverso un'attività umana di analisi e classificazione. Gli astronomi, infatti, hanno dovuto applicare tecniche di clustering non supervisionato, analizzando le somiglianze negli spettri per raggruppare le stelle in classi omogenee sulla base delle loro proprietà fisiche.<ref>Russell e Norvig, ''Artificial Intelligence. A Modern Approach'', p. 789.</ref>

	Tuttavia, quando i dati sono rappresentati in spazi ad alta dimensione, cioè con un numero elevato di caratteristiche (o feature) per ciascun oggetto, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, differenti sottoinsiemi di caratteristiche possono produrre cluster tra loro differenti ma ugualmente coerenti, rendendo ambigua l’interpretazione dei risultati.		Tuttavia, quando i dati sono rappresentati in spazi ad alta dimensione, cioè con un numero elevato di caratteristiche (o feature) per ciascun oggetto, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, differenti sottoinsiemi di caratteristiche possono produrre cluster tra loro differenti ma ugualmente coerenti, rendendo ambigua l’interpretazione dei risultati.
Riga 24:		Riga 19:
	Le misure di validazione si suddividono in due categorie principali:		Le misure di validazione si suddividono in due categorie principali:

	Le misure di validazione esterna si basano su informazioni esterne al dataset (come etichette di classe note) per confrontare la struttura del clustering con una classificazione di riferimento. Esempi comuni sono l’entropia, l’indice Rand e la F-measure.		*Le misure di validazione esterna si basano su informazioni esterne al dataset (come etichette di classe note) per confrontare la struttura del clustering con una classificazione di riferimento. Esempi comuni sono l’entropia, l’indice Rand e la F-measure.

	Le misure di validazione interna valutano invece la bontà del clustering esclusivamente sulla base della distribuzione interna dei dati, senza bisogno di etichette. Un esempio ampiamente utilizzato è l’indice di Silhouette, che misura la compattezza dei cluster e la separazione tra essi.		*Le misure di validazione interna valutano invece la bontà del clustering esclusivamente sulla base della distribuzione interna dei dati, senza bisogno di etichette. Un esempio ampiamente utilizzato è l’indice di Silhouette, che misura la compattezza dei cluster e la separazione tra essi.

	Le misure interne sono particolarmente utili quando non sono disponibili dati etichettati, come accade spesso nei casi reali. Tuttavia, entrambe le famiglie di misure presentano limiti: ad esempio, le etichette possono non riflettere fedelmente la struttura dei dati, o le metriche interne possono risultare sensibili al rumore o alla presenza di sottocluster.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 573.</ref>		Le misure interne sono particolarmente utili quando non sono disponibili dati etichettati, come accade spesso nei casi reali. Tuttavia, entrambe le famiglie di misure presentano limiti: per esempio, le etichette possono non riflettere fedelmente la struttura dei dati, o le metriche interne possono risultare sensibili al rumore o alla presenza di sottocluster.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 573.</ref>

	== Algoritmo K-means ==		== Algoritmo K-means ==
Riga 36:		Riga 31:
	“necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.”		“necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.”

	"condizioni necessarie […] che i quanti e ~~gli~~ intervalli di quantizzazione associati in uno schema di quantizzazione finito ottimale ~~devono soddisfare~~."		"condizioni necessarie […] che devono essere soddisfatti dai quanti e dagli intervalli di quantizzazione a essi associati in uno schema di quantizzazione finito ottimale."

	L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means.<ref>Lloyd, ''Least Squares Quantization in PCM'', p. 129.</ref>		L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means.<ref>Lloyd, ''Least Squares Quantization in PCM'', p. 129.</ref>

	Il termine “K-means” fu introdotto precedentemente da James MacQueen nel 1967, nell’articolo ''Some Methods for Classification and Analysis of Multivariate Observations'', in cui ~~propose~~ una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.		Il termine “K-means” era stato introdotto precedentemente da James MacQueen nel 1967, nell’articolo ''Some Methods for Classification and Analysis of Multivariate Observations'', in cui l'autore proponeva una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.

	K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.<ref>Aggarwal e Reddy, ''Data Clustering'', pp. 73–74.</ref>		K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.<ref>Aggarwal e Reddy, ''Data Clustering'', pp. 73–74.</ref>
Riga 64:		Riga 59:
	5: Fino a che non viene soddisfatto un criterio di convergenza		5: Fino a che non viene soddisfatto un criterio di convergenza
	</pre><ref>Aggarwal e Reddy, ''Data Clustering'', p. 89.</ref>		</pre><ref>Aggarwal e Reddy, ''Data Clustering'', p. 89.</ref>


	In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 90.</ref>		In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 90.</ref>
Riga 72:		Riga 66:
	* Richiede di specificare a priori il numero k di cluster.		* Richiede di specificare a priori il numero k di cluster.

	* Presuppone che i cluster abbiano forma sferica e dimensione simile (non adatto a cluster non convessi o con densità variabile).		* Presuppone che i cluster abbiano forma sferica e dimensione simile (non è quindi adatto a cluster non convessi o con densità variabile).

	* È sensibile all’inizializzazione: scelte diverse dei centroidi iniziali possono portare a soluzioni differenti.		* È sensibile all’inizializzazione: scelte diverse dei centroidi iniziali possono portare a soluzioni differenti.
Riga 86:		Riga 80:
	L’algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987, nel volume ''Finding Groups in Data: An Introduction to Cluster Analysis'', come alternativa robusta al K-means. A differenza di quest’ultimo, che utilizza la media aritmetica dei punti come centroide, il K-medoids rappresenta ciascun cluster con un oggetto reale del dataset, selezionato in modo da minimizzare la dissimilarità media all’interno del gruppo.		L’algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987, nel volume ''Finding Groups in Data: An Introduction to Cluster Analysis'', come alternativa robusta al K-means. A differenza di quest’ultimo, che utilizza la media aritmetica dei punti come centroide, il K-medoids rappresenta ciascun cluster con un oggetto reale del dataset, selezionato in modo da minimizzare la dissimilarità media all’interno del gruppo.

	“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”		“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids'', p. 1.</ref>
	<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids'', p. 1.</ref>

	"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."		"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."
Riga 140:		Riga 133:
	== Bibliografia ==		== Bibliografia ==

	Russell, S. J., & Norvig, P. (2022). ''Artificial Intelligence. A Modern Approach'', Ed. Pearson.		*Russell, S. J., & Norvig, P. (2022). ''Artificial Intelligence. A Modern Approach'', Ed. Pearson.

	Charu C. Aggarwal, Chandan K. Reddy (2014). ''Data Clustering: Algorithms and Applications'', CRC Press.		*Charu C. Aggarwal, Chandan K. Reddy (2014). ''Data Clustering: Algorithms and Applications'', CRC Press.

	Lloyd, S. P. (1982). ''Least Squares Quantization in PCM.'' IEEE Transactions on Information Theory, 28(2).		*Lloyd, S. P. (1982). ''Least Squares Quantization in PCM.'' IEEE Transactions on Information Theory, 28(2).

	Kaufman, L., & Rousseeuw, P. J. (1987). ''Clustering by means of medoids.''		*Kaufman, L., & Rousseeuw, P. J. (1987). ''Clustering by means of medoids.''

660903: /* Algoritmo K-medoids */

2025-06-01T10:40:35Z

Algoritmo K-medoids

← Versione meno recente		Versione delle 10:40, 1 giu 2025
Riga 87:		Riga 87:

	“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”		“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”
	<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids''.</ref>		<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids'', p. 1.</ref>

	"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."		"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."

660903: /* Algoritmo K-medoids */

2025-06-01T10:38:44Z

Algoritmo K-medoids

← Versione meno recente		Versione delle 10:38, 1 giu 2025
Riga 87:		Riga 87:

	“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”		“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”
	<ref>Kaufman~~, L., &~~ Rousseeuw, ~~P. J. (1987).~~ Clustering by ~~means~~ of ~~medoids~~. </ref>		<ref>Kaufman e Rousseeuw, ''Clustering by Means of Medoids''.</ref>

	"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."		"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."

	K-medoids è il nome del metodo generale di clustering basato sui medoidi. L’algoritmo più noto per implementarlo è PAM (Partitioning Around Medoids), che fornisce un procedimento esplicito per trovare i medoidi ottimali. PAM lavora minimizzando una funzione di costo basata sulle dissimilarità tra punti, calcolando per ogni possibile scambio tra un medoide e un punto non-medoide l’impatto sulla qualità del clustering.<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 93. </ref>		K-medoids è il nome del metodo generale di clustering basato sui medoidi. L’algoritmo più noto per implementarlo è PAM (Partitioning Around Medoids), che fornisce un procedimento esplicito per trovare i medoidi ottimali. PAM lavora minimizzando una funzione di costo basata sulle dissimilarità tra punti, calcolando per ogni possibile scambio tra un medoide e un punto non-medoide l’impatto sulla qualità del clustering.<<ref>Aggarwal e Reddy, ''Data Clustering'', p. 93.</ref>

	Dal punto di vista formale, dato un insieme di dati X = {x₁, x₂, ..., xₙ}, si cerca un insieme di medoidi M = {m₁, ..., mₖ} ⊆ X che minimizzi la seguente funzione obiettivo:		Dal punto di vista formale, dato un insieme di dati X = {x₁, x₂, ..., xₙ}, si cerca un insieme di medoidi M = {m₁, ..., mₖ} ⊆ X che minimizzi la seguente funzione obiettivo:
Riga 115:		Riga 115:
	7: fino alla convergenza.		7: fino alla convergenza.
	</pre>		</pre>
	<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 94.</ref>		<ref>Aggarwal e Reddy, ''Data Clustering'', p. 94.</ref>

	Si inizia con la selezione casuale di k medoidi, quindi assegna ciascun punto al medoide più vicino. In seguito, valuta iterativamente se la sostituzione di un medoide con un altro punto del dataset riduce il costo complessivo; in tal caso, la sostituzione viene effettuata. Il processo continua fino a stabilizzazione.<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 94.</ref>
			Si inizia con la selezione casuale di k medoidi, quindi assegna ciascun punto al medoide più vicino. In seguito, valuta iterativamente se la sostituzione di un medoide con un altro punto del dataset riduce il costo complessivo; in tal caso, la sostituzione viene effettuata. Il processo continua fino a stabilizzazione.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 94.</ref>

	Rispetto a K-means, K-medoids presenta una maggiore robustezza e può operare con qualsiasi metrica di distanza, anche non euclidea. Tuttavia, ciò avviene a scapito della complessità computazionale, che risulta più elevata, specialmente su dataset di grandi dimensioni.		Rispetto a K-means, K-medoids presenta una maggiore robustezza e può operare con qualsiasi metrica di distanza, anche non euclidea. Tuttavia, ciò avviene a scapito della complessità computazionale, che risulta più elevata, specialmente su dataset di grandi dimensioni.

660903: /* Algoritmo K-means */

2025-06-01T10:35:58Z

Algoritmo K-means

660903: /* Validazione del clustering */

2025-06-01T10:34:01Z

Validazione del clustering

← Versione meno recente		Versione delle 10:34, 1 giu 2025
Riga 18:		Riga 18:
	Per questi motivi, ovvero l’elevato costo computazionale e la variabilità dei risultati dovuta all’alta dimensionalità, si rende necessario l’impiego di tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre l’impatto negativo della dimensionalità elevata e migliorare la qualità dei gruppi individuati.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>		Per questi motivi, ovvero l’elevato costo computazionale e la variabilità dei risultati dovuta all’alta dimensionalità, si rende necessario l’impiego di tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre l’impatto negativo della dimensionalità elevata e migliorare la qualità dei gruppi individuati.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>

	==Validazione del clustering==		== Validazione del clustering ==

	Poiché il clustering è un compito non supervisionato, risulta fondamentale disporre di misure di validazione per valutare la qualità delle partizioni ottenute. Senza tali strumenti, sarebbe difficile stabilire se i gruppi trovati riflettano realmente una struttura coerente nei dati.<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 572. </ref>		Poiché il clustering è un compito non supervisionato, risulta fondamentale disporre di misure di validazione per valutare la qualità delle partizioni ottenute. Senza tali strumenti, sarebbe difficile stabilire se i gruppi trovati riflettano realmente una struttura coerente nei dati.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 572.</ref>

	Le misure di validazione si suddividono in due categorie principali:		Le misure di validazione si suddividono in due categorie principali:

	* Le misure di validazione esterna si basano su informazioni esterne al dataset (come etichette di classe note) per confrontare la struttura del clustering con una classificazione di riferimento. Esempi comuni sono l’entropia, l’indice Rand e la F-measure.		Le misure di validazione esterna si basano su informazioni esterne al dataset (come etichette di classe note) per confrontare la struttura del clustering con una classificazione di riferimento. Esempi comuni sono l’entropia, l’indice Rand e la F-measure.

	* Le misure di validazione interna valutano invece la bontà del clustering esclusivamente sulla base della distribuzione interna dei dati, senza bisogno di etichette. Un esempio ampiamente utilizzato è l’indice di Silhouette, che misura la compattezza dei cluster e la separazione tra essi.		Le misure di validazione interna valutano invece la bontà del clustering esclusivamente sulla base della distribuzione interna dei dati, senza bisogno di etichette. Un esempio ampiamente utilizzato è l’indice di Silhouette, che misura la compattezza dei cluster e la separazione tra essi.

	Le misure interne sono particolarmente utili quando non sono disponibili dati etichettati, come accade spesso nei casi reali. Tuttavia, entrambe le famiglie di misure presentano limiti: ad esempio, le etichette possono non riflettere fedelmente la struttura dei dati, o le metriche interne possono risultare sensibili al rumore o alla presenza di sottocluster.<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 573. </ref>		Le misure interne sono particolarmente utili quando non sono disponibili dati etichettati, come accade spesso nei casi reali. Tuttavia, entrambe le famiglie di misure presentano limiti: ad esempio, le etichette possono non riflettere fedelmente la struttura dei dati, o le metriche interne possono risultare sensibili al rumore o alla presenza di sottocluster.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 573.</ref>

	== Algoritmo K-means ==		== Algoritmo K-means ==

660903: /* Clustering */

2025-06-01T10:33:02Z

Clustering

← Versione meno recente		Versione delle 10:33, 1 giu 2025
Riga 10:		Riga 10:

	Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato.		Il clustering è uno degli approcci centrali nell'apprendimento non supervisionato.
	È una tecnica che mira a raggruppare "oggetti" simili all’interno di un unico gruppo, detto cluster. Ogni cluster è caratterizzato da una massima somiglianza interna e da una minima somiglianza rispetto agli altri cluster, secondo un determinato indice di similarità.<ref>~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 31.</ref>		È una tecnica che mira a raggruppare "oggetti" simili all’interno di un unico gruppo, detto cluster. Ogni cluster è caratterizzato da una massima somiglianza interna e da una minima somiglianza rispetto agli altri cluster, secondo un determinato indice di similarità.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>

	Per esempio, si consideri il caso in cui vengano registrati gli spettri di centomila stelle. È possibile identificare, a partire da questi dati, diversi tipi di stelle? E quanti sarebbero, con quali caratteristiche distintive? Termini come “gigante rossa” o “nana bianca” risultano familiari, ma non corrispondono a etichette esplicite presenti in natura: si tratta di categorie costruite a posteriori attraverso un'attività umana di analisi e classificazione. Gli astronomi, infatti, hanno dovuto applicare tecniche di clustering non supervisionato, analizzando le somiglianze negli spettri per raggruppare le stelle in classi omogenee sulla base delle loro proprietà fisiche.<ref>Russell~~, S. J., &~~ Norvig, ~~P. (2022).~~ Artificial Intelligence. A Modern Approach~~, Ed. Pearson~~, p. 789.</ref>		Per esempio, si consideri il caso in cui vengano registrati gli spettri di centomila stelle. È possibile identificare, a partire da questi dati, diversi tipi di stelle? E quanti sarebbero, con quali caratteristiche distintive? Termini come “gigante rossa” o “nana bianca” risultano familiari, ma non corrispondono a etichette esplicite presenti in natura: si tratta di categorie costruite a posteriori attraverso un'attività umana di analisi e classificazione. Gli astronomi, infatti, hanno dovuto applicare tecniche di clustering non supervisionato, analizzando le somiglianze negli spettri per raggruppare le stelle in classi omogenee sulla base delle loro proprietà fisiche.<ref>Russell e Norvig, ''Artificial Intelligence. A Modern Approach'', p. 789.</ref>

	Tuttavia, quando i dati sono rappresentati in spazi ad alta dimensione, cioè con un numero elevato di caratteristiche (o feature) per ciascun oggetto, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, differenti sottoinsiemi di caratteristiche possono produrre cluster tra loro differenti ma ugualmente coerenti, rendendo ambigua l’interpretazione dei risultati.		Tuttavia, quando i dati sono rappresentati in spazi ad alta dimensione, cioè con un numero elevato di caratteristiche (o feature) per ciascun oggetto, l’individuazione di tali gruppi diventa computazionalmente onerosa e può compromettere la qualità dell’apprendimento. Inoltre, differenti sottoinsiemi di caratteristiche possono produrre cluster tra loro differenti ma ugualmente coerenti, rendendo ambigua l’interpretazione dei risultati.

	Per questi motivi, ovvero l’elevato costo computazionale e la variabilità dei risultati dovuta all’alta dimensionalità, si rende necessario l’impiego di tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre l’impatto negativo della dimensionalità elevata e migliorare la qualità dei gruppi individuati.<ref>~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. 31.</ref>		Per questi motivi, ovvero l’elevato costo computazionale e la variabilità dei risultati dovuta all’alta dimensionalità, si rende necessario l’impiego di tecniche di selezione delle caratteristiche (feature selection) nell’ambito del clustering, al fine di ridurre l’impatto negativo della dimensionalità elevata e migliorare la qualità dei gruppi individuati.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 31.</ref>

	==Validazione del clustering==		==Validazione del clustering==

660903: /* Algoritmo K-means */

2025-06-01T10:27:03Z

Algoritmo K-means

← Versione meno recente		Versione delle 10:27, 1 giu 2025
Riga 48:		Riga 48:
	SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²		SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²

	~~Dove~~: c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ		dove: c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ

	Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.		Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.

660903: /* Algoritmo K-means */

2025-06-01T10:26:38Z

Algoritmo K-means

← Versione meno recente		Versione delle 10:26, 1 giu 2025
Riga 48:		Riga 48:
	SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²		SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²

	Dove c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ		Dove: c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ

	Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.		Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.

660903: /* Algoritmo K-medoids */

2025-06-01T10:25:26Z

Algoritmo K-medoids

← Versione meno recente		Versione delle 10:25, 1 giu 2025
Riga 83:		Riga 83:
	== Algoritmo K-medoids ==		== Algoritmo K-medoids ==

	L’algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987, come alternativa robusta al K-means. A differenza di quest’ultimo, che utilizza la media aritmetica dei punti come centroide, il K-medoids rappresenta ciascun cluster con un oggetto reale del dataset, selezionato in modo da minimizzare la dissimilarità media all’interno del gruppo.		L’algoritmo K-medoids è stato introdotto da Leonard Kaufman e Peter J. Rousseeuw nel 1987, nel volume ''Finding Groups in Data: An Introduction to Cluster Analysis'', come alternativa robusta al K-means. A differenza di quest’ultimo, che utilizza la media aritmetica dei punti come centroide, il K-medoids rappresenta ciascun cluster con un oggetto reale del dataset, selezionato in modo da minimizzare la dissimilarità media all’interno del gruppo.

	“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”		“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”

660903: /* Algoritmo K-medoids */

2025-06-01T10:21:31Z

Algoritmo K-medoids

← Versione meno recente		Versione delle 10:21, 1 giu 2025
Riga 87:		Riga 87:
	“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”		“The model described in this paper is based upon the search for k representative objects, which should represent the various aspects of the structure of the data. In this model the representative object of a cluster is the object for which the average dissimilarity […] to all the objects of the cluster is minimal.”
	<ref>Kaufman, L., & Rousseeuw, P. J. (1987). Clustering by means of medoids. </ref>		<ref>Kaufman, L., & Rousseeuw, P. J. (1987). Clustering by means of medoids. </ref>

			"Il modello descritto in questo articolo si basa sulla ricerca di k oggetti rappresentativi, che dovrebbero riflettere i diversi aspetti della struttura dei dati. In questo modello, l’oggetto rappresentativo di un cluster è quello per cui la dissimilarità media rispetto a tutti gli altri oggetti del cluster è minima."

	K-medoids è il nome del metodo generale di clustering basato sui medoidi. L’algoritmo più noto per implementarlo è PAM (Partitioning Around Medoids), che fornisce un procedimento esplicito per trovare i medoidi ottimali. PAM lavora minimizzando una funzione di costo basata sulle dissimilarità tra punti, calcolando per ogni possibile scambio tra un medoide e un punto non-medoide l’impatto sulla qualità del clustering.<ref> Charu C. Aggarwal, Chandan K. Reddy (2014). Data Clustering: Algorithms and Applications, CRC Press, p. 93. </ref>		K-medoids è il nome del metodo generale di clustering basato sui medoidi. L’algoritmo più noto per implementarlo è PAM (Partitioning Around Medoids), che fornisce un procedimento esplicito per trovare i medoidi ottimali. PAM lavora minimizzando una funzione di costo basata sulle dissimilarità tra punti, calcolando per ogni possibile scambio tra un medoide e un punto non-medoide l’impatto sulla qualità del clustering.<ref> Charu C. Aggarwal, Chandan K. Reddy (2014). Data Clustering: Algorithms and Applications, CRC Press, p. 93. </ref>

← Versione meno recente		Versione delle 10:35, 1 giu 2025
Riga 32:		Riga 32:
	== Algoritmo K-means ==		== Algoritmo K-means ==

	L’algoritmo K-means fu presentato per la prima volta da Stuart P. Lloyd nell’articolo ''Least Squares Quantization in PCM'' (1982). L’autore descrive un metodo iterativo per la quantizzazione vettoriale, oggi riconosciuto come la base computazionale del K-means, e ne espone il principio scrivendo:		L’algoritmo K-means fu presentato per la prima volta da Stuart P. Lloyd nell’articolo ''Least Squares Quantization in PCM'' (1982). L’autore descrive un metodo iterativo per la quantizzazione vettoriale, oggi riconosciuto come la base computazionale del K-means, e ne espone il principio scrivendo:

	“necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.”		“necessary conditions […] that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.”
Riga 38:		Riga 38:
	"condizioni necessarie […] che i quanti e gli intervalli di quantizzazione associati in uno schema di quantizzazione finito ottimale devono soddisfare."		"condizioni necessarie […] che i quanti e gli intervalli di quantizzazione associati in uno schema di quantizzazione finito ottimale devono soddisfare."

	L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means.<ref> Lloyd, ~~S. P. (1982). “Least~~ Squares Quantization in PCM~~.” IEEE Transactions on Information Theory, 28(2)~~, p. 129. </ref>		L’ottimizzazione si basa sul criterio di minimizzare la potenza media del rumore di quantizzazione, concetto che corrisponde alla minimizzazione dell’errore quadratico medio, oggi al centro del metodo K-means.<ref>Lloyd, ''Least Squares Quantization in PCM'', p. 129.</ref>

	Il termine “K-means” fu introdotto precedentemente da James MacQueen nel 1967, nell’articolo ''Some Methods for Classification and Analysis of Multivariate Observations'', in cui propose una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.		Il termine “K-means” fu introdotto precedentemente da James MacQueen nel 1967, nell’articolo ''Some Methods for Classification and Analysis of Multivariate Observations'', in cui propose una versione stocastica dell’algoritmo. Tale formulazione differisce da quella oggi comunemente utilizzata, che è più riconducibile al metodo deterministico descritto da Lloyd.

	K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.<ref> ~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, p. ~~73-74~~. </ref>		K-means è uno degli strumenti più noti e ampiamente utilizzati per l'analisi non supervisionata. Assume che il numero di cluster sia fissato a priori e che ciascun cluster possa essere descritto da un centroide, inteso come media dei punti che lo compongono. L'obiettivo è minimizzare la somma delle distanze quadratiche tra ogni punto del dataset e il centroide del cluster cui viene assegnato.<ref>Aggarwal e Reddy, ''Data Clustering'', pp. 73–74.</ref>

	Dal punto di vista matematico, dato un insieme di dati D = {x₁, x₂, ..., xₙ}, con xᵢ ∈ ℝᵈ, e una partizione in cluster C = {C₁, C₂, ..., C_K}, l’obiettivo è minimizzare la seguente funzione di costo, detta Sum of Squared Errors (SSE):		Dal punto di vista matematico, dato un insieme di dati D = {x₁, x₂, ..., xₙ}, con xᵢ ∈ ℝᵈ, e una partizione in cluster C = {C₁, C₂, ..., C_K}, l’obiettivo è minimizzare la seguente funzione di costo, detta Sum of Squared Errors (SSE):
Riga 48:		Riga 48:
	SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²		SSE(C) = ∑ (da k=1 a K) ∑ (xᵢ ∈ C_k) \|\| xᵢ − c_k \|\|²

	dove: c_k è il centroide del cluster C_k, calcolato come: c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ		dove: c_k è il centroide del cluster C_k, calcolato come:
			c_k = (1 / \|C_k\|) ∑ (xᵢ ∈ C_k) xᵢ

	Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.		Dal punto di vista implementativo, l’algoritmo K-means si basa su una procedura iterativa che alterna due operazioni fondamentali: l’assegnazione dei punti ai centroidi e l’aggiornamento dei centroidi stessi. Queste fasi vengono ripetute fino al raggiungimento della convergenza.
Riga 62:		Riga 63:
	4: Ricalcolare ogni centroide come media dei punti assegnati		4: Ricalcolare ogni centroide come media dei punti assegnati
	5: Fino a che non viene soddisfatto un criterio di convergenza		5: Fino a che non viene soddisfatto un criterio di convergenza
	</pre><ref>~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, pp. 89.</ref>		</pre><ref>Aggarwal e Reddy, ''Data Clustering'', p. 89.</ref>


	In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.<ref>~~Charu C.~~ Aggarwal, ~~Chandan K. Reddy (2014).~~ Data Clustering~~: Algorithms and Applications, CRC Press~~, pp. 90.</ref>		In pratica, il procedimento inizia con l’inizializzazione casuale di K centroidi. Successivamente, ciascun punto viene associato al centroide più vicino secondo la distanza euclidea, e i centroidi vengono aggiornati ricalcolando la media dei punti che sono stati loro assegnati. Questa fase di riassegnazione e aggiornamento continua fino alla convergenza, ovvero fino a quando le assegnazioni non cambiano più in modo significativo.<ref>Aggarwal e Reddy, ''Data Clustering'', p. 90.</ref>

	K-means presenta però alcune limitazioni:		K-means presenta però alcune limitazioni: