k-means algorithm

Partition based method

Given a data set D with N data objects and the number of clusters to be generated K (k < n), in the partition method D, the objects are allocated to K groups, and each group represents a cluster. Then an objective function is used to evaluate the partition quality, so that the objects in the cluster are similar but different from the objects in other clusters.

characteristic

• It is very suitable to find spherical mutually exclusive clusters in small and medium-sized data sets.
• Is based on distance
• The cluster center can be represented by mean or center point

Introduction to K-means

Because of its excellent speed and good scalability, K-means clustering algorithm is the most famous clustering method. K-means algorithm is a process of repeatedly moving the center point of the class, moving the center point of the class, also known as centroids, to the average position of its containing members, and then re dividing its internal members.

Related concepts of K-means algorithm

Distance measurement

Manhattan distance

Driving from one intersection to another in Manhattan is obviously not a straight distance between two points. This actual driving distance is "Manhattan distance", also known as "city block distance".

Euclidean distance

Euclidean distance is a commonly used definition of distance, which refers to the real distance between two points in m-dimensional space

cosine similarity

Cosine similarity measures the difference between two individuals by using the cosine value of the angle between two vectors in vector space. Compared with distance measurement, cosine similarity pays more attention to the difference of two vectors in direction than distance or length.
The closer the cosine value is to 1, the closer the included angle is to 0 degrees, that is, the more similar the two vectors are, which is called "cosine similarity".

Common distance code implementation

import numpy as np
def distance(x,y,p=2):
    '''
    input:x(ndarray):Coordinates of the first sample
          y(ndarray):Coordinates of the second sample
          p(int):Manhattan distance is equal to 1 and Euclidean distance is equal to 2
    output:distance(float):x reach y Distance      
    ''' 
    if(p==1):
        return  sum(abs(x-y))
    elif(p==2):
        return (sum((x-y)**2))**(1/2)

Calculate the square of Euclidean distance between a sample and all samples in the data set

def euclidean_distance(one_sample, X):
    one_sample = one_sample.reshape(1, -1)
    distances = np.power(np.tile(one_sample, (X.shape[0], 1)) - X, 2).sum(axis=1)
    return distances

Centroid and objective function

centroid

Abbreviation of quality center. The centroid of a particle system is the average position of the mass distribution of the particle system.
The centroid may change with different data proximity measures and clustering objectives.

Proximity measure

Euclidean distance is usually used for points in Euclidean space and cosine similarity is used for documents.
Here, we use European distance

objective function

For the data whose proximity measure is Euclidean distance, we usually use the Sum of the Squared Error (SSE) as the objective function to measure the clustering quality. In other words, calculate the error of each data point, that is, the Euclidean distance from it to the nearest centroid, and then calculate the sum of the squares of the errors.

K-means algorithm flow

python class initialization

class MyKmeans():
    """Kmeans clustering algorithm .
    Parameters:
    -----------
    k: int
        Number of clusters.
    max_iterations: int
        Maximum number of iterations. 
    varepsilon: float
        Judge whether convergence, If all the last time k Cluster centers and all of this k The difference of two cluster centers is less than varepsilon, 
        Then the algorithm has converged
    """
    def __init__(self, k=5, max_iterations=300, varepsilon=0.0001, random_state=2):
        self.k = k
        self.max_iterations = max_iterations
        self.varepsilon = varepsilon
        np.random.seed(random_state)

Select initial centroid

    # Select self at random from all samples K-sample is used as the initial clustering center
    def init_random_centroids(self, X):
        n_samples, n_features = np.shape(X)
        centroids = np.zeros((self.k, n_features))
        for i in range(self.k):
            centroid = X[np.random.choice(range(n_samples))]
            centroids[i] = centroid
        return centroids

Assign each object to the most similar cluster

    # Returns the nearest central index [0, self.k) to the sample
    def _closest_centroid(self, sample, centroids):
        distances = euclidean_distance(sample, centroids)
        closest_i = np.argmin(distances)
        return closest_i

    # Classify all samples. The classification rule is to classify the sample to its nearest center
    def create_clusters(self, centroids, X):
        n_samples = np.shape(X)[0]
        clusters = [[] for _ in range(self.k)]
        for sample_i, sample in enumerate(X):
            centroid_i = self._closest_centroid(sample, centroids)
            clusters[centroid_i].append(sample_i)
        return clusters

