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

《数据挖掘算法介绍-综述.ppt》由会员分享，可在线阅读，更多相关《数据挖掘算法介绍-综述.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、Microfluidics）2023/4/232什么是数据挖掘？什么是数据挖掘？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/

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

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

5、l）而非算法（）而非算法（Algorithm）n但二者具有相当密切的联系但二者具有相当密切的联系从数据分析的角度，统计学现在是且仍将是数据挖掘最重要的技术支撑和思想源泉从数据分析的角度，统计学现在是且仍将是数据挖掘最重要的技术支撑和思想源泉更加深入的渗透和交叉（如探索性数据分析，更加深入的渗透和交叉（如探索性数据分析，EDA）数据挖掘是数据驱动的探索性分析!2023/4/235其他数据分析方法：商业智能其他数据分析方法：商业智能n的数据分析模型的数据分析模型绝对模型（绝对模型（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 Discove

7、ryMachine-assisted Discovery现象 模型 误差数据挖掘寻找的是模型!2023/4/236数据挖掘数据挖掘数据挖掘数据挖掘数据挖掘数据挖掘是从是从是从是从大量数据大量数据大量数据大量数据中中中中提取出有效的、新颖的、有提取出有效的、新颖的、有提取出有效的、新颖的、有提取出有效的、新颖的、有潜在作用的、可信的、并能潜在作用的、可信的、并能潜在作用的、可信的、并能潜在作用的、可信的、并能最终被人理解的最终被人理解的最终被人理解的最终被人理解的模式模式模式模式(pattern)pattern)的非平凡的处理的非平凡的处理的非平凡的处理的非平凡的处理过程。过程。过程。过程。KD

8、D DM2023/4/237KDDKDD:knowledge discovery in database数据数据建模建模验证验证应用应用2023/4/238DMDM:datamingKDD的一个阶段KDD与DM等同2023/4/239DM is like setting up a restaurant kitchen.Starting a restaurantkitchenData MiningFood/InfoCooks/TeamKitchen/DWH2023/4/2310数据挖掘与其他学科的关系数据挖掘与其他学科的关系Data MiningDatabase TechnologyStatis

9、ticsOtherDisciplinesInformationScienceMachineLearning(AI)Visualization2023/4/2311数据挖掘与数据挖掘与OLAPlOLAP（on-line analytical processing）:l只能限制于少量的维度和数据类型只能限制于少量的维度和数据类型l用户控制的流程用户控制的流程l假设假设验证验证结论结论lDM：l没有明确假设的前提下去挖掘信息、发现知识没有明确假设的前提下去挖掘信息、发现知识具具 有未知、有效、可实用三个特征有未知、有效、可实用三个特征 l能自动的发现隐藏在数据中的规律能自动的发现隐藏在数据中的规律l

10、可以发现比可以发现比OLAP更复杂而细致的信息更复杂而细致的信息l未知未知归纳归纳结论结论l联系：联系：lOLAPDMlOLAM2023/4/2312数据挖掘与统计学数据挖掘与统计学l数据挖掘：数据挖掘：l数据挖掘利用了统计、人工智能、数据库等技术，数据挖掘利用了统计、人工智能、数据库等技术，把这些高深复杂的技术封装起来，使人们不用自己把这些高深复杂的技术封装起来，使人们不用自己掌握这些技术也能完成同样的功能，并且更专注于掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问题自己所要解决的问题 ；l不仅仅是统计分析不仅仅是统计分析；l统计分析：统计分析：l统计分析技术都基于完善的数学理

11、论和高超的技巧，统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求预测的准确度还是令人满意的，但对使用者的要求很高很高 l联系联系l统计分析方法学的延伸和扩展统计分析方法学的延伸和扩展 l很多的挖掘算法来源于统计学很多的挖掘算法来源于统计学2023/4/2313前景前景l预言：预言：l著名的咨询公司著名的咨询公司 Gartner Group在（在（2000年）一次高级年）一次高级技术调查将数据挖掘和人工智能列为技术调查将数据挖掘和人工智能列为“未来三到五年内未来三到五年内将对工业产生深远影响的五大关键技术将对工业产生深远影响的五大关键技术”之首，并且还之

