SkillWisor

import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error, r2_score
from sklearn.model_selection import train_test_split

# Generate synthetic data for demonstration
# We create data where y has a linear relationship with X, plus some random noise
np.random.seed(42)  # for reproducibility
X = 2 * np.random.rand(100, 1)  # 100 samples, 1 feature (values between 0 and 2)
y = 4 + 3 * X + np.random.randn(100, 1)  # y = 4 + 3*X + Gaussian noise (intercept=4, slope=3)

# Split the data into training and testing sets
# This helps evaluate the model's performance on unseen data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# --- Using scikit-learn ---
print("--- scikit-learn Linear Regression ---")
# Initialize the LinearRegression model
model = LinearRegression()

# Train the model using the training data
# The fit method finds the optimal beta_0 and beta_1 values
model.fit(X_train, y_train)

# Make predictions on the test data
y_pred_sklearn = model.predict(X_test)

# Evaluate the model
# Mean Squared Error (MSE): Average of the squares of the errors. Lower is better.
mse_sklearn = mean_squared_error(y_test, y_pred_sklearn)
# R-squared (R²) Score: Proportion of the variance in the dependent variable that is predictable from the independent variable(s). Closer to 1 is better.
r2_sklearn = r2_score(y_test, y_pred_sklearn)

print(f"Intercept (beta_0): {model.intercept_[0]:.4f}") # Access the intercept
print(f"Coefficient (beta_1): {model.coef_[0][0]:.4f}") # Access the coefficient
print(f"Mean Squared Error: {mse_sklearn:.4f}")
print(f"R² Score: {r2_sklearn:.4f}")

# Plot the results for scikit-learn model
plt.figure(figsize=(10, 6))
plt.scatter(X_test, y_test, color='blue', alpha=0.7, label='Actual values')
plt.plot(X_test, y_pred_sklearn, color='red', linewidth=2, label='Predicted line (sklearn)')
plt.title('Linear Regression (scikit-learn)')
plt.xlabel('X (Feature)')
plt.ylabel('y (Target)')
plt.legend()
plt.grid(True)
plt.show()

# --- Implementing Linear Regression from scratch using the Normal Equation ---
print("\n--- Linear Regression from Scratch (Normal Equation) ---")
def linear_regression_normal_equation(X_data, y_data):
    """
    Calculates linear regression coefficients using the Normal Equation.
    
    Args:
        X_data (np.array): Feature matrix (m_samples, n_features).
        y_data (np.array): Target vector (m_samples, 1).
        
    Returns:
        np.array: Coefficient vector (n_features + 1, 1), including intercept.
    """
    # Add a column of ones to X_data for the intercept term (beta_0)
    # np.c_ is a convenient way to concatenate arrays column-wise
    X_b = np.c_[np.ones((X_data.shape[0], 1)), X_data] # X_b is now (m_samples, n_features + 1)
    
    # Compute the parameter vector using the normal equation: beta_hat = (X_b^T * X_b)^(-1) * X_b^T * y
    try:
        # X_b.T @ X_b is equivalent to np.dot(X_b.T, X_b) or X_b.T.dot(X_b)
        beta_hat = np.linalg.inv(X_b.T @ X_b) @ X_b.T @ y_data
    except np.linalg.LinAlgError:
        # This can happen if X_b.T @ X_b is singular (not invertible)
        # Often due to perfect multicollinearity or if num_features > num_samples
        print("Error: Singular matrix. Cannot compute inverse. Consider using Moore-Penrose pseudo-inverse or gradient descent.")
        # Using pseudo-inverse as a fallback (more robust but computationally more expensive)
        beta_hat = np.linalg.pinv(X_b.T @ X_b) @ X_b.T @ y_data
        
    return beta_hat

# Train the model using the normal equation on the training data
theta_scratch = linear_regression_normal_equation(X_train, y_train)

# The first element of theta_scratch is the intercept, the rest are coefficients
intercept_scratch = theta_scratch[0][0]
coefficient_scratch = theta_scratch[1][0]

print(f"From scratch - Intercept (beta_0): {intercept_scratch:.4f}")
print(f"From scratch - Coefficient (beta_1): {coefficient_scratch:.4f}")

# Make predictions using the from-scratch model
X_test_b = np.c_[np.ones((X_test.shape[0], 1)), X_test] # Add intercept term to test data
y_pred_scratch = X_test_b @ theta_scratch

# Evaluate the from-scratch model
mse_scratch = mean_squared_error(y_test, y_pred_scratch)
r2_scratch = r2_score(y_test, y_pred_scratch)
print(f"From scratch - Mean Squared Error: {mse_scratch:.4f}")
print(f"From scratch - R² Score: {r2_scratch:.4f}")

