To construct a handwriting recognition system, we utilize the k-Nearest Neighbors (kNN) algorithm. The dataset consists of binary images representing digits (0 through 9), stored as text files where every character is either a '0' or a '1'. These images are typically 32x32 pixels in size.

Data Preparation: Image Vectorization

Since the kNN algorithm requires numerical feature vectors rather than 2D image grids, the first step involves transforming the 32x32 matrix into a 1x1024 vector. This function reads a file line by line and constructs the flat vector.

import numpy as np

def flatten_image_file(file_path):
    # Initialize a zero vector with 1024 features (32 * 32)
    feature_vector = np.zeros(1024)
    
    with open(file_path) as f:
        for row in range(32):
            line = f.readline().strip()
            for col in range(32):
                # Map the 2D coordinate to a 1D index
                feature_vector[row * 32 + col] = int(line[col])
                
    return feature_vector

Algorithm Implementation: kNN Classifier

The core logic of the kNN classifier involves calculating the Euclidean distance between the input vector and every vector in the training dataset. It then identifies the top k closest neighbors and determines the most frequent label among them.

import operator

def classify_input(input_vector, dataset, labels, k):
    dataset_size = dataset.shape[0]
    
    # Calculate Euclidean distance using matrix operations
    diff_matrix = np.tile(input_vector, (dataset_size, 1)) - dataset
    sq_diff_matrix = diff_matrix ** 2
    sq_distances = sq_diff_matrix.sum(axis=1)
    distances = sq_distances ** 0.5
    
    # Sort distances to find nearest neighbors
    sorted_indices = distances.argsort()
    
    # Voting mechanism for the k nearest neighbors
    class_votes = {}
    for i in range(k):
        neighbor_label = labels[sorted_indices[i]]
        class_votes[neighbor_label] = class_votes.get(neighbor_label, 0) + 1
        
    # Sort votes in descending order
    sorted_votes = sorted(class_votes.items(), key=operator.itemgetter(1), reverse=True)
    
    return sorted_votes[0][0]

System Testing and Evaluation

To validate the model, we load the training data into a matrix and iteratively test it against the test dataset. The file naming convention (e.g., 0_13.txt) indicates the digit label (the first number) and a sample index. We track prediction errors to calculate the overall accuracy.

from os import listdir

def evaluate_recognition_system(training_dir, test_dir, k=3):
    training_files = listdir(training_dir)
    num_train = len(training_files)
    
    # Prepare training matrix
    training_matrix = np.zeros((num_train, 1024))
    ground_truth_labels = []
    
    for i in range(num_train):
        filename = training_files[i]
        label = int(filename.split('_')[0])
        ground_truth_labels.append(label)
        training_matrix[i, :] = flatten_image_file(f'{training_dir}/{filename}')
        
    test_files = listdir(test_dir)
    error_count = 0
    num_test = len(test_files)
    
    for i in range(num_test):
        filename = test_files[i]
        actual_label = int(filename.split('_')[0])
        test_vector = flatten_image_file(f'{test_dir}/{filename}')
        
        prediction = classify_input(test_vector, training_matrix, ground_truth_labels, k)
        
        if prediction != actual_label:
            error_count += 1
            print(f"Mismatch: Model predicted {prediction}, Actual was {actual_label}")
            
    print(f"\nTotal Errors: {error_count}")
    print(f"Error Rate: {error_count / num_test:.4f}")

# Example usage
# evaluate_recognition_system('trainingDigits', 'testDigits')

Running the evaluaiton function processes the test images. The system calculates distances against the training set for each test sample.

Mismatch: Model predicted 3, Actual was 5
Mismatch: Model predicted 5, Actual was 6
...

Total Errors: 11
Error Rate: 0.0116

The output shows that the algorithm achieves a high accuracy rate, typically around 98-99% on this dataset, demonstrating the effectiveness of kNN for simple handwriting recognition tasks.