数据挖掘(浙江大学研究生课程-自动化方向)

©CopyrightbySongZhihuan工业控制技术研究所自动化前沿第四讲数据挖掘技术及其应用宋执环浙江大学工业控制研究所控制科学与工程学系研究生课程©CopyrightbySongZhihuan工业控制技术研究所主要内容数据挖掘概述数据预处理数据挖掘算法－分类与预测数据挖掘算法－聚类数据挖掘算法－关联分析序列模式挖掘数据挖掘软件数据挖掘应用©CopyrightbySongZhihuan工业控制技术研究所一、数据挖掘概述©CopyrightbySongZhihuan工业控制技术研究所数据挖掘概念数据挖掘--从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术的综合。数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构；数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型。数据挖掘与KDD©CopyrightbySongZhihuan工业控制技术研究所数据挖掘与KDD知识发现（KD）输出的是规则数据挖掘（DM）输出的是模型共同点两种方法输入的都是学习集（learningsets）目的都是尽可能多的自动化数据挖掘过程数据挖掘过程并不能完全自动化，只能半自动化©CopyrightbySongZhihuan工业控制技术研究所数据挖掘的社会需求国民经济和社会的信息化•社会信息化后，社会的运转是软件的运转•社会信息化后，社会的历史是数据的历史©CopyrightbySongZhihuan工业控制技术研究所数据挖掘的社会需求数据挖掘数据库越来越大有价值的知识可怕的数据©CopyrightbySongZhihuan工业控制技术研究所数据挖掘的社会需求数据爆炸，知识贫乏苦恼:淹没在数据中;不能制定合适的决策!数据知识决策模式趋势事实关系模型关联规则序列目标市场资金分配贸易选择在哪儿做广告销售的地理位置金融经济政府POS.人口统计生命周期©CopyrightbySongZhihuan工业控制技术研究所数据挖掘的发展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.©CopyrightbySongZhihuan工业控制技术研究所数据挖掘技术技术分类预言（Predication）：用历史预测未来描述（Description）：了解数据中潜在的规律数据挖掘技术关联分析序列模式分类（预言）聚集异常检测©CopyrightbySongZhihuan工业控制技术研究所异常检测异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。异常探测应用电信和信用卡欺骗贷款审批药物研究气象预报金融领域客户分类网络入侵检测故障检测与诊断等©CopyrightbySongZhihuan工业控制技术研究所什么是异常（outlier）？Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。©CopyrightbySongZhihuan工业控制技术研究所异常检测方法的分类基于统计（statistical-based)的方法基于距离(distance-based)的方法基于偏差(deviation-based)的方法基于密度(density-based)的方法高维数据的异常探测©CopyrightbySongZhihuan工业控制技术研究所数据挖掘系统的特征数据的特征知识的特征算法的特征矿山（数据）挖掘工具（算法）金子（知识）©CopyrightbySongZhihuan工业控制技术研究所数据的特征大容量•POS数据（某个超市每天要处理高达2000万笔交易）•卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据）•互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）©CopyrightbySongZhihuan工业控制技术研究所系统的特征知识发现系统需要一个前处理过程•数据抽取•数据清洗•数据选择•数据转换知识发现系统是一个自动/半自动过程知识发现系统要有很好的性能©CopyrightbySongZhihuan工业控制技术研究所知识（模式）的特征知识发现系统能够发现什么知识？计算学习理论COLT（ComputationalLearningTheory）以FOL为基础的以发现关系为目的的归纳逻辑程序设计现行的知识发现系统只能发现特定模式的知识规则分类关联©CopyrightbySongZhihuan工业控制技术研究所知识表示：规则IF条件THEN结论条件和结论的粒度（抽象度）可以有多种单值区间模糊值规则可以有确信度精确规则概率规则©CopyrightbySongZhihuan工业控制技术研究所知识表示：分类树分类条件1分类条件2分类条件3类1类2类3类4©CopyrightbySongZhihuan工业控制技术研究所数据挖掘算法的特征构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索©CopyrightbySongZhihuan工业控制技术研究所数据挖掘的主要方法分类（Classification）聚类(Clustering)相关规则(AssociationRule)回归(Regression)其他©CopyrightbySongZhihuan工业控制技术研究所数据挖掘系统代特征数据挖掘算法集成分布计算模型数据模型第一代数据挖掘作为一个独立的应用支持一个或者多个算法独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质/局部区域的计算机群集有些系统支持对象、文本、和连续的媒体数据第三代和预言模型系统集成多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算数据联合多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型©CopyrightbySongZhihuan工业控制技术研究所数据挖掘系统第一代数据挖掘系统支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valueddata），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。第二代数据挖掘系统目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（dataminingschema）和数据挖掘查询语言（DMQL）增加系统的灵活性。©CopyrightbySongZhihuan工业控制技术研究所数据挖掘系统第三代数据挖掘系统第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（firstclass）的支持。第四代数据挖掘系统第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据。©CopyrightbySongZhihuan工业控制技术研究所二、数据预处理©CopyrightbySongZhihuan工业控制技术研究所为什么需要预处理数据不完整含观测噪声不一致包含其它不希望的成分数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。©CopyrightbySongZhihuan工业控制技术研究所污染数据形成的原因滥用缩写词数据输入错误数据中的内嵌控制信息不同的惯用语重复记录丢失值拼写变化不同的计量单位过时的编码含有各种噪声©CopyrightbySongZhihuan工业控制技术研究所数据清理的重要性1.污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。2.垃圾进、垃圾出©CopyrightbySongZhihuan工业控制技术研究所数据清理处理内容格式标准化异常数据清除错误纠正重复数据的清除©CopyrightbySongZhihuan工业控制技术研究所数据规约数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果主要策略:数据聚集维规约数据压缩数值规约©CopyrightbySongZhihuan工业控制技术研究所空缺值忽略元组人工填写空缺值使用固定值使用属性平均值使用最有可能值©CopyrightbySongZhihuan工业控制技术研究所噪声数据如何平滑数据，去掉噪声数据平滑技术分箱聚类计算机和人工检查相结合回归©CopyrightbySongZhihuan工业控制技术研究所分箱箱的深度：表示不同的箱里有相同个数的数据。箱的宽度：每个箱值的取值区间是个常数。平滑方法:按箱平均值平滑按箱中值平滑按箱边界值平滑©CopyrightbySongZhihuan工业控制技术研究所聚类每个簇中的数据用其中心值代替忽略孤立点先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。人工再审查这些孤立点©CopyrightbySongZhihuan工业控制技术研究所回归通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。线性回归多线性回归©CopyrightbySongZhihuan工业控制技术研究所数据集成将多个数据源中的数据结合起来存放在一个一直得数据存贮中。实体识别实体和模式的匹配冗余：某个属性可以由别的属性推出。相关分析相关性rA,B.rA,B0,正相关。A随B的值得增大而增大rA,B0,正相关。AB无关rA,B0,正相关。A随B的值得增大而减少重复同一数据存储多次数据值冲突的检测和处理©CopyrightbySongZhihuan工业控制技术研究所数据变换平滑聚集数据概化规范化属性构造(特征构造)©CopyrightbySongZhihuan工业控制技术研究所最小最大规范化小数定标规范化属性构造由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解规范化©CopyrightbySongZhihuan工业控制技术研究所数据立方体聚集寻找感兴趣的维度进行再聚集©CopyrightbySongZhihua