結合半監督與主動學習的時間序列PU問題分類

陳 娟，朱福喜，2

CHEN Juan1,ZHU Fuxi1，2

1.武漢大學 計算機學院，武漢 430072

2.漢口學院 計算機科學與技術學院，武漢 430212

1.Computer School,Wuhan University,Wuhan 430072,China

2.School of Computer Science and Technology,Hankou University,Wuhan 430212,China

1 引言

時間序列是一系列按時間點取得的觀測值，產生于許多自然或經濟生產過程，如股票市場、醫學、科學和自然觀測[1-2]，一般可表示為序列T=t[1],…,t[j],…,t[n]。其中n表示其長度，t[j]表示時刻 j得到的觀測值，T表示按時間順序得到的觀測值序列。

近年來，時間序列分類引起了國內外學者的研究興趣。時間序列分類是指，基于已經標注的時間序列數據樣本，構建數學模型，用于預測未知類別時間序列的類別，如在醫學診斷中，通過患者與正常人的心率變化觀測值（時間序列數據）作為訓練集，構建數學模型，針對檢查者的時間序列數據樣本，通過數學模型判斷其是否為患者。

一般分類模型總是通過足夠的目標類(P)標注數據以及非目標類(N)標注數據進行有監督學習并構建分類器[1-2]，然而由于很多領域（比如醫療、工業應用中）對數據的標注代價過大，數據量的驟增進一步加大了標注數據的難度[3]。因此，出現了基于PU問題的分類，即通過少量標注的目標類(P)數據以及大量未標注(U)的數據，進行訓練，從而得到一個分類模型。這種方法大大降低了人工標注數據量，從而有效減少了獲取完整標注訓練集的代價[4]。

在PU問題的分類中，由于訓練集中僅包含目標類(P)的標注數據，不存在非目標類(N)的標注數據，導致通過有監督學習構建分類器的方式難以適用于其中。因此，有學者提出先采用半監督學習，獲取足夠的標注數據作為分類器的訓練數據，再進行分類器的構建。其過程為：首先，以半監督學習對未標注數據集U中的數據進行自動標注；然后，以自動標注得到的數據集作為訓練集，構建分類器[4-7]。然而，半監督學習對于分類平面附近的數據難以準確地自動標注，而恰恰這些數據對于分類平面的確立又至關重要。

針對上述問題，本文擬采用主動學習對PU問題中未標注數據集進行數據選擇，選出邊界數據樣本并人工標注，以得到準確的標注訓練集，從而以標注數據集進行分類器構建。本文的主要工作如下：

（1）將主動學習技術應用于基于PU問題的時間序列分類中，選擇少量邊界數據，通過人工標注，得到可靠標注訓練集，繼而構建分類器，實現精準分類。

（2）提出一種基于QBC（Query By Committee）度量數據樣本不確定性的方法，作為主動學習的數據選擇策略。

（3）提出一種結合主動學習與半監督學習的方法SAL，以獲取足夠多的標注訓練數據。

（4）以主動學習選擇得到的人工標注數據以及半監督學習得到的自動標注數據作為標注訓練集，構建基于PU數據集的分類器，用于對未知類別數據進行類別的預測。

2 相關工作

Li Wei等[5]提出一種半監督學習框架用于對PU數據集構建分類器，從未標注數據集DU中選擇與P類數據集最近鄰的未標注數據樣本u，標注為P類，迭代標注直至達到停止條件，其中停止條件根據P類數據集中最近鄰數據對的相似性距離的變化趨勢確定。

Ratanamahatana C A等[6]在Li Wei的文獻[5]的基礎上，進一步對停止條件進行研究，其停止條件通過后驗式的方法進行確定。首先，將未標注數據集U中所有數據樣本，根據與P類標注數據集中數據樣本的相似性距離，依次加入P類標注數據集，并計算每個數據樣本加入后的停止標準置信度，最后基于此置信度確定上述迭代過程的停止條件。

