（计算机应用技术专业论文）基于分布式概念格的知识发现研究.pdf

基于分布式概念格的知识发现研究 摘要 知谚 发现和数据挖掘是人工智能、机器学习、数据库和统计理论等相交叉 形成的新学科，目的是从数据库中提取有用的模式，因而具有广阔的应用价值。 然而，随着信息技术日新月异的发展，人类生产生活的各个领域都积累了规模 庞大的数据，从大规模的数据中高效地提取有用的模式已经成为了一种挑战。 为此，并行和分布式的方法成为解决这一问题的一个有效途径受到重视。然而， 组织数据的方式和并行处理的方法无论在理论上还是在技术卜都有许多问题需 要研究。概念格模型具有坚实的理论基础、完备的结构以及并行性的特征，因 而成为解决上述问题的一个重要工具。本文针对分布式概念格的模型以及在此 基础上的数据挖掘开展研究。 论文的主要工作和贡献如下： 1 概述了知识发现和数据挖掘研究和应用。 2 阐述了概念格的数学基础、传统的概念格研究及概念格的扩展模型和 概念格构造，分析了批处理算法和渐进式算法的优缺点。 3 给出了一种新的分布式概念格的模型，提出了与传统分布式数据库中 的横向、纵向、混合型分片方式不同的数据有机分割方式，在此基础 上给出了便于并行实现的概念格构造算法s e a 。该算法结合了批处理 算法的并行性和渐进式算法的高效性，使得在进行平行处理的同时又 保持了算法的性能。实验表明该算法在时间性能上要明显优于基于原 始形式背景的算法( g o d i n ) 。 4 在分布式概念格模型的基础上，提出了基于类特征的分类算法。该算 法利用基于子全概念的概念格构造算法s e a 对每一个类生成子格，通 过在各个子格上提取的特征相互之间的协作来实现对新对象的分类。 关键词：概念格，知识发现，数据挖掘，分布式，分类 r e s e a 比ho n l ( n o w i e d g ed i s c o v e r y i nd a t a b a s e s b a s e do nd i s t r i b u t e dc o n c e p tl a n i c e s a b s t r a c t a st l l er e s u ho fa n i f i c i a l i n t e l l i g e n c e ，m a c h i n el e a n l i n g ，d a t a b 鹊e s a n d s t a t i s t i c sa n do t h e rs u b j e c t s t h ea i mo fd a t am i i l 崦a n dk d di st of i n ds o m e m e a i l i i l g m ip a t t e m sf b m d a 钯b a s e s 淅ma lt e c h n o l o g y s oi th a sg r e a ta p p l i c a t i o n v a l u e 、i t l it l l es i t u a t i o nt h a tt h eq l l i c kd c v e l o p m e n to f i n f o 舯a t i o nt e c l l l l o l o g yl e a d s ar o c k e ti na 王lk i n d so fd 姐f e t c gm e 8 n 王r l g f i l lp 讹n l se c t i v e l y 舶ml a r g e d 砒a b 踮e sh a v eb e c o m eac h a l l e n g ea 1 1 da i le 脓t i v ew a yt os o l v et h ep m b l e r ni s p 删l e l d i s t r i b u t e dt e c h n o l o g y t h e r e a r ea l s om 姐y p r o b l e m s a b o u th o wt oo r g a l l i z e d i s t r i b u t e dd a t as t o r a g ea n dp a r a l l e lp r o c e s s m gw h e 协e ro nt e c l l l l o l o g yo ro nt h e o r ) ， t 0r e s e 鲫c h d u et oas t a b i l i t y m e o r yb a s e ，s e l f c o 慨n e d 曲m c t u r ca i l dp 耐i l e l c h a r 孔t e r ，c o n c e p tl a n i c ei sat o o l t os o l 、忙t l l ep r o b l 锄s a f o r e s a i d i i lt l i i sm e s i st | l e m o d e lo f d i s 缸b 曲鲴c o n c e p tl a m c ea n dd a t ai i l i i l i n gr c s e a r c ho nw i l i c hi sg i v e n n l i s 血e s i si n c l u d i n g 也ef o l l o w 啦c o n 把n t ： 1 t h eb a s i cn o t i o na i l dm eb a c k g m u n do ft h ed a t am i i l i n ga n dk d di s i 1 1 廿d i i u c c d 2 t h em 甜l e m a t i c a lf o l l l l d a t i o n ，t r a d i t i o n a lc o n c 印tl a n i c er e s e a r c 札e 姐e n d c o n c 印tl a t t i c em o d e l a n dt l l eb u i l d i n ga l g o r i t l l mo f t l ”c o n c e p tl a t t i c ea r e i n 仃o d u c e d n l e a d v a i l t a g e a i l d d i s a d v 姐诅g e o fb a t c h a l g o r i t h j _ l l s a n d 证c r e m e n t a la l g o r i t h m sa r c 阴a l y z c d ，b a do nw h i c han e wk i n do f p a m l l e l a 王g o r i t l l m w h i c hc o m b i n e st h ea d v 踟m l g c so fb o 恤b a t c ha i g o r i t h m sa n d i n c r e m e n t a l a l g o r i t l l m s 盯ep u t f o ，a r d 3 an e wk j n do fd i s 仃i b u t c dc o n c e p tl a t t i c em o d e li sg i v e no u t ，a d v a n c et l e o r g a i l i cs p l i tw a y o fd a 饥w 址c hi sd i 艉r e mt ot h es p l i tw a yi l l 廿a d i t i o n a l d i 矧b i i t e d 出l 切b a s e st l l a t s p l “也ed a t a i i lh o r i z o n t a ld i r e c t i o n ，v e r t i c a l d i r e c t i o no rm i x e dw a y s 职l ep a 试l dc o n c e p tl a m c eb l l i l d h ga 1 9 0 r i 也m s e ab a s e do nm e o l - g a i l i cs p l i tc o n c e p ti sp u tf o n v a r d t h ee x p e r i m e n t s h o w 血a tt h es e aa l g 鲥n u ni ss u p e r i o rt ot h ea l g o t l l i nt h a tg e t st h e l a t t i c ef b mc o i l t e x td 慨t l y 血t 访1 e c 0 璐u m i f l g 4 o nt h eb a s i so fw m n gd a s s i 6 c a t i o nc o s t t e c h n o l o g y ac l 船s i f i c a t i o n t e c h n o l o g yw l i c hu s ct h ec l 踮sc h a r 扯t e r st oc l a s s i 毋也en e wi n s t a n c ei s 舀v e n o nm eb 船i so f d i s m b u t e d c o n c 印t l a c t i c em o d e l k e y w o r d s ： c o n c c p tl a t t i c e ，k d d ，d a l 诅疵i l i 】唱，d i s 埘b l l t e d ，c l a s s i 行c 撕o n 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合 合肥工业大学硕士学位论文质量要求。 答辩委员会签名 姓名 工作单位 主席：摧解绋彩 导师： 弦憋冷咯 奔彤i 职称 撇 苏压 务瑶 易1 张 刻钰及 】 撇 碌吖i 甜y 口 碧 划叫老 一 口贝夤 圈卜l 图卜2 阁13 图2 一l 图3 1 图3 3 图3 2 图3 4 图3 5 图3 6 图4 1 图4 2 图4 3 图5 一l 图5 2 插图清单 数据库技术的发展2 数据挖掘的过程4 典型地数据挖掘系统结构5 表2l 形式背景对i 亟的概念格1 4 子全概念( f 1 4 5 ) ，f e l ) ) 牛成的于格l 1 一3 0 了全概念( 】2 6 r i ，m l ，s l ) 生成的了：格l 3 3 0 子全概念 2 ，3 1 1 吐，m 1 r l ) 生成的子格l 2 3 0 由子格l l l 2 l 3 合成的完整格3 1 s e a 算法与g o d i n 算法的实验结果3 2 最大子格符点数与整个格节点数的比较3 2 个简单的贝叶斯信念网络3 8 由元组忸1 ，x 2 ，x 3 。x 6 ) 建造的概念格l 4 5 由元组仪4 x 5 璃! 造的概念格l 2 4 5 c o n d i s 系统体系结构5 0 图42 表4 2 对应的概念格5 3 i i i 表格清单 袭zl 太阳系行星形式背景l4 表4l 一个小型的数据库实例2 8 表41图4 一ll u n g c a n c e rc p t 表3 8 表5 】 一个形式背景j 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得 的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也卞包古为获得 金壁工业左。茎 或其他教育机构的学位或证书而使用过的材料。与我一同j 二作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示谢意。 一签勿当芽 签字日期：炉歹年，月，专日 学位论文版权使用授权书 本学位论文作者完全了解垒尴工些杰堂有关保留，使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被 查阅和借阅。本人授杈盒壁工些盘堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期：年月同 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期：曝旷月h 电话： 邮编： ，t 臣6 弓衍叫f 釉弦 豸 致谢 衷心感谢我的导师胡学铡老师在整个论文阶段给予的悉心指导和帮助。导 师不断从学业t 、生活上关心作者。为作者创造了良好的_ 作和学习环境，使 作者在理论和实践两个方面都得到了良好的锻炼，没有导师付出的辛勤劳动， 本论文是不可能完成的。三年来，胡老师严谨的治学态度和谆谆教导给我留下 了深刻的印象，馊作者终身难忘。 同时，作者深深地感谢k d d 研究室的王浩老师对作者的指导、肩发与帮 助。 感谢我的同学孙莹、刘凡、郭亚光以及师蛆张玉红给予的无私帮助和支持。 感谢合肥工业大学研究生部及计算机与信息学院的王新生老师和各位院 系领导对我的帮助与支持。 感谢我的父亲，母亲和蛆姐为我提供的无忧无虑学习环境。 作者：唐志军 2 0 0 5 年5 月 第一章概述 伴随着数据库技术、网络技术以及许多高新技术的广泛应用，人们在享受 科技成果的同时，必须顽对数据库数量激增和信息处理能力有限的现状，从数 据库中提取知识( k n o w l e d g ed i s c o v e 叫i nd a 诅b a s e s ，简称k d d ) 应运而生， 并且成为个研究和应用的热点问题。本章主要介绍k d d 的产生背景，有关 概念，以及k d d 的研究和应用的现状和面临的挑战。 1 1 1 数据库技术的发展 1 1 问题的提出 目前，随着社会各领域中信息的数字化，电子商务的发展和e r p 技术的应 用，使数据库技术及网络通讯己成为重要的基础。数据库技术与网络的发展既 促进了应用的展开，同时引发了一系列新的问题。 四十多年来，随着计算机应用的普及和数据处理在计算机应用中所占比重 的上升，数据库技术得到了迅速发展，但是随着计算机硬件设计、生产进步和 互联网的发展，也给数据库技术的研究提出了新的课题。 从2 0 世纪6 0 年代的数据库技术出现到现在，已经从大量数据的管理系统 演变成大量数据中信息的提取和发现的综合信息系统【见图1 1 】。 数据库是6 0 年代末期作为数据管理的最新技术而出现的。最初的数据信 息存放于文件中，文件仅作为数掘的存储方式，文件管理与数据管理是同一个 概念，不存在数据管理的概念。数据、文件、信息并没有区别开来。随着数据 数量和内容的变化以及计算机由单纯的科学计算转变到数据处理，数据管理的 方式由文件管理形式转变到数据库管理方式，在不到十年的时间内，经过不断 的研究和发展出现了功能强大的数据库系统。从7 0 年代开始，数据库和信息技 术的研究和发展主要集中在层次数据库和网状数据库系统方面。主要的工作成 果有：数据库系统、数据建模和数据组织技术；存储技术；检索和事务处理等。 研究和开发主要集中在进一步地深化数据管理和信息的处理方面。 8 0 年代中期以来，由于数据类型的极大丰富和人们对数据处理的不断提高 的要求。关系数据库被广泛接受，由此而展开的应用使得数据库管理系统的发 展进入了新的高潮期。以关系数据库管理系统为代表的数据库管理系统也逐渐 成熟。【见图1 1 】 图1 - 1数据库技术的发展 1 1 2 网络技术的发展 k t e m e t 技术的出现和发展促使人们对数据库技术提出了更高的要求。由于 数据库技术在不同的应用领域迅速得到应用，造成数据库的格式不一致。 i n t e m e t 技术的发展可能会造成数据的存储地点不同，不同的用户需要通过网络 访问处于不同地点的不同格式的数据库，因而需要运用一定方法来处理，数据 仓库( d a _ t aw a r e h o u s e ) 和联机分析处理( 0 l a p ) 随之出现。数据仓库是异种 数据统一的组织方式。而联机分析处理的数据分析技术对于数据的深层次分析 2 存在不足。 面对信息时代的美好前途，一方面是迅速积累的海量数据，另一方面是人 们对数据处理和分析上的捉襟见肘甚至是困惑，信息的有效利用率和其自身的 快速膨胀极不相称。据估计，世界f ：的信息量每2 0 个月就要翻一番，作为信息 的主要存储形式之一的数据库的规模和数量的增长速度则更快 1 0 】。从其中获 得人们需要的信息是一个亟待解决的课题，由于现存的专家系统技术对用户和 专家的知识具有较大的依赖性同时分析过程常常有偏差和错误，因此数据挖 掘( d m ) 技术适应实际需求应运而生，经过不断的研究和实践，已经在商务 决策、知识库和医疗研究领域做出巨大贡献，成为数据分析的主要工具。 1 2 1 基本概念 1 2 知识发现和数据挖掘 知识发现( k n o w l e d g ed i s c o v e r y 洒d a t a b 硒e s k d d ) 是从数据中识别有效 的、新颖的并且可能是有价值的可理解的模式的非凡过程 2 9 】( 也有人认为知 识发现和数据挖掘是同一个概念，本文采用，数据挖掘是知识发现的一个阶段 的观点) 。 数据是实例或者事务、样本的集合。例如数据库中一条记录等。 一般地说，数据挖掘的数据类型可以是任何类型的信息。其数据的存在形 式有多种形式，如可以是保存在本地的关系数据库、层次数据库、网状数据库， 也可以是通过网络连接的异地的异构数据库，甚至是早期的展开文件( n 砒右l e s l ， 还可能是多媒体数据库、空间数据库等。 模式是以某种语言描述的数据子集，或者是可用于该子集合的模型。因此， 提取一个模式也称为对数据拟合一个模型或从数据中发现结构。或更一般地说 是发现数据集合的任意高级描述。模式的表现形式多种多样，根据挖掘的任务 的不同，模式的类型有：特征化和区分；关联模式；分类和预测模式：聚类分 析：演变分析等。其中较常见的表达形式是规则的形式：特征规则的发现：关 联规则的发现：分类规则的发现：序列模式的发现等，每一种规则都有其相应 的发现的方法。 由于k 叻的目标是发现隐含在数据中的模式( 知识) ，服务于用户，提高 效率，因而模式的有效性、新颖性、有价值和可理解性显得尤其重要。通常使 用必趣度的这一个重要的概念来刻画，其中已经结合了有效性、新颖性、有用 性和简化等指标。兴趣程度函数可由k 叻系统显式地定义或以发现的模式或模 型的有序排列来隐含地给出。其相关的客观度量如支持度和置信度，每个客观 度量都于一个用户所确定的阈值相关联，体现用户对相关模式的认可程度，以 此来判断是否接受所挖掘的模式。其主观度量主要反映用户的需要和兴趣，因 3 人而异，因挖掘任务而异。 非凡过程意指某些搜索是复杂的，即不是一个象计算数据的平均值那样的 简单计算问题。同时也指明搜索的过程中不发现显而易见的模式，而特指发现 隐含的模式。 1 2 2k d d 过程和任务 术语“过程”意指k d d 包括许多阶段，包括数据清理j 集成、选择和变 换、数据挖掘、模式评估与表示、形成知识【见图1 2 】。 文竹 当日鲫 骘抟= = = = 目标数据可赶理数据 模式知识 图卜2 数据挖掘过程 k d d 过程中的数据清理主要用于消除噪声或不致数据：数据集成主要是 多种数据源的组装和集成，可能需要集成的数据处于不同的位置或不同数据格 式：数据选择从数据库中检索与分析任务相关的数据；数据变换的目的是将来 自各种数据源的数据变换成适合挖掘的形式：数据挖掘根据不同的任务，使用 有关方法发现其中的知识，如各种规则：等价搜则，蕴涵规则，关联规则等： 模式评估主要目的在于根据某种兴趣度度量，识别表示知识的真证有趣的模式， 从整个知识发现的过程看，模式评估在评价模式的同时对所发现的知识进行优 化，力求提交给用户的知识最实用，最有价值。知识表示阶段使用可视化和知 识表示技术，向用户提交挖掘的结果，为用户的易理解考虑，这个阶段主要采 用可视化或者是相关的显示化的技术。 数据挖掘任务主要有两类：预测和描述。预测和描述之间的分界不明显( 某 些预测模型可用于描述，在某种程度上是可理解的) ，但理解两者的不同对理解 整个发现目标是有用的。特定问题的数据挖掘的预测和描述是相当重要的。然 而在k d d 中，描述比预测更为重要。而在许多模型学习和模式识别问题中， 预测常是主要目标。 1 2 3 数据挖掘系统的构成 数据挖掘系统至少经过图1 2 中所述的一般过程，因此必须具备相关的构 件( 图1 3 ) ：数据预处理构件、数据挖掘引擎、模式评估构件、知识库构件 1 0 。 4 暑一 一垦 知识库 数据厍数据仓厍 图卜3 典型地数据挖掘系统结构 数据预处理构件：主要是将不同形式的数据经过集成、转换为可以被数据 挖掘引擎所能识别和使用的数据，为挖掘准备数据。在这个阶段，除了完成多 种数据的集成外，还要进行数据的预处理工作，将噪声和异常数据尽力删除， 并把所要进行挖掘的数据表示成种合适的数据形式，便于挖掘。 数据挖掘引擎：接受处理过的数据，根据挖掘任务的要求选用合适的挖掘 算法，从数据中提取有用的模式。这个阶段的主要任务是完成算法、模式的生 成和对知识库中先验知识的利用。同时为了提高效率，利用先验知识优化算法。 模型估价构件：模式的有效性、新颖性、有价值和可理解性是评价模式的 标准。如前所述，通常使用兴趣度概念来刻画，兴趣度在挖掘过程中可以是用 户和挖掘引擎的交互接口，用户通过它控制挖掘集中到有趣的模式上。有时直 接将该构件集成在挖掘引擎中，提高挖掘的效率。 知识库构件：知识库是经过专家和用户的检验和认可的模式。可以在新的 挖掘任务中使用和进化。 该系统的核心在于数据挖掘引擎和模式评估模块的设计，用户通过各个模 s 块的接口控制或者是约束模块的行为来达到挖掘的效率和精度要求。 k d d 过程是一个数据、用户和挖掘算法相互作用的过程，具有些智能性 和交互性的特点。数据挖掘根据不同的挖掘任务，最多只需要用户给定相关的 挖掘要求如规则闽值等，挖掘引擎就能自己完成任务，根少再需要用户的丁 预。但是有用户的参与卜，往往利用相关的先验知识，提高挖掘的效率和精度。 因此在挖掘的过程中，用，、和专家的参与程度与系统的智能性相辅相成。 1 2 4 数据挖掘发展及所面临的问题 数据挖掘( k 叻) 是一个多学科交叉的研究领域，涉及数据库技术、统 f 学、 机器学习、高性能计算、模式识别、神经网络等技术的集成，并和专家系统等 领域紧密相关。并借鉴了这些领域的研究成果，不断丰富和发展自己。 首先，k d d 是以数据库技术为基础的，从k d d 产生、发展的过程可以看出， 数据库基础研究的发展促进了k 叻的发展。 其次，另一个与k d d 紧密相关的领域是数据仓库，数据仓库试图从单个站 点来管理异种数据源的数据库结构，并提供数据分析和决策支持。 与机器学习、模式识别在特定数据挖掘理论和算法中的交叉：模拟数据和 提取模式的方法。k d d 集中在发现被认为是有用的或感兴趣的、并且可理解的 模式方面，强调对现实世界中大规模数据集的工作。因此，针对大规模数据集 的算法的规模化性质是基本要求。 k d d 也与统计学有许多共同的内容，特别是分析数据的方法。统计方法采 用精确的方法定量化不确定性。k d d 软件系统常常在整个知识发现框架中调用 特定的统计过程来抽样、模型化、估价假设、处理噪音。与统计学传统方法相 比，k d d 方法在模型提取操作中一般要调用更多的搜索。 1 2 4 1 数据挖掘发展 数据挖掘是从数据库中提取知识，作为新一代数据库分析工具和技术，借 助于计算机系统来进行自动分析，发现其中有价值的知识。从出现以来的短短 十多年的时间内迅速发展，并已经取得了许多成果f 2 9 】。 数据库知识发现( k d d ) 在1 9 8 9 年召开的第1 l 届国际人工智能联合学术会 议( u c 赳) 上首次提出的。在这届学术会议上举行了以k d d 为主题的学术研讨 会，在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年相继举行了k d d 专题研讨会。随着k d d 的深入研究以及k d d 在许多领域的成功应用，于1 9 9 5 年在加拿大召开了第 届知识发现和数据挖掘国际学术会议，此后每年都召开大规模的国际会议。第 一本关于k d d 的国际学术杂志d a t am i 面唱a n dk n o w l e d g ed i s c o v e r y 也予 6 9 7 年3 月创刊发行。亚太地区于1 9 9 7 年在新加坡召开了首次k d d 研讨会 ( p a k d d ) ，其后又在澳大利亚的墨尔本召开了第二届，在中国北京召丌了第三 届。目前，在l j c a l 、a a a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据 库技术研究最高水平的国际学术会议上，知识发现的研究都占有较大的比例， 知识发现的研究已经成为当今计算机科学与技术研究、应用的热点领域之一。 砌) d 的动力来自于其实际应用需求。许多公司也致力于这一领域的研究、 开发。从大量的数据中找出感兴趣且有用的模式，为决策过程提供支持，是各 个企业和研究者共同关心的课题。 随着知识发现在国际上的兴起我国也积极她开展了研究和应用。目前， 在国内许多学术会议如中国人工智能联合学术会议、数据库学术会议、机器学 习学术会议等也都将知识发现列为重要的研究专题。一些高等院校与科研机构 也开展了知识发现系统的研究。我校是国内较早进行知识发现研究的单位之一， 八十年代末期以来相继在国家自然科学基金资助下开展了“从关系数据库中提 取领域知识的自动化获取研究”，在国家教委博士学科点专项科研基金资助下 开展了“从大规模数据库中自动提取领域知识的算法与实现研究”，也开展了 国家自然科学基金项目“基于粗糙集合理论的概念格模型研究”。本文即是在 上述背景下开展的研究。 数据量的激增和人们处理数据的要求的提高，产生了同益增强的对从数据 库中提取知识的工具和技术的需要，并为这一领域的发展提供了曝实的基础和 验证的条件。 数据库知识发现，是数据库与人工智能相结合的产物，但从事这一领域研 究和应用的有许多领域的科研人员。有关k d d 研究和发展的新情况见【1 1 ，1 8 ，2 7 2 8 1 1 2 4 2 数据挖掘所面临的挑战 经过近十多年的发展，k d d 在研究和应用方面取得丰硕的成果，但依然面 临来自研究和应用方面的挑战。在k d d 的研究领域中，随着数据的激增和数 据形式的不断发展，必须解决下列问题： l 数据库的多样性问题 关系的和复杂的数据类型的处理。由于关系数据库和数据仓库已经广泛应 用，因而数据库中可能包括复杂的数据对象、超文本和多媒体数据、空间数据、 时间数据或事务数据等。由于数据不同，数据挖掘任务不同，实现所有的挖掘 任务的通用方法是不现实的。雨各种挖掘系统都是根据数据类型和挖掘任务来 决定挖掘系统。 2 数据挖掘的性能问题 7 数据挖掘由于面向的是大规模数据库，因而算法的运算量较大，因此，改 进算法的时问和空间性能一直是一个重要问题。当前较常用的方法有并行的挖 掘、分布式的挖掘和增量挖掘方法以及利用先验知识来提高挖掘的效率和精度。 3 数据的预处理问题 噪声数据和不完全数据的存在，使得数据集合呈现过分拟合的状态，在此 之上面进行的挖掘必然受到影响，使得挖掘的效零和精度得不到保障，因此必 须在预处理的过程中予以删除。 4 先验知识的应用 利用背景知识指导挖掘过程，并使发现的模式以筒捷的形式表达。先验知 识的运用可以提高挖掘的速度和准确率，同时，先验知识来自于过去的实际数 据，需要适应现在的数据和进一步地调整。 1 3 形式概念分析概述 1 3 1 形式概念分析的起源 概念是人类进行思维的最基本的单位，是用来组织成为诸如判断、结论等 更为复杂思想的基础，是人类进行知识表述的一种有效手段，是一个哲学的范 畴。对概念的这种理解源于古希腊哲学，发展于十七世纪的近代学院派，进 步发展成德国标准，最终成为了世界标准1 4 】。由于概念是思维的基本单位，因 此我们不难理解为何概念会成为人工智能的一个重要组成部分。在知识表示、 知识管理、机器学习、专家系统等不同的领域，研究者们从不同的角度和观点 来分析概念，形成了对概念的不同形式化描述方法。 形式概念分析 f o 哦d c a n c e p t 趿址y s 妫大约诞生于二十世纪八十年代，当时 位于德国的d a r m s t a d t 的研究小组开始系统的研究和发展一种基于格理论的应 用软件。形式概念分析的首次描述是在1 9 8 1 年的关于有序集合的b 锄仃会议的 专题演讲上。从那以后，数以百计的相关论文开始出版和发表，甚至包括篇 格理论的数学基础的书籍。d a n n s t a d t 研究小组一直从事多达上百个基于格理论 的应用软件研究，此研究小组先前的部分成员已经建立了个小小的原型系统， 并进一步使其逐步实用化。形式概念分析看起来是一个很难理解的复杂名词。 有必要加以解释。它是一种对数据进行分析的工具或者方法，特别是可以对给 定的信息进行调查和处理。而数据应该是从人类有意义的可以理解的思维单位 一概念中抽取而形成的形式化的单元。形式化表明的是所处理的数据是形式化 的数学实体，不必和人类思维中的概念完全相同，它同时也指出形式概念分析 处理的基本数据形式是形式背景，形式背景是人类背景知识中的一小部分。 8 许多应用数学需要直接借助r 格理论来实现其最终的应用。而从一个二维 表中来构造完全的格结构已经在b i r l ( l o f r 的格理论( 1 a n i c et h e o r y ) 的第一版中加 以解释和说明。但是由于新的应j 羽目和发展的需要，b r i l d l o 行的格理论需要进 一步的扩展和更深入的研究。即使不考虑实际的应用，形式概念分析的提出也 引起了研究者的很大兴趣，由此形式概念分析从应用的角度开始走向理论的形 式化研究。 1 3 2 形式概念分析主要内容 基于b i r k l l o 仃对格理论的贡献，德国的w m e 5 】教授在1 9 8 2 年做为一种数 学理论首先引入了概念格( c o n c e p t l a n i c e ) ，奠定了形式概念分析的理论基础，将 哲学的概念进行数学化的描述，实现了概念的一种形式化描述方法。概念格理 论是形式概念分析理论的核心数据结构，被认为是知识发现和数据分析的有力 数学工具。 形式概念分析主要包含三个方面的内容： 一、基础理论，研究概念的形式化描述和定义、定理、特征等，是形式概 念分析的理论基础，目前仍有研究者从事这方面的工作。 二、概念格的形成方法，主要关注概念格快速且有效的构造，国内外提出 了多种概念格的快速构造算法，概念格的构造在形式概念分析中占有十分重要 的地位，是概念格理论的实践和概念格应用的基础。 三、概念格的应用，主要研究基于概念格的知识表示、规则发现等各种问 题，将概念格应用于知识发现和软件【程等领域。 形式概念分析作为一种形式化的数学方法和人工智能、数据库技术、软件 工程等其它领域的计算机科学有着紧密的联系，但同时又相对独立。 1 3 3 国内外研究现状 国内外基于概念格模型的知识发现研究已成为k d d 研究中的重要课题。 国外已经提出了多种概念格的快速构造算法，研究了基于概念格模型知识表示、 规则发现，并将概念格模型成功应用到软件工程、数据挖掘、信息检索等各个 领域：国内，清华大学智能技术与系统国家重点实验室进行了粗糙集与概念格 的理论研究与算法研究工作。 我校承接国家知识发现方面的自然科学基金项目和国家教委博士学科点 9 专项科研基金项目以及安徽省的k d d 项目，己完成博士学位论文3 篇、硕士 学位论文若干篇，在基于形式概念分析的知识发现研究中取得以下成绩： 1 ) 系统的研究概念格和粗糙集合之问的关系，提出一种基了：对象插入的概 念格构造算法，此算法在构造概念格的同时可以发现蕴含在概念格中的部分蕴 含规则。同时后续研究分别提出了一种渐进式和批处理的快速概念格构造算法。 2 ) 针对概念格的庞大空间存储量，引入等价内涵提出了扩展概念格、引入 冗余内涵提出约简概念格，引入相对冗余内涵提出相对约简格，豉化概念外延 给出量化格和量化的相对约简格，讨论了扩展概念格的渐进式构造算法等。 3 ) 分析基于扩展概念格的等价规则、蕴含规则、特征规则等规则的提取， 针对形式背景中对象的增加和删除、属性的增加和删除提出对已有概念格进行 修改的维护算法。 4 ) 基于概念格模型研究关联规则发现、序列模式发现，并研究了基于概念 格的分类器的构造。 5 ) 在概念格的扩展模型研究中，提出缺值背景的概念格分析和知识获取、 属性值域的偏序集结构、扩展模型的序列和格论基础。并研究了区分系统和不 可区分格。 1 。4 本文的组织 本文的其余部分组织为：第二章介绍概念格的数学模型和概念格的基本理 论；第三章介绍了分布式概念格模型和并行算法s e a ；第四章介绍了分类的基 本概念并给出了一个基于类特征的分类系统；第五章介绍了基于概念格的数据 挖掘系统：第六章为结束语。 1 0 第二章概念格模型的基础 概念格从w i l l e r 提出经过近2 0 年的发展，被应用在很多领域。本章首先 介绍格理论( l a t t i c e1 1 1 e o r y ) 和概念格( c o n c e p tl a t t i c e ) 的相关概念：接着介绍 当柯出现的几个概念格的模型和相关研究：最后介绍概念格构造算法的研究。 2 1 概念格数学模型 2 1 1 序论与格论中的基本定义代数格 格论形成于1 9 3 5 年左右，是代数学的一个重要分支，而且在近世解析几 何、半序空间等方面都有重要作用。本节从有序集【5 】玎始，介绍代数格的一些 基本概念。 定义2 1 设a 是一个集合，如果a 上的一个关系r ，对于v x ，y ，z e a ，满 足如下条件：x r x ( 自反性) x r y ，y r x j x = y ( 反对称性) x r 弘y r z j x r 2( 传递性) 则称r 是a 上的一个偏序关系，把它记作“( ，。序偶 称为偏序集。 定义2 2设 为偏序集且b a 为一个子集，如有a a ，对b 的任意 ，亡素x ，都满足x a ，则称a 为子集b 的上晃。同理，对b 的任意元素x ，都 满足a 虫，则称a 为子集b 的下界。 定义2 3设 为偏序集且b a 为一个子集，a 为b 上的任一上界， 若对于b 的所有上界y 均有a y ，则称a 为b 的最小上界( 上确界s u p e m l 嘲) ， 记作s u p ( b ) 。同样若b 为b 上的任一下界，若对于b 的所有下界z 均有z b ， 则称b 为b 的最大下界( 下确界i 丘m u m ) ，记作i 觚b ) 。 定义2 4设 为偏序集，如果a 中任意两个元素都有最小上界和虽 大下界，则称 为格。 定义2 s 设 是一个格，如果在a 上定义两个二元运算v 和八，使 得对于任意的4 b a ，a v b 等于a 和b 的最小上界，a 八b 等于a 和b 的最大下界， 那么，就称 为由格所诱导的代数系统。二元运算v 和八分别称为并 运算和交运算。 通常，我们用a v b 来代替s u p ( 曲) ) ，a 八b 来代替i 叫 如 ) 。类似的分别 用v b 和 b 来代替s u p ( b ) 和i n f 【b ) 。 定义2 6 设 是一个偏序集，如果对于任意非空的集合s a ，都存 在有v s ，则 被称为是一个完全并半格，类似地如果对于任意非空的集 合s a 都存在有八s ，则 被称为是一个完全交半格。如果 既是完 全并半格完全交半格，则它是一个完全格。 2 1 2 形式概念分析的理论基础概念格 形式概念分析通常由形式背景这一基本概念开始。形式背景被定义为三元 组 o 叫，d ，r ) ，其中u 是对象集d 是属性集，r 是u 和d 之间的二元关系，即 r u d ，o r d 表示“对象。具有特征d ，。在形式背景k 中，在u 的幂集和d 的幂集 之间可以定义两个映射f 和2 如f ： v o l u ：，( 0 1 ) = 埘i v x q ( 斌d ) 、 v d d ：g ( d 1 ) = z i v d d i ( x j r d ) 、 7 称为u 的幂集和d 的幂集之间的g a l o i s 联接。来自尸( 尸( d ) 的二元组 ( 0 l ，d 1 ) ，如果满足两个条件：0 l = g ( 日) 及d l = ，( d 1 ) ，则被称为是形式背景 k 的一个形式概念，其中0 l 和d 。分别被称为概念( q ，d 1 ) 的外延和内涵，若定义 c = ( 0 1 ，d 。) ，其外延和内涵也可分别用e x t e n t ( c ) 和i n t e n t ( c ) 来表示。k 的所 有形式概念的集合被标记为c s ( k ) 。 c s ( k ) 上最重要的结构是由子概念父概念关系( 又称为泛化例化 关系或前驱后继关系) 产生的，其定义如下：给定形式概念c 和c ：，如果 e x t e n t ( c 1 ) e x t e n c 2 ) ( 等价于i m e n t ( c 2 ) i m e m ( c 1 ) ) ，则c l 是c 2 的子概念，c 2 是 c 。的父概念，记为c l c ：，通过这个关系，我们得到偏序集c ，( 芷) = ( c s ( 置) ，) ， 因为对于c s ( k ) 任意非空子集s 中任意两个形式概念都有最小上界和最大下 界，所以偏序集c s ( 足) 是一个完全格，称为形式背景k 的概念格，记为l ( 1 ( ) 。 概念格中的每个节点都是一个形式概念。对于概念格中两个不同的节点 c l = ( q ，d 1 ) 和c ：；( 0 2 ，d ：) ，如累c 。是c ：的一个子概念且不存在其它的节点 c ，满足c l c ，c ，则称c ，为c ，的子节点或直接后继，而c ：为g 的父节点或 直接前趋。 概念格上的基本定理：设k = ( u ，d ，r ) 为一形式背景，l ( k ) = ( c s ( k ) ，) 是形 式背景k 的概念格，那么l ( k ) 为一完全格，对于c s 噼) 的任意非空子集，其最 小上界s u p ( l ( k ) ) 和最大下界嘲l ( k ) ) 分别为： s u p 犯( k ) ) = ( 。，g ( x ，) ) = ( g ( 厂( x ，) ) ，qg ( x ，) )( 2 2 ) i n 坟( k ) ) = 聂( x ，g ( x 。) ) = ( 9 鼍：y ( g ( 2 致置) ) ) )( 2 3 ) 概念格可以图形化表示为有标号的线图。生成图的方法如下：如果c 1 c 2 ， 且格中没有元素c 3 使得c i c 3 c 2 ，那么就存在一条从c 1 到c 2 的边。在线图 中，我们使用圆圈表示形式概念，使用线段表示子概念父概念关系。对于 一个对象，如果c 是包含改对象的最小概念，则对象的名称被附在c 所对应的 圆圈上。对于一个特征，如果c 是包含该特征的最大概念，则特征的名称被附 在c 所对应的圆圈上。概念格的有标号线图通常被用作通信模式，这使得给定 1 2 数据背景的概念结构变得清晰和易于理解，从而实现了格的可视化的显示。 2 2 概念格及其扩展模型的研究 在机器学习领域，我们对由两个集合之日j 的伽罗瓦连接定义的有限的伽罗 瓦格感兴趣，伽罗瓦格又称概念格，是允许建立对象集合内部类别的数学框架， 基于伽罗瓦格的系统的主要困难来自格的构造。伽罗瓦格的完备性在表达层次 结构时使得格的大小随数据量呈现指数增长。目前的研究主要集中在概念格的 构建和为了提高效率的规则求解算法研究，并产生了一些成果。 2 2 1 传统的概念格 传统( 只是时间的差别，非严格说法) 的概念格研究主要从w i l l e r 开始 的概念格结构讨论，主要讨论概念格的一些基本理论和性质。随后的主要工作 有：概念格的构造算法和概念格上的规则求解算法。 w i l l e r 在【2 1 】中主要研究了特定形式背景( 定义见上) ( u ，d ，r ) 上的概念之 间的关系以及这些概念构成的概念格的一些性质，为构造概念格做准备，为尽 可能具体地解释格论，增进格论研究者和潜在用户的交流 【2 1 】。 定义2 7 对形式背景( u ，d ，r ) ，u 和d 分别称为对象和属性，r 为u 和d 上的二元关系。如果对于任意x u 和d d 都存在x r d ，则称对象x 具有特征 d 。且定义映射： a 2 d ed 1 vx a ，x r d ( 2 4 ) b 2 x ul vd b ，x r d ( 2 - 5 ) 则称映射a _ + a7 和b _ b 在u 和d 幂集上形成伽罗瓦连接。 定义2 8 对形式背景( u ，d ，r ) 中的概念( a l ，b 1 ) 和( a 2 ，b 2 ) ，超概念和 子概念( a 1 b 1 ) ( a 2 b 2 ) a 1 c a 2( b b b 2 ) 。 定理2 1 令( u ，d ，r ) 为形式背景，那么一个完全格( l ( u ，d ，r ) ，) 被称为 ( u ，d