基于改进局部密度的可扩展层次聚类算法

图1 DBSC算法的流程

Fig.1 The processing of DBSC

3.1　构建最近邻分量

构造最近邻分量是DBSC的基础步骤，其主要目的是：（1）通过最近邻关系划分数据集；（2）定位每个最近邻分量上的互惠最近邻.使用Ball⁃Tree算法^［10］可以快速获得结点间的最近邻关系，紧接着连接每个最近邻对，如果发现某对结点重复连接，说明该对结点为互惠最近邻，最后从互惠最近邻点开始执行广度优先搜索，就可以得到多个最近邻分量.此外，如果存在孤立最近邻分量，则通过 $i N N C s R e p$ 进行再优化.而 $R o o t s D e t$ 将通过局部密度在互惠最近邻中选择一个最佳的代表点.

该过程的伪代码如算法2所示. $N N C s C o n$ 首先初始化一个集合 $R N N s$ 用于保存互惠最近邻， $𝒯$ 用于保存最近邻分量（步骤1），然后计算数据集合 $r$ 的最近邻关系保存在集合 $E$ 中（步骤2）.接下来，通过一个循环遍历集合 $E$ （步骤3~5），当 $x_{i}$ 和 ${δ_{i}}^{(1)}$ 没有连接时，连接 $x_{i}$ 和 ${δ_{i}}^{(1)}$ （步骤5）.否则，说明 $x_{i}$ 和 ${δ_{i}}^{(1)}$ 是互惠最近邻，将其添加至 $R N N s$ 中（步骤4）.最后通过一个循环遍历集合 $R N N s$ （步骤6~8），从互惠最近邻结点开始执行广度优先搜索（步骤7），并返回最近邻分量保存在集合 $𝒯$ 中（步骤8）.最后返回最近邻分量集合 $𝒯$ （步骤9）.

算法2 NNCsCon算法

输入：数据集合 $r$

输出：最近邻分量集合 $𝒯$

1. $R N N s \leftarrow \emptyset$ ， $𝒯 \leftarrow \emptyset$

2. $E \leftarrow g e t N e a r e s t N e i g h b o r s (r)$ ∥计算每个结点的最近邻

3.for each $e = (x_{i}, {δ_{i}}^{(1)})$ in $E$ do

4. if $x_{i}$ 和 ${δ_{i}}^{(1)}$ 已连接 $R N N s . a p p e n d (e)$ ∥保存最近邻对

5. else 将 $x_{i}$ 和 ${δ_{i}}^{(1)}$ 连接

6.for each $R N N$ in $R N N s$ do

7. $τ \leftarrow B F S (R N N)$ ∥通过广度优先搜索遍历NNC

8. $𝒯 . a p p e n d (τ)$

9.return $𝒯$

图2为 $N N C s C o n$ 算法流程的示意图，七个结点的初始位置如图2a所示，阴影部分标明它们位于图1的位置.图2b为七个结点之间距离的热力图.由于互惠最近邻会被连接两次，所以被算法轻易地识别出来.如图2c所示，互惠最近邻为结点1和结点2.如图2d所示，在获取互惠最近邻后，算法通过广度优先搜索遍历其孩子结点，即结点4，5和7.最后，直至结点4的最近邻结点3和结点5的最近邻结点6被访问，至此算法得到一个完整的最近邻分量 $τ$ ，如图2e所示.

图2

图2 NNCsCon算法的流程

Fig.2 The processing of NNCsCon

3.2　重连孤立最近邻分量

由于iNNC的两个节点的密度相等，所以无法有效识别唯一的代表点.为了保证对于每个NNC都存在唯一一个代表点，本文提出一种优化策略.该策略将借助iNNC的二阶最近邻结点定位距离它最近的NNC.然后将iNNC和结点数量较小的NNC相连接.通过该操作，一方面解决最近邻选择策略无法作用于iNNC的问题，另一方面通过增加结点数量以加强局部密度对于选择代表点的作用.

该过程的伪代码如算法3所示.

算法3

iNNCsRep算法

输入：最近邻分量集合 $𝒯$

输出：最近邻分量集合 $𝒯$

1.从 $𝒯^{*}$ 抽取孤立最近邻集合 $𝒯$

2.For each $e = (x, y)$ in $𝒯^{*}$ do

3. 寻找 $x, y$ 的第二近邻 $δ_{x}^{(2)}, δ_{y}^{(2)}$

4. $τ_{x}, τ_{y} \leftarrow B F S (δ_{x}^{(2)}, δ_{x}^{(2)})$ ∥通过广度优先搜索寻找NNC