Nguyen M N等在文獻[7-8]中，提出了LCLC（Learning from Common Local Clusters）的方法，即基于共同局部簇學習的方法，將未標注數據集劃分為LP（Likely Positive）、LN（Likely Negative）、RN（Reliable Negative），與P一起作為訓練集構建1NN分類器；文獻[8]是在LCLC方法[7]上進行深入研究，針對LCLC方法中假設每個簇中數據樣本的類別一致的問題進行了改進，提出了通過多次采用LCLC對未標注數據進行類別置信度計算，根據置信度將類別傾向不明確的數據樣本從未標注數據集U中刪除，最后以剩余的數據樣本作為訓練數據集，構建KNN分類器。

針對時間序列數據的PU學習問題，有學者利用Markov性質和“完全隨機假設”設計出了正例未標Markov（Positive Unlabeled Markov，PU Markov）時間序列分類器。實驗證明其算法能提高滿足Markov性質的時間序列分類的效率。但該算法適用范圍有限，且對最優分類方法的選擇方式難以確定[9]。

張影提出利用已經標記的正類點、負類點以及基于所有點構造的Universum數據集，采用U-SVM進行訓練。采用訓練得到的模型，來標記可靠的正類點以及可靠的負類點，以生成新的訓練集。通過迭代的方法來重復上述過程，直到滿足某種迭代終止條件[10]。

主動學習關鍵在于數據的選擇策略[3]。基于數據樣本的不確定性，選擇根據當前訓練集最難以確定其類別的數據樣本用于人工標注；基于數據樣本對訓練集構建分類模型的期望值，選擇標注之后能夠對當前訓練集所構建的分類模型產生最大改變的數據樣本，用于人工標注；基于數據樣本對訓練集構建分類模型的期望錯誤率，選擇標注后能夠對當前訓練集所構建的分類模型產生最小期望錯誤率的數據樣本；基于投票委員會QBC，根據訓練集數據構建多個不同的分類模型，作為委員會（Committee），并對未標注數據集U中數據樣本進行投票，以投票結果不一致性作為數據選擇策略。

趙建華等在文獻[11]中，提出了一種結合主動學習到半監督學習中的方法，通過主動學習選擇信息量高的數據樣本進行自動標注，主要是對問題規模進行了縮減，從其實驗結果中可以得出，其準確率相對于該文中選擇的半監督方法幾乎沒有提升，因為文中并沒有通過人工標注信息量高的數據樣本來保證正確性。

鑒于半監督學習方法在PU問題的應用過程中，自動標注難以確保對訓練集中數據樣本標注的正確性，從而影響所構建分類器的準確率，主動學習通過人工標注訓練集中部分高信息量的邊界數據樣本[12]，能夠更加精準地確立分類平面，從而提高分類器準確率，藉此本文對如何應用主動學習于PU問題進行研究，并提出了一種結合主動學習以及半監督學習[13]的方法。

3OAL算法

基于PU問題的分類方法關鍵在于如何正確標注未標注數據集DU中的P類、N類數據樣本，而分類邊界附近數據樣本的正確標注則更具挑戰性。半監督學習，作為一種常用于PU問題中標注數據樣本的方法，在一定程度上能夠實現對未標注數據樣本的自動標注，但是其對分類邊界附近的數據樣本仍難以準確標注。因此，本文提出一種方法OAL（Only Active Learning），在時間序列的PU問題分類中，采用主動學習對未標注數據集中數據樣本進行有選擇性的標注，即選擇分類邊界附近的數據樣本，進行人工標注，以解決數據樣本標注不準確的問題。

3.1OAL算法流程

在基于PU問題的時間序列分類中，初始訓練集僅含有少量標注的P類數據集DP，以及大量未標注的數據集DU，其中并沒有N類的標注數據，因此本文主動學習選擇數據過程分為兩個步驟，即初始N類數據樣本的獲取與邊界數據樣本的獲取。

