import numpy as np
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import r2_score

class LinearRegression:
    def __init__(self, learning_rate=0.01, n_iterations=1000):
        """
        Initialize Linear Regression model
        
        Parameters:
        learning_rate -- step size for parameter updates (default 0.01)
        n_iterations -- number of training iterations (default 1000)
        """
        self.learning_rate = learning_rate
        self.n_iterations = n_iterations
        self.weights = None  # weight parameters
        self.bias = None     # bias parameter
        self.loss_history = []  # to record loss at each iteration
    
    def fit(self, X, y):
        """
        Train the linear regression model
        
        Parameters:
        X -- feature matrix of shape (n_samples, n_features)
        y -- target vector of shape (n_samples,)
        """
        n_samples, n_features = X.shape
        
        # 1. Initialize parameters
        self.weights = np.zeros(n_features)  # initialize weights to 0
        self.bias = 0                       # initialize bias to 0
        
        # 2. Gradient descent iterations
        for _ in range(self.n_iterations):
            # Forward pass: compute predictions
            y_pred = np.dot(X, self.weights) + self.bias
            
            # Compute loss (mean squared error)
            loss = (1 / (2 * n_samples)) * np.sum((y_pred - y) ** 2)
            self.loss_history.append(loss)
            
            # Compute gradients
            dw = (1 / n_samples) * np.dot(X.T, (y_pred - y))  # weight gradients
            db = (1 / n_samples) * np.sum(y_pred - y)         # bias gradient
            
            # Update parameters
            self.weights -= self.learning_rate * dw
            self.bias -= self.learning_rate * db
    
    def predict(self, X):
        """
        Make predictions using the trained model
        
        Parameters:
        X -- feature matrix of shape (n_samples, n_features)
        
        Returns:
        y_pred -- predicted values of shape (n_samples,)
        """
        return np.dot(X, self.weights) + self.bias

from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score

# 加载数据集
iris = datasets.load_iris()
X = iris.data
y = iris.target

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 创建SVM分类器
clf = SVC(kernel='linear')

# 训练模型
clf.fit(X_train, y_train)

# 预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy}")

import numpy as np
from collections import Counter
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

class KNN:
    """
    K-Nearest Neighbors classifier manual implementation
    
    Parameters:
        k: int, optional (default=5), number of nearest neighbors to consider
    """
    
    def __init__(self, k=5):
        self.k = k
    
    def fit(self, X, y):
        """
        Train the KNN model (actually just stores the data as KNN is a lazy learner)
        
        Parameters:
            X: Training feature data, array of shape [n_samples, n_features]
            y: Training target values, array of shape [n_samples]
        """
        # Standardize data (improves KNN performance)
        self.scaler = StandardScaler()
        self.X_train = self.scaler.fit_transform(X)
        self.y_train = y
        
    def predict(self, X):
        """
        Make predictions for test data
        
        Parameters:
            X: Test feature data, array of shape [n_samples, n_features]
            
        Returns:
            Predictions, array of shape [n_samples]
        """
        # Standardize test data (using mean and variance from training data)
        X = self.scaler.transform(X)
        # Initialize prediction array
        predictions = np.zeros(X.shape[0], dtype=self.y_train.dtype)
        
        # Make prediction for each test sample
        for i, x in enumerate(X):
            # 1. Calculate distances between current test sample and all training samples
            distances = self._compute_distances(x)
            
            # 2. Get indices of k nearest neighbors
            k_indices = np.argpartition(distances, self.k)[:self.k]
            
            # 3. Get labels of these k neighbors
            k_nearest_labels = self.y_train[k_indices]
            
            # 4. Vote for prediction (take most common class)
            most_common = Counter(k_nearest_labels).most_common(1)
            predictions[i] = most_common[0][0]
            
        return predictions
    
    def _compute_distances(self, x):
        """
        Calculate distances between one sample and all training samples (Euclidean distance)
        
        Parameters:
            x: Single sample point, array of shape [n_features]
            
        Returns:
            Array of distances, array of shape [n_train_samples]
        """
        # Euclidean distance calculation: sqrt(sum((x1 - x2)^2))
        distances = np.sqrt(np.sum((self.X_train - x) ** 2, axis=1))
        return distances

