Логическая ошибка: неверное вычисление среднего центроида, бесконечное выполнение, функция «entry» — K означает кластеризацию для набора точек в переполнении стека

Я пишу программу для кластеризации K-средних, чтобы найти кластеры, к которым должна принадлежать каждая точка. Для этого кода есть 8 точек и 3 кластера. Каким-то образом в моем коде функция «записи» выполняется бесконечно. Я не мог найти, где я ошибся. Это логика, которой я придерживаюсь:

  1. Жестко закодированный ввод 8 баллов

  2. Произвольно генерировать 3 кластерных центра

  3. Рассчитайте расстояние каждой точки от 3 центров кластера и используйте arr1 [] [] для хранения расстояний.
  4. В cent_tally [] [] сохраните номер кластера, к которому должна принадлежать каждая точка. например. 0 для кластера 1, 1 для кластера 2 и 2 для кластера 3. (Также сохраняются те же значения в 4-м столбце 2-D массива, ‘arr1’).
  5. Рассчитать средние центроиды (центры кластеров), используя кластеры №. за каждую точку.
  6. Снова вызовите функцию «записи» для расчета расстояний и кластера №. к которой должна принадлежать каждая точка, но на этот раз используется 2-й набор centroids.i.e. средние центроиды.
  7. Если второй набор кластеров нет. для каждой точки (хранится во 2-м столбце cent_tally [] []) совпадает с номерами кластеров. для каждой точки используйте случайно сгенерированные центроиды (первый столбец cent_tally [] []), затем напечатайте cent_tally [] [], напечатайте arr1 [] [] и остановите.

Вот код:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#include<math.h>

using namespace std;

class points
{
float x;
float y;

static int point_cnt;
static int flag;
int cent_tally[8][4];
int count2;struct centroids
{
float cx;
float cy;
}c[3];

public:

points()
{
count2=0;

for(int i=0;i<3;i++)
{
c[i].cx=0;
c[i].cy=0;
}

for(int i=0;i<8;i++)
{
for(int j=0;j<4;j++)
{
cent_tally[i][j]=0;
}
}

}void means(points * );

float dist(float a,float b,float c,float d);

int entries(float c11x,float c11y,float c22x,float c22y,float c33x,float c33y,float arr[8][4],points *p);

};

int points::point_cnt=8;
int points::flag=0;

int points::entries(float c11x,float c11y,float c22x,float c22y,float c33x,float c33y,float arr[8][4],points *p)
{

float sum1x,sum1y,sum2x,sum2y,sum3x,sum3y; //to calC mean centroids
sum1x=0;
sum1y=0;
sum2x=0;
sum2y=0;
sum3x=0;
sum3y=0;

int cnt1,cnt2,cnt3;
cnt1=0;
cnt2=0;
cnt3=0;                                    //to calC mean centroids//count2=0;
//in the first iteration of entries, count2=0
cout<<"count 2 value:"<<count2<<endl;

for(int k=0;k<8;k++) //0 to 7 for 8 points
{

arr[k][0]=dist(p[k].x,p[k].y,c11x,c11y);
arr[k][1]=dist(p[k].x,p[k].y,c22x,c22y);
arr[k][2]=dist(p[k].x,p[k].y,c33x,c33y);float temp,min;
temp = (arr[k][0] < arr[k][1])    ? arr[k][0] : arr[k][1];
min =  (arr[k][2] < temp) ? arr[k][2] : temp;

//cout<<"mins:"<<min<<endl;
for(int l=0;l<3;l++)
{
if(arr[k][l]==min)
{
arr[k][3]=l; //0 for c1, 1 for c2, 2 for c3 in 4th column of table
cent_tally[k][count2]=l;
if(l==0)
{
sum1x+=p[k].x;
sum1y+=p[k].y;
cnt1++;
}
else if (l==1)
{
sum2x+=p[k].x;
sum2y+=p[k].y;
cnt2++;

}
else if (l==2)
{   sum3x+=p[k].x;
sum3y+=p[k].y;
cnt3++;
}
else
{
cout<<"";
}
}
}

}

count2++;//for index into cent_tally

//finding mean centroid ...//re entering values of mean centroid into the same structure created for 3 centroid coordinates ...

c[0].cx=sum1x/cnt1;
c[0].cy=sum1y/cnt1;

c[1].cx=sum2x/cnt2;
c[1].cy=sum2y/cnt2;

c[2].cx=sum3x/cnt3;
c[2].cy=sum3y/cnt3;
//now the struct contains mean centroidsfor(int i=0;i<8;i++)
{ int temp=0;
temp=count2-1;
if(cent_tally[i][temp]==cent_tally[i][count2])
{
flag++;
}
else
{
break;
}
}if(flag==8)
{
cout<<"centroids found: "<<endl;
for(int i=0;i<8;i++)
{
for(int j=0;j<4;j++)
{
cout<<" "<<cent_tally[i][j];
}
cout<<endl;
}

return 0;

}

else
{

return flag;
}

//while(flag!=8) //WHILE ALL 8 entries of latest 2 columns of cent_tally are not matching
//{
//entries(c[0].cx,c[0].cy,c[1].cx,c[1].cy,c[2].cx,c[2].cy,arr,&p[0]);

//}
}

