基于无监督算法的紧急市场聚类快速检测

2022-5-6 00:20:39

基于无监督并行遗传算法Dieter-Hendricks的紧急市场聚类快速检测*, 蒂姆·格比（Tim Gebbie），戴安·威尔科克斯（Diane Wilcox）计算和应用数学学院，威特沃特斯兰大学约翰内斯堡分校，威茨2050，南非*电子邮件：迪特。hendricks@students.wits.ac.zaAbstractWe采用主从并行遗传算法（PGA）和定制的对数似然函数来识别价格演变中的紧急聚类。我们使用图形处理单元（GPU）实现PGA，并使用不相交的最小生成树（MST）将结果可视化。我们证明，我们的GPU PGA在商用通用GPU上实现，能够基于南非市场的一部分股票以亚秒的速度恢复股票集群。这代表了低成本、可扩展并行计算的实用选择，并且比基于优化C的第四代编程语言中的原型串行实现要快得多，尽管由于编译器的差异，结果无法直接比较。结合基于高频数据的快速在线日内相关矩阵估计聚类识别，拟议的实施为金融从业者提供了成本效益高、近实时的风险评估。关键词：无监督聚类、遗传算法、并行算法、金融数据处理、最大似然聚类1。引言支持多个领域的技术进步提高了生成和存储与领域进程相关的数据和元数据的能力。数据科学领域正在不断发展，以应对从这些大型数据集中收集见解的挑战，对解决组合优化问题的精确算法、启发式和元启发式进行了广泛研究。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:20:42

使用精确方法的主要优点是保证找到问题的全局最优解。然而，在解决复杂（NP难）问题时，一个缺点是执行时间的指数增长与问题实例的大小成正比[23]。启发式似乎很有效，但解决方案的质量无法保证，而且技术往往不是万能的[9]。元启发式试图整合这两种方法，并在合理的时间范围内提供可接受的解决方案。文献中存在大量用于解决复杂问题的元启发式算法，遗传算法（GA）已成为一种突出的技术，它使用密集的全局搜索启发式算法，智能地探索搜索空间来解决优化问题。虽然算法必须穿越大空间，但计算密集型计算可以独立执行。Compute Unified Device Architecture（CUDA）是NVIDIAS并行计算平台，非常适合于任何计算任务，尤其是在可能实现数据并行的情况下。使用该平台实现遗传算法对海量数据集进行聚类分析，可以相对快速地挖掘数据，并且只需花费大型数据中心或计算网格的一小部分成本。许多作者考虑了并行架构来加速气体（参见[35,11,18,31,32,5,4,20]作为示例）。虽然[20]的工作在概念上与本文提出的实现类似，但一个关键区别在于我们对聚类方案的适应性函数的选择。Giada和Marsili基于最大似然原理，提出了一种无监督、无参数的数据聚类方法[16]。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:20:45

他们推导出一个对数似然函数，其中可以评估给定的聚类配置，以确定它是否代表数据集的固有结构：接近最大对数似然的聚类配置更能代表数据结构。因此，这种对数似然函数是GA实现中的适应性函数的自然候选函数，在GA实现中，种群不断进化以产生最大对数似然的集群配置。最佳聚类数是一个自由参数，与传统技术不同，传统技术需要预先指定聚类数。虽然已经考虑了无监督方法（参见[30]和其中的参考文献），但Giada和Marsili方法的优势在于，它对这里探讨的应用领域中的聚类有一个自然的解释。通过监测金融工具的日内聚集，可以更好地了解市场特征和系统性风险。虽然遗传算法为识别此类集群提供了一种通用方法，但串行实现需要大量计算，可能需要很长时间才能收敛到最佳近似值。在本文中，我们介绍了一个可维护和可扩展的主从并行遗传算法（PGA）框架，用于CUDA平台上的无监督聚类分析，该框架能够使用Giada和Marsili似然函数检测聚类。通过应用所提出的聚类分析方法并检查金融工具的聚类行为，这为近实时监测股市的日内特征和检测结构变化提供了独特的视角。本文提出的新实现基于Cieslakiewicz的贡献[7]。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-5-6 00:20:49

虽然本文提供了该算法的概述和特定用例，但作者正在研究伴随参数调整、性能可扩展性以及不同股票宇宙大小和集群类型对解决方案质量的影响。本文的工作如下：第2节介绍了聚类分析，重点介绍了Giada和Marsili[15]提出的最大似然法。第3节讨论主从PGA。第4节讨论CUDA计算平台和我们的具体实现。第5节在总结第6.2节之前讨论了该分析的数据和结果。聚类分析聚类分析根据描述对象或其关联的元数据对对象进行分组[13]。目标是确保一个群体中的对象具有相似的特征，并且与其他群体中的对象无关。一个群体内的同质性越大，群体间的异质性越大，集群效应越明显。为了隔离相似对象的集群，需要使用能够高效恢复固有结构的数据集群方法。2.1. 相似性的相关性度量相关性度量是一种通过使用数据点之间的统计相关性来标准化数据的方法。相关性表示两个数据点之间关系的方向（正或负）和程度或强度。衡量数据点之间关系的最常见的相关系数是Pearson相关系数，它只对数据点之间的线性关系敏感。在完全正线性关系的情况下，皮尔逊相关系数为+1；在完全负线性关系的情况下，皮尔逊相关系数为-1；在所有其他情况下，皮尔逊相关系数的某些值介于1和+1之间，接近0表示相互依赖性可忽略不计。2.2.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-5-6 00:20:53

