信息回忆检索方法

摘要

本发明公开了一种信息回忆检索方法，包括以下步骤：S1：接收包含情境实例的查询请求；S2：以至少包含一个情境实例的情境记忆作为查询对象，与用户提交的查询请求中的情境实例进行匹配，得到满足查询条件的一组情境实例；S3：依据所述一组情境实例和查询请求中的情境实例的相似度对所述一组情境实例进行排序；S4：得到经过排序的一组情境实例后，根据所述一组情境实例和各自的信息内容的映射关系，将具体的信息内容返回给用户。本发明实现了对曾经访问过的信息更准确、快速地检索。

说明书

技术领域

本发明涉及数据管理技术领域，特别涉及一种信息回忆检索。

背景技术

在日常生活中，重新查找曾经看过或使用过的信息是一种很普遍 的行为。信息的重新查找不同于信息的查找，后者由于用户没有掌握 充足的资讯存在了不确定性，而前者则是一个很直接的过程，因为用 户曾经看过该信息。支持信息的回忆检索的一般方法是维护用户的信 息使用记录，例如根据用户回忆的频率来记录用户曾看过的信息，如 1小时前，一天前，一个月前，等等。随着时间的流逝，用户的历史 记录会急剧增加，在这种情况下，用户一般更偏好于搜索而非浏览全 部历史记录。但是，由于记忆的退化及模糊性，用户在重新检索信息 时，有时候会不可避免地遇到困难，因为记错或忘记，通过简单地输 入一些关键字来搜索想要的消息将是一件很耗时的事情。

心理学研究表明，在回忆信息的时候，与信息相关联的情境(如 时间、地点和活动等)可作为一种极有用的回忆线索，因为它们通常 会比具体的信息内容更容易记住。例如，“查找去年去非洲旅行时在 酒店里看到的菜谱”，一般地，用户很难记起菜谱的详细内容，但是 会比较容易记住与之关联的情境信息，如时间(“去年”)，地点(“酒 店”)和活动(“在非洲旅行”)，等等。在人脑中有一种记忆叫做情节 记忆，它存储有关时序的情节或事件，以及事件之间的时空关系，并 且通常会将事件与已知的一些事实或知识关联起来。情节记忆能够使 用户重新体验过去发生的事情，它根据用户回忆起来的一个或几个情 境线索而把整体的情节回忆起来。

目前，在网页搜索及个人信息管理领域关于信息的回忆检索这个 课题已经有了很多的研究工作，它们主要基于浏览和搜索两个方法来 实现信息的重新获取。

在网页搜索领域，有一些比较典型的方法和工具来辅助用户重新 查找网页，比如回退按钮，浏览器的书签，历史列表，以及搜索引擎， 等等。以Google的“Web History”为例，Google的搜索引擎会记录 注册用户的网页活动数据，如搜索请求和点击的网页等，然后将它们 分类为不同的主题，如网页、图像、新闻或博客等等。基于此，Google 可以让用户在选定一个日期或在不同的时间段(如最新、比较新、比 较旧和最旧等)来浏览过去访问过的网页。此外，Google还可以让 用户在全部历史或不同主题之下通过输入一些关键字(如网页标题和 网页内容的关键字等)来搜索曾经访问过的网页。利用Google Web  History来回忆检索曾经看过的信息，只能针对用户在Google上的历 史记录，并且用户需要提供一些具体内容的关键字信息来进行回忆检 索，而没有很好的利用情境信息。微软的研究者开发了一个工具叫 “SearchBar”，把用户的网页访问历史组织成一个层次结构，涵盖了 用户最近的搜索主题、搜索的关键字、访问的结果，以及用户在主题 上所做的标记内容等。通过浏览这个层次结构，用户可以获取之前的 搜索信息(如搜索的关键字、访问的结果，及其标记的内容等)。这 种方法需要用户付出额外的代价来组织和维护其所访问网页的历史， 且只能以浏览的方式来查看，不提供基于情境信息来进行回忆检索。 美国麻省理工学院的研究者构建了一种搜索引擎“Re：Search  Engine”，不但可以搜索新信息，还可以支持重新搜索旧的信息。该 搜索引擎对用户过去的查询请求建立了索引，以识别重复的搜索，而 用户最近浏览过的网页则被保存在一个结果缓存里。为了决定在访问 过的结果里哪些内容最有可能被用户记住，该搜索引擎维护了用户的 交互记录缓存。在合并新旧内容时，该搜索引擎使用了关于新内容增 益值和旧内容记忆值的一个测度函数来决定最后的网页排序。该搜索 引擎基于具体内容的关键字来检索新旧内容，同样不提供利用情境信 息来进行回忆检索。