12、首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位十大新兴技术前两位l国外现状：国外现状：l成熟、成熟、l产品：产品：SAS、CLEMENTINE、UNICA、各大数据库各大数据库l国内现状：国内现状：l起步起步l产品：大部分是实验室产品产品：大部分是实验室产品2023/4/2314数据挖掘分类数据挖掘分类l挖掘对象挖掘对象基于数据库的挖掘基于数据库的挖掘基于基于web的挖掘的挖掘基于文本的挖掘基于文本的挖掘其他：音频、视频等多媒体数据库其他：音频、视频等多媒体数据库2023/4/2315数据挖掘分类数据挖掘分类l应用应

13、用响应模型响应模型交叉销售交叉销售价值评估价值评估客户分群客户分群2023/4/2316数据挖掘分类数据挖掘分类l挖掘模式挖掘模式l预测型预测型(Predictive)Predictive)l描述型描述型(Descriptive)Descriptive)l实际作用可分为以下几种模式：实际作用可分为以下几种模式：分类：对没有分类的数据进行分类；分类：对没有分类的数据进行分类；预测：用历史来预测未来；预测：用历史来预测未来；关联分析：关联规则；关联分析：关联规则；聚类：物以类聚；聚类：物以类聚；序列模式：序列模式：在多个数据序列中发现共同的行为模式在多个数据序列中发现共同的行为模式;描述和可视化：

14、数据挖掘的结果的表示形式描述和可视化：数据挖掘的结果的表示形式;偏差分析：偏差分析：从数据分析中发现异常情况。从数据分析中发现异常情况。2023/4/2317数据挖掘分类数据挖掘分类l我的理解挖掘的算法分为三个层次：我的理解挖掘的算法分为三个层次：l模式：比如分类、聚类模式：比如分类、聚类l模型：决策树、神经网络模型：决策树、神经网络l算法：算法：ID3、CHAID、BPl举例：举例：l分类决策树分类决策树ID3、CHAID等；等；l聚类聚类分析聚类聚类分析k-means、EM等。等。2023/4/2318数据挖掘分类数据挖掘分类l挖掘模型挖掘模型决策树决策树(decision tree)关联

15、规则关联规则(association rules)聚类聚类(clustering)神经网络神经网络(Artificial Neural Networks，简记作简记作ANN)粗糙集粗糙集(rough set)概念格概念格(concept lattice)遗传算法遗传算法(genetic algorithms)序列模式序列模式(sequence pattern)贝叶斯贝叶斯(Bayes)支持向量机支持向量机(support vector machine，简记作简记作SVM)模糊集模糊集(fuzzy set)基于案例的推理基于案例的推理(case-based reasoning，简记作简记作CBR

16、)2023/4/2319决策树决策树l决策树学习是以实例为基础的归纳学习算法决策树学习是以实例为基础的归纳学习算法,着着眼于从一组无次序眼于从一组无次序/无规则的事例中推理出决策无规则的事例中推理出决策树表示形式的分类规则；树表示形式的分类规则；l决策树基本算法是决策树基本算法是:贪心算法贪心算法,它以自顶向下递它以自顶向下递归、各个击破方式构造决策树归、各个击破方式构造决策树.2023/4/2320关联规则关联规则l关联规则是形式如下的一种规则，关联规则是形式如下的一种规则，“在购买面在购买面包和黄油的顾客中，有包和黄油的顾客中，有9090的人同时也买了牛的人同时也买了牛奶奶”（面包黄油（面

17、包黄油 牛奶）；牛奶）；l关联规则的关联规则的“三度三度”：支持度、可信度、兴趣：支持度、可信度、兴趣度。度。2023/4/2321聚类聚类l聚类是根据数据的不同特征聚类是根据数据的不同特征,将其划分为不同的将其划分为不同的簇（簇（clustercluster）,目的是使得属于同一个簇中的目的是使得属于同一个簇中的对象之间具有较高的相似度，而不同簇中的对对象之间具有较高的相似度，而不同簇中的对象差别（相异度）较大；象差别（相异度）较大；l聚类技术大致分为五种：聚类技术大致分为五种：l划分方法（划分方法（partitioning methodpartitioning method）l层次方法（层

