ในทางสถิติอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุดk ตัว ( k -NN ) เป็น วิธี การเรียนรู้แบบมีผู้กำกับดูแลที่ไม่ใช้พารามิเตอร์ อัลกอริทึม นี้ได้รับการพัฒนาครั้งแรกโดยEvelyn FixและJoseph Hodgesในปี 1951 ^{[ 1 ]}และต่อมาได้รับการขยายโดยThomas Cover [ ^{2 ] ใน}การจำแนกประเภท ตัวอย่างใหม่จะได้รับป้ายกำกับตามป้ายกำกับของ ตัวอย่างการฝึกอบรมที่ใกล้ที่สุด kตัว ในการถดถอย การทำนายจะคำนวณจากค่าของเพื่อนบ้านเหล่านั้น^{[ 1 ] [ 2 ]} ส่วนใหญ่แล้วจะใช้สำหรับการจำแนกประเภทเป็น ตัวจำแนก k -NNซึ่งผลลัพธ์คือการเป็นสมาชิกของคลาส วัตถุจะถูกจำแนกโดยการลงคะแนนเสียงส่วนใหญ่ของเพื่อนบ้าน โดยวัตถุจะถูกกำหนดให้กับคลาสที่พบมากที่สุดในบรรดาเพื่อนบ้านที่ใกล้ที่สุดk ตัว ( kเป็นจำนวนเต็ม บวก โดยทั่วไปจะมีค่าน้อย) ถ้าk  = 1 วัตถุจะถูกกำหนดให้กับคลาสของเพื่อนบ้านที่ใกล้ที่สุดเพียงตัวเดียว

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

สำหรับทั้งการจำแนกและการถดถอย เทคนิคที่มีประโยชน์อย่างหนึ่งคือการกำหนดน้ำหนักให้กับการมีส่วนร่วมของเพื่อนบ้าน เพื่อให้เพื่อนบ้านที่อยู่ใกล้กว่ามีส่วนร่วมในค่าเฉลี่ยมากกว่าเพื่อนบ้านที่อยู่ไกลออกไป ตัวอย่างเช่น รูปแบบการถ่วงน้ำหนักทั่วไปประกอบด้วยการให้น้ำหนักเพื่อนบ้านแต่ละรายเท่ากับ 1/ dโดยที่dคือระยะห่างจากเพื่อนบ้าน^{[ 3 ]}

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

ลักษณะเฉพาะ (บางครั้งอาจเป็นข้อเสีย) ของ อัลกอริทึม k -NN คือความไวต่อโครงสร้างเฉพาะที่ของข้อมูล ใน การจำแนกประเภท k -NN ฟังก์ชันจะถูกประมาณค่าเฉพาะที่เท่านั้น และการคำนวณทั้งหมดจะถูกเลื่อนออกไปจนกว่าจะมีการประเมินฟังก์ชัน เนื่องจากอัลกอริทึมนี้อาศัยระยะทาง หากคุณลักษณะแสดงถึงหน่วยทางกายภาพที่แตกต่างกันหรือมีขนาดที่แตกต่างกันอย่างมาก การปรับมาตรฐาน ข้อมูลการฝึกอบรม ตามคุณลักษณะสามารถปรับปรุงความแม่นยำได้อย่างมาก^{[ 4 ]}

สมมติว่าเรามีคู่ที่รับค่าในช่วงโดยที่Yคือป้ายกำกับคลาสของXดังนั้นสำหรับ(และการกระจายความน่าจะเป็น) กำหนดให้ค่ามาตรฐานบางอย่างบนและจุดให้เป็นการเรียงลำดับใหม่ของข้อมูลฝึกฝนโดยที่ ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\จุด ,(X_{n},Y_{n})}$${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$${\displaystyle X|Y=r\sim P_{r}}$${\displaystyle r=1,2}$${\displaystyle P_{r}}$${\displaystyle \|\cdot \|}$${\displaystyle \mathbb {R} ^{d}}$${\displaystyle x\in \mathbb {R} ^{d}}$${\displaystyle (X_{(1)},Y_{(1)}),\dots ,(X_{(n)},Y_{(n)})}$${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(n)}-x\|}$

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

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

