21xrx.com
2024-12-26 02:49:31 Thursday
登录
文章检索 我的文章 写文章
K-means算法的C语言实现
2023-11-21 22:04:51 深夜i     --     --
means algorithm language

K-means算法是一种经典的聚类算法，常用于数据挖掘和模式识别领域。本文将介绍K-means算法的C语言实现。

K-means算法的思想非常简单，它将数据样本划分为k个簇，每个簇包含具有相似特征的数据点。算法的具体步骤如下：

1. 随机选择k个初始中心点。这些中心点可以是随机选择的，也可以是从数据集中选择的。

2. 将所有数据点分配给距离其最近的中心点所在的簇。这一步是通过计算每个中心点与数据点之间的距离，然后将数据点分配给最近的中心点所在的簇。

3. 重新计算每个簇的中心点。将属于同一簇的数据点的特征向量求和后取平均值，得到新的中心点。

4. 重复步骤2和步骤3，直到中心点不发生变化或达到预定的迭代次数。

下面是K-means算法的C语言实现：



#include <stdio.h>


#include <stdlib.h>


#include <math.h>


#define MAX_ITERATIONS 100


// 数据点结构体


typedef struct


  double x;


  double y;


Point;


// 中心点结构体


typedef struct


  double x;


  double y;


  int count;


Centroid;


// 计算两个点之间的距离


double distance(Point p1, Point p2) {


  return sqrt(pow((p1.x - p2.x), 2) + pow((p1.y - p2.y), 2));


}


// K-means算法


void kMeans(Point *points, int numPoints, Centroid *centroids, int numCentroids) {


  int i, j;


  int iter = 0;


  double minDistance, distance;


  int minCentroidIndex;


  Centroid previousCentroids[numCentroids];


  // 初始化中心点


  for (i = 0; i < numCentroids; i++) {


    centroids[i].x = points[i].x;


    centroids[i].y = points[i].y;


    centroids[i].count = 0;


  }


  // 迭代计算中心点


  while (iter < MAX_ITERATIONS) {


    // 保存上一次的中心点


    for (i = 0; i < numCentroids; i++) {


      previousCentroids[i] = centroids[i];


    }


    // 分配数据点到最近的中心点


    for (i = 0; i < numPoints; i++) {


      minDistance = distance(points[i], centroids[0]);


      minCentroidIndex = 0;


      for (j = 1; j < numCentroids; j++) {


        distance = distance(points[i], centroids[j]);


        if (distance < minDistance)


          minDistance = distance;


          minCentroidIndex = j;


        


      }


      centroids[minCentroidIndex].count++;


      centroids[minCentroidIndex].x += points[i].x;


      centroids[minCentroidIndex].y += points[i].y;


    }


    // 计算新的中心点


    for (i = 0; i < numCentroids; i++) {


      centroids[i].x /= centroids[i].count;


      centroids[i].y /= centroids[i].count;


    }


    // 检查中心点是否变化


    int isConverged = 1;


    for (i = 0; i < numCentroids; i++) {


      if (previousCentroids[i].x != centroids[i].x || previousCentroids[i].y != centroids[i].y)


        isConverged = 0;


        break;


      


    }


    if (isConverged)


      break;


    


    iter++;


  }


}


int main() {


  // 定义数据点和中心点


  Point points[] = { 1.0, 2.0, 3.0, 10.0, 11.0, 12.0};


  int numPoints = sizeof(points) / sizeof(Point);


  Centroid centroids[] = {0.0, 10.0};


  int numCentroids = sizeof(centroids) / sizeof(Centroid);


  // 调用K-means算法


  kMeans(points, numPoints, centroids, numCentroids);


  // 输出结果


  for (int i = 0; i < numCentroids; i++) {


    printf("Cluster %d: (%f, %f)\n", i+1, centroids[i].x, centroids[i].y);


  }


  return 0;


}

该C语言实现的K-means算法接收一个数据点数组和中心点数组作为输入，并输出几个簇的中心点。在主函数中，我们定义了一个简单的数据集和两个初始中心点。算法将根据数据点的特征进行聚类并计算出新的中心点。最后，输出每个簇的中心点。

K-means算法的C语言实现虽然简单，但能够有效地对数据进行聚类。通过该实现，我们可以更好地理解K-means算法的原理和实现方法。同时，我们也可以根据实际需求对代码进行调整和扩展，以满足不同的应用场景。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复