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

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"，因为这会产生与 [=41 相同的二进制拆分=] 在 left 和 "bc" 在 right）。每个拆分中的顺序也无关紧要（例如 "ad" 与拆分一侧的 "da" 相同）。

当前尝试

我忘记了确切的术语，但我认为这是某种形式的 combination/permutation 问题。我知道这不是我想要的动力装置。我能找到的最接近我的问题是链接 .

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

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

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

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

Answer 1

我会使用 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')

Answer 2

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

事实上，如果您 generate the powerset of your string in shortlex order，您基本上可以将功率集对折以产生所需的分区。

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')

这也表明对于大小为 n 的集合，有 (2^n - 2) / 2) = 2^(n - 1) - 1) 个大小为 2 的分区。

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

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

Find All Binary Splits of a Nominal Attribute

python

combinations

split

permutation

decision-tree

问题

当前尝试