基于随机矩阵分解的大数据无向压缩算法设计

2023-09-20李恒武王辰阳

计算机仿真 2023年8期

高勇,李恒武,王辰阳

(信息工程大学,河南郑州 450001)

1 引言

伴随科学技术的发展及网络的现实需求,各类网络系统数据量呈直线增长,储存空间占比不断增加[1],对后续网络建设与运行维护产生很大影响。数据库较大、备份耗时较长,即便数据库磁盘空间得到提升,但依旧无法匹配数据增长速率,严重影响系统运行平稳性,数据的查询与储存效率也面临严峻考验[2]。

数据压缩技术的目标是降低文件所占储存空间的同时不损失重要数据,相关领域也从不同层面研究,例如,文献[3]运用相邻轨迹点经纬度更改走向确定行驶特征点,保存时序信息并压缩停滞点,利用采样法保留轨迹点,完成轨迹信息压缩。但压缩过程中没有消除冗余信息干扰,极易产生压缩失效问题;文献[4]利用空间变换技术分析数据相关性,通过时间相关性感知算法压缩处理空间系数,降低无用数据的空间占用率。但方法运算时间过长,无法保障数据压缩的即时性。

为解决当前数据压缩方法的不足,引入无向压缩概念,将数据设置为对称结构,有效提升数据压缩与解压精度,提出一种基于随机矩阵分解的大数据无向压缩算法。通过创建随机矩阵分解模型,有效剔除大数据中不相关的冗余信息,利用数据归约技术明确数据属性,通过无向旋转门算法完成数据无向压缩目标。与传统方法相比,本文方法具备更优的压缩效率与准确性。

2 随机矩阵分解下大数据可靠挖掘

网络大数据种类繁多,包含大量不相干数据,利用随机矩阵分解模型,挖掘海量大数据内被隐藏的可靠信息[5,6],剔除冗余数据,增强数据无向压缩整体质量。若在网络系统内拥有N个用户与M个项目,组成用户集U={u1,u2,…,un}和项目集I={i1,i2,…,im}。

随机矩阵分解模型给予用户与项目一种隐含特征矢量,分别记作

(1)

(2)

将已观测到的可靠数据条件概率计算过程记作

(3)

在随机概率矩阵分解模型内引入用户相邻数据,用户u的特征矢量用来描述其相邻矢量的加权和,Nu为用户u的相邻用户,Sui为用户u和用户i的项目偏好相似度,归一化处理Sui,挖掘网络中隐含可靠数据,过程为

(4)

3 基于无向旋转门的大数据无向压缩算法设计

利用以上过程消除冗余数据后,采用无向图即对称稀疏矩阵,定义数据为对称型结构,降低数据压缩难度,获得更为简单快捷的压缩方式。在此基础上,提出基于无向旋转门的大数据无向压缩算法,下面为方法详细推理过程。

3.1 大数据归约处理

数据归约为在数据自身含义前提下,探寻目标特性,确保数据原始面貌的同时减小数据规模。假设大数据集C内包含n个样本,各个样本中具备k项变量,将初始数据矩阵记作:

(5)

主成分分析法为一种应用较多的特征归约算法,利用不同变量的线性组合顶替初始变量,产生的线性组合间互相独立、数量小于初始变量,同时涵盖大量初始变量信息[7],完成恰当的数据归约处理。算法共分为以下五个步骤:

第一,标准化大数据样本,便于统一量纲;

第二,计算变量协方差矩阵D

(6)

(7)

式中,x′为线性变换后的变量,T是变换指数。

第三,推算以上协方差矩阵Dk×k的特征参变量λ1,λ2,…,λk,及其相应的正交化单位特征矢量ζ1,ζ2,…,ζk。矩阵Dk×k内和前m个最大特征值相对的m个特征矢量,可描述初始大数据从k维空间变换至的m维空间,且变换后的m维空间内特征两两之间互不相等;

第四,推导最大特征值和与全部特征值和的比值,如式(8)所示。比值结果采用百分比形式,命名为累积方差贡献率。该值展现出前m个主成分在方差总和内的投影。若投影比率较高,则涵盖m个特征的子集是k维空间的初步估计。

(8)

第五,计算上述特征矢量作为系数的m个主成分解析式

Yi=ζ1Xj

(9)

其中,Y为主成分元素,i、j均为数据集个数,ζ1表示正交化单位特征矢量。

通过式(9)的主成分解析式获得各个样本在每个主成分上的得分,获得全新的数据归约矩阵。

3.2 大数据的无向压缩

