（通信与信息系统专业论文）基于概念格的关联规则挖掘研究.pdf

中文摘要 摘要 当今，社会已经进入了网络信息时代，计算机与网络信息技术的飞速发展使 得各个领域的数据和信息急剧增加( 信息爆炸) ，同时人类的参与使数据与信息 系统中的不确定性更加显著。如何有效地实现对数据的分析和处理，如何快速地 从数据中提取出隐含的知识，长期以来一直是人工智能领域的研究热点。在此背 景下诞生的知识发现k d d ( k n 0 w l e d g ed i s c o v e 叮蛔da _ t a b a s e s ) 和数据挖掘d m ( d a t a h n l l i n g ) 给人们提供了一种新的认识数据和理解数据的智能手段。 作为数据挖掘的重要研究模式，关联规则一直受到广泛的关注。而概念格以 其完备的结构和坚实的理论基础使其成为研究数据挖掘的主要工具之一。因此， 利用概念格研究关联规则是有意义的。 基于粗糙集和概念格，本文给出了一种挖掘关联规则的新算法。该算法首先 通过粗糙集的思想对形式背景进行了约简，然后通过预先给定的阚值，减少属性 的个数，从而减少了建格的复杂度和搜索概念的时间。利用概念格本身的信息， 计算出了所得到的关联规则的支持度和信任度。实验说明了该方法实现的具体步 骤及其有效性。 关键词：形式概念分析；概念格；关联规则；数据挖掘 英文摘要 t h es t u d yo f 舢s o c i a t i o nr u i em i n i n g b a s e do nc o n c e p tl a t t i c e a b s t r a c t n o w a d a l y s ，灶l es o c i e t yh 舔e n t e r e dt h ei l l f o 删i o ne r a ，t h ec o m p u t e ra n dn e r 0 i k j n f o 】m l a t i o nt e c h n o l o g yh a v eb e e nd e v e l o p e ds or a p i d l yt h a td a t a 孔di n j b 眦a t i o n 缸e k r e 弱崦妇l a t i c a l l y ( i i 面衄a t i o ne x p l o s i o n ) i 1 1a l lf i e l d s ，m e a n w l l i l e d a 乜a i l d m f o n n a t i o ns y s t e m sb e c o m em o 咒l m c e r t a i nd u et 0h m n a n sp a n i c i p a t i o n h o wt o e 撩c 6 v e l ya c l l i e v et h ed a t a 锄a ：【y s i s 弛dp r o c s i n g 觚dq u i c k l yg e t 吼p l i c i tk n o w l e d g e h 船l o n gb e e i la ni m p o r t a n td i r e c t i o no fa r t 讯c i a lh n e l l i g c n c e i i lt t l i sb a c k g r o u n d k n o w l e d g ed i s c o v e r yi nd 砌b 缴s 卿d ) a n dd a t am i n i n g 岣p r o v i d ean c w i i l t e l l i 毋m tw a yo f l l n d e r s 眦d b gd a ：t a t h e 硒s o c i a t i o nm l e sw i l i c ha r ea ni m p o r t a 】吡p a 壮e mi n 加m i n i l l gh a v ew i d e l y i n v e s t 追a t e d c o n c e p tl a n i c e 晰mc o m p l e t es t n l c t i l r e 锄d9 0 0 d 也e o r yh 勰b e e no 鹏o f 也e 嫩i nt o o l si nd m t h e r e 南r ei ti ss i 鲥f i c a n tt os t l 珂ya s s o c i a t i o nm i e sb yl l s i l l go f c o n c e p tl a t t i c e b 弱e do nr 0 u g hs e tn l e o r ) ，a n dc o n c e p tl a t t i c e ，an e wm e 也o di sp r o p o s e dt o s e a r c hf o r 舾s o c i a t i o n 兀1 l e s t h ef o 玎1 1 a lc o n t e x ti sf i r s tr e d u c e dv i ar o u g hs e tt 1 l e o r y a 丑dt h c ns o m eo f 也ca 仕舶u t e sa r et l l r o 、 1 1 1o f ff o r 也eg i v e i lt h r e s h o l d t h ec o m p l e x 毋 o fc o n s 圩u c t i i l gl 甜i c ea f l ds e a r c h i 】1 9f o rt h ed e s c o n c e p ti sd e c e a s e d t h es u p p o r t s a n dc o i d e n c e sf o rm eo b t a i n e d 鼬s o c i a t i o nm l e sa r cc o m p u t e d 砸t ht h e a i do fc o n c e p t l a t t i c e t h ee x p e r i i i l e n ts h o w sm cv a l i d i t y 卸dd e t a i ls t e p so f t h i sm e t h o d k e yw o r d s ：f o r m a lc o 耻e p ta 蚰l y s i s ；c o n c e p tl a t t i c e ；a 5 s o c i a t i o n 饨l e ； d a t am i n i g 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：基王拯垒揸的羞壁拯巫l 控塑婴窒：。除论文中已经注 明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确 方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或 未公开发表的成果。 轳釉擀艴蚌镰：参4 z 加7 论文作者签名：吃夏z加o 年，9 月矽臼 | 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 论文作者签名。妻_ 。：签三：上孓忉涉日期：年月日。 基于概念格的关联规则挖掘研究 第1 章绪论 随着信息技术的发展，指数级激增的数据量迫切地需要转化成有用的知识， 而且数据库和数据仓库技术的迅速发展，使得从潜在、隐性的数据中发现有用的 知识和模式成为可能。在这样的技术和经济背景下k d d ( 妣w l e d g e d i s c o v e r ym d 呲a b a s e s ，数据库中的知识发现) 和d m ( d a t am i i 血g ，数据挖掘) ，它们已经被广 泛地应用到科学研究、金融、保险、医疗保健、司法等各个行业。本章在介绍信 息技术及隐性知识的发展应用的基础上，主要讨论k d d ，d m 的内涵及相互的关系 以及d m 和统计学的关系，并关注d m 的发展及当前最新的研究热点。 1 1 引言 1 1 1 信息技术的发展 近年来，随着数据库理论研究的深入以及数据仓库技术的广泛应用，各类金 融企业、商业机构、教育产业等众多行业积累了大量的数据及丰富的信息资料。 这些资料涉及到企业管理、金融活动、商业运作等各类应用。从这些数据中抽取 出各种不同的，隐藏着的，并且可满足不同需求的规律和知识，为企业资源规划、 客户关系管理、企业风险防范、供应关系管理、金融投资等商业行为以及企业的 营销管理及竞争优势分析和决策支持提供了技术上的保障。 数据挖掘这一概念起源于知识发现( k n o w i e d g ed i s c o v c r yi nd a t a b a s e ，k d d ) 领域【l l ，它主要包括数据挖掘和w e b 挖掘两个主要研究分支。自从1 9 8 9 年在美国 底特律市召开的k d d 专题讨论会上正式提出知识发现这个概念以来，数据挖掘已 经被广泛地应用到科学研究、金融、保险、医疗保健、司法等各个行业【2 1 。一份最 近的g a n n e r 报告列举了五项在今后3 5 年内对工业将产生重要影响的关键技术， 其中k d d 和人工智能排名第一。这份报告将并行计算机体系结构和k d d 的研究， 列入今后5 年内公司应该投资的十个新技术领域。特别是近年来，数据仓库技术、 i n t e m e t 技术、移动智能体技术的快速发展，又提出了对于非结构化的，复杂信息 的获取和挖掘问题。 第l 章绪论 1 1 2 隐性知识的应用 根据知识能否清晰地表述和有效的转移，可以把知识分为显性知识( e x p l i c i t k n o w l e d g e ) 和隐性知识( t a c i tk n o w l e d g e ) 。 对于隐性知识的概念，不同的学科领域有不同的解释。澳大利距麦克夸利大 学( m a c q u 撕eu 1 1 i v e r s i t y ) 计算机系的两位学者d e b b i e c h a r d s ，与p e t c rb 1 1 s c h 侧重 于借助计算机技术来研究隐性知识。他们基于s t e m b e r g 等人的理论对隐性知识进 行测试，然后根据形式概念分析( f o m l a lc 0 n c 印ta n a l y s i s ) 方法对在隐性知识测试 中的差异进行建模和比较，把数据可视化，进而分析隐性知识。 形式概念分析的基础是形式概念格，它产生于1 9 8 2 年，是一个在德国的达姆 施塔特( d a m s t a d t ) 的研究小组，在试图让系统自动通过应用格论( 1 a n i c et h e o r y ) 来 生成一个结构框架时发现“3 1 。形式概念格可以用来分析数据，例如调查和处理明 确给定的信息。这个方法可以把数据按结构分成若干组( 块) ，每个组都是人脑可以 理解和解释的形式化的抽象概念，然后把这些具有内在结构的数据可视化。目前 这种分析和处理数据的方法己经广泛地应用于各个领域( 例如医学、心理学、信息 科学、土木工程学、生态学等) ，有广阔的发展前景。尤其对于社会科学家来说， 他们经常无法通过定性分析的方法获取数据，那么通过这种定量的方法就可以做 到：，这样就把统计与概念分析的方法结合起来。 虽然d e b b i e 尉c h a r d s 与p e t e rb u s c h 的研究是初步的，但他们为利用技术手段 来测试与表征隐性知识提供了一种方法，进而为挖掘、分析与利用隐性知识提供 了一条途径。 1 2k d d 和数据挖掘 商业自动化极大地促进了数据的增长，即使一件简单的事务，比如电话呼叫， 使用信用卡，医疗测试等等，都己电子化。这些存在的大量数据迫切需要转化成 有用的信息和知识。如何处理这些数据显然是一个新的问题【4 】。 对待这些浩如烟海的数据只能使用计算机来理解。然而，数据产生和数据理 解存在很大的不同【5 1 。获取的知识可以广泛用于各种应用，包括商务管理、生产控 基于概念格的关联规则挖掘研究 制、市场分析、工程设计和科学探索等。极富竞争力的前景给k d d 的发展创造了 条件。 “数据库中的知识发现”即k d d ，首次出现在1 9 8 9 年8 月举行的第1 1 届 国际联合入工智能学术会议上。1 9 8 9u c a jw o d 曲o p 会议上p i a t e t s 姆一s h a r p 沛正 式提出k d d ； 1 9 9 lp i a t e t s l ( ys h a r p 曲和w f r a w l e y 出版著作幻1 0 w l e d g ed i s c o v e r y i nd a d a b 嬲e ；随后在1 9 9 l ，1 9 9 3 ，1 9 9 4 年都举行了k d d 专题讨论会，集中讨论 数据统计、海量数据分析算法、知识表示、知识运用等问题。1 9 9 5 年，第一届k d d d m 国际学术会议于加拿大召开；1 9 9 6 年u f a y y d 第二本专著a d v a n c c sj n 鼬l o w l e d g e d i s c o v e r y 蛆d d a t a m 砒培出版；1 9 9 s - 1 9 9 8 年举办i ( d d 国际会议；1 9 9 7 年关于k d d 的杂志j o u m a lo fd m 锄dk d d 创刊；1 9 9 8 年a c m 的特殊兴趣组 s i g k d d 成立。此后s i g k d d 召开了众多的学术会议。第9 届国际知识发现与数 据挖掘会议( m en ma c ms i g k d dm 【e m 撕o n a lc o 础b r e n c e o nk n o w l e d g e d i s c o v e r ya n dd a _ c a m i l l i n g ( k d d 2 0 0 3 ) 于2 0 0 3 年在美国召开；第l o 届a c m s i g k d d 会议于2 0 0 4 年8 月在美国西雅图召开。迄今为止，由美国人工智能协会 主办的k d d 国际研讨会已经召开了l o 次。会议的规模由原来的专题讨论会发展 到国际学术大会，人数由二三十人到七八百人，研究重点也逐渐从发现方法转向 系统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透， 强调知识是数据驱动探索的最终产品。k d d 一词已经广泛地适用于a j 和机器学 习领域。 1 2 1k d d 的内涵 k d d 是从数据中发现有用的知识的总体过程，而数据挖掘指的是这一过程中 的一个特定步骤【h l 。数据挖掘( d a t a 蛐i n g ) 运用具体的算法从数据里提取模式。 k d d 过程和其中的数据挖掘步骤的区别是值得注意的。k d d 过程的其他步骤，如 数据准备、数据选择、数据清理以及对挖掘结果的合理解释，对于确保从数据中 获取了有用的知识起到了重要作用。盲目地应用数据挖掘法是很危险的，会导致 产生无意义和无效的模式。k d d 一直在不断的演化，涉及众多领域：机器学习，模 式识别，数据库，统计学，人工智能，专家系统等。在这些领域里k d d 的统一目 标是从存在于大型数据库里的低层次的数据中提取出高层次的知识旧。 第1 章绪论 k d d 旨在确定数据中有效、新颖、潜在的知识，并且最终发现可理解的模式。 这是一种非平凡过程“过程”一词也暗示了l ( 1 ) d 包含许多步骤：数据准备、寻 求模式、知识评估及精化等，而这些步骤可能是多次重复的。非平凡指的是一些 研究和参考，也就是说，k d d 不是像求解一系列数值的平均值那样对预定义的数 据的直接计算。发现的模式应该对于新的数据在一定的置信度下是有效的。同时 模式期望是新颖且有用的。即是说，可以给用户或任务带来益处。最后，至少经 过后期处理，模式应该可理解【6 】。 我们可以定义量化的度量来评估提取出的模式。在许多情况下定义置信度的 量化度量是可行的。然而，类似于新颖性、可理解性就不太容易定义量化的度量， 因为这些概念比置信度要主观的多。兴趣度是一个重要的概念，综合了有效性、 新颖性、有用性以及简洁性，通常被视为模式的总体度量。基于这些概念，如果 一个模式超过兴趣度阈值，则它是属于特定领域的且是纯面向用户，它是由用户 选择的功能和阈值决定的。但是，总体用户驱动这一概念并不是k d d 独有的，在 统计学和机器学习领域都有相似之处。 1 2 2k d d 的过程和任务 k d d 过程对数据运用数据分析和算法，这些算法在可接受的计算限制下，可 以生成特定模式。数据挖掘只是其中的一个步骤，k d d 运用数据挖掘的方法列举 得到的模式，并且评估数据挖掘的产品。事实上，k d d 的总体过程包括了对挖掘 出来的模式评估和的可能的解释，并据此决定哪一个模式可视为新知识。它交互、 可重复，且包括许多步骤。k d d 知识发现过程包括数据清理、数据集成、数据变 换、模式评估和知识表示。 k d d 基本步骤如下m ： 第一步是对应用领域和相关先验知识的理解以及从客户的角度确定k d d 过程 的目标。 第二步是创建目标数据集：选择一个数据集，或者从将要进行操作的变量或数 据样本中选一个子集。 第三步是数据清理和预处理。基本操作包括去除噪声，收集必要的信息来建 模解决噪声，决定如何处理丢失的数据域，并且说明时序信息和己知的变化。 基于概念格的关联规则挖掘研究 第四步是数据约简：基于任务目标找寻有用的特征来体现数据。 第五步是基于k d d 的目标选择特定的数据挖掘方法。比如分类、综合、回归、 聚类等等。 第六步是探查分析和模型及假设选择：选择数据挖掘算法和方法去搜寻数据模 式。这一过程包括决定哪一种模型和参数合适，并且基于k d d 整体标准配备一种 数据挖掘算法。 第七步是数据挖掘：搜寻有趣的模式，包括分类规则、树、回归和聚类等等。 通过正确地执行前面的步骤，用户能显著地辅助数据挖掘方法。 第八步是解释挖掘出的模式，有可能会回到1 到7 的任何步骤。 第九步是将挖掘出的知识直接应用于另一个系统，或者做出文档，提交给感 兴趣的部门。该过程也包括用之前己经确定的知识检查、解决潜在的冲突。 这只是一种步骤的划分方法，有些专家则倾向于合并某几步基于这种划分 方法，k d d 大部分前面的工作集中在第七步，即数据挖掘。然而，其他步骤对于 将k d d 成功用于实践同样重要。比如数据选择和数据预处理对于整个知识发现过 程有着很重要的作用，同时又是最费时的步骤。完全自动的系统不能达到最终的 目标，由于大多数的数据不是由数据仓库提供或者说仅仅零散地存放在数据库中， 作为日常的商业处理，如支出，入账等等，直接对这样的数据操作，会导致生成 适用性很低的模式或知识发现的失败。所以成功的知识发现过程是需要相关的领 域专家，数据专家和用户所关心的目标来辅助的。 1 2 ，3 数据挖掘的概念 数据挖掘是信息技术自然演化的结果。从6 0 年代最初的数据收集和创建到7 0 年代数据库管理系统d b m s ，进一步发展到高级数据库管理系统和基于w e b 的数 据库系统。在后来的发展中，当数据仓库成为商务运作的一个有价值的工具时， 使用的查询语言s q l 以及联机事务处理( o l t p ) 也有了进一步的发展。数据仓库是 从数据库演化来的一个相关领域，是一种数据的长期存储，这些数据来自多数据 源，是经过组织的，以便支持管理决策，而且在一种一致的模式下存放，通常是 汇总的。数据仓库是一个数据库，它与组织机构的操作系统分别维护，允许将各 种应用系统集成在一起，为统一的历史数据分析提供坚实的平台，对信息处理提 第1 章绪论 供支持构造数据仓库涉及数据清理和数据集成，可以看作数据挖掘的一个重要预 处理步骤。数据仓库提供联机分析处理( o l a p ) ，在o l 垤中使用扩展的s q l 语言， 成为数据分析和联机分析处理日趋重要的平台，并为数据挖掘提供有效的平台。 近年来，数据挖掘成为人们在研究工作中时常听到的术语。然而，也是比较 难以理解的。原因主要有两点：第一，从事数据挖掘研究的人员并不属于同一领域。 他们来自各个不同的相关领域，拥有不用的领域知识和实践经验，比如机器学习、 统计学、心理学等等，即使对于他们来说，也不能说完全了解该领域所涉及的知 识范围。第二，数据挖掘的某些主流思想和统计学不同，旱期有些对数据挖掘感 兴趣的公司团体中的统计学家对此产生对立情绪。统计大多基于假设检验，然后 使用统计工具去检验、证明或推翻该假定。在建立检验模型时，是需要考虑到统 计人员本身对于数据的理解是否正确，恰当。检验模型建立的好不好，是否能反 映问题，还与统计人员的经验有关。而数据挖掘本质上不需要做假设检验，这也 是和统计的一个主要区别。数据挖掘旨在从用户关心的数据中发现有趣的联系， 它不要求执行挖掘的必须是专家，而且还增大了发现用户之前未能想得到的新知 识，新联系，新模式。 数据挖掘的应用对象从结构化数据发展到半结构化及非结构化的复杂数据类 型，包括关系数据库、面向对象数据库、空间数据库、推理数据库、多媒体数据 库、时态数据、文本数据、w e b 臼志文件、图形图像数据及音频、视频数据等。 数据挖掘所涉及到的知识类型，根据应用特点可分为预测型、描述型、发现 型、验证型等类型知识；据知识的性质特点可分为关联规则、分类规则、聚类规则、 时序模式、相似模式、混沌模式、回归模式、趋势分析、偏差分析和模式分析等。 1 2 4 数据挖掘系统 尽管丰富和强大的数据挖掘功能形成了数据挖掘系统的核心，像大部分软件 系统一样，数据挖掘系统的结构和设计是至关重要的。一个好的系统结构将有利 于更好地利用软件环境，有利于有效、及时地完成数据挖掘任务，有利于与其他 信息系统协调和交换信息，有利于系统适应用户的各种要求，井随时间优化。 如今数据库和数据仓库己经成为主流信息系统，数据挖掘系统将由多个相对 独立的部分组成，能够通过o d b c o l ed b 连接实现多个异种数据库、数据仓库 基于概念格的关联规则挖掘研究 的访问、集成、统一和转换，并能提供基于w e b 的访问、服务、报表功能以及 o l a p 分析处理能力。在这种情况下，数据挖掘系统必须面对的一个重要问题是： 是否应当将数据挖掘p m ) 系统与数据库( d b ) 系统和数据仓库( d 、) 统集成或耦合 昵? 基于不同的结构设计，d m 系统与d b ，d w 系统的集成方式分为不耦合、松散 耦合、半紧密耦合和紧密耦合【1 3 】： 不藕合意味着d m 系统不利用d b 或d w 系统的任何功能。它可能由特定的 源( 如文件系统) 提取数据，使用某些数据挖掘算法处理数据，然后再将挖掘结果存 放到另一个文件中。 松散耦合即表示d m 系统将使用d b 或d w 系统的某些工具，从这些系统管 理的数据存储提取数据，进行数据挖掘，然后将挖掘结果存放到文件中，或是存 放到d b 或d w 指定的位置。 半紧密耦合即除了将d m 系统连到一个d b d w 系统之外，一些基本数据挖 掘原语( 通过分析频繁遇到的数耀挖掘功能确定) 可以在d b 仍w 系统中实现。这些 原语可能包括排序、索引、聚集、分析、多路连接和一些基本的统计度量的预计 算。 紧密耦合指d m 系统平滑地集成到d b d w 系统中。d m 子系统被视为信息系 统的一部分。d m 查询和功能根据d b 和d w 系统的挖掘查询分析、数据结构、索 引模式和查询处理方法优化 一般地，耦合程度越高越好，因为它提供一个一致的处理环境结构，有利于 数据挖掘功能的有效实现，有利于提高系统性能，有利于实现集成的信息处理环 境。 数据挖掘系统必须具备相关的构件：数据预处理构件、数据挖掘引擎、模式 评估构件、知识库构件。 数据预处理构件：主要是将不同形式的数据经过集成、转换为可以被数据挖掘 引擎所能识别和使用的数据，为挖掘准备数据。在这个阶段，除了完成多种数据 的集成外，还要进行数据的预处理工作，将噪声和异常数据尽力删除，并把所要 进行挖掘的数据表示成一种合适的数据形式，便于挖掘。 第l 章绪论 数据挖掘引擎：接受处理过的数据，根据挖掘任务的要求选用合适的挖掘算法， 从数据中提取有用的模式。这个阶段的主要任务是完成算法，模式的生成和对知 识库中先验知识的利用。同时为了提高效率，利用先验知识优化算法。 模型估价构件：模式的有效性、新颖性、有价值和可理解性是评价模式的标准。 如前所述，通常使用兴趣度概念来刻画，兴趣度在挖掘过程中可以是用户和挖掘 引擎的交互接口，用户通过它控制挖掘集中到有趣的模式上。有时直接将该构件 集成在挖掘引擎中，提高挖掘的效率。 知识库构件：知识库是经过专家和用户的检验和认可的模式。可以在新的挖掘 任务中使用和进化。 该系统的核心在于数据挖掘引擎和模式评估模块的设计，用户通过各个模块 的接口控制或者是约束模块的行为来达到挖掘的效率和精度要求。 数据挖掘系统的输入包括：任务相关的数据；要挖掘什么类型的知识；背景知识； 兴趣度度量；发现模式的表示和可视化。数据挖掘可以发现的模式有： 概念类描述：用汇总、简洁的、精确的方式描述每个类和概念，这种描述称 为概念类描述： 关联分析：发现关联规则，这些规则展示属性一值频繁地在给定数据集中一 起出现的条件； 孤立点分析：数据库中可能包含一些数据对象，它们与数据的般行为或模 型不一致。这些数据对象是孤立点，大部分数据挖掘方法将孤立点视为噪声或异 常而丢弃。然而，在某些应用中，罕见的事件可能比正常出现的更有趣。孤立点 数据分析称作孤立点挖掘； 演变分析：描述行为随时间变化的对象的规律或趋势，并对其建模。还有聚 类分析和分类和预测分析等等。 数据挖掘涉及从观察的数据中建立模型或确定模式。所建立的模型作为推论 知识起了十分重要的作用：这些模型是否反应有用的或有趣的知识是k d d 过程关 注的一部分。该过程是全面，交互的，而且需要人的主观判断的参与。 基于概念格的关联规则挖掘研究 1 3 数据挖掘的发展 1 3 1 数据挖掘的动态 数据库知识发现( k d d ) 在1 9 8 9 年召开的第l l 届国际人工智能联合学术会议 ( u c a i ) 上首次提出的。在这届学术会议上举行了以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 幽ga n d 勋1 0 w l e d g ed i s c o v e r y 也于9 7 年3 月创刊发行。 亚太地区于1 9 9 7 年在新加坡召开了首次k d d 研讨会( p 越d ) ，其后又在澳大利 甄的墨尔本召开了第二届，在中国北京召开了第三届。目前，在u c a j ，a a a i ，v l d b ， a c m s i g m o d 等代表人工智能与数据库技术研究最高水平的国际学术会议上，知 识发现的研究都占有较大的比例，知识发现的研究已经成为当今计算机科学与技 术研究、应用的熟点领域之一。 世界上大多数先进国家的大学、实验室和众多企业都在积极从事数据挖掘的 研究，他们从各个角度深入数据挖掘分析，原理及算法设计，并且在过去的1 0 年 中取得了卓越的成绩，主要在以下的几个方面： 多维数据分析：数据仓库和0 l a p ： 关联分析、相关分析和因果分析； 分类研究：可量测性和其它新途径； 聚类和孤立点分析： 相似度分析：曲线，趋势，图像，文本等； 序列模式和时间序列分析； 文本挖掘，w e b 挖掘和w e b 日志分析： 空间、多媒体及科学数据分析： 数据预处理和数据库压缩： 数据可视化和可视化数据挖掘： 第1 章绪论 1 3 2 数据挖掘的研究焦点 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、 机器学习、可视化和信息科学。此外，依赖于所用的数据挖掘方法、以及可以使 用的其他学科的技术，入神经网络、粗糙集理论、知识表示、归纳逻辑程序设计 或高性能计算。依赖于所挖掘的书籍性或给定的数据应用，数据挖掘系统也可能 集成空间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、 经济、商业或心理学领域的技术。 目前国内外信息挖掘的研究主要是以知识发现的任务描述、知识评价与知识 呈现为主线，以基于各种理论的有效知识发现算法研究为中心，以及更加广泛的 应用研究为主要特点。具体体现在结构化数据和非结构化的复杂数据类型的挖掘 技术和应用的研究上，以及相应软件产品和应用系统的开发中。信息挖掘机理和 一般性框架的理论研究日益受到重视。 结构化数据挖掘技术的研究：结构化数据挖掘技术的研究较为成熟，目前的工 作主要集中在算法的适应性、扩展性和鲁棒性的研究上。围绕统计学方法的数据 挖掘算法的研究一直受到关注，s a s ，s p s s 等软件厂商均在其统计软件系统中增加 数据挖掘的功能。他们通过b a y e s 理论的拓展，用于在具有先验知识的情况下的 不确定知识发现。实际上，统计理论的基本概念，如概率、独立性和因果性等也 是数据挖掘算法的基础。 关联规则知识发现算法，主要适应于布尔型关联规则的挖掘。该算法是为数 众多的应用研究的基础，目前主要的研究工作集中在算法的改造以及可扩展性和 普适性的研究上。 序列模式( s e q u e 蚯a ip a t c 唧) 是r a g r a w a l 【5 】提出的另一重要的数据挖掘方法。 目前国际学术界关于序列模式的研究限于单一的概念层次，尚未研究多概念层次 的序列模式。不过，在不同的概念层次发现序列模式是十分有价值的。 神经网络是目前常用的数据挖掘技术，广泛应用于分类、聚类、预测建模和 混沌模式的知识发现，其中自组织神经网络和细胞神经网络在空间数据的可视化 方面的应用较为广泛。 基于概念格的关联规则挖掘研究 基于概念格( c o n c e p tl a t t i c e ) 理论的知识发现的理论研究和应用近年来受到重 视。目前，概念格知识发现的研究主要集中在：用概念格改进k d d 过程，快速建 立格算法、格的修正与扩展技术的研究等。撅念格还被证明是分析复杂数据的有 效工具【7 - 2 们。 非结构化复杂类型数据挖掘技术的研究：复杂类型数据的知识发现是目前国内 外知识发现领域的研究热点。非结构化复杂类型数据的数据挖掘和知识发现包括： 复杂数据对象的高维分析；空间数据挖掘；多媒体数据库的数据挖掘；时间序列挖掘： 文本数据挖掘以及w e b 挖掘等。 空间数据是指同占有一定空间的对象的相关联的数据。空间对象由空间数据 类型及其空间关系所定义。空间数据库中存储的海量数据包括对象的空间拓扑特 征、非空间属性特征以及对象在时间上的状态变化。空间数据挖掘方法主要包括 空间分类和空间趋势分析。 文本挖掘( t e x tm i l l i i l g ) 是信息挖掘的一个研究分支，用于基于文本信息的知识 发现。文本挖掘是利用智能算法，如神经网络、基于案例的推理、可能性推理等， 并结合文字处理技术，分析大量的非结构化文本源( 如文档、电子表格、客户电子 邮件、问题查询、网页等) ，抽取或标记关键字概念，文字间的关系，并按照内容 对文档进行分类，获取有用的知识和信息。文本挖掘的早期研究是信息检索，包 括了基于关键字检索和全文检索。数据挖掘是揭示存储在数据库中的结构化数据 的数值属性之间的关系，而文本挖掘则是分析和发现大量非结构化文本中的关系。 文本挖掘研究的关键在于文本内容的量化表征。 知识发现框架的理论研究：目前，信息挖掘的研究大多局限于知识发现方法和 实现技术细节的研究上，缺乏知识发现的机理研究。对知识发现系统潜规律和内 在机理，以及k d d 的挖掘过程、总体结构与运行机制很少进行研究。过多的实现 技术研究无助于克服现有知识发现方法在扩展性、适应性和挖掘效率等方面的局 限性。我们应当从人类的认知过程，从知识本身开始研究以寻求有效的解决办法。 在研究和构造知识发现系统时应当充分应用领域所提供的知识以提高知识发现的 效率，同时考虑所发现的知识同己有知识之间的融合，从而可建立更加完善的实 用系统。 第l 章绪论 1 4 本文的主要研究内容和组织 基于粗糙集的中等价类的思想和概念格，我们首先定义了属性和概念的支持 度，然后给出了一种挖掘关联规则的新方法。为了得到有效的关联规则，对于给 定的阈值，该方法首先对形式背景进行约化和对属性进行了过滤，减少了属性的 个数，从而减少了建格的复杂度和搜索概念的时间。同时，利用概念格的信息， 我们还计算出了关联规则的支持度和信任度。实验说明我们方法实现的具体步骤 及其有效性。 本文组织如下： 第1 章介绍了数据挖掘的产生及其发展过程。 第2 章阐述了形式概念分析的一些基本理论，构造方法和它的一些应用。 第3 章叙述了数据挖掘中关联规则的经典算法。 第4 章给出了基于概念格的关联规则的挖掘算法和实验结果。 最后是本文的结论。 基于概念格的关联规则挖掘研究 第2 章形式概念分析及其应用 形式概念分析是由德国的数学家w i l l e 教授于2 0 世纪8 0 年代初提出的，它 反映了概念的哲学理解，其核心数据结构概念格，也称g a l o i s 格，准确而简洁地 描述了概念之间的层次关系，因此成为一种重要的知识表示方法。随着研究的深 入，形式概念分析越来越多地被应用到数据挖掘、信息检索、软件工程等领域， 成为处理和组织大规模数据的有效工具。本章主要介绍概念格的一些基本概念和 相关的研究内容，并介绍了形式概念分析的应用现状。 2 1 形式概念分析的理论基础 在哲学中，概念被理解为由外延和内涵两个部分所组成的思想单元。基于概 念的这一哲学理解，德国的w i l l e 教授吼提出了形式概念分析，用于概念的发现、 排序和显示。在形式概念分析中，概念的外延被理解为属于这个概念的所有对象 的集合，而内涵则被认为是所有这些对象所共有的特征或属性集，这实现了对概 念的哲学理解的形式化。所有的概念连同它们之间的泛化例化关系构成一个概念 格。概念格结构模型是形式概念分析理论中的核心数据结构，它本质上描述了对 象和特征之间的联系，表明了概念之间的泛化与例化关系，其相应的h 勰图则 实现了对数据的可视化。 2 1 1 基本概念 这里首先介绍形式概念分析中的一些基本概念，更详尽的描述可参考文献2 “。 定义2 1 形式背景定义为一个三元组k = ( g ，m ，d ，其中，g 是对象集合，m 是属性集合，i g m 是g 与m 之间的一个二元关系。若( g ，m ) i ，读作“对 象g 具有属性m 。 形式背景通常用交叉表来表示。在交叉表中一行代表一个对象，一列代表一 个属性，第g 行和第m 列的交叉点有一个“”，当且仅当( g ，m ) i 。表2 1 是 一个例子形式背景的交叉表。 第2 章形式概念分析及其应用 表2 1 形式背景 t a b2 1f b 姗a lc o n t e ) ( t 膳 ，口占cde ，g i ll010ld】d 2l0l0o181 g3100100i8l 4 01l08i010 5dlo010l00 定义2 2 对对象集合的每个子集a g ，定义导出算子f ( a ) 求出集合a 中所有 对象的共有属性： f ( a ) 2 m m iv g a ，( g ，m ) i 对称地，对属性集合的每个子集b m ，定义导出算子h ( b ) 求出具有集合b 中所 有属性的对象的集合： h ( b ) 2 geg fvm b ，( g ，m ) i 。 通常，为书写方便，这两个导出算子不加区分地写为a ，和b 。如果a 是个对 象子集，那么a 是一个属性子集，对它可以再应用第二个导出算子得到一个对象 子集a ”( 即：h ( a ) ) ) 。对称地，对属性子集b ，可以得到一个属性子集b ” ( 即：f ( h ( b ) ) ) a 命题2 1 对子集a ，a l ，a 2 量g ，有 1 a l a 2 ：a 2 a 1 ； 2 a a ”； 3 a = a ： 对称地，对子集b ，b l ，b 2 m ，有 i b l b 2 jb 2 量b 1 ： 2 b b ”； 基于概念格的关联规则挖掘研究 3 b = b ： 注意到，这两个导出算子组成集合g 的幂集和集合m 幂集之间的一个g a l o i s 连接。 定义2 3 形式背景k = ( g ，m ，i ) 上的一个形式概念( 简称概念) 定义为一个二 元组( a ，b ) 。满足： a g ，b 量m ，a = b ，b = a 其中，a 称为概念( a ，b ) 的外延，b 称为概念( a ，b ) 的内涵。 一个形式背景可能有许多概念。事实上，形式概念的数目是形式背景大小的指数【3 l 。 形式背景k ；( g ，m ，d 上的所有概念的集合记为b ( k ) 。 定义2 4 设( a b ) 和( c ，d ) 是形式背景k = ( g ，m ，i ) 上的任何两个概念，称( a ，b ) 是( c ，d ) 的超概念( 等价地t ( c ，d ) 为( a ，b ) 的予概念) ，当且仅当b d ( 等价地， c a ) ，记为( c ，d ) s ( a ，b ) 。即： ( c ，d ) s ( a ，b ) 营b d ( 营c 量a ) 通过这种序关系，得到一个有序集b = ( b ( k ) ， b 在事务集d 中成立，具有支持度s ，其中s 是d 中事务包含a u b 的百 分比。它是概率，“u b ) 。规则怜b 在事务集d 中具有置信度c ，如果d 中包 含a 的事务同时也包含b 的百分比是c 。这是条件概率p ( b i a ) 。即是 s - 豇l p p o r t ( a b ) = p ( 4 u 印；( 3 1 ) c 弋o n f i 曲e ( a ： b ) - p ( b l a ) ；( 3 2 ) 同时满足最小支持度阈值( 啦u p ) 和最小置信度阈值( m l - c o n f ) 的规则称为 强规则。为了挖掘有效的关联规则，必须由用户设定最小支持度和最小可信度。 关联规则的挖掘问题是：给定一个事务数据库d ，求出所有支持度不低于用户指 定的最小支持度和最小可信度的关联规则。 关联规则的挖掘问题就是求解所有的强规则，既要求解满足： 第3 章经典关联规则算法 s u p p o r t ( a - b ) n l i i l u p p o n 且c o l l fi d 髓c e ( a = b ) m i n - c o 越d e n c e 的规则 a = - b 。 关联规则的形式如下：“在购买面包和黄油的顾客中，有9 0 的人同时也买 了牛奶”( 面包十黄油一牛奶) 。用于关联规则挖掘的主要对象是事务型数据库 ( t 阳n s a c t i o nd a t a b a s e s ) ，其中针对的应用则是销售货物数据，也称购货篮数据分析。 关联规则可以分为两种：布尔型关联规则和多值属性关联规则，布尔型关联规则 可以看作是多值属性关联规则的基础和特例，所以本文仅对布尔型关联规则进行 研究，不过该方法同样适用于多值属性关联规则。支持度和置信度是描述关联规 则的两个重要概念，前者用于衡量关联规则在整个数据库中统计的重要性，后者 用于衡量关联规则的可信程度。一般来说，只有支持度和置信度均较高的关联规 则才可能是用户感兴趣、有用的关联规则。 2 、期望可信度( e x p e c t e dc o n f i d e n c e ) 期望可信度描