凝聚似然聚类

[40].使用该模型，我们在两个层次的块相关示例上演示了聚类：a.）图（4a）中的250只股票的聚类的相关矩阵，图（4a）中的5个层次（每个层次50只股票），和b.）系统的相关矩阵，图（4b）中的3个聚类的估计时间序列为250个观测值（即1个交易年），α=0.4（如图（4b））。与我们的玩具模型不同，真实的相关矩阵不太可能以一种可以揭示其块结构的方式进行静态排序，这将使聚类变得平凡。使用单链接算法创建的图（4c）和（4d）中的树状图揭示了图（4a）和（4b）中相关矩阵中存在的层次结构。乍一看，通过有序相关矩阵可以区分图（4c）和（4a）中的5个层次。然而，在包含这些嵌套簇集的倍数的系统中，表观结构是具有潜在子簇的3个簇的结构。这里的关键问题是，由ALC和HDBSC产生的解决方案是否包含子簇或大簇；i、 e.图（4a）中的数据分析结果是否包含1个或5个聚类，以及图（4b）中的那些、3个或15个聚类？为了回答这个问题，我们对这两个数据集进行了若干α值的聚类，以研究低相关性和间接低聚类密度对算法输出的影响。我们发现，对于低α，时间序列主要受这些因素的影响，对于图（4a）和（4b）中的数据，HDBSCAN和ALC都分别恢复了5个和15个簇。HDBSCAN的噪声影响更大，算法开始将α>0.2（见图（6））生成的数据集的观测值添加到图（4a）中数据的“噪声”类别中。而ALC生成的溶液开始从α>0.4降解。数据inFig也是如此。

（4b）当α>0.2时，HDBSCAN开始将嵌套簇合并为3个大簇，当α>0.5时，解决方案会进一步退化（见图（6））。同样，ALC解决方案更具弹性，当α>0.4时，嵌套簇合并，3cluster解决方案永远无法恢复，ALC解决方案开始退化。这标志着ALC和HDBSCAN之间存在着明显的差异：ALC似乎优先考虑较小但更紧密相关的集群，而HDBSCAN的默认行为是合并集群，即使产生的集群密度较低（即噪音较大）。ALC似乎对噪声的鲁棒性也提高了20%。最后，对于α>0.7的ALC溶液，是完全无序的分区。七、性能改进ALC类聚类算法的吸引力在于其始终优于f-SPCalgorithm的能力，同时通常对噪声具有鲁棒性。在此，我们使用附录B中所述的综合模型对时间序列数据集进行聚类，其大小不断增大（N=50100200300）和10个聚类。图7a显示，如果我们使用似然函数作为质量函数，ALC可以恢复质量更好的聚类解决方案，如[12]所述。此外，算法运行时间大致为二次型。这是根据合成数据集SO（N1.97）和真实数据集SO（N2.11）进行估计的，从而使其在在线学习问题上具有竞争力。我们将该算法的运行时间与之前的f-SPC和HDBSCAN进行了比较【27】。如前所述，f-SPC的解决方案不仅具有较低的可能性，而且需要更多的计算能力，才能在10个大小不等的聚类的显著高斯混合中实现收敛。1998年至2020年间，我们每天对CRSP美国共同基金净资产值（NAV）进行采样，从中获得的数据集的大小为100到10000，时间更长。图7b表明，如果未来的优化算法提供低质量的解决方案，则其成本预计不会比ALC更高。

最后，我们认为HDBScan是ALC的天然替代品，是一种基于层次和密度的聚类方法，它比我们的算法优化得多，因此目前更适合于超大数据集。然而，有证据表明，ALC可以被视为HDBSC的重要替代品，因为在某些情况下，当数据密度较低、相关性较低且噪音较大时，它在ARI方面表现优异（见表IV）。关键的一点是，ALC在质量和性能方面都具有竞争力，而不是为了优化运行时间性能而重新定义算法。八、讨论和结论我们提出了一种能够实现Giada MarsiliLclikelihood最大化的凝聚算法（见等式（4））。在之前的工作中，我们建立并证明了一种使用Eqn局部最大化可能性的机制。（7） 而不是Eqn。(4) [47]. 在这里，我们不是随机移动，而是对所有可能的组合进行综合搜索，并在每次迭代中选择最佳移动。该算法比马尔可夫链蒙特卡罗算法和基于遗传算法的求解速度要快得多，并达到相等或更好的最大值。它只需要一个相关矩阵作为输入，其输出是反映相关样本的最佳聚类数的聚类配置。它不需要关于集群数量的优先信息。该特性可能使该算法适用于快速大数据环境中在线学习的状态检测。我们还提出了一种基于inEqn中给出的Noh ansatz的模拟相关时间序列数据生成方法。(2). 单个时间序列由其日常随机效应确定 虽然它们仍然受到集群效应η的影响，但单个对象与其集群之间的耦合强度由gs表示。

