算法原理:
由于传统KMeans算法的聚类结果易受初始聚类中心点选择的影响,因此在传统的KMeans算法的基础上进行改进。
二分KMeans(Bisecting KMeans)算法的主要思想是:首先将所有点作为一个簇,然后将该簇一分为二。之后选择能最大限度降低聚类代价函数(误差平方和SSE)的簇划分为两个簇。以此进行下去,直到簇的数目等于给定的数目K为止。
代码实现:
基于DataFrame
def bi_kmeans(data: 'DataFrame', K: int) -> 'DataFrame':
"""二分KMeans
data: data['embedding'] 输入x的向量
K: 聚类类别数
"""
def sse(error):
"""计算误差平方和"""
return np.square(np.linalg.norm(error))
def euclidean_dist(v1, v2):
"""计算两个向量间的欧氏距离"""
return np.linalg.norm(v1 - v2)
def dist_from_center(label, embedding, cluster_center, offset=0):
"""计算每个元素与其类别中心的欧氏距离
offset: label的偏移量
return: float"""
center = cluster_center[label - offset]
dist = euclidean_dist(embedding, center)
return dist
# 初始化类的中心
cluster_center = [np.mean(data.embedding)]
# 初始化每个item的label和到聚类中心的距离
data['label'] = 0
data['dist_from_center'] = data.apply(lambda x: dist_from_center(x['label'], x['embedding'], cluster_center), axis=1)
# 当前k小于给定K值时
k = 1
while k < K :
print('Current Cluster Number: {} >>>'.format(k))
# 计算当前sse
total_sse = sse(data.dist_from_center)
sharp_drop = 0
# 遍历当前每个簇,将其一分为二,计算新的sse
keep_i = -1
for i in range(k):
# 第i簇数据
group_i = data[data.label == i]
if group_i.shape[0] > 2:
pre_sse = sse(group_i.dist_from_center)
# 二分当前簇
bi_kmeans = KMeans(n_clusters=2).fit(group_i.embedding.tolist())
# 更新label和dist
group_i['label'] = bi_kmeans.labels_
new_center = bi_kmeans.cluster_centers_
group_i['dist_from_center'] = group_i.apply(lambda x: dist_from_center(x['label'], x['embedding'], new_center), axis=1)
# 计算当前sse
post_sse = sse(group_i.dist_from_center)
# sse下降程度
drop = pre_sse - post_sse
# 保留最大下降ssd的i
if drop > sharp_drop:
keep_i = i
sharp_drop = drop
# 选出待二分的数据
group_i = data[data.label == keep_i]
group_i_index = data[data.label == keep_i].index
# 二分,更新label
bi_kmeans = KMeans(n_clusters=2).fit(group_i.embedding.tolist())
group_i['label'] = bi_kmeans.labels_ + k
data.loc[group_i_index, 'label'] = bi_kmeans.labels_ + k
new_center = bi_kmeans.cluster_centers_
# 更新距中心距离
data.loc[group_i_index, 'dist_from_center'] = group_i.apply(lambda x: dist_from_center(x['label'], x['embedding'], new_center, offset=k), axis=1)
# 更新超出k的label为原有label
k_plus_1_index = data[data.label == k + 1].index
data.loc[k_plus_1_index, 'label'] = keep_i
# 更新类别数
k += 1
return data
网友评论