जोड़ी दूरी के सेट से अंक निर्धारित करना

Question

अंक के बीच दूरी के मैट्रिक्स को देखते हुए एन-आयामी बिंदुओं का एक सेट निर्धारित करने के लिए एक एल्गोरिदम है जिसमें इन दूरी हैं? (या कम से कम त्रुटि को कम करता है)

टर्नपाइक समस्या के एन-आयामी संस्करण की तरह।

सबसे अच्छा मैं साथ आ सकता हूं बहुआयामी स्केलिंग का उपयोग कर रहा है।

Answer 1

आप बहु-आयामी स्केलिंग (एमडीएस) के साथ सही रास्ते पर हैं, लेकिन एमडीएस बड़े डेटासेट के लिए अव्यवहारिक है, क्योंकि इसकी समय जटिलता अंक की संख्या में वर्गबद्ध है। आप फास्ट मैप को देखना चाह सकते हैं, जिसमें रैखिक समय जटिलता है और अनुक्रमण के लिए बेहतर अनुकूल है। देखें:

क्रिस्टोस फालूसोस और राजा-आईपी लिन: "FastMap:। अनुक्रमण, डाटा माइनिंग और पारंपरिक और मल्टीमीडिया डेटासेट के दृश्य के लिए एक फास्ट एल्गोरिथ्म प्रोक में SIGMOD, 1995, doi:10.1145/223784.223812

Answer 2

मैं मूल संपादित नहीं कर सकता, क्योंकि मेरे पास पर्याप्त प्रतिनिधि नहीं है, लेकिन मैंने यहां समस्या को पुन: स्थापित करने का प्रयास किया है।

ओपी में दूरी के इनपुट एनएक्सएन मैट्रिक्स है। वह बिंदुओं का प्रतिनिधित्व करने वाले एन-आयामी निर्देशांक का आउटपुट सरणी, आकार एन बनाना चाहता है, जहां प्रत्येक बिंदु के बीच की दूरी इनपुट मैट्रिक्स में संग्रहीत होती है।

ध्यान दें कि यह सामान्य स्थिति में व्याख्या करने योग्य नहीं है:

मान लीजिए मैं इस

 
    A B C 
A x 1 2 
B  x 0 
C  x 

एक तरह एक मैट्रिक्स दूरी की 1 यूनिट (जैसे कि 1 मीटर) बी से दूर है, और एक है सी से एक मीटर दूर है लेकिन बी और सी एक ही स्थान पर हैं।

इस विशेष मामले में त्रुटियों की न्यूनतम राशि 1 मीटर है, और समाधान है कि परिणाम

Answer 3

प्राप्त Programming Collective Intelligence में यह कर, पी के लिए एक एल्गोरिथ्म है से एक अनंत प्रकार देखते हैं। 49, "दो आयामों में डेटा देखना", जिसे एन-आयामों के लिए अनुकूलित किया जा सकता है।

अरे - यह बहुआयामी स्केलिंग है - इसलिए मुझे लगता है कि आप सही रास्ते पर हैं।

Answer 4

आप "धोखा" कर सकते हैं और इस के लिए एक सतत संख्यात्मक विधि का उपयोग करें। अंक के सभी शुरू में कुछ "यादृच्छिक" की स्थिति में होना करने के लिए ले लो, और फिर उन्हें के माध्यम से लूप, उन्हें दूर एक दूसरे से आनुपातिक में जाने requir एड दूरी। यह कुछ बिंदुओं को पसंद करेगा, लेकिन उन्हें लागू करने से पहले चाल का औसत लेना, फिर औसत लागू करना इस समस्या को हटा देगा। यह एक ओ (एन²) एल्गोरिदम है, लेकिन इसे लागू करने और समझने के लिए बहुत आसान है। त्रुटि के नीचे 2-डी उदाहरण में < < 10% है, हालांकि अगर दूरी दूर अवास्तविक है तो यह बहुत अच्छा व्यवहार नहीं कर सकता है।

सी ++ उदाहरण:

#include <conio.h> 
#include <math.h> 
#include <stdio.h> 
#include <stdlib.h> 

#define DAMPING_FACTOR 0.99f 

class point 
{ 
public: 
    float x; 
    float y; 
public: 
    point() : x(0), y(0) {} 
}; 

// symmetric matrix with distances 
float matrix[5][5] = { 
          { 0.0f, 4.5f, 1.5f, 2.0f, 4.0f }, 
          { 4.5f, 0.0f, 4.0f, 3.0f, 3.5f }, 
          { 1.5f, 4.0f, 0.0f, 1.0f, 5.0f }, 
          { 2.0f, 3.0f, 1.0f, 0.0f, 4.5f }, 
          { 4.0f, 3.5f, 5.0f, 4.5f, 0.0f } 
         }; 
int main(int argc, char** argv) 
{ 
    point p[5]; 
    for(unsigned int i = 0; i < 5; ++i) 
    { 
     p[i].x = (float)(rand()%100)*0.1f; 
     p[i].y = (float)(rand()%100)*0.1f; 
    } 

    // do 1000 iterations 
    float dx = 0.0f, dy = 0.0f, d = 0.0f; 
    float xmoves[5], ymoves[5]; 

    for(unsigned int c = 0; c < 1000; ++c) 
    { 
     for(unsigned int i = 0; i < 5; ++i) xmoves[i] = ymoves[i] = 0.0f; 
     // iterate across each point x each point to work out the results of all of the constraints in the matrix 
     // collect moves together which are slightly less than enough (DAMPING_FACTOR) to correct half the distance between each pair of points 
     for(unsigned int i = 0; i < 5; ++i) 
     for(unsigned int j = 0; j < 5; ++j) 
     { 
      if(i==j) continue; 
      dx = p[i].x - p[j].x; 
      dy = p[i].y - p[j].y; 
      d = sqrt(dx*dx + dy*dy); 
      dx /= d; 
      dy /= d; 
      d = (d - matrix[i][j])*DAMPING_FACTOR*0.5f*0.2f; 

      xmoves[i] -= d*dx; 
      ymoves[i] -= d*dy; 

      xmoves[j] += d*dx; 
      ymoves[j] += d*dy; 
     } 

     // apply all at once 
     for(unsigned int i = 0; i < 5; ++i) 
     { 
      p[i].x += xmoves[i]; 
      p[i].y += ymoves[i]; 
     } 
    } 

    // output results 
    printf("Result:\r\n"); 
    for(unsigned int i = 0; i < 5; ++i) 
    { 
     for(unsigned int j = 0; j < 5; ++j) 
     { 
      dx = p[i].x - p[j].x; 
      dy = p[i].y - p[j].y; 
      printf("%f ", sqrt(dx*dx + dy*dy)); 
     } 
     printf("\r\n"); 
    } 

    printf("\r\nDesired:\r\n"); 
    for(unsigned int i = 0; i < 5; ++i) 
    { 
     for(unsigned int j = 0; j < 5; ++j) 
     { 
      printf("%f ", matrix[i][j]); 
     } 
     printf("\r\n"); 
    } 

    printf("Absolute difference:\r\n"); 
    for(unsigned int i = 0; i < 5; ++i) 
    { 
     for(unsigned int j = 0; j < 5; ++j) 
     { 
      dx = p[i].x - p[j].x; 
      dy = p[i].y - p[j].y; 
      printf("%f ", abs(sqrt(dx*dx + dy*dy) - matrix[i][j])); 
     } 
     printf("\r\n"); 
    } 

    printf("Press any key to continue..."); 

    while(!_kbhit()); 

    return 0; 
}