7

这是一个更复杂的后续问题:查找顺序值的有效方法

每个产品可以有许多细分行(数千)。每个段都有每个产品从 1 开始的位置列(1、2、3、4、5 等)和一个可以包含任何值的列,例如(323.113、5423.231、873.42、422.64、763.1 等)。 )。数据是只读的。

将产品视为一首歌曲,将片段视为歌曲中的一组音符可能会有所帮助。

给定一个连续片段的子集,比如一首歌的片段,我想确定产品的潜在匹配。然而,由于测量中的潜在错误,子集中的段可能与数据库中的段完全匹配。

如何通过查找与我测量的细分子集最匹配的产品细分来识别候选产品?此外,数据库是此类数据的最佳媒介吗?

-

这里只是关于我将如何解决这个问题的一些想法。请不要将这些作为确切的要求。我对任何类型的算法都持开放态度,以使这项工作尽可能好。我在想需要有多个阈值变量来确定接近度。一种可能性可能是实现接近阈值和匹配阈值。

例如,给定这些值:

Product A contains these segments: 11,21,13,13,15.
Measurement 1 has captured: 20,14,14,15.
Measurement 2 has captured: 11,21,78,13.
Measurement 3 has captured: 15,13,21,13,11.

如果接近阈值允许测量的段高于或低于实际段 1,则测量 1 可能与产品 A 匹配,因为尽管许多段不完全匹配但它们在相对于实际值的接近阈值之内。

如果匹配阈值允许具有 3 个或更多匹配的测量,则测量 2 可能会返回产品 A,因为尽管其中一个段 (78) 远远超过邻近阈值,但它仍然以正确的顺序匹配 3 个段,因此在匹配阈值。

测量 3 与产品 A 不匹配,因为尽管所有测量的段都存在于实际段中,但它们不在邻近或匹配阈值内。

更新:其中一个答案要求我定义最接近匹配的意思。我不完全确定如何回答这个问题,但我会尝试通过继续歌曲类比来解释。假设这些片段代表录制歌曲的最大频率。如果我再次录制同一首歌曲,它会很相似,但由于背景噪音和其他录音设备的限制,一些频率会匹配,一些会接近,还有一些会相差甚远。在这种情况下,您将如何定义一个记录何时“匹配”另一个?这与我正在寻找在此问题中使用的相同类型的匹配逻辑。

4

4 回答 4

3

From the information you posted this can be solved with the edmond's blossom v perfect match algorithm. Either you can minimize or maximize the function and it will always find the best match. Maybe you can use a brute force solution with 2 loops. The wikipedia about edmond's matching algorithm: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

于 2011-11-10T14:08:31.420 回答
2

您需要提出“最接近匹配”的定义。我不知道这里的任何人可以如何帮助您,因为这里没有人会知道业务需求或数据的复杂性。你的两种方法听起来都很合理,但我不知道它们是否真的是。

至于数据库是否是这种数据的正确介质,我想说数据库可能是数据的完美介质,但它很像不是处理数据的正确介质。是否可能取决于您对“最接近匹配”的最终解决方案。

快速说明一下,SSIS 内置了一些模糊匹配功能,用于处理数据。不过我只玩过它,那是几年前的事了,所以我不知道它是否适用于你正在做的事情。

于 2011-11-07T20:48:35.097 回答
1

您能否采用将测量值与每个段位置逐个位置进行匹配并计算每个位置的差异的方法。然后将测量值沿一个位置滑动并计算差异。然后找出哪个幻灯片位置得分最低。对每个产品都这样做,然后您就知道测量结果与哪个产品最接近。

测试表和数据:

CREATE TABLE [dbo].[Segment]
(
    [ProductId] INT,
    [Position] INT,
    [Value] INT
)

INSERT  [dbo].[Segment]
VALUES  (1, 1, 300),
        (1, 2, 5000),
        (1, 3, 900),
        (1, 4, 400),
        (1, 5, 800),

        (2, 1, 400),
        (2, 2, 6000),
        (2, 3, 1000),
        (2, 4, 500),
        (2, 5, 900),

        (3, 1, 400),
        (3, 2, 5400),
        (3, 3, 900),
        (3, 4, 400),
        (3, 5, 900)

