数据挖掘算法.

数据挖掘算法WangYe2006.8一、概念和术语1.1数据挖掘/知识发现（1）数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。（2）数据挖掘，又称为数据库中知识发现（KnowledgeDiscoveryinDatabases）或知识发现，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。（3）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。（4）数据库查询系统和专家系统不是数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。1.2机器学习（1）对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么这个计算机程序被称为在从经验E学习。（2）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。1.3数据挖掘的对象（1）关系型数据库、事务型数据库、面向对象的数据库；（2）数据仓库/多维数据库；（3）空间数据（如地图信息）（4）工程数据（如建筑、集成电路的信息）（5）文本和多媒体数据（如文本、图象、音频、视频数据）（6）时间相关的数据（如历史数据或股票交换数据）（7）万维网（如半结构化的HTML，结构化的XML以及其他网络信息）1.4数据挖掘的步骤（1）数据清理（消除噪音或不一致数据，补缺）；（2）数据集成（多种数据源可以组合在一起）；（3）数据选择（从数据库中提取相关的数据）；（4）数据变换（变换成适合挖掘的形式）；（5）数据挖掘（使用智能方法提取数据模式）；（6）模式评估（识别提供知识的真正有趣模式）；（7）知识表示（可视化和知识表示技术）。1.5支持数据挖掘的关键技术（1）数据库/数据仓库/OLAP（2）数学/统计（回归分析：多元回归、自回归；判别分析：Bayes判别、Fisher判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）（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(Q−q)=IND(Q)，则q在S中不是独立的；否则称q在S中是独立的。（4）若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的，则R被称为Q的一个“约简”，记作R=RED(Q)。（5）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。2.2数据变换2.2-1归一化与模糊化有限区间的归一化：无限区间的归一化：模糊隶属度：minmaxminvv'vev11'2.2-2核函数（1）核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。（2）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系f，使高维空间的特征向量f(x)可以被直接计算出来。（3）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求f(x)的计算困难。核函数即某高维特征空间中向量的内积，是核矩阵中的一个元素。（4）并不是所有的实值函数f(x)都可以作为空间映射的核函数，只有f(x)是某一特征空间的内积时，即符合Mercer条件，它才能成为核函数。)',(K)'(),(ijxxKxfxf2.2-2核函数（续）多项式函数：高斯（RBF）函数：多层感知机函数：低维空间向量映射到高维空间向量举例：dxxxxK)',1()',()/||'||exp()',(22xxxxK)',tanh()',(21kxxkxxK],2,[],[22212121xxxxxx2.3数据压缩2.3-1离散化离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。离散化的方法包括几下几种。（1）等距分割；（2）聚类分割；（3）直方图分割；（4）基于熵的分割；（5）基于自然属性的分割。2.3-2回归回归和对数线性模型可以用来近似给定的数据。在线性回归中，用一条直线来模拟数据的生成规则。多元回归是线性回归的扩展，涉及多个预测变量。在多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。XY2211XXY33221XXXY2.3-2回归（续）利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。在广义线性模型中，因变量Y的变化速率是Y均值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。对数回归模型是利用一些事件发生的概率作为自变量所建立的线性回归模型。泊松回归模型主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。2.3-3主成分分析（PCA）PCA算法搜索c个最能代表数据的k-维正交向量；这里ck。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：（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个奇异值重构“特征-样本”矩阵。TVUATkkkkVUATkkkkTkkkTkkkkTkVVVUUVAATkkkkTkkkTkkkTkkUUUVVUAA下面两式分别代表在语义空间特征与特征之间的距离和在语义空间样本与样本之间的距离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是项的集合，使得TI。设A是一个项集，事务T包含A当且仅当AT。关联规则是形如AB的蕴涵式，其中AI，BI，并且AB=。规则AB在事务集D中成立，具有支持度s，其中s是D中事务包含AB的百分比。即，P(AB)。规则AB在事务集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比是c。这是条件概率P(B|A)。即support(AB)=P(AB)confidence(AB)=P(B|A)3.1关联规则挖掘（续）Apriori性质：频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值s，