Найти все двоичные разрывы номинального атрибута

Вопрос

Я пытаюсь построить двоичный классификатор дерева решений в Python с нуля на основе набора данных, который имеет только номинальные атрибуты.

Один шаг, на который я застрял, – найти все возможные способы вычисления двоичного разделения номинального атрибута. Например, для атрибута с возможными значениями [a, b, c, d] я ищу способ разделить их на два массива, которые мы получаем:

left right ---- ----- a bcd b acd c abd d abc ab cd ac bd ad bc 

без дублирования разделов (например, нам не нужно «bc» в left и «объявлении» right так как это приведет к тому же двоичному расщеплению, что и «ad» left и «bc» right ). Заказ в каждом расколе также не имеет значения (например, «объявление» совпадает с «да» на одной стороне раскола).

Текущая попытка

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

До сих пор я начал итеративную процедуру:

 for i in range(1, array.length / 2): for j in range(1, i): # stuck here 

Причина для цикла только через пол половины длины возможных значений атрибута ( array ) заключается в том, что если мы сохраняем до array.length / 2 в left , правая имеет значения 1 - (array.length / 2) , охватывающие все возможные расколы.

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

2 Solutions collect form web for “Найти все двоичные разрывы номинального атрибута”

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

 import itertools def binary_splits(seq): for result_indices in itertools.product((0,1), repeat=len(seq)): result = ([], []) for seq_index, result_index in enumerate(result_indices): result[result_index].append(seq[seq_index]) #skip results where one of the sides is empty if not result[0] or not result[1]: continue #convert from list to tuple so we can hash it later yield map(tuple, result) def binary_splits_no_dupes(seq): seen = set() for item in binary_splits(seq): key = tuple(sorted(item)) if key in seen: continue yield key seen.add(key) for left, right in binary_splits_no_dupes("abcd"): print left, right 

Результат:

 ('a', 'b', 'c') ('d',) ('a', 'b', 'd') ('c',) ('a', 'b') ('c', 'd') ('a', 'c', 'd') ('b',) ('a', 'c') ('b', 'd') ('a', 'd') ('b', 'c') ('a',) ('b', 'c', 'd') 

Для справки ваши двоичные расщепления также известны как разделы с ровно 2 частями. Каждый 2-раздел полностью определяется подмножеством (другая половина раздела является дополнением к подмножеству), следовательно, отношение к комбинациям.

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

 import itertools def bsplit(chars): "Returns a list of all unique 2-partitions." assert len(chars) >= 2 # first, we generate the powerset in shortlex order, # minus the empty set and its complement subsets = (itertools.combinations(chars, k) for k in range(1, len(chars))) subsets = itertools.chain.from_iterable(subsets) subsets = [''.join(sub) for sub in subsets] # then, we "fold" the set in half--pairing each subset # in the first half with its complement from the second half half = len(subsets) // 2 return list(zip(subsets[:half], reversed(subsets[half:]))) def test(*strings): for string in strings: for left, right in bsplit(string): print(left, right) print() test('ab', 'abc', 'abcd', 'abcde') 

Это также показывает, что существуют (2^n - 2) / 2) = 2^(n - 1) - 1) разбиения размера 2 для набора размера n .

Очевидно, что вы не можете использовать это для больших последовательностей, потому что он должен полностью реализовать весь комплект питания. Несмотря на это, оно предлагает эффективное решение, которое позволяет избежать генерации дубликатов: перечислить первые 2^(n - 1) - 1) непустые элементы упорядоченного силового набора и сопоставить каждое подмножество с соответствующим разделом.

  • Как отделить мои модели от django?
  • Python: Как именно вы можете взять строку, разделить ее, отменить ее и снова объединить?
  • Сплит CSV-файл с использованием Python показывает не все данные в Excel
  • Python: разделите строковое поле на 3 отдельных поля, используя Lambda
  • Python: Разделить массив NumPy на основе значений в массиве
  • Разделение строк на Python
  • Разделение кадра данных на несколько фреймов данных
  • Как разбить матрицу на 4 блока с помощью numpy?
  • Разделить один файл на несколько файлов на основе шаблона (разрез может возникать в строках)
  • Python: Разделить список в массиве
  • множественное разделение в строке с использованием регулярного выражения
  • Python - лучший язык программирования в мире.