无向旋转门算法作为利用直线拟合的数据压缩方法,其中的最高准许偏差可获得最长的直线趋势[8-10],优化数据压缩性能与修复能力。无向旋转门算法的压缩过程如图1所示。横坐标表示数据点时间坐标,纵坐标是数据点的数值。若ΔE是压缩误差,将数据点Y0看作初始点,将距离数据点Y0的上下两个点作为支撑点[11],构建一个虚拟门。伴随数据点的增多,门会自动旋转开启,其长度也可无向无限延伸,门开启后会无法闭合。若两扇门的内角总和低于180°,继续旋转动作,内角总和高于180°,终止操作,储存前一个数据点,从该数据点开始重新压缩数据,图1内的储存点为Y0、Y3和Y4。

图1 无向旋转门算法压缩过程

两扇门平行时数据的精度取决于无向旋转门算法的压缩误差ΔE范围,压缩误差ΔE设定的越高,原数据点个数越少,压缩的数据量随之减少[12],压缩性能越优秀,反之压缩效果越差。

(10)

(11)

(12)

(13)

压缩比用来衡量压缩算法对数据的压缩性能,压缩比数值越高,表明压缩成效越优,是一种硬性压缩评估标准[13]。其它三种解压缩误差均不同层面地展现了数据的失真度,也就是数据解压缩后的数据精度,误差值越小,表明算法无向压缩准确性越高[14]。均方误差的计算最简便且计算量小,将其设定为本文的压缩评估指标,在描述数据压缩能力时节约运算开销。

网络正常运行时,把数据实际值和解压缩值之间的期望偏差δ看作输入值[15],真实平均绝对误差是输出值,二者相减获得的差值ε为反馈值,利用负反馈调节压缩误差。参变量ΔE为一个可以随机改变的值,仅需设定上、下临界值,就能按照真实压缩状况完成动态调节。

如果Emax、Emin依次为压缩误差ΔE的上、下临界值,D是压缩误差调节参变量,τ表示数据解压缩真实偏差和期望偏差的误差容差,y1～yn是待压缩数据集,压缩过程如下:

①压缩y1～yn数据前,初始化压缩参变量。Emax、Emin可自主设置,D、τ需要提前设置;

②假设T为大数据无向压缩算法容许的最大时间间隔,从待压缩数据内提取数据点yi,若此点和上个储存点的时间间隔大于等于T,直接储存上个数据点yi-1,无需使用无向旋转门分析,反之采取无向旋转门压缩;

③推算数据点yi位置无向旋转门两扇门的斜率kup、kdown,若两扇门为平行状态,那么储存数据点yi-1,同时将该点看作全新的压缩初始点,反之舍掉数据点yi;

⑤按照差值ε的状况,调节压缩误差ΔE。如果0≤ε<δ·t,证明偏差处于容许偏差范围,无需实施调节;若ε≥δ·t,证明数据误差值偏高,计算得到的平均压缩误差偏小,ΔE值偏小,要在Emax取值范围内扩大ΔE,过程为

(14)

⑥若-δ·t<ε<0,证明数据误差偏小,平均压缩偏差较大,ΔE值较大,丢弃了很多初始数据,要在Emin范围中缩小ΔE值,记作

(15)

假设ε没发生以上状况,证明解压缩数据失真度高,返回第一步重新计算。

⑦动态调节压缩误差后,折回第二步使用全新的ΔE值完成压缩任务,持续迭代直至误差ε在可接受范围,实现大数据无向压缩。

4 仿真研究

4.1 仿真设置

利用仿真验证本文压缩算法可靠性,实验平台是面向对象的开源仿真平台OMNeT++3.3,在一个500×500网络监测区域任意部署400个数据节点,节点采集的各数据长度是3byte。局域网络包括一个基站、3个分簇和各分簇中的7个采集节点,如表1所示。将文献[3]滑动窗口法与文献[4]时空相关法作为对比方法,比较三者压缩性能优劣。

表1 簇头与分簇采集节点编号

4.2 不同算法压缩比情况

图2为三种算法相同实验环境下的压缩比情况。

图2 三种方法数据压缩比分析

从图2看出,本文算法的压缩比要显著高于两个对比方法,压缩能力更好。这是由于本文采用随机矩阵分解策略最大限度剔除不相关信息,保证海量大数据信息准确性,伴随节点采集数据量的增多,数据之间的时间相关性越来越大,本文方法可描述较多初始数据,压缩比也随之提高,最终趋于稳定,展现出较强的数据压缩实用性。

4.3 不同算法数据压缩节点能耗情况

数据压缩时会产生额外的节点计算能耗,将节点能耗当作衡量大数据压缩算法优劣的指标。实验前预先设置节点的初始能量、收发功率、数据收发速度等参数,按照数据分组长度获得节点剩余能量。另外,按照节点原始能量和总节点数量推算网络原始总能量,原始总能量和网络剩余能量的差就是网络数据压缩总能耗,总能耗和网络节点数量相除就是节点的平均能耗。

仿真中节点总数是150,节点初始能量为2J,发射功率是0.07W,接收功率为0.09W。三种算法数据压缩节点平均能耗对比结果如图3所示。