C++中聚类算法的数据压缩与解压

在C++中，聚类算法可以用于数据压缩，因为它们可以将相似的数据点分组在一起，从而减少数据集中的冗余。以下是一个简单的例子，展示了如何使用K-means聚类算法进行数据压缩和解压：

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

// K-means聚类算法
std::vector<std::vector<double>> kMeans(const std::vector<std::vector<double>>& data, int k, int maxIterations = 100) {
    int n = data.size();
    std::vector<int> labels(n, -1);
    std::vector<std::vector<double>> centroids(k, std::vector<double>(data[0].size(), 0));
    std::vector<std::vector<double>> clusterCentroids(k, std::vector<double>(data[0].size(), 0));

    // 随机初始化质心
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(data.begin(), data.end(), gen);
    for (int i = 0; i < k; ++i) {
        centroids[i] = data[i];
    }

    for (int i = 0; i < maxIterations; ++i) {
        std::vector<std::vector<double>> clusters(k);

        // 将数据点分配到最近的质心
        for (int j = 0; j < n; ++j) {
            double minDist = std::numeric_limits<double>::max();
            int minIndex = -1;
            for (int l = 0; l < k; ++l) {
                double dist = 0;
                for (int m = 0; m < data[j].size(); ++m) {
                    dist += pow(data[j][m] - centroids[l][m], 2);
                }
                if (dist < minDist) {
                    minDist = dist;
                    minIndex = l;
                }
            }
            labels[j] = minIndex;
            clusters[minIndex].push_back(data[j]);
        }

        // 更新质心
        for (int j = 0; j < k; ++j) {
            double sum = 0;
            for (const auto& point : clusters[j]) {
                for (int m = 0; m < point.size(); ++m) {
                    sum += point[m];
                }
            }
            for (int m = 0; m < point.size(); ++m) {
                centroids[j][m] = sum / clusters[j].size();
            }
        }
    }

    // 计算最终的质心
    std::vector<std::vector<double>> finalCentroids;
    for (int i = 0; i < k; ++i) {
        if (!clusters[i].empty()) {
            double sum = 0;
            for (const auto& point : clusters[i]) {
                for (int m = 0; m < point.size(); ++m) {
                    sum += point[m];
                }
            }
            for (int m = 0; m < point.size(); ++m) {
                finalCentroids[i][m] = sum / clusters[i].size();
            }
        }
    }

    return finalCentroids;
}

// 数据压缩
std::vector<std::vector<double>> compressData(const std::vector<std::vector<double>>& data, int k) {
    std::vector<std::vector<double>> centroids = kMeans(data, k);
    std::vector<std::vector<double>> compressedData;

    for (const auto& point : data) {
        double minDist = std::numeric_limits<double>::max();
        int minIndex = -1;
        for (int i = 0; i < centroids.size(); ++i) {
            double dist = 0;
            for (int m = 0; m < point.size(); ++m) {
                dist += pow(point[m] - centroids[i][m], 2);
            }
            if (dist < minDist) {
                minDist = dist;
                minIndex = i;
            }
        }
        compressedData.push_back(centroids[minIndex]);
    }

    return compressedData;
}

// 数据解压
std::vector<std::vector<double>> decompressData(const std::vector<std::vector<double>>& compressedData, const std::vector<std::vector<double>>& originalData, int k) {
    std::vector<std::vector<double>> centroids = kMeans(originalData, k);
    std::vector<std::vector<double>> decompressedData;

    for (const auto& point : compressedData) {
        double minDist = std::numeric_limits<double>::max();
        int minIndex = -1;
        for (int i = 0; i < centroids.size(); ++i) {
            double dist = 0;
            for (int m = 0; m < point.size(); ++m) {
                dist += pow(point[m] - centroids[i][m], 2);
            }
            if (dist < minDist) {
                minDist = dist;
                minIndex = i;
            }
        }
        decompressedData.push_back(originalData[minIndex]);
    }

    return decompressedData;
}

int main() {
    std::vector<std::vector<double>> data = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}};
    int k = 2;

    // 数据压缩
    std::vector<std::vector<double>> compressedData = compressData(data, k);
    std::cout << "Compressed data:" << std::endl;
    for (const auto& point : compressedData) {
        std::cout << "[" << point[0] << ", " << point[1] << "]" << std::endl;
    }

    // 数据解压
    std::vector<std::vector<double>> decompressedData = decompressData(compressedData, data, k);
    std::cout << "Decompressed data:" << std::endl;
    for (const auto& point : decompressedData) {
        std::cout << "[" << point[0] << ", " << point[1] << "]" << std::endl;
    }

    return 0;
}

这个例子中，我们首先使用K-means聚类算法对数据进行压缩，将相似的数据点分组在一起。然后，我们可以使用相同的算法对压缩后的数据进行解压，恢复原始数据。请注意，这个例子仅用于演示目的，实际应用中可能需要根据具体需求进行调整。