（计算机应用技术专业论文）密度偏差抽样在海量数据挖掘中的应用研究.pdf

重庆邮电大学硕士论文摘要 摘要 挖掘海量数据，从中发现有用的信息与知识是当前数据挖掘研究领域面临的 重大挑战。到目前为止，海量数据挖掘的主要解决策略包括数据约简和数据降维 等，其中，基于统计学中的抽样方法是数据约简方法之一。简单随机抽样方法虽 然简单易行，但由于许多数据集含有噪声、非对称、不均匀分布，因此不能正确 反映原始数据的总体特性。密度偏差抽样算法通过把数据集密度映射为数据点的 抽样概率，调整其抽样概率来达到偏差抽样的目的。 本文在c p a l m e r 的密度偏差抽样算法的基础上，提出了改进的基于网格的密 度偏差抽样算法。该算法利用网格结构映射存储数据，经实验证明可以抽取得到 高质量的样本，更好的保持了原始数据集的分布特征，并且具有良好的抗噪声能 力，因此该算法在实现数据约简的过程中是可行的。 本文针对密度偏差抽样在海量数据挖掘中的聚类和关联规则领域的应用进行 了探讨。前者是在密度偏差抽样的样本上进行聚类分析；后者将密度偏差抽样算 法与经典a p r i o r i 算法融合，提出了基于密度偏差抽样的加权挖掘频繁项集的算 法。在聚类实验过程中，首先通过基于网格的密度偏差抽样和简单随机抽样方法 获得样本，然后在各自的样本上进行聚类的正确识别对比测试，实验证明本文的 方法在较低抽样概率的情况下获得了较高的正确识别率。同时，在经实验测试后 也验证了基于密度偏差抽样的加权挖掘频繁项集的算法在关联规则挖掘中的高效 性。 关键词：数据挖掘，偏差抽样，网格，聚类，关联规则 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t i t so n eo fi m p o r t a n tc h a l l e n g e st h a tm i n el a r g ed a t aa n df i n do u tu s e f u l i n f o r m a t i o na n dk n o w l e d g e n o w a d a y s ，t h em a j o rs o l v es t r a t e g i e sc o n t a i nd a t a r e d u c t i o n , d i m e n s i o nr e d u c t i o n ，a n ds oo n t h es a m p l i n gm e t h o d ，w h i c hb a s e do n s t a t i s t i c s ，i so n eo f d a t ar e d u c t i o nm e t h o d a l t h o u g hu n i f o r mr a n d o ms a m p l i n gi ss i m p l e a n de a s y , w h e nd a t as e tc o n t a i n sn o i s y , d i s s y m m e t r ya n da s y m m e t r yd i s t r i b u t i o n ， s a m p l ec a n tr e f l e c tt h ew h o l ec h a r a c t e r so fo r i g i n a ld a t a t h ed e n s i t yb i a s e ds a m p l i n g a l g o r i t h mc a ng e tt ks a m p l i n gp r o b a b i l i t yo fd a t ap o i n t sb ym a p p i n gt h e _ d a t ad e n s i t y , t h e na d j u s tt h es a m p l i n gp r o b a b i l i t yt ob i a s e ds a m p l i n g t h i sp a p e rb a s e so nc p a l m e r sd e n s i t yb i a s e ds a m p l i n ga l g o r i t h ma n dp r o p o s e sa n i m p r o v e dg r i d - b a s e dd e n s i t yb i a s e ds a m p l i n ga l g o r i t h m t h i sa l g o r i t h ms t o r e sd a t ab y g r i ds t r u c t u r e a c c o r d i n gt ot h ee x p e r i m e n t ，w ec a ng e th i g hq u a l i t ys a m p l e ，k e e pt h e d i s t r i b u t i n gc h a r a c t e r so f o r i g i n a ld a t as e t t h i sa l g o r i t h m i si n s e n s i t i v et on o i s e s oi ti s f e a s i b l ei np r o c e s so f d a t ar e d u c t i o n t h i sp a p e rd i s c u s s e st h eu s eo fd e n s i t yb i a s e ds a m p l i n gi nc l u s t e r i n ga n d a s s o c i a t i o nr u l e so nl a r g ed a t am i n i n gf i e l d t h ef o r m e ri sc l u s t e r i n ga n a l y s i sa b o u tt h e d e n s i t yb i a s e ds a m p l e s t h el a t t e rf u s e st h ed e n s i t yb i a s e ds a m p l i n ga l g o r i t h ma n d c l a s s i c a la p r i o r ia l g o r i t h m ，t h e np r o p o s e saw e i g h t e dm i n i n gf r e q u e n ti t e m s e t s a l g o r i t h mb a s e do i ld e n s i t yb i a s e ds a m p l i n g d u r i n gt h ec l u s t e r i n ge x p e r i m e n t ，f i r s t l y w eg e ts a m p l e sb yg r i d b a s e dd e n s i t yb i a s e ds a m p l i n ga n ds i m p l er a n d o ms a m p l i n g , s e c o n d l yw ed oc o r r e c ti d e n t i f yc o n t r a s ta n a l y s i s0 ns a m p l e sc l u s t e r i n g i tp r o v e st h a t t h em e t h o dg e t sh i g hc u r r e c ti d e n t i f yr a t ed u r i n gl o w e rs a m p l i n gp r o b a b i l i t y i ta l s o p r o v e st h a tt h ew e i g h t e dm i n i n gf r e q u e n ti t e m s e t sa l g o r i t h mb a s e do nd e n s i t yb i a s e d s a m p l i n gi sh i g he f f i c i e n c yi na s s o c i a t i o nr u l e sm i n i n g k e yw o r d s ：d a t am i n i n g , b i a s e ds a m p l i n g ，咖d ，c l u s t e r i n g ，a s s o c i a t i o nr u l e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重废塑盥太堂或其他教育 机构的学位或证书而使用过的材科。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位做作者躲旅螂签字吼孑的7 年月7 日 学位论文版权使用授权书 本学位论文作者完全了解 重庆塑生盘堂有关保留，使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重废邮电太堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期 孑舻7 年占月厂日 导师签名： 签字目期：如矿年和 i i 7 r 重庆邮电大学硕士论文 第一章绪论 1 1 引言 第一章绪论 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含其中的、人们事先不知道的、具有潜在利用价值的信息和知 识的过程i ”。数据挖掘技术自兴起以来，一直是研究的热点问题，现已有大量的经 典算法。随着网络技术的飞速发展，以及数据库技术的进步诸如：多媒体数据库、 空间信息系统，传感技术以及空间数据库的出现，需要处理的数据规模越来越大， 动辄以g b ，甚至t b 计。使得现有挖掘算法在进行大规模数据分析时的时空代价都比 较大。为了减少大规模数据分析所消耗的资源，人们通常在保证挖掘结果准确性 的同时，通过降低数据规模来提高数据挖掘算法的效率。 一个数据集具有海量的记录或很多属性，或者两者都有，则称它为大规模数 据集( v e r yl a r g ed a t as e t s ) 。随着大规模数据集越来越普遍，数据挖掘的发展也需 要使其更适宜于处理这些数据集。在面向大规模数据集的处理时，现有方法主要 思想，均是减少计算机直接处理的数据规模。对于降低数据规模的方法可以进一 步细分为下面的两种思路：1 ) 纵向约简( 如降维，提升概念层次等方法) ；2 ) 横向约 简( 如分布式挖掘，抽样等方法) 。基于统计学中的抽样方法，对部分数据进行分析， 然后推测原始总体数据集的相关信息，无疑是克服大规模数据的成功方法之一， 能有效减少需要调入内存的数据量，有效实现数据约简，提高算法执行效率。 本文主要研究横向约简中的抽样技术在数据挖掘中的应用。通过抽样技术从 大规模数据集中，挑选出具有代表性的部分数据，然后用已有的挖掘算法对其进 行处理，这样可以大大提高运算效率。 1 2 关联规则挖掘的研究现状 关联规则是数据挖掘的核心技术之一，它是由r a 伊a w a l 等人首先提出的印j 。 关联规则就是给定一组项目( i t e m ) 和一个记录集合，通过分析记录集合，推导出i t e m 间的相关性，关联规则广泛地应用于商业界、医疗保险、金融业、司法部门等。 因此对它的研究有着极其重要的意义。在所有关联规则挖掘的算法中，著名的算 法是r a g r a w a l 等人于1 9 9 3 年提 ；的a p o r j 算法【2 j ，该算法是最有影响的挖掘布尔 型频繁项目集的算法。a p r i o r i 算法是通过发现支持度大于用户设定的最低支持度 重庆邮电大学硕士论文第一章绪论 ( m i n s u p p o n ) 的频繁项目集( f r e q u e n ti t e m s e t s ) ，再从频繁项目集中挖掘其可信度大 于用户设定的最低可信度( m i n c o n f i d e n c e ) 的关联规则。 1 2 1 基本概念 挖掘关联规则的问题，最早出现于 2 】中针对的是超市的数据，交易集由顾客 购买的项目组成，数据看成是二制的( 在交易中出现时为l ，否则为o ) ，不考虑交易 中项目的数量。a g r a w a l 给出了在数据库中挖掘关联规则问题的定义，描述如下： 设l = i l ，i 2 ，i m 是n 1 个不同项目的集合。设任务相关的数据d 是数据库事务的集 合，其中每个事务t 是项的集合，使得t c l 。每一个事务有一个标识符，称作t i d 。 设a 是一个项集，事务t 包含a 当且仅当a _ c t ，记t ( a ) 表示包含a 的事务的集合。 定义1 1 ：令x 是i 中任一项目集，若其中含有k 个项目，则称为k 项目集。 定义1 2 ：当且仅当x c t 时，称交易t 支持x ，一个项目集x 的支持度( s u p p o r t ) 为数据集d 中包含x 的事务数量与数据集d 的总事务数量之比，但为下文便于叙述， 项目集x 的支持度用数据集d 中包含x 的交易数量来表示。 定义1 3 ：若项目集x 在d 中的支持度s u p p o r t ( x ) 大于用户给出的最小支持度 ( m i n - s u p ) ，则此项目集为频繁项目集( 大项目集1 。否则为小项目集。 定义1 4 ：关联规贝l j ( a s s o c i a t i o nr u l e ) 就是形如x y 的式子，其中x c l ，y c l ， 并且x n y = 彩。这里x 称为规则的前件( a n t e c e d e n t ) ，y 称为规则的后件( c o n s e q u e n t ) 。 若交易d 中s 的交易包含x 的同时也包含y ，则规则在d 中的支持度为s ，表示出来 就是s = s u p p ( x u y ) ；若交易集d 中包含x 的交易的c 也包含y ，则规则在d 中的置信 度( c o n f i d e n c e ) 为c ，用公式表示就是c = c o n f ：竺丛! ；当。可以看出其实置信度是 s u p t xj 一个条件概率，是在给定x 条件下y 出现的概率。 支持度表示规则在数据库中出现的频度，置信度表示规则的强度。最小支持 度闽值( r a i n表示项目集在统计意义上的最低主要性。最小置信度阈值sup) ( m i n 阈值，支持度和置信度大于规定的阂值的规则称为强关联规则，反之，为弱关联 规则。挖掘关联规则的任务就是发现所有支持度和置信度大于用户给定闽值的强 规则，即产生所有形式为x j y 的关联规则，其中s u p ( x w y ) m i ns u p i d l ， c o n f _ s u p ( x u r ) m i nc o n f o 关联规则挖掘问题可以分成两个子问题： s u p ( x ) ( 1 ) 产生所有支持度大于用户指定最小支持度的项目集，也就是频繁项目集； ( 2 ) 利用这些频繁项目集生成关联规则。对于每。个大项目集i ，找出它的所 重庆邮电大学硕士论文第一章绪论 有非空子集，对每一个非空子集a ，如果竺旦舆2 m i nc o n f , 则生成形式为a j i - a s u p ( a ) 的规则。那些在第一步被发现是频繁的项目集的支持度要保留，以供第二步计算 规则的置信度时使用。 在关联规则挖掘问题中，第二步相对比较容易，可以直接产生出规则。第一 步却比较费时，对于大数据库来说计算代价很大，现实生活数据更是如此。大的 零售数据库中，交易上百万，项目( 属性) 成千，当数据包含有n 个项目时，大项目 集的数目则可能会达至u 2 n - i ，但实际上数据库中的大项目集数目会比2 n 1 小，所以 就要耗费成指数倍的时间来发现大项目集。为减少可能的大项目集的数目，已经 出现了许多有效的算法。这些算法大都采用有效的数据结构( 像h a s ht a b l e s ，h a s h 仃e e s ，m u l t i h y p e r g r a p h s ，e t c ) 来减小潜在大项目集的大小，进而加速搜索进程。总 的来说，关联规则算法的效率依赖于候选项目集的大小和扫描数据库的次数。目 前大多数关联规则算法主要集中在以下几个方面来高效提取大项目集： 1 减少扫描事务数据库的次数以减少i o 时间； 2 最大程度的对候选项集进行剪枝； 3 尽快的能够计算候选项目集的支持度； 4 并行产生候选项目集； 在这种意义上，关联规则算法的不同集中在下面几个方面： 1 候选集的产生； 2 候选项目集支持度的计算； 3 扫描数据库的次数； 4 使用的数据结构； 另一方面，发现大项目集是很耗时的过程，候选项目集越少，算法越快。当 降低支持度时，算法运行时间增长，因为它要检查很多的候选集和大项目集。 1 2 2 关联规则挖掘算法研究现状 ( 1 ) 关联规则经典的a p r i o r i 算法 a p r i o r i 算法是关联规则中一种最有影响的挖掘布尔型关联规则频繁项目集的 算法。算法的基本思想是基于先验知识，a p f i o r i 算法所采用的是逐层迭代搜索方 法，利用k 频繁项目集搜索并确定( k + 1 ) 项频繁项集。在搜索过程中，可以利用一种 称作a p r i o r i 性质的重要性质来压缩搜索空间，以提高频繁项集逐层产乍的效率。 a p r i o r i 性质：频繁项集的非空子集都必须是频繁的。a 鲥o “性质基j ：如下观察： 根据定义，如果项集i 小满足最小支持度阈值m i n s u p p o r t ，则i 不是频繁的。如果项 重庆邮电大学硕士论文第一章绪论 a 添加到i ，则结果项集f i u a 不可能比i 更频繁出现。 利用a p r i o r i 算法逐层挖掘频繁项集主要分为两个步骤：连接步骤和剪枝步骤。 其中连接步骤利用y a p r i o r i 性质将( k - t ) 项频繁集连接组成k 项频繁集的候选集；剪 枝步骤则是在候选集中确定出k 项频繁集。 ( 2 ) 频繁项目集的优化算法 虽然a p r i o r i 算法自身己经进行了一定的优化，但是在实际的应用中还是存在 不足，如利用a p n o n 性质挖掘频繁项集时可能产生大量的频繁项集的候选集，而 从这些候选集中确定出频繁集时候还需要多次遍历数据库。于是人们相继提出了 以下一些优化的方法； 1 ) 基于栈变换的算法：惠晓滨等在文【4 】中提出了一个基于频繁模式栈变换的 高效关联规则算法f a s t ，该算法采用一种频繁模式栈的数据结构来储存所有的频 繁模式信息，所有的栈单元都具有偏序关系，并分成构造算法和变换算法两个子 算法，算法效率提高，且在数据集的记录数较大时有很好的线性性和伸缩性。 2 ) 基于划分的方法：s a v a s e r e 等在文 5 】中设计了一个基于划分( p a r t i t i o n ) 的算 法，这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个 分块并对它生成所有的频繁项集，然后把产生的频繁项集合并，用来生成所有可 能的频繁项集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分 块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能 的频繁项集至少在某一个分块中是频繁项集所保证的。这个算法是可以高度并行 的，可以把每一分块分别分配给某一个处理器生成频繁项集。产生频繁项集的每 一个循环结束后，处理器之间进行通信来产生全局的候选k 一项集。 3 ) 减少冗余规则的算法：吴伟平等在文 6 】中提出一种无冗余快速关联规则发 现算法，该算法基本原理与a p r i o r i 算法相似，但采取了不同的计算候选项集支持 度的方法。首先通过对数据库的一次搜索得到频繁1 项集，然后使用一个链表得到 其他频繁项集。规则生成的方法也与a p r i o r i 算法不同，该算法首先以最大频繁项 集中的某一项目为前件生成规则，再讨论前件中包含该项目的子规则。所以，该 算法所需的脚次数较少且内存开销适中，消除了简单和严格冗余规则，减少了发 现的规则数量，同时提高了规则发现的速度。 4 ) 基于h a s h 的方法：基于哈希( h a s h ) 的算法由p a r k 等在文 7 】中提出。通过实验 他们发现寻找频繁项集主要的计算是在生成频繁2 项集上，于是p a r k 等人利用这个 性质引入哈希技术来改进产生频繁2 项集的方法。 4 重庆邮电大学硕士论文第一章绪论 1 3 聚类挖掘的研究现状 聚类是把一组个体按照相似性归成若干类别，即“物以类聚”。聚类算法是将 一组分布未知的数据进行分类，以尽可能地使同一类中的数据具有相同性质，而 不同类的数据其性质各异。聚类的目的是寻找隐藏在数据中的结构。由于聚类算 法不对数据做任何先验统计假设，故在模式识别和人工智能等领域，聚类算法也 常常被称之为“无导师学习”或“自组织算法”。 1 3 1 基本概念 将物理或抽样对象的集合分成由类似的对象组成的过各类的过程被称为聚 类。它的目的是使得同一类别的个体之间的距离尽可能的小，而不同类别上的个 体间的距离尽可能的大。聚类方法包括统计方法、机器学习方法、神经网络方法 和面向数据库的方法。聚类是一个富有挑战的研究领域，它的潜在应用提出了各 自特殊的要求。数据挖掘对聚类的典型要求如下： 1 ) 可伸缩性 很多聚类算法在小数据集合上工作的很好，但对于大型数据库执行聚类算法 的时空代价都太大，而且可能会得到偏差较大的结果。这就需要聚类算法具有高 度的可伸缩性。 2 1 处理不同类型属性的能力 许多算法被设计用来聚类数值型数据，但实际中的聚类数据可能是序数型 ( o r d i n a l ) ，语义文本类型，分类标称类型( c a t e g o r i c a l n o m i n a l ) ，二元类型( b i n a r y ) 的数据或者这些数据类型的混合。 3 ) 发现任意形状的聚类 许多聚类算法是基于度量距离来决定聚类，这些算法只能发现具有相近尺度 和密度的球状簇。但实际的聚类簇可能是任意形状的。因此，提出能发现任意形 状聚类簇的算法是很重要的。 4 1 用于决定输入参数的领域知识最小化 许多聚类算法的结果对于在分析过程中用户输入的参数十分敏感，参数的优 劣决定着聚类结果的好坏，使得聚类的质量难以控制。 5 1 处理噪声数据的能力 绝大多数现实世界中的数据库都包含了孤口点，空缺，未知数据或者错误数 捌。一些聚类算法对这样的数据十分敏感，这“j 能导致低质量的聚类结果。 6 1 对于输入记录的j 瞑序不敏感 重庆邮电大学硕士论文第一章绪论 一些聚类算法对于输入数据的顺序是敏感的。开发数据输入顺序不敏感的算 法具有重要的意义。 7 ) 高维性 一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理 低维的数据，可能只涉及两到三维。在高维空间中进行数据聚类是非常有挑战性 的，特别是考虑到这样的数据可能非常稀疏，而且高度偏斜。 8 ) 基于约束的聚类 现实世界的应用可能需要在各种约束条件下进行聚类，假设你的工作是在一 个城市中为给定数目的自动提款机( 姗选择安放位置。为了做出决定，你可以对 住宅区进行聚类，同时要考虑到城市的河流和公路网，每个地区的客户要求等情 况。要找到既满足特定的约束，又具有良好聚类特性的数据分组是一项具有挑战 性的任务。 9 ) 可解释性和可用性 通常用户希望聚类结果是可解释的，可理解和可用的。也就是说，聚类应当 能够与特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一 个重要的研究课题。 1 3 2 聚类算法的研究现状 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的 目的和应用。大体主要的聚类算法可以划分为划分方法( p a r t i t i o n i n gm e t h o d ) ，层次 的方法( h i e r a r c h i c a lm e t h o d ) ，基于密度的方法( d e n s i t y - b a s e dm e t h o d ) ，基于模型的 方法( r r i o d e l b a s e dm e t h o d ) ，基于网格的方法( g r i d - b a s e dm e t h o d ) 。具体方法的选择 取决于数据的类型、聚类的目的和应用的领域等，如果聚类分析用于描述或预测， 还可以对相向的数据集合分别采用多种聚类算法，这种尝试可能会发现有趣的结 呆。图1 1 是对已有的一些聚类方法之问的演变关系和它们的分类进行的总结。 6 重庆邮电大学硕士论文第一章绪论 图1 1 聚类算法分类演进图 ( 1 ) 基于划分的方法 给定一个1 1 个对象或元组的数据库，一个划分方法构建数据的k 个划分，每个 划分表示一个聚类，并且k - - n 。也就是说，它将数据划分为k 个组，同时满足如下 的要求：1 ) 每个组至少包含一个对象；2 ) 每个对象必须属于且只属于一个组。 给 定k ，即要构建的划分的数目，划分方法首先创建一个初始划分。然后采用一种迭 代的复位技术，尝试通过对象在划分间移动来改进划分。一个好的划分的一般准 则是：在同一个类中的对象之间的距离尽可能小，而不同类问对象的距离尽可能 大。 为了达到全局最优，基于划分的聚类可能会要求穷举所有可能的划分。实际 上，绝大多数应用采用了以下两个比较流行的启发式方法：1 ) k - 均值算法，在该算 法中，每个簇用该簇中对象的平均值来表示：2 ) k - 中心算法，在该算法中，每个簇 用接近聚类中心的一个对象来表示。 这些启发式聚类方法容易实现，而且对在中小规模的数据库中发现球状簇很 适用，但这些方法对用户输入的参数十分敏感，而且不适用于大规模数据库的聚 类挖掘工作。 划分方法的典型代表是k m e a n s 方法、k - m e d o i d 方法、p a m 方法、c l a r a 方 法、c l a r a n s 方法等。 ( 2 ) 基于层次的方法 层次的方法是对给定数据集合进行层次的分解。根据层次的分解如何形成， 层次的方法可以被分为凝聚的或分裂的方法。凝聚的方法，也称为自底向上的方 重庆邮电大学硕士论文第一章绪论 法，一开始将每个对象作为单独的一个组，然后继续地合并相近的对象或组，直 到所有的组合并为一个( 层次的最上层) ，或者达到一个终止条件。分裂的方法，也 称为自顶向下的方法，一开始将所有的对象置于一个簇中。在迭代的每一步中， 一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个 终止条件。 为了克服聚类过程中一旦合并或分裂完成就不能撤消的问题，研究人员提出 了c u r e ，c h a m e l e o n ，以及b 取c h 算法来改进层次聚类的结果。 基于层次的聚类算法优点是：1 ) 对于大规模数据良好的伸缩性；2 ) 可以发现任 意形状的簇。其共同的缺陷是：1 ) 对用户的输入参数敏感；2 ) 对聚类数据的输入顺 序敏感；3 ) 在处理高维数据能力一般。 ( 3 ) 基于密度的方法 为了发现任意形状的聚类结果，研究人员提出了基于密度的聚类算法。其主 要思想是：只要临近区域的密度( 对象或数据点的数目) 超过某个闭值，就继续聚类。 也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须包含至少某 个数目的点。这样的方法可以用来过滤“嗓音”数据，发现任意形状的簇。 基于密度的聚类方法的优点是：1 ) 能够发现任意形状的聚类簇；2 ) 对于领域知 识的依赖较低。其缺点是：1 ) 对于用户输入的参数敏感；2 ) 对于大规模高维数据的 伸缩性较差。 代表算法有基于高密度连接区域的密度聚类方法d b s c a n ，通过对象排序识 别聚类结构的聚类方法o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) 和基于密度分布函数的聚类方法d e n c l u e ( d e n s i t y - b a s e dc l u s t e r i n g ) 。 ( 4 ) 基于模型的方法 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳匹配。 一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。 它也可以基于标准的统计数字自动决定聚类的数目，考虑“噪音”数据和孤立点， 从而产生健壮的聚类方法。 基于模型的方法主要有两类：统计学方法和神经网络方法。基于模型的聚类 方法的优点是：1 ) 对大规模数据的伸缩性较好；2 ) 对于领域知识的依赖程度低。缺 点是：1 ) 对于每一簇假定的模型对聚类结果影响较大；2 ) 对数据的输入顺序敏感。 f 5 ) 基于网格的方法 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有的聚类操作都在这个网格结构( 即量化的空m ) 上进行。这种方法的主要优 点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化窄间中每 1 维的单元数目有关。 重庆邮电大学硕士论文第一章绪论 基于网格的方法的优点：1 ) 对于大规模数据和高维数据聚类有着良好的伸缩 性；2 ) 能够发现任意形状的聚类簇；3 ) 对噪声数据不敏感。缺点：聚类结果与基础 网格结构的划分粒度有关。 基于网格方法的有代表性的例子包括：s t i n g 方法，它利用存储在网格单元 中的统计信息；w a v e c l u s t e r ：方法，它用一种小波转换方法来聚类对象： c l i q u e ( c l u s t e r i n gi nq l i e s t ) ，它是在高维数据空间中基于网格和密度的聚类方 法。 1 4 统计学中的抽样调查基本概念及术语 抽样调查是统计学的概念，它按照一定的程序，从全体调查对象中抽取一部 分进行调查，然后根据样本数据对总体目标进行估计。2 0 世纪2 0 年代起抽样调查 的基本理论逐步形成。抽样调查因其节约时间、节约花费、高正确性和应用领域 广等特性，被广泛应用于社会调查的各个领域中。 抽样调查i s , 9 1 d p 包含若干重要的概念如总体、样本、抽样方法、抽样单元以及 样本量等。 总体( 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 ) ：为使概率抽样能够实施，同时也为了具体抽样的便 利，通常将总体划分成互不重迭的若干部分。 样本量：样本中包含的样本数目。 1 5 数据挖掘中的抽样技术 1 5 1 抽样在数据挖掘中的作用 抽样技术在数据挖掘领域中主要有如下作用： ( 1 ) 提高速度和效率 速度和效率楚评价数据挖掘技术好坏的两大主要因素。数抓挖掘的速度和效 9 重庆邮电大学硕士论文第一章绪论 率取决于系统软硬件的运算能力、采用的分析工具和算法、选取数据的方法以及 数据集的特点这几个方面。合理运用抽样技术可以在保证大部分信息不丢失的同 时，提高速度、降低成本，而且由此得出的结论在统计意义上是能够让人信服的。 采用了抽样技术，数据挖掘工作者就可以把精力主要放在建立模型、选择模型上， 而不用把时间浪费在等待系统运算庞大数据的过程中。 f 2 1 帮助分析特殊性问题 所要分析问题的特点也会影响数据处理的方法。有些商业问题涉及到破坏性 的实验，显然抽取产品的- 4 , 部分来做耐用性的实验才是最经济、最有效的方法。 ( 3 ) 满足数据处理本身的需要 有时数据收集过程中的一些原因可能会造成数据库中会存在一部分无关的、 过时的、错误的或者缺省的记录。当然在进行数据挖掘之前应把这部分数据删除 掉或加以修正，即是数据挖掘中的数据清理。对整个原数据进行数据清理也许会 比较因难，比较费时费力；即使有时数据挖掘是直接在已经预处理过的数据仓库 里进行，但为了解决具体的商业问题，根据问题关于数据的一些假设对数据进行 迸一步的调整仍是必需的。 1 5 2 数据挖掘中的抽样技术与统计学中的抽样技术的比较 抽样技术最初是来源于统计学的概念，而数据挖掘与统计学之间既存在联系 又存在区别。 统计学和数据挖掘有着共同的目标：发现数据中的结构或模式。数据挖掘强 调对大量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学习， 模式识别及数据可视化等科学的边缘学科。用统计的观点，它可以看成是通过计 算机对大量的复杂数据集的自动探索性分析。 数据挖掘和统计学之间有着很大的联系，数据挖掘是建立在统计学的基础之 上。离开了统计学的基础，数据挖掘也就成了无源之水，无根之木。统计在数据 样本选择，数据预处理，数据挖掘过程及评价抽取知识的不注重有着非常重要的 作用。 但是统计学和数据挖掘两者之间也存在着较大的差异： ( 1 ) 统计学是一个非常严谨的学科，它有着较完善的理论基础和很强的数学背 景：在采用一个方法之前先要证明，而不是像计算机科学和机器学习那样注重经 验。有些时候同一问题的其他研究者提出一个很明显有用的方法，但它却不能被 证明，在统计学上则说该方法缺乏理论基础。 ( 2 ) 数据挖掘作为几门学年 的综合，己经从机器学习那里继承了实验的念度。 o 重庆邮电大学硕士论文第一章绪论 这并不意味着数据挖掘工作者不注重精确，而只是说明如果方法不能产生结果的 话就会被放弃。 ( 3 ) 统计学在对数据进行分析时，首先要建立统计模型，模型的好坏直接影响 统计推断结果，而计算、模型选择条件是次要的。相对于统计学而言，准则在数 据挖掘中起着更为核心的作用。数据点被逐一应用以更新估计量的适应性和连续 性。尽管一些统计学的准则已经得到发展，但更多的应用还是机器学习。 ( 4 ) 处理数据的规模上也有所不同。在统计中所认为的大型数据集在数据挖掘 者的眼中就显得微不足道。由于处理数据规模的巨大差异，使一些成熟的统计方 法和技术不能直接应用到数据挖掘中去。 ( 5 ) 很多情况下，数据挖掘的本质是很偶然的发现非预期但很有价值的信息、 这说明数据挖掘过程本质上是实验性的。这和统计学是不同的，统计属于确定性 分析的一种。确定性分析着眼于最适合的模型一建立一个推荐模型，这个模型也 许不能很好的解释观测到的数据。数据挖掘分析的任务是找出数据之间的特征， 规律，联系而不是验证。 ( 6 ) 统计学关心的是如何对数据进行选择，以及用己有统计模型来描述具体问 题。而数据挖掘是一种探索性的过程，它操作的对象是已收集到的数据，目的是 如何采用合适的算法和结构来从中发现知识。 ( 7 ) 统计学很少会关心实时分析，然而数据挖掘问题常常需要这些。 ( 8 ) 统计学往往处理的对象是数字型的数据，而数据挖掘还可以处理非数字型 的数据。 正由于这些原因导致了数据挖掘中的抽样技术与统计学中的抽样技术既相互 联系又相互区别的关系。 数据挖掘中的抽样技术是以统计学中的抽样技术为基础，它们的基本概念以 及基本理论相通。此外，由于下面几点原因，使得它们又相互区别： ( 1 ) 问题发生的起点不同 在统计学中，总体中的数据可能仅有一小部分是可以获得的，抽样在很多情 况下是获得总体信息的唯一办法。而在数据挖掘中，总体数据是存在的，但困难 是怎么去研究这些数据。 ( 2 ) 目的不同 数据挖掘中的抽样主要是以下三个目的：1 ) 克服计算机硬件设备的限制；2 ) 降低学习算法的复杂度；3 1 在适当降低正确性的情况f ，加快学习的速度。统计中 抽样的目的是推算总体的属性。 ( 3 ) 在样本上将进行不同的分析操作 在数据挖掘中，数据挖掘算法将用样本取代总体泉获取知识；在统计中，样 重庆邮电大学硕士论文 第一章绪论 本是用来推测未知总体的有用特性。 因此，并不是所有统计学中的抽样策略都可以应用在数据挖掘中；同时对于 小同的挖掘目的和领域需要采用不同的抽样策略才能获得较好的挖掘效果。 1 5 3 抽样在数据挖掘中应用的研究现状 鉴于抽样技术的优点以及与数据挖掘技术的密切联系，近些年来一些研究学 者在分别在分类领域、关联规则领域以及聚类领域中开展了抽样技术应用和研究， 并取得了一定的成果。 ( 1 ) 关联规则领域 将抽样方法应用于关联规则的挖掘是p b t o i v o n e n 在文【1 0 】中首先提出的。该文 提出了一种基于抽样的关联规则发现算法，该算法仅需要对数据集完整扫描一遍 就可以发现几乎所有的关联规则。该算法的基本原理是，获得一个随机的样本， 在这个样本上发现关联规则，并把发现的关联规则当作总体数据集的规则，然后 再用数据集中剩余的数据来验证这些规则。在一般情况下，该算法对整个数据集 进行一遍扫描就可以发现所有的关联规则。 文 1 l 】提出的f a s t ( f i n d i n ga s s o c i a t i o n sf r o ms a m p l e dt r a n s a c t i o n s ) 算法，也是 一种基于抽样的两阶段的关联规则发现算法。在第一阶段，f a s t 算法首先抽样生 成数据样本，并根据数据样本快速地估计数据集中每个数据项的支持度；在第二 阶段。使用估计得到的数据项的支持度，在初始的样本中对“离群”数据进行裁 剪或者选择更具有代表性的数据，并形成最终样本，该样本能够正确反映整个数 据集合的统计特性。最后，在这个样本数据集上实现关联规则的发现。 t o i v o n e n 根据c h c m o f f 边界确定出的样本容量进行随机抽样挖掘关联规则【l 们。 王春花，黄厚宽利用抽样技术分布式开采可变精度的关联规则u 4 1 。 ( 2 ) 分类领域 通常的分类方法有三种：判定树、神经网络和统计学方法，这些方法都借助 了抽样的思想，所以分类与抽样是密不可分的。 在判定树归纳算法的i d 3 版本中用到的“窗口”就是一种抽样策略。窗口用来 选定进行判定树训练的训练数据，它的形成分为两步：1 ) 从所有训练数据中随机抽 样生成一个初始窗口；2 ) 在初始窗口上生成初始决策树，使用剩余训练数据验证初 始决策树，并根据验证结果调整窗口直到获得满意的决策树。 分类中可以采用的抽样策略很多，c a t l e t t 在文【1 5 】中例举并比较了四种分类中 的抽样策略。这四种策略是简单随机抽样、压缩重复、改进窗口和分层化，其中 后三种为i # 随机抽样。压缩重复就是将每组重复的事例用一条事例柬表示；改进 重庆邮电大学硕士论文第一章绪论 窗口就是在窗口初始化时进行评估，并选择评估结果最好的窗口作为初始化窗口： 分层化就是使用分层抽样方法，目的是尽量获得连贯的数据分布。 ( 3 ) 聚类领域 抽样在聚类中的应用主要在两个方面：形成初始的簇、数据约简。 聚类中最著名与最常用的划分方法是l 卜平均和k - 中心点两种方法，它们执行的 第一步都是抽样获取k 个对象作为初始簇的中心。然后再根据相应的算法执行计 算，调节这些中心，直到不发生变化为止。聚类中的一些算法对初始簇的选择很 敏感，所以在获得初始簇的过程中，抽样策略的选择尤为重要。 抽样在聚类中也起数据约筒的作用。例如，典型的k 冲心点划分算法p a m 对小 数据集非常有效，但对大的数据集没有良好的可伸缩性，这时可以采用一个基于 抽样的方法c l a r a ( c l u s t e r i n gl a r g ea p p l i c a t i o n ) ，c l a r a 的主要思想是：不考虑 整个数据集，随机抽样实际数据的一小部分作为数据的样本，然后用p a m 方法从 样本中选择中心点。随机抽样策略产生的样本的代表性较好，所以生成的簇亦具 有代表性。 1 5 4 抽样在数据挖掘中需要考虑的问题 ( 1 ) 抽样的效率及正确性 效率和正确性都是d m 算法中最重要的因素。处理的数据越多，得到结果的正 确性就越高，但是同时却降低了效率；相反，处理的数据减少时，效率会增加， 但是却降低了正确性。d m 中通过抽样来获得结果，是以正确性换取效率的策略。 一般来说，一种抽样策略需要扫描几遍总体数据集才能得到较真实的样本数 据集。因此，在决定实施抽样以前，必须对比抽样所带来的额外开销同其所带来 的效率，避免既降低了d m 的正确性，同时又降低了效率。 ( 2 ) 样本量 样本量( 即样本大小) 是决定抽样后d m 分析的正确性和效率的重要因素之一。 样本量大，正确性高，效率低；样本量小，正确性低，效率高。总体数据集中数 据分布的特性、d m 算法、d m 算法的正确性要求程度等因素决定了样本量的需求 1 9 】。所以在确定样本量时要综合考虑以上因素。 ( 3 ) 样本的质量 样本的质量就是样本对于总体数据集的代表性。对一个给定的数据挖掘分析 方法、抽样策略和样本量，可以通过对该样本的数据状况和抽样误差来评价样本 的质量。 样本质量是衡量。个抽样柑本的重要标准。样本质肇的度量有许多种方法 重庆邮电大学硕士论文第一章绪论 通常采用统计样本质量作为度量标准。统计样本质量的基本含义就是计算抽样样 本与整体样本的相似性。 假设一数据集d 包含，个属性，s 是其中一个抽样样本集，用j = ，( s ，d ) 表示 样本集s 和数据集d 的差异： ，( s ，d ) = 以( s ，d ) ( 1 | 1 ) i = 1 其中以( s ，d ) 是k u l l b