在我的集合中给定对象的度量，我需要形成满足两个条件的聚类：
- 聚类中任何对象与其最远邻居之间的距离必须小于t1。
- 聚类中任何对象与其最近邻居之间的距离必须小于t2。
目前我使用的是具有覆盖度量函数（对于远距离对象为0）的凝聚聚类方法，但感觉不太合适。
回答：
方法1：SAT求解
对于n个对象，所有可能的聚类可以用一个对称的二进制矩阵{0, 1}^{n \times n}来描述。位置(i, j)处的元素描述了对象i是否与对象j在同一个聚类中。这意味着你将有
(n^2 + n)/2 - n = n^2 - n个二进制变量。在你的情况下将是224 985 000个变量。这很多。然而，如果你能将其简化为SAT求解问题，这仍然是可行的。我猜这取决于满足约束条件但仍不理想的聚类有多少。
现在你可以将其转化为布尔可满足性问题：
聚类中任何对象与其最远邻居之间的距离必须小于t1。
这个约束使得矩阵中的某些元素被设为0，因为它们相距太远。
聚类中任何对象与其最近邻居之间的距离必须小于t2。
我想你指的是聚类中的最近邻居。这意味着要么o不在任何聚类中（例如，如果o的索引为i，则对于所有j，(i, j) = 0），要么一组可预先计算的j中的一个必须为1。因此，对于索引为i的每个对象，你在这里会得到类似这样的约束
((i, 0) = 0 且 (i, 1) = 0 且 ... 且 (i,i)=1 且 ... 且 (i,n)=0) 或 ((i, k1)=1 或 (i, k2)=1 或 (i, k3)=1)其中dist(i, k_j) < t2。
现在你可以尝试简单地遍历许多解并找到最佳解（例如，轮廓系数），或者你可以尝试更复杂的方法。有关更多信息，请参阅约束优化。
方法2：DBSCAN
你可以使用DBSCAN（或该家族的其中一种算法），设置epsilon = t2。然后，如果有必要的话，如果聚类不满足第一个条件，就分割聚类。
