变熵画像:一种数量级压缩物端数据的多粒度信息模型

朝 鲁 彭晓晖 徐志伟

1(中国科学院计算技术研究所 北京 100190)2(中国科学院大学 北京 100049)3 (智能处理器研究中心(中国科学院计算技术研究所) 北京 100190) (chaolu@ict.ac.cn)

Fig. 1 From computation offloading to data modelizing图1 从计算下沉到数据模型化

近年来，数据的爆发式增长给云计算模式带来了计算负载、网络带宽、响应延迟等一系列巨大的挑战.据IDC预测，全球每年产生的数据量将达到160泽字节(160 ZB),而其中由边缘设备和终端设备产生的数据大约占据78%[1].利用海量物联网设备分担庞大的计算需求，催生了边缘计算[2-3]、雾计算[4]、物端计算[5-6]等新型计算模式和体系架构.作为云计算的重要补充，它们的共同理念是强调计算应尽可能地分散在靠近用户和数据源的边缘或端上，从而针对计算、通信、存储和功耗等硬件约束优化系统任务分配，改善性能和降低功耗.然而这类模式并未致力于解决以下2个重要问题：1)数据存储位置决定了计算任务能够靠近网络边缘的最短距离，但网络边缘设备的存储、计算资源以及通信能力相对受限，无法有效存储和快速传输这些从物理世界感知到的原始数据，导致计算无法深度下沉;2)不同计算场景需要获取不同粒度的信息，在原始数据级实现多粒度查询和存储引入了昂贵的计算冗余和空间开销.如图1所示，在支持多粒度数据需求的情况下数量级地压缩感知数据，为资源相对受限环境的应用提供统一数据抽象支持，是这类新型计算模式能够进一步演化的关键挑战之一.

我们将物联网环境中面向物理世界并具备与物理世界交互功能的设备称为物端设备，例如传感器设备、控制器设备和中小型智能设备.在其上采集或控制的数据称为物端数据，例如温度、能耗和事件次数.物端设备和物端数据构成了自然界最根本的数据生产源，其专有的内在特征也是我们设计新型数据抽象的关键动机.由物端设备、通信设备、计算机及其周围环境组成的具有一定物理或概念界限的计算系统称为物端控域.例如，智能家居、楼宇、以人为中心的可穿戴设备组成的系统等.物端控域的首要目标是对域内产生的事件快速响应，同时降低系统处理计算任务的整体能耗.在资源相对受限环境下，高效且快速地为不同计算任务提供其所需的不同粒度数据是实现这个目标的重要途径.下面我们将从物端数据和物端设备2方面，挖掘和分析物端控域中这种多粒度信息模型抽象相对于原始数据形式的约束变化.

从物端数据角度看，物端数据具有3个特征：1)数据可广泛地用时间序列的形式表征.正如同NoSQL数据库领域使用键值对方式描述一切数据一样，时间戳是天然标识物端数据的“键”，而“值”是物端数据所蕴含的数值属性.2)物理世界数据偏离正常值的频率是稀疏的.根据环境、能耗和人类行为活动等领域相关实证研究结果[7-10]，来源自然界的物端数据相对于期望的偏离程度通常符合长尾分布，即异常总是少见的，周期化数据却是常态.如图2所示，大部分偏离程度低的数据(常态情况)在长尾部分，极少部分偏离程度高的数据(异常情况)在长尾头部.3)本文提出的一个假说，数据偏离程度导致了观测者对数据的注意力和需求程度不同，可简称为注意力差别假说.具体来说，偏离程度小的常态数据占据大量的比例，因此带来的信息量小，仅需要用户少量的注意力，例如呈周期性变化的室内温度，用户多查看其周期走势；偏离程度大的异常数据占据少量比例，带来的信息量大，需要用户较多的注意力.例如因为暖气损坏导致的室内温度急剧降低，设备应及时通知用户或报警.这里的“温度急剧降低”具有大量的信息，需要应用或用户更多的注意力.该假说在其他领域也有许多应用场景，例如图片文件的前景轮廓能够吸引更多的注意力，压缩算法很少牺牲这部分画面的质量，而更多牺牲容易被人忽略背景部分画质.类似的情形也发生在音频压缩情景中.这一假说也可以从功能感知[11]理论框架中获得支持：舍弃不重要的信息，并不影响应用对数据内部隐藏的重要知识的提取.

Fig. 2 The long-tailed distribution of deviations over normal values with data on things图2 物端数据偏差正常值程度的长尾分布示意图

总体来说，物端数据第3个特征的注意力差别导致的用户需求不同体现在3点：

1) 数据质量.注意力聚焦的数据需要较高的精确度，需要准确描述数据周围的形态；反之精确度可以降低，少量轮廓数据便可以满足数据分析需求.

