基于图的数据压缩方法的实验验证与应用

可在www.sciencedirect.com在线获取理论计算机科学电子笔记354（2020）45-60www.elsevier.com/locate/entcs凝聚数据的加权完全图A. Guzm'an-Ponce1J. RaymundoMarcial-Romero2R.M. Valdovinos-Rosas3UniversidadAuton'omadelEstadodeM'exico，FacultaddeIngenier'ıaToluca，EstadodeM'exico，M'exicoJ.S. S'anchez-Garreta4新成像技术研究所，计算机语言和系统系，JaumeI大学，Castell l′odelaPlana，Spain摘要在许多现实世界的问题（如工业应用，化学模型，社会网络分析等），他们的解决方案可以通过转换的顶点和边的问题也就是说，使用图论。 数据科学应用程序的特点是处理大量数据在某些情况下，数据的大小可能高于其处理的资源，这种情况使得禁止使用传统方法。通过这种方式，开发基于图的压缩数据的解决方案可能是处理大数据集的好策略。本文提出了两种基于图的数据压缩方法，这两种方法都是通过从整个数据集中获取一个导出子图或一棵最小生成树来构造一个带权的完全图。 我们做了一些实验为了验证我们的建议，使用24个基准真实数据集来训练1NN，C4.5和SVM分类器。 实验结果表明，该方法在不降低性能的前提下，有效地压缩了数据集分类器的几何平均值和Wilcoxon关键词：加权图，导出子图，最小生成树，凝聚数据，数据科学。1介绍如今，从数据中提取知识的一个有希望的领域被称为数据科学。数据科学是一种多学科方法，通过数据挖掘，深度学习，1电子邮件：mailto:angelicagp1416@hotmail.com2 通讯作者Email：mailto:jrmarcialr@uaemex.mx3电子邮件地址：mailto:rvaldovinosr@uaemex.mx4电子邮件：mailto:sanchez@uji.eshttps://doi.org/10.1016/j.entcs.2020.10.0051571-0661/© 2020作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。46A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45预测，机器学习，优化，预测分析和统计，以及其他[3]。数据科学中的主要问题是数据量，在某些情况下，数据量可能非常大，以至于无法应用传统的统计方法，甚至一些机器学习或数据挖掘算法。出于这个原因，有必要制定策略来获得数据的代表性子集，以便分类或预测算法不会影响其性能。图论正在成为其他科学领域的一种流行技术，用于解决现实世界中的问题。例如，在化学中，图可以表示分子的拓扑结构，在物理学中，图可以用于描述热力学稳定性的等级，在电气工程中，图论可以应用于天线及其频率的配置，在城市规划中，可以用于规划公共汽车路径或交通灯，以及许多其他优化问题可以通过图论解决，因为它是一种知识抽象的方式，从而可以获得可靠的解决方案[13，16，8，6]。在数据科学中，有几种基于图的方法，其主要思想是基于从图拓扑中提取知识。Newman等人[11]提出了一种通过迭代从图中移除边来聚类社区的方法，该算法赋予社区之间的边界边比社区内部的边更多的权重。他们的结果表明，可以从使用已知社区信息人工生成的网络中提取社区结构。Zhang和Hancock[18]提出了一种基于图的特征选择方法。他们使用权重图，其中一个顶点代表一个特征，它们的成对关系是一条边，边的权重由两个特征之间的相关程度给出。他们的建议使用多维交互信息标准进行特征选择，该标准检测具有更大相关性的特征组合之间的关系因此，建议获得类所拥有的最多信息。另一方面，Maillo等人。[10]提出了一种基于混合溢出树的模糊kNN方法，其中通过树结构近似最近邻。该方法有两种类型的二叉树：度量树和溢出树。度量树以空间层次的方式组织数据集的实例，其中它的根顶点表示所有实例，每个顶点表示一个实例。内部顶点被划分为两个子集，它们是不相交的集合，即它们没有重复的实例。而溢出树类似于度量树，不同之处在于溢出树允许重复实例。本文介绍了两种基于图论的数据压缩方法，即利用带权的完全图进行数据压缩。主要贡献可归纳如下：• 我们提出了使用图论来获得一个诱导子图，它允许得到类的边界，并建立一个最小生成树（MST），其中包括核心的数据。• 根据数据中所包括的类别之间的平衡，A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4547的代表性的情况下，将被认为是由诱导子图和MSP计算。• 实验表明，当使用我们的方法获得的压缩数据集时，分类器并没有降低其性能，事实上，它是增加的。本文其余部分的结构如下。在第2节中，我们回顾了本文中使用的主要定义。有关这两项建议的详情，请参阅第3节。而在第4节中，我们总结了所提出的方法所需的时间复杂度。 实验设置见第5节。 之后， 第6节解释了实验结果。最后，在第7节中，主要的结论和一些开放的行被暴露。2预赛设G=（V，E）是一个无向简单图（即无环且无平行边），它由一个非空顶点集V和一个边集E组成，其中每条边是一个非序顶点对，记为{u，v}.两个顶点v和v称为相邻的，如果有一条边{u，v}∈E，连接它们。一个完全图是一个简单的图，其中任何两个顶点是相邻的。图G =（V，E）中顶点v的邻域为N（v）={v ∈ V|{v，u} ∈E}，即N（v）是当N（v）≠v时，不含自身及其闭邻域的所有与v相邻的顶点的集合，记为N[v].注意v不在N（v）中，但在N[v]中。图H是G的一个子图，如果V（H）<$V（G）且E（H）<$E（G）.设X∈V（G）是一个删除的顶点集，其导出子图记为G-X;如果Y=V\X表示未删除的顶点集，则其导出子图记为G[Y]，称为G的Y导出子图，其中Y是G的顶点集，其边集由G的所有两端都在Y中的边组成。图中从顶点v到顶点u的路径是一个边序列：v0v1，v1v2，···，vn−1vn，使得v=v0，vn=u，vk与vk+1相邻，路径的长度为n。简单路是这样的路，使得v0，v1，···，vn−1都是不同的。一个循环是一个非空路径，使得第一个和最后一个顶点是相同的，一个简单循环是一个循环，其中没有顶点是重复的，除了第一个和最后一个顶点。一个连通图是一个图G=（V，E），如果G中的每一对顶点之间都有一条路。如果图是不连通的，则每个最大连通段称为一个分支。一个赋权图Gw=（V，E），是指图的每条边e∈E，令与一个实数w（e）相关联，称为其权重。加权图Gw的邻接矩阵是一个V×V矩阵MG=（wvu），其中每个元素（vi，vj）包含权w（e），权w（e）根据以下条件分配给边e=vi，vj或0顶点Vi和Vi在图中相邻或不相邻如果H是一个子图，使得H<$Gw，则H的权w（H）是48A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45Σ--的权重w（e）在其边缘上。 具有最小值的某类子图(or最大）权重，是一个图，其中最小（或最大）权重的路径连接两个指定的顶点u0和v0。 最小生成树是一个导出子图，它的边集连接所有顶点，没有任何圈，且它的边权和最小。3建议的压缩数据集在本节中，我们将介绍两种基于图的数据压缩方法。该建议首先将具有n个实例的两类数据集划分为两个子集，表示为C−和C+，分别来自负类和正类的实例。C+通常是最重要的类，它与另一个或多个类的代表性较低。我们的建议只适用于否定类，以减少它的基数，直到它可以类似于C+。为此，在生成导出子图或最小生成树之前，从C−we中包含的数据中构建加权完全图，其目的是分别获得负类的边界线或核算法1描述了一般过程。这些建议构建了一个加权的完全图（算法1中的GraphProcedure）来生成一个归纳子图（第3.1节）或一个最小生成树（第3.2节）。注意，IRm是期望的不平衡比率，即，正类大小与负类大小的期望比率。算法1压缩数据要求：DS=p1，p2，...，pn，IRm确保：DS1：将DS分成两个子集C−和C+。2：C′−←GraphProcedure（C−，IRm，C+）3：DS′=C+<$C′−给定由具有m个特征的n个实例形成的数据集DS，每个实例p n是元组（f n，1，fn，2，...，f n，m，ω），其中，f m是实例p n的第m个特征的值。这个实例属于一个类ω。图被用来模拟实际问题并获得最优解，因此我们的建议使用基于图的方法来获得子集CJ−。我们把集合C−看作一个加权完全图，记为Gw，它的构造如下：• V（G）={\displaystyle {\pi}∈C−|i∈V（G）}是顶点的集合。• E（G）={{v，u}|v，u ∈ V（G）}是边的集合.• 其中d（pv，pu）是v和u之间的欧氏距离.3.1诱导图欠采样（IG-US）IG-US是一种得到导出子图的方法，其目的是保持边界实例，即彼此距离较远的实例。算法2中描述的IG-US建议通过以下方式压缩负类A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4549←←←--联系我们--2016年10月22日，|C1−|−1）+σ2Z2联系我们⎩⎪（一）生成Gw的导出子图，该顶点集合将具有根据等式1的大小。 该大小将被更新并存储在变量Sample中，直到算法获得等于maxIR的不平衡比（IR5）（算法2中的第2-7行）。⎪⎧|C1−|σ2Z2f（x）=如果x= 12-|C1−|−1）+σ2Z2否则其中Z = 1。96，σ = 0。5，e = 0。05，置信度为95%。一旦获得了负类子集的大小，算法2通过每对实例（顶点）之间的距离来计算Gw的邻接矩阵（第9行）。函数GetMaximum确保一组边（实例对），根据邻接矩阵（第11行），这些边具有高距离。对于这个集合中的每条边，还没有被访问的顶点被添加到C2−中以标记为已访问（第12-20行）。最后，集合C2−是来自负类的压缩数据集。算法2IG-US算法Require：C1−，Rmax，C+确保：C2-压缩数据集1：建立Gw=（V，E）一个加权图，其中V=C1−2：Samp le←|C1−|3：IR样品|C+|4：当IR > maxIR时，样品σ2Z22016年10月22日，|C1−|−1）+σ2Z26：IR样品|C+|7：结束时8：C2−←[]9：M G← adjacencyMatrix（Gw）10：while|C2−| IRm时，Sσ2Z22016年10月22日，|C−| − 1）+ σ2 Z29：IRS|C+|10：结束时11：所有人v，u在E（MST）中，12：C′−u13：C′−v14：如果 C′−> S，则15：返回C′−16：如果结束17：结束在我们的建议中，首先在处理GetMST方法之前建立关联矩阵MG，以确保MST。GetMST需要权重图Gw及其关联矩阵来处理Prim(i) 选择一个顶点v，这是开始顶点。(ii) 选择MG中具有较低权重的边e={v，u}，将v标记为已访问。 现在，下一个要分析的顶点是u。(iii) 重复步骤2，只要选择的边链接一个已访问的顶点和其他未访问的顶点，提供任何循环。(iv) MST将被构建，直到所有顶点都被访问。虽然根据定义，MST包含图的所有顶点，但在我们的理论中，凝聚负类仅由MST的边集中的第一个S-顶点构建MIST-US算法在CJ−的大小大于S. S值是来自负类的实例的代表数量，并且它由等式1（第7-10行）计算4时间复杂度时间复杂度是通过计算算法执行的操作数量来估计的[2]，因此最坏情况被用来衡量时间复杂度。在我们的建议中，IG-US和MIST-US的时间复杂度描述如下：IG-US算法的时间复杂度为O（n2）。 在这种情况下，复杂性主要由以下指令集控制• 更新Sample和IR（第4-7行）的复杂度为n。• 计算邻接矩阵（第9行）的复杂度为n2.S8：S←A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4551• 生成样本大小的多数类子集（第10-23行）的复杂度为n2，它来自n次迭代，以计算复杂度为n的集合Maximum。因此，在最坏情况下，IG-US算法的时间复杂度为O（n2）。同样，MIST-US也是在O（n2）上计算的，因为：• 计算了n2上最坏情况下Gw的关联矩阵• 得到一个最小生成树，基于普里姆5实验装置为了验证所提出的方法，我们进行了一个实验研究，设计了超过24个实际问题的数据集与几个不平衡的比率（IR），即。IR>9.接下来的部分描述了所使用的数据集，用于测量方法性能的指标以及用于验证我们的建议的分类器5.1数据集实验在取自KEEL数据集存储库（https://sci2s.ugr.es/keel/imbalanced.php#subA）的24个两类数据集上进行，每个数据集在类之间具有不同的分布，即IR。表1总结了实验中使用的数据集的主要特征，数据集根据IR值的增加IR是通过将C +中包含的模式数除以C-的模式数而获得的。 我们可以看到 在表1中，IR的范围大约大于9到 82，这表示高的不平衡比。所有数据集均使用10倍交叉验证进行分区，以避免偏倚结果[5]。每个原始数据集被随机分为10个分层部分，对于每个折叠，9个块被用作训练集，其余部分被用作测试集。我们评估了我们的方法，比较了它们与文献中最流行的压缩数据方法的优势（见表2）。5.2评估指标使用决策树分类器（C4. 5）、1-最近邻分类器（1-NN）和支持向量机（SVM）分类器以及WEKA软件的所有默认值测试了压缩方法的性能为了评估学习分类器的行为，通常使用表3中的混淆矩阵（对于两类问题）[4]。由此，可以直接得到四个简单的度量：TP和TN表示正确分类的阳性和阴性案例的数量，而FP和FN分别表示错误分类的阳性和阴性样本的数量。52A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45方法描述RUS从C−中随机消除实例。CNN HartTL TomekEUS进化欠采样[9]，使用遗传算法从C−中删除实例RUSBOOST这种方法将RUS与AdaBoost算法结合起来[14]。基于聚类的SBC欠采样[17]，将数据集划分为k个聚类并根据其IR从每个聚类中的C-中随机选择若干实例预测阳性预测阴性正类真阳性（TP）假阴性（FN）负类假阳性（FP）真阴性（TN）表1数据库的基本特征的简要概述数据集类别分布#CNOIR1酵母-0-5-6-7-9 vs 4 51-477 528 9.352元音0 90-898 988 9.983玻璃-0-1-6 vs 2 17-175 192 10.294玻璃杯2 17-197 214 11.595梭-c 0-vs-c4 123-1706 1829 13.876酵母菌-1 vs 7 30-429 459 14.307玻璃杯4 13-201 214 15.478经济4 20-316 336 15.809页块-1-3 vs 4 28-444 472 15.8610玻璃-0-1-6 vs 5 9-175 184 19.4411梭-c2-vs-c4 6-123 129 20.5012酵母-1-4-5-8 vs 7 30-663 693 22.1013玻璃5 9-205 214 22.7814酵母菌-2 vs 8 20-462 482 23.1015阿扎尔-F 43-1023 1066 23.7916酵母菌4 51-1433 1484 28.1017酵母菌-1-2-8-9 vs 7 30-917 947 30.5718酵母菌5 44-1440 1484 32.7319埃科利0-1-3-7 vs 2-6 7-274 281 39.1420鲍鱼-17 vs 7-8-9-10 58-2280 2338 39.3121酵母菌6 35-1449 1484 41.4022架穿梭机2对5架49-3267 3316 66. 6723 kdd-bu-bu vs back 30-2203 2233 73.4324扑克-8-9 vs 5 25-2050 2075 82.00表2冷凝方法表3混淆矩阵当数据集中类别之间的分布不相等时，最推荐的度量是几何平均值，因为它试图最大化两个类别中每个类别的准确度，同时保持这些准确度平衡[1]：A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4553TP+FNTN+FPCNNTLRus1NNC4.5SVMEUS原始02468 10RUSBOOST关于我们SBCIG-USFig. 1. 平均秩g=a+·a−，其中a+表示少数类的精度（TP），a−是多数类精度（TN）。6结果分析在本节中，我们将通过两种方式分析结果：(i) 所提出的方法与表2中描述的技术之间的比较，使用分类器1NN，C4.5和SVM。(ii) 当使用压缩数据集时，分类器1NN，C4.5和SVM6.1性能比较图1中给出的实验结果对应于平均Fisher秩，其中最佳冷凝方法是具有最低值的方法。这些结果是通过总体几何平均值获得的，其结果报告在Ap-pendulum A中。出于比较目的，纳入了原始数据集（即未还原）的结果。从本节报告的结果中，可以得出一些初步结论。首先，从图1中的结果来看，根据Fisher秩，独立使用IG-US和MIST-US的分类器获得了最佳性能。当比较压缩方法之间的行为时，我们可以看到我们的方法优于基于邻域的策略，如CNN和TL。然而，一些随机方法可以获得有竞争力的结果，如RUS和RUSBOOTS，其Fisher比较这两种方案（表A.3），我们可以观察到IG-US在每个分类器的14个和13个数据集上仍然优于1 NN和C4.5分类器的MIST-US，而MIST-US分别有6个和8个数据集。仅在SVM分类器中，MIST-US在11个数据集上的性能优于IG-US在10个数据集上的性能54A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45数据集。最后，我们可以得出结论，得到一个负类的核作为一个凝聚-由于MIST-US保留了一个远离类间边界的根据本节所示的结果，我们认为有必要进行统计分析，这包括在下一节。6.2统计显著性分析为了完成分析，我们采用置信水平为0的Wilcoxon检验。九比零。95，以确定结果之间的统计意义。表4 - 6总结了Wilcoxon检验，其中上对角线是水平显著性α = 0的一部分。9，下对角线为α = 0。95.符号“·“表示行中的方法改进了列中的方法，否则，我们使用符号“"。最后两行表示根据显著性水平，列方法与其他方法相比具有统计学显著性的方法数量。表4使用1NN分类器的Wilcoxon检验总结原始RusCNNTLEUSRUSBOOSTSBCIG-US关于我们原始-○·○○○○○○Rus·-··○CNN○○-○○○○○○TL·○·-○○○○○EUS···-·○RUSBOOST···-○SBC···○-○○IG-US·······-·关于我们····-α= 0。9130243374α= 0。95130243374为了进行分析，我们以表5为例，重点关注提案IG-US，当我们进行配对比较时，显著性水平为0。95（粗体行），有四种方法IG-US改进了其他方法（原始，CNN，TL和SBC）。但是，显著性水平为0。90（粗体栏），IG-US提供了六种方法的统计学显著性：原始，RUS，CNN，TL，EUS和SBC。从表4-6中的结果可以看出，删除被认为是冗余的实例的方法，例如CNN，性能低于其他方法，因为在任何分类器中，与其他方法相比，都有一些元素可以改善CNN获得的结果尽管如此，RUS、TL、RUSBOOST和SBC等方法在统计学上显著低于我们对1 NN分类器的建议，但对于SVM分类器，EUS方法的统计显著性优于IG-US，但MIST-US明显优于A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4555表5使用C4.5分类器的Wilcoxon检验总结原始RusCNNTLEUSRUSBOOSTSBCIG-US关于我们○ ○ ○•○○○ ○ ○ ○○ ○ ○•○- -○-○ ○•-关于我们····-α= 0。9140144165α= 0。95140144144表6使用SVM分类器的Wilcoxon检验总结原始RusCNNTLEUSRUSBOOSTSBCIG-US关于我们○ ○ ○•○○ ○ ○○ ○ ○··- ·○○-○ ○•-关于我们······-α= 0。9040054046α= 0。95040054046整体方法。从这些结果中，我们可以得出结论，加权完全图的压缩数据比在实验中使用的另一种方法6.3减少百分比的影响确定浓缩方法是否可行的一个重要方面是获得的IR百分比。图2绘制了每种方法的平均降低百分比，每种方法和数据集的降低百分比详情见附录B。从图2中，我们可以注意到：• IB-US和MIST-US是IR降低最高的方法，约为1.0。• 没有很好的减少百分比的方法是TL和SBC。第一个是根据实现链接的形式来删除实例，因此在大多数数据集中，在负类中可能没有形成Tomek链接的实例。而第二种方法，集群建设可能是原因，由于低密度的负类。原始俄罗斯- ○·○- -CNNTL○ ○-○ ○○·-○EUS···-RUSBOOSTSBC···○·○IG-US···原始俄罗斯- ○ ○- -CNN○-○TL○-○EUS···-RUSBOOSTSBC···○○ ○IG-US···56A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45• 最后，IB-US和MIST-US在几何平均值方面具有最佳性能，数据集浓缩的IR太低TLEUSRUSBOOSTSBCCNNRus0 20 40 60 80 100关于我们IG-US图二. 平均减少7总结发言在这项工作中，我们提出了两种新的凝聚方法，称为IG-US和MIST-US。新的方法考虑了一个加权完全图，以获得两个结构：第一种方法是生成一个导出子图，该子图保持了否定类的边界实例，第二种方法是利用否定类的核所包含的模式构造一棵最小生成树。使用三种监督分类器：1NN，C4. 5和SVM进行实验研究，从而验证了所提出方法的有效性我们将这两种方法的性能与一些众所周知的压缩方法进行了比较，发现这两种方法都获得了IR非常低的高质量数据集，其中分类器的行为优于使用其他压缩方法时获得此外，计算在最坏的情况下，两个建议的成本都是O（n2）。最后，使用Wilcoxon检验可以强调，与现有技术中广泛使用的其他压缩方法相比，所提出的方法获得了高度压缩的数据集，而没有丢失有用的信息，在几何平均值方面具有统计学显著性和更好的开放线指出要研究多类问题，应用另一个分类器，以及使用更大规模的数据集确认这项工作部分得到了Jaume I大学的资助[UJI-B2018-49]，墨西哥CONACYT奖学金[702275]和5046/2020 CIC UAEM项目的支持。A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）4557引用[1] Cleofas-Sanchez ， L. ，J.你 好 ， 维 。Garc'ıa 和 R.Valdovinos ， Associativelearningonimbalancedenvironments ： An empirical study ， Expert Systems with Applications 54（2016），pp. 387-397.[2] Cormen，T. H、C. E.莱瑟森河L. Rivest和C. Stein，[3] Dhar，V.，数据科学与预测，Commun。ACM56（2013），pp. 六十四比七十三[4] Galar，M.，A. Fernandez，E. Barrenechea，H. Bustince和F. Herrera，A Review on Ensembles forthe Class Imbalance Problem ： Bagging- ， Boosting- ， and Hybrid-Based Approaches ， IEEETransactions on Systems ， Man ， and Cybernetics ， Part C （ Applications and Reviews ） 42（2012），pp.463-484.[5] Gar c'ıa，V.，A. I. Marq u′es和J. S. S'anc hez，探索样本类型对信用风险和企业破产预测的集合性能的同步效应，信息融合47（2019），pp. 88比101[6] Gonz'alez ， A. ，E.Barra ， A.Beghelli和 A.Leiva ， Asub-graphmapping-basedalgorithmforvirtualnetwork allocation over a mixable grid networks ， in ： 2015 17th InternationalConference on Transparent Optical Networks（ICTON），2015，pp. 一比四[7] Hart ， P. ， The Condensed Nearest Neighbor Rule ， IEEE Transactions on Information Theory14（1968），pp. 515-516[8] 哈桑尼湖，M. R. Moosavi和P. Setoodeh，一种基于图形的方法来分析应变工程的代谢网络，在：2019年第27届伊朗电气工程会议（ICEE），2019年，pp. 1839-1843.[9] 刘 ， X. ， J.Wu 和 Z. Zhou ， Exploratory Undersampling for Class-Imbalance Learning ， IEEETransactions on Systems，Man，and Cybernetics，Part B（Cybernetics）39（2009），pp.539-550[10] Maillo，J.， J. Luengo，S. Gar c'ıa，F. 我和赫拉拉。 Triguero，Apreeliminarystudyonhybridspil l-t reefuzzyk-nearest neighbors for big data classification ， in ： 2018 IEEE International Conference on FuzzySystems（FUZZ-IEEE），2018，pp. 一比八[11] Newman，M. E. J.和M. Girvan，Finding and Evaluating Community Structure in Networks，Phys. Rev.E69（2004），p.026113。URLhttps://link.aps.org/doi/10.1103/PhysRevE.69.026113[12] 普里姆河C.的方法，最短连接网络和一些推广，贝尔系统技术杂志36（1957），pp. 公元1389-1401年。[13] Samaddar，A.， T. Goswami，S. Ghosh和S. 2015年IEEE国际高级计算会议（IACC），2015年，第100页，一种用于输入和存储更广泛的化学反应类别以挖掘化学图的算法1082-1086[14] 塞伊·塞尔特角，T. M. Khoshgoftaar，J. Van Hulse和A. Napolitano，RUSBoost：缓解阶级不平衡的混 合 方 法 ， IEEE Transactions on Systems ， Man ， and Cybernetics - Part A ： Systems andHumans40（2010），pp. 185-197.[15] 托梅克岛CNN的两个，IEEE Transactions on Systems，Man，and CyberneticsSMC-6（1976），pp. 769-772。[16] Turvill，D.，L. Barnby和A. Anjum，在高能物理分析中使用图形表示的概念框架，在：2018年第18届IEEE/ACM集群，云和网格计算国际研讨会（CCGRID），2018年，pp. 384-385.[17] Yen ， S.- J. 和 Y.- S. Lee ， 基 于 不 平 衡 数 据 分 布 的 欠 采 样 方 法 ， Expert Systems with Applications36（2009），pp.5718-5727[18] Zhang，Z.和E. R. Hancock，基于图的特征选择方法，X。Jiang，M.费雷尔和A. Torsello，editors，Graph-Based Representations in Pattern Recognition（2011），pp. 205-21458A. 古兹曼-庞塞等人/理论计算机科学电子笔记354（2020）45A分类结果本附录中的表格总结了1-NN、C4.5和SVM分类器在压缩数据集上的性能分类。表A.1通过1-NN获得的几何平均结果数据集原始RusCNNTLEUSRUSBOOSTSBCIG-US关于我们酵母-0-5-6-7-9 vs 461.273.550.769.078.476.777.193.775.8元音010097.270.710098.998.799.810098.8玻璃-0-1-6 vs 247.074.451.052.668.364.153.191.163.4玻璃杯240.776.251.641.064.768.753.193.968.6shuttle-c0-vs-c4 799.699.610099.699.699.699.699.699.6酵母菌-1 vs 762.374.846.267.666.665.967.294.970.7玻璃杯486.679.965.386.680.787.486.688.496.1Ecoli486.395.081.486.392.592.291.994.9100页面块-1-3 vs 498.298.294.598.294.596.699.998.198.2玻璃-0-1-6 vs 580.977.065.180.994.391.094.088.994.9穿梭机-c2-vs-c491.391.381.691.310098.291.391.392.6酵母-1-4-5-8 vs 744.164.539.747.969.765.157.090.670.5玻璃581.194.375.281.288.291.293.394.394.9酵母菌-2 vs 877.059.858.377.354.875.180.292.265.5双氯芬酸-F30.381.430.633.778.977.326.176.682.4酵母458.883.343.762.284.377.178.688.472.3酵母-1-2-8-9 vs 747.656.642.554.264.565.047.694.973.0酵母582.110065.587.693.294.682.186.397.5ecoli-0-1-3-7 vs 2-683.778.248.884.092.681.984.265.587.3鲍鱼-17 vs 7-8-9-1050.677.644.845.373.978.658.397.289.9酵母671.169.954.879.081.083.771.293.579.2shuttle-2 vs 510099.096.110010099.9100100100kdd-bu-bu10010010010010010010098.4100扑克-8-9 vs 519.953.114.820.061.265.134.587.749.6Avg. 秩6.54.88.25.64.24.45.03.13.3表A.2通过c4.5获得的几何平均值结果数据集原始RusCNNTLEUSRUSBOOSTSBCIG-US关于我们酵母-0-5-6-7-9 vs 465.170.660.265.873.277.074.387.973.0元音096.992.880.396.995.095.994.596.096.5玻璃-0-1-6 vs 252.360.043.853.146.763.552.094.133.4玻璃杯253.190.722.433.255.265.258.297.082.4shuttle-c0-vs-c4 710010099.610010099.999.9100100酵母菌-1 vs 754.364.557.265.271.667.462.884.970.9玻璃杯482.273.073.082.288.489.172.480.796.1Ecoli482.987.592.382.976.586.377.181.482.8页面块-1-3 vs 496.110094.599.898.297.597.194.398.2玻璃-0-1-6 vs 599.488.295.393.710092.599.783.1100穿梭机-c2-vs-c490.910081.690.991.399.490.9100100酵母-1-4-5-8 vs 70.059.60.00.066.653.125.891.362.5玻璃598.810085.399.594.393.910083.1100酵母菌-2 vs 822.461.269.20.074.872.131.679.164.7双氯芬酸-F15.285.932.70.084.884.20.078.989.4酵母453.978.30.057.483.378.268.482.377.3酵母-1-2-8-9 vs 748.253.747.944.659.967.340.896.566.6酵母586.396.677.889.087.494.288.987.795.2ecoli-0-1-3-7 vs 2-684.471.470.484.470.074.584.457.194.3鲍鱼-17 vs 7-8-9-1034.775.00.034.678.875.557.092.788.7酵母673.372.870.273.382.681.971.490.885.3shuttle-2 vs 5100100100100100100100100100kdd-bu-bu98.395.00.098.398.397.798.395.096.6扑克-8-9 vs 50.047.80.00.044.044.60.056.644.4