数据挖掘的概念与技术的知识

1、数 据 挖 掘概念与技术数据库与信息系统研究室Tel: Email: Cell Phone: 引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容大批成熟的业务信息系统投入运行信息系统多年运行，积累了海量的数据各类信息系统大多属于面向事务处理的OLTP系统数据是一种宝贵的资源，但没有充分发挥作用企业信息化发展现状我在数据中获取知识（有益的模式）发展趋势数据集中化业务综合化管理“扁平化”决策科学化特点以客户为中心以服务求发展企业信息化发展趋势数据处理的发展趋势（需求与产品）Data MiningDatabase

2、TechnologyStatisticsOtherDisciplinesInformationScienceMachineLearningVisualization数据挖掘多学科交叉的领域引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容什么是数据挖掘？数据挖掘是从大量的数据中抽取出潜在的、不为人知的有用信息、模式和趋势Jiawei Han(University of Illinois at Urbana-Champaign )数据挖掘不同的术语和定义：data mining, knowledge disco

3、very, pattern discovery数据挖掘知识发现过程（KDD）的核心数据清理：消除噪音或不一致数据数据集成：多种数据源可以组合在一起 数据选择：从数据库中提取与分析任务相关的数据数据变换：数据变换或统一成适合挖掘的形式 数据挖掘：基本步骤，使用智能方法提取数据模式模式评估：根据某种兴趣度度量，识别提供知识的真正有用的模式知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识数据挖掘系统分类根据挖掘的数据类型分类根据挖掘的知识类型分类根据所用的挖掘技术分类根据系统的应用领域分类关系数据库面向对象数据库文本数据多媒体数据异构数据WWW数据数据挖掘分类数据类型Data Warehou

4、se数据挖掘分类知识类型关联挖掘序列模式挖掘聚类挖掘分类挖掘孤立点挖掘概化挖掘预测挖掘数据库技术机器学习技术统计技术神经网络技术可视化技术数据挖掘分类挖掘技术引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容关联挖掘序列模式挖掘分类挖掘聚类挖掘孤立点挖掘数据挖掘原理与方法关联（Association）反映一个事件和其他事件之间依赖或关联的知识如果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测可以用关联规则的形式表示规则形式： “Body Head support, confide

5、nce”.举例： contains(T, “computer”) contains(T, “software”) support = 1%, confidence = 75%age(X, “20.29”) income(X, “20.29K”) buys(X, “PC”) 2%, 60%应用：业务相关性分析、交叉销售、产品目录设计等关联规则（一）X Y满足X中条件的数据库元组也满足Y中条件规则兴趣度度量支持度置信度强规则同时满足最小支持度阈值和最小置信度阈值的规则给定: (1)交易数据库 (2)每笔交易是：一个项目列表 (消费者一次购买活动中购买的商品)查找: 所有描述一个项目集合与其他项目集

6、合相关性的规则E.g., 98% of people who purchase tires and auto accessories also get automotive services done应用* 护理用品 (商店应该怎样提高护理用品的销售？)家用电器 * (其他商品的库存有什么影响?)在产品直销中使用附加邮寄关联规则（二）规则度量：支持度与置信度查找所有的规则 X & Y Z 具有最小支持度和可信度支持度 s, 一次交易中包含X 、 Y 、 Z的可能性置信度 c, 包含X 、 Y的交易中也包含Z的条件概率设最小支持度为50%, 最小置信度为 50%, 则可得到A C (50%, 6

7、6.6%)C A (50%, 100%)买尿布的客户二者都买的客户买啤酒的客户关联规则挖掘方法对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%最小支持度50%最小置信度 50%找出所有的频繁项集由频繁项集产生强关联规则关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如, 如果AB 是频繁集，则 A B 也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则Apriori算法连接: 用 Lk-1自连接得到Ck修剪: 一个k-项集

8、，如果他的一个k-1项集（他的子集 ）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck: Candidate itemset of size kLk : frequent itemset of size kL1 = frequent items;for (k = 1; Lk !=; k+) do begin Ck+1 = candidates generated from Lk; for each transaction t in database do increment the count of all candidates in Ck+1 that are contained in t

