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

Question

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

Каждый Продукт может иметь много Сегмент строки (тысячи).Каждый сегмент имеет столбец position , который начинается с 1 для каждого продукта (1, 2, 3, 4, 5 и т. Д.), И столбец value , который может содержать любые значения, такие как (323,113, 5423,231, 873,42, 422,64, 763,1 и т. Д.).Данные доступны только для чтения.

Это может помочь представить продукт как песню, а сегменты - как набор музыкальных нот в песне.

Учитывая подмножество смежных сегментов, например фрагмент песни, я хотел бы определить потенциальные совпадения для продуктов.Однако из-за возможных ошибок в измерениях сегменты в подмножестве могут не соответствовать сегментам в базе данных точно .

Как определить кандидатов на продукт, найдясегменты продуктов, которые наиболее близко соответствуют подмножеству сегментов, которые я измерил?Кроме того, является ли база данных лучшим средством для данных такого типа?

-

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

Например, с учетом следующих значений:

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

Если порог совпадение разрешен для измерений с совпадениями 3 или более, измерение 2 может вернуть Продукт A, поскольку, хотя один из сегментов (78) далекопревышает порог близости, он по-прежнему соответствует 3 сегментам в правильном порядке и находится в пределах порога match .

Измерение 3 не соответствует продукту A, поскольку, хотя все измеренные сегменты существуют вфактические сегменты, они не находятся в пределах порогов близости или совпадения.

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

Answer 1

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

Answer 2

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

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

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

Answer 3

Если вы буквально берете пример своей песни, один из подходов состоит в том, чтобы свести ваш ввод к отпечатку битового вектора, а затем найти этот отпечаток в базе данных как точное совпадение. Вы можете увеличить шансы найти хорошее совпадение, извлекая несколько отпечатков из вашего ввода и / или пытаясь, например, все битовые векторы, которые находятся всего в 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. Также есть некоторая информация на http://www.music.mcgill.ca/~alastair/621/porter11fingerprint-summary.pdf.

Формат ввода, который вы описываете, предполагает, что вы могли бы что-то сделать с помощью метода случайной проекции, описанного в http://en.wikipedia.org/wiki/Locality_sensitive_hashing.

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

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)