这使我们能够调整集群密度，并研究其对集群质量和基准性能的影响。我们发现，即使在较低的簇内耦合值（gs≈ 0.05）性能很差，但随着GSR的增加和群集的密集化，该算法比其竞争的替代HDBSCAN更快。对于ALC和HDBSCAN，我们能够对更大的数据集进行集群，并将模拟扩展到N=10000。所有脚本均在带有4个CPU的移动Intel i7 CPU上执行。这取决于高代，对于更高的数字，应该可以获得更好的结果。这说明f-SPCR需要非平凡的参数化，而ALC则不需要。（a） 使用HDBSCan和ALC对图（4a）中的数据恢复的群集数，作为功能群集规范。ALC对层次相关模型中的聚类特定噪声更具鲁棒性。（b） 使用HDBSCan和ALC对图（4b）中的数据恢复的簇数，作为簇特定噪声的函数。ALC对层次相关模型中的聚类特定噪声更具鲁棒性。图5：集群数量与集群特定噪声级参数α的函数关系。随着α增加，集群特定噪声增加。ALC从α=0.4降低，并且在高噪声水平下会产生许多单态。图6:HDBSCAN对“集群”图（4a）和“系统”图（4b）中的数据误分类为噪声的对象百分比。当信噪比较低时，在某些情况下，可以通过结合ALC使用自举来减轻相关矩阵噪声的影响。这允许更好的总体性能，但代价是算法运行时间显著增加。与引导相关的增加的计算可以以批处理格式执行，也可以与集群算法本身并行执行。

然而，能够对相对较短的时间序列（或相当低维的数据集）执行准确的聚类是很有价值的。我们注意到，为引导步骤探索替代的、也许更有效的采样方案可以减轻这一额外成本【21】。在（V）中引入的currentBootstrap方法是在n个变量中的n个均匀样本空间中进行的，对于大的n，该方法变得非常昂贵。此外，我们在已知地面真实情况的合成数据上演示了它的使用。在realdata上，显然需要为潜在用户确定停止标准（即似然Lc的收敛性）。当我们使用分层因子模型设计和聚类数据集时，ALC和HDSCAN都会恢复底层嵌套的集群。ALC对生成的合成数据集的鲁棒性提高了20%。事实上，对于这样的层次集群的大型系统，HDBSCAN有将集群合并为大型集群的趋势。这类聚类问题没有单一的解决方案，由从业者来确定具有较大但密度较小的聚类的解决方案是否比具有较小但密度较大的聚类的解决方案更有用。在在线学习环境中使用该算法可以实现潜在的进一步研究。我们怀疑，在金融市场的情况下，可能会进行时间聚类，这将允许对金融市场现有动态进行分析，从而提高可靠性。

专门用于围绕记录的极端事件对金融市场进行动态聚类分析。当前版本的算法能够轻松处理多达10000个样本的数据集即将在Intel（R）Core（TM）i7-6700HQ CPU上进行测试，测试频率为2.60GHz（a），通过使用f-SPC（47）和ALC（第三节）在对数尺度上增加数据集大小时获得的解决方案的似然Lc（见第二节中的模型），比较群集质量。ALC解决方案系统地比使用f-SPC获得的解决方案具有更高的可能性。（b）当我们在fSPC【47】、ALC（第三节）和HDBSCAN【27】的对数尺度上增加数据集大小时，比较算法运行时性能。所有都大致为二次型，f-SPC的价格明显更高，而HDBSCAN的表现优于ALC。在不到5分钟的时间内，就有足够的时间来“喝杯咖啡”。重要的是，还应该注意到，Louvain算法存在多个比当前算法中使用的原始实现更快的版本【9、32、39】，人们应该能够找到进一步的优化，这将使大规模密集相关矩阵的聚类成为可能，类似于目前在网络科学领域所做的工作。对分布假设的影响也是未来工作的一个重要领域，第（II）节的Giada Marsili可能性是在假设IID Gaussianrandom变量的情况下得出的。使用相同的Noz-Ansatz，应该可以得出假设不同分布的相关模型扩展。e、 g.学生t分布。具体而言，高斯假设是这类模型的基线，但众所周知，股票市场的对数收益率至少是厚尾分布的（除了其他类型化的事实，如长记忆、波动性聚类和杠杆效应）。

