K-Nearest Neighbor คืออะไร? ML Algorithm เพื่อจำแนกข้อมูล

อัลกอริทึมขับเคลื่อนโลกแห่งการเรียนรู้ของเครื่อง

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

ในหมู่พวกเขามีอัลกอริทึมที่มักระบุว่าขี้เกียจ แต่มันค่อนข้างมีประสิทธิภาพในการจำแนกจุดข้อมูล เรียกว่าอัลกอริธึมเพื่อนบ้านที่ใกล้ที่สุด k และมักถูกยกมาเป็นหนึ่งในสิ่งที่สำคัญที่สุด   การเรียนรู้ของเครื่อง   อัลกอริทึม

อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด k คืออะไร?

อัลกอริธึม k-nearest neighbors (KNN) เป็นวิธีการจัดหมวดหมู่ข้อมูลสำหรับการประเมินความน่าจะเป็นที่จุดข้อมูลจะกลายเป็นสมาชิกของกลุ่มใดกลุ่มหนึ่งหรืออีกกลุ่มหนึ่งโดยพิจารณาจากกลุ่มที่จุดข้อมูลที่ใกล้เคียงที่สุดอยู่

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

KNN คือการเรียนรู้แบบ ขี้เกียจ และอัลกอริธึม ที่ไม่มีพารามิเตอร์

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

ถือเป็นวิธีการที่ไม่ใช้พารามิเตอร์ เนื่องจากไม่มีการตั้งสมมติฐานใดๆ เกี่ยวกับการกระจายข้อมูลพื้นฐาน พูดง่ายๆ ก็คือ KNN พยายามกำหนดว่าจุดข้อมูลอยู่ในกลุ่มใดโดยดูที่จุดข้อมูลรอบๆ

พิจารณามีสองกลุ่มคือ A และ B

ในการพิจารณาว่าจุดข้อมูลอยู่ในกลุ่ม A หรือกลุ่ม B อัลกอริทึมจะพิจารณาสถานะของจุดข้อมูลที่อยู่ใกล้ๆ หากจุดข้อมูลส่วนใหญ่อยู่ในกลุ่ม A มีความเป็นไปได้สูงที่จุดข้อมูลดังกล่าวจะอยู่ในกลุ่ม A และในทางกลับกัน

กล่าวโดยย่อ KNN เกี่ยวข้องกับการจัดประเภทจุดข้อมูลโดยดูที่จุดข้อมูลที่มีคำอธิบายประกอบที่ใกล้ที่สุด หรือที่เรียกว่า เพื่อนบ้านที่ใกล้ที่สุด

อย่าสับสนการจัดประเภท K-NN กับการจัดกลุ่ม K-mean KNN เป็นอัลกอริธึมการจำแนกประเภทภายใต้การดูแลที่จัดประเภทจุดข้อมูลใหม่ตามจุดข้อมูลที่ใกล้ที่สุด ในทางกลับกัน K-mean clustering คือ an   ไม่ได้รับการดูแล   อัลกอริทึมการจัดกลุ่มที่จัดกลุ่มข้อมูลเป็นจำนวน K ของคลัสเตอร์

KNN ทำงานอย่างไร?

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

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

โดยพื้นฐานแล้ว KNN ดำเนินการกลไกการลงคะแนนเพื่อกำหนดคลาสของการสังเกตที่มองไม่เห็น ซึ่งหมายความว่าชั้นเรียนที่มีคะแนนเสียงข้างมากจะกลายเป็นชั้นเรียนของจุดข้อมูลที่เป็นปัญหา

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

ในการทำให้เป็นเปอร์สเปคทีฟ ให้พิจารณาจุดข้อมูล X ที่ไม่ได้จัดประเภท มีจุดข้อมูลหลายจุดที่มีหมวดหมู่ที่รู้จักคือ A และ B ในพล็อตแบบกระจาย

สมมติว่าจุดข้อมูล X ถูกวางไว้ใกล้กลุ่ม A

