第三讲数据挖掘技术讲义教材

《第三讲数据挖掘技术讲义教材》由会员分享，可在线阅读，更多相关《第三讲数据挖掘技术讲义教材（173页珍藏版）》请在金锄头文库上搜索。

1、于 金 霞计算机科学与技术学院信息管理与信息系统专业课程第三讲 数据挖掘技术主要内容主要内容 l 一、数据挖掘概述l 二、数据预处理l 三、数据挖掘算法分类与预测l 四、数据挖掘算法聚类l 五、数据挖掘算法关联分析l 六、序列模式挖掘l 七、数据挖掘软件l 八、数据挖掘应用一、数据挖掘概述一、数据挖掘概述数据挖掘与数据挖掘与KDDKDDl 知识发现（KD） 输出的是规则 l 数据挖掘（DM） 输出的是模型 l 共同点 两种方法输入的都是学习集（learning sets） 目的都是尽可能多的自动化数据挖掘过程 数据挖掘过程并不能完全自动化，只能半自动化 数据挖掘的社会需求数据挖掘的社会需求国民

2、经济和社会的信息化 社会信息化后，社会的运转是软件的运转社会信息化后，社会的运转是软件的运转 社会信息化后，社会的历史是数据的历史社会信息化后，社会的历史是数据的历史数据挖掘的社会需求数据挖掘的社会需求数据挖掘数据库越来越大有价值的知识可怕的数据数据挖掘的社会需求数据挖掘的社会需求数据爆炸，知识贫乏 苦恼: 淹没在数据中 ; 不能制定合适的决策! 数据知识知识决策决策n模式n趋势n事实n关系n模型n关联规则n序列n目标市场n资金分配n贸易选择n在哪儿做广告n销售的地理位置n金融n经济n政府nPOS.n人口统计n生命周期数据挖掘的发展数据挖掘的发展l1989 IJCAI会议： 数据库中的知识发现

3、讨论专题Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)l1991-1994 KDD讨论专题Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)l1995-1998 KDD国际会议 (KDD95-98)Journal of Data Mining and Knowledge Discovery (1997)l199

4、8 ACM SIGKDD, SIGKDD1999-2002 会议,以及SIGKDD Explorationsl数据挖掘方面更多的国际会议PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.数据挖掘技术数据挖掘技术l技术分类 预言（Predication）：用历史预测未来 描述（Description）：了解数据中潜在的规律l数据挖掘技术 关联分析 序列模式 分类（预言） 聚集 异常检测异常检测异常检测l 异常检测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。l 异常

5、探测应用 电信和信用卡欺骗 贷款审批 药物研究 气象预报 金融领域 客户分类 网络入侵检测 故障检测与诊断等 什么是异常（什么是异常（outlieroutlier）？）？l Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。l 聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。l 异常检测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。异常检测方法的分类异常检测方法的分类l 基于统计（statistical-based)的方法l 基于距离 (distance-

6、based)的方法l 基于偏差(deviation-based)的方法l 基于密度(density-based)的方法l 高维数据的异常探测数据挖掘系统的特征数据挖掘系统的特征数据的特征知识的特征算法的特征矿山（数据）挖掘工具（算法）金子（知识）数据的特征数据的特征大容量 POS数据（某个超市每天要处理高达2000万笔交易） 卫星图象（NASA的地球观测卫星以每小时50GB的速度发回数据） 互联网数据含噪音（不完全、不正确）异质数据（多种数据类型混合的数据源，来自互联网的数据是典型的例子）系统的特征系统的特征知识发现系统需要一个前处理过程 数据抽取 数据清洗 数据选择 数据转换知识发现系统是一

