持续同调[1]是拓扑数据分析领域中的一项重要技术，主要用于提取数据中的拓扑结构信息．持续同调技术为研究者提供了一个新的思路，它无须对数据进行降维，就能准确描述出原数据在高维空间中的拓扑结构和数据中存在的集群和环结构，从而辅助研究者在避免损失过多信息的前提下完成相关数据分析．高维数据往往是稀疏的，主成分分析法(PCA)等经典降维方法由于其过程会损失一定的信息，当面对高维数据时无法获得良好的降维效果．根据持续同调的特点，若能将其应用到机器学习或是大数据分析算法中是很有意义的．近年来也有一些相关的研究，如文献[2-5]尝试将持续同调与机器学习或一些大数据方法相结合，说明了持续同调能够与机器学习技术相结合，并从拓扑的角度提供帮助．但持续同调与聚类的结合目前尚无相关的工作，仍有许多亟待挖掘的研究方向．持续同调的本质是对样本中拓扑特征的出生和死亡进行持续性地追踪，并将这些拓扑特征的生命周期以二维点的形式输出成一个图，即持续生死图[6]，从而发现拓扑空间中持续存在的拓扑特征．目前使用由持续同调提取出的信息主要有两种形式：一种是在持续生死图上定义距离，通过这样的方式来体现不同种类的数据样本的差异性，如瓶颈距离[1]和瓦瑟斯坦距离[7]；另一种是将持续生死图转化为一组向量，常用的有持续峰图[8]、持续图像[9]和Bubenik等[10]利用持续峰图作为分类算法的前置环节，并通过实验说明了将持续生死图转换为向量后仍能从拓扑的角度区分不同的样本．本研究主要探索持续同调与聚类算法结合的可行性，实验结果表明：所提出的聚类算法的性能优于若干个经典的聚类算法，同时受随机状态的影响相对较小．1 单纯复形和持续同调1.1　单纯复形单纯复形是拓扑数据分析中一个非常重要的概念，是一种由单纯形复合而成的几何结构．单纯形可以理解为三角形在不同维度下的泛化．简单来说，一个n维单纯形是一个包含了n+1个点的凸多面体，具体如定义1所示．定义1[1] 假设RN中存在一个实数域向量集a0,a1,⋯,an，使得{a1-a0,a2-a0,⋯,an-a0}线性无关，则点集E={s=t0a0+t1a1+…+tnan|∑i=0nti=1,ti≥0}就是一个n维单纯形，称ti为单纯形E的点s关于a0,a1,⋯,an的重心坐标．在持续同调过程中，选定距离参数ε，若数据之间的距离满足ε的界定条件则可形成边的连接，从而构成单纯形．以二维欧氏空间中的点云数据为例，单个节点为零维单纯形；若两点之间的距离不超过ε的取值，则该两点连接形成边，边在持续同调中的定义即为一维单纯形；对于二维空间中的3个点云数据，若任意两点之间的距离均不超过ε，则任意两点连接形成边，构成一个封闭的三角形，即二维单纯形．单纯复形简而言之就是由不同的单纯形组合在一起构成的．在RN空间中，单纯复形K满足定义2．定义2[1] 单纯复形K是当前空间下，一组单纯形的组合，它满足以下条件．a．K中任意单纯形的任意一个面仍旧属于K．b．K中任意两个单纯形的交集是空集或二者共享的其中一个面．单纯复形结构有很多种，不同的单纯复形结构具有不同的特点．其中维托里斯-里普斯复形(简称Rips复形)[11]是基于图论而构造的单纯复形．由于构造简洁，Rips复形面对高维度数据也能相对快速地构造出单纯复形，因此应用最为广泛．1.2　持续同调在持续同调中，一般会采用滤流嵌套复形来计算拓扑特征的生命周期．滤流嵌套复形是针对一组点云数据X，按照一组具有包含关系的递增距离参数ε1≤ε2≤…≤εk构造生成一系列具有包含关系的单纯复形，当距离参数不断增大时，原有的单纯复形不会受到影响，而是会包含到更大距离参数所构成的新的单纯复形中．假设在距离参数下εk生成的单纯复形为K(X,εk)，由此可以得到生成的单纯复形序列K(X,ε1)⊂K(X,ε2)⊂…⊂K(X,εk)．可以发现在滤流嵌套复形构建过程中，距离参数不断增大，会伴随着拓扑特征的“出生”和“死亡”，即某些点会消失进而连接成边，对应的就是2个零维单纯形“死亡”而1个一维单纯形“出生”，边的特征也可能消失，形成更高维的拓扑形状．因此，一个拓扑特征a也可以定义其生命周期，假设a最开始出现在K(X,εi)中，但是在K(X,εj)中，则称a在εi“出生”，在εj“死亡”．那么这个拓扑特征a的生命周期，或其持续时间为εj-εi．同时可以记该拓扑特征的“出生时间”为εi，“死亡时间”为εj．在持续同调过程中，持续时间较长的特征通常具有特别的实际意义，因此须特别关注，而持续时间较短的拓扑特征通常被视为噪声，须忽略．这个过程无须改变原有数据的结构就能够提取出数据的拓扑特征的信息，因此说持续同调可以在不降维的前提下提取数据的拓扑特征，并以拓扑特征的出生和死亡描述其生命周期．以两组具有明显拓扑特征的三维数据样本为例，分别对其进行二维持续同调的计算，使用Rips复形作为构造工具，并输出持续生死图．一组是球面数据样本，另一组是环面数据样本，每组都包含了400个三维点，三维数据样本示例见图1．10.13245/j.hust.240202.F001图1三维数据样本示例两组样本的持续生死图如图2所示，图中：Hi为i (i=0，1，2)维拓扑特征；B为“出生时间”；D为“死亡时间”；每一个点代表一个拓扑特征的生命周期．两种拓扑结构明显不同的数据样本提取出的持续同调信息是不一样的．环面数据集在持续同调过程中会产生很多生命周期很短的二维拓扑特征，对应图中的H2，同时有一些生命周期较长的一维拓扑特征．而球面的二维拓扑特征中生命周期比较长的只有一个，且一维拓扑特征分布比较紧密，说明球面样本内部隐藏着二维拓扑特征．10.13245/j.hust.240202.F002图2样本的持续生死图可以发现：不同种类样本的持续生死图有差别，并且能够反映出样本的拓扑结构，因此通过持续同调提取的信息能够体现不同数据样本的拓扑特征，即通过持续同调提取出的拓扑信息仍具有可解释性．并且把这些信息进行可视化后，能够直观地观察出数据样本的拓扑特征区别，因此将持续同调用于区分两种不同的数据具有一定可行性．2 基于持续同调的聚类算法基于持续同调的聚类(PHBC)算法主要包括三个步骤：a．对数据中的样本计算持续同调信息得到持续生死图；b．将获得的持续生死图转换为持续图像向量；c．利用K-Means算法[12]对获得的持续图像向量进行聚类．2.1　持续图像生成算法持续图像是由持续生死图转换而来的向量形式．假设B为持续生死图中的点构成的点集，T:R2→R2为一线性映射，满足T(x,y)=(x,y-x)．T(B)为由B变换而来的点集，即每个点(x,y)∈B对应一个点(x,y-x)∈T(B)．假设Φu:R2→R为二维可微概率分布，其均值为u=(ux,uy)，一般而言取该分布为高斯分布，即Φu=gu，gu(x,y)=12πσexp{-12σ2[(x-ux)2+(y-uy)2]}.同时，还须确定一个非负的加权函数f:R2→R，并在水平横轴上为0，最简单的是选择一个只和垂直坐标轴相关的加权函数，这是为了能够使生命周期长的点有更高的权重，在图像中更为明显．一般选择二次幂函数，即w(t)=t2．这样就可以将持续生死图转化为一个平面上的标量函数．首先须定义持续性表面ρB(z):R2→R为一个函数，可定义为ρB(z)=∑u∈T(B)f(u)Φu(z)，然后通过离散相关子域对离散过程中每个区域的ρB(z)进行积分，将曲面ρB(z)简化为有限维向量．可以看出加权函数非常重要，直接影响从持续生死图到持续图像的转换效果．特别地，须要设置一个平面并固定一个带有n个像素的网格，并将该区域上的ρB(z)积分分配给每个像素，因此可以把持续图像记为像素I(ρB)p的集合，其中I(ρB)p=∬ρBdxdy．为解决持续图像引入很多拓扑噪声这一不足，本研究使用加权函数作为分段函数，对其进行改进并验证其有效性．一般而言，加权函数往往会选择将持续时间进行幂运算加权，但是这样的加权方式没有过滤生命周期较短的拓扑特征，因此这些噪声也会显示在生成的持续图像中，对后续的操作有一定干扰．据此本研究提出利用分段函数进行线性加权映射，所提出使用的加权函数为w(t)=0    (ta);(t-a)/(b-a)    (a≤t≤b);1    (tb),这种加权函数能保证生命周期更长的拓扑特征有更大的权值．同时将生命周期较短的拓扑特征的权值设置为0，从而避免对生成的持续图像有过多的干扰．为说明分段函数加权的有效性，构造了一组同心圆加上噪声的数据，共400个点，其中有200个点为噪声点．对模拟数据计算不同下界参数下的持续图像，如图3所示，图中P为持续时间．10.13245/j.hust.240202.F003图3不同下界参数生成的持续图像可以看出：当参数增大时，一些生命周期较短的拓扑噪声从图中被过滤掉了．尽管增加下界参数能够屏蔽掉一些生命周期相对较短的拓扑特征，但是若一味增加下界参数，则有可能会错误地过滤掉一些重要的拓扑特征信息．因此，使用持续图像时应根据数据集的实际情况选择合适的下界参数．在生成持续图像过程中加入一个参数用于控制像素块的大小，进而控制输出向量的大小是有必要的．通过控制该参数的大小，进而控制输出持续图像的尺寸和像素．因此，本研究提出在生成持续图像的过程中加入像素参数p，它表示生成持续图像时单个像素的大小，单个像素块大小为p2．针对模拟数据，变换不同的像素参数生成对应的持续图像，当p=1.0时的持续图像为初始状态的持续图像，具体如图4所示．10.13245/j.hust.240202.F004图4不同像素参数生成的持续图像直观来看，像素参数越小生成的持续图像分辨率越高，当把持续图像输出为向量时，向量的维度也越大．这是因为向量的维度就是持续图像中像素块的个数，当网格大小一定时，单个像素块越小填满网格需要的像素块越多．2.2　算法描述提出改进的持续图像生成算法(MPIGA)，改造原有的持续图像生成算法，使得持续图像能够过滤一些生命周期较短的拓扑特征，同时加入了像素参数p，上下界参数a和b控制生成的持续图像尺寸和输出的向量维度．具体算法描述如下：对于由m个n维数据样本构成的点云数据集X={x1,x2,⋯,xm}，首先，分别计算每一个样本的q维持续同调信息，由此获得m个持续同调点集，每个点集的点数不一样但都是二维的点；然后，记录整个数据集中“出生时间”最小和最大值(Bmin和Bmax)及生命周期最小和最大值(Pmin和Pmax)，目的是为了选取一个统一的持续图像尺寸，设L为持续图像的长，W为持续图像的宽，有：L=Bmax-Bmin；W=Pmax-Pmin，最后，使用持续图像生成算法，根据新增的像素参数p和构建持续图像的上下界参数a和b，对每个持续同调点集用指定的加权函数计算每个点的权重值，并针对每个像素块计算二重积分作为该像素块的值，将这些像素块按序组合获得一系列点阵像素图，把这些像素图向量化后获得持续同调向量集合，再将其输出，最终获得了一组图片向量I={i1,i2,⋯,im}，其中每个向量维度为{L×W}．基于此，提出基于持续同调的聚类(PHBC)算法．PHBC算法将点云数据集X利用MPIGA转化为持续同调向量形式I．选定适合的簇划分值k，再将I作为K-Means聚类算法的输入，并获取其簇划分C={c1,c2,⋯,ck}输出作为结果．由于持续图像本质上由持续生死图进行映射并转化而得，因此很大程度上保留了持续生死图的可解释性，同时也能体现其拓扑不变性．由于拓扑不变性的存在，持续图像具有很强的结构性，这会导致PHBC算法具有较好的稳定性，即当随机参数改变时，PHBC算法的输出结果改变幅度很小．同时通过对计算复杂度的分析可以发现：由于增加了对数据集的持续同调过程，PHBC算法的时间复杂度为O((mqLW)/p2+nkm)，其中：q为计算的高维持续同调信息；k为选择聚类簇数．3 实验结果及分析3.1　实验数据选择的公用数据集为分类数据集Cifar-10、手写数字数据集MNIST和人脸数据集ORL[13]．Cifar-10图片数据集包括10类图片，共6×104张，每一类有6×103张图片，是尺寸为32×32×3的彩色图像，在此数据集中选择聚类簇k=10．MNIST是由250个不同的人手写的数字构成的图片数据集，共有6×104个训练样本，是尺寸为28×28的灰度图片，在此数据集中选择聚类簇k=10．ORL数据集是比较经典的人脸识别数据集，其中每个人有10张照片，共40个人，即400张照片，是尺寸为112×92的灰度图像，在此数据集中选择聚类簇k=40．使用的对比算法有K-Means[12]，DBSCAN[14]，谱聚类SC[15]和CKM[16]．使用的评估指标有同质性度量、完整性度量、V-Measure、调整兰德指数(ARI)、调整互信息(AMI)和准确性得分(ACC)．对每一种算法切换不同的参数(主要包括随机数种子)运行30次，对结果进行统计．3.2　实验结果在三种公用数据集上的实验结果如表1~3所示，表中数值为对应算法在相应的数据集上运行30次后，计算指标的平均值和标准差，并分别乘以100后的值，即为平均值×100±标准差×100．10.13245/j.hust.240202.T001表1对Cifar-10数据集的聚类实验结果对比评估指标K-MeansSCDBSCANCKMPHBCp=1p=10p=40ACC10.1±2.59.8±2.38.9±3.19.6±4.313.2±2.29.4±1.58.6±1.2AMI29.6±2.639.6±3.142.3±1.822.2±3.752.6±1.438.5±2.221.5±2.7ARI23.5±2.425.8±4.123.5±4.221.9±3.226.3±3.522.4±3.619.8±3.5V-Measure31.3±1.241.2±1.346.1±4.830.5±3.553.1±2.843.5±2.740.6±2.7同质性度量51.2±1.668.4±4.482.8±20.155.8±3.081.2±5.365.3±7.764.4±6.910.13245/j.hust.240202.T002表2对MNIST数据集的聚类实验结果对比评估指标K-MeansSCDBSCANCKMPHBCp=1p=10p=40ACC9.4±3.914.7±4.69.7±2.422.5±1.813.6±1.314.2±1.710.5±1.5AMI47.8±2.056.7±1.235.8±1.558.2±2.359.2±1.763.4±1.958.2±1.4ARI35.1±2.355.4±5.229.3±9.746.1±1.442.9±3.448.8±1.141.4±2.1V-Measure48.8±1.949.9±3.752.0±2.657.3±1.154.3±1.557.3±2.251.3±1.6同质性度量48.2±1.852.8±4.447.4±32.361.4±1.755.7±2.766.4±1.548.3±1.310.13245/j.hust.240202.T003表3对ORL数据集的聚类实验结果对比评估指标K-MeansSCDBSCANCKMPHBCp=1p=10p=40ACC14.4±2.116.5±2.312.0±3.311.1±2.312.4±0.913.4±1.514.7±1.1AMI76.8±2.275.7±4.134.1±20.058.0±3.755.7±4.257.5±2.258.6±1.9ARI55.2±3.759.5±2.216.0±16.052.5±3.554.5±2.450.1±1.755.2±2.1V-Measure84.1±1.468.4±5.472.6±13.164.2±4.279.2±1.280.2±3.182.3±1.4同质性度量82.7±1.574.9±2.781.4±26.180.6±5.781.4±2.581.7±2.283.3±1.7对于Cifar-10数据集，PHBC在参数设置p=1时，在ACC，AMI，ARI和V-Measure指标上的平均值均最高，在ACC和AMI指标上的标准差最低．其他参数设置下的PHBC算法综合各项指标来看依旧是很有竞争力的．同时，由于每张图片都是在一定场景下拍摄的，因此K-Means，SC及CKM算法表现不佳，而在一定程度上能克服噪声环境的DBSCAN和PHBC算法表现更好．对于MNIST数据集，几种算法的差距不大，但是PHBC在p=10时，在AMI，V-Measure及同质性度量3项指标上的表现依旧是最好的，并且保持相对较低的标准差．PHBC算法在p=10时，ACC指标的标准差为0.017，其他算法中CKM算法的标准差最低，为0.018，标准差最低的是PHBC (p=1)算法，为0.013．这是由于MNIST数据集中每个样本都存在相对明显的结构特征．因此，PHBC算法能够在MNIST上有相对更好的表现，但是依旧存在一定的局限性．同时由于MNIST中样本不存在噪声，因此K-Means算法的表现与DBSCAN或SC算法相比差距并不大．在ORL数据集上，PHBC算法的表现相对而言要弱一些，但是各项指标仍旧很稳定，并且与最好的效果相比差距并不大．PHBC算法在p=40时的V-Measure指标的标准差为0.823，在同质性度量指标上的效果为0.833，是总体上最好的．PHBC算法在p=10时的ACC指标上的标准差为0.009，对比其他算法，该指标最低的为SC算法(0.023)．这是由于人脸的特征是相似的，因此很难提取出差异化的拓扑特征，也就导致了PHBC算法的效果并不会有大幅度的提升．同时由于CKM算法将图像信息进行了压缩，导致损失了部分信息，因此效果不理想．根据以上实验结果可知：与其他对比算法相比，PHBC算法在三种公用数据集上都取得了有竞争力的结果，并且效果更稳定，受随机状态的影响很小，这是由于持续同调生成的向量很好地保持了数据本身的拓扑结构，同时由于持续同调信息能够体现数据的拓扑不变性，因此在聚类算法中更为稳定．也就是说将持续同调和聚类算法进行结合是有意义的，并且对于一些样本中拓扑结构明显的数据集，PHBC算法能够敏锐地捕捉到这些特征并加以利用．在运行时间上，由于PHBC算法多了计算持续同调的前置过程，因此比K-Means算法花费更多时间，而且像素参数p越小，需要生成的像素块越多，单次运行时间会更久．以在MNIST数据集上的结果为例，K-Means，CKM和PHBC算法单次最快的运行时间分别约为10，17.85和21.74 s，符合对算法时间复杂度的分析．综上可以得出：持续同调在多个公共数据集中均能够提取并保持数据原本的拓扑结构，由于这种结构信息能够区分不同种类的数据，因此将其进行一定程度的处理后，应用于聚类算法中对其效果有提升．4 结论本研究基于持续同调理论，研究将持续同调与聚类算法结合的可行性，提出了基于持续同调的聚类算法，在三种公用数据集上进行了实验测试与对比．实验结果表明：所提算法在多个指标上比传统聚类算法表现更佳，同时在随机数种子不同的状态下各种指标的标准差更小．这说明持续同调能够很好地发掘高维数据内部的拓扑结构信息，将持续同调与聚类算法进行结合在一定程度上能够提升聚类算法的性能和稳定性．对于规则的平面几何图形(包括数字和英文字母)加上噪声产生的模拟数据集，PHBC算法相比于传统聚类算法在精度上有较大的优势；但对于公用数据集，PHBC算法并没有表现出明显的优势．其原因是规则的平面几何模拟数据集中只含有二维拓扑信息，而公用数据集包含三维和更高维拓扑信息．由于高维持续同调数据计算的复杂性，PHBC算法只使用了0维和1维持续同调数据，并未使用高维持续同调数据，从而遗失了数据的高维拓扑信息，影响了算法在公用数据集上的效果．如果在基于持续同调的算法中使用高维持续同调数据，那么算法在公用数据集上的效果会有显著改善．