2) 数据时效.注意力聚焦的数据可能需要较高的时效性.这类数据通常代表异常事件，需要及时更新数据，并通知上层应用；反之时效可以放宽，甚至存入离线数据仓库备用.

3) 数据隐私.需要注意力聚焦的数据可能具有较高的价值，如果数据未经脱敏处理容易泄露用户或环境的指纹特征；反之数据信息价值较低，不易泄露指纹特征.

从物端设备角度看，多数物端设备存在低容量、低性能、低能耗、低带宽和高延迟等诸多硬件资源约束.因此，当物端设备接入互联网提供Web服务时，其数据存储和传输服务存在3方面挑战：

1) 空间占用.大多数物端设备的内存和外存空间从千字节到兆字节级不等，仅能提供非常有限的存储容量，而提供Web服务需要存储大量历史数据，因此，对物端数据进行有效压缩是数据存储的关键.

2) 传输尺寸.物端设备经常采用的IEEE 802.15.4、蓝牙等低功耗传输技术提供的网络带宽极为有限，在物端节点之间传输大量的数据会造成高延迟和高能耗.因此节点间大量传输数据时，需要压缩其传输尺寸.

3) 查询速度.如何在性能相对较低的物端设备上进行快速数据查询，需要新的快速索引机制.

综上所述，我们围绕引言介绍的物端数据角度的3个特征来解决物端设备角度的3个挑战，引入时间序列表示、最大误差保证的有损压缩以及长尾分布下的多粒度信息这3个约束，使得物端数据特征和物端设备资源限制匹配.本文首次提出了满足以上约束的一种多粒度信息模型抽象理论——变熵画像(variant entropy profile, VEP).其含义是将原始数据向信息层次跃升，如同画像一样高度概要地刻画数据关键特征，同时满足上层应用多样化需求，允许变化熵值的信息进行存储或传输.同时设计并实现了一种基于时间序列分解原理，且满足VEP理论的物端数据存储原型——TSR-VEP.通过使用马萨诸塞大学发布的Smart*真实楼宇能耗数据集和相关数据挖掘应用进行测试的结果表明，TSR-VEP实现了多粒度信息存储和查询，可达到约20倍数据压缩率以及平均4%的观测结果误差率，初步验证了注意力差别假说，以一种抽象方式统一解决了新型物联网计算模型遇到的2类缺陷问题.

1 相关工作

围绕物端信息模型的3个约束，本节将依次介绍相关领域的研究工作：

1) 时间序列存储

时间序列存储是物联网数据存储领域的重要研究内容.这些存储技术大多通过关系型数据和NoSQL数据库来实现，并针对时间序列相关性和频繁写的特征，在压缩效率、索引、执行方式、存储规模和存储结构等方面进行优化，如InfluxDB[12]，OpenTSDB[13]等.这些时间序列数据库在云计算环境中性能优异、可扩展性强，但未针对存在明显资源约束的物端设备如家庭智能网关、嵌入式设备及传感器设备等进行优化设计.其较大的存储占用、I/O密集的特点很难适合物端计算环境.同时，大部分时间序列数据都存在明显的冷热数据分离情况，占用了大量的存储空间，而这类数据库无法从知识理解层次解决这个问题.

2) 有损数据压缩

物端数据偏离正常值的频率符合长尾分布，时间序列数据在时域和值域构成的空间中具有较强的周期性和稀疏性.因此，在压缩感知等相关领域中，大量的稀疏化技术被应用.本文将这类稀疏化技术按照是否可以通过时间进行索引分为2类：不可时间索引的和可时间索引的数据稀疏化技术.不可时间索引的稀疏化技术通常仅针对数据的值域空间进行压缩，丢弃了数据内在相关性，因此压缩还原结果仅能重构值域空间的分布.这类方法包括PCA[14]、大量的神经网络算法如DNN[15]等.另外循环神经网络(RNN)[16]可通过自回归方式进行一定时域相关性建模，但这种方式依然不支持索引.而可时间索引的稀疏化技术同时保留了时域和值域空间数据之间的相关性，因此能够重构有序时间序列.这类方法包括神经网络分解(ND)[17]、快速傅里叶变换(FFT)[18]、离散余弦变换(DCT)[19]、离散小波变换(DWT)[20]等.此类稀疏化技术，具备较好的数据拟合和过滤特性，能有效地去除噪声和异常，实现一定程度的周期化预测.但它们通常利用平均化或比例化的度量进行损失估计以防止出现过拟合情况，如平均绝对误差(MAE)、均方根误差(RMSE)等，无法保证单个样本点的误差范围.因此，该类方法虽然有效体现数据的整体趋势及周期性，但是不适用于有较强精度需求的场景.

