数据挖掘算法介绍综述课件-2.ppt

1、数据挖掘算法介绍数据挖掘算法介绍 综述综述2022年8月12日星期五2改变未来世界的十大新兴技术改变未来世界的十大新兴技术nTechnology Review（麻省理工学院（麻省理工学院2002年年1月出刊）月出刊）机器与人脑的接口机器与人脑的接口塑胶晶体管塑胶晶体管数据挖掘（数据挖掘（Data Mining）数字权利管理数字权利管理生物测定学（生物测定学（Biometrics）语言识别处理语言识别处理微光学技术（微光学技术（Microphotonics）解开程序代码（解开程序代码（Untangling Code）机器人设计机器人设计微应用流体学（微应用流体学（Microfluidics）20

2、22年8月12日星期五3什么是数据挖掘？什么是数据挖掘？DataInformationKnowledgeWisdomn存在太多数据挖掘的定义，但基本上有这样一种描述存在太多数据挖掘的定义，但基本上有这样一种描述结构结构To find/discover/extract /dredge/harvest、Interesting/novel/useful/implicit/actable/meaningful、Information/knowledge/patterns/trends/rules/anomalies、In massive data/large data set/large databa

3、se/data warehouse、Data+contextInformation+rulesKnowledge+experience2022年8月12日星期五4为什么会出现数据挖掘？为什么会出现数据挖掘？n数据爆炸性增长是数据挖掘技术应运而生的根本原因。数据爆炸性增长是数据挖掘技术应运而生的根本原因。只见树木，不见森林（只见树木，不见森林（Drowning in data but starving for information）计算复杂度计算复杂度数据管理问题数据管理问题数据类型的多样性数据类型的多样性处理大容量数据是数据挖掘技术区别于其他数据分析方法的唯一标志吗？2022年8月12日星期

4、五5其他数据分析方法：统计学其他数据分析方法：统计学n从处理数据的角度看、从处理数据的角度看、数据规模不同数据规模不同数据来源不同：观测数据（数据来源不同：观测数据（Secondary Analysis）VS 试验数据（试验数据（Primary Analysis）数据类型不同（结构化数据、半结构化数据、非结构化数据）数据类型不同（结构化数据、半结构化数据、非结构化数据）n从分析思想的角度看从分析思想的角度看更关注实证性分析（更关注实证性分析（Empirical Analysis）而非探索性分析（）而非探索性分析（Exploratory Analysis）更关注模型（更关注模型（Model）而非

5、算法（）而非算法（Algorithm）n但二者具有相当密切的联系但二者具有相当密切的联系从数据分析的角度，统计学现在是且仍将是数据挖掘最重要的技术支撑和思想源泉从数据分析的角度，统计学现在是且仍将是数据挖掘最重要的技术支撑和思想源泉更加深入的渗透和交叉（如探索性数据分析，更加深入的渗透和交叉（如探索性数据分析，EDA）数据挖掘是数据驱动的探索性分析!2022年8月12日星期五6其他数据分析方法：商业智能其他数据分析方法：商业智能nE.F.Codd的数据分析模型的数据分析模型绝对模型（绝对模型（Categorical Model）：依据预定义路径寻找原因，如查）：依据预定义路径寻找原因，如查询询

6、解释模型（解释模型（Exegetical Model）：依据多层次路径寻找原因，如多维）：依据多层次路径寻找原因，如多维分析分析思考模型（思考模型（Contemplative Model）：参数化路径，如场景分析）：参数化路径，如场景分析公式模型（公式模型（Formulaic Model）：模型化路径，如数据挖掘）：模型化路径，如数据挖掘ReportingAd Hoc QueriesPredictive ModelingWhat happened?Why did it happen?What will happen?ROI应用复杂性应用复杂性Stage 3Stage 2Stage 1Human

7、 DiscoveryMachine-assisted Discovery现象 模型 误差数据挖掘寻找的是模型!2022年8月12日星期五7数据挖掘数据挖掘 KDD DM2022年8月12日星期五8KDDKDD:knowledge discovery in database数据数据建模建模验证验证应用应用2022年8月12日星期五9DMDM:datamingKDD的一个阶段KDD与DM等同2022年8月12日星期五10DM is like setting up a restaurant kitchen.Starting a restaurantkitchenData MiningFood/Inf

8、oCooks/TeamKitchen/DWHData Mining2022年8月12日星期五11数据挖掘与其他学科的关系数据挖掘与其他学科的关系Data MiningDatabase TechnologyStatisticsOtherDisciplinesInformationScienceMachineLearning(AI)Visualization2022年8月12日星期五12数据挖掘与数据挖掘与OLAPlOLAP（on-line analytical processing）:l只能限制于少量的维度和数据类型只能限制于少量的维度和数据类型l用户控制的流程用户控制的流程l假设假设验证验证结

