{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Bag of Visual Words (BoVW) & k-Nearest Neighbors for Dogs vs. Cats Classification\n\nUsing the dogs vs cats dataset collected from Kaggle, we want to try and construct a k-nearest neighbors classifier fitting it with visual vocabulary created from the data retrieved.","metadata":{}},{"cell_type":"code","source":"!unzip -q \"/kaggle/input/dogs-vs-cats/test1.zip\"\n!unzip -q \"/kaggle/input/dogs-vs-cats/train.zip\"","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:52:49.868952Z","iopub.execute_input":"2023-01-26T15:52:49.869484Z","iopub.status.idle":"2023-01-26T15:53:07.811322Z","shell.execute_reply.started":"2023-01-26T15:52:49.86938Z","shell.execute_reply":"2023-01-26T15:53:07.809878Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Time to setup our environment.","metadata":{}},{"cell_type":"code","source":"import os\nimport random\nimport cv2 as cv\nimport numpy as np\nimport matplotlib.pyplot as plt\nfrom scipy.cluster.vq import vq, kmeans","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:07.813349Z","iopub.execute_input":"2023-01-26T15:53:07.813754Z","iopub.status.idle":"2023-01-26T15:53:08.137044Z","shell.execute_reply.started":"2023-01-26T15:53:07.813715Z","shell.execute_reply":"2023-01-26T15:53:08.135705Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's specify the provided train and test directory.","metadata":{}},{"cell_type":"code","source":"train_dir = \"/kaggle/working/train\"\ntest_dir = \"/kaggle/working/test1\"","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.139036Z","iopub.execute_input":"2023-01-26T15:53:08.139908Z","iopub.status.idle":"2023-01-26T15:53:08.145791Z","shell.execute_reply.started":"2023-01-26T15:53:08.139856Z","shell.execute_reply":"2023-01-26T15:53:08.144449Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Given that the data is provided with two labels which are dog and cat. We store it in a list where cat should be the first index positionally as it is specified that cat is identified as 0. Whereas dog is identified as 1, so it should be the second index positionally.","metadata":{}},{"cell_type":"code","source":"labels = [\"cat\", \"dog\"]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.150061Z","iopub.execute_input":"2023-01-26T15:53:08.15116Z","iopub.status.idle":"2023-01-26T15:53:08.158585Z","shell.execute_reply.started":"2023-01-26T15:53:08.151102Z","shell.execute_reply":"2023-01-26T15:53:08.157231Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's now check the sample size of data provided.","metadata":{}},{"cell_type":"code","source":"len(os.listdir(train_dir)), len(os.listdir(test_dir))","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.160998Z","iopub.execute_input":"2023-01-26T15:53:08.162164Z","iopub.status.idle":"2023-01-26T15:53:08.198432Z","shell.execute_reply.started":"2023-01-26T15:53:08.162108Z","shell.execute_reply":"2023-01-26T15:53:08.197237Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Since there is a huge amount of data provided, we want 5000 sample of the data from the train directory to prevent expensive computing resources.","metadata":{}},{"cell_type":"code","source":"random.seed(21)\nfilenames = os.listdir(train_dir)\ntrain_data = random.sample(filenames, 5000)\ntrain_data[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.199951Z","iopub.execute_input":"2023-01-26T15:53:08.200384Z","iopub.status.idle":"2023-01-26T15:53:08.230385Z","shell.execute_reply.started":"2023-01-26T15:53:08.200348Z","shell.execute_reply":"2023-01-26T15:53:08.229218Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Notice how the file format contains label for the specific image. We can store them into a list.","metadata":{}},{"cell_type":"code","source":"train_labels = []\n\nfor filename in train_data:\n    \n    if filename.split(\".\")[0] == \"dog\":\n        train_labels.append(1)\n    elif filename.split(\".\")[0] == \"cat\":\n        train_labels.append(0)\n        \nprint(f\"There are {train_labels.count(1)} dog images in the train directory.\")\nprint(f\"There are {train_labels.count(0)} cat images in the train directory.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.232796Z","iopub.execute_input":"2023-01-26T15:53:08.233827Z","iopub.status.idle":"2023-01-26T15:53:08.245162Z","shell.execute_reply.started":"2023-01-26T15:53:08.233784Z","shell.execute_reply":"2023-01-26T15:53:08.243811Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The sample taken for both dogs and cats is equally divided.","metadata":{}},{"cell_type":"code","source":"train_images = []\n\nfor filename in train_data:\n    filepath = os.path.join(train_dir, filename)\n    image = cv.imread(filepath)\n    image = cv.cvtColor(image, cv.COLOR_BGR2RGB)\n    train_images.append(image)\n\nprint(f\"Loaded {len(train_images)} images from the train directory.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:08.247321Z","iopub.execute_input":"2023-01-26T15:53:08.248031Z","iopub.status.idle":"2023-01-26T15:53:23.891542Z","shell.execute_reply.started":"2023-01-26T15:53:08.247981Z","shell.execute_reply":"2023-01-26T15:53:23.890558Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's take a look at some of the images.","metadata":{}},{"cell_type":"code","source":"plt.figure(figsize=(15, 15))\n\nindex = 1\n\nfor image in train_images[:25]:\n    plt.subplot(5, 5, index)\n    plt.imshow(image, cmap=\"gray\")\n    plt.title(labels[train_labels[index - 1]])\n    plt.axis(\"off\")\n    \n    index = index + 1\n    \nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:23.892742Z","iopub.execute_input":"2023-01-26T15:53:23.893107Z","iopub.status.idle":"2023-01-26T15:53:25.944658Z","shell.execute_reply.started":"2023-01-26T15:53:23.893074Z","shell.execute_reply":"2023-01-26T15:53:25.943066Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We use Scale Invariant Features Transform (SIFT) to extract local feature descriptors.","metadata":{}},{"cell_type":"code","source":"train_descriptors = []\nfeature_extractor = cv.SIFT_create()\n\nfor image in train_images:\n    gray_image = cv.cvtColor(image, cv.COLOR_RGB2GRAY)\n    _, descriptors = feature_extractor.detectAndCompute(gray_image, None)\n    train_descriptors.append(descriptors)\n    \nprint(f\"Extracted {len(train_descriptors)} descriptors from train data.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:53:25.949461Z","iopub.execute_input":"2023-01-26T15:53:25.949904Z","iopub.status.idle":"2023-01-26T15:57:38.056152Z","shell.execute_reply.started":"2023-01-26T15:53:25.949864Z","shell.execute_reply":"2023-01-26T15:57:38.054681Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Next, we stack the descriptors for clustering purposes later on.","metadata":{}},{"cell_type":"code","source":"train_descriptors_stack = train_descriptors[0]\n\nfor descriptors in train_descriptors[1:]:\n    train_descriptors_stack = np.vstack((train_descriptors_stack, descriptors))\n    \ntrain_descriptors_stack = train_descriptors_stack.astype(\"float32\")\ntrain_descriptors_stack[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T15:57:38.05783Z","iopub.execute_input":"2023-01-26T15:57:38.058234Z","iopub.status.idle":"2023-01-26T16:29:37.32729Z","shell.execute_reply.started":"2023-01-26T15:57:38.058198Z","shell.execute_reply":"2023-01-26T16:29:37.326021Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Here we retrieve the centroids from clustering with k-Means using the train descriptors.","metadata":{}},{"cell_type":"code","source":"centroids, _ = kmeans(train_descriptors_stack, k_or_guess=5, iter=20, seed=21)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:15:44.421918Z","iopub.execute_input":"2023-01-26T18:15:44.422406Z","iopub.status.idle":"2023-01-26T18:34:47.703057Z","shell.execute_reply.started":"2023-01-26T18:15:44.422366Z","shell.execute_reply":"2023-01-26T18:34:47.701798Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Finally, we can compute the vectors using the previously computed centroids and extracted features.","metadata":{}},{"cell_type":"code","source":"train_vectors = np.zeros((len(train_images), len(centroids)), dtype=\"float32\")\n\nfor index in range(len(train_images)):\n    words, _ = vq(train_descriptors[index], centroids)\n    \n    for word in words:\n        train_vectors[index][word] = train_vectors[index][word] + 1\n        \ntrain_vectors[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:34:47.705631Z","iopub.execute_input":"2023-01-26T18:34:47.706144Z","iopub.status.idle":"2023-01-26T18:35:18.665974Z","shell.execute_reply.started":"2023-01-26T18:34:47.706094Z","shell.execute_reply":"2023-01-26T18:35:18.664701Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We then normalize the values in these vectors to make it comparable to one another on the same scale.","metadata":{}},{"cell_type":"code","source":"train_vectors = np.array([vector / np.sum(vector) for vector in train_vectors])\ntrain_vectors[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:18.667584Z","iopub.execute_input":"2023-01-26T18:35:18.668643Z","iopub.status.idle":"2023-01-26T18:35:18.741309Z","shell.execute_reply.started":"2023-01-26T18:35:18.668584Z","shell.execute_reply":"2023-01-26T18:35:18.739813Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We repeat the same steps for test data as well. But now, we only use 50 samples for testing our model performance at the end.","metadata":{}},{"cell_type":"code","source":"random.seed(21)\nfilenames = os.listdir(test_dir)\ntest_data = random.sample(filenames, 50)\ntest_data[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:18.744586Z","iopub.execute_input":"2023-01-26T18:35:18.745853Z","iopub.status.idle":"2023-01-26T18:35:18.768748Z","shell.execute_reply.started":"2023-01-26T18:35:18.745782Z","shell.execute_reply":"2023-01-26T18:35:18.767518Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Obviously, the test data is provided without any labels.","metadata":{}},{"cell_type":"code","source":"test_images = []\n\nfor filename in test_data:\n    image = cv.imread(os.path.join(test_dir, filename))\n    image = cv.cvtColor(image, cv.COLOR_BGR2RGB)\n    test_images.append(image)\n    \nprint(f\"Loaded {len(test_images)} images from the test directory.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:18.77059Z","iopub.execute_input":"2023-01-26T18:35:18.771474Z","iopub.status.idle":"2023-01-26T18:35:18.942545Z","shell.execute_reply.started":"2023-01-26T18:35:18.771425Z","shell.execute_reply":"2023-01-26T18:35:18.941198Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Let's also take a look at our test images.","metadata":{}},{"cell_type":"code","source":"plt.figure(figsize=(15, 30))\n\nindex = 1\n\nfor image in test_images:\n    plt.subplot(10, 5, index)\n    plt.imshow(image, cmap=\"gray\")\n    plt.axis(\"off\")\n    \n    index = index + 1\n    \nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:18.943988Z","iopub.execute_input":"2023-01-26T18:35:18.944388Z","iopub.status.idle":"2023-01-26T18:35:22.468161Z","shell.execute_reply.started":"2023-01-26T18:35:18.944351Z","shell.execute_reply":"2023-01-26T18:35:22.466358Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We can extract the local features as done before with the training data.","metadata":{}},{"cell_type":"code","source":"test_descriptors = []\n\nfor image in test_images:\n    gray_image = cv.cvtColor(image, cv.COLOR_RGB2GRAY)\n    _, descriptors = feature_extractor.detectAndCompute(gray_image, None)\n    test_descriptors.append(descriptors)\n    \nprint(f\"Extracted {len(test_descriptors)} descriptors from test data.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:22.470073Z","iopub.execute_input":"2023-01-26T18:35:22.470475Z","iopub.status.idle":"2023-01-26T18:35:24.534355Z","shell.execute_reply.started":"2023-01-26T18:35:22.470432Z","shell.execute_reply":"2023-01-26T18:35:24.533025Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We then stack it so that it suits our purpose.","metadata":{}},{"cell_type":"code","source":"test_descriptors_stack = test_descriptors[0]\n\nfor descriptors in test_descriptors[1:]:\n    test_descriptors_stack = np.vstack((test_descriptors_stack, descriptors))\n    \ntest_descriptors_stack = test_descriptors_stack.astype(\"float32\")\ntest_descriptors_stack[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:24.535712Z","iopub.execute_input":"2023-01-26T18:35:24.536106Z","iopub.status.idle":"2023-01-26T18:35:24.675585Z","shell.execute_reply.started":"2023-01-26T18:35:24.53607Z","shell.execute_reply":"2023-01-26T18:35:24.674289Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"With the resources, we can now compute the test vectors.","metadata":{}},{"cell_type":"code","source":"test_vectors = np.zeros((len(test_images), len(centroids)), dtype=\"float32\")\n\nfor index in range(len(test_images)):\n    words, _ = vq(test_descriptors[index], centroids)\n    \n    for word in words:\n        test_vectors[index][word] = test_vectors[index][word] + 1\n        \ntest_vectors[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:24.676907Z","iopub.execute_input":"2023-01-26T18:35:24.677369Z","iopub.status.idle":"2023-01-26T18:35:24.930601Z","shell.execute_reply.started":"2023-01-26T18:35:24.677333Z","shell.execute_reply":"2023-01-26T18:35:24.929357Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"We want to scale the vectors so that it is comparable to one another.","metadata":{}},{"cell_type":"code","source":"test_vectors = np.array([vector / np.sum(vector) for vector in test_vectors])\ntest_vectors[:5]","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:24.934662Z","iopub.execute_input":"2023-01-26T18:35:24.935834Z","iopub.status.idle":"2023-01-26T18:35:24.945746Z","shell.execute_reply.started":"2023-01-26T18:35:24.935785Z","shell.execute_reply":"2023-01-26T18:35:24.944512Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Moving on, we model the k-Neighbors Classifier.","metadata":{}},{"cell_type":"code","source":"from scipy.stats import mode\n\nclass KNeighborsClassifier:\n    \n    def __init__(self, n_neighbors, p=2):\n        self.n_neighbors = n_neighbors\n        self.p = p\n        \n    def fit(self, X_train, y_train):\n        self.X_train = X_train\n        self.y_train = y_train\n        \n    def get_distance(self, a, b):\n        return np.sqrt(np.sum((a - b) ** 2))\n        \n    def predict(self, X_test):\n        y_pred = []\n        for test_data in X_test:\n            distances = []\n            for train_data in self.X_train:\n                distances.append(self.get_distance(test_data, train_data))\n            distances = np.array(distances)\n            sorted_distances = np.argsort(distances)[:self.n_neighbors]\n            neighbor_labels = self.y_train[sorted_distances]\n            y_pred.append(mode(neighbor_labels).mode[0])\n            \n        return y_pred","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:24.947249Z","iopub.execute_input":"2023-01-26T18:35:24.948343Z","iopub.status.idle":"2023-01-26T18:35:25.407844Z","shell.execute_reply.started":"2023-01-26T18:35:24.948299Z","shell.execute_reply":"2023-01-26T18:35:25.406748Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Having list the train data labels, we want to convert it into a numpy array so that it suits our model.","metadata":{}},{"cell_type":"code","source":"train_labels = np.array(train_labels)\ntype(train_labels)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:25.4095Z","iopub.execute_input":"2023-01-26T18:35:25.409914Z","iopub.status.idle":"2023-01-26T18:35:25.417775Z","shell.execute_reply.started":"2023-01-26T18:35:25.409839Z","shell.execute_reply":"2023-01-26T18:35:25.416449Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"For modeling, we want to have three set splits of training, validation, and testing set. The training of course being 80% of the train data we used, validation being 20% of the train data we used, and testing being the 50 test data we used.","metadata":{}},{"cell_type":"code","source":"from sklearn.model_selection import train_test_split\n\ntrain_vectors, val_vectors, train_labels, val_labels = train_test_split(train_vectors,\n                                                                        train_labels,\n                                                                        test_size=0.2,\n                                                                        random_state=21,\n                                                                        stratify=train_labels)\n\nprint(f\"There are {sum(train_labels == 1)} dog images for training.\")\nprint(f\"There are {sum(train_labels == 0)} cat images for training.\")\nprint(f\"There are {sum(val_labels == 1)} dog images for validation.\")\nprint(f\"There are {sum(val_labels == 0)} cat images for validation.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:25.419255Z","iopub.execute_input":"2023-01-26T18:35:25.419813Z","iopub.status.idle":"2023-01-26T18:35:25.657128Z","shell.execute_reply.started":"2023-01-26T18:35:25.419774Z","shell.execute_reply":"2023-01-26T18:35:25.65573Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"As we can see, the labels are equally spread across both training and validation data. Then, we can fit the training data into the model and predict on validation to initially take a look on its accuracy.","metadata":{}},{"cell_type":"code","source":"from sklearn.metrics import classification_report, accuracy_score\n\nmodel = KNeighborsClassifier(n_neighbors=10)\nmodel.fit(train_vectors, train_labels)\nval_pred = model.predict(val_vectors)\n\nprint(f\"The model reaches an accuracy of {accuracy_score(val_labels, val_pred) * 100:.2f}%.\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:35:25.659093Z","iopub.execute_input":"2023-01-26T18:35:25.659665Z","iopub.status.idle":"2023-01-26T18:36:02.696647Z","shell.execute_reply.started":"2023-01-26T18:35:25.659616Z","shell.execute_reply":"2023-01-26T18:36:02.695336Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"It seems like the model is not well suited for this specific problem as it is not doing a convincing job of predicting on validation data. However, let's have a look at what the model predicts for every test data we used.","metadata":{}},{"cell_type":"code","source":"plt.figure(figsize=(15, 30))\n\nindex = 1\npred = model.predict(test_vectors)\n\nfor image in test_images:\n    plt.subplot(10, 5, index)\n    plt.imshow(image, cmap=\"gray\")\n    plt.title(labels[pred[index - 1]])\n    plt.axis(\"off\")\n    \n    index = index + 1\n    \nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T18:40:18.379778Z","iopub.execute_input":"2023-01-26T18:40:18.38043Z","iopub.status.idle":"2023-01-26T18:40:23.960283Z","shell.execute_reply.started":"2023-01-26T18:40:18.380379Z","shell.execute_reply":"2023-01-26T18:40:23.957378Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"From our model predictions, it simply shows that the results is not convincing at all especially on images that are more challenging rather than an obvious visual of dogs or cats. It might be due to using visual vocabulary, which may not be the best solution to such a problem. Else, we can use more data and implement methods to set proper hyperparameters in our experiment.","metadata":{}}]}