18、次方法（hierarchical methodhierarchical method）l基于密度的方法（基于密度的方法（density-based methoddensity-based method）l基于网格的方法（基于网格的方法（grid-based methodgrid-based method）l基于模型的方法（基于模型的方法（model-based methodmodel-based method）2023/4/2322神经网络神经网络l人工神经网络人工神经网络，是对人类大脑系统的中模拟；是对人类大脑系统的中模拟；l神神经经网网络络是是一一组组连连接接的的输输入入/输输出出单单元元

19、,其其中中每每个个连连接接都都与与一一个个权权相相关关联联,在在学学习习阶阶段段,通通过过调调整整神神经经网网络络的的权权,使使得得能能够够预预测测输输入入样样本本的的正正确确类标号来学习类标号来学习。l激励函数的选择和权值的调整激励函数的选择和权值的调整2023/4/2323粗糙集粗糙集l粗糙集理论是一种研究不精确、不确定性知识的数学工具；粗糙集理论是一种研究不精确、不确定性知识的数学工具；l粗糙集对不精确概念的描述方法是：通过上近似概念和下粗糙集对不精确概念的描述方法是：通过上近似概念和下近似概念这两个精确概念来表示；近似概念这两个精确概念来表示；一个概念（或集合）的一个概念（或集合）的下

20、近似指的是其中的元素肯定属于该概念；一个概念（或下近似指的是其中的元素肯定属于该概念；一个概念（或集合）的上近似指的是其中的元素可能属于该概念。集合）的上近似指的是其中的元素可能属于该概念。l粗糙集方法则有几个优点：不需要预先知道的额外信息，粗糙集方法则有几个优点：不需要预先知道的额外信息，如统计中要求的先验概率和模糊集中要求的隶属度；算法如统计中要求的先验概率和模糊集中要求的隶属度；算法简单，易于操作。简单，易于操作。l粗糙集理论在知识发现研究中有着许多具体应用，特别适粗糙集理论在知识发现研究中有着许多具体应用，特别适合于数据之间（精确的或近似的）依赖关系发现、评价某合于数据之间（精确的或近

21、似的）依赖关系发现、评价某一分类（属性）的重要性、数据相似或差异发现、数据模一分类（属性）的重要性、数据相似或差异发现、数据模式发现、从数据中产生一般决策规则、削减冗余对象与属式发现、从数据中产生一般决策规则、削减冗余对象与属性、寻求属性的最小子集以确保产生满意的近似分类等等性、寻求属性的最小子集以确保产生满意的近似分类等等 2023/4/2324粗糙集粗糙集l举例2023/4/2325概念格概念格l概念格描述的是对象和属性之间的联系和统一，概念格描述的是对象和属性之间的联系和统一，表明概念之间的泛化和例化关系，相应的表明概念之间的泛化和例化关系，相应的Hasse图实现数据的可视化图实现数据的

22、可视化。2023/4/2326遗传算法遗传算法l遗传算法（遗传算法（Genetic Algoritms，简称简称GA）是是以自然选择和遗传理论为基础，将生物进化过以自然选择和遗传理论为基础，将生物进化过程中程中“适者生存适者生存”规则与群体内部染色体的随规则与群体内部染色体的随机信息交换机制相结合的搜索算法机信息交换机制相结合的搜索算法；l遗传算法主要组成部分包括编码方案、适应度遗传算法主要组成部分包括编码方案、适应度计算、父代选择、交换算子和变异算子。计算、父代选择、交换算子和变异算子。2023/4/2327序列模式序列模式l是指在多个数据序列中发现共同的行为模式。是指在多个数据序列中发现共

23、同的行为模式。l通过时间序列搜索出重复发生概率较高的模式。通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。这里强调时间序列的影响。l例如，在所有购买了激光打印机的人中，半年后例如，在所有购买了激光打印机的人中，半年后80%的人再购买新硒鼓，的人再购买新硒鼓，20%的人用旧硒鼓装碳粉；的人用旧硒鼓装碳粉；l在所有购买了彩色电视机的人中，有在所有购买了彩色电视机的人中，有60%的人再购的人再购买买VCD产品产品；l在时序模式中，需要找出在某个最短时间内出在时序模式中，需要找出在某个最短时间内出现比率一直高于某一最小百分比（阈值）的规现比率一直高于某一最小百分比（阈值）的规则。则。

