Question about calculating euclidean distance between two 2d vectors

[bpt0004]

Hi everyone this is my first post, i've been browsing for awhile and finally decided to join. I'm having trouble with an assignment i have in class. I need to calculate the euclidean distance between two 2d vector. The function takes in two 2d vectors of integers. I'm also having trouble deciding what to use as a return when i calculate the distance between both 2d vectors either a vector<int> or a vector<vector<int> >??

vector <vector<double> > Location::CalculateEuclideanDistance (vector <vector<int> >trainingData, vector <vector<int> > testData)
{ 
     count=trainingData.size();
     
  /*   using iterators
     for ( ; rowIterator != rowEnd; ++rowIterator ) 
         {
             vector<int>::iterator columnIterator = rowIterator->begin();
             vector<int>::iterator columnEnd = rowIterator->end();
         
     
     for ( ; columnIterator != columnEnd; ++columnIterator )
   */
     for(int i=0; i <count ;i++)
             for(int j=0; j <count ; j++)
             {
                  
                  addedSum= addedSum+ pow( fabs(trainingData[i][j]-testData[i][j]),2);
     
                  distance=sqrt(addedSum);
                  cout << distance;
                  distanceVector[i][j]=distance;
     
                  cout <<" The Euclidean Distances at point " << distanceVector[i][j] << "is " << distance;
         }    
         
         return distanceVector;
}

[mrnutty]

The distance between two vector is given by (v1-v2).length();
Your return type should be similar to the parameters passed.

And welcome!

[bpt0004]

wouldn't v1-v2.length be the distance in 1 dimension? for 2 dimension the euclidean distance would be sqrt[ (x1-y1)^2+(x2-y2)^2+....]? i'm just having trouble inputting the algorithm for a two 2d vectors

[jonsca]

Based on how you've set it up, your vector<int> for each sample will have two members, say V1(0) = 1, and V1(1) = 2, and another would have V2(0) = 2, V2(1) = 3. So you are correct that you would have to calculate a third vector V3(0) = V1(0) - V2(0)=-1,V3(1) = V1(1)-V2(1) = -1. Then you could iterate through the vector and square all the members, then take the square root (root 2 in this example). Return a vector<int> of all of the Euclidian distances(make sure the index in the distance vector lines up with the corresponding training data).

[mrnutty]

v1 an v2 represent vectors, so if v1 = <i,j,k> and v2 = <i,j,k> then
the distance between them is (v1 - v2).length.

Remember the length is the magnitude of the vector.

[bpt0004]

could you guys help me on the code implementation of your solutions. I did this but still not solved

vector<double> Location::CalculateEuclideanDistance (vector <vector<int> >trainingData, vector <vector<int> > testData)
{ 
        
    
     count=trainingData.size();
     
     /*
     for ( ; rowIterator != rowEnd; ++rowIterator ) 
         {
             vector<int>::iterator columnIterator = rowIterator->begin();
             vector<int>::iterator columnEnd = rowIterator->end();
         
     
     for ( ; columnIterator != columnEnd; ++columnIterator )
     */
     
   
     for(int i=0; i <count ;i++)
             for(int j=0; j <count ; j++)
             {
                  
                  addedSum= addedSum+ pow( fabs(trainingData[i][j]-testData[i][j]),2);
     
                  distance=sqrt(addedSum);
                  cout << distance;
                  distanceVector[i]=distance;
     
                  cout <<" The Euclidean Distances at point " << distanceVector[i] << "is " << distance;
         }    
         
         return distanceVector; 
}

[jonsca]

Other than the fact that you don't need to calculate distance until after the for loops complete (you probably left it in there to debug at this point) and you don't need fabs since you are squaring, it seems to be ok.

[bpt0004]

i'm getting a run-time error running the code which causes the program to crash.

running the gdb debugger i get a "An Access Violation (Segmentation Fault) raised in your program" on this line

addedSum= addedSum+ pow( fabs(trainingData[i][j]-testData[i][j]),2);

[jonsca]

i'm getting a run-time error running the code which causes the program to crash.