เมตริกระยะทางที่ใช้กันทั่วไปสำหรับตัวแปรต่อเนื่องคือระยะทางแบบยุคลิดสำหรับตัวแปรไม่ต่อเนื่อง เช่น สำหรับการจำแนกข้อความ สามารถใช้เมตริกอื่นได้ เช่นเมตริกการทับซ้อน (หรือระยะทางแฮมมิง ) ตัวอย่างเช่นในบริบทของ ข้อมูลไมโครอาร์เรย์การแสดงออก ของยีนk -NN ได้ถูกนำมาใช้ร่วมกับสัมประสิทธิ์สหสัมพันธ์ เช่น เพียร์สันและสเปียร์แมน เป็นเมตริก^{[ 5 ]}บ่อยครั้งที่ความแม่นยำในการจำแนกของk -NN สามารถปรับปรุงได้อย่างมีนัยสำคัญหากเรียนรู้เมตริกระยะทางด้วยอัลกอริธึมเฉพาะทาง เช่นเพื่อนบ้านที่ใกล้ที่สุดที่มีระยะขอบขนาดใหญ่หรือ การ วิเคราะห์ ส่วนประกอบของเพื่อนบ้าน

ข้อเสียของการจำแนกประเภทแบบ "การลงคะแนนเสียงข้างมาก" พื้นฐานเกิดขึ้นเมื่อการกระจายของคลาสเบี่ยงเบน นั่นคือ ตัวอย่างของคลาสที่เกิดขึ้นบ่อยกว่ามักจะครอบงำการทำนายของตัวอย่างใหม่ เนื่องจากมักจะพบได้ทั่วไปในกลุ่ม เพื่อนบ้านที่ใกล้ที่สุด kตัว เนื่องจากมีจำนวนมาก^{[ 7 ]}วิธีหนึ่งที่จะเอาชนะปัญหานี้ได้คือการถ่วงน้ำหนักการจำแนกประเภท โดยคำนึงถึงระยะห่างจากจุดทดสอบไปยัง เพื่อนบ้านที่ใกล้ที่สุด k ตัวแต่ละตัว คลาส (หรือค่า ในปัญหาการถดถอย) ของ จุดที่ใกล้ที่สุด k จุดแต่ละ จุดจะถูกคูณด้วยน้ำหนักที่เป็นสัดส่วนผกผันกับระยะห่างจากจุดนั้นไปยังจุดทดสอบ อีกวิธีหนึ่งที่จะเอาชนะความเบี่ยงเบนได้คือการสร้างนามธรรมในการแสดงข้อมูล ตัวอย่างเช่น ในแผนที่จัดระเบียบตนเอง (SOM) แต่ละโหนดเป็นตัวแทน (ศูนย์กลาง) ของกลุ่มจุดที่คล้ายกัน โดยไม่คำนึงถึงความหนาแน่นในข้อมูลการฝึกอบรมดั้งเดิม จากนั้นสามารถใช้ k -NN กับ SOM ได้

การเลือกค่าk ที่ดีที่สุด ขึ้นอยู่กับข้อมูล โดยทั่วไปแล้ว ค่าk ที่มากขึ้น จะช่วยลดผลกระทบของสัญญาณรบกวนต่อการจำแนกประเภท^{[ 8 ]}แต่จะทำให้ขอบเขตระหว่างคลาสไม่ชัดเจนสามารถเลือก ค่า k ที่ดีได้โดยใช้เทคนิค ฮิวริสติก ต่างๆ (ดูการเพิ่มประสิทธิภาพไฮเปอร์พารามิเตอร์ ) กรณีพิเศษที่คลาสถูกทำนายว่าเป็นคลาสของตัวอย่างการฝึกอบรมที่ใกล้ที่สุด (เช่น เมื่อk = 1) เรียกว่าอัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด

ความแม่นยำของ อัลกอริทึม k -NN อาจลดลงอย่างมากหากมีฟีเจอร์ที่มีเสียงรบกวนหรือไม่เกี่ยวข้อง หรือหากขนาดของฟีเจอร์ไม่สอดคล้องกับความสำคัญของฟีเจอร์นั้น งานวิจัยจำนวนมากมุ่งเน้นไปที่การเลือกหรือปรับขนาดฟีเจอร์เพื่อปรับปรุงการจำแนกประเภท แนวทางที่เป็นที่นิยมอย่างยิ่งคือการใช้ อัลก อริทึมเชิงวิวัฒนาการเพื่อเพิ่มประสิทธิภาพการปรับขนาดฟีเจอร์^{[ 9 ]}อีกแนวทางที่เป็นที่นิยมคือการปรับขนาดฟีเจอร์โดยใช้ข้อมูลร่วมกันของข้อมูลการฝึกอบรมกับคลาสการฝึกอบรม