9、 Lk+1 = candidates in Ck+1 with min_support endreturn k Lk;Apriori算法 例子数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 D（最小支持度为2）如何生成候选集假定 Lk-1 中的项按顺序排列第一步: 自连接 Lk-1 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 6THEN tenured =

10、yes 模型分类过程 : 使用模型模型测试集未知数据(Jeff, Professor, 4)Tenured?一 个训 练 集一棵关于“买计算机”的决策树实例age?overcaststudent?credit rating?noyesfairexcellent40yes31.40nonoyesyes根内部节点叶子分枝分类结果分类比例非空间分类属性类标号决策树空间分类属性分类挖掘实例全国县经济状况空间分类关联挖掘序列模式挖掘分类挖掘聚类挖掘孤立点挖掘数据挖掘原理与方法聚类（Clustering）最大化类内的相似性、最小化类间相似性的原则进行聚类或者分组，使得在一个类中的对象具有很高的相似性，而与

11、其他类中的对象很不相似簇（Cluster）:一个数据对象的集合在同一个类中，对象之间具有相似性不同类的对象之间是相异的聚类分析：把一个给定的数据对象集合分成不同的簇特点：一种无监督分类法，没有预先指定的类别有监督和无监督学习有监督学习 (分类)训练集是带有类标签的新的数据是基于训练集进行分类的无监督学习 (聚集)训练集是没有类标签的提供一组属性，然后寻找出训练集中存在类别或者聚集应用聚类分析的例子客户划分与市场销售: 帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用: 在一个陆地观察数据库中标识那些土地使用相似的地区；保险: 对购买了汽车保险的客户，标识那

12、些有较高平均赔偿成本的客户；城市规划: 根据类型、价格、地理位置等来划分不同类型的住宅；什么是一个好的聚类方法?一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：高的簇内相似性低的簇间相似性 聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；聚类实现的一个方法：划分划分方法: 将一个包含n个数据对象的数据库组织成k个划分（k=n），其中每个划分代表一个簇（Cluster）。给定一个k，要构造出k个簇，并满足采用的划分准则：全局最优:尽可能的列举所有的划分；启发式方法: k-平均和k-中心点算法

13、k-平均 (MacQueen67):由簇的中心来代表簇；k-中心点或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每个簇由簇中的某个数据对象来代表。 K-平均算法012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the clus

14、ter meansreassignreassign聚类数据挖掘实例（1） 关联挖掘序列模式挖掘分类挖掘聚类挖掘孤立点挖掘数据挖掘原理与方法数据库中可能包含一些数据对象，它们与数据的一般行为或模型很不一致，这些对象称作孤立点孤立点包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、量值随时间的变化等孤立点（Outlier）挖掘引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容数据挖掘标准化简介模型级别XML PMML应用级别XML（JAVA） SOAP数据挖掘与标准化进程CRI

15、SPDM过程标准化（CRoss-Industry Standard Process for Data Mining）XML与数据预处理相结合SOAP（Simple Object Access Protocol ）数据库与系统互操作的标准PMML预言模型交换标准PMML:预言模型标记语言PMML 标准的由来什么是PMML?PMML的主要目的PMML的内容PMML 标准的由来PMML 最初由NCDM开发 National Center for Data Mining (NCDM) at the University of Illinois at Chicago (UIC) Robert Gross

16、man 1997Grossman,etc: The Management and Mining of Multiple Predictive Models Using the Predictive Modeling Markup Language (PMML), 1999DMG（Data Mining Group）修正和扩充DMG最初成员包括：Angoss, Magnify, NCDM,SPSSPMML1.0在1999年7月由DMG组织发布DMG目的是开发数据挖掘标准目前由9个成员组成：Angoss，IBM，Magnify，NCR，Oracle，SPSS，NCDM，Xchange,MINEit

