K表示有条件
K means with a condition
我想将 K 均值（或任何其他简单的聚类算法）应用于具有两个变量的数据，但我希望聚类遵守一个条件：每个聚类的第三个变量之和 > some_value。
这可能吗？
处理此问题的一种方法是在 聚类之前过滤数据。
>>> cluster_data = df.loc[df['third_variable'] > some_value]
>>> from sklearn.cluster import KMeans
>>> y_pred = KMeans(n_clusters=2).fit_predict(cluster_data)
如果总和是指每个聚类的第三个变量的总和，那么您可以使用 RandomSearchCV 来查找满足或不满足条件的 KMeans 的超参数。
K-means本身就是一个优化问题。
您的附加约束也是一个相当常见的优化约束。
所以我宁愿使用优化求解器来解决这个问题。
符号：
- K 是簇数
- 假设前两个变量是点坐标 (x,y)
- V 表示第三个变量
- Ci : 每个簇 i
上的 V 总和
-S总和(sumCi)
- 和阈值 T
问题定义：
据我了解，目标是 运行 一种在尊重约束的同时保持 kmeans 精神的算法。
任务 1 - 按与质心的接近程度对点进行分组 [kmeans]
任务 2 - 对于每个集群 i，Ci > T* [constraint]
约束问题的常规 kmeans 限制：
常规 kmeans，通过以任意顺序获取点来将点分配给质心。在我们的例子中，这将导致 Ci 在添加点时不受控制地增长。
例如，K=2，T=40和4个点，第三个变量等于V1=50，V2=1，V3=50，V4=50。
还假设点 P1、P3、P4 更接近质心 1。点 P2 更接近质心 2。
让我们 运行 常规 kmeans 的分配步骤并跟踪 Ci :
1--取点P1，将其分配到簇1。C1=50 > T
2--取点P2，将其分配到簇2 C2=1
3-- 取点 P3，将其分配给簇 1。C1=100 > T => C1 增长太多！
4--取点P4，将其分配到簇1。C1=150 > T => !!!
修改后的 kmeans :
前面我们是想防止C1长的太多，帮助C2长。
这就像将香槟倒入几杯中：如果您看到一杯香槟较少，就去倒满。你这样做是因为你有限制：香槟的数量有限（S 是有界的）并且因为你希望每个玻璃杯都有足够的香槟（Ci>T）。
当然这只是一个类比。我们修改后的 kmeans 将以最小 Ci 向集群添加新点，直到达到约束（任务 2）。现在我们应该按什么顺序加分？通过接近质心（任务 1）。在对所有集群 i 实现所有约束后，我们可以 运行 对剩余未分配的点进行常规 kmeans。
实施：
接下来，我给出一个python修改算法的实现。图 1 显示了第三个变量的表示，它使用透明度来可视化大值 VS 低值。图 2 使用颜色显示了进化集群。
你可以玩accept_thresh参数。特别要注意：
对于 accept_thresh=0 => 常规 kmeans（立即达到约束）
对于 accept_thresh = third_var.sum().sum() / (2*K)，您可能会观察到一些靠近给定质心的点由于约束原因而受到另一个点的影响。
代码 :
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
import time
nb_samples = 1000
K = 3 # for demo purpose, used to generate cloud points
c_std = 1.2
# Generate test samples :
points, classes = datasets.make_blobs(n_features=2, n_samples=nb_samples, \
centers=K, cluster_std=c_std)
third_var_distribution = 'cubic_bycluster' # 'uniform'
if third_var_distribution == 'uniform':
third_var = np.random.random((nb_samples))
elif third_var_distribution == 'linear_bycluster':
third_var = np.random.random((nb_samples))
third_var = third_var * classes
elif third_var_distribution == 'cubic_bycluster':
third_var = np.random.random((nb_samples))
third_var = third_var * classes
# Threshold parameters :
# Try with K=3 and :
# T = K => one cluster reach cosntraint, two clusters won't converge
# T = 2K =>
accept_thresh = third_var.sum().sum() / (2*K)
def dist2centroids(points, centroids):
'''return arrays of ordered points to each centroids
first array is index of points
second array is distance to centroid
dim 0 : centroid
dim 1 : distance or point index
'''
dist = np.sqrt(((points - centroids[:, np.newaxis]) ** 2).sum(axis=2))
ord_dist_indices = np.argsort(dist, axis=1)
ord_dist_indices = ord_dist_indices.transpose()
dist = dist.transpose()
return ord_dist_indices, dist
def assign_points_with_constraints(inds, dists, tv, accept_thresh):
assigned = [False] * nb_samples
assignements = np.ones(nb_samples, dtype=int) * (-1)
cumul_third_var = np.zeros(K, dtype=float)
current_inds = np.zeros(K, dtype=int)
max_round = nb_samples * K
for round in range(0, max_round): # we'll break anyway
# worst advanced cluster in terms of cumulated third_var :
cluster = np.argmin(cumul_third_var)
if cumul_third_var[cluster] > accept_thresh:
continue # cluster had enough samples
while current_inds[cluster] < nb_samples:
# add points to increase cumulated third_var on this cluster
i_inds = current_inds[cluster]
closest_pt_index = inds[i_inds][cluster]
if assigned[closest_pt_index] == True:
current_inds[cluster] += 1
continue # pt already assigned to a cluster
assignements[closest_pt_index] = cluster
cumul_third_var[cluster] += tv[closest_pt_index]
assigned[closest_pt_index] = True
current_inds[cluster] += 1
new_cluster = np.argmin(cumul_third_var)
if new_cluster != cluster:
break
return assignements, cumul_third_var
def assign_points_with_kmeans(points, centroids, assignements):
new_assignements = np.array(assignements, copy=True)
count = -1
for asg in assignements:
count += 1
if asg > -1:
continue
pt = points[count, :]
distances = np.sqrt(((pt - centroids) ** 2).sum(axis=1))
centroid = np.argmin(distances)
new_assignements[count] = centroid
return new_assignements
def move_centroids(points, labels):
centroids = np.zeros((K, 2), dtype=float)
for k in range(0, K):
centroids[k] = points[assignements == k].mean(axis=0)
return centroids
rgba_colors = np.zeros((third_var.size, 4))
rgba_colors[:, 0] = 1.0
rgba_colors[:, 3] = 0.1 + (third_var / max(third_var))/1.12
plt.figure(1, figsize=(14, 14))
plt.title("Three blobs", fontsize='small')
plt.scatter(points[:, 0], points[:, 1], marker='o', c=rgba_colors)
# Initialize centroids
centroids = np.random.random((K, 2)) * 10
plt.scatter(centroids[:, 0], centroids[:, 1], marker='X', color='red')
# Step 1 : order points by distance to centroid :
inds, dists = dist2centroids(points, centroids)
# Check if clustering is theoriticaly possible :
tv_sum = third_var.sum()
tv_max = third_var.max()
if (tv_max > 1 / 3 * tv_sum):
print("No solution to the clustering problem !\n")
print("For one point : third variable is too high.")
sys.exit(0)
stop_criter_eps = 0.001
epsilon = 100000
prev_cumdist = 100000
plt.figure(2, figsize=(14, 14))
ln, = plt.plot([])
plt.ion()
plt.show()
while epsilon > stop_criter_eps:
# Modified kmeans assignment :
assignements, cumul_third_var = assign_points_with_constraints(inds, dists, third_var, accept_thresh)
# Kmeans on remaining points :
assignements = assign_points_with_kmeans(points, centroids, assignements)
centroids = move_centroids(points, assignements)
inds, dists = dist2centroids(points, centroids)
epsilon = np.abs(prev_cumdist - dists.sum().sum())
print("Delta on error :", epsilon)
prev_cumdist = dists.sum().sum()
plt.clf()
plt.title("Current Assignements", fontsize='small')
plt.scatter(points[:, 0], points[:, 1], marker='o', c=assignements)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='o', color='red', linewidths=10)
plt.text(0,0,"THRESHOLD T = "+str(accept_thresh), va='top', ha='left', color="red", fontsize='x-large')
for k in range(0, K):
plt.text(centroids[k, 0], centroids[k, 1] + 0.7, "Ci = "+str(cumul_third_var[k]))
plt.show()
plt.pause(1)
改进：
- 使用第三个变量的分布进行赋值。
- 管理算法的分歧
- 更好的初始化 (kmeans++)
我想将 K 均值（或任何其他简单的聚类算法）应用于具有两个变量的数据，但我希望聚类遵守一个条件：每个聚类的第三个变量之和 > some_value。 这可能吗？
处理此问题的一种方法是在 聚类之前过滤数据。
>>> cluster_data = df.loc[df['third_variable'] > some_value]
>>> from sklearn.cluster import KMeans
>>> y_pred = KMeans(n_clusters=2).fit_predict(cluster_data)
如果总和是指每个聚类的第三个变量的总和，那么您可以使用 RandomSearchCV 来查找满足或不满足条件的 KMeans 的超参数。
K-means本身就是一个优化问题。
您的附加约束也是一个相当常见的优化约束。
所以我宁愿使用优化求解器来解决这个问题。
符号：
- K 是簇数
- 假设前两个变量是点坐标 (x,y)
- V 表示第三个变量
- Ci : 每个簇 i
上的 V 总和
-S总和(sumCi)
- 和阈值 T
问题定义：
据我了解，目标是 运行 一种在尊重约束的同时保持 kmeans 精神的算法。
任务 1 - 按与质心的接近程度对点进行分组 [kmeans]
任务 2 - 对于每个集群 i，Ci > T* [constraint]
约束问题的常规 kmeans 限制：
常规 kmeans，通过以任意顺序获取点来将点分配给质心。在我们的例子中，这将导致 Ci 在添加点时不受控制地增长。
例如，K=2，T=40和4个点，第三个变量等于V1=50，V2=1，V3=50，V4=50。 还假设点 P1、P3、P4 更接近质心 1。点 P2 更接近质心 2。
让我们 运行 常规 kmeans 的分配步骤并跟踪 Ci :
1--取点P1，将其分配到簇1。C1=50 > T
2--取点P2，将其分配到簇2 C2=1
3-- 取点 P3，将其分配给簇 1。C1=100 > T => C1 增长太多！
4--取点P4，将其分配到簇1。C1=150 > T => !!!
修改后的 kmeans :
前面我们是想防止C1长的太多，帮助C2长。
这就像将香槟倒入几杯中：如果您看到一杯香槟较少，就去倒满。你这样做是因为你有限制：香槟的数量有限（S 是有界的）并且因为你希望每个玻璃杯都有足够的香槟（Ci>T）。
当然这只是一个类比。我们修改后的 kmeans 将以最小 Ci 向集群添加新点，直到达到约束（任务 2）。现在我们应该按什么顺序加分？通过接近质心（任务 1）。在对所有集群 i 实现所有约束后，我们可以 运行 对剩余未分配的点进行常规 kmeans。
实施：
接下来，我给出一个python修改算法的实现。图 1 显示了第三个变量的表示，它使用透明度来可视化大值 VS 低值。图 2 使用颜色显示了进化集群。
你可以玩accept_thresh参数。特别要注意：
对于 accept_thresh=0 => 常规 kmeans（立即达到约束）
对于 accept_thresh = third_var.sum().sum() / (2*K)，您可能会观察到一些靠近给定质心的点由于约束原因而受到另一个点的影响。
代码 :
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
import time
nb_samples = 1000
K = 3 # for demo purpose, used to generate cloud points
c_std = 1.2
# Generate test samples :
points, classes = datasets.make_blobs(n_features=2, n_samples=nb_samples, \
centers=K, cluster_std=c_std)
third_var_distribution = 'cubic_bycluster' # 'uniform'
if third_var_distribution == 'uniform':
third_var = np.random.random((nb_samples))
elif third_var_distribution == 'linear_bycluster':
third_var = np.random.random((nb_samples))
third_var = third_var * classes
elif third_var_distribution == 'cubic_bycluster':
third_var = np.random.random((nb_samples))
third_var = third_var * classes
# Threshold parameters :
# Try with K=3 and :
# T = K => one cluster reach cosntraint, two clusters won't converge
# T = 2K =>
accept_thresh = third_var.sum().sum() / (2*K)
def dist2centroids(points, centroids):
'''return arrays of ordered points to each centroids
first array is index of points
second array is distance to centroid
dim 0 : centroid
dim 1 : distance or point index
'''
dist = np.sqrt(((points - centroids[:, np.newaxis]) ** 2).sum(axis=2))
ord_dist_indices = np.argsort(dist, axis=1)
ord_dist_indices = ord_dist_indices.transpose()
dist = dist.transpose()
return ord_dist_indices, dist
def assign_points_with_constraints(inds, dists, tv, accept_thresh):
assigned = [False] * nb_samples
assignements = np.ones(nb_samples, dtype=int) * (-1)
cumul_third_var = np.zeros(K, dtype=float)
current_inds = np.zeros(K, dtype=int)
max_round = nb_samples * K
for round in range(0, max_round): # we'll break anyway
# worst advanced cluster in terms of cumulated third_var :
cluster = np.argmin(cumul_third_var)
if cumul_third_var[cluster] > accept_thresh:
continue # cluster had enough samples
while current_inds[cluster] < nb_samples:
# add points to increase cumulated third_var on this cluster
i_inds = current_inds[cluster]
closest_pt_index = inds[i_inds][cluster]
if assigned[closest_pt_index] == True:
current_inds[cluster] += 1
continue # pt already assigned to a cluster
assignements[closest_pt_index] = cluster
cumul_third_var[cluster] += tv[closest_pt_index]
assigned[closest_pt_index] = True
current_inds[cluster] += 1
new_cluster = np.argmin(cumul_third_var)
if new_cluster != cluster:
break
return assignements, cumul_third_var
def assign_points_with_kmeans(points, centroids, assignements):
new_assignements = np.array(assignements, copy=True)
count = -1
for asg in assignements:
count += 1
if asg > -1:
continue
pt = points[count, :]
distances = np.sqrt(((pt - centroids) ** 2).sum(axis=1))
centroid = np.argmin(distances)
new_assignements[count] = centroid
return new_assignements
def move_centroids(points, labels):
centroids = np.zeros((K, 2), dtype=float)
for k in range(0, K):
centroids[k] = points[assignements == k].mean(axis=0)
return centroids
rgba_colors = np.zeros((third_var.size, 4))
rgba_colors[:, 0] = 1.0
rgba_colors[:, 3] = 0.1 + (third_var / max(third_var))/1.12
plt.figure(1, figsize=(14, 14))
plt.title("Three blobs", fontsize='small')
plt.scatter(points[:, 0], points[:, 1], marker='o', c=rgba_colors)
# Initialize centroids
centroids = np.random.random((K, 2)) * 10
plt.scatter(centroids[:, 0], centroids[:, 1], marker='X', color='red')
# Step 1 : order points by distance to centroid :
inds, dists = dist2centroids(points, centroids)
# Check if clustering is theoriticaly possible :
tv_sum = third_var.sum()
tv_max = third_var.max()
if (tv_max > 1 / 3 * tv_sum):
print("No solution to the clustering problem !\n")
print("For one point : third variable is too high.")
sys.exit(0)
stop_criter_eps = 0.001
epsilon = 100000
prev_cumdist = 100000
plt.figure(2, figsize=(14, 14))
ln, = plt.plot([])
plt.ion()
plt.show()
while epsilon > stop_criter_eps:
# Modified kmeans assignment :
assignements, cumul_third_var = assign_points_with_constraints(inds, dists, third_var, accept_thresh)
# Kmeans on remaining points :
assignements = assign_points_with_kmeans(points, centroids, assignements)
centroids = move_centroids(points, assignements)
inds, dists = dist2centroids(points, centroids)
epsilon = np.abs(prev_cumdist - dists.sum().sum())
print("Delta on error :", epsilon)
prev_cumdist = dists.sum().sum()
plt.clf()
plt.title("Current Assignements", fontsize='small')
plt.scatter(points[:, 0], points[:, 1], marker='o', c=assignements)
plt.scatter(centroids[:, 0], centroids[:, 1], marker='o', color='red', linewidths=10)
plt.text(0,0,"THRESHOLD T = "+str(accept_thresh), va='top', ha='left', color="red", fontsize='x-large')
for k in range(0, K):
plt.text(centroids[k, 0], centroids[k, 1] + 0.7, "Ci = "+str(cumul_third_var[k]))
plt.show()
plt.pause(1)
改进：
- 使用第三个变量的分布进行赋值。
- 管理算法的分歧
- 更好的初始化 (kmeans++)