基于片段和DTW的模式識別外文翻譯@中英文翻譯@外文文獻翻譯

基于片段和 DTW的模式識別 摘要 本文專門對動態(tài)過程的狀態(tài)進行評估。過程狀態(tài)和異常將從被測量過程變量的模式中得到，利用這些模式的正確反映和分類，可以對一種確切的運行狀態(tài)進行識別。然而相同狀態(tài)的不同模式有著不同的時間持續(xù)或者大小，這篇論文中將提到一種動態(tài)時間歸正算法（ DTW），通過相似性匹配法進行不同模式的比較和分類。這個算法的主要改進在于利用了片段的方法對模式變量的性質(zhì)進行反映。 介紹 在動態(tài)過程的狀態(tài)評估中對被測量動態(tài)信號的解釋是一項最重要的工作，即對錯誤的檢測和修正。因此，擁有處理信號的工具是十分重要的 ，性質(zhì)的反映期望能夠代表被監(jiān)測信號的趨勢（傾向、震動度、警示、短暫度 .），特別是在錯誤的檢測和修正中。根據(jù)有關(guān)過程和行為的知識，一些技術(shù)可以用于這個目的。 利用片段的方法反映信號是其中一種技術(shù)。在這種情況下，一系列的片段被用于描述表征特定變化狀況的模式中，然后，問題轉(zhuǎn)化為獲得能夠表征這些模式的分類機制。這篇文章將描述用于這種模式識別技術(shù)的一種工具。 論文將按照以下線索進行組織。如下部分討論用以類似時間級數(shù)的方法，然后介紹動態(tài)時間歸整算法和有關(guān)片段的基本概念。最后，提及 DTW 的一項新進展并在一個診斷應用例 子中進行檢查。 時間級數(shù)比較 在許多應用中時間級數(shù)比較的研究已經(jīng)大量展開，下一步，將觀察距離類似的一些模型。 Agrawal et al. (1995b)提出形狀定義語言 SDL，用于取回包含在基于形狀的歷史中的信息。 SDL在它可以進行頻率比較的改進的性質(zhì)描述中永許改變原始的數(shù)據(jù)。 在 Agrawal et al. (1995a)中推出了另一種相似模型，基于兩個時間序列如果有足夠非重疊時間有序的相似子序列則認為它們是相似的。由于這一模型的推出，通過建立一個可索引的數(shù)據(jù)結(jié)構(gòu)，快速搜索技術(shù)被用于檢測一組序列中的相似 序列成分。 Faloutsos et al(1994) 或 Chan and Fu (1999)提出了把 Haar微波轉(zhuǎn)變用于時間系列索引問題的其他從收集到的序列中確定有用序列的索引方法。Keogh 和 Pazzani(1998)采用了一種新的表示法，組成 piecewise線性片段去描述形狀和包含每個單獨線性片段的重量矢量，并永許用戶自己定義各種各樣的類似量。 (Keogh &Pazzani 2000) 介紹了一種支持索引法的維度伸縮辦法。 另外一種有關(guān)序列相似的有用量是最長共同序列（ LLCS）的長度，基于從一個 序列傳到另一個序列的編輯長度。 Paterson 和 Danck, (1994)對一些存在方案進行了修訂。 在 Konstantinov and Yoshida 1992中線的組合代表了信號的性質(zhì)形狀。因此，如果兩種瞬時狀態(tài)的 qshapes偶合可以認為它們性質(zhì)相同。一個真實時間部分的分析程序，從預先確定的時間間隙中提取 qshapes，并把它們與儲存了有趣行為的可擴張庫進行比較。 在 (Bakshi and Stephanopoulos 1994b)中描述了基于片段的模式識別。每一個模式被一連串元素代表，同時用模 式語法的辦法進行定義。包含所有分類信息的特征序列通過與代表這些趨勢中的相似事件的明顯句法描述的匹配而確定，模式匹配促進了被用語解決需決定樹法再次解決的分類問題中的性質(zhì)和數(shù)量的提取。 動態(tài)時間歸整 通過時間序列數(shù)據(jù)進行的大部分算法是使用歐幾里得距離或者它的一些變化。然而由于它對于時間軸上小的失真非常敏感，歐幾里得距離可以形成相似上的不正確量。 一種試圖解決這種不便的方法是動態(tài)時間歸整法（ DTW），這種技術(shù)是利用動態(tài)方程把時間級數(shù)與一個特定的模板對齊使累積距離最小。 DTW已經(jīng)廣泛用于消除詞識別中因講話的不同速度 引起的失真。 下面描述 DTW的概念： 設兩個長度分別為 M和 N的時間級數(shù) X、 Y： X=x1,x2,.,xi,.,xm Y=y1,y2,.,yj,.,yn (1) 為了對齊兩序列， DTW將在 M*N的矩陣中尋找一個具有 K點的 W序列，矩陣中每一個元素（ i， j）包含了 Xi和 Xj之間的距離 d（ Xi， Yj）。路徑 W是為了減少兩序列間矩陣元素對齊的距離。 W=w1,w2,.,wk max(m,n)km+n (2) wk=ik,jk (3) ik和 jk分別表示軌道 X和 Y的索引時間，為了尋找最佳路徑 Wi，考慮一些關(guān)于匹配過程的條件，主要有： 路徑端點條件： w， ， wk=m,n。 連續(xù)性時間匹配路徑不可能是逆時的，所以必須滿足： ik+ 1ik， jk+1jk。 通過把該點距離 d(xi,yj)與先前單元中距離的最小值之和 D(i,j) 作為累積距離來抽取路徑： D(i,j)=d(xi,yj)+minD(i-1,j-1),D(i-1,j),D(i,j-1) ( 1 ) 圖 1：形狀相同的兩個信號， a）由于信號不及時對齊，歐幾里得距離將產(chǎn)生一個不良結(jié)果。 b） dtw找到一個永許相似量的對 齊。 這項技術(shù)進行了許多更改用于在通過線性代表的較高層面上進行操作。 DTW和基于代表的片段的結(jié)合 在前面的部分中， DTW由于其在不同經(jīng)度下的序列對齊能力而被作為確定不同片段的相似性的一種方法。不利的方面其算法計算時間過長和試圖通過歪曲X軸來解決 Y軸的可變性可能引起無法對齊。在這一部分中，將介紹可以解決這種缺陷的 DTW算法。 擬采用的解決方案組成上， DTW將用在基于代表的片段上而不是原始的時間級數(shù)上。作為片段的序列表征通過減少數(shù)據(jù)的計算量來減少計算時間。類似的，定義片段的性質(zhì)特征將回避 Y軸的可變問題。因此， DTW將可用于更長距離的片段對齊中。 唯一的問題是去定義片段間的累積距離。在這種意義中，一個距離的圖表被定義，與前部分所描述的 13類片段相一致。累積距離跟性質(zhì)狀況和定義了不同種類片段的輔助特性有關(guān)。然而，這些累積距離是以用戶的標準為條件的，因此 .這樣 DTW算法的一個新的進展（ EPDTW）就建立了，利用片段作為信號更高水平的表征。 必須牢記，被比較的序列可以有不同的持續(xù)，這個事實使的擬議技術(shù)的概括復雜化，在下一個例子中被分析的序列的長度是不同的，盡管不是太不相似。 診斷應用 如應用的例子中，前面提到的 改進已經(jīng)在一座以診斷為目的的實驗室設備中使用了。在這套設備中，容器 A的水位由 PID控制器通過從水庫（容器 B）中抽水來控制。 三個閥門（ V1， V2， V3）可以通過控制開或關(guān)。然后打開或關(guān)閉閥門的合適組合的一些行為將發(fā)生。表 2描述了有關(guān)情形。 系統(tǒng)力學可以通過利用外部水填滿或者清空水庫做稍微改變。再說外部水的輸入或輸出也是控制所感興趣的部分。試驗在假設兩種情況不互搭的基礎上已經(jīng)被改進了。這樣，閥門配置方面的改變只有過程是穩(wěn)態(tài)時才被實施。被監(jiān)控信號的容器 A的水位和控制信號。 監(jiān)測系統(tǒng)可以檢測這些情形并且根 據(jù)片段序列描述的被測量信號的行為源診斷。監(jiān)測系統(tǒng)周期性地獲得并作為根據(jù)目前描述片段序列的表征。這些序列通過 EPDTW法與其他著名模式進行比較來完成發(fā)現(xiàn)和診斷情況的目的。 執(zhí)行例子 這部分中所講的例子與表格 2中所描述的三個閥門的操作是相一致的。首先，操作閥們模擬失靈，接著再操作閥們使回到正常操作狀態(tài)。前面提到的三種模式（ R1、 R2和 R3）已經(jīng)得到分別去代表每一個不正常狀態(tài)，每一種（圖 5-7）由兩個被監(jiān)測的信號和它在事件中的表征所組成。 然后，三種測試模板 T1、 T2和 T3（圖 8-10）與相同的情 況相一致，但是擁有不同的起點用以與前面提到的模式相比較，從而診斷狀態(tài)。 首先，每一模式的電平和控制信號在使信號正?；笠呀?jīng)和一種古典的DTW算法進行了比較，得到的結(jié)論在表 3和 4中給出。然后，測試模板的序列與前面模板的已知序列用 EPDTW算法進行比較。表 5和 6給出了電平的控制信號的比較結(jié)果。在所有情形下，所獲得的有用結(jié)果是一個正常距離，因此， 0代表完全匹配。 最后，獲得兩信號距離主要目的是為了得到每一種狀況和不同情況（ DTW和 EPDTW）下模式之間是本地距離，這種類似評價的結(jié)果，在表 7和 8中給出。 可以看出利用表 8比表 7更容易分離出正確或錯誤的診斷。另一個要考慮的是處理時間。在這些例子中，利用 DTW算法在 AMD K2處理器中的最大執(zhí)行時間是 5.34秒，而利用 EPDTW算法是 0.3seg。 總結(jié) 這項工作表明利用片段法進行信號的性質(zhì)表征和用于診斷領域模式識別的DTW算法的結(jié)合是可能的。 既然屬于相同狀態(tài)的不同模式可以有不同的時間持續(xù)或重要性， DTW算法的一種改進提出來，用以比較和分類相同模式，利用相似匹配法。這樣，由 DTW實現(xiàn)的受時間限制的對齊優(yōu)勢就加到了利用片段作為信號表征的優(yōu)勢 中，從水位控制系統(tǒ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