当前位置：首页 > 科技 > 软件

详解 C++ 实现 K-means 算法

来源：责编：时间：2024-04-19 09:22:26 89观看

导读一、K-means算法概述K-means算法是一种非常经典的聚类算法，其主要目的是将数据点划分为K个集群，以使得每个数据点与其所属集群的中心点（质心）的平方距离之和最小。这种算法在数据挖掘、图像处理、模式识别等领域有着广泛

一、K-means算法概述

K-means算法是一种非常经典的聚类算法，其主要目的是将数据点划分为K个集群，以使得每个数据点与其所属集群的中心点（质心）的平方距离之和最小。这种算法在数据挖掘、图像处理、模式识别等领域有着广泛的应用。

二、K-means算法的基本原理

K-means算法的基本原理相对简单直观。算法接受两个输入参数：一是数据集，二是用户指定的集群数量K。算法的输出是K个集群，每个集群都有其中心点以及属于该集群的数据点。

K-means算法的执行过程如下：

初始化：随机选择K个点作为初始集群中心（质心）。
分配数据点到最近的集群：对于数据集中的每个点，计算其与各个质心的距离，并将其分配到距离最近的质心所对应的集群中。
重新计算质心：对于每个集群，计算其内所有数据点的平均值，并将该平均值设为新的质心。
迭代优化：重复步骤2和3，直到满足某个终止条件（如质心的变化小于某个阈值，或者达到最大迭代次数）。

图解说明：

2.聚类中心

3.目标函数

4.迭代更新

5.算法终止条件

迭代进行分配步骤和更新步骤，直到聚类中心不再发生显著变化，或者达到预设的最大迭代次数。

四、K-means算法的C++实现

首先是头文件：

#include <iostream>  #include <vector>  #include <cmath>  #include <limits>  #include <algorithm>

第一步: 数据结构定义

我们定义了一个Point结构体来表示二维空间中的点。

struct Point {    double x, y;    Point(double x = 0, double y = 0) : x(x), y(y) {}};

这个结构体很简单，只有两个成员变量x和y，分别表示点在二维空间中的横坐标和纵坐标。还有一个构造函数，用于创建点对象时初始化坐标。

第二步: 辅助函数

距离计算函数

double distance(const Point& a, const Point& b) {    return std::hypot(a.x - b.x, a.y - b.y);}

这个函数计算两个点之间的距离，使用了<cmath>库中的std::hypot函数，它接受两个参数（横坐标和纵坐标的差值），并返回这两点之间的欧几里得距离。

质心计算函数

Point centroid(const std::vector<Point>& cluster) {    double sum_x = 0, sum_y = 0;    for (const auto& point : cluster) {        sum_x += point.x;        sum_y += point.y;    }    return Point(sum_x / cluster.size(), sum_y / cluster.size());}

这个函数计算一个点集的质心。质心是所有点的坐标平均值。函数遍历点集，累加所有点的x坐标和y坐标，然后分别除以点的数量，得到质心的坐标。

第三步: K-means算法主体

K-means算法的主体部分可以进一步拆分为几个小的步骤：初始化、分配点、重新计算质心和检查收敛性。

初始化

在K-means算法中，我们需要首先选择K个初始质心。在这个简单的实现中，我们随机选择数据集中的K个点作为初始质心。

std::vector<Point> centroids(k);for (int i = 0; i < k; ++i) {    centroids[i] = data[rand() % data.size()];}

分配点

对于数据集中的每个点，我们需要找到最近的质心，并将其分配给该质心对应的集群。

std::vector<std::vector<Point>> clusters(k);for (const auto& point : data) {    double min_distance = std::numeric_limits<double>::max();    int cluster_index = 0;    for (int i = 0; i < k; ++i) {        double dist = distance(point, centroids[i]);        if (dist < min_distance) {            min_distance = dist;            cluster_index = i;        }    }    clusters[cluster_index].push_back(point);}

