MapReduce - Algoritma

Algoritma MapReduce mengandungi dua tugas penting, iaitu Peta dan Mengurangkan.

  • Tugas peta dilakukan dengan cara Mapper Class
  • Tugas mengurangkan dilakukan dengan menggunakan Kelas Reducer.

Kelas Mapper mengambil input, mengaitkannya, membuat peta dan menyusunnya. Pengeluaran kelas Mapper digunakan sebagai input oleh kelas Reducer, yang pada gilirannya mencari pasangan yang sepadan dan mengurangkannya.

Kelas Reducer Mapper

MapReduce menerapkan pelbagai algoritma matematik untuk membahagikan tugas ke bahagian kecil dan menyerahkannya kepada pelbagai sistem. Dalam istilah teknikal, algoritma MapReduce membantu dalam menghantar Peta & Mengurangkan tugas ke server yang sesuai dalam kelompok.

Algoritma matematik ini mungkin termasuk berikut -

  • Menyusun
  • Mencari
  • Pengindeksan
  • TF-IDF

Menyusun

Penyusun adalah salah satu daripada algoritma MapReduce asas untuk memproses dan menganalisis data. MapReduce mengimplementasikan algoritma sorting untuk secara automatik menyusun pasangan kunci nilai output dari mapper dengan kunci mereka.

  • Kaedah pengisihan dilaksanakan dalam kelas pemetaan itu sendiri.

  • Dalam fasa Shuffle and Sort, selepas mengaitkan nilai-nilai dalam kelas mapper, kelas Konteks (kelas yang ditetapkan pengguna) mengumpul kunci yang disesuaikan sebagai koleksi.

  • Untuk mengumpul pasangan kunci yang sama (kunci perantaraan), kelas Mapper mengambil bantuan kelas RawComparator untuk menyusun pasangan nilai utama.

  • Sepasang pasangan nilai utama perantaraan untuk Reducer diberikan secara automatik disusun oleh Hadoop untuk membentuk nilai-nilai utama (K2, {V2, V2, ...}) sebelum mereka dibentangkan kepada Reducer.

Mencari

Mencari memainkan peranan penting dalam algoritma MapReduce. Ia membantu dalam fasa combiner (pilihan) dan dalam fasa Reducer. Marilah kita cuba memahami bagaimana Melakukan kerja dengan bantuan contoh.

Contoh

Contoh berikut menunjukkan bagaimana MapReduce menggunakan algoritma Carian untuk mengetahui butiran pekerja yang menarik gaji tertinggi dalam dataset pekerja yang diberikan.

  • Mari kita ingatkan kita mempunyai data pekerja dalam empat fail berbeza - A, B, C, dan D. Mari kita juga mengandaikan terdapat salinan rekod pekerja dalam semua empat fail kerana mengimport data pekerja dari semua jadual pangkalan data berulang kali. Lihat ilustrasi berikut.

<span class = Peta Mengurangi Ilustrasi "/>
  • Fasa peta memproses setiap fail input dan menyediakan data pekerja dalam pasangan nilai utama (<k, v>: <emp nama, gaji>). Lihat ilustrasi berikut.

<span class = Peta Mengurangi Ilustrasi "/>
  • Tahap combiner (teknik mencari) akan menerima masukan dari fasa Peta sebagai pasangan nilai utama dengan nama dan gaji pekerja. Dengan menggunakan teknik mencari, combiner akan memeriksa semua gaji pekerja untuk mencari pekerja gaji yang paling tinggi dalam setiap fail. Lihat coretan berikut.

<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;
}

Hasil yang diharapkan adalah seperti berikut -

<satish, 26000>

<gopal, 50000>

<kiran, 45000>

<manisha, 45000>

  • Fasa pengurangan - Bentuk setiap fail, anda akan dapati pekerja yang paling bergaji tinggi. Untuk mengelakkan redundansi, periksa semua pasangan <k, v> dan hapuskan pendua salinan, jika ada. Algoritma yang sama digunakan di antara empat pasangan <k, v>, yang datang dari empat fail input. Keluaran akhir harus seperti berikut -

<gopal, 50000>

Pengindeksan

Biasanya pengindeksan digunakan untuk menunjuk kepada data tertentu dan alamatnya. Ia melakukan pengindeksan batch pada fail input untuk Mapper tertentu.

Teknik pengindeksan yang biasanya digunakan dalam MapReduce dikenali sebagai indeks terbalik. Enjin carian seperti Google dan Bing menggunakan teknik pengindeksan terbalik. Marilah kita cuba memahami bagaimana Pengindeksan berfungsi dengan bantuan contoh mudah.

Contoh

Teks berikut adalah input untuk pengindeksan terbalik. Di sini T [0], T [1], dan t [2] adalah nama fail dan kandungan mereka dalam petikan berganda.

T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"

Selepas menggunakan algoritma Pengindeksan, kami mendapat output berikut -

"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}

Di sini "a": {2} membayangkan istilah "a" muncul dalam fail T [2]. Begitu juga, "adalah": {0, 1, 2} menunjukkan istilah "ada" muncul dalam fail T [0], T [1], dan T [2].

TF-IDF

TF-IDF adalah algoritma pemprosesan teks yang pendek untuk Frequency Frequency - Frekuensi Dokumentasi songsang. Ia adalah salah satu daripada algoritma analisis web biasa. Di sini, istilah 'frekuensi' merujuk kepada bilangan kali istilah muncul dalam dokumen.

Frekuensi Jangka (TF)

Ia mengukur seberapa sering istilah tertentu berlaku dalam dokumen. Ia dikira dengan beberapa kali perkataan muncul dalam dokumen dibahagikan dengan jumlah perkataan dalam dokumen itu.

TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)

Frekuensi Dokumen songsang (IDF)

Ia mengukur kepentingan istilah. Ia dikira dengan jumlah dokumen dalam pangkalan data teks yang dibahagikan dengan jumlah dokumen di mana istilah tertentu muncul.

Semasa pengkomputeran TF, semua istilah dianggap sama penting. Maksudnya, TF mengira kekerapan istilah untuk kata-kata biasa seperti "is", "a", "what", dan sebagainya. Oleh itu, kita perlu mengetahui terma-terma kerap semasa menaikkan yang jarang, dengan mengira yang berikut -

IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).

Algoritma diterangkan di bawah dengan bantuan contoh kecil.

Contoh

Pertimbangkan satu dokumen yang mengandungi 1000 perkataan, di mana perkataan sarang muncul 50 kali. TF untuk sarang kemudian (50/1000) = 0.05.

Sekarang, anggap kami mempunyai 10 juta dokumen dan perkataan sarang muncul dalam 1000 dari ini. Kemudian, IDF dikira sebagai log (10,000,000 / 1,000) = 4.

Berat TF-IDF adalah hasil kuantiti ini - 0.05 × 4 = 0.20.