另一类有损压缩方法为了支持任意长度时间序列数据的在线学习压缩，多采用了分段线性逼近方法，并限制了误差范围[21].由于分段表示采用了线性回归等多种技术，该方法具备有限的预测和快速查询能力.近年来的一些相关工作利用无穷范式距离L∞(即一组绝对值误差的最大值)约束误差，使得还原数据的误差更容易被人类理解和使用.如分段常数近似方法(PMR-midrange)[22]利用平均值和中位数进行逐段逼近满足无穷范式距离，具有最高的计算效率，但数据的局部特征基本消失.为了进一步利用局部特征进行压缩，卡尔斯鲁厄大学提出分段压缩算法[23]利用不同次数多项式进行逐段逼近，在一些波形数据上取得了良好的效果.自适应逼近方法[24]与多模型逼近方法[25]采用了线性函数与非线性核函数的混合方式进行逐段逼近，能够进一步表达非线性区间，但该方式也牺牲了性能.在这些方法中，卡尔斯鲁厄大学的分段压缩算法在性能和压缩率上表现极佳，简洁的算法也适合执行在物端设备环境.然而由于它缺乏对于时间序列波形的整体理解，在针对功耗分析等较高精确度要求的场景下，压缩率急剧下降.受到真实问题的时间序列建模和数据挖掘工作的启发，近来也有研究人员借鉴较为成熟的有损失季节性-趋势分解方式(STL)[26]，通过去除掉时间序列里隐藏的周期和趋势成分，获得更高效的分段近似表达.昆士兰大学提出一种基于STL分解的最大误差保证方法[27]，通过STL分解工具消除了大量稀疏成分，并用常数分段近似和哈夫曼编码进行参数压缩，该工作在有较强周期性的数据集上取得了可观的压缩效果.但在周期性较差的真实数据集上，单一的STL周期成分估计方法不利于高效压缩.

3) 多粒度信息数据挖掘

现阶段多粒度数据表达的尝试主要有2类：计算输出导致的数据多粒度和视图导致的数据多粒度.第1种方法使用不同的计算函数生成多粒度信息，例如边缘计算的智能摄像头场景中使用脸部特征向量代替完整图像数据传输实现人脸识别工作[28]、在智能插排场景中使用神经网络的Softmax层数据代替电流波形数据的传输[29],这类工作的特点是需要开发者针对特定的应用场景进行数据粒度的定制，数据难以被其他应用共享.第2种方法通常是多维数据库利用视图变换方法，形成不同时间、空间和关系粒度的信息块查询加速，如DataCube[30]，STREAMCUBE[31]等，这类方法本质上改善了数据的存储和查询方式，但在维度较为单一的物端数据上难以发挥优化效果.

综上所述，本文将结合这3方面相关工作的优势进行变熵画像的构建.

2 变熵画像原语与架构设计

2.1 变熵画像形式化表达

本节将依照第1节约定的3个约束，给出惊异度(surprisal)和变熵画像的定义，并确定其具备的性质.

定义1. 惊异度.对于时间点个数为N的时间序列TS={(t1,v1),(t2,v2),…,(tN,vN)}，使用时间序列预测方法进行压缩编码和重构得到TS′，则在值的绝对残差距离Δv构成的分布Γ上，称自信息量Ii=-log(PΓ(Δvi))为时刻i的惊异度.

定义2. 变熵画像.对于时间点个数为N的时间序列TS={(t1,v1),(t2,v2),…,(tN,vN)}，给定阶数M，各阶误差集ε={εm|0≤m

(1)

其中，映射规则φm是时间序列TS中下标集合的一个子集，TSm={(ti,vi),i∈φm}，并同时满足约束:

|fm(ti)-vi|≤εm,∀i∈φm,

(2)

Ii

(3)

1) 有序性.由式(3)可得，高阶VEP总是具有比低阶VEP更高的惊异度.

2) 有界性.由式(2)可得，各阶VEP还原重构的时间序列满足各阶最大限定误差.

4) 稀疏性.根据第1节的物端数据稀疏性假设，经过压缩的函数集参数空间显著小于原始数据集大小，即‖f‖≪|TS|.

2.2 基本原语与接口设计

满足基础约束的VEP可有多种实现，为了能够无缝地在不同节点和环境进行统一传输和存储，所有的VEP实现对外都需要具有相同的数据封装和操作接口.

VEP采用可移动配置mVEP作为统一的存储和传输载体.mVEP既可用来描述全新的VEP参数配置，也可用来描述已经填充数据的VEP序列化实例.VEP在设备内或节点间进行复制或迁移时，均需要完成VEP和mVEP的转换.

我们在此定义VEP的最简操作集合，包括CREATE，APPEND,FORK，QUERY,SUBSCRIBE这5个原语，其定义和功能分别如下所述：

1) 创建

接口声明：CREATE(mVEP).

输入：mVEP;

输出：VEP实例.