聚类过程任何特定的聚类过程都需要优化某种标准，例如最小化簇内差异或最大化对象或簇之间的距离。2.2.1. 基于最大似然原理的聚类分析最大似然估计是一种估计统计模型参数的方法。另一方面，数据聚类处理的是对一组N个对象或簇进行分类或归类的问题，因此agroup或簇中的对象比属于不同组的对象更相似。如果每个对象由D个测量值识别，那么一个对象可以表示为一个元组，\'xi=（x（1）i。。。，x（n）i），i=1。。。，D维空间中的N。数据聚类将尝试将聚类识别为该向量空间中人口更密集的区域。因此，集群的配置由一组S={si，…，sN}整数标签表示，其中侧注对象i所属的集群，N是对象的数量[16]（如果si=sj=S，则对象i和对象j位于同一个集群中），如果位于1到M和M=N的值上，则每个集群都是仅构成一个对象的单一集群。2.2.2. 与Potts modelOne类似，可以直接将q态Potts Model的超顺磁排序应用于簇识别[3]。在市场模型中，每只股票都可以呈现q状态，每种状态都可以由一组相似的股票来表示[3,22,15]。集群成员资格表明集群成员之间存在一些共性。每只股票都有一个作为其所处状态函数的动态分量，以及一个受股票特定噪声影响的动态分量。此外，可能存在影响所有股票的全球耦合，即。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

点击查看更多内容…

mingdashike22

2022-5-6 00:20:57

代表市场模式的外部领域。在超顺磁聚类方法中，成本函数可以被视为哈密顿量，其低能量状态对应于与数据样本最兼容的聚类结构。然后，用S={si}Ni=1的聚类指数si来识别结构，该指数代表第i个对象所属的聚类。这使得oneto能够在Potts模型哈密顿量中解释sias Potts自旋，并随物体之间的距离而减小[3,22]。哈密顿量的形式为：Hg=-Xsi，sj∈SJi jδ（si，sj）-βXihMisi，（1）其中自旋可以呈现q态，外部磁场由hMi给出。第一项代表共同的内部影响，第二项代表外部影响。在整理数据时，我们忽略了第二个术语，因为我们在后面的章节中讨论信息和风险以及这些因素对价格变化的影响时，会直接将共享因素包括在内。在Potts模型方法中，可以认为耦合参数Ji jas是相关系数的函数[22,15]。这用于指定随着对象之间的距离而减小的距离函数。如果所有的自旋都是以这种方式关联的，那么每对自旋都是通过某种非消失耦合Ji j=Ji j（ci j）连接的。在这个模型中，只有一个集群的情况可以被认为是基态。随着系统变得更加兴奋，它可能会分裂成更多的簇，每个簇都会有特定的磁感应，即使整个系统的净磁化可能保持为零。一般来说，这种相关性将是时间和温度的函数，以便将簇的演化以及簇的层次结构编码为温度的函数。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-5-6 00:21:04

（3）变量δ是狄拉克δ函数，h。。。我表示数学期望。对于给定的簇结构S，当参数Gs取数值Gs时，其亲和力最大*s=qcs-NSN-ns对于ns>1,0对于ns≤ 1.（4）等式4中的数量表示对象的数量，包括s，即ns=NXi=1δsi，s。（5）变量Csi是sthcluster的内部相关性，由以下等式表示：cs=NXi=1NXj=1Ci，jδsi，sδsj，s。（6）变量Ci，jis数据的皮尔逊相关系数，由以下等式表示：Ci，j=’xi xi xjqk’’xikk’’xjk。（7）结构S的最大可能性可以写成asP（G）*, S|xi）∝ expDL（见[34]），其中每个特征LCI的结果似然函数用byLc（S）表示=Xs:ns>1lognscs+（ns- 1） logns- NSN- 反恐精英！。（8）从等式8可以看出，对于不相关的对象簇，Lc=0，即*对于所有ClusterIndex（ns=1），当对象被分组为单态集群时，S=0或cs=nsor。等式8表明，S的最大似然函数取决于皮尔逊相关系数Ci，因此与传统聚类方法相比，jand表现出以下优势：o它是无监督的：最佳聚类数是先验未知的，在一开始就不确定o结果的解释在模型方面是透明的，即方程式2。Giada和Marsili指出，maxsLc（S）提供了一种测量集群结构固有结构的方法，该集群结构由集合S={S，…，sn}[16]表示。值越高，结构越明显。3.

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:08

