# General instructions


## High Level Description

In this assignment you are asked to implement K-means clustering to identify main clusters in
the data, use the discovered centroid of cluster for classification. Specifically, you will

 - Implement K-means clustering algorithm to identify clusters in a two-dimensional toy-dataset.
 - Implement image compression using K-means clustering algorithm.
 - Implement classification using the centroids identified by clustering on digits dataset.
 - Implement K-means++ clustering algorithm to identify clusters in a two-dimensional toy-dataset i.e. implement the kmeans++ function to compute the centers.
 
NOTE: You only need to make changes in Kmeans.py and use KmeansTest.py for testing purposes and to see your results. You can find all TODO's sequentially in the Kmeans.py file. <br>
Depending on your environment you may need to install the python library named, ”pillow”, which is used by matplotlib to process some of the images needed for this assignment. <br>
You can install it by running ’pip3 install pillow’ in your command line.


```python
!pip3 install pillow
```

### Grading Guidelines (50 points):

You are only required to submit Kmeans.py as that is the only file where you will be making any changes.
 - get_k_means_plus_plus_center_indices - 5 points (5 *1)
 - transform_image - 10 points (5 * 2 test cases) We are checking the MSE and the number of iterations for this
 - Kmeans( ) class on Toy dataset - 15 points (3 * 5 test cases) We are checking the centroid and membership for Kmeans and Kmeans++ 
 - KmeansClassifier( ) class - 20 points (5 * 4 test cases) We are checking the accuracy and the centroids of the assignments.


### Office Hours

Ashir Alam (ashirala@usc.edu) <br> 
April 5th  12:00pm- 1:00pm Leavey 301F <br> 
April 9th 10am - 12pm Leavey 301F <br>
April 16th 10am - 12pm Leavey 301F <br>


### Dataset for K-Means Clustering

We will use 2 datasets - 2-D Toy Dataset and Digits datasets for K means part.<br>
Toy Dataset is a two-dimensional dataset generated from 4 Gaussian distributions. We will use this
dataset to visualize the results of our algorithm in two dimensions. You can find it in data_loader.py<br>
We will use digits dataset from sklearn to test K-means based classifier and generate digits using
Gaussian Mixture model. Each data point is a 8 × 8 image of a digit. This is similar to MNIST but less
complex. There are 10 classes in digits dataset. <br>
Link for Digits dataset: sklearn.datasets.digits http://scikit-learn.org/stable/modules/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits

## 1. K Means Clustering

 

Recall that for a dataset $ x_1, . . . , x_N ∈ R^D $, the K-means distortion objective is: 
$$ F(\{\mu_k\}, \{r_{nk}\}) = \sum_{i=1}^N \sum_{k=1}^K r_{nk} \|\mu_k- x_n\|_2^2     \qquad  (1)   $$   

where $ µ_1, . . . , µ_K $ are centroids of the K clusters and $ r_{ik} ∈ {0, 1} $ represents whether example i belongs to cluster k. <br>
Clearly, fixing the centroids and minimizing J over the assignment give

$$ \begin{equation}
    \hat r_{ik} = \begin{cases}
        1 & k = argmin_{k'} \|\mu_{k'}-x_n\|_2^2 \\
        0 & \text{Otherwise.}
    \end{cases}
    \label{eq:opt_membership}
\end{equation} \qquad  (2)$$

On the other hand, fixing the assignment and minimizing $J$ over the centroids give
$$ \begin{equation}
    \hat \mu_k =\frac{ \sum_{i=1}^N r_{nk} x_n}{\sum_{i=1}^N r_{nk}}
    \label{eq:opt_mean}
\end{equation} \qquad  (3) $$ 

What the K-means algorithm does is simply to alternate between these two steps.




### 1.1 Implementing k-means++ algorithm


Recall from lecture Kmeans++. Please refer to the algorithm below. In simple terms, cluster centers are initially chosen at random from the set of input observation vectors, where the probability of choosing vector x is high if x is not near any previously chosen centers. <br>

Here is a one-dimensional example. Our observations are $ [0, 1, 2, 3, 4] $. Let the first center, $ c1 $, be 0. The probability that the next cluster center, $ c2 $, is x is proportional to $ ||c1-x||^2 $. So, $ P(c2 = 1) = 1a, P(c2 = 2) = 4a, P(c2 = 3) = 9a, P(c2 = 4) = 16a $, where $ a = 1/(1+4+9+16) $.<br>
Suppose $ c2 = 4 $. Then, $ P(c3 = 1) = 1a, P(c3 = 2) = 4a, P(c3 = 3) = 1a $, where $ a = 1/(1+4+1) $. <br>
For more insights, follow this: http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf <br>


