自动化前沿数据挖掘技术及其应用.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=professorOR years 6THEN 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*统计得票，并将得票最高的预测赋予XBoosting技术每个训练样本赋予一个权值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)0d(i,i)=0d(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 criterionHierarchy algorithms:Create a hierarchical decomposition of the set of data(or objects)using some criterionDensity-based:based on connectivity and density functionsGrid-based:based on a multiple-level granularity structureModel-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%,层 1min_sup=5%,层 2min_sup=5%,工业控制技术研究所,支持度递减,支持度递减多层挖掘,酸奶 support=6%,脱脂奶 support=4%,层 1min_sup=5%,层 2min_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。我们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能