MapReduce - อัลกอริทึม

อัลกอริทึม MapReduce ประกอบด้วยสองงานที่สำคัญ ได้แก่ แผนที่และลด

• งานแผนที่ทำได้โดยใช้ Mapper Class
• งานลดจะทำโดยวิธีการลดระดับ

คลาส Mapper รับอินพุตโทเค็นแมปและจัดเรียงข้อมูล เอาต์พุตของคลาส Mapper ถูกใช้เป็นอินพุตโดยคลาส Reducer ซึ่งจะค้นหาคู่ที่ตรงกันและลดจำนวนคู่ลง

MapReduce ใช้อัลกอริธึมทางคณิตศาสตร์ต่างๆเพื่อแบ่งงานออกเป็นส่วนเล็ก ๆ และกำหนดให้กับหลายระบบ ในแง่เทคนิคอัลกอริทึม MapReduce ช่วยในการส่งงานแผนที่และลดไปยังเซิร์ฟเวอร์ที่เหมาะสมในคลัสเตอร์

อัลกอริทึมทางคณิตศาสตร์เหล่านี้อาจรวมถึงสิ่งต่อไปนี้ -

• Sorting
• Searching
• Indexing
• TF-IDF

การเรียงลำดับ

การเรียงลำดับเป็นหนึ่งในอัลกอริทึม MapReduce พื้นฐานในการประมวลผลและวิเคราะห์ข้อมูล MapReduce ใช้อัลกอริทึมการเรียงลำดับเพื่อจัดเรียงคู่คีย์ - ค่าเอาต์พุตจากตัวทำแผนที่โดยใช้คีย์โดยอัตโนมัติ

• วิธีการเรียงลำดับถูกนำไปใช้ในคลาส mapper เอง

• ในเฟสสุ่มและเรียงลำดับหลังจากโทเค็นค่าในคลาส mapper แล้วไฟล์ Context คลาส (คลาสที่ผู้ใช้กำหนดเอง) รวบรวมคีย์มูลค่าที่ตรงกันเป็นคอลเลกชัน

• ในการรวบรวมคู่คีย์ - ค่าที่คล้ายกัน (คีย์กลาง) คลาส Mapper จะช่วย RawComparator คลาสเพื่อจัดเรียงคู่คีย์ - ค่า

• ชุดของคู่คีย์ - ค่าระดับกลางสำหรับตัวลดที่กำหนดจะถูกจัดเรียงโดย Hadoop โดยอัตโนมัติเพื่อสร้างคีย์ - ค่า (K2, {V2, V2, …}) ก่อนที่จะนำเสนอต่อตัวลด

กำลังค้นหา

การค้นหามีบทบาทสำคัญในอัลกอริทึม MapReduce ช่วยในเฟส Combiner (ทางเลือก) และในเฟส Reducer ให้เราพยายามทำความเข้าใจว่า Searching ทำงานอย่างไรโดยใช้ตัวอย่าง

ตัวอย่าง

ตัวอย่างต่อไปนี้แสดงให้เห็นว่า MapReduce ใช้อัลกอริทึมการค้นหาเพื่อค้นหารายละเอียดของพนักงานที่ได้รับเงินเดือนสูงสุดในชุดข้อมูลพนักงานที่กำหนดอย่างไร

• สมมติว่าเรามีข้อมูลพนักงานในสี่ไฟล์ที่แตกต่างกัน - A, B, C และ D นอกจากนี้เรายังถือว่ามีประวัติพนักงานที่ซ้ำกันในทั้งสี่ไฟล์เนื่องจากการนำเข้าข้อมูลพนักงานจากตารางฐานข้อมูลทั้งหมดซ้ำ ๆ ดูภาพประกอบต่อไปนี้

• The Map phaseประมวลผลไฟล์อินพุตแต่ละไฟล์และจัดเตรียมข้อมูลพนักงานในคู่คีย์ - ค่า (<k, v>: <emp name, เงินเดือน>) ดูภาพประกอบต่อไปนี้

• The combiner phase(เทคนิคการค้นหา) จะรับอินพุตจากเฟสแผนที่เป็นคู่คีย์ - ค่าพร้อมชื่อพนักงานและเงินเดือน การใช้เทคนิคการค้นหาผู้รวมจะตรวจสอบเงินเดือนพนักงานทั้งหมดเพื่อค้นหาพนักงานที่ได้รับเงินเดือนสูงสุดในแต่ละไฟล์ ดูตัวอย่างต่อไปนี้

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

