MapReduce - Algoritma
Algoritma MapReduce berisi dua tugas penting, yaitu Map dan Reduce.
- Tugas peta dilakukan dengan menggunakan Mapper Class
- Tugas pengurangan dilakukan dengan menggunakan Kelas Peredam.
Kelas mapper mengambil masukan, membuat token, memetakan, dan mengurutkannya. Output dari kelas Mapper digunakan sebagai input oleh kelas Reducer, yang pada gilirannya mencari pasangan yang cocok dan menguranginya.
MapReduce menerapkan berbagai algoritma matematika untuk membagi tugas menjadi bagian-bagian kecil dan menetapkannya ke banyak sistem. Dalam istilah teknis, algoritma MapReduce membantu dalam mengirimkan tugas Map & Reduce ke server yang sesuai dalam sebuah cluster.
Algoritma matematika ini mungkin termasuk yang berikut -
- Sorting
- Searching
- Indexing
- TF-IDF
Penyortiran
Pengurutan adalah salah satu algoritma MapReduce dasar untuk memproses dan menganalisis data. MapReduce mengimplementasikan algoritme pengurutan untuk secara otomatis mengurutkan pasangan nilai kunci keluaran dari mapper menurut kuncinya.
Metode pengurutan diimplementasikan di kelas mapper itu sendiri.
Dalam fase Acak dan Urutkan, setelah memberi token pada nilai di kelas mapper, file Context class (kelas yang ditentukan pengguna) mengumpulkan kunci bernilai yang cocok sebagai koleksi.
Untuk mengumpulkan pasangan nilai kunci yang serupa (kunci perantara), kelas Mapper membutuhkan bantuan RawComparator kelas untuk mengurutkan pasangan nilai kunci.
Kumpulan pasangan nilai kunci perantara untuk Peredam tertentu diurutkan secara otomatis oleh Hadoop untuk membentuk nilai kunci (K2, {V2, V2,…}) sebelum disajikan ke Peredam.
Mencari
Pencarian memainkan peran penting dalam algoritma MapReduce. Ini membantu dalam fase penggabung (opsional) dan dalam fase Peredam. Mari kita coba memahami cara kerja Penelusuran dengan bantuan sebuah contoh.
Contoh
Contoh berikut menunjukkan bagaimana MapReduce menggunakan algoritma Pencarian untuk mengetahui detail karyawan yang memperoleh gaji tertinggi dalam kumpulan data karyawan tertentu.
Mari kita asumsikan kita memiliki data karyawan dalam empat file berbeda - A, B, C, dan D. Mari kita asumsikan juga ada catatan karyawan duplikat di keempat file karena mengimpor data karyawan dari semua tabel database berulang kali. Lihat ilustrasi berikut.
The Map phasememproses setiap file masukan dan memberikan data karyawan dalam pasangan nilai kunci (<k, v>: <nama emp, gaji>). Lihat ilustrasi berikut.
The combiner phase(teknik pencarian) akan menerima masukan dari fase Peta sebagai pasangan nilai kunci dengan nama dan gaji karyawan. Dengan menggunakan teknik pencarian, penggabung akan memeriksa semua gaji karyawan untuk menemukan karyawan dengan gaji tertinggi di setiap file. Lihat cuplikan 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 sebagai berikut -
|
Reducer phase- Bentuk setiap file, Anda akan menemukan karyawan bergaji tertinggi. Untuk menghindari redundansi, periksa semua pasangan <k, v> dan hilangkan entri duplikat, jika ada. Algoritma yang sama digunakan di antara empat pasangan <k, v>, yang berasal dari empat file masukan. Hasil akhirnya harus sebagai berikut -
<gopal, 50000>Pengindeksan
Biasanya pengindeksan digunakan untuk menunjuk ke data tertentu dan alamatnya. Ia melakukan pengindeksan batch pada file input untuk Mapper tertentu.
Teknik pengindeksan yang biasanya digunakan di MapReduce dikenal sebagai inverted index.Mesin pencari seperti Google dan Bing menggunakan teknik pengindeksan terbalik. Mari kita coba memahami cara kerja Pengindeksan dengan bantuan contoh sederhana.
Contoh
Teks berikut adalah masukan untuk pengindeksan terbalik. Di sini T [0], T [1], dan t [2] adalah nama file dan isinya dalam tanda kutip ganda.
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"Setelah menerapkan algoritma Pengindeksan, kami mendapatkan output berikut -
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}Di sini "a": {2} menyiratkan istilah "a" muncul di file T [2]. Demikian pula, "adalah": {0, 1, 2} menyiratkan istilah "adalah" muncul di file T [0], T [1], dan T [2].
TF-IDF
TF-IDF adalah algoritma pengolah teks yang merupakan kependekan dari Term Frequency - Inverse Document Frequency. Ini adalah salah satu algoritma analisis web yang umum. Di sini, istilah 'frekuensi' mengacu pada berapa kali sebuah istilah muncul dalam dokumen.
Frekuensi Jangka (TF)
Ini mengukur seberapa sering istilah tertentu muncul dalam dokumen. Ini dihitung dengan berapa kali kata muncul dalam dokumen dibagi dengan jumlah kata dalam dokumen itu.
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)Frekuensi Dokumen Terbalik (IDF)
Ini mengukur pentingnya suatu istilah. Ini dihitung dengan jumlah dokumen dalam database teks dibagi dengan jumlah dokumen di mana istilah tertentu muncul.
Saat menghitung TF, semua istilah dianggap sama pentingnya. Artinya, TF menghitung frekuensi istilah untuk kata-kata normal seperti "adalah", "a", "apa", dll. Oleh karena itu, kita perlu mengetahui istilah yang sering digunakan saat meningkatkan yang jarang, dengan menghitung yang berikut -
IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).Algoritme dijelaskan di bawah ini dengan bantuan contoh kecil.
Contoh
Pertimbangkan sebuah dokumen yang berisi 1000 kata, dimana kata tersebut hivemuncul 50 kali. TF untukhive kemudian (50/1000) = 0,05.
Sekarang, anggaplah kita memiliki 10 juta dokumen dan kata hivemuncul di 1000 ini. Kemudian, IDF dihitung sebagai log (10.000.000 / 1.000) = 4.
Bobot TF-IDF adalah hasil kali dari jumlah ini - 0,05 × 4 = 0,20.