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

Question

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

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

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

    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

有（至少）三大类索引：

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

对于你的情况，我会考虑倒排索引。如果您有很多属性，度量索引可能会起作用，但我怀疑它是否成立，因为您使用带有字符串的 POJO 来存储数据。

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

Answer 2

首先注意，SMC通常定义为similarity函数，而不是distance函数，而是1-SMC是通常的变换。只是不要混淆这两者。

对于简单的匹配系数，您可能希望为您的特定 POJO 数据类型构建自己的倒排索引。由于您的 POJO 设计（Dimension 听起来像一个非常糟糕的名字，顺便说一句。），这不能以通用、可重用的方式轻松实现。这将需要昂贵的自省，并且仍然需要定制：字符串匹配是否应该区分大小写？他们需要修剪吗？他们应该被代币化吗？

您的倒排索引可能会包含一系列特定于您的 POJO 的映射：

Map<String, DBIDs> by_app;
Map<String, DBIDs> by_node;
Map<String, DBIDs> by_cluster;
...

对于每个属性，您都会获得匹配的 DBID，并计算它们出现的频率。最常返回的 DBIDs 具有最高的 SMC（因此距离最短）。在某些时候，您可能会忘记计算无法再进入结果集中的候选人。查一查信息检索书这样的搜索是如何工作的。

如果每个属性的平均匹配数较低，则此类索引很有用。您可以通过位图索引压缩和此类技术进一步加快速度，但这可能不是必需的（在某些时候，构建在 Apache Lucene 等现有工具上来处理搜索可能很有吸引力）。

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

How to add index in Database using ELKI java API for Custom POJO with String type fields

java

cluster-analysis

dbscan

elki