改进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算法对扫描路径进行聚类。应用在智能教育领域，评估学习者的学习状态。实验结果表明，基于时间序列的眼动模式挖掘能够提取群体观看模式，并根据聚类评估学习状态。