当前位置： 首页 > article >正文

聚类算法总结

article 2024/11/19 12:50:01

一、引言

聚类分析是数据挖掘、机器学习等领域中的重要任务，旨在将数据集中相似的数据对象划分到同一组（簇）中。聚类算法无需事先知道数据的类别标签，是一种无监督学习方法。它在许多应用场景中发挥了关键作用，例如客户细分、图像分割、生物信息学中的基因分类等。

二、常见聚类算法

K - 均值聚类（K - Means Clustering）

  1. 原理
    K - 均值算法的目标是将数据集划分为 K 个簇，使得簇内数据点的平方和最小。算法的基本步骤如下：

    • 随机初始化 K 个聚类中心。
    • 将每个数据点分配到距离其最近的聚类中心所在的簇。
    • 根据新划分的簇，重新计算每个簇的聚类中心（即簇内所有数据点的均值）。
    • 重复步骤 2 和 3，直到聚类中心不再发生显著变化或者达到指定的迭代次数。

  2. 公式

    • 设数据集。

层次聚类（Hierarchical Clustering）

  1. 原理
    层次聚类方法构建了聚类的层次结构，有两种基本类型：凝聚式层次聚类和分裂式层次聚类。

    • 凝聚式层次聚类：开始时，每个数据点都作为一个单独的簇，然后不断合并相似的簇，直到所有数据点都在一个簇中或者达到某个停止条件。
    • 分裂式层次聚类：开始时所有数据点都在一个簇中，然后逐步将簇分裂成更小的簇。

  2. 公式
    在凝聚式层次聚类中，常用的簇间距离度量方法有：

    • 单连接（Single - Linkage）：，即两个簇之间的距离是两个簇中数据点对之间的最小距离。
    • 全连接（Complete - Linkage）：，两个簇之间的距离是两个簇中数据点对之间的最大距离。
    • 平均连接（Average - Linkage）：，其中和分别是簇和中的数据点个数。

密度 - 基于聚类（Density - Based Clustering）

  1. 原理
    密度 - 基于聚类算法的主要思想是基于数据点的密度，如果一个区域内的数据点密度超过某个阈值，则将这些数据点划分为一个簇。DBSCAN（Density - Based Spatial Clustering of Applications with Noise）是一种典型的密度 - 基于聚类算法。

    • 它定义了核心点（在其邻域内包含至少指定数量的点）、边界点（在某个核心点的邻域内但本身不是核心点）和噪声点（不属于任何簇的点）。

  2. 公式

高斯混合模型聚类（Gaussian Mixture Model Clustering）

  1. 原理
    假设数据是由多个高斯分布混合而成的，通过估计每个高斯分布的参数（均值、协方差等）来确定簇。每个高斯分布对应一个簇，数据点属于某个簇的概率由该簇的高斯分布决定。

  2. 公式

三、聚类算法的评估指标

  1. 内部评估指标

    • 轮廓系数（Silhouette Coefficient）：对于每个数据点xi，计算其轮廓系数s(i)。，其中是到其所属簇内其他点的平均距离，bi是xi到其他簇中数据点的最小平均距离。轮廓系数的值在之间，值越高表示聚类效果越好。
    • 簇内平方和（Within - Cluster Sum of Squares，WCSS）：即 K - 均值算法中的目标函数J，WCSS 越小，聚类效果越好。

  2. 外部评估指标（当有真实标签时）

    • 调整兰德指数（Adjusted Rand Index）：对兰德指数进行了调整，克服了兰德指数在某些情况下的缺陷。

四、聚类算法的优缺点及适用场景

K - 均值聚类

  1. 优点
    • 简单、易于理解和实现。
    • 计算效率高，对于大规模数据集有较好的可扩展性。
  2. 缺点
    • 需要事先指定簇的数量，值的选择不当会影响聚类效果。
    • 对初始聚类中心敏感，不同的初始值可能导致不同的聚类结果。
    • 只能处理球形簇，对于非球形簇效果不佳。
  3. 适用场景
    • 数据分布大致为球形，且簇之间区分比较明显的情况。
    • 对聚类结果精度要求不是特别高的大规模数据集初步聚类。

层次聚类

  1. 优点
    • 不需要事先指定簇的数量，聚类结果以树状图（Dendrogram）形式呈现，直观地展示了数据的层次结构。
  2. 缺点
    • 计算复杂度高，特别是对于大规模数据集，效率较低。
    • 一旦一个合并或者分裂被执行，就不能再撤销，可能导致聚类结果不好。
  3. 适用场景
    • 对数据的层次结构有兴趣的情况，例如生物分类等领域。
    • 数据集规模相对较小，对计算效率要求不是极高的场景。

