Nell’articolo precedente abbiamo parlato di comportamento sorprendente dei dati in dimensioni superiori. Abbiamo scoperto che il volume tende ad accumularsi negli angoli degli spazi in un modo strano, e per indagare abbiamo simulato un’ipersfera inscritta all’interno di un ipercubo, osservando un’interessante diminuzione nel rapporto dei volumi man mano che le dimensioni crescono. Esempi che hanno dimostrato i vantaggi del pensiero multidimensionale sono stati l’esperimento DVD-paper e il trucco del kernel nelle macchine a vettori di supporto (SVM).
Oggi esamineremo alcuni degli aspetti difficili dei dati ad alta dimensionalità, definiti maledizione della dimensionalità. Il nostro obiettivo è avere una comprensione intuitiva di questo concetto e delle sue implicazioni pratiche. Il diagramma seguente illustra come è strutturato il nostro articolo.
Comprendere la maledizione della dimensionalità
“Maledizione della dimensionalità” è un termine usato per la prima volta da Richard E. Bellman negli anni ’60. È iniziato come un’idea di Bellman dall’ottimizzazione dinamica e si è rivelato un concetto fondamentale per comprendere la complessità negli spazi ad alta dimensione.
Bene, ma cos’è la “maledizione della dimensionalità”?
Al centro ci sono le difficoltà e le caratteristiche uniche che si affrontano quando si lavora con i dati in spazi ad alta dimensione (nel nostro caso questo si riferisce all’avere molte caratteristiche, colonne o attributi nei set di dati). Questi spazi vanno ben oltre la nostra esperienza della vita quotidiana nello spazio tridimensionale.
Quando aumentiamo il numero di dimensioni su un set di dati, il volume che occupa si espande in modo esponenziale. Ciò potrebbe inizialmente sembrare un vantaggio: più spazio potrebbe significare più dati e probabilmente più approfondimenti? Tuttavia, non è così, perché avere molte dimensioni comporta una serie di sfide che cambiano il modo in cui dobbiamo affrontare e comprendere questi dati ad alta dimensione.
Il passaggio dai dati a bassa dimensionalità a quelli ad alta dimensionalità deve affrontare diverse sfide difficili. Ce ne sono due, che si distinguono perché hanno gli effetti più significativi: 1) scarsità di dati; 2) il problema con la metrica della distanza. Ciascuno di essi rende l’analisi nelle dimensioni superiori ancora più complessa.
Sparsità dei dati: isole in un oceano di vuoto
La scarsità di dati in spazi altamente dimensionali è come poche piccole isole perse in un vasto oceano. Quando la dimensionalità aumenta, i punti dati che erano vicini tra loro nelle dimensioni inferiori diventano sempre più separati. Ciò è dovuto al fatto che la quantità di spazio si espande esponenzialmente con ogni nuova aggiunta di un’altra dimensione. Immagina solo che un cubo diventi un ipercubo; i suoi angoli si allontanano dal suo centro e lo rendono più vuoto all’interno. Questo vuoto crescente è ciò che chiamiamo scarsità di dati.
Molte tecniche di analisi dei dati lottano con la scarsità. Ad esempio, molti algoritmi di clustering dipendono da punti dati situati molto vicini per formare cluster significativi. Tuttavia, quando i punti dati diventano troppo dispersi, questi algoritmi incontrano difficoltà.
Problemi metrici della distanza: quando la prossimità perde significato
Negli spazi ad alta dimensione, la misurazione della distanza incontra sfide significative. Metriche come le distanze euclidee o di Manhattan, utili per misurare la prossimità tra punti dati in dimensioni inferiori, perdono la loro efficacia. In questi spazi espansi le distanze cominciano a convergere. Ciò significa che la maggior parte delle coppie di punti diventano quasi equidistanti tra loro e da un punto di riferimento. Questa convergenza rende più difficile distinguere tra vicini vicini e lontani.
In attività come la classificazione, in cui le misurazioni della distanza sono cruciali per classificare nuovi punti dati, queste metriche diventano meno efficaci. Di conseguenza, le prestazioni dell’algoritmo diminuiscono, portando a previsioni e analisi meno accurate.
Per comprendere meglio come cambia il comportamento a distanza nelle dimensioni superiori, eseguiamo una semplice simulazione. Genereremo punti casuali sia negli spazi a bassa che ad alta dimensione. Ciò ci consentirà di osservare e confrontare la distribuzione delle distanze, mostrandoci come queste distanze si evolvono man mano che ci spostiamo verso dimensioni superiori.
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdistdef generate_points(dimensions, num_points, range_min, range_max):
return np.random.uniform(range_min, range_max, (num_points, dimensions))
def calculate_pairwise_distances(points):
distances = np.sqrt(((points(:, np.newaxis, :) - points(np.newaxis, :, :)) ** 2).sum(axis=-1))
np.fill_diagonal(distances, np.nan) # Ignore self-distances by setting them to NaN
return distances
def calculate_distances_from_reference(points, reference_point):
distances = np.sqrt(((points - reference_point) ** 2).sum(axis=1))
return distances
def calculate_stats_for_dimensions(num_points, dimensions_range, range_min, range_max):
means_pairwise = ()
stds_pairwise = ()
means_ref = ()
stds_ref = ()
for dim in dimensions_range:
points = generate_points(dim, num_points, range_min, range_max)
pairwise_distances = calculate_pairwise_distances(points)
reference_point = generate_points(dim, 1, range_min, range_max)
distances_from_ref = calculate_distances_from_reference(points, reference_point)
means_pairwise.append(np.nanmean(pairwise_distances))
stds_pairwise.append(np.nanstd(pairwise_distances))
means_ref.append(np.mean(distances_from_ref))
stds_ref.append(np.std(distances_from_ref))
return means_pairwise, stds_pairwise, means_ref, stds_ref
def plot_histograms_and_stats(num_points, dimensions_range, range_min, range_max):
fig, axs = plt.subplots(2, 3, figsize=(12, 7), tight_layout=True)
# Plotting histograms for 3D and 100D
for i, dim in enumerate((3, 100)):
points = generate_points(dim, num_points, range_min, range_max)
pairwise_distances = calculate_pairwise_distances(points)
reference_point = generate_points(dim, 1, range_min, range_max)
distances_from_ref = calculate_distances_from_reference(points, reference_point)
axs(i, 0).hist(pairwise_distances(~np.isnan(pairwise_distances)), bins=50, alpha=0.7, color='blue', edgecolor='black')
axs(i, 0).set_title(f'Pairwise Distances in {dim}D')
axs(i, 1).hist(distances_from_ref, bins=30, alpha=0.7, color='green', edgecolor='black', range=(0, max(distances_from_ref)))
axs(i, 1).set_title(f'Distances to Reference in {dim}D')
# Calculating and plotting mean and std deviation trends across dimensions
means_pairwise, stds_pairwise, means_ref, stds_ref = calculate_stats_for_dimensions(num_points, dimensions_range, range_min, range_max)
# Plotting mean and std deviation graphs for pairwise distances
axs(0, 2).plot(dimensions_range, means_pairwise, label='Mean Pairwise', marker='o', color='blue')
axs(0, 2).plot(dimensions_range, stds_pairwise, label='Std Dev Pairwise', marker='x', color='cyan')
axs(0, 2).set_title('Pairwise Distances Stats')
# Plotting mean and std deviation graphs for distances to reference point
axs(1, 2).plot(dimensions_range, means_ref, label='Mean Reference', marker='o', color='green')
axs(1, 2).plot(dimensions_range, stds_ref, label='Std Dev Reference', marker='x', color='lime')
axs(1, 2).set_title('Reference Point Distances Stats')
axs(0, 2).legend()
axs(1, 2).legend()
plt.show()
plot_histograms_and_stats(1000, range(1, 101), 1, 100)
L’output del codice mostra come cambiano le distanze tra le dimensioni. In 3D, ci sono diverse distanze tra i punti. In 100D, le distanze tra i punti tendono ad essere simili. I grafici a destra mostrano anche che all’aumentare delle dimensioni, la distanza media tra i punti aumenta, ma la deviazione standard rimane più o meno la stessa dello spazio 2D o 3D.
Un’altra nota qui è che all’aumentare delle dimensioni, la distanza media tra i punti aumenta e si avvicina alla distanza massima. Ciò accade perché la maggior parte dello spazio è concentrato negli angoli.
Per capirlo meglio, possiamo simulare punti casuali con dimensioni fino a 100D. Questo ci permetterà di confrontare la distanza media con la distanza massima.
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdistdef generate_points(dimensions, num_points, range_min, range_max):
return np.random.uniform(range_min, range_max, (num_points, dimensions))
def calculate_distances_stats(points):
# Compute pairwise distances
distances = pdist(points)
# Calculate average and maximum distance
average_distance = np.mean(distances)
max_distance = np.max(distances)
return average_distance, max_distance
def plot_normalized_difference(num_points, dimensions_range, range_min, range_max):
normalized_differences = ()
for dim in dimensions_range:
points = generate_points(dim, num_points, range_min, range_max)
average_distance, max_distance = calculate_distances_stats(points)
normalized_difference = (max_distance - average_distance) / max_distance
normalized_differences.append(normalized_difference)
plt.figure(figsize=(8, 6))
plt.plot(dimensions_range, normalized_differences, label='Normalized Difference', marker='o', color='blue')
plt.xlabel('Number of Dimensions')
plt.ylabel('Normalized Difference')
plt.title('Normalized Difference Between Max and Average Distances Across Dimensions')
plt.legend()
plt.show()
plot_normalized_difference(500, range(1, 101), 0, 1)
Il grafico mostra che man mano che entriamo nelle dimensioni più elevate, la distanza media si avvicina alla distanza massima. Abbiamo usato la normalizzazione qui per assicurarci che le scale fossero accurate.
È importante comprendere la differenza tra distanze assolute e relative. Sebbene le distanze assolute generalmente aumentino con l’aumentare delle dimensioni, sono le differenze relative che contano di più. Gli algoritmi di clustering come K-means o DBSCAN funzionano osservando il modo in cui i punti sono posizionati tra loro, non le loro distanze esatte. Ciò ci consente di trovare modelli e relazioni che potremmo perdere se guardassimo solo alle distanze.
Ma questo porta a una domanda interessante: perché le coppie di punti negli spazi ad alta dimensione tendono ad essere all’incirca alla stessa distanza l’uno dall’altro quando aggiungiamo più dimensioni? Cosa fa sì che ciò accada?
Per capire perché coppie di punti in spazi ad alta dimensione diventano equidistanti, possiamo guardare alla Legge dei Grandi Numeri (LLN). Questo principio statistico suggerisce che man mano che aumentiamo la dimensione del nostro campione o il numero di dimensioni, la media delle nostre osservazioni si avvicina al valore atteso.
Consideriamo l’esempio del lancio di un dado equilibrato a sei facce. La media prevista di un lancio è 3,5, che è la media di tutti i possibili risultati. Inizialmente, con solo pochi tiri, come 5 o 10, la media potrebbe essere significativamente diversa da 3,5 a causa della casualità. Ma quando aumentiamo il numero di tiri a centinaia o migliaia, il valore medio dei tiri si avvicina a 3,5. Questo fenomeno, in cui la media di molte prove si allinea con il valore atteso, mostra l’essenza dell’LLN. Dimostra che mentre i risultati individuali sono imprevedibili, la media diventa altamente prevedibile in molti studi.
Ora, come si collega questo alle distanze negli spazi ad alta dimensione?
La distanza euclidea tra due punti in uno spazio n-dimensionale viene calcolata sommando le differenze al quadrato di ciascuna dimensione. Possiamo pensare a ciascuna differenza al quadrato come a una variabile casuale, simile al lancio di un dado. All’aumentare del numero di dimensioni (o rotoli), la somma di questi “rulli” si avvicina al valore previsto.
Un requisito cruciale per la LLN è l’indipendenza delle variabili casuali. Nei vettori ad alta dimensione, questa indipendenza potrebbe essere mostrata attraverso un’interessante proprietà geometrica: i vettori tendono ad essere quasi ortogonali tra loro.
import numpy as npdef test_orthogonality(dimensions, n_trials):
for i in range(n_trials):
# Generate two random vectors
v1 = np.random.randn(dimensions)
v2 = np.random.randn(dimensions)
# Calculate dot product
dot_product = np.dot(v1, v2)
# Calculate magnitudes
magnitude_v1 = np.linalg.norm(v1)
magnitude_v2 = np.linalg.norm(v2)
# Calculate the cosine of the angle
cos_theta = dot_product / (magnitude_v1 * magnitude_v2)
# Check if vectors are almost orthogonal
if np.abs(cos_theta) < 0.1: # Adjust this threshold as needed
orthogonality = "Almost Orthogonal"
else:
orthogonality = "Not Orthogonal"
# Calculate angle in degrees
theta = np.arccos(cos_theta) * (180 / np.pi) # Convert to degrees
print(f"Trial {i+1}:")
print(f" Dot Product: {dot_product}")
print(f" Cosine of Angle: {cos_theta}")
print(f" Angle: {theta} degrees")
print(f" Status: {orthogonality}")
print("--------------------------------")
# Try to edit this and notice the near-orthogonality of vectors in higher dimensions
dimensions = 100 # Number of dimensions
n_trials = 10 # Number of trials
test_orthogonality(dimensions, n_trials)
Prova a eseguire il codice sopra e a modificare il numero di dimensioni/prove e puoi notare che i vettori in dimensioni superiori sono quasi ortogonali.
L’angolo tra due vettori, A e B, è determinato dal coseno dell’angolo, che deriva dal loro prodotto scalare e dalle grandezze. La formula è espressa come:
Qui, UN⋅B rappresenta il prodotto scalare dei vettori A e B e ∥UN∥ e ∥B∥ sono le rispettive grandezze. Affinché due vettori siano ortogonali, l’angolo tra loro deve essere di 90 gradi, rendendo cos(io) uguale a zero. In genere, ciò si ottiene quando il prodotto scalare UN⋅B è zero, una condizione familiare nelle dimensioni inferiori.
Tuttavia, negli spazi ad alta dimensione emerge un altro fenomeno. Il rapporto tra il prodotto scalare e la grandezza dei vettori diventa così piccolo che possiamo considerare i vettori “quasi ortogonali”.
Ma cosa significa in questo contesto che due vettori sono “indipendenti”?
Navigare in una città a griglia: un’analogia per l’indipendenza nelle dimensioni elevate
Immagina di trovarti in una città disposta a griglia, come le strade di Manhattan. Immaginati a un incrocio, mentre cerchi di raggiungere un altro punto di questa città. In questa analogia, ogni strada rappresenta una dimensione in uno spazio ad alta dimensione. Muoversi lungo una strada è come cambiare il valore in una dimensione di un vettore ad alta dimensione. Muoversi lungo una strada non influisce sulla tua posizione su un’altra strada, proprio come cambiare una dimensione non influisce sulle altre.
Per raggiungere un’intersezione specifica, prendi una serie di decisioni indipendenti, come il calcolo della distanza nello spazio ad alta dimensione. Ogni decisione contribuisce in modo indipendente ma ti porta a destinazione.
Questa analogia si applica anche al concetto di ortogonalità nei vettori ad alta dimensione. Quando i vettori sono quasi ortogonali, seguono percorsi propri senza influenzarsi in modo significativo a vicenda. Questa condizione integra la necessità di indipendenza statistica per il LLN.
Una nota importante: sebbene questa analogia con LLN offra una prospettiva utile, potrebbe non catturare tutta l’idea o le cause alla base di questo comportamento. Tuttavia, funge da utile proxy, fornendo una comprensione del motivo Potrebbe essere che le coppie di punti siano quasi equidistanti.
Un modo in cui si manifesta la maledizione dei problemi di dimensionalità è l’adattamento eccessivo. L’overfitting si verifica quando un modello complesso apprende il rumore invece dei modelli nei dati. Ciò è particolarmente vero negli spazi ad alta dimensione dove sono presenti molte funzionalità. Il modello può creare false connessioni o correlazioni e funzionare male quando rileva nuovi dati (non riuscendo a generalizzare).
La maledizione rende anche difficile trovare modelli nei grandi set di dati. I dati ad alta dimensione sono sparsi e sparsi, quindi è difficile per i metodi di analisi tradizionali trovare informazioni significative. Sono necessarie alcune modifiche o metodi specializzati per navigare e comprendere questo tipo di dati.
Un’altra implicazione è che l’elaborazione di dati ad alta dimensionalità richiede molta potenza di calcolo e memoria. Gli algoritmi che funzionano bene nelle dimensioni inferiori diventano molto più complessi e pesanti in termini di risorse all’aumentare del numero di dimensioni. Ciò significa disporre di hardware più potente o ottimizzare gli algoritmi per gestire in modo efficiente il maggiore carico computazionale.
Esistono diverse strategie per affrontare la maledizione della dimensionalità. Un modo è ridurre la dimensionalità mantenendo le informazioni importanti (es. algoritmo PCA). Un altro metodo è l’apprendimento multiplo (può essere considerato come un tipo di riduzione della dimensionalità), che scopre la struttura all’interno dei dati ad alta dimensionalità. L’idea chiave alla base dell’apprendimento multidimensionale è che molti set di dati ad alta dimensione in realtà si trovano su una varietà a dimensione inferiore all’interno dello spazio ad alta dimensione (es. Isomappe)
Si noti qui che, in generale, le tecniche tradizionali di riduzione della dimensionalità come la PCA (analisi delle componenti principali) si concentrano sulla conservazione della struttura e della varianza dei dati globali in modo lineare. Al contrario, molteplici tecniche di apprendimento come Isomap (mappatura isometrica) enfatizzano la scoperta della struttura non lineare sottostante (varietà) dei dati, con l’obiettivo di preservare le relazioni locali e le caratteristiche geometriche.
Anche la selezione delle funzionalità è un’opzione, in cui vengono scelte le funzionalità rilevanti per migliorare le prestazioni del modello. Le tecniche di regolarizzazione prevengono l’overfitting riducendo le caratteristiche meno importanti. Anche aumentare la dimensione del campione può aiutare, anche se potrebbe non essere sempre possibile. Questi metodi possono aiutarci ad analizzare i dati ad alta dimensione in modo più accurato ed efficiente.
La maledizione della dimensionalità è uno dei problemi più importanti nella scienza dei dati e nell’apprendimento automatico. Succede quando si ha a che fare con spazi ad alta dimensione. Due sfide significative che si presentano sono la scarsità dei dati e i problemi con le misurazioni della distanza. Queste sfide possono causare un adattamento eccessivo dei modelli di apprendimento automatico e rendere i calcoli più complessi. Per affrontare queste sfide, è possibile utilizzare strategie come la riduzione della dimensionalità, la selezione delle caratteristiche e le tecniche di regolarizzazione.
Se sei arrivato fin qui, vorrei ringraziarti per aver dedicato del tempo a leggerlo! Spero che tu abbia trovato l’argomento divertente e almeno abbastanza stimolante da approfondire il mondo dei dati ad alta dimensione. Non esitate a suggerire eventuali modifiche o segnalare eventuali errori o imprecisioni.
Fonte: towardsdatascience.com
