改進DBA算法的眼動模式分析

陳子麟，戰蔭偉，楊 卓

廣東工業大學 計算機學院，廣州 510006

眼動追蹤是衡量視覺注意力分布的一項重要技術，通常用以分析參與者在視覺刺激上完成任務的表現，目前已廣泛應用于市場營銷、神經科學、人機交互和閱讀分析等領域。隨著眼動追蹤技術的進步和設備成本的降低，眼動追蹤技術能夠以更高的速率產生更多的數據[1]，正從實驗室走向實際應用領域。

在教育領域，傳統的教學模式是教師與學生面對面教學，教師受制于學生人數，無法對所有學生的學習狀態進行有效的監測，教學效率難以提高。而今網絡在線課程蓬勃興起，采用視頻錄播的方式進行教學能夠合理分配教育資源，提升教學效率。然而，在線學習缺乏線下教學的氛圍，更易受環境干擾，學習者的注意力會不自覺地從與任務相關的事物轉移到與任務無關的思考中，即心理學上所謂的心智游移現象。大量研究已經證明這種現象是普遍存在的，且與各種任務之間的效率呈負相關關系，與任務的復雜度呈正比例關系[2]。更為不幸的是，這是一種高度內在的狀態，不易從明顯的行為和表情中進行推斷。人類的認知活動和眼睛的行為有密切關聯，因而利用眼動數據來挖掘不同的眼動模式，進而分析學生的學習狀態成為解決這種問題的一種途徑。

近年來，在教育領域，眼動追蹤已用于探索學生的學習模式，以期把握學生的真實需求，開展個性化教育，提升教學質量。程時偉等人[3]基于注視點和眼跳等眼動數據生成可視化批注，能夠有效幫助學生提高閱讀水平。安璐等人[4]以15名大學生為被試，利用眼動數據分析PPT背景顏色對學生的影響。Mason等人[5]錄制專家閱讀時的眼動數據并用其引導初學者學習，該方法能有效提高學習效率。Rahman等人[6]在VR教學環境下，通過可視化技術分析學生的凝視數據，識別走神的學生并給予個性化指導。眼動追蹤還能夠幫助評估用戶在探索性學習環境中的行為，所收集的數據可以用來改進學生模型[7]。

眼動掃描路徑是眼睛在觀察事物時隨著時間的變化而產生的一系列注視點，即在視覺刺激下視線變化的位置。眼動模式則是群體的代表性掃描路徑，是群體眼動行為的共性抽象。相同時間內掃描路徑的共性和差異能夠揭示不同的眼動模式，幫助分析參與者內在的情感認知和閱讀策略。Frame等人[8]通過比較在復雜搜索任務中掃描路徑的相似性來區分專家和新手的搜索策略，以改善對新手的培訓。Tablatin等人[9]提出STA（scanpath trend analysis）算法來分析掃描路徑的趨勢，證明在計算機編程中，成績優秀的學生具有不同的閱讀策略，但都遵循相同的邏輯方式。這類研究表明，通過掃描路徑探索群體的眼動行為，進而分析潛在的認知過程是高度可行的。

很多學者為探索群體的閱讀策略和情感認知進行了研究。Eraslan等人[10]提出一種eMINE方法，結合最長公共子序列算法和層次聚類算法來獲取公共掃描路徑作為群體的眼動模式。Ming等人[11]則根據NW（Needleman-Wunsch）算法度量掃描路徑之間的相似性，選擇與其他實例相似度最高的掃描路徑作為群體的眼動模式。然而，上述方法都要求掃描路徑必須先轉換為字符串，再采取字符串匹配算法進行比較，因而丟失了空間分布。Kurzhals等人[12]則另辟蹊徑，用可視化這種直觀的方式來分析掃描路徑，提出Gaze Stripes[12]將所有參與者的掃描路徑映射到圖像縮略圖的水平軸上，以時間對齊的方式分析和比較參與者隨時間變化的觀看行為。然而，隨著用戶數量的增加，視覺效果明顯降低且算法性能低下。為了解決這類問題，文獻[13-14]采用顏色編碼的鄰接矩陣來挖掘眼動模式。先利用相似性度量算法計算成對掃描路徑的相似度，并在顏色編碼的鄰接矩陣中展示，再對矩陣排序以進行聚類分析。該方法利用交互技術與原始刺激鏈接，能夠通過矩陣中不同的顏色區域揭示不同的眼動模式，算法復雜度較低且不受用戶數量限制。然而，在矩陣中采用聚類重排序技術[15]取得的聚類效果較差，無法很好地分離不同的眼動模式。

