转载 数据挖掘算法Word文档格式.docx
- 文档编号:4753819
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:26
- 大小:35.32KB
转载 数据挖掘算法Word文档格式.docx
《转载 数据挖掘算法Word文档格式.docx》由会员分享,可在线阅读,更多相关《转载 数据挖掘算法Word文档格式.docx(26页珍藏版)》请在冰点文库上搜索。
粗糙集)
(3)机器学习(聚类分析;
关联规则;
决策树;
范例推理;
贝叶斯网络;
神经网络;
支持向量机;
遗传算法)
(4)可视化:
将数据,知识和规则转化为图形表现的形式.
1.6数据仓库
(1)数据仓库是一个面向主题的,集成的,随时间变化的,非易失性数据的集合,用于支持管理人员的决策.
(2)数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储,以支持管理决策.数据仓库技术包括数据清理,数据集成和联机分析处理(OLAP).
(3)数据仓库的逻辑结构是多维数据库.数据仓库的实际物理结构可以是关系数据存储或多维数据方(Cube).
(4)数据方是由维度(Dimension)和度量(Measure)定义的一种数据集,度量存放在由维度索引的数据方单元中.维度对应于模式中的属性组,度量对应于与主题相关的事实数据.数据方的物化是指预计算并存储全部或部分单元中的度量.
1.7数据仓库的模型
(1)星形模式:
最常见模型;
其中数据仓库包括一个大的,包含大批数据,不含冗余的中心表(事实表);
一组小的附属表(维表),每维一个.
(2)雪花模式:
雪花模式是星型模式的变种,其中某些维表是规范化的,因而把数据进一步分解到附加的表中.
(3)星系模式:
多个事实表共享维表.这种模式可以看作星形模式集,因此称为星系模式,或事实星座.
1.8典型的OLAP操作
(1)OLAP是一种多维数据分析技术.包括汇总,合并和聚集等功能,以及从不同的角度观察信息的能力.
(2)上卷:
从某一维度的更高概念层次观察数据方,获得更概要的数据.它通过沿维的概念分层向上或维归约来实现.
(3)下钻:
下钻是上卷的逆操作.它从某一维度的更低概念层次观察数据方,获得更详细的数据.下钻可以通过沿维的概念分层向下或引入新的维来实现.
(4)切片和切块:
切片操作在给定的数据方的选择一个维的部分属性,获得一个较小的子数据方.切块操作通过对选择两个或多个维的部分属性,获得一个较小的子数据方.
(5)转轴:
是一种改变数据方二维展现形式的操作.它将数据方的二维展现中的某些维度由行改为列,或由列改为行.
二,数据准备
现实世界的数据是不完整的(有些感兴趣的属性缺少属性值,或仅包含聚集数据),含噪音的(包含错误,或存在偏离期望的异常值),不一致的(例如,用于商品分类的部门编码存在差异).
需要数据清理,数据集成,数据选择,数据变换等技术对数据进行处理.
2.1维归约/特征提取
2.1-1决策树归约
(1)决策树归约构造一个类似于流程图的结构:
其每个非叶子结点表示一个属性上的测试,每个分枝对应于测试的一个输出;
每个叶子结点表示一个决策类.
(2)在每个结点,算法选择"
当前对分类最有帮助"
的属性,出现在树中的属性形成归约后的属性子集.
2.1-2粗糙集归约
(1)粗糙集理论在数学意义上描述了知识的不确定性,它的特点是把用于分类的知识嵌入集合内,使分类与知识联系在一起.
(2)知识的粒度,不可分辨关系,上近似,下近似,边界等概念见下图.
2.1-2粗糙集归约(续)
(3)令Q代表属性的集合.q∈Q是一个属性,如果IND(Qq)=IND(Q),则q在S中不是独立的;
否则称q在S中是独立的.
(4)若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的,则R被称为Q的一个"
约简"
记作R=RED(Q).
(5)约简可以通过删除冗余的(不独立的)属性而获得,约简包含的属性即为"
对分类有帮助"
的属性.
2.2数据变换
2.2-1归一化与模糊化
有限区间的归一化:
无限区间的归一化:
模糊隶属度:
2.2-2核函数
(1)核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去.
(2)映射可以是显式的,也可以是隐式的.显式映射即找到一个映射关系f,使高维空间的特征向量f(x)可以被直接计算出来.
(3)隐式映射,即引入一个核函数进行整体处理,就避免了对的直接求f(x)的计算困难.核函数即某高维特征空间中向量的内积,是核矩阵中的一个元素.
(4)并不是所有的实值函数f(x)都可以作为空间映射的核函数,只有f(x)是某一特征空间的内积时,即符合Mercer条件,它才能成为核函数.
2.2-2核函数(续)
多项式函数:
高斯(RBF)函数:
多层感知机函数:
低维空间向量映射到高维空间向量举例:
2.3数据压缩
2.3-1离散化
离散化的用途:
(1)适应某些仅接受离散值的算法;
(2)减小数据的尺度.
离散化的方法包括几下几种.
(1)等距分割;
(2)聚类分割;
(3)直方图分割;
(4)基于熵的分割;
(5)基于自然属性的分割.
2.3-2回归
回归和对数线性模型可以用来近似给定的数据.
在线性回归中,用一条直线来模拟数据的生成规则.
多元回归是线性回归的扩展,涉及多个预测变量.
在多项式回归中,通过对变量进行变换,可以将非线性模型转换成线性的,然后用最小平方和法求解.
2.3-2回归(续)
利用线性回归可以为连续取值的函数建模.广义线性模型则可以用于对离散取值变量进行回归建模.
在广义线性模型中,因变量Y的变化速率是Y均值的一个函数;
这一点与线性回归不同.常见的广义线性模型有:
对数回归和泊松回归.
对数回归模型是利用一些事件发生的概率作为自变量所建立的线性回归模型.
泊松回归模型主要是描述数据出现次数的模型,因为它们常常表现为泊松分布.
2.3-3主成分分析(PCA)
PCA算法搜索c个最能代表数据的k-维正交向量;
这里ck.这样,原来的数据投影到一个较小的空间,导致数据压缩.步骤如下:
(1)对输入数据归一化,使得每个属性都落入相同的区间.
(2)PCA计算c个规范正交向量,作为归一化输入数据的基.这些是单位向量,每一个都垂直于另一个:
称为主成分.输入数据是主要成分的线性组合.
(3)对主成分按"
意义"
或强度降序排列,选择部分主成分充当数据的一组新坐标轴.
2.3-4离散小波变换(DWT)
离散小波变换是一种线性信号处理技术.该技术方法可以将一个数据向量转换为另一个数据向量(为小波相关系数);
且两个向量具有相同长度.
可以舍弃转换后的数据向量中的一些小波相关系数.保留所有大于用户指定阈值的小波系数,而将其它小波系数置为0,以帮助提高数据处理的运算效率.
这一技术方法可以在保留数据主要特征情况下除去数据中的噪声,因此该方法可以有效地进行数据清洗.
给定一组小波相关系数,利用离散小波变换的逆运算还可以近似恢复原来的数据.
2.3-4离散小波变换(续)
常用的小波函数包括Haar系列,Daubechies系列,Moret系列,Sym系列,Meyer系列,Coif系列.
2.3-5潜在语义分析
潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系.
(1)构造"
特征-样本"
矩阵,"
矩阵中的每一列是对应于第i个样本特征向量;
(2)对该矩阵进行奇异值分解(SVD);
(3)用最大的k个奇异值所对应的"
特征-语义"
矩阵Uk和"
样本-语义"
矩阵Vk以及最大的k个奇异值重构"
矩阵.
下面两式分别代表在语义空间特征与特征之间的距离和在语义空间样本与样本之间的距离
2.3-6聚类分析
聚类技术将数据元组视为对象.它将对象划分为聚类,使在一个聚类中的对象"
类似"
但与其它聚类中的对象"
不类似"
.
通常,类似性基于距离,用对象在空间中的"
接近"
程度定义.聚类的"
质量"
可以用"
直径"
表示;
而直径是一个聚类中两个任意对象的最大距离.
质心距离是聚类质量的另一种度量,它定义为由聚类质心(表示"
平均对象"
或聚类空间中的平均点)到每个聚类对象的平均距离.
2.3-6聚类分析(续)
k-means算法
k-medoids算法
三,数据挖掘算法
数据挖掘算法按挖掘目的可分为:
(1)概念描述(总结,对比等)
(2)关联规则分析
(3)分类与预测
(信息自动分类,信息过滤,图像识别等)
(4)聚类分析
(5)异常分析(入侵检测,金融安全等)
(6)趋势,演化分析(回归,序列模式挖掘)
按训练方式,机器学习可分为:
(1)有监督的学习;
有训练样本,学习机通过学习获得训练样本包含的知识,并用其作为判断测试样本的类别的依据.
(2)无监督的学习:
无训练样本,仅根据测试样本的在特征空间分布情况判断其类别.
(3)半监督的学习:
有少量训练样本,学习机以从训练样本获得的知识为基础,结合测试样本的分布情况逐步修正已有知识,并判断测试样本的类别.
(4)强化学习:
没有训练样本,但有对学习机每一步是否更接近目标的奖惩措施.
有监督的学习
半监督的学习
无监督的学习
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)
3.1关联规则挖掘(续)
Apriori性质:
频繁项集的所有非空子集都必须也是频繁的.
Apriori性质基于如下观察:
根据定义,如果项集I不满足最小支持度阈值s,则I不是频繁的,即P(I)s.如果项A添加到I,则结果项集(即IA)不可能比I更频繁出现.因此,IA也不是频繁的,即P(IA)s.
该性质表明如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试.
将Apriori性质应用于算法:
下面算法的两个主要步过程由连接和剪枝组成.
连接步:
为找Lk,通过Lk-1与自己连接产生候选k-项集的集合.该候选项集的集合记作Ck.Ck是Lk的超集.扫描数据库,确定Ck中每个候选的计数,将令计数值不小于最小支持度计数的(频繁的)所有候选加入Lk.
剪枝步:
但Ck可能很大,这样所涉及的计算量就很大.根据Apriori性质如果一个候选k-项集的(k-1)-子集不在Lk-1中,则该候选也不可能是频繁的,从而可以由Ck中删除.
Apriori性质(逆反描述):
任何非频繁的(k-1)-项集都不是可能是频繁k-项集的子集.
3.2决策树
决策树学习是归纳推理算法.它是一种逼近离散函数的方法,且对噪声数据有很好的健壮性.在这种方法中学习到的知识被表示为决策树,决策树也能再被表示为多个if-then的规则,以提高可读性.
基本决策树算法就是一个贪心算法.它采用自上而下,分而制之的递归方式来构造一个决策树
通常,决策树是一种自顶向下增长树的贪婪算法,在每个结点选取能最好地分类样例的属性.继续这个过程直到这棵树能完美分类训练样例,或所有的属性都使用过了."
信息增益"
用于衡量属性的价值.熵(entropy)是一种度量信息增益的指标,它描述了样本的纯度(purity).下面是熵的定义:
Entropy=-∑Pilog2Pi3.2决策树(续)
注意点:
(1)避免过度拟合,应该适度剪枝;
(2)连续值的离散化;
(3)处理缺失值的方法:
最常见值,按概率分配;
(4)处理权重不同的属性
常用实现算法:
CART,ID3,ASSISTANT,C4.53.3人工神经网络
人工神经网络(ArtificialNeuralNetworks)提供了一种普遍而且实用的方法,来从样例中学习值为实数,离散或向量的函数.
反向传播(BackPropagation)这样的算法使用梯度下降来调节网络参数以最佳拟合由输入/输出对组成的训练集合.
BP网络的学习方法和目标:
对网络的连接权值进行调整,使得对任一输入都能得到所期望的输出.
常用的非线性作用函数是Sigmoid函数,即f(x)=1/(1+e-x).在神经网络模型中,大量神经元节点按一定体系结构连接成网状.神经网络一般都具有输入层,隐层和输出层.
每个神经元都是一个结构相似的独立单元,它接受前一层传来的数据,并将这些数据的加权和输入非线性作用函数中,最后将非线性作用函数的输出结果传递给后一层.
误差反向传播的过程
3.3人工神经网络(续)
自适应共振理论模型(ART)--聚类
连续/离散Hopfield神经网络--求近似最优解,识别与分类
双向联想记忆模型(BAM)--识别
玻尔兹曼机(BM)--求最优解
脑中盒模型(BSB)--识别与分类
自组织映射模型(SOM)--识别与分类
对向传播网络模型(CPN)--识别与分类
小脑模型(CMAC)--快速识别
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是苹果的确信程度.
朴素贝叶斯分类能够奏效的前提是,P(X|H)相对比较容易计算.假定X表示红色和圆的,H表示假定X是苹果;
则P(X|H)表示已知苹果,它既红又圆的概率.
3.5期望最大化(EM)
期望最大化(EM)方法和朴素贝叶斯方法有着共同的理论基础.期望最大化是一种基于循环过程的最大似然参数估计方法,用于解决带缺失数据的参数估计问题.
样本数据分为标记样本和未标记样本,按照统计的观点,对于每一个样本的产生,其背后都有一个模型,即样本生成模型.样本生成模型的参数先由标记样本确定,再通过标记样本和利用当前模型判断标记的未标记样本共同调整.
3.5期望最大化(续)
如果参数适当,EM算法能得到较好的分类结果,但计算速度相对较慢.其具体的步骤如下:
一,初始参数估计,将未标记的样本按朴素贝叶斯分类方法进行类标注.
二,反复迭代E步骤和M步骤,直到收敛.
三,E步骤:
对于每个未标记的样本,按下式计算类标记的期望值.
四,M步骤:
利用E步骤计算出的期望值,按下式用已标记样本和未标记样本重新估计新的分类器参数.
3.6K-最近邻分类
K-近邻(K-NN)分类是基于范例的分类方法,它的基本思想是:
给定待分类样本后,考虑在训练样本集中与该待分类样本距离最近(最相似)的K个样本,根据这K个样本中大多数样本所属的类别判定待分类样本的类别.
它的特例是1-NN,即分类时选出待分类样本的最近邻,并以此最近邻的类标记来判断样本的类.
K-NN算法的优点在于它有较高的精确程度,研究表明,K-NN的分类效果要明显好于朴素贝叶斯分类,决策树分类.
3.6K-最近邻分类(续)
最近邻分类的算法步骤如下:
一,以向量空间模型的形式描述各训练样本.
二,在全部训练样本集中选出与待分类样本最相似的K个样本.K值的确定目前没有很好的方法,一般采用先定一个100左右的初始值,然后再调整.
三,将待分类样本标记为其K个邻居中所属最多的那个类别中.
3.7遗传算法
遗传算法易于并行处理,其依据是自然界进化和适者生存的原则.遗传学习开始如下:
创建若干个由随机产生的个体组成的初始群体.每个个体用一个二进位串表示.
形成由当前群体中最适合的个体组成新的群体,以及这些规则的子女.个体的适合度用某一目标函数来评估.
子女通过使用诸如交叉和变异等遗传操作来创建.在交叉操作中,来自个体对的子串交换,形成新的个体对.在变异操作中,个体中随机选择的位被反转.
3.7遗传算法(续)
Fitness:
适应度评分函数,为给定假设赋予一个评估得分.
Fitness_threshold:
指定终止判据的阈值.
p:
群体中包含的假设数量.r:
每一步中通过交叉取代群体成员的比例.m:
变异率.
初始化群体:
P随机产生的p个假设
评估:
对于P中的每一个h,计算Fitness(h)
当[Fitness(h)]产生新的一代PS:
选择:
用概率方法选择P的(1-r)p个成员加入PS.从P中选择假设hi的概率P(hi)通过下面公式计算:
交叉:
根据上面给出的P(hi),从P中按概率选择rp/2对假设.对于每一对假设应用交叉算子产生两个后代.把所有的后代加入PS.
变异:
使用均匀的概率从PS中选择m百分比的成员.对于选出的每个成员,在它的表示中随机选择一个位取反.
更新:
PPS.
对于P中的每一个h计算Fitness(h)
从P中返回适应度最高的假设.
3.8聚类分析
为达到全局最优,基于划分的聚类会要求穷举所有可能的划分.聚类技术将数据元组视为对象.它将对象划分为群或聚类,使得在一个聚类中的对象"
绝大多数应用采用了以下两个比较流行的基于划分的方法,这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用.
(1)k-means算法,在该算法中,每个簇用该簇中对象的平均值来表示.
(2)k-medoids算法,在该算法中,每个簇用接近聚类中心的一个对象来表示.
3.8聚类分析(续)
常用的相似程度度量
余弦夹角:
Dice系数:
Jaccard系数:
基于层次的方法:
层次的方法对给定数据集合进行层次的分解.根据层次的分解如何形成,层次的方法可以被分为凝聚或分裂方法.(Chameleon,CURE,BIRCH)
基于密度的方法:
只要临近区域的密度超过某个阈值,就继续聚类.避免仅生成球状聚类.(DBSCAN,OPTICS,DENCLUE)
基于网格的方法:
基于网格的方法把对象空间量化为有限数目的单元,所有的聚类操作都在这个量化的空间上进行.这种方法的主要优点是它的处理速度很快.(STING,CLIQUE,WaveCluster)
基于模型的方法:
为每个簇假设一个模型,发现数据对模型的最好匹配.(COBWEB,CLASSIT,AutoClass)
3.9隐马尔可夫模型
对于一个随机事件,有一个观察值序列:
O1,.,OT.该事件隐含着一个状态序列:
X1,.,XT
假设1:
马尔可夫性,P(Xi|Xi-1…X1)=P(Xi|Xi-1)
假设2:
不动性,P(Xi+1|Xi)=P(Xj+1|Xj),对任意i,j成立
假设3:
输出独立性,P(O1,.,OT|X1,.,XT)=∏P(Ot|Xt)
一个隐马尔可夫模型是一个五元组:
(ΩX,ΩO,A,B,π)
其中:
ΩX={Q1,.,QN}:
状态的有限集合;
ΩO={V1,.,VM}:
观察值的有限集合;
A={aij},aij=P(Xt+1=Qj|Xt=Qi):
转移概率;
B={bik},bik=P(Ot=Vk|Xt=Qi):
输出概率;
π={πi},πi=P(X1=Qi):
初始状态分布.
3.9隐马尔可夫模型(续)
令λ={A,B,π}为给定HMM的参数,
令σ=O1,.,OT为观察值序列,
隐马尔可夫模型的三个基本问题:
评估问题:
对于给定模型,求某个观察值序列的概率P(σ|λ).向前/向后算法:
定义向前/向后变量.采用动态规划算法,复杂度O(N2T)
解码问题:
对于给定模型和观察值序列,求可能性最大的状态序列.Viterbi算法:
采用动态规划算法,复杂度O(N2T)
学习问题:
对于给定的一个观察值序列,调整参数λ,使得观察值出现的概率P(σ|λ)最大.向前EM算法的一个特例,带隐变量的最大似然估计.Baum-Welch算法.
向前/向后算法:
定义向前/向后变量:
初始化:
递归:
终结:
Viterbi算法
求S序列:
Baum-Welch算法
主要步骤:
1.初始模型(待训练模型)l0,
2.基于l0以及观察值序列s,训练新模型l;
3.如果log_P(X|l)-log(P(X|l0)Delta,说明训练已经达到预期效果,算法结束.
4.否则,令l0=l,继续第2步工作
3.10支持向量机
支持向量机基本模型是针对线性可分情况下的最优分界面提出的.在这一条件下,正类和反类训练样本可用超平面完全正确地分开.
设线性可分样本集合为(xi,yi),i=1,…,n;
x∈Rd,y∈{+1,-1}是类别标记.支持向量机工作的机理可描述为:
寻找一个超平面w·
x+b=0,该平面把两类训练样本点完全正确地分开,即满足且;
同时满足两类训练点到此超平面的最近距离之和,即"
间隔"
(Margin),达到最大.
满足上述条件的分界面就是最优分界面,经过两类样本中距离最优分类面最近的点,且平行于最优分界面的超平面H1,H2(边界超平面)上的训练样本称为支持向量,即图中带圈的点.
3.10支持向量机(续)
根据最近距离之和最大以及正确分离两类样本这两个条件,可以构造约束极值问题:
见
(1)式.
通过拉格朗日乘数法并引入拉格朗日乘数,该约束极值问题就可以转化成一个求解较为简单的对偶问题,通过寻求该对偶问题的最优解,就
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 转载 数据挖掘算法 数据 挖掘 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)