最大最小距离算法——模式识别

参考链接： 最小最大算法

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <string>

#include <string.h>

#include <map>

#include <set>

#include <queue>

#include <deque>

#include <list>

#include <bitset>

#include <stack>

#include <stdlib.h>

using namespace std;

#define C 0.5

int main()

{

    int x[100][3],z[100][3],b[100];//x[][]：输入点坐标；z[][]:标记第几个聚类中心;w[][]用于标记各点到聚类中心距离最小值

    int i,j,h,N,flag,k=1,f=1;//f:聚类中心个数    ;b[]用于记录与聚类中心最大距离的点标号;dd[][]:在循环体中记录各点与聚类中心距离

    float w[100][100],dd[100][100],Q,max1,max2,distance[100];//distance[]:记并求出录第二个聚类点

    b[0]=0;

    printf("    最大最小距离分类法\n\n");

    printf("请输入坐标数N：");

    scanf("%d",&N);

    printf("请输入各点的坐标:\n");

    for(i=0;i<N;i++)

    {

        x[i][0]=i+1;//x[0[0]=1,x[1][0]=2...

        for(j=1;j<=2;j++)//x数组为三列数组，其中第一列用来编号记录个点，编号从1开始，x1,x2。如：x[3][3]={{1,0,0},{2,3,8},{3,2,2}}

            scanf("%d",&x[i][j]);

    }

    printf("输入的点为：\n");

    for(i=0;i<N;i++)//打印输出输入的点坐标；

    {

        printf("x%d:",x[i][0]);

        printf("{%d,%d} ",x[i][1],x[i][2]);

    }

    z[0][0]=x[0][0],z[0][1]=x[0][1],z[0][2]=x[0][2];

    printf("\n取输入的第一个点为第一聚类中心z%d:{%d,%d}\n",x[0][0],x[0][1],x[0][2]);

    for(i=0;i<N;i++)//循环计算各点到z1的距离

    {

        distance[i]=sqrt((x[i][1]-z[0][1])*(x[i][1]-z[0][1])+(x[i][2]-z[0][2])*(x[i][2]-z[0][2]));

        printf("第%d个点(%d,%d)到z%d(%d,%d)的距离是：%f\n",(i+1),x[i][1],x[i][2],z[0][0],z[0][1],z[0][2],distance[i]);

    }

    max1=distance[0];

    for(j=0;j<=N;j++)

    {

        if(distance[j]>max1)

        {max1=distance[j];

            flag=j;}

    }

    b[f]=flag;

    printf("到z%d{%d,%d}距离最远的点(既聚类点)是：(%d,%d)\n",z[0][0],z[0][1],z[0][2],x[flag][1],x[flag][2]);

    Q=C*max1;

    printf("阈值Q是：%f\n",Q);

    while(k!=0)

    {

        for(j=0;j<=f;j++)

        {

            printf("各点到各聚类中心距离为\n");

            for(i=0;i<N;i++)

            {

                for(j=0;j<=f;j++)

                {

                    dd[i][j]=(float)sqrt((x[i][1]-x[b[j]][1])*(x[i][1]-x[b[j]][1])+(x[i][2]-x[b[j]][2])*(x[i][2]-x[b[j]][2]));

                    printf("%f ",dd[i][j]);

                } printf("\n");

            }

        }

        for(i=0;i<N;i++)//找出各点到聚类中心距离的最小值

        {    w[i][0]=dd[i][0];

            for(j=0;j<=f;j++)

            {

                if(w[i][0]>=dd[i][j])//if(w[i][0]>dd[i][j]不对，这样会导致最后打印不出第一类的各点；

                {w[i][0]=dd[i][j];

                    w[i][2]=j;}

            }

            w[i][1]=i;

        }

        printf("各坐标点到聚类中心最小距离是：\n");

        for(i=0;i<N;i++)

            printf("%f\n",w[i][0]);

        max2=w[0][0];

        for(i=0;i<N;i++)

        {

            if(max2<w[i][0])

            {max2=w[i][0];

                h=i;}

        }

        if(max2>Q)

        {

            f=f+1;

            b[f]=h;

            printf("\n由于到聚类中心距离中有比阈值大的，新聚类中心产生");

            printf("x%d:{%d,%d}\n",h+1,x[h][1],x[h][2]);

        }

        else

        {

            printf("各坐标点到聚类中心距离均小于阈值%f,分类结束\n",Q);

            k=0;

            printf("一共产生%d类聚类中心\n",f+1);

                   for(i=0;i<=f;i++)

            { printf("第%d类聚类中心包含坐标有：",i+1);

                for(j=0;j<N;j++)

                {

                    if(w[j][2]==i)

                    {printf("x%d:(%d,%d) ",j+1,x[j][1],x[j][2]); }

                }

                printf("\n");

            }

                   }

                   }

                   return 0;

}