==软件X 17（2022）100944原始软件出版物DCEM：一个通过以数据为中心的期望最大化修改来聚类大数据的R包Parichit Sharmaa，Mr. Hasan Kurbana，b，Mehmet Dalkilicaa印第安纳大学Luddy信息学、计算和工程学院计算机科学系，700 N。 Woodlawn Ave. 关闭IN，USAb土耳其锡尔特大学计算机工程系，56100 Siirtar t i cl e i nf o文章历史记录：接收20九月2021收到修订版2021年12月11日保留字：以数据为中心的机器学习大数据无监督聚类期望最大化开源软件a b st ra ct聚类是棘手的，所以存在技术来给出最佳近似。期望最大化（EM），最初用于填补缺失数据，是最流行的。固定数量的概率分布（PDF）的参数以及属于每个PDF的数据的概率迭代计算。EM不随数据大小而扩展，这阻碍了其当前的使用。使用以数据为中心的方法，我们在算法中插入层次结构，以将高表达数据（HE）与低表达数据（LE）分开：前者在某些迭代i处极大地影响目标函数，而LE则不会。通过交替使用HE或HE+LE，我们显著减少了EM的运行时间。我们称之为新的、以数据为中心的EM，EM*。我们设计并开发了一个名为DCEM（带有E期望最大化的数据聚类）的R软件包来强调这些数据在驱动算法DCEM优于EM，因为我们改变大小，尺寸和可分性，独立于科学领域。DCEM是模块化的，可以用作独立程序或可插拔组件。DCEM也包括我们对原始EM的实现。据我们所知，没有开源软件专门专注于在没有显式并行化，修改种子或数据减少的情况下改进EM聚类。DCEM可以在CRAN（Comprehensive R Archive Network）上免费访问。版权所有2021作者。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v2.0.3用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-21-00177法律代码许可证GPL-3使用GIT的代码版本控制系统使用的软件代码语言、工具和服务R>3.5编译要求，操作环境依赖性R>3.5，matrixcalc，mvtnorm，MASS，Rcpp如果可用，链接到开发人员文档/手册https://cran.r-project.org/web/packages/DCEM/DCEM.pdf问题支持电子邮件parishar@iu.edu1. 介绍著名物理学家费曼在50多年前观察到，随着时间的推移，计算时间与数据大小的比率将接近于零。令人惊讶的是我们已经接近零的速度！以数据为中心的人工智能[2，3]是对这一日益增长的挑战的回应，它专注于数据，它的准备和管理，以及如何，当迭代到*通讯作者。电子邮件地址：parishar@iu.edu（Parichit Sharma）.https://doi.org/10.1016/j.softx.2021.100944一个最佳值，不仅数据的值会改变，而且该值可以在更有效的算法中被利用。第一个以数据为中心的人工智能研讨会于今年成立[4]。虽然很容易理解，但聚类是困难的，因为它缺乏理论基础，并且其搜索空间的增长速度超过指数增长（即使对于非常小的大小，也不可能使用蛮力直接后果是聚类算法是固定先验的近似，例如，的集群。最流行的方法之一是期望最大化（EM），最初是为估算缺失值而开发的EM假设固定数量的聚类（或质心），2352-7110/©2021作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxParichit Sharma、Hasan Kurban和Mehmet Dalkilic软件X 17（2022）1009442×∗≤≤∗∗∗∗事实上，它们是概率分布（PDF）。该技术迭代地找到PDF的参数的期望值和属于每个PDF的数据的概率收敛是这些值的对数概率。不幸的是，在大数据时代（数量，多样性，速度），EM无法扩展。我们注意到，“大数据”没有正式的定义。相反，这是一个共识，现在数据以多种方式存在，对传统的人工智能算法构成了挑战，其中许多算法已经有几十年的历史了。作为我们工作的一个例子[5]，在D. melanogaster有25K个节点。有O（9）。8 1021）长度为5的路径，这在生物学上很小，但在计算上很大。为了使EM现代化，我们利用以数据为中心的方法：数据应该在迭代发生时直接驱动和影响算法。观察到在一些迭代算法中，数据可以根据它如何影响目标函数来分离[6]。当EM迭代时，我们忽略不影响目标函数的数据（低表达数据），而使用影响目标函数的数据（高表达数据）。我们插入捕获LE+HE区域的数据结构，在使用HE或LE+HE之间交替对应于期望和最大化。数据的重建和插入都非常有效。我们选择R [7]，因为它是开源的，有一个活跃的社区，并且是数据分析中使用最广泛的语言/平台之一。1.1. 深入了解DCEMEM-T（我们使用EM-T的一个特别流行的用途是用于软聚类，其中每个数据与所有质心相关联。在聚类中使用EM-T假设每个数据来自一个特定的概率分布-最简单的方法是假设正态分布。为了将数据分配给聚类，通过最大化对数似然函数来迭代地更新每个聚类的每个概率分布的参数值。当数据点停止在聚类之间移动时，EM-T收敛-换句话说，概率稳定。为了与历史使用保持一致，DCEM包括EM-T的原始实现和我们的以数据为中心的扩展EM*（EM-star）。应该注意的是，实际上，EM-T算法有许多稍微不同的版本。我们选择了[12]这个包。此外，我们包括一个改进的播种方法。1.2. 相关工作CRAN有几个解决非监督学习和基于模型的聚类问题的软件包虽然可以在CRAN任务视图[13]中访问一个简单的列表，但表1提供了基于功能的软件包比较（使用EM- T或其变体）：补充信息中还提供了对可用R软件包及其优点的全面讨论。尽管大多数软件包都为无监督聚类问题提供了定制的解决方案，但没有太多的重要工作致力于使EM-T与实际的大数据一起工作（如[14]中所讨论的）。1.3. 背景动机大数据，以及它现在与数据科学的流行领域的典型配对，暴露了迭代算法的一个明显弱点-而访问数据的运行时间是O（n），因为n通常会达到100 GB甚至几GB的大小表1MB是基于模型的聚类。相关CRAN软件包及其功能的列表作为（09/03/2021）。Pkg.Vrs.Clust./类密度测试MB平行mclust5.4.6Y/YYYN混合物1.5Y/YNYNRmixmod2.1.5Y/YYYN柔性混合2.3-15Y/NNYNEMCluster0.2-12Y/YNYNmixtools1.2.0Y/NYNNChaoterR1.2.2Y/YNNYDCEM（EM*）2.0.2Y/YNNNFig. 1. EM的执行过程，其中，EM是收敛阈值。(A)该软件包需要数据帧。(B)例如，指定的参数无效，数据中缺少/无效的值。(C)例如，空块，较少的模态数据比用户指定的要多。 (D)要么EM要么EM。 (E)埃隆·马斯克：检查是否为100。01（99%的叶子在堆中是相同的）或达到最大迭代次数。EM-T：检查是否达到最大收敛阈值或最大迭代次数。TB（以及在不久的将来的PB）以及规则地跨越100到1000个特征的维度，访问每个数据的操作使许多传统的迭代算法复杂化。为了弥补这一差距，我们设计并实现了DCEM，专门针对大数据--“高维度、大规模和不同领域”--进行有效工作。DCEM（EM）不仅大大提高了大数据的运行时间，而且在几乎所有情况下都达到了有竞争力的准确率[14]。2. 软件描述工作流DCEM被组织成模块化脚本，用于执行诸如从文件读取数据、预处理和清理数据、执行期望和最大化过程以及格式化输出数据等任务。包执行工作流的抽象视图在（图1）中给出。①的人。2.1. 封装特征结构DCEM为EM和EM-T算法提供了一个直观的界面，可以通过函数调用配置轻松自定义。它还支持高级初始化方案[15，16]，以加快收敛过程。为了进一步提高性能，代码向量化被广泛用于矩阵计算，堆创建和初始化的例程在Rcpp中实现[17]-原始Python代码中缺乏的功能。要开始使用该包，用户可以通过R控制台直接访问帮助和文档。此外，详细的代码示例，各种用例和API包的全面解释也可以在用户手册[18]和补充快速入门文档中找到。Parichit Sharma、Hasan Kurban和Mehmet Dalkilic软件X 17（2022）1009443∗∗∗图二. 在执行时间和迭代的情况下，对于除了k=2之外的所有k值，EM迭代都明显优于EM-T（其中EM-T略好）。准确度图显示，EM-T在k=10.25时稍好，而EMT在k=10.20时更好，并且两种算法在k>20时的性能相似3. 说明性实例在[14]中给出了使用旧Python代码在各种真实和合成数据集上的EM和EM-T的比较。在这里，我们通过对环范数数据进行基准测试来说明DCEM的实用性[19]，并将比较扩展到大数据上选择性R包（补充资料中提供了其他基准）。 结果（图） 2）证明EM在执行时间和迭代次数方面优于EM-T，同时保持甚至提高准确性。如表1所述，CRAN有许多软件以某种方式使用EM-T，但并非所有软件都提供EM-T。T作为主要例程或专注于扩展EM-T以处理大数据;因此，我们选择了以下包进行比较：（1）通过使用预定义模型，不对数据的特定属性（分布的形状，体积或方向）施加限制，（2）提供集成（组合E和M步骤）API以直接调用EM算法，（3）支持随机初始化，以及（4）用R语言实现E和M步骤。我们只剩下检查EMCluster[20]和mixtools[21]。实验结果如图所示。 3和图 四、为了在合理的时间内获得结果，我们对所有算法设置了2小时的时间限制，以防止它们运行很长时间，并且不会重复运行用户可以通过查阅补充信息来再现选择结果4. 影响结论聚类（或者更正式地说，分区）是理解数据的第一步。尽管最原始的分析，聚类没有统一的理论基础，而且很难处理。具有讽刺意味的是，理解数据的最明显的初始尝试是最困难的这具有约束的特征数、质心数和数据大小。DCEM建立在以数据为中心的数据表达原则之上，该原则捕获了数据价值在迭代优化问题中重新访问时的变化。我们确定了一个色域的数据表现力从低（LE）到高（HE），影响目标函数或多或少，分别。我们发现，堆具有相关的表达区域，我们称之为强（LE数据）和弱（HE数据）。通过有时忽略强区域，我们忽略了显着更少的数据[23]。自发布以来（2018年9月），DCEM已被下载18，000次（图1，补充信息），这也表明其在更广泛的开源社区中的受欢迎程度。我们认为，下载的数量与科学家研究更大数据量的成功有关。我们证明了，与现有的软件相比，显着的改进，在运行时间和迭代次数的DCEM实现的数据复杂性（大小，尺寸和集群）超过一定的限制。总之，DCEM是一个独立于领域的程序，可以用作（1）一个用于聚类的独立程序(2) 一个即插即用的组件被合并到现有的软件中，更像是对现有EM-T实现的补充，以加快参数估计。DCEM为EM-T（广泛用于多个领域[24-26 ]）和EM（EM-T的扩展）提供了开源实现DCEM可以加速科学发现过程，Parichit Sharma、Hasan Kurban和Mehmet Dalkilic软件X 17（2022）1009444∼图三. 大量集群的比较：在训练时间方面，DCEM明显快于EMCluster和mixtools。DCEM需要的迭代次数比EMCluster少，未报告mixtools的迭代次数，因为它无法在2 h的阈值内收敛[22]第22话，我的世界见图4。 大数据比较：DCEM始终收敛（33分钟，200万个点），而EMCluster和mixtools未能在2小时的时间限制内收敛。没有报告mixtools和EMCluster的迭代次数，因为它们无法对所有n值收敛。创建的图ggplot2 [22].对于无监督聚类，也可以通过[2，27]中的大量实验来说明。CRediT作者贡献声明Parichit Sharma：方法论，软件，验证，调查，写作-原始草稿，写作-审查编辑，可视化，项目管理。哈桑·库尔班：方法论，调查，验证，写作-评论编辑，可视化，监督。Mehmet Dalkilic：概念化，写作竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作确认作者感谢Rob Henderson（计算机科学系）提供的技术支持，他帮助部署了这项工作的系统基础设施。附录A. 补充数据与本文相关的补充材料可以在https://doi.org/10.1016/j.softx.2021.100944上找到。引用[1]费曼河物理学前沿（Frontiers in Physics）第1版CRCPress;2000.[2]库尔班河一种新的方法来优化堆结构上的迭代机器学习算法（博士学位）。论文），印第安纳大学; 2017年。[3]Kurban H，Sharma P，DalkilicM.数据表现力和其用于数据中心人工智能，数据为中心AI车间，第35神经信息处理系统会议（NeurIPS2021），澳大利亚悉尼，https://datacentricai.org/papers/145_CameraReady_Poster_DCAI_DataExpressiveness_2021.pdf。[4] 以 数 据 为 中 心 的 人 工 智 能 NeurIPS; 2021 年 ， URLhttp ：//www.cnentricai。org/.[5]科斯特洛JC，Dalkilic MM，Beason SM，Gehlhausen JR，Patwardhan R，Mid-dha S，Eads BD，Andrews JR。果蝇的基因网络：整合实验数据预测基因功能。Genome Biol2009;10（9）：1-29.[6]沃尔珀特DH。普适研讨会：进化计算和生命的过程：没有免费的午餐定理的真正含义：如何改进搜索算法。Ubiquity2013;2013（December）：1-15.Parichit Sharma、Hasan Kurban和Mehmet Dalkilic软件X 17（2022）1009445[7] RCore团队。R：统计计算的语言和环境。奥地利维也纳：R Foundation forStatistical Computing; 2021，URLhttps：//www.R-project.org/网站。[8] 放大图片作者：A.通过EM算法从不完整数据中获得最大似然。J R Stat Soc SerB Stat Methodol1977;39（1）：1-22.[9] Yuille A，Stolorz P，Utans J. Statistical physics，mixtures of distribution，andthe EM algorithm. 神经计算1994;6（2）：334[10]放大图片作者：John M.混合高斯模型EM算法的收敛性质。神经计算1996;8（1）：129-51.[11]Roweis S ， Ghahramani Z. 线 性 高 斯 模 型 的 统 一 审 查 。 神 经 计 算 1999;11（2）：305-45.[12]Zaki MJ，Meira Jr. W，Meira W.数据挖掘与分析：基本概念和算法。剑桥大学出版社; 2014.[13]Leisch F GB. CRAN 任 务 视 图 ： 聚 类 分 析 有 限 混 合 模 型 。 2012 年 ，URLhttp://CRAN.R-project.org/view=Cluster。[14]Kurban H ， Jenne M ， Dalkilic M. 使 用 数 据 构 建 更 好 的 EM ： EM*forBigData。Int J Data Sci Anal 2017;4（2）：83[15]Bahmani B，Moseley B，Vattani A，Kumar R，Vassilvitskii S.可扩展的k-means++。Proc Very Large Data Bases Endow（PVLDB）2012;5（7）：622[16]Arthur D，Vassilvitskii S. K-means++：谨慎播种的优势。在：第十八届年度ACM-SIAM离散算法研讨会论文集。SODA '07，USA：Society for Industrialand Applied Mathematics; 2007，p. 1027-35[17] Eddelbuettel D，Balamuta JJ.用extitC++扩展extitr：Rcpp简介。PeerJ预印本2017;5：e3188v1。http://dx.doi.org/10的网站。7287/peerj.preprints.3188v1.[18]Sharma P.使用期望最大化星（EM*）算法对大数据进行聚类。CRAN; 2019，URLhttps://cran.r-project.org/web/packages/DCEM/DCEM.pdf。[19]布 雷 曼 湖 偏 差 、 方 差 和 电 弧 分 类 器 。 1996 年 ， URL https ： //www.stat.berkeley.edu/~breiman/arcall96.pdf网站。[20]W.C. C，R。M. EMCluster：EM算法，用于有限混合高斯分布的基于模型的聚类。2015年，URLhttp://cran.r-project.org/package=EMCluster。[21]张文辉，张文辉，张文辉. Mixtools：一个R包用于分析有限混合模型。J StatSoftw 2009;32（6）：1http://www.jstatsoft.org/v32/i06/[22]威克姆·H Ggplot2：用于数据分析的优雅图形。Springer-Verlag New York;2016，URLhttps://ggplot2.tidyverse.org。[23] Kurban H ， Dalkilic M. A novel approach to optimization of iterativemachine learning algorithms：Over heap structures.在：2017年电气和电子 工 程 师 协 会 ， 大 数 据 国 际 会 议 （ 大 数 据 ） 。 2017 ， p. 102-9.http://dx.doi.org/10.1109/BigData.2017.8257917网站。[24]Do C，Batzoglou S.什么是期望最大化算法？自然生物技术2008;26（8）：897-9.[25]Jung Y，Kang M，Heo J.使用K-means和期望最大化算法的聚类性能比较。Biotechnol Biotechnol Equip2014;28（sup1）：S44-8.[26]放大图片作者：Kristan T. EM算法及其扩展第382卷，JohnWiley& Sons;2007年。[27]Kurban H，Kockan C，Jenne M，Dalkilic MM。案例研究：使用EM聚类大恒星数据。在：第四届IEEE/ACM大数据计算，应用和技术国际会议论文集;2017年。第271-2页。
我的内容管理
展开
