cost_sensitive_learning_genetic.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from sklearn.tree import DecisionTreeClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Genetic():\n",
    "    \"\"\"\n",
    "    Parameters:\n",
    "    -----------\n",
    "    population_size: int\n",
    "    mutation_prob: float\n",
    "    ...\n",
    "    \"\"\"\n",
    "    def __init__(self, classifier, X_train, y_train, X_test, y_test, feature_costs, feature_names, \n",
    "                     population_size, crossover_prob, mutation_prob):\n",
    "        self.classifier = classifier\n",
    "        self.X_train = X_train\n",
    "        self.y_train = y_train\n",
    "        self.X_test = X_test\n",
    "        self.y_test = y_test\n",
    "        self.feature_costs = feature_costs\n",
    "        self.feature_names = feature_names\n",
    "        self.num_features = X_train.shape[1]\n",
    "        self.population_size = population_size\n",
    "        self.crossover_prob = crossover_prob\n",
    "        self.mutation_prob = mutation_prob\n",
    "\n",
    "    def _initialize(self):\n",
    "        \"\"\" \n",
    "        Initialize population \n",
    "        \"\"\"\n",
    "        self.population = []\n",
    "        for _ in range(self.population_size):\n",
    "            individual = \"\".join(np.random.choice(['0', '1'], size=self.num_features))\n",
    "            self.population.append(individual)\n",
    "    \n",
    "    def _ones_indexes(self, individual):\n",
    "        \"\"\"\n",
    "        Return a list of indexes of '1's in individual string\n",
    "        \"\"\"\n",
    "        ones = [i for i in range(len(individual) - 1) if individual[i] == '1']\n",
    "        if individual[20] == '1':\n",
    "            if individual[18] == '0' or individual[19] == '0':\n",
    "                ones.append(20)\n",
    "        return ones\n",
    "        \n",
    "    def _fitness(self):\n",
    "        \"\"\" \n",
    "        Calculate the fitness (cost) of each individual in the population \n",
    "        \"\"\"\n",
    "        alpha = 2 # coefficient of classification error in fitness function\n",
    "        beta = 1 # coefficient of feature selection cost in fitness function\n",
    "        total_sum_feature_costs = sum(self.feature_costs)\n",
    "        population_fitness = [] # list of fitness values of all individuals\n",
    "        for individual in self.population:\n",
    "            ones_list = self._ones_indexes(individual) # which features are selected\n",
    "            if len(ones_list) > 0:\n",
    "                # limit X_train and X_test to the selected features\n",
    "                X_train = self.X_train[:, ones_list]\n",
    "                X_test = self.X_test[:, ones_list]\n",
    "                self.classifier.fit(X=X_train, y=self.y_train) \n",
    "                classification_error = 1 - self.classifier.score(X=X_test, y=self.y_test)\n",
    "                feature_selection_cost = sum(self.feature_costs[ones_list]) / total_sum_feature_costs\n",
    "                cost = (alpha * classification_error + beta * feature_selection_cost) / (alpha + beta)\n",
    "                fitness = cost\n",
    "            else: # no feature selected => max cost\n",
    "                fitness = 1\n",
    "            population_fitness.append(fitness)\n",
    "        return population_fitness\n",
    "    \n",
    "    def _mutate(self, individual):\n",
    "        \"\"\" \n",
    "        Flip one bit of individual with probability self.mutation_prob\n",
    "        \"\"\"\n",
    "        if np.random.random() < self.mutation_prob:\n",
    "            mutation_point = np.random.randint(0, len(individual))\n",
    "            individual = individual[:mutation_point] + \\\n",
    "                            str(1 - int(individual[mutation_point])) + individual[mutation_point+1:]\n",
    "        return individual\n",
    "\n",
    "    def _crossover(self, parent1, parent2):\n",
    "        \"\"\" \n",
    "        Create children from parents by single-point crossover \n",
    "        \"\"\"\n",
    "        if np.random.random() < self.crossover_prob: # consider crossover probability\n",
    "            # randomly select crossover point\n",
    "            crossover_point = np.random.randint(0, len(parent1))\n",
    "            child1 = parent1[:crossover_point] + parent2[crossover_point:]\n",
    "            child2 = parent2[:crossover_point] + parent1[crossover_point:]\n",
    "        else: # no crossover\n",
    "            child1 = parent1\n",
    "            child2 = parent2\n",
    "        return child1, child2\n",
    "\n",
    "    def run(self, max_iterations):\n",
    "        \n",
    "        self._initialize() # initialize the population\n",
    "        \n",
    "        last_fittest_individuals = [] # a list of fittest individuals, used in stopping criteria\n",
    "\n",
    "        for iteration in range(max_iterations):\n",
    "            population_fitness = self._fitness() # compute fitness of all individuals\n",
    "\n",
    "            fittest_individual = self.population[np.argmin(population_fitness)]\n",
    "            best_fitness = min(population_fitness)\n",
    "            last_fittest_individuals.append(fittest_individual)\n",
    "            \n",
    "            # stopping criteria: 3 last fittest individual remain unchanged\n",
    "            if last_fittest_individuals[-2:] == last_fittest_individuals[-3:-1]:\n",
    "                break\n",
    "\n",
    "            sum_population_fitness = sum(population_fitness) + 1\n",
    "            parent_probs = np.array([sum_population_fitness - fit for fit in population_fitness])\n",
    "            parent_probs = parent_probs / sum(parent_probs)\n",
    "\n",
    "            new_population = []\n",
    "            for i in np.arange(0, self.population_size, 2):\n",
    "                parent1, parent2 = np.random.choice(self.population, size=2, p=parent_probs, replace=True)\n",
    "                child1, child2 = self._crossover(parent1, parent2)\n",
    "                child1 = self._mutate(child1)\n",
    "                child2 = self._mutate(child2)\n",
    "                new_population += [child1, child2]\n",
    "\n",
    "            print (\"Iteration: %d, Best Fitness: %.2f, Fittest Individual: %s]\" % (iteration, best_fitness, fittest_individual))\n",
    "            self.population = new_population\n",
    "\n",
    "        self.report_results(iteration, fittest_individual)\n",
    "        return\n",
    "        \n",
    "    def report_results(self, last_iteration, fittest_individual):\n",
    "        \"\"\"\n",
    "        Print features selected by the genetic algorithm, the total cost of the selected features,\n",
    "        and the training and test set accuracies.\n",
    "        \"\"\"\n",
    "        print (\"\\nIteration: %d, Final Best Individual: '%s']\" % (last_iteration, fittest_individual))\n",
    "        ones_list = self._ones_indexes(fittest_individual) # which features are selected\n",
    "        print('\\nSelected Features:', feature_names[ones_list])\n",
    "        feature_selection_cost = sum(self.feature_costs[ones_list]) / sum(self.feature_costs)\n",
    "        print('\\nTotal cost of the selected features:', feature_selection_cost)\n",
    "        X_train = self.X_train[:, ones_list]\n",
    "        X_test = self.X_test[:, ones_list]\n",
    "        self.classifier.fit(X=X_train, y=self.y_train)\n",
    "        test_score = self.classifier.score(X=X_test, y=self.y_test)\n",
    "        print('\\nTest accuracy:', test_score)\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_data():\n",
    "    \"\"\"\n",
    "    Read train data, test data, and feature costs\n",
    "    \"\"\"\n",
    "    train = pd.read_csv('ann-train.data', delimiter=' ', header=None)\n",
    "    X_train = train.iloc[:, 0:21].values\n",
    "    y_train = train[21]\n",
    "    y_train = y_train.values.reshape(y_train.shape[0], 1)\n",
    "    \n",
    "    test = pd.read_csv('ann-test.data', delimiter=' ', header=None)\n",
    "    X_test = test.iloc[:, 0:21].values\n",
    "    y_test = test[21]\n",
    "    y_test = y_test.values.reshape(y_test.shape[0], 1)\n",
    "    \n",
    "    features = pd.read_csv('ann-thyroid.cost', delimiter='\\t+', header=None, engine='python')\n",
    "    feature_names = features[0].values\n",
    "    feature_names = np.array([name.split(':')[0] for name in feature_names])\n",
    "    feature_costs = features[1].values\n",
    "    feature_costs = np.append(feature_costs, feature_costs[-1] + feature_costs[-2])\n",
    "    \n",
    "    return X_train, y_train, X_test, y_test, feature_costs, feature_names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Iteration: 0, Best Fitness: 0.06, Fittest Individual: 011100000100001000000]\n",
      "Iteration: 1, Best Fitness: 0.07, Fittest Individual: 010100100110100000000]\n",
      "Iteration: 2, Best Fitness: 0.06, Fittest Individual: 000100001010110000000]\n",
      "Iteration: 3, Best Fitness: 0.06, Fittest Individual: 011101000000001000000]\n",
      "Iteration: 4, Best Fitness: 0.07, Fittest Individual: 010001100011101000000]\n",
      "Iteration: 5, Best Fitness: 0.06, Fittest Individual: 000000001000010000000]\n",
      "Iteration: 6, Best Fitness: 0.06, Fittest Individual: 000000001000010000000]\n",
      "Iteration: 7, Best Fitness: 0.06, Fittest Individual: 001000100001110000000]\n",
      "Iteration: 8, Best Fitness: 0.06, Fittest Individual: 100101000000001000000]\n",
      "Iteration: 9, Best Fitness: 0.06, Fittest Individual: 100101000000001000000]\n",
      "Iteration: 10, Best Fitness: 0.07, Fittest Individual: 000001010100010100000]\n",
      "Iteration: 11, Best Fitness: 0.07, Fittest Individual: 000101011000011000000]\n",
      "Iteration: 12, Best Fitness: 0.07, Fittest Individual: 011110000100100000000]\n",
      "Iteration: 13, Best Fitness: 0.06, Fittest Individual: 000001010100001000000]\n",
      "Iteration: 14, Best Fitness: 0.07, Fittest Individual: 011001001101000000000]\n",
      "Iteration: 15, Best Fitness: 0.06, Fittest Individual: 001001001101000000000]\n",
      "Iteration: 16, Best Fitness: 0.06, Fittest Individual: 000001010100001000000]\n",
      "Iteration: 17, Best Fitness: 0.06, Fittest Individual: 001001001101000000000]\n",
      "Iteration: 18, Best Fitness: 0.07, Fittest Individual: 010110000101100000000]\n",
      "Iteration: 19, Best Fitness: 0.07, Fittest Individual: 010001110001101000000]\n",
      "Iteration: 20, Best Fitness: 0.07, Fittest Individual: 110100010001100000000]\n",
      "Iteration: 21, Best Fitness: 0.07, Fittest Individual: 000010100100111000000]\n",
      "Iteration: 22, Best Fitness: 0.07, Fittest Individual: 001010011100100000000]\n",
      "Iteration: 23, Best Fitness: 0.07, Fittest Individual: 000000111100011100000]\n",
      "Iteration: 24, Best Fitness: 0.07, Fittest Individual: 001010110000101000000]\n",
      "Iteration: 25, Best Fitness: 0.07, Fittest Individual: 100000001010100000000]\n",
      "Iteration: 26, Best Fitness: 0.07, Fittest Individual: 010001000110100000000]\n",
      "Iteration: 27, Best Fitness: 0.07, Fittest Individual: 000110110000101000000]\n",
      "Iteration: 28, Best Fitness: 0.06, Fittest Individual: 000110000010100000000]\n",
      "Iteration: 29, Best Fitness: 0.06, Fittest Individual: 000110000010100000000]\n",
      "Iteration: 30, Best Fitness: 0.07, Fittest Individual: 000100110100011000000]\n",
      "Iteration: 31, Best Fitness: 0.07, Fittest Individual: 000100000101011000000]\n",
      "Iteration: 32, Best Fitness: 0.07, Fittest Individual: 000111100001101000000]\n",
      "Iteration: 33, Best Fitness: 0.08, Fittest Individual: 011001010011111000000]\n",
      "Iteration: 34, Best Fitness: 0.07, Fittest Individual: 011100010101101000000]\n",
      "Iteration: 35, Best Fitness: 0.08, Fittest Individual: 010110111001111000000]\n",
      "Iteration: 36, Best Fitness: 0.07, Fittest Individual: 010001100001111000000]\n",
      "Iteration: 37, Best Fitness: 0.06, Fittest Individual: 000001000010111000000]\n",
      "Iteration: 38, Best Fitness: 0.07, Fittest Individual: 000000101010011100000]\n",
      "Iteration: 39, Best Fitness: 0.06, Fittest Individual: 000100010010001000000]\n",
      "Iteration: 40, Best Fitness: 0.06, Fittest Individual: 000100010010001000000]\n",
      "Iteration: 41, Best Fitness: 0.07, Fittest Individual: 000110110010001000000]\n",
      "Iteration: 42, Best Fitness: 0.06, Fittest Individual: 000010010010001100000]\n",
      "Iteration: 43, Best Fitness: 0.06, Fittest Individual: 000010010010001100000]\n",
      "\n",
      "Iteration: 44, Final Best Individual: '000010010010001100000']\n",
      "\n",
      "Selected Features: ['on_antithyroid_medication' 'thyroid_surgery' 'query_hyperthyroid'\n",
      " 'hypopituitary' 'psych']\n",
      "\n",
      "Total cost of the selected features: 0.04900519455062236\n",
      "\n",
      "Test accuracy: 0.927071178529755\n"
     ]
    }
   ],
   "source": [
    "X_train, y_train, X_test, y_test, feature_costs, feature_names = read_data()\n",
    "\n",
    "clf = DecisionTreeClassifier()\n",
    "\n",
    "population_size = 500\n",
    "crossover_prob = 0.8\n",
    "mutation_prob = 0.05\n",
    "max_iterations = 500\n",
    "\n",
    "genetic = Genetic(clf, X_train, y_train, X_test, y_test, feature_costs, feature_names, \n",
    "                                            population_size, crossover_prob, mutation_prob)\n",
    "genetic.run(max_iterations=max_iterations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}