Категоризация данных на основе подписи данных

Question

Допустим, у меня есть большая коллекция строк данных, где каждый элемент в строке является парой (ключ, значение):

1)    [(bird, "eagle"), (fish, "cod"),      ... , (soda, "coke")]
2)    [(bird, "lark"),  (fish, "bass"),     ...,  (soda, "pepsi")]
n)    ....
n+1)  [(bird, "robin"), (fish, "flounder"), ...,  (soda, "fanta")]

Я хотел бы иметь возможность выполнить некоторое вычисление, котороепозволил бы мне определить для новой строки, какая строка «наиболее похожа» на эту строку?

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

Я ищу решение в следующей форме.

• Функция, которая может взять строку и сгенерировать некоторое производное целое число для этой строки.Это возвращаемое целое число будет своего рода «подписью» строки.Важным свойством этой сигнатуры является то, что если две строки очень «похожи», они будут генерировать очень близкие целые числа, если строки очень «разные», они будут генерировать удаленные целые числа.Очевидно, что если бы они были идентичными строками, они бы сгенерировали одну и ту же сигнатуру.

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

• Когда у меня появится новая строка, я хочу знать, какая существующая строка в базе данных B наиболее похожа, я бы:

  1. Сгенерировать подпись для новой строки
  2. Двоичный поиск по отсортированному списку (подпись, индекс) в базе данных B для поиска совпадений
  3. Вернуть строку с наиболее близким соответствием (может быть идеальным)в базе данных Б.

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

Спасибо.

Answer 1

РЕДАКТИРОВАТЬ: Это мой первоначальный ответ, который мы будем называть Случай 1, где нет приоритет для клавиш

Вы не можете сделать это какотсортировано целое число, потому что это одномерное и ваши данные многомерны.Таким образом, «близость» в этом смысле не может быть установлена ​​на линии.

Ваш пример показывает птицу, рыбу и соду для всех 3 линий.Ключи зафиксированы и известны?Если это не так, то ваш первый шаг - хешировать ключи строки, чтобы установить строки с одинаковыми ключами.

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

Если N - количество пар ключ / значение:

Ближайшая неточная «близость» будет означать совпадение N-1 из N значений.Таким образом, вы генерируете еще N хэшей, каждый из которых пропускает одно из значений.Любые две строки, которые совпадают в этих хешах, имеют N-1 из N общих значений.

Следующая ближайшая неточная "близость" будет означать совпадение N-2 из N значений.Таким образом, вы генерируете более N хешей (я не могу понять двоичный файл так поздно), на этот раз каждый хеш пропускает комбинацию из двух значений.Любые две строки, совпадающие в этих хэшах, имеют общие значения N-2 из N.

Таким образом, вы можете видеть, куда это идет.В логическом крайнем случае вы получите 2 ^ N хешей, не очень вкусных, но я предполагаю, что вы не пойдете так далеко, потому что вы достигнете точки, где слишком мало совпадающих значений будет считаться «далеко», чтобы стоить рассматривать.

РЕДАКТИРОВАТЬ: Чтобы увидеть, как мы не можем избежать размерности, рассмотрим только два ключа со значениями 1-9.Разместите все возможные значения на графике.Мы видим, что {1,1} близко к {2,2}, но также что {5,6} близко к {6,7}.Итак, мы получаем мозговой штурм, мы говорим, ага!Я вычислю расстояние каждой точки от начала координат, используя теорему Пифагора!Это упростит обнаружение {1,1} и {2,2}.Но тогда две точки {1,10} и {10,1} получат одно и то же число, даже если они настолько далеко друг от друга, насколько они могут быть на графике.Итак, мы говорим, хорошо, мне нужно добавить угол для каждого.Две точки на одинаковом расстоянии различаются по их углу, две точки под одним и тем же углом различаются по их расстоянию.Но, конечно, теперь мы построили их в двух измерениях.

РЕДАКТИРОВАТЬ: Случай 2 будет, когда есть приоритет для клавиш, когда ключ 1 является более значимым, чем ключ2, что более важно, чем клавиша 3, и т. Д. В этом случае, если допустимые значения были AZ, вы бы соединили значения вместе, как если бы они были цифрами, чтобы получить сортируемое значение.ABC очень близко к ABD, но очень далеко от BBD.

Answer 2

Если у вас было много данных и вы хотели сделать этот хардкор, я бы предложил статистический метод, такой как PLSA или PSVM , который может извлечь идентифицирующие темы из текста и идентифицировать документы с похожей темой вероятностей.

Более простой, но менее точный способ сделать это - использовать Soundex , который доступен для многих языков. Вы можете сохранить soundex (это будет короткая строка, а не целое число, я боюсь) и искать точные совпадения с soundex, которые должны указывать на похожие строки.

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