2-D Matrix: поиск и удаление столбцов, которые являются подмножествами других столбцов

Вот еще один подход, использующий 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] 

Определите подмножество как col1.dot(col1) == col1.dot(col2) тогда и только тогда, когда col1 является подмножеством col2

Определить col1 и col2 одинаковы, если и только если col1 является подмножеством col2 и наоборот.

Я разделил работу на две части. Сначала избавитесь от всех эквивалентных столбцов. Затем удалите подмножества.

Решение

 import numpy as np def drop_duplicates(A): N = ATdot(A) D = np.diag(N)[:, None] drops = np.tril((N == D) & (N == DT), -1).any(axis=1) return A[:, ~drops], drops def drop_subsets(A): N = ATdot(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 = ATdot(A) – матрица каждой комбинации точечного произведения. Для определения подмножества в верхней части это пригодится.

 def drop_duplicates(A): N = ATdot(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 == DT), -1).any(axis=1) return A[:, ~drops], drops def drop_subsets(A): N = ATdot(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 

Поскольку матрицы A с которыми я нахожусь, имеют 5000×5000 и разреженные с плотностью около 4%, я решил попробовать разреженный матричный подход в сочетании с «установленными» объектами Python. В целом это намного быстрее, чем мое оригинальное решение, но я чувствую, что мой процесс перехода от матрицы 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