system.py

"""Baseline classification system.

Solution outline for the COM2004/3004 assignment.

version: v1.0
"""

from typing import List

import numpy as np
import scipy as sp

N_DIMENSIONS = 10

def classify(train: np.ndarray, train_labels: np.ndarray, test: np.ndarray) -> List[str]:
    """Classify a set of feature vectors using a training set.

    Args:
        train (np.ndarray): 2-D array storing the training feature vectors.
        train_labels (np.ndarray): 1-D array storing the training labels.
        test (np.ndarray): 2-D array storing the test feature vectors.

    Returns:
        list[str]: A list of one-character strings representing the labels for each square.
    
    """
    #using sub functions to test different methods and hyperparamters easily

    return k_nearest_neighbour(train, train_labels, test, 5)


def reduce_dimensions(data: np.ndarray, model: dict) -> np.ndarray:
    """Reduce the dimensionality of a set of feature vectors down to N_DIMENSIONS.

    The feature vectors are stored in the rows of 2-D array data, (i.e., a data matrix).
    
    Args:
        data (np.ndarray): The feature vectors to reduce.
        model (dict): A dictionary storing the model data that may be needed.

    Returns:
        np.ndarray: The reduced feature vectors.
    """

    # Project the data onto principal components axes
    data = np.dot((data  - model["mean_data"]), (model["eigenvectors"]))

    # Select the best features for classification
    reduced_data = data[:, np.array(model["selected_features"])]

    return reduced_data
  


def process_training_data(fvectors_train: np.ndarray, labels_train: np.ndarray) -> dict:
    """Process the labeled training data and return model parameters stored in a dictionary.

    Note, the contents of the dictionary are up to you, and it can contain any serializable
    data types stored under any keys. This dictionary will be passed to the classifier.

    Args:
        fvectors_train (np.ndarray): training data feature vectors stored as rows.
        labels_train (np.ndarray): the labels corresponding to the feature vectors.

    Returns:
        dict: a dictionary storing the model data.
    """

    #create model 
    model = {}
    model["labels_train"] = labels_train.tolist()

    # Perform PCA on the training data
    pcatrain_data = pca(fvectors_train, model)

    # Select the best features for classification amd add to model
    features = feature_selection(pcatrain_data, labels_train)
    model["selected_features"] = features.tolist()

    # Reduce the dimensionality of the training data
    fvectors_train_reduced = reduce_dimensions(fvectors_train, model)
    model["fvectors_train"] = fvectors_train_reduced.tolist()

    return model


def images_to_feature_vectors(images: List[np.ndarray]) -> np.ndarray:
    """Takes a list of images (of squares) and returns a 2-D feature vector array.

    In the feature vector array, each row corresponds to an image in the input list.

    Args:
        images (list[np.ndarray]): A list of input images to convert to feature vectors.

    Returns:
        np.ndarray: An 2-D array in which the rows represent feature vectors.
    """
    # added gaussian filter to reduce noise

    h, w = images[0].shape
    n_features = h * w
    fvectors = np.empty((len(images), n_features))
    for i, image in enumerate(images):

        image = sp.ndimage.gaussian_filter(image, sigma=1)

        fvectors[i, :] = image.reshape(1, n_features)

    return fvectors


def classify_squares(fvectors_test: np.ndarray, model: dict) -> List[str]:
    """Run classifier on a array of image feature vectors presented in an arbitrary order.

    Note, the feature vectors stored in the rows of fvectors_test represent squares
    to be classified. The ordering of the feature vectors is arbitrary, i.e., no information
    about the position of the squares within the board is available.

    Args:
        fvectors_test (np.ndarray): An array in which feature vectors are stored as rows.
        model (dict): A dictionary storing the model data.

    Returns:
        list[str]: A list of one-character strings representing the labels for each square.
    """

    # Get some data out of the model. It's up to you what you've stored in here
    fvectors_train = np.array(model["fvectors_train"])
    labels_train = np.array(model["labels_train"])

    # Call the classify function.
    labels = classify(fvectors_train, labels_train, fvectors_test)
    

    return labels

# classify_boards` that appears in `system.py`. `classify_boards` is passed the squares in the same order as they appear in the board. 
# This means that you can work out the position of the square within the board, and you can see the contents of other squares on the same board.
#  You can potentially use this information to improve the classification performance.

def classify_boards(fvectors_test: np.ndarray, model: dict) -> List[str]:
    """Run classifier on a array of image feature vectors presented in 'board order'.

    The feature vectors for each square are guaranteed to be in 'board order', i.e.
    you can infer the position on the board from the position of the feature vector
    in the feature vector array.

    Args:
        fvectors_test (np.ndarray): An array in which feature vectors are stored as rows.
        model (dict): A dictionary storing the model data.

    Returns:
        list[str]: A list of one-character strings representing the labels for each square.

    """

    # Get some data out of the model. It's up to you what you've stored in here
    fvectors_train = np.array(model["fvectors_train"])
    labels_train = np.array(model["labels_train"])

    # Call the classify function.
    labels = classify(fvectors_train, labels_train, fvectors_test)

    # Reclassify the pawns to kings if they are on the back rows and there is no king of that color already
    for board_start in range(0, len(labels), 64):
        board_labels = labels[board_start:board_start+64]
        white_king_on_board = "K" in board_labels
        black_king_on_board = "k" in board_labels
        for i in range(len(board_labels)):
            if board_labels[i] == "p" and i < 8 and not black_king_on_board:
                board_labels[i] = "k"
            elif board_labels[i] == "P" and i >= 56 and not white_king_on_board:
                board_labels[i] = "K"
        labels[board_start:board_start+64] = board_labels
    
    return labels


