jjzjj

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

coder 2024-05-30 原文

我的情况

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

我用很多不同的方式解析这些电影,收集每个电影的参数、关键字和统计数据。让我们称它们为键。我还为每个键分配了一个权重,范围从 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 时使用的方法吗? ?
  • 我听说有一种软件可以通过在数千篇已发表的论文和以前的测试中找到相似之处来检测考试作弊。他们使用什么方法?

  • 干杯!

    最佳答案

    替代方案:特征向量

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

    处理此类向量时,应应用 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 mapsparticle swarm optimizations .

    备选方案 3:混合方法

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

    关于c# - 创建对象的可比较且灵活的指纹,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21622998/

    有关c# - 创建对象的可比较且灵活的指纹的更多相关文章

    1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法? - 2

      总的来说,我对ruby​​还比较陌生,我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础,我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

    2. ruby - 如何在 Ruby 中顺序创建 PI - 2

      出于纯粹的兴趣,我很好奇如何按顺序创建PI,而不是在过程结果之后生成数字,而是让数字在过程本身生成时显示。如果是这种情况,那么数字可以自行产生,我可以对以前看到的数字实现垃圾收集,从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法,类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

    3. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声? - 2

      关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题?更新问题,以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点?我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等),但我确实想创建一个输出文件。

    4. ruby-on-rails - 按天对 Mongoid 对象进行分组 - 2

      在控制台中反复尝试之后,我想到了这种方法,可以按发生日期对类似activerecord的(Mongoid)对象进行分组。我不确定这是完成此任务的最佳方法,但它确实有效。有没有人有更好的建议,或者这是一个很好的方法?#eventsisanarrayofactiverecord-likeobjectsthatincludeatimeattributeevents.map{|event|#converteventsarrayintoanarrayofhasheswiththedayofthemonthandtheevent{:number=>event.time.day,:event=>ev

    5. ruby - 使用 Vim Rails,您可以创建一个新的迁移文件并一次性打开它吗? - 2

      使用带有Rails插件的vim,您可以创建一个迁移文件,然后一次性打开该文件吗?textmate也可以这样吗? 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件,这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails,您可以创建一个新的迁移文件并一次性打开它吗?,我们在StackOverflow上找到一个类似的问题: https://sta

    6. ruby-on-rails - 无法使用 Rails 3.2 创建插件? - 2

      我对最新版本的Rails有疑问。我创建了一个新应用程序(railsnewMyProject),但我没有脚本/生成,只有脚本/rails,当我输入ruby./script/railsgeneratepluginmy_plugin"Couldnotfindgeneratorplugin.".你知道如何生成插件模板吗?没有这个命令可以创建插件吗?PS:我正在使用Rails3.2.1和ruby​​1.8.7[universal-darwin11.0] 最佳答案 随着Rails3.2.0的发布,插件生成器已经被移除。查看变更日志here.现在

    7. ruby - Ruby 的 Hash 在比较键时使用哪种相等性测试? - 2

      我有一个围绕一些对象的包装类,我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。

    8. ruby-on-rails - 如何验证非模型(甚至非对象)字段 - 2

      我有一个表单,其中有很多字段取自数组(而不是模型或对象)。我如何验证这些字段的存在?solve_problem_pathdo|f|%>... 最佳答案 创建一个简单的类来包装请求参数并使用ActiveModel::Validations。#definedsomewhere,atthesimplest:require'ostruct'classSolvetrue#youcouldevencheckthesolutionwithavalidatorvalidatedoerrors.add(:base,"WRONG!!!")unlesss

    9. ruby - 如何使用 RSpec::Core::RakeTask 创建 RSpec Rake 任务? - 2

      如何使用RSpec::Core::RakeTask初始化RSpecRake任务?require'rspec/core/rake_task'RSpec::Core::RakeTask.newdo|t|#whatdoIputinhere?endInitialize函数记录在http://rubydoc.info/github/rspec/rspec-core/RSpec/Core/RakeTask#initialize-instance_method没有很好的记录;它只是说:-(RakeTask)initialize(*args,&task_block)AnewinstanceofRake

    10. Ruby 写入和读取对象到文件 - 2

      好的,所以我的目标是轻松地将一些数据保存到磁盘以备后用。您如何简单地写入然后读取一个对象?所以如果我有一个简单的类classCattr_accessor:a,:bdefinitialize(a,b)@a,@b=a,bendend所以如果我从中非常快地制作一个objobj=C.new("foo","bar")#justgaveitsomerandomvalues然后我可以把它变成一个kindaidstring=obj.to_s#whichreturns""我终于可以将此字符串打印到文件或其他内容中。我的问题是,我该如何再次将这个id变回一个对象?我知道我可以自己挑选信息并制作一个接受该信

    随机推荐