포인트가 포인트 클러스터 내에 있는지 확인하는 방법

Question

벡터 양자화에 대한 숙제를 묻는 질문입니다.

포인트 클러스터의 중심을 감지하기 위해 다소 고전적인 알고리즘을 구현했습니다. 그러나 입력 데이터에는 여러 클러스터가 있습니다 (클러스터 수와 총 입력 수를 알고 있음). 각 클러스터의 중심을 찾아야하지만 어떤 점이 클러스터를 만드는지는 알 수 없습니다. 그래서 내 미래의 중심점을 내부 또는 클러스터 근처의 다른 어떤 초기화 된 중심점보다 가까운 곳에 초기화하면 알고리즘이 반복되어 올바른 중심으로 이동할 수 있습니다.

그러나 제대로 초기화하는 방법을 모르겠다. 무작위로 초기화하고 두 센터가 서로 너무 가깝고 센터가 입력 포인트에서 너무 멀리 떨어져 있는지 확인하지만이 방법은 매개 변수화가 쉽지 않습니다. 즉 "컴퓨팅"시간을 많이 차지하거나 올바른 센터를 확보하지 못합니다. .

제 아이디어는 간단합니다. 무작위로 초기화하고 포인트가 클러스터 내에 있는지 확인하십시오. 누군가 내가 그걸 어떻게 할 수 있는지 알고 있습니까? 내가 클러스터의 한계를 모르기 때문에 나는 다각형을 만들 수 없다. C로 구현하는 것을 선호하지만 아이디어 만 생각하면됩니다.

편집 : 입력 데이터의 예 :

내 코드 :

#include <stdio.h> 
#include <string.h> 
#include <math.h> 
#include <stdlib.h> 
#include <time.h> 
#include <float.h> 

#define TRAINING_CYCLE 10000 
#define LEARNING_RATE 0.001 
#define CENTROID_DISTANCE_SCALE 0.7 //used for setting a minimal distance between centroids 
#define CENTROID_POINT_SCALE 0.1 
#define CLUSTER_SIZE_PERCENTAGE 0.3 

//User:  REMOVED 
//Password: REMOVED 

typedef enum { false, true } bool; 

typedef struct point{ 
    double x; 
    double y; 
} point; 

int nbOfClusters; 

double in1[1000]; 
double in2[1000]; 


point centers[100]; //later it is limited by number of clusters 

int dataSize=0; 
double maxX1, maxY1, maxX2, maxY2=0; //maximums of each data set 
double deltaX, deltaY=0; //error toleration of each axis 

double getAbs(double n){ 
    if (n>=0){ 
     return n; 
    } else { 
     return (-1)*n; 
    } 
} 

int findNearestCentroid(point p1){ //returns the location in the table of the nearest centroid to the argument point 
    double distance=DBL_MAX; 
    int nearest=0; 
    for (int i=0; i<nbOfClusters; i++){ 
     double distance_temp = (p1.x-centers[i].x)*(p1.x-centers[i].x)+(p1.y-centers[i].y)*(p1.y-centers[i].y); 
     if (distance_temp < distance){ 
      distance=distance_temp; 
      nearest=i; 
     } 
    } 
    return nearest; 
} 

double getDistance(point p1, point p2){ 
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 
} 

bool isCentroidsNear(double minDistance){ 

    for (int i=0;i<nbOfClusters;i++){ 
     for (int j=0; j<nbOfClusters; j++){ 
      if (i != j){ 
       double temp_distance=getDistance(centers[i],centers[j]); 
       if (temp_distance<minDistance){ // the distance shouldn't be small 
        return true; 
       } 
      } 
     } 
    } 
    return false; //if nothing hit the condition, there is no centroid too close to another 
} 
point findNearestInput(int centroid){ //returns the location in the table of the nearest centroid to the argument point 
    double distance=DBL_MAX; 
    point returnPoint; 
    int nearest=0; 
    for (int i=0; i<nbOfClusters; i++){ 
     double distance_temp = (in1[i]-centers[centroid].x)*(in1[i]-centers[centroid].x)+(in2[i]-centers[centroid].y)*(in2[i]-centers[centroid].y); 
     if (distance_temp < distance){ 
      distance=distance_temp; 
      nearest=i; 
     } 
    } 
    returnPoint.x=in1[nearest]; 
    returnPoint.y=in2[nearest]; 
    return returnPoint; 
} 

bool isPointNear(double minDistance){ 
    for(int i=0; i<nbOfClusters; i++){ 
     double distance=getDistance(findNearestInput(i),centers[i]); //the distance to the nearest point 
     if(distance>minDistance){ 
      return true; 
     } 
    } 
    return false; 
} 

bool isCountNearPoints(double distance){ 
    int counter=0; 
    for(int i=0;i<nbOfClusters;i++){ 
     point p; 
     for(int j=0; j<dataSize; j++){ 
      p.x=in1[j]; 
      p.y=in2[j]; 
      double tempDistance=getDistance(p,centers[i]); 
      if (tempDistance<distance){ 
       counter++; 
      } 
     } 
     //this is the number of points that the centroid should be near to 
     int minNearPoints = dataSize/nbOfClusters*CLUSTER_SIZE_PERCENTAGE; 
     if (counter<minNearPoints){ 
      return true; 
     } 
    } 
    return false; 
} 

