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