โจทย์
K เพื่อนบ้านที่ใกล้ที่สุด (KNN) จำแนกจุดใหม่โดยดูจุดฝึก k จุดที่ใกล้ที่สุดแล้วเลือกป้ายกำกับที่พบบ่อยที่สุด
- คำนวณระยะทางแบบยุคลิดจาก
queryไปยังทุกจุด - เรียงจุดตามระยะทาง ถ้าระยะทางเท่ากัน จุดที่มีดัชนีน้อยกว่าจะมาก่อน
- เลือก k จุดแรกแล้วนับป้ายกำกับ
- คืนค่าป้ายกำกับที่ได้เสียงมากที่สุด ถ้าเสมอกัน ให้คืนค่าป้ายกำกับที่จุดซึ่งใกล้ที่สุดของมันมาก่อนในลำดับที่เรียงแล้ว
จงเขียน knn_predict(points, labels, query, k)
อินพุต
points: จุดฝึก แต่ละจุดเป็นลิสต์ของพิกัด
labels: ป้ายกำกับของแต่ละจุด
query: จุดที่ต้องการจำแนก
k: จำนวนเพื่อนบ้านที่ร่วมโหวต
เอาต์พุต
คืนค่าป้ายกำกับที่ทำนายได้
เงื่อนไข
1 ≤ k ≤ จำนวนจุด ≤ 1,000
1 ≤ จำนวนมิติ ≤ 20
-1,000 ≤ แต่ละพิกัด ≤ 1,000
ตัวอย่าง
อินพุต:
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3
ผลลัพธ์ที่คาดหวัง:
expected = "A"
อินพุต:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "A";
อินพุต:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
string[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;
ผลลัพธ์ที่คาดหวัง:
string expected = "A";
คำอธิบาย
ระยะทางจาก (3, 3): (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07 ป้ายกำกับ 3 อันที่ใกล้ที่สุดคือ A, A และ B ดังนั้นคำตอบคือ A
อินพุต:
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2
ผลลัพธ์ที่คาดหวัง:
expected = "red"
อินพุต:
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;
ผลลัพธ์ที่คาดหวัง:
std::string expected = "red";
อินพุต:
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;
ผลลัพธ์ที่คาดหวัง:
string expected = "red";
คำอธิบาย
จุดที่ใกล้ที่สุดคือ (0, 0) (red) อีกสองจุดถัดไปคือ (4, 0) และ (0, 4) อยู่ห่างเท่ากัน จึงเลือกจุดที่ดัชนีน้อยกว่าคือ (4, 0) (blue) red และ blue ได้คนละหนึ่งเสียง และจุดของ red มาก่อน ดังนั้นคำตอบคือ red
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
วัดระยะ Euclidean ของแต่ละจุดจาก query แล้วเรียงตามระยะ โดยให้ index ที่น้อยกว่าชนะเมื่อระยะเท่ากัน
คำใบ้ 2
ใช้แค่ k จุดแรกที่เรียงแล้วโหวต ดังนั้น label สุดท้ายจึงขึ้นกับชุดข้อมูลฝึกเพียงส่วนเล็กๆ
คำใบ้ 3
ถ้าคะแนนโหวตเสมอ ให้เลือก label ที่มีจุดใกล้ที่สุดที่เกี่ยวข้องและปรากฏก่อนในรายการเพื่อนบ้านที่เรียงแล้ว
ความซับซ้อนที่คาดหวัง
เวลา O(n log n), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน