第2章 数据处理基础 2.1数据及数据类型 2.2 数据统计特性 2.3 数据预处理 2.4 相似性度量 2.2.1 据的中心度量 2.2.2 据散布程度度量 2.3 数据预处理 2.3.1 数据清理 2.3.2 数据聚合 2.3.3 数据变换 2.3.4 数据归约 2.4 相似性度量

2.1 数据类型 相关概念 数据 属性 数据集 狭义：数字 。 广义：数据对象及其属性的集合，其表现形式可以是数字、符号、文字、图像抑或是计算机代码等等。 属性 (也称为特征、维或字段)，是指一个对象的某方面性质或特性。一个对象通过若干属性来刻画。 数据集 数据对象的集合(同分布、同特征)

案例 包含电信客户信息的样本数据集 属性 对象 客户编号 客户类别 行业大类 通话级别 通话总费用 … N22011002518 大客户 采矿业和一般制造业 市话 16352 C14004839358 商业客户 批发和零售业 市话＋国内长途(含国内IP) 27891 N22004895555 市话＋国际长途(含国际IP) 63124 3221026196 科学教育和文化卫生 53057 D14004737444 房地产和建筑业 80827 ︰

不同的属性类型 属性类型 描述 例子 操作 分类的 (定性的) 标称 其属性值只提供足够的信息以区分对象。这种属性值没有实际意义。 颜色、性别、 产品编号 众数、熵、 列联相关。 序数 其属性值提供足够的信息以区分对象的序。 成绩等级(优、良、中、及格、不及格)、年级(一年级、二年级、三年级、四年级) 中值、百分位、秩相关、符号检验。 数值的 (定量的) 区间 其属性值之间的差是有意义的。 日历日期、摄氏温度 均值、标准差、皮尔逊相关 比率 其属性值之间的差和比率都是有意义的。 长度、时间和速度 几何平均、调和平均、百分比变差

数据集的特性 维度(Dimensionality) 稀疏性(Sparsity) 分辨率(Resolution) 指数据集中的对象具有的属性个数总和。 维归约 稀疏性(Sparsity) 指在某些数据集中，有意义的数据非常少，对象在大部分属性上的取值为0；非零项不到1%。 文本数据集 分辨率(Resolution) 不同分辨率下数据的性质不同

数据集的类型 数据集的类别 记录数据 基于图形的数据 有序数据 事务数据或购物篮数据 数据矩阵 文本数据 万维网 化合物结构 时序数据 序列数据 时间序列数据 空间数据 流数据

记录数据 事务数据(Transaction Data)是一种特殊类型的记录数据，其中每个记录涉及一个项的集合。 事务数据事例 事务ID 商品的ID列表 T100 Bread， Milk， Beer T200 Soda， cup， Diaper … 典型的事务数据如超市零售数据，顾客一次购物所购买的商品的集合就构成一个事务，而购买的商品就是项。这种类型的数据也称作购物篮数据(Market Basket Data)，因为记录中的每一项都是一位顾客“购物篮”中购买的商品。

数据矩阵 如果一个数据集簇中的所有数据对象都具有相同的数值属性集，则数据对象可以看作多维空间中的点，其中每个维代表描述对象的一个不同属性。 数据集可以用一个m×n的矩阵表示，其中m行，一个对象一行；n列，一个属性一列。

文本数据 文档用词向量表示 每个词是向量的一个分量(属性) 每个分量的值是对应词在文档中出现的次数

图形数据 网页链接 化合物结构

有序数据 时序数据或失态数据 项/事件 时序元素

有序数据 基因组序列数据

有序数据 空间温度数据

2.2 数据统计特征 数据统计又称为汇总统计，用单个数或数的小集合来捕获大的数据集的各种属性特征。通常需要数据的中心趋势和离散程度特征。 中心趋势度量包括均值(mean)、中位数(median)、众数(mode)和中列数(midrange)，而数据离散程度度量包括四分位数(quartiles)、四分位数极差(InterQuartiles Range, IQR)和方差(variance)等。

