การวิเคราะห์ส่วนประกอบของเพื่อนบ้าน (Neighbourhood components analysis)เป็น วิธี การเรียนรู้แบบมีผู้กำกับดูแล (supervised learning)สำหรับจำแนก ข้อมูล หลายตัวแปรออกเป็นกลุ่มต่างๆ ตามเมตริกวัดระยะทาง ที่กำหนดไว้ บนข้อมูล ในทางฟังก์ชันการทำงาน มันทำหน้าที่เหมือนกับ อัลกอริ ทึมเพื่อนบ้านที่ใกล้ที่สุด K ตัว (K-nearest neighbors algorithm)และใช้แนวคิดที่เกี่ยวข้องที่เรียกว่าเพื่อนบ้านที่ใกล้ที่สุดแบบสุ่ม (stochastic nearest neighbours ) โดยตรง

การวิเคราะห์ส่วนประกอบของพื้นที่ใกล้เคียงมีเป้าหมายเพื่อ "เรียนรู้" เมตริกซ์ระยะทางโดยการหาการแปลงเชิงเส้นของข้อมูลอินพุตเพื่อให้ประสิทธิภาพการจำแนกประเภทแบบ Leave-One-Out (LOO) เฉลี่ยสูงสุดในพื้นที่ที่แปลงแล้ว แนวคิดหลักของอัลกอริทึมนี้คือเมทริกซ์ที่สอดคล้องกับการแปลงสามารถหาได้โดยการกำหนดฟังก์ชันเป้าหมายที่หาอนุพันธ์ได้สำหรับตามด้วยการใช้ตัวแก้ปัญหาแบบวนซ้ำ เช่นการไล่ระดับแบบสังยุค (Conjugate Gradient Descent ) ข้อดีอย่างหนึ่งของอัลกอริทึมนี้คือจำนวนคลาสสามารถกำหนดได้เป็นฟังก์ชันของโดยมีค่าคงที่สเกลาร์อยู่ด้วย ดังนั้นการใช้อัลกอริทึมนี้จึงช่วยแก้ปัญหาเรื่องการเลือกแบบจำลองได้ ${\displaystyle A}$${\displaystyle A}$${\displaystyle k}$${\displaystyle A}$

เพื่อให้ได้มาซึ่งค่าที่ต้องการเราจึงกำหนดฟังก์ชันเป้าหมายที่อธิบายความแม่นยำในการจำแนกประเภทในพื้นที่ที่แปลงแล้ว และพยายามหาค่าที่ทำให้ฟังก์ชันเป้าหมายนี้มีค่าสูงสุด ${\displaystyle A}$${\displaystyle A^{*}}$

${\displaystyle A^{*}={\mbox{argmax}}_{A}f(A)}$

ลองพิจารณาการทำนายป้ายกำกับคลาสของจุดข้อมูลเดียวโดยอาศัยฉันทามติของเพื่อนบ้านที่ใกล้ที่สุดจำนวนหนึ่งที่มีเมตริกซ์ระยะทางที่กำหนด วิธีนี้เรียกว่า การจำแนกประเภท แบบตัดออกทีละจุด (leave-one-out classification) อย่างไรก็ตาม ชุดของเพื่อนบ้านที่ใกล้ที่สุดอาจแตกต่างกันมากหลังจากผ่านจุดทั้งหมดผ่านการแปลงเชิงเส้น โดยเฉพาะอย่างยิ่ง ชุดของเพื่อนบ้านสำหรับจุดหนึ่งอาจเปลี่ยนแปลงแบบไม่ต่อเนื่องเมื่อตอบสนองต่อการเปลี่ยนแปลงแบบราบเรียบในองค์ประกอบของ ซึ่งหมายความว่าฟังก์ชันเป้าหมายใดๆที่อิงตามเพื่อนบ้านของจุดนั้นจะมีค่าคงที่แบบเป็นช่วงๆและดังนั้นจึงไม่สามารถหาอนุพันธ์ได้ ${\displaystyle k}$${\displaystyle C_{i}}$${\displaystyle A}$${\displaystyle f(\cdot )}$

เราสามารถแก้ไขปัญหานี้ได้โดยใช้วิธีการที่ได้รับแรงบันดาลใจจากการไล่ระดับแบบสุ่ม (stochastic gradient descent ) แทนที่จะพิจารณาเพื่อนบ้านที่ใกล้ที่สุด n จุดในแต่ละจุดที่แปลงแล้วในการจำแนกประเภทแบบ LOO เราจะพิจารณาชุดข้อมูลที่แปลงแล้วทั้งหมดเป็นเพื่อนบ้านที่ใกล้ที่สุดแบบสุ่มเรากำหนดสิ่งเหล่านี้โดยใช้ฟังก์ชัน softmaxของระยะทางแบบยุคลิด กำลังสอง ระหว่างจุดการจำแนกประเภทแบบ LOO ที่กำหนดกับจุดอื่นๆ ทุกจุดในพื้นที่ที่แปลงแล้ว: ${\displaystyle k}$

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{ถ้า }}j\neq i\\0,&{\mbox{ถ้า }}j=i\end{cases}}}$