这激发了使用分布的替代建模，这些分布捕获了额外的样式化事实【10，13】。此外，可以使用不同的相似性度量。两个随机变量之间的协方差是用于对金融市场资产收益率序列进行数据聚类的标准相似性度量。信息论互信息等替代方法此前已直接用于金融数据时间序列[8，14]。最后，我们认为有可能升级ALC，使其具有更高效的编码，并对优化方案本身进行更好的修改，类似于最近Louvain的实现。九、 致谢作者感谢Nic Murphy、Daniele Marinazzo、Gautier Marti和Unarine Singo的讨论和评论。[1] Aghabozorgi，S.，Shirkhorshidi，A.S.，和Wah，T.Y.（2015）。时间序列聚类——十年回顾。信息系统，53:16–38。[2] 布拉特，M.、怀斯曼，S.和多曼尼，E.（1996）。数据的超顺磁性聚类。物理。修订版。Lett。，76(18):3251–3254.[3] Blatt，M.、Wiseman，S.和Domany，E.（1997年）。使用模型粒状磁铁进行数据聚类。神经计算，9（8）：1805-1842。32GB随机存取内存。[4] Blondel，V.D.，Guillaume，J.-L.，Lambiotte，R.，andLefebvre，E.（2008）。大型网络中社区的快速发展。统计力学杂志：理论与实验，2008（10）：P10008。[5] Bun，J.、Bouchaud，J.-P.和Potters，M.（2017）。清理大型相关矩阵：来自随机矩阵理论的工具。物理报告，666:1–109。[6] Campello，R.J.G.B.、Moulavi，D.和Sander，J.（2013）。基于层次密度估计的基于密度的聚类。《知识发现和数据挖掘进展》，编者，裴，J.，曾，V.S.，曹，L.，Motoda，H.，和Xu，G.，计算机科学讲稿，第160-172页，柏林，海德堡。

斯普林格。[7] Ester，M.、Kriegel，H.-P.、Sander，J.和Xu，X.（1996）。一种基于密度的聚类发现算法一种基于密度的聚类发现算法，用于在有噪声的大型空间数据库中发现聚类。《第二届知识发现和数据挖掘国际会议论文集》，KDD\'96，第226–231页。AAAIPress。[8] Fiedor，P.（2014）。基于互信息率的金融市场网络。物理。修订版。E、 89（5）：052801。[9] Fontolan，F.（2020年）。GPU上基于模块化的社区检测。威尼斯大学学士学位论文。[10] Gabaix，X.、Gopikrishnan，P.、Plerou，V.和Stanley，H.E.（2003）。金融市场波动中的幂律分布理论。《自然》，423（6937）：267–270。[11] Giada，L.和Marsili，M.（2001年）。数据聚类和相关矩阵的噪声去除。物理。修订版。E、 63（6）：061101。[12] Giada，L.和Marsili，M.（2002年）。最大似然数据聚类算法及其应用。Physica A：统计力学及其应用，315（3）：650–664。[13] Gopikrishnan，P.、Meyer，M.、Amaral，L.和Stanley，H.（1998年）。股票价格变化分布的逆三次定律。欧元。物理。J、 B，3（2）：139–140。[14] 郭，X.，张，H.，和田，T.（2018）。利用互信息和金融大数据开发股票关联网络。《公共科学图书馆》一书，13（4）：e0195941。[15] Hendricks，D.、Gebbie，T.和Wilcox，D.（2016a）。使用时间聚类法检测日内金融市场状态。定量金融，16（11）：1657–1678。[16] Hendricks，D.、Gebbie，T.和Wilcox，D.（2016b）。基于无监督并行遗传算法的紧急市场聚类快速检测。南非科学杂志，112（1/2）：9。[17] Jain，A.K.（2010）。数据聚类：50年超越K均值。模式识别字母，31（8）：651–666。[18] Javed，硕士，Younis，硕士。

