一种基于整数线性规划和多目标优化的渐进式时间线可视布局方法

摘要

一种基于数学优化模型的渐进式时间线布局方法，包括：(1)获取某一时间数据，或者对非时间数据进行分析代入时间，得到时间演化集，对时间演化集数据进行表示；(2)在时间演化集中将原始数据固定，并插入新的数据点，通过目标函数确定新点的顺序，并尽可能和谐；(3)设计优化目标函数，对新点的坐标进行缩放并计算连续的坐标，设计约束条件对坐标的位置进行约束；(4)利用线性技术处理模型的目标函数以适应Gurobi编程接口，最后通过Gurobi求解模型。本发明解决了视觉上的负担和混乱的问题，实现了一种时间演化集的可视布局方案。

说明书

技术领域

本发明涉及一种基于整数线性规划和多目标优化的渐进式时间线可视布局方法。

背景技术

随着信息化时代的发展，人类的生产活动会产生大量的数据，其中有部分数据随时间相关，即随时间演化的数据。为了分析和探索时间演化集数据，获取动态高维度信息中的关键信息，可以使用数据投影模式对时间演化集进行可视分析。数据投影是数据可视化中广泛使用的技术，可以降低数据维度、细化特征和汇总数据信息。而散点图是在数据降维后最常用的表示数据分布的可视化形式。

时间线布局算法通过时间推进对散点图的元素布局进行更新，是一种有效处理时间演化集的集合元素布局的算法。近年来，许多研究都涉及到时间演化集数据，比如在行人重识别中的识别模型将提供符合用户查询的人员排名列表，受限于可扩展性，用户只关注Top K数据点。此外，由于数据和用户查询的变化，数据点的集合会随着时间的推移而发生巨大的变化。

时间线是一种可视化形式，用于表示垂直或水平方向的动态数据。许多研究人员利用基于时间线的布局来可视化事件的进展和故事线布局。故事线布局作为一种典型的基于时间线的布局，引起了很多研究者的关注，他们的大部分工作都从美学角度优化了故事线的布局。

基于时间线的可视化表示时间演化集时，能有效地显示集合中数据在水平方向上的时变信息，但是大量的时间演化集数据用可视化形式表现出来的时候会造成视觉上的负担和混乱。

发明内容

本发明要克服现有技术的上述缺点，提出一种基于整数线性规划和多目标优化的渐进式时间线可视布局方法，用于在当前布局的时间戳插入新数据时，确定插入的数据集合中元素的顺序和坐标，并设计坐标缩放的目标函数从美学方面最小化曲线摆动和高度。

为了解决上述技术问题，本发明提供如下的技术方案：

一种基于整数线性规划和多目标优化的渐进式时间线可视布局方法，所述方法包括以下步骤：

1)数据描述；本发明将时间演化集表示为S

(1-1)点的坐标；本发明在布局算法中对S

(1-2)渐近式时间线可视布局；本发明在布局S

2)确定S

在模型(1)中，目标函数包含一个指示函数I{·}，这意味着当且仅当指标函数的条件为真时，该函数取1。在该模型中，

模型(1)中的约束旨在保持

模型(1)是非线性规划模型，具有非线性目标函数和线性约束。考虑到模型(1)中的目标函数比较繁琐，本发明利用线性化技术和其他决策变量来简化模型，并通过Gurobi求解器对其进行求解。当使用Gurobi接口编程时，本发明利用线性化技术帮助处理指示函数。例如，为了处理目标函数中的绝对值，本发明定义了两个0-1的决策变量p

其中式(2)是一个线性函数，避免了式(1)中的繁琐形式，但是需要添加新的约束来描述

其中M表示任意选取的足够大的正数。式(3)结合了

本发明结合新的约束条件和新的目标函数，得到了一个新的非线性规划模型，并通过Gurobi接口求解。

3)缩放坐标；本发明在确定S

(3-1)三个优化目标函数；分别是比例目标函数、边界目标函数、摆动目标函数。

比例目标函数是离散优化中目标函数的扩展。给定两个点i和j，它们之间的坐标距离与特征距离的比值表示为

其中

边界目标函数旨在避免点坐标范围过大。它通过式(6)目标函数使点的坐标范围更接近：

