(浙江工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310023)

近年來學(xué)生整體的體質(zhì)狀況呈現(xiàn)下降的趨勢。為改善學(xué)生體質(zhì)，高校陸續(xù)開始實(shí)行“陽光跑步”計(jì)劃，要求學(xué)生開展課外鍛煉。為了對(duì)學(xué)生課外健身跑的情況進(jìn)行監(jiān)督，傳統(tǒng)方法是在校園內(nèi)設(shè)置一些檢查點(diǎn)，學(xué)生跑步通過這些檢查點(diǎn)時(shí)以刷卡或者指紋識(shí)別的方式來進(jìn)行身份識(shí)別，按時(shí)完成規(guī)定的行程，以此保證鍛煉的質(zhì)量。該做法的局限性也是明顯的，首先是所有檢查點(diǎn)需要有專門人員負(fù)責(zé)看管，耗費(fèi)人力與財(cái)力；其次，由于專門人員的監(jiān)管不是全天的，學(xué)生只能在特定的時(shí)間進(jìn)行跑步，無法選擇自己最合適的鍛煉時(shí)間；最重要的是監(jiān)管具有被動(dòng)性，只獲取到每個(gè)學(xué)生抵達(dá)檢查點(diǎn)的時(shí)間信息，無法深入地分析學(xué)生的鍛煉狀況，更無法進(jìn)行個(gè)性化運(yùn)動(dòng)指導(dǎo)。

隨著穿戴技術(shù)的發(fā)展，以上問題可以得到有效解決。采用運(yùn)動(dòng)心率腕表是其中一種方法：一則通過腕表實(shí)時(shí)監(jiān)控學(xué)生課外鍛煉狀況，學(xué)生運(yùn)動(dòng)時(shí)間不再受監(jiān)管人員的約束；二則通過采集心率數(shù)據(jù)了解鍛煉強(qiáng)度，由此開展運(yùn)動(dòng)效果的分析，進(jìn)行個(gè)性化運(yùn)動(dòng)指導(dǎo)；此外，還可以減少監(jiān)管人力投入。當(dāng)然也存在一些技術(shù)問題需要克服，比如由于缺少直接監(jiān)督，可能會(huì)出現(xiàn)一人佩戴多個(gè)腕表替他人代跑的情形，筆者稱此為“多表代跑”。為了避免該情況，非常需要一種合適的方案對(duì)其進(jìn)行檢測，進(jìn)而達(dá)到有效的監(jiān)督，保證學(xué)生的課外鍛煉質(zhì)量。

1 相關(guān)工作

多表代跑的檢測本質(zhì)上屬于分類問題，但它又區(qū)別于時(shí)間序列的分類，并不針對(duì)單條序列，而是面向序列對(duì)的分類問題。該問題主要涉及三個(gè)方面：時(shí)間序列表示方法、時(shí)間序列相似性度量和時(shí)間序列分類。

在時(shí)間序列的表示上，有基于時(shí)域和基于轉(zhuǎn)換域的兩類方法?；跁r(shí)域方法有分段累積近似法(PAA)[1]、適應(yīng)性分段常數(shù)近似(APCA)[3]、符號(hào)化聚合近似法(SAX)[4]、感知要點(diǎn)(PIP)[5]、分段線性表示(PLR)法[6]還有旋轉(zhuǎn)門(SDT)[7]?；陬l域的方法有離散傅里葉變換(DFT)[8]和離散小波變換(DWT)[9]。在第4節(jié)將會(huì)針對(duì)多表代跑問題對(duì)所有這些方法進(jìn)行充分討論。

在時(shí)間序列的相似性度量上，主要有基于Lp-范數(shù)[10]的曼哈頓距離、歐氏距離和切比雪夫距離，還有動(dòng)態(tài)時(shí)間規(guī)整[11]和短時(shí)間序列(STS)距離[12]。與表示方法一樣，第4節(jié)將對(duì)它們進(jìn)行充分討論。

時(shí)間序列分類的研究主要有兩個(gè)關(guān)注點(diǎn)。首先有許多研究關(guān)注數(shù)據(jù)自身的性質(zhì)并對(duì)其進(jìn)行特殊處理。Geurts[13]提出基于時(shí)間序列中局部模式的分類方法。Zhang等[14]提出一種使用小波分解并且能夠自適應(yīng)選擇參數(shù)的表示方法用于分類?；谠摫硎就茖?dǎo)出合適的度量并使用最近鄰算法進(jìn)行分類。Kadous等[15]使用元特征途徑(比如時(shí)間序列中的局部最大值)來生成分類器。類似地，Yang等[16]使用基于公共主成分的特征子集選擇來保留在原始特征集中的關(guān)聯(lián)信息。然后根據(jù)分類的有效性對(duì)這些選擇的特征子集進(jìn)行評(píng)價(jià)。另一方面，研究者們關(guān)注定制或開發(fā)專門用于時(shí)間序列數(shù)據(jù)的分類器。比如，Povinelli等[17]提出一種基于對(duì)系統(tǒng)動(dòng)態(tài)建模的信號(hào)分類方法。這些動(dòng)態(tài)信息是從使用高斯混合模型對(duì)時(shí)域特征重建后的階段中捕獲得到的。Rodríguez等[18]研究能較好地對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行分類的區(qū)間決策樹和基于DTW的決策樹，然后使用集成方法將所有基分類器結(jié)合起來。此外，Xi等[19]提出一種半監(jiān)督的時(shí)間序列分類器，適用于只有少量帶標(biāo)簽樣本的情況。由于時(shí)間序列分類的研究都是針對(duì)單條序列，更適用于解決分次代跑問題。而本研究要解決的多表代跑問題中需要分類的是序列對(duì)，這些方法并不適用。

2 問題定義

當(dāng)前有許多研究工作通過移動(dòng)終端對(duì)數(shù)據(jù)進(jìn)行采集[20-22]。筆者將使用某公司生產(chǎn)的運(yùn)動(dòng)腕表采集學(xué)生的跑步心率數(shù)據(jù)。圖1為一同學(xué)在986 s的跑步過程中采集到的心率序列(采樣間隔為每秒一次，采集時(shí)間精確到秒，心率值精確到整數(shù))。

