大数据与数据挖掘.ppt

数据挖掘课程教学研讨,数据挖掘课程的目的,什么是数据挖掘,Wiki中的定义theanalysisstepoftheKnowledgeDiscoveryinDatabasesprocess,orKDDAninterdisciplinarysubfieldofcomputerscience,isthecomputationalprocessofdiscoveringpatternsinlargedatasetsinvolvingmethodsattheintersectionofartificialintelligence,machinelearning,statistics,anddatabasesystems.Theoverallgoalofthedataminingprocessistoextractinformationfromadatasetandtransformitintoanunderstandablestructureforfurtheruse.Asidefromtherawanalysisstep,itinvolvesdatabaseanddatamanagementaspects,datapre-processing,modelandinferenceconsiderations,interestingnessmetrics,complexityconsiderations,post-processingofdiscoveredstructures,visualization,andonlineupdating.,2020/6/3,数据库研究所,3,开设数据挖掘课程的目的,技术发展的趋势的需要大数据和智能化是信息技术发展的新动力技术发展路径数据库-数据仓库-数据挖掘-大数据数据挖掘技术已经成为很多应用领域的基本支撑技术WEB数据分析电子商务生物信息学金融数据分析,2020/6/3,数据库研究所,4,开设数据挖掘课程的目的,数据分析类课程在计算机教学体系中的作用将逐渐增加数据挖掘、机器学习、培养学生理论与应用相结合能力培养学生应用基本的方法，提高解决实际的系统能力数据挖掘课程的特点入门容易有深度应用实例多易于设计实验,2020/6/3,数据库研究所,5,复旦大学数据挖掘课程的设置,复旦大学计算机科学技术学院基本情况学生情况120名本科生/年150名研究生/年教师情况教学科研教师：100名左右教学理念强调数据基础强调学生综合能力的培养强调学生创新能力培养,复旦大学计算机科学技术学院基本情况主要研究方向媒体计算数据库与数据科学网络与信息安全智能信息处理人机接口和服务计算理论计算机科学软件工程与系统软件,2020/6/3,数据库研究所,6,复旦大学数据挖掘课程的设置,总体目标掌握大规模数据挖掘与分析的基本流程掌握数据挖掘的基本算法掌握对实际数据集进行挖掘的系统能力算法设计挖掘算法的内涵参数设置结果评估了解数据挖掘的主要应用方向为后续的课程做准备,2020/6/3,数据库研究所,7,复旦大学数据挖掘课程的设置,2020/6/3,数据库研究所,8,数据仓库与数据挖掘,WEB数据管理和数据挖掘,数据密集型计算,文本数据挖掘,高级数据挖掘技术,数据库系统,机器学习,生物信息学,多媒体数据处理,数据库新技术,数据仓库与数据挖掘,课程的教学目的掌握数据仓库数据挖掘原理、技术和方法，掌握建立数据挖掘应用系统的方法，了解相关前沿的研究。教学内容数据挖掘、数据仓库的基本概念数据仓库设计和应用数据挖掘的基本技术关联分析、分类分析、聚类分析、异常分析和演化分析等；联机分析处理OLAP技术；数据挖掘应用系统开发数据挖掘技术的新应用数据挖掘软件发展,2020/6/3,数据库研究所,9,高级数据挖掘,课程的教学目的让学生掌握数据挖掘的基本概念、算法和高级技术；将这些概念、算法和技术应用于实际问题。教学内容分类算法，包括决策树(ID3,C4.5,SPRINT等)、基于规则的分类器(C4.5rules,RIPPLE等)、NaveBayes分类器和贝叶斯网络、最近邻分类器(kNN,CondensedkNN,DANN等)、支持向量机(SVM)、Ensemble方法(如AdaBoost,Bagging,RainForest等)，以及模型选择(如MDL，RegularizationNetwork等)。,2020/6/3,数据库研究所,10,高级数据挖掘,教学内容聚类分析划分型聚类算法，如K-means等层次型聚类算法，如Singlelink,completelink,Ward方法等及基于模型的聚类如EM算法；基于密度的聚类算法如DBSCAN其他高级聚类算法，如Clique,CURE,CHAMELEON,BIRCH等关联分析，Apriori算法、DHP、FP-growth，以及频繁序列挖掘、图挖掘等,教学内容数据挖掘应用异常检测、数据流挖掘、Web挖掘(PageRank,HITS和Spam,OpinionMining)、社会网络分析(Blog、Tag分析等)、数据挖掘和隐私保护、文本挖掘(PLSA,概率主题模型等)、降维技术(SVD,FastMap,LSH等)和特征选择(基于互信息量的方法、Relief等)等主题具体内容逐步调整研讨是主要的授课方式,2020/6/3,数据库研究所,11,Web数据管理和数据挖掘,本课程的教学目的了解大规模WEB数据（包括HTML数据、XML等类型数据）的管理与挖掘技术，及其在WEB领域中的应用，学会充分利用领域内的信息课程内容网络爬虫技术DNS解析、链接抽取、重复网页处理、WEB搜索和信息检索文本预处理、向量空间模型、相关性反馈WEB数据挖掘相似性计算和聚类、文本分类、链接分析、WEB数据挖掘应用社交网络分析、资源发现、,2020/6/3,数据库研究所,12,文本数据挖掘,课程的教学目的了解大规模文本数据的处理和挖掘技术，及其在生物/医疗等文本数据分析中的应用课程内容文本预处理技术文本聚类技术基于本体的文本数据挖掘文本挖掘中的概率模型可视化技术生物/医疗文本数据挖掘,2020/6/3,数据库研究所,13,数据密集型计算理论与实践,课程的教学目的了解基于云计算平台或其他的新型分布式/并行计算平台上数据挖掘算法的实现技术及其应用课程内容,分布式系统简介分布式文件系统并行编程基础Map/Reduce编程模型分布式图算法与PageRank聚类算法与MapReduce,2020/6/3,数据库研究所,14,分类算法与MapReduceNOSQL介绍GPU通用编程基础CUDA介绍与调优社会媒体中典型应用信息检索中典型应用,主要参考文献,JiaweiHan,etc.DataMiningConceptandTechniques,MaganKarfmannPublishersSoumenChakrabarti,MiningtheWEB-discoveringknowledgefromhypertextdata,MaganKarfmannPublishers朱扬勇等，数据挖掘技术及其应用Pang-NingTan,M.Steinbach,andV.Kumar.IntroductiontoDataMining(影印版),人民邮电出版社,2006.1.IanWitten,andE.Frank.DataMining:PracticalMachineLearningToolsandTechniques(影印版,第2版),机械工业出版社,2005.9.DavidHand,H.Mannila,andP.Smyth.PrinciplesofDataMining,机械工业出版社,2003.4.T.Hastie,R.Tibshirani,andJ.Friedman,TheElementsofStatisticalLearning:DataMining,Inference,andPrediction,Springer-Verlag,2001DataandXML,MorganKaufmanPublishers,20006.KDD,VLDB,SIGMOD,ICDM,SDM,ICML等会议论文,2020/6/3,数据库研究所,15,数据挖掘课程的主要内容,数据挖掘的理念,数据挖掘是一个过程数据准备、挖掘、评估、参数调整、再挖掘、数据挖掘是一个白盒操作挖掘结果的解释是一个重要操作数据挖掘是对数据的操作理解数据整理数据面向目标设计挖掘模式,2020/6/3,数据库研究所,17,数据挖掘课程的主要内容,先导课程数据库、概率统计数据挖掘的基本算法适用于本科生推荐教材JiaweiHan,JianPei,etc.DataMiningConceptandTechniques,MaganKarfmannPublishers,高级数据挖掘技术适用于研究生适用于研究生面向特定领域的数据挖掘技术适用于本科生科创活动选题,2020/6/3,数据库研究所,18,数据挖掘是一个过程,数据清理,数据集成,数据库,数据仓库,知识,任务相关的数据,选择,数据挖掘,模式评估,2020/6/3,数据库研究所,19,数据,数据的类型各种类型的数据文本、序列、图片、视频特征抽取属性数据图、树结构数据数据的关联关系和数据内容理解数据的语义的体现的形式，明确数据挖掘的依据,2020/6/3,数据库研究所,20,数据,数据集的特点数据的稀疏性数据的分布数据的覆盖范围,2020/6/3,数据库研究所,21,数据挖掘的结果和数据集有很大的关联挖掘之前需要了解数据,数据,数据的相似性度量度量的三个性质非负性、对称性、三角不等式各种评价相似性的方法欧几里得距离、明考斯基距离、余弦相似度、皮尔森相关系数,2020/6/3,数据库研究所,22,评价数据的相似性是数据挖掘的基础,数据仓库,定义数据仓库是为支持管理决策建立的，面向主题的、集成的、随时间变化的、不可修改的数据集合主要内容ETL工具数据仓库建模联机分析,2020/6/3,数据库研究所,23,数据仓库为数据挖掘构建了数据基础，是大数据集成技术的雏形，联机分析是数据挖掘的一种,数据仓库,2020/6/3,数据库研究所,24,数据抽取E,针对多个数据源(来自不同设备，使用不同数据格式),数据清洁(编码矛盾，遗失值，重复值，规范化；组合多源记录数据，清除无用源数据等）；数据汇总,包括最初的装载，数据仓库开始工作后的将变动的数据进行转换后存入正在工作的数据仓库,数据转换T,数据加载L,数据仓库,ETL（Extract、Transfer、Load）,2020/6/3,数据库研究所,25,在一个给定时刻捕获的数据，即相关源数据在某个特定时刻的快照。(一般初始装载时使用),静态数据抽取,修正/追加数据抽取,延缓型数据抽取,立即型数据抽取,数据抽取技术,抽取是实时的，当交易发生时就会在源数据库和文件中发生。通过交易日志捕获；从数据库触发器捕获；从源应用程序捕获。,基于日期和时间标记捕获；通过文件比较捕获。,数据仓库,数据抽取将不同来源的数据放在一起,2020/6/3,数据库研究所,26,数据转换,选择,转化汇总,分离/合并,选择从源系统得到的整个记录或部分记录（抽取过程）,标准化，使字段对用户可用可理解；粒度,多个系统中选中部分的合并操作,常见的转换类型格式修正；字段解码；计算值和导出值；单个字段分离；信息合并；特征集合转化；度量单位转化；日期/时间转化；汇总；键重新构造等,数据转换：根据转换规则进行转换和重新结构化（映射）,数据仓库,数据转换将统一不同格式的数据,2020/6/3,数据库研究所,27,数据仓库,数据清洗不完整的数据可能来自收集数据时该数据值（属性）没有用、不考虑人员/硬件/软件故障噪声数据（不正确的数值）可能来自仪器设备产生错误数据数据输入时人为错误或计算机错误数据传输错误不一致数据可能来自不同的数据源,数据质量是取得好的数据挖掘结果的基础,2020/6/3,数据库研究所,28,初始装载：第一次对所有的数据仓库表进行迁移,增量装载：根据需要定期应用运行过程中发生的变化,完全刷新：完全删除一个或多个表的内容，并重新装载新的数据,数据仓库,2020/6/3,数据库研究所,29,数据仓库模式-雪花模型,雪花模型是描述属性数据的候选模型,2020/6/3,数据库研究所,30,联机分析,联机分析1993年，E.F.Codd提出多维数据库和多维分析的概念（即OLAP），侧重于分析型应用用于区别于OLTP的操作型应用OLTP已不能满足用户对数据库查询分析的需要，SQL对大数据库进行的简单查询也不能满足用户分析的需求,2020/6/3,数据库研究所,31,数据立方体,2020/6/3,数据库研究所,32,2020/6/3,数据库研究所,33,数据立方体,联机分析是数据挖掘的一种重要的形式,数据准备,数据裁剪和构造在保持原数据完整性的基础上，对这些数据进行归约化处理，以提高数据分析或数据挖掘的效果维归约选维：使用特征的一个子集降维：主成分分析PCA特征加权与筛选特征转换与构造数据压缩数值归约,2020/6/3,数据库研究所,34,构造合适的数据是取得好的数据挖掘结果的基础,2020/6/3,数据库研究所,35,关联规则,项集X=x1,xk找到满足最小支持度和置信度的规则XY支持度,s,事务包含XY的概率置信度,c,包含X同时包含Y的条件概率,Letsupmin=50%,confmin=50%Freq.Pat.:A:3,B:3,D:4,E:3,AD:3Associationrules:AD(60%,100%)DA(60%,75%),关联规则,关联规则的主要算法种类AprioriFP-growth模式的变种约束闭模式信息量的评估方法不同类型数据中的频繁模式序列图,2020/6/3,数据库研究所,36,减少频繁模式/规则的规模是关联规则技术应用的关键,聚类分析,2020/6/3,数据库研究所,37,是根据最大化簇内的相似性、最小化簇间的相似性的原则将数据对象聚类或分组，所形成的每个簇可以看作一个数据对象类，用显式或隐式的方法描述它们,基于划分的,基于层次的,基于密度的,基于网格的,基于模型的,聚类算法,K-means,K-medoids,凝聚的,分裂的,DBSCAN,OPTICS,STING,CLIQUE,Statistics,NeuralNetwork,聚类分析,2020/6/3,数据库研究所,38,能够适用于大数据量(可伸缩性),能够处理不同类型数据(距离定义),能够处理高维数据,能够发现任意形状的簇(结果特点),应用聚类算法需要考虑的因素,聚类结果可解释、易使用,具有处理噪声的能力,聚类分析,2020/6/3,数据库研究所,39,2020/6/3,数据库研究所,40,分类分析,定义给定一个数据样本集DX1,X2,Xn，样本XiD，类的集合CC1,C2,Cm，分类是从数据样本集到类集合的映射f：DC，即数据集中的样本Xi分配到某个类Cj中，有CjXi|f(Xi)=Cj，1in，1jm，且XiD。即通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y，f又称分类模型,分类分析,2020/6/3,数据库研究所,41,分类分析,分类算法决策树贝叶斯方法最近邻支持向量机神经网络,评估分类算法的要素预测的准确度计算复杂度模型描述的简洁性模型的可解释性避免过度拟合,2020/6/3,数据库研究所,42,2020/6/3,数据库研究所,异常检测,异常一个数据集中往往包含一些特别的数据，其行为和模式与一般的数据不同，这些数据称为“异常”（小模式）异常检测发现数据集中明显不同于其他数据的对象的过程。即对“异常”数据的发现和分析,43,异常、噪声,如何定义异常？,2020/6/3,数据库研究所,44,2020/6/3,数据库研究所,异常检测,异常检测的主要方法基于聚类的异常挖掘k-近邻方法基于统计的异常分析方法基于偏差的异常分析方法具体算法DB(pct,dmin)异常DnK异常k-distanceLOF,45,序列数据挖掘,应用领域生物信息学金融数据分析电子商务信用卡分析,主要的挖掘角度趋势变化序列模式挖掘循环变化非规则随机变化关联分析,2020/6/3,数据库研究所,46,可视化,2020/6/3,数据库研究所,47,可视化是评估挖掘结果的有效工具,数据挖掘技术的应用领域,商业数据挖掘,“尿布与啤酒”的故事数据挖掘项目实施良好的数据积累明确的业务需求准备数据数据挖掘技术结果表达结果评价结果利用,2020/6/3,数据库研究所,49,信用卡分析,持卡人（去哪里消费优惠）特约商户（有哪些消费者）客户信用等级评估（VIP、二八法则）客户利润分析（银行贡献度）客户消费行为分析客户消费异常行为分析,2020/6/3,数据库研究所,50,2020/6/3,数据库研究所,51,WEB数据挖掘,面向网络用户行为的分析和网页内容的挖掘是WEB应用企业的核心技术,关注点分析,社交网络挖掘,基于社交网络的富媒体分析DBLP、微博社交网络上的信息传播模式分析,2020/6/3,数据库研究所,52,金融数据挖掘,面向股票和期货价格趋势及其同相关因素关联关系的挖掘是程序化交易的核心技术,2020/6/3,数据库研究所,53,生物数据挖掘,面向基因数据的挖掘是生物信息学的基础生物信息数据的类型基因序列、蛋白质相互作用网络、蛋白质三维结构、,2020/6/3,数据库研究所,54,基因中能发现什么？转录结合变化？,生物数据挖掘,生物/医疗文本挖掘是现代医疗发展的主要支撑技术之一,2020/6/3,数据库研究所,55,医药分析,面向海量分子结构的分析成为当前新药研制的主要手段其核心技术的对图模型描述的海量分子结构的模式分析,2020/6/3,数据库研究所,56,数据挖掘其他应用领域,基于位置的服务智能交通桥梁监控节能分析,2020/6/3,数据库研究所,57,数据挖掘技术的发展趋势,数据挖掘领域的主要期刊和学术会议,国际学术会议SIGKDD、ICDM、SIAMDM、PKDD、SIGMOD、VLDB、ICDE、国际学术期刊IEEEKDDDKDM,2020/6/3,数据库研究所,59,从KDD2012看数据挖掘的发展方向,2020/6/3,数据库研究所,60,从KDD2012看数据挖掘的发展方向,BestpaperT.Rakthanmanon,B.Campana,A.Mueen,G.Batista,B.Westover,Q.Zhu,J.Zakaria,E.Keogh.SearchingandMiningTrillionsofTimeSeriesSubsequencesunderDynamicTimeWarping.(UCR)BestStudentpaperY.Sun,B.Norick,J.Han,X.Yan,P.Yu,X.Yu.IntegratingMeta-PathSelectionwithUserGuidedObjectClusteringinHeterogeneousInformationNetworks.(UIUC)Q.Ding,N.Katenka,P.Barford,E.Kolaczyk,MarkCrovella.Intrusionas(Anti)socialCommunication:CharacterizationandDetection.(BostonU.),2020/6/3,数据库研究所,61,从KDD2012看数据挖掘的发展方向,WEB和社交数据分析针对社交网络和WEB数据，结合社会学等方面的理论，研究其信息传播和用户行为模式的分析方法主要研究问题面向市场划分社交网络的聚类面向竞争的网络中的病毒传播模式分析,2020/6/3,数据库研究所,62,从KDD2012看数据挖掘的发展方向,图挖掘基于新型计算平台研究超大规模图数据的管理与挖掘技术主要研究问题基于流计算模式的超大规模图数据分割算法最大团的有效计算方法基于图数据的用户行为分析方法大规模二部图的摘要分析,2020/6/3,数据库研究所,63,从KDD2012看数据挖掘的发展方向,时空数据挖掘面向移动互联网、基于位置的服务等应用的需求，研究各种时空数据及相关数据的模式和关联关系的挖掘方法主要研究问题移动对象间关联关系的分析轨迹数据分析,2020/6/3,数据库研究所,64,从KDD2012看数据挖掘的发展方向,知识库通过对WEB数据、访问日志等数据源的数据进行分析，获取概念/实体间的关联关系(包括分类体系等)，以构建知识库知识库是数据语义的新的描述形式主要研究问题面向检索关键词的分类体系构造链接实体分析,2020/6/3,数据库研究所,65,从KDD2012看数据挖掘的发展方向,模式挖掘研究各种新型模式的挖掘和评估技术主要研究问题面向流环境的动态模式挖掘模式的精简表示模糊覆盖Categorical属性的布尔表示,2020/6/3,数据库研究所,66,从KDD2012看数据挖掘的发展方向,时间序列分析和事件挖掘针对大规模的时间序列数据研究其蕴含的事件挖掘方法主要研究问题时间序列数据的语义描述（事件分析）超大规模序列数据（包括GPS路径、通讯网络）的挖掘技术,2020/6/3,数据库研究所,67,不确定数据（Uncertaindata）挖掘,不确定数据产生的原因信息集成数据采集封闭世界假设主要挑战中间结果的规模过于庞大主要研究方向频繁模式挖掘不确定