在个人信息管理领域，为了支持信息的回忆检索，一些研究工作 把信息内容以外的访问情境信息考虑进来。微软的研究者开发了一个 系统叫做“Stuff I’ve Seen”，以支持个人信息的重新检索。该系统为 用户曾经看过或使用过的信息(如电子邮件、文件和网页等等)建立 了索引，并且使用了一些线索如文件类型、访问的日期和作者信息等 来对搜索的结果进行筛选和排序。该系统虽然利用了一些情境线索来 辅助筛选个人信息，但是这些情境信息仅限于几种类型，而且没有对 情境信息进行有效的管理和利用，不具一般性。EMC中国研发中心 和复旦大学合作开发了一个叫做“iMecho”的桌面搜索系统，把文件 之间的关联关系考虑进来，以加强基于关键字的全文搜索。该系统从 内容上如文件之间的相似关系和用户的操作上如从一个网页跳到另 一个网页及文件复制等来挖掘关联关系。在该系统下，用户首先通过 输入关键字来搜索，然后根据文件之间的关联图来导航到目标文件。 “iMecho”系统仅通过挖掘文件内部之间某些特定的关联关系来辅助 查找文件，并且其查询条件仍为全文的某些关键字，而没有利用文件 以外更加丰富的情境信息来进行有效的回忆检索。

发明内容

(一)要解决的技术问题

本发明要解决的技术问题是：如何对曾经访问过的信息实现更准 确、快速地检索。

(二)技术方案

为解决上述技术问题，本发明提供了一种信息回忆检索方法，包 括以下步骤：

S1：接收包含情境实例的查询请求；

S2：以至少包含一个情境实例的情境记忆作为查询对象，与用户 提交的查询请求中的情境实例进行匹配，得到满足查询条件的一组情 境实例；

S3：依据所述一组情境实例和查询请求中的情境实例的相似度对 所述一组情境实例进行排序；

S4：得到经过排序的一组情境实例后，根据所述一组情境实例和 各自的信息内容的映射关系，将具体的信息内容返回给用户。

其中，所述情境记忆为确定型有穷自动机(P，∑，η，p₀，p_f)表示， 其中P是一组情境记忆快照的集合；∑是一组事件的集合，包括时间 事件和用户以情境实例作为查询条件的回忆检索事件；η是一组演化 函数P×∑→P的集合，满足于转化η(p_i，e_k)＝p_i+1，p_i＜_P p_i+1；p₀∈P是 初始情境记忆快照；p_f∈P是终止情境记忆快照，包含空值

所述情境记忆快照表示为图CM＝(V_CC，E_CC)，其中节点V_CC是一组 情境实例的聚簇的集合，边E_CC是在情境实例之间的关联关系；

所述情境实例是访问情境的实例，访问情境包含了n维情境属性 (A₁，A₂，...，A_n)，每一维情境属性的定义域构成了一个不同抽象级别 的排序的层次结构，情境属性A_i的层次结构为一个偏序关系格(H， ＜_h)，其中H＝(h₁，h₂，...，h_L-1，ALL)共有L个层次，对应到的层次标 识为(1，2，...，L-1，L)，＜_h是H中层次级别之间的偏序关系，对任 意的1＜i＜L满足h₁＜_h h_i＜_h ALL，在H中的两个连续的层次h_i和 h_i+1之间的相似度为s_i，i+1，0≤s_i，i+1≤1；

所述情境实例表示为n元组C＝(c₁，c₂，...，c_n)，其中对于任意的1 ≤i≤n，c_i∈Dom(A_i)；

给定两个情境属性值c_i，c_i′∈Dom(A_i)，k为c_i在A_i的偏序关系的层 级值，k′为c_i′在A_i的偏序关系的层级值，c_i和c_i′之间的相似度，记为sim(A_i， c_i，c_i′)，定义如下：

(1)如果c_i＝c_i′，则sim(A_i，c_i，c_i′)＝1；

(2)如果c_i′＜_ac_i，则$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })={\Pi }_{l=k^{\prime }}^{k-1}{s}_{l,l+1},$c_i′＜_ac_i表示c_i为c_i′ 的父亲；

(3)如果c_i＜_ac_i′，则$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })={\Pi }_{l=k}^{k^{\prime }-1}{s}_{l,l+1};$

(4)如果c_i和c_i′位于相同的层级而且有共同的父亲c_p，令n_p为c_p的孩子数目，n_c和n_c′为c_i和c_i′在c_p的所有孩子中的排序值，则

$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })=s_{k,k+1}^2+(1-\frac{|n_c-n_{c^{\prime }}|}{n_p-1})·s_{k,k+1}·(1-s_{k,k+1})$

(5)如果c_i和c_i′位于两个不同的层次级别并且它们的共同祖先为 c_p，令m＝h(A_i，c_p)，则

$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })=\underset{l=k}{\overset{m-1}{\Pi }}{s}_{l,l+1}·\underset{j=k^{\prime }}{\overset{m-1}{\Pi }}{s}_{j,j+1}$

给定两个情境实例C＝(c₁，c₂，...，c_n)和C′＝(c’₁，c’₂，...，c’_n)，它们的相似度计 算如下：

$\mathrm{Sim}(C,C^{\prime })=\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sim}}^2(A_i,c_i,c_i^{,})}.$

其中，所述情境记忆中的情境属性的保持度随时间t逐渐衰退，采 用修正的指数-幂函数R(A_i，c_i，t)来表示情境属性值c_i在访问事件发生t时 间后的保持度变化；采用实数值b∈[0，1]来表示一个情境属性值的保持 度；

其中，b₀是保持度的初始值，λ是退化速度系数，θ_max和θ_min是两个 最大和最小的阈值；

