kNN.cpp

#include <iostream>
#include <fstream>
#include <string>
#include <vector> 
#include <cstdlib>
#include <cmath>

#define MAX_TOK 10  

using namespace std;

// ---------------------------- Functions ------------------------------------------
string* StringSplit(string strOrigin, string strTok){
	int     cutAt;                            //자르는위치
	int     index     = 0;                    //문자열인덱스
	string* strResult = new string[MAX_TOK];  //결과return 할변수

	//strTok을찾을때까지반복
	while ((cutAt = strOrigin.find_first_of(strTok)) != strOrigin.npos)
	{
	    if (cutAt > 0)  //자르는위치가0보다크면(성공시)
	    {
	        strResult[index++] = strOrigin.substr(0, cutAt);  //결과배열에추가
	    }
	    strOrigin = strOrigin.substr(cutAt+1);  //원본은자른부분제외한나머지
	}

	if(strOrigin.length() > 0)  //원본이아직남았으면
	{
	    strResult[index++] = strOrigin.substr(0, cutAt);  //나머지를결과배열에추가
	}

	return strResult;  //결과return
/*
This function split string row to the tokenizers
*/
}

vector< vector<float> > LoadFile(string filename){
/* 
This function loads data and convert txt into float matrix 
*/
	string line;
	vector< vector<float> > Hans_Matrix; 
	vector<float> row; 
	ifstream MyStream (filename);

	if (MyStream.is_open()) {
    	while ( getline (MyStream,line) ){
			row.clear();
			string *token = StringSplit(line, "\t");
			// For each row in Matrix 
			for (int idx = 0; idx < 4; idx ++){
				float Str_to_Double = atof(token[idx].c_str()); // String Number 
				row.push_back(Str_to_Double);
			}
			Hans_Matrix.push_back(row);
    	}
    	MyStream.close();
  	}
  	return Hans_Matrix;
}

float Distance(vector<float> A, vector<float> B){
/* 
This function compute the distance
A.size = B.size
*/	
	float distance = 0; 
	for (int idx = 0; idx < A.size(); idx ++){
		distance += pow((A[idx] - B[idx]),2);
	}
	return sqrt(distance);

}

bool isPresent(vector< vector<float> > Vector_Matrix, vector<float> Target){
/* 
	Check if Target Vector is in the Vector Matrix or Not 
*/
	bool result = false;
	for (int idx = 0; idx < Vector_Matrix.size(); idx ++){
		if (Vector_Matrix[idx] == Target){
			result = true;
			break;
		}
		else{
			result = false;
		}
	}

	return result; 
}

float Performance_Check(vector< vector<float> > My_Answer_R, vector< vector<float> > My_Answer_G, vector< vector<float> > My_Answer_B, 
	vector< vector<float> > R_Matrix, vector< vector<float> > G_Matrix, vector< vector<float> > B_Matrix){
	/* 
		Compute the Accuracy
	*/ 
	double score = 0.0; 
	float Accuracy; 
	for (int idx = 0; idx < My_Answer_R.size(); idx++){
		vector<float> Current =  My_Answer_R[idx];
		if (isPresent(R_Matrix, Current) ){
			score ++; 
		}
	}

	for (int idx = 0; idx < My_Answer_G.size(); idx++){
		vector<float> Current =  My_Answer_G[idx];
		if (isPresent(G_Matrix, Current) ){
			score ++; 
		}
	}

	for (int idx = 0; idx < My_Answer_B.size(); idx++){
		vector<float> Current =  My_Answer_B[idx];
		if (isPresent(B_Matrix, Current) ){
			score ++; 
		}
	}

	Accuracy = score / 900; 
	return Accuracy;

}

int Where_is_Max_Idx(vector<float> A){
	int max_idx = 0; 
	float max_val = -1000.0; 
	for (int idx = 0; idx < A.size(); idx ++){
		if (A[idx] > max_val){
			max_val = A[idx];
			max_idx = idx;
		}
	}
	return max_idx; 

}

