Блог

У меня есть python dict , показанный ниже:

 d = {
    'AAA':['a', 'b', 'c'],
    'BBB':['b', 'c', 'd'],
    'CCC':['d', 'e', 'f', 'h', 'x'],
    'DDD':['d', 'f', 'g'],
    'EEE':['g','d','h','o']
}
  

dict Значением являются элементы.

Я хочу, чтобы группа элементов охватывала все dict ключи.

т.е. ('b', 'c') группа существует в AAA и BBB . Таким образом, эта группа может охватывать AAA и BBB .

один из возможных результатов, как показано ниже.

 {('b', 'c'): ['AAA', 'BBB'],
 ('d', 'f'): ['CCC', 'DDD'],
 ('d', 'g'): ['EEE', 'DDD'],}
  

Все AAA , BBB CCC , DDD EEE , ('b', 'c') ('d', 'f') могут быть покрыты ('d', 'g') , ,, и,,.

Может работать алгоритм FP-Growth и Apriori. Я пробовал FP-Growth , как показано ниже, но все еще не могу получить такой результат.

 import pyfpgrowth

d = [
    ['a', 'b', 'c'],
    ['b', 'c', 'd'],
    ['d', 'e', 'f', 'h', 'x'],
    ['d', 'f', 'g'],
    ['g','d','h','o']
]
#Use find_frequent_patterns to find patterns in baskets that occur over the support threshold:
patterns = pyfpgrowth.find_frequent_patterns(d, 2)
print(patterns)
  

Результат таков

 {('b',): 2,
 ('b', 'c'): 2,
 ('c',): 2,
 ('d',): 4,
 ('d', 'f'): 2,
 ('d', 'g'): 2,
 ('d', 'h'): 2,
 ('f',): 2,
 ('g',): 2,
 ('h',): 2}
  

FP-Growth и алгоритм Apriori не могут решить проблему напрямую. Помимо этого, их производительность невелика.

Есть ли у нас какой-либо алгоритм или библиотека для выполнения такой задачи?

Вот возможное решение с использованием pandas. Длина групп, содержащих ключи, может быть ограничена минимальным и максимальным значением.

 import pandas as pd

d = {
    'AAA':['a', 'b', 'c'],
    'BBB':['b', 'c', 'd'],
    'CCC':['d', 'e', 'f', 'h', 'x'],
    'DDD':['d', 'f', 'g'],
    'EEE':['g','d','h','o']
}


for k, i in d.items():
    df1 = pd.DataFrame(columns=list(i), index=[k])
    df1[:]=True
    try:
        df=df.append(df1, sort=True)
    except:
        df=df1.copy()

  

Просто чтобы знать, что здесь происходит, промежуточный фрейм данных df представляет собой таблицу, подобную этой:

     a    b    c    d    e    f    g    h    o    x
AAA True True True NaN  NaN  NaN  NaN  NaN  NaN  NaN
BBB NaN  True True True NaN  NaN  NaN  NaN  NaN  NaN
CCC NaN  NaN  NaN  True True True NaN  True NaN  True
DDD NaN  NaN  NaN  True NaN  True True NaN  NaN  NaN
EEE NaN  NaN  NaN  True NaN  NaN  True True True NaN
  

Затем вы транспонируете этот фрейм данных и извлекаете группы, как в приведенном ниже коде; вы можете установить ограничения на количество элементов, которые вы хотите в каждой группе ключей.
Нет ограничений на количество элементов, охватывающих каждую группу. Таким образом, группа ключей может быть покрыта одним элементом (результатами).
Это возможное решение, поскольку, если не указаны другие ограничения, существует множество других решений вашей проблемы.
Код также проверяет, все ли ключи охвачены решением с заданными ограничениями.

 # set min and max number of items in each tuple of keys
min = 2
max = 3

df=df.fillna(False)

dft=df.transpose()

dft['sum'] = dft[:].sum(axis=1)

dft1 = dft[(dft['sum']>=min) amp; (dft['sum']<=max)]
dft1 = dft1.drop('sum', axis=1)

g = lambda a,b:[x for x, y in zip(tuple(a), tuple(b)) if y == True]

c=dft1.columns
dft1['groups'] = dft1.apply(lambda x: g(c, x), axis=1)
dft1['groups'] = dft1['groups'].apply(tuple)

grouped=dft1.groupby('groups')

final = dict()
key_covered = []
for key, item in grouped:
    lkey = list(key)
    if not set(lkey).issubset(key_covered):
        final[key] = tuple(item.index)
        key_covered  = key

print('Result:')
for k,i in final.items():
    print(i, end=': ')
    print(k)

print('Keys covered')
print(key_covered)

# Check if result covers all keys
if not set(key_covered).issubset(d.keys()):
    print('Initial dict is not covered with this constrains')

  

При минимальном количестве элементов в каждой группе ключей, равном 2, и максимальном количестве 3, конечный результат будет:

 Result:
('b', 'c'): ('AAA', 'BBB')
('f',): ('CCC', 'DDD')
('h',): ('CCC', 'EEE')
Keys covered
['AAA', 'BBB', 'CCC', 'DDD', 'CCC', 'EEE']
  

Если минимальное количество элементов в каждой группе ключей равно 2, а максимальное число 4, конечный результат будет:

 Result:
('b', 'c'): ('AAA', 'BBB')
('d',): ('BBB', 'CCC', 'DDD', 'EEE')
Keys covered
['AAA', 'BBB', 'BBB', 'CCC', 'DDD', 'EEE']