基于强化学习的聚类算法

Clustering Algorithm Based on Reinforcement Learning

摘要: 创新性地将强化学习技术引入聚类算法中，旨在解决传统聚类方法面临的两大难题：初始聚类中心选择的不确定性以及计算过程中欧氏距离划分样本导致的高时间复杂度。通过引入强化学习的奖惩机制，设计了一种基于“代理”Agent的行为选择策略，有效替代了传统的欧氏距离计算过程，从而消除了初始聚类中心对算法稳定性的潜在影响，并大幅提升了算法的收敛速度。提出了一种全新的基于强化学习的聚类算法，不仅在数学上严谨证明了其收敛性，而且在实际应用中展现了显著优势。通过数值实验验证，该算法在聚类准确率上较传统方法有明显提升，同时在算法性能上也表现出更加优越的特点，这一研究对于提升数据处理效率和准确性具有重要意义。

Abstract: Innovatively introducing reinforcement learning techniques into clustering algorithms, this research aims to address two major challenges faced by traditional clustering methods: the uncertainty in selecting initial cluster centers and the high time complexity caused by the Euclidean distance metric in sample classification. By introducing the reward-punishment mechanism of reinforcement learning, this paper designs a behavior selection strategy based on an “agent,” effectively replacing the traditional Euclidean distance calculation process. This approach eliminates the potential impact of initial cluster centers on the stability of the algorithm and significantly improves the convergence speed. A novel clustering algorithm based on reinforcement learning is proposed, which not only rigorously proves its convergence mathematically but also demonstrates significant advantages in practical applications. Through numerical experiments, it is verified that the algorithm achieves significantly higher clustering accuracy compared to traditional methods, while also exhibiting superior algorithm performance. This research is of great significance for improving the efficiency and accuracy of data processing.

1. 引言

随着科技的飞速发展，数学在多个领域的重要性日益凸显。尤其在当代社会，利用数学原理解决现实挑战至关重要。互联网产业虽带来便利[1]，但也产生海量冗余数据[2]。因此，数据挖掘技术成为处理大数据的关键工具[3]，通过算法从无序数据中提取有价值信息[4]。借助AI和机器学习，数据挖掘能深入处理、分析大数据，帮助发现数据模式、降低风险、制定策略[5]。其中，聚类分析因其高效和线性计算复杂度备受青睐[6]。数学在聚类分析等领域发挥关键作用，当前研究强调如何有效利用数据挖掘的见解。

2. 预备知识及问题分析

聚类分析是数据挖掘的核心，它将无标签数据分类，是无监督学习的重要部分[6]。现有聚类算法虽技术多样但原理相通[7]，旨在最大化类别间差异并最小化内部相似性。其中，基于划分的算法如K-means，虽受欢迎但受限于初始中心和欧氏距离计算。

强化学习通过智能体与环境交互优化策略，为聚类算法提供新思路[8]。它指导智能体选择聚类中心，减少对初始值的依赖，并引入更复杂的相似度度量提升准确性。提出基于强化学习的聚类算法RLC，旨在解决传统算法的初始中心选择和计算复杂度问题。RLC通过奖惩机制智能选择聚类中心，优化样本空间划分，并采用高效相似度度量降低计算复杂度。这一创新方法不仅提升了性能，还为处理复杂数据集提供新方案。RLC通过构建Q表存储知识，避免随机选择初始中心的问题。然而，该算法研究尚有限，其收敛性、准确率和性能需进一步验证，以推动聚类算法的研究与应用。

在深入RLC算法之前，首先梳理了相关的预备知识，包括极限的相关性质、Q-Learning算法以及学习自动机算法，为后文研究奠定理论基础。

引理1(极限的相关性质)极限具有以下如式(1)所示的性质：

$\underset{n\to \infty }{\lim }\frac{1}{2^n}=0$ (1)

