kmeans|【ML31】Advanced K-means clustering algorithm 算法|聚类

Cost Function for K-means J ( c ( 1 ) , c ( 2 ) , . . . , c ( m ) , μ 1 , μ 2 , . . . , μ k ) = 1 m ∑ i = 1 m ∣ ∣ x ( i ) ? μ c ( i ) ∣ ∣ 2 J(c^{(1)},c^{(2)},...,c^{(m)},μ_1,μ_2,...,μ_k) = \frac 1 m \sum_{i=1}^m ||x^{(i)}-μ_{c^{(i)}}||^2 J(c(1),c(2),...,c(m),μ1?,μ2?,...,μk?)=m1?∑i=1m?∣∣x(i)?μc(i)?∣∣2
说明上式含义：上式为 K-means 的损失函数，其中c ( 1 ) , . . . c ( m ) c^{(1)},...c^{(m)} c(1),...c(m) 代表着有 m 个等待分类的点； μ 1 , . . . , μ k μ_1,...,μ_k μ1?,...,μk? 代表着会分为k k k 个组 Cluster。
而等式的右侧，即∣ ∣ x ( i ) ? μ c ( i ) ∣ ∣ 2 ||x^{(i)}-μ_{c^{(i)}}||^2 ∣∣x(i)?μc(i)?∣∣2，代表着第 i 个点距离μ 1 , . . . , μ k μ_1,...,μ_k μ1?,...,μk? 点之间最近距离的值。当这些值的和为最小时，即每个点都得到了合理的分配，这时损失函数 J 的值最小，且完成 K-means 聚类算法的迭代与循环。
初始化 K-means 的K值以及位置

关于初始化 K 的值，以及初始化 K 的位置。

初始化 k 的值首先，k应该选择为多少合适？
第一种选定k的值的方法：Elbow method

kmeans|【ML31】Advanced K-means clustering algorithm

文章图片

elbow 方法：在损失函数J-分类数量k 函数中，会有一个折点，在这点会骤减“ 通过增加分类数量k从而快速减少损失函数J” 的点。换句话说，在 elbow point 这点，会发现增大 k 的值不会给降低损失函数 J 带来很明显的影响。
很明显，J-K 函数最终会与x轴相交，但是将m个点分成m组明显不是我们想要的。虽然我们的目的是为了尽量减少损失函数J，但是目标并不是损失函数J为零。
第二种选定k的值的方法：枚举法
在 k 值的合理范围内，一般为 2-5 之间，枚举 k 带来的损失函数值，然后在更多k值带来的成本与减少的损失值之间进行权衡，选择一个合理的k值。
初始化K的位置选定好分为几个类之后，第一步初始化k的位置应该怎么选？

文章图片

假设 K=3，初始化三个 Centroid 点的位置为：
从坐标中16个待分类的点中不重复的选择三个点，然后按照 K-means 算法的步骤执行。有关 K-means 算法步骤见博客【ML30】Basic K-means
根据初始化点的不同，最终得到的结果也是不同的。很明显，我们想要的结果（K=3时损失函数J最小）为三图中的最上面的图而非下面两个图。所以现在的问题是如何初始化K的位置可以最后得到我们想要的上图的结果？

文章图片

方法为多次枚举。可能我们第一次，第二次初始化后没有得到最优解，但是我们循环10次，100次总会有达到最优解效果的一次。所以我们设置循环的方法，将10次，100次的方案的损失函数计算出来，然后找到损失函数最低的那次，作为我们的结果。
Pseudocode

In pseudocode, the K-means algorithm is as follows:# Initialize centroids # K is the number of clusters centroids = kMeans_init_centroids(X, K)for iter in range(iterations): # Cluster assignment step: # Assign each data point to the closest centroid. # idx[i] corresponds to the index of the centroid # assigned to example i idx = find_closest_centroids(X, centroids)# Move centroid step: # Compute means based on centroid assignments centroids = compute_means(X, idx, K)

Python code K-means Part1：找到最近的质心点

说明两个函数作用：
np.linalg.norm(a,b[0])： ( a [ 0 ] ? b [ 0 ] ) 2 + ( a [ 1 ] ? b [ 0 ] ) 2 + . . . + ( a [ m ] ? b [ 0 ] ) 2 \sqrt {(a[0]-b[0])^2+(a[1]-b[0])^2+...+(a[m]-b[0])^2} (a[0]?b[0])2+(a[1]?b[0])2+...+(a[m]?b[0])2 ?
np.argmin( c )：获得数组 c 中最小值的索引值（位置）获得数组 c 中最小值的索引值（位置）获得数组c中最小值的索引值（位置）

from numpy import linalg as LA def find_closest_centroids(X, centroids):K = centroids.shape[0]# K即Centroid质心的数量 idx = np.zeros(X.shape[0], dtype=int) # 初始化一个全为零数的组，其目的是记录每个点的被分为哪个centroidfor i in range(X.shape[0]): distance = [] for j in range(centroids.shape[0]): norm_ij = LA.norm(X[i]-centroids[j]) # 为每个点测量其与所有质心的距离，记录在 distance 数组中。 distance.append(norm_ij)idx[i] = np.argmin(distance)# idx数组中记录着每个点与哪个质心距离最近return idx

Part2：计算新的质心点的坐标

说明一个函数的作用：
idx.ravel()：将多维数组拉伸为一维数组

#####################################################################
STOP HERE
我想解释一下python函数含义，当然已知可以跳过直接看代码部分

X[idx.ravel() == k, :]

首先，ravel 函数的作用：

import numpy as np a = np.array([[1,2,3], [4,5,1], [7,8,1]]) b = a.ravel()# 用ravel()方法将数组a拉成一维数组 print(b)

“拉伸”后结果

文章图片

其次，解释 idx.ravel() == k

import numpy as np# 导入numpy模块a = np.array([[1,2,3], [4,5,1], [7,8,1]]) b = a.ravel()==1# 设置b为a拉伸成为一维数组之后值为1的索引的数组 print(b)

文章图片

STOP END
#####################################################################

def compute_centroids(X, idx, K):m, n = X.shape centroids = np.zeros((K, n))for k in range(K): centroids[k, :] = np.mean(X[idx.ravel() == k, :], axis=0)return centroids

Part3：核心代码

def run_kMeans(X, initial_centroids, max_iters=10):m, n = X.shape K = initial_centroids.shape[0] centroids = initial_centroids previous_centroids = centroids idx = np.zeros(m)for i in range(max_iters): print("K-Means iteration %d/%d" % (i, max_iters-1))idx = find_closest_centroids(X, centroids) # 分配质心 centroids = compute_centroids(X, idx, K) # 重置质心位置 plt.show() return centroids, idx

Part4：random初始化