Slide Title,Body Text,Second level,Third level,数据挖掘算法介绍 综述,2004年12月17日,数据挖掘,数据挖掘,是从,大量数据,中提取出有效的、新颖的、有潜在作用的、可信的、并能最终被人理解的,模式(,pattern),的非平凡的处理过程。,KDD,DM,KDD,KDD:knowledge discovery in database,数据,建模,验证,应用,DM,DM:dataming,KDD,的一个阶段,KDD,与,DM,等同,DM,is like setting up a restaurant kitchen.,Starting a restaurant,kitchen,Data Mining,Food/Info,Cooks/Team,Kitchen/DWH,数据挖掘与其他学科的关系,Data Mining,Database,Technology,Statistics,Other,Disciplines,Information,Science,Machine,Learning(AI),Visualization,数据挖掘与,OLAP,OLAP（,on,-line analytical processing,）:,只能限制于少量的维度和数据类型,用户控制的流程,假设验证结论,DM：,没有明确假设的前提下去挖掘信息、发现知识具,有未知、有效、可实用三个特征,能自动的发现隐藏在数据中的规律,可以发现比,OLAP,更复杂而细致的信息,未知归纳结论,联系：,OLAPDM,OLAM,数据挖掘与统计学,数据挖掘：,数据挖掘利用了统计,、,人工智能,、数据库等,技术，把这些高深复杂的技术封装起来，使人们不用自己掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问题；,不仅仅是统计分析,；,统计分析：,统计分析技术都基于完善的数学理论和高超的技巧，预测的准确度还是令人满意的，但对使用者的要求很高,联系,统计分析方法学的延伸和扩展,很多的挖掘算法来源于统计学,前景,预言：,著名的咨询公司,Gartner Group,在（2000年）一次高级技术调查将数据挖掘和人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位,国外现状：,成熟、,产品：,SAS、CLEMENTINE、UNICA、,各大数据库,国内现状：,起步,产品：大部分是实验室产品,数据挖掘分类,挖掘对象,基于数据库的挖掘,基于,web,的挖掘,基于文本的挖掘,其他：音频、视频等多媒体数据库,数据挖掘分类,应用,响应模型,交叉销售,价值评估,客户分群,数据挖掘分类,挖掘模式,预测型(,Predictive),描述型(,Descriptive),实际作用可分为以下几种模式：,分类：对没有分类的数据进行分类；,预测：用历史来预测未来；,关联分析：关联规则；,聚类：物以类聚；,序列模式：,在多个数据序列中发现共同的行为模式;,描述和可视化：数据挖掘的结果的表示形式;,偏差分析：,从数据分析中发现异常情况。,数据挖掘分类,我的理解挖掘的算法分为三个层次：,模式：比如分类、聚类,模型：决策树、神经网络,算法：,ID3、CHAID、BP,举例：,分类决策树,ID3、CHAID,等；,聚类聚类分析,k-means、EM,等。,数据挖掘分类,挖掘模型,决策树(,decision tree),关联规则(,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),决策树,决策树学习是以实例为基础的归纳学习算法,着眼于从一组无次序,/,无规则的事例中推理出决策树表示形式的分类规则；,决策树基本算法是,:,贪心算法,它以自顶向下递归、各个击破方式构造决策树,.,关联规则,关联规则是形式如下的一种规则，,“,在购买面包和黄油的顾客中，有90的人同时也买了牛奶,”,（面包黄油 牛奶）；,关联规则的,“,三度,”,：支持度、可信度、兴趣度。,聚类,聚类是根据数据的不同特征,将其划分为不同的簇（,cluster）,目的是使得属于同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别（相异度）较大；,聚类技术大致分为五种：,划分方法（,partitioning method）,层次方法（,hierarchical method）,基于密度的方法（,density-based method）,基于网格的方法（,grid-based method）,基于模型的方法（,model-based method）,神经网络,人工神经网络,，,是对人类大脑系统的中模拟；,神经网络是一组连接的输入,/,输出单元,其中每个连接都与一个权相关联,在学习阶段,通过调整神经网络的权,使得能够预测输入样本的正确类标号来学习,。,激励函数的选择和权值的调整,粗糙集,粗糙集理论是一种研究不精确、不确定性知识的数学工具；,粗糙集对不精确概念的描述方法是：通过上近似概念和下近似概念这两个精确概念来表示；,一个概念（或集合）的下近似指的是其中的元素肯定属于该概念；一个概念（或集合）的上近似指的是其中的元素可能属于该概念。,粗糙集方法则有几个优点：不需要预先知道的额外信息，如统计中要求的先验概率和模糊集中要求的隶属度；算法简单，易于操作。,粗糙集理论在知识发现研究中有着许多具体应用，特别适合于数据之间（精确的或近似的）依赖关系发现、评价某一分类（属性）的重要性、数据相似或差异发现、数据模式发现、从数据中产生一般决策规则、削减冗余对象与属性、寻求属性的最小子集以确保产生满意的近似分类等等,粗糙集,举例,概念格,概念格描述的是对象和属性之间的联系和统一，表明概念之间的泛化和例化关系，相应的,Hasse,图实现数据的可视化,。,遗传算法,遗传算法（,Genetic,Algoritms,，,简称,GA）,是以自然选择和遗传理论为基础，将生物进化过程中“适者生存”规则与群体内部染色体的随机信息交换机制相结合的搜索算法；,遗传算法主要组成部分包括编码方案、适应度计算、父代选择、交换算子和变异算子。,序列模式,是指在多个数据序列中发现共同的行为模式,。,通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。,例如，在所有购买了激光打印机的人中，半年后,80%,的人再购买新硒鼓，,20%,的人用旧硒鼓装碳粉；,在所有购买了彩色电视机的人中，有,60%,的人再购买,VCD,产品,；,在时序模式中，需要找出在某个最短时间内出现比率一直高于某一最小百分比（阈值）的规则。,贝叶斯,贝叶斯分类是统计学的分类方法，其分析方法的特点是使用概率来表示所有形式的不确定性，学习或推理都用概率规则来实现；,朴素贝叶斯分类：假定一个属性值对给定类的影响独立于其他属性的值；,贝叶斯网络：是用来表示变量间连接概率的图形模式,它提供了一种自然的表示因果信息的方法,用来发现数据间的潜在关系。,支持向量机,支持向量机（,Support Vector Machine,SVM）,建立在计算学习理论的结构风险最小化(,SRM),原则之上。其核心问题是寻找一种归纳原则，以实现最小化风险，从而实现最佳的推广能力。而且,SVM,一个重要的优点是可以处理线性不可分的情况,。,以往的机器学习理论的核心是经验风险最小化原则（,ERM）,模糊集,模糊集：不同于经典集合，没有精确边界的集合；,定义：设,X,是对象,x,的集合，,x,是,X,的任一个元素。,X,上的模糊集合,A,定义为一组有序对：,A（x，u,A,(X)）|x,X,其中,u,A,(X,),称为模糊集合,A,的隶属度函数（,membership,function,MF）MF,将集合中的元素映射为0到1之间的隶属度；,隶属度为0，或者1，则,A,就退化为经典集合。,案例的推理,案例是一段带有上下文信息的知识,该知识表达了推理机在达到其目标的过程中能起关键作用的经验,几个概念的区别,分类和聚类,分类是指将数据归于一系列,已知类别,之中的某个类的分类过程,;,聚类是根据客体属性对一系列,未分类,的客体进行类别的识别,把一组个体按照相似性归成若干类。,分类和预测,是两种数据分析形式,.,是两类主要的预测问题,分类是预测分类号,(,或者,离散值,);,而预测是建立,连续值,(,例如使用回归分析,),的函数模型,预测和回归：,预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据的种类，特征等,预测的典型方法就是回归分析。,其他问题,数据挖掘的发展趋势涉及到：分布、并行、异质数据库等方面的技术,谢谢,