Come le macchine danno senso ai big data: un'introduzione agli algoritmi di clustering

Dai un'occhiata all'immagine qui sotto. È una raccolta di bug e insetti striscianti di diverse forme e dimensioni. Prenditi un momento per classificarli per somiglianza in un numero di gruppi.

Questa non è una domanda trabocchetto. Inizia con il raggruppamento dei ragni insieme.

Immagini tramite Ricerca immagini di Google, etichettate per il riutilizzo

Fatto? Sebbene non ci sia necessariamente una risposta "corretta" qui, è molto probabile che tu divida i bug in quattro cluster. I ragni in un grappolo, la coppia di lumache in un altro, le farfalle e la falena in uno, e il trio di vespe e api in un altro.

Non era poi così male, vero? Probabilmente potresti fare lo stesso con il doppio del numero di bug, giusto? Se avessi un po 'di tempo libero - o una passione per l'entomologia - probabilmente potresti fare lo stesso con un centinaio di bug.

Tuttavia, per una macchina, raggruppare dieci oggetti in molti cluster significativi non è un compito da poco, grazie a un ramo di matematica strabiliante chiamato combinatoria, che ci dice che ci sono 115.975 modi diversi in cui avresti potuto raggruppare quei dieci insetti. Se ci fossero stati venti bug, ci sarebbero stati più di cinquanta trilioni di modi possibili per raggrupparli.

Con un centinaio di bug - ci sarebbero molte volte più soluzioni di quante siano le particelle nell'universo conosciuto. Quante volte di più? Secondo il mio calcolo, circa cinquecento milioni di miliardi di volte più. In effetti, ci sono più di quattro milioni di miliardi di soluzioni di googol (che cos'è un googol?). Per solo un centinaio di oggetti.

Quasi tutte queste soluzioni sarebbero prive di significato, eppure da quel numero inimmaginabile di possibili scelte, hai trovato abbastanza rapidamente uno dei pochissimi che raggruppava gli insetti in modo utile.

Noi umani diamo per scontato quanto bene stiamo classificando e dando un senso a grandi volumi di dati abbastanza rapidamente. Che si tratti di un paragrafo di testo, di immagini su uno schermo o di una sequenza di oggetti, gli umani sono generalmente abbastanza efficienti nel dare un senso ai dati che il mondo ci fornisce.

Dato che un aspetto chiave dello sviluppo di A.I. e Machine Learning sta facendo in modo che le macchine comprendano rapidamente grandi serie di dati di input, quali scorciatoie sono disponibili? Qui puoi leggere tre algoritmi di clustering che le macchine possono usare per dare rapidamente un senso a grandi set di dati. Questo non è affatto un elenco esaustivo - ci sono altri algoritmi là fuori - ma rappresentano un buon punto di partenza!

Troverai per ciascuno un breve riepilogo di quando potresti utilizzarli, una breve panoramica del loro funzionamento e un esempio più dettagliato e dettagliato. Credo che aiuta a capire un algoritmo eseguendo effettivamente te stesso. Se sei davvero appassionato, troverai il modo migliore per farlo è con carta e penna. Vai avanti - nessuno giudicherà!

Tre cluster sospetti, con K = 3

K significa clustering

Utilizzare quando:

... hai un'idea di quanti gruppi ti aspetti di trovare a priori.

Come funziona:

L'algoritmo assegna casualmente ogni osservazione in una delle k categorie, quindi calcola la media di ciascuna categoria. Successivamente, riassegna ogni osservazione alla categoria con la media più vicina prima di ricalcolare le medie. Questo passaggio si ripete ripetutamente fino a quando non sono necessarie ulteriori riassegnazioni.

Esempio lavorato:

