2
0
2
2
/
5
/
9
4. 数据预处理
2
0
2
2
/
5
/
9
1
为什么要进行数据挖掘?
现实世界的数据是脏的
不完整: 缺乏属性值，缺乏有意义的属性，或者
只包含了汇总数据
., occupation=“ ”
有噪声: 包含错误的数据或异常值
., Salary=“-10”
不一致: 在代码或者名字中存在矛盾或不一致
., Age=“42” Birthday=“03/07/1997”
., Was rating “1,2,3”, now rating “A, B, C”
., discrepancy between duplicate records
2
0
2
2
/
5
/
9
2
为什么数据预处理重要?
No quality data, no quality mining results!
Quality decisions must be based on quality data
., duplicate or missing data may cause incorrect or
even misleading statistics.
Data warehouse needs consistent integration of
quality data
Data extraction, cleaning, and transformation
comprises the majority of the work of building a data
warehouse
2
0
2
2
/
5
/
9
3
2
0
2
2
/
5
/
9
4
数据预处
理的主要
内容：
2
0
2
2
/
5
/
9
数据预处理的主要内容
一、原始数据的表述
二、数据清理
三、数据变换
四、元组的归约
五、属性的归约
2
0
2
2
/
5
/
9
5
数据样本是数据挖掘过程的基本组成部分。
一、原始数据的表述
2022/5/9
6
每个样本都用几个特征来描述，每个特征有不
同类型的值。
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
常见的数据类型有：数值型和分类型。
数值型包括实型变量和整型变量
注：具有数值型值的特征有两个重要的属
性：其值有顺序关系和距离关系。
7
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
一个有两个值的分类型变量:
分类型变量的两个值可以平等或不平等。
原则上可以转化成一个二进制的数值型变量，
这种数值型变量有两个值：0或1；
而有N值的分类型变量原则上可以转化成
一个二进制的数值型变量，这种数值型变
量有N个值。
8
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
例如：如果变量“眼睛颜色”有4个值：黑色、
蓝色、绿色、褐色。
特征值 编码
黑色 1000
蓝色 0100
绿色 0010
褐色 0001
9
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
变量的分类：连续型变量和离散型变量。
连续型变量也认为是定量型或是量度型，
是指在一定区间内可以任意取值的变量。
离散型变量也叫定性型变量，是指全部可
能取到的不相同的值是有限个的变量。
注：一种特殊类型的离散型变量是周期变
量，例如：星期、月和年中的日期。
10
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
与时间有关的数据分类：
静态数据——数据不随时间变化而变化
动态数据（时间数据）——随时间变化而
变化的属性。
注：大多数数据挖掘方法更适用于静态数
据，在对动态数据进行挖掘时要有特殊的考
虑和预处理。
11
2
0
2
2
/
5
/
9
二、数据清理——缺失值的填补
2
0
2
2
/
5
/
9
对数据挖掘的实际应用而言，即使数据量很大，
具有完整数据的案例也非常少，这样就面临数据
的缺失问题。
应用数据挖掘方法之前如何处理这样现象，最
简单的办法是减少数据集，去掉所有有缺失值的
样本。
如果我们不想扔掉这些有缺失值的样本，就必
须找到它们的缺失值，用什么方法来实现呢？
填补缺失值。
12
2
0
2
2
/
5
/
9
1、单一填补法
（1）均值填补法。
均值填补法是根据与含缺失值的目标属性相关性高的
其它属性的信息将样品分为若干组，然后分别计算各
组目标属性的均值，将各组均值作为组内所有缺失项
的填补值。
均值填补的优点是操作简便，并且可以有效地降低其
点估计的偏差。
但它的缺点也比较突出：首先，由于同组中的缺失值
由同一个值填补，填补结果歪曲了目标属性的分布；
其次，也导致在均值和总量估计中对方差的低估。
2
0
2
2
/
5
/
9
13
例：
2
0
2
2
/
5
/
9
14
均值填补：
2
0
2
2
/
5
/
9
15
2
0
2
2
/
5
/
9
（2）随机填补法。
随机填补法是采用某种概率抽样的方式，
从有完整信息的元组中抽取缺失数据的填补
值的方法。
它虽然能够避免均值填补中填补值过于凝
集以及容易扭曲目标属性分布的弱点，使得
填补值的分布与真值分布更为接近。但它却
增大了估计量的方差，并且稳定性不够。
2
0
2
2
/
5
/
9
16
2
0
2
2
/
5
/
9
（3）热卡填补法。
热卡填补法（hot deck imputation）是规定一个或多
个排序属性，按其观察值大小对全部观察单位排序，
如果选择的是两个以上的属性，排序按属性的入选
顺序依次进行。
排序属性值完全相同的观察单位称为匹配，缺失值
就用与之匹配的观察单位的属性值来填补。如果有
多例相匹配，可取第一例或随机取其一。如果没有
相匹配的，可以每次减少一个排序属性，再找相匹
配的元组。如果直到最后一个排序属性，还没有找
到相匹配的，则需要重新规定排序属性。
2
0
2
2
/
5
/
9
17
项目 性别 年龄 学生身分 收入 办卡
1 男 >45 否 高 会
2 女 31~45 否 高 会
3 女 20~30 是 低 会
4 男 <20 是 低 不会
5 女 20~30 是 中 不会
6 女 20~30 否 中 会
7 女 31~45 否 高 会
8 男 31~45 是 中 不会
9 男 31~45 否 中 会
10 女 <20 是 低 会
2
0
2
2
/
5
/
9
（4）回归填补法。
回归填补法是指在现有观察值基础上，以
含有缺失值的目标属性为因变量，以与目标
属性相关性高的其它属性为自变量，建立最
小二乘回归模型或判别模型，以估计缺失值。
注意：以上几种方法都存在扭曲样本分布
的问题，如均值填补会降低属性之间的相关
关系，回归填补则会人为地加大变量之间的
相关关系等。
2
0
2
2
/
5
/
9
18
例：
2
0
2
2
/
5
/
9
19
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
（二）异常值（孤立点）探测
在大型数据集中，通常存在着不遵循数据
模型的普遍行为的样本，这些样本和其他残
余部分数据有很大不同或不一致，叫做异常
点。
异常点可能是由测量误差造成的，也可能
是数据故有的可变性结果。
例如：在检测银行交易中的信用卡欺诈行为
时，异常点是可能揭示欺诈行为的典型例子。
20
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
异常值的探测方法
第一，一维样本异常点的检测方法
• 例如：如果所给的数据集用20个不同的值描述年龄特
征：
3, 56, 23, 39, 156, 52, 41, 22, 9,28,
139, 31, 55, 20, -67, 37, 11, 55, 45, 37
均值=; 标准差=
阈值=均值±2×标准差
那么，所有在[, ]区间以外的数据都是潜
在的异常点。根据实际可以把区间缩减到[0, ]
，由这个标准发现3个异常点：156, 139, -67。 21
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
第二，基于距离的异常点检测（二维以上数据）
例如：数据集为：
S={S1,S2,S3,S4,S5,S6,S7}＝
{(2,4),(3,2),(1,1),(4,3),(1,6),(5,3),(4,2)}
欧氏距离 d=[(X1-X2)
2+(Y1-Y2)
2]1/2
取阈值距离为 d=3
22
异常
点
2022/5/9 23
根据所用程序的结果和所给的阈值，可选
择S3和S5作为异常点。
2022/5/9 24
2
0
2
2
/
5
/
9
第三：基于分类预测模型的异常值探测
异常值的探测也可以认为是一类特殊的分类问题。因
为对于一般的分类问题，考虑的是如何将各种类别有
效地分开，而在异常值探测中，分类的目标是准确地
描述总体的正常行为特征，在此之外大范围的其它对
象被视为异常值。
其基本思想是：对总体的特征建立分类模型，形成正
常行为的特征库；然后针对新的数据判断其是否属于
正常行为，从而认定其是否与总体偏离，发生偏离的
即是异常值。
根据所建立的分类器的不同，异常值的探测方法有以
下几种：决策树分类；贝叶斯分类；神经网络分类；
聚类。
2
0
2
2
/
5
/
9
25
2
0
2
2
/
5
/
9
异常值探测的应用
信用卡、保险行业以及电信用户欺诈行为的探测。
异常值探测对于欺诈行为的发现，主要是基于这
样的思想：
任何人在使用信用卡、投保和电信消费的正常行为都
是有一定的规律的，并且可以通过这些行为产生的信
息总结出这些规律；
由于欺诈行为和正常的行为存在严重的差异，检查出
这些差异就可以探测出是否存在欺诈发生。因此可以
认为，欺诈行为的发现过程就是一种异常数据的挖掘
过程。
2
0
2
2
/
5
/
9
26
2
0
2
2
/
5
/
9
具体的实现途径是：利用聚类、神经网络和决策
树等分类方法，通过分析用户的购买、投保或消
费习惯，细分客户，以此分辨出偏离模式的信用
卡欺诈行为；然后，推导出合法交易的定义，建
立模型；利用模型来分析一个新的交易是合法还
是非法。
也可以通过六西格玛探测、聚类等方法，寻找出
与正常投保行为有极大差别的不正常行为，即有
可能的欺诈行为。
除了利用上述技术对异常数据进行识别外，还可
以通过关联规则的Apriori算法寻找异常数据间的
隐含模型，从而达到反欺诈的目的。
2
0
2
2
/
5
/
9
27
2
0
2
2
/
5
/
9
例如：对电信用户的欺诈行为探测的具体做法是：
首先，将目标属性定为无意欠费客户和恶意欠费两类；
其次，选择属性作为输入属性，通常包括服务合同属性
（如服务类型、服务时间、交费类型等）、客户的基本
状态（如性别、年龄、收入、婚姻状况、受教育年限/学
历、职业、居住地区等）以及经常或定期改变的数据
（如每月消费金额、交费纪录等）；
然后，将分类方法用于预先选定的包含客户欠费状态的
训练集中，从而挖掘归纳出规则集；
最后，利用所获取的规则，对电信企业新用户的缴费情
况进行预测分类，从而达到预防欺诈的目的。
2
0
2
2
/
5
/
9
28
2
0
2
2
/
5
/
9
三、数据变换
数据变换是将数据转换成适合于挖掘的形式。
数据变换可能涉及到如下内容：
数据规范化
数据平滑
数据概化
2
0
2
2
/
5
/
9
29
为什么要进行标准化？
一些数据挖掘方法，需要对数据进行标准化以获
得最佳的效果。
例如，对于分类算法，如涉及神经网络的算法
或诸如最临近分类和聚类的距离度量分类算法，
都需要将训练样本属性度量输入值规范化，这
样有助于加快学习阶段的速度。
对于基于距离的方法，规范化可以帮助防止具
有较大初始值域的属性与具有较小初始值域的
属性相比，权重过大。
2
0
2
2
/
5
/
9
30
（一）规范化（标准化）
小数缩放移动小数点，但是要仍然保持原始数据的
特征。小数点的移动位数依赖于X的最大绝对值。
典型的缩放是保持数值在-1和1范围内，可以用格
式描述：
1、小数缩放
规范化是指通过将属性数据按比例缩放，使之落
入一个小的特定区间，如到，对属性规范
化。
2022/5/9 31
2、最小-最大规范化
2022/5/9 32
最小-最大规范化是对原始数据进行线性变换。
最小-最大规范化的格式：
从而将X的值映射到[0，1]中。
2
0
2
2
/
5
/
9
3、标准差规范化（Z-SCORE规范化）
标准差规范化是将某个属性的值基于其平均值和
标准差进行规范化。
标准差规范化的格式是
其中： 是均值； 是标准差。
注意：该方法适用于当属性X的最大和最小值未知，
或孤立点左右了最大-最小规范化的情况下。
2
0
2
2
/
5
/
9
33
为什么要进行数据的平滑？
一个数值型的特征可能包含许多不同的值。对许
多数据挖掘技术来说，这些值之间小小的区别并
不重要，但可能会降低挖掘方法的性能并影响最
终的结果。因此，对变量的值进行平滑处理很重
要。
2
0
2
2
/
5
/
9
34
（二）数据平滑(离散化)
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
数据平滑：是指去掉数据中的噪声。这种技术包括
分箱技术、聚类和回归。
35
例如：进行圆整处理。如果给定特征的值的集合是
平滑后的集合是
2
0
2
2
/
5
/
9
1、分箱
分箱方法是通过考察“邻居”来平滑存储数据的
值。存储的值被分布到一些“桶”或“箱”中。
由于分箱方法参考的是相邻的值，因此，它进行
的是局部平滑。分箱方法有以下几种：
按箱平均值平滑
按箱中值平滑
按箱边值平滑。
2
0
2
2
/
5
/
9
36
2
0
2
2
/
5
/
9
例如：某产品的价格排序后的数据为：4、8、15、21
、21、24、25、28、34。
首先，将上述数据划分为等深的箱：
箱1：4、8、15
箱2：21、21、24
箱3：25、28、34
（1）按箱中值平滑：
箱1：8、8、8
箱2：21、21、21
箱3：28、28、28
2
0
2
2
/
5
/
9
37
2
0
2
2
/
5
/
9
排序后的数据为：4、8、15、21、21、24、25、28、
34。
箱1：4、8、15
箱2：21、21、24
箱3：25、28、34
（2）按箱平均值平滑：
箱1：9、9、9
箱2：22、22、22
箱3：29、29、29
2
0
2
2
/
5
/
9
38
排序后的数据为：4、8、15、21、21、24、25、28、
34。
箱1：4、8、15
箱2：21、21、24
箱3：25、28、34
（3）按箱边界值平滑：
箱1：4、4、15
箱2：21、21、24
箱3：25、25、34
2
0
2
2
/
5
/
9
39
对于按箱边值平
滑来说，箱中的
最大和最小值被
视为箱边界。箱
中每一个值被最
近的边界值替换。
2、回归
x
y
y = x + 1
X1
Y1
Y1’
2
0
2
2
/
5
/
9
40
3、通过自然划分分段
3-4-5规则可以将数值数据划分成相对一致和“自然”区
间。
如果一个区间在最高有效位上包含3, 6, 7或9个不同的
值，则将该区间划分为3个区间（对于3、6和9划分为
3个等宽区间；对于7，按2-3-2分组，划分为3个区间）；
如果最高有效位上包含2, 4或8个不同的值，则将区间
划分为4个等宽区间；
如果最高有效位上包含1, 5或10个不同的值，则将区
间划分为5个等宽区间.
2
0
2
2
/
5
/
9
41
EXAMPLE
(-$400 -$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,000Step 2:
Step 4:
Step 1: -$351 -$159 profit $1,838 $4,700
Min Low (, 5%-tile) High(, 95%-0 tile) Max
count
(-$1,000 - $2,000)
(-$1,000 - 0) (0 -$ 1,000)
Step 3:
($1,000 - $2,000)
2
0
2
2
/
5
/
9
42
为什么要进行数据概化？
数据库通常存放有大量的细节数据，但我们通常希
望看到的是以简洁的、更一般的描述形式来观察数
据的特点。
例如：对于一个销售经理来说，面对顾客数据库，
他可能不想考察每个顾客的事务，而更愿意概化
到高层的数据，比如说，根据地区按顾客的分组
汇总，来观察每组顾客的购买频率和顾客的收入，
以此来分析区域差异。
2
0
2
2
/
5
/
9
43
（三）数据概化
2
0
2
2
/
5
/
9
数据概化：是一个过程，它将大的任务相关的数
据集从较低的概念层抽象到较高的概念层。
使用概念分层，用高层次概念替换低层次“原始”
数据。
例如，分类的属性，“street”，可以概化为较高
层的概念，如“city”或“country”；再如，“年龄”
可以概化为“青年”、“中年”和“老年”等。
2
0
2
2
/
5
/
9
44
2
0
2
2
/
5
/
9
四、元组的归约
为什么要进行离散化？
在机器学习和数据挖掘中，已经发展了处
理离散型数据的很多算法，如决策树、关联
规则及基于粗糙集理论的许多方法，而这些
算法对于连续型数据却不适用；另外，有些
算法即使能处理连续型数据，挖掘和学习也
没有处理离散型数据有用和有效。
离散化后可以达到归约元祖的目的。
2
0
2
2
/
5
/
9
45
连续属性的离散化就是将数值属性的值域
划分为若干子区间，每个区间对应一个离散
值。
离散化方法依据不同的标准主要有以下几
种划分：有监督和无监督、动态和静态、全
局和局部、自顶向下和自底向上等。
2
0
2
2
/
5
/
9
46
2
0
2
2
/
5
/
9
按照离散化过程中是否考虑类别信息，可以将离散化
算法分为有监督算法和无监督算法。
有监督算法是其输入样本集中除了待离散化的数值
属性外，还有一个或多个离散型的类别属性。这种
算法在离散化时，将类别信息作为参考。
无监督离散化是在离散化过程中不考虑类别信息的方
法，其输入样本集中仅含有待离散化的属性。
早期的等宽、等频的离散化方法是无监督方法的典型代表。
无监督的方法的缺陷在于它对分布不均匀的数据不适用，对
异常点比较敏感。
2
0
2
2
/
5
/
9
47
1、有监督离散化和无监督离散化
2、动态和静态离散化
动态离散化方法是在建立分类模型的同时
对连续特征进行离散化，例如，算法。
在静态离散化方法中，离散化是先于分类
任务进行的。
2
0
2
2
/
5
/
9
48
2
0
2
2
/
5
/
9自顶向下的方法是离散化开始于空的分割点
（分裂点）列表，通过“分裂”区间增加新
的分割点到列表中的离散化过程。
自底向上是开始于属性的全部连续值作为分
割点的完全列表，以通过“合并”区间来移
除它们中的一部分作为离散化的过程。
2
0
2
2
/
5
/
9
49
3、自顶向下和自底向上
4、局部和全局离散化
局部离散化方法是仅对每一个属性的属性
值进行划分，如等宽区间法、等频区间法和
最大熵法等。
全局离散化则是考虑全部条件属性的属性
值进行划分的方法，如全局聚类分析方法。
2
0
2
2
/
5
/
9
50
2
0
2
2
/
5
/
9
（二）典型离散化的过程
一个局部单个属性的离散化过程主要由以下四步
组成（自底向上）：
• （1）对要离散化的属性的连续值排序。
• （2）根据一定的规则产生候选断点集，构造初始
区间。
• （3）按照合并的规则，合并相邻的初始区间。
• （4）制定停止标准，使得合并一直进行到符合停
止标准为止。
2
0
2
2
/
5
/
9
51
2
0
2
2
/
5
/
9
（三）离散化方法的评价
（1）区间的总数。
这是对模型简洁性的要求。理论上来说，离散得到的区间
数越少越好，便于理解；但区间数的减少另一方面也会导
致数据的可理解性变差。
（2）由离散化引起的不一致性的数目。
所谓不一致性是指当两个样本所有的条件属性取值相同而
类别属性的取值不同时，就称这两个样本是不一致的。
离散化后的不一致性数目至少应该比在离散化前原始数据
的不一致性数目少，且不一致性数目越少越好。
（3）预测精确度。
根据训练样本集预测新样本类别的准确率即是预测精确度，
预测精确度越高，当然就说明此离散化方法越好。
2
0
2
2
/
5
/
9
52
2
0
2
2
/
5
/
9
1、直方图方法
直方图方法是将要离散化的变量值从小到大排序，
然后对这些数值进行分组，最后，对这些进行赋
值。
依据分组的方式该方法又可以分为等宽和等频两
种。
等宽是指所分组是等距式分组。
等频是指所有的分组的次数是相等的。
2
0
2
2
/
5
/
9
（四）具体的离散化方法
53
2
0
2
2
/
5
/
9 采用Iris样本集进行统计模拟（数据来源：加州大学
UCI Machine Learning 的数据库中Iris样本集）。
Iris样本集是对3种鸢尾花：刚毛鸢(yuan)尾花、变色鸢
尾花、佛吉尼亚鸢尾花各抽取50个样本。属性是sepal
length in cm萼片长度、sepal width in cm萼片宽度、
petal length in cm花瓣长度、petal width in cm花瓣宽度。
2
0
2
2
/
5
/
9
等宽直方图离散化的应用
54
我们现在以花萼长（ sepal length in cm ）属
性为例，来进行连续型值属性的离散化。
具体步骤为如下：
（1）对要离散化的属性的连续值排序。
（2）根据一定的规则产生候选断点集，构
造初始区间。
2
0
2
2
/
5
/
9
55
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
数值 频数 数值 频数 数值 频数 数值 频数 数值 频数
1 5 10 8 7 1
3 9 7 5 3
1 4 3 2 1
4 1 6 6 8 1
2 6 6 3 1
5 7 4 4 4
6 6 9 7 1 1
56
2
0
2
2
/
5
/
9
（3）按照合并的规则，合并相邻
的初始区间。
根据斯特杰公式有：
n=1+=1+≈8
那么，
组距为 d=R/n
=()/8=
现分组如右：
2
0
2
2
/
5
/
9
分组 频数
~ 11
~ 30
~ 24
~ 24
~ 31
~7 17
7~ 7
~ 6
57
2
0
2
2
/
5
/
9
（4）制定停止标准，使得合并一直进行到
符合停止标准为止。
（5）防止过度拟合。
为防止过度拟合，应使得每个区间的频数大
于等于总体单位数的平方根。
sqrt(150)≈12
2
0
2
2
/
5
/
9
58
2
0
2
2
/
5
/
9
59
分组 频数
~ 11
~ 30
~ 24
~ 24
~ 31
~7 17
7~ 7
~ 6
2
0
2
2
/
5
/
9
进行重新分组：使得每个区间的频数大于12
2
0
2
2
/
5
/
9
分组 频数 赋值
~ 41 1
～ 48 2
~7 48 3
7~ 13 4
60
2
0
2
2
/
5
/
9
2、聚类
聚类算法可以用来将数据划分为群或簇。
每一个簇形成概念分层的一个节点，而所
有的节点在同一个概念层。每一个簇可以进
一步分成若干子簇，形成较低的概念层簇也
可以聚集在一起，以形成分层结构中较高的
概念层。
2
0
2
2
/
5
/
9
61
具体方法是：
首先，将元组划分为群或簇，使得在每一个簇
中的对象“类似”，但与其他簇中的对象“不
类似”。
其次，为这些簇赋值，所有包含在同一个簇中
的对象的值相同。
注意：这种方法的有效性依赖于数据的性
质，数据必须能够组织成不同的聚类；另外，
它只适用于无监督的离散化。
2
0
2
2
/
5
/
9
62
2
0
2
2
/
5
/
9
例如：见IRIS样本集，在不考虑类别信息的情况下，
现用聚类方法离散化属性“sepal length in cm ”。有：
2
0
2
2
/
5
/
9
分组 频数 赋值
~ 46 1
~ 37 2
~ 32 3
~ 35 4
63
2
0
2
2
/
5
/
9
3、基于熵的离散化方法
信息熵的概念
• 信息论中的熵：是信息的度量单位，是一种 对属性“不确
定性的度量”。属性的不确定性越大，把它搞清楚所需要
的信息量也就越大，熵也就越大。
• Shannon公式：
其中，I(A)度量事件A发生所提供的信息量，称之为事件
A的自信息，P(A)为事件A发生的概率。
2
0
2
2
/
5
/
9
64
如果一个属性有N个可能的取值，且它们出
现的概率分别为 ，那么这个属性的信
息熵为：
一个系统越是有序，信息熵就越低。
2
0
2
2
/
5
/
9
65
贪心算法
所谓贪心算法是指，在对问题求解时，总
是做出在当前看来是最好的选择。也就是说，
不从整体最优上加以考虑，他所做出的仅是
在某种意义上的局部最优解。
2
0
2
2
/
5
/
9
66
例如：假设有四种硬币，它们的面值分别为二角五分、
一角、五分和一分。现在要找给某顾客六角三分钱。
这时，我们会不假思索地拿出2个二角五分的硬币，1个一
角的硬币和3个一分的硬币交给顾客。这种找硬币方法与
其他的找法相比，所拿出的硬币个数是最少的。
这里，我们下意识地使用了这样的找硬币算法：首先选出
一个面值不超过六角三分的最大硬币，即二角五分；然后
从六角三分中减去二角五分，剩下三角八分；再选出一个
面值不超过三角八分的最大硬币，即又一个二角五分，如
此一直做下去。
这个找硬币的方法实际上就是贪心算法。顾名思义，贪
心算法总是作出在当前看来是最好的选择。也就是说贪
心算法并不从整体最优上加以考虑，它所作出的选择只
是在某种意义上的局部最优选择。
2
0
2
2
/
5
/
9
67
但是：
如果硬币的面值改为一分、五分和一角一分3种，
而要找给顾客的是一角五分钱。还用贪心算法，
我们将找给顾客1个一角一分的硬币和4个一分的
硬币。然而3个五分的硬币显然是最好的找法。
显然贪心算法不是对所有问题都能得到整体最优
解，但对范围相当广的许多问题它能产生整体最
优解。如，图的单源最短路径问题。
在一些情况下，即使贪心算法不能得到整体最优
解，但其最终结果却是最优解的很好的近似解。
2
0
2
2
/
5
/
9
68
基于熵的离散化方法是通过贪心算法搜寻给定
数据区间内的具有熵值最小的数据点作为断点。
该方法将区间内的每一个数值作为候选断点，
计算其熵值，然后从中选出具有最小熵值的数
据点作为断点，将区间一分为二，然后再对得
到的区间递归地应用以上方法进行离散化。
停止准则是当得到的每个区间中的类标签都是
一致时，即停止离散化过程；或者达到某个停
止标准时，停止。
2
0
2
2
/
5
/
9
69
基于熵的离散化方法
2
0
2
2
/
5
/
9
基于熵的离散化方法
2
0
2
2
/
5
/
9
一个给定的
样本分类所
需要的信息
某种划分的期
望信息
70
项目 性别 年龄 学生身分 收入 办卡
1 男 >45 否 高 会
2 女 31~45 否 高 会
3 女 20~30 是 低 会
4 男 <20 是 低 不会
5 女 20~30 是 中 不会
6 女 20~30 否 中 会
7 女 31~45 否 高 会
8 男 31~45 是 中 不会
9 男 31~45 否 中 会
10 女 <20 是 低 会
2
0
2
2
/
5
/
9
Sepallen:(cm) d1 d2 d3 Sepallen:(cm) d1 d2 d3
1 0 0 0 4 2
3 0 0 0 2 2
1 0 0 0 3 6
4 0 0 0 2 5
2 0 0 0 1 4
5 0 0 0 2 0
4 1 1 0 3 5
5 8 2 0 0 1 2
8 1 0 0 1 3
3 1 0 7 0 1 0
1 0 0 0 0 1
5 1 0 0 0 3
2 5 0 0 0 1
0 5 1 0 0 1
2 5 1 0 0 1
1 3 3 0 0 4
0 2 1 0 0 1
6 0 4 2
2
0
2
2
/
5
/
9
举例：IRIS样本集的具体步骤
71
2
0
2
2
/
5
/
9
首先，从第一个分割点开始，将属性值分为两部分即
[,)和[,]，则分割后新的类别熵为：
2
0
2
2
/
5
/
9
区间 d1 d2 d3 合计
[,) 1 0 0 1
[,] 49 50 50 149
72
2
0
2
2
/
5
/
9
以此类推，如把属性值分为[,)和[,7,9]两个区
间时，产生的新的类别熵为：
2
0
2
2
/
5
/
9
区间 d1 d2 d3 合计
[,) 47 11 1 59
[,] 3 39 49 91
73
2
0
2
2
/
5
/
9
对所有的分割点将属性值分为两个区间的新类别熵计
算出来，有
2
0
2
2
/
5
/
9
d1 d2 d3 新的类别熵 d1 d2 d3 新的类别熵
1 0 0 6 0 4 2
3 0 0 0 4 2
1 0 0 0 2 2
4 0 0 0 3 6
2 0 0 0 2 5
5 0 0 0 1 4
4 1 1 0 2 0
5 8 2 0 0 3 5
8 1 0 0 1 2
3 1 0 0 1 3
1 0 0 7 0 1 0
5 1 0 0 0 1
2 5 0 0 0 3
0 5 1 0 0 1
2 5 1 0 0 1
1 3 3 0 0 1
0 2 1 0 0 4
0 0 1
74
2
0
2
2
/
5
/
9从上表中可以看到，将属性值分为[,)和
[,7,9]两个区间时，类别熵最小，因此首先把属
性值分为两大部分。
按照上述步骤， 分别再找出区间 [,)和
[,7,9]的二分点，以此类推，逐渐将区间分割为
更小的区间，直到满足某个终止条件为止。
2
0
2
2
/
5
/
9
75
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
d1 d2 d3 新的类别熵 d1 d2 d3 新的类别熵
1 0 0 6 0 4 2
3 0 0 0 4 2
1 0 0 0 2 2
4 0 0 0 3 6
2 0 0 0 2 5
5 0 0 0 1 4
4 1 1 0 2 0
5 8 2 0 0 3 5
8 1 0 0 1 2
3 1 0 0 1 3
1 0 0 7 0 1 0
5 1 0 0 0 1
2 5 0 0 0 3
0 5 1 0 0 1
2 5 1 0 0 1
1 3 3 0 0 1
0 2 1 0 0 4
0 0 1 76
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
4、CHIMERGE算法
77
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
78
Sepallen:(cm) d1 d2 d3 Sepallen:(cm) d1 d2 d3
1 0 0 0 4 2
3 0 0 0 2 2
1 0 0 0 3 6
4 0 0 0 2 5
2 0 0 0 1 4
5 0 0 0 2 0
4 1 1 0 3 5
5 8 2 0 0 1 2
8 1 0 0 1 3
3 1 0 7 0 1 0
1 0 0 0 0 1
5 1 0 0 0 3
2 5 0 0 0 1
0 5 1 0 0 1
2 5 1 0 0 1
1 3 3 0 0 4
0 2 1 0 0 1
6 0 4 2
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
79
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
80
2
0
2
2
/
5
/
9
应用
采用Iris样本集进行统计模拟。现在以花萼
长（ sepal length in cm ）属性为例，来进行
连续型值属性的离散化。
2
0
2
2
/
5
/
9
81
2
0
2
2
/
5
/
9
Sepallen:(cm) d1 d2 d3 Sepallen:(cm) d1 d2 d3
1 0 0 0 4 2
3 0 0 0 2 2
1 0 0 0 3 6
4 0 0 0 2 5
2 0 0 0 1 4
5 0 0 0 2 0
4 1 1 0 3 5
5 8 2 0 0 1 2
8 1 0 0 1 3
3 1 0 7 0 1 0
1 0 0 0 0 1
5 1 0 0 0 3
2 5 0 0 0 1
0 5 1 0 0 1
2 5 1 0 0 1
1 3 3 0 0 4
0 2 1 0 0 1
6 0 4 2
2
0
2
2
/
5
/
9
82
2
0
2
2
/
5
/
9
具体步骤：
（1）观察各区间，先将类分布完全相同的区间进行合并。
2
0
2
2
/
5
/
9
区间 d1 d2 d3 区间 d1 d2 d3
[,) 16 0 0 [,) 3 8 4
[,) 4 1 1 [,) 0 18 22
[,) 19 4 0 [,) 0 2 0
[,) 1 0 0 [,) 0 5 10
[,) 7 6 0 [,) 0 1 0
[,) 0 5 1 [,) 0 0 12
83
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
（2）考察[,)与[,5)，看其是否能够合并？
两区间的卡方统计量和为，大于临界值，因此两区间
不能合并。
区间 d1 d2 d3 求和
[,) 16 0 0 16
[,5) 4 1 1 6
求和 20 1 1 22
区间 eij eij eij
[,)
[,5)
区间 χ2
[,)
[,5)
表1：两区间的列联表 表2：计算各项的eij
表3：两区间的卡方统计量值
84
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
（3）继续考察区间[,5)与[,) ，看其是否
能够合并，直到所有的区间卡方统计量大于阀值
为止。
85
2
0
2
2
/
5
/
9
五、属性的归约
属性的归约包括两类方法：属性的提取和属性子集的
选择。
（一）属性的提取
属性的提取是通过映射（或变换）的方法，将高维的
属性空间压缩为低维的属性空间，即将原始属性变换
为较少的新属性。
此时，“较少的新属性”是原始属性的某种线性组合，
也可以称为“二次属性”。
2
0
2
2
/
5
/
9
86
2
0
2
2
/
5
/
9
属性提取的最大的优点在于：这样的线性组合比
属性选择中的最优子集有更好的判别能力。但相
应的问题是，这样的线性组合的实际意义却不明
显，有时难以解释。
到目前为止，对属性提取的研究主要是从线性和
非线性的数据变换角度进行的。
用的比较多的线性数据变换方法是：主成分分
析、因子分析、判别分析、聚类分析、多维标
度、投影寻踪以及小波变换等。
非线性的数据变换，主要是基于自组织映射的
属性抽取方法、基于核的主成分分析和基于核
的判别分析方法等。
2
0
2
2
/
5
/
9
87
2
0
2
2
/
5
/
9
1、主成分分析（因子分析）
主成分分析和因子分析都是多元统计分析中
的一种常用方法，是数学上处理降维的一种
方法。
主成分分析的基本思想：
• 设法将原始属性重新组合成一组新的互相无关的
几个综合属性，同时根据需要从中选取少数几个
综合属性来尽可能多地反映原来指标的信息。
• 综合指标的选取使用的是方差最大法。
2
0
2
2
/
5
/
9
88
2、因子分析
因子分析的基本思想：
通过变量（或样本）的相关系数矩阵内部
结构的研究，找出能控制所有变量的少数几
个因子去描述多个变量之间的相关关系；
然后，根据相关性的大小把变量分组，使
得同组内的变量之间相关性较高，但不同组
之间相关性较低。
2
0
2
2
/
5
/
9
89
2
0
2
2
/
5
/
9
主成分分析和因子分析的对比
数据标准化
建立指标之间的
相关系数矩阵R
求R的特征值和特
征向量
计算累计贡献率大
于85%的前n个特
征值的特征向量
根据特征向量建立
n个主成分（由变
量的线性组合而成）
2
0
2
2
/
5
/
9
根据n个
特征向量
建立因子
载荷阵
对因子载
荷阵实行
方差最大
旋转
按照变量在
每个因子上
载荷阵的高
低，分类。
主成分
分析
因子
分析
由因子的线
性组合来解
释变量
90
主成份分析和因子分析的优点
因子（主成份）之间的线性相关关系不显著。
主成份参与数据建模能够有效地解决变量多重共线
性等分析应用带来的问题。
因子能够反映原有变量的绝大部分信息。
因子的方差贡献和方差贡献率是衡量因子重要性的关
键指标。该值越高，说明相应因子的重要性越高。
aij因子载荷反映了某i个变量在第j因子上的相对重要
性。
因子得分是因子分析的最终体现。在后续的分析中可
以用因子变量代替原有变量进行建模，或者利用因子
变量对样本分类、评价或排序等研究。
2
0
2
2
/
5
/
9
91
3、聚类分析——K均值聚类分析
K均值法是麦奎因（MacQueen，1967）提出的，
这种算法的基本思想是将每一个样品分配给最近中
心（均值）的类中.
具体的算法至少包括以下三个步骤：
1．将所有的样品分成K个初始类；
2．通过欧氏距离将某个样品划入离中心最近的类
中，并对获得样品与失去样品的类，重新计算中心
坐标；
3．重复步骤2，直到所有的样品都不能再分配时为
止。
2
0
2
2
/
5
/
9
92
2
0
2
2
/
5
/
9
（二）属性子集的选择
属性子集的选择是通过删除不相关的属性来减少数据量。
属性子集选择的目标是找出最小属性集，使得数据类的概
率分布尽可能地接近使用所有属性的原分布。
2
0
2
2
/
5
/
9
93
2
0
2
2
/
5
/
9
属性子集的选择方法一般有两个组成部分：
一是高效率的属性子集搜索策略，即在允许的
时间内，用以找出最小的、最能描述类别的属
性组合的搜索方法；
二是确定评价函数，是衡量属性组合是否最优
的标准。
属性子集的选择一般分两步进行：
首先，产生属性子集；
然后，对子集进行评价，如果满足停止条件则
停止，否则重复前述两步直到条件满足为止。
2
0
2
2
/
5
/
9
94
通过该标准，要能够衡量哪组属性子集的分类效
果最好，即使得数据类的概率分布尽可能地接近使
用所有属性的原分布；
或者能够衡量哪组属性子集的分类效果最好，即
最能够代表全部的属性集合对样本的划分。
2
0
2
2
/
5
/
9
1、搜索策略
按照搜索属性形成属性子集的方式，搜索策略可
以分为：穷举法、启发式和随机搜索。
启发式搜索即贪心算法。
基本的启发式属性选择算法主要有：逐步向前选
择（SFS）、逐步向后选择（SBG ）以及向前选
择和向后删除相结合的方法等。
2
0
2
2
/
5
/
9
95
2
0
2
2
/
5
/
9
（1）逐步向前选择
逐步向前选择方法是一种自下而上的搜索方法，
它是由空属性集开始，依次从未入选的属性中选
择一个属性，使它与已入选的属性组合在一起时
所得的评价函数达到最大值（或最小值，依评价
函数选取的不同，取最大或最小值），直到评价
函数的值不再增加（或减小）时为止，亦或者达
到指定的属性数为止。
2
0
2
2
/
5
/
9
9696
能够衡量哪组属性子集的分类效果最好，
最能够代表全部的属性集合对样本的划
分。
这种算法的不足是：在算法中虽然考虑了所选属
性与已入选属性之间的相关性，但却未考虑未入
选属性之间的统计相关性，并且一旦某个属性已
入选，即使由于后加入的属性使它变为多余，也
无法再剔除。
2
0
2
2
/
5
/
9
97
2
0
2
2
/
5
/
9
（2）逐步向后删除
逐步向后删除是一种自上而下搜索的方法，它由
整个属性集开始，在每一步删除掉在属性集中最
坏的属性，评判属性好坏的准则是，如果剔除该
属性后，属性集的评价函数达到最大（或最小）
值，那么这个属性是最坏的。
2
0
2
2
/
5
/
9
9898
（3）逐步向前选择和逐步向后删除相结合
向前选择和向后删除结合的方法则是将向前选择
和向后删除方法结合在一起，每一步选择一个最
好的属性，并在其剩余的属性中删除掉一个最坏
的属性。
这两种方法也存在着与逐步向前选择方法相同的
缺点。
2
0
2
2
/
5
/
9
99
2
0
2
2
/
5
/
9
（4）广义逐步向前选择
广义逐步向前选择方法是逐步向前选择方法的推广，
针对逐步向前选择方法“未能考虑未入选属性之间的
统计相关性”的缺点，该方法每次从未入选的属性中
挑选的不止是一个属性而是多个属性。
广义逐步向前选择方法的缺点是：计算量要比逐步向
前选择方法大很多，并且也未解决“一旦某个属性已
入选，即使由于后加入的属性使它变为多余，也无法
再剔除”的问题。
2
0
2
2
/
5
/
9
100100
2
0
2
2
/
5
/
9
2、属性子集选择中的评价函数
在属性子集选择中，找出最具代表性的属性子集需要
一个子集优劣的评价标准。通过该标准，使得数据类
的概率分布尽可能地接近使用所有属性的原分布；如
果没有类属性，则能够衡量哪组属性子集的分类效果
最好，最能够代表全部的属性集合对样本的划分。
这种评价标准以函数的形式表示出来就是评价函数。
它在模式识别中，也被称为类别可分性判据。
2
0
2
2
/
5
/
9
101
2
0
2
2
/
5
/
9
评价函数在属性子集的选择中是非常关键的，不同
的评价函数可能会得出不同的结果。评价函数的建
立形式是多种多样的：
基于距离的评价函数、基于相关性的评价函数（无
监督属性子集的选择方法）。
基于一致性的评价函数、分类错误率以及基于信息
熵的评价函数等(有监督属性子集选择方法)。
2
0
2
2
/
5
/
9
102
3、评价函数的要求
2
0
2
2
/
5
/
9
103
2
0
2
2
/
5
/
9
4、模式识别中基于距离的评价函数
2
0
2
2
/
5
/
9
104
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
105
2
0
2
2
/
5
/
9
属性子集选择方法的应用
主要思路：通过因子分析和相关分析为逐步向前选择
算法找到每一次选用子集的最优属性。
选用2004年各地区城镇居民家庭人均全年消费性支出
样本集对逐步向前的属性子集选择方法进行模拟。
具体步骤如下：
首先，对这个样本集作KMO (Kaiser-Meyer-Olkin)检验，
KMO值为，表明该数据集适合作因子分析。
KMO值是用于比较变量间简单相关系数和偏相关系数
的指标。KMO值在以上表式非常适合作因子分析，
在～之间表示适合，在～表示一般，在
～之间表示不太适合，以下表示极不适合。
2
0
2
2
/
5
/
9
106
2
0
2
2
/
5
/
9
107
2
0
2
2
/
5
/
9
108
因子初始解
第二列说明提
取公因子后，
变量可以被因
子解释的信息
有多少
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
109
对样本集进行因
子分析，因子分
析中前2个因子
的贡献率分别是
%和
%，累计
贡献率为
%。
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
110
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
111
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
112
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
113
2
0
2
2
/
5
/
9
2
0
2
2
/
5
/
9
114