import numpy as np
from sklearn.preprocessing import StandardScaler

class LogisticRegression:
    """
    A manually implemented Logistic Regression class
    """
    
    def __init__(self, learning_rate=0.01, n_iterations=1000, fit_intercept=True, verbose=False):
        """
        Initialize the Logistic Regression model
        
        Parameters:
        learning_rate -- Step size for gradient descent (default: 0.01)
        n_iterations -- Number of iterations for gradient descent (default: 1000)
        fit_intercept -- Whether to add an intercept term (default: True)
        verbose -- Whether to print training progress (default: False)
        """
        self.learning_rate = learning_rate
        self.n_iterations = n_iterations
        self.fit_intercept = fit_intercept
        self.verbose = verbose
        self.weights = None
        self.scaler = StandardScaler()  # For feature standardization
    
    def __add_intercept(self, X):
        """
        Add intercept term (column of 1's) to feature matrix
        
        Parameters:
        X -- Input feature matrix (n_samples, n_features)
        
        Returns:
        Feature matrix with intercept term added (n_samples, n_features + 1)
        """
        intercept = np.ones((X.shape[0], 1))
        return np.concatenate((intercept, X), axis=1)
    
    def __sigmoid(self, z):
        """
        Sigmoid activation function mapping input to (0,1) interval
        
        Parameters:
        z -- Linear combination of inputs and weights
        
        Returns:
        Probability after sigmoid transformation
        """
        return 1 / (1 + np.exp(-z))
    
    def __loss(self, h, y):
        """
        Compute the logistic loss (log loss/cross-entropy loss)
        
        Parameters:
        h -- Predicted probabilities (n_samples,)
        y -- True labels (n_samples,)
        
        Returns:
        Current loss value
        """
        return (-y * np.log(h) - (1 - y) * np.log(1 - h)).mean()
    
    def fit(self, X, y):
        """
        Train the logistic regression model
        
        Parameters:
        X -- Training feature matrix (n_samples, n_features)
        y -- Training label vector (n_samples,)
        """
        # Standardize features
        X = self.scaler.fit_transform(X)
        
        # Add intercept term
        if self.fit_intercept:
            X = self.__add_intercept(X)
        
        # Initialize weights (zeros)
        self.weights = np.zeros(X.shape[1])
        
        # Gradient descent
        for i in range(self.n_iterations):
            # Linear combination of inputs and weights
            z = np.dot(X, self.weights)
            
            # Apply sigmoid to get probabilities
            h = self.__sigmoid(z)
            
            # Compute gradient (X.T * (h - y)) / n_samples
            gradient = np.dot(X.T, (h - y)) / y.size
            
            # Update weights
            self.weights -= self.learning_rate * gradient
            
            # Print training progress if verbose
            if self.verbose and i % 100 == 0:
                loss = self.__loss(h, y)
                print(f'Iteration {i}, Loss: {loss}')
    
    def predict_prob(self, X):
        """
        Predict probability of positive class
        
        Parameters:
        X -- Input feature matrix (n_samples, n_features)
        
        Returns:
        Probability of positive class (n_samples,)
        """
        # Standardize features
        X = self.scaler.transform(X)
        
        # Add intercept term
        if self.fit_intercept:
            X = self.__add_intercept(X)
        
        # Compute probabilities
        return self.__sigmoid(np.dot(X, self.weights))
    
    def predict(self, X, threshold=0.5):
        """
        Predict class labels
        
        Parameters:
        X -- Input feature matrix (n_samples, n_features)
        threshold -- Classification threshold (default: 0.5)
        
        Returns:
        Predicted class labels (n_samples,)
        """
        return self.predict_prob(X) >= threshold