本文算法模型如算法1所示。其主要步驟是：第一，獲取準確標注的初始N類數據集DN，采用與文獻[5]中找P類數據相類似的方法，即將未標注集DU中與P類數據最不相似的數據樣本u選出，迭代進行人工標注，直至u的類別為N ，則DN={u}；第二，以DP、DN的并集L作為訓練集，構建數據選擇模型M；第三，根據M從未標注數據集DU中選擇數據樣本u，判斷是否滿足主動學習停止準則，若是，則停止主動學習過程；若不是，則人工標注u，加入L。迭代上述第二、三步，直到滿足主動學習停止準則；第四，根據主動學習過程得到的標注訓練集，構建分類器。

算法1

輸入：輸入初始DP、DU

輸出：分類器

1.獲取N類數據DN，得L=DP∪DN

2.基于L，構建數據選擇模型M

3.根據M，選擇數據樣本u

4.while未達到停止準則

5. 人工標注u，加入L

6. 基于L，構建數據選擇模型M

7. 根據M，選擇數據樣本u

8.end while

9. 根據L，構建分類器

3.2 構建數據選擇模型M

針對基于投票委員會（QBC）方法[14]，根據時間序列的特點，構建多個不同的分類器C1,C2,…,CK，作為數據選擇模型M，分別對未標注數據集U中數據樣本進行類別概率預測，以不同分類器的預測結果計算數據樣本的不一致性，結合數據樣本的區域密度，作為主動學習的數據選擇策略。本文方法與傳統QBC方法有所區別的是，并沒有直接根據多個不同分類器的投票結果進行計數從而分類，而是采用QBC的思想結合多個不同分類器對未標注數據樣本的類別進行預測，并以此為據計算未標注數據樣本屬于每個不同類別的概率。

3.2.1 時間序列多分類器構建

針對時間序列是由一組隨著時間變化的序列值，由于數據本身的誤差，或者數據獲取過程中的誤差，將會導致每個時間點的數據采樣會有誤差波動。本文通過均值化，將原始時間序列作2-均值、3-均值等多均值轉換，構建多個訓練數據集，其中原始訓練集中時間序列看作為1-均值轉換，本文中均值指算術平均數。K-均值是指對時間序列的每個點，以當前點開始的K個時間序列采樣點的算術平均數作為當前時間點的值。如K取2，原始時間序列 Torigin=[1.2，2.2，3.2，4.2]，則2-均值時間序列：

時間序如圖1～3所示，分別表示數據集ECG[5]某個數據樣本的1-均值、2-均值、3均值序列示意圖，（a）圖所示為兩個P類數據樣本，（b）圖所示為一個P類數據樣本、一個N 類數據樣本，從圖1～3中的（a）圖可發現，隨著均值的增加兩個P類數據樣本之間的距離在減小，尤其是波動較明顯部分，如序列的最后幾個數據采樣；從圖1～3中的（b）圖可知，數據樣本作多均值轉換，并不會降低異類數據樣本之間的距離，圖中有差異的區域部分在圖1～3均值序列下都保持著類似的距離差。

圖1 ECG數據1-均值示例圖

圖2 ECG數據2-均值示例圖

圖3 ECG數據3-均值示例圖

綜上所述，時間序列的K-均值變換能夠使得同類數據樣本相似性距離更加小，同時不同類別數據樣本之間相似性距離基本不變，其中相似性距離采用歐式距離度量[15]。因此，本文對原訓練集進行1-均值、2-均值、…、K-均值變換，則可得到K個訓練數據集，分別構建分類器得到K個分類器C1、C2、…、CK。

3.2.2 數據樣本的不一致性Diff

對于i-均值變換得到的訓練集Li，其中i的取值范圍為[1,K]，對U中數據樣本u作i-均值變換得ui，計算ui到Li中P類、N類的相似性距離：

其中

ui與某類別的相似性距離越小，則ui是此類別的可能性越大。因此，定義ui屬于P類、N類概率如下：

其中，

