第3章 数据预处理

第三章数据预处理

4.1预处理的必要性

目前，数据挖掘的研究工作大都集中在算法的探讨而忽视对数据处理的研究。事实上，数据预处理对数据挖掘十分重要，一些成熟的算法对其处理的数据集合都有一定的要求：比如数据的完整性好，冗余性小，属性的相关性小等。数据预处理是数据挖掘的重要一环，而且必不可少。要使挖掘算法挖掘出有效的知识，必须为其提供干净，准确，简洁的数据。然而，实际应用系统中收集的数据通常是“脏”数据

1、杂乱性

如性别：

A数据库male=1,female=2B数据库

male=‘男’，female=‘女’

C数据库

male=‘M’,female=‘F’2、重复性

同一客观事物在数据库中存在两个以上的物理描述假设某周刊有100000个订户，邮件列表中0.1%的记录是重复的，主要是一个名字有不同的写法

JonDoe和JohnDoe

因此，每周需要印刷和邮寄100份额外的刊物，假设每周的邮寄和印刷费用是两圆，公司每年将浪费10000元以上3、不完整性

由于实际系统设计时存在的缺陷以及使用过程中的一些人为因素，数据记录可能会出现数据值的丢失或不确定，原因可能有：（1）有些属性的内容有时没有（家庭收入，参与销售事物数据中的顾客信息）（2）有些数据当时被认为是不必要的（3）由于误解或检测设备失灵导致相关数据没有记录下来（4）与其它记录内容不一致而被删除（5）忽略了历史数据或对数据的修改4、噪声数据

数据中存在着错误或异常（偏离期望值），血压和身高为0就是明显的错误，当数据缺失且用默认值来填充缺失项时，很容易发生这类错误。（1）数据采集设备有问题（2）数据录入过程中发生了人为或计算机错误（3）传输过程中发生错误4.2数据预处理的功能

数据清理（清洗）

------填写空缺的值，平滑噪声数据，识别、删除孤立点，解决不一致性

数据集成

-----将多个数据源合并成一致的数据存储，构成一个完整的数据集，如数据仓库或数据立方体

数据变换（转换）---将一种格式的数据转换为另一格式的数据(如规范化)

数据归约（消减）----可以通过聚集、删除冗余特性或聚类等方法来压缩数据

这里需要指出的是：上述的各种数据预处理方法，并不是相互独立的，而是相互关联的，如消除数据冗余既可以看成是一种形式的数据清洗，也可以看成是一种数据消减。4.3数据清理（清洗）数据清理完成:

填充空缺的值识别孤立点消除噪声纠正数据中的不一致

数据清理可以分为有监督和无监督两类

有监督过程是在领域专家指导下，分析收集的数据，去除明显错误的噪声数据和重复记录，填补缺省数据；

无监督过程是用样本数据训练算法，使其获得一定的经验，并在以后的处理过程中自动采用这些经验完成数据清洗工作。一、遗漏数据的处理

(1)忽略该元组

(2)人工填写空缺值

(3)使用一个全局常量填充空缺值

(4)使用属性的平均值填充空缺值

(5)利用同类别均值填补遗漏数据

(6)使用最可能的值填充空缺值

二、噪声数据

噪声(noise)是一个测量变量中的随机错误或偏差。给定一个数值属性，例如price，我们怎样才能平滑数据，去掉噪声?

(1)分箱(binning)

分箱方法通过考察“邻居”(即周围的值)来平滑存储数据的值。存储的值被分布到一些“桶”或箱中。由于分箱方法参考相邻的值，因此它进行局部平滑。分箱(binning):首先排序数据，并将他们分到箱子中然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等分箱方法统一权重，也称等深分箱法，按记录行数分箱，每箱具有相同的记录数统一区间，也称等宽分箱法，按区间范围平均分布各箱最小熵，使在各区间分组内的记录具有最小的熵，数据集的熵越低说明数据之间的差异最小用户自定义区间，用户根据实际需要自定义区间

在该例中，price数据首先被划分并存人等深的箱中(深度3)。对于按箱平均值平滑，箱中每一个值被箱中的平均值替换。例如，箱1中的值4，8和15的平均值是9；这样，该箱中的每一个值被替换为9。类似地，可以使用按箱中值平滑。此时，箱中的每一个值被箱中的中值替换。对于按箱边界平滑，箱中的最大和最小值被视为箱边界。箱中的每一个值被最近的边界值替换。分箱例子Income排序后的值为：800，1000，1200，1500，1500，1800，2000，2300，2500，2800，3000，3500，4000，4500，4800，5000

对此记录进行分箱平滑噪声统一权重（深度为4）：箱1：800100012001500

箱2：1500180020002300

箱3：2500280030003500

箱4：4000450048005000统一区间，设定区间范围为1000箱1：800，1000，1200，1500，1500，1800箱2：2000，2300，2500，2800，3000箱3：3500，4000，4500箱4：4800，5000再采用各种平滑方法进行噪声平滑，结果为？用户自定义，将客户收入划分为1000以下、1000-2000，2000-3000，3000-4000和4000以上箱1：800

