凝聚似然聚类

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

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

立即领取

感谢您参与论坛问题回答

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

+2 论坛币

英文标题：
《Agglomerative Likelihood Clustering》
---
作者：
Lionel Yelibi, Tim Gebbie
---
最新提交年份：
2021
---
英文摘要：
  We consider the problem of fast time-series data clustering. Building on previous work modeling the correlation-based Hamiltonian of spin variables we present an updated fast non-expensive Agglomerative Likelihood Clustering algorithm (ALC). The method replaces the optimized genetic algorithm based approach (f-SPC) with an agglomerative recursive merging framework inspired by previous work in Econophysics and Community Detection. The method is tested on noisy synthetic correlated time-series data-sets with built-in cluster structure to demonstrate that the algorithm produces meaningful non-trivial results. We apply it to time-series data-sets as large as 20,000 assets and we argue that ALC can reduce compute time costs and resource usage cost for large scale clustering for time-series applications while being serialized, and hence has no obvious parallelization requirement. The algorithm can be an effective choice for state-detection for online learning in a fast non-linear data environment because the algorithm requires no prior information about the number of clusters.
---
中文摘要：
我们考虑了快速时间序列数据聚类问题。在对基于关联的自旋变量哈密顿量建模的基础上，我们提出了一种更新的快速非昂贵凝聚似然聚类算法（ALC）。该方法将基于优化遗传算法的方法（f-SPC）替换为凝聚式递归合并框架，该框架受到了经济物理学和社区检测领域先前工作的启发。该方法在具有内置聚类结构的噪声合成相关时间序列数据集上进行了测试，结果表明该算法产生了有意义的非平凡结果。我们将其应用于多达20000个资产的时间序列数据集，并认为ALC可以在序列化的同时减少时间序列应用程序大规模集群的计算时间成本和资源使用成本，因此没有明显的并行化要求。由于该算法不需要关于聚类数目的先验信息，因此可以作为快速非线性数据环境中在线学习状态检测的有效选择。
---
分类信息：

一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Physics        物理学
二级分类：Data Analysis, Statistics and Probability        数据分析、统计与概率
分类描述：Methods, software and hardware for physics data analysis: data processing and storage; measurement methodology; statistical and mathematical aspects such as parametrization and uncertainties.
物理数据分析的方法、软硬件：数据处理与存储；测量方法；统计和数学方面，如参数化和不确定性。
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--

---
PDF下载：
--> Agglomerative_Likelihood_Clustering.pdf (1.97 MB)

2022-6-24 13:23:41 上传

扫码加我 拉你入群

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

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

分享0 收藏0 回帖

关键词：Applications Econophysics Mathematical Quantitative time-series

聚集似然聚类法*和Tim Gebbie+南非开普敦大学统计科学系，Rondebosch 7701（日期：2021 10月6日），我们考虑了快速时间序列数据聚类的问题。在对基于关联的自旋变量哈密顿量建模的基础上，我们提出了一种更新的快速非代价聚集似然聚类算法（ALC）。该方法将基于优化遗传算法的方法（f-SPC）替换为凝聚式递归合并框架，该框架受到了经济物理学和社区检测领域先前工作的启发。该方法在具有内置聚类结构的噪声合成相关时间序列数据集上进行了测试，结果表明该算法产生了有意义的非平凡结果。我们将其应用于多达20000个资产的时间序列数据集，并认为ALC可以在序列化的同时减少时间序列应用程序大规模集群的计算时间成本和资源使用成本，因此没有明显的并行化要求。该算法对于快速非线性数据环境中在线学习的状态检测是一种有效的选择，因为该算法不需要关于聚类数的先验信息。PACS编号：05.10。Ln，75.10。Nr，89.65。GhI。简介总结从具有未知动态演化和非线性交互的环境中采样的大量快速实时特征时间序列数据需要某种无监督学习。先前的工作[47]探讨了金融市场数据背景下的无监督统计学习问题，其中显示了从数据快速近似超顺磁性团簇结构的能力[2，11]。具体而言，该算法在熵极大值附近恢复了正确的超顺磁团簇结构。

以前的案例研究包括股票数据聚类[47]和[12]中的基因数据，金融市场的时间状态[23]，以及交易中自适应机器学习的状态检测[15]。这种快速大数据集群技术的潜在使用案例数不胜数。以前实现的关键问题与非常大的数据集的计算时间有关。在先前工作的基础上，我们提出并演示了一种快速超顺磁聚类（fSPC）的替代方案【47】，该方案采用了【12】中首次提出的“合并算法”的现代简化实现，该算法可以恢复相同或更好的聚类配置，但计算时间显著减少。该算法在精神上类似于网络科学社区检测算法[4，36]。股票市场相关矩阵的结构分析构成了经济物理学、定量金融和网络科学的一大研究主体。代表*莱昂内尔。yelibi@alumni.uct.ac.za+tim。gebbie@uct.ac.zaFor回顾过去20年来基于金融市场相关性的数据聚类（见[25]），更一般的数据聚类（见[17]），尤其是时间序列聚类（见[1，22]）。从网络的角度来看，金融资产之间的关系已成为探索、洞察和可视化各种聚合动态过程对资产的集体影响的越来越有用的方法；无论是市场崩溃的影响，还是投资组合优化的迭代应用的影响。

