ｄ　ｏｆ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｌｏｗｅｒ．Ｗｉｔｈ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｔｈｅ　ｂｉｇ　ｄａｔａ　ａｎｄ　ｔｈｅ　ｔｅｃｈｎｏｌｏｇｉｅｓ　ｏｆ　ｃｌｏｕｄｐｌａｔｆｏｒｍ，ｔｒａｄｉｔｉｏｎａｌ　ｓｔｏｒａｇｅ　ｄｅｖｉｃｅｓ　ｈａｖｅ　ｂｅｅｎ　ｕｎａｂｌｅ　ｔｏ　ｋｅｅｐ　ｕｐ　ｗｉｔｈ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｄａｔａ　ｔｒａｎｓｍｉｓｓｉｏｎ．Ｔｈｅｒｅｆｏｒｅ，ｉｆ　ｓｔａｔｉｃ　ｄａｔａ　ｉｓ　ｓｔｉｌｌ　ｕｓｅｄ　ａｓ　ｔｈｅ　ｏｂｊｅｃｔ　ｏｆ　ｔｈｅ　ｒｅｓｅａｒｃｈ，ｔｈｅ　ｓｔｏｒａｇｅ　ｄｅｖｉｃｅ　ｍａｙ　ｅａｓｉｌｙｌｏｓｅ　ｄａｔａ　ｗｈｅｎ　ｓｔｏｒｉｎｇ　ｔｈｅ　ｄａｔａ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ａｂｏｖｅ　ｐｒｏｂｌｅｍｓ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｍｉｎｉｍａｌｒａｒｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄ　ｔｈａｔ　ｃａｎ　ｑｕｉｃｋｌｙ　ｄｉｓｃｏｖｅｒ　ｔｈｅ　ｈｉｄｄｅｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｉｎ　ｔｈｅ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙｄａｔａ　ｓｔｒｅａｍ．Ｉｔ　ｈａｓ　ｔｈｅ　ｆｏｌｌｏｗｉｎｇ　ａｄｖａｎｔａｇｅｓ：Ｆｉｒｓｔ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｔｈａｔｉｓ，ｔｈｅ　ｍｉｎｉｍａｌ　ｒａｒｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ，ｄｏｅｓ　ｎｏｔ　ｒｅｑｕｉｒｅ　ｋｎｏｗｌｅｄｇｅ　ｉｎ　ｔｈｅ　ｓａｔｅｌｌｉｔｅ　ｆｉｅｌｄ．Ｓｅｃｏｎｄ，ｔｈｉｓ　ｐａｐｅｒ　ｒｅｆｅｒｅｎｃｅｓ　ｔｈｅ　ｓｌｉｄｉｎｇ　ｗｉｎｄｏｗ　ｔｅｃｈｎｏｌｏｇｙ　ａｎｄ　ｏｂｊｅｃｔｉｆｉｅｓ　ｔｈｅ　ｓｕｂｊｅｃｔｉｖｅ　ｐａｒａｍｅｔｅｒｓ（ｔｈａｔ　ｉｓ，ｗｉｎｄｏｗ　ｓｉｚｅ）ｓｏ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｃａｎ　ｐｒｏｃｅｓｓ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙｄａｔａ　ｓｔｒｅａｍ　ｉｎ　ｒｅａｌ　ｔｉｍｅ．Ｔｈｉｒｄ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｍｉｎｉｎｇ　ｅｆｆｉｃｉｅｎｃｙ　ｂｙ　ｏｎｌｙ　ｍｉｎｉｎｇ　ｔｈｅｍｉｎｉｍａｌ　ｒａｒｅ　ｐａｔｔｅｒｎ，ｉｎｓｔｅａｄ　ｏｆ　ａｌｌ　ｔｈｅ　ｒａｒｅ　ｐａｔｔｅｒｎｓ．Ｆｏｕｒｔｈ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ｂｉｄｉｒｅｃｔｉｏｎａｌｔｒａｖｅｒｓａｌ　ｔｅｃｈｎｉｑｕｅｓ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｔｅｎ　ｋｅｙ　ｆｅａｔｕｒｅｓ　ａｒｅ　ｓｅｌｅｃｔｅｄ　ｆｒｏｍ　ｔｈｅｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙ　ｄａｔａ　ｓｔｒｅａｍ　ｏｆ　ｓｏｍｅ　ｏｒｂｉｔｉｎｇ　ｓａｔｅｌｌｉｔｅ　ｔｏ　ｖｅｒｉｆｙ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｍｅｔｈｏｄ　ｉｎ　ｔｈｉｓｐａｐｅｒ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙｍｉｎｅ　ａｌｌ　ｔｈｅ　ｍｉｎｉｍａｌ　ｒａｒｅ　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙ　ｄａｔａ　ｓｔｒｅａｍ，ａｎｄ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｔｈｅｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｆａｓｔｅｒ　ｔｈａｎ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ｍｅｔｈｏｄｓ．Ｋｅｙｗｏｒｄｓ　 ｍｉｎｉｍａｌ　ｒａｒｅ　ｐａｔｔｅｒｎ；ｓａｔｅｌｌｉｔｅ；ｔｅｌｅｍｅｔｒｙ　ｄａｔａ　ｓｔｒｅａｍ；ｔｏｐ－ｄｏｗｎ；ｂｏｔｔｏｍ－ｕｐ；ｂｉｄｉｒｅｃｔｉｏｎａｌｔｒａｖｅｒｓａｌ；ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ；ｄａｔａ　ｍｉｎｉｎｇ１　引　言中国自主研发的北斗卫星系统是一款服务于全球的卫星导航和定位系统，在全球范围内提供定位精确度为１０ｍ，测速精确度为０．２ｍ／ｓ，授时精度为１０ｎｓ的高精度服务．它主要由３５颗卫星组成，目前广泛应用于电信、交通、救灾、测绘等诸多领域［１］．它在全球范围内持续地传输大量的实时监测数据，但由于太空环境复杂多变，卫星的健康安全时刻面临着威胁挑战［２－３］．因此，为了确保北斗卫星的正常运行，必须提供一种智能服务来自动监控卫星的运行状态，并实时地处理卫星遥测数据．卫星遥测数据是以数据流的形式呈现的．所谓数据流是指只能以预先规定的顺序被读取一次的数据序列［４］．起初，卫星产生的海量数据流大多用二三级存储设备进行存储，但随着内存技术和处理器技术的进步，使得二三级存储设备的数据处理速度越来越跟不上数据传输的速度［５］．如果数据处理的速度比数据传输的速度慢，就会导致大量的信息流失，这对于卫星的健康检测来说是不允许的．因此，有必要对卫星遥测数据流进行实时处理．但是遥测数据流的处理是十分困难的，原因如下：（１）卫星遥测数据流的传输速度非常快，需要在短时间内处理大量的数据［６］．因此除了对硬件的性能要求外，处理算法必须是高效的、健壮的．（２）遥测数据流在卫星生命周期内是无限传输的，无法进行一次性处理，也无法得到最终的处理结果［６］．所以必须对数据流进行实时分段处理，从而得出部分处理结果．（３）卫星遥测数据流的数据维度较大［６］，导致其数据容量远超二三级存储设备的容量．所以为了保存完整的未经处理的数据信息，避免数据丢失，需要进行实时的数据处理，以便及时地得到部分的处理结果．在必要时，可 以放弃已 经 处理过的 无用数据，以便接纳新的遥测数据．现如今，在轨卫星主要采用自主运行为主，地面遥控为辅的方式运行，卫星发送的遥测数据是地面人员监测卫星设备状态的唯一依据［７］．卫星由多个分系统组成，各个分系统根据需要在一些关键部件上设置遥测点，智能监控系统按一定周期对各个遥测点上的数值进行采集，包括角度、电流值、电压值、压力值、温度值、状态字、标识符、同步字等．由于采集到的卫星遥测数据是一种含有噪声和缺失值的高维大数据流，所以传统的人工服务和一般的数据分析工具无法满足卫星遥测数据的分析要求．因此，卫星监测系统需要一种智能服务来代替人工服务．它不仅能够实时地监控在轨卫星的参数状态，而且还３１２５ 计　　算　　机　　学　　报 ２０１９年种高效的遥测数据分析方法，用于实时地挖掘卫星大数据流，而模式挖掘方法恰能满足这种要求［８］．遥测数据的模式挖掘对于卫星的自动异常检测和故障诊断都非常重要，是一种具有广阔应用前景的智能监控手段［７］．目前智能服务的研究热点主要是关于移动互联网、物联网和传感器等背景下的研究［９－１２］．在卫星传感器和数据挖掘的背景下，针对卫星智能监控方面的研究绝大多数都致力于研究频繁模式挖掘，而稀有模式挖掘研究甚少［７，１３－１５］．然而在卫星态势安全预防等领域，稀有模式挖掘更有研究意义与实用价值，因为它可以从少部分信息中揭示出频繁模式挖掘无法发现的隐藏信息［１６］，而这些信息通常应用于卫星安全监测．一种做法是将挖掘出的最小稀有模式作为异常发现方法的输入数据，之后通过计算异常因子来识别卫星存在的潜在异常．例如：２０１５年，Ｈｅｍａｌａｔｈａ等人［１７］在乳腺癌异常检测的背景下，提出了一种通过挖掘稀有模式的方式来检测异常值的方法，并且通过实验证明其效率和准确率都高于基于频繁模式的异常检测方法．通过挖掘稀有模式应用于卫星异常检测的基本思想是，那些构成最小稀有模式生成源的观察结果可能是异常值，因为它与所考虑的其它观察结果相比具有“区别特征值”［１７］．因此，稀有模式挖掘作为一种重要的模式挖掘方法，可以智能地发现卫星遥测数据中的稀有模式，进而服务于在轨卫星智能监控．尽管稀有模式挖掘方法还不如频繁模式成熟，但仍然存在一些稀有模式挖掘算法，它们的应用意义及效率要远高于现有的频繁模式挖掘算法，例如 Ｈｙｐｅｒ－Ｌｉｎｋｅｄ　ＲＰＭ［１８］算法．稀有模式一般是指支持度小于指定最小支持度阈值的模式，但随着算法要求的变化，也有不同的定义．例如，Ｂｈａｔｔ和 Ｐａｔｅｌ［１９］提出的以最大约束为限制条件的稀有模式，当且仅当该模式的支持度小于指定的最小频繁支持度阈值并且大于或者等于指定的最小稀有支持度阈值时，才可以称为稀有模式．与大多数以静态数据为研究对象的模式挖掘相比，以动态数据流为对象的模式挖掘要困难许多，这是因为数据流包含一系列连续到达的、无限的和无序的数字序 列［６］，并 且这 些数 字 序 列通 常 只 能 读 取 一次［４］．为了解决这个难题，Ｃｈａｎｇ和 Ｌｅｅ［２０］提出了采用滑动窗口机制挖掘数据流的方法，得到了不错的实验结果．其后的许多研究者都采用滑动窗口技术来处理数据流，例如 Ｌｅｉ［１６］和 Ｚｈａｎｇ等人［２１］．通过滑动窗口可以对数据流进行实时地处理，从而克服处理数据流对象的困难．卫星遥测数据流面临的问题和挑战总结如下：（１）在缺乏专业领域知识的前提下，如何从遥测数据流中挖掘出最小稀有模式．已有的数据流处理方法通常会涉及很多专业领域知识［２２－２３］，从而增加了卫星遥测数据流挖掘的难度，也阻碍了研究成果的应用．（２）如何发现少部分数据中的隐藏信息．稀有模式挖掘不如频繁模式挖掘成熟，我们可以借鉴的算法很少．目前，大多数算法都是从大部分数据中挖掘出频繁模式，找出相应的规律，并将少部分数据直接舍弃．然而，卫星在绝大多数情况下都是正常运行的，那些少部分数据中可能隐藏着卫星潜在的不正常运行的重要信息．（３）如何实时处理数据流．由于数据流的诸多特性，导致以动态数据流为对象的算法比以静态数据为对象的算法要困难许多．（４）如何设定滑动窗口的尺寸．滑动窗口尺寸通常是一个主观变量，对用户敏感，不具客观性．（５）如何提高挖掘算法的效率．传统的稀有模式挖掘算法在处理卫星遥测数据流时速度较慢，因为它们首先需要生成全部的候选集，然后再从候选集中选出符合要求的模式．针对上 述 困 难 和 挑 战，本 文 做 出 的 主 要 贡 献如下：（１）针对卫星遥测数据流，本文提出了一种无需专业领域知识的挖掘算法，该算法只需要输入一定格式的遥测数据就可以挖掘出最小稀有模式．考虑到用户缺乏卫星专业领域知识，因此在设计算法时，仅以遥测数据为研究对象，不借助偏差、帆板旋转角等任何卫星领域知识．这样可以使得卫星的智能监控服务系统在挖掘模块和知识库上的耦合度较低．否则，一旦专业知识库出错或缺乏，就会导致挖掘模块无法运行．（２）本文 提 出 了一 种 最 小 稀有 模式 挖 掘 算法ＭＲＰ－ＴＢ（Ｍｉｎｉｍａｌ　Ｒａｒｅ　Ｐａｔｔｅｒｎ　ｂａｓｅｄ　ｏｎ　Ｔｏｐ－ｄｏｗｎａｎｄ　Ｂｏｔｔｏｍ－ｕｐ）．该算法通过挖掘最小稀有模式来揭示隐藏在少部分数据中的规律［１６］．与频繁模式挖掘不同，该算法以少部分卫星遥测数据流为研究对象，目的是找出在少部分数据中隐藏的有用信息．（３）本文首先使用连续小波去除卫星遥测数据的噪声，然后通过小波方差模拟出遥测数据流的第一主周期．为了使滑动窗口尺寸只与数据流本身相关，而不受人为主观因素的影响，我们以数据流的第６期 周忠玉等：面向卫星遥测数据流的最小稀有模式挖掘方法３１３５为参照，设定滑动窗口的尺寸．然后再将滑动窗口技术应用于卫星遥测数据流．该技术主要对卫星遥测数据流进行分段，使得 ＭＲＰ－ＴＢ算法能够实时地处理海量的卫星遥测数据流．（４）ＭＲＰ－ＴＢ算法无需生成全部候选集，也无需挖掘出全部稀有模式．最小稀有模式能够表征所有稀有模式，但其生成数量却远小于稀有模式．该算法通过挖掘最小稀有模式来提高算法效率．此外，为了进一步提高算法的运行速度，算法同时使用自顶向下和自底向上的双向遍历技 术来生成树的候选集，寻找最小稀有模式，提高算法效率．通过真实的卫星遥测数据对所提算法进行验证，大量实验表明本文所提的算法是有效的，并且其运行速度要高于传统算法．本文 第 ２ 节介绍稀有模式挖掘领域的相关工作；第３ 节引入模式挖掘的预备知识，给出最小稀有模式挖掘算法和示例，分析 算 法的理论复杂度；第４节进行实验并分析实验对比结果；第５节总结全文．２　相关工作目前，模式挖掘以频繁模式挖掘居多，而稀有模式挖掘相对较少［１６］．从现有的关于稀有模式挖掘的研究来看，大多数关于稀有模式挖掘的研究都是基于静态数据的．但是，随着大数据和云计算技术的飞速发展，基于动态数据的稀有模式挖掘方法也许更为实用．本文将现有的稀有模式挖掘方法分为２类（如表１所示），即基于静态数据的稀有模式挖掘和基于动态数据流的稀有模式挖掘．表 １　稀有模式挖掘分类类型１：基于静态数据Ｈｙｐｅｒ－Ｌｉｎｋｅｄ　ＲＰＭ　 Ａｐｒｉｏｒｉ－Ｉｎｖｅｒｓｅ　 ＡｆＲＩＭ　 ＲＰ－Ｔｒｅｅ类型２：基于动态数据流ＳＲＰ－Ｔｒｅｅ　 ＭＩＰ－ＤＳ　 ＭＲＳＰ－ＳＷ　 ＳＲＡＭ２．１　基于静态数据的稀有模式挖掘当从一般的密集型数据中挖掘稀有模式时，模式增长法有较大的优势．但在处理稀疏数据集和短格式 数 据 集 时，该 方 法 存 在 性 能 上 的 缺 陷．为 此，Ｂｏｒａｈ和 Ｎａｔｈ［１８］提出了 Ｈｙｐｅｒ－Ｌｉｎｋｅｄ　ＲＰＭ 算法．该算法采用基于队列的超链接数据结构，使得算法在挖掘稀有模式的同时能够自动调整链接，从而减少树结构的内存开销．由于该算法主要处理稀疏数据集和短格式数据，所以在挖掘密集型数据的稀有模式时，其性能不如模式增长类的算法．Ｙｕｎ和 Ｒｏｕｎｔｒｅｅ［２４］根 据 Ａｐｒｉｏｒｉ算 法 提 出 了一种稀有模式挖掘算法 Ａｐｒｉｏｒｉ－Ｉｎｖｅｒｓｅ．该算法可以发现“完美的零星规则”，所谓“完美的零星规则”是指在发现的规则中，模式本身以及模式中包含的所有单个项都是稀有的．在算法结构上，该算法采用与 Ａｐｒｉｏｒｉ算法相似的自下而 上 的搜索方 式．在阈值设定上，Ａｐｒｉｏｒｉ－Ｉｎｖｅｒｓｅ算法设定了２个阈值，即最小支持度阈值和最大支持度阈值．只有支持度在最小支持度阈值和最大支持度阈值之间的模式才认为是稀有的．然而，该算法只能挖掘“完美的零星规则”，对于那些“不完美的零星规则”（即在规则中，模式本身是稀有的，而单个项是频繁的）则无法挖掘．与 Ａｐｒｉｏｒｉ－Ｉｎｖｅｒｓｅ算 法 不 同，Ａｄｄａ等 人［２５］提出的 ＡｆＲＩＭ 算法没有采用 自 底向上的 搜 索方式，而是采用 了 自 顶 向 下 的 搜 索 方 法．该 算 法 通 过 将Ａｐｒｉｏｒｉ算法实例化来解决稀有模式挖掘的问题．由于 ＡｆＲＩＭ 算法没有考虑舍弃那些支持度为０（支持度为０的项通常不具有实际意义）的项，所以其运行效率不高．由于上述算法大多数是基于 Ａｐｒｉｏｒｉ算法，所以通常会生成大量的候选集，并且需要繁琐的剪枝策略．为此，这类算法需要大量的时间来执行这个过程，从而导致算法的运行效率不高．为了解决这个问题，许多研究者们开始采用基于 ＦＰ－Ｇｒｏｗｔｈ算法的树形结构来代替类 Ａｐｒｉｏｒｉ算 法的剪枝策 略，从而避免在候选集生成和剪枝步骤上浪费大量的时间．例如，Ｔｓａｎｇ 等 人［２６］提 出 的 基 于 ＦＰ－Ｔｒｅｅ结 构 的ＲＰ－Ｔｒｅｅ算法．该算法只需要对数据库进行一次扫描就可以挖掘出符合条件的稀有模式，其运行时间比使用 Ａｐｒｉｏｒｉ策略的算法少 很 多．但是该 算法仍有一些缺点，它只会生成特定类型的稀有模式，存在像 Ａｐｒｉｏｒｉ－Ｉｎｖｅｒｓｅ算法那样无法挖掘出“不完美的零星规则”的问题．２．２　基于动态数据流的稀有模式挖掘２０１２年，Ｈｕａｎｇ等人［２７］提 出 了 一 种 使 用 树 形数据结构来搜索数据流的稀有模式方法，称之为流式稀有模式树ＳＲＰ－Ｔｒｅｅ．为了与数据流的传输速度同步，ＳＲＰ－Ｔｒｅｅ算法采用了滑动窗口技术，并且该算法可以仅对数据流进行一次扫描就可以找出所需结果．此外，该算法既可以挖掘动态数据流，也可以挖掘静态数据．为了适应不断变化的数据分布，该算法设置了不同的滑动窗口大小来进行稀有 模式挖３１４５ 计　　算　　机　　学　　报 ２０１９年日期：２０１８－０９－１０；在线出 版 日 期：２０１９－０３－０４．本 课 题 得 到 国 家 自 然 科 学 基 金 （Ｕ１４３３１１６）、中 央 高 校 基 本 科 研 业 务 费 专 项 资 金（ＮＰ２０１７２０８）、南京航空航天大学研究生创新基地（实验室）开放基金（ｋｆｊｊ２０１８１６０５）资助．周忠玉，硕士研究生，主要研究方向为数据挖掘、机器学习．Ｅ－ｍａｉｌ：ｚｚｙ１４３３７７１０１５＠１６３．ｃｏｍ．皮德常（通信作者），博士，教授，博士生导师，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为数据挖掘、大数据管理与分析．Ｅ－ｍａｉｌ：ｎｕａａｃｓ＠１２６．ｃｏｍ．面向卫星遥测数据流的最小稀有模式挖掘方法周忠玉　　皮德常（南京航空航天大学计算机科学与技术学院　南京　２１１１０６）摘　要　模式挖掘是应用于卫星智能监控服务中的一项重要技术．当前频繁模式挖掘的使用率要远远高于稀有模式挖掘，然而对于卫星遥测数据流来说，频繁模式挖掘在安全监测和故障预防等方面所取得的成效不如稀有模式挖掘．因为频繁模式挖掘无法从卫星的遥测数据中揭示卫星可能存在的潜在故障．卫星遥测是持续不断进行的，所以其数据流存在数据量大、传输速度快和数据重复性高的特点．如果采用一般的稀有模式挖掘方法来挖掘卫星数据流，尽管其速度比频繁模式挖掘快，但总体上仍然较慢，不能满足卫星实时监测的需要．针对上述问题，本文提出一种可快速找出卫星遥测数据流中隐藏信息的最小稀有模式挖掘方法，它具有如下优点：（１）无需卫星领域知识；（２）引用滑动窗口技术并将主观参数（窗口尺寸）客观化，使得算法能够实时地处理数据流；（３）通过仅挖掘最小稀有模式方式来提高算法的挖掘效率；（４）该算法使用双向遍历技术提高算法的运行速度．从某在轨卫星的遥测数据流中选取１０个关键特征参数进行算法验证．实验结果表明，本文所提算法能有效地从卫星遥测数据流中挖掘出全部的最小稀有模式，并且其挖掘速度比现有的方法快．关键词　最小稀有模式；卫星；遥测数据流；自顶向下；自底向上；双向遍历；模式挖掘；数据挖掘中图法分类号 ＴＰ３１１　　　ＤＯＩ号 １０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．０１３５１Ｍｉｎｉｍａｌ　Ｒａｒｅ　Ｐａｔｔｅｒｎ　Ｍｉｎｉｎｇ　Ｍｅｔｈｏｄ　Ｆｏｒ　Ｓａｔｅｌｌｉｔｅ　Ｔｅｌｅｍｅｔｒｙ　Ｄａｔａ　ＳｔｒｅａｍｓＺＨＯＵ　Ｚｈｏｎｇ－Ｙｕ　ＰＩ　Ｄｅ－Ｃｈａｎｇ（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ａｅｒｏｎａｕｔｉｃｓ　ａｎｄ　Ａｓｔｒｏｎａｕｔｉｃｓ，Ｎａｎｊｉｎｇ　２１１１０６）Ａｂｓｔｒａｃｔ　 Ｔｈｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｉｓ　ａｎ　ｉｍｐｏｒｔａｎｔ　ｔｅｃｈｎｏｌｏｇｙ　ａｐｐｌｉｅｄ　ｔｏ　ｓａｔｅｌｌｉｔｅ　ｉｎｔｅｌｌｉｇｅｎｔ　ｍｏｎｉｔｏｒｉｎｇｓｅｒｖｉｃｅｓ．Ａｔ　ｐｒｅｓｅｎｔ，ｔｈｅ　ｕｓａｇｅ　ｒａｔｉｏｎ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｉｓ　ｍｕｃｈ　ｈｉｇｈｅｒ　ｔｈａｎ　ｔｈａｔ　ｏｆ　ｔｈｅｒａｒｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ．Ｈｏｗｅｖｅｒ，ａｓ　ｆａｒ　ａｓ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｗｈｏｓｅ　ｔａｒｇｅｔ　ｏｂｊｅｃｔ　ｉｓ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙｄａｔａ　ｓｔｒｅａｍ，ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｔｈｅ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｉｓ　ｎｏｔ　ａｓ　ｅｆｆｅｃｔｉｖｅ　ａｓ　ｔｈｏｓｅ　ｏｆ　ｔｈｅ　ｒａｒｅ　ｐａｔｔｅｒｎｍｉｎｉｎｇ　ｉｎ　ｔｅｒｍｓ　ｏｆ　ｔｈｅ　ｓｅｃｕｒｉｔｙ　ｍｏｎｉｔｏｒｉｎｇ，ｆａｕｌｔ　ｐｒｅｖｅｎｔｉｏｎ　ａｎｄ　ｓｏ　ｏｎ．Ｔｈｉｓ　ｉｓ　ｄｕｅ　ｔｏ　ｔｈｅ　ｆａｃｔ　ｔｈａｔｔｈｅ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｃａｎ　ｎｏｔ　ｒｅｖｅａｌ　ｔｈｅ　ｐｏｔｅｎｔｉａｌ　ｆａｕｌｔｓ　ａｎｄ　ｈｉｄｄｅｎ　ｄａｎｇｅｒｓ　ｔｈａｔ　ｍａｙ　ｅｘｉｓｔｉｎ　ｔｈｅ　ｃｏｍｐｏｎｅｎｔｓ　ｏｆ　ｓａｔｅｌｌｉｔｅｓ　ｆｒｏｍ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙ　ｄａｔａ　ｓｔｒｅａｍ，ａｎｄ　ｉｔ　ｃａｎｎｏｔ　ａｌｓｏ　ｐｒｏｖｉｄｅｐｒｅｖｅｎｔｉｖｅ　ｍｅａｓｕｒｅｓ．Ｓｉｎｃｅ　ｔｅｌｅｍｅｔｒｙ　ｆｏｒ　ｓａｔｅｌｌｉｔｅｓ　ｉｓ　ｃｏｎｔｉｎｕｏｕｓｌｙ　ｃａｒｒｉｅｄ　ｏｕｔ，ｔｈｅ　ｄａｔａ　ｓｔｒｅａｍ　ｏｎｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙ　ｈａｓ　ｔｈｅ　ｆｏｌｌｏｗｉｎｇ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ：ｉｎ　ｔｈｅ　ｆｉｒｓｔ　ｐｌａｃｅ，ｉｔ　ｉｎｃｌｕｄｅｓ　ａ　ｌａｒｇｅ　ａｍｏｕｎｔｏｆ　ｄａｔａ；ｉｎ　ａｎｏｔｈｅｒ，ｉｔｓ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｓｐｅｅｄ　ｉｓ　ｆａｓｔ，ａｎｄ　ｗｈａｔ　ｉｓ　ｍｏｒｅ，ｉｔｓ　ｄａｔａ　ｒｅｐｅｔｉｔｉｏｎ　ｒａｔｅ　ｉｓｈｉｇｈ．Ｉｆ　ｔｈｅ　ｃｏｍｍｏｎ　ｒａｒｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄｓ　ａｒｅ　ｕｓｅｄ　ｔｏ　ｍｉｎｅ　ｓａｔｅｌｌｉｔｅ　ｔｅｌｅｍｅｔｒｙ　ｄａｔａｓｔｒｅａｍ，ａｌｔｈｏｕｇｈ　ｉｔｓ　ｍｉｎｉｎｇ　ｓｐｅｅｄ　ｉｓ　ｆａｓｔｅｒ　ｔｈａｎ　ｔｈｅ　ｍｉｎｉｎｇ　ｓｐｅｅｄ　ｏｆ　ｔｈｅ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ，ｉｔ　ｉｓ　ｓｔｉｌｌ　ｓｌｏｗ　ｏｎ　ｔｈｅ　ｗｈｏｌｅ　ａｎｄ　ｃａｎｎｏｔ　ｍｅｅｔ　ｔｈｅ　ｎｅｅｄｓ　ｏｆ　ｒｅａｌ－ｔｉｍｅ　ｍｏｎｉｔｏｒｉｎｇ　ｆｏｒ　ｓａｔｅｌｌｉｔｅ．Ｗｈａｔｉｓ　ｍｏｒｅ，ｔｈｅ　ｇｅｎｅｒａｌ　ｒａｒｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｍａｉｎｌｙ　ｔａｋｅｓ　ｓｔａｔｉｃ　ｄａｔａ　ａｓ　ｔｈｅ　ｏｂｊｅｃｔ　ｏｆ　ｔｈｅ　ｒｅｓｅａｒｃｈ．Ｉｎｏｒｄｅｒ　ｔｏ　ｆｉｎｄ　ｏｕｔ　ａｌｌ　ｔｈｅ　ｒａｒｅ　ｐａｔｔｅｒｎｓ，ｔｈｅ　ｓｔｒａｔｅｇｙ　ｏｆ　ｇｅｎｅｒａｔｉｎｇ　ａｌｌ　ｃａｎｄｉｄａｔｅｓ　ａｎｄ　ｔｈｅｎ　ｐｒｕｎｉｎｇｉｓ　ｕｓｕａｌｌｙ　ａｄｏｐｔｅｄ，ｂｕｔ　ｗｈｉｃｈ　ｍａｙ　ｂｅ　ｌｅａｄｉｎｇ　ｔｏ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｅｘｐｌｏｓｉｏｎ　ａｎｄ　ｔｈｅ人为的预定义滑动窗口大小，始终无法赶上流数据分布的变化．该算法可以改为动态调整滑动窗口和 阈 值 的 方 式，以 适 应 不 断 变 化 的 流 数 据环境．２０１５年 Ｈｅｍａｌａｔｈａ等人［１７］提出了一种最小稀有模式挖掘算法 ＭＩＰ－ＤＳ．该算法首先将数据流转换为二进制矩阵的形式，以此矩阵为处理对象，采用滑动窗口以跟上数据流分布的变化．此外，他们还提出了一种扩展算法 ＭＩＦＰＯＤ，该算法针对 ＭＩＰ－ＤＳ算法挖掘出的最小稀有模式，计算出基于异常值的最小稀有模式因子 ＭＩＦＰＯＦ，然后根据 ＭＩＦＰＯＦ判断数据流中的异常值．但该算法存在２个缺点：（１）将数据流转换为二进制矩阵的形式，可能会丢失部分信息；（２）该算法采用了固定的最小支持度阈值，没有考虑概念漂移，不能适应数据流的变化．传统的模式挖掘有２种局限性：（１）在静态的数据集中进行挖掘；（２）结果仅是频繁模式．为了突破这种局限性，Ｏｕｙａｎｇ［８］在２０１７年提出了 ＭＲＳＰ－ＳＷ算法．该算法能够在动态的数据流中挖掘稀有模式．该算法与 ＭＩＰ－ＤＳ算法类似，采用滑动窗口技术来与数据流的变化同步．从其实验结果可知，算法是高效的．但是算法用的是合成数据，不能证明该算法在真实数据上是正确的、有效的．为了确保网络服务质量，Ｌｉｕ等人［２８］于２０１７年提出了一种针对网络性能的挖掘方法，称之为基于Ｓｐａｒｋ的稀有关联规则挖掘算法 ＳＲＡＭ．该算法采用 ＦＰ－Ｇｒｏｗｔｈ数据结构，并结合 Ｓｐａｒｋ等大数据技术，可以快速地从动态数据流中挖掘出符合条件的稀有关联规则．由于该算法的目的是确保网络服务质量，所以将重心放在 ＮＰＣ 和 ＫＱＩ的异常值检测上．据实验分析可知，该算法的准确度为８５％，仍然有较大的晋升空间．３　高效的最小稀有模式挖掘算法本节给出基于双向遍历的最小稀有模式挖掘算法．在３．１节介绍一些最小稀有模式挖掘的预备知识；在３．２节给出对应的算法和解释算法的简单示例；３．３节给出算法的效率分析；３．４节分析算法的复杂度．３．１　预备知识定义项集Ｉ＝｛ｉ１，ｉ２，…，ｉｍ｝，其中ｉｋ（１ｋｍ）为一个项，每一个项表示事务的一条信息．假设事务数据流 ＤＳ＝｛ｔ１，ｔ２，…，ｔｎ｝表示一个ｎ事务的集合，其中ｔｉ（１ｉｎ）是一组项的集合，当ｎ→ ∞时表示该数据流有无穷多个事务．如果一个项的集合Ｉ′＝｛ｉｕ，ｉｖ，…，ｉｗ｝Ｉ（ｕ，ｖ，ｗ∈［１，ｍ］）是非空的，那么称这个集合Ｉ′为项集或者模式．如果 项集Ｉ′包含ｋ 个项，则项集Ｉ′的长度｜Ｉ′｜＝ｋ，并且称该项集为ｋ－项集．一个数据流事务ｔｉ通常用一个形如〈Ｔｉｄ，Ｉｉｄ〉的二元组来表示，其中 Ｔｉｄ表示事务标识符，Ｉｉｄ表示事务Ｔｉｄ对应的模式．定义１．　滑动窗口是一种流量控制技术，在同一时段内仅允许处理窗口内部的数据，用ＳＷ （ＳｌｉｄｉｎｇＷｉｎｄｏｗ）表示．滑动窗口ＳＷ 使得算法仅允许处理数据流ＤＳ 中最近接收的事务．滑动窗口的大小用符号 ＳＷ 表示，意思是 指 数据流 ＤＳ 中最近接收的事务的数量．定义２．　项集或者模式Ｉ′的支持度定义为滑动窗口ＳＷ 中包含模式Ｉ′的事务数量占滑动窗口ＳＷ 中事务总数量的比例，用式（１）表示．其中自定义函数ＣｏｕｎｔＳＷ（Ｉ′）表示在滑动窗口ＳＷ 中包含模式Ｉ′的事务数量．Ｓｕｐｐｏｒｔ　ｉＳＷ（Ｉ′）＝ＣｏｕｎｔＳＷ （ｉ）ＳＷ，ｉ∈Ｉ′ （１）定义３．　一个模式Ｉ′被称为是稀有模式［２９］，当且仅当它在滑动窗口ＳＷ 中的支持度小于用户指定的最小支持度阈值δ，用式（２）表示．实际中通常使用其变形公式（３），这便于判断模式的类型．ＳｕｐｐｏｒｔｉＳＷ（Ｉ′）＜δ，ｉ∈Ｉ′ （２）ＣｏｕｎｔＳＷ （ｉ）＜δ× ＳＷ ，ｉ∈Ｉ′ （３）定义４．　一个模式Ｉ′被称为是频繁模式［２９］，当且仅当它在滑动窗口ＳＷ 中的支持度大于或者等于用户指定的最小支持度阈值δ，用式（４）表示．实际中会使用其变形公式（５），便于判断模式的类型．Ｓｕｐｐｏｒｔ　ｉＳＷ（Ｉ′）δ，ｉ∈Ｉ′ （４）ＣｏｕｎｔＳＷ （ｉ）δ× ＳＷ ，ｉ∈Ｉ′ （５）定义５．　如果一个稀有模式Ｉ′的所有子集都是频繁的，则称这个模式Ｉ′为最小稀有模式，记为ＭＰ，用式（６）表示．ＭＰ＝｛ｉ｜Ｓｕｐｐｏｒｔ　ｉＳＷ（Ｉ′）＜δ∧Ｓｕｐｐｏｒｔ　ｊＳＷ（Ｉ′）δ｝，ｊｉ （６）３．２　简单的算法示例和 ＭＲＰ－ＴＢ算法本节分为两个部分，第１部分介绍算法思想，第２部分举例说明算法步骤，然后给出相应算法的描述．３．２．１　ＭＲＰ－ＴＢ算法思想ＭＲＰ－ＴＢ算法是一种快速的最小稀有模式挖掘算法．该算法基 于 数据本 身，而 无需卫星 领域知６期 周忠玉等：面向卫星遥测数据流的最小稀有模式挖掘方法３１５５周期作为滑动窗口尺寸，使得算法可以实时地处理数据流并减少主观因素的影响．通过双向遍历法（ＢＴ）生成中间项集，寻找最小稀有模式．期间使用向下闭合性（反向单调性）来减少中间项集的生成数量，以进一步提高算法效率．算法保证遍历方向始终向最小稀有模式进行，即始终保持顶部为稀有模式，底部为频繁模式．假设滑动窗口中包含一个５－事务的数据流ＤＳ＝｛ｔ１，ｔ２，ｔ３，ｔ４，ｔ５｝，ＤＳ中的事务特征域为（ａ，ｂ，ｃ，ｄ，ｅ）．每条事 务 的 详 细 特 征 值 见 表 ２，其 中 ｛Ｔ１，Ｔ２，Ｔ３，Ｔ４，Ｔ５｝是事务标识符，（ａ，ｂ，ｃ，ｄ，ｅ）表示特征列表．表 ２　事务数据流Ｔｉｄ ＩｉｄＴ１ ｛ａ，ｂ，ｃ，ｄ｝Ｔ２ ｛ａ，ｂ，ｃ｝Ｔ３ ｛ａ，ｂ，ｃ，ｅ｝Ｔ４ ｛ｂ，ｃ，ｄ｝Ｔ５ ｛ａ，ｂ，ｄ｝设最小支持度阈值δ＝６０％，根据式（３）可知，稀有模式最多只能出现２次；根据式（５）可知，频繁模式至少出现３次．以双向遍历找出最小稀有模式：首先，考虑１－项集，根据表２可知只有ｅ的支持度小于δ，所以ｅ是长度为１的最小稀有模式，因为１－项集不存在非空子集．其次，考虑项集长度大于１的情况，由于稀有模式的超集一定是稀有模式，所以包含ｅ的模式都是稀有模式．从逆向考虑，由于这些包含ｅ的超集的子集中含有稀有模式ｅ，所以在之后的步骤中不需要再考虑ｅ的超集，因为它们不可能是最小稀有模式．而对于频繁模式来说，其超集有可能是稀有模式，也有可能是频繁模式，所以在之后的步骤中仍需考虑ａ、ｂ、ｃ、ｄ这些１－频繁项集．将频繁模式按其支持度升序排序，支持度越小越有可能是稀有模式．此外，根据表２可知５－项集ａｂｃｄｅ的支持度为０，所以ａｂｃｄｅ是稀有模式，尽管它没有实际意义．由于稀有模式的子集可能是稀有模式，也有可能是频繁模式，所以保留ａｂｃｄｅ．以频繁模式（ａ，ｂ，ｃ，ｄ）作为底部（Ｉｂｏｔｔｏｍ），以稀有模式ａｂｃｄｅ为顶部（Ｉｔｏｐ），生成中间模式Ｉｍｉｄ．该中间模式Ｉｍｉｄ必须满足式（７）和式（８），其中ｂｏｔｔｏｍ 是底部的长度，ｔｏｐ 是顶部的长度，ｍｉｄ 是生成的中间项集的长度．ｍｉｄ＝ｂｏｔｔｏｍ＋ｔｏｐ２（７）ＩｂｏｔｔｏｍＩｍｉｄＩｔｏｐ （８）根据式（１）计算Ｉｍｉｄ的支持度；根据定义３和定义４判断Ｉｍｉｄ中的项集是频繁的还是稀有的．若是稀有的，则以Ｉｍｉｄ作为新的顶部，以Ｉｂｏｔｔｏｍ作为底部继续寻找Ｉｍｉｄ；若是频繁的，则以Ｉｍｉｄ作为新的底部，以Ｉｔｏｐ作为顶部继续寻找Ｉｍｉｄ．如此循环直至无法生成新的中间项集，即顶部和底部的长度相差１．这样确保顶部始终为稀有模式，底部始终为频繁模式，遍历方向始终向最小稀有模式进行．最后，生成顶部的所有子集并计算其支持度，若所有子集都是频繁的，则该顶部为最小稀有模式；反之，则不是．３．２．２　ＭＲＰ－ＴＢ算法过程及举例真实数据流的维度较高并且具有无限性，因而无法用真实的数据流进行举例．为此，需要将数据流有限化．此外，由于 无 法提前预 知 数据流中 的数据集，所以必须对数 据 流进行 实 时处理．我们 设一个长度为５的滑动窗口 ＳＷ，并确保处理的都是最近传来 的 数 据，即 ＳＷ ＝５．为 简 化 说 明，我 们 仍 以３．２．１节中表２的事务为例，阈值仍设为６０％．以ａｂｃｄｅ为顶部，ａ为底部，并通过表２对应的格空间示意图（如图１所示）来对最小稀有模式的挖掘过程进行简单说明．图中粗体实线椭圆表示支持度为非０的稀有模式，虚线椭圆表示最小稀有模式（ｅ，ａｄ，ｃｄ），右上角数字表示对应模式的支持数．根据式（７）可知，由ａｂｃｄｅ和ａ生成的中间项集长度为３，符合式（８）并且不是ｅ的超集（根据上文可知无需考虑ｅ的超集）的模式只有ａｂｃ、ａｂｄ和ａｃｄ．计算支持度，可知ａｂｃ为频繁模式，ａｂｄ和ａｃｄ为稀有模式．这里仅以ａｂｄ为例，将ａｂｄ作为新的顶部，而ａ作为底部，生成的中间项集为２－项集ａｄ和ａｂ．计算后可知ａｄ是稀有的，所以将其作为新的顶部，ａ仍为底部，此时无法生成中间项集．由于顶部 ａｄ的子集 ａ和ｄ均为 频 繁 项 集，所 以 找 到 一 个 最 小 稀 有 模 式ａｄ．另一个项集ａｂ是频繁的，所以将其作为新的底部，ａｂｄ仍为顶部，此时无法生成中间项集．又由于顶部ａｂｄ的子集ａｄ是稀有的，所以ａｂｄ不是最小稀有模式．过程如图１红色标注所示，圆圈数字表示步骤，外围有向箭头表示执行方向，无向连线表示与之相连的项集的状态，Ｉｂｏｔｔｏｍ表示状态为底部，Ｉｔｏｐ表示状态为顶部，Ｉｍｉｄ表示中间状态，ＭＲＰ 表示最小稀有模式，ＦＰ表示频繁模式，“→”表示状态转换符．不断重复上述步骤，最终从表２的窗口数据中挖掘出３个最小稀有模式：ｅ、ａｄ和ｃｄ．此外，由于支持度为０的模式不具有实际意义，所以如果最终的挖掘结果中含有支持度为０的模式，则将其舍弃．将上述过程用算法表示，可以得出一个高效的３１６５ 计　　算　　机　　学　　报 ２０１９年图 １　最小稀有模式挖掘过程演示挖掘算法，即支持双向遍历的最小稀有模式挖掘算法，用算法１和函数１表示．算法１．　ＭＲＰ－ＴＢ．输入：ＤＳ：事务数据流ＳＷ ：滑动窗口尺寸δ：最小支持度阈值输出：ＭＲＰ：最小稀有模式１．Ｃ１← ｛１－ｉｔｅｍｓｅｔ｝２．ＳｕｐｐｏｒｔｉＳＷ（Ｃ１）＝ＣｏｕｎｔＳＷ （ｉ）ＳＷ，ｉ∈Ｃ１３．ＭＲＰ１← ｛ｉ∈Ｃ１｜ＳｕｐｐｏｒｔｉＳＷ＜δ｝４．ＦＰ１← ｛ｉ∈Ｃ１｜ＳｕｐｐｏｒｔｉＳＷδ｝５．ＦＰ１←ｓｏｒｔ｛Ｓｕｐｐｏｒｔ　ｊＳＷ（ＦＰ１）｝，ｊ∈ＦＰ１６．Ｃｌｅｎ←｛ｌｅｎ－ｉｔｅｍｓｅｔ｝７．Ｓｕｐｐｏｒｔ　ｋＳＷ（Ｃｌｅｎ）＝ＣｏｕｎｔＳＷ （ｋ）ＳＷ，ｋ∈Ｃｌｅｎ８．ＲＰｌｅｎ← ｛ｋ∈Ｃｌｅｎ｜Ｓｕｐｐｏｒｔ　ｋＳＷ＜δ｝９．ＦＰｌｅｎ← ｛ｋ∈Ｃｌｅｎ｜Ｓｕｐｐｏｒｔ　ｋＳＷδ｝１０．ＲＰｌｅｎ←ｓｏｒｔ｛Ｓｕｐｐｏｒｔ　ｒＳＷ（ＲＰｌｅｎ）｝，ｒ∈ＲＰｌｅｎ１１．ＦＯＲ　ａｌｌ　Ｓｉｉｎ　ＲＰｌｅｎ｛１２．　ＦＯＲ　ａｌｌ　Ｓｊｉｎ　ＦＰ１｛１３．　　ＭＲＰｎｅｘｔ←ＢＴ（Ｓｊ，Ｓｉ）１４．　｝１５．｝１６．ＭＲＰ←Ｆｉｌｔｅｒｉｎｇ（ＭＲＰ１∪ＭＲＰｎｅｘｔ）函数１．　ＢＴ．输入：Ｓｔｏｐ：顶部项集，属于集合ＲＰｌｅｎＳｂｏｔｔｏｍ ：底部项集，属于集合ＦＰ１δ：最小支持度阈值输出：ＭＲＰｎｅｘｔ：长度＞１的最小稀有模式１．ＢＴ （Ｓｂｏｔｔｏｍ，Ｓｔｏｐ）｛２． ｍｉｄ＝ｂｏｔｔｏｍ＋ｔｏｐ２３． ＩＦ（ｔｏｐ－ｂｏｔｔｏｍ１）｛４． ＩＦ（Ｓｂｏｔｔｏｍｉｓ　ｒａｒｅ）｛Ｓｔｏｐｄｏｅｓ　ｎｏｔ　ｂｅｌｏｎｇ　ｔｏ　ＭＲＰｎｅｘｔ｝５． ＥＬＳＥ　ＩＦ（ａｌｌ　ｔｈｅ　ｓｕｂｉｔｅｍｓ　ｏｆ　Ｓｔｏｐａｒｅ　ｆｒｅｑｕｅｎｔ）６．　　　｛ＭＲＰｎｅｘｔ←Ｓｔｏｐ｝７． ｝８． ＥＬＳＥ ｛９． Ｓｍｉｄ←ｇｅｎｅｒａｔｅ　ｍｉｄｄｌｅ　ｉｔｅｍｓ　ｂｅｔｗｅｅｎ　Ｓｂｏｔｔｏｍａｎｄ　Ｓｔｏｐ１０． ＦＯＲ　ａｌｌ　Ｓｉｉｎ　Ｓｍｉｄ｛１１．　 　ＩＦ（Ｓｉｉｓ　ｆｒｅｑｕｅｎｔ）１２．　　 　　ＢＴ （Ｓｉ，Ｓｔｏｐ）１３．　 　ＥＬＳＥ１４．　　 　　ＢＴ （Ｓｂｏｔｔｏｍ，Ｓｉ）１５．　 　｝１６． ｝１７．ＲＥＴＵＲＮ　ＭＲＰｎｅｘｔ１８．｝ＭＲＰ－ＴＢ算法采用３种参数作为输入：事务数据流ＤＳ，滑动窗口尺寸 ＳＷ 和最小支持度阈值δ．算法结果是最小稀有模式 ＭＲＰ．首先，考虑所有长度为１的模式，将其放入集合Ｃ１．根据式（１）计算出Ｃ１中所有模式的支持度，根据式（２）找出所有稀有模式．由于１－项集不存在非空子集，所以这些稀有的１－项集就 是 最 小 稀 有 模 式，并 将 它 们 放 入 集 合ＭＲＰ１；然后将剩余的频繁１－项集放入ＦＰ１，并按其支持度升序排序．其次，找出所有长度为ｌｅｎ（ｌｅｎ 是所有不同项的个数）的模式，并将其放入集合Ｃｌｅｎ，然后根据式（１）计算它们的支持度，根据式（２）和式（４）区分稀有模式和频繁模式，并将稀有的ｌｅｎ－项集放６期 周忠玉等：面向卫星遥测数据流的最小稀有模式挖掘方法３１７５Ｐｌｅｎ，将频繁的ｌｅｎ－项集放入集合ＦＰｌｅｎ．最后，以集合ＲＰｌｅｎ为顶部，集合ＦＰ１为底部，调用双向遍历函数 ＢＴ（Ｂｉｄｉｒｅｃｔｉｏｎａｌ　Ｔｒａｖｅｒｓａｌ）找出所有长度大于１的最小稀有模式，结合集合 ＭＲＰ１输出最终结果 ＭＲＰ．ＢＴ 函 数 采 用 算 法 １ 的 处 理 结 果 集ＲＰｌｅｎ和ＦＰ１作为输入，输出结果是长度大于１的最小稀有模式 ＭＲＰｎｅｘｔ．虽然该函数与折半查找形似，但却存在许多改进之处．例如，折半查找每次（非最后一次）迭代都存在唯一确定的中间项，而 ＢＴ 函数每次迭代生成的中间项集的值和数量都无法确定，需要根据 限 制 条 件 进 行 确 定．因 为 折 半 查 找 法 在ＢＴ函数中只能确定每次迭代生成的中间项集的长度，而无法确定生 成中间项 集的具体值和数量．此外，ＢＴ 函数在算法出口处并没有直接退出，而是新增了一个关键性的限制条件，用来判别某一模式是否为最小稀有模式，如 ＢＴ 函数的第４～６行所示．３．３　ＭＲＰ－ＴＢ算法效率分析从３．２．２节图１示例的分析过程可以看出，双向遍历算法 ＭＲＰ－ＴＢ 只需３步就可以找到最小稀有模式ａｄ，在图１中用 ＭＲＰ表示．如果不采用双向遍历算法，而使用单向遍历算法，那么算法 ＭＲＰ－ＴＢ的效率会很低．仍以图１寻找最小稀有模式ａｄ为例，下面对采用单向遍历算法的过程进行分析：（１）以自顶向下遍历为例．第１步，单向算法首先计算ａｂｃｄｅ的支持度，并判断其是否是稀有的；第２步，以ａｂｃｄｅ为种子，生成候选集．通过计算支持度得到２ 个稀有模式，即 ａｂｃｄ 和 ａｂｃｅ；第 ３ 步，以ａｂｃｄ和ａｂｃｅ为种子生成新的候选集．在算法中，由于上述生成过程是并行执行的，所以在效率分析中以单个稀有模式为种子即可（下同）．计算由ａｂｃｄ生成的候选集的支持度，可以 得到 ３ 个稀有模 式，即ａｂｄ、ａｃｄ和ｂｃｄ；第４步，以ａｂｄ为种子，生成候选集ａｂ和ａｄ．计算其支持度，可以得到稀有模式ａｄ；第５步，以ａｄ为种子，生成候选集ａ和 ｄ．计算它们的支持度后可以确定ａ和ｄ均为频繁的；第６步，从所有稀有模式中识别出最小稀有模式ａｄ．（２）以自底向上遍历为例．第１步，从所有的１－项集中找出所有的稀有模式．从图１中可以知道，仅ｅ为稀有的，其它４个１－项集均为频繁的；第２步，以频繁项ａ为种子，生成候选集ａｂ、ａｃ、ａｄ和ａｅ．其中ａｄ和ａｅ为稀有的，ａｂ和ａｃ为频繁的；第３步，以ａｂ为种子生成新的候选集ａｂｃ、ａｂｄ和ａｂｅ．其中ａｂｄ和ａｂｅ是稀有的，ａｂｃ是频繁的；第４步，以ａｂｃ为种子生成候选集ａｂｃｄ和ａｂｃｅ．计算它们的支持度可以确定它们均为稀有模式；第５步，从所有稀有模式中识别出最小稀有模式ａｄ．从上述分析过程并结合图１可知，双向遍历算法仅需３步 即 可 发 现 最 小 稀 有 模 式 ａｄ，而 单 向 的自顶向下方法需要６步，单向的自底向上方法需要５步，显然双向遍历 ＭＲＰ－ＴＢ算法的效率明显优于单向遍历．３．４　ＭＲＰ－ＴＢ算法复杂度分析首先，分析 ＭＲＰ－ＴＢ算法的时间复杂度．（１）算法 ＭＲＰ－ＴＢ的第１～４行用于区分稀有１－项集和频繁１－项集，需要计算每个项的支持度．因此，算法 ＭＲＰ－ＴＢ的第１～４行的时间复杂度为Ｏ（ｗＮ）．其中ｗ 为事务的平均宽度，Ｎ 为事务数．（２）算法 ＭＲＰ－ＴＢ 的第５行为频繁１－项集的堆排序过程．因此，算法 ＭＲＰ－ＴＢ 的第５行的时间复杂度为Ｏ（ｍｌｏｇ２ｍ）．其中ｍ 为频繁１－项集的数量．（３）算法 ＭＲＰ－ＴＢ的第６～９行用于区分稀有ｌｅｎ－项集和频繁ｌｅｎ－项集（ｌｅｎ 是所有不同项的个数，图１中ｌｅｎ＝５，即有 ａ、ｂ、ｃ、ｄ、ｅ这 ５ 个不同的项）．其中，最好的情况是 Ｃｌｅｎ中只有一个支持度不为０的稀有项集，因此只需要计算１次；最坏的情况是长度为ｌｅｎ 的项的支持度为０或为频繁项，则需要用长度ｌｅｎ－１并且支持度不为０的稀有项的项来代替，时间开销为 Ｏ（ｗＮ）．因此，算法 ＭＲＰ－ＴＢ的第６～９行的最坏时间复杂度为Ｏ（ｗＮ）．（４）算 法 ＭＲＰ－ＴＢ 的 第 １０ 行 为 稀 有ｌｅｎ－项集的堆排序过程．因此，算法 ＭＲＰ－ＴＢ的第１０行的时间复杂度为Ｏ（ｎｌｏｇ２ｎ）．其中ｎ为稀有ｌｅｎ－项集的数量．（５）算法 ＭＲＰ－ＴＢ的第１１～１５行为生成最小稀有模式的过程．其中，第１３行为双向遍历过程，其时间复杂度为Ｏ（ｌｏｇ２Ｎ），进而推出算法１１～１５的时间复杂度为Ｏ（ｍｎｌｏｇ２Ｎ）．算法第１６行为过滤函数，其时间复杂度为Ｏ（１）．因此，算 法 ＭＲＰ－ＴＢ 所 需 的 总 时 间 开 销 为Ｏ（２ｗＮ＋ｍｌｏｇ２ｍ＋ｎｌｏｇ２ｎ＋ｍｎｌｏｇ２Ｎ＋１）．之后，分析 ＭＲＰ－ＴＢ算法的空间复杂度．（１）算法 ＭＲＰ－ＴＢ的第１行和第６行为构造初始集合的过程，第３～４行和第８～９行是构造稀有项集和频繁项集的过程．因此空间复杂度与事务数量呈线性关系，即为Ｏ（Ｎ）．（２）算法 ＭＲＰ－ＴＢ的第５行和第１０行是堆排序过程，所需辅助空间的复杂度为Ｏ（１）．（３）从函数ＢＴ第１０～１５行可见，双向遍历方法３１８５ 计　　算　　机　　学　　报 ２０１９年是一种递归过程，并且每次递归都会创建变量 ｍｉｄ．由于ＢＴ函数的递归深度为Ｏ（ｌｏｇ２　Ｎ），因此函数 ＢＴ的空间复杂度为Ｏ（ｌｏｇ２　Ｎ）．进而推到算法 ＭＲＰ－ＴＢ的第１１～１５行的空间复杂度为Ｏ（ｍｎｌｏｇ２　Ｎ）．因此，算 法 ＭＲＰ－ＴＢ 所 需 的 总 辅 助 空 间 为Ｏ（Ｎ＋１＋ｍｎｌｏｇ２　Ｎ）．４　实验结果和分析为了评估本文提出的基于双向遍历的最小稀有模式挖掘算法 ＭＲＰ－ＴＢ 的有效性，使用 ２０１５年某卫星的真 实 遥 测 数 据 流 进 行 验 证．整 个 实 验 分 为３部分，即第１部分是数据预处理；第２部分选取卫星数据流的关键特征验证所提算法的有效性，即证明算法可以找出最小稀有模式 ＭＲＰ；第３部分，通过对比实验验证所提算法的效率．４．１　数据预处理实验数据是某卫星２０１５年的遥测数据，总共有８０个特征参数．我们截取２０１５年３月１日～２０１５年５月３０日这一个时间段的遥测数据作为本次实验的初始数据，约１６００万条记录．由于卫星遥测数据中存在许多冗余数据，所以我们将这些数据记录以１ｍｉｎ为单位进行压缩，然后利用一维小波去除噪声，从而可以将原始记录压缩成 约 １３ 万条数据记录［３０］．但这种压缩方式具有特殊性．因为卫星遥测数据中存在这样的特殊数据，它们在某一段时间内的数值是相同的或相近的．因此，经过离散化处理后，这些数据大都属于同一区间，会映射到同一整数上．假设在某一长度为 ＳＷ 的窗口中，有 ｍ 个数据值映射到整数１上，ｎ个数据值映射到整数２上，并且ｍ＋ｎ的个数无限接近 ＳＷ ，那么Ｓｕｐｐｏｒｔ（１）＝ｍ／ ＳＷ ．假设压缩率为ｐ％，那么对项目１和２进行压缩后，项目１的支持度Ｓｕｐｐｏｒｔ（１）＝（ｍ×ｐ％）／［（ｍ＋ｎ）×ｐ％＋（ＳＷ －ｍ－ｎ）］．由于 ｍ＋ｎ无限接近 ＳＷ ，即 ＳＷ －ｍ－ｎ趋于０，所以（ＳＷ －ｍ－ｎ）×ｐ％仍然趋于 ０．因此，Ｓｕｐｐｏｒｔ（１）＝（ｍ×ｐ％）／［（ｍ＋ｎ）×ｐ％ ＋（ＳＷ －ｍ－ｎ）×ｐ％］＝ｍ／ ＳＷ ．所以在这种特殊的数据上 使 用 这 种 压缩方式不会改变项目的支持度，也不会影响稀有模式的判定．再结合专家经验和文献［３０］，最终选择以１ｍｉｎ为单位对数据进行特殊的压缩处理．此外，由于实验数据的维度较高，包含８０个特征参数，因此需要对原始数据进行降维 处理．其原因如下：一 方面，算法的性能受到特征参数数量的影响．对于同一个算法来说，增加目标数据的特征参数容易造成算法的计算量增大，从而导致算法的性能下降，更为重要的是，不必要的特征参数会干扰算法的挖掘效果．因此需要通过降维来减少算法的计算．另一方面，卫星遥测数据存在许多冗余参数．所谓冗余参数是指那些变化趋势相近、存在明显函数关系的参数，由于这些参数关联性较大，符合相似的变化规 律，因 此不需要进行重复计算．所以我们通过灰关联分析从８０个特征参数中选取１０个相对独立的关键特征，实现参数降维，以减少数据集中的冗余参数．本次实验选取的特征如表３所示．表 ３　关键参数特征描述ＩＤ　 Ｆｅａｔｕｒｅ　ＩＤ１　 １０２６２　 １０３０３　 １０３１４　 １０４９５　 １０５３６　 １０５４７　 １０５８８　 １０７６９　 １３３９５１０　 １３３９６ＩＤ表示序号，Ｆｅａｔｕｒｅ　ＩＤ 表示特征参数的遥测代号．针对数值型的遥测参数，需要在挖掘之前对其进行离散化处理．由于卫星遥测数据中每个参数的取值较为集中，因此等宽度划分与等深度划分都无法满足离散化要求，而基于聚类的划分方法可以直观 地 反 应 原 始 数 据 的 分 布 情 况，符 合 离 散 化 要求［３１］．因此，在考虑数据分布的情况下，本文对每个参数单独执行聚类，然后根据各自的聚类结果将它们的域划分为多个长度不等的不相交区间，从而得到１０个参数的离散化结果．４．２　最小稀有模式挖掘分析由于实验设备受限，无法使用真实的卫星进行实验．我们将卫星遥测数据模拟成数据流作为算法的输入．整个算法代码是在集成开发环境Ｅｃｌｉｐｓｅ上完成的，编程语言是ＪＡＶＡ，编译器采用ＪＤＫ　１．８．算法在一台服务器上运行，环境配置如下：Ｉｎｔｅｌ（Ｒ）Ｘｅｏｎ（Ｒ）ＣＰＵ　Ｅ５－２６２０、２．４０ＧＨｚ　ＣＰＵ、６４ＧＢ　ＲＡＭ、Ｗｉｎｄｏｗｓ　Ｓｅｒｖｅｒ　２００８ＨＰＣ　Ｅｄｉｔｉｏｎ　６４－ｂｉｔ　ＯＳ．表４给出了本文所提算法 ＭＲＰ－ＴＢ 在真实的卫星数据（简称 Ｒｅａｌ　Ｄａｔａ）和 ＵＣＩ公开数据集的运行 情 况．其 中，公 开 数 据 集 包 括：Ｂｒｅａｓｔ　ＣａｎｃｅｒＷｉｓｃｏｎｓｉｎ（简称 ＢＣＷ）、Ｃｏｎｔｒａｃｅｐｔｉｖｅ　Ｍｅｔｈｏｄ　Ｃｈｏｉｃｅ（简称 ＣＭＣ）和 Ｍｕｓｈｒｏｏｍ．通过对比数据集 ＢＣＷ６期 周忠玉等：面向卫星遥测数据流的最小稀有模式挖掘方法３１９５