通过基于语法的方法为交互序列建模并进行数据探索中的推荐(A Grammar-based Approach for Modeling User Interactions and Generating Suggestions During the Data Exploration Process)

在可视化系统中,往往会有很多交互功能。丰富的交互功能一方面使得用户能够灵活地探索数据的不同方面,另一方面却也容易让用户信息过载,不知道使用哪些交互能够高效地完成数据探索的任务。为了解决这个问题,帮助用户沿着正确的交互探索路径使用可视化系统,作者提出将过往的多个用户的探索序列合成一个有限状态自动机,推荐用户采取能够高效地达到解决方案的状态转移对应的交互。得到的自动机不仅能够用来产生推荐,而且可以用来理解用户的交互方式。

在介绍这个工作的整体流程前,首先,让我们通过例子来看一下这篇工作中关心的交互序列是怎样的。一个示例可视化系统如下,这个系统中用户可以进行的交互包括点击左侧的checkbox,点击左上角的按钮,在平行坐标的某个轴上brush,在下侧的方框中填入用户需要完成的task的答案。那么在完成一个task过程中,从开始到填入答案完成task,一个可能的交互序列的例子如下:点击Bathroom的Checkbox、刷选Year轴、点击Region按钮、点击South Region的Checkbox、输入答案。

yuzhang_20161217_1

图1. 最终实现的带推荐机制的一个可视化系统

 

这项工作中为一个可视化系统实现推荐功能的整体流程如下:第1步,需要找出可视化系统中所有的交互参数;第2步,找若干个用户使用这个可视化系统,给出探索任务以后,收集他们解决任务的交互序列;第3步,用这些交互序列生成一个自动机,并且将各种元数据和统计量标记在状态和路径上;第4步,通过这个自动机,推荐用户进行能够高效解决探索任务的交互。

下面主要说明上面的第3步和第4步具体怎么做,也就是怎么训练出自动机,以及怎么用自动机进行推荐。

自动机的训练过程主要是利用K-Reversible算法进行状态合并。K-Reversible算法的流程如下。假设有下图两个状态机,我们检查状态p和状态q是否需要合并时,则检查状态q之前的长为K+1的路径,以及状态p之前的长为K+1的路径是否相同。比如取K=2时,q对应的路径是cba,p对应的路径是cda,两者不相同,所以p和q不要合并。如果取K=0,q对应的路径是a,p对应的路径是a,两者相同,所以p和q要合并。K越小,能合并的状态越多,实际实现中使用了K=0,即最为激进的合并方法。

yuzhang_20161217_2

图2. 两个状态机,考虑是否需要合并状态p和状态q

 

有两个交互序列:click Bathroom, brush Year, click Region, click South, type Answer与click Bathroom, click Region, click South, brush Year, type Answer。那么通过这两个交互序列用K=0的K-Reversible算法合成的自动机如下。

yuzhang_20161217_3

图3. 合成出来的自动机

 

在K-Reversible算法的基础上,实现中还有2处调整。

首先,算法中会尝试对调操作的先后顺序以后能否进行状态合并,如果可以的话就进行交换然后合并。这里做了一个假设:两个交互操作先后顺序交换,交互以后可视化系统到达的状态仍然是相同的。这个假设在多数情况是正确的。

另外,考虑到2个相同类型的交互的结果未必是相同的。比如同样是刷选平行坐标的Year轴,刷选轴的上面一半、刷选上面三分之二、刷选下面一半,高亮给用户的结果是不同的,可能导致用户下一步的操作也是不同的。因此就需要对这些相同类型,但是描述的元数据不同的交互进行区分。具体实现中,通过加上了贝叶斯准则帮助选取k的Kmeans,对元数据进行聚类,从而将一类交互划分成不同的各种子类型。

介绍完了自动机怎么训练,接着介绍怎么用自动机进行推荐。

一方面,推荐的时机是由自动机决定的,在4种情况下会给出推荐。不妨设用户一开始处在状态A,交互以后处在状态B。第1种情况,状态B是一个“坏”状态,即状态B需要经过状态A才能到达End状态,此时也可以认为是用户进行了无用的交互,这时需要给出推荐。第2种情况,若用户交互的反应时接近于那些从状态A到达了一个“坏”状态的用户的反应时,则给出推荐。第3种情况,在用户交互过程中有一定概率随机出现推荐。第4种情况,当用户的反应时比绝大多数其他用户的反应时更长时,给出推荐。

另一方面,推荐的内容也由自动机决定。用户会被推荐使用当前状态下概率最大的状态转移路径对应的交互。

最后,作者还对这种方法进行了实验评估。被试需要使用可视化系统完成12个不同的任务。实验中的自变量是用于进行推荐的自动机的生成使用了多少了训练样本,这个自变量一共有4个水平:0,50,100,200。其中0即没有使用训练样本生成自动机,也即不给出推荐。因变量是用户完成每个任务的准确率、耗时、对自己答案的确信度、交互次数。

实验结果发现,有没有推荐机制对于用户的准确率、耗时、确信度都没有显著影响,只有交互次数在有了推荐以后显著降低了。此外,还发现了用户按照推荐的进行交互的概率只有23.16%,虽然显著高于随机交互的概率,但是仍然很低。并且,从第3个推荐开始,有不小比例的用户拒绝推荐。

总的来说,这篇工作提出了一种基于自动机的交互推荐机制,给出了自动机的训练算法,并对这个推荐机制进行了评估。但是评估结果不太理想,根据用户反馈意见,后续还需要进一步研究如何找到合适的推荐时机。

 

Reference

[1] F. Dabek and J. J. Caban, “A Grammar-based Approach for Modeling User Interactions and Generating Suggestions During the Data Exploration Process,” in IEEE Transactions on Visualization and Computer Graphics, vol. 23, no. 1, pp. 41-50, Jan. 2017.

评论关闭。