论文部分内容阅读
九、核心丛集法(kernel-based clustering)
核心丛集法的发展动力在于转换数据维度的困难性，依据Mercer理论可知，各维度所产生的困难性，可利用核心转换的方式加以克服。之所以如此转换是因为运算复杂度(computational complexity)对于大型数据集上之应用而言具有关键性的地位，对现在许多线性算法而言，在建构平方和(sum of squared)丛集法与K-means算法的过程，其均展示了一个非常好的非线性再公式化的例子。对于这些非线性变量能否保持原始算法某些有用而重要的属性之研究，目前也是一个重要的议题。此方法的应用例子目前已有许多，例如B. Schlkopf、A. Smola以及K. Müller便曾在在线模式中(on-line mode)描述了一个核心K-means方法(kernel K-means algorithm)。在其方法中，假设我们有d维度之模式集合xj，j=1,…,N；以及一个非线性对应，在此F表示一个具有任意维度之特征空间。该算法的客观面，表示要找出K个中心点，以方便我们最小化这些对应模式(mapped patterns)之间的距离以及他们所最接近之中心点，运算方式如下：
其中ml表示为第l个丛集，而k(x,xj)＝Ф(x)．Ф(xj)表示内积核心。我们可以定义一个丛集旗标变量Cjl，如果其值为1，表示xj属于l丛集，否则将其值指定为0。核心式学习算法的运作理论，乃基于覆盖(cover)理论而来。
也就是说，藉由非线性转换一个复数集合与非线性可分模式到较高维度之特征空间(features space)，以取得以线性方法分别此模式的可能性。藉由设计及计算核心内积(kernel inner-product)，我们可以节省时间的耗费，有时甚至可以将非线性描述过程，加以对应并计算其在已转换空间中的对应点(corresponding points)。J.Corchado及C.Fyfe提议了两种变异的核心K-means算法，其研究的动机乃来自SOFM及ART网络概念，这些变异方法在调整丛集指定变量时，会把邻近关系所产生的影响纳入考虑，并使用“警惕参数(vigilance parameters)”来控制平均向量的产生过程。另外2002年M. Girolami所提议的“替代性核心丛集法”亦颇具意思，其将丛集化问题公式化成侦测一个函数Г最佳化部分的问题，并同时将特征空间之群组的散布矩阵(scatter matrix)最小化，即是，他们在此以RBF函数(radial basis function)作为其核心函数。不同型态的核心函数效果，可在大量的文献中到相关的研究，而此领域亦为研究核心丛集算法时一个颇具潜力的领域。目前有许多人研究核心式的丛集法，其因素有很多，但最主要的是因为核心式丛集法具有以下一些优点：
1. 更易取得线性的可分离性：
在高维度超平面(hyperplane)或无限维度之特征空间更可能取得线性的可分离性。
2. 所形成之丛集形状种类多样化：
除了形成超球体(hypersphere)以及超椭圆体(hyperellipsoid)形状之外，他们也可以形成任意的丛集形状。
3. 噪声与分离体抗性问题：
一些核心式的丛集算法，具有处理噪声及分离体干扰问题(例如：SVC法)。
4、不需要先有侦测系统拓朴结构的先验知识：
对SVC方法(如后叙)而言，其不需要具备侦测系统的拓朴结构的先验知识(prior knowledge)，其核心矩阵仍可以提供平均向量，以估算丛集数目。
虽然核心是丛集法有着上述几项优点，但是并不代表其是完美的方式。目前这领域仍存有一些争议，尚待解决，不过在综合说来这种方法还算可被接受的一种方式。在传统的核心K-means算法计算方式里，其首先要用一个xi来起始化中心点ml。其次，取得xi+1并计算C(i+1)h。如果C(i+1)h＝1，则表示对所有j≠h之情形，其||Ф(xi+1)-mh||2<||Ф(xi+1)-mj||2。若C(i+1)h＝0则表示属其它情形。然后，令C(i+1)h与的比值为，则利用式子更新平均向量(mean vector)－mh，使其所对应的C(i+1)h＝1。对每个Ф(xj)而言，如果j≠i+1，则，若如果j=i+1则，以调整系数。这种计算C(i+1)h、平均向量之更新以及系数的调整过程会一直进行，直到完成“收敛(convergence)状态”为止。其它比较重要的丛集算法还有SVC(support vector clustering)丛集法，这种方法是A. Ben-Hur、D. Horn、H. Siegelmann及V. Vapnik在2001年时所提出的新的丛集方法，以便在原始数据空间找到丛集的边界轮廓集合，这些轮廓可以藉由对应回去转换特征空间中最小的封闭球形来取得。在SVC的方法里面，其可形成两种丛集，一种称为“分化阶层丛集(division hierarchical cluster，DHC)”，另一种称为“同化阶层丛集(agglomerative hierarchical cluster，AHC)”。都某些点被允许存在于超球体(hypersphere)之外时，SVC可以更有效率的处理分离体(outliers)的问题。此外还可以将SVC与fuzzy结合使用，此方面的延伸例子可以在J. Chiang及P. Hao(2003)的研究里找到，有兴趣的读者不妨参考看看。
十、循序数据(sequential data)之丛集化
循序数据和其它数据不太相同，其中次序性(或称为“时序依存性”)是其重要特征。也就是说，这种数据通常是依据变量长度排列，并具有与其它数据不同的特性。例如：具有大量空间需求，具备动态行为之使用与时间上的限制。循序数据的处理以往均为数据处理之重点，如今此类数据在大型数据分析里面又重新获得重视，主要要归功于两种循序资料来源的取得。第一种重要的循序数据来源，便是基于人类基因解读计划(HGP)而来的大量DNA序列(DNA sequences)数据，如何找寻基因序列与某种疾病或蛋白质之间的关系，已成为目前生化研究领域上一个非常重要的领域。藉由疾病辨识的基因疗法，将使一些难治的疾病出现治愈的一线希望；其次，另一个重要的循序数据来源，主要是自然语音处理程序的需求。这类需求随着监控安全自动化的趋势越显重要，尤其是搭配脸部辨识等其它生物特征辨识系统，与语音自然处理DSP，建构起更精确的生物特征辨识系统，以维护国家社会，并进而建立24小时的全天候小区安全监控能力。往后这类技术纯熟之后，各路口的监视摄影机将可搭配国家犯罪数据库，以实时辨识搜寻的方式，找寻可能的犯罪嫌疑人所在，并自动由系统通知附近警网前往拦截。因此美国、英国等先进国家，莫不强化此项技术的发展应用，尤其在国际机场的安全辨识上面，该系统将对反恐行动提供非常大的帮助。其它循序数据的重要来源还包含医学诊断数据(medical diagnosis)、文字探勘(text mining)、股票市场(stock market)数据以及客户交易数据(customer transactions)…等等。
自从计算器处理信息能力大幅提升之后，循序数据的数量可谓大幅增加。尤其是生化上大量的基因序列或蛋白质序列数据，亦促使传统研究方式发生潜移默化之变化。然而要探索这些庞大序列数据内的潜在模块并非易事，并且长久以来便存有应用方法上的争议。今日大家所热衷的丛集分析技术，亦只是其中一项时代演进下被用来作为探索之工具而已。一般而言，循序丛集化(sequential clustering)的技术可概略区分为三种不同的类别：第一种类型是利用序列之间的相似度(sequence similarity)为运算基础；第二种类型是统计式的序列丛集法(statistical sequence clustering)；第三种类型是间接序列丛集法(indirect sequence clustering)。这三种方法所应用之原理，我们简述如下：
(一)序列相似法：
这种策略运作原理，主要是基于测量序列中待测组与比对组之间的序列相似度(或称为pair之间的距离)为基础。然后再利用阶层算法或是部分丛集法来将这些序列群组化，在DNA或是蛋白质的氨基酸序列(amino acid sequences)中，因为其序列多以英文字母为排列方式，故传统的测量方法对这些数据的测量可能便不适用。如果一个序列之比较可视为一种序列间的转换过程(例如：利用一连串的运算子，像是：插入、删除、取代…等等来完成转换)，则此两序列间之距离，可被定义为所需使用的运算子(operators)数目，运算子的使用需求量少，表示此两序列的相似度高。一个常见的分析过程便是组合配对( alignment)，而其内容之配对结果可分为四种状况，分别是吻合(M)、取代(S)、插入(I)以及删除(D)，兹表示如图6。
在图6此种配对分析法里面所定义的距离是大家所熟知的编辑距离(edit distance)或是Levenshtein距离，这些编辑运算(edit operation)是可以根据某些先验知识与其中的距离，以及和完成转换之最小成本，来作为增、减的加权方式，在此两序列之间的相似度或是距离可以被重新公式化成一个最佳化的组合配对问题，其在动态规划(dynamic programming)中可以适用的非常好。如果给定两个序列X=(x1,…,xN)以及Y＝(y1,…,yM)，则其基本的动态规划序列比对算法，可以利用著名的Needleman-Wursch算法为之，其可以下面递归程序来描述：
其中S(i,j)为被定义为两个序列片段之间所比对的最佳比对分数( alignment score)；而e(xi,yj)、e(xi,)及e(,yj)分别表示组合配对xi到yi的成本、组合配对xi到空格(gap，以表示)的成本及组合配对yj到空格的成本。每个i、j位置的运算结果均会被纪录到指针数组里面，其存有目前最佳化之运算及提供一个有效的路径可回去追踪这些组合配对。在Needleman-Wursch算法中，其会比较两个序列的全部长度，已完成全域(global)最佳配对的取得，不过要注意的是在许多环境中，有时找出局部相似度也是一项很重要的工作。在此方面，Smith-Waterman算法允许我们起使一个新的组合配对，并允许在组合配对之动态规划时，可在任何位置停下来。不论其为全域或是局部的组合配对算法，其运算复杂度均为O(NM)。因此在需要比较整个序列组合时，此运算成本将会变得非常可观。为解决此问题，R. Durbin等人及D. Gusfield提出了另一种改良方法，其可加快运算速度并降低些许运算成本，此方法对于生物序列分析(biological sequence analysis)具有相当大的帮助。当然该方法除了可被用在生物序列分析上之外，其对于探索模式探勘(pattern mining)与自然语音辨识(speech recognition)的应用上亦颇具效益。
(二)统计式序列丛集法
不像前面的方法着重于静态位置之计算，这种方法是利用统计模型来描述两序列之间的“动态关系”，其可被用于数值序列或是类别式序列中。为了使我们得以正确解译数据中的特征，模型的选择变成了胜败关键。可惜值至目前为止，并没有一套标准可供我们在选择模型时参考，模型的选择目前仍非常复杂且其中存有相当多的影响因子。因此在动态关系的描述上，目前最重要的方法还是要属隐藏马可夫模型(hidden Markov models，HMMs)，这种方法目前被广用在脸部辨识与语音的辨识应用上。在这种模型上，每个HMM的起始分布决定，乃依据每个丛集之先验机率而来，其基本的学习过程开始于各个参数起始化策略，以先对每个序列形成一个初步的对数可能性(log-likehood)切割来作为距离之测量，此切割会进一步经由典型的EM算法来对所有序列施以HMM训练后被精致化，并利用蒙地卡罗交互确认法来评估可能的丛集数目。而HMM之下一个状态之决定乃依据状态移转分布(T)所决定，并依据放射分布(E)来产生所对应的字符。此过程会不断重复，一直到完成最后状态为止。在此过程中其会产应连串的观察字符(observation symbol)来取代状态，此即说明了此方法之所以被称为“隐藏”马可夫模型的意思。1996年的时候，P. Symth曾提出了一种基于HMM的丛集模型，该模型与混合密度丛集法所楷橥的理论概念非常类似，其同样是利用机率分布来决定丛集的产生，不过其中较大的差异点，在于其使用的机率模型是HMM模型而非一般大家使用的t分布或高斯机率模型。除了形成有限的混合密度之外，混合模型也可以被描述成一种具有HMM移转数组之平均移转数组(means transition matrix)。
有关HMM的详细理论描述，可以参考1989年L. Rabiner的相关研究文章，因为该理论已经广被使用在各种领域，因此其重要性也就不言而喻。实务上常使用离散的隐藏马可夫模型来描述一个不可观测的一连串状态之机率推移过程(stochastic process)，此一连串状态彼此间的关系乃依据机率高低而定其转变机率，一个HMM的定义如下：
1.存有一个Q状态的有限集合V，其中V＝{v1,…,vQ}。
2.在一个离散集合O中，存有M个观察字符(symbol)，即O={o1,…,oM}。
3.一个奘太移转(state transition)分布A＝{αij}，其中αij＝P[时间为t+1时的第j个状态 | 时间t时的第i个状态]。
4. 一个字符的放射分布(emission distribution)B＝{Bil}，Bil＝P[t时的vl ｜ t时的第i个状态]。
5. 一个起使状态分布，π＝{πi}，其中πi＝P[t=1时的第i个状态]。
不过在HMM中有3个基本问题存在，分别为“参数评估(parameter estimation)”、“可能性(likehood)”以及“状态转译(state interpretation)”等问题。所谓的参数评估，主要是要设计一个最适合的模型参数，以从模型中取得一个最大化的观察序列机率，在此评估方法如Baum-welch算法便是。而所谓的可能性问题，主要是要计算所给定的模式，其观察系列的机率。这类的算法包含forward或是backward算法均是。最后一个HMM问题是状态转译，此问题并不好解决。所谓的状态转译，是从给定的模型与观察序列中，利用一些最佳化的规则函数，来找到一个最佳化的状态序列，这方法的算法主要有Verbi算法。为了解决HMM的这3个基本问题，目前已经有一些动态规划及EM算法被发展出来。关于HMM与一个递归反向散播网络(recurrent back-propagation network)的等值性，可以参考早期J. Hwang、J. Volntzos及S. Kung(1989年)所发表的语意辨识研究资料，其提出了可同时用以描述HMM及类神经网络的运算属性及结构属性的一般性架构，该篇文章对于要了解其彼此间的关连性颇有帮助。而为了更真切的捕捉动态数据，以及更有弹性的处理可变长度序列之问题，一些研究者以更直觉的方式处理数据，像是范文模型(paradigm model)丛集法乃直接从原始资料来做其它额外处理，但这种方式也许会导致资料毁损的不可逆性及导致其它重要信息的遗失。且其方法对于决定组件模型的数目方面，仍存有一定的复杂度且不确定过程之问题。其它模型式的序列丛集法还包含Smyth提议之混合一级马可夫链法(first-order Markov chain)，以及2002年时Y. Xiong及D. Yeung所提到的线性模型(他们称为ARMA(autoregressive moving average))，通常这些方法均会和EM方法结合作为参数评估的方式，其中Symth等人更进一步尝试利用一般性机率架构来将混合数据的测量加以模型化。
(三)间接序列丛集法
所谓“间接”乃意味着不直接处理特征数据，即是所有的序列会被对应到转换的特征空间，然后再用典型的“空间向量丛集法”来形成丛集。因此此法所使用的是一种间接策略，再撷取序列的特征后还要将其转换到对应的特征空间，方能启动丛集过程。在这种方法里面，特征撷取便成为其算法效能高低的决定性因子。V. Guralnik及G. Karypis便曾讨论过两个序列模式之间的潜在依存性，并建议为了使全域或局部方法能再新的特征空间里面，有更佳的序列表现结果，须要减少起始特征集合。T. Morzy、M. Wojciechowski及M. Zakrzewice曾利用循序模式(sequential patterns)来当作同化阶层丛集法的基本要素，并定义了一种称为“同生(co-occurrence)”测量法，来作为较小丛集间融合的标准。这些方法有效的降低了运算复杂度，并可被用于大量的序列数据库中使用。不过要注意的是，在所有特征转换的方法里面，虽然其可以让非线性的问题转变为线性分解的可能，但特征选择的处理将无可避免的会导致某些原始信息的遗失，这是使用这些方法时所需要付出的代价。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”
核心丛集法的发展动力在于转换数据维度的困难性，依据Mercer理论可知，各维度所产生的困难性，可利用核心转换的方式加以克服。之所以如此转换是因为运算复杂度(computational complexity)对于大型数据集上之应用而言具有关键性的地位，对现在许多线性算法而言，在建构平方和(sum of squared)丛集法与K-means算法的过程，其均展示了一个非常好的非线性再公式化的例子。对于这些非线性变量能否保持原始算法某些有用而重要的属性之研究，目前也是一个重要的议题。此方法的应用例子目前已有许多，例如B. Schlkopf、A. Smola以及K. Müller便曾在在线模式中(on-line mode)描述了一个核心K-means方法(kernel K-means algorithm)。在其方法中，假设我们有d维度之模式集合xj，j=1,…,N；以及一个非线性对应，在此F表示一个具有任意维度之特征空间。该算法的客观面，表示要找出K个中心点，以方便我们最小化这些对应模式(mapped patterns)之间的距离以及他们所最接近之中心点，运算方式如下：
其中ml表示为第l个丛集，而k(x,xj)＝Ф(x)．Ф(xj)表示内积核心。我们可以定义一个丛集旗标变量Cjl，如果其值为1，表示xj属于l丛集，否则将其值指定为0。核心式学习算法的运作理论，乃基于覆盖(cover)理论而来。
也就是说，藉由非线性转换一个复数集合与非线性可分模式到较高维度之特征空间(features space)，以取得以线性方法分别此模式的可能性。藉由设计及计算核心内积(kernel inner-product)，我们可以节省时间的耗费，有时甚至可以将非线性描述过程，加以对应并计算其在已转换空间中的对应点(corresponding points)。J.Corchado及C.Fyfe提议了两种变异的核心K-means算法，其研究的动机乃来自SOFM及ART网络概念，这些变异方法在调整丛集指定变量时，会把邻近关系所产生的影响纳入考虑，并使用“警惕参数(vigilance parameters)”来控制平均向量的产生过程。另外2002年M. Girolami所提议的“替代性核心丛集法”亦颇具意思，其将丛集化问题公式化成侦测一个函数Г最佳化部分的问题，并同时将特征空间之群组的散布矩阵(scatter matrix)最小化，即是，他们在此以RBF函数(radial basis function)作为其核心函数。不同型态的核心函数效果，可在大量的文献中到相关的研究，而此领域亦为研究核心丛集算法时一个颇具潜力的领域。目前有许多人研究核心式的丛集法，其因素有很多，但最主要的是因为核心式丛集法具有以下一些优点：
1. 更易取得线性的可分离性：
在高维度超平面(hyperplane)或无限维度之特征空间更可能取得线性的可分离性。
2. 所形成之丛集形状种类多样化：
除了形成超球体(hypersphere)以及超椭圆体(hyperellipsoid)形状之外，他们也可以形成任意的丛集形状。
3. 噪声与分离体抗性问题：
一些核心式的丛集算法，具有处理噪声及分离体干扰问题(例如：SVC法)。
4、不需要先有侦测系统拓朴结构的先验知识：
对SVC方法(如后叙)而言，其不需要具备侦测系统的拓朴结构的先验知识(prior knowledge)，其核心矩阵仍可以提供平均向量，以估算丛集数目。
虽然核心是丛集法有着上述几项优点，但是并不代表其是完美的方式。目前这领域仍存有一些争议，尚待解决，不过在综合说来这种方法还算可被接受的一种方式。在传统的核心K-means算法计算方式里，其首先要用一个xi来起始化中心点ml。其次，取得xi+1并计算C(i+1)h。如果C(i+1)h＝1，则表示对所有j≠h之情形，其||Ф(xi+1)-mh||2<||Ф(xi+1)-mj||2。若C(i+1)h＝0则表示属其它情形。然后，令C(i+1)h与的比值为，则利用式子更新平均向量(mean vector)－mh，使其所对应的C(i+1)h＝1。对每个Ф(xj)而言，如果j≠i+1，则，若如果j=i+1则，以调整系数。这种计算C(i+1)h、平均向量之更新以及系数的调整过程会一直进行，直到完成“收敛(convergence)状态”为止。其它比较重要的丛集算法还有SVC(support vector clustering)丛集法，这种方法是A. Ben-Hur、D. Horn、H. Siegelmann及V. Vapnik在2001年时所提出的新的丛集方法，以便在原始数据空间找到丛集的边界轮廓集合，这些轮廓可以藉由对应回去转换特征空间中最小的封闭球形来取得。在SVC的方法里面，其可形成两种丛集，一种称为“分化阶层丛集(division hierarchical cluster，DHC)”，另一种称为“同化阶层丛集(agglomerative hierarchical cluster，AHC)”。都某些点被允许存在于超球体(hypersphere)之外时，SVC可以更有效率的处理分离体(outliers)的问题。此外还可以将SVC与fuzzy结合使用，此方面的延伸例子可以在J. Chiang及P. Hao(2003)的研究里找到，有兴趣的读者不妨参考看看。
十、循序数据(sequential data)之丛集化
循序数据和其它数据不太相同，其中次序性(或称为“时序依存性”)是其重要特征。也就是说，这种数据通常是依据变量长度排列，并具有与其它数据不同的特性。例如：具有大量空间需求，具备动态行为之使用与时间上的限制。循序数据的处理以往均为数据处理之重点，如今此类数据在大型数据分析里面又重新获得重视，主要要归功于两种循序资料来源的取得。第一种重要的循序数据来源，便是基于人类基因解读计划(HGP)而来的大量DNA序列(DNA sequences)数据，如何找寻基因序列与某种疾病或蛋白质之间的关系，已成为目前生化研究领域上一个非常重要的领域。藉由疾病辨识的基因疗法，将使一些难治的疾病出现治愈的一线希望；其次，另一个重要的循序数据来源，主要是自然语音处理程序的需求。这类需求随着监控安全自动化的趋势越显重要，尤其是搭配脸部辨识等其它生物特征辨识系统，与语音自然处理DSP，建构起更精确的生物特征辨识系统，以维护国家社会，并进而建立24小时的全天候小区安全监控能力。往后这类技术纯熟之后，各路口的监视摄影机将可搭配国家犯罪数据库，以实时辨识搜寻的方式，找寻可能的犯罪嫌疑人所在，并自动由系统通知附近警网前往拦截。因此美国、英国等先进国家，莫不强化此项技术的发展应用，尤其在国际机场的安全辨识上面，该系统将对反恐行动提供非常大的帮助。其它循序数据的重要来源还包含医学诊断数据(medical diagnosis)、文字探勘(text mining)、股票市场(stock market)数据以及客户交易数据(customer transactions)…等等。
自从计算器处理信息能力大幅提升之后，循序数据的数量可谓大幅增加。尤其是生化上大量的基因序列或蛋白质序列数据，亦促使传统研究方式发生潜移默化之变化。然而要探索这些庞大序列数据内的潜在模块并非易事，并且长久以来便存有应用方法上的争议。今日大家所热衷的丛集分析技术，亦只是其中一项时代演进下被用来作为探索之工具而已。一般而言，循序丛集化(sequential clustering)的技术可概略区分为三种不同的类别：第一种类型是利用序列之间的相似度(sequence similarity)为运算基础；第二种类型是统计式的序列丛集法(statistical sequence clustering)；第三种类型是间接序列丛集法(indirect sequence clustering)。这三种方法所应用之原理，我们简述如下：
(一)序列相似法：
这种策略运作原理，主要是基于测量序列中待测组与比对组之间的序列相似度(或称为pair之间的距离)为基础。然后再利用阶层算法或是部分丛集法来将这些序列群组化，在DNA或是蛋白质的氨基酸序列(amino acid sequences)中，因为其序列多以英文字母为排列方式，故传统的测量方法对这些数据的测量可能便不适用。如果一个序列之比较可视为一种序列间的转换过程(例如：利用一连串的运算子，像是：插入、删除、取代…等等来完成转换)，则此两序列间之距离，可被定义为所需使用的运算子(operators)数目，运算子的使用需求量少，表示此两序列的相似度高。一个常见的分析过程便是组合配对( alignment)，而其内容之配对结果可分为四种状况，分别是吻合(M)、取代(S)、插入(I)以及删除(D)，兹表示如图6。
在图6此种配对分析法里面所定义的距离是大家所熟知的编辑距离(edit distance)或是Levenshtein距离，这些编辑运算(edit operation)是可以根据某些先验知识与其中的距离，以及和完成转换之最小成本，来作为增、减的加权方式，在此两序列之间的相似度或是距离可以被重新公式化成一个最佳化的组合配对问题，其在动态规划(dynamic programming)中可以适用的非常好。如果给定两个序列X=(x1,…,xN)以及Y＝(y1,…,yM)，则其基本的动态规划序列比对算法，可以利用著名的Needleman-Wursch算法为之，其可以下面递归程序来描述：
其中S(i,j)为被定义为两个序列片段之间所比对的最佳比对分数( alignment score)；而e(xi,yj)、e(xi,)及e(,yj)分别表示组合配对xi到yi的成本、组合配对xi到空格(gap，以表示)的成本及组合配对yj到空格的成本。每个i、j位置的运算结果均会被纪录到指针数组里面，其存有目前最佳化之运算及提供一个有效的路径可回去追踪这些组合配对。在Needleman-Wursch算法中，其会比较两个序列的全部长度，已完成全域(global)最佳配对的取得，不过要注意的是在许多环境中，有时找出局部相似度也是一项很重要的工作。在此方面，Smith-Waterman算法允许我们起使一个新的组合配对，并允许在组合配对之动态规划时，可在任何位置停下来。不论其为全域或是局部的组合配对算法，其运算复杂度均为O(NM)。因此在需要比较整个序列组合时，此运算成本将会变得非常可观。为解决此问题，R. Durbin等人及D. Gusfield提出了另一种改良方法，其可加快运算速度并降低些许运算成本，此方法对于生物序列分析(biological sequence analysis)具有相当大的帮助。当然该方法除了可被用在生物序列分析上之外，其对于探索模式探勘(pattern mining)与自然语音辨识(speech recognition)的应用上亦颇具效益。
(二)统计式序列丛集法
不像前面的方法着重于静态位置之计算，这种方法是利用统计模型来描述两序列之间的“动态关系”，其可被用于数值序列或是类别式序列中。为了使我们得以正确解译数据中的特征，模型的选择变成了胜败关键。可惜值至目前为止，并没有一套标准可供我们在选择模型时参考，模型的选择目前仍非常复杂且其中存有相当多的影响因子。因此在动态关系的描述上，目前最重要的方法还是要属隐藏马可夫模型(hidden Markov models，HMMs)，这种方法目前被广用在脸部辨识与语音的辨识应用上。在这种模型上，每个HMM的起始分布决定，乃依据每个丛集之先验机率而来，其基本的学习过程开始于各个参数起始化策略，以先对每个序列形成一个初步的对数可能性(log-likehood)切割来作为距离之测量，此切割会进一步经由典型的EM算法来对所有序列施以HMM训练后被精致化，并利用蒙地卡罗交互确认法来评估可能的丛集数目。而HMM之下一个状态之决定乃依据状态移转分布(T)所决定，并依据放射分布(E)来产生所对应的字符。此过程会不断重复，一直到完成最后状态为止。在此过程中其会产应连串的观察字符(observation symbol)来取代状态，此即说明了此方法之所以被称为“隐藏”马可夫模型的意思。1996年的时候，P. Symth曾提出了一种基于HMM的丛集模型，该模型与混合密度丛集法所楷橥的理论概念非常类似，其同样是利用机率分布来决定丛集的产生，不过其中较大的差异点，在于其使用的机率模型是HMM模型而非一般大家使用的t分布或高斯机率模型。除了形成有限的混合密度之外，混合模型也可以被描述成一种具有HMM移转数组之平均移转数组(means transition matrix)。
有关HMM的详细理论描述，可以参考1989年L. Rabiner的相关研究文章，因为该理论已经广被使用在各种领域，因此其重要性也就不言而喻。实务上常使用离散的隐藏马可夫模型来描述一个不可观测的一连串状态之机率推移过程(stochastic process)，此一连串状态彼此间的关系乃依据机率高低而定其转变机率，一个HMM的定义如下：
1.存有一个Q状态的有限集合V，其中V＝{v1,…,vQ}。
2.在一个离散集合O中，存有M个观察字符(symbol)，即O={o1,…,oM}。
3.一个奘太移转(state transition)分布A＝{αij}，其中αij＝P[时间为t+1时的第j个状态 | 时间t时的第i个状态]。
4. 一个字符的放射分布(emission distribution)B＝{Bil}，Bil＝P[t时的vl ｜ t时的第i个状态]。
5. 一个起使状态分布，π＝{πi}，其中πi＝P[t=1时的第i个状态]。
不过在HMM中有3个基本问题存在，分别为“参数评估(parameter estimation)”、“可能性(likehood)”以及“状态转译(state interpretation)”等问题。所谓的参数评估，主要是要设计一个最适合的模型参数，以从模型中取得一个最大化的观察序列机率，在此评估方法如Baum-welch算法便是。而所谓的可能性问题，主要是要计算所给定的模式，其观察系列的机率。这类的算法包含forward或是backward算法均是。最后一个HMM问题是状态转译，此问题并不好解决。所谓的状态转译，是从给定的模型与观察序列中，利用一些最佳化的规则函数，来找到一个最佳化的状态序列，这方法的算法主要有Verbi算法。为了解决HMM的这3个基本问题，目前已经有一些动态规划及EM算法被发展出来。关于HMM与一个递归反向散播网络(recurrent back-propagation network)的等值性，可以参考早期J. Hwang、J. Volntzos及S. Kung(1989年)所发表的语意辨识研究资料，其提出了可同时用以描述HMM及类神经网络的运算属性及结构属性的一般性架构，该篇文章对于要了解其彼此间的关连性颇有帮助。而为了更真切的捕捉动态数据，以及更有弹性的处理可变长度序列之问题，一些研究者以更直觉的方式处理数据，像是范文模型(paradigm model)丛集法乃直接从原始资料来做其它额外处理，但这种方式也许会导致资料毁损的不可逆性及导致其它重要信息的遗失。且其方法对于决定组件模型的数目方面，仍存有一定的复杂度且不确定过程之问题。其它模型式的序列丛集法还包含Smyth提议之混合一级马可夫链法(first-order Markov chain)，以及2002年时Y. Xiong及D. Yeung所提到的线性模型(他们称为ARMA(autoregressive moving average))，通常这些方法均会和EM方法结合作为参数评估的方式，其中Symth等人更进一步尝试利用一般性机率架构来将混合数据的测量加以模型化。
(三)间接序列丛集法
所谓“间接”乃意味着不直接处理特征数据，即是所有的序列会被对应到转换的特征空间，然后再用典型的“空间向量丛集法”来形成丛集。因此此法所使用的是一种间接策略，再撷取序列的特征后还要将其转换到对应的特征空间，方能启动丛集过程。在这种方法里面，特征撷取便成为其算法效能高低的决定性因子。V. Guralnik及G. Karypis便曾讨论过两个序列模式之间的潜在依存性，并建议为了使全域或局部方法能再新的特征空间里面，有更佳的序列表现结果，须要减少起始特征集合。T. Morzy、M. Wojciechowski及M. Zakrzewice曾利用循序模式(sequential patterns)来当作同化阶层丛集法的基本要素，并定义了一种称为“同生(co-occurrence)”测量法，来作为较小丛集间融合的标准。这些方法有效的降低了运算复杂度，并可被用于大量的序列数据库中使用。不过要注意的是，在所有特征转换的方法里面，虽然其可以让非线性的问题转变为线性分解的可能，但特征选择的处理将无可避免的会导致某些原始信息的遗失，这是使用这些方法时所需要付出的代价。
注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”