running the gdb debugger i get a "An Access Violation (Segmentation Fault) raised in your program" on this line

addedSum= addedSum+ pow( fabs(trainingData[i][j]-testData[i][j]),2);

sry I missed it before but count for one element should be equal to trainingData[currentindex].size() (or however you are going to designate the "active" training set vector -- theoretically if all your vectors are going to be the same size you could take trainingData[0] but that's not as extensible) and then iterate over the entire set using another for loop.
the way you have it, your for loops are trying to sum the squares over the size of the _entire_ training set, whereas you want to perform the calculation using just one of the vectors at a time).

[bpt0004]

jonsca, i changed my code to this

vector<double> Location::CalculateEuclideanDistance (vector <vector<int> >trainingData, vector <vector<int> > testData)
{ 
      
     
     vector<vector<int> >::iterator rowIterator=trainingData.begin();
     vector<vector<int> >::iterator rowEnd=trainingData.end();
  /*    
     for ( ; rowIterator != rowEnd; ++rowIterator ) 
         {
             vector<int>::iterator columnIterator = rowIterator->begin();
             vector<int>::iterator columnEnd = rowIterator->end();
         
     
     for ( ; columnIterator != columnEnd; ++columnIterator )
     */     
     for(int i=0; i <count ;i++)
            
             for(int j=0; j <count ; j++)
             { 
                  count=trainingData[i].size();
                  addedSum= addedSum+ pow( fabs(trainingData[i][j]-testData[i][j]),2);
     
                  distance=sqrt(addedSum);
                  cout << distance;
                  distanceVector[i]=distance;
     
                  cout <<" The Euclidean Distances at point " << distanceVector[i] << "is " << distance;
         }   
                  
         return distanceVector; 
}

but i'm still getting the same error?? PLZ help me, i have 2 days to finish this.

[jonsca]

You're really close (at least with this part)...

for(int i=0; i <trainingData.size() ;i++)
     {  
        count = trainingData[i].size(); //can make this trainingData[0] if guaranteed same size
	for(int j=0; j <count ; j++)
        {                  
            addedSum= addedSum+ (trainingData[i][j]-testData[i][j])*(trainingData[i][j]-testData[i][j]);
        }

	returnvec.push_back(sqrt(addedSum));   	         
         
      }

I didn't have a chance to check it thoroughly but I'm sure you get the basic idea. I wrote the square out (you can leave the pow in if you want) but you really don't need the fabs cause you are squaring the value anyway.

[bpt0004]

I'm still getting the same error from the debugger from the same line with addedSum. The debugger is also saying the error is when i=1, and that it could not watch the variable "i". I've tried everything already and i'm getting really frustrated, thank you so much jonsca for everything and all your future help.

[jonsca]

Can you post up the main that you are using to test it?

[bpt0004]

Heres the entire program

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <fstream>
#include <sstream>
#include <stdexcept>
#include <stdio.h>
#include <ctype.h>
#include <vector>
#include <cctype>
#include <conio.h>
#include <algorithm>
#include <iterator>
#include <iomanip>


using namespace std;
using std :: ifstream;
using std :: ofstream;
using std :: endl;

struct integer 
{
       int x;
       int y;
};
struct OrderingFunction
/* Ordering function used for sort(vec_begin, vec_end, function)
compares two integers in a structure "integer" and depending whether both are equal
returns a comparison between both integers
*/
{
       bool operator ()(const integer& a, const integer& b)
       {
            if (a.x==b.x)
               return (a.y < b.y);
            else
                return (a.x < b.x);
       }
};       

class Location
{
      public:    
             Location();
             vector<double> CalculateEuclideanDistance (vector <vector<int> >trainingData, vector <vector<int> >testData);
             double distance;
             double addedSum;
             double count;
             int kValue;
             vector <double>  distanceVector;
             vector <vector <double> > GetDistanceVector;
             
             
             vector< vector<int> >::iterator rowIterator; 
             vector<vector<int> >::iterator rowEnd ;
             vector< vector<int> >::iterator columnIterator;
             vector< vector<int> >::iterator columnEnd;
             
             
             void PerformPrediction();
             void SetKValue();
             int GetKValue();
             int k_value;
             void Sort();
             