箱2：1000，1200，1500，1500，1800，2000

箱3：2300，2500，2800，3000

箱4：3500，4000

箱5：4500，4800，5000

(2)聚类(clustering)

通过聚类分析可以检测孤立点，聚类将类似的值组织成群或“聚类”。直观地看，落在聚类集合之外的值被视为孤立点(3)计算机和人工检查结合

可以通过计算机和人工检查结合的办法来识别孤立点。

(4)回归(regression)

可以利用拟合函数(如回归函数)来平滑数据。

如线性回归涉及找出适合两个变量的“最佳”直线，使得一个变量能够预测另一个。使用回归，找出适合数据的数学方程式，能够帮助消除噪声。Regressionxyy=x+1X1Y1Y1’

许多数据平滑的方法也是涉及离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。概念分层是一种数据离散化形式，也可以用于数据平滑。例如，price的概念分层可以把price的值映射到inexpensive，moderately_priced和expensive，从而减少了挖掘过程所处理的值的数量。

4.4

数据集成和变换一、数据集成

它需要统一原始数据中的所有矛盾之处，如字段的:

同名异义、异名同义、单位不统一字长不一致，从而把原始数据在最低层上加以转换，提炼和集成。

1、模式集成

数据分析者或计算机如何才能确信一个数据库中的customer_id和另一个数据库中的cust_number指的是同一实体？通常，数据库和数据仓库有元数据——关于数据的数据。这种元数据可以帮助避免模式集成中的错误。2、冗余问题一个属性是冗余的，如果它能由另一个表“导出”，如年薪属性；命名的不一致也可能导致数据集中的冗余有些冗余可以被相关分析检测到。例如，给定两个属性，根据可用的数据，这种分析可以度量一个属性能在多大程度上蕴含另一个。属性A和B之间的相关性可用下式度量：其中，n是元组个数，分别是A和B的平均值，分别是A和B的标准差。

如果(3.1)式的值大于0，则A和B是正相关的，意味A的值随B的值增加而增加。该值越大，一个属性蕴涵另一个的可能性越大。因此，一个很大的值表明A(或B)可以作为冗余而被去掉。如果结果等于0，则A和B是独立的，它们之间不相关。如果结果值小于0，则A和B是负相关的，一个值随另一个减少而增加。

(3．1)式可以用来检测上面的的customer_id和cust_number的相关性。3、数据值冲突的检测与处理

表示不同导致数据冲突

语义不同导致数据冲突不同文化

旅馆价格等

对于现实世界的同一实体，来自不同数据源的属性值可能不同。这可能是因为表示、比例或编码不同。例如，重量属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放。不同旅馆的价格不仅可能涉及不同的货币，而且可能涉及不同的服务(如免费早餐)和税。数据这种语义上的异种性，是数据集成的巨大挑战。

仔细将多个数据源中的数据集成起来，能够减少或避免结果数据集中数据的冗余和不一致性。这有助于提高其后挖掘的精度和速度。另外，在数据集成中还应考虑数据类型的选择问题，如在值域范围内应尽量用tinyint代替int,可大大减少字节数，对于大规模数据集来说将会大大减少系统开销。二、数据变换-----数据变换将数据转换成适合于挖掘的形式。主要是找到数据的特征表示，对数据进行规格化处理。用维变换或转换方式减少有效变量的数目或找到数据的不变式

（1）平滑(smoothing)

去掉数据中的噪声。这种技术包括分箱（Bin)、聚类和回归。

（2）聚集对数据进行汇总和聚集例如，可以聚集日销售数据，计算月和年销售额。这一步用来为多粒度数据分析构造数据立方体。

(3)数据概化使用概念分层，用高层次概念替换低层次“原始”数据。例如，分类的属性，如street，可以概化为较高层的概念，如city或country。类似地，数值属性，如age映射到较高层概念，如young，middle-age和senior。

