数据挖掘原理与算法教案

数据挖掘原理与算法教案讲授：王志明**************湖南农业大学理学院信息科学系第一章绪论教学目的：掌握数据挖掘的概念，背景，基本理论，基本应用，发展趋势教学重点难点：数据挖掘的概念，粗糙集方法教学课时：2教学过程：一、概念数据挖掘(Data mining)属一交叉学科，融合了数据库技术(Database)，人工智能(Artificial Intelligence)，机器学习(Machine Learning)，统计学(Statistics)，知识工程(Knowledge Engineering),面向对象方法(Object-Oriented Method)，信息检索(Information Retrieval)，高性能计算(High-Performance Computing)以及数据可视化（Data Visualization）等技术。

联机事物处理（On Line Transaction Processing，OLTP）是在网络环境下的事务处理工作，以快速的响应和频繁的数据修改为特征，使用户利用数据库能够快速地处理具体的业务。

知识：广义讲就是数据、信息的表现形式。

人们常把概念、规则、模式、规律和约束等看成知识。

数据挖掘：又称数据库中的知识发现(Knowledge Discovery in Database, 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、神经网络 七、粗糙集方法粗糙集（Rough Set ）是波兰数学家Z.Pawlak 于1982年提出的。

粗糙集以等价关系（不可分辨关系）为基础，用于分类问题。

它用上、下近似（upper approximation, lower approximation ）两个集合来逼近任意一个集合，该集合的边界线区域被定义为上近似集和下近似集之差集。

1、等价粗糙集把客观世界抽象为一个信息系统，一个信息系统是一四元组S=(U ，A ，V ，f )的定义为:U:是一个非空有限对象(元组)集合,U={x1 x2 …xn},其中xi 为对象(元组)。

A:是对象的属性集合,A={A1,A2,…,An},A 常分为两个不相交的子集,即条件属性C 和决策属性D, A C D =⋃V:是属性值的集合， V={V1,V2,…,Vn},Vi 是Ai 的值域。

f ：是信息函数，f:,(,)i j j U A V f x A V ⨯→∈对于A 中任意一个属性a,若两记录i e 和j e 它们的属性值相同，称i e 和je 是对属性a 的等价关系。

属于同一等价关系的归位一个等价类。

2、上近似和下近似1、设U 是对象（事例）的集合U={x1 x2 …xn}；B 是属性集A 的子集，R(B)是U 上的二元等价关系，1212(){(,)|(,)(,),}R B x x f x b f x b b B ==∈，若对任意集合O ，B 是属性集A 的子集，则O 的下近似定义为： (){|[]},R B BO x U x O =∈⊂这里()[]R B x 表示x 在R(B)上的等价类。

上近似定义为：(){|[]},R B BO x U x O =∈≠∅3、约简设有两属性集12,B B ,1B 是2B 的真子集，如果1()R B =2()R B ，则称2B 可归约为1B ，若属性集B 不可归约，则称B 为U 的一个约简或归约子。

4、依赖度设有两属性集P 和Q ，则P 对Q 的属性依赖度定义为：#()()#p p pos Q r Q U=，其中*()()p x R Q pos Q PX ∈=，PX 表示集合X 在属性集上的下近似。

设B C ⊆，C 是条件属性和D 是决策属性,则属性重要度定义为：()()AS B C B r r D r D -=- 全集U 可以划分为三个不相交的区域，即正域（Pos ），负域（NEG ）和边界（BND ）：()()A Pos X A X = ()()A NEG X U A X =- ()()()A BND X A X A X =-从上面可见：()()()A A X A X BND X =+用图说明正域、负域和边界，每一个小长方形表示一个等价类。

5、粗糙集若()()A X A X =，即()BND X =Φ，即边界为空，称X 为A 的可定义集；否则X 为A 不可定义的，即()()A X A X ≠，称X 为A 的Rough 集（粗糙集）。

6、规则的提取通过分析U 中的两个划分{}i C E =和{}j D Y =之间的关系，把C 视为分类条件，D 视为分类结论，我们可以得到下面的分类规则：1）当≠∅i j E Y ，则有：ij r ：()()i j Des E Des Y →()i Des E 和()j Des Y 分别是等价集i E 和等价集j Y 中的特征描述。

2）当=i j i E Y E 时（i E 完全被j Y 包含）即下近似，建立的规则ij r 是确定的，规则的可信度cf=1.0。

3）当≠i j i E Y E 时（i E 部分被j Y 包含）即上近似，建立的规则ij r 是不确定的，规则的可信度为：cf=i j iE Y E4)当=∅i j E Y 时（i E 不被j Y 包含），i E 和j Y 不能建立规则。

7、举例(汽车数据)（X ）（X ）=（X ） X()A X -U={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）数据抽取阶段目标数据（Target Data），是根据用户的需要从原始数据库中选取的一组数据。

数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。

数据转换的主要目的是完成数据类型转换。

尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。

（3）数据挖掘首先要确定挖掘的任务或目的，如数据分类、聚类、关联规则发现或序列模式发现等。

确定了挖掘任务后，就要决定使用什么样的挖掘算法。

实施数据挖掘算法，获取有用的模式（4）知识评估阶段获取的模式经过评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求。

把结果转换为用户易懂的另一种表示，如把分类决策树转换为“if ...then…”规则。

2、数据清洗与预处理目标数据（Target Data），是根据用户的需要从原始数据库中选取的一组数据。

数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录等。

数据转换的主要目的是完成数据类型转换。

尽量消减数据维数或降维，以减少数据挖掘时要考虑的属性个数。

二、数据库中的知识发现处理过程模型1、阶梯处理过程模型2、螺旋处理过程模型 G . H. John 提出定义问题 抽取数据 清洗数据 数据工程 算法工程 运行挖掘算法 分析结果3、以用户为中心的处理模型Brachman 和 Anand 从用户角度对KDD 处理过程进行了分析。

任务发现 数据发现 数据清洗结果评价KDD 过程模型开发数据分析输出结果生成4、联机KDD模型传统数据挖掘的缺陷：（1）过分强调自动化，忽视交互性，导致用户对数据挖掘过程参与过程困难；（2）数据挖掘算法对用户是一个“黑盒”，只有在算法挖掘结束后，用户才能评价发现的模式，若对模式不满意，则重复挖掘过程，消耗资源；（3）传统数据挖掘过程只能一次对一个数据集进行挖掘。

OLAM（On Line Analytical Mining）联机分析挖掘由OLAP发展而来。

被分为几个层次：（1）L0层：数据集，包含了相关的数据库和数据仓库。

（2）L1层：形成支持OLAP和OLDM的多维数据集，主要由元数据集和数据立方体。

（3）L2层：是OLAP和OLDM的应用层，包含相互关联并协同工作的OLAM引擎和OLAP引擎。

L2接受数据挖掘请求，通过访问多维数据和元数据，完成数据挖掘和分析工作。

（4）L3层：是一个用户接口层，它主要承担用户请求的理解与挖掘结果的解释和表达等。

三、知识发现软件和工具的发展1、独立的知识发现软件2、横向的知识发现工具集(P52)DBMiner, Quest, IBM Intelligent Miner, Darwin, ReMind3、纵向的知识发现解决方案如证券系统的趋势预测；银行和电信行业的欺诈行为检测；基因分析系统中的DNA识别等4、KDD系统介绍Quest：QUEST是IBM公司Almaden研究中心开发的一个多任务数据挖掘系统，目的是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。