MapReduce - Algoritmo
L'algoritmo MapReduce contiene due attività importanti, ovvero Map e Reduce.
- L'attività della mappa viene eseguita tramite Mapper Class
- L'attività di riduzione viene eseguita tramite la Classe Riduttore.
La classe Mapper prende l'input, lo tokenizza, lo mappa e lo ordina. L'output della classe Mapper viene utilizzato come input dalla classe Reducer, che a sua volta ricerca le coppie corrispondenti e le riduce.
MapReduce implementa vari algoritmi matematici per dividere un'attività in piccole parti e assegnarle a più sistemi. In termini tecnici, l'algoritmo MapReduce aiuta a inviare le attività di Map & Reduce ai server appropriati in un cluster.
Questi algoritmi matematici possono includere quanto segue:
- Sorting
- Searching
- Indexing
- TF-IDF
Ordinamento
L'ordinamento è uno degli algoritmi di base di MapReduce per elaborare e analizzare i dati. MapReduce implementa l'algoritmo di ordinamento per ordinare automaticamente le coppie chiave-valore di output dal mappatore in base alle loro chiavi.
I metodi di ordinamento vengono implementati nella classe mapper stessa.
Nella fase Shuffle and Sort, dopo aver tokenizzato i valori nella classe mapper, il file Context class (classe definita dall'utente) raccoglie le chiavi con valori corrispondenti come raccolta.
Per raccogliere coppie chiave-valore simili (chiavi intermedie), la classe Mapper richiede l'aiuto di RawComparator class per ordinare le coppie chiave-valore.
L'insieme di coppie chiave-valore intermedie per un determinato Riduttore viene ordinato automaticamente da Hadoop per formare valori-chiave (K2, {V2, V2,…}) prima di essere presentati al Riduttore.
Ricerca
La ricerca gioca un ruolo importante nell'algoritmo MapReduce. Aiuta nella fase combinatore (opzionale) e nella fase riduttore. Cerchiamo di capire come funziona la ricerca con l'aiuto di un esempio.
Esempio
L'esempio seguente mostra come MapReduce utilizza l'algoritmo di ricerca per scoprire i dettagli del dipendente che percepisce lo stipendio più alto in un dato set di dati del dipendente.
Supponiamo di avere i dati dei dipendenti in quattro file diversi: A, B, C e D. Supponiamo inoltre che ci siano record dei dipendenti duplicati in tutti e quattro i file a causa dell'importazione ripetuta dei dati dei dipendenti da tutte le tabelle del database. Vedere la figura seguente.
The Map phaseelabora ogni file di input e fornisce i dati del dipendente in coppie chiave-valore (<k, v>: <emp name, salary>). Vedere la figura seguente.
The combiner phase(tecnica di ricerca) accetterà l'input dalla fase Mappa come coppia chiave-valore con il nome del dipendente e lo stipendio. Utilizzando la tecnica di ricerca, il combinatore controllerà tutto lo stipendio dei dipendenti per trovare il dipendente più salariato in ogni file. Vedi il seguente frammento.
<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary
if(v(second employee).salary > Max){
Max = v(salary);
}
else{
Continue checking;
}Il risultato atteso è il seguente:
|
Reducer phase- In ogni scheda troverai l'impiegato più salariato. Per evitare la ridondanza, controllare tutte le coppie <k, v> ed eliminare le voci duplicate, se presenti. Lo stesso algoritmo viene utilizzato tra le quattro coppie <k, v>, che provengono da quattro file di input. L'output finale dovrebbe essere il seguente:
<gopal, 50000>Indicizzazione
Normalmente l'indicizzazione viene utilizzata per puntare a un dato dato e al suo indirizzo. Esegue l'indicizzazione batch sui file di input per un particolare Mapper.
La tecnica di indicizzazione normalmente utilizzata in MapReduce è nota come inverted index.I motori di ricerca come Google e Bing utilizzano la tecnica di indicizzazione invertita. Cerchiamo di capire come funziona l'indicizzazione con l'aiuto di un semplice esempio.
Esempio
Il testo seguente è l'input per l'indicizzazione invertita. Qui T [0], T [1] et [2] sono i nomi dei file e il loro contenuto è tra virgolette doppie.
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"Dopo aver applicato l'algoritmo di indicizzazione, otteniamo il seguente output:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}Qui "a": {2} implica che il termine "a" appare nel file T [2]. Allo stesso modo, "è": {0, 1, 2} implica che il termine "è" venga visualizzato nei file T [0], T [1] e T [2].
TF-IDF
TF-IDF è un algoritmo di elaborazione del testo che è l'abbreviazione di Term Frequency - Inverse Document Frequency. È uno degli algoritmi di analisi web comuni. In questo caso, il termine "frequenza" si riferisce al numero di volte in cui un termine appare in un documento.
Frequenza del termine (TF)
Misura la frequenza con cui un determinato termine ricorre in un documento. Viene calcolato dal numero di volte in cui una parola appare in un documento diviso per il numero totale di parole in quel documento.
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)Frequenza documento inverso (IDF)
Misura l'importanza di un termine. Viene calcolato dal numero di documenti nel database di testo diviso per il numero di documenti in cui compare un termine specifico.
Durante il calcolo di TF, tutti i termini sono considerati ugualmente importanti. Ciò significa che TF conta la frequenza del termine per parole normali come "è", "a", "cosa", ecc. Pertanto, dobbiamo conoscere i termini frequenti mentre aumentiamo quelli rari, calcolando quanto segue:
IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).L'algoritmo è spiegato di seguito con l'aiuto di un piccolo esempio.
Esempio
Considera un documento contenente 1000 parole, in cui la parola hiveappare 50 volte. Il TF perhive è quindi (50/1000) = 0,05.
Ora, supponiamo di avere 10 milioni di documenti e la parola hivecompare in 1000 di questi. Quindi, l'IDF viene calcolato come log (10.000.000 / 1.000) = 4.
Il peso TF-IDF è il prodotto di queste quantità: 0,05 × 4 = 0,20.