重新计算质心

分配完点后，我们需要重新计算每个集群的质心。

std::vector<Point> new_centroids(k);for (int i = 0; i < k; ++i) {    new_centroids[i] = centroid(clusters[i]);}

检查收敛性

如果新旧质心之间的变化很小（在一个很小的阈值以内），则算法收敛，可以停止迭代。

bool converged = true;for (int i = 0; i < k; ++i) {    if (distance(centroids[i], new_centroids[i]) > 1e-6) {        converged = false;        break;    }}

如果算法未收敛，则更新质心并继续迭代。

第四步: 主函数和数据准备

在主函数中，我们准备了一个简单的数据集（整体代码见最后），并设置了K值和最大迭代次数。然后调用kmeans函数进行聚类。

这就是K-means算法的一个基本实现。在实际应用中，可能还需要考虑更多的优化和异常情况处理，比如处理空集群、改进初始质心的选择方法、添加对异常值的鲁棒性等。

结果输出：

Cluster 1 centroid: (3.5, 3.9)(1, 0.6) (8, 5) (1, 4) (4, 6) Cluster 2 centroid: (5.41667, 9.06667)(2, 10) (2.5, 8.4) (5, 8) (8, 8) (9, 11) (6, 9)

五、K-means算法的优缺点

优点：

算法简单直观，易于理解和实现。
对于大数据集，K-means算法是相对高效的，因为它的复杂度是线性的，即O(n)。
当集群之间的区别明显且数据分布紧凑时，K-means算法表现良好。

缺点：

需要预先指定集群数量K，这在实际应用中可能是一个挑战。
对初始质心的选择敏感，不同的初始质心可能导致完全不同的结果。
只能发现球形的集群，对于非球形或复杂形状的集群效果不佳。
对噪声和异常值敏感，因为它们会影响质心的计算。

六、源代码如下

#include <iostream>  #include <vector>  #include <cmath>  #include <limits>  #include <algorithm>    struct Point {      double x, y;      Point(double x = 0, double y = 0) : x(x), y(y) {}  };    double distance(const Point& a, const Point& b) {      return std::hypot(a.x - b.x, a.y - b.y);  }    Point centroid(const std::vector<Point>& cluster) {      double sum_x = 0, sum_y = 0;      for (const auto& point : cluster) {          sum_x += point.x;          sum_y += point.y;      }      return Point(sum_x / cluster.size(), sum_y / cluster.size());  }    void kmeans(std::vector<Point>& data, int k, int max_iterations) {      std::vector<Point> centroids(k);      std::vector<std::vector<Point>> clusters(k);            // 随机化第一个质点    for (int i = 0; i < k; ++i) {          centroids[i] = data[rand() % data.size()];      }            for (int iter = 0; iter < max_iterations; ++iter) {           for (const auto& point : data) {              double min_distance = std::numeric_limits<double>::max();              int cluster_index = 0;              for (int i = 0; i < k; ++i) {                  double dist = distance(point, centroids[i]);                  if (dist < min_distance) {                      min_distance = dist;                      cluster_index = i;                  }              }              clusters[cluster_index].push_back(point);          }                    // 清除前一个的质点        for (auto& cluster : clusters) {              cluster.clear();          }                    // 重新计算质点         for (int i = 0; i < data.size(); ++i) {              int cluster_index = 0;              double min_distance = std::numeric_limits<double>::max();              for (int j = 0; j < k; ++j) {                  double dist = distance(data[i], centroids[j]);                  if (dist < min_distance) {                      min_distance = dist;                      cluster_index = j;                  }              }              clusters[cluster_index].push_back(data[i]);          }                    std::vector<Point> new_centroids(k);          for (int i = 0; i < k; ++i) {              new_centroids[i] = centroid(clusters[i]);          }                     bool converged = true;          for (int i = 0; i < k; ++i) {              if (distance(centroids[i], new_centroids[i]) > 1e-6) {                  converged = false;                  break;              }          }                    if (converged) {              break;          }                    centroids = new_centroids;      }            // 输出结果      for (int i = 0; i < k; ++i) {          std::cout << "Cluster " << i + 1 << " centroid: (" << centroids[i].x << ", " << centroids[i].y << ")" << std::endl;          for (const auto& point : clusters[i]) {              std::cout << "(" << point.x << ", " << point.y << ") ";          }          std::cout << std::endl;      }  }    int main() {      srand(time(nullptr)); // 随机数种子，可以使用随机数生成数据集          std::vector<Point> data = {          // 数据集         {2.0, 10.0}, {2.5, 8.4}, {5.0, 8.0}, {8.0, 8.0}, {1.0, 0.6},          {9.0, 11.0}, {8.0, 5.0}, {1.0, 4.0}, {4.0, 6.0}, {6.0, 9.0}      };            int k = 2; // 集群数量     int max_iterations = 5; // 迭代次数          kmeans(data, k, max_iterations);            return 0;  }