9、论结论lDM：l没有明确假设的前提下去挖掘信息、发现知识没有明确假设的前提下去挖掘信息、发现知识具具 有未知、有效、可实用三个特征有未知、有效、可实用三个特征 l能自动的发现隐藏在数据中的规律能自动的发现隐藏在数据中的规律l可以发现比可以发现比OLAP更复杂而细致的信息更复杂而细致的信息l未知未知归纳归纳结论结论l联系：联系：lOLAPDMlOLAM2022年8月12日星期五13数据挖掘与统计学数据挖掘与统计学l数据挖掘：数据挖掘：l数据挖掘利用了统计数据挖掘利用了统计、人工智能人工智能、数据库等、数据库等技术，技术，把这些高深复杂的技术封装起来，使人们不用自己把这些高深复杂的技术封装起来，使

10、人们不用自己掌握这些技术也能完成同样的功能，并且更专注于掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问题自己所要解决的问题 ；l不仅仅是统计分析不仅仅是统计分析；l统计分析：统计分析：l统计分析技术都基于完善的数学理论和高超的技巧，统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求预测的准确度还是令人满意的，但对使用者的要求很高很高 l联系联系l统计分析方法学的延伸和扩展统计分析方法学的延伸和扩展 l很多的挖掘算法来源于统计学很多的挖掘算法来源于统计学2022年8月12日星期五14前景前景l预言：预言：l著名的咨询公司著名的咨询公司 Gar

11、tner Group在（在（2000年）一次高级年）一次高级技术调查将数据挖掘和人工智能列为技术调查将数据挖掘和人工智能列为“未来三到五年内未来三到五年内将对工业产生深远影响的五大关键技术将对工业产生深远影响的五大关键技术”之首，并且还之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位十大新兴技术前两位l国外现状：国外现状：l成熟、成熟、l产品：产品：SAS、CLEMENTINE、UNICA、各大数据库各大数据库l国内现状：国内现状：l起步起步l产品：大部分是实验室产品产品：大部分是实验室产品2022年8月12日星期五

12、15数据挖掘分类数据挖掘分类l挖掘对象挖掘对象基于数据库的挖掘基于数据库的挖掘基于基于web的挖掘的挖掘基于文本的挖掘基于文本的挖掘其他：音频、视频等多媒体数据库其他：音频、视频等多媒体数据库2022年8月12日星期五16数据挖掘分类数据挖掘分类l应用应用响应模型响应模型交叉销售交叉销售价值评估价值评估客户分群客户分群2022年8月12日星期五17数据挖掘分类数据挖掘分类l挖掘模式挖掘模式l预测型预测型(Predictive)Predictive)l描述型描述型(Descriptive)Descriptive)l实际作用可分为以下几种模式：实际作用可分为以下几种模式：分类：对没有分类的数据进行

13、分类；分类：对没有分类的数据进行分类；预测：用历史来预测未来；预测：用历史来预测未来；关联分析：关联规则；关联分析：关联规则；聚类：物以类聚；聚类：物以类聚；序列模式：序列模式：在多个数据序列中发现共同的行为模式在多个数据序列中发现共同的行为模式;描述和可视化：数据挖掘的结果的表示形式描述和可视化：数据挖掘的结果的表示形式;偏差分析：偏差分析：从数据分析中发现异常情况。从数据分析中发现异常情况。2022年8月12日星期五18数据挖掘分类数据挖掘分类l我的理解挖掘的算法分为三个层次：我的理解挖掘的算法分为三个层次：l模式：比如分类、聚类模式：比如分类、聚类l模型：决策树、神经网络模型：决策树、神

14、经网络l算法：算法：ID3、CHAID、BPl举例：举例：l分类决策树分类决策树ID3、CHAID等；等；l聚类聚类分析聚类聚类分析k-means、EM等。等。2022年8月12日星期五19数据挖掘分类数据挖掘分类l挖掘模型挖掘模型决策树决策树(decision tree)关联规则关联规则(association rules)聚类聚类(clustering)神经网络神经网络(Artificial Neural Networks，简记作简记作ANN)粗糙集粗糙集(rough set)概念格概念格(concept lattice)遗传算法遗传算法(genetic algorithms)序列模式序列

15、模式(sequence pattern)贝叶斯贝叶斯(Bayes)支持向量机支持向量机(support vector machine，简记作简记作SVM)模糊集模糊集(fuzzy set)基于案例的推理基于案例的推理(case-based reasoning，简记作简记作CBR)2022年8月12日星期五20决策树决策树l决策树学习是以实例为基础的归纳学习算法决策树学习是以实例为基础的归纳学习算法,着着眼于从一组无次序眼于从一组无次序/无规则的事例中推理出决策无规则的事例中推理出决策树表示形式的分类规则；树表示形式的分类规则；l决策树基本算法是决策树基本算法是:贪心算法贪心算法,它以自顶向下递

