数据仓库与数据挖掘_DBMS题库考试大纲和答案

1、1 .数据仓库的四个基本特征是指数据仓库中的数据是面向主题的、集成的、不可更新的和随时间不断变化的 。2 . OLAP的实现方式有以下两种：基于关系数据库系统的实现和基于多维数据组织 的实现。3 .数据从操作型环境到数据仓库过程中，通常需要进行的处理操作有数据X （extraction ）、转换 （transformation ）、装载 （Load）和清洗 （cleaning）。4 .数据仓库中数据的分割是指将 数据分散到各自的物理单元中去以便能分别独立处理。数据分割后的数据单元称为 分片，数据分片的类型有 水平分片、垂直分片、混合分片和导 出分片等。5 .数据仓库系统是多种技术的综合体，它是

2、由 数据仓库的前台后台工具 、数据仓库服务 壁和OLAP服务器三部分组成。6 .聚集函数分为三种类型，分别是分布型聚集函数、 代数型聚集函数 、 和整体型聚集函数 。7 .粒度是数据仓库的重要概念，粒度越 小，数据的细节程度越 直，可以回答查询的种类 就越上，但是查询效率将会很低；提高粒度将会提高查询效率， 在数据仓库中通常采用多重粒度。OLAP展现在用户面前的是一幅幅多维视图。联机分析处理维（Dimension ）:是人们观察数据的特定角度，是考虑问题时的一类属性，属性集合构成 一个维（时间维、地理维等）。维的层次（Level）:人们观察数据的某个特定角度（即某个维）还可以存在细节程度 不同

3、的各个描述方面（时间维：日期、月份、季度、年）。维的成员（Member ）:维的一个取值，是数据项在某维中位置的描述。（某年某月某日”是在时间维上位置的描述）。度量（Measure ）:多维数组的取值。（2000年1月，上海，笔记本电脑， 0000 ）。OLAP的基本多维分析操作有钻取 （Drill-up和Drill-down ）、切片（Slice）和切块（Dice）、 以及旋转（Pivot）等。钻取：是改变维的层次，变换分析的粒度。它包括向下钻取（ Drill-down ）和向上钻取（Drill-up ） /上卷（Roll-up）。Drill-up是在某一维上将低层次的细节数据概括到高层次的

4、汇总 数据，或者减少维数；而Drill-down则相反，它从汇总数据深入到细节数据进行观察或增加 新维。二 切片和切块:二是在一部分维上选定值后，二关心度量数据在剩余维上的分布。二如果剩余的 维只有两个，则是切片；如果有三个或以上，则是切块。旋转：是变换维的方向，即在表格中重新安排维的放置（例如行列互换）。:、名次解释:1 .数据集市：数据集市包含企业范围数据的一个子集，对于特定的用户是有用的。其范围 限于选定的主题。例如， 一个商场的数据集市可能限定其主题为顾客、商品和销售。包括在数据集市中的数据通常是汇总的。2 .数据仓库的元数据： 关于数据的数据第一种:从操作型环境向数据仓库环境转换而建

5、立 的元数据。包含：所有源数据项名、属性及其在数据仓库中的转换.第二种：与终端用户的多维商业模型/前端工具之间建立映射的DSS元数据3 .粒度：对数据仓库中的数据的综合程度高低的一个度量 ，粒度越小，细节程度越高，综合 程度越低，粒度大小影响数据仓库效率、能回答询问的种类 ，数据仓库是多粒度的，不同的粒 度回答不同的查询4 .分割：指将数据分散到各自的物理单元中去以便能分别独立处理。5 .聚类分析：根据数据的特征找出数据间的相似性，将相似的数据分成一个类。又称无指 导的学习，客观根据被处理对象的特征分类，将相同特征的对象归为一类。6 .数据仓库的主题： 主题是在较高层次上将企业信息系统中的数据

6、综合、归类并进行分析 利用的抽象。逻辑意义：对应企业中某一宏观分析领域所涉及的分析对象。7 .分类：分类就是按照分析对象的属性分门别类，加以定义建立类组，分类的关键是按照 什么样的标准和规律进行分类，所以分类需要先确定规则，再进行分类。分类聚类区别：分类规则需要预先定义类别和训练样本，而聚类分析直接面向数据源数据，没有预先定义类别和训练样本，所有记录都根据彼此相似程序加以归类。预测：利用历史数据建立模型，再运用新数据作为输入值，获得未来变化趋势，或评估 给定样本可能具有的属性范围。8 .序列模式分析： 给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序 有序排列，每个元素由不同项目