根據K個訓練集的計算結果，采用QBC方法思路，通過多個分類器計算u屬于不同類別的概率，定義數據樣本u屬于P類、N類的概率Pr(u,P)、Pr(u,N)如下：

根據公式（4）、（5）定義數據樣本u的不一致性，有：

由式（3）可知 Pr(u,P)+Pr(u,N)=1，則 Diff(u)的取值范圍為[0，1]，Diff(u)越大，u的一致性越差，則數據樣本越應該被選擇用于人工標注。

3.2.3 數據樣本的區域密度Den

為了避免選擇離異點數據，本文在考慮數據樣本的類別不一致前提下，分析數據樣本的密度，選擇區域密度大的數據樣本用于人工標注。本文僅在原始訓練集中計算未標注數據樣本的區域密度。數據樣本u的區域密度通過其與近鄰數據的相似性距離均值進行計算，定義如下：

其中，NNi表示數據樣本u的第i個近鄰數據樣本，M表示取數據樣本u的M個近鄰數據樣本進行區域密度的計算，本文中M 取值5。Den(u)越小說明其近鄰數據樣本與u越緊湊，從而表示u附近數據樣本分布密度越高，標注數據樣本u之后能夠提供更多的有效信息。

3.2.4 數據選擇參數Info

本文綜合考慮上述兩個因素，作為未標注數據樣本的選擇策略，定義如下：

Info(u)值越大，表現為數據樣本u的分類結果一致性差，且所在區域分布密度高。因此，本文在主動學習過程中，選擇Info值最大的數據樣本用于人工標注。

3.3 停止準則

在完成上述3.2節的數據選擇過程之后，計算被選擇用于人工標注的數據樣本u，是否能夠提供有效的信息量。通過以u和標注數據集作為訓練集，對訓練集中剩余未標注數據樣本進行最近鄰分類，如果沒有以u為最近鄰的未標注數據樣本，則停止主動學習，因為即使標注了u也不能對分類器的下一步構建提供有效信息量。

由于樣本的選擇是通過未標注數據樣本不一致性和區域密度進行計算的，因此選擇的未標注數據樣本會逐漸趨向于P、N類的分類邊界，在最壞的情況下，分類邊界處的數據樣本全部標注之后，上述停止準則也能滿足。本文實驗也證明了，在人工標注數據量占數據集比例25%以下停止準則就已經達到。

3.4 SAL算法

PU問題存在大量的未標注數據樣本，僅通過主動學習選擇數據樣本用于人工標注，將會導致人工標注數據量過多，而且通過學習得到的標注數據量并不充足，因此，本文提出一種將主動學習與半監督學習相結合的SAL（Semi-supervised Active Learning）算法，進行數據標注。在主動學習過程中，結合半監督學習對部分數據樣本進行自動標注，有效降低主動學習人工標注數據量的同時，增加最終訓練分類器的標注數據量。

具體實現為，根據3.2.2節計算得到未標注數據集DU中所有數據樣本的Diff值，選取最小的NUM個數據樣本u1,…,ui,…,uNUM，根據Pr(ui,P)、Pr(ui,N)進行自動標注，前者大(Pr(ui,P)＞Pr(ui,N))則標注ui為P類，否則標注ui為N類，NUM為實驗參數，具體由實驗確定。

4 實驗

4.1 分類器構建

基于PU問題的分類，其最終目的在于構建一個高準確率的分類器。通過本文提出的OAL或者SAL方法，或者半監督學習方法從未標注數據集U中獲取足夠多的標注數據，以獲取的標注數據進行有監督學習，構建分類器，用于對未知類別數據樣本進行類別預測。

對于通過學習得到的標注訓練集，其中包括目標類(P)以及非目標類(N)的標注數據，本文構建分類器采用1NN方法，用于對未知數據樣本進行類別預測，以測試本文方法的有效性。1NN分類方法作為一種經典的分類方法，被證明是高效的、易于實現的。很多研究表明，時間序列分類的最好分類結果來源于簡單的最近鄰分類（1NN）方法[15]。

