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

设置是不同的，直到收敛速度最大化。一旦从训练集中确定了每个伴随参数的最佳值，就在测试集中部署了最佳算法配置。在进一步的研究中，作者将研究不同的伴随参数选择对不同股票宇宙大小的收敛速度和算法效率的影响。测试集上部署了以下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只真实世界股票的单一相关矩阵中的剩余集群，展示其作为近实时风险评估工具的潜力。

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

这应该在进一步的研究中加以探讨。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说明了英国开盘对当地交易模式的影响。我们看到一个大型集群的明显出现，表明英国投资者的交易活动对当地市场产生了重大影响。在研究大型单一集群时，所有股票在美国和英国都有一级或二级上市。

特别是，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。

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

聚类算法捕捉系统动力学的可解释和有意义特征的能力，以及其构造的一般性，表明该方法可以在其他领域获得成功。进一步的研究包括针对不同库存范围大小和集群类型的伴随参数调整和性能可扩展性，量化非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.瓦克斯鲁瑟。

基于密度的群集化图形处理器。第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.马西里。

数据聚类和相关矩阵的噪声去除。菲斯。牧师。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]英伟达。

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。

1-12, 2010.[He.S]张。基于oncuda的并行遗传算法的实现。第四届国际不计算与智能进展研讨会论文集，ISICA\'09，柏林，海德堡，斯普林伯格，第24-30页，2009年。[41]G.张，W.刘，G.刘。基于mpi环境的并行遗传算法。Telkomnika，第10卷，第1708-1715页，2012年。