层次聚类算法之single-linkage和complete-linkage（C语言实现）

2023-10-11 04:48
文章标签 算法 语言 实现 层次 聚类 single complete linkage

本文主要是介绍层次聚类算法之single-linkage和complete-linkage（C语言实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

层次聚类试图在不同层次上对数据集合进行划分， 从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可以采用“自顶向下”的分拆策略。

AGNES是一种采用自底向上的聚合策略的层次聚合算法，它先将数据集中的每个样本看作是一个初始的聚类簇，然后在算法进行的每一步中找出距离最近的两个聚类来进行合并，该过程不断的重复，直到到达预设的聚类簇的个数。

改算法的关键是如何计算聚类之间的距离， 实际上，每一个聚类是一个样本的集合，因此，只需要采用关于集合的某种距离即可。

最近距离由两个簇的最近的样本来决定， 最大距离由两个簇的最远的样本来决定，由此分别产生的AGNES算法又分别称为single-linkage和complete-linkage算法。


single-linkage算法

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<io.h>int sample_size;
int sample_dimension;
char filename[200];double** data;
double** distance;
int cluster_count;void initialization();
void readDataFromFile();
double calculateDistance_BetweenTwoObject(int, int);
void initializationDistanceMatrix();
void AGNES();
void findMinDistance_BetweenClsuter_MIN(int*, int*);
void combineCluster(int, int);
void writeToFile(int);int main(int argc, char* argv[])
{if( argc != 4 ){printf("This algorithm requires 4 user-specified parameter""\n\t\tthe number of sample""\n\t\tthe dimension of sample""\n\t\tthe filename contain the sample""\n\n");exit(0);}sample_size = atoi(argv[1]);sample_dimension = atoi(argv[2]);strcat(filename, argv[3]);initialization();readDataFromFile();initializationDistanceMatrix();AGNES();return 0;
}/** initialize the dynamic array for storing sample* */
void initialization()
{//initializaion the sample dataint i, j;data = (double**)malloc(sizeof(double*) * (sample_size + 1));if( !data ){printf("data malloc error: 0");exit(0);}for( i = 1; i <= sample_size; i++ ){data[i] = (double*)malloc(sizeof(double) * (sample_dimension + 1));if( !data[i] ){printf("data malloc error: %d", i);exit(0);}}//initialiation the distance datadistance = (double**)malloc(sizeof(double*) * (sample_size + 1));if( !distance ){printf("distance malloc error: 0");exit(0);}for( i = 1; i <= sample_size; i++ ){distance[i] = (double*)malloc(sizeof(double) * (sample_size + 1));if( !distance[i] ){printf("distance malloc error: %d", i);exit(0);}}//the 0th element of all row indicate the clauterID of the objectfor( i = 1; i <= sample_size; i++ ){distance[i][0] = i;}
}/** read the sample data from file* */
void readDataFromFile()
{FILE* fread;int i;int j;if( NULL == (fread = fopen(filename, "r"))){printf("open file(%s) error: ", filename);exit(0);}for( i = 1; i <= sample_size; i++ ){for( j = 1; j <= sample_dimension; j++ ){if( 1 != fscanf(fread, "%lf ", &data[i][j])){printf("fscanf error: (%d, %d)", i, j);exit(0);}}}//testprintf("print the origin data:\n");for( i = 1; i <= sample_size; i++ ){for( j = 1; j <= sample_dimension; j++ ){printf("%f\t", data[i][j]);}printf("\n");}//test END
}/** calculate distance between two objects* */
double calculateDistance_BetweenTwoObject(int firstID, int secondID)
{double distance = 0.0;int i;for( i = 1; i <= sample_dimension; i++ ){distance = distance + pow(data[firstID][i] - data[secondID][i], 2);}return sqrt(distance);
}/** calculate initialization distance matrix* */
void initializationDistanceMatrix()
{int i, j;for( i = 1; i <= sample_size; i++ ){for( j = i; j <= sample_size; j++ ){distance[i][j] = calculateDistance_BetweenTwoObject(i, j);distance[j][i] = distance[i][j];}}//testprintf("print the origin distance matrix\n");for( i = 1; i <= sample_size; i++ ){for( j = 0; j <= sample_size; j++ ){printf("%f ", distance[i][j]);}printf("\n");}//test END
}/****************************************************************************************************************						AGNES***************************************************************************************************************/
void AGNES()
{cluster_count = sample_size;int cluster_1, cluster_2;int count = 1;while( cluster_count > 3 ){printf("-------------------%d--------------------\n", count);findMinDistance_BetweenClsuter_MIN(&cluster_1, &cluster_2);combineCluster(cluster_1, cluster_2);				cluster_count--;writeToFile(count++);}
}/** find two clusters the distance between them is minimun, and store the clusterID in @cluster_1 and @cluster_2, respectively.* */
void findMinDistance_BetweenClsuter_MIN(int* cluster_1, int* cluster_2)
{int i, j;double min_distance;int flag = 1;for( i = 1; i <= sample_size; i++ ){for( j = i + 1; j <= sample_size; j++ ){if( distance[i][0] == distance[j][0] ){printf("same cluster!!!! %d and %d\n\n", i , j);continue;}else if( flag == 1 ){min_distance = distance[i][j];*cluster_1 = i;*cluster_2 = j;flag = 0;printf("----get the initial minimum distance is %f(%d, %d)\n", min_distance, i, j);continue;}if( distance[i][j] < min_distance ){min_distance = distance[i][j];*cluster_1 = i;*cluster_2 = j;}}}printf("the minimum is %f :(%d, %d)\n", min_distance, *cluster_1, *cluster_2);
}/** combine the two clusters to one* */
void combineCluster(int cluster_1, int cluster_2)
{int i;int buffer;buffer = distance[cluster_2][0];for( i = 1; i <= sample_size; i++ ){if( distance[i][0] == buffer ){distance[i][0] = distance[cluster_1][0];}}//testprintf(" the minimum distance is %f, and the object is %d and %d\n", distance[cluster_1][cluster_2], cluster_1, cluster_2);int j;for( i = 1; i <= sample_size; i++ ){for( j = 0; j <= sample_size; j++ ){printf("%f ", distance[i][j]);}printf("\n");}
}/** write the result of clustering information to file* */
void writeToFile(int round)
{int i;int j;int* auxiliary = (int*)malloc(sizeof(int) * (sample_size + 1));if( !auxiliary ){printf("auxiliary malloc error");exit(0);}for( i = 1; i <= sample_size; i++ )auxiliary[i] = 0;for( i = 1; i <= sample_size; i++ ){auxiliary[(int)distance[i][0]]++;}int *clusterID = (int*)malloc(sizeof(int) * (sample_size - round + 1));if( !clusterID ){printf("clusterID malloc error");exit(0);}int counter = 1;for( i = 1; i <= sample_size; i++ ){if( auxiliary[i] != 0 )clusterID[counter++] = i;}//testprintf("cluster ID:");for( i = 1; i <= sample_size - round; i++ ){printf("%d ", clusterID[i]);}printf("\n");//test ENDprintf("writeToFile -----------round: %d\n", round);FILE** fwrite;fwrite = (FILE**)malloc(sizeof(FILE*) * (sample_size + 1));if( !fwrite ){printf("fwrite malloc error\n");exit(0);}char filename[200] = "";char instruction[200] = "";sprintf(instruction, "md  Round_%d", round);system(instruction);for( i = 1; i <= sample_size - round; i++ ){sprintf(filename, ".//Round_%d//cluster_%d.data", round, clusterID[i]);if( NULL == (fwrite[clusterID[i]] = fopen(filename, "w"))){printf("open file(%s) error\n", filename);exit(0);}}for( i = 1; i <= sample_size; i++ ){printf("%d ", (int)distance[i][0]);for( j = 1; j <= sample_dimension; j++ ){fprintf(fwrite[(int)distance[i][0]], "%f\t", data[i][j]);printf("%f ", data[i][j]);}fprintf(fwrite[(int)distance[i][0]], "\n");printf("\n");}for( i = 1; i <= sample_size - round; i++ ){fclose(fwrite[clusterID[i]]);}
}

