<reponame>Oren0001/IML.HUJI
from __future__ import annotations
from typing import Tuple, NoReturn
from ...base import BaseEstimator
import numpy as np
from itertools import product


class DecisionStump(BaseEstimator):
    """
    A decision stump classifier for {-1,1} labels according to the CART algorithm

    Attributes
    ----------
    self.threshold_ : float
        The threshold by which the data is split

    self.j_ : int
        The index of the feature by which to split the data

    self.sign_: int
        The label to predict for samples where the value of the j'th feature is about the threshold
    """

    def __init__(self) -> DecisionStump:
        """
        Instantiate a Decision stump classifier
        """
        super().__init__()
        self.threshold_, self.j_, self.sign_ = None, None, None
        self.threshold_err, self.j_temp = None, None

    def _fit(self, X: np.ndarray, y: np.ndarray) -> NoReturn:
        """
        fits a decision stump to the given data

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to fit an estimator for

        y : ndarray of shape (n_samples, )
            Responses of input data to fit to
        """
        thr_star = np.inf
        for sign, j in product([-1, 1], range(X.shape[1])):
            self.j_temp = j
            thr, thr_err = self._find_threshold(X, y, sign)
            if thr < thr_star:
                self.sign_, self.j_ = sign, j
                self.threshold_, self.threshold_err = thr, thr_err
                thr_star = thr

    def _predict(self, X: np.ndarray) -> np.ndarray:
        """
        Predict responses for given samples using fitted estimator

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to predict responses for

        y : ndarray of shape (n_samples, )
            Responses of input data to fit to

        Returns
        -------
        responses : ndarray of shape (n_samples, )
            Predicted responses of given samples

        Notes
        -----
        Feature values strictly below threshold are predicted as `-sign` whereas values which equal
        to or above the threshold are predicted as `sign`
        """
        return self.sign_ * ((X[:, self.j_] >= self.threshold_err) * 2 - 1)

    def _find_threshold(self, values: np.ndarray, labels: np.ndarray, sign: int) -> Tuple[
        float, float]:
        """
        Given a feature vector and labels, find a threshold by which to perform a split
        The threshold is found according to the value minimizing the misclassification
        error along this feature

        Parameters
        ----------
        values: ndarray of shape (n_samples,)
            A feature vector to find a splitting threshold for

        labels: ndarray of shape (n_samples,)
            The labels to compare against

        sign: int
            Predicted label assigned to values equal to or above threshold

        Returns
        -------
        thr: float
            Threshold by which to perform split

        thr_err: float between 0 and 1
            Misclassificaiton error of returned threshold

        Notes
        -----
        For every tested threshold, values strictly below threshold are predicted as `-sign` whereas values
        which equal to or above the threshold are predicted as `sign`
        """
        sorted_args = np.argsort(values[:, self.j_temp])
        X, y = values[sorted_args], labels[sorted_args]
        thr_errors = np.concatenate([[-np.inf],
                                     (X[1:, self.j_temp] + X[:-1, self.j_temp]) / 2,
                                     [np.inf]])
        min_loss = np.sum(y == sign)
        losses = np.append(min_loss, min_loss - np.cumsum(y * sign))
        return losses[np.argmin(losses)], thr_errors[np.argmin(losses)]

    def _loss(self, X: np.ndarray, y: np.ndarray) -> float:
        """
        Evaluate performance under misclassification loss function

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Test samples

        y : ndarray of shape (n_samples, )
            True labels of test samples

        Returns
        -------
        loss : float
            Performance under missclassification loss function
        """
        y_pred = self._predict(X)
        return sum(abs(y - y_pred) / 2) / y.shape[0]

from __future__ import annotations
from typing import Tuple, NoReturn
from ...base import BaseEstimator
import numpy as np
from itertools import product