CREATE TABLE #Measurement
(
    [Position] INT,
    [Value] INT
)

INSERT  #Measurement
VALUES  (1, 5400),
        (2, 900),
        (3, 400)

如您所见,测量结果与第三个产品(的一个子集)完全匹配。

一些帮手:

CREATE TABLE #ProductSegmentCount
(
    [ProductId] INT,
    [SegmentCount] INT
)

INSERT #ProductSegmentCount
SELECT [ProductId], MAX([Position])
FROM [dbo].[Segment]
GROUP BY [ProductId]

DECLARE @MeasurementSegmentCount INT = (SELECT MAX([Position]) FROM #Measurement)

一个递归公用表表达式,用于显示按最接近匹配排序的产品:

;WITH [cteRecursive] AS
(
    SELECT  s.[ProductId],
            0 AS [RecursionId],
            m.[Position] AS [MeasurementPosition],
            s.[Position] AS [SegmentPosition],
            ABS(m.[Value] - s.[Value]) AS [Difference]
    FROM #Measurement m
    INNER JOIN [dbo].[Segment] s 
        ON m.[Position] = s.[Position]
    UNION ALL
    SELECT s.[ProductId],
            [RecursionId] + 1 AS [RecursionId],
            m.[Position],
            s.[Position],
            ABS(m.[Value] - s.[Value]) AS [Difference]
    FROM [cteRecursive] r
    INNER JOIN #Measurement m
        ON m.[Position] = r.[MeasurementPosition]
    INNER JOIN [dbo].[Segment] s 
        ON r.[ProductId] = s.[ProductId]
        AND m.[Position] + (r.[RecursionId]) = s.[Position]
    INNER JOIN #ProductSegmentCount psc
        ON s.[ProductId] = psc.[ProductId]
    WHERE [RecursionId] <= ABS(@MeasurementSegmentCount - psc.[SegmentCount])
)-- select * from [cteRecursive] where [ProductId] = 3 order by RecursionId, SegmentPosition
, [cteDifferences] AS
(
    SELECT [ProductId], [RecursionId], SUM([Difference]) AS [Difference]
    FROM [cteRecursive]
    GROUP BY [ProductId], [RecursionId]
)-- select * from [cteDifferences]
SELECT [ProductId], MIN([Difference]) AS [Difference]
FROM [cteDifferences] 
GROUP BY [ProductId]
ORDER BY MIN([Difference])
OPTION (MAXRECURSION 0)
于 2011-11-10T17:33:15.603 回答
1

如果您从字面上看您的歌曲示例,一种方法是将您的输入归结为位向量指纹,然后在数据库中查找该指纹​​作为精确匹配。您可以通过从您的输入中提取多个指纹和/或尝试例如距离您的指纹仅 1 或位错误的所有位向量来增加找到良好匹配的机会。

如果您可以访问 ACM 数字图书馆,您可以在 acm=1321038137_73cd62cf2b16cd73ca9070e7d5ea0744">http://delivery.acm.org/10.1145/1150000/1145312/ 的“Shazam 音乐识别服务”中阅读这种方法的描述p44-wang.pdf?ip=94.195.253.182&acc=ACTIVE%20SERVICE&CFID=53180383&CFTOKEN=41480065& acm =1321038137_73cd62cf2b16cd73ca9070e7d5ea0744. 还有一些信息在http://www.music.mcgill.ca/~alastair-sum621/porterport .pdf

您描述的输入格式表明您可以使用http://en.wikipedia.org/wiki/Locality_sensitive_hashing中描述的随机投影方法做一些事情。

要回答您的第二个问题,具体取决于位置对应的确切位置,您可以考虑将数字归结为由位或字符组成的哈希指纹,并将它们存储在文本搜索数据库中,例如 Apache Lucene。

于 2011-11-12T11:50:33.830 回答