Skip to content
กลับไปยังผลการค้นหา

เพื่อนบ้านใกล้ที่สุด K ตัว (K-Nearest Neighbors)

ผู้เสนอ
Cover, T.M. & Hart, P.E.
ปี
1967
ประเภท
Instance-based (non-parametric) learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

K-Nearest Neighbors (KNN) ซึ่งได้รับการวางรากฐานอย่างเป็นทางการโดย Cover และ Hart ในปี 1967 เป็นวิธีการแบบไม่ใช้พารามิเตอร์ (non-parametric) และแบบอิงตัวอย่าง (instance-based) ที่จำแนกประเภทหรือทำนายการสังเกตใหม่โดยพิจารณาจากตัวอย่างที่ใกล้ที่สุด k ตัวในข้อมูลการฝึกอบรม สำหรับการจำแนกประเภท จะใช้วิธีการลงคะแนนเสียงข้างมากในหมู่เพื่อนบ้านเหล่านั้น สำหรับการถดถอย จะหาค่าเฉลี่ยของค่าของเพื่อนบ้านเหล่านั้น

แนวคิดเบื้องหลังวิธีการ

แนวคิดนั้นง่าย: อินพุตที่คล้ายกันมักจะให้เอาต์พุตที่คล้ายกัน ในการติดป้ายจุดใหม่ KNN จะค้นหาตัวอย่างการฝึกอบรมจำนวนเล็กน้อยที่อยู่ใกล้ที่สุดในปริมาณลักษณะเฉพาะ (feature space) และให้ตัวอย่างเหล่านั้นตัดสินใจ จะไม่มีการปรับสมการใด ๆ ล่วงหน้า — ข้อมูลการฝึกอบรมนั้นเองคือโมเดล และการทำนายจะเกิดขึ้นเมื่อมีจุดใหม่เข้ามาเท่านั้น

ประวัติศาสตร์

การจำแนกรูปแบบเพื่อนบ้านที่ใกล้ที่สุด (Nearest-neighbor pattern classification) ได้รับการวางรากฐานทางสถิติอย่างเป็นทางการโดย Thomas Cover และ Peter Hart ในบทความปี 1967 ของพวกเขาในวารสาร IEEE Transactions on Information Theory ซึ่งวิเคราะห์อัตราข้อผิดพลาดของกฎเพื่อนบ้านที่ใกล้ที่สุด (nearest-neighbor rule) KNN กลายเป็นหนึ่งในวิธีการเรียนรู้แบบอิงตัวอย่าง (instance-based learning) ที่เก่าแก่และยั่งยืนที่สุด และยังคงเป็นตัวจำแนกประเภทพื้นฐานมาตรฐาน

ควรใช้เมื่อใด

ใช้ KNN สำหรับการจำแนกประเภทหรือการทำนายบนข้อมูลแบบตาราง (tabular data) ที่มีปริมาณลักษณะเฉพาะแบบต่อเนื่อง แบบไบนารี หรือแบบอันดับ (ordinal) และมีจำนวนการสังเกตอย่างน้อยประมาณ 30 รายการ วิธีการนี้ไม่ได้สมมติการกระจายตัวแบบเฉพาะเจาะจงใด ๆ แต่ต้องการให้ปริมาณลักษณะเฉพาะได้รับการปรับมาตรฐาน (normalized) และจำนวนปริมาณลักษณะเฉพาะยังคงน้อยเมื่อเทียบกับขนาดตัวอย่าง (p น้อยกว่า n มากเป็นที่ต้องการ) ในตัวอย่างขนาดเล็กหรือมิติสูง คำสาปของมิติ (curse of dimensionality) จะครอบงำ — ระยะห่างของเพื่อนบ้านจะไม่มีข้อมูล และโมเดลแบบใช้พารามิเตอร์ (parametric model) เช่น การถดถอยโลจิสติก (logistic regression) หรือ Naive Bayes จะเป็นทางเลือกที่ดีกว่า

ข้อจำกัดและข้อควรพิจารณา

  • อ่อนไหวต่อการปรับสเกลปริมาณลักษณะเฉพาะ หากไม่มีการปรับมาตรฐาน ปริมาณลักษณะเฉพาะที่มีสเกลขนาดใหญ่จะครอบงำระยะทาง
  • ประสิทธิภาพลดลงอย่างรวดเร็วในมิติสูง (คำสาปของมิติ) ซึ่งระยะห่างของเพื่อนบ้านจะสูญเสียความหมาย
  • ทุกการทำนายต้องสแกนชุดข้อมูลการฝึกอบรมทั้งหมด ซึ่งจะช้าในขั้นตอนการทำนายกับข้อมูลขนาดใหญ่
  • ต้องการขนาดตัวอย่างปานกลางเป็นอย่างน้อย ในตัวอย่างขนาดเล็ก ระยะห่างของเพื่อนบ้านที่ใกล้ที่สุดจะไม่มีความหมาย

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • แนวคิดง่ายและอธิบายได้ง่าย: ไม่มีสมการในขั้นตอนการฝึกอบรม ข้อมูลคือโมเดล
  • ไม่ใช้พารามิเตอร์ — ไม่ได้สมมติเกี่ยวกับการกระจายตัวพื้นฐาน
  • จัดการปัญหาแบบหลายคลาส (multi-class) และขอบเขตการตัดสินใจที่ซับซ้อน ไม่เป็นเชิงเส้น (nonlinear) ได้ตามธรรมชาติ
  • ใช้ได้ทั้งกับการจำแนกประเภทและการถดถอยด้วยแนวคิดพื้นฐานเดียวกัน

