大数据与数据挖掘

数据挖掘课程的目的第一页，共76页。什么是数据挖掘Wiki中的定义theanalysisstepofthe"KnowledgeDiscoveryinDatabases"process,orKDDAninterdisciplinarysubfieldofcomputerscience,isthecomputationalprocessofdiscoveringpatternsinlargedatasetsinvolvingmethodsattheintersectionofartificialintelligence,machinelearning,statistics,anddatabasesystems.

Theoverallgoalofthedataminingprocessistoextractinformationfromadatasetandtransformitintoanunderstandablestructureforfurtheruse.Asidefromtherawanalysisstep,itinvolvesdatabaseanddatamanagementaspects,datapre-processing,modelandinferenceconsiderations,interestingnessmetrics,complexityconsiderations,post-processingofdiscoveredstructures,visualization,andonlineupdating.2022/12/13数据库研究所2第二页，共76页。开设数据挖掘课程的目的技术发展的趋势的需要大数据和智能化是信息技术发展的新动力技术发展路径数据库->数据仓库->数据挖掘->大数据数据挖掘技术已经成为很多应用领域的基本支撑技术WEB数据分析电子商务生物信息学金融数据分析…2022/12/13数据库研究所3第三页，共76页。开设数据挖掘课程的目的数据分析类课程在计算机教学体系中的作用将逐渐增加数据挖掘、机器学习、…培养学生理论与应用相结合能力培养学生应用基本的方法，提高解决实际的系统能力数据挖掘课程的特点入门容易有深度应用实例多易于设计实验2022/12/13数据库研究所4第四页，共76页。复旦大学数据挖掘课程的设置复旦大学计算机科学技术学院基本情况学生情况120名本科生/年150名研究生/年教师情况教学科研教师：100名左右教学理念强调数据基础强调学生综合能力的培养强调学生创新能力培养复旦大学计算机科学技术学院基本情况主要研究方向媒体计算数据库与数据科学网络与信息安全智能信息处理人机接口和服务计算理论计算机科学软件工程与系统软件2022/12/13数据库研究所5第五页，共76页。复旦大学数据挖掘课程的设置总体目标掌握大规模数据挖掘与分析的基本流程掌握数据挖掘的基本算法掌握对实际数据集进行挖掘的系统能力算法设计挖掘算法的内涵参数设置结果评估…了解数据挖掘的主要应用方向为后续的课程做准备2022/12/13数据库研究所6第六页，共76页。复旦大学数据挖掘课程的设置2022/12/13数据库研究所7数据仓库与数据挖掘WEB数据管理和数据挖掘数据密集型计算文本数据挖掘…高级数据挖掘技术数据库系统机器学习生物信息学多媒体数据处理数据库新技术第七页，共76页。数据仓库与数据挖掘课程的教学目的掌握数据仓库数据挖掘原理、技术和方法，掌握建立数据挖掘应用系统的方法，了解相关前沿的研究。教学内容数据挖掘、数据仓库的基本概念数据仓库设计和应用数据挖掘的基本技术关联分析、分类分析、聚类分析、异常分析和演化分析等；联机分析处理OLAP技术；数据挖掘应用系统开发数据挖掘技术的新应用数据挖掘软件发展2022/12/13数据库研究所8第八页，共76页。高级数据挖掘课程的教学目的让学生掌握数据挖掘的基本概念、算法和高级技术；将这些概念、算法和技术应用于实际问题。教学内容分类算法，包括决策树(ID3,C4.5,SPRINT等)、基于规则的分类器(C4.5rules,RIPPLE等)、NaïveBayes分类器和贝叶斯网络、最近邻分类器(kNN,CondensedkNN,DANN等)、支持向量机(SVM)、Ensemble方法(如AdaBoost,Bagging,RainForest等)，以及模型选择(如MDL，RegularizationNetwork等)。2022/12/13数据库研究所9第九页，共76页。高级数据挖掘教学内容聚类分析划分型聚类算法，如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等)等主题具体内容逐步调整研讨是主要的授课方式2022/12/13数据库研究所10第十页，共76页。Web数据管理和数据挖掘本课程的教学目的了解大规模WEB数据（包括HTML数据、XML等类型数据）的管理与挖掘技术，及其在WEB领域中的应用，学会充分利用领域内的信息课程内容网络爬虫技术DNS解析、链接抽取、重复网页处理、…WEB搜索和信息检索文本预处理、向量空间模型、相关性反馈WEB数据挖掘相似性计算和聚类、文本分类、链接分析、…WEB数据挖掘应用社交网络分析、资源发现、…2022/12/13数据库研究所11第十一页，共76页。文本数据挖掘课程的教学目的了解大规模文本数据的处理和挖掘技术，及其在生物/医疗等文本数据分析中的应用课程内容文本预处理技术文本聚类技术基于本体的文本数据挖掘文本挖掘中的概率模型可视化技术生物/医疗文本数据挖掘2022/12/13数据库研究所12第十二页，共76页。数据密集型计算理论与实践课程的教学目的了解基于云计算平台或其他的新型分布式/并行计算平台上数据挖掘算法的实现技术及其应用课程内容分布式系统简介分布式文件系统并行编程基础Map/Reduce编程模型分布式图算法与PageRank聚类算法与MapReduce2022/12/13数据库研究所13分类算法与MapReduceNOSQL介绍 GPU通用编程基础CUDA介绍与调优社会媒体中典型应用信息检索中典型应用第十三页，共76页。主要参考文献JiaweiHan,etc.DataMiningConceptandTechniques,MaganKarfmannPublishersSoumenChakrabarti,Mining

theWEB-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等会议论文2022/12/13数据库研究所14第十四页，共76页。数据挖掘课程的主要内容第十五页，共76页。数据挖掘的理念数据挖掘是一个过程数据准备、挖掘、评估、参数调整、再挖掘、…数据挖掘是一个白盒操作挖掘结果的解释是一个重要操作数据挖掘是对数据的操作理解数据整理数据面向目标设计挖掘模式2022/12/13数据库研究所16第十六页，共76页。数据挖掘课程的主要内容先导课程数据库、概率统计数据挖掘的基本算法适用于本科生推荐教材JiaweiHan,JianPei,etc.DataMiningConceptandTechniques,MaganKarfmannPublishers高级数据挖掘技术适用于研究生适用于研究生面向特定领域的数据挖掘技术适用于本科生科创活动选题2022/12/13数据库研究所17第十七页，共76页。数据挖掘是一个过程数据清理数据集成数据库数据仓库知识任务相关的数据选择数据挖掘模式评估2022/12/13数据库研究所18第十八页，共76页。数据数据的类型各种类型的数据文本、序列、图片、视频特征抽取属性数据图、树结构数据数据的关联关系和数据内容理解数据的语义的体现的形式，明确数据挖掘的依据2022/12/13数据库研究所19第十九页，共76页。数据数据集的特点数据的稀疏性数据的分布数据的覆盖范围…2022/12/13数据库研究所20数据挖掘的结果和数据集有很大的关联挖掘之前需要了解数据第二十页，共76页。数据数据的相似性度量度量的三个性质非负性、对称性、三角不等式各种评价相似性的方法欧几里得距离、明考斯基距离、余弦相似度、皮尔森相关系数2022/12/13数据库研究所21评价数据的相似性是数据挖掘的基础第二十一页，共76页。数据仓库定义数据仓库是为支持管理决策建立的，面向主题的、集成的、随时间变化的、不可修改的数据集合主要内容ETL工具数据仓库建模联机分析2022/12/13数据库研究所22数据仓库为数据挖掘构建了数据基础，是大数据集成技术的雏形，联机分析是数据挖掘的一种第二十二页，共76页。数据源数据抽取加载数据仓库管理和监控工具ETL工具前端工具终端用户数据仓库数据仓库集市集市OLAP数据清洗关系数据库其它数据源元数据数据挖掘元数据数据获取数据存储信息传递数据仓库2022/12/13数据库研究所23第二十三页，共76页。数据抽取E针对多个数据源(来自不同设备，使用不同数据格式)数据清洁(编码矛盾，遗失值，重复值，规范化；组合多源记录数据，清除无用源数据等）；数据汇总包括最初的装载，数据仓库开始工作后的将变动的数据进行转换后存入正在工作的数据仓库数据转换T数据加载L数据仓库ETL（Extract、Transfer

、Load）2022/12/13数据库研究所24第二十四页，共76页。在一个给定时刻捕获的数据，即相关源数据在某个特定时刻的快照。(一般初始装载时使用)静态数据抽取修正/追加数据抽取延缓型数据抽取立即型数据抽取数据抽取技术抽取是实时的，当交易发生时就会在源数据库和文件中发生。通过交易日志捕获；从数据库触发器捕获；从源应用程序捕获。基于日期和时间标记捕获；通过文件比较捕获。数据仓库数据抽取将不同来源的数据放在一起2022/12/13数据库研究所25第二十五页，共76页。数据转换选择……转化汇总分离/合并选择从源系统得到的整个记录或部分记录（抽取过程）标准化，使字段对用户可用可理解；粒度多个系统中选中部分的合并操作常见的转换类型格式修正；字段解码；计算值和导出值；单个字段分离；信息合并；特征集合转化；度量单位转化；日期/时间转化；汇总；键重新构造等数据转换：根据转换规则进行转换和重新结构化（映射）数据仓库数据转换将统一不同格式的数据2022/12/13数据库研究所26第二十六页，共76页。数据仓库数据清洗不完整的数据可能来自收集数据时该数据值（属性）没有用、不考虑人员/硬件/软件故障噪声数据（不正确的数值）可能来自仪器设备产生错误数据数据输入时人为错误或计算机错误数据传输错误不一致数据可能来自不同的数据源数据质量是取得好的数据挖掘结果的基础2022/12/13数据库研究所27第二十七页，共76页。初始装载：第一次对所有的数据仓库表进行迁移增量装载：根据需要定期应用运行过程中发生的变化完全刷新：完全删除一个或多个表的内容，并重新装载新的数据数据仓库2022/12/13数据库研究所28第二十八页，共76页。数据仓库模式-雪花模型雪花模型是描述属性数据的候选模型2022/12/13数据库研究所29第二十九页，共76页。联机分析联机分析1993年，提出多维数据库和多维分析的概念（即OLAP），侧重于分析型应用用于区别于OLTP的操作型应用OLTP已不能满足用户对数据库查询分析的需要，SQL对大数据库进行的简单查询也不能满足用户分析的需求2022/12/13数据库研究所30第三十页，共76页。城市按季度时间、城市地区和商品类型三个维销售的数据计算机家庭娱乐南京上海北京天津Q1Q2Q3Q4电话空调商品类型季度销售额数据立方体2022/12/13数据库研究所31第三十一页，共76页。2022/12/13数据库研究所32数据立方体联机分析是数据挖掘的一种重要的形式第三十二页，共76页。数据准备数据裁剪和构造在保持原数据完整性的基础上，对这些数据进行归约化处理，以提高数据分析或数据挖掘的效果维归约选维：使用特征的一个子集降维：主成分分析PCA特征加权与筛选特征转换与构造数据压缩数值归约2022/12/13数据库研究所33构造合适的数据是取得好的数据挖掘结果的基础第三十三页，共76页。2022/12/13数据库研究所34关联规则项集X={x1,…,xk}找到满足最小支持度和置信度的规则

XY

支持度,s,事务包含XY的概率置信度,c,

包含X同时包含Y的条件概率Letsupmin=50%,confmin=50%Freq.Pat.:{A:3,B:3,D:4,E:3,AD:3}Associationrules:AD(60%,100%)DA(60%,75%)CustomerbuysdiaperCustomerbuysbothCustomerbuysbeerTransaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F第三十四页，共76页。关联规则关联规则的主要算法种类AprioriFP-growth模式的变种约束闭模式信息量的评估方法不同类型数据中的频繁模式序列图2022/12/13数据库研究所35减少频繁模式/规则的规模是关联规则技术应用的关键第三十五页，共76页。聚类分析2022/12/13数据库研究所36是根据最大化簇内的相似性、最小化簇间的相似性的原则将数据对象聚类或分组，所形成的每个簇可以看作一个数据对象类，用显式或隐式的方法描述它们第三十六页，共76页。基于划分的基于层次的基于密度的基于网格的基于模型的聚类算法K-meansK-medoids凝聚的分裂的DBSCANOPTICSSTINGCLIQUEStatisticsNeuralNetwork聚类分析2022/12/13数据库研究所37第三十七页，共76页。能够适用于大数据量(可伸缩性)能够处理不同类型数据(距离定义)能够处理高维数据能够发现任意形状的簇(结果特点)应用聚类算法需要考虑的因素聚类结果可解释、易使用具有处理噪声的能力聚类分析2022/12/13数据库研究所38第三十八页，共76页。2022/12/13数据库研究所39分类分析定义给定一个数据样本集D＝｛X1,X2,…,Xn｝，样本XiD，类的集合C＝｛C1,C2,……,Cm｝，分类是从数据样本集到类集合的映射f：DC，即数据集中的样本Xi分配到某个类Cj中，有Cj

＝｛Xi|f(Xi)=Cj，1≤i≤n，1≤j≤m，且XiD｝。即通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y，f又称分类模型第三十九页，共76页。分类分析b.测试(使用模型分类)阶段a.模型训练阶段构造分类器：2022/12/13数据库研究所40第四十页，共76页。分类分析分类算法决策树贝叶斯方法最近邻支持向量机神经网络……评估分类算法的要素预测的准确度计算复杂度模型描述的简洁性模型的可解释性避免过度拟合2022/12/13数据库研究所41第四十一页，共76页。2022/12/13数据库研究所异常检测异常一个数据集中往往包含一些特别的数据，其行为和模式与一般的数据不同，这些数据称为“异常”（‘小模式‘）异常检测发现数据集中明显不同于其他数据的对象的过程。即对“异常”数据的发现和分析42第四十二页，共76页。噪声异常“噪声”：定义在簇的基础上，是不隶属于任何簇的数据多数聚类算法具有一定的噪声处理能力，在一定程度上可以检测异常数据。但聚类定义的“噪声”和“异常”在概念上是有偏差的。“异常”：是不依赖于是否存在簇。聚类算法中具有处理噪声能力的出发点和目的是优化簇，在生成结果簇时，噪声是可以容忍或忽略的。异常、噪声如何定义异常？2022/12/13数据库研究所43第四十三页，共76页。2022/12/13数据库研究所异常检测异常检测的主要方法基于聚类的异常挖掘k-近邻方法基于统计的异常分析方法基于偏差的异常分析方法具体算法DB(pct,dmin)异常DnK异常k-distanceLOF44第四十四页，共76页。序列数据挖掘应用领域生物信息学金融数据分析电子商务信用卡分析主要的挖掘角度趋势变化序列模式挖掘循环变化非规则随机变化关联分析2022/12/13数据库研究所45第四十五页，共76页。可视化2022/12/13数据库研究所46可视化是评估挖掘结果的有效工具第四十六页，共76页。数据挖掘技术的应用领域第四十七页，共76页。商业数据挖掘“尿布与啤酒”的故事－－数据挖掘项目实施良好的数据积累明确的业务需求准备数据数据挖掘技术结果表达结果评价结果利用2022/12/13数据库研究所48第四十八页，共76页。信用卡分析

持卡人（去哪里消费优惠）－特约商户（有哪些消费者）客户信用等级评估（VIP、二八法则）客户利润分析（银行贡献度）客户消费行为分析客户消费异常行为分析……2022/12/13数据库研究所49第四十九页，共76页。2022/12/13数据库研究所50WEB数据挖掘面向网络用户行为的分析和网页内容的挖掘是WEB应用企业的核心技术关注点分析第五十页，共76页。社交网络挖掘基于社交网络的富媒体分析DBLP、微博社交网络上的信息传播模式分析2022/12/13数据库研究所51第五十一页，共76页。金融数据挖掘面向股票和期货价格趋势及其同相关因素关联关系的挖掘是程序化交易的核心技术2022/12/13数据库研究所52第五十二页，共76页。生物数据挖掘面向基因数据的挖掘是生物信息学的基础生物信息数据的类型基因序列、蛋白质相互作用网络、蛋白质三维结构、…2022/12/13数据库研究所53基因中能发现什么？转录结合变化？第五十三页，共76页。生物数据挖掘生物/医疗文本挖掘是现代医疗发展的主要支撑技术之一2022/12/13数据库研究所54第五十四页，共76页。医药分析面向海量分子结构的分析成为当前新药研制的主要手段其核心技术的对图模型描述的海量分子结构的模式分析2022/12/13数据库研究所55第五十五页，共76页。数据挖掘其他应用领域基于位置的服务智能交通桥梁监控节能分析…2022/12/13数据库研究所56第五十六页，共76页。数据挖掘技术的发展趋势第五十七页，共76页。数据挖掘领域的主要期刊和学术会议国际学术会议SIGKDD、ICDM、SIAMDM、PKDD、…SIGMOD、VLDB、ICDE、…国际学术期刊IEEEKDDDKDM…2022/12/13数据库研究所58第五十八页，共76页。从KDD2012看数据挖掘的发展方向主题#submissionSocial(Socialandinformationnetworks,graphandlinkmining,other)134Richdatatypes(TemporalandSpatial,text,Sequence,Unstructured,Other) 78Supervisedlearning(Classification,Regression,other) 76Unsupervisedlearning(Clustering,TopicDiscovery,Factorization,Visualization,ExploratoryAnalysis,Other) 75Bigdata(DistributedComputingCloud,GPU,MPI,others,EfficientAlgorithms,ScalableMethods,OptimizationTechniques) 55Web(Webmining,OnlineAdvertising,other) 49RuleandPatternMining 47Recommendersystems(collaborativefiltering,contentbasedmethods,hybridmethods,evaluationandmetrics,otheraspects) 412022/12/13数据库研究所59第五十九页，共76页。从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.)2022/12/13数据库研究所60第六十页，共76页。从KDD2012看数据挖掘的发展方向WEB和社交数据分析针对社交网络和WEB数据，结合社会学等方面的理论，研究其信息传播和用户行为模式的分析方法主要研究问题面向市场划分社交网络的聚类面向竞争的网络中的病毒传播模式分析2022/12/13数据库研究所61第六十一页，共76页。从KDD2012看数据挖掘的发展方向图挖掘基于新型计算平台研究超大规模图数据的管理与挖掘技术主要研究问题基于流计算模式的超大规模图数据分割算法最大团的有效计算方法基于图数据的用户行为分析方法大规模二部图的摘要分析2022/12/13数据库研究所62第六十二页，共76页。从KDD2012看数据挖掘的发展方向时空数据挖掘面向移动互联网、基于位置的服务等应用的需求，研究各种时空数据及相关数据的模式和关联关系的挖掘方法主要研究问题移动对象间关联关系的分析轨迹数据分析…2022/12/13数据库研究所63第六十三页，共76页。从KDD2012看数据挖掘的发展方向知识库通过对WEB数据、访问日志等数据源的数据进行分析，获取概念/实体间的关联关系(包括分类体系等)，以构建知识库知识库是数据语义的新的描述形式主要研究问题面向检索关键词的分类体系构造链接实体分析2022/12/13数据库研究所64第六十四页，共76页。从KDD2012看数据挖掘的发展方向模式挖掘研究各种新型模式的挖掘和评估技术主要研究问题面向流环境的动态模式挖掘模式的精简表示模糊覆盖Categorical属性的布尔表示2022/12/13数据库研究所65第六十五页，共76页。从KDD2012看数据挖掘的发展方向时间序列分析和事件挖掘针对大规模的时间序列数据研究其蕴含的事件挖掘方法主要研究问题时间序列数据的语义描述（事件分析）超大规模序列数据（包括GPS路径、通讯网络）的挖掘技术2022/12/13数据库研究所