      private:             
};

class UserInterface
{
      public:
             UserInterface();
             void MainMenu();
             bool menuBool;
             string userName;
             int inputNumber;
             bool get_number ( int& number );
                     
      private:             
};

class NegativeNumberOption
{
      public:
             NegativeNumberOption(){}
             NegativeNumberOption (string theMessage): message(theMessage){}
             string getMessage() const {return message;}
      private:
              string message;
};
class NotAnOption
{
      public:
             NotAnOption(){}
             NotAnOption (string theMessage1): message1(theMessage1){}
             string getMessage() const {return message1;}
      private:
              string message1;
};

class LocationDatabase
{
      public:
             LocationDatabase();
             
             vector< vector<int> >LoadTrainingData();
             string trainingDataName;
             vector <vector<int> >trainingDataVector;
             int trainingData;
             bool trainingBool;
             
             void DisplayTrainingData();
             void DisplayTestData();
             vector<int>::iterator trainingIterator; 
             
             
             vector<vector <int> > LoadTestData();
             string testDataName;
             int testData;
             vector <vector <int> >testDataVector;
             
             int testBool;
             ifstream inputTrainingData;
             ifstream inputTestData;
             
             vector <vector <int> > GetTrainingData();
             vector <vector<int> > GetTestData();
             
      private:             
};

/*
Templates used in the LoadTrainingData & LoadTestData functions. The template reads 
in a text file of a certain type and sets the data to a two dimensional vector.
Reference:http://www.cppreference.com/wiki/stl/algorithm/start 
*/
template< typename T >
std::ostream& operator<<(std::ostream& os, std::vector<std::vector<T> >& array)
{
typedef typename std::vector<std::vector<T> >::const_iterator ci;
for ( ci it = array.begin(); it != array.end(); ++it )
{
std::copy((*it).begin(), (*it).end(), std::ostream_iterator<T>(os, "   "));
os << '\n';
}
return os;
} 

template<class RanIt>
    void sort(RanIt first, RanIt last);
    
template<class Iter_T, class Iter2_T>
double vectorDistance(Iter_T first, Iter_T last, Iter2_T first2) {
  double ret = 0.0;
  while (first != last) {
    double dist = (*first++) - (*first2++);
    ret += dist * dist;
  }
  return ret > 0.0 ? sqrt(ret) : 0.0;
}


int main()
{
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(2);
    
    UserInterface newUserInterface;
    newUserInterface.MainMenu();
    
    return 0;
}

//------------------------------------------------------------------------------
LocationDatabase::LocationDatabase()
{
}

vector <vector<int> >LocationDatabase::LoadTrainingData()
{    
/* Pre-condition: takes in text file from ifstream containing training data. If 
   data is empty or fails to open, an error prompt is given to the user.

   Post-condition: Sets the training data vector to the contents of the text file
   skipping the first line of text. After setting the data to the training vector
   the program displays the contents of the training data to the user.                  
*/
  
     cout << "To load training data, please enter the name of the training data text file \n"
          << "\n"; 
           
          
     cin  >> trainingDataName;
     
     cout << "Your file was: " << trainingDataName << endl;

     
     inputTrainingData.open(trainingDataName.data(), ios::in); 

     if (inputTrainingData.fail()) 
         cout <<"ERROR!!!!Training data loaded unsuccessfully or training data is already loaded!\n"
              <<"There was an error in opening the training data, please try again\n"
              <<"\n";              
     else
         {
  
       string line;
   
       while ( getline(inputTrainingData, line) )
           {
   
               vector<int> row;  
               int trainingData;            
               istringstream stringSpace (line);
              
   while ( stringSpace >> trainingData)
           {
             
               row.push_back(trainingData);
           }     
         trainingDataVector.push_back(row);    
         }                                                                 
              cout << "Training data loaded successfully \n"
                   << "\n";    
              cout <<"Location "<<"I " <<"II "<<"III "<< "IV " <<"V "<<"VI "<< "VII " << "A " <<"B " <<"C "<< "Threat Score"<<endl;      
              cout << trainingDataVector << endl;       
         } 
         
         return trainingDataVector;
}
vector<vector<int> >LocationDatabase::GetTrainingData()
{
// returns the training data vector for the PerformPrediction() function used in the Location class
       
       return trainingDataVector;
}
vector<vector<int> >LocationDatabase::GetTestData()
{
// returns the test data vector for the PerformPrediction() function used in the Location class
       
       return testDataVector;
}

