c# - 创建对象的可比较且灵活的指纹

Question

我的情况

假设我有数千个对象，在这个例子中可能是电影。

我用很多不同的方式解析这些电影，收集每个电影的参数、关键字和统计数据。让我们称它们为键。我还为每个键分配了一个权重，范围从 0 到 1，具体取决于频率、相关性、强度、分数等。

例如，这里是电影 的几个键和权重世界末日 :

"Armageddon"
------------------
disaster       0.8
bruce willis   1.0
metascore      0.2
imdb score     0.4
asteroid       1.0
action         0.8
adventure      0.9
...            ...

可能有几千个这样的键和权重，为了清楚起见，这是另一部电影:

"The Fast and the Furious"
------------------
disaster       0.1
bruce willis   0.0
metascore      0.5
imdb score     0.6
asteroid       0.0
action         0.9
adventure      0.6
...            ...

我称之为电影的指纹，我想用它们在我的数据库中找到类似的电影。

我还想象可以插入电影以外的内容，例如文章或 Facebook 个人资料，并根据需要为其分配指纹。但这不应该影响我的问题。

我的问题

所以我已经走了这么远，但现在是我觉得棘手的部分。我想把上面的指纹变成易于比较和快速的东西。我尝试创建一个数组，其中索引 0 = disaster , 1 = bruce willis , 2 = metascore它们的值是重量。

我上面的两部电影的结果是这样的:

[ 0.8 , 1.0 , 0.2 , ... ]
[ 0.1 , 0.0 , 0.5 , ... ]

我尝试以不同的方式进行比较，只需乘以:

public double CompareFingerprints(double[] f1, double[] f2)
{
    double result = 0;

    if (f1.Length == f2.Length)
    {
        for (int i = 0; i < f1.Length; i++)
        {
            result += f1[i] * f2[i];
        }
    }

    return result;
}

或比较:

public double CompareFingerprints(double[] f1, double[] f2)
{
    double result = 0;

    if (f1.Length == f2.Length)
    {
        for (int i = 0; i < f1.Length; i++)
        {
            result += (1 - Math.Abs(f1[i] - f2[i])) / f1.Length;
        }
    }

    return result;
}

等等。

这些都返回了非常令人满意的结果，但它们都有一个共同的问题:它们非常适合比较两部电影，但实际上，当我想将单个电影指纹与数千个电影指纹进行比较时，这非常耗时并且感觉非常糟糕存储在我的 MSSQL 数据库中的指纹。特别是如果它应该与自动完成之类的东西一起使用，我想在几分之一秒内返回结果。

我的问题

我在这里有正确的方法还是我以一种非常低效的方式重新发明轮子？我希望我的问题对于 Stack Overflow 来说不是太宽泛，但我已经用下面的一些想法缩小了范围。

一些想法

我的指纹真的应该是一组权重吗？

我应该考虑散列我的指纹吗？它可能有助于指纹存储，但会使比较复杂化。通过使用 Locality-sensitive hashing，我发现了一些提示，这可能是一种有效的方法。 ，但数学有点超出我的能力范围。

我应该从 SQL 中获取所有数千部电影并使用结果，还是有办法将我的比较实现到 SQL 查询中并只返回前 100 次点击？

是 sparse data representation有什么要看的？ (感谢 Speed8ump)

我可以应用比较实际指纹或 OCR 时使用的方法吗？ ?

我听说有一种软件可以通过在数千篇已发表的论文和以前的测试中找到相似之处来检测考试作弊。他们使用什么方法？

干杯!

Answer 1

替代方案:特征向量

你所描述的是一个经典的特征向量。特征向量中的每一列描述一个类别。您的特征向量是一种特殊类型:它具有模糊数据，描述属于某个类别的程度。

处理此类向量时，应应用 fuzzy logic用于计算。使用模糊逻辑，您必须稍微尝试一下，直到找到与您的模糊运算相匹配的最佳数值算子。例如。模糊 AND 和 OR 可以用“min”和“max”或“*”和“+”甚至更复杂的指数运算来计算。您必须在良好的结果和快速计算之间找到适当的平衡。

不幸的是，模糊逻辑不太适合 SQL 数据库。如果采用模糊方式，则应考虑将所有数据保存在内存中并使用某种数值处理加速(处理器 SIMD 指令、CUDA/OpenCL、FPGA 等)。

替代方案:星形/雪花模式

另一种方法是构建经典的数据仓库方案。这非常适合现代 SQL 数据库。他们有很好的加速从中型数据仓库(最多几十亿条记录)中检索数据:

Materialized views (用于数据缩减)

(压缩)bitmap indexes (用于快速组合多个功能)

压缩存储(用于快速传输大量数据)

Pertitioning(根据数据的特征物理分离数据)

要使用这些优化，您必须首先准备好您的约会对象。

层次维度

您应该根据 snowflake schema 对您的功能进行分层排序。 .当数据以这种方式排序时(并且您有相应的索引)，数据库可以使用一组新的优化，例如 bitmap filtering .

以这种方式组织的数据应该主要是只读的。数据库需要的数据结构对于特殊类型的查询速度非常快，但更新成本也非常高。

一个例子是位图索引。位图索引是一个二进制矩阵。矩阵的行是数据库中一个表的行。列是此表中一行的可能值。当表中对应行中的列作为根据矩阵列的值时，矩阵中的条目为1。否则为 0。

位图索引将以压缩的二进制格式存储。对于数据库，通过使用快速二进制处理(通过使用处理器 SIMD 指令或什至 OpenCL/CUDA 等对二进制值进行 AND 或 OR 运算)组合多个位图索引非常容易。

有一种可以跨越多个表的特殊位图索引，称为位图连接索引。它们专为以雪花模式组织的数据而构建。

降维

您还应该使用降维来减少必须存储的特征数量。为此，您可以使用诸如 principal component analysis 之类的技术。 .有了这个，您可以将多个高度耦合的特征组合到一个人工特征中，并完全删除根本不会改变其值(value)的特征。

离散维度成员

对于模糊逻辑，使用浮点数很好。但是在数据仓库中存储数据时，减少到可能的值是一个好主意。位图索引和分区仅适用于有限数量的值。您可以使用分类算法来实现这一点，例如 self organizing feature maps或 particle swarm optimizations .

备选方案 3:混合方法

您可以轻松地将上述两种方法结合起来。您使用简洁的描述(更少的维度，更少的成员)将日期存储在数据仓库中。每个数据集都包含原始特征。当您从数据仓库中检索数据集时，您可以使用备选方案 1 中的技术对完整描述进行操作，例如根据当前的情况确定竞争的顶级候选人。