数据挖掘课件-第一课.ppt

数据仓库与数据挖掘 信息学院李翠平 2020年2月18日星期二 2 CourseOutline IntroductionFrequentPatternsClassificationClusterAnalysisOurlierDetectionDataWarehouseandOLAPTechnologyforDataMiningAdvancedtopicindataminingStreamdataminingTime seriesandsequentialpatternminingGraphandstructuredpatternminingSpatiotemporalandmultimediadataminingMulti relationalandcross databasedataminingSocialnetworkanalysisTextandWebminingOtherinterestingdataminingtopicsDataMiningApplications Examples 分组报告 3 课程要求 成绩评估 参考书 课程要求 按时上课和完成作业 积极参与课堂讨论 评估成绩 平时 50 考勤 课堂报告期末 50 参考书 JiaweiHan DataMining ConceptandTechniques 数据库视角看数据挖掘 DavidJ Hand等 PrinciplesofDataMining 统计视角看数据挖掘 王珊 李翠平等 数据仓库与数据分析原理 2020年2月18日星期二 4 Introduction Motivation Whydatamining Whatisdatamining DataMining Onwhatkindofdata DataminingfunctionalityAreallthepatternsinteresting DataMiningFrameworkIntegrationofDataMiningandDataWarehousingMajordataminingconference 2020年2月18日星期二 5 NecessityIstheMotherofInvention DataexplosionproblemAutomateddatacollectiontoolsandmaturedatabasetechnologyleadtotremendousamountsofdataaccumulatedand ortobeanalyzedindatabases datawarehouses andotherinformationrepositoriesWearedrowningindata butstarvingforknowledge Solution DatawarehousinganddataminingDatawarehousingandon lineanalyticalprocessingMininginterestingknowledge rules regularities patterns constraints fromdatainlargedatabases 2020年2月18日星期二 6 EvolutionofDatabaseTechnology 1960s Datacollection databasecreation IMSandnetworkDBMS1970s Relationaldatamodel relationalDBMSimplementation1980s RDBMS advanceddatamodels extended relational OO deductive etc Application orientedDBMS spatial scientific engineering etc 1990s Datamining datawarehousing multimediadatabases andWebdatabases2000sStreamdatamanagementandminingDatamininganditsapplicationsWebtechnology XML dataintegration andglobalinformationsystems 2020年2月18日星期二 7 WhatIsDataMining Datamining knowledgediscoveryfromdata Extractionofinteresting non trivial implicit previouslyunknownandpotentiallyuseful patternsorknowledgefromhugeamountofdataDatamining amisnomer AlternativenamesKnowledgediscovery mining indatabases KDD knowledgeextraction data patternanalysis dataarcheology datadredging informationharvesting businessintelligence etc Watchout Iseverything datamining Deductive queryprocessing ExpertsystemsorsmallML statisticalprograms 2020年2月18日星期二 8 数据挖掘与KDD 也可以把数据挖掘作为KDD的一个步骤 KDD是一个以知识使用者为中心 人机交互的探索过程 包括了在指定的数据库中用数据挖掘算法提取模型 以及围绕数据挖掘所进行的预处理和结果表达等一系列的步骤 尽管数据挖掘是整个过程的中心 但它通常只占KDD过程15 25 的工作量 2020年2月18日星期二 9 DataMining OnWhatKindsofData RelationaldatabaseDatawarehouseTransactionaldatabaseAdvanceddatabaseandadvancedapplicationsObject relationaldatabasesTemporaldatabasesandtime seriesdatabasesSpatialdatabasesandspatiotemporaldatabasesTextdatabasesandmultimediadatabaseHeterogeneousdatabasesandlegacydatabasesDatastreamsTheWorld WideWeb 2020年2月18日星期二 10 数据挖掘的特点 1 第一 数据挖掘的数据源必须是真实的 数据挖掘所处理的数据通常是已经存在的真实数据 如超市业务数据 而不是为了进行数据分析而专门收集的数据 因此 数据收集本身不属于数据挖掘所关注的焦点 这是数据挖掘区别于大多数统计任务的特征之一 2020年2月18日星期二 11 数据挖掘的特点 2 第二 数据挖掘所处理的数据必须是海量的 如果数据集很小的话 采用单纯的统计分析方法就可以了 但是 当数据集很大时 会面临许多新的问题 诸如 数据的有效存储 快速访问 合理表示等 2020年2月18日星期二 12 数据挖掘的特点 3 第三 查询一般是决策制定者 用户 提出的随机查询 查询要求灵活 往往不能形成精确的查询要求 要靠数据挖掘技术来寻找可能的查询结果 2020年2月18日星期二 13 数据挖掘的特点 4 第四 挖掘出来的知识一般是不能预知的 数据挖掘发现的是潜在的 新颖的知识 这些知识在特定环境下是可以接受 可以理解 可以运用的 但不是放之四海皆准的 2020年2月18日星期二 14 DataMiningFunctionalities Conceptdescription CharacterizationanddiscriminationGeneralize summarize andcontrastdatacharacteristics e g dryvs wetregionsAssociation correlationandcausality Diaper Beer 0 5 75 Correlationorcausality ClassificationandPredictionConstructmodels functions thatdescribeanddistinguishclassesorconceptsforfuturepredictionE g classifycountriesbasedonclimate orclassifycarsbasedongasmileagePresentation decision tree classificationrule neuralnetworkPredictsomeunknownormissingnumericalvalues 2020年2月18日星期二 15 DataMiningFunctionalities 2 ClusteranalysisClasslabelisunknown Groupdatatoformnewclasses e g clusterhousestofinddistributionpatternsMaximizingintra classsimilarity minimizinginterclasssimilarityOutlieranalysisOutlier adataobjectthatdoesnotcomplywiththegeneralbehaviorofthedataNoiseorexception No usefulinfrauddetection rareeventsanalysisTrendandevolutionanalysisTrendanddeviation regressionanalysisSequentialpatternmining periodicityanalysisSimilarity basedanalysisOtherpattern directedorstatisticalanalyses 2020年2月18日星期二 16 AreAllthe Discovered PatternsInteresting Dataminingmaygeneratethousandsofpatterns NotallofthemareinterestingSuggestedapproach Human centered query based focusedminingInterestingnessmeasuresApatternisinterestingifitiseasilyunderstoodbyhumans validonnewortestdatawithsomedegreeofcertainty potentiallyuseful novel orvalidatessomehypothesisthatauserseekstoconfirmObjectivevs subjectiveinterestingnessmeasuresObjective basedonstatisticsandstructuresofpatterns e g support confidence etc Subjective basedonuser sbeliefinthedata e g unexpectedness novelty actionability etc 2020年2月18日星期二 17 DataMining AGeneralizedFramework Applications Techniques Principles CustomerRelationshipManagement CRM WebpagesSearchesandAnalysisNetworkSecurityGeographicalDataAnalysisGenomicDatabase AssociationrulesdiscoverySequentialPatternDiscoveryClusteranalysisOutlierDetectionClassifierBuildingDataCube DataWarehouseConstructionVisualization 2020年2月18日星期二 18 数据挖掘的分类 1 根据挖掘的数据库类型分类数据库系统本身可以根据不同的标准分类 例如 按照数据模型或处理的数据所涉及的应用类型分类 每一类可能需要不同的数据挖掘技术 例如 根据数据模型分类 可以有关系的 面向对象的 对象 关系的 或数据仓库的数据挖掘 如果根据所处理的数据的特定类型分类 有空间的 时间序列的 文本的 多媒体 或Web数据等数据挖掘 2020年2月18日星期二 19 数据挖掘的分类 2 根据挖掘的知识类型分类例如特征分析 关联分析 分类分析 聚类分析 异常点分析 趋势和演化分析 偏差分析 类似性分析等 此外 数据挖掘也可以根据所挖掘的知识的粒度或抽象级别进行区分 包括泛化知识 在高抽象层 原始层知识 在原始数据层 或多层知识 考虑若干抽象层 2020年2月18日星期二 20 数据挖掘的分类 3 根据所用的技术分类这些技术可以根据用户交互程度 例如 自动系统 交互探查系统 查询驱动系统 或所用的数据分析方法 例如 面向数据库或数据仓库的技术 机器学习 统计 可视化 模式识别 神经网络等等 描述 复杂的数据挖掘通常采用多种数据挖掘技术 或采用有效的 集成的技术 以综合若干不同方法的优点 2020年2月18日星期二 21 数据挖掘的分类 4 根据数据挖掘的应用领域分类例如 可能有些数据挖掘方法特别适合财政 电讯 有些数据挖掘方法特别适合DNA 股票市场等 不同的应用有适合该应用不同的数据挖掘方法 而通用的 全面的数据挖掘可能并不适合特定领域的挖掘任务 2020年2月18日星期二 22 数据挖掘算法太多 1 聚类分析 基于划分的算法基于层次的算法K Means K Medoids K Modes K Prototypes CLARA CLARANS focusedCLARANS基于密度的算法基于方格的算法基于模型的算法 2020年2月18日星期二 23 数据挖掘算法太多 2 分类分析决策树算法ID3 C4 5 EC4 5 PC4 5 CHAID CART Elisee SIPINA QR MDL等近20种贝叶斯算法支持向量机人工神经网络 2020年2月18日星期二 24 数据挖掘算法的组件化思想 1 与此同时 每年仍有大批新的算法产生 对数据挖掘初学者来说 要搞清这些算法之间的区别和联系 是非常困难 但又是必须的 数据挖掘算法的组件化思想 许多著名的数据挖掘算法都是由五个 标准组件 构成的 即 模型或模式结构数据挖掘任务评分函数搜索和优化方法数据管理策略 2020年2月18日星期二 25 数据挖掘算法的组件化思想 2 每一种组件都蕴含着一些非常通用的系统原理 例如 广泛使用的评分函数有 似然 误差平方和 准确率等 掌握了每一种组件的基本原理之后 再来理解由不同组件 装配 起来的算法就变得相对轻松一些 而且 不同算法之间的比较也变得更加容易 因为能从组件这个层面看出算法之间的异同 2020年2月18日星期二 26 组件1 模型或模式结构 通过数据挖掘过程所得到的知识通常被称为模型 model 或模式 pattern 例如 线性回归模型层次聚类模型频繁序列模式等等 2020年2月18日星期二 27 组件1 模型或模式结构 模型是对整个数据集的高层次 全局性的描述或总结 例如 模型可以将数据集中的每一个对象分配到某个聚类中 模型是对现实世界的抽象描述例如 Y aX b就是一个简单的模型 其中X和Y是变量 a和c是模型的参数 2020年2月18日星期二 28 组件1 模型或模式结构 模式是局部的 它仅对一小部分数据做出描述 例如 购买商品A和B的人也可能经常购买C 就是一个模式 模式有可能只支持几个对象或对象的几个属性 2020年2月18日星期二 29 组件1 模型或模式结构 全局的模型和局部的模式是相互联系的 就好比一个硬币的两个面 例如 为了检测出数据集内的异常对象 局部模式 需要一种对数据集内正常对象的描述 全局模型 2020年2月18日星期二 30 组件1 模型或模式结构 模型和模式都有参数与之相关 如模型Y aX b的参数是a和b 模式 如果X c 则Y d的概率为p 的参数为c d和p 通常把参数不确定的模型叫做模型的结构 把参数不确定的模式叫做模式的结构 一般形式 一旦模型 模式 的参数被确定 便将这个特定的模型 模式 称为 已经拟合了的模型 模式 或者简称为模型 模式 2020年2月18日星期二 31 组件2 数据挖掘任务 根据数据分析者的目标 可以将数据挖掘任务分为 模式挖掘描述建模预测建模 2020年2月18日星期二 32 组件2 数据挖掘任务 模式挖掘 致力于从数据中寻找模式 比如寻找频繁模式 异常点等 频繁模式指在某个数据集中频繁出现的模式 这些模式可以是一个项集 一个子序列或者一个子结构 子图 例如 在交易数据集中 牛奶和面包经常在一起出现 称之为频繁的项集 又如 人们经常在购买了个人电脑之后 就会购买打印机 称之为频繁的子序列 在某些图 树或格结构中频繁出现的一些子图 子树或子格则被称为频繁的子结构 2020年2月18日星期二 33 组件2 数据挖掘任务 预测建模 根据现有数据先建立一个模型 然后应用这个模型来对未来的数据进行预测 当被预测的变量是范畴型 category 时 称之为分类 当被预测的变量是数量型 quantitative 时 称之为回归 分类模型有时也称作分类函数或分类器 分类的典型应用如 信用卡系统中的信用分级 市场调查 疗效诊断 寻找店址等 因为分类的过程中 用到了训练集 进行了学习 所以分类是一个有监督的学习过程 回归的典型应用如性能评测 概率估计等 2020年2月18日星期二 34 组件2 数据挖掘任务 描述建模 目标是描述数据的全局特征 描述和预测的关键区别是 预测的目标是唯一的变量 如信用等级 疾病种类等 而描述并不以单一的变量为中心 描述建模的典型例子是聚类分析 2020年2月18日星期二 35 组件3 评分函数 有了模型 模式 的结构之后 接下来的任务就是要根据数据集为模型 模式 选择合适的参数值 即将结构拟合到数据 由于模型 模式 代表的是函数的一般形式 它的参数空间非常大 可选的参数值有很多 那么什么样的参数值比较好呢 需要一个评价指标 这个评价指标就是评分函数 2020年2月18日星期二 36 组件3 评分函数 评分函数用来对数据集与模型 模式 的拟合程度进行评估 如果没有评分函数 就无法说出一个特定的已拟合的模型是否比另一个要好 或者说 就没有办法为模型 模式 选择出一套好的参数值来 常用的评分函数有 似然 likelihood 函数 误差平方和 准确率等 2020年2月18日星期二 37 组件3 评分函数 在为模型 模式 选择一个评分函数时 既要能够很好地拟合现有数据 又要避免过度拟合 对极端值过于敏感 同时还要使拟合后的模型 模式 尽量简洁 不存在绝对 正确 的模型 模式 所有模型 模式 都是对现有数据的一种近似 从这个角度来讲 如果模型 模式 没有随着现有数据的变化而剧烈变化 这个模型 模式 就是能够接受的了 换句话说 对数据的微小变化不太敏感的模型 模式 才是一个好的模型 模式 2020年2月18日星期二 38 组件4 搜索和优化方法 评分函数衡量了提出的模型 模式 与现有数据集的拟合程度 搜索和优化的目标是确定模型 模式 的结构及其参数值 以使评分函数达到最小值 或最大值 平方差最小准确率最高 2020年2月18日星期二 39 组件4 搜索和优化方法 如果模型 模式 的结构已经确定 则搜索将在参数空间内进行 目的是针对这个固定的模型 模式 结构 优化评分函数 如果模型 模式 的结构还没有确定的话 例如 存在一族不同的模型 模式 结构 那么搜索既要针对结构空间又要针对和这些结构相联系的参数空间进行 针对特定的模型 发现其最佳参数值的过程通常被称为优化问题 而从潜在的模型 模式 族中发现最佳模型 模式 结构的过程通常被称为搜索问题 2020年2月18日星期二 40 组件4 搜索和优化方法 常用的优化方法有 爬山 Hill Climing 最陡峭下降 Steepest Descend 期望最大化 Expectation Maximization EM 常用的搜索方法有 贪婪搜索分支界定宽度 深度 优先遍历 2020年2月18日星期二 41 组件5 数据管理策略 传统的统计和机器学习算法都假定数据是可以全部放入内存的 所以不太关心数据管理技术 但是 对于数据挖掘工作者来说 GB甚至TB数量级的数据是常见的 由于外存的访问速度要慢的多 直接将传统的内存算法应用于这些外存数据 性能将变得非常差 因此 针对海量数据 应该设计有效的数据组织和索引技术 或者通过采样 近似等手段 来减少数据的扫描次数 从而提高数据挖掘算法的效率 2020年2月18日星期二 42 组件化思想的应用 在实践中 数据挖掘算法的组件化思想是非常有用的 它通过将算法分解成一些核心组件而阐明了算法的实现机制 更重要的是 该观点强调了算法的本质 而不仅仅是算法的罗列 当面对一个新的应用时 数据挖掘人员应该从组件的角度 根据应用需求 考虑应该选取哪些组件 来组成一个新的算法 而不是考虑选取哪个现成的算法 2020年2月18日星期二 43 组件化思想的应用 确定模型 模式 结构和评分函数的过程通常由人来完成而优化评分函数的过程通常需要计算机辅助来实现 实践中 通常要根据前一次的计算结果来改进模型 模式 结构和评分函数 所以整个过程要重复很多次 2020年2月18日星期二 44 组件化思想的应用 有趣的是 不同的研究团体将注意力放在不同的数据挖掘算法组件上 统计学家强调推理过程 关注模型 模式 评分函数 参数估计等 很少突出计算效率问题 而从事数据挖掘的计算机科学家则更注重高效的空间搜索和数据管理 不太关心模型 模式 或评分函数是否合适 2020年2月18日星期二 45 组件化思想的应用 实际上 一个数据挖掘算法的所有组件都是至关重要的 对于小的数据集 模型 模式 的解释和预测能力相对于计算效率来说可能要重要的多 但是 随着数据集的增大 计算效率将变得越来越重要 对于海量数据 必须在模型 模式 的完备性和计算效率之间进行平衡 以期对现有数据达到某种程度的拟合 2020年2月18日星期二 46 Examples decisiontree clusters associationrules structureofthemodelorpattern NA NA NA datamanagementtechnique greedy gradientdescent breadthfirstwithpruning search optimizationmethod accuracy informationgain squareerror support confidence scorefunction allpossiblecombinationofdecisiontreesize potentiallyinfinity choiceofanykpointsascentersize infinity latticeofallpossiblecombinationofitemssize 2m searchspace classification clustering rulepatterndiscovery task ID3 K means Apriori 2020年2月18日星期二 47 IntegrationofDataMiningandDataWarehousing Dataminingsystems DBMS DatawarehousesystemscouplingNocoupling loose coupling semi tight coupling tight couplingOn lineanalyticalminingdataintegrationofminingandOLAPtechnologiesInteractiveminingmulti levelknowledgeNecessityofminingknowledgeandpatternsatdifferentlevelsofabstractionbydrilling rolling pivoting slicing dicing etc IntegrationofmultipleminingfunctionsCharacterizedclassification firstclusteringandthenassociation 2020年2月18日星期二 48 Architecture TypicalDataMiningSystem DataWarehouse Datacleaning dataintegration Filtering Databases Databaseordatawarehouseserver Dataminingengine Patternevaluation Graphicaluserinterface Knowledge base 2020年2月18日星期二 49 ABriefHistoryofDataMiningSociety 1989IJCAIWorkshoponKnowledgeDiscoveryinDatabases Piatetsky Shapiro KnowledgeDiscoveryinDatabases G Piatetsky ShapiroandW Frawley 1991 1991 1994WorkshopsonKnowledgeDiscoveryinDatabasesAdvancesinKnowledgeDiscoveryandDataMining U Fayyad G Piatetsky Shapiro P Smyth andR Uthurusamy 1996 1995 1998InternationalConferencesonKnowledgeDiscoveryinDatabasesandDataMining KDD 95 98 JournalofDataMiningandKnowledgeDiscovery 1997 1998ACMSIGKDD SIGKDD 1999 2001conferences andSIGKDDExplorationsMoreconferencesondataminingPAKDD 1997 PKDD 1997 SIAM DataMining 2001 IEEE ICDM 2001 etc 2020年2月18日星期二 50 ConferencesandJournalsonDataMining KDDConferencesACMSIGKDDInt Conf onKnowledgeDiscoveryinDatabasesandDataMining KDD SIAMDataMiningConf SDM IEEE Int Conf onDataMining ICDM Conf onPrinciplesandpracticesofKnowledgeDiscoveryandDataMining PKDD Pacific AsiaConf onKnowledgeDiscoveryandDataMining PAKDD OtherrelatedconferencesACMSIGMODVLDB IEEE ICDEWWW SIGIRICML CVPR NIPSJournalsDataMiningandKnowledgeDiscovery DAMIorDMKD IEEETrans OnKnowledgeandDataEng TKDE KDDExplorations 2020年2月18日星期二 51 WheretoFindReferences DBLP CiteSeer Google DataminingandKDD SIGKDD CDROM Conferences ACM SIGKDD IEEE ICDM SIAM DM PKDD PAKDD etc Journal DataMiningandKnowledgeDiscovery KDDExplorationsDatabasesystems SIGMOD ACMSIGMODAnthology CDROM Conferences ACM SIGMOD ACM PODS VLDB IEEE ICDE EDBT ICDT DASFAAJournals IEEE TKDE ACM TODS TOIS JIIS J ACM VLDBJ Info Sys etc AI MachineLearningConferences Machinelearning ML AAAI IJCAI COLT LearningTheory CVPR NIPS etc Journals MachineLearning ArtificialIntelligence KnowledgeandInformationSystems IEEE PAMI etc WebandIRConferences SIGIR WWW CIKM etc Journals WWW InternetandWebInformationSystems StatisticsConferences JointStat Meeting etc Journals Annalsofstatistics etc VisualizationConferenceproceedings CHI ACM SIGGraph etc Journals IEEETrans visualizationandcomputergraphics etc 2020年2月18日星期二 52 Reference http www cs uiuc edu homes hanj Jiaweihan slectureppt p nus edu sg atung AnthonyTung slectureppt T DasuandT Johnson ExploratoryDataMiningandDataCleaning JohnWiley Sons 2003U M Fayyad G Piatetsky Shapiro P Smyth andR Uthurusamy AdvancesinKnowledgeDiscoveryandDataMining AAAI MITPress 1996U Fayyad G Grinstein andA Wierse InformationVisualizationinDataMiningandKnowledgeDiscovery MorganKaufmann 2001J HanandM Kamber DataMining ConceptsandTechniques 2nded MorganKaufmann 2005D J Hand H Mannila andP Smyth PrinciplesofDataMining MITPress 2001T Hastie R Tibshirani andJ Friedman TheElementsofStatisticalLearning DataMining Inference andPrediction Springer Verlag 2001T M Mitchell MachineLearning McGrawHill 1997G Piatetsky ShapiroandW J Frawley KnowledgeDiscoveryinDatabases AAAI MITPress 1991S M WeissandN Indurkhya PredictiveDataMining MorganKaufmann 1998I H WittenandE Frank DataMining PracticalMachineLearningToolsandTechniqueswithJavaImplementations 2nded MorganKaufmann 2005