vector<vector<int> > LocationDatabase::LoadTestData()
{
/* Pre-condition: takes in text file from ifstream containing test data. If 
   data is empty or fails to open, an error prompt is given to the user.

   Post-condition: Sets the test data vector to the contents of the text file
   skipping the first line of text. After setting the data to the test vector
   the program displays the contents of the test data to the user.                  
*/
     cout << "To load test data, please enter the name of the test data text file \n"
          << "\n"; 
          
     cin  >> testDataName;
     
     cout << "Your file was: " << testDataName << endl;

     inputTestData.clear();
     
     inputTestData.open(testDataName.data(), ios::in); 

     if (inputTestData.fail())
        { 
         cout <<"ERROR!!!!Test data loaded unsuccessfully or file is already loaded!\n"
              <<"There was an error in opening the test data, please try again\n"
              <<"\n";  
        }     
     else
         {
         vector<vector<int> > testDataVector;
         string line;
   
         while ( getline(inputTestData, line) )
           {
               vector<int> row;  
               int testData;
              
              istringstream stringSpace (line);
              
         while ( stringSpace >> testData)
           {
               row.push_back(testData);
           }
         
         testDataVector.push_back(row);       
         }                                                                 
              cout << "Test data loaded successfully \n"
                   << "\n";    
              cout <<"Location "<<"I " <<"II "<<"III "<< "IV " <<"V "<<"VI "<< "VII " << "A " <<"B " <<"C "<< "Threat Score"<<endl;    
              cout << testDataVector << endl;       
         }                      
          
         return testDataVector; 
         }     
                      
void LocationDatabase::DisplayTrainingData()
{
     if (trainingDataVector.empty())
        cout << "Training information is empty or isn't loaded \n";
     else
        cout <<"Location "<<"I " <<"II "<<"III "<< "IV " <<"V "<<"VI "<< "VII " << "A " <<"B " <<"C "<< "Threat Score"<<endl; 
        cout << trainingDataVector;
      
} 
//------------------------------------------------------------------------------
Location::Location()
{
} 
vector<double> Location::CalculateEuclideanDistance (vector <vector<int> >trainingData, vector <vector<int> > testData)
{    
/*
Pre-condition: takes in two 2d vectors of integers, the trainingData & testData vector. 
Post-condition: returns the euclidean distance for each element in each 2d vector
and sets it to a vector "distanceVector" which will be sorted for the KNN algorithm.
*/
     for(int i=0; i <trainingData.size() ;i++)
     {  
        count = trainingData[i].size(); 
     for(int j=0; j <count ; j++)
        {                  
            addedSum= addedSum+ (trainingData[i][j]-testData[i][j])*(trainingData[i][j]-testData[i][j]);
            cout <<addedSum;
        }
	distanceVector.push_back(sqrt(addedSum));  
            
      }
      return distanceVector;
}           

void Location:: SetKValue()
{
     
    kValue=3;   
    cout <<"Enter new k value";
    cin >> kValue;
    
    cout <<"K value: " << kValue << endl;
}
int Location::GetKValue()
{
    return kValue;
}