接口描述：根据mVEP生成满足相应条件的VEP实例.其作用是提取mVEP参数创建新的VEP，或从mVEP中恢复已有VEP.

2) 追加

接口声明：APPEND(T,V).

输入：时间戳T、数值V;

输出：无.

3) 分叉

接口声明：FORK(filter).

输入：过滤参数filter；

输出：mVEP.

接口描述：根据过滤参数filter对VEP进行时域、值域或阶粒度的拆分与复制，并形成包含VEP序列化信息的mVEP.该接口作用有2点：①用于获得不同尺寸和粒度的mVEP进行传输；②用于裁剪VEP自身参数集.

4) 查询

接口声明：QUERY(T).

输入：时间T;

输出：值V、[rank].

接口描述：查询指定时刻T的值V，并返回对应V所处的阶数.

5) 订阅

接口声明：SUBSCRIBE(filter,callback_func).

输入：过滤条件filter、待注册的订阅回调函数callback_func(T,V,rank);

输出：订阅有效时间.

接口描述：对新增数据进行订阅操作，符合过滤参数的结果会通过callback_func返回.例如可通过filter仅订阅高阶VEP,以异步的方式推送高惊异度数据给订阅者.

通过5个操作原语的描述，我们已将VEP由数学模型转换为可访问信息资源，并部分具备了存储单元的增添、读取和删除操作能力.如表1所示，我们将VEP的操作原语与SQL和HTTP的CRUD方法进行了对比，VEP作为在线时间序列存储模型，不支持修改操作，但其余的增、读和删操作都可以得到有效支持，这使得VEP可轻易被封装为更高层的存储表达形式，如HTTP RESTful资源.

Table 1 Comparison of VEP Primitive Operators andCRUD Methods

2.3 趋势-稀疏-回归变熵画像(TSR-VEP)

根据VEP定义，本节将给出VEP的一种具体实现，即趋势-稀疏-回归 (TSR-VEP)变熵画像.TSR-VEP在满足VEP约束的前提下借鉴了STL分解思想，进一步将时间序列分解为趋势成分(TC)、稀疏成分(SC)以及残差回归成分(RC)，并表示成P=(f,ε,φ)的三元组.如图3所示，对应的f可利用TSR表示为

(4)

其中，趋势成分为fTC(ti)，是对整个时间序列粗粒度走势的近似.稀疏成分为

(5)

是第k段周期特征的近似表示，共K段.残差回归成分为

(6)

是第m阶有最大误差保证的残差近似，也是数据异常程度的体现.

Fig. 3 A demo of data decomposition图3 数据分解示意图

(7)

这表明φ始终优先映射高阶VEP，而较低阶VEP的映射需要减去比其高阶的所有映射.因此，当自顶向下建立fRCm(t)函数时，可借用该函数的定义域构建φ.

由于φm在TSR-VEP实现中被隐式定义在函数定义域中，我们需要引入一个新的参数指示φm的配置.设比率τm=|TSm||TS|表示各阶数据的拆分比例，我们即可按照图3所示方法将排序后残差项Δv进行比例拆分依次确定φm.通常情况下，根据注意力差别假说，应满足τm>τm+1，εm>εm+1.另外，我们利用τS和εS将稀疏化组件的构建目标约束为：相对于原始时间序列，升序排列的τS百分位重构误差不应超过εS.

τm与εm的配置策略较为灵活，本文在此提出等熵拆分策略作为一种可选策略.我们希望各阶VEP含有相似熵值，即不同粒度的VEP可包含相近的信息不确定度，从而进一步符合注意力差别假说.根据定义1可建立约束如下：

HΓ(ΔVm)=HΓ(ΔVm+1)，

(8)

(9)

(10)

根据注意力差别假说，我们引入非负递减的惊异度-精度函数I=γ(ε)表示两者关系，得出：

τmγ(εm)=τm+1γ(εm+1).

(11)

例如我们可定义非负递减指数函数I=αe-β ε，其中α>0,β>0，并最终获得两者关系如下：

(12)

2.4 TSR-VEP计算组件

TSR-VEP在架构上主要由4个组件组成，分别是控制器(Controller)、评估器(Estimator)、稀疏化组件(Sparse Component，简写为S)和回归组件(Regress Component，简写为R)，这4个组件作用分别如下：

1) 控制器.维护VEP所有原语的解析和处理、数据缓存和在线窗口缓冲区的控制，及协调创建其他3个组件.

2) 评估器.利用输入的样本数据和用户预定义初始参数进行参数估计与校正，以满足用户对于空间占用和精度控制的需求.