ผลที่คาดว่าจะได้รับมีดังนี้ -

<อิ่ม 26000> <gopal, 50000> <kiran, 45000> <manisha, 45000>

• Reducer phase- สร้างแต่ละไฟล์คุณจะพบพนักงานที่ได้รับเงินเดือนสูงสุด เพื่อหลีกเลี่ยงความซ้ำซ้อนให้ตรวจสอบคู่ <k, v> ทั้งหมดและกำจัดรายการที่ซ้ำกันถ้ามี อัลกอริทึมเดียวกันใช้ระหว่างคู่ <k, v> สี่คู่ซึ่งมาจากไฟล์อินพุตสี่ไฟล์ ผลลัพธ์สุดท้ายควรเป็นดังนี้ -

<gopal, 50000>

การจัดทำดัชนี

โดยปกติการจัดทำดัชนีจะใช้เพื่อชี้ไปที่ข้อมูลเฉพาะและที่อยู่ ดำเนินการจัดทำดัชนีแบทช์ในไฟล์อินพุตสำหรับ Mapper เฉพาะ

เทคนิคการสร้างดัชนีที่ปกติใช้ใน MapReduce เรียกว่า inverted index.เครื่องมือค้นหาเช่น Google และ Bing ใช้เทคนิคการสร้างดัชนีกลับด้าน ให้เราพยายามทำความเข้าใจว่าการจัดทำดัชนีทำงานอย่างไรโดยใช้ตัวอย่างง่ายๆ

ตัวอย่าง

ข้อความต่อไปนี้เป็นข้อมูลสำหรับการจัดทำดัชนีกลับหัว ที่นี่ T [0], T [1] และ t [2] คือชื่อไฟล์และเนื้อหาอยู่ในเครื่องหมายอัญประกาศคู่

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

หลังจากใช้อัลกอริทึมการทำดัชนีเราจะได้ผลลัพธ์ดังต่อไปนี้ -

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

นี่คือ "a": {2} แสดงนัยถึงคำว่า "a" ปรากฏในไฟล์ T [2] ในทำนองเดียวกัน "is": {0, 1, 2} มีความหมายโดยนัยของคำว่า "is" ปรากฏในไฟล์ T [0], T [1] และ T [2]

TF-IDF

TF-IDF เป็นอัลกอริทึมการประมวลผลข้อความซึ่งย่อมาจาก Term Frequency - Inverse Document Frequency เป็นหนึ่งในอัลกอริทึมการวิเคราะห์เว็บทั่วไป ในที่นี้คำว่า 'ความถี่' หมายถึงจำนวนครั้งที่คำที่ปรากฏในเอกสาร

ระยะความถี่ (TF)

เป็นการวัดความถี่ที่คำศัพท์หนึ่ง ๆ เกิดขึ้นในเอกสาร คำนวณโดยจำนวนครั้งที่คำปรากฏในเอกสารหารด้วยจำนวนคำทั้งหมดในเอกสารนั้น

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

ความถี่เอกสารผกผัน (IDF)

เป็นการวัดความสำคัญของคำศัพท์ คำนวณโดยจำนวนเอกสารในฐานข้อมูลข้อความหารด้วยจำนวนเอกสารที่มีคำเฉพาะปรากฏขึ้น

ในขณะที่คำนวณ TF คำศัพท์ทั้งหมดถือว่ามีความสำคัญเท่าเทียมกัน นั่นหมายความว่า TF จะนับความถี่ของคำศัพท์สำหรับคำปกติเช่น "is", "a", "what" ฯลฯ ดังนั้นเราจึงจำเป็นต้องทราบคำศัพท์ที่ใช้บ่อยในขณะที่ขยายคำที่หายากโดยคำนวณดังต่อไปนี้ -

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

อัลกอริทึมอธิบายไว้ด้านล่างด้วยความช่วยเหลือของตัวอย่างเล็ก ๆ

ตัวอย่าง

พิจารณาเอกสารที่มีคำ 1,000 คำซึ่งคำนั้น hiveปรากฏ 50 ครั้ง TF สำหรับhive คือ (50/1000) = 0.05

ตอนนี้สมมติว่าเรามีเอกสาร 10 ล้านฉบับและคำว่า hiveปรากฏใน 1,000 รายการ จากนั้น IDF จะถูกคำนวณเป็นบันทึก (10,000,000 / 1,000) = 4

น้ำหนัก TF-IDF เป็นผลคูณจากปริมาณเหล่านี้ - 0.05 × 4 = 0.20