数据挖掘DM1序论

DataMiningByYaoLi-xiuxyao@Outline:IntroductionDataPreprocessingConceptDescriptionAssociationRulesClassificationandRegressionClusteringChapter1IntroductionAI、ML、PR、DMFunction&Applicaton

定义1人工智能是一种使计算机能够思维，使机器具有智力的激动人心的新尝试。定义2人工智能是那些与人的思维、决策、问题求解和学习等有关活动的自动化。定义3人工智能是用计算模型研究智力行为。定义4人工智能是研究那些使理解、推理和行为成为可能的计算。人工智能的定义定义5人工智能是一种能够执行需要人的智能的创造性机器的技术。定义6人工智能研究如何使计算机做事让人过得更好。定义7人工智能是一门通过计算过程力图理解和模仿智能行为的学科。定义8人工智能是计算机科学中与智能行为的自动化有关的一个分支。其中，定义1和定义2涉及拟人思维；定义3和定义4与理性思维有关；定义5和定义6涉及拟人行为；定义7和定义8与拟人理性行为有关。人工智能的定义Russell&Norvig的定义SystemsthatthinklikehumansSystemsthatthinkrationallySystemsthatactlikehumansSystemsthatactrationally

人工智能是计算机科学的一个分支，是研究使计算机表现出人类智能的学科。它涉及逻辑学、计算机科学、脑科学、神经生理学、心理学、哲学、语言学、信息论、控制论等多个学科，是一门综合性的交叉和边缘学科。人工智能的定义

人工智能学科的诞生经历了漫长的历史过程。历史上一些伟大的科学家和思想家对此作出了巨大的贡献，为今天的人工智能研究作了长足和充分的准备。人工智能的诞生人工智能的诞生（1）由大前提和小前提推出结论。如‘凡金属(M)都能导电(P)’（大前提），‘铜(S)是金属(M)’（小前提），‘所以铜(S)能导电(P)’（结论）。演绎:从普遍性结论或一般性事理推导出个别性结论亚里士多德（Aristotle）（公元前384—322）古希腊伟大的哲学家、思想家，研究人类思维规律的鼻祖，为形式逻辑奠定了基础，提出了推理方法，给出了形式逻辑的一些基本定律，创造了三段论法。FrancisBacon（1561—1626）英国哲学家和自然科学家，系统提出了归纳法，成为和亚里士多德的演绎法相辅相成的思维法则。他强调了知识的重要作用，指出“知识就是力量”。人工智能的诞生（2）归纳：从个别性知识,引出一般性知识的推理,是由已知真的前提,引出可能真的结论

莱布尼茨（Leibnitz）（1646—1716）德国数学家和哲学家，提出了关于数理逻辑的思想，即把形式逻辑符号化，从而对人的思维进行运算和推理的思想。人工智能的诞生（3）-3,-2,5,(?),61,122-3-252461122他们的差是1，7，19，37，61，后五数的差是6，2*6，3*64*64

布尔（Boole）（1815—1864）英国数学家、逻辑学家。他的主要贡献是初步实现了莱布尼茨关于思维符号化和数学化的思想，提出了一种崭新的代数系统——布尔代数，凡是传统逻辑能处理的问题，布尔代数都能处理。符号逻辑

对于逻辑代数，布尔的方法是着重于外延逻辑，即类的逻辑。其中类或集合用x，y，z，…表示，而符号X，Y，Z，…则代表个体元素．用1表示万有类，用0表示空类或零类．他用xy表示两个集合的交[他称这个运算为选拔(election)]，即x与y所有共同元素的集合…

人工智能的诞生（4）歌德尔（Gödel）（1906—1978）美籍奥地利数理逻辑学家，他研究数理逻辑中的一些带根本性的问题，即不完全性定理和连续假设的相对协调性证明

，指出了把人的思维形式化和机械化的某些极限，在理论上证明了有些事情是机器做不到的。人工智能的诞生（5）图灵（Turing）（1912—1954）英国数学家。他于1936年提出了一种理想计算机的数学模型（图灵机）。现已公认，所有可计算函数都能用图灵机计算，这为电子计算机的构建提供了理论根据。

1950年，他还提出了著名的“图灵实验”，给智能的标准提供了明确的定义：

把人和计算机分两个房间，并且相互对话，如果作为人的一方不能判断对方是人还是计算机，那这台计算机就达到了人的智能。人工智能的诞生（6）莫克利（J.W.Mauchly）（1907—1980）美国数学家，和他的学生埃克特（J.P.Eckert），于1946年研制成功了世界上第一台通用电子数字计算机ENIAC。人工智能的诞生（7）

