{"cells":[{"metadata":{"_uuid":"1af22bfc351387a4da1023a5bbf9f26ff547cb73"},"cell_type":"markdown","source":"## K Means Clustering not using any framework\n\nK means Clustering is a type of unsupervised learning. The goal of this algortihm is to find groups in the data. L1 and L2 distance are used.\n\n\nReference to this book. : Ethem Alpaydın Introduction to Machine Learning, third edition\n\n\n"},{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true,"scrolled":true},"cell_type":"code","source":"import numpy as np # linear algebra\nimport pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)\nimport matplotlib.pyplot as plt\nfrom sklearn.model_selection import train_test_split\nimport seaborn as sns\nimport os\nprint(os.listdir(\"../input\"))","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"8ced10f4eddb7e15180a5c058595ddedf72477ff"},"cell_type":"markdown","source":"## L1 distances"},{"metadata":{"_uuid":"b3379150816dd201005504ea1cdeb7f32a6254f5"},"cell_type":"markdown","source":"## Step 1 \nRead Data and Extract Label"},{"metadata":{"trusted":true,"_uuid":"6901cce2bf62950ff2d9566e7a60314f6e8bc04d"},"cell_type":"code","source":"train_all = pd.read_csv(\"../input/opt_digits_train.csv\")\ntrain_all = train_all.reset_index(drop=True)\nlabels = train_all.iloc[:,64]\ntrain_all = train_all.drop(labels = [\"64\"],axis = 1) ","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"0f6e861ff691545c8d8c21c74e3bc135def364e8"},"cell_type":"markdown","source":"## Step 2\nDetermine randomly k means center. \nk = 20 "},{"metadata":{"trusted":true,"_uuid":"a370efb61b9863bece5f4035e30f1b86260d4445"},"cell_type":"code","source":"clusters = np.zeros(len(train_all))\nk = 20\nn = train_all.shape[0]\nc = train_all.shape[1]\nmean = np.mean(train_all, axis = 0)\nstd = np.std(train_all, axis = 0)\ncenters = np.random.randn(k,c) + mean.values.reshape(1,64)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"c64188b920351170c36fb9cb97431d4ca49b16c4"},"cell_type":"markdown","source":"## Step 3\n* Store old centers\n* Store new centers\n* Error equals ( New center - Old centers)"},{"metadata":{"trusted":true,"_uuid":"040770efeff8565a34e6259972a19ce7b2c52951"},"cell_type":"code","source":"centers_L2 = centers.copy()\ncenters_old = np.zeros(centers.shape) \ncenters_new = centers.copy() \n\nclusters = np.zeros(n)\ndistances = np.zeros((n,k))\nerror = np.linalg.norm(centers_new - centers_old)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"b15076697b72dfe0f188c41f9176fc9ffde4a72f"},"cell_type":"markdown","source":"## Step 3\n* Find the distances of all figures to the centers and label them with the smallest distance\n* Each data point is assigned to its nearest centroid. \n* The centroids are recomputed.\n* If error equals zero, stop loop (No data points change clusters)"},{"metadata":{"trusted":true,"_uuid":"56c35023ddd0c9961e681bd14eea692cb4bba847"},"cell_type":"code","source":"while error != 0:\n    for i in range(k):\n        distances[:,i] = np.linalg.norm(train_all - centers_new[i], axis=1,ord=1) #L1 distances \n\n    clusters = np.argmin(distances, axis = 1)\n    centers_old = centers_new.copy()\n\n    for i in range(k):\n        centers_new[i] = np.mean(train_all[clusters == i], axis=0)\n        \n    error = np.linalg.norm(centers_new - centers_old)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"49a396bb494db4e8f259f3124b27ff83e6440dd6"},"cell_type":"markdown","source":"## Step 4\n* K = 20, \n* Number of Label  = 10 \n* Clusters is assigned to each label.\n* Calculate error - True Labels and Clusters labels"},{"metadata":{"trusted":true,"_uuid":"acf4c5ebe726153ee0e8d4da20c4cad120df07d7"},"cell_type":"code","source":"cluster_separete= []\ny = []\n\nfor m in range(20):\n    cluster_separete.append(labels[clusters == m])\nfor a in range(20):\n    x = []\n    for b in range(10):\n        x.append((cluster_separete[a]==b).sum())   \n    y.append(np.argmax(x))\n\ntotal_error = 0\nfor z in range(20):\n    total_true = (cluster_separete[z] == y[z]).sum()\n    total_error = total_error+ cluster_separete[z].shape[0]-total_true\n    \nk_means_clustering_error = total_error/train_all.shape[0] ","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"cb7ff34afcac3a978551a40e3de45e58f6c007eb"},"cell_type":"markdown","source":"## L2 Distances"},{"metadata":{"trusted":true,"_uuid":"7ff693160f04606898c3c649a837bd4141b803d7"},"cell_type":"code","source":"centers_old_L2 = np.zeros(centers_L2.shape) # to store old centers\ncenters_new_L2 = centers_L2.copy() # Store new centers\nclusters_L2 = np.zeros(n)\n\ndistances_L2 = np.zeros((n,k))\nerror_L2 = np.linalg.norm(centers_new_L2 - centers_old_L2)\ni = 0 \nwhile error_L2 != 0:\n    for i in range(k):\n        distances_L2[:,i] = np.linalg.norm(train_all - centers_new_L2[i],axis=1)  #L2 distances \n    clusters_L2 = np.argmin(distances_L2, axis = 1)\n    centers_old_L2 = centers_new_L2.copy()\n    for i in range(k):\n        centers_new_L2[i] = np.mean(train_all[clusters_L2 == i], axis=0)        \n    error_L2 = np.linalg.norm(centers_new_L2 - centers_old_L2)\n\n\n\ncluster_seperate_L2 = []\ny_L2 = []\n\nm = 0\nfor m in range(20):\n    cluster_seperate_L2.append(labels[clusters_L2 == m])\nfor a in range(20):\n    x = []\n    for b in range(10):\n        x.append((cluster_seperate_L2[a]==b).sum())   \n    y_L2.append(np.argmax(x))\n    \ntotal_error_L2 = 0\nfor z in range(20):\n    total_true_L2 = (cluster_seperate_L2[z] == y_L2[z]).sum()\n    total_error_L2 = total_error_L2+ cluster_seperate_L2[z].shape[0]-total_true_L2\n\nk_means_clustering_error_L2 = total_error_L2/train_all.shape[0] \n\nprint('Q3-k_means_clustering_error L1 and L2')\nprint(k_means_clustering_error)\nprint(k_means_clustering_error_L2)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"eea00bd64d7696a6b12d11c11f661dc708d55d1f"},"cell_type":"markdown","source":"L2 distances is the best solutions in this problem."}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}