基于片段和 DTW的模式識(shí)別 摘要 本文專門對(duì)動(dòng)態(tài)過(guò)程的狀態(tài)進(jìn)行評(píng)估。過(guò)程狀態(tài)和異常將從被測(cè)量過(guò)程變量的模式中得到，利用這些模式的正確反映和分類，可以對(duì)一種確切的運(yùn)行狀態(tài)進(jìn)行識(shí)別。然而相同狀態(tài)的不同模式有著不同的時(shí)間持續(xù)或者大小，這篇論文中將提到一種動(dòng)態(tài)時(shí)間歸正算法（ DTW），通過(guò)相似性匹配法進(jìn)行不同模式的比較和分類。這個(gè)算法的主要改進(jìn)在于利用了片段的方法對(duì)模式變量的性質(zhì)進(jìn)行反映。 介紹 在動(dòng)態(tài)過(guò)程的狀態(tài)評(píng)估中對(duì)被測(cè)量動(dòng)態(tài)信號(hào)的解釋是一項(xiàng)最重要的工作，即對(duì)錯(cuò)誤的檢測(cè)和修正。因此，擁有處理信號(hào)的工具是十分重要的 ，性質(zhì)的反映期望能夠代表被監(jiān)測(cè)信號(hào)的趨勢(shì)（傾向、震動(dòng)度、警示、短暫度 .），特別是在錯(cuò)誤的檢測(cè)和修正中。根據(jù)有關(guān)過(guò)程和行為的知識(shí)，一些技術(shù)可以用于這個(gè)目的。 利用片段的方法反映信號(hào)是其中一種技術(shù)。在這種情況下，一系列的片段被用于描述表征特定變化狀況的模式中，然后，問(wèn)題轉(zhuǎn)化為獲得能夠表征這些模式的分類機(jī)制。這篇文章將描述用于這種模式識(shí)別技術(shù)的一種工具。 論文將按照以下線索進(jìn)行組織。如下部分討論用以類似時(shí)間級(jí)數(shù)的方法，然后介紹動(dòng)態(tài)時(shí)間歸整算法和有關(guān)片段的基本概念。最后，提及 DTW 的一項(xiàng)新進(jìn)展并在一個(gè)診斷應(yīng)用例 子中進(jìn)行檢查。 時(shí)間級(jí)數(shù)比較 在許多應(yīng)用中時(shí)間級(jí)數(shù)比較的研究已經(jīng)大量展開(kāi)，下一步，將觀察距離類似的一些模型。 Agrawal et al. (1995b)提出形狀定義語(yǔ)言 SDL，用于取回包含在基于形狀的歷史中的信息。 SDL在它可以進(jìn)行頻率比較的改進(jìn)的性質(zhì)描述中永許改變?cè)嫉臄?shù)據(jù)。 在 Agrawal et al. (1995a)中推出了另一種相似模型，基于兩個(gè)時(shí)間序列如果有足夠非重疊時(shí)間有序的相似子序列則認(rèn)為它們是相似的。由于這一模型的推出，通過(guò)建立一個(gè)可索引的數(shù)據(jù)結(jié)構(gòu)，快速搜索技術(shù)被用于檢測(cè)一組序列中的相似 序列成分。 Faloutsos et al(1994) 或 Chan and Fu (1999)提出了把 Haar微波轉(zhuǎn)變用于時(shí)間系列索引問(wèn)題的其他從收集到的序列中確定有用序列的索引方法。Keogh 和 Pazzani(1998)采用了一種新的表示法，組成 piecewise線性片段去描述形狀和包含每個(gè)單獨(dú)線性片段的重量矢量，并永許用戶自己定義各種各樣的類似量。 (Keogh &Pazzani 2000) 介紹了一種支持索引法的維度伸縮辦法。 另外一種有關(guān)序列相似的有用量是最長(zhǎng)共同序列（ LLCS）的長(zhǎng)度，基于從一個(gè) 序列傳到另一個(gè)序列的編輯長(zhǎng)度。 Paterson 和 Danck, (1994)對(duì)一些存在方案進(jìn)行了修訂。 在 Konstantinov and Yoshida 1992中線的組合代表了信號(hào)的性質(zhì)形狀。因此，如果兩種瞬時(shí)狀態(tài)的 qshapes偶合可以認(rèn)為它們性質(zhì)相同。一個(gè)真實(shí)時(shí)間部分的分析程序，從預(yù)先確定的時(shí)間間隙中提取 qshapes，并把它們與儲(chǔ)存了有趣行為的可擴(kuò)張庫(kù)進(jìn)行比較。 在 (Bakshi and Stephanopoulos 1994b)中描述了基于片段的模式識(shí)別。每一個(gè)模式被一連串元素代表，同時(shí)用模 式語(yǔ)法的辦法進(jìn)行定義。包含所有分類信息的特征序列通過(guò)與代表這些趨勢(shì)中的相似事件的明顯句法描述的匹配而確定，模式匹配促進(jìn)了被用語(yǔ)解決需決定樹(shù)法再次解決的分類問(wèn)題中的性質(zhì)和數(shù)量的提取。 動(dòng)態(tài)時(shí)間歸整 通過(guò)時(shí)間序列數(shù)據(jù)進(jìn)行的大部分算法是使用歐幾里得距離或者它的一些變化。然而由于它對(duì)于時(shí)間軸上小的失真非常敏感，歐幾里得距離可以形成相似上的不正確量。 一種試圖解決這種不便的方法是動(dòng)態(tài)時(shí)間歸整法（ DTW），這種技術(shù)是利用動(dòng)態(tài)方程把時(shí)間級(jí)數(shù)與一個(gè)特定的模板對(duì)齊使累積距離最小。 DTW已經(jīng)廣泛用于消除詞識(shí)別中因講話的不同速度 引起的失真。 下面描述 DTW的概念： 設(shè)兩個(gè)長(zhǎng)度分別為 M和 N的時(shí)間級(jí)數(shù) X、 Y： X=x1,x2,.,xi,.,xm Y=y1,y2,.,yj,.,yn (1) 為了對(duì)齊兩序列， DTW將在 M*N的矩陣中尋找一個(gè)具有 K點(diǎn)的 W序列，矩陣中每一個(gè)元素（ i， j）包含了 Xi和 Xj之間的距離 d（ Xi， Yj）。路徑 W是為了減少兩序列間矩陣元素對(duì)齊的距離。 W=w1,w2,.,wk max(m,n)km+n (2) wk=ik,jk (3) ik和 jk分別表示軌道 X和 Y的索引時(shí)間，為了尋找最佳路徑 Wi，考慮一些關(guān)于匹配過(guò)程的條件，主要有： 路徑端點(diǎn)條件： w， ， wk=m,n。 連續(xù)性時(shí)間匹配路徑不可能是逆時(shí)的，所以必須滿足： ik+ 1ik， jk+1jk。 通過(guò)把該點(diǎn)距離 d(xi,yj)與先前單元中距離的最小值之和 D(i,j) 作為累積距離來(lái)抽取路徑： D(i,j)=d(xi,yj)+minD(i-1,j-1),D(i-1,j),D(i,j-1) ( 1 ) 圖 1：形狀相同的兩個(gè)信號(hào)， a）由于信號(hào)不及時(shí)對(duì)齊，歐幾里得距離將產(chǎn)生一個(gè)不良結(jié)果。 b） dtw找到一個(gè)永許相似量的對(duì) 齊。 這項(xiàng)技術(shù)進(jìn)行了許多更改用于在通過(guò)線性代表的較高層面上進(jìn)行操作。 DTW和基于代表的片段的結(jié)合 在前面的部分中， DTW由于其在不同經(jīng)度下的序列對(duì)齊能力而被作為確定不同片段的相似性的一種方法。不利的方面其算法計(jì)算時(shí)間過(guò)長(zhǎng)和試圖通過(guò)歪曲X軸來(lái)解決 Y軸的可變性可能引起無(wú)法對(duì)齊。在這一部分中，將介紹可以解決這種缺陷的 DTW算法。 擬采用的解決方案組成上， DTW將用在基于代表的片段上而不是原始的時(shí)間級(jí)數(shù)上。作為片段的序列表征通過(guò)減少數(shù)據(jù)的計(jì)算量來(lái)減少計(jì)算時(shí)間。類似的，定義片段的性質(zhì)特征將回避 Y軸的可變問(wèn)題。因此， DTW將可用于更長(zhǎng)距離的片段對(duì)齊中。 唯一的問(wèn)題是去定義片段間的累積距離。在這種意義中，一個(gè)距離的圖表被定義，與前部分所描述的 13類片段相一致。累積距離跟性質(zhì)狀況和定義了不同種類片段的輔助特性有關(guān)。然而，這些累積距離是以用戶的標(biāo)準(zhǔn)為條件的，因此 .這樣 DTW算法的一個(gè)新的進(jìn)展（ EPDTW）就建立了，利用片段作為信號(hào)更高水平的表征。 必須牢記，被比較的序列可以有不同的持續(xù)，這個(gè)事實(shí)使的擬議技術(shù)的概括復(fù)雜化，在下一個(gè)例子中被分析的序列的長(zhǎng)度是不同的，盡管不是太不相似。 診斷應(yīng)用 如應(yīng)用的例子中，前面提到的 改進(jìn)已經(jīng)在一座以診斷為目的的實(shí)驗(yàn)室設(shè)備中使用了。在這套設(shè)備中，容器 A的水位由 PID控制器通過(guò)從水庫(kù)（容器 B）中抽水來(lái)控制。 三個(gè)閥門（ V1， V2， V3）可以通過(guò)控制開(kāi)或關(guān)。然后打開(kāi)或關(guān)閉閥門的合適組合的一些行為將發(fā)生。表 2描述了有關(guān)情形。 系統(tǒng)力學(xué)可以通過(guò)利用外部水填滿或者清空水庫(kù)做稍微改變。再說(shuō)外部水的輸入或輸出也是控制所感興趣的部分。試驗(yàn)在假設(shè)兩種情況不互搭的基礎(chǔ)上已經(jīng)被改進(jìn)了。這樣，閥門配置方面的改變只有過(guò)程是穩(wěn)態(tài)時(shí)才被實(shí)施。被監(jiān)控信號(hào)的容器 A的水位和控制信號(hào)。 監(jiān)測(cè)系統(tǒng)可以檢測(cè)這些情形并且根 據(jù)片段序列描述的被測(cè)量信號(hào)的行為源診斷。監(jiān)測(cè)系統(tǒng)周期性地獲得并作為根據(jù)目前描述片段序列的表征。這些序列通過(guò) EPDTW法與其他著名模式進(jìn)行比較來(lái)完成發(fā)現(xiàn)和診斷情況的目的。 執(zhí)行例子 這部分中所講的例子與表格 2中所描述的三個(gè)閥門的操作是相一致的。首先，操作閥們模擬失靈，接著再操作閥們使回到正常操作狀態(tài)。前面提到的三種模式（ R1、 R2和 R3）已經(jīng)得到分別去代表每一個(gè)不正常狀態(tài)，每一種（圖 5-7）由兩個(gè)被監(jiān)測(cè)的信號(hào)和它在事件中的表征所組成。 然后，三種測(cè)試模板 T1、 T2和 T3（圖 8-10）與相同的情 況相一致，但是擁有不同的起點(diǎn)用以與前面提到的模式相比較，從而診斷狀態(tài)。 首先，每一模式的電平和控制信號(hào)在使信號(hào)正?；笠呀?jīng)和一種古典的DTW算法進(jìn)行了比較，得到的結(jié)論在表 3和 4中給出。然后，測(cè)試模板的序列與前面模板的已知序列用 EPDTW算法進(jìn)行比較。表 5和 6給出了電平的控制信號(hào)的比較結(jié)果。在所有情形下，所獲得的有用結(jié)果是一個(gè)正常距離，因此， 0代表完全匹配。 最后，獲得兩信號(hào)距離主要目的是為了得到每一種狀況和不同情況（ DTW和 EPDTW）下模式之間是本地距離，這種類似評(píng)價(jià)的結(jié)果，在表 7和 8中給出。 可以看出利用表 8比表 7更容易分離出正確或錯(cuò)誤的診斷。另一個(gè)要考慮的是處理時(shí)間。在這些例子中，利用 DTW算法在 AMD K2處理器中的最大執(zhí)行時(shí)間是 5.34秒，而利用 EPDTW算法是 0.3seg。 總結(jié) 這項(xiàng)工作表明利用片段法進(jìn)行信號(hào)的性質(zhì)表征和用于診斷領(lǐng)域模式識(shí)別的DTW算法的結(jié)合是可能的。 既然屬于相同狀態(tài)的不同模式可以有不同的時(shí)間持續(xù)或重要性， DTW算法的一種改進(jìn)提出來(lái)，用以比較和分類相同模式，利用相似匹配法。這樣，由 DTW實(shí)現(xiàn)的受時(shí)間限制的對(duì)齊優(yōu)勢(shì)就加到了利用片段作為信號(hào)表征的優(yōu)勢(shì) 中，從水位控制系統(tǒng)的例子中可以看出，控制狀況的正確識(shí)別可以從當(dāng)前模式和前面已知模式的比較中得出。 Pattern recognition based on episodes and DTW Abstract This work is oriented towards situation assessment of dynamic processes. Process conditions and abnormalities can be detected from patterns of measured process variables. Then, a correct representation and classification of these patterns allows identifying a particular class of operating situation. Nevertheless, different patterns belonging to the same class of situations could have different time duration or magnitudes. In this paper a modification of Dynamic Time warping (DTW) algorithm is presented in order to compare and classify patterns by means of a measure of similarity. The main improvement introduced in this algorithm is the use of qualitative representation of process variables by means of episodes. Introduction Interpretation of measured process signals is an important task in Situation Assessment of dynamic processes, namely for Fault Detection and Diagnosis. For this reason, it is necessary to have tools for dealing with signal coming from processes. Qualitative representations are proposed to represent trends of signals (tendencies, oscillation degrees,alarms, degree of transient states.) needed in supervision,especially in fault detection and diagnosis. According takenowledge about process and its behaviour several techniques could be used with this aim. One of these techniques is the representation of signals by means of episodes. In this case, series of episodes are used to describe patterns that identify particular classes of operating situation. Then the problem is to obtain a classification mechanism of these patterns in order to identify the state of the process. In this paper a description of the tools used in this pattern recognition methodology is shown. The paper is organized as follows. In the following section, similarity methods applied to time series are discussed. Then Dynamic Time Warping (DTW) is introduced and basic concepts related to episodes are presented. Finally, a new approach of DTW is proposed and tested in a diagnosis application example. Comparing Time Series. There are numerous studies that have been carried to compare time series of data in several applications. Next, some models of distance-similarity are observed. Agrawal et al. (1995b) present a shape definition language (SDL) for retrieving objects contained in the histories based on shapes. SDL allows converting original data in a qualitative description of its evolution that allows a comparison between sequences. In Agrawal et al. (1995a) another model of similarity is introduced, it is based on the notion that two time sequences are said to be similar if they have enough nonoverlapping time-ordered pairs of subsequences that are similar. Given this similarity model, fast search techniques are used for discovering all similar sequences in a set of sequences by creating a indexable data structure. Other indexing methods to locate subsequences within a collection of sequences are presented by Faloutsos et al (1994) or Chan and Fu (1999) where a Haar wavelet transformation is used for the time series indexing problem. A new representation, adopted by Keogh and Pazzani (1998), consists of piecewise linear segments to represent shape and a weight vector containing the relative importance of each individual linear segment, allowing the user to define a variety of similarity measures. (Keogh & Pazzani 2000) introduce a dimensionality reduction technique that supports an indexing algorithm. A useful measure of similarity for strings is the length of a longest common subsequence (LLCS), based on the edit distance required in passing from one string to another one. Paterson and Danck, (1994) carry out a revision of some existing solutions. In (Konstantinov and Yoshida 1992) the qualitative shape of a signal is represented by the combination of strings. Hence, two temporal shapes are considered qualitatively equivalent if their qshapes coincide. A real time analyzing procedure extracts qshapes over a predefined time interval and compares them with those of an expandable shape library that stores all interesting behaviours. A methodology for pattern recognition based on episodes is described in (Bakshi and Stephanopoulos 1994b). Each pattern is represented by a string of primitives, also identified by means of a pattern grammar. The string that captures all the features necessary for classification is determined by matching the distinct syntactic descriptions, which represent similar events in these trends. Pattern matching facilitates extraction of qualitative and quantitative features used for solving the classification problem resolved by means of decision trees. Dynamic Time Warping. Most of algorithms that operate with time series of data use the Euclidean distance or some variation. However,Euclidean distance could produce an incorrect measure of similarity because it is very sensitive to small distortions in the time axis. A method that tries to solve this inconvenience is Dynamic Time Warping (DTW), this technique uses dynamic programming (Sakoe and Chiba, 1978； Silverman,1990) to align time series with a given template so that the total distance measure in minimised (Fig. 1). DTW has been widely used in word recognition to compensate the temporal distortions related to different speeds of speech. Next, a brief notion of DTW is described. Given two time series X and Y, of length m and n respectively X=x1,x2,.,xi,.,xm Y=y1,y2,.,yj,.,yn (1) To align the two sequences, DTW will find a sequence W of k points on a m-by-n matrix where every element (i,j) of the matrix contains the distance d(xi,yj) between the points xi and yj. The path W is a contiguous set of matrix elements that minimise the distance between the two sequences. W=w1,w2,.,wk max(m,n)km+n (2) wk=ik,jk (3) where ik and jk denote the time index of trajectories X and Y respectively. In order to find the best path W, some constraints on the matching process are considered, main ones are: Constraints at the endpoints of the path, w1=1,1 and wk=m,n Continuity constraints, matching paths cannot go backwards in time, this is achieved forcing ik+1ik and jk+1jk. The path is extracted by evaluating the cumulative distance D(i,j) as the sum of the local distance d(xi,yj) in the current cell and the minimum of the cumulative distances in the previous cells. This can be expressed as: D(i,j)=d(xi,yj)+minD(i-1,j-1),D(i-1,j),D(i,j-1) ( 1 ) Several modifications of this technique have been introduced in order to apply the method in several situations. In (Keogh and Pazzani 1999) a modification of DTW is introduced to operate on a higher level of data abstraction through a piecewise linear representation. (Keogh and Pazzani 2001) consider a higher level feature of shape considering the first derivative of the sequences. Caiani et al. (1998) adapt the DTW approach to the analysis of the left ventricular volume signal for an optimal temporal alignment between pairs of cardiac cycles. (Vullings et al. 1998) implement a piecewise linear approximation and segment the signal into separate heartbeats. DTW also is used in (Kassidas et al. 1998) to synchronise batch process trajectories in order to reconcile timing differences among them. Combining DTW and Episodes based Representations In previous section, DTW has been shown as a good method to determine the similarity between two sequences of episodes due to its capacity to align sequences with different longitudes. As disadvantages, it is a computationally expensive algorithm and it could fail in the alignment by trying to solve the variability in the Y-axis by warping the X-axis. In this section, a modification of the DTW algorithm that allows solving these inconveniences is introduced. The proposed solution consists on apply DTW not in original time series but in its episodes based representations. The representation of a sequence as episodes reduces the calculation time by decreasing the amount of manipulated data. Likewise, the qualitative character that defines an episode avoids the problem of the variability in the Y-axis. Therefore DTW can be used to align episodes to obtain a global distance. The only problem is to define a local distance between episodes. In this sense, a chart of distances has been defined where the 13 types of episodes described in the previous section are related. Distances are based on the qualitative state and auxiliary characteristics that define the different types of episodes (Table 1). However, these local distances could be subject to the criterion of the user, so one could give more importance to some episodes concerning another obtaining a different global distance and preserving the essential features of the process signal. This way, a new approach (EpDTW) of the DTW algorithm is created using episodes as a higher level representation of the signal. It is necessary to keep in mind that compared sequences could have different duration. This fact complicates the generalisation of the proposed technique, in the next example the length of the analysed sequences is different although not too dissimilar. A Diagnosis Application As application example, the proposed approach has been used in a laboratory plant for diagnosis purposes. In this plant (See Fig. 4), level in tank A is controlled by means of a PID controller by pumping water from a reservoir (tankB). Three valves (V1,V2 and V3) can be handled in order to simulate obstructions and leakages. Then several behaviours are possible by appropriate combination of opening and closing valves. Table 2 represents these situations. Additionally, system dynamics can by slightly modified by filling or emptying the reservoir with external water. Then, input and output of external water are also interesting situations to detect. The experiments have been developed under the assumption that two situations can not be overlapped. Thus, changes in the configuration of valves are only performed when process is in steady state. Monitored signals are the level in tank A and the control signal (pump). The monitoring system will be able to detect such situations and diagnose about the origin of misbehaviours according to the behaviour of measured signals described by sequences of episodes. The monitoring system acquires data periodically and represents them as sequences of episodes according to the previous description. These sequences are compared by means of EpDTW with other well-known patterns with the purpose of detecting and diagnose the situation. Execution Example The example described in this section corresponds to the manipulation of the three valves as described in Table 2. First the valves are manipulated in order to simulate the failure and later are manipulated again in order to return to the normal operation. Three reference patterns (R1,R2 and R3) have been obtained to represent each abnormal situation, each one (Fig. 5-7) is composed by the two monitored signals (level in tank A and control) and its representation in episodes. Then, three test patterns T1, T2, and T3 (Fig. 8-10)corresponding to the same situations but with different setpoints are used in order to compare them with the referencepatterns and diagnose the situation. First, the level and control signals of each pattern have been compared with a classical DTW algorithm after normalising the signals. The obtained results are shown in the Table 3 and Table 4. Then, the sequences of the test patterns are compared by means of EpDTW with the wellknown seque