4.2 數據集

實驗數據分別采用 ECG、Word Spotting、Wafer、Yoga數據集[5]。實驗數據如表1所示，其中，Training Set、Testing Set分別表示訓練集、測試集；P、N 分別表示目標類、非目標類；如ECG數據訓練集中含目標類數據樣本208個，非目標類數據樣本602個。

表1 實驗數據集說明

4.3 實驗說明

本文在實驗中模擬人工標注過程，即將訓練集分為標注集和未標注集，通過主動學習選擇的數據樣本，則加入標注集，并使用真實標注信息，而U中數據樣本視為沒有標注。通過主動學習得到標注數據集，再構建分類器，以分類器對測試集的分類效果檢測本文方法的有效性。具體實現過程如下。

首先，訓練集（Training Set）包括標注的正類數據集DP、未標注數據集U、負類數據集DN為空；其次，通過主動學習（OAL、SAL），將U 中部分數據進行標注，并根據標注的類別加入DP或DN。然后，以學習得到的DP以及DN，作為訓練集，構建1NN分類器。最后，在對未知類別數據樣本u進行預測類別時，計算u到{DPU DN}中所有數據樣本的距離，以u最近鄰數據樣本的類別作為u的預測類別。

最終，分類效果則通過分類器對測試集（Testing Set）中數據樣本進行類別預測，即以單個數據樣本是否能夠被正確分類為依據，進而根據測試集中所有樣本是否被正確分類進行統計，以計算通過本文算法得到的標注訓練數據集所構建的1NN分類器的分類效果F-measure。

4.4 結果分析

4.4.1 對比實驗

首先，通過將本文方法OAL、SAL與2006、2008、2011、2012、2015年五篇針對時間序列PU問題進行研究的國際學術論文結果作對比，分析本文方法有效性，效果圖如圖4所示。其次，由于本文方法中需要人工參考標注過程，因此需要對人工標注量進行分析，OAL、SAL的人工標注比例如表2所示。

圖4 不同方法的分類效果對比

表2 人工標注量分析%

從圖4中可知，OAL、SAL相對于上述五篇國際學術論文中提出的半監督學習方法，在數據集ECG、Wafer、Word的表現上，優勢非常明顯，且差異顯著。在數據集Yoga上，相對于2006、2008、2015年的方法優勢同樣非常明顯，而相比于2011、2012年基于聚類的半監督方法，分類效果也好。說明，本文方法OAL、SAL，由于人工標注了通過主動學習選擇的邊界數據樣本，因此能夠更加準確標注未標注數據集U中的數據樣本，從而構建分類效果更好的分類器。

從圖4可知，SAL方法在分類效果F-measure上與OAL不相上下，再從表2中所需人工標注量分析，本文SAL算法能夠有效降低人工標注數據樣本量。顯然，由于SAL自動標注的數據樣本不斷加入，訓練集中標注數據量更加充足，所能提供的信息量更多，從而需要的人工標注量減少，而邊界附近的數據樣本同樣是以人工進行標注，因此也能保證未標注數據樣本的標注正確性。從表2也可得出，本文方法SAL在提高分類效果的同時，能夠將人工標注量有效控制在10%以內。

4.4.2 SAL方法參數實驗

在SAL方法中，每次迭代都自動標注部分不一致性最小的數據樣本，由于自動標注難以保證百分之百的準確性，過多地自動標注可能導致錯誤標注的出現，但是過少的自動標注又顯得毫無意義。因此本文通過實驗分析每次主動學習迭代過程中自動標注的樣本數量。實驗結果如圖5所示。

圖5 SAL參數分析