Q-Learning算法是一种经典的强化学习技术，用于解决马尔可夫决策过程中的最优决策问题。该算法通过构建Q表来估计每个状态——动作对Q (s_i, a_i)的长期期望收益，智能体“Agent”根据这些Q值在未知环境中进行决策。Q-Learning算法无需事先了解环境模型，而是通过不断试错和从经验中学习来优化行为策略。其独特的离策略特性使得智能体能够灵活选择动作，既追求当前的最大收益，又保留探索新策略的可能性。因此，Q-Learning算法被广泛应用，如机器人导航、游戏策略优化以及自动驾驶等领域。Q-Learning算法通过不断学习和迭代，最终构建出一个二维的Q表(Q-table)，其中横轴代表不同的状态(state, s)，纵轴代表可执行的动作(action, a)。这个Q表的核心在于存储了智能体在不同状态下采取不同动作所能获得的期望奖励值，也被称为Q值。通过这些信息，智能体可以高效地在未知环境中进行决策，从而最大化长期累积的奖励。Q-Learning是一种针对单智能体的强化学习算法，其核心在于通过不断试错学习来优化决策过程。表1所描述了在一个特定环境中，智能体在不同状态下选择不同动作所获得的奖励情况，为智能体后续的决策提供了关键依据。其中s_n代表Agent所处的状态，a_k代表Agent可选择的行为，q (s_n, a_k)代表Agent在状态s_n下选择行为a_k后所得到的反馈奖励期望值。

Table 1. Q represents the meaning table

表1. Q表示意表

S	a1	a2	...	ak
s1	q (s1, a1)	q (s1, a2)	...	q (s1, ak)
s2	q (s2, a1)	q (s2, a2)	...	q (s2, ak)
...	...	...	...	...
sn	q (sn, a1)	q (sn, a2)	...	q (sn, ak)

学习自动机算法，亦称为多智能体算法[9]，是强化学习的重要分支，在概率空间中通过与环境交互，根据强化信号调整动作选择概率，以逼近最优决策。算法分为有限(FALA)和无限(CALA)动作学习自动机，分别适用于组合和连续数值优化问题。FALA以其试错学习方式，在处理非线性及不确定性优化问题时表现出色，为复杂环境下的决策优化提供高效解决方案。重点介绍FALA算法，其核心特性由四元组<α, β, R, U>描述，其中α为行为动作，β为反馈信号，R为累积概率集合，满足概率和为1的约束条件，如下公式(2)。

${\displaystyle \sum _{i=1}^K{r}_i=1}$ (2)

鉴于离散行为学习自动机(FALA)与聚类算法在动作选择和相似度计算上的契合度，提出利用FALA优化聚类算法，以提升聚类效果和效率。

3. RLC算法

当前，强化学习与聚类算法的结合是优化聚类性能的研究热点。已有研究如王玉荣等[10]利用学习自动机算法优化模糊FCM聚类的参数，而Yuanfeng Yang等[11]则通过引入强化学习的奖惩机制优化隶属度，提出新的对抗学习聚类算法。提出一种基于强化学习的聚类算法(RLC)，结合离散行为学习自动机(FALA)的多智能体协同优化思想与K-means算法，以提升聚类效果和算法性能。RLC算法通过引入强化学习思想，使智能体能自适应地调整聚类行为，优化聚类过程。实验表明，RLC算法在模型性能和聚类结果上均优于主流聚类算法，为聚类分析提供了新工具。该算法将聚类任务形式化为马尔科夫决策过程，利用累积奖励指导聚类，并通过引入ε-贪婪策略平衡探索和利用，通过监测平均类内距离变化发送强化信号，优化聚类效果。首先给出RLC算法的流程图，如下表2所示。

Table 2. RLC algorithm process steps

表2. RLC 算法流程步骤

算法：RLC算法

输入：数据集Data_ori、聚类数K、最大迭代次数数Max_iter、平均类内距离变化阈值Stop；输出：样本所在类簇的标签Label。 步骤1：前两次迭代，Agent通过K-means++算法选择行为输出，同时计算各类别的平均类内距离； 步骤2：根据前两次迭代的结果，比较平均类内距离的变化，并向Agent发送强化信号，更新Q表； 步骤3：从第三次迭代开始Agent根据ε-贪婪策略选择行为输出，计算类别的平均类内距离； 步骤4：比较平均类内距离的变化，向Agent发送强化信号，更新Q表； 步骤5：算法依次迭代下去，直至平均类内距离变化小于阈值Stop或迭代数达到Max_iter，停止运行； 步骤6：输出所有样本的类标签。

RLC算法在初始化阶段需设定初值和参数。在前两次迭代中，由于Q表尚未更新，所有Agent均采用K-means++策略选择行为，并计算各类别平均类内距离存入向量。自第三次迭代起，Agent依据ε-贪婪策略选择动作并输出，随后重新计算并保存平均类内距离。算法比较当前与上一次迭代的平均类内距离，据此发出强化信号。Agent接收信号后更新Q表，此过程反复进行，直至平均类内距离变化低于阈值Stop或达到最大迭代次数Max_iter。各Agent选择累积奖励最大的行为，将选择相同行为的Agent对应样本归入同一类别并赋予类标签，输出结果。

3.1. 贪婪系数的选取

RLC算法通过迭代收敛，使Q表中每个行为的累积奖励值稳定，即每行仅有一个行为的累积奖励值为1。算法执行中，引入ε-贪婪策略，Agent以ε的概率选择最大累积奖励行为实现“利用”，以1 − ε的概率随机选择实现“探索”。根据环境反馈调整累积奖励值，优化聚类效果。实验利用Matlab对iris数据集进行聚类，比较不同贪婪系数(0.5、0.6、0.7、0.8、0.9)下的准确率，发现贪婪系数设为0.9时，算法准确率最高。因此，设定ε-贪婪策略的ε为0.9，显著提升收敛性能，实现高效聚类分析。

3.2. 平均类内距离的构建

在构建强化信号时，该信号是Agent在选择行为后从环境获得的反馈，分为奖励和惩罚信号。传统聚类算法依赖聚类中心变化判断迭代停止，但聚类中心不能全面反映类别内部样本的紧密程度和分布。因此，RLC算法采用平均类内距离作为强化信号的关键指标，以反映类别内样本的紧密程度。平均类内距离定义为同类别样本到聚类中心距离的均值，量化类别的紧凑程度，与样本紧凑程度呈反比。通过计算平均类内距离，可精确度量类别的紧凑性，公式如下(3)所示。

$Adis\left(c_j\right)=\frac{1}{\left|c_j\right|}{\displaystyle \sum _{i=1}^{\left|c_j\right|}\sqrt{{\displaystyle \sum _{m=1}^M{\left(x_{im}-c_{jm}\right)}^2}}}$ (3)

$\text{Adis}\left(c_j\right)$ 代表第j个类别的平均类内距离，其中1 ≤ j ≤ K，$\left|c_j\right|$ 代表第j个类别中样本的总数，M代表输入的样本数据的维度，$x_{im}$ 代表样本i的第m个属性值，$c_{jm}$ 代表聚类中心j的第m个属性。

平均类内距离作为量化类别紧密程度的指标，既融合了聚类中心信息，又显著降低了计算复杂度，尤其在算法迭代中表现突出。因此，RLC算法选用平均类内距离作为强化信号的关键指标，以准确反映聚类质量。

3.3. Q表的建立

由表2可知，在RLC算法中，N个Agent与数据集中的N个样本形成一一映射关系。同时输入的聚类数K与离散行为集中的行为一一对应。设r_ij为第i个Agent执行第j个行为的累积奖励值，其中各行为的累积奖励值之和满足归一化条件。在一次迭代过程中，Agent会根据环境反馈更新其所有行为的累积奖励值。最终，算法将使得某一行为的累积奖励值收敛至1，而其余行为的累积奖励值收敛至0。

