{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "a2ef4347-3c2e-5b6c-11a8-6f8767806f46"
      },
      "source": [
        "## Introduction ##\n",
        "\n",
        "\n",
        "Extending from Olga's Minimum Distance Classifier (https://www.kaggle.com/olhacher/digit-recognizer/minimum-distance-classifier) ***to use a within cluster sum of square metric as a guide to determine the optimal number of clusters for each label.***\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "47d2e746-4cab-7278-7160-252796db296f"
      },
      "outputs": [],
      "source": [
        "#Loading Data (no changes from Olga's Minimum Distance Classifier)\n",
        "train <- read.csv(\"../input/train.csv\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "5d13cc7d-18e8-bc0c-5f77-c4e4fcdd34e4"
      },
      "source": [
        "## Splitting Data into Train and Test Sets ##\n",
        "(no changes from Olga's Minimum Distance Classifier )\n",
        "---------------------------------------\n",
        "\n",
        "1) about 25% of observations goes to test set; \n",
        "2) train and test sets have to be balanced - have about equal amount of observations from all classes."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "08768ae7-4a60-bbce-2142-041960b78866"
      },
      "outputs": [],
      "source": [
        "#(no changes from Olga's Minimum Distance Classifier)\n",
        "set.seed(25)\n",
        "intest <- sample(1:42000,10000)\n",
        "X_train <- train[-intest,-1]\n",
        "Y_train <- train[-intest,1]\n",
        "X_test <- train[intest,-1]\n",
        "Y_test <- train[intest,1]\n",
        "\n",
        "table(Y_train)\n",
        "table(Y_test)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "a4403ca5-1294-630e-815a-02fa00146fa0"
      },
      "source": [
        "## Decreasing Size of Train Set ##\n",
        "***(Enhancements in bold-italics)***\n",
        "\n",
        "----------\n",
        "Determine up to a maximum of ***50 of the most distinct digits in every class using the minimum of the sum of the distance within clusters for each class.*** \n",
        "\n",
        "To build a new train set I am going to: 1) use K-Mean clustering algorithm; 2) *** with up to 500 class centers*** (10 digits * ***up to 50 clusters per digit***) as observations for the train set. Euclidean distance is distance metric and simple average of all observations in clusters as cluster centers.\n",
        "\n",
        "***Optimization reduced the number of class centers from 500 to 498 (not a great difference here, but might be useful for large datasets)***\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "d4af1c65-c789-8ff3-f5db-2abee76d37f2"
      },
      "outputs": [],
      "source": [
        "raw_train_set <- train[-intest,]\n",
        "final_train_set <- NULL\n",
        "\n",
        "for (i in 0:9)\n",
        "{\n",
        "    digit <- raw_train_set[raw_train_set$label==i,-1]\n",
        "    set.seed(222)\n",
        "    # addition of automatic optimal cluster size determination (start)\n",
        "    mydata=digit\n",
        "    wss=c()\n",
        "    wss[1:50] <- -1\n",
        "      for (j in 40:50) wss[j] <- sum(kmeans(mydata,\n",
        "                                           centers=j)$withinss)\n",
        "    pos=which(wss>0)\n",
        "    print(wss)\n",
        "    if(length(pos)>0)\n",
        "    {\n",
        "         optim_clus=min(which(wss==min(wss[pos])))     \n",
        "    }else{\n",
        "         optim_clus=50\n",
        "    }\n",
        "   \t                                           \n",
        "    cluster <- kmeans(x = digit,centers =optim_clus , iter.max = 20)\n",
        "    new_data <- cbind(rep(i,optim_clus),cluster$centers)\n",
        "     # addition of automatic optimal cluster size determination (end)      \n",
        "    final_train_set<- rbind(final_train_set,new_data)\n",
        "}\n",
        "final_train_set<-as.data.frame(final_train_set)\n",
        "\n",
        "X_train <- final_train_set[,-1]\n",
        "Y_train <- final_train_set[,1]\n",
        "table (Y_train)\n",
        "\n",
        "rm(digit,cluster,new_data,i,raw_train_set,final_train_set)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "ae5a9541-87a8-bf97-0439-f10bb1b71494"
      },
      "source": [
        "## Predictions ##\n",
        "***(no changes from Olga's Minimum Distance Classifier except train set has now 498 columns as compared to the previous fixed value of 500 columns, 0.4% reduction in training size)***\n",
        "\n",
        "----------\n",
        "Time for predictions! First part of the script calculates distance matrix **distances**, which has 10,000 rows (10,000 observations in test set) and ***498 columns*** (distances to all observations in train set). The second part finds mimimum distance in the row and ties it to observation in train set (both cluster number and digit type); output is a matrix **predictions**.\n",
        "\n",
        "(Actually, my script does not calculate euclidean distances, it calculates squared euclidean distances. As I don't need actual distances, I decided not to take square roots because it increases number of caclulations. I need just comparance of distances, and it is known that if x^2 > y^2, then x > y for all positive numbers.)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "ea09680f-7cb8-1911-9f7d-fbf5fb354493"
      },
      "outputs": [],
      "source": [
        "#Calculating distances (no changes from Olga's Minimum Distance Classifier)\n",
        "distances <- NULL\n",
        "X_train <- as.matrix(X_train)\n",
        "X_test <- as.matrix(X_test)\n",
        "m <- dim(X_train)[1]\n",
        "n <- dim(X_test)[1]\n",
        "\n",
        "for (j in 1:n)\n",
        "{\n",
        "    dist <- rowSums((X_train - t(replicate(m, X_test[j,])))^2)\n",
        "    distances<-cbind(distances,dist)\n",
        "}\n",
        "distances <- (t(distances))\n",
        "\n",
        "#Predicting (no changes from Olga's Minimum Distance Classifier)\n",
        "rows<-NULL\n",
        "for (i in 1:n)\n",
        "    rows <- c(rows, which.min(distances[i,])[[1]])\n",
        "\n",
        "predictions <- data.frame(predicted = Y_train[rows], actual = Y_test, cluster = rows)\n",
        "rm(dist,j,m,n,i,rows)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "7bf897f3-9234-d9dd-1029-e12f1173d2c7"
      },
      "source": [
        "## Model Valuation ##\n",
        "\n",
        "\n",
        "----------\n",
        "Model accuracy is still 94.9%"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "d698fe3b-4604-57f8-f051-08772efd4a10"
      },
      "outputs": [],
      "source": [
        "#function (no changes from Olga's Minimum Distance Classifier)\n",
        "accuracy <- function (pred,actual)\n",
        "{\n",
        "    conf_matrix <- table(predictions = pred, actual = actual)\n",
        "    sum <- 0\n",
        "    for (j in 1:10)\n",
        "        for (i in 1:10)\n",
        "            if (j == i)\n",
        "                sum<-sum+conf_matrix[i,j]\n",
        "    return(list(conf_matrix,sum/length(pred)))\n",
        "}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "_cell_guid": "fce5c1b5-194d-7418-552f-3c35897e8876"
      },
      "outputs": [],
      "source": [
        "print(accuracy(predictions$predicted,predictions$actual))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "_cell_guid": "11587533-5911-e123-16a3-2b52f4c78757"
      },
      "source": [
        "## Conclusion ##\n",
        "\n",
        "\n",
        "----------\n",
        "Just as a proof of concept, automatic parameter optimization is easy. It can reduce training size while maintaining prediction accuracy for a minimum distance classifier.\n",
        "\n",
        "Still 94.9% accuracy! \n"
      ]
    }
  ],
  "metadata": {
    "_change_revision": 0,
    "_is_fork": false,
    "kernelspec": {
      "display_name": "R",
      "language": "R",
      "name": "ir"
    },
    "language_info": {
      "codemirror_mode": "r",
      "file_extension": ".r",
      "mimetype": "text/x-r-source",
      "name": "R",
      "pygments_lexer": "r",
      "version": "3.3.2"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}