python - 查找标称属性的所有二进制拆分

Question

问题

我正在尝试基于仅具有标称属性的数据集在 Python 中从头构建一个二元决策树分类器。

我坚持的一个步骤是找到所有可能的方法来计算名义属性的二元分割。例如，对于具有可能值 [a、b、c、d] 的属性，我正在寻找一种方法将它们分成两个数组，以便我们获得:

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

没有重复拆分(例如，我们不需要在 left 中使用“bc”，在right 中不需要“ad”，因为这会产生与“ad”相同的二进制拆分在 left 中，“bc”在 right 中)。每个拆分中的顺序也无关紧要(例如，“ad”在拆分的一侧与“da”相同)。

当前尝试

我想不出确切的术语，但我认为这是某种形式的组合/排列问题。我知道这不是我想要的动力装置。我能找到的与我的相似的最接近的问题是链接 here .

到目前为止，我已经开始了一个迭代过程:

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

循环仅遍历属性可能值(array)一半长度的原因是因为如果我们存储最多 array.length/2 值在 left 中，right 有 1 - (array.length/2) 值，涵盖所有可能的拆分。

此外，我听说过 itertools 库......所以也许有一种方法可以实现我所追求的目标？

Answer 1

仅供引用，您的二进制拆分也称为 partitions正好有 2 个部分。每个 2 分区完全由一个子集决定(分区的另一半​​是子集的补集)，因此与组合的关系。

事实上，如果你generate the powerset你的字符串在 shortlex order ，您基本上可以将 powerset 对折以产生所需的分区。

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)大小为 n 的集合的大小为 2 的分区。

显然，您不能将其用于大型序列，因为它需要同时实现(几乎)整个幂集。虽然，它确实提出了一种避免生成重复项的有效解决方案:枚举第一个 2^(n - 1) - 1) 有序幂集的非空元素，并将每个子集映射到其对应的分区.