int main() 
{ 
    char dummy[1]; 
    scanf("%c",&dummy[0]); 
    nbOfClusters=dummy[0]-'0'; 



    while (scanf("%lf,%lf", &in1[dataSize], &in2[dataSize]) != EOF){ 
     dataSize++; 
    } 


    //finding the maximums to determine the error toleration delta 

    for(int i =0; i< dataSize; i++){ 
     if(in1[i]>0 && in1[i] > maxX1){ 
      maxX1=in1[i]; 
     } 
     if(in2[i]>0 && in2[i]>maxY1){ 
      maxY1=in2[i]; 
     } 
     if(in1[i]<0 && in1[i] < maxX1){ 
      maxX2=in1[i]; 
     } 
     if(in2[i]<0 && in2[i] < maxY1){ 
      maxY2=in2[i]; 
     } 
    } 

    //double minDistance = CENTROID_DISTANCE_SCALE*sqrt((maxX1-maxX2)*(maxX1-maxX2)+(maxY1-maxY2)*(maxY1-maxY2)); 
    double minDistance = 1/nbOfClusters*sqrt((maxX1-maxX2)*(maxX1-maxX2)+(maxY1-maxY2)*(maxY1-maxY2)); 
    double pointMinDistance = CENTROID_POINT_SCALE*sqrt((maxX1-maxX2)*(maxX1-maxX2)+(maxY1-maxY2)*(maxY1-maxY2)); 

/* 
    do { //randomly generate centroids but have finally nothing near 
     for(int i=0; i<nbOfClusters; i++){ 
      centers[i].x=(double)rand()/RAND_MAX*2*(maxX1-maxX2)-(maxX1-maxX2); 
      centers[i].y=(double)rand()/RAND_MAX*2*(maxY1-maxY2)-(maxY1-maxY2); 
     } 
    //} while(isCentroidsNear(minDistance) || isCountNearPoints(pointMinDistance)); 
    } while(isCentroidsNear(minDistance) || isPointNear(pointMinDistance)); 
    //} while(isCentroidsNear(minDistance)); 
    */ 
    int randomInputs[50]; 
    bool isSame; 
    //generating nbOfClusters amount of random numbers from dataSize range that will later used to pick inputs 
    do { 
     do{ 
      //generate random numbers 
      for(int i=0; i<nbOfClusters; i++){ 
       randomInputs[i]=(int)((double)rand()/RAND_MAX*dataSize); 
      } 
      isSame = false; 
      //checking if the generated numbers are the same 
      for(int i=0; i<nbOfClusters-1; i++){ 
       for(int j=i+1; j<nbOfClusters; j++){ 
        if(randomInputs[i]==randomInputs[j]){ 
         isSame=true; 
         break; 
        } 
       } 
       if(isSame){ 
        break; 
       } 
      } 

     }while(isSame); 
     //assign centroids to the generated numbers 
     for (int i =0;i<nbOfClusters;i++){ 
      centers[i].x=in1[randomInputs[i]]; 
      centers[i].y=in2[randomInputs[i]]; 
     } 
    }while(isCentroidsNear(minDistance)); //if the centroids are too close, i.e. in the same cluster 
    //learning 
    point p1;//point for iteration 

    for (int ii=0; ii<TRAINING_CYCLE; ii++){ 
     for (int i=0; i<dataSize; i++){ 

      //construct a point 
      p1.x=in1[i]; 
      p1.y=in2[i]; 

      //find the nearest point and the distance to it 
      int nearPt=findNearestCentroid(p1); 
      double distance=getDistance(p1,centers[nearPt]); 

      //the distance that I want to move it 
      double deltaDistance=LEARNING_RATE*distance; 

      //moving the center on the DIRECTION of the other point 
      //the slope of the line passing through both 
      double slope=(in2[i]-centers[nearPt].y)/(in1[i]-centers[nearPt].x); 

      double dx,dy; 
      // finding how much the x needs to change => totalchange^2=dx^2+dy^2 but I know dy from dx 
      dx=sqrt(deltaDistance*deltaDistance/(1+slope*slope)); //dx=(totaldist^2/(1+slope^2) 


      //dx is always positive till now, so it should be neg. if the center is to the right of the point 
      if(centers[nearPt].x>in1[i]){ 
       dx=(-1)*dx; 
      } 
      dy=slope*dx; 
      //updating the center value 
      centers[nearPt].x += dx; 
      centers[nearPt].y += dy; 

     } 

    } 

    //printing the results 

    for (int i=0; i<nbOfClusters; i++){ 
     printf("%lf,%lf\n",centers[i].x,centers[i].y); 
    } 

    return 0; 
} 

Answer 1

일반적인 접근 방식은 오히려 균일 한 랜덤보다, 기존 데이터에서 포인트를 선택하는 것입니다.

데이터 모델에서 모든 포인트는 클러스터에 속하므로 기존 포인트를 선택하면 (모호한) 문제가 해결됩니다. 그렇습니까?