筆者分別對(duì)兩種類型的數(shù)據(jù)進(jìn)行采集：代跑序列和正常序列。代跑序列指的是一位同學(xué)替其他同學(xué)代跑產(chǎn)生的心率序列，有兩種情形：1) 同時(shí)戴多個(gè)心率腕表代替其他同學(xué)跑產(chǎn)生的序列；2) 多次替他人跑步產(chǎn)生的心率序列。筆者聚焦“多表代跑”的情形，通過機(jī)器學(xué)習(xí)算法自動(dòng)分辨代跑，分次代跑問題留到后續(xù)研究解決。正常序列指的是學(xué)生運(yùn)動(dòng)中只戴一只腕表采集得到的自身心率序列。

完成了心率序列的采集，所有的序列還需要先經(jīng)過適當(dāng)?shù)奶幚聿拍鼙皇褂谩４送?，互為代跑關(guān)系的兩條序列在完成采集后，它們各自采集起始時(shí)間的偏移都會(huì)被記錄下來。因?yàn)樵诤竺娴膶?shí)驗(yàn)部分，所有的心率序列會(huì)被分配在一個(gè)限定的時(shí)間域中進(jìn)行現(xiàn)實(shí)場景的模擬，兩條代跑序列的采集起始時(shí)間偏移仍應(yīng)該在模擬環(huán)境中保留。

Si=表示一條心率序列，它是一個(gè)<起始時(shí)間，結(jié)束時(shí)間，{心率值序列}>三元組。起始時(shí)間和結(jié)束時(shí)間分別表示心率序列采集開始和結(jié)束時(shí)的真實(shí)時(shí)間，比如圖1中序列的起始時(shí)間為2017年5月5日17時(shí)4分28秒，結(jié)束時(shí)間為2017年5月5日17時(shí)34分23秒。心率值序列即為所有采集到的心率值。對(duì)于給定的兩條多表代跑序列，它們的基本特征是：1) 心率序列采集起訖時(shí)間區(qū)間存在重疊；2) 心率值存在相同的波動(dòng)趨勢。因此多表代跑檢測問題可以描述為：給定時(shí)間序列數(shù)據(jù)集d，找出那些具有一定重疊時(shí)間區(qū)間，心率趨勢相同的序列對(duì)。其核心問題是如何合理計(jì)算序列對(duì)的相似度。

例如，在一段時(shí)間內(nèi)采集到的4條時(shí)間序列A，B，C，D，如圖2所示。橫軸代表時(shí)間，序列的高低與心率值無關(guān)，僅為互相區(qū)分。序列A與B的采集時(shí)間存在重疊，它們由多表代跑產(chǎn)生，屬于代跑序列對(duì)；序列A與C存在時(shí)間重疊，但它們心率波動(dòng)趨勢不同，不屬于多表代跑產(chǎn)生序列，屬于正常序列對(duì)。圖2中屬于正常序列對(duì)的還有A與D，B與D。

圖1 學(xué)生跑步過程中采集到的心率序列Fig.1 Heart rate series gathered when student is running

圖2 正常序列對(duì)和代跑序列對(duì)Fig.2 Normal series pair and fake running series pair

由此可知：當(dāng)兩段序列存在時(shí)間重疊，它們將組成一個(gè)序列對(duì)(正常序列對(duì)或代跑序列對(duì))。在給定的一段采集時(shí)間內(nèi)，會(huì)存在大量這樣的序列對(duì)。本研究的任務(wù)是提出一套代跑檢測方案識(shí)別其中的多表代跑序列對(duì)。

3 表示方法與相似性度量的選擇

本節(jié)討論表示方法和相似性度量的選擇，這兩方面是開展時(shí)間序列分析的關(guān)鍵。講述筆者選擇PAA、差值序列、斜率序列和百分比序列作為潛在的表示方法(當(dāng)然還包括原始序列)，以及選擇曼哈頓距離、歐氏距離、短時(shí)間序列距離、堪培拉距離還有Bray-Curtis距離作為潛在的相似性度量方法的考慮與理由。所有這些潛在的表示方法和相似性度量將組合在一起，在進(jìn)行特征抽取時(shí)每個(gè)組合對(duì)應(yīng)的距離值都作為特征集合的一部分。

3.1 表示方法

時(shí)間序列通常被轉(zhuǎn)換成合適的表示形式，在轉(zhuǎn)換后的序列上進(jìn)行相應(yīng)的分析[1]。目前時(shí)間序列表示方法主要可分為兩類：基于時(shí)域的表示方法和基于轉(zhuǎn)換域的表示方法。下面將針對(duì)當(dāng)前的研究對(duì)一些主要的方法進(jìn)行討論。

基于時(shí)域的時(shí)間序列表示法之一是對(duì)原始時(shí)間序列進(jìn)行分段處理，將其分成等長的片段，計(jì)算出每個(gè)片段中數(shù)據(jù)點(diǎn)的平均值，該方法被稱為分段累積近似法(PAA)[1]。該表示雖然壓縮了原有信息，但可能抽取出具有代表性的片段進(jìn)而提升檢測效果，因此將在實(shí)驗(yàn)方案中嘗試。另一種表示方法是適應(yīng)性分段常數(shù)近似(APCA)[3]，APCA作為分段累積近似法的擴(kuò)展版本被提了出來，該方法中各片段的長度不固定，隨時(shí)間序列的形狀自適應(yīng)變化，不能合理地在相應(yīng)時(shí)間匹配序列對(duì)，將不納入實(shí)驗(yàn)方案。

另一種通用類型的時(shí)間序列表示方法的思路是將數(shù)值化的時(shí)間序列轉(zhuǎn)換為符號(hào)化的表示。這類方法先將原始的時(shí)間序列離散化為一個(gè)個(gè)片段，然后再把每個(gè)片段映射到不同字符上。在這類方法中，最有代表性的是由Lin等[4]提出的符號(hào)化聚合近似法(SAX)。SAX本質(zhì)上是對(duì)PAA表示的進(jìn)一步壓縮。使用PAA已經(jīng)損失掉大量原始序列的信息，如果效果不佳，那么使用SAX只會(huì)讓最終的效果更差。所以將先在實(shí)驗(yàn)中對(duì)PAA方法的效果進(jìn)行觀察，根據(jù)情況決定是否在后續(xù)研究中將SAX納入實(shí)驗(yàn)方案。

