数据挖掘第一与第二章课件

1、第一章 绪论第一章 绪论为什么要挖掘数据？大量数据被收集,存储在数据库数据仓库中 竞争压力越来越大 计算机越来越便宜，功能越来越强大数据以极快的速度收集和存储 (GB/hour)传统的技术难以处理这些原始数据 为什么要挖掘数据？大量数据被收集,存储在数据库数据仓库中常常有些信息“隐藏”在数据中, 并非显而易见的人分析需要数周数月, 才能发现有用的信息许多数据根本未曾分析过挖掘大型数据集：动机挖掘大型数据集：动机什么是数据挖掘许多不同定义本书定义在大型数据存储库中，自动地发现有用信息的过程。 Exploration & analysis, by automatic or semi-automat

2、ic means, of large quantities of data in order to discover meaningful patternsJiawei Han的定义从大型数据集中提取有趣的 (非平凡的, 蕴涵的, 先前未知的并且是潜在有用的) 信息或模式什么是数据挖掘许多不同定义数据挖掘技术的定义定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的，人们事先不知道的、但又是潜在有用的信息和知识的过程. 定义所包含的意义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；这些知识是相对的

3、，是有特定前提和约束条件的，在特定领域中具有实际应用价值.数据挖掘技术的定义定义：数据挖掘就是从大量的、不完全的、有噪12 十月 2022数据挖掘导论6数据挖掘与KDD数据挖掘与知识发现 数据挖掘是数据库中知识发现（knowledge discovery in database, KDD）不可缺少的一部分KDD是将未加工的数据转换为有用信息的整个过程 10 十月 2022数据挖掘导论6数据挖掘与KDD数据挖掘与12 十月 2022数据挖掘导论7引发数据挖掘的挑战1 可伸缩海量数据集越来越普遍数千兆字节(terabytes)为处理海量数据，算法必须是可伸缩的（scalable）可伸缩可能还需要新

4、的数据结构，以有效的方式访问个别记录例如，当要处理的数据不能放进内存时，可能需要非内存算法使用抽样技术或开发并行和分布算法也可以提高可伸缩程度 10 十月 2022数据挖掘导论7引发数据挖掘的挑战1 可伸12 十月 2022数据挖掘导论8挑战2高维性具有数以百计或数以千计属性的数据集 生物信息学：涉及数千特征的基因表达数据 不同地区温度测量：如果在一个相当长的时间周期内进行测量，维度（特征数）的增长正比于测量的次数 为低维数据开发的数据分析技术不能很好地处理高维数据 某些数据分析算法，随着维度（特征数）的增加，计算复杂性迅速增加 10 十月 2022数据挖掘导论8挑战2高维性12 十月 202

5、2数据挖掘导论9挑战3异种数据和复杂数据传统的数据分析方法只处理包含相同类型属性的数据集非传统的数据类型的出现需要能够处理异种属性的技术半结构化文本和超链接的Web页面集具有序列和三维结构的DNA数据地球表面不同位置上的时间序列测量值（温度、气压等）的气象数据数据中的联系如时间和空间的自相关性、图的连通性、半结构化文本和XML文 档中元素之间的父子联系 10 十月 2022数据挖掘导论9挑战3异种数据和复杂数据12 十月 2022数据挖掘导论10挑战4数据的所有权与分布 数据地理上分布在属于多个机构的资源中需要开发分布式数据挖掘技术分布式数据挖掘算法面临的主要挑战包括(1) 如何降低执行分布式

6、计算所需的通信量？(2) 如何有效地统一从多个资源得到的数据挖掘结果？(3) 如何处理数据安全性问题？ 10 十月 2022数据挖掘导论10挑战4数据的所有权与分布12 十月 2022数据挖掘导论11挑战5非传统的分析传统的统计学方法：假设-检验模式提出一种假设，设计实验来收集数据，然后针对假设分析数据当前的数据分析任务常常需要产生和评估数以千计的假设希望自动地产生和评估假设导致了一些数据挖掘技术的开发数据挖掘所分析的数据集通常不是精心设计的实验的结果代表数据的时机性样本（opportunistic sample）而不是随机样本（random sample）数据集常常涉及非传统的数据类型和数据

