数据挖掘(偶然看到比较好的)

自动化前沿第四讲数据挖掘技术及其应用宋执环浙江大学工业控制研究所控制科学与工程学系研究生课程主要内容数据挖掘概述数据预处理数据挖掘算法－分类与预测数据挖掘算法－聚类数据挖掘算法－关联 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 序列模式挖掘数据挖掘软件数据挖掘应用一、数据挖掘概述数据挖掘概念数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。数据挖掘与KDD数据挖掘与KDD知识发现（KD）输出的是规则数据挖掘（DM）输出的是模型共同点两种方法输入的都是学习集（learningsets）目的都是尽可能多的自动化数据挖掘过程数据挖掘过程并不能完全自动化，只能半自动化数据挖掘的社会需求国民经济和社会的信息化社会信息化后，社会的运转是软件的运转社会信息化后，社会的历史是数据的历史数据挖掘的社会需求数据挖掘数据库越来越大有价值的知识可怕的数据数据挖掘的社会需求数据爆炸，知识贫乏苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府POS.人口统计生命周期数据挖掘的发展1989IJCAI会议：数据库中的知识发现讨论专题KnowledgeDiscoveryinDatabases(G.Piatetsky-ShapiroandW.Frawley,1991)1991-1994KDD讨论专题AdvancesinKnowledgeDiscoveryandDataMining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,andR.Uthurusamy,1996)1995-1998KDD国际会议(KDD’95-98)JournalofDataMiningandKnowledgeDiscovery(1997)1998ACMSIGKDD,SIGKDD’1999-2002会议,以及SIGKDDExplorations数据挖掘方面更多的国际会议PAKDD,PKDD,SIAM-DataMining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.数据挖掘技术技术分类预言（Predication）：用历史预测未来描述（Description）：了解数据中潜在的规律数据挖掘技术关联分析序列模式分类（预言）聚集异常检测异常检测异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。异常探测应用电信和信用卡欺骗贷款审批药物研究气象预报金融领域客户分类网络入侵检测故障检测与诊断等什么是异常（outlier）？Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。异常检测方法的分类基于统计（statistical-based)的方法基于距离(distance-based)的方法基于偏差(deviation-based)的方法基于密度(density-based)的方法高维数据的异常探测数据挖掘系统的特征数据的特征知识的特征算法的特征矿山（数据）挖掘工具（算法）金子（知识）数据的特征大容量POS数据（某个超市每天要处理高达2000万笔交易）卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据）互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）系统的特征知识发现系统需要一个前处理过程数据抽取数据清洗数据选择数据转换知识发现系统是一个自动/半自动过程知识发现系统要有很好的性能知识（模式）的特征知识发现系统能够发现什么知识？计算学习理论COLT（ComputationalLearningTheory）以FOL为基础的以发现关系为目的的归纳逻辑程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 现行的知识发现系统只能发现特定模式的知识规则分类关联知识表示：规则IF条件THEN结论条件和结论的粒度（抽象度）可以有多种单值区间模糊值规则可以有确信度精确规则概率规则知识表示：分类树分类条件1分类条件2分类条件3类1类2类3类4数据挖掘算法的特征构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索数据挖掘的主要方法分类（Classification）聚类(Clustering)相关规则(AssociationRule)回归(Regression)其他数据挖掘系统代特征数据挖掘算法集成分布计算模型数据模型第一代数据挖掘作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质/局部区域的计算机群集有些系统支持对象、文本、和连续的媒体数据第三代和预言模型系统集成多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算数据联合多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型数据挖掘系统第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valueddata），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（dataminingschema）和数据挖掘查询语言（DMQL）增加系统的灵活性。数据挖掘系统第三代数据挖掘系统第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（firstclass）的支持。第四代数据挖掘系统第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据。二、数据预处理为什么需要预处理数据不完整含观测噪声不一致包含其它不希望的成分数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。污染数据形成的原因滥用缩写词数据输入错误数据中的内嵌控制信息不同的惯用语重复记录丢失值拼写变化不同的计量单位过时的编码含有各种噪声数据清理的重要性污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。垃圾进、垃圾出数据清理处理内容格式 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 化异常数据清除错误纠正重复数据的清除数据规约数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果主要策略:数据聚集维规约数据压缩数值规约空缺值忽略元组人工填写空缺值使用固定值使用属性平均值使用最有可能值噪声数据如何平滑数据，去掉噪声数据平滑技术分箱聚类计算机和人工检查相结合回归分箱箱的深度：表示不同的箱里有相同个数的数据。箱的宽度：每个箱值的取值区间是个常数。平滑方法:按箱平均值平滑按箱中值平滑按箱边界值平滑聚类每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点回归通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归多线性回归数据集成将多个数据源中的数据结合起来存放在一个一直得数据存贮中。实体识别实体和模式的匹配冗余：某个属性可以由别的属性推出。相关分析相关性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规则如果一个区间最高有效位上包括369个不同的值，划分为3个等宽区间。7个不同值，按2-3-3划分为3个区间最高位包含2，4，8个不同值，划分为4个等宽区间最高位包含1，5，10个不同值，划分为5个等宽区间最高分层一般在第5个百分位到第95个百分位上进行分类数据的概念分层生成分类数据是离散数据。一个分类属性可能有有限个不同的值。方法由用户和专家在模式级显式的说明属性的部分序通过显式的数据分组说明分层结构的一部分说明属性集，但不说明他们的偏序只说明部分的属性集三、数据挖掘算法－分类与预测分类VS.预测分类：预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据预测：建立连续函数值模型，比如预测空缺值典型应用信誉证实目标市场医疗诊断性能预测数据分类：两步过程第一步，建立一个模型，描述预定数据类集和概念集假定每个元组属于一个预定义的类，由一个类标号属性确定基本概念训练数据集：由为建立模型而被分析的数据元组形成训练样本：训练数据集中的单个样本（元组）学习模型可以用分类规则、判定树或数学公式的形式提供第二步，使用模型，对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本，将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集，否则会出现“过分适应数据”的情况第一步：建立模型训练数据集分类算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分类规则第二步：用模型进行分类分类规则测试集未知数据(Jeff,Professor,4)Tenured?准备分类和预测的数据通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性数据清理消除或减少噪声，处理空缺值，从而减少学习时的混乱相关性分析数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确数据变换可以将数据概化到较高层概念，或将数据进行规范化比较分类方法使用下列标准比较分类和预测方法预测的准确率：模型正确预测新数据的类编号的能力速度：产生和使用模型的计算花销鲁棒性：给定噪声数据或有空缺值的数据，模型正确预测的能力可伸缩性：对大量数据，有效的构建模型的能力可解释性：学习模型提供的理解和洞察的层次用判定树归纳分类什么是判定树？类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布判定树的生成由两个阶段组成判定树构建开始时，所有的训练样本都在根节点递归的通过选定的属性，来划分样本（必须是离散值）树剪枝许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝判定树的使用：对未知样本进行分类通过将样本的属性值与判定树相比较判定归纳树算法判定归纳树算法（一个贪心算法）自顶向下的分治方式构造判定树树以代表训练样本的单个根节点开始使用分类属性（如果是量化属性，则需先进行离散化）递归的通过选择相应的测试属性，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益）递归划分步骤停止的条件给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本——使用多数表决没有剩余的样本贝叶斯分类贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。后向传播分类后向传播是一种神经网络学习算法；神经网络是一组连接的输入/输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。优点预测精度总的来说较高健壮性好，训练样本中包含错误时也可正常工作输出可能是离散值、连续值或者是离散或量化属性的向量值对目标进行分类较快缺点训练（学习）时间长蕴涵在学习的权中的符号含义很难理解很难根专业领域知识相整合其他分类方法k-最临近分类给定一个未知样本，k-最临近分类法搜索模式空间，找出最接近未知样本的k个训练样本；然后使用k个最临近者中最公共的类来预测当前样本的类标号基于案例的推理样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例遗传算法结合生物进化思想的算法粗糙集方法模糊集方法允许在分类规则中定义“模糊的”临界值或边界什么是预测？预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。预测和分类的异同相同点两者都需要构建模型都用模型来估计未知值预测当中主要的估计方法是回归分析线性回归和多元回归非线性回归不同点分类法主要是用来预测类标号（分类属性值）预测法主要是用来估计连续值（量化属性值）回归方法线性回归：Y=+X其中和是回归系数，可以根据给定的数据点，通过最小二乘法来求得多元回归：Y=+1X1+2X2线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的，1和2非线性回归：Y=+1X1+2X22+3X33对不呈线性依赖的数据建模使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解评估分类法的准确性导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计保持方法给定数据随机划分为两个集合：训练集(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*统计得票，并将得票最高的预测赋予XBoosting技术每个训练样本赋予一个权值Ct的权值取决于其错误率四、数据挖掘算法－聚类聚类分析什么是聚类分析?聚类分析中的数据类型主要聚类分析方法分类划分方法（PartitioningMethods）分层方法基于密度的方法基于表格的方法基于模型（Model-Based）的聚类方法异常分析总结什么是聚类分析?簇（Cluster）:一个数据对象的集合在同一个类中，对象之间0具有相似性；不同类的对象之间是相异的。聚类分析把一个给定的数据对象集合分成不同的簇；聚类是一种无监督分类法:没有预先指定的类别；典型的应用作为一个独立的分析工具，用于了解数据的分布；作为其它算法的一个数据预处理步骤；聚类的常规应用模式识别空间数据分析在GIS中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解释空间中的簇；图象处理经济学(尤其是市场研究方面)WWW文档分类分析WEB日志数据来发现相似的访问模式应用聚类分析的例子市场销售:帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用:在一个陆地观察数据库中标识那些土地使用相似的地区；保险:对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:根据地质断层的特点把已观察到的地震中心分成不同的类；聚类方法性能评价一个好的聚类方法要能产生高质量的聚类结果——簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；聚类方法性能评价可伸缩性能够处理不同类型的属性能发现任意形状的簇在决定输入参数的时候，尽量不需要特定的领域知识；能够处理噪声和异常对输入数据对象的顺序不敏感能处理高维数据能产生一个好的、能满足用户指定约束的聚类结果结果是可解释的、可理解的和可用的两种数据结构数据矩阵(twomodes)差异度矩阵(onemode)评价聚类质量差异度/相似度矩阵:相似度通常用距离函数来表示；有一个单独的质量评估函数来评判一个簇的好坏；对不同类型的变量，距离函数的定义通常是不同的，这在下面有详细讨论；根据实际的应用和数据的语义，在计算距离的时候，不同的变量有不同的权值相联系；很难定义“足够相似了”或者“足够好了”只能凭主观确定；聚类分析中的数据类型区间标度变量（Interval-scaledvariables）:二元变量（Binaryvariables）:标称型，序数型和比例型变量（Nominal,ordinal,andratiovariables）:混合类型变量（Variablesofmixedtypes）:区间标度变量数据标准化计算绝对偏差的平均值:其中计算标准度量值(z-score)使用绝对偏差的平均值比使用标准偏差更健壮（robust）计算对象之间的相异度通常使用距离来衡量两个对象之间的相异度。常用的距离度量方法有:明考斯基距离（Minkowskidistance）:其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是两个p维的数据对象,q是一个正整数。当q=1时,d称为曼哈坦距离（Manhattandistance）计算对象之间的相异度当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-scaledvariable）:总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如AeBtorAe-Bt计算相异度的方法:采用与处理区间标度变量相同的方法—不是一个好的选择进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法yif=log(xif)将其作为连续的序数型数据，将其秩作为区间标度的值来对待。混合类型的变量一个数据库可能包含了所有这6中类型的变量用以下公式计算对象i，j之间的相异度.其中，p为对象中的变量个数如果xif或xjf缺失（即对象i或对象j没有变量f的值），或者xif=xjf=0，且变量f是不对称的二元变量，则指示项δij(f)=0；否则δij(f)=1混合类型的变量f是二元变量或标称变量:ifxif=xjfdij(f)=0,elsedij(f)=1f是区间标度变量:dij(f)=|xif-xjf|/maxhxhf-minhxhf其中h遍取变量f的所有非空缺对象f是序数型或比例标度型计算秩rif计算zif并将其作为区间标度变量值对待主要聚类方法Partitioningalgorithms:ConstructvariouspartitionsandthenevaluatethembysomecriterionHierarchyalgorithms:Createahierarchicaldecompositionofthesetofdata(orobjects)usingsomecriterionDensity-based:basedonconnectivityanddensityfunctionsGrid-based:basedonamultiple-levelgranularitystructureModel-based:Amodelishypothesizedforeachoftheclustersandtheideaistofindthebestfitofthatmodeltoeachother五、数据挖掘算法－关联什么是关联挖掘?关联规则挖掘：在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用：购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。举例：规则形式：“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%ofpeoplewhopurchasetiresandautoaccessoriesalsogetautomotiveservicesdone应用*护理用品(商店应该怎样提高护理用品的销售？)家用电器*(其他商品的库存有什么影响?)在产品直销中使用附加邮寄Detecting“ping-pong”ingofpatients,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,SSD’95).逐步求精空间关联规则挖掘空间关系的层次：“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维立方体的每个单元对应一个维词集合使用数据立方体速度更快(income)(age)()(buys)(age,income)(age,buys)(income,buys)(age,income,buys)带数量的关联规则age(X,”30-34”)income(X,”24K-48K”)buys(X,”highresolutionTV”)动态离散化数值属性Suchthattheconfidenceorcompactnessoftherulesminedismaximized.2-维数量关联规则：Aquan1Aquan2Acat用2-维表格把“邻近”的关联规则组合起来例子ARCS(关联规则聚集系统)ARCS流程1.分箱2.查找频繁维词集合3.聚集4.优化ARCS的局限性数值属性只能出现在规则的左侧左侧只能有两个属性(2维)ARCS的改进不用基于栅格的方法等深分箱基于局部完整性测度的聚集“MiningQuantitativeAssociationRulesinLargeRelationalTables”byR.SrikantandR.Agrawal.基于距离的关联规则挖掘分箱的方法没有体现数据间隔的语义基于距离的分割是更有“意义”的离散化方法，考虑：区间内密度或点的个数区间内点的“紧密程度记S[X]为N个元组t1,t2,…,tN在属性集X上的投影则S[X]的直径:distx:距离量度,如欧几里德距离或Manhattan聚集和距离度量用直径d评估聚集CX的密度，其中查找聚集和基于距离的规则用密度阈值d0代替支持度采用修改过的BIRCH聚集算法聚集和距离度量关联规则可视化UsingPlaneGraph关联规则可视化UsingRuleGraph六、序列模式挖掘序列模式概念序列模式的概念最早是由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<=j140<(ef)(ab)(df)cb>30<(ad)c(bc)(ae)>2010SequenceSequence_id序列是序列的子序列序列<(ab)c>是长度为3的序列模式序列模式挖掘问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列序列模式挖掘算法序列模式挖掘的主要算法GSP(GeneralizedSequentialPatterns)算法：类似于Apriori算法PrefixSpan(Prefix-projectSequentialPatternmining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘序列模式挖掘算法上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务缺少分类层次：只能在项目的原始级别上进行挖掘七、数据挖掘软件数据挖掘软件的发展代特征数据挖掘算法集成分布计算模型数据模型第一代作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质、局部区域的计算机群集有些系统支持对象,文本和连续的媒体数据第三代和预言模型系统集成多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算设备的数据联合多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型数据挖掘软件的发展第一代数据挖掘软件特点支持一个或少数几个数据挖掘算法挖掘向量数据（vector-valueddata）数据一般一次性调进内存进行处理典型的系统如SalfordSystems公司早期的CART系统(www.salford-systems.com)缺陷如果数据足够大，并且频繁的变化，这就需要利用数据库或者数据仓库技术进行管理，第一代系统显然不能满足需求。数据挖掘软件的发展第一代数据挖掘软件CBA新加坡国立大学。基于关联规则的分类算法，能从关系数据或者交易数据中挖掘关联规则，使用关联规则进行分类和预测二、数据挖掘软件的发展第二代数据挖掘软件特点与数据库管理系统（DBMS）集成支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性能够挖掘大数据集、以及更复杂的数据集通过支持数据挖掘模式（dataminingschema）和数据挖掘查询语言增加系统的灵活性典型的系统如DBMiner，能通过DMQL挖掘语言进行挖掘操作缺陷只注重模型的生成，如何和预言模型系统集成导致了第三代数据挖掘系统的开发数据挖掘软件的发展第二代数据挖掘软件DBMiner数据挖掘软件的发展第二代软件SASEnterpriseMiner数据挖掘软件的发展第三代数据挖掘软件特点和预言模型系统之间能够无缝的集成，使得由数据挖掘软件产生的模型的变化能够及时反映到预言模型系统中由数据挖掘软件产生的预言模型能够自动地被操作型系统吸收，从而与操作型系统中的预言模型相联合提供决策支持的功能能够挖掘网络环境下（Internet/Extranet）的分布式和高度异质的数据，并且能够有效地和操作型系统集成缺陷不能支持移动环境数据挖掘软件的发展第三代软件SPSSClementine以PMML的格式提供与预言模型系统的接口二、数据挖掘软件的发展第四代数据挖掘软件特点目前移动计算越发显得重要，将数据挖掘和移动计算相结合是当前的一个研究领域。第四代软件能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据第四代数据挖掘原型或商业系统尚未见报导，PKDD2001上Kargupta发表了一篇在移动环境下挖掘决策树的 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 ，Kargupta是马里兰巴尔的摩州立大学（UniversityofMarylandBaltimoreCounty）正在研制的CAREER数据挖掘项目的负责人，该项目研究期限是2001年4月到2006年4月，目的是开发挖掘分布式和异质数据（Ubiquitous设备）的第四代数据挖掘系统。数据挖掘软件的发展第一代系统与第二代相比因为不具有和数据管理系统之间有效的接口，所以在数据预处理方面有一定缺陷第三、四代系统强调预测模型的使用和操作型环境的部署第二代系统提供数据管理系统和数据挖掘系统之间的有效接口第三代系统另外还提供数据挖掘系统和预言模型系统之间的有效的接口目前，随着新的挖掘算法的研究和开发，第一代数据挖掘系统仍然会出现，第二代系统是商业软件的主流，部分第二代系统开发商开始研制相应的第三代数据挖掘系统，比如IBMIntelligentScoreService。第四代数据挖掘原型或商业系统尚未见报导数据挖掘软件的发展数据挖掘软件发展的三个阶段独立的数据挖掘软件横向的数据挖掘工具集纵向的数据挖掘解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数据挖掘软件的发展独立的数据挖掘软件（95年以前）特点独立的数据挖掘软件对应第一代系统，出现在数据挖掘技术发展早期，研究人员开发出一种新型的数据挖掘算法，就形成一个软件。这类软件要求用户对具体的算法和数据挖掘技术有相当的了解，还要负责大量的数据预处理工作。比如C4.5决策树，平行坐标可视化（parallel-coordinatevisualization）。数据挖掘软件的发展横向的数据挖掘工具集（95年开始）发展原因随着数据挖掘应用的发展，人们逐渐认识到数据挖掘软件需要和以下三个方面紧密结合：1）数据库和数据仓库；2）多种类型的数据挖掘算法；3）数据清洗、转换等预处理工作。随着数据量的增加，需要利用数据库或者数据仓库技术进行管理，所以数据挖掘系统与数据库和数据仓库结合是自然的发展。现实领域的问题是多种多样的，一种或少数数据挖掘算法难以解决挖掘的数据通常不符合算法的要求，需要有数据清洗、转换等数据预处理的配合，才能得出有价值的模型数据挖掘软件的发展横向的数据挖掘工具集（95年开始）发展过程随着这些需求的出现，1995年左右软件开发商开始提供称之为“工具集”的数据挖掘软件特点此类工具集的特点是提供多种数据挖掘算法包括数据的转换和可视化由于此类工具并非面向特定的应用，是通用的算法集合，可以称之为横向的数据挖掘工具（HorizontalDataMiningTools）由于此类工具并非面向特定的应用，是通用的算法集合，所以称之为横向的数据挖掘工具典型的横向工具有IBMIntelligentMiner、SPSS的Clementine、SAS的EnterpriseMiner、SGI的MineSet、OracleDarwin等数据挖掘软件的发展横向的数据挖掘工具集（95年开始）IBMIntelligentMinerSPSS的ClementineSAS的EnterpriseMinerSGI的MineSetOracleDarwin数据挖掘软件的发展纵向的数据挖掘解决方案（99年开始）发展原因随着横向的数据挖掘工具的使用日渐广泛，人们也发现这类工具只有精通数数据挖掘算法的专家才能熟练使用，如果对算法不了解，难以得出好的模型从1999年开始，大量的数据挖掘工具研制者开始提供纵向的数据挖掘解决方案（VerticalSolution），即针对特定的应用提供完整的数据挖掘方案对于纵向的解决方案，数据挖掘技术的应用多数还是为了解决某些特定的难题，而嵌入在应用系统中数据挖掘软件的发展纵向的数据挖掘解决方案（99年开始）在证券系统中嵌入神经网络预测功能在欺诈检测系统中嵌入欺诈行为的分类/识别模型在客户关系管理系统中嵌入客户成簇/分类功能或客户行为分析功能在机器维护系统中嵌入监/检测或识别难以定性的设备故障功能在数据库营销中嵌入选择最可能购买产品的客户功能在机场管理系统中嵌入旅客人数预测、货运优化功能在基因分析系统中嵌入DNA识别功能在制造/生产系统中嵌入质量控制功能等数据挖掘软件的发展纵向的数据挖掘解决方案（99年开始）KD1（主要用于零售业）Options&Choice(主要用于保险业)HNC（欺诈行为侦测）UnicaModel1(主要用于市场营销)数据挖掘软件的发展各行业电子商务网站算法层商业逻辑层行业应用层商业应用商业模型挖掘算法CRM产品推荐客户细分客户流失客户利润客户响应关联规则、序列模式、分类、聚集、神经元网络、偏差分析…WEB挖掘网站结构优化网页推荐商品推荐。。。基因挖掘基因表达路径分析基因表达相似性分析基因表达共发生分析。。。银行电信零售保险制药生物信息科学研究。。。相关行业数据挖掘软件的现状情况概览2002年9月，Amazon上关于数据挖掘的书有251本(www.amazon.com)目前有数百个数据挖掘软件产品（www.kdnuggets.com）数据挖掘应用相对广泛数据挖掘软件的现状国内大部分处于科研阶段各大学和科研机构从事数据挖掘算法的研究国内著作的数据挖掘方面的书较少（翻译的有）数据挖掘讨论组（www.dmgroup.org.cn）有一些公司在国外产品基础上开发的特定的应用IBMIntelligentMinerSASEnterpriseMiner自主知识产权的数据挖掘软件复旦德门（www.datamining.com.cn）等八、数据挖掘应用数据挖掘应用数据挖掘应用银行美国银行家协会(ABA)预测数据仓库和数据挖掘技术在美国商业银行的应用增长率是14.9％。分析客户使用分销渠道的情况和分销渠道的容量；建立利润评测模型；客户关系优化；风险控制等电子商务网上商品推荐；个性化网页；自适应网站…生物制药、基因研究DNA序列查询和匹配；识别基因序列的共发生性…电信欺诈甄别；客户流失…保险、零售。。。。。。数据挖掘应用数据挖掘客户分析析基分因其他保险客户证券客户银行客户电信客户零售客户信用卡储蓄卡存折按揭借贷人类基因植物基因动物基因特殊群体基因基因序列基因表达谱基因功能基因制药………...数据挖掘应用为什么没有广泛使用？数据挖掘正在快速的发展技术的研究和开发已经走在很前沿的地方数据挖掘应用面已经扩充了很多但是仍然没有希望的高，为什么？希望在多少年内达到数十亿元的盈利？是一种增值服务（Notbread-and-butter）不能认为高不可攀，所以不去过问是一门年轻的技术，需要和实际结合，解决现实问题数据挖掘应用国内应用存在的问题数据积累不充分、不全面业务模型构建困难缺少有经验的实施者数据挖掘应用Debt<10%ofIncomeDebt=0%GoodCreditRisksBadCreditRisksGoodCreditRisksYesYesYesNONONOIncome>$40KQQQQII123456factor1factor2factorn神经网络NeuralNetworks聚类分析ClusteringOpenAccn’tAddNewProductDecreaseUsage???Time序列分析SequenceAnalysis决策树DecisionTrees倾向性分析客户保留客户生命周期管理目标市场价格弹性分析客户细分市场细分倾向性分析客户保留目标市场欺诈检测关联分析Association市场组合分析套装产品分析目录设计交叉销售数据挖掘应用聚集（Cluster）聚集是把整个数据库分成不同的群组。它的目的是要群与群之间差别很明显，而同一个群之间的数据尽量相似。常用技术：神经元网络、K均值、最近邻…数据挖掘应用异常检测及时发现有欺诈嫌疑的异常行为，正确进行欺诈问题的评估，对欺诈者实施控制和强制措施。技术：决策树，神经元网络，异常因子LOF检测客户消费异常行为分析模型数据挖掘应用客户分析业务模型交叉销售客户响应客户流失客户利润信用卡分析业务模型客户信用等级评估客户透支分析客户利润分析客户消费行为分析客户消费异常行为分析数据挖掘应用MISERPCRME_BusinessCDW客户数据仓库数据挖掘算法库模型库组件库产品推荐客户细分客户流失客户利润客户响应…行业应用知识CIAS应用服务器信息系统行业分析数据挖掘应用平台CIAS数据挖掘应用客户响应模型—基本概念响应率分析:分析客户对某种新服务或者新产品的感兴趣情况.为什么要进行响应率分析:通过响应率分析能够有效的降低市场推广的费用,同时能够更加有针对性的面对目标市场.达到以最小的投入获得最佳效果的目的数据挖掘应用用哪一种数据挖掘技术实现？响应率分析是为了对某项市场营销（新产品销售）活动找到最合适的响应客户，需要预测哪些客户能够响应，以及响应的可能性是多少。因此，需要构建预言模型分类是预言模型的一种技术，可以利用分类技术构建客户响应率模型决策树神经网络贝叶斯分类…数据挖掘未来发展与数据库数据仓库系统集成与预言模型系统集成挖掘各种复杂类型的数据与应用相结合研制和开发数据挖掘标准支持移动环境数据挖掘应用——时间序列模式挖掘工业过程变量时间序列生产过程的类型连续过程：工艺参数（设定值）均为常量。批量过程：工艺参数（设定值）通常为变量。工艺参数的数据类型数值型、逻辑型、枚举型产品质量的数据类型逻辑型：只判断产品的好坏数值型：给出产品质量好坏的程度生产过程工艺参数1（连续型时间序列）工艺参数2（离散型时间序列）产品质量（离散型时间序列）批量型生产过程质量检验！t0t1t2t3T预热阶段加热阶段均热阶段T连续型生产过程T1T2T3vx1x2x3质量检验！0x预热区加热区均热区t0t1t2t3质量检验！TT1T3T2数据挖掘对象的基本构成生产过程X：工艺参数时间序列Y：质量检测结果tXtY样本的抽取（批量生产过程）ttx1(t)y1y2y3x2(t)x3(t)XY样本1样本2样本3……连续生产过程的样本抽取连续过程批量过程T1T2T3vx1x2x3tT3T2T10质量检验！0T1T2T3Ttt1＝x1/vt2＝x2/vt3＝x3/v0质量检验！t1t2t3如何“组装”时间序列？T1T3T2质量检验！tT3T2T10t1t2t3质量检验！T组装前t0t1t2t3T组装后样本关于生产质量改变的模式假设生产质量不良的原因是工艺参数设计或控制有问题：设计阶段：工艺参数设计有错误；控制阶段：工艺参数未能控制在设计值；上述因素都可通过生产过程中工艺参数的时间序列实测样本反映出来。工艺参数的时间序列中某些特征的改变，引起生产质量从量变到质变。时间序列的特征，可以用模式来描述。时间序列的模式改变，是生产质量不良的原因。数据挖掘的目的，就是要寻找引起生产质量不良的工艺参数模式。时间序列的模式抽取目的：将时间序列样本集合转换为特征模式样本集合，每一种模式（或若干种模式的一种组合）用一个整数来编码，从而将数据挖掘的对象从时间序列空间转换为整数空间。其中，mi为xi(t)所包含的特征模式的集合。注意：mi不再是时间序列mi可能是多元素的集合，即xi(t)可包含多种模式模式抽取时间序列的模式抽取时间序列分析理论中已给出一类模式抽取的方法：根据时间序列建立ARMA模型。或理解为把时间序列空间映射到ARMA模型中的参数空间，也称为时间序列的ARMA特征空间。这一方法的优点是：成熟有严密的数学基础缺点是：ARMA特征没有物理意义，难以据其改进产品质量。时间序列的模式抽取（有物理意义的）模式抽取问题：给定（有物理意义的）模式集