此外，通過僅保留那些關(guān)鍵數(shù)據(jù)點(diǎn)來降低時(shí)間序列的維度也是一種很有前景的方法。這些關(guān)鍵點(diǎn)被稱作感知要點(diǎn)(PIP)[5]。對(duì)于一條時(shí)間序列P={p1，p2，…，pn}，通過PIP鑒別過程，對(duì)序列P中所有的數(shù)據(jù)點(diǎn)根據(jù)其重要性進(jìn)行排序，從而發(fā)現(xiàn)那些最重要的數(shù)據(jù)點(diǎn)。該表示找出的關(guān)鍵點(diǎn)很容易受到序列中噪聲的影響，比如一些由于噪聲帶來的極值點(diǎn)也會(huì)被選為關(guān)鍵數(shù)據(jù)點(diǎn)，進(jìn)而偏離了原始序列的信息。同時(shí)當(dāng)序列對(duì)重疊區(qū)域的兩片段被轉(zhuǎn)換之后，各自得到的關(guān)鍵點(diǎn)的時(shí)間戳往往是不一致的，無法匹配進(jìn)行距離計(jì)算。此外PIP需要通過特定算法對(duì)每條序列進(jìn)行一個(gè)關(guān)鍵點(diǎn)的尋找過程，這會(huì)帶來過多的計(jì)算消耗。

使用線段來擬合時(shí)間序列是另一種表示法，稱為分段表示法。其中的一個(gè)典型方法是分段線性表示(PLR)法[6]。設(shè)S(pi，…，pj)為一個(gè)子序列片段，其中pi，pj表示該序列中的數(shù)據(jù)點(diǎn)，該方法用連接pi和pj的線段作為該子序列的近似表示，該方法將這些連續(xù)片段的端點(diǎn)對(duì)齊，得到一個(gè)前后連接的線段組成的分段近似表示。具體地說，PLR是一個(gè)自底向上的算法，它先將時(shí)間序列中前后直接相鄰的兩個(gè)點(diǎn)作為片段創(chuàng)建一個(gè)最細(xì)粒度的近似；之后不斷地合并所需代價(jià)最低的相鄰片段對(duì)，直到當(dāng)前的片段數(shù)達(dá)到所需的數(shù)量。當(dāng)兩個(gè)相鄰的片段合并之后，該算法將會(huì)分別計(jì)算這個(gè)新片段與其前后相鄰片段合并所需的代價(jià)。與PLR類似，旋轉(zhuǎn)門(SDT)[7]算法也用于原始時(shí)間序列的線性分段表示，該算法在一定誤差范圍內(nèi)用起點(diǎn)和終點(diǎn)確定的直線來代替兩點(diǎn)之間其他的數(shù)據(jù)點(diǎn)，并保存起點(diǎn)和終點(diǎn)的時(shí)間及數(shù)值大小，且前一壓縮區(qū)間的終點(diǎn)即為后一壓縮區(qū)間的起點(diǎn)。這兩種表示與PIP的問題類似，無法對(duì)轉(zhuǎn)換后表示中的線段進(jìn)行匹配，因?yàn)檫@些線段是根據(jù)各自原始序列的波動(dòng)特征而生成的，它們所覆蓋的時(shí)間范圍并不一致。

前面提到的方法主要都是直接在時(shí)域?qū)r(shí)間序列進(jìn)行表示，然而也可以在轉(zhuǎn)換域中表示它們。離散傅里葉變換(DFT)是另一種表示法[8]。傅里葉變換可以視為一個(gè)基變換，把一個(gè)向量從無窮維的時(shí)域空間變換到另一個(gè)無窮維的頻域空間中；離散傅里葉變換也是一個(gè)基變換，它把原來一個(gè)n維的點(diǎn)變成了k維，因此，它也可以對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行降維處理。在DFT之后，Chan等[9]發(fā)現(xiàn)離散小波變換(DWT)可以很好地代替離散傅里葉變換。不同于傅里葉變換，其變量只有頻率，小波變換有兩個(gè)變量：尺度(scale)和平移量(translation)。尺度控制小波函數(shù)的伸縮，平移量控制小波函數(shù)的平移。尺度就對(duì)應(yīng)于頻率(反比)，平移量就對(duì)應(yīng)于時(shí)間。傅里葉變換只能得到一個(gè)頻譜，而小波變換卻可以得到一個(gè)時(shí)頻譜，小波變換可對(duì)非穩(wěn)定信號(hào)進(jìn)行時(shí)頻分析。這兩種方法雖常被用于時(shí)間序列的研究，但并不適用于當(dāng)前工作。首先，代跑鑒別是基于兩條序列在重疊區(qū)域里片段的比較展開的，在這個(gè)區(qū)域內(nèi)可能只有少量的對(duì)齊數(shù)據(jù)點(diǎn)，這樣貧乏的信息不足以讓頻域表示方法捕捉到心率序列信號(hào)的波動(dòng)特征；其次，將心率序列轉(zhuǎn)換為頻率上的系數(shù)后，時(shí)域中時(shí)間戳的對(duì)應(yīng)關(guān)系將會(huì)丟失，頻域中兩條序列很可能對(duì)應(yīng)不一樣的頻譜，此時(shí)不能再通過比較兩序列在重疊區(qū)域里對(duì)齊數(shù)據(jù)點(diǎn)的差值來進(jìn)行度量。