（1）数据的中心度量-1 数据集 “中心”的最常用、最有效的数值度量是(算术)均值(mean)。 设x1, x2,…, xN是N个值的集合，则该值集的均值定义为：

（1）数据的中心度量-2 集合中每个值 与一个权值 相关联。权值反映对应值的显著性、重要性或出现频率。在这种情况下，使用加权算术均值(weighted arithmetic mean)：

（1）数据的中心度量-3 截断均值：指定0和100间的百分位数p，丢弃高端和低端(p/2)%的数据，然后用常规方法计算均值，所得的结果即是截断均值。 中位数是p=100%时的截断均值，而标准均值是对应于p=0%的截断均值。 例：计算{1,2,3,4,5,90}值集的均值，中位数和p=40%的截断均值. 解：均值是17.5，中位数是3.5，p=40%时的截断均值也是3.5

（2）数据散布程度度量-1 最简单的散布度量是极差，即最大值和最小值之差 假设属性x具有m个值 ,其极差定义为： 极差和方差是值集的散布度量，表明属性值是否散布很宽，或者是否相对集中在单个点(如均值)附近。 最简单的散布度量是极差，即最大值和最小值之差 假设属性x具有m个值 ,其极差定义为： range(x)=max(x)-min(x)=x(m)-x(1) 方差(variance)定义如下:

（2）数据散布程度度量-2 因为方差用到了均值，而均值容易被离群值扭曲，所以方差对离群值很敏感。 更加稳健的值集散布估计方法： 绝对平均偏差(absolute average deviation,AAD) 中位数绝对偏差(median absolute deviation,MAD) 四分位数极差(interquartile range,IQR)

2.3 数据预处理 数据挖掘的目的是在大量的、潜在有用的数据中挖掘出有用的模式或信息，挖掘的效果直接受到源数据质量的影响。 高质量的数据是进行有效挖掘的前提，高质量的决定必须建立在高质量的数据上。

数据预处理的主要任务 数据清理 数据集成 数据变换 数据归约 数据离散化 填写空缺数据，平滑噪声数据，识别、删除孤立点，解决不一致性 集成多个数据库，数据立方体或文件 数据变换 规范化和特征构造 数据归约 得到数据集的压缩表示及特征选择 数据离散化 通过概念分层和数据离散化来规约数据，对数值数据特别重要

数据预处理 数据清理 数据集成 数据变换 数据归约 脏数据 “干净”数据 -2，32，100，59，48 -0.02, 0.32, 1.00,0.59,0.48 T1 T2 … T2000 A1 A2 A3 … A126 T3 T1456 A1 A3 … A115

数据清理——为什么要清理数据? 现实世界的数据是“肮脏的” 意义： 不完整的：有感兴趣的属性缺少属性值 含噪声的：包含错误的或是“孤立点” 不一致的：在命名或是编码上存在差异 意义： 数据清理的目的就是试图填充缺失值、去除噪声并识别离群点、纠正数据中的不一致值。

数据清理——缺失值 数据并不总是完整的 引起空缺值的原因 设备异常 与其它已有数据不一致而被删除 因为误解而没有被输入的数据 在输入数据时，有些数据认为得不到重视而没有被输入 对数据的改变没有进行日志记载

数据清理——缺失值的处理方法 忽略元组：当缺少类标号时通常这样处理(在分类任务中)。除非同一记录中有多个属性缺失值，否则该方法不是很有效。 忽略属性列：如果该属性的缺失值太多，如超过80%，则在整个数据集中忽略该属性。 人工填写缺失值：通常情况下，该方法费时费力，并且当数据集很大或缺少很多值时，该方法可能行不通。 自动填充缺失值：有三种不同的策略。 策略一：使用一个全局常量填充缺失值，将缺失的属性值用同一个常数替换。 策略二：使用与给定记录属同一类的所有样本的均值或众数填充缺省值。 策略三：用可能值来代替缺失值：可以用回归、基于推理的工具或决策树归纳确定。