若b₀＞θ_max：情境属性值的保持度大小保持不变；

若θ_min≤b₀≤θ_max：保持度大小会随着时间的流逝而逐渐减小，λ越 大，R(A₁，c_i，t)减小得越快，意味着情境属性值退化得越快；

若b₀＜θ_min保持度大小被置为0；

对于一个情境属性A_i，不同的层次级别被赋予了不同的保持度区 间，层次结构中所有的保持度区间没有交集，且所有的保持度区间的 并集构成整个区间[θ_min，θ_max]；

对于情境属性A_i的一个值c_i，它的保持度大小会依据函数 R(A_i，c_i，t)而减小，若当t＝t₀时，R(A_i，c_i，t)∈(θ_i-1，θ_i]，当t′＝t₀+Δt时， R(A_i，c_i，t′)∈(θ_j-1，θ_j]，1≤i＜j≤L，那么，c_i将会从层级h_i退化到层级h_j。

其中，所述步骤S1中的查询请求表示为： RF(Q，CM)＝<C₁，C₂，...，C_m>，其中，Q是用情境实例来形式化表示的 查询请求，CM是情境记忆快照，而Q在CM之上的中间查询结果是 情境实例的排序列表，<C₁，C₂，...，C_m>。

其中，所述步骤S2具体包括：逐个扫描CM中的情境实例，查 找与Q中的情境实例相匹配的情景实例，匹配的条件满足Q＝C、 C＜Q或Q＜C。

其中，所述步骤S2采用聚簇的方式进行匹配，所述聚簇为对于 每一个情境属性A_i的一组情境实例的聚簇集合，得到n个聚簇的集合 CL(A₁)，CL(A₂)，...，CL(A_n)，对于任意1≤i≤n，CL(A_i)＝{CC(A_i，r₁)， CC(A_i，r₂)，...，CC(A_i，r_z)}，其中z是CL(A_i)中的聚簇总数，CC(A_i，r_j)是 一个情境实例的聚簇，其中，1≤j≤z，每一个情境实例仅属于其中的 一个聚簇，r_j表示A_i中的情境属性，具体包括步骤：

S2.1：选取开始进行匹配的属性A_i，置匹配结果列表List为空；

S2.2：对于聚簇集合CL(A_i)中的每一个聚簇CC(A_i，r_j)，若 (r_j＝q_i)∨(r_j＜_aq_i)∨(q_i＜_ar_j)成立，则再检查CC(A_i，r_j)中的每一个情境实 例C，若满足(C＝Q)∨(C＜Q)∨(Q＜C)，则将C加入List。

其中，生成聚簇的步骤具体包括：

步骤1：为一个新的聚簇CC(A_i，r)确定其代表属性值r，从情境记 忆CM中尚未被聚簇的情境实例里面，以情境属性A_i为出发点找到一 个位于该层次结构中层级最高的情境属性值，然后以该值作为新聚簇 的代表属性值r；

步骤2：以CM中尚未被聚簇的情境实例组装CC(A_i，r)，对尚未 被聚簇的任一情境实例C，若其属性值等于r或是r的后代，且与r 的相似度不小于预定的聚簇阈值δ，则把C聚到CC(A_i，r)，因此， CC(A_i，r)＝{C|(C∈CM尚未被聚簇)∧((c_i＜_ar)∨(c_i＝r))∧sim(A_i，c_i，r)≥δ}， sim(A_i，c_i，r)为c_i和r的相似度。

步骤3：重复步骤1和步骤2，直到所有的情境实例都已被聚簇。

其中，所述步骤S2采用情境属性关联的方式进行匹配，为其层 次结构中的每一个值v构建一个关联关系链Chain(A_i，v)，该链连接了 所有包含该属性值v的情境实例，即对于任意C∈Chain(A_i，v)，都有 (c_i＝v)；扩展关联关系链Chain(A_i，v)，得到EChain(A_i，v)，满足对于任 意C∈EChain(A_i，v)，都有(c_i＝v)∨(c_i＜_av)∨(v＜_ac_i)，具体包括步骤：

S2.1：以Q的属性值出发，选取具有最短长度扩展链所对应的属 性A_i，置匹配结果列表List为空；

S2.2：对于扩展链EChain(A_i，q_i)中所连接的每一个情境实例C， 若满足以下条件(C＝Q)∨(C＜Q)∨(Q＜C)，则将C加入List。

其中，所述步骤S3具体为利用以下相似度函数来对情境记忆快 照中的情境实例基于查询请求Q来进行排序，

$\mathrm{Rank}(Q,C)=\mathrm{Sim}(Q,C)=\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sim}}^2(A_i,q_i,c_i)}.$

其中，所述步骤S3具体为基于加权的相似度排序，公式如下：

$\mathrm{Rank}(Q,C)=\sqrt{\underset{i=1}{\overset{n}{\Sigma }}{w_i·\mathrm{sim}}^2(A_i,q_i,c_i)}$

其中，w_i为情境属性q_i的权值，且w_i∈[0，1]，并且

其中，所述步骤S3具体为基于负向非相似度排序，公式如下：