其中max{y

摆动目标函数旨在避免

其中ω

此外，本发明考虑这几个约束，包括间隙约束、边界约束和顺序约束。

(3-2)三个约束；分别是间隙约束、边界约束、顺序约束。

边界目标函数使点的距离更近。为了避免过近的点重叠造成的视觉混乱和干扰，本发明建立间隙约束来限制点之间的最小距离，表示如下：

其中D

边界约束旨在将点布局在矩形画布的高度上，表示如下：

顺序约束使用模型(1)的结果。本发明利用顺序约束通过

其中上述约束中的

(3-3)多目标规划模型；将目标函数和约束结合为一个多目标规划模型，由于求解多目标模型的复杂性，本发明使用加权线性组合来简化这三个目标函数，如下所示：

minα

其中α

f

其中z

本发明利用线性技术处理模型的目标函数以适应Gurobi编程接口，然后通过Gurobi求解模型。

优选地，步骤(3-3)中经过多次测试，α

本发明的技术构思是：通过时间演化集插入新的数据点，将数据点赋予顺序和坐标属性。为了使新点的距离和原始集合中的距离比例尽可能协调，设计非线性目标函数和模型来确定顺序，利用线性化技术和其他决策变量来简化模型后通过Gurobi求解器进行求解。接着从坐标缩放角度结合多目标优化和约束条件，得到一个新的非线性规划模型，并通过Gurobi接口进行求解。

本发明的优点是：渐进式时间线可视布局方法，用基于整数线性规划的数学模型表示了一种对时间线布局中数据点求解顺序的高效方法，并设计坐标缩放目标函数和约束条件对大量的时间数据从美学方面最小化曲线摆动和高度，一定程度上解决了视觉上的负担和混乱的问题，实现了一种时间演化集的可视布局方案。

附图说明

图1为本发明的渐进式时间线可视布局流程图；

图2为本发明的在布局S

图3为本发明的在布局S

图4为本发明的在布局S

具体实施方案

下面结合附图1-4对本发明作进一步说明；

本实施例是应用本发明的一种基于整数线性规划和多目标优化的渐进式时间线可视布局方法的公园重点区域的人流数据收集方法，包括以下步骤：

1)如图1所示，方案实施过程的主要内容包括获取数据库中的数据，将相关的时间数据或非时间数据处理为时间演化集，然后确定当前时间插入数据点的顺序，确定顺序后进行坐标缩放操作，确定当前时间数据点的坐标。

本发明将时间演化集表示为S

具体为：获取公园重点区域到访的人群数据，按一定时间段分片(如按天分片)，得到每一时间段到访重点区域的人群数据，作为时间演化集。

随着时间的变化，当公园重点区域到访的人群数据进行更新，如获得了某日新采集到的数据时，采用本发明提供的渐进式可视布局方法，不需要改变过去时段的时间线布局中人群点的顺序和坐标，确定当前时段的人群点的顺序和坐标，以进行渐进式的可式布局。

(1-1)本发明在布局算法中对S

(1-2)本发明在布局S

在公园重点区域到访的人群数据中，表现为：新增的数据为S

2)在离散布局中，本发明首先在

在模型(1)中，目标函数包含一个指示函数I{·}，这意味着当且仅当指标函数的条件为真时，该函数取1。在该模型中，

模型(1)中的约束旨在保持

模型(1)是非线性规划模型，具有非线性目标函数和线性约束。考虑到模型(1)中的目标函数比较繁琐，本发明利用线性化技术和其他决策变量来简化模型，并通过Gurobi求解器对其进行求解。当使用Gurobi接口编程时，本发明利用线性化技术帮助处理指示函数。例如，为了处理目标函数中的绝对值，本发明定义了两个0-1的决策变量p

其中式(2)是一个线性函数，避免了式(1)中的繁琐形式，但是需要添加新的约束来描述

p

x

其中M表示任意选取的足够大的正数。式(3)结合了

本发明结合新的约束条件和新的目标函数，得到了一个新的非线性规划模型，并通过Gurobi接口求解。

3)在确定S

(3-1)使用比例目标函数、边界目标函数、摆动目标函数进行坐标优化。

比例目标函数是离散优化中目标函数的扩展。给定两个点i和j，它们之间的坐标距离与特征距离的比值表示为

其中

边界目标函数旨在避免点坐标范围过大。它通过式(6)目标函数使点的坐标范围更接近：

其中max{y

摆动目标函数旨在避免

其中ω

(3-2)使用间隙约束、边界约束、顺序约束对坐标进行约束。

边界目标函数使点的距离更近。为了避免过近的点重叠造成的视觉混乱和干扰，本发明建立间隙约束来限制点之间的最小距离，表示如下：

其中D

边界约束旨在将点布局在矩形画布的高度上，表示如下：

顺序约束使用模型(1)的结果。本发明利用顺序约束通过

其中上述约束中的

(3-3)将目标函数和约束结合为一个多目标规划模型，由于求解多目标模型的复杂性，本发明使用加权线性组合来简化这三个目标函数，如下所示：

minα

其中α

f

其中z

本发明利用线性化技术处理模型的目标函数以适应Gurobi编程接口，然后通过Gurobi求解模型。

(4)得到数据点的坐标后，通过可视化工具包D3.js在时间线可视化中绘制新增集合的元素。时间线中不同集合元素的对比可以辅助工作人员分析，根据对比集合元素的变化，来辅助公园管理人员进行决策，从而加强对重点区域的管理。并且随着时间的变化，当公园重点区域到访人群数据发生更新(即新增了一个时段的数据)时，应用本发明的方法确定新增时段的人群点的坐标位置，对时间线可视化进行更新，可以帮助工作人员实时观测公园访客差异(例如流量变化)，帮助公园工作人员引导访客。