16、归、它以自顶向下递归、各个击破方式构造决策树各个击破方式构造决策树.2022年8月12日星期五21关联规则关联规则l关联规则是形式如下的一种规则，关联规则是形式如下的一种规则，“在购买面在购买面包和黄油的顾客中，有包和黄油的顾客中，有9090的人同时也买了牛的人同时也买了牛奶奶”（面包黄油（面包黄油 牛奶）；牛奶）；l关联规则的关联规则的“三度三度”：支持度、可信度、兴趣：支持度、可信度、兴趣度。度。2022年8月12日星期五22聚类聚类l聚类是根据数据的不同特征聚类是根据数据的不同特征,将其划分为不同的将其划分为不同的簇（簇（clustercluster）,目的是使得属于同一个簇中的目的是使

17、得属于同一个簇中的对象之间具有较高的相似度，而不同簇中的对对象之间具有较高的相似度，而不同簇中的对象差别（相异度）较大；象差别（相异度）较大；l聚类技术大致分为五种：聚类技术大致分为五种：l划分方法（划分方法（partitioning methodpartitioning method）l层次方法（层次方法（hierarchical methodhierarchical method）l基于密度的方法（基于密度的方法（density-based methoddensity-based method）l基于网格的方法（基于网格的方法（grid-based methodgrid-based met

18、hod）l基于模型的方法（基于模型的方法（model-based methodmodel-based method）2022年8月12日星期五23神经网络神经网络l人工神经网络人工神经网络，是对人类大脑系统的中模拟；是对人类大脑系统的中模拟；l神经网络是一组连接的输入神经网络是一组连接的输入/输出单元输出单元,其中每个其中每个连接都与一个权相关联连接都与一个权相关联,在学习阶段在学习阶段,通过调整神通过调整神经网络的权经网络的权,使得能够预测输入样本的正确类标使得能够预测输入样本的正确类标号来学习号来学习。l激励函数的选择和权值的调整激励函数的选择和权值的调整2022年8月12日星期五24粗糙

19、集粗糙集l粗糙集理论是一种研究不精确、不确定性知识的数学工具；粗糙集理论是一种研究不精确、不确定性知识的数学工具；l粗糙集对不精确概念的描述方法是：通过上近似概念和下粗糙集对不精确概念的描述方法是：通过上近似概念和下近似概念这两个精确概念来表示；近似概念这两个精确概念来表示；一个概念（或集合）的一个概念（或集合）的下近似指的是其中的元素肯定属于该概念；一个概念（或下近似指的是其中的元素肯定属于该概念；一个概念（或集合）的上近似指的是其中的元素可能属于该概念。集合）的上近似指的是其中的元素可能属于该概念。l粗糙集方法则有几个优点：不需要预先知道的额外信息，粗糙集方法则有几个优点：不需要预先知道的

20、额外信息，如统计中要求的先验概率和模糊集中要求的隶属度；算法如统计中要求的先验概率和模糊集中要求的隶属度；算法简单，易于操作。简单，易于操作。l粗糙集理论在知识发现研究中有着许多具体应用，特别适粗糙集理论在知识发现研究中有着许多具体应用，特别适合于数据之间（精确的或近似的）依赖关系发现、评价某合于数据之间（精确的或近似的）依赖关系发现、评价某一分类（属性）的重要性、数据相似或差异发现、数据模一分类（属性）的重要性、数据相似或差异发现、数据模式发现、从数据中产生一般决策规则、削减冗余对象与属式发现、从数据中产生一般决策规则、削减冗余对象与属性、寻求属性的最小子集以确保产生满意的近似分类等等性、寻

21、求属性的最小子集以确保产生满意的近似分类等等 2022年8月12日星期五25粗糙集粗糙集l举例2022年8月12日星期五26概念格概念格l概念格描述的是对象和属性之间的联系和统一，概念格描述的是对象和属性之间的联系和统一，表明概念之间的泛化和例化关系，相应的表明概念之间的泛化和例化关系，相应的Hasse图实现数据的可视化图实现数据的可视化。2022年8月12日星期五27遗传算法遗传算法l遗传算法（遗传算法（Genetic Algoritms，简称简称GA）是是以自然选择和遗传理论为基础，将生物进化过以自然选择和遗传理论为基础，将生物进化过程中程中“适者生存适者生存”规则与群体内部染色体的随规则