17、当前PMML最新版本是2.0什么是PMML?（一）定义PMML称为预言模型标记语言（Predictive Model Markup Language），利用XML描述和存储数据挖掘模型， 是一个已经被W3C所接受的标准。PMML2.0Tree ModelNaive BayesGeneral RegressionRegression ModelSequencesGeneral StructureAsscocation Rules什么是PMML?（二）PMML的主要目的允许应用程序和联机分析处理（OLAP）工具能从数据挖掘系统获得模型，而不用独自开发数据挖掘模块 能够收集使用大量潜在的模型，并且统

18、一管理各种模型的集合 解决目前各数据挖掘系统之间封闭性的问题可以在其它应用系统中间嵌入数据挖掘模型，解决孤立的知识发现问题 引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容数据库、数据仓库、或其它信息库：数据挖掘的数据源，需要在其上进行数据清理和集成数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务器负责提取相关数据知识库：存储面向领域的知识，用于指导搜索，或评估结果模式的兴趣度数据挖掘引擎：数据挖掘系统核心部分，由一组功能模块组成，用于特征、关联、分类、聚类分析、演变和偏差分析等数据挖掘

19、系统体系结构模式评估模块：使用兴趣度度量，与挖掘模块交互，以便将搜索聚焦在有趣的模式上可能使用兴趣度阈值过滤发现的模式模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现对于有效的数据挖掘，建议尽可能地将模式评估推进到挖掘过程之中，以便将搜索限制在有兴趣的模式上数据挖掘系统体系结构（续一）图形用户界面：该模块在用户和挖掘系统之间通讯允许用户与系统交互，指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结果进行探索式数据挖掘。允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘的模式，以不同的形式对模式可视化数据挖掘系统体系结构（续二）引言数据挖掘的概念与分类

20、体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容数据挖掘系统设计中的若干问题挖掘方法与用户交互问题如何设计覆盖广谱的数据分析和知识发现任务多个抽象层的交互知识挖掘如何纳入领域知识数据挖掘系统的性能问题算法的有效性和可伸缩性并行、分布和增量挖掘算法与体系挖掘方法与用户交互问题不同的用户可能对不同类型的知识感兴趣数据挖掘系统应当覆盖广谱的数据分析和知识发现任务，包括数据特征、区分、关联、聚类、趋势、偏差分析和类似性分析等这些任务可能以不同的方式使用相同的数据库避免开发单一的挖掘应用，需设计良好的系统可扩展性多个抽象层的交互知识挖掘问题

21、由于很难准确地知道能够在数据库中发现什么，数据挖掘过程应当是交互的对于包含大量数据的数据库，应当使用适当的选样技术，进行交互式数据探查交互式挖掘允许用户聚焦搜索模式，根据返回的结果提出和精炼数据挖掘请求特殊地，类似于立方体上的OLAP操作，应当通过交互地在数据空间和知识空间下钻、上卷和转轴，挖掘知识。用这种方法，用户可以与数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发现模式纳入领域知识的问题结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过程，并使得发现的模式以简洁的形式，在不同的抽象层表示关于数据库的领域知识，如完整性限制和演绎规则，可以帮助聚焦和加快数据挖掘过程，或

22、评估发现的模式的兴趣度挖掘结果的表示问题发现的知识应当用高级语言、可视化表示形式、或其它表示形式表示，使得知识易于理解，能够直接被人使用如果数据挖掘系统是交互的，这一点尤为重要要求系统采用有表达能力的知识表示技术，如树、表、图、图表、交叉表、矩阵或曲线处理噪音和不完全数据问题存放在数据库中数据可能反映噪音、例外情况、或不完全的数据对象这些对象可能搞乱分析过程，导致数据与所构造的知识模型过分适应其结果是，所发现的模式的精确性可能很差。需要处理数据噪音的数据清理方法和数据分析方法，以及发现和分析例外情况的孤立点挖掘方法模式评估兴趣度问题数据挖掘系统可能发现数以千计的模式对于给定的用户，许多模式不是