Implement Algorithm by filling out the TODO parts in function **get_k_means_plus_plus_center_indices** of file **kmeans.py**. You can test this function on Vocareum separately. 


```

def get_k_means_plus_plus_center_indices(n, n_cluster, x, generator=np.random):
    :param n: number of samples in the data
    :param n_cluster: the number of cluster centers required
    :param x: data - numpy array of points
    :param generator: random number generator from 0 to n for choosing the first cluster at random
            The default is np.random here but in grading, to calculate deterministic results,
            We will be using our own random number generator.


    :return: the center points array of length n_clusters with each entry being index to a sample
             which is chosen as centroid.
           
```
If the generator is still not clear, its basically a np.random but helps us control the result during testing. SO wherever you would use np.random, use generator instead. <br> 


### 1.2 Implementing K-means clustering algorithm


Implement Algorithm 1 by filling out the TODO parts (**fit** function) in class **KMeans** of file **kmeans.py**. Note the following:

 - Initialize means by picking self.n_cluster from N data points
 - Update means and membership until convergence or until you have made self.max_iter updates.
 - return (means, membership, number_of_updates)
 - If at some iteration, there exists a cluster k with no points assigned to it, then do not update the centroid of this cluster for this round.
 - While assigning a sample to a cluster, if there’s a tie (i.e. the sample is equidistant from two centroids), you should choose the one with smaller index (like what numpy.argmin does).
 - For each k, we are trying to compare based on the Euclidean distance. <br>
 
 
 ``` <br>
 Class KMeans:
        Attr:
            n_cluster - Number of cluster for kmeans clustering (Int)
            max_iter - maximum updates for kmeans clustering (Int)
            e - error tolerance (Float)
            generator - random number generator from 0 to n for choosing the first cluster at random
                The default is np.random here but in grading, to calculate deterministic results,
                We will be using our own random number generator.
            
            def __init__(self, n_cluster, max_iter=100, e=0.0001, generator=np.random):
                self.n_cluster = n_cluster
                self.max_iter = max_iter
                self.e = e
                self.generator = generator
              

            def fit(self, x, centroid_func=get_lloyd_k_means):
                Finds n_cluster in the data x
                params: 
                x - N X D numpy array
                centroid_func - To specify which algorithm we are using to compute the centers(Lloyd(regular) or Kmeans++) The default is Lloyd's Kmeans.
                
                returns: A tuple (centroids a n_cluster X D numpy array, y a length (N,) numpy array where cell i is the ith sample's assigned cluster, number_of_updates a Int)
            Note: Number of iterations is the number of time you update the assignment
 
 ```
 
After you complete the implementation, run KmeansTest.py to see the results of this on toy
dataset. You should be able to see three images generated in plots folder. In particular, you can see
toy dataset predicted labels.png and toy dataset real labels.png and compare the clusters identified by the algorithm against the real clusters. Your implementation should be able to recover the correct clusters sufficiently well. Representative images are shown in fig. 2. Red dots are cluster centroids.
Note that color coding of recovered clusters may not match that of correct clusters. This is due to mis-match
in ordering of retrieved clusters and correct clusters (which is fine). <br>






### 1.3 Classification with k-means

Another application of clustering is to obtain a faster version of the nearest neighbor algorithm. Recall that nearest neighbor evaluates the distance of a test sample from every training point to predict its class, which can be very slow. Instead, we can compress the entire training dataset to just the K centroids, where each centroid is now labeled as the majority class of the corresponding cluster. After this compression the prediction time of nearest neighbor is reduced from O(N) to just O(K) (see Algorithm 2 for the pseudocode). <br>
 
<br>
Complete the **fit** and **predict** function in **KMeansClassifier** in file **kmeans.py** . Once completed,
run **KmeansTest.py** to evaluate the classifier on a test set (digits). For comparison, the script will also print accuracy of a logistic classifier and a nearest neighbor classifier. (Note: a naive K-means classifier may not do well but it can be an effective unsupervised method in a classification pipeline .) <br>

Note: 1) break ties in the same way as in previous problems; 2) if some centroid doesn’t contain any
point, set the label of this centroid as 0. <br>

The prediction accuracy baseline is 0.77 for KMeans Lloyd(regular) algorithm and 0.72 for KMeans++ algorithm. Note: these differ on different datasets and in more cases Kmeans++ works better. 