# Plot the results for the from-scratch model
plt.figure(figsize=(10, 6))
plt.scatter(X_test, y_test, color='green', alpha=0.7, label='Actual values')
plt.plot(X_test, y_pred_scratch, color='purple', linewidth=2, label='Predicted line (from scratch)')
plt.title('Linear Regression (from Scratch)')
plt.xlabel('X (Feature)')
plt.ylabel('y (Target)')
plt.legend()
plt.grid(True)
plt.show()

import numpy as np
import matplotlib.pyplot as plt
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, classification_report, confusion_matrix
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_classification # For generating synthetic classification data
from sklearn.preprocessing import StandardScaler

# Generate synthetic data for binary classification
# n_features=2 for easy visualization
X, y = make_classification(n_samples=1000, n_features=2, n_informative=2, 
                           n_redundant=0, n_clusters_per_class=1, random_state=42)

# Split the data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# Standardize features (important for gradient descent based algorithms)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)


# --- Using scikit-learn ---
print("--- scikit-learn Logistic Regression ---")
# Initialize the LogisticRegression model
# C is the inverse of regularization strength; smaller values specify stronger regularization.
# solver='liblinear' is good for small datasets. 'lbfgs' is a common default.
model_sklearn = LogisticRegression(random_state=42, solver='liblinear', C=1.0)

# Train the model
model_sklearn.fit(X_train_scaled, y_train)

# Make predictions
y_pred_sklearn = model_sklearn.predict(X_test_scaled)
y_prob_sklearn = model_sklearn.predict_proba(X_test_scaled)[:, 1] # Probabilities for class 1

# Evaluate the model
accuracy_sklearn = accuracy_score(y_test, y_pred_sklearn)
print(f"Accuracy: {accuracy_sklearn:.4f}")
print("\nClassification Report (sklearn):")
print(classification_report(y_test, y_pred_sklearn))
print("\nConfusion Matrix (sklearn):")
print(confusion_matrix(y_test, y_pred_sklearn))

