（计算机软件与理论专业论文）抽样技术在数据挖掘中的应用研究.pdf

抽样技术在数据挖掘中的应用研究 摘要 数据库规模的急剧膨胀使利用已有数据挖掘算法处理大规模数据集的时空 代价较大，而抽样技术是一种解决大规模数据挖掘的重要手段，适当的抽样技 术可以保证挖掘结果准确性并且降低算法的时空代价。本文主要对数据挖掘中 的抽样技术进行研究。 本文主要工i 乍如下： f 1 ) 将最优统计样本数的桫。念引入抽样过程，以克服已有抽样挖掘算法主 观因素过重的缺陷。以最优统计样本数为样本容量的抽样挖掘算法不仅能反映 故据本身的分却特点，而且能在保证挖掘结果准确性的同时降低抽样的样本容 量。 f 2 ) 提出一种面向分类规则提取的分层抽样算法。该算法以在保证重要分 类规则不丢失的前提下降低样本容量为目的，采用最优统计样本数确定样本容 量并且利用分层抽样提高分类算法在不均匀数据集上分类的准确率。 f 3 ) 提出一种加权挖掘频繁项集的抽样算法。该算法以在大规模数据集中 挖掘大频繁项集为目的，同时兼顾了样本的质量和容量两个方面的因素，能够 在保持频繁项集基本不丢失的基础上降低处理的数据规模。 ( 4 ) 提出一种新的基于随机抽样的网格聚类算法。该算法继承了网格聚类 算法对大规模和高维数据聚类良好的伸缩性，并利用随机抽样确定网格划分粒 度的方法进一步提高基于网格聚类方法聚类的精确度。 实验结果验证了上述算法的有效性。 关键词：数据挖掘，抽样，最优统计样本数，分层抽样，加权抽样，网格聚类 t h er e s e a r c ho i ls a m p l i n gf o rd a t am i n i n g a b s t r a c t w i t ht h er a p i d l yg r o w t ho fd a t a b a s es c a l e ，h i g hc o m p u t a t i o n a l ( t i m ea n ds p a c e ) c o s t sa r er e q u i r e dw h e nd i r e c t l ya p p l y i n gk n o w nm i n i n ga l g o r i t h m st ol a r g es c a l e d a t a b a s e s w h i l es a m p l i n gi so n eo ft h em o s ti m p o r t a n tm e t h o d si nm i n i n g k n o w l e d g ef r o ml a r g es c a l ed a t a b a s e sa n dp r o p e rs a m p l i n gc a l lg u a r a n t e et h e a c c u r a c yo fr e s u l ta n dr e d u c et h ec o m p u t a t i o n a lc o s t so fa l g o r i t h m s t h es a m p l i n g m e t h o d so nd a t am i n i n ga r es t u d i e di nt h ed i s s e r t a t i o n l em a j o rw o r ko ft h ed i s s e r t a t i o na r ea sf o l l o w s ： ( i ) i no r d e rt oo v e r c o m et h ep r o b l e mt h a tk n o w ns a m p l i n gm i n i n gm e t h o d s h e a v i l yr e l y0 nt h es h b j e c t i v ef a c t o r s ，t h es t a t i s t i c a lo p t i m a ls a m p l es i z ei sd r a w n i n t os a m p l i n g t h es a m p l i n gm i n i n ga l g o r i t h m sw h o s es a m p l es i z ei sd e t e r m i n e d a c c o r d i n gt ot h es t a t i s t i c a lo p t i m a ls a m p l es i z ec a nn o to n l ys h o wt h ep e c u l i a r i t yo f d a t ad i s l r i b u t i o nb u ta l s og u a r a n t e et h ea c c u r a c yo fr e s u l ta n ds h r i n kt h es a m p l e s i z ea tt h es a m et i m e ( 2 ) as t r a t i f ys a m p l i n ga l g o r i t h mf o re x t r a c t i n gc l a s s i f i c a t i o nr u l e si sp r o p o s e d i nt h ed i s s e r t a t i o n t h eg o a lo ft h ea l g o r i t h mi st om a i n t a i nt h ec h i e fc l a s s i f i c a t i o n r u l e sa n dt os h r i n kt h es a m p l es i z ea tt h es a m et i m e li nt h ea l g o r i t h m ，t h es t a t i s t i c a l o p t i m a ls a m p l es i z ei su s e dt od e t e r m i n et h es a m p l es i z e ，a n ds t r a t i f ys a m p l i n gi s u s e dt o r a i s et h ec l a s s i f i c a t i o n a c c u r a c y o fc l a s s i f i c a t i o n a l g o r i t h m s o n i n h o m o g e n e o u sd i s t r i b u t i o nd a t a ( 3 ) aw e i g h t e ds a m p l i n gm e t h o df o rm i n i n gf r e q u e n ti t e m s e t si sp r o p o s e di n t h ed i s s e r t a t i o n - t h ea l g o r i t h ma i m st om i n et h el o n gf r e q u e n ti t e m s e t sf r o ml a r g e s c a l ed a t aa n dg i v e sa t t e n t i o n st ob o t hs a m p l eq u a l i t ya n ds a m p l es i z e s oi t c a n b a s i c a l l yh o l dt h ef r e q u e n ti t e m s e t sa n dr e d u c et h ed a t as c a l es i m u l t a n e o u s l v ( 4 ) an e wg r i dc l u s t e r i n gm e t h o db a s e do nt h er a n d o ms a m p l i n gi sp r o p o s e di n t h ed i s s e r t a t i o n - i ti n h e r i t st h em e r i tt h a t c l u s t e r i n gm e t h o d sb a s e do ng r i dh a v ea g o o df l e x i b i l i t yt od a t aw i t h l a r g e s c a l ea n dh y p e r s p a c e ，a n di m p r o v e st h e c l u s t e r i n ga c c u r a c yu s i n gr a n d o ms a m p l i n gt od e t e r m i n et h ep a r t i t i o ng r a n u l a r i t yo f g r i d t h ee x p e r i m e n t sv e r i f yt h ev a l i d i t yo ft h e s ea l g o r i t h m s k e y w o r d s ：d a t am i n i n g ，s a m p l i n g ，s t a t i s t i c a l o p t i m a ls a m p l es i z e ( s o s s ) ， s t r a t i f ys a m p l i n g ，w e i g h t e ds a m p l i n g ，g r i dc l u s t e r i n g 图表目录 图1 1k d d 的处理过程模型 图3 1 抽样样本容量和结果准确性的关系 图4 1m u s h r o o m 数据库测试集的学习曲线 图6 1 空间距离在各个坐标轴的投影距离 图6 2 数据集d t 的投影 图6 3 数据集d 2 的投影 图6 4 数据集d 3 的投影一一 表4 1 分类实验结果比较 表5l 事务数据库d 表5 2 事务数据库d 的频繁项集 表5 3 运用加权挖掘频繁项集的实验结果 表6 1 聚类实验结果 ：坶钉钳甜“”弛们 独创性声明 本人声明所是交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒目王些厶堂 或其他教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学何论文作者签名 寸姻姥 签字日期：知e 年3 月多日 学位论文版权使用授权书 本学位论文作者完全了解垒8 b 王些态堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒日b 兰些盔堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适h j 本授权l5 ) 一虢寸筠谤聊虢穹嘶 签字日蝴：知6 年3 月；。日签字目期：口年j 月；。日 电话： 邮编： 7 ，无 嘲 曲w a 幼名曝 鞴 睹幸 致谢 三年的研究生生活即将划上句号，在这三年的学习和生活中，老师、同学、 亲人、朋友们给予我的关心和帮助将永远留在我美好的记忆深处。 首先，我要感谢我的导师胡学钢教授。胡老师治学态度严谨、工作作风踏 实、学术思维开阔、知识渊博，见解新颖独到。我在硕士期间所取得的成绩， 离不开胡老师的悉心指导和鼓励。胡老师在这三年中以他在数据挖掘领域深厚 的理论基础和对研究方向良好的把握，指引我从事科学研究，使我在研究中少 走了很多弯路。此外，胡老师性格上乐观豁达，在做人与做事等方面为我们树 立了学习的榜样，他经常指导我们要热爱生活、热心工作，并身体力行，这种 耳濡同染的熏陶对于我们的一生都将是一笔宝贵的财富。 我要感谢胡春玲、马冯、陈慧、王听娅、张冬艳、徐勇、张亮、胡谢斐， 与他们在一起学习生活的点点滴滴都是愉快而难忘的。感谢0 4 级与0 5 级的师 弟师妹们，通过和他们的交流拓宽了我的思路。此外我还要感谢计算机学院的 王新生和徐静老师的辛苦劳动。 最后，我要感谢我的家人，感谢他们这么多年来他们一如既往的关心，不 仅从物质上给予支持，更从精神上给予无尽的关爱，鼓舞我不断前进，为我创 造了一个轻松的生活和学习环境。 作者：于海涛 2 0 0 6 年5 月 第一章数据库知识发现 随着计算机科学与技术的飞速发展，计算机的处理能力和存储能力都得到 了不断提高，各种类型的数据库也得到广泛使用。由于计算机技术和信息技术 地进一步融合，在全球范围内掀起了信息化的浪潮，信息产生的渠道越来越多， 信息更新的频率日益加快，各行各业产生了数以亿计的数据库，数据库中存储 的数堀量急剧增大 然而从如此大舌的信息中，获取我们有用的知识却变得越来越困难了，这 就足破j o h nn a i s b e r t 称之为“信息丰富而知识贫乏”的窘境，因此，有效的利 用利处理大量的数据成为当前世界范围内所共同关心的问题。 数据库知识发现( 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 ) 1 ，2 ，3 技术就是为满足这种需求而产生和发展起来的。一般将k d d 中进行知识发现的阶 段称为数据挖掘( d a t am i n i n g ，d m ) 4 。某些应用领域对数据挖掘与k d d 不加 区分地使用，而在某种意义上二者可看作同一个概念。 k d d 一词是在1 9 8 9 年于美国底特律市召开的第届国际人工智能联合会议 上首次提出的，这届学术会议上举行了以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 a m i n i n ga n dk n o w l e d g e d i s c o v e r y ) ) 也于1 9 9 7 年3 月创刊发行。亚太地区于1 9 9 7 年在新加坡召开了首次k d d 国际学术研讨会。 目前，在i j c a i ，a a a i ，v l d b ，a c m s i g m o d 等代表人工智能与数据库 技术研究最高水平的国际学术会议上，对k d d 的研究都占有较大的比例，k d d 己经成为当今计算机科学与技术研究、应用的热点领域之一。随着k d d 在国际 j ：的兴起，我国也积极地开展了相应的研究和应用。目前国内许多学术会议， 如数掂库学术会议、机器学习会议等，也都将k d d 列为重要的研究方向。 1 2 数据库知识发现 1 2 1k d d 的定义和处理过程 数据库知识发现的定义几经变化，其中比较公认比较完整、深刻和全面的 个定义是由德国j f a y y a d z 等- 在1 9 9 6 年发表在会议论文 f r o m d a t a m i n i n g t o k n o w l e d g ed i s c o v e r y ) ) 一文【5 中将k d d 定义为： ”t h en o n t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ，n o v e lp o t e n t i a l l yu s e f u l ，a n d u l t i m a t e l yu n d e r s t a n d a b l ep a t t e r n si nd a t a ” n j k d d 是从大量数据中提取出有效的、新颖的、有潜在作用的、可信的、 并能最终被人理解的模式的非平凡的处理过程。 从该定义可以看出k d d 是一个高级的处理过程 6 ，它从数据集中识别出 以模式来表示的知识。k d d 的过程是一个多步骤的处理过程，如图1 1 所示，多 步骤之间相互影响，反复调整，形成一种螺旋式上升过程，主要包括以下一些 处理步骤： | + 一数据准备+ i 一数据挖掘叶卜绍果表达和解释叫 数据游 图1 1k d d 的处理过程模型 ( 1 ) 数据准备 k d d 的处理对象是大量的数据，这些数据一般存储在数据库系统中，是长 期积累的结果，往往不适合直接在这些数据上面进行知识挖掘，需要做数据准 备工作，一般包括数据的选择( 选择相关的数据) 、净化( 消除噪音、冗余数据) 、 推测( 推算缺失数据) 、转换( 离散值数据与连续值数据之间的相互转换，数据值 的分组分类，数据项之间的计算组合等) 、数据缩减( 减少数据量) 。如果k d d 的 对象是数据仓库，那么这些工作往往在生成数据仓库时已经准备妥当。数据准 备是k d d 的第一个步骤，也是比较重要的一个步骤。数据准备是否做好，将影响 到数据挖掘的效率和准确度以及最终模式的有效性。 ( 2 ) 数据挖掘 数据挖掘是k d d 中最关键的步骤，也是技术难点所在。研究k d d 的人员大部 分都在研究数据挖掘技术，采用较多的技术有分类、聚类、关联、时序等。数 据挖掘根据k d d 的目标，选取相应算法的参数，分析数据，得到可能形成知识的 模式模型。 ( 3 ) 评估、解释模式模型 上面得到的模式模型，有可能是没有实际意义或没有实用价值的，也有可 能是不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因此 需要评估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验， 有些模式也可以直接用数据来检验其准确性。这个步骤还包括把模式以易于理 解的方式呈现给用户。 ( 4 ) 巩固知识 用户理解的、并被认为是符合实际和有价值的模式模型形成了知识，还要 注意对知识做一致性检查，解决与以前得到的知识互相冲突、矛盾的地方，使 知识得到巩固。 ( 5 ) 运用知以 发现知识是为i + 运用，如何化知识能被运用也是k d d 的步骤之一运用知识 有两种方法，一种是只需看知识本身所描述的关系或结果，就可以对决策提供 支持；另一种是要求对新的数据运用知识，由此固能产生新的问题，需要对知 识做进一步的优化。 j 2 2k i l l ) 的特性 k d d 就是利用机器学习的方法从d b 中提取有价值知识的过程 7 】，是数据 库技术和机器学习两个学科的交叉学科。数据库技术侧重于对数据存储处理的 高效率方法的研究，而机器学习则侧重于设计新的方法从数据中提取知识。 k d d 币r j 用数据库技术对数据进行前端处理，而利用机器学习方法则从处理后的 数掘中提取有用的知识。k d d 与其他学科也有很强的联系，如统计学、数学、 人工智能和可视化技术等等。 k d d 有如下几个特性： ( i ) k d d 是从现实世界中存在的一些具体数据中提取知识。这些数据在 k d d 出现之前早已存在，对现实世界很有意义。 ( 2 ) k d d 使用的数据来源于d b 处理的数据量可能很大。因此，k d d 中学 习算法的效率和可扩充性就显得尤为重要。 ( 3 ) k d d 所处理的数据来自现实世界，数据的完整性、一致性和正确性都 很难保证，因此如何将这些数据加工成学习算法可以接收的数据也需要进行深 入的研究。 ( 4 ) k d d 利用目前数据库技术所取得的研究成果来加快学习过程，提高学 习效率。 ( 5 ) k d d 处理的数据来自于实际的数据库，而与这些数据库数据有关的还 有其他一些背景知识，这些背景知识的合理运用也会提高学习算法的效率。 1 3 数据挖掘 1 3 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程。与数掘挖掘相近的同义词有数据融合、数据分析和 决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪 声的；发观的是用户感岁：趣的知识；发现的知识是要可接受、可理解、可运用 的；并j 、要求发现放之四海皆准的知识，仅要求其支持特定的发现问题。 1 3 2 数据挖掘的对象 数据挖掘技术从兴起到发展的十几年问，主要面对的挖掘对象是以结构化 数据为主的关系数据库和数据仓库。但随着数据库技术和i n t e r n e t 技术的迅速 发展。大量的复杂类型的数据不断涌现，恰恰正是在这些数据里隐含了更具价 值的知识和信息。因此数据挖掘对象的进一步发展就是针对复杂类型数据的挖 掘。复杂类型数据的挖掘主要包括：空间数据挖掘，多媒体数据挖掘，时序数 掘挖掘，文本数据挖掘，w e b 数据挖掘，流数据挖掘。 ( 1 ) 空间数据挖掘 空间数据挖掘( s p a t i a ld a t a m i n i n g ) ，是指对空间数据库中非显式存在的知 识空间关系或其它有意义的模式等的提取。 ( 2 ) 多媒体数据挖掘 多媒体数据挖掘( m u t i m e d i ad a t a m i n f n ，主要是指对多媒体数据库中多媒 体数据的相似性搜索，多维分析，分类和预测分析，以及多媒体数据的关联挖 掘。 ( 3 ) 时序数据挖掘 时序数据挖掘( t i m e s e r i e sd a t a m i n i n g ) ，主要指对时序数据库中时序数据 的趋势分析，相似性搜索，与时间有关数据的序列模式挖掘和周期模式挖掘。 ( 4 ) 文本数据挖掘 文本数据挖掘( t e x td a t a m i n i n g ) ，当数据挖掘的对象完全由文本这种数据 类型组成时，这个挖掘过程就称为文本数据挖掘。 ( 5 ) w e b 数据挖掘 w e b 数据挖掘( w e bm i n i n g ) 。是将数据挖掘技术应用于w e b ，以实现对w e b 存取模式、w e b 结构和规财以及动态的w e b 内容的查找。一般将w e b 挖掘分为 三类：w e b 内容挖掘( w e bc o n t e n tm i n i n g ) ，w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) 。 和w e b 使用记录的挖掘( w e bu s a g em i n i n g ) 。 值得一提的是x m l 技术的出现，不仅为互联网上的电子数据交换提供了一 个标准。而且x m l 技术从数据的角度提供了一个更好地表示数据内容以及数据 所代表的意义的手段。因此基于x m l 技术进行数据挖掘为数据挖掘的研究提供 了新的契机。对于w e b 数据挖掘的研究也逐渐与x m l 结合起来。 r 6 1 流数据挖掘 流数据挖掘( s t r e a m i n gd a t am i n i n g ) ，在数据挖掘和数据分析研究领域中， 最近出现了一个新的研究方向，即流数据的挖掘与分析。流数据是指那些数据 量非常巨大的，无法全部存放在存储介质上进行分析和计算的数据。其特点是 数据持续到达，且速度快、规模宏大：其研究核心是设计高效的单遍数据集扫 描算法，在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构， 使得在任何时候都能够根据这个结构迅速获得近似查询结果。 1 3 3 数据挖掘的功能 数据挖掘不仅能对过去的数据进行查询和遍历，并且能够对将来的趋势和 行为进行预测，并自动探测以前未发现的模式，从而很好地支持人们的决策。 被挖掘出来的信息，能够用于信息管理、查询处理、决策支持、过程控制以及 许多其它应用。数据挖掘按其功能划分主要包括以下几类： f 1 ) 分类 分类是数据挖掘中应用的最多的方法。分类是找出一个类别的概念描述， 它代表了这类数据的整体信息，即该类的内涵描述，一般用规则或决策树模式 表示。一个类的内涵描述分为特征性描述和区别性描述。特征性描述是对类中 对象的共同特征的描述，区别性描述是对两个或多个类之间区别的描述。 ( 2 ) 关联分析 若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种关联， 可以建立起这些数据项的关联规则。关联分析的目的是找出数据库中隐藏的关 联网。在大型数据库中，这种关联规则是很多的，一般用“支持度”，“可信度” 两个闽值来淘汰那些无用的关联规则。 f 3 ) 聚类 数据库中的数据可分为一系列有意义的子集或称为类。在同一类别中，个 体之间的距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客 观现实的认识，即通过聚类建立宏观概念。 ( 4 ) 时序模式 通过时间序列搜索出重复发生概率较高的模式，这里强调时间序列对挖掘 结果的影响。 ( 5 ) 偏差检验 数据库中的数据常有一些异常记录，从数据库中检测出这些偏差很有意义。 偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结 果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是寻找观 测结果与参照之间的差别。 ( 6 ) 预测 预测是利用历史数据找出变化规律，即建立模型，并用此模型来预测未来 数据的种类、特征等。 i 3 4 数据挖掘的方法 ( 】) 粗糙集 粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家 z i ，w l a k 在1 9 8 2 年首先提出，这一方法在数据挖掘中具有重要的作用，通常处 理含糊性和不确定的问题，发现不准确数据或噪音数据内在的结构关系，还可 用于特征的约简和相关分析中。知识工程研究中，一直存在着信息的含糊性 ( v a g u e n e s s ) 等问题。含糊性有三种：1 ) 术语的模糊性，如高矮；2 ) 数据的不确 定性，如噪音引起的；3 ) 知识自身的不确定性，如规则的前提与结果之间的依 赖关系并不是完全可靠的。 人工智能的基础理论之一一经典逻辑不足以解决这些不确定性问题。为此， 人们提出了一些解决方法，包括统计方法、模糊集理论以及d e m p s t e r s h a f f e r 证据理论，但这些方法都有一些内在缺陷或限定范围。例如，基于统计的方法 在理论上还难以令人信服；而模糊集方法则存在一个本质问题即如何确定成员 隶属度，相比之下，粗糙集方法则有几个优点：不需要预先知道的额外信息，如 统计中要求的先验概率和模糊集中要求的隶属度，算法简单，易于操作。 粗糙集对不精确概念的描述是通过上近似( u p p e ra p p r o x i m a t i o n ) 和下近似 ( 1 0 w e ra p p r o x i m a t i o n ) 这两个精确概念来实现的。一个概念( 或集合) 的下近似是 指其中的元组肯定属于该概念：一个概念( 或集合) 的上近似是指其中的元组可 能属于该概念。 ( 2 ) 统计分析 统计分析的理论基础主要是统计学和概率论的原理，是一种较为精确的数 据挖掘技术，它是一种基于模型的方法，包括回归分析、因子分析和判别分析 等，该方法比较容易理解，对结果描述精确。但是当利用大规模数据集来学习 时，统计分析的评估代价变的很敏感。收集关于数据的各种统计量的代价随着 实例数目的增长而增大。尽管最近的收集技术可能减少这个收集活动的代价， 但对每个新的我们所要的统计量集合仍然要花费大量的时间。 ( 3 ) 概念格 r w i l l e 等提出了根据一个二元关系来建立相应概念格或g a l o i s 格的基本 思想，它在本质上描述了对象与属性之间的联系，表明了概念之间泛化与例化 之间的关系。概念格的非形式化定义为： 给定上下文( c o n t e x t ) 为三元组t = ( o ，d ，r ) ，其中o 是对象集合，d 是性质 集合，r 是o 和d 之间的二元关系，则存在唯一的偏序集合与之对应，并且这 个偏序集合产生一种格结构，这种由上下文所诱导出的格称为概念格。x r x 表 示o 中的一个元素x 与d 中一个元素x 之间有关系r 。格中每个结点是一个序 偶( 即概念) ，记为( a ，b ) ，其中a p ( 0 ) ，b p ( d ) ，p ( 0 ) 是o 的幂集，p ( d ) 是d 的幂集，称a 为概念的外延( e x t e n s i o n ) ，称b 为概念的内涵( i n t e n s i o n ) 概念格 是一种完备的概念层次结构，在信息检索、数字图书馆、软件工程、知识分类、 类的设计、网络管理和k d d 等领域，概念格已经显示出一定的应用价值。 ( 4 ) 决燕树 决策树是通过一系列规则对数据进行分类的过程。它以信息论中的互信息 ( 信息增益) 原理为基础寻找数据库中具有最大信息量的字段，建立决策树的 一个结点，再根据字段的不同取值建立树的分枝；在每个分枝中集中重复建树 的下层结点和分枝的过程，即可建立决策树。采用决策树，可以将数据规则可 视化，其输出结果也容易理解。该类方法的实用效果好，影响较大。 ( 5 ) 贝叶斯网络 贝叶斯网络基于后验概念的贝时斯定理，是建立在数据进行统计处理基础 上的方法。它将不确定事件通过网络连接起来，可以对于其他相关事件的结果 进行预测；此外其网络变量可以是可见的，也可隐藏在训练样本中。贝叶斯网 络具有分类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效 果较好，缺点是对发生频率很低的事件预测效果不好。其在医学和制造业等领 域的应用具有较好的效果。 ( 6 ) 人工神经网络 人工神经网络建立在可以自学习的数学模型的基础之上。它可以对大量复 杂的数掘进行分析，并可以完成对人脑或其他计算机来说极为复杂的模式抽取 及趋势分析。 神经网络系统由一系列类似于人脑神经元一样的处理单元组成，我们称之 为节点( n o d e ) 。这些节点通过网络彼此互连，如果有数据输入，它们便可以进 行确定数据模式的工作。神经网络的处理过程主要是通过网络的学习功能找到 一个恰当的连接加权值来得到最佳结果。其比较典型的学习方法是回溯法。它 通过将输出结果同一些已知值进行一系列比较，加权值不断调整，得到一个新 的输出值，再经过不断的学习过程，最后该神经网络得到一个稳定的结果。 ( 7 ) 遗传算法 这是模拟生物进化过程的算法，由三个基本算子组成：1 ) 繁殖( 选择) 是从 一个父代选出生命力强的个体，产生新种群( 后代) 的过程；2 ) 交叉( 重组) 选择两 个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个体；3 ) 变异( 突变) 对某些 个体的某些基因进行变异。 遗传算法可起到产生优良后代的作用。这些后代需满足适应值，经过若干 代的遗传，将得到满足要求的后代( 问题的解) 。 ( 8 ) 规则推理方法 该方法在训练集中搜集规则空间寻找对目标数据进行分类的最有效的规 则( 一般用i f t h e n 形式表示) 。 i 。3 5 数据挖掘的发展方肉 虽然数据挖掘领域已取得令人瞩目的进展。但由于数据挖掘技术还很不成 熟，其应用还有很大的局限性，一些急需解决和完善的问题也摆在了研究者的面 前： ( 1 ) 大规模数据的挖掘 有些挖掘算法在小规模数据库上可获得很好的挖掘结果，但在进行大规模 数据分析时的时空代价却比较大。大规模数据的挖掘技术是近年来研究人员研 究的重点。 ( 2 ) 复杂类型数据的挖掘 以前的数据挖掘面对的主要是以结构化数据为主的关系数据库、事务数据 库和数掘仓库，随着数据处理工具、先进数据库技术以及w w w 技术的迅速发展， 空间数据、多媒体数据、时间序列数据、文本数据、w e b 数据复杂类型的数据 不断涌现。 ( 3 ) 证实技术的局限性 数据挖掘使用特定的分析方法或逻辑形式发现知识，但系统可能没有能力 去交互证实发现的知识，使得发现的知识没有普遍适应性而不能成为有用的知 识。 ( 4 ) 知识的维护和更新 新的数据积累可能导致以前发现的知识失效，这些知识需要动态维护和及 时更新，目前主要采用增量更新的方法来维护已有的知识。 ( 5 ) 数据挖掘语言的标准化 标准的数据挖掘语言或其l 也方面的标准化工作将有勖于数据挖掘系统的开 发，改进多个数据挖掘系统和功能间的互操作，促进数据挖掘系统在企业和社会 中的使用 1 3 6 抽样技术在数据挖掘中的应用 随着人工智能技术，信息技术的日新胃异以及广泛地交互应用，人们已经 开始利用k d d 和d m 技术从浩瀚的数据海洋中挖掘有价值的信息。可近十 几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，而原有的数据 库规模一再膨胀，此外，由于数据分析内部的复杂性都使得现有挖掘算法在进 行大规模数据分析时韵时空代价都比较大。为了减少大规模数据分析所消耗的 资源，人们通常在保证挖掘结果准确性的同时，通过降低数据规模来提高数据 挖掘算法的效率。 显然，对于某一特定应用领域的数据库而者，其特征数及其取值是相对稳 定的，因此当数据增长到一定规模时，该数据库中可能蕴含的知识和模式都不 会继续大幅度地增长。这也就为通过降低数据规模来挖掘大规模数据集的挖掘 算法提供了实用的可能性。 对于，簪低数据规模的力法可以进一步细分为下面的两种思路：1 ) 纵向约简 ( 如降维，堤升概念层次等，i 法) ；2 ) 横向约简( 如分布式挖掘，抽样等方法) 。 本文主要 ，究横向约简中的抽样技术在数据挖掘中的应用。 通过蛐样技术从大规模数据集中，挑选出具有代表性的部分数据，然后用 已有的挖面算法对其进行处理，这样可以大大提高运算效率。 1 4 本文的内容组织 本文主要对抽样技术在数据挖掘中的应用进行研究，全文由七章组成： 第一章首先简述数据库知识发现产生的原因以及发展前景，概述了知识发 现的处理过程和特性，然后详细阐述了知识发现的核心技术数据挖掘的定义、 处理对象、功能、方法以及发展方向，最后介绍了在数据挖掘中引入抽样技术 的原因：适应大规模数据集的挖掘要求。 第二章首先介绍了统计学中抽样调查所的基本概念和术语，并分类介绍统 计学中几种常用的抽样策略，然后在分析统计学和数据挖掘两个领域关系的基 础上，对两个领域中不同的抽样技术进行了比较和探讨，最后介绍了数据挖掘 中常用的抽样策略及其研究和应用的现状。 第三章重点分析了抽样过程中两个基本的要索：样本容量和样本质量。首 先介绍了样本质量的定义及其意义，然后通过分析阐述了样本容量和挖掘结果 准确性之间的关系，最后引入最佳统计样本数( s o s s ) 的定义，并介绍了以数 据驱动的方式确定s o s s 的方法。 第四章本章主要涉及抽样技术在分类规则提取中的应用，研究并提出一种 面向分类规则提取的分层抽样算法。该算法以在保证重要分类规则不丢失的前 提下降低样本容量为目的，采用最优统计样本数确定样本容量并且利用分层抽 样提高分类算法在不均匀数掘集上分类的准确率。 第五章本章主要涉及抽样技术在关联规则提取中的应用，研究并提出一种 加权挖掘频繁项集的抽样方法，该方法是以挖掘大规模频繁项集为目的，同时 兼顾了样本的质量和容量两方面的因素，能够在保持频繁项集基本不丢失的基 础上，降低处理的数据规模。 第六章本章主要涉及抽样技术在聚类分析中的应用，研究并提出一种新的 基于随机抽样的网格聚类算法。该算法继承了基于网格聚类算法对于大规模数 据和高维数据聚类良好的伸缩性，并利用随机抽样确定网格划分粒度的方法进 一步提高基于网格聚类方法的精确度。同时提出若干基于网格聚类算法的改进 方法，进一步提高了聚类的效率。 本章主要介绍了数据库中的知识发现，主要涉及其定义、处理过程及其定 义。对数据库中知识发现中的核心技术数据挖掘进行了详细的阐述，主要涉及 其定义、处理对象、功能、方法以及发展方向。最后介绍了在数据挖掘中引入 抽样技术的原因：j 吞应大规模数据集的挖掘要求。 2 1 引言 第二章数据挖掘中的抽样技术 抽样调查是统计学的概念，它按照一定的程序，从全体调查对象中抽取一 部分进行调查，然后根据样本数据对总体目标进行估计。2 0 世纪2 0 年代起抽 样调查的基本理论逐步形成。抽样调查因其节约时间、节约花费、高正确性和 应用领域广等特性，被广泛应用于社会调查的各个领域中。 2 2 抽样的基本概念和术语 抽4 j f 渊查中包含若予重要的概念如总体、样本、抽样方法、抽样单元以及 样本量等 8 , 9 】。 总体( p o p u l a t i o n ) ：所研究( 调查) 对象的全体。 样本( s a m p l e ) ：按某种方法从总体中抽取其中一部分的个体。 抽样方法：样本的抽取方法，主要可分为概率抽样( p r o b a b i l i t ys a m p l i n g ) 和非概率抽样( n o n p r o b a b i l i t ys a m p l i n g ) 两类。概率抽样也称为随机抽样。概率 抽样是一种从总体中按一定概率获取样本的方法。概率抽样的优点是能够保证 样本的代表性，避免人为的干扰和偏差。它还能对由于抽样引起的误差一抽样 误差进行估计。因此采用概率抽样可以获得估计的精确度。 抽样单元( s a m p l i n gu n i t ) ：为使概率抽样能够实施，同时也为了具体抽样的 便利，通常将总体划分成互不重达的若干部分。 样本量：样本中包含的样本数目。 2 3 统计学中常用的抽样策略 统计学中常见的抽样方法是以下5 种策略的组合： ( 1 ) 简单随机抽样( s i m p l er a n d o ms a m p l i n g ) 从大小为n 的总体中逐个不放回地抽取n 个单元组成样本，每次抽取对于 当时尚未抽取的单元来说都是随机抽取的，也即都是等概率的。 ( 2 ) 分层抽样( s t r a t i f ys a m p l i n g ) 将总体中的单元按某种原则划分成若干个子总体，每个子总体称为层，在 每层中独立进行简单随机抽样或其它抽样。 ( 3 ) 整群抽样( c l u s t e rs a m p l i n 9 1 总体中的每个抽样单元可以分成若干个次级单元，抽样仅对初级单元抽， 若某个切线单元被抽中，则调查这个单元中的所有次级单元。 ( 4 ) 多阶抽样( m u l t i s t a g es a m p l i n g ) 若初级单元内的次级单元相似程度较大，调查所有次级单元会造成很大的 浪费。此时一个自然的想法是在被抽中的初级单元中再对次级单元进行抽样， 这就是多阶抽样。 ( 5 ) 系统抽样( s y s t e m a t i cs a m p l i n g ) 总体中的抽样单元按某种次序排列，在规定的范围内随机抽取一个( 或组) 初始单元，然后按一套事先确定的规则确定其他样本单元的抽样方法。 2 4 数据挖掘中的抽样技术 2 4 1 抽样在数撕挖掘中的作用 抽样技术在据挖掘领域叶主要有如下作用： f 1 ) 提高速度椰效率 速度和效率是评价数据挖掘技术好坏的两大主要因素。数掘挖掘的速度和 效率取决于系统软硬件的运算能力、采用的分析工具和算法、选取数据的方法 以及数据集的特点这几个方面。合理运用抽样技术可以在保证大部分信息不丢 失的同时，提高速度、降低成本，而且由此得出的结论在统计意义上是能够让 人信服的。采用了抽样技术，数据挖掘工作者就可以把精力主要放在建立模型、 选择模型上。而不用把时问浪费在等待系统运算庞大数据的过程中。 f 2 ) 帮助分析特殊性问题 所要分析问题的特点也会影响数掘处理的方法。有些商业问题涉及到破坏 性的实验，显然抽取产品的一小部分来做利用性的实验才是最经济、最有效的 方法。 ( 3 ) 满足数据处理本身的需要 有时数据收集过程中的一些原因可能会造成数据库中会存在一部分无关 的、过时的、错误的或者缺省的记录。当然在进行数据挖掘之前应把这部分数 扼删除掉或加以修正，即是数据挖掘中的数据清理。对整个原数据进行数据清 理也许会比较因难，比较费时费力；即使有时数据挖掘是直接在已经预处理过 的数据仓库里进行但为了解决具体的商业问题。根据问题关于数据的一些假 设对数掘进行进一步的调整仍是必需的。 2 4 2 数据挖掘中的抽样技术与统计学中的抽样技术的比较 抽样技术最初是来源于统计学的概念，而数据挖掘与统计学之间既存在联 系又存在区别。 统计学和数据挖掘有着共同的目标：发现数据中的结构或模式。数据挖掘 强调队大量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学 习，模式识别及数据可视化等科学的边缘学科。用统计的观点，它可以看成是 通过计算机对大量的复杂数据集的自动探索性分析。 数据挖掘和统计学之间有着很大的联系，数据挖掘是建立在统计学的基础 之上。离丌了统计学的基础，数据挖掘机数也就成了无源之水，无根之木。统 计在数据样本选择，数据预处理，数据挖掘过程及评价抽取知识的不注重有着 非常重要的作用。 但是统计学和数据挖掘两者之间也存在着较大的差异： f 1 ) 统计学是一个非常严谨的学科，它有着较完善的理论基础和很强的数 学背景：在采用一个方法之前先要证明，而不是像计算机科学和机器学习那样 注重经验。有些时候同一问题的其他研究者提出一个很明显有用的方法，但它 却不能被证明，在统计学上则说该方法缺乏理论基础。 ( 2 ) 数据挖掘作为几门学科的综合，已经从机器学习那里继承了实验的态 度。这并不意味着数据挖掘工作者不注重精确，而只是说明如果方法不能产生 结果的l 舌就会被放弃。 ( 3 ) 统计学在对数掘进行分析时，首先要建立统计模型，模型的好坏直接 影响统计推断结果，而计算、模型选择条件是次要的。相对于统计学而言，准 则在数据挖掘中起着更为核心的作用。数据点被逐一应用以更新估计量的适应 性和连续性。尽管一些统计学的准则已经得到发展，但更多的应用还是机器学 习。 ( 4 ) 处理数据的规模上也有所不同。在统计中所认为的大型数据集在数据 挖掘者的眼中就显得微不足道。出于处理数据规模的巨大差异，使一些成熟的 统计方法和技术不能直接应用到数据挖掘中去。 ( 5 ) 很多情况下，数据挖掘的本质是很偶然的发现非预期但很有价值的信 息。这说明数据挖掘过程本质上是实验性的。这和统计学是不同的，统计属于 确定性分