密度 - 基于聚类

  1. 优点
    • 不需要事先指定簇的数量，能够发现任意形状的簇，对噪声点不敏感。
  2. 缺点
    • 计算复杂度较高，特别是对于高维数据和大规模数据集。
  3. 适用场景
    • 数据分布形状不规则，存在噪声点的情况，如地理信息系统中的数据聚类。

高斯混合模型聚类

  1. 优点
    • 理论基础强，对数据的分布有较好的建模能力，能够处理具有复杂分布的数据。
  2. 缺点
    • 计算复杂度高，特别是在估计高斯混合模型的参数时，可能存在局部最优解问题。
    • 需要较多的数据来准确估计模型参数。
  3. 适用场景
    • 数据具有复杂的概率分布，且对聚类的概率解释有要求的场景，如语音识别中的声学模型聚类。

五、C++ 实现示例（以 K - 均值聚类为例）

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

// 计算欧氏距离
double euclideanDistance(const std::vector<double>& point1, const std::vector<double>& point2) {
    double distance = 0.0;
    for (size_t i = 0; i < point1.size(); ++i) {
        double diff = point1[i] - point2[i];
        distance += diff * diff;
    }
    return std::sqrt(distance);
}

// K - 均值聚类算法
void kMeansClustering(std::vector<std::vector<double>>& data, int k, int maxIterations) {
    int numPoints = data.size();
    int numDimensions = data[0].size();

    // 随机初始化聚类中心
    std::vector<std::vector<double>> centroids(k, std::vector<double>(numDimensions));
    for (int i = 0; i < k; ++i) {
        int randomIndex = rand() % numPoints;
        centroids[i] = data[randomIndex];
    }

    std::vector<int> clusterAssignments(numPoints);
    for (int iteration = 0; iteration < maxIterations; ++iteration) {
        // 分配数据点到最近的聚类中心
        for (int i = 0; i < numPoints; ++i) {
            double minDistance = std::numeric_limits<double>::max();
            int closestCentroid = -1;
            for (int j = 0; j < k; ++j) {
                double distance = euclideanDistance(data[i], centroids[j]);
                if (distance < minDistance) {
                    minDistance = distance;
                    closestCentroid = j;
                }
            }
            clusterAssignments[i] = closestCentroid;
        }

        // 更新聚类中心
        std::vector<std::vector<double>> newCentroids(k, std::vector<double>(numDimensions, 0.0));
        std::vector<int> clusterSizes(k, 0);
        for (int i = 0; i < numPoints; ++i) {
            int cluster = clusterAssignments[i];
            for (int j = 0; j < numDimensions; ++j) {
                newCentroids[cluster][j] += data[i][j];
            }
            clusterSizes[cluster]++;
        }
        for (int i = 0; i < k; ++i) {
            if (clusterSizes[i] > 0) {
                for (int j = 0; j < numDimensions; ++j) {
                    newCentroids[i][j] /= clusterSizes[i];
                }
            }
        }

        bool centroidsChanged = false;
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j < numDimensions; ++j) {
                if (newCentroids[i][j]!= centroids[i][j]) {
                    centroidsChanged = true;
                    break;
                }
            }
            if (centroidsChanged) {
                break;
            }
        }
        if (!centroidsChanged) {
            break;
        }
        centroids = newCentroids;
    }

    // 输出聚类结果
    for (int i = 0; i < numPoints; ++i) {
        std::cout << "Point " << i << " belongs to cluster " << clusterAssignments[i] << std::endl;
    }
}

int main() {
    // 示例数据
    std::vector<std::vector<double>> data = {
        {1.0, 2.0},
        {1.5, 1.8},
        {5.0, 8.0},
        {5.2, 7.9},
        {10.0, 12.0},
        {10.2, 11.8}
    };
    int k = 3;
    int maxIterations = 100;
    kMeansClustering(data, k, maxIterations);
    return 0;
}

以上代码实现了 K - 均值聚类算法，包括计算欧氏距离、初始化聚类中心、分配数据点到簇和更新聚类中心等步骤。在main函数中提供了一个简单的示例数据集进行聚类。对于其他聚类算法，也可以使用 C++ 按照其原理实现相应的代码，在实现过程中需要注意数据结构的选择和算法的效率优化。同时，可以进一步扩展代码来处理更复杂的数据集和应用场景，如从文件中读取数据、可视化聚类结果等。