7、组成， 同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。9 .广义索引：预先计算出来的，用来记录具有某些特殊性质数据的索引。比如最小值，top-k值等。特点：非常小，大大提高查询效率。最流行的数据仓库数据模型是多维数据模型。这种模型可以以 星形模式、雪花模式、或事实星座模式形式存在。10 .星型模型：最常见的模型范例星形模式；其中数据仓库包括（1） 一个大的、包含大批数据、不含冗余的 中心表（事实表）；（2） 一组小的附属表（维表），每维一个。这种模 式图很象星星爆发，维表围绕中心表显示在射线上。sale

8、s事实表item舞表11 . OLAP中的维和维层次：观察数据的角度、程度不同分层。12 .雪片模型：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。 结果，模式图形成类似于雪花的形状。雪花模式和星形模式的主要不同在于，雪花模式的维表可能是规范化形式，以便减少冗余。这种表易于维护，并节省存储空间，因为当维结构作为列包含在内时，大维表可能非常大。11nte推表e止日军买强血亚琳强,呼Pr推表-值频繁地在给定数据集中一起13 .关联分析：关联分析发现关联规则，这些规则展示属性 出现的条件。关联分析广泛用于购物篮或事务数据分析。1 .操作型数据和分析型数据的主要区

9、别是什么？答：OLTP和OLAP的主要区别如下：用户和系统的面向性， OLTP是面向顾客的，用于办事员、客户和信息技术人员到额事务和查询处理，而 OLAP是面向市场的，用于知识工人的数据分析。从数据内容上区别，OLTP是当前数据，通常这种数据太琐碎，难以方面地用于决策，OLAP系统管理大量的历史数据，提供汇总和汇聚机制，并在不同的粒度级别上存储和管理信息。这些特点使得历史数据容易用于见多识广的决策。从数据库设计上，通常 OLTP采用实体-联系模型和面向应用的数据库设计。而OLAP系统通常采用星型或者雪花模型和面向主题的数据库设计。从视图上区别：OLTP系统主要关注一个企业或者部门内部的当前数据

10、，而不涉及历史数据 或不听组织的数据，相比之下，由于组织的变化，OLAP系统常常跨越数据库模式的多个版本，OLAP系统也出来来自不同组织的信息，由多个数据存储集成的信息，由于数据量巨大，OLAP数据页存放在多个存储介质上。访问模式：OLTP系统的访问主要由短的原子事务组成，这种系统需要并行控制和恢复机制，然而对OLAP系统的访问大部分是只读操作，尽管许多查询是复杂的查询。L操作型分析型效据 细节的筹含的.或置母的在存展牖间，净礴的代表讨夫的殴橱可更新不更新幄和窝笊轮可知他操作需求事苑不知遒生脩周期符合SDLC克至不同的生命周明对性旄费求高附性能要求宽松一个时为一单元f时期操作带嬖动.分折胆动此

11、向应用面向分析一次操作数16量小一次操作数据量大芨持日常报祚支持瞥理需求2 .你是如何理解数据仓库的数据是不可更新的，数据仓库的数据又是随时间不断变化的。 数据仓库中的数据不可更新是针对应用而言的，用户进行分析处理时是不进行数据更新操作的.数据仓库的数据是随时间的变化不断变化的，随时间变化不断增加新的数据内容，随时间变化不断删去旧的数据内容。数据仓库中包含有大量的跟时间有关的综合数据， 经常按照时间段进行综合，随着时间的变化不断地进行重新综合。3 .举例说明数据仓库有哪三类聚集函数。(1)分布的：一个聚集函数是分布的，如果它能以如下分布方式进行计算：设数 据被划分为n个集合，函数在每一部分上的

12、计算得到一个聚集值。如果将函数用于n个聚集值得到的结果，与将函数用于所有数据得到的结果一样，则该函数可以用分布方式 计算。例如，count()可以这样计算：首先将数据方分割成子方的集合，对每个子方计算 count(),然后对这些子方得到的计数求和。因此，count()是分布聚集函数。 同理，sum(),min()和max()是分布聚集函数。一个度量是分布的，如果它可以用分布聚集函数得到。(2)代数的：一个聚集函数是代数的，如果它能够由一个具有 M (其中，M是一 个整数界)个参数的代数函数计算，而每个参数都可以用一个分布聚集函数求得。例如，avg()可以由sum()/count()计算，其中s

