二维矩阵:查找和删除属于其他列子集的列

Question

我有一个问题，我想识别和删除逻辑矩阵中作为其他列子集的列。 即 [1， 0， 1] 是 [1， 1， 1] 的子集; 但 [1， 1， 0] 和 [0， 1， 1] 都不是彼此的子集。我写了一段快速的代码来标识作为子集的列，它使用嵌套的 for 循环进行 （n^2-n）/2 检查。

import numpy as np
A = np.array([[1, 0, 0, 0, 0, 1],
              [0, 1, 1, 1, 1, 0],
              [1, 0, 1, 0, 1, 1],
              [1, 1, 0, 1, 0, 1],
              [1, 1, 0, 1, 0, 0],
              [1, 0, 0, 0, 0, 0],
              [0, 0, 1, 1, 1, 0],
              [0, 0, 1, 0, 1, 0]])
rows,cols = A.shape
columns = [True]*cols
for i in range(cols):
    for j in range(i+1,cols):
        diff = A[:,i]-A[:,j]
        if all(diff >= 0):
            print "%d is a subset of %d" % (j, i)
            columns[j] = False
        elif all(diff <= 0):
            print "%d is a subset of %d" % (i, j)
            columns[i] = False
B = A[:,columns]

解决方案应该是

>>> print B
[[1 0 0]
 [0 1 1]
 [1 1 0]
 [1 0 1]
 [1 0 1]
 [1 0 0]
 [0 1 1]
 [0 1 0]]

不过，对于大量矩阵，我相信有一种方法可以更快地做到这一点。一个想法是在我去的时候消除子集列，这样我就不会检查已知是子集的列。另一个想法是对此进行矢量化，因此不要进行 O（n^2） 操作。谢谢。

Answer 1

由于我实际处理的A矩阵是 5000x5000 并且稀疏，密度约为 4%，因此我决定尝试将稀疏矩阵方法与 Python 的"set"对象相结合。总的来说，它比我原来的解决方案快得多，但我觉得我从矩阵A到集合列表的过程D没有那么快。任何关于如何做得更好的想法都值得赞赏。

溶液

import numpy as np
A = np.array([[1, 0, 0, 0, 0, 1],
              [0, 1, 1, 1, 1, 0],
              [1, 0, 1, 0, 1, 1],
              [1, 1, 0, 1, 0, 1],
              [1, 1, 0, 1, 0, 0],
              [1, 0, 0, 0, 0, 0],
              [0, 0, 1, 1, 1, 0],
              [0, 0, 1, 0, 1, 0]])
rows,cols = A.shape
drops = np.zeros(cols).astype(bool)
# sparse nonzero elements
C = np.nonzero(A)
# create a list of sets containing the indices of non-zero elements of each column
D = [set() for j in range(cols)]
for i in range(len(C[0])):
    D[C[1][i]].add(C[0][i])
# find subsets, ignoring columns that are known to already be subsets
for i in range(cols):
    if drops[i]==True:
        continue
    col1 = D[i]
    for j in range(i+1,cols):
        col2 = D[j]
        if col2.issubset(col1):
            # I tried `if drops[j]==True: continue` here, but that was slower
            print "%d is a subset of %d" % (j, i)
            drops[j] = True
        elif col1.issubset(col2):
            print "%d is a subset of %d" % (i, j)
            drops[i] = True
            break
B = A[:, ~drops]
print B

Answer 2

这是使用NumPy broadcasting的另一种方法 -

A[:,~((np.triu(((A[:,:,None] - A[:,None,:])>=0).all(0),1)).any(0))]

下面列出了详细的注释解释 -

# Perform elementwise subtractions keeping the alignment along the columns
sub = A[:,:,None] - A[:,None,:]
# Look for >=0 subtractions as they indicate non-subset criteria
mask3D = sub>=0
# Check if all elements along each column satisfy that criteria giving us a 2D
# mask which represent the relationship between all columns against each other
# for the non subset criteria
mask2D = mask3D.all(0)
# Finally get the valid column mask by checking for all columns in the 2D mas
# that have at least one element in a column san the diagonal elements.
# Index into input array with it for the final output.
colmask = ~(np.triu(mask2D,1).any(0))
out = A[:,colmask]

Answer 3

当且仅当col1是col2的子集时，将子集定义为col1.dot(col1) == col1.dot(col2)

定义col1，当且仅当col1是col2的子集时，col2是相同的，反之亦然。

我把工作一分为二。 首先删除除一个等效列之外的所有列。 然后删除子集。

溶液

import numpy as np
def drop_duplicates(A):
    N = A.T.dot(A)
    D = np.diag(N)[:, None]
    drops = np.tril((N == D) & (N == D.T), -1).any(axis=1)
    return A[:, ~drops], drops
def drop_subsets(A):
    N = A.T.dot(A)
    drops = ((N == np.diag(N)).sum(axis=0) > 1)
    return A[:, ~drops], drops
def drop_strict(A):
    A1, d1 = drop_duplicates(A)
    A2, d2 = drop_subsets(A1)
    d1[~d1] = d2
    return A2, d1

A = np.array([[1, 0, 0, 0, 0, 1],
              [0, 1, 1, 1, 1, 0],
              [1, 0, 1, 0, 1, 1],
              [1, 1, 0, 1, 0, 1],
              [1, 1, 0, 1, 0, 0],
              [1, 0, 0, 0, 0, 0],
              [0, 0, 1, 1, 1, 0],
              [0, 0, 1, 0, 1, 0]])    
B, drops = drop_strict(A)

示范

print B
print
print drops
[[1 0 0]
 [0 1 1]
 [1 1 0]
 [1 0 1]
 [1 0 1]
 [1 0 0]
 [0 1 1]
 [0 1 0]]
[False  True False False  True  True]

解释

N = A.T.dot(A)是点积的每个组合的矩阵。 根据顶部子集的定义，这将派上用场。

def drop_duplicates(A):
    N = A.T.dot(A)
    D = np.diag(N)[:, None]
    # (N == D)[i, j] being True identifies A[:, i] as a subset
    # of A[:, j] if i < j.  The relationship is reversed if j < i.
    # If A[:, j] is subset of A[:, i] and vice versa, then we have
    # equivalent columns.  Taking the lower triangle ensures we
    # leave one.
    drops = np.tril((N == D) & (N == D.T), -1).any(axis=1)
    return A[:, ~drops], drops
def drop_subsets(A):
    N = A.T.dot(A)
    # without concern for removing equivalent columns, this
    # removes any column that has an off diagonal equal to the diagonal
    drops = ((N == np.diag(N)).sum(axis=0) > 1)
    return A[:, ~drops], drops