3) 稀疏化组件.利用可时间索引的稀疏化算法将原始时间序列数据进行稀疏化表达，从而获得具有一定周期性预测能力的稀疏压缩编码.由于数据存在数值和频率随机性，我们无法保证单一的稀疏编码能够预测任意长度的数据集，因此我们采用了分段的稀疏编码对不同时间片段进行压缩.同时为了降低稀疏参数所占用的空间，系统将在保证稀疏化函数误差范围的前提下，自动合并相同或相似的稀疏编码段.该组件对外提供的方法为添加数据Append和查询数据Query.目前可选用的稀疏化算法有神经分解网络ND[17]，FFT[18]，DCT-II[19]等，其中，ND方法通过含有正弦周期性激活函数的神经网络进行时间序列表征学习，FFT和DCT-II分别通过选取能量最大的一组复数频域和实数频域方式进行稀疏化表征.如表 2所示，我们在相同数据集和相同误差要求下进行了简单的选型分析.

Table 2 The Selection Analysis of Sparse Components表2 稀疏化组件选型分析

结果显示，神经网络分解的ND方法由于能够精确学习识别时间序列信号的固有频率，具有最高的压缩率和预测能力；而其余频域变换方式仅能够按基波频率的倍数展开，难以提取时间序列信号中真实固有频率的组合.通过测试发现，目前ND的学习训练时间过长，即使在有GPU加速的情况下，也不能保证任何类型的数据输入都能在预计迭代次数内完成收敛.虽然该方法具有极大的优化潜力，但过长的训练时间和无法预计的收敛特性，使其暂时不适用于物端设备.DCT-II的余弦变换方式相对FFT方法具有更紧凑的能量分布，节省了一半的虚数域参数空间.因此，本文最终选择了相对可以接受的DCT-II方法构建稀疏化组件.

4) 回归组件.该组件利用能够保证误差范围的分段逼近算法拟合残差成分和趋势成分.本文基于卡尔斯鲁厄大学提出分段压缩算法[23]进行了部分修改，新增了低参数空间占用、动态优化数据精度和快速在线数据添加等特性，但并未影响到该算法的核心内容.由于篇幅所限制，本文不再赘述这些改进的具体内容.该组件对外提供的方法为添加数据Append和查询数据Query.

2.5 变熵画像核心算法

本节将讨论TSR-VEP的核心实现算法，包括参数调整、数据添加和数据查询这3部分.

1) 参数调整

评估器的参数计算是实现数据多粒度分阶的依据，虽然用户和系统会给定组件的部分缺省参数配置，我们仍需要在运行时为不同数据模式动态校正参数.在TSR-VEP具体实现中，用户必须给出的参数为分阶比率的集合τ、稀疏化组件的εS和τS、最高阶的误差限制εM-1，而其余阶误差参数将通过样本学习方式进行调整.具体来说，我们将利用式(11)确定最大压缩率目标下的各阶ε误差.通过对样本残差距离的排序，利用τ确定各阶残差的边界值，并提供Cast和Slice方法将数据添加过程中产生的残差按照边界值投入到不同阶的残差回归组件中.

2) 数据添加

在物端计算环境中，数据的添加需要在线进行，为了兼顾批处理性能优化和低查询延迟的目标，其采用基于窗口滑动缓冲区的流处理算法.如图4所示，在线添加新数据T,V时，首先数据会被存入缓冲区，然后依次滑动4类窗口，分别实现快速缓冲、趋势成分、稀疏成分和残差成分的处理.在这些窗口滑动过程中，执行流程根据参数的初始状态情况分为2个阶段：参数学习阶段和参数就绪阶段.在参数学习阶段，各组件均采用用户预设值和缺省值，并持续收集数据样本填入评估器.当评估器收集到足够数据后，进行参数估计和各组件的参数校正，执行流程随后进入参数就绪阶段.

算法1. VEP拆分与添加.

需要已初始化的buffer缓冲区、R组件、S组件；

FunctionFeedTrend(T,V)

②Rtrend.Append()；

③buffer.MoveWindow(“trend”).

FunctionFeedSparse(T,V)

①Vtrend←Rtrend.Query(T)，若结果缺失，程序停止；

②S.Append(T,V-Vtrend)；

③buffer.MoveWindow(“sparse”).

FunctionFeedResidue(T,V)

①Vtrend←Rtrend.Query(T)，若结果缺失，程序停止；

②Vsparse←S.Query(T)，若结果缺失，程序停止；

③Vresidue=V-Vtrend-Vsparse；

④RANKS←Cast(|Vresidue|)；

⑥ forrank←0 ～M-1 do

⑦Rrank.Append(T,Vresiduerank)；

⑧ end for

⑨buffer.MoveWindow(“residue”).

在算法1中，FeedTrend函数将T,V数据添加进入回归组件Rtrend中；FeedSparse函数尝试将T,V去除趋势成分并填入稀疏化组件S中；FeedResidue函数尝试将T,V去除趋势成分和稀疏成分后得到残差成分，并根据评估器的区间划分结果将残差成分切分为不同阶数据，依次添加进不同阶对应的回归组件Rrank中.在这类函数执行过程中，如果发现数据所依赖的去除项有不完全的情况，则不进行窗口滑动，等待所依赖的去除项完备后重新滑动.

