一种基于时间序列分析的网络拓扑推断方法及装置

1.一种基于时间序列分析的网络拓扑推断方法，其特征在于，包括以下步骤：步骤S101：获取信息数据，将所述信息数据以时间序列进行表征；步骤S102：根据表征结果，对各节点进行排序，并按照排序次序将各节点对应的时间序列进行拼接；步骤S103：对拼接后的时间序列进行分段近似聚合；步骤S104：使用格拉姆角差场算法对分段近似聚合后的时间序列进行编码，构建类格拉姆矩阵；步骤S105：根据所述类格拉姆矩阵，对网络进行拓扑推断；所述步骤S101：获取信息数据，将所述信息数据以时间序列进行表征，包括：获取信息数据，设定采样时间间隔，对所述信息数据进行分析，若在采样间隔内有信号发送，则该采样间隔对应的时间序列中的值为1，否则为0；所述步骤S102：根据表征结果，对各节点进行排序，并按照排序次序将各节点对应的时间序列进行拼接，包括：所述信息数据的时间序列的表征方式是0和1组成的序列，将各节点首次出现1的时间进行比较，即按照1出现的时间对节点进行排序，1出现的早的节点排在前面；按照排序次序将各节点对应的时间序列进行拼接；所述步骤S103：对拼接后的时间序列进行分段近似聚合，包括：对于一个包含 n 个观测值的时间序列 T ， T={t 1 ,t 2 ,…,t n } ，使用 N d 表示时间序列被处理后得到的最终维数；设定压缩率 ψ 用于表示原始时间序列的长度与其分段聚合后的长度之比， ψ 的计算公式如下： （1）使用 表示时间序列 T 压缩后得到的结果， T ψ 中第r个元素 对应的计算公式如下： （2）其中， t j 为 T 中的第 j 个元素；在分段近似聚合的基础上，将 T ψ 中元素归一化到[-1,1]区间内，得到集合 ， ，其中， 为聚合结果归一化后集合 中的第 i 个元素， 的计算公式为： （3） 为 中第i个元素，max( T ψ )为 T ψ 中最大值，min( T ψ )为 T ψ 中最小值；步骤S104：使用格拉姆角差场算法对分段近似聚合后的时间序列进行编码，构建类格拉姆矩阵，包括：根据归一化的结果，将分段近似聚合后的时间序列 从笛卡尔坐标系转换到极坐标系，将缩放后得到的数值 编码为角度 ，且存在 ，将 对应的时间戳 t i ’ 编码为半径 r i ，坐标变换公式如下： （4）其中， t i ’ 是时间序列中第 i 个元素对应的时间戳， 是对极坐标系统生成空间进行正则化的常数因子， 为常数集合；利用格拉姆角差场算法对分段近似聚合后的时间序列进行编码构建类格拉姆矩阵，其计算公式如下：其中，G为编码得到的类格拉姆矩阵， 为 对应的角度值大小， 为 对应的角度值大小， 是 的平方操作，I是单位行向量[1,1,…,1]， 是 的转置操作， 为 的转置向量；所述步骤S105：根据所述类格拉姆矩阵，对网络进行拓扑推断，包括：根据节点之间是否存在通联关系为不同节点对形成的类格拉姆矩阵增加标签，即节点对之间存在通联关系则其对应的标签为1，否则为0；在标签数据构建的基础上，使用K最近邻算法进行判定，使用余弦相似度来衡量样本之间的相似性，余弦相似度的计算公式为： （6）其中 P 为已训练好模型中的一个序列， p k 为 P 中第 k 个元素， P ’ 为待判定序列， p ’ k 为 P ’ 中第 k 个元素；在样本相似度求取得基础上，根据样本相似性找出相似度最高的K个训练样本作为待分类样本的K个近邻，再根据K个近邻采用投票策略实现对待分类样本类型的判定，判定待分类样本对应的两个节点之间是否存在通联关系，根据判定结果和节点位置信息完成拓扑推断结果的输出。 2.一种基于时间序列分析的网络拓扑推断装置，其特征在于，所述装置包括：表征模块：配置为获取信息数据，将所述信息数据以时间序列进行表征；拼接模块：配置为根据表征结果，对各节点进行排序，并按照排序次序将各节点对应的时间序列进行拼接；聚合模块：配置为对拼接后的时间序列进行分段近似聚合；编码模块：配置为使用格拉姆角差场算法对分段近似聚合后的时间序列进行编码，构建类格拉姆矩阵；拓扑推断模块：配置为根据所述类格拉姆矩阵，对网络进行拓扑推断；所述表征模块，包括：获取子模块：配置为获取信息数据，设定采样时间间隔，对所述信息数据进行分析，若在采样间隔内有信号发送，则该采样间隔对应的时间序列中的值为1，否则为0；所述拼接模块，包括：拼接子模块，配置为所述信息数据的时间序列的表征方式是0和1组成的序列，将各节点首次出现1的时间进行比较，即按照1出现的时间对节点进行排序，1出现的早的节点排在前面；按照排序次序将各节点对应的时间序列进行拼接；所述聚合模块，包括：压缩子模块，配置为对于一个包含 n 个观测值的时间序列 T ， T={t 1 ,t 2 ,…,t n } ，使用 N d 表示时间序列被处理后得到的最终维数；设定压缩率 ψ 用于表示原始时间序列的长度与其分段聚合后的长度之比， ψ 的计算公式如下： （1）使用 表示时间序列 T 压缩后得到的结果， T ψ 中第r个元素 对应的计算公式如下： （2）其中， t j 为 T 中的第 j 个元素；在分段近似聚合的基础上，将 T ψ 中元素归一化到[-1,1]区间内，得到集合 ， ，其中， 为聚合结果归一化后集合 中的第 i 个元素， 的计算公式为： （3） 为 T ψ 中第i个元素，max( T ψ )为 T ψ 中最大值，min( T ψ )为 T ψ 中最小值；所述编码模块，包括：转换子模块：配置为根据归一化的结果，将分段近似聚合后的时间序列 从笛卡尔坐标系转换到极坐标系，将缩放后得到的数值 编码为角度 ，且存在 ，将 对应的时间戳 t i ’ 编码为半径 r i ，坐标变换公式如下： （4）其中， t i ’ 是时间序列中第 i 个元素对应的时间戳， 是对极坐标系统生成空间进行正则化的常数因子， 为常数集合；矩阵构建子模块：配置为利用格拉姆角差场算法对分段近似聚合后的时间序列进行编码构建类格拉姆矩阵，其计算公式如下：其中，G为编码得到的类格拉姆矩阵， 为 对应的角度值大小， 为 对应的角度值大小， 是 的平方操作，I是单位行向量[1,1,…,1]， 是 的转置操作， 为 的转置向量；所述拓扑推断模块，包括：标记子模块：配置为根据节点之间是否存在通联关系为不同节点对形成的类格拉姆矩阵增加标签，即节点对之间存在通联关系则其对应的标签为1，否则为0；余弦计算子模块：配置为在标签数据构建的基础上，使用K最近邻算法进行判定，使用余弦相似度来衡量样本之间的相似性，余弦相似度的计算公式为： （6）其中 P 为已训练好模型中的一个序列， p k 为 P 中第 k 个元素， P ’ 为待判定序列， p ’ k 为 P ’ 中第 k 个元素；推断子模块：配置为在样本相似度求取得基础上，根据样本相似性找出相似度最高的K个训练样本作为待分类样本的K个近邻，再根据K个近邻采用投票策略实现对待分类样本类型的判定，判定待分类样本对应的两个节点之间是否存在通联关系，根据判定结果和节点位置信息完成拓扑推断结果的输出。 3.一种基于时间序列分析的网络拓扑推断系统，其特征在于，包括：处理器，用于执行多条指令；存储器，用于存储多条指令；其中，所述多条指令，用于由所述存储器存储，并由所述处理器加载并执行如权利要求1所述的基于时间序列分析的网络拓扑推断方法。 4.一种计算机可读存储介质，其特征在于，所述存储介质中存储有多条指令；所述多条指令，用于由处理器加载并执行如权利要求1所述的基于时间序列分析的网络拓扑推断方法。