本文針對上述方法的局限性，對DBA算法進行改進，并用來計算群體的代表性掃描路徑，識別異常的眼動行為；同時分別利用DTW和改進的DBA算法計算時間序列的相似度和聚類種子，通過一種距離密度聚類方法對時間序列進行聚類。最后根據聚類個數和性能評估專注、走神及信息迷航三種學習狀態。

1 數據建模與轉換

與眼動數據相關的基本術語的定義可參考文獻[16]，這里簡要介紹文中使用的幾種指標，詳見圖1。其中，凝視點是從眼動設備中采集獲取的原始眼動數據；注視點是由指定區域和時間跨度的凝視點聚集而來；掃視描述了從一個注視點到另一個注視點的快速眼動過程；掃描路徑則表示一系列交替的注視和掃視的序列；感興趣區域（area of interest，AOI）是根據視覺刺激的語義信息創建的，通常標記為一個對象的整體或部分。

1.1 掃描路徑構建

當人們觀察事物時，注視點的位置是不斷發生變化的，并隨著大腦思維的變化而起伏不定。這些注視點位置的變化即構成了觀察者在觀察整個事物時的眼動行為。給定一組有序的注視點P={p1,p2,…,pm},pi=(xi,yi)表示時刻ti的注視點位置，t1＜t2＜…＜tn。任意兩個連續注視點的坐標連成一條線，表示眼睛從視覺刺激的一個位置移動到另一個位置。

1.2 創建AOI

在自由觀看條件下，吸引觀察者注意力的不是單個像素，而是整個感興趣區域（AOI）。對于相同的目標，觀察者的注意力可能分布在不同的位置。因此，基于注視的掃描路徑無法促進抽象的表達，難以探索參與者眼動行為的相似性。本文通過AOI序列來代替參與者的掃描路徑，采用均值漂移算法（mean-shift algorithm），把注視點聚類為AOI，生成眼動序列。均值漂移算法無需輸入聚類個數，Santella等人[17]已將其用于眼動分析，證明比k-means算法具有更好的性能。對注視點執行均值漂移聚類算法后獲得集群個數，每個集群代表一個AOI。本文將聚類的質心坐標作為AOI的坐標，再根據注視點距AOI質心坐標的最小距離，將注視點分配在AOI中，并以AOI的質心坐標代替原來的注視坐標。

2 相關技術

2.1 動態時間規整

動態時間規整（dynamic time warping，DTW）可以用來比較具有兩個不同長度的時間序列[18]。給定兩個長度分別為m和n的序列X=(x1,x2,…,xi,…,xm)和Y=(y1,y2,…,yj,…,yn)，構建距離矩陣：

其中，dij為點xi和點yj之間的歐氏距離。

DTW算法需要從（1，1）到(m,n)找到一條最優路徑W=來匹配序列。為確保該路徑全局最優，須同時滿足三個條件：有界性、連續性和單調性。有界性意味著路徑的起點為（1，1）和終點為(m,n)；連續性指不能跨過某個點去匹配，路徑中的下一個點必須與當前點相鄰，即(i,j)的下一個點必須是(i+1,j)、(i,j+1)或(i+1,j+1)；單調性指路徑保持時間順序單調不減。滿足上述三個條件時，可以將DTW定義為：

