（计算机应用技术专业论文）可继承性birch研究及其在飞行品质监控中的应用.pdf

中国民航大学硕士学位论文 摘要 民用航空在当今社会中已成为国民经济发展的重要驱动力量。如何提高飞行 安全成为我国民航快速发展中的一个不可回避的问题。目前，世界上一些发达国 家将飞行数据运用于日常监控工作，获益匪浅。将数据挖掘方法应用于飞行品质 监控已成为一重要课题。 在对数据挖掘中的多种聚类算法( 如k - m e a n s 、b i r c h 等) 进行系统和深 入地探讨和研究的基础上，本文主要做了以下的工作：深入研究了b i r c h 算法， 设计了启发式阈值估计方法；结合k - m e a n s 算法对b i r c h 进行改进；结合x m l 技术设计了可继承性b i r c h 算法模型，有效地对海量数据进行聚类；将可继承 性b i r c h 算法应用于o a r 数据处理。 可继承性b i r c h 算法增强了b i r c h 算法的灵活性，解决了b i r c h 算法中 处理新增数据效率较低的缺陷。通过实验表明，在增加数据特别是多次增加数据 的情况下聚类，可继承性b i r c h 算法效率明显优于b i r c h 算法。 本文研究表明，可继承性b i r c h 算法在飞行品质监控领域表现出了较为良 好的性能，具有一定的应用前景。 关键词：聚类；飞行品质监控；快速存取记录器 中国民航大学硕士学位论文 a b s t r a c t n o w a d a y s , c i v i l a v i a t i o nh a sb e c o m em o r ea n dm o r ei m p o r t a n ti nt h e d e v e l o p m e n to fn a t i o n a le c o n o m y h o wt oe n h a n c et h ef l i g h ts a f e t yi sa nu n e v a d a b l e q u e s t i o ni nt h ed e v e l o p m e n to fc i v i la v i a t i o ni no u rc o u n t r y u pt od a t e ，f l y i n gd a t ah a s b e e nu s e di nd a i l yf l i g h to p e r a t i o n a lq u a l i t ya s s u r a n c eb ym a n y d e v e l o p e dc o u n t r i e s ， a n dt h ec o u n t r i e sb e n e f i tf r o mi t a p p l y i n gd a t am i n i n gi nf l i g h to p e r a t i o n a lq u a l i t y a s s u r a n c eh a sb e c o m ea ni m p o r t a n tt a s k b a s e do ns y s t e m sa n a l y s i sa n dl u c u b r a t eo nv a r i o u sc l u s t e r i n ga l g o r i t h m si n d a t am i n i n g ( e g k - m e a n s ，b i r c he t c ) ，t h ef o l l o w i n gw o r kh a v eb e e nd o n ei nt h i s p a p e r ：h e u f i s t i ca l g o r i t h mf o rt h r e s h o l dh a sb e e np r e s e n t e d ，k - m e a n sh a sb e e nj o i n e d , i m p r o v et h ec l u s t e r i n gr e s u l t ；i n h e r i t a b l eb i r c ha l g o r i t h m sp r o c e s s i n gm o d e lh a s b e e np r e s e n t e d ，c o m b i n e dw i t hx m l t e c h n o l o g yb i r c hc l u s t e r i n gf e a t u r et r e e s s a v i n ga n dp a r s i n ga l g o r i t h m sh a v eb e e np r e s e n t e da n dr e a l i z e d ，c l u s t e r i n gh u g ed a t a e f f e c t i v e l y , a n da p p l yi ti nq a r ，a n a l y z et h er e s u l t s c o r r e l a t i o ne x p e r i m e n t sh a v eb e e nm a d ef o rv a l i d a t i n gt h ea l g o r i t h m s v a l i d i t y , i n e f f e c t i v e l yp r o c e s s i n gn e wd a t ab yb i r c ha l g o r i t h mh a sb e e ns o l v e d i ti ss h o w e d i ne x p e r i m e n tt h a ti n h e r i t a b l eb i r c ha l g o r i t h m si sm o r ee f f e c t i v et h a tn e wa d d e d d a t ao n l ya d do n c eo ra d dn e wd a t am u l t i p l yt o t h ei n i t i a ld a t a i ti ss h o w e di nt h i sp a p e r , i n h e r i t a b l eb i r c ha l g o r i t h mi se f f e c t i v ei nf l i g h t o p e r a t i o n a lq u a l i t ya s s u r a n c e ，a n dw i l la p p l i e di nt h ef u t u r e k e yw o r d s ：c l u s t e r i n g ；f o q a ；q a r 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：华-1 日期：鲨叁：竖h 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名： 导师签名：也日 期：吵? 中国民航大学硕士学位论文 1 1 研究的背景和意义 第一章绪论 飞行品质监控( f o q a ) 1 1 】能够及时发现飞机运行过程中出现的各种超限事 件，是保证飞行安全的重要手段。飞行品质监控( f o q a ) 特指利用机载设备采 集和记录的飞行数据对机组操纵、发动机等进行事件探测和趋势分析的一种方 法，在中国民航俗称为“q 娘工作 。其目的是及时发现机组操纵、发动机状 况以及航空器性能等方面存在的问题，分析查找原因，掌握安全动态，采取针对 性措施，消除隐患，确保飞行安全。1 9 9 7 年，民航总局要求所有运输机加装快 速存取记录器( q a r ) 设备，并对每个航班实施飞行品质监控，为保证飞行安 全，加快培养新飞行员提供了有效的科学手段，有利于事前的安全管理。飞行品 质监控结果是飞行技术检查、飞机维修、安全评估和不安全事件调查的重要依据。 目前，飞行品质监控工作已经成为各航空公司的一项日常性工作。监控范围包括 机组操纵品质和发动机状况。 q a r ( q u i c ka c c e s sr e c o r d e r ) 快速存取记录器【1 j 指无保护装置的机载飞行 数据记录设备，主要用于日常运营时获取飞行数据。根据飞机类型和生产日期不 同，q a r 的容量、所记录参数的格式及参数数量也不同。其作为一种先进的监 控手段，有着重大的作用和无限的生命力，主要表现在：1 ) 在分析译码数据的 基础上，及时、准确地挖掘存在的安全隐患和预测可能出现的趋势性问题，制定 和实施有效的安全措施，对当事人、机进行必要地培训、检查，将问题苗头遏制 在萌芽状态。2 ) q 嘘所提供的监控信息有助于企业决策。q a r 能够帮助航空 公司制定正确的运行程序，提高运行效率。3 ) q a r 能够帮助飞行员及时准确地 挖掘安全隐患和预测可能出现的趋势性的问题，并对症下药，使之改善，督促飞 行员严格执行公司标准。如果在阶段性、局部性安全管理中，对重点航线、重点 机场、飞机关键部件、技术重点人员等方面进行重点监控，完善、开发相应的数 据库，就能够为飞机放飞和人员培训提供科学的依据。 目前世界上一些发达国家将飞行数据运用于日常监控工作，获益匪浅。美国 的飞行事故率，从1 9 5 0 年的万时率3 6 降到目前的o 1 5 就是很明显的实例。因 此，对q a r 数据进行深入分析并加以利用，能有效改进飞行品质，提高安全系 数，改善飞行效益【z j 。 数据挖掘【”】是信息处理领域最有前途的- - i - j 交叉学科，旨在从大量的、不 完全的、有噪声的数据中，自动提取隐含在其中的模式和知识。聚类是数据挖掘 中国民航大学硕士学位论文 领域的一种重要方法，将聚类技术应用于q a r 工作具有重要意义。本文在对数 据挖掘中的多种聚类算法( 如k - m e a n s 、b i r c h 等) 进行系统深入地探讨和研 究的基础之上，设计了可继承性b i r c h 聚类算法1 5 】，该算法能自动高效地提取 隐含在q a r 数据中的模式和知识，也能够为其他挖掘算法提供支持。 1 2 国内外研究现状 聚类有着广阔的应用，早期的聚类分析研究工作主要集中在生物学和动物学 领域，目前已经扩展到更多的研究和应用领域中，如数据挖掘，模式识别，图像 分割，信息检索，统计学，数据库技术，医学和生物信息学，以及无线网络等诸 多方面。在数据挖掘中，可以利用聚类方法来分析数据以发现有意义的聚类；在 模式识别中，聚类方法也能够用来分析数据的潜在的特征模式；图像处理中也可 以借助聚类方法来发现有意义的图像前景；在信息检索、搜索引擎急剧发展的互 联网时代，利用文本聚类来实现新闻和资讯信息的自动分类是各大搜索公司采用 的一种主要方法；此外，在无线网络中，人们也逐渐采用聚类技术来合理地选择 路由结点以提高效率。总之，聚类算法的研究和应用越来越得到人们的关注 聚类技术应用于飞行记录数据的分析中，把相似的飞行记录聚成一类，使得 在飞行分析中不必去单独研究每次飞行记录，把更多的精力放在研究特定飞行模 式。方便人们发现和理解普通模式，识别异常的飞行模式【6 j 。 k 均值和层次聚类技术已经被用于空中交通中的雷达跟踪数据处理，主要处 理步骤是：1 ) 对源数据矩阵进行主成分分析；2 ) 确定每个类的初始中心点；3 ) 将每个飞行记录分到最近的类中；4 ) 根据需要进行迭代处理。 国外的一些研究资料表明，在对大量飞行数据进行分类以发现超限事件，并 进一步找出超限事件的原因、提出解决方案以消除危险隐患的过程中也用到了聚 类方法。在参数数量很多，数据量急速增加的条件下，采用聚类技术，将相似的 飞行记录聚集到一类，用类中某些具有代表性的对象来代替这个类，这就可以大 大压缩要处理的数据，加速了分类的进程。 在国内，q 讯工作开始于1 9 9 7 年，目前国内航空公司主要实现了q a r 数 据在以下方面的应用：1 ) 飞行品质监控。主要用于航后讲评，但没有趋势分析 和综合评述；2 ) 飞机性能方面。主要是根据飞机的出厂数据分析其性能，以达 到设计飞行计划，实施经济飞行的目的，但是目前的应用深度还不够；3 ) 维修 方面。主要用于部分直观参数的观察和观察基础上的视情维修，还无法做到趋势 分析和在此基础上的结构维修；4 ) 安全评估方面。由于尚未建立起获取数据的 有效机制，造成采样样本不足，无法产生可靠的结论；5 ) 事故分析是目前该数 据的主流应用领域，已有三维再现飞行状态的相关成果。 2 中国民航大学硕士学位论文 1 3 论文研究内容 在对多种聚类算法( 如k - m e a n s 、b i r c h 等) 进行系统深入地探讨和研究 的基础上，对b i r c h 算法进行了改进，设计了启发式阈值估计方法，将b i r c h 算法与k - m e a n s 相结合，同时设计了一种可继承性b i r c h 算法模型，实现了可 继承性b i r c h 算法，并将其应用于o a r 数据处理。 本文主要完成了以下几个方面的工作： 1 对b i r c h 算法进行了改进，设计了启发式阈值估计方法，有效减少树的 重建次数，并将b i r c h 算法与k - m e a n s 结合，实现了更好的聚类； 2 结合x m l 技术设计了可继承性b i r c h 算法模型； 3 用大量的实验验证了可继承性b i r c h 算法的正确性，并对b i r c h 算法和 可继承性b i r c h 算法的效率进行了对比； 4 将o a r 数据进行相关处理，并用可继承性b i r c h 算法对o a r 数据进行 聚类，将可继承性b i r c h 算法应用于飞行品质监控。 1 4 论文组织结构 本文在绪论中介绍了可继承性b i r c h 算法应用于飞行品质监控的研究背景 和意义，以及国内外研究现状，并且在总体上介绍了可继承性b i r c h 研究的主 要内容及本文主要完成的工作。 第二章主要介绍数据挖掘技术的聚类算法与飞行品质监控。 第三章主要介绍聚类中的b i r c h 算法，设计了启发式阈值估计方法，对 b i r c h 的阈值设置进行了改进，并详细描述了结合k - m e a n s 算法对b i r c h 算法 进行改进的方法。 第四章详细描述了基于x m l 技术的可继承性b i r c h 算法模型，以及可继 承性b i r c h 算法的实现过程和效率对比。 第五章主要介绍可继承性b i r c h 算法在飞行品质监控中的应用。 第六章是对全文的总结以及对数据挖掘技术应用于飞行品质监控发展前景 的展望。 3 中国r 航大学碰十学位论文 第二章聚类算法及飞行品质监控 2 1 数据挖掘技术 2 1 1 数据挖掘概念和过程 数据挖掘是从大型数据集( 可能是不完全的、有噪声的、不确定性的、各种 存储形式的) 中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的 过程。这个定义说明了：) 数据源必须是真实的、大量的、含噪声的：2 ) 发现 的是用户感兴趣的知识：3 ) 发现的知识是可接受、可理解、可运用的，所有发 现的知识都是相对的，是有特定前提和约束条件、面向特定领域的，同时还要易 于被用户理解。 数据挖掘所依赖的数据来源多种多样，可以是常用的关系数据库、事务数据 库、文本数据库、多媒体数据库等，主要取决于用户的目的及所处的领域。数据 挖掘过程描述如图21 所示。 = t i 的情况下，需利用所有的t i 的叶条目重建一棵其阈值为t i + l 的c f 树 t i + l ，且t i + l 的大小不大于s i 。 规约定理：设c f 树t i ，阈值为面，高h i ，结点数s i ，在树的每个结点中， 元组被标为0 一n l 【1 ，从根结点到叶结点的路径为( i l ，i 2 , - - , i h 1 ) ，如果i 1 ( 1 ) = i 1 ( 2 ) ，i j ( 1 ) i j ( 2 ) ，贝j j ( i l ( 1 ) ，i 2 ( 1 ) ，i h 一1 ( 1 ) ) ( i 1 ( 2 ) ，i 2 ( 2 ) ，i h - 1 ( 2 ”。 每一个叶结点惟一对应一条路径，因此，路径及叶结点两个术语可以交换使 用。 o l dt r e e f r e e d 、 雕蒸蒸缓缀阂霎箧 n e wt r e e o l d c u l t e n t p a t h n e w c l o s e s t p a t hn e w c u r r e n t p a t h 图3 - 2 重建树算法示意图 重建算法的示意图如图3 2 所示，对旧树逐条路径进行扫描并释放，同时， 对新树逐条路径生成。新树开始是n u l l ，o l d c u r r e n t p a t h 初始化时是旧树的最 左路径。 1 在新树中生成对应的n e w c u r r e n t p a t h 拷贝在旧树中属于o l d c u r r e n t p a t h 的结点到新树的最右路径；调用该 n e w c u r r e n t p a t h 。 1 4 中国民航大学硕士学位论文 2 将在o l d c u r r e n t p a t h 中的叶条目插入到新树 由于有了新的阈值，在o l d c u r r e n t p a t h 中的每一个叶条目都要对新树进行测 试，判断是由已存在的叶条目吸收，还是存放在一个新的叶条目中，在 n e w c l o s e s t p a t h 中，自上而下需采用新树中的最近准则。若符合准则而且 n e w c l o s e s t p a t h 是在n e w c u r r e n t p a t h 之前，则插入到n e w c l o s e s t p a t h 中，并从 n e w c u r r e n t p a t h 中删除。 3 释放o l d c u r r e n t p a t h 及n c w c u r r e n t p a t h 中的空间 一旦处理完毕o l d c u r r e n t p a t h 中的所有叶条目，沿着o l d c u r r e n t p a t h 的结点 就可以从旧树中删除。有可能沿着n e w c u r r e n t p a t h 路径的某些结点是空的，原 因是原来对应这条路径的叶条目已经向前推进了，在这种情况下，将空结点从新 树中删除。 4 处理旧树中的下一条路径 在旧树中若存在路径，就将o l d c u r r e n t p a t h 设置到下一条路径上，重复上述 步骤。 由上可看出，通过增加阈值t ，用较少的空间就可以重建一棵更小的c f 树。 3 1 3b i r c h 算法步骤 b i r c h 算法的主要工作步骤如下： 图3 - 3b i r c h 算法步骤图 1 5 中国民航大学硕士学位论文 b i r c h 每阶段主要完成的工作如下： 第一阶段： 扫描所有数据，建立初始化的c f - 树 把稠密数据分成簇，稀疏数据作为孤立点对待 第二阶段：( 可选的) 阶段3 的全局或半全局聚类算法有着输入范围的要求，以达到速度 与质量的要求 在阶段1 的基础上，建立一个更小的c f 树 第三阶段： 补救由于输入顺序和页面大小带来的分裂 使用全局半全局算法对全部叶结点进行聚类 现有的聚类算法可以被改进，用于簇与簇之间的聚类 一把中心点作为簇的代表，把每个簇作为单个点来对待 一把簇作为中心点的n 次重复 一直接使用c f 向量信息 第四阶段：( 可选的，精确化) 把阶段3 的中心点作为种子，将数据点重新分配到最近的种子上， 保证重复数据分到同一个簇中 添加簇标签 3 2 启发式阈值估计法 3 2 1b i r c h 的阈值问题 在b i r c h 算法的第一阶段，设置初始化阈值、扫描数据及将数据点插入到 树中。若内存超出范围，则修正阈值，通过重新将旧树的叶条目插入到新树的 c f - t r c c 中，重建一个更小的c f - t r c c 。 一个合适的阈值将大大减少树的重建次数。因为初始化阈值t 0 是动态地增 加，在开始时可以将它调整到很低。如果初始化时t o 设置的太大，就会造成无 法充分利用内存和c f - t r c c 不够详细的现象，因此t o 的设置应保守一些，b i r c h 缺省的设置是0 ，有丰富经验的用户可以根据具体情况设置合适的初始值。 当阈值为t i 时，在扫描了n i 个数据点后，造成内存溢出。基于已经扫描数 据的比例及已经建立的c f - t r c c ，试图估计下一个合适的阈值上“1 是一个非常困难 的问题。 由于b i r c h 算法在判定簇之间是否能进行合并时采用的是基于中心点的统 1 6 中国民航大学硕士学位论文 一阈值聚类算法，对规模相差较大的簇的聚类结果较差，同时该算法无法实现对 任意形状的簇的聚类。针对这个问题，已经有一种多阈值b i r c h 聚类( m b i r c h ) 【刎算法被提出。m b i r c h 算法通过给每个叶结点设置不同的阈值，将阈值作为 簇的属性，充分考虑簇与簇之间体积的不一致性，来提高算法的精确性。在结点 分裂算法中引入分割因子来最大限度的保持原结点的聚类特征信息，将结点中的 聚类特征合理的划分开来【2 。阈值的设置对树的重建以及聚类的精确性有很大 的影响，在m b i r c h 算法中多阈值是通过取叶结点相邻条目之间的距离的平均 值来设置，这样设置只简单考虑叶结点中条目的距离，在树的重建过程中合并距 离最近的两个条目。而本文提出的启发式阈值设置方法，是在充分考虑数据分布 的情况下，通过对阈值的估计及一定范围内的调整，来提升阈值。采用启发式算 法来设置阈值，将能够大大减小树的重建次数，有效提高聚类结果的精确性。 3 2 2m b i r c h m b i r c h 将阈值作为簇的属性，为每个簇设立一个阈值，即c f = ( n j ，嬲，t ) ，其中t 表示该簇的阈值。非叶结点中c f 也包含阈值t ，用来存储 子结点的阈值的信息。 合并定理：假定n ( n 2 ) 个簇c 进行合并，n 个簇的聚类特征表示为 c f , i ( m ，虿，踺，王) ，其中( i = 1 ，2 ，3 ，n ) ，那么合并后的簇为w ，其聚 类特征表示为c 巴一( ，l s ，s s ，r ) ： n - 二。m ( 1 )么_ ，l 。l 历一2 。丽( 2 )z i 。 。 s s 一i ? - 1 氍( 3 )z 一 it m a x ( d i s t ( w j n e a n ，c m e a n ) + 1 ) ( 4 ) 一一 n ：= 其中，e 朋阳n m l s ；ic i m e a n - 等，形朋明刀- 祷，合并后簇的聚类特 厶i - 1 征表示了两个聚类合并后的渐增性【刎。 m b i r c h 算法中将一个叶结点中各条目的阈值设置为该叶结点相邻条目之 间距离的平均值。所以根据叶结点的不同，结点内条目的阈值也不同。 m b i r c h 算法将阈值作为簇的属性，为叶结点中的簇建立一个阈值，聚类 特征如上文所述。非叶子结点的c f 也包含阈值t ，用来存储子结点的阈值的信 息，描述子结点中簇与簇的关系。在插入过程中综合考虑插入条目与中心点的距 离和簇的阈值，来提高条目插入的准确性；在结点分裂过程中引入分割因子p ， 通过分割因子的设定尽可能最大限度的保持原结点的聚类特征，将结点中的聚类 1 7 中国民航大学硕士学位论文 特征合理的划分开i 刎。 多阈值b i r c h 算法在保留原b i r c h 算法的基础上，充分考虑到簇大小的 不一致性，针对不同大小的簇采用不同的阈值，在一定程度上减少了聚类特征树 的重建次数，降低了时间复杂度。由于结点分裂采用了分割因子，能得到较好的 聚类结果，提高了算法的精确性。 3 2 4 启发式阈值估计算法的提出 如果当前的c f - 树占据了所有的内存，在b i r c h 算法中，将根据已经扫描 数据的比例以及已经建立的c f 树估计下一个阈值互1 ，其主要做法是将阈值提 升为所有叶条目的“最近邻对 之间的距离的平均值，这样，相似的两个叶条目 将合并成一个。 在m b i r c h 算法中，多阈值的设置实际上就是对不同叶结点设置不同的条 目阈值。对于一个叶结点，它所包含的条目的阈值取该叶结点相邻条目之间距离 的平均值。每次重建树之前，都要通过寻找每个叶结点相邻条目对，计算它们距 离的平均值，来提升各阈值，使得各叶结点能吸收更多的数据对象。 另外，在插入过程中由于结点分裂造成内存不够用，除了采用延迟分裂法来 处理之外，还可通过提升阈值来吸收更多的结点。所以阈值的设置在树的重建过 程中起着重要的作用，它的设置是否合理直接影响树的重建次数、以及算法处理 的时间。 阈值的估计是b i r c h 算法聚类过程中一个重要的步骤，如果设置不合理将 会降低算法的效率，并且难以获得较好的聚类结果。本文设计了启发式阈值估计 方法，估计、调整多阈值b i r c h 算法的阈值，以达到高效聚类的目的。 假设目前某叶结点中条目的阈值为z ，它所吸收的数据对象个数为m ，n 为总的数据对象个数，c 为当前已经形成的叶结点的个数。 启发式阈值估计法主要包括以下几个步骤： 1 试图给出某个叶结点中条目的阈值霉+ 。，使m + 。一m i n ( k n l ，n c ) 。系数 l k c y e a r s i b l