这很方便，因为图形可以用邻接矩阵表示，相关矩阵可以在处理之前映射到网络数据；这里通过了社区检测算法。网络数据通常由稀疏矩阵表示，这在操作上可以被视为数据聚类和社区检测之间的主要差异，即表示上的差异。为了将相关矩阵映射到邻接矩阵中，应用了阈值isoften[30、41、48]。链接或取消链接相关节点的阈值是任意的。然而，这会给金融资产图的研究增加一层复杂性，同时也是一个额外的噪声源，与控制集合或对象之间关系的动态过程几乎没有关系。我们的方法不同于基于阈值的方法，因为它是一个faithfuldata聚类模型，可与密集的相关矩阵一起工作–这可以使其适用于噪声环境中的复杂系统，但无需任意选择阈值。在此，我们再次利用了Giada和Marsili提出的Noh-Ansatz[31]和最大似然估计（MLE）方法[11，12]。我们称之为新算法凝聚似然聚类（ALC）；与之前在[15、16、47]中实现的并行遗传算法（PGA）相比，它的优点是计算成本更低。性能增强源于能够将算法序列化为跨集群配置的蛮力搜索，以避免不必要的计算开销。

f-SPC的实现。论文内容如下：在第（II）节中，我们介绍了Giada Marsili模型，在第（III）节中，我们描述了优化算法，在第（IV）节中，我们考虑了合成生成的时间序列数据的聚类，在第（V）节中，当信噪比相对较低时，我们提供了额外的工具，第（VI）节探讨了具有嵌套块结构的复杂相关矩阵的解决方案恢复，第（VII）节讨论并比较了我们的新方法执行运行时与以前的算法和HDBSCAN，然后是第（VIII）节的讨论和结论，强调了我们介绍的算法的性能。二、GIADA-MARSILI似然模型股票市场相关性矩阵的谱分析提供了一种以Nohansatz[31]为形式的直觉：在金融市场中存在一种层次结构，其中单个股票是较大资产组的子组成部分，每个资产的个别回报率受其所属资产集合的影响。这可以用一个简单的生成模型来表示【31】：xi=fi+i（1）夏尔股票的特征、集群相关影响，以及i节点的特定影响。反过来，这种生成模型可以迭代地嵌套在一组更复杂的独立层次结构中，通过存在自上而下和自下而上因果关系的未知噪声项进行扩展【40，43】。在这里，我们将自己限制在一个单独的集合中，该集合被分成多个组，并使用一个简单的噪声术语来解释无法解释的外部性。我们考虑一组嵌入在aspace中的N个观测值，每个观测值都被赋予一个自旋值，每个观测值的维数为D。

ansatzmodels的一个版本的观测特征是xi=gsiηsi+q1- gsi公司i（2）其中xi是一个特征，即簇内耦合参数，η是簇相关影响，以及itheobservation的特定影响和测量误差。A方差分析产生额外的术语，如聚类的结构和聚类内的相关性。我们明确提到，必须强制执行ns<cs<ns：需要下限，因为未定义cs值的gsi≤ ns和上限要求热平均hgsi可用于重建具有与原始时间序列相同的统计特征的数据集，使用Eqn。（2） 【11】此处ns=PNi=1δsi，s，cs=PNi=1PNj=1Cijδsi，sδsj，s，gs=qcs-NSN-ns【11，15】。一个严格不等式，因为方程。（4） 当S=ns时为未定义。我们引入Dirac delta函数来模拟在临界状态下观测数据的概率【26】：P=DYd=1NYi=1*δ（xi- （gsiηsi+q1- gsi公司i） ）+。（3） 这种联合可能性是每个观测值和每个特征的聚类配置与观测数据相匹配的概率。从P导出的对数似然可以看作这个Pottssystem的哈密顿量【44】：Lc=Xs：ns>1lnnscs+（ns- 1） lnns公司- NSN- 反恐精英. （4） 计算每个特征的总和，并表示数据中存在的结构量。LCI的值通过NSA和cs间接依赖于自旋。相对于大多数行业标准备选方案，该方法有以下优点：首先，LCI完全依赖于Cij，数据集的维数仅在计算Cij中起作用。其次，它是自适应的：与K-MEANS（38）或类似算法不同，簇的数量不作为输入。聚类配置是随机生成的，而最大化LCS的配置为我们提供了聚类的数量及其组成。

