1. 我认为许多通常使用度量的聚类算法实际上并不依赖于度量属性（除了交换性，但我认为你会在这里）。例如，DBSCAN 在一个点周围使用 epsilon-neighborhoods；里面没有什么特别说明三角不等式很重要。因此，您可能可以使用 DBSCAN，尽管您可能必须执行某种非标准空间索引才能在您的情况下进行有效的查找。您的 epsilon-neighborhood 版本可能是 sim > 1/epsilon 而不是相反。k-means 和相关算法的情况相同。

2. 你能从你的相似性中构建一个度量吗？一种可能性：dist(ei, ej) = min( sim(ei, ek) + sim(ek, ej) ) for all k ... 或者，您能否提供一个上限，使得 sim(ei, ej) < sim (ei, ek) + sim(ek, ej) + d，对于所有 k 和一些正常数 d？直观地说，大的 sim 值意味着更接近：1/sim 度量标准吗？那么 1/（sim + 常数）呢？所有 k 的 min( 1/sim(ei, ek) + 1/sim(ek, ej) ) 怎么样？（最后保证是一个指标，顺便说一句）

3. 度量的另一种构造是进行嵌入。作为第一步，您可以尝试映射您的点 ei -> xi，以使 xi 最小化 sum( abs( sim(ei, ej) - f( dist(xi, xj) ) ) )，以获得一些合适的函数 f 和度量dist。函数 f 将嵌入中的距离转换为类似相似的值；您必须进行一些实验，但 1/dist 或 exp^-dist 是很好的起点。您还必须尝试最好的xi 的维度。从那里，您可以在 xi 上使用常规聚类。这里的想法是，您几乎可以（在最佳拟合意义上）将嵌入中的距离转换为相似值，以便它们正确聚类。

4. 在使用预定义参数时，所有算法都有一些调整。DBSCAN 可以找到簇的数量，但是你仍然需要给它一些参数。一般来说，调整需要多次运行具有不同可调参数值的算法，以及一些评估聚类优度的函数（单独计算，由聚类算法本身提供，或者只是目测:) 如果您的数据不会改变，您可以调整一次，然后使用这些固定参数；如果它发生变化，那么您必须为每次运行进行调整。您可以通过调整每次运行，然后比较一次运行的参数在另一次运行中的效果，与专门为此调整的参数进行比较来发现这一点。

Alex 提出了许多好的观点，尽管我可能不得不对他暗示 DBSCAN 是这里使用的最佳聚类算法的暗示有所回击。根据您的实现，以及您是否使用加速索引（许多实现不使用），您的时间和空间复杂度都将是O(n2)，这远非理想。

就个人而言，我的首选聚类算法是 OpenOrd 用于赢者通吃的聚类，而 FLAME 用于模糊聚类。两种方法都对所使用的度量是相似性还是距离无关（特别是 FLAME 在两种结构中几乎相同）。Gephi 中 OpenOrd 的实现O(nlogn)比 Gephi 包中存在的任何其他聚类算法更具可扩展性。

另一方面，如果您正在寻找模糊聚类方法，则 FLAME 非常棒。虽然 FLAME 的复杂性有点难以确定，因为它是一个迭代过程，但它已被证明是次二次的，并且在运行速度上与 knn 相似。

DBSCAN（另见：Generalized DBSCAN）不需要距离。它所需要的只是一个二元决策。通常，人们会使用“距离< epsilon”，但没有人说您不能使用“similarity > epsilon”。不需要三角不等式等。

顾名思义，相似性传播使用相似性。

层次聚类，除了可能是 Ward 链接，不做任何假设。在许多实现中，当您有相似之处时，您可以只使用负距离，它会正常工作。因为只需要最小值、最大值和 <。

如果您的相似性是一个好的内核函数，内核 k-means 可以工作。将其视为在不同的向量空间中计算 k 均值，其中欧几里德距离对应于您的相似度函数。但是你需要知道k。

PAM（K-medoids）应该可以工作。将每个对象分配给最相似的中心点，然后选择具有最高平均相似度的对象作为新中心点......不需要三角不等式。

...可能还有更多。实际上有数百种聚类算法。大多数应该工作恕我直言。似乎很少有人真正需要度量属性。K-means 可能有最强烈的要求：它最小化方差（不是距离或相似性），并且您必须能够计算均值。

拓扑数据分析是一种为您描述的设置明确设计的方法。它不是全局距离度量，而是仅依赖于邻近度或邻域的局部度量。请参阅：拓扑和数据以及使用拓扑从复杂数据的形状中提取见解。您可以在 Ayasdi 的网站上找到更多资源。