ในปัญหาการจำแนกประเภทแบบไบนารี (สองคลาส) การเลือก kให้เป็นเลขคี่จะเป็นประโยชน์ เนื่องจากจะช่วยหลีกเลี่ยงการลงคะแนนที่เสมอกัน วิธีที่นิยมในการเลือก k ที่เหมาะสมที่สุดตามประสบการณ์ ในสถานการณ์นี้คือการใช้วิธีบูตสแตรป^{[ 10 ]}

ตัวจำแนกประเภทเพื่อนบ้านที่ใกล้ที่สุดที่เข้าใจง่ายที่สุดคือตัวจำแนกประเภทเพื่อนบ้านที่ใกล้ที่สุดตัวเดียวที่กำหนดจุดxให้กับคลาสของเพื่อนบ้านที่ใกล้ที่สุดในพื้นที่คุณลักษณะ นั่นคือ ${\displaystyle C_{n}^{1nn}(x)=Y_{(1)}}$

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

ตัว จำแนกเพื่อนบ้านที่ใกล้ที่สุด kตัวสามารถมองได้ว่าเป็นการกำหนดน้ำหนักให้กับเพื่อนบ้านที่ใกล้ที่สุดk ตัวและ กำหนดน้ำหนัก เป็น 0 ให้กับตัวอื่นๆ ทั้งหมด ซึ่งสามารถขยายไปสู่ตัวจำแนกเพื่อนบ้านที่ใกล้ที่สุดแบบมีน้ำหนักได้ กล่าวคือ เพื่อนบ้านที่ใกล้ที่สุดลำดับที่ iจะได้รับน้ำหนักโดยที่ผลลัพธ์ที่คล้ายกันเกี่ยวกับความสอดคล้องอย่างเข้มแข็งของตัวจำแนกเพื่อนบ้านที่ใกล้ที่สุดแบบมีน้ำหนักก็ยังคงใช้ได้^{[ 11 ]}${\displaystyle 1/k}$${\displaystyle w_{ni}}$${\textstyle \sum _{i=1}^{n}w_{ni}=1}$