此外，除了前面提到的PAA，筆者還考慮了差值序列(前后時(shí)間戳對(duì)應(yīng)心率值的差值)、斜率序列(前后時(shí)間戳對(duì)應(yīng)心率值的差值/前后時(shí)間戳的差值)、百分比變化序列(前后時(shí)間戳對(duì)應(yīng)心率值的差值/前一時(shí)間戳對(duì)應(yīng)的心率值)這些基本的轉(zhuǎn)換作為后面實(shí)驗(yàn)中嘗試的表示方法，其優(yōu)點(diǎn)有：1) 操作方便；2) 能從不同的角度去表示原始心率序列中蘊(yùn)含的信息；3) 使用它們進(jìn)行表示依然可以保留兩條序列在時(shí)間戳上的對(duì)應(yīng)關(guān)系，這為后面距離的度量帶來了極大的便利。

3.2 相似性度量

對(duì)于多表代跑檢測問題，需要度量的是兩序列在重疊時(shí)間范圍內(nèi)片段之間的相似性。由于兩片段中數(shù)據(jù)點(diǎn)的對(duì)應(yīng)關(guān)系是可以由時(shí)間戳準(zhǔn)確鎖定的，所以不必考慮局部時(shí)間位移的問題，只需將所有數(shù)據(jù)點(diǎn)配對(duì)的偏差累加起來即可。另外采集過程中如果個(gè)體的運(yùn)動(dòng)強(qiáng)度過大，獲取的心率值很可能受到汗水或者腕表脫落的影響導(dǎo)致不夠精確。因此可考慮在度量中加上一定的權(quán)值，盡可能減少這種現(xiàn)象帶來的影響。

更全面的時(shí)間序列相似性度量方法可參考文獻(xiàn)[1]，本節(jié)講述典型的幾類方法。相似性度量在時(shí)間序列分析中是非常關(guān)鍵的一步。時(shí)間序列相似性度量是基于近似匹配的方式定義的?；贚p-范數(shù)[10]的歐氏距離[23]和它的變種是度量時(shí)間序列相似性最直接的方法。Lp-范數(shù)也被稱作閔可夫斯基距離。對(duì)于兩條長度相等的時(shí)間序列x和y，Lp-范數(shù)通過計(jì)算它們之間所有兩兩對(duì)應(yīng)時(shí)間點(diǎn)的距離之和來衡量兩條序列的近似程度。該距離和越小，相似程度越高。計(jì)算該距離和的公式為

(1)

式中：p取1時(shí)為曼哈頓距離；p取2時(shí)為歐氏距離；p取無窮大時(shí)為切比雪夫距離。歐氏距離和它的變種含義清晰、容易理解，它們還具有線性時(shí)間復(fù)雜度、易于實(shí)現(xiàn)、不需要設(shè)定額外的參數(shù)等特性。Ding等[1]嘗試通過實(shí)驗(yàn)對(duì)各種不同的相似性度量方法進(jìn)行比較，發(fā)現(xiàn)歐氏距離相比于其他更復(fù)雜的相似性度量方法更有競爭力，尤其是在數(shù)據(jù)庫/訓(xùn)練集相對(duì)比較大的時(shí)候。曼哈頓距離和歐氏距離都是通過累加兩條序列對(duì)齊數(shù)據(jù)點(diǎn)的差值作為距離的度量結(jié)果。該思路原理簡單，相對(duì)于其他度量方法具有更低的時(shí)間復(fù)雜度，將會(huì)在后續(xù)的檢測方案中使用。切比雪夫距離以兩序列對(duì)齊數(shù)據(jù)點(diǎn)中最大的偏差作為最終距離，可以看出該方法很容易受到局部噪聲的影響，兩條序列之間只要有一對(duì)偏差較大的數(shù)據(jù)點(diǎn)，它們就被認(rèn)為是高度不相似的。該方法至多只能作為初步的篩選，無法準(zhǔn)確度量兩條序列之間的相似度，不納入實(shí)驗(yàn)方案。

Lp-范數(shù)也有局限性，由于該度量對(duì)于兩時(shí)間序列內(nèi)點(diǎn)的對(duì)應(yīng)是固定的，其對(duì)噪聲和錯(cuò)誤的對(duì)齊非常敏感，且沒有辦法解決局部時(shí)間位移的問題(Local time shifting)，比如兩個(gè)時(shí)間序列片段相似但在位移上有一定的偏差。

為了對(duì)存在一定程度變形的時(shí)間序列進(jìn)行相似性度量，Berndt等[11]提出了動(dòng)態(tài)時(shí)間規(guī)整(Dynamic time warping)。該技術(shù)可以通過一種非線性的方式對(duì)齊，計(jì)算相似但局部存在偏移的兩序列之間的相似性。在本研究中，由于已經(jīng)能夠獲得序列中每個(gè)時(shí)間戳確定的時(shí)間，將重疊區(qū)域時(shí)間戳相同的數(shù)據(jù)點(diǎn)對(duì)齊，然后進(jìn)行距離的度量，所以并不需要該方法的特性。而且使用該方法很可能會(huì)因?yàn)樗膹澢鷮?duì)齊使得相似性的度量結(jié)果更不準(zhǔn)確。

為了對(duì)具有相同但不均勻采樣率的兩條時(shí)間序列進(jìn)行相似性度量，M?llerlevet等[12]提出了短時(shí)間序列(STS)距離，計(jì)算公式為

(2)

式中：x，y表示兩條不同的序列；n為兩條時(shí)間序列的長度。

雖然當(dāng)前使用序列采樣率均勻，但這種基于斜率偏差的距離度量是一種新思路，值得在實(shí)驗(yàn)中嘗試。

除了曼哈頓距離、歐式距離和短時(shí)間序列距離外，筆者還考慮了另外兩種方法?？芭嗬?canberra)距離本質(zhì)上是權(quán)重化的曼哈頓距離。權(quán)重是指會(huì)給不同對(duì)齊數(shù)據(jù)點(diǎn)的差值分配不同的權(quán)重，這個(gè)權(quán)重由兩個(gè)數(shù)據(jù)點(diǎn)對(duì)應(yīng)值的絕對(duì)大小來決定。假設(shè)有兩條時(shí)間序列x=和y=，兩段序列的堪培拉距離為

(3)

