资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,工业控制技术研究所,Copyright by Song,Zhihuan,自动化前沿,第四讲 数据挖掘技术及其应用,宋执环,浙江大学工业控制研究所,控制科学与工程学系,研究生课程,工业控制技术研究所,主要内容,数据挖掘概述,数据预处理,数据挖掘算法分类与预测,数据挖掘算法聚类,数据挖掘算法关联分析,序列模式挖掘,数据挖掘软件,数据挖掘应用,工业控制技术研究所,一、数据挖掘概述,工业控制技术研究所,数据挖掘概念,数据挖掘,-,从大量数据中寻找其规律的技术，,是统计学、数据库技术和人工智能技术的综合。,数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构,；,数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型,。,数据挖掘与,KDD,工业控制技术研究所,数据挖掘与,KDD,知识发现（,KD）,输出的是规则,数据挖掘（,DM）,输出的是模型,共同点,两种方法输入的都是学习集（,learning sets,）,目的都是尽可能多的自动化数据挖掘过程,数据挖掘过程并不能完全自动化，只能半自动化,工业控制技术研究所,数据挖掘的社会需求,国民经济和社会的信息化,社会信息化后，社会的运转是软件的运转,社会信息化后，社会的历史是数据的历史,工业控制技术研究所,数据挖掘的社会需求,数据挖掘,数据库越来越大,有价值的知识,可怕的数据,工业控制技术研究所,数据挖掘的社会需求,数据爆炸，知识贫乏,苦恼,:,淹没在数据中,;,不能制定合适的决策,!,数据,知识,决策,模式,趋势,事实,关系,模型,关联规则,序列,目标市场,资金分配,贸易选择,在哪儿做广告,销售的地理位置,金融,经济,政府,POS.,人口统计,生命周期,工业控制技术研究所,数据挖掘的发展,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,的地球观测卫星以每小时,50,GB,的速度发回数据）,互联网数据,含噪音（不完全、不正确）,异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）,工业控制技术研究所,系统的特征,知识发现系统需要一个前处理过程,数据抽取,数据清洗,数据选择,数据转换,知识发现系统是一个自动,/,半自动过程,知识发现系统要有很好的性能,工业控制技术研究所,知识（模式）的特征,知识发现系统能够发现什么知识？,计算学习理论,COLT（Computational Learning Theory）,以,FOL,为基础的以发现关系为目的的归纳逻辑程序设计,现行的知识发现系统只能发现特定模式的知识,规则,分类,关联,工业控制技术研究所,知识表示：规则,IF,条件,THEN,结论,条件和结论的粒度（抽象度）可以有多种,单值,区间,模糊值,规则可以有确信度,精确规则,概率规则,工业控制技术研究所,知识表示：分类树,分类条件,1,分类条件,2,分类条件,3,类,1,类,2,类,3,类,4,工业控制技术研究所,数据挖掘算法的特征,构成数据挖掘算法的三要素,模式记述语言：反映了算法可以发现什么样的知识,模式评价：反映了什么样的模式可以称为知识,模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索,工业控制技术研究所,数据挖掘的主要方法,分类（,Classification）,聚类,(,Clustering),相关规则,(,Association Rule),回归,(,Regression),其他,工业控制技术研究所,数据挖掘系统,代,特征,数据挖掘算法,集成,分布计算模型,数据模型,第一代,数据挖掘作为一个独立的应用,支持一个或者多个算法,独立的系统,单个机器,向量数据,第二代,和数据库以及数据仓库集成,多个算法：能够挖掘一次不能放进内存的数据,数据管理系统，包括数据库和数据仓库,同质,/,局部区域的计算机群集,有些系统支持对象、文本、和连续的媒体数据,第三代,和预言模型系统集成,多个算法,数据管理和预言模型系统,intranet/extranet,网络计算,支持半结构化数据和,web,数据,第四代,和移动数据,/,各种计算数据联合,多个算法,数据管理、预言模型、移动系统,移动和各种计算设备,普遍存在的计算模型,工业控制技术研究所,数据挖掘系统,第一代数据挖掘系统,支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（,vector-valued data），,这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。,第二代数据挖掘系统,目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（,data mining schema,）,和数据挖掘查询语言（,DMQL,）,增加系统的灵活性。,工业控制技术研究所,数据挖掘系统,第三代数据挖掘系统,第三代的特征是能够挖掘,Internet/Extranet,的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（,first class,）,的支持。,第四代数据挖掘系统,第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（,ubiquitous,）,计算设备产生的各种类型的数据,。,工业控制技术研究所,二、数据预处理,工业控制技术研究所,为什么需要预处理,数据,不完整,含观测噪声,不一致,包含其它不希望的成分,数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。,工业控制技术研究所,污染数据形成的原因,滥用缩写词,数据输入错误,数据中的内嵌控制信息,不同的惯用语,重复记录,丢失值,拼写变化,不同的计量单位,过时的编码,含有各种噪声,工业控制技术研究所,数据清理的重要性,污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。,垃圾进、垃圾出,工业控制技术研究所,数据清理处理内容,格式标准化,异常数据清除,错误纠正,重复数据的清除,工业控制技术研究所,数据规约,数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果,主要策略,:,数据聚集,维规约,数据压缩,数值规约,工业控制技术研究所,空缺值,忽略元组,人工填写空缺值,使用固定值,使用属性平均值,使用最有可能值,工业控制技术研究所,噪声数据,如何平滑数据，去掉噪声,数据平滑技术,分箱,聚类,计算机和人工检查相结合,回归,工业控制技术研究所,分箱,箱的深度：表示不同的箱里有相同个数的数据。,箱的宽度：每个箱值的取值区间是个常数。,平滑方法,:,按箱平均值平滑,按箱中值平滑,按箱边界值平滑,工业控制技术研究所,聚类,每个簇中的数据用其中心值代替,忽略孤立点,先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。,人工再审查这些孤立点,工业控制技术研究所,回归,通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。,线性回归,多线性回归,工业控制技术研究所,数据集成,将多个数据源中的数据结合起来存放在一个一直得数据存贮中。,实体识别 实体和模式的匹配,冗余：某个属性可以由别的属性推出。,相关分析,相关性,r,A,B .,r,A,B,0,正相关。,A,随,B,的值得增大而增大,r,A,B,0,正相关。,AB,无关,r,A,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.,预测,分类：,预测分类标号（或离散值）,根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据,预测：,建立连续函数值模型，比如预测空缺值,典型应用,信誉证实,目标市场,医疗诊断,性能预测,工业控制技术研究所,数据分类：两步过程,第一步，建立一个模型，描述预定数据类集和概念集,假定每个元组属于一个预定义的类，由一个类标号属性确定,基本概念,训练数据集,：由为建立模型而被分析的数据元组形成,训练样本,：训练数据集中的单个样本（元组）,学习模型可以用分类规则、判定树或数学公式的形式提供,第二步，使用模型，对将来的或未知的对象进行分类,首先评估模型的预测准确率,对每个测试样本，将已知的类标号和该样本的学习模型类预测比较,模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比,测试集要独立于训练样本集，否则会出现“过分适应数据”的情况,工业控制技术研究所,第一步：建立模型,训练数,据集,分类算法,IF rank = professor,OR years 6,THEN tenured = yes,分类规则,工业控制技术研究所,第二步：用模型进行分类,分类规则,测试集,未知数据,(Jeff, Professor, 4),Tenured?,工业控制技术研究所,准备分类和预测的数据,通过对数据进行预处理，可以提高分类和预测过程的准确性、有效性和可伸缩性,数据清理,消除或减少噪声，处理空缺值，从而减少学习时的混乱,相关性分析,数据中的有些属性可能与当前任务不相关；也有些属性可能是冗余的；删除这些属性可以加快学习步骤，使学习结果更精确,数据变换,可以将数据概化到较高层概念，或将数据进行规范化,工业控制技术研究所,比较分类方法,使用下列标准比较分类和预测方法,预测的准确率：模型正确预测新数据的类编号的能力,速度：产生和使用模型的计算花销,鲁棒性：给定噪声数据或有空缺值的数据，模型正确预测的能力,可伸缩性：对大量数据，有效的构建模型的能力,可解释性：学习模型提供的理解和洞察的层次,工业控制技术研究所,用判定树归纳分类,什么是判定树？,类似于流程图的树结构,每个内部节点表示在一个属性上的测试,每个分枝代表一个测试输出,每个树叶节点代表类或类分布,判定树的生成由两个阶段组成,判定树构建,开始时，所有的训练样本都在根节点,递归的通过选定的属性，来划分样本 （必须是离散值）,树剪枝,许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝,判定树的使用：对未知样本进行分类,通过将样本的属性值与判定树相比较,工业控制技术研究所,判定归纳树算法,判定归纳树算法（一个贪心算法）,自顶向下的分治方式构造判定树,树以代表训练样本的单个根节点开始,使用分类属性（如果是量化属性，则需先进行离散化）,递归的通过选择相应的,测试属性,，来划分样本，一旦一个属性出现在一个节点上，就不在该节点的任何后代上出现,测试属性是根据某种启发信息或者是统计信息来进行选择（如：信息增益）,递归划分步骤停止的条件,给定节点的所有样本属于同一类,没有剩余属性可以用来进一步划分样本,使用多数表决,没有剩余的样本,详细算法见P189,工业控制技术研究所,贝叶斯分类,贝叶斯分类利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。,朴素贝叶斯分类：假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。,工业控制技术研究所,后向传播分类,后向传播是一种神经网络学习算法；神经网络是一组连接的输入,/,输出单元，每个连接都与一个权相连。在学习阶段，通过调整神经网络的权，使得能够预测输入样本的正确标号来学习。,优点,预测精度总的来说较高,健壮性好，训练样本中包含错误时也可正常工作,输出可能是离散值、连续值或者是离散或量化属性的向量值,对目标进行分类较快,缺点,训练（学习）时间长,蕴涵在学习的权中的符号含义很难理解,很难根专业领域知识相整合,工业控制技术研究所,其他分类方法,k-,最临近分类,给定一个未知样本，,k-,最临近分类法搜索模式空间，找出最接近未知样本的,k,个训练样本；然后使用,k,个最临近者中最公共的类来预测当前样本的类标号,基于案例的推理,样本或案例使用复杂的符号表示，对于新案例，先检测是否存在同样的训练案例；如果找不到，则搜索类似的训练案例,遗传算法,结合生物进化思想的算法,粗糙集方法,模糊集方法,允许在分类规则中定义“模糊的”临界值或边界,工业控制技术研究所,什么是预测？,预测是构造和使用模型评估无样本类，或评估给定样本可能具有的属性或值空间。,预测和分类的异同,相同点,两者都需要构建模型,都用模型来估计未知值,预测当中主要的估计方法是回归分析,线性回归和多元回归,非线性回归,不同点,分类法主要是用来预测类标号（分类属性值）,预测法主要是用来估计连续值（量化属性值）,工业控制技术研究所,回归方法,线性回归：,Y =, + X,其中,和,是回归系数，可以根据给定的数据点，通过最小二乘法来求得,多元回归：,Y =, + ,1,X,1,+ ,2,X,2,线性回归的扩展，设计多个预测变量，可以用最小二乘法求得上式中的,，,1,和,2,非线性回归：,Y =, + ,1,X,1,+ ,2,X,2,2,+ ,3,X,3,3,对不呈线性依赖的数据建模,使用多项式回归建模方法，然后进行变量变换，将非线性模型转换为线性模型，然后用最小二乘法求解,工业控制技术研究所,评估分类法的准确性,导出分类法后，再使用训练数据评估分类法，可能错误的导致乐观的估计,保持方法,给定数据随机划分为两个集合：训练集,(2/3),和测试集,(1/3),训练集导出分类法，测试集对其准确性进行评估,随机子选样,：保持方法的一个变形，将保持方法重复,k,次，然后取准确率的平均值,k-,折交叉确认,初始数据被划分为,k,个不相交的，大小大致相同的子集,S,1,S,2,S,k,进行,k,次训练和测试，第,i,次时，以,S,i,做测试集，其他做训练集,准确率为,k,次迭代正确分类数除以初始数据集样本总数,工业控制技术研究所,提高分类法的准确性,Bagging,技术和,boosting,技术都通过将,T,个学习得到的分类法,C,1,C,2,C,T,组合起来，从而创造一个改进的分类法,C*,Bagging,技术,对训练集,S,进行,T,次迭代，每次通过放回取样选取样本集,S,t,，,通过学习,S,t,得到分类法,C,t,对于未知样本,X,，,每个分类法返回其类预测，作为一票,C*,统计得票，并将得票最高的预测赋予,X,Boosting,技术,每个训练样本赋予一个权值,C,t,的权值取决于其错误率,工业控制技术研究所,四、数据挖掘算法聚类,工业控制技术研究所,聚类分析,什么是聚类分析,?,聚类分析中的数据类型,主要聚类分析方法分类,划分方法（,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,= (,x,i1,x,i2, ,x,ip,),和,j,= (,x,j1,x,j2, ,x,jp,),是两个,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,个状态是以有意义的序列排序的，比如职称,连续的序数型变量类似于区间标度变量，但是它没有单位，值的相对顺序是必要的，而其实际大小并不重要。,工业控制技术研究所,序数型变量,相异度的计算,与区间标度变量的计算方法相类似,将,x,if,用它对应的秩代替,将每个变量的值域映射到,0.0，1.0,上，使得每个变量都有相同的权重。这通过用,z,if,来替代,r,if,来实现,用前面所述的区间标度变量的任一种距离计算方法来计算,工业控制技术研究所,比例标度型变量,比例标度型变量,（,Ratio-scaled variable）,:,总是取正的度量值，有一个非线性的标度，近似的遵循指数标度，比如,Ae,Bt,or,Ae,-Bt,计算相异度的方法,:,采用与处理区间标度变量相同的方法,不是一个好的选择,进行对数变换，对变换得到的值在采用与处理区间标度变量相同的方法,y,if,=,log(,x,if,),将其作为连续的序数型数据，将其秩作为区间标度的值来对待。,工业控制技术研究所,混合类型的变量,一个数据库可能包含了所有这,6,中类型的变量,用以下公式计算对象,i，j,之间的相异度,.,其中，,p,为对象中的变量个数,如果,x,if,或,x,jf,缺失（即对象,i,或对象,j,没有变量,f,的值），或者,x,if,=,x,jf,=0，,且变量,f,是不对称的二元变量，则指示项,ij,(f)=0,；,否则,ij,(f)=1,工业控制技术研究所,混合类型的变量,f,是二元变量或标称变量,:,if,x,if,=,x,jf,d,ij,(f),= 0, else,d,ij,(f),= 1,f,是区间标度变量,:,d,ij,(f),= |,x,if,-,x,jf,|/,max,h,x,hf,-,min,h,x,hf,其中,h,遍取变量,f,的所有非空缺对象,f,是序数型或比例标度型,计算秩,r,if,计算,z,if,并将其作为区间标度变量值对待,工业控制技术研究所,主要聚类方法,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, H,ead 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,维立方体的每个单元 对应一个维词集合,使用数据立方体速度更快,(income),(age),(),(buys),(age, income),(age,buys),(income,buys),(age,income,buys),工业控制技术研究所,带数量的关联规则,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-,维数量关联规则：,A,quan1, A,quan2,A,cat,用,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,个元组,t,1, t,2, ,t,N,在 属性集,X,上的投影,则,SX,的直径,:,dist,x,:,距离量度,如 欧几里德距离或,Manhattan,聚集和距离度量,工业控制技术研究所,用直径,d,评估,聚集,C,X,的密度，其中,查找聚集和基于距离的规则,用密度阈值,d,0,代替支持度,采用修改过的,BIRCH,聚集算法,聚集和距离度量,工业控制技术研究所,关联规则可视化,Using Plane Graph,工业控制技术研究所,关联规则可视化,Using Rule Graph,工业控制技术研究所,六、序列模式挖掘,工业控制技术研究所,序列模式概念,序列模式的概念最早是由,Agrawal,和,Srikant,提出的,序列模式定义：给定一个由不同序列组成的集合，其中，每个,序列,由不同的元素按顺序有序排列，每个,元素,由不同,项目,组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值,工业控制技术研究所,序列模式实例,例1,：在两年前购买了,Ford,牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动,例,2,：在购买了自行车和购物篮的所有客户中，有,70%,的客户会在两个月后购买打气筒,例,3,：工业过程控制领域：过程变量采样值时时间序列；变量之间的关系是动态的；系统故障模式；等等,工业控制技术研究所,序列模式应用领域,应用领域：,客户购买行为模式预测,Web,访问模式预测,疾病诊断,自然灾害预测,DNA,序列分析,工业控制,工业控制技术研究所,序列模式表示,符号化表示：,项目集,(,Itemset,),是各种项目组成的集合,序列,(,Sequence),是不同项目集,(,ItemSet,),的有序排列，序列,s,可以表示为,s = ，s,j,(1 = j = l),为项目集,(,Itemset,)，,也,称为序列,s,的元素,序列的元素,(,Element),可表示为,(,x,1,x,2,x,m,)， x,k,(1 = k = m),为,不同的项目，如果一个序列只有一个项目，则括号可以省略,一个序列包含的所有项目的个数称为序列的长度。长度为,l,的序列记为,l-,序列,工业控制技术研究所,序列模式表示,符号化表示：,设,=,，, =,，,如果存在整数,1 =,j,1, j,2,j,n,= m，,使得,a,1,b,j1,，a,2,b,j2,， a,n,b,jn,，,则称序列,为序列,的子序列，又称序列,包含序列,，记为 ,序列在序列数据库,S,中的支持数为序列数据库,S,中包含序列的序列个数，记为,Support(),给定支持度阈值，如果序列在序列数据库中的支持数不低于，则称序列为序列模式,长度,为,l,的序列模式记为,l-,模式,工业控制技术研究所,序列模式表示,例子：设序列数据库如下图所示，并设用户指定的最小支持度,min-support = 2。,Sequence_id,Sequence,10,20,30,40,序列,是序列,的子序列,序列,是长度为,3,的序列模式,工业控制技术研究所,序列模式挖掘,问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式,系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列,工业控制技术研究所,序列模式挖掘算法,序列模式挖掘的主要算法,GSP(Generalized Sequential Patterns),算法：类似于,Apriori,算法,PrefixSpan,(,Prefix,-project,S,equential,Pa,tter,n,mining),算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘,工业控制技术研究所,序列模式挖掘算法,上述算法存在的主要问题：,缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔。例如，一个序列模式可能会发现客户在购买了物品,A,后的第三年购买物品,B,。,我们需要的却是给定时间间隔内用户的购买意向,事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务,缺少分类层次：,只能在项目的原始级别上进行挖掘,工业控制技术研究所,七、数据挖掘软件,工业控制技术研究所,数据挖掘软件的发展,代,特征,数据挖掘算法,集成,分布计算模型,数据模型,第一代,作为一个独立的应用,支持一个或者多个算法,独立的系统,单个机器,向量数据,第二代,和数据库以及数据仓库集成,多个算法：能够挖掘一次不能放进内存的数据,数据管理系统，包括数据库和数据仓库,同质、局部区域的计算机群集,有些系统支持对象,文本和连续的媒体数据,第三代,和预言模型系统集成,多个算法,数据管理和预言模型系统,intranet/extranet,网络计算,支持半结构化数据和,web,数据,第四代,和移动数据,/,各种计算设备的数据联合,多个算法,数据管理、预言模型、移动系统,移动和各种计算设备,普遍存在的计算模型,工业控制技术研究所,数据挖掘软件的发展,第一代数据挖掘软件,特点,支持一个或少数几个数据挖掘算法,挖掘向量数据（,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,设备）的第四
展开阅读全文