在RLC算法的运行过程中，各Agent在贪婪策略的指导下，从Q表的离散动作集中选择行为。初始化时，所有Agent选择各行为的Q值均设为1/K，其中K为离散动作总数。首次迭代时，Agent通过K-means++算法选择行为，并将选择相同行为的Agent划分至同一类别，赋予相应的类标签。此时，由于算法尚未计算平均类内距离，故环境无法给出强化信号。自第二次迭代起，Agent再次通过K-means++算法选择行为并完成类别划分后，计算各类别的平均类内距离$\text{Adist}\left(c_j\right)$ ，1 ≤ j ≤ K，其中t为迭代次数。此时，算法得以根据平均类内距离的变化给出强化信号，Agent据此更新Q表。在算法运行过程中，环境提供的反馈信号中，“1”代表奖励信号，而“0”代表惩罚信号。通过这些信号，Agent不断优化其选择行为，直至算法收敛。当RLC算法推进至第三次迭代时，Q表已基于前两次迭代的反馈信号进行过一次更新，其内容已不再是初始的均匀分布1/K。因此，Agent现在能够依据ε-贪婪策略在“利用”已知信息和“探索”新可能行为之间取得平衡，从而更有效地选择行为。总体而言，在RLC算法的运行过程中，各个Agent的“探索”与“利用”行为相互交织、互为制约，并持续更新Q表以趋于收敛。

若Agent_i接收到的强化信号为奖励信号，则增大Q表中该Agent行为k的累积奖励值，同时减小其余行为的累积奖励值，若Agent_i接收到的强化信号为惩罚信号，则减小Q表中该Agent行为k的累积奖励值，增大其余行为的累积奖励值，Q表的累积奖励，的更新公式如下式(4)和式(5)所示。

$r_k\left(iter\right)=\{\begin{array}{l}{r}_k\left(iter-1\right)+0.5\left(1-r_k\left(iter-1\right)\right),k=i\\ 0.5r_k\left(iter-1\right),k\ne i\end{array}$ (4)

$r_k\left(iter\right)=\{\begin{array}{l}0.5r_k\left(iter-1\right),k\text{ = }i\\ r_k\left(iter-1\right)+\frac{1}{K-1}\left(0.5\left(r_k\left(iter-1\right)\right)\right),k\ne i\end{array}$ (5)

式(4)给出Agent_i在接收到环境所反馈的奖励信号后，Q表中该Agent的各行为累积奖励值的更新公式，式(5)给出Agent_i在接收到环境所反馈的惩罚信号后，Q表中该Agent的各行为累积奖励值的更新公式。$r_k\left(iter\right)$ 和$r_k\left(iter-1\right)$ 分别代表第iter次和第iter − 1次迭代结束后，Q表中Agent_i行为k的累积奖励值，其中1 ≤ i，k ≤ K。

3.4. 收敛性证明

定理1：如上表2所示的RLC算法中Q表经过多次迭代之后，最终每个Agent的行为将会形成以下的形式：

1) 其中一个行为的累积奖励值收敛至1；

2) 其余行为的累积奖励值则收敛至0。

证明由式(2)所示的${\displaystyle {\sum }_{i=1}^K{r}_i=1}$ ，1 ≤ i ≤ N的约束条件，其中K代表有限行为动作集合中Agent选择的动作数量，可知若2)成立，则1)一定也成立。则证明2)。以Agent₁为例，其余Agent_i同理得证。

Q表中累积奖励的更新公式(4)与累积惩罚更新公式(5)可知当奖励信号$k\ne i$ 与惩罚信号$k=i$ 时，奖励值为上一次迭代所产生的奖励值的1/2，则由引理1，

$\underset{N\to \infty }{\lim }\frac{c}{2^N}=c\underset{N\to \infty }{\lim }\frac{1}{2^N}=0$

其中c为任一常数，则2)得证。

证明成立。

4. 试验设计与分析

