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

数据仓库与数据挖掘,信息学院 李翠平,2023/8/15,Data Mining:Concepts and Techniques,2,Course Outline,IntroductionFrequent PatternsClassification Cluster AnalysisOurlier DetectionData Warehouse and OLAP Technology for Data MiningAdvanced topic in data miningStream data mining Time-series and sequential pattern mining Graph and structured pattern miningSpatiotemporal and multimedia data miningMulti-relational and cross-database data miningSocial network analysis Text and Web mining Other interesting data mining topicsData Mining Applications&Examples(分组报告),2023/8/15,Data Mining:Concepts and Techniques,3,课程要求、成绩评估、参考书,课程要求：按时上课和完成作业，积极参与课堂讨论，评估成绩：平时（50)：考勤+课堂报告期末（50)：参考书：Jiawei Han:Data Mining:Concept and Techniques（数据库视角看数据挖掘）David J.Hand等，Principles of Data Mining（统计视角看数据挖掘）王珊，李翠平等，数据仓库与数据分析原理,2023/8/15,Data Mining:Concepts and Techniques,4,Introduction,Motivation:Why data mining?What is data mining?Data Mining:On what kind of data?Data mining functionalityAre all the patterns interesting?Data Mining FrameworkIntegration of Data Mining and Data WarehousingMajor data mining conference,2023/8/15,Data Mining:Concepts and Techniques,5,Necessity Is the Mother of Invention,Data explosion problem Automated data collection tools and mature database technology lead to tremendous amounts of data accumulated and/or to be analyzed in databases,data warehouses,and other information repositories We are drowning in data,but starving for knowledge!Solution:Data warehousing and data miningData warehousing and on-line analytical processingMining interesting knowledge(rules,regularities,patterns,constraints)from data in large databases,2023/8/15,Data Mining:Concepts and Techniques,6,Evolution of Database Technology,1960s:Data collection,database creation,IMS and network DBMS1970s:Relational data model,relational DBMS implementation1980s:RDBMS,advanced data models(extended-relational,OO,deductive,etc.)Application-oriented DBMS(spatial,scientific,engineering,etc.)1990s:Data mining,data warehousing,multimedia databases,and Web databases2000sStream data management and miningData mining and its applicationsWeb technology(XML,data integration)and global information systems,2023/8/15,Data Mining:Concepts and Techniques,7,What Is Data Mining?,Data mining(knowledge discovery from data)Extraction of interesting(non-trivial,implicit,previously unknown and potentially useful)patterns or knowledge from huge amount of dataData mining:a misnomer?Alternative namesKnowledge discovery(mining)in databases(KDD),knowledge extraction,data/pattern analysis,data archeology,data dredging,information harvesting,business intelligence,etc.Watch out:Is everything“data mining”?(Deductive)query processing.Expert systems or small ML/statistical programs,2023/8/15,Data Mining:Concepts and Techniques,8,数据挖掘与KDD,也可以把数据挖掘作为KDD的一个步骤。KDD 是一个以知识使用者为中心，人机交互的探索过程，包括了在指定的数据库中用数据挖掘算法提取模型，以及围绕数据挖掘所进行的预处理和结果表达等一系列的步骤。尽管数据挖掘是整个过程的中心，但它通常只占KDD 过程15%25%的工作量。,2023/8/15,Data Mining:Concepts and Techniques,9,Data Mining:On What Kinds of Data?,Relational databaseData warehouseTransactional databaseAdvanced database and advanced applications Object-relational databasesTemporal databases and time-series databases Spatial databases and spatiotemporal databasesText databases and multimedia databaseHeterogeneous databases and legacy databasesData streams The World-Wide Web,2023/8/15,Data Mining:Concepts and Techniques,10,数据挖掘的特点（1）,第一，数据挖掘的数据源必须是真实的。数据挖掘所处理的数据通常是已经存在的真实数据（如超市业务数据），而不是为了进行数据分析而专门收集的数据。因此，数据收集本身不属于数据挖掘所关注的焦点，这是数据挖掘区别于大多数统计任务的特征之一。,2023/8/15,Data Mining:Concepts and Techniques,11,数据挖掘的特点（2）,第二，数据挖掘所处理的数据必须是海量的。如果数据集很小的话，采用单纯的统计分析方法就可以了。但是，当数据集很大时，会面临许多新的问题，诸如，数据的有效存储、快速访问、合理表示等。,2023/8/15,Data Mining:Concepts and Techniques,12,数据挖掘的特点（3）,第三，查询一般是决策制定者（用户）提出的随机查询。查询要求灵活，往往不能形成精确的查询要求，要靠数据挖掘技术来寻找可能的查询结果。,2023/8/15,Data Mining:Concepts and Techniques,13,数据挖掘的特点（4）,第四，挖掘出来的知识一般是不能预知的，数据挖掘发现的是潜在的、新颖的知识。这些知识在特定环境下是可以接受、可以理解、可以运用的，但不是放之四海皆准的。,2023/8/15,Data Mining:Concepts and Techniques,14,Data Mining Functionalities,Concept description:Characterization and discriminationGeneralize,summarize,and contrast data characteristics,e.g.,dry vs.wet regionsAssociation(correlation and causality)Diaper Beer 0.5%,75%(Correlation or causality?)Classification and Prediction Construct models(functions)that describe and distinguish classes or concepts for future predictionE.g.,classify countries based on climate,or classify cars based on gas mileagePresentation:decision-tree,classification rule,neural networkPredict some unknown or missing numerical values,2023/8/15,Data Mining:Concepts and Techniques,15,Data Mining Functionalities(2),Cluster analysisClass label is unknown:Group data to form new classes,e.g.,cluster houses to find distribution patternsMaximizing intra-class similarity&minimizing interclass similarityOutlier analysisOutlier:a data object that does not comply with the general behavior of the dataNoise or exception?No!useful in fraud detection,rare events analysisTrend and evolution analysisTrend and deviation:regression analysisSequential pattern mining,periodicity analysisSimilarity-based analysisOther pattern-directed or statistical analyses,2023/8/15,Data Mining:Concepts and Techniques,16,Are All the“Discovered”Patterns Interesting?,Data mining may generate thousands of patterns:Not all of them are interestingSuggested approach:Human-centered,query-based,focused miningInterestingness measuresA pattern is interesting if it is easily understood by humans,valid on new or test data with some degree of certainty,potentially useful,novel,or validates some hypothesis that a user seeks to confirm Objective vs.subjective interestingness measuresObjective:based on statistics and structures of patterns,e.g.,support,confidence,etc.Subjective:based on users belief in the data,e.g.,unexpectedness,novelty,actionability,etc.,2023/8/15,Data Mining:Concepts and Techniques,17,Data Mining:A Generalized Framework,Applications,Techniques,Principles,Customer Relationship Management(CRM)Web pages Searches and Analysis Network SecurityGeographical Data AnalysisGenomic Database,Association rules discoverySequential Pattern DiscoveryCluster analysis Outlier DetectionClassifier BuildingData Cube/Data Warehouse ConstructionVisualization,2023/8/15,Data Mining:Concepts and Techniques,18,数据挖掘的分类（1）,根据挖掘的数据库类型分类数据库系统本身可以根据不同的标准分类，例如,按照数据模型或处理的数据所涉及的应用类型分类。每一类可能需要不同的数据挖掘技术。例如，根据数据模型分类，可以有关系的、面向对象的、对象-关系的、或数据仓库的数据挖掘。如果根据所处理的数据的特定类型分类，有空间的、时间序列的、文本的、多媒体、或Web数据等数据挖掘。,2023/8/15,Data Mining:Concepts and Techniques,19,数据挖掘的分类（2）,根据挖掘的知识类型分类例如特征分析、关联分析、分类分析、聚类分析、异常点分析、趋势和演化分析、偏差分析、类似性分析等。此外，数据挖掘也可以根据所挖掘的知识的粒度或抽象级别进行区分，包括泛化知识（在高抽象层），原始层知识（在原始数据层），或多层知识（考虑若干抽象层）。,2023/8/15,Data Mining:Concepts and Techniques,20,数据挖掘的分类（3）,根据所用的技术分类这些技术可以根据用户交互程度（例如，自动系统、交互探查系统、查询驱动系统）或所用的数据分析方法（例如，面向数据库或数据仓库的技术、机器学习、统计、可视化、模式识别、神经网络等等）描述。复杂的数据挖掘通常采用多种数据挖掘技术，或采用有效的、集成的技术，以综合若干不同方法的优点。,2023/8/15,Data Mining:Concepts and Techniques,21,数据挖掘的分类（4）,根据数据挖掘的应用领域分类例如，可能有些数据挖掘方法特别适合财政、电讯，有些数据挖掘方法特别适合DNA、股票市场等。不同的应用有适合该应用不同的数据挖掘方法。而通用的、全面的数据挖掘可能并不适合特定领域的挖掘任务。,2023/8/15,Data Mining:Concepts and Techniques,22,数据挖掘算法太多（1）,聚类分析：基于划分的算法基于层次的算法K-Means、K-Medoids、K-Modes、K-Prototypes、CLARA、CLARANS、focused CLARANS基于密度的算法基于方格的算法基于模型的算法,2023/8/15,Data Mining:Concepts and Techniques,23,数据挖掘算法太多（2）,分类分析决策树算法ID3、C4.5、EC4.5、PC4.5、CHAID、CART、Elisee、SIPINA、QR-MDL等近20种贝叶斯算法支持向量机人工神经网络,2023/8/15,Data Mining:Concepts and Techniques,24,数据挖掘算法的组件化思想(1),与此同时，每年仍有大批新的算法产生。对数据挖掘初学者来说，要搞清这些算法之间的区别和联系，是非常困难，但又是必须的。数据挖掘算法的组件化思想：许多著名的数据挖掘算法都是由五个“标准组件”构成的，即：模型或模式结构数据挖掘任务评分函数 搜索和优化方法数据管理策略,2023/8/15,Data Mining:Concepts and Techniques,25,数据挖掘算法的组件化思想(2),每一种组件都蕴含着一些非常通用的系统原理，例如，广泛使用的评分函数有：似然、误差平方和、准确率等。掌握了每一种组件的基本原理之后，再来理解由不同组件“装配”起来的算法就变得相对轻松一些。而且，不同算法之间的比较也变得更加容易，因为能从组件这个层面看出算法之间的异同。,2023/8/15,Data Mining:Concepts and Techniques,26,组件1：模型或模式结构,通过数据挖掘过程所得到的知识通常被称为模型（model）或模式(pattern)。例如:线性回归模型层次聚类模型频繁序列模式等等,2023/8/15,Data Mining:Concepts and Techniques,27,组件1：模型或模式结构,模型是对整个数据集的高层次、全局性的描述或总结。例如，模型可以将数据集中的每一个对象分配到某个聚类中。模型是对现实世界的抽象描述例如，Y=aX+b就是一个简单的模型，其中X和Y是变量，a和c是模型的参数。,2023/8/15,Data Mining:Concepts and Techniques,28,组件1：模型或模式结构,模式是局部的，它仅对一小部分数据做出描述。例如，购买商品A和B的人也可能经常购买C，就是一个模式。模式有可能只支持几个对象或对象的几个属性。,2023/8/15,Data Mining:Concepts and Techniques,29,组件1：模型或模式结构,全局的模型和局部的模式是相互联系的，就好比一个硬币的两个面。例如，为了检测出数据集内的异常对象（局部模式），需要一种对数据集内正常对象的描述（全局模型）。,2023/8/15,Data Mining:Concepts and Techniques,30,组件1：模型或模式结构,模型和模式都有参数与之相关，如模型Y=aX+b的参数是a和b。模式（如果Xc，则Yd的概率为p）的参数为c，d和p。通常把参数不确定的模型叫做模型的结构。把参数不确定的模式叫做模式的结构。（一般形式）一旦模型（模式）的参数被确定，便将这个特定的模型（模式）称为“已经拟合了的模型（模式）”，或者简称为模型（模式）,2023/8/15,Data Mining:Concepts and Techniques,31,组件2：数据挖掘任务,根据数据分析者的目标，可以将数据挖掘任务分为：模式挖掘描述建模预测建模,2023/8/15,Data Mining:Concepts and Techniques,32,组件2：数据挖掘任务,模式挖掘：致力于从数据中寻找模式，比如寻找频繁模式，异常点等。频繁模式指在某个数据集中频繁出现的模式，这些模式可以是一个项集、一个子序列或者一个子结构(子图)。例如，在交易数据集中，牛奶和面包经常在一起出现，称之为频繁的项集。又如，人们经常在购买了个人电脑之后，就会购买打印机，称之为频繁的子序列。在某些图、树或格结构中频繁出现的一些子图、子树或子格则被称为频繁的子结构。,2023/8/15,Data Mining:Concepts and Techniques,33,组件2：数据挖掘任务,预测建模：根据现有数据先建立一个模型，然后应用这个模型来对未来的数据进行预测。当被预测的变量是范畴型(category)时，称之为分类；当被预测的变量是数量型(quantitative)时，称之为回归。分类模型有时也称作分类函数或分类器。分类的典型应用如，信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等。因为分类的过程中，用到了训练集，进行了学习，所以分类是一个有监督的学习过程。回归的典型应用如性能评测、概率估计等。,2023/8/15,Data Mining:Concepts and Techniques,34,组件2：数据挖掘任务,描述建模：目标是描述数据的全局特征。描述和预测的关键区别是：预测的目标是唯一的变量，如信用等级、疾病种类等，而描述并不以单一的变量为中心。描述建模的典型例子是聚类分析。,2023/8/15,Data Mining:Concepts and Techniques,35,组件3：评分函数,有了模型（模式）的结构之后，接下来的任务就是要根据数据集为模型（模式）选择合适的参数值，即将结构拟合到数据。由于模型（模式）代表的是函数的一般形式，它的参数空间非常大，可选的参数值有很多。那么什么样的参数值比较好呢，需要一个评价指标，这个评价指标就是评分函数。,2023/8/15,Data Mining:Concepts and Techniques,36,组件3：评分函数,评分函数用来对数据集与模型（模式）的拟合程度进行评估。如果没有评分函数，就无法说出一个特定的已拟合的模型是否比另一个要好。或者说，就没有办法为模型（模式）选择出一套好的参数值来。常用的评分函数有：似然（likelihood）函数、误差平方和、准确率等。,2023/8/15,Data Mining:Concepts and Techniques,37,组件3：评分函数,在为模型（模式）选择一个评分函数时，既要能够很好地拟合现有数据，又要避免过度拟合（对极端值过于敏感），同时还要使拟合后的模型（模式）尽量简洁。不存在绝对“正确”的模型（模式），所有模型（模式）都是对现有数据的一种近似。从这个角度来讲，如果模型（模式）没有随着现有数据的变化而剧烈变化，这个模型（模式）就是能够接受的了。换句话说，对数据的微小变化不太敏感的模型（模式）才是一个好的模型（模式）。,2023/8/15,Data Mining:Concepts and Techniques,38,组件4：搜索和优化方法,评分函数衡量了提出的模型（模式）与现有数据集的拟合程度。搜索和优化的目标是确定模型（模式）的结构及其参数值，以使评分函数达到最小值（或最大值）。平方差最小准确率最高,2023/8/15,Data Mining:Concepts and Techniques,39,组件4：搜索和优化方法,如果模型（模式）的结构已经确定，则搜索将在参数空间内进行，目的是针对这个固定的模型（模式）结构，优化评分函数。如果模型（模式）的结构还没有确定的话（例如，存在一族不同的模型（模式）结构），那么搜索既要针对结构空间又要针对和这些结构相联系的参数空间进行。针对特定的模型，发现其最佳参数值的过程通常被称为优化问题。而从潜在的模型（模式）族中发现最佳模型（模式）结构的过程通常被称为搜索问题。,2023/8/15,Data Mining:Concepts and Techniques,40,组件4：搜索和优化方法,常用的优化方法有:爬山（Hill-Climing）最陡峭下降（Steepest-Descend）期望最大化（Expectation-Maximization,EM）常用的搜索方法有:贪婪搜索分支界定宽度（深度）优先遍历,2023/8/15,Data Mining:Concepts and Techniques,41,组件5：数据管理策略,传统的统计和机器学习算法都假定数据是可以全部放入内存的，所以不太关心数据管理技术。但是，对于数据挖掘工作者来说，GB甚至TB数量级的数据是常见的。由于外存的访问速度要慢的多，直接将传统的内存算法应用于这些外存数据，性能将变得非常差。因此，针对海量数据，应该设计有效的数据组织和索引技术，或者通过采样、近似等手段，来减少数据的扫描次数，从而提高数据挖掘算法的效率。,2023/8/15,Data Mining:Concepts and Techniques,42,组件化思想的应用,在实践中，数据挖掘算法的组件化思想是非常有用的。它通过将算法分解成一些核心组件而阐明了算法的实现机制。更重要的是，该观点强调了算法的本质，而不仅仅是算法的罗列。当面对一个新的应用时，数据挖掘人员应该从组件的角度，根据应用需求，考虑应该选取哪些组件，来组成一个新的算法，而不是考虑选取哪个现成的算法。,2023/8/15,Data Mining:Concepts and Techniques,43,组件化思想的应用,确定模型（模式）结构和评分函数的过程通常由人来完成而优化评分函数的过程通常需要计算机辅助来实现。实践中，通常要根据前一次的计算结果来改进模型（模式）结构和评分函数，所以整个过程要重复很多次。,2023/8/15,Data Mining:Concepts and Techniques,44,组件化思想的应用,有趣的是，不同的研究团体将注意力放在不同的数据挖掘算法组件上。统计学家强调推理过程，关注模型（模式）、评分函数、参数估计等，很少突出计算效率问题。而从事数据挖掘的计算机科学家则更注重高效的空间搜索和数据管理，不太关心模型（模式）或评分函数是否合适。,2023/8/15,Data Mining:Concepts and Techniques,45,组件化思想的应用,实际上，一个数据挖掘算法的所有组件都是至关重要的。对于小的数据集，模型（模式）的解释和预测能力相对于计算效率来说可能要重要的多。但是，随着数据集的增大，计算效率将变得越来越重要。对于海量数据，必须在模型（模式）的完备性和计算效率之间进行平衡，以期对现有数据达到某种程度的拟合。,2023/8/15,Data Mining:Concepts and Techniques,46,Examples,decision tree,clusters,association rules,structure of the model or pattern,NA,NA,NA,data management technique,greedy,gradient descent,breadth first with pruning,search/optimization method,accuracy,information gain,square error,support,confidence,score function,all possible combination of decision treesize=potentially infinity,choice of any k points as centersize=infinity,lattice of all possible combination of itemssize=2m,search space,classification,clustering,rule pattern discovery,task,ID3,K-means,Apriori,2023/8/15,Data Mining:Concepts and Techniques,47,Integration of Data Mining and Data Warehousing,Data mining systems,DBMS,Data warehouse systems couplingNo coupling,loose-coupling,semi-tight-coupling,tight-couplingOn-line analytical mining dataintegration of mining and OLAP technologiesInteractive mining multi-level knowledgeNecessity of mining knowledge and patterns at different levels of abstraction by drilling/rolling,pivoting,slicing/dicing,etc.Integration of multiple mining functions Characterized classification,first clustering and then association,2023/8/15,Data Mining:Concepts and Techniques,48,Architecture:Typical Data Mining System,Data Warehouse,Data cleaning&data integration,Filtering,Databases,Database or data warehouse server,Data mining engine,Pattern evaluation,Graphical user interface,Knowledge-base,2023/8/15,Data Mining:Concepts and Techniques,49,A Brief History of Data Mining Society,1989 IJCAI Workshop on Knowledge Discovery in Databases(Piatetsky-Shapiro)Knowledge Discovery in Databases(G.Piatetsky-Shapiro and W.Frawley,1991)1991-1994 Workshops on Knowledge Discovery in DatabasesAdvances in Knowledge Discovery and Data Mining(U.Fayyad,G.Piatetsky-Shapiro,P.Smyth,and R.Uthurusamy,1996)1995-1998 International Conferences on Knowledge Discovery in Databases and Data Mining(KDD95-98)Journal of Data Mining and Knowledge Discovery(1997)1998 ACM SIGKDD,SIGKDD1999-2001 conferences,and SIGKDD ExplorationsMore conferences on data miningPAKDD(1997),PKDD(1997),SIAM-Data Mining(2001),(IEEE)ICDM(2001),etc.,2023/8/15,Data Mining:Concepts and Techniques,50,Conferences and Journals on Data Mining,KDD ConferencesACM SIGKDD Int.Conf.on Knowledge Discovery in Databases and Data Mining(KDD)SIAM Data Mining Conf.(SDM)(IEEE)Int.Conf.on Data Mining(ICDM)Conf.on Principles and practices of Knowledge Discovery and Data Mining(PKDD)Pacific-Asia Conf.on Knowledge Discovery and Data Mining(PAKDD),Other related conferencesACM SIGMODVLDB(IEEE)ICDEWWW,SIGIRICML,CVPR,NIPSJournals Data Mining and Knowledge Discovery(DAMI or DMKD)IEEE Trans.On Knowledge and Data Eng.(TKDE)KDD Explorations,2023/8/15,Data Mining:Concepts and Techniques,51,Where to Find References?DBLP,CiteSeer,Google,Data mining and KDD(SIGKDD:CDROM)Conferences:ACM-SIGKDD,IEEE-ICDM,SIAM-DM,PKDD,PAKDD,etc.Journal:Data Mining and Knowledge Discovery,KDD ExplorationsDatabase systems(SIGMOD:ACM SIGMOD AnthologyCD ROM)Conferences:ACM-SIGMOD,ACM-PODS,VLDB,IEEE-ICDE,EDBT,ICDT,DASFAAJournals:IEEE-TKDE,ACM-TODS/TOIS,JIIS,J.ACM,VLDB J.,Info.Sys.,etc.AI&Machine LearningConferences:Machine learning(ML),AAAI,IJCAI,COLT(Learning Theory),CVPR,NIPS,etc.Journals:Machine Learning,Artificial Intelligence,Knowledge and Information Systems,IEEE-PAMI,etc.Web and IR Conferences:SIGIR,WWW,CIKM,etc.Journals:WWW:Internet and Web Information Systems,StatisticsConferences:Joint Stat.Meeting,etc.Journals:Annals of statistics,etc.VisualizationConference proceedings:CHI,ACM-SIGGraph,