冯·诺依曼（JohnvonNeumann）（1903—1957)

美籍匈牙利数学家，提出了以二进制和程序存储控制为核心的通用电子数字计算机体系结构原理，奠定了现代电子计算机体系结构的基础。1946——EDVAC。人工智能的诞生（8）由五个基本部分组成：

1）运算器

2）控制器

3）存储器

4）输入装置

5）输出装置

麦卡锡（JohnMcCarthy），美国数学家、计算机科学家，“人工智能之父”。

人工智能的诞生（9）首次提出“人工智能”

（AI）概念；发明Lisp语言；研究不寻常的常识推理；发明“情景演算”。

1956年夏，在美国的达特茅斯学院，由McCarthy（斯坦福大学）、Minsky（哈佛大学）、Lochester（IBM公司）、Shannon（贝尔实验室）四人共同发起，邀请IBM公司的More、Samuel，MIT的Selfridge、Solomonff，还有Simon、Newell等人参加学术讨论班，在一起共同学习和探讨用机器模拟智能的各种问题。在会上，经McCarthy提议，决定使用“人工智能”一词来概括该研究方向。这次具有历史意义的会议标志着人工智能这个学科的正式诞生。人工智能的诞生（10）

1956年夏季，人类历史上第一次人工智能研讨会在美国的达特茅斯(Dartmouth)大学举行，标志着人工智能学科的诞生。

1969年召开了第一届国际人工智能联合会议(InternationalJointConferenceonAI,IJCAI),此后每两年召开一次。

1970年《人工智能》国际杂志(InternationalJournalofAI)创刊。这些对开展人工智能国际学术活动和交流、促进人工智能的研究和发展起到积极作用。人工智能的研究及应用领域

人工智能研究及应用领域很多，主要研究领域包括问题求解、机器学习、专家系统、模式识别、自动定理证明、自然语言理解等。

第1章人工智能概述

第2章确定性知识表示

第3章确定性推理

第4章搜索策略

第5章计算智能

第6章不确定性推理

第7章机器学习

第8章自然语言理解

第9章分布智能

第10章新型专家系统

机器学习

学习是人类智能的主要标志和获得知识的基本手段；要使机器象人一样拥有知识和智能，就必须使机器具有获得知识的能力。计算机获得知识的两种途径：直接获得；学习获得（机器学习）。学习是一个有特定目的的知识获取过程，其内部表现为新知识结构的不断建立和修改，而外部表现为性能的改善。

第1章引言

第2章概念学习和一般到特殊序

第3章决策树学习

第4章人工神经网络

第5章评估假设

第6章贝叶斯学习

第7章计算学习理论

第8章基于实例的学习

第9章遗传算法

第10章学习规则集合

第11章分析学习

第12章归纳和分析学习的结合

第13章增强学习周志华数据挖掘，机器学习和统计数据挖掘是在人工智能（AI）和统计分析基础上发展起来的，这两门学科都致力于模式发现和预测。数据挖掘不是为了替代传统的统计分析技术。相反，他是统计分析方法学的延伸和扩展。数据挖掘就是利用了统计和人工智能技术的应用程序，他把这些高深复杂的技术封装起来，使人们不用自己掌握这些技术也能完成同样的功能，并且更专注于自己所要解决的问题。WhyDataMining?TheExplosiveGrowthofData:fromterabytestopetabytesDatacollectionanddataavailabilityAutomateddatacollectiontools,databasesystems,Web,computerizedsocietyMajorsourcesofabundantdataBusiness:Web,e-commerce,transactions,stocks,…Science:Remotesensing,bioinformatics,scientificsimulation,…Societyandeveryone:news,digitalcameras,YouTubeWearedrowningindata,butstarvingforknowledge!

Majorreason:Thewidelyavailabilityofhugeamountsofdataandtheimminentneedforturningsuchdataintousefulinformationandknowledge.数据挖掘技术是1、必然：网络之后的下一个技术热点2、数据挖掘技术的动力：数据爆炸但知识贫乏3、数据挖掘技术的实现基础：计算机技术的发展WhyDataMining?一、数据挖掘的概念

二、数据挖掘技术的发展三、功能与应用四、DM的处理流程五、一些流行的数据挖掘软件

数据挖掘的定义

数据挖掘的历史虽然较短，但从20世纪90年代以来，它的发展速度很快，加之它是多学科综合的产物，目前还没有一个完整的定义，人们提出了多种数据挖掘的定义，例如：

