1.2 国内外研究现状

1.2.1 推荐在工作流系统中的应用

遵照工作流领域[11]的术语规范，本书将模型中某项业务的最小逻辑执行单元称为任务（Task）；将某项正在运行的业务中已经执行过的任务、满足条件可以执行的任务、当前正在执行的任务统称为活动（activity）。这些内容将在第2章中详细讲解。

为更好地描述各种不同类型的推荐工作，本书总结出了各种不同的推荐类型（recommendation type，RecType），参见表1-2。推荐不是凭空进行的，必须依据一定量的历史信息，这些信息可以是大量的执行过的工作流实例，也可以是建模人员积累的大量模型信息，表1-2中第1列指出了推荐类型所依据的是何种信息。推荐可以是对当前不完整的工作流实例进行的下一项可能执行活动的推荐，也可以是对当前建模模型的下一个可能的Task的推荐。表1-2中第2列指出了推荐类型做的是何种推荐，第3列内容为对各种推荐类型进行标记。

表1-2 推荐应用于工作流系统中的各种类型

一个WfMS经过一段时间的运行，会积累一定数量的工作流模型，这些模型既包含当前正在使用的，也包含过去曾经使用但现在不再使用的模型，它们共同构成了工作流模型库。当模型设计者在设计一个新模型时，可将当前不完整模型与模型库中模型进行相似性匹配，向模型设计者推荐其可能建模的下一个Task，从而辅助模型设计者快速地建模。

Agnes Koschmider等人[52]利用元数据信息筛选出与当前模型块相似的业务模型或业务模型块，供模型设计者选用。他们方法的推荐粒度比较大，不完全是一次推荐一个活动，推荐出的可能是Task或Task组合，其推荐类型为RecType Ⅲ，以辅助业务模型建模。文献[51, 53]先利用图挖掘的方法从模型库中找出子图在整个库中出现的频率，从而建立一个模式表；然后用最小DFS（depth-first search，深度优先搜索）编码[54]将模式表中图结构表示的模型转化成字符串，接着用字符串匹配的方法向当前不完整模型推荐其下一个可能的Task，辅助模型设计者建模。这种仍然是模型级别上的推荐，推荐类型为RecType Ⅲ。

在面向服务的计算（service oriented computing）领域，Web服务的发现及组合优化可以看作是工作流模型的构建；每个具体的Web服务确定后，就构成了一个由多个Web服务组成的Web应用，Web应用的每次具体执行可看作是工作流实例在执行。Web应用是工作流系统的特例，其中的活动自动化程度较高， 几乎不需人工干预。在构造Web应用时，要得到更好的Web服务，以达到更优的Web组合和应用，就需要使用推荐技术。

文献[55]将语义信息加入到Web服务的描述中，利用语义匹配的方法找出与当前用户需求相符合的Web服务——候选Web服务列表；用户选择符合的Web服务后，还要求用户对该服务打分；有了打分数据后就形成了用户对Web服务的打分矩阵，在后来的推荐中使用基于物品的协同过滤算法（item-based collaborative filtering）[56]向用户推荐Web服务。该方法没有考虑Web服务间的执行顺序信息，仅仅是在局部情景下对用户当前的需求做出反应。本书的推荐方法考虑了活动间的执行顺序信息，未考虑活动名称间的语义匹配信息，但这可能成为我们未来的工作方向。本书第5章介绍的协同过滤所基于的打分矩阵与文献[55]中的产生过程不同，是根据用户执行过的实例活动序列信息与库中其他实例的序列信息进行比较分析自动生成的，反映的是用户对一个完整实例的偏好程度，而不是对一个活动的偏好程度。另外一区别在于，文献[55]推荐时所依据的语义描述是预先确定的，而本书第5章的推荐方法依据的实例库是事先不确定的。

文献[50]提出的推荐方法，其应用场景是服务组合领域[57]。该文献讨论了如何更好地利用历史服务组合例子来帮助构建当前的服务组合，利用离线创建的模式表向当前不完整的服务组合推荐下一个较合适的服务，是服务组合模型级别上的推荐，其推荐类型为RecType Ⅲ。抛开上述应用场景，该推荐方法同样可以应用于本书的推荐场景——RecType I。因为该文献中的实例库的实例既不包含角色信息，也不包含用户信息，所以在本书第4章中，我们将与文献[50]的推荐方法通过实验对比进行分析。

科学工作流系统[58-60]领域讨论了如何根据工作流执行实例库向用户推荐和帮助用户发现他们需要的、有用的工作流组件（workflow component）。此方法的缺点是，某个工作流组件的推荐是根据上游直接相邻的一个结点，例如，如果a和b具有很强的相关性，即a→b，那么当执行a后，b就会被向用户推荐。当不直接相邻的上游结点存在强相关性时，这个推荐方法的结果就不准确。David Koop等人[61]提出了一种更复杂的方法，先利用实例库信息确定所有可能的线性不间断活动序列，为每个序列计算置信分（confidence score），向当前不完整的实例ě推荐时，从ě中找出置信分最大的那个序列，以其为基准向ě推荐其下一项可能的活动。该方法的缺点是当间断的序列对下一项活动具有较强的影响时，推荐的结果就不太准确。