7、个自动/半自动过程知识发现系统要有很好的性能知识（模式）的特征知识（模式）的特征知识发现系统能够发现什么知识？计算学习理论COLT（Computational Learning Theory）以FOL为基础的以发现关系为目的的归纳逻辑程序设计现行的知识发现系统只能发现特定模式的知识规则分类关联知识表示：规则知识表示：规则 IF 条件 THEN 结论 条件和结论的粒度（抽象度）可以有多种 单值 区间 模糊值 规则可以有确信度 精确规则 概率规则知识表示：分类树知识表示：分类树分类条件1分类条件2分类条件3类1类2类3类4数据挖掘算法的特征数据挖掘算法的特征构成数据挖掘算法的三要素模式记述语言：反

8、映了算法可以发现什么样的知识模式评价：反映了什么样的模式可以称为知识模式探索：包括针对某一特定模式对参数空间的探索和对模式空间的探索数据挖掘的主要方法数据挖掘的主要方法分类（Classification）聚类(Clustering)相关规则(Association Rule)回归(Regression)其他数据挖掘系统数据挖掘系统代特征数据挖掘算法集成分布计算模型数据模型第一代数据挖掘作为一个独立的应用支持一个或者多个算法 独立的系统单个机器向量数据第二代和数据库以及数据仓库集成多个算法：能够挖掘一次不能放进内存的数据数据管理系统，包括数据库和数据仓库同质/局部区域的计算机群集有些系统支持对象

9、、文本、和连续的媒体数据第三代和预言模型系统集成 多个算法数据管理和预言模型系统intranet/extranet网络计算支持半结构化数据和web数据第四代和移动数据/各种计算数据联合 多个算法数据管理、预言模型、移动系统移动和各种计算设备普遍存在的计算模型数据挖掘系统数据挖掘系统l 第一代数据挖掘系统 支持一个或少数几个数据挖掘算法，这些算法设计用来挖掘向量数据（vector-valued data），这些数据模型在挖掘时候，一般一次性调进内存进行处理。许多这样的系统已经商业化。l 第二代数据挖掘系统 目前的研究，是改善第一代数据挖掘系统，开发第二代数据挖掘系统。第二代数据挖掘系统支持数据库

10、和数据仓库，和它们具有高性能的接口，具有高的可扩展性。例如，第二代系统能够挖掘大数据集、更复杂的数据集、以及高维数据。这一代系统通过支持数据挖掘模式（data mining schema）和数据挖掘查询语言（DMQL）增加系统的灵活性。 数据挖掘系统数据挖掘系统l 第三代数据挖掘系统 第三代的特征是能够挖掘Internet/Extranet的分布式和高度异质的数据，并且能够有效地和操作型系统集成。这一代数据挖掘系统关键的技术之一是提供对建立在异质系统上的多个预言模型以及管理这些预言模型的元数据提供第一级别（first class）的支持。 l 第四代数据挖掘系统 第四代数据挖掘系统能够挖掘嵌入

11、式系统、移动系统、和普遍存在（ubiquitous）计算设备产生的各种类型的数据 。二、数据预处理二、数据预处理为什么需要预处理为什么需要预处理l 数据 不完整 含观测噪声 不一致 包含其它不希望的成分l 数据清理通过填写空缺值，平滑噪声数据，识别删除孤立点，并解决不一致来清理数据。污染数据形成的原因污染数据形成的原因l 滥用缩写词l 数据输入错误l 数据中的内嵌控制信息l 不同的惯用语l 重复记录l 丢失值l 拼写变化l 不同的计量单位l 过时的编码l 含有各种噪声数据清理的重要性数据清理的重要性1. 污染数据的普遍存在，使得在大型数据库中维护数据的正确性和一致性成为一个及其困难的任务。2.

12、 垃圾进、垃圾出数据清理处理内容数据清理处理内容l 格式标准化l 异常数据清除l 错误纠正l 重复数据的清除数据规约数据规约l 数据集的压缩表示，但是能和原始数据集达到相同或基本相同的分析结果l 主要策略: 数据聚集 维规约 数据压缩 数值规约空缺值空缺值l 忽略元组l 人工填写空缺值l 使用固定值l 使用属性平均值l 使用最有可能值噪声数据噪声数据l 如何平滑数据，去掉噪声l 数据平滑技术 分箱 聚类 计算机和人工检查相结合 回归分箱分箱l 箱的深度：表示不同的箱里有相同个数的数据。l 箱的宽度：每个箱值的取值区间是个常数。l 平滑方法: 按箱平均值平滑 按箱中值平滑 按箱边界值平滑聚类聚类

