基于数据流的时间条件占优查询

doi:10.13232/j.cnki.jnju.2023.04.004

基于数据流的时间条件占优查询

田金灿, 孙雪姣^,

烟台大学计算机与控制工程学院，烟台，264005

Query time⁃conditional preference query based on data flow

Tian Jincan, Sun Xuejiao^,

College of Computer and Control Engineering，Yantai University，Yantai，264005，China

通讯作者: E⁃mail：sunxuejiao6@sina.com

收稿日期: 2023-06-05

基金资助:

国家自然科学基金. 62072392

Received: 2023-06-05

摘要

传统的偏好推理使用权衡增强的条件偏好网络（Tradeoff⁃Enhanced Conditional Preference Networks，TCP⁃nets）进行用户的偏好推理，不仅能高效地表示对元组的定性偏好关系并优化用户偏好结果，还能描述每个属性之间的偏好关系，其主要聚焦于关系元组中的单个属性的偏好.但把对条件偏好查询的技术推广到数据流的条件提取却是一个挑战，面临的技术困难主要是对数据流中序列的提取，对提取的序列进行占优查找等.首先，针对偏好数据流，提出一种时间条件查询语言Stream Pref来处理数据流；其次，在Stream Pref中加入时间索引来推理和规范数据流提取序列的时间条件偏好，提出提取对象序列算法、占优对象及占优序列查找算法和数据流序列间占优对比的算法；最后，在数据集上分析验证提出的算法的有效性.实验结果证明，提出的算法与min Top⁃k，Partition和Incpartition算法相比，得到的结果更准确.

关键词： TCP⁃nets ; 偏好查询 ; 连续查询语言 ; 时间索引 ; 占优对比

Abstract

Traditional preference inference uses tradeoff⁃enhanced conditional preference networks for user preference inference，which not only efficiently represent qualitative preference relations over tuples and optimize user preference results，but also describe preference relations between each attribute. The main focus is on the preference of individual attributes in relational tuples，but it is a challenge to extend the technique of conditional preference query to the conditional extraction of data streams，and the technical difficulties are mainly the extraction of sequences in the data streams and the preference finding of the extracted sequences. Firstly，a temporal conditional query language Stream Pref is proposed to process the data streams for preference data streams. Secondly，Stream Pref incorporates a temporal index to reason and standardize the temporal conditional preferences of the extracted sequences of data streams. An algorithm for extracting object sequences，an algorithm for finding preference objects and preference sequences and an algorithm for preference comparison among data stream sequences are proposed. Finally，the effectiveness of the algorithm proposed in this paper is analyzed and verified on the data set. Experimental results show that the proposed algorithm gets more accurate results compared with min top⁃k algorithm，partition algorithm and incpartition algorithm.

Keywords： TCP⁃nets ; preference query ; continuous query language ; time index ; dominant contrast