Fig. 4 The data flow of online appending图4 在线新增数据流程

3) 数据查询

在数据查询阶段，TSR-VEP使用算法2中Query方法，依次查询各组件数据并按照式(4)进行重新融合.需要注意的是查询过程中如何利用回归组件从分阶残差定义域中恢复隐藏的φm信息.如图5和QueryResidue方法所示，我们将从高阶向低阶依次进行回归组件查询.根据式(7)，各阶查询过程仅保留尚未被高阶所覆盖的值，从而促使最终查询结果具有尽可能高的精度值.同时，为了确保VEP可查询任意时刻数据，我们通过Neighbors变量保留了各阶数据查询时的临近点位置信息，并逐层向低阶的临近点信息收缩合并，得到最终合并数据的临近点信息，从而可利用Interpolate的线性插值方法进行时间间隙的插值查询.

Fig. 5 Merging residues of different ranks图5 不同阶残差的融合示意图

算法2. VEP合并与查询.

需要已赋值的各阶R部件、S部件；

FunctionQuery(T)

①Vtrend←Rtrend.Query(T)；

②Vsparse←S.Query(T)；

③Vresidue,Neighbors←QueryResidue(T)；

④V←Vtrend+Vsparse+Vresidue；

⑤ returnInterpolate(T,V,Neighbors).

FunctionQueryResidue(T)

① 初始化V*,Neighbors*为与T等长的数组；

② forrank←M-1～0 do

③V,Neighbors←Rrank.Query(T)；

④V*←V*⊕V；*只增扩展*

⑤Neighbors*←Neighbors*⊗Neighbors；

⑥ end for

⑦ returnV*,Neighbors*.

FunctionInterpolate(T,V,Neighbors)

① 初始化V*为与T等长的数组；

③ if(v=∅)

⑥ end if

⑦ end for

⑧ returnV*.

3 实验与评价

本文将从真实应用场景出发，采用马萨诸塞大学Smart*项目采集的公寓能耗数据集[32]，并结合Liu等人提出的智能电表分析应用基准测试程序组作为验证VEP理论的数据挖掘类应用负载[33]，评估VEP理论在不同场景下的正确性和有效性.

实验选取Smart*项目的2016年公寓数据集，该数据集记录了114个公寓房间的功耗 (kW)以及实验地区的环境温度 (℉)，详细数据集信息如表3所示：

Table 3 The Details of Smart* Dataset表3 Smart*数据集详情

智能电表分析应用基准测试程序组包含需要使用功耗和温度数据的4个应用程序，分别是：1)PAR[34].建立功耗数据的周期性自回归模型，倾向于分析相邻时间数据的相关性.2)Histogram.提取功耗的直方图分布区间参数及对应区间的落点数量，倾向于分析单一用户的用电走势.3)Similarity.利用向量余弦判断不同公寓用电功耗相似程度，倾向于分析多用户间的用电走势.4)Threeline[35].建立不同温度走势下的用电倾向三线段模型，区分不同公寓的用电习惯，该负载倾向于分析单用户用电走势和温度之间的相关度.

本次TSR-VEP原型采用Python 2.7实现，仅用于原理验证，并采用Dell PowerEdge R730服务器实验环境进行模拟测试.服务器具体配置为2颗英特尔至强 E5-2640 v4 2.4 GHz处理器，8条16 GB RDIMM内存，基准测试应用负载选用Matlab语言实现.

我们设定VEP模型自身为f函数，应用负载为观测者g函数，本节将从3个角度评价VEP模型：1)无应用负载测试loss(x,f′(f(x)))，仅研究VEP自身不被观察时的数据压缩和还原过程；2)有应用负载测试loss(g(x),g(f′(f(x))))，研究被应用负载观察后的数据压缩和还原过程；3)通过初步测试结果讨论VEP在物端的实用性.

3.1 无应用负载情况目标测试

压缩性能和误差保证是分析VEP有效性的2个关键指标，本实验针对Smart*数据，通过调整不同的误差限制条件分析压缩率变化，本文定义压缩率为

(13)

Fig. 6 Compression rates with different highest rank error bounds图6 在不同最高阶误差限制下的压缩率变化情况

Fig. 7 Compression rates with different weighted average error bounds图7 在不同加权平均误差限制下的压缩率变化情况