7、分布 10 十月 2022数据挖掘导论11挑战5非传统的分析12 十月 2022数据挖掘导论12数据挖掘的起源 数据挖掘是多学科交叉领域利用了来自如下一些领域的思想：统计学的抽样、估计和假设检验人工智能、模式识别和机器学习的搜索算法、建模技术和学习理论数据库系统提供有效的存储、索引和查询处理支持 分布式技术也能帮助处理海量数据最优化、进化计算、信息论、信号处理、可视化和信息检索 Machine Learning/Pattern RecognitionStatistics/AIData MiningDatabase systems10 十月 2022数据挖掘导论12数据挖掘的起源 数据挖掘12

8、十月 2022数据挖掘导论13 数据挖掘任务 预测vs.描述预测(Prediction)根据其他属性的值，预测特定属性的值 描述(Description)导出概括数据中潜在联系的模式 10 十月 2022数据挖掘导论13 数据挖掘任务 预测vs数据挖掘任务预测建模 涉及以说明自变量函数的方式为目标变量建立模型。 有两类预测建模任务：分类，用于预测离散的目标变量；回归，用于预测连续的目标变量。 预测建模可以用来确定顾客对产品促销活动的反应，预测地球生态系统的扰动，或根据检查结果判断病人是否患有某种疾病。数据挖掘任务预测建模 数据挖掘任务关联分析 用来描述数据中强关联特征的模式。 关联分析的应用包

9、括找出具有相关功能的基因组、识别用户一起访问的Web页面、理解地球气候系统不同元素之间的联系等。数据挖掘任务关联分析数据挖掘任务聚类分析 旨在发现紧密相关的观测值组群，使得与属于不同族的观测值相比，属于同一族的观测值相互之间尽可能类似。 聚类可以用来对相关的顾客分组、找出显著影响地球气候的海洋区域以及压缩数据等。数据挖掘任务聚类分析数据挖掘任务异常检测 识别其特征显著不同于其他数据的观测值。这样的观测值称为异常点或离群点。异常检测的算法的目标是发现真正的异常点，而避免错误地将正常的对象标注为异常点。 异常检测的应用包括检测欺诈、网络攻击、疾病的不寻常模式、生态系统扰动等。数据挖掘任务异常检测第

10、2章 数据数据类型数据质量数据预处理相似性和相异性度量第2章 数据数据类型2.1 数据类型 数据集的不同表现在很多方面。例如，某些数据集包含时间序列或者彼此之间具有明显联系的对象。毫不奇怪，数据的类型决定我们应使用何种工具和技术来分析数据。此外，数据挖掘研究常常是为了适应新的应用领域和新的数据类型的需要而展开的。2.1 数据类型 数据集的不同表现在很多方面。例数据数据集是数据对象的集合数据对象用一组刻画对象基本特性（如物体质量或事件发生时间）的属性描述 数据对象的其他名称记录、点、向量、模式、事件、案例、样本、观测或实体 属性的其他名称变量、特性、字段、特征或维 AttributesObjec

11、ts数据数据集是数据对象的集合AttributesObjects属性与度量属性是对象的性质和特性，它因对象而异，或随时间而变化。例如，人的眼球颜色因人而异，而物体的温度随时间而变化。测量标度是将数值或符号值与对象的属性相关联的规则属性与度量属性是对象的性质和特性，它因对象而异，或随时间而变12 十月 2022数据挖掘导论22属性值的类型数值的如下性质常常用来描述属性:相异性: = 序: 加法: + - 乘法: * /给定这些性质，我们可以定义四种属性类型：标称、序数、区间和比例。10 十月 2022数据挖掘导论22属性值的类型数值的如下性12 十月 2022数据挖掘导论23表2-2 不同的属性

