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

ถาม: สมมติฐานพื้นฐานของ KNN คืออะไร?

ตอบ โดยถือว่าเพื่อนบ้านที่ใกล้ที่สุดมีป้ายกำกับที่คล้ายกัน

แล้วจะมีอะไรพังตรงไหนล่ะ? — เมื่อสมมติฐานไม่เป็นที่พอใจ กล่าวคือ ไม่มีเพื่อนบ้านที่ใกล้ที่สุดสำหรับจุดใดก็ตาม

ถาม มันเกิดขึ้นได้อย่างไร?

จะเกิดขึ้นได้เมื่อทุกจุดอยู่ห่างจากกัน?

ถาม โอเค สิ่งนั้นจะเกิดขึ้นเมื่อไหร่?

เราจะพยายามตอบคำถามนี้โดยเชื่อมโยงความใกล้ชิดกับระยะทางในไฮเปอร์คิวบ์จินตภาพด้านล่าง

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

ถาม: ลูกบาศก์ที่มีความยาวด้าน l ในขนาด d จะมีปริมาตรเท่าใด

สำหรับลูกบาศก์สามมิติ มันจะเป็น l ลูกบาศก์ ในทำนองเดียวกันสำหรับไฮเปอร์คิวบ์ที่มีความยาวด้าน l& ในมิติ d ปริมาตรของไฮเปอร์คิวบ์ดังกล่าวจะเป็น l กำลัง d

ถาม ปริมาณนี้จะเทียบเท่ากับเท่าใด

เนื่องจากจุด n มีการกระจายสม่ำเสมอทั่วทั้งไฮเปอร์คิวบ์หนึ่งหน่วย และเมื่อเราถือว่าไฮเปอร์คิวบ์ที่มีขนาดเล็กกว่านี้มีจุด k ปริมาตรจึงควรเท่ากับ k/n

ถาม หากเราต้องการได้เพื่อนบ้านที่ใกล้ที่สุด 10 ตัวในชุดข้อมูลที่มี 1,000 จุด มิติข้อมูลที่แตกต่างกันจะได้รับผลกระทบอย่างไร

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

ถาม แล้วปัญหาคืออะไร?

หมายความว่าเมื่อมิติเพิ่มขึ้น 10 จุดที่เราเริ่มต้น เกือบจะกระจายไปทั่วไฮเปอร์คิวบ์ทั้งหมด ดังนั้นจึงไม่มีแนวคิดเรื่องความใกล้เคียงในขณะนี้และทำลายสมมติฐานของอัลกอริทึม

ถาม เราสามารถเพิ่มขนาดชุดข้อมูลเพื่อแก้ไขปัญหานี้ได้หรือไม่

ในที่นี้ ขนาดข้อมูลที่พิจารณาคือ 1,000 จุดข้อมูล และเพื่อนบ้านที่ใกล้ที่สุดคือ 10 สมมติว่าถ้าเรากำหนดความยาวด้าน l เป็น 0.1 แล้วเท่ากับจำนวนจุดที่ต้องรักษา l นั้น จากนั้นขนาดข้อมูลจะต้องเพิ่มกำลังเป็น 10 ซึ่งจะขยายเร็วเกินไป & แทบจะเป็นไปไม่ได้เลยที่จะหาชุดข้อมูลขนาดใหญ่เช่นนี้

บทสรุป :เนื่องจากมิติข้อมูลที่สูงทำลายสมมติฐานของ KNN เราจึงไม่ควรใช้ KNN สำหรับชุดข้อมูลที่มีมิติสูง

ข้อมูลอ้างอิง:

ฉันรู้สึกขอบคุณ Kilian Weinberger สำหรับการบรรยายที่น่าทึ่งเกี่ยวกับ ML ความคิดที่นำเสนอที่นี่คือบทสรุปจากสิ่งที่ฉันเข้าใจจากหนึ่งในบทความของ KNN