数据清理——噪声数据的平滑方法 噪声是测量变量的随机错误或偏差。噪声是测量误差的随机部分，包含错误或孤立点值。 导致噪声产生的原因有： 数据收集的设备故障 数据录入过程中人的疏忽 数据传输过程中的错误 目前噪声数据的平滑方法包括： 分箱：分箱方法通过考察“邻居”(即周围的值)来平滑有序数据的值。 聚类：聚类将类似的值组织成群或“簇”。 回归：让数据适合一个函数来平滑数据。

数据平滑实例 一组排序后的数据(单位：元)：4，8，15，21，21，24，25，28，34 划分为等深的箱 用箱平均值进行平滑 箱1：4，8，15 箱2：21，21，24 箱3：25，28，34 用箱平均值进行平滑 箱1：9，9，9（下同） 用箱的边界进行平滑 箱1：4，4，15 箱3：25，25，34

数据集成 将两个或多个数据源中的数据，存放在一个一致的数据存储设备中。 在数据集成时，有许多问题需要考虑，数据一致性和冗余是两个重要问题。 不同表中可能使用不同名称来指示同一属性，正如一个人有多个不同的别名或不同的人拥有相同的名字，这样将导致数据的不一致或冲突。 一个属性是冗余的，如果它能由另一个表“导出”；属性或维命名的不一致也可能导致数据集中的冗余。

数据变换 平滑：去除数据中的噪声数据 聚集：汇总，数据立方体的构建 数据概化：沿概念分层高上汇总 规范化：将数据按比例缩放，使之落入一个小的特定区间（消除量纲的影响） 最小-最大规范化 Z-score规范化 小数定标规范化 属性构造 通过现有属性构造新的属性，并添加到数据集中

数据变换——规范化 最小-最大规范化 Z-score规范化 小数定标规范化

数据变换——特征构造 特征提取(Feature Extraction) 映射数据到新的空间 特征构造 由原始数据创建新的特征集 从不同视角提示重要和有趣的特征 傅里叶变换(Fourier Transform) 小波变换(Wavelet Transform) 特征构造 由一个或多个原始特征共同构造新的特征

数据变换——离散化与概念分层 离散化 概念分层 通过将属性域划分为区间，减少给定连续属性值的个数。区间标号可以代替实际的数据值。 通过使用高层的概念（比如：老年，中年，青年）来替代底层的属性值（比如：实际的年龄数据值）来规约数据 概念分层可以用树来表示，树的每一个节点代表一个概念（比如：按地区划分世界）

无监督离散化 原始数据 等宽离散化 等频离散化 K-means

有监督离散化 基于熵的离散化(Entropy based approach)

数据归约 维规约的好处 从记录和维度两个方面减少数据量 维归约 如果维度较低，许多数据挖掘算法效果会更好。 维度(数据特征的数目)归约是指通过使用数据编码或变换，得到原始数据的归约或“压缩”表示。 如果原始数据可以由压缩数据重新构造而不丢失任何信息，则该数据归约是无损的。 如果只能重新构造原始数据的近似表示，则该数据归约是有损的。 维规约的好处 如果维度较低，许多数据挖掘算法效果会更好。 维归约使模型涉及更少的特征，因而可以产生更容易理解的模型。 使用维归约可以降低数据挖掘算法的时间和空间复杂度。

数据归约——抽样 抽样是一种选择数据对象子集进行分析的常用方法 统计学使用抽样是因为得到感兴趣的整个数据集的费用太高、太费时间 事先调查和最终的数据分析 统计学使用抽样是因为得到感兴趣的整个数据集的费用太高、太费时间 数据挖掘使用抽样是因处理所有的数据的费用太高、太费时间

有效抽样原理 如果样本是有代表性的，则使用样本与使用整个数据集的效果几乎一样 如果数据对象的均值是感兴趣的性质，而样本具有近似于原数据集的均值，则样本是有代表性的 抽样是一个统计过程，特定样本的代表性是变化的