```


    Class KMeansClassifier:
        
        Attr:
            n_cluster - Number of cluster for kmeans clustering (Int)
            max_iter - maximum updates for kmeans clustering (Int)
            e - error tolerance (Float)
            generator - random number generator from 0 to n for choosing the first cluster at random
            The default is np.random here but in grading, to calculate deterministic results,
            We will be using our own random number generator.
    

        def __init__(self, n_cluster, max_iter=100, e=1e-6, generator=np.random):
            self.n_cluster = n_cluster
            self.max_iter = max_iter
            self.e = e
            self.generator = generator


        def fit(self, x, y, centroid_func=get_lloyd_k_means):
        
            Train the classifier
            params:
                x - N X D size  numpy array
                y - (N,) size numpy array of labels
                centroid_func - To specify which algorithm we are using to compute the centers(Lloyd(regular) or Kmeans++) The default is Lloyd's Kmeans.
            returns:
                None
            Stores following attributes:
                self.centroids : centroids obtained by kmeans clustering (n_cluster X D numpy array)
                self.centroid_labels : labels of each centroid obtained by 
                    majority voting (N,) numpy array) 
                    
    
         def predict(self, x):
        
            Predict function
            params:
                x - N X D size  numpy array
            returns:
                predicted labels - numpy array of size (N,)
        
       
        
```


### 1.4 Image compression with K-means 
In this part, we will look at lossy image compression as an application of clustering. The idea is simply to treat each pixel of an image as a point $x_i$, then perform K-means algorithm to cluster these points, and finally replace each pixel with its centroid. <br> 

What you need to implement is to compress an image with K centroids given. Specifically, complete the
function **transform_image** in the file **kmeans.py**. You have to reduce the image pixels and size by replacing each RGB values with nearest code vectors based on Euclidean distance. <br>
After your implementation, and after completing Kmeans class, when you run KmeansTest.py, you should be able to see an image compressed_baboon.png in the plots folder. You can see that this image is distorted as compared to the original baboon.tiff. <br>
The ideal result should take about 35-40 iterations and the Mean Square Error should be less than 0.0098. It takes about 1-2 minutes to complete normally.


```
def transform_image(image, code_vectors):

        Quantize image using the code_vectors

        Return new image from the image by replacing each RGB value in image with nearest code vectors (nearest in euclidean distance sense)

        returns:
            numpy array of shape image.shape
```





```python
import numpy as np
```


```python
a = [40.25739993, -0.90848143]
b = [-40.11362305, 3.36270893]
```


```python
np.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)
```


```python
!pwd
```


```python
import time
```


```python
!python kmeansTest.py
```

    [+] K-Means on Toy Dataset
    [+] K-Means Vanilla
    current obj is:21.005828715842064
    current obj is:11.775075840226158
    current obj is:7.798263032257955
    current obj is:5.196863304021689
    current obj is:1.7362525284421513
    current obj is:0.0
    finish at tieration:5
    time takes for init phase:4.410743713378906e-05
    time takes for assign phase:0.07600855827331543
    time takes for recenter phase:0.018338441848754883
    time takes for calculting phase:0.0002689361572265625
    [success] : kmeans clustering done on toy dataset
    Toy dataset K means clustering converged in 100 steps
    
    [+] K-Means Plus Plus
    [+] returning center for [450, 450] points: [105, 308, 433, 207, 21, 183, 353, 277, 92]
    current obj is:17.131773111149105
    current obj is:0.03837134352341161
    current obj is:0.0
    finish at tieration:2
    time takes for init phase:1.0967254638671875e-05
    time takes for assign phase:0.022047758102416992
    time takes for recenter phase:0.005051136016845703
    time takes for calculting phase:8.893013000488281e-05
    [success] : kmeans clustering done on toy dataset
    Toy dataset K means clustering converged in 100 steps
    
    [+] K-Means Classification
    [+] K-Means Vanilla
    current obj is:19.032172655325788
    current obj is:1.9431216658063568
    current obj is:0.6370326823068089
    current obj is:0.28907528333436705
    current obj is:0.07965732382552201
    current obj is:0.07649490073191392
    current obj is:0.0722215469749252
    current obj is:0.03875062012088978
    current obj is:0.06301439148451696
    finish at tieration:8
    time takes for init phase:0.00018095970153808594
    time takes for assign phase:0.4124763011932373
    time takes for recenter phase:0.07694768905639648
    time takes for calculting phase:0.0004820823669433594
    [*] Prediction accuracy of K-means classifier with 10 cluster is 0.7222222222222222
    
    [+] K-Means Plus Plus
    [+] returning center for [1347, 1347] points: [1126, 723, 204, 1139, 1112, 1111, 1110, 1109, 928, 941]
    current obj is:21.640707654161865
    current obj is:1.3674124715725702
    current obj is:0.7560187440116068
    current obj is:0.3333613690466702
    current obj is:0.20685348761320696
    current obj is:0.11875970020033064
    current obj is:0.12751659131413587
    finish at tieration:6
    time takes for init phase:0.015789031982421875
    time takes for assign phase:0.39307188987731934
    time takes for recenter phase:0.08215069770812988
    time takes for calculting phase:0.0005495548248291016
    [*] Prediction accuracy of K-means classifier with 10 cluster is 0.6711111111111111
    [*] Accuracy of logistic regression classifier is 0.9622222222222222
    [*] Accuracy of Nearest Neighbour classifier is 0.9933333333333333



