在线学习中的自适应隐马尔可夫模型分析与仿真的研究（20字）

可在www.sciencedirect.com在线获取理论计算机科学电子笔记318（2015）109-127www.elsevier.com/locate/entcs自适应隐马尔可夫模型用于在线学习Tiberiu Chis1，2 Peter G.哈里森3英国伦敦帝国理工学院计算机系摘要在现代计算机系统中，不频繁的附加负载的间歇性行为影响性能。通常，存储磁盘或远程服务器的代表性痕迹可能很少，并且获得真实数据有时是昂贵的。因此，随机模型，通过模拟和分析，提供更便宜，有效的解决方案，其中输入模型参数获得。一个典型的例子是马尔可夫调制泊松过程（MMPP），它可以将其时间索引离散化以形成隐马尔可夫模型（HMM）。这些使用离散（或连续）马尔可夫链的基本属性，模型已经成功地捕获了I/O操作和互联网传输的突发行为和循环模式然而学习通过对数据集进行重新训练，在复杂性方面，对这些模型进行重新训练可能是繁琐的。因此，我们提供了一种在线学习HMM（OnlineHMM），它由两种现有的HMM变体组成：第一，滑动HMM使用移动平均技术来更新其参数“上-的”，其次，多输入HMM能够训练上的多个离散的痕迹同时。OnlineHMM显著减少了数据处理时间，因此合成工作负载在计算上更具成本效益。我们衡量的准确性再现代表性的痕迹，通过对原始数据点和HMM生成的合成痕迹的时刻和自相关的比较。我们提出，分析，通过OnlineHMM的自适应Baum-Welch算法节省的训练步骤，并通过仿真获得，平均等待时间的一个嵌入模型。 最后，对本文的工作进行了总结，并对今后的模型扩展进行了展望.关键词：隐马尔可夫模型，在线学习，自适应鲍姆-韦尔奇，自相关，MMPP。1引言在过去十年中，网络和存储系统的性能和可靠性一直是拥有全球在线业务的国际企业的关键问题在大范围内，企业越来越多地面临网络性能可能对其关键IP应用程序、远程桌面或视频会议造成的技术挑战，例如等待时间滞后、可用性和拥塞，以及每个国家/地区不同的实时互联网条件此外，存储数据的成本1感谢Nigel Thomas和UKPEW委员会2电子邮件：imperial.ac.uk3电子邮件：p. imperial.ac.ukhttp://dx.doi.org/10.1016/j.entcs.2015.10.0221571-0661/© 2015作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。110T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109随着用户与服务器的比例不断增长，导致顶级云提供商（即Amazon EC2）之间的竞争用户要求应用程序在平板电脑和智能手机上可用，并期望这些移动设备具有可靠的性能因此，设备、服务器和网络都必须满足由来自相应客户端和供应商的实际服务水平协议（SLA）确定的所需服务质量（QoS）标准。然而，通过不断升级基础设施或增加带宽来保持稳定的网络性能，对于满足大量需求的庞大用户群来说是昂贵的存储.为了解决这些挑战，工程师和研究人员依靠各种方法的组合。从地理上讲，大型系统分散开来，以最大限度地减少位于最终用户和数据中心附近的服务器之间的通信（从而最大限度地减少延迟）。随着不同位置经历可变连接，挑战是为所有用户保持一致的服务，而不管位置如何。在数据包级别，传输分类等方法有助于调节数据包传输和带宽[13]。然而，简单地对IP流量进行分类是不够的（即，还没有对系统负载、等待时间、分组类型、到达突发性等进行建模）。因为非确定性事件规定了传输行为，并且应当被建模以改进存储系统和网络性能以及可靠性。可扩展模型允许试验新的存储系统设计，其中生产系统提供其应用程序的关键特性[3]。因此，需要从存储跟踪中提取代表性的工作负载参数简单的模型，如泊松过程，不再提供现实的工具来模拟互联网传输和存储访问，因为它们无法考虑长距离依赖（LRD）或数据包和I/O命令的突发性。因此，为了改进这一点，研究人员将注意力转向更复杂的模型，如马尔可夫调制泊松过程（MMPP）和隐马尔可夫模型（HHMPM）。事实上，MMPP可以被视为离散索引的HMM，通过观察事件之间的间隔作为随机变量序列[17]。HMM是一个状态和转移的双变量马尔可夫链，由一个隐藏链（具有未知状态）和一个可观察链组成。这样的模型在解释LRD、自相似性、工作中的突发性和切换模式方面更成功，我们将读者的注意力转向类似地，Harrison等人使用Hacks来获得闪存性能模型的输入[3]。尽管这些模型在分类互联网交易和存储访问的属性方面取得了成功，但在静态学习和（不必要的）重复数据训练方面存在不科学性。以在线方式（即“在线”）学习数据的需求文献中的一些集合，其中模型参数用新数据更新[6，11]。特别是增量HMM [11]，通过其适应的期望最大化算法提供了简约性和可移植性，该算法严格地在新数据点上训练。这T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109111工作已经证明，产生参数化模型的计算时间可以显著减少，同时保持模型的准确性。类似的HHMM变体使用基于移动平均值的数据点滑动窗口（即当新点到达时旧点被丢弃），并以在线方式对离散数据进行训练，称为SlidHMM[9]。增量和滑动方法都是逐步更新模型使用这样的模型，人们可以重现有意义的和代表性的工作量的痕迹，模拟现场系统，定量的措施。然而，这种自适应训练是针对每个轨迹执行的，并且有用的升级将是获得能够同时在多个轨迹上进行训练的模型。随着对社交媒体上的在线交互以及跨共享系统和资源的分析，在多个轨迹上训练模型的能力越来越重要。例如，Hacks的变体通过调整k-means聚类和Baum-Welch算法来同时训练多个用户，从而识别Twitter数据中的群体行为趋势[4]。这种多输入HMM（Mul- tiHMM）是对计算昂贵的耦合HMM [19]的改进（随着我们规模的扩大），耦合HMM使用马尔可夫链来表示一个用户，链的耦合是社会交互。尽管MultiHMM节省了计算，但通过参数的增量训练进行改进将有利于在线学习。为了解决上述问题，我们提出了一个在线的，多输入的HMM能够在多个轨迹上以增量的方式进行训练，而不会降低准确性和计算效率。我们采用著名的k-means聚类和Baum-Welch算法来同时支持多个轨迹，并获得离散时间的在线HMM（OnlineHMM）。该模型的应用包括实时系统的传输分类和工作负载基准测试为了验证我们的方法的有效性，我们定量地比较了原始（即未聚类），标准HMM和OnlineHMM 生成的轨迹的矩和自相关。我们的OnlineHMM的另一个效率度量（与标准和HMM变体相比）是模型参数在自适应Baum-Welch算法组件中收敛所需的步骤数。我们的模型的潜在在线应用包括：表征突发性的工作负载模式以预测高活动的峰值;基于在线交互在社会网络中构建用户配置文件;管理具有间歇性活动模式的共享应用程序的资源分配本文的组织如下：在第2节中，我们概述了交易分类的方法，定义MAP和MMPP，介绍HMM算法，总结现有的HHMM变体，并解释如何合并各种模型特征以形成一个更好的在线模型;第3节建立了OnlineHMM，并提供了相关的模型，模型训练和仿真;在第4节中，我们给出了结果来验证OnlineHMM对其他模型变体的效率，并获得了表示抽象存储设备的相关存储模型的平均等待时间;第5节是为结论和今后的工作保留的。112T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）1092背景在本节中，我们将描述现有的交易分类模型，包括MAP和MMPP，并解释它们与HALF的关系。 我们探讨了这些模型的适用性，相关的应用程序和Osunier简单的扩展到eaking理论分析其他系统功能。然后，我们介绍了HMM训练算法，并定义了用于收敛HMM参数的迭代公式。OnlineHMM由两个主要过程组成：第一个是使用移动平均技术学习数据的滑动窗口;第二个是自适应k均值聚类技术，要求在将轨迹作为输入传递到在线Baum-Welch算法之前对其进行双重聚类。 我们在本节中概述了这两个过程，解释了当这些过程合并时，新的在线学习方法是如何工作的，并讨论了由此产生的优势。2.1MAP和MMPP对Internet传输的分析和分类对于理解、规划和设计健壮的大规模工作负载模型至关重要存在不同类型的交易分类。按端口号进行分类速度很快，并得到许多网络设备的支持，但只对使用固定端口号的应用程序有用。相比之下，深度数据包检测（DPI），它检查数据包的有效载荷，是缓慢的，需要更多的资源，使用这种方法很少超过加密。另一种方法是统计分类，并将传输数据视为多维时间序列，这提供了一些优于上述方法的好处：比端口号分类更快的技术;通过分析数据包大小和数据包到达间隔时间，可以更深入地了解不同时间的系统行为;数据包到达的周期和突发性可以使用这种方法检测。与Internet传输类似的应用包括记录存储访问时间的时间序列和磁盘上I/O命令的序列当使用这种技术来构建工作负载模型时，设计和规划过程可以在时间和成本方面变化。在一端，有大规模的云服务模型，如基础设施即服务（IaaS）、平台即服务（PaaS）和软件即服务（SaaS），它们处理在分布式服务器集群上收集的数据在另一端，随机模型，如马尔可夫到达过程（MAP），批量MAP [18]和相位型分布提供了更多的分析工具。因此，存在一系列用于分析时间序列的模型，其中最简单的模型之一是对到达间隔时间进行建模的泊松过程（PP）。 的PP是一个连续时间随机点过程，其中到达时间间隔（事件之间）是独立的和指数分布的。这个过程可以通过将时间戳数据划分为“bin”来区分，并转化为可移植的离散时间随机过程或时间序列。此外，PP被MAP概括，MAP根据连续时间马尔可夫链（CTMC）中的转换而演变[10]。我们在定义2.1中正式定义了MAP：定义2.1设Q=D0+D1是CTMC的无穷小生成元，其中D0和D1是方阵（具有D0和D 1的非负对角元素）。T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109113ΣΣi=10⎝λ⎠D1的元素）。然后，MAP（D0，D1）是一个点过程，在该点过程中，通过与D1相关联的转变，在CTMC中发生事件。二阶MAP（D0，D1）（即MAP（2））具有参数：D=−（σ1） α12α21⎞⎠andD=λ11λ1221 λ22其中σ1= α12+jλ1j;σ2= α21+j λ2j; α ij≥ 0是从状态i到状态j的隐藏跃迁; λ ij≥ 0是D 1的可观测跃迁，其中i，j = 1，2。一 个 子 集 的 地图 ， 认 为 工 作 类型 的 到 来 是 马 尔 可 夫 调 制 泊松 过 程（MMPP）。事实上，当D1（根据定义2.1）是对角矩阵时，MAP就变成了MMPP。MMPP的优点包括用于到达间隔时间之间的相关性的封闭形式表达式和对多个作业类型进行建模。例如，在后者的情况下，MMPP（2）（即具有两个状态的MMPP）充当作业到达过程，其在具有到达率λ1的频繁到达（状态1）和具有到达率（λ2）的较少到达（状态2）的时段之间切换，其中λ1> λ2[8]。因此，MMPP（2）的无穷小生成元（即D=D0+D1）定义如下：D=λ1−（α12+λ1）α12+ 0⎞α21−（α21+λ2）<$⎝0λ2⎠其中αij是从状态i到状态j的隐藏转换，i，j= 1， 2。通过使用MMPP，人们可以推断出作业到达之间的相关性，其中底层属性适合各种存储和互联网工作负载时间序列的行为。例如，以一个准生灭（QBD）过程为例，图1显示了一个MMPP/M/1队列，MMPP（2）到达（λ1或λ2），指数服务时间（μ），一个服务器和状态之间的转换（α12或α21）。请注意，可指定多个服务时间比率（即：μ1和μ2）在超临界模型中，例如超临界模型，指数服务器的概率（2pi= 1）的利率。主要好处将MMPP集成到一个嵌入系统中的方法是创建一个复杂的抽象，服务器行为和模拟测量，否则很难从实际数据中获得。μ μ μ...α12...Fig. 1. MMPP/M/1的QBD过程从图1中，可以看到MMPP和HPLF之间的相似之处，即通过状态的内部转换切换模式。为了能够对抵达进行分类-λ1λ1λ1α21α 12α 21α 12α 21μ μμλ2λ2λ2−（σ2）1114T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109对作业进行工作负载基准测试和MMPP分布式任务的调度很有用，但这只是更广泛目标的一部分通过将服务器建模为嵌入式系统的一部分，人们可以理解并（理想情况下）预测云和文件存储应用程序中现代服务器的等待时间、可变负载、系统瓶颈和资源分配。在4.4节中，我们将MMPP合并到先来先服务（FCFS）队列中，并获得不同负载的平均等待时间。流体输入模型，例如MMPP，可以具有离散化的时间变量，例如HMM，其建模更简单，并且具有类似的强大的流量分析。事实上，Hondrance的一个优点是它的简约性，它允许在工作负载模型中表示时变的、相关的传输流。在下一节中，将介绍基本的HMM算法。2.2隐马尔可夫算法为了构建OnlineHMM并用作工作负载模型的输入，我们首先调整用于训练模型的标准HMM算法。研究中的统计算法解决了与HST相关的三个基本问题：首先，获得P（O;λ），或给定模型λ的观测序列O的概率;其次，通过调整给定观测序列O的λ的模型参数来最大化P（O;λ）;第三，确定观测序列O的最可能隐藏状态序列S。这些问题分别由三种算法解决：前向-后向算法（FBA）[1]、Baum-Welch算法4（BWA）[2]和Viterbi算法（VA）[7]。FBA和BWA训练HMM参数直到收敛，我们将在下一节更详细地描述这些算法，包括模型参数和递归方程。事实上，由等式（4）定义的BWA重新估计公式仅对固定大小的单个迹线起作用，并且BWA的有用升级是处理用于以在线方式表征离散数据的多流此外，我们适应FBA和BWA模型多输入过程使用聚类技术，并添加了一个高效的，更新技术使用滑动窗口，形成OnlineHMM。2.3前向后向算法前向-后向算法（FBA）解决了以下问题：给定观测序列O =（O1，O2，.，OT）（即T是观测集的大小）和模型λ =（A，B，π），计算P（O; λ）（即给定模型，O的概率），并获得O的似然性。λ的参数是：状态转移矩阵（A），包含从一个状态移动到另一个状态的概率;观察矩阵（B），每个状态发出观察的概率;初始隐藏状态分布（π）。基于[12]中的解决方案，我们提 出 我 们 将 前 向 变 量 αt （ i ） 定 义 为 ： 给 定 我 们 的 模 型 λ ， O 在 时 间 t（1≤t≤T）和状态qi在时间t的概率。所以，α t（i）= P（O1，O2，.，0 t，st= q i; λ），其中i = 1，2，.，N（即N是4.该算法迭代地使用FBAT. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109115ΣΣNΣ不ΣP（O;λ）不不Σj=1HMM中的隐藏状态），t = 1，2，.，是时间t的状态。α t（i）（对于i=1，2， . . . ， N）初 始 为α1 （i） =πibi （O1），并递归地定义（ 对于t= 2，3，...，T）如下：Nαt（i）=[ αt−1（j）aji]bi（Ot）（1）j=1其中αt−1（j）a ji是O1，O2，. Ot−1被观测到（g i venbyα t−1（j）），并且存在从时间t−1的状态qj到时间t的状态qi的转变（g i venbyaji）;bi（Ot）是Ot从状态q i被观测到的概率。类似地，我们可以将后向变量βt（i）定义为从时间t+ 1到结束的观测序列的概率，给定时间t的状态qi和模型λ。 则β t（i）= P（0 t+1，0 t+2，. 0 T; s t= q i，λ）。 β t（i）（i = 1，2，...，N）最初由β T（i）= 1给出，并递归定义（对于t = T − 1，T − 2，...，1）如下：Nβt（i）= aijbj（Ot+1）βt+1（j）（2）j=1其中观测值Ot+1是从ny状态qj 生 成 的。 对于α和β项的进一步分析，读者可以参考第2节。3 [15]。通过计算α和β值，可以定义BWA迭代方程。2.4Baum-Welch算法给定模型λ =（A，B，π），Baum-Welch算法（BWA）在固定的观测集O=（O1，O2，.，O T）。通过调整其参数A、B、π，BWA使P（O;λ）最大化。如第2节所述。3 .第三章。2，迭代地更新BWA的参数（对于i，j= 1，2，.，N，且t= 1，2，.，T-1）如下：n（i，j）=αt（i）aijbj（Ot+1）βt+1（j）;γ（i）=nn（i，j）（ 3）其中，t（i，j）是路径在时间t到达状态q i并在时间t + 1转换到状态qj的概率。对一组观察结果求和，我们可以获得从任何任意状态或到任何任意状态的预期转变次数的值。因此，更新我们的HMM参数很简单：T−1t（i，j）不γt（j）aJ= t=1;bJ（k）=t=1，Ot=k;πJ=γ（i）（4）ijT−1t=1Jγt（i）不t=1I1γt（j）我们现在可以使用λJ=（AJ，BJ，πJ）迭代地重新估计我们的模型参数，其中AJ={aJij}，B J={bJj（k）}和πJ={πiJ}，这是一个定义（4）。请注意，对于大型观测集，由于值趋于零，因此建议将这些项归一化[14，15]。116T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109j=1j=1⎠⎝Σ2⎛Σ2.5障碍的变化要理解OnlineHMM，我们必须首先分析组成它的过程。第一种是滑动HMM（SlidHMM）[9]的适应，它基于简单的移动平均，并使用滑动窗口技术进行数据测量。第二种是多输入HMM（MultiHMM），能够同时在多个离散轨迹上进行训练。OnlineHMM试图合并这两种技术，并创建一个新的在线学习工作量基准。2.5.1滑动HMM滑动窗口的概念，以更新数据集上的HMM参数的训练上，在运行时的性能和在线工作负载表征方面是有吸引力的通过用新到达的数据更新数据集，同时丢弃最旧的观测值，人们可以简单地测量时变过程滑动窗口效应改进了IncHMM [11]的增量学习，IncHMM积累了越来越大的观察集，因为过时的数据点被包括在HMM参数的迭代更新为了实现SlidHMM，对HMM算法进行了修改。FBA，从而创建向前递归向后近似。因此，BWA适应于新的FBA并且相对容易地更新HMM参数。首先，我们描述向后近似背后的原理，它使用α和β值。假设HMM是在T个观测的离散迹上训练的，并且M个新观测被添加到这个集合中。 为了更新我们的模型，我们首先使用FBA定义α T+1（i）=[<$Nα T（j）aji]bi（OT）。TheKnowofthe项αT（j）、aji和bi（OT）都给出了新的α变量，可以使用前向递推公式 然而，找到βT+1（i）更困难，因为它取决于一个步骤来锁定头部（即， βT+1（i）=<$Nai jbj（OT+2）βT+2（j）），不幸的是，βT+2（j）的值是未知的。通过调整β变量的近似值[6，11]，可以获得与α项类似的前向递推公式。然后，一旦α和β集合是完整的，则可以容易地获得BWA变量（α，γ，aJij和bJj（k））。β近似假设βt（i）=δ（t，i）是一个连续函数，参数为t（时间）和i（状态）。对于任意状态i，函数δ（t，i），w.r.t. t从0增加到1。等价地，当t→0时，δ（t，i）趋于0。 从t=T−1到t=1的所有β项都小于1，并且随着t的每一步减小，通过向后公式（2）的计算，βt（i）趋于0。因此，对于大的观测集，我们得到近似等式δ（t，i）<$0<$δ（t，j），其中i和j是不同的状态。β近似定义如下：βt（i）βt（j）（5）我们使用等式（5）将向后递归公式转换为向前递归首先，设N= 2，等式（2）给出：中文（简体）2j=1 a1jbj（Ot+1）βt+1（j）中文（简体）=j=1a2jbj（Ot+1）βt+1（j）⎠T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109117O（O）+a b（O）ΣΣt=2Σt=2IJΣγT+1γ（j）tγT+1γ（j）tJ电话+1t=2IJNj=1不t=2 t（i，j）+t=2t=2γT+1γt（i）γT+1γt（i）t=2γT+1γt（i）IJγT+1γt（i）bT+1（k）=t=2，Ot=k t=T+1，Ot=k为t=2塔布t=2（k）+t=T+1，Ot=kt=2取βt（1）并在RHS上展开求和，我们得到：βt（1）=a11b1（Ot+1）βt+1（1）+a12b2（Ot+1）βt+1（2）假设t+ 1非常小，并利用（5），我们推导出βt+1（1）βt+1（2），得到：β t（1）<$β t +1（1）（a 1 1 b 1（O t +1）+a 1 2 b 2（O t +1））=βt+1βt（1）（一）11 1t +1 12 2t +1（六）对状态i的推广产生了我们的前向递归β近似[11]：β（i）β-环己二烯βt（i）一IJ（七）电话+1使用（7）中定义的β近似，我们以向前递归的方式执行FBAα-pass和β-pass。在新观测{OT+1，OT+2，.，O T+M}时，γ和γ值仍由等式（3）定义。由于观测值是按顺序添加的，因此我们以增量步长定义了HMM参数（A，B，π）的修改后的重新估计。最初，对于i=1， . . . ， N，我们有π π∈IJ=γ1（i）。对于A组，我们有：aT+1=Tt（i，j）+j=1 T+1（i，j）=Tγt（i）γTt（i，j）γt（i）+T+1（i，j）t=2=Tγt（i）aγT+T+1（i，j）t=2因此，对于OT+1，仅需要计算新的γT+1（i，j）和γT+1（i），因为对于1 ≤ t ≤ T，将t（i，j）值存储在a_T_n树中。请注意，从和中减去t=1 h，然后丢弃更新的值。对于B组，我们有：联系我们Jγt（j）+ΔT+1不t=2γt（j）电子邮件γ（j）TJ简体中文γt（j）其中，更新γ T+1（j）（使得O T+1= k）是足够的，因为先前的γ值包括在nbT（k）中。一旦HMM参数（Aβ，Bβ，πβ）被确定，模型就准备好生成具有底层模型分Nj=1bj（O）不t=2γt（j） +γT+1（j）118T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109布的合成工作负载轨迹。作为SlidHMM的一部分，滑动BWA的能力在于减少了前向和后向变量的计算（仅在新数据上），从而收敛了模型参数T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109119i=122≤比传统的BWA更快。如果我们在T个新的观测值上连续k次训练模型，那么与SlidHMM（S2）相比，训练标准HMM（S1）所需的额外步骤是步骤（即S1-S2）的差异，由下式给出：S1−S2=（T+2T +.. . +kT）−（T+T+.. . +T）=（Tki）−kT=Tk（k+1）−kT=Tk（k−1）随着SlidHMM方法的评估，OnlineHMM的另一个功能是BWA的多输入自适应，我们将在下一节中描述2.5.2多输入HMM多输入HMM（MultiHMM）[4]由k均值聚类算法和加权BWA组成，它同时在多个跟踪时刻的比较。我们提出了双聚类方法和完整的MultiHMM算法。用于预处理BWA训练的输入迹线的简单聚类技术是k均值，其将来自H迹线（即H元组）的数据点分组为K个不同的聚类[15]（K H）。 来自所选择的输入轨迹的每个数据点属于C类别中的一个，这在聚类期间为H元组产生HC组合。为了避免这种高组合值，Chis等人通过将来自同一聚类的数据点分组在一起将H迹线减少到K，然后在BWA训练之前为每个迹线分配权重。算法1中提供了MultiHMM的伪代码，该算法以相等的概率（即，ωk= 1/K，其中1≤k≤K）初始化所有K个轨迹的权重ωk一个扩展是根据每个轨迹的各个特征的强度来优先考虑这些权重，并定义MultiHMM的变化在定义了多输入特征（改编自MultiHMM）之后，下一个目标是将此过程与上述改编自SlidHMM的滑动窗口学习技术组合在一起。下一节将合并这两个有用的属性，以实现一种新的OnlineHMM学习算法。3OnlineHMM分类在本节中，讨论OnlineHMM的参数。 这些方法包括跟踪收集、分箱过程、k-均值聚类技术和OnlineHMM的参数初始化。3.1Netapp和Microsoft跟踪我们收集了数百万个I/O命令（即带时间戳的读取和写入），来自通用Internet文件系统（CIFS）网络跟踪（约500 GB）。这些文件服务器位于联合国总部，120T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109ΣΣΣΣˆΣˆ我中国电子邮件Σ算法1使用MultiHMM进行训练[4]要求：K个群集的轨迹长度=轨迹长度ωk=权重对于i= 1：H，原始迹线而群集点不固定迹i上的K均值聚类结束while结束for对于j= 1：K，组j={}对于t= 1：size，i= 1：Hdo，如果Pointi（t）∈Cluterj，则（t）i（t）i（t）如果结束，则结束端当BWA参数不收敛时，k= 1：K个观测迹α=Ni=1ωkαi;β=Ni=1ωkβi;ωk=Ni=1ω ki端N不不T−1 t（i，j）1IJ不γt（j）Jγ（i）=（i，j）;πJ=γ（i）;aJ=t=1;bJ（k）=t=1，Ot=kT−1t（i，j）γt（j）end whilej=1t=1t=1使用各种应用程序的Windows台式机和笔记本电脑。因此，这两种类型的跟踪被表示为“Netapp读取”和“Netapp写入”。同样地，我们从可用服务器收集Microsoft存储数据，并将顺序I/O命令划分为读和写（即“Microsoft读”和“Microsoft写”）。随着跟踪数据的收集，读取和写入被划分到统一的固定大小的间隔）。箱大小应代表数据中存在显著方差的区间（即避免太多空区间），并选择1秒区间一旦轨迹被分箱，我们应用双聚类k均值算法[4]，如第2.5.2节所述。我们选择了11个集群的初始化，优化后的距离为基础的聚类算法在试运行。在k-means聚类之后，我们获得了具有读取和写入值的11个质心对的向量，这些质心对表示各个聚类。最后，通过将数据点（即每秒读取或写入的次数）分配给数据点对应的群集（即1到11之间的整数）来转换原始轨迹。因此，这个j=1T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）1091213.2OnlineHMM训练和仿真OnlineHMM有两个隐藏状态，自适应BWA在观测值上训练，直到参数收敛（即A，B，π变得固定）。在线BWA沿着数据集滑动，数据集逐渐更新，并同时在多个轨迹上训练。它是SlidHMM和MultiHMM的自适应BWA的组合，但减少了两者的参数收敛时间。随着每个新点添加到数据集，过时的点被OnlineHMM丢弃，同时参数被更新。因此，OnlineHMM首先在T个观测值上训练，然后在M个新观测值上训练（即在M个幻灯片中），现在保留T+M个数据点上的信息。标准的HMM在T个数据点上训练，然后在T+M个点上重新训练，等等。对于我们的模拟，我们初始化A，B和π等概率分布和T范围从500到100000秒。我们执行多达10000个连续的幻灯片使用- ing Netapp和微软的读取和写入，多达1000个跟踪组。一旦参数收敛，模型就生成单独的合成轨迹。请注意，同一个OnlineHMM生成多个跟踪（一对多关系），而标准HMM只生成一个跟踪。这是在线隐马尔可夫模型相对于标准隐马尔可夫模型的一个明显优势.我们获得原始和合成读取和写入的平均值、标准差、偏度和自相关，我们将在下一节中介绍。4结果4.1平均值、标准差和偏度我们使用原始、HMM和OnlineHMM生成的数据点计算了Netapp和Microsoft读取和写入的离散跟踪的统计数据。已对特定迹线进行了1000次模拟，并以95%置信区间对每个箱进行了相应统计评估。例如，表1显示了HMM生成的Microsoft读数的平均值为“48. 84 ± 0。08”，表明HMM平均产生48。每秒84次读取，置信区间为0。08.此外，“Fourth Microsoft read after no slides”意味着我们选择了第四个跟踪（从一组中的1000个）的Microsoft读取，其中在训练期间没有添加新的读取（即，没有载玻片）。 表1至表5列出了各种痕迹。正如预期的那样，HMM提供了更好的均值和标准差估计。OnlineHMM中使用的聚类技术和向后近似方程可能是造成这些估计值差异的原因。尽管如此，OnlineHMM满足准确性的最低基准，有时优于标准HMM（表1和表5）。122T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109表1无幻灯片后的第四次Microsoft读取：Raw，HMM和OnlineHMM微量是说STD Dev偏度原49.09167.494.32嗯48.84 ±0.08164.76 ±0.164.36 ±0.012OnlineHMM49.09 ±0.14165.66 ±0.314.29 ±0.008表2第六次微软写后没有幻灯片：原始，HMM和OnlineHMM微量是说STD Dev偏度原0.6630.1641.019嗯0.665 ±0.0020.162 ±0.0020.96 ±0.012OnlineHMM0.620 ±0.0010.219 ±0.0011.102 ±0.009表3五张幻灯片后的第二次微软阅读：原始，HMM和OnlineHMM微量是说STD Dev偏度原47.87166.344.36嗯46.78 ±0.25160.61 ±0.504.51 ±0.013OnlineHMM51.39 ±0.12149.21 ±0.304.75 ±0.009表4四张幻灯片后的第四次Netapp写作：原始、HMM和OnlineHMM微量是说STD Dev偏度原0.4310.124-0.365嗯0.431 ±0.0010.122 ±0.002-0.409 ±0.004OnlineHMM0.409 ±0.0010.214 ±0.001-0.269 ±0.009T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109123Σ=t=1Nt=1 （年不表5九张幻灯片后的第一个Netapp阅读：原始、HMM和OnlineHMM微量是说STD Dev偏度原100.96248.522.54嗯102.07 ±0.60245.35 ±0.682.6 ±0.012OnlineHMM 102.77± 0.25 250.81±0.33 2.51 ± 0.0044.2自相关自相关的一个主要好处是观察自相关时间序列中的趋势或周期由于自相关是标准化的自协方差，不幸的是，这两个术语有时在工业中互换使用。观测值y1，y2， . ，yN（平均值为y<$）定义如下：）（yt+k−y）我们研究了Microsoft和Netapp数据的ACF，并将这些原始（即未聚类）数据点与HMM和OnlineHMM生成的相应合成轨迹进行比较。图二. Netapp读取的自相关。p（八）K-y'）2124T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109图三. Netapp写入的自相关。图2显示了原始、HMM和OnlineHMM Netapp读取的ACF中的不同行为原始读段的相似性最好由OnlineHMM在滞后140到160时捕获，其中ACF大于零。值得注意的是，在滞后170附近，原始数据中的两个跳跃被OnlineHMM中的两个尖峰增强，与HMM的相关性很小。类似地，图3显示了OnlineHMM匹配的原始写入行为（滞后65到70），与HMM写入没有相关性。事实上，这种ACF的匹配赋予了OnlineHMM作为突发分类器的能力，应用于磁盘和文件服务器的I/O管理和资源分配见图4。 Microsoft读取的自相关。T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）109125图五. Microsoft写入的自相关。在图4中，原始、HMM和OnlineHMM读取几乎没有ACF然而，在滞后100处以及在滞后118至130期间，HMM读取表现出ACF中的跳跃，这与由原始和 OnlineHMM 读 取 两 者 给 出 的 ACF 行 为 的 跳 跃 不 同 。 图 5 再 次 展 示 了OnlineHMM的强大功能，这一次是针对微软的写入，滞后213到217;唯一模糊地表示原始写入的任何重要ACF值的模型是OnlineHMM。从模拟结果到更多的分析结果，下一节介绍了OnlineHMM在自适应BWA收敛方面的优势。4.3BWA的融合标准HMM（使用BWA）批量学习的空间和时间复杂度为O（N2T），其中T是迹长，N是隐藏状态的数量。表6呈现了两状态HMM及其变体（即，SlidHMM，MultiHMM和OnlineHMM）测量以下内容：第一，当模型在H个不同轨迹上训练时BWA的收敛;第二，数据集中K个增量更新的BWA收敛（即K个幻灯片，每个幻灯片添加一个新数据点）;第三，H个轨迹上K在所有模型中，OnlineHMM在空间和时间复杂度方面受H和K缩放的影响最小。表6使用HMM、SlidHMM、MultiHMM和OnlineHMM的BWA变化的收敛率模型H轨迹K滑块K滑块H轨迹HMMO（HN2T）O（N2（T+K（T+K+1）））O（HN2（T+K（T+K+1）））2 2SlidHMMO（HN2T）O（N2（T+K））O（HN2（T+K））O（N2T）O（N2（T+K（T+K+1）O（N2（T+K（T+K+1）2 2O（N2T）O（N2（T+K））O（N2（T+K））126T. Chis，P.G.Harrison/Electronic Notes in Theoretical Computer Science 318（2015）1094.4排队模型建模作业到达（即数据