（统计学专业论文）数据挖掘中抽样技术的应用研究——方法改进与实证分析.pdf

在改进前后性能的变化情况。 本文主要创新工作如下： ( 1 ) 提出且在实践中实现了改进的静态抽样算法，并提出了改进 的动态抽样算法的思想。 ( 2 ) 将改进的抽样技术引入分类、关联、聚类三个挖掘任务中， 写出了相应的算法，并在数据挖掘软件上加以实现，对结果进行了分 析。 ( 3 ) 提出了一种新的关联规则挖掘的评估方法，并实现了该评估 方法。 关键词： 静态抽样；动态抽样；分类；关联规则；聚类；性能评估 t h ea p p r o v i n gs t u d yo fs a m p l i n gt e c h n o l o g y u s e di nd a i am i n n ga i t e a ：m e t h o d s i m p r o v i n ga n de m p i r i c a ls t u d y a bs t r a c t s a m p l i n gt e c h n i q u e sh a v en o tp u r s u e dt h e i re s s e n t i a lp o s i t i o n si n d a t am i n i n gr e a l ma sw e l la st h e y v eg o ti ns t a t i s t i c si nw h i c ha so n eo f t h em o s ti m p o r t a n t a n a l y s i sm e t h o d s a l t h o u g hs o m es c h o l a r sp u t f o r w a r dt h a tp a r a l l e l i z a t i o na n dc h u n ka l g o r i t h mw o u l db ee v e nb e t t e r t h a ns a m p l i n gi n s u p e rd a t as e t s b u td u r i n gt h ep r a c t i c ep r o c e s sw e f o u n dt h a ts a m p l i n gt e c h n i q u e sh a v et h ea d v a n t a g e st h a to t h e rm e t h o d s c o u l d n tc o m p a r ew h e nt h es i z eo ft h ed a t as e t si sf r o mt e nt h o u s a n dt o h u n d r e dt h o u s a n d - _ - _ _ _ _ s o o n e r s p e e dh i g h e ra c c u r a c y a n de a s i e r r e a l i z a t i o n f u r t h e r m o r e ，a p p l i c a t i o ni nr e a lw o r l di sd i f f e r e n tt os c i e n t i f i c s t u d y h o wt og e tt h em i n i n gr e s u l t sa sa na s s i s t a n tt oc o n c e r nd e c i s i o n a n dp o l i c y q u i c k l ya c c u r a t e l y i st h ef i n a l p u r p o s e r e b u i l d i n ga n d r e s t r u c t u r i n gc o m p l i c a t ea n a l y s i se n v i r o n m e n ti sl o s i n gm o r et h a ng a i n o u t s i d eo ft h em i n i n gl a b o r a t o r y f o rf u r t h e rs t u d yt ot h ep o s s i b i l i t yo ft h ea p p l i c a t i o ni nt h ed a t a m i n i n g ，t h i sp a p e rl a u n c hf r o mt h e o r yc e r t i f i c a t i o na n de x a m p l er e s e a r c h i nt h ef i r s ta s p e c t ：d e f i n i n gt h eo v e r a l lp r o c e s so fk d d s c i e n t i f i c a l l y s u m m a r i z i n gt h ee x t e n s i o no ft h es a m p l i n gt e c h n o l o g yi nt h ec u r r e n t m i n i n gr e a l m ；i n d u c i n gt h r e em o s ti m p o r t a n tm i n i n gm e t h o dp o p u l a r l y a n dm a k i n ga ne l a b o r a t i o na b o u tt h ec o m b i n a t i o no ft h es a m p l i n ga n d d a t am i n i n g c i t i n gt w on e wm e t h o d sa b o u ts a m p l i n gu s e di nm i n i n g w h i c hw a sn a m e da s i m p r o v i n g s t a t i c s a m p l i n g a n d i m p r o v i n g p r o g r e s s i v es a m p l i n ga l g o r i t h m i nt h es e c o n da s p e c t ，d i s c u s s i n gt h e c u r r e n te x t e n s i o no ft h ec o m b i n a t i o no ft h es a m p l i n ga n dm i n i n gi nt h e a r e ao ft h ef i n a n c e ，i n s u r a n c e ，r e t a i l ，m a n u f a c t u r i n ge t c m e a n w h i l ea n e s s e n t i a l t e s t i n g f o rn e wm e t h o dh a sb e e nm a d et o c o m p a r et h e b e t t e r m e n to ft h ef u n c t i o na f t e ri m p r o v i n g t h em a i nr e f o r m i n gw o r kh a sb e e nd o n ei nt h i sp a p e ra sf o l l o w i n g ： ( 1 ) p u tf o r w a r da ni m p r o v e m e n ts t a t i cs a m p l i n ga l g o r i t h ma n da n i m p r o v e m e n tp r o g r e s s i v es a m p l i n ga l g o r i t h m ( 2 ) t h r e ed a t am i n i n gm e t h o d ss u c ha sc l a s s i f i c a t i o na s s o c i a t i o na n d c l u s t e r i n gb a s e do nt h ei m p r o v e m e n ts a m p l i n ga r ed e s i g n e da n dr e a l i z e d i nt h ew e k aa sw e l la sg o tt h em e r i t so ft h e s ea l g o r i t h m s ( 3 ) p u tf o r w a r dan e wv a l u a t i o nm e t h o da b o u ta s s o c i a t i o na l g o r i t h m w h i c hh a sb e e nr e a l i z e di nt h i sp a p e r k e yw o r d s ：s t a t i cs a m p l i n g ；p r o g r e s s i v es a m p l i n g ；c l a s s i f i c a t i o n ； a s s o c i a t i o n ；c l u s t e r i n g ；a b i l i t ye v a l u a t i o n 4 目录 第一章引言7 第一节选题意义7 第二节研究内容和方法。7 第三节文献综述9 第二章数据库中的知识发现13 第一节序言1 3 第二节k d d 的实现过程一1 4 第三节数据挖掘理论15 一、数据挖掘的对象1 5 二、数据挖掘的技术。1 7 三、数据挖掘的应用1 8 第三章数据挖掘与抽样技术1 9 第一节抽样技术的基本理论2 0 一、概率抽样的基本类型2 0 第二节数据挖掘中抽样技术的实现方法2 1 一、静态抽样2 1 二、动态抽样2 2 三、数据挖掘中抽样技术的应用缺陷2 3 第三节基于数据挖掘的抽样方法的改进2 4 一、最优样本容量2 4 二、改进的静态抽样2 5 三、改进的动态抽样2 5 四、改进的抽样技术在数据挖掘中的应用2 6 第四章基于抽样的分类规则提取2 7 第一节数据挖掘中的分类技术2 7 一、常见的分类方法2 7 第二节基于抽样的分类算法的改进2 9 一、方法分析2 9 二、实证分析：3 0 第五章基于抽样的关联规则挖掘3 l 第一节关联规则理论31 一、关联规则3 1 二、关联规则发现3 2 第二节基于频繁项集的a p rio ri 算法3 2 第三节基于抽样技术的关联规则挖掘算法的改进3 3 一、方法分析3 3 二、实证分析。3 4 第六章基于抽样的聚类分析3 7 第一节聚类分析理论3 7 一、主要的聚类分析方法3 7 第二节基于抽样技术的聚类分析方法的改进4 3 一、方法分析4 3 二、实证分析。“ 第七章研究结论与展望4 6 参考文献4 7 附录5 0 6 第一章引言 第一节选题意义 数据挖掘( d a t am i n i n g ) 【1 】是指从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程，其中的信息和知识往往是指有意义的模式和规律。数据 挖掘这个概念被首次提出于上个世纪九十年代初，提出伊始就被迅速地运用到金 融、保险、零售、制造等各个行业。数据挖掘技术的兴起是数据库技术发展的必 然产物，它实现了基于数据库技术的信息管理系统的智能化，提高了信息系统的 有效性和实用性，为利用信息做出决策提供了令人信服的依据。 作为一门涉及甚广的交叉学科，数据挖掘的理论来源主要有数据库、统计学、 机器学习、人工智能、模式识别等。作为数据挖掘理论最重要的基础之一的统计 学更是在挖掘过程中起到了至关重要的作用，甚至有人认为数据挖掘不过是统计 理论在计算机技术上的延续而已，由此对统计方法在数据挖掘中应用之广泛可见 一斑。 当今的数据挖掘研究领域主要分为三大部分：( 1 ) 从数据库技术角度研究数 据挖掘；( 2 ) 从统计学角度研究数据挖掘；( 3 ) 从机器学习角度研究数据挖掘。 应该看到统计的方法和技术几乎已经渗透到了数据挖掘的所有阶段中，而作为统 计学中发展最成熟、应用最广泛之一的抽样技术也在数据挖掘领域应用甚广。 随着数据库规模的扩大，又或者受限于个人电脑的硬件配置，大部分数据挖 掘算法的计算效率在实践中遇到了挑战。作为提高计算效率的一种经济、可行、 有效的手段，抽样技术已被广泛应用于数据挖掘领域。运用抽样技术的关键是要 有一个好的抽样方案，既能提高效率，又能保证结果的正确性。由于抽样和推断 方案的设计需要较深的统计学、数据库、计算科学的知识，所以该技术在数据挖 掘中的应用研究目前尚有许多需要完善之处。 第二节研究内容和方法 抽样技术的应用可以贯穿于数据挖掘的整个阶段：数据准备阶段，数据算法 实现阶段，挖掘效果评估阶段；不同的阶段往往可以根据数据集的特点使用不同 7 的抽样方法进行多次抽样。运用抽样技术不仅仅要达到提高数据挖掘的效率的目 的，更重要的是要保证数据挖掘结果的准确性，并能给出挖掘的误差范围，这就 使得统计方法在数据挖掘的领域有了用武之地，更凸显了统计方法的重要性。 本文从抽样技术在分类、关联和聚类等挖掘技术中的运用着手，首先将统计 学中的抽样技术进行一定的改进，使之适合应用于数据挖掘环境中。其次介绍了 已经存在的分类，关联，聚类中的代表性算法，并从中选出适合用抽样技术进行 改进的一类或几类方法，研究了利用改进的抽样技术如何实现这些数据挖掘任 务，并通过实例实现了这些算法，最后通过相应的统计分析对改进后算法的优越 性做了一定的分析和比较。在本文的写作过程中，运用到了几个学科的知识和思 想，有些可能是前人提到过的，有些可能是本人的创新，但因受制于时空性，无 法一一甄别，若有未注明之处，敬请原创者原谅。 全文主要分成六个章节： 第一章：绪论，简述了本文的选题意义以及研究内容和方法，并回顾了数据 挖掘技术兴起以来抽样技术的发展和相关研究成果。从抽样方式的确定、抽样误 差的定义、样本量的确定、抽样程序的设计、总体参数的推断等五个方面介绍了 数据挖掘领域中抽样技术的研究现状，并指出抽样技术的研究主要集中在国外。 第二章：数据库中的知识发现，比较了数据库中的知识发现( 1 d ) 和数 据挖掘的异同，指出数据挖掘是k d d 实现的主要部分，并总结了k d d 的实现 流程，着重介绍了数据挖掘的主要对象及实现方法，并强调指出k d d 不是提取 一个数据集，将学习算法应用于数据上这么简单的事情，每个挖掘问题都不相同。 必须对数据集进行思考，琢磨它的特点和意义，然后从不同的角度来检验，具有 独创性的找到一个合适的观点，并为数据集设计出合适它的挖掘学习算法。 第三章：抽样技术与数据挖掘，总结了统计学中发展成熟的抽样技术种类：概 率抽样和非概率抽样，同时还列举了数据挖掘中的两类抽样方法：静态抽样和动 态抽样，并比较了这两个领域中抽样技术应用的异同。该处的创新点是提出了一 个改进的静态抽样技术和一个改进的动态抽样技术，并且对改进的理论依据做了 必要的探讨。 第四章：基于抽样的分类规则提取，总结了数据挖掘中现有的分类挖掘的方 法，对各个分类方法的最新研究现状做了简要的介绍。将前文提出的改进的静态 8 抽样技术引入决策树分类算法j 4 8 ，并对该算法做了必要的修改，在某个具体的 数据集上实现了该算法，并比较了引入抽样技术前后的分类效果。 第五章：基于抽样的关联规则挖掘算法，总结了关联规则挖掘的历史，介绍 了关联规则中最流行的a p r i o r 基于频繁项集的关联挖掘，将前文提出的改进的 静态抽样技术引入a p r i o r 挖掘，在某个具体的数据集上实现了该算法，并比较 了引入抽样技术前后的关联规则挖掘的效果。 第六章：面向聚类分析的抽样算法，总结了现今流行的聚类分析的方法，针 对基于统计模型的模糊聚类算法e m ，用上文提出的改进的静态抽样对该算法进 行了改进处理，写出了具体的实现步骤，并在一个具体的数据集上实现了该算法， 比较了引入抽样技术前后该算法的运行效率。 第三节文献综述 对于数据挖掘中抽样问题的研究 2 1 ，主要集中在国外，国内只有少数学者在 研究。数据挖掘中运用抽样技术要保证实现两大目标：提高整个数据挖掘过程的 效率、减少估计的误差( 偏差和抽样误差) 。而实现两大目标的途径主要有：选 择适当的抽样方式，适当定义抽样误差并以此确定适当的样本量，设计合适的抽 样程序。所以在数据挖掘中研究抽样技术，可以从以下几个方面入手：抽样方式 的确定、抽样误差的定义、样本量的确定、抽样程序的设计、总体参数的推断。 目前，就抽样方式来看，学者们主要使用两种方法来研究挖掘问题：即静态 抽样和动态抽样。静态抽样也称单阶段抽样或一次性抽样，是根据预先估计的误 差范围、可靠性等计算一个固定的样本量，所有的后续分析只依据一次性抽取的 一个样本，该抽样方式一般在数据挖掘算法执行之前进行，适合各类挖掘任务的 运用。数据挖掘的静态抽样方式都来自于统计抽样调查领域，主要有：简单随机 抽样、分层抽样、整群抽样。其中，简单随机抽样可以在任何地方单独使用，但 往往包含在其他复杂抽样形式中；分层抽样在分类问题中运用普遍，其中简单和 加权分层抽样都得以运用；整群抽样在聚类时运用较多。比如，h e i k k im a n j l i l a 【3 】， e i n o s h i ns u z t l k i 4 】，都运用一次性抽样方式挖掘了关联规则。 动态抽样指需要经过两次或更多次抽样才能达到最终要求的抽样方法，抽 样过程与算法的执行过程和推断是交互进行的。它直接利用挖掘工具，能及时提 9 供样本与总体接近程度的信息，而不是间接地考虑样本的统计特性。在该抽样方 式下，决策者能够在算法效率和模型正确性之间及时做出抉择。数据挖掘中常用 的动态抽样技术有序贯抽样和累进抽样，它们都可以称为适应。i 生( a d a p t i v e ) 抽 样。序贯抽样是贯序地抽取样本点，可以是一个接一个地抽( o n e b y o n e ) ，也可以 一批接一批地抽( b l o c kb yb l o c k ) ，根据前面已经抽取的样本点组成的样本来判 断样本是否符合要求。如果符合就停止抽样，否则就继续抽取。序贯抽样是数据 挖掘中最早使用的适应性抽样方法，主要用于关联规则挖掘【5 】和聚类分析【6 】。累 进抽样是从一个较小的样本开始，然后按一定规则不断地增加样本容量，同时对 每个样本计算相应的模型正确性，直到正确性不再有明显改善为止，这时的样本 容量就认为是最理想的样本量o s s ( o p t i m i z e ds a m p l i n gs i z e ，简称o s s ) 。动态 抽样方法在分类挖掘的决策树【刀和神经网络【刀的方法中有较好的运用。 另外，构造分类决策树的著名i d 3 算法中运用的w i n d o w i n g 技术，也是 一种较早使用的动态抽样技术，可以看作是累进抽样的一个变种。其思想是通过 使用一个窗口来保存一批数据作为训练集，窗口在初始化时，用数据的一个小的 随机样本构成，得到树模型后用其他数据进行验证。若学习的模型不够准确，在 保留原数据的基础上，从测试集的误分类的记录中随机抽样一些增加到样本中 去。重复此过程直到达到正确性要求。该技术与累进抽样技术相似，只不过增加 样本量时更有选择性、目的性。累进抽样易于理解和接受，适于各类问题的挖掘， 很多研究已经显示了其优越性。但由于实际数据的复杂性，在解决具体问题时， 可能经过多次累进抽样仍达不到最优，增加了计算负担，达不到抽样的目的；有 时还可能抽取的样本量超过实际需要的样本量，造成不必要的浪费。 数据挖掘中抽样误差的定义与估计能直接考量抽样技术的有效性，并能间接 地确定样本容量，是完成抽样方案必不可少的一环。数据挖掘中的误差用来反映 样本模型( 或模式) 与总体模型( 或模式) 的差别，它包含了抽样产生的偏差和 抽样误差。但我们假定已经按照随机抽样的方式进行抽取，所以不考虑抽样偏差， 仅考虑抽样误差。抽样误差的定义对样本量的计算、算法的计算效率和模型正确 性都有影响。一般有三种定义：( 1 ) 定义为样本与总体的实际差异。如，k u n - t a c h u a n g 等【8 】在运用累进抽样挖掘关联规则时，就将抽样误差定义为项目集在样 本中的支持度与在总体中的支持度的绝对差异i f r ( s ) f r ( x ) i ，需要扫描整个数据库， 1 0 以计算项目集x 在总体中的支持度，从而计算该种形式的抽样误差。它适用于 静态抽样和动态抽样。但在计算抽样误差时，需要知道总体参数的值，这在许多 情况下是不现实的。( 2 ) 在动态抽样中，将两个相邻样本问的实际差异作为抽样 误差的估计。如s r i n i v a s a n 【9 】运用同一频繁集在两个相邻样本之问的支持度的差 异来构造相似性函数，以估计抽样误差。( 3 ) 定义实际值与理论值的差异。如f r e y a n df i s h e r 1 0 1 等研究学习曲线的形式时，用幂函数曲线形式进行回归估计，然后 用回归估计的抽样误差作为定义的抽样误差的估计。 上文提到，考查了数据挖掘中抽样误差的确定方法，在一定程度上解决了确 定样本容量的问题。静态抽样的样本量，一般利用统计方法，事先确定推断的精 确度和置信度等参数，然后根据特定原则在抽样之前确定一个概率意义上的有 效样本。依据的原则主要有切比雪夫不等式、中心极限定理、抽样误差的公式等。 动态抽样的最终样本量，是根据预先定义的停止规则来确定的。停止规则就是事 先规定的误差或正确性的阀值。所以动态抽样的最终样本量的确定与抽样误差的 定义有关。正如抽样误差的定义有多种，在这里最终样本量的确定方法也很多。 总的来说，可以归为三类：( 1 ) 用概率标准判断样本与总体的接近程度，如 l a n g l e y t l l 】利用p c e ( p r o b a b l yc l o s ee n o u g h ) 标准，评价样本的特性，判别样本量 是否已经足够大，与总体足够接近。( 2 ) 根据相邻两样本的差异估计总体与样本 的接近程度，如，v e n k a t e s h 等【1 2 】用统计上的w i l c o x o n 两样本检验方法来检验 较大样本产生的偏差与较小样本产生的偏差之间的差异是否显著，如果显著就 应该继续抽样，否则就可以停止抽样。( 3 ) 根据实际值与理论值差异的阀值作为 停止标准，如p r o v o s t 等运用线性回归技术探测最终样本量：在样本量为的某 个邻域内依次增加一定的样本量，根据这些样本量和模型正确性建立线性学习 曲线，如果曲线的斜率接近0 ，则认为最终样本量的坐标点已找到。 完成了上述三部分的研究，剩下的就是在某种环境下实现相应的抽样程序 了。数据挖掘的工具经过近十年的发展已经得到相当广泛的应用，当前具有代表 性的数据挖掘软件一类是基于统计分析的软件，如s a s 中的e n t e r p r i s em i n e r 、 s p s s 中的c l e m e n t i n e 等；另一类是应用于新技术如模糊逻辑、人工神经网络、 决策树理论的工具，如c b re x p r e s s 、e s t e e n 、k a t e c b r 、f u z z yt e c hf o rb u s i n e s s 、 n e u r a ln e t w o r kb r o w s e r 等软件，这些软件并不能完全应用于任何数据挖掘技术的 软件，而是有所侧重。还有一个不得不提的数据挖掘软件w e k a 机器 台，是由新西兰怀卡托大学开发的智能分析系统，它包括了几乎当前流行 的挖掘学习算法，为用户提供了多种实现的方式。除此之外，一些以数学为主的 软件比如r ，m a t l a b 等也提供了部分实现数据挖掘的功能。我们国家数据挖 掘软件的运用和开发还未全面展开，尤其是在模糊逻辑、人工神经网络、决策树 等领域对数据挖掘工具的开发不足。因此，开拓数据挖掘工具的应用和实践是未 来数据挖掘工作中亟待解决的问题【i3 1 。基于统计分析的数据挖掘软件都自带了 实现抽样技术的功能，但基本上都局限于随机抽样，通过适当的设计可以在 w e k a ，r ，m a t l a b 等环境下实现复杂的抽样技术，本文所涉及的改进的抽样 技术就是在w e k a 环境下实现的。 1 2 第二章数据库中的知识发现 第一节序言 计算和通讯的结合建立了一个以信息为源头的新领域，但绝大多数信息尚处 在它的原始状态：数据。这些数据，通常以某种格式被存储在某种类型的数据库 中。随着人们活动的日趋频繁，数据的规模不断扩大，数据库成了数据的海洋。 虽然数据库中有大量的信息，但那些潜在的重要的信息却不会自动地跳到我们的 面前。如何才能将揭示出那些尚未被发现和表达出来的信息呢? 数据库知识发现 k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 技术正是为了满足这种要求而产生和发 展起来的。根据f a y y a d 【1 4 】对k d d 的定义“1 1 1 en o n t r i v i a lp r o c e s so f i n d e n t i f y i n g v a l i d ，n o v e l ，p o t e n t i a l l yu s e f u la n du 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 ni nd a t a ”，知识发 现过程可以粗略的理解为三步骤：数据准备，数据挖掘及结果的解释评估( 见图 2 1 ) 。因为数据挖掘是知识发现的最重要的部分，所以某些应用领域将k d d 与 数据挖掘等同于一个概念。 但k d d 从来就不是提取一个数据集，将学习算法应用于数据上然后等待运 行结果那么简单的事情。每个问题都不相同，你必须对数据进行思考，琢磨它的 特点和意义，然后从不同的角度来分析，具有独创性的找到一个合适的观点，然 后从这个观点出发，为数据设计出适合它的学习算法。对于算法的结果，还需要 从统计学的角度或相关领域的角度进行解释和评价，保留有实际意义结果，剔除 没有实际意义的结论。 图2 1 知识发现过程示意图 第二节肋d 的实现过程 数据库知识发现的出现为从海量数据中发现人们感兴趣的、隐含的、事先未 知的信息提供了有效的解决方案，同时也为数据库领域中对数据的深层次利用开 辟了新的发展空间，结合前人的研究，本文将k d d 的实现过程总结如下： 一、了解待挖掘的数据集的特点，包括结构上的和语义上的；在开始数据挖 掘之前，有必要对待挖掘的数据集进行必要的研究和探索，以便能更好的理解它 的特殊性质。虽然当数据的容量超过一定的数量级之后，传统的统计分布理论不 再适合，但对数据集进行必要的汇总统计，可视化和联机分析处理( o l a p ) 还 是大有裨益的。汇总统计( 如集合的均值和标准差) 和可视化技术( 如直方图和 散点图) 用以考察数据集的分布特点，o l a p 技术主要是从多维数据数组中创建 汇总表的各种方法，从而得到不同抽象层次的数据立方体，以达到全面探索和理 解数据的目的。 二、明确挖掘目的，即问自己想从数据集中得到什么。数据挖掘工具只是人 们认识数据获取信息的手段，它本身并没有目的性，只有当人们把自己的意志转 换成一系列的算法和操作，挖掘工具才能开始工作。比如，经过分析数据集的特 点，发现数据集中提供了许多分类信息，而挖掘的目的正是要获取一个未知实例 的所属类，那么你就可以据此推断将会有哪些类别会出现在未知实例中了。 三、根据需要对数据进行必要的预处理：数据库因为受噪声，丢失数据和不 一致数据的侵扰而使得待挖掘的数据质量低下。低质量的数据将导致低质量的挖 掘结果，因此，对待数据进行预处理显得十分重要。数据清理可以用来去掉数据 中的噪声，纠正不一致。数据集成和数据变换( 如规范化) 将数据由多个源合并 成一致的数据类型。数据归约通过聚集，删除冗余特征或聚类等方法减小数据规 模。实现上述的数据预处理方法的技术很多，有从数据库角度实现的，有从统计 学方法角度实现的，还有从机器学习角度实现的，但它们之间并不互相排斥，可 以一起使用。 四、根据需求建立合适的算法：数据挖掘中常用的方法有分类( c l a s s i f i c a t i o n ) ， 估计( e s t i m a t i o n ) ，预钡t j ( p r e d i c t i o n ) ，关联规则( a s s o c i a t i o nr u l e s ) ，聚类( c l u s t e r i n g ) ， 描述与可视化( d e s c r i p t i o na n dv i s u a l i z a t i o n ) 。其中，前三种方法属于直接的数据 挖掘，目标是应用可得到的数据建立模型，用其他可得到的数据来描述我们感兴 1 4 趣的某一变量。后三种方法，属于间接数据挖掘，期间没有单一的目标变量，目 标是在所有的变量中发现某些关系。自从数据挖掘诞生以来，各个领域的学者和 专家们提出了许许多多实现上述方法的算法，并在不断地对各个算法进行着各种 各样的改进，这一直以来都是数据挖掘研究的一个主要方向。 五、建立计算机程序，自动在数据中实现，以发现规律或者模式。数据挖掘 发展几十年以来，已经诞生了很多种挖掘软件工具，这些工具或者作为数据库系 统( 比如m i c r o s o t ts q ls e r v e r ) 或统计软件系统( 比如s a s ，s p s s ) 中的一个 独立软件包，或者作为一个独立的工作平台( 比如w e k a ) 包含了当今最前沿的数 据挖掘算法及预处理工具。它们大致都提供了两种实现方法：图形界面交互实现 法和命令行界面法。本文在算法改进时主要采用了w e k a 平台的e x p l o r e r 界面和 命令行界面。 六、对结果进行必要的评估。数据挖掘是否真正取得了进展，这是评估的意 义所在。对挖掘结果进行评估并不是件容易的事，因为评估的结果有多大程度的 可靠性本身就是个问题。通常的做法是，事先为算法指定一个训练集( t r a i n i n g s e t ) ，一个测试集( t e s ts e t ) ，在训练集上获得算法的实现，在测试集上评估算法的 可信度。评估中用到很多领域的知识，比如信息理论( 熵，信息损益等) ，比如 统计学理论( 假设检验，r o c 曲线) ，经济学理论( 比如成本函数) 等。不同的 评估方法可以对同一个挖掘方案进行评估。 第三节数据挖掘理论 一、数据挖掘的对象 原则上说，一切数据集都可以成为数据挖掘的对象，参考当下数据存储的方 式，主要有如下对象：关系数据库，数据仓库，高级数据库系统( 包括对象一关 系数据库，空间数据库，时间序列数据库，文本数据库，多媒体数据库等) ，数 据流，万维网。 ( 一) 关系数据库 关系数据库是二维表的汇总，每个表包含一组属性，通常存放大量的元组， 每个元组代表一个对象，被唯一的关键码标识，并被一组属性值描述。从统计学 角度看，一张表相当于一个总体，一个元组相当于一个样本。通过关系数据库提 1 5 供的函数功能，可以了解一些元组之间的统计关系，由其提供的查询功能可以从 不同的层次( 或维度) 上对数据进行汇总和抽象。 关系数据库是数据挖掘最常见，最丰富的数据源，是数据挖掘研究的主要 数据形式。 ( 二) 数据仓库 数据仓库是一个从多个数据源收集的信息存储库，存放在一个一致的模式 下，并驻留在某个站点。数据仓库是通过数据清理、数据变换、数据集成、数据 装入和定期数据刷新构成的。与数据库相比，它有更稳定、安全、数据处理更灵 活等特点。许多大型企业都有自己的数据仓库，这往往是企业做出研究决策的基 础。 ( 三) 高级数据库系统 高级数据库系统，包括对象一关系数据库，空间数据库，时间序列数据库， 文本数据库，多媒体数据库等，虽然这些高级数据库德存储和访问机制很复杂， 但现实的需求还是大大带动了这类数据库系统的挖掘研究。 ( 四) 数据流 数据流也常被称为流数据( s t r e a md a t a ) ，指数据以固定的次序动态地从观 察窗口流进或流出，比如股票交易、w e b 点击流、网络通信等。因为流数据是海 量的甚至是无限的，所以通常不存放在数据存储库中，因此要求对它的挖掘算法 也是要动态的或增量式的，这对挖掘工作提出了巨大的挑战。目前，许多研究者 正在考察研究数据流管理系统开发的问题，这种系统通过连续查询模型，以预定 义的方式，不断计算进入流，收集聚集数据，报告当前数据流的状态，对它们的 变化做出响应。 ( 五) 万维网 万维网及其分布式信息系统提供了丰富的世界范围的联机信息服务，用户通 过链接从一个对象搜索到另一个对象，但搜索到的对象往往范围太广，要从中找 到用户感兴趣的内容，又是一个繁复的过程。如果能根据用户的需求为搜索建立 一个合适的搜索模式，就能使链接更具有针对性和高效性，而这就对数据挖掘提 出了新的挑战。 1 6 二、数据挖掘的技术 数据挖掘是k d d 中最关键的步骤，也是技术难点所在。研究k d d 的人员 大部分都在研究数据挖掘技术，而采用较多的技术有分类、聚类、关联、时序等。 数据挖掘根据k d d 的目标，选取相应算法的参数并分析数据，得到可能形成知 识的模式和模型。常见的数据挖掘技术主要有以下几类： ( 一) 分类 分类首先对不同的类别加以定义，并从分类定义后的数据集中抽取适当的样 本构成训练集( t r a i n i n gt e s t ) ，建立一个适当的模型，通过这个模型将未知类别 的新事物分配到事先确定的类别当中。常见的例子有：将信用卡申请者按低、中、 高风险进行分类等。 ( 二) 估计 通过对已知数据的分析，用估计的方法得到未知的连续型随机变量的某个数 值，估计与分类有相同的实现机制，只不过分类针对的是离散型数据，而估计是 针对于连续型数据。在实际工作中估计也常被用来实现分类工作。常见的估计有： 对各种已知成员结构家庭总收入的估计等。 ( 三) 预测 预测是通过目前存在的数据状态，预测数据未来的情况，预测的结果可能是 离散的，可能是连续的，这似乎与分类和估计十分相似，区别在于预测是对没有 发生事情的未来把握，而分类或估计是对现存事物的研究。比如：预测未来一段 时间内哪些客户会增加在公司的业务。 ( 四) 关联规则分析 关联规则分析用于发现隐藏在大型数据集中令人感兴趣的联系，或者说是要 找到数据集中哪些数据项会一起出现，或一定不会一起出现。典型的例子是：超 市购物中，顾客通常会同时购买那些商品。 ( 五) 聚类 聚类是将相似的事物分成一类，差异较大的事物分在不同的类中，它与分类 的区别在于，聚类事先并不知道事物所在的类别，事物只是按照自身特征的相似 性聚集在不同的类别当中，所以聚类常被称为无指导的挖掘。常见的聚类例子是： 将有相同购物习惯的顾客分在同一个类别当中。 1 7 ( 六) 描述与可视化 有时候数据集本身并没有明确的模型，我们要做的只是将数据集的特征描述 清楚。数据可视化是数据挖掘的一种描述性的有效手段。虽然这并不太容易，但 却非常有效。常见的可视化例子是：当前中国社会中男女就业情况的性别差异。 三、数据挖掘的应用 数据挖掘技术起源于数据库技术的广泛应用，由于金融、保险、零售、制造 等行业中数据量的急剧膨胀造成了“数据丰富而知识贫乏”的局面，从海量数据 中攫取信息和知识的数据挖掘技术应运而生。从上世纪九十年代至今，数据挖掘 技术的应用已经越来越频繁，但数据挖掘的应用研究还应该向新的领域进行探索 和扩张。在注重理论、技术研究的同时，强调实际应用的研究。杨立雄认为，基于 电子商务环境下的数据挖掘技术能获取顾客、商品、市场、广告策略、网站服务 器、网页信息【1 5 】。谢丹夏，李晓东认为，数据挖掘有助于理解顾客行为，判断w e b 站点的效率，评估电子商务模式的成功与否【1 6 】。谭小萍，柳炳祥认为，数据挖掘 可以被应用到以客户为中心的企业决策分析和客户关系管理的各个领域和阶段， 以增强企业的竞争优势1 7 1 。本文对数据挖掘中抽样技术的应用研究正是为了提 高数据挖掘方法在实际应用中的效率，而研究结果的有效性也将由实践来检验。 1 8 第三章数据挖掘与抽样技术 数据挖掘是从存放在数据库、数据仓库或其他信息库的海量数据中挖掘有趣 知识的过程。数据挖掘技术自兴起以来，一直是研究的热点问题，现在已经有了 大量的实现算法。但随着需要处理的数据规模越来越大，且由于数据内部的复杂 性，许多算法在进行大规模数据分析时需要消耗大量的人力和物力，如何减少大 规模数据分析所消耗的资源问题就不可避免地摆在我们面前。为了提高数据挖掘 算法效率，我们很自然地会引进统计中的抽样思想，作为提高算法计算效率的一 种经济、可行、有效的手段，抽样技术已被广泛应用于数据挖掘领域。运用抽样 技术的关键是要有一个好的抽样方案，既能提高效率，又能保证结果的正确性。 当然，数据挖掘中的抽样技术和统计学中的抽样技术还是有不同之处的，虽然前 者的理论来源于后者，但它的实现方式和实现步骤与后者有很大的差别：首先必 须先对大规模数据集的数据进行必要的分析，然后根据相应的结果选择适当的抽 样策略使抽出的样本对原数据集的数据扭曲( d a t ac r e w ) 尽可能小，最后给出抽 样误差。 抽样技术是一种选择数据对象子集进行分析的常用方法。在统计学中，抽样 长期用于数据的事先调查和最终的数据分析。在数据挖掘中，抽样技术也非常有 用，然而在统计学和数据挖掘中，抽样技术的应用动机和作用并不一样。统计学 使用抽样是因为得到整个数据集的费用太高、太费时间，或者根本不知道数据的 总体是什么，因此只能使用抽样技术来研究数据总体。应用抽样技术的目的主要 是对总体特征进行推断；在数据挖掘中，使用抽样技术是因为处理所有数据的费 用太高、太费时间，应用抽样技术可以压缩数据量，减少计算的开销，从而挖掘 出与总体挖掘效果相近的知识或模式。当然，两者也有共同性，比如，无论是统 计学中的抽样还是数据挖掘中的抽样，评价抽样技术好坏的标准是一致的，都是 看样本是否对总体数据集有较好的代表性。 抽样技术的应用可以贯穿于数据挖掘的整个阶段：数据准备阶段，数据算法 实现阶段，挖掘效果评估阶段；不同的阶段往往可以根据数据集的特点使用不同 的抽样方法进行多次抽样。运用抽样技术不仅仅要达到提高数据挖掘效率的目 的，更要保证数据挖掘结果的准确性，并能给出挖掘的误差范围，这就使得统计 方法在数据挖掘的领域有了用武之地，更凸显了统计方法的重要性。 1 9 第一节抽样技术的基本理论 抽样调查是一种非全面调查，是从全部调查研究对象( 总体) 中，抽选 一部分单位( 样本) 进行调查，并据此对总体做出估计和推断的一种调查方法。 抽样调查虽然是非全面调查，但其目的却在于取得反映总体特性的信息，是统计 学中最重要的方法之一。通常抽样调查可以分为两类：概率抽样和非概率抽样。 概率抽样是按照随机原则进行抽样，不加主观因素，组成总体的每个单位都有被 抽中的概率，可以避免样本出现偏差，样本对总体有很强的代表性。非概率抽样 是按主观意向进行的抽样( 非随机的) ，组成总体的很大部分单位可能没有被抽 中的机会，在某些情况下会使调查容易出现倾向性偏差，它的特点是误差大、难 以估计、代表性小，适合探索性研究，主要方法有：偶遇抽样、判断抽样、定额 抽样、雪球抽样等。 当前，在数据挖掘中被广泛应用的抽样调查是指概率抽样。从统计学角度看， 概率抽样的关键问题就在于对所关心的总体目标量构造出相应的样本估计量，并 能确定该估计量的抽样分布。对于同一目标量而言，可以得到不同的样本估计量， 而庄抽样调查中评判估计量优劣的主要指标就是比较其方差的大小。 一、概率抽样的基本类型 概率抽样是依据概率论的基本原理，按照随机原则进行抽样，主要方法有： 简单随机抽样、系统抽样、分层抽样、整群抽样、多阶段抽样等。 ( 一) 简单随机抽样 按照等概率原则直接从含有n 个元素的总体中随机抽取n 个元素组成样本 ( n n ) 。简单随机抽样是一种最基本的抽样方法，是其他抽样方法的基础，它 能产生代表