c语言实现K均值算法

1.算法简介

   k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

2.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N   11
#define k   3

typedef struct {
    float x;
    float y;
} Point;

Point point[N] = {
    { 2.0, 10.0 }, { 2.0, 5.0 }, { 8.0, 4.0 }, { 5.0, 8.0 }, { 7.0, 5.0 },
    { 6.0,  4.0 }, { 1.0, 2.0 }, { 4.0, 9.0 }, { 7.0, 3.0 }, { 1.0, 3.0 },
    { 3.0,  9.0 }
};

Point mean[k];
int center[N];

float getdistance(Point point1, Point point2);
void cluster();
float gete();
void getmean(int center[N]);

int main()
{
    int number = 0;
    float temp1, temp2;

    //初始化k个中心点,这里选择给定中心点，而不是随机生成，需要更多的先验知识
    //若没有相关先验知识，可选择随机生成初始中心点
    mean[0].x = point[0].x;
    mean[0].y = point[0].y;

    mean[1].x = point[3].x;
    mean[1].y = point[3].y;

    mean[2].x = point[6].x;
    mean[2].y = point[6].y;

    //第一次聚类
    cluster();

    //number统计进行了几次聚类
    number++;

    //对第一次聚类的结果进行误差平方和的计算   
    temp1 = gete();
    printf("the error1 is:%f\n", temp1);

    //针对第一次聚类的结果，重新计算聚类中心
    getmean(center);

    //第二次聚类
    cluster();
    number++;
    temp2 = gete();
    printf("the error2 is:%f\n", temp2);

    //迭代循环，直到两次迭代误差的差值在一定阈值范围内，则迭代停止
    while(fabs(temp1 - temp2) > 0.1)
    {
        temp1 = temp2;
        getmean(center);
        cluster();
        temp2 = gete();
        number++;

        printf("the error%d is:%f\n", number,temp2);
    }

    printf("the total number of cluster is:%d\n", number);

    return 0;
}

//计算距离函数，欧式距离
float getdistance(Point point1, Point point2)
{
    float d;

    d = sqrt((point1.x - point2.x)*(point1.x - point2.x) + (point1.y - point2.y)*(point1.y - point2.y));

    return d;
}

//聚类函数
void cluster()
{
    float distance[N][k];
    float min;
    int i, j;

    for(i=0; i<N; i++)
    {
        for(j=0; j<k; j++)
        {
            distance[i][j] = getdistance(point[i], mean[j]);
        }

        min = 9999.0;

        for(j=0; j<k; j++)
        {
            if(distance[i][j] < min)
            {
                min = distance[i][j];
                center[i] = j;
            }
        }

        printf("(%.0f,%.0f)\t in cluster-%d\n", point[i].x, point[i].y, center[i] + 1);
    }
}

//聚类后误差计算函数
float gete()
{
    float cnt=0, sum=0;
    int i, j;

    for(i=0; i<N; i++)
    {
        for(j=0; j<k; j++)
        {
            if(center[i] == j)
            {
                cnt = getdistance(point[i], mean[j]);
            }
        }

        sum += cnt;     
    }

    return sum;
}

//重新计算聚类中心
void getmean(int center[N])
{
    Point sum;
    int count;
    int i, j;

    for(i=0; i<k; i++)
    {
        sum.x = 0.0;
        sum.y = 0.0;
        count = 0;

        for(j=0; j<N; j++)
        {
            if(center[j] == i)
            {
                sum.x += point[j].x;
                sum.y += point[j].y;
                count++;
            }
        }

        mean[i].x = sum.x / count;
        mean[i].y = sum.y / count;
    }

    for(i=0; i<k; i++)
    {
        printf("the new center point of %d is:\t(%f,%f)\n", i + 1, mean[i].x, mean[i].y);
    }
}

3.编译源码

$ gcc -o example example.c -lm

4.运行程序及其结果

./example
(2,10)   in cluster-1
(2,5)    in cluster-3
(8,4)    in cluster-2
(5,8)    in cluster-2
(7,5)    in cluster-2
(6,4)    in cluster-2
(1,2)    in cluster-3
(4,9)    in cluster-2
(7,3)    in cluster-2
(1,3)    in cluster-3
(3,9)    in cluster-1
the error1 is:25.104525
the new center point of 1 is:   (2.500000,9.500000)
the new center point of 2 is:   (6.166667,5.500000)
the new center point of 3 is:   (1.333333,3.333333)
(2,10)   in cluster-1
(2,5)    in cluster-3
(8,4)    in cluster-2
(5,8)    in cluster-2
(7,5)    in cluster-2
(6,4)    in cluster-2
(1,2)    in cluster-3
(4,9)    in cluster-1
(7,3)    in cluster-2
(1,3)    in cluster-3
(3,9)    in cluster-1
the error2 is:16.880072
the new center point of 1 is:   (3.000000,9.333333)
the new center point of 2 is:   (6.600000,4.800000)
the new center point of 3 is:   (1.333333,3.333333)
(2,10)   in cluster-1
(2,5)    in cluster-3
(8,4)    in cluster-2
(5,8)    in cluster-1
(7,5)    in cluster-2
(6,4)    in cluster-2
(1,2)    in cluster-3
(4,9)    in cluster-1
(7,3)    in cluster-2
(1,3)    in cluster-3
(3,9)    in cluster-1
the error3 is:13.537380
the new center point of 1 is:   (3.500000,9.000000)
the new center point of 2 is:   (7.000000,4.000000)
the new center point of 3 is:   (1.333333,3.333333)
(2,10)   in cluster-1
(2,5)    in cluster-3
(8,4)    in cluster-2
(5,8)    in cluster-1
(7,5)    in cluster-2
(6,4)    in cluster-2
(1,2)    in cluster-3
(4,9)    in cluster-1
(7,3)    in cluster-2
(1,3)    in cluster-3
(3,9)    in cluster-1
the error4 is:12.246379
the new center point of 1 is:   (3.500000,9.000000)
the new center point of 2 is:   (7.000000,4.000000)
the new center point of 3 is:   (1.333333,3.333333)
(2,10)   in cluster-1
(2,5)    in cluster-3
(8,4)    in cluster-2
(5,8)    in cluster-1
(7,5)    in cluster-2
(6,4)    in cluster-2
(1,2)    in cluster-3
(4,9)    in cluster-1
(7,3)    in cluster-2
(1,3)    in cluster-3
(3,9)    in cluster-1
the error5 is:12.246379
the total number of cluster is:5