在本研究中該度量方法可以理解為對(duì)心率絕對(duì)水平較高情況的差值給予更多的懲罰。因?yàn)樵趯?shí)際心率數(shù)據(jù)采集過程中，當(dāng)采集人的運(yùn)動(dòng)狀態(tài)越來越劇烈，他的心率就會(huì)不斷上升，這時(shí)更容易出現(xiàn)手環(huán)松動(dòng)、汗水干擾的情況，進(jìn)而影響心率采集的精確度。若對(duì)這種情況的心率給予更多的懲罰，那么最終的度量結(jié)果有可能也會(huì)更接近于真實(shí)的序列相似情況。

此外還考慮將Bray-Curtis距離加入到檢測方案中。假設(shè)有兩段時(shí)間序列x和y，它們的Bray-Curtis距離為

(4)

本質(zhì)上該方法相當(dāng)于是曼哈頓距離的調(diào)整。當(dāng)使用曼哈頓距離，得到距離值后，將除上對(duì)齊點(diǎn)的個(gè)數(shù)，作為最終度量結(jié)果。而這里，除的值與序列本身的數(shù)值有關(guān)。由于心率值都是正的，不用考慮負(fù)數(shù)的情況，該方法便包含這樣的含義：如果兩序列心率值的總體水平比較高，那么它們之間的曼哈頓距離就會(huì)得到更多的懲罰。

4 代跑檢測方案

4.1 整體框架

已獲得的原始心率數(shù)據(jù)集需要先轉(zhuǎn)換為對(duì)應(yīng)的樣本集才能供分類器訓(xùn)練和測試。為了對(duì)分類器檢測效果進(jìn)行合理的評(píng)價(jià)，樣本集將劃分為訓(xùn)練集和測試集兩部分，分別用于分類器訓(xùn)練和代跑檢測。訓(xùn)練分類器時(shí)，將依次經(jīng)歷特征縮放、特征選擇還有模型訓(xùn)練的環(huán)節(jié)。代跑檢測時(shí)，前面兩環(huán)節(jié)與訓(xùn)練時(shí)一致，最后將針對(duì)代跑檢測問題確定合理的指標(biāo)對(duì)檢測結(jié)果進(jìn)行評(píng)價(jià)。

本方案主要包含3個(gè)部分：樣本集生成、分類器訓(xùn)練還有代跑檢測。代跑檢測方案為

名稱：代跑檢測方案。

輸入：原始心率數(shù)據(jù)集(包含標(biāo)簽和采集時(shí)間)。

重疊閾值：兩條序列的重疊部分需要有多長的時(shí)間才能被認(rèn)為是合法序列對(duì)。

輸出：代跑檢測分類結(jié)果。

1) 樣本集生成。樣本集生成：根據(jù)心率數(shù)據(jù)集中的所有序列對(duì)生成樣本集；訓(xùn)練集和測試集劃分：根據(jù)指定的比例將數(shù)據(jù)集劃分為訓(xùn)練集和測試集兩部分。

2) 分類器訓(xùn)練。對(duì)訓(xùn)練集中的特征進(jìn)行縮放；對(duì)訓(xùn)練集中的特征進(jìn)行選擇；調(diào)整SVM的模型參數(shù)并根據(jù)訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練。

3) 代跑檢測。對(duì)測試集中的特征進(jìn)行縮放；對(duì)測試集中的特征進(jìn)行選擇；使用訓(xùn)練好的SVM對(duì)測試集中的數(shù)據(jù)進(jìn)行代跑檢測。

4) 分析最終得到的代跑檢測結(jié)果。

4.2 樣本集生成

筆者將根據(jù)學(xué)生跑步時(shí)采集到的心率序列生成對(duì)應(yīng)的樣本集。對(duì)于采集到的心率序列：ξ1，ξ2，…，ξn，若序列ξi.[start, end]∩ξj·[start, end]≠φ，則依據(jù)ξi與ξj在重疊時(shí)間區(qū)間上的片段生成特征集。提取的特征，除兩條序列之間的距離度量外，還包括各種統(tǒng)計(jì)特征。根據(jù)兩條序列在采集時(shí)的實(shí)際關(guān)系賦予當(dāng)前樣本對(duì)應(yīng)的標(biāo)簽(戴多表采集的代跑關(guān)系為1，獨(dú)立采集的正常關(guān)系為0)。由此，得到樣本集。為了序列對(duì)提取特征時(shí)能夠獲得更充分的信息，要求重疊的時(shí)間區(qū)間達(dá)到一定長度，提升代跑鑒別的效果。若對(duì)該區(qū)間限制過大將導(dǎo)致一些重疊范圍較小的代跑序列對(duì)被忽略，這種序列歸入多次代跑問題中去解決。重疊區(qū)間大小對(duì)檢測效果的影響將在后續(xù)的實(shí)驗(yàn)中作進(jìn)一步分析。

下面講述特征序列的生成。

4.2.1 距離度量特征

距離度量可以用來直接表示兩條序列之間的相似程度[1]，也可以用某種相似性度量計(jì)算兩條序列在特定表示下的距離作為該序列對(duì)的一個(gè)特征。筆者將對(duì)前面所選的表示方法和相似性度量進(jìn)行組合，由此得到的距離值作為樣本特征集的一部分。

圖3 序列對(duì)在重疊區(qū)域的距離度量Fig.3 Distance measurement of series pair within overlapping area

Bray-Curtis距離的度量值已經(jīng)消除了數(shù)據(jù)點(diǎn)個(gè)數(shù)的影響，使用上文提到的其他度量方法計(jì)算兩序列間的距離時(shí)都需除以對(duì)齊數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

4.2.2 統(tǒng)計(jì)相關(guān)特征

