欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

博士论文
当前位置:首页 > 博士论文
面向卫星遥测数据流的最小稀有模式挖掘方法
来源:一起赢论文网     日期:2020-04-27     浏览数:219     【 字体:

 d of algorithm is slower.With the development of the big data and the technologies of cloudplatform,traditional storage devices have been unable to keep up with the speed of data transmission.Therefore,if static data is still used as the object of the research,the storage device may easilylose data when storing the data.In order to solve the above problems,this paper proposes a minimalrare pattern mining method that can quickly discover the hidden information in the satellite telemetrydata stream.It has the following advantages:First,the algorithm proposed in this paper,thatis,the minimal rare pattern mining algorithm,does not require knowledge in the satellite field.Second,this paper references the sliding window technology and objectifies the subjective parameters(that is,window size)so that the algorithm proposed in this paper can process satellite telemetrydata stream in real time.Third,the algorithm improves the mining efficiency by only mining theminimal rare pattern,instead of all the rare patterns.Fourth,the algorithm uses bidirectionaltraversal techniques to improve the speed of the algorithm.Ten key features are selected from thesatellite telemetry data stream of some orbiting satellite to verify the proposed method in thispaper.The experimental results indicate that the algorithm proposed in this paper can effectivelymine all the minimal rare patterns from satellite telemetry data stream,and the speed of theproposed algorithm is faster than that of the existing methods.Keywords  minimal rare pattern;satellite;telemetry data stream;top-down;bottom-up;bidirectionaltraversal;pattern mining;data mining1 引 言中国自主研发的北斗卫星系统是一款服务于全球的卫星导航和定位系统,在全球范围内提供定位精确度为10m,测速精确度为0.2m/s,授时精度为10ns的高精度服务.它主要由35颗卫星组成,目前广泛应用于电信、交通、救灾、测绘等诸多领域[1].它在全球范围内持续地传输大量的实时监测数据,但由于太空环境复杂多变,卫星的健康安全时刻面临着威胁挑战[2-3].因此,为了确保北斗卫星的正常运行,必须提供一种智能服务来自动监控卫星的运行状态,并实时地处理卫星遥测数据.卫星遥测数据是以数据流的形式呈现的.所谓数据流是指只能以预先规定的顺序被读取一次的数据序列[4].起初,卫星产生的海量数据流大多用二三级存储设备进行存储,但随着内存技术和处理器技术的进步,使得二三级存储设备的数据处理速度越来越跟不上数据传输的速度[5].如果数据处理的速度比数据传输的速度慢,就会导致大量的信息流失,这对于卫星的健康检测来说是不允许的.因此,有必要对卫星遥测数据流进行实时处理.但是遥测数据流的处理是十分困难的,原因如下:(1)卫星遥测数据流的传输速度非常快,需要在短时间内处理大量的数据[6].因此除了对硬件的性能要求外,处理算法必须是高效的、健壮的.(2)遥测数据流在卫星生命周期内是无限传输的,无法进行一次性处理,也无法得到最终的处理结果[6].所以必须对数据流进行实时分段处理,从而得出部分处理结果.(3)卫星遥测数据流的数据维度较大[6],导致其数据容量远超二三级存储设备的容量.所以为了保存完整的未经处理的数据信息,避免数据丢失,需要进行实时的数据处理,以便及时地得到部分的处理结果.在必要时,可 以放弃已 处理过的 无用数据,以便接纳新的遥测数据.现如今,在轨卫星主要采用自主运行为主,地面遥控为辅的方式运行,卫星发送的遥测数据是地面人员监测卫星设备状态的唯一依据[7].卫星由多个分系统组成,各个分系统根据需要在一些关键部件上设置遥测点,智能监控系统按一定周期对各个遥测点上的数值进行采集,包括角度、电流值、电压值、压力值、温度值、状态字、标识符、同步字等.由于采集到的卫星遥测数据是一种含有噪声和缺失值的高维大数据流,所以传统的人工服务和一般的数据分析工具无法满足卫星遥测数据的分析要求.因此,卫星监测系统需要一种智能服务来代替人工服务.它不仅能够实时地监控在轨卫星的参数状态,而且还3125 计  算  机  学  报 2019年种高效的遥测数据分析方法,用于实时地挖掘卫星大数据流,而模式挖掘方法恰能满足这种要求[8].遥测数据的模式挖掘对于卫星的自动异常检测和故障诊断都非常重要,是一种具有广阔应用前景的智能监控手段[7].目前智能服务的研究热点主要是关于移动互联网、物联网和传感器等背景下的研究[9-12].在卫星传感器和数据挖掘的背景下,针对卫星智能监控方面的研究绝大多数都致力于研究频繁模式挖掘,而稀有模式挖掘研究甚少[7,13-15].然而在卫星态势安全预防等领域,稀有模式挖掘更有研究意义与实用价值,因为它可以从少部分信息中揭示出频繁模式挖掘无法发现的隐藏信息[16],而这些信息通常应用于卫星安全监测.一种做法是将挖掘出的最小稀有模式作为异常发现方法的输入数据,之后通过计算异常因子来识别卫星存在的潜在异常.例如:2015年,Hemalatha等人[17]在乳腺癌异常检测的背景下,提出了一种通过挖掘稀有模式的方式来检测异常值的方法,并且通过实验证明其效率和准确率都高于基于频繁模式的异常检测方法.通过挖掘稀有模式应用于卫星异常检测的基本思想是,那些构成最小稀有模式生成源的观察结果可能是异常值,因为它与所考虑的其它观察结果相比具有“区别特征值”[17].因此,稀有模式挖掘作为一种重要的模式挖掘方法,可以智能地发现卫星遥测数据中的稀有模式,进而服务于在轨卫星智能监控.尽管稀有模式挖掘方法还不如频繁模式成熟,但仍然存在一些稀有模式挖掘算法,它们的应用意义及效率要远高于现有的频繁模式挖掘算法,例如 Hyper-Linked RPM[18]算法.稀有模式一般是指支持度小于指定最小支持度阈值的模式,但随着算法要求的变化,也有不同的定义.例如,Bhatt和 Patel[19]提出的以最大约束为限制条件的稀有模式,当且仅当该模式的支持度小于指定的最小频繁支持度阈值并且大于或者等于指定的最小稀有支持度阈值时,才可以称为稀有模式.与大多数以静态数据为研究对象的模式挖掘相比,以动态数据流为对象的模式挖掘要困难许多,这是因为数据流包含一系列连续到达的、无限的和无序的数字序 列[6],并 且这 些数 字 序 列通 常 只 能 读 取 一次[4].为了解决这个难题,Chang和 Lee[20]提出了采用滑动窗口机制挖掘数据流的方法,得到了不错的实验结果.其后的许多研究者都采用滑动窗口技术来处理数据流,例如 Lei[16]和 Zhang等人[21].通过滑动窗口可以对数据流进行实时地处理,从而克服处理数据流对象的困难.卫星遥测数据流面临的问题和挑战总结如下:(1)在缺乏专业领域知识的前提下,如何从遥测数据流中挖掘出最小稀有模式.已有的数据流处理方法通常会涉及很多专业领域知识[22-23],从而增加了卫星遥测数据流挖掘的难度,也阻碍了研究成果的应用.(2)如何发现少部分数据中的隐藏信息.稀有模式挖掘不如频繁模式挖掘成熟,我们可以借鉴的算法很少.目前,大多数算法都是从大部分数据中挖掘出频繁模式,找出相应的规律,并将少部分数据直接舍弃.然而,卫星在绝大多数情况下都是正常运行的,那些少部分数据中可能隐藏着卫星潜在的不正常运行的重要信息.(3)如何实时处理数据流.由于数据流的诸多特性,导致以动态数据流为对象的算法比以静态数据为对象的算法要困难许多.(4)如何设定滑动窗口的尺寸.滑动窗口尺寸通常是一个主观变量,对用户敏感,不具客观性.(5)如何提高挖掘算法的效率.传统的稀有模式挖掘算法在处理卫星遥测数据流时速度较慢,因为它们首先需要生成全部的候选集,然后再从候选集中选出符合要求的模式.针对上 述 困 难 和 挑 战,本 文 做 出 的 主 要 贡 献如下:(1)针对卫星遥测数据流,本文提出了一种无需专业领域知识的挖掘算法,该算法只需要输入一定格式的遥测数据就可以挖掘出最小稀有模式.考虑到用户缺乏卫星专业领域知识,因此在设计算法时,仅以遥测数据为研究对象,不借助偏差、帆板旋转角等任何卫星领域知识.这样可以使得卫星的智能监控服务系统在挖掘模块和知识库上的耦合度较低.否则,一旦专业知识库出错或缺乏,就会导致挖掘模块无法运行.(2)本文 提 出 了一 种 最 小 稀有 模式 挖 掘 算法MRP-TB(Minimal Rare Pattern based on Top-downand Bottom-up).该算法通过挖掘最小稀有模式来揭示隐藏在少部分数据中的规律[16].与频繁模式挖掘不同,该算法以少部分卫星遥测数据流为研究对象,目的是找出在少部分数据中隐藏的有用信息.(3)本文首先使用连续小波去除卫星遥测数据的噪声,然后通过小波方差模拟出遥测数据流的第一主周期.为了使滑动窗口尺寸只与数据流本身相关,而不受人为主观因素的影响,我们以数据流的第6期 周忠玉等:面向卫星遥测数据流的最小稀有模式挖掘方法3135为参照,设定滑动窗口的尺寸.然后再将滑动窗口技术应用于卫星遥测数据流.该技术主要对卫星遥测数据流进行分段,使得 MRP-TB算法能够实时地处理海量的卫星遥测数据流.(4)MRP-TB算法无需生成全部候选集,也无需挖掘出全部稀有模式.最小稀有模式能够表征所有稀有模式,但其生成数量却远小于稀有模式.该算法通过挖掘最小稀有模式来提高算法效率.此外,为了进一步提高算法的运行速度,算法同时使用自顶向下和自底向上的双向遍历技 术来生成树的候选集,寻找最小稀有模式,提高算法效率.通过真实的卫星遥测数据对所提算法进行验证,大量实验表明本文所提的算法是有效的,并且其运行速度要高于传统算法.本文 第 2 节介绍稀有模式挖掘领域的相关工作;第3 节引入模式挖掘的预备知识,给出最小稀有模式挖掘算法和示例,分析 算 法的理论复杂度;第4节进行实验并分析实验对比结果;第5节总结全文.2 相关工作目前,模式挖掘以频繁模式挖掘居多,而稀有模式挖掘相对较少[16].从现有的关于稀有模式挖掘的研究来看,大多数关于稀有模式挖掘的研究都是基于静态数据的.但是,随着大数据和云计算技术的飞速发展,基于动态数据的稀有模式挖掘方法也许更为实用.本文将现有的稀有模式挖掘方法分为2类(如表1所示),即基于静态数据的稀有模式挖掘和基于动态数据流的稀有模式挖掘.表 1 稀有模式挖掘分类类型1:基于静态数据Hyper-Linked RPM  Apriori-Inverse  AfRIM  RP-Tree类型2:基于动态数据流SRP-Tree  MIP-DS  MRSP-SW  SRAM2.1 基于静态数据的稀有模式挖掘当从一般的密集型数据中挖掘稀有模式时,模式增长法有较大的优势.但在处理稀疏数据集和短格式 数 据 集 时,该 方 法 存 在 性 能 上 的 缺 陷.为 此,Borah和 Nath[18]提出了 Hyper-Linked RPM 算法.该算法采用基于队列的超链接数据结构,使得算法在挖掘稀有模式的同时能够自动调整链接,从而减少树结构的内存开销.由于该算法主要处理稀疏数据集和短格式数据,所以在挖掘密集型数据的稀有模式时,其性能不如模式增长类的算法.Yun和 Rountree[24]根 据 Apriori算 法 提 出 了一种稀有模式挖掘算法 Apriori-Inverse.该算法可以发现“完美的零星规则”,所谓“完美的零星规则”是指在发现的规则中,模式本身以及模式中包含的所有单个项都是稀有的.在算法结构上,该算法采用与 Apriori算法相似的自下而 上 的搜索方 式.在阈值设定上,Apriori-Inverse算法设定了2个阈值,即最小支持度阈值和最大支持度阈值.只有支持度在最小支持度阈值和最大支持度阈值之间的模式才认为是稀有的.然而,该算法只能挖掘“完美的零星规则”,对于那些“不完美的零星规则”(即在规则中,模式本身是稀有的,而单个项是频繁的)则无法挖掘.与 Apriori-Inverse算 法 不 同,Adda等 人[25]提出的 AfRIM 算法没有采用 自 底向上的 搜 索方式,而是采用 了 自 顶 向 下 的 搜 索 方 法.该 算 法 通 过 将Apriori算法实例化来解决稀有模式挖掘的问题.由于 AfRIM 算法没有考虑舍弃那些支持度为0(支持度为0的项通常不具有实际意义)的项,所以其运行效率不高.由于上述算法大多数是基于 Apriori算法,所以通常会生成大量的候选集,并且需要繁琐的剪枝策略.为此,这类算法需要大量的时间来执行这个过程,从而导致算法的运行效率不高.为了解决这个问题,许多研究者们开始采用基于 FP-Growth算法的树形结构来代替类 Apriori算 法的剪枝策 略,从而避免在候选集生成和剪枝步骤上浪费大量的时间.例如,Tsang 等 人[26]提 出 的 基 于 FP-Tree结 构 的RP-Tree算法.该算法只需要对数据库进行一次扫描就可以挖掘出符合条件的稀有模式,其运行时间比使用 Apriori策略的算法少 很 多.但是该 算法仍有一些缺点,它只会生成特定类型的稀有模式,存在像 Apriori-Inverse算法那样无法挖掘出“不完美的零星规则”的问题.2.2 基于动态数据流的稀有模式挖掘2012年,Huang等人[27]提 出 了 一 种 使 用 树 形数据结构来搜索数据流的稀有模式方法,称之为流式稀有模式树SRP-Tree.为了与数据流的传输速度同步,SRP-Tree算法采用了滑动窗口技术,并且该算法可以仅对数据流进行一次扫描就可以找出所需结果.此外,该算法既可以挖掘动态数据流,也可以挖掘静态数据.为了适应不断变化的数据分布,该算法设置了不同的滑动窗口大小来进行稀有 模式挖3145 计  算  机  学  报 2019年日期:2018-09-10;在线出 版 日 期:2019-03-04.本 课 题 得 到 国 家 自 然 科 学 基 金 (U1433116)、中 央 高 校 基 本 科 研 业 务 费 专 项 资 金(NP2017208)、南京航空航天大学研究生创新基地(实验室)开放基金(kfjj20181605)资助.周忠玉,硕士研究生,主要研究方向为数据挖掘、机器学习.E-mail:zzy1433771015@163.com.皮德常(通信作者),博士,教授,博士生导师,中国计算机学会(CCF)高级会员,主要研究领域为数据挖掘、大数据管理与分析.E-mail:nuaacs@126.com.面向卫星遥测数据流的最小稀有模式挖掘方法周忠玉  皮德常(南京航空航天大学计算机科学与技术学院 南京 211106)摘 要 模式挖掘是应用于卫星智能监控服务中的一项重要技术.当前频繁模式挖掘的使用率要远远高于稀有模式挖掘,然而对于卫星遥测数据流来说,频繁模式挖掘在安全监测和故障预防等方面所取得的成效不如稀有模式挖掘.因为频繁模式挖掘无法从卫星的遥测数据中揭示卫星可能存在的潜在故障.卫星遥测是持续不断进行的,所以其数据流存在数据量大、传输速度快和数据重复性高的特点.如果采用一般的稀有模式挖掘方法来挖掘卫星数据流,尽管其速度比频繁模式挖掘快,但总体上仍然较慢,不能满足卫星实时监测的需要.针对上述问题,本文提出一种可快速找出卫星遥测数据流中隐藏信息的最小稀有模式挖掘方法,它具有如下优点:(1)无需卫星领域知识;(2)引用滑动窗口技术并将主观参数(窗口尺寸)客观化,使得算法能够实时地处理数据流;(3)通过仅挖掘最小稀有模式方式来提高算法的挖掘效率;(4)该算法使用双向遍历技术提高算法的运行速度.从某在轨卫星的遥测数据流中选取10个关键特征参数进行算法验证.实验结果表明,本文所提算法能有效地从卫星遥测数据流中挖掘出全部的最小稀有模式,并且其挖掘速度比现有的方法快.关键词 最小稀有模式;卫星;遥测数据流;自顶向下;自底向上;双向遍历;模式挖掘;数据挖掘中图法分类号 TP311   DOI号 10.11897/SP.J.1016.2019.01351Minimal Rare Pattern Mining Method For Satellite Telemetry Data StreamsZHOU Zhong-Yu PI De-Chang(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106)Abstract  The pattern mining is an important technology applied to satellite intelligent monitoringservices.At present,the usage ration of frequent pattern mining is much higher than that of therare pattern mining.However,as far as the research whose target object is satellite telemetrydata stream,the results of the frequent pattern mining is not as effective as those of the rare patternmining in terms of the security monitoring,fault prevention and so on.This is due to the fact thatthe frequent pattern mining can not reveal the potential faults and hidden dangers that may existin the components of satellites from satellite telemetry data stream,and it cannot also providepreventive measures.Since telemetry for satellites is continuously carried out,the data stream onsatellite telemetry has the following characteristics:in the first place,it includes a large amountof data;in another,its transmission speed is fast,and what is more,its data repetition rate ishigh.If the common rare pattern mining methods are used to mine satellite telemetry datastream,although its mining speed is faster than the mining speed of the frequent pattern mining,it is still slow on the whole and cannot meet the needs of real-time monitoring for satellite.Whatis more,the general rare pattern mining mainly takes static data as the object of the research.Inorder to find out all the rare patterns,the strategy of generating all candidates and then pruningis usually adopted,but which may be leading to the problem of combinatorial explosion and the人为的预定义滑动窗口大小,始终无法赶上流数据分布的变化.该算法可以改为动态调整滑动窗口和 阈 值 的 方 式,以 适 应 不 断 变 化 的 流 数 据环境.2015年 Hemalatha等人[17]提出了一种最小稀有模式挖掘算法 MIP-DS.该算法首先将数据流转换为二进制矩阵的形式,以此矩阵为处理对象,采用滑动窗口以跟上数据流分布的变化.此外,他们还提出了一种扩展算法 MIFPOD,该算法针对 MIP-DS算法挖掘出的最小稀有模式,计算出基于异常值的最小稀有模式因子 MIFPOF,然后根据 MIFPOF判断数据流中的异常值.但该算法存在2个缺点:(1)将数据流转换为二进制矩阵的形式,可能会丢失部分信息;(2)该算法采用了固定的最小支持度阈值,没有考虑概念漂移,不能适应数据流的变化.传统的模式挖掘有2种局限性:(1)在静态的数据集中进行挖掘;(2)结果仅是频繁模式.为了突破这种局限性,Ouyang[8]在2017年提出了 MRSP-SW算法.该算法能够在动态的数据流中挖掘稀有模式.该算法与 MIP-DS算法类似,采用滑动窗口技术来与数据流的变化同步.从其实验结果可知,算法是高效的.但是算法用的是合成数据,不能证明该算法在真实数据上是正确的、有效的.为了确保网络服务质量,Liu等人[28]于2017年提出了一种针对网络性能的挖掘方法,称之为基于Spark的稀有关联规则挖掘算法 SRAM.该算法采用 FP-Growth数据结构,并结合 Spark等大数据技术,可以快速地从动态数据流中挖掘出符合条件的稀有关联规则.由于该算法的目的是确保网络服务质量,所以将重心放在 NPC 和 KQI的异常值检测上.据实验分析可知,该算法的准确度为85%,仍然有较大的晋升空间.3 高效的最小稀有模式挖掘算法本节给出基于双向遍历的最小稀有模式挖掘算法.在3.1节介绍一些最小稀有模式挖掘的预备知识;在3.2节给出对应的算法和解释算法的简单示例;3.3节给出算法的效率分析;3.4节分析算法的复杂度.3.1 预备知识定义项集I={i1,i2,…,im},其中ik(1km)为一个项,每一个项表示事务的一条信息.假设事务数据流 DS={t1,t2,…,tn}表示一个n事务的集合,其中ti(1in)是一组项的集合,当n→ ∞时表示该数据流有无穷多个事务.如果一个项的集合I′={iu,iv,…,iw}I(u,v,w∈[1,m])是非空的,那么称这个集合I′为项集或者模式.如果 项集I′包含k 个项,则项集I′的长度|I′|=k,并且称该项集为k-项集.一个数据流事务ti通常用一个形如〈Tid,Iid〉的二元组来表示,其中 Tid表示事务标识符,Iid表示事务Tid对应的模式.定义1. 滑动窗口是一种流量控制技术,在同一时段内仅允许处理窗口内部的数据,用SW (SlidingWindow)表示.滑动窗口SW 使得算法仅允许处理数据流DS 中最近接收的事务.滑动窗口的大小用符号 SW 表示,意思是 指 数据流 DS 中最近接收的事务的数量.定义2. 项集或者模式I′的支持度定义为滑动窗口SW 中包含模式I′的事务数量占滑动窗口SW 中事务总数量的比例,用式(1)表示.其中自定义函数CountSW(I′)表示在滑动窗口SW 中包含模式I′的事务数量.Support iSW(I′)=CountSW (i)SW,i∈I′ (1)定义3. 一个模式I′被称为是稀有模式[29],当且仅当它在滑动窗口SW 中的支持度小于用户指定的最小支持度阈值δ,用式(2)表示.实际中通常使用其变形公式(3),这便于判断模式的类型.SupportiSW(I′)<δ,i∈I′ (2)CountSW (i)<δ× SW ,i∈I′ (3)定义4. 一个模式I′被称为是频繁模式[29],当且仅当它在滑动窗口SW 中的支持度大于或者等于用户指定的最小支持度阈值δ,用式(4)表示.实际中会使用其变形公式(5),便于判断模式的类型.Support iSW(I′)δ,i∈I′ (4)CountSW (i)δ× SW ,i∈I′ (5)定义5. 如果一个稀有模式I′的所有子集都是频繁的,则称这个模式I′为最小稀有模式,记为MP,用式(6)表示.MP={i|Support iSW(I′)<δ∧Support jSW(I′)δ},ji (6)3.2 简单的算法示例和 MRP-TB算法本节分为两个部分,第1部分介绍算法思想,第2部分举例说明算法步骤,然后给出相应算法的描述.3.2.1 MRP-TB算法思想MRP-TB算法是一种快速的最小稀有模式挖掘算法.该算法基 于 数据本 身,而 无需卫星 领域知6期 周忠玉等:面向卫星遥测数据流的最小稀有模式挖掘方法3155周期作为滑动窗口尺寸,使得算法可以实时地处理数据流并减少主观因素的影响.通过双向遍历法(BT)生成中间项集,寻找最小稀有模式.期间使用向下闭合性(反向单调性)来减少中间项集的生成数量,以进一步提高算法效率.算法保证遍历方向始终向最小稀有模式进行,即始终保持顶部为稀有模式,底部为频繁模式.假设滑动窗口中包含一个5-事务的数据流DS={t1,t2,t3,t4,t5},DS中的事务特征域为(a,b,c,d,e).每条事 务 的 详 细 特 征 值 见 表 2,其 中 {T1,T2,T3,T4,T5}是事务标识符,(a,b,c,d,e)表示特征列表.表 2 事务数据流Tid IidT1 {a,b,c,d}T2 {a,b,c}T3 {a,b,c,e}T4 {b,c,d}T5 {a,b,d}设最小支持度阈值δ=60%,根据式(3)可知,稀有模式最多只能出现2次;根据式(5)可知,频繁模式至少出现3次.以双向遍历找出最小稀有模式:首先,考虑1-项集,根据表2可知只有e的支持度小于δ,所以e是长度为1的最小稀有模式,因为1-项集不存在非空子集.其次,考虑项集长度大于1的情况,由于稀有模式的超集一定是稀有模式,所以包含e的模式都是稀有模式.从逆向考虑,由于这些包含e的超集的子集中含有稀有模式e,所以在之后的步骤中不需要再考虑e的超集,因为它们不可能是最小稀有模式.而对于频繁模式来说,其超集有可能是稀有模式,也有可能是频繁模式,所以在之后的步骤中仍需考虑a、b、c、d这些1-频繁项集.将频繁模式按其支持度升序排序,支持度越小越有可能是稀有模式.此外,根据表2可知5-项集abcde的支持度为0,所以abcde是稀有模式,尽管它没有实际意义.由于稀有模式的子集可能是稀有模式,也有可能是频繁模式,所以保留abcde.以频繁模式(a,b,c,d)作为底部(Ibottom),以稀有模式abcde为顶部(Itop),生成中间模式Imid.该中间模式Imid必须满足式(7)和式(8),其中bottom 是底部的长度,top 是顶部的长度,mid 是生成的中间项集的长度.mid=bottom+top2(7)IbottomImidItop (8)根据式(1)计算Imid的支持度;根据定义3和定义4判断Imid中的项集是频繁的还是稀有的.若是稀有的,则以Imid作为新的顶部,以Ibottom作为底部继续寻找Imid;若是频繁的,则以Imid作为新的底部,以Itop作为顶部继续寻找Imid.如此循环直至无法生成新的中间项集,即顶部和底部的长度相差1.这样确保顶部始终为稀有模式,底部始终为频繁模式,遍历方向始终向最小稀有模式进行.最后,生成顶部的所有子集并计算其支持度,若所有子集都是频繁的,则该顶部为最小稀有模式;反之,则不是.3.2.2 MRP-TB算法过程及举例真实数据流的维度较高并且具有无限性,因而无法用真实的数据流进行举例.为此,需要将数据流有限化.此外,由于 无 法提前预 知 数据流中 的数据集,所以必须对数 据 流进行 实 时处理.我们 设一个长度为5的滑动窗口 SW,并确保处理的都是最近传来 的 数 据,即 SW =5.为 简 化 说 明,我 们 仍 以3.2.1节中表2的事务为例,阈值仍设为60%.以abcde为顶部,a为底部,并通过表2对应的格空间示意图(如图1所示)来对最小稀有模式的挖掘过程进行简单说明.图中粗体实线椭圆表示支持度为非0的稀有模式,虚线椭圆表示最小稀有模式(e,ad,cd),右上角数字表示对应模式的支持数.根据式(7)可知,由abcde和a生成的中间项集长度为3,符合式(8)并且不是e的超集(根据上文可知无需考虑e的超集)的模式只有abc、abd和acd.计算支持度,可知abc为频繁模式,abd和acd为稀有模式.这里仅以abd为例,将abd作为新的顶部,而a作为底部,生成的中间项集为2-项集ad和ab.计算后可知ad是稀有的,所以将其作为新的顶部,a仍为底部,此时无法生成中间项集.由于顶部 ad的子集 a和d均为 频 繁 项 集,所 以 找 到 一 个 最 小 稀 有 模 式ad.另一个项集ab是频繁的,所以将其作为新的底部,abd仍为顶部,此时无法生成中间项集.又由于顶部abd的子集ad是稀有的,所以abd不是最小稀有模式.过程如图1红色标注所示,圆圈数字表示步骤,外围有向箭头表示执行方向,无向连线表示与之相连的项集的状态,Ibottom表示状态为底部,Itop表示状态为顶部,Imid表示中间状态,MRP 表示最小稀有模式,FP表示频繁模式,“→”表示状态转换符.不断重复上述步骤,最终从表2的窗口数据中挖掘出3个最小稀有模式:e、ad和cd.此外,由于支持度为0的模式不具有实际意义,所以如果最终的挖掘结果中含有支持度为0的模式,则将其舍弃.将上述过程用算法表示,可以得出一个高效的3165 计  算  机  学  报 2019年图 1 最小稀有模式挖掘过程演示挖掘算法,即支持双向遍历的最小稀有模式挖掘算法,用算法1和函数1表示.算法1. MRP-TB.输入:DS:事务数据流SW :滑动窗口尺寸δ:最小支持度阈值输出:MRP:最小稀有模式1.C1← {1-itemset}2.SupportiSW(C1)=CountSW (i)SW,i∈C13.MRP1← {i∈C1|SupportiSW<δ}4.FP1← {i∈C1|SupportiSWδ}5.FP1←sort{Support jSW(FP1)},j∈FP16.Clen←{len-itemset}7.Support kSW(Clen)=CountSW (k)SW,k∈Clen8.RPlen← {k∈Clen|Support kSW<δ}9.FPlen← {k∈Clen|Support kSWδ}10.RPlen←sort{Support rSW(RPlen)},r∈RPlen11.FOR all Siin RPlen{12. FOR all Sjin FP1{13.  MRPnext←BT(Sj,Si)14. }15.}16.MRP←Filtering(MRP1∪MRPnext)函数1. BT.输入:Stop:顶部项集,属于集合RPlenSbottom :底部项集,属于集合FP1δ:最小支持度阈值输出:MRPnext:长度>1的最小稀有模式1.BT (Sbottom,Stop){2. mid=bottom+top23. IF(top-bottom1){4. IF(Sbottomis rare){Stopdoes not belong to MRPnext}5. ELSE IF(all the subitems of Stopare frequent)6.   {MRPnext←Stop}7. }8. ELSE {9. Smid←generate middle items between Sbottomand Stop10. FOR all Siin Smid{11.   IF(Siis frequent)12.     BT (Si,Stop)13.   ELSE14.     BT (Sbottom,Si)15.   }16. }17.RETURN MRPnext18.}MRP-TB算法采用3种参数作为输入:事务数据流DS,滑动窗口尺寸 SW 和最小支持度阈值δ.算法结果是最小稀有模式 MRP.首先,考虑所有长度为1的模式,将其放入集合C1.根据式(1)计算出C1中所有模式的支持度,根据式(2)找出所有稀有模式.由于1-项集不存在非空子集,所以这些稀有的1-项集就 是 最 小 稀 有 模 式,并 将 它 们 放 入 集 合MRP1;然后将剩余的频繁1-项集放入FP1,并按其支持度升序排序.其次,找出所有长度为len(len 是所有不同项的个数)的模式,并将其放入集合Clen,然后根据式(1)计算它们的支持度,根据式(2)和式(4)区分稀有模式和频繁模式,并将稀有的len-项集放6期 周忠玉等:面向卫星遥测数据流的最小稀有模式挖掘方法3175Plen,将频繁的len-项集放入集合FPlen.最后,以集合RPlen为顶部,集合FP1为底部,调用双向遍历函数 BT(Bidirectional Traversal)找出所有长度大于1的最小稀有模式,结合集合 MRP1输出最终结果 MRP.BT 函 数 采 用 算 法 1 的 处 理 结 果 集RPlen和FP1作为输入,输出结果是长度大于1的最小稀有模式 MRPnext.虽然该函数与折半查找形似,但却存在许多改进之处.例如,折半查找每次(非最后一次)迭代都存在唯一确定的中间项,而 BT 函数每次迭代生成的中间项集的值和数量都无法确定,需要根据 限 制 条 件 进 行 确 定.因 为 折 半 查 找 法 在BT函数中只能确定每次迭代生成的中间项集的长度,而无法确定生 成中间项 集的具体值和数量.此外,BT 函数在算法出口处并没有直接退出,而是新增了一个关键性的限制条件,用来判别某一模式是否为最小稀有模式,如 BT 函数的第4~6行所示.3.3 MRP-TB算法效率分析从3.2.2节图1示例的分析过程可以看出,双向遍历算法 MRP-TB 只需3步就可以找到最小稀有模式ad,在图1中用 MRP表示.如果不采用双向遍历算法,而使用单向遍历算法,那么算法 MRP-TB的效率会很低.仍以图1寻找最小稀有模式ad为例,下面对采用单向遍历算法的过程进行分析:(1)以自顶向下遍历为例.第1步,单向算法首先计算abcde的支持度,并判断其是否是稀有的;第2步,以abcde为种子,生成候选集.通过计算支持度得到2 个稀有模式,即 abcd 和 abce;第 3 步,以abcd和abce为种子生成新的候选集.在算法中,由于上述生成过程是并行执行的,所以在效率分析中以单个稀有模式为种子即可(下同).计算由abcd生成的候选集的支持度,可以 得到 3 个稀有模 式,即abd、acd和bcd;第4步,以abd为种子,生成候选集ab和ad.计算其支持度,可以得到稀有模式ad;第5步,以ad为种子,生成候选集a和 d.计算它们的支持度后可以确定a和d均为频繁的;第6步,从所有稀有模式中识别出最小稀有模式ad.(2)以自底向上遍历为例.第1步,从所有的1-项集中找出所有的稀有模式.从图1中可以知道,仅e为稀有的,其它4个1-项集均为频繁的;第2步,以频繁项a为种子,生成候选集ab、ac、ad和ae.其中ad和ae为稀有的,ab和ac为频繁的;第3步,以ab为种子生成新的候选集abc、abd和abe.其中abd和abe是稀有的,abc是频繁的;第4步,以abc为种子生成候选集abcd和abce.计算它们的支持度可以确定它们均为稀有模式;第5步,从所有稀有模式中识别出最小稀有模式ad.从上述分析过程并结合图1可知,双向遍历算法仅需3步 即 可 发 现 最 小 稀 有 模 式 ad,而 单 向 的自顶向下方法需要6步,单向的自底向上方法需要5步,显然双向遍历 MRP-TB算法的效率明显优于单向遍历.3.4 MRP-TB算法复杂度分析首先,分析 MRP-TB算法的时间复杂度.(1)算法 MRP-TB的第1~4行用于区分稀有1-项集和频繁1-项集,需要计算每个项的支持度.因此,算法 MRP-TB的第1~4行的时间复杂度为O(wN).其中w 为事务的平均宽度,N 为事务数.(2)算法 MRP-TB 的第5行为频繁1-项集的堆排序过程.因此,算法 MRP-TB 的第5行的时间复杂度为O(mlog2m).其中m 为频繁1-项集的数量.(3)算法 MRP-TB的第6~9行用于区分稀有len-项集和频繁len-项集(len 是所有不同项的个数,图1中len=5,即有 a、b、c、d、e这 5 个不同的项).其中,最好的情况是 Clen中只有一个支持度不为0的稀有项集,因此只需要计算1次;最坏的情况是长度为len 的项的支持度为0或为频繁项,则需要用长度len-1并且支持度不为0的稀有项的项来代替,时间开销为 O(wN).因此,算法 MRP-TB的第6~9行的最坏时间复杂度为O(wN).(4)算 法 MRP-TB 的 第 10 行 为 稀 有len-项集的堆排序过程.因此,算法 MRP-TB的第10行的时间复杂度为O(nlog2n).其中n为稀有len-项集的数量.(5)算法 MRP-TB的第11~15行为生成最小稀有模式的过程.其中,第13行为双向遍历过程,其时间复杂度为O(log2N),进而推出算法11~15的时间复杂度为O(mnlog2N).算法第16行为过滤函数,其时间复杂度为O(1).因此,算 法 MRP-TB 所 需 的 总 时 间 开 销 为O(2wN+mlog2m+nlog2n+mnlog2N+1).之后,分析 MRP-TB算法的空间复杂度.(1)算法 MRP-TB的第1行和第6行为构造初始集合的过程,第3~4行和第8~9行是构造稀有项集和频繁项集的过程.因此空间复杂度与事务数量呈线性关系,即为O(N).(2)算法 MRP-TB的第5行和第10行是堆排序过程,所需辅助空间的复杂度为O(1).(3)从函数BT第10~15行可见,双向遍历方法3185 计  算  机  学  报 2019年是一种递归过程,并且每次递归都会创建变量 mid.由于BT函数的递归深度为O(log2 N),因此函数 BT的空间复杂度为O(log2 N).进而推到算法 MRP-TB的第11~15行的空间复杂度为O(mnlog2 N).因此,算 法 MRP-TB 所 需 的 总 辅 助 空 间 为O(N+1+mnlog2 N).4 实验结果和分析为了评估本文提出的基于双向遍历的最小稀有模式挖掘算法 MRP-TB 的有效性,使用 2015年某卫星的真 实 遥 测 数 据 流 进 行 验 证.整 个 实 验 分 为3部分,即第1部分是数据预处理;第2部分选取卫星数据流的关键特征验证所提算法的有效性,即证明算法可以找出最小稀有模式 MRP;第3部分,通过对比实验验证所提算法的效率.4.1 数据预处理实验数据是某卫星2015年的遥测数据,总共有80个特征参数.我们截取2015年3月1日~2015年5月30日这一个时间段的遥测数据作为本次实验的初始数据,约1600万条记录.由于卫星遥测数据中存在许多冗余数据,所以我们将这些数据记录以1min为单位进行压缩,然后利用一维小波去除噪声,从而可以将原始记录压缩成 约 13 万条数据记录[30].但这种压缩方式具有特殊性.因为卫星遥测数据中存在这样的特殊数据,它们在某一段时间内的数值是相同的或相近的.因此,经过离散化处理后,这些数据大都属于同一区间,会映射到同一整数上.假设在某一长度为 SW 的窗口中,有 m 个数据值映射到整数1上,n个数据值映射到整数2上,并且m+n的个数无限接近 SW ,那么Support(1)=m/ SW .假设压缩率为p%,那么对项目1和2进行压缩后,项目1的支持度Support(1)=(m×p%)/[(m+n)×p%+(SW -m-n)].由于 m+n无限接近 SW ,即 SW -m-n趋于0,所以(SW -m-n)×p%仍然趋于 0.因此,Support(1)=(m×p%)/[(m+n)×p% +(SW -m-n)×p%]=m/ SW .所以在这种特殊的数据上 使 用 这 种 压缩方式不会改变项目的支持度,也不会影响稀有模式的判定.再结合专家经验和文献[30],最终选择以1min为单位对数据进行特殊的压缩处理.此外,由于实验数据的维度较高,包含80个特征参数,因此需要对原始数据进行降维 处理.其原因如下:一 方面,算法的性能受到特征参数数量的影响.对于同一个算法来说,增加目标数据的特征参数容易造成算法的计算量增大,从而导致算法的性能下降,更为重要的是,不必要的特征参数会干扰算法的挖掘效果.因此需要通过降维来减少算法的计算.另一方面,卫星遥测数据存在许多冗余参数.所谓冗余参数是指那些变化趋势相近、存在明显函数关系的参数,由于这些参数关联性较大,符合相似的变化规 律,因 此不需要进行重复计算.所以我们通过灰关联分析从80个特征参数中选取10个相对独立的关键特征,实现参数降维,以减少数据集中的冗余参数.本次实验选取的特征如表3所示.表 3 关键参数特征描述ID  Feature ID1  10262  10303  10314  10495  10536  10547  10588  10769  1339510  13396ID表示序号,Feature ID 表示特征参数的遥测代号.针对数值型的遥测参数,需要在挖掘之前对其进行离散化处理.由于卫星遥测数据中每个参数的取值较为集中,因此等宽度划分与等深度划分都无法满足离散化要求,而基于聚类的划分方法可以直观 地 反 应 原 始 数 据 的 分 布 情 况,符 合 离 散 化 要求[31].因此,在考虑数据分布的情况下,本文对每个参数单独执行聚类,然后根据各自的聚类结果将它们的域划分为多个长度不等的不相交区间,从而得到10个参数的离散化结果.4.2 最小稀有模式挖掘分析由于实验设备受限,无法使用真实的卫星进行实验.我们将卫星遥测数据模拟成数据流作为算法的输入.整个算法代码是在集成开发环境Eclipse上完成的,编程语言是JAVA,编译器采用JDK 1.8.算法在一台服务器上运行,环境配置如下:Intel(R)Xeon(R)CPU E5-2620、2.40GHz CPU、64GB RAM、Windows Server 2008HPC Edition 64-bit OS.表4给出了本文所提算法 MRP-TB 在真实的卫星数据(简称 Real Data)和 UCI公开数据集的运行 情 况.其 中,公 开 数 据 集 包 括:Breast CancerWisconsin(简称 BCW)、Contraceptive Method Choice(简称 CMC)和 Mushroom.通过对比数据集 BCW6期 周忠玉等:面向卫星遥测数据流的最小稀有模式挖掘方法3195

[返回]
上一篇:面向搜索引擎的实体推荐综述
下一篇:基于通用串预测算法的AVS2屏幕混合内容帧间编码优化