SAS研究所（1997）：“在大量相关数据基础之上进行数据探索和建立相关模型的先进方法”。

Bhavani（1999）：“使用模式识别技术、统计和数学技术，在大量的数据中发现有意义的新关系、模式和趋势的过程”。关键词：大量数据挖掘的定义——韩家炜简单的说，DM就是从大量数据(Largeamountdata)里挖掘或提取有用的知识。广义的说，DM是一个从存储在Database/datawarehouse或其它介质里的大量数据中识别有效的、新颖的、有潜在价值的以及最终可理解的模式的非常规的过程。技术上的定义，DM就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。

Bigdata数据:Staticnumericdata：1，2，3…(Time)SeriesData(thedatarelatedtotimechange)

Stockanalysis,Bankaccount,Sensordataetc.BioinformaticsSpatialData(thedatarelatedtospatialorgeographicalinformation,GIS)RemoteSensing,CensusTextData(word,sentence,journaletc.)

Weblogmining,MachinetranslateMultimediaData(figure,image,hyper-text,soundetc.)

Content-basedImageRetrieval

一、数据挖掘的概念

二、数据挖掘技术的发展三、功能与应用四、DM的处理流程五、一些流行的数据挖掘软件

1、1989年，USADetroit,召开的11th国际人工智能联合会议的专题讨论会上，首次提出KDD的概念2、1995年在Canada蒙特利尔召开的第一届知识发现和数据挖掘国际学术会议，作为人们重新认识数据、认识存储、认识数据统计和分析的新的起点，唤来了知识发现和数据挖掘理论及应用研究的热潮。美国计算机学会（ACM）于当年提出了数据挖掘的概念时间会议名称会议地址August20.1989KDD-1989WorkshopDetroit,MI,USAJuly.31-Aug.11994KDD-1994WorkshopSeattle,WA,USAAugust20-21,1995ThefirstinternationalconferenceonKnowledgeDiscoveryandDataMining(KDD-95)Montreal,Canada.August2-4,1996TheSecondInternationalConferenceon

KnowledgeDiscoveryandDataMining(KDD-96)Portland,Oregon,USAAugust14-17,19973rdInternationalConferenceon

KnowledgeDiscoveryandDataMining(KDD-97)Newportbeach,California,USAAugust19984thInternationalConferenceon

KnowledgeDiscoveryandDataMining(KDD-98)NewYork,USA。。。。。。。。。August21-24,201117thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningSanDiego,CAAugust12-16,201218thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningBeijing,ChinaAugust9-10,201319thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningChicago,USAAugust24-27,201420thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningNewYork,USAAugust10-13,201521thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningSydney,Australia摘自/DataMining国际顶级会议ACMKDDcup

KDDCup是由美国计算机协会(ACM)组织的知识发现和数据挖掘国际竞赛；向Data

Mining领域的学术界和工业界开放，其目标是找出最有创新性和最有效的Data

Mining方法。

在每年的ACMSIGKDD会议举行之前的三四个月，组织者在网站上公布比赛任务，参赛者必须在指定日期前提交结果。经组织者评审后，在SIGKDD会议上公布比赛结果，并邀请优胜者作报告。竞赛题目通常都是当前各个学科中实际的热门数据挖掘问题，具有较高的挑战性。往年的題目和数据来源于经济、制药、生物、信息等领域。ACMKDDcupKDD-Cup2014,PredictfundingrequeststhatdeserveanA+KDD-Cup2013,author与paper的对应关系KDD-Cup2012,社交网络中的个性化推荐系统（ACM班）KDD-Cup2011,音乐评分预测KDD-Cup2010,Studentperformanceevaluation

KDD-Cup2009,FastScoringonaLargeDatabase

KDD-Cup2008,BreastcancerKDD-Cup2007,Consumerrecommendations……KDD-Cup1999,ComputernetworkintrusiondetectionKDD-Cup1998,DirectmarketingforprofitoptimizationKDD-Cup1997,Directmarketingforliftcurveoptimization

摘自/kddcup/index.phpConferencesACMSIGKDDInt.Conf.onKnowledgeDiscoveryinDatabasesandDataMining(KDD)SIAMDataMiningConf.(SDM)IEEEInt.Conf.onDataMining(ICDM)Conf.onPrinciplesandpracticesofKnowledgeDiscoveryandDataMining(PKDD)Pacific-AsiaConf.onKnowledgeDiscoveryandDataMining(PAKDD)数据挖掘的其他国际会议一、数据挖掘的概念