為表征代跑序列的相似性，除距離度量之外，還可引入許多統(tǒng)計(jì)相關(guān)的特征：均值、平均絕對(duì)誤差、最大值、最小值、標(biāo)準(zhǔn)差、平均標(biāo)準(zhǔn)誤差、傾斜度、峰度、協(xié)方差、關(guān)聯(lián)性、絕對(duì)能量、絕對(duì)變化和、復(fù)雜不變距離、高于均值計(jì)數(shù)、低于均值計(jì)數(shù)、最大值首次出現(xiàn)位置、最小值首次出現(xiàn)位置、有無重復(fù)數(shù)值、最大值是否重復(fù)、最小值是否重復(fù)、最大值最后出現(xiàn)位置、最小值最后出現(xiàn)位置、高于均值的最長連續(xù)子串長度、低于均值的最長連續(xù)子串長度、平均絕對(duì)變化、變化和的平均、二級(jí)導(dǎo)數(shù)的中心近似、中位數(shù)、重復(fù)出現(xiàn)數(shù)據(jù)點(diǎn)的比例、唯一數(shù)據(jù)點(diǎn)的比例、樣本熵、重復(fù)出現(xiàn)數(shù)據(jù)點(diǎn)之和、重復(fù)出現(xiàn)數(shù)值之和、所有數(shù)值之和、方差是否大于標(biāo)準(zhǔn)差。

這些特征對(duì)應(yīng)的特征值都是基于序列對(duì)在重疊時(shí)間區(qū)域上的片段計(jì)算得到的；特征抽取時(shí)，將為兩條序列重疊區(qū)域上的片段分別計(jì)算出某個(gè)特征的值，然后計(jì)算兩者之間的差值的絕對(duì)值；布爾值特征不需計(jì)算差值，只需比較兩片段的布爾結(jié)果，根據(jù)是否相同賦值0或1；大部分特征都可以在文獻(xiàn)[24]中找到詳細(xì)的說明。

4.3 分類器訓(xùn)練

對(duì)于本研究中提到的二分類問題，需要選擇一個(gè)合適的分類器從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)并對(duì)測試數(shù)據(jù)進(jìn)行檢測。支持向量機(jī)(SVM)非常適合解決本研究中的分類問題。給定一組訓(xùn)練樣本，其中每個(gè)樣本都屬于兩個(gè)類別中的一個(gè)。SVM訓(xùn)練算法可以在被輸入新的樣本后將其分類到兩個(gè)類別中的一個(gè)，使自身成為非概率二進(jìn)制線性分類器。SVM將訓(xùn)練樣本表示為空間中的點(diǎn)，它們被映射到一幅圖中，由一條明確的、盡可能寬的間隔分開以區(qū)分兩個(gè)類別。隨后新的樣本會(huì)被映射到同一空間中，并基于它們落在間隔的哪一側(cè)來預(yù)測它屬于的類別。

SVM有許多優(yōu)點(diǎn)：首先，它背后的理論基礎(chǔ)十分完善；其次，相對(duì)于其他分類器，SVM盡量保持與樣本間距離的性質(zhì)使其抗攻擊的能力較強(qiáng)；此外，SVM除了能夠處理線性分類問題還可以通過核函數(shù)來高效地解決非線性分類問題，即隱含地將SVM的輸入映射到高維的特征空間當(dāng)中；最后，在實(shí)際的應(yīng)用效果上，SVM在很多數(shù)據(jù)集上都有優(yōu)秀的表現(xiàn)[25]。

在訓(xùn)練SVM前，需要對(duì)生成樣本集的所有特征進(jìn)行縮放。文獻(xiàn)[26]中提到使用支持向量機(jī)分類任務(wù)前進(jìn)行特征的縮放非常重要。特征縮放可避免數(shù)值范圍較大的特征主導(dǎo)數(shù)值范圍較小的特征，同時(shí)還能避免一些數(shù)值計(jì)算問題。具體地，該文推薦將特征縮放到[-1, +1]或者[0, 1]的區(qū)間，即使用0-1標(biāo)準(zhǔn)化的方法進(jìn)行特征的縮放，筆者將參照該建議進(jìn)行后續(xù)的實(shí)驗(yàn)。

完成了特征的縮放，還需要對(duì)現(xiàn)有的特征集進(jìn)行特征選擇。筆者挑選了以下3 種較常用的特征選擇方法：

1) 方差法：預(yù)先設(shè)定一個(gè)方差閾值，如果某個(gè)特征的方差小于閾值，則將該特征刪除。

2)F檢驗(yàn)：可以被用來估計(jì)兩個(gè)隨機(jī)變量之間的線性相關(guān)程度。進(jìn)而可以通過該方法篩選掉高度線性相關(guān)的冗余特征。

3) 互信息：兩個(gè)隨機(jī)變量之間的互信息是一個(gè)非負(fù)值。通過它可以度量兩個(gè)變量之間的依賴程度。當(dāng)該值為0表示兩個(gè)隨機(jī)變量是相互獨(dú)立的，如果值更高說明兩者依賴更強(qiáng)。

實(shí)驗(yàn)前，不存在足以選出最合適的特征選擇方法的依據(jù)，因此將對(duì)這3 種方法進(jìn)行實(shí)驗(yàn)評(píng)估，根據(jù)每種方法對(duì)應(yīng)實(shí)驗(yàn)結(jié)果的優(yōu)劣進(jìn)行選擇。具體的方案設(shè)計(jì)與結(jié)果會(huì)在實(shí)驗(yàn)部分詳細(xì)說明。

選擇支持向量機(jī)作為本研究使用的分類器后，仍需對(duì)核函數(shù)的類型進(jìn)行選擇，線性核和徑向基內(nèi)(RBF)核是最常用的兩種。線性核主要用于線性可分的情形。線性核參數(shù)少、速度快，對(duì)于大部分?jǐn)?shù)據(jù)集的分類效果都比較理想。RBF核主要用于線性不可分的情形。RBF核參數(shù)多，分類結(jié)果非常依賴于參數(shù)。由于缺少充分的選擇依據(jù)，與特征選擇方法類似，將通過實(shí)驗(yàn)進(jìn)行詳細(xì)比較。