void Location::PerformPrediction()
{
     LocationDatabase newDatabase;
        
     vector <vector<int> >testDataVector;
     vector <vector<int> >trainingDataVector;
     
     trainingDataVector=newDatabase.LoadTrainingData();
     testDataVector=newDatabase.LoadTestData(); 
     
     if (trainingDataVector.empty() || trainingDataVector.empty())
        cout <<"Training data vector or test data vector is empty. \n"
             <<"Please load training or test data before performing the prediction" << endl;
        
     else
     {
     
     k_value=GetKValue();
     
     if (k_value==3)
        cout <<"No set value for k was given, therefore k value=3";
     else 
        cout <<"Set value for k is " << k_value<<endl;
     
     CalculateEuclideanDistance (trainingDataVector, testDataVector);
  //  sort (distanceVector.begin(),distanceVector.end(),OrderingFunction());
     //display threat score    
     }   
}
//------------------------------------------------------------------------------
UserInterface::UserInterface()
{
}
bool UserInterface::get_number ( int& number )
{
  while ( !( cin >> number ) ) {
    if ( cin.eof() )
      return false;
    else {
      char ch;

      cin.clear();

      cout<<"Invalid input, please try again: ";
      while (cin.get(ch) && ch != '\n' );
    }
  }

  return true;
}
void UserInterface::MainMenu()
{
      LocationDatabase newDatabase;
      Location newLocation;
      menuBool=true;
      
      cout << "Welcome to the Predictive Zombie Attack Response Database \n"
           << "Please log-in to begin the system \n"
           << "\n"
           << "UserName: ";
           
      cin >> userName;
      
      cout   <<"\n"
             <<"//////////////////////////////////////////////////////////////////////////////" <<endl
             <<"/                                                                             /" <<endl
             <<"                         Pedictive Zombie Attack Response Database            /" << endl
             <<"/                                  User:" << userName                            << endl
             <<"/                                                                             /" << endl
             <<"/                                                                             /" << endl
             <<"/////////////////////////////////////////////////////////////////////////////\n"
             << "\n";
         
      while (menuBool=true)
      {
            cout << "1) Load Training Data from File \n"
                 << "2) Load Test Data from File \n"
                 << "3) Set the value of K (default= 3) \n"
                 << "4) Display Training Data \n"
                 << "5) Perform Prediction on Test Data \n"
                 << "6 Exit the system \n"
                 << "\n";
        
      int inputNumber;
     if ( get_number ( inputNumber ) )
      
     
      switch (inputNumber)
      {
             
             case 1: 
                  newDatabase.LoadTrainingData();
                  
                  break;
             case 2:
                  newDatabase.LoadTestData();
                  break;
             case 3:
                  newLocation.SetKValue();
                  break;
             case 4: 
                  newDatabase.DisplayTrainingData();
                  break;                              
             case 5:
                newLocation.PerformPrediction();
                  break;
             case 6:
             
                  cout << "Exiting the Pedictive Zombie Attack Response Database System";
                  exit(1);
                  break;
             
             default:
                   cout <<"Unknow Input\n"
                        <<"\n";
      }
      menuBool=true; 
      }   
}

[bpt0004]

Sample Training Data

LocationNumber I II III IV V VI VII A B C ThreatScore
1 1 0 2 5 90 137 3 522 0 0 -192
2 2 1 0 5 135 65 9 33 2 2 -614
3 5 1 3 3 138 126 7 477 3 0 -369
4 3 0 0 2 37 149 6 247 1 2 -341
5 4 1 1 1 138 62 0 76 4 2 -539
6 5 0 1 1 20 257 5 980 0 0 113
7 4 0 3 3 71 304 5 433 1 0 -736
8 0 0 2 2 86 242 10 33 0 1 -992
9 2 0 2 4 48 223 3 189 4 2 -651
10 3 1 1 3 98 152 9 369 5 1 -426
11 3 1 2 3 39 349 2 806 5 2 -384
12 4 0 2 5 128 181 7 658 1 1 -321
13 1 1 0 0 76 119 9 365 3 0 -250
14 0 1 2 2 54 217 7 460 4 2 -383
15 2 0 2 4 69 165 0 1000 4 0 278
16 3 1 2 5 99 157 2 61 0 0 -746
17 2 1 1 2 28 222 4 102 0 2 -676
18 2 0 3 5 134 136 1 490 3 0 -350
19 1 0 1 2 4 288 1 805 5 1 -80
20 3 1 1 4 26 341 1 432 3 1 -695
21 4 1 0 5 123 212 7 625 4 2 -425
22 3 0 3 0 70 309 5 764 1 0 -405
23 4 0 3 0 70 36 0 227 1 1 -110
24 2 0 0 0 147 352 2 618 5 2 -884
25 3 1 0 0 106 289 9 527 0 1 -696
26 2 1 3 0 141 142 0 982 4 1 120
27 2 1 0 3 138 237 7 89 4 0 -1071
28 3 1 3 3 2 286 0 20 5 1 -868
29 5 0 2 3 94 70 9 0 5 1 -543
30 3 1 1 1 46 99 8 927 3 2 455
31 5 1 1 3 20 101 6 295 2 2 -112
32 0 0 1 3 106 298 5 215 4 0 -1020
33 2 0 0 2 95 159 9 138 2 2 -659
34 2 1 0 4 55 255 7 160 0 0 -812
35 3 1 0 1 58 195 2 287 3 0 -490
36 3 1 0 0 68 345 2 747 4 2 -504
37 5 1 1 1 73 18 8 275 4 1 -41
38 4 1 2 2 17 61 10 71 0 1 -219
39 4 1 0 2 24 141 1 592 3 2 78
40 2 0 0 3 24 152 3 863 2 0 313

