数据挖掘概念与技术

《数据挖掘概念与技术》由会员分享，可在线阅读，更多相关《数据挖掘概念与技术（61页珍藏版）》请在金锄头文库上搜索。

1、数据挖掘：概念与技术数据挖掘：概念与技术武永亮武永亮大数据方向的宣讲图大数据方向的宣讲图2数据挖掘工作缺口数据挖掘工作缺口3生活中的数据挖掘生活中的数据挖掘n垃圾邮件的处理，邮件分类，过滤，筛选垃圾邮件的处理，邮件分类，过滤，筛选.n商品推荐，相关度推荐，猜你喜欢商品推荐，相关度推荐，猜你喜欢.n匹配，游戏匹配匹配，游戏匹配.n预测，天气预报，股市，房价预测，天气预报，股市，房价4算法：可以完成任何事生活中的数据挖掘生活中的数据挖掘n写出你的性别，姓名（可用昵称）写出你的性别，姓名（可用昵称）n写出你期望的未来一半的身高，体重，大数据成绩区间写出你期望的未来一半的身高，体重，大数据成绩区间.5

2、数据收集数据整理，预处理数据挖掘（算法）结果呈现算法的调优常见混淆概念常见混淆概念n数据挖掘、机器学习、模式识别数据挖掘、机器学习、模式识别67教材教材-作者作者nhttp:/www.cs.illinois.edu/homes/hanj/nThe book will be covered in two courses at CS, UIUC：伊利诺伊大学，厄：伊利诺伊大学，厄巴纳巴纳-尚佩恩尚佩恩(University of Illinois at Urbana-Champaign)nCS412: Introduction to data warehousing and data mining

3、 Coverage (Chapters 1-7 of This Book)nCS512: Data mining: Principles and algorithms (Chapters 8-11 of This Book)8课程信息课程信息n数据挖掘的（前数据挖掘的（前7章的内容），章的内容），n第第1章章 引言引言n第第2章章 数据预处理数据预处理n第第3章章 数据仓库与数据仓库与OLAP技术概述技术概述n第第4章章 数据立方体计算与数据泛化数据立方体计算与数据泛化n第第5章章 挖掘频繁模式、关联和相关挖掘频繁模式、关联和相关n第第6章章 分类和预测分类和预测n第第7章章 聚类分析聚类分析

4、n导论课程（从数据库角度出发）导论课程（从数据库角度出发）n相关涉及：数据仓库、数据库系统、统计学与机器学习的概相关涉及：数据仓库、数据库系统、统计学与机器学习的概念和技术念和技术9课时安排与考核课时安排与考核n课时安排课时安排n总总学时学时 18，课次，课次6半天，共半天，共2周周n考核考核n平时成绩：平时成绩：6次作业次作业n考试成绩：考试成绩：10第第1章章 引论引论n动机：为什么要数据挖掘动机：为什么要数据挖掘?n什么是数据挖掘什么是数据挖掘?n数据挖掘：在什么数据上进行数据挖掘：在什么数据上进行?n数据挖掘功能数据挖掘功能n所有的模式都是有趣的吗所有的模式都是有趣的吗?n数据挖掘系统

5、分类数据挖掘系统分类 n数据挖掘的主要问题数据挖掘的主要问题11数据处理技术的演进数据处理技术的演进n1960s:n数据收集数据收集, 数据库创建数据库创建, IMS层次层次和网状和网状 DBMSn1970s: n关系数据库模型关系数据库模型, 关系关系 DBMS 实现实现n1980s: nRDBMS, 先进的数据模型先进的数据模型 (扩充关系的扩充关系的, OO, 演绎的演绎的, 等等.) 和面向应用和面向应用 的的 DBMS (空间的空间的, 科学的科学的, 工程的工程的, 等等.)n1990s2000s: n数据挖掘和数据仓库数据挖掘和数据仓库, 多媒体数据库多媒体数据库, 和和 Web

6、 数据库数据库1213动机动机: 需要是发明之母需要是发明之母n数据爆炸问题数据爆炸问题n自动的数据收集工具和成熟的数据库技术导致大量数据存放在数据自动的数据收集工具和成熟的数据库技术导致大量数据存放在数据库库, 数据仓库数据仓库, 和其它信息存储中和其它信息存储中nBusiness: Web, e-commerce, transactions, stocks, nScience: Remote sensing, bioinformatics, scientific simulation, nSociety and everyone: news, digital cameras, YouTub