ดังที่คุณทราบ เราจัดประเภทจุดข้อมูลโดยดูที่จุดที่มีคำอธิบายประกอบที่ใกล้ที่สุด หากค่าของ K เท่ากับ 1 เราจะใช้เพื่อนบ้านที่ใกล้ที่สุดเพียงตัวเดียวในการกำหนดกลุ่มของจุดข้อมูล

ในกรณีนี้ จุดข้อมูล X อยู่ในกลุ่ม A เนื่องจากเพื่อนบ้านที่ใกล้ที่สุดอยู่ในกลุ่มเดียวกัน หากกลุ่ม A มีจุดข้อมูลมากกว่า 10 จุด และค่าของ K เท่ากับ 10 จุดข้อมูล X จะยังคงอยู่ในกลุ่ม A เนื่องจากเพื่อนบ้านที่ใกล้ที่สุดทั้งหมดอยู่ในกลุ่มเดียวกัน

สมมติว่ามีจุดข้อมูล Y ที่ไม่ได้จัดประเภทอื่นอยู่ระหว่างกลุ่ม A และกลุ่ม B หาก K เท่ากับ 10 เราจะเลือกกลุ่มที่ได้รับการโหวตมากที่สุด ซึ่งหมายความว่าเราจัดประเภท Y เป็นกลุ่มที่มีเพื่อนบ้านมากที่สุด ตัวอย่างเช่น ถ้า Y มีเพื่อนบ้านเจ็ดคนในกลุ่ม B และเพื่อนบ้านสามคนในกลุ่ม A เพื่อนบ้านนั้นจะอยู่ในกลุ่ม B

ความจริงที่ว่าลักษณนามกำหนดหมวดหมู่ด้วยจำนวนโหวตสูงสุดนั้นเป็นความจริงโดยไม่คำนึงถึงจำนวนหมวดหมู่ที่มีอยู่

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

มีสี่วิธีในการคำนวณการวัดระยะทางระหว่างจุดข้อมูลกับเพื่อนบ้านที่ใกล้ที่สุด: ระยะทางแบบยุคลิด ระยะทาง แมนฮัตตัน ระยะทาง แฮมมิ ง และ ระยะทางมินโควสกี จากทั้งสามนี้ ระยะทางแบบยุคลิดคือฟังก์ชันหรือเมตริกระยะทางที่ใช้บ่อยที่สุด

เพื่อตรวจสอบความถูกต้องของการจำแนกประเภท KNN a   เมทริกซ์ความสับสน   ถูกนำมาใช้. วิธีการทางสถิติอื่น ๆ เช่นการทดสอบอัตราส่วนความน่าจะเป็นยังใช้สำหรับการตรวจสอบ

ในกรณีของการถดถอย KNN ขั้นตอนส่วนใหญ่จะเหมือนกัน แทนที่จะกำหนดชั้นเรียนที่มีคะแนนเสียงสูงสุด ค่าเฉลี่ยของค่าเพื่อนบ้านจะถูกคำนวณและกำหนดให้กับจุดข้อมูลที่ไม่รู้จัก

เหตุใดจึงต้องใช้อัลกอริทึม KNN

การจัดประเภทเป็นปัญหาสำคัญในด้านวิทยาศาสตร์ข้อมูลและการเรียนรู้ของเครื่อง KNN เป็นหนึ่งในอัลกอริธึมที่เก่าแก่แต่แม่นยำที่สุดที่ใช้สำหรับการจำแนกรูปแบบและแบบจำลองการถดถอย

นี่คือบางส่วนของพื้นที่ที่สามารถใช้อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด k:

• อันดับเครดิต: อัลกอริธึม KNN ช่วยกำหนดอันดับเครดิตของแต่ละบุคคลโดยเปรียบเทียบกับอันดับเครดิตที่มีลักษณะคล้ายคลึงกัน
• การอนุมัติสินเชื่อ: คล้ายกับการจัดอันดับเครดิต อัลกอริธึมเพื่อนบ้านที่ใกล้ที่สุด k มีประโยชน์ในการระบุบุคคลที่มีแนวโน้มที่จะผิดนัดชำระหนี้โดยการเปรียบเทียบลักษณะของพวกเขากับบุคคลที่คล้ายคลึงกัน
• การประมวลผลข้อมูลล่วงหน้า: ชุดข้อมูลอาจมีค่าที่หายไปหลายค่า อัลกอริทึม KNN ใช้สำหรับกระบวนการที่เรียกว่า การใส่ข้อมูลที่ขาดหายไป ซึ่งประเมินค่าที่ขาดหายไป
• การจดจำรูปแบบ: ความสามารถของอัลกอริทึม KNN ในการระบุรูปแบบสร้างแอปพลิเคชันที่หลากหลาย ตัวอย่างเช่น ช่วยตรวจจับรูปแบบการใช้บัตรเครดิตและระบุรูปแบบที่ผิดปกติ การตรวจจับรูปแบบยังมีประโยชน์ในการระบุรูปแบบในพฤติกรรมการซื้อของลูกค้า
• การทำนายราคาหุ้น: เนื่องจากอัลกอริธึม KNN มีไหวพริบในการทำนายมูลค่าของเอนทิตีที่ไม่รู้จัก จึงมีประโยชน์ในการทำนายมูลค่าหุ้นในอนาคตโดยอิงจากข้อมูลในอดีต
• ระบบคำแนะนำ: เนื่องจาก KNN สามารถช่วยค้นหาผู้ใช้ที่มีลักษณะคล้ายคลึงกัน จึงสามารถใช้ในระบบคำแนะนำได้ ตัวอย่างเช่น สามารถใช้ในแพลตฟอร์มการสตรีมวิดีโอออนไลน์เพื่อแนะนำเนื้อหาที่ผู้ใช้มีแนวโน้มที่จะดูมากขึ้นโดยการวิเคราะห์สิ่งที่ผู้ใช้ที่คล้ายกันดู
• คอมพิวเตอร์วิทัศน์: อัลกอริทึม KNN ใช้สำหรับการจัดประเภทรูปภาพ เนื่องจากสามารถจัดกลุ่มจุดข้อมูลที่คล้ายคลึงกัน เช่น การจัดกลุ่มแมวเข้าด้วยกันและสุนัขในคลาสต่างๆ จึงมีประโยชน์ในหลายด้าน   วิสัยทัศน์คอมพิวเตอร์   แอปพลิเคชัน

วิธีการเลือกค่าที่เหมาะสมที่สุดของ K

ไม่มีวิธีเฉพาะในการกำหนดค่า K ที่ดีที่สุด กล่าวคือ จำนวนเพื่อนบ้านใน KNN ซึ่งหมายความว่าคุณอาจต้องทดลองกับค่าสองสามค่าก่อนที่จะตัดสินใจว่าจะใช้ค่าใดต่อไป

วิธีหนึ่งในการทำเช่นนี้คือการพิจารณา (หรือแกล้งทำเป็น) ว่าส่วนหนึ่งของตัวอย่างการฝึกอบรมนั้น "ไม่ทราบ" จากนั้น คุณสามารถจัดหมวดหมู่ข้อมูลที่ไม่รู้จักในชุดการทดสอบโดยใช้อัลกอริธึมเพื่อนบ้านที่ใกล้เคียงที่สุด k และวิเคราะห์ว่าการจัดหมวดหมู่ใหม่นั้นดีเพียงใดโดยเปรียบเทียบกับข้อมูลที่คุณมีอยู่แล้วในข้อมูลการฝึกอบรม

เมื่อต้องรับมือกับปัญหาแบบสองคลาส จะเป็นการดีกว่าที่จะเลือกค่า K เป็นค่าคี่ มิฉะนั้น อาจเกิดสถานการณ์ขึ้นโดยที่จำนวนเพื่อนบ้านในแต่ละคลาสเท่ากัน นอกจากนี้ ค่าของ K ต้องไม่เป็นทวีคูณของจำนวนคลาสที่มีอยู่