二、数据挖掘技术的发展三、功能与应用四、DM的处理流程五、一些流行的数据挖掘软件

1.面向属性的归纳学习归纳学习旨在从大量的经验数据中归纳抽取出一般的规则和模式。面向属性的归纳学习通过归纳学习，使得属性域取值的抽象程度提高，从而得到较精练的数据集合，大大提高了规则的学习效率。可用于预处理阶段的属性约简。也可用于规则的提取。2.关联分析就是从给定的数据集发现频繁出现的项集模式知识，即发现各属性之间的关联关系并用关联规则描述出来

不用很绝对的数字，只是提供一种大概的规则——多数准则

常见表现形式:orWhere,areattribute-valuepares.ande.g.1

Givenarelationaldatabase,adataminingsystemmayfindassociationrules:

最流行的就是货篮分析（啤酒/尿布）主要功能：市场定位消费者分析预测销售趋势优化营销策略（根据居民消费习惯采取相应的策略）价格分析分析库存需求建立合理的物流供应链3.分类、回归Classification/Regression:

根据一系列已知样本（训练样本），用各种算法训练产生一套能描述或区别数据的类别或概念的模型，并能够根据这个模型或函数来预测未知类别样本（测试样本）的分类结果。

e.g.Facerecognition,fingerprintrecognition两者的区别可视为预报的目标不同Classification：离散型的Regression:数量型的，连续型的一个是类别，一个是目标值，而类别一般是依据目标值来分类的。常见算法：PCA、DT、ANN、BN、SVM

最经典的数据挖掘方法：模式分类图像分析工业诊断金融数据分析生物数据信息……4.聚类分析unsupervisedclassification(analyzesdataobjectsunknowingabouttheclasslabel)

根据属性标识对样本聚类，从数据集中找出相似的数据并组成不同的组。聚类的准则：聚类后，同一类之间的样本具有很强的相似性而非同类之间的样本具有很强的非相似性。相似性的度量：一般用的是距离。之后还有人根据具体数据格式加上别的一些度量方式，如对称性。MeasurementofSimilarity1)distance2)distance+otherother:symmetry,weight,etc.Distance1、MenkowskyDistance

2、EuclideanDistance3、WeightedDistance4、MahalanobisDistance5、HamingDistance(ForthedatawithBooleanvariable)6、GeodesicDistance

测地距离当数据集中样本分布在高维空间且满足某一特定曲面时，欧氏距离则不能反映样本间的真实距离。此时，应该将样本分布的形状信息考虑在内来衡量样本间的相似性。测地距离的基本思想：对于近邻样本，欧氏距离近似反映样本间沿数据分布曲面间的距离；对于相隔较远的样本，样本间的距离为样本分布曲面上连接两样本点间的最短空间曲线的长度。J.B.Tenenbaum,V.D.Silva,andJ.C.Langford,Aglobalgeometricframeworkfornonlineardimensionalityreduction,Science,2000,vol.290:2319-23235.序列分析、趋势分析

对随时间变化的数据对象的变化规律和趋势进行建模描述，可根据前一段时间的运动预测下一个时间点的状态。解决的问题一般可以分为下面两类：总结数据的序列或者变化趋势；（股票/期货交易，网页点击顺序记录）检测数据随时间变化的变化；（自来水厂用水量的日、周、月、年等周期变化）流程图预测存/贷款趋势预测股票趋势分析客户的要求、信誉客户类型分析客户流失报警优化存/贷款利率识别欺诈行为

序列分析的应用对金融数据的自身发展规律进行的预测，对参与其中的可客户有用对与客户行为有关的数据记录进行建模和预测，对经营者有用Web挖掘6.离异点分析：噪声还是例外

是实际生活中的反常行为的写照。包括：噪声(删除)：实验错误…

