数据挖掘原理与算法.ppt

2023/9/18,Data Mining:Concepts and Techniques,1,数据挖掘原理与算法 By 毛国君，段立娟，王石，石云 Pub.清华大学出版社，2004使用说明：本书是一本全面介绍数据挖掘和知识发现技术的专业书籍，可作为计算机专业研究生或高年级本科生教材。共分8章，各章相对独立成篇，以利于读者选择性学习。本课件供全书讲解之用，为了取得好的教学效果，教师应该根据学生层次、教学大纲或课时安排进行必要裁减。,2023/9/18,Data Mining:Concepts and Techniques,2,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,3,数据挖掘技术的商业需求分析,随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，网络环境成为主流等等。产生“数据丰富而信息贫乏（Data Rich&Information Poor）”现象。在强大的商业需求的驱动下，商家们开始注意到有效地解决大容量数据的利用问题具有巨大的商机；学者们开始思考如何从大容量数据集中获取有用信息和知识的方法。随着信息技术的高速发展，人们希望能够提供更高层次的数据处理功能。新的需求推动新的技术的诞生。数据（Data）、信息（Information）和知识（Knowledge）是广义数据表现的不同形式。,2023/9/18,Data Mining:Concepts and Techniques,4,数据、信息和知识,data,information,knowledge,2023/9/18,Data Mining:Concepts and Techniques,5,数据挖掘产生的技术背景,数据挖掘是相关学科充分发展的基础上被提出和发展的。主要的相关技术：数据库等信息技术的发展统计学深入应用人工智能技术的研究和应用,2023/9/18,Data Mining:Concepts and Techniques,6,数据挖掘是一个多学科交叉技术,Data Mining,Database Technology,Statistics,OtherDisciplines,InformationScience,AI/MachineLearning,Visualization,2023/9/18,Data Mining:Concepts and Techniques,7,数据库系统的发展,60年代：简单文件处理系统向数据库系统变革。70年代：层次、网络和关系型数据库普及。80年代：RDBS及其相关工具、数据索引及数据组织技术被广泛采用；中期开始，分布式数据库广发讨论，关系数据库技术和新型技术的结合。90年代：数据库领域中的新内容、新应用、新技术层出不穷，形成了庞大的数据库家族；人们期望分析预测、决策支持等高级应用，Data mining and data warehousing等出现。本世纪开始：Data mining 得到理论/技术深化。,2023/9/18,Data Mining:Concepts and Techniques,8,统计学的深入应用,强大有效的数理统计方法和工具，已成为信息咨询业的基础。统计分析技术是基于严格的数学理论和高超的应用技巧的。数据挖掘技术是数理统计分析应用的延伸和发展。和数据库技术的结合性研究,2023/9/18,Data Mining:Concepts and Techniques,9,人工智能技术的研究和应用,人工智能是计算机科学研究中争议最多而又仍始终保持强大生命的研究领域。专家系统曾经是人工智能研究工作者的骄傲，但是诸多难题限制了专家系统的应用：知识获取成为专家系统研究中公认的瓶颈问题。知识表示成为一大难题：知识工程师在整理表达从领域专家那里获得的知识时勉强抽象出来的规则有很强的工艺色彩。对常识和百科知识出奇地贫乏：人工智能学家Feigenbaum估计，一般人拥有的常识存入计算机大约有100万条事实和抽象经验法则，离开常识的专家系统有时会比傻子还傻。数据挖掘继承了专家系统的高度实用性特点，并且以数据为基本出发点，客观地挖掘知识。机器学习得到了充分的研究和发展：理论和算法。数据挖掘研究在继承已有的人工智能相关领域，特别是机器学习的研究成果的基础上，成为新的研究分支。,2023/9/18,Data Mining:Concepts and Techniques,10,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,11,数据挖掘处于研究和应用探索阶段,经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果而形成独具特色的研究分支。大部分学者认为数据挖掘的研究仍然处于广泛研究和探索阶段：一方面，数据挖掘的概念已经被广泛接受。另一方面，数据挖掘的大面积应用还有待时日。随着KDD在学术界和工业界的影响越来越大，数据挖掘的研究向着更深入和实用技术方向发展：大学等研究机构的大多数基础性研究集中在数据挖掘理论、挖掘算法等的探讨上。公司的研究更注重和实际商业问题结合。数据挖掘的经济价值已经显现出来：Gartner报告中列举重要影响的五项关键技术，其中KDD和人工智能排名第一。,2023/9/18,Data Mining:Concepts and Techniques,12,数据挖掘研究聚焦点,数据挖掘在如下几个方面需要重点开展工作：数据挖掘技术与特定商业逻辑的平滑集成问题：数据挖掘需要代表性的应用实例来证明（像“啤酒与尿布”）。数据挖掘技术与特定数据存储类型的适应问题：不同的数据存储方式会影响数据挖掘的具体实现机制、目标定位、技术有效性等。大型数据的选择与规格化问题：数据的噪音、信息丢失等问题的处理；针对特定挖掘方法进行数据规格化等问题。数据挖掘系统的构架与交互式挖掘技术：在具体的实现机制、技术路线以及各阶段的功能定位等方面仍需细化和深入研究。良好的交互式挖掘（Interaction Mining）也是数据挖掘系统成功的前提。数据挖掘语言与系统的可视化问题：可视化挖掘除了要和良好的交互式技术结合外，还必须在挖掘结果或过程的可视化进行探索和实践。数据挖掘理论与算法研究一方面，在已有的理论框架下有许多面向实际应用目标的挖掘理论等待探索和创新。另一方面，随着数据挖掘技术本身和相关技术的发展，新的挖掘理论和算法的诞生是必然的。,2023/9/18,Data Mining:Concepts and Techniques,13,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势数据挖掘概念数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,14,从商业角度看数据挖掘技术,数据挖掘从本质上说是一种新的商业信息处理技术：数据挖掘技术把人们对数据的应用，从低层次的联机查询操作，提高到决策支持、分析预测等更高级应用上。通过对数据的统计、分析、综合和推理，发现数据间的关联性、未来趋势以及一般性的概括知识等，这些知识性的信息可以用来指导高级商务活动。从决策、分析和预测等高级商业目的看，原始数据只是未被开采的矿山，需要挖掘和提炼才能获得对商业目的有用的规律性知识。从商业角度看，数据挖掘就是按企业的既定业务目标，对大量的企业数据进行深层次分析以揭示隐藏的、未知的规律性并将其模型化，从而支持商业决策活动。,2023/9/18,Data Mining:Concepts and Techniques,15,数据挖掘的技术含义,数据库中的知识发现（KDD：Knowledge Discovery in Databases）是比数据挖掘出现更早的一个名词。KDD与Data Mining的关系，有不同的看法：KDD看成数据挖掘的一个特例：这是早期比较流行的观点，这种描述强调了数据挖掘在源数据形式上的多样性。数据挖掘是KDD的一个关键步骤：这种观点得到大多数学者认同，有它的合理性。KDD与Data Mining含义相同：事实上，在现今的许多场合，如技术综述等，这两个术语仍然不加区分地使用着。也有其他的说法：KDD在人工智能界更流行，而Data Mining在数据库界使用更多。在研究领域被称作KDD，在工程领域则称之为数据挖掘。,2023/9/18,Data Mining:Concepts and Techniques,16,数据挖掘定义,数据挖掘定义有广义和狭义之分。从广义的观点，数据挖掘是从大型数据集（可能是不完全的、有噪声的、不确定性的、各种存储形式的）中，挖掘隐含在其中的、人们事先不知道的、对决策有用的知识的过程。从这种狭义的观点上，我们可以定义数据挖掘是从特定形式的数据集中提炼知识的过程。下列技术不是数据挖掘：OLTP Expert systems Small MLStatistical programs,2023/9/18,Data Mining:Concepts and Techniques,17,数据挖掘研究的理论基础,数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也可以是归纳的。从研究者可能是来自于数据库、人工智能、数理统计、计算机科学以及其他方面的学者和工程技术人员，他们会从不同的视点进行探讨性研究。有下面一些重要的理论视点值得关注：模式发现（Pattern Discovery）架构规则发现（Rule Discovery）架构 基于概率和统计理论微观经济学观点（Microeconomic View）基于数据压缩（Data Compression）理论基于归纳数据库（Inductive Database）理论可视化数据挖掘（Visual Data Mining）等等,2023/9/18,Data Mining:Concepts and Techniques,18,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,19,根据挖掘任务,分类或预测模型发现数据总结与聚类发现关联规则发现序列模式发现相似模式发现混沌模式发现依赖关系或依赖模型发现异常和趋势发现等,2023/9/18,Data Mining:Concepts and Techniques,20,根据挖掘对象,关系数据库挖掘面向对象数据库挖掘空间数据库挖掘时态数据库挖掘文本数据源挖掘多媒体数据库挖掘异质数据库挖掘遗产数据库挖掘web数据挖掘等,2023/9/18,Data Mining:Concepts and Techniques,21,根据挖掘方法,机器学习方法统计方法聚类分析方法神经网络（Neural Network）方法遗传算法（Genetic Algorithm）方法数据库方法近似推理和不确定性推理方法基于证据理论和元模式的方法现代数学分析方法粗糙集（Rough Set）或模糊集方法集成方法等,2023/9/18,Data Mining:Concepts and Techniques,22,根据知识类型,挖掘广义型知识挖掘差异型知识挖掘关联型知识挖掘预测型知识挖掘偏离型（异常）知识挖掘不确定性知识等,2023/9/18,Data Mining:Concepts and Techniques,23,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,24,知识表示模式分类,数据挖掘的目的是发现知识，知识要通过一定的模式给出。通过对数据挖掘中知识表示模式及其所采用方法的分析，可以更清楚地了解数据挖掘系统的特点。主要知识模式类型有：广义知识（Generalization）关联知识（Association）类知识（Class/Cluster）预测型知识（Prediction）特异型知识（Exception）,2023/9/18,Data Mining:Concepts and Techniques,25,广义知识挖掘,广义知识是指描述类别特征的概括性知识。这类数据挖掘系统是对细节数据的所蕴涵的概念特征信息的概括和抽象的过程。主要方法有：概念描述（Concept Description）方法：概念描述本质上就是对某类对象的内涵特征进行概括：特征性（Characterization）描述：描述某类对象的共同特征。区别性（Discrimination）描述：描述不同类对象之间的区别。多维数据分析可以看作是一种广义知识挖掘的特例多层次概念描述问题：由数据归纳出的概念是有层次的，不同层次的概念是对原始数据的不同粒度上的概念抽象。例如，“北京工业大学”能归纳出“北京市”、“中国”、“亚洲”等层次。销售表SALES（ENO，ENAME，EAGE，VALUE，DEPT），它的每个属性的定义域都可能存在蕴涵于领域知识内的概念延伸。例如，DEPT能归纳出公司COMPANY、城市CITY或国家COUNTRY等层次概念分层（Concept Hierarchy）技术：将低层概念集映射到高层概念集的方法，是一个常用的处理多层次概念描述的方法。,2023/9/18,Data Mining:Concepts and Techniques,26,主要的概念分层方法,模式分层（Schema Hierarchy）：利用属性在特定背景知识下的语义层次形成不同层次的模式关联。这种关联是一种的全序或偏序关系。例如，DEPT的模式分层结构可能是：DEPTCOMPANYCITYCOUNTRY。集合分组分层（Set-Grouping Hierarchy）：将属性在特定背景知识下的取值范围合理分割，形成替代的离散值或区间集合。例如，年龄EAGE可以抽象成20，29，30，39，40，49，50，59或者青年，中年，老年。操作导出分层（Operation-Drived Hierarchy）：有些属性可能包含多类信息。例如，一个跨国公司的雇员号可能包含这个雇员的所在的部门、城市、国家和雇佣的时间等。对这类对象可以作为背景知识定义它的结构，通过编码解析等操作完成概念的抽象。基于规则分层（Rule-Based Hierarchy）：通过定义背景知识的抽象规则，形成不同层次上的概念的抽象。,2023/9/18,Data Mining:Concepts and Techniques,27,关联知识挖掘,关联知识挖掘的目的就是找出数据库中隐藏的关联信息。关联知识反映一个事件和其他事件之间的依赖或关联。关联可分为简单关联、时序（Time Series）关联、因果关联、数量关联等。从广义上讲，关联分析是数据挖掘的本质。关联规则挖掘（Association Rule Mining）是关联知识发现的最常用方法：关联规则的研究最早的分支之一，最著名的Apriori算法。是数据挖掘研究中比较深入的分支，许多关联规则挖掘的理论和算法已经被提出。,2023/9/18,Data Mining:Concepts and Techniques,28,类知识挖掘,类知识（Class）刻画了一类事物，这类事物具有某种意义上的共同特征，并明显和不同类事物相区别。有两个基本的方法来挖掘类知识：分类：分类是数据挖掘中的一个重要的目标和任务，是目前的研究和应用最多的分支之一。分类的目的是学会一个分类模型（称作分类器），该模型能把数据库中的数据项映射到给定类别中。分类技术是一种有指导的学习（Supervised Learning），即每个训练样本的数据对象已经有类标识，通过学习可以形成表达数据对象与类标识间对应的知识。聚类：数据挖掘的目标之一是进行聚类分析。聚类是把一组个体按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的差别尽可能的小，而不同类别上的个体间的差别尽可能的大。聚类属于无指导学习（Unsupervised Learning），当一组数据对象可以由一个概念（区别于其他的概念）来描述时，就形成一个簇（Cluster）。刻画了数据所蕴涵的类知识。,2023/9/18,Data Mining:Concepts and Techniques,29,分类中的基础方法,决策树方法：基本的分类技术之一，如ID3及其改进算法ID4、ID5、C4.5、C5.0等；针对大训练样本集的SLIQ、SPRINT、雨林（Rainforest）BOAT等算法。贝叶斯分类：具有坚实的理论基础，理论上具有较小的出错率。但是，它的适应性差。神经网络：作为一个相对独立的研究分支已经很早被提出，具有高度的抗干扰能力和可以对未训练数据进行分类等优点，因此产生了神经网络和数据挖掘技术的结合性研究。遗传算法：是基于进化理论的机器学习方法。类比学习：最典型的方法是k-最临近分类（k-Nearest Neighbor Classification）方法，它属于懒散学习法。其他方法：如粗糙集（Rough Set）、模糊集（Fuzzy Set）方法等。,2023/9/18,Data Mining:Concepts and Techniques,30,主要聚类的技术,基于划分的聚类方法：k-平均算法是统计学中的一个经典聚类方法，它以预先定义好的簇平均值，构造划分，评价和选择他们。基于层次的聚类方法：通过对源数据库中的数据进行层次分解，达到目标簇的逐步生成。凝聚（Agglomeration）：由小到大逐步合并、评价。分裂（Division）由大到小逐步分裂、评价。基于密度的聚类方法：基于密度的聚类方法是通过度量区域所包含的对象数目来形成最终目标的。如果一个区域的密度超过指定的值，那么它就需要进一步分解。基于网格的聚类方法：对象空间离散化成有限的网格单元，聚类工作在这种网格结构上进行。基于模型的聚类方法：每个簇假定一个模型，寻找数据对给定模型的最佳拟和。,2023/9/18,Data Mining:Concepts and Techniques,31,预测型知识挖掘,预测型知识（Prediction）是指由历史的数据产生的并能推测未来数据趋势的知识。预测性挖掘主要是对未来数据的概念分类和趋势输出。分类技术可以用于产生预测型的类知识。统计学中的回归方法等可以通过历史数据直接产生对未来数据预测的连续值，因而这些预测型知识已经蕴藏在诸如趋势曲线等输出形式中。预测型知识的挖掘可以结合经典的统计方法、神经网络和机器学习等技术来研究。,2023/9/18,Data Mining:Concepts and Techniques,32,预测型知识挖掘中的典型方法,趋势预测模式：主要是针对那些具有时序（Time Series）属性的数据，如股票价格等，或者是序列项目（Sequence Items）的数据，如年龄和薪水对照等，发现长期的趋势变化等。周期分析模式：主要是针对那些数据分布和时间的依赖性很强的数据进行周期模式的挖掘。例如，服装在某季节或所有季节的销售周期。序列模式：主要是针对历史事件发生次序的分析形成预测模式来对未来行为进行预测。例如，预测“三年前购买计算机的客户有很大概率会买数字相机”。神经网络：在预测型知识挖掘中，神经网络也是很有用的模式结构。,2023/9/18,Data Mining:Concepts and Techniques,33,特异型知识挖掘,特异型知识（Exception）是源数据中所蕴涵的极端特例或明显区别于其他数据的知识描述，它揭示了事物偏离常规的异常规律。特异知识挖掘的价值：例如，在Web站点发现那些区别于正常登录行为的用户特点可以防止非法入侵。金融、电信欺诈等分类中的反常实例、不满足普通规则的特例、观测结果与模型预测值的偏差、数据聚类外的离群值等许多技术可以扩展到特异型知识挖掘中,如：孤立点（Outlier）分析：孤立点是指不符合数据的一般模型的数据。在类知识挖掘中，孤立点分析是不能归入正常类知识中的零散数据的再分析。异常序列分析：在一系列行为或事件对应的序列中发现明显不符合一般规律的特异型知识。特异规则发现：产生并评价虽然具有低支持度但可能很有价值的规则。,2023/9/18,Data Mining:Concepts and Techniques,34,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,35,数据挖掘方法与数据存储类型,数据挖掘技术应该应用到任何数据存储方式的知识挖掘中，但是因为源数据的存储类型的不同，挖掘的挑战性和技术会不同。近年来的研究表明数据挖掘所涉及的数据存储类型越来越丰富，除了一些有通用价值的模型、构架等研究外，也开展了一些针对复杂或新型数据存储方式下的挖掘技术或算法的研究。主要的数据类型：事务数据库（Transactional Database）关系型数据库（Related Database）数据仓库（Data Warehouse）在关系模型基础上发展的新型数据库 面向应用的新型数据源 Web数据,2023/9/18,Data Mining:Concepts and Techniques,36,事务数据库中的数据挖掘,一个事务数据库是对事务型数据的收集。1993年，当Agrawal等开始讨论数据挖掘问题时，是以购物篮分析（Market Basket Analysis）作为商业应用背景的。从事务数据库中发现知识是数据挖掘中研究较早但至今仍然很活跃的问题。通过特定的技术对事务数据库进行挖掘，可以获得动态行为所蕴藏的关联规则、分类、聚类以及预测等知识模式。第三章将详细讲解,2023/9/18,Data Mining:Concepts and Techniques,37,关系型数据库中的数据挖掘,关系型数据库是由一系列数据表组成的，相当成熟：成熟的语义模型（像实体-关系模型）；成熟的DBMS（像Oracle）成熟的查询语言（像SQL语言；可视化的辅助工具和优化软件。一些更深入和亟待解决的问题：多维知识挖掘：传统的事务数据库挖掘所研究的知识一般是单维（Single-Demension）的，但是，在关系型数据库中，多维的知识更普遍和有应用价值。单维：“购买计算机的人也购买打印机”。多维：“什么样购买计算机的人也购买打印机的可能性更大？”。多表挖掘：关系型数据库是一系列表的集合。因此，多表挖掘是必然的。数量数据挖掘：关系型数据库经常包含非离散数量属性（如工资）。多层知识挖掘：数据及其关联总是可在多个不同的概念层上来理解它。知识评价问题：对传统的数据挖掘框架的知识评价问题，也是关系型数据库中数据挖掘走向实际应用必须要解决的问题。约束数据挖掘问题：数据挖掘系统在用户的约束指导下进行，可以提高挖掘效率和准确度。,2023/9/18,Data Mining:Concepts and Techniques,38,数据仓库中的数据挖掘,数据仓库中的数据是按着主题来组织的。存储的数据可以从历史的观点提供信息。虽然目前的一些数据仓库辅助工具可以帮助完成数据分析，但是发现蕴藏在数据内部的知识模式及其按知识工程方法来完成高层次的工作仍需要数据挖掘技术支持。数据挖掘不仅伴随数据仓库而产生，而且随着应用深入产生了许多新的课题。如果我们把数据挖掘作为高级数据分析手段来看，那么它是伴随数据仓库技术提出并发展起来的。OLAP尽管在许多方面和数据挖掘是有区别的，但是它们在应用目标上有很大的重合度。数据挖掘更看中数据分析后所形成的知识表示模式，而OLAP更注重利用多维等高级数据模型实现数据的聚合。从某种意义上讲，我们可以把数据挖掘看作是OLAP的高级形式，与此更接近的名词可能算是OLAM（联机分析挖掘）。,2023/9/18,Data Mining:Concepts and Techniques,39,新型数据库中的数据挖掘,对象关系型数据库（Object-Ralational Database）挖掘；面向对象数据库的挖掘；空间数据库的挖掘；时态数据库的挖掘；工程数据库（Engineering Database）的挖掘；多媒体数据库（Multimedia Database）的挖掘；等等,2023/9/18,Data Mining:Concepts and Techniques,40,Web数据源中的数据挖掘,随着Internet的广泛使用，Web这一巨大的海洋中蕴藏着极其丰富的有用信息。面向Web的数据挖掘比面向数据库和数据仓库的数据挖掘要复杂得多：异构数据源环境：Web网站上的信息是异构:每个站点的信息和组织都不一样；存在大量的无结构的文本信息、复杂的多媒体信息；站点使用和安全性、私密性要求各异等等。数据的是复杂性：有些是无结构的（如Web页），通常都是用长的句子或短语来表达文档类信息；有些可能是半结构的（如Email，HTML页）。当然有些具有很好的结构（如电子表格）。揭开这些复合对象蕴涵的一般性描述特征成为数据挖掘的不可推卸的责任。动态变化的应用环境：Web的信息是频繁变化的，像新闻、股票等信息是实时更新的。这种高变化也体现在页面的动态链接和随机存取上。Web上的用户是难以预测的。Web上的数据环境是高噪音的。,2023/9/18,Data Mining:Concepts and Techniques,41,Web挖掘的研究主要流派,Web结构挖掘：挖掘Web上的链接结构。通过Web页面间的链接信息可以识别出权威页面（Authoritative Page）、安全隐患（非法链接）等。Web使用挖掘对Web上的Log日志记录的挖掘Web上的Log日志记录了包括URL请求、IP地址以及时间等的访问信息。分析和发现Log日志中蕴藏的规律可以帮助我们识别潜在的客户、跟踪Web服务的质量以及侦探非法访问的隐患等。Web内容挖掘：Web的内容是丰富的，而且构成成分是复杂的（无结构的、半结构的等），对内容的分析是重要而艰巨的工作。Web的内容主要是包含文本、声音、图片等的文档信息。文本挖掘（Text Mining）和Web搜索引擎（Search Engine）等相关领域的研究。目多媒体信息挖掘技术。,2023/9/18,Data Mining:Concepts and Techniques,42,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,43,粗糙集理论简介,粗糙集理论是一种研究不精确、不确定性知识的数学工具，由波兰科学家Z.Pawlak在1982年首先提出的。粗糙集一经提出就立刻引起数据挖掘研究人员的注意，并被广泛讨论。粗糙集的知识形成思想可以概括为：一种类别对应于一个概念，知识由概念组成。粗糙集对不精确概念的描述方法是通过下近似（Lower Approximation）和上近似（Upper Approximation）概念来表示：一个概念（或集合）的下近似概念（或集合）中的元素肯定属于该概念（或集合）一个概念（或集合）的上近似概念（或集合）只是可能属于该概念。,2023/9/18,Data Mining:Concepts and Techniques,44,信息系统,粗糙集把客观世界抽象为一个信息系统。一个信息系统是一个四元组，：U是对象（或事例）的有限集合，记为Ux1，x2，.，xn。A是属性的有限集合，记为AA1，A2，.Am。属性集A常常又划分为两个集合C和D，即ACD，CD，C表示条件属性集，D表示决策属性集。V是属性的值域集，记为VV1，V2，.，Vm，其中Vi是属性Ai的值域；f是信息函数（Information Function），即：，f（xi，Aj）Vj。f（e，a）的值确定记录e关于属性a的取值。基于某个属性集A的所有等价记录的集合，被定义为等价类。属于同一等价类的记录称为基于属性集A的划分。,2023/9/18,Data Mining:Concepts and Techniques,45,近似空间（Approximation Space）,近似空间有一个二元组，（）给出：U是对象（或事例）的有限集合，记为U x1，x2，.，xn；B是A的属性子集，R（B）是U上的二元等价关系，即R（B）=（x1，x2）|f（x1，b）=f（x2，b），b B。R（B）也称无区别关系（Indiscernibility Relation）。R（B）把U划分为k个等价类R*（B）=X1，X2，.，Xk。即对任意的x1，x2Xi，有（x1，x2）R（B）；对任意的x1Xi，x2Xj，ij，有（x1，x2）R（B）。,2023/9/18,Data Mining:Concepts and Techniques,46,下近似和上近似定义,对任意一个概念（或集合）O，B是U的一个子集，O的下近似定义为：其中xR（B）表示x在R（B）上的等价类。O的上近似定义为：设有两个属性集B1，B2，B1是B2的真子集，如果R（B1）=R（B2），则称B2可归约为B1。如果属性集B不可进一步归约，则称B是U的一个约简或归约子。,2023/9/18,Data Mining:Concepts and Techniques,47,粗糙集中的约简概念,极小属性集：去掉任何一个属性，都将使得该属性集对应的规则覆盖反例，即导致规则与例子的不一致。极大属性集：向它加入任何一个不属于它的属性，则会使得该属性集对应的规则覆盖更少的正例。粗糙集中的约简是极小属性集，约简对应的规则为极小规则，极大属性集对应的规则为极大规则。挖掘的目标：获得的极小规则的尽可能简洁形式（即极小属性集尽可能的小）。基于极小规则和极大规则的概念，我们就可以实现极小规则和极大规则的生成。,2023/9/18,Data Mining:Concepts and Techniques,48,粗糙集在KDD中的应用举例,规则学习和决策表推导。在保证简化后的决策系统具有与原先系统一样的分类能力的前提条件下，通过使用知识简约和范畴简约，将决策系统简化并且找到最小（最短）决策规则集合，以达到最大限度泛化的目的。知识简约。简约和相对简约在粗糙集中十分重要，它反应了一个决策系统的本质。通过对条件属性集合的简约，可以保证简化后的决策系统具有与原先系统一样的分类能力。属性相关分析。粗糙集方法中的属性重要程度可以用来衡量该属性对分类的影响程度，它与ID3中的信息增益类似，可以证明两者在一定条件下是等价的。进行数据预处理。粗糙集方法可以去掉多余属性，可提高发现效率，降低错误率等,2023/9/18,Data Mining:Concepts and Techniques,49,第一章 绪论 内容提要,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,50,数据挖掘技术应用广泛,数据挖掘技术从一开始就是面向应用的。由于现在各行业的业务操作都向着流程自动化的方向发展，企业内产生了大量的业务数据。数据挖掘技术应用很广，应用较好的领域有：金融保险业：Credit Scoring；Insurance Evaluation电信：Detecting telephone fraud零售（如超级市场）等商业领域：Marketing Analysis医学：Detecting inappropriate medical treatment体育：IBM Advanced Scout analyzed NBA game statistics 在天文学、分子生物学等科学研究方面等等,2023/9/18,Data Mining:Concepts and Techniques,51,数据挖掘与CRM,CRM（客户关系管理）是指对企业和客户之间的交互活动或行为进行管理的过程。数据挖掘能够帮助企业确定客户的特点，使企业能够为客户提供有针对性的服务。因此，把数据挖掘和CRM结合起来进行研究和实践，是一个有很大应用前景的工作。所能解决的典型商业问题包括：数据库营销（Database Marketing）客户群体划分（Customer Segmentation&Classification）客户背景分析（Profile Analysis）交叉销售（Cross-selling）客户流失性分析（Churn Analysis）客户信用记分（Credit Scoring）欺诈发现（Fraud Detection）等等。,2023/9/18,Data Mining:Concepts and Techniques,52,数据挖掘与信息安全,随着网络上需要进行存储和处理的敏感信息的日益增多，安全问题逐渐成为网络和系统中的首要问题。现代信息安全的内涵已经不局限于信息的保护，而是对整个信息系统的保护和防御，包括对信息的保护、检测、反映和恢复能力（PDRR）等。传统的信息安全系统概括性差，只能发现模式规定的、已知的入侵行为，难以发现新的入侵行为。人们希望能够对审计数据进行自动的、更高抽象层次的分析，从中提取出具有代表性、概括性的系统特征模式，以便减轻人们的工作量，且能自动发现新的入侵行为。数据挖掘正是具有这样功能的一种技术。数据挖掘可以对海量的数据进行智能化的处理，提取出我们感兴趣的信息。利用数据挖掘、机器学习等智能方法作为入侵检测的数据分析技术，可从海量的安全事件数据中提取出尽可能多的隐藏安全信息，抽象出有利于进行判断和比较的与安全相关的普遍特征，从而发现未知的入侵行为。,2023/9/18,Data Mining:Concepts and Techniques,53,第一章 绪论 内容小结,数据挖掘技术的产生与发展 数据挖掘研究的发展趋势 数据挖掘概念 数据挖掘技术的分类问题数据挖掘常用的知识表示模式与方法不同数据存储形式下的数据挖掘问题 粗糙集方法及其在数据挖掘中的应用 数据挖掘的应用分析,2023/9/18,Data Mining:Concepts and Techniques,54,http:/www.cs.sfu.ca/han,Thank you!,2023/9/18,Data Mining:Concepts and Techniques,55,CMPT-843 Course Arrangement,1st week:full instructor teaching2nd to 11th