$\mathrm{Dissim}(Q,C)=1-\underset{i=1}{\overset{n}{\min }}\mathrm{sim}(A_i,q_i,c_i)$

$\mathrm{Rank}(Q,C)=1-\mathrm{Dissim}(Q,C)=\underset{i=1}{\overset{n}{\min }}\mathrm{sim}(A_i,q_i,c_i).$

(三)有益效果

本发明提出的在情境记忆模型之上基于情境的信息回忆检索的 方法，具有以下优点：

1、依据人脑记忆机制而提出的基于情境的信息回忆检索的方法， 能够使得用户通过更容易记住的相关情境来查找曾经访问过的信息， 更加接近于人脑的回忆模式，使查找更准确、快速；

2、通过模拟人脑来构建情境记忆模型，应用了情境实例的聚簇 和关联关系结构，以及动态的生命周期演化策略，使得情境信息得以 有效组织，同时很好地消除了无关的情境信息；

3、通过应用情境聚簇及关联关系的特性来匹配查询请求，大大 减少了匹配过程所需耗费的时间代价。

附图说明

图1为本发明实施例的一种信息回忆检索方法中的情境记忆模型 演化的框架图；

图2为本发明实施例的一种信息回忆检索方法中的情境记忆模型 中的两个情境属性时间和地点的层次结构示意图；

图3为发明实施例的一种信息回忆检索方法中的情境记忆模型中 的一个情境记忆的演化示例；

图4为本发明实施例的一种信息回忆检索方法流程图；

图5为图4的方法中三种情境匹配的示意图，(a)为精确匹配、(b) 特殊匹配、(c)一般匹配；

图6为图4方法中的情境实例之间关联关系的示意图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细 描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

本发明基于人脑的回忆机制，用一个多维的向量来表示与信息内 容相关的情境实例，并在它们之间建立映射关系，从而使得用户可以 通过输入情境来查找想要的信息。具体是通过本发明提出的情境记忆 模型来实现信息回忆检索，以下是关于发明提出的情境记忆模型的详 细说明。

如图1所示，是本发明的情境记忆模型的框架图，在人脑记忆的 启发之下，本发明提出将情境记忆组织为两种记忆单元，即短期情境 记忆单元和长期情境记忆单元：

·短期情境记忆单元不但容量小，而且只持续很短的时间，通 常在几秒以内。存储在此单元中的情境信息一般会保持其原 始格式。

·长期情境记忆单元在容量上几乎是无限的，持续的时间可能 是几天或者是几十年。情境信息在长期记忆单元中被很好地 组织起来。长期情境记忆单元又分为两类：永久单元和一般 单元。前者存储的情境信息维持不变，而后者的情境信息则 会退化。

在本发明中，一个用户在访问信息时所处的境况被称为访问情 境，这些情境可以是用户相关的(如用户名，活动和日程安排等)， 也可以是外部环境相关的(如时间，地点和周围的人等)。如果所访 问的信息是用户感兴趣的，那么一个有关该信息的标识和访问情境实 例的映射关系就会被建立起来，而该信息的具体内容则会被保存到一 个实体库中。这样一个访问事件被称为有效的访问事件。

情境记忆是动态演化的，信息在两种情境记忆单元之间的流转如 下所示：

1、对于一个被短期情境记忆单元接收到的访问事件，如果它是 有效的，即用户能够记住该访问信息，则对应的情境实例将会在几秒 钟内传递到长期情境记忆单元；否则，它将会很快被丢失。

2、在长期情境记忆单元内，如果访问情境对于用户是极为深刻 或异常重要的，那么它将会被存储在永久单元里；否则，它会被存储 在一般单元里。

3、类似于人脑记忆会逐渐变得模糊，在一般单元内的情境信息 也会在其生命周期里随着时间的流逝而逐渐退化。

4、当一个在长期情境记忆单元里的情境实例被回忆起来时，它 会被送回到短期情境记忆单元中加强它的新鲜度和保持度，从而延缓 其退化进程。

本发明主要集中于长期情境记忆单元(简称为情境记忆)，接下 来介绍其静态结构和动态演化细节。

情境记忆的静态结构

访问情境包含了n维情境属性(A₁，A₂，...，A_n)，每一维情境属性 的定义域构成了一个不同抽象级别的排序的层次结构。情境属性A_i的层次结构可以看作为一个偏序关系格(H，＜_h)，其中H＝(h₁，h₂，...， h_L-1，ALL)共有L个层次，对应到的层次标识为(1，2，...，L-1，L)， 而＜_h是H中层次级别之间的偏序关系，对任意的1＜i＜L满足(h₁＜_h h_i＜_hALL)。如图2所示，为两个情境属性时间和地点的层次结 构例子。在H中的两个连续的层次h_i和h_i+1之间，有一个范围是0 到1之间的权重，以表示h_i和h_i+1的层次相似度，记为s_i，i+1。

对于H中的每一个层次级别，本发明基于一个选定的参照值， 根据属性值之间的距离为每一个结点进行排序。例如，在图2中，以 “2010-10-1”为参照值，则“2010-10-3”比“2010-10-8”更接近于 “2010-10-1”，所以在该层次级别中前者排在后者之前。同样地，在地 理位置上，“上海”比“广东”更靠近参照值“北京”，因此“上海”排在“广 东”之前。需要说明的是，情境属性值之间的排序依赖于具体的应用。