Sample Test Data
LocationNumber I II III IV V VI VII A B C ThreatScore
41 4 0 3 5 110 200 8 816 0 1 -173
42 2 0 2 2 141 73 5 340 1 0 -334
43 2 1 0 1 31 149 0 140 1 1 -410
44 5 1 2 5 138 11 3 838 0 1 344
45 2 0 0 5 73 196 0 15 5 0 -808
46 0 1 0 4 136 279 1 657 1 0 -605
47 1 1 3 1 21 93 3 590 2 1 224
48 5 1 0 3 92 48 9 152 1 1 -320
49 3 0 0 4 13 158 0 801 4 1 272
50 4 0 0 3 40 336 10 296 0 0 -883

[jonsca]

For some reason you are getting a vector of length 0 at the beginning of your training data (I'll look more closely later) and one at the end of your testing data. When it tries to step through the 0 length vector it chokes. I looked through, but are you clearing a line out somewhere? At any rate, as a band-aid you could scan your data and delete any zero length vectors so that you can keep going with the program but it's definitely worth your while to delve into it.

[bpt0004]

yes, i'm clearing the first line of both text files to take out the
LocationNumber I II III IV V VI VII A B C ThreatScore

in the first line of each text, is there a better way to read in the text file into a 2d vector and skip the first line?

[bpt0004]

yes, i'm clearing the first line of both text files to take out the
LocationNumber I II III IV V VI VII A B C ThreatScore

in the first line of each text, is there a better way to read in the text file into a 2d vector and skip the first line?

[jonsca]

This is probably your best bet:
http://www.cplusplus.com/reference/iostream/istream/ignore/
(with a newline as your delimiter)

[bpt0004]

I've already tried everything including the ignore line, but i'm still getting error with the CalculateEuclideanDistance function :(

[jonsca]

Double check the sizes of the vectors in the vector<vector<int> > make sure they are not zero. Also remember that you have a mismatch between the size of your training and testing sets so if you are iterating over both your testing set it going to run out. Keep printing out your iteration step by step until it crashes...

[jonsca]

There's no testing data! I thought I was checking for it before but it was just reporting the training data sizes.

[bpt0004]

why is there no testing data, i return the testDataVector from the LoadTestData() function?

[jonsca]

TestDataVector is declared locally within your else block. Once the else block completes it's out of scope and destroyed and there's nothing to return (I had missed this before).

So just move it to the top of your method and it should work (bearing in mind that it still crashes now because you have more training data than testing). So take that into account or make more testing samples.

[bpt0004]

Thank you so much jonsca!! is there a way to make it work if the test data is less than the training data or do the vectors have to be the same size?

[jonsca]

You're very welcome, glad I could help.

It might be a safe choice to put in i < min(testData.size(),trainingData.size()) for your for loop condition to make sure you don't get a mismatch.
If you wanted to get fancy, and with more data, you could take a random sample of your training set equal to the size of the testing set. That's the only way I can think of offhand.

[bpt0004]

sdf