请注意，实际应用中可能需要对代码进行更多的优化和改进，例如采用更高效的距离计算方法、更好的初始化策略以及处理异常情况等。此外，不同的聚类算法在实现上有各自的特点和难点，需要根据具体算法进行深入的设计和编码。

以下是一个使用 OpenCV 库在 C++ 中实现 K-Means 聚类的示例代码。这个示例将读取一张图像，把图像的像素数据转换为适合聚类分析的格式，然后应用 K-Means 聚类算法对像素进行聚类，并根据聚类结果对图像进行重新着色以展示聚类效果。

#include <iostream>
#include <opencv2/opencv.hpp>

using namespace std;
using namespace cv;

// 将图像数据转换为适合K-Means聚类的格式（一维向量）
Mat imageToData(const Mat& image) {
    int width = image.cols;
    int height = image.rows;
    int channels = image.channels();

    Mat data(height * width, channels, CV_32F);

    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            Vec3b pixel = image.at<Vec3b>(i, j);
            for (int k = 0; k < channels; ++k) {
                data.at<float>(i * width + j, k) = static_cast<float>(pixel[k]);
            }
        }
    }

    return data;
}

// 将聚类结果应用到图像上，重新着色
Mat applyClusteringToImage(const Mat& image, const Mat& labels, const Mat& centroids) {
    int width = image.cols;
    int height = image.rows;
    int channels = image.channels();

    Mat result = image.clone();

    for (int i = 0; i < height; ++i) {
        for (int j = 0; j < width; ++j) {
            int label = labels.at<int>(i * width + j);
            Vec3f newColor = centroids.at<Vec3f>(label);
            for (int k = 0; k < channels; ++k) {
                result.at<Vec3b>(i, j)[k] = static_cast<unsigned char>(newColor[k]);
            }
        }
    }

    return result;
}

int main() {
    // 读取图像
    Mat image = imread("your_image_path.jpg");
    if (image.empty()) {
        cout << "无法读取图像！" << endl;
        return -1;
    }

    // 将图像数据转换为适合聚类的格式
    Mat data = imageToData(image);

    // 设置聚类的类别数（K值）
    int K = 5;

    // 应用K-Means聚类算法
    Mat labels;
    Mat centroids;
    kmeans(data, K, labels, TermCriteria(TermCriteria::MAX_ITER + TermCriteria::EPS, 100, 0.1),
           3, KMEANS_PP_CENTERS, centroids);

    // 将聚类结果应用到图像上，重新着色
    Mat resultImage = applyClusteringToImage(image, labels, centroids);

    // 显示原始图像和聚类后的图像
    imshow("原始图像", image);
    imshow("聚类后图像", resultImage);
    waitKey(0);

    return 0;
}

效果图：

原图

处理后


http://www.kler.cn/a/400109.html

相关文章：

  • 17.100ASK_T113-PRO 配置QT运行环境(三)
  • 视觉SLAM--经典视觉SLAM框架
  • 【MySql】实验十六 综合练习：图书管理系统数据库结构
  • C++线程基础使用方法
  • 如何在MindMaster思维导图中制作PPT课件？
  • STM32完全学习——使用标准库点亮LED
  • win7系统下惠普测试打印页失败提示“系统不支持请求的命令”解决方法
  • FPGA通过MIPI CSI-2发送实时图像到RK3588，并HDMI显示
  • Maven的下载安装及配置
  • Postman之数据提取
  • R语言-快速对多个变量取交集
  • JavaWeb 开发面试题及参考答案
  • Python+Pyecharts重画基金净值曲线（全）
  • K8S资源限制之resources
  • 《大数据中的高级 SQL 技巧技》
  • LinuxWEB服务器的部署及优化
  • Jupyter Notebook 与 PyTorch 配置教程
  • 迷你游戏作为电子学习中的趋势工具
  • hadoop3.x 新特性
  • 学习threejs，使用TWEEN插件实现动画
  • 利用正则表达式批量修改文件名
  • Python读取prophesee相机输出的raw文件
  • java itext后端生成pdf导出
  • 企业架构框架之银行业参考架构BIAN
  • 数据分析-50-时间序列信息编码之采用正余弦循环编码
  • kafka-clients之max.block.ms