{"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":"Group QUIZ 2 (Dog and Cat Recognizer with BoVW and KNN)\n* 2440037430 - Tyrone Matthew Phanghegar\n* 2440013506 - Sofie Kimberly\n* 2440022050 - James Martin","metadata":{}},{"cell_type":"markdown","source":"Import libraries","metadata":{}},{"cell_type":"code","source":"import cv2 as cv\nimport numpy as np\nimport matplotlib.pyplot as plt\nimport os\nimport zipfile\nfrom collections import Counter\nfrom scipy.cluster.vq import *\nfrom sklearn.cluster import KMeans\nfrom sklearn.preprocessing import StandardScaler\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.model_selection import train_test_split\nfrom sklearn.metrics import confusion_matrix, classification_report\nimport seaborn","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2023-01-26T04:24:47.484617Z","iopub.execute_input":"2023-01-26T04:24:47.484917Z","iopub.status.idle":"2023-01-26T04:24:49.033863Z","shell.execute_reply.started":"2023-01-26T04:24:47.484851Z","shell.execute_reply":"2023-01-26T04:24:49.032903Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"function get_image_names to get all file names within the dataset, which is later on used to determine splitting among train and test data","metadata":{}},{"cell_type":"code","source":"def get_image_names(root_path):\n    names = os.listdir(root_path)\n    return names","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:24:50.983630Z","iopub.execute_input":"2023-01-26T04:24:50.984870Z","iopub.status.idle":"2023-01-26T04:24:50.989775Z","shell.execute_reply.started":"2023-01-26T04:24:50.984824Z","shell.execute_reply":"2023-01-26T04:24:50.988853Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"function get_images is to get the images listed in img_name_list from the given root path","metadata":{}},{"cell_type":"code","source":"def get_images(root_path, img_name_list):\n    img_list = []\n    img_class_list = []\n    \n    for img_name in img_name_list:\n        img_path = root_path + '/' + img_name\n        img = cv.imread(img_path)\n        img_list.append(img)\n        \n        if ('cat' in img_name):\n            img_class_list.append(0)\n        elif ('dog' in img_name):\n            img_class_list.append(1)\n    \n    return img_list, img_class_list","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:24:53.501880Z","iopub.execute_input":"2023-01-26T04:24:53.503047Z","iopub.status.idle":"2023-01-26T04:24:53.510364Z","shell.execute_reply.started":"2023-01-26T04:24:53.502983Z","shell.execute_reply":"2023-01-26T04:24:53.509368Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"**Bag of Visual Words (BoVW)**\n\nConsists of 3 parts:\n1. Feature detection and description (we used SIFT)\n2. Dictionary/codewords generation (perform k-means clustering over all vectors. The resulting center of cluters are the codewords/visual words, which represent similar image patches.)\n3. Vector quantization (comparing the distances between visual words with the images' features using scipy.cluster.vq. If the current feature descriptor is closer to centroid/visual word i, then it belongs to cluster i. This will produce a histogram (the bag of words) for each image, which represent the frequency of visual words in the image.","metadata":{}},{"cell_type":"markdown","source":"Extract image descriptors using SIFT","metadata":{}},{"cell_type":"code","source":"def get_sift_descriptors(img_list):\n    sift = cv.SIFT_create()\n    descriptor_list = []\n\n    for img in img_list:\n        _, descriptors = sift.detectAndCompute(img, None)\n        descriptor_list.append(descriptors)\n    \n    return descriptor_list","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:24:55.269998Z","iopub.execute_input":"2023-01-26T04:24:55.270377Z","iopub.status.idle":"2023-01-26T04:24:55.276381Z","shell.execute_reply.started":"2023-01-26T04:24:55.270347Z","shell.execute_reply":"2023-01-26T04:24:55.275207Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Elbow method (wcss)","metadata":{}},{"cell_type":"code","source":"def elbow_method_cluster(descriptor_list):\n    stacked_descriptors = descriptor_list[0]\n    for descriptor in descriptor_list[1:]:\n        stacked_descriptors = np.vstack((stacked_descriptors, descriptor))\n    stacked_descriptors = np.float32(stacked_descriptors)\n    \n    wcss = []\n    k_values = []\n    for i in range(1, 10):\n        clustering = KMeans(n_clusters=i, init='k-means++', random_state=42)\n        clustering.fit(stacked_descriptors)\n        wcss.append(clustering.inertia_)\n        k_values.append(i)\n    \n    plt.plot(wcss, marker='o')\n    plt.xticks(np.arange(0, len(wcss)), k_values)\n    plt.title('Elbow Method: WCSS vs K (number of clusters)')\n    plt.xlabel('K')\n    plt.ylabel('Inertia')\n    plt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T05:17:03.287633Z","iopub.execute_input":"2023-01-26T05:17:03.288572Z","iopub.status.idle":"2023-01-26T05:17:03.298150Z","shell.execute_reply.started":"2023-01-26T05:17:03.288536Z","shell.execute_reply":"2023-01-26T05:17:03.297206Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Clustering (creating centroids) using K-means, in which we will experiment with k (number of clusters) of 2 (based on number of class, dog and cat) and custom (optimal number, based on elbow method/wcss)","metadata":{}},{"cell_type":"code","source":"def clustering(descriptor_list, k):\n    stacked_descriptors = descriptor_list[0]\n    for descriptor in descriptor_list[1:]:\n        stacked_descriptors = np.vstack((stacked_descriptors, descriptor))\n    stacked_descriptors = np.float32(stacked_descriptors)\n    \n    centroids, _ = kmeans(stacked_descriptors, k, 20)\n\n    return centroids","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:24:59.088295Z","iopub.execute_input":"2023-01-26T04:24:59.088645Z","iopub.status.idle":"2023-01-26T04:24:59.094233Z","shell.execute_reply.started":"2023-01-26T04:24:59.088614Z","shell.execute_reply":"2023-01-26T04:24:59.093185Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Vector quantization (Bag of Words)\n","metadata":{}},{"cell_type":"code","source":"def vector_quantization(descriptor_list, number_of_images, centroids):\n    image_features = np.zeros((number_of_images, len(centroids)), \"float32\")\n\n    for i in range(number_of_images):\n        words, _ = vq(descriptor_list[i], centroids)\n        for w in words:\n            image_features[i][w] += 1\n\n    return image_features","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:25:00.670063Z","iopub.execute_input":"2023-01-26T04:25:00.670729Z","iopub.status.idle":"2023-01-26T04:25:00.676177Z","shell.execute_reply.started":"2023-01-26T04:25:00.670693Z","shell.execute_reply":"2023-01-26T04:25:00.675165Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Histogram normalization using standard scaler, where data is scaled to a standard deviation of 1 and mean of 0, so that the histogram's frequencies are distributed to a wider range.","metadata":{}},{"cell_type":"code","source":"def normalization(img_feature_list):\n    stdscaler = StandardScaler().fit(img_feature_list)\n    img_feature_list = stdscaler.transform(img_feature_list)\n\n    return img_feature_list","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:25:02.231095Z","iopub.execute_input":"2023-01-26T04:25:02.231652Z","iopub.status.idle":"2023-01-26T04:25:02.236530Z","shell.execute_reply.started":"2023-01-26T04:25:02.231615Z","shell.execute_reply":"2023-01-26T04:25:02.235223Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"**Classification using nearest neighbors**\n\nElbow method to determine the optimal number of k (nearest neighbors) in KNN by plotting error rate. Only odd numbers are considered in order to have a tiebreaker.","metadata":{}},{"cell_type":"code","source":"def elbow_method_neighbor(train_feature_list, train_class_list, test_feature_list, test_class_list):\n    error_rate = []\n    min_error = 100\n    min_idx = -1\n    for i in range(1, 300, 2):\n        knn = KNeighborsClassifier(n_neighbors=i)\n        knn.fit(train_feature_list, train_class_list)\n        pred_i = knn.predict(test_feature_list)\n        err = np.mean(pred_i != test_class_list)\n        error_rate.append(err)\n        \n        if (err < min_error):\n            min_error = err\n            min_idx = i\n        \n    k_values = [1]\n    for i in range(10, 301, 10):\n        k_values.append(i)\n    \n    print(\"Minimum error rate is at k = \", min_idx, \"with error rate of \", min_error)\n    plt.figure(figsize=(20, 5))\n    plt.plot(error_rate, marker='o')\n    plt.xticks(np.arange(0, 151, 5), k_values)\n    plt.title('Elbow Method: Error rate vs K (number of neighbors)')\n    plt.xlabel('K')\n    plt.ylabel('Error Rate')\n    plt.show()\n    \n    return min_idx, min_error","metadata":{"execution":{"iopub.status.busy":"2023-01-26T05:17:21.815550Z","iopub.execute_input":"2023-01-26T05:17:21.815898Z","iopub.status.idle":"2023-01-26T05:17:21.824389Z","shell.execute_reply.started":"2023-01-26T05:17:21.815868Z","shell.execute_reply":"2023-01-26T05:17:21.823193Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"KNN\n\nK-nearest neighbors is a supervised machine learning algorithm that is used to make classification or prediction. Since this is a classification task, then the algorithm must determine whether an object is a 'Dog' or 'Cat'. To determine this, KNN uses a technique called 'majority voting' or simply checks the K nearest points and  predict the class based on the voting of the most frequent class.","metadata":{}},{"cell_type":"code","source":"def KNN(train_feature_list, train_class_list, test_feature_list, test_class_list, k):\n    knn = KNeighborsClassifier(n_neighbors=k)\n    knn.fit(train_feature_list, train_class_list)\n\n    results = knn.predict(test_feature_list)\n    return results","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:26:14.431597Z","iopub.execute_input":"2023-01-26T04:26:14.431959Z","iopub.status.idle":"2023-01-26T04:26:14.437803Z","shell.execute_reply.started":"2023-01-26T04:26:14.431928Z","shell.execute_reply":"2023-01-26T04:26:14.436779Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"**Main code**\n\nOur KNN experiment consists of 2 models:\n1. KNN with 2 clusters/centroids and elbow method observation-based number of neighbors\n2. KNN with elbow method observation-based number of clusters and also elbow method observation-based number of neighbors","metadata":{}},{"cell_type":"code","source":"with zipfile.ZipFile(\"../input/dogs-vs-cats/train.zip\",'r') as z:\n    z.extractall(\".\")","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:26:16.396351Z","iopub.execute_input":"2023-01-26T04:26:16.396758Z","iopub.status.idle":"2023-01-26T04:26:27.253535Z","shell.execute_reply.started":"2023-01-26T04:26:16.396708Z","shell.execute_reply":"2023-01-26T04:26:27.251979Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Read and split train and test images","metadata":{}},{"cell_type":"code","source":"root_path = \"./train\"\nimg_name_list = get_image_names(root_path)\ntrain_name_list, test_name_list = train_test_split(img_name_list, test_size=0.1, random_state=42)\n\ntrain_name_list = train_name_list[:5400]\ntest_name_list = test_name_list[:600]\n\ntrain_image_list, train_class_list = get_images(root_path, train_name_list)\ntest_image_list, test_class_list = get_images(root_path, test_name_list)\n\nprint(\"Number of train images = \", len(train_image_list))\nprint(Counter(train_class_list))\nprint(\"Number of test images = \", len(test_image_list))\nprint(Counter(test_class_list))","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:26:32.623855Z","iopub.execute_input":"2023-01-26T04:26:32.624345Z","iopub.status.idle":"2023-01-26T04:26:45.800465Z","shell.execute_reply.started":"2023-01-26T04:26:32.624297Z","shell.execute_reply":"2023-01-26T04:26:45.799390Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Due to memory limit issues, the total of images being used is 6000 out of 25000, with ratio between train and test data being 9:1. The counter above show the distribution of classes in train and test dataset; 0 for cat and 1 for dog. The numbers show that they are balanced.","metadata":{}},{"cell_type":"code","source":"train_descriptor_list = get_sift_descriptors(train_image_list)\ntest_descriptor_list = get_sift_descriptors(test_image_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T04:27:14.566553Z","iopub.execute_input":"2023-01-26T04:27:14.566919Z","iopub.status.idle":"2023-01-26T04:33:33.552098Z","shell.execute_reply.started":"2023-01-26T04:27:14.566887Z","shell.execute_reply":"2023-01-26T04:33:33.551051Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"(1) KNN with 2 clusters/centroids and elbow method observation-based number of neighbors\n\nUnder a simple logic that the number of categories in this dataset is 2 (dog and cat), our first attempt uses k (number of clusters) = 2.","metadata":{}},{"cell_type":"code","source":"centroids = clustering(train_descriptor_list, 2)\ntrain_feature_list = vector_quantization(train_descriptor_list, len(train_image_list), centroids)\ntrain_feature_list = normalization(train_feature_list)\n\ntest_feature_list = vector_quantization(test_descriptor_list, len(test_image_list), centroids)\ntest_feature_list = normalization(test_feature_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T07:42:24.424576Z","iopub.execute_input":"2023-01-26T07:42:24.424988Z","iopub.status.idle":"2023-01-26T08:24:17.702255Z","shell.execute_reply.started":"2023-01-26T07:42:24.424951Z","shell.execute_reply":"2023-01-26T08:24:17.700688Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"min_error_idx, min_error_val = elbow_method_neighbor(train_feature_list, train_class_list, test_feature_list, test_class_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T08:27:19.181422Z","iopub.execute_input":"2023-01-26T08:27:19.181834Z","iopub.status.idle":"2023-01-26T08:27:24.052876Z","shell.execute_reply.started":"2023-01-26T08:27:19.181801Z","shell.execute_reply":"2023-01-26T08:27:24.051936Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"Using elbow method, we can observe the error rates as visualized by the plot above, and the global minima is found at k=41, with an error rate of 0.39. At the same time, through visual observation, we can see that the plot only continues to averagely decrease until +- k = 40. Therefore, we can conclude that the elbow is located at the same point as the global minima, which is k = 41.","metadata":{}},{"cell_type":"code","source":"results = KNN(train_feature_list, train_class_list, test_feature_list, test_class_list, 41)\n\nconf_matrix = confusion_matrix(test_class_list, results)\nax = seaborn.heatmap(conf_matrix, xticklabels='01', yticklabels='01', annot=True, cmap='Blues', fmt='g')\nax.set_xlabel('Actual')\nax.set_ylabel('Predicted')\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T08:27:33.284097Z","iopub.execute_input":"2023-01-26T08:27:33.284693Z","iopub.status.idle":"2023-01-26T08:27:33.537926Z","shell.execute_reply.started":"2023-01-26T08:27:33.284656Z","shell.execute_reply":"2023-01-26T08:27:33.536922Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(classification_report(test_class_list, results, target_names=['Cat', 'Dog']))","metadata":{"execution":{"iopub.status.busy":"2023-01-26T08:27:36.215737Z","iopub.execute_input":"2023-01-26T08:27:36.216128Z","iopub.status.idle":"2023-01-26T08:27:36.228756Z","shell.execute_reply.started":"2023-01-26T08:27:36.216098Z","shell.execute_reply":"2023-01-26T08:27:36.227649Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"(2) KNN with elbow method observation-based number of clusters and also elbow method observation-based number of neighbors\n\nHowever, when observing the dataset, it is apparent that there are diverse images with different types of dogs and cats. It would make sense to have a multicluster KNN, where the number of cluster not only represents cats/dogs, but might also help differentiating subtypes of cats/dogs. In order to find this optimal number of clusters, we use elbow method with WCSS.","metadata":{}},{"cell_type":"code","source":"elbow_method_cluster(train_descriptor_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T06:04:46.216783Z","iopub.execute_input":"2023-01-26T06:04:46.217681Z","iopub.status.idle":"2023-01-26T07:38:56.093113Z","shell.execute_reply.started":"2023-01-26T06:04:46.217631Z","shell.execute_reply":"2023-01-26T07:38:56.091977Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"The WCSS plot shows that the elbow (or bend) is at either k = 3 or k = 4 clusters; yet it is more obvious to observe that the curve after k = 3 has formed an almost straight, flat line. Therefore, the optimal number of clusters we will use is 3.","metadata":{}},{"cell_type":"code","source":"centroids = clustering(train_descriptor_list, 3)\ntrain_feature_list = vector_quantization(train_descriptor_list, len(train_image_list), centroids)\ntrain_feature_list = normalization(train_feature_list)\n\ntest_feature_list = vector_quantization(test_descriptor_list, len(test_image_list), centroids)\ntest_feature_list = normalization(test_feature_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T05:18:02.197748Z","iopub.execute_input":"2023-01-26T05:18:02.198226Z","iopub.status.idle":"2023-01-26T06:01:30.652089Z","shell.execute_reply.started":"2023-01-26T05:18:02.198183Z","shell.execute_reply":"2023-01-26T06:01:30.650586Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"min_error_idx, min_error_val = elbow_method_neighbor(train_feature_list, train_class_list, test_feature_list, test_class_list)","metadata":{"execution":{"iopub.status.busy":"2023-01-26T06:01:44.810739Z","iopub.execute_input":"2023-01-26T06:01:44.811124Z","iopub.status.idle":"2023-01-26T06:01:50.047799Z","shell.execute_reply.started":"2023-01-26T06:01:44.811090Z","shell.execute_reply":"2023-01-26T06:01:50.046731Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"This plot also doesn't show a proper curve, which imply that the clusters in this model most likely had irregular shapes. However, although the global minima is located at k = 73 neighbors, we can observe that the error rate averagely decreases until +- k = 60.\nTherefore, we can conclude that the elbow is located k = 61.","metadata":{}},{"cell_type":"code","source":"results = KNN(train_feature_list, train_class_list, test_feature_list, test_class_list, 61)\n\nconf_matrix = confusion_matrix(test_class_list, results)\nax = seaborn.heatmap(conf_matrix, xticklabels='01', yticklabels='01', annot=True, cmap='Blues', fmt='g')\nax.set_xlabel('Actual')\nax.set_ylabel('Predicted')\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T06:03:31.321524Z","iopub.execute_input":"2023-01-26T06:03:31.321958Z","iopub.status.idle":"2023-01-26T06:03:31.663577Z","shell.execute_reply.started":"2023-01-26T06:03:31.321912Z","shell.execute_reply":"2023-01-26T06:03:31.662162Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"print(classification_report(test_class_list, results, target_names=['Cat', 'Dog']))","metadata":{"execution":{"iopub.status.busy":"2023-01-26T06:03:34.455718Z","iopub.execute_input":"2023-01-26T06:03:34.456126Z","iopub.status.idle":"2023-01-26T06:03:34.469285Z","shell.execute_reply.started":"2023-01-26T06:03:34.456092Z","shell.execute_reply":"2023-01-26T06:03:34.468388Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"In conclusion, with the Dogs vs Cats dataset, KNN with 2 clusters obtained a test accuracy of 61%, while KNN with optimal number of clusters (k = 3) resulted in a test accuracy of 59%. It turns out that there are no improvements after a custom optimal value of k (clusters) are chosen using elbow method (WCSS). This is likely to have happened due to the cluster's irregular shapes, which can be proven from the improper curves of error rate plots.","metadata":{}},{"cell_type":"code","source":"plt.figure(figsize = (10, 30))\nlabels = [\"Cat\", \"Dog\"]\nfor i in range(30):\n    plt.xticks([])\n    plt.yticks([])\n    plt.subplot(6, 5, i + 1)\n    plt.imshow(cv.cvtColor(test_image_list[i], cv.COLOR_BGR2RGB))\n    plt.title(labels[results[i]])\nprint(\"Preview of 30 Random KNN Classification Results (with 2nd model)\")\nplt.show()","metadata":{"execution":{"iopub.status.busy":"2023-01-26T06:04:35.008214Z","iopub.execute_input":"2023-01-26T06:04:35.008575Z","iopub.status.idle":"2023-01-26T06:04:36.769177Z","shell.execute_reply.started":"2023-01-26T06:04:35.008543Z","shell.execute_reply":"2023-01-26T06:04:36.768306Z"},"trusted":true},"execution_count":null,"outputs":[]}]}