其中，d(wk)=d(xi,yj)表示為路徑中k處對應的i和j。路徑的累計距離可以通過遞歸計算得：

2.2 重心平均動態時間規整

在許多場景中，通常使用時間序列集合的平均序列來代表整個集合。然而，集合中的每條時間序列長度不一定相等，且其特征在時間軸上可能是錯位的。若按照逐個時間點一一對應的方式計算平均序列，無法取得很好的結果。為此，數據挖掘領域提出了基于DTW計算平均時間序列的方法，主要分為局部平均策略和全局平均策略。局部平均策略采用迭代計算成對時間序列的平均值，計算獲取的臨時平均序列與下一條時間序列的平均值，直到遍歷完整個集合為止[19]。PSA（prioritized shape averaging）算法[20]在此基礎上進行優化，結合層次聚類的思想，在序列進行成對平均之前根據序列的形狀相似性進行排序，從相似度最高的序列開始計算平均值，這樣能夠改善隨機選擇序列所帶來的負面影響。然而，局部平均策略導致每次迭代所獲取的平均序列長度變長，不利于后續分析。為此，Petitjean等人[21]提出了DBA算法，以一種全局平均的策略計算集合的平均序列。從隨機選擇的初始平均序列開始，對臨時平均序列進行迭代優化，以最小化差異距離。

DBA是一種迭代算法，能夠對目標集中的平均序列進行調整。其中每次迭代都遵循期望最大化方案，涉及兩個階段：（1）隨機選擇一條時間序列作為初始序列，計算該序列與目標集中每個單獨序列之間的DTW距離，從而找到初始序列上時間點與其他序列上時間點之間的關聯；（2）將初始序列上的每個時間點與其關聯的時間點分為一組，并計算平均值，將其結果更新為初始序列。重復此過程，直到達到收斂或最大迭代次數為止。

3 時間序列挖掘與聚類

3.1 EBA-DBA：改進的DBA

實驗已經表明DBA算法是迄今為止性能最好的方法，但DBA算法仍然存在一些缺點：（1）異常序列對其性能影響較大；（2）所得平均序列的長度取決于初始序列的長度，其性能對初始化高度敏感。針對以上兩個問題，本文提出了相應的解決方案。

首先是去除異常序列，在一定程度上保證時間序列的一致性，提高DBA算法的性能。為了刪除明顯的異常值，使用Grubbs’Test進行最值檢測。Grubbs’Test是一種從樣本數據中檢測異常值的方法，通常用于檢測服從近似正態分布的單變量數據中的最值。其核心思想是將最值作為可疑值計算與均值的絕對偏差，判斷是否大于臨界值。若大于臨界值，則認定這個可疑值為異常數據；否則為正常數據。臨界值可以從Grubbs提出的表中查詢獲得。詳見算法1。

算法1異常值刪除

輸入：時間序列集合S={S1,S2,…,SK},數量K,臨界值Gn。

輸出：去除異常值后的集合S′={S1′,S2′,…,SK′}。

1.begin

2.aveDTWdist←new List

3.for S∈S do

4. temp=averageDTW(S,S)

5. aveDTWdist.append(temp)

6.end for

7.for i in range(K)do

8. (Distmax,index)=MAX(aveDTWdist)

9. Distmin=MIN(aveDTWdist)

10. μ=AVERAGE(aveDTWdist)

11.σ=STDEVP(aveDTWdist)

12.G=(Distmax-μ)/σ←suspicious value

13. ifG＞Gn

14. S.remove(index)

15. else

16. break

17. end if

18.end for

19.end

接著獲取初始序列，不同于DBA算法隨機地選擇初始序列，本文從目標集序列中創建一條歐式重心的平均序列，作為DBA算法的初始序列。具體如下：

（1）對所有目標序列集求平均長度：

其中，K表示目標集中序列的數量，Nk表示第k條時間序列的長度。

（2）計算目標集中每一條時間序列與剩余序列之間的DTW距離矩陣。選取一條參考序列A0，使其與所有其他序列之間的DTW距離之和最小，即：

