### clustering algorithm

A typical unsupervised learning algorithm, which is mainly used to automatically classify similar samples into one category.

In the clustering algorithm, samples are divided into different categories according to the similarity between samples. Different clustering results will be obtained for different similarity calculation methods.

The biggest difference between clustering algorithm and classification algorithm is that clustering algorithm is unsupervised learning algorithm, while classification algorithm belongs to supervised learning algorithm.

k-means actually contains two layers:

- K: number of initial center points (number of planned clusters)
- means: average the distance from the center point to other data points
- k-means clustering steps

1. Randomly set K points in the feature space as the initial clustering center

2. For each other point, calculate the distance to K centers. For unknown points, select the nearest cluster center as the marker category

3. Then, after facing the marked cluster center, recalculate the new center point (average value) of each cluster

4. If the calculated new center point is the same as the original center point (the center of mass no longer moves), then it is over, otherwise repeat the second step of the process

### kmean algorithm in sklearn

Import package

from sklearn.cluster import KMeans, import pandas as pd import numpy as np import matplotlib.pyplot as plt

Load data data = pd.read_csv("kmeans.txt", delimiter=" ",header=None) data

0 1 2 3

0 1.658985 4.285136 NaN NaN

1 -3.453687 3.424321 NaN NaN

2 4.838138 -1.151539 NaN NaN

... ... ... ... ...

79 -4.905566 -2.911070 NaN NaN

80 rows × 4 columns

The data is in txt format. The third and fourth columns have nan values. Because they are spaces, make a conversion to delete the last two columns

data = data.iloc[:,:2] data

0 1 0 1.658985 4.285136 1 -3.453687 3.424321 .. ... ... 79 -4.905566 -2.911070 80 rows × 2 columns

# Set k value k = 4 estimator = KMeans(n_clusters=k) # estimator = MiniBatchKMeans(n_clusters=k) estimator.fit(data) centers = estimator.cluster_centers_ centers

array([[ 2.6265299 , 3.10868015],

[-3.38237045, -2.9473363 ],

[-2.46154315, 2.78737555],

[ 2.80293085, -2.7315146 ]])

4 categories center point of each category

result = estimator.predict(data) result

Prediction results

array([0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2,

3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1,

0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2,

3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1])

estimator.labels_

array([0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2,

3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1,

0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2,

3, 1, 0, 2, 3, 1, 0, 2, 3, 1, 0, 2, 3, 1])

#Draw each data point and use different colors to represent the classification mark = ['or', 'ob', 'og', 'oy'] for i in range(len(data)): plt.plot(data.iloc[i,0],data.iloc[i,1], mark[result[i]]) # # Draw the center point of each category mark = ['*r', '*b', '*g', '*y'] for i,center in enumerate(centers): plt.plot(center[0],center[1], mark[i], markersize=20) plt.show()

# Gets the range of data values x_min, x_max = data.iloc[:, 0].min() - 1, data.iloc[:, 0].max() + 1 y_min, y_max = data.iloc[:, 1].min() - 1, data.iloc[:, 1].max() + 1 # Generate grid matrix xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02), np.arange(y_min, y_max, 0.02)) z = estimator.predict(np.c_[xx.ravel(), yy.ravel()])# Travel is similar to flatten in that multidimensional data is converted to one dimension. Flatten will not change the original data, and travel will change the original data z = z.reshape(xx.shape) # Contour map cs = plt.contourf(xx, yy, z) # Display results # Draw each data point and use different colors to represent the classification mark = ['or', 'ob', 'og', 'oy'] for i in range(len(data)): plt.plot(data.iloc[i,0],data.iloc[i,1], mark[result[i]]) # Draw the center point of each category mark = ['*r', '*b', '*g', '*y'] for i,center in enumerate(centers): plt.plot(center[0],center[1], mark[i], markersize=20) plt.show()

When the amount of data becomes large, we can use the minibatch kmeans (n_clusters = k) algorithm.

Mini Batch K-Means algorithm is a variant of K-Means algorithm, which uses a small batch of data subsets to reduce the calculation time. The so-called small batch here refers to the data subsets randomly selected during each training algorithm. Using these randomly generated subsets to train the algorithm greatly reduces the calculation time, and the result is generally only slightly worse than the standard algorithm.

The iterative algorithm has two steps:

1: Randomly select some data from the data set to form a small batch, and assign them to the nearest centroid

2: Update centroid

Compared with the K-means algorithm, the data is updated on each small sample set.

Mini Batch K-Means has faster convergence speed than K-Means, but at the same time

It also reduces the effect of clustering, but it is not obvious in the actual project.

Summary of clustering algorithm

k-means algorithm is relatively simple, but it also has several major shortcomings

(1) The selection of K value is specified by the user. Different K results will be quite different, as shown in the figure below. On the left is the result of k=3, which is too sparse. In fact, the blue cluster can be divided into two clusters. The figure on the right shows the result of k=5. It can be seen that the two clusters of red diamond and blue diamond can be combined into one cluster:

(2) It is sensitive to the selection of k initial centroids and is easy to fall into local minimum. For example, when the above algorithm is running, we may get different results, such as the following two cases. K-means also converges, but converges to the local minimum:

(3) There are limitations, such as the following non spherical data distribution:

(4) When the database is large, the convergence will be slow.