12、类型属性类型描 述例 子操 作标称属性的值仅仅只是不同的名字，即标称值只提供足够的信息以区分对象（=，）邮政编码、雇员ID号、眼球颜色、性别众数、熵、列联相关、2检验序数属性的值提供足够的信息确定对象的序（）矿石硬度、好，较好，最好、成绩、街道号码中值、百分位、秩相关、游程检验、符号检验对于区间属性，值之间的差是有意义的，即存在测量单位（，）日历日期、摄氏或华氏温度均值、标准差、皮尔逊相关、t和F检验对于比率变量，差和比率都是有意义的（*，/）绝对温度、货币量、计数、年龄、质量、长度、电流几何平均、调和平均、百分比变差分类的(定性的)数值的(定量的)标称序数区间比率10 十月 2022数据挖掘

13、导论23表2-2 不同的属性类12 十月 2022数据挖掘导论24表2-3 定义属性层次的变换属性类型变 换注 释任何一对一变换，例如值的一个排列如果所有雇员的ID号都重新赋值，不会导致任何不同值的保序变换，即 新值= f(旧值),其中f是单调函数包括概念好、较好、最好的属性可以完全等价地用值1, 2, 3或用0.5, 1, 10表示新值 = a旧值+ b,其中a、b是常数华氏和摄氏温度标度零度的位置和1度的大小（单位）不同新值= a 旧值长度可以用米或英尺度量分类的(定性的)数值的(定量的)标称序数区间比率10 十月 2022数据挖掘导论24表2-3 定义属性层次12 十月 2022数据挖掘

14、导论25离散vs.连续属性离散属性(Discrete Attribute)有限或无限可数 (countable infinite )个值例: 邮政编码, 计数, 文档集的词常表示为整数变量. 注意: 二元属性(binary attributes)是离散属性的特例连续属性(Continuous Attribute)属性值为实数例: 温度, 高度, 重量. 实践中, 实数只能用有限的精度测量和表示.连续属性一般用浮点变量表示. 10 十月 2022数据挖掘导论25离散vs.连续属性离散属12 十月 2022数据挖掘导论26数据集的重要特性维度(Dimensionality)数据集的维度是数据集中的