除了核函數(shù)之外，SVM還有兩個(gè)重要的參數(shù)γ和C需要確定。γ是針對(duì)RBF這種非線性核函數(shù)的。直觀上而言，它決定了模型對(duì)于特征向量之間區(qū)別的敏感度。較高的γ值會(huì)使訓(xùn)練后的SVM偏差較高，方差較小，反之亦然。參數(shù)C又稱為懲罰項(xiàng)，指的是SVM里拉格朗日乘數(shù)的約束程度。C的大小決定了SVM對(duì)于outlier的忍受程度。較低的C值會(huì)使得決策平面更光滑，而較高的C值將會(huì)讓模型去選擇更多的樣本作為支持向量，進(jìn)而能夠?qū)λ杏?xùn)練樣本進(jìn)行更準(zhǔn)確的分類。對(duì)任意特征選擇方法與核函數(shù)組合，將對(duì)這兩個(gè)參數(shù)進(jìn)行網(wǎng)格搜索，即對(duì)兩個(gè)參數(shù)在特定范圍內(nèi)進(jìn)行遍歷，然后以最優(yōu)實(shí)驗(yàn)結(jié)果代表當(dāng)前特征選擇方法與核函數(shù)組合的效果。

代跑序列對(duì)只占所有序列對(duì)的小部分，由這些序列對(duì)產(chǎn)生的樣本集會(huì)存在類別不平衡的問題，所以在訓(xùn)練SVM時(shí)需要考慮類別權(quán)重。權(quán)重值將與γ，C一起在限定范圍內(nèi)進(jìn)行網(wǎng)格搜索，具體細(xì)節(jié)將在實(shí)驗(yàn)章節(jié)說明。

4.4 代跑檢測

在代跑檢測環(huán)節(jié)，訓(xùn)練得到的分類器會(huì)對(duì)測試樣本集的數(shù)據(jù)進(jìn)行分類，根據(jù)分類結(jié)果對(duì)分類器進(jìn)行相應(yīng)評(píng)價(jià)。

