数据挖掘算法的基础适合入门精.ppt
《数据挖掘算法的基础适合入门精.ppt》由会员分享,可在线阅读,更多相关《数据挖掘算法的基础适合入门精.ppt(87页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据挖掘算法的基础适合数据挖掘算法的基础适合入门入门第1页,本讲稿共87页一、概念和术语n n1.1 数据挖掘数据挖掘/知识发现知识发现(1 1)数据挖掘数据挖掘数据挖掘数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。是从存放在数据集中的大量数据挖掘出有趣知识的过程。(2 2)数据挖掘,又称为)数据挖掘,又称为数据库中知识发现数据库中知识发现数据库中知识发现数据库中知识发现(Knowledge Discovery in Knowledge Discovery in DatabasesDatabases)或)或知识发现知识发现知识发现知识发现,它是一个从大量数据中抽取挖掘出未,它是一个
2、从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程,它与数据仓知的、有价值的模式或规律等知识的非平凡过程,它与数据仓库有着密切的联系。库有着密切的联系。(3 3)广义的数据挖掘是指知识发现的全过程;狭义的数据挖掘是指统)广义的数据挖掘是指知识发现的全过程;狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法,即偏重于模型和算计分析、机器学习等发现数据模式的智能方法,即偏重于模型和算法。法。(4 4)数据库查询系统和专家系统)数据库查询系统和专家系统不是不是不是不是数据挖掘!在小规模数据上数据挖掘!在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。的统计分析和机器
3、学习过程也不应算作数据挖掘。第2页,本讲稿共87页n n1.2 机器学习机器学习(1)对于某类任务T和性能度量P,如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善,那么这个计算机程序被称为在从经验E学习。(2)机器学习是知识发现的一种方法,是指一个系统通过执行某种过程而改进它处理某一问题的能力。第3页,本讲稿共87页n n1.3 数据挖掘的对象数据挖掘的对象(1)关系型数据库、事务型数据库、面向对象的数据库;(2)数据仓库/多维数据库;(3 3)空间数据(如地图信息)空间数据(如地图信息)(4 4)工程数据(如建筑、集成电路的信息)工程数据(如建筑、集成电路的信息)(5)文本和多媒体
4、数据(如文本、图象、音频、视频数据)(6 6)时间相关的数据(如历史数据或股票交换数据)时间相关的数据(如历史数据或股票交换数据)(7)万维网(如半结构化的HTML,结构化的XML以及其他网络信息)第4页,本讲稿共87页n n1.4 数据挖掘的步骤数据挖掘的步骤(1 1)数据清理(消除噪音或不一致数据,补缺);)数据清理(消除噪音或不一致数据,补缺);(2)数据集成(多种数据源可以组合在一起);(3 3)数据选择(从数据库中提取相关的数据);)数据选择(从数据库中提取相关的数据);(4)数据变换(变换成适合挖掘的形式);(5 5)数据挖掘(使用智能方法提取数据模式);)数据挖掘(使用智能方法提
5、取数据模式);(6)模式评估(识别提供知识的真正有趣模式);(7)知识表示(可视化和知识表示技术)。第5页,本讲稿共87页n n1.5 支持数据挖掘的关键技术支持数据挖掘的关键技术(1)数据库/数据仓库/OLAP(2)数学/统计(回归分析:多元回归、自回归;判别分析:Bayes判别、Fisher判别、非参数判别;主成分分析、相关性分析;模糊集;粗糙集)(3)机器学习(聚类分析;关联规则;决策树;范例推理;贝叶斯网络;神经网络;支持向量机;遗传算法)(4)可视化:将数据、知识和规则转化为图形表现的形式。第6页,本讲稿共87页n n1.6 数据仓库数据仓库(1 1)数据仓库数据仓库是一个面向主题的
6、、集成的、随时间变化的、是一个面向主题的、集成的、随时间变化的、非易失性数据的集合,用于支持管理人员的决策。非易失性数据的集合,用于支持管理人员的决策。(2 2)数据仓库是一种多个异种数据源在单个站点以统一的模式)数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储,以支持管理决策。数据仓库技术包括数据清理、组织的存储,以支持管理决策。数据仓库技术包括数据清理、数据集成和数据集成和联机分析处理联机分析处理联机分析处理联机分析处理(OLAPOLAP)。)。(3 3)数据仓库的逻辑结构是多维数据库。数据仓库的实际物理)数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储
7、或结构可以是关系数据存储或多维数据方多维数据方(Cube)。(4 4)数据方是由)数据方是由维度维度(DimensionDimension)和)和度量度量(MeasureMeasure)定义)定义的一种数据集,度量存放在由维度索引的数据方单元中。维的一种数据集,度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组,度量对应于与主题相关的事实数度对应于模式中的属性组,度量对应于与主题相关的事实数据。数据方的据。数据方的物化物化物化物化是指预计算并存储全部或部分单元中的度量。第7页,本讲稿共87页n n1.7 数据仓库的模型数据仓库的模型(1)星形模式星形模式:最常见模型;其中数据仓库包括
8、一个大的、包含大批数据、不含冗余的中心表(事实表);一组小的附属表(维表),每维一个。(2)雪花模式雪花模式:雪花模式是星型模式的变种,其中某些维表是规范化的,因而把数据进一步分解到附加的表中。(3)星系模式星系模式:多个事实表共享维表。这种模式可以看作星形模式集,因此称为星系模式,或事实星座。第8页,本讲稿共87页n n1.8 典型的典型的OLAP操作操作(1 1)OLAPOLAP是一种多维数据分析技术。包括汇总、合并和聚集是一种多维数据分析技术。包括汇总、合并和聚集等功能,以及从不同的角度观察信息的能力。等功能,以及从不同的角度观察信息的能力。(2 2)上卷上卷上卷上卷:从某一维度的更高概
9、念层次观察数据方,获得更概:从某一维度的更高概念层次观察数据方,获得更概要的数据。它通过沿维的概念分层向上或维归约来实现。要的数据。它通过沿维的概念分层向上或维归约来实现。(3 3)下钻下钻下钻下钻:下钻是上卷的逆操作。它从某一维度的更低概念层次观察:下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方,获得更详细的数据。下钻可以通过沿维的概念分层向下或数据方,获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。引入新的维来实现。(4 4)切片和切块切片和切块切片和切块切片和切块:切片操作在给定的数据方的选择一个维的部:切片操作在给定的数据方的选择一个维的部分属性,获得一个
10、较小的子数据方。切块操作通过对选择两分属性,获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性,获得一个较小的子数据方。个或多个维的部分属性,获得一个较小的子数据方。(5 5)转轴转轴转轴转轴:是一种改变数据方二维展现形式的操作。它将数据:是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维度由行改为列,或由列改为行。方的二维展现中的某些维度由行改为列,或由列改为行。第9页,本讲稿共87页二、数据准备n n现实世界的数据是不完整的不完整的(有些感兴趣的属性缺少属性值,或仅包含聚集数据),含噪音的含噪音的(包含错误,或存在偏离期望的异常值),不一致的不一致的(例如,用
11、于商品分类的部门编码存在差异)。n n需要数据清理数据清理、数据集成数据集成、数据选择数据选择、数据数据变换变换等技术对数据进行处理。第10页,本讲稿共87页n n2.1 维归约维归约/特征提取特征提取n n2.1-1 决策树归约决策树归约(1)决策树归约构造一个类似于流程图的结构:其每个非叶子结点表示一个属性上的测试,每个分枝对应于测试的一个输出;每个叶子结点表示一个决策类。(2)在每个结点,算法选择“当前对分类最有帮助”的属性,出现在树中的属性形成归约后的属性子集。第11页,本讲稿共87页n n2.1-2 粗糙集归约粗糙集归约(1)粗糙集理论在数学意义上描述了知识的不确定性,它的特点是把用
12、于分类的知识嵌入集合内,使分类与知识联系在一起。(2)知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。第12页,本讲稿共87页n n2.1-2 粗糙集归约(续)粗糙集归约(续)(3)令Q代表属性的集合。qQ是一个属性,如果IND(Qq)=IND(Q),则q在S中不是独立的;否则称q在S中是独立的。(4)若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的,则R被称为Q的一个“约简”,记作R=RED(Q)。(5)约简可以通过删除冗余的(不独立的)属性而获得,约简包含的属性即为“对分类有帮助”的属性。第13页,本讲稿共87页n n2.2 数据变换数据变换n n2.2-1 归
13、一化与模糊化归一化与模糊化有限区间的归一化:无限区间的归一化:模糊隶属度:第14页,本讲稿共87页n n2.2-2 核函数核函数(1)核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。(2)映射可以是显式的,也可以是隐式的。显式映射即找到一个映射关系f,使高维空间的特征向量f(x)可以被直接计算出来。(3)隐式映射,即引入一个核函数进行整体处理,就避免了对的直接求f(x)的计算困难。核函数即某高维特征空间中向量的内积,是核矩阵中的一个元素。(4)并不是所有的实值函数f(x)都可以作为空间映射的核函数,只有f(x)是某一特征空间的内积时,即符合Mercer条件,
14、它才能成为核函数。第15页,本讲稿共87页n n2.2-2 核函数(续)核函数(续)n n多项式函数:n n n n高斯(RBF)函数:n n n n多层感知机函数:n n低维空间向量映射到高维空间向量举例:第16页,本讲稿共87页n n2.3 数据压缩数据压缩n n2.3-1 离散化离散化n n离散化的用途:(1)适应某些仅接受离散值的算法;(2)减小数据的尺度。n n离散化的方法包括几下几种。n n(1)等距分割;n n(2)聚类分割;n n(3)直方图分割;n n(4)基于熵的分割;n n(5)基于自然属性的分割。第17页,本讲稿共87页n n2.3-2 回归回归n n回归和对数线性模型
15、可以用来近似给定的数据。n n在线性回归线性回归中,用一条直线来模拟数据的生成规则。n n多元回归多元回归是线性回归的扩展,涉及多个预测变量。n n在多项式回归多项式回归中,通过对变量进行变换,可以将非线性模型转换成线性的,然后用最小平方和法求解。第18页,本讲稿共87页n n2.3-2 回归(续)回归(续)n n利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。n n在广义线性模型中,因变量Y 的变化速率是Y 均值的一个函数;这一点与线性回归不同。常见的广义线性模型有:对数回归和泊松回归。n n对数回归模型对数回归模型是利用一些事件发生的概率作为自变量所
16、建立的线性回归模型。n n泊松回归模型泊松回归模型主要是描述数据出现次数的模型,因为它主要是描述数据出现次数的模型,因为它们常常表现为泊松分布。们常常表现为泊松分布。第19页,本讲稿共87页n n2.3-3 主成分分析(主成分分析(PCA)n nPCA算法搜索c个最能代表数据的个最能代表数据的k-k-维正交向量;这里维正交向量;这里c k k。这样,原来的数据投影到一个较小的空间,导致数据压缩。步骤如下:(1 1)对输入数据归一化,使得每个属性都落入相同的区)对输入数据归一化,使得每个属性都落入相同的区间。间。(2 2)PCAPCA计算计算c个规范正交向量,作为归一化输入数据的基。个规范正交向
17、量,作为归一化输入数据的基。这些是单位向量,每一个都垂直于另一个:称为主成分。这些是单位向量,每一个都垂直于另一个:称为主成分。输入数据是主要成分的线性组合。输入数据是主要成分的线性组合。(3 3)对主成分按)对主成分按“意义意义”或强度降序排列,选择部分主成分充当数据的一组新坐标轴。第20页,本讲稿共87页n n2.3-4 离散小波变换(离散小波变换(DWT)n n离散小波变换是一种线性离散小波变换是一种线性信号处理技术。该技术方法可以将一个数据向量转换为另一个数据向量(为小波相关系数);且两个向量具有相同长度。n n可以舍弃转换后的数据向量中的一些小波相关系数。保留可以舍弃转换后的数据向量
18、中的一些小波相关系数。保留所有大于用户指定阈值的小波系数,而将其它小波系数置所有大于用户指定阈值的小波系数,而将其它小波系数置为为0 0,以帮助提高数据处理的运算效率。,以帮助提高数据处理的运算效率。n n这一技术方法可以在保留数据主要特征情况下除去数据中这一技术方法可以在保留数据主要特征情况下除去数据中的噪声,因此该方法可以有效地进行数据清洗。的噪声,因此该方法可以有效地进行数据清洗。n n给定一组小波相关系数,利用离散小波变换的逆运算还可以近似恢复原来的数据。第21页,本讲稿共87页n n2.3-4 离散小波变换(续)离散小波变换(续)n n常用的小波函数包括Haar系列,Daubechi
19、es系列,Moret系列,Sym系列,Meyer系列,Coif系列。第22页,本讲稿共87页n n2.3-5 潜在语义分析潜在语义分析n n潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。n n(1 1)构造)构造“特征-样本”矩阵,矩阵,“特征-样本”矩阵中的每一列是对应于第i i个样本特征向量;个样本特征向量;n n(2)对该矩阵进行奇异值分解(SVD);n n(3)用最大的k k个奇异值所对应的个奇异值所对应的“特征-语义”矩阵矩阵Uk和和“样本-语义”矩阵矩阵VkVk以及最大的k k个奇异值重构个奇异值重构“特征特征-样本样本”矩阵。矩阵。下面两式分别代表在下面两
20、式分别代表在语义空间特征与特征语义空间特征与特征之间的距离和之间的距离和在语义在语义空间空间样本与样本之样本与样本之间的距离间的距离第23页,本讲稿共87页n n2.3-6 聚类分析聚类分析n n聚类技术将数据元组视为对象。它将对象划分为聚类,使在一个聚类中的对象“类似”,但与其它聚类中的对象“不类似”。n n通常,类似性基于距离,用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示;而直径是一个聚类中两个任意对象的最大距离。n n质心距离是聚类质量的另一种度量,它定义为由聚类质心(表示“平均对象”,或聚类空间中的平均点)到每个聚类对象的平均距离。第24页,本讲稿共87页n n2
21、.3-6 聚类分析(续)聚类分析(续)k-means算法k-medoids算法第25页,本讲稿共87页三、数据挖掘算法n n数据挖掘算法按挖掘目的可分为:数据挖掘算法按挖掘目的可分为:(1)概念描述(总结,对比等)(2)关联规则分析(3)分类与预测 (信息自动分类,信息过滤,图像识别等)(4)聚类分析(5)异常分析(入侵检测,金融安全等)(6)趋势、演化分析(回归,序列模式挖掘)第26页,本讲稿共87页n n按训练方式,机器学习可分为:按训练方式,机器学习可分为:按训练方式,机器学习可分为:按训练方式,机器学习可分为:(1 1)有监督的学习;有训练样本,学习机通过学习获得训练样本包含的知识,并
22、用其作为判断测试样本的类别的依据。(2)无监督的学习无监督的学习:无训练样本,仅根据测试样本的在特:无训练样本,仅根据测试样本的在特征空间分布情况判断其类别。征空间分布情况判断其类别。(3 3)半监督的学习半监督的学习:有少量训练样本,学习机以从训练样本:有少量训练样本,学习机以从训练样本获得的知识为基础,结合测试样本的分布情况逐步修正已有获得的知识为基础,结合测试样本的分布情况逐步修正已有知识,并判断测试样本的类别。知识,并判断测试样本的类别。(4 4)强化学习强化学习:没有训练样本,但有对学习机每一步是否更接近目标的奖惩措施。第27页,本讲稿共87页n n有监督的学习n n半监督的学习n
23、n无监督的学习第28页,本讲稿共87页n n3.1 关联规则挖掘关联规则挖掘n n关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设I I=i i1,i,i2,.,im 是项的集合。设任务相关的数据D D是数据库事务的集合,其中每个事务T T是项的集合,使得是项的集合,使得T T I I。设A是一个项集,事务T T包含包含A当且仅当当且仅当A T T。n n关联规则关联规则关联规则关联规则是形如是形如A A B B的蕴涵式,其中A I,B I I,并且A B B=。规则A B在事务集D中成立,具有中成立,具有支持度支持度s,其中,其中s是D中事务包含中事务包含A B B的百分比。即,的
24、百分比。即,P(A B)B)。规则规则A A B在事务集在事务集D D中具有置信度c c,如果D中包含A的事务同时也包含B B的百分比是c。这是条件概率P P(B|A)。即n nsupport support(A B B)=)=P P(A A B)n nconfidence(A A B)=P P(B|A)第29页,本讲稿共87页n n3.1 关联规则挖掘(续)关联规则挖掘(续)n nApriori性质:频繁项集的所有非空子集都必须也是频:频繁项集的所有非空子集都必须也是频繁的。繁的。n nAprioriApriori性质基于如下观察:根据定义,如果项集性质基于如下观察:根据定义,如果项集I不满
25、足不满足最小支持度阈值最小支持度阈值s,则,则I不是频繁的,即P(I)s s。如果。如果项项A A添加到I I,则结果项集(即I I A)不可能比I更频繁更频繁出现。因此,出现。因此,I I A也不是频繁的,即P(I I A A)s。n n该性质表明如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试。n n将Apriori性质应用于算法:下面算法的两个主要步过程由连接和剪枝组成。组成。第30页,本讲稿共87页n n3.1 关联规则挖掘(续)关联规则挖掘(续)n n连接步连接步:为找L Lk k,通过Lk-1与自己连接产生候选与自己连接产生候选k k-项集的集合。该候选项集的集合记作
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 挖掘 算法 基础 适合 入门
限制150内