本节对比了K-means (KM)、K-means++ (KM++)、FCM以及提出的RLC算法的性能，使用准确率作为主要评价指标。实验基于iris、KEEL、enterprise等公共数据库的10个带标签数据集，通过量化各算法在准确率上的表现，评估了它们在聚类效果上的优劣。实验数据集信息及Q表初始化详见电子附录，为后续性能分析提供支持。

Table 3. Accuracy results of cluster algorithm experiment

表3. 聚类算法实验准确率结果表

数据集	编号	K-means准确率	K-means++准确率	FCM准确率	RLC准确率
0enterprise_nk	D1	0.8663	0.9151	0.9215	0.9321
1iris	D2	0.9017	0.9692	0.9212	0.9513
2zsweather1	D3	0.8726	0.9026	0.9326	0.9152
3jhweather3	D4	0.9052	0.8827	0.8923	0.9652
4sensor0	D5	0.7923	0.8724	0.8826	0.8923
5vegetable_vir	D6	0.7723	0.7326	0.7523	0.7982
6provision012	D7	0.7513	0.7966	0.8152	0.8235
7degree	D8	0.6623	0.6525	0.6895	0.6826
8bid_set	D9	0.6922	0.7523	0.6925	0.8236
9med_refer	D10	0.6529	0.6328	0.6513	0.6613

Table 4. Experimental dataset and Q-table initial values table

表4. 实验数据集及Q表初始化值表

数据集	编号	样本数量	维度	类别数(行为数)	Q表初值
0enterprise_nk	D1	53	9	3	1/3
1iris	D2	150	4	3	1/3
2zsweather1	D3	180	6	19	1/19
3jhweather3	D4	198	6	18	1/18
4sensor0	D5	223	4	2	1/2
5vegetable_vir	D6	233	2	4	1/4
6provision012	D7	268	2	5	1/5
7degree	D8	295	5	3	1/3
8bid_set	D9	369	3	5	1/5
9med_refer	D10	658	3448	11	1/11

经过全面测试10个数据集，本实验统计了各算法运行100次的平均准确率，并将准确率扩大三倍以百分比形式展示。表3详细对比了RLC算法与K-means、K-means++及FCM在准确率方面的数据，直观展现了各算法在聚类性能上的优劣，表4为实验数据集及Q表初始化值表。实验结果有力支持了对各算法性能的深入分析，显示RLC算法在7个数据集中准确率更高，验证了其可行性。

5. 总结

在起始部分，首先探讨聚类算法面临核心挑战，旨在寻找更为精准和高效的解决方案。第二节中，聚焦于强化学习的基本原理，为基于强化学习的聚类算法构建奠定基石。还介绍Q-Learning算法和学习自动机算法，特别是以离散行为集为核心的FALA算法，这些理论知识的积累为后续算法的提出奠定了坚实的基础。

在第三节中，详细阐述所提出的基于强化学习的聚类算法(RLC)，并对其收敛性进行了严格的数学证明。构建二维Q表，通过其横纵坐标对应离散行为集和样本空间中的代理Agent，实现了策略的选择与更新。利用ε-贪婪策略，Agent在Q表中平衡对已知知识的利用和对环境的探索。采用计算复杂度较低的平均类内距离作为强化信号，该信号综合考虑了聚类中心的关键因素。环境根据此信号向每个Agent提供奖励或惩罚，进而更新Q表。通过iris鸢尾花数据集的初步实验，确定了贪婪系数ε为0.9时算法表现最佳。最后，经过严格的收敛性证明，验证RLC算法的可行性和有效性。

在第四节中，设计了实验方案，将提出的RLC算法与K-means算法、K-means++算法和FCM算法进行对比分析。选用十个公开的、带有标签的数据集，以确保实验结果的全面性和公正性。在实验中，每种算法都运行了100次，每次运行都将聚类结果与真实标签进行对比，计算出准确率。最终，取这100次运行的平均准确率作为各聚类算法的性能指标。通过对比分析，得出结论：在大量的实验运行中，RLC算法展现出了更高的准确率，从而充分证明了其在聚类任务中的卓越性能。

NOTES

^*通讯作者。