数据挖掘复习总结.doc

一、数据挖掘的概念：（商业及学术方面）定义：a.技术定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们实现不知道的、但又是潜在的有用的信息和知识的过程。与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义包括以下几层含义：1.数据源必须是真实的、大量的2.发现的是用户感兴趣的知识3.发现的知识是可接受的、可理解的、可运用的4.发现的知识并不要求发放之四海皆准，仅要求支持特定的业务问题。商业定义：数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关建化数据。简而言之，数据挖掘其实就一类深层次的数据分析方法二、数据挖掘的模式模式：数据特征化：目标类数据的一般特征或特性的汇总。通常用户指定类的数据通过数据库查询收集。模式类型：a.概念/类描述：特征和区分 数据可以与类或概念相关联。b.关联分析 关联分析发现关联规则，这些规则展示属性-值频繁地在给定数据集中一起出现的条件。关联分析广泛用于购物篮或事务数据分析。c.分类与预测 分类是这样的过程，它找描述或识别数据类或概念的模型(或函数)，以便能够使用模型预测类标号未知的对象。导出模型是基于对训练数据集（即，其类标号已知的数据对象）的分析。d.聚类分析 “何为聚类分析？”与分类和预测不同，聚类分析数据对象，而不考虑已知的类标号。e.局外者分析 在一些应用中（如，欺骗检测），罕见的事件可能比正规出现的那些更有趣。局外者数据分析称作局外者挖掘。局外者可以使用统计试验检测。f演变分析 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。三、OLAP技术，多维数据模型，数据立方体概念，构建星型数据库模型 OLAP技术（联机分析处理）：可以用不同的格式组织和提供数据，以满足不同用户的各种需求。特点：面向市场的，用于知识工人的数据分析、管理大量历史数据，提供汇总和聚集机制，并在不同的粒度级别上存储和管理信息、通常采用星形或者雪花模型以及面向主题的数据库设计尝尝跨越数据库模式的多个版本，还可以处理来自不同组织的信息，由多个数据存储集成的信息、访问大部分是只读操作、多位数据模型：这种模型将数据看成数据立方体形式数据立方体：允许从多维对数据建模和观察，它由维和事实定义，维是关于一个组织想要保存记录的透视图或实体，事实是数值度量的。构建星形数据库模型：数据仓库包括：一个大的包含大批数据并且不含冗余的中心表（事实表）；一组小的附属表，每维一个四、度量分类与计算度量可以根据其所用的聚集函数分成三类：（1）分布的：一个聚集函数是分布的，如果它能以如下分布方式进行计算：设数据被划分为n个集合，函数在每一部分上的计算得到一个聚集值。如果将函数用于n个聚集值得到的结果，与将函数用于所有数据得到的结果一样，则该函数可以用分布方式计算。（2）代数的：一个聚集函数是代数的，如果它能够由一个具有M个参数的代数函数计算（其中M是一个有界整数），而每个参数都可以用一个分布聚集函数求得。（3）整体的：一个聚集函数是整体的，如果描述它的子聚集所需的存储没有一个常数界。即不存在一个具有,个参数的代数函数进行这一计算（其中M是常数）。整体函数的常见例子包括median()，mode()和rank()。一个度量是整体的，如果它可以用整体聚集函数得到。 如何计算度量，首先看看如何对度量分类。注意，数据立方体空间的多维点由维-值对定义。例如，。数据立方体度量是一个数值函数，该函数可以对数据立方体的每一个点求值，通过对给定点的个维-值对聚集数据，计算该点的度量值。五、K均值分配方法（1）把对象划分为K个非空的子集 （2）随机的选择一些种子点作为目前划分的簇的质心。质心是簇的中心（平均点） （3）把每一个对象赋给最近的种子点 （4）重复第二步，直到没有新的分配六、OLAP操作有哪些（1）上卷：上卷操作（有些人称之为“上钻”操作）或者通过沿概念分层向上攀升，或者通过维归约，在数据方上进行聚集。（2）下钻：下钻是上卷的逆操作，它由不太详细的数据到更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。转轴：转轴（又称旋转）是一种目视操作，它转动数据的视角，提供数据的替代表示。（3）切片和切块：切片操作在给定的数据方的一个维上进行选择，导致一个子方。（4）其它OLAP 操作：有些OLAP 还提供其它操作。例如，drill_across 执行涉及多个事实表的查询；drill_through 操作使用关系SQL 机制，钻到数据方的底层，到后端关系表。其它OLAP 操作可能包括列出表中最高或最低的N 项，以及计算移动平均值、增长率、利润、内部返回率、贬值、流通转换、和统计功能。七、数据预处理（最小-最大规范化和小数定标规范化）八、置信度与精确度的概念精度是指重复测量值之间的接近度所谓置信度,也叫可靠度，或置信水平、置信系数，它是指特定个体对待特定命题真实性相信的程度.也就是概率是对个人信念合理性的量度.概率的置信度解释表明,事件本身并没有什么概率,事件之所以指派有概率只是指派概率的人头脑中所具有的信念证据。置信水平是指总体参数值落在样本统计值某一区内的概率；而置信区间是指在某一置信水平下，样本统计值与总体参数值间误差范围。置信区间越大，置信水平越高。九、T权值与D权值计算T-weight:量化规则a) 使用t_weight表示主泛化关系中每个元组的典型性量化特征规则将泛化的结果映射到相应的量化特征规则中，比如：量化特征规则中每个析取代表一个条件，一般，这些条件的析取形成目标类的必要条件，因为该条件是根据目标类的所有情况导出的。也就是说，目标类的所有元组必须满足该条件。然而，该规则可能不是目标类的充分条件，因为满足同一条件的元组可能属于其他类。 eg.D-wight:类比较描述中的目标类和对比类的区分特性也可以用量化规则来表示，即量化判别规则。量化判别规则使用d-weight作为兴趣度度量 （qa概化元组Cj目标类qa的d-weight是初始目标类工作关系中被qa覆盖的元组数 与 初始目标类和对比类工作关系中被qa覆盖的总元组数的比 例子：以下按照location分类，分成EURTOPE和NORTH_AMERICA两类，描述这两类的特征和比较 TVCOMPUTERBOTHT-权D-权T-权D-权T-权D-权EUROPE800.250.42400.750.332010.32NORTH_AMERICA1200.180.65600.820.768010.68BOTH2000.218000.81100011其中：第一个T-权=80/320=0.25，120/680=0.18；D-权=80/200=0.4，120/200=0.6形象地说：T-权刻画同意类别中的不同属性特征；D-权刻画同一属性的不同类别比较。十、目标类与对比类（得到一些最终的描述）概念（或类）描述由特征和比较组成。前者汇总并描述称作目标类的数据集，而后者汇总并将一个称作目标类数据集与称作对比类的其他数据集相区别。数据挖掘中，将目标类与对比类相区别的描述。目标类和对比类必须是可比较的，意指他们具有相似的维和属性。例如，三个类person,address和item是不可比较的。然而，过去三年的销售是可比较的，计算机系的同学和物理系的同学同样是可比较的。十一、APRIORI算法（用apriori算法找出频繁项集）十二、由关联挖掘到相关分析，强关联规则未必有趣，通过例子进行说明“挖掘了关联规则之后，数据挖掘系统如何指出那些规则是用户感兴趣的？”大部分关联规则挖掘算法使用支持度-置信度框架。尽管最小支持度和置信度阀值排除了一些无兴趣的规则的探查，仍然会产生一些对用户来说不感兴趣的规则。我们首先看看即便是强关联规则为何也可能是无兴趣的并可能误导，然后，讨论基于统计独立性和相关分析的其他度量。十三、分类的步骤有哪些分类的基本步骤：（1）建模：选取训练样本集，每个训练样本都有一个类标签与之对应，根据训练集中的数据表现出来的特性，为每一个类找到一种准确地学习模型，学习模型主要使用分类规则、决策树、等式、不等式和规则等形式提供。（2）使用模型进行分类：首先评估模型的预测准确度，方法是选择一组独立于训练集的随机样本在给定的模型上进行测试，被正确分类的测试样本的百分比就是准确度（使用交叉验证法来评估模型是比较合理的）；如果准确度可以被接受，就可以用它来对未知的数据进行分类了。十四、分类的方法有哪些（1）用判定树归纳分类：判定树是一个类似于流程图的树结构；其中，每个内部结点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶结点代表类或类分布。树的最顶层结点是根结点。内部结点用矩形表示，而树叶用椭圆表示。 为了对未知的样本分类，样本的属性值在判定树上测试。路径由根到存放该样本预测的叶结点。判定树容易转换成分类规则。 （2）贝叶斯分类 ：贝叶斯分类是统计学分类方法。它们可以预测类成员关系的可能性，简单贝叶斯分类算法可以与判定树和神经网络分类算法相媲美。用于大型数据库，贝叶斯分类也已表现出高准确率与高速度。 朴素贝叶斯分类假定一个属性值对给定类的影响独立于其它属性的值。 该假定称作类条件独立。做此假定是为了简化所需计算，并在此意义下称为“朴素的”。 贝叶斯信念网络是图形模型。不象贝叶斯朴素分类，它能表示属性子集间的依赖。贝叶斯信念网络也可以用于分类。 （3）后向传播分类 ：后向传播是一种神经网络学习算法。神经网络最早是由心理学家和神经家提出的，旨在寻求开发和测试神经的计算模拟。粗略地说，神经网络是一组连接的输入/输出单元，其中每个连接都与一个权相相联。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确类标号来学习。由于单元之间的连接，神经网络学习又称连接者学习。 （4）基于源于关联规则挖掘概念的分类 ：关联规则挖掘是数据挖掘研究的一个重要的、高度活跃的领域。十五、预测中的线性回归是怎么计算的“什么是线性回归？”在线性回归中，数据用直线建模。线性回归是最简单的回归形式。双变量回归将一个随机变量 Y（称作响应变量）视为另一个随机变量 X（称为预测变量）的线性函数。即： 其中，Y 的方差为常数；和是回归系数，分别表示直线在 Y轴的截断和直线的斜率。这些系数可以用最小平方法求解，这使得实际数据与该直线的估计之间误差最小。给定 s 个样本或形如(x1,y1), (x2,y2),., (xs,ys)的数据点，回归系数和可以用下式计算： 其中，x 是 x1, x2 ,., xs的平均值，而 y是 y1, y2 ,., ys的平均值。与其它复杂的回归方法相比，线性回归常常给出很好的近似。 十六、聚类的概念，分类方法有哪些，开均值方法要掌握 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生成一组数据对象的集合称为簇，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，一个簇中的数据对象可以被作为一个整体来对待。常用的聚类算法大致可以分成如下几类：划分式聚类算法、层次聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法。划分式聚类算法需要预先指定聚类数目和聚类中心，通过反复迭代运算，足部优化准则函数的值，当准则函数收敛时，得到最终的聚类结果。该类算法包括K均值算法、K中心点算法及它们的变种。层次聚类算法包括BIRCH算法，ROCK算法、Chameleon算法。基于密度的聚类算法包括DBSCAN算法、OPTICS算法、DENCLUR算法等。基于网格的聚类算法包括STING、WaveCluster等。基于模型的聚类算法算法包括EM算法、OBWEB算法、SOM算法等。K均值算法描述：算法：K均值聚类算法（D,K）输入：数据对象集合D，簇的数目K输出：K个簇的集合步骤：（1）从D中随机选取K个不同的数据对象作为K个簇C1，C2，CK的中心m1,m2,mk（2）repat（2.1） for D 中每个数据对象o（2.1.1）寻找i,i=arg min|o-mj|, j = 1,2,k (2.1.2)将o分配给Ci（2.2）for 每个簇Ci（i=1,2,k） 计算mi= 计算新的聚类中心，|Ci|为当前簇Ci中的对象的个数（2.3）计算平方误差（3）Until J 不在发生变化十七、描述数据离散程度的统计度量数值数据趋向于离散的程度称为数据的离散度或方差。数据离散度的最长用度量是五数概括（基于四分数）、中间四分位数区间和标准差。盒图的绘制（展现孤立点值）也用作一种有用的图形方法。十八、信用卡欺骗检测 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这些数据对象是局外者。大部分数据挖掘方法将局外者视为噪音或例外而丢弃。然而，在一些应用中（如，欺骗检测），罕见的事件可能比正规出现的那些更有趣。局外者数据分析称作局外者挖掘。局外者可以使用统计试验检测。它假定一个数据分布或概率模型，并使用距离度量，到其它聚类的距离很大的对象被视为局外者。基于偏差的方法通过考察一群对象主要特征上的差别识别局外者，而不是使用统计或距离度量。例 1.9 局外者分析可以发现信用卡欺骗。通过检测一个给定帐号与正常的付费相比，付款数额特别大来发现信用卡欺骗性使用。局外者值还可以通过购物地点和类型，或购物频率来检测。十九、通过面向属性的归纳后得到的训练样本集合，要求用信息增益的办法判断其某些属性是否为强相关属性关于属性相关分析，在机器学习、统计、模糊和粗糙集理论等方面都有许多研究。属性相关分析的基本思想是计算某种度量，用于量化属性与给定类或概念的相关性。这种度量包括信息增益、Gini 索引、不确定性和相关系数。“信息增益计算如何工作？”设S 是训练样本的集合，其中每个样本的类标号是已知的。事实上，每个样本是一个元组，一个属性用于确定训练样本的类。例如，属性status 可以用于定义每个样本的类标号或者是“graduate”，或者是“undergraduate”。假定有m 个类。设S 包含si 个Ci 类样本，i = 1, ., m。一个任意样本属于类Ci 的可能性是si / s，其中s 是集合S 中对象的总数。对一个给定的样本分类所需的期望信息是 具有值a1,a2,.,av的属性A 可以用来将S 划分为子集 S1,S2,.,Sv ，其中，Sj 包含S 中A值为aj 的那些样本。设Sj 包含类Ci 的sij 个对象。根据A 的这种划分的期望信息称作A 的熵。它是加权平均： A 上该划分的信息增益定义为: 在这种相关分析方法中，我们可以计算定义S 中样本的每个属性的信息增益。具有最高信息增益的属性是给定集合中具有最高区分度的属性。通过计算信息增益，我们可以得到属性的秩评定。这种秩评定可用于相关分析，选择用于概念描述的属性。概念描述的属性相关分析执行步骤如下：1 数据收集：通过查询处理，收集目标类和对比类的数据。对于类比较，目标类和对比类都由用户在数据挖掘查询中提供。对于类特征，目标类是要特征化的类，而对比类是不在目标类中的可比较数据。2 使用保守的AOI 进行预相关分析：这一步识别属性和维的集合，选择的相关性度量用于它们。由于维的不同层次对于给定的类具有很不相同的相关性，原则上，定义维概念层的每个属性都应当包含在相关分析中。通过删除或泛化具有大量不同值的属性（如，name 和phone#），面向属性的归纳（AOI）可以用来进行一些预相关分析。对于概念描述，具有大量的不同值的属性多半没有意义。保守一点，这里进行的AOI 使用的属性分析阈值要合理的大，使得更多的（但非所有的）属性在进一步相关分析（下面的步骤3）中被考虑。这样使用AOI 得到的关系称作挖掘任务的候选关系。3 使用选定的相关分析度量删除不相关和弱相关属性：使用选定的相关分析度量，评估候选关系中的每个属性。此步所用的相关性度量可以建立在数据挖掘系统中，或由用户提供。例如，可以使用上面介绍的信息增益度量。根据计算的属性与数据挖掘任务的相关性，对属性排序（即，确定秩）。然后删除与类描述任务不相关或弱相关的属性。可以设置一个阈值来定义“弱相关”。其结果为初始目标类工作关系和初始对比类工作关系。4 使用AOI 产生概念描述：使用一组不太保守的属性泛化阈值进行AOI。如果类描述任务是类特征，这里只包含初始目标类工作关系。如果类描述任务是类比较， 初始目标类工作关系和初始对比类工作关系都要包含在分析中。该过程的复杂性类似于图5.1 中的算法，因为归纳过程进行了两次，一次是预相关分析（步骤2），另一次是在初始工作关系上归纳（步骤4）。以选定度量进行属性相关性分析（步骤3）所用的统计可以在步骤2 的数据库扫描时确定。一个例子如果挖掘的类描述涉及许多属性，应当运行解析特征。该过程在进行特化之前，首先删除不相关或弱相关的属性。让我们考察一个解析挖掘过程的例子。例5.9 假定我们想使用解析特征挖掘Big-University 的研究生的一般特征描述。给定的属性是name, gender, major, birth_place, birth_date, phone#和gpa。“解析特征如何执行？”第1 步，收集目标类数据，它由研究生的集合组成。还需要对比类的数据，以便进行相关分析。对比类取本科生的集合。第2 步，用保守的属性泛化阈值进行面向属性的归纳，通过属性删除和属性泛化进行预相关分析。类似于例5.3，属性name 和phone#被删除，因为它们的不同值个数超过了它们对应的属性分析阈值。与例5.3 相同，使用概念分层将birth_place 泛化到birth_country，birth_date 泛化到age_range。属性major 和gpa 也使用例5.3 的概念分层泛化到较高的抽象概念层。因此，候选关系中剩下的属性是gender, major, birth_country, age_range 和gpa。结果关系在表5.5 和5.6中。第3 步，使用选定的相关分析度量(如, 信息增益)，评估候选关系中的属性。设C1 对应于研究生类，C2 对应于本科生类。在研究生类有120 个样本，本科生有130 个样本。为计算每个属性的信息增益，我们先用(5.4)式计算对给定的样本分类所需要的期望信息。即 下一步，我们需要计算每个属性的熵。让我们试属性major。我们需要观察对于属性major 的每个值，研究生和本科生的分布。对每个分布，计算期望信息。对于major = ”Science”类似地，我们可以对剩下的属性计算信息增益。对于每个属性，它们的信息增益按递增序分别是：gender: 0.0003，birth_country: 0.0407，major: 0.2115，gpa: 0.4490 和age_range: 0.5971。假定我们用于识别弱相关性的属性相关阈值为0.1。属性gender 和birth_country 的信息增益小于该阈值，因此被认为是弱相关的。这样，它们被删除。对比类也被删除，产生初始目标类工作关系。第4 步，按照图5.1 算法，将面向属性归纳用于初始目标类工作关系。二十、星型模式图最常见的模型范例星形模式；其中数据仓库包括（1）一个大的、包含大批数据、不。含冗余的中心表（事实表）；（2）一组小的附属表（维表），每维一个。这种模式图很象星星爆发，维表围绕中心表显示在射线上。例 2.1 作为一个例子，Allelectronics 的星形模式如图2.4 所示。sales 有四个维，分别是time, item,branch 和location。该模式包含一个中心事实表sales，它包含四个维的关键字和两个度量dollars_sold和units_sold。为尽量减小事实表的尺寸，维标识符（如，time_key 和item_key）是系统产生的标识符。注意：在星形模式中，每维只用一个表表示，每个表包含一组属性。例如，location 维表包含属性集location_key, street, city, province_or_state, country。这一限制可能造成某些冗余。例如，“Vancouver”和“Victoria”都是加拿大不列颠哥伦比亚省的城市。location 维表中这些城市实体的属性province_or_state， country 之间都会有些冗余，即, (., Vancouver, British Columbia, Canada),(.,Victoria, British Columbia, Canada)。此外，一个维表中的属性可能形成一个层次（全序）或格（偏序）。二十一、量化特征规则、量化判别规则和量化描述规则的区别量化特征规则：必要条件量化区分规则：充分条件量化描述规则：充分必要条件二十二、SQL Server Analysis Services来建立一个数据仓库（1）首先在 Analysis Services 项目中定义数据源视图创建 Analysis Services 项目，为其设置数据源和数据源视图，最后修改表的默认名称。（2）定义和部署数据仓库，修改度量值、属性和层次结构，定义高级属性和维度属性，维度与度量值组之间的关系，以及计算、关键绩效指标和操作（3）在组织、修改好并理解了准备分析的数据后, 我们就可以开始创建数据挖掘对象。在SQL Server Analysis Services里有两个关键对象: 挖掘结构和挖掘模型。我们借助数据挖