float points::dist(float a,float b,float c,float d)

{

return (abs(a-c)+abs(b-d));}
void points:: means(points * p)
{

float arr1[8][4]; //array to store dist b/w each point and cluster center and cluster values for each point after distance calculation
float arr2[8][4];

//let c1 c2 and c3 be initial cluster centers
//float c1x,c2x,c1y,c2y,c3x,c3y;

//Can take input from a file also...
p[0].x=2;
p[0].y=2;

p[1].x=1;
p[1].y=14;

p[2].x=10;
p[2].y=7;

p[3].x=1;
p[3].y=11;

p[4].x=3;
p[4].y=4;

p[5].x=11;
p[5].y=8;

p[6].x=4;
p[6].y=3;

p[7].x=12;
p[7].y=2;srand ( time(NULL) );
for(int i=0;i<3;i++) //for 3 cluster centers, we need 3 centroids
{
int randIndex=1+rand()%(point_cnt-i-1);//where 8 is the no. of points
c[i].cx=p[randIndex].x;
c[i].cy=p[randIndex].y;

}int val;

val=entries(c[0].cx,c[0].cy,c[1].cx,c[1].cy,c[2].cx,c[2].cy,arr1,&p[0]);

while(val!=8)
{
val=entries(c[0].cx,c[0].cy,c[1].cx,c[1].cy,c[2].cx,c[2].cy,arr1,&p[0]);
}

for(int i=0;i<8;i++)
{
for(int j=0;j<4;j++)
{

cout<<arr1[i][j]<<" ";

}
cout<<endl;
}
//displaying 1st table

//2.1 calculate mean centroid
//2.2 re enter new values in same table
//2.3 first 2 columns of cent_tally
//2.4 if not same repeat step 2.1

}int main()

{

int c=8;points p[8];

points obj;
obj.means(&p[0]);

return 0;
}

Еще одна ошибка, которую я допустил, это не инициализация flag = 0 в начале функции ‘records’!

Теперь моя запись не работает бесконечно, но у меня сейчас следующие проблемы:

  1. Средний центроид (второй набор центроидов и далее) вычисляется неправильно после использования первого набора центроидов
  2. Я пытаюсь скопировать четвертый столбец arr [] [] в первый и последующие столбцы, в конце концов, из cent_tally [] [], используя count2 в качестве индекса, но первый столбец в центре не соответствует 4-му столбцу обр [] []

Я не могу понять, где я ошибся.

0

Решение

Благодаря этой логике в entries функция

if(flag==8)
{
cout<<"centroids found: "<<endl;
for(int i=0;i<8;i++)
{
for(int j=0;j<4;j++)
{
cout<<" "<<cent_tally[i][j];
}
cout<<endl;
}

return 0;

}

else
{

return flag;
}

8 никогда не вернется из entries функция.

С другой стороны, эта логика в means функция

while(val!=8)
{
val=entries(c[0].cx,c[0].cy,c[1].cx,c[1].cy,c[2].cx,c[2].cy,arr1,&p[0]);
}

петли, пока 8 не возвращается из entries функция.

Это кажется причиной бесконечного цикла. Подумайте о корректировке поведения одного из этих двух пунктов.

1

Другие решения

Причины неверного вычисления среднего центроида:

  1. Самое важное: в цикле for, где l работает от 0 до 2, если два значения расстояний одинаковы, счетчики увеличиваются для двух значений l, поэтому можно использовать флаг, чтобы гарантировать, что принимается только одно минимальное расстояние. рассмотрение, для решения центроида, которому принадлежит точка.
  2. Abs принимает целочисленные значения и слышит, что мы имеем дело с плавающей точкой, поэтому нам нужно определить функцию, которая обрабатывает значения с плавающей точкой.
  3. Флаг должен быть установлен в 0 в начале функции ‘entry’.
  4. Если два случайно сгенерированных центроида одинаковы, вы можете не получить правильный ответ.
0