7-8
王 灿
数据挖掘
sjwj@dlc.zju.edu.cn
0703004
数据预处理
为什么要预处理数据?
? 现实世界的数据是“肮脏的” —— 数据多了,
什么问题都会出现
? 不完整的:有些感兴趣的属性缺少属性值,或仅包
含聚集数据
? 含噪声的:包含错误或者“孤立点”
? 不一致的:在编码或者命名上存在差异
? 没有高质量的数据,就没有高质量的挖掘结果
? 高质量的决策必须依赖高质量的数据
? 数据仓库需要对高质量的数据进行一致地集成
数据质量的多维度量
? 一个广为认可的多维度量观点,
? 精确度
? 完整度
? 一致性
? 合乎时机
? 可信度
? 附加价值
? 可访问性
? 跟数据本身的含义相关的
? 内在的、上下文的、表象的
数据预处理的主要任务
? 数据清理
? 填写空缺的值,平滑噪声数据,识别、删除孤立点,解决不一致性
? 数据集成
? 集成多个数据库、数据立方体或文件
? 数据变换
? 规范化和聚集
? 数据归约
? 得到数据集的压缩表示,它小得多,但可以得到相同或相近
的结果
? 数据离散化
? 数据归约的一部分,通过概念分层和数据的离散化来规约数
据,对数字型数据特别重要
空缺值
? 数据并不总是完整的
? 例如:数据库表中,很多条记录的对应字段没有相
应值,比如销售表中的顾客收入
? 引起空缺值的原因
? 设备异常
? 与其他已有数据不一致而被删除
? 因为误解而没有被输入的数据
? 在输入时,有些数据应为得不到重视而没有被输入
? 对数据的改变没有进行日志记载
? 空缺值要经过推断而补上
如何处理空缺值
? 忽略元组:当类标号缺少时通常这么做(假定挖掘任
务涉及分类或描述),当每个属性缺少值的百分比变
化很大时,它的效果非常差。
? 人工填写空缺值:工作量大,可行性低
? 使用一个全局变量填充空缺值:比如使用 unknown或
-∞
? 使用属性的平均值填充空缺值
? 使用与给定元组属同一类的所有样本的平均值
? 使用最可能的值填充空缺值:使用像 Bayesian公式
或判定树这样的基于推断的方法
噪声数据
? 噪声:一个测量变量中的随机错误或偏差
? 引起噪声数据的原因
? 数据收集工具的问题
? 数据输入错误
? 数据传输错误
? 技术限制
? 命名规则的不一致
如何处理噪声数据
? 分箱 (binning),
? 首先排序数据,并将他们分到等深的箱中
? 然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平
滑等等
? 聚类,
? 监测并且去除孤立点
? 计算机和人工检查结合
? 计算机检测可疑数据,然后对它们进行人工判断
? 回归
? 通过让数据适应回归函数来平滑数据
数据平滑的分箱方法
? price的排序后数据(单位:美元),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
? 箱 2,22,22,22
? 箱 3,29,29,29
? 用箱边界平滑,
? 箱 1,4,4,15
? 箱 2,21,21,24
? 箱 3,25,25,34
聚类
? 通过聚类分析查找孤立点,消除噪声
回归
x
y
y = x + 1
X1
Y1
Y1’
数据集成
? 数据集成,
? 将多个数据源中的数据整合到一个一致的存储中
? 模式集成,
? 整合不同数据源中的元数据
? 实体识别问题:匹配来自不同数据源的现实世界的
实体,比如,A.cust-id=B.customer_no
? 检测并解决数据值的冲突
? 对现实世界中的同一实体,来自不同数据源的属性
值可能是不同的
? 可能的原因:不同的数据表示,不同的度量等等
处理数据集成中的冗余数据
? 集成多个数据库时,经常会出现冗余数据
? 同一属性在不同的数据库中会有不同的字段名
? 一个属性可以由另外一个表导出,如“年薪”
? 有些冗余可以被相关分析检测到
? 仔细将多个数据源中的数据集成起来,能够减
少或避免结果数据中的冗余与不一致性,从而
可以提高挖掘的速度和质量。
BA
BA n
BBAAr
??)1(
))((
,?
??? ?
数据变换
? 平滑:去除数据中的噪声 (分箱、聚类、回归)
? 聚集:汇总,数据立方体的构建
? 数据概化:沿概念分层向上概化
? 规范化,将数据按比例缩放,使之落入一个小的特定
区间
? 最小-最大规范化
? z-score规范化
? 小数定标规范化
? 属性构造
? 通过现有属性构造新的属性,并添加到属性集中;以增加对
高维数据的结构的理解和精确度
数据变换 —— 规范化
? 最小-最大规范化
? z-score规范化
? 小数定标规范化
AAA
AA
A m i nn e wm i nn e wm a xn e w
m i nm a x
m i nvv _)__(' ??
?
??
A
A
d e vs ta n d a r d
m e a nvv
_'
??
j
vv
10'?
其中,j是使 Max(| |)<1的最小整数 'v
数据归约策略
? 数据仓库中往往存有海量数据,在其上进行复杂的数
据分析与挖掘需要很长的时间
? 数据归约
? 数据归约可以用来得到数据集的归约表示,它小得多,但可
以产生相同的(或几乎相同的)分析结果
? 数据归约策略
? 数据立方体聚集
? 维归约
? 数据压缩
? 数值归约
? 离散化和概念分层产生
? 用于数据归约的时间不应当超过或“抵消”在归约后的数据上挖掘节省的时间。
数据立方体聚集
? 最底层的方体对应于基本方体
? 基本方体对应于感兴趣的实体
? 在数据立方体中存在着不同级别的汇总
? 数据立方体可以看成方体的格
? 每个较高层次的抽象将进一步减少结果数据
? 数据立方体提供了对预计算的汇总数据的快速
访问
? 使用与给定任务相关的最小方体
? 在可能的情况下,对于汇总数据的查询应当使用数
据立方体
维归约
? 通过删除不相干的属性或维减少数据量
? 属性子集选择
? 找出最小属性集,使得数据类的概率分布尽可能的接近使用
所有属性的原分布
? 减少出现在发现模式上的属性的数目,使得模式更易于理解
? 启发式的(探索性的)方法
? 逐步向前选择
? 逐步向后删除
? 向前选择和向后删除相结合
? 判定归纳树
数据压缩
? 有损压缩 VS,无损压缩
? 字符串压缩
? 有广泛的理论基础和精妙的算法
? 通常是无损压缩
? 在解压缩前对字符串的操作非常有限
? 音频 /视频压缩
? 通常是有损压缩,压缩精度可以递进选择
? 有时可以在不解压整体数据的情况下,重构某个片断
? 两种有损数据压缩的方法:小波变换和主要成分分析
数值归约
? 通过选择替代的、较小的数据表示形式来减少数据量
? 有参方法:使用一个参数模型估计数据,最后只要存
储参数即可。
? 线性回归方法,Y=α+βX
? 多元回归:线性回归的扩充
? 对数线性模型:近似离散的多维数据概率分布
? 无参方法,
? 直方图
? 聚类
? 选样
直方图
? 一种流行的数据归约技术
? 将某属性的数据划分为不相交的子集,或桶,桶中放
置该值的出现频率
? 桶和属性值的划分规则
? 等宽
? 等深
? V-最优
? MaxDiff
0
5
10
15
20
25
30
35
40
10000 30000 50000 70000 90000
聚类
? 将数据集划分为聚类,然后通过聚类来表示数
据集
? 如果数据可以组成各种不同的聚类,则该技术
非常有效,反之如果数据界线模糊,则方法无

? 数据可以分层聚类,并被存储在多层索引树中
? 聚类的定义和算法都有很多选择
选样
? 允许用数据的较小随机样本(子集)表示大的数据集
? 对数据集 D的样本选择,
? 简单随机选择 n个样本,不回放:由 D的 N个元组中抽取 n个
样本
? 简单随机选择 n个样本,回放:过程同上,只是元组被抽取
后,将被回放,可能再次被抽取
? 聚类选样,D中元组被分入 M个互不相交的聚类中,可在其
中的 m个聚类上进行简单随机选择( m<M)
? 分层选样,D被划分为互不相交的“层”,则可通过对每一
层的简单随机选样得到 D的分层选样
选样 —— SRS
原始数据
选样 —— 聚类 /分层选样
原始数据 聚类 /分层选样
离散化
? 三种类型的属性值,
? 名称型 —— e.g,无序集合中的值
? 序数 —— e.g,有序集合中的值
? 连续值 —— e.g,实数
? 离散化
? 将连续属性的范围划分为区间
? 有效的规约数据
? 基于判定树的分类挖掘
? 离散化的数值用于进一步分析
离散化和概念分层
? 离散化
? 通过将属性域划分为区间,减少给定连续属性值的
个数。区间的标号可以代替实际的数据值。
? 概念分层
? 通过使用高层的概念(比如:青年、中年、老年)
来替代底层的属性值(比如:实际的年龄数据值)
来规约数据
数据数值的离散化和概念分层生成
? 分箱( binning)
? 分箱技术递归的用于结果划分,可以产生概念分层。
? 直方图分析( histogram)
? 直方图分析方法递归的应用于每一部分,可以自动产生多级
概念分层。
? 聚类分析
? 将数据划分成簇,每个簇形成同一个概念层上的一个节点,
每个簇可再分成多个子簇,形成子节点。
? 基于熵的离散化
? 通过自然划分分段
通过自然划分分段
? 将数值区域划分为相对一致的、易于阅读的、
看上去更直观或自然的区间。
? 聚类分析产生概念分层可能会将一个工资区间划分
为,[51263.98,60872.34]
? 通常数据分析人员希望看到划分的形式为 [50000,
60000]
? 自然划分的 3-4-5规则常被用来将数值数据划
分为相对一致,“更自然”的区间
自然划分的 3-4-5规则
? 规则的划分步骤,
? 如果一个区间最高有效位上包含 3,6,7或 9个不同的值,就
将该区间划分为 3个等宽子区间; (7?2,3,2)
? 如果一个区间最高有效位上包含 2,4,或 8个不同的值,就
将该区间划分为 4个等宽子区间;
? 如果一个区间最高有效位上包含 1,5,或 10个不同的值,就
将该区间划分为 5个等宽子区间;
? 将该规则递归的应用于每个子区间,产生给定数值属性的概
念分层;
? 对于数据集中出现的最大值和最小值的极端分布,为了避免
上述方法出现的结果扭曲,可以在 顶层分段 时,选用一个大
部分的概率空间。 e.g,5%-95%
3-4-5规则 —— 例子
(-$4000 -$5,000)
(-$400 - 0)
(-$400 -
-$300)
(-$300 -
-$200)
(-$200 -
-$100)
(-$100 -
0)
(0 - $1,000)
(0 -
$200)
($200 -
$400)
($400 -
$600)
($600 -
$800) ($800 -
$1,000)
($2,000 - $5,000)
($2,000 -
$3,000)
($3,000 -
$4,000)
($4,000 -
$5,000)
($1,000 - $2,000)
($1,000 -
$1,200)
($1,200 -
$1,400)
($1,400 -
$1,600)
($1,600 -
$1,800) ($1,800 - $2,000)
msd=1,000 Low=-$1,000 High=$2,000 第二步
第四步
第一步 -$351 -$159 profit $1,838 $4,700
Min Low (i.e,5%-tile) High(i.e,95%-0 tile) Max
count
(-$1,000 - $2,000)
(-$1,000 - 0) (0 -$ 1,000)
第三步
($1,000 - $2,000)
分类数据的概念分层生成
? 分类数据是指无序的离散数据,它有有限个值(可能
很多个)。
? 分类数据的概念分层生成方法,
? 由用户或专家在模式级显式的说明属性的部分序。
? 通过显示数据分组说明分层结构的一部分。
? 说明属性集,但不说明它们的偏序,然后系统根据算法自动
产生属性的序,构造有意义的概念分层。
? 对只说明部分属性集的情况,则可根据数据库模式中的数据
语义定义对属性的捆绑信息,来恢复相关的属性。
属性集的规格
? 根据在给定属性集中,每个属性所包含的不同
值的个数,可以自动的生成概念分成;不同值
个数最多的属性将被放在概念分层的最底层。
country
province
city
street
5个不同值
65 个不同值
3567 个不同值
674,339 个不同值