k-means.zip

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<iostream> #include<omp.h> #include<time.h> #include<math.h> #define NUM_THREADS 8//线程数 #define Num 5000//数据点数量 #define K_Num 10//中心点数量 #define Dim 2//坐标维度 #define N 10000//迭代次数 typedef struct dot {//数据点结构体 int ZB[Dim];//坐标 int group_id;//类别标签 }dot; typedef struct group {//中心点结构体 double ZB[Dim];//中心点坐标 }group; void random_create_data(dot &A) {//随机生成n维数据 int i; for (i = 0;i < Dim;i++) { A.ZB[i] = rand(); } } double Distance(int* A, double* B) {//计算欧氏距离 int i; double result=0; for (i = 0;i < Dim;i++) { result += pow((A[i] - B[i]), 2) ; } result = sqrt(result); return result; } void CX(dot* A,group* B) {//串行算法 int i, j, k, l; double dis; double C[K_Num][Dim + 1]; for (l = 0;l < N;l++) { for (i = 0;i < Num;i++) { double min_dis = 99999.0; int min; for (j = 0;j < K_Num;j++) { dis = Distance(A[i].ZB, B[j].ZB); if (dis < min_dis) { min = j; min_dis = dis; } } A[i].group_id = min; } for (i = 0;i < K_Num;i++) { for (j = 0;j < Dim + 1;j++) { C[i][j] = 0.0; } } for (i = 0;i < Num;i++) { k = A[i].group_id; C[k][Dim] += 1; for (j = 0;j < Dim;j++) { C[k][j] += A[i].ZB[j]; } } for (i = 0;i < K_Num;i++) { for (j = 0;j < Dim;j++) { B[i].ZB[j] = C[i][j] / C[i][Dim]; } } } } void BX1(dot* A, group* B) {//并行算法 int i, j, k, l; double dis; double C[K_Num][Dim + 1]; omp_set_num_threads (NUM_THREADS); for (l = 0;l < N;l++) { #pragma omp parallel { #pragma omp for for (i = 0;i < Num;i++) { double min_dis = 99999.0; int min; for (j = 0;j < K_Num;j++) { dis = Distance(A[i].ZB, B[j].ZB); if (dis < min_dis) { min = j; min_dis = dis; } } A[i].group_id = min; } #pragma omp for for (i = 0;i < K_Num;i++) { for (j = 0;j < Dim + 1;j++) { C[i][j] = 0; } } for (i = 0;i < Num;i++) { k = (int)A[i].group_id; C[k][Dim] += 1; for (j = 0;j < Dim;j++) { C[k][j] += A[i].ZB[j]; } } #pragma omp for for (i = 0;i < K_Num;i++) { for (j = 0;j < Dim;j++) { B[i].ZB[j] = C[i][j] / C[i][Dim]; } } } } } int main() { int i,j,k,l; double dis; dot A[Num]; group B[K_Num]; for (i = 0;i < Num;i++) { random_create_data(A[i]); } for (i = 0;i < K_Num;i++) {//随机选择十个数据点作为中心点初始值 k = rand() % Num; for (j = 0;j < Dim;j++) { B[i].ZB[j] =double( A[k].ZB[j]); } } clock_t a = clock(); //CX(A, B);//串行程序 BX1(A,B);//并行程序 clock_t b = clock(); printf("%dms\n", b - a); FILE* fptr;//结果写入文件 fptr = fopen("res.txt", "w"); for (i = 0;i < Num;i++) { for (j = 0;j < Dim;j++) fprintf(fptr, "%d\t", A[i].ZB[j]); fprintf(fptr, "%d\n", A[i].group_id); } fclose(fptr); }