定义1：令c_i和c_i′是A_i的两个情境属性值(c_i，c_i′∈Dom(A_i))，则 c_i和c_i′可能位于H中相同或不同的层级。假设函数h(A_i，c_i)和h(A_i，c_i′) 分别返回c_i和c_i′所在的层级的标识值。c_i′称为c_i的父亲，记为c_i＜_ac_i′ (反过来，c_i称为c_i′的孩子)，当且仅当h(A_i，c_i)＝h(A_i，c_i′)-1并且 从c_i到c_i′存在一条只有一条边的路径。

本发明中，c_i＜_ac_i′也用来表示c_i′是c_i的父亲的父亲，等等。换 言之，c′_i称为c_i的祖先(反过来，c_i称为c_i′的后代)。

计算两个情境属性之间的相似度，取决于它们在层次级别中的距 离，以及它们在相同层级中的排序情况。

定义2：给定两个情境属性值c_i，c_i′∈Dom(A_i)，令k＝h(A_i，c_i)，k′ ＝h(A_i，c_i′)。c_i和c_i′之间的相似度，记为sim(A_i，c_i，c_i′)，定义如下：

1、如果c_i＝c_i′，则sim(A_i，c_i，c_i′)＝1；

2、如果c_i′＜_ac_i，则$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })={\Pi }_{l=k^{\prime }}^{k-1}{s}_{l,l+1},$c_i′＜_ac_i表示c_i为c_i′的 父亲；

3、如果c_i＜_ac_i′，则$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })={\Pi }_{l=k}^{k^{\prime }-1}{s}_{l,l+1};$

4、如果c_i和c_i′位于相同的层级而且有共同的父亲c_p，令n_p为c_p的孩子数目，n_c和n_c′为c_i和c_i′在c_p的所有孩子中的排序值，则

$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })=s_{k,k+1}^2+(1-\frac{|n_c-n_{c^{\prime }}|}{n_p-1})·s_{k,k+1}·(1-s_{k,k+1});$

5、如果c_i和c_i′位于两个不同的层次级别并且它们的共同祖先为c_p， 令m＝h(A_i，c_p)，则：

$\mathrm{sim}(A_i,c_i,{c_i}^{\prime })=\underset{l=k}{\overset{m-1}{\Pi }}{s}_{l,l+1}·\underset{j=k^{\prime }}{\overset{m-1}{\Pi }}{s}_{j,j+1}.$

根据定义2，给定三个情境属性值c_i1，c_i2，c_i3∈Dom(A_i)，可以很 容易得到以下两个推论：

1、如果c_i1＜_ac_i2且c_i2＜_ac_i3，那么sim(A_i，c_i1，c_i3)＜sim(A_i，c_i2，c_i3)；

2、如果c_i和c_i′位于相同的层级而且有共同的父亲c_p，令h(A_i，c_i) ＝h(A_i，c_i′)＝k，那么$s_{k,k+1}^2\le \mathrm{sim}(A_i,c_i,{c_i}^{\prime })<s_{k,k+1}.$

一个情境实例是其n维情境属性的实例化，表示为一个n元组 C＝(c₁，c₂，...，c_n)，其中对于任意的1≤i≤n，c_i∈Dom(A_i)。基于情境属 性值的相似度，可以计算两个情境实例的相似度。

定义3：给定两个情境实例C＝(c₁，c₂，...，c_n)和C′＝(c’_i，c’₂，...，c’_n)，它们 的相似度计算如下：

$\mathrm{Sim}(C,C^{\prime })=\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sim}}^2(A_i,c_i,c_i^{,})}.$

如图2中，假设C＝(“2010-10-1”，“北京”)和C′＝(“2010-10-3”，“北 京”)是两个二维的情境实例，则可计算$\mathrm{Sim}(C,C^{\prime })=\sqrt{\frac{1}{2}({0.72}^2+1)}=0.87.$

定义4：假设情境是一个n维的向量(A₁，A₂，...，A_n)，令 C＝(c₁，c₂，...，c_n)和C′＝(c’₁，c’₂，...，c’_n)为两个情境实例，则：

1、C等于C′，记为C＝C′，当且仅当$\forall i\in \{\mathrm{1,2},...,n\}(c_i^{,}=c_i).$

2、C比C′更一般化，记为C′＜C，当且仅当

3、C和C′在情境属性A_i上相关联，记为当且仅当 sim(A_i，c_i，c’_i)≥θ，其中θ是预设好的阈值。

例如，以图2所示的时间和地点两个情境属性的层次结构，令 C＝(“2010-10”，“中国”)，C′＝(“2010-10-1”，“北京”)，则C比C′更一般 化。在地点这一维情境属性上，当阈值θ＝0.75时C和C′相关联，因 为sim(地点，“中国”，“北京”)＝0.8＞θ。

