k means c++实现
时间: 2023-10-24 15:02:47 浏览: 30
k-means算法是一种基于聚类的机器学习算法,旨在将一组数据点划分为k个不同的簇,使得同一个簇内的数据点之间的相似度最大化,而不同簇之间的相似度最小化。
k-means算法的实现步骤如下:
1. 初始化:随机选择k个数据点作为初始聚类中心。
2. 分配数据点:计算每个数据点到各个聚类中心的距离,并将其分配给距离最近的聚类中心所代表的簇。
3. 更新聚类中心:对于每个簇,将其所有数据点的均值作为新的聚类中心。
4. 重复步骤2和3,直到聚类中心不再发生变化,或者达到设定的迭代次数。
具体来说,可以按照以下步骤实现k-means算法:
1. 随机选择k个数据点作为初始聚类中心。
2. 对于每个数据点,计算其到每个聚类中心的距离,选择距离最近的聚类中心,并将该数据点分配到对应的簇中。
3. 对于每个簇,计算该簇内所有数据点的均值,并将其作为新的聚类中心。
4. 检查新的聚类中心是否与上一次迭代时的聚类中心相同,如果相同则停止迭代;否则,返回步骤2。
需要注意的是,k-means算法对于初始聚类中心的选择敏感,不同的初始聚类中心可能会导致不同的聚类结果。
总结起来,k-means算法通过计算数据点与聚类中心的距离,并将数据点分配给最近的聚类中心,然后更新聚类中心,不断迭代直至收敛,最终将数据点划分为k个不同的簇。
相关问题
k-means聚类算法c++实现
以下是一个简单的C++实现k-means聚类算法的示例代码:
```c++
#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;
}
```
这是一个简单的示例,更复杂的应用可能需要更多的优化和调整。
k-means算法c++
以下是k-means算法的C++实现:
```c++
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAXN = 1000;
const int MAXK = 10;
const int MAXD = 10;
const int INF = 0x3f3f3f3f;
struct Point {
double element[MAXD];
};
struct Cluster {
Point center;
Point sum;
int size;
};
double dist(Point a, Point b, int n) {
double res = 0;
for (int i = 0; i < n; i++) {
res += (a.element[i] - b.element[i]) * (a.element[i] - b.element[i]);
}
return sqrt(res);
}
void Kmeans(int k, Point X[], Point Z[], int m, int n) {
Cluster C[MAXK];
for (int i = 0; i < k; i++) {
C[i].center = Z[i];
C[i].size = 0;
for (int j = 0; j < n; j++) {
C[i].sum.element[j] = 0;
}
}
bool flag = true;
while (flag) {
flag = false;
for (int i = 0; i < k; i++) {
C[i].size = 0;
for (int j = 0; j < n; j++) {
C[i].sum.element[j] = 0;
}
}
for (int i = 0; i < m; i++) {
int index = 0;
double minDist = INF;
for (int j = 0; j < k; j++) {
double d = dist(X[i], C[j].center, n);
if (d < minDist) {
minDist = d;
index = j;
}
}
C[index].size++;
for (int j = 0; j < n; j++) {
C[index].sum.element[j] += X[i].element[j];
}
}
for (int i = 0; i < k; i++) {
if (C[i].size == 0) {
continue;
}
Point newCenter;
for (int j = 0; j < n; j++) {
newCenter.element[j] = C[i].sum.element[j] / C[i].size;
}
if (dist(newCenter, C[i].center, n) > 0.0001) {
flag = true;
}
C[i].center = newCenter;
}
}
cout << "经过计算\n";
for (int i = 0; i < k; i++) {
cout << "聚类中心Z" << i + 1 << "=( ";
for (int j = 0; j < n; j++) {
cout << C[i].center.element[j] << " ";
}
cout << ")\n";
}
}
int main() {
srand(time(NULL));
int m, n, k;
Point X[MAXN], Z[MAXK];
cout << "请输入数据点个数m:";
cin >> m;
cout << "请输入数据点维数n:";
cin >> n;
cout << "请输入聚类中心个数k:";
cin >> k;
cout << "请输入数据点:\n";
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> X[i].element[j];
}
}
cout << "请输入聚类中心:\n";
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
cin >> Z[i].element[j];
}
}
Kmeans(k, X, Z, m, n);
return 0;
}
```