数据挖掘与数据仓库-知识点总结.doc

1、数据仓库定义：数据仓库是一种新的数据处理体系结构,它与组织机构的操作数据库分别维护，允许将各种应用系统一起，为统一的历史数据分析提供坚实的平台，对信息处理提供支持。数据仓库是面向主题的、集成的、相对稳定的、反映历史变化的数据集合，为企业决策支持系统提供所需的集成信息。设计和构造步骤:1）选取待建模的商务处理;2)选取商务处理的粒变；3）选取用于每个事实表记录的维；4)选取事实表中每条记录的变量系统结构:(1)底层是仓库数据服务器,总是关系数据库系统.（2)中间层是OLAP服务器,有ROLAP和MOLAP，它将对多维数据的操作映射为标准的关系操作（3）顶层是前端客户端，它包括查询和报表工具、分析工具和数据挖掘工具2、数据仓库的多维数据模型：（1）星形模式:在此模型下，数据仓库包括一个大的包含大批数据并且不含冗余的中心表，一组小的附属表，维表围绕中心事实表显示的射线上.特征:星型模型四周的实体是维度实体，其作用是限制和过滤用户的查询结果,缩小访问范围。每个维表都有自己的属性，维表和事实表通过关键字相关联。【例子：sales数据仓库的星形模式,此模式包含一个中心事实表sales，它包含四个维time, item， branch和location。（2）雪花型模式：它是星形模式的变种,其中某些维表是规范化的，因而把数据进一步分解到附加的表中.特征：雪花模型通过最大限度地减少数据存储量和联合较小的维表来改善查询性能，增加了用户必须处理的表数量和某些查询的复杂性，但同时提高了处理的灵活性,可以回答更多的商业问题，特别适合系统的逐步建设要求。【例子同上，只不过把其中的某些维给扩展了。（3)事实星座形:复杂的应用可能需要多个事实表共享维表,这种模式可看作星形模式的汇集。特征：事实星座模型能对多个相关的主题建模。例子：有两个事实表sales和shipping，它们可以共享维表time， item和location。3、OLAP：即联机分析处理，是在OLTP基础上发展起来的、以数据仓库基础上的、面向高层管理人员和专业分析人员、为企业决策支持服务。特点:1.实时性要求不是很高。2。数据量大。3。因为重点在于决策支持，所以查询一般是动态的，也就是说允许用户随机提出查询要求.OLAP操作：上卷:通过沿一个维的概念分层向上攀登，或者通过维归约，对数据立方体进行类聚。下钻:是上卷的逆操作，它由不太详细的数据得到更详细的数据，下钻可以通过沿维的概念分层向下或引入附加的维来实现。切片：对给定方体的一个维进行进行选择，导致一个子立方体。切块：通过对两个或多个维执行选择，定义子立方体。转轴：是一种可视化操作,它转动数据的视角,提供数据的替代表示。OLTP:即联机事务处理,是以传统数据库为基础、面向操作人员和低层管理人员、对基本数据进行查询和增、删、改等的日常事务处理。OLTP的特点有：a.实时性要求高；b。数据量不是很大.C.交易一般是确定的，是对确定性数据进行存取。d.并发性要求高且严格的要求事务的完整性，安全性。OLTP和OLAP的区别：1）用户和系统的面向性:OLTP面向顾客，而OLAP面向市场;2）数据内容：OLTP系统管理当前数据,而OLAP管理历史的数据；3）数据库设计：OLTP系统采用实体联系（ER）模型和面向应用的数据库设计，而OLAP系统通常采用星形和雪花模型；4)视图：OLTP系统主要关注一个企业或部门内部的当前数据,而OLAP 系统主要关注汇总的统一的数据；5)访问模式：OLTP访问主要有短的原子事务组成，而OLAP系统的访问大部分是只读操作，尽管许多可能是复杂的查询。7、PageRank算法原理：1)在初始阶段：构建Web图，每个页面初始设置相同的PageRank值，通过迭代计算,会得到每个页面所获得的最终PageRank值.2）在一轮中更新页面PageRank得分的计算方法：每个页面将其当前的PageRank值平均分配到本页面包含的出链上。每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。优点：是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量,极大降低了查询响应时间。缺点：1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低.2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。5、分类：指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类.过程：在已知训练数据集上，根据属性特征,为每一种类别找到一个合理的描述或模型,即分类规则；然后根据规则对新数据进行分类。分类的方法有哪些，给出你所了解的评估分类器的方法和特点?分类方法：用基于归纳的学习算法，k-最近邻分类，人工神经网络法、粗糙集法和遗传算法。用判定树归纳分类；贝叶斯分类；后向传播分类；基于规则的分类;关联分类，SVM支持向量机等。分类和预测的评估方法：预测的准确率、速度、强壮性、可规模性、可解释性。评估方法：（1）保持方法，给定数据随机地划分成两个独立的集合:训练集和测试集.通常，三分之二的数据分配到训练集,其余三分之一分配到测试集.使用训练集导出分类法，其准确率用测试集评估.评估是保守的,因为只有一部分初始数据用于导出的分类法.(2）交叉确认：在k-折交叉确认中,初试数据被划分成 k 个互不相交的子集或“折S 1，S 2，.。.,S k,每个折的大小大致相等。训练和测试进行 k次。在第 i次迭代，S i用作测试集，其余的子集都用于训练分类法。其它方法包括解靴带(bootstrapping）和留一。前者使用一致的、带放回的选样，选取给定的训练实例；后者是 k-折交叉确认，这里 k 为初始样本数 s。一般地，建议使用调整的 10折交叉确认，因为它具有相对低的偏置和方差.（3)袋装：给定 s 个样本的集合 S,对于迭代 t （ t = 1,2,。，T ），训练集 S t采用放回选样，由原始样本集 S 选取。由于使用放回选样,S 的某些样本可能不在 St中，而其它的可能出现多次。由每个训练集 S t学习，得到一个分类法 C t.为对一个未知的样本 X 分类,每个分类法 C t返回它的类预测,算作一票。装袋的分类法 C统计得票，并将得票最高的类赋予 X。通过取得票的平均值,而不是多数，装袋也可以用于连续值的预测。(4）推进：每个训练样本赋予一个权。学习得到一系列分类法。学习得到分类法 Ct后,更新权，使得随后的分类法 C t+1 “更关注 C t的分类错误.最终的推进分类法 C组合每个分类法的表决,这里每个分类法的表决是其准确率的函数。推进算法也可以扩充到连续值预测。应用领域:是数据挖掘领域中研究和应用最为广泛的技术之一，许多分类算法被包含在统计分析工具的软件包中,作为专门的分类工具来使用。分类问题在商业、银行业、生物学、文本挖掘、因特网筛选等领域都有广泛应用.例如在因特网筛选中,分类方法可以协助网络工作人员将正常邮件和垃圾邮件进行分类，从而制定有效的垃圾邮件过滤机制，防止垃圾邮件干扰人们的正常生活。8、决策树归纳算法及其优缺点决策树定义:是用样本的属性作为结点,用属性的取值作为分支的树结构.它是利用信息论原理对大量样本的属性进行分析和归纳而产生的。决策树的根结点是所有样本中信息量最大的属性。树的中间结点是以该结点为根的子树所包含的样本子集中信息量最大的属性.决策树的叶结点是样本的类别值。归纳算法过程：创建节点N,若划分D中所有元组属于同一个类C，返回N，并用C标记若属性表为空，返回N并以D中多数类标记 从属性表中找到最优属性a，标记节点N 如果a是离散的且允许多路划分，则从属性表中删除a 对属性a在D上的每个划分Dj,若Dj为空，则加一个树叶到N并标记D中的多数类,否则递归调用本算法处理Dj，返回的节点加到N 返回N优点:更高的准确性可以生成可理解的规则计算量不是很大可以处理连续和种类字段可以清晰显示哪些字段比较重要容易转化成分类规则:只要沿着树根向下一直走到叶子,沿途的分裂条件就能够唯一的决定一条分类的谓词缺点:缺乏伸缩性，由于进行深度优先搜索，所以算法受内存大小限制，难于处理大训练集为了处理大数据集的种种算法（离散化、取样)不仅增加了分类算法的额外开销，而且降低了分类的准确性。6。聚类分析的功能，主要的聚类方法及其特点。聚类:【不知道数据的分类,甚至连分成几类也不知道】将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类.由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。是无指导的学习。聚类与分类的主要区别：和分类学习相比，聚类的样本没有标记，需要由聚类学习算法来自动确定.聚类分析是研究如何在没有训练集的条件下把样本划分为若干类.在分类中,对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。主要的聚类方法：1)划分方法:给定n个对象或数据元组的数据库,划分方法构建数据的K个划分，每个划分表示一个簇，k=n。构建不同划分.如K均值、K中心点算法等。缺点是需要穷举所有可能划分，适用于中小规模数据库2） 层次方法：对给定数据库对象进行层次分解，如Diana，Agnes、BIRCH、ROCK、CAMELEON等，缺点在于一旦一个步骤（合并或分裂）完成,就不能撤销3） 基于密度的方法.基于连接和密度函数,如DBSCAN和OPTICS4） 基于网格的方法，基于多层粒度函数，如STING、WaveCluster、CLIQUE等，把对象空间量化为有限个单元,形成网格结构,聚类都在网格上进行。处理速度快，处理时间依赖于量化空间每一维的单元数目5） 基于模型的方法,为每个簇假定一个模型，寻找数据对给定模型的最佳拟合,如EM、SOM、COBWEB算法等6） 基于频繁模式的聚类:从频繁出现的维数自己中提取不同的频繁模式。7） 基于约束的聚类：结合用户指定或面向应用的约束进行聚类.应用领域：是数据挖掘应用的主要技术之一，它可以作为一个独立的工具来使用，将未知类标号的数据集划分为多个类别之后,观察每个类别中数据样本的特点，并且对某些特定的类别作进一步的分析。此外，聚类分析还可以作为其他数据挖掘技术(例如分类学习、关联规则挖掘等）的预处理工作。4、人工神经网络：是一个函数,主要在于这个函数的自学习过程，在学习过程中,它根据正确结果不停的校正自己的网络结构.分类方法:1.依学习策略分类主要有：监督式学习网络为主、无监督式学习网络、混合式学习网络、联想式学习网络、最适化学习网络2。依网络架构分类主要有:前向式架构、回馈式架构、强化式架构优点:预测准确性高、对噪声数据的高承受力(训练样本差错时仍可工作）、输出离散值、快速评估目标 缺点：1、需要很长的训练时间 2、难以与域知识合作3、可解释性差BP网络：是一种按误差逆传播算法训练的多层前馈网络。BP网络能学习和存贮大量的输入输出模式映射关系,而无需事前揭示描述这种映射关系的数学方程。BP算法由数据流的前向计算(正向传播)和误差信号的反向传播两个过程构成。BP神经网络的学习过程：神经网络在外界输入样本的刺激下不断改变网络连接的权值，阈值。以使网络的输出不断地接近期望的输出.学习的本质：对各连接权值、阈值的动态调整。学习规则：权值、阈值调整规则,即在学习过程中网络中各神经元的连接权变化所依据的一定的调整规则BP学习算法的步骤: 选定学习的数据，p=1，,P， 随机确定初始权矩阵W(0）；用学习数据计算网络输出；反向修正，直到用完所有学习数据。BP神经网络算法步骤:1初始化，依据实际问题给出网络连接结构,随机设置所有连接权值。2提供训练样本，如果输入变量为n个,输出变量为m个，则每个训练样本形式为（x1,x2，xn;t1,t2，,tm）。这里t1，t2，tm是输入为x1,x2,，xn的期望输出。3计算实际输出，利用非纯属函数逐级计算各层节点的输入值。4权值调整，用递归方法从输出节点开始返回到隐层节点。5返回第二步，重复执行,直到达到满意误差。BP网络的缺点：易陷入局部最小点;收敛速度慢;学习过程容易出现震荡；9、提升Adaboost：在提升方法中，权重赋予每个训练元组。迭代地学习k个分类器序列。学习得到分类器Mi之后，更新权重，使得其后的分类器Mi+1“更关注”Mi误分类的训练元组。最终提升的分类器M组合每个个体分类器，其中每个分类器投票的权重是其准确率的函数。过程：给定数据集D,包含d个类标记的元组(X1,y1）,(X2，y2）,，（Xd，yd），其中，yi是元组Xi的类标号.Adaboost对每个训练元组赋予相等的权重1/d。在第i轮中:从D中元组抽样，形成大小为d的训练集Di。每个元组被选中的机会由它的权重决定。从训练元组Di导出分类模型Mi。使用Di作为检验集计算Mi的误差。调整训练元组D的权重：如果元组不正确地分类，则它的权重增加。如果元组正确分类，则它的权重减少。元组的权重反应对它们分类的困难程度权重越高,越可能错误地分类。分类器使用这些权重产生下一轮的训练样本。如果分类器Mi的性能太差，误差率超过0.5，则丢弃它。AdaBoost算法的优点：一是训练的错误率上界，随着迭代次数的增加,会逐渐下降；二是adaboost算法即使训练次数很多，也不会出现过拟合的问题。10、DBSCAN算法的特点和算法描述DBSCAN 原理:（具有噪声的基于密度的聚类应用)，这类方法将簇卸任是数据空间中被低密度区域分割开的稠密数据对象区域。它将簇定义为密度相连的点的最大集合。可在具有噪声的空间数据库中发现任意开关的聚类。基于密度的簇是基于密度可达性的密度相连的点的最大集合。算法描述:(1）任选一未处理过的点p为种子点；(2)如果p为核心对象,则查找点p直接密度可达的点，将其中未标记的点标记簇标号，并且将未处理的其它核心点加入种子列表；否则，转到(1）;(3） 将种子列表的点依次执行操作（2)直到列表为空，一个簇形成；（4) 重复（1)-(3），直到没有点可以加到任何一个簇中，聚类完成，剩余的点为噪声点.优点：1如果用户定义的参数设置的恰当，该算法可以有效地找出任意形状的簇。同时,DBSCAN能够识别出噪声点.2DBSCAN对于数据库中的样本的顺序不敏感。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动.缺点：1聚类质量对参数非常敏感；2需要较大的内存和输入输出支持.3使用全局密度参数,不能处理多密度数据集.4、支持向量机(SVM）思想:使用一种非线性映射，将原训练集映射到较高的维,在新的维上，它搜索最佳分离超平面，使用一个适合的对足够高维的非线性映射，两类数据总可以被超平面分开。优点：(1）对复杂的非线性决策边界的建模能力是高度准确的（2）不太容易过分拟合（3）提供了学习模型的紧凑表示。（4）可以用来预测和分类。缺点：训练时间长。特点：SVM是一种有坚实理论基础的小样本学习方法 ； SVM最终决策函数只由少数的支持向量所确定,计算复杂度和支持向量的数目有关。算法具有较好的“鲁棒”性。SVM可以有效处理非线性分类和回归问题; SVM可以确定所建模型的推广能力的上界 ;核函数的选取和参数优化仍需要解决5、EM：（定义）EM(期望最大化）算法是一种流行的迭代求精算法，可以用来求得参数的估计值，它可看作是k均值算法的一种扩展，基于簇的均值把对象指派到最相似的簇中。EM不是把每个对象指派到特定的簇,而是根据一个代表隶属概率的权重将每个对象指派到簇.（步骤)(1)期望步:对每簇计算对象x的簇隶属概率（2）最大化步：利用前面得到的概率估计重新估计模型参数（优点）简单和稳定，收敛快（缺点)达不到局部最优4、关联规则：定义：最初由R。Agrawal 等人提出，用来发现超级市场中用户购买的商品之间的隐含关联关系,并用规则的形式表示出来，称为关联规则.应用:关联规则除了可以发现超市购物中隐含的关联关系之外，还可以应用于其他很多领域.关联规则的应用还包括文本挖掘、商品广告邮寄分析、网络故障分析等。分类:(1）基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。（2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。(3)基于规则中处理的变量的类型不同,关联规则可以分为布尔型和数值型。挖掘步骤：1)找出交易数据库中所有大于或等于用户指定的最小支持度的频繁项集;（2)利用频繁项集生成所需要的关联规则，根据用户设定的最小可信度进行取舍,产生强关联规。3、朴素贝叶斯分类：定义：贝叶斯分类法是统计学分类方法,可以预测类成员关系的可能性.朴素贝叶斯分类法假定一个属性值对给定类的影响独立于其他属性值。它表示属性子集间的依赖主要思想:设为一个类别未知的数据样本，H为某个假设，若数据样本X属于一个特定的类别C，分类问题就是决定P（HX)，即在获得数据样本X时假设成立的概率。优点:（1）理论上，贝叶斯分类具有最小的错误率（2）可以用来为不直接使用贝叶斯定理的其他分类法提供理论判定（3）有着坚实的数学基础，以及稳定的分类效率(4）模型所需估计的参数很少，对缺失数据不太敏感,算法也比较简单（5）网格结构一旦确定下来后,添加新变量容易(5）适合处理不完整的数据(6)对过分拟合问题鲁棒。缺点：（1)实际上，由于对其使用的假定的不正确性,以及缺乏可用的概率，此分类法并不具有最小的错误率（2)有可能遇到零概率值,需要修正（3）构造网格费时、费力为什么朴素：朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值.该假定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”2、简述数值数据根据直观划分离散化的3-45规则(1)如果一个区间在最高有效位包括3, 6，7或 9 个不同的值,则将该区间划分为3个区间（对于3,6和9 ，划分为3个等宽的区间；对于7，按23-2划分为3个区间)。（2）如果最高位包含2,4,8个不同值，则将区间划分为4个等宽区间.（3)如果最高位包含1 ，5或10个不同的值，则将区间划分为5个等宽的区间。最高分层一般在第5个百分位到第95个百分位上进行。2、急切学习法是在接收待分类的新元组(如检验元组）之前，利用训练集,构造泛化模型，即分类器。学习后的模型已经就绪,并急于对先前未见过的元组进行分类。常见的急切学习法主要有支持向量机，决策树归纳，贝叶斯分类，基于规则的分类等.3、惰性学习法是当给定一组训练元组时,简单地存储它,仅当给出检验元组时，才利用存储的训练元组的相似性对该元组进行分类,不像急切学习法，惰性学习法在提供训练元组时只做少量工作，而在进行分类或预测时才做更多的工作.常见的惰性学习法有K最近邻和基于案例的推理分类法。急切学习法和惰性学习法的优缺点：急切学习法训练分类器时需耗费大量时间，但对检验元组进行分类或预测时速度较快,且占用空间少;惰性学习法不需要建立模型，但是在对检验元组进行分类或预测时，需要将所有训练元组与检验元组进行运算，计算开销可能相当大，耗费大量时间。1、后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元,每个连接都与一个权相连.在学习阶段,通过调整神经网络的权,使得能够预测输入样本的正确标号来学习.优点：预测精度总的来说较高、健壮性好，训练样本中包含错误时也可正常工作、输出可能是离散值、连续值或者是离散或量化属性的向量值、对目标进行分类较快缺点:训练(学习）时间长、蕴涵在学习的权中的符号含义很难理解、很难根专业领域知识相整合34、KNN定义：即K最近邻分类法，它是基于类比学习，即通过给定的检验元组与和他相似的训练元组进行比较来学习。优点1)算法简单直观，易于实现；（2）不需要产生额外的数据来描述规则，并且可以存在噪音；(3)可以较好地避免样本数量的不平衡问题；（4）减少了类别特征选择不当对分类结果造成的不利影响，可以最大程度地减少分类过程中的误差项（5）适合增量学习缺点：1）分类速度慢(2）样本库容量依赖性较强（3)必须指定K值，K值选择不当则分类精度不能保证。k值的设定，k太小，分类结果易受噪声点影响，k值太大,近邻中又可能包含太多的其它类别的点（4）计算开销大(5）需要有效的存储技术和并行硬件的支撑。1、数据预处理过程:数据清理:旨在消除或减少数据噪音和处理遗漏值的数据预处理。相关性分析：数据中许多属性可能与分类和预测任务不相关。数据变换：数据可以泛化到较高层概念。3。数据仓库的特点和操作数据库和数据仓库的区别：数据仓库的特点：(1）面向主题的：数据仓库围绕一些主题，如顾客、供应商、产品和销售组织。数据仓库关注决策者的数据建模与分析,而不是构造组织机构的日常操作和事务处理。因此，数据仓库排除对于决策无用的数据,提供特定主题的简明视图。（2）集成的：通常，构造数据仓库是将多个异种数据源,如关系数据库、一般文件和联机事务处理记录,集成在一起.使用数据清理和数据集成技术,确保命名约定、编码结构、属性度量的一致性。 （3）时变的：数据存储从历史的角度（例如，过去 510 年）提供信息.数据仓库中的关键结构，隐式或显式地包含时间元素. （4）非易失的：数据仓库总是物理地分离存放数据；这些数据源于操作环境下的应用数据.由于这种分离，数据仓库不需要事务处理、恢复和并行控制机制。通常,它只需要两种数据访问：数据的初始化装入和数据访问.操作数据库和数据仓库的区别: （1）用户和系统的面向性：OLTP 是面向顾客的，用于办事员、客户、和信息技术专业人员的事务和查询处理.OLAP 是面向市场的，用于知识工人（包括经理、主管、和分析人员)的数据分析.（2)数据内容：OLTP 系统管理当前数据。通常，这种数据太琐碎，难以方便地用于决策。OLAP 系统管理大量历史数据,提供汇总和聚集机制，并在不同的粒度级别上存储和管理信息。这些特点使得数据容易用于见多识广的决策。（3）数据库设计:通常，OLTP 系统采用实体-联系（ER）模型和面向应用的数据库设计.而 OLAP 系统通常采用星形或雪花模型（2.2。2小节讨论）和面向主题的数据库设计.（4)视图：OLTP系统主要关注一个企业或部门内部的当前数据，而不涉及历史数据或不同组织的数据。相比之下,由于组织的变化，OLAP 系统常常跨越数据库模式的多个版本.OLAP 系统也处理来自不同组织的信息，由多个数据存储集成的信息。由于数据量巨大，OLAP 数据也存放在多个存储介质上。（5)访问模式：OLTP 系统的访问主要由短的、原子事务组成。这种系统需要并行控制和恢复机制。然而，对 OLAP 系统的访问大部分是只读操作（由于大部分数据仓库存放历史数据，而不是当前数据），尽管许多可能是复杂的查询.1、 概念分层及作用，举例说明。一个概念分层定义一个映射序列，将低层概念到更一般的高层概念.概念分层也可以通过将给定维或属性的值离散化或分组来定义，产生集合分组分层.可以在值组间定义全序或偏序.例子如图关于维 price 的集合分组概念分层。其中，区间（X。.Y 表示由X（不包括）到Y（包括）。概念分层可以由系统用户、领域专家、知识工程师人工地提供,也可以根据数据分布的统计分析自动地产生.对于一个给定的属性或维，根据不同的用户视图，可能有多个概念分层。例如，用户可能愿意用 inepensive， moderately_priced和 expensive 来组织price。6。ID3算法基本思想和算法描述,C4.5算法增加了那些功能？基本思想：首先找出最有判别力的因素，然后把数据分成多个子集，每个子集又选择最有判别力的因素进一步划分，一直进行到所有子集仅包含同一类型的数据为止.最后得到一棵决策树，可以用它来对新的样例进行分类。算法描述：从训练集中随机选择一个既含正例又含反例的子集（称为窗口)；用“建树算法”对当前窗口形成一棵决策树;对训练集（窗口除外）中例子用所得决策树进行类别判定,找出错判的例子;若存在错判的例子，把它们插入窗口，重复步骤，否则结束。优点:1、理论清晰，算法简单，很有实用价值的示例学习算法.2、计算时间是例子个数、特征属性个数、节点个数之积的线性函数，总预测准确率较令人满意缺点：（1）ID3算法在选择根结点和各内部结点中的分枝属性时，使用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息（2)ID3算法只能对描述属性为离散型属性的数据集构造决策树C4。5是机器学习算法中的另一个分类决策树算法，基于ID3算法进行改进后的一种重要算法,相比于ID3算法，改进有如下几个要点:（1）用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵（entropy， 熵是一种不纯度度量准则)，也就是熵的变化值，而C4.5用的是信息增益率。(2）在决策树构造过程中进行剪枝，因为某些具有很少元素的结点可能会使构造的决策树过适应（Overfitting），如果不考虑这些结点可能会更好.（3）对非离散数据也能处理.(4）能够对不完整数据进行处理。8、划分算法的描述1、K均值：输入:簇的数目 k 和包含 n 个对象的数据库。输出：k 个簇，使平方误差最小方法：（1），随机地选择k个对象作为初始簇中心（2）根据簇中对象的均值,将每个对象再只拍到最相似的簇（3）更新簇均值，即计算每个簇中对象的均值;（4）重复（2)(3）步，直到簇中心点不再发生变化。优点:（1）思想简单易行；相对有效:O（tkn）,n是多有对象的数目,K是簇的数目,t是迭代的次数,通常k,tn(2）经常以局部最优结束（3）时间复杂度接近线性；（4）对大数据集，是可伸缩和高效率的.缺点:（1）只有在簇的平均值被定义时才能使用，不适合分类属性的数据;（2）必须实现给出要生成的簇的数目K（3）不能处理噪声点和孤立点数据（4）不适合发现凸面向形状的簇,或者大小差别很大的簇。2、K-中心点算法的输入、输出及聚类过程(流程）.输入：结果簇的数目k，包含n个对象的数据集；输出：k个簇,使得所有对象与其最近中心点的相异度总和最小.描述：随机选择k个对象作为初始中心点;计算其它对象与这k个中心的距离，然后把每个对象归入离它“最近”的簇； 随机地选择一个非中心点对象Orandom,并计算用Orandom代替Oj的总代价S;如果S0,则用Orandom代替Oj，形成新的k个中心点集合;重复迭代第3、4步，直到中心点不变为止。K中心点算法的特点：（1）当存在噪声和离群点时，K中心点方法比K均值更健壮，因为中心点不像均值那样容易受离群点或其他极端值的影响。（2）K中心点方法的执行代价比K均值算法高。(3）两种方法都要指定簇的个数K.2OLAP上卷操作与SQL的group操作的异同？上卷：上卷操作通过沿概念分层向上攀升，或者通过维归约,在数据方上进行聚集。分层被定义为全序 street city province_or_state country。所展示的上卷操作沿 location 的分层,结果数据方按 country，而不是按 city 对数据分组。 当用维归约进行上卷时，一个或多个维由给定的数据方删除SQL的group操作：是对一个属性中相同值的数据进行合并。