（应用数学专业论文）概念格分布式构造算法研究.pdf

p 蟹 囊 1 ，- 1 ， ，时虬 ，i ，!z目l 中文摘要 |jll j mill lff rl f l hf frplil y 17 8 9 2 6 9 概念格是一种反映概念问层次关系的数学模型，具有完备性、精确性和简洁性等特 点，也是数据挖掘与知识发现领域中的一种有效 具。随着分布、异构数据集大量出现， 概念格构造的复杂性r 益增大，分布式构造是降低面向海量数据的概念格构造复杂性的 一种有效途径。本文，针对概念格分布式构造算法进行了研究。主要研究结果如下： 第一、基于网格的概念格分布式构造。利用网格作为分布式计算平台，采用适合概 念格构造规模的多次分发调度策略，给出了一种网格环境下的概念格分命式构造方法。 最后，采用恒星光谱数据作为形式背景，实验验证了方法的i f 确性和有效性。 第二、基于剪枝的概念格分布式构造。采用剪枝技术，消除概念格分布式渐进式构 造过程中出现的冗余信息，给出了一种概念格分和式构造算法，从而有效地减少了插入 概念的比较次数，提高了概念格的分布式构造效率。采用恒星天体光谱数据作为形式背 景，实验验证了算法的f 确性和有效性。 关键字：概念格；剪枝；分布式；网格；多次分发；恒星光谱数掘 t 、f a b s t r a c t c o n c e p tl a t t i c e ，w i t h t h ec h a r a c t e r i s t i c so fi n t e g r a l i t y , a c c u r a c ya n d s i m p l i c i t y e t c ，i sa m a t h e m a t i c a lm o d e lw h i c hr e f l e c t st h eh i e r a r c h yb e t w e e n c o n c e p t s ，a n dap o w e r f u lt o o lf o rd a t aa n a l y s i sa n d d a t am i n i n g w i t he x i s t i n go f m a n yd i s t r i b u t e da n dh e t e r o g e n e o u sd a t as e t s ，a n dc o n s t r u c t i n gc o m p l e x i t yo f c o n c e p tl a t t i c e ，d i s t r i b u t e dc o n s t r u c t i n go fc o n c e p tl a t t i c ei sa ne f f e c t i v ew a y t o r e d u c et h et i m ea n ds p a c ec o m p l e x i t yo ft h ec o n c e p tl a t t i c eo r i e n t e dm a s s i v e d a t a i nt h i sp a p e r , d i s t r i b u t e dc o n s t r u c t i i n ga l g o r i t h m so fc o n c e p tl a t t i c ea r e s t u d i e db yu s i n gg r i da sac o m p u t i n gp l a t f o r m t h em a i nr e s e a r c hw o r k sc a nb e s u m m a r i z e da sf o l l o w s ： f i r s t l y , ad i s t r i b u t e dc o n s t r u c t i n gm e t h o do fc o n c e p tl a t t i c e i sp r e s e n t e d b a s e do ng r i d u s i n gt h eg r i da sad i s t r i b u t e dc o m p u t i n gp l a t f o r m ，ad i s t r i b u t e d c o n s t r u c t i n ga l g o r i t h mi sp r e s e n t e db yt a k i n gas c h e d u l i n gs t r a t e g yo fm u l t i p l e d i s t r i b u t i o ns u i t a b l e f o rt h es c a l eo fc o n c e p tl a t t i c ec o n s t r u c t i n g i nt h e e n d ，e x p e r i m e n t a lr e s u l t sv a l i d a t et h ea l g o r i t h mi sc o r r e c ta n de f f i c i e n tb yt a k i n g t h es t a rs p e c t r ad a t aa st h ef o r m a lc o n t e x t s e c o n d l y ，ad i s t r i b u t e dc o n s t r u c t i n gm e t h o do fc o n c e p tl a t t i c e i sp r e s e n t d b a s e do n p r u n i n g u s i n g a p r u n i n gt e c h n o l o g y t oe li m i n a t er e d u n d a n t i n f o r m a t i o nw h i c ha p p e a r si nt h ec o n c e p t l a t t i c e sd i s t r i b u t e di n c r e m e n t a l c o n s t r u c t i o np r o c e s s ，ad i s t r i b u t e dc o n s t r u c t i n ga l g o r i t h mo fc o n c e p tl a t t i c ei s p r e n s e t e d ，s ot h a tt h ec o m p a r i n gt i m eo fi n s e r t e dc o n c e p t si sr e d u c e d ，a n d t h e c o n s t r u c t i n ge f f i c i e n c y o f c o n c e p t l a t t i c e i s e f f e c t i v e l yi m p r o v e d t h e e x p e r i m e n tr e s u l t s v a l i d a t et h ec o r r e c t n e s sa n dv a l i d i t yo ft h ea l g o r i t h mb y u s i n g t h ec e l e s t i a ls p e c t r u md a t aa st h ef o r m a lc o n t e x t k e yw o r d s ：c o n c e p tl a t t i c e ；p r u n i n g ：d i s t r i b u t e dc o n s t r u c t i n g ；g r i d ；m u l t i p l e d is t r i b u t i o n ；s t a rs p e c t r ad a t a i v 磊 ，瑚黧髫i蠹，*c k ： 第一章绪论l 1 1 数据挖掘1 1 1 1 数据挖掘的产生和定义1 1 1 2 数据挖掘的功能2 1 1 3 数据挖掘的技术3 1 1 4 数据挖掘的应用4 1 2 概念格5 1 2 1 概念格的基本概念和定义5 1 2 2 传统的概念格的构造方法6 1 2 3 概念格的分布式构造7 1 2 4 概念格的扩展与应用7 1 3 网格8 1 3 1 网格的产牛和定义8 1 3 2 网格的结构8 1 3 3 网格的应用9 1 4 本文主要的研究内容及论文的组织安排1 0 1 4 1 研究内容的提出1 0 1 4 2 沦文组织结构1 0 第二章概念格1 l 2 1 概念格的定义1 l 2 2 概念格的构造方法1 l 2 2 1 批处理构造算法1 1 2 2 2 渐进式构造算法1 2 2 3 概念格的分布式构造1 3 2 3 1 形式背景的分布处理1 3 2 3 2 不一致背景及其处理13 2 3 3 概念格分布式构造1 4 2 4 剪枝的概念格构造l 6 2 5 小结1 7 v 第三章基于网格的概念格分布式构造1 9 3 1 引言1 9 3 2 基于网格的概念格分布式构造1 9 3 2 1 调度策略1 9 3 2 2 子格构造和合并模块2 0 3 3 实例分析2 1 3 4 实验分析2 2 3 5 结束语2 4 第四章基于剪枝的概念格分布式构造2 5 4 1 引言2 5 4 2 基于剪枝的概念格分布式构造2 5 4 3 算法描述2 6 4 4 实验分析2 9 4 5 小结3 0 第五章总结与展望3 1 5 1 总结3 1 5 2 展望3 1 参考文献3 3 致谢3 7 研究生期间发表的论文和参加的科研项目3 9 v l ； ，f 挚 女 ， 第一章绪论 第一章绪论弟一早珀t 匕 1 1 数据挖掘 1 1 1 数据挖掘的产生和定义 随着计算机技术特别是数据库技术和网络的飞速发展，人们利用信息技术生产和搜 集数据的能力大幅度提高，数据库系统在商业管理、政府办公、科学研究和二i ：程丌发等 领域得到广泛应用，这使得可供奄询的信息爆炸性增长，毫无疑问的是，这一趋势还将 长期持续下去。在给人们带来方便的同时，数据的增加也带来了一系列问题。首先，由 于信息量十分庞大，仅仅是查找数据也会花费过长的时问；其次，数据库中有用与无用 的信息混杂，很难用简单的方法分辨；再次，并彳、= 是所有信息都是安全的，没有进行安 全过滤的数据可能会带来损失；最后，不同的信息源提供的数据在形式和结构卜往往有 定的差异，统一处理时需要经过繁琐的预处理过程。如何解决上述问题，从海量的信 息中获取有价值的客广l 关心的部分。i 卜是在这样的需求背景下，数据库的知识发现 ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 产生并迅速发展了起来i 陀j 。 数据库的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 是从大量未经过处理 的数据中提取出可信赖的、不陈旧的、有价值的并能被用户理解的模式的处理过程。常 见的k d d 模型由以。卜7 个部分组成【3 j ： 1 数据选择：根据用户的要求提取相关的数据。 2 数据清理：对不一致数据进行消除。 3 数据集成：将来源不同的数据组合在一起。 4数据变换：将组合好的数据统一为适合挖掘的形式。 5数据挖掘：选定的数据挖掘算法，从数据中提取出用户感兴趣的知识。 6模式评估：根据兴趣度对发现的模式进行评估。 7 知识评价：将挖掘得到的知识以用户能了解的方式呈现给用，“。 由k d d 模型，不能把数据挖掘( d a t am i n i n g ，d m ) 简单的当作数据库的知识发现， 数据挖掘只是数据库的知识发现过程巾的一个重要步骤。可以定义数据挖掘为从大量 的、不完全的、有噪声的、模糊的、随机的数据中获墩隐含在其中的，人们事先不知道 的，但又是潜在有用的信息和知识的过干旱f 4 1 。这早的数据可以是数据库中的数据，也呵 以是文本、图形，甚至足网络上的异构型数据。发现知谚 的方法i 【i j 以是数学的，也可以 是来自其他学科的。经由数据挖掘发现的知识呵以被用于食业管理、信息查询、方案优 化、决策分析、过程控制等。可以说数据挖抓i 是一个概率统计、人工智能、模式谚 别、 比较有代表性的是基于几何距离度量的聚类方法，如欧式距离、曼哈坦距离、明考斯基 距离等。聚类可以作为一个独立的工具，获得数据的分斫j 状况，观察每一个类中数据的 特征，集中对特定的类的集合作进一步地分析；也可以作为其他算法( 如分类和定性归 纳算法) 的预处理步骤。最近的研究中，大多被用来解决大型数据库或高维数据库等的 聚类挖掘问题。 分类( c l a s s i f i c a t i o n ) - 分类过程中将依据样本数据形成的类知识对源数据进行分 类，进而进行事物的描述和预测。与聚类不同，分类中的类是已知的。分类过程通常分 为两步：构造分类模型和使用模型进行分类。分类模型是通过分析，山属性描述的数据 库元组构建的，使用时要先评估分类模型预测的准确率。分类模型的构造通常用分类规 则、概念树、数学公式、神经网络等形式表示，常用的分类方法主要有决策树、概念格、 遗传算法、贝叶斯分类、人工神经网络等。 。预；1 9 1 , l j ( p r e d i c a t i o n ) 预测是对己知的数据变化规律进行归纳总结，建立数据的变 化趋势模犁，并用建锣的模型对未米数据及叮能的特征进行拙述的过程。视构造模型的 第一章绪论 不同以及给定样本的属性值、值区m 的不同，可以使用不同方法，例如线性叫归、非线 性网归、多元回归等。通常以预测方筹衡量预测的精度和不确定性。 时序模式( t i m e s e r i e sp a t t e r n ) ：时序模式是指发现重复发生概率较高的事物的一 种时间序列分析方法。时序模式l 一样用己知的数据预测未来的值，与预测的区别是时序 模式使用的数据考虑了时问因素。 偏差分析( d e v i a t i o n ) ：偏差分析是发现数据库巾异常数据的过程。其基本方法是 寻找数据与观察结果之间的异同。 1 1 3 数据挖掘的技术 为了实现数据挖掘的功能，会用到各种各样的技术。常用的数据挖掘技术有：决策 树、神经网络、遗传算法、粗糙集、模糊集、概念格等【5 l 。 决策树：决策树足从机器学习角度研究和发展起来的，具有描述简单，分类速 度快，适合大规模数据处理等优点。核心问题是如何使构造好的决策树精度更高、 规模更小。决策树中最上面的结点为根结点，每个结点不同的输出将导致不同的分枝， 最后到达叶子结点。决策树中的缚个分枝都足一个新的决策结点或叶子结点。决策结点 通常对应于待分类对象的属性代表一个问题或决策，叶子结点代表一种可能的分类结 果。构造决策树分为生成和剪枝两步：生成即由代表训练集样本的单个结点丌始，以递 归的形式白顶向下构建决策树；剪枝即用测试集测试生成过程构建的决策树，剪去可能 影h 向决策树精度的分枝，分为先剪枝和后剪枝。 神经网络：神经网络是一种越来越受到人们关注的算法。人工神经网络以m p 模型和i i e b b 舰则为基础，模拟人脑思维的方式，建立了三大类多种神经网络模型：前 馈式网络，反馈式网络，白组织网络，足种以。定的规则学习的非线性预测模型。由 于神经网络具有稳定性、自组织性、自适j 赶性、并行处理、分布存储和高度容错 等特性，在分类、聚类、关联规则挖掘等多种数据挖掘任务中广泛应用。神经网络方 法的缺点是不可预测性，人们并不足总能理解机器的学习和决策过程。 遗传算法：遗传算法是一种仿生算法，是模拟生物的d n a 理论与种群物竞 天择的近似最优解全局搜索算法。采用遗传算法，首先要对求解的问题进行染色体 编码产牛初始群体；然后通过计算适宜度，按照定比例对进行染色体的复制、变换、 突变产生新的种群。重复上述过程，直剑一定代数，求得较佳个体。遗传算法也足一 科t 数据挖掘中常被应用的技术，具有易于并行、易于和其他算法结合等优秀性质。 遗传算法的缺点是较复杂且不能保证精确，不适合解决较小规模的问题。 粗糙集：以波兰数学家p a w l a k 为代表的研究者在1 9 8 2 年首次提出的粗糙集的 概念格分布式构造算法彬f 究 概念。料糙集是一种研究不精确、不确定知识的数学工具，能有效地从各种不精确、 不一致和不完整等不完备信息中发玑隐减的知谚 ，揭示潜在的规律。拳 i 糙集不需要给 出预备信息和附加信息，提供了消除冗余属性的数学方法，算法简单，适合并行 运行。可以直接从题设出发，通过1 i 可分辨关系和不可分辨类确定问题的近似域找出 问题的潜在规律。粗糙集的缺点是建立在集合沦基础上，不能直接处理连续的属性， 而现实中的信息往往是连续的，因此使用粗糙集通常要提前对连续属性进行离散 化。 模糊集：模糊集理论推翻了经典集合论中r 亡素与集合之间的关系不是属于就是 不属于的概念，它认为元素与集合之间除了属于和不属于，还能以一定的程度属于某个 集合，也町能以不同的程度分别属于几个集合。经典集合沦中集合的边界是清晰的，模 糊集理论中集合的边界是模糊的。系统越复杂，模糊性越强。模糊集合理论是用隶属 度来刻画事物办此亦彼的特性。在数据挖掘领域，模糊集可以被用作进行模糊综合判别、 模糊聚类分析等。 概念格：即形式概念分析，是德国的r w i l l e 教授在2 0 世纪8 0 年代初提出来 的，用于概念的发现、排序和显示。概念格中的每个结点是一个形式概念，由外延和内 涵两部分组成。外延是概念覆盖的对象：内涵是概念的描述，办即该概念覆盖实例的共 同特征。概念格通过h a s s e 图直观而简洁地体现了概念之问的泛化和特化关系。概念格 足进行数据分析的一种有力工具，具有完备性、简洁性和直观性，在信息检索、软件工 程、知识工程和规则发现等方面得到了广泛的应用。 1 1 4 数据挖掘的应用 只要有需要分析且具有价值的数据库，都可利用挖掘工具进行面向服务的数据发 掘，且使用便捷客户不需要具备专业技术( 挖掘时借助专业工具，结论转化为客户能够 理解的模式) ，因此数据挖掘技术的应用十分广泛。当前，其主要应用在如下领域： 金融f 1 常的金融事务中会产生大量的数据，通过分析这些数据，发现数据模式 ( 对应现实中的客户、消费群体) 及数据特征( 对应现实中组织的金融和商q k 倾向) ， 从而预测金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包括数据统计、市场 分析、市场预测、偏差分析、信息分类、信用评估等。 医疗保健医疗保健、l k 同样有着海量的数据需要处理，但这个行业数据模式往往 并不通用，不同的机构采用的信息管理系统管理不同，数据保存的格式也不同，可以说 在医疗保健业数据足无组织的。因此，数据挖掘的关键任务是进行数据清理，将结构不 同的数据经过预处理整合到一起，进而通过数据挖掘系统分析。例如g t e 实验室就通 4 第一章绪论 过对不h 医疗保健机构的数据进行多维分析，对比和预测数据、统计并处理偏差，最后 生成报表。 市场业市场业和金融、i k 类似，数据挖掘技术被应用在市场定位、消费者分析、 消费趋势分析等方面，从而轴助固家对市场进行宏观调控及企业和个人制定市场销售策 略。 零售、l 匕零售、i k 是最早运用数据挖掘技术的行业。同前，主要运用f 消费倾向预 测、库存调配管理、销售点设置、零售价格分析等。 制造业制造业对数据挖掘技术的应甩也f _ 分广泛。如：故障诊断排除、资源优 化管理、生产过程优化等。 司法案件中同样存在大量的数据，对案件数据的整理可以给法律的制定及执行 带来巨大的便利。 工程和科学天文、气象、地质、生物- t 程等科研领域中存在的信息量极为庞大， 这些数据仅靠传统的数据分析是不够的，因此，科学研究对功能强人的智能化数据挖掘 工具要求极为迫切，这种需求推动了数据挖掘技术在科学研究领域的应用发展，且目前 已经获得了很多非常重要的的研究成果，例如，j e t p r o p u l s i o nl a b o r a t o r y 利用决策树方 法对海量高维天体数据进行分析，已经帮助天文学家发现1 6 个星体，比人工分析准确 和迅速的多。 保险业通过数据挖掘呵以通过对不同职业、彳、= 同年龄层次、不同社会地位的人 进行消费倾向的关联分析，从而制定适当的保险额度和策略。 1 2 概念格 w i l l e 教授在2 0 世纪8 0 年代初提出了形式概念分析i 制。形式概念分析义被称作概 念格，目前已经在很多方面有广泛的应用，下面埘概念格进7 j ：一些仞步的介绍： 1 2 1 概念格的基本概念和定义 人们把事物的特征加以总结，得到的结果就足概念。概念格则是一种反应概念问层 次关系的数学模型。在概念格中，每个结点表示一个形式概念，每个形式概念都由内涵 和外延两部分组成。其中外延表示概念所覆盖的对象，内涵表示概念所覆盖对象的共同 特征，足该概念的捕述。概念格并不是巾纯的概念的罗列，还反j 迎着概念问的关系，并 用层次结构的形式表现出来。概念格从本质卜体现了实体和属性之间的笑系，概念之间 的泛化和特化关系可以用h a s s e 图的形式简洁地体现出来。冈为概念格具有以上优秀性 质，被认为是进行数据分析和知识提取的种有力工具。目前，在信息榆索、数字图书 馆、软件工程和知以发现等力而对概念格已经有了一定的应用1 7 i 。 s 概念格分布i = 构造算法研究 1 2 2 传统的概念格的构造方法 概念格构造足概念格应用的皋础，概念格的构造方法主要分为批处理算法和渐进式 算法两大类l7 1 。 1 批处理算法 批处理算法视形式背景为整体进行构造，并不是所有批处理算法都会生成l l a s s e 图，b o r d a t 算法1 8 j 、c h e i n 算法【9 1 、t i t a n i c 算法【l o 】、g a n t e r 算法【等都是批处理算法。 根据构造概念格的不刚方式，批处理算法分为自顶向下算法、白底向上算法和枚举算法 【7 j 。自项向下算法是先构造最顶层结点，然后依次向下构造；自底向上算法是先构造最 底层结点，然后依次向上构造；枚举算法是按照某种顺序先构造出格的所有结点，然后再 生成格结点的关系。当形式背景发生改变时，即使仅仅是添加了一个对象或一个属性， 批处理算法也必须重新构造概念格。现实数据库往往是动态变化的，每次都重新构造， 代价很大，非常不合算。 2 渐进式构造算法 针对批处理算法的不足，1 9 9 5 年g o d i n 提出了概念格的渐进式构造算法瞵j 。与批处 理算法相比，渐进式算法随着形式背景中对象个数的增加或属性个数的增加，可以在现 有的概念格基础上动念更新概念格，因此被视为更有前途的构造方法。渐进式构造算法 的基本思想是将当f j 要插入的概念和概念格中已有的所有概念比较，根据比较的结果把 结点分为不变结点、更新结点和新增结点，然后分别进行处理，最经典的渐进式算法是 基于对象变化的g o d i n 算法【l2 1 。在g o d i n 算法的基础上，国内外学者进行了许多改进， 例如：文献 1 3 】提出了基于索引树的概念格快速构造算法。文献【1 4 】提出的基于属性变 化的渐进式算法c l i fa 。文献 1 5 提出的自底向上插入属性的a d d i n t e m 算法等。 批处理和渐进式，两类算法各有利弊，适用于不同的形式背景，构造概念格时算法 的选择通常是依照形式背景的特点选择的。其中：b o r d a t 算法适用于数据规模较大的稀 疏或平均密度数据，这是因为当数据量较小时，b o r d a t 算法时问复杂度远大于其他算法， 但随着数据规模增加，b o r d a t 算法的时f h j 复杂度与其他算法的差距逐渐变小，多数情况 下，尤其是当h a s s e 图已经构造好时，只要数据规模足够，它会比其他算法更好；对于 数据规模较大的稠密数据，最快的算法足自底而上的批处理构造算法；数据规模较小时， g a n t e r 算法和c h e i n 算法足一个很好的选择，但随着数据量增大这两种算法的效率会降 的很低。相对丁一卜面说剑的批处理算法，渐进式算法更适合变动中的数据库，仅从一次 构造的效率来看，当数掘规模较小时，渐进式构造的效率要优于大多数的批处理构造方 法；数据规模较大时，由于渐进式概念格构造中新增对象要与格中已生成的大量结点比 6 第一章绪论 较，其构造效率要低于批处理构造方法i l6 | 。 1 2 ： 概念格的分布式构造 当i 订，由于实际应用中数据量不断增大，概念格构造的复杂性，己成为网扰概念格 进一步应用的主要难题之一。随着分布式数据库技术和计算机网络技术的发展，概念格 的分仃式构造，已成为概念格构造研究的重要内容之一。典型的概念格分布式构造包括 w i l l e 提出的叠置和并置两种【 j 。叠置即通过形式背景的纵向合并构造概念格，并旨即 通过形式背景的横向合并构造概念格。叠置和并置拆分形式背景的方法不同，但构造思 想没有本质区别。在此基础上，n g u i f o j s l 提出了基于闭包的概念格分布式构造算法， n j i w o u a 1 9 1 提出了基于b o r d a t 算法的概念格分布式构造算法，刘宗田、李云等【2 0 2 1 】 提出了基于渐进式的概念格分御式构造算法。这些概念格分布式构造方法普遍偏向理 论，在实际运用中往往受限于局域网，可扩展性低，且分配时采用一次分发，分节点构 造子格期i 、日j 丰：常点等待时间过长。 1 2 4 概念格的扩展与应用 为了使概念格更适合应用需求，人们对传统概念格还有一些扩展，如：扩展概念格 1 2 引、量化概念格【2 3 】、模糊概念格2 4 1 、加权概念格【2 5 】、粗糙概念格、约束概念格1 2 7 j 、 i c e b e r g 概念格2 8 1 和多维概念格2 引。 扩展概念格，首先引入了外延相r d 的内涵足等价内涵的概念，即等价关系的概念， 扩展了结点结构，在此基础上文献 2 2 】还提出了约简格，简化了扩展概念格。量化概念 格，矧样是引入等价关系的概念，刁i 同的是，量化概念格用对象数来表示外延，这样能 够更方便的总结数据挖掘中规律。模糊概念格，是将模糊引入概念格，形式背景是模糊 的，建立了内涵弓外延之间的映射也足模糊，通过模糊集来描述模糊概念。应用中，模 糊概念格将对象属性表看成属性与对象的隶属关系表，模糊集合中的元素属于集合的程 度称为隶属度。加权概念格，对不同兴趣度( 重要度) 的内涵进行区分，即给内涵引入 了一个0 至1 1 之间的权值，使提取山的知识更有利于用户的决策，具有实际意义。粗糙概 念格，用粗糙集中的近似集拙述概念格中节点的内涵所对应的外延，使外延可以具有不 确定的性质，从而使概念格可以描述带有不确定件知识的形式背景的能力。i c e b e r g 概念 格，它根据概念的支持度，把格分为上卜两部分。上部分是i c e b e r g 概念格，由频繁概念 构成；下部分山非频繁概念构成。i c e b e r g 概念格是闭频繁概念组成的半格。多维概念格， 在一般概念格的基础上，针对多维序列模式挖掘应用提出，是对概念格的泛化。多维概 念格通过结点的序列模式和关联模式把内涵分为基内涵和附加内涵，可以进行有效的多 维模式序列挖掘。 概念格分布式构造算法研究 1 3 网格 1 3 1 网格的产生和定义 网格( g r i d ) 足一种新兴的技术，崽想来源于电力网( p o w e r6 r i d ) 。将地理e 处于 i 同位置的各种资源，例如：计算资源、存储资源、带宽资源、软件资源、数据资源、 信息资源、知识资源等，连成一个逻辑整体，通过网络提供给网络上需要完成计算任务 的个体，个体完成计算任务时不用关心资源的来源i j 。 与数据挖掘相i 川，网格提出的背景建立在当今计算机技术的飞速发展一卜，尤其足储 存、网络和计算技术。这些新的发展为解决现今数据和计算量同益加大的商业和科学问 题带来了希望也带来了空前挑战。即使是最高性能的超级计算机也不总是能够应付不断 增加的计算负荷，与此同时，尽管对资源的需求不断增大，但是在网络上，并不是所有 的资源都得到了充分利用。相当多的服务器在运算一些大规模任务时处于满负荷状态， 在运算结束后处于窄负荷状态。大多数时候，整个网络上存在大量非满负荷状态的服务 器和资源。如何充分利用起这些资源，使其可以用于满足f 1 益增长的资源需求? 网格计 算就足在这种需求背景下提出的，网格在分散的控制环境下协调、调配资源；使用一定 标准的、开放的和通用的协议和接r i ；提供非平儿的服务。可以说，网格为用户提供一 体化信息和应用服务( 计算、存储、访问等) ，把整个互联网及互联网上的资源整合成 一台超级计算机，通过虚拟组织和网络资源共享在这个虚拟的超级计算机中进行协同工 作，实现信息共享消除网络上的资源孤岛。网格具有高度抽象、自相似、动态性、多样 性、分布与资源共享等特征，依据侧重不同，分为：强调计算力获取、管理的计算网格： 强调数据存储、管理、传输、处理的数据网格；强调信息存储、管理、传输、处理的信 息网格；强调知识存储、管理、传输、处理的知识网格；强调语义解析的网格，实现语 义互操作的语义网格。 1 3 2 网格的结构 构建网格的基础足瓦联网，因此，建设网格最重要的是标准化协议与服务。参照 i n t e r n e t 网络协议并结合网格特性，i a nf o s t e r 于本世纪初提出了网格计算协议体系 结构。该结构由五层组成，包括构造层( f a b r i c ) 、连接层( c o n n e c t i v i t y ) 、资源层 ( r e s o u r c e ) 、汇集层( c o l l e c t i v e ) 和应用层( a p p l i c a t i o n ) 。后来相继提出的开放网格 服务体系结构( o p e ng r i ds e r v i c e sa r c h i t e c t u r e ，o g s a ) 和网络服务资源框架( w e b s e r v i c er e s o u r c ef r a m e w o r k ，w s r f ) 都是建市在网格计算协议体系结构基础上。计算 任务使用网格时，通过结构各层间接 调用相应的服务，再通过服务调动网格上的资源， 最终达到计算目的。 。o。0，戤 一 妒一 构造层为上层提供共享资源，受上层需求影响。构造层组件的功能包括资源查询和 资源管理的服务质量保证( q u a l i t yo f s e r v i c e ) ，受控资源由局部的物理或逻辑资源组成， 包括计算资源、存储系统、目录、网络资源、分向式文件系统、分布计算池、计算机群 等。 连接层定义网格中认证授权控制等安全方嵋i 的核心协议，保证资源瓦访的便利和安 全。这一层实现资源i 日j 的数据交换和通讯时的授权认证、安全控制。该层通常解决代理 委托、提供服务的登录、用户信任策略设置、网际与本地安全策略不同时进行的处理等。 资源层建立在连接层协议之上，以服务的形式共享资源。该层通过调用构造层服务 访问和控制局部资源，提供安全会话、服务查洵、服务运行状况监测、资源能力判定等 功能。 汇集层汇集资源层提交的受控资源情况，供网格形成的“超级计算机”共享和调用。 汇集层通过调配资源层服务实现各种共享行为，通常提供目录服务、资源协同、资源监 测诊断、数据复制、负荷控制、账户管理等功能。 应用层和i n t e r n e t 网络协议中的应用层相同，是为网格上用户提供的应用程序层。 实现网格与人的沟通。 1 3 3 网格的应用 目前，网格应用多为研究服务。国外f 在进行的主要的网格计算相关研发项目有： 网格基础设施g l o b u s ，其内容包含资源调配、数据管理、应用丌发、网格安全等，g 1 0 b u s 史类似于一种基准，g l o b u st o o lk it 就来自g 1o b u s 项目。g l o b u st o o l k i t 是完全开源 的，用广i 可以很方便的在官方网站f 载到最新版本用于网格系统建设。信息动力网格 ( i n f o r m a t i o np o w e rg r i d ，i p g ) ，是美国国家航空航天局丌发建设的，目的是为航空 航天研究提供持续、可靠的计算力资源。美国困家技术网格( n a t i o n a lt e c h n o l o g y g r i d ) ，通过网格中间件( g r i d w a r e ) 、系统工具的高级分布式计算基础设施( a d c i ) 构 建计算体系，目的是提供满足美国能源部研究所需科学计算的计算力资源。虚拟实验室 项目( v i r t u a ll a b o r a t o r yp r o j e c t ) ，为处理分子生物学中进行的大规模计算建立的 网格体系，主要解决大规模密集数据集。天体物理仿真合作实验室( a s t r o p h y s i c s s i m u l a t i o nc o l l a b o r a t o r y ，a s c ) ，为天体物理学领域研究而构造的网格体系，利用 g l o b u s 及其他项目的研究成果提供大规模并行计算力资源，实现天体物理仿真实验。 幽际虚拟数据格网实验室( i n t e r n a t i o n a lv i r t u a ld a t ag r i dl a b o r a t o r y ，i v d g l ) ， 由国际上多个网格实验审共卉j g , j 建，f 1 的足提供更完善的网格标准，为更大规模的使用 网格做准备，事要合作者仃欧盟的数据格网( d a t a g r i d ) 、美国的格网物理网络( g r i d 9 概念格分布构造算法研究 p h y s jc sn e t w o r k ) 和粒予物理数据格网( p a r t i c l ep h y s i c sd a t ag r i d ) 等。 圈内的网格研究起步较晚，但也已经取得了一定成就。先进计算基础设施i 二程 ( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ，a c il ：程) ，由清华人学计算机系承担研究， 通过把不同地域的高性能计算机、贵重仪器、数据库等剧高速网络连接在一起构成一台 超级计算机，a c i 计划已经取得阶段性成果。织女星网格( v e g ag r i d ) 主要研究服务网 格，由中科院计算所2 0 0 2 年起动研究，利用幽际已有技术，并有一定的创新。 1 4 本文主要的研究内容及论文的组织安排 1 4 1 研究内容的提出 随着分布、异构数据集的大量出现，分布式构造成为研究概念格构造的主要内容之 一。目前的概念格分布式构造方法普遍偏向理论，通常是预先将初始化好的同域或同项 概念格分发f 去，分节点构造好子格后交由主节点合并。这是由于实验环境往往是局域 网，而实际应用各服务器往往不在同一地域。实际使用时，这些构造算法存在扩展性差、 资源利用率较低等问题，且分配时采用一次分发，分节点构造子格期问乇节点等待时间 过长。如何通过凋度使得分布式构造不再局限于实验室有着重要的意义。 概念格分布式渐进式构造在合并子格时需要进行大量的内涵对比，其中一些比较不 会对影响概念格的结构，这些无用的比较降低了算法性能。数据规模越大，生成的格节 点越多，合并时无用的比较( 即：冗余信息) 也越多。消除这些冗余信息，能够显著提 高概念格的构造效率，因此，如何消除冗余信息有着重要的意义。 1 4 2 论文组织结构 第一章介绍数据挖掘产生、定义、功能、技术及应用，概念格和网格的研究现状 及研究内容的提出依据。 第二章介绍概念格的基本概念及其构造算法。 第三章研究基于网格的概念格分布式构造，引入网格作为分布式平台，采用多次 分发的调度策略，使概念格分布式构造更方便在实际应用中使用。 第四章研究剪枝的概念格渐进式分布式构造，说明构造过程中确实存在冗余信 息。利用剪枝技术，消除了不变节点，提高了概念格构造效率。 最后，作为本文的结束，对所做的研究：r ：作进行总结，并展望了今后进一步要做的 一些工作。 1 0 第一：章概念格 第二章概念格 2 1 概念格的定义 概念格是根据数据集中对象与属性之i b j 的i 元关系提卜h 的一种概念层次结构。由于 可以便捷、直观的表示概念及概念间的关系，被视为数掘分析和知识提取的一种有效数 学工具。参照文献 6 ，概念格的定义和概念描述如下： 定义2 1 一个形式背景k = ( g ；m ，i ) 为二三几组，g 表示埘象集，m 表示属性集，i 是对 象和属性之间的二元关系。( a ，b ) 为k 上的任意二元组，a _ c g ，b m ，且( a ，b ) 满足： 1 ) f ( a ) = m m l v g a ，g l m 、 2 ) g ( b ) 2 g g l v m b ，g l m ) 若f ( a ) = b 且g ( b ) = a ，即二元组( a ，b ) 满足最大扩展性，则称( a ，b ) 为形式背景 k = ( g m ，i ) e 的一个概念，a 称为概念( a ，b ) 的外延，b 称为概念( a ，b ) 的内涵。 定义2 2 若( a l ，b 1 ) 、( a 2 ，b 2 ) 是形式背景k - - ( g , m ，i ) 上的概念，且a i a 2 ( b l b 2 ) ， 则称( a 1 ，b 1 ) 是( a 2 ，b 2 ) 的子概念( 子孙节点) ，( a 2 ，b 2 ) 是( a l ，b 1 ) 的超概念( 祖先节点) ，并 让为( a l ，b 1 ) ( a 2 ，b 2 ) ，关系称为足概念的层次序( 简称为序) 。形式背景( g m ，i ) 的所 有用这种序组成的集合称为形式背景( g m ，i ) 上的概念格。格中所有概念的最大下确界称 为空概念，所有概念的最小上确界称为全概念。 2 2 概念格的构造方法 概念格作为一种有效的数据挖掘工具，已经在一些领域得到应用，并表现出了较强 的优越性。但是，概念格构造的复杂性制约了概念格的进一步应用，国内外研究人员对 概念格构造方法，进行了大量研究。目前，主要分为批处理和渐进式两类构造方法。 2 2 1 批处理构造算法 批处理算法分为自顶向下算法、自底向上算法和枚举算法f 67 1 。自顶向下算法是先 构造最顶层结点，然后依次向下构造，例如b o r d a t 算法、t i t a n i c 算法等；白底向上算 法是先构造最底层结点，然后依次向上构造，例如c h e i n 算法、m c a 算法等；枚举算法 是按照某种顺序先构造出格的所有结点，然后再生成格结点的关系，例如c a n t e r 算法、 n o u r i n e 算法等。 下而以自顶向一卜算法说明概念格批处理构造算法的结构瞄j ： 1 ) 建立只包含顶端节点的队列f 和格i ； 2 ) 对f 中的第个节点c i 生产其全部子概念； 3 ) 若上一步产生的一个子概念c 2 没有被产生过，添加c 2 至队列f 和格l 中； 4 ) 添加c l 和c 2 问的关系； 1 1 概念格分斫j 式构造算法研究 5 ) 重复2 4 步直到队列f 为空。 2 2 2 渐进式构造算法 概念格的渐进式构造算法的思想米源于概念格的维护。构造时视形式背景为不断变 化的，首先按空形式背景构造格，然后逐条将形式背景巾的对象或属性插入到概念格中。 在形式背景k = ( g m ，i ) 中追加属性或对象时，用新增的属性或刈象比较k 对应概念 格l ( k ) e p 所有概念，依据比较结果得到新的概念格l ，( k ) 。l ( k ) 中节点分为：不变节点、 更新节点和新增常点12 1 。 不变节点：与新增属性或对象属性无关的节点； 更新节点：在原概念基础上更新得到的节点； 新增节点：原概念格中没有的节点，由于新增节点时概念间的关系产生变化，因此 需要对相应的边进行修改。 定义2 3 设l ( k ) 是形式背景k = ( g m ，i ) 对应的概念格，c i = ( a i ，b 1 ) 是概念格l 上的任一节 点，b 2 是新增对象s 的属性集，往