```python
#a = [1,2,3]
b = [4,5,6]
np.true_divide(b, 4)
```


```python
a = []
a[1]+=1
a[1]
```


```python
a = [1,2,10,0]
print(3 in a)
```


```python
a = np.array([[1,2,3],[2,3,4]])
b = np.array([[4,5,6],[7,8,9]])
#a**2 + b**2 - 2*a*b
np.sum(a**2 + b**2 - 2*a*b)
```




    102




```python
np.argmin(np.sum(a**2 + b**2 - 2* a* b,axis=1))
```


```python
a = [1,1,1]
np.argmin(a)
```


```python
x = {1: 2, 3: 4, 4: 3, 2: 1, 0: 0}
sorted_x = sorted(x.items(), key=lambda kv: kv[1])
```


```python
sorted_x
```


```python
a = {1:2}
len(a)
```


```python
import time
```


```python
start = time.time()
a = np.array([ 0,1])
b = np.array([[ 3, 4],[5,6]])
# c = a
print(min(np.sum(a**2 + b**2 - 2*a*b,axis=1)))
#cur_distance = -1
end = time.time()
print(end-start)
```


```python
start = time.time()
# a = np.array([1,2,3])
# #b = np.array([3])
# # np.linalg.norm(a - b)
# #print(np.true_divide(a,b))
# c = np.array(a)
cur_distance = float('inf')
end = time.time()
print(end-start)
```


```python
import numpy as np
```


```python
a = [[[0.64313725, 0.58823529, 0.27843137],
  [0.24705882, 0.22352941, 0.12156863],
  [0.29411765, 0.16862745, 0.03921569],
  [0.45882353, 0.46666667, 0.26666667],
  [0.55294118, 0.66666667, 0.39607843],
  [0.70196078, 0.7372549,  0.4627451 ]],
[[0.03529412, 0.04313725, 0.04705882],
  [0.03921569, 0.04705882, 0.04313725],
  [0.04313725, 0.05882353, 0.04705882],
  [0.01960784, 0.03137255, 0.01960784],
  [0.00784314, 0.01960784, 0.        ],
  [0.01568627, 0.01960784, 0.00784314]]]
# print(np.array(a).shape)

M,N = np.array(a).shape

for i in range(2):
    for j in range(6):
        print(a[i][j])
```

    (2, 6, 3)
    [0.64313725, 0.58823529, 0.27843137]
    [0.24705882, 0.22352941, 0.12156863]
    [0.29411765, 0.16862745, 0.03921569]
    [0.45882353, 0.46666667, 0.26666667]
    [0.55294118, 0.66666667, 0.39607843]
    [0.70196078, 0.7372549, 0.4627451]
    [0.03529412, 0.04313725, 0.04705882]
    [0.03921569, 0.04705882, 0.04313725]
    [0.04313725, 0.05882353, 0.04705882]
    [0.01960784, 0.03137255, 0.01960784]
    [0.00784314, 0.01960784, 0.0]
    [0.01568627, 0.01960784, 0.00784314]



```python
[ 9.25739993 -0.90848143]
[[ 1.46803737  8.83069153]
 [-8.33991861 -2.98825783]
 [-4.49239055 -8.02316563]
 [ 6.81286498 -5.80567293]
 [-4.63815699  7.82263388]
 [ 6.9738859   5.73474059]
 [ 9.00454882  0.12461644]
 [ 1.66467893 -9.12247052]
 [-8.25184968  3.16991064]]
[155.52565903 313.99108957 239.6754694   29.95823571 269.31887645
  49.34683509   1.13122489 125.11902879 323.20710352]
```


```python
a = 9.25739993
b = 1.46803737

c = -0.90848143
d = 8.83069153
(a-b)**2 + (c-d) **2


```




    155.5256590359249




```python

```

fe2d01a224b4005fc5451407420c1a903235e2b4
ipynb
Jupyter Notebook
PA4/kmeans/PA4_kmeans.ipynb
Magicicesea/Python-Machine-Learning-algorithm-implement
8a766932d0e65cbf65ad695f9d2c6a92857b41a3
MIT
PA4/kmeans/PA4_kmeans.ipynb
Magicicesea/Python-Machine-Learning-algorithm-implement
8a766932d0e65cbf65ad695f9d2c6a92857b41a3
MIT
PA4/kmeans/PA4_kmeans.ipynb
Magicicesea/Python-Machine-Learning-algorithm-implement
8a766932d0e65cbf65ad695f9d2c6a92857b41a3
MIT
Qwen/Qwen-72B
1. YES
2. YES