13、um()和count()是分布聚集函数。类似地，可以表 明min_N(), max_N()和standard_deviation()是代数聚集函数。 一个度量是代数的，如果它可以用代数聚集函数得到。(3)整体的：一个聚集函数是整体的，如果描述它的子聚集所需的存储没有一个 常数界。即，不存在一个具有 M个(其中，M是常数)参数的代数函数进行这一计算。 整体函数的常见例子包括median(),mode()(即，最常出现的项)，和rank()。一个度量是整体的，如果它可以用整体聚集函数得到。大部分数据方应用需要有效地计算分布的和 代数的度量。对于这些，存在许多有效的技术。相比之下，有效地计算整体度量

14、是很困 难的。然而，对于有些整体函数的近似计算，有效的技术是存在的。4 .为什么说 naive Bayesian分类法是 na?Ve的?朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值。该假定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”。5 .请简述数据仓库的体系结构。a）数据仓库的后台工具b）数据仓库服务器c） OLAP服务器d） 前台工具n；ktaA IVIulti-Tiered AivhitectuiviI*'- "hi! itaCesratarDis Mmi t Mira4i Tr-iiiaf«tn Lc41d Reia

15、eitATHljTiisQ忙门Rep mt$口ai 日 miningflData Sourees Dti Storage口LAP 日咂h亡 FrcuM-End Tools6 .举例说明多维分析操作（drill-down , roll-up）的含义是什么?saleprodikdstore Iddat»amip1c1112p1ci111ple3150P?C21Bpid244Plq22境saleprod Iddateamtpl162成1J9P124Brollupdrill-down（Vwaqvw.Qlj 安全）计置机馥1计H机安坐电话 ifafeni在bftlt上_1_卷一个通常用于数据仓

16、库多维数据方，（a）展示AllElectronics的汇总数据（b）展示数据方（a）上的下钻与上卷结果。7 .举例说明数据仓库有哪三类聚集函数（同3）8 .试述常用的数值属性离散化方法等宽：每个bin的距离间隔一样。等深：每个bin所具有的元组的数目相等。等质：bin的大小决定后，每一个 bin中的元组是统一分布的9 .向数据仓库追加数据时，捕捉数据变化常用的途径有哪些？数据追加：数据仓库白数据初装完成后，再向数据仓输入数据的过程追加内容：上次数据追加后在OLT啖据库中变化了的数据变化数据的捕捉途径：1）时标方法（如果数据含有时标，对新插入或更新的数据记录，加更新时的时标）2） DELTA文件

17、（由应用生成DELTAS件，记录应用所改变的所有内容）3）前后映象文件（抽取数据到数据仓库之后，本次将抽取数据之前，对数据库分别作一次快照，比较两幅快照的不同，确定追加的数据）4）日志文件（利用 DB的固有机制，数据只限于日志文件，不用扫描整个数据库）10 .试述数据仓库的设计中提高数据仓库性能的方法和技术？由于数据仓库的数据极少甚至不再更新，可采取如下技术来提高数据仓库的性能：11 .简要说明事务处理环境不适宜DSS应用的原因？操作型处理也叫事务处理，是指对数据库联机的日常操作，通常是对一个或一组记录的查询和修改，主要是为企业的特定应用服务的，人们关心的是响应时间，数据的安全性和完整性。分析

18、型处理则用于管理人员的决策分析。例如：DSS （决策支持系统），EIS （主管信息系统）和多维分析等，经常要访问大量的历史数据。事务处理环境不适宜 DSS应用的原因：（1）事务处理和分析处理的性能特性不同（在事务处理环境中，数据的存取操作频率高而每次操作处理的时间短，在分析处理环境中，DSS应用需要运行时间长，消耗系统资源多.）（2）数据集成问题（DSS需要的数据：全面、集成、相关数据收集得越完整结果就越可靠）（3）数据动态集成问题（事务处理的数据： 与本部门业务有关当前数据，对整个企业范围内 的集成应用考虑少，当前企业内数据的状况a.分散而非集成一一这是事务处理环境所固有的 b.事务处理应用