数据归约——抽样 用数据较小的随机样本表示大的数据集 简单随机抽样 分层抽样 无放回抽样 有放回的抽样 特点 随着每个项被抽出，它被从构成总体的所有对象集中删除 有放回的抽样 对象被选中时不从总体中删除 分层抽样 特点 总体由不同类别的对象组成 每种类型的对象数量差别很大 先对数据集进行分组：数据集D被划分为互不相交的“层”，则可通过对每一层按一定比例简单随机选样得到D的分层选样 利用聚类实现分层抽样：将数据集D划分成m个不相交的簇，再在聚类结果的簇上进行简单随机抽样

案例 8000 个点 2000个点 500个点

聚类抽样 同分层抽样的原理一样

数据归约——特征选择 特征选择 概念：从一组已知特征集合中选择最具代表性的特征子集，使其保留原有数据的大部分信息，即所选特征子集可以像原来的特征全集一样用来正确区分数据集的每个数据对象。通过特征选择，一些和任务无关或是冗余的特征被删除，从而提高数据处理的效率。 目的：去除不相关和冗余的特征，降低时间空间复杂度，提高数据质量及数据泛化能力。 理想的特征子集：每个有价值的非目标特征与目标特征强相关，而非目标特征之间不相关或是弱相关 基本步骤： 去掉与目标特征不相关的特征 删除冗余特征

特征选择过程流程 停止标准 评估 选择的属性 验证过程 不满足 特征子集 搜索策略 属性

特征选择 通过删除不相干的属性或维减少数据量 属性子集选择 启发式（探索式）搜索方法 找出最小属性集，使得数据类的概率分布尽可能的接近使用所有属性的原分布 减少出现在发现模式上的属性的数目，使得模式更易于理解 启发式（探索式）搜索方法 逐步向前选择 逐步向后删除 向前选择和向后删除相结合 判定归纳树

探索性选择方法 d个属性有2d个可能的子集 逐步向前选择 逐步向后删除 向前选择和向后删除相结合 由空属性集开始，选择原属性集中最好的属性，并将其添加入该集合，重复该步骤直到无法选择出最优属性或满足一定阈值约束为止。 逐步向后删除 由整个属性集开始，每一步都删除掉尚在属性集中的最坏属性。直到无法选择出最差属性为止或满足一定阈值约束为止。 向前选择和向后删除相结合 每一步选择一个最好属性，并删除一个最坏属性 可以使用一个临界值来判定上述三种方法的结束条件 判定归纳树 利用决策树的归纳方法对初始数据进行分类归纳学习，获得一个初始决策树，所有没有出现这个决策树上的属性均认为是无关属性，因此将这些属性从初始属性集合删除掉，就可以获得一个较优的属性子集。

属性子集选择的贪心方法 向前选择 向后删除 决策树归纳 初始属性集： （A1,A2,A3,A4,A5,A6） 初始归约集： ｛｝ => 归约后的属性子集： ｛A1,A4,A6｝ =>{A1,A3,A4,A5,A6} =>{A1,A4,A5,A6} 与决策树建模相似

特征选择的分类 根据有无类信息的指导可以将特征选择分为 根据特征或特征子集评价准则差异 有监督(有指导)的 无监督(无指导)的 半监督的：少数样本有类标号 根据特征或特征子集评价准则差异 Filter(过滤式) :根据数据的内在特性，对选取的特征子集进行评价，独立于学习算法。该类算法运行效率高，适用于大规模数据集 Wrapper（封装式）：将后续学习的结果作为特征子集评价准则的一部分。该类算法效果好，但效率低

有监督的特征选择方法 特征评估方法 距离度量 不一致度 类间距离（欧氏、马氏距离） 概率距离度量 相关度 定义：某种模式下，如果两个样本除了类别外其余特征都相同，则说这个模式不一致。比如：特征模式A［X,Y,C］，其中X，Y 是一般特征，C是目标特征。样本A[0,1,1],B[0,1,0],A和B的前两个特征相同，而类别却不同。 某种模式下的不一致数目：在这种模式下所有样本个数减去不同类别中最多的样本个数。Eg:在模式P下有n个样本，在他们当中有c1个属于类别1， c2个属于类别2， c3个属于类别3，且满足条件c1+c2+c3=n;如果c3=max(c1,c2,c3),则不一致数目为U=n-c3.