อีกวิธีในการเลือกค่าที่เหมาะสมที่สุดของ K คือการคำนวณ sqrt(N) โดยที่ N หมายถึงจำนวนตัวอย่างในชุดข้อมูลการฝึก

อย่างไรก็ตาม K ที่มีค่าต่ำกว่า เช่น K=1 หรือ K=2 อาจมีสัญญาณรบกวนและได้รับผลกระทบจากค่าผิดปกติ โอกาสในการสวมใส่มากเกินไปก็สูงเช่นกันในกรณีเช่นนี้

ในทางกลับกัน K ที่มีค่ามากกว่า ในกรณีส่วนใหญ่จะทำให้เกิดขอบเขตการตัดสินใจที่ราบรื่นขึ้น แต่ไม่ควรมีขนาดใหญ่เกินไป มิฉะนั้น กลุ่มที่มีจุดข้อมูลน้อยกว่าจะถูกโหวตออกจากกลุ่มอื่นเสมอ นอกจากนี้ K ที่ใหญ่กว่าจะมีราคาแพงในการคำนวณ

ข้อดีและข้อเสียของ KNN

ข้อดีที่สำคัญที่สุดอย่างหนึ่งของการใช้อัลกอริทึม KNN คือไม่จำเป็นต้องสร้างแบบจำลองหรือปรับแต่งพารามิเตอร์หลายตัว เนื่องจากเป็นอัลกอริธึมการเรียนรู้แบบขี้เกียจและไม่ใช่ผู้เรียนที่กระตือรือร้น จึงไม่จำเป็นต้องฝึกโมเดล แต่จะใช้จุดข้อมูลทั้งหมดในขณะที่คาดการณ์

แน่นอนว่ามันมีราคาแพงและใช้เวลานานในการคำนวณ แต่ถ้าคุณมีทรัพยากรการคำนวณที่จำเป็น คุณสามารถใช้ KNN เพื่อแก้ปัญหาการถดถอยและการจำแนกประเภทได้ แม้ว่าจะมีอัลกอริธึมที่เร็วกว่าหลายแบบที่สามารถสร้างการคาดการณ์ที่แม่นยำได้

แน่นอน KNN ไม่ใช่อัลกอริธึมการเรียนรู้ของเครื่องที่สมบูรณ์แบบ เนื่องจากตัวทำนาย KNN คำนวณทุกอย่างตั้งแต่เริ่มต้น จึงอาจไม่เหมาะสำหรับชุดข้อมูลขนาดใหญ่

KNN กับคำสาปแห่งมิติ

เมื่อคุณมีข้อมูลจำนวนมากในมือ การดึงข้อมูลที่รวดเร็วและตรงไปตรงมาออกจากข้อมูลนั้นอาจเป็นเรื่องยาก เพื่อการนั้น เราสามารถใช้อัลกอริธึมการลดมิติ ซึ่งโดยพื้นฐานแล้ว ทำให้ข้อมูล "เข้าถึงตรงประเด็น"

คำว่า "คำสาปแห่งมิติ" อาจให้ความรู้สึกเหมือนหลุดออกมาจากหนังไซไฟ แต่ความหมายก็คือข้อมูลมีคุณสมบัติมากเกินไป

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

อัลกอริธึมเพื่อนบ้านที่ใกล้เคียงที่สุด k มีความอ่อนไหวสูงต่อการโอเวอร์โหลดเนื่องจากการสาปแช่งของมิติ อย่างไรก็ตาม ปัญหานี้สามารถแก้ไขได้ด้วย   การใช้กำลังดุร้าย   ของอัลกอริทึม KNN แต่ใช้ไม่ได้กับชุดข้อมูลขนาดใหญ่

KNN ทำงานได้ไม่ดีหากมีคุณสมบัติมากเกินไป ดังนั้น เทคนิคการลดขนาด เช่น การวิเคราะห์องค์ประกอบหลัก (PCA) และ การเลือกคุณลักษณะ จะต้องดำเนินการในระหว่างขั้นตอนการเตรียมข้อมูล

KNN: อัลกอริธึมขี้เกียจที่ชนะใจ

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

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