# Plot the decision boundary for scikit-learn model
def plot_decision_boundary(X_plot, y_plot, model_to_plot, title, scaler_obj=None):
    plt.figure(figsize=(10, 6))
    
    # Create a mesh grid
    h = 0.02 # step size in the mesh
    x_min, x_max = X_plot[:, 0].min() - 0.5, X_plot[:, 0].max() + 0.5
    y_min, y_max = X_plot[:, 1].min() - 0.5, X_plot[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
    
    # Meshgrid points to predict
    mesh_points = np.c_[xx.ravel(), yy.ravel()]
    
    # If data was scaled, scale mesh points before prediction
    if scaler_obj:
        mesh_points_scaled = scaler_obj.transform(mesh_points)
        Z = model_to_plot.predict(mesh_points_scaled)
    else: # For from-scratch model if it doesn't use scaled data internally for prediction
        Z = model_to_plot.predict(mesh_points) # Assuming from-scratch predict handles intercept
        
    Z = Z.reshape(xx.shape)
    
    # Plot the decision boundary and data points
    plt.contourf(xx, yy, Z, alpha=0.4, cmap=plt.cm.RdYlBu)
    plt.scatter(X_plot[:, 0], X_plot[:, 1], c=y_plot, s=20, edgecolor='k', cmap=plt.cm.RdYlBu)
    
    plt.title(title)
    plt.xlabel('Feature 1 (Scaled)' if scaler_obj else 'Feature 1')
    plt.ylabel('Feature 2 (Scaled)' if scaler_obj else 'Feature 2')
    plt.grid(True)
    plt.show()

# Use original X_test for plotting, but scale it inside the plot_decision_boundary if needed
# or pass X_test_scaled directly. For consistency with how model was trained:
plot_decision_boundary(X_test_scaled, y_test, model_sklearn, 'Logistic Regression Decision Boundary (sklearn)', scaler_obj=None) # Model expects scaled data

# --- Implementing Logistic Regression from scratch using Gradient Descent ---
print("\n--- Logistic Regression from Scratch (Gradient Descent) ---")

def sigmoid(z):
    """Computes the sigmoid function."""
    return 1 / (1 + np.exp(-z))

class LogisticRegressionScratch:
    def __init__(self, learning_rate=0.01, num_iterations=10000, verbose=False, tol=1e-4):
        self.learning_rate = learning_rate
        self.num_iterations = num_iterations
        self.verbose = verbose
        self.tol = tol # Tolerance for convergence
        self.theta = None # Weights and bias

    def _add_intercept(self, X):
        """Adds an intercept term (column of ones) to X."""
        return np.c_[np.ones((X.shape[0], 1)), X]

    def fit(self, X, y):
        """Trains the logistic regression model using gradient descent."""
        X_b = self._add_intercept(X) # Add intercept: X_b is (n_samples, n_features + 1)
        n_samples, n_features_plus_intercept = X_b.shape
        
        # Initialize parameters (weights theta) to zeros
        self.theta = np.zeros((n_features_plus_intercept, 1))
        y = y.reshape(-1, 1) # Ensure y is a column vector
        
        # Gradient descent loop
        for i in range(self.num_iterations):
            # Calculate linear combination: z = X_b * theta
            z = X_b @ self.theta
            # Apply sigmoid function to get probabilities: h = sigma(z)
            h = sigmoid(z)
            
            # Calculate gradient of the cost function
            # gradient = (1/n_samples) * X_b^T * (h - y)
            gradient = (1 / n_samples) * X_b.T @ (h - y)
            
            # Update parameters: theta = theta - learning_rate * gradient
            prev_theta = self.theta.copy()
            self.theta = self.theta - self.learning_rate * gradient
            
            # Optional: Print cost every 1000 iterations
            if self.verbose and i % 1000 == 0:
                cost = self._compute_cost(X_b, y, h)
                print(f"Iteration {i}, Cost: {cost:.4f}")

            # Check for convergence
            if np.linalg.norm(self.theta - prev_theta) < self.tol:
                if self.verbose:
                    print(f"Converged at iteration {i}.")
                break
        if self.verbose and i == self.num_iterations -1:
             print(f"Reached max iterations ({self.num_iterations}).")


    def _compute_cost(self, X_b, y, h):
        """Computes the cost (negative log-likelihood)."""
        n_samples = y.shape[0]
        # Add epsilon to log arguments to prevent log(0)
        epsilon = 1e-7 
        cost = - (1 / n_samples) * np.sum(y * np.log(h + epsilon) + (1 - y) * np.log(1 - h + epsilon))
        return cost

    def predict_proba(self, X):
        """Predicts probabilities for each class."""
        X_b = self._add_intercept(X)
        return sigmoid(X_b @ self.theta)

    def predict(self, X, threshold=0.5):
        """Predicts class labels based on a threshold."""
        probabilities = self.predict_proba(X)
        return (probabilities >= threshold).astype(int)

# Train the from-scratch model
# Using scaled data is crucial for gradient descent to converge well
model_scratch = LogisticRegressionScratch(learning_rate=0.1, num_iterations=5000, verbose=True)
model_scratch.fit(X_train_scaled, y_train)

# Make predictions with the from-scratch model
y_pred_scratch = model_scratch.predict(X_test_scaled)

# Evaluate the from-scratch model
accuracy_scratch = accuracy_score(y_test, y_pred_scratch)
print(f"\nFrom scratch - Accuracy: {accuracy_scratch:.4f}")
print("\nClassification Report (from scratch):")
print(classification_report(y_test, y_pred_scratch))
print("\nConfusion Matrix (from scratch):")
print(confusion_matrix(y_test, y_pred_scratch))

# For plotting the decision boundary of the from-scratch model
# We need a wrapper or to adjust the plot_decision_boundary function
# The from-scratch model's predict method already handles the intercept if fit was called.
# The plot_decision_boundary function needs X data without intercept for meshgrid creation.
# The model's predict method will add intercept internally.
plot_decision_boundary(X_test_scaled, y_test, model_scratch, 'Logistic Regression Decision Boundary (from Scratch)', scaler_obj=None)

import numpy as np
import matplotlib.pyplot as plt
from sklearn.svm import SVC # Support Vector Classifier
from sklearn.metrics import accuracy_score, classification_report
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_classification, make_moons, make_circles # Datasets for testing
from sklearn.preprocessing import StandardScaler

# Generate synthetic non-linear data (moons are good for this)
X, y = make_moons(n_samples=200, noise=0.15, random_state=42)
# Alternatively, for more complex boundaries:
# X, y = make_circles(n_samples=200, noise=0.1, factor=0.5, random_state=42)

# Split the data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Standardize the features (very important for SVM, especially with RBF kernel)
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# --- Using scikit-learn ---
print("--- scikit-learn SVM ---")

# Train SVM models with different kernels
# Kernels to test: 'linear', 'poly', 'rbf'
# C is the regularization parameter.
# gamma ('scale' or 'auto' or a float) is the kernel coefficient for 'rbf', 'poly', 'sigmoid'.
# degree is for 'poly' kernel.

kernels_to_test = {
    'Linear (C=1.0)': SVC(kernel='linear', C=1.0, random_state=42, probability=True),
    'RBF (C=1.0, gamma=auto)': SVC(kernel='rbf', C=1.0, gamma='auto', random_state=42, probability=True),
    'RBF (C=1.0, gamma=1.0)': SVC(kernel='rbf', C=1.0, gamma=1.0, random_state=42, probability=True),
    'RBF (C=10.0, gamma=auto)': SVC(kernel='rbf', C=10.0, gamma='auto', random_state=42, probability=True),
    'Polynomial (degree=3, C=1.0)': SVC(kernel='poly', degree=3, C=1.0, random_state=42, probability=True)
}

svm_models = {}

for name, model_instance in kernels_to_test.items():
    print(f"\nTraining SVM with {name}...")
    model_instance.fit(X_train_scaled, y_train)
    svm_models[name] = model_instance
    
    y_pred = model_instance.predict(X_test_scaled)
    accuracy = accuracy_score(y_test, y_pred)
    
    print(f"Accuracy for {name}: {accuracy:.4f}")
    # print("Classification Report:")
    # print(classification_report(y_test, y_pred))

# Plot decision boundaries for different SVM models
def plot_decision_boundary_svm_detailed(X_data_scaled, y_data, models_dict, scaler_obj):
    num_models = len(models_dict)
    # Determine grid size for subplots (e.g., 2x3 or 3x2)
    n_cols = 3 
    n_rows = (num_models + n_cols - 1) // n_cols # Calculate rows needed
    
    plt.figure(figsize=(n_cols * 5, n_rows * 4)) # Adjust figure size
    
    # Create a mesh grid based on scaled data
    h = 0.02 # step size in the mesh
    x_min, x_max = X_data_scaled[:, 0].min() - 0.5, X_data_scaled[:, 0].max() + 0.5
    y_min, y_max = X_data_scaled[:, 1].min() - 0.5, X_data_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
    
    mesh_points = np.c_[xx.ravel(), yy.ravel()] # These are already in "scaled" space
    
    for i, (name, model) in enumerate(models_dict.items()):
        plt.subplot(n_rows, n_cols, i + 1)
        
        # Predict using the model
        Z = model.predict(mesh_points) # Model expects scaled data
        Z = Z.reshape(xx.shape)
        
        # Plot the decision boundary
        plt.contourf(xx, yy, Z, alpha=0.4, cmap=plt.cm.coolwarm)
        
        # Plot the training/test points (use original scaled data for plotting)
        plt.scatter(X_data_scaled[:, 0], X_data_scaled[:, 1], c=y_data, cmap=plt.cm.coolwarm, s=20, edgecolors='k')
        
        # Highlight support vectors (if the model is SVC and probability=False or not too many)
        if hasattr(model, 'support_vectors_'):
            sv = model.support_vectors_ # These are in scaled space
            plt.scatter(sv[:, 0], sv[:, 1], s=100, facecolors='none', edgecolors='k', linewidths=1.5, label='Support Vectors')
        
        plt.title(name)
        plt.xlabel('Feature 1 (Scaled)')
        plt.ylabel('Feature 2 (Scaled)')
        plt.xlim(xx.min(), xx.max())
        plt.ylim(yy.min(), yy.max())
        plt.xticks(())
        plt.yticks(())
        if i == 0: plt.legend() # Show legend only on the first plot if support vectors are highlighted

    plt.tight_layout()
    plt.show()

# Plotting with X_test_scaled and y_test
plot_decision_boundary_svm_detailed(X_test_scaled, y_test, svm_models, scaler)

# Note: A from-scratch implementation of SVM is complex, involving quadratic programming.
# It's beyond the scope of a typical "from scratch" section in such guides unless highly simplified.
# Key concepts to understand are margin maximization, slack variables, and the kernel trick.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor, plot_tree
from sklearn.metrics import accuracy_score, classification_report, mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_classification, make_regression # For synthetic data

# --- Classification Example ---
print("--- Decision Tree Classification ---")
# Generate synthetic classification data
X_c, y_c = make_classification(n_samples=1000, n_features=5, n_informative=3, 
                               n_redundant=1, n_clusters_per_class=1, random_state=42)
feature_names_c = [f"Feature_{i}" for i in range(X_c.shape[1])]
class_names_c = [f"Class_{i}" for i in np.unique(y_c)]

# Split the data
X_c_train, X_c_test, y_c_train, y_c_test = train_test_split(X_c, y_c, test_size=0.2, random_state=42)

# Train the model with different maximum depths (to show effect on overfitting)
# Criterion can be 'gini' or 'entropy'
max_depths = [2, 3, 5, None] # None means nodes are expanded until all leaves are pure or contain less than min_samples_split samples
dt_models_c = {}

for depth in max_depths:
    model_name = f"Depth_{depth if depth is not None else 'Unlimited'}"
    # Using Gini impurity by default
    dt_models_c[model_name] = DecisionTreeClassifier(max_depth=depth, random_state=42, criterion='gini')
    dt_models_c[model_name].fit(X_c_train, y_c_train)
    
    y_c_pred = dt_models_c[model_name].predict(X_c_test)
    accuracy = accuracy_score(y_c_test, y_c_pred)
    
    depth_str = str(depth) if depth is not None else "Unlimited"
    print(f"\nDecision Tree (Classification) with max_depth={depth_str}:")
    print(f"Accuracy: {accuracy:.4f}")
    if depth == 3: # Print detailed report for one model
        print("Classification Report:")
        print(classification_report(y_c_test, y_c_pred, target_names=class_names_c))

# Visualize a decision tree (e.g., the one with max_depth=3)
plt.figure(figsize=(20, 12)) # Increased figure size for better readability
plot_tree(dt_models_c['Depth_3'], 
          feature_names=feature_names_c, 
          class_names=class_names_c, 
          filled=True, 
          rounded=True,
          fontsize=10)
plt.title('Decision Tree (Classification, max_depth=3, Gini)', fontsize=16)
plt.show()

# Feature importance from a reasonably complex tree (e.g., depth 5 or unlimited if not too large)
model_for_importance = dt_models_c.get('Depth_5', dt_models_c.get('Depth_Unlimited'))
if model_for_importance:
    plt.figure(figsize=(10, 6))
    importances = model_for_importance.feature_importances_
    indices = np.argsort(importances)[::-1]
    sorted_feature_names = [feature_names_c[i] for i in indices]

    plt.bar(range(X_c.shape[1]), importances[indices], color='skyblue')
    plt.xticks(range(X_c.shape[1]), sorted_feature_names, rotation=45, ha="right")
    plt.xlabel('Features')
    plt.ylabel('Importance (Gini Importance)')
    plt.title('Feature Importance (Decision Tree Classifier)')
    plt.tight_layout()
    plt.show()

# --- Implementing key parts of a decision tree from scratch (for illustration) ---
print("\n--- Decision Tree from Scratch (Conceptual Parts) ---")

def calculate_gini_impurity(y_labels):
    """Calculates Gini impurity for a set of labels."""
    if len(y_labels) == 0:
        return 0
    
    # Count occurrences of each class
    _, counts = np.unique(y_labels, return_counts=True)
    # Calculate proportions
    proportions = counts / len(y_labels)
    # Calculate Gini impurity
    gini = 1 - np.sum(proportions**2)
    return gini

def calculate_entropy(y_labels):
    """Calculates Entropy for a set of labels."""
    if len(y_labels) == 0:
        return 0.0
    _, counts = np.unique(y_labels, return_counts=True)
    probabilities = counts / len(y_labels)
    # Entropy calculation, handling p=0 case where log2(p) is undefined (p*log2(p) = 0)
    entropy = -np.sum([p * np.log2(p) for p in probabilities if p > 0])
    return entropy

def find_best_split_classification(X_node, y_node, criterion_func=calculate_gini_impurity):
    """
    Finds the best feature and threshold for splitting a node in a classification tree.
    This is a simplified version focusing on numerical features.
    """
    num_samples_node, num_features_node = X_node.shape
    if num_samples_node <= 1: # Cannot split further
        return None, None, -1 # No feature, no threshold, no gain

    # Calculate impurity of the current node before split (parent impurity)
    parent_impurity = criterion_func(y_node)
    
    best_feature_idx = None
    best_threshold_val = None
    max_info_gain = -1.0 # Initialize with a very small number

    # Iterate over all features
    for feature_idx in range(num_features_node):
        # Get unique values in the current feature column to use as potential thresholds
        unique_feature_values = np.unique(X_node[:, feature_idx])
        
        if len(unique_feature_values) <= 1: # Cannot split on this feature if all values are the same
            continue

        # Iterate over unique values as potential split thresholds
        # A common strategy is to use midpoints between sorted unique values
        potential_thresholds = (unique_feature_values[:-1] + unique_feature_values[1:]) / 2.0
        
        for threshold in potential_thresholds:
            # Split the data based on the current feature and threshold
            left_indices = X_node[:, feature_idx] <= threshold
            right_indices = X_node[:, feature_idx] > threshold
            
            y_left, y_right = y_node[left_indices], y_node[right_indices]
            
            # Skip if a split results in an empty child node
            if len(y_left) == 0 or len(y_right) == 0:
                continue
            
            # Calculate impurity for left and right children
            impurity_left = criterion_func(y_left)
            impurity_right = criterion_func(y_right)
            
            # Calculate weighted average impurity of children
            num_left, num_right = len(y_left), len(y_right)
            weighted_child_impurity = (num_left / num_samples_node) * impurity_left + \
                                      (num_right / num_samples_node) * impurity_right
            
            # Calculate information gain
            current_info_gain = parent_impurity - weighted_child_impurity
            
            # Update best split if current split is better
            if current_info_gain > max_info_gain:
                max_info_gain = current_info_gain
                best_feature_idx = feature_idx
                best_threshold_val = threshold
                
    return best_feature_idx, best_threshold_val, max_info_gain

# Example usage of scratch functions:
print(f"Gini impurity of y_c_train: {calculate_gini_impurity(y_c_train):.4f}")
print(f"Entropy of y_c_train: {calculate_entropy(y_c_train):.4f}")

# Find best split for the root node of the training data (using Gini)
best_feat, best_thresh, gain = find_best_split_classification(X_c_train, y_c_train, calculate_gini_impurity)
if best_feat is not None:
    print(f"Best initial split: Feature {best_feat} at threshold {best_thresh:.4f} with Gini Gain {gain:.4f}")
else:
    print("No beneficial split found for the root node.")

# Note: A complete from-scratch implementation would involve recursively building the tree,
# handling stopping conditions (max depth, min samples per leaf, min impurity decrease),
# and implementing prediction logic by traversing the tree. This is quite involved.
# The functions above illustrate the core logic of impurity calculation and finding the best split.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import RandomForestClassifier, RandomForestRegressor
from sklearn.metrics import accuracy_score, classification_report, mean_squared_error
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.datasets import make_classification, make_regression

# --- Classification Example ---
print("--- Random Forest Classification ---")
# Generate synthetic classification data
X_c, y_c = make_classification(n_samples=1000, n_features=20, n_informative=10, 
                               n_redundant=5, n_clusters_per_class=1, random_state=42)
feature_names_c = [f"Feature_{i}" for i in range(X_c.shape[1])]

# Split the data
X_c_train, X_c_test, y_c_train, y_c_test = train_test_split(X_c, y_c, test_size=0.2, random_state=42)

# Train the model with different numbers of trees (n_estimators)
# oob_score=True allows us to get an estimate of generalization error
n_estimators_list = [10, 50, 100, 200]
rf_models_c = {}

for n_trees in n_estimators_list:
    model_name = f"Trees_{n_trees}"
    # max_features='sqrt' is common for classification
    rf_models_c[model_name] = RandomForestClassifier(n_estimators=n_trees, 
                                                     max_features='sqrt', 
                                                     random_state=42,
                                                     oob_score=True,
                                                     n_jobs=-1) # Use all available cores
    rf_models_c[model_name].fit(X_c_train, y_c_train)
    
    y_c_pred = rf_models_c[model_name].predict(X_c_test)
    accuracy = accuracy_score(y_c_test, y_c_pred)
    
    print(f"\nRandom Forest (Classification) with {n_trees} trees:")
    print(f"Accuracy: {accuracy:.4f}")
    print(f"OOB Score: {rf_models_c[model_name].oob_score_:.4f}") # Out-of-Bag score
    if n_trees == 100: # Print detailed report for one model
        print("Classification Report:")
        print(classification_report(y_c_test, y_c_pred))

# Perform cross-validation on the model with 100 trees
best_rf_model_c = rf_models_c['Trees_100']
cv_scores = cross_val_score(best_rf_model_c, X_c, y_c, cv=5, scoring='accuracy') # 5-fold CV
print(f"\nCross-validation scores (Accuracy) for 100 trees: {cv_scores}")
print(f"Mean CV Accuracy: {cv_scores.mean():.4f} ± {cv_scores.std():.4f}")

# Feature importance (Random Forest provides this as an average over trees)
plt.figure(figsize=(12, 7))
importances = best_rf_model_c.feature_importances_
indices = np.argsort(importances)[::-1]
sorted_feature_names = [feature_names_c[i] for i in indices]

plt.bar(range(X_c.shape[1]), importances[indices], color='lightgreen', align='center')
plt.xticks(range(X_c.shape[1]), sorted_feature_names, rotation=60, ha="right")
plt.xlabel('Features')
plt.ylabel('Importance (Mean Decrease in Impurity)')
plt.title('Feature Importance in Random Forest Classifier')
plt.tight_layout()
plt.show()


# --- Implementing a simplified Random Forest from scratch (for illustration) ---
# This uses the previously defined conceptual Decision Tree parts.
# A full, robust SimpleDecisionTree class would be needed.
# For simplicity, we'll assume a basic structure for SimpleDecisionTree.

print("\n--- Random Forest from Scratch (Conceptual) ---")

# (Re-using calculate_gini_impurity and find_best_split_classification from Decision Tree section)
# For this scratch RF, we need a simplified Decision Tree that can be trained and predict.

class SimpleScratchDecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2, criterion_func=calculate_gini_impurity, num_features_subset=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.criterion_func = criterion_func
        self.num_features_subset = num_features_subset # For random feature selection
        self.tree_ = None # Stores the learned tree structure

    def _build_tree(self, X_node, y_node, current_depth):
        # Stopping conditions
        num_samples_node, num_features_node = X_node.shape
        if (self.max_depth is not None and current_depth >= self.max_depth) or \
           num_samples_node < self.min_samples_split or \
           len(np.unique(y_node)) == 1: # Pure node
            # Leaf node: predict the majority class
            leaf_value = np.bincount(y_node).argmax()
            return leaf_value

        # Feature subset selection for current split
        if self.num_features_subset is not None and self.num_features_subset < num_features_node:
            feature_indices_to_consider = np.random.choice(num_features_node, self.num_features_subset, replace=False)
        else:
            feature_indices_to_consider = np.arange(num_features_node)
        
        X_subset = X_node[:, feature_indices_to_consider]

        # Find the best split using only the subset of features
        # (find_best_split_classification needs to be adapted or used carefully if feature_indices_to_consider is used)
        # For simplicity, we'll assume find_best_split works on X_subset and returns original indices if needed,
        # or we modify find_best_split to accept feature_indices_to_consider.
        # Here, we'll call it on X_subset and if a split is found, map the feature_idx back.
        
        best_feature_idx_subset, best_threshold_val, gain = find_best_split_classification(X_subset, y_node, self.criterion_func)

        if best_feature_idx_subset is None or gain <= 0: # No beneficial split found
            leaf_value = np.bincount(y_node).argmax()
            return leaf_value
        
        # Map subset feature index back to original feature index
        best_feature_idx_original = feature_indices_to_consider[best_feature_idx_subset]

        # Split data
        left_indices = X_node[:, best_feature_idx_original] <= best_threshold_val
        right_indices = X_node[:, best_feature_idx_original] > best_threshold_val
        
        # Handle cases where a split doesn't actually divide the data (e.g., all points go to one side)
        if not np.any(left_indices) or not np.any(right_indices):
            leaf_value = np.bincount(y_node).argmax()
            return leaf_value

        # Recursively build subtrees
        left_subtree = self._build_tree(X_node[left_indices], y_node[left_indices], current_depth + 1)
        right_subtree = self._build_tree(X_node[right_indices], y_node[right_indices], current_depth + 1)
        
        return (best_feature_idx_original, best_threshold_val, left_subtree, right_subtree)

    def fit(self, X, y):
        self.tree_ = self._build_tree(X, y, 0)
        return self

    def _predict_one(self, x_sample, node):
        if not isinstance(node, tuple): # Leaf node
            return node
        
        feature_idx, threshold, left_subtree, right_subtree = node
        if x_sample[feature_idx] <= threshold:
            return self._predict_one(x_sample, left_subtree)
        else:
            return self._predict_one(x_sample, right_subtree)

    def predict(self, X):
        return np.array([self._predict_one(x_sample, self.tree_) for x_sample in X])


class SimpleScratchRandomForestClassifier:
    def __init__(self, n_estimators=10, max_depth=None, min_samples_split=2, max_features_ratio=0.5):
        self.n_estimators = n_estimators
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features_ratio = max_features_ratio # Ratio of features to consider for a split
        self.trees_ = []
        self.feature_indices_per_tree_ = [] # To store which features were selected for each tree (optional)

    def fit(self, X, y):
        self.trees_ = []
        n_samples, n_features = X.shape
        num_features_subset = int(n_features * self.max_features_ratio)
        if num_features_subset == 0: num_features_subset = 1 # At least one feature

        for _ in range(self.n_estimators):
            # Bootstrap sampling
            bootstrap_indices = np.random.choice(n_samples, n_samples, replace=True)
            X_bootstrap, y_bootstrap = X[bootstrap_indices], y[bootstrap_indices]
            
            # Initialize and train a decision tree
            tree = SimpleScratchDecisionTree(max_depth=self.max_depth, 
                                             min_samples_split=self.min_samples_split,
                                             num_features_subset=num_features_subset)
            tree.fit(X_bootstrap, y_bootstrap)
            self.trees_.append(tree)
        return self

    def predict(self, X):
        # Get predictions from all trees
        tree_predictions = np.array([tree.predict(X) for tree in self.trees_]) # Shape: (n_estimators, n_samples_X)
        
        # Majority vote for each sample
        # scipy.stats.mode can do this efficiently along an axis
        # For simplicity, a loop:
        final_predictions = np.zeros(X.shape[0], dtype=int)
        for i in range(X.shape[0]): # For each sample
            votes = tree_predictions[:, i]
            final_predictions[i] = np.bincount(votes.astype(int)).argmax() # astype(int) if predictions can be float
            
        return final_predictions

# Test the scratch Random Forest (this is very basic and for illustration)
# Note: The SimpleScratchDecisionTree and RandomForest are highly simplified.
# For robust performance, scikit-learn's implementation is far more optimized and complete.
print("\nTraining simplified scratch Random Forest (may be slow and basic)...")
# Using a small subset of data and few estimators for speed
X_c_train_small, y_c_train_small = X_c_train[:200], y_c_train[:200] # Smaller dataset
X_c_test_small, y_c_test_small = X_c_test[:50], y_c_test[:50]

scratch_rf = SimpleScratchRandomForestClassifier(n_estimators=5, max_depth=5, max_features_ratio=0.7)
scratch_rf.fit(X_c_train_small, y_c_train_small)
y_pred_scratch_rf = scratch_rf.predict(X_c_test_small)

accuracy_scratch_rf = accuracy_score(y_c_test_small, y_pred_scratch_rf)
print(f"Simplified Scratch Random Forest Accuracy: {accuracy_scratch_rf:.4f}")
# End of conceptual scratch implementation part.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.metrics import accuracy_score, classification_report, mean_squared_error
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.datasets import make_classification, make_regression
from sklearn.preprocessing import StandardScaler
from collections import Counter # For majority voting in scratch implementation

# --- Classification Example ---
print("--- k-NN Classification ---")
# Generate synthetic classification data
X_c, y_c = make_classification(n_samples=500, n_features=2, n_informative=2, 
                               n_redundant=0, n_clusters_per_class=1, random_state=42)

# Split the data
X_c_train, X_c_test, y_c_train, y_c_test = train_test_split(X_c, y_c, test_size=0.3, random_state=42)

# Standardize features (VERY important for k-NN)
scaler_c = StandardScaler()
X_c_train_scaled = scaler_c.fit_transform(X_c_train)
X_c_test_scaled = scaler_c.transform(X_c_test)

# Train k-NN classifiers with different values of k
k_values = [1, 3, 5, 7, 10, 15]
knn_models_c = {}

for k_val in k_values:
    model_name = f"k={k_val}"
    # 'uniform' weights: all points in each neighborhood are weighted equally.
    # 'distance' weights: closer neighbors have a greater influence.
    # p=2 for Euclidean distance (Minkowski p-parameter)
    knn_models_c[model_name] = KNeighborsClassifier(n_neighbors=k_val, weights='uniform', p=2)
    knn_models_c[model_name].fit(X_c_train_scaled, y_c_train)
    
    y_c_pred = knn_models_c[model_name].predict(X_c_test_scaled)
    accuracy = accuracy_score(y_c_test, y_c_pred)
    
    print(f"\nk-NN Classifier with {model_name}:")
    print(f"Accuracy: {accuracy:.4f}")
    if k_val == 5: # Print detailed report for one model
        print("Classification Report (k=5):")
        print(classification_report(y_c_test, y_c_pred))

# Plot decision boundary for k=5 (example)
def plot_decision_boundary_knn(X_plot_scaled, y_plot, model_to_plot, title):
    plt.figure(figsize=(10, 6))
    h = 0.02 # step size in the mesh
    x_min, x_max = X_plot_scaled[:, 0].min() - 0.5, X_plot_scaled[:, 0].max() + 0.5
    y_min, y_max = X_plot_scaled[:, 1].min() - 0.5, X_plot_scaled[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))
    
    mesh_points = np.c_[xx.ravel(), yy.ravel()] # Already in "scaled" space
    Z = model_to_plot.predict(mesh_points)
    Z = Z.reshape(xx.shape)
    
    plt.contourf(xx, yy, Z, alpha=0.4, cmap=plt.cm.RdYlBu)
    plt.scatter(X_plot_scaled[:, 0], X_plot_scaled[:, 1], c=y_plot, s=20, edgecolor='k', cmap=plt.cm.RdYlBu)
    plt.title(title)
    plt.xlabel('Feature 1 (Scaled)')
    plt.ylabel('Feature 2 (Scaled)')
    plt.grid(True)
    plt.show()