Update the centroid of the cluster

    # Update the center
    def update_centroids(self, clusters, X):
        n_features = np.shape(X)[1]
        centroids = np.zeros((self.k, n_features))
        for i, cluster in enumerate(clusters):
            centroid = np.mean(X[cluster], axis=0)
            centroids[i] = centroid
        return centroids

Calculate the label and centroid

    # All samples are classified, and the index of their category is their category label
    def get_cluster_labels(self, clusters, X):
        y_pred = np.zeros(np.shape(X)[0])
        for cluster_i, cluster in enumerate(clusters):
            for sample_i in cluster:
                y_pred[sample_i] = cluster_i
        return y_pred

    # For clusters, return the centroid of its clustering result
    def get_cluster_centroids(self, clusters, X):
        centroids = np.zeros((self.k,np.shape(X)[1]))
        for i, cluster in enumerate(clusters):
            centroid = np.mean(X[cluster], axis=0)
            centroids[i] = centroid
        return centroids

clustering

    # Perform Kmeans clustering on the whole data set X and return the clustered label
    def predict(self, X):
                
        # Select self at random from all samples K-sample is used as the initial clustering center
        centroids = self.init_random_centroids(X)
         
        # Iterate until the algorithm converges (the cluster center of the last time almost coincides with the cluster center of this time) or reaches the maximum number of iterations
        for _ in range(self.max_iterations):
            # Classify all samples. The classification rule is to classify the sample to its nearest center
            clusters = self.create_clusters(centroids, X)
            former_centroids = centroids
             
            # Calculate the new cluster center
            centroids = self.update_centroids(clusters, X)
             
            # If there is almost no change in the cluster center, it indicates that the algorithm has converged and exits the iteration
            diff = centroids - former_centroids
            if diff.any() < self.varepsilon:
                break
         
        return self.get_cluster_labels(clusters, X),self.get_cluster_centroids(clusters, X)

K-means actual combat

requirement

The epidemic situation of each country in the data is different, and some even vary greatly. Therefore, we want to cluster 78 countries first to judge the epidemic prevention effect of each country.

data set

Data source: https://github.com/datasets/covid-19

Through data cleaning and integration, some data are as follows

data reduction

Cumulative confirmed case density = cumulative confirmed cases / total population; Density of existing confirmed cases = number of existing confirmed cases / total population
Therefore, the column of total population belongs to redundant data, so this column of data will be deleted during k-means algorithm.

data conversion

Data normalization is a basic operation of data mining. In reality, the dimensions of different features in the data may be inconsistent, and the differences between values may be very large. Without processing, it may affect the results of data analysis. Therefore, it is necessary to scale the data according to a certain proportion to make it fall in a specific area for comprehensive analysis.

Data normalization can effectively improve the accuracy and effectiveness of algorithms involving distance measurement. For the classification algorithm and clustering algorithm using distance measurement, data normalization is a particularly important step.

method

• Min max normalization
• z-score normalization (zero mean normalization) StandardScaler
• Normalization by decimal scaling

Introduction to sklearn preprocessing in python

There is a StandardScaler function in sklearn preprocessing that can be used for zero mean normalization

scaler = StandardScaler()
scaler.fit(data)
data = scaler.transform(data)

Practical k-means algorithm code

import pandas as pd
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from My_KMeans import MyKmeans

df = pd.read_csv('Test\\77 Country clustering.csv',header=0,index_col='country')
data = df.iloc[:,:-1]

scaler = StandardScaler()
scaler.fit(data)
data = scaler.transform(data)

mykm = MyKmeans()
label,centroids = mykm.predict(data)
print(label)
result_centroid = scaler.inverse_transform(centroids)
# pd.DataFrame(result_centroid).to_csv('Test\\centroids.csv')
print(result_centroid)
# km = KMeans(5,random_state=2) #The KMeans Library in sklearn is used here (the same effect can be achieved)
# res = km.fit(data)
# print(res.labels_+1)

# result = scaler.inverse_transform(res.cluster_centers_)
# print(result)