import numpy as np
from math import log
from collections import Counter

class DecisionTree:
    """
    A decision tree classifier using ID3 algorithm.
    
    Attributes:
        tree (dict): The constructed decision tree.
        max_depth (int): Maximum depth of the tree.
        min_samples_split (int): Minimum number of samples required to split a node.
    """
    
    def __init__(self, max_depth=None, min_samples_split=2):
        """
        Initialize the decision tree.
        
        Args:
            max_depth (int, optional): Maximum depth of the tree. Defaults to None.
            min_samples_split (int, optional): Minimum samples to split. Defaults to 2.
        """
        self.tree = {}
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
    
    def fit(self, X, y, depth=0):
        """
        Build the decision tree from training data.
        
        Args:
            X (numpy.ndarray): Feature matrix of shape (n_samples, n_features).
            y (numpy.ndarray): Target vector of shape (n_samples,).
            depth (int, optional): Current depth of the tree. Defaults to 0.
            
        Returns:
            dict: The constructed decision tree.
        """
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))
        
        # Stopping criteria
        if (n_classes == 1 or 
            n_samples < self.min_samples_split or 
            (self.max_depth is not None and depth == self.max_depth)):
            return self._most_common_label(y)
        
        # Find the best split
        best_feature, best_threshold = self._best_split(X, y, n_features)
        
        # If no split improves purity, return leaf node
        if best_feature is None:
            return self._most_common_label(y)
        
        # Split the dataset
        left_indices = X[:, best_feature] <= best_threshold
        right_indices = X[:, best_feature] > best_threshold
        
        # Recursively build left and right subtrees
        left_subtree = self.fit(X[left_indices], y[left_indices], depth+1)
        right_subtree = self.fit(X[right_indices], y[right_indices], depth+1)
        
        # Return the decision node
        return {
            'feature_index': best_feature,
            'threshold': best_threshold,
            'left': left_subtree,
            'right': right_subtree
        }
    
    def _best_split(self, X, y, n_features):
        """
        Find the best feature and threshold to split on.
        
        Args:
            X (numpy.ndarray): Feature matrix.
            y (numpy.ndarray): Target vector.
            n_features (int): Number of features.
            
        Returns:
            tuple: (best_feature_index, best_threshold)
        """
        best_gain = -1
        best_feature, best_threshold = None, None
        
        for feature_idx in range(n_features):
            thresholds = np.unique(X[:, feature_idx])
            for threshold in thresholds:
                gain = self._information_gain(X, y, feature_idx, threshold)
                
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature_idx
                    best_threshold = threshold
        
        return best_feature, best_threshold
    
    def _information_gain(self, X, y, feature_idx, threshold):
        """
        Calculate information gain from splitting on a feature and threshold.
        
        Args:
            X (numpy.ndarray): Feature matrix.
            y (numpy.ndarray): Target vector.
            feature_idx (int): Index of feature to split on.
            threshold (float): Threshold value for the split.
            
        Returns:
            float: Information gain.
        """
        # Parent entropy
        parent_entropy = self._entropy(y)
        
        # Split data
        left_indices = X[:, feature_idx] <= threshold
        right_indices = X[:, feature_idx] > threshold
        
        if len(y[left_indices]) == 0 or len(y[right_indices]) == 0:
            return 0
        
        # Calculate weighted child entropy
        n = len(y)
        n_left, n_right = len(y[left_indices]), len(y[right_indices])
        child_entropy = (n_left/n) * self._entropy(y[left_indices]) + \
                        (n_right/n) * self._entropy(y[right_indices])
        
        # Information gain is difference in entropy
        return parent_entropy - child_entropy
    
    def _entropy(self, y):
        """
        Calculate entropy of a target vector.
        
        Args:
            y (numpy.ndarray): Target vector.
            
        Returns:
            float: Entropy value.
        """
        counts = np.bincount(y)
        probabilities = counts / len(y)
        return -np.sum([p * np.log2(p) for p in probabilities if p > 0])
    
    def _most_common_label(self, y):
        """
        Find the most common label in a target vector.
        
        Args:
            y (numpy.ndarray): Target vector.
            
        Returns:
            int: The most common class label.
        """
        counter = Counter(y)
        return counter.most_common(1)[0][0]
    
    def predict(self, X):
        """
        Predict class labels for samples in X.
        
        Args:
            X (numpy.ndarray): Feature matrix of shape (n_samples, n_features).
            
        Returns:
            numpy.ndarray: Predicted class labels.
        """
        return np.array([self._predict_single(x, self.tree) for x in X])
    
    def _predict_single(self, x, tree):
        """
        Predict class for a single sample by traversing the tree.
        
        Args:
            x (numpy.ndarray): Single sample features.
            tree (dict): Decision tree or subtree.
            
        Returns:
            int: Predicted class label.
        """
        if not isinstance(tree, dict):
            return tree
        
        feature_idx = tree['feature_index']
        threshold = tree['threshold']
        
        if x[feature_idx] <= threshold:
            return self._predict_single(x, tree['left'])
        else:
            return self._predict_single(x, tree['right'])

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

