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

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

在进行选择和突变之前，宿主会等待，直到它收到群体中所有个体的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。

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。

这两种卡都提供了双精度计算和可比数量的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所示，用作适应度函数。

这用于确定群集配置是否代表数据集的固有结构，即它将用于检测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操作发出命令来控制进化过程。

实现的算法的伪代码如算法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概述了个体基因到线程的所选映射对允许种群范围和种群规模的限制。

对于较大的问题，选择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中的不同线程会严重影响性能。

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

特别是，考虑了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文件中读取。

接着，通过使用相关矩阵中的数据值，结合各自数据集的计算聚类配置，构造邻接矩阵。然后利用邻接矩阵构造一组不相交的最小生成树（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的最佳伴随参数。在每一种情况下，该算法都连续应用于训练集，具有已知的不相交聚类。