图6显示不同阶数情形下压缩率在1.96～30.67区间变化，整体上来讲，压缩率和最高阶误差正相关.针对极端情况εM-1=0，即强制VEP进行无损压缩，压缩率高度退化，最小为1.96倍.由于回归组件的高效编码实现，结果显示其对时间序列数据仍然有一定的压缩效果.在εM-1=0.4前后，我们观察到各阶压缩率曲线出现了交叉点.在该点之前，由于阶数增加导致更多的数据被下放到允许较高误差的低阶回归组件，促使压缩率一定程度增加.在该点之后，低阶容许误差继续增大，但回归组件已经足够容纳全部数据，无法进一步缩减线性分段数量，因此增加阶数带来的压缩优化较少.同时,图7进一步显示了递增的阶数通过放宽各阶加权平均后的误差限制提升了整体压缩率，但压缩率的上升速率也随之减缓.

Fig. 8 The compression ratios of multiple apartments图8 多公寓压缩率图

3.2 有应用负载目标测试

本节分别将114个公寓功耗与温度的VEP还原数据、DCT还原数据及原始数据作为输入，进行4组用电分析应用负载为观测函数的对照实验.VEP和DCT的构建采用统一参数设定，结合3.1节分析，实验选定参数为：阶数M=3，分阶比例依次是τ={0.80,0.15,0.05}，依据式(12)的分阶误差依次为ε={1.48,0.65,0.1}，τS=0.8,εS=1.0.实验过程首先将原始数据集转换为VEP和DCT模型；再在相同的时间T下进行查询，还原得到应用程序所需的输入数据集；最后将得到的数据集输入应用负载得到观测结果.为使不同应用负载和不同公寓的观测结果能够统一比较，本实验以原始数据集的结果为参照量，通过标准差归一化(Z-Score)和结果平均化的方式得到各公寓的标量观测结果，即：

(13)

而不同重构方法与应用负载可通过相对于原始数据标量观测结果的绝对误差(absolute error)比较.

转换的VEP和DCT模型的压缩率如图8所示，VEP数据存储空间占用从平均10.8 MB降至平均576 KB，压缩率在16～43倍之间，平均压缩倍率为20.67倍.相比之下，无误差保证的DCT数据存储空间占用降至223 KB，压缩率49倍.

通过TSR-VEP的设计可知，周期性越强的家庭用电数据会产生越少的稀疏化组件数量,图9显示了本实验中各公寓VEP模型中的稀疏化组件数量.通过实验结果分析，18号公寓具有最少的122个稀疏化组件并表现了最佳的周期性，而全部公寓的平均组件数量为309个.对比观察图8和图9，稀疏化组件数量与压缩率负相关，这也说明了容易被预测的数据通常具备更好的压缩效率.

接下来我们将针对各类负载结果逐一分析:

Fig. 9 The number of sparse components图9 稀疏化组件数量

Fig. 10 The comparison results of PAR图10 PAR实验对照结果

1) PAR.如图10所示，VEP观测结果相对于原始数据观测结果的绝对误差在0.000 1和0.22之间，平均绝对误差是0.07，误差波动百分比为3.5%.DCT观测结果相对于原始数据观测结果的绝对误差在0.001 5和1.03之间，平均绝对误差是0.33.测试结果显示无误差保证的DCT方法的观测误差极大.这是由于PAR应用的部分注意力集中在描述细节走势的高阶信息上，无误差保证的DCT方法缺失了大量的局部细节与关键特征,而VEP弥补了这一缺点.

Fig. 11 The comparison results of Histogram图11 Histogram实验对照结果

2) Histogram.如图11所示，VEP观测结果相对于原始数据观测结果的绝对误差在0.000 7～0.105之间，平均绝对误差是0.02，误差波动百分比为1%.DCT观测结果相对于原始数据观测结果的绝对误差在0.000 2～0.23之间，平均绝对误差是0.04.实验结果显示，VEP和DCT与原始数据观测结果误差都处于极小的波动范围，这说明绘制直方图负载对能耗数据的高阶信息注意力较低，其所需的全部必要特征可通过简单的稀疏化成分提供.

3) Similarity.如图12所示，VEP观测结果相对于原始数据观测结果的绝对误差在0～0.28之间，平均绝对误差是0.035，误差波动百分比为1.75%.DCT观测结果相对于原始数据观测结果的绝对误差在0.38～0.75之间，平均绝对误差是0.52.实验结果显示，VEP误差波动可以被接受，而DCT的观测结果呈现出相对实际结果整体向上平移的形态，这是由于无误差保证的DCT丢失了局部细节，而过于平滑的波形增加了不同公寓用电模式之间的相似性，忽视了应用对高阶信息的注意力.VEP则弥补了这一缺点.

Fig. 12 The comparison results of Similarity图12 Similarity实验对照结果

4) Threeline.如图13所示，VEP观测结果相对于原始数据观测结果的绝对误差在0.003～1.49之间，平均绝对误差是0.2,误差波动百分比为10%.DCT观测结果相对于原始数据观测结果的绝对误差在0～1.39之间，平均绝对误差是0.2.实验结果显示，VEP和DCT的观测结果误差都相对较高，但整体仍可以接受.这类应用的特点是注意力较为分散，即使是低阶数据也需要一定注意力，而VEP允许低阶数据具备低精度的特点造成了应用的累计误差.