19、产生的细节数据不能成为统一的整体c.DSS应用必须在应用程序中进行数据集成）（4）历史数据问题（事务处理系统中的数据：当前数据及短期数据；决策分析的数据：必 须要历史数据）（5）数据的综合问题（DSS系统的分析对象：一般不对细节数据进行分析，分析前需要对细节 数据进行不同程度的综合.事务处理系统的对象：只关心细节数据，不具备综合能力，综合是一种数据冗余，需要加以限制）12 .数据仓库的设计方法与操作型环境中系统设计采用的系统生命周期法有什么不同？SDLC操作型环境中，业务过程和规则比较规范和固定。系统设计人员能够清晰地了解应用 的需求和数据流程，系统的设计一般采取系统生命周期法（Systems

20、 Development Life Cycle）CLDS分析型环境中，DSS分析对决策分析的需求不能预先作出规范说明，只能给设计人员 一个抽象模糊的描述。设计人员必须在与用户不断的交流中，将系统需求逐步明确与完善。为了强调这种开发的不确定型，将此设计方法定名为CLDS方法（与SDLC相反）SDLC与CLD5方,法比较鱼!5C LDS13 .举例说明多维分析操作（切片、切块、旋转）的含义是什么？切片和切块：切片操作在给定的数据方的一个维上进行选择，导致一个子方。图2.10图示了一个对维time的切片操作，它对中心数据方使用条件time = "Q1”选择销售数据。切块操作通过对两个或多个

21、维执行选择，定义子方。图2.10图示了一个切块操作，它涉及三个维，根据如下条件对中心表切块：（location = " Montreal 0r ' Vancouver" a"d （time = 'Q1"or "Q2" a nd （item = " homeentertainmentor "" computer。"）转轴：转轴（又称旋转）是一种目视操作，它转动数据的视角，提供数据的替代表示。 图2.10 给出一个转轴操作， 这里item和location在一个2-D切片上转动。其它

22、例子包括转动3-D数 据方，或将一个3-D立方转换成2-D平面序列。14 .数据挖掘的步骤是什么？数据挖掘作为KDD （知识发现）的一个步骤。KDD是一个以知识使用者为中心，人机交互的探索过程，包括了在指定的数据库中用数据 挖掘算法提取模型，以及围绕数据挖掘所进行的预处理和结果表达等一系列的步骤。瓯】辖驻据费看作KDD的一个净一15 .简要说明数据仓库环境中元数据的内容。元数据是关于数据的数据 。在数据仓库中，元数据是定义仓库对象的数据。对于给定数据仓库的数据名和定义，创建元数据。其它元数据包括对提取数据添加的时间标签、提取数据的源、被数据清理或集成处理添加的字段等。16 .企业的数据库体系化

23、环境的四个层次是什么？它们之间的关系是什么？层次的体系化环境四个层次分别为：操作型环境、全局级数据仓库、部门级的局部仓库、个人级数据仓库。操作型环境存放：细节的操作型数据，服务于高性能事务处理全局级数据仓库：存放细节数据、导出数据部门级局部仓库：一般存放导出数据个人级数据仓库：数据一般是暂时存放，用于启发式分析。探件型环境|金碗 副演"一 王式鹫掾作型坏盘 斗|仝局仓床|* 部门仓& 1 饪k仓囱任：口 一 “蠹小 i Kiss 的扬|aH.17 .简要说明数据仓库设计的步骤。数据仓库的设计方法：CLDS方法（与SDLC相反）参考12题18 .简要说明异常点挖掘有哪些方法？一

24、定普代定布 二二有替代分布 飞：温含静代外粘异常点挖他方法框于承元的罪法,台值离模型V就靛图W守密点花就其法纣兖19 .什么是元数据？简要说明数据仓库环境中元数据的内容。（参考15）20 .你是如何理解数据仓库的数据是不可更新的，数据仓库的数据又是随时间不断变化的。答：数据仓库存放的数据都是历史数据，基本操作都是查询操作，一般情况下并不进行修改操作，数据一旦超过存储期限是可以删除的。数据仓库随时间变化不断增加新的数据内容，并且存在大量和时间有关的综合数据，数据仓库数据的码键都包含时间项，以标明数据的历史时期。21 .什么是数据驱动的系统设计方法？（参考 12）22 .试简述数据仓库的体系结构（

