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

Question

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

我想将距离表示为 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除外，显然它需要数字来计算均值）都可以与任意距离函数一起使用。

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

如果度量是“预先计算的”，则假定 X 是距离矩阵并且必须是方阵。

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