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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《High-speed detection of emergent market clustering via an unsupervised
  parallel genetic algorithm》
---
作者：
Dieter Hendricks, Diane Wilcox, Tim Gebbie
---
最新提交年份：
2015
---
英文摘要：
  We implement a master-slave parallel genetic algorithm (PGA) with a bespoke log-likelihood fitness function to identify emergent clusters within price evolutions. We use graphics processing units (GPUs) to implement a PGA and visualise the results using disjoint minimal spanning trees (MSTs). We demonstrate that our GPU PGA, implemented on a commercially available general purpose GPU, is able to recover stock clusters in sub-second speed, based on a subset of stocks in the South African market. This represents a pragmatic choice for low-cost, scalable parallel computing and is significantly faster than a prototype serial implementation in an optimised C-based fourth-generation programming language, although the results are not directly comparable due to compiler differences. Combined with fast online intraday correlation matrix estimation from high frequency data for cluster identification, the proposed implementation offers cost-effective, near-real-time risk assessment for financial practitioners.
---
中文摘要：
我们实现了一个主从并行遗传算法（PGA），该算法带有一个定制的对数似然适应度函数，用于识别价格演化中出现的聚类。我们使用图形处理单元（GPU）实现PGA，并使用不相交的最小生成树（MST）将结果可视化。我们证明，我们的GPU PGA在商用通用GPU上实现，能够基于南非市场的一部分股票以亚秒的速度恢复股票集群。这代表了低成本、可扩展并行计算的实用选择，并且比基于优化C的第四代编程语言中的原型串行实现要快得多，尽管由于编译器的差异，结果无法直接比较。结合基于高频数据的快速在线日内相关矩阵估计进行聚类识别，该方案为金融从业者提供了经济高效的近实时风险评估。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Computer Science        计算机科学
二级分类：Distributed, Parallel, and Cluster Computing        分布式、并行和集群计算
分类描述：Covers fault-tolerance, distributed algorithms, stabilility, parallel computation, and cluster computing. Roughly includes material in ACM Subject Classes C.1.2, C.1.4, C.2.4, D.1.3, D.4.5, D.4.7, E.1.
包括容错、分布式算法、稳定性、并行计算和集群计算。大致包括ACM学科类C.1.2、C.1.4、C.2.4、D.1.3、D.4.5、D.4.7、E.1中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Neural and Evolutionary Computing        神经与进化计算
分类描述：Covers neural networks, connectionism, genetic algorithms, artificial life, adaptive behavior. Roughly includes some material in ACM Subject Class C.1.3, I.2.6, I.5.
涵盖神经网络，连接主义，遗传算法，人工生命，自适应行为。大致包括ACM学科类C.1.3、I.2.6、I.5中的一些材料。
--

---
PDF下载：
--> High-speed_detection_of_emergent_market_clustering_via_an_unsupervised_parallel_.pdf (201.67 KB)

2022-5-6 00:20:34 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Evolutionary Practitioner Quantitative Applications Computation

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

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

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

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

聚类过程任何特定的聚类过程都需要优化某种标准，例如最小化簇内差异或最大化对象或簇之间的距离。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]。集群成员资格表明集群成员之间存在一些共性。每只股票都有一个作为其所处状态函数的动态分量，以及一个受股票特定噪声影响的动态分量。此外，可能存在影响所有股票的全球耦合，即。

代表市场模式的外部领域。在超顺磁聚类方法中，成本函数可以被视为哈密顿量，其低能量状态对应于与数据样本最兼容的聚类结构。然后，用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）连接的。在这个模型中，只有一个集群的情况可以被认为是基态。随着系统变得更加兴奋，它可能会分裂成更多的簇，每个簇都会有特定的磁感应，即使整个系统的净磁化可能保持为零。一般来说，这种相关性将是时间和温度的函数，以便将簇的演化以及簇的层次结构编码为温度的函数。

（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.

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

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