Найти серию данных, используя неточные измерения (нечеткая логика)

Question

Это более сложный дополнительный вопрос: Эффективный способ поиска последовательных значений

Каждый продукт может иметь много строк сегмента (тысячи). Каждый сегмент имеет столбец положения, который начинается с 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, поскольку, хотя все измеренные сегменты существуют в реальных сегментах, они не находятся в пределах порогов близости или соответствия.

Обновление: один из ответов попросил меня определить, что я подразумеваю под наиболее близким соответствием. Я не совсем уверен, как на это ответить, но я постараюсь объяснить, продолжая аналогию с песней. Допустим, сегменты представляют максимальные частоты записанной песни. Если я снова запишу ту же песню, она будет похожей, но из-за фонового шума и других ограничений записывающего оборудования, некоторые частоты будут совпадать, некоторые будут близки, а некоторые - далеко. В этом сценарии, как бы вы определили, когда одна запись "соответствует" другой? Это та же логика сопоставления, которую я ищу для использования в этой задаче.

Answer 1

Если вы буквально берете пример своей песни, один из подходов состоит в том, чтобы свести ваш ввод к отпечатку битового вектора, а затем найти этот отпечаток в базе данных как точное совпадение. Вы можете увеличить шансы найти хорошее совпадение, извлекая несколько отпечатков из вашего ввода и / или пробуя, например, все битовые векторы, которые находятся всего в 1 или битовые ошибки от вашего отпечатка пальца.

Если у вас есть доступ к цифровой библиотеке ACM, вы можете прочитать описание такого подхода в "Службе распознавания музыки Shazam" по адресу acm = 1321038137_73cd62cf2b16cd73ca9070e7d5ea0744 "> http://delivery.acm.org/10.1145/1150000/1145312/ p44-wang.pdf?ip=94.195.253.182&acc=ACTIVE%20SERVICE&CFID=53180383&CFTOKEN=41480065&acm=1321038137_73cd62cf2b16cd73ca9070e7d5ea0744. There is also some information at http://www.music.mcgill.ca/~alastair/621/porter11fingerprint-summary.pdf.

The input format you describe suggests that you might be able to do something with the random projection method described in http://en.wikipedia.org/wiki/Locality_sensitive_hashing.

To answer your second question, depending on exactly what a position corresponds to, you might consider boiling down the numbers to hash fingerprints made up of bits or characters, and storing these in a text search database, such as Apache Lucene.

Answer 2

Из информации, которую вы разместили, это можно решить с помощью алгоритма Эдмонда Блоссом v Идеальное соответствие. Либо вы можете минимизировать или максимизировать функцию, и она всегда найдет наилучшее соответствие. Может быть, вы можете использовать решение грубой силы с 2 петлями. Википедия об алгоритме сопоставления Эдмонда: http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm

Answer 3

Вам нужно придумать определение для "наиболее близкого соответствия". Я не знаю, как кто-то здесь может помочь вам с этим, так как никто здесь не собирается знать бизнес-требования или тонкости данных. Оба ваших метода звучат разумно, но я понятия не имею, так ли это на самом деле или нет.

Что касается того, является ли база данных правильным носителем для такого рода данных, я бы сказал, что база данных, вероятно, является идеальным носителем для данных, но это очень похоже на неправильный носитель для обработки данных. Будет ли это возможно или нет, будет зависеть от вашего окончательного решения о том, что представляет собой "наиболее близкое соответствие".

В качестве краткого замечания, в SSIS встроены некоторые функции нечеткого сопоставления для обработки данных. Я только играл с этим, хотя это было пару лет назад, поэтому я не знаю, сработает ли это для того, что вы делаете или нет.

Answer 4

Не могли бы вы использовать подход сопоставления измерений для каждой позиции сегмента по позиции и расчета разницы для каждой позиции. Затем проведите измерения вдоль одной позиции и рассчитайте разницу. Затем найдите, какая позиция слайда набрала самую низкую разницу. Сделайте это для каждого продукта, и тогда вы узнаете, какой продукт соответствует измерениям.

Тестовые таблицы и данные:

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)