मेरे पास छवियों के नामों की एक सूची है और उनके लिए एक (दहलीज) समानता मैट्रिक्स है। समानता संबंध स्वतुल्य और सममित है, लेकिन आवश्यक सकर्मक नहीं है, अर्थात यदि image_i, image_j और image_k के समान है, तो यह आवश्यक नहीं है कि image_j और image_k समान हैं।

उदाहरण के लिए:

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

समानता मैट्रिक्स sm की व्याख्या इस प्रकार की जाती है: यदि sm[i, j] == 1 तो image_i और image_j समान हैं, अन्यथा वे समान नहीं हैं। यहां हम देखते हैं कि image_0, image_1 और image_2 के समान है, लेकिन image_1 और image_2 समान नहीं हैं (यह गैर-पारगमन का सिर्फ एक उदाहरण है) .

मैं अद्वितीय छवियों की अधिकतम संख्या रखना चाहता हूं (जो दिए गए sm मैट्रिक्स के अनुसार सभी जोड़ीदार गैर-समान हैं)। इस उदाहरण के लिए यह [image_2, image_3, image_4] या [image_1, image_2, image_3] होगा (आम तौर पर ऐसे कई उपसमुच्चय होते हैं लेकिन मुझे कोई फर्क नहीं पड़ता कि उन्हें तब तक रखना है जब तक वे अधिकतम लंबाई के हों)। मैं ऐसा करने का एक कुशल तरीका ढूंढ रहा हूं क्योंकि मेरे पास हजारों छवियां हैं।

संपादित करें: मेरा मूल समाधान निम्नलिखित था

np.array(images)[np.tril(sm).sum(0) == 1]

हालांकि इसकी गारंटी नहीं है कि यह एक अधिकतम लंबाई वाला सबसेट लौटाएगा। निम्नलिखित उदाहरण पर विचार करें:

sm = np.array([[1, 1, 0, 0, 0],
               [1, 1, 0, 0, 0],
               [0, 0, 1, 1, 0],
               [0, 0, 1, 1, 1],
               [0, 0, 0, 1, 1]])

यह समाधान ['image_1', 'image_4'] लौटाएगा, जबकि वांछित परिणाम ['image_0', 'image_2', 'image_4'] या ['image_1', 'image_2', 'image_4'] है।

अपडेट: कृपया मेरा उत्तर देखें जो ग्राफ़ सिद्धांत का उपयोग करके समस्या को अधिक विस्तार से बताता है। मैं अभी भी सुझावों के लिए खुला हूं क्योंकि मुझे हजारों छवियों की सूची के लिए परिणाम प्राप्त करने का एक उचित तेज़ तरीका नहीं मिला है।

2
Andreas K. 25 जिंदा 2020, 11:41

3 जवाब

सबसे बढ़िया उत्तर

थोड़ा और शोध करने के बाद, मैंने पाया कि यह ग्राफ सिद्धांत में तथाकथित अधिकतम स्वतंत्र सेट समस्या है, जो दुर्भाग्य से एनपी-हार्ड है।

एक स्वतंत्र सेट ग्राफ़ G का S, G के शीर्षों का एक उपसमुच्चय है, जैसे कि S में कोई भी शीर्ष एक दूसरे के निकट नहीं है। हमारे मामले में, हम एक अधिकतम स्वतंत्र समुच्चय (एमआईएस) की तलाश कर रहे हैं, यानी एक स्वतंत्र समुच्चय जिसमें अधिकतम संभव संख्या में शीर्ष हों।

ग्राफ़ और नेटवर्क के साथ काम करने के लिए कुछ पुस्तकालय हैं, जैसे कि igraph या NetworkX, जिनमें अधिकतम स्वतंत्र सेट खोजने के लिए कार्य हैं। मैं igraph का उपयोग कर समाप्त हुआ।

मेरी समस्या के लिए, हम छवियों को ग्राफ़ G के कोने और आसन्न मैट्रिक्स के रूप में "समानता मैट्रिक्स" के रूप में सोच सकते हैं:

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

# Adjacency matrix
adj = sm.copy()
np.fill_diagonal(adj, 0)

