数据挖掘原理与算法教案

数据挖掘原理与算法教案讲授：王志明[e-mail]湖南农业大学理学院信息科学系第一章绪论教学目的：掌握数据挖掘的概念，背景，基本理论，基本应用，发展趋势教学重点难点：数据挖掘的概念，粗糙集方法教学课时：2教学过程：一、概念数据挖掘(Datamining)属一交叉学科，融合了数据库技术(Database)，人工智能(ArtificialIntelligence)，机器学习(MachineLearning)，统计学(Statistics)，知识工程(KnowledgeEngineering),面向对象方法(Object-OrientedMethod)，信息检索(InformationRetrieval)，高性能计算(High-PerformanceComputing)以及数据可视化（DataVisualization）等技术。联机事物处理（OnLineTransactionProcessing，OLTP）是在网络环境下的事务处理工作，以快速的响应和频繁的数据修改为特征，使用户利用数据库能够快速地处理具体的业务。知识：广义讲就是数据、信息的表现形式。人们常把概念、规则、模式、规律和约束等看成知识。数据挖掘：又称数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD),就是从大量数据中获取有效地、新颖的、潜在有用的、最终可理解的模式的非平凡过程。简单的说就是从大量数据中提取或挖掘知识。数据仓库是面向主题的、集成的、稳定的，不同时间的数据集合，用于支持经营管理中决策制定过程。二、数据挖掘产生与发展1）查询、统计、报表等简单传统的数据处理无法获取知识。这样促使数据挖掘技术的发展。利用数据仓库存储数据。2）数据挖掘技术产生的技术背景：（1）数据库、数据仓库、Internet等信息技术的发展；(2)计算机性能的提升；(3)统计学和人工智能等数据分析方法的应用。3）数据挖掘技术发展应用以及重点需要的研究的方面：（1）商业中的应用（2）与特定数据存储类型的适应问题（3）大型数据的选择与规格化问题（4）数据挖掘系统的构架与交互式挖掘技术（5）数据挖掘语言与系统的可视化问题（6）数据挖掘理论与算法研究三、数据挖掘的分类见书P11四、广义知识挖掘1、概念描述，包括特征性描述和区别性描述2、多维数据分析，如求和，计数，平均，最大值等3、多层次概念描述（1）模式分层；（2）集合分组分层；（3）操作导出层；（4）基于规则分层五、类知识挖掘1、分类：决策树、贝叶斯分类、神经网络、遗传算法与进化理论、类比学习、粗糙集、模糊集等2、聚类：基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法六、预测型知识挖掘1、趋势预测分析2、周期分析模式3、序列模式4、神经网络七、粗糙集方法粗糙集（RoughSet）是波兰数学家Z.Pawlak于1982年提出的。粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。它用上、下近似（upperapproximation,lowerapproximation）两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。1、等价粗糙集把客观世界抽象为一个信息系统，一个信息系统是一四元组S=(U，A，V，f)的定义为:U:是一个非空有限对象(元组)集合,U={x1x2…xn},其中xi为对象(元组)。A:是对象的属性集合,A={A1,A2,…,An},A常分为两个不相交的子集,即条件属性C和决策属性D,ACDV:是属性值的集合，V={V1,V2,…,Vn},Vi是Ai的值域。f：是信息函数，f:,(,)ijjUAVfxAV对于A中任意一个属性a,若两记录ie和je它们的属性值相同，称ie和je是对属性a的等价关系。属于同一等价关系的归位一个等价类。2、上近似和下近似1、设U是对象（事例）的集合U={x1x2…xn}；B是属性集A的子集，R(B)是U上的二元等价关系，1212(){(,)|(,)(,),}RBxxfxbfxbbB，若对任意集合O，B是属性集A的子集，则O的下近似定义为：(){|[]},RBBOxUxO这里()[]RBx表示x在R(B)上的等价类。上近似定义为：(){|[]},RBBOxUxO3、约简设有两属性集12,BB,1B是2B的真子集，如果1()RB2()RB，则称2B可归约为1B，若属性集B不可归约，则称B为U的一个约简或归约子。4、依赖度设有两属性集P和Q，则P对Q的属性依赖度定义为：#()()#ppposQrQU，其中*()()pxRQposQPX，PX表示集合X在属性集上的下近似。设BC，C是条件属性和D是决策属性,则属性重要度定义为：()()ASBCBrrDrD全集U可以划分为三个不相交的区域，即正域（Pos），负域（NEG）和边界（BND）：()()APosXAX()()ANEGXUAX()()()ABNDXAXAX从上面可见：()()()AAXAXBNDX用图说明正域、负域和边界，每一个小长方形表示一个等价类。5、粗糙集若()()AXAX，即()BNDX，即边界为空，称X为A的可定义集；否则X为A不可定义的，即()()AXAX，称X为A的Rough集（粗糙集）。6、规则的提取通过分析U中的两个划分{}iCE和{}jDY之间的关系，把C视为分类条件，D视为分类结论，我们可以得到下面的分类规则：1）当ijEYI，则有：ijr：()()ijDesEDesY()iDesE和()jDesY分别是等价集iE和等价集jY中的特征描述。2）当ijiEYEI时（iE完全被jY包含）即下近似，建立的规则ijr是确定的，规则的可信度cf=1.0。3）当ijiEYEI时（iE部分被jY包含）即上近似，建立的规则ijr是不确定的，规则的可信度为：cf=ijiEYE4)当ijEYI时（iE不被jY包含），iE和jY不能建立规则。7、举例(汽车数据)正域、负域和边界NEG（X）Pos（X）=BND（X）X正域负域边界()AXIDPowerTurboWeightIDPowerTurboWeight1highyesmed6mediumyeslight2lownolight7lownoheavy3mediumyeslight8highnoheavy4highnolight9highyesmed5highyesmed10lownoheavyU={1,2,3,4,5,6,7,8,9,10}A={power,turbo,weight}V={low,high,medium,yes,no,light,heavy,med}C={power,turbo},D={weight}按照C，则U分为：E1={1，5，9}，E2={2，7，10}，E3={3，6}，E4={4，8}按照D，则U可分为Y1={1,5,9},Y2={7,8,10},Y3={2,3,4,6}P28八、数据挖掘的应用1、CRM（客户关系管理）的应用2、体育竞技中的应用3、商业银行的应用4、电信中的应用5、科学探索中的应用6、信息安全中的应用第二章教学目的：掌握知识发现过程以及数据处理有关概念的概念，基本应用教学重点难点：知识发现技术要点、过程模型处理教学课时：3教学过程：一、知识发现过程1、大概过程（1）问题定义阶段（2）数据抽取阶段目标数据（TargetData），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。（3）数据挖掘首先要确定挖掘的任务或目的，如数据分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。实施数据挖掘算法，获取有用的模式（4）知识评估阶段获取的模式经过评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求。把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if...then…”规则。2、数据清洗与预处理目标数据（TargetData），是根据用户的需要从原始数据库中选取的一组数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。数据转换的主要目的是完成数据类型转换。尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。二、数据库中的知识发现处理过程模型1、阶梯处理过程模型2、螺旋处理过程模型G.H.John提出定义问题抽取数据清洗数据数据工程算法工程运行挖掘算法分析结果3、以用户为中心的处理模型Brachman和Anand从用户角度对KDD处理过程进行了分析。任务发现数据发现数据清洗数据源数据数据集成目标数据预处理后数据转换数据模式知识数据选择预处理数据挖掘数据转换结果表达和解释数据准备数据挖掘结果评价KDD过程模型开发数据分析输出结果生成4、联机KDD模型传统数据挖掘的缺陷：（1）过分强调自动化，忽视交互性，导致用户对数据挖掘过程参与过程困难；（2）数据挖掘算法对用户是一个“黑盒”，只有在算法挖掘结束后，用户才能评价发现的模式，若对模式不满意，则重复挖掘过程，消耗资源；（3）传统数据挖掘过程只能一次对一个数据集进行挖掘。OLAM（OnLineAnalyticalMining）联机分析挖掘由OLAP发展而来。被分为几个层次：（1）L0层：数据集，包含了相关的数据库和数据仓库。（2）L1层：形成支持OLAP和OLDM的多维数据集，主要由元数据集和数据立方体。（3）L2层：是OLAP和OLDM的应用层，包含相互关联并协同工作的OLAM引擎和OLAP引擎。L2接受数据挖掘请求，通过访问多维数据和元数据，完成数据挖掘和分析工作。（4）L3层：是一个用户接口层，它主要承担用户请求的理解与挖掘结果的解释和表达等。三、知识发现软件和工具的发展1、独立的知识发现软件2、横向的知识发现工具集(P52)DBMiner,Quest,IBMIntelligentMiner,Darwin,ReMind3、纵向的知识发现解决方案如证券系统的趋势预测；银行和电信行业的欺诈行为检测；基因分析系统中的DNA识别等4、KDD系统介绍Quest：QUEST是IBM公司Almaden研究中心开发的一个多任务数据挖掘系统，目的是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下特点：提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式发现、时间序列聚类、决策树分类、递增式主动开采等。各种开采算法具有近似线性（O(n)）计算复杂度，可适用于任意大小的数据库。算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。为各种发现功能设计了相应的并行算法。DBMiner：DBMiner是加拿大SimonFraser（加拿大名校-西蒙菲沙大学）大学开发的一个多任务数据挖掘系统，它的前身是DBLearn。该系统设计的目的是把关系数据库和数据开采集成在一起，以面向属性的多级概念为基础发现各种知识。DBMiner系统具有如下特色：能完成多种知识的发现：泛化规则、特性规则、关联规则、分类规则、演化知识、偏离知识等。综合了多种数据开采技术：面向属性的归纳、统计分析、逐级深化发现多级规则、元规则引导发现等方法。提出了一种交互式的类SQL语言——数据开采查询语言DMQL。能与关系数据库平滑集成。实现了基于客户/服务器体系结构的Unix和PC（Windows/NT）版本的系统。四、知识发现项目的过程化管理（略）五、数据挖掘语言介绍第三章关联规则挖掘理论和算法教学目的：掌握关联规则挖掘的概念，背景知识，了解常见关联规则挖掘的数据挖掘算法教学重点难点：关联规则挖掘常见算法教学课时：6教学过程：关联规则挖掘最早由Agrawal于1993年提出，目的是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式。一、概念：事务数据库：设12{,,..