dynamic-weighted-knn-parametric-approach.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ceeb7cfd",
   "metadata": {
    "papermill": {
     "duration": 0.00395,
     "end_time": "2024-05-15T21:12:09.922895",
     "exception": false,
     "start_time": "2024-05-15T21:12:09.918945",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Introduction\n",
    "\n",
    "## What is KNN?\n",
    "\n",
    "The K-Nearest Neighbors (KNN) algorithm is a simple, intuitive, and powerful machine learning technique used for classification and regression tasks. It belongs to the family of instance-based learning algorithms, also known as lazy learning algorithms, because it does not build an explicit model during the training phase. Instead, it memorizes the training dataset and makes predictions based on the most similar instances (neighbors) in the dataset.\n",
    "\n",
    "## How Does KNN Work?\n",
    "\n",
    "KNN operates based on the following steps:\n",
    "1. **Storing the Dataset**: During the training phase, KNN simply stores the training data points along with their corresponding labels.\n",
    "2. **Calculating Distance**: When a new data point needs to be classified, KNN calculates the distance between this new point and all the points in the training dataset. Common distance metrics include Euclidean distance, Manhattan distance, and Minkowski distance.\n",
    "3. **Finding Neighbors**: It then identifies the 'k' nearest neighbors to the new data point. The value of 'k' is a hyperparameter that determines the number of closest neighbors to consider.\n",
    "4. **Majority Voting**: For classification tasks, KNN assigns the most frequent label among the 'k' neighbors to the new data point. For regression tasks, it computes the average value of the 'k' neighbors.\n",
    "\n",
    "## Strengths of KNN\n",
    "\n",
    "- **Simplicity**: KNN is easy to understand and implement, making it an excellent choice for beginners in machine learning.\n",
    "- **No Training Phase**: Since KNN is a lazy learning algorithm, there is no explicit training phase, which can save computational resources.\n",
    "- **Flexibility**: KNN can be used for both classification and regression tasks.\n",
    "- **Adaptability**: KNN can naturally handle multi-class classification problems.\n",
    "\n",
    "## Weaknesses of KNN\n",
    "\n",
    "- **Computational Cost**: The prediction phase can be slow, especially with large datasets, as it involves calculating the distance between the new data point and all training points.\n",
    "- **Memory Usage**: KNN requires storing the entire training dataset, which can be memory-intensive.\n",
    "- **Sensitivity to Irrelevant Features**: KNN can be adversely affected by irrelevant or redundant features, which can distort distance calculations.\n",
    "- **Choice of 'k' and Distance Metric**: The performance of KNN heavily depends on the choice of 'k' and the distance metric used. An inappropriate choice can lead to poor performance.\n",
    "\n",
    "![K Nearest Neighbors illustration by GeeksforGeeks](https://i.ibb.co/PYdrThX/K-Nearest-Neighbors.png \"Source: GeeksforGeeks\")\n",
    "\n",
    "## Enhancing KNN with Learnable Weights\n",
    "\n",
    "In this notebook, I introduce an enhancement to the traditional KNN algorithm by incorporating feature weights that are learned using gradient descent. This approach aims to address some of the weaknesses of standard KNN, particularly its sensitivity to irrelevant features. By assigning and optimizing weights for each feature, our Dynamic Weighted KNN algorithm adapts to the importance of different features, potentially improving classification accuracy and robustness. **We will examine whether this is worth implementing and what disadvantages it may offer.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0a3659ff",
   "metadata": {
    "_cell_guid": "b1076dfc-b9ad-4769-8c92-a6c4dae69d19",
    "_uuid": "8f2839f25d086af736a60e9eeb907d3b93b6e0e5",
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:09.932266Z",
     "iopub.status.busy": "2024-05-15T21:12:09.931519Z",
     "iopub.status.idle": "2024-05-15T21:12:11.147232Z",
     "shell.execute_reply": "2024-05-15T21:12:11.146176Z"
    },
    "papermill": {
     "duration": 1.223279,
     "end_time": "2024-05-15T21:12:11.149905",
     "exception": false,
     "start_time": "2024-05-15T21:12:09.926626",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Imports and Setup\n",
    "import time\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import make_classification\n",
    "from sklearn.model_selection import StratifiedKFold\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "# Seed for reproducibility\n",
    "np.random.seed(42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "75f84741",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:11.158717Z",
     "iopub.status.busy": "2024-05-15T21:12:11.158071Z",
     "iopub.status.idle": "2024-05-15T21:12:11.169759Z",
     "shell.execute_reply": "2024-05-15T21:12:11.169091Z"
    },
    "papermill": {
     "duration": 0.018042,
     "end_time": "2024-05-15T21:12:11.171679",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.153637",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Generate a synthetic dataset\n",
    "X, y = make_classification(n_samples=750, n_features=5, \n",
    "                           n_informative=2, n_redundant=0,\n",
    "                           random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c60a5ea9",
   "metadata": {
    "papermill": {
     "duration": 0.00286,
     "end_time": "2024-05-15T21:12:11.177676",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.174816",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "# Dynamic Weighted KNN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d621ebd5",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:11.185421Z",
     "iopub.status.busy": "2024-05-15T21:12:11.184769Z",
     "iopub.status.idle": "2024-05-15T21:12:11.196138Z",
     "shell.execute_reply": "2024-05-15T21:12:11.195422Z"
    },
    "papermill": {
     "duration": 0.017323,
     "end_time": "2024-05-15T21:12:11.198080",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.180757",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class DynamicWeightedKNN:\n",
    "    def __init__(self, k=3, learning_rate=0.01):\n",
    "        \"\"\"Initialize the DynamicWeightedKNN with basic parameters.\"\"\"\n",
    "        self.k = k  # Number of neighbors to consider\n",
    "        self.learning_rate = learning_rate  # Learning rate for weight updates\n",
    "        self.X_train = None  # Training features\n",
    "        self.y_train = None  # Training labels\n",
    "        self.weights = None  # Weights for the features\n",
    "    \n",
    "    def fit(self, X, y, weights=None, n_iterations=25):\n",
    "        \"\"\"Fit the model using the provided training dataset and optional initial weights.\"\"\"\n",
    "        self.X_train = X\n",
    "        self.y_train = y\n",
    "        self.weights = np.ones(X.shape[1]) if weights is None else weights\n",
    "        \n",
    "        for _ in range(n_iterations):\n",
    "            self.update_weights()\n",
    "    \n",
    "    def predict_proba(self, X):\n",
    "        \"\"\"Predict the probabilities for the dataset X using the weighted Euclidean distance.\"\"\"\n",
    "        probas = []\n",
    "        for x in X:\n",
    "            distances = np.array([self.weighted_euclidean_distance(x, x_train) for x_train in self.X_train])\n",
    "            k_indices = np.argsort(distances)[:self.k]\n",
    "            k_nearest_labels = self.y_train[k_indices]\n",
    "            prob = np.mean(k_nearest_labels)\n",
    "            probas.append(prob)\n",
    "        return np.array(probas)\n",
    "    \n",
    "    def update_weights(self):\n",
    "        \"\"\"Update weights using the gradient of the loss function incorporating logistic derivative.\"\"\"\n",
    "        y_pred = self.predict_proba(self.X_train)\n",
    "        error = y_pred - self.y_train\n",
    "        for i in range(len(self.weights)):\n",
    "            # Incorporating the logistic derivative for the gradient calculation\n",
    "            gradient = np.dot(error * y_pred * (1 - y_pred), self.X_train[:, i])\n",
    "            self.weights[i] -= self.learning_rate * gradient\n",
    "        self.weights = np.maximum(0, self.weights)  # Ensure weights remain non-negative\n",
    "    \n",
    "    def weighted_euclidean_distance(self, x, y):\n",
    "        \"\"\"Calculate the weighted Euclidean distance between two vectors.\"\"\"\n",
    "        difference = x - y\n",
    "        weighted_squared_diff = self.weights * np.square(difference)\n",
    "        return np.sqrt(np.sum(weighted_squared_diff))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ece9c678",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:11.205540Z",
     "iopub.status.busy": "2024-05-15T21:12:11.205258Z",
     "iopub.status.idle": "2024-05-15T21:12:11.211939Z",
     "shell.execute_reply": "2024-05-15T21:12:11.211080Z"
    },
    "papermill": {
     "duration": 0.012491,
     "end_time": "2024-05-15T21:12:11.213841",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.201350",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "class KNN:\n",
    "    def __init__(self, k=3):\n",
    "        \"\"\"Initialize the BasicKNN with the number of neighbors to consider.\"\"\"\n",
    "        self.k = k\n",
    "        self.X_train = None  # Training features\n",
    "        self.y_train = None  # Training labels\n",
    "    \n",
    "    def fit(self, X, y):\n",
    "        \"\"\"Fit the model using the provided training dataset.\"\"\"\n",
    "        self.X_train = X\n",
    "        self.y_train = y\n",
    "    \n",
    "    def predict(self, X):\n",
    "        \"\"\"Predict the labels for the dataset X.\"\"\"\n",
    "        predictions = []\n",
    "        for x in X:\n",
    "            distances = np.array([self.euclidean_distance(x, x_train) for x_train in self.X_train])\n",
    "            k_indices = np.argsort(distances)[:self.k]\n",
    "            k_nearest_labels = self.y_train[k_indices]\n",
    "            majority_vote = np.argmax(np.bincount(k_nearest_labels))\n",
    "            predictions.append(majority_vote)\n",
    "        return np.array(predictions)\n",
    "    \n",
    "    def euclidean_distance(self, x, y):\n",
    "        \"\"\"Calculate the Euclidean distance between two vectors.\"\"\"\n",
    "        return np.sqrt(np.sum((x - y) ** 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "23437af6",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:11.221078Z",
     "iopub.status.busy": "2024-05-15T21:12:11.220824Z",
     "iopub.status.idle": "2024-05-15T21:12:11.224162Z",
     "shell.execute_reply": "2024-05-15T21:12:11.223551Z"
    },
    "papermill": {
     "duration": 0.008996,
     "end_time": "2024-05-15T21:12:11.225883",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.216887",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Initialize Stratified K-Fold\n",
    "skf = StratifiedKFold(n_splits=5)\n",
    "\n",
    "# Prepare lists to store results\n",
    "standard_knn_accuracies = []\n",
    "dynamic_weighted_knn_accuracies = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "21632240",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:11.233197Z",
     "iopub.status.busy": "2024-05-15T21:12:11.232750Z",
     "iopub.status.idle": "2024-05-15T21:12:14.311828Z",
     "shell.execute_reply": "2024-05-15T21:12:14.310619Z"
    },
    "papermill": {
     "duration": 3.085272,
     "end_time": "2024-05-15T21:12:14.314179",
     "exception": false,
     "start_time": "2024-05-15T21:12:11.228907",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed time: 3.0716617107391357 seconds\n",
      "Average Accuracy with Standard KNN: 0.9333333333333332\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "# Conduct Stratified K-Fold Cross-Validation for Standard KNN\n",
    "for train_index, test_index in skf.split(X, y):\n",
    "    X_train, X_test = X[train_index], X[test_index]\n",
    "    y_train, y_test = y[train_index], y[test_index]\n",
    "\n",
    "    # Standard KNN\n",
    "    standard_knn = KNN(k=5)\n",
    "    standard_knn.fit(X_train, y_train)\n",
    "    standard_predictions = standard_knn.predict(X_test)\n",
    "    standard_accuracy = accuracy_score(y_test, standard_predictions)\n",
    "    standard_knn_accuracies.append(standard_accuracy)\n",
    "    \n",
    "elapsed_time = time.time() - start_time\n",
    "print(f\"Elapsed time: {elapsed_time} seconds\")\n",
    "    \n",
    "# Print average accuracy for Standard KNN\n",
    "print(\"Average Accuracy with Standard KNN:\", np.mean(standard_knn_accuracies))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "d44e4df9",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-15T21:12:14.322109Z",
     "iopub.status.busy": "2024-05-15T21:12:14.321816Z",
     "iopub.status.idle": "2024-05-15T21:18:05.690443Z",
     "shell.execute_reply": "2024-05-15T21:18:05.689259Z"
    },
    "papermill": {
     "duration": 351.377942,
     "end_time": "2024-05-15T21:18:05.695500",
     "exception": false,
     "start_time": "2024-05-15T21:12:14.317558",
     "status": "completed"
    },
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Elapsed time: 351.3615128993988 seconds\n",
      "Average Accuracy with Dynamic Weighted KNN: 0.9306666666666666\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "# Conduct Stratified K-Fold Cross-Validation for Dynamic Weighted KNN\n",
    "for train_index, test_index in skf.split(X, y):\n",
    "    X_train, X_test = X[train_index], X[test_index]\n",
    "    y_train, y_test = y[train_index], y[test_index]\n",
    "\n",
    "    # Dynamic Weighted KNN\n",
    "    dynamic_knn = DynamicWeightedKNN(k=5, learning_rate=0.01)\n",
    "    dynamic_knn.fit(X_train, y_train, n_iterations=25)\n",
    "    dynamic_predictions = dynamic_knn.predict_proba(X_test) > 0.5  # Thresholding to get binary predictions\n",
    "    dynamic_accuracy = accuracy_score(y_test, dynamic_predictions)\n",
    "    dynamic_weighted_knn_accuracies.append(dynamic_accuracy)\n",
    "\n",
    "elapsed_time = time.time() - start_time\n",
    "print(f\"Elapsed time: {elapsed_time} seconds\")\n",
    "\n",
    "# Print average accuracy for Dynamic Weighted KNN\n",
    "print(\"Average Accuracy with Dynamic Weighted KNN:\", np.mean(dynamic_weighted_knn_accuracies))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01916d52",
   "metadata": {
    "papermill": {
     "duration": 0.002984,
     "end_time": "2024-05-15T21:18:05.701723",
     "exception": false,
     "start_time": "2024-05-15T21:18:05.698739",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Outcomes\n",
    "\n",
    "### Performance Analysis\n",
    "\n",
    "After applying both the Dynamic Weighted KNN and the standard KNN to our selected dataset using stratified cross-validation, we observed key differences in both accuracy and computational efficiency.\n",
    "\n",
    "**Accuracy**: The Dynamic Weighted KNN showed mixed results in terms of accuracy compared to the standard KNN. While it demonstrated slightly better accuracy on some datasets, it also performed slightly worse on others. This variability suggests that the introduction of feature-specific weights, optimized through gradient descent, might not consistently capture the importance of different features across diverse datasets.\n",
    "\n",
    "**Speed**: The Dynamic Weighted KNN was significantly slower than the standard KNN. The added computational overhead from updating weights using gradient descent at each training step substantially increases the time required for the model to train. This drawback makes the Dynamic Weighted KNN impractical for scenarios where quick training or real-time prediction is crucial.\n",
    "\n",
    "### Considerations for Slowness\n",
    "\n",
    "The slower performance of the Dynamic Weighted KNN is a significant limitation. Even with occasional accuracy improvements, its computational inefficiency could be a dealbreaker in many real-world applications where speed and scalability are paramount.\n",
    "\n",
    "### Potential Optimizations\n",
    "\n",
    "Despite its current limitations, there are several strategies that could potentially optimize the performance of the Dynamic Weighted KNN:\n",
    "\n",
    "- **Efficient Data Structures**: Using more efficient data structures like KD-Trees or Ball Trees could reduce the computational complexity associated with finding the nearest neighbors, thus speeding up both the training and prediction phases.\n",
    "- **Parallel Processing**: Leveraging parallel processing techniques to distribute the computation of distances and updates across multiple cores or GPUs could significantly reduce execution time.\n",
    "- **Feature Selection**: Performing feature selection before training to reduce the dimensionality of the data could decrease the number of weights that need to be optimized, thereby simplifying the model and speeding up the calculations.\n",
    "- **Algorithmic Refinements**: Applying more sophisticated methods for gradient descent (e.g., incorporating momentum or adaptive learning rate techniques) could improve the efficiency of weight updates.\n",
    "\n",
    "### Conclusion\n",
    "\n",
    "Given the variable accuracy and significantly slower performance of the Dynamic Weighted KNN, it is not recommended for use over the standard KNN in most practical scenarios. The potential improvements in accuracy do not outweigh the considerable increase in computational costs. However, with targeted optimizations and enhancements, there may be potential to make this model viable for specific applications where the unique advantages of feature-weighted learning can be fully realized."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6162a3f0",
   "metadata": {
    "papermill": {
     "duration": 0.002898,
     "end_time": "2024-05-15T21:18:05.707754",
     "exception": false,
     "start_time": "2024-05-15T21:18:05.704856",
     "status": "completed"
    },
    "tags": []
   },
   "source": [
    "## Time Complexity\n",
    "\n",
    "### Training Phase\n",
    "\n",
    "During the training phase:\n",
    "- **Distance Calculation**: Calculating the weighted Euclidean distance between all pairs of data points involves O(d) operations per pair. Given n data points, computing distances for all pairs leads to O(n^2 * d) complexity.\n",
    "- **Weight Updates**: The gradient update for weights based on the calculated distances and errors involves O(n * d) operations per iteration.\n",
    "- **Iterations**: Repeating the weight update process across t iterations, the total complexity becomes O(t * n^2 * d)."
   ]
  }
 ],
 "metadata": {
  "kaggle": {
   "accelerator": "none",
   "dataSources": [],
   "dockerImageVersionId": 30698,
   "isGpuEnabled": false,
   "isInternetEnabled": true,
   "language": "python",
   "sourceType": "notebook"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.13"
  },
  "papermill": {
   "default_parameters": {},
   "duration": 358.591916,
   "end_time": "2024-05-15T21:18:06.032069",
   "environment_variables": {},
   "exception": null,
   "input_path": "__notebook__.ipynb",
   "output_path": "__notebook__.ipynb",
   "parameters": {},
   "start_time": "2024-05-15T21:12:07.440153",
   "version": "2.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}