class DecisionStump(BaseEstimator):
    """
    A decision stump classifier for {-1,1} labels according to the CART algorithm

    Attributes
    ----------
    self.threshold_ : float
        The threshold by which the data is split

    self.j_ : int
        The index of the feature by which to split the data

    self.sign_: int
        The label to predict for samples where the value of the j'th feature is about the threshold
    """

    def __init__(self) -> DecisionStump:
        """
        Instantiate a Decision stump classifier
        """
        super().__init__()
        self.threshold_, self.j_, self.sign_ = None, None, None
        self.threshold_err, self.j_temp = None, None

    def _fit(self, X: np.ndarray, y: np.ndarray) -> NoReturn:
        """
        fits a decision stump to the given data

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to fit an estimator for

        y : ndarray of shape (n_samples, )
            Responses of input data to fit to
        """
        thr_star = np.inf
        for sign, j in product([-1, 1], range(X.shape[1])):
            self.j_temp = j
            thr, thr_err = self._find_threshold(X, y, sign)
            if thr < thr_star:
                self.sign_, self.j_ = sign, j
                self.threshold_, self.threshold_err = thr, thr_err
                thr_star = thr

    def _predict(self, X: np.ndarray) -> np.ndarray:
        """
        Predict responses for given samples using fitted estimator

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Input data to predict responses for

        y : ndarray of shape (n_samples, )
            Responses of input data to fit to

        Returns
        -------
        responses : ndarray of shape (n_samples, )
            Predicted responses of given samples

        Notes
        -----
        Feature values strictly below threshold are predicted as `-sign` whereas values which equal
        to or above the threshold are predicted as `sign`
        """
        return self.sign_ * ((X[:, self.j_] >= self.threshold_err) * 2 - 1)

    def _find_threshold(self, values: np.ndarray, labels: np.ndarray, sign: int) -> Tuple[
        float, float]:
        """
        Given a feature vector and labels, find a threshold by which to perform a split
        The threshold is found according to the value minimizing the misclassification
        error along this feature

        Parameters
        ----------
        values: ndarray of shape (n_samples,)
            A feature vector to find a splitting threshold for

        labels: ndarray of shape (n_samples,)
            The labels to compare against

        sign: int
            Predicted label assigned to values equal to or above threshold

        Returns
        -------
        thr: float
            Threshold by which to perform split

        thr_err: float between 0 and 1
            Misclassificaiton error of returned threshold

        Notes
        -----
        For every tested threshold, values strictly below threshold are predicted as `-sign` whereas values
        which equal to or above the threshold are predicted as `sign`
        """
        sorted_args = np.argsort(values[:, self.j_temp])
        X, y = values[sorted_args], labels[sorted_args]
        thr_errors = np.concatenate([[-np.inf],
                                     (X[1:, self.j_temp] + X[:-1, self.j_temp]) / 2,
                                     [np.inf]])
        min_loss = np.sum(y == sign)
        losses = np.append(min_loss, min_loss - np.cumsum(y * sign))
        return losses[np.argmin(losses)], thr_errors[np.argmin(losses)]

    def _loss(self, X: np.ndarray, y: np.ndarray) -> float:
        """
        Evaluate performance under misclassification loss function

        Parameters
        ----------
        X : ndarray of shape (n_samples, n_features)
            Test samples

        y : ndarray of shape (n_samples, )
            True labels of test samples

        Returns
        -------
        loss : float
            Performance under missclassification loss function
        """
        y_pred = self._predict(X)
        return sum(abs(y - y_pred) / 2) / y.shape[0]
A decision stump classifier for {-1,1} labels according to the CART algorithm      Attributes     ----------     self.threshold_ : float         The threshold by which the data is split      self.j_ : int         The index of the feature by which to split the data      self.sign_: int         The label to predict for samples where the value of the j'th feature is about the threshold Instantiate a Decision stump classifier fits a decision stump to the given data          Parameters         ----------         X : ndarray of shape (n_samples, n_features)             Input data to fit an estimator for          y : ndarray of shape (n_samples, )             Responses of input data to fit to Predict responses for given samples using fitted estimator          Parameters         ----------         X : ndarray of shape (n_samples, n_features)             Input data to predict responses for          y : ndarray of shape (n_samples, )             Responses of input data to fit to          Returns         -------         responses : ndarray of shape (n_samples, )             Predicted responses of given samples          Notes         -----         Feature values strictly below threshold are predicted as `-sign` whereas values which equal         to or above the threshold are predicted as `sign` Given a feature vector and labels, find a threshold by which to perform a split         The threshold is found according to the value minimizing the misclassification         error along this feature          Parameters         ----------         values: ndarray of shape (n_samples,)             A feature vector to find a splitting threshold for          labels: ndarray of shape (n_samples,)             The labels to compare against          sign: int             Predicted label assigned to values equal to or above threshold          Returns         -------         thr: float             Threshold by which to perform split          thr_err: float between 0 and 1             Misclassificaiton error of returned threshold          Notes         -----         For every tested threshold, values strictly below threshold are predicted as `-sign` whereas values         which equal to or above the threshold are predicted as `sign` Evaluate performance under misclassification loss function          Parameters         ----------         X : ndarray of shape (n_samples, n_features)             Test samples          y : ndarray of shape (n_samples, )             True labels of test samples          Returns         -------         loss : float             Performance under missclassification loss function