典型算法(FCBF) 1-4行为第一步，主要用来去除不相关特征。 6-12行为第二步，主要用来删除冗余特征。

一种基于特征相关性的特征选择 基本步骤： 输入：训练数据集D。 步骤1 ：离散化及初始化：离散数据集D中的连续特征，结果仍用D表示。 步骤2 ：特征聚类： 步骤2.1 ：根据对称的不确定性计算数据集D中任意两个特征之间的相关度； 步骤2.2： 根据特征之间的相关度大小进行聚类：在聚类过程中，首先将每个特征看成包含一个特征的簇，以特征之间相关度大小进行聚类，簇中每个特征至少与该簇其他特征中的一个特征之间相关度超过阈值。 步骤3：选择代表性特征(用于删除冗余特征)。 步骤4 ：将步骤3 精简后的特征集按照与目标特征之间的相关性强弱进行再次选择(用于去除不相关特征)。

一种无监督特征选择方法 样本聚类法 选择的依据是同类样本相同特征的取值相同或相近 特征聚类(子空间聚类) 第一步：聚类； 第二步：根据特征重要性评价函数计算特征的重要性； 第三步：依据重要性进行特征选择。 特征聚类(子空间聚类) 选择的依据是在相同数据集的不同子空间搜索簇群。先对所有特征进行聚类，然后在每个簇中挑选出具有代表性的特征共同作为最终的特征子集。

数据归约——数据压缩 数据压缩——用数据编码或者变换，得到原始数据的压缩表示。 有损压缩 VS. 无损压缩 无损(loseless)压缩：可以不丢失任何信息地还原压缩数据 例如：字符串压缩 有广泛的理论基础和精妙的算法 在解压缩前对字符串的操作非常有限 有损(lossy)压缩：只能重新构造原数据的近似表示 例如：音频/视频压缩 有时可以在不解压整体数据的情况下，重构某个片断 两种有损数据压缩的方法：小波变换和主成分分析

主成分分析(PCA) 找出新的属性(主成分)，这些属性是原属性的线性组合 属性之间相互正交的 用于连续属性的线性代数技术 捕获数据的最大变差 x2 x1 e

第二章 数据处理基础 2.1数据及数据类型 2.2 数据统计特性 2.3 数据预处理 2.4 相似性度量 2.2.1 据的中心度量 2.2.2 据散布程度度量 2.3 数据预处理 2.3.1 数据清理 2.3.2 数据聚合 2.3.3 数据变换 2.3.4 数据归约 2.4 相似性度量 53

2.4 相似性度量 2.4.1 属性之间的相似性度量 2.4.2 对象之间的相似性度量

简单数据对象之间的相似度和相异度 相似度 两个对象相似程度的数值度量，两对象越相似，它们的相似度就越高。相异度与相似度相反。 属性类别 标称的 序数的 S=1-d 区间的或 比率的

连续属性之间的相关度 线性相关系数 对于两个连续特征(x,y)，其相关度的计算公式： r的取值范围在［-1，1］，r的值越接近1或-1，表示两特征的相关性越强，越接近于0，相关性越弱。 不足：对于非线性的数据的相关性计算会存在偏差。

余弦相似度 如果(文档) d1 和 d2 是两(文档)向量，则 cos( d1, d2 ) = (d1  d2) / ||d1|| ||d2|| , 其中， 表示向量点积， || d || 是向量d的长度. 例: d1 = 3 2 0 5 0 0 0 2 0 0 d2 = 1 0 0 0 0 0 0 1 0 2 d1  d2= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5 ||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481 ||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245 cos( d1, d2 ) =0 .3150

离散属性间的相关性计算 对称的不确定性 离散型数据间相关性计算（互信息） 特征x的信息熵 已知变量y后x的条件信息熵 信息增益 互信息

数据对象之间的相异度 距离： 欧几里得距离 其中，n的维数（总特征数），Xk和Yk分别表示X和Y的第k个分量 闵可夫斯基(Minkowski )距离 x=1,城市块（曼哈顿）距离 x=2,欧几里得距离 x=∞,切比雪夫(Chebyshev)距离