// ---------------------------- Program  ------------------------------------------
int main () {
	/* ============== DATA LOAD AND GENERATING MATRIX =============== */ 
	string Train_Blue = "Wb_train.txt"; 
	string Train_Red= "Wr_train.txt";
	string Train_Green = "Wg_train.txt";

	string Test_Blue = "Wb_test.txt"; 
	string Test_Red= "Wr_test.txt";
	string Test_Green = "Wg_test.txt";
	

	vector< vector<float> > Train_Blue_Matrix = LoadFile(Train_Blue);
	vector< vector<float> > Train_Red_Matrix = LoadFile(Train_Red);
	vector< vector<float> > Train_Green_Matrix = LoadFile(Train_Green);
	vector< vector<float> > Test_Blue_Matrix = LoadFile(Test_Blue);
	vector< vector<float> > Test_Red_Matrix = LoadFile(Test_Red);
	vector< vector<float> > Test_Green_Matrix = LoadFile(Test_Green);

	vector< vector<float> > Train_Matrix; 
	vector< vector<float> > Test_Matrix;

	Train_Matrix.insert(Train_Matrix.end(), Train_Blue_Matrix.begin(), Train_Blue_Matrix.end());
	Train_Matrix.insert(Train_Matrix.end(), Train_Red_Matrix.begin(), Train_Red_Matrix.end());
	Train_Matrix.insert(Train_Matrix.end(), Train_Green_Matrix.begin(), Train_Green_Matrix.end());

	Test_Matrix.insert(Test_Matrix.end(), Test_Blue_Matrix.begin(), Test_Blue_Matrix.end());
	Test_Matrix.insert(Test_Matrix.end(), Test_Red_Matrix.begin(), Test_Red_Matrix.end());
	Test_Matrix.insert(Test_Matrix.end(), Test_Green_Matrix.begin(), Test_Green_Matrix.end());

	vector< vector<float> > My_Answer_Red; // index = 0
	vector< vector<float> > My_Answer_Green; // index = 1 
	vector< vector<float> > My_Answer_Blue; // index = 2

	/* ============== Find K Nearest Neighbor =============== */ 
	int K;
	cout << "K : ";
	cin >> K;

	for (int idx_test = 0; idx_test < Test_Matrix.size(); idx_test ++){
		vector<float> Target = Test_Matrix[idx_test];
		float Min_Distance = 100000.0; 
		float distance = 100000.0; 
		int Decision_Index = 100; 
		vector< vector<float> > Near_Matrix;  
		vector<float> Near_Matrix_Distance;   
		float Max_Near_Distance = 100000.0; 

		/* 
			Key : Target Matrix in Test 
			Value : NN vector (Set of points )
		*/

		for (int idx_train = 0; idx_train < Train_Matrix.size(); idx_train ++ ){
			vector <float> NN_Vector = Train_Matrix[idx_train];
			int max_idx = 0; 
			distance = Distance(Target, NN_Vector); // Compute Each distance 

			if (NN_Vector.size() < K || distance <  Max_Near_Distance){
				Near_Matrix.push_back(NN_Vector);
				Near_Matrix_Distance.push_back(distance);
				max_idx = Where_is_Max_Idx(Near_Matrix_Distance);

				// -------- Debugging --------------
				// cout << Near_Matrix.size() << endl;
				// cout << Near_Matrix_Distance.size() << endl; 
				// cout << distance << endl; 
				// cout << max_idx << endl;

				// This occures errors 
				if (Near_Matrix.size() > K){
					Near_Matrix_Distance.erase(Near_Matrix_Distance.begin() + max_idx);
					Near_Matrix.erase(Near_Matrix.begin() + max_idx);
				}

				// Why did I do that? 
				max_idx = Where_is_Max_Idx(Near_Matrix_Distance);
				Max_Near_Distance = Near_Matrix_Distance[max_idx];
			}

		}

		int Count_Red = 0;
		int Count_Green = 0;
		int Count_Blue = 0;
		vector<int> Count_RGB;

		for (int idx = 0; idx < Near_Matrix.size(); idx++){
			if (isPresent(Train_Red_Matrix, Near_Matrix[idx])){
				Count_Red ++; 
			}
			else if (isPresent(Train_Green_Matrix, Near_Matrix[idx])){
				Count_Green ++; 
			}
			else if (isPresent(Train_Blue_Matrix, Near_Matrix[idx])){
				Count_Blue ++; 
			}
		}

		Count_RGB.push_back(Count_Red);
		Count_RGB.push_back(Count_Green);
		Count_RGB.push_back(Count_Blue);
		auto Max_Count = max_element(Count_RGB.begin(), Count_RGB.end());

		if (*Max_Count == Count_Red){
			My_Answer_Red.push_back(Target);
		}
		else if (*Max_Count == Count_Green){
			My_Answer_Green.push_back(Target);
		}
		else if (*Max_Count == Count_Blue){
			My_Answer_Blue.push_back(Target);
		}
		Near_Matrix.clear();  
		Near_Matrix_Distance.clear();   

	}

	/* ============== PERFORMANCE CHECK =============== */ 

	// cout << My_Answer_Red.size() << endl;
	// cout << My_Answer_Green.size() << endl;
	// cout << My_Answer_Blue.size() << endl;
	cout << "Accuracy : " << Performance_Check(My_Answer_Red, My_Answer_Green, My_Answer_Blue, Test_Red_Matrix, Test_Green_Matrix, Test_Blue_Matrix) << endl;

  	

  	return 0;
}