并行遗传算法为了定位金融数据中的标准化股票收益率集群，Giada和Marsili使用了模拟退火算法[15,16]，其中-LCA是将对数似然函数应用于真实世界数据集以证实其方法的成本函数。然后将其与其他聚类算法进行比较，如K-均值、单链接、质心链接、平均链接、合并和确定性最大化[16]。Mbambiso等人利用模拟退火算法的串行实现（见[24]和[14]），成功地将该技术应用于南非金融数据。模拟退火和确定性最大化为最大似然结构提供了可接受的近似值，但计算成本固有。我们提倡使用PGA作为一种可行的方法来近似最大似然结构。Lc将被用作能力函数，PGA算法将被用于确定Lc的最大值，以便有效地隔离不相关财务数据的集群。3.1. 遗传算法原理和遗传算子遗传算法的主要优点之一是概念简单。核心算法可以概括为以下步骤：初始化种群、进化个体、评估能力、选择个体存活到下一代。GAs具有广泛适用性的特点[33]，因为它们可以应用于任何问题，其解域可以通过需要优化的函数量化。在繁殖过程中，特定的遗传算子被应用到父母身上，然后产生后代。遗传算子可分为以下几类：选择：选择的目的是在群体中分离出更好的个体，并允许它们传播，以产生具有更高适应性值的新的结果。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:11

实现了随机通用抽样选择算子，个体被映射到一条直线上与其适应性值成比例的连续段[2]。然后通过均匀间隔的采样线选择个体。虽然更好的个体被选中的概率更高，但这种技术提高了较弱个体被选中的可能性，允许多样性进入群体，并降低收敛到局部最优的概率。交叉：交叉是两个个体交配的过程，期望它们能产生更好的弹簧[33]。交叉遗传操作包括选择随机位点，在两条父染色体内标记一个交叉位点，将基因复制到另一条染色体上。为我们的实现[7]开发了一个基于bespokeknowledge的交叉算子，以整合领域知识并提高收敛速度。变异：变异是候选解集或搜索空间多样性的关键驱动因素[33]。它通常在交叉后应用，旨在确保遗传信息随机分布，防止算法陷入局部极小。它通过随机修改一些构建块在种群中引入新的遗传结构，并使算法能够全局遍历搜索空间。精英主义：科利指出，能力比例选择并不一定有利于选择任何特定的个人，即使是被测试者[8]。因此，被测试的个体可能无法在进化周期中存活。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

mingdashike22

2022-5-6 00:21:14

精英主义是通过对下一代的固有提升来保护被测试个体的过程，而不经历任何交叉或突变的遗传转化[33]。替换：替换是任何进化周期的最后阶段，算法需要用新成员替换当前种群中的旧成员[33]。这一机制确保了种群规模保持不变，而每一代中最脆弱的个体则会减少。虽然GAs对于解决复杂问题非常有效，但不幸的是，由于搜索空间的遍历，长时间执行可能会影响这种积极特性。GAs适合于并行化，前提是每个候选解决方案的适配度值可以独立确定。虽然文献中提出了许多方案来实现这种并行化（参见[17]、[33]和[31]），但我们选择了实现主从模式。3.2. 主从并行主从气体，也称为全局PGA，涉及单个群体，但分布在多个处理单元中，用于确定适合度值和遗传算子的后续应用。它们允许在共享内存处理实体或任何类型的分布式系统拓扑上进行计算，例如网格计算[31]。Ismail总结了主从式PGA的主要功能[17]：该算法使用单一总体（由主从存储）和并行执行的所有个体的适应性评估（由从机执行）。只有当每个奴隶接收个体（或个体子集）进行评估时，以及奴隶返回适应性值时，通信才会发生，有时是在应用了给定可能性的变异后。我们实现的特定算法是同步的，即。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:18

在进行选择和突变之前，宿主会等待，直到它收到群体中所有个体的fitnessValue。因此，同步主从式遗传算法具有与传统遗传算法相同的特性，只是可以快速评估种群的适应性。该算法相对容易实现，如果通信成本不占计算成本的主导地位，则可以预期显著的加速。整个过程必须等待最慢的处理器完成其能力评估，直到可以应用选择运算符。许多作者已经使用消息解析接口（MPI）范例来实现主从PGA。Digalakis和Margaritis实现了一种同步MPI PGA和共享内存PGA，通过这种方式，能力计算是并行的，其他遗传算子仅由主节点应用[12]。它们展示了一种计算速度，在较大的总体规模下，计算速度与处理器数量成线性关系。Zhang等人使用集中控制岛模型将遗传算子同时应用于子群体，并使用子群体中的精英个体定制迁移策略[41]。Nan等人使用MATLAB并行计算和分布式计算工具箱开发了主从PGA[25]，展示了它在使用集群计算配置时对图像配准问题的有效性。在我们的实现中，我们利用英伟达CUDAplatform，通过使用图形处理单元（GPU）流式多处理器（SM）组件和CPU作为主处理器来实现大规模并行。计算平台与实现Compute Unified Device Architecture（CUDA）是英伟达GPU上大规模并行高性能计算的Nvidiasplatform。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:21

