数据挖掘概念与技术课件

数据挖掘：概念与技数据挖掘：概念与技术术Jiawei Han and Micheline Kamber著著Monrgan Kaufmann Publishers Inc.范明范明 孟小峰等孟小峰等译译机械工机械工业业出版社出版社8/3/20241a8/3/20242a8/3/20243a第第1章章 引言引言英文幻灯片制作：英文幻灯片制作：Jiawei Han中文幻灯片中文幻灯片编译编译：范明：范明8/3/20244a第一章第一章 引引论论n动动机：机：为为什么要数据挖掘什么要数据挖掘?n什么是数据挖掘什么是数据挖掘?n数据挖掘：在什么数据上数据挖掘：在什么数据上进进行行?n数据挖掘功能数据挖掘功能n所有的模式都是有趣的所有的模式都是有趣的吗吗?n数据挖掘系数据挖掘系统统分分类类 n数据挖掘的主要数据挖掘的主要问题问题8/3/20245a动动机机:需要是需要是发发明之母明之母n数据爆炸数据爆炸问题问题n自自动动的数据收集工具和成熟的数据的数据收集工具和成熟的数据库库技技术导术导致大量数据致大量数据存放在数据存放在数据库库,数据数据仓库仓库,和其它信息存和其它信息存储储中中n我我们们正被数据淹没正被数据淹没,但却缺乏知但却缺乏知识识n解决解决办办法法:数据数据仓库仓库与数据挖掘与数据挖掘n数据数据仓库仓库与与联联机分析机分析处处理理(OLAP)n从大型数据从大型数据库库的数据中提取有趣的知的数据中提取有趣的知识识(规则规则,规规律性律性,模模式式,限制等限制等)8/3/20246a数据数据处处理技理技术术的演的演进进n1960s:n数据收集数据收集,数据数据库创库创建建,IMS 和网状和网状 DBMSn1970s:n关系数据关系数据库库模型模型,关系关系 DBMS 实现实现n1980s:nRDBMS,先先进进的数据模型的数据模型(扩扩充关系的充关系的,OO,演演绎绎的的,等等.)和面向和面向应应用用 的的 DBMS(空空间间的的,科学的科学的,工程的工程的,等等.)n1990s2000s:n数据挖掘和数据数据挖掘和数据仓库仓库,多媒体数据多媒体数据库库,和和 Web 数据数据库库8/3/20247a什么是数据挖掘什么是数据挖掘?n数据挖掘数据挖掘(数据数据库库中知中知识发现识发现):n从从大型数据大型数据库库中提取有趣的中提取有趣的(非平凡的非平凡的,蕴涵的涵的,先前未知的先前未知的 并且是并且是潜在有用的潜在有用的)信息或模式信息或模式n其它叫法和其它叫法和“inside stories”:n数据挖掘数据挖掘:用用词词不当不当?n数据数据库库中知中知识发现识发现(挖掘挖掘)(Knowledge discovery in databases,KDD),知知识识提取提取(knowledge extraction),数据数据/模式分析模式分析(data/pattern analysis),数据考古数据考古(data archeology),数据捕数据捕捞捞(data dredging),信息收信息收获获(information harvesting),商商务务智能智能(business intelligence),等等.n什么不是数据挖掘什么不是数据挖掘?n(演演绎绎)查询处查询处理理.n 专专家系家系统统 或小型或小型 机器学机器学习习(ML)/统计统计程序程序8/3/20248a为为什么要数据挖掘什么要数据挖掘?可能的可能的应应用用n数据数据库库分析和决策支持分析和决策支持n市市场场分析和管理分析和管理n针对销针对销售售(target marketing),顾顾客关系管理客关系管理,购购物物篮篮分析分析,交叉交叉销销售售(cross selling),市市场场分割分割(market segmentation)n风险风险分析与管理分析与管理n预测预测,顾顾客关系客关系,改改进进保保险险,质质量控制量控制,竞竞争能力分析争能力分析n欺欺骗检测骗检测与管理与管理n其它其它应应用用n文本挖掘文本挖掘(新新闻组闻组,email,文档文档资资料料)n流数据挖掘流数据挖掘(Stream data mining)nWeb挖掘挖掘.nDNA 数据分析数据分析8/3/20249a市市场场分析与管理分析与管理(1)n用于分析的数据源在哪用于分析的数据源在哪?n信用卡交易信用卡交易,会会员员卡卡,打折打折优优惠卷惠卷,顾顾客投客投诉电话诉电话,(公共公共)生活生活时时尚研究尚研究n针对销针对销售售(Target marketing)n找出找出顾顾客群客群,他他们们具有相同特征具有相同特征:兴兴趣趣,收入水平收入水平,消消费习惯费习惯,等等.n确定确定顾顾客随客随时间变时间变化的化的购买购买模式模式n个人个人帐帐号到号到联联合合帐帐号的号的转变转变:结结婚婚,等等.n交叉交叉销销售分析售分析(Cross-market analysis)n产产品品销销售之售之间间的关的关联联/相关相关 n基于关基于关联联信息的信息的预测预测8/3/202410a市市场场分析与管理分析与管理(2)n顾顾客分客分类类(Customer profiling)n数据挖掘能数据挖掘能够够告告诉诉我我们们什么什么样样的的顾顾客客买买什么什么产产品品(聚聚类类或分或分类类)n识别顾识别顾客需求客需求n对对不同的不同的顾顾客客识别识别最好的最好的产产品品n使用使用预测发现预测发现什么因素影响新什么因素影响新顾顾客客n提供提供汇总汇总信息信息n各种多各种多维汇总报维汇总报告告n统计统计的的汇总汇总信息信息(数据的中心数据的中心趋势趋势和方差和方差)8/3/202411a法人分析和法人分析和风险风险管理管理n财经规财经规划和划和资产评资产评估估n现现金流分析和金流分析和预测预测n临时临时提出的提出的资产评资产评估估n交叉交叉组组合合(cross-sectional)和和时间时间序列分析序列分析(金融比率金融比率(financial-ratio),趋势趋势分析分析,等等.)n资资源源规规划划:n资资源与开源与开销销的的汇总汇总与比与比较较n竞竞争争:n管理管理竞竞争者和市争者和市场场指指导导n对顾对顾客分客分类类和基于和基于类类的定价的定价n在高度在高度竞竞争的市争的市场调场调整价格策略整价格策略8/3/202412a欺欺骗检测骗检测和管理和管理(1)n应应用用n广泛用于健康照料广泛用于健康照料,零售零售,信用卡服信用卡服务务,电讯电讯(电话电话卡欺卡欺骗骗),等等.n方法方法n使用使用历历史数据建立欺史数据建立欺骗骗行行为为模型模型,使用数据挖掘帮助使用数据挖掘帮助识别类识别类似的似的实实例例n例例n汽汽车车保保险险:检测这样检测这样的人的人,他他/她假造事故她假造事故骗骗取保取保险赔偿险赔偿n洗洗钱钱:检测检测可疑的金可疑的金钱钱交易交易(US Treasurys Financial Crimes Enforcement Network)n医医疗疗保保险险:检测职业检测职业病患者病患者,医生和介医生和介绍绍人圈人圈8/3/202413a欺欺骗检测骗检测和管理和管理(2)n检测检测不适当的医不适当的医疗处疗处置置n澳大利澳大利亚亚健康保健康保险险会会(Australian Health Insurance Commission)发现发现许许多全面的多全面的检查检查是是请请求做的求做的,而不是而不是实际实际需要的需要的(每年每年节节省省100万澳万澳元元).n检测电话检测电话欺欺骗骗n电话电话呼叫模式呼叫模式:通通话话距离距离,通通话时间话时间,每天或每周通每天或每周通话话次数次数.分析偏离分析偏离期望的模式期望的模式.n英国英国电讯电讯(British Telecom)识别频识别频繁内部通繁内部通话话的呼叫者的离散群的呼叫者的离散群,特特别别是移是移动电话动电话,超超过过数百万美元的欺数百万美元的欺骗骗.n零售零售n分析家估分析家估计计,38%的零售的零售业业萎萎缩缩是由于不忠是由于不忠诚诚的雇的雇员员造成的造成的.8/3/202414a其它其它应应用用n运运动动nIBM Advanced Scout分析分析NBA的的统计统计数据数据(阻阻挡挡投投篮篮,助攻助攻,和犯和犯规规)获获得了得了对纽约对纽约小牛小牛队队(New York Knicks)和和迈迈艾米艾米热队热队(Miami Heat)的的竞竞争争优势优势n天文天文n借助于数据挖掘的帮助借助于数据挖掘的帮助,JPL 和和 Palomar Observatory 发现发现了了22 颗类颗类星体星体(quasars)nInternet Web Surf-AidnIBM Surf-Aid 将数据挖掘算法用于有关交易的将数据挖掘算法用于有关交易的页页面的面的Web访问访问日志日志,以以发现顾发现顾客喜客喜爱爱的的页页面面,分析分析Web 销销售的效果售的效果,改改进进Web 站点的站点的组织组织,等等.8/3/202415a数据挖掘数据挖掘过过程程n数据挖掘：数据挖掘：KDD的核心的核心.数据清理数据清理数据集成数据集成数据数据库库数据数据仓库仓库任任务务相关数据相关数据选择选择数据挖掘数据挖掘模式模式评评估估8/3/202416aKDD过过程的步程的步骤骤n学学习应习应用用领领域域:n相关的先相关的先验验知知识识和和应应用的目用的目标标n创创建目建目标标数据集数据集:数据数据选择选择n数据清理和数据清理和预处预处理理:(可能占全部工作的可能占全部工作的 60%!)n数据数据归约归约与与变换变换:n发现发现有用的特征有用的特征,维维/变变量量归约归约,不不变变量的表示量的表示.n选择选择数据挖掘函数数据挖掘函数 n 汇总汇总,分分类类,回回归归,关关联联,聚聚类类.8/3/202417aKDD过过程的步程的步骤骤(续续)n选择选择挖掘算法挖掘算法n数据挖掘数据挖掘:搜索有趣的模式搜索有趣的模式n模式模式评评估和知估和知识识表示表示n可可视视化化,变换变换,删删除冗余模式除冗余模式,等等.n发现发现知知识识的使用的使用8/3/202418a数据挖掘和商数据挖掘和商务务智能智能 提高支持商提高支持商务务决策的潜能决策的潜能最最终终用用户户商商务务分析人分析人员员 数据分析人数据分析人员员DBA 制定决策制定决策数据表示数据表示可可视视化技化技术术数据挖掘数据挖掘信息信息发现发现数据探数据探查查OLAP,MDA统计统计分析分析,查询查询和和报报告告数据数据仓库仓库/数据集市数据集市数据源数据源文字文字记录记录,文件文件,信息提供者信息提供者,数据数据库库系系统统,OLTP系系统统8/3/202419a典型的数据挖掘系典型的数据挖掘系统结统结构构数据数据仓库仓库数据清理数据清理 数据集成数据集成过滤过滤数据数据库库数据数据库库或数据或数据仓库仓库数据挖掘引擎数据挖掘引擎模式模式评评估估图图形用形用户户界面界面知知识库识库8/3/202420a数据挖掘数据挖掘:在什么数据上在什么数据上进进行行?n关系数据关系数据库库n数据数据仓库仓库n事事务务(交易交易)数据数据库库n先先进进的数据的数据库库和信息存和信息存储储n面向面向对对象和象和对对象象-关系数据关系数据库库n空空间间和和时间时间数据数据n时间时间序列数据和流数据序列数据和流数据n文本数据文本数据库库和多媒体数据和多媒体数据库库n异种数据异种数据库库和和遗产遗产数据数据库库 nWWW8/3/202421a数据挖掘功能数据挖掘功能(1)n概念描述概念描述:特征和区分特征和区分n概化概化,汇总汇总,和比和比较较数据特征数据特征,例如例如,干燥和潮湿的地区干燥和潮湿的地区n关关联联(相关和因果关系相关和因果关系)n多多维维和和单维单维关关联联 nage(X,“20.29”)income(X,“20.29K”)buys(X,“PC”)support=2%,confidence=60%ncontains(T,“computer”)contains(T,“software”)support=1%,confidence=75%8/3/202422a数据挖掘功能数据挖掘功能(2)n分分类类和和预测预测n找出描述和找出描述和识别类识别类或概念的模型或概念的模型(函数函数),用于将来的用于将来的预测预测n例如根据气候例如根据气候对对国家分国家分类类,或根据或根据单单位里程的耗油量位里程的耗油量对对汽汽车车分分类类n表示表示:判定判定树树(decision-tree),分分类规则类规则,神神经经网网络络n预测预测:预测预测某些未知或某些未知或遗遗漏的数漏的数值值值值n聚聚类类分析分析n类标类标号号(Class label)未知未知:对对数据分数据分组组,形成新的形成新的类类.例如例如,对对房屋分房屋分类类,找出分布模式找出分布模式n聚聚类类原原则则:最大化最大化类类内的相似性内的相似性,最小化最小化类间类间的相似性的相似性8/3/202423a数据挖掘功能数据挖掘功能(3)n孤立点孤立点(Outlier)分析分析n孤立点孤立点:一个数据一个数据对对象象,它它 与数据的一般行与数据的一般行为为不一致不一致n孤立点可以被孤立点可以被视为视为例外例外,但但对对于欺于欺骗检测骗检测和罕和罕见见事件分析事件分析,它是相当有用的它是相当有用的n趋势趋势和演和演变变分析分析n趋势趋势和偏离和偏离:回回归归分析分析n序列模式挖掘序列模式挖掘,周期性分析周期性分析n基于相似的分析基于相似的分析n其它基于模式或其它基于模式或统计统计的分析的分析8/3/202424a挖掘出的所有模式都是有趣的挖掘出的所有模式都是有趣的吗吗?n一个数据挖掘系一个数据挖掘系统统/查询查询可以挖掘出数以千可以挖掘出数以千计计的模式的模式,并非所有的模式都并非所有的模式都是有趣的是有趣的n建建议议的方法的方法:以人以人为为中心中心,基于基于查询查询的的,聚焦的挖掘聚焦的挖掘n兴兴趣度度量趣度度量:一个模式是一个模式是 有趣的有趣的 如果它是如果它是 易于被人理解的易于被人理解的,在某种程度在某种程度上上在新的或在新的或测试测试数据上是有效的数据上是有效的,潜在有用的潜在有用的,新新颖颖的的,或或验证验证了用了用户户希希望望证实证实的某种假的某种假设设n客客观观与主与主观观的的兴兴趣度度量趣度度量:n客客观观:基于模式的基于模式的统计统计和和结结构构,例如例如,支持度支持度,置信度置信度,等等.n主主观观:基于用基于用户对户对数据的确信数据的确信,例如例如,出乎意料出乎意料,新新颖颖性性,可行可行动动性性(actionability),等等.8/3/202425a能能够够只只发现发现有趣的模式有趣的模式吗吗?n发现发现所有有趣的模式所有有趣的模式:完全性完全性n数据挖掘系数据挖掘系统统能能够发现够发现所有所有有趣的模式有趣的模式吗吗?n关关联联 vs.分分类类 vs.聚聚类类n仅仅搜索有趣的模式搜索有趣的模式:优优化化n数据挖掘系数据挖掘系统统能能够够仅仅发现发现有趣的模式有趣的模式吗吗?n方法方法n首先找出所有模式首先找出所有模式,然后然后过滤过滤掉不是有趣的那些掉不是有趣的那些.n仅产仅产生有趣的模式生有趣的模式 挖掘挖掘查询优查询优化化8/3/202426a数据挖掘数据挖掘:多学科交叉多学科交叉 数据挖掘数据挖掘数据数据库库技技术术统计统计学学其它学科其它学科信息科学信息科学机器学机器学习习可可视视化化8/3/202427a数据挖掘分数据挖掘分类类n一般功能一般功能n描述式数据挖掘描述式数据挖掘n预测预测式数据挖掘式数据挖掘n不同的角度不同的角度,不同的分不同的分类类n待挖掘的数据待挖掘的数据库类库类型型 n待待发现发现的知的知识类识类型型n所用的技所用的技术类术类型型n所适合的所适合的应应用用类类型型8/3/202428a数据挖掘分数据挖掘分类类的多的多维视图维视图n待挖掘的数据待挖掘的数据库库n关系的关系的,事事务务的的,面向面向对对象的象的,对对象象-关系的关系的,主主动动的的,空空间间的的,时间时间序列的序列的,文本文本的的,多媒体的多媒体的,异种的异种的,遗产遗产的的,WWW,等等.n所挖掘的知所挖掘的知识识n特征特征,区分区分,关关联联,分分类类,聚聚类类,趋势趋势,偏离和孤立点分析偏离和孤立点分析,等等.n多多/集成的功能集成的功能,和多和多层层次上的挖掘次上的挖掘n所用技所用技术术n面向数据面向数据库库的的,数据数据仓库仓库(OLAP),机器学机器学习习,统计统计学学,可可视视化化,神神经经网网络络,等等.n适合的适合的应应用用n零售零售,电讯电讯,银银行行,欺欺骗骗分析分析,DNA 挖掘挖掘,股票市股票市场场分析分析,Web 挖掘挖掘,Web日志分析日志分析,等等8/3/202429aOLAP挖掘挖掘:数据挖掘与数据数据挖掘与数据仓库仓库的集成的集成n数据挖掘系数据挖掘系统统,DBMS,数据数据仓库仓库系系统统的耦合的耦合 n不耦合不耦合,松耦合松耦合,半半紧紧密耦合密耦合,紧紧密耦合密耦合n联联机分析挖掘机分析挖掘n挖掘与挖掘与 OLAP 技技术术的集成的集成n交互挖掘多交互挖掘多层层知知识识n通通过过下下钻钻,上卷上卷,转轴转轴,切片切片,切切块块等操作等操作,在不同的抽象在不同的抽象层层挖掘知挖掘知识识和模式的和模式的必要性必要性.n多种挖掘功能的集成多种挖掘功能的集成n 特征分特征分类类,先聚先聚类类在关在关联联8/3/202430aOLAM 的的结结构构数据数据仓库仓库元数据元数据MDDBOLAM引擎引擎OLAP引擎引擎用用户户 GUI API数据立方体数据立方体 API数据数据库库 API数据清理数据清理数据集成数据集成第第3层层OLAP/OLAM第第2层层MDDB第第1层层数据存数据存储储第第4层层用用户户界面界面过滤过滤和集成和集成过滤过滤Databases挖掘挖掘查询查询挖掘挖掘结结果果8/3/202431a数据挖掘的主要数据挖掘的主要问题问题(1)n挖掘方法和用挖掘方法和用户户交互交互n在数据在数据库库中挖掘不同中挖掘不同类类型的知型的知识识n在多个抽象在多个抽象层层的交互式知的交互式知识识挖掘挖掘n结结合背景知合背景知识识n数据挖掘数据挖掘语语言和启言和启发发式数据挖掘式数据挖掘 n数据挖掘数据挖掘结结果的表示和可果的表示和可视视化化n处处理噪音和不完全数据理噪音和不完全数据n模式模式评评估估:兴兴趣度趣度问题问题n性能和可伸性能和可伸缩缩性性(scalability)n数据挖掘算法的性能和可伸数据挖掘算法的性能和可伸缩缩性性n并行并行,分布和增量的挖掘方法分布和增量的挖掘方法8/3/202432a数据挖掘的主要数据挖掘的主要问题问题(2)n数据数据类类型的多型的多样样性性问题问题n处处理关系的和复理关系的和复杂类杂类型的数据型的数据n从异种数据从异种数据库库和全球信息系和全球信息系统统(WWW)挖掘信息挖掘信息n应应用和社会效果用和社会效果问题问题n发现发现知知识识的的应应用用n特定特定领领域的数据挖掘工具域的数据挖掘工具n智能智能查询查询回答回答n过过程控制和决策制定程控制和决策制定n发现发现知知识识与已有知与已有知识识的集成的集成:知知识识融合融合问题问题n数据安全数据安全,完整和私有的保完整和私有的保护护8/3/202433a小小结结n数据挖掘数据挖掘:从大量数据中从大量数据中发现发现有趣的模式有趣的模式n数据数据库库技技术术的自然的自然进进化化,具有巨大需求和广泛具有巨大需求和广泛应应用用nKDD 过过程包括数据清理程包括数据清理,数据集成数据集成,数据数据选择选择,变换变换,数据挖掘数据挖掘,模式模式评评估估,和知和知识识表示表示n挖掘可以在各种数据存挖掘可以在各种数据存储储上上进进行行n数据挖掘功能数据挖掘功能:特征特征,区分区分,关关联联,分分类类,聚聚类类,孤立点孤立点 和和趋势趋势分析分析,等等.n数据挖掘系数据挖掘系统统的分的分类类n数据挖掘的主要数据挖掘的主要问题问题8/3/202434a数据挖掘界数据挖掘界简简史史n1989 IJCAI Workshop on Knowledge Discovery in Databases(Piatetsky-Shapiro)nKnowledge Discovery in Databases(G.Piatetsky-Shapiro and W.Frawley,1991)n1991-1994 Workshops on Knowledge Discovery in DatabasesnAdvances in Knowledge Discovery and Data Mining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy,1996)n1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining(KDD95-98)nJournal of Data Mining and Knowledge Discovery(1997)n1998 ACM SIGKDD,SIGKDD1999-2001 conferences,and SIGKDD ExplorationsnMore conferences on data miningnPAKDD,PKDD,SIAM-Data Mining,(IEEE)ICDM,etc.8/3/202435a参考文献源参考文献源nData mining and KDD(SIGKDD member CDROM):nConference proceedings:KDD,and others,such as PKDD,PAKDD,etc.nJournal:Data Mining and Knowledge DiscoverynDatabase field(SIGMOD member CD ROM):nConference proceedings:ACM-SIGMOD,ACM-PODS,VLDB,ICDE,EDBT,DASFAAnJournals:ACM-TODS,J.ACM,IEEE-TKDE,JIIS,etc.nAI and Machine Learning:nConference proceedings:Machine learning,AAAI,IJCAI,etc.nJournals:Machine Learning,Artificial Intelligence,etc.nStatistics:nConference proceedings:Joint Stat.Meeting,etc.nJournals:Annals of statistics,etc.nVisualization:nConference proceedings:CHI,etc.nJournals:IEEE Trans.visualization and computer graphics,etc.8/3/202436a参考文献参考文献nU.M.Fayyad,G.Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy.Advances in Knowledge Discovery and Data Mining.AAAI/MIT Press,1996.nJ.Han and M.Kamber.Data Mining:Concepts and Techniques.Morgan Kaufmann,2000.nT.Imielinski and H.Mannila.A database perspective on knowledge discovery.Communications of ACM,39:58-64,1996.nG.Piatetsky-Shapiro,U.Fayyad,and P.Smith.From data mining to knowledge discovery:An overview.In U.M.Fayyad,et al.(eds.),Advances in Knowledge Discovery and Data Mining,1-35.AAAI/MIT Press,1996.nG.Piatetsky-Shapiro and W.J.Frawley.Knowledge Discovery in Databases.AAAI/MIT Press,1991.8/3/202437a谢谢谢谢大家大家!Email:phone#:(371)7762002(H)(371)7761542(O)8/3/202438a