ให้แทนตัวจำแนกที่ใกล้ที่สุดแบบถ่วงน้ำหนักด้วยน้ำหนักภายใต้เงื่อนไขความสม่ำเสมอ ซึ่งในทฤษฎีเชิงอะซิมโทติกคือตัวแปรเงื่อนไขที่ต้องใช้สมมติฐานเพื่อแยกแยะพารามิเตอร์ด้วยเกณฑ์บางอย่าง บนการกระจายคลาส ความเสี่ยงส่วนเกินมีการขยายเชิงอะซิมโทติก ดังต่อไปนี้ ^{[ 12 ]} สำหรับค่าคงที่และโดย ที่และ${\displaystyle C_{n}^{wnn}}$${\displaystyle \{w_{ni}\__{i=1}^{n}}$$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{wnn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left(B_{1}s_{n}^{2}+B_{2}t_{n}^{2}\right)\{1+o(1)\},}$$${\displaystyle B_{1}}$${\displaystyle B_{2}}$${\displaystyle s_{n}^{2}=\sum _{i=1}^{n}w_{ni}^{2}}$${\displaystyle t_{n}=n^{-2/d}\sum _{i=1}^{n}w_{ni}\left\{i^{1+2/d}-(i-1)^{1+2/d}\right\}}$

รูปแบบการถ่วงน้ำหนักที่เหมาะสมที่สุด ซึ่ง จะ สร้างความสมดุลให้กับทั้งสองเงื่อนไขในการแสดงผลข้างต้น มีดังนี้: กำหนดให้ สำหรับและ สำหรับ${\displaystyle \{w_{ni}^{*}\__{i=1}^{n}}$${\displaystyle k^{*}=\lfloor Bn^{\frac {4}{d+4}}\rfloor }$$${\displaystyle w_{ni}^{*}={\frac {1}{k^{*}}}\left[1+{\frac {d}{2}}-{\frac {d}{2{k^{*}}^{2/d}}}\{i^{1+2/d}-(i-1)^{1+2/d}\}\right]}$$${\displaystyle i=1,2,\dots ,k^{*}}$$${\displaystyle w_{ni}^{*}=0}$$${\displaystyle i=k^{*}+1,\dots ,n}$

เมื่อใช้ค่าน้ำหนักที่เหมาะสม พจน์เด่นในการขยายอนุกรมอสิมโทติกของความเสี่ยงส่วนเกินคือผลลัพธ์ที่คล้ายกันนี้ก็เป็นจริงเช่นกันเมื่อใช้ตัวจำแนกเพื่อนบ้านที่ใกล้ที่สุดแบบแบ็กกิ้ง ${\displaystyle {\mathcal {O}}(n^{-{\frac {4}{d+4}}})}$

วิธีการเพื่อนบ้านที่ใกล้ที่สุดอีกรูปแบบหนึ่งใช้ เพื่อนบ้านที่ไกลที่สุด kตัวแทนเพื่อนบ้านที่ใกล้ที่สุด ในการตั้งค่านี้ เพื่อนบ้านจะถูกเลือกโดยพิจารณาจากความแตกต่างสูงสุดแทนที่จะเป็นความคล้ายคลึงกัน วิธีการนี้ได้รับการเสนอในระบบแนะนำในรูปแบบ "เพื่อนบ้านแบบกลับด้าน" โดยจะระบุผู้ใช้ที่มีความแตกต่างมากที่สุดและใช้ความชอบของพวกเขาในทางกลับกันเพื่อสร้างคำแนะนำ^{[ 13 ]}โดยทั่วไปเป้าหมายคือการเพิ่มความหลากหลายหรือความแปลกใหม่ในรายการที่แนะนำ เนื่องจากวิธีการเพื่อนบ้านที่ใกล้ที่สุดแบบดั้งเดิมอาจให้ความสำคัญกับรายการที่เป็นที่นิยมหรือชัดเจน การประเมินเชิงประจักษ์พบว่าวิธีการเพื่อนบ้านที่ไกลที่สุดโดยทั่วไปมีความแม่นยำในการทำนายต่ำกว่าวิธีการเพื่อนบ้านที่ใกล้ที่สุด k ตัวแบบมาตรฐาน แม้ว่าประโยชน์ที่ผู้ใช้รับรู้จะคล้ายกันหรือสูงกว่าในบางกรณี

k -NN เป็นกรณีพิเศษของตัวประมาณค่า "บอลลูน" ความหนาแน่นเคอร์เนลแบบแบนด์วิดท์แปรผันที่ มี เคอร์เนลสม่ำเสมอ^{[ 14 ] [ 15 ]}

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

k- NN มีผลลัพธ์ ที่สอดคล้องกันอย่างมากเมื่อปริมาณข้อมูลเข้าใกล้ ค่าอนันต์ อัลกอริทึม k- NN แบบสองคลาสจะรับประกันว่าจะมีอัตราข้อผิดพลาดไม่แย่ไปกว่าสองเท่าของอัตราข้อผิดพลาดของเบย์ ส (อัตราข้อผิดพลาดขั้นต่ำที่สามารถทำได้เมื่อพิจารณาจากการกระจายของข้อมูล) ^{[ 2 ]}การปรับปรุงความเร็วของk -NN สามารถทำได้โดยใช้กราฟความใกล้เคียง^{[ 16 ]}

สำหรับการจำแนกประเภท k- NN หลายคลาสCoverและHart (1967) พิสูจน์อัตราข้อผิดพลาดขอบเขตบน โดย ที่คืออัตราข้อผิดพลาดของ Bayes (ซึ่งเป็นอัตราข้อผิดพลาดขั้นต่ำที่เป็นไปได้) คือ อัตราข้อผิดพลาด k- NN แบบไม่จำกัด และMคือจำนวนคลาสในปัญหา ขอบเขตนี้แน่นหนาในแง่ที่ว่าทั้งขอบเขตล่างและขอบเขตบนสามารถบรรลุได้ด้วยการกระจายบางอย่าง^{[ 17 ]}สำหรับและเมื่ออัตราข้อผิดพลาดของ Bayesian เข้าใกล้ศูนย์ ขีดจำกัดนี้จะลดลงเหลือ "ไม่เกินสองเท่าของอัตราข้อผิดพลาดของ Bayesian" $${\displaystyle R^{*}\ \leq \ R_{k\mathrm {NN} }\ \leq \ R^{*}\left(2-{\frac {MR^{*}}{M-1}}\right)}$$${\displaystyle R^{*}}$${\displaystyle R_{kNN}}$${\displaystyle M=2}$${\displaystyle R^{*}}$

มีผลลัพธ์มากมายเกี่ยวกับอัตราข้อผิดพลาดของตัวจำแนกเพื่อนบ้านที่ใกล้ที่สุดk ตัว ^{[ 18 ]}ตัว จำแนกเพื่อนบ้านที่ใกล้ที่สุด kตัวมีความสอดคล้องอย่างมาก (นั่นคือสำหรับการกระจายร่วมใด ๆ บน) โดย มีเงื่อนไข ว่า เบี่ยงเบนและลู่เข้าสู่ศูนย์เมื่อ ${\displaystyle (X,Y)}$${\displaystyle k:=k_{n}}$${\displaystyle k_{n}/n}$${\displaystyle n\to \infty }$

ให้แทนตัว จำแนกเพื่อนบ้านที่ใกล้ที่สุด k ตัวโดยอิงจากชุดฝึกอบรมขนาดnภายใต้เงื่อนไขความสม่ำเสมอบางประการความเสี่ยงส่วนเกินจะให้การขยายอนุกรมอสิมโทติกต่อไปนี้[ ^{12 ] สำหรับ} ค่าคงที่บางค่าและ${\displaystyle C_{n}^{knn}}$$${\displaystyle {\mathcal {R}}_{\mathcal {R}}(C_{n}^{knn})-{\mathcal {R}}_{\mathcal {R}}(C^{\text{Bayes}})=\left\{B_{1}{\frac {1}{k}}+B_{2}\left({\frac {k}{n}}\right)^{4/d}\right\}\{1+o(1)\},}$$${\displaystyle B_{1}}$${\displaystyle B_{2}}$

ตัวเลือกนี้เป็นการแลกเปลี่ยนระหว่างสองเงื่อนไขในแผนภาพด้านบน ซึ่งข้อผิดพลาดของเพื่อนบ้านที่ใกล้ที่สุดจะลู่เข้าสู่ข้อผิดพลาดของเบย์สในอัตราที่เหมาะสมที่สุด( minimax )${\displaystyle k^{*}=\left\lfloor Bn^{\frac {4}{d+4}}\right\rfloor }$${\displaystyle k^{*}}$${\displaystyle {\mathcal {O}}\left(n^{-{\frac {4}{d+4}}}\right)}$

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

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

ตัวอย่างของ กระบวนการประมวล ผลภาพด้วยคอมพิวเตอร์ ทั่วไป สำหรับการจดจำใบหน้าโดยใช้k -NN ซึ่งรวมถึงขั้นตอนการสกัดคุณลักษณะและการลดมิติข้อมูล (โดยปกติจะใช้OpenCV ในการดำเนินการ ):

1. การตรวจจับใบหน้าแบบ Haar
2. การวิเคราะห์การติดตามการเปลี่ยนแปลงค่าเฉลี่ย
3. การฉายภาพ PCAหรือFisher LDAลงในพื้นที่คุณลักษณะ ตามด้วย การจำแนกประเภท k -NN

สำหรับข้อมูลที่มีมิติสูง (เช่น มีจำนวนมิติมากกว่า 10) มักจะทำการ ลดมิติก่อนที่จะใช้ อัลกอริธึม k -NN เพื่อหลีกเลี่ยงผลกระทบของคำสาปแห่งมิติ^{[ 19 ]}

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

การสกัดคุณลักษณะและการลดมิติสามารถรวมเข้าด้วยกันได้ในขั้นตอนเดียวโดยใช้ เทคนิค การวิเคราะห์ส่วนประกอบหลัก (PCA) การวิเคราะห์การจำแนกเชิงเส้น (LDA) หรือการวิเคราะห์ความสัมพันธ์แบบแคนอนิก (CCA) เป็นขั้นตอนการประมวลผลล่วงหน้า ตามด้วยการจัดกลุ่มโดยk -NN บนเวกเตอร์คุณลักษณะในพื้นที่มิติที่ลดลง กระบวนการนี้เรียกอีกอย่างว่าการฝัง มิติที่ ^ต่ำ [ ^{20 ]}

สำหรับชุดข้อมูลที่มีมิติสูงมาก (เช่น เมื่อทำการค้นหาความคล้ายคลึงกันบนสตรีมวิดีโอสด ข้อมูล DNA หรืออนุกรมเวลา ที่มีมิติสูง ) การเรียกใช้ การค้นหา k -NN โดยประมาณ อย่างรวดเร็ว โดยใช้แฮชที่ไวต่อตำแหน่ง "การฉายภาพแบบสุ่ม" ^{[ 21 ]} "ภาพร่าง" ^{[ 22 ]}หรือเทคนิคการค้นหาความคล้ายคลึงกันที่มีมิติสูงอื่นๆ จากกล่องเครื่องมือ VLDB อาจเป็นทางเลือกเดียวที่เป็นไปได้

กฎเพื่อนบ้านที่ใกล้ที่สุดจะคำนวณ ขอบเขตการตัดสินใจโดยปริยาย นอกจากนี้ยังสามารถคำนวณขอบเขตการตัดสินใจได้อย่างชัดเจน และทำได้อย่างมีประสิทธิภาพ โดยความซับซ้อนในการคำนวณขึ้นอยู่กับความซับซ้อนของขอบเขต^{[ 23 ]}

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

1. เลือก ข้อมูล ผิดปกติของคลาสซึ่งก็คือข้อมูลฝึกฝนที่ถูกจำแนกผิดโดยk -NN (สำหรับค่าk ที่กำหนด )
2. แบ่งข้อมูลที่เหลือออกเป็นสองชุด: (i) ต้นแบบที่ใช้สำหรับการตัดสินใจจำแนกประเภท และ (ii) จุดดูดซับที่สามารถจำแนกประเภทได้อย่างถูกต้องโดยk -NN โดยใช้ต้นแบบ จากนั้นสามารถลบจุดดูดซับออกจากชุดข้อมูลฝึกฝนได้

ตัวอย่างข้อมูลฝึกฝนที่อยู่ท่ามกลางตัวอย่างของคลาสอื่น ๆ เรียกว่า ข้อมูลผิดปกติของคลาส (Class Outlier) สาเหตุของข้อมูลผิดปกติของคลาส ได้แก่:

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

ข้อมูลผิดปกติของคลาสที่มีk -NN จะสร้างสัญญาณรบกวน ซึ่งสามารถตรวจจับและแยกออกเพื่อการวิเคราะห์ในอนาคตได้ เมื่อกำหนดจำนวนธรรมชาติสองจำนวนk > r > 0 ตัวอย่างการฝึกอบรมจะถูกเรียกว่าข้อมูลผิดปกติของคลาส ( k , r )NN หาก เพื่อนบ้านที่ใกล้ที่สุด k ตัวของตัวอย่างนั้นมี ตัวอย่างของคลาสอื่น มากกว่าr ตัวอย่าง

เพื่อนบ้านที่ใกล้ที่สุดแบบย่อ (CNN, อัลกอริทึมHart ) เป็นอัลกอริทึมที่ออกแบบมาเพื่อลดชุดข้อมูลสำหรับการจำแนกประเภทk -NN ^{[ 24 ]}โดยจะเลือกชุดต้นแบบUจากข้อมูลการฝึกอบรม เพื่อให้ 1NN ที่มีUสามารถจำแนกตัวอย่างได้อย่างแม่นยำเกือบเท่ากับที่ 1NN ทำกับชุดข้อมูลทั้งหมด

เมื่อกำหนดชุดข้อมูลฝึกฝนXแล้ว CNN จะทำงานแบบวนซ้ำ:

1. สแกนองค์ประกอบทั้งหมดของXโดยมองหาองค์ประกอบxที่มีต้นแบบที่ใกล้ที่สุดจากUซึ่งมีป้ายกำกับแตกต่างจากx
2. ลบx ออก จากXแล้วเพิ่มเข้าไปในU
3. ทำการสแกนซ้ำจนกว่าจะไม่มีต้นแบบใดถูกเพิ่มเข้าไปในU อีกต่อ ไป

ใช้UแทนXในการจำแนกประเภท ตัวอย่างที่ไม่ใช่ต้นแบบเรียกว่าจุด "ดูดซับ"

การสแกนตัวอย่างการฝึกอบรมตามลำดับอัตราส่วนขอบที่ลดลงนั้นมีประสิทธิภาพ^{[ 25 ]}อัตราส่วนขอบของตัวอย่างการฝึกอบรมxถูกกำหนดดังนี้

โดยที่‖ xy ‖คือระยะห่างจากตัวอย่าง y ที่ใกล้ที่สุดซึ่ง มีสีต่างจากxและ‖ x'-y ‖คือระยะห่างจากyไปยังตัวอย่างx' ที่ใกล้ที่สุด ซึ่งมีป้ายกำกับเดียวกันกับx

อัตราส่วนขอบเขตอยู่ในช่วง [0,1] เนื่องจาก‖ x'-y ‖ไม่เกิน‖ xy ‖ลำดับนี้ให้ความสำคัญกับขอบเขตของคลาสสำหรับการรวมอยู่ในชุดของต้นแบบUจุดที่มีป้ายกำกับต่างจากxเรียกว่าจุดภายนอกxการคำนวณอัตราส่วนขอบเขตแสดงไว้ในรูปทางด้านขวา จุดข้อมูลมีป้ายกำกับสี: จุดเริ่มต้นคือxและป้ายกำกับของมันคือสีแดง จุดภายนอกเป็นสีน้ำเงินและสีเขียว จุดภายนอกที่ใกล้ที่สุดกับxคือyจุดสีแดงที่ใกล้ที่สุดกับy คือ x'อัตราส่วนขอบเขตa ( x ) = ‖ x'-y ‖ / ‖ xy ‖คือ คุณลักษณะของจุดเริ่มต้นx

ด้านล่างนี้คือภาพประกอบของ CNN ในชุดรูปภาพ มีสามคลาส (สีแดง สีเขียว และสีน้ำเงิน) รูปที่ 1: ในตอนเริ่มต้นมี 60 จุดในแต่ละคลาส รูปที่ 2 แสดงแผนที่การจำแนกประเภท 1NN: แต่ละพิกเซลถูกจำแนกประเภทโดย 1NN โดยใช้ข้อมูลทั้งหมด รูปที่ 3 แสดงแผนที่การจำแนกประเภท 5NN พื้นที่สีขาวสอดคล้องกับบริเวณที่ยังไม่ได้จำแนกประเภท ซึ่งการลงคะแนน 5NN เสมอกัน (ตัวอย่างเช่น หากมีจุดสีเขียวสองจุด สีแดงสองจุด และสีน้ำเงินหนึ่งจุด ในบรรดาเพื่อนบ้านที่ใกล้ที่สุด 5 จุด) รูปที่ 4 แสดงชุดข้อมูลที่ลดลง เครื่องหมายกากบาทคือจุดนอกคลาสที่เลือกโดยกฎ (3,2)NN (เพื่อนบ้านที่ใกล้ที่สุดสามจุดของอินสแตนซ์เหล่านี้เป็นของคลาสอื่นทั้งหมด) สี่เหลี่ยมคือต้นแบบ และวงกลมว่างคือจุดที่ถูกดูดซับ มุมล่างซ้ายแสดงจำนวนจุดนอกคลาส ต้นแบบ และจุดที่ถูกดูดซับสำหรับทั้งสามคลาส จำนวนต้นแบบแตกต่างกันไปตั้งแต่ 15% ถึง 20% สำหรับคลาสต่างๆ ในตัวอย่างนี้ รูปที่ 5 แสดงให้เห็นว่าแผนที่การจำแนกประเภท 1NN ที่มีต้นแบบนั้นคล้ายคลึงกับแผนที่ที่มีชุดข้อมูลเริ่มต้นมาก รูปภาพเหล่านี้สร้างขึ้นโดยใช้แอปเพล็ต Mirkes ^{[ 25 ]}

• การลดโมเดล CNN สำหรับตัวจำแนก k-NN
• 
  รูปที่ 1. ชุดข้อมูล
• 
  รูปที่ 2 แผนผังการจำแนกประเภท 1NN
• 
  รูปที่ 3 แผนผังการจำแนกประเภท 5NN
• 
  รูปที่ 4. ชุดข้อมูลที่ลดขนาดลงด้วยโครงข่ายประสาทเทียมแบบ CNN
• 
  รูปที่ 5 แผนผังการจำแนกประเภท 1NN โดยอิงจากต้นแบบที่สกัดจาก CNN

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

1. คำนวณระยะทางแบบยุคลิดหรือแบบมาฮาลาโนบิสจากตัวอย่างคำถามไปยังตัวอย่างที่มีป้ายกำกับ
2. เรียงลำดับตัวอย่างที่มีป้ายกำกับตามระยะทางที่เพิ่มขึ้น
3. ค้นหาจำนวนเพื่อนบ้านที่ใกล้ที่สุดk ที่เหมาะสมที่สุดโดยใช้หลักการเชิงฮิวริสติก โดยพิจารณาจาก ค่า RMSEซึ่งทำได้โดยใช้การตรวจสอบแบบไขว้ (cross validation)
4. คำนวณค่าเฉลี่ยถ่วงน้ำหนักตามระยะทางผกผันโดยใช้เพื่อนบ้านหลายตัวแปรที่ใกล้ที่สุดk ตัว

ระยะห่างไป ยังเพื่อนบ้านที่ใกล้ที่สุดลำดับที่ kสามารถมองได้ว่าเป็นค่าประมาณความหนาแน่นในพื้นที่ และด้วยเหตุนี้จึงเป็นคะแนนความผิดปกติที่นิยมใช้ในการตรวจจับความผิดปกติยิ่งระยะห่างไปยังเพื่อนบ้านที่ใกล้ที่สุดลำดับที่k มาก เท่าใด ความหนาแน่นในพื้นที่ก็จะยิ่งต่ำลงเท่านั้น และจุดที่สอบถามก็มีแนวโน้มที่จะเป็นความผิดปกติมากขึ้นเท่านั้น^{[ 26 ]} แม้จะค่อนข้างเรียบง่าย แต่แบบจำลองความผิดปกตินี้ ร่วมกับ วิธีการขุดข้อมูลแบบคลาสสิกอีกวิธีหนึ่ง คือ ปัจจัยความผิดปกติในพื้นที่ก็ทำงานได้ดีทีเดียวเมื่อเปรียบเทียบกับวิธีการที่ทันสมัยและซับซ้อนกว่า ตามการวิเคราะห์เชิงทดลองขนาดใหญ่^{[ 27 ]}

เมทริกซ์ความสับสนหรือ "เมทริกซ์การจับคู่" มักถูกใช้เป็นเครื่องมือในการตรวจสอบความถูกต้องของ การจำแนกประเภท k -NN นอกจากนี้ยังสามารถใช้ วิธีทางสถิติที่แข็งแกร่งกว่า เช่นการทดสอบอัตราส่วนความน่าจะ เป็นได้อีกด้วย

• ตัวจำแนกจุดศูนย์กลางที่ใกล้ที่สุด
• ปัญหาจุดที่อยู่ใกล้กันที่สุด
• กราฟเพื่อนบ้านที่ใกล้ที่สุด
• การจำแนกประเภทวัตถุตามการแบ่งส่วน

• Dasarathy, Belur V. , บรรณาธิการ (1991). มาตรฐานเพื่อนบ้านที่ใกล้ที่สุด (NN): เทคนิคการจำแนกรูปแบบเพื่อนบ้านที่ใกล้ที่สุดสำนักพิมพ์ IEEE Computer Society. ISBN 978-0818689307.
• Shakhnarovich, Gregory; Darrell, Trevor; Indyk, Piotr, บรรณาธิการ (2005). วิธีการเพื่อนบ้านที่ใกล้ที่สุดในการเรียนรู้และการมองเห็น . สำนักพิมพ์ MIT . ISBN 978-0262195478.