7、en我们正被数据淹没我们正被数据淹没,但却缺乏知识但却缺乏知识n数据丰富，但信息贫乏数据丰富，但信息贫乏n解决办法解决办法: 数据仓库与数据挖掘数据仓库与数据挖掘n数据仓库与联机分析处理数据仓库与联机分析处理(OLAP)n从大型数据库的数据中提取有趣的知识从大型数据库的数据中提取有趣的知识(规则规则, 规律性规律性, 模式模式, 限制等限制等)14数据挖掘界简史数据挖掘界简史n1989 IJCAI Workshop on Knowledge Discovery in Databases (Piatetsky-Shapiro)nKnowledge Discovery in Databases (

8、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 Min

9、ing (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.nACM Transactions on KDD starting in 200715Conferences and Journals on Data Minin

10、gnKDD ConferencesnACM SIGKDD Int. Conf. on Knowledge Discovery in Databases and Data Mining (KDD)nSIAM Data Mining Conf. (SDM)n(IEEE) Int. Conf. on Data Mining (ICDM)nConf. on Principles and practices of Knowledge Discovery and Data Mining (PKDD)nPacific-Asia Conf. on Knowledge Discovery and Data Mi

11、ning (PAKDD)nOther related conferencesnACM SIGMODnVLDBn(IEEE) ICDEnWWW, SIGIRnICML, CVPR, NIPSnJournals nData Mining and Knowledge Discovery (DAMI or DMKD)nIEEE Trans. On Knowledge and Data Eng. (TKDE)nKDD ExplorationsnACM Trans. on KDD16Where 2 Find References? DBLP, CiteSeer, GooglenData mining an

12、d KDD (SIGKDD: CDROM)nConferences: ACM-SIGKDD, IEEE-ICDM, SIAM-DM, PKDD, PAKDD, etc.nJournal: Data Mining and Knowledge Discovery, KDD Explorations, ACM TKDDnDatabase systems (SIGMOD: ACM SIGMOD AnthologyCD ROM)nConferences: ACM-SIGMOD, ACM-PODS, VLDB, IEEE-ICDE, EDBT, ICDT, DASFAAnJournals: IEEE-TK

13、DE, ACM-TODS/TOIS, JIIS, J. ACM, VLDB J., Info. Sys., etc.nAI & Machine LearningnConferences: Machine learning (ML), AAAI, IJCAI, COLT (Learning Theory), CVPR, NIPS, etc.nJournals: Machine Learning, Artificial Intelligence, Knowledge and Information Systems, IEEE-PAMI, etc.nWeb and IR nConferences:

14、SIGIR, WWW, CIKM, etc.nJournals: WWW: Internet and Web Information Systems, nStatisticsnConferences: Joint Stat. Meeting, etc.nJournals: Annals of statistics, etc.nVisualizationnConference proceedings: CHI, ACM-SIGGraph, etc.nJournals: IEEE Trans. visualization and computer graphics, etc.17什么是数据挖掘什么

15、是数据挖掘?n数据挖掘数据挖掘 (从数据中挖掘知识从数据中挖掘知识): n从从大型数据库大型数据库中提取有趣的中提取有趣的 (非平凡的非平凡的, 蕴涵的蕴涵的, 先前未知的先前未知的 并且是并且是潜在有用的潜在有用的) 信息或模式信息或模式n数据挖掘数据挖掘: 用词不当用词不当?n其它叫法和其它叫法和“inside stories”内幕新闻内幕新闻 : n数据库中知识发现数据库中知识发现(挖掘挖掘) (Knowledge discovery in databases, KDD), 知识提取知识提取(knowledge extraction), 数据数据/模式分析模式分析(data/patter

16、n analysis), 数据考古数据考古(data archeology), 数据捕捞数据捕捞(data dredging), 信息收获信息收获(information harvesting), 商务智能商务智能(business intelligence), 等等.n什么不是数据挖掘什么不是数据挖掘?n(演绎演绎) 查询处理查询处理. n 专家系统专家系统 或小型或小型 机器学习机器学习(ML)/统计程序统计程序n处理大量数据处理大量数据/ 有效的可伸缩的技术有效的可伸缩的技术Why Not Traditional Data Analysis?n 巨大的数据巨大的数据Tremendous

17、amount of datanAlgorithms must be highly scalable to handle such as tera-bytes of datanHigh-dimensionality of data nMicro-array may have tens of thousands of dimensionsnHigh complexity of datanData streams and sensor datanTime-series data, temporal data, sequence data nStructure data, graphs, social

18、 networks and multi-linked datanHeterogeneous databases and legacy(遗产遗产) databasesnSpatial, spatiotemporal, multimedia, text and Web datanSoftware programs, scientific simulationsnNew and sophisticated applications19数据挖掘过程数据挖掘过程n数据挖掘：数据挖掘：KDD的核心的核心.数据清理数据清理数据集成数据集成数据库数据库选择与变换选择与变换数据挖掘数据挖掘模式评估模式评估数据仓

19、库数据仓库任务相关数据任务相关数据20KDD过程的步骤过程的步骤n学习应用领域学习应用领域:n相关的先验知识和应用的目标相关的先验知识和应用的目标n创建目标数据集创建目标数据集: 数据选择数据选择n数据清理和预处理数据清理和预处理: (可能占全部工作的可能占全部工作的 60%!)n数据归约与变换数据归约与变换:n发现有用的特征发现有用的特征, 维维/变量归约变量归约, 不变量的表示不变量的表示.n选择数据挖掘函数选择数据挖掘函数 n 汇总汇总, 分类分类, 回归回归, 关联关联, 聚类聚类.n选择挖掘算法选择挖掘算法n数据挖掘数据挖掘: 搜索有趣的模式搜索有趣的模式n模式评估和知识表示模式评估

20、和知识表示n可视化可视化, 变换变换, 删除冗余模式删除冗余模式, 等等.n发现知识的使用发现知识的使用2131 七月 2024Data Mining: Concepts and Techniques21KDD过程过程: 机器学习和统计的角度机器学习和统计的角度Input DataData MiningData Pre-ProcessingPost-ProcessingnThis is a view from typical machine learning and statistics communitiesData integrationNormalizationFeature selec

21、tionDimension reductionPattern discoveryAssociation & correlationClassificationClusteringOutlier analysis Pattern evaluationPattern selectionPattern interpretationPattern visualization22典型的数据挖掘系统结构典型的数据挖掘系统结构23数据挖掘和商务智能数据挖掘和商务智能提高支持提高支持商务决策的潜能商务决策的潜能最终用户最终用户商务分析人员商务分析人员 数据分析人员数据分析人员DBA 制定决策制定决策数据表示数

22、据表示可视化技术可视化技术数据挖掘数据挖掘信息发现信息发现数据探查数据探查OLAP, MDA统计分析统计分析, 查询和报告查询和报告数据仓库数据仓库 / 数据集市数据集市数据源数据源文字记录文字记录, 文件文件, 信息提供者信息提供者, 数据库系统数据库系统, OLTP系统系统24为什么要数据挖掘为什么要数据挖掘?可能的应用可能的应用n数据库分析和决策支持数据库分析和决策支持n市场分析和管理市场分析和管理n针对销售针对销售(target marketing), 顾客关系管理顾客关系管理, 购物篮分析购物篮分析, 交叉销售交叉销售(cross selling), 市场分割市场分割(market

23、segmentation)n风险分析与管理风险分析与管理n预测预测, 顾客关系顾客关系, 改进保险改进保险, 质量控制质量控制, 竞争能力分析竞争能力分析n欺骗检测与管理欺骗检测与管理n其它应用其它应用n文本挖掘文本挖掘 (新闻组新闻组, email, 文档资料文档资料)n流数据挖掘流数据挖掘(Stream data mining)nWeb挖掘挖掘.n生物信息学生物信息学/生物生物 数据分析数据分析25市场分析与管理市场分析与管理(1)n用于分析的数据源在哪用于分析的数据源在哪?n信用卡交易信用卡交易, 会员卡会员卡, 打折优惠卷打折优惠卷, 顾客投诉电话顾客投诉电话, (公共公共) 生活时尚

24、研究生活时尚研究n针对销售针对销售(Target marketing)n找出顾客群找出顾客群, 他们具有相同特征他们具有相同特征 : 兴趣兴趣, 收入水平收入水平, 消费习惯消费习惯, 等等.n确定顾客随时间变化的购买模式确定顾客随时间变化的购买模式n个人帐号到联合帐号的转变个人帐号到联合帐号的转变: 结婚结婚, 等等.n交叉销售分析交叉销售分析(Cross-market analysis)n产品销售之间的关联产品销售之间的关联/相关相关 n基于关联信息的预测基于关联信息的预测26市场分析与管理市场分析与管理(2)n顾客分类顾客分类(Customer profiling)n数据挖掘能够告诉我们

25、什么样的顾客买什么产品数据挖掘能够告诉我们什么样的顾客买什么产品(聚类或分类聚类或分类)n识别顾客需求识别顾客需求n对不同的顾客识别最好的产品对不同的顾客识别最好的产品n使用预测发现什么因素影响新顾客使用预测发现什么因素影响新顾客n提供汇总信息提供汇总信息n各种多维汇总报告各种多维汇总报告n统计的汇总信息统计的汇总信息 (数据的中心趋势和方差数据的中心趋势和方差)27法人分析和风险管理法人分析和风险管理n财经规划和资产评估财经规划和资产评估n现金流分析和预测现金流分析和预测n临时提出的资产评估临时提出的资产评估n交叉组合交叉组合(cross-sectional) 和时间序列分析和时间序列分析

26、(金融比率金融比率(financial-ratio), 趋势分析趋势分析, 等等.)n资源规划资源规划 :n资源与开销的汇总与比较资源与开销的汇总与比较n竞争竞争:n管理竞争者和市场指导管理竞争者和市场指导n对顾客分类和基于类的定价对顾客分类和基于类的定价n在高度竞争的市场调整价格策略在高度竞争的市场调整价格策略28欺骗检测和管理欺骗检测和管理(1)n应用应用n广泛用于健康照料广泛用于健康照料, 零售零售, 信用卡服务信用卡服务, 电讯电讯 (电话卡欺骗电话卡欺骗), 等等.n方法方法n使用历史数据建立欺骗行为模型使用历史数据建立欺骗行为模型, 使用数据挖掘帮助识别类似的实例使用数据挖掘帮助识

27、别类似的实例n例例n汽车保险汽车保险: 检测这样的人检测这样的人, 他他/她假造事故骗取保险赔偿她假造事故骗取保险赔偿n洗钱洗钱: 检测可疑的金钱交易检测可疑的金钱交易 (US Treasurys Financial Crimes Enforcement Network) n医疗保险医疗保险 : 检测职业病患者检测职业病患者, 医生和介绍人圈医生和介绍人圈29欺骗检测和管理欺骗检测和管理(2)n检测不适当的医疗处置检测不适当的医疗处置n澳大利亚健康保险会澳大利亚健康保险会(Australian Health Insurance Commission) 发现发现许多全面的检查是请求做的许多全面的

28、检查是请求做的, 而不是实际需要的而不是实际需要的 (每年节省每年节省100万澳万澳元元).n检测电话欺骗检测电话欺骗n电话呼叫模式电话呼叫模式: 通话距离通话距离, 通话时间通话时间, 每天或每周通话次数每天或每周通话次数. 分析偏离分析偏离期望的模式期望的模式.n英国电讯英国电讯(British Telecom)识别频繁内部通话的呼叫者的离散群识别频繁内部通话的呼叫者的离散群, 特特别是移动电话别是移动电话, 超过数百万美元的欺骗超过数百万美元的欺骗. n零售零售n分析家估计分析家估计, 38%的零售业萎缩是由于不忠诚的雇员造成的的零售业萎缩是由于不忠诚的雇员造成的.30生物数据分析生物数

29、据分析/挖掘挖掘nmicroarray data analysis 微阵列数据微阵列数据nbiological sequence analysis生物序列生物序列nbiological network analysis 生物学网络生物学网络n生物文本挖掘生物文本挖掘n文本数据中抽取文本数据中抽取biological informationn从抽取信息中从抽取信息中infer, predict biological features31其它应用其它应用n运动运动nIBM Advanced Scout分析分析NBA的统计数据的统计数据 ( 阻挡投篮阻挡投篮, 助攻助攻, 和犯规和犯规 ) 获得了对

30、纽约小牛队获得了对纽约小牛队(New York Knicks)和迈艾米热队和迈艾米热队( Miami Heat )的竞争优势的竞争优势n天文天文n借助于数据挖掘的帮助借助于数据挖掘的帮助,JPL 和和 Palomar Observatory 发现了发现了22 颗类颗类星体星体(quasars)nInternet Web Surf-AidnIBM Surf-Aid 将数据挖掘算法用于有关交易的页面的将数据挖掘算法用于有关交易的页面的Web访问日志访问日志, 以发现顾客喜爱的页面以发现顾客喜爱的页面, 分析分析Web 销售的效果销售的效果, 改进改进Web 站点的组织站点的组织, 等等.nWeb：

31、页面的分类、聚类、推荐：页面的分类、聚类、推荐/用户的访问模式用户的访问模式32数据挖掘数据挖掘:在什么数据上进行在什么数据上进行?n关系数据库关系数据库n数据仓库数据仓库n事务事务(交易交易)数据库数据库n先进的数据库和信息存储先进的数据库和信息存储n面向对象和对象面向对象和对象-关系数据库关系数据库n空间和时间数据空间和时间数据n时间序列数据和流数据时间序列数据和流数据n文本数据库和多媒体数据库文本数据库和多媒体数据库n异种数据库和遗产数据库异种数据库和遗产数据库 nWWW33数据挖掘功能数据挖掘功能(1)n概念描述概念描述: 特征和区分特征和区分Characterization and

32、discriminationn概化概化, 汇总和比较数据特征汇总和比较数据特征, 例如例如, 干燥和潮湿的地区干燥和潮湿的地区n频繁模式频繁模式,关联关联,相关相关 Frequent patterns, association, correlation vs. causalityn频繁模式频繁模式：数据中频繁出现的模式：数据中频繁出现的模式n多维和单维关联多维和单维关联nage(X, “20.29”) income(X, “20.29K”) buys(X, “PC”) support = 2%, confidence = 60%ncontains(T, “computer”) contains

33、(T, “software”)support = 1%, confidence = 75%34数据挖掘功能数据挖掘功能(2)n分类和预测分类和预测n找出描述和识别类或概念的模型找出描述和识别类或概念的模型( 函数函数), 用于标号未知的对象的标号用于标号未知的对象的标号预测预测/Predict some unknown class labelsn例如根据气候对国家分类例如根据气候对国家分类, 或根据单位里程的耗油量对汽车分类或根据单位里程的耗油量对汽车分类n模型表示模型表示: 判定树判定树(decision-tree), 分类规则分类规则, 神经网络神经网络判别分析discriminat an

34、alysis有监督方法 supervised method/在已知对象分成若干类别并取得各种类别的一组观测样本，在此基础上根据某些准则（学习学习）建立判别式；然后对未知类别样本进行（判别）分类n预测预测: 预测某些未知或遗漏的数值值预测某些未知或遗漏的数值值/定量的定量的quantitative输出变量输出变量35数据挖掘功能数据挖掘功能(3)n聚类分析聚类分析Unsupervised learning (i.e., Class label is unknown)n类标号类标号(Class label) 未知未知: 对数据分组对数据分组, 形成新的类形成新的类. 例如例如, 对房屋分类对房屋分

35、类, 找出分布模式找出分布模式n聚类原则聚类原则: 最大化类内的相似性最大化类内的相似性, 最小化类间的相似性最小化类间的相似性36数据挖掘功能数据挖掘功能(4)n孤立点孤立点(Outlier)分析分析n孤立点孤立点: 一个数据对象一个数据对象, 它它 与数据的一般行为不一致与数据的一般行为不一致n孤立点可以被视为例外孤立点可以被视为例外, 但对于欺骗检测和罕见事件分析但对于欺骗检测和罕见事件分析, 它是相当有用的它是相当有用的n趋势和演变分析趋势和演变分析n趋势和偏离趋势和偏离: 回归分析回归分析n序列模式挖掘序列模式挖掘, 周期性分析周期性分析ne.g., first buy digita

36、l camera, then buy large SD memory cardsn基于相似的分析基于相似的分析nApproximate and consecutive motifs3737数据挖掘功能数据挖掘功能(5) -Structure and Network AnalysisnGraph miningnFinding frequent subgraphs (e.g., chemical compounds), trees (XML), substructures (web fragments)nInformation network analysisnSocial networks: a

37、ctors (objects, nodes) and relationships (edges)ne.g., author networks in CS, terrorist networksnMultiple heterogeneous networksnA person could be multiple information networks: friends, family, classmates, nLinks carry a lot of semantic information: Link miningnWeb miningnWeb is a big information n

38、etwork: from PageRank to GooglenAnalysis of Web information networksnWeb community discovery, opinion mining, usage mining, 38Top-10 Most Popular DM Algorithms:18 Identified Candidates (I)n Classificationn#1. C4.5: Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann., 1993.n#2. CART:

39、 L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, 1984.n#3. K Nearest Neighbours (kNN): Hastie, T. and Tibshirani, R. 1996. Discriminant Adaptive Nearest Neighbor Classification. TPAMI. 18(6)n#4. Naive Bayes Hand, D.J., Yu, K., 2001. Idiots Bayes: Not

40、 So Stupid After All? Internat. Statist. Rev. 69, 385-398.nStatistical Learningn#5. SVM: Vapnik, V. N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag.n #6. EM: McLachlan, G. and Peel, D. (2000). Finite Mixture Models. J. Wiley, New York. Association Analysisn#7. Apriori: Rakesh Agr

41、awal and Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In VLDB 94.n#8. FP-Tree: Han, J., Pei, J., and Yin, Y. 2000. Mining frequent patterns without candidate generation. In SIGMOD 00.39The 18 Identified Candidates (II)nLink Miningn#9. PageRank: Brin, S. and Page, L. 1998. The

42、anatomy of a large-scale hypertextual Web search engine. In WWW-7, 1998.n#10. HITS: Kleinberg, J. M. 1998. Authoritative sources in a hyperlinked environment. SODA, 1998.nClusteringn#11. K-Means: MacQueen, J. B., Some methods for classification and analysis of multivariate observations, in Proc. 5th

43、 Berkeley Symp. Mathematical Statistics and Probability, 1967.n#12. BIRCH: Zhang, T., Ramakrishnan, R., and Livny, M. 1996. BIRCH: an efficient data clustering method for very large databases. In SIGMOD 96.nBagging and Boostingn#13. AdaBoost: Freund, Y. and Schapire, R. E. 1997. A decision-theoretic

44、 generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci. 55, 1 (Aug. 1997), 119-139.40The 18 Identified Candidates (III)nSequential Patternsn#14. GSP: Srikant, R. and Agrawal, R. 1996. Mining Sequential Patterns: Generalizations and Performance Improvements. 5th Inte

45、rnational Conference on Extending Database Technology, 1996.n#15. PrefixSpan: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. Hsu. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In ICDE 01.nIntegrated Miningn#16. CBA: Liu, B., Hsu, W. an

46、d Ma, Y. M. Integrating classification and association rule mining. KDD-98. nRough Setsn#17. Finding reduct: Zdzislaw Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Norwell, MA, 1992nGraph Miningn#18. gSpan: Yan, X. and Han, J. 2002. gSpan: Graph-Based S

47、ubstructure Pattern Mining. In ICDM 02.41Top-10 Algorithm Finally Selected at ICDM06n#1: C4.5 (61 votes)n#2: K-Means (60 votes)n#3: SVM (58 votes)n#4: Apriori (52 votes)n#5: EM (48 votes)n#6: PageRank (46 votes)n#7: AdaBoost (45 votes)n#7: kNN (45 votes)n#7: Naive Bayes (45 votes)n#10: CART (34 vote

48、s)42挖掘出的所有模式都是有趣的吗挖掘出的所有模式都是有趣的吗?n一个数据挖掘系统一个数据挖掘系统/查询可以挖掘出数以千计的模式查询可以挖掘出数以千计的模式, 并非所并非所有的模式都是有趣的有的模式都是有趣的n建议的方法建议的方法: 以人为中心以人为中心, 基于查询的基于查询的, 聚焦的挖掘聚焦的挖掘n兴趣度度量兴趣度度量 : 一个模式是一个模式是 有趣的有趣的 如果它是如果它是 易于被人理解的易于被人理解的, 在某种程度上在某种程度上在新的或测试数据上是有效的在新的或测试数据上是有效的, 潜在有用的潜在有用的, 新新颖的颖的, 或或验证了用户希望证实的某种假设验证了用户希望证实的某种假设n

49、客观与主观的兴趣度度量客观与主观的兴趣度度量 :n客观客观: 基于模式的统计和结构基于模式的统计和结构, 例如例如, 支持度支持度, 置信度置信度, 等等.n主观主观: 基于用户对数据的确信基于用户对数据的确信, 例如例如, 出乎意料出乎意料, 新颖性新颖性, 可可行动性行动性(actionability), 等等.43能够只发现有趣的模式吗能够只发现有趣的模式吗?n发现所有有趣的模式发现所有有趣的模式: 完全性完全性n数据挖掘系统能够发现数据挖掘系统能够发现所有所有有趣的模式吗有趣的模式吗? n关联关联 vs. 分类分类 vs. 聚类聚类n仅搜索有趣的模式仅搜索有趣的模式: 优化优化n数据挖

50、掘系统能够数据挖掘系统能够仅仅发现有趣的模式吗发现有趣的模式吗? n方法方法n首先找出所有模式首先找出所有模式, 然后过滤掉不是有趣的那些然后过滤掉不是有趣的那些.n仅产生有趣的模式仅产生有趣的模式 挖掘查询优化挖掘查询优化44数据挖掘数据挖掘: 多学科交叉多学科交叉数据挖掘数据挖掘数据库技术数据库技术统计学统计学其它学科其它学科信息科学信息科学机器学习机器学习可视化可视化45数据挖掘分类数据挖掘分类n一般功能一般功能n描述式数据挖掘描述式数据挖掘描述数据的一般性质描述数据的一般性质n预测式数据挖掘预测式数据挖掘对数据进行推断，做预测对数据进行推断，做预测n不同的角度不同的角度,不同的分类不同

51、的分类n待挖掘的数据库类型待挖掘的数据库类型 n待发现的知识类型待发现的知识类型n所用的技术类型所用的技术类型n所适合的应用类型所适合的应用类型46数据挖掘分类的多维视图数据挖掘分类的多维视图n待挖掘的数据库待挖掘的数据库n关系的关系的, 事务的事务的, 面向对象的面向对象的, 对象对象-关系的关系的, 主动的主动的, 空间的空间的, 时间序列的时间序列的, 文本文本的的, 多媒体的多媒体的, 异种的异种的, 遗产的遗产的, WWW, 等等.n所挖掘的知识所挖掘的知识n特征特征, 区分区分, 关联关联, 分类分类, 聚类聚类, 趋势趋势, 偏离和孤立点分析偏离和孤立点分析, 等等.n多多/集成

52、的功能集成的功能, 和多层次上的挖掘和多层次上的挖掘n所用技术所用技术n面向数据库的面向数据库的, 数据仓库数据仓库 (OLAP), 机器学习机器学习, 统计学统计学, 可视化可视化, 神经网络神经网络, 等等.n适合的应用适合的应用n零售零售, 电讯电讯, 银行银行, 欺骗分析欺骗分析, DNA 挖掘挖掘, 股票市场分析股票市场分析, Web 挖掘挖掘, Web日志分析日志分析, 等等47OLAP挖掘挖掘: 数据挖掘与数据仓库的集成数据挖掘与数据仓库的集成n数据挖掘系统数据挖掘系统, DBMS, 数据仓库系统的耦合数据仓库系统的耦合 n不耦合不耦合, 松耦合松耦合, 半紧密耦合半紧密耦合,

53、紧密耦合紧密耦合n联机分析挖掘联机分析挖掘n挖掘与挖掘与 OLAP 技术的集成技术的集成n交互挖掘多层知识交互挖掘多层知识n通过下钻通过下钻, 上卷上卷, 转轴转轴, 切片切片, 切块等操作切块等操作, 在不同的抽象层挖掘知识和在不同的抽象层挖掘知识和模式的必要性模式的必要性.n多种挖掘功能的集成多种挖掘功能的集成n 特征分类特征分类, 先聚类再关联先聚类再关联48OLAM 的结构的结构数据仓库数据仓库元数据元数据MDDBOLAM引擎引擎OLAP引擎引擎用户用户 GUI API数据立方体数据立方体 API数据库数据库 API数据清理数据清理数据集成数据集成第第3层层OLAP/OLAM第第2层层

54、MDDB第第1层层数据存储数据存储第第4层层用户界面用户界面过滤和集成过滤和集成过滤过滤Databases挖掘查询挖掘查询挖掘结果挖掘结果OLAM(数据联机分析挖掘)是OLAP(联机分析处理)与DM(数据挖掘)相结合而形成的一个新的体系结构。 49Why Data Mining Query Language? nAutomated vs. query-driven?nFinding all the patterns autonomously in a database?unrealistic because the patterns could be too many but unintere

55、stingnData mining should be an interactive process nUser directs what to be minednUsers must be provided with a set of primitives(原语原语,基本要素基本要素) to be used to communicate with the data mining systemnIncorporating these primitives in a data mining query languagenMore flexible user interaction nFounda

56、tion for design of graphical user interfacenStandardization of data mining industry and practice50数据挖据查询语言数据挖据查询语言n通过数据挖掘查询语言，数据挖掘任务可以通过查询的形式通过数据挖掘查询语言，数据挖掘任务可以通过查询的形式输入到数据挖掘系统中。输入到数据挖掘系统中。 n定义数据挖据查询语言的优势定义数据挖据查询语言的优势51Primitives that Define a Data Mining TasknTask-relevant datanDatabase or data war

57、ehouse namenDatabase tables or data warehouse cubesnCondition for data selectionnRelevant attributes or dimensionsnData grouping criterianType of knowledge to be minednCharacterization, discrimination, association, classification, prediction, clustering, outlier analysis, other data mining tasksnBac

58、kground knowledgenPattern interestingness measurementsnVisualization/presentation of discovered patterns52数据挖据原语数据挖据原语53Primitive 3: Background KnowledgenA typical kind of background knowledge: Concept hierarchiesnSchema hierarchynE.g., street city province_or_state countrynSet-grouping hierarchynE.

59、g., 20-39 = young, 40-59 = middle_agednOperation-derived hierarchynemail address: hagonzalcs.uiuc.edulogin-name department university countrynRule-based hierarchynlow_profit_margin (X) = price(X, P1) and cost (X, P2) and (P1 - P2) $5054Primitive 4: Pattern Interestingness Measure nSimplicitye.g., (a

60、ssociation) rule length, (decision) tree sizenCertaintye.g., confidence, P(A|B) = #(A and B)/ #(B), classification reliability or accuracy, certainty factor, rule strength, rule quality, discriminating weight, etc.nUtilitypotential usefulness, e.g., support (association), noise threshold (descriptio

61、n)nNoveltynot previously known, surprising (used to remove redundant rules, e.g., Illinois vs. Champaign rule implication support ratio)55Primitive 5: Presentation of Discovered PatternsnDifferent backgrounds/usages may require different forms of representationnE.g., rules, tables, crosstabs, pie/ba