ความน่าจะเป็นของการจำแนกจุดข้อมูลได้อย่างถูกต้องคือ ความน่าจะเป็นของการจำแนกจุดข้อมูลของจุดข้อมูลข้างเคียงแต่ละจุดให้อยู่ในคลาสเดียวกัน: ${\displaystyle i}$${\displaystyle C_{i}}$

${\displaystyle p_{i}=\sum _{j\in C_{i}}p_{ij}\quad }$ความน่าจะเป็นของการจำแนกจุดข้างเคียงของจุดนั้นคือ เท่าใด${\displaystyle p_{ij}}$${\displaystyle j}$${\displaystyle i}$

กำหนดฟังก์ชันเป้าหมายโดยใช้การจำแนกประเภทแบบ LOO โดยครั้งนี้ใช้ชุดข้อมูลทั้งหมดเป็นเพื่อนบ้านที่ใกล้ที่สุดแบบสุ่ม:

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}$

โปรดทราบว่าภายใต้เพื่อนบ้านที่ใกล้ที่สุดแบบสุ่ม คลาสที่เป็นเอกฉันท์สำหรับจุดเดียวคือค่าที่คาดหวังของคลาสของจุดนั้นในขีดจำกัดของจำนวนตัวอย่างที่ไม่มีที่สิ้นสุดที่ดึงมาจากการแจกแจงเหนือเพื่อนบ้าน กล่าวคือ: ดังนั้นคลาสที่ทำนายได้จึงเป็นการรวมกันเชิงเส้นของคลาสของทุกจุดอื่น ๆ โดยถ่วงน้ำหนักด้วยฟังก์ชัน softmax สำหรับแต่ละจุด โดยที่คือชุดข้อมูลที่แปลงแล้วทั้งหมด ${\displaystyle i}$${\displaystyle j\in C_{i}}$${\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}}$${\displaystyle j\in C_{j}}$${\displaystyle C_{j}}$

การเลือกฟังก์ชันเป้าหมายนี้เป็นที่ต้องการมากกว่า เนื่องจากสามารถหาอนุพันธ์เทียบกับ(กำหนดให้): ${\displaystyle A}$${\displaystyle x_{ij}=x_{i}-x_{j}}$

${\displaystyle {\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)}$

${\displaystyle =2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)}$

การหาค่าเกรเดียนต์หมายความว่าสามารถหาได้ด้วยตัวแก้ปัญหาแบบวนซ้ำ เช่น การลดเกรเดียนต์แบบสังยุค (conjugate gradient descent ) โปรดทราบว่าในทางปฏิบัติ เทอมภายในสุดส่วนใหญ่ของเกรเดียนต์จะมีส่วนร่วมที่ไม่สำคัญ เนื่องจากส่วนร่วมของจุดที่อยู่ห่างไกลจากจุดที่สนใจจะลดลงอย่างรวดเร็ว ซึ่งหมายความว่าผลรวมภายในของเกรเดียนต์สามารถตัดทอนได้ ส่งผลให้เวลาในการคำนวณเหมาะสมแม้กับชุดข้อมูลขนาดใหญ่ ${\displaystyle A}$

"การหาค่าสูงสุดเทียบเท่ากับการลดระยะห่าง-distance ระหว่างการกระจายตัวของคลาสที่คาดการณ์ไว้กับการกระจายตัวของคลาสที่แท้จริงให้เหลือน้อยที่สุด (กล่าวคือ โดยที่ ค่า distance ที่เกิดจาก distance ทั้งหมดเท่ากับ 1) ทางเลือกที่เป็นธรรมชาติอีกอย่างหนึ่งคือ KL-divergence ซึ่งทำให้เกิดฟังก์ชันวัตถุประสงค์และเกรเดียนต์ดังต่อไปนี้:" (Goldberger 2005) ${\displaystyle f(\cdot )}$${\displaystyle L_{1}}$${\displaystyle p_{i}}$${\displaystyle A}$

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}$

${\displaystyle {\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)}$

ในทางปฏิบัติ การปรับปรุงการใช้งานฟังก์ชันนี้มักให้ผลลัพธ์ด้านประสิทธิภาพที่คล้ายคลึงกับแบบดั้งเดิม ${\displaystyle A}$

การวิเคราะห์ส่วนประกอบของย่านใกล้เคียงได้รับการพัฒนาโดย Jacob Goldberger, Sam Roweis, Ruslan SalakhutdinovและGeoff Hintonที่ภาควิชาวิทยาการคอมพิวเตอร์ มหาวิทยาลัยโทรอนโต ในปี 2547

• การจัดกลุ่มสเปกตรัม
• ระยะห่างมาก เพื่อนบ้านที่ใกล้ที่สุด

• ไลบรารีMLPACKมีการใช้งาน ในภาษา C++
• nca ( C++ )
• การใช้งาน " NeighborhoodComponentsAnalysis " ของscikit-learn ( Python )