Minkowski 距离 Distance Matrix 60

距离的性质 相似度的性质： 非负性 对称性（有些距离定义不满足这一条！） 三角不等式（有些距离定义不满足这一条！） 仅当x=y时，s(x,y)=1.0<=s<=1 对称性

马氏距离 由印度统计学家Mahalanobis于1936年引入的 考虑了属性之间的相关性 可以更准确地衡量多维数据之间的距离 计算公式如下( 为m×m的协方差矩阵 ) 不足 协方差矩阵难以确定 计算量大 不适合大规模数据集

Canberra/Bray Curtis/Czekanowski距离

Mahalanobis距离 Covariance Matrix: C A: (0.5, 0.5) B B: (0, 1) Mahal(A,B) = 5 Mahal(A,C) = 4 B A

二值属性 二元数据相似性度量 M01 = x取0并且y取1的属性的个数 Jaccard系数 简单匹配系数(Simple Matching Coefficient,SMC)： SMC = 值匹配的属性个数 /属性个数 = (M11 + M00) / (M01 + M10 + M11 + M00) Jaccard系数 J = 匹配的个数 /不涉及0-0匹配的属性个数 = (M11) / (M01 + M10 + M11)

例子 X = （1 0 0 0 0 0 0 0 0 0） Y= （ 0 0 0 0 0 0 1 0 0 1） M01 = 2 (x取0并且y取1的属性的个数) M10 = 1 (x取1并且y取0的属性的个数) M00 = 7 (x取0并且y取0的属性的个数) M11 = 0 (x取1并且y取1的属性的个数) SMC = (M11 + M00)/(M01 + M10 + M11 + M00) = (0+7) / (2+1+0+7) = 0.7 J = M11 / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0

符号、顺序和比例数值属性 符号属性变量 对于符号变量，最常用的计算对象p和对象q之间差异程度的方法是简单匹配方法，其定义如下： 其中s表示对象p和对象q取值相同状态的符号变量个数，M为符号变量总的状态个数，M-s表示对象p和对象q取不同状态的符号变量个数。

符号、顺序和比例数值属性 顺序变量 在计算对象间的差异程度时，顺序变量的处理方法与间隔数值变量的处理方法类似。涉及变量f的差异程度计算方法如下： 第i个对象的f变量值记为Xif,变量f有个Mf有序状态，利用等级1,2,…, Mf分别替换相应的Xif ，得到相应的rif， 。 将顺序变量做变换 映射到区间[0, 1]上。 利用有关间隔数值变量的任一种距离计算公式来计算差异程度。

符号、顺序和比例数值属性 比例数值变量 在计算比例数值变量所描述对象间的距离时，有三种 处理方法，它们是： 将比例数值变量当做区间间隔数值变量来进行计算处理，这种方法不太好，因为非线性的比例尺度可能会被扭曲。 将比例数值变量看成是连续的顺序变量进行处理。 利用变换(如对数转换 )来处理第i个对象中属性f的值xif得到yif ，将yif当作间隔数值变量进行处理。这里的变换需要根据具体定义或应用要求而选择log或log-log或其它变换。相对来说这一方法效果最好。

符号、顺序和比例数值属性 混合类型的变量 计算具有混合类型变量对象之间差异程度的一种方法是将变量按类型分组，对每种类型的变量单独进行聚类分析。 另一种方法是将不同类型的变量组合在一个差异度矩阵中，把所有变量转换到统一的区间[0,1]中.假设数据集包含m种不同类型的变量，对象p和q之间的差异度d(p,q)定义为:

对象之间的相似系数 可以通过一个单调递减函数，将距离转换成相似性度量，相似性度量的取值一般在区间[0,1]之间，值越大，说明两个对象越相似。 采用负指数函数将Euclidean距离转换为相似性度量s，即 采用取Euclidean距离的倒数，为了避免分母为0的情况，在分母上加1，即 若距离在0～1之间，可采用与1的差作为相似系数，即：

作业：