1

一种复杂但简单的矩阵运算。我想找到并最大化行数，以便至少有x列，其中受这些行约束的矩阵都是一。

行本身不必是连续的，列也不必是连续的。并且矩阵假设所有行都至少有x一个，因此，我不会删除任何没有 minimum 的行x。

我最初的方法如下：取第一行。找到其中包含 1 的第一个“x”列。然后对于这些列，检查有多少行也有 1。跟踪我找到了多少行。从每一行开始执行此操作。

但是，这不起作用，因为即使对于第一行，我也需要考虑所有不同的列组合，这些组合仍然给我最小x的列，其中包含 1，而不仅仅是第一x列。

为此，计算时间迅速增加。有没有一种有效的方法来解决这个问题？

我正在尝试用python来做。

考虑以下示例，并且x = 2。

这没有解决方案，因为第 1、3、5 行最初都被消除了。然后，对于第 2 行和第 4 行，没有 3 列在两行中都有。

在此处输入图像描述

但在这里，第 2 行和第 4 行至少有 3 列全为 1。所以这有一个解决方案，最大行数是2。

在此处输入图像描述

4

1 回答 1

1

您似乎在描述的是关联规则学习问题的改写，例如可以使用 Apriori 算法解决。

这是一个快速制作的示例，展示了该算法的基础知识。它可能需要一些改进，并且不确定是否没有错误。

它也没有要求它必须找到所有不同的列组合，这些组合提供最少的“x”行。它只使用“x”来更快地过滤所有解决方案，并最终返回一个包含至少“x”行的最大列数的解决方案。

from operator import itemgetter, or_
from itertools import combinations, starmap
from collections import Counter
from math import factorial


class Apriori:

    def __init__(self, input, x):
        self.input = input
        self.cols = len(input[0])
        self.rows = len(input)
        self.x = x

    def _get_freq_combs(self, comb):
        return sum(map(lambda row:
                       sum([bool(e) for i, e in enumerate(row)
                            if i in comb]) // len(comb), self.input))

    def _make_new_combs(self, combs, comb_size):
        candidates = Counter(map(frozenset,
                                 starmap(or_, combinations(combs, 2))))
        possible_candidate_freq = factorial(comb_size) // factorial(2) \
            // factorial(comb_size - 2)
        for c, f in candidates.items():
            if f == possible_candidate_freq:
                yield c

    def solve(self):
        """Returns a list of sets with the most common items, at least x."""
        freq = [self._get_freq_combs([i]) for i in range(self.cols)]

        most_freq = [{ind} for ind in range(self.cols) if freq[ind] >= x]
        comb_size = 2
        while most_freq:
            old_freq = most_freq
            most_freq = [c for c in self._make_new_combs(most_freq, comb_size)
                         if self._get_freq_combs(c) >= x]
            comb_size += 1
        return old_freq


if __name__ == '__main__':
    input = [[1, 0, 1, 0],
             [0, 1, 1, 0],
             [0, 1, 1, 1],
             [0, 0, 0, 1]]
    x = 2
    apriori = Apriori(input, x)
    print(apriori.solve())
于 2019-03-05T22:58:56.150 回答