特例(格外关注，建立案例库）：工业生产中的特例…

离异点的检测被广泛用于调查商业欺诈，偷税漏税等行为一、数据挖掘的概念

二、数据挖掘技术的发展三、功能与应用四、DM的处理流程五、一些流行的数据挖掘软件

1.待发掘的目标(例如提高证券交易的收入)Target(howtogetmoremoneyfromstockmarket)2.发掘的工具(例如统计方法)Tools(statisticmethods)4.挖掘结果的使用(例如明天我要..)Application(TomorrowIwill..)

3.发掘结果的评估(例如这个结果看来…)Evaluation(thisresultseemstobe…)4.1数据挖掘环境4.2数据挖掘流程图

同时考虑可靠性、繁简程度、可理解性等数据挖掘的主要步骤：数据准备。（问题的提出和数据的选取）数据预处理，包括：数据填充。针对不完备信息系统。数据清洗。清除数据噪声和与挖掘主题明显无关的数据。数据集成。将来自多数据源中的相关数据组合到一起。数据转换。将数据转换为易于进行数据挖掘的数据存储形式。数据消减。缩小所挖掘数据的规模，但却不影响最终的结果。包括：数据立方、维数消减、数据压缩、数据块消减、离散化与概念层次生成等。数据挖掘(datamining)。算法设计与知识获取，利用智能方法挖掘数据模式或规律知识。模式评估(patternevaluation)。根据一定评估标准，从挖掘结果筛选出有意义的模式知识。知识表示(knowledgepresentation)。利用可视化和知识表达技术，向用户展示所挖掘出的相关知识一、数据挖掘的概念

二、数据挖掘技术的发展三、功能与应用四、DM的处理流程五、一些流行的数据挖掘算法与软件

2006年ICDM会议选出了10大经典算法

Classification#1.C4.5:Quinlan,J.R.C4.5:ProgramsforMachineLearning.MorganKaufmann.,1993.#2.CART:L.Breiman,J.Friedman,R.Olshen,andC.Stone.ClassificationandRegressionTrees.Wadsworth,1984.#3.KNearestNeighbours(kNN):Hastie,T.andTibshirani,R.1996.DiscriminantAdaptiveNearestNeighborClassification.TPAMI.18(6)#4.NaiveBayes：

Hand,D.J.,Yu,K.,2001.Idiot'sBayes:NotSoStupidAfterAll?Internat.Statist.Rev.69,385-398.StatisticalLearning#5.SVM:Vapnik,V.N.1995.TheNatureofStatisticalLearningTheory.Springer-Verlag.#6.EM:McLachlan,G.andPeel,D.(2000).FiniteMixtureModels.J.Wiley,NewYork.AssociationAnalysis#7.Apriori:RakeshAgrawalandRamakrishnanSrikant.FastAlgorithmsforMiningAssociationRules.InVLDB'94.#8.FP-Tree:Han,J.,Pei,J.,andYin,Y.2000.Miningfrequentpatternswithoutcandidategeneration.InSIGMOD'00.一些流行的算法与软件

LinkMining#9.PageRank:Brin,S.andPage,L.1998.Theanatomyofalarge-scalehypertextualWebsearchengine.InWWW-7,1998.#10.HITS:Kleinberg,J.M.1998.Authoritativesourcesinahyperlinkedenvironment.SODA,1998.Clustering#11.K-Means:MacQueen,J.B.,Somemethodsforclassificationandanalysisofmultivariateobservations,inProc.5thBerkeleySymp.MathematicalStatisticsandProbability,1967.#12.BIRCH:Zhang,T.,Ramakrishnan,R.,andLivny,M.1996.BIRCH:anefficientdataclusteringmethodforverylargedatabases.InSIGMOD'96.BaggingandBoosting#13.AdaBoost:Freund,Y.andSchapire,R.E.1997.Adecision-theoreticgeneralizationofon-linelearningandanapplicationtoboosting.J.Comput.Syst.Sci.55,1(Aug.1997),119-139.一些流行的算法与软件

SequentialPatterns#14.GSP:Srikant,R.andAgrawal,R.1996.MiningSequentialPatterns:GeneralizationsandPerformanceImprovements.InProceedingsofthe5thInternationalConferenceonExtendingDatabaseTechnology,1996.#15.PrefixSpan:J.Pei,J.Han,B.Mortazavi-Asl,H.Pinto,Q.Chen,U.DayalandM-C.Hsu.PrefixSpan:MiningSequentialPatternsEfficientlybyPrefix-ProjectedPatternGrowth.InICDE'01.IntegratedMining#16.CBA:Liu,B.,Hsu,W.andMa,Y.M.Integratingclassificationandassociationrulemining.KDD-98.RoughSets#17.Findingreduct:ZdzislawPawlak,RoughSets:TheoreticalAspectsofReasoningaboutData,KluwerAcademicPublishers,Norwell,MA,1992GraphMining#18.gSpan:Yan,X.andHan,J.2002.gSpan:Graph-BasedSubstructurePatternMining.InICDM'02.一些流行的算法与软件

#1:C4.5(61votes)#2:K-Means(60votes)#3:SVM(58votes)#4:Apriori(52votes)#5:EM(48votes)#6:PageRank(46votes)#7:AdaBoost(45votes)#7:kNN(45votes)#7:NaiveBayes(45votes)#10