聚类算法总结

server/2024/11/19 15:58:42/

一、引言

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

二、常见聚类算法

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.ppmy.cn/server/143230.html

相关文章

React 教程第一节 简介概述 以及 特点

React 教程第一节 简介概述 以及 特点

概述&#xff1a; 一个用于构建web与原生交互界面的UI库&#xff0c;无论是独立开发者&#xff0c;还是团队协作&#xff0c;React 都可以轻松的组合由不同人群开发的组件&#xff0c;随写随插随用&#xff0c;方便快捷&#xff1b; 特点&#xff1a; 1、声明式设计&#xf…
阅读更多...
RLC串联电路基础

RLC串联电路基础

RLC串联电路 一、电路基本构成与方程 RLC串联电路由电阻&#xff08;R&#xff09;、电感&#xff08;L&#xff09;和电容&#xff08;C&#xff09;串联组成。其描述行为的二阶微分方程为 L d 2 i d t 2 R d i d t 1 C i 0 L\frac{d^{2}i}{dt^{2}} R\frac{di}{dt} \fr…
阅读更多...
内网安全、域渗透测试工具-NetExec介绍及使用（优秀）

内网安全、域渗透测试工具-NetExec介绍及使用（优秀）

目录 ​编辑 介绍 支持的协议 安装 Unix 使用 pipx 安装NetExec Kali安装 使用pip安装 Windows MacOS 手动编译二进制 设置 Tab 补全 使用方法 帮助 NetExec 目标格式 使用凭证 更多使用教程 github地址 介绍 NeNetExec (nxc) 是一款功能强大的自动化网络安…
阅读更多...
原生cesium 实现楼栋抽离效果

原生cesium 实现楼栋抽离效果

这里写自定义目录标题 需求背景解决思路解决效果index.vue 需求背景 需要实现整栋楼的展开&#xff0c;合上&#xff0c;单层抽离的预览效果 解决思路 由于3dtiles格式分成选中的元素太多&#xff0c;做模型抽离较麻烦 采用把模型按每层分成小模型用model的方式交互加载 解…
阅读更多...
nginx证书流式响应配置

nginx证书流式响应配置

要配置 Nginx 支持流式响应的反向代理&#xff0c;你需要进行一些特定的设置&#xff0c;以确保 Nginx 不会缓冲响应并正确地将数据转发到后端服务器。以下是一个简单的配置示例&#xff0c;假设你的后端服务器运行在 http://backend-server:port&#xff1a; server {listen …
阅读更多...
lua脚本语言基本原理

lua脚本语言基本原理

Lua是一种轻量级、高效的脚本语言&#xff0c;其原理主要包括以下几个方面&#xff1a; 词法分析 原理&#xff1a;词法分析器按从左到右的顺序对 Lua 脚本的源程序字符流进行扫描&#xff0c;依据词法规则将其识别为一个个单词&#xff0c;如关键字、标识符、常量、运算符等…
阅读更多...
Python学习27天

Python学习27天

字典 dict{one:1,two:2,three:3} # 遍历1&#xff1a; # 先取出Key for key in dict:# 取出Key对应的valueprint(f"key:{key}---value:{dict[key]}")#遍历2&#xff0c;依次取出value for value in dict.values():print(value)# 遍历3&#xff1a;依次取出key,value …
阅读更多...
【网络安全】SSL（二）：Keyless SSL技术细节

【网络安全】SSL（二）：Keyless SSL技术细节

未经许可，不得转载。 文章目录 TLS双重目标握手过程是什么？TLS 中的握手类型TLS 术语表RSA 握手协议临时 Diffie-Hellman 握手Diffie-Hellman 握手过程保护密钥服务器其他安全考虑性能提升场景分析持久连接精简握手会话恢复的问题Keyless SSL 的会话恢复功能会话票据恢复会话…
阅读更多...
最新文章

Copyright @ 2022~2023