聚类算法基准测试框架及数据集浏览器

软件X 20（2022）101270原始软件出版物一个聚类算法基准测试框架马雷克·加戈列夫斯基华沙理工大学数学与信息科学学院，ul。Koszykowa 75，00-662 Warsaw，Poland迪肯大学，IT学院数据到智能研究中心，Geelong，VIC 3220，Australiaar t i cl e i nf o文章历史记录：收到日期：2022年收到修订版2022年11月7日接受2022年关键词：聚类机器学习基准数据噪声点外部聚类有效性分区相似性得分a b st ra ct聚类算法的评估可以包括在各种基准问题上运行它们，并将它们的输出与专家提供的参考、地面实况分组进行比较。不幸的是，许多研究论文和毕业论文只考虑了少量的数据集。此外，事实上，可以有许多同样有效的方法来聚类一个给定的问题集，考虑了为了克服这些限制，我们已经开发了一个框架，其目的是引入一个一致的方法来测试聚类算法。 此外，我们已经聚合，抛光和标准化了许多机器学习和数据挖掘文献中提到的聚类基准数据集，并包括不同维度，大小和聚类类型的新数据集。一个交互式数据集浏览器，Python API的文档，从其他编程语言（如R或MATLAB）与框架交互的方式的描述，以及其他细节都在https：//clustering-benchmarks上提供。gagolewski.com网站。©2022作者（S）。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本1.1.1代码库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-22-00288法律代码许可证GNU AGPL v3使用git的代码版本控制系统软件代码语言使用Python编译要求、操作环境和依赖关系Python 3.7+，包含numpy、scipy、pandas、matplotlib、scikit-learn和genieclust链接到开发人员文档/手册https://clustering-benchmarks.gagolewski.com功能请求和错误跟踪器https://github.com/gagolews/clustering-benchmarks/issues1. 介绍聚类分析[1-我们知道没有一个然而，在将有希望的方法与系统性令人失望的方法分开方面，还有很多工作要做[3，5，6聚类验证的一种方法依赖于使用所谓的内部度量，联系人：迪肯大学，数据到智能研究中心，IT学院，吉朗，VIC 3220，澳大利亚。电子邮件地址：m. deakin.edu.au。网址：https://www.gagolewski.com。https://doi.org/10.1016/j.softx.2022.101270将质量划分为单个数字[7在实践中，他们只能关注给定分割的单个属性（例如，集可分性或紧致性），它们所促进的划分可能远非合理[10]。另一种方法是使用外部有效性度量[11-不幸的是，研究论文和研究生论文只考虑少量基准数据集的情况并不少见。我们经常从UCI [ 15 ]数据库中遇到相同的5这显然是太少，使任何评估足够严格，从而可能导致过度拟合[16，17]。一些作者提出了自己的数据集，但没有针对其他基准电池测试他们的方法。这可能会引起 有偏见的结论，因为有一个风险，只有问题，2352-7110/©2022作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx马雷克·加戈列夫斯基软件X 20（2022）1012702σ（∑）联系我们ˆ≥Kimport clustbench#clustering-benchmarksimport os.path，genieclust，sklearn.cluster#我们稍后会用到这些data_path= os.path.join（“连接”，“Projects”，“clustering-data-v1”）#example‘‘easy’’另一方面，慷慨分享数据的研究人员（例如，[15，18此外，现有的存储库没有反映出同一数据集可能有许多同样有效/合理/有用的分区的想法;参见[2，22]进行讨论。另一方面，在其他机器学习我们可以确定混淆矩阵C，其中ci，j表示第i个参考聚类中分配给第j个聚类的点的数量。即使这样的矩阵总结了判断两个分区之间的相似性所需的所有信息，如果我们希望比较质量，不同的算法，我们宁愿它聚合在一个单一的数字的形式。作为许多外部聚类有效性指数之一（参见，例如，[12域（分类和回归数据集，Max1∑kci，σ（i） −1提到了UCI [15];但也测试了用于测试全局优化求解器，例如，[23、24]）。AAA（C）=i=11−1ci，·k为了克服这些差距，本项目建议一个一致的框架基准聚类算法。下一节将对其进行描述。在第三节中，我们=1−min1Kki=1ci，1+···+ci，k−ci，σ（i）、k−k1（ci，1+···+ci，k）描述一个Python API（集群基准包可用，可 以 在 PyPI 上 使 用 ; 参 见 https://pypi.org/project/clustering-benchmarks/），这使得与之的交互相对容易。第4节总结了本文，并提出了一些想法，这一框架的未来发展。2. 方法我们已经编译了一个相当大的套件的示例真实和模拟基准数据集。为了可重复性，我们套件的发布版本是有版本的：例如，https://github.com/gagolews/clustering-data-v1/releases/tag/v1.1.0链接到2022年9月发布的修订版[25]。目前，有九个电池（集合），每个电池都有几个不同来源，维度，大小不平衡和重叠程度的数据集;包括但不限于[12，15，18请注意，数据集和所述软件彼此独立。因此，将来可以轻松添加新的数据集。此外，用户可以自由使用自己的集合或从其他编程环境中访问数据。当前框架定义了建议的统一文件格式，详细信息见项目引用分区。当提到一个特定的基准问题时，我们使用约定“电池/数据集”，例如，‘‘设X是由Rd中的n个点组成的这样的数据集之一。 每个数据集都配备了专家分配的参考分区。这样的将点分组为k 2个聚类的分组使用标签向量y进行编码，其中y i1，. . .，k给出第i个对象的簇ID。例如，图1的左子图。图1描绘了wut/x2的地面实况3-聚类（基于有关如何从三个高斯分布的混合生成该数据集的信息）。运行问题中的算法。让我们考虑一个聚类算法的质量，我们想评估。当我们在X上应用它来发现新的k-分区时（以无监督的方式，即，不显示真实的y），我们获得编码新分组y的预测标签的向量。例如，图2中的第一行散点图描绘了通过三种不同方法发现的wut/x2的3个分区。评估分区相似性。理想情况下，我们希望使用产生与参考分区紧密匹配的分区的算法。在尽可能广泛的一组问题上，这应该是正确的因此，我们需要将预测的标签与参考标签相关联。1原始数据集没有配备替代标签，也没有噪音点标记;这些都是由当前作者添加的它可以被认为是衡量正确识别每个聚类中的点 由于实际的集群ID无关紧要（分区是集群的集合，并且集合根据定义是无序的），因此通过找到集合{1，. . .，k}。可以有许多有效的分区。更重要的是，在无监督学习的精神中，在许多情况下，可能有许多同样有效的方法来分割给定的数据集。一个算法如果能找到一个与任何一个参考分区紧密匹配的分区，就应该得到奖励这可能需要多次运行该方法（除非它是一个分层的方法）来找到不同基数的然后，针对所有可用的参考标签评估生成的输出，并报告最大相似性得分噪音点。此外，为了使聚类问题更加困难，一些数据集可能以噪声点为特征（例如，实际聚类之间的异常值或不相关点）。它们在地面实况向量中被特别标记：我们为它们分配了集群ID 0;比较图1的右侧子图。1、颜色为灰色。聚类算法决不能被告知这些“问题”点的位置。一旦确定了数据集的分区，它们就被排除在外部聚类有效性度量的计算之外。换句话说，将噪声点分配给哪个聚类并不重要。3. Python API为了促进上述框架的使用，我们为Python实现了一个名为集群基准的开源包。它可以从PyPI（https：//pypi.org/project/clustering-benchmarks/），例如， 通过调用pip 3installclustering-benchmarks。然后，可以通过调用导入：获取基准数据。示例数据集存储库[25]（或用户提供的任何自定义存储库）可以轻松查询。假设我们将其存储在以下目录中：一个特定的数据集（例如：wut/x2）可以通过调用来访问：马雷克·加戈列夫斯基软件X 20（2022）1012703==-电池，数据集=“wut”，“x2”b= clustbench.load_dataset（电池，数据集，路径=数据路径）b.数据，标签s=b.标签[i]-1，轴=“相等“，标题e=f“标签{i}“）plt.show）搜索结果Fig. 1. 示例基准数据集（wut/x2）和两个 对应的 参考分区（k = 3和k = 4;噪声点以灰色标记）。图二. Genie（g 0. 3）[33，34]，k-means和ITM [35]（k 3和k 4）.混淆矩阵和调整 不对称准确性（AAA; [11];与图11中所示的参考分区进行比较。（1）报告。 请注意，第二个地面真值分区具有一些噪声点：因此，在k = 4的 情况下，混 淆 矩 阵 的第一行不 被考虑。上面的调用返回一个命名的元组，其data字段给出数据矩阵，labels 给出所有ground-truth partitions 的列表（ 编码为labelvectors），n_clusters给出相应的子集数量。例如，这里有一个方法我们已经生成了图。1.一、获取预先计算的结果。 假设我们想 研究一些预先计算聚类结果（参见https：//github.com/gagolews/clustering-results-v1），我们将其本地存储在以下目录中：results_path= os.path.join（“目录”，“项目”，“clustering-results-v1”，“原始”）可以通过调用以下命令来获取分区：foriinrange（len（b.labels））：plt.subplot（1，len（b.labels），i+1）马雷克·加戈列夫斯基软件X 20（2022）1012704=res= clustbench.load_results（“Genie”，b.battery，b.dataset，b.n_clusters，path= results_path）print（list（res.keys（）##['Genie_G0.1'，'Genie_G0.3'，'Genie_G0.5'，'Genie_G0.7'，'Genie_G1.0']因此，我们可以访问具有不同gini_threshold（g）参数设置（g 1. 0给出了单一链接方法）。计算外部集群有效性度量。以下是计算外部集群有效性度量的方法：round（clustbench.get_score（b.labels，res[“Genie_G0.3”]），2）0.87默认情况下，应用调整的不对称准确度（AAA; [11]），但可以通过显式设置度量参数将其更改为任何其他分数如上所述，我们将预测的聚类与所有参考分区进行比较（忽略噪声点），并报告最大得分。手动应用聚类方法。我们可以使用clustbench.fit_predict_many来生成将我们自己与引用标签进行比较所让我们测试scikit-learn包中实现的k-means算法[36]：m= sklearn.cluster.KMeans（）res[“KMeans”]=clustbench.fit_predict_many（m，b.data，b.n_clusters）round（clustbench.get_score（b.labels，res[“KMeans”]），2）0.98我们看到，k均值（专门用于检测对称高斯样斑点）在这个特定数据集上的表现优于Genie;见图。2用于说明（也具有ITM方法产生的结果[35]）。该项目4. 结论目前的项目被设计为可扩展的，以便它可以容纳新的数据集和/或标签向量在未来-从而使聚类算法的评估更加严格。任何贡献都是热烈欢迎的;请参阅https：github.com/gagolews/clustering-benchmarks/issues获取功能请求和错误跟踪。特别是，我们已经实现了一个交互式的独立应用程序，可用于准备我们自己的二维数据集（Colouriser）。基准测试套件的未来版本将包括用于生成与给定数据集类似的任意大小/聚类大小分布的随机样本更多的噪音）。由于这一点，在具有许多可调参数的算法的情况[17]以及其中的参考文献）从测试中（用于最终比较），这是其他机器学习领域中相当标准的方法。此外，该框架可以扩展到覆盖重叠聚类以及半监督学习任务，其中算法提前知道一些输入点的正确分配。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作数据可用性数据是公开的。确认这项研究得到了澳大利亚研究发现项目ARC DP210100227的支持。文档和数据可在http：//clustering-benchmarks上公开获取。gagogolewski. com ， https ： //github. com/gagolews/clustering-data-v1 ， 以 及 https ： //github 。 com/gagolews/clustering-results-v1.非常感谢所有与聚类社区分享数据集的研究人员引用[1] 亨 尼 希 角 什 么 是 真 正 的 集 群 ？ Pattern Recognit Lett 2015;64 ：53http://dx.doi.org/10.1016/j.patrec.2015.04.009网站。[2]作者： Luxburg U， Williamson R，Guyon I.集群： 科学还是艺 术？In：Guyon I，et al.，编辑器。ICML关于无监督和迁移学习的研讨会。Proc. 机器学习研究，卷。27，2012，p.六十五比七十九[3]Van Mechelen I，et al. Benchmarking in Cluster Analysis：A White Paper.2018年12月28日，中国科学院出版社。https://arxiv.org/pdf/1809.10496.pdf[4] Ackerman M，Ben-David S，Brânzei S，Loker D.加权聚类：解决用户的困境。模式识别2021;120：108152。http://dx.doi.org/10.1016/j.patcog.2021.108152网站。[5]熊红，李志.聚类验证措施。在：Aggarwal C，Reddy C，编辑.数据聚类：算法和应用。CRC Press; 2014，p. 571 -606.[6] 张文辉，张文辉，张文辉.基于对象的密度聚类验证。模式识别2022;121：108223。http://dx.doi.org/10.1016/j的网站。2021.108223。[7]放 大 图 片 作 者 ： Kristan M. 对 确 定 数 据 集 中 聚 类 数 的 过 程 的 研 究 。Psychometrika1985;50（2）：159-79.[8] Bandyopadhyay S. 若 干 聚 类 算 法 的 性 能 评 价 及 有 效 性 指 标 。 IEEETransPatternAnalMachIntell2002;24（12）：1650-4.http://dx.doi.org/10.1109/TPAMI.2002.1114856网站。[9]Arbelaitz O，Gurrutxaga I，Muguerza J，Pérez J，Perona I. 聚类有效性指标 的 广 泛 比 较 研 究 。 PatternRecognit 2013;46 （ 1 ） ： 243-56.http://dx.doi.org/10.1016/j.patcog.2012.07.021网站。[10] 杨伟华，王伟华，王伟华.集群有效性度量（in）是否有效？Inform Sci2021;581：620-36. http://dx.doi.org/10.1016/j.ins的网站。2021.10.004。[11]加戈列夫斯基湾调整后的不对称准确性：表现良好的外部集群有效性测量，（预印本）2022 [提交出版]，https：//doi.org/10.48550/arXiv.2209.02935、https://arxiv.org/pdf/2209.02935.pdf。[12]Rezaei M，Fränti P.设置外部集群有效性的匹配措施。IEEE Trans KnowlDataEng2016;28（8）：2173-86.http://dx.doi.org/10.1109/TKDE.2016.2551240.[13]Wagner S ， Wagner D. 比 较 聚 类 - 概 述 。 Tech. rep. 2006-04 ， Faculty ofInformatics，UniversitätKarlsruhe（TH）;2006，URLhttps://i11www.iti.kit.edu/extra/publications/ww-cco-06.pdf.[14]奥尔塔D，坎佩洛R。比较硬聚类和重叠聚类。J MachLearn Res2015;16（93）：2949-97.[15]Dua D，Graff C. UCI机器学习库。2022年，http://archive.ics。uci.edu/ml网站。[16]Ullmann T，Beer A，Hünemörder M，Seidl T，Boulesteix A-L.过度乐观的评 估 和 报 告 的 新 的 集 群 算 法 ： 一 个 说 明 性 的 研 究 。 2022 年 .http://dx.doi.org/10.1007/s11634-022-00496-5.[17]Ullmann T，Hennig C，Boulesteix A-L.验证数据的聚类分析结果的验证：一个系统框架。Wiley Interpretation Rev：Data Min Knowl Dis 2021;12（3）：e14444。http://dx.doi.org/10.1002/widm.1444网站。[18] 作者：Graves D，Pedrycz W.基于核的模糊聚类和模糊聚类：一个比较实验研究。模糊集与系统2010;161：522-43。http://dx.doi.org/10.1016/j.fss.2009.10.021网站。[19]乌尔奇河使用SOM聚类：U*C。在：自组织地图研讨会。2005年，p. 75比82[20]Thrun M，Ultsch A.利用基本聚类问题对基准数据集进行聚类。数据摘要2020;30 ： 105501 。 http://dx.doi.org/10.1016/j.dib.2020.105501 的 网 站 上 发 布的。[21] Fränti P，Sieranoja S.六个聚类基准数据集上的K均值属性。Appl Intell2018;48（12）：4743-59. http://dx.doi.org/10.1007/s10489-018-1238-7.马雷克·加戈列夫斯基软件X 20（2022）1012705[22]Dasgupta S，Ng V. Single Data，Multiple Clusterings.在：Proc. NIPS研讨会集群：科学还是艺术？有原则的方法。2009年[23]Jamil M，Yang X-S，Zepernick H-J. 8-全局优化的测试函数：全面调查。在 ： 群 智 能 和 生 物 启 发 计 算 。 2013 年 ， 第 193-222 页 。http://dx.doi.org/10.1016/B978-0-12-405163-8.00008-9.[24] Benchmarking Optimization Algorithms ： An Open Source Frameworkfor the Traveling Salesman Problem. IEEE Comput Intell Mag 2014;9（3）：40-52. http://dx.doi.org/10.1109/MCI.2014.2326101网站。[25]Gagolewski M，et al.聚类算法的基准测试套件：版本1.1.0. 2022，http://dx.doi.org/10.5281/zenodo.7088171，URL https：//github.com/gagolews/clustering-data-v1/releases/tag/v1.1.0.[26] Thrun M ， Stier Q. 基 本 聚 类 算 法 套 件 。 SoftwareX 2021;13 ： 100642.http://dx.doi.org/10.1016/j.softx.2020.100642网站。[27]Karypis G，Han E，Kumar V. CHAMELEON：使用动态建模的层次聚类。计算机1999;32（8）：68-75. http://dx.doi.org/10.1109/2.781637.[28]Bezdek J，Keller J，Krishnapuram R，Kuncheva L，Czech N. 真正的虹膜数据能站起来吗？IEEE Trans-Fuzzy Syst 1999;7（3）：368网址：//dx.doi.org/10.1109/91.771092网站。[29] McInnes L，Healy J，Astels S. hdbscan：基于层次密度的聚类。J OpenSource Softw 2017;2（11）：205. http://dx.doi.org/10.21105/joss的网站。00205。[30]弗伦蒂·P，维尔马约基·O.聚类问题的迭代收缩法。模式识别2006;39（5）：761-5.[31] Sieranoja S，Fränti P.快速和一般密度峰值聚类。Pattern Recognit Lett2019;128：551-8. http://dx.doi.org/10.1016/j.patrec.2019.10的网站。019.[32]Jain A，Law M.数据聚类：用户的困境。计算机科学讲义2005;3776：1-10.[33]杨伟华，王伟华，王伟华. Genie：一种新的、快速的、抗离群的层次聚类算法.Inform Sci 2016;363：8-23. 网址：//dx.doi.org/10.1016/j.ins.2016.05.003网站。[34] 加戈列夫斯基湾genieclust：快速和强大的层次聚类。SoftwareX 2021;15：100722. http://dx.doi.org/10.1016/j.softx.2021.100722网站。[35]Müller A，Nowozin S，Lampert C. 基于最小生成树的信息论聚类。在：Proc.德国模式识别会议。2012年。[36]Pedregosa F ， et al. Scikit-learn ： Machine learning in Python. J MachLearnRes2011;12（85）：2825-30.