定义5：给定一个情境属性的代表值r∈Dom(A_i)，以r为基准，一 组情境实例构成一个聚簇，记为CC(A_i，r)，对于 $\forall C=(c_1,c_2,...,c_n)\in \mathrm{CC}(A_i,r)$sim(A_i，c_i，r)≥δ∧(c_i∈Dom(A_i))∧((c_i＝r) ∨(c_i＜_ar))，其中δ是0到1之间的一个聚簇阈值。

例如上面的两个情境实例C＝(“2010-10”，“中国”)， C′＝(“2010-10-1”，“北京”)，当δ＝0.7时，它们就可以构成一个聚簇 CC(地点，“中国”)。

定义6：一个情境记忆的快照是一个图CM＝(V_CC，E_CC)，其中V_CC是 一组结点的集合(表示情境实例的聚簇)，E_CC是在一组在结点上的边 的集合(表示情境实例之间的关联关系)。这个图会随着时间而发生 变化，换言之，从某种程度上讲它是时间的一个函数。

一个情境记忆快照的图可能不是连接的。如图3所示，展示了三 个情境记忆快照。以CM₂为例，每一个方框表示一个情境实例C，它 由三个情境属性组成：时间、地点、活动。每一个虚线椭圆表示一个 情境实例的聚簇，而连接在两个情境实例之间的边表示关联关系(例 如，表示情境实例C₁和C₄在第二维情境属性相关联)。

情境记忆的动态演化

类似于人脑记忆会逐渐模糊直至消失，情境记忆快照也经历一个 逐步退化的生命周期，其中情境属性值会基于其所在的层次结构独立 地退化。当一个情境实例的全部属性都退化为“ALL”时，本发明认为 其对应的访问事件已被用户忘记，因此该情境实例会被剔除出情境记 忆快照。

为了量化情境属性的退化，基于心理学领域的研究成果，本发明 采用一个修正的指数-幂函数R(A_i，c_i，t)来表示情境属性值c_i在访问事 件发生t时间后(t也称为c_i的年龄)的保持度大小。本发明采用一 个实数值b∈[0，1]来刻画一个情境属性值的保持度，若b趋于1，则该 情境属性值被记得最清楚，若b接近于0，则该情境属性趋于被忘记。

其中，b₀是保持度的初始值，λ是退化速度系数，θ_max和θ_min是两 个最大和最小的阈值。

·若b₀＞θ_max：情境属性值的保持度大小保持不变，对应于前文

所述的长期情境记忆中的永久单元。

·若θ_min≤b₀≤θ_max：保持度大小会随着时间的流逝而逐渐减小，

对应于长期情境记忆中的一般单元。λ越大，R(A，c，t)减小得

越快，意味着情境属性值退化得越快。

·若b₀＜θ_max：保持度大小被置为0，对应于短期情境记忆单元。

对于一个情境属性A_i，不同的层次级别被赋予了不同的保持度区 间，如图2所示。特别地，一个层次结构中所有的保持度区间是互斥 的，且它们的并集构成一个区间[θ_min，θ_max]。图2所示的例子中， θ_min＝0.08，θ_max＝0.98。

对于情境属性A_i的一个值c_i，它的保持度大小会依据函数 R(A_i，c_i，t)而减小，其中t是c_i的年龄。若当t＝t₀时，R(A_i，c_i，t)∈[θ_i-1，θ_i)， 当t′＝t₀+Δt时，R(A_i，c_i，t′)∈[θ_j-1，θ_j)1≤i＜j≤L，那么，c将会从层级 h_i退化到层级h_j。

为了模拟人脑记忆的强化现象，即当情境属性A_i的一个值c_i被 用户回忆起来一次或多次时，为保持度的初始值r₀增大一个百分比 δ_r，同时为λ值减小一个百分比δ_λ，从而使得函数R(A_i，c_i，t)返回一个 较大的保持度值，亦即减缓了该情境属性值的退化速度。如图3所示， 展示了情境退化过程的一个例子。

基于以上说明，对情境记忆给出一个完整的定义如下：

定义7：一个情境记忆是一个确定型有穷自动机(P，∑，η，p₀，p_f)， 其中P是一组情境记忆快照的集合；∑是一组事件的集合，包括时间 事件和用户以情境实例作为查询条件的回忆检索事件；η是一组演化 函数P×∑→P的集合，满足于转化η(p_i，e_k)＝p_i+1，(p_i＜_P p_i+1)；p₀∈P是 初始情境记忆快照；p_f∈P是终止情境记忆快照，包含空值

建立了情境记忆模型，便可以基于情境记忆模型实现信息回忆检 索，以下详细说明在情境记忆模型之上，基于情境的信息回忆检索的 实现方法。

基于情境的信息回忆检索与传统的数据库查询方法相比，主要有 三方面的不同。首先，查询请求的形式表示是基于情境属性的，而非 数据库内容；其次，查询的对象是情境记忆快照，而不是数据库；第 三，查询的中间结果是情境实例的一个排序列表，它们所映射到的用 户曾经访问的信息是最终的查询结果。考虑到最终的查询结果可以很 容易地从中间结果中获取到，本发明主要集中于怎样得到查询请求的 中间结果。

如图4所示，本发明的方法包括：