(4)规范化(规格化）

将属性数据按比例缩放，使之落入一个小的特定区间，如-1．0到1．0或0.0到1.0。如学生成绩GINT（G/10）规格化的目的是将一个属性取值范围影射到一个特定范围之内，以消除数值性属性因大小不一而造成挖掘结果的偏差

在正式进行数据挖掘之前，尤其是使用基于对象距离的挖掘算法时，必须进行数据的规格化。如对于一个顾客信息数据库中年龄属性或工资属性，由于工资属性的取值比年龄属性的取值要大得多，若不进行规格化处理，基于工资属性的距离计算值将远远超过基于年龄属性的计算值，这就意味着工资属性的作用在整个数据对象的距离计算中被错误放大了①最小-最大规范化对原始数据进行线性变换。假定minA，和maxA分别为属性A的最小和最大值。最小—最大规范化通过计算(3.2)将属性A的一个值v影射到v’[new_minA,new-maxA]

EX1假定属性income最小与最大值分别为$12000和$98000。我们想映射income到区间[0，1]。根据最小-最大规范化，income值$73000将变换为②Z-score规范化（或零-均值规范化）该方法是根据属性A的平均值和标准差规范化。A的值v被规范化为v’，由下式计算：(3.3)EX2假定属性income的平均值和标准差分别为$54000和$16000。使用z-score规范化，值$73600被转化为

③小数定标规范化(十基数变换）通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。

A的值v被规范化为，由下式计算

其中，j是使max(|v’|<1)成立最小整数。

EX3假定A的值由-986到917。

A的最大绝对值为986。为使用小数定标规范化，我们用1000（即j=3）除每一值。这样，-986被规范化为-0.986。注意，规范化将原来的数据改变很多，特别是上述的后两种方法。有必要保留规范化参数（如平均值和标准差，如果使用z-score规范化），以便将来的数据可以用一致的方式规范化。

（5）属性构造(或特征构造)

可以利用已知的属性构造新的属性并添加到属性集中，以帮助挖掘过程。（由长，宽求面积）4.5数据规约（消减）

数据立方合计维数削减数据压缩数据块消减离散化与概念层次生成

1、数据立方体合计主要用于构造数据立方---建立数据仓库如对某公司三年销售合计处理，可用一个三维数据立方体（时间，商品，部门）表示，它从三个角度描述相应时空的销售额。每个属性都可对应一个概念层次树，以帮助进行多抽象层次的数据分析。2、维归约

----主要用于检测并删除不相关、弱相关或冗余的属性维。用于数据分析的数据可能包含数以百计的属性，其中大部分属性与挖掘任务不相关，是冗余的。例如，如果分析任务是按顾客听到广告后，是否愿意在A11E1ectronics买流行的新款CD将顾客分类，与属性age，music_tasfe不同，诸如顾客的电话号码等属性多半是不相关的。

属性子集选择的目标是找出最小属性子集，使得数据类的概率分布尽可能地接近原分布。

“如何找出原属性的一个‘好的’子集?”d个属性有2d个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当d和数据类的数目增加时。

因此，对于属性子集选择，通常使用压缩搜索空间的启发式算法。它们的策略是做局部最优选择，期望由此导致全局最优解。

(1)逐步向前选择(逐步添加方法）：该过程由空属性集开始，选择原属性集中最好的属性，并将它添加到该集合中。在其后的每一次迭代，将原属性集剩下的属性中的最好的属性添加到该集合中。如遗传算法遗传算法是一种基于生物进化论和分子遗传学的全局随机搜索算法。

(2)逐步向后删除(逐步消减方法）：该过程由整个属性集开始。在每一步，删除掉在属性集中的最坏属性。直到无法选择出最坏属性或满足一定的阈值为止。

如粗集理论不需要先验知识；算法简单，易于操作，可有效地去除冗余属性，对于每个属性值域出现的冗余现象，也可用粗集理论删除，从而使条件属性的个数和取值得到化减。其基本思路是：利用定义的数据集合U上的等价关系对U进行划分，对于数据表来说，这种等价关系可以是某个属性，或者是几个属性的集合。因此，按照不同属性的组合就把数据表划分成不同的基本类，在这些基本类的基础上进一步求得最小约简集。(3)向前选择和向后删除的结合：向前选择和向后删除方法可以结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。

(4)判定树归纳

判定树算法，如ID3和C4．5最初是用于分类的,也可用于构造属性子集利用决策树的归纳方法对初始数据进行分类归纳学习，获得一个初始决策树，所有没出现在这个树上的属性均认为是无关属性，删除无关属性之后，就可获得一个较优的属性子集。3、数据压缩数据压缩使用数据编码或数据转换机制压缩数据集。若根据压缩后的数据集可以恢复原来的数据集-----无损（loseless)若根据压缩后的数据集不能恢复原来的数据集-----有损(lossy)常用的有小波变换和主要素分析

离散小波变换是一种线形信号处理技术，可将一个向量D转换为D’（为小波相关系数）为提高数据运算处理的效率，可以保留用户指定阈值的小波系数，而将其他小波系数置0。小波变换可以保留数据的主要特征情况下除去数据中的噪声。应用小波变换进行数据转换时，通常采用通用层次算法：(1)L为所输入数据向量的长度，它必须是2的幂(2)每次转换使用两个函数，第一个负责初步平滑，第二个完成带权差值计算以获得数据的主要特征。(3)将数据向量一分为二，应用(2)中的两个函数分别处理低频、高频数据(4)对所输入的向量循环使用(3)中的处理步骤，直到所有划分的子数据向量的长度均为2为止(5)取出(3),(4)步骤处理结果便获得被转换数据向量的小波相关系数。4、数据块消减------利用更简单的数据表达形式

参数与非参数两种方法参数方法是通过模型计算获得原来的数据，只要存储模型的参数即可非参数方法是指存储利用直方图、聚类或采样而获得的消减后的数据直方图（等宽，等高）采样（随机，聚类，分类）5离散化和概念分层生成

离散化技术通过将属性域划分为区间来减少给定连续属性值的个数。区间的标号可以替代实际的数据值。概念层次树可以通过利用较高层次概念替换较低层次概念而减少原来的数据。

对于用户或领域专家，人工地定义概念分层可能是一项令人乏味、耗时的任务。幸而，许多分层蕴涵在数据库模式中，并且可以在模式定义级定义。概念分层常常自动地产生，或根据数据分布的统计分析动态地加以提炼。

数值数据的离散化和概念分层生成数值属性的概念分层可以根据数据分布分析自动地构造。分箱

通过将数据分布到箱中，并用箱中的平均值或中值替换箱中的每个值，可以将属性值离散化。就像用箱的平均值平滑或用箱的中值平滑一样。这些技术可以递归地作用于结果划分，产生概念分层。

直方图分析

直方图也可以用于离散化.下面给出了一个直方图，显示某给定数据集price属性的数据分布。例如，频率最高的价格大约在$300—$325。可以使用划分规则定义值的范围。例如，在等宽直方图中，将值划分成相等的部分或区间(如($0…S100)，($100…$200)，…，($900…S1000)。在等深直方图中，值被划分使得每一部分包括相同个数的样本。

聚类算法可以用来将数据划分成簇或群。每一个簇形成概念分层的一个节点，而所有的节点在同一概念层。每一个簇可以进一步分成若干子簇，形成较低的概念层。簇也可以聚集在一起，以形成分层结构中较高的概念层。

基于熵的离散化

熵(entropy)，可以用来递归地划分数值属性A的值，产生分层的离散化,形成属性的数值概念分层。给定一个数据元组的集合S，基于熵对A离散化的方法如下：

1)A的每个值可以认为是一个潜在的区间边界或阈值T。例如，A的值v可以将样本划分成分别满足条件A<T和A>T的两个子集,这样就创建了一个二元离散化。2)给定S，所选择的阈值是这样的值，它使其后划分得到的信息增益最大。信息增益(informationgain)是

其中，S1，S2分别对应于S中满足条件A<T和A>T的样本。对它的熵函数Ent根据集合中样本的类分布来计算。例如，给定m个类Ci，它的熵是其中，pi是任意样本属于Ci

的概率，并用si/S估计3)确定阈值的过程递归地用于所得到的每一个划分，直到满足某个终止条件，如

基于熵的离散化可以压缩数据量。与迄今为止提到的其他方法不同，基于熵的离散化使用类信息，有助于提高分类的准确性。这里介绍的信息增益和熵也用于判定树归纳。

分类数据的概念分层生成分类数据(categoricaldata)是离散数据。一个分类属性具有有限个(但可能很多)不同值，值之间无序。如地理位置、工作分类和商品类型。

由用户或专家在模式级显式地说明属性的部分序：通常，分类属性或维的概念分层涉及一组属性。用户或专家在模式级通过说明属性的部分序或全序，可以很容易地定义概念分层。例如，关系数据库或数据仓库的维location可能包含如下一组属性：street，city，province_or_state，和country。可以在模式级说明一个全序，如street<city<province_or_state<country，来定义分层结构。

通过数据聚合来描述层次树例如，在模式级说明了province和country形成一个分层后，可能想人工地添加某些中间层。如显式地定义“安徽，江苏，山东”华东地区

说明属性集，但不说明它们的序

用户可以简单将一组属性组织在一起，以便构成一个层次树，这就需要自动地产生属性的序，以便构造有意义的概念分层。一个较高层的概念通常包含若干从属的较低层概念，定义在高概念层的属性与定义在较低概念层的属性相比，通常包含较少数目的不同值

根据这一事实，可以根据给定属性集中每个属性不同值的个数，自动地产生概念分层。

具有最多不同值的属性放在分层结构的最低层。一个属性的不同值个数越少，它在所产生的概念分层结构中所处的层越高。

例4假定用户对于A11E1ectronics的维location选定了属性集：street，country，province_or_state和city、但没有指出属性之间的层次序。

location的概念分层可以按如下步骤自动地产生。

首先，根据每个属性的不同值个数，将属性按降序排列。其结果如下(每个属性的不同值数目在括号中)：country(15)，province_or_state(365)，city(3567)，street(674339)。其次，按照排好的次序，自顶向下产生分层，第一个属性在最顶层，最后一个属性在最底层。

最后，用户可以考察所产生的分层，如果必要的话，修改它，以反映期望属性应满足的联系

注意，不能把启发式规则推向极端，因为显然有些情况并不遵循该规则。例如，在一个数据库中，时间维可能包含20个不同的年，12个不同的月，每星期7个不同的天。然而，这并不意味时间分层应当是:“year<month<days_of_the_week”,days_of_the_week在分层结构的最顶层。基于属性的分类方法简介

基于属性的分类算法可以看成是一种面向元组的归纳方法。该算法以数据库中关系表为基础，在原始数据增加的情况下，可以通过化简来压缩数据规模，使之只与属性值有关系，而与原始的数据量无关。而现在的数据存放中，几乎所有的数据都是用关系表的形式存放的，这为基于属性分类的数据挖掘方法提供了极大的方便，并可方便得到发现属性间的联系形成决策规则或产生式规则。基于属性分类的方法可分三步数据预处理在基于属性分类的挖掘方法中，整理缩减过程主要是离散化和剔除重复项。离散化就是将一些连续的值按区间变成离散的值。例如：对销售数量来说就可以将其离散化，用１表示〔１，１０〕的销售量。这样之后整个表就是用离散的数据表示，它可以去掉一些相同的数据；剔除重复项，就是合并相同的元组，减小数据量，便于分析使用。如:对下表年龄离散化(19,21)—1(22-24)—2(25-27)---3姓名性别年龄籍贯系别状况元组数赵民男25无锡计算机硕士生1钱文男23青岛计算机硕士生1孙辉男19北京管理新生1李小红女26淄博化工学院博士生1周倩倩女21山西外语三年级1吴青海男23南通计算机硕士生1郑力女27淄博化工学院博士生1王岚女20仓洲社科二年级1刘敏女22保定外语三年级1姓名性别年龄籍贯系别状况元组数赵民男3无锡计算机硕士生1钱文男2青岛计算机硕士生1孙辉男1北京管理新生1李小红女3淄博化工学院博士生1周倩倩女1山西外语三年级1吴青海男2青岛计算机硕士生1郑力女3淄博化工学院博士生1王岚女1仓洲社科二年级1刘敏女2保定外语三年级1年龄籍贯系别状况元组数3无锡计算机硕士生12青岛计算机硕士生11北京管理新生13淄博化工学院博士生11山西外语三年级12青岛计算机硕士生13淄博化工学院博士生11仓洲社科二年级12保定外语三年级1年龄籍贯系别状况元组数3无锡计算机硕士生12青岛计算机硕士生21北京管理新生13淄博化工学院博士生21山西外语三年级11仓洲社科二年级12保定外语三年级1宏经过数据预处理后形成的基表（知识模板）还要进行统计运算，最简单的统计属性就是相同元组的数目（VOTE），或者是占总元组数的百分比，也可以是置信度。从而形成宏元组（MacroTuples）,也称为知识宏。宏元组是知识模板中的最小单位，已经不是数据库传统意义上的元组了。最重要的区别是宏元组已经没有所谓的KeyDomain(键域)，而且增加了统计属性域。它们实际上代表各种生知识碎片，不妨称之为宏。它已经不反映信息的最小粒度了。

初步形成的知识模板的结构可反映出隐含的知识量和发现知识的复杂程度。用知识熵E和发现难度C来度量隐含的知识量和发现知识的复杂程度。定义1：设知识模板D含有n个宏，其中第K个宏覆盖的元组数为Vk,则整个知识模板覆盖的总元组数为：

N=

又设从该模板中可能得到的知识（规则）条数为M，支持第i条规则的宏元组数为Mi，其中第Mi个宏覆盖的元组数为Mij，则第i条规则覆盖的元组数为：Ni=

定义模板D对应的知识熵为：

E=

定义2：设知识模板D含有t

个属性（A1，A2，…Ai…..At）,其中，第j个属性Aj有W个取值{aj1,aj2,….ajw},

若按照Aj值来划分知识模板D，可得到W个知识子模板{Dj1,Dj2,….Djw，其中，DjP

含有Nj

p

个宏，这些宏在Aj这个属性中具有相同的ajp

值。如果子模板DjP

的知识熵为EjP

，则对于属性Aj来说，知识熵为：

Ej=

年龄籍贯系别状况元组数3无锡计算机硕士生12青岛计算机硕士生21北京管理新生13淄博化工学院博士生21山西外语三年级11仓洲社科二年级12保定外语三年级1宏因此，由Aj引起的知识增益为：Gain(A

j)=E–Ej因为Aj属性值而表现出来的信息容量为：

I(Aj)=

因此知识发现难度为：

在关系基表中，依据决策规则的需要可以将属性分为两大类:

一类是条件属性(conditionattribute)

另一类是决策属性（decisionattribute）。条件属性的值对决策属性的值有影响，甚至某一属性值的改变使得决策属性的值发生改变。例如，在超市市场决策中，可以考虑几个比较常见的影响超市销售额的因素：如地理位置，交通条件，购物环境，周围人均工资等，这几个因素称为条件属性，而销售额则是受这几个因素影响的，任何一个项值的改变都可能改变销售额。2.数据化简按照上述的预处理，可得到一个表（decision）,其中条件属性（C属性）为：A1，A2,….An,决策属性（D属性）为B1，B2…..Bn

如下表所示

化简就是要除去规则中的不重要的属性，减少规则中的约束条件。但化简后的决策表具有此前的决策表的功能，而化简后的决策表具有更少的条件属性。在此，我们仅考虑知识相容的情况，也即在条件属性值相同的情况下，决策属性值也相同。

化简的思想为：

若去掉某一个信息量小的属性后，知识的相容性不变，说明此属性的存在与否并不影响决策属性和条件属性之间的关系，则此属性可以省略，否则不能省。化简的步骤为：去掉信息量最小的属性删除重复行重复进行上述步骤，直到没有多余的属性存在。算法(基于属性的化简)为：输入：按上述要求得到一个整理后的表----decision,条件属性为A1，A2，……An。输出：化简后的表详细算法为：STEP1．按照某一个信息量函数计算各个属性的信息量，并将属性按信息量从小到大排序，记为Ai1,Ai2,…….Ain,STEP2.CDtable=decision,m=1,Cn=C;/*设置起始参数，进行初始化赋值*/STEP3./*第三步是算法的核心*/令Ctable=selectdistinctCnfromCDtableK=selectcount(*)fromCtable-------在决策表中，选择条件属性组成的元组，并且去掉其中的重复项。得出记录数Ｋ令CAtable=selectdistinctCn-AimfromCDtableL=selectcount(*)fromCAtable--------从条件属性中去除“侯选消去”属性Aim

，并按新的条件属性选择出元组，去掉其中的重复项．得出记录数Ｌ令Dtable=selectdistinct*-AimfromCDtableN=selectcount(*)fromDtable-------去除“侯选消去”属性，并按新的属性选择出元组，去掉其中的重复项．得出记录数Ｎ

STEP4.

进行比较。如果Ｋ＝Ｌ或Ｎ＝Ｌ，则表明Ａｉｍ的存在与否，不影响条件对决策的结果。否则，说明Ａｉｍ影响条件和决策的相互关系。

STEP5.对所有条件属性处理完毕，得到最简的决策表.

例如，我们以上面提到的例二“胜大超市信息管理系统”数据库为例进行化简。胜大超市在东营市已开了13家分店，下表给出了几家分店的赢利情况。我们的任务是通过此表，找出影响赢利的主要因素以及它们之间的近似关系。表1---相对精细的表对表离散化，将平均工资按（0，700）----1，（700，900）----2，（900，1100）----3（1100，1300）----4进行离散化，并去掉次要属性----地理位置名称得到下表表2----离散化后的表对表2按我们定义的信息量函数I（A）进行由小到大排序，可得：表3---按信息量由小到大排序后的表按照上述的化简步骤，先尝试去掉c4,将表3去掉c4后，可得新表表4---去掉c4属性后的表计算:L=5N=5满足:N=L所以C4可去掉接着尝试去掉c3,此时可得新表：表5---去掉c3属性后的表从表5即可看出，ID1和ID2有相同的条件值，却得出了不同的决策值，即知识的相容性发生了变化，说明C3的重要性同理：可以省去c2,不可以省去c1。最后可得简化的表：表6---化简后的表3、属性分析经过上述几步，得到一个简化的表9，可从表中可以得出一些规则，如只有c3=4时，D才为4，即c3=4

D=4

4.多元线形回归算法

属性间的多元线形回归模型，

y估=a0+a1X1+a2X2+….+amXm设有n个样本，即对x1,x2,….xm和y做了n次实验,或说从数据库中取出n条记录，则得到n组有关（Xi,Yi

）(i=1….,n)两个假设

H01：a1=a2=…..=am=0H02：ai=0(对某个i,1=<i<=m)验证假设S总2=

S回2=

S残2=

容易验证S总2=S回2+S残2

可用S回2和S残2

的相对大小来衡量x1,x2,…xm对y的线形影响程度。查表F=

可以证明：F属于F（m,n-m-1）分布

若用户给定水平α，

查F分布表可得λ,若F>λ,否定H01回归方程无意义的情况

(1)解释属性x1,x2,…xm对依赖属性y无影响；

(2)解释属性x1,x2,…xm对依赖属性y有影响，但不是线形的；

(3)除解释属性x1,x2,…xm对依赖属性y有影响外，还有另外不可忽略的因素对y有影响，需要进一步研究。（用统计学找回丢失的数据）

若上面得到的模型是显著的，并不能说明每一个解释属性变量是显著的，若属性变量xi对y的作用不显著，则从上面的模型中剔除xi,此时即验证假设H02------引入新的统计量---偏回归平方和Pi=S回2–Si回2,

其中Si回2

是原回归模型中去掉第i个因子后新回归模型的回归平方和。由定义可以看出Pi反映了因子xi对回归平方和的贡献，其大小可以衡量回归因子作用的主次若pi很大，说明因子xi对y的影响大；反之，则说明xi对y的影响很小，这时，应把这些因子剔除，而只保留对y影响较大的因子于回归方程中。一个因子是否应从回归模型中剔除可通过下属统计量进行检验：

可以证明：当H02成立时，Fi属于F（1,n-m-1）分布，若用户给定水平α，由p{Fi>λ}=α,查F分布表可得λ，当Fi>λ时，否定H02，说明在检验水平α下，解释属性xi对依赖属性y的影响是显著的，保留因子xi,否则接受H02，Fi=5.基于属性分类和回归模式相结合的模型用多元线形回归模型得到的一组数据：(m=2,n=8)实验结果由实验结果知：所求的最优回归方程是：Y=-0.149+0.905X1+0.252X2；

当给定水平α=0.10时，模型显著；当给定水平α=0.05时，模型显著；当给定水平α=0.025时，模型不显著；即“销售额”与“平均工资”和“交通条件”成线形关系的90%<置信度<=95%,可以认为线形关系成立。

粗糙集(Roughset)理论是1982年由波兰学者Z.Pawlak

针对G..Frege的边界线区域思想提出的处理含糊和不确定性问题的新型数学工具。其主要思想是利用已知的知识库，将知识理解为对数据的划分，每一被划分的集合称为概念，将不确定或不精确的知识用已知的知识库中的知识来刻画。该理论是建立在分类机制基础上的，它将分类理解为在特定空间上的等价关系，而等价关系构成了对该空间的划分。

粗集理论简洁由于粗糙集理论思想新颖、方法独特，粗糙集理论已成为一种重要的智能信息处理技术，该理论已经在机器学习与知识发现、数据挖掘、决策支持与分析等方面得到广泛应用。目前，有三个有关粗糙集的系列国际会议，即：RSCTC、RSFDGrC和RSKT。中国学者在这方面也取得了很大的成果，从2001年开始每年召开中国粗糙集与软计算学术会议；RSFDGRC2003、IEEEGrC2005、RSKT2006、IFKT2008、RSKT2008、IEEEGrC2008等一系列国际学术会议在中国召开。目前主要研究内容

属性约简

规则获取

基于粗糙集的计算智能算法研究等应用领域

工业控制

医学卫生及生物科学

交通运输

农业科学

环境科学与环境保护管理

安全科学

社会科学

航空

航天和军事等领域。具体应用如下：电厂气温过热控制虚拟现实的可视化对原棉纱线强度和纤维性能之间的知识规则提取手写体识别胸部X线数字图像滤波增强湖泊生态系统健康评定指数法的评价医疗图像处理遥感数据处理综合分类器设计与实现铁路行车调度指挥食品安全综合评价昆虫总科阶元分类泥石流危险度区划指标选取

网络故障诊断上市公司违规行为预警武器系统灰色关联评估和航空控制等等。

粗集理论基于不完全的数据或信息，给出所需概念的

下近似（即必然属于此概念的个体）

上近似（即可能属于此概念的个体）描述。对应于下近似和上近似的描述给出相应的必然和可能的决策规则。粗集示意图如：甲流，非典等

粗集理论被证明特别适合于数据化简,数据相关性、相似性的查找，发现数据模式，从数据中提取推理规则等。通过粗集理论主要能够解决如下问题:

进行信息表中各属性的重要性评价并寻找主导属性；在保证分类质量不变的前提下寻求最小属性集；消除信息表中的冗余属性；从约简后的信息表中提取决策规则。

粗集约简包括属性约简和值约简。

粗集约简方法属性约简方法：（1）数据分析方法

（2）差别矩阵方法值约简方法：

数据分析方法从信息系统的决策表中，将属性集C中的属性逐个移去，每移去一个属性即刻检查其决策表，如果不出现新的不一致，则该属性是可被约去的；否则该属性不能被约去，称这种方法为属性约简的数据分析方法。利用差别矩阵产生约简的过程为：（1）计算决策表T的差别矩阵；（2）计算与差别矩阵相关的差别函数；（3）计算差别函数的最小析取范式，它将给出所有的约简。

最小约简算法基于属性重要性最小约简算法基于差别矩阵最小约简算法RedFreSigni算法该算法是在以上两种算法基础上的改进。定义1：信息系统和决策系统信息系统（informationsystem,IS）是一个四元组IS=<U,A,V,f>，其中：

U为对象的非空有限集合，简称对象集，称为论域；

A为属性的非空有限集合，简称属性集

V是属性的值域集合

f为信息函数f：U×A→V，即任意a∈A，x∈U，f(x,a)∈V。有时IS可以简化为IS=<U,A>。例如下表就是一个信息系统，其中论域，属性集

若属性集A由条件属性C和决策属性D组成，且C∩D=Φ，C∪D=A，则称IS为决策系统，记作DS=<U,(C,D)>，也简称为CD决策表或信息表。

可见，决策表是一类特殊而重要的信息系统，是一种条件、行为表，当满足某些条件时，决策（行为）应当怎样进行。多数决策问题都可以用决策表形式来表达，因此这一工具在决策应用中起着重要的作用。定义2：等价关系信息系统IS=<U,A,V,f>，设R

A，等价关系IND(R)定义为：IND(R)={(xi,x

j)∈U×U|对任意a∈R,f(xi,a)=f(x

j,a)},xi,xj对属性R而言具有相同属性值vr,则称xi,xj是等价的，xi,xj是论域对象。在用关系表表示的信息系统中，可以认为是唯一标识的元组号。依此可得：IND(D)是对决策属性D的值进行分类成{D1,D2,D3,…..Dn}个类；IND(C)是对条件属性C的值进行分类成{C1

，C2，C3，…..Cm}个类

定义3：等价类设R

A，对任意x∈U，关于R的等价类[x]R

定义为：[x]R={y∈U|(x,y)∈IND(R)}定义4：上下近似及边界设X

U，R

A，则X对于R的下近似R*(X)和上近似R*(X)及边界BNR(X)定义为：通常，也把POSRX）=R*(X)称为X的正域，正域POSRX）或R*(X)---对于知识R，U中所有一定能归入X的元素的集合；R*(X)是对于知识R，U中可能归入X的元素的集合；BNR(X)是对知识R既不能归入X，也不能归入-X的元素的集合。如在上述病人信息表(头痛，肌肉痛，体温）中，出现e7={是，酸，高｝R={头痛，肌肉痛}则R*(X)=｛e1,e2,e3}R*(X)={e1,e2,e3,e7}

定义5：粗糙度、依赖度和重要性①X的粗糙度λ：λ=card(R*(X))/card(R*(X))(公式5-1)其中card表示集合的基数。是用X的下和上近似集成员个数之比来度量的。②X的依赖度γC(X)：γC(X)=card(R*(X))/card(U)(公式5-2)是用X的下近似集成员个数与对象集成员个数之比来度量

这样,粗糙集概念可以通过两个精确概念(上近似和下近似)来粗糙定义,这就使我们可以精确讲述不精确的概念③属性ａ对条件属性子集H的重要性属性的重要性,记为βa(R),其形式定义为βa(R)=γH∪{a}(R)-γH(R)(公式5-3)

表示从属性集去掉属性ａ对对象分类时，分类U/R的正域受到怎样的影响。若去掉该属性会相应地改变分类，即改变正域，则说明该属性的强度大，即重要性高；反之说明该属性的强度小，即重要性低。定义6：属性的核对于任一属性a∈C，如果IND(C)≠IND(C_{a})，则称a为C中不可省略的；否则，a为C中可省略的。

C中所有不可省略关系的集合称为C的核，记为CORD(C)。

约简与核(Decisiontable,reductandcore)

约简(reduct)：不含多余属性并保证分类正确

的最小条件属性集。

核(core)：一个决策表可能同时存在几个约简,这

些约简的交集定义为决策表的核。

上面的例子中，{a,c}，{b,c}都是约简，它们都不含多余属性，并保证分类正确。

{c}是核。

“约简”和“核”这两个概念很重要,是RS方法的精华。计算约简的复杂性随着决策表的增大呈指数增长,是一个典型的NP完全问题。决策表的化简决策表化简就是化简决策表中的条件属性，除去规则中的不重要的属性，减少规则中的约束条件。化简后的决策表具有此前的决策表的功能，而化简后的决策表具有更少的条件属性。

数据挖掘中的属性约简

Rough集理论支持DM的多个步骤，如数据预处理、数据约简、规则生成、数据依赖关系发现等，因此基于Rough集理论方法成为KDD主流方法之一算法1：DM属性约简----RSDM算法输入：离散化的决策表，条件属性为C1，C2，……Cm，决策属性为D。输出：该决策表的一个知识约简R。STEP1计算C的核，并赋给R，即R=KCD；①根据公式5-2计算决策属性D对各个条件属性Ci的依赖度γCi(D)，并将条件属性根据依赖度从小到大排序，记为A1,A2,…Am；②KCD={A1,A2,…Am}；③fori=1tom从条件属性去除依赖度最小属性，若去掉该属性Ai，正域不改变，则KCD=KCD-{Ai}；否则，KCD不变进行下一属性的处理。

STEP2:分别计算POSR(D)和POSC(D),若POSR(D)=POSC(D)，则算法结束；STEP3:根据公式5-3计算每个属性x∈C-R的重要性，并找出其最大者ａM，R=R∪{ａM}；STEP4:转STEP2。RSDM算法结束后，得到R中的属性即是所求的约简后属性，从而得到对于决策属性最有用的信息。举例

将粗集法应用于设备故障诊断主要是消除信息表中的冗余属性，降低特征维数。由于描述设备运行状态的特征往往很多，如石化总厂对重油催化车间的烟机采集转速，