S、 ，Latif，S.，Qadir，J.，andBaig，A.（2018年）。网络中的社区检测：多学科综述。网络与计算机应用杂志，108:87–111。[19] Kalayci，C.B.、Ertenlice，O.和Akbay，M.A.（2019年）。对均值-方差投资组合优化的确定性模型和应用进行全面回顾。ExpertSystems with Applications，125:345–368。[20] Khan，K.、Rehman，S.U.、Aziz，K.、Fong，S.和Sarasvady，S.（2014）。DBSCAN：过去、现在和未来。第五届数字信息和网络技术应用国际会议（ICADIWT2014），第232-238页。[21]Kim，J.、Lee，W.、Song，J.J.和Lee，S.-B.（2017）。随机过程的优化组合聚类。群集计算机，20（2）：1135–1148。[22]Liao，T.W.（2005）。时间序列数据的聚类。模式识别，38（11）：1857-1874。[23]Marsili，M.（2002）。剖析金融市场：部门和国家。定量金融，2（4）：297–302。[24]Marti，G.、Andler，S.、Nielsen，F.和Donnat，P.（2016）。聚类金融时间序列：多长时间足够？《第二十五届国际艺术情报联合会议记录》，IJCAI\'16，第2583–2589页。AAAI出版社。活动地点：美国纽约州纽约市【25】Marti，G.、Nielsen，F.、Bi'nkowski，M.、Donnat，P.（2017）。回顾二十年来金融市场的相关性、层级、网络和集群。arXiv预印本arXiv:1703.00485。[26]Mastromatteo，I.和Marsili，M.（2011）。关于推断模型的临界性。统计力学杂志：理论与实验，2011（10）：P10012。【27】McInnes，L.、Healy，J.和Astels，S.（2017年）。hdbscan：基于层次密度的聚类。开源软件杂志，2（11）：205。【28】McInnes，L.、Healy，J.、Saul，N.和Groiberger，L.（2018）。UMAP：一致流形近似和投影。

《开源软件杂志》，3（29）：861。[29]Murtagh，F.和Contreras，P.（2012）。层次聚类算法：概述。WIREs Data Miningand Knowledge Discovery，2（1）：86–97。【30】Namaki，A.、Shirazi，A.H.、Raei，R.和Jafari，G.R.（2011）。基于因果关系和阈值法的金融市场网络分析。Physica A：统计力学及其应用，390（21）：3835–3841。[31]Noh，J.D.（2000）。股票市场相关性模型。物理。修订版。E、 61（5）：5981–5982。【32】Ozaki，N.，Tezuka，H.，和Inaba，M.（2016）。Louvain算法的SimpleAcceleration方法。未定义。[33]Pedregosa，F.、Varoquaux，G.、Gramfort，A.、Michel，V.、Thirion，B.、Grisel，O.、Blondel，M.、Prettenhofer，P.、Weiss，R.、Dubourg，V.、Vanderplas，J.、Passos，A.、Cournapeau，D.、Brucher，M.、Perrot，M.和Duchesnay，E.（2011年）。Scikit学习：Python中的机器学习。机器学习研究杂志，12:2825–2830。【34】Pollet，J.M.和Wilson，M.（2010）。平均相关性和股市回报。《金融经济学杂志》，96（3）：364-380。[35]Prado，M.L.d.（2016）。构建表现优于样本外的多样化投资组合。《港口管理杂志》，42（4）：59–69。【36】Ronhovde，P.和Nussinov，Z.（2010）。用于社区检测的局部分辨率无限制Potts模型。物理。修订版。E、 81（4）：046114。[37]Santos，J.M.和Embrechts，M.（2009）。使用调整后的兰德指数作为评估监督分类的指标。ICANN 2009。《计算机科学》第5769卷讲稿。，摘自：Alippi C.、Polycarpou M.、Panayiotou C.、Ellinas G.（编辑）Arti-ficial NeuralNetworks–ICANN 2009。施普林格，柏林，海德堡。[38]Steinley，D.（2006）。K-均值聚类：半个世纪的综合。英国数学与统计心理学杂志，59（1）：1-34。[39]Traag，V.A.（2015年）。