模糊c均值聚类与k均值聚类区别

k均值聚类

k均值聚类的实现中，把每个样本划分到单一的类别中，亦即是每个样本只能属于一种类别，不能属于多种类别。这样的划分，称为硬划分。

模糊c均值均类

为了解决硬划分所带来的问题，因此有了称为软划分的聚类算法，这一类算法中，每个样本不再只能属于一种类别，而是对于每个样本，都有对应的隶属度数组，数组里的每一个元素代表该样本属于某种类别的程度。而该样本的隶属度数组中的总值等于1。
其目标方程以及优化的推导过程可以参照下述链接，个人认为推导过程十分详细。
模糊c均值聚类推导

实现步骤：

根据相关的推导结果，具体实现步骤如下：

1. 初始化数据集
2. 初始化隶属度数组
3. 根据隶属度数组更新聚类中心
4. 根据聚类中心更新隶属度数组
5. 是否达到结束条件，没有达到则重复2-4步骤。

实现

各个相关函数都有注释。

#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
typedef struct{
    double x;
    double y;
} Position;

//随机生成二维数据点
//len:节点数量
//range：节点x、y值的范围
Position *randomPosition(int len, int range){
    srand((unsigned)time(NULL));
    Position *allPos = (Position *)malloc(len * sizeof(Position));

    short a = 1; //人为差异量
    for (int i = 0; i < len; ++i)
    {
        if (a)
        {
            allPos[i].x = (double)rand() / 2147483647 * range;
            allPos[i].y = (double)rand() / 2147483647 * range;
            a = 0;
        }
        else if (!a)
        {
            allPos[i].x = (double)rand() / 2147483647 * range+50;
            allPos[i].y = (double)rand() / 2147483647 * range+50;
            a = 1;
        }
    }
    return allPos;
}
//fcm初始化：隶属度矩阵
//posNum：节点数量
//clusterNum：聚类中心数量
double **init(int posNum, int clusterNum){
    double **u = (double **)malloc(sizeof(double *) * clusterNum);
    for (int i = 0; i <clusterNum; ++i)
    {
        u[i] = (double *)malloc(sizeof(double) * posNum);
    }
    srand((unsigned)time(NULL));
    double sum;
    //初始化u：sigmaU[i]=1
    for (int i = 0; i < posNum; ++i)
    {
        sum=1;
        for (int x = 0; x < clusterNum - 1; ++x)
        {
            u[x][i] = ((double)rand() / 2147483647) * sum;
            sum -= u[x][i];
            printf("u[%d][%d]:%f ",x,i,u[x][i]);
        }
        u[clusterNum-1][i]=sum;
        printf("u[%d][%d]:%f\n",clusterNum-1,i,u[clusterNum-1][i]);
    }
    return u;
}
//输出所有数据点
//allPos：节点数组
//len：节点数量
void outputPos(Position *allPos, int len){

    for (int i = 0; i < len; ++i)
        printf("position %d:(%f,%f)\n", i, allPos[i].x, allPos[i].y);
    return;
}
//所有隶属于聚类中心i的点的隶属程度和
//u：隶属度矩阵
//posNum：节点数量
//i:第i个聚类中心
//m：隶属度因子
double sumUi(double** u,int posNum,int i,int m){
    double res=0;
    for(int x=0;x<posNum;++x)
        res+=pow(u[i][x],m);
    return res;
}
//所有隶属于聚类中心i的点的x坐标的和
//u：隶属度矩阵
//allPos:节点数组
//posNum：节点数量
//i:第i个聚类中心
//m：隶属度因子
double sumXi(double** u,Position* allPos,int posNum,int i,int m){
    double res=0;
    for(int x=0;x<posNum;++x)
        res+=allPos[x].x*pow(u[i][x],m);
    return res;
}
//所有隶属于聚类中心i的点的y坐标的和
//u：隶属度矩阵
//posNum：节点数量
//i:第i个聚类中心
//m：隶属度因子
double sumYi(double** u,Position* allPos,int posNum,int i,int m){
    double res=0;
    for(int x=0;x<posNum;++x)
        res+=allPos[x].y*pow(u[i][x],m);
    return res;
}
//第j个节点到所有聚类中心距离总和
//pos:第j个节点
//cluster:聚类中心数组
//clusterNum：聚类中心数量
//m：隶属度因子
double sumDis(Position pos,Position* cluster,int clusterNum,int m){
    double res=0;
    for(int i=0;i<clusterNum;++i)
        res+=(double)1/pow(pow(pos.x-cluster[i].x,2)+pow(pos.y-cluster[i].y,2),(double)1/(m-1));
    return res;
}
//更新聚类中心
//allPos:节点数组
//cluster:聚类中心数组
//u：隶属度矩阵
//posNum：节点数量
//clusterNum：聚类中心数量
//m：隶属度因子
void updateCluster(Position* allPos,Position* cluster,double** u,int posNum,int clusterNum,int m){
    for(int i=0;i<clusterNum;++i){
        cluster[i].x=sumXi(u,allPos,posNum,i,m)/sumUi(u,posNum,i,m);
        cluster[i].y=sumYi(u,allPos,posNum,i,m)/sumUi(u,posNum,i,m);
    }
}
//更新隶属度矩阵
//allPos:节点数组
//cluster:聚类中心数组
//u：隶属度矩阵
//posNum：节点数量
//clusterNum：聚类中心数量
//m：隶属度因子
void updateU(Position* allPos,Position* cluster,double** u,int posNum,int clusterNum,int m){
    double disXI;
    for(int i=0;i<clusterNum;++i)
    for(int x=0;x<posNum;++x){
        disXI=pow(pow(allPos[x].x-cluster[i].x,2)+pow(allPos[x].y-cluster[i].y,2),(double)1/(m-1));
        u[i][x]=(double)1/(disXI*sumDis(allPos[x],cluster,clusterNum,m));
    }
}
//输出目标函数
//allPos:节点数组
//cluster:聚类中心数组
//u：隶属度矩阵
//posNum：节点数量
//clusterNum：聚类中心数量
//m：隶属度因子
void outpuCost_fun(Position* allPos,Position* cluster,double** u,int posNum,int clusterNum,int m){
    double res=0;
    for(int i=0;i<clusterNum;++i)
    for(int x=0;x<posNum;++x)
        res+=(pow(u[i][x],m)*(pow(allPos[x].x-cluster[i].x,2)+pow(allPos[x].y-cluster[i].y,2)));
    printf("costFun:%f\n",res);
}
//..略，同上
void outputU(double** u,int posNum,int clusterNum){
    for(int i=0;i<posNum;++i){
        for(int x=0;x<clusterNum;++x)
            printf("u[%d][%d]:%f ",x,i,u[x][i]);
        printf("\n");
    }
}
void fuzzy_Cmeans(int posNum,int clusterNum, int m, int iterTime,int range)
{
    Position* allPos=randomPosition(posNum,range);
    Position* cluster=(Position*)malloc(sizeof(Position)*clusterNum);
    double** u=init(posNum,clusterNum);
    for (int i = 0; i < iterTime; ++i)
    {   
        updateCluster(allPos,cluster,u,posNum,clusterNum,m);
        updateU(allPos,cluster,u,posNum,clusterNum,m);
        outpuCost_fun(allPos,cluster,u,posNum,clusterNum,m);
        //outputU(u,posNum,clusterNum);
    }
}
int main(){
    fuzzy_Cmeans(100,10,3,500,500);
    return 0;
}

结果

可以看到，其目标函数的值是逐渐减少的，最后达到稳定的状态。