序列的同步子集的大规模解决方案

9493发现序列的同步子集：一个大规模的解决方案作者：Evangelos Sariyanidi1，Casey J. Zampella1，Keith G. 1，John D. Herrington1，2，Theodore D.作者声明：Robert T. Schultz1，2和Birkan Tunc1，21费城儿童医院自闭症研究中心{sariyanide，zampellac，bartleyg，herringtonj，schultzrt，tuncb}@ email.chop.edu摘要找到序列的最大子集（即，时间序列）在大数据集内相关超过某一阈值，对于跨领域的计算机视觉和模式识别问题具有重要意义，所述领域包括生物学分析、计算生物学、神经科学和金融。最大团算法可以用来解决这个问题，但它们是不可扩展的。我们提出了一个近似的，但高效和可扩展的方法，表示搜索空间作为一个联盟的集合称为扩展集群，其中之一是理论上保证包含最大的子集的同步序列。该方法发现同步集拟合欧几里德球上扩展集群，使用荣格定理。我们验证了该方法的数据来自三个不同的领域的fa-cial行为分析，金融，神经科学，我们分别发现像素的人脸视频，股票市场项目的价格，和动态大脑连接数据之间的同步。实验表明，我们的方法产生的结果相媲美，但高达300倍的速度比，最大-团算法，与速度增益增加exponentially与输入序列的数量。1. 介绍同步性在无数现象中被观察到，它的发现对于回答许多计算机视觉和模式识别问题至关重要然而，令人惊讶的是，一个基础研究问题仍然没有得到充分探索：给定一组序列（即，时间序列），我们如何发现其中每对序列满足同步标准的最大子集？这个问题在许多领域自然会出现。例如，在视频中，只有像素子集中的运动在时间上同步，并且它们的识别可以导致发现感兴趣的事件（例如，面部表情[58，54]）。在股票市场中，只有确定的资产和先验未知的资产的价格是相关的.大脑被动态地组织成神经元的子集（即，模块、系统）具有同步激活。的确，研究人员已经利用序列之间的同步性来挖掘金融数据[4，29]，定义大脑的功能架构[22，6]，并识别复杂网络中的社区结构[36，31]。以往的研究在这方面通常采用最大团算法。然而，尽管它们被广泛使用，但最大集团出租具有指数复杂性[48]，这对可以针对的可能研究问题施加了障碍在本文中，我们提出了一个有效的和可扩展的框架来近似解决以下问题：给定一组序列，找到最大的子集，使得该子集中的所有序列对都相关超过给定的阈值。框架首先对所有输入序列进行聚类，然后细化聚类，直到聚类内的所有序列都同步（即，pairwisecorrelated）。在细化之前，将簇扩大以获得所谓的经扩展的簇。我们称我们的方法为SyncRef，因为它通过细化找到同步的子集。在这里，我们通过对来自三个不同领域的数据进行实验来证明SyncRef这些实验清楚地表明，SyncRef产生的解与精确解高度可比，但获得的速度要快数百倍。此外，SyncRef的速度增益随序列的数量呈指数增长。本文提出了两个具体的技术贡献。首先，我们介绍了扩展的概念，一个原则的方法来扩大一组集群，跨越输入集。理论上保证同步序列的最大可能子集包含在扩展群集之一中。其次，我们展示了如何使用荣格定理来确保输出解中所有可能的序列对在给定阈值以上是相关的。我们还提供了如何扩展SyncRef方法，以发现在一个未知的时间窗口内的局部相关序列的最大子集的方向。SyncRef的代码可在https上公开获得//github.com/sariyanidi/SyncRef网站。9494i=1i=11.1. 问题公式化我们现在用公式表示发现同步（即，成对相关的）序列子集（即，时间序列）。 设X是N个序列的集合，每个序列具有-对T个时间值，X={x i}N。设r（x i，x j）为cor，序列x i和x j之间的相关系数。 我们如果一对序列的相关性不小于ρθ，或者等价地，如果z归一化序列的差的范数不大于θ：= 2T（1−ρθ）（见补充附录A）。模拟类似地，我们称序列集合S：={xi}i∈I，其中I是{1，. -是的- 是的 ，N}同步。我们的目标是找到最大的同步集;即，极大基数集|.|.该优化问题表示如下。与我们相关的一个问题是最长公共子串（LCS）发现[23]。然而，LCS发现适用于离散值数据（例如，单词，DNA/蛋白质序列），而我们感兴趣的是连续值序列。可以使用聚类来识别相似序列[46]。然而，没有聚类方法（包括层次聚类）或其他空间划分算法（例如KD树）可以确保满足（3）中的条件-聚类的所有成员之间的成对相关性与我们最接近的聚类范例是基于密度的方法，它施加了一个邻近约束然而，这些方法并不要求集群中的所有对都满足邻近约束;集群的任何成员足够接近任何其它成员就足够了。问题1. 给定序列集X={xi}N和θ，最后，我们的问题可以使用通用极大团算法[48，5]（第1.1节）解决。不幸的是，最大|S|（一）若S={xi}i∈I，I∈{1，. -是的-是的，N}， （2）||2≤ <$θ <$i，j ∈ I，（3）||2≤ǫθ∀i,j∈I,(3)由于它们的计算时间和空间复杂性，这些算法对于在大N上的操作是不实用的（也参见3.1.4节）。还可以使用近似的最大团查找算法[17]来减少计算量。Wheeexbirds是序列xi的z归一化版本。复杂性在我们的实验中，我们比较了精确和近似的最大团发现算法。我们这个问题等价于在一个二值图中寻找最大的极大团，其节点表示序列，并且如果两个节点之间的距离至多为<$θ，则两个节点是连通的-这是一个NP完全问题。1.2. 相关工作相关性可以说是跨域同步的最标准度量[12，18，38，20，30，33，28，45，47，52]。然而，将相关性度量应用于识别给定序列集中的同步序列一种简单的方法是构建给定序列集合的所有可能子集，并测试每个子集的所有成员之间的成对相关性是否大于预定义阈值。然而，具有n个序列的集合具有2n个可能的子集;因此该方法是不可缩放的。识别同步性的一种流行方法是使用翘曲方法（例如，动态时间规整）[40，41]。虽然存在可以应用于多个序列的方法[55，56，49，50]，但扭曲方法的目的不是识别同步序列的最大子集，因为它们的目标是优化序列之间的时间扭曲路径分支定界（B& B）框架最近被提出用于无监督的时间共性[10]和同步发现[9，8]，但它们所解决的问题本质上不同于我们的方法所解决的问题;那些BB&方法的目的不是识别同步的序列子集[即，的子集满足（3）中的条件]。使用面部视频、金融时间序列和大脑连接数据进行实验。SyncRef可以有进一步的应用，如异常检测[3]，如果异常是manifested与时间序列的一个子集的同步行为2. SyncRef方法我们现在描述如何用所提出的SyncRef方法近似地解决问题1SyncRef的输入是包含所有序列X的集合。SyncRef逐渐过滤掉不相关的序列以产生同步的集合。图1示出了整个框架。我们首先将所有序列转换为时不变的主成分分析（PCA）表示（图1）。1 c）。然后，我们通过在它们的PCA系数上定义阈值来有效地聚类序列（图1）。1 c，第2.2节）。然后，我们扩大集群，以获得所谓的扩展集群（图2）。1d）的情况。我们表明最大可能的同步集合S被保证完全包含在扩展的簇之一中。Fi-最后，我们通过从扩展簇中删除序列来输出同步集，直到满足（3）中的不等式（图2）。1 e、f;第2.4节）。整个过程总结在表1的算法中。2.1. 通过PCA由于SyncRef需要计算序列之间的距离，因此降低输入序列的维数提高了效率。 为此，我们来-通过应用PCA按下所有序列 为此，我们形成一个T×N矩阵X，其列是z归一化的。9495ǫj=1K11 KK1K（一）frame（）102030405060708090（b）第（1）款（c）（d）（e）（f）第（1）款10 20 30 40 5060708010 20 30 40 50 607080图1.SyncRef如何查找同步序列集的说明（a）100×100帧的人脸视频（b）到SyncRef的输入：10，000个序列的集合X第一帧。(c)图示（b）中序列的PCA表示;为了可视化，我们使用两个PCA系数u1，u2。由虚线限定的每个矩形区域（即，thresholdsθj）是一个簇。Cj是最多的集群。（d）扩展的簇C j。（ e）已确定的k同步集合S;圆内的所有点至少通过ρ θ= 0相关。八十(f)在时域上示出的同步序列集：这些序列对应于（a）中微笑激活的嘴部区域周围的像素。表1.总结SyncRef方法的算法是分割的，我们总是将θ0设为−∞，θ M设为∞。的输入：N个序列的集合，X={x}Nk kii=1输出：同步序列S的集合，使得S ≠ X1. 使用等式计算所有序列的PCA表示{ui}i（四）2. 通过计算第2.2的阈值{θj}j，k来确定聚类{Cj}j3. 对于j= l，. - 是的- 是的，M，K，找到属于聚类Cj的所有序列，determination of the other thresholds is explained below.定义1. 一个簇是R K 中的一个集合， 定义如下：K个 阈值区间（θ j1，θ j1 + 1]，. - 是的- 是的 ，（θjK，θ jK +1]为cj1j2. jK：={（u 1，. - 是的- 是的 ，u K）∈ RK：θjk

下载后可阅读完整内容，剩余1页未读，立即下载