步骤S401，接收包含情境实例的查询请求。一个基于情境的信 息回忆检索的查询可以表示为一个函数RF(Q，CM)＝<C₁，C₂，...，C_m>， 其中Q是用一个情境实例来形式化表示的查询请求，CM是查询对象， 即是一个情境记忆快照，而Q在CM之上的中间查询结果是一个情 境实例的排序列表，<C₁，C₂，...，C_m>，它们的排序结果是基于一个排序 函数的。

步骤S402，以情境记忆作为查询对象，与用户提交的查询请求 中的情境实例进行匹配，得到满足查询条件的一组情境实例，其中， 情境记忆中至少包含一个情境实例。对于一个查询请求(情境实例)， 由于查询对象(情境记忆快照)的退化，有可能或不一定能够精确匹 配到情境记忆中的情境实例。Q和C匹配时，有三种匹配情形，如图 5中(a)、(b)、(c)所示，分别为(a)精确匹配，Q＝C；(b)特殊 匹配，C＜Q；(c)一般匹配，Q＜C。

基于Q的信息回忆检索的一种很直接的方法就是，逐个扫描CM 中的情境实例，以返回那些对Q精确匹配、特殊匹配和一般匹配的 情境实例，然后再根据排序方法来对匹配到的结果进行排序。在这一 过程中，匹配部分占到最主要的时间开销，其时间复杂度为 O(n·|CM|)，其中n是情境属性的维数，|CM|是情境记忆的大小(即 CM中情境实例的数量)。显然地，这种查找方法没有很好的可伸缩 性，当情境实例的数量不断增加时，其时间开销也会极大地增加。因 此，需要设计一些高效的查询策略，以减少开销。

查询策略1：基于聚簇的回忆检索方法。

对于每一个情境属性A_i，可以生成一组情境实例的聚簇集合，其 过程如下：

步骤1、为一个新的聚簇CC(A_i，r)确定其代表属性值r。从情境记 忆CM中尚未被聚簇的情境实例里面，以情境属性A_i为出发点找到一 个位于该层次结构中层级最高的情境属性值，然后以该值作为新聚簇 的代表属性值r。

步骤2、以CM中尚未被聚簇的情境实例组装CC(A_i，r)。对尚未 被聚簇的任一情境实例C，若其属性值等于r或是r的后代，且与r 的相似度不小于聚簇阈值δ，则把C聚到CC(A_i，r)。因此， CC(A_i，r)＝{C|(C∈CM尚未被聚簇)∧((c_i＜_ar)∨(c_i＝r))∧sim(A_i，c_i，r)≥δ}。

步骤3、重复步骤1和2，直到所有的情境实例都已被聚簇。

由此，可以得到n个聚簇的集合CL(A₁)，CL(A₂)，...，CL(A_n)。对于 任意(1≤i≤n)，CL(A_i)＝{CC(A_i，r₁)，CC(A_i，r₂)，...，CC(A_i，r_z)}，其中z 是CL(A_i)中的聚簇总数，CC(A_i，r_j)是一个情境实例的聚簇，其中，1≤j ≤z。这些情境聚簇都是互斥的，换言之，每一个情境实例仅属于其 中的一个聚簇。

经过聚簇以后，对查询请求Q的匹配可以利用聚簇的性质来实 现。对于一个聚簇CC(A_i，r)，若其所包含的情境实例有可能匹配Q即 满足以下三个条件之一：(1)r＝q_i；(2)r＜_aq_i；(3)q_i＜_ar，则 称CC(A_i，r)为Q的一个候选聚簇。

考虑到Q有n个属性值，这里只选取其中的一个属性值来开始 匹配：选取的属性值应当能够得到最少数量的候选聚簇，即n个属性 值中层级最低的那个属性。匹配的过程如下：

步骤1、选取开始进行匹配的属性A_i；

步骤2、置匹配结果列表List为空；

步骤3、对于聚簇集合CL(A_i)中的每一个聚簇CC(A_i，r_j)，若 (r_j＝q_i)∨(r_j＜_aq_i)∨(q_i＜_ar_j)成立(CC(A_i，r_j)是候选聚簇)，则再检查 CC(A_i，r_j)中的每一个情境实例C，若满足(C＝Q)∨(C＜Q)∨(Q＜C)，则 将C加入List；

步骤4、基于Q对List进行排序，即得到查询请求的中间结果。

互斥的候选聚簇中包含了所有可能匹配Q的情境实例。显然地， 因为对于任意情境实例C，若C匹配Q，即意味着 (r_j＝q_i)∨(r_j＜_aq_i)∨(q_i＜_ar_j)成立，而这恰是筛选出候选聚簇的条件。因 此，上述的匹配方法是正确的。

考虑步骤1至步骤3的时间复杂度，步骤1需要O(n)级开销，步 骤2需要O(1)级开销，而步骤3需要O(n·|CL(A_i)|·|CC(A_i，r_j)|)级开销。

因此，步骤1至步骤3的整体时间开销为 O(n)+O(1)+O(n·|CL(A_i)|·|CC(A_i，r_j)|)＝O(n·|CL(A_i)|·|CC(A_i，r_j)|)，其中 |CL(A_i)|是聚簇集合的数目，|CC(A_i，r_j)|是聚簇CC(A_i，r_j)中情境实例的 数目。显然，基于聚簇来查询的时间开销依赖于聚簇的数量以及聚簇 的大小，而这与聚簇阈值δ相关。

