Toggle navigation

• Projekt Jupyter
• Návody
• Stiahnuť
• Prihlásiť sa na test
• Prihlásiť sa

1. Data Lab
2. ZSU
3. cv08_kNN.ipynb

Toto je statické zobrazenie, ak chcete Notebook spustiť, prihláste sa do prostredia Data Lab.

K-Nearest Neighbors (kNN) - Student Assignment

Total Points: 8 (4 parts × 2 points each)

---

Prehľad postupu výpočtu algoritmu kNN

1. Vybrať optimálnu hodnotu k
2. Vypočítať vzdialenosť medzi testovacím bodom a trénovacími bodmi
3. Nájsť k najbližších susedov
4. Rozhodnúť hlasovaním (klasifikácia) alebo priemerom (regresia)

V tomto cvičení sa zameriame na klasifikáciu.

Setup - Required Imports

import numpy as np
from typing import List

---

Part 1: Calculate Euclidean Distance (2 points)

Implementujte výpočet euklidovskej vzdialenosti medzi dvoma bodmi.

Vzorec: $d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$

Vstupy:

• point1: prvý bod ako pole hodnôt
• point2: druhý bod ako pole hodnôt

Výstup:

• distance: euklidovská vzdialenosť medzi bodmi

def euclidean_distance(point1: np.ndarray, point2: np.ndarray) -> float:
    # Sample return value for [1, 2] and [4, 6]: 5.0
    """
    Compute the Euclidean distance between two points.

    Args:
        point1: First point
        point2: Second point

    Returns:
        distance: float - Euclidean distance
    """
    distance = 0.0

    # TODO: Implement Euclidean distance
    # Your code here

    return distance

---

Part 2: Find the k Nearest Neighbors (2 points)

Implementujte funkciu, ktorá nájde triedy k najbližších susedov testovacieho bodu.

Postup:

1. Pre každý trénovací bod vypočítajte vzdialenosť od test_point
2. Uložte si dvojice (distance, label)
3. Zotrieďte ich podľa vzdialenosti vzostupne
4. Vráťte labely prvých k susedov

Vstupy:

• training_data: trénovacie body
• training_labels: triedy trénovacích bodov
• test_point: bod, ktorý chceme klasifikovať
• k: počet susedov

Výstup:

• neighbors: zoznam tried k najbližších susedov

def get_k_nearest_neighbors(training_data: np.ndarray,
                            training_labels: List[str],
                            test_point: np.ndarray,
                            k: int) -> List[str]:
    # Sample return value: ['A', 'A', 'B']
    """
    Return the labels of the k nearest neighbors.

    Args:
        training_data: Array of training points
        training_labels: Labels for training points
        test_point: Point to classify
        k: Number of neighbors

    Returns:
        neighbors: List[str] - Labels of k nearest points
    """
    neighbors = []

    # TODO: Implement nearest-neighbor search
    # Your code here

    return neighbors

---

Part 3: Voting for Classification (2 points)

Implementujte finálnu klasifikáciu pomocou väčšinového hlasovania medzi k najbližšími susedmi.

Postup:

1. Získajte k najbližších susedov
2. Spočítajte výskyty jednotlivých tried
3. Vráťte triedu s najväčším počtom hlasov

Poznámka:

• Pri zhode hlasov vráťte triedu, ktorá sa objaví ako prvá medzi susedmi po zotriedení podľa vzdialenosti

Vstupy:

• training_data
• training_labels
• test_point
• k

Výstup:

• prediction: predikovaná trieda pre test_point

def knn_predict(training_data: np.ndarray,
                training_labels: List[str],
                test_point: np.ndarray,
                k: int) -> str:
    # Sample return value for the test dataset and k=3: 'A'
    """
    Predict the class of a test point using kNN.

    Args:
        training_data: Array of training points
        training_labels: Labels for training points
        test_point: Point to classify
        k: Number of neighbors

    Returns:
        prediction: str - Predicted class label
    """
    prediction = ""

    # TODO: Implement kNN classification by majority vote
    # Your code here

    return prediction

