（计算机应用技术专业论文）数据挖掘网格若干关键技术研究.pdf

北京邮电大学博士学位论文 数据挖掘冈格若干关键技术研究 摘要 本论文的主旨是研究数据挖掘网格的架构及其若干关键技术，为数据挖掘网 格系统的设计和实施提供参考。 论文通过研究当前数据挖掘面临的挑战和网格计算技术的发展，展现了当前 数据挖掘网格的研究现状和最新研究动态；着重研究了电信领域数据挖掘网格的 熟点问题、技术难度等方面，并对电信领域数据挖掘网格的若干亟待解决的关键 技术进行了深入研究 本文中作者主要的研究和设计工作如下： 夺综述了数据挖掘算法的研究现状和网格系统的发展状况；通过分析比较多个 主要的网格架构和网格系统，给出了这些网格架构的特点和不足。指出数据 挖掘网格的实施是解决当前电信领域数据分析和数据挖掘难题的主要方案。 通过分析电信数据挖掘应用的需求，分析比较研究了网格系统的基本架构， 尝试提出了数据挖掘网格的概念，并提出和设计了一种数据挖掘网格的体系 结构，该系统结构依据分层思想，把数据挖掘网格的架构自上而下从对外接 口层到基本资源层总共划分为六层，该架构能够提供从数据挖掘接口服务到 数据挖掘的领域应用的支撑，能够支撑数据挖掘的分稚计算，也能很好的支 撑并行计算资源和数据的分配。文中从多个角度详细描述了数据挖掘网格的 层次结构，体系特征，模块功能，动态特性，交互关系。 夺提出了对三大类经典数据挖掘算法和基于图的数据挖掘算法的并行化算法， 同时总结了挖掘算法并行化的通用方法；提出了网格调度算法来优化并行化 任务的执行效率，并且对并行算法及其调度算法都进行了性能分析，这些研 究为数据挖掘并行算法的基本实现提供了保障，也验证了数据挖掘网格的可 行性和实用性 夺通过研究元数据模型的当前标准发现现有元数据标准不能支持数据挖掘网 格的元数据模型，因此提出适合数据挖掘网格需要的元数据模型；元数据模 型提供了对于数据挖掘网格架构的各个层面的支撑，该元数据模型的核心是 支撑了分布式数据挖掘的算法元数据和网格系统的元数据；为了规范化和利 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 于计算机之间的信息交互，把元数据模型用x m ls c h w a 进行了描述，并详 细描述了一个实例 通过研究元数据服务的机制，根据元数据服务的应用需求，提出了利w e b 服务技术构建数据挖掘的元数据服务系统结构，并给出了一个典型的利用 w e b 服务方式提供的数据挖掘元数据服务的实例。 数据挖掘网格原型系统设计实现和验证为了展现数据挖掘网格体系结构设 计的正确性和可行性，设计实现了数据挖掘的一个原型；通过原型系统的运 行，展示了数据挖掘网格的工作过程，并且通过具体的数据试验，验证了数 据挖掘网格系统的可行性和高效性。 关键词：数据挖掘，网格架构，并行计算，任务调度，元数据模型，元数据服务 n 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 a b s t r a c t t h i sd i s s e r t a t i o nr e s e a r c h e st h ed a t am i m n ga r c h i t e c t u r ea n dt h ek e yt e c h n o l o g i e ss ot h a tt h e d e s i g na n dc o n s t r u c t i o no ft h ed a t am i n i n gg r i d ( d m g ) c a nb cg u i d e d s e v e r a lc h a l l e n g e so nt h ec o m p u t a t i o no ft h ed a t am i n i n ga r ei n t r o d u c e di nt h ef i e l do f t e l e c o m t h i sd i s s e r t a t i o nt e n t a t i v e l yp r o p o s e st h ep r i n c i p l eo fd a t am i n i n g 鲥da n da d d r e s s e s t h ee m e r g i n gi s s u e s t h ek e y 把c h n o l o g i e sa n dp r o b l e m so ft h ed m ga g e a n a l y z e d t h i s d i s s e r t a t i o n p r o p o s e s i d e a sa n d m e t h o d s t os o l v e t h o s e p r o b l e m sa n d p r e s e n t t h ep r o s p e c t o f d m g i no r d e rt os o l v et h ec h a n l l e n g so ft h ed m g ，t h i sd i s s e r t a t i o ns t u d i e ss e v e r a lk e y t e c h n o l o g i e s g e n e r a l l y , t h er e s e a r c hw o r k so ft h i sd i s s e r t a t i o nh a v es i xa sf o l l o w i n g ： s u r v e yo ft h et h e o r ya n dt e c h n o l o g i e sf o rd a t am i n i n ga n dg r i dc o m p u t i n g a f t e r a n a l y s i s i n gt h ef e a t u r e so ft h ec l a s s i c a la l g o r i t h ma n dc o m p a r i s i n gt h ea r c h i t e c t u r e so f g r i dn o w a d a y s ，t h ed e f i c i e n c i e so ft h e s eg r i da r c h i t e c t u r e sa r ep r e s e n t e d i n d i c a t e s t h a tt h er e a l i z a t i o no ft h ed m gi st h er i 曲tw a yt os o l v et h ep r o b l e m so ft e l e c o md a t a m i n i n g p r o p o s e da r c h i t e c t u r eo ft h ed a t am i n i n gg r i db ya n a l y z i n gt h er e q u i r e m e n t so f t h ed a t am i n i n g 鲥da n dc o m p a r i n gt h ea r c h i t e c t u r e so ft h e 鲥d s ，t h i sd i s s e r t a t i o n p r o p o s e dad m ga r c h i t e c t u r e t h e nt h i sd i s s e r t a t i o nd e s e r i p t sm a n yf e a t u r e so ft h e d m gf o rt h ep u r p o s eo fp r o v i n gt h ec o r r e c t i o na n dt h ep r a c t i c a b i l i t y , a n da p a r a d i g m i sd e s i g n e da n dt h es o e n ea n a n y s i sm e t h o di si n t r o d u c e di n p r o p o s e dt h ep a r a l l e la l g o r i t h m sf o rv a r i o u sd a t am i n i ga l g o r i t h m s t h e ng e n e r a l p a r a l l e lm e t h o di sp r o p o s e d t h eo p t i m i z e ds c h e d u l ea l g o r i t h mi sr e a l i z e d t h e nt h e p a r a l l e la l g o r i t h ma n dt h es c h e d u l ea l g o r i t h ma l ea n a l y z e d t h i si sas u c c e s so f p a r a l l e la l g o r i t h mf o rf u l f i l l i n gf o rt h ed a t am i n i n gt a s k ，w h i c hc a ns u p p o r tt h ed a t a a n a l y s i sa n dt h ek n o w l e d g ed i s c o v e r yf o rt e l e c o m mc a l t i e rb u s i n n e s si n t e l l i g e n c e s u r v e yt h em e a t a - d a t ac r i t e r i o n s a n dt h em e t a - d a t aa p i s a n da n a l y z et h e i m p o r t a n c ea n dt h er e q i r e m e n t so ft h em e t a - d a t af o rt h ed m gt h e np r o p o s ea m e t a d a t am o d e lt os u i t et ot h en e e do ft h ed a t am i n i n gg r i ds y s t e m f o rt h ep u r p o s e o ft h en o r m a l i z a t i o na n dt h ei n t e r o p e r a t i o nb e t w e e nt h ec o m p u t e r s ，t h ex m ls c h e m a v l 韭塞坚皇查兰堕主兰垒堡苎塾塑丝塑翌垒董王叁壁垫查竺壅 i su s e dt od e s c r i p tt h em o d e l i no r d e rt os h o wt h ep r a c t i c a l b i l i t yo ft h em e t a d a t a m o d e l ，t h ei n s t a n c e sa r eg i v e n t h em e t a d a t as e r v i c ea r c h i t e c t u r e i s p r o p o s e d b e s i d e t h ed e s i g no ft h e m e t a d a t am o d e l ，t h em e c h a n i s mo ft h em a n a g e m e n ta n dt h ep u b l i c a t i o no ft h e r e c t a - d a t aa r ep r e s e n t e da sw e l l a ni n s t a n c eu s i n gt h ew e bs e r v i c es h o w st h e p r a c t i c a l b i l i t yo f t h ea r c h i t e c t u r e d e s i g n e da n dr e a l i z e dad m gp r o t o t y p es y s t e mt op r o v et h e f e a s i b l ea n dt h e p r a c t i c a l b i l i t yo ft h ed m gb yr u n n i n gt h ew o r k f l o w so fs o m eg i v e n b u s i n e s s i n t e l l i g e n c es o l u t i o no nt h ed m gp r o t o t y p e t h ef e a s i b i l i t ya n dt h ee f f i c i e n c ya l e p r o v e d k e yw o r d s ：d a t am i n i n g ，鲥d ，a r c h i t e c t u r e ，p a r a l l e lc o m p u t i n g ，t a s ks c h e d u l e ，m e t a _ d a t am o d e l ， m e t a - d a t as e i v i c e v i l 北京邮电大学博士学位论文致据挖掘网格若干关键技术研究 图2 - 1 数据挖掘的方法分类 图2 - 2o g s a 框架【州 图目录 9 儿 1 2 图2 - 3 w s 和g s 融合为w s 聪l s 】 图2 4o g s a 框架中o g s i 与w s r f 的对应关系删 图2 - 5o r a c l e l o g 基础架构删 图2 - 6s u ng r i de n g i n e 的体系架构【2 0 j 图2 - 7v e g ag r i d 的三层结构矧 图2 - 8 数据挖掘网格的一种体系结构”q 圈2 - 9 知识随格多空间体系结构瞄l 图2 1 0w e k a 4 w s 通用框架嘲 图3 1 数据挖掘网格的总体结构简圈 圈3 - 2 数据挖掘网格的体系结构 图3 3 安全认证与计费管理模块 图3 4 通信与信息服务模块 围3 5 数据挖掘网格的一个拓扑结构图 图3 - 6 数据挖掘网格中各主要实体合作图 图3 7 客户视图的流狸图 圈3 8 数据挖掘网格模块在数决挖掘过程中的顺序图一 图3 - 9a g e n t 局部的顺序图 1 4 1 5 t 5 l ， 1 8 2 4 2 5 2 7 2 7 2 8 2 9 3 0 3 l 幽3 - 1 0a g e n t 的状态转换图 图3 - 11m d c 局部的顺序图 图3 1 2m d c 状态转换图 幽3 1 3 c o m p u t i n g n o d e 局部的顺序图 3 2 3 3 图3 1 4c o m p u t i n gn o d e 的状态转换图 圈3 1 5c l i e n t 与d m g 的顺序图 图3 1 6c l i e n t 的状态转换图 图3 - 1 7 a g e n t 模块设计 图3 1 8 m d c 模块 图3 1 9 电信客户流失预测方案分析流程 图3 - 2 0 一个数据挖掘网格的原型结构设计 图4 - l 问题并行求解过程懈】 图4 - 2 两种基本的并行结构“ 图4 - 3 电信呼叫图的局部示意图 图4 4 数据分割方式图 图4 5 中介度并行算法 3 5 3 5 3 6 3 6 3 9 3 9 4 0 ，4 4 图4 63 0 c p u 并行计算各c p u 的计算时间图 图4 74 s c p u 并行计算各c p u 的计算时问图 图4 - 86 0 c p u 并行计算各c p u 的计算时间图 图4 9 不同个数c p u 组的加速比 图4 1 0 不同个数c p u 组的并行效率 图4 1 l 决策树生成算法。 图4 1 2 并行决策树生成算法。 4 5 4 6 4 8 4 9 4 9 i x 5 2 5 4 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 5 9 5 9 ，6 2 。6 4 酷 6 7 矾 图4 1 4k - m e a n s 算法的迭代过程 图4 1 5 并行k 平均算法 图4 - 1 6 n i l 并行算法l 图4 1 8a p r i o r i 算法串行算法。 图4 一1 9 关联规则a p 面r i 并行算法。 图4 - 2 0 极大团串行算法【7 j 图4 2 l 极大团并行算法 图4 - 2 2 数据分割方式示意 图4 2 3 数据动静态分配比例为1 2 的实例 图5 1 信息网格资源的元数据目录i 。叫。 图5 - 2p m m l 描述的数据挖掘元模型棒耐 图5 - 3c w m 元模型的包结构 图5 - 4 j d m 的三种可选架构 图5 5 网格应用的资源抽象层次和对应元数据以及映射关系“0 4 1 幽5 6 数据挖掘网格元数据的分层示意图 圈5 7 数据挖掘网格元数据模型 图5 - 8 数据挖搦网格的元数据 6 9 7 l 7 3 8 0 8 2 8 3 图5 - 9 元素的定义 图5 - 1 0 元素的定义 图5 1l 元素的定义 8 6 8 7 8 8 8 9 9 0 图5 - 1 4 元；素的定义 9 2 9 3 图5 1 5 元素的定义。9 3 图5 - 】6 ：o 啦p i i l 玎】d j s 廿i 姗s c t l i l l g 元素的定义 图5 1 7 元索的定义。 图5 - 1 8 元素的定义 图5 1 9 元素的定义 图5 2 0 元素的定义 9 4 9 4 9 5 ，9 5 9 6 图5 - 2 1 素的定义 图5 2 2 元素的定义， 图5 - 2 3 数据挖掘元数据服务结构 图6 - 1 客户流失的预测 图6 - 2 客户流失的关联关系 9 7 1 0 2 图6 - 3 团属性的计算。1 0 8 图6 - 4 客户流失的分析 图6 - s 客户价值的分析 图6 6 中介度属性的计算。 1 0 9 1 0 9 图6 7 客户价值的分析和预测1 0 9 图6 8 一个数据挖掘网格的原型结构设计 图6 - 9 用户使用界面总流程 图6 1 0 模型运行后的提升图 x 1 1 1 1 1 2 。1 1 6 ! ! 星塑皇查竺坚主堂竺丝苎 墼塑丝塑旦堑堇三茎壁垫查里壅 图6 1 1 提升值比较( 红线为本文算法) 图6 1 2 基于链接分类的查全率 图6 1 3 按a r p u 值分档后各档提升值比较 1 1 7 1 1 7 1 1 8 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 表目录 表6 1 数据集说明1 1 3 表6 - 2 按a l l p u 值的客户分类1 1 3 表6 - 3 客户流失预测属性1 1 3 表6 - 4 用户第k 个月中介度值。1 1 4 表6 - 5 目标变量1 1 4 表6 - 6 模型的覆盖率和正确率1 1 5 表6 - 7 准确率和涵盏率1 1 6 表6 8 三组c p u 数目情况中的运行时问结果1 1 9 l 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果尽我所 知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰 写过韵研究成果，也不包古为获得北京邮电大学或其他教育机构的学位或证书而使用过的材 科与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位 本人签名 关于论文使用授权的说明 学位论文作者完全了解北京邮电人学有关保留和使_ i i 学位论文的规定，卸：研究生在校 攻读学位期间论文工作的知识产权单位属北京邮电大学学校有权保留并向国家有关部门或 机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存、汇编学位论文( 保密的学位 论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适鬣翌弛= 函日期：1 鲤f ：避= 1 颦 嗍：而日舻 i l l 北京邮电大学博士学位论文 数据挖掘网格若干关键技术研究 第1 章前言 1 1 研究工作的背景和意义 从世界范围来讲，数据分析技术，特别是以数据挖掘技术为主并结合知识 管理的交叉研究正处于新兴交叉科学的萌芽阶段与其它学科相比，我国与外 国在此领域的发展差距相对较小，但如不能采取有效措施，此差距却会不断增 大并导致在未来成为中国与世界水平之间的一道巨大的鸿沟。因此，开展建立 以数据挖掘网格为中心的多层智能网络在知识管理中的应用。开展多种知识管 理( 诸如电信业务、金融保险、能源勘探、生物信息技术与新医药筛选、信息 安全、宇宙探测、灾害预警监测、创新智能研究等) 与数据分析中的应用平台 研究。至为重要。这些研究的开展，将极大地夯实我国在知识经济时代的科学 研究的基础，并能极大地推进我国在各种经济活动中的应用，提高我国在全球 经济一体化的知识经济时代的整体竞争能力具有重要的现实科学意义和广泛 的商业应用价值。 1 1 1 电信经营和企业信息应用的挑战 电信运营商的信息分析是数据挖掘技术重要的应用领域。全球电信市场正 在逐渐走向开放和自由化，电信市场的竞争日趋激烈如何提供高质量的服务 来吸引和留住客户、扩大市场份额、降低成本、提高收益，已经成为全球电信 业决策者共同关注的课题。随着中国加入w t o 及电信市场的开放的步伐日益 加快，中国电信市场的竞争必将更为激烈【1 1 因此，为了提高企业的核心竞争 力，国内各大电信运营商都相继着手建立企业经营信息分析系统。经过近几年 的建设，多家移动通信运营公司已经构建了经营信息的数据仓库，存储了大量 企业经营数据及客户信息，虽然经营分析系统中应用了传统的联机分析处理、 数据挖掘等技术，但是由于相关技术的局限性，大量分析需求仍然不能得到满 足。怎样从海量电信数据中挖掘深层次的信息，有效地指导经营决策是运营商 和相关技术厂商面临的急迫问题。例如，通过分析群体客户通信网络涌现特征， 可以提取客户关系结构模型和客户通信行为特征指纹，这些模型和特征对市场 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 细分、客户价值分析、客户离网预测分析、集团客户分析、竞争对手分析、电 信服务产品设计等众多电信企业核心的市场问题的决策支持，都极有意义【2 1 1 1 2 数据挖掘技术面临的挑战 数据爆炸，知识却愈加相对贫乏，这就是当前电信等领域内经营分析和知 识发现方面的现状数据挖掘的目标就是为了解决这些问题。数据挖掘是一个 宽泛的，面向目标的定义事实上它的基本技术涉及机器学习、统计学、数据 库、可视化技术、高性能计算等诸多方面的交叉学科 3 1 。这个领域的发展体现 了各种技术和应用需求的相互作用和矛盾演化的过程。随着各个学科飞速发展， 各种网络尤其是h l t 锄e t 的广泛使用，使得各种数据猛然增长，数据的海量和数 据的异构( 结构化和半结构化，非结构化) 。都对于数据挖掘提出了重大的挑战 电信运营商以及各大银行的经营分析和决策支持都需要数据挖掘，这些领 域具有超级的海量数据，但在这些海量数据之上进行卓有成效的经营分析和决 策支持，带来的却是大规模计算问题对计算能力提出的挑战。 新的挑战引发了新的热点，使得矛盾的主要方面凸现出来 4 1 。在一些应用 场合，当前的主要矛盾是，诸多的企业得不到足够强大的计算力，使得有些通 用或者专用的数据挖掘算法得不到有效的运行，但是同时却有大量的小设备闲 置。 一些场景需要分布式式的数据挖掘应用。电信运营商的海量分散数据之上 的经营分析系统，这些都需要大量的计算和存储资源；金融组织问通过合作防 止信用卡欺诈( 数据共享) 既需要信息合作又要信息各自独立；大型跨国公司 销售点分敬，数据一般都是分散的；而且在有些行业，许多情况下，将所有数 据集中在一起进行分析往往是不可行的；还有的因为出于对安全性、容错性、 商业竞争以及法律约束等多方面因素的考虑，数据需要分散存储和分析。这样， 必须数据挖掘系统具有更好的分布性和可扩展性。 新的挖掘策略和算法，比如多关联计算的数据挖掘和基于图的社群分析， 犯罪预防分析，信用卡欺诈等需求对于计算能力和模式都提出了巨大的挑战， 需要采纳分布式的计算方式才能完成i 卯。很多大的计算量的数据挖掘也向中小 企业渗透，而中小企业又缺乏提供强大计算能力。 2 北京邮电大学博士学位论文 致据挖掘网格若干关键技术研究 1 1 3 现有解决方案及其不足 面临数据、计算挑战和应用需求的挑战，数据挖掘的主要矛盾集中体现在 了计算能力的不足上，数据挖掘的计算问题成了主要瓶颈。 目前主要的解决方案就是购置大量的新的高性能设备但是这样产生了一 个矛盾，那就是在购置昂贵的大型设备同时，却有很多内部的计算机资源闲置， 比如很多p c 或工作站的利用率就很低一方面存在大量的闲散资源，一方面 是计算资源的极度缺乏这就需要重新定位和调整我们的研究重点 1 2 项目背景和主要研究工作 本论文是作者在博士生期间参加多个项目的工作总结和提炼与论文工作 在直接相关的项目包括国家自然科学基金项目“面向电信海量数据的多实体关 系结构数据挖掘研究”( 编号：6 0 4 0 2 0 1 1 ) 的研究，和“北京市教委合作研究项 目- 多媒体网格关键技术研究( 编号：s y s l 0 0 1 3 0 4 2 2 ) ”，这些项目都直接的支持 了数据挖掘网格的相关关键技术的深入研究。本博士论文的主要内容也部分基 于这些项目的研究。 研究的主要内容包括： 研究和综述了数据挖掘的算法研究现状和网格系统的发展状况，分别研究 了经典数据挖掘的分布算法的特点和适用性，分析比较了多个主要的网格架构 和网格系统；分析了这些网格架构的特点和不足。 通过分析电信数据挖掘应用的需求，分析比较研究了网格系统的基本架构， 尝试提出了数据挖掘网格的概念，并提出和设计了一种数据挖掘网格的系统结 构，并且从多个角度详细描述了数据挖掘网格的层次结构，体系特征，模块功 能，动态特性，交互关系。 研究了几大类经典数据挖掘算法和基于图的数据挖掘算法的直接并行算 法，总结了挖掘算法并行化的通用方法；提出了网格调度算法来优化并行化任 务的执行效率，并且对并行算法及其调度算法进行了性能分析。 研究了元数据的若干标准，发现现有标准不能完全解决数据挖掘网格的元 数据需求，因此提出描述数据挖掘网格的元数据模型；元数据模型提供了对于 数据挖掘网格架构的各个层面的支撑，主要支撑了分布式数据挖掘的算法元数 据和网格系统的元数据；为了说明元数据模型的实用性，给出了数据挖掘网格 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 的接口，方案，资源的描述实例。 研究了元数据管理和发布和服务提供，这也是数据挖掘网格中的一项关键 技术。元数据管理的一个重要目标是提供元数据服务首先根据元数据服务的 应用需求其分为对内服务和对外服务接着提出了利用w e b 服务技术构建数据 挖掘的元数据服务系统，探讨了元数据服务的机制。 为了展现数据挖掘网格体系结构设计的正确性和可行性。设计实现了数据 挖掘的一个原型；通过原型系统的运行，展示了数据挖掘网格的工作过程；为 了验证该体系结构的正确性和实用性，文中采用了实例场景的分析方法，通过 一个电信数据挖掘方案在数据挖掘网格模块问的运行过程，验证了数据挖掘网 格的功能能够适应电信领域的数据挖掘应用，以及数据挖掘网格系统的可行性 和高效性。 1 3 论文的主要创新点 本文的主要贡献在于： 1 1 提出了数据挖掘网格的概念，并通过分析数据挖掘网格系统的需求， 研究分析比较了数据挖掘算法和网格系统的基本架构，提出了数据挖 掘网格的体系结构。该系统结构依据分层思想按照功能关系划分为六 层，能够提供从数据挖掘接口服务到数据挖掘的领域应用的支撑，能 够支撑数据挖掘的分布计算，对于并行计算资源和数据的分配都能够 提供很好的支撑。 2 1 提出了对三类数据挖掘算法的并行化算法，提出了对于几大类别的数 据挖掘算法的并行化的一般方法，并且提出了一种网格调度算法来优 化并行化任务的执行效率：对于3 个基于复杂图的算法进行了研究， 提出了复杂图的中介度算法、极大团的改进算法、聚集度的算法，以 及它们的并行算法；提出了基于图的算法并行化的一般性方法。并行 化一般方法的提出，为数据挖掘并行算法的基本实现提供了保障，也 验证了数据挖掘网格的可行性和实用性。通过中介度计算等算法的并 行实现，以及调度算法的优化，验证了数据挖掘分布算法的可行性和 高效性 3 1 提出了数据挖掘网格的元数据层次体系模型，该模型综合了当前的网 4 北京邮电大学博士学位论文致据挖掘网格若干关键技术研究 格和数据挖掘相关的元数据模型，该模型的重点还包括分布式算法紧 密相关的新的元数据元素，包括数据分片与否，数据横向分片的大小 ( 包含起止点) ，数据纵向分片的大小( 包含起止点) 等；元数据体系 模型为数据挖掘网格中的软硬件资源管理、方案管理、算法调度、数 据分割和传输提供了元数据保障。 4 ) 提出了利用w e b 服务技术构建数据挖掘的元数据服务系统结构，该服 务架构提供数据挖掘网格元数据的w e b 发布和管理，使得数据挖掘网 格的元数据可以对外部程序提供通用的w e b 服务接口，这样的架构增 强了系统的开放性。 5 ) 实现了数据挖掘网格系统。通过设计一个数据挖掘的一个原型，说明 了电信领域里面从解决方案到各个分布式算法的设计中的关键模块和 模块之间的主要关系，展现了数据挖掘网格体系结构设计的正确性和 可行性。通过原型系统的运行，展示了数据挖掘网格的工作过程，并 且通过具体的数据试验，验证了数据挖掘网格系统的可行性和高效性。 1 4 论文结构 整个论文的结构是从架构研究到技术研究，再到系统实现和验证，论文的 结构安排如下所示： 第一章是前言。 第二章数据挖掘网格的相关研究综述；着重介绍了电信领域数据挖掘的挑 战，对于研究热点，研究思路，技术路线，技术难度等方面进行了分析，深入 探讨了电信领域数据挖掘网格研究的重点方向以及亟待研究的技术。 第三章数据挖掘网格体系结构研究；这一章属于框架和系统性的内容，提 出了数据挖掘网格的一种体系结构，并且从多个角度详细描述了数据挖掘网格 的层次结构，体系特征，模块功能，动态特性，交互关系。 第四和第五章都是技术与方法的研究和设计的内容。 第四章数据挖掘网格并行算法研究和设计，主要进行数据挖掘算法的并行 化相关的研究，包括算法并行化，并行化后算法的加速比、并行效率的分析， 数据挖掘任务在网格上的调度算法及其效率研究。 第五章数据挖掘网格的元数据信息模型和元数据服务体系架构；主要研究 北京邮电大学博士学位论文 数据挖掘网格若干关键技术研究 和提出适合数据挖掘网格需要的元数据的元模型，并把信息模型用x m l s c h 舶植进行了描述为了说明元数据模型的实用性，描述了几个实例 第六章主要设计实现了数据挖掘网格系统的个原型系统基于具体的数 据挖掘分析方案，实现了从数据处理到建立信息模型，然后训练预测模型，最 后得到对某电信运营商某个地市的客户流失预测结果比较了在数据挖掘网格 上面运算得到的数据挖掘结果与一般分析方法得到的结果之问的比较，说明了 数据挖掘网格的实用性和高效性 最后一章是总结。 6 北京邮电大学博士学位论文 数据挖掘网格若干关键技术研究 第2 章数据挖掘网格的相关研究综述 本章主要研究数据挖掘和网格系统相关技术的研究现状首先，简要介绍 了数据挖掘的知识，然后尝试提出了数据挖掘网格的定义，并迸行了阐述和深 化；然后展现了当前数据挖掘和网格技术的发展现状和最新研究动态着重对 电信领域数据挖掘的研究热点、研究思路、技术路线、技术难度等方面进行了 分析，探讨了电信领域数据挖掘网格研究的重点方向以及亟待研究的技术。 2 1 数据挖掘简介 2 1 1 数据挖掘的任务 数据挖掘的任务就是从实例集合中找出容易理解的规则和关系。这些规则 可以用于预测未来趋势、评价顾客、评估风险或简单地描述和解释给定的数据 【5 叼。通常数据挖掘的任务包括以下几个部分： 数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单 的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统 计值，或者用直方图、饼图等图形方式表示。数据挖掘主要关心从数据泛化的 角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到 高层次上的过程【5 5 1 数据泛化目前主要有两种技术：多维数据分析方法和面向 属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ， o n l i n e a n a l y s i sp r o c e s s ) 。数据仓库是面向决策支持的、集成的、稳定的，不同 时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如 求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大因此 一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持 系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经 在决策支持系统中获得了成功的应用，如著名的s a s 数据分析软件包、b u s i n e s s o b j e c t 公司的决策支持系统b u s i n e s so b j e c t ，以及i b m 公司的决策分析工具都 使用了多维数据分析技术。 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 采用多维数据分析方法进行数据总结。它针对的是数据仓库，数据仓库存 储的是脱机的历史数据为了处理联机数据，研究人员提出了一种面向属性的 归纳方法它的思路是，直接对用户感兴趣的数据视图( 用一般的s q l 查询语 言即可获得) 进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化 数据方法的提出者对这种数据泛化技术称之为面向属性的归纳方法原始关 系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次 上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足 用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则， 以及关联规则等。 2 1 2 数据挖掘的分类 数据挖掘所能发现的知识有如下几种 s g l ： 广义型知识，反映同类事物共同性质的知识； 特征型知识，反映事物各方面的特征知识； 差异型知识，反映不同事物之间属性差别的知识； 关联型知识，反映事物之间依赖或关联的知识： 预测型知识，根据历史的和当前的数据推测未来数据； 偏离型知识。揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从 微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家 超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾 客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则 对于商家开发和实施客户化的销售计划和策略是非常有用的 2 1 3 数据挖掘的方法 数据挖掘并非一个完全自动化的过程。整个过程需要考虑数据的所有因素 和其预定的效用，然后应用最佳的数据挖掘方法。数据挖掘的方法很重要。在 数据挖掘的领域里有一点已经被广泛地接受，即不管你选择哪种方法，总存 在着某种协定。因此对实际情况，应该具体分析，根据累积的经验和优秀的范 例选择最佳的方澍6 1 】。数据挖掘中没有免费的午餐，也没有适合每个人的简单 方法。 数据挖掘算法作为数据挖掘的核心部分，它被研究得最多。目前存在很多 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 数据挖掘方法或算法，有必要对这些方法进行分门别判5 9 1 我们知道，描述或 说明一个算法涉及三个部分：输入、输出和处理过程数据开采算法的输入是 数据库，算法的输出是要发现的知识或模式，算法的处理过程则涉及具体的搜 索算法，可以确定这样几种分类标准：挖掘任务、挖掘对象和挖掘方法。 r分类或顶溯模墨! 发现 i 数培总结 l 聚类 根据挖掘任务l 关联规删发瑷 i 芹刭覆式发现、 l 依赣关系或依赣锤陵现 l 异常和趋势发现 r -关系数据库 i 面向对象数鼍库 l遗产数据库 根据挖喝对象l异髓款骞库 i 空f 司蔽据库 l 时态致据库 l 文本数据碌 i 多嫖俸数据库 l 删 r 归纳学习方 圭( 决策树、规则归纳簪) 、 广一机器学习方法l 基于范例学习， il 遗传茸法等 i l广回归分析( 多元回归、自回归等， l坑计方法i 判耕分析( 贝叶斯、舞歇尔和非笋敦判别， ll 聚类分折系坑聚粪、动态聚粪等) li 探索性分析主元分析法，相关分析法等) 挖掘方法i l 神经网络方法i 前向神经髓络即算法等) ii 自组织神经网络自组织映射、竟母学习等) i l 躲舫法i 多罐数据分析或o u p 方j 去 一 l 面向t i i t 的妇纳方：圭 圈2 1 数据挖掘的方法分类 此外，还有粗糙集方法【7 0 l 、云模型等。 2 2 数据挖掘网格的定义 在数据挖掘技术和网格计算的研究背景下，数据挖掘网格( d m g ，d a t a m i n i n gg r i d ) 作为一个研究方向出现了由于这是一个新的技术交叉领域，目 前没有权威的定义。 本文尝试对“数据挖掘网格”定义如下：它是数据挖掘技术与网格计算的 有机结合，可以用于分布式环境下的数据模式发现。数据挖掘网格能够提供对 大规模数据挖掘计算的解决方案，可以充分利用分布式计算的能力对相关的数 9 北京邮电大学博士学位论文数据挖掘网格若干关键技术研究 据进行分析与综合。 具体而言，数据挖掘网格是一种通过共享解决方案、算法、计算、数据， 存储服务来解决可靠和可扩展的商业智能分析( 主要为数据挖掘) 任务的系统， 它能够在动态变化的多个节点间共享资源和协同解决商业智能分析( 主要为数 据挖掘) 问题。其特点是具有好的扩展性( 从理论上可以无限扩展) ，用户透明 性，可靠性，高性能计算，分布性，协同性，主要应用于协同解决商业智能分 析问题。 2 3 数据挖掘网格的意义 将数据合理地划分为若干个小模块，并山分布式数据挖掘系统并行地处理， 最后再将各个局部处理结果综合成最终的输出模式，可以解决本文前言中提到 的分布式计算和海量数据的挑战。这样不但能够保护已有软硬件投资，而且这 种系统天生还具有计算力可无限扩展的能力 分布并行计算是超级计算的研究重点，分布计算的当前研究重点是网格计 算。网格计算的实质是，从逻辑上看它是一台可扩展的超级计算机，可以实时 的进行计算能力的扩展，特点是按照计算的需要提供计算能力( 规模可大可小) ， 而不是预先购置超级的计算能力( 成本高，难于扩展) 这就是网格计算区别于 一般超级计算机的最大优势 2 4 国内外数据挖掘和网格结构研究 2 4 1 体系结构研究 数据挖掘网格是一个新的概念和技术，是数据挖掘和网格技术的结合。鲜 有资料专门论述数据挖掘网格架构的，所以，在论述当前已有相关研究，本文 主要从网格架构和数据挖掘技术两个方面分别的研究现状进行综述。 数据挖掘网格相关的研究主要包含数据挖掘网格分布式算法研究和数据挖 掘网格体系结构研究f 6 1 ，以下是这两大方面在研究的项目和成果。 网格技术研究历史方面，先提出的概念是计算网格【7 x 3 l 、数据网格9 1 、信息 网格 i o j 、网格中间件f l l j 。然后逐渐形成了服务网格【1 2 1 、语义网【3 1 ，w e b 数据 挖掘( ，知识网格【5 】的概念，并展开了研究工作。数据挖掘网格是一种从计算 网格和到知识网格的一个阶段上的研究成果【1 6 1 。其中，计算网格研究得最早， l o 北京邮电大学博士学位论文 数据挖掘网格若干关键技术研究 全球目前的网格项日中，绝大多数都是计算网格 当前，国内外已经对分布式数据挖掘展开了一定的研究【。研究主要集中 在分布式数据挖掘算法研究和数据挖据网格体系结构的研究 目前有些有影响的项目和成果叙述如下 2 4 1 。1g i o b u st o o l k i t 。o g s i 与0 g s a g l o b e s p r o j e c i 是当前最著名的网格项目，g l o b u s t o o l k i t 是该项目开发的 网格系统和开发环境【s l ，目前版本为g t 4 。 2 0 0 2 年g l o b u s j 、组和i b m 联合提出o g s a 的网格体系结构，将w e bs e r v i c e 和g r i d 相结合，为网格扩展到更多的应用领域提供支持g t 4 发展自以前的 舨本，版本的架构目前已经发展到了o g s a 。o g s a 是开放网格服务架构( o p e l