Поиск общих наборов в шумных данных - PullRequest
4 голосов
/ 17 декабря 2009

Контекст. Рассматривайте каждый набор в G как набор файлов (содержимого или хэшей MD5, а не имен), которые находятся на конкретном компьютере.

Предположим, у меня есть гигантский список наборов G и неизвестный мне список наборов H. Каждый отдельный набор I в G был создан путем объединения некоторого неизвестного числа наборов из списка H, а затем добавления и удаления неизвестного количества элементов.

Теперь я мог бы использовать другие данные для построения нескольких наборов в списке H. Тем не менее, я чувствую, что может быть какая-то техника, включающая байесовскую вероятность , чтобы сделать это. Например. что-то вроде: «Если нахождение X в наборе в G означает, что существует высокая вероятность также нахождения Y, то, вероятно, в H есть набор, содержащий как X, так и Y».

Редактировать: Моя цель - создать набор множеств, который с высокой вероятностью очень похож или равен H.

Есть мысли?

Пример использования:

Сжать G, заменив его куски кусочками H, например,

G[1]  = {1,2,3,5,6,7,9,10,11}
H[5]  = {1,2,3}
H[6]  = {5,6,7,8,9,10}
G[1]' = {H[5],H[6],-8,11}

Ответы [ 4 ]

3 голосов
/ 18 декабря 2009

Определите расстояние d (i, j) = 1 / (количество наборов в G, которые содержат и i, и j), а затем выполните кластерный анализ. (http://en.wikipedia.org/wiki/Cluster_analysis) Полученные кластеры - ваши кандидаты на элементы в H.

0 голосов
/ 18 декабря 2009

Как насчет детерминированного пути (если вы не хотите, чтобы множества вообще пересекались): A) Превратить множества в H в вершины с метками 1, 2, 3, ... size (H). Создайте полный [не] ориентированный граф между ними. Каждая вершина получает значение, равное количеству элементов / размеру. Б) Просмотрите все элементы x в наборах в H, создайте отображение x -> [x1, x2, ... xm] тогда и только тогда, когда x находится в H [xi]. Массив наборов подойдет. Это поможет вам найти перекрывающиеся наборы. C) Просмотрите все наборы в этом массиве для каждой пары x1, x2, которые находятся в одном наборе, - исключите два ребра между x1 и x2. D) В оставшемся графе только неперекрывающиеся множества (ну, их индексы в H). E) Теперь найдите непересекающийся путь в этом графе с наибольшим общим значением. Из этого вы можете восстановить список непересекающихся наборов с наибольшим охватом. Тривиально вычислить недостающие элементы. F) Если вы хотите минимизировать количество элементов оставшегося множества, то вычтите 0,5 из значения каждой вершины. Мы знаем, что 1 + 1 = 2, но 0,5 + 0,5 <1,5 - поэтому алгоритм предпочтет множество {a, b} над {a} и {b}. Это может быть не совсем то, что вы хотите, но это может истечь вас. </p>

0 голосов
/ 18 декабря 2009

Что ж, текущий метод ad-hoc, который кажется достаточно хорошим, выглядит следующим образом:

  • Удалите все элементы из всех G_x из 25 комплектов.
  • Создание отображения из элемента в набор и из набора в элемент.
  • Для каждого элемента E на карте элементов, выберите 3 комплекта и возьмите их пересечение. Сделайте две копии этого, A и B.
  • Для каждого набора S в карте набора, который не содержит E, удалите все элементы S из A или B (чередуйте их)
  • Добавить Union(A,B) к H
  • Удалите все элементы `Union (A, B) из элемента, чтобы установить карту (то есть не найти перекрывающихся наборов).
0 голосов
/ 18 декабря 2009

Существует множество не-мозговых ad hoc способов атаковать. Вот один.

Начните с отбора случайной выборки из G, скажем, 64 комплекта.

Для каждого файла в этих наборах создайте 64-разрядное целое число, сообщающее, в каких наборах оно появляется.

Группировать файлы по этому 64-битному значению; поэтому все файлы, которые всегда появляются вместе, попадают в одну группу. Найдите группу с максимальным ((количество файлов в группе - 1) & times; (количество битов, установленных в битовом векторе - 1)) и назовите это H [0].

Теперь отбросьте эту выборку назад и возьмите новую случайную выборку. Уменьшите его как можно больше, используя H [0], который вы уже определили. Затем примените тот же алгоритм, чтобы найти H [1]. Полоскание. Повторите.

Остановитесь, когда дополнительные H больше не помогут вам сжать наборы.

Чтобы улучшить этот алгоритм:

  • Вы можете легко выбрать немного другой показатель благости групп, который продвигает группы с множеством соседних соседей - файлы, которые появляются в почти того же набора наборов.
  • Вы также можете довольно легко проверить существующие H на случайных выборках из G, чтобы увидеть, есть ли файлы, которые вы должны рассмотреть, добавляя или удаляя.
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...