62、r chart, etc.nConcept hierarchy is also important nDiscovered knowledge might be more understandable when represented at high level of abstraction nInteractive drill up/down, pivoting, slicing and dicing provide different perspectives to datanDifferent kinds of knowledge require different representa

63、tion: association, classification, clustering, etc.56An Example Query in DMQL57数据挖掘的主要问题数据挖掘的主要问题(1)n挖掘方法和用户交互挖掘方法和用户交互n在数据库中挖掘不同类型的知识在数据库中挖掘不同类型的知识n在多个抽象层的交互式知识挖掘在多个抽象层的交互式知识挖掘n结合背景知识结合背景知识n数据挖掘语言和启发式数据挖掘数据挖掘语言和启发式数据挖掘 n数据挖掘结果的表示和可视化数据挖掘结果的表示和可视化n处理噪音和不完全数据处理噪音和不完全数据n模式评估模式评估: 兴趣度问题兴趣度问题n性能和可伸缩性性能和

64、可伸缩性( scalability)n数据挖掘算法的性能和可伸缩性数据挖掘算法的性能和可伸缩性n并行并行, 分布和增量的挖掘方法分布和增量的挖掘方法58数据挖掘的主要问题数据挖掘的主要问题(2)n数据类型的多样性问题数据类型的多样性问题n处理关系的和复杂类型的数据处理关系的和复杂类型的数据n从异种数据库和全球信息系统从异种数据库和全球信息系统 (WWW)挖掘信息挖掘信息n应用和社会效果问题应用和社会效果问题n发现知识的应用发现知识的应用n特定领域的数据挖掘工具特定领域的数据挖掘工具n智能查询回答智能查询回答n过程控制和决策制定过程控制和决策制定n发现知识与已有知识的集成发现知识与已有知识的集成

65、: 知识融合问题知识融合问题n数据安全数据安全, 完整和私有的保护完整和私有的保护59小结小结n数据挖掘数据挖掘: 从大量数据中发现有趣的模式从大量数据中发现有趣的模式n数据库技术的自然进化数据库技术的自然进化, 具有巨大需求和广泛应用具有巨大需求和广泛应用nKDD 过程包括数据清理过程包括数据清理, 数据集成数据集成, 数据选择数据选择, 变换变换, 数据挖掘数据挖掘, 模式评估模式评估, 和知识表示和知识表示n挖掘可以在各种数据存储上进行挖掘可以在各种数据存储上进行n数据挖掘功能数据挖掘功能: 特征特征, 区分区分, 关联关联, 分类分类, 聚类聚类, 孤立点孤立点 和趋势分析和趋势分析,

66、 等等.n数据挖掘系统的分类数据挖掘系统的分类n数据挖掘的主要问题数据挖掘的主要问题60参考文献参考文献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

67、. 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.61谢谢大家谢谢大家!