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

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个人资料,并为其指定指纹.但那不应该影响我的问题.

我的问题

所以我已经走到了这一步,但现在我觉得这部分很棘手.我想把上面的指纹变成容易比较和快速的东西.我尝试创建一个数组,其中index 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的广泛问题,但我已经通过下面的一些想法将其缩小了.

几个想法

• 我的指纹真的应该是一系列重量吗？
• 我应该考虑哈希指纹吗？它可能有助于指纹存储,但比较复杂.我发现一些提示,这可能是一种有效的方法,通过使用局部敏感的散列,但数学有点超出我的范围.
• 我应该从SQL中获取所有数千部电影并使用结果,还是有办法将我的比较实现到SQL查询中并且只返回前100个命中？
• 稀疏数据表示是否有待研究？(感谢Speed8ump)
• 我可以应用比较实际指纹或OCR时使用的方法吗？
• 我听说有软件可以通过发现成千上万篇论文和以前的测试中的相似性来检测考试作弊.他们使用什么方法？

干杯!

Answer 1

替代方案：特征向量

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

处理此类向量时，应应用模糊逻辑进行计算。对于模糊逻辑，您必须进行一些尝试，直到找到最适合您的模糊操作的数值运算符。例如，模糊AND和OR可以用“min”和“max”或者用“*”和“+”或者甚至用更复杂的指数运算来计算。您必须在良好结果和快速计算之间找到适当的平衡。

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

替代方案：星型/雪花模式

另一种方法是构建经典的数据仓库方案。这非常适合现代 SQL 数据库。它们可以很好地加速从中型数据仓库（最多数十亿条记录）中检索数据：

1. 物化视图（用于数据缩减）
2. （压缩）位图索引（用于快速组合多个功能）
3. 压缩存储（用于快速传输大量数据）
4. 划分（根据数据的特征在物理上分离数据）

要使用这些优化，您必须首先准备好日期。

层次维度

您应该根据雪花模式对功能进行分层排序。当数据以这种方式排序时（并且您有相应的索引），数据库可以使用一组新的优化，例如位图过滤。

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

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

位图索引将以压缩的二进制格式存储。对于数据库来说，通过使用快速二进制处理（通过使用处理器 SIMD 指令甚至 OpenCL/CUDA 等对二进制值进行 AND 或 OR 运算）可以非常轻松地组合多个位图索引。

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

降维

您还应该使用降维来减少必须存储的特征量。为此，您可以使用主成分分析等技术。通过这种方式，您可以将多个高度耦合的特征组合为一个人工特征，并完全删除根本不会改变其价值的特征。

离散维度成员

对于模糊逻辑，使用浮点数是很好的选择。但是，当将数据存储在数据仓库中时，最好减少到可能的值。位图索引和分区仅适用于有限数量的值。您可以使用分类算法来实现此目的，例如自组织特征图或粒子群优化。

替代方案 3：混合方法

您可以轻松地将上述两种方法结合起来。您使用压缩描述（更少的维度、更少的成员）将日期存储在数据仓库中。每个数据集都包含原始特征。当您从数据仓库检索数据集时，您可以使用替代方案 1 中的技术来操作完整的描述，例如根据当前上下文确定竞争的最佳候选者。