后一个特性的重要性不应丢失，因为它消除了一层不必要的超参数调整。因此，该算法与DBSCAN[7，20]和HDBSCAN[6，27]等算法竞争。三、 聚集可能性聚类（aggregative likelihoodclustering）在考虑聚类问题时，通常使用的传统观点是尝试将方法划分为实现自顶向下或自底向上算法的方法。使用这种观点，自上而下的方法被认为是分裂的，包括以单个集群作为初始条件开始，并在最小化成本的同时迭代地将图拆分（或分割）到其他集群中。另一方面，自底向上方法最初从其自身集群中的每个观测值开始，然后进行迭代合并[29]。所谓的“Louvain”算法[4]是聚合的，因此可以认为是为了在网络上实现后一种自下而上的“社区检测”方法。ItLet yi=xi-gsiηsi+q1- gsi公司我, δ（y）是y的狄拉克三角函数，当y=0时为1，否则为0。在精神上与Marsili和Giada在[12]中开发的合并算法（MR）非常相似。我们以前实现的方法是基于高效的实现，这些实现简化了DPGA优化框架，例如，在[15、16、47]中提出的那些允许各种突变。然而，这些方法对初始条件很敏感，因为在每一步都会对新一代个体进行突变、评估，然后一组最佳候选个体存活下来，直到下一个算法的迭代——这可以是任意路径依赖的。

f-SPC算法[47]通过能够排除[15，16]中使用的geneticprogramming框架中计算代价高昂的变异约束，在PGA框架中获得了额外的计算优势。然而，基于遗传算法的方法也有缺点，表（I）中讨论了关键方法，并说明了以下需要：I.）不明确的停止或收敛标准，ii。）随机突变，以及iii.）某种并行化以减少计算时间。（一） 1收敛标准：假设存在多个局部极大值，它试图围绕这些“次优”解决方案导航，以达到全局最大值。然而，这是不确定的，它只是假设一旦满足一个标准，算法就会停止——该算法是显式随机不收敛的。（一） 2随机突变：由于算法应用随机突变，种群规模、突变数量和多样性以及世代数都会对最终结果产生影响-这可能会引入路径依赖。（一） 3并行化：该算法要求在每次迭代时评估整个变异群体。这需要在每个工作者身上加载数据（即相关性或相似性矩阵），因此需要计算和内存成本。可能性评估本身并不昂贵，但多处理会增加CPU开销。这可以通过使用GPU来缓解，如[15]所示。表一：似然Lc的PGA算法的缺点。A、 贪婪的merging要构建一个快速的通用自底向上合并算法，我们再次从N个簇中的所有N个自旋开始，但以贪婪的方式迭代合并簇。Giada Marsili合并算法（MR）的实现需要计算可能性的变化Lc：我们考虑三个集群C、C和CwithC=C+CW，其中加法运算符“+”表示集群Cand Care合并。

Marsili和Giada de finetwo案例Lc【12】：案例1：Lc=Lc（C）- 最大值[Lc（C），Lc（C）]（5）情况2：Lc=Lc（C）- 【Lc（C）+Lc（C）】（6）如式（5）所述，在案例1中，C将比任何C和C更好。在这里，我们选择使用更具限制性的定义，如式（6）所定义的案例2。关键是要认识到，案例2要求新合并的集群必须优于两个单独子集群的组合。我们可以通过构建一个在集群空间上执行综合网格搜索的算法来迭代利用这一点。为了实现这一点，我们可以通过去掉和来修改等式（4），并且只计算单个集群的可能性：Lc=lnnscs+（ns- 1） lnns公司- NSN- 反恐精英. （7） 每次迭代的目标是最大化l完成所有可能的动作。我们用于生成移动的实现受到了隔离检测方法创新的启发，即社区检测[18]算法，如“Louvain算法”[4]。使用这种类型的社区检测，我们返回到Abotomup聚集方法，使用似然法快速列举候选配置，以确定特定配置的有效性。凝聚似然聚类框架是一个通用框架，适用于任何有用的似然函数选择。在这里，我们将选择修改后的GiadaMarsili似然函数，然后使用合并算法中的案例2（等式（6））。还可以选择其他可能性，例如多因素聚类规范或可能性函数分叉方法。该框架是通用的，但所做的选择特定于自旋哈密顿框架。B、 迭代群集配置实现需要跟踪关联矩阵和算法每次运行时的群集配置。

为了保持集群结构的灵活但动态的表示，我们引入了跟踪器阵列的概念（见表（II））。此对象将在算法更新期间存储每个集群中表示的对象列表。该算法是用单态集群初始化的。一旦执行了表（II）中的初始化步骤，我们就可以进入所需的实际优化步骤，在python中，计算出的numpy相关矩阵可以存储到python字典中，以便轻松高效地进行修改。跟踪器可以存储为列表变量。这些在表（III）中描述。这需要群集更新步骤，计算可能性变化，使用跟踪列表更新配置记录，更新相关矩阵，然后检查收敛标准。（二） 1相关矩阵：C存储在一个结构中，每当需要新条目、创建额外的聚类或删除以前的聚类对象时，都可以轻松修改该结构。（二） 2单例初始化：所有对象都从它们自己的集群开始。（二） 3跟踪列表：我们创建一个存储对象列表的列表：每个列表代表一个集群，列表中的标签是集群成员。变量nsis是集群大小。表I I:ALC初始化使用单例配置、以高效方式存储的相关矩阵（可在算法实施期间轻松修改）以及记录配置的跟踪列表。（三） 1聚类：在Tracker的标签中随机选取一个对象，将其与所有其他对象聚类，并存储结果Lcvalues。（三） 2最大化可能性变化：找出最大信用证；如果大于0，则继续下一步。