Compute Unified Device Architecture（CUDA）是英伟达GPU上大规模并行高性能计算的Nvidias平台。其核心是三个关键的抽象：线程组的层次结构、共享内存和障碍同步。此处省略了有关执行环境、线程层次结构、内存层次结构和读取同步方案的全部细节，但请读者参阅Nvidia技术文档[27,28]进行全面讨论。4.1. 特定的计算环境CUDA算法和相应的测试工具是使用Microsoft Visual Studio 2012 Professional开发的，带有针对CUDA-c项目的英伟达Nsight扩展。测试了以下配置，以确定CUDA群集算法在以下体系结构上的多功能性：我们有机会测试两个候选图形环境配置框架Windows 7 Professional Service Pack 1（64位），CUDA 5.5GTX CUDA Intel Core i7-4770KCPU@3.5GHz，32GB内存，（并行）Nvidia GTX Titan Black带6GB内存，CC:3.0，SM:3.5Windows 7 Professional Service Pack 1（64位），MATLABGTX MATLAB Intel Core i7-4770KCPU@3.5GHz，32GB内存，2013aNvidia GTX Titan Black带6GB内存，（串行）CC:3.0，SM:3.5Windows 7 Professional Service Pack 1（64位），CUDA 5.5TESLA CUDA Intel Core i7-X980CPU@3.33GHz，24GB内存，（并行）Nvidia TESLA C2050，带2.5GB内存，CC:2.0，SM:2.0Windows 7专业服务包1（64位），MATLABTESLA MATLAB Intel Core i7-X980CPU@3.33GHz，24GB RAM，2013NVIDIA TESLA C2050，2.5GB RAM，（串行）CC:2.0，SM:2.0表1：开发、测试和基准测试环境用于算法实现的ICS卡：英伟达GTXTitan Black和英伟达TESLA C2050。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:25

这两种卡都提供了双精度计算和可比数量的UDA核和TFLOP（每秒的tera浮点运算），但GTX卡比TESLA卡便宜得多。其主要原因是特斯拉卡上使用了ECC（错误检查和纠正）存储器，存在额外的存储器位来检测和校正存储器错误[1]。ECC内存的存在确保了特斯拉卡生成结果的一致性，这对于严格的科学计算至关重要。在进一步调查中，作者将探索GTX卡生成的解决方案质量的一致性，以及由此产生的误差是否足够小，足以证明与特斯拉卡相比节省了成本。4.2. 实施本研究考虑了以下目标：1）使用一组预先定义的40个模拟股票，以4个不同的不相交集群为特征，调查并调整PGA实施的行为；2）识别真实世界数据集中的集群，即。股票价格的高频演化；3）测试GPU环境的效率。4.2.1. 我们使用基于整数的编码来表示遗传算法中的个体，即个体=S={S，S，…，si-1，是的。。。，sN}（9），其中si=1。。。，K和i=1。。。，这里是我所属的星团。就toGAs相关术语而言，这意味着ithgene表示ithobject或asset所属的集群。对象或资产的数量不多，因此为了允许全单态配置的可能性，我们将K=N。这种表示由Gebbie等人在其系列GA中实现，并在本研究中采用[14]。4.2.2。适应度函数Giada和Marsili最大对数似然函数Lc，如等式8所示，用作适应度函数。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:28

这用于确定群集配置是否代表数据集的固有结构，即它将用于检测GA是否收敛到测试个体，这将代表数据集中相关资产或对象的群集配置。4.2.3. 主从式PGA实现Gebbie、Wilcox和Mbambiso[14]对Likelihood函数的未经分析的MATLAB GA实现是一个起点。为了最大限度地提高遗传算法的性能，CUDA框架将遗传算子的应用和适应性函数的评估并行化[7]。这里是一个总结性的论述。重点是将尽可能多的GA执行外包给GPU，并尽可能广泛地使用GPU内存[40]。主从式PGA使用单一群体，个体评估和遗传算子的成功应用并行进行。全局并行化模型不预测任何有关底层计算机架构的内容，因此它可以在共享内存和分布式内存模型平台上高效地实现[33]。通过将这些任务委托给GPU并广泛使用GPU内存，这将最大限度地减少主机和设备之间的数据传输。这些传输的带宽明显低于共享或全局内存与GPU上执行的内核之间的数据传输。对[14]中的算法进行了修改，以最大限度地提高主从PGA的性能，并对主节点（CPU）进行了明确区分，CPU通过为从节点（GPU流式多处理器）执行的GA操作发出命令来控制进化过程。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:32

实现的算法的伪代码如算法1所示。算法1用于集群识别的主从PGA初始化进化生态系统大小线程块和网格以在GPU上实现最大的并行性：创建初始填充，而在GPU上为TRUE doON：评估所有个体的适用性在GPU上：评估状态和统计GPU：确定是否满足终止标准如果是，则终止算法；在循环时退出；elseContinueend If on GPU:隔离测试个体on GPU:Apply elitismON GPU:Apply scalingON GPU:Apply genetic operator:selectionON GPU:Apply genetic operator:crossoverON GPU:Apply genetic operator:Transoveron GPU:Apply genetic operator:Mutation on GPU:Apply replacement（新一代创建）end whiler Report on Results Clean up（在GPU/CPU上释放内存；释放设备）以实现数据并行性并利用在CUDAthread层次结构中，我们将单个基因映射到二维网格上。使用等式9所示的表示法，假设人口为400人和18只股票：个体={1,2,4,5,7，…，6}个体={9,2,1,1,1，…，2}个体={3,1,3,4,6，…，2}。。。个体={8,1,9,8,7，…，3}将被映射到网格单元，如图1所示。数据网格单元映射到线程，其中每个线程执行一个内核，在相应的XY坐标下处理数据单元。图1：个体到CUDA线程层次的映射鉴于本次调查中使用的硬件（见表1），表2概述了个体基因到线程的所选映射对允许种群范围和种群规模的限制。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-6 00:21:35