PDF (729KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

田金灿, 孙雪姣. 基于数据流的时间条件占优查询. 南京大学学报（自然科学）[J], 2023, 59(4): 570-579 doi:10.13232/j.cnki.jnju.2023.04.004

Tian Jincan, Sun Xuejiao. Query time⁃conditional preference query based on data flow. Journal of nanjing University[J], 2023, 59(4): 570-579 doi:10.13232/j.cnki.jnju.2023.04.004

偏好在很多情况下可以引导用户的选择，用户偏好分定量和定性，定量偏好通过效用函数^［1］来描述用户的偏好，定性偏好通过定义二元关系来表示偏好关系.用户偏好的特征分两点：（1）偏好通常受一组属性所影响，例如用户旅游时天气等因素会影响用户的体验；（2）用户偏好之间有依赖关系，例如用户选择上衣时依赖裤子的颜色^［2］.过去几十年，偏好推理的研究在人工智能、数据库等领域不断发展，许多研究都致力于评价偏好问题.

大数据技术的发展，在网络中产生了大量的无界数据，导致需要处理数据流的新应用程序的增加，因此，提取偏好信息是数据流领域^［3-4］的重要任务.数据流具有连续性、无限性，只能读取一次，而且数据总量大，因此处理数据流时需要实时处理新生成的数据元素^［5］.同时，数据的不断变化使用户需要长时间连续查询并更新查询结果，成为偏好领域的热门研究之一.在数据流场景中，数据元素按时间顺序关联，因此，用户可以使用时间条件偏好来表达偏好如何受前一个时刻的影响，更加适用于对数据流的偏好处理.

Stream Pref语言主要处理带有时间索引的条件偏好连续查询（Continuous Temporal Condition Preference Queries），其使用逻辑框架TPref，对时间索引对象序列进行定性偏好诱导和推理，通过在CP⁃nets中使用静态规则外的时间条件偏好来推广CP⁃nets的形式体系，提出一种算法来产生满足给定时间约束的最优序列.本文提出一种时间偏好查询算法，首先提取数据流中的序列，其次利用占优对比算法对序列进行偏好比较，最终，得到满足用户偏好的信息.

1 相关工作

1.1　偏好推理

偏好推理可以得到数据流中最符合用户需求的信息.

权衡增强的条件偏好网络（Tradeoff⁃Enhanced CP⁃nets，TCP⁃nets）^［6-7］是研究偏好推理、描述用户偏好的主要工具之一，它使用图形模型高效地表示对元组的定性偏好关系，同时优化用户所有感兴趣的偏好结果.Amor et al^［8］提出关于偏好表示的图形模型来描述用户偏好.Kießling and Köstler^［9］提出偏好SQL （Structured Query Language）语言，第一次引入偏好推理的相关概念，通过基于严格偏序的偏好模型扩展了结构化查询语言，提出基本偏好构造函数，将Preference SQL偏好转换为标准的SQL查询.TCP⁃nets^［10］是CP⁃nets的一种演化，引入了属性的绝对和相对重要性.Ahmed and Mouhoub^［11］提出逻辑形式主义，通过允许不同的属性来概括CP⁃nets和TCP⁃nets方法，可以减缓Ceteris Paribus语义，达到更高的表达能力.这种逻辑形式主义也是CPrefSQL语言使用的偏好模型的基础.de Amo and Giacometti^［12］用TPref形式来表达时间条件偏好.Ribeiro et al^［13］提出Stream Pref形式主义，是TPref形式主义的改进，但Stream Pref更适合对数据流进行推理.Stream Pref查询语言的BESTSEQ运算符使用Stream Pref形式来比较序列.

1.2　偏好查询

一个查询被启动后连续不断地运行直到该查询被终止，对于数据流偏好的查询是考虑用户偏好进行的连续查询.

刘兆伟^［14］提出基于流式数据的增量式学习方法.Alguliyev et al^［15］基于skyline操作符来解决用户偏好查询的算法.El Maarry et al^［16］提出skyline操作符的偏好查询优化，还提出一些基于启发式的方法.Huo and Zhang^［17］提出的skyline操作符提高了查询效率.Zervoudakis et al^［18］提出与连续偏好查询相关的内容.杨茸和牛保宁^［19］提出文本数据流的连续查询.传统的连续查询语言（Continuous Query Language，CQL）不支持序列结构^［20］.Ribeiro et al^［21］提出连续查询语言的等效算法，在其中加入元组（tuple），用一组tuple表示对序列的处理.Kontaki et al^［22］提出对最近数据的连续偏好查询进行评估的算法，其中每个元组都有一个时间戳和有效区间.de Amo and Bueno^［23］提出一种基于祖先列表的增量算法来评估连续CP⁃queries.Ribeiro et al^［24］提出Stream语言，在传统CQL基础上添加了两个操作符SEQ和BESTSEQ来选择提取最佳序列.王卫星^［25］提出一种流式数据的CP⁃nets的学习方法，通过比较基本块与滑动窗口的大小，对偏好关系进行实时更新.

本文算法加入了时间索引，使用基于哈希的访问方法对数据序列进行处理，占优对比得到最优序列；同时，减少了序列间对象的对比次数，提高了偏好信息的查询效率.

2 相关定义

定义1

设 $X = \{A_{1}, A_{2}, \dots, A_{n}\}$ 是表示决策属性的集合，其中， $D o m (A_{i})$ 代表属性 $Α_{i}$ 的定义域， $X$ 上的对象集 $Ω = D o m (A_{1}) \times D o m (A_{2}) \times \dots \times D o m (A_{n})$ 表示所有属性的可能组合.序列 $s = 〈t_{1}, t_{2}, \dots, t_{n}〉$ 是一个元组的有序集合，对于 $i \in \{1,2, \dots, n\}$ ，有 $t_{i} \in Ω$ .

$|s|$ 表示序列 $s$ 的长度，序列 $s$ 中位于位置 $i$ 的元组用符号 $s [i]$ 表示， $A$ 表示在 $s$ 的第 $i$ 个位置的属性 $A$ .符号 $s [i, j]$ 表示序列 $s' = 〈t_{i}, \dots, t_{j}〉$ 是序列 $s$ 的子序列 $(1 \leq i \leq n, i \leq j \leq n)$ .两个序列的连接 $s = 〈t_{1}, \dots, t_{n}〉$ 和 $s' = 〈t_{1}^{'}, t_{2}^{'}, \dots, t_{n^{'}}^{'}〉$ ，用 $s + s^{'}$ 表示为 $s ″ = 〈t_{1}, t_{2}, \dots, t_{n}, t_{1}^{'}, t_{2}^{'}, \dots, t_{n^{'}}^{'}〉$ .属性 $X$ 上所有可能序列的集合用 $S e q (X)$ 表示.

Stream Pref使用命题构成的公式，形式如式（1）所示：

\begin{array}{l} A θ a (A 为命 题, a \in D o m (A), \\ θ \in \{\leq, <, =, \neq, >, \geq\}) \end{array}

(1)

假设 $Q (A)$ 是一个命题， $a = Q (A)$ 表示满足命题 $Q (A)$ ， $S_{Q (A)} = \{a \in D o m (A)| a = Q (A)\}$ 表示满足 $Q (A)$ 的值集.

定义2

在对象集 $Ω$ 上定义一个二元关系 $≻$ ，具有自反性、传递性和反对称性，即 $≻$ 是严格的偏序关系时称 $≻$ 为 $Ω$ 上的严格偏好关系. $≻$ 反映决策者对于两个配置 $o$ 和 $o^{'}$ 的偏好强弱关系，即 $o ≻ o^{'}$ 表示决策者对 $o$ 的偏好强于对 $o^{'}$ 的偏好.

定义3

Ceteris Paribus理论上表示其他条件均有相同的偏好，这种偏好关系表达了所有配置上可能存在的偏好信息，若其他条件不变，对象之间偏序的关系会被单个属性的改变影响.CP⁃nets严格遵循Ceteris Paribus（all else being equal）的语义，即对于 $o \in Ω$ ，除了某个属性 $X_{i}$ 值不同而其他属性值都相同的情况下，用户对 $X_{i}$ 不同取值的一种偏好排序.

定义4

基本公式^［26］ $t r u e$ 和 $f a l s e$ 是基本公式.如果 $F$ 是一个命题，那么 $F$ 是一个基本公式.如果 $F$ 和 $G$ 是基本公式，则 $(F \land G)$ ， $(F \lor G)$ ， $(F s i n c e G)$ ， $\neg F$ 和 $\neg G$ 是基本公式.

序列 $s = 〈t_{1}, t_{2}, \dots, t_{n}〉$ 在位置 $i \in \{1,2, \dots, n\}$

$(用 (s, i)| = F 表示)$ ，满足公式 $F$ 的概念定义如式（2）~（7）所示：

(s, i)| = Q (A) \Leftrightarrow s [i]| = Q (A)

(2)

(s, i)| = F \land G \Leftrightarrow (s, i)| = F \land (s, i)| = G

(3)

(s, i)| = F \lor G \Leftrightarrow (s, i)| = F \lor (s, i)| = G

(4)

(s, i)| = \neg F \Leftrightarrow (s, i)| \neq F

(5)

\begin{array}{l} (s, i)| = (F s i n c e G) \Leftrightarrow (s, j)| = G \land (s, k)| = \\ F (\exists j, 1 \leq j \leq i, j + 1 < k \leq i) \end{array}

(6)

\begin{array}{l} (s, i)| = (F u n t i l G) \Leftrightarrow (s, j)| = G \land (s, k)| = \\ F (\exists j, i \leq j \leq |s|, j + 1 < k \leq i) \end{array}

(7)

还有以下派生公式，如式（8）~（11）所示：

\begin{array}{l} P r e v Q (A) : (s, i)| = P r e v Q (A) \Leftrightarrow \\ (s, i - 1)| = Q (A) \end{array}

(8)

\begin{array}{l} S o m e P r e v Q (A) : (s, i)| = S o m e P r e v Q (A) \Leftrightarrow \\ (s, j)| = Q (A) (\exists j, 1 \leq j \leq i) \end{array}

(9)

\begin{array}{l} A l l P r e v Q (A) : (s, i)| = A l l P r e v Q (A) \Leftrightarrow \\ (s, j)| = Q (A) (j \in \{1,2, \dots, i - 1\}) \end{array}

(10)

F i r s t : (s, i)| = F i r s t Q (A) \Leftrightarrow i = 1

(11)

定义5

时间条件是 $F = F_{1} \land F_{2} \dots \land F_{n}$ ，其中 $F_{1}, F_{2}, \dots, F_{n}$ 是命题或导出公式. $F$ 的时态分量（ $F \leftarrow$ ）为 $F$ 中所有推导公式的合取. $F •$ 表示 $F$ 的非时态分量，是 $F$ 中所有命题的合取，在 $F \leftarrow$ 中不存在.符号 $A t t (F)$ 表示出现在 $F$ 中的属性.

定义6

给定TCP两个规则 $φ$ 和 $φ^{'}$ ，且 $C_{φ} = (F_{1} \land F_{2} \dots \land F_{p})$ ， $C_{φ^{'}} = (F_{1}^{'} \land F_{2}^{'} \land \dots \land F_{p}^{'})$ .如果命题 $F_{i}$ 和 $F_{j^{'}}$ 在时间上是兼容的，那么两个TCP规则是时间兼容的， $i \in \{1,2, \dots, p\}, j \in (1,2, \dots, q)$ .

定义7

假设X是一组属性集合.时间条件偏好规则（Temporal Condition Preference rules，TCP⁃rules）的表达式如式（12）所示：

C_{φ} \to Q_{φ}^{+} (A_{φ}) ≻ Q_{φ}^{-} (A_{φ})

(12)

（1）在同一个属性 $A_{φ}$ 上，命题 $Q_{φ}^{+}$ 和 $Q_{φ}^{-}$ 分别表示占优项和非占优项，属性 $A_{φ}$ 被称为偏好属性. $S_{Q_{φ}}^{+} (A_{φ}) ⋂ S_{Q_{φ}}^{-} (A_{φ}) = \emptyset$ .

（2） $W_{φ} \subset X$ 是无关属性的集合，例如 $A_{φ} \notin W_{φ}$ .

（3） $C_{φ}$ 是一个时间条件， $A t t (C \cdot φ) ⋂ W_{φ} = \emptyset$ .

时间条件偏好理论（TCP理论）是有限的TCP⁃rules集合.

给定一条TCP⁃rules和两个序列 $s$ ， $s^{'}$ ，根据 $φ$ ，用 $s ≻_{φ} s^{'}$ 表示序列 $s$ 优先于序列 $s^{'}$ ，iff $\exists i$ .

（1）在 $i$ 之前的所有位置在两个序列中都必须相同， $s [j] = s^{'} [j], j \in \{1, \dots, i - 1\}$ .

（2） $s$ 和 $s^{'}$ 的位置必须满足规则条件 $C_{φ}$ ， $(s, i)| = C_{φ}$ 且 $(s^{'}, i)| = C_{φ}$ .

（3） $s$ 的位置 $i$ 具有优选值，而 $s^{'}$ 的位置 $i$ 具有非优选值，有 $s [i] . A_{φ}| = Q_{φ}^{+}$ 和 $s^{'} [i] . A_{φ}| = Q_{φ}^{-}$ .

（4）不包括偏好属性 $A_{φ}$ 和 $W_{φ}$ 的无关属性，位置 $i$ 的所有属性在两个序列中必须有相同的值， $s [i] . A^{'} = s^{'} [i] . A^{'}$ ，对于所有 $A^{'} \notin (\{A_{φ}\} ⋃ W_{φ})$ .

实例1 假设一名足球教练使用足球场信息管理系统来查询球员在球场移动的实时数据信息，有属性集合Mm（球员的移动类型）、L（运动员在足球场的位置）、H（是否控球）.Mm的取值有前进（Qi）、后退（Ho）、横向（Pi）.L的取值有守门区（aa）、防守区（ab）、前卫（ac）、进攻区（ad）和射门区（ae）.H的取值为1（控球）或0（不控球）.例如序列 $s = 〈(a b, 1, Q i), (a c, 1, P i), (a b, 1, H o)〉$ 表示运动员s在球场中的位置行动轨迹是：在防守区控球前进，在前卫控球横向移动，在防守区控球向后移动，如图1所示.考虑该应用程序的场景，足球教练可以决定以下关于球员移动的时间偏好：

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 运动员的行动轨迹

Fig.1 The athletes' action trajectory

（1）假如在某时刻球员控球，并且在此刻之前该球员处在ab，那么教练更喜欢该球员去ac而不是ab，与Mm无关.

（2）假如在某时刻球员不控球，并且在此之前球员控球并且处于ad，那么教练更喜欢球员在ac而不是ab.

（3）横向移动比前进更好.

使用TCP理论 $Φ = \{φ_{1}, φ_{2}, φ_{3}\}$ 来表示偏好信息.该理论由以下TCP规则组成：

\begin{array}{l} φ_{1} : P r e (L = a b) \land (H = 1) \to \\ (L = a c) ≻ (L = a b) [M m] \\ φ_{2} : A l l P r e (H = 1) \land (H = 0) \land P r e (L = a d) \to \\ (L = a c) ≻ (L = a d) \\ φ_{3} : \to (M m = P i) ≻ (M m = Q i) \end{array}

根据TCP理论 $Φ = \{φ_{1}, φ_{2}, φ_{3}\}$ ，对以下序列进行优先级推理.

\begin{array}{l} s a = \\ 〈(a b, 1, Q i), (a c, 1, Q i), (a d, 1, Q i), (a c, 0, P i)〉 \end{array}

\begin{array}{l} s b = \\ 〈(a b, 1, Q i), (a c, 1, Q i), (a d, 1, Q i), (a d, 0, P i)〉 \end{array}

s c = 〈(a b, 1, Q i), (a b, 1, P i), (a c, 1, Q i), (a c, 0, H o)〉

由TCP规则 $φ_{1}$ 可知，在防守区 $s a ≻_{φ_{1}} s c$ ，且 $s b ≻_{φ_{1}} s c$ ；由TCP规则 $φ_{2}$ 可知，在进攻区 $s a ≻_{φ_{2}} s b$ .因此可知 $s a ≻_{Φ} s b ≻_{Φ} s c$ .

3 算法设计

3.1　算法详细设计

本节详细描述从数据流中提取序列的算法、对提取序列的查找算法以及占优查找算法.

算法1是提取序列算法，使用散列表 $H$ 来增量地执行序列的提取.以秒为单位接受时间范围参数 $k$ ，基于时间滑动窗口，时间间隔为1 s.

算法1 提取序列算法EXT sequences

输入：要提取的数据流 $S$ ，属性 $z$ ，时间滑动间隔 $k$

输出：散列表 $H$ 中的序列

Step 1

for each $o \in S [λ]$

Step 1.1

$z \leftarrow G e t I d (o, Z)$ /*获取对象的属性*/

Step 1.2

if $z \notin H . K e y s (), s_{z} \leftarrow {〈o / Z〉}_{z}$ /*将对象o中移除z的属性标识符*/

Step 1.3

else $s_{z} \leftarrow H . G e t (z) + {〈o / Z〉}_{z}$ /*从H中获取属性z，移除z的属性标识符*/

Step 2

$H . P u t (z, s_{z})$ /*将序列插入散列表*/

Step 3

for each $s_{z} \in H$ $D e l e t e (s_{z}, λ - k)$ /*循环散列表序列删除过期元素*/

Step 4

return $H$

散列表 $H$ 将每个属性 $z$ 与序列 $s_{z}$ 关联.散列表最初是空表，在时间滑动间隔 $k$ 时，算法更新散列表并返回序列，直至当前时刻 $λ$ .首先循环遍历数据流对象集合，通过Step1.1获取对象的属性；通过Step1.2判断对象的属性是否属于散列表 $H$ ，如果属于 $H$ ，将对象 $o$ 中移除 $z$ 的属性标识后赋值给 $s_{z}$ ，否则将 $〈o / Z〉$ 加入原有的散列表 $H$ ；Step2将插入各自序列，通过Step3将循环遍历 $s_{z}$ 删除过期元素，最后Step4返回 $H$ 中的序列.

占优对象查找算法使用深度优先搜索（Depth First Search，DFS）寻找从对象 $o^{+}$ 到对象 $o^{-}$ 的规则，用来验证序列间对应位置 $i$ 处对象 $s [i]$ 是否优于对象 $s' [i]$ .

算法2

占优对象查找算法（FDO）

输入：条件偏好理论Γ，对象 $o^{+}$ ， $o^{-}$

输出：占优对象 $o'$

Step 1

$i n t e r v i e w e d \leftarrow \{\}$

Step 2

$c o n t i n u e \leftarrow S t a c k (i n t e r v a l O b j e c t (o^{+}))$ /*将对象 $o^{+}$ 转化为区间再转为堆栈存储到continue中*/

Step 3

while $(t r u e)$

Step 3.1

if $|c o n t i n u e| = 0$ break /*判断continue是否为空*/

Step 3.2

$o \leftarrow c o n t i n u e . p o p ()$ /*从continue中获取对象o并将o标记为已访问*/

Step 3.3

$i n t e r v i e w e d \leftarrow i n t e r v i e w e d ⋃ \{o\}$

Step 3.4

if $I s G o a l (o^{-}, o)$ return true/*判断属性 $A_{i}$ ，是否存在从对象 $o . A_{i}$ 到 $o^{-} . A_{i}$ 的规则*/

Step 3.5

for each $φ \in Γ$ /*循环时间条件偏好规则 $φ$ */

Step 3.5.1

if $o \neq C_{φ}$ 或 $o \neq Q_{φ}^{+} (A_{φ})$ return $\emptyset$ /*判断对象 $o$ 是否满足条件偏好规则或是否为占优项*/

Step 3.5.2

$o^{'} . A_{φ} \leftarrow I n t e r v a l (Q_{φ}^{-} (A_{φ}))$ /*获取新对象 $o^{-}$ */

Step 3.5.3

for each $A_{i} \in W_{φ}$ $o^{'} . A_{i} \leftarrow [- \infty, + \infty]$ /*在 $W_{φ}$ 循环属性 $A_{i}$ */

Steo 3.5.4 if $(o' \neq N U L L) & (o' \notin i n t e r v i e w e d)$ /*判断对象 $o^{'}$ 不为空且未被访问*/

c o n t i n u e . p u s h (o')

Step 3.6 return false

Step 1~3.3查找目标对象，Step 2中 $i n t e r v a l O b j e c t (o^{+})$ 将对象 $o^{+}$ 转换为区间，再通过 $S t a c k$ 转化成堆栈，Step3.1判断 $c o n t i n u e$ 是否为空，不为空时将 $o$ 出栈并标记为已访问.通过 $I s G o a l$ 判断 $o$ . $A_{i}$ 到 $o^{-}$ . $A_{i}$ 的规则是否存在，若存在返回true，反之通过循环Step 3.4在 $o$ 应用偏好规则 $φ$ .获取新的对象 $o^{-}$ ，若 $o^{-}$ 不为空且未被访问，将 $o^{-}$ 推回 $c o n t i n u e$ 中，在另一个堆栈中搜索.

占优序列查找算法搜索序列第一个不同位置标记为 $i$ ，然后在位置 $i$ 处创建TCP规则，通过在 $i$ 处的偏好进而对序列之间的偏好关系进行验证.

算法3

占优序列查找算法（DS）

输入：提取序列 $s$ ， $s^{'}$

输出： $s ≻ s^{'}$

Step1

$j \leftarrow m i n \{|s|, |s'|\}$

Step 2

for each $i \in \{1,2, \dots, j\}$

Step 2.1

if $s [i] \neq s' [i]$ $Γ \leftarrow \{\}$ /*判断位置 $i$ 是否相同，创建TCP规则和TCP理论*/

Step 2.2

for each $φ \in Φ$ /*循环 $φ$ */

Step 2.2.1

if $((s, i) = C_{φ}), ((s', i) = C_{φ})$

$Γ \leftarrow Γ ⋃ \{φ^{0}\}$ /*判断序列在位置 $i$ 是否满足TCP规则*/

Step 2.2.2

return $F D O (Γ, s [i], s' [i])$ /*算法2*/

Step 3 return false

循环遍历找到序列第一个不同位置 $i$ ，创建TCP规则和TCP理论.通过验证位置 $i$ 处对象的偏好关系验证序列之间的偏好关系，最后输出占优序列.

占优对比算法通过序列和TCP理论，验证序列 $s 和 s'$ 之间的占优对比，将占优序列保存到 $T'$ 中.

算法4

占优对比算法（DS）

输入：一组序列 $T$ ，TCP理论 $Φ$

输出：占优序列 $T'$

Step 1

$T' \leftarrow T$ /*将序列 $T$ 复制到 $T'$ 中*/

Step 2

for each $s, s' \in \{T'\}$

Step 2.1

if $D S (Φ, s, s')$ $T' \leftarrow T' - \{s'\}$ /*算法3，判断位置 $i 处 s ≻ s'$ 从 $T'$ 删除 $s'$ */

Step 2.2

else $D S (Φ, s', s)$ $T' \leftarrow T' - \{s\}$ /*从 $T'$ 删除 $s$ */

Step 3

return $T'$

Step1将序列 $T$ 复制到 $T'$ 中，循环遍历属于 $T'$ 的 $s, s'$ .通过调用算法3返回的占优序列来占优对比，若 $s ≻ s'$ ，从 $T'$ 中删除非占优序列 $s'$ ，反之若 $s' ≻ s$ ，从 $T'$ 中删除 $s$ ，其他情况下不对 $T'$ 进行操作.

3.2　时间复杂性分析

算法1提取序列算法对象插入的成本为 $O (n l)$ ，其中 $l$ 为属性数.删除过期序列的成本为 $O (n k)$ ，其中 $k$ 为时间范围.因此算法1的复杂度为 $O (n l + n k)$ ，即 $O (n)$ .

算法2占优对象查找算法的时间复杂度为 $O (l m^{m})$ ，其中 $l$ 为属性数， $m$ 为偏好规则数.

算法3占优序列查找算法的时间复杂度为 $O (k l m^{m})$ ，其中 $k$ 为序列的最大长度.

算法4占优对比算法的时间复杂度为 $O (n^{2} k l m^{m})$ ，即 $O (n^{2} m^{m})$ ，其中， $n$ 为序列数， $m$ 为偏好规则数.

实例2 给出实例1的TCP理论和以下提取序列，用 $t_{1}, t_{2}, t_{3}, t_{4}, t_{5}$ 表示时刻1到时刻5.

t_{1} :

s_{1} = 〈(a b, 0, Q i)〉

s_{2} = 〈(a b, 0, Q i)〉

s_{3} = 〈(a b, 0, Q i)〉

将输入的序列对象添加到 $t_{1}$ 序列末尾.

$t_{2}$ ： $s_{1} = 〈(a b, 0, Q i), (a c, 1, Q i)〉$

s_{2} = 〈(a b, 0, Q i), (a c, 1, Q i)〉

s_{3} = 〈(a b, 0, Q i), (a b, 1, P i)〉

$t_{3}$ ： $s_{1} = 〈(a b, 0, Q i), (a c, 1, Q i), (a c, 1, Q i)〉$

s_{2} = 〈(a b, 0, Q i), (a c, 1, Q i), (a c, 1, Q i)〉

s_{3} = 〈(a b, 0, Q i), (a b, 1, P i), (a c, 1, Q i)〉

如果序列长度大于3，将删除序列的第一个元组.

$t_{4}$ ： $s_{1} = 〈(a c, 1, Q i), (a c, 1, Q i), (a d, 1, P i)〉$

s_{2} = 〈(a c, 1, Q i), (a c, 1, Q i), (a d, 1, P i)〉

s_{3} = 〈(a b, 1, P i), (a c, 1, Q i), (a d, 1, P i)〉

$t_{5}$ ： $s_{1} = 〈(a c, 1, Q i), (a d, 1, P i), (a d, 0, P i)〉$

s_{2} = 〈(a c, 1, Q i), (a d, 1, P i), (a c, 0, P i)〉

s_{3} = 〈(a c, 1, Q i), (a d, 1, P i), (a c, 0, P i)〉

在 $t_{5}$ 中提取序列运动员 $s_{1}$ 和 $s_{2}$ 的占优对比.

（1）在第三次迭代中，算法找到要比较的位置 $i = 3$ .

（2）循环扫描TCP，寻找在位置 $i = 3$ 处满足序列s₁和s₂的TCP规则.

（3）由 $φ_{2}$ 和 $φ_{3}$ 产生的偏好理论 $Γ$ 规则如下：

$φ_{2}^{0}$ ： $(H = 0) \to (L = a c) ≻ (L = a d)$

$φ_{3}^{0}$ ： $\to (M m = P i) ≻ (M m = Q i)$

（4）由占优对象查找算法，可以得到 $o^{+} = (a c, 0, P i)$ ， $o^{-} = (a d, 0, Q i)$ .占优查找算法的搜索树如图2所示.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 占优对象查找算法的搜索树

Fig.2 Search tree of the dominant object finding algorithm

（5）由占优序列查找算法可得序列 $s_{2} ≻ s_{1}$ .

（6）由占优对比算法可得 $T' = \{s_{2}\}$ .

4 实验

在合成模拟数据集和世界杯足球赛真实数据集上对提出的算法进行验证.合成数据集通过程序设置参数和变量值，按照合理性和可操作性准则生成.在合成数据集上进行测试的目的是评估算法处理数据的能力，在真实数据集上进行测试是为了评估算法的可应用性.处理器为Inter （R） Core （TM） i5⁃7000u CPU @ 2.5 GHz，RAM 4 GB，64位操作系统，使用Python语言.

4.1　在合成数据集上的实验结果

在合成数据集上的实验验证了合成参数和提取序列参数对EXT sequences与CQL equivalent算法的影响，测试在不同参数下算法的运行时间.算法采用对应的TCP规则对数据流提取序列，其运行时间受到属性维度的影响.算法生成tuple数由序列数决定，时间范围（RAN）和时间滑动间隔（SLI）决定对象的选择.合成数据集上的生成参数如表1所示，提取数据流序列的参数如表2所示.

表1 合成数据集的生成参数

Table 1 Generation parameters of synthetic dataset

参数	变量	默认值
属性数量	8,10,12,14,16	10
序列数量	4,8,16,24,32	8

新窗口打开| 下载CSV

表2 从合成数据集提取数据流序列的参数

Table 2 Parameters for extracting data stream sequences from synthetic datasets

参数	变量	默认值
时间范围(s)	10,20,40,60,80,100	20
时间滑动间隔(s)	1,10,20,30,40	1

新窗口打开| 下载CSV

根据TCP⁃rules提取数据流序列，序列的属性标识符如下：

\begin{array}{l} A_{1} : φ_{u} = \\ F i r s t \land Q (A_{3}) \to Q_{A_{2}}^{+} ≻ Q_{A_{2}}^{-} [A_{4}, A_{5}] \end{array}

\begin{array}{l} φ_{v} = P r e v Q (A_{3}) \land S o m e P r e v (A_{4}) \land A l l P r e v Q (A_{5}) \land \\ Q (A_{3}) \to Q_{A_{2}}^{+} ≻ Q_{A_{2}}^{-} [A_{4}, A_{5}] \end{array}

实验结果如图3所示.

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 合成数据集中使用不同参数时两种算法运行时间的对比

(a)属性数不同；(b)序列数不同；（c）时间范围不同；（d）滑动间隔不同；其余参数均采用默认值

Fig.3 Running time of two algorithms with different parameters on synthetic dataset

第一组实验测试生成属性的数量对算法的影响，属性数量8~16（其他参数不变），如图3a所示.由图可见：（1）即使生成的属性数很少，EXT sequences也优于CQL equivalent；（2）随着属性数量的增加，EXT sequences和CQL equivalent的运行时间都在增加，但CQL equivalent的增幅较大.

第二组实验测试序列数对算法的影响，序列数量4~32，如图3b所示.由图可见：（1）随着序列数量的增加，提取序列算法的性能优于CQL equivalent；（2）随着序列数量的增加，提取序列算法处理tuple的数量也增加.

第三组实验测试时间范围对提取序列算法的影响，时间范围10~100 s，如图3c所示.由图可见，当RAN不断增加，提取序列算法的性能优于CQL equivalent.

第四组实验测试时间滑动间隔对算法的影响，时间滑动间隔1~40 s，如图3d所示.由图可见：（1）EXT sequences的性能优于CQL equivalent；（2）随着时间滑动间隔的增大，两个算法的运行时间都在减少.

四组实验结果证明，随着属性数、序列数、时间范围以及滑动时间间隔的增加，本文的提取序列算法对偏好数据流中提取序列的效率更高，用时更短.

4.2　在真实数据集上的实验结果

在世界杯足球赛数据集上采用TCP规则，对数据流进行序列提取，分析EXT sequences与CQL equivalent算法的时耗.真实数据集的参数如表3所示，提取数据流序列的参数如表4所示.

表3 真实数据集的参数

Table 3 Parameters of real dataset

属性	变量	时刻
比赛队伍	32	32
比赛场次	64	62
运动员	736	736
动作	167081	2621
移动方向	130607	2040
场上位置	137621	2150

新窗口打开| 下载CSV

表4 从真实数据集提取数据流序列的参数

Table 4 Parameters for extracting data stream sequences from real datasets

参数	变量	默认值
时间范围 (s)	6,12,18,24,30	24
时间滑动间隔 (s)	1,3,6,9,12	1

新窗口打开| 下载CSV

实验采用以下的TCP规则：

\begin{array}{l} φ_{1} : P r e (L = a b) \land (H = 1) \to \\ (L = a c) ≻ (L = a b) [M m] \end{array}

\begin{array}{l} φ_{2} : A l l P r e (H = 1) \land (H = 0) \land \\ P r e (L = a d) \to (L = a c) ≻ (L = a d) \end{array}

φ_{3} : \to (M m = P i) ≻ (M m = Q i)

第五组实验测试改变时间范围RAN及滑动时间间隔SLI对提取序列算法性能的影响，如图4所示.由图可见，随着RAN和SLI的不断增加，提取序列算法的性能优于CQL equivalent.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 真实数据集上使用不同参数时两种算法运行时间的对比

(a)时间范围不同（滑动间隔为1 s）；

(b)滑动间隔不同（时间范围为24 s）

Fig.4 Running time of two algorithms with different parameters on real dataset

为了测试RAN及SLI参数对算法的影响，选用RAN和SLI进行实验，如表5所示，实验结果如图5所示.

表5 真实数据参数

Table 5 Real data parameters

参数	变量	默认值
时间范围(s)	5,10,20,40,80,160	40
时间滑动间隔(s)	1,3,6,9,12	1

新窗口打开| 下载CSV

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 在真实数据集上使用不同参数的连续查询算法运行时间的对比

(a)时间范围不同（滑动间隔为1 s）；

(b)滑动间隔不同（时间范围为24 s）

Fig.5 Running time of consecutive query algorithms with different parameters in real dataset

由图可见：（1）Dominant Contrast算法比其他算法的性能更好；（2）算法的运行时间随着时间范围的扩大而增加，但是占优算法运行时间增长的幅度最小；（3）随着时间滑动间隔的增加，产生的新元组会覆盖过期序列元组，序列间占优对比的次数减少，占优查询算法的运行时间减少.原因在于：（1）占优算法处理按时间条件提取数据流中的序列，不需要多次扫描窗口；（2）Partition和Incpartition算法对时间滑动参数不敏感；（3）min Top⁃k算法在时间范围不变而增加时间滑动间隔时，候选集合的访问次数也在不断地增加，候选对象数量变少.

综上，占优对比算法和Partition，Incpartition，min Top⁃k算法相比，表现最优.

5 结论

本文提出一种加入时间索引对数据流提取序列并对所得序列进行占优查询的方法，扩展了CQL，对数据流上的数据进行偏好查询有进一步了解.在不同的数据集上对提出的Dominant Contrast算法和其他查询算法进行了实验对比，实验结果证明，提出的提取序列算法和占优查找算法，运行时间比其他算法更少，性能更优，得到了更精确的查询结果.

未来的研究方向：（1）完善提取数据流序列算法和占优对比算法，提高偏好查询效率；（2）获取时间条件偏好的属性优先级，生成一致性排序算法，并进行验证.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Doyle

Prospects for preferences

Computational Intelligence，2004，20(2)：111-136.