class KMeans:
    """
    K-means clustering algorithm implementation
    
    Parameters:
    -----------
    n_clusters: int
        Number of clusters to form
    max_iter: int
        Maximum number of iterations
    tol: float
        Tolerance to declare convergence (if centroids move less than tol)
    random_state: int
        Seed for random initialization
    """
    
    def __init__(self, n_clusters=3, max_iter=100, tol=1e-4, random_state=42):
        self.n_clusters = n_clusters
        self.max_iter = max_iter
        self.tol = tol
        self.random_state = random_state
        self.centroids = None
        self.labels = None
        
    def _initialize_centroids(self, X):
        """Randomly initialize centroids by selecting K points from dataset"""
        np.random.seed(self.random_state)
        random_idx = np.random.permutation(X.shape[0])
        centroids = X[random_idx[:self.n_clusters]]
        return centroids
    
    def _compute_distances(self, X, centroids):
        """
        Compute distances between each data point and each centroid
        
        Parameters:
        -----------
        X: ndarray of shape (n_samples, n_features)
            Input data
        centroids: ndarray of shape (n_clusters, n_features)
            Current centroids
            
        Returns:
        --------
        distances: ndarray of shape (n_samples, n_clusters)
            Distance from each point to each centroid
        """
        distances = np.zeros((X.shape[0], self.n_clusters))
        for k in range(self.n_clusters):
            # Compute Euclidean distance (L2 norm)
            distances[:, k] = np.linalg.norm(X - centroids[k], axis=1)
        return distances
    
    def _assign_clusters(self, distances):
        """
        Assign each data point to the nearest centroid
        
        Parameters:
        -----------
        distances: ndarray of shape (n_samples, n_clusters)
            Distance from each point to each centroid
            
        Returns:
        --------
        labels: ndarray of shape (n_samples,)
            Cluster index for each data point
        """
        return np.argmin(distances, axis=1)
    
    def _update_centroids(self, X, labels):
        """
        Update centroids as the mean of data points in each cluster
        
        Parameters:
        -----------
        X: ndarray of shape (n_samples, n_features)
            Input data
        labels: ndarray of shape (n_samples,)
            Cluster assignments
            
        Returns:
        --------
        centroids: ndarray of shape (n_clusters, n_features)
            New centroids
        """
        centroids = np.zeros((self.n_clusters, X.shape[1]))
        for k in range(self.n_clusters):
            # Compute mean of points assigned to cluster k
            centroids[k] = np.mean(X[labels == k], axis=0)
        return centroids
    
    def fit(self, X):
        """
        Fit K-means algorithm to the input data
        
        Parameters:
        -----------
        X: ndarray of shape (n_samples, n_features)
            Input data
        """
        # Initialize centroids
        self.centroids = self._initialize_centroids(X)
        
        for i in range(self.max_iter):
            # Compute distances from points to centroids
            distances = self._compute_distances(X, self.centroids)
            
            # Assign points to nearest centroid
            self.labels = self._assign_clusters(distances)
            
            # Store current centroids for convergence check
            old_centroids = self.centroids.copy()
            
            # Update centroids
            self.centroids = self._update_centroids(X, self.labels)
            
            # Check for convergence (if centroids don't move much)
            centroid_shift = np.linalg.norm(self.centroids - old_centroids)
            if centroid_shift < self.tol:
                print(f"Converged at iteration {i}")
                break
    
    def predict(self, X):
        """
        Predict cluster labels for new data
        
        Parameters:
        -----------
        X: ndarray of shape (n_samples, n_features)
            New data to predict
            
        Returns:
        --------
        labels: ndarray of shape (n_samples,)
            Predicted cluster labels
        """
        distances = self._compute_distances(X, self.centroids)
        return self._assign_clusters(distances)