---

Part 4: Select the Optimal Value of k (2 points)

Implementujte funkciu, ktorá vyberie najvhodnejšiu hodnotu k na základe presnosti na validačných dátach.

Použite svoje implementácie z predchádzajúcich častí. Pre každé kandidátne k:

1. Predikujte triedu pre každý bod vo validation_data
2. Porovnajte predikcie so validation_labels
3. Vypočítajte accuracy ako podiel správnych predikcií ku všetkým predikciám
4. Vyberte k s najvyššou accuracy

Vstupy:

• training_data: trénovacie body
• training_labels: triedy trénovacích bodov
• validation_data: validačné body
• validation_labels: správne triedy validačných bodov
• candidate_k_values: zoznam kandidátnych hodnôt k

Výstup:

• best_k: hodnota k s najvyšším skóre

Pravidlá:

• Ak má viac kandidátov rovnaké najvyššie skóre, vyberte z nich najmenšie nepárne k

def select_best_k(training_data: np.ndarray,
                  training_labels: List[str],
                  validation_data: np.ndarray,
                  validation_labels: List[str],
                  candidate_k_values: List[int]) -> int:
    # Sample return value for the test dataset: 1
    """
    Select the best k based on validation accuracy.

    Args:
        training_data: Array of training points
        training_labels: Labels for training points
        validation_data: Array of validation points
        validation_labels: Correct labels for validation points
        candidate_k_values: Candidate values of k to test

    Returns:
        best_k: int - Selected value of k
    """
    best_k = -1

    # TODO: Implement best-k selection using validation accuracy
    # Your code here

    return best_k

Testing Dataset

Budeme pracovať s jednoduchým 2D datasetom s dvoma triedami: A a B.

training_data = np.array([
    [1.0, 2.0],
    [2.0, 3.0],
    [3.0, 3.5],
    [6.0, 6.0],
    [7.0, 7.0],
    [8.0, 6.5]
])

training_labels = ['A', 'A', 'A', 'B', 'B', 'B']

validation_data = np.array([
    [2.5, 2.5],
    [6.5, 6.5],
    [3.5, 3.0],
    [7.5, 6.0]
])

validation_labels = ['A', 'B', 'A', 'B']

test_point = np.array([4.0, 4.5])
candidate_k_values = [1, 3, 5]

---

Test your implementation

# Test Part 1: Euclidean Distance
test_point1 = np.array([1.0, 2.0])
test_point2 = np.array([4.0, 6.0])
distance_result = euclidean_distance(test_point1, test_point2)
print("Part 1 - Euclidean Distance:")
print(f"Input points: {test_point1}, {test_point2}")
print(f"Your result: {distance_result}")
print(f"Expected: 5.0")
print()

# Test Part 2: k Nearest Neighbors
neighbors_result = get_k_nearest_neighbors(training_data, training_labels, test_point, 3)
print("Part 2 - k Nearest Neighbors:")
print(f"Test point: {test_point}, k: 3")
print(f"Your result: {neighbors_result}")
print(f"Expected: ['A', 'A', 'B']")
print()

# Test Part 3: kNN Prediction
prediction_result = knn_predict(training_data, training_labels, test_point, 3)
print("Part 3 - kNN Prediction:")
print(f"Test point: {test_point}, k: 3")
print(f"Your result: {prediction_result}")
print(f"Expected: A")
print()

# Test Part 4: Select Best k
best_k_result = select_best_k(
    training_data,
    training_labels,
    validation_data,
    validation_labels,
    candidate_k_values
)
print("Part 4 - Select Best k:")
print(f"Candidate k values: {candidate_k_values}")
print(f"Your result: {best_k_result}")
print(f"Expected: 1")
print()

---

© 2020-2026 UUI