5. If $|τ_{x}| \leq |τ_{y}|$ then 连接 $τ_{x}$ 和 $τ$ ∥选择结点数量较小的NNC重连

6. Else 连接 $τ_{y}$ 和 $τ$

7.return $𝒯$

$i N N C s R e p$ 算法遍历最近邻分量集合 $𝒯$ 获得孤立最近邻分量集合 $𝒯^{*}$ （步骤1）；遍历 $𝒯^{*}$ （步骤2~6），其中，步骤3和步骤4是在循环过程中，首先借助构成孤立最近邻的结点 $x, y$ 定位它们二阶最近邻 $δ_{x}^{(2)}, δ_{y}^{(2)}$ 所在的最近邻分量 $τ_{x}, τ_{y}$ ；步骤5和步骤6是判断 $τ_{x}$ 和 $τ_{y}$ 的结点数量 $|τ_{x}|$ 和 $|τ_{y}|$ 的大小，将孤立最近邻分量 $τ^{*}$ 与结点数量较少的最近邻分量重连为一个新的最近邻分量；最后返回 $𝒯$ （步骤7）.

图3a展示了 $τ_{A}, τ_{B}, τ_{C}$ 的相对位置，阴影部分标明它们位于图1的区域，其中 $τ_{C}$ 是孤立最近邻分量， $τ_{A}, τ_{B}$ 分别是构成 $τ_{C}$ 的结点 $x, y$ 的二阶最近邻 $δ_{x}^{(2)}, δ_{y}^{(2)}$ 所在的最近邻分量.由于 $|τ_{A}| = 7$ ， $|τ_{B}| = 4$ ，因此， $i N N C s R e p$ 将 $τ_{B}$ 和 $τ_{C}$ 重连为一个新的最近邻分量.

图3

图3 iNNCsRep和RootsDet的流程

Fig.3 The processing of iNNCsRep and RootsDet

3.3　寻找代表结点

DBSC的最后一步就是在每个RNN中选择一个结点，该结点将作为最近邻分量的根结点.在后续迭代过程中，代表结点代替最近邻分量中的其余结点参与聚类树的构造.因此，每轮迭代后，需要计算的数据量将大幅减少.本文采用基于密度的代表点选举策略，给定截断阈值 $α$ ，对于每个最近邻分量 $τ$ ，都存在唯一一个截断距离 $d_{c}$ ，计算如下：

d_{c} = M (⌈l e n (M) \times α⌉)

（1）

其中， $M$ 是将 $τ$ 的成对距离数组正序排列后的一维数组列表， $α$ 代表截断阈值.

给定一个最近邻组件 $C = (V, E)$ ，设向量集 $V = {\{x_{i}\}}_{1}^{m}$ 的点对距离为 $d_{i j}$ ，则向量 $x_{i}$ 的局部密度 $ρ_{i}$ 定义如下：

ρ_{i} = \sum_{j \in τ} χ (d_{i j} - d_{c})

（2）