# Create the graph
import igraph
g = igraph.Graph.Adjacency(adj.tolist(), mode='UNDIRECTED')

enter image description here


# Find the maximum independent sets
g.largest_independent_vertex_sets()
[(1, 2, 3), (2, 3, 4)]

enter image description here


enter image description here


दुर्भाग्य से यह हजारों छवियों (कोने) के लिए बहुत धीमा है। तो मैं अभी भी इसे करने के तेज़ तरीके के सुझावों के लिए खुला हूं (शायद सभी एमआईएस खोजने के बजाय, बस एक ढूंढें)।

नोट: @Sergey (UPDATE#1) और @marke द्वारा प्रस्तावित समाधान हमेशा एक MIS नहीं लौटाते -- वे लालची अनुमानित एल्गोरिदम हैं जो एक को हटाते हैं अधिकतम डिग्री का शीर्ष जब तक कोई किनारा न रह जाए। इसे प्रदर्शित करने के लिए, निम्नलिखित उदाहरण पर विचार करें:

sm = np.array([[1, 1, 0, 0, 0, 1],
               [1, 1, 0, 1, 0, 0],
               [0, 0, 1, 1, 1, 0],
               [0, 1, 1, 1, 0, 0],
               [0, 0, 1, 0, 1, 1],
               [1, 0, 0, 0, 1, 1]])

दोनों समाधान [3, 5] लौटते हैं, लेकिन इस उदाहरण के लिए अधिकतम स्वतंत्र सेट दो हैं, [(0, 3, 4), (1, 2, 5)], जैसा कि igraph द्वारा सही पाया गया है। यह देखने के लिए कि ये समाधान एमआईएस को खोजने में विफल क्यों हैं, नीचे एक जीआईएफ है जो दिखाता है कि प्रत्येक पुनरावृत्ति पर कोने और किनारों को कैसे हटाया जाता है (जो कि np.argmax का "दुष्प्रभाव" है, जो कई घटनाओं के लिए पहली घटना को लौटाता है। अधिकतम मूल्य):

enter image description here

सर्गेई का समाधान (अद्यतन#2) काम करता प्रतीत होता है, हालांकि यह igraph के largest_independent_vertex_sets() की तुलना में बहुत धीमा है। गति तुलना के लिए आप लंबाई 100 के निम्नलिखित बेतरतीब ढंग से उत्पन्न समानता मैट्रिक्स का उपयोग कर सकते हैं:

a = np.random.randint(2, size=(100, 100))

# create a symmetric similarity matrix
sm = np.tril(a) + np.tril(a, -1).T  
np.fill_diagonal(sm, 1)  

# create adjacency matrix for igraph
adj = sm.copy()
np.fill_diagonal(adj, 0)

अपडेट: यह पता चला है कि हालांकि मेरे पास हजारों छवियां हैं - शिखर, किनारों की संख्या अपेक्षाकृत छोटी है (यानी मेरे पास एक विरल ग्राफ है), इसलिए एमआईएस को खोजने के लिए आईग्राफ का उपयोग करना स्वीकार्य है यह गति की शर्तें है . वैकल्पिक रूप से, एक समझौता के रूप में, एक बड़ा स्वतंत्र सेट खोजने के लिए एक लालची अनुमानित एल्गोरिदम का उपयोग कर सकता है (या यदि पर्याप्त भाग्यशाली हो तो एमआईएस)। नीचे एक एल्गोरिदम है जो बहुत तेज़ लगता है:

def independent_set(adj):
    ''' 
    Given adjacency matrix, returns an independent set
    of size >= np.sum(1/(1 + adj.sum(0)))
    '''
    adj = np.array(adj, dtype=bool).astype(np.uint8)
    np.fill_diagonal(adj, 1)  # for the purposes of algorithm

    indep_set = set(range(len(adj)))
    # Loop until no edges remain
    while adj.sum(0).max() > 1: 
        degrees = adj.sum(0)
        # Randomly pick a vertex v of max degree
        v = random.choice(np.where(degrees == degrees.max())[0])
        # "Remove" the vertex v and the edges to its neigbours
        adj[v, :], adj[:, v] = 0, 0      
        # Update the maximal independent set
        indep_set.difference_update({v})
    return indep_set

या इससे भी बेहतर, हम एक अधिकतम स्वतंत्र सेट प्राप्त कर सकते हैं:

def maximal_independent_set(adj):  
    adj = np.array(adj, dtype=bool).astype(np.uint8)
    degrees = adj.sum(0)
    V = set(range(len(adj)))  # vertices of the graph
    mis = set()  # maximal independent set
    while V:
        # Randomly pick a vertex of min degree
        v = random.choice(np.where(degrees == degrees.min())[0])
        # Add it to the mis and remove it and its neighbours from V
        mis.add(v)
        Nv_c = set(np.nonzero(adj[v])[0]).union({v})  # closed neighbourhood of v
        V.difference_update(Nv_c)
        degrees[list(Nv_c)] = len(adj) + 1
    return mis
5
Andreas K. 6 फरवरी 2020, 21:45

अंतिम संपादन: यह समाधान गलत है, पोस्टर का उत्तर देखें। मैं यह पोस्ट इसलिए छोड़ रहा हूं क्योंकि इसका दो बार उल्लेख किया गया था।

यहां एक लूप के साथ है, यह सुनिश्चित नहीं है कि इसे बिना किसी के कैसे किया जाए:

results = [images[i] for i in range(len(images)) if sum(sm[i][i:]) == 1]

संपादित करें:

यहां एक सही समाधान है, यह अनिवार्य रूप से वही काम करता है जो @ सर्गेई का समाधान है लेकिन एक अलग तरीके से

def put_zeros_to_image_with_most_similarities(arr: np.array):
    index = np.sum(arr, axis=1).argmax()
    if np.sum(arr[index], axis=0) == 1:
        return
    arr[index] = 0
    arr[:, index] = 0
for _ in sm:
    put_zeros_to_image_with_most_similarities(sm)
results = [images[i] for i in range(len(images)) if sum(sm[i][i:]) == 1]
1
marke 27 जिंदा 2020, 09:44

जैसा कि मैं इसे समझता हूं, अद्वितीय छवियां वे हैं जो किसी अन्य की तरह नहीं हैं। यदि ऐसा है, तो हम पंक्तियों (या स्तंभों) को सारांशित कर सकते हैं और परिणाम के उन तत्वों का चयन कर सकते हैं जो 1 के बराबर हैं। फिर हमें छवियों की सूची से समान तत्वों को लेने की आवश्यकता है।

फिलहाल मैं नहीं जानता कि दूसरे चरण में चक्र को कैसे हटाया जाए।

[images[i] for i in np.where(sm.sum(0) == 1)[0]]

अद्यतन#1

ऊपर की चर्चा समस्या की एक नई समझ की ओर ले जाती है।

एक नया विचार यह है कि छवियों को एक-एक करके हटा दिया जाए, उन छवियों को चुना जाए जिनमें अधिकतम समान संख्या में चित्र हों।

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

ix = list(range(len(images)))

while sm[ix].T[ix].sum() != len(ix): # exit if we got the identity matrix
  va = sm[ix].T[ix].sum(0)           # count similar images
  jx = np.argmax(va)                 # get the index of the worst image
  del ix[jx]                         # delete index of the worst image

print([images[i] for i in ix])

आउटपुट:

['image_2', 'image_3', 'image_4']

अद्यतन#2

वही लेकिन समानता के सबसे खराब मूल्य के साथ हर शाखा की जांच के साथ

res = []

def get_wres(sm, ix):
  if sm[ix].T[ix].sum() == len(ix):
    res.append(list(ix))
    return
  va = sm[ix].T[ix].sum(0) # count similar images
  vx = np.max(va)          # get the value of the worst
  for i in range(len(ix)): # check every image
    if va[i] == vx:        # for the worst value
      ixn = list(ix)       # isolate one worst
      del ixn[i]           # image and
      get_wres(sm, ixn)    # try without it

get_wres(sm, ix)
print(res)

आउटपुट:

[[2, 3, 4], [1, 2, 3]]
3
Sergey 25 जिंदा 2020, 15:44