对于较大的问题，选择32的螺纹块尺寸，因为这可以确保允许的总体尺寸大于集群中的库存数量。图形卡Nvidia GTX Titan Black Nvidia Tesla C2050计算能力3.5 2.0SMs 15 14最大线程/线程块1024 1024线程块尺寸32最大线程块/多处理器16 8最大库存数量3840 3584最大总体大小17 472 18 720表2：库存数量和总体大小限制。对于特斯拉卡，最大库存数量=（14）* (1024/32) * 8=3584，最大人口规模=（65535/（3584/32））* 32 = 18720.我们注意到，算法的效率可能会在表2中列出的物理限制附近受到影响，因为CUDA内存层次结构将迫使线程更频繁地访问高延迟全局内存库。然而，对于我们在本文中考虑的特定领域问题，约翰内斯堡证券交易所在其主板上由大约400家上市公司组成，这代表了本地聚类分析中感兴趣的股票数量的上限。这在算法的物理限制范围内，同时仍然提供了将应用程序扩展到多个市场的范围。[7].4.2.4中给出了完整实现的详细信息，以及关于初始化、块大小和每个块的线程的具体选择。关键实施挑战CUDA编程中的一个关键挑战是适应单程序多数据（SPMD）范式，其中单个程序的多个实例使用唯一的功能集来操作数据块的部分[10]。这种体系结构适合数据并行，而任务并行需要特殊的功能。此外，由于每个warp（由32个线程组成的组）在单个SPMD处理器上执行，warp中的不同线程会严重影响性能。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:40

为了利用多处理器中的所有处理元素，使用一条指令来处理来自每个线程的数据。但是，如果一个线程由于条件分歧需要执行不同的指令，那么所有其他线程必须有效地等待，直到分歧线程重新连接它们。因此，分歧会强制执行顺序线程，从而抵消SPMD处理带来的巨大好处。CUDA内存层次结构包含许多sharedmemory Bank，它们充当线程块中线程的公共数据缓存。为了实现完全吞吐量，每个线程必须访问不同的存储库，并避免存储库冲突，这将导致额外的内存请求和效率降低。在我们的实现中，通过使用填充避免了银行冲突，共享内存中填充了一个外部元素，使得相邻元素存储在不同的银行中[6]。CUDA通过syncthreads（）barrier函数为线程块内的线程同步提供了一种简单而高效的机制，但是在内核执行期间不直接支持块间通信。考虑到遗传算子只能在计算整个种群的适应度后应用，因此有必要将线程块与适应度计算操作同步。我们实现了CPU隐式同步方案[39,29]。由于内核启动是异步的，连续的内核启动是流水线的，因此执行与前一次启动隐式同步，第一次内核启动除外。考虑到CPU和GPU之间的通话延迟，以及由此带来的性能拖累，我们探索了GPU同步方案，以实现所需的中间块通信。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:43

特别是，考虑了GPU简单同步、基于GPU树的同步和GPU无锁同步[39]。最终，GPU同步方案对我们的特定问题限制太大，因为线程块的数量上限等于GPU卡上SMU的数量。如果线程块的数量大于卡上SMs的数量，执行可能会死锁。这可能是由GPU的扭曲调度行为造成的，即驻留在SM上的活动线程块可能会保持忙碌等待状态，等待未调度的线程块到达同步点。虽然这种方案对于较小的问题可能更有效，但出于相对可伸缩性的考虑，我们选择了CPU同步方案。4.2.5. 数据预处理为了生成N股相关矩阵，以证明该算法在真实测试数据上的可行性，在使用零阶保持插值处理缺失数据的数据上计算数据相关性[37]。使用Giada和Marsili[15]提出的方法，使用递归平均算法，消除了市场模式。然后使用迭代的非线性指数加权移动平均（EWMA）滤波器计算协方差矩阵，默认遗忘因子λ=0.98。相关矩阵由协方差矩阵计算得出，并用随机矩阵理论方法进行清理。特别是，通过以轨迹保留方式消除Wishart范围内的特征值，减少了高斯噪声影响[37]。这增强了聚类，提高了相关矩阵估计序列的稳定性。4.2.6. 数据后处理计算的群集配置从CUDAoutput文件中读取。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-6 00:21:46

