Как найти похожий шаблон вместе с отсутствующими объектами для больших данных? - PullRequest
Новая
       24

Как найти похожий шаблон вместе с отсутствующими объектами для больших данных?

0 голосов
/ 02 октября 2018

Я хочу найти определенный тип данных шаблона в списке данных вместе с отсутствующими объектами.Например, у меня есть следующие данные пользователя: 

User 1: 123 254 225 367 125 745 587
User 2: 333 444 225 123 254
User 3: 777 451 225 745 254 458
User 4: 111 222 333 444 555 666 777 888

И у меня есть шаблон поиска: 

254 225 125 587 745

Мне нужно найти этот шаблон по пользовательским данным независимо от ихпорядок появления и предоставления результатов следующим образом: 

User 1: 
User 2: 125 587 745
User 3: 125 587
User 4: 254 225 125 587 745

Числа в результате обозначают отсутствующие объекты для шаблона.

Я попытался реализовать алгоритм Apriori и FP-Growth, чтобы найти шаблон,но это не сработало, как ожидалось.Кроме того, размер данных очень велик, просто создание графика или дерева шаблонов заняло слишком много времени.Приведенные выше данные являются только примерными данными.Мне нужно выполнить этот анализ для нескольких тысяч пользовательских данных.

Какой может быть лучший подход для достижения этой цели?

Ответы [ 3 ]

0 голосов
/ 02 октября 2018

Вот как я мог бы сделать это на чистом Python.

Сложность по времени составляет O(um+n), где m - размер шаблона поиска, u - количество пользователей во входном дикте.и n - это размер входного диктанта.Для сравнительно небольших шаблонов поиска, описанных в определении проблемы, этот метод эффективен O(n). 

# Inputs
userDict = {
  'User 1': [123, 254, 225, 367, 125, 745, 587],
  'User 2': [333, 444, 225, 123, 254],
  'User 3': [777, 451, 225, 745, 254, 458],
  'User 4': [111, 222, 333, 444, 555, 666, 777, 888]
}

filterList = [254, 225, 125, 587, 745]

# Filter a dictionary of lists based on a search pattern
# Returns for each value in the dictionary, the elements from the search pattern
# which were not found in the list
#
def filterLists(inputDict, filterList):
  # Use a Set for the O(1) lookup
  filterSet = set(filterList)
  res = {}
  for key, vals in inputDict.items():
    # Creating a Set from a list of size n is O(n)
    # Set difference is O(size of the leftmost set)
    # Assuming the search pattern is shorter than the average User list,
    # this gives us effectively O(n)
    res[key] = list(filterSet - set(vals))
  return res

print(filterLists(userDict, filterList))

По сути, не переусердствуйте, алгоритмы Apriori и FP-Growth предназначены для другого классапроблемы с этим.Здесь вы в основном реализуете фильтр или сито, и поскольку ваши входные данные не структурированы и не упорядочены, вы действительно не можете прочитать каждое целое число хотя бы один раз, а это означает, что вы не можете получить скорость быстрее, чем O (n).

Итак, в моем коде я просто делаю пару операций над множествами за O (n) и возвращаю вывод.Нет необходимости в более сложных или умных представлениях.Вы можете добиться большего успеха, чем мой код, с небольшими изменениями, но не асимптотически лучше в общем случае.

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

0 голосов
/ 03 октября 2018

Используя словарь пользователей и контрольный список, это можно сделать, используя понимание словаря 

users = {
  'User 1': [123, 254, 225, 367, 125, 745, 587],
  'User 2': [333, 444, 225, 123, 254],
  'User 3': [777, 451, 225, 745, 254, 458],
  'User 4': [111, 222, 333, 444, 555, 666, 777, 888]
}

check = [254, 225, 125, 587, 745]
res = {k: [i for i in check if i not in users[k]] for k in users}

{'User 1': [], 'User 2': [125, 587, 745], 'User 3': [125, 587], 'User 4': [254, 225, 125, 587, 745]}
0 голосов
/ 02 октября 2018

Вот то, что работает для меня (но, возможно, это не самое эффективное решение):

Я полагаю, вы можете как-то преобразовать свой вклад в dict формы: 

d = {'User 1': [123, 254, 225, 367, 125, 745, 587],
     'User 2': [333, 444, 225, 123 ,254], ...}

Теперь, с данным шаблоном 

pattern = [254, 225, 125, 587, 745]

давайте создадим второй dict, который содержит вывод: 

d_out = {}
for key in d.keys():
    d_out[key] = []
    for value in pattern:
        d_out[key].append(value in d[key])

Производительность может быть не оптимальной, если ваш список шаблонов большой (потому чтоцикла), он должен быть более или менее независимым от размера пользовательских данных.

Теперь я беру pattern в качестве маски и использую собственную версию функции itertools.compress, чтобы получитьрезультат (функция вызвала ошибку на моем компьютере, и я не смог использовать ее напрямую, извините): 

for key in d.keys():
    print(key, [data for data, mask in zip(pattern, d_out[key]) if not mask])

, что приводит к выводу: 

User 1 []
User 2 [125, 587, 745]

Может быть, это то, что вы можетеначать с.

...