從圖5（a）中可知，隨著自動標注量的增多，ECG、Wafer數據集的F-measure值基本保持不變。Yoga數據集呈現出略微的波動，但是整體上來說，并沒有大的變化。而Word數據集隨著自動標注量的增加F-measure有下降的趨勢，自動標注量取值為5、6、7之后，F-measure呈下降明顯。綜上所述，說明不同數據集的數據分布不一樣，從而使得自動標注的數據準確率不相同，即指ECG、Wafer與Yoga數據集不同類別數據樣本分布區域離分類平面較遠，因此自動標注數據樣本的準確率高，從而即使增多自動標注數據樣本也不會導致最終F-measure的下降，而Word數據集不同類別數據樣本分布區域較分類平面近，從而自動標注過程更加容易出現誤標注，隨著自動標注量的增加而導致F-measure值下降。

從圖5（b）可知，自動標注量的增加，人工標注量在減少。顯然，自動標注的增加使得標注數據集的信息量加大，從而更早停止主動學習過程。自動標注量取值為5、6、7時，人工標注量開始趨于穩定。

綜上所述，SAL方法中自動標注量參數取值為6，能夠在降低人工標注量的同時，保持標注訓練集的分類效果。

5 結束語

本文針對時間序列的PU問題分類，提出了基于主動學習的方法，通過少量的人工標注，得到正確標注的邊界數據，從而訓練出更加精準有效的分類器。由于人工標注的數據量有限，本文結合半監督學習與主動學習的方法，在進行人工標注的同時對數據樣本自動標注，有效降低了在主動學習過程中人工標注量，并增加了標注訓練數據量。

本文采用最近鄰算法作為分類器的構建方法，應用主動學習于PU問題中相比半監督學習能夠得到更好的分類效果，將繼續研究如何將本文方法有效結合于某些復雜模型構建分類器如SVM，以使得分類效果更加突出。

參考文獻：

[1]Xing Zhengzheng，Pei Jian，Yu Philip S，et al.Extracting interpretable features for early classification on time series[J].Knowledge&Information Systems，2012，31（1）：105-127.

[2]Arathi M，Govardhan A.Accurate time series classification using shapelets[J].International Journal of Data Mining&Knowledge Management，2014：39-47.

[3]Settles B.Active learning literature survey[R].University of Wisconsin-Madison，2010：127-131.

[4]劉露，彭濤，左萬利，等.一種基于聚類的PU主動文本分類方法[J].軟件學報，2013，24（11）：2571-2583.

[5]Li Wei，Eamonn K.Semi-supervised time series classification[C]//ACM Sigkdd International Conference on Knowledge Discovery&Data Mining，2006：748-753.

[6]Ratanamahatana C A，Wanichsan D.Stopping criterion selection for efficient semi-supervised time series classification[M]//Software Engineering，Artificial Intelligence，Networking&Parallel/Distributed Computing.Berlin Heidelberg：Springer-Verlag，2008：1-14.

[7]Nguyen M N，Li X L，Ng S K.Positive unlabeled learning for time series classification[C]//International Joint Conference on Artificial Intelligence，2011：1421-1426.

[8]Nguyen M N，Li X L，Ng S K.Ensemble based positive unlabeled learning for time series classification[C]//Database Systems for Advanced Applications，2012：243-257.

[9]張道坤.針對文本和時間序列數據的正例未標注學習算法研究[D].陜西咸陽：西北農林科技大學，2015.

[10]張影.基于SVM的PU問題與半監督問題研究[D].北京：中國科學院大學，2015.

[11]趙建華，劉寧.結合主動學習策略的半監督分類算法[J].計算機應用與研究，2015，32（8）：2295-2298.

[12]劉康，錢旭，王自強，等.主動學習算法綜述[J].計算機工程與應用，2012，48（34）：1-4.

[13]陳榮，曹永鋒，孫洪.基于主動學習和半監督學習的多類圖像分類[J].自動化學報，2011，37（8）：954-962.

[14]陳念，唐振民.QBC主動采樣學習在垃圾郵件在線過濾中的應用[J].計算機工程與應用，2014，50（22）：170-174.

[15]Serrà J，Arcos J L.An empirical evaluation of similarity measures for time series classification[J].Knowledge-Based Systems，2014，67（3）：305-314.