22、与群体内部染色体的随机信息交换机制相结合的搜索算法机信息交换机制相结合的搜索算法；l遗传算法主要组成部分包括编码方案、适应度遗传算法主要组成部分包括编码方案、适应度计算、父代选择、交换算子和变异算子。计算、父代选择、交换算子和变异算子。2022年8月12日星期五28序列模式序列模式l是指在多个数据序列中发现共同的行为模式。是指在多个数据序列中发现共同的行为模式。l通过时间序列搜索出重复发生概率较高的模式。通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。这里强调时间序列的影响。l例如，在所有购买了激光打印机的人中，半年后例如，在所有购买了激光打印机的人中，半年后80%的人再购买

23、新硒鼓，的人再购买新硒鼓，20%的人用旧硒鼓装碳粉；的人用旧硒鼓装碳粉；l在所有购买了彩色电视机的人中，有在所有购买了彩色电视机的人中，有60%的人再购的人再购买买VCD产品产品；l在时序模式中，需要找出在某个最短时间内出在时序模式中，需要找出在某个最短时间内出现比率一直高于某一最小百分比（阈值）的规现比率一直高于某一最小百分比（阈值）的规则。则。2022年8月12日星期五29贝叶斯贝叶斯l贝叶斯分类是统计学的分类方法，其分析方法贝叶斯分类是统计学的分类方法，其分析方法的特点是使用概率来表示所有形式的不确定性，的特点是使用概率来表示所有形式的不确定性，学习或推理都用概率规则来实现；学习或推理都

24、用概率规则来实现；l朴素贝叶斯分类：假定一个属性值对给定类的朴素贝叶斯分类：假定一个属性值对给定类的影响独立于其他属性的值；影响独立于其他属性的值；l贝叶斯网络：是用来表示变量间连接概率的图贝叶斯网络：是用来表示变量间连接概率的图形模式形模式,它提供了一种自然的表示因果信息的方它提供了一种自然的表示因果信息的方法法,用来发现数据间的潜在关系。用来发现数据间的潜在关系。2022年8月12日星期五30支持向量机支持向量机l支持向量机（支持向量机（Support Vector Machine,SVM）建立在计算学习理论的结构风险最小化建立在计算学习理论的结构风险最小化(SRM)原则之上。其核心问题是

25、寻找一种归纳原则，原则之上。其核心问题是寻找一种归纳原则，以实现最小化风险，从而实现最佳的推广能力。以实现最小化风险，从而实现最佳的推广能力。而且而且SVM一个重要的优点是可以处理线性不可一个重要的优点是可以处理线性不可分的情况分的情况。l以往的机器学习理论的核心是经验风险最小化以往的机器学习理论的核心是经验风险最小化原则（原则（ERM）2022年8月12日星期五31模糊集模糊集l模糊集：不同于经典集合，没有精确边界的集模糊集：不同于经典集合，没有精确边界的集合；合；l定义：设定义：设X是对象是对象x的集合，的集合，x是是X的任一个元素。的任一个元素。X上的模糊集合上的模糊集合A定义为一组有序

26、对：定义为一组有序对：A（x，uA(X)）|x X,其中其中uA(X)称为模糊集合称为模糊集合A的隶属的隶属度函数（度函数（membership function,MF）MF将集将集合中的元素映射为合中的元素映射为0到到1之间的隶属度；之间的隶属度；l隶属度为隶属度为0，或者，或者1，则，则A就退化为经典集合。就退化为经典集合。2022年8月12日星期五32案例的推理案例的推理l案例是一段带有上下文信息的知识案例是一段带有上下文信息的知识,该知识表达该知识表达了推理机在达到其目标的过程中能起关键作用了推理机在达到其目标的过程中能起关键作用的经验的经验 2022年8月12日星期五33几个概念的区

27、别几个概念的区别l分类和聚类分类和聚类l分类是指将数据归于一系列分类是指将数据归于一系列已知类别已知类别之中的某个类之中的某个类的分类过程的分类过程;l聚类是根据客体属性对一系列聚类是根据客体属性对一系列未分类未分类的客体进行类的客体进行类别的识别别的识别,把一组个体按照相似性归成若干类。把一组个体按照相似性归成若干类。l分类和预测分类和预测l是两种数据分析形式是两种数据分析形式.是两类主要的预测问题是两类主要的预测问题l分类是预测分类号分类是预测分类号(或者或者离散值离散值);l而预测是建立而预测是建立连续值连续值(例如使用回归分析例如使用回归分析)的函数模型的函数模型 l预测和回归：预测和回归：l预测是利用历史数据找出变化规律，建立模型，并预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类，特征等用此模型来预测未来数据的种类，特征等 l预测的典型方法就是回归分析。预测的典型方法就是回归分析。2022年8月12日星期五34其他问题其他问题l数据挖掘的发展趋势涉及到：分布、并行、异数据挖掘的发展趋势涉及到：分布、并行、异质数据库等方面的技术质数据库等方面的技术2022年8月12日星期五35谢谢谢谢