数据挖掘1(经典)PPT课件.ppt

Copyright by Song ZhihuanCopyright by Song Zhihuan自动化前沿自动化前沿第四讲 数据挖掘技术及其应用宋执环宋执环浙江大学工业控制研究所浙江大学工业控制研究所控制科学与工程学系 研究生课程研究生课程.Copyright by Song ZhihuanCopyright by Song Zhihuan主要内容主要内容 l数据挖掘概述数据挖掘概述数据挖掘概述数据挖掘概述l数据预处理数据预处理数据预处理数据预处理l数据挖掘算法分类与预测数据挖掘算法分类与预测数据挖掘算法分类与预测数据挖掘算法分类与预测l数据挖掘算法聚类数据挖掘算法聚类数据挖掘算法聚类数据挖掘算法聚类l数据挖掘算法关联分析数据挖掘算法关联分析数据挖掘算法关联分析数据挖掘算法关联分析l序列模式挖掘序列模式挖掘序列模式挖掘序列模式挖掘l数据挖掘软件数据挖掘软件数据挖掘软件数据挖掘软件l数据挖掘应用数据挖掘应用数据挖掘应用数据挖掘应用.Copyright by Song ZhihuanCopyright by Song Zhihuan一、数据挖掘概述一、数据挖掘概述.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘概念数据挖掘概念l数据挖掘数据挖掘-从大量数据中寻找其规律的技从大量数据中寻找其规律的技术，是统计学、数据库技术和人工智能技术，是统计学、数据库技术和人工智能技术的综合。术的综合。l数据挖掘是从数据中自动地抽取模式、关联、变数据挖掘是从数据中自动地抽取模式、关联、变化、异常和有意义的结构化、异常和有意义的结构；l数据挖掘大部分的价值在于利用数据挖掘技术改数据挖掘大部分的价值在于利用数据挖掘技术改善预测模型善预测模型。数据挖掘与数据挖掘与KDD.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘与数据挖掘与KDDl知识发现（知识发现（知识发现（知识发现（KDKD）输出的是规则输出的是规则输出的是规则输出的是规则 l数据挖掘（数据挖掘（数据挖掘（数据挖掘（DMDM）输出的是模型输出的是模型输出的是模型输出的是模型 l共同点共同点共同点共同点两种方法输入的都是学习集（两种方法输入的都是学习集（两种方法输入的都是学习集（两种方法输入的都是学习集（learning setslearning sets）目的都是尽可能多的自动化数据挖掘过程目的都是尽可能多的自动化数据挖掘过程目的都是尽可能多的自动化数据挖掘过程目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全自动化，只能半自动化数据挖掘过程并不能完全自动化，只能半自动化数据挖掘过程并不能完全自动化，只能半自动化数据挖掘过程并不能完全自动化，只能半自动化 .Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘的社会需求数据挖掘的社会需求国民经济和社会的信息化国民经济和社会的信息化社会信息化后，社会的运转是软件的运转社会信息化后，社会的运转是软件的运转社会信息化后，社会的历史是数据的历史社会信息化后，社会的历史是数据的历史.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘的社会需求数据挖掘的社会需求数据挖掘数据挖掘数据库越来越大数据库越来越大有价值的知识有价值的知识可怕的数据可怕的数据.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘的社会需求数据挖掘的社会需求数据爆炸，知识贫乏数据爆炸，知识贫乏 苦恼:淹没在数据中;不能制定合适的决策!数据数据知识知识决策决策n模式模式n趋势趋势n事实事实n关系关系n模型模型n关联规则关联规则n序列序列n目标市场目标市场n资金分配资金分配n贸易选择贸易选择n在哪儿做广告在哪儿做广告n销售的地理位置销售的地理位置n金融金融n经济经济n政府政府nPOS.n人口统计人口统计n生命周期生命周期.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘的发展数据挖掘的发展l l1989 IJCAI1989 IJCAI会议：会议：数据库中的知识发现讨论专题数据库中的知识发现讨论专题Knowledge Discovery in Databases(G.Piatetsky-Shapiro and W.Knowledge Discovery in Databases(G.Piatetsky-Shapiro and W.Frawley,1991)Frawley,1991)l l1991-1994 KDD1991-1994 KDD讨论专题讨论专题Advances in Knowledge Discovery and Data Mining(U.Fayyad,G.Advances in Knowledge Discovery and Data Mining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy,1996)Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy,1996)l l1995-1998 KDD1995-1998 KDD国际会议国际会议(KDD95-98)(KDD95-98)Journal of Data Mining and Knowledge Discovery(1997)Journal of Data Mining and Knowledge Discovery(1997)l l1998 ACM SIGKDD,SIGKDD1999-2002 1998 ACM SIGKDD,SIGKDD1999-2002 会议会议,以及以及SIGKDD SIGKDD ExplorationsExplorationsl l数据挖掘方面更多的国际会议数据挖掘方面更多的国际会议PAKDD,PKDD,SIAM-Data Mining,(IEEE)ICDM,DaWaK,SPIE-PAKDD,PKDD,SIAM-Data Mining,(IEEE)ICDM,DaWaK,SPIE-DM,etc.DM,etc.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘技术数据挖掘技术l技术分类技术分类预言（预言（PredicationPredication）：用历史预测未来）：用历史预测未来描述（描述（DescriptionDescription）：了解数据中潜在的规律）：了解数据中潜在的规律l数据挖掘技术数据挖掘技术关联分析关联分析序列模式序列模式分类（分类（预言预言）聚集聚集异常检测异常检测.Copyright by Song ZhihuanCopyright by Song Zhihuan异常检测异常检测l l异常检测是数据挖掘中一个重要方面，用来发现异常检测是数据挖掘中一个重要方面，用来发现异常检测是数据挖掘中一个重要方面，用来发现异常检测是数据挖掘中一个重要方面，用来发现”小的模小的模小的模小的模式式式式”(”(相对于聚类相对于聚类相对于聚类相对于聚类)，即数据集中间显著不同于其它数据的对，即数据集中间显著不同于其它数据的对，即数据集中间显著不同于其它数据的对，即数据集中间显著不同于其它数据的对象。象。象。象。l l异常探测应用异常探测应用异常探测应用异常探测应用电信和信用卡欺骗电信和信用卡欺骗电信和信用卡欺骗电信和信用卡欺骗贷款审批贷款审批贷款审批贷款审批药物研究药物研究药物研究药物研究气象预报气象预报气象预报气象预报金融领域金融领域金融领域金融领域客户分类客户分类客户分类客户分类网络入侵检测网络入侵检测网络入侵检测网络入侵检测故障检测与诊断等故障检测与诊断等故障检测与诊断等故障检测与诊断等 .Copyright by Song ZhihuanCopyright by Song Zhihuan什么是异常（什么是异常（outlier）？）？l lHawkins(1980)Hawkins(1980)给出了异常的本质性的定义：给出了异常的本质性的定义：给出了异常的本质性的定义：给出了异常的本质性的定义：异常是在数异常是在数异常是在数异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏据集中与众不同的数据，使人怀疑这些数据并非随机偏据集中与众不同的数据，使人怀疑这些数据并非随机偏据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。差，而是产生于完全不同的机制。差，而是产生于完全不同的机制。差，而是产生于完全不同的机制。l l 聚类算法对异常的定义：聚类算法对异常的定义：聚类算法对异常的定义：聚类算法对异常的定义：异常是聚类嵌于其中的背景噪异常是聚类嵌于其中的背景噪异常是聚类嵌于其中的背景噪异常是聚类嵌于其中的背景噪声。声。声。声。l l异常检测算法对异常的定义：异常检测算法对异常的定义：异常检测算法对异常的定义：异常检测算法对异常的定义：异常是既不属于聚类也不异常是既不属于聚类也不异常是既不属于聚类也不异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不属于背景噪声的点。他们的行为与正常的行为有很大不属于背景噪声的点。他们的行为与正常的行为有很大不属于背景噪声的点。他们的行为与正常的行为有很大不同。同。同。同。.Copyright by Song ZhihuanCopyright by Song Zhihuan异常检测方法的分类异常检测方法的分类l基于统计（基于统计（基于统计（基于统计（statistical-based)statistical-based)的方法的方法的方法的方法l基于距离基于距离基于距离基于距离(distance-based)(distance-based)的方法的方法的方法的方法l基于偏差基于偏差基于偏差基于偏差(deviation-based)(deviation-based)的方法的方法的方法的方法l基于密度基于密度基于密度基于密度(density-based)(density-based)的方法的方法的方法的方法l高维数据的异常探测高维数据的异常探测高维数据的异常探测高维数据的异常探测.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘系统的特征数据挖掘系统的特征数据的特征数据的特征知识的特征知识的特征算法的特征算法的特征矿山（数据）挖掘工具（算法）金子（知识）.Copyright by Song ZhihuanCopyright by Song Zhihuan数据的特征数据的特征大容量大容量 POSPOS数据（某个超市每天要处理高达数据（某个超市每天要处理高达20002000万笔交万笔交易）易）卫星图象（卫星图象（NASANASA的地球观测卫星以每小时的地球观测卫星以每小时5050GBGB的速度发回数据）的速度发回数据）互联网数据互联网数据含噪音（不完全、不正确）含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）自互联网的数据是典型的例子）.Copyright by Song ZhihuanCopyright by Song Zhihuan系统的特征系统的特征知识发现系统需要一个前处理过程知识发现系统需要一个前处理过程 数据抽取数据抽取 数据清洗数据清洗 数据选择数据选择 数据转换数据转换知识发现系统是一个自动知识发现系统是一个自动/半自动过程半自动过程知识发现系统要有很好的性能知识发现系统要有很好的性能.Copyright by Song ZhihuanCopyright by Song Zhihuan知识（模式）的特征知识（模式）的特征知识发现系统能够发现什么知识？知识发现系统能够发现什么知识？计算学习理论计算学习理论COLTCOLT（Computational Learning Computational Learning TheoryTheory）以以FOLFOL为基础的以发现关系为目的的归纳逻辑程序设计为基础的以发现关系为目的的归纳逻辑程序设计现行的知识发现系统只能发现特定模式的知识现行的知识发现系统只能发现特定模式的知识规则规则分类分类关联关联.Copyright by Song ZhihuanCopyright by Song Zhihuan知识表示：规则知识表示：规则IF IF 条件条件 THEN THEN 结论结论条件和结论的粒度（抽象度）可以有多种条件和结论的粒度（抽象度）可以有多种单值单值区间区间模糊值模糊值规则可以有确信度规则可以有确信度精确规则精确规则概率规则概率规则.Copyright by Song ZhihuanCopyright by Song Zhihuan知识表示：分类树知识表示：分类树分类条件1分类条件2分类条件3类1类2类3类4.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘算法的特征数据挖掘算法的特征构成数据挖掘算法的三要素构成数据挖掘算法的三要素模式记述语言：反映了算法可以发现什么样的知模式记述语言：反映了算法可以发现什么样的知识识模式评价：反映了什么样的模式可以称为知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索探索和对模式空间的探索.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘的主要方法数据挖掘的主要方法分类（分类（ClassificationClassification）聚类聚类(Clustering)Clustering)相关规则相关规则(Association Rule)Association Rule)回归回归(Regression)Regression)其他其他.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘系统数据挖掘系统代代特征特征数据挖掘算法数据挖掘算法集成集成分布计算分布计算模型模型数据模型数据模型第一代第一代数数据据挖挖掘掘作作为为一一个个独独立立的的应应用用支持一个或者支持一个或者多个算法多个算法 独立的系独立的系统统单个机单个机器器向量数据向量数据第二代第二代和和数数据据库库以以及及数据仓库集成数据仓库集成多多个个算算法法：能能够够挖挖掘掘一一次次不不能能放放进内存的数据进内存的数据数数据据管管理理系系统统，包包括括数数据据库库和和数数据据仓库仓库同质同质/局局部区域部区域的计算的计算机群集机群集有有些些系系统统支支持持对对象象、文文本本、和和连连续续的媒体数据的媒体数据第三代第三代和预言模型系和预言模型系统集成统集成 多个算法多个算法数数据据管管理理和和预预言言模模型型系系统统intranet/extranet网网络计算络计算支支持持半半结结构构化化 数数 据据 和和webweb数据数据第四代第四代和移动数据和移动数据/各种计算数据各种计算数据联合联合 多个算法多个算法数数据据管管理理、预预言言模模型型、移动系统移动系统移移动动和和各各种种计计算算设设备备普普遍遍存存在在的的计计算算模模型型.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘系统数据挖掘系统l第一代数据挖掘系统第一代数据挖掘系统第一代数据挖掘系统第一代数据挖掘系统 支支支支持持持持一一一一个个个个或或或或少少少少数数数数几几几几个个个个数数数数据据据据挖挖挖挖掘掘掘掘算算算算法法法法，这这这这些些些些算算算算法法法法设设设设计计计计用用用用来来来来挖挖挖挖掘掘掘掘向向向向量量量量数数数数据据据据（vector-valued vector-valued vector-valued vector-valued datadatadatadata），这这这这些些些些数数数数据据据据模模模模型型型型在在在在挖挖挖挖掘掘掘掘时时时时候候候候，一一一一般般般般一一一一次次次次性性性性调调调调进进进进内内内内存存存存进进进进行行行行处处处处理理理理。许许许许多这样的系统已经商业化。多这样的系统已经商业化。多这样的系统已经商业化。多这样的系统已经商业化。l第二代数据挖掘系统第二代数据挖掘系统第二代数据挖掘系统第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二目前的研究，是改善第一代数据挖掘系统，开发第二目前的研究，是改善第一代数据挖掘系统，开发第二目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库和代数据挖掘系统。第二代数据挖掘系统支持数据库和代数据挖掘系统。第二代数据挖掘系统支持数据库和代数据挖掘系统。第二代数据挖掘系统支持数据库和数据仓库，和它们具有高性能的接口，具有高的可扩数据仓库，和它们具有高性能的接口，具有高的可扩数据仓库，和它们具有高性能的接口，具有高的可扩数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂展性。例如，第二代系统能够挖掘大数据集、更复杂展性。例如，第二代系统能够挖掘大数据集、更复杂展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据的数据集、以及高维数据。这一代系统通过支持数据的数据集、以及高维数据。这一代系统通过支持数据的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（挖掘模式（挖掘模式（挖掘模式（data mining schemadata mining schema）和数据挖掘查询语言）和数据挖掘查询语言）和数据挖掘查询语言）和数据挖掘查询语言（DMQLDMQL）增加系统的灵活性。）增加系统的灵活性。）增加系统的灵活性。）增加系统的灵活性。.Copyright by Song ZhihuanCopyright by Song Zhihuan数据挖掘系统数据挖掘系统l第三代数据挖掘系统第三代数据挖掘系统第三代数据挖掘系统第三代数据挖掘系统 第三代的特征是能够挖掘第三代的特征是能够挖掘第三代的特征是能够挖掘第三代的特征是能够挖掘Internet/ExtranetInternet/Extranet的分布式和的分布式和的分布式和的分布式和高度异质的数据，并且能够有效地和操作型系统集成。高度异质的数据，并且能够有效地和操作型系统集成。高度异质的数据，并且能够有效地和操作型系统集成。高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在这一代数据挖掘系统关键的技术之一是提供对建立在这一代数据挖掘系统关键的技术之一是提供对建立在这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的异质系统上的多个预言模型以及管理这些预言模型的异质系统上的多个预言模型以及管理这些预言模型的异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（元数据提供第一级别（元数据提供第一级别（元数据提供第一级别（first classfirst class）的支持。）的支持。）的支持。）的支持。l第四代数据挖掘系统第四代数据挖掘系统第四代数据挖掘系统第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、第四代数据挖掘系统能够挖掘嵌入式系统、移动系统、和普遍存在（和普遍存在（和普遍存在（和普遍存在（ubiquitousubiquitous）计算设备产生的各种类型的）计算设备产生的各种类型的）计算设备产生的各种类型的）计算设备产生的各种类型的数据数据数据数据 。.Copyright by Song ZhihuanCopyright by Song Zhihuan二、数据预处理二、数据预处理.Copyright by Song ZhihuanCopyright by Song Zhihuan为什么需要预处理为什么需要预处理l数据数据数据数据不完整不完整不完整不完整含观测噪声含观测噪声含观测噪声含观测噪声不一致不一致不一致不一致包含其它不希望的成分包含其它不希望的成分包含其它不希望的成分包含其它不希望的成分l数据清理通过填写空缺值，平滑噪声数据，识别数据清理通过填写空缺值，平滑噪声数据，识别数据清理通过填写空缺值，平滑噪声数据，识别数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。删除孤立点，并解决不一致来清理数据。删除孤立点，并解决不一致来清理数据。删除孤立点，并解决不一致来清理数据。.Copyright by Song ZhihuanCopyright by Song Zhihuan污染数据形成的原因污染数据形成的原因l l滥用缩写词滥用缩写词滥用缩写词滥用缩写词l l数据输入错误数据输入错误数据输入错误数据输入错误l l数据中的内嵌控制信息数据中的内嵌控制信息数据中的内嵌控制信息数据中的内嵌控制信息l l不同的惯用语不同的惯用语不同的惯用语不同的惯用语l l重复记录重复记录重复记录重复记录l l丢失值丢失值丢失值丢失值l l拼写变化拼写变化拼写变化拼写变化l l不同的计量单位不同的计量单位不同的计量单位不同的计量单位l l过时的编码过时的编码过时的编码过时的编码l l含有各种噪声含有各种噪声含有各种噪声含有各种噪声.Copyright by Song ZhihuanCopyright by Song Zhihuan数据清理的重要性数据清理的重要性1.污染数据的普遍存在，使得在大型数据库污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及中维护数据的正确性和一致性成为一个及其困难的任务。其困难的任务。2.垃圾进、垃圾出垃圾进、垃圾出.Copyright by Song ZhihuanCopyright by Song Zhihuan数据清理处理内容数据清理处理内容l格式标准化格式标准化l异常数据清除异常数据清除l错误纠正错误纠正l重复数据的清除重复数据的清除.Copyright by Song ZhihuanCopyright by Song Zhihuan数据规约数据规约l数据集的压缩表示，但是能和原始数据集达到相数据集的压缩表示，但是能和原始数据集达到相数据集的压缩表示，但是能和原始数据集达到相数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果同或基本相同的分析结果同或基本相同的分析结果同或基本相同的分析结果l主要策略主要策略主要策略主要策略:数据聚集数据聚集数据聚集数据聚集维规约维规约维规约维规约数据压缩数据压缩数据压缩数据压缩数值规约数值规约数值规约数值规约.Copyright by Song ZhihuanCopyright by Song Zhihuan空缺值空缺值l忽略元组忽略元组忽略元组忽略元组l人工填写空缺值人工填写空缺值人工填写空缺值人工填写空缺值l使用固定值使用固定值使用固定值使用固定值l使用属性平均值使用属性平均值使用属性平均值使用属性平均值l使用最有可能值使用最有可能值使用最有可能值使用最有可能值.Copyright by Song ZhihuanCopyright by Song Zhihuan噪声数据噪声数据l如何平滑数据，去掉噪声如何平滑数据，去掉噪声如何平滑数据，去掉噪声如何平滑数据，去掉噪声l数据平滑技术数据平滑技术数据平滑技术数据平滑技术分箱分箱分箱分箱聚类聚类聚类聚类计算机和人工检查相结合计算机和人工检查相结合计算机和人工检查相结合计算机和人工检查相结合回归回归回归回归.Copyright by Song ZhihuanCopyright by Song Zhihuan分箱分箱l箱的深度：表示不同的箱里有相同个数的数据。箱的深度：表示不同的箱里有相同个数的数据。箱的深度：表示不同的箱里有相同个数的数据。箱的深度：表示不同的箱里有相同个数的数据。l箱的宽度：每个箱值的取值区间是个常数。箱的宽度：每个箱值的取值区间是个常数。箱的宽度：每个箱值的取值区间是个常数。箱的宽度：每个箱值的取值区间是个常数。l平滑方法平滑方法平滑方法平滑方法:按箱平均值平滑按箱平均值平滑按箱平均值平滑按箱平均值平滑按箱中值平滑按箱中值平滑按箱中值平滑按箱中值平滑按箱边界值平滑按箱边界值平滑按箱边界值平滑按箱边界值平滑.Copyright by Song ZhihuanCopyright by Song Zhihuan聚类聚类l每个簇中的数据用其中心值代替每个簇中的数据用其中心值代替每个簇中的数据用其中心值代替每个簇中的数据用其中心值代替l忽略孤立点忽略孤立点忽略孤立点忽略孤立点l先通过聚类等方法找出孤立点。这些孤立点可能先通过聚类等方法找出孤立点。这些孤立点可能先通过聚类等方法找出孤立点。这些孤立点可能先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。包含有用的信息。包含有用的信息。包含有用的信息。l人工再审查这些孤立点人工再审查这些孤立点人工再审查这些孤立点人工再审查这些孤立点.Copyright by Song ZhihuanCopyright by Song Zhihuan回归回归l通过构造函数来符合数据变化的趋势，这样可以通过构造函数来符合数据变化的趋势，这样可以通过构造函数来符合数据变化的趋势，这样可以通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。用一个变量预测另一个变量。用一个变量预测另一个变量。用一个变量预测另一个变量。线性回归线性回归线性回归线性回归多线性回归多线性回归多线性回归多线性回归.Copyright by Song ZhihuanCopyright by Song Zhihuan数据集成数据集成l l将多个数据源中的数据结合起来存放在一个一直得数据存将多个数据源中的数据结合起来存放在一个一直得数据存将多个数据源中的数据结合起来存放在一个一直得数据存将多个数据源中的数据结合起来存放在一个一直得数据存贮中。贮中。贮中。贮中。l l实体识别实体识别实体识别实体识别 实体和模式的匹配实体和模式的匹配实体和模式的匹配实体和模式的匹配l l冗余：某个属性可以由别的属性推出。冗余：某个属性可以由别的属性推出。冗余：某个属性可以由别的属性推出。冗余：某个属性可以由别的属性推出。相关分析相关分析相关分析相关分析相关性相关性相关性相关性r rA,B.A,B.r rA,BA,B0,0,正相关。正相关。正相关。正相关。A A随随随随B B的值得增大而增大的值得增大而增大的值得增大而增大的值得增大而增大r rA,BA,B0,0,正相关。正相关。正相关。正相关。ABAB无关无关无关无关r rA,BA,B0,0,正相关。正相关。正相关。正相关。A A随随随随B B的值得增大而减少的值得增大而减少的值得增大而减少的值得增大而减少l l重复重复重复重复 同一数据存储多次同一数据存储多次同一数据存储多次同一数据存储多次l l数据值冲突的检测和处理数据值冲突的检测和处理数据值冲突的检测和处理数据值冲突的检测和处理.Copyright by Song ZhihuanCopyright by Song Zhihuan数据变换数据变换l平滑平滑平滑平滑l聚集聚集聚集聚集l数据概化数据概化数据概化数据概化l规范化规范化规范化规范化l属性构造属性构造属性构造属性构造(特征构造特征构造特征构造特征构造).Copyright by Song ZhihuanCopyright by Song Zhihuanl最小最小最小最小 最大规范化最大规范化最大规范化最大规范化l小数定标规范化小数定标规范化小数定标规范化小数定标规范化l属性构造属性构造属性构造属性构造由给定的属性构造和添加新的属性，以帮助提高精度由给定的属性构造和添加新的属性，以帮助提高精度由给定的属性构造和添加新的属性，以帮助提高精度由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解和对高维数据结构的理解和对高维数据结构的理解和对高维数据结构的理解规范化规范化.Copyright by Song ZhihuanCopyright by Song Zhihuan数据立方体聚集数据立方体聚集l寻找感兴趣的维度进行再聚集寻找感兴趣的维度进行再聚集寻找感兴趣的维度进行再聚集寻找感兴趣的维度进行再聚集.Copyright by Song ZhihuanCopyright by Song Zhihuan维规约维规约l删除不相关的属性（维）来减少数据量。删除不相关的属性（维）来减少数据量。删除不相关的属性（维）来减少数据量。删除不相关的属性（维）来减少数据量。l属性子集选择属性子集选择属性子集选择属性子集选择找出最小属性集合，使得数据类的概率分布找出最小属性集合，使得数据类的概率分布找出最小属性集合，使得数据类的概率分布找出最小属性集合，使得数据类的概率分布尽可能地接近使用所有属性的原分布尽可能地接近使用所有属性的原分布尽可能地接近使用所有属性的原分布尽可能地接近使用所有属性的原分布如何选取？如何选取？如何选取？如何选取？贪心算法贪心算法贪心算法贪心算法逐步向前选择逐步向前选择逐步向前选择逐步向前选择逐步后向删除逐步后向删除逐步后向删除逐步后向删除向前选择和后向删除相结合向前选择和后向删除相结合向前选择和后向删除相结合向前选择和后向删除相结合判定树归纳判定树归纳判定树归纳判定树归纳.Copyright by Song ZhihuanCopyright by Song Zhihuan数据压缩数据压缩l有损，无损有损，无损有损，无损有损，无损l小波变换小波变换小波变换小波变换将数据向量将数据向量将数据向量将数据向量D D转换成为数值上不同的小波系数的向量转换成为数值上不同的小波系数的向量转换成为数值上不同的小波系数的向量转换成为数值上不同的小波系数的向量D.D.对对对对DD进行剪裁，保留小波系数最强的部分。进行剪裁，保留小波系数最强的部分。进行剪裁，保留小波系数最强的部分。进行剪裁，保留小波系数最强的部分。l主要成分分析主要成分分析主要成分分析主要成分分析.Copyright by Song ZhihuanCopyright by Song Zhihuan数值规约数值规约l回归和对数线形模型回归和对数线形模型回归和对数线形模型回归和对数线形模型线形回归线形回归线形回归线形回归对数线形模型对数线形模型对数线形模型对数线形模型l直方图直方图直方图直方图等宽等宽等宽等宽等深等深等深等深V-V-最优最优最优最优maxDiffmaxDiff.Copyright by Song ZhihuanCopyright by Song Zhihuan数值规约数值规约l聚类聚类聚类聚类多维索引树多维索引树多维索引树多维索引树 ：对于给定的数据集合，索引树动态的对于给定的数据集合，索引树动态的对于给定的数据集合，索引树动态的对于给定的数据集合，索引树动态的划分多维空间。划分多维空间。划分多维空间。划分多维空间。l选样选样选样选样简单选择简单选择简单选择简单选择n n个样本，不放回个样本，不放回个样本，不放回个样本，不放回简单选择简单选择简单选择简单选择n n个样本，放回个样本，放回个样本，放回个样本，放回聚类选样聚类选样聚类选样聚类选样分层选样分层选样分层选样分层选样.Copyright by Song ZhihuanCopyright by Song Zhihuan离散化和概念分层离散化和概念分层l离散化技术用来减少给定连续属性的个数离散化技术用来减少给定连续属性的个数离散化技术用来减少给定连续属性的个数离散化技术用来减少给定连续属性的个数l通常是递归的。通常是递归的。通常是递归的。通常是递归的。l大量时间花在排序上。大量时间花在排序上。大量时间花在排序上。大量时间花在排序上。l对于给定的数值属性，概念分层定义了该属性的对于给定的数值属性，概念分层定义了该属性的对于给定的数值属性，概念分层定义了该属性的对于给定的数值属性，概念分层定义了该属性的一个离散化的值。一个离散化的值。一个离散化的值。一个离散化的值。l分箱分箱分箱分箱l直方图分析直方图分析直方图分析直方图分析.Copyright by Song ZhihuanCopyright by Song Zhihuan数值数据离散化数值数据离散化l聚类分析聚类分析聚类分析聚类分析l基于熵的离散化基于熵的离散化基于熵的离散化基于熵的离散化l通过自然划分分段通过自然划分分段通过自然划分分段通过自然划分分段 3-4-5 3-4-5规则规则规则规则如果一个区间最高有效位上包括如果一个区间最高有效位上包括如果一个区间最高有效位上包括如果一个区间最高有效位上包括3 6 9 3 6 9 个不同的值，划个不同的值，划个不同的值，划个不同的值，划分为分为分为分为3 3个等宽区间。个等宽区间。个等宽区间。个等宽区间。7 7个不同值，按个不同值，按个不同值，按个不同值，按2-3-32-3-3划分为划分为划分为划分为3 3个区个区个区个区间间间间最高位包含最高位包含最高位包含最高位包含2 2，4 4，8 8个不同值，划分为个不同值，划分为个不同值，划分为个不同值，划分为4 4个等宽区间个等宽区间个等宽区间个等宽区间最高位包含最高位包含最高位包含最高位包含1 1，5 5，1010个不同值，划分为个不同值，划分为个不同值，划分为个不同值，划分为5 5个等宽区间个等宽区间个等宽区间个等宽区间最高分层一般在第最高分层一般在第最高分层一般在第最高分层一般在第5 5个百分位到第个百分位到第个百分位到第个百分位到第9595个百分位上进行个百分位上进行个百分位上进行个百分位上进行.Copyright by Song ZhihuanCopyright by Song Zhihuan分类数据的概念分层生成分类数据的概念分层生成l分类数据是离散数据。一个分类属性可能有有限分类数据是离散数据。一个分类属性可能有有限分类数据是离散数据。一个分类属性可能有有限分类数据是离散数据。一个分类属性可能有有限个不同的值。个不同的值。个不同的值。个不同的值。l方法方法方法方法 由用户和专家在模式级显式的说明属性的部分序由用户和专家在模式级显式的说明属性的部分序由用户和专家在模式级显式的说明属性的部分序由用户和专家在模式级显式的说明属性的部分序通过显式的数据分组说明分层结构的一部分通过显式的数据分组说明分层结构的一部分通过显式的数据分组说明分层结构的一部分通过显式的数据分组说明分层结构的一部分说明属性集，但不说明他们的偏序说明属性集，但不说明他们的偏序说明属性集，但不说明他们的偏序说明属性集，但不说明他们的偏序只说明部分的属性集只说明部分的属性集只说明部分的属性集只说明部分的属性集.Copyright by Song ZhihuanCopyright by Song Zhihuan三、数据挖掘算法三、数据挖掘算法分类与预测分类与预测.Copyright by Song ZhihuanCopyright by Song Zhihuan分类分类 VS.预测预测l分类：分类：分类：分类：预测分类标号（或离散值）预测分类标号（或离散值）预测分类标号（或离散值）预测分类标号（或离散值）根据训练数据集和类标号属性，构建模型来分类现有数根据训练数据集和类标号属性，构建模型来分类现有数根据训练数据集和类标号属性，构建模型来分类现有数根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据据，并用来分类新数据据，并用来分类新数据据，并用来分类新数据l预测：预测：预测：预测：建立连续函数值模型，比如