数据约简包括样例约简和属性约简, 是从不同角度对数据进行约简. 《数据约简——样例约简与属性约简》在分类的框架下介绍数据约简的方法, 重点介绍了确定性与不确定性环境下的样例约简方法和属性约简方法. 样例约简方法包括交叉选择样例算法、压缩模糊K近邻规则方法、概率神经网络样例选择算法. 属性约简方法包括最小相关性最大依赖度属性约简方法、模糊属性约简方法及属性约简方法在模型选择中的应用. 另外, 《数据约简——样例约简与属性约简》还介绍了样例选择准则和特征子集评价准则. 《数据约简——样例约简与属性约简》以监督学习的基本理论为基础, 全面系统地讨论了数据约简中的主要问题.

第1章预备知识
本章介绍后续章节将要用到的基础知识，包括分类与回归的概念、随机变量不确定性度量、模糊集、样例约简和属性约简的形式化定义。
1.1分类问题与回归问题
下面通过一个例子介绍什么是分类问题[1]，并在此基础上给出回归问题的定义.因为本书在分类的框架下讨论问题，所以本节重点介绍分类问题。
例1.1.1疾病诊断问题设某疾病的诊断要化验d个指标。这些指标也称为属性或特征，表1:1给出了n个患者的化验结果及医生的最终诊断结果。其中，要么等于1，要么等于1，表示患有这种疾病，yi=1表示没有患这种疾病.我们希望根据这些数据，对新来的病人只检测这d个指标，就可以推断该病人是否患有这种疾病，这类问题就称为分类问题。
如表1:1所示的数据集称为分类数据集，也称为决策表，可以用以下两种形式抽象地表示。
1)用二元组表示
表1:1所示的分类数据集，可用二元组(xi，yi)抽象地表示成如下形式，即
其中，xi表示第i个样例，yi表示样例xi所对应的类别标号
2)用四元组表示
表1:1所示的分类数据集，也可以抽象地表示为四元组，即
其中，是n个样例的集合，是描述对象(或样例)的条件属性(或特征)集合，是决策属性(或类别属性)集合，V是d个属性值域的笛卡儿积，是属性ai的值域是信息函数：
用式(1.2)表示的四元组也称为决策表，为了描述方便，本书中这两种等价表示会交替使用.
表1:1所述的分类问题是一个二类分类问题，对于多类问题，y的取值范围不再是，而是由多个离散值构成的集合，如对于手写数字识别问题，y的取值范围是，当然也可以用其他符号来表示，如。下面针对多类分类问题，从数学的角度给出分类的定义。
定义1.1.1给定分类数据集，如果存在一个映射使得对于任意的都有成立.根据给定的分类
数据集D寻找函数y=f(x)的问题，称为分类问题.函数y=f(x)也称为分类函数.
说明:
①在分类问题中，因变量y的取值范围是一个由有限个离散值构成的集合C，它相当于高级程序设计语言(如C++语言)中的枚举类型.若C变为实数集R或R中的一个区间[a，b]，则这类问题称为回归问题.显然，分类问题是回归问题的特殊情况。
②函数y=f(x)不一定有解析表达式，可以用其他的形式，如树、图或网络来表示。
③如果所有的Vi都是实数集R，此时V=Rd。
下面举几个分类问题的例子。
例1.1.2天气分类问题天气分类问题[3]是一个两类分类问题，用来预测什么样的天气条件适宜打网球.天气数据集是机器学习领域中的一个经典数据集，是包含14个样例的一个小数据集，如表1.2所示.
天气分类问题数据集有14个样例，即，4个条件属性，即A=fa1，a2，a3，a4g，其中， a1=Outlook， a2=Temperature，a3=Humidity，a4=Wind，它们都是离散值属性，相当于高级程序设计语言中 的枚举类型属性，V1=fSunny，Cloudy，Raing，V2=fHot，Mild，Coolg，V3=fHigh，Normalg， V4=fStrong，Weakg.决策属性集合由单决策属性构成，即C=fyg，y=PlayTennis，它只取Yes和No两个值，所以天气分类问题是一个两类分类问题.显然，从该数据集中找到的分类函y=f(x)不可能有解析表达式.在第3章，我们将会看到y=f(x)可用一棵树来表示。
例1.1.3鸢尾花分类问题鸢尾花分类问题是一个三类分类问题，它根据花萼长(Sepallength)、花萼宽(Sepalwidth)、花瓣长(Petallength)和花瓣宽(Petalwidth)四个条件属性对鸢尾花进行分类.鸢尾花数据集包含三类150个样。
例，每类50个样例，如表1.3所示.Iris数据集有150个样例，即4个条件属性，即其中， 它们都是连续值属性.V=V1￡V2￡V3￡V4，V1=V2=V3=V4=R，即V=R4.决策属性集合由单决策属性构成，即由于Iris数据集中四个条件属性都是连续值属性，所以该数据集是一个连续值数据集。
例1.1.4助教评估分类问题助教评估分类问题也是一个三类分类问题，
它根据母语是否是英语(AnativeEnglishspeaker)、课程讲师(Courseinstructor)、课程(Course)、是否正常学期(Aregularsemester)和班级规模(Classsize)五个条件属性对助教评估分类.助教评估分类数据集包含三类151个样例，第一类49个样例，第二类(Medium)50个样例，第三类(High)52个样例，如表1:4所示。
TAE数据集有151个样例，即5个条件属性，其中，a1表示母语是否是英语，是一个二值属性，a2表示课程讲师，共25个课程讲师，每个课程讲师用一个符号值表示，共25个值，a3表示助教课程，共26门课程，每门课程用一个符号值表示，共26个值，a4表示是否正常学期，是一个二值属性，a5表示班级规模，是一个数值属性.显然，TAE数据集是一个混合类型数据集。
1.2不确定性度量
不确定性在机器学习中是一种常见的现象，存在于学习过程的各个环节，如数据预处理(包括特征选择和样例选择)、算法设计、模型选择等，它对学习系统的性能有重要的影响.常见不确定性包括随机性、模糊性和粗糙性.随机性[5]是客观存在的一种不确定性.模糊性是人类在认识客观实际的过程中，由于无法给出清晰准确的界限而产生的一种不确定性，是一种认知不确定性.粗糙性是由于人类掌握的知识不充分而产生的一种不确定性，是一种知识不确定性.本节介绍前两种不确定性的度量，粗糙性度量在第2章详细介绍。
1.2.1随机变量的不确定性度量
熵是随机变量不确定性的度量，下面分两种情况给出熵的定义，并讨论其性质。
1.离散型随机变量不确定性度量
1)熵
设X是离散型随机变量，它所有可能取值的集合为X，对于任意的x2X，令PrfX=xg=p(x)，X服从的概率分布为p(x)，记为，下面给出熵的定义。
定义1.2.1离散型随机变量X的熵定义为
说明:
①熵的单位为bit，当公式(1.3)中的对数变成以e为底的对数，即自然对数
时，熵的单位为net。
②随机变量X的熵表示它取值的混乱程度，即不确定性程度。
③随机变量X的熵也可以写成H(p)。
④熵是随机变量X的分布函数，不依赖于X的具体取值，而依赖于取值的概率.
设E是期望算子，如果X？p(x)，则随机变量X的函数g(X)的期望值为p(X)，则X的熵有如下定义形式，即
因为，所以
从而有
例1.2.1设，且Pr(X=1)=p，求随机变量X的熵.
因为X服从0-1分布，所以Pr(X=0)=1？p.根据式(1.3)，随机变量X的熵为
从式(1.6)可以看出，随机变量X的熵是p的函数H(p).当时，熵的值最大，等于1.H(p)的图形如图1.1

