नंबर की एक 2 डी सरणी को देखते हुए लगता है समूहों

Question

उदाहरण के लिए एक 2 डी सरणी को देखते हुए: समूहों के

समूहों

0 0 0 0 0 
0 2 3 0 1 
0 8 5 0 7 
7 0 0 0 4 

आउटपुट होना चाहिए:

क्लस्टर 1: <2,3,8,5,7>

क्लस्टर 2: <1,7,4>

Answer 1

ऐसा करने का एक तरीका ग्राफ के साथ है। कुछ क्रम में मैट्रिक्स को पार करें (मैं बाएं से दाएं, ऊपर से नीचे जाऊंगा)। जब आप एक गैर-शून्य तत्व का सामना करते हैं, तो इसे ग्राफ़ में जोड़ें। फिर अपने सभी पड़ोसियों की जांच करें (ऐसा लगता है कि आप 8-जुड़े पड़ोसियों को चाहते हैं), और प्रत्येक जो गैर-शून्य है, उसके नोड को ग्राफ में जोड़ें, और इसे वर्तमान तत्व से कनेक्ट करें। ग्राफ में तत्वों को शायद उनके निर्देशांक का ट्रैक रखना होगा ताकि आप देख सकें कि क्या आप डुप्लिकेट जोड़ रहे हैं या नहीं। जब आप मैट्रिक्स को घुमाते हैं, तो आपके पास एक ग्राफ होता है जिसमें क्लस्टर का एक सेट होता है। क्लस्टर जुड़े तत्वों के उप-ग्राफ होना चाहिए।

Answer 2

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

void DFS(int x, int y) 
{ 
    printf("%d ", g[x][y]); 
    g[x][y] = 0; 
    // iterate over neighbours 
    for(dx=-1; dx<=1; dx++) 
    for(dy=-1; dy<=1; dy++) 
     if (g[x+dx][y+dy]) DFS(x+dx, y+dy); 
} 

for(i=0; i<n; i++) 
    for(j=0; j<n; j++) 
    if (g[i][j]) 
    { 
     DFS(i, j); 
     printf("\n"); 
    } 

Answer 3

आप समूहों की संख्या पता है या समूहों की एक स्थिर संख्या के लिए अपने डेटा फिट करने के लिए चाहते हैं, आप के-साधन कर सकते हैं।

http://en.wikipedia.org/wiki/K-means_clustering

Answer 4

आप Connected Component Labeling करना चाहते हैं। इसे आमतौर पर एक छवि प्रसंस्करण एल्गोरिदम माना जाता है, लेकिन यह आपके द्वारा वर्णित मिलान से मेल खाता है।

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

Answer 5

कोड का नमूना:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace Practice 
{ 
    class Program 
    { 
     static void Main() 
     { 
      var matrix = new[] { new StringBuilder("00000"), new StringBuilder("02301"), new StringBuilder("08507"), new StringBuilder("70004") }; 
      var clusters = 0; 
      for (var i = 0; i < matrix.Length; i++) 
       for (var j = 0; j < (matrix.Any() ? matrix[i].Length : 0); j++) 
        if (matrix[i][j] != '0') 
        { 
         Console.Write("Cluster {0}: <", ++clusters); 
         var cluster = new List<char>(); 
         Traverse(matrix, i, j, ref cluster); 
         Console.WriteLine("{0}>", string.Join(",", cluster)); 
        } 
      Console.ReadKey(); 
     } 

     private static void Traverse(StringBuilder[] matrix, int row, int col, ref List<char> cluster) 
     { 
      cluster.Add(matrix[row][col]); 
      matrix[row][col] = '0'; 
      for (var i = -1; i <= 1 && row + i >= 0 && row + i < matrix.Length; i++) 
       for (var j = -1; j <= 1 && col + j >= 0 && col + j < (matrix.Any() ? matrix[row + i].Length : 0); j++) 
        if(matrix[row + i][col + j] != '0') 
         Traverse(matrix, row + i, col + j, ref cluster); 
     } 
    } 
} 

एल्गोरिथ्म स्पष्टीकरण:

• प्रत्येक पंक्ति के लिए:
  • कि पंक्ति में प्रत्येक स्तंभ के लिए:
    • हैं आइटम एक विज़िट नहीं किए गए है गैर-शून्य:
      1. पाए गए क्लस्टर सदस्य को सहेजें;
      2. दौरे के रूप में [पंक्ति, कॉलम] पर स्थान चिह्नित करें; किसी भी विज़िट नहीं किए गए गैर शून्य पड़ोसियों के लिए
      3. चेक समय में-सीमा मैट्रिक्स के रहने:
         • [पंक्ति - 1, स्तंभ - 1];
         • [पंक्ति - 1, कॉलम];
         • [पंक्ति - 1, कॉलम + 1];
         • [पंक्ति, कॉलम - 1];
         • [पंक्ति, कॉलम + 1];
         • [पंक्ति + 1, कॉलम - 1];
         • [पंक्ति + 1, कॉलम];
         • [पंक्ति + 1, कॉलम + 1]।
      4. यदि कोई पड़ोसी एक अनजान गैर-शून्य दोहराना चरण 1-4 पुनरावर्ती है तब तक सभी पड़ोसियों को शून्य का दौरा नहीं किया जाता है (सभी क्लस्टर सदस्यों को मिला है)।