Algorithm: K-Means

阅读量：360 次

发布时间：2019-03-04

本文共 4531 字，大约阅读时间需要 15 分钟。

K-Means

The K-Means is an unsupervised learning algorithm which has the input sample data without label.

Sometimes we use the CRM system to manage the relationship between the customer. The concept is clustering

The application of clustering:

It can also be used to compress the images

The concept of K-mean:

1. rearange each sample to the nearest category by compare the distances.

2. for each category we calculate the center point.

For K = 2

We choose two center point randomly

We clustering each example to each category respect to the center points.

Then we recalculate the center point by the calculating the mean coordinate of each points of the respect cluster(category.)

We use the new center points for clustering.

Then we recalculate the center point again.

And we do the cluster again:

If the new center point is the same as the previous iteration, then we can stop the calculation for converge.

Python Implementation for K-Mean

# import packagefrom copy import deepcopyimport numpy as npimport pandas as pdimport matplotlib.pyplot as plt# set paramter k for K-meansk = 3# randomize the center point. and save the result into CX = np.random.random((200, 2)) * 10C_x = np.random.choice(range(0, int(np.max(X[:, 0]))), size = k, replace = False)C_y = np.random.choice(range(0, int(np.max(X[:, 1]))), size = k, replace = False)C = np.array(list(zip(C_x, C_y)), dtype = np.float32)print("The init center point is :")print(C)# plot the center pointplt.scatter(X[:, 0], X[:, 1], c = '#050505', s = 7)plt.scatter(C[:, 0], C[:, 1], marker = '*', s = 300, c = 'g')plt.show()

# store the previous center pointC_old = np.zeros(C.shape)clusters = np.zeros(len(X))# calculate the distancedef dist(a, b, ax = 1):    return np.linalg.norm(a - b, axis = ax)error = dist(C, C_old, None)# iteration for K-mean clustering until converge(that is the error = 0)while error != 0:    # Assigning each value to its closest cluster    for i in range(len(X)):        distances = dist(X[i], C)        category = np.argmin(distances)        clusters[i] = category        # We save the old center points    C_old = deepcopy(C)    # and calculate the new center points    for i in range(k):        points = [X[j] for j in range(len(X)) if clusters[j] == i]        C[i] = np.mean(points, axis = 0)    error = dist(C, C_old, None)# plot the clusterscolors = ['r', 'g', 'b', 'y', 'c', 'm']fig, ax = plt.subplots()for i in range(k):    points = np.array([X[j] for j in range(len(X)) if clusters[j] == i])    ax.scatter(points[:, 0], points[:, 1], s = 7, c = colors[i])ax.scatter(C[:, 0], C[:, 1], marker = '*', s = 200, c = '#050505')plt.show()

K-Means in detail

What is the object function os K-mean？

At first ,we don't known the cluster and the center point, how do we define the loss function?

we obtain two parameters γ and μ from the object function of K-mean

We can optimize the parameter separately，the approach is set one parameters as known and we optimize the other one.

Does the K-means must converge？

$l=\sum_{i=1}^{N} \sum_{k=1}^{k} \gamma_{i k}\left\|x_{i-} \mu_{k l}\right\|_{2}^{2}$

Alternative Optimization

1）fix {uk} to solve {γik}

calculate the distance between sample to the center points

tag each sample to the specific cluster

2) Fix{γik} to recalculate center{uk}

$l=\sum_{k=1}^{k} \sum_{i: i \in \text { cluster} \atop-k}\left\|x_{i}-\mu_{k}\right\|_{2}^{2}$

It is an optimization problem, the step 1 well let our object function become small.

the step 2 will let our object function become small.

Coordinate Descent

EM Algorithm(GMM)

Gaussian Mixer Model

K-Means named hard cluster, GMM - soft cluster

The different start center point will result different result

Because we could only obtain the local optima due to the object function of k-mean is not convex

How to choose K for K-mean？

Recall the loss function

$l=\sum_{i=1}^{N} \sum_{k=1}^{k} \gamma_{i k}\left\|x_{i-} \mu_{k l}\right\|_{2}^{2}$

base on the change of the L to choose the K

Vector Qualization

This method can be used to compress the image data. The core concept is that we use the k-mean to present the similary color pixels

#import packagesfrom pylab import imread, imshow, figure, show, subplotimport numpy as npfrom sklearn.cluster import KMeansfrom copy import deepcopy# read the image dataimg = imread('Tulips.jpg')imshow(img)show()# convert three dimension tensor into two dimension matrixpixel = img.reshape(img.shape[0] * img.shape[1], 3)pixel_new = deepcopy(pixel)print (img.shape)# construct K-means modelmodel = KMeans(n_clusters = 3)labels = model.fit_predict(pixel)palette = model.cluster_centers_for i in range(len(pixel)):    pixel_new[i,:] = palette[labels[i]]# reshow the compressed imageimshow(pixel_new.reshape(img.shape[0], img.shape[1], 3))show()

原始图像，