截图
简介
这是一个关于数据挖掘技术PPT，包括了数据挖掘概述，数据预处理，数据挖掘算法－分类与预测，数据挖掘算法－聚类，数据挖掘算法－关联分析，序列模式挖掘，数据挖掘软件，数据挖掘应用等内容，自动化前沿第四讲 数据挖掘技术及其应用 宋执环浙江大学工业控制研究所 主要内容 数据挖掘概述数据预处理数据挖掘算法－分类与预测数据挖掘算法－聚类数据挖掘算法－关联分析序列模式挖掘数据挖掘软件数据挖掘应用一、数据挖掘概述数据挖掘概念数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。 数据挖掘与KDD 知识发现（KD）输出的是规则 数据挖掘（DM）输出的是模型 共同点两种方法输入的都是学习集（learning sets） 目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全自动化，只能半自动化 异常检测异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。异常探测应用电信和信用卡欺骗贷款审批药物研究气象预报金融领域客户分类网络入侵检测故障检测与诊断等 什么是异常（outlier）？Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点，欢迎点击下载数据挖掘技术PPT哦。
数据挖掘技术PPT是由红软PPT免费下载网推荐的一款公司管理PPT类型的PowerPoint.
自动化前沿第四讲 数据挖掘技术及其应用 宋执环浙江大学工业控制研究所 主要内容 数据挖掘概述数据预处理数据挖掘算法－分类与预测数据挖掘算法－聚类数据挖掘算法－关联分析序列模式挖掘数据挖掘软件数据挖掘应用一、数据挖掘概述数据挖掘概念数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。 数据挖掘与KDD 知识发现（KD）输出的是规则 数据挖掘（DM）输出的是模型 共同点两种方法输入的都是学习集（learning sets） 目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全自动化，只能半自动化 异常检测异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。异常探测应用电信和信用卡欺骗贷款审批药物研究气象预报金融领域客户分类网络入侵检测故障检测与诊断等 什么是异常（outlier）？ Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。 聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。异常检测方法的分类基于统计（statistical-based)的方法基于距离 (distance-based)的方法基于偏差(deviation-based)的方法基于密度(density-based)的方法高维数据的异常探测数据挖掘系统的特征数据的特征知识的特征算法的特征数据的特征大容量 POS数据（某个超市每天要处理高达2000万笔交易）卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据）互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）系统的特征知识发现系统需要一个前处理过程数据抽取数据清洗数据选择数据转换知识发现系统是一个自动/半自动过程知识发现系统要有很好的性能知识（模式）的特征知识发现系统能够发现什么知识？计算学习理论COLT（Computational Learning Theory）以FOL为基础的以发现关系为目的的归纳逻辑程序设计现行的知识发现系统只能发现特定模式的知识规则分类关联知识表示：规则 IF 条件 THEN 结论条件和结论的粒度（抽象度）可以有多种单值区间模糊值规则可以有确信度精确规则概率规则知识表示：分类树数据挖掘算法的特征构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索数据挖掘的主要方法分类（Classification）聚类(Clustering) 相关规则(Association Rule) 回归(Regression) 其他数据挖掘系统数据挖掘系统第一代数据挖掘系统 支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valued data），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。 数据挖掘系统第三代数据挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。 第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 。二、数据预处理为什么需要预处理数据不完整含观测噪声不一致包含其它不希望的成分数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。污染数据形成的原因滥用缩写词数据输入错误数据中的内嵌控制信息不同的惯用语重复记录丢失值拼写变化不同的计量单位过时的编码含有各种噪声数据清理的重要性污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。垃圾进、垃圾出数据清理处理内容格式标准化异常数据清除错误纠正重复数据的清除数据规约数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果主要策略: 数据聚集维规约数据压缩数值规约空缺值忽略元组人工填写空缺值使用固定值使用属性平均值使用最有可能值噪声数据如何平滑数据，去掉噪声数据平滑技术分箱聚类计算机和人工检查相结合回归分箱箱的深度：表示不同的箱里有相同个数的数据。箱的宽度：每个箱值的取值区间是个常数。平滑方法: 按箱平均值平滑按箱中值平滑按箱边界值平滑聚类每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点 回归通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归多线性回归数据集成将多个数据源中的数据结合起来存放在一个一直得数据存贮中。实体识别 实体和模式的匹配冗余：某个属性可以由别的属性推出。相关分析相关性rA，B . rA，B>0，正相关。A随B的值得增大而增大 rA，B>0，正相关。AB无关 rA，B>0，正相关。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. 预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测数据分类：两步过程第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第一步：建立模型第二步：用模型进行分类准备分类和预测的数据通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性数据清理消除或减少噪声，处理空缺值，从而减少学习时的混乱相关性分析数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确数据变换可以将数据概化到较高层概念，或将数据进行规范化比较分类方法使用下列标准比较分类和预测方法预测的准确率：模型正确预测新数据的类编号的能力速度：产生和使用模型的计算花销鲁棒性：给定噪声数据或有空缺值的数据，模型正确预测的能力可伸缩性：对大量数据，有效的构建模型的能力可解释性：学习模型提供的理解和洞察的层次用判定树归纳分类什么是判定树？类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布判定树的生成由两个阶段组成判定树构建开始时，所有的训练样本都在根节点递归的通过选定的属性，来划分样本 （必须是离散值）树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝判定树的使用：对未知样本进行分类通过将样本的属性值与判定树相比较判定归纳树算法判定归纳树算法（一个贪心算法）自顶向下的分治方式构造判定树树以代表训练样本的单个根节点开始使用分类属性（如果是量化属性，则需先进行离散化）递归的通过选择相应的测试属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益）递归划分步骤停止的条件给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本——使用多数表决没有剩余的样本贝叶斯分类贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。 朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。后向传播分类后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。优点预测精度总的来说较高健壮性好，训练样本中包含错误时也可正常工作输出可能是离散值、连续值或者是离散或量化属性的向量值对目标进行分类较快缺点训练（学习）时间长蕴涵在学习的权中的符号含义很难理解很难根专业领域知识相整合其他分类方法 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，S2…Sk 进行k次训练和测试，第i次时，以Si做测试集，其他做训练集准确率为k次迭代正确分类数除以初始数据集样本总数提高分类法的准确性 Bagging技术和boosting技术都通过将T个学习得到的分类法C1，C2…CT组合起来，从而创造一个改进的分类法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 五、数据挖掘算法－关联什么是关联挖掘? 关联规则：基本概念规则度量：支持度与可信度关联规则挖掘：路线图关联规则挖掘—一个例子关键步骤：挖掘频繁集多层关联规则项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义交易数据库可以按照维或层编码可以进行共享的多维挖掘挖掘多层关联规则自上而下，深度优先的方法：先找高层的“强”规则：牛奶 ® 面包 [20%， 60%]. 再找他们底层的“弱”规则：酸奶 ® 黄面包 [6%， 50%]. 多层关联规则的变种层次交叉的关联规则： 酸奶 ® 面包房 黄面包不同种分层方法间的关联规则：酸奶 ® 面包房面包多层关联规则支持度不变: 在各层之间使用统一的支持度 + 一个最小支持度阈值. 如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。 – 底层项不会成为频繁集，如果支持度太高 丢失底层关联规则太低 生成太多的高层关联规则支持度递减: 随着层次的降低支持度递减 4种搜索策略：层与层独立用k-项集跨层过滤用项跨层过滤用项进行可控跨层过滤支持度不变支持度递减多层关联：冗余过滤由于“祖先”关系的原因，有些规则可能是多余的。例子牛奶 白面包 [support = 8%， confidence = 70%] 酸奶 白面包 [support = 2%， confidence = 72%] 我们称第一个规则是第二个规则的祖先参考规则的祖先，如果他的支持度与我们“预期”的支持度近似的话，我们就说这条规则是冗余的。多层挖掘：深度优先自顶向下，深度优先的方法：先挖掘高层频繁项： 牛奶 (15%)， 面包 (10%) 再挖掘他们底层的相对较弱的频繁项： 酸奶 (5%)， 白面包 (4%) 跨层时对支持度的不同处理方法，对应了不同的算法: 层之间支持度不变：如果t的祖先是非频繁的，则不用考虑t 支持度随层递减：则只考虑那些其祖先是频繁的/不可忽略的项数据挖掘查询的逐步精化为什么要逐步精化挖掘操作的代价可能高或低，结果可能细致或粗糙在速度和质量之间折衷：逐步精化超集覆盖特征：预存储所有正面答案—允许进一步正确性验证，而不必验证已经错误的 2或多步挖掘：先执行粗糙的、容易的操作 (超集覆盖) 然后在减少后的候选集上进行计算量大的算法 (Koperski & Han， SSD’95). 逐步求精空间关联规则挖掘逐步求精空间关联规则挖掘空间关联规则的两步算法：步骤 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. 基于距离的关联规则用数据点之间的距离动态的离散化数值属性的静态离散化带数量的关联规则 ARCS (关联规则聚集系统) ARCS 流程 1. 分箱 2. 查找频繁维词 集合 3. 聚集 4. 优化 ARCS的局限性基于距离的关联规则挖掘分箱的方法没有体现数据间隔的语义 基于距离的分割是更有“意义”的离散化方法，考虑：区间内密度或点的个数区间内点的“紧密程度聚集和距离度量聚集和距离度量 六、序列模式挖掘序列模式概念序列模式的概念最早是由Agrawal和Srikant 提出的序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值序列模式实例例1：在两年前购买了Ford 牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动例2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒例3：工业过程控制领域：过程变量采样值时时间序列；变量之间的关系是动态的；系统故障模式；等等 序列模式应用领域应用领域：客户购买行为模式预测 Web访问模式预测疾病诊断自然灾害预测 DNA序列分析工业控制序列模式表示符号化表示：项目集(Itemset)是各种项目组成的集合序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s = ，sj(1 <= j <= l)为项目集(Itemset)，也称为序列s的元素序列的元素(Element)可表示为(x1x2…xm)， 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。序列模式挖掘问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式 系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列序列模式挖掘算法序列模式挖掘的主要算法 GSP(Generalized Sequential Patterns)算法：类似于Apriori算法 PrefixSpan(Prefix-project Sequential Pattern mining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘序列模式挖掘算法上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务缺少分类层次：只能在项目的原始级别上进行挖掘七、数据挖掘软件 八、数据挖掘应用 数据挖掘应用—— 时间序列模式挖掘工业过程变量时间序列生产过程的类型连续过程：工艺参数（设定值）均为常量。批量过程：工艺参数（设定值）通常为变量。工艺参数的数据类型数值型、逻辑型、枚举型产品质量的数据类型逻辑型：只判断产品的好坏数值型：给出产品质量好坏的程度 批量型生产过程连续型生产过程数据挖掘对象的基本构成样本的抽取（批量生产过程）连续生产过程的样本抽取连续过程 批量过程 关于生产质量改变的模式假设生产质量不良的原因是工艺参数设计或控制有问题：设计阶段：工艺参数设计有错误；控制阶段：工艺参数未能控制在设计值；上述因素都可通过生产过程中工艺参数的时间序列实测样本反映出来。工艺参数的时间序列中某些特征的改变，引起生产质量从量变到质变。时间序列的特征，可以用模式来描述。时间序列的模式改变，是生产质量不良的原因。数据挖掘的目的，就是要寻找引起生产质量不良的工艺参数模式。 时间序列的模式抽取目的：将时间序列样本集合转换为特征模式样本集合，每一种模式（或若干种模式的一种组合）用一个整数来编码，从而将数据挖掘的对象从时间序列空间转换为整数空间。 其中，mi 为 xi (t) 所包含的特征模式的集合。注意： mi 不再是时间序列 mi 可能是多元素的集合，即 xi(t) 可包含多种模式时间序列的模式抽取时间序列分析理论中已给出一类模式抽取的方法：根据时间序列建立 ARMA模型。或理解为把时间序列空间映射到 ARMA模型中的参数空间，也称为时间序列的 ARMA特征空间。这一方法的优点是：成熟有严密的数学基础缺点是： ARMA特征没有物理意义，难以据其改进产品质量。时间序列的模式抽取（有物理意义的）模式抽取问题：给定（有物理意义的）模式集合，寻找时间序列中存在的模式种类。给定模式集合的方法：有先验知识 —— 根据先验知识构造与产品质量有关的模式类没有先验知识 —— 穷举构造所有可能的有物理意义的模式只有部分先验知识 —— 上述两种方法的组合寻找时间序列中模式的方法：给出模式的特征给出计算特征匹配的指标在时间序列中进行特征匹配常见的有物理意义的特征模式统计模式均值、方差（标准差）、最大值、最小值、中间值、局部极值出现频率趋势模式单调性（单增、单减）、变化性（最大、最小、平均、中值）、凹凸性偏差模式与标准值（设定值）之间的偏差（最大、最小、平均、中值）累积模式时间累计、绝对值时间累计、偏差值时间累计、平均值时间累计数据挖掘的两种应用方式质量分类模型的挖掘给定特征模式样本的集合 {(mi， yi)}i=1，2，，n ， 构造分类器 f (m)，满足 f (mi) ＝ yi 。在复杂情况下，可构造分类决策树。这是一个类别已知（ yi， i=1， 2， ， n 已知）情况下的分类模型建立问题。质量分析结论的挖掘给定特征模式样本的集合 {(mi， yi)}i=1，2，，n ， 建立质量指标 yi 与特征模式 mi 之间的相关关系。该相关关系直接作为结论提供给用户。一个示例：加热炉生产质量数据挖掘生产工艺：间歇式加热过程（均热炉） 一个示例：加热炉生产质量数据挖掘质量指标：钢锭内裂影响质量的因素（先验知识）：各加热段之间切换时温度变化太快；各加热段的温度设定值相差太大；燃料燃烧不充分；加热时间太短；某些钢种的钢锭特别容易裂；大型钢锭比小型钢锭容易裂。 一个示例：加热炉生产质量数据挖掘参加挖掘的工艺参数（共7个参数）：炉膛温度（500℃ — 1700 ℃，采样周期：1 sec）烟道成分（1% — 10% ，采样周期：1 min）加热时间（0.6 hr — 2.2 hr）钢锭钢种（高碳、中碳、低碳、镇静、沸腾、硅钢）钢锭规格（0.5 T、 1.0 T、 1.5 T、 2.0 T）燃料流量（1000 m3/hr — 2000 m3/hr ，采样周期：1 sec）翻板开度（0% — 100%）一个示例：加热炉生产质量数据挖掘时间序列的模式抽取（共10个特征模式，均有物理意义）炉膛温度：各加热段的平均温度、各加热段之间的最大温差、各加热段内的最大温度波动；烟道成分：各加热段的平均烟道气含氧量；加热时间：各加热段的加热时间；钢锭钢种：钢种；钢锭规格：规格；燃料流量：各加热段的平均流量、各加热段内的最大流量波动；翻板开度：各加热段的翻板开度。一个示例：加热炉生产质量数据挖掘样本抽取：每加热一炉钢锭的生产历史数据记录为一组样本。数据挖掘步骤：数据清洗：去除野值、数据平滑（移动平均）模式抽取：所有样本各抽取10个特征模式若用于质量预测：主元分析：去除次要特征模式；分类分析：建立质量分类模型（决策树）； 若用于质量分析：主元分析：去除次要特征模式；相关分析：计算主要特征模式与钢锭内裂之间的相关度；结果验证：用测试样本集对挖掘结果进行测试结果输出：输出质量分类决策树或质量相关分析结果。 谢谢！
展开