其中，S={S1,S2,…,SK}為序列集合。

（3）對目標集中的序列進行重采樣，對齊A0與Sj，并利用它們的DTW翹曲路徑定義縮放系數：

并依據縮放系數對序列進行拉伸或壓縮，使得所有序列長度變為集合的平均長度。

若A0與Sj上的時間點一一對應，則這兩條序列匹配，λj=0。若A0上一個時間點與Sj上α個時間點對齊，則λj=α-1，需要對Sj壓縮操作。若A0上β個時間點與Sj上的一個時間點對齊，則λj=1-β，需要對Sj拉伸操作。圖2展示了兩個序列之間的縮放系數，sN j是Sj時間序列上的時間點，N表示時間序列上時間點數量。對于重采樣操作，若Sj的長度大于L，則在λj最大值處刪除一個時間點，更新λj，重復操作直到Sj長度等于L為止；若Sj的長度小于L，則在λj最小值處，相鄰的兩個時間點sx j與sx+1j處插入一個時間點

；更新λj，重復操作直到Sj長度等于L為止；若Sj的長度等于L，則無需進行操作。

（4）生成一個基于歐式重心平均的序列，將重采樣序列中時間點的關聯集取均值。對目標集中的序列采用歐式距離一一對齊，計算每個時間點的平均值作為輸入DBA算法的初始序列。將該初始序列在原始目標集中計算平均序列。

上述對DBA算法的改進過程，本文命名為EBA-DBA算法，其流程圖見圖3。

3.2 距離密度聚類

DDC是一種時間序列的確定性聚類方法，是距離聚類和密度距離相結合的擴展，特別適用于時間序列數據[22]。本文采用DDC聚類算法進行距離密度聚類。

DDC是一個分裂的聚類過程，每次迭代都會引入一個新的聚類種子。該方法首先構建DTW距離矩陣，選取距離其他實例最遠或最近的時間序列作為初始聚類的種子。選取最遠的時間序列作為初始聚類的種子是受到k-means++算法的啟發，表明此算法從稀疏區域開始初始化，可以提高聚類的質量和速度。接著利用每個時間序列到簇中心的距離，模擬時間序列數據的密度。當各時間序列與聚類種子之間的DTW距離進行排序后，距離增加最大處，即為時間序列組中的稀疏區域，在此處進行分裂。為了更好地表示時間序列聚類，采用了改進DBA算法求出每個聚類的平均序列，并用聚類中與其平均序列最相似的序列來作為新的聚類種子。在獲得新的聚類種子后，利用每個時間序列到聚類中心的DTW距離來重新平衡聚類。整個過程將不斷重復，直到收斂或達到用戶定義的最大迭代量為止。詳細見算法2。

算法2距離密度聚類

輸入：時間序列集合S={S1,S2,…,Sn}，聚類種子Ck-1={c1,c2,…,ck-1}，種子數量k，不相同的聚類標簽Lk。

輸出：更新后的聚類種子C′k-1={c′1,c′2,…,c′k-1},對應時間序列的聚類標簽Ln={l(e)|=1,2,…,n}。

1.begin

2.forl∈Lk-1do

3.Lk-1←Cluster(Ck-1)

4.arr=[1,2,…,k-1]=DTWSort(Lk-1)←calculate

5. DTW and sort in the cluster

6.dist[i]←max(arr[2]-arr[1],…,arr[k-1]-arr[k-2])

7. ifarr[n]-arr[n-1]==max(dist[i])then

8.location[i]=n

9. end if

10.end for

11.ifi==max(dist[1,2,…,k-1])then

12.l(i1,i2)←l(i),(ci1,ci2)←ci←split new

13. cluster seeds

14.end if

15.Ln={1,2,…,i1,i2,…,n}←Ck={(c1,c2,…,ci1,ci2,…,ck-1)}

16.forS∈S do

