c++ - 逻辑错误 : Incorrect computation of mean centroid , Infinite Execution of , 'entries ' function - K means clustering for a set of points, in C++

Question

我正在编写一个用于 K 均值聚类的程序，以找到每个点应属于的聚类。此代码有 8 个点和 3 个簇。在我的代码中，“条目”函数以某种方式无限执行。我找不到哪里出错了。这是我遵循的逻辑:

1. 8个点的硬编码输入

2. 随机生成3个聚类中心

3. 计算每个点到 3 个聚类中心的距离，并使用 arr1[][] 存储距离。
4. 在cent_tally[][]中，存储每个点应该属于的簇的编号。例如。集群 1 为 0，集群 2 为 1，集群 3 为 2。(还在二维数组“arr1”的第 4 列中存储相同的值)。
5. 使用簇编号计算平均质心(簇中心)。对于每个点。
6. 再次调用'entries'函数来计算距离和簇号。每个点应该属于哪个，但这次使用第二组质心。即平均质心。
7. 如果第二组簇号。对于每个点，(存储在 cent_tally[][] 的第 2 列中)与簇编号相符。对于使用随机生成的质心(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 centroids



for(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;
}

我犯的另一个错误是没有在“entries”函数的开头初始化 flag=0!

现在我的条目函数不是无限运行的，但我现在有以下问题:

1. 在使用第一组质心后，平均质心(从第二组质心开始)计算错误
2. 我试图通过使用 count2 作为索引将 arr[][] 的第四列最终复制到 cent_tally[][] 的第一列和下一列，但 cent-tally 的第一列不匹配arr[][]的第4列

我无法弄清楚哪里出了问题。

Answer 1

由于 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;
}

entries 函数永远不会返回 8。

另一方面，中的这个逻辑意味着函数

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]);
}

循环直到从 entries 函数返回 8。

这似乎是无限循环的原因。考虑调整这两点之一的行为。