Python 中具有自定义距离函数的聚类算法

Question

我遇到了一个聚类问题，我认为它需要一个直观的距离函数。每个实例都有一个 x, y 坐标，但也有一组描述它的属性（每个实例的数量不同）。理想情况下，可以将 pythonobjects（class 的实例）传递给它，并根据它们的内容任意比较它们。

我想将距离表示为 x、y 值和类似 jaccard 指数的欧氏距离的加权和，以衡量其他属性的集合重叠。类似于：

dist = (euclidean(x1, y1, x2, y2) * 0.6) + (1-jaccard(attrs1, attrs2) * 0.4)

我发现的大多数聚类算法和实现都将实例特征转换为数字。例如，在 sklearn 中使用 dbscan，要执行我的距离函数，我需要以某种方式将数字转换回原始表示形式。

如果可以使用可以以任意方式比较实例的距离函数进行聚类，那就太好了。例如，想象一个欧几里德距离函数，如果对象与另一个非空间特征匹配，它将评估对象是否更近。

def dist(ins1, ins2):
     euc = euclidean(ins1.x, ins1.y, ins2.x, ins2.y)
     if ins1.feature1 == ins2.feature1:
          euc = euc * 0.9
     return euc

有适合这个的方法吗？如果不必预先设置集群的数量也很好（但这对我来说并不重要）。

Answer 1

实际上，几乎所有的聚类算法（除了用于 k-means，它需要数字来计算 mean，显然）与任意距离函数一起使用。

在 sklearn 中，大多数算法接受 metric="precomputed" 和 距离矩阵 而不是原始输入数据。请更仔细地检查文档。例如 DBSCAN:

If metric is “precomputed”, X is assumed to be a distance matrix and must be square.

你失去的是通过索引加速某些算法的能力。计算距离矩阵是 O(n^2)，因此您的算法不能比这更快。在 sklearn 中，您需要修改 sklearn Cython 代码以添加新的距离函数（不幸的是，使用 pyfunc 会产生非常糟糕的性能）。 Java 工具，例如 ELKI can be extended with little overhead，因为 Java 的即时编译器对此进行了很好的优化。如果你的距离是 metric 那么许多索引可以用于加速例如DBSCAN.

Python 中具有自定义距离函数的聚类算法

Clustering algorithms with custom distance function in Python

python

cluster-analysis