import numpy as np
from collections import Counter
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

class RandomForest:
    """
    A simple implementation of Random Forest classifier from scratch.
    
    Parameters:
    -----------
    n_estimators: int
        The number of decision trees in the forest.
    max_features: int or float
        The number of features to consider when looking for the best split.
        If int, then consider max_features features at each split.
        If float, then max_features is a fraction and int(max_features * n_features) features are considered.
    max_depth: int
        The maximum depth of the tree.
    min_samples_split: int
        The minimum number of samples required to split an internal node.
    bootstrap: bool
        Whether bootstrap samples are used when building trees.
    random_state: int
        Random seed for reproducibility.
    """
    
    def __init__(self, n_estimators=100, max_features='sqrt', max_depth=None, 
                 min_samples_split=2, bootstrap=True, random_state=None):
        self.n_estimators = n_estimators
        self.max_features = max_features
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.bootstrap = bootstrap
        self.random_state = random_state
        self.trees = []
        self.feature_indices = []  # Stores feature indices used in each tree
        
        if random_state is not None:
            np.random.seed(random_state)
    
    def _bootstrap_sample(self, X, y):
        """
        Create bootstrap sample from the training data.
        
        Parameters:
        -----------
        X: array-like
            Training features.
        y: array-like
            Training labels.
            
        Returns:
        --------
        X_sample: array-like
            Bootstrap sample of features.
        y_sample: array-like
            Bootstrap sample of labels.
        oob_indices: array-like
            Indices of out-of-bag samples.
        """
        n_samples = X.shape[0]
        indices = np.random.choice(n_samples, size=n_samples, replace=True)
        oob_indices = np.array([i for i in range(n_samples) if i not in indices])
        
        X_sample = X[indices]
        y_sample = y[indices]
        
        return X_sample, y_sample, oob_indices
    
    def _get_feature_subset(self, n_features):
        """
        Get random subset of features for a tree.
        
        Parameters:
        -----------
        n_features: int
            Total number of features.
            
        Returns:
        --------
        feature_indices: array-like
            Indices of selected features.
        """
        if isinstance(self.max_features, int):
            m = min(self.max_features, n_features)
        elif isinstance(self.max_features, float):
            m = int(self.max_features * n_features)
        elif self.max_features == 'sqrt':
            m = int(np.sqrt(n_features))
        else:
            m = n_features
            
        return np.random.choice(n_features, m, replace=False)
    
    def fit(self, X, y):
        """
        Build a forest of decision trees from the training set (X, y).
        
        Parameters:
        -----------
        X: array-like
            Training features.
        y: array-like
            Training labels.
        """
        n_samples, n_features = X.shape
        self.classes_ = np.unique(y)
        self.trees = []
        self.feature_indices = []
        
        for _ in range(self.n_estimators):
            # Create bootstrap sample
            if self.bootstrap:
                X_sample, y_sample, _ = self._bootstrap_sample(X, y)
            else:
                X_sample, y_sample = X, y
                
            # Get random feature subset
            feature_idx = self._get_feature_subset(n_features)
            X_sample_subset = X_sample[:, feature_idx]
            
            # Grow decision tree
            tree = DecisionTreeClassifier(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features='auto'  # Use all features in the subset (already subsetted)
            )
            tree.fit(X_sample_subset, y_sample)
            
            # Save tree and feature indices
            self.trees.append(tree)
            self.feature_indices.append(feature_idx)
    
    def predict(self, X):
        """
        Predict class for X.
        
        Parameters:
        -----------
        X: array-like
            Input features.
            
        Returns:
        --------
        predictions: array-like
            Predicted class labels.
        """
        # Get predictions from all trees
        tree_preds = np.array([tree.predict(X[:, features]) 
                              for tree, features in zip(self.trees, self.feature_indices)])
        
        # Majority voting
        predictions = np.array([Counter(tree_preds[:, i]).most_common(1)[0][0] 
                              for i in range(X.shape[0])])
        return predictions
    
    def predict_proba(self, X):
        """
        Predict class probabilities for X.
        
        Parameters:
        -----------
        X: array-like
            Input features.
            
        Returns:
        --------
        proba: array-like
            Class probabilities of the input samples.
        """
        # Get predictions from all trees
        tree_preds = np.array([tree.predict(X[:, features]) 
                              for tree, features in zip(self.trees, self.feature_indices)])
        
        # Calculate probabilities
        proba = np.zeros((X.shape[0], len(self.classes_)))
        for i in range(X.shape[0]):
            counts = np.bincount(tree_preds[:, i], minlength=len(self.classes_))
            proba[i, :] = counts / self.n_estimators
            
        return proba