接着，通过使用相关矩阵中的数据值，结合各自数据集的计算聚类配置，构造邻接矩阵。然后利用邻接矩阵构造一组不相交的最小生成树（MST），每棵树捕捉每个簇的互连性。每个MST都展示了一个新的标签- 1边，以边的权重之和最小的方式连接簇的NSStock。Kruskal的算法用于生成MST，它描述了高度相关股票之间的联系，提供了不相交聚类结果集的图形可视化[21]。数据和结果5。数据本次调查使用了两组数据：训练集和测试集。训练集由40只股票的模拟时间序列组成，这些股票表现出已知的不同、不相交的聚类。利用这些诱导簇的恢复来调整PGA参数。测试集包括从2012年9月28日到2012年10月10日的实际股票报价中间价，总计为3分钟的条形图，即。每个股票大约有1800个数据点。根据交易量，选择的股票代表了该时期JSE上流动性最强的18只股票。对于这两个数据集，如第4.2.4节所述，从时间序列数据构建相关矩阵，作为聚类算法的输入。下面的测试集结果显示了18个JSEstocks的1760个相关矩阵的汇总统计数据。5.2. 结果我们在这里展示了一组结果样本。[7].5.2.1中给出了有关分析方面的进一步讨论。优化算法设置进行了各种调查，以确定PGA的最佳伴随参数。在每一种情况下，该算法都连续应用于训练集，具有已知的不相交聚类。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:49

设置是不同的，直到收敛速度最大化。一旦从训练集中确定了每个伴随参数的最佳值，就在测试集中部署了最佳算法配置。在进一步的研究中，作者将研究不同的伴随参数选择对不同股票宇宙大小的收敛速度和算法效率的影响。测试集上部署了以下PGA的最佳配置：，假设种群规模为1000：伴随参数值世代数400交叉概率（Pc）0.9变异概率（Pm）0.1错误容忍度0.00001高世代（Gstall）50精英规模10交叉算子基于知识的算子变异算子随机替换基于知识的交叉概率0.9表3：开发、测试和基准环境5。2.2. 基准计时结果表4说明了CUDA PGA实现与MATLAB串行GA相比的效率。MATLAB串行GA和CUDA PGA之间的直接比较可能会受到两个平台基本架构差异的影响。然而，我们立即观察到测试集clusteranalysis运行的性能显著提高了10-15倍。这可以归因于使用了并行计算平台、新型遗传算子和所采用的算法调整技术。在GTX平台上，CUDA PGA需要0.80秒来识别18只真实世界股票的单一相关矩阵中的剩余集群，展示其作为近实时风险评估工具的潜力。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

kedemingshi

2022-5-6 00:21:54

与特斯拉相比，GTX卡的核心速度、内存速度、内存容量和内存带宽相对更快，这很可能解释了GTX卡的优越性。尽管这可能证明使用更具成本效益的VEGTX卡是合理的，但目前尚不清楚，随着库存规模的增加，这种性能差异是否会持续，或者GTX卡是否能保持解决方案质量。我们注意到，与串行算法相比，性能改善的规模并不像获得亚秒计算时间的绝对结果那样重要。因此，CUDA PGA服务于近实时风险评估的目标，由此可以识别新兴股票集群行为中的有趣现象并采取行动，以缓解不利情景。这些结果的可扩展性有待于进一步研究，尤其是CUDA内存层次结构对计算时间的影响，因为全局内存访问增加。这些结果假设相关矩阵可以作为聚类分析算法的输入。为了开发一种稳健实用的近实时风险评估工具，进一步研究高频数据的计算效率相关估计是一个单独的问题。尽管结果令人鼓舞，但尚不清楚CUDA使用的PMD体系结构是否适合考虑的特定问题。跨线程块所需的数据依赖性限制了将总体基因分配给线程，并导致大量同步调用，以确保每一代的一致性。具有分布式能力计算和受控迁移的MPI岛模型是一个更适合的解决方案[36]，然而，需要考虑实现CUDA提供的等效加速所需的设置成本。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:21:57

这应该在进一步的研究中加以探讨。5.2.3. 真实世界测试集结果的解释在本节中，我们展示了从我们的模型生成的结果聚类配置的样本，用MST图形表示[24,7]。这是一个特定的领域应用程序，它提供了一个有意义解释的结果集群配置示例。连接节点的顶点的厚度表示股票之间的相关性强度。南非股市的特点通常是金融/工业股和资源股之间的行为差异，并与全球市场趋势紧密耦合。图2：早盘交易剩余集群（2012年9月28日09:03）在图2中，我们看到，由于市场开盘后的早盘交易模式，出现了4个不同的集群。最重要的是，6节点的金融/产业集群（SLM、SBK、ASA、SHF、GFI、OML）和3节点的资源集群（BIL、SOL、AGL）。从表面上看，这些配置是可以预期的，但我们注意到，黄金开采公司GFI出现在金融集群中，而银行公司FSR不出现在金融集群中。这些都是由于特质因素导致的个别股票短期脱钩行为的例子。图3：上午交易（英国开盘后）剩余集群（2012年9月28日10:21）图3说明了英国开盘对当地交易模式的影响。我们看到一个大型集群的明显出现，表明英国投资者的交易活动对当地市场产生了重大影响。在研究大型单一集群时，所有股票在美国和英国都有一级或二级上市。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:22:00