23、有益的，它们表示平凡知识或缺乏新颖性使用兴趣度度量，指导发现过程和压缩搜索空间，是有效筛选有益模式的方法算法的有效性和可伸缩性问题为了有效地从数据库中大量数据提取信息，数据挖掘算法必须是有效的和可伸缩的对于大型数据库，数据挖掘算法的运行时间必须是可预计的和可接受的从数据库角度，有效性和可伸缩性是数据挖掘系统实现的关键问题上面讨论的挖掘技术和用户交互的大多数问题，也必须考虑有效性和可伸缩性引言数据挖掘的概念与分类体系数据挖掘的原理与方法数据挖掘的相关国际标准数据挖掘系统结构数据挖掘系统设计中的若干问题数据挖掘新技术主要内容数据挖掘新技术数据流挖掘技术基于数据立方体的挖掘时空数据挖掘技术移动对象挖

24、掘技术Web挖掘技术数据流问题的提出电信领域：电话呼叫记录分析、网络管理数据分析金融领域：信用卡交易分析、证券交易分析网络监测和流量控制Web日志与点击流分析能源供给部门的能源供给分析天气预报、地震预测传感网络监控 数据流的定义与特点数据流：以顺序(ordered)、快速、随时间变化、可能无法预测并且数量巨大的流的形式连续到达的数据序列： 特点大量、连续到达的数据，可能无限快速变化，需要快速、实时响应单次线性扫描算法，随机访问代价太高只能存储数据的汇总或提纲（synopsis）低层次、多维数据，需要多层次、多维处理数据流研究中的主要问题数据流查询技术当前焦点，主要是连续查询（continuou

25、s query）查询语言、查询计划、近似查询回答技术等 数据流分析技术传统的统计分析，已比较成熟结合数据仓库与OLAP技术的多维多层次分析数据流挖掘数据流管理系统查询处理、资源管理、存储实现等DBMS与DSMS的比较DBMS DSMS 持久关系 临时数据流 一次查询（one-time query） 连续查询（continuous query） 随机访问 顺序访问（sequential access） “极大的”（unbounded）磁盘存储 有限的（bounded）主存 仅是当前状态事务 历史数据是重要的 没有实时服务 实时服务需求 相当低的更新率 可能多GB的到达率 任何粒度层次的数据 精粒

26、度层次的数据 采取精确数据形式 数据是不精确的 准确的查询回答 近似回答 通过查询处理器、物理数据库设计决定访问计划 不可预测的、易变的数据到达情况和特征 数据流处理的挑战多个、连续、快速、时变、有序的数据流主存计算查询经常是连续的数据到来时的连续估计随时间更新的查询结果查询经常是复杂的超越了“一次一成员”（element-at-a-time）的处理方式超越了“一次个流”（stream-at-a-time）的处理方式超越了关系查询（科学数据库、数据挖掘、OLAP）多层次/多维处理和数据挖掘绝大多数流数据是相当低层的、多维的数据挖掘新技术数据流挖掘技术基于数据立方体的挖掘时空数据挖掘技术移动对象

27、挖掘技术Web挖掘技术根据用户的交互，系统自动完成用户的OLAP分析需求根据用户的交互，系统自动调整挖掘角度和策略基于数据立方体的挖掘用户期望什么？如何使分析更简单、更高效？DSS的分析工具OLAPDataMining既有用户的参与又有系统的自动发现两者的无缝联接与融合提供功能更强、操作更方便的分析分析更简单更高效假定驱动与发现驱动假定驱动的探查(hypothesis-driven exploration)用户通过使用下钻、上卷、切片、切块等OLAP操作，检索方中感兴趣的模式尽管这些工具可以用于帮助用户探查数据，但这一过程不是自动的用户根据他的直观和假定，试图去识别数据中的例外和异常缺点：搜索空间非常大，容易忽略有益的模式发现驱动的探查(discovery-driven exploration)将挖掘引入立方体集成的OLAM和OLAP结构数据挖掘新技术数据流挖掘技术基于数据立方体的挖掘时空数据挖掘技术移动对象挖掘技术Web挖掘技术时空数据挖掘时空数据挖掘是一种非平凡的从大型时空数据库中进行隐