plot_decision_boundary_knn(X_c_test_scaled, y_c_test, knn_models_c['k=5'], 'k-NN Decision Boundary (k=5, scikit-learn)')


# --- Implementing k-NN Classifier from scratch ---
print("\n--- k-NN Classifier from Scratch ---")

def euclidean_distance(point1, point2):
    """Calculates Euclidean distance between two points."""
    return np.sqrt(np.sum((point1 - point2)**2))

class KNNClassifierScratch:
    def __init__(self, k=3):
        self.k = k
        self.X_train = None
        self.y_train = None

    def fit(self, X_train_data, y_train_data):
        """Stores the training data. k-NN is a lazy learner."""
        self.X_train = X_train_data
        self.y_train = y_train_data

    def _predict_one(self, x_test_sample):
        """Predicts the class for a single test sample."""
        # 1. Calculate distances from x_test_sample to all training samples
        distances = [euclidean_distance(x_test_sample, x_train_sample) for x_train_sample in self.X_train]
        
        # 2. Get indices of the k nearest neighbors
        # np.argsort returns indices that would sort an array
        k_nearest_indices = np.argsort(distances)[:self.k]
        
        # 3. Get the labels of these k nearest neighbors
        k_nearest_labels = [self.y_train[i] for i in k_nearest_indices]
        
        # 4. Perform majority vote
        # Counter is useful for finding the most common element
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0] # Returns the label

    def predict(self, X_test_data):
        """Predicts class labels for a set of test samples."""
        if self.X_train is None or self.y_train is None:
            raise ValueError("Model has not been trained yet. Call fit() first.")
        
        predictions = [self._predict_one(x_test_sample) for x_test_sample in X_test_data]
        return np.array(predictions)

# Test the scratch k-NN classifier
# Using scaled data is crucial
knn_scratch = KNNClassifierScratch(k=5)
knn_scratch.fit(X_c_train_scaled, y_c_train)
y_pred_scratch_knn = knn_scratch.predict(X_c_test_scaled)

accuracy_scratch_knn = accuracy_score(y_c_test, y_pred_scratch_knn)
print(f"Scratch k-NN Classifier (k=5) Accuracy: {accuracy_scratch_knn:.4f}")
print("Classification Report (Scratch k-NN, k=5):")
print(classification_report(y_c_test, y_pred_scratch_knn))
# Note: Plotting decision boundary for scratch k-NN would be similar to sklearn's.