25、参考4）23 .简述采用决策树方法进行分类的过程。1）基本算法（贪婪算法）由上到下，分而治之，递归构造树开始时，所有的训练样本都在树根属性都是可分类的属性（如果是连续值的话，首先要对其进行离散化）根据选择的属性，对样本递归地进行划分在启发式或统计度量（如information gain） 的基础上选择测试属性2）停止划分的条件某个节点上的所有样本都属于相同的类所有的属性都用到了-这时采用多数有效的方法对叶子节点进行分类没有样本了24请简述采用神经元网络进行分类的过程。在开始训练之前，用户必须说明输入层的单元数、隐藏层数（如果多于一层）、每一隐藏层的单元数和输出层的单元数，以确定网络拓扑。定义网

26、络拓扑向传播算法学习过程：迭代地处理一组训练样本，将每个样本的网络预测与实际的类标号比较。每次迭代后，修改权值，使得网络预测和实际类之间的均方差最小25举一个实例说明如何确定数据仓库的主题，如何确定主题所应包含的数据内容？数据仓库中的数据是面向主题进行组织的主题 是在较高层次上将企业信息系统中的数据综合、归类并进行分析利用的抽象逻辑意义：对应企业中某一宏观分析领域所涉及的分析对象面向主题的数据组织步骤1、 抽取主题: 按照分析的要求来确定2、 确定每个主题所应包含的数据内容例如：商场商品采购1）在OLTP数据库中，“订单” “订单细则”“供应商”三个数据库模式清晰完整地描述了一笔采购业务所涉及

27、的数据内容, 这是面向应用来进行数据组织的方式；2）在数据仓库中,主要是进行数据分析处理, 商品采购时的分析活动主要是要了解各供应商的情况 , “供应商”是采购分析时的分析对象。所以不需要组织象“订单”和“订单细则”这样的数据库模式，因为它们包含的是纯操作型的数据；但是仅仅只用OLTP数据库的“供应商”中的数据又是不够的 , 因而要重新组织“供应商”这么一个主题。26举例说明数据仓库的多粒度。粒度对数据仓库中的数据的综合程度高低的一个度量粒度越小，细节程度越高，综合程度越低， 粒度大小影响数据仓库效率、能回答询问的种类，数据仓库是多粒度的，不同的粒度回答不同的查询实际：两种形式的粒度都存在例：

28、 “商品”主题表的划分：销售综合表和采购综合表是属于第一种形式的粒度（时间段上信息的综合）库存信息的不同表：则属于第二种形式粒度划分（不同时点上的粒度）27举例说明什么是“星星模式”。 （名词解10）28常用的聚类方法有哪些？（1）划分方法（ 2）层次方法（ 3）基于密度的方法（ 4）基于网格的方法(5)基于模型的方法四、计算题:1 .现有如下事务数据库，设min sup = 60%, min conf = 80%.请用Apriori算法找出所有的频繁项目集。扫描口对每个候选计数集 口J3J40 口"1515) 页 1 11L.22-I T1 I W1 I I I _I I I fl