与本书相似，文献[62]的推荐类型为RecType I，它采用历史工作流实例信息对不完整实例进行下一项可能的活动推荐，它采用三种不同的方法筛选与不完整实例相似的完整实例：前缀法、集合法和多重集合法。前缀法仅仅考虑不完整实例的最后一项活动，完整实例在对应索引位置上的活动与该活动完全匹配才被筛选出来，这个要求太苛刻且没有考虑该活动之前的活动信息；集合法和多重集合法则完全忽略了活动的顺序信息。为克服这个方法的不足，本书第4章介绍的算法不仅考虑了不完整实例的最后一项活动，也考虑了该活动之前的活动信息，同时也考虑了这些活动的顺序信息。

1.2.2 协同过滤

推荐系统是用来向当前用户（active user）推荐其感兴趣的商品或服务的程序或应用系统。从20世纪90年代初开始研究它以来，诞生了各种各样的推荐算法。值得一提的是，在2006年，Netflix为改善自己的推荐系统性能，以高额的奖金为举办了一个推荐系统大赛之后，推荐系统和推荐算法的研究蓬勃发展，出现了各种各样的系统优化和改进。从推荐系统的发展历程来看，协同过滤（collaborative filtering，CF）是使用最为广泛、研究最为深入的推荐方法，并在学术和工业界得到了成功应用。CF考虑了用户间的爱好关系，将与当前用户具有相似兴趣的用户所感兴趣的项推荐给当前用户。

David Goldberg等人于1992年首次提出CF这一术语，并利用CF技术对信息进行过滤。他们设计了系统Tapestry用于过滤和筛选出当前用户感兴趣的电子邮件，是第一个使用CF技术的系统。每个用户需对他们已读过的邮件进行标注（annotation），这些标注对其他使用系统的用户可见，通过这些已有的标注， 当前用户可以构造出过滤查询语句，从而得到其真正需要和感兴趣阅读的邮件。Tapestry使用的CF不是自动的，需要用户基于预先设计的查询语言构造复杂的查询语句。

GroupLens是第一个自动化CF系统，使用了基于用户近邻的（user-based，neighborhood-based）推荐算法。GroupLens向用户推荐他们可能喜欢的文章。它的新闻阅读客户端（news reader clients）能够显示当前用户对未阅读文章的预测评分，也能够接收用户对已阅读文章的评分。最初的GroupLens系统采用Pearson相关系数度量用户间的相似性，并用所有近邻用户评分与其各自平均评分的差的加权平均作为最终的评分预测。为保护隐私，用户评分时使用假名，这样并不影响评分预测效果。Konstan等人讨论了实现GroupLens协同过滤系统面临的挑战、GroupLens的运作机制、评分预测方法、用户兴趣的分布等， 指出个性化推荐要好于非个性化推荐。

上述基于用户近邻的CF算法的计算量随着用户数的增加而增加，当用户的数量远远大于项的数量时，例如，商务网站Amazon的用户数量就远大于待销售的书籍的数量，基于用户近邻的CF算法所需的计算量就特别巨大，不能满足商务网站推荐的实时性要求。为克服上述缺点，使得推荐系统能在很短的时间内推荐出高质量的结果，基于项近邻的（item-based, neighborhood-based）CF推荐算法被设计出来并得以运用[56]。与基于用户近邻的CF算法类似，基于项近邻的CF算法首先计算项间的相似性，然后向当前用户推荐与他喜欢项相似的项。由于项间的关系相对稳定，所以基于项近邻的CF算法在保持与基于用户近邻CF算法相同推荐效果下能够使用较少的在线计算时间。

当数据比较稀疏时，CF算法既无法找出当前用户的近邻用户，也无法找出某些项的近邻项，因此，其推荐效果就受到影响。例如，如果没有用户对新加入的项评分，那么这个项就无法被推荐。为了使基于CF的推荐系统运作良好，必须有一定数量的用户对项进行评分。为解决数据的稀疏问题，Sarwar等人使用了一些专门设计的智能体自动地填充一些数值，从而方便CF算法的执行。这些智能体是一些自动打分的机器人，本身携带非协同过滤信息（基于内容的信息）对新加入的项进行评分，以此来解决数据的稀疏性问题。此外，数据稀疏还会造成两个用户共同评分的项比较少，这对采用Pearson相关系数计算用户间相似性的算法带来不利影响，解决办法是使用默认评分（default voting）。