《数据挖掘技术》PPT课件.ppt

于 金 霞 计算机科学与技术学院,信息管理与信息系统专业课程,第三讲 数据挖掘技术,主要内容,一、数据挖掘概述 二、数据预处理 三、数据挖掘算法分类与预测 四、数据挖掘算法聚类 五、数据挖掘算法关联分析 六、序列模式挖掘 七、数据挖掘软件 八、数据挖掘应用,一、数据挖掘概述,数据挖掘概念,数据挖掘-从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。 数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构； 数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。,数据挖掘与KDD,数据挖掘与KDD,知识发现（KD） 输出的是规则 数据挖掘（DM） 输出的是模型 共同点 两种方法输入的都是学习集（learning sets） 目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全自动化，只能半自动化,数据挖掘的社会需求,国民经济和社会的信息化,社会信息化后，社会的运转是软件的运转 社会信息化后，社会的历史是数据的历史,数据挖掘的社会需求,有价值的知识,可怕的数据,数据挖掘的社会需求,数据爆炸，知识贫乏,数据挖掘的发展,1989 IJCAI会议： 数据库中的知识发现讨论专题 Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991) 1991-1994 KDD讨论专题 Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996) 1995-1998 KDD国际会议 (KDD95-98) Journal of Data Mining and Knowledge Discovery (1997) 1998 ACM SIGKDD, SIGKDD1999-2002 会议,以及SIGKDD Explorations 数据挖掘方面更多的国际会议 PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.,数据挖掘技术,技术分类 预言（Predication）：用历史预测未来 描述（Description）：了解数据中潜在的规律 数据挖掘技术 关联分析 序列模式 分类（预言） 聚集 异常检测,异常检测,异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。 异常探测应用 电信和信用卡欺骗 贷款审批 药物研究 气象预报 金融领域 客户分类 网络入侵检测 故障检测与诊断等,什么是异常（outlier）？,Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。 聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。 异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。,异常检测方法的分类,基于统计（statistical-based)的方法 基于距离 (distance-based)的方法 基于偏差(deviation-based)的方法 基于密度(density-based)的方法 高维数据的异常探测,数据挖掘系统的特征,数据的特征 知识的特征 算法的特征,矿山（数据）,挖掘工具（算法）,金子（知识）,数据的特征,大容量 POS数据（某个超市每天要处理高达2000万笔交易） 卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据） 互联网数据 含噪音（不完全、不正确） 异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）,系统的特征,知识发现系统需要一个前处理过程 数据抽取 数据清洗 数据选择 数据转换 知识发现系统是一个自动/半自动过程 知识发现系统要有很好的性能,知识（模式）的特征,知识发现系统能够发现什么知识？ 计算学习理论COLT（Computational Learning Theory） 以FOL为基础的以发现关系为目的的归纳逻辑程序设计 现行的知识发现系统只能发现特定模式的知识 规则 分类 关联,知识表示：规则,IF 条件 THEN 结论 条件和结论的粒度（抽象度）可以有多种 单值 区间 模糊值 规则可以有确信度 精确规则 概率规则,知识表示：分类树,分类条件1,分类条件2,分类条件3,类1,类2,类3,类4,数据挖掘算法的特征,构成数据挖掘算法的三要素 模式记述语言：反映了算法可以发现什么样的知识 模式评价：反映了什么样的模式可以称为知识 模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索,数据挖掘的主要方法,分类（Classification） 聚类(Clustering) 相关规则(Association Rule) 回归(Regression) 其他,数据挖掘系统,数据挖掘系统,第一代数据挖掘系统 支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valued data），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。 第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。,数据挖掘系统,第三代数据挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。 第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 。,二、数据预处理,为什么需要预处理,数据 不完整 含观测噪声 不一致 包含其它不希望的成分 数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。,污染数据形成的原因,滥用缩写词 数据输入错误 数据中的内嵌控制信息 不同的惯用语 重复记录 丢失值 拼写变化 不同的计量单位 过时的编码 含有各种噪声,数据清理的重要性,污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。 垃圾进、垃圾出,数据清理处理内容,格式标准化 异常数据清除 错误纠正 重复数据的清除,数据规约,数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果 主要策略: 数据聚集 维规约 数据压缩 数值规约,空缺值,忽略元组 人工填写空缺值 使用固定值 使用属性平均值 使用最有可能值,噪声数据,如何平滑数据，去掉噪声 数据平滑技术 分箱 聚类 计算机和人工检查相结合 回归,分箱,箱的深度：表示不同的箱里有相同个数的数据。 箱的宽度：每个箱值的取值区间是个常数。 平滑方法: 按箱平均值平滑 按箱中值平滑 按箱边界值平滑,聚类,每个簇中的数据用其中心值代替 忽略孤立点 先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。 人工再审查这些孤立点,回归,通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。 线性回归 多线性回归,数据集成,将多个数据源中的数据结合起来存放在一个一直得数据存贮中。 实体识别 实体和模式的匹配 冗余：某个属性可以由别的属性推出。 相关分析 相关性rA,B . rA,B0,正相关。A随B的值得增大而增大 rA,B0,正相关。AB无关 rA,B0,正相关。A随B的值得增大而减少 重复 同一数据存储多次 数据值冲突的检测和处理,数据变换,平滑 聚集 数据概化 规范化 属性构造(特征构造),最小 最大规范化 小数定标规范化 属性构造 由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解,规范化,数据立方体聚集,寻找感兴趣的维度进行再聚集,维规约,删除不相关的属性（维）来减少数据量。 属性子集选择 找出最小属性集合，使得数据类的概率分布尽可能地接近使用所有属性的原分布 如何选取？ 贪心算法 逐步向前选择 逐步后向删除 向前选择和后向删除相结合 判定树归纳,数据压缩,有损，无损 小波变换 将数据向量D转换成为数值上不同的小波系数的向量D. 对D进行剪裁，保留小波系数最强的部分。,主要成分分析,数值规约,回归和对数线形模型 线形回归 对数线形模型 直方图 等宽 等深 V-最优 maxDiff,数值规约,聚类 多维索引树 ： 对于给定的数据集合，索引树动态的划分多维空间。 选样 简单选择n个样本，不放回 简单选择n个样本，放回 聚类选样 分层选样,离散化和概念分层,离散化技术用来减少给定连续属性的个数 通常是递归的。 大量时间花在排序上。 对于给定的数值属性，概念分层定义了该属性的一个离散化的值。 分箱 直方图分析,数值数据离散化,聚类分析 基于熵的离散化 通过自然划分分段 3-4-5规则 如果一个区间最高有效位上包括3 6 9 个不同的值，划分为3个等宽区间。 7个不同值，按2-3-3划分为3个区间 最高位包含2，4，8个不同值，划分为4个等宽区间 最高位包含1 ，5，10个不同值，划分为5个等宽区间 最高分层一般在第5个百分位到第95个百分位上进行,分类数据的概念分层生成,分类数据是离散数据。一个分类属性可能有有限个不同的值。 方法 由用户和专家在模式级显式的说明属性的部分序 通过显式的数据分组说明分层结构的一部分 说明属性集，但不说明他们的偏序 只说明部分的属性集,三、数据挖掘算法分类与预测,分类 VS. 预测,分类： 预测分类标号（或离散值） 根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据 预测： 建立连续函数值模型，比如预测空缺值 典型应用 信誉证实 目标市场 医疗诊断 性能预测,数据分类：两步过程,第一步，建立一个模型，描述预定数据类集和概念集 假定每个元组属于一个预定义的类，由一个类标号属性确定 基本概念 训练数据集：由为建立模型而被分析的数据元组形成 训练样本：训练数据集中的单个样本（元组） 学习模型可以用分类规则、判定树或数学公式的形式提供 第二步，使用模型，对将来的或未知的对象进行分类 首先评估模型的预测准确率 对每个测试样本，将已知的类标号和该样本的学习模型类预测比较 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比 测试集要独立于训练样本集，否则会出现“过分适应数据”的情况,第一步：建立模型,训练数 据集,分类算法,IF rank = professor OR years 6 THEN tenured = yes,分类规则,第二步：用模型进行分类,分类规则,测试集,未知数据,(Jeff, Professor, 4),Tenured?,准备分类和预测的数据,通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性 数据清理 消除或减少噪声，处理空缺值，从而减少学习时的混乱 相关性分析 数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确 数据变换 可以将数据概化到较高层概念，或将数据进行规范化,比较分类方法,使用下列标准比较分类和预测方法 预测的准确率：模型正确预测新数据的类编号的能力 速度：产生和使用模型的计算花销 鲁棒性：给定噪声数据或有空缺值的数据，模型正确预测的能力 可伸缩性：对大量数据，有效的构建模型的能力 可解释性：学习模型提供的理解和洞察的层次,用判定树归纳分类,什么是判定树？ 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 每个树叶节点代表类或类分布 判定树的生成由两个阶段组成 判定树构建 开始时，所有的训练样本都在根节点 递归的通过选定的属性，来划分样本 （必须是离散值） 树剪枝 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝 判定树的使用：对未知样本进行分类 通过将样本的属性值与判定树相比较,判定归纳树算法,判定归纳树算法（一个贪心算法） 自顶向下的分治方式构造判定树 树以代表训练样本的单个根节点开始 使用分类属性（如果是量化属性，则需先进行离散化） 递归的通过选择相应的测试属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现 测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益） 递归划分步骤停止的条件 给定节点的所有样本属于同一类 没有剩余属性可以用来进一步划分样本使用多数表决 没有剩余的样本,详细算法见P189,贝叶斯分类,贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。 朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。,后向传播分类,后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。 优点 预测精度总的来说较高 健壮性好，训练样本中包含错误时也可正常工作 输出可能是离散值、连续值或者是离散或量化属性的向量值 对目标进行分类较快 缺点 训练（学习）时间长 蕴涵在学习的权中的符号含义很难理解 很难根专业领域知识相整合,其他分类方法,k-最临近分类 给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本；然后使用k个最临近者中最公共的类来预测当前样本的类标号 基于案例的推理 样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例 遗传算法 结合生物进化思想的算法 粗糙集方法 模糊集方法 允许在分类规则中定义“模糊的”临界值或边界,什么是预测？,预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。 预测和分类的异同 相同点 两者都需要构建模型 都用模型来估计未知值 预测当中主要的估计方法是回归分析 线性回归和多元回归 非线性回归 不同点 分类法主要是用来预测类标号（分类属性值） 预测法主要是用来估计连续值（量化属性值）,回归方法,线性回归：Y = + X 其中和是回归系数，可以根据给定的数据点，通过最小二乘法来求得 多元回归：Y = + 1X1 + 2 X2 线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的，1 和2 非线性回归：Y = + 1X1 + 2 X22+ 3 X33 对不呈线性依赖的数据建模 使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解,评估分类法的准确性,导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计 保持方法 给定数据随机划分为两个集合：训练集(2/3)和测试集(1/3) 训练集导出分类法，测试集对其准确性进行评估 随机子选样：保持方法的一个变形，将保持方法重复k次，然后取准确率的平均值 k-折交叉确认 初始数据被划分为k个不相交的，大小大致相同的子集S1,S2Sk 进行k次训练和测试，第i次时，以Si做测试集，其他做训练集 准确率为k次迭代正确分类数除以初始数据集样本总数,提高分类法的准确性,Bagging技术和boosting技术都通过将T个学习得到的分类法C1,C2CT组合起来，从而创造一个改进的分类法C* Bagging技术 对训练集S进行T次迭代，每次通过放回取样选取样本集St，通过学习St得到分类法Ct 对于未知样本X，每个分类法返回其类预测，作为一票 C*统计得票，并将得票最高的预测赋予X Boosting技术 每个训练样本赋予一个权值 Ct的权值取决于其错误率,四、数据挖掘算法聚类,聚类分析,什么是聚类分析? 聚类分析中的数据类型 主要聚类分析方法分类 划分方法（Partitioning Methods） 分层方法 基于密度的方法 基于表格的方法 基于模型（Model-Based）的聚类方法 异常分析 总结,什么是聚类分析?,簇（Cluster）:一个数据对象的集合 在同一个类中，对象之间0具有相似性； 不同类的对象之间是相异的。 聚类分析 把一个给定的数据对象集合分成不同的簇； 聚类是一种无监督分类法: 没有预先指定的类别； 典型的应用 作为一个独立的分析工具，用于了解数据的分布； 作为其它算法的一个数据预处理步骤；,聚类的常规应用,模式识别 空间数据分析 在GIS中，通过聚类发现特征空间来建立主题索引； 在空间数据挖掘中，检测并解释空间中的簇； 图象处理 经济学 (尤其是市场研究方面) WWW 文档分类 分析WEB日志数据来发现相似的访问模式,应用聚类分析的例子,市场销售: 帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划； 土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区； 保险: 对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户； 城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅； 地震研究: 根据地质断层的特点把已观察到的地震中心分成不同的类；,聚类方法性能评价,一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点： 高的簇内相似性 低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现； 聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；,聚类方法性能评价,可伸缩性 能够处理不同类型的属性 能发现任意形状的簇 在决定输入参数的时候，尽量不需要特定的领域知识； 能够处理噪声和异常 对输入数据对象的顺序不敏感 能处理高维数据 能产生一个好的、能满足用户指定约束的聚类结果 结果是可解释的、可理解的和可用的,两种数据结构,数据矩阵 (two modes) 差异度矩阵 (one mode),评价聚类质量,差异度/相似度矩阵: 相似度通常用距离函数来表示； 有一个单独的质量评估函数来评判一个簇的好坏； 对不同类型的变量，距离函数的定义通常是不同的，这在下面有详细讨论； 根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系； 很难定义“足够相似了”或者“足够好了” 只能凭主观确定；,聚类分析中的数据类型,区间标度变量（Interval-scaled variables）: 二元变量（Binary variables）: 标称型，序数型和比例型变量（Nominal, ordinal, and ratio variables）: 混合类型变量（Variables of mixed types）:,区间标度变量,数据标准化 计算绝对偏差的平均值: 其中 计算标准度量值 (z-score) 使用绝对偏差的平均值比使用标准偏差更健壮（robust）,计算对象之间的相异度,通常使用距离来衡量两个对象之间的相异度。 常用的距离度量方法有: 明考斯基距离（ Minkowski distance）: 其中 i = (xi1, xi2, , xip) 和 j = (xj1, xj2, , xjp) 是两个p维的数据对象, q是一个正整数。 当q = 1时, d 称为曼哈坦距离（ Manhattan distance）,计算对象之间的相异度,当q=2时, d 就成为欧几里德距离: 距离函数有如下特性： d(i,j) 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) d(i,k) + d(k,j) 可以根据每个变量的重要性赋予一个权重,序数型变量,一个序数型变量可以是离散的也可以是连续的 离散的序数型变量类似于标称变量，除了它的M个状态是以有意义的序列排序的，比如职称 连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。,序数型变量,相异度的计算 与区间标度变量的计算方法相类似 将xif 用它对应的秩代替 将每个变量的值域映射到0.0，1.0上，使得每个变量都有相同的权重。这通过用zif来替代rif来实现 用前面所述的区间标度变量的任一种距离计算方法来计算,比例标度型变量,比例标度型变量（Ratio-scaled variable） : 总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如 AeBt or Ae-Bt 计算相异度的方法: 采用与处理区间标度变量相同的方法 不是一个好的选择 进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法 yif = log(xif) 将其作为连续的序数型数据，将其秩作为区间标度的值来对待。,混合类型的变量,一个数据库可能包含了所有这6中类型的变量 用以下公式计算对象i，j之间的相异度. 其中，p为对象中的变量个数 如果xif或xjf 缺失（即对象i或对象j没有变量f的值），或者xif = xjf =0，且变量f是不对称的二元变量，则指示项ij(f)=0；否则ij(f)=1,混合类型的变量,f 是二元变量或标称变量: if xif = xjf dij(f) = 0, else dij(f) = 1 f 是区间标度变量: dij(f) = | xif-xjf |/maxhxhf-minhxhf 其中h遍取变量f的所有非空缺对象 f 是序数型或比例标度型 计算秩 rif 计算 zif并将其作为区间标度变量值对待,主要聚类方法,Partitioning algorithms: Construct various partitions and then evaluate them by some criterion Hierarchy algorithms: Create a hierarchical decomposition of the set of data (or objects) using some criterion Density-based: based on connectivity and density functions Grid-based: based on a multiple-level granularity structure Model-based: A model is hypothesized for each of the clusters and the idea is to find the best fit of that model to each other,五、数据挖掘算法关联,什么是关联挖掘?,关联规则挖掘： 在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。 应用： 购物篮分析、交叉销售、产品目录设计、 loss-leader analysis、聚集、分类等。 举例： 规则形式： “Body Head support, confidence”. buys(x, “diapers”) buys(x, “beers”) 0.5%, 60% major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%,关联规则：基本概念,给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品) 查找: 所有描述一个项目集合与其他项目集合相关性的规则 E.g., 98% of people who purchase tires and auto accessories also get automotive services done 应用 * 护理用品 (商店应该怎样提高护理用品的销售？) 家用电器 * (其他商品的库存有什么影响?) 在产品直销中使用附加邮寄 Detecting “ping-pong”ing of patients, faulty “collisions”,规则度量：支持度与可信度,查找所有的规则 X & Y Z 具有最小支持度和可信度 支持度, s, 一次交易中包含X 、 Y 、 Z的可能性 可信度, c, 包含X 、 Y的交易中也包含Z的条件概率,设最小支持度为50%, 最小可信度为 50%, 则可得到 A C (50%, 66.6%) C A (50%, 100%),买尿布的客户,二者都买的客户,买啤酒的客户,关联规则挖掘：路线图,布尔 vs. 定量 关联 (基于 处理数据的类型) buys(x, “SQLServer”) buys(x, “DMBook”) buys(x, “DBMiner”) 0.2%, 60% age(x, “30.39”) income(x, “42.48K”) buys(x, “PC”) 1%, 75% 单维 vs. 多维 关联 (例子同上) 单层 vs. 多层 分析 那个品种牌子的啤酒与那个牌子的尿布有关系? 各种扩展 相关性、因果分析 关联并不一定意味着相关或因果 最大模式和闭合相集 添加约束 如, 哪些“小东西”的销售促发了“大家伙”的买卖？,关联规则挖掘一个例子,对于 A C： support = support(A 、C) = 50% confidence = support(A 、C)/support(A) = 66.6% Apriori的基本思想: 频繁项集的任何子集也一定是频繁的,最小值尺度 50% 最小可信度 50%,关键步骤：挖掘频繁集,频繁集:是指满足最小支持度的项目集合 频繁集的子集也一定是频繁的 如, 如果AB 是频繁集，则 A B 也一定是频繁集 从1到k（k-频繁集）递归查找频繁集 用得到的频繁集生成关联规则,多层关联规则,项通常具有层次 底层的项通常支持度也低 某些特定层的规则可能更有意义 交易数据库可以按照维或层编码 可以进行共享的多维挖掘,挖掘多层关联规则,自上而下，深度优先的方法： 先找高层的“强”规则： 牛奶 面包 20%, 60%. 再找他们底层的“弱”规则： 酸奶 黄面包 6%, 50%. 多层关联规则的变种 层次交叉的关联规则： 酸奶 面包房 黄面包 不同种分层方法间的关联规则： 酸奶 面包房面包,多层关联规则,支持度不变: 在各层之间使用统一的支持度 + 一个最小支持度阈值. 如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。 底层项不会成为频繁集，如果支持度 太高 丢失底层关联规则 太低 生成太多的高层关联规则 支持度递减: 随着层次的降低支持度递减 4种搜索策略： 层与层独立 用k-项集跨层过滤 用项跨层过滤 用项进行可控跨层过滤,支持度不变,支持度不变多层挖掘,牛奶 support = 10%,酸奶 support = 6%,脱脂奶 support = 4%,层 1 min_sup = 5%,层 2 min_sup = 5%,支持度递减,支持度递减多层挖掘,酸奶 support = 6%,脱脂奶 support = 4%,层 1 min_sup = 5%,层 2 min_sup = 3%,牛奶 support = 10%,多层关联：冗余过滤,由于“祖先”关系的原因，有些规则可能是多余的。 例子 牛奶 白面包 support = 8%, confidence = 70% 酸奶 白面包 support = 2%, confidence = 72% 我们称第一个规则是第二个规则的祖先 参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。,多层挖掘：深度优先,自顶向下，深度优先的方法： 先挖掘高层频繁项： 牛奶 (15%), 面包 (10%) 再挖掘他们底层的相对较弱的频繁项： 酸奶 (5%), 白面包 (4%) 跨层时对支持度的不同处理方法，对应了不同的算法: 层之间支持度不变： 如果t的祖先是非频繁的，则不用考虑t 支持度随层递减： 则只考虑那些其祖先是频繁的/不可忽略的项,数据挖掘查询的逐步精化,为什么要逐步精化 挖掘操作的代价可能高或低，结果可能细致或粗糙 在速度和质量之间折衷：逐步精化 超集覆盖特征： 预存储所有正面答案允许进一步正确性验证，而不必验证已经错误的 2或多步挖掘： 先执行粗糙的、容易的操作 (超集覆盖) 然后在减少后的候选集上进行计算量大的算法 (Koperski & Han, SSD95).,逐步求精空间关联规则挖掘,空间关系的层次： “g_close_to”: 邻近, 接触, 交叉, 包含 先搜索粗糙的关系然后再精化,逐步求精空间关联规则挖掘,空间关联规则的两步算法： 步骤 1: 粗糙空间计算 (用于过滤) 用 MBR 或 R-tree 做粗糙估计 步骤 2: 细致空间算法 (用于精化) 只计算已经通过空间计算的对象,多维关联规则：概念,单维规则： buys(X, “milk”) buys(X, “bread”) 多维规则： 2个以上维/谓词 维间关联规则 (维词不重复) age(X,”19-25”) occupation(X,“student”) buys(X,“coke”) 混合维关联规则 (维词重复) age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”) 类别属性 有限个值, 值之间无顺序关系 数量属性 数字的，值之间隐含了顺序关系,挖掘多维关联的技术,搜索频繁k-维词集合： 如: age, occupation, buys 是一个3-维词集合。 按照对 age 处理方式的不同，分为： 1. 用静态方法把数值属性离散化 数值属性可用预定义的概念层次加以离散化。 2. 带数量的关联规则 根据数据的分布动态的把数值属性离散化到不同的“箱”。 3. 基于距离的关联规则 用数据点之间的距离动态的离散化,数值属性的静态离散化,在挖掘之前用概念层次先离散化 数值被替换为区间范围 关系数据库中，要找到所有频繁k-维词需要k或k+1次表扫描。 适宜使用数据立方体 N维立方体的每个单元 对应一个维词集合 使用数据立方体速度更快,带数量的关联规则,age(X,”30-34”) income(X,”24K - 48K”) buys(X,”high resolution TV”),动态 离散化数值属性 Such that the confidence or compactness of the rules mined is maximized. 2-维数量关联规则： Aquan1 Aquan2 Acat 用2-维表格把“邻近”的关联规则组合起来 例子,ARCS (关联规则聚集系统),ARCS 流程 1. 分箱 2. 查找频繁维词 集合 3. 聚集 4. 优化,ARCS的局限性,数值属性只能出现在规则的左侧 左侧只能有两个属性 (2维) ARCS 的改进 不用基于栅格的方法 等深分箱 基于局部完整性 测度的聚集 “Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.,基于距离的关联规则挖掘,分箱的方法没有体现数据间隔的语义 基于距离的分割是更有“意义”的离散化方法，考虑： 区间内密度或点的个数 区间内点的“紧密程度,记SX 为 N 个元组 t1, t2, , tN 在 属性集 X 上的投影 则 SX 的直径: distx:距离量度,如 欧几里德距离或 Manhattan,聚集和距离度量,用直径 d 评估聚集 CX 的密度，其中 查找聚集和基于距离的规则 用密度阈值 d0代替支持度 采用修改过的 BIRCH 聚集算法,聚集和距离度量,关联规则可视化Using Plane Graph,关联规则可视化Using Rule Graph,六、序列模式挖掘,序列模式概念,序列模式的概念最早是由Agrawal和Srikant 提出的 序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值,序列模式实例,例1：在两年前购买了Ford 牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动 例2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒 例3：工业过程控制领域：过程变量采样值时时间序列；变量之间的关系是动态的；系统故障模式；等等,序列模式应用领域,应用领域： 客户购买行为模式预测 Web访问模式预测 疾病诊断 自然灾害预测 DNA序列分析 工业控制,序列模式表示,符号化表示： 项目集(Itemset)是各种项目组成的集合 序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s = ，sj(1 = j = l)为项目集(Itemset)，也称为序列s的元素 序列的元素(Element)可表示为(x1x2xm)， xk(1 = k = m)为不同的项目，如果一个序列只有一个项目，则括号可以省略 一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列,序列模式表示,符号化表示： 设 = ， = ，如果存在整数1 = j1 j2 jn = m，使得a1 bj1，a2 bj2， an bjn，则称序列为序列的子序列，又称序列包含序列，记为 序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数，记为Support() 给定支持度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式 长度为l的序列模式记为l-模式,序列模式表示,例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。,序列是序列的子序列 序列是长度为3的序列模式,序列模式挖掘,问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式 系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列,序列模式挖掘算法,序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法：类似于Apriori算法 PrefixSpan(Prefix-project Sequential Pattern mining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘,序列模式挖掘算法,上述算法存在的主要问题： 缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向 事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务 缺少分类层次：只能在项目的原始级别上进行挖掘,七、数据挖掘软件,数据挖掘软件的发展,数据挖掘软件的发展,第一代数据挖掘软件,特点 支持一个或少数几个数据挖掘算法 挖掘向量数据（vector-valued data） 数据一般一次性调进内存进行处理 典型的系统如Salford Systems公司早期的CART系统(www.salford-) 缺陷 如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。,数据挖掘软件的发展,第一代数据挖掘软件 CBA,新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测,二、数据挖掘软件的发展,第二代数据挖掘软件,特点 与数据库管理系统（DBMS）集成 支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性 能够挖掘大数据集、以及更复杂的数据集 通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言增加系统的灵活性 典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作 缺陷 只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发,数据挖掘软件的发展,第二代数据挖掘软件 DBMiner,数据挖掘软件的发展,第二代软件 SAS Enterprise Miner,数据挖掘软件的发展,第三代数据挖掘软件,特点 和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中 由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能 能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成 缺陷 不能支持移动环境,数据挖掘软件的发展,第三代软件 SPSS Clementine,以PMML的格式提供与预言模型系统的接口,数据挖掘软件的发展,第四代数据挖掘软件,特点 目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。 第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 第四代数据挖掘原型或商业系统尚未见报导，PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的论文，Kargupta是马里兰巴尔的摩州立大学（University of Maryland Baltimore County）正在研制的CAREER数据挖掘项目的负责人，该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数据（Ubiquitous设备）的第四代数据挖掘系统。,数据挖掘软件的发展,第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口，所以在数据预处理方面有一定缺陷 第三、四代系统强调预测模型的使用和操作型环境的部署 第二代系统提供数据管理系统和数据挖掘系统之间的有效接口 第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口 目前，随着新的挖掘算法的研究和开发，第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流，部分第二代系统开发商开始研制相应的第三代数据挖掘系统，比如 IBM Intelligent Score Service。第四代数据挖掘原型或商业系统尚未见报导,数据挖掘软件的发展,数据挖掘软件发展的三个阶段 独立的数据挖掘软件 横向的数据挖掘工具集 纵向的数据挖掘解决方案,数据挖掘软件的发展,独立的数据挖掘软件（95年以前）,特点 独立的数据挖掘软件对应第一代系统，出现在数据挖掘技术发展早期，研究人员开发出一种新型的数据挖掘算法，就形成一个软件。 这类软件要求用户对具体的算法和数据挖掘技术有相当的了解，还要负责大量的数据预处理工作。比如C4.5决策树，平行坐标可视化（parallel-coordinate visualization）。,数据挖掘软件的发展,横向的数据挖掘工具集（95年开始）,发展原因 随着数据挖掘应用的发展，人们逐渐认识到数据挖掘软件需要和以下三个方面紧密结合：1）数据库和数据仓库；2）多种类型的数据挖掘算法；3）数据清洗、转换等预处理工作。 随着数据量的增加，需要利用数据库或者数据仓库技术进行管理，所以数据挖掘系统与数据库和数据仓库结合是自然的发展。 现实领域的问题是多种多样的，一种或少数数据挖掘算法难以解决 挖掘的数据通常不符合算法的要求，需要有数据清洗、转换等数据预处理的配合，才能得出有价值的模型,数据挖掘软件的发展,横向的数据挖掘工具集（95年开始）,发展过程 随着这些需求的出现，1995年左右软件开发商开始提供称之为“工具集”的数据挖掘软件 特点 此类工具集的特点是提供多种数据挖掘算法 包括数据的转换和可视化 由于此类工具并非面向特定的应用，是通用的算法集合，可以称之为横向的数据挖掘工具（Horizontal Data Mining Tools） 由于此类工具并非面向特定的应用，是通用的算法集合，所以称之为横向的数据挖掘工具 典型的横向工具有IBM Intelligent Miner、SPSS的Clementine、SAS的Enterprise Miner、SGI的MineSet、Oracle Darwin等,数据挖掘软件的发展,横向的数据挖掘工具集（95年开始）,IBM Intelligent Miner SPSS的Clementine SAS的Enterprise Miner SGI的MineSet Oracle Darwin,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,发展原因 随着横向的数据挖掘工具的使用日渐广泛，人们也发现这类工具只有精通数数据挖掘算法的专家才能熟练使用，如果对算法不了解，难以得出好的模型 从1999年开始，大量的数据挖掘工具研制者开始提供纵向的数据挖掘解决方案（Vertical Solution），即针对特定的应用提供完整的数据挖掘方案 对于纵向的解决方案，数据挖掘技术的应用多数还是为了解决某些特定的难题，而嵌入在应用系统中,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,在证券系统中嵌入神经网络预测功能 在欺诈检测系统中嵌入欺诈行为的分类/识别模型 在客户关系管理系统中嵌入客户成簇/分类功能或客户行为分析功能 在机器维护系统中嵌入监/检测或识别难以定性的设备故障功能 在数据库营销中嵌入选择最可能购买产品的客户功能 在机场管理系统中嵌入旅客人数预测、货运优化功能 在基因分析系统中嵌入DNA识别功能 在制造/生产系统中嵌入质量控制功能等,数据挖掘软件的发展,纵向的数据挖掘解决方案（99年开始）,KD1（主要用于零售业） Options&Choice(主要用于保险业) HNC（欺诈行为侦测） Unica Model 1(主要用于市场营销),数据挖掘软件的发展,数据挖掘软件的现状,情况概览 2002年9月，Amazon上关于数据挖掘的书有251本() 目前有数百个数据挖掘软件产品（） 数据挖掘应用相对广泛,数据挖掘软件的现状,国内大部分处于科研阶段 各大学和科研机构从事数据挖掘算法的研究 国内著作的数据挖掘方面的书较少（翻译的有） 数据挖掘讨论组（） 有一些公司在国外产品基础上开发的特定的应用 IBM Intelligent Miner SAS Enterprise Miner 自主知识产权的数据挖掘软件 复旦德门（）等,八、数据挖掘应用,数据挖掘应用,数据挖掘应用,银行 美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9。 分析客户使用分销渠道的情况和分销渠道的容量 ；建立利润评测模型；客户关系优化；风险控制等 电子商务 网上商品推荐；个性化网页；自适应网站 生物制药、基因研究 DNA序列查询和匹配；识别基因序列的共发生性 电信 欺诈甄别；客户流失 保险、零售。,数据挖掘应用,数据挖掘,保险客户,证券客户,银行客户,电信客户,零售客户,人类基因,植物基因,动物基因,特殊群体基因,基因序列 基因表达谱 基因功能 基因制药 .,数据挖掘应用,为什么没有广泛使用？,数据挖掘正在快速的发展 技术的研究和开发已经走在很前沿的地方 数据挖掘应用面已经扩充了很多 但是仍然没有希望的高，为什么？ 希望在多少年内达到数十亿元的盈利？ 是一种增值服务（Not bread-and-butter） 不能认为高不可攀，所以不去过问 是一门年轻的技术，需要和实际结合，解决现实问题,数据挖掘应用,国内应用存在的问题,数据积累不充分、不全面 业务模型构建困难 缺少有经验的实施者,数据挖掘应用,神经网络 Neural Networks,聚类分析 Clustering,Open Accnt,Add New Product,Decrease Usage,?,Time,序列分析 Sequence Analysis,决策树 Decision Trees,倾向性分析,客户保留 客户生命周期管理 目标市场 价格弹性分析,客户细分 市场细分,倾向性分析 客户保留 目标市场 欺诈检测,关联分析 Association,市场组合分析 套装产品分析 目录设计 交叉销售,数据挖掘应用,聚集（Cluster） 聚集是把整个数据库分成不同的群组。它的目的是要群与群之间差别很明显，而同一个群之间的数据尽量相似。 常用技术：神经元网络、K均值、最近邻,数据挖掘应用,异常检测 及时发现有欺诈嫌疑的异常行为，正确进行欺诈问题的评估，对欺诈者实施控制和强制措施。 技术：决策树，神经元网络，异常因子LOF检测,客户消费异常行为分析模型,数据挖掘应用,客户分析业务模型 交叉销售 客户响应 客户流失 客户利润 信用卡分析业务模型 客户信用等级评估 客户透支分析 客户利润分析 客户消费行为分析 客户消费异常行为分析,数据挖掘应用,数据挖掘应用,客户响应模型基本概念,响应率分析: 分析客户对某种新服务或者新产品的感兴趣情况. 为什么要进行响应率分析: 通过响应率分析能够有效的降低市场推广的费用,同时能够更加有针对性的面对目标市场.达到以最小的投入获得最佳效果的目的,数据挖掘应用,用哪一种数据挖掘技术实现？,响应率分析是为了对某项市场营销（新产品销售）活动找到最合适的响应客户，需要预测哪些客户能够响应，以及响应的可能性是多少。 因此，需要构建预言模型 分类是预言模型的一种技术，可以利用分类技术构建客户响应率模型 决策树 神经网络 贝叶斯分类 ,数据挖掘未来发展,与数据库数据仓库系统集成 与预言模型系统集成 挖掘各种复杂类型的数据 与应用相结合 研制和开发数据挖掘标准 支持移动环境,数据挖掘应用时间序列模式挖掘,工业过程变量时间序列,生产过程的类型 连续过程：工艺参数（设定值）均为常量。 批量过程：工艺参数（设定值）通常为变量。 工艺参数的数据类型 数值型、逻辑型、枚举型 产品质量的数据类型 逻辑型：只判断产品的好坏 数值型：给出产品质量好坏的程度,批量型生产过程,质量检验！,预热阶段,加热阶段,均热阶段,连续型生产过程,数据挖掘对象的基本构成,样本的抽取（批量生产过程）,t,t,x1(t),y1,y2,y3,x2(t),x3(t),X,Y,连续生产过程的样本抽取,连续过程 批量过程,T1,T2,T3,v,x1,x2,x3,质量检验！,0,t1,t2,t3,如何“组装”时间序列？,关于生产质量改变的模式假设,生产质量不良的原因是工艺参数设计或控制有问题： 设计阶段：工艺参数设计有错误； 控制阶段：工艺参数未能控制在设计值； 上述因素都可通过生产过程中工艺参数的时间序列实测样本反映出来。 工艺参数的时间序列中某些特征的改变，引起生产质量从量变到质变。 时间序列的特征，可以用模式来描述。 时间序列的模式改变，是生产质量不良的原因。 数据挖掘的目的，就是要寻找引起生产质量不良的工艺参数模式。,时间序列的模式抽取,目的： 将时间序列样本集合转换为特征模式样本集合，每一种模式（或若干种模式的一种组合）用一个整数来编码，从而将数据挖掘的对象从时间序列空间转换为整数空间。 其中，mi 为 xi (t) 所包含的特征模式的集合。注意： mi 不再是时间序列 mi 可能是多元素的集合，即 xi(t)