Assignment-79.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1f1ec3d7-2f90-44c6-b950-c6001a19250b",
   "metadata": {},
   "source": [
    "## Q1. What is anomaly detection and what is its purpose?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86b5435f",
   "metadata": {},
   "source": [
    "Anomaly detection, also known as outlier detection, is a technique used in data analysis and machine learning to identify patterns or data \n",
    "points that deviate significantly from the majority of the data. Anomalies are observations that do not conform to the expected behavior or \n",
    "follow the same patterns as the majority of the data. The primary purpose of anomaly detection is to find and flag unusual or potentially \n",
    "suspicious data points or events that may require further investigation.\n",
    "\n",
    "Key aspects and purposes of anomaly detection include:\n",
    "\n",
    "* #### Identifying Unusual Patterns: \n",
    "Anomaly detection aims to identify patterns, behaviors, or data points that are significantly different from the norm. These anomalies could be indicative of errors, fraud, rare events, or novel insights.\n",
    "\n",
    "* #### Quality Control: \n",
    "In industrial applications, anomaly detection is used to monitor and maintain the quality of products or processes by identifying defective or unusual items on assembly lines or in manufacturing processes.\n",
    "\n",
    "* #### Security and Fraud Detection:\n",
    "Anomaly detection plays a crucial role in cybersecurity and fraud detection. It helps identify abnormal network traffic, unauthorized access, or fraudulent transactions.\n",
    "\n",
    "* #### Healthcare: \n",
    "In healthcare, it can be used to detect abnormal patient data, such as unusual vital signs, lab results, or disease outbreaks.\n",
    "\n",
    "* #### Finance: \n",
    "In the financial sector, anomaly detection is used to identify unusual trading activity, potential financial fraud, or credit card fraud.\n",
    "\n",
    "* #### Environmental Monitoring: \n",
    "It can be used to identify unusual environmental conditions or events, such as pollution spikes or seismic activity.\n",
    "\n",
    "* #### Network Monitoring: \n",
    "Anomaly detection is used to detect unusual behavior in computer networks, which could be indicative of network intrusions or malfunctions.\n",
    "\n",
    "* #### Quality Assurance in Data: \n",
    "In data preprocessing, anomaly detection can be applied to identify and handle outliers or errors in data, ensuring the quality of datasets used for machine learning.\n",
    "\n",
    "Methods for anomaly detection can vary widely, including statistical methods, machine learning algorithms, clustering techniques, and domain-specific approaches. The choice of method depends on the nature of the data and the specific application.\n",
    "\n",
    "Overall, the purpose of anomaly detection is to provide early warnings or insights into unusual events or data points, helping organizations take timely actions, investigate issues, and maintain the integrity and security of their systems and data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64462160",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b4e5d7a3-1546-468f-9b0c-e96b7198733a",
   "metadata": {},
   "source": [
    "## Q2. What are the key challenges in anomaly detection?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbcc64cf",
   "metadata": {},
   "source": [
    "Anomaly detection is a valuable technique, but it comes with several challenges, some of which can make the task complex and \n",
    "context-dependent. Key challenges in anomaly detection include:\n",
    "\n",
    "* #### Imbalanced Data: \n",
    "Anomalies are typically rare events compared to normal data points. Imbalanced datasets can bias models towards the majority class and make it challenging to detect anomalies accurately.\n",
    "\n",
    "* #### Labeling and Ground Truth: \n",
    "Anomalies often lack clear labels or ground truth, especially in unsupervised anomaly detection. Defining what constitutes an anomaly can be subjective and context-specific.\n",
    "\n",
    "* #### High-Dimensional Data: \n",
    "In high-dimensional spaces, the concept of distance or similarity can become less intuitive, and traditional distance-based methods may struggle to identify anomalies effectively. This is known as the \"curse of dimensionality.\"\n",
    "\n",
    "* #### Data Preprocessing:\n",
    "Anomaly detection can be sensitive to the quality of the data. Noisy data, missing values, or outliers can influence the detection process and lead to false positives or negatives.\n",
    "\n",
    "* #### Scalability: \n",
    "Scaling anomaly detection to large datasets can be computationally intensive. Efficient algorithms and distributed computing may be required to handle big data scenarios.\n",
    "\n",
    "* #### Dynamic Environments: \n",
    "Anomalies may evolve or change over time. Detecting anomalies in dynamic environments requires models that can adapt and update in real-time.\n",
    "\n",
    "* #### Feature Engineering:\n",
    "Selecting relevant features and transforming data appropriately are crucial for accurate anomaly detection. In some cases, domain knowledge is needed to identify relevant features.\n",
    "\n",
    "* #### Model Selection: \n",
    "Choosing the right anomaly detection algorithm or model depends on the data distribution and the type of anomalies present. There is no one-size-fits-all solution.\n",
    "\n",
    "* #### False Positives: \n",
    "Minimizing false positives is critical in anomaly detection. A high false positive rate can lead to excessive alerts or alarms, which can be costly and reduce trust in the system.\n",
    "\n",
    "* #### Interpretable Models: \n",
    "Some anomaly detection techniques produce results that are difficult to interpret. Explaining why a particular data point is considered an anomaly can be important, especially in applications like healthcare or finance.\n",
    "\n",
    "* #### Concept Drift: \n",
    "In situations where data distributions change over time, detecting anomalies becomes challenging. Anomalies may be normal in a new context, and the model needs to adapt to evolving patterns.\n",
    "\n",
    "* #### Data Distribution Assumptions: \n",
    "Many anomaly detection methods assume that the data follows a specific distribution (e.g., Gaussian distribution). If this assumption does not hold, the model's performance may suffer.\n",
    "\n",
    "* #### Anomaly Types: \n",
    "Different types of anomalies exist, such as point anomalies (individual data points are anomalies), contextual anomalies (anomalies depend on the context), and collective anomalies (anomalies occur collectively but not individually). Detecting each type may require different approaches.\n",
    "\n",
    "* #### Evaluating Performance: \n",
    "Evaluating the performance of anomaly detection models can be challenging, especially when ground truth labels are unavailable or imprecise. Choosing appropriate evaluation metrics is important.\n",
    "\n",
    "Addressing these challenges often requires a combination of domain knowledge, data preprocessing, algorithm selection, and ongoing monitoring and refinement of the anomaly detection system. Different applications may prioritize different challenges, depending on their specific goals and contexts."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e16dc198-8ac4-4dd8-9825-788f7f999cd4",
   "metadata": {},
   "source": [
    "## Q3. How does unsupervised anomaly detection differ from supervised anomaly detection?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1551eab1",
   "metadata": {},
   "source": [
    "Unsupervised anomaly detection and supervised anomaly detection are two distinct approaches to identifying anomalies or\n",
    "outliers in a dataset. They differ primarily in how they utilize labeled data during the training process and the level of \n",
    "supervision involved:\n",
    "\n",
    "#### <u>Unsupervised Anomaly Detection:</u>\n",
    "\n",
    "* #### Training Data: \n",
    "Unsupervised anomaly detection methods do not rely on labeled data for training. They operate solely on the input data, assuming that it consists of both normal and anomalous instances.\n",
    "\n",
    "* #### Objective: \n",
    "The primary objective of unsupervised anomaly detection is to identify data points or patterns that deviate significantly from the majority of the data without using any prior knowledge of which data points are anomalies.\n",
    "\n",
    "* #### Algorithms: \n",
    "Unsupervised methods include techniques such as clustering-based approaches (e.g., K-Means, DBSCAN), density estimation (e.g., Gaussian Mixture Models, kernel density estimation), and dimensionality reduction (e.g., Principal Component Analysis, t-SNE) that aim to capture the underlying structure of the data.\n",
    "\n",
    "* #### Challenges: \n",
    "Unsupervised anomaly detection is challenging when there are no labeled anomalies for model evaluation, and the definition of anomalies is often subjective and context-dependent.\n",
    "\n",
    "* #### Applications: \n",
    "Unsupervised methods are suitable when there is little to no prior knowledge of the anomalies or when labeling anomalies in the training data is infeasible.\n",
    "\n",
    "#### <u>Supervised Anomaly Detection:</u>\n",
    "\n",
    "* #### Training Data: \n",
    "Supervised anomaly detection methods require labeled training data, where each data point is labeled as either normal or anomalous. This labeled dataset is used to train a model.\n",
    "\n",
    "* #### Objective: \n",
    "The primary objective of supervised anomaly detection is to build a model that can accurately classify new, unlabeled data points as either normal or anomalous based on patterns learned from the labeled training data.\n",
    "\n",
    "* #### Algorithms: \n",
    "Supervised methods typically involve machine learning algorithms such as decision trees, support vector machines (SVMs), random forests, neural networks, or any other supervised classification algorithm.\n",
    "\n",
    "* #### Challenges: \n",
    "The main challenge in supervised anomaly detection is obtaining a high-quality labeled dataset with representative anomalies. Creating such a dataset can be labor-intensive and expensive.\n",
    "\n",
    "* #### Applications: \n",
    "Supervised methods are applicable when you have a reliable source of labeled anomalies and want to build a model that can classify anomalies with high precision.\n",
    "\n",
    "\n",
    "#### <u>Key Differences:</u>\n",
    "\n",
    "* #### Data Requirement: \n",
    "Unsupervised methods do not require labeled training data, while supervised methods rely on labeled anomalies.\n",
    "\n",
    "* #### Model Goal: \n",
    "Unsupervised methods aim to discover anomalies without prior knowledge of what constitutes an anomaly. Supervised methods aim to classify new data points as normal or anomalous based on a predefined anomaly definition.\n",
    "\n",
    "* #### Use Cases: \n",
    "Unsupervised methods are suitable when you have limited or no labeled anomaly data and want to explore data for unexpected patterns. Supervised methods are used when you have labeled anomalies and want to build a predictive model for anomaly classification.\n",
    "\n",
    "* #### Evaluation: \n",
    "Unsupervised methods often rely on intrinsic measures (e.g., Silhouette Score) for evaluation, while supervised methods use standard classification metrics like precision, recall, F1-score, and ROC-AUC.\n",
    "\n",
    "In practice, the choice between unsupervised and supervised anomaly detection depends on the availability of labeled data, the nature of the problem, and the specific goals of the analysis or application. Hybrid approaches, where unsupervised methods are used initially to discover potential anomalies and then supervised methods are applied for classification, are also common in certain scenarios."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0afc5787",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1a48fc34-72e9-4641-afe3-9882692aaa3b",
   "metadata": {},
   "source": [
    "## Q4. What are the main categories of anomaly detection algorithms?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d91bf415",
   "metadata": {},
   "source": [
    "Anomaly detection algorithms can be categorized into several main groups based on their underlying techniques and approaches. \n",
    "The main categories of anomaly detection algorithms include:\n",
    "\n",
    "#### Statistical Methods:\n",
    "Z-Score/Standard Score: Detects anomalies by measuring how many standard deviations a data point is from the mean.\n",
    "Percentile-based Methods: Identifies anomalies based on percentiles or quantiles of the data distribution, such as the Interquartile Range (IQR) method.\n",
    "* Grubbs' Test: Detects anomalies by comparing the sample mean and standard deviation to identify values that deviate         \n",
    "  significantly from the mean.\n",
    "\n",
    "\n",
    "#### Density-Based Methods:\n",
    "DBSCAN (Density-Based Spatial Clustering of Applications with Noise): Clusters data points based on density, considering points with low neighbor density as anomalies.\n",
    "LOF (Local Outlier Factor): Measures the local density deviation of a data point compared to its neighbors to identify anomalies.One-Class SVM (Support Vector Machine): Constructs a decision boundary around the majority of data points, labeling points outside the boundary as anomalies.\n",
    "\n",
    "\n",
    "#### Clustering-Based Methods:\n",
    "* K-Means Clustering: Detects anomalies as data points that do not belong to any cluster or belong to small clusters.\n",
    "* Hierarchical Clustering: Identifies anomalies based on the structure of the hierarchical clustering tree.\n",
    "* DBSCAN: Can also be used for anomaly detection when applied to clustering.\n",
    "\n",
    "\n",
    "#### Proximity-Based Methods:\n",
    "Distance-Based Methods: Detect anomalies based on the distances between data points, such as the nearest-neighbor approach or Mahalanobis distance.\n",
    "K-Nearest Neighbors (KNN): Labels data points as anomalies if they are significantly different from their K-nearest neighbors.\n",
    "\n",
    "\n",
    "#### Machine Learning-Based Methods:\n",
    "Supervised Learning: Trains a model on labeled data to classify anomalies. Common algorithms include decision trees, random forests, support vector machines, and neural networks.\n",
    "Semi-Supervised Learning: Combines labeled and unlabeled data to build an anomaly detection model.\n",
    "Autoencoders: Neural networks used for unsupervised anomaly detection by learning to reconstruct normal data and identifying deviations.Isolation Forest: Constructs a decision tree structure to isolate anomalies efficiently.\n",
    "\n",
    "\n",
    "#### Time-Series Anomaly Detection:\n",
    "Moving Average: Detects anomalies based on deviations from a moving average or rolling mean.\n",
    "Exponential Smoothing: Identifies anomalies by comparing actual values to predicted values using exponential smoothing.\n",
    "Seasonal Decomposition: Decomposes time series into trend, seasonal, and residual components and identifies anomalies in the residual component.\n",
    "\n",
    "\n",
    "#### Ensemble Methods:\n",
    "Combining Multiple Models: Combines the outputs of multiple anomaly detection models to improve overall performance and reduce false positives.\n",
    "Bootstrap Aggregating (Bagging): Constructs multiple models using bootstrapped samples and combines their results.\n",
    "\n",
    "\n",
    "#### Domain-Specific Methods:\n",
    "Specialized approaches tailored to specific domains or industries, such as fraud detection, network security, healthcare, and\n",
    "manufacturing.\n",
    "\n",
    "\n",
    "#### Deep Learning-Based Methods:\n",
    "Utilizes deep neural networks, including recurrent neural networks (RNNs), convolutional neural networks (CNNs), and recurrent autoencodersfor complex data patterns and sequences.\n",
    "\n",
    "#### Graph-Based Methods:\n",
    "Analyzes relationships between data points in graph structures, identifying anomalies based on graph properties, connectivity, or node attributes.\n",
    "\n",
    "\n",
    "\n",
    "The choice of an anomaly detection method depends on the nature of the data, the type of anomalies expected, the availability of labeled data,and the specific requirements of the application. Often, a combination of methods or hybrid approaches is used to address the challenges of detecting anomalies effectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5b91a57c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "25c7ce18-1643-4b9a-a46a-f1bbd8bb1848",
   "metadata": {},
   "source": [
    "## Q5. What are the main assumptions made by distance-based anomaly detection methods?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5ee85fe",
   "metadata": {},
   "source": [
    "Distance-based anomaly detection methods rely on certain assumptions about the data and the behavior of normal data points. \n",
    "The main assumptions made by these methods include:\n",
    "\n",
    "* #### Distance to Neighbors: \n",
    "These methods assume that normal data points are closer to their neighbors in feature space compared to anomalies. In other words, normal data points tend to have similar characteristics to their nearest neighbors.\n",
    "\n",
    "* #### Clustering of Normal Data: \n",
    "Distance-based methods assume that normal data points cluster together in feature space. They form dense regions or clusters, while anomalies are isolated and have fewer nearby neighbors.\n",
    "\n",
    "* #### Constant Density: \n",
    "The assumption of constant density implies that the density of data points is relatively uniform across the feature space for normal data.\n",
    "In contrast, anomalies are expected to have lower local density, indicating a sparsity of nearby data points.\n",
    "\n",
    "* #### Euclidean Distance:\n",
    "Many distance-based methods, such as K-Means, DBSCAN, and LOF, assume that Euclidean distance or other distance metrics (e.g., Mahalanobis distance) are meaningful for measuring dissimilarity between data points. These methods may not perform well when data does not conform to this assumption, especially in high-dimensional spaces.\n",
    "\n",
    "* #### Global vs. Local Behavior: \n",
    "Some distance-based methods assume that anomalies exhibit different global or local behavior compared to normal data. For instance, anomalies may be far from the center of a cluster or may have a different distribution of distances to their neighbors.\n",
    "\n",
    "* #### Homogeneous Data: \n",
    "Distance-based methods work well when the data is relatively homogeneous, meaning that the majority of data points follow similar patterns or distributions. They may struggle with highly heterogeneous data where multiple subpopulations exist.\n",
    "\n",
    "* #### Outliers as Isolated Points: \n",
    "Distance-based methods often assume that anomalies are isolated data points or form small clusters with few members. They may not perform well when anomalies themselves exhibit complex structures.\n",
    "\n",
    "* #### Stable Features: \n",
    "These methods assume that the features used for distance computation are stable and reliable. If features are noisy or subject to measurement errors, it can impact the effectiveness of distance-based methods.\n",
    "\n",
    "It's important to note that distance-based anomaly detection methods may not be suitable for all types of data or anomalies. The effectiveness of these methods depends on how well the data adheres to the assumptions mentioned above. In practice, it's advisable to evaluate different anomaly detection approaches and choose the one that best aligns with the specific characteristics of the data and the nature of the anomalies being targeted. Additionally, feature engineering and preprocessing techniques can help improve the performance of distance-based methods by aligning data more closely with these assumptions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "642bda5c",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "3b950436-98f7-45b2-873b-fa0a1aad9e3e",
   "metadata": {},
   "source": [
    "## Q6. How does the LOF algorithm compute anomaly scores?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c9f1171",
   "metadata": {},
   "source": [
    "The LOF (Local Outlier Factor) algorithm computes anomaly scores by quantifying the local deviation of a data point from its neighbors\n",
    "in a feature space. It identifies anomalies by comparing the density of data points in the neighborhood of each point to the density of their\n",
    "neighbors. Here's how the LOF algorithm computes anomaly scores:\n",
    "\n",
    "* #### Define a Neighborhood: \n",
    "For each data point, the LOF algorithm defines a neighborhood of other data points in the feature space. The size of the neighborhood is determined by a user-defined parameter, often denoted as \"k,\" which specifies the number of nearest neighbors to consider.\n",
    "\n",
    "* #### Calculate Reachability Distance: \n",
    "For each point in the dataset, the reachability distance to each of its k-nearest neighbors is computed. The reachability distance from point A to point B is defined as the maximum of two distances:\n",
    "\n",
    "       The Euclidean distance between points A and B.\n",
    "       The distance between point A and its k-th nearest neighbor (k-distance).\n",
    "       Mathematically, the reachability distance from point A to point B is given as:\n",
    "\n",
    "       ReachDist(A, B) = max(d(A, B), k-distance(A))\n",
    "\n",
    "  where d(A, B) is the Euclidean distance between points A and B.\n",
    "\n",
    "* #### Calculate Local Reachability Density (LRD): \n",
    "The local reachability density of a data point A is the inverse of the average reachability distance from point A to its k-nearest neighbors. It measures how dense the neighborhood of A is with respect to its neighbors.\n",
    "\n",
    "       LRD(A) = 1 / (mean(ReachDist(A, N)), for N in k-nearest neighbors of A)\n",
    "\n",
    "* #### Calculate Local Outlier Factor (LOF): \n",
    "The LOF of a data point A quantifies how much its local density differs from the local densities of its neighbors. It is calculated as the ratio of the average LRD of A's k-nearest neighbors to the LRD of A itself.\n",
    "\n",
    "       LOF(A) = (mean(LRD(Neighbors of A)) / LRD(A)), for N in k-nearest neighbors of A\n",
    "\n",
    "* #### Anomaly Score: \n",
    "The anomaly score for each data point is determined by its LOF value. A higher LOF indicates that the data point deviates from its local neighborhood, suggesting it may be an anomaly. Conversely, a lower LOF suggests that the data point is similar to its local neighborhood and is less likely to be an anomaly.\n",
    "\n",
    "* #### Thresholding: \n",
    "Anomaly scores can be thresholded to classify data points as anomalies or normals. A common approach is to set a threshold and classify data points with LOF values above the threshold as anomalies.\n",
    "\n",
    "In summary, the LOF algorithm computes anomaly scores by comparing the local density of each data point to the local densities of its neighbors. Anomalous data points are those that have significantly different local densities compared to their neighbors, as indicated by higher LOF values. LOF is particularly effective at identifying anomalies in datasets with varying local densities and complex structures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fcf0ea59",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7a839269-2938-476d-a229-541fd9d27b66",
   "metadata": {},
   "source": [
    "## Q7. What are the key parameters of the Isolation Forest algorithm?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ecc78ec",
   "metadata": {},
   "source": [
    "The Isolation Forest algorithm is an unsupervised anomaly detection method that works by isolating anomalies or outliers in a dataset. \n",
    "It uses decision trees to separate anomalies from normal data points. The main parameters of the Isolation Forest algorithm include:\n",
    "\n",
    "* #### Number of Trees (n_estimators):\n",
    "This parameter determines the number of decision trees to build in the ensemble. A larger number of trees can improve the algorithm's performance but may increase computation time.\n",
    "\n",
    "* #### Subsample Size (max_samples):\n",
    "It specifies the size of the random subsample of the dataset used to build each decision tree. Setting this parameter to a smaller value can speed up the training process and reduce memory usage but may also decrease the algorithm's accuracy.\n",
    "\n",
    "* #### Maximum Tree Depth (max_depth):\n",
    "This parameter sets the maximum depth of each decision tree. A deeper tree can capture more complex patterns but may be prone to \n",
    "overfitting. Setting this parameter appropriately is crucial to balancing model complexity and accuracy.\n",
    "\n",
    "* #### Contamination (contamination):\n",
    "Contamination is a user-defined parameter that represents the expected proportion of anomalies or outliers in the dataset. It helps the algorithm determine the threshold for classifying data points as anomalies or normals. For example, if contamination is set to 0.1, the algorithm will classify the top 10% of data points with the highest anomaly scores as anomalies.\n",
    "\n",
    "* #### Random Seed (random_state):\n",
    "This parameter allows you to set a random seed for reproducibility. By specifying the same random seed, you can ensure that the algorithm produces the same results when run multiple times.\n",
    "\n",
    "* #### Bootstrap (bootstrap):\n",
    "A Boolean parameter that determines whether or not to use bootstrapping when sampling data for each tree. Bootstrapping involves randomly selecting data points with replacement, which can introduce diversity into the training process.\n",
    "\n",
    "These parameters are essential for configuring the Isolation Forest algorithm to suit the characteristics of your dataset and the specific anomaly detection task. The choice of parameter values may depend on factors such as the size of the dataset, the expected proportion of anomalies, the computational resources available, and the desired trade-off between model complexity and accuracy. Proper hyperparameter tuning is often necessary to optimize the performance of the Isolation Forest for a given problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0bc87fa4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "897e54e1-d6a5-4d78-99e5-e8b17f77a496",
   "metadata": {},
   "source": [
    "## Q8. If a data point has only 2 neighbours of the same class within a radius of 0.5, what is its anomaly score using KNN with K=10?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282a8c19",
   "metadata": {},
   "source": [
    "To calculate the anomaly score of a data point using K-Nearest Neighbors (KNN) with K=10, you need to consider the density of points within \n",
    "its neighborhood. In this case, the data point has only 2 neighbors of the same class within a radius of 0.5. To compute its anomaly score, \n",
    "you can follow these steps:\n",
    "\n",
    "Compute the reachability distance (reach-dist) for the data point to each of its 2 neighbors. The reachability distance is the maximum of the \n",
    "Euclidean distance between the data point and its neighbor and the distance to the K-th nearest neighbor (K=10 in this case). Since K=10 is\n",
    "larger than the number of neighbors (2), the reachability distance will be the distance to the 10th nearest neighbor.\n",
    "\n",
    "Calculate the local reachability density (LRD) for the data point. LRD is the inverse of the average reachability distance from the data point\n",
    "to its neighbors. In this case, since you have 2 neighbors, you'll calculate the average reachability distance to these 2 neighbors and take \n",
    "the inverse.\n",
    "\n",
    "Compute the K-Nearest Neighbors (KNN) anomaly score (or LOF, Local Outlier Factor) for the data point. The KNN anomaly score compares the LRD \n",
    "of the data point to the LRD of its neighbors. Specifically, it's the ratio of the average LRD of the neighbors to the LRD of the data point \n",
    "itself.\n",
    "\n",
    "The exact calculations depend on the specific distances and data values, but the general formula for the KNN anomaly score for a data point\n",
    "\"X\" with neighbors \"N\" would be:\n",
    "\n",
    "    KNN Score(X) = (mean(LRD(N)) / LRD(X))\n",
    "\n",
    "    Where:\n",
    "\n",
    "    LRD(N) is the local reachability density of the neighbors.\n",
    "    LRD(X) is the local reachability density of the data point X.\n",
    "\n",
    "The resulting KNN anomaly score will indicate how different the local density of the data point is from its neighbors. A higher score suggests \n",
    "that the data point is an anomaly compared to its local neighborhood, while a lower score suggests that it is similar to its neighbors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9ef42bb4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "9ba6a879-70fc-45e5-99bf-296907745fd1",
   "metadata": {},
   "source": [
    "## Q9. Using the Isolation Forest algorithm with 100 trees and a dataset of 3000 data points, what is the anomaly score for a data point that has an average path length of 5.0 compared to the average path length of the trees?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a0d0948",
   "metadata": {},
   "source": [
    "In the Isolation Forest algorithm, the anomaly score of a data point is computed based on its average path length in the\n",
    "decision trees relative to the expected average path length for normal data points. The formula to calculate the anomaly score for a data \n",
    "point is as follows:\n",
    "\n",
    "    Anomaly Score = 2^(- (average path length / c(avg_path_length)))\n",
    "\n",
    "  Where:\n",
    "\n",
    "    \"average path length\" is the average path length of the data point across all trees.\n",
    "    \"c(avg_path_length)\" is the average path length of a data point in a randomly generated binary tree with the same number of data points.\n",
    "\n",
    "In your case, you have the following information:\n",
    "\n",
    "    Number of trees (n_estimators) = 100.\n",
    "    Total number of data points = 3000.\n",
    "    Average path length of the data point = 5.0.\n",
    "\n",
    "To calculate the anomaly score, you'll need to compute \"c(avg_path_length)\" first. This is done by generating a large number of random binary \n",
    "trees (e.g., 1000 trees) with 3000 data points each and calculating the average path length for a data point in these trees.\n",
    "\n",
    "Once you have \"c(avg_path_length),\" you can plug it into the formula along with the data point's average path length (5.0) to calculate the \n",
    "anomaly score.\n",
    "\n",
    "Please note that generating the random binary trees and computing \"c(avg_path_length)\" can be computationally expensive, so it's often done in\n",
    "practice using approximations or by sampling a smaller number of random trees. The specific value of \"c(avg_path_length)\" may vary depending\n",
    "on the implementation and settings of the Isolation Forest algorithm you are using."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4b10c959-2639-4c02-bc50-aedcee179ca6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "c(avg_path_length): 0.11556883734266465\n"
     ]
    }
   ],
   "source": [
    "from sklearn.ensemble import IsolationForest\n",
    "import numpy as np\n",
    "\n",
    "# Sample data with 3000 data points (you should replace this with your actual data)\n",
    "data = np.random.rand(3000, 2)\n",
    "\n",
    "# Create an Isolation Forest model with 100 trees (adjust as needed)\n",
    "model = IsolationForest(n_estimators=100)\n",
    "\n",
    "# Fit the model on your data\n",
    "model.fit(data)\n",
    "\n",
    "# Generate a random data point to compute c(avg_path_length)\n",
    "random_data_point = np.random.rand(1, 2)  # Replace with your data point\n",
    "\n",
    "# Compute c(avg_path_length) for the random data point\n",
    "c_avg_path_length = -np.mean(model.decision_function(random_data_point))\n",
    "\n",
    "print(\"c(avg_path_length):\", c_avg_path_length)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "6ba6953f-4d78-4866-beb3-a9e3eb502328",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Anomaly Score: [2.]\n"
     ]
    }
   ],
   "source": [
    "# Compute the average path length for the specific data point (replace with your actual data point)\n",
    "average_path_length = model.decision_function(random_data_point)\n",
    "\n",
    "# Calculate the anomaly score\n",
    "anomaly_score = 2 ** (- (average_path_length / c_avg_path_length))\n",
    "\n",
    "print(\"Anomaly Score:\", anomaly_score)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a490f2e7-223c-42f5-a288-4a233c4fd913",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}