import numpy as np

class GaussianNaiveBayes:
    """
    A Gaussian Naive Bayes classifier implementation.
    Assumes features follow normal distribution and are conditionally independent given the class.
    """
    
    def fit(self, X, y):
        """
        Train the Gaussian Naive Bayes model with training data.
        
        Parameters:
        X : numpy array, shape (n_samples, n_features)
            Training feature vectors
        y : numpy array, shape (n_samples,)
            Target class labels
        """
        # Get unique class labels from training data
        self.classes = np.unique(y)
        
        # Initialize dictionaries to store:
        self.mean = {}      # Mean of each feature per class
        self.var = {}       # Variance of each feature per class
        self.priors = {}    # Prior probability of each class
        
        # Calculate statistics for each class
        for c in self.classes:
            # Get samples belonging to current class
            X_c = X[y == c]
            
            # Calculate mean and variance of each feature for this class
            self.mean[c] = X_c.mean(axis=0)  # Mean along each feature column
            self.var[c] = X_c.var(axis=0)   # Variance along each feature column
            
            # Calculate prior probability: P(class=c)
            self.priors[c] = X_c.shape[0] / X.shape[0]
    
    def predict(self, X):
        """
        Make predictions for new samples using the trained model.
        
        Parameters:
        X : numpy array, shape (n_samples, n_features)
            Test feature vectors to predict
            
        Returns:
        predictions : list
            Predicted class labels for each test sample
        """
        predictions = []
        
        # Process each test sample individually
        for x in X:
            posteriors = []
            
            # Calculate posterior probability for each class
            for c in self.classes:
                # Calculate likelihood using Gaussian PDF (simplified computation):
                # P(x|class=c) = product of P(x_i|class=c) for all features
                exponent = -((x - self.mean[c]) ** 2) / (2 * self.var[c])
                likelihood = np.exp(exponent) / np.sqrt(2 * np.pi * self.var[c])
                
                # Calculate posterior: P(class=c|x) ∝ P(x|class=c) * P(class=c)
                posterior = np.prod(likelihood) * self.priors[c]
                posteriors.append(posterior)
            
            # Select class with highest posterior probability
            predicted_class = self.classes[np.argmax(posteriors)]
            predictions.append(predicted_class)
            
        return predictions