特别是，SAB和ANG在伦敦证券交易所（LSE）有二级上市，而BIL和AGL在伦敦证券交易所（LSE）有一级上市[19]。矿业公司Nagl和奢侈品公司CFR之间如此紧密的联系（相关性）也很少见。这可能是证据，表明英国在这2个股票中的大量交易可能会导致短期相关性升高，这可能没有意义或不可持续。图4：午盘交易剩余集群（2012年9月28日12:21）图4考虑了午盘交易模式。我们看到英国贸易的集群效应已经消散，出现了多点集群。正如我们所料，在英国市场开放后的两个小时内，CFR与AGLin脱钩。我们看到一个四节点的金融/产业集群（NPN、MTN、ASA、IMP）和四节点的资源集群（AGL、SAB、SOL、BIL）；矿业公司IMP出现在金融/产业集群中。图5：午后交易（美国公开市场后）剩余集群（2012年9月28日15:33）图5说明了美国公开市场对当地交易模式的影响。与我们在图3中观察到的类似，我们看到了一个大型单一集群的出现，其驱动力是成分股之间的短期相关性提高。这进一步证明，外国投资者在本地股票上的大量交易可能会对股市动态产生重大影响。环境框架基准中值时间最小时间最大时间GTX CUDA CUDA 5.5 18库存测试集（最优配置）0.80 0.73 3.17GTX MATLAB系列18库存测试集（最优配置）7.77 6.72 13.27TESLA CUDA CUDA 5.5 18库存测试集（最优配置）1.39 1.36 5.51 Tesla MATLAB系列18库存测试集（最优配置）15.91 13.41 26.22表4：基准计算速度结果6。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

可人4

2022-5-6 00:22:04

结论本文验证了Giada和Marsili[15]似然函数是一种可行的、可并行的方法，可用于在GPU平台上对数据集中的孤立类进行分析。与传统聚类方法相比，该方法的主要优点是：1）该方法无监督，2）结果的解释在模型方面是透明的。主从式PGA的实现表明，效率取决于各种算法设置。使用的变异算子类型对算法在搜索空间中分离最优解的效率有显著影响，而其他伴随参数设置主要影响收敛率。根据基准测试结果，UDA PGA实现比MATLAB中的串行GA实现运行速度快10-15倍，用于检测18个股票真实世界相关矩阵中的聚类。具体而言，当使用英伟达GTX Titan黑卡时，集群以亚秒的速度恢复，证明了算法的效率。如果可以从高频数据估计日内相关矩阵，这显著减少了计算时间，表明日内聚类识别对于金融从业者的近实时风险评估是可行的。检测集群异常和测量效应的持续性可以为金融从业者提供有用的信息，以支持当地的交易策略。从所示的样本结果来看，很明显，日内金融市场演变是动态的，反映了外生和内生的影响。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:22:07

聚类算法捕捉系统动力学的可解释和有意义特征的能力，以及其构造的一般性，表明该方法可以在其他领域获得成功。进一步的研究包括针对不同库存范围大小和集群类型的伴随参数调整和性能可扩展性，量化非ECC内存使用导致的GTX体系结构上解决方案质量的可变性，以及研究替代的成本效益并行方案。考虑到CUDA使用的SPMD架构，线程块之间所需的数据依赖性限制了群体基因对线程的分配，并导致大量同步调用，以确保每一代的一致性。具有分布式适应性计算和受控迁移的MPI岛模型可能是一种更适合探索的解决方案[36]，然而，实现CUDA提供的同等速度所需的安装成本应该是合理的。承认这项工作部分基于南非国家研究基金会（授权号87830、74223和70643）支持的研究。本文的结论应归于作者，NRF对此不承担任何责任。参考文献[1]先进的集群技术。HPC集群博客——GTX vsTesla。看见http://www.headachefreehpc.com/company-blog/hpc-clusterblog-gtx-vs-tesla.html了解更多细节。查阅日期：2014年9月25日。[2] 贝克。减少选择算法中的偏差和效率。第二届遗传算法及其应用国际会议记录，新泽西州希尔斯代尔，第14-21页，1987年。[3] M.布拉特、S.怀斯曼、E.多曼尼。数据的超顺磁性聚类。菲斯。牧师。莱特。，第76卷第18期，第3251-3254页，1996年。[4] C.博姆，R.诺尔，C.普兰特，B.瓦克斯鲁瑟。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:22:10