本文链接：//www.dmpip.com//www.dmpip.com/showinfo-26-83992-0.html详解 C++ 实现 K-means 算法

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇：面试官：限流的常见算法有哪些？

下一篇： C++中提升性能相关的十大特性

标签：

热门焦点

6月iOS设备性能榜：M2稳居榜首 A系列只能等一手3nm来救

没有新品发布，自然iOS设备性能榜的上榜设备就没有什么更替，仅仅只有跑分变化而产生的排名变动，毕竟苹果新品的发布节奏就是这样的，一年下来也就几个移动端新品，不会像安卓厂商，一
容量越大越不坏？24万块硬盘故障率报告公布这些产品零故障

8月5日消息，云存储服务商Backblaze发布了最新的硬盘故障率报告，年故障率有所上升。Backblaze发布的硬盘季度统计数据，其中包括故障率等重要方面。这些结
一加首款折叠屏！一加Open渲染图出炉：罕见单手可握小尺寸

8月5日消息，此前就有爆料称，一加首款折叠屏手机将会在第三季度上市，如今随着时间临近，新机的各种消息也开始浮出水面。据悉，这款新机将会被命名为“On
Python异步IO编程的进程/线程通信实现

这篇文章再讲3种方式，同时讲4中进程间通信的方式一、 Python 中线程间通信的实现方式共享变量共享变量是多个线程可以共同访问的变量。在Python中，可以使用threading模块中的L
信通院：小米、华为等11家应用商店基本完成APP签名及验签工作

中国信通院表示，目前，小米、华为、OPPO、vivo、360手机助手、百度手机助手、应用宝、豌豆荚和努比亚等9家应用商店，以及抖音和快手2家新型应用分发平
朋友圈可以修改可见范围了苹果用户可率先体验

近日，iOS用户迎来微信8.0.27正式版更新，除了可更换二维码背景外，还新增了多项实用功能。在新版微信中，朋友圈终于可以修改可见范围，简单来说就是已发布的朋友圈
SN570 NVMe SSD固态硬盘价格与性能兼具

SN570 NVMe SSD固态硬盘是西部数据发布的最新一代WD Blue系列的固态硬盘，不仅闪存技术更为精进，性能也得到了进一步的跃升。WD Blue SN570 NVMe SSD的包装外
华为举行春季智慧办公新品发布会首次推出电子墨水屏平板

北京时间2月27日晚，华为在巴塞罗那举行春季智慧办公新品发布会，在海外市场推出之前已经在中国市场上市的笔记本、平板、激光打印机等办公产品，并首次推出搭载
电博会与软博会实现"线下+云端"的双线融合

在本次“电博会”与“软博会”双展会利好条件的加持下，既可以发挥展会拉动人流、信息流、资金流实现快速交互流动的作用，继而推动区域经济良性发展；又可以聚