## Plain Python implementation of K-Means

K-Means is a very simple clustering algorithm (clustering belongs to unsupervised learning). Given a fixed number of clusters and an input dataset the algorithm tries to partition the data into clusters such that the clusters have high intra-class similarity and low inter-class similarity. 

### Algorithm

1. Initialize the cluster centers, either randomly within the range of the input data or (recommended) with some of the existing training examples

2. Until convergence  

   2.1. Assign each datapoint to the closest cluster. The distance between a point and cluster center is measured using the Euclidean distance.  

   2.2. Update the current estimates of the cluster centers by setting them to the mean of all instance belonging to that cluster  
   
   
### Objective function

The underlying objective function tries to find cluster centers such that, if the data are partitioned into the corresponding clusters, distances between data points and their closest cluster centers become as small as possible.

Given a set of datapoints ${x_1, ..., x_n}$ and a positive number $k$, find the clusters $C_1, ..., C_k$ that minimize

\begin{equation}
J = \sum_{i=1}^n \, \sum_{j=1}^k \, z_{ij} \, || x_i - \mu_j ||_2
\end{equation}

where:  
- $z_{ij} \in \{0,1\}$ defines whether of not datapoint $x_i$ belongs to cluster $C_j$
- $\mu_j$ denotes the cluster center of cluster $C_j$
- $|| \, ||_2$ denotes the Euclidean distance

### Disadvantages of K-Means
- The number of clusters has to be set in the beginning
- The results depend on the inital cluster centers
- It's sensitive to outliers
- It's not suitable for finding non-convex clusters
- It's not guaranteed to find a global optimum, so it can get stuck in a local minimum
- ...

### How to solve major disadvantages?
However, the k-means algorithm has at least two major theoretic shortcomings:

- First, it has been shown that the worst case running time of the algorithm is super-polynomial in the input size.
- Second, the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering.

The k-means++ algorithm addresses the second of these obstacles by specifying a procedure to initialize the cluster centers before proceeding with the standard k-means optimization iterations. With the k-means++ initialization, the algorithm is guaranteed to find a solution that is O(log k) competitive to the optimal k-means solution.  
Ref: https://datasciencelab.wordpress.com/2014/01/15/improved-seeding-for-clustering-with-k-means/


```python
import numpy as np
import matplotlib.pyplot as plt
import random
from sklearn.datasets import make_blobs
np.random.seed(123)

# % matplotlib inline
```

## K-Means class 


```python
class MyKMeansCluster():
    def __init__(self, n_cluster: int = 4):
        self.k = n_cluster
    
    def fit(self, data: np.ndarray):
        """
        Fits the k-means model to the given dataset
        """
        n_samples, _ = data.shape
        # init the centers using python random.sample(population, k)
        self.centers = np.array(random.sample(list(data), self.k))
        self.init_centers = np.copy(self.centers)
        
        # We will keep track of whether the assignment of data points to the clusters has changed. 
        # If it stops changing, we are done fitting the model
        old_assign = None
        n_iter = 0
        
        while True:
            # step 1: assign all data points based on the current centers
            new_assign = [self.classify(data_point) for data_point in data]
            if new_assign == old_assign:
                print("Iteration is done: {}!".format(n_iter))
                break
            old_assign = new_assign
            
            # step 2: re-calculate the centers
            for cluster_id in range(self.k):
                data_indexes = np.where(np.array(new_assign) == cluster_id)
                data_pointers = data[data_indexes]
                self.centers[cluster_id] = data_pointers.mean(axis = 0)
            n_iter += 1
    
    def classify(self, data_point: np.array) -> np.array:
        """
        Given a datapoint, compute the cluster closest to the datapoint. 
        Return the cluster ID of that cluster.
        """
        dists = self._l2_distance(data_point)
        return np.argmin(dists)
    
    def get_center(self):
        return self.centers
    
    def _l2_distance(self, data_point: np.array) -> np.ndarray:
        """ Calculate the l2 distances between current centers and an given data point"""
        dists = np.sqrt(np.sum((self.centers - data_point)**2, axis=1))
        return dists
    
    def _l1_distance(self, data_point: np.array) -> np.ndarray:
        dists = np.sum(np.abs(self.centers - data_point), axis=1)
        return dists

    def plot_clusters(self, data: np.array):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black, final centers in red")
        plt.scatter(data[:, 0], data[:, 1], marker='.', c='y')
        plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
        plt.scatter(self.init_centers[:, 0], self.init_centers[:,1], c='k')
        plt.show()
```

## Test case


```python
data1 = np.random.normal(loc=(10, 4), scale=0.1, size=(10, 2))
data2 = np.random.normal(loc=(5, 5), scale=0.1, size=(10, 2))

# X = np.concatenate((data1, data2), axis=0)
X = np.vstack((data1, data2))

kmeans = MyKMeansCluster(n_cluster = 2)
# print("type: {}, shape: {}".format(type(X), X.shape))
kmeans.fit(X)
kmeans.plot_clusters(X)

print("centers: {}".format(kmeans.get_center()))
```