24、2023/4/2328贝叶斯贝叶斯l贝贝叶叶斯斯分分类类是是统统计计学学的的分分类类方方法法，其其分分析析方方法法的的特特点点是是使使用用概概率率来来表表示示所所有有形形式式的的不不确确定定性性，学习或推理都用概率规则来实现；学习或推理都用概率规则来实现；l朴朴素素贝贝叶叶斯斯分分类类：假假定定一一个个属属性性值值对对给给定定类类的的影响独立于其他属性的值；影响独立于其他属性的值；l贝贝叶叶斯斯网网络络：是是用用来来表表示示变变量量间间连连接接概概率率的的图图形形模模式式,它它提提供供了了一一种种自自然然的的表表示示因因果果信信息息的的方方法法,用来发现数据间的潜在关系。用来发现数据间的潜在关

25、系。2023/4/2329支持向量机支持向量机l支持向量机（支持向量机（Support Vector Machine,SVM）建立在计算学习理论的结构风险最小化建立在计算学习理论的结构风险最小化(SRM)原原则之上。其核心问题是寻找一种归纳原则，以则之上。其核心问题是寻找一种归纳原则，以实现最小化风险，从而实现最佳的推广能力。实现最小化风险，从而实现最佳的推广能力。而且而且SVM一个重要的优点是可以处理线性不可一个重要的优点是可以处理线性不可分的情况分的情况。l以往的机器学习理论的核心是经验风险最小化以往的机器学习理论的核心是经验风险最小化原则（原则（ERM）2023/4/2330模糊集模糊集

26、l模糊集：不同于经典集合，没有精确边界的集模糊集：不同于经典集合，没有精确边界的集合；合；l定义：设定义：设X是对象是对象x的集合，的集合，x是是X的任一个元素。的任一个元素。X上的模糊集合上的模糊集合A定义为一组有序对：定义为一组有序对：A（x，uA(X)）|x X,其中其中uA(X)称为模糊集合称为模糊集合A的的隶属度函数（隶属度函数（membership function,MF）MF将集合中的元素映射为将集合中的元素映射为0到到1之间的隶属度；之间的隶属度；l隶属度为隶属度为0，或者，或者1，则，则A就退化为经典集合。就退化为经典集合。2023/4/2331案例的推理案例的推理l案例是一

27、段带有上下文信息的知识案例是一段带有上下文信息的知识,该知识表达该知识表达了推理机在达到其目标的过程中能起关键作用了推理机在达到其目标的过程中能起关键作用的经验的经验 2023/4/2332几个概念的区别几个概念的区别l分类和聚类分类和聚类l分类是指将数据归于一系列分类是指将数据归于一系列已知类别已知类别之中的某个类之中的某个类的分类过程的分类过程;l聚类是根据客体属性对一系列聚类是根据客体属性对一系列未分类未分类的客体进行类的客体进行类别的识别别的识别,把一组个体按照相似性归成若干类。把一组个体按照相似性归成若干类。l分类和预测分类和预测l是两种数据分析形式是两种数据分析形式.是两类主要的预

28、测问题是两类主要的预测问题l分类是预测分类号分类是预测分类号(或者或者离散值离散值);l而预测是建立而预测是建立连续值连续值(例如使用回归分析例如使用回归分析)的函数模的函数模型型 l预测和回归：预测和回归：l预测是利用历史数据找出变化规律，建立模型，并预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类，特征等用此模型来预测未来数据的种类，特征等 l预测的典型方法就是回归分析。预测的典型方法就是回归分析。2023/4/2333其他问题其他问题l数据挖掘的发展趋势涉及到：分布、并行、异数据挖掘的发展趋势涉及到：分布、并行、异质数据库等方面的技术质数据库等方面的技术2023/4/2334谢谢谢谢2023/4/2335