complete-linkage算法 

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<io.h>int sample_size;
int sample_dimension;
char filename[200];double** data;
double** distance;
int cluster_count;void initialization();
void readDataFromFile();
double calculateDistance_BetweenTwoObject(int, int);
void initializationDistanceMatrix();
void findMinDistance_BetweenClsuter_MAX(int*, int*);
void AGNES();
void combineCluster(int, int);
void updateDistance(int);
void writeToFile(int);int main(int argc, char* argv[])
{if( argc != 4 ){printf("This algorithm requires 4 user-specified parameter""\n\t\tthe number of sample""\n\t\tthe dimension of sample""\n\t\tthe filename contain the sample""\n\n");exit(0);}sample_size = atoi(argv[1]);sample_dimension = atoi(argv[2]);strcat(filename, argv[3]);initialization();readDataFromFile();initializationDistanceMatrix();AGNES();return 0;
}/** initialize the dynamic array for storing sample* */
void initialization()
{//initializaion the sample dataint i, j;data = (double**)malloc(sizeof(double*) * (sample_size + 1));if( !data ){printf("data malloc error: 0");exit(0);}for( i = 1; i <= sample_size; i++ ){data[i] = (double*)malloc(sizeof(double) * (sample_dimension + 1));if( !data[i] ){printf("data malloc error: %d", i);exit(0);}}//initialiation the distance datadistance = (double**)malloc(sizeof(double*) * (sample_size + 1));if( !distance ){printf("distance malloc error: 0");exit(0);}for( i = 0; i <= sample_size; i++ ){distance[i] = (double*)malloc(sizeof(double) * (sample_size + 1));if( !distance[i] ){printf("distance malloc error: %d", i);exit(0);}}//the 0th element of all row indicate the clauterID of the objectfor( i = 1; i <= sample_size; i++ ){distance[i][0] = i;}//where reserved if distance[0][i] = 1, for( i = 1; i <= sample_size; i++ ){distance[0][i] = 1;}
}/** read the sample data from file* */
void readDataFromFile()
{FILE* fread;int i;int j;if( NULL == (fread = fopen(filename, "r"))){printf("open file(%s) error: ", filename);exit(0);}for( i = 1; i <= sample_size; i++ ){for( j = 1; j <= sample_dimension; j++ ){if( 1 != fscanf(fread, "%lf ", &data[i][j])){printf("fscanf error: (%d, %d)", i, j);exit(0);}}}
}/** calculate distance between two objects* */
double calculateDistance_BetweenTwoObject(int firstID, int secondID)
{double distance = 0.0;int i;for( i = 1; i <= sample_dimension; i++ ){distance = distance + pow(data[firstID][i] - data[secondID][i], 2);}return sqrt(distance);
}/** calculate initialization distance matrix* */
void initializationDistanceMatrix()
{int i, j;for( i = 1; i <= sample_size; i++ ){for( j = i; j <= sample_size; j++ ){distance[i][j] = calculateDistance_BetweenTwoObject(i, j);distance[j][i] = distance[i][j];}}
}/****************************************************************************************************************						AGNES***************************************************************************************************************/
void AGNES()
{cluster_count = sample_size;int cluster_1, cluster_2;int count = 1;while( cluster_count > 3 ){printf("-------------------%d--------------------\n", count);findMinDistance_BetweenClsuter_MAX(&cluster_1, &cluster_2);combineCluster(cluster_1, cluster_2);updateDistance(cluster_1);		cluster_count--;writeToFile(count++);}
}/** find two clusters the distance between them is minimun, and store the clusterID in @cluster_1 and @cluster_2, respectively.* */
void findMinDistance_BetweenClsuter_MAX(int* cluster_1, int* cluster_2)
{int i, j;double min_distance;int flag = 1;int object_1;int object_2;for( i = 1; i <= sample_size; i++ ){for( j = i + 1; j <= sample_size; j++ ){if( distance[i][0] == distance[j][0] || ( distance[0][i] == 0 || distance[0][j] == 0 ) ){continue;}else if( flag == 1 ){min_distance = distance[i][j];object_1 = i;object_2 = j;flag = 0;continue;}if( distance[i][j] < min_distance ){min_distance = distance[i][j];object_1 = i;object_2 = j;}}}*cluster_1 = distance[object_1][0];*cluster_2 = distance[object_2][0];
}/** combine the two clusters to one* */
void combineCluster(int cluster_1, int cluster_2)
{int i;for( i = 1; i <= sample_size; i++ ){if( distance[i][0] == cluster_2 ){distance[i][0] = cluster_1;}}
}/** update distance data* */
void updateDistance(int clusterID)
{int i, j;int flag = 1;int save_i;for( i = 1; i <= sample_size; i++ ){if( distance[i][0] == clusterID && flag == 1 ){flag = 0;save_i = i;continue;}else if( distance[i][0] == clusterID && flag == 0 ){distance[0][i] = 0;for( j = 1; j <= sample_size; j++ ){if( distance[i][j] > distance[save_i][j] ){distance[save_i][j] = distance[i][j];}}}}for( i = 1; i <= sample_size; i++ ){distance[i][save_i] = distance[save_i][i];}
}/** write the result of clustering information to file* */
void writeToFile(int round)
{int i;int j;int* auxiliary = (int*)malloc(sizeof(int) * (sample_size + 1));if( !auxiliary ){printf("auxiliary malloc error");exit(0);}for( i = 1; i <= sample_size; i++ )auxiliary[i] = 0;for( i = 1; i <= sample_size; i++ ){auxiliary[(int)distance[i][0]]++;}int *clusterID = (int*)malloc(sizeof(int) * (sample_size - round + 1));if( !clusterID ){printf("clusterID malloc error");exit(0);}int counter = 1;for( i = 1; i <= sample_size; i++ ){if( auxiliary[i] != 0 )clusterID[counter++] = i;}printf("writeToFile -----------round: %d\n", round);FILE** fwrite;fwrite = (FILE**)malloc(sizeof(FILE*) * (sample_size + 1));if( !fwrite ){printf("fwrite malloc error\n");exit(0);}char filename[200] = "";char instruction[200] = "";sprintf(instruction, "md  Round_%d", round);system(instruction);for( i = 1; i <= sample_size - round; i++ ){sprintf(filename, ".//Round_%d//cluster_%d.data", round, clusterID[i]);if( NULL == (fwrite[clusterID[i]] = fopen(filename, "w"))){printf("open file(%s) error\n", filename);exit(0);}}for( i = 1; i <= sample_size; i++ ){printf("%d ", (int)distance[i][0]);for( j = 1; j <= sample_dimension; j++ ){fprintf(fwrite[(int)distance[i][0]], "%f\t", data[i][j]);}fprintf(fwrite[(int)distance[i][0]], "\n");}for( i = 1; i <= sample_size - round; i++ ){fclose(fwrite[clusterID[i]]);}
}


这篇关于层次聚类算法之single-linkage和complete-linkage（C语言实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/185619。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2