```python
class KMeans():
    def __init__(self, n_clusters=4):
        self.k = n_clusters

    def fit(self, data):
        """
        Fits the k-means model to the given dataset
        """
        n_samples, _ = data.shape
        # initialize cluster centers
        self.centers = np.array(random.sample(list(data), self.k))
        self.initial_centers = np.copy(self.centers)

        # We will keep track of whether the assignment of data points
        # to the clusters has changed. If it stops changing, we are 
        # done fitting the model
        old_assigns = None
        n_iters = 0

        while True:
            new_assigns = [self.classify(datapoint) for datapoint in data]

            if new_assigns == old_assigns:
                print(f"Training finished after {n_iters} iterations!")
                return

            old_assigns = new_assigns
            n_iters += 1

            # recalculate centers
            for id_ in range(self.k):
                points_idx = np.where(np.array(new_assigns) == id_)
                datapoints = data[points_idx]
                self.centers[id_] = datapoints.mean(axis=0)

    def l2_distance(self, datapoint):
        dists = np.sqrt(np.sum((self.centers - datapoint)**2, axis=1))
        return dists

    def classify(self, datapoint):
        """
        Given a datapoint, compute the cluster closest to the
        datapoint. Return the cluster ID of that cluster.
        """
        dists = self.l2_distance(datapoint)
        return np.argmin(dists)

    def plot_clusters(self, data):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black, final centers in red")
        plt.scatter(data[:, 0], data[:, 1], marker='.', c=y)
        plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
        plt.scatter(self.initial_centers[:, 0], self.initial_centers[:,1], c='k')
        plt.show()
```

## Dataset


```python
X, y = make_blobs(centers=4, n_samples=1000)
print(f'Shape of dataset: {X.shape}')

fig = plt.figure(figsize=(8,6))
plt.scatter(X[:,0], X[:,1], c=y)
plt.title("Dataset with 4 clusters")
plt.xlabel("First feature")
plt.ylabel("Second feature")
plt.show()
```

## Initializing and fitting the model


```python
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)
```

    datapoints size: (179, 2)
    datapoints size: (71, 2)
    datapoints size: (249, 2)
    datapoints size: (501, 2)
    datapoints size: (157, 2)
    datapoints size: (93, 2)
    datapoints size: (250, 2)
    datapoints size: (500, 2)
    datapoints size: (147, 2)
    datapoints size: (103, 2)
    datapoints size: (250, 2)
    datapoints size: (500, 2)
    datapoints size: (142, 2)
    datapoints size: (108, 2)
    datapoints size: (250, 2)
    datapoints size: (500, 2)
    datapoints size: (138, 2)
    datapoints size: (112, 2)
    datapoints size: (250, 2)
    datapoints size: (500, 2)
    datapoints size: (136, 2)
    datapoints size: (114, 2)
    datapoints size: (250, 2)
    datapoints size: (500, 2)
    Training finished after 6 iterations!


## Plot initial and final cluster centers


```python
kmeans.plot_clusters(X)
```


```python
class MyKMeansCluster:
    def __init__(self, n_cluster: int):
        assert(n_cluster > 0), "Invalid cluster number {}".format(n_cluster)
        self.k = n_cluster
    
    def fit(self, data: np.array):
        n_samples, _ = data.shape
        
        # init centers
        self.centers = np.array(random.sample(list(data), self.k))
        self.init_centers = np.copy(self.centers)
        
        old_assign = None
        n_iter = 0
        
        while True:
            # calculate new assigments
            new_assign = [self.classify(data_point) for data_point in data]
            
            if new_assign == old_assign:
                print("fit is done after {} iterations".format(n_iter))
                break
            
            # re-calculate the centers
            for cluster_id in range(self.k):
                assign_indexes = np.where(np.array(new_assign) == cluster_id)
                cluster_points = data[assign_indexes]
                self.centers[cluster_id] = cluster_points.mean(axis=0)
                
            old_assign = new_assign
            n_iter += 1
            
    def classify(self, data_point: np.array):
        distances = self._l2_distance(data_point)
        return np.argmin(distances)
    
    def plot(self, data):
        plt.figure(figsize=(12,10))
        plt.title("Initial centers in black, final centers in red")
        plt.scatter(data[:, 0], data[:, 1], marker='.', c=y)
        plt.scatter(self.centers[:, 0], self.centers[:,1], c='r')
        plt.scatter(self.init_centers[:, 0], self.init_centers[:,1], c='k')
        plt.show()
        
    def _l2_distance(self, data_point: np.array):
        return np.sqrt(np.sum((self.centers - data_point)**2, axis=1))
```


```python
knn_cluster = MyKMeansCluster(4)
knn_cluster.fit(X)
knn_cluster.plot(X)
```


```python

```

d1184722954fc50f4c788a06c66abdc373d907d9
ipynb
Jupyter Notebook
kmeans.ipynb
louis-xu-ustc/machine_learning_basics
92839d0c24c469ff0094e6027a8d34313b87312f
MIT
kmeans.ipynb
louis-xu-ustc/machine_learning_basics
92839d0c24c469ff0094e6027a8d34313b87312f
MIT
kmeans.ipynb
louis-xu-ustc/machine_learning_basics
92839d0c24c469ff0094e6027a8d34313b87312f
MIT
Qwen/Qwen-72B
1. YES
2. YES