C# · 12月 31, 2021

c# – 创建对象的可比较和灵活的指纹

我的情况

说我有数以千计的对象,在这个例子中可以是电影.

我以许多不同的方式解析这些电影,收集参数,关键字和统计资料.我们叫他们的钥匙我还为每个键分配一个权重,范围从0到1,具体取决于频率,相关性,强度,分数等.

举个例子,这里有一些关键和重量的电影“世界末日”:

“Armageddon”——————disaster 0.8bruce willis 1.0Metascore 0.2imdb score 0.4asteroid 1.0action 0.8adventure 0.9… …

这些钥匙和重量可能有几千个,为了清楚起见,这是另一部电影:

“The Fast and the FurIoUs”——————disaster 0.1bruce willis 0.0Metascore 0.5imdb score 0.6asteroid 0.0action 0.9adventure 0.6… …

我称之为电影的指纹,我想用它们在我的数据库中查找类似的电影.

我也想象,如果我想要的话,可以插入电影以外的东西,如文章或Facebook个人资料,并为其指定一个指纹.但这不应该影响我的问题.

我的问题

所以我来了这么远,但现在我觉得很棘手.我想拿上面的指纹,把它变成一个容易比较和快速的东西.我尝试创建一个数组,其中索引0 =灾难,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时使用的方法吗?
>我听说有软件通过在数以千计的发表论文和以前的测试中发现相似之处来检测考试作弊.他们使用什么方法?

干杯!

解决方法 替代:特征向量

你正在描述的是一个经典的特征向量.特征向量中的每个列描述一个类别.您的特征向量是一种独特的类型:它具有模糊数据,描述属于某个类别的程度.

处理这样的向量时,应该应用fuzzy logic进行计算.使用模糊逻辑,你必须玩一下,直到找到最好的数字运算符来匹配你的模糊操作.例如.模糊AND和OR可以用“min”和“max”或“*”和“”甚至更复杂的指数运算来计算.您必须找到良好的结果和快速计算之间的平衡.

不幸的是,模糊逻辑不适合sql数据库.如果您采用模糊的方式,您应该考虑将所有数据保存在内存中,并使用某种数字处理加速(处理器SIMD指令,CUDA / OpenCL,FPGA等).

替代方案:星/雪花图

不同的方法是建立一个经典的数据仓库方案.这适合现代sql数据库.他们有很好的加速度从中型数据仓库检索数据(达几十亿条记录):

> Materialized views(用于数据简化)
>(压缩)bitmap indexes(用于快速组合多个功能)
>压缩存储(快速传输大量日期)
>授权(根据其特征对身体分隔数据)

要使用这些优化,您必须首先准备您的日期.

分层维度

您应该按照snowflake schema的顺序排列您的功能.当数据以这种方式排序(并且具有相应的索引)时,数据库可以使用一组新的优化. bitmap filtering.

以这种方式组织的数据应该主要是只读的.数据库将需要对于特殊类型的查询非常快的数据结构,但更新也是非常昂贵的.

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

位图索引将以压缩的二进制格式存储.对于数据库,通过使用快速二进制处理(通过对处理器SIMD指令中使用的二进制值进行或运算或甚至OpenCL / CUDA等)组合多个位图索引非常简单.

有特殊的位图索引可以跨越多个表,也就是所谓的位图连接索引.它们是针对以雪花模式组织的数据专门构建的.

尺寸缩小

您还应使用维度降低来减少必须存储的功能量.为此,您可以使用像principal component analysis这样的技术.通过这种技术,您可以将多个高度耦合的功能与一个人工功能相结合,完全删除不改变其价值的功能.

离散维度成员

对于模糊逻辑,使用浮点数很好.但是当将数据存储在数据仓库中时,最好减少到可能的值.位图索引和分区仅适用于有限数量的值.您可以使用分类算法达到此目的. self organizing feature maps或particle swarm optimizations.

备选方案3:混合方法

您可以轻松地组合上述两种方法.您将日期存储在数据仓库中,使用简明说明(维度较少,成员少).每个数据集包含原始特征.当您从数据仓库检索数据集时,您可以使用替代方案1中的技术来完整描述,例如,根据当前情况确定竞争的顶级候选人.