def pca(data: np.ndarray, model: dict) -> np.ndarray:

    #adapted from week 7 Lab

    """
    Perform PCA on a data matrix and return the reduced data matrix.
    Args:
        data (np.ndarray): The data to reduce.
        model (dict): A dictionary storing the model data.

    Returns:
        np.ndarray: The reduced data.
    """

    # Compute eigenvectors of the covariance matrix
    covariance_matrix = np.cov(data, rowvar=0)
    num_features = covariance_matrix.shape[0]
    eigenvalues , eigenvectors = sp.linalg.eigh(covariance_matrix, eigvals=(num_features - 40, num_features - 1))
    eigenvectors = np.fliplr(eigenvectors)

    # Store the eigenvalues and eigenvectors in the model
    model["eigenvectors"] = eigenvectors.tolist()
    model["mean_data"] = np.mean(data)

    # Project the data onto principal components axes
    pca_data = np.dot((data - np.mean(data)), eigenvectors)
    return pca_data


square_content = ["." , "p", "P", "b", "B", "n", "N", "R", "r","q" ,"Q", "k", "K"]

def feature_selection(pca_data, train_labels) -> np.ndarray:

    #adapted from week 6 lab to fit square_content

    """
    Select the best features for classification.
    args: 
        pca_data (np.ndarray): The data to reduce.
        train_labels (np.ndarray): The labels for the training data.
    returns: 
        features - a vector of feature indexes
    """

    d = 0
    for piece1 in square_content:
        piece1_data = pca_data[train_labels == piece1, :]
        for piece2 in square_content:
            piece2_data = pca_data[train_labels == piece2, :]
            d12 = divergence(piece1_data, piece2_data)
            d = d + d12
            sorted_indexes = np.argsort(-d)
            features = sorted_indexes[0:N_DIMENSIONS]

    return features

def divergence(class1, class2):
    """compute a vector of 1-D divergences
    
    class1 - data matrix for class 1, each row is a sample
    class2 - data matrix for class 2
    
    returns: d12 - a vector of 1-D divergence scores
    """ 

    #divergence from week 6 lab

    m1 = np.mean(class1, axis=0)
    m2 = np.mean(class2, axis=0)
    v1 = np.var(class1, axis=0)
    v2 = np.var(class2, axis=0)

    d12 = 0.5 * (v1 / v2 + v2 / v1 - 2) + 0.5 * (m1 - m2) * (m1 - m2) * (
        1.0 / v1 + 1.0 / v2
    )

    return d12


def k_nearest_neighbour(train: np.ndarray, train_labels: np.ndarray, test: np.ndarray, k: int) -> List[str]:
    """
    Use k nearest neighbour to classify a set of feature vectors using a training set.

    Args:
        train (np.ndarray): 2-D array storing the training feature vectors.
        train_labels (np.ndarray): 1-D array storing the training labels.
        test (np.ndarray): 2-D array storing the test feature vectors.
        k (int): The number of nearest neighbours to consider.

    Returns:
        list[str]: A list of one-character strings representing the labels for each square.
    """

    # Calculate distances between test and train vectors
    distances = sp.spatial.distance.cdist(test, train, metric="euclidean")

    # Find the k nearest neighbors for each test vector
    nearest_neighbours = np.argsort(distances, axis=1)[:, :k]

    # Get the labels of the nearest neighbors
    nearest_labels = train_labels[nearest_neighbours]

    # Predict the label of each test vector by mode of nearest neighbors
    predicted_labels = []
    for neighbors in nearest_labels:
        label_counts = {}
        for neighbor_label in neighbors:
            label_counts[neighbor_label] = label_counts.get(neighbor_label, 0) + 1
        most_common_label = max(label_counts, key=label_counts.get)
        predicted_labels.append(most_common_label)

    return predicted_labels


# old functions replaced by k_nearest_neighbour

def nearest_neighbour1(train: np.ndarray, train_labels: np.ndarray, test: np.ndarray) -> List[str]:
    # Super compact implementation of nearest neighbour
    x = np.dot(test, train.transpose())
    modtest = np.sqrt(np.sum(test * test, axis=1))
    modtrain = np.sqrt(np.sum(train * train, axis=1))
    dist = x / np.outer(modtest, modtrain.transpose())  # cosine distance
    nearest = np.argmax(dist, axis=1)
    label = train_labels[nearest]

    return label.tolist()

def nearest_neighbour2(train: np.ndarray, train_labels: np.ndarray, test: np.ndarray) -> List[str]:
    # Super compact implementation of nearest neighbour
    distances = sp.spatial.distance.cdist(test, train, metric="euclidean")
    nearest_neighbours = np.argmin(distances, axis=1)
    labels = train_labels[nearest_neighbours]

    return labels.tolist()