目录
《信息科学技术学术著作丛书》序
前言
第1章预备知识1
1.1分类问题与回归问题1
1.2不确定性度量5
1.2.1随机变量的不确定性度量5
1.2.2认知的模糊性度量13
1.3数据约简17
参考文献20
第2章粗糙集及其扩展模型24
2.1经典粗糙集模型25
2.1.1上近似和下近似25
2.1.2粗糙集模型的特征31
2.1.3属性约简与核50
2.1.4属性约简算法51
2.2变精度粗糙集模型56
2.3相容粗糙集模型62
2.4粗糙模糊集模型65
2.5模糊粗糙集模型80
参考文献87
第3章求解分类问题的方法90
3.1决策树90
3.1.1离散值决策树归纳算法90
3.1.2连续值决策树归纳算法100
3.2模糊决策树111
3.2.1模糊ID3算法111
3.2.2基于模糊粗糙集技术的模糊决策树算法120
3.3支持向量机127
3.3.1线性可分问题的支持向量机127
3.3.2近似线性可分问题的支持向量机131
3.3.3线性不可分问题的支持向量机132
3.4极限学习机135
3.5概率神经网络137
参考文献140
第4章样例约简143
4.1样例选择准则143
4.1.1样例选择的不确定性准则.143
4.1.2样例选择的期望误差减少准则144
4.1.3一致性准则145
4.2交叉选择样例算法147
4.2.1算法的基本思想148
4.2.2交叉选择样例算法150
4.2.3实验结果及分析151
4.3基于模糊粗糙集技术的压缩模糊K近邻规则163
4.3.1基础知识163
4.3.2压缩模糊K近邻规则165
4.3.3实验结果及分析169
4.4概率神经网络样例选择算法178
参考文献184
第5章属性约简186
5.1特征提取186
5.1.1主成分分析186
5.1.2线性判别分析189
5.2特征子集评价准则193
5.2.1类别可分离性准则193
5.2.2不一致性准则194
5.3最小相关性最大依赖度属性约简198
5.3.1算法的基本思想199
5.3.2最小相关性最大依赖度属性约简算法201
5.3.3实验结果201
5.4模糊属性约简方法203
5.4.1相关工作203
5.4.2模糊属性约简方法205
5.4.3实验结果及分析213
5.5极限学习机网络结构选择214
5.5.1模型选择准则215
5.5.2基于结点敏感性的模型选择217
5.5.3实验结果及分析219
参考文献2