13、l 每个簇中的数据用其中心值代替l 忽略孤立点l 先通过聚类等方法找出孤立点。这些孤立点可能包含有用的信息。l 人工再审查这些孤立点回归回归l 通过构造函数来符合数据变化的趋势，这样可以用一个变量预测另一个变量。 线性回归 多线性回归数据集成数据集成l 将多个数据源中的数据结合起来存放在一个一直得数据存贮中。l 实体识别 实体和模式的匹配l 冗余：某个属性可以由别的属性推出。相关分析相关性rA,B .rA,B0,正相关。A随B的值得增大而增大rA,B0,正相关。AB无关rA,B0,正相关。A随B的值得增大而减少l 重复 同一数据存储多次l 数据值冲突的检测和处理数据变换数据变换l 平滑l 聚集

14、l 数据概化l 规范化l 属性构造(特征构造)l 最小 最大规范化l 小数定标规范化l 属性构造 由给定的属性构造和添加新的属性，以帮助提高精度和对高维数据结构的理解规范化规范化数据立方体聚集数据立方体聚集l 寻找感兴趣的维度进行再聚集维规约维规约l 删除不相关的属性（维）来减少数据量。l 属性子集选择 找出最小属性集合，使得数据类的概率分布尽可能地接近使用所有属性的原分布 如何选取？贪心算法 逐步向前选择 逐步后向删除 向前选择和后向删除相结合 判定树归纳数据压缩数据压缩l 有损，无损l 小波变换 将数据向量D转换成为数值上不同的小波系数的向量D. 对D进行剪裁，保留小波系数最强的部分。l

15、l主要成分分析主要成分分析数值规约数值规约l 回归和对数线形模型 线形回归 对数线形模型l 直方图 等宽 等深 V-最优 maxDiff数值规约数值规约l 聚类 多维索引树 ： 对于给定的数据集合，索引树动态的划分多维空间。l 选样 简单选择n个样本，不放回 简单选择n个样本，放回 聚类选样 分层选样离散化和概念分层离散化和概念分层l 离散化技术用来减少给定连续属性的个数l 通常是递归的。l 大量时间花在排序上。l 对于给定的数值属性，概念分层定义了该属性的一个离散化的值。l 分箱l 直方图分析数值数据离散化数值数据离散化l 聚类分析l 基于熵的离散化l 通过自然划分分段 3-4-5规则如果一

16、个区间最高有效位上包括3 6 9 个不同的值，划分为3个等宽区间。 7个不同值，按2-3-3划分为3个区间最高位包含2，4，8个不同值，划分为4个等宽区间最高位包含1 ，5，10个不同值，划分为5个等宽区间最高分层一般在第5个百分位到第95个百分位上进行分类数据的概念分层生成分类数据的概念分层生成l 分类数据是离散数据。一个分类属性可能有有限个不同的值。l 方法 由用户和专家在模式级显式的说明属性的部分序 通过显式的数据分组说明分层结构的一部分 说明属性集，但不说明他们的偏序 只说明部分的属性集三、数据挖掘算法三、数据挖掘算法分类与预测分类与预测分类分类 VS. VS. 预测预测l 分类： 预测分类标号（或离散值） 根据训练数据集和类标号属性，构建模型来分类现有数据，并用来分类新数据l 预测： 建立连续函数值模型，比如预测空缺值l 典型应用 信誉证实 目标市场 医疗诊断 性能预测数据分类：两步过程数据分类：两步过程l 第一步，建立一个模型，描述预定数据类集和概念集 假定每个元组属于一个预定义的类，由一个类标号属性确定 基本概念 训练数据集：由为建立模型而被分析的数据元组形成 训练样本：