在對(duì)特征集的處理上(特征選擇和特征縮放)，只要和前面訓(xùn)練時(shí)的處理方式保持一致即可。處理完特征集之后，這些樣本將交給分類器去判斷，并和實(shí)際的標(biāo)簽進(jìn)行比較。關(guān)于分類的評(píng)價(jià)指標(biāo)，這里主要考慮分類器對(duì)于代跑序列對(duì)(正例)的鑒別情況，即針對(duì)正例的精準(zhǔn)度、召回率。僅僅是分類的準(zhǔn)確度不能較好地反映代跑檢測的分類效果，因?yàn)檎麄€(gè)樣本集中包含了大量的負(fù)例和少量的負(fù)例，一個(gè)把所有樣本都認(rèn)為是負(fù)例的分類器都可以取得較高的準(zhǔn)確度。同時(shí)經(jīng)過大量的實(shí)驗(yàn)后發(fā)現(xiàn)，針對(duì)負(fù)例的精準(zhǔn)度，召回率基本都是接近1的，有時(shí)可能會(huì)因?yàn)榉诸惼靼岩恍┱`認(rèn)為是負(fù)例使得針對(duì)負(fù)例的精準(zhǔn)度略微降低。而針對(duì)正例的精準(zhǔn)度反映了正例的判別能力，將負(fù)例判別為正例(正常跑步同學(xué)判定為代跑同學(xué))是急需避免發(fā)生的情況，因此該指標(biāo)的理想值應(yīng)為1。針對(duì)正例的召回率反映了正例的回收情況，該值越高表示分類器鑒別出代跑的能力就越強(qiáng)。綜上，在正例的精準(zhǔn)度控制在1的前提下，希望針對(duì)正例的召回率越高越好。

5 實(shí) 驗(yàn)

本節(jié)通過實(shí)驗(yàn)驗(yàn)證所提代跑檢測方案的有效性。首先介紹實(shí)驗(yàn)數(shù)據(jù)，然后比較不同SVM內(nèi)核與不同特征選擇方法組合下的檢測效果，最后通過實(shí)驗(yàn)分析序列對(duì)重疊時(shí)間限制對(duì)代跑檢測效果的影響。

本實(shí)驗(yàn)使用的所有數(shù)據(jù)都是由學(xué)生跑步時(shí)佩戴運(yùn)動(dòng)腕表所采集得到。目前共有代跑序列508 對(duì)(1 016 條)和正常序列800 條，數(shù)據(jù)具體情況見表1。

表1 數(shù)據(jù)概要Table 1 Data summary

5.1 模擬環(huán)境構(gòu)建

由于本研究中使用的心率序列并不是在特定時(shí)間段內(nèi)一并采集的，而為了對(duì)筆者提出的代跑檢測方案進(jìn)行合理評(píng)估，需要將所有心率序列都分配在一個(gè)特定的時(shí)間域中。這樣可以使所有序列之間存在更多的重疊，產(chǎn)生更多區(qū)別于代跑序列對(duì)的正常序列對(duì)，使得最終的評(píng)價(jià)結(jié)果更有說服力。

為了構(gòu)建這樣一個(gè)模擬的測試環(huán)境，需要預(yù)先給定一個(gè)時(shí)間域的范圍，即開始時(shí)間與結(jié)束時(shí)間。然后便可以在這個(gè)時(shí)間域中為所有序列隨機(jī)分配新的采集開始時(shí)間。當(dāng)每條序列都被分配好新的采集開始時(shí)間后，模擬測試環(huán)境的構(gòu)建便已完成，然后進(jìn)行樣本集的生成。

考慮到本實(shí)驗(yàn)使用的心率序列數(shù)量和長度，時(shí)間域?qū)⒃O(shè)為4 h，即所有的心率序列的起點(diǎn)都會(huì)被分配于該時(shí)間范圍中的任意秒上。雖然該選擇并沒有足夠的依據(jù)支撐，但主要考慮了如下幾點(diǎn)：1) 使重疊的序列對(duì)更多，能對(duì)代跑序列對(duì)的鑒別產(chǎn)生干擾；2) 該范圍相當(dāng)于一個(gè)下午內(nèi)適宜鍛煉的時(shí)間長度，可以使實(shí)驗(yàn)更接近真實(shí)的場景；3) 只要保證時(shí)間域中存在充分?jǐn)?shù)量的重疊序列，該時(shí)間域的范圍是可以自由調(diào)整的。

5.2 不同特征選擇算法對(duì)檢測結(jié)果的影響

本實(shí)驗(yàn)分別使用方差法、F檢驗(yàn)和互信息這3 種特征選擇算法對(duì)SVM的線性核和RBF核進(jìn)行實(shí)驗(yàn)比較，用以判定哪種特征選擇算法與內(nèi)核的組合最適用于解決代跑檢測問題。4.4節(jié)已對(duì)代跑檢測的目標(biāo)進(jìn)行說明，下面的實(shí)驗(yàn)中將不對(duì)負(fù)例(正常序列對(duì)產(chǎn)生的樣本)的精準(zhǔn)度和召回率進(jìn)行討論。具體地，每一種組合都將對(duì)SVM參數(shù)γ(只針對(duì)RBF核)、C還有類別權(quán)重這3 個(gè)參數(shù)進(jìn)行網(wǎng)格搜索。這3 個(gè)參數(shù)都以指數(shù)增長的序列作為搜索范圍，其中γ=10-3，10-2，…，103，C=10-3，10-2，…，103，類別權(quán)重(正例與負(fù)例權(quán)重之比)=20，21，22，23，24，25，26，27。

圖4，5是使用F檢驗(yàn)作為特征選擇算法的實(shí)驗(yàn)結(jié)果，分別顯示了正例精準(zhǔn)度和召回率隨特征選擇個(gè)數(shù)變化的情況。F檢驗(yàn)將高度線性相關(guān)的特征刪除。所選特征的個(gè)數(shù)由5到55，間隔為5。從圖中可以看出：只有RBF核選擇5 個(gè)特征可以達(dá)到100%的精準(zhǔn)度。正例召回率隨著特征選擇個(gè)數(shù)的增多有上升的趨勢，而正例精準(zhǔn)度并沒有呈現(xiàn)出明顯的趨勢。

圖4 通過F檢驗(yàn)進(jìn)行特征選擇時(shí)的正例精準(zhǔn)度Fig.4 Positive sample precision using F test

圖5 通過F檢驗(yàn)進(jìn)行特征選擇時(shí)的正例召回率Fig.5 Positive sample recall using F test

圖6，7是使用互信息作為特征選擇算法的實(shí)驗(yàn)結(jié)果，類似前一實(shí)驗(yàn)，分別顯示了正例精準(zhǔn)度和召回率隨特征選擇個(gè)數(shù)變化的情況。互信息將高度相互依賴的特征刪除。所選特征范圍與前一實(shí)驗(yàn)相同。從圖6中可以看出：使用互信息作為特征選擇算法時(shí)，精準(zhǔn)度最高只能到95%左右。正例召回率和正例精準(zhǔn)度和前一實(shí)驗(yàn)情況相同。

圖6 通過互信息進(jìn)行特征選擇時(shí)的正例精準(zhǔn)度Fig.6 Positive sample precision using mutual-info

圖7 通過互信息進(jìn)行特征選擇時(shí)的正例召回率Fig.7 Positive sample recall using mutual-info

圖8，9是使用方差法作為特征選擇算法的實(shí)驗(yàn)結(jié)果，顯示內(nèi)容與前面實(shí)驗(yàn)一致。方差法將方差小于設(shè)定閾值的特征刪除。其中，當(dāng)方差從0到0.02按0.002遞增時(shí)(預(yù)先對(duì)不同方差閾值進(jìn)行實(shí)驗(yàn)后確定的范圍)，剩余的特征個(gè)數(shù)分別為：54，53，50，46，41，37，36，34，31，26，24。從圖8，9中可以看出：此時(shí)線性核不論是在精準(zhǔn)度還是召回率上都明顯優(yōu)于RBF核。其中方差閾值設(shè)為0.01，0.012和0.014時(shí)線性核能在最高的精準(zhǔn)度下達(dá)到的最高召回率?？紤]到0.01和0.014為這個(gè)最優(yōu)范圍的邊界，實(shí)際效果可能會(huì)存在一定的波動(dòng)，因此選擇0.012作為最終選擇的閾值。綜上，通過方差法以0.012閾值篩選出的特征集通過線性核SVM進(jìn)行訓(xùn)練能夠達(dá)到最優(yōu)的檢測效果。后面將以該組合進(jìn)行實(shí)驗(yàn)。

圖8 通過方差法進(jìn)行特征選擇時(shí)的正例精準(zhǔn)度Fig.8 Positive sample precision using variance

圖9 通過方差法進(jìn)行特征選擇時(shí)的正例召回率Fig.9 Positive sample recall using variance

5.3 不同重疊時(shí)間限制對(duì)檢測結(jié)果的影響

圖10是使用不同重疊時(shí)間限制生成樣本集后，使用5.2節(jié)選出的最優(yōu)方案組合的實(shí)驗(yàn)結(jié)果，顯示了檢測結(jié)果隨重疊時(shí)間限制變化的情況。其中，重疊時(shí)間限制從100 s到500 s按50 s遞增。從圖10中可以看出：隨著該參數(shù)增大，精準(zhǔn)度并未有明顯改變，而召回率雖然有波動(dòng)但總體呈現(xiàn)出上升的趨勢。召回率這樣變化的原因很可能是由于重疊時(shí)間限制增大后，正常序列對(duì)便會(huì)減少，使得代跑序列對(duì)的相對(duì)比率更高，分類器也能更側(cè)重正例的辨別。

圖10 序列對(duì)重疊時(shí)間限制對(duì)檢測效果的影響Fig.10 Effect of limit overlapping time to detection

6 結(jié) 論

由學(xué)生的跑步監(jiān)測提出了多表代跑的問題，并根據(jù)該問題提出了一套基于SVM的代跑檢測方案。該方案先由大量序列對(duì)生成樣本集，再基于部分樣本集訓(xùn)練SVM，最后使用訓(xùn)練得到的分類器進(jìn)行剩余樣本的代跑檢測。筆者也對(duì)當(dāng)前最有效的幾種特征選擇算法進(jìn)行了比較，確定方差法為最適合本類型問題的方法。實(shí)驗(yàn)對(duì)所提方案進(jìn)行了充分的比較和驗(yàn)證，結(jié)果表明所提方案能夠在精準(zhǔn)度為100%的情況下取得較高的召回率。