cluster-analysis - 如何使用 ELKI java API 为具有字符串类型字段的自定义 POJO 在数据库中添加索引

Question

我正在使用 DBSCAN 使用 POJO 对一些分类数据进行聚类。我的类看起来像这样

public class Dimension {
    private String app;
    private String node;
    private String cluster;
 .............

我的所有字段都是字符串而不是整数或浮点，因为它们是离散/分类值。我的其余代码如下。

    final SimpleTypeInformation<Dimension> dimensionTypeInformation = new SimpleTypeInformation<>(Dimension.class);
    PrimitiveDistanceFunction<Dimension> dimensionPrimitiveDistanceFunction = new PrimitiveDistanceFunction<Dimension>() {
        public double distance(Dimension d1, Dimension d2) {
            return simpleMatchingCoefficient(d1, d2);
        }
        public SimpleTypeInformation<? super Dimension> getInputTypeRestriction() {
            return dimensionTypeInformation;
        }
        public boolean isSymmetric() {
            return true;
        }
        public boolean isMetric() {
            return true;
        }
        public <T extends Dimension> DistanceQuery<T> instantiate(Relation<T> relation) {
            return new PrimitiveDistanceQuery<>(relation, this);
        }
    };
    DatabaseConnection dbc = new DimensionDatabaseConnection(dimensionList);
    Database db = new StaticArrayDatabase(dbc, null);
    db.initialize();
    DBSCAN<Dimension> dbscan = new DBSCAN<>(dimensionPrimitiveDistanceFunction, 0.6, 20);
    Result result = dbscan.run(db);

现在，正如预期的那样，该代码对于小型数据集运行良好，但当我的数据集变大时，代码会变得非常非常慢。所以我想添加一个索引来加快这个过程。但我能想到的所有索引都需要我实现 NumberVector。但我的类(class)只有字符串而不是数字。在这种情况下我可以使用什么索引？我可以使用距离函数 double simpleMatchingCoefficient(Dimension d1, Dimension d2) 来创建 IndexFactory 吗？

提前致谢。

Answer 1

(至少)有三大类索引:

1. 基于坐标的索引，例如 k-d-tree 和 R-tree。这些对于密集的连续变量效果很好
2. 度量指标，要求距离函数满足三角不等式。这些可以适用于任何类型的数据，但可能仍然需要相当平滑的距离值分布(例如，它们对离散度量没有帮助，即 x=y 为 0，否则为 1)。
3. 倒排查找索引。它们主要用于文本搜索，并利用每个属性只有一小部分数据是相关的。这些对于高基数离散属性非常有效。

就您而言，我会考虑倒排索引。如果您有很多属性，则指标索引可能会起作用，但我怀疑这种情况是否成立，因为您使用带有字符串的 POJO 来存储数据。

当然，分析您的代码并检查是否可以改进距离函数的实现!例如。字符串驻留可能会有所帮助，它可以减少字符串与相等性测试的匹配时间，而不是比较每个字符......