Prendi un gruppo di 12 giocatori di calcio (o "calcio") che hanno segnato ognuno un certo numero di goal in questa stagione (diciamo nell'intervallo 3–30). Dividiamoli in cluster separati - diciamo tre.

Il passaggio 1 ci richiede di dividere casualmente i giocatori in tre gruppi e calcolare la media di ciascuno.

Gruppo 1
Giocatore A (5 goal), Giocatore B (20 goal), Giocatore C (11 goal)
Media gruppo = (5 + 20 + 11) / 3 = 12
Gruppo 2
Giocatore D (5 goal), Giocatore E (3 goal), Giocatore F (19 goal)
Media del gruppo = 9
Gruppo 3
Giocatore G (30 goal), Giocatore H (3 goal), Giocatore I (15 goal)
Media gruppo = 16

Passaggio 2: per ogni giocatore, riassegnali al gruppo con la media più vicina. Ad esempio, il giocatore A (5 goal) è assegnato al gruppo 2 (media = 9). Quindi ricalcolare il gruppo significa.

Gruppo 1 (media vecchia = 12)
Giocatore C (11 gol)
Nuova media = 11
Gruppo 2 (media vecchia = 9)
Giocatore A (5 goal), Giocatore D (5 goal), Giocatore E (3 goal), Giocatore H (3 goal)
Nuova media = 4
Gruppo 3 (media vecchia = 16)
Giocatore G (30 goal), Giocatore I (15 goal), Giocatore B (20 goal), Giocatore F (19 goal)
Nuova media = 21

Ripeti il ​​passaggio 2 fino a quando il gruppo non significa più cambiare. Per questo esempio in qualche modo inventato, ciò accade alla prossima iterazione. Fermare! Ora hai formato tre cluster dal set di dati!

Gruppo 1 (media vecchia = 11)
Giocatore C (11 goal), Giocatore I (15 goal)
Media finale = 13
Gruppo 2 (media vecchia = 4)
Giocatore A (5 goal), Giocatore D (5 goal), Giocatore E (3 goal), Giocatore H (3 goal)
Media finale = 4
Gruppo 3 (media vecchia = 21)
Giocatore G (30 goal), Giocatore B (20 goal), Giocatore F (19 goal)
Media finale = 23

Con questo esempio, i cluster potrebbero corrispondere alle posizioni dei giocatori sul campo, come difensori, centrocampisti e attaccanti. K-mean funziona qui perché potremmo ragionevolmente aspettarci che i dati rientrino naturalmente in queste tre categorie.

In questo modo, dati dati su una serie di statistiche sulle prestazioni, una macchina potrebbe fare un lavoro ragionevole per stimare le posizioni dei giocatori da qualsiasi sport di squadra - utile per l'analisi degli sport, e in effetti qualsiasi altro scopo in cui la classificazione di un set di dati in gruppi predefiniti può fornire approfondimenti pertinenti.

Dettagli più fini:

Esistono diverse varianti dell'algoritmo qui descritto. Il metodo iniziale di "seeding" dei cluster può essere eseguito in diversi modi. Qui, abbiamo assegnato casualmente ogni giocatore in un gruppo, quindi abbiamo calcolato le medie del gruppo. Ciò fa sì che il gruppo iniziale significhi tendenzialmente essere simile l'uno all'altro, il che garantisce una maggiore ripetibilità.

Un'alternativa è seminare i cluster con un solo giocatore ciascuno, quindi iniziare ad assegnare i giocatori al cluster più vicino. I cluster restituiti sono più sensibili alla fase di seeding iniziale, riducendo la ripetibilità in set di dati altamente variabili. Tuttavia, questo approccio può ridurre il numero di iterazioni richieste per completare l'algoritmo, poiché i gruppi impiegheranno meno tempo a divergere.

Un'ovvia limitazione al clustering di K-signi è che devi fornire ipotesi a priori su quanti cluster ti aspetti di trovare. Esistono metodi per valutare l'adattamento di un particolare insieme di cluster. Ad esempio, la somma dei quadrati all'interno del cluster è una misura della varianza all'interno di ciascun cluster. "Migliori" sono i cluster, minore è il WCSS complessivo.

Clustering gerarchico

Utilizzare quando:

... desideri scoprire le relazioni sottostanti tra le tue osservazioni.

Come funziona:

Viene calcolata una matrice di distanza, in cui il valore della cella (i, j) è una metrica di distanza tra le osservazioni i e j. Quindi, accoppia le due osservazioni più vicine e calcola la loro media. Forma una nuova matrice di distanza, unendo le osservazioni accoppiate in un singolo oggetto. Da questa matrice di distanza, accoppia le due osservazioni più vicine e calcola la loro media. Ripetere fino a quando tutte le osservazioni sono raggruppate insieme.

Esempio lavorato:

Ecco un set di dati super-semplificato su una selezione di specie di balene e delfini. Come biologo qualificato, posso assicurarti che normalmente utilizziamo set di dati molto più dettagliati per cose come la ricostruzione della filogenesi. Per ora però, vedremo solo le lunghezze tipiche del corpo per queste sei specie. Useremo solo due passaggi ripetuti.

Lunghezza iniziale specie (m)
Bottlenose Dolphin BD 3.0
Risso's Dolphin RD 3.6
Pilot Whale PW 6.5
Killer Whale KW 7.5
Megattera HW 15.0
Fin Whale FW 20.0

Passaggio 1: calcolare una matrice di distanza tra ciascuna specie. Qui useremo la distanza euclidea - quanto distano i punti dati? Leggi esattamente come faresti con un diagramma di distanza in un atlante stradale. La differenza di lunghezza tra qualsiasi coppia di specie può essere cercata leggendo il valore all'intersezione della riga e colonna pertinente.

    BD RD PW KW HW
RD 0.6
PW 3.5 2.9
KW 4,5 3,9 1,0
HW 12,0 11,4 8,5 7,5
AI 17,0 16,4 13,5 12,5 5,0

Passaggio 2: accoppia le due specie più vicine. Qui, saranno i tursiopi e di Risso, con una lunghezza media di 3,3 m.

Ripeti il ​​passaggio 1 ricalcolando la matrice della distanza, ma questa volta unisci i tursiopi e i delfini di Risso in un singolo oggetto con una lunghezza di 3,3 m.

    [BD, RD] PW KW HW
PW 3.2
KW 4.2 1.0
HW 11,7 8,5 7,5
AI 16,7 13,5 12,5 5,0

Quindi, ripetere il passaggio 2 con questa nuova matrice di distanza. Qui, la distanza più piccola è tra le Pilot & Killer Whales, quindi le accoppiamo e prendiamo la loro media - che ci dà 7,0 m.

Quindi, ripetiamo il Passaggio 1: ricalcola la matrice della distanza, ma ora abbiamo unito le Pilot & Killer Whales in un singolo oggetto di lunghezza 7,0 m.

         [BD, RD] [PW, KW] HW
[PW, KW] 3.7
HW 11.7 8.0
AI 16,7 13,0 5,0

Quindi, ripetiamo il passaggio 2 con questa matrice di distanza. La distanza più piccola (3,7 m) è tra i due oggetti uniti - quindi ora li uniamo in un oggetto ancora più grande e prendiamo la media (che è 5,2 m).

Quindi, ripetiamo il passaggio 1 e calcoliamo una nuova matrice di distanza, dopo aver unito i delfini di Bottlenose e Risso con i piloti e le orche.

   [[BD, RD], [PW, KW]] HW
HW 9.8
AI 14,8 5,0

Successivamente, ripetiamo il passaggio 2. La distanza minima (5,0 m) è tra le megattere e le balene, quindi le uniamo in un unico oggetto e prendiamo la media (17,5 m).

Quindi, torna al passaggio 1: calcola la matrice della distanza, dopo aver unito le megattere e le balene.

         [[BD, RD], [PW, KW]]
[HW, FW] 12.3

Infine, ripetiamo il passaggio 2: in questa matrice esiste solo una distanza (12,3 m), quindi accoppiamo tutto in un unico grande oggetto e ora possiamo fermarci! Diamo un'occhiata all'oggetto unito finale:

[[[BD, RD], [PW, KW]], [HW, FW]]

Ha una struttura nidificata (pensa a JSON), che gli consente di essere disegnata come un grafico ad albero o dendrogramma. Legge più o meno allo stesso modo di un albero genealogico. Più due osservazioni sono vicine sull'albero, più sono simili o strettamente correlate.

Un dendrogramma senza fronzoli generato su R-Fiddle.org

La struttura del dendrogramma ci fornisce informazioni su come è strutturato il nostro set di dati. Nel nostro esempio, vediamo due rami principali, con Humpback Whale e Fin Whale da un lato, e il Bottlenose Dolphin / Risso’s Dolphin e Pilot Whale / Killer Whale dall'altro.

Nella biologia evolutiva, set di dati molto più grandi con molti più campioni e misurazioni vengono utilizzati in questo modo per inferire le relazioni tassonomiche tra di loro. Al di fuori della biologia, il clustering gerarchico ha applicazioni in contesti di data mining e machine learning.

La cosa interessante è che questo approccio non richiede ipotesi sul numero di cluster che stai cercando. È possibile dividere il dendrogramma restituito in gruppi "tagliando" l'albero a una determinata altezza. Questa altezza può essere scelta in diversi modi, a seconda della risoluzione con cui si desidera raggruppare i dati.

Ad esempio, guardando il dendrogramma sopra, se disegnassimo una linea orizzontale ad altezza = 10, intersecheremmo i due rami principali, dividendo il dendrogramma in due sotto-grafici. Se tagliassimo ad altezza = 2, divideremmo il dendrogramma in tre gruppi.

Dettagli più fini:

Esistono essenzialmente tre aspetti in cui gli algoritmi di clustering gerarchico possono variare rispetto a quello qui indicato.

L'approccio più fondamentale è l'approccio: qui abbiamo utilizzato un processo agglomerato, in base al quale iniziamo con singoli punti dati e li raggruppiamo iterativamente insieme fino a quando non restiamo in un unico grande cluster. Un approccio alternativo (ma più intensivo dal punto di vista computazionale) è quello di iniziare con un cluster gigante, quindi procedere a dividere i dati in cluster sempre più piccoli fino a quando non vengono lasciati punti dati isolati.

Esistono anche una serie di metodi che possono essere utilizzati per calcolare le matrici della distanza. Per molti scopi, la distanza euclidea (pensa il teorema di Pitagora) sarà sufficiente, ma ci sono alternative che potrebbero essere più applicabili in alcune circostanze.

Infine, anche il criterio di collegamento può variare. I cluster sono collegati in base alla vicinanza tra loro, ma il modo in cui definiamo "vicino" è flessibile. Nell'esempio sopra, abbiamo misurato le distanze tra le medie (o "centroidi") di ciascun gruppo e abbinato i gruppi più vicini. Tuttavia, potresti voler utilizzare una definizione diversa.

Ad esempio, ogni cluster è composto da diversi punti discreti. Potremmo definire la distanza tra due cluster come la distanza minima (o massima) tra i loro punti, come illustrato nella figura seguente. Esistono ancora altri modi per definire il criterio di collegamento, che può essere adatto in contesti diversi.

Rosso / Blu: collegamento centroide; Rosso / Verde: collegamento minimo; Verde / Blu: massimo collegamento

Rilevamento grafico della comunità

Utilizzare quando:

... hai dati che possono essere rappresentati come una rete o "grafico".

Come funziona:

Una comunità grafica è generalmente definita come un sottoinsieme di vertici che sono più connessi tra loro che con il resto della rete. Esistono vari algoritmi per identificare le comunità, sulla base di definizioni più specifiche. Gli algoritmi includono, tra l'altro, Edge Betweenness, Modularity-Maximsation, Walktrap, Clique Percolation, Leading Eigenvector ...

Esempio lavorato:

La teoria dei grafi, o lo studio matematico delle reti, è un affascinante ramo della matematica che ci consente di modellare sistemi complessi come una raccolta astratta di "punti" (o vertici) collegati da "linee" (o bordi).

Forse i casi di studio più intuitivi sono i social network. Qui, i vertici rappresentano le persone e i bordi collegano i vertici che sono amici / follower. Tuttavia, qualsiasi sistema può essere modellato come una rete se è possibile giustificare un metodo per connettere in modo significativo diversi componenti. Tra le applicazioni più innovative della teoria dei grafi al raggruppamento vi sono l'estrazione di caratteristiche dai dati di immagine e l'analisi delle reti di regolazione genica.

Come esempio entry-level, dai un'occhiata a questo grafico rapidamente messo insieme. Mostra gli otto siti Web che ho visitato di recente, collegati in base al collegamento tra i rispettivi articoli di Wikipedia. Puoi assemblare questi dati manualmente, ma per progetti su larga scala, è molto più veloce scrivere uno script Python per fare lo stesso. Eccone uno che ho scritto prima.

Grafico tracciato con il pacchetto

I vertici sono colorati in base all'appartenenza alla comunità e dimensionati in base alla loro centralità. Vedi come Google e Twitter sono i più centrali?

Inoltre, i cluster hanno un buon senso nel mondo reale (sempre un importante indicatore di prestazioni). I vertici gialli sono generalmente siti di riferimento / ricerca; i vertici blu sono tutti usati per la pubblicazione online (di articoli, tweet o codice); e i vertici rossi includono YouTube, che è stato ovviamente fondato da ex dipendenti PayPal. Detrazioni non sbagliate per una macchina!

Oltre ad essere un modo utile per visualizzare sistemi di grandi dimensioni, il vero potere delle reti deriva dalla loro analisi matematica. Cominciamo traducendo la nostra bella immagine della rete in un formato più matematico. Di seguito è la matrice di adiacenza della rete.

         GH Gl M P Q T W Y
GitHub 0 1 0 0 0 1 0 0
Google 1 0 1 1 1 1 1 1
Medio 0 1 0 0 0 1 0 0
PayPal 0 1 0 0 0 1 0 1
Quora 0 1 0 0 0 1 1 0
Twitter 1 1 1 1 1 0 0 1
Wikipedia 0 1 0 0 1 0 0 0
YouTube 0 1 0 1 0 1 0 0

Il valore all'intersezione di ciascuna riga e colonna indica se esiste un bordo tra quella coppia di vertici. Ad esempio, c'è un bordo tra Medio e Twitter (sorpresa, sorpresa!), Quindi il valore in cui le loro file / colonne si intersecano è 1. Allo stesso modo, non c'è bordo tra Medio e PayPal, quindi restituisce l'intersezione delle loro file / colonne 0.

Nella matrice di adiacenza sono codificate tutte le proprietà di questa rete: ci fornisce la chiave per iniziare a sbloccare ogni sorta di informazioni preziose. Per cominciare, sommare qualsiasi colonna (o riga) ti dà il grado di ciascun vertice, cioè a quanti altri è collegato. Questo è comunemente indicato con la lettera k.

Allo stesso modo, sommando i gradi di ogni vertice e dividendo per due si ottiene L, il numero di spigoli (o "collegamenti") nella rete. Il numero di righe / colonne indica N, il numero di vertici (o "nodi") nella rete.

Conoscere solo k, L, N e il valore di ogni cella nella matrice di adiacenza A ci consente di calcolare la modularità di ogni dato cluster della rete.

Supponiamo che abbiamo raggruppato la rete in diverse comunità. Possiamo usare il punteggio di modularità per valutare la "qualità" di questo raggruppamento. Un punteggio più alto mostrerà che abbiamo diviso la rete in comunità "accurate", mentre un punteggio basso indica che i nostri cluster sono più casuali che perspicaci. L'immagine seguente illustra questo.

La modularità funge da misura della

La modularità può essere calcolata utilizzando la formula seguente:

È una buona dose di matematica, ma possiamo scomporla a poco a poco e avrà più senso.

M è ovviamente ciò che stiamo calcolando: la modularità.

1 / 2L ci dice di dividere tutto ciò che segue per 2L, cioè il doppio del numero di bordi nella rete. Fin qui tutto bene.

Il simbolo Σ ci dice che stiamo riassumendo tutto a destra e ci consente di scorrere su ogni riga e colonna nella matrice di adiacenza A. Per coloro che non hanno familiarità con la notazione della somma, i, j = 1 e N funzionano in modo molto simile a nidificati loop di programmazione. In Python, lo scrivi come segue:

somma = 0
per i nell'intervallo (1, N):
    per j nell'intervallo (1, N):
        ans = #stuff con i e j come indici
        somma + = ans

Cos'è #stuff con io e j in modo più dettagliato?

Bene, il bit tra parentesi ci dice di sottrarre (k_i k_j) / 2L da A_ij.

A_ij è semplicemente il valore nella matrice di adiacenza nella riga i, colonna j.

I valori di k_i e k_j sono i gradi di ciascun vertice, rilevati sommando rispettivamente le voci nella riga i e nella colonna j. Moltiplicarli insieme e dividere per 2L ci dà il numero atteso di spigoli tra i vertici iej se la rete fosse mescolata casualmente.

Nel complesso, il termine tra parentesi indica la differenza tra la struttura reale della rete e la struttura prevista che avrebbe se riassemblata casualmente. Giocare con i valori mostra che restituisce il suo valore più alto quando A_ij = 1 e (k_i k_j) / 2L è basso. Ciò significa che vediamo un valore più alto se c'è un bordo "inatteso" tra i vertici iej.

Infine, moltiplichiamo il termine tra parentesi per qualunque cosa si riferiscano gli ultimi simboli.

𝛿c_i, c_j è la funzione Kronecker-delta dal suono di fantasia ma totalmente innocua. Eccolo, spiegato in Python:

def Kronecker_Delta (ci, cj):
    se ci == cj:
        ritorno 1
    altro:
        ritorna 0
Kronecker_Delta ("A", "A") #returns 1
Kronecker_Delta ("A", "B") #returns 0

Si, e davvero cosi semplice. La funzione Kronecker-delta accetta due argomenti e restituisce 1 se sono identici, altrimenti zero.

Ciò significa che se i vertici iej sono stati inseriti nello stesso cluster, allora 𝛿c_i, c_j = 1. Altrimenti, se si trovano in cluster diversi, la funzione restituisce zero.

Mentre moltiplichiamo il termine tra parentesi per questa funzione di Kronecker-delta, scopriamo che per la somma nidificata Σ, il risultato è più alto quando ci sono molti bordi "imprevisti" che collegano i vertici assegnati allo stesso cluster. Pertanto, la modularità è una misura di quanto il grafico sia ben raggruppato in comunità separate.

La divisione per 2L limita il valore superiore della modularità a 1. I punteggi di modularità vicini o inferiori allo zero indicano che l'attuale clustering della rete è davvero inutile. Maggiore è la modularità, migliore è il raggruppamento della rete in comunità separate. Massimizzando la modularità, possiamo trovare il modo migliore di raggruppare la rete.

Si noti che dobbiamo pre-definire il modo in cui il grafico è raggruppato per scoprire quanto "buono" sia effettivamente quel cluster. Sfortunatamente, impiegando la forza bruta per provare ogni possibile modo di raggruppare il grafico per scoprire quale ha il punteggio di modularità più elevato sarebbe impossibile dal punto di vista computazionale oltre una dimensione del campione molto limitata.

Combinatorics ci dice che per una rete di soli otto vertici, ci sono 4140 modi diversi di raggrupparli. Una rete di dimensioni doppie avrebbe oltre dieci miliardi di possibili modi di raggruppare i vertici. Raddoppiare di nuovo la rete (fino a 32 vertici molto modesti) darebbe 128 settilioni di modi possibili, e una rete di ottanta vertici sarebbe in grado di raggrupparsi in più modi di quanti sono gli atomi nell'universo osservabile.

Invece, dobbiamo ricorrere a un metodo euristico che fa un buon lavoro nel valutare i cluster che produrranno il punteggio di modularità più alto, senza provare ogni singola possibilità. Questo è un algoritmo chiamato Fast-Greedy Modularity-Maximization, ed è in qualche modo analogo all'algoritmo di clustering gerarchico agglomerativo descritto sopra. Invece di fondersi in base alla distanza, "Mod-Max" unisce le comunità in base ai cambiamenti nella modularità. Ecco come va:

Inizia assegnando inizialmente ogni vertice alla propria comunità e calcolando la modularità dell'intera rete, M.

Il passaggio 1 richiede che per ciascuna coppia di comunità collegata da almeno un bordo, l'algoritmo calcoli la risultante modifica della modularità ΔM se le due comunità fossero unite in una sola.

Il passaggio 2 prende quindi la coppia di comunità che producono il maggiore aumento di ΔM, che vengono poi unite. Calcola la nuova modularità M per questo clustering e conservane una traccia.

Ripeti i passaggi 1 e 2 - ogni volta unendo la coppia di comunità per le quali ciò produce il maggior guadagno in ΔM, quindi registra il nuovo modello di clustering e il punteggio di modularità associato M.

Fermati quando tutti i vertici sono raggruppati in un cluster gigante. Ora l'algoritmo controlla i record mantenuti man mano che procedeva e identifica il modello di cluster che ha restituito il valore più alto di M. Questa è la struttura della comunità restituita.

Dettagli più fini:

Meno male! Quello era intensivo dal punto di vista computazionale, almeno per noi umani. La teoria dei grafi è una ricca fonte di problemi computazionalmente impegnativi, spesso NP-difficili, ma ha anche un potenziale incredibile per fornire informazioni preziose su sistemi e set di dati complessi. Basta chiedere a Larry Page, il cui algoritmo PageRank omonimo - che ha aiutato a spingere Google dall'inizio alla dominazione mondiale in meno di una generazione - era interamente basato sulla teoria dei grafi.

Il rilevamento da parte della comunità è uno dei punti focali dell'attuale ricerca nella teoria dei grafi e ci sono molte alternative alla Modularità-Massimizzazione, che sebbene utile, presenta alcuni inconvenienti.

Tanto per cominciare, il suo approccio agglomerato vede spesso piccole comunità ben definite inghiottite in più grandi. Questo è noto come limite di risoluzione: l'algoritmo non troverà comunità al di sotto di una determinata dimensione. Un'altra sfida è che piuttosto che avere un picco globale distinto e facile da raggiungere, l'approccio Mod-Max tende effettivamente a produrre un ampio "plateau" di molti punteggi simili ad alta modularità - rendendo in qualche modo difficile identificare veramente il punteggio massimo assoluto .

Altri algoritmi utilizzano modi diversi per definire e affrontare il rilevamento della comunità. Edge-Betweenness è un algoritmo divisivo, che inizia con tutti i vertici raggruppati in un cluster gigante. Procede rimuovendo in modo iterativo i bordi meno "importanti" della rete, fino a quando tutti i vertici rimangono isolati. Questo produce una struttura gerarchica, con vertici simili più vicini nella gerarchia.

Un altro algoritmo è Clique Percolation, che tiene conto della possibile sovrapposizione tra le comunità grafiche. Ancora un altro set di algoritmi si basa su passeggiate casuali attraverso il grafico, e poi ci sono metodi di clustering spettrale che iniziano a scavare nella composizione di eigend della matrice di adiacenza e di altre matrici che ne derivano. Queste idee vengono utilizzate nell'estrazione di funzioni, ad esempio in aree come Computer Vision.

Sarebbe ben oltre lo scopo di questo articolo dare ad ogni algoritmo il proprio esempio di lavoro approfondito. Basti dire che si tratta di un'area attiva di ricerca, che fornisce potenti metodi per dare un senso ai dati che anche una generazione fa sarebbe stato estremamente difficile da elaborare.

Conclusione

Spero che questo articolo ti abbia informato e ispirato a capire meglio come le macchine possono dare un senso ai Big Data! Il futuro è un luogo in rapida evoluzione e molti di questi cambiamenti saranno guidati da ciò che la tecnologia diventerà capace nella prossima generazione o due.

Come indicato nell'introduzione, l'apprendimento automatico è un campo di ricerca straordinariamente ambizioso, in cui i problemi estremamente complessi richiedono la soluzione nel modo più accurato ed efficiente possibile. Compiti che sono naturali per noi umani richiedono soluzioni innovative se assunti dalle macchine.

Ci sono ancora molti progressi da fare e chiunque contribuirà alla prossima idea rivoluzionaria sarà senza dubbio ricompensato generosamente. Forse qualcuno che leggerà questo articolo sarà dietro al prossimo potente algoritmo? Tutte le grandi idee devono iniziare da qualche parte!