Classifying Dogs vs Cats - KNN & Decision Trees

KNN and Decision Trees

We have created two simple models using our training data in order to have a preliminary idea of what type of accuracy we are trying to improve upon. The two models we chose are KNN and Decision Tree.

KNN stands for k-nearest-neighbors and in this method, each point is classified based on its neighboring points. Meanwhile, in the Decision Tree method, the data is broken down into smaller and smaller subsets to find distinct features, while also grouping these pieces together to make a final dataset that can be classified.

MATLAB

At first, we used MATLAB to train these models using a small subset of our full-color data: 800 cat and 800 dog images. We then tested them on only 200 cat and 200 dog images. We ran the default MATLAB KNN model which only has k = 1 neighbor.

Below are two confusion matrixes for this subset of the data. As shown below, KNN had an accuracy of 53.75% and decision tree had an accuracy of 56.5% on the subset of the data.

When attempting to create models for the entire dataset (in either color or black and white) on MATLAB, we ran out of memory in addition to computations taking a long time to run. To be able to use more data, we pivoted to using Python which is much faster due to higher computational power.

Python

We focused on training and testing with greyscale images for KNN and Decision Tree models as there is not enough memory to store the full-color images. KNN and decision trees both require storing the entire training dataset which is very large. Lastly, we also experimented with the parameters for KNN using Python's faster runtime and decided that k = 5 neighbors gives us the best accuracy.

Below are confusion matrixes for the models with these new changes. Both the KNN and Decision Tree Models were trained on 10,000 cats and 10,000 dogs, and tested on 2500 cats and 2500 dogs.

KNN (5) Confusion Matrix
GRAYSCALE - 55.60% accuracy

Decision Tree Confusion Matrix
GRAYSCALE - 55.76% accuracy

As we can see above, simple models such as KNN and Decision Trees provide us with an accuracy of less than 60% .

Here is a link to our MATLAB and Python Code for the Simple KNN and Decision Tree:

Simple KNN & Decision Tree

Edge Extraction

After performing our feature extraction analysis and finding that using edges as features is better at distinguishing between cats and dogs than gray-scale pixels, we decided to pass the extracted edges into our KNN and Decision Tree Models.

Here is a link to our code:

KNN&DT-Edge

KNN (5) with Edges Confusion Matrix

GRAYSCALE - 61.72% accuracy

Decision Tree with Edges Confusion Matrix

GRAYSCALE - 55.86% accuracy

Above we have the confusion matrixes for the KNN and Decision Tree with Edge Extraction. We can see that the KNN increased by 6% accuracy while the Decision Tree changed less than a percent. This indicates that the greedy heuristic of KNN where it chooses 5 nearest neighbors performs better than the divide and conquer method for the Decision Tree.

That being said, even with the edge extraction both still have less than 65% accuracy which is not very impressive. This is due to the shortcomings in our edge detection method where we had to use a pre-determined medium kernel size. In our algorithm, we were not able to properly detect edges in images where the cat/dog was the entire picture or the background picture was extremely noisy because those require kernels that are extremely small or extremely large respectively. When performing our LDA for edge extraction analysis, we saw that these images were classified in the same points for cats and dogs. Therefore, it is most likely that a great percentage of the images that were mislabeled fall into this category. (For information please visit our Edge Extraction page.)

If we were to use pre-trained models for edge extraction, we expect that the accuracies would be much higher for the KNN model. In fact, we have begun to work on CNNs, which tend to have higher accuracy in image classification. In the future, it would be useful to use those models to extract features and repass them into the KNN and Decision Tree Models to see if the accuracy improves, but that is beyond the scope of this project.

Note: The KNN&DT-Edge code can only run half of our dataset without running into RAM issues on Google Colab. If you'd like to run it on the full data set you will need to download the file and run it locally. Comments have been added in the places where you would need to modify the number of images the code is being run on.

Note: We also made a few attempts to plot a meaningful decision boundary plot for the KNN, but since the code is not in full working condition, the files have been added to the final submission with a quick note on the README.

Page updated

Report abuse