信息与电气工程学院
实 验 报 告
（2023-2024 学年第 2 学期）
课程名称 模式识别
实验题目 基于距离阈值的聚类算法
专 业 计算机科学与技术
2023 年 9 月 15 日
1
实验题目
紧邻聚类算法
实验类型
验证型
实验日期
2023.9.15
题目来源
自拟（设计）
一、实验目的及要求
1. 实验目的:
(1).
实现近邻聚类算法
(2).
实现对样本数据的分类
2. 实验要求：
(1).
掌握近邻聚类算法的原理与实现
(2).
掌握最大距离算法的原理与实现
(3).
掌握使用近邻聚类算法对样本数据分类，并分析性能影响
(4).
掌握使用最大距离算法对样本数据分类，并分析性能影响
二、实验仪器设备与软件环境
64 位操作系统的 win10
处理器：AMD Ryzen 7 5800H with Radeon Graphics 3.20 GHz
三、实验过程及实验结果分析
（包括实验原理、步骤、数据、图表、结果及分析。软件类实验应写出程序代
码；硬件类实验画出电路原理图（或逻辑框图）、列出实验数据，并对实验结果
进行分析）
一：近邻聚类法
1.1: 算法原理：
（1）. 任取样本�
�
作为第一个聚类中心的初始值，如令�
1
= �
1
。
（2）. 计算样本𝑋
2
到𝑍
1
的欧氏距离 D
12
= ||X
2
− Z
1
|| ， 若D
21
> T，定义一新
的聚类中心𝑍
2
= 𝑋
2
否则 𝑋
2
∈以𝑍
1
为中心的聚类。
(3) . 假设已有聚类中心𝑍
1
、𝑍
2
，计算D
31
= ||X
3
− Z
1
|| 和 D
32
= ||X
3
− Z
2
||，
若 D
31
> T且 D
32
> T ，则建立第三个聚类中心𝑍
3
= 𝑋
3
；
2
否则 X3∈离 Z1 和 Z2 中最近者（最近邻的聚类中心）。
……依此类推，直到将所有的 N 个样本都进行分类。
1.2
: 算法复杂度分析：
根据阈值的不同和点集范围的不同 ， 复杂度不同 ， 但是存在一个复杂度上
限 ， 即当每一个点都成为一个聚类中心的时候 ， 复杂度为：
O
(
n
2
)
1.3
: 数据处理：
(1)
.数据生成：
使用 C++ 的 rand() 函数随机生成 n 个范围在[0 - 999]以内的随机点对。
x = rand() % 1000;
y = rand() % 1000;
p[i] = point{x , y};
(2)
. 第一个聚类中心的选择：
使用 C++ 的 rand() 函数随机生成一个点作为聚类中心。
id = rand() % n;
(3)
. 阈值的确定：
规定一个常数作为阈值。
const double T = 400;
(4)
. 聚类过程中的数据的存放：
point p[N]; //存放点集
int center[N] , cnt;//存放聚类中心标号
vector<int>ve[N];//存放每一个聚类点集合
1.4
: 实验步骤：
1.4.1 ：手动输入 n ， 随机生成平面上 n 个二维点对
x = rand() % 1000;
y = rand() % 1000;
p[i] = point{x , y};
1.4.2 任取一个点作为聚类中心 ， 并处理这个点的相关信息
id = rand() % n;
3
1.4.3 遍历每个点 ， 计算当前点和所有聚类中心的距离最小值 ， 如果这个值大于
阈值 ， 则将这个点作为新的聚类中心 ， 否则将这个点放入距离最近的类中。
1.4.4 算法花费时间记录 ， 采用 C++ 的 clock 函数记录整个过程花费的时间
1.4.5 使用 python 的 matplotlib 中的 pyplot 库绘制散点图查看聚类结果。
1.5
: 实验结果及分析：
分别使用不同范围的点集进行实验
1.5.1 使用 100 个点进行实验：
具体运行结果如下(图 1.1 —— 图 1.3)
//计算当前点和已有的聚类中心的距离
if(dist(p[center[j]] , p[i]) < T){
tag = 1;
if(dist(p[center[j]] , p[i]) < minn){
minn = dist(p[center[j]] , p[i]);
now = center[j];
}
}
//找不到合适的距离中心
if(!tag) center[++cnt] = i , ve[i].push_back(i);
else ve[now].push_back(i);//找到了最近的聚类中心
start = clock();
ed = clock();
double waste = (double)(ed - start) / CLOCKS_PER_SEC;
plt.scatter(x_1 , y_1 , label = "第一个聚类" , color =
"#000000" )
plt.show()