29、 n -JI fl- ft ft- fl ix ft J11方127g6蚓21_21项集支持度计麴HJ2J4HJ3J4口1刊12UI34IWJ212,15)201X151(4,1510扫描D,对每个候选计数1支持度计数1比较候选支持度计数HJ2与是小支持度计数山4*-(11,15)2UI3I2J4LL_1L史由L2产生 候选。3C3项集支持度讨数ILI2J322面也I扫描口对每 一如晟个候选i+数11,12 I 口回|项集支持度计数(1143,13HJ2J5J22叱莪候选支持度计数 与最小支持度计数TIDLhl of iltm IDS1100T2CI0T3(IO T400T500T600 17

30、00TS00T900riJ2.15 12J4 I2J3 riJ2.M Il.B 12J3 I LB rLI2.B.I5 11,12,132 .请根据能找出的cluster的形状、预先指定的参数、所存在的缺陷这三个方面对如下聚类 方法进行评价：1 . K-MeansK-Mean分群法是一种分割式分群方法，其主要目标是要在大量高纬的资料点中找出具有代表性的资料点；这些资料点可以称为群中心，代表点；然后再根据这些群中心，进行后续的处理，这些处理可以包含1 )资料压缩：以少数的资料点来代表大量的资料，达到资料压缩的功能；2 ）资料分类：以少数代表点来代表特点类别的资料，可以降低资料量及计算量；2.实现

31、k-means算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同 一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所 获得一个 中心对象”（引力中心）来进行计算的。k-means算法的工作过程说明如下： 首先从n个数据对象任意选择 k个对象作为初始聚类中心； 而对 于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数.k

32、个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。K-means算法的特点采用两阶段反复循环过程算法，结束的条件是不再有数据元素被重新分配： 指定聚类即指定数据到某一个聚类，使得它与这个聚类中心的距离比它到其它聚类中心的距离要近。 修改聚类中心优点：本算法确定的 K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效 果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为O（NKt）,其中N是数据对象的数目，t是迭代的次数。一般来说，K<<N, t<<N。缺点： 在K-means算法中K是事先给定的，这个 K值的选定是非

33、常难以估计的。很多时候，事先并不知道 给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K,例如ISODATA算法。关于K-means算法中聚类数目K值的确定在文献中，是根据方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分燧来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵的RPCL算法，并逐步删除那些只包含少量训练数据的类。而文献中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类的适当数目。它的 思想是：对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采

34、用惩罚的方 法使之远离输入值。在K-means算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA）,例如文献中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的 聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。 所以需要对算 法的时间复杂度进行分析、 改进，提高算法应用范围。在文

35、献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉 聚类中心的侯选集。而在文献中，使用的 K-means算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛 速度。2 . BIRCHBIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的 聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两

36、个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数，而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类， 非叶子结点为它的子女的最大关键字，可以根据这些关键字进行插人索弓I,它总结了其子女的信息。聚类特征树可以动态构造，因此不要求所有数据读人内存，而可以在外存上逐个读人。新的数据项总是插人到树中与该数 据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T,则把该叶子节点分裂。 其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类

37、直径修改特征树 大小，控制其占内存容量。BIRCH算法通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。对于给定的M兆内存空间，其空间复杂度为O(M),时间间复杂度为 O(dNBlnB(M/P).其中d为维数,N为节点数，P为内存页的大小，B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只 适用于类的分布呈凸形 及球形的情况，并且由于 BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。3 DBSCANDBSCANB法即基于密度的聚类算法。该算法利用类的密度连通性可以快速发现任意形状的类。其基本思想是： 对于一个类中的每个对象，在其给定

38、半径的领域中包含的对象不能少于某一给定的最小数目。在 DBSCAN算法中， 发现一个类的过程是基于这样的事实：一 个类能够被其中的任意一个核心对象所确定。为了发现一个类，DBSCANfc从对象集D中找到任意一对象 P,并查找D中关于关径Eps和最小对象数 Minpts的从 P密度可达的所有对象。如果P是核心对象，即半径为 Eps的P的邻域中包含的对象不少于Minpts,则根据算法，可以找到一个关于参数Eps和Minpts的类。如果P是一个边界点，则半径为 Eps的P邻域包含的对象少于Minpts, P被暂时标注为噪声点。然后，DBSCANb理D中的下一个对象。密度可达对象的获取是通过不断执行区

39、域查询来实现的。一个区域查询返回指定区域中的所有对象。为了 有效地执行区域查询，DBSCANB法使用了空间查询 R树结构。在进行聚类前，必须建立针对所有数据的 R*-树。另外，DBSCAN要求用户指定一个全局参数Eps(为了减少计算量，预先确定参数 Minpts)。为了确定取值，DBSCAN计算任意对象与它的第 k个最临近的对象之间的距离。然后，根据求得的距离由小到大排序，并绘出排序后的图，称做k-dist 图。 k-dist 图中的横坐标表示数据对象与它的第k 个最近的对象间的距离；纵坐标为对应于某一 k- dist距离值的数据对象的个数。R*-树的建立和k-dist图的绘制非常消耗时间。此外，为了得到较好的聚类结果，用户必须根据 k-dist图，通过 试探选定一个比较合适的Eps值。DBSCAN算法不进行任何的预处理而直接对整个数据集进行聚类操作。当数据量非常大时，就必须有大内存量支持，I/O 消耗也非常大。其时间复杂度为O(nlogn)(n 为数据量)，聚类过程的大部分时间用在区域查询操作上。DBSCAN法对参数Eps及Minpts非常