[人工智能]【转载】有规模限制的聚类算法Python轮子

背景介绍

机器学习的聚类算法在很多场景中都有应用，比如用户群体的聚类，地址聚类等。但是，在实际问题中，我们的聚类问题常常是有类的规模限制的，比如我们需要创建几个等大的类，或者有最小类大小的限制等。

虽然在很多学习算法和初入机器学习的同学们看来，聚类相关算法是机器学习中无监督学习中常见的一种，但从另一个角度看，聚类其实是求解一个组合优化问题，属于NP-hard问题。

应用场景

• 员工/外卖员等任务分配：我们给员工分配具体的工作区域或者工作任务量。因为我们分配对象的任务是人，所以我们需要考虑人性，考虑任务量的公平。因此，可以考虑等大聚类获得不同的等大类的区域结果分配给员工。当然，我们考虑员工的能力差异，也可以考虑按能力比例进行区域的聚类。
• 前置仓的选取：我们知道电商的前置仓是要选取离消费者近的地方的，能够提高实效，提升服务质量。但是前置仓选取太多，或者面向消费者的需求点太少，这样会导致仓的成本太高。因此，有的时候是基于消费者需求空间分布进行聚类选点。从这个角度来说，我们可以考虑最小最大限制的聚类方式进行初步选点。
• 路径规划：路径规划中有一种启发式算法是Cluster-first-Route-second。我们要考虑同种车型的可服务的需求点是有限的，且一致的，所以在做Cluster的时候考虑有空间规模限制的聚类。
• 选址规划：类比路径规划，我们在做门店选址/工厂选址等问题的时候，也得考虑空间聚类问题选取候选点，也可以缩小问题求解的规模。
• 其它在生物/化学/工程实际问题中的一些应用。

Size Constrained Clustering轮子介绍

Github地址：

https://github.com/jingw2/size_constrained_clustering?github.com/jingw2/size_constrained_clustering

PyPI地址：

https://pypi.org/project/size-constrained-clustering/?pypi.org/project/size-constrained-clustering/

方法介绍

• Fuzzy C-means Algorithm: 和KMeans类似，不过利用了归属概率（membership probability）进行计算，而不是直接的0或者1
• Same Size Contrained KMeans Heuristics: 利用启发式的方法获取等大聚类结果
• Same Size Contrained KMeans Inspired by Minimum Cost Flow Problem：将聚类转换为分配问题，并用最小费用流的思路进行求解
• Minimum and Maximum Size Constrained KMeans Inspired by Minimum Cost Flow Problem：将聚类转换为分配问题，并用最小费用流的思路进行求解，加入最小和最大聚类规模限制
• Deterministic Annealling Algorithm: 输入目标每类规模比例，获得相应聚类规模的结果。
• Shrinkage Clustering: base algorithm and minimum size constraints：启发式缩减的方式获得聚类结果。

且支持聚类距离函数定义callback。由于现实问题，我们常常涉及的不是欧氏距离，而是经纬度距离等，因此本轮子支持自定义函数输入。

例子展示

初始化

# setup
from size_constrained_clustering import fcm, equal, minmax, shrinkage
# 默认都是欧式距离计算，可接受其它distance函数，比如haversine
from sklearn.metrics.pairwise import haversine_distances

Fuzzy C-means

n_samples = 2000
n_clusters = 4
centers = [(-5, -5), (0, 0), (5, 5), (7, 10)]
X, _ = make_blobs(n_samples=n_samples, n_features=2, cluster_std=1.0,
                    centers=centers, shuffle=False, random_state=42)
model = fcm.FCM(n_clusters)
# 如果使用别的distance function，如haversine distance
# model = fcm.FCM(n_clusters, distance_func=haversine_distances)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_

等大聚类

n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
# 使用minmax flow方式求解
model = equal.SameSizeKMeansMinCostFlow(n_clusters)
# 使用heuristics方法求解
model = equal.SameSizeKMeansHeuristics(n_clusters)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_

图中共2000个正态分布的点，聚成3类，分别有667，667和666个点。

最小和最大规模限制

n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
model = minmax.MinMaxKMeansMinCostFlow(n_clusters, size_min=400,   size_max=800)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_

(二维码自动识别)

获取结果聚类size分别为753, 645, 602。

Deterministic Annealing

n_samples = 2000
n_clusters = 3
X = np.random.rand(n_samples, 2)
# distribution 表明各cluster目标的比例
model = da.DeterministicAnnealing(n_clusters, distribution=[0.1, 0.6, 0.3])
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_

获取的结果cluster size分别为：1200，600和200。对应比例为0.6, 0.3和0.1。

Shrinkage Clustering

只能保证收敛到局部最优，且获取的结果不一定可用。

n_samples = 1000
n_clusters = 4
centers = [(-5, -5), (0, 0), (5, 5), (7, 10)]
X, _ = make_blobs(n_samples=n_samples, n_features=2, cluster_std=1.0, centers=centers, shuffle=False, random_state=42)


model = shrinkage.Shrinkage(n_clusters, size_min=100)
model.fit(X)
centers = model.cluster_centers_
labels = model.labels_

参考文献

• Clustering with Capacity and Size Constraints: A Deterministic Approach
• Deterministic Annealing, Clustering and Optimization
• Deterministic Annealing, Constrained Clustering, and Opthiieation
• Shrinkage Clustering
• Clustering with size constraints
• Data Clustering with Cluster Size Constraints Using a Modified k-means Algorithm
• KMeans Constrained Clustering Inspired by Minimum Cost Flow Problem
• Same Size Kmeans Heuristics Methods
• Google's Operations Research tools's?SimpleMinCostFlow
• Cluster KMeans Constrained