数据挖掘十大经典算法系列,点击链接直接跳转:
数据挖掘简介及十大经典算法(大纲索引)1. 数据挖掘十大经典算法之——C4.5 算法2. 数据挖掘十大经典算法之——K-Means 算法3. 数据挖掘十大经典算法之——SVM 算法4. 数据挖掘十大经典算法之——Apriori 算法5. 数据挖掘十大经典算法之——EM 算法6. 数据挖掘十大经典算法之——PageRank 算法7 数据挖掘十大经典算法之——AdaBoost 算法8. 数据挖掘十大经典算法之——KNN 算法9. 数据挖掘十大经典算法之——Naive Bayes 算法10. 数据挖掘十大经典算法之——CART 算法
文章目录
一 概念介绍二 方法简介1. 分类 (Classification)2. 回归(regression )3. 聚类(Clustering)4. 相关性分组或关联规则(Affinity grouping or association rules)5. 描述和可视化(Description and Visualization)三 应用领域四 应用依据五 十大经典算法1. C4.52. K-means算法3. SVM4. Apriori5. EM6. pagerank7. Adaboost8. KNN9. Naive Bayes10. CART六 关联规则1. 过程2. 分类3. 算法4. 应用5. 研究6. 相关性和区别一 概念介绍
定义:数据挖掘(Data mining)又译为资料探勘、数据采矿。它是数据库知识发现(Knowledge-Discovery in Databases,简称:KDD)中的一个步骤。是计算机科学的一种。 数据挖掘一般是指从大量的数据中通过算法搜索隐藏于其中信息的过程。数据挖掘通常与计算机科学有关,并通过统计、在线分析处理、情报检索、机器学习、专家系统(依靠过去的经验法则)和模式识别等诸多方法来实现上述目标。
应用:近年来,数据挖掘引起了信息产业界的极大关注,其主要原因是存在大量数据,可以广泛使用,并且迫切需要将这些数据转换成有用的信息和知识。获取的信息和知识可以广泛用于各种应用,包括商务管理,生产控制,市场分析,工程设计和科学探索等。
数据挖掘利用了来自如下一些领域的思想:
(1)统计学的抽样、估计和假设检验;
(2)人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论;
(3)最优化、进化计算、信息论、信号处理、可视化和信息检索;
(4)数据库系统提供有效的存储、索引和查询处理支持;
(5)高性能(并行)计算技术处理海量数据集;
(6)分布式技术处理非集中分布海量数据。
图1 数据挖掘的系统模型
二 方法简介
1. 分类 (Classification)
首先从数据中选出已经分好类的训练集,在该训练集上运用数据挖掘分类的技术,建立分类模型,对于没有分类的数据进行分类。
应用:
a. 信用卡申请者,分类为低、中、高风险
b. 故障诊断:中国宝钢集团与上海天律信息技术有限公司合作,采用数据挖掘技术对钢材生产的全流程进行质量监控和分析,构建故障地图,实时分析产品出现瑕疵的原因,有效提高了产品的优良率。
注意: 类的个数是确定的,预先定义好的
2. 回归(regression )
回归与分类类似,不同之处在于,分类描述的是离散型变量的输出,而回归处理连续值的输出;分类的类别是确定数目的,回归的量是不确定的。
应用:
a. 根据购买模式,估计一个家庭的孩子个数
b. 根据购买模式,估计一个家庭的收入
c. 估计real estate的价值
一般来说,回归可以作为分类的前一步工作。给定一些输入数据,通过回归,得到未知的连续变量的值,然后,根据预先设定的阈值,进行分类。例如:银行对家庭贷款业务,运用估值,给各个客户记分(Score 0~1)。然后,根据阈值,将贷款级别分类。
3. 聚类(Clustering)
聚类是对记录分组,把相似的记录在一个聚集里。聚类和分类的区别是聚集不依赖于预先定义好的类,不需要训练集。
例子:
a. 一些特定症状的聚集可能预示了一个特定的疾病
b. 租VCD类型不相似的客户聚集,可能暗示成员属于不同的亚文化群
聚集通常作为数据挖掘的第一步。例如,“哪一种类的促销对客户响应最好?”,对于这一 类问题,首先对整个客户做聚集,将客户分组在各自的聚集里,然后对每个不同的聚集,回答问题,可能效果更好。
4. 相关性分组或关联规则(Affinity grouping or association rules)
决定哪些事情将一起发生。
例子:
a. 超市中客户在购买A的同时,经常会购买B,即A => B(关联规则)
b. 客户在购买A后,隔一段时间,会购买B (序列分析)
5. 描述和可视化(Description and Visualization)
是对数据挖掘结果的表示方式。一般只是指数据可视化工具,包含报表工具和商业智能分析产品(BI)的统称。通过可视化工具进行数据的展现,分析,钻取,将数据挖掘的分析结果更形象,深刻的展现出来。
三 应用领域
从目前网络招聘的信息来看,大小公司对数据挖掘的需求有50多个方面:
1、数据统计分析
2、预测预警模型
3、数据信息阐释
4、数据采集评估
5、数据加工仓库
6、品类数据分析
7、销售数据分析
8、网络数据分析
9、流量数据分析
10、交易数据分析
11、媒体数据分析
12、情报数据分析
13、金融产品设计
14、日常数据分析
15、总裁万事通
16、数据变化趋势
17、预测预警模型
18、运营数据分析
19、商业机遇挖掘
20、风险数据分析
21、缺陷信息挖掘
22、决策数据支持
23、运营优化与成本控制
24、质量控制与预测预警
25、系统工程数学技术
26、用户行为分析/客户需求模型
27、产品销售预测(热销特征)
28、商场整体利润最大化系统设计
29、市场数据分析
30、综合数据关联系统设计
31、行业/企业指标设计
32、企业发展关键点分析
33、资金链管理设计与风险控制
34、用户需求挖掘
35、产品数据分析
36、销售数据分析
37、异常数据分析
38、数学规划与数学方案
39、数据实验模拟
40、数学建模与分析
41、呼叫中心数据分析
42、贸易/进出口数据分析
43、海量数据分析系统设计、关键技术研究
44、数据清洗、分析、建模、调试、优化
45、数据挖掘算法的分析研究、建模、实验模拟
46、组织机构运营监测、评估、预测预警
47、经济数据分析、预测、预警
48、金融数据分析、预测、预警
49、科研数学建模与数据分析:社会科学,自然科学,医药,农学,计算机,工程,信息,军事,图书情报等
50、数据指标开发、分析与管理
51、产品数据挖掘与分析
52、商业数学与数据技术
53、故障预测预警技术
54、数据自动分析技术
55、泛工具分析
56、互译
57、指数化
其中,互译与指数化是数据挖掘除计算机技术之外最核心的两大技术。
四 应用依据
第一,目标律:业务目标是所有数据解决方案的源头。
第二,知识律:业务知识是数据挖掘过程每一步的核心。
第三,准备律:数据预处理比数据挖掘其他任何一个过程都重要。
第四,试验律(NFL律:No Free Lunch):对于数据挖掘者来说,天下没有免费的午餐,一个正确的模型只有通过试验(experiment)才能被发现。
第五,模式律(大卫律):数据中总含有模式。
第六,洞察律:数据挖掘增大对业务的认知。
第七,预测律:预测提高了信息泛化能力。
第八,价值律:数据挖掘的结果的价值不取决于模型的稳定性或预测的准确性。
第九,变化律:所有的模式因业务变化而变化。 [2]
五 十大经典算法
1. C4.5
数据挖掘十大经典算法之——C4.5 算法
2. K-means算法
数据挖掘十大经典算法之——K-Means 算法
3. SVM
数据挖掘十大经典算法之——SVM 算法
4. Apriori
数据挖掘十大经典算法之——Apriori 算法
5. EM
数据挖掘十大经典算法之——EM 算法
6. pagerank
数据挖掘十大经典算法之——PageRank 算法
7. Adaboost
数据挖掘十大经典算法之——AdaBoost 算法
8. KNN
数据挖掘十大经典算法之——KNN 算法
9. Naive Bayes
数据挖掘十大经典算法之——Naive Bayes 算法
10. CART
数据挖掘十大经典算法之——CART 算法
六 关联规则
数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值之间存在某种规律性,就称为关联。关联可分为简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数,即使知道也是不确定的,因此关联分析生成的规则带有可信度。关联规则挖掘发现大量数据中项集之间存在有趣的关联或相关联系。Agrawal等于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题,以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行优化,如引入随机采样、并行的思想等,以提高算法挖掘规则的效率;对关联规则的应用进行推广。关联规则挖掘在数据挖掘中是一个重要的课题,最近几年已被业界所广泛研究。
1. 过程
关联规则挖掘过程主要包含两个阶段:第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets),第二阶段再由这些高频项目组中产生关联规则(Association Rules)。
关联规则挖掘的第一阶段必须从原始资料集合中,找出所有高频项目组(Large Itemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言,必须达到某一水平。一项目组出现的频率称为支持度(Support),以一个包含A与B两个项目的2-itemset为例,我们可以经由公式(1)求得包含{A,B}项目组的支持度,若支持度大于等于所设定的最小支持度(Minimum Support)门槛值时,则{A,B}称为高频项目组。一个满足最小支持度的k-itemset,则称为高频k-项目组(Frequent k-itemset),一般表示为Large k或Frequent k。算法并从Large k的项目组中再产生Large k+1,直到无法再找到更长的高频项目组为止。
关联规则挖掘的第二阶段是要产生关联规则(Association Rules)。从高频项目组产生关联规则,是利用前一步骤的高频k-项目组来产生规则,在最小信赖度(Minimum Confidence)的条件门槛下,若一规则所求得的信赖度满足最小信赖度,称此规则为关联规则。例如:经由高频k-项目组{A,B}所产生的规则AB,其信赖度可经由公式(2)求得,若信赖度大于等于最小信赖度,则称AB为关联规则。
关联规则挖掘通常比较适用与记录中的指标取离散值的情况。如果原始数据库中的指标值是取连续的数据,则在关联规则挖掘之前应该进行适当的数据离散化(实际上就是将某个区间的值对应于某个值),数据的离散化是数据挖掘前的重要环节,离散化的过程是否合理将直接影响关联规则的挖掘结果。
2. 分类
按照不同情况,关联规则可以进行分类如下:
1.基于规则中处理的变量的类别,关联规则可以分为布尔型和数值型。
布尔型关联规则处理的值都是离散的、种类化的,它显示了这些变量之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起来,对数值型字段进行处理,将其进行动态的分割,或者直接对原始的数据进行处理,当然数值型关联规则中也可以包含种类变量。例如:性别=“女”=>职业=“秘书” ,是布尔型关联规则;性别=“女”=>avg(收入)=2300,涉及的收入是数值类
型,所以是一个数值型关联规则。
2.基于规则中数据的抽象层次,可以分为单层关联规则和多层关联规则。
在单层的关联规则中,所有的变量都没有考虑到现实的数据是具有多个不同的层次的;而在多层的关联规则中,对数据的多层性已经进行了充分的考虑。例如:IBM台式机=>Sony打印机,是一个细节数据上的单层关联规则;台式机=>Sony打印机,是一个较高层次和细节层次之间的多层关联规则。
3.基于规则中涉及到的数据的维数,关联规则可以分为单维的和多维的。
在单维的关联规则中,我们只涉及到数据的一个维,如用户购买的物品;而在多维的关联规则中,要处理的数据将会涉及多个维。换成另一句话,单维关联规则是处理单个属性中的一些关系;多维关联规则是处理各个属性之间的某些关系。例如:啤酒=>尿布,这条规则只涉及到用户的购买的物品;性别=“女”=>职业=“秘书”,这条规则就涉及到两个字段的信息,是两个维上的一条关联规则。 [2]
3. 算法
1.Apriori算法:使用候选项集找频繁项集
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里,所有支持度大于最小支持度的项集称为频繁项集,简称频集。
该算法的基本思想是:首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集,使用了递推的方法。
可能产生大量的候选集,以及可能需要重复扫描数据库,是Apriori算法的两大缺点。
2.基于划分的算法
Savasere等设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频集合并,用来生成所有可能的频集,最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的,可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后,处理器之间进行通信来产生全局的候选k-项集。通常这里的通信过程是算法执行时间的主要瓶颈;而另一方面,每个独立的处理器生成频集的时间也是一个瓶颈。
3.FP-树频集算法
针对Apriori算法的固有缺陷,J. Han等提出了不产生候选挖掘频繁项集的方法:FP-树频集算法。采用分而治之的策略,在经过第一遍扫描之后,把数据库中的频集压缩进一棵频繁模式树(FP-tree),同时依然保留其中的关联信息,随后再将FP-tree分化成一些条件库,每个库和一个长度为1的频集相关,然后再对这些条件库分别进行挖掘。当原始数据量很大的时候,也可以结合划分的方法,使得一个FP-tree可以放入主存中。实验表明,FP-growth对不同长度的规则都有很好的适应性,同时在效率上较之Apriori算法有巨大的提高。
4. 应用
就目前而言,关联规则挖掘技术已经被广泛应用在西方金融行业企业中,它可以成功预测银行客户需求。一旦获得了这些信息,银行就可以改善自身营销。现在银行天天都在开发新的沟通客户的方法。各银行在自己的ATM机上就捆绑了顾客可能感兴趣的本行产品信息,供使用本行ATM机的用户了解。如果数据库中显示,某个高信用限额的客户更换了地址,这个客户很有可能新近购买了一栋更大的住宅,因此会有可能需要更高信用限额,更高端的新信用卡,或者需要一个住房改善贷款,这些产品都可以通过信用卡账单邮寄给客户。当客户打电话咨询的时候,数据库可以有力地帮助电话销售代表。销售代表的电脑屏幕上可以显示出客户的特点,同时也可以显示出顾客会对什么产品感兴趣。
同时,一些知名的电子商务站点也从强大的关联规则挖掘中的受益。这些电子购物网站使用关联规则中规则进行挖掘,然后设置用户有意要一起购买的捆绑包。也有一些购物网站使用它们设置相应的交叉销售,也就是购买某种商品的顾客会看到相关的另外一种商品的广告。
但是目前在我国,“数据海量,信息缺乏”是商业银行在数据大集中之后普遍所面对的尴尬。目前金融业实施的大多数数据库只能实现数据的录入、查询、统计等较低层次的功能,却无法发现数据中存在的各种有用的信息,譬如对这些数据进行分析,发现其数据模式及特征,然后可能发现某个客户、消费群体或组织的金融和商业兴趣,并可观察金融市场的变化趋势。可以说,关联规则挖掘的技术在我国的研究与应用并不是很广泛深入。
近年来,电信业从单纯的语音服务演变为提供多种服务的综合信息服务商。随着网络技术和电信业务的发展,电信市场竞争也日趋激烈,电信业务的发展提出了对数据挖掘技术的迫切需求,以便帮助理解商业行为,识别电信模式,捕捉盗用行为,更好地利用资源,提高服务质量并增强自身的竞争力。下面运用一些简单的实例说明如何在电信行业使用数据挖掘技术。可以使用上面提到的K 均值、EM 等聚类算法,针对运营商积累的大量用户消费数据建立客户分群模型,通过客户分群模型对客户进行细分,找出有相同特征的目标客户群,然后有针对性地进行营销。而且,聚类算法也可以实现离群点检测,即在对用户消费数据进行聚类的过程中,发现一些用户的异常消费行为,据此判断这些用户是否存在欺诈行为,决定是否采取防范措施。可以使用上面提到的C4.5、SVM 和贝叶斯等分类算法,针对用户的行为数据,对用户进行信用等级评定,对于信用等级好的客户可以给予某些优惠服务等,对于信用等级差的用户不能享受促销等优惠。可以使用预测相关的算法,对电信客户的网络使用和客户投诉数据进行建模,建立预测模型,预测大客户离网风险,采取激励和挽留措施防止客户流失。可以使用相关分析找出选择了多个套餐的客户在套餐组合中的潜在规律,哪些套餐容易被客户同时选取,例如,选择了流量套餐的客户中大部分选择了彩铃业务,然后基于相关性的法则,对选择流量但是没有选择彩铃的客户进行交叉营销,向他们推销彩铃业务。 [2]
5. 研究
由于许多应用问题往往比超市购买问题更复杂,大量研究从不同的角度对关联规则做了扩展,将更多的因素集成到关联规则挖掘方法之中,以此丰富关联规则的应用领域,拓宽支持管理决策的范围。如考虑属性之间的类别层次关系,时态关系,多表挖掘等。近年来围绕关联规则的研究主要集中于两个方面,即扩展经典关联规则能够解决问题的范围,改善经典关联规则挖掘算法效率和规则兴趣性。
6. 相关性和区别
一个经常问的问题是,数据挖掘和OLAP到底有何不同。下面将会解释,他们是完全不同的工具,基于的技术也大相径庭。
OLAP是决策支持领域的一部分。传统的查询和报表工具是告诉你数据库中都有什么(what happened),OLAP则更进一步告诉你下一步会怎么样(What next)、和如果我采取这样的措施又会怎么样(What if)。用户首先建立一个假设,然后用OLAP检索数据库来验证这个假设是否正确。比如,一个分析师想找到什么原因导致了贷款拖欠,他可能先做一个初始的假定,认为低收入的人信用度也低,然后用OLAP来验证他这个假设。如果这个假设没有被证实,他可能去察看那些高负债的账户,如果还不行,他也许要把收入和负债一起考虑,一直进行下去,直到找到他想要的结果或放弃。
也就是说,OLAP分析师是建立一系列的假设,然后通过OLAP来证实或推翻这些假设来最终得到自己的结论。OLAP分析过程在本质上是一个演绎推理的过程。但是如果分析的变量达到几十或上百个,那么再用OLAP手动分析验证这些假设将是一件非常困难和痛苦的事情。
数据挖掘与OLAP不同的地方是,数据挖掘不是用于验证某个假定的模式(模型)的正确性,而是在数据库中自己寻找模型。他在本质上是一个归纳的过程。比如,一个用数据挖掘工具的分析师想找到引起贷款拖欠的风险因素。数据挖掘工具可能帮他找到高负债和低收入是引起这个问题的因素,甚至还可能发现一些分析师从来没有想过或试过的其他因素,比如年龄。
数据挖掘和OLAP具有一定的互补性。在利用数据挖掘出来的结论采取行动之前,你也许要验证一下如果采取这样的行动会给公司带来什么样的影响,那么OLAP工具能回答你的这些问题。
而且在知识发现的早期阶段,OLAP工具还有其他一些用途。可以帮你探索数据,找到哪些是对一个问题比较重要的变量,发现异常数据和互相影响的变量。这都能帮你更好的理解你的数据,加快知识发现的过程。
相关技术
数据挖掘利用了人工智能(AI)和统计分析的进步所带来的好处。这两门学科都致力于模式发现和预测。
数据挖掘不是为了替代传统的统计分析技术。相反,他是统计分析方法学的延伸和扩展。大多数的统计分析技术都基于完善的数学理论和高超的技巧,预测的准确度还是令人满意的,但对使用者的要求很高。而随着计算机计算能力的不断增强,我们有可能利用计算机强大的计算能力只通过相对简单和固定的方法完成同样的功能。
一些新兴的技术同样在知识发现领域取得了很好的效果,如神经元网络和决策树,在足够多的数据和计算能力下,他们几乎不用人的关照自动就能完成许多有价值的功能。
数据挖掘就是利用了统计和人工智能技术的应用程序,他把这些高深复杂的技术封装起来,使人们不用自己掌握这些技术也能完成同样的功能,并且更专注于自己所要解决的问题。
相关影响
使数据挖掘这件事情成为可能的关键一点是计算机性能价格比的巨大进步。在过去的几年里磁盘存储器的价格几乎降低了99%,这在很大程度上改变了企业界对数据收集和存储的态度。如果每兆的价格是¥10,那存放1TB的价格是¥10,000,000,但当每兆的价格降为1毛钱时,存储同样的数据只有¥100,000!
计算机计算能力价格的降低同样非常显著。每一代芯片的诞生都会把CPU的计算能力提高一大步。内存RAM也同样降价迅速,几年之内每兆内存的价格由几百块钱降到现在只要几块钱。通常PC都有64M内存,工作站达到了256M,拥有上G内存的服务器已经不是什么新鲜事了。
在单个CPU计算能力大幅提升的同时,基于多个CPU的并行系统也取得了很大的进步。目前几乎所有的服务器都支持多个CPU,这些SMP服务器簇甚至能让成百上千个CPU同时工作。
基于并行系统的数据库管理系统也给数据挖掘技术的应用带来了便利。如果你有一个庞大而复杂的数据挖掘问题要求通过访问数据库取得数据,那么效率最高的办法就是利用一个本地的并行数据库。
所有这些都为数据挖掘的实施扫清了道路,随着时间的延续,我们相信这条道路会越来越平坦。 [2]
【参考资料】百度百科-数据挖掘