查询策略2：基于关联关系的回忆检索方法。

本发明还设计了基于情境属性值之间的关联关系来回忆检索信 息的方法。对于每一个情境属性A_i，本发明为其层次结构中的每一个 值v构建一个关联关系链Chain(A_i，v)，该链连接了所有包含该属性值 v的情境实例，也就是，对于任意C∈Chain(A_i，v)，都有(c_i＝v)。如图 6所示，展示了情境记忆中的6个3维情境实例，C₁，C₂，C₃，C₄，C₅，C₆。 图6的左侧列举了一些关联关系链。

为了更好地支持查询请求和情境实例之间的精确、特殊以及一般 的匹配，需要对每一个关联关系链进行扩展，使其包含该属性值在层 次结构中的所有祖先及后代。从而得到扩展的关联关系链 EChain(A_i，v)，满足对于任意C∈EChain(A_i，v)，都有 (c_i＝v)∨(c_i＜_av)∨(v＜_ac_i)。

例如，因为“2010-09”，“2010-10”＜_a“2010”，Chain(A_i，″2010″)被 扩展到包含了{“2010”，“2010-09”，“2010-10”}，而Chain(A₁，″2010-09″) 被扩展到包含了{“2010”，“2010-09”}，如图6的右侧所示。

给定一个查询请求Q＝(“2010”，“家”，“聊天”)，为了查找与其 匹配的情境实例，应当从具有最短长度的扩展链开始，然后检查所连 接的情境实例的其他属性值与Q的属性值的匹配情况。

基于关联关系的匹配过程如下：

步骤1、以Q的属性值出发，选取具有最短长度扩展链所对应的 属性A_i；

步骤2、置匹配结果列表List为空；

步骤3、对于扩展链EChain(A_i，q_i)中所连接的每一个情境实例C， 若满足以下条件(C＝Q)∨(C＜Q)∨(Q＜C)，则将C加入List；

步骤4、基于Q对List进行排序，即得到查询请求的中间结果。

因为所有可能匹配Q的情境实例都包含在选取的具有最短长度 的扩展链EChain(A_i，q_i)中，显然结果列表List包含了全部匹配的情境 实例。因此，上述查询方法是正确的。

考虑步骤1至步骤3的时间复杂度，步骤1需要O(n)级开销，步 骤2需要O(1)级开销，而步骤3需要O(n·|EChain(A_i，q_i)|)级开销。因此， 步骤1至步骤3的整体时间开销为 O(n)+O(1)+O(n·|EChain(A_i，q_i)|)＝O(n·|EChain(A_i，q_i)|)，其中 |EChain(A_i，q_i)|是扩展链包含的全部情境实例数目。

步骤S403，依据所述一组情境实例和查询请求中的情境实例的 相似度对所述一组情境实例进行排序。本发明提供了有三种不同的排 序方法，即基于Q和C之间的简单相似度排序、基于加权的相似度 排序和基于负向非相似度排序。不失一般性，令Q＝(q₁，q₂，...，q_n)， C＝(c₁，c₂，...，c_n)。

基于简单相似度排序：一种直接的方法就是利用前文所述的相似 度函数来对情境记忆快照中的情境实例基于查询请求Q来进行排序。

$\mathrm{Rank}(Q,C)=\mathrm{Sim}(Q,C)=\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{\mathrm{sim}}^2(A_i,q_i,c_i)}.$

基于加权的相似度排序：考虑到用户的查询请求Q会由于记忆 的模糊化而变得模糊起来，而有些情境属性值(例如活动)有可能比 其他属性值(例如时间)会给用户留下更深刻的印象，这里引入一个 权值向量(w₁，w₂，...，w_n)，用来表征查询请求Q中不同属性值的精确 度，其中对于每一个1≤i≤n都满足w_i∈[0，1]，并且

$\mathrm{Rank}(Q,C)=\sqrt{\underset{i=1}{\overset{n}{\Sigma }}{w_i·\mathrm{sim}}^2(A_i,q_i,c_i)}.$

基于负向非相似度排序：Q和C之间的相似度也可以通过它们之 间的非相似度来衡量。

$\mathrm{Dissim}(Q,C)=1-\underset{i=1}{\overset{n}{\min }}\mathrm{sim}(A_i,q_i,c_i)$

$\mathrm{Rank}(Q,C)=1-\mathrm{Dissim}(Q,C)=\underset{i=1}{\overset{n}{\min }}\mathrm{sim}(A_i,q_i,c_i).$

步骤S404，得到经过排序的一组情境实例后，根据一组情境实例 和各自的信息内容的映射关系，将具体的信息内容返回给用户。其中， 情境实例和对应的具体信息内容的映射关系事先已建立，并存储在情 境记忆中。

以上实施方式仅用于说明本发明，而并非对本发明的限制，有关 技术领域的普通技术人员，在不脱离本发明的精神和范围的情况下， 还可以做出各种变化和变型，因此所有等同的技术方案也属于本发明 的范畴，本发明的专利保护范围应由权利要求限定。