การประยุกต์ใช้

  • การจำแนกข้อมูลแบบตารางออกเป็นสองหมวดหมู่หรือมากกว่า
  • การทำนายเชิงตัวเลข (regression) โดยการหาค่าเฉลี่ยของตัวอย่างที่ใกล้ที่สุด
  • ตัวจำแนกประเภทพื้นฐานที่เรียบง่ายและตีความได้ ก่อนที่จะลองใช้โมเดลที่ซับซ้อนกว่า
  • การรู้จำรูปแบบ (Pattern recognition) ที่ความคล้ายคลึงกับตัวอย่างที่รู้จักเป็นตัวขับเคลื่อนการตัดสินใจ

วิธีการทำงาน

วิธีการทำงาน

1

สำหรับการสังเกตใหม่ KNN จะวัดระยะห่างจากตัวอย่างการฝึกอบรมแต่ละตัว โดยทั่วไปจะใช้ระยะทางแบบยุคลิด (Euclidean distance) ข้ามปริมาณลักษณะเฉพาะ เนื่องจากระยะทางมีความอ่อนไหวต่อสเกล ปริมาณลักษณะเฉพาะจึงต้องได้รับการปรับมาตรฐานก่อน — มิฉะนั้น ตัวแปรที่วัดในสเกลตัวเลขขนาดใหญ่จะครอบงำการคำนวณและบิดเบือนว่าเพื่อนบ้านใดถือว่าใกล้ที่สุด

สูตร
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

จะเลือกจุดฝึกอบรม k จุดที่มีระยะทางน้อยที่สุดไปยังการสังเกตใหม่เป็นเพื่อนบ้าน ค่าของ k จะควบคุมว่าการตัดสินใจนั้นมีความเฉพาะเจาะจงเพียงใด: k ขนาดเล็กจะติดตามข้อมูลอย่างใกล้ชิด แต่จะอ่อนไหวต่อสัญญาณรบกวน (noise) ในขณะที่ k ขนาดใหญ่จะทำให้ขอบเขตเรียบขึ้น ควรเลือก k โดยการตรวจสอบไขว้ (cross-validation) (เช่น วิธีการข้อศอก (elbow method)) แทนที่จะคาดเดา

3

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

สูตร
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

ข้อผิดพลาดที่พบบ่อย

  • การข้ามการปรับมาตรฐานปริมาณลักษณะเฉพาะ ทำให้ตัวแปรที่มีสเกลขนาดใหญ่เพียงตัวเดียวควบคุมระยะทางโดยไม่เปิดเผย
  • การเลือก k ด้วยตนเองแทนที่จะเลือกด้วยการตรวจสอบไขว้
  • การใช้ KNN กับปริมาณลักษณะเฉพาะจำนวนมากและจำนวนการสังเกตน้อย ซึ่งอัตราส่วนมิติ/ตัวอย่างทำให้วิธีการล้มเหลว
  • การรายงานเฉพาะความแม่นยำ (accuracy) แทนที่จะเป็นความเที่ยงตรง (precision) การระลึก (recall) ค่า F1 และเมทริกซ์ความสับสน (confusion matrix)

คำถามที่พบบ่อย

ฉันจะเลือกค่า k ได้อย่างไร?

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

ทำไมฉันต้องปรับมาตรฐานปริมาณลักษณะเฉพาะ?

KNN ตัดสินว่าใคร 'ใกล้ที่สุด' โดยใช้ระยะทาง ซึ่งอ่อนไหวต่อสเกล หากปริมาณลักษณะเฉพาะหนึ่งมีสเกลตัวเลขที่ใหญ่กว่ามากเมื่อเทียบกับปริมาณอื่น ๆ มันจะครอบงำระยะทางและบิดเบือนชุดเพื่อนบ้าน การปรับมาตรฐานปริมาณลักษณะเฉพาะ (เช่น ด้วย StandardScaler) เป็นสิ่งจำเป็นเพื่อให้แต่ละปริมาณลักษณะเฉพาะมีส่วนร่วมอย่างยุติธรรม

ทำไม KNN จึงมีปัญหากับปริมาณลักษณะเฉพาะจำนวนมาก?

ในปริมาณลักษณะเฉพาะสูง จุดทั้งหมดจะอยู่ห่างกันเท่า ๆ กัน — คำสาปของมิติ — ดังนั้นเพื่อนบ้านที่ 'ใกล้ที่สุด' จึงไม่ใกล้กันอย่างมีความหมายอีกต่อไป ประสิทธิภาพของ KNN ลดลงอย่างรวดเร็ว และโมเดลแบบใช้พารามิเตอร์ เช่น Naive Bayes หรือ logistic regression มักจะดีกว่า การรักษา p ให้เล็กกว่า n มากจะช่วยได้

มีขั้นตอนการฝึกอบรมหรือไม่?

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

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว