kmeans算法python源码_无监督聚类算法 K-Means 原理及 Python 代码实现

目标

将样本按照 相似度 划分为 $k$ 个群体。其中 $k$ 需要用户指定；相似度 通常由样本间距离决定，距离越近，相似度越高。

核心思想

输入：样本、$k$

随机选择 $k$ 个群体的质心

计算每个样本点分别到各个质心的欧式距离，并归入到距离最小质心所在的群体

根据样本群体划分，重新计算质心

重复步骤 2 和 步骤 3，直到所有质心不再变化

算法实现

需要使用到的库：numpy

定义欧式距离函数，公式为 $ d(a, b) = \sqrt{ \sum_{i=1}^{n} (a_i - b_i)^2 } = ||a-b||_2 $，$a, b$ 的维度为 $n$。

def distance(a, b):

return np.linalg.norm(a-b)

定义 $k$ 个质心初始化函数，其中 $data$ 为样本。

def random_centers(data, k):

data_shape = data.shape

data_min = np.min(data, axis=0) # (1, n)

data_max = np.max(data, axis=0) # (1, n)

data_diff = data_max - data_min # (1, n)

centers = []

for i in range(k):

centers.append(

data_min + np.multiply(np.random.rand(data_shape[1]), data_diff)

return np.concatenate(centers, axis=0) # (k, n)

定义 kmeans 函数，实现完整流程

def kmeans(data, k):

data_shape = data.shape

# 用于存储样本状态的矩阵，[样本所属群体，样本到该群体质心的距离]

data_label = np.mat(np.zeros([data_shape[0], 2]))

# 随机初始化质心

centers = random_centers(data, k)

learning = True

while learning:

learning = False

# 步骤2

for i in range(data_shape[0]):

min_dist = None

min_index = -1

for j in range(k):

# 步骤2：计算每个样本点分别到各个质心的欧式距离

dist = distance(data[i, :], centers[j, :])

# 步骤2：归入到距离最小质心所在的群体

if min_dist is None or min_dist > dist:

min_dist = dist

min_index = j

# 直到所有质心不再变化，停止循环

if data_label[i, 0] != min_index:

learning = True

data_label[i, :] = min_index, min_dist

# 步骤3

for c in range(k):

# 步骤3：根据样本群体划分，重新计算质心

labeled_data = data[(data_label[:, 0] == c).flatten().A[0]]

centers[c, :] = np.mean(labeled_data, axis=0)

return centers, data_label

算法测试

需要使用到的库：matplotlib、sklearn

if __name__ == '__main__':

X1, Y1 = datasets.make_circles(n_samples=2000, factor=0.6, noise=0.05,random_state = 1)

X2, Y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.5, 1.5]], cluster_std = [[0.1]], random_state = 5)

X = np.concatenate([X1, X2])

index, result = kmeans(np.mat(X), 5)

plt.scatter(X[:, 0], X[:, 1], c=result[:,0].flatten().A[0], marker='.')

plt.show()

算法缺点

由于采用了贪心策略，导致容易局部收敛，在大规模数据集上求解较慢

对离群点和噪声点非常敏感

对初始质心选取敏感

不适用于非凸面形状样本集(如上图)