17. (c1′,c2′,…,ck′)←DBA(c1,c2,…,ci1,ci2,…,ck-1)

18. UpdateClusterDBA(Ck)

19.end for

20.end

4 實驗

本文通過改進DBA算法，并將其應用在眼動模式挖掘和聚類分析上，挖掘群體的眼動模式和不同的閱讀策略。實驗流程見圖4。

4.1 實驗數據集

本文采用Netzel等人[23]提供的眼動追蹤數據集和本地采集的眼動追蹤數據集進行實驗。前者是20名參與者在公共交通地圖中查找路線時的眼動數據；后者是15名計算機專業研究生在學習“網易云課堂”平臺上“機器學習”課程中的眼動數據。本文的目標不是要打破刺激的數量和參與者的界限，相反，是以一組受控的刺激和任務組合為目標進行基準測試。“公共交通地圖”數據集提供靜態視覺刺激，探索參與者在任務導向情況下的掃描路徑共性和差異性。在任務導向的靜態視覺刺激下，參與者注視點的起始位置相同，而掃描路徑卻不盡相同，這與個體的潛在認知過程相關。而本地采集的數據提供的是動態視覺刺激，在注意力集中的情況下，參與者的注視點會跟隨視覺刺激的變化而改變。由于動態視覺刺激的特性，參與者的眼球運動是趨于一致的。因此，在這個數據集上對掃描路徑進行聚類，能夠分離離群值，對參與者的學習狀態進行評估。表1對上述兩個數據集的特性做了詳細對比。

表1 兩個數據集對比Table 1 Comparison of two datasets

4.2 眼動模式挖掘

4.2.1 Grubbs’Test有效性

DBA算法是一種全局的平均策略。如果時間序列集合中存在異常值，那么將會對算法性能造成一定的負面影響。本文采用Grubbs’Test檢測時間序列集合中的最值，并刪除偏離均值程度異常的最值。在兩個數據集上，比較了使用Grubbs’Test檢測并刪除異常值前后的DBA算法性能。圖5顯示了兩個數據集上的平均DTW距離。平均DTW距離用來表示DBA平均序列與實際數據之間的形狀和差異。平均DTW距離越小，性能越好，相似度越高。通過圖5可以看出，刪除異常值后，任意選擇一條時間序列初始化，DBA算法性能都有了明顯提高。因此，證明了異常序列對DBA算法具有較大的負面影響。而本文采用Grubbs’Test去除異常序列能夠在一定程度上保證時間序列的一致性，提高DBA算法的性能。

4.2.2 EBA-DBA算法性能

DBA算法主要目的是從時間序列集合中隨機選取一條序列作為模板，與其他序列進行DTW計算；對模板上逐個時間點匹配關聯的時間點，并進行加權平均計算。因此，初始序列的選取對算法的性能至關重要。本文定義了一個伸縮系數，并據此對時間序列集合進行重采樣，最后從重采樣的集合中計算歐式重心平均的序列作為DBA算法的初始序列。這種方法只需對時間序列集合進行簡單的插值或刪除操作，沒有增加太多的計算量。表2比較了DBA算法和EBA-DBA算法的性能。從表中可以看出，DBA算法對初始序列的選取高度敏感。對于最好的結果和最壞結果之間平均DTW相差1 721。而本文對DBA算法進行改進，效果比DBA算法最好情況下的效果更優。因此，本文提出的方法能夠在不增加計算復雜度的同時，提高算法性能。本文還通過圖6比較了在兩個數據集上DBA算法和EBA-DBA算法的收斂精度和速度。EBA-DBA算法不論是收斂精度，還是速度上，都高于DBA算法。

表2 EBA-DBA和DBA性能對比Table 2 Performance comparison of EBA-DBA and DBA

4.2.3 不同眼動模式挖掘方法對比

