Как сгенерировать k-itemset для априорного алгоритма в python

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

Как мне сделать эту функцию универсальной? Я имею в виду, что, передавая ключи словаря и количество элементов, необходимых в кортеже, алгоритм должен генерировать все возможные n-число (k + 1) подмножеств с использованием ключей. Я знаю, что объединение наборов возможно, но есть ли способ объединить кортежи, которые по сути являются ключами словаря?

# generate 2-itemset candidates by joining the 1-itemset candidates
def candidate_gen(keys):
    adict={}
    for i in keys:
        for j in keys:
            #if i != j and (j,i) not in adict:
            if j>i:
        #call join procedure which will generate f(k+1) keys
        #call has_infrequent_subset --> generates all possible k+1 itemsets and checks if k itemsets are present in f(k) keys
                adict[tuple([min(i,j),max(i,j)])] = 0
    return adict

Например, если мой исходный словарь выглядит так: {ключ, значение} --> значение - это частота

{'382': 1163, '298': 560, '248': 1087, '458': 720, 
 '118': 509,  '723': 528, '390': 1288}

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

{('390', '723'): 65, ('118', '298'): 20, ('298', '390'): 70, ('298', '458'): 35, 
 ('248', '382'): 88, ('248', '458'): 76, ('248', '723'): 26, ('382', '723'): 203,
 ('390', '458'): 33, ('118', '458'): 26, ('458', '723'): 26, ('248', '390'): 87,
 ('118', '248'): 54, ('298', '382'): 47, ('118', '723'): 41, ('382', '390'): 413,
 ('382', '458'): 57, ('248', '298'): 64, ('118', '382'): 40, ('298', '723'): 36, 
 ('118', '390'): 52}

Как я сгенерировал подмножества из 3-х элементов из приведенных выше ключей.


python tuples apriori
person prakyath j    schedule 23.10.2014    source источник
comment
Можете ли вы привести пример ввода и ожидаемого результата? Это сделает вашу проблему более понятной для всех.   -  person parchment    schedule 23.10.2014
comment
В вашем коде есть if j>i: adict[tuple([min(i,j),max(i,j)])] = 0, но он эквивалентен более простому if j>i: adict[i,j]=0.   -  person gboffi    schedule 23.10.2014
comment
В вашем коде keys являются строками, и сравнение j>i работает, если строки имеют одинаковую длину. Пожалуйста, попробуйте print('oh!' if '99'>'100' else 'ok.') в приглашении интерпретатора...   -  person gboffi    schedule 23.10.2014

Ответы (2)


arrow_upward
1
arrow_downward

Я предполагаю, что, учитывая вашу область, вы можете извлечь большую пользу из изучения itertoolsбиблиотека.

В вашем случае использования вы можете напрямую использовать itertools combinations или обернуть его во вспомогательную функцию.

from itertools import combinations
def ord_comb(l,n):
    return list(combinations(l,n))

#### TESTING ####
a = [1,2,3,4,5]
print(ord_comb(a,1))
print(ord_comb(a,5))
print(ord_comb(a,6))
print(ord_comb([],2))
print(ord_comb(a,3))

Вывод

[(1,), (2,), (3,), (4,), (5,)]
[(1, 2, 3, 4, 5)]
[]
[]
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]

Обратите внимание, что порядок элементов в n-uples зависит от порядка, который вы использовали в итерации, которую вы передаете combinations.

person gboffi    schedule 23.10.2014
comment
Спасибо за ответ. Это даст n-числовые комбинации в списке, содержащем a = [1,2,3,4,5] --> отдельные элементы. скажем, если бы мой ввод был = [(1,2), (3,4), (1,5)] и так далее. Как сгенерировать n-числовые комбинации над этим? например, вывод --> a= [(1,2,3),(1,2,4)...,(1,2,5)] и так далее. - person prakyath j; 23.10.2014
comment
@prakyathj, последний случай в моем коде TESTING, разве это не то, что вы ищете? В вашем примере кортежи уровня 2 были в количестве 21, то есть ((7x8)/2-7) все неповторяющиеся комбинации исходных 7 элементов, взятые 2 на 2, поэтому я пришел к выводу (без опыта в априорных алгоритмах), что вам нужны все отдельные, упорядоченные комбинации из 3-х предметов из исходных семи... Если для уровня 3 вам нужно что-то отличное от этих комбинаций, пожалуйста, скажите мне, потому что я не могу понять. - person gboffi; 23.10.2014
comment
@prakyathj Я хотел бы подчеркнуть, что последняя строка в поле с пометкой Вывод в моем ответе точно соответствует тому, что вы написали в условия неудовлетворенного требования, в конце вашего предыдущего комментария. - person gboffi; 24.10.2014

arrow_upward
0
arrow_downward

Этот?

In [12]: [(x, y) for x in keys for y in keys if y>x]
Out[12]: 
[('382', '723'),
 ('382', '458'),
 ('382', '390'),
 ('458', '723'),
 ('298', '382'),
 ('298', '723'),
 ('298', '458'),
 ('298', '390'),
 ('390', '723'),
 ('390', '458'),
 ('248', '382'),
 ('248', '723'),
 ('248', '458'),
 ('248', '298'),
 ('248', '390'),
 ('118', '382'),
 ('118', '723'),
 ('118', '458'),
 ('118', '298'),
 ('118', '390'),
 ('118', '248')]
person Marcin Fabrykowski    schedule 23.10.2014
comment
OP требует комбинации 3-го уровня, как в [ (x, y, z) for x in l for y in l for z in l if x < y < z], так что вы близки. Если ему нужны более глубокие уровни (4, ..., n) имхо лучше функцию типа itertools.combinations - person gboffi; 24.10.2014
comment
если ему нужен более глубокий уровень и гибкость, то да. код, который он вставил, генерирует наборы из 2 элементов - person Marcin Fabrykowski; 25.10.2014