数据挖掘入门基础ppt课件

数据挖掘基础,1,一、概念和术语,1.1数据挖掘/知识发现（1）数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。（2）数据挖掘，又称为数据库中知识发现（KnowledgeDiscoveryinDatabases）或知识发现，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。（3）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。（4）数据库查询系统和专家系统不是数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。,2,1.2机器学习（1）对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么这个计算机程序被称为在从经验E学习。（2）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。,3,1.3数据挖掘的对象（1）关系型数据库、事务型数据库、面向对象的数据库；（2）数据仓库/多维数据库；（3）空间数据（如地图信息）（4）工程数据（如建筑、集成电路的信息）（5）文本和多媒体数据（如文本、图象、音频、视频数据）（6）时间相关的数据（如历史数据或股票交换数据）（7）万维网（如半结构化的HTML，结构化的XML以及其他网络信息）,4,1.4数据挖掘的步骤（1）数据清理（消除噪音或不一致数据，补缺）；（2）数据集成（多种数据源可以组合在一起）；（3）数据选择（从数据库中提取相关的数据）；（4）数据变换（变换成适合挖掘的形式）；（5）数据挖掘（使用智能方法提取数据模式）；（6）模式评估（识别提供知识的真正有趣模式）；（7）知识表示（可视化和知识表示技术）。,5,1.5支持数据挖掘的关键技术（1）数据库/数据仓库/OLAP（2）数学/统计（回归分析：多元回归、自回归；判别分析：Bayes判别、Fisher判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）（3）机器学习（聚类分析；关联规则；决策树；范例推理；贝叶斯网络；神经网络；支持向量机；遗传算法）（4）可视化：将数据、知识和规则转化为图形表现的形式。,6,1.6数据仓库（1）数据仓库是一个面向主题的、集成的、随时间变化的、非易失性数据的集合，用于支持管理人员的决策。（2）数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决策。数据仓库技术包括数据清理、数据集成和联机分析处理（OLAP）。（3）数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储或多维数据方（Cube）。（4）数据方是由维度（Dimension）和度量（Measure）定义的一种数据集，度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组，度量对应于与主题相关的事实数据。数据方的物化是指预计算并存储全部或部分单元中的度量。,7,1.7数据仓库的模型（1）星形模式：最常见模型；其中数据仓库包括一个大的、包含大批数据、不含冗余的中心表（事实表）；一组小的附属表（维表），每维一个。（2）雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。（3）星系模式：多个事实表共享维表。这种模式可以看作星形模式集，因此称为星系模式，或事实星座。,8,1.8典型的OLAP操作（1）OLAP是一种多维数据分析技术。包括汇总、合并和聚集等功能，以及从不同的角度观察信息的能力。（2）上卷：从某一维度的更高概念层次观察数据方，获得更概要的数据。它通过沿维的概念分层向上或维归约来实现。（3）下钻：下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方，获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。（4）切片和切块：切片操作在给定的数据方的选择一个维的部分属性，获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性，获得一个较小的子数据方。（5）转轴：是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维度由行改为列，或由列改为行。,9,二、数据准备,现实世界的数据是不完整的（有些感兴趣的属性缺少属性值，或仅包含聚集数据），含噪音的（包含错误，或存在偏离期望的异常值），不一致的（例如，用于商品分类的部门编码存在差异）。需要数据清理、数据集成、数据选择、数据变换等技术对数据进行处理。,10,2.1维归约/特征提取2.1-1决策树归约（1）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结点表示一个决策类。（2）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。,11,2.2数据变换2.2-1归一化与模糊化有限区间的归一化：无限区间的归一化：模糊隶属度：,12,2.2-2核函数（1）核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。（2）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系f，使高维空间的特征向量f(x)可以被直接计算出来。（3）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求f(x)的计算困难。核函数即某高维特征空间中向量的内积，是核矩阵中的一个元素。（4）并不是所有的实值函数f(x)都可以作为空间映射的核函数，只有f(x)是某一特征空间的内积时，即符合Mercer条件，它才能成为核函数。,13,2.2-2核函数（续）多项式函数：高斯（RBF）函数：多层感知机函数：低维空间向量映射到高维空间向量举例：,14,2.3数据压缩2.3-1离散化离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。离散化的方法包括几下几种。（1）等距分割；（2）聚类分割；（3）直方图分割；（4）基于熵的分割；（5）基于自然属性的分割。,15,2.3-2回归回归和对数线性模型可以用来近似给定的数据。在线性回归中，用一条直线来模拟数据的生成规则。多元回归是线性回归的扩展，涉及多个预测变量。在多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。,16,2.3-2回归（续）利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。在广义线性模型中，因变量Y的变化速率是Y均值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。对数回归模型是利用一些事件发生的概率作为自变量所建立的线性回归模型。泊松回归模型主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。,17,2.3-3主成分分析（PCA）PCA算法搜索c个最能代表数据的k-维正交向量；这里ck。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：（1）对输入数据归一化，使得每个属性都落入相同的区间。（2）PCA计算c个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性组合。（3）对主成分按“意义”或强度降序排列，选择部分主成分充当数据的一组新坐标轴。,18,2.3-4潜在语义分析潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。（1）构造“特征-样本”矩阵，“特征-样本”矩阵中的每一列是对应于第i个样本特征向量；（2）对该矩阵进行奇异值分解(SVD)；（3）用最大的k个奇异值所对应的“特征-语义”矩阵Uk和“样本-语义”矩阵Vk以及最大的k个奇异值重构“特征-样本”矩阵。,下面两式分别代表在语义空间特征与特征之间的距离和在语义空间样本与样本之间的距离,19,2.3-5聚类分析聚类技术将数据元组视为对象。它将对象划分为聚类，使在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。通常，类似性基于距离，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示；而直径是一个聚类中两个任意对象的最大距离。质心距离是聚类质量的另一种度量，它定义为由聚类质心（表示“平均对象”，或聚类空间中的平均点）到每个聚类对象的平均距离。,20,2.3-5聚类分析（续）,k-means算法,k-medoids算法,21,三、数据挖掘算法,数据挖掘算法按挖掘目的可分为：（1）概念描述（总结，对比等）（2）关联规则分析（3）分类与预测（信息自动分类，信息过滤，图像识别等）（4）聚类分析（5）异常分析（入侵检测，金融安全等）（6）趋势、演化分析（回归，序列模式挖掘）,22,按训练方式，机器学习可分为：（1）有监督的学习；有训练样本，学习机通过学习获得训练样本包含的知识，并用其作为判断测试样本的类别的依据。（2）无监督的学习：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。（3）半监督的学习：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。（4）强化学习：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。,23,有监督的学习,半监督的学习,无监督的学习,24,3.1关联规则挖掘关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设I=i1,i2,.,im是项的集合。设任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得TI。设A是一个项集，事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，并且AB=。规则AB在事务集D中成立，具有支持度s，其中s是D中事务包含AB的百分比。即，P(AB)。规则AB在事务集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比是c。这是条件概率P(B|A)。即support(AB)=P(AB)confidence(AB)=P(B|A),25,3.1关联规则挖掘（续）连接步：为找Lk，通过Lk-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck。Ck是Lk的超集。扫描数据库，确定Ck中每个候选的计数，将令计数值不小于最小支持度计数的（频繁的）所有候选加入Lk。剪枝步：但Ck可能很大，这样所涉及的计算量就很大。根据Apriori性质如果一个候选k-项集的(k-1)-子集不在Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中删除。Apriori性质(逆反描述)：任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集。,26,3.2决策树决策树学习是归纳推理算法。它是一种逼近离散函数的方法，且对噪声数据有很好的健壮性。在这种方法中学习到的知识被表示为决策树，决策树也能再被表示为多个if-then的规则，以提高可读性。基本决策树算法就是一个贪心算法。它采用自上而下、分而制之的递归方式来构造一个决策树通常，决策树是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。“信息增益”用于衡量属性的价值。熵（entropy）是一种度量信息增益的指标，它描述了样本的纯度（purity）。下面是熵的定义：Entropy=-Pilog2Pi,27,3.2决策树（续）注意点：（1）避免过度拟合，应该适度剪枝；（2）连续值的离散化；（3）处理缺失值的方法：最常见值、按概率分配；（4）处理权重不同的属性常用实现算法：CART、ID3、ASSISTANT、C4.5,28,3.3人工神经网络人工神经网络（ArtificialNeuralNetworks）提供了一种普遍而且实用的方法，来从样例中学习值为实数、离散或向量的函数。反向传播（BackPropagation）这样的算法使用梯度下降来调节网络参数以最佳拟合由输入/输出对组成的训练集合。BP网络的学习方法和目标：对网络的连接权值进行调整，使得对任一输入都能得到所期望的输出。,29,常用的非线性作用函数是Sigmoid函数，即f(x)=1/(1+e-x)。在神经网络模型中，大量神经元节点按一定体系结构连接成网状。神经网络一般都具有输入层，隐层和输出层。,每个神经元都是一个结构相似的独立单元，它接受前一层传来的数据，并将这些数据的加权和输入非线性作用函数中，最后将非线性作用函数的输出结果传递给后一层。,30,3.4朴素贝叶斯（NaiveBayes）分类器朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信任程度。P(H)是先验概率，或H的先验概率。P(H|X)是后验概率，或条件X下，H的后验概率。后验概率P(H|X)比先验概率P(H)基于更多的信息。P(H)是独立于X的。假定数据样本世界由水果组成，用它们的颜色和形状描述。假定X表示红色和圆的，H表示假定X是苹果，则P(H|X)反映当我们看到X是红色并是圆的时，我们对X是苹果的确信程度。,31,朴素贝叶斯分类能够奏效的前提是，P(X|H)相对比较容易计算。假定X表示红色和圆的，H表示假定X是苹果；则P(X|H)表示已知苹果，它既红又圆的概率。,32,3.5期望最大化（EM）期望最大化（EM）方法和朴素贝叶斯方法有着共同的理论基础。期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。样本数据分为标记样本和未标记样本，按照统计的观点，对于每一个样本的产生，其背后都有一个模型，即样本生成模型。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。,33,3.5期望最大化（续）如果参数适当，EM算法能得到较好的分类结果，但计算速度相对较慢。其具体的步骤如下：一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法进行类标注。二、反复迭代E步骤和M步骤，直到收敛。三、E步骤：对于每个未标记的样本，按下式计算类标记的期望值。四、M步骤：利用E步骤计算出的期望值，按下式用已标记样本和未标记样本重新估计新的分类器参数。,34,3.6K-最近邻分类K-近邻（K-NN）分类是基于范例的分类方法，它的基本思想是：给定待分类样本后，考虑在训练样本集中与该待分类样本距离最近（最相似）的K个样本，根据这K个样本中大多数样本所属的类别判定待分类样本的类别。它的特例是1-NN，即分类时选出待分类样本的最近邻，并以此最近邻的类标记来判断样本的类。K-NN算法的优点在于它有较高的精确程度，研究表明，K-NN的分类效果要明显好于朴素贝叶斯分类、决策树分类。,35,3.6K-最近邻分类（续）最近邻分类的算法步骤如下：一、以向量空间模型的形式描述各训练样本。二、在全部训练样本集中选出与待分类样本最相似的K个样本。K值的确定目前没有很好的方法，一般采用先定一个100左右的初始值，然后再调整。三、将待分类样本标记为其K个邻居中所属最多的那个类别中。,36,3.7聚类分析为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。绝大多数应用采用了以下两个比较流行的基于划分的方法，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。（1）k-means算法，在该算法中，每个簇用该簇中对象的平均值来表示。（2）k-medoids算法，在该算法中，每个簇用接近聚类中心的一个对象来表示。,37,3.7聚类分析（续）常用的相似程度度量余弦夹角：Dice系数：Jaccard系数：,38,四、模型上的模型,4.1装袋/提升给定s个样本的集合S。装袋（Bagging）过程如下。对于迭代t(t=1,2,.,T)，训练集St采用放回选样，由原始样本集S选取。由于使用放回选样，S的某些样本可能不在St中，而其它的可能出现多次。由每个训练集St学习，得到一个分类法Ct。为对一个未知的样本X分类，每个分类法Ct返回它的类预测，算作一票。装袋的分类法C*统计得票，并将得票最高的类赋予X。通过取得票的平均值，装袋也可以用于连续值的预测。,39,4.1装袋/提升（续）提升（Boosting）过程如下：每个训练样本赋予一个权，并学习得到一系列分类法。对于迭代t(t=1,2,.,T)，学习得到分类法Ct后，更新权，使得随后的分类法Ct+1“更关注”Ct的分类错误。最终的提升分类法C*组合每个分类法的表决，这里每个分类法的表决是其准确率的函数。通过取得票的平均值，提升算法也可以扩充到连续值预测。,40,4.2共同训练（Co-Training）共同训练算法用两个不同的“视图”（即特征集合）来描述文本的特征。基本思路：每个视图对应一个学习机，而每个学习机都根据自身已学到的规律来标记“最有把握”的无标记样本，然后将这个（或这几个）新标记的样本加入训练样本，并扩展后的训练样本提供给另一个学习机进行学习。如此反复，直到满足一定的条件为止。该算法中所用到的两个视图需要满足以下两个条件：首先，每个特征集合对文本分类学习来说都是充分的；其次，在给定类别标记的条件下，两个特征集合相互独立。,41,4.3主动学习/被动学习主动学习在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，它能有效地减少评价样本的数量；被动学习只是随机地选择训练样本，被动地接受这些样本的信息进行学习。主动学习是实现监督学习过程的一个有效的方法。在主动学习过程中，分类器主动地选择对其“最有帮助”的一组子样本进行学习，而不是被动地接受训练集。“最有帮助”的样本指的是对当前分类器来说，归属最不确定的样本。即当前分类器最难以区分的样本。通常情况下，主动学习的计算复杂度比一般的监督学习过程要显著得低。,42,4.3主动学习/被动学习（续）初始状态下，候选样本集中所有的样本都未带类别标注，根据先验知识或者随机地从候选样本集中选择少量样本并标注它们的类别，构造初始训练样本集，确保初始训练样本集中至少包含有一个正例样本和一个负例样本。在上述初始训练样本集上训练一个分类器，并采用某种针对该分类器采样算法，从候选样本集中选择最有利于提高分类器性能的样本，手工标注其类别并加入训练样本集，再重新训练分类器。重复以上过程，直到候选样本集为空或达到某种要求。主动学习是一个循环反复的过程。,43,在主动学习的模型中，全部数据被分为两部分，一部分是带标签的样本集X，另一部分是无标签的样本集U。主动学习的模型还包括了一个在带标签的样本集X上训练的学习机L和一个决策模块q。决策模块q用来决定U中的哪一些样本应该被选出标记标签，并加入带标签的样本集X。更新后的X将在下一个轮次被用于训练学习机L。主动学习的框架模型如图。,根据决策模块q的不同工作机理，主动学习方法又可以被分为两大类：其一是不确定取样方法；另一是委员会咨询方法。,44,5.1分类精度评价指标理想的分类器应该将所有属于某一类的样本标记为该类；且不将任何一个不属于该类的样本标记为该类。可以采有两个指标用来评价分类器的性能：准确率（查准率）和召回率(查全率)。对于某一特定类别Ci，准确率(P)=召回率(R)=,五、性能评估,45,5.1分类精度评价指标（续）对于同一分类器，这准确率和查全率的变化趋势通常是相反的，片面追求其中一个指标而完全不顾及另一个是没有意义的。为综合考虑准确率和查全率，可以使用一种能够全面评价分类器性能的指标：F-1。F-1=F-1综合考虑了上述两指标，且偏向于准确率和查全率中较小的一个，只有当准确率和查全率都较大时，F-1指标才会比较大。,46,5.1分类精度评价指标（续）多数分类器可以通过调整参数获得不同的准确率和查全率，当分类器的参数调节到正好使准确率和查全率相等时，该值称为P/R无损耗(平衡)点。它也是一种综合考虑准确率和查全率的指标。在综合考虑全部类别的条件下，精确度(Accuracy)也是一个常用的指标，它是指所有分类正确的