目标
将样本按照 相似度 划分为 $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()
算法缺点
由于采用了贪心策略,导致容易局部收敛,在大规模数据集上求解较慢
对离群点和噪声点非常敏感
对初始质心选取敏感
不适用于非凸面形状样本集(如上图)