眼動模式可以作為掃描路徑預測和分類的研究基礎，為有關心理學研究提供群體行為的有用知識。在之前的研究中，把最長公共子序列（eMINE）[10]、掃描路徑趨勢（STA）[9]或相似度最高的實際掃描路徑（NW）[11]作為群體的眼動模式。將本文方法（EBA-DBA）與這些方法進行實驗對比，如圖7所示。

由圖7可以看出，DBA算法性能明顯優于eMINE、STA和NW算法。DBA算法的初始序列是隨機選擇的，以迭代的方式達到最優。而EBA-DBA算法的平均DTW距離低于DBA算法，性能更好。這是因為與DBA算法相比，EBA-DBA算法剔除了離群值，有效地對原始序列進行平均，在保留掃描路徑內部可變性的同時提供更加平滑的對齊方式。

本文還采用Needleman-Wunsch算法[24]計算群體的實際掃描路徑與眼動模式間的相似度得分，并進行歸一化，即計算：

其中，scoreNW是Needleman-Wunsch算法計算的相似度得分，lenmax是成對掃描路徑中較長掃描路徑的長度。Needleman-Wunsch算法被認為是一個有意義的度量，在生物信息學中通常通過此算法找到DNA序列的同源信息。從表3中可以看出，本文方法提取的眼動模式與實際掃描路徑之間差異最小，更能代表整個群體的眼動行為。

表3 平均NW得分Table 3 Average NW score

4.3 聚類分析

眼動模式的聚類可以分析人們不同的閱讀行為，并能夠客觀地評估其潛在的認知過程。本文比較了DDC、k-means和Hierarchical三種算法的性能。采用EBA-DBA算法計算聚類的平均序列來確定聚類的質心。由于DDC算法在“公共交通地圖”數據集上聚類個數為6的時候達到收斂，不再分裂新的聚類，因此對聚類個數為6和7時的各種方法性能進行對比，使用DBI（Davies-Bouldin index）來評估聚類性能，DBI值越低，集群的分離和集群內部的“緊密性”越好。從表4中可以看出，當聚類個數為6時，三種聚類算法都達到收斂，DBI值最低，證明了DDC算法的收斂是可行的。而DDC聚類算法比k-means和Hierarchical性能更好，DBI值達到最低值1.441。

表4 不同算法的DBI值Table 4 DBI values of different algorithms

在本地采集的數據集中，DDC與k-means算法性能較為接近，高于Hierarchical。但是，k-means是隨機選擇初始聚類種子，聚類的質量會發生波動。相比之下，DDC是一種確定性的聚類算法，結果是可重現的。同時DDC算法從密度稀疏開始初始化，能夠提高聚類質量和速度。因此本文選取DDC聚類算法，能高效分離異常掃描路徑聚類，達到更好的效果。

5 討論與應用

根據聚類結果能簡單地對學習者的學習狀態進行評估。對于包含動態視覺刺激的數據集，不僅能夠挖掘不同的閱讀策略，更能為評估學習者學習狀態提供參考。在動態視覺刺激下，學習者的掃描路徑是趨于一致的，表明學習者注意力集中，注視跟隨課程內容改變而變化。本文通過聚類的方法分離離群值，識別多類不同的眼動模式。將聚類個數作為判斷依據：當聚類個數為1～2時，學生的學習狀態為專注；當聚類數為3～4時，則表示走神，部分人注意力不集中；當聚類數大于或等于5時，則表示信息迷航，注意力極度分散，無法找到課程重點。表4所示，在本文采集的數據集中，聚類個數為2時達到收斂，DBI值為0.141，達到最小。因此，評估該群體的學習狀態為專注。

6 結束語

本文針對掃描路徑進行分析，探索學習者眼動行為的共性和差異性。研究了在同一任務情況下學習者掃描路徑的時間序列表示和聚類。對DBA算法進行改進以獲取群體眼動模式，并結合DDC算法對掃描路徑進行聚類。應用在智能教育領域，評估學習者的學習狀態。實驗結果表明，基于時間序列的眼動模式挖掘能夠提取群體觀看模式，并根據聚類評估學習狀態。