Fig. 13 The comparison results of Threeline图13 Threeline实验对照结果

综上所述，VEP在尽量减小应用负载观测误差的情况下，相对于原始数据存储实现了平均20.67倍的压缩率，在不同应用类型的测试上保持了的最低1%、平均4%的误差波动程度.同时实验结果显示PAR,Histogram和Similarity应用都具有高度集中的注意力，初步印证了注意力差别假说的正确性.

3.3 边缘及物端应用场景可行性探讨

目前变熵画像的研究仍处于初步探索阶段，仅使用Python语言快速地实现了验证原型，并未做面向过多性能和嵌入式芯片的专门优化.本节将从初步测试结果和算法估计给出内存脚迹、数据添加性能、数据查询性能以及物端设备执行的可行性分析.

针对内存脚迹的实验结果表明完整加载一个Smart*年度用电数据，需要放置于内存的索引空间仅为35 KB左右，其余的数据部分可放置于外存.若进一步针对不同的时间远近顺序使用放置策略，例如丢弃80%历史时间点的高阶数据，可进一步压缩内存脚迹到7 KB，从而满足了部分低端设备的硬件要求.此外，我们也可以通过仅保留低阶数据、仅保留高阶数据等不同策略，适应差异程度较大的各类硬件环境和应用场景.

在数据添加性能方面，主要时间消耗在建立稀疏化参数和分段逼近拟合算法的过程中.该部分操作利用快速缓存和窗口批处理方式，极大地降低了添加延时.针对Smart*数据的实测显示，目前平均1 s内可添加约1 000个时间点.而在真实的物端使用场景下，通常数据产生速度为秒级及分钟级以上，即使物端设备性能有较大的限制，目前的添加速度仍可满足物端应用的需求.

在数据查询性能方面，当前VEP实现仍有极大的提升空间.针对将长达一年的Smart*数据从分钟级降到小时级的批量筛选查询任务，VEP需要时间约1.5 s，而MySQL查询时间仅需要0.2 s左右.这部分原因在于目前的VEP实现还没有采用B -tree[36]等高效索引技术，未来有较大的优化空间.但针对单一时刻的数据查询，VEP的响应时间为5 ms，已满足了此类简单任务的时延需求.

综上所述，从初步测试结果的估计和推测，TSR-VEP可满足极其苛刻的物端计算环境.同时，我们也可通过Fork和Subscribe原语实现变熵复制和注意力订阅，实现不同级别、不同尺寸信息的整体推送或传输，从而优化节点间整体的性能功耗并实现数据重新布局.例如，使用Subscribe原语实现异常事件的推送报警，或仅允许Fork低阶VEP的方式保护数据交易过程中的用户隐私.

4 总 结

在物端设备资源相对受限的背景下，为使用统一方式解决物端海量数据的存储和应用多粒度信息需求问题，本文提出了一种数量级压缩物端数据的多粒度信息模型——变熵画像(VEP)，并实现了TSR-VEP数据存储原型.通过马萨诸塞大学的Smart*楼宇能耗数据集及智能电表基准测试应用，我们从压缩率、观测误差和运行开销这3个角度得出以下结论：1)VEP能够以相对原始数据集最高43倍、平均20.67倍的压缩率建立多粒度信息模型，甚至在零误差的极端限制条件下未发生压缩崩溃，仍然具备1.96倍压缩率; 2)在实现上述压缩率的同时，VEP取得了最低1%、平均4%的观测误差波动程度，初步验证了注意力差别假说的有效性; 3)目前VEP添加数据的速度约1 000条/秒，大跨度的批量数据查询筛选时间为秒级，单一时刻的简单查询为毫秒级，内存脚迹开销为7～35 KB，可满足物端设备资源相对受限的执行环境.

变熵画像是边缘和物端计算场景中具有潜力的一项技术，但仍存在优化空间.例如：1)改进索引和压缩方法，进一步优化数据添加、查询性能和数据存储压缩比；2)完善变熵画像理论，从理论模型推导和控制不同应用负载下的观测结果误差；3)将变熵画像融入到物端计算、边缘计算等计算模式中，与更多真实应用相结合，在接下来的工作中探讨变熵画像对于整个物端控域带来的优化效果.

ChaoLu, born in 1989. PhD candidate. Student member of CCF. His main research interests include things computing system and distributed data computing framework.

PengXiaohui, born in 1984. Assistant professor. Member of CCF. His main research interests include the architecture and computing models of things computing system.

XuZhiwei, born in 1956. Professor. Member of CCF. His main research interests include the distributed architecture and computing for the masses.