15、对象具有的属性数目 维灾难（Curse of Dimensionality）维归约（dimensionality reduction） 稀疏性(Sparsity)具有非对称特征的数据集，一个对象的大部分属性上的值都为0 只存储和处理非零值分辨率(Resolution) 模式依赖于度量尺度(scale)在数米的分辨率下，地球表面看上去很不平坦，但在数十公里的分辨率下却相对平坦 小时标度下的气压变化反映风暴或其他天气系统的移动；在月标度下，这些现象就检测不到 10 十月 2022数据挖掘导论26数据集的重要特性维度(D12 十月 2022数据挖掘导论27数据集类型记录数据数据矩阵事务数据或购物篮数

16、据稀疏数据矩阵基于图(Graph)形的数据带有对象之间联系的数据具有图像对象的数据有序(Ordered)数据时序数据序列数据时间序列数据空间数据10 十月 2022数据挖掘导论27数据集类型记录数据12 十月 2022数据挖掘导论28记录数据: 典型情况记录数据由多种变体典型的记录数据数据集是记录数据对象的汇集，每个记录包含固定的数 据字段集10 十月 2022数据挖掘导论28记录数据: 典型情况记录12 十月 2022数据挖掘导论29记录数据: 数据矩阵如果一个数据集族中所有数据对象都具有相同的数值属性值，则数据对象可以看做多维空间中的点，每个维代表对象的一个不同属性。 这样的数据对象可以用

17、一个m n的矩阵表示，其中m行，一个对象一行；n列，一个属性一列。10 十月 2022数据挖掘导论29记录数据: 数据矩阵如果12 十月 2022数据挖掘导论30记录数据: 文档数据文档可以用词向量表示每个词是向量的一个分量每个分量的值是对应词在文档中出现的次数10 十月 2022数据挖掘导论30记录数据: 文档数据文档12 十月 2022数据挖掘导论31记录数据: 事务数据一种特殊类型的数据 每个记录涉及一系列的项例如，考虑一个杂货店，顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品就是项10 十月 2022数据挖掘导论31记录数据: 事务数据一种12 十月 2022数据挖掘导论3

18、2基于图形的数据1带有对象之间联系的数据 Examples: HTML Links 10 十月 2022数据挖掘导论32基于图形的数据1带有对象12 十月 2022数据挖掘导论33基于图形的数据2具有图形对象的数据 对象具有结构，即对象包含具有联系的子对象 例: 苯分子的球棍图，包含碳原子（黑色）和氢原子（灰色） 10 十月 2022数据挖掘导论33基于图形的数据2具有图形12 十月 2022数据挖掘导论34有序数据: 时序数据有序数据有多种, 常常涉及时间或空间序时序数据（sequential data）也称时间数据（temporal data） 时间次序重要, 但具体时间不重要例：事务序列

19、10 十月 2022数据挖掘导论34有序数据: 时序数据有序12 十月 2022数据挖掘导论35有序数据: 序列数据序列数据（sequence data）个体项的序列 例：基因组序列数据DNA都由4种核苷酸 A, T, G和C构造没有时间标记，但与时序数据类似重要的是在序列中的位置10 十月 2022数据挖掘导论35有序数据: 序列数据序列12 十月 2022数据挖掘导论36有序数据: 时间序列数据 时间序列数据（time series data）特殊的时序数据，其中每个记录都是一个时间序列(time series)，即一段时间的测量序列 时间自相关（temporal autocorrelat

20、ion），即如果两个测量的时间很接近，这些测量的值通常非常相似 10 十月 2022数据挖掘导论36有序数据: 时间序列数据12 十月 2022数据挖掘导论37有序数据:空间数据空间数据 具有空间属性，如位置或区域例: 不同的地理位置收集的气象数据（降水量、气温、气压）空间自相关性（spatial autocorrelation）: 物理上靠近的对象趋向于在其他方面也相似 右图每月是空间数据,显示多月是时间-空间数据(Spatial-Temporal Data)10 十月 2022数据挖掘导论37有序数据:空间数据空间数2.2 数据质量2.2 数据质量12 十月 2022数据挖掘导论39数据质

21、量数据质量的问题有哪几类?怎么去发现这些数据质量的问题? 处理这些问题我们应该怎么做? 数据质量问题的例子: 噪声和离群点数据遗漏 不一致或重复10 十月 2022数据挖掘导论39数据质量数据质量的问题有12 十月 2022数据挖掘导论40数据质量测量误差和数据收集错误 测量误差（measurement error）测量过程导致的任何问题 数据收集错误（data collection error）遗漏数据对象或属性值，或不正确地包含数据对象等错误 测量误差和数据收集错误都可能是系统的或随机的 10 十月 2022数据挖掘导论40数据质量测量误差和数据收12 十月 2022数据挖掘导论41数据质

22、量: 噪声噪声是测量误差的随机部分可能扭曲值或附加的谬误对象 Examples: distortion of a persons voice when talking on a poor phone and “snow” on television screenTwo Sine WavesTwo Sine Waves + Noise10 十月 2022数据挖掘导论41数据质量: 噪声噪声是测12 十月 2022数据挖掘导论42数据质量: 离群点离群点(Outliers)是在某种意义上具有不同于数据集中其他大部分数据对象的特征的数据对象，或是相对于该属性的典型值来说不 寻常的属性值10 十月 2

23、022数据挖掘导论42数据质量: 离群点离群点12 十月 2022数据挖掘导论43数据质量: 遗漏值原因信息收集不全(例如，有人拒绝透露年龄或体重)某些属性并不能应用于所有的对象(例如，年收入并不适用于小孩)处理删除具有遗漏值的数据对象或属性估计遗漏值在分析时忽略遗漏值10 十月 2022数据挖掘导论43数据质量: 遗漏值原因12 十月 2022数据挖掘导论44数据质量: 不一致的值数据可能包含不一致的值例如, 地址字段，其中列出了邮政编码和城市，但是特定的邮政编码区域并不包含在该城市 纠正不一致需要附加或冗余信息 时间序列数据中的不一致可能是使用不同的测量手段例: 海洋表面温度（SST） 1

24、9581982年用船或浮标 收集SST1983年之后使用卫星收集SST两组数据, 每组内的年相互之间趋向于正相关，但与另一组的年负相关 10 十月 2022数据挖掘导论44数据质量: 不一致的值数12 十月 2022数据挖掘导论45数据质量: 重复数据数据集可能包含重复或几乎重复的数据对象例子:许多人都收到过重复的邮件去重复 如果两个对象实际代表同一个对象，则对应的属性值必然不同，必须解决这些不一致的值 需要避免意外地将两个相似但并非重复的数据对象合并在一起。10 十月 2022数据挖掘导论45数据质量: 重复数据数据12 十月 2022数据挖掘导论46数据质量: 应用问题时效性 例如, 顾客

25、的购买行为或Web浏览模式的快照只代表有限时间内的真实情况 如果数据已经过时，则基于它的模型和模式也已经过时。相关性 可用的数据必须包含应用所需要的信息例如, 构造一个模型，预测驾驶事故发生率如果忽略了关于驾驶员的年龄和性别信息，那么除非这些信息可以间接地通过其他属性得到，否则模型的精度可能是有限的 10 十月 2022数据挖掘导论46数据质量: 应用问题时效2.3 数据预处理2.3 数据预处理12 十月 2022数据挖掘导论48数据预处理数据预处理方法聚集(Aggregation)抽样(Sampling)维归约(Dimensionality Reduction)特征子集选择(Feature

26、subset selection)特征构造(Feature creation)离散化与二元化(Discretization and Binarization)属性变换(Attribute Transformation)10 十月 2022数据挖掘导论48数据预处理数据预处理方法12 十月 2022数据挖掘导论49聚集聚集: 就是将两个或者多个对象合并成单个对象。聚集的动机数据归约导致的较小数据集需要较少的内存和处理时间，因此可以使用开销更大的数据挖掘算法通过高层而不是低层的数据视图，聚集起到了范围和标度的转换作用对象或属性群的行为通常比单个对象或属性的行为更加稳定10 十月 2022数据挖掘导

27、论49聚集聚集:12 十月 2022数据挖掘导论50聚集: 例澳大利亚的降水量平均月降水量标准差的直方图平均年降水量标准差的直方图10 十月 2022数据挖掘导论50聚集: 例澳大利亚的降水12 十月 2022数据挖掘导论51抽样抽样是一种选择数据对象子集进行分析的常用方法在统计学中，抽样长期用于数据的事先调查和最终的数据分析 统计学抽样vs数据挖掘抽样统计学抽样是因为得到感兴趣的整个数据集的费用太高，太费时间. 数据挖掘抽样是因为处理所有的数据的费用太高，太费时间.10 十月 2022数据挖掘导论51抽样抽样是一种选择数据对12 十月 2022数据挖掘导论52抽样有效抽样的原则:代表性使用样

28、本与使用整个数据集的效果几乎一样保留原数据集的性质样本是有代表性的，前提是它近似地与原数据集相同的性质10 十月 2022数据挖掘导论52抽样有效抽样的原则:12 十月 2022数据挖掘导论53抽样方法简单抽样(Simple Random Sampling)选取任何特定项的概率相等简单无放回抽样(Sampling without replacement)若被选择，选中项就要从构成总体的所有对象集中删除简单有放回抽样(Sampling with replacement)对象选中时不从总体中删除，相同对象可能被多次抽出分层抽样(Stratified sampling)总体由不同类型的对象组成，每种

29、类型的对象数量差别很大每组抽相同个数vs按比例10 十月 2022数据挖掘导论53抽样方法简单抽样(Sim12 十月 2022数据挖掘导论54样本大小: 例从8000个点分别抽2000和500个点2000个点的样本保留了数据集的大部分结构 500个点的样本丢失了许多结构8000 points 2000 Points500 Points10 十月 2022数据挖掘导论54样本大小: 例从800012 十月 2022数据挖掘导论55样本大小: 例给定一个数据集，它包含少量容量大致相等的组。从每组至少找出一个代表点 10 十月 2022数据挖掘导论55样本大小: 例给定一个数12 十月 2022数据

30、挖掘导论56渐进抽样 自适应(adaptive)或渐进抽样(progressive sampling)原因：有时难以预先确定样本集大小方法：从一个小样本开始，然后增加样本容量直至得到足够容量的样本 需要评估样本的方法，确定它是否足够大 例：使用渐进抽样来学习一个预测模型 预测模型的准确率随样本容量增加，但是在某一点准确率的增加趋于稳定在稳定点停止增加样本容量 找出准确率随样本容量变化的函数10 十月 2022数据挖掘导论56渐进抽样 自适应(ada12 十月 2022数据挖掘导论57维归约数据集包含大量特征例：文档数据集，数以万计的词对应数以万计的属性维灾难(curse of dimensio

31、nality)随着数据维度的增加，许多数据分析变得非常困难。特殊地，随着维度增加，数据在它所占据的空间中越来越稀疏 对于分类，这可能意味没有足够的数据对象来创建模型 对于聚类，点之间的密度和距离的定义（对聚类是至关重要的）变得不太有意义 结果: 对于高维数据, 许多分类和聚类算法（以及其他数据分析算法）都有麻烦分类准确率降低，聚类质量下降 10 十月 2022数据挖掘导论57维归约数据集包含大量特征12 十月 2022数据挖掘导论58维归约: 目的与方法目的:避免导致维灾难可以使模型更容易理解，让数据可视化使用维归约降低了数据挖掘算法的时间和内存需求技术主成分分析（PCA）是一种用于连续属性的

32、线性代数技术奇异值分解（SVD）是一种线性代数技术，它与PCA有关，并且也用于维归约。10 十月 2022数据挖掘导论58维归约: 目的与方法目的12 十月 2022数据挖掘导论59特征子集选择降低维度的另一种方法是仅使用特征的一个子集冗余特征（Redundant features）重复了包含在一个或多个其他属性中的许多或所有信息例：一种产品的购买价格和所支付的销售税额包含了许多相同的信息不相关特征（Irrelevant features）包含对于手头的挖掘任务几乎完全没用的信息例：学生的ID号码对于预测学生的总平均成绩是不相关的。10 十月 2022数据挖掘导论59特征子集选择降低维度的另1

33、2 十月 2022数据挖掘导论60特征子集选择: 技术技术:嵌入方法:数据挖掘算法运行期间，算法本身决定使用哪些属性或忽略哪些属性过滤方法:使用某种独立于数据挖掘任务的方法，在数据挖掘算法运行前进行特征选择包装方法:将目标数据挖掘算法作为黑盒，使用一种理想算法，但通常并不举出所有可能的子集来找出最佳属性子集10 十月 2022数据挖掘导论60特征子集选择: 技术技术12 十月 2022数据挖掘导论61特征创建由原来的属性创建新的属性，更有效的捕获数据集中的重要信息三种一般方法 :特征提取由原始数据创建新的特征集映射数据到新空间特征构造10 十月 2022数据挖掘导论61特征创建由原来的属性创建

34、12 十月 2022数据挖掘导论62映射数据到新空间傅里叶变换(Fourier transform)小波变换(Wavelet transform)例: 傅里叶变换左: 两个sin波; 中: 两个sin波之和+噪声; 检测不到模式右: 傅里叶变换到频谱; 两个尖峰对应于两个无噪声的时间序列 Two Sine WavesTwo Sine Waves + NoiseFrequency10 十月 2022数据挖掘导论62映射数据到新空间傅里叶变12 十月 2022数据挖掘导论63特征构造原始数据集的特征具有必要的信息，但其形式不适合数据挖掘算法 由原特征构造的新特征可能比原特征更有用 例: 文物数据库

35、每件文物的特征包括: 体积和质量，以及其他信息 文物材质(类): 木材、陶土、青铜、黄金 原特征不适合分类构造新特征: 密度=质量/体积10 十月 2022数据挖掘导论63特征构造原始数据集的特征12 十月 2022数据挖掘导论64离散化和二元化 为什么要离散化/二元化减少属性值个数，便于挖掘，结果使知识表达更简洁、更易于理解、更易使用离散化产生概念分层结构，可以在不同抽象层进行挖掘有些算法需要离散属性有些算法需要二元属性非监督vs监督离散化差别：是否使用类信息10 十月 2022数据挖掘导论64离散化和二元化 为什么要12 十月 2022数据挖掘导论65离散属性二元化1方法1如果属性具有m个

36、值，则将每个原始值唯一地映射到区间0, m1中的一个整数 (保序)把m个整数都变换成一个二进制数需要n = log2m个二进位表示这些整数 用n个二元属性表示这些二进制数 例: 5个值awful, poor, OK, good, great的分类变量需要三个二元变量x1、x2、x3 10 十月 2022数据挖掘导论65离散属性二元化1方法112 十月 2022数据挖掘导论66离散属性二元化2方法1的缺点建立了属性之间的联系，如good值用x2=1，x3=1表示不适合非对称属性处理非对称的二元属性，1比0更重要方法2：对m个属性值建立m个二元变量，每个对应于一个原属性值10 十月 2022数据挖

37、掘导论66离散属性二元化2方法1的12 十月 2022数据挖掘导论67连续属性离散化 基本思想将连续属性值排序后，通过指定n1个分割点（split point）把它们分成n个区间 将一个区间中的所有值映射到相同的分类值 离散化问题就是决定选择多少个分割点和确定分割点位置的问题分割点数目一般由用户确定分割点位置可以用非监督/监督方法确定结果表示区间集合：(x0, x1, (x1, x2,., (xn-1, xn)，其中x0和xn可以分别为-或+一系列不等式：x0 x x1, ., xn-1 x xn10 十月 2022数据挖掘导论67连续属性离散化 基本思想12 十月 2022数据挖掘导论68连

38、续属性离散化: 非监督例：四个不同组的数据点，以及两个离群点 分别采用等宽、等频、K-均值离散化x属性值DataEqual interval widthEqual frequencyK-means10 十月 2022数据挖掘导论68连续属性离散化: 非监督12 十月 2022数据挖掘导论69连续属性离散化: 监督监督离散化假定数据属于不同类确定分割点的原则极大化区间纯度区间中的数据都属于一个类-最纯区间中的数据以相同比例属于各类-最不纯有多种度量纯度的方法10 十月 2022数据挖掘导论69连续属性离散化: 监督监12 十月 2022数据挖掘导论70监督离散化: 熵熵(entropy) 是一种

39、不纯度度量属性A有m个值，属于k个不同的类属性A的值被划分成n个区间mi: 第i个区间中值的个数mij: 区间i中类j的值的个数第i个区间的熵ei划分的总熵e是每个区间的熵的加权平均 10 十月 2022数据挖掘导论70监督离散化: 熵熵(en12 十月 2022数据挖掘导论71基于熵的离散化:基本思想开始，将初始值切分成两部分，使得两个结果区间产生最小熵 然后，取一个区间，通常是取具有最大熵的区间，重复分割过程，直到区间的个数达到用户指定的个数，或者满足终止条件 3 categories for both x and y5 categories for both x and y10 十月 2

40、022数据挖掘导论71基于熵的离散化:基本思想12 十月 2022数据挖掘导论72具有过多值的分类属性进一步离散化减少分类值的个数序数属性用类似于连续属性的方法标称属性一般需要领域知识例如, 系名属性可能具有数十个不同的值可以使用系之间联系的知识，将系合并成较大的组，如工程学、社会科学或生物科学 例如, 城市有许多值合并成省, 进一步合并成国家10 十月 2022数据挖掘导论72具有过多值的分类属性进一12 十月 2022数据挖掘导论73变量变换 变量/属性变换（variable/attribute transformation） 是指用于变量的所有值的变换。换言之，对于每个对象，变换都作用于

41、该对象的变量值简单变换简单函数: xk, log(x), ex, |x|, 1/x注意:可能改变数据的特性 例: 变换1/x压缩了大于1的值，但是放大了0和1之间的值 10 十月 2022数据挖掘导论73变量变换 变量/属性变换12 十月 2022数据挖掘导论74变量变换: 标准化/规范化标准化（standardization）规范化（normalization）在数据挖掘中不区分 在统计学有不同涵义目标: 使整个值的集合具有特定的性质 例: 设 是属性值的均值, sx是它们的标准差, 变换创建一个新的变量，它具有均值0和标准差1 可以用中位数取代均值可以绝对标准差（absolute stan

42、dard deviation）取代标准差 10 十月 2022数据挖掘导论74变量变换: 标准化/规范2.4 相似性和相异性的度量2.4 相似性和相异性的度量12 十月 2022数据挖掘导论76相似性和相异性 相似性(Similarity)描述两个对象相似程度的数值度量.如果两个对象越相似，则它们的相似度越高.在区间0,1之间取值相异性(Dissimilarity)描述两个对象差异程度的数值度量对象越相似，它们的相异度就越低有时相异度在区间0,1之间取值，但是相异度在0和无穷大之间取值也很常见邻近性 (Proximity)是用来表示相似性和相异性的10 十月 2022数据挖掘导论76相似性和相

43、异性 相似性(12 十月 2022数据挖掘导论77p and q are the attribute values for two data objects简单属性的相似/相异度10 十月 2022数据挖掘导论77p and q are 12 十月 2022数据挖掘导论78数据对象的相异度:欧氏距离欧氏距离n是维数，而xk和yk分别是x和y的第k个属性（分量） 10 十月 2022数据挖掘导论78数据对象的相异度:欧氏距12 十月 2022数据挖掘导论79闵可夫斯基距离 Minkowski距离是欧氏距离的推广其中r是参数r = 1. 城市街区(也称曼哈顿, 出租车， L1 范数) 距离。一个常

44、见的例子是汉明距离，它是两个具有二元属性的对象（即两个二元向量）之间不同的二进制位个数。r = 2. 欧几里得距离r . 上确界距离，这是对象属性之间的最大距离，更正式地，最大距离由下列公式定义。10 十月 2022数据挖掘导论79闵可夫斯基距离 Mink12 十月 2022数据挖掘导论80距离的性质距离，具有一些众所周知的性质非负性: d(x, y) 0 for all x and y, and d(x, y) = 0 only if x = y. 对称性: d(x, y) = d(y, x) for all x and y. 三角不等式: d(x, z) d(x, y) + d(y, z)

45、 for all points x, y, and z. where d(x, y) is the distance (dissimilarity) between points (data objects), x and y.10 十月 2022数据挖掘导论80距离的性质距离，具有一些12 十月 2022数据挖掘导论81非度量的相异度有些相异度都不满足一个或多个度量性质 例1. 集合差每个对象是一个集合相异度用集合差的元素个数定义d(A, B) = size(AB)一般地，可能AB BA， size(AB) size(BA) 定义d(A, B) = size(A B) + size(B A)

46、 例2. 时间 10 十月 2022数据挖掘导论81非度量的相异度有些相异度12 十月 2022数据挖掘导论82数据对象之间的相似度 设s(x, y)是数据点x和y之间的相似度通常, 0 s(x, y) 1s(x, y)=1, iff x=y三角不等式（或类似的性质）通常不成立 通常, s(x, y) 具有如下性质s(x, y) = 1 (or maximum similarity) only if x = ys(x, y) = s(x, y) for all x and y. (Symmetry)有时可以将相似度变换成一种度量距离如，余弦相似性度量，Jaccard相似性度量 10 十月 20

47、22数据挖掘导论82数据对象之间的相似度 设12 十月 2022数据挖掘导论83简单匹配系数/ Jaccard系数设x和y是两个对象，都由n个二元属性组成f00 = x取0并且y取0的属性个数f01 = x取0并且y取1的属性个数f10 = x取1并且y取0的属性个数f11 = x取1并且y取1的属性个数简单匹配系数(Simple Matching Coefficient, SMC )Jaccard系数（Jaccard Coefficient） 10 十月 2022数据挖掘导论83简单匹配系数/ Jacc12 十月 2022数据挖掘导论84简单匹配系数/ Jaccard系数:例例: 两个对象x和yx = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0)y = (0, 0, 0, 0, 0, 0, 1, 0, 0, 1)f01 = 2 x取0并且y取1的属性个数f10 = 1 x取1并且y取0的属性个数f00 = 7 x取0并且y取0的属性个数f11 = 0 x取1并且y取1的属性个数