其中， $χ (x) = \{\begin{matrix} 1, x < 0 \\ 0, x > 0 \end{matrix}$ ， $d_{c}$ 为截断距离.

该过程的伪代码如算法4所示.

算法4

RootsDet算法

输入：最近邻分量集合 $𝒯$ ，截断阈值 $α$

输出：根节点集合 $r$

1. $r \leftarrow \emptyset$

2.For each $τ$ in $𝒯$ do

3. $x, y \leftarrow τ$

4. $M \leftarrow$ getPairsDistances（ $τ$ ） ∥计算NNC的成对距离

5. $d_{c} = M (⌈l e n (M) \times α⌉)$ ∥确定截断距离

6. $ρ_{x}, ρ_{y} = \sum_{j \in τ} χ (d_{i j} - d_{c})$ ∥由式（2）计算RNN的局部密度

7. If $ρ_{x} > ρ_{y}$ then $r \leftarrow x$ ∥选择局部密度大的结点作为根

8. else $r \leftarrow y$

9. $r = r ⋃ r$

10.return $r$

RootsDet遍历每个最近邻分量 $τ$ （步骤2~9）得到对应的根结点 $r$ 并保存在集合 $r$ 中（步骤1）.在迭代过程中，算法首先获得 $τ$ 的互惠最近邻结点 $x, y$ （步骤3），并计算 $τ$ 的成对距离以正序排列的方式保存在一维数组 $M$ 中（步骤4）.通过 $M$ 和截断阈值 $α$ 计算得到截断距离 $d_{c}$ （步骤5，式（1））和结点 $x, y$ 的局部密度 $ρ_{x}, ρ_{y}$ （步骤6，式（2））.最后通较 $ρ_{x}$ 和 $ρ_{y}$ （步骤7~8），选择局部密度最大的结点 $r$ 作为 $τ$ 的根结点保存在集合 $r$ 中（步骤9）.

如图3b所示，在 $τ_{A}$ 中结点1和结点2是一对互惠最近邻， $d_{c}$ 是截断阈值 $α = 0.3$ 时的截断距离.根据式（2），如图3c所示，结点2的局部密度 $ρ_{2} = 4$ ，结点1的局部密度 $ρ_{1} = 5$ .由于 $ρ_{2} < ρ_{1}$ ，因此根结点为结点1.

3.4　复杂度分析

DBSC算法主要包括三个步骤：（1）最近邻图的构建 $N N C s C o n$ ；（2）孤立互惠最近邻的重连 $i N N C s R e p$ ；（3）代表点的选择 $R o o t s D e t$ .步骤1，每个数据结点被连接到其最近的邻居.在面对多维数据时，通常应用一些快速搜索方法（Ball⁃Tree）^［26］来寻找所有数据结点的最近邻居，其时间复杂度为 $O (n l g n)$ .因此，步骤1的时间复杂度为 $O (n l g n)$ .步骤2，假设iNNC的数量为 $m$ ，因此遍历每个iNNC的时间复杂度为 $O (m)$ ，通过计算和比较NNC中的结点数量来重连每个iNNC的时间复杂度是 $O (n)$ ，因此，步骤2的时间复杂度是每轮迭代的 $O (m + n)$ .步骤3，由于局部密度的比较，需要对NNC中的结点进行成对距离计算.在一轮迭代中，假设有 $p$ 个NNC，每个NNC平均有 $q$ 个结点，因此，步骤3的时间复杂度为 $O (p q^{2})$ ，其中， $p q$ 等于当前一轮迭代中的结点数量.考虑最坏的情况，所有检测到的NNC都是iNNC，每轮迭代将提取结点数的一半的根，即每轮迭代都提取一半的结点，在这种情况下DBSC将构建一棵二叉树，进行 $t = l o g_{2} n$ 轮迭代.结合步骤1~3，DBSC的总体时间复杂度如下所示：

\begin{array}{l} T = (\begin{matrix} \underset{i t e r a t i o n 1}{\underset{︸}{n l g n + \frac{n}{2} + p q^{2}}} \end{matrix}) + (\begin{matrix} \underset{i t e r a t i o n 2}{\underset{︸}{\frac{n}{2^{2}} l g \frac{n}{2^{2}} + \frac{n}{2^{2}} + p q^{2}}} \end{matrix}) + (\begin{matrix} \underset{i t e r a t i o n 3}{\underset{︸}{\frac{n}{2^{3}} l g \frac{n}{2^{3}} + \frac{n}{2^{3}} + p q^{2}}} \end{matrix}) + \cdot \cdot \cdot < \\ (\begin{matrix} n + \frac{n}{2^{2}} + \frac{n}{2^{3}} + \cdot \cdot \cdot \end{matrix}) l g n + (\begin{matrix} \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdot \cdot \cdot \end{matrix}) n + 2 n \times l o g_{2} n < O (2 n l g n) + O (n) + O (2 n l g n) \in O (n l g n) \end{array}

由上可知，DBSC的时间复杂度为 $O (n l g n)$ .此外，由于DBSC不需要辅助结点，只有一个参数 $α$ 是全局驻留的.因此，DBSC的空间复杂度仅为 $O (1)$ .

4 实验

4.1　实验数据集

采用12个真实数据集对算法进行测试，证明本文提出的算法解决现实问题的效果，其中包括七个UCI数据集和五个大型数据集：ALOI^［27］代表物体的三维渲染，地面真相集群指每个物体类型；ILSVRC（Ⅰ）和ILSVRC（Ⅱ）代表ImageNet ILSVRC 2012^［28］的图像，其矢量表示源自inception神经网络的最后一层；CovType^［8］代表森林覆盖类型；har代表经过专业注释的15位老人的人类活动识别数据集.以上数据集的基本信息如表1所示.

表1 实验中采用的来源于真实世界的数据集

Table 1 The datasets derived from real⁃world sources used in experiments

编号	名称	样本数	属性	类别
1	mfeat⁃fourier	2000	76	10
2	mfeat⁃karhune	2000	64	10
3	mfeat⁃zernike	2000	47	10
4	segment	2310	18	7
5	optdigits	5620	62	10
6	letter	20000	16	26
7	avila	20867	10	12
8	ALOI	108K	128	1000
9	ILSVRC(Ⅰ)	500K	100	400
10	ILSVRC(Ⅱ)	500K	100	400
11	CovType	500K	54	7
12	har	2259K	7	15

实验使用的人工数据集是利用在机器学习领域广泛使用的python工具包sklearn生成不同数量的数据集.这些数据集具有十个维度，大小为 $2^{n}, n \in [9,17]$ .

4.2　评价指标

兰德指数^［29］（Rand Index，RI）考虑所有样本对，计算在预测聚类和真实聚类中分配在相同或不同聚类中的对来计算两个聚类之间的相似性度量.取值为 $[0,1]$ ，值越大，说明聚类效果越好，与真实情况越拟合，计算如下：

R = \frac{a + b}{C_{2}^{n}}

（3）

其中， $a$ 表示两种聚类方法中一对元素属于同一簇的次数， $b$ 表示在两种聚类方法中一对元素属于不同聚类的次数， $C_{2}^{n}$ 表示数据集中可以组成的总元素对数.

调整兰德指数^［30］（Adjusted Rand Index，ARI）通过计算在真实标签和聚类结果中被分配在相同或不同类簇的样本对的个数来进行聚类有效性的评价.其取值为 $[- 1,1]$ ，值越大，说明聚类效果越好，与真实情况越拟合.计算如下：

A R I = \frac{R I - E (R I)}{m a x (R I) - E (R I)}

（4）

归一化互信息^［31］（Normalized Mutual Information，NMI）可以衡量两个数据分布的吻合程度，表示两个事件集合之间的相关性.其取值为 $[0,1]$ ，值越大，说明聚类效果越好，与真实情况越拟合.计算如下：

N M I (Ω, C) = \frac{I (Ω; C)}{(H (Ω) + H (C)) / 2}

（5）

其中， $I (Ω; C)$ 表示互信息， $H (Ω)$ 为熵.

4.3　对比算法

对于小规模数据集的参数 $α = 0.70$ ，用DBSC（0.7）表示；对于大规模数据集的参数 $α = 0.50$ ，用DBSC（0.5）表示.此外，对小规模数据集在 $α = \{n \times 0.05 |n \in [1,14]\}$ 范围内进行参数调优，最优结果用DBSC（opt= $α$ ）表示.

RSC^［7］是一种高效的凝聚式层次聚类算法，借助最近邻链和人造结点构造聚类树.

HK⁃means^［8］是一种自顶向下的层次聚类算法，使用K⁃means算法划分并构造聚类树.

SCC^［11］是一种基于一阶最近邻图和传统连接方法的可扩展的凝聚式层次聚类算法.

Munec^［13］是一种凝聚式的层次聚类算法，同时考虑了距离和最近邻对于簇的影响.

DPC^［17］是基于密度峰值的聚类算法，使用决策图选择密度中心进行聚类.

HAC^［32］是传统的凝聚式层次聚类算法，本文算法使用average⁃link方式进行聚类.

Affinity^［33］是基于Boruvka最小生成树和链接函数的层次聚类.

GRINCH^［34］是一种用于大规模、非贪婪的分层聚类的聚类算法.

streaKHC^［35］是一种流式聚类算法，基于随机划分判断簇间相似性进行点对合并操作.

4.4　实验环境配置

硬件设备CPU为i9⁃12900，内存为64 G，操作系统为Windows 11.编程语言采用Python 3.8.

4.5　参数敏感性

如图4所示，使用RI，ARI和NMI指标测量的DBSC算法精度在avila，letter，optdigits数据集上波动较小，但是在其他数据集上波动明显，证明DBSC对于参数 $α$ 的选择略微敏感，但并没有明显趋势.

图4

图4 参数 $α$ 的敏感性测试

Fig.4 The sensitivity testing of parameter $α$

4.6　聚类准确性

表2展示了所有算法在七个普通UCI数据集上的表现，表中黑体字表示性能最优，下划线表示性能次优.其中，DBSC（opt= $α$ ）表示DBSC的最佳情况， $α$ 表示取得最佳效果的参数值.DBSC（0.7）表示当参数 $α = 0.7$ 时DBSC的表现.分析表明，与其他算法相比，DBSC在mfeat⁃fourier，mfeat⁃karhune，mfeat⁃zernike，optdigits，avila五个数据集上的RI，ARI，NMI指标均达到最优；在segment数据集上，仅有NMI略低于Affinity算法，letter数据集仅有ARI略低于RSC算法.除此之外，DBSC是表现最好的算法.并且在平均情况下，DBSC全部达到最优.由此可见，DBSC在聚类准确性上优于其他算法.经过分析表明，DBSC即使随机选取一个参数 $α$ ，在大多数情况下表现仍旧好于其他算法，并且在平均情况下可达到最优.可见，DBSC算法的下限仍高于其他算法的上限.

表2 本文算法和对比算法在UCI数据集上的聚类结果

Table 2 The clustering results of our algorithm and other algorithms on UCI datasets

数据集	算法	RI	ARI	NMI	数据集	算法	RI	ARI	NMI
mfeat⁃fourier	DBSC(opt=0.65)	0.8810	0.3680	0.5345	mfeat⁃karhune	DBSC(opt=0.2)	0.9305	0.6261	0.7384
	DBSC(0.7)	0.8308	0.3204	0.5163		DBSC(0.7)	0.9090	0.5385	0.6990
	HAC	0.1818	0.0040	0.0816		HAC	0.5016	0.1030	0.3423
	Affinity	0.7980	0.2159	0.4523		Affinity	0.8965	0.5086	0.6778
	DPC	0.5036	0.0796	0.1897		DPC	0.7228	0.1766	0.3798
	GRINCH	0.1988	0.0002	0.0159		GRINCH	0.2091	<0.0001	0.0233
	HK⁃means	0.8562	0.3169	0.4557		HK⁃means	0.8959	0.3964	0.5316
	Munec	0.8168	0.2581	0.4821		Munec	0.8729	0.3294	0.6209
	RSC	0.8367	0.3195	0.5046		RSC	0.8830	0.5172	0.7110
	SCC	0.1028	<0.0001	0.0028		SCC	0.4869	0.0261	0.1333
	streaKHC	0.8619	0.3035	0.4220		streaKHC	0.8737	0.3539	0.4710
mfeat⁃zernike	DBSC(opt=0.35)	0.9084	0.5174	0.6270	segment	DBSC(opt=0.3)	0.8910	0.5584	0.6396
	DBSC(0.7)	0.8729	0.4322	0.6009		DBSC(0.7)	0.8862	0.5434	0.6246
	HAC	0.5733	0.1368	0.4016		HAC	0.5983	0.2394	0.5757
	Affinity	0.8036	0.2592	0.4650		Affinity	0.8752	0.5090	0.6481
	DPC	0.4934	0.0296	0.0617		DPC	0.3970	0.0122	0.0320
	GRINCH	0.3800	0.0601	0.1636		GRINCH	0.5897	0.2385	0.3908
	HK⁃means	0.8565	0.3195	0.4323		HK⁃means	0.8412	0.4165	0.5391
	Munec	0.8293	0.2354	0.5365		Munec	0.8428	0.2052	0.5154
	RSC	0.8893	0.4667	0.5903		RSC	0.7311	0.3043	0.5329
	SCC	0.6082	0.0701	0.1829		SCC	0.6148	0.2139	0.3669
	streaKHC	0.8609	0.3158	0.4358		streaKHC	0.8592	0.4625	0.5699
optdigits	DBSC(opt=0.15)	0.9722	0.8401	0.8694	letter	DBSC(opt=0.4)	0.9261	0.1355	0.4027
	DBSC(0.7)	0.9576	0.7603	0.8373		DBSC(0.7)	0.9140	0.1303	0.3941
	HAC	0.8956	0.5517	0.7341		HAC	0.7841	0.0608	0.3342
	Affinity	0.9640	0.8010	0.8433		Affinity	0.9047	0.1283	0.3830
	DPC	0.6551	0.1146	0.2730		DPC	0.0663	0.0001	0.0066
	GRINCH	0.2754	0.0160	0.1001		GRINCH	0.2311	0.0017	0.0514
	HK⁃means	0.9119	0.5374	0.6347		HK⁃means	0.8323	0.0713	0.2440
	Munec	0.7739	0.1791	0.5729		Munec	0.5131	0.0092	0.2367
	RSC	0.8623	0.4832	0.7013		RSC	0.9145	0.1498	0.3927
	SCC	0.7108	0.1906	0.3654		SCC	0.3948	0.0059	0.0511
	streaKHC	0.8946	0.4515	0.5507		streaKHC	0.9125	0.0836	0.2396
avila	DBSC(opt=0.15)	0.7249	0.0929	0.1842	Mean	DBSC(opt)	0.8906	0.4483	0.5708
	DBSC(0.7)	0.7134	0.0643	0.1820		DBSC(0.7)	0.8691	0.3985	0.5527
	HAC	0.2820	<0.0001	0.0328		HAC	0.5452	0.1557	0.3575
	Affinity	0.7113	0.0528	0.1617		Affinity	0.8505	0.3535	0.5188
	DPC	0.5009	0.0151	0.0814		DPC	0.4770	0.0611	0.1463
	GRINCH	0.2967	0.0069	0.0420		GRINCH	0.3115	0.0461	0.1124
	HK⁃means	0.2598	<0.0001	0.0199		HK⁃means	0.7791	0.2932	0.4082
	Munec	0.5761	0.0480	0.1615		Munec	0.7464	0.1806	0.4466
	RSC	0.5271	0.0224	0.0714		RSC	0.8063	0.3233	0.5006
	SCC	0.2484	<0.0001	0.0284		SCC	0.4524	0.0716	0.1615
	streaKHC	0.7224	0.0245	0.0886		streaKHC	0.8550	0.2850	0.3968

表3展示了所有算法在大型数据集上的表现，表中黑体字表示性能最优，“-”表示由于内存需求过大无法在实验环境中运行的算法.DBSC（0.5）表示参数 $α = 0.5$ 时DBSC的表现.分析表明，与其他算法相比，DBSC在大型数据集上表现优秀，在ILSVRC（Ⅰ），ILSVRC（Ⅱ），har三个数据集上的RI，ARI，NMI指标均达到最高.在ALOI数据集上仅有NMI指标略低于RSC算法，在CovType数据集上，ARI和NMI低于HK⁃means算法.而在平均情况下，DBSC全部达到最优.由此可见，DBSC在大型数据集上的聚类准确性也优于其他算法.

表3 本文算法和对比算法在五个大规模数据集上的聚类结果

Table 3 The clustering results of our algorithm and other algorithms on five large⁃scale datasets

数据集	算法	RI	ARI	NMI	数据集	算法	RI	ARI	NMI
ALOI	DBSC（0.5）	0.9990	0.4543	0.7834	CovType	DBSC（0.5）	0.6113	0.0346	0.1592
	HK⁃means	0.9921	0.0864	0.6701		HK⁃means	0.5997	0.0941	0.1595
	RSC	0.9962	0.2565	0.8004		RSC	0.5645	0.0083	0.0461
	SCC	0.9900	<0.0001	0.6915		SCC	0.4316	0.0504	<0.0001
	streaKHC	0.0901	<0.0001	0.0600		streaKHC	-	-	-
ILSVRC(I)	DBSC（0.5）	0.9851	0.0420	0.3031	ILSVRC(Ⅱ)	DBSC（0.5）	0.9918	0.0483	0.3309
	HK⁃means	0.5181	0.0002	0.0439		HK⁃means	0.5700	0.0002	0.0385
	RSC	0.6343	0.0011	0.2042		RSC	0.9867	0.0291	0.3050
	SCC	0.1585	<0.0001	0.0143		SCC	0.2696	<0.0001	0.0125
	streaKHC	-	-	-		streaKHC	-	-	-
har	DBSC（0.5）	0.7049	0.2718	0.4406	Mean	DBSC（0.5）	0.8584	0.1702	0.4035
	HK⁃means	0.6409	0.1749	0.2679		HK⁃means	0.6642	0.0711	0.2360
	RSC	0.5795	0.2476	0.3851		RSC	0.7523	0.1085	0.3482
	SCC	-	-	-		SCC	-	-	-
	streaKHC	-	-	-		streaKHC	-	-	-

4.7　统计学检验评估

为了验证DBSC算法的上述优势具有统计学意义，进行配对 $t$ 检验.将零假设设为 $H_{0} : R_{D B S C} - R_{b a s e l i n e} = 0$ ，备选假设为 $H_{a} : R_{D B S C} - R_{b a s e l i n e} \neq 0$ ，其中， $R_{D B S C}$ 和 $R_{b a s e l i n e}$ 分别代表DBSC和其他算法的聚类精度（用RI，ARI和NMI度量）.表4展示了所有数据集上的统计测试结果，由表可见，最高的 $p = 0.0277$ （streaKHC，RI，黑体标注）.证明DBSC算法与其他基线方法相比，在5%的统计显著水平上表现了更优越的性能，即根据统计分析，本文提出的DBSC算法，其聚类准确性优于其他基准方法.

表4 在所有数据集上的成对检验结果

Table 4 The pairwise test results on all datasets

评价指标		HAC	Affinity	DPC	GRINCH	HK⁃means	Munec	RSC	SCC	streaKHC
RI	t⁃value	5.0204	3.0212	6.8472	11.0110	2.7193	3.8603	3.1274	7.6177	2.5354
RI	p⁃value	0.0004	0.0116	<0.0001	<0.0001	0.0200	0.0027	0.0096	<0.0001	0.0277
ARI	t⁃value	4.5508	3.2136	4.3996	4.1685	3.7369	3.9972	3.0334	4.5698	4.1749
ARI	p⁃value	0.0008	0.0083	0.0011	0.0016	0.0033	0.0021	0.0114	0.0008	0.0016
NMI	t⁃value	5.6271	2.9437	7.3709	6.7397	6.9410	3.9242	4.0527	7.6785	6.7032
NMI	p⁃value	0.0002	0.0134	<0.0001	<0.0001	<0.0001	0.0024	0.0019	<0.0001	<0.0001

4.8　效率和可扩展性

为了更好地证明DBSC算法在执行效率上的优势，在增量人工数据集上对所有算法进行响应时间的多项式拟合，结果如表5所示.由表可见，DBSC的拟合结果为1.62，仅次于SCC（1.40）和HK⁃means（1.39）.

表5 所有算法响应时间的多项式拟合结果

Table 5 The polynomial fitting results for the response time of all algorithms

算法名称	DBSC	HAC	Affinity	DPC	GRINCH
拟合结果	1.62	2.38	2.17	2.23	3.24
算法名称	HK⁃means	Munec	RSC	SCC	streaKHC
拟合结果	1.39	3.02	1.70	1.40	2.08

图5展示了DBSC及其他九个基准算法的响应时间和内存占用情况，其结果在双对数坐标下展示.实验表明，与大多数基准算法相比，DBSC算法的时间和内存消耗较少，对比算法中只有HK⁃means的内存消耗较低.

图5

图5 DBSC的可扩展性验证

Fig.5 The scalability of DBSC validation

综上所述，DBSC的准确性优于所有基准算法，效率和可扩展性仅次于HK⁃means.

5 结论

对于层次聚类算法难以平衡时间和空间的开销问题，本文提出基于改进局部密度的可扩展层次聚类算法.通过最近邻关系构造最近邻图，从局部密度峰值的角度出发，为每个最近邻分量确定最佳代表点以构造子簇树.最终，算法迭代地构造一棵聚类树，并有效地降低了时间和空间的开销.经过大量实验证明，本文提出的算法在聚类精度上优于其他基准算法.此外，本文与其他算法相比，具有更低的时间和空间开销.

综上所述，本文提出的DBSC算法在较低的时间消耗和空间消耗下，能够高效地对数据进行聚类，同时提供可靠的聚类结果，是一种有效且高效的算法，并能够在现实应用中发挥作用.未来将致力于解决参数 $α$ 在不同最近邻分量的表征问题，进一步提升算法的聚类效果.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

宋鹏，葛洪伟，乔宇鑫.

加权最近邻分配的局部间隙密度聚类

南京大学学报(自然科学)，2022，58(5)：827-835.

Song

， Ge

H W

， Qiao

Y X

Weighted nearest neighbor distribution of local gap density clustering

Journal of Nanjing University (Natural Science)，2022，58(5)：827-835.

[2]

时照群，刘兆伟，刘惊雷.

基于相关熵和流形正则化的图像聚类

南京大学学报(自然科学)，2022，58(3)：469-482.

Shi

Z Q

， Liu

Z W

， Liu

J L

Image clustering based on correntropy and manifold regularization

Journal of Nanjing University (Natural Science)，2022，58(3)：469-482.

[3]

李苓玉，刘治平.

基于机器学习的自发性早产生物标记物发现

南京大学学报(自然科学)，2021，57(5)：767-774.

L Y

， Liu

Z P

Discovery of spontaneous preterm birth biomarkers based on machine learning

Journal of Nanjing University (Natural Science)，2021，57(5)：767-774.

[4]

Habib

， Akram

， Kahraman

Minimum spanning tree hierarchical clustering algorithm：A new Pythagorean fuzzy similarity measure for the analysis of functional brain networks

Expert Systems with Applications，2022，201：117016.

[5]

Dugan

H A

， Bartlett

S L

， Burke

S M

，et al.

Salting our freshwater lakes

Proceedings of the National Academy of Sciences，2017，114(17)：4453-4458.

[6]

Xie

W B

， Liu

， Chen

，et al.

Boosting cluster tree with reciprocal nearest neighbors scoring

Engineering Applications of Artificial Intelligence，2024，127：107438.

[7]

Xie

W B

， Lee

Y L

， Wang

，et al.

Hierarchical clustering supported by reciprocal nearest neighbors

Information Sciences，2020，527：279-292.

[本文引用: 5]

[8]

Kobren

， Monath

， Krishnamurthy

，et al.

A hierarchical algorithm for extreme clustering

∥Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Halifax，Canada：Association for Computing Machinery，2017：255-264.

[本文引用: 4]

[9]

Ahmed

， Seraj

， Islam

S M S

The k⁃means algorithm：A comprehensive survey and performance evaluation

Electronics，2020，9(8)：1295.

[10]

Bentley

J L

Multidimensional binary search trees used for associative searching

Communications of the ACM，1975，18(9)：509-517.

[11]

Monath

， Dubey

K A

， Guruganesh

，et al.

Scalable hierarchical agglomerative clustering

∥Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. Singapore，Singapore：Association for Computing Machinery，2021：1245-1255.

[12]

Monath

， Zaheer

， McCallum

Online level⁃wise hierarchical clustering

∥Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Long Beach，CA，USA：Association for Computing Machinery，2023：1733-1745.

[13]

Ros

， Guillaume

Munec：A mutual neighbor⁃based clustering algorithm

Information Sciences，2019，486：148-170.

[14]

Huang

Q R

， Gao

， Akhavan

An ensemble hierarchical clustering algorithm based on merits at cluster and partition levels

Pattern Recognition，2023，136：109255.

[15]

Ding

Z L

， Cao

， Chen

，et al.

Large⁃scale multimodal multiobjective evolutionary optimization based on hybrid hierarchical clustering

Knowledge⁃Based Systems，2023，266：110398.

[16]

Ester

， Kriegel

H P

， Sander

，et al.

A density⁃based algorithm for discovering clusters in large spatial databases with noise

∥Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland，OR，USA：AAAI Press，1996：226-231.

[17]

Rodriguez

， Laio

Clustering by fast search and find of density peaks

Science，2014，344(6191)：1492-1496.

[18]

Mehmood

， Zhang

G Z

， Bie

R F

，et al.

Clustering by fast search and find of density peaks via heat diffusion

Neurocomputing，2016，208：210-217.

[19]

， Ding

S F

， Du

M J

，et al.

DPCG：An efficient density peaks clustering algorithm based on grid

International Journal of Machine Learning and Cybernetics，2018，9(5)：743-754.

[20]

Wang

Y Z

， Wang

， Zhou

，et al.

VDPC：Variational density peak clustering algorithm

Information Sciences，2023，621：627-651.

[21]

Ding

S F

， Du

， Xu

，et al.

An improved density peaks clustering algorithm based on natural neighbor with a merging strategy

Information Sciences，2023，624：252-276.

[22]

Ding

S F

， Li

， Xu

，et al.

A sampling⁃based density peaks clustering algorithm for large⁃scale data

Pattern Recognition，2023，136：109238.

[23]

Xie

J Y

， Liu

X L

， Wang

M Z

SFKNN⁃DPC：Standard deviation weighted distance based density peak clustering algorithm

Information Sciences，2024，653：119788.

[24]

， Ding

S F

， Xu

，et al.

Fast density peaks clustering algorithm based on improved mutual K⁃nearest⁃neighbor and sub⁃cluster merging

Information Sciences，2023，647：119470.

[25]

Xie

W B

， Liu

， Das

，et al.

Scalable clustering by aggregating representatives in hierarchical groups

Pattern Recognition，2023，136：109230.

[26]

Liaw

Y C

， Leou

M L

， Wu

C M

Fast exact k nearest neighbors search using an orthogonal search tree

Pattern Recognition，2010，43(6)：2351-2358.

[27]

Geusebroek

J M

， Burghouts

G J

， Smeulders

A W M

The Amsterdam library of object images

International Journal of Computer Vision，2005，61(1)：103-112.

[28]

Russakovsky

， Deng

， Su

，et al.

ImageNet large scale visual recognition challenge

International Journal of Computer Vision，2015，115(3)：211-252.

[29]

Rand

W M

Objective criteria for the evaluation of clustering methods

Journal of the American Statistical Association，1971，66(336)：846-850.

[30]

Hubert

， Arabie

Comparing partitions

Journal of Classification，1985，2(1)：193-218.

[31]

Yang

， Shen

F M

， Huang

，et al.

Discrete nonnegative spectral clustering

IEEE Transactions on Knowledge and Data Engineering，2017，29(9)：1834-1845.

[32]

Bouguettaya

， Yu

， Liu

X M

，et al.

Efficient agglomerative hierarchical clustering

Expert Systems with Applications，2015，42(5)：2785-2797.

[33]

Bateni

M H

， Behnezhad

， Derakhshan

，et al.

Affinity clustering：Hierarchical clustering at scale

∥Proceedings of the 31st Conference on Neural Information Processing Systems. Long Beach，CA，USA：Curran Associates Inc.，2017：6867-6877.

[34]

Monath

， Kobren

， Krishnamurthy

，et al.

Scalable hierarchical clustering with tree grafting

∥Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Anchorage，AK，USA：Association for Computing Machinery，2019：1438-1448.

[35]

Han

， Zhu

， Ting

K M

，et al.

Streaming hierarchical clustering based on point⁃set kernel

∥Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Washington，DC，USA：Association for Computing Machinery，2022：525-533.