保持给定的一组对分离的聚类算法

Question

我有一个聚类问题，我必须将一组

S

样本分成

C

簇，其中

C

已知。通常，我可以使用简单的 KMeans 聚类来执行聚类操作，效果很好。

让事情变得复杂的是，我有一组已知的样本对

D

，在任何情况下都不能分配到同一个集群。目前我没有使用这些信息，聚类仍然工作正常，但我想引入它来提高鲁棒性，因为它是免费解决我试图解决的问题的。

示例：

S

由 20 个样本组成，每个样本有 5 个特征，

C

为 3，

D

强制以下对

{(1, 3), (3, 5), (10, 19)}

位于不同的集群中。

我正在寻找 python3 中的解决方案，最好使用 numpy/sklearn/scipy。 您知道是否有一些开箱即用的聚类算法考虑了这种约束？我研究过 sklearn 但没有发现这样的东西。

Answer 1

这听起来就像半监督的带有成对约束的聚类。其中，无监督 k 均值聚类通过数据子集的成对约束通过（不完美）监督得到增强。在您的特定示例中，它是一个 cannot link 约束。此外，还可以添加 must-link 约束。

不幸的是，我在 Python 中遇到的大多数实现都相当脆弱。例如，Python 库

active-semi-supervised-clustering

允许添加

ml

（必须链接）和

cl

（无法链接）关系，正如您所描述的那样。代码是：

import numpy as np
from matplotlib import pyplot as plt
from active_semi_clustering.semi_supervised.pairwise_constraints import PCKMeans

# data
S = [[-0.2, -1.0], [3.3, 3.9], [-2.0, 0.6], [2.3, -0.8], [1.1, 1.9], [2.8, -0.3], [4.2, 2.6], [1.8, 6.8], [1.4, -0.7], [2.6, 1.8], [2.6, 5.4], [0.8, -0.6], [3.0, 1.4], [-0.6, -0.4], [0.3, -0.2], [0.8, -0.4], [4.8, 5.1], [2.4, 5.2], [2.3, 5.3], [0.9, 0.3], [2.8, 4.1], [1.4, -0.7], [2.7, 5.6], [0.8, 0.8], [1.9, 5.3], [2.3, 5.3], [2.1, 0.5], [3.1, 5.3], [2.3, 0.8], [-0.2, -0.0], [2.4, 0.0], [3.6, -0.5], [1.3, -0.4], [3.0, 4.6], [0.4, -0.1], [-2.3, -1.4], [-1.9, -1.9], [4.2, 5.4], [-1.3, -0.9], [2.7, 0.2], [1.9, 6.5], [2.8, -0.8], [0.0, -0.3], [3.2, 5.9], [1.7, 4.6], [2.3, -0.3], [2.9, 1.2], [3.5, 2.0], [1.2, 2.3], [2.0, 1.5], [4.2, 5.8], [0.7, -2.0], [-0.8, -0.9], [4.7, 0.7], [-1.2, -1.8], [3.5, 5.1], [2.6, 0.7], [1.1, 3.0], [1.9, 6.5], [2.5, 6.5], [2.2, -0.2], [-0.9, -0.3], [3.1, 4.1], [-0.7, -0.3], [4.1, 5.2], [2.6, 0.8], [4.0, 3.5], [4.2, 4.3], [3.1, 1.1], [0.9, -0.1], [-0.3, 1.2], [0.2, -0.8], [0.1, -1.1], [0.4, -1.1], [-0.1, -0.7]]
S = np.array([np.array(s) for s in S])

# no. of clusters
C = 3

# constraints (indices of points in S)
D = [(1, 3), (3, 5), (10, 19), (7, 11), (4, 6)]

# color plots
colDict = {0: '#fc6A03', 1 : 'green', 2 :'#006699'}

plt.title('Input Data ($S$)', fontsize=20)
plt.scatter(x=[s[0] for s in list(S)], y=[s[1] for s in list(S)], c='darkgrey')
plt.show()

# Naïve Clustering
clust = PCKMeans(n_clusters=C, max_iter=1000)
clust.fit(S, cl=[], ml=[])
plt.title('Naïve (unconstrained) k-Means', fontsize=18)
plt.scatter(x=[s[0] for s in list(S)], y=[s[1] for s in list(S)], c=[colDict[c] for c in clust.labels_])
plt.show()

# Constr. Clustering
const_clust = PCKMeans(n_clusters=C, max_iter=10000)
const_clust.fit(S, ml=[], cl=D)
plt.title('Constrained k-Means', fontsize=18)
plt.scatter(x=[s[0] for s in S.tolist()], y=[s[1] for s in S.tolist()], c=[colDict[c] for c in const_clust.labels_])
plt.show()

产生

虽然情节看起来不同，但检查是否确实满足无法链接约束会导致

[const_clust.labels_[d[0]] != const_clust.labels_[d[1]] for d in D]
>[True, False, True]

表示索引为

3

和

5

的点被分配了相同的簇标签。不好。然而，样本大小和数据点在特征空间中的分布似乎对此影响很大。当您将其应用于实际数据时，您可能不会看到任何不利影响。

不幸的是，存储库不允许设置种子（以使迭代估计过程可重复）并忽略通过

np.random.seed(567)

设置的种子。注意可重复性并多次重新运行代码。

其他存储库（例如

scikit-learn

）表明某些聚类例程可能允许约束，但没有表明如何做到这一点。

请注意，约束 k 均值聚类还有其他变体，例如其中成对约束不确定（请参阅此参考文献）或每个簇的数据点数量受到限制（请参阅此Python库）。

Answer 2

Here是COP-Kmeans算法的Python实现，支持must-link和cannot-link约束。

免责声明：我已经实现了这个库