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

Вопрос

Я пытаюсь построить двоичный классификатор дерева решений в 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) непустые элементы упорядоченного силового набора и сопоставить каждое подмножество с соответствующим разделом.

  • Размещение данных в соответствующих именах полей в файле CSV Использование Python
  • Python: Разделить массив NumPy на основе значений в массиве
  • Как разобрать вход и присвоить разные значения разделительной строке
  • разделил серию Pandas без мультииндекса
  • Разделение списка словарей на несколько списков словарей
  • регулярное выражение или другой способ получения данных из строки с переменной записью
  • что означает разделение python (r ', "')?
  • Чтение файла .txt по строкам в Python
  •  
    Interesting Posts for Van-Lav

    Скопируйте все значения в столбце в новый столбец в кадре данных pandas

    Проблема преобразования Python UTF-8

    Истинная приватность в Python

    Как написать вывод в том же месте на консоли?

    В сценариях оболочки Windows (cmd.exe) как вы назначаете stdout программы переменной окружения?

    Django: заблокировать подключение к Интернету для тестирования

    Django не может получить доступ к raw_post_data

    Все текущие и средние дни в диапазоне дат: есть ли более питонический путь?

    Создание большой таблицы сначала с вложенными заголовками столбцов и получение рендеринга латекса для обертывания текста заголовка

    Как сделать копию модуля python во время выполнения?

    Как установить инструмент Python для Visual Studio 2015?

    Как заменить отрицательные числа в кадре данных Pandas на ноль

    DataFrame.interpolate () экстраполирует данные за отсутствующие данные

    Как контролировать приложения, открытые или запущенные в linux / tcl / python?

    Ubuntu 11.10 + Ошибка Bash + Python + Неверная установка python

    Python - лучший язык программирования в мире.