基于密度的群集化图形处理器。第18届ACM信息与知识管理会议记录，CIKM 09，ACM:纽约，第661-670页，2009年。[5] S.Brecheisen，H.P.Kriegel，M.Pfei FLE.复杂物体的平行密度聚类。Pakd，《计算机科学课堂讲稿》，德国，第3918卷，第179188页，2006年。[6] A.布罗德科布，T.哈根，M.塞特拉。图形处理单元（GPU）编程策略和GPU计算的发展趋势。《并行与分布式计算杂志》，第73卷，第4-13页，2012年。[7] D.Cieslakiewicz。在英伟达CUDA平台上使用并行遗传算法实现无监督资产聚类分析。维特沃特斯兰德大学硕士论文，2014年。[8] D.科利。为科学家和工程师介绍遗传算法。《世界科学》，1999年。[9] A.科洛尼、M.多里戈、F.马奥利、V.马尼埃佐、G.里基尼、M.特鲁宾。来自大自然的启发式算法，用于解决困难的组合优化问题。《运筹学国际交易》第3卷，第1-21页，1996年。[10] F.达雷马。SPMD模型：过去、现在和未来。并行虚拟机和消息传递接口的最新进展：第八届欧洲PVM/MPI用户组会议，2001年。[11] T.德塞尔，D.P.安德森，M.马格登·伊斯梅尔，H.纽伯格，B.K.西曼斯基，C.A.瓦雷拉。对大规模分布式进化算法的分析。2010年IEEE进化计算大会（CEC）会议记录，巴塞罗那，2010年1-8页。[12] J.Digalakis，K.Margaritis。消息解析集群上的并行进化算法。并行计算会议录，2003年。[13] B.埃弗里特，S.兰多，M.里斯。聚类分析。泰勒和弗朗西斯，2001年。[14] T.Gebbie，D.Wilcox，B.Mbambiso。Spin，随机因素模型，安达-加洲，南部非洲金融协会会议，开普敦，2010年。[15] L.贾达，M.马西里。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

2022-5-6 00:22:13

数据聚类和相关矩阵的噪声去除。菲斯。牧师。E、第63卷，第061101号，2001年。[16] L.贾达，M.马西里。最大似然数据聚类算法及其应用。《物理学A：统计力学及其应用》，第315卷，第34期，第650-6642002页。[17] 伊斯梅尔先生。并行遗传算法（PGA）：使用MPI的主从模式方法。IEEE电子技术，第31卷，第83-87页，2004年。[18] A.詹姆士，C.科埃罗。MRMOGA：一种新的基于多分辨率的并行多目标进化算法。《并发与计算：实践与经验》，第19卷，第4期，第3974412007页。[19] JSE。双重上市公司。网址：http://www.jse.co.za/how-tolist/main-board/dual-listed-companies.aspx检索日期：2014年3月8日。[20] P·克罗默，J·柏拉图，V·斯内塞。基于CUDA体系结构的基于数据并行密度的遗传聚类。《并发与计算：实践与经验》，第26卷，第5期，第1097-1112页，2014年。[21]J.克鲁斯卡尔。关于图的最短生成子树和travelingsalesman问题。《美国数学学会会刊》，第7卷，第48501956页。[22]L.Kullmann，J.Kert\'esz，R.N.Mantegnae。通过Potts超顺磁转换识别股票指数中的公司集群，arXiv:cond mat/0002238v2。[23]G.卢克，E.阿尔巴。并行遗传算法。斯普林格·维拉格，2011年。[24]B.姆班比索。将南非股票市场划分为不同的行业和国家。开普敦大学硕士论文，2009年。[25]李楠，G.彭东，L.涌泉，Y.文华。两种并行遗传算法的Matlab实现与比较。第九届分布式计算及商业、工程和科学应用国际研讨会，2010年。[26]诺杰德。股票市场相关性的模型。《物理评论E》，第61卷，第5981页，2000年。[27]英伟达。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

nandehutu2022

2022-5-6 00:22:17

Nvidia CUDA C编程指南。英伟达公司，2011年。[28]英伟达。CUDA动态并行编程指南。英伟达公司，2012年。[29]英伟达。CUDA C最佳实践指南。英伟达公司，2012年。[30]M.Omran，A.Salaman，A.Engelbrecht。粒子群算法在图像分割中的应用。《模式分析与应用》，第8卷，第4期，332-344页。[31]P.Pospichal，J.Jaros，J.Schwarz。基于CUDA体系结构的并行遗传算法。2010年进化计算应用国际会议论文集（EvoApplicatons\'10），SpringServerLag，第一卷，第442-451页，2010年。[32]D.罗比利亚德，V.马里恩，C.方卢普。GPU上的高性能遗传编程。2009年分布式系统仿生算法研讨会论文集，BADS 09，ACM:纽约，纽约，美国，第85942009页。[33]S.西瓦南丹，S.迪帕。遗传算法导论。斯普林格，2010年。[34]D.索内特。《自然科学中的临界现象：混沌、分形、自组织和无序：概念和工具》，斯普林格，2000年。[35]V.Tirumalai，K.Ricks，K.Woodbury。使用并行化和硬件来提高遗传算法的性能。《并发与计算：实践与经验》，第19卷，第4期，第443462页，2007年。[36]D.Whitley，S.Rana，R.Heckendorn。孤岛模型遗传算法：关于可分离性、种群规模和收敛性。《计算与信息技术杂志》，第7卷，第33-47页，1999年。[37]D.威尔科克斯，T.格比。南非市场数据的交叉相关性分析。Physica A，第375卷，第584-598页，2007年。[38]F.Y.吴。波茨模型，Rev。摩登派青年物理。，1982年，第54卷，第235-268页。[39]萧S，冯W。通过快速屏障同步进行块间GPU通信。2010年IEEE并行与分布式处理国际研讨会（IPDPS），pp。

扫码加我拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