c++ K-means聚类

K-means 聚类是一种聚类分析算法，它属于无监督学习算法，其目的是将数据划分为 K 个不重叠的簇，并使每个簇内的数据尽量相似。

算法的工作流程如下：
1. 选择 K 个初始聚类中心；
2. 将数据点分配到最近的聚类中心；
3. 更新聚类中心为当前聚类内所有数据点的平均值；
4. 重复步骤 2 和 3 直到聚类中心不再变化，或者到达最大迭代次数。

K-means 聚类算法常用于数据挖掘、计算机视觉等领域，但是它也有一些缺陷，例如对于噪声数据的敏感性以及对初始聚类中心选择的敏感性等。

相关问题

k-means聚类算法C++

k-means聚类算法是一种常用的无监督学习算法，用于将数据集划分为k个不同的类别。它的主要思想是通过迭代的方式将数据点分配到k个簇中，使得每个数据点与所属簇的质心之间的距离最小化。

以下是k-means聚类算法的C++实现步骤：

1. 初始化：随机选择k个数据点作为初始质心。
2. 分配：对于每个数据点，计算其与每个质心之间的距离，并将其分配到距离最近的质心所属的簇中。
3. 更新：对于每个簇，计算其所有数据点的平均值作为新的质心。
4. 重复步骤2和步骤3，直到质心不再发生变化或达到最大迭代次数。

以下是一个简单的k-means聚类算法的C++代码示例：

#include <iostream>
#include <vector>
#include <cmath>

// 计算两个数据点之间的欧氏距离
double distance(const std::vector<double>& point1, const std::vector<double>& point2) {
    double sum = 0.0;
    for (int i = 0; i < point1.size(); ++i) {
        sum += std::pow(point1[i] - point2[i], 2);
    }
    return std::sqrt(sum);
}

// k-means聚类算法
std::vector<int> kMeansClustering(const std::vector<std::vector<double>>& data, int k, int maxIterations) {
    std::vector<std::vector<double>> centroids(k);  // 质心
    std::vector<int> clusterAssignments(data.size());  // 数据点所属的簇

    // 随机初始化质心
    for (int i = 0; i < k; ++i) {
        centroids[i] = data[std::rand() % data.size()];
    }

    bool centroidsChanged = true;
    int iterations = 0;

    while (centroidsChanged && iterations < maxIterations) {
        centroidsChanged = false;

        // 分配数据点到最近的质心所属的簇
        for (int i = 0; i < data.size(); ++i) {
            double minDistance = std::numeric_limits<double>::max();
            int minIndex = -1;

            for (int j = 0; j < k; ++j) {
                double dist = distance(data[i], centroids[j]);
                if (dist < minDistance) {
                    minDistance = dist;
                    minIndex = j;
                }
            }

            if (clusterAssignments[i] != minIndex) {
                clusterAssignments[i] = minIndex;
                centroidsChanged = true;
            }
        }

        // 更新质心
        for (int i = 0; i < k; ++i) {
            std::vector<double> sum(data.size(), 0.0);
            int count = 0;

            for (int j = 0; j < data.size(); ++j) {
                if (clusterAssignments[j] == i) {
                    for (int d = 0; d < data[j].size(); ++d) {
                        sum[d] += data[j][d];
                    }
                    count++;
                }
            }

            if (count > 0) {
                for (int d = 0; d < sum.size(); ++d) {
                    centroids[i][d] = sum[d] / count;
                }
            }
        }

        iterations++;
    }

    return clusterAssignments;
}

int main() {
    // 示例数据
    std::vector<std::vector<double>> data = {{1.0, 2.0}, {2.0, 1.0}, {10.0, 12.0}, {12.0, 10.0}, {20.0, 22.0}, {22.0, 20.0}};
    int k = 2;  // 聚类的簇数
    int maxIterations = 100;  // 最大迭代次数

    std::vector<int> clusterAssignments = kMeansClustering(data, k, maxIterations);

    // 输出每个数据点所属的簇
    for (int i = 0; i < clusterAssignments.size(); ++i) {
        std::cout << "Data point " << i << " belongs to cluster " << clusterAssignments[i] << std::endl;
    }

    return 0;
}

k-means聚类算法c++实现

以下是一个简单的C++实现k-means聚类算法的示例代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <random>

//定义一个点的结构体
struct Point {
    double x, y;
    int cluster; //点所属簇的编号
};

//计算两个点之间的距离
double distance(Point& a, Point& b) {
    return std::sqrt(std::pow(a.x - b.x, 2.0) + std::pow(a.y - b.y, 2.0));
}

//随机生成k个初始聚类中心
void initClusterCenter(std::vector<Point>& points, std::vector<Point>& clusters, int k) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(0, points.size() - 1);
    for (int i = 0; i < k; ++i) {
        Point p = points[dis(gen)];
        p.cluster = i;
        clusters.push_back(p);
    }
}

//将每个点分配到距离最近的聚类中心所在的簇
void assignCluster(std::vector<Point>& points, std::vector<Point>& clusters) {
    for (auto& p : points) {
        double minDistance = distance(p, clusters[0]);
        int clusterIndex = 0;
        for (int i = 1; i < clusters.size(); ++i) {
            double d = distance(p, clusters[i]);
            if (d < minDistance) {
                minDistance = d;
                clusterIndex = i;
            }
        }
        p.cluster = clusterIndex;
    }
}

//重新计算每个簇的中心点
void updateClusterCenter(std::vector<Point>& points, std::vector<Point>& clusters) {
    for (auto& c : clusters) {
        double sumX = 0.0, sumY = 0.0;
        int count = 0;
        for (auto& p : points) {
            if (p.cluster == c.cluster) {
                sumX += p.x;
                sumY += p.y;
                ++count;
            }
        }
        c.x = sumX / count;
        c.y = sumY / count;
    }
}

//判断聚类是否已经收敛
bool isConverged(std::vector<Point>& oldClusters, std::vector<Point>& newClusters, double epsilon) {
    for (int i = 0; i < oldClusters.size(); ++i) {
        if (distance(oldClusters[i], newClusters[i]) > epsilon) {
            return false;
        }
    }
    return true;
}

//k-means聚类算法
std::vector<Point> kMeans(std::vector<Point>& points, int k, double epsilon, int maxIterations) {
    std::vector<Point> clusters;
    initClusterCenter(points, clusters, k);

    int iter = 0;
    while (true) {
        assignCluster(points, clusters);
        std::vector<Point> newClusters = clusters;
        updateClusterCenter(points, newClusters);
        ++iter;
        if (isConverged(clusters, newClusters, epsilon) || iter >= maxIterations) {
            return newClusters;
        }
        clusters = newClusters;
    }
}

int main() {
    //生成一些随机点
    std::vector<Point> points;
    for (int i = 0; i < 100; ++i) {
        Point p;
        p.x = std::rand() % 100;
        p.y = std::rand() % 100;
        points.push_back(p);
    }

    //运行k-means聚类
    std::vector<Point> clusters = kMeans(points, 3, 0.01, 100);

    //打印每个簇中的点
    for (auto& c : clusters) {
        std::cout << "Cluster " << c.cluster << ":\n";
        for (auto& p : points) {
            if (p.cluster == c.cluster) {
